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