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 "induction_var_range.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "builder.h"
22 #include "induction_var_analysis.h"
23 #include "nodes.h"
24 #include "optimizing_unit_test.h"
25
26 namespace art HIDDEN {
27
28 using Value = InductionVarRange::Value;
29
30 /**
31 * Fixture class for the InductionVarRange tests.
32 */
33 class InductionVarRangeTest : public OptimizingUnitTest {
34 public:
InductionVarRangeTest()35 InductionVarRangeTest()
36 : graph_(CreateGraph()),
37 iva_(new (GetAllocator()) 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 (GetAllocator()) HBasicBlock(graph_);
64 exit_block_ = new (GetAllocator()) 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 (GetAllocator()) HParameterValue(graph_->GetDexFile(),
71 dex::TypeIndex(0),
72 0,
73 DataType::Type::kInt32);
74 entry_block_->AddInstruction(x_);
75 y_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
76 dex::TypeIndex(0),
77 0,
78 DataType::Type::kInt32);
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 (GetAllocator()) HBasicBlock(graph_);
88 graph_->AddBlock(loop_preheader_);
89 loop_header_ = new (GetAllocator()) HBasicBlock(graph_);
90 graph_->AddBlock(loop_header_);
91 loop_body_ = new (GetAllocator()) HBasicBlock(graph_);
92 graph_->AddBlock(loop_body_);
93 HBasicBlock* return_block = new (GetAllocator()) 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 (GetAllocator()) HGoto());
103 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
104 loop_header_->AddPhi(phi);
105 phi->AddInput(graph_->GetIntConstant(lower)); // i = l
106 if (stride > 0) {
107 condition_ = new (GetAllocator()) HLessThan(phi, upper); // i < u
108 } else {
109 condition_ = new (GetAllocator()) HGreaterThan(phi, upper); // i > u
110 }
111 loop_header_->AddInstruction(condition_);
112 loop_header_->AddInstruction(new (GetAllocator()) HIf(condition_));
113 increment_ =
114 new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, graph_->GetIntConstant(stride));
115 loop_body_->AddInstruction(increment_); // i += s
116 phi->AddInput(increment_);
117 loop_body_->AddInstruction(new (GetAllocator()) HGoto());
118 return_block->AddInstruction(new (GetAllocator()) HReturnVoid());
119 exit_block_->AddInstruction(new (GetAllocator()) HExit());
120 }
121
122 /** Constructs SSA and performs induction variable analysis. */
PerformInductionVarAnalysis()123 void PerformInductionVarAnalysis() {
124 graph_->BuildDominatorTree();
125 iva_->Run();
126 }
127
128 /** Sets hint. */
SetHint(HInstruction * hint)129 void SetHint(HInstruction* hint) {
130 range_.chase_hint_ = hint;
131 }
132
133 /** Constructs an invariant. */
CreateInvariant(char opc,HInductionVarAnalysis::InductionInfo * a,HInductionVarAnalysis::InductionInfo * b)134 HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc,
135 HInductionVarAnalysis::InductionInfo* a,
136 HInductionVarAnalysis::InductionInfo* b) {
137 HInductionVarAnalysis::InductionOp op;
138 switch (opc) {
139 case '+': op = HInductionVarAnalysis::kAdd; break;
140 case '-': op = HInductionVarAnalysis::kSub; break;
141 case 'n': op = HInductionVarAnalysis::kNeg; break;
142 case '*': op = HInductionVarAnalysis::kMul; break;
143 case '/': op = HInductionVarAnalysis::kDiv; break;
144 case '%': op = HInductionVarAnalysis::kRem; break;
145 case '^': op = HInductionVarAnalysis::kXor; break;
146 case '<': op = HInductionVarAnalysis::kLT; break;
147 default: op = HInductionVarAnalysis::kNop; break;
148 }
149 // Use bogus loop information and context out of the bogus loop.
150 HLoopInformation loop(exit_block_, graph_);
151 HBasicBlock* context = entry_block_;
152 return iva_->CreateInvariantOp(context, &loop, op, a, b);
153 }
154
155 /** Constructs a fetch. */
CreateFetch(HInstruction * fetch)156 HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) {
157 return iva_->CreateInvariantFetch(fetch);
158 }
159
160 /** Constructs a constant. */
CreateConst(int32_t c)161 HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) {
162 return CreateFetch(graph_->GetIntConstant(c));
163 }
164
165 /** Constructs a constant trip-count. */
CreateTripCount(int32_t tc,bool in_loop,bool safe)166 HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
167 HInductionVarAnalysis::InductionOp op = HInductionVarAnalysis::kTripCountInBodyUnsafe;
168 if (in_loop && safe) {
169 op = HInductionVarAnalysis::kTripCountInLoop;
170 } else if (in_loop) {
171 op = HInductionVarAnalysis::kTripCountInLoopUnsafe;
172 } else if (safe) {
173 op = HInductionVarAnalysis::kTripCountInBody;
174 }
175 // Return TC with taken-test 0 < TC.
176 return iva_->CreateTripCount(op,
177 CreateConst(tc),
178 CreateInvariant('<', CreateConst(0), CreateConst(tc)),
179 DataType::Type::kInt32);
180 }
181
182 /** Constructs a linear a * i + b induction. */
CreateLinear(int32_t a,int32_t b)183 HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) {
184 return iva_->CreateInduction(HInductionVarAnalysis::kLinear,
185 HInductionVarAnalysis::kNop,
186 CreateConst(a),
187 CreateConst(b),
188 nullptr,
189 DataType::Type::kInt32);
190 }
191
192 /** Constructs a polynomial sum(a * i + b) + c induction. */
CreatePolynomial(int32_t a,int32_t b,int32_t c)193 HInductionVarAnalysis::InductionInfo* CreatePolynomial(int32_t a, int32_t b, int32_t c) {
194 return iva_->CreateInduction(HInductionVarAnalysis::kPolynomial,
195 HInductionVarAnalysis::kNop,
196 CreateLinear(a, b),
197 CreateConst(c),
198 nullptr,
199 DataType::Type::kInt32);
200 }
201
202 /** Constructs a geometric a * f^i + b induction. */
CreateGeometric(int32_t a,int32_t b,int32_t f,char op)203 HInductionVarAnalysis::InductionInfo* CreateGeometric(int32_t a, int32_t b, int32_t f, char op) {
204 return iva_->CreateInduction(HInductionVarAnalysis::kGeometric,
205 op == '*' ? HInductionVarAnalysis::kMul
206 : HInductionVarAnalysis::kDiv,
207 CreateConst(a),
208 CreateConst(b),
209 graph_->GetIntConstant(f),
210 DataType::Type::kInt32);
211 }
212
213 /** Constructs a range [lo, hi] using a periodic induction. */
CreateRange(int32_t lo,int32_t hi)214 HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) {
215 return iva_->CreateInduction(HInductionVarAnalysis::kPeriodic,
216 HInductionVarAnalysis::kNop,
217 CreateConst(lo),
218 CreateConst(hi),
219 nullptr,
220 DataType::Type::kInt32);
221 }
222
223 /** Constructs a wrap-around induction consisting of a constant, followed by info. */
CreateWrapAround(int32_t initial,HInductionVarAnalysis::InductionInfo * info)224 HInductionVarAnalysis::InductionInfo* CreateWrapAround(
225 int32_t initial,
226 HInductionVarAnalysis::InductionInfo* info) {
227 return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround,
228 HInductionVarAnalysis::kNop,
229 CreateConst(initial),
230 info,
231 nullptr,
232 DataType::Type::kInt32);
233 }
234
235 /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
CreateWrapAround(int32_t initial,int32_t lo,int32_t hi)236 HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
237 return CreateWrapAround(initial, CreateRange(lo, hi));
238 }
239
240 //
241 // Relay methods.
242 //
243
NeedsTripCount(HInductionVarAnalysis::InductionInfo * info)244 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
245 // Use bogus loop information and context out of the bogus loop.
246 HLoopInformation loop(exit_block_, graph_);
247 HBasicBlock* context = entry_block_;
248 int64_t s = 0;
249 return range_.NeedsTripCount(context, &loop, info, &s);
250 }
251
IsBodyTripCount(HInductionVarAnalysis::InductionInfo * trip)252 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
253 return range_.IsBodyTripCount(trip);
254 }
255
IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo * trip)256 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
257 return range_.IsUnsafeTripCount(trip);
258 }
259
GetMin(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)260 Value GetMin(HInductionVarAnalysis::InductionInfo* info,
261 HInductionVarAnalysis::InductionInfo* trip) {
262 // Use bogus loop information and context out of the bogus loop.
263 HLoopInformation loop(exit_block_, graph_);
264 HBasicBlock* context = entry_block_;
265 return GetMin(context, &loop, info, trip);
266 }
267
GetMin(HBasicBlock * context,HLoopInformation * loop,HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)268 Value GetMin(HBasicBlock* context,
269 HLoopInformation* loop,
270 HInductionVarAnalysis::InductionInfo* info,
271 HInductionVarAnalysis::InductionInfo* trip) {
272 return range_.GetVal(context, loop, info, trip, /*is_min=*/ true);
273 }
274
GetMax(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)275 Value GetMax(HInductionVarAnalysis::InductionInfo* info,
276 HInductionVarAnalysis::InductionInfo* trip) {
277 // Use bogus loop information and context out of the bogus loop.
278 HLoopInformation loop(exit_block_, graph_);
279 HBasicBlock* context = entry_block_;
280 return GetMax(context, &loop, info, trip);
281 }
282
GetMax(HBasicBlock * context,HLoopInformation * loop,HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip)283 Value GetMax(HBasicBlock* context,
284 HLoopInformation* loop,
285 HInductionVarAnalysis::InductionInfo* info,
286 HInductionVarAnalysis::InductionInfo* trip) {
287 return range_.GetVal(context, loop, info, trip, /*is_min=*/ false);
288 }
289
GetMul(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)290 Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
291 HInductionVarAnalysis::InductionInfo* info2,
292 bool is_min) {
293 // Use bogus loop information and context out of the bogus loop.
294 HLoopInformation loop(exit_block_, graph_);
295 HBasicBlock* context = entry_block_;
296 return range_.GetMul(context, &loop, info1, info2, nullptr, is_min);
297 }
298
GetDiv(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)299 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
300 HInductionVarAnalysis::InductionInfo* info2,
301 bool is_min) {
302 // Use bogus loop information and context out of the bogus loop.
303 HLoopInformation loop(exit_block_, graph_);
304 HBasicBlock* context = entry_block_;
305 return range_.GetDiv(context, &loop, info1, info2, nullptr, is_min);
306 }
307
GetRem(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2)308 Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
309 HInductionVarAnalysis::InductionInfo* info2) {
310 // Use bogus loop information and context out of the bogus loop.
311 HLoopInformation loop(exit_block_, graph_);
312 HBasicBlock* context = entry_block_;
313 return range_.GetRem(context, &loop, info1, info2);
314 }
315
GetXor(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2)316 Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
317 HInductionVarAnalysis::InductionInfo* info2) {
318 // Use bogus loop information and context out of the bogus loop.
319 HLoopInformation loop(exit_block_, graph_);
320 HBasicBlock* context = entry_block_;
321 return range_.GetXor(context, &loop, info1, info2);
322 }
323
IsExact(HInductionVarAnalysis::InductionInfo * info,int64_t * value)324 bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
325 // Use bogus loop information and context out of the bogus loop.
326 HLoopInformation loop(exit_block_, graph_);
327 HBasicBlock* context = entry_block_;
328 return range_.IsConstant(context, &loop, info, InductionVarRange::kExact, value);
329 }
330
IsAtMost(HInductionVarAnalysis::InductionInfo * info,int64_t * value)331 bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
332 // Use bogus loop information and context out of the bogus loop.
333 HLoopInformation loop(exit_block_, graph_);
334 HBasicBlock* context = entry_block_;
335 return range_.IsConstant(context, &loop, info, InductionVarRange::kAtMost, value);
336 }
337
IsAtLeast(HInductionVarAnalysis::InductionInfo * info,int64_t * value)338 bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
339 // Use bogus loop information and context out of the bogus loop.
340 HLoopInformation loop(exit_block_, graph_);
341 HBasicBlock* context = entry_block_;
342 return range_.IsConstant(context, &loop, info, InductionVarRange::kAtLeast, value);
343 }
344
AddValue(Value v1,Value v2)345 Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
SubValue(Value v1,Value v2)346 Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); }
MulValue(Value v1,Value v2)347 Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); }
DivValue(Value v1,Value v2)348 Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); }
MinValue(Value v1,Value v2)349 Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); }
MaxValue(Value v1,Value v2)350 Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); }
351
352 // General building fields.
353 HGraph* graph_;
354 HBasicBlock* entry_block_;
355 HBasicBlock* exit_block_;
356 HBasicBlock* loop_preheader_;
357 HBasicBlock* loop_header_;
358 HBasicBlock* loop_body_;
359 HInductionVarAnalysis* iva_;
360 InductionVarRange range_;
361
362 // Instructions.
363 HInstruction* condition_;
364 HInstruction* increment_;
365 HInstruction* x_;
366 HInstruction* y_;
367 };
368
369 //
370 // Tests on private methods.
371 //
372
TEST_F(InductionVarRangeTest,IsConstant)373 TEST_F(InductionVarRangeTest, IsConstant) {
374 int64_t value;
375 // Constant.
376 EXPECT_TRUE(IsExact(CreateConst(12345), &value));
377 EXPECT_EQ(12345, value);
378 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value));
379 EXPECT_EQ(12345, value);
380 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value));
381 EXPECT_EQ(12345, value);
382 // Constant trivial range.
383 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value));
384 EXPECT_EQ(111, value);
385 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value));
386 EXPECT_EQ(111, value);
387 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value));
388 EXPECT_EQ(111, value);
389 // Constant non-trivial range.
390 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value));
391 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value));
392 EXPECT_EQ(22, value);
393 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value));
394 EXPECT_EQ(11, value);
395 // Symbolic.
396 EXPECT_FALSE(IsExact(CreateFetch(x_), &value));
397 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value));
398 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value));
399 }
400
TEST_F(InductionVarRangeTest,TripCountProperties)401 TEST_F(InductionVarRangeTest, TripCountProperties) {
402 EXPECT_FALSE(NeedsTripCount(nullptr));
403 EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
404 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1)));
405 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3)));
406 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1))));
407
408 EXPECT_FALSE(IsBodyTripCount(nullptr));
409 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true)));
410 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false)));
411 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true)));
412 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false)));
413
414 EXPECT_FALSE(IsUnsafeTripCount(nullptr));
415 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true)));
416 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false)));
417 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true)));
418 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false)));
419 }
420
TEST_F(InductionVarRangeTest,GetMinMaxNull)421 TEST_F(InductionVarRangeTest, GetMinMaxNull) {
422 ExpectEqual(Value(), GetMin(nullptr, nullptr));
423 ExpectEqual(Value(), GetMax(nullptr, nullptr));
424 }
425
TEST_F(InductionVarRangeTest,GetMinMaxAdd)426 TEST_F(InductionVarRangeTest, GetMinMaxAdd) {
427 ExpectEqual(Value(12),
428 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
429 ExpectEqual(Value(22),
430 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
431 ExpectEqual(Value(x_, 1, -20),
432 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
433 ExpectEqual(Value(x_, 1, -10),
434 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
435 ExpectEqual(Value(x_, 1, 10),
436 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
437 ExpectEqual(Value(x_, 1, 20),
438 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
439 ExpectEqual(Value(5),
440 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
441 ExpectEqual(Value(19),
442 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
443 }
444
TEST_F(InductionVarRangeTest,GetMinMaxSub)445 TEST_F(InductionVarRangeTest, GetMinMaxSub) {
446 ExpectEqual(Value(-18),
447 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
448 ExpectEqual(Value(-8),
449 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
450 ExpectEqual(Value(x_, 1, 10),
451 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
452 ExpectEqual(Value(x_, 1, 20),
453 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
454 ExpectEqual(Value(x_, -1, 10),
455 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
456 ExpectEqual(Value(x_, -1, 20),
457 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
458 ExpectEqual(Value(-25),
459 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
460 ExpectEqual(Value(-11),
461 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
462 }
463
TEST_F(InductionVarRangeTest,GetMinMaxNeg)464 TEST_F(InductionVarRangeTest, GetMinMaxNeg) {
465 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
466 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
467 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
468 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
469 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
470 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
471 }
472
TEST_F(InductionVarRangeTest,GetMinMaxMul)473 TEST_F(InductionVarRangeTest, GetMinMaxMul) {
474 ExpectEqual(Value(20),
475 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
476 ExpectEqual(Value(40),
477 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
478 }
479
TEST_F(InductionVarRangeTest,GetMinMaxDiv)480 TEST_F(InductionVarRangeTest, GetMinMaxDiv) {
481 ExpectEqual(Value(3),
482 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
483 ExpectEqual(Value(5),
484 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
485 }
486
TEST_F(InductionVarRangeTest,GetMinMaxConstant)487 TEST_F(InductionVarRangeTest, GetMinMaxConstant) {
488 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr));
489 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr));
490 }
491
TEST_F(InductionVarRangeTest,GetMinMaxFetch)492 TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
493 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr));
494 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr));
495 }
496
TEST_F(InductionVarRangeTest,GetMinMaxLinear)497 TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
498 BuildLoop(0, graph_->GetIntConstant(100), 1);
499 PerformInductionVarAnalysis();
500 HLoopInformation* loop = loop_header_->GetLoopInformation();
501 ASSERT_TRUE(loop != nullptr);
502
503 ExpectEqual(Value(20),
504 GetMin(loop_header_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
505 ExpectEqual(Value(1020),
506 GetMax(loop_header_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
507 ExpectEqual(Value(20),
508 GetMin(loop_body_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
509 ExpectEqual(Value(1010),
510 GetMax(loop_body_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
511 ExpectEqual(Value(1020),
512 GetMin(exit_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
513 ExpectEqual(Value(1020),
514 GetMax(exit_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
515 ExpectEqual(Value(20),
516 GetMin(entry_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
517 ExpectEqual(Value(),
518 GetMax(entry_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
519
520 ExpectEqual(Value(-980),
521 GetMin(loop_header_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
522 ExpectEqual(Value(20),
523 GetMax(loop_header_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
524 ExpectEqual(Value(-970),
525 GetMin(loop_body_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
526 ExpectEqual(Value(20),
527 GetMax(loop_body_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
528 ExpectEqual(Value(-980),
529 GetMin(exit_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
530 ExpectEqual(Value(-980),
531 GetMax(exit_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
532 ExpectEqual(Value(),
533 GetMin(entry_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
534 ExpectEqual(Value(20),
535 GetMax(entry_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
536 }
537
TEST_F(InductionVarRangeTest,GetMinMaxWrapAround)538 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
539 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr));
540 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr));
541 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr));
542 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr));
543 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr));
544 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
545 }
546
TEST_F(InductionVarRangeTest,GetMinMaxPolynomial)547 TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) {
548 BuildLoop(0, graph_->GetIntConstant(100), 1);
549 PerformInductionVarAnalysis();
550 HLoopInformation* loop = loop_header_->GetLoopInformation();
551 ASSERT_TRUE(loop != nullptr);
552
553 ExpectEqual(Value(), GetMin(CreatePolynomial(3, 5, 7), nullptr));
554 ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr));
555
556 ExpectEqual(
557 Value(7),
558 GetMin(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
559 ExpectEqual(
560 Value(62),
561 GetMax(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
562 ExpectEqual(
563 Value(7),
564 GetMin(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
565 ExpectEqual(
566 Value(45),
567 GetMax(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
568 ExpectEqual(
569 Value(62),
570 GetMin(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
571 ExpectEqual(
572 Value(62),
573 GetMax(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
574 ExpectEqual(
575 Value(7),
576 GetMin(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
577 ExpectEqual(
578 Value(),
579 GetMax(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
580
581 ExpectEqual(
582 Value(7),
583 GetMin(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
584 ExpectEqual(
585 Value(192),
586 GetMax(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
587 ExpectEqual(
588 Value(7),
589 GetMin(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
590 ExpectEqual(
591 Value(160),
592 GetMax(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
593 ExpectEqual(
594 Value(192),
595 GetMin(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
596 ExpectEqual(
597 Value(192),
598 GetMax(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
599 ExpectEqual(
600 Value(7),
601 GetMin(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
602 ExpectEqual(
603 Value(),
604 GetMax(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
605
606 ExpectEqual(
607 Value(-7),
608 GetMin(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
609 ExpectEqual(
610 Value(168),
611 GetMax(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
612 ExpectEqual(
613 Value(-7),
614 GetMin(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
615 ExpectEqual(
616 Value(111),
617 GetMax(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
618 ExpectEqual(
619 Value(168),
620 GetMin(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
621 ExpectEqual(
622 Value(168),
623 GetMax(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
624 ExpectEqual(
625 Value(-7),
626 GetMin(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
627 ExpectEqual(
628 Value(),
629 GetMax(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
630
631 ExpectEqual(
632 Value(-7),
633 GetMin(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
634 ExpectEqual(
635 Value(618),
636 GetMax(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
637 ExpectEqual(
638 Value(-7),
639 GetMin(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
640 ExpectEqual(
641 Value(506),
642 GetMax(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
643 ExpectEqual(
644 Value(618),
645 GetMin(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
646 ExpectEqual(
647 Value(618),
648 GetMax(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
649 ExpectEqual(
650 Value(-7),
651 GetMin(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
652 ExpectEqual(
653 Value(),
654 GetMax(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
655
656 ExpectEqual(
657 Value(),
658 GetMin(loop_header_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
659 ExpectEqual(
660 Value(),
661 GetMax(loop_header_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
662 ExpectEqual(
663 Value(),
664 GetMin(loop_body_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
665 ExpectEqual(
666 Value(),
667 GetMax(loop_body_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
668 ExpectEqual(
669 Value(),
670 GetMin(exit_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
671 ExpectEqual(
672 Value(),
673 GetMax(exit_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
674 ExpectEqual(
675 Value(),
676 GetMin(entry_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
677 ExpectEqual(
678 Value(),
679 GetMax(entry_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
680
681 ExpectEqual(
682 Value(),
683 GetMin(loop_header_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
684 ExpectEqual(
685 Value(),
686 GetMax(loop_header_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
687 ExpectEqual(
688 Value(),
689 GetMin(loop_body_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
690 ExpectEqual(
691 Value(),
692 GetMax(loop_body_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
693 ExpectEqual(
694 Value(),
695 GetMin(exit_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
696 ExpectEqual(
697 Value(),
698 GetMax(exit_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
699 ExpectEqual(
700 Value(),
701 GetMin(entry_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
702 ExpectEqual(
703 Value(),
704 GetMax(entry_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
705 }
706
TEST_F(InductionVarRangeTest,GetMinMaxGeometricMul)707 TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) {
708 ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr));
709 ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr));
710 }
711
TEST_F(InductionVarRangeTest,GetMinMaxGeometricDiv)712 TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) {
713 ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr));
714 ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr));
715 ExpectEqual(Value(-5), GetMin(CreateGeometric(11, -5, 3, '/'), nullptr));
716 ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '/'), nullptr));
717 ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '/'), nullptr));
718 ExpectEqual(Value(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr));
719 ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr));
720 ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr));
721 }
722
TEST_F(InductionVarRangeTest,GetMinMaxPeriodic)723 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) {
724 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr));
725 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr));
726 }
727
TEST_F(InductionVarRangeTest,GetMulMin)728 TEST_F(InductionVarRangeTest, GetMulMin) {
729 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true));
730 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true));
731 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true));
732 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true));
733 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true));
734 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true));
735 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true));
736 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true));
737 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true));
738 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true));
739 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true));
740 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true));
741 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true));
742 }
743
TEST_F(InductionVarRangeTest,GetMulMax)744 TEST_F(InductionVarRangeTest, GetMulMax) {
745 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false));
746 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false));
747 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false));
748 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false));
749 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false));
750 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false));
751 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false));
752 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false));
753 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false));
754 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false));
755 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false));
756 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false));
757 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false));
758 }
759
TEST_F(InductionVarRangeTest,GetDivMin)760 TEST_F(InductionVarRangeTest, GetDivMin) {
761 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true));
762 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true));
763 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true));
764 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true));
765 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true));
766 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true));
767 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true));
768 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true));
769 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true));
770 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true));
771 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true));
772 }
773
TEST_F(InductionVarRangeTest,GetDivMax)774 TEST_F(InductionVarRangeTest, GetDivMax) {
775 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false));
776 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false));
777 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false));
778 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false));
779 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false));
780 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false));
781 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
782 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false));
783 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false));
784 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false));
785 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
786 }
787
TEST_F(InductionVarRangeTest,GetMinMaxRem)788 TEST_F(InductionVarRangeTest, GetMinMaxRem) {
789 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
790 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
791 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
792 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
793 ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
794 ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
795 ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
796 ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
797 }
798
TEST_F(InductionVarRangeTest,GetRem)799 TEST_F(InductionVarRangeTest, GetRem) {
800 ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1)));
801 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5)));
802 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5)));
803 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(5)));
804 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(5)));
805 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(-5)));
806 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(-5)));
807 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(-5)));
808 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(-5)));
809 ExpectEqual(Value(), GetRem(CreateConst(1), CreateConst(0)));
810 }
811
TEST_F(InductionVarRangeTest,GetMinMaxXor)812 TEST_F(InductionVarRangeTest, GetMinMaxXor) {
813 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
814 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
815 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
816 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
817 ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
818 ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
819 }
820
TEST_F(InductionVarRangeTest,GetXor)821 TEST_F(InductionVarRangeTest, GetXor) {
822 ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1)));
823 ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2)));
824 ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1)));
825 ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1)));
826 }
827
TEST_F(InductionVarRangeTest,AddValue)828 TEST_F(InductionVarRangeTest, AddValue) {
829 ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
830 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
831 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1)));
832 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7)));
833 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3)));
834 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50)));
835 const int32_t max_value = std::numeric_limits<int32_t>::max();
836 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5)));
837 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe
838 }
839
TEST_F(InductionVarRangeTest,SubValue)840 TEST_F(InductionVarRangeTest, SubValue) {
841 ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
842 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1)));
843 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1)));
844 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7)));
845 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3)));
846 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50)));
847 const int32_t min_value = std::numeric_limits<int32_t>::min();
848 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5)));
849 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe
850 }
851
TEST_F(InductionVarRangeTest,MulValue)852 TEST_F(InductionVarRangeTest, MulValue) {
853 ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
854 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1)));
855 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7)));
856 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3)));
857 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2)));
858 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe
859 }
860
TEST_F(InductionVarRangeTest,MulValueSpecial)861 TEST_F(InductionVarRangeTest, MulValueSpecial) {
862 const int32_t min_value = std::numeric_limits<int32_t>::min();
863 const int32_t max_value = std::numeric_limits<int32_t>::max();
864
865 // Unsafe.
866 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value)));
867 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1)));
868 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value)));
869 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value)));
870
871 // Safe.
872 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1)));
873 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1)));
874 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1)));
875 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1)));
876 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1)));
877 }
878
TEST_F(InductionVarRangeTest,DivValue)879 TEST_F(InductionVarRangeTest, DivValue) {
880 ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
881 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1)));
882 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7)));
883 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3)));
884 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50)));
885 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe
886 }
887
TEST_F(InductionVarRangeTest,DivValueSpecial)888 TEST_F(InductionVarRangeTest, DivValueSpecial) {
889 const int32_t min_value = std::numeric_limits<int32_t>::min();
890 const int32_t max_value = std::numeric_limits<int32_t>::max();
891
892 // Unsafe.
893 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1)));
894
895 // Safe.
896 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value)));
897 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value)));
898 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1)));
899 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1)));
900 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1)));
901 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1)));
902 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1)));
903 }
904
TEST_F(InductionVarRangeTest,MinValue)905 TEST_F(InductionVarRangeTest, MinValue) {
906 ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
907 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1)));
908 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1)));
909 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7)));
910 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3)));
911 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50)));
912 }
913
TEST_F(InductionVarRangeTest,MaxValue)914 TEST_F(InductionVarRangeTest, MaxValue) {
915 ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
916 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1)));
917 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1)));
918 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7)));
919 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3)));
920 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50)));
921 }
922
TEST_F(InductionVarRangeTest,ArrayLengthAndHints)923 TEST_F(InductionVarRangeTest, ArrayLengthAndHints) {
924 // We pass a bogus constant for the class to avoid mocking one.
925 HInstruction* new_array = new (GetAllocator()) HNewArray(
926 /* cls= */ x_,
927 /* length= */ x_,
928 /* dex_pc= */ 0,
929 /* component_size_shift= */ 0);
930 entry_block_->AddInstruction(new_array);
931 HInstruction* array_length = new (GetAllocator()) HArrayLength(new_array, 0);
932 entry_block_->AddInstruction(array_length);
933 // With null hint: yields extreme constants.
934 const int32_t max_value = std::numeric_limits<int32_t>::max();
935 SetHint(nullptr);
936 ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr));
937 ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr));
938 // With explicit hint: yields the length instruction.
939 SetHint(array_length);
940 ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr));
941 ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr));
942 // With any non-null hint: chases beyond the length instruction.
943 SetHint(x_);
944 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr));
945 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr));
946 }
947
TEST_F(InductionVarRangeTest,AddOrSubAndConstant)948 TEST_F(InductionVarRangeTest, AddOrSubAndConstant) {
949 HInstruction* add = new (GetAllocator())
950 HAdd(DataType::Type::kInt32, x_, graph_->GetIntConstant(-1));
951 HInstruction* alt = new (GetAllocator())
952 HAdd(DataType::Type::kInt32, graph_->GetIntConstant(-1), x_);
953 HInstruction* sub = new (GetAllocator())
954 HSub(DataType::Type::kInt32, x_, graph_->GetIntConstant(1));
955 HInstruction* rev = new (GetAllocator())
956 HSub(DataType::Type::kInt32, graph_->GetIntConstant(1), x_);
957 entry_block_->AddInstruction(add);
958 entry_block_->AddInstruction(alt);
959 entry_block_->AddInstruction(sub);
960 entry_block_->AddInstruction(rev);
961 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(add), nullptr));
962 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(add), nullptr));
963 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(alt), nullptr));
964 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(alt), nullptr));
965 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(sub), nullptr));
966 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(sub), nullptr));
967 ExpectEqual(Value(x_, -1, 1), GetMin(CreateFetch(rev), nullptr));
968 ExpectEqual(Value(x_, -1, 1), GetMax(CreateFetch(rev), nullptr));
969 }
970
971 //
972 // Tests on public methods.
973 //
974
TEST_F(InductionVarRangeTest,ConstantTripCountUp)975 TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
976 BuildLoop(0, graph_->GetIntConstant(1000), 1);
977 PerformInductionVarAnalysis();
978
979 Value v1, v2;
980 bool needs_finite_test = true;
981 bool needs_taken_test = true;
982
983 HInstruction* phi = condition_->InputAt(0);
984 HInstruction* exit = exit_block_->GetLastInstruction();
985
986 // In context of header: known.
987 range_.GetInductionRange(condition_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
988 EXPECT_FALSE(needs_finite_test);
989 ExpectEqual(Value(0), v1);
990 ExpectEqual(Value(1000), v2);
991
992 // In context of loop-body: known.
993 range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
994 EXPECT_FALSE(needs_finite_test);
995 ExpectEqual(Value(0), v1);
996 ExpectEqual(Value(999), v2);
997 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
998 EXPECT_FALSE(needs_finite_test);
999 ExpectEqual(Value(1), v1);
1000 ExpectEqual(Value(1000), v2);
1001
1002 // Induction vs. no-induction.
1003 EXPECT_TRUE(
1004 range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1005 EXPECT_TRUE(range_.CanGenerateLastValue(phi));
1006 EXPECT_FALSE(
1007 range_.CanGenerateRange(exit->GetBlock(), exit, &needs_finite_test, &needs_taken_test));
1008 EXPECT_FALSE(range_.CanGenerateLastValue(exit));
1009
1010 // Last value (unsimplified).
1011 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
1012 ASSERT_TRUE(last->IsAdd());
1013 ExpectInt(1000, last->InputAt(0));
1014 ExpectInt(0, last->InputAt(1));
1015
1016 // Loop logic.
1017 int64_t tc = 0;
1018 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
1019 EXPECT_EQ(1000, tc);
1020 HInstruction* offset = nullptr;
1021 EXPECT_TRUE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
1022 ExpectInt(0, offset);
1023 HInstruction* tce = range_.GenerateTripCount(
1024 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
1025 ASSERT_TRUE(tce != nullptr);
1026 ExpectInt(1000, tce);
1027 }
1028
TEST_F(InductionVarRangeTest,ConstantTripCountDown)1029 TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
1030 BuildLoop(1000, graph_->GetIntConstant(0), -1);
1031 PerformInductionVarAnalysis();
1032
1033 Value v1, v2;
1034 bool needs_finite_test = true;
1035 bool needs_taken_test = true;
1036
1037 HInstruction* phi = condition_->InputAt(0);
1038 HInstruction* exit = exit_block_->GetLastInstruction();
1039
1040 // In context of header: known.
1041 range_.GetInductionRange(condition_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1042 EXPECT_FALSE(needs_finite_test);
1043 ExpectEqual(Value(0), v1);
1044 ExpectEqual(Value(1000), v2);
1045
1046 // In context of loop-body: known.
1047 range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1048 EXPECT_FALSE(needs_finite_test);
1049 ExpectEqual(Value(1), v1);
1050 ExpectEqual(Value(1000), v2);
1051 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
1052 EXPECT_FALSE(needs_finite_test);
1053 ExpectEqual(Value(0), v1);
1054 ExpectEqual(Value(999), v2);
1055
1056 // Induction vs. no-induction.
1057 EXPECT_TRUE(
1058 range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1059 EXPECT_TRUE(range_.CanGenerateLastValue(phi));
1060 EXPECT_FALSE(
1061 range_.CanGenerateRange(exit->GetBlock(), exit, &needs_finite_test, &needs_taken_test));
1062 EXPECT_FALSE(range_.CanGenerateLastValue(exit));
1063
1064 // Last value (unsimplified).
1065 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
1066 ASSERT_TRUE(last->IsSub());
1067 ExpectInt(1000, last->InputAt(0));
1068 ExpectInt(1000, last->InputAt(1));
1069
1070 // Loop logic.
1071 int64_t tc = 0;
1072 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
1073 EXPECT_EQ(1000, tc);
1074 HInstruction* offset = nullptr;
1075 EXPECT_FALSE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
1076 HInstruction* tce = range_.GenerateTripCount(
1077 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
1078 ASSERT_TRUE(tce != nullptr);
1079 ASSERT_TRUE(tce->IsNeg());
1080 last = tce->InputAt(0);
1081 EXPECT_TRUE(last->IsSub());
1082 ExpectInt(0, last->InputAt(0));
1083 ExpectInt(1000, last->InputAt(1));
1084 }
1085
TEST_F(InductionVarRangeTest,SymbolicTripCountUp)1086 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
1087 BuildLoop(0, x_, 1);
1088 PerformInductionVarAnalysis();
1089
1090 Value v1, v2;
1091 bool needs_finite_test = true;
1092 bool needs_taken_test = true;
1093
1094 HInstruction* phi = condition_->InputAt(0);
1095
1096 // In context of header: upper unknown.
1097 range_.GetInductionRange(condition_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1098 EXPECT_FALSE(needs_finite_test);
1099 ExpectEqual(Value(0), v1);
1100 ExpectEqual(Value(), v2);
1101
1102 // In context of loop-body: known.
1103 range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1104 EXPECT_FALSE(needs_finite_test);
1105 ExpectEqual(Value(0), v1);
1106 ExpectEqual(Value(x_, 1, -1), v2);
1107 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
1108 EXPECT_FALSE(needs_finite_test);
1109 ExpectEqual(Value(1), v1);
1110 ExpectEqual(Value(x_, 1, 0), v2);
1111
1112 HInstruction* lower = nullptr;
1113 HInstruction* upper = nullptr;
1114
1115 // Can generate code in context of loop-body only.
1116 EXPECT_FALSE(
1117 range_.CanGenerateRange(condition_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1118 ASSERT_TRUE(
1119 range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1120 EXPECT_FALSE(needs_finite_test);
1121 EXPECT_TRUE(needs_taken_test);
1122
1123 // Generates code (unsimplified).
1124 range_.GenerateRange(increment_->GetBlock(), phi, graph_, loop_preheader_, &lower, &upper);
1125
1126 // Verify lower is 0+0.
1127 ASSERT_TRUE(lower != nullptr);
1128 ASSERT_TRUE(lower->IsAdd());
1129 ExpectInt(0, lower->InputAt(0));
1130 ExpectInt(0, lower->InputAt(1));
1131
1132 // Verify upper is (V-1)+0.
1133 ASSERT_TRUE(upper != nullptr);
1134 ASSERT_TRUE(upper->IsAdd());
1135 ASSERT_TRUE(upper->InputAt(0)->IsSub());
1136 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue());
1137 ExpectInt(1, upper->InputAt(0)->InputAt(1));
1138 ExpectInt(0, upper->InputAt(1));
1139
1140 // Verify taken-test is 0<V.
1141 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
1142 ASSERT_TRUE(taken != nullptr);
1143 ASSERT_TRUE(taken->IsLessThan());
1144 ExpectInt(0, taken->InputAt(0));
1145 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
1146
1147 // Replacement.
1148 range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
1149 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
1150 EXPECT_FALSE(needs_finite_test);
1151 ExpectEqual(Value(1), v1);
1152 ExpectEqual(Value(y_, 1, 0), v2);
1153
1154 // Loop logic.
1155 int64_t tc = 0;
1156 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
1157 EXPECT_EQ(0, tc); // unknown
1158 HInstruction* offset = nullptr;
1159 EXPECT_TRUE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
1160 ExpectInt(0, offset);
1161 HInstruction* tce = range_.GenerateTripCount(
1162 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
1163 ASSERT_TRUE(tce != nullptr);
1164 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test
1165 ExpectInt(0, tce->InputAt(0));
1166 EXPECT_TRUE(tce->InputAt(1)->IsParameterValue());
1167 EXPECT_TRUE(tce->InputAt(2)->IsLessThan());
1168 }
1169
TEST_F(InductionVarRangeTest,SymbolicTripCountDown)1170 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
1171 BuildLoop(1000, x_, -1);
1172 PerformInductionVarAnalysis();
1173
1174 Value v1, v2;
1175 bool needs_finite_test = true;
1176 bool needs_taken_test = true;
1177
1178 HInstruction* phi = condition_->InputAt(0);
1179
1180 // In context of header: lower unknown.
1181 range_.GetInductionRange(condition_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1182 EXPECT_FALSE(needs_finite_test);
1183 ExpectEqual(Value(), v1);
1184 ExpectEqual(Value(1000), v2);
1185
1186 // In context of loop-body: known.
1187 range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
1188 EXPECT_FALSE(needs_finite_test);
1189 ExpectEqual(Value(x_, 1, 1), v1);
1190 ExpectEqual(Value(1000), v2);
1191 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
1192 EXPECT_FALSE(needs_finite_test);
1193 ExpectEqual(Value(x_, 1, 0), v1);
1194 ExpectEqual(Value(999), v2);
1195
1196 HInstruction* lower = nullptr;
1197 HInstruction* upper = nullptr;
1198
1199 // Can generate code in context of loop-body only.
1200 EXPECT_FALSE(
1201 range_.CanGenerateRange(condition_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1202 ASSERT_TRUE(
1203 range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
1204 EXPECT_FALSE(needs_finite_test);
1205 EXPECT_TRUE(needs_taken_test);
1206
1207 // Generates code (unsimplified).
1208 range_.GenerateRange(increment_->GetBlock(), phi, graph_, loop_preheader_, &lower, &upper);
1209
1210 // Verify lower is 1000-((1000-V)-1).
1211 ASSERT_TRUE(lower != nullptr);
1212 ASSERT_TRUE(lower->IsSub());
1213 ExpectInt(1000, lower->InputAt(0));
1214 lower = lower->InputAt(1);
1215 ASSERT_TRUE(lower->IsSub());
1216 ExpectInt(1, lower->InputAt(1));
1217 lower = lower->InputAt(0);
1218 ASSERT_TRUE(lower->IsSub());
1219 ExpectInt(1000, lower->InputAt(0));
1220 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue());
1221
1222 // Verify upper is 1000-0.
1223 ASSERT_TRUE(upper != nullptr);
1224 ASSERT_TRUE(upper->IsSub());
1225 ExpectInt(1000, upper->InputAt(0));
1226 ExpectInt(0, upper->InputAt(1));
1227
1228 // Verify taken-test is 1000>V.
1229 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
1230 ASSERT_TRUE(taken != nullptr);
1231 ASSERT_TRUE(taken->IsGreaterThan());
1232 ExpectInt(1000, taken->InputAt(0));
1233 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
1234
1235 // Replacement.
1236 range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
1237 range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
1238 EXPECT_FALSE(needs_finite_test);
1239 ExpectEqual(Value(y_, 1, 0), v1);
1240 ExpectEqual(Value(999), v2);
1241
1242 // Loop logic.
1243 int64_t tc = 0;
1244 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
1245 EXPECT_EQ(0, tc); // unknown
1246 HInstruction* offset = nullptr;
1247 EXPECT_FALSE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
1248 HInstruction* tce = range_.GenerateTripCount(
1249 loop_header_->GetLoopInformation(), graph_, loop_preheader_);
1250 ASSERT_TRUE(tce != nullptr);
1251 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test
1252 ExpectInt(0, tce->InputAt(0));
1253 EXPECT_TRUE(tce->InputAt(1)->IsSub());
1254 EXPECT_TRUE(tce->InputAt(2)->IsGreaterThan());
1255 tce = tce->InputAt(1);
1256 ExpectInt(1000, taken->InputAt(0));
1257 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
1258 }
1259
1260 } // namespace art
1261