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