1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "base/arena_allocator.h"
18 #include "builder.h"
19 #include "induction_var_analysis.h"
20 #include "induction_var_range.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23
24 namespace art {
25
26 using Value = InductionVarRange::Value;
27
28 /**
29 * Fixture class for the InductionVarRange tests.
30 */
31 class InductionVarRangeTest : public CommonCompilerTest {
32 public:
InductionVarRangeTest()33 InductionVarRangeTest()
34 : pool_(),
35 allocator_(&pool_),
36 graph_(CreateGraph(&allocator_)),
37 iva_(new (&allocator_) HInductionVarAnalysis(graph_)),
38 range_(iva_) {
39 BuildGraph();
40 }
41
~InductionVarRangeTest()42 ~InductionVarRangeTest() { }
43
ExpectEqual(Value v1,Value v2)44 void ExpectEqual(Value v1, Value v2) {
45 EXPECT_EQ(v1.instruction, v2.instruction);
46 EXPECT_EQ(v1.a_constant, v2.a_constant);
47 EXPECT_EQ(v1.b_constant, v2.b_constant);
48 EXPECT_EQ(v1.is_known, v2.is_known);
49 }
50
51 //
52 // Construction methods.
53 //
54
55 /** Constructs bare minimum graph. */
BuildGraph()56 void BuildGraph() {
57 graph_->SetNumberOfVRegs(1);
58 entry_block_ = new (&allocator_) HBasicBlock(graph_);
59 exit_block_ = new (&allocator_) HBasicBlock(graph_);
60 graph_->AddBlock(entry_block_);
61 graph_->AddBlock(exit_block_);
62 graph_->SetEntryBlock(entry_block_);
63 graph_->SetExitBlock(exit_block_);
64 // Two parameters.
65 x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
66 entry_block_->AddInstruction(x_);
67 y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
68 entry_block_->AddInstruction(y_);
69 }
70
71 /** Constructs loop with given upper bound. */
BuildLoop(int32_t lower,HInstruction * upper,int32_t stride)72 void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) {
73 // Control flow.
74 loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
75 graph_->AddBlock(loop_preheader_);
76 HBasicBlock* loop_header = new (&allocator_) HBasicBlock(graph_);
77 graph_->AddBlock(loop_header);
78 HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_);
79 graph_->AddBlock(loop_body);
80 HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_);
81 graph_->AddBlock(return_block);
82 entry_block_->AddSuccessor(loop_preheader_);
83 loop_preheader_->AddSuccessor(loop_header);
84 loop_header->AddSuccessor(loop_body);
85 loop_header->AddSuccessor(return_block);
86 loop_body->AddSuccessor(loop_header);
87 return_block->AddSuccessor(exit_block_);
88 // Instructions.
89 loop_preheader_->AddInstruction(new (&allocator_) HGoto());
90 HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
91 loop_header->AddPhi(phi);
92 phi->AddInput(graph_->GetIntConstant(lower)); // i = l
93 if (stride > 0) {
94 condition_ = new (&allocator_) HLessThan(phi, upper); // i < u
95 } else {
96 condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u
97 }
98 loop_header->AddInstruction(condition_);
99 loop_header->AddInstruction(new (&allocator_) HIf(condition_));
100 increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride));
101 loop_body->AddInstruction(increment_); // i += s
102 phi->AddInput(increment_);
103 loop_body->AddInstruction(new (&allocator_) HGoto());
104 return_block->AddInstruction(new (&allocator_) HReturnVoid());
105 exit_block_->AddInstruction(new (&allocator_) HExit());
106 }
107
108 /** Constructs SSA and performs induction variable analysis. */
PerformInductionVarAnalysis()109 void PerformInductionVarAnalysis() {
110 graph_->BuildDominatorTree();
111 iva_->Run();
112 }
113
114 /** Constructs an invariant. */
CreateInvariant(char opc,HInductionVarAnalysis::InductionInfo * a,HInductionVarAnalysis::InductionInfo * b)115 HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc,
116 HInductionVarAnalysis::InductionInfo* a,
117 HInductionVarAnalysis::InductionInfo* b) {
118 HInductionVarAnalysis::InductionOp op;
119 switch (opc) {
120 case '+': op = HInductionVarAnalysis::kAdd; break;
121 case '-': op = HInductionVarAnalysis::kSub; break;
122 case 'n': op = HInductionVarAnalysis::kNeg; break;
123 case '*': op = HInductionVarAnalysis::kMul; break;
124 case '/': op = HInductionVarAnalysis::kDiv; break;
125 default: op = HInductionVarAnalysis::kNop; break;
126 }
127 return iva_->CreateInvariantOp(op, a, b);
128 }
129
130 /** Constructs a fetch. */
CreateFetch(HInstruction * fetch)131 HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) {
132 return iva_->CreateInvariantFetch(fetch);
133 }
134
135 /** Constructs a constant. */
CreateConst(int32_t c)136 HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) {
137 return CreateFetch(graph_->GetIntConstant(c));
138 }
139
140 /** Constructs a trip-count. */
CreateTripCount(int32_t tc,bool in_loop,bool safe)141 HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
142 Primitive::Type type = Primitive::kPrimInt;
143 if (in_loop && safe) {
144 return iva_->CreateTripCount(
145 HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr, type);
146 } else if (in_loop) {
147 return iva_->CreateTripCount(
148 HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr, type);
149 } else if (safe) {
150 return iva_->CreateTripCount(
151 HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr, type);
152 } else {
153 return iva_->CreateTripCount(
154 HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr, type);
155 }
156 }
157
158 /** Constructs a linear a * i + b induction. */
CreateLinear(int32_t a,int32_t b)159 HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) {
160 return iva_->CreateInduction(
161 HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b), Primitive::kPrimInt);
162 }
163
164 /** Constructs a range [lo, hi] using a periodic induction. */
CreateRange(int32_t lo,int32_t hi)165 HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) {
166 return iva_->CreateInduction(
167 HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi), Primitive::kPrimInt);
168 }
169
170 /** Constructs a wrap-around induction consisting of a constant, followed info */
CreateWrapAround(int32_t initial,HInductionVarAnalysis::InductionInfo * info)171 HInductionVarAnalysis::InductionInfo* CreateWrapAround(
172 int32_t initial,
173 HInductionVarAnalysis::InductionInfo* info) {
174 return iva_->CreateInduction(
175 HInductionVarAnalysis::kWrapAround, CreateConst(initial), info, Primitive::kPrimInt);
176 }
177
178 /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
CreateWrapAround(int32_t initial,int32_t lo,int32_t hi)179 HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
180 return CreateWrapAround(initial, CreateRange(lo, hi));
181 }
182
183 //
184 // Relay methods.
185 //
186
NeedsTripCount(HInductionVarAnalysis::InductionInfo * info)187 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
188 return range_.NeedsTripCount(info);
189 }
190
IsBodyTripCount(HInductionVarAnalysis::InductionInfo * trip)191 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
192 return range_.IsBodyTripCount(trip);
193 }
194
IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo * trip)195 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
196 return range_.IsUnsafeTripCount(trip);
197 }
198
GetMin(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * induc)199 Value GetMin(HInductionVarAnalysis::InductionInfo* info,
200 HInductionVarAnalysis::InductionInfo* induc) {
201 return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ true);
202 }
203
GetMax(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * induc)204 Value GetMax(HInductionVarAnalysis::InductionInfo* info,
205 HInductionVarAnalysis::InductionInfo* induc) {
206 return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ false);
207 }
208
GetMul(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)209 Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
210 HInductionVarAnalysis::InductionInfo* info2,
211 bool is_min) {
212 return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min);
213 }
214
GetDiv(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,bool is_min)215 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
216 HInductionVarAnalysis::InductionInfo* info2,
217 bool is_min) {
218 return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
219 }
220
IsExact(HInductionVarAnalysis::InductionInfo * info,int64_t * value)221 bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
222 return range_.IsConstant(info, InductionVarRange::kExact, value);
223 }
224
IsAtMost(HInductionVarAnalysis::InductionInfo * info,int64_t * value)225 bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
226 return range_.IsConstant(info, InductionVarRange::kAtMost, value);
227 }
228
IsAtLeast(HInductionVarAnalysis::InductionInfo * info,int64_t * value)229 bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
230 return range_.IsConstant(info, InductionVarRange::kAtLeast, value);
231 }
232
AddValue(Value v1,Value v2)233 Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
SubValue(Value v1,Value v2)234 Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); }
MulValue(Value v1,Value v2)235 Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); }
DivValue(Value v1,Value v2)236 Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); }
MinValue(Value v1,Value v2)237 Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); }
MaxValue(Value v1,Value v2)238 Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); }
239
240 // General building fields.
241 ArenaPool pool_;
242 ArenaAllocator allocator_;
243 HGraph* graph_;
244 HBasicBlock* entry_block_;
245 HBasicBlock* exit_block_;
246 HBasicBlock* loop_preheader_;
247 HInductionVarAnalysis* iva_;
248 InductionVarRange range_;
249
250 // Instructions.
251 HInstruction* condition_;
252 HInstruction* increment_;
253 HInstruction* x_;
254 HInstruction* y_;
255 };
256
257 //
258 // Tests on private methods.
259 //
260
TEST_F(InductionVarRangeTest,IsConstant)261 TEST_F(InductionVarRangeTest, IsConstant) {
262 int64_t value;
263 // Constant.
264 EXPECT_TRUE(IsExact(CreateConst(12345), &value));
265 EXPECT_EQ(12345, value);
266 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value));
267 EXPECT_EQ(12345, value);
268 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value));
269 EXPECT_EQ(12345, value);
270 // Constant trivial range.
271 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value));
272 EXPECT_EQ(111, value);
273 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value));
274 EXPECT_EQ(111, value);
275 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value));
276 EXPECT_EQ(111, value);
277 // Constant non-trivial range.
278 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value));
279 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value));
280 EXPECT_EQ(22, value);
281 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value));
282 EXPECT_EQ(11, value);
283 // Symbolic.
284 EXPECT_FALSE(IsExact(CreateFetch(x_), &value));
285 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value));
286 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value));
287 }
288
TEST_F(InductionVarRangeTest,TripCountProperties)289 TEST_F(InductionVarRangeTest, TripCountProperties) {
290 EXPECT_FALSE(NeedsTripCount(nullptr));
291 EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
292 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1)));
293 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3)));
294 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1))));
295
296 EXPECT_FALSE(IsBodyTripCount(nullptr));
297 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true)));
298 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false)));
299 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true)));
300 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false)));
301
302 EXPECT_FALSE(IsUnsafeTripCount(nullptr));
303 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true)));
304 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false)));
305 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true)));
306 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false)));
307 }
308
TEST_F(InductionVarRangeTest,GetMinMaxNull)309 TEST_F(InductionVarRangeTest, GetMinMaxNull) {
310 ExpectEqual(Value(), GetMin(nullptr, nullptr));
311 ExpectEqual(Value(), GetMax(nullptr, nullptr));
312 }
313
TEST_F(InductionVarRangeTest,GetMinMaxAdd)314 TEST_F(InductionVarRangeTest, GetMinMaxAdd) {
315 ExpectEqual(Value(12),
316 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
317 ExpectEqual(Value(22),
318 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
319 ExpectEqual(Value(x_, 1, -20),
320 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
321 ExpectEqual(Value(x_, 1, -10),
322 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
323 ExpectEqual(Value(x_, 1, 10),
324 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
325 ExpectEqual(Value(x_, 1, 20),
326 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
327 ExpectEqual(Value(5),
328 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
329 ExpectEqual(Value(19),
330 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
331 }
332
TEST_F(InductionVarRangeTest,GetMinMaxSub)333 TEST_F(InductionVarRangeTest, GetMinMaxSub) {
334 ExpectEqual(Value(-18),
335 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
336 ExpectEqual(Value(-8),
337 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
338 ExpectEqual(Value(x_, 1, 10),
339 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
340 ExpectEqual(Value(x_, 1, 20),
341 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
342 ExpectEqual(Value(x_, -1, 10),
343 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
344 ExpectEqual(Value(x_, -1, 20),
345 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
346 ExpectEqual(Value(-25),
347 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
348 ExpectEqual(Value(-11),
349 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
350 }
351
TEST_F(InductionVarRangeTest,GetMinMaxNeg)352 TEST_F(InductionVarRangeTest, GetMinMaxNeg) {
353 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
354 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
355 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
356 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
357 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
358 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
359 }
360
TEST_F(InductionVarRangeTest,GetMinMaxMul)361 TEST_F(InductionVarRangeTest, GetMinMaxMul) {
362 ExpectEqual(Value(20),
363 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
364 ExpectEqual(Value(40),
365 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
366 }
367
TEST_F(InductionVarRangeTest,GetMinMaxDiv)368 TEST_F(InductionVarRangeTest, GetMinMaxDiv) {
369 ExpectEqual(Value(3),
370 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
371 ExpectEqual(Value(5),
372 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
373 }
374
TEST_F(InductionVarRangeTest,GetMinMaxConstant)375 TEST_F(InductionVarRangeTest, GetMinMaxConstant) {
376 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr));
377 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr));
378 }
379
TEST_F(InductionVarRangeTest,GetMinMaxFetch)380 TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
381 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr));
382 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr));
383 }
384
TEST_F(InductionVarRangeTest,GetMinMaxLinear)385 TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
386 ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true)));
387 ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true)));
388 ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
389 ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
390 }
391
TEST_F(InductionVarRangeTest,GetMinMaxWrapAround)392 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
393 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr));
394 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr));
395 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr));
396 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr));
397 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr));
398 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
399 }
400
TEST_F(InductionVarRangeTest,GetMinMaxPeriodic)401 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) {
402 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr));
403 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr));
404 }
405
TEST_F(InductionVarRangeTest,GetMulMin)406 TEST_F(InductionVarRangeTest, GetMulMin) {
407 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true));
408 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true));
409 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true));
410 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true));
411 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true));
412 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true));
413 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true));
414 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true));
415 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true));
416 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true));
417 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true));
418 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true));
419 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true));
420 }
421
TEST_F(InductionVarRangeTest,GetMulMax)422 TEST_F(InductionVarRangeTest, GetMulMax) {
423 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false));
424 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false));
425 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false));
426 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false));
427 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false));
428 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false));
429 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false));
430 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false));
431 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false));
432 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false));
433 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false));
434 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false));
435 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false));
436 }
437
TEST_F(InductionVarRangeTest,GetDivMin)438 TEST_F(InductionVarRangeTest, GetDivMin) {
439 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true));
440 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true));
441 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true));
442 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true));
443 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true));
444 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true));
445 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true));
446 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true));
447 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true));
448 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true));
449 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true));
450 }
451
TEST_F(InductionVarRangeTest,GetDivMax)452 TEST_F(InductionVarRangeTest, GetDivMax) {
453 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false));
454 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false));
455 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false));
456 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false));
457 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false));
458 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false));
459 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
460 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false));
461 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false));
462 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false));
463 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
464 }
465
TEST_F(InductionVarRangeTest,AddValue)466 TEST_F(InductionVarRangeTest, AddValue) {
467 ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
468 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
469 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1)));
470 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7)));
471 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3)));
472 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50)));
473 const int32_t max_value = std::numeric_limits<int32_t>::max();
474 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5)));
475 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe
476 }
477
TEST_F(InductionVarRangeTest,SubValue)478 TEST_F(InductionVarRangeTest, SubValue) {
479 ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
480 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1)));
481 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1)));
482 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7)));
483 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3)));
484 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50)));
485 const int32_t min_value = std::numeric_limits<int32_t>::min();
486 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5)));
487 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe
488 }
489
TEST_F(InductionVarRangeTest,MulValue)490 TEST_F(InductionVarRangeTest, MulValue) {
491 ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
492 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1)));
493 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7)));
494 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3)));
495 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2)));
496 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe
497 }
498
TEST_F(InductionVarRangeTest,MulValueSpecial)499 TEST_F(InductionVarRangeTest, MulValueSpecial) {
500 const int32_t min_value = std::numeric_limits<int32_t>::min();
501 const int32_t max_value = std::numeric_limits<int32_t>::max();
502
503 // Unsafe.
504 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value)));
505 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1)));
506 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value)));
507 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value)));
508
509 // Safe.
510 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1)));
511 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1)));
512 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1)));
513 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1)));
514 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1)));
515 }
516
TEST_F(InductionVarRangeTest,DivValue)517 TEST_F(InductionVarRangeTest, DivValue) {
518 ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
519 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1)));
520 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7)));
521 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3)));
522 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50)));
523 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe
524 }
525
TEST_F(InductionVarRangeTest,DivValueSpecial)526 TEST_F(InductionVarRangeTest, DivValueSpecial) {
527 const int32_t min_value = std::numeric_limits<int32_t>::min();
528 const int32_t max_value = std::numeric_limits<int32_t>::max();
529
530 // Unsafe.
531 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1)));
532
533 // Safe.
534 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value)));
535 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value)));
536 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1)));
537 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1)));
538 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1)));
539 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1)));
540 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1)));
541 }
542
TEST_F(InductionVarRangeTest,MinValue)543 TEST_F(InductionVarRangeTest, MinValue) {
544 ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
545 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1)));
546 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1)));
547 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7)));
548 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3)));
549 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50)));
550 }
551
TEST_F(InductionVarRangeTest,MaxValue)552 TEST_F(InductionVarRangeTest, MaxValue) {
553 ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
554 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1)));
555 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1)));
556 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7)));
557 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3)));
558 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50)));
559 }
560
561 //
562 // Tests on public methods.
563 //
564
TEST_F(InductionVarRangeTest,ConstantTripCountUp)565 TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
566 BuildLoop(0, graph_->GetIntConstant(1000), 1);
567 PerformInductionVarAnalysis();
568
569 Value v1, v2;
570 bool needs_finite_test = true;
571
572 // In context of header: known.
573 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
574 EXPECT_FALSE(needs_finite_test);
575 ExpectEqual(Value(0), v1);
576 ExpectEqual(Value(1000), v2);
577 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
578
579 // In context of loop-body: known.
580 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
581 EXPECT_FALSE(needs_finite_test);
582 ExpectEqual(Value(0), v1);
583 ExpectEqual(Value(999), v2);
584 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
585 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
586 EXPECT_FALSE(needs_finite_test);
587 ExpectEqual(Value(1), v1);
588 ExpectEqual(Value(1000), v2);
589 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
590 }
591
TEST_F(InductionVarRangeTest,ConstantTripCountDown)592 TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
593 BuildLoop(1000, graph_->GetIntConstant(0), -1);
594 PerformInductionVarAnalysis();
595
596 Value v1, v2;
597 bool needs_finite_test = true;
598
599 // In context of header: known.
600 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
601 EXPECT_FALSE(needs_finite_test);
602 ExpectEqual(Value(0), v1);
603 ExpectEqual(Value(1000), v2);
604 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
605
606 // In context of loop-body: known.
607 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
608 EXPECT_FALSE(needs_finite_test);
609 ExpectEqual(Value(1), v1);
610 ExpectEqual(Value(1000), v2);
611 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
612 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
613 EXPECT_FALSE(needs_finite_test);
614 ExpectEqual(Value(0), v1);
615 ExpectEqual(Value(999), v2);
616 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
617 }
618
TEST_F(InductionVarRangeTest,SymbolicTripCountUp)619 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
620 BuildLoop(0, x_, 1);
621 PerformInductionVarAnalysis();
622
623 Value v1, v2;
624 bool needs_finite_test = true;
625 bool needs_taken_test = true;
626
627 // In context of header: upper unknown.
628 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
629 EXPECT_FALSE(needs_finite_test);
630 ExpectEqual(Value(0), v1);
631 ExpectEqual(Value(), v2);
632 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
633
634 // In context of loop-body: known.
635 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
636 EXPECT_FALSE(needs_finite_test);
637 ExpectEqual(Value(0), v1);
638 ExpectEqual(Value(x_, 1, -1), v2);
639 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
640 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
641 EXPECT_FALSE(needs_finite_test);
642 ExpectEqual(Value(1), v1);
643 ExpectEqual(Value(x_, 1, 0), v2);
644 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
645
646 HInstruction* lower = nullptr;
647 HInstruction* upper = nullptr;
648 HInstruction* taken = nullptr;
649
650 // Can generate code in context of loop-body only.
651 EXPECT_FALSE(range_.CanGenerateCode(
652 condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
653 ASSERT_TRUE(range_.CanGenerateCode(
654 increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
655 EXPECT_FALSE(needs_finite_test);
656 EXPECT_TRUE(needs_taken_test);
657
658 // Generates code.
659 range_.GenerateRangeCode(
660 increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
661
662 // Verify lower is 0+0.
663 ASSERT_TRUE(lower != nullptr);
664 ASSERT_TRUE(lower->IsAdd());
665 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
666 EXPECT_EQ(0, lower->InputAt(0)->AsIntConstant()->GetValue());
667 ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
668 EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue());
669
670 // Verify upper is (V-1)+0.
671 ASSERT_TRUE(upper != nullptr);
672 ASSERT_TRUE(upper->IsAdd());
673 ASSERT_TRUE(upper->InputAt(0)->IsSub());
674 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue());
675 ASSERT_TRUE(upper->InputAt(0)->InputAt(1)->IsIntConstant());
676 EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue());
677 ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
678 EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
679
680 // Verify taken-test is 0<V.
681 range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
682 ASSERT_TRUE(taken != nullptr);
683 ASSERT_TRUE(taken->IsLessThan());
684 ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
685 EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue());
686 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
687 }
688
TEST_F(InductionVarRangeTest,SymbolicTripCountDown)689 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
690 BuildLoop(1000, x_, -1);
691 PerformInductionVarAnalysis();
692
693 Value v1, v2;
694 bool needs_finite_test = true;
695 bool needs_taken_test = true;
696
697 // In context of header: lower unknown.
698 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
699 EXPECT_FALSE(needs_finite_test);
700 ExpectEqual(Value(), v1);
701 ExpectEqual(Value(1000), v2);
702 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
703
704 // In context of loop-body: known.
705 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
706 EXPECT_FALSE(needs_finite_test);
707 ExpectEqual(Value(x_, 1, 1), v1);
708 ExpectEqual(Value(1000), v2);
709 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
710 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
711 EXPECT_FALSE(needs_finite_test);
712 ExpectEqual(Value(x_, 1, 0), v1);
713 ExpectEqual(Value(999), v2);
714 EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
715
716 HInstruction* lower = nullptr;
717 HInstruction* upper = nullptr;
718 HInstruction* taken = nullptr;
719
720 // Can generate code in context of loop-body only.
721 EXPECT_FALSE(range_.CanGenerateCode(
722 condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
723 ASSERT_TRUE(range_.CanGenerateCode(
724 increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
725 EXPECT_FALSE(needs_finite_test);
726 EXPECT_TRUE(needs_taken_test);
727
728 // Generates code.
729 range_.GenerateRangeCode(
730 increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
731
732 // Verify lower is 1000-((1000-V)-1).
733 ASSERT_TRUE(lower != nullptr);
734 ASSERT_TRUE(lower->IsSub());
735 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
736 EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue());
737 lower = lower->InputAt(1);
738 ASSERT_TRUE(lower->IsSub());
739 ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
740 EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue());
741 lower = lower->InputAt(0);
742 ASSERT_TRUE(lower->IsSub());
743 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
744 EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue());
745 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue());
746
747 // Verify upper is 1000-0.
748 ASSERT_TRUE(upper != nullptr);
749 ASSERT_TRUE(upper->IsSub());
750 ASSERT_TRUE(upper->InputAt(0)->IsIntConstant());
751 EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue());
752 ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
753 EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
754
755 // Verify taken-test is 1000>V.
756 range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
757 ASSERT_TRUE(taken != nullptr);
758 ASSERT_TRUE(taken->IsGreaterThan());
759 ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
760 EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue());
761 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
762 }
763
764 } // namespace art
765