1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "base/arena_allocator.h"
18 #include "builder.h"
19 #include "induction_var_analysis.h"
20 #include "induction_var_range.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23
24 namespace art {
25
26 using Value = InductionVarRange::Value;
27
28 /**
29 * Fixture class for the InductionVarRange tests.
30 */
31 class InductionVarRangeTest : public CommonCompilerTest {
32 public:
InductionVarRangeTest()33 InductionVarRangeTest()
34 : pool_(),
35 allocator_(&pool_),
36 graph_(CreateGraph(&allocator_)),
37 iva_(new (&allocator_) HInductionVarAnalysis(graph_)),
38 range_(iva_) {
39 BuildGraph();
40 }
41
~InductionVarRangeTest()42 ~InductionVarRangeTest() { }
43
ExpectEqual(Value v1,Value v2)44 void ExpectEqual(Value v1, Value v2) {
45 EXPECT_EQ(v1.instruction, v2.instruction);
46 EXPECT_EQ(v1.a_constant, v2.a_constant);
47 EXPECT_EQ(v1.b_constant, v2.b_constant);
48 EXPECT_EQ(v1.is_known, v2.is_known);
49 }
50
ExpectInt(int32_t value,HInstruction * i)51 void ExpectInt(int32_t value, HInstruction* i) {
52 ASSERT_TRUE(i->IsIntConstant());
53 EXPECT_EQ(value, i->AsIntConstant()->GetValue());
54 }
55
56 //
57 // Construction methods.
58 //
59
60 /** Constructs bare minimum graph. */
BuildGraph()61 void BuildGraph() {
62 graph_->SetNumberOfVRegs(1);
63 entry_block_ = new (&allocator_) HBasicBlock(graph_);
64 exit_block_ = new (&allocator_) HBasicBlock(graph_);
65 graph_->AddBlock(entry_block_);
66 graph_->AddBlock(exit_block_);
67 graph_->SetEntryBlock(entry_block_);
68 graph_->SetExitBlock(exit_block_);
69 // Two parameters.
70 x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(),
71 dex::TypeIndex(0),
72 0,
73 Primitive::kPrimInt);
74 entry_block_->AddInstruction(x_);
75 y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(),
76 dex::TypeIndex(0),
77 0,
78 Primitive::kPrimInt);
79 entry_block_->AddInstruction(y_);
80 // Set arbitrary range analysis hint while testing private methods.
81 SetHint(x_);
82 }
83
84 /** Constructs loop with given upper bound. */
BuildLoop(int32_t lower,HInstruction * upper,int32_t stride)85 void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) {
86 // Control flow.
87 loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
88 graph_->AddBlock(loop_preheader_);
89 loop_header_ = new (&allocator_) HBasicBlock(graph_);
90 graph_->AddBlock(loop_header_);
91 loop_body_ = new (&allocator_) HBasicBlock(graph_);
92 graph_->AddBlock(loop_body_);
93 HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_);
94 graph_->AddBlock(return_block);
95 entry_block_->AddSuccessor(loop_preheader_);
96 loop_preheader_->AddSuccessor(loop_header_);
97 loop_header_->AddSuccessor(loop_body_);
98 loop_header_->AddSuccessor(return_block);
99 loop_body_->AddSuccessor(loop_header_);
100 return_block->AddSuccessor(exit_block_);
101 // Instructions.
102 loop_preheader_->AddInstruction(new (&allocator_) HGoto());
103 HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
104 loop_header_->AddPhi(phi);
105 phi->AddInput(graph_->GetIntConstant(lower)); // i = l
106 if (stride > 0) {
107 condition_ = new (&allocator_) HLessThan(phi, upper); // i < u
108 } else {
109 condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u
110 }
111 loop_header_->AddInstruction(condition_);
112 loop_header_->AddInstruction(new (&allocator_) HIf(condition_));
113 increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride));
114 loop_body_->AddInstruction(increment_); // i += s
115 phi->AddInput(increment_);
116 loop_body_->AddInstruction(new (&allocator_) HGoto());
117 return_block->AddInstruction(new (&allocator_) HReturnVoid());
118 exit_block_->AddInstruction(new (&allocator_) HExit());
119 }
120
121 /** Constructs SSA and performs induction variable analysis. */
PerformInductionVarAnalysis()122 void PerformInductionVarAnalysis() {
123 graph_->BuildDominatorTree();
124 iva_->Run();
125 }
126
127 /** Sets hint. */
SetHint(HInstruction * hint)128 void SetHint(HInstruction* hint) {
129 range_.chase_hint_ = hint;
130 }
131
132 /** Constructs an invariant. */
CreateInvariant(char opc,HInductionVarAnalysis::InductionInfo * a,HInductionVarAnalysis::InductionInfo * b)133 HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc,
134 HInductionVarAnalysis::InductionInfo* a,
135 HInductionVarAnalysis::InductionInfo* b) {
136 HInductionVarAnalysis::InductionOp op;
137 switch (opc) {
138 case '+': op = HInductionVarAnalysis::kAdd; break;
139 case '-': op = HInductionVarAnalysis::kSub; break;
140 case 'n': op = HInductionVarAnalysis::kNeg; break;
141 case '*': op = HInductionVarAnalysis::kMul; break;
142 case '/': op = HInductionVarAnalysis::kDiv; break;
143 case '%': op = HInductionVarAnalysis::kRem; break;
144 case '^': op = HInductionVarAnalysis::kXor; break;
145 case '<': op = HInductionVarAnalysis::kLT; break;
146 default: op = HInductionVarAnalysis::kNop; break;
147 }
148 return iva_->CreateInvariantOp(op, a, b);
149 }
150
151 /** Constructs a fetch. */
CreateFetch(HInstruction * fetch)152 HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) {
153 return iva_->CreateInvariantFetch(fetch);
154 }
155
156 /** Constructs a constant. */
CreateConst(int32_t c)157 HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) {
158 return CreateFetch(graph_->GetIntConstant(c));
159 }
160
161 /** Constructs a constant trip-count. */
CreateTripCount(int32_t tc,bool in_loop,bool safe)162 HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
163 HInductionVarAnalysis::InductionOp op = HInductionVarAnalysis::kTripCountInBodyUnsafe;
164 if (in_loop && safe) {
165 op = HInductionVarAnalysis::kTripCountInLoop;
166 } else if (in_loop) {
167 op = HInductionVarAnalysis::kTripCountInLoopUnsafe;
168 } else if (safe) {
169 op = HInductionVarAnalysis::kTripCountInBody;
170 }
171 // Return TC with taken-test 0 < TC.
172 return iva_->CreateTripCount(op,
173 CreateConst(tc),
174 CreateInvariant('<', CreateConst(0), CreateConst(tc)),
175 Primitive::kPrimInt);
176 }
177
178 /** Constructs a linear a * i + b induction. */
CreateLinear(int32_t a,int32_t b)179 HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) {
180 return iva_->CreateInduction(HInductionVarAnalysis::kLinear,
181 HInductionVarAnalysis::kNop,
182 CreateConst(a),
183 CreateConst(b),
184 nullptr,
185 Primitive::kPrimInt);
186 }
187
188 /** Constructs a polynomial sum(a * i + b) + c induction. */
CreatePolynomial(int32_t a,int32_t b,int32_t c)189 HInductionVarAnalysis::InductionInfo* CreatePolynomial(int32_t a, int32_t b, int32_t c) {
190 return iva_->CreateInduction(HInductionVarAnalysis::kPolynomial,
191 HInductionVarAnalysis::kNop,
192 CreateLinear(a, b),
193 CreateConst(c),
194 nullptr,
195 Primitive::kPrimInt);
196 }
197
198 /** Constructs a geometric a * f^i + b induction. */
CreateGeometric(int32_t a,int32_t b,int32_t f,char op)199 HInductionVarAnalysis::InductionInfo* CreateGeometric(int32_t a, int32_t b, int32_t f, char op) {
200 return iva_->CreateInduction(HInductionVarAnalysis::kGeometric,
201 op == '*' ? HInductionVarAnalysis::kMul
202 : HInductionVarAnalysis::kDiv,
203 CreateConst(a),
204 CreateConst(b),
205 graph_->GetIntConstant(f),
206 Primitive::kPrimInt);
207 }
208
209 /** Constructs a range [lo, hi] using a periodic induction. */
CreateRange(int32_t lo,int32_t hi)210 HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) {
211 return iva_->CreateInduction(HInductionVarAnalysis::kPeriodic,
212 HInductionVarAnalysis::kNop,
213 CreateConst(lo),
214 CreateConst(hi),
215 nullptr,
216 Primitive::kPrimInt);
217 }
218
219 /** Constructs a wrap-around induction consisting of a constant, followed by info. */
CreateWrapAround(int32_t initial,HInductionVarAnalysis::InductionInfo * info)220 HInductionVarAnalysis::InductionInfo* CreateWrapAround(
221 int32_t initial,
222 HInductionVarAnalysis::InductionInfo* info) {
223 return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround,
224 HInductionVarAnalysis::kNop,
225 CreateConst(initial),
226 info,
227 nullptr,
228 Primitive::kPrimInt);
229 }
230
231 /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
CreateWrapAround(int32_t initial,int32_t lo,int32_t hi)232 HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
233 return CreateWrapAround(initial, CreateRange(lo, hi));
234 }
235
236 //
237 // Relay methods.
238 //
239
NeedsTripCount(HInductionVarAnalysis::InductionInfo * info)240 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
241 int64_t s = 0;
242 return range_.NeedsTripCount(info, &s);
243 }
244
IsBodyTripCount(HInductionVarAnalysis::InductionInfo * trip)245 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
246 return range_.IsBodyTripCount(trip);
247 }
248
IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo * trip)249 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
250 return range_.IsUnsafeTripCount(trip);
251 }
252
GetMin(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)253 Value GetMin(HInductionVarAnalysis::InductionInfo* info,
254 HInductionVarAnalysis::InductionInfo* trip) {
255 return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ true);
256 }
257
GetMax(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)258 Value GetMax(HInductionVarAnalysis::InductionInfo* info,
259 HInductionVarAnalysis::InductionInfo* trip) {
260 return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ false);
261 }
262
GetMul(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)263 Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
264 HInductionVarAnalysis::InductionInfo* info2,
265 bool is_min) {
266 return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min);
267 }
268
GetDiv(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)269 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
270 HInductionVarAnalysis::InductionInfo* info2,
271 bool is_min) {
272 return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
273 }
274
GetRem(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2)275 Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
276 HInductionVarAnalysis::InductionInfo* info2) {
277 return range_.GetRem(info1, info2);
278 }
279
GetXor(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2)280 Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
281 HInductionVarAnalysis::InductionInfo* info2) {
282 return range_.GetXor(info1, info2);
283 }
284
IsExact(HInductionVarAnalysis::InductionInfo * info,int64_t * value)285 bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
286 return range_.IsConstant(info, InductionVarRange::kExact, value);
287 }
288
IsAtMost(HInductionVarAnalysis::InductionInfo * info,int64_t * value)289 bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
290 return range_.IsConstant(info, InductionVarRange::kAtMost, value);
291 }
292
IsAtLeast(HInductionVarAnalysis::InductionInfo * info,int64_t * value)293 bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
294 return range_.IsConstant(info, InductionVarRange::kAtLeast, value);
295 }
296
AddValue(Value v1,Value v2)297 Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
SubValue(Value v1,Value v2)298 Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); }
MulValue(Value v1,Value v2)299 Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); }
DivValue(Value v1,Value v2)300 Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); }
MinValue(Value v1,Value v2)301 Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); }
MaxValue(Value v1,Value v2)302 Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); }
303
304 // General building fields.
305 ArenaPool pool_;
306 ArenaAllocator allocator_;
307 HGraph* graph_;
308 HBasicBlock* entry_block_;
309 HBasicBlock* exit_block_;
310 HBasicBlock* loop_preheader_;
311 HBasicBlock* loop_header_;
312 HBasicBlock* loop_body_;
313 HInductionVarAnalysis* iva_;
314 InductionVarRange range_;
315
316 // Instructions.
317 HInstruction* condition_;
318 HInstruction* increment_;
319 HInstruction* x_;
320 HInstruction* y_;
321 };
322
323 //
324 // Tests on private methods.
325 //
326
TEST_F(InductionVarRangeTest,IsConstant)327 TEST_F(InductionVarRangeTest, IsConstant) {
328 int64_t value;
329 // Constant.
330 EXPECT_TRUE(IsExact(CreateConst(12345), &value));
331 EXPECT_EQ(12345, value);
332 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value));
333 EXPECT_EQ(12345, value);
334 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value));
335 EXPECT_EQ(12345, value);
336 // Constant trivial range.
337 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value));
338 EXPECT_EQ(111, value);
339 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value));
340 EXPECT_EQ(111, value);
341 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value));
342 EXPECT_EQ(111, value);
343 // Constant non-trivial range.
344 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value));
345 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value));
346 EXPECT_EQ(22, value);
347 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value));
348 EXPECT_EQ(11, value);
349 // Symbolic.
350 EXPECT_FALSE(IsExact(CreateFetch(x_), &value));
351 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value));
352 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value));
353 }
354
TEST_F(InductionVarRangeTest,TripCountProperties)355 TEST_F(InductionVarRangeTest, TripCountProperties) {
356 EXPECT_FALSE(NeedsTripCount(nullptr));
357 EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
358 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1)));
359 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3)));
360 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1))));
361
362 EXPECT_FALSE(IsBodyTripCount(nullptr));
363 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true)));
364 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false)));
365 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true)));
366 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false)));
367
368 EXPECT_FALSE(IsUnsafeTripCount(nullptr));
369 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true)));
370 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false)));
371 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true)));
372 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false)));
373 }
374
TEST_F(InductionVarRangeTest,GetMinMaxNull)375 TEST_F(InductionVarRangeTest, GetMinMaxNull) {
376 ExpectEqual(Value(), GetMin(nullptr, nullptr));
377 ExpectEqual(Value(), GetMax(nullptr, nullptr));
378 }
379
TEST_F(InductionVarRangeTest,GetMinMaxAdd)380 TEST_F(InductionVarRangeTest, GetMinMaxAdd) {
381 ExpectEqual(Value(12),
382 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
383 ExpectEqual(Value(22),
384 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
385 ExpectEqual(Value(x_, 1, -20),
386 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
387 ExpectEqual(Value(x_, 1, -10),
388 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
389 ExpectEqual(Value(x_, 1, 10),
390 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
391 ExpectEqual(Value(x_, 1, 20),
392 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
393 ExpectEqual(Value(5),
394 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
395 ExpectEqual(Value(19),
396 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
397 }
398
TEST_F(InductionVarRangeTest,GetMinMaxSub)399 TEST_F(InductionVarRangeTest, GetMinMaxSub) {
400 ExpectEqual(Value(-18),
401 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
402 ExpectEqual(Value(-8),
403 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
404 ExpectEqual(Value(x_, 1, 10),
405 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
406 ExpectEqual(Value(x_, 1, 20),
407 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
408 ExpectEqual(Value(x_, -1, 10),
409 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
410 ExpectEqual(Value(x_, -1, 20),
411 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
412 ExpectEqual(Value(-25),
413 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
414 ExpectEqual(Value(-11),
415 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
416 }
417
TEST_F(InductionVarRangeTest,GetMinMaxNeg)418 TEST_F(InductionVarRangeTest, GetMinMaxNeg) {
419 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
420 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
421 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
422 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
423 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
424 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
425 }
426
TEST_F(InductionVarRangeTest,GetMinMaxMul)427 TEST_F(InductionVarRangeTest, GetMinMaxMul) {
428 ExpectEqual(Value(20),
429 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
430 ExpectEqual(Value(40),
431 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
432 }
433
TEST_F(InductionVarRangeTest,GetMinMaxDiv)434 TEST_F(InductionVarRangeTest, GetMinMaxDiv) {
435 ExpectEqual(Value(3),
436 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
437 ExpectEqual(Value(5),
438 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
439 }
440
TEST_F(InductionVarRangeTest,GetMinMaxConstant)441 TEST_F(InductionVarRangeTest, GetMinMaxConstant) {
442 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr));
443 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr));
444 }
445
TEST_F(InductionVarRangeTest,GetMinMaxFetch)446 TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
447 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr));
448 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr));
449 }
450
TEST_F(InductionVarRangeTest,GetMinMaxLinear)451 TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
452 ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true)));
453 ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true)));
454 ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
455 ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
456 }
457
TEST_F(InductionVarRangeTest,GetMinMaxWrapAround)458 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
459 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr));
460 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr));
461 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr));
462 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr));
463 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr));
464 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
465 }
466
TEST_F(InductionVarRangeTest,GetMinMaxPolynomial)467 TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) {
468 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr));
469 ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr));
470 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
471 ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
472 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
473 ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
474 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
475 CreateTripCount(5, true, true)));
476 ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7),
477 CreateTripCount(5, true, true)));
478 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
479 CreateTripCount(10, true, true)));
480 ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7),
481 CreateTripCount(10, true, true)));
482 ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
483 ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
484 ExpectEqual(Value(), GetMin(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
485 ExpectEqual(Value(), GetMax(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
486 }
487
TEST_F(InductionVarRangeTest,GetMinMaxGeometricMul)488 TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) {
489 ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr));
490 ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr));
491 }
492
TEST_F(InductionVarRangeTest,GetMinMaxGeometricDiv)493 TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) {
494 ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr));
495 ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr));
496 ExpectEqual(Value(-5), GetMin(CreateGeometric(11, -5, 3, '/'), nullptr));
497 ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '/'), nullptr));
498 ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '/'), nullptr));
499 ExpectEqual(Value(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr));
500 ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr));
501 ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr));
502 }
503
TEST_F(InductionVarRangeTest,GetMinMaxPeriodic)504 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) {
505 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr));
506 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr));
507 }
508
TEST_F(InductionVarRangeTest,GetMulMin)509 TEST_F(InductionVarRangeTest, GetMulMin) {
510 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true));
511 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true));
512 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true));
513 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true));
514 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true));
515 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true));
516 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true));
517 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true));
518 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true));
519 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true));
520 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true));
521 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true));
522 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true));
523 }
524
TEST_F(InductionVarRangeTest,GetMulMax)525 TEST_F(InductionVarRangeTest, GetMulMax) {
526 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false));
527 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false));
528 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false));
529 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false));
530 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false));
531 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false));
532 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false));
533 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false));
534 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false));
535 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false));
536 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false));
537 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false));
538 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false));
539 }
540
TEST_F(InductionVarRangeTest,GetDivMin)541 TEST_F(InductionVarRangeTest, GetDivMin) {
542 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true));
543 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true));
544 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true));
545 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true));
546 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true));
547 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true));
548 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true));
549 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true));
550 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true));
551 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true));
552 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true));
553 }
554
TEST_F(InductionVarRangeTest,GetDivMax)555 TEST_F(InductionVarRangeTest, GetDivMax) {
556 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false));
557 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false));
558 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false));
559 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false));
560 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false));
561 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false));
562 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
563 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false));
564 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false));
565 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false));
566 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
567 }
568
TEST_F(InductionVarRangeTest,GetMinMaxRem)569 TEST_F(InductionVarRangeTest, GetMinMaxRem) {
570 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
571 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
572 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
573 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
574 ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
575 ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
576 ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
577 ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
578 }
579
TEST_F(InductionVarRangeTest,GetRem)580 TEST_F(InductionVarRangeTest, GetRem) {
581 ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1)));
582 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5)));
583 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5)));
584 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(5)));
585 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(5)));
586 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(-5)));
587 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(-5)));
588 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(-5)));
589 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(-5)));
590 ExpectEqual(Value(), GetRem(CreateConst(1), CreateConst(0)));
591 }
592
TEST_F(InductionVarRangeTest,GetMinMaxXor)593 TEST_F(InductionVarRangeTest, GetMinMaxXor) {
594 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
595 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
596 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
597 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
598 ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
599 ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
600 }
601
TEST_F(InductionVarRangeTest,GetXor)602 TEST_F(InductionVarRangeTest, GetXor) {
603 ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1)));
604 ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2)));
605 ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1)));
606 ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1)));
607 }
608
TEST_F(InductionVarRangeTest,AddValue)609 TEST_F(InductionVarRangeTest, AddValue) {
610 ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
611 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
612 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1)));
613 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7)));
614 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3)));
615 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50)));
616 const int32_t max_value = std::numeric_limits<int32_t>::max();
617 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5)));
618 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe
619 }
620
TEST_F(InductionVarRangeTest,SubValue)621 TEST_F(InductionVarRangeTest, SubValue) {
622 ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
623 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1)));
624 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1)));
625 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7)));
626 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3)));
627 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50)));
628 const int32_t min_value = std::numeric_limits<int32_t>::min();
629 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5)));
630 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe
631 }
632
TEST_F(InductionVarRangeTest,MulValue)633 TEST_F(InductionVarRangeTest, MulValue) {
634 ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
635 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1)));
636 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7)));
637 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3)));
638 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2)));
639 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe
640 }
641
TEST_F(InductionVarRangeTest,MulValueSpecial)642 TEST_F(InductionVarRangeTest, MulValueSpecial) {
643 const int32_t min_value = std::numeric_limits<int32_t>::min();
644 const int32_t max_value = std::numeric_limits<int32_t>::max();
645
646 // Unsafe.
647 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value)));
648 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1)));
649 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value)));
650 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value)));
651
652 // Safe.
653 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1)));
654 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1)));
655 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1)));
656 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1)));
657 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1)));
658 }
659
TEST_F(InductionVarRangeTest,DivValue)660 TEST_F(InductionVarRangeTest, DivValue) {
661 ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
662 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1)));
663 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7)));
664 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3)));
665 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50)));
666 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe
667 }
668
TEST_F(InductionVarRangeTest,DivValueSpecial)669 TEST_F(InductionVarRangeTest, DivValueSpecial) {
670 const int32_t min_value = std::numeric_limits<int32_t>::min();
671 const int32_t max_value = std::numeric_limits<int32_t>::max();
672
673 // Unsafe.
674 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1)));
675
676 // Safe.
677 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value)));
678 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value)));
679 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1)));
680 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1)));
681 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1)));
682 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1)));
683 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1)));
684 }
685
TEST_F(InductionVarRangeTest,MinValue)686 TEST_F(InductionVarRangeTest, MinValue) {
687 ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
688 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1)));
689 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1)));
690 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7)));
691 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3)));
692 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50)));
693 }
694
TEST_F(InductionVarRangeTest,MaxValue)695 TEST_F(InductionVarRangeTest, MaxValue) {
696 ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
697 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1)));
698 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1)));
699 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7)));
700 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3)));
701 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50)));
702 }
703
TEST_F(InductionVarRangeTest,ArrayLengthAndHints)704 TEST_F(InductionVarRangeTest, ArrayLengthAndHints) {
705 // We pass a bogus constant for the class to avoid mocking one.
706 HInstruction* new_array = new (&allocator_) HNewArray(x_, x_, 0);
707 entry_block_->AddInstruction(new_array);
708 HInstruction* array_length = new (&allocator_) HArrayLength(new_array, 0);
709 entry_block_->AddInstruction(array_length);
710 // With null hint: yields extreme constants.
711 const int32_t max_value = std::numeric_limits<int32_t>::max();
712 SetHint(nullptr);
713 ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr));
714 ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr));
715 // With explicit hint: yields the length instruction.
716 SetHint(array_length);
717 ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr));
718 ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr));
719 // With any non-null hint: chases beyond the length instruction.
720 SetHint(x_);
721 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr));
722 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr));
723 }
724
725 //
726 // Tests on public methods.
727 //
728
TEST_F(InductionVarRangeTest,ConstantTripCountUp)729 TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
730 BuildLoop(0, graph_->GetIntConstant(1000), 1);
731 PerformInductionVarAnalysis();
732
733 Value v1, v2;
734 bool needs_finite_test = true;
735 bool needs_taken_test = true;
736
737 HInstruction* phi = condition_->InputAt(0);
738 HInstruction* exit = exit_block_->GetLastInstruction();
739
740 // In context of header: known.
741 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
742 EXPECT_FALSE(needs_finite_test);
743 ExpectEqual(Value(0), v1);
744 ExpectEqual(Value(1000), v2);
745
746 // In context of loop-body: known.
747 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
748 EXPECT_FALSE(needs_finite_test);
749 ExpectEqual(Value(0), v1);
750 ExpectEqual(Value(999), v2);
751 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
752 EXPECT_FALSE(needs_finite_test);
753 ExpectEqual(Value(1), v1);
754 ExpectEqual(Value(1000), v2);
755
756 // Induction vs. no-induction.
757 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
758 EXPECT_TRUE(range_.CanGenerateLastValue(phi));
759 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test));
760 EXPECT_FALSE(range_.CanGenerateLastValue(exit));
761
762 // Last value (unsimplified).
763 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
764 ASSERT_TRUE(last->IsAdd());
765 ExpectInt(1000, last->InputAt(0));
766 ExpectInt(0, last->InputAt(1));
767
768 // Loop logic.
769 int64_t tc = 0;
770 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
771 EXPECT_EQ(1000, tc);
772 HInstruction* offset = nullptr;
773 EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
774 EXPECT_TRUE(offset == nullptr);
775 HInstruction* tce = range_.GenerateTripCount(
776 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
777 ASSERT_TRUE(tce != nullptr);
778 ExpectInt(1000, tce);
779 }
780
TEST_F(InductionVarRangeTest,ConstantTripCountDown)781 TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
782 BuildLoop(1000, graph_->GetIntConstant(0), -1);
783 PerformInductionVarAnalysis();
784
785 Value v1, v2;
786 bool needs_finite_test = true;
787 bool needs_taken_test = true;
788
789 HInstruction* phi = condition_->InputAt(0);
790 HInstruction* exit = exit_block_->GetLastInstruction();
791
792 // In context of header: known.
793 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
794 EXPECT_FALSE(needs_finite_test);
795 ExpectEqual(Value(0), v1);
796 ExpectEqual(Value(1000), v2);
797
798 // In context of loop-body: known.
799 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
800 EXPECT_FALSE(needs_finite_test);
801 ExpectEqual(Value(1), v1);
802 ExpectEqual(Value(1000), v2);
803 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
804 EXPECT_FALSE(needs_finite_test);
805 ExpectEqual(Value(0), v1);
806 ExpectEqual(Value(999), v2);
807
808 // Induction vs. no-induction.
809 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
810 EXPECT_TRUE(range_.CanGenerateLastValue(phi));
811 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test));
812 EXPECT_FALSE(range_.CanGenerateLastValue(exit));
813
814 // Last value (unsimplified).
815 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
816 ASSERT_TRUE(last->IsSub());
817 ExpectInt(1000, last->InputAt(0));
818 ASSERT_TRUE(last->InputAt(1)->IsNeg());
819 last = last->InputAt(1)->InputAt(0);
820 ASSERT_TRUE(last->IsSub());
821 ExpectInt(0, last->InputAt(0));
822 ExpectInt(1000, last->InputAt(1));
823
824 // Loop logic.
825 int64_t tc = 0;
826 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
827 EXPECT_EQ(1000, tc);
828 HInstruction* offset = nullptr;
829 EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
830 HInstruction* tce = range_.GenerateTripCount(
831 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
832 ASSERT_TRUE(tce != nullptr);
833 ASSERT_TRUE(tce->IsNeg());
834 last = tce->InputAt(0);
835 EXPECT_TRUE(last->IsSub());
836 ExpectInt(0, last->InputAt(0));
837 ExpectInt(1000, last->InputAt(1));
838 }
839
TEST_F(InductionVarRangeTest,SymbolicTripCountUp)840 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
841 BuildLoop(0, x_, 1);
842 PerformInductionVarAnalysis();
843
844 Value v1, v2;
845 bool needs_finite_test = true;
846 bool needs_taken_test = true;
847
848 HInstruction* phi = condition_->InputAt(0);
849
850 // In context of header: upper unknown.
851 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
852 EXPECT_FALSE(needs_finite_test);
853 ExpectEqual(Value(0), v1);
854 ExpectEqual(Value(), v2);
855
856 // In context of loop-body: known.
857 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
858 EXPECT_FALSE(needs_finite_test);
859 ExpectEqual(Value(0), v1);
860 ExpectEqual(Value(x_, 1, -1), v2);
861 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
862 EXPECT_FALSE(needs_finite_test);
863 ExpectEqual(Value(1), v1);
864 ExpectEqual(Value(x_, 1, 0), v2);
865
866 HInstruction* lower = nullptr;
867 HInstruction* upper = nullptr;
868
869 // Can generate code in context of loop-body only.
870 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test));
871 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
872 EXPECT_FALSE(needs_finite_test);
873 EXPECT_TRUE(needs_taken_test);
874
875 // Generates code (unsimplified).
876 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
877
878 // Verify lower is 0+0.
879 ASSERT_TRUE(lower != nullptr);
880 ASSERT_TRUE(lower->IsAdd());
881 ExpectInt(0, lower->InputAt(0));
882 ExpectInt(0, lower->InputAt(1));
883
884 // Verify upper is (V-1)+0.
885 ASSERT_TRUE(upper != nullptr);
886 ASSERT_TRUE(upper->IsAdd());
887 ASSERT_TRUE(upper->InputAt(0)->IsSub());
888 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue());
889 ExpectInt(1, upper->InputAt(0)->InputAt(1));
890 ExpectInt(0, upper->InputAt(1));
891
892 // Verify taken-test is 0<V.
893 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
894 ASSERT_TRUE(taken != nullptr);
895 ASSERT_TRUE(taken->IsLessThan());
896 ExpectInt(0, taken->InputAt(0));
897 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
898
899 // Replacement.
900 range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
901 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
902 EXPECT_FALSE(needs_finite_test);
903 ExpectEqual(Value(1), v1);
904 ExpectEqual(Value(y_, 1, 0), v2);
905
906 // Loop logic.
907 int64_t tc = 0;
908 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
909 EXPECT_EQ(0, tc); // unknown
910 HInstruction* offset = nullptr;
911 EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
912 EXPECT_TRUE(offset == nullptr);
913 HInstruction* tce = range_.GenerateTripCount(
914 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
915 ASSERT_TRUE(tce != nullptr);
916 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test
917 ExpectInt(0, tce->InputAt(0));
918 EXPECT_TRUE(tce->InputAt(1)->IsParameterValue());
919 EXPECT_TRUE(tce->InputAt(2)->IsLessThan());
920 }
921
TEST_F(InductionVarRangeTest,SymbolicTripCountDown)922 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
923 BuildLoop(1000, x_, -1);
924 PerformInductionVarAnalysis();
925
926 Value v1, v2;
927 bool needs_finite_test = true;
928 bool needs_taken_test = true;
929
930 HInstruction* phi = condition_->InputAt(0);
931
932 // In context of header: lower unknown.
933 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
934 EXPECT_FALSE(needs_finite_test);
935 ExpectEqual(Value(), v1);
936 ExpectEqual(Value(1000), v2);
937
938 // In context of loop-body: known.
939 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
940 EXPECT_FALSE(needs_finite_test);
941 ExpectEqual(Value(x_, 1, 1), v1);
942 ExpectEqual(Value(1000), v2);
943 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
944 EXPECT_FALSE(needs_finite_test);
945 ExpectEqual(Value(x_, 1, 0), v1);
946 ExpectEqual(Value(999), v2);
947
948 HInstruction* lower = nullptr;
949 HInstruction* upper = nullptr;
950
951 // Can generate code in context of loop-body only.
952 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test));
953 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
954 EXPECT_FALSE(needs_finite_test);
955 EXPECT_TRUE(needs_taken_test);
956
957 // Generates code (unsimplified).
958 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
959
960 // Verify lower is 1000-((1000-V)-1).
961 ASSERT_TRUE(lower != nullptr);
962 ASSERT_TRUE(lower->IsSub());
963 ExpectInt(1000, lower->InputAt(0));
964 lower = lower->InputAt(1);
965 ASSERT_TRUE(lower->IsSub());
966 ExpectInt(1, lower->InputAt(1));
967 lower = lower->InputAt(0);
968 ASSERT_TRUE(lower->IsSub());
969 ExpectInt(1000, lower->InputAt(0));
970 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue());
971
972 // Verify upper is 1000-0.
973 ASSERT_TRUE(upper != nullptr);
974 ASSERT_TRUE(upper->IsSub());
975 ExpectInt(1000, upper->InputAt(0));
976 ExpectInt(0, upper->InputAt(1));
977
978 // Verify taken-test is 1000>V.
979 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
980 ASSERT_TRUE(taken != nullptr);
981 ASSERT_TRUE(taken->IsGreaterThan());
982 ExpectInt(1000, taken->InputAt(0));
983 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
984
985 // Replacement.
986 range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
987 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
988 EXPECT_FALSE(needs_finite_test);
989 ExpectEqual(Value(y_, 1, 0), v1);
990 ExpectEqual(Value(999), v2);
991
992 // Loop logic.
993 int64_t tc = 0;
994 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
995 EXPECT_EQ(0, tc); // unknown
996 HInstruction* offset = nullptr;
997 EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
998 HInstruction* tce = range_.GenerateTripCount(
999 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
1000 ASSERT_TRUE(tce != nullptr);
1001 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test
1002 ExpectInt(0, tce->InputAt(0));
1003 EXPECT_TRUE(tce->InputAt(1)->IsSub());
1004 EXPECT_TRUE(tce->InputAt(2)->IsGreaterThan());
1005 tce = tce->InputAt(1);
1006 ExpectInt(1000, taken->InputAt(0));
1007 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
1008 }
1009
1010 } // namespace art
1011