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 <regex>
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 /**
29 * Fixture class for the InductionVarAnalysis tests.
30 */
31 class InductionVarAnalysisTest : public OptimizingUnitTest {
32 public:
InductionVarAnalysisTest()33 InductionVarAnalysisTest()
34 : iva_(nullptr),
35 parameter_(nullptr),
36 constant0_(nullptr),
37 constant1_(nullptr),
38 constant2_(nullptr),
39 constant7_(nullptr),
40 constant100_(nullptr),
41 constantm1_(nullptr),
42 float_constant0_(nullptr) {
43 }
44
~InductionVarAnalysisTest()45 ~InductionVarAnalysisTest() { }
46
47 // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n
48 // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further
49 // populate the loop with instructions to set up interesting scenarios.
BuildLoopNest(size_t n)50 void BuildLoopNest(size_t n) {
51 ASSERT_LE(n, 10);
52 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
53 graph_->SetNumberOfVRegs(n + 3);
54
55 // Build nested loops.
56 HBasicBlock* loop_pos = return_block;
57 for (size_t d = 0; d < n; ++d) {
58 std::tie(loop_preheader_[d], loop_header_[d], loop_body_[d]) = CreateWhileLoop(loop_pos);
59 loop_header_[d]->SwapSuccessors(); // Move the loop exit to the "else" successor.
60 loop_pos = loop_body_[d];
61 }
62
63 // Provide entry instructions.
64 parameter_ = MakeParam(DataType::Type::kReference);
65 constant0_ = graph_->GetIntConstant(0);
66 constant1_ = graph_->GetIntConstant(1);
67 constant2_ = graph_->GetIntConstant(2);
68 constant7_ = graph_->GetIntConstant(7);
69 constant100_ = graph_->GetIntConstant(100);
70 constantm1_ = graph_->GetIntConstant(-1);
71 float_constant0_ = graph_->GetFloatConstant(0.0f);
72
73 // Provide loop instructions.
74 for (int d = 0; d < n; d++) {
75 std::tie(basic_[d], increment_[d]) =
76 MakeLinearLoopVar(loop_header_[d], loop_body_[d], constant0_, constant1_);
77 HInstruction* compare = MakeCondition(loop_header_[d], kCondLT, basic_[d], constant100_);
78 MakeIf(loop_header_[d], compare);
79 }
80 }
81
82 // Builds if-statement at depth d.
BuildIf(int d,HBasicBlock ** ifT,HBasicBlock ** ifF)83 HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock** ifF) {
84 HBasicBlock* cond = AddNewBlock();
85 HBasicBlock* ifTrue = AddNewBlock();
86 HBasicBlock* ifFalse = AddNewBlock();
87 // Conditional split.
88 loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond);
89 cond->AddSuccessor(ifTrue);
90 cond->AddSuccessor(ifFalse);
91 ifTrue->AddSuccessor(loop_body_[d]);
92 ifFalse->AddSuccessor(loop_body_[d]);
93 MakeIf(cond, parameter_);
94 *ifT = ifTrue;
95 *ifF = ifFalse;
96
97 HPhi* select_phi = new (GetAllocator()) HPhi(GetAllocator(), -1, 0, DataType::Type::kInt32);
98 loop_body_[d]->AddPhi(select_phi);
99 return select_phi;
100 }
101
102 // Inserts instruction right before increment at depth d.
InsertInstruction(HInstruction * instruction,int d)103 HInstruction* InsertInstruction(HInstruction* instruction, int d) {
104 loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]);
105 return instruction;
106 }
107
108 // Inserts a phi to loop header at depth d and returns it.
InsertLoopPhi(int vreg,int d)109 HPhi* InsertLoopPhi(int vreg, int d) {
110 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), vreg, 0, DataType::Type::kInt32);
111 loop_header_[d]->AddPhi(phi);
112 return phi;
113 }
114
115 // Inserts an array store with given `subscript` at depth d to
116 // enable tests to inspect the computed induction at that point easily.
InsertArrayStore(HInstruction * subscript,int d)117 HInstruction* InsertArrayStore(HInstruction* subscript, int d) {
118 // ArraySet is given a float value in order to avoid SsaBuilder typing
119 // it from the array's non-existent reference type info.
120 return InsertInstruction(new (GetAllocator()) HArraySet(
121 parameter_, subscript, float_constant0_, DataType::Type::kFloat32, 0), d);
122 }
123
124 // Returns induction information of instruction in loop at depth d.
GetInductionInfo(HInstruction * instruction,int d)125 std::string GetInductionInfo(HInstruction* instruction, int d) {
126 return HInductionVarAnalysis::InductionToString(
127 iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction));
128 }
129
130 // Returns induction information of the trip-count of loop at depth d.
GetTripCount(int d)131 std::string GetTripCount(int d) {
132 HInstruction* control = loop_header_[d]->GetLastInstruction();
133 DCHECK(control->IsIf());
134 return GetInductionInfo(control, d);
135 }
136
137 // Returns true if instructions have identical induction.
HaveSameInduction(HInstruction * instruction1,HInstruction * instruction2)138 bool HaveSameInduction(HInstruction* instruction1, HInstruction* instruction2) {
139 return HInductionVarAnalysis::InductionEqual(
140 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction1),
141 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction2));
142 }
143
144 // Returns true for narrowing linear induction.
IsNarrowingLinear(HInstruction * instruction)145 bool IsNarrowingLinear(HInstruction* instruction) {
146 return HInductionVarAnalysis::IsNarrowingLinear(
147 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction));
148 }
149
150 // Performs InductionVarAnalysis (after proper set up).
PerformInductionVarAnalysis()151 void PerformInductionVarAnalysis() {
152 graph_->BuildDominatorTree();
153 iva_ = new (GetAllocator()) HInductionVarAnalysis(graph_);
154 iva_->Run();
155 }
156
157 // General building fields.
158 HInductionVarAnalysis* iva_;
159
160 // Fixed basic blocks and instructions.
161 HInstruction* parameter_; // "this"
162 HInstruction* constant0_;
163 HInstruction* constant1_;
164 HInstruction* constant2_;
165 HInstruction* constant7_;
166 HInstruction* constant100_;
167 HInstruction* constantm1_;
168 HInstruction* float_constant0_;
169
170 // Loop specifics.
171 HBasicBlock* loop_preheader_[10];
172 HBasicBlock* loop_header_[10];
173 HBasicBlock* loop_body_[10];
174 HInstruction* increment_[10];
175 HPhi* basic_[10]; // "vreg_d", the "i_d"
176 };
177
178 //
179 // The actual InductionVarAnalysis tests.
180 //
181
TEST_F(InductionVarAnalysisTest,ProperLoopSetup)182 TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
183 // Setup:
184 // for (int i_0 = 0; i_0 < 100; i_0++) {
185 // ..
186 // for (int i_9 = 0; i_9 < 100; i_9++) {
187 // }
188 // ..
189 // }
190 BuildLoopNest(10);
191 graph_->BuildDominatorTree();
192
193 ASSERT_EQ(entry_block_->GetLoopInformation(), nullptr);
194 for (int d = 0; d < 1; d++) {
195 ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
196 (d == 0) ? nullptr
197 : loop_header_[d - 1]->GetLoopInformation());
198 ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr);
199 ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr);
200 ASSERT_EQ(loop_header_[d]->GetLoopInformation(),
201 loop_body_[d]->GetLoopInformation());
202 }
203 ASSERT_EQ(exit_block_->GetLoopInformation(), nullptr);
204 }
205
TEST_F(InductionVarAnalysisTest,FindBasicInduction)206 TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
207 // Setup:
208 // for (int i = 0; i < 100; i++) {
209 // a[i] = 0;
210 // }
211 BuildLoopNest(1);
212 HInstruction* store = InsertArrayStore(basic_[0], 0);
213 PerformInductionVarAnalysis();
214
215 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str());
216 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[0], 0).c_str());
217
218 // Offset matters!
219 EXPECT_FALSE(HaveSameInduction(store->InputAt(1), increment_[0]));
220
221 // Trip-count.
222 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(0).c_str());
223 }
224
TEST_F(InductionVarAnalysisTest,FindDerivedInduction)225 TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
226 // Setup:
227 // for (int i = 0; i < 100; i++) {
228 // t = 100 + i;
229 // t = 100 - i;
230 // t = 100 * i;
231 // t = i << 1;
232 // t = - i;
233 // }
234 BuildLoopNest(1);
235 HInstruction* add = InsertInstruction(
236 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant100_, basic_[0]), 0);
237 HInstruction* sub = InsertInstruction(
238 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0]), 0);
239 HInstruction* mul = InsertInstruction(
240 new (GetAllocator()) HMul(DataType::Type::kInt32, constant100_, basic_[0]), 0);
241 HInstruction* shl = InsertInstruction(
242 new (GetAllocator()) HShl(DataType::Type::kInt32, basic_[0], constant1_), 0);
243 HInstruction* neg = InsertInstruction(
244 new (GetAllocator()) HNeg(DataType::Type::kInt32, basic_[0]), 0);
245 PerformInductionVarAnalysis();
246
247 EXPECT_STREQ("((1) * i + (100)):Int32", GetInductionInfo(add, 0).c_str());
248 EXPECT_STREQ("(( - (1)) * i + (100)):Int32", GetInductionInfo(sub, 0).c_str());
249 EXPECT_STREQ("((100) * i + (0)):Int32", GetInductionInfo(mul, 0).c_str());
250 EXPECT_STREQ("((2) * i + (0)):Int32", GetInductionInfo(shl, 0).c_str());
251 EXPECT_STREQ("(( - (1)) * i + (0)):Int32", GetInductionInfo(neg, 0).c_str());
252 }
253
TEST_F(InductionVarAnalysisTest,FindChainInduction)254 TEST_F(InductionVarAnalysisTest, FindChainInduction) {
255 // Setup:
256 // k = 0;
257 // for (int i = 0; i < 100; i++) {
258 // k = k + 100;
259 // a[k] = 0;
260 // k = k - 1;
261 // a[k] = 0;
262 // }
263 BuildLoopNest(1);
264 HPhi* k_header = InsertLoopPhi(0, 0);
265 k_header->AddInput(constant0_);
266
267 HInstruction* add = InsertInstruction(
268 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0);
269 HInstruction* store1 = InsertArrayStore(add, 0);
270 HInstruction* sub = InsertInstruction(
271 new (GetAllocator()) HSub(DataType::Type::kInt32, add, constant1_), 0);
272 HInstruction* store2 = InsertArrayStore(sub, 0);
273 k_header->AddInput(sub);
274 PerformInductionVarAnalysis();
275
276 EXPECT_STREQ("(((100) - (1)) * i + (0)):Int32",
277 GetInductionInfo(k_header, 0).c_str());
278 EXPECT_STREQ("(((100) - (1)) * i + (100)):Int32",
279 GetInductionInfo(store1->InputAt(1), 0).c_str());
280 EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):Int32",
281 GetInductionInfo(store2->InputAt(1), 0).c_str());
282 }
283
TEST_F(InductionVarAnalysisTest,FindTwoWayBasicInduction)284 TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) {
285 // Setup:
286 // k = 0;
287 // for (int i = 0; i < 100; i++) {
288 // if () k = k + 1;
289 // else k = k + 1;
290 // a[k] = 0;
291 // }
292 BuildLoopNest(1);
293 HPhi* k_header = InsertLoopPhi(0, 0);
294 k_header->AddInput(constant0_);
295
296 HBasicBlock* ifTrue;
297 HBasicBlock* ifFalse;
298 HPhi* k_body = BuildIf(0, &ifTrue, &ifFalse);
299
300 // True-branch.
301 HInstruction* inc1 = MakeBinOp<HAdd>(ifTrue, DataType::Type::kInt32, k_header, constant1_);
302 k_body->AddInput(inc1);
303 // False-branch.
304 HInstruction* inc2 = MakeBinOp<HAdd>(ifFalse, DataType::Type::kInt32, k_header, constant1_);
305 k_body->AddInput(inc2);
306 // Merge over a phi.
307 HInstruction* store = InsertArrayStore(k_body, 0);
308 k_header->AddInput(k_body);
309 PerformInductionVarAnalysis();
310
311 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(k_header, 0).c_str());
312 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str());
313
314 // Both increments get same induction.
315 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1));
316 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2));
317 }
318
TEST_F(InductionVarAnalysisTest,FindTwoWayDerivedInduction)319 TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
320 // Setup:
321 // for (int i = 0; i < 100; i++) {
322 // if () k = i + 1;
323 // else k = i + 1;
324 // a[k] = 0;
325 // }
326 BuildLoopNest(1);
327 HBasicBlock* ifTrue;
328 HBasicBlock* ifFalse;
329 HPhi* k = BuildIf(0, &ifTrue, &ifFalse);
330
331 // True-branch.
332 HInstruction* inc1 = MakeBinOp<HAdd>(ifTrue, DataType::Type::kInt32, basic_[0], constant1_);
333 k->AddInput(inc1);
334 // False-branch.
335 HInstruction* inc2 = MakeBinOp<HAdd>(ifFalse, DataType::Type::kInt32, basic_[0], constant1_);
336 k->AddInput(inc2);
337 // Merge over a phi.
338 HInstruction* store = InsertArrayStore(k, 0);
339 PerformInductionVarAnalysis();
340
341 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str());
342
343 // Both increments get same induction.
344 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1));
345 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2));
346 }
347
TEST_F(InductionVarAnalysisTest,AddLinear)348 TEST_F(InductionVarAnalysisTest, AddLinear) {
349 // Setup:
350 // for (int i = 0; i < 100; i++) {
351 // t1 = i + i;
352 // t2 = 7 + i;
353 // t3 = t1 + t2;
354 // }
355 BuildLoopNest(1);
356
357 HInstruction* add1 = InsertInstruction(
358 new (GetAllocator()) HAdd(DataType::Type::kInt32, basic_[0], basic_[0]), 0);
359 HInstruction* add2 = InsertInstruction(
360 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant7_, basic_[0]), 0);
361 HInstruction* add3 = InsertInstruction(
362 new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, add2), 0);
363 PerformInductionVarAnalysis();
364
365 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(basic_[0], 0).c_str());
366 EXPECT_STREQ("(((1) + (1)) * i + (0)):Int32", GetInductionInfo(add1, 0).c_str());
367 EXPECT_STREQ("((1) * i + (7)):Int32", GetInductionInfo(add2, 0).c_str());
368 EXPECT_STREQ("((((1) + (1)) + (1)) * i + (7)):Int32", GetInductionInfo(add3, 0).c_str());
369 }
370
TEST_F(InductionVarAnalysisTest,FindPolynomialInduction)371 TEST_F(InductionVarAnalysisTest, FindPolynomialInduction) {
372 // Setup:
373 // k = 1;
374 // for (int i = 0; i < 100; i++) {
375 // t = i * 2;
376 // t = 100 + t
377 // k = t + k; // polynomial
378 // }
379 BuildLoopNest(1);
380 HPhi* k_header = InsertLoopPhi(0, 0);
381 k_header->AddInput(constant1_);
382
383 HInstruction* mul = InsertInstruction(
384 new (GetAllocator()) HMul(DataType::Type::kInt32, basic_[0], constant2_), 0);
385 HInstruction* add = InsertInstruction(
386 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant100_, mul), 0);
387 HInstruction* pol = InsertInstruction(
388 new (GetAllocator()) HAdd(DataType::Type::kInt32, add, k_header), 0);
389 k_header->AddInput(pol);
390 PerformInductionVarAnalysis();
391
392 // Note, only the phi in the cycle and the base linear induction are classified.
393 EXPECT_STREQ("poly(sum_lt(((2) * i + (100)):Int32) + (1)):Int32",
394 GetInductionInfo(k_header, 0).c_str());
395 EXPECT_STREQ("((2) * i + (100)):Int32", GetInductionInfo(add, 0).c_str());
396 EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str());
397 }
398
TEST_F(InductionVarAnalysisTest,FindPolynomialInductionAndDerived)399 TEST_F(InductionVarAnalysisTest, FindPolynomialInductionAndDerived) {
400 // Setup:
401 // k = 1;
402 // for (int i = 0; i < 100; i++) {
403 // t = k + 100;
404 // t = k - 1;
405 // t = - t
406 // t = k * 2;
407 // t = k << 2;
408 // k = k + i; // polynomial
409 // }
410 BuildLoopNest(1);
411 HPhi* k_header = InsertLoopPhi(0, 0);
412 k_header->AddInput(constant1_);
413
414 HInstruction* add = InsertInstruction(
415 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0);
416 HInstruction* sub = InsertInstruction(
417 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0);
418 HInstruction* neg = InsertInstruction(
419 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0);
420 HInstruction* mul = InsertInstruction(
421 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0);
422 HInstruction* shl = InsertInstruction(
423 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0);
424 HInstruction* pol = InsertInstruction(
425 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, basic_[0]), 0);
426 k_header->AddInput(pol);
427 PerformInductionVarAnalysis();
428
429 // Note, only the phi in the cycle and derived are classified.
430 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + (1)):Int32",
431 GetInductionInfo(k_header, 0).c_str());
432 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + ((1) + (100))):Int32",
433 GetInductionInfo(add, 0).c_str());
434 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + ((1) - (1))):Int32",
435 GetInductionInfo(sub, 0).c_str());
436 EXPECT_STREQ("poly(sum_lt((( - (1)) * i + (0)):Int32) + ((1) - (1))):Int32",
437 GetInductionInfo(neg, 0).c_str());
438 EXPECT_STREQ("poly(sum_lt(((2) * i + (0)):Int32) + (2)):Int32",
439 GetInductionInfo(mul, 0).c_str());
440 EXPECT_STREQ("poly(sum_lt(((4) * i + (0)):Int32) + (4)):Int32",
441 GetInductionInfo(shl, 0).c_str());
442 EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str());
443 }
444
TEST_F(InductionVarAnalysisTest,AddPolynomial)445 TEST_F(InductionVarAnalysisTest, AddPolynomial) {
446 // Setup:
447 // k = 7;
448 // for (int i = 0; i < 100; i++) {
449 // t = k + k;
450 // t = t + k;
451 // k = k + i
452 // }
453 BuildLoopNest(1);
454 HPhi* k_header = InsertLoopPhi(0, 0);
455 k_header->AddInput(constant7_);
456
457 HInstruction* add1 = InsertInstruction(
458 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, k_header), 0);
459 HInstruction* add2 = InsertInstruction(
460 new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, k_header), 0);
461 HInstruction* add3 = InsertInstruction(
462 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, basic_[0]), 0);
463 k_header->AddInput(add3);
464 PerformInductionVarAnalysis();
465
466 // Note, only the phi in the cycle and added-derived are classified.
467 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + (7)):Int32",
468 GetInductionInfo(k_header, 0).c_str());
469 EXPECT_STREQ("poly(sum_lt((((1) + (1)) * i + (0)):Int32) + ((7) + (7))):Int32",
470 GetInductionInfo(add1, 0).c_str());
471 EXPECT_STREQ(
472 "poly(sum_lt(((((1) + (1)) + (1)) * i + (0)):Int32) + (((7) + (7)) + (7))):Int32",
473 GetInductionInfo(add2, 0).c_str());
474 EXPECT_STREQ("", GetInductionInfo(add3, 0).c_str());
475 }
476
TEST_F(InductionVarAnalysisTest,FindGeometricMulInduction)477 TEST_F(InductionVarAnalysisTest, FindGeometricMulInduction) {
478 // Setup:
479 // k = 1;
480 // for (int i = 0; i < 100; i++) {
481 // k = k * 100; // geometric (x 100)
482 // }
483 BuildLoopNest(1);
484 HPhi* k_header = InsertLoopPhi(0, 0);
485 k_header->AddInput(constant1_);
486
487 HInstruction* mul = InsertInstruction(
488 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant100_), 0);
489 k_header->AddInput(mul);
490 PerformInductionVarAnalysis();
491
492 EXPECT_STREQ("geo((1) * 100 ^ i + (0)):Int32", GetInductionInfo(k_header, 0).c_str());
493 EXPECT_STREQ("geo((100) * 100 ^ i + (0)):Int32", GetInductionInfo(mul, 0).c_str());
494 }
495
TEST_F(InductionVarAnalysisTest,FindGeometricShlInductionAndDerived)496 TEST_F(InductionVarAnalysisTest, FindGeometricShlInductionAndDerived) {
497 // Setup:
498 // k = 1;
499 // for (int i = 0; i < 100; i++) {
500 // t = k + 1;
501 // k = k << 1; // geometric (x 2)
502 // t = k + 100;
503 // t = k - 1;
504 // t = - t;
505 // t = k * 2;
506 // t = k << 2;
507 // }
508 BuildLoopNest(1);
509 HPhi* k_header = InsertLoopPhi(0, 0);
510 k_header->AddInput(constant1_);
511
512 HInstruction* add1 = InsertInstruction(
513 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0);
514 HInstruction* shl1 = InsertInstruction(
515 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant1_), 0);
516 HInstruction* add2 = InsertInstruction(
517 new (GetAllocator()) HAdd(DataType::Type::kInt32, shl1, constant100_), 0);
518 HInstruction* sub = InsertInstruction(
519 new (GetAllocator()) HSub(DataType::Type::kInt32, shl1, constant1_), 0);
520 HInstruction* neg = InsertInstruction(
521 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0);
522 HInstruction* mul = InsertInstruction(
523 new (GetAllocator()) HMul(DataType::Type::kInt32, shl1, constant2_), 0);
524 HInstruction* shl2 = InsertInstruction(
525 new (GetAllocator()) HShl(DataType::Type::kInt32, shl1, constant2_), 0);
526 k_header->AddInput(shl1);
527 PerformInductionVarAnalysis();
528
529 EXPECT_STREQ("geo((1) * 2 ^ i + (0)):Int32", GetInductionInfo(k_header, 0).c_str());
530 EXPECT_STREQ("geo((1) * 2 ^ i + (1)):Int32", GetInductionInfo(add1, 0).c_str());
531 EXPECT_STREQ("geo((2) * 2 ^ i + (0)):Int32", GetInductionInfo(shl1, 0).c_str());
532 EXPECT_STREQ("geo((2) * 2 ^ i + (100)):Int32", GetInductionInfo(add2, 0).c_str());
533 EXPECT_STREQ("geo((2) * 2 ^ i + ((0) - (1))):Int32", GetInductionInfo(sub, 0).c_str());
534 EXPECT_STREQ("geo(( - (2)) * 2 ^ i + ( - ((0) - (1)))):Int32",
535 GetInductionInfo(neg, 0).c_str());
536 EXPECT_STREQ("geo(((2) * (2)) * 2 ^ i + (0)):Int32", GetInductionInfo(mul, 0).c_str());
537 EXPECT_STREQ("geo(((2) * (4)) * 2 ^ i + (0)):Int32", GetInductionInfo(shl2, 0).c_str());
538 }
539
TEST_F(InductionVarAnalysisTest,FindGeometricDivInductionAndDerived)540 TEST_F(InductionVarAnalysisTest, FindGeometricDivInductionAndDerived) {
541 // Setup:
542 // k = 1;
543 // for (int i = 0; i < 100; i++) {
544 // t = k + 100;
545 // t = k - 1;
546 // t = - t
547 // t = k * 2;
548 // t = k << 2;
549 // k = k / 100; // geometric (/ 100)
550 // }
551 BuildLoopNest(1);
552 HPhi* k_header = InsertLoopPhi(0, 0);
553 k_header->AddInput(constant1_);
554
555 HInstruction* add = InsertInstruction(
556 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0);
557 HInstruction* sub = InsertInstruction(
558 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0);
559 HInstruction* neg = InsertInstruction(
560 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0);
561 HInstruction* mul = InsertInstruction(
562 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0);
563 HInstruction* shl = InsertInstruction(
564 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0);
565 HInstruction* div = InsertInstruction(
566 new (GetAllocator()) HDiv(DataType::Type::kInt32, k_header, constant100_, kNoDexPc), 0);
567 k_header->AddInput(div);
568 PerformInductionVarAnalysis();
569
570 // Note, only the phi in the cycle and direct additive derived are classified.
571 EXPECT_STREQ("geo((1) * 100 ^ -i + (0)):Int32", GetInductionInfo(k_header, 0).c_str());
572 EXPECT_STREQ("geo((1) * 100 ^ -i + (100)):Int32", GetInductionInfo(add, 0).c_str());
573 EXPECT_STREQ("geo((1) * 100 ^ -i + ((0) - (1))):Int32", GetInductionInfo(sub, 0).c_str());
574 EXPECT_STREQ("", GetInductionInfo(neg, 0).c_str());
575 EXPECT_STREQ("", GetInductionInfo(mul, 0).c_str());
576 EXPECT_STREQ("", GetInductionInfo(shl, 0).c_str());
577 EXPECT_STREQ("", GetInductionInfo(div, 0).c_str());
578 }
579
TEST_F(InductionVarAnalysisTest,FindGeometricShrInduction)580 TEST_F(InductionVarAnalysisTest, FindGeometricShrInduction) {
581 // Setup:
582 // k = 100;
583 // for (int i = 0; i < 100; i++) {
584 // k = k >> 1; // geometric (/ 2)
585 // }
586 BuildLoopNest(1);
587 HPhi* k_header = InsertLoopPhi(0, 0);
588 k_header->AddInput(constant100_);
589
590 HInstruction* shr = InsertInstruction(
591 new (GetAllocator()) HShr(DataType::Type::kInt32, k_header, constant1_), 0);
592 k_header->AddInput(shr);
593 PerformInductionVarAnalysis();
594
595 // Note, only the phi in the cycle is classified.
596 EXPECT_STREQ("geo((100) * 2 ^ -i + (0)):Int32", GetInductionInfo(k_header, 0).c_str());
597 EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str());
598 }
599
TEST_F(InductionVarAnalysisTest,FindNotGeometricShrInduction)600 TEST_F(InductionVarAnalysisTest, FindNotGeometricShrInduction) {
601 // Setup:
602 // k = -1;
603 // for (int i = 0; i < 100; i++) {
604 // k = k >> 1; // initial value is negative
605 // }
606 BuildLoopNest(1);
607 HPhi* k_header = InsertLoopPhi(0, 0);
608 k_header->AddInput(constantm1_);
609
610 HInstruction* shr = InsertInstruction(
611 new (GetAllocator()) HShr(DataType::Type::kInt32, k_header, constant1_), 0);
612 k_header->AddInput(shr);
613 PerformInductionVarAnalysis();
614
615 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str());
616 EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str());
617 }
618
TEST_F(InductionVarAnalysisTest,FindRemWrapAroundInductionAndDerived)619 TEST_F(InductionVarAnalysisTest, FindRemWrapAroundInductionAndDerived) {
620 // Setup:
621 // k = 100;
622 // for (int i = 0; i < 100; i++) {
623 // t = k + 100;
624 // t = k - 1;
625 // t = -t
626 // t = k * 2;
627 // t = k << 2;
628 // k = k % 7;
629 // }
630 BuildLoopNest(1);
631 HPhi* k_header = InsertLoopPhi(0, 0);
632 k_header->AddInput(constant100_);
633
634 HInstruction* add = InsertInstruction(
635 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0);
636 HInstruction* sub = InsertInstruction(
637 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0);
638 HInstruction* neg = InsertInstruction(
639 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0);
640 HInstruction* mul = InsertInstruction(
641 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0);
642 HInstruction* shl = InsertInstruction(
643 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0);
644 HInstruction* rem = InsertInstruction(
645 new (GetAllocator()) HRem(DataType::Type::kInt32, k_header, constant7_, kNoDexPc), 0);
646 k_header->AddInput(rem);
647 PerformInductionVarAnalysis();
648
649 // Note, only the phi in the cycle and derived are classified.
650 EXPECT_STREQ("wrap((100), ((100) % (7))):Int32", GetInductionInfo(k_header, 0).c_str());
651 EXPECT_STREQ("wrap(((100) + (100)), (((100) % (7)) + (100))):Int32",
652 GetInductionInfo(add, 0).c_str());
653 EXPECT_STREQ("wrap(((100) - (1)), (((100) % (7)) - (1))):Int32",
654 GetInductionInfo(sub, 0).c_str());
655 EXPECT_STREQ("wrap(( - ((100) - (1))), ( - (((100) % (7)) - (1)))):Int32",
656 GetInductionInfo(neg, 0).c_str());
657 EXPECT_STREQ("wrap(((100) * (2)), (((100) % (7)) * (2))):Int32",
658 GetInductionInfo(mul, 0).c_str());
659 EXPECT_STREQ("wrap(((100) * (4)), (((100) % (7)) * (4))):Int32",
660 GetInductionInfo(shl, 0).c_str());
661 EXPECT_STREQ("", GetInductionInfo(rem, 0).c_str());
662 }
663
TEST_F(InductionVarAnalysisTest,FindFirstOrderWrapAroundInduction)664 TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
665 // Setup:
666 // k = 0;
667 // for (int i = 0; i < 100; i++) {
668 // a[k] = 0;
669 // k = 100 - i;
670 // }
671 BuildLoopNest(1);
672 HPhi* k_header = InsertLoopPhi(0, 0);
673 k_header->AddInput(constant0_);
674
675 HInstruction* store = InsertArrayStore(k_header, 0);
676 HInstruction* sub = InsertInstruction(
677 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0]), 0);
678 k_header->AddInput(sub);
679 PerformInductionVarAnalysis();
680
681 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):Int32):Int32",
682 GetInductionInfo(k_header, 0).c_str());
683 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):Int32):Int32",
684 GetInductionInfo(store->InputAt(1), 0).c_str());
685 EXPECT_STREQ("(( - (1)) * i + (100)):Int32", GetInductionInfo(sub, 0).c_str());
686 }
687
TEST_F(InductionVarAnalysisTest,FindSecondOrderWrapAroundInduction)688 TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
689 // Setup:
690 // k = 0;
691 // t = 100;
692 // for (int i = 0; i < 100; i++) {
693 // a[k] = 0;
694 // k = t;
695 // t = 100 - i;
696 // }
697 BuildLoopNest(1);
698 HPhi* k_header = InsertLoopPhi(0, 0);
699 k_header->AddInput(constant0_);
700 HPhi* t = InsertLoopPhi(1, 0);
701 t->AddInput(constant100_);
702
703 HInstruction* store = InsertArrayStore(k_header, 0);
704 k_header->AddInput(t);
705 HInstruction* sub = InsertInstruction(
706 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0], 0), 0);
707 t->AddInput(sub);
708 PerformInductionVarAnalysis();
709
710 EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100)):Int32):Int32):Int32",
711 GetInductionInfo(store->InputAt(1), 0).c_str());
712 }
713
TEST_F(InductionVarAnalysisTest,FindWrapAroundDerivedInduction)714 TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
715 // Setup:
716 // k = 0;
717 // for (int i = 0; i < 100; i++) {
718 // t = k + 100;
719 // t = k - 100;
720 // t = k * 100;
721 // t = k << 1;
722 // t = - k;
723 // k = i << 1;
724 // t = - k;
725 // }
726 BuildLoopNest(1);
727 HPhi* k_header = InsertLoopPhi(0, 0);
728 k_header->AddInput(constant0_);
729
730 HInstruction* add = InsertInstruction(
731 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0);
732 HInstruction* sub = InsertInstruction(
733 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant100_), 0);
734 HInstruction* mul = InsertInstruction(
735 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant100_), 0);
736 HInstruction* shl1 = InsertInstruction(
737 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant1_), 0);
738 HInstruction* neg1 = InsertInstruction(
739 new (GetAllocator()) HNeg(DataType::Type::kInt32, k_header), 0);
740 HInstruction* shl2 = InsertInstruction(
741 new (GetAllocator()) HShl(DataType::Type::kInt32, basic_[0], constant1_), 0);
742 HInstruction* neg2 = InsertInstruction(
743 new (GetAllocator()) HNeg(DataType::Type::kInt32, shl2), 0);
744 k_header->AddInput(shl2);
745 PerformInductionVarAnalysis();
746
747 EXPECT_STREQ("wrap((100), ((2) * i + (100)):Int32):Int32",
748 GetInductionInfo(add, 0).c_str());
749 EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))):Int32):Int32",
750 GetInductionInfo(sub, 0).c_str());
751 EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):Int32):Int32",
752 GetInductionInfo(mul, 0).c_str());
753 EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):Int32):Int32",
754 GetInductionInfo(shl1, 0).c_str());
755 EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):Int32):Int32",
756 GetInductionInfo(neg1, 0).c_str());
757 EXPECT_STREQ("((2) * i + (0)):Int32", GetInductionInfo(shl2, 0).c_str());
758 EXPECT_STREQ("(( - (2)) * i + (0)):Int32", GetInductionInfo(neg2, 0).c_str());
759 }
760
TEST_F(InductionVarAnalysisTest,FindPeriodicInduction)761 TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
762 // Setup:
763 // k = 0;
764 // t = 100;
765 // for (int i = 0; i < 100; i++) {
766 // a[k] = 0;
767 // a[t] = 0;
768 // // Swap t <-> k.
769 // d = t;
770 // t = k;
771 // k = d;
772 // }
773 BuildLoopNest(1);
774 HPhi* k_header = InsertLoopPhi(0, 0);
775 k_header->AddInput(constant0_);
776 HPhi* t = InsertLoopPhi(1, 0);
777 t->AddInput(constant100_);
778
779 HInstruction* store1 = InsertArrayStore(k_header, 0);
780 HInstruction* store2 = InsertArrayStore(t, 0);
781 k_header->AddInput(t);
782 t->AddInput(k_header);
783 PerformInductionVarAnalysis();
784
785 EXPECT_STREQ("periodic((0), (100)):Int32", GetInductionInfo(store1->InputAt(1), 0).c_str());
786 EXPECT_STREQ("periodic((100), (0)):Int32", GetInductionInfo(store2->InputAt(1), 0).c_str());
787 }
788
TEST_F(InductionVarAnalysisTest,FindIdiomaticPeriodicInduction)789 TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) {
790 // Setup:
791 // k = 0;
792 // for (int i = 0; i < 100; i++) {
793 // a[k] = 0;
794 // k = 1 - k;
795 // }
796 BuildLoopNest(1);
797 HPhi* k_header = InsertLoopPhi(0, 0);
798 k_header->AddInput(constant0_);
799
800 HInstruction* store = InsertArrayStore(k_header, 0);
801 HInstruction* sub = InsertInstruction(
802 new (GetAllocator()) HSub(DataType::Type::kInt32, constant1_, k_header), 0);
803 k_header->AddInput(sub);
804 PerformInductionVarAnalysis();
805
806 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str());
807 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(sub, 0).c_str());
808 }
809
TEST_F(InductionVarAnalysisTest,FindXorPeriodicInduction)810 TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) {
811 // Setup:
812 // k = 0;
813 // for (int i = 0; i < 100; i++) {
814 // a[k] = 0;
815 // k = k ^ 1;
816 // }
817 BuildLoopNest(1);
818 HPhi* k_header = InsertLoopPhi(0, 0);
819 k_header->AddInput(constant0_);
820
821 HInstruction* store = InsertArrayStore(k_header, 0);
822 HInstruction* x = InsertInstruction(
823 new (GetAllocator()) HXor(DataType::Type::kInt32, k_header, constant1_), 0);
824 k_header->AddInput(x);
825 PerformInductionVarAnalysis();
826
827 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str());
828 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(x, 0).c_str());
829 }
830
TEST_F(InductionVarAnalysisTest,FindXorConstantLeftPeriodicInduction)831 TEST_F(InductionVarAnalysisTest, FindXorConstantLeftPeriodicInduction) {
832 // Setup:
833 // k = 1;
834 // for (int i = 0; i < 100; i++) {
835 // k = 1 ^ k;
836 // }
837 BuildLoopNest(1);
838 HPhi* k_header = InsertLoopPhi(0, 0);
839 k_header->AddInput(constant1_);
840
841 HInstruction* x = InsertInstruction(
842 new (GetAllocator()) HXor(DataType::Type::kInt32, constant1_, k_header), 0);
843 k_header->AddInput(x);
844 PerformInductionVarAnalysis();
845
846 EXPECT_STREQ("periodic((1), ((1) ^ (1))):Int32", GetInductionInfo(k_header, 0).c_str());
847 EXPECT_STREQ("periodic(((1) ^ (1)), (1)):Int32", GetInductionInfo(x, 0).c_str());
848 }
849
TEST_F(InductionVarAnalysisTest,FindXor100PeriodicInduction)850 TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) {
851 // Setup:
852 // k = 1;
853 // for (int i = 0; i < 100; i++) {
854 // k = k ^ 100;
855 // }
856 BuildLoopNest(1);
857 HPhi* k_header = InsertLoopPhi(0, 0);
858 k_header->AddInput(constant1_);
859
860 HInstruction* x = InsertInstruction(
861 new (GetAllocator()) HXor(DataType::Type::kInt32, k_header, constant100_), 0);
862 k_header->AddInput(x);
863 PerformInductionVarAnalysis();
864
865 EXPECT_STREQ("periodic((1), ((1) ^ (100))):Int32", GetInductionInfo(k_header, 0).c_str());
866 EXPECT_STREQ("periodic(((1) ^ (100)), (1)):Int32", GetInductionInfo(x, 0).c_str());
867 }
868
TEST_F(InductionVarAnalysisTest,FindBooleanEqPeriodicInduction)869 TEST_F(InductionVarAnalysisTest, FindBooleanEqPeriodicInduction) {
870 // Setup:
871 // k = 0;
872 // for (int i = 0; i < 100; i++) {
873 // k = (k == 0);
874 // }
875 BuildLoopNest(1);
876 HPhi* k_header = InsertLoopPhi(0, 0);
877 k_header->AddInput(constant0_);
878
879 HInstruction* x = InsertInstruction(new (GetAllocator()) HEqual(k_header, constant0_), 0);
880 k_header->AddInput(x);
881 PerformInductionVarAnalysis();
882
883 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str());
884 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str());
885 }
886
TEST_F(InductionVarAnalysisTest,FindBooleanEqConstantLeftPeriodicInduction)887 TEST_F(InductionVarAnalysisTest, FindBooleanEqConstantLeftPeriodicInduction) {
888 // Setup:
889 // k = 0;
890 // for (int i = 0; i < 100; i++) {
891 // k = (0 == k);
892 // }
893 BuildLoopNest(1);
894 HPhi* k_header = InsertLoopPhi(0, 0);
895 k_header->AddInput(constant0_);
896
897 HInstruction* x = InsertInstruction(new (GetAllocator()) HEqual(constant0_, k_header), 0);
898 k_header->AddInput(x);
899 PerformInductionVarAnalysis();
900
901 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str());
902 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str());
903 }
904
TEST_F(InductionVarAnalysisTest,FindBooleanNePeriodicInduction)905 TEST_F(InductionVarAnalysisTest, FindBooleanNePeriodicInduction) {
906 // Setup:
907 // k = 0;
908 // for (int i = 0; i < 100; i++) {
909 // k = (k != 1);
910 // }
911 BuildLoopNest(1);
912 HPhi* k_header = InsertLoopPhi(0, 0);
913 k_header->AddInput(constant0_);
914
915 HInstruction* x = InsertInstruction(new (GetAllocator()) HNotEqual(k_header, constant1_), 0);
916 k_header->AddInput(x);
917 PerformInductionVarAnalysis();
918
919 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str());
920 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str());
921 }
922
TEST_F(InductionVarAnalysisTest,FindBooleanNeConstantLeftPeriodicInduction)923 TEST_F(InductionVarAnalysisTest, FindBooleanNeConstantLeftPeriodicInduction) {
924 // Setup:
925 // k = 0;
926 // for (int i = 0; i < 100; i++) {
927 // k = (1 != k);
928 // }
929 BuildLoopNest(1);
930 HPhi* k_header = InsertLoopPhi(0, 0);
931 k_header->AddInput(constant0_);
932
933 HInstruction* x = InsertInstruction(new (GetAllocator()) HNotEqual(constant1_, k_header), 0);
934 k_header->AddInput(x);
935 PerformInductionVarAnalysis();
936
937 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str());
938 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str());
939 }
940
TEST_F(InductionVarAnalysisTest,FindDerivedPeriodicInduction)941 TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
942 // Setup:
943 // k = 0;
944 // for (int i = 0; i < 100; i++) {
945 // t = - k;
946 // k = 1 - k;
947 // t = k + 100;
948 // t = k - 100;
949 // t = k * 100;
950 // t = k << 1;
951 // t = - k;
952 // }
953 BuildLoopNest(1);
954 HPhi* k_header = InsertLoopPhi(0, 0);
955 k_header->AddInput(constant0_);
956
957 HInstruction* neg1 = InsertInstruction(
958 new (GetAllocator()) HNeg(DataType::Type::kInt32, k_header), 0);
959 HInstruction* idiom = InsertInstruction(
960 new (GetAllocator()) HSub(DataType::Type::kInt32, constant1_, k_header), 0);
961 HInstruction* add = InsertInstruction(
962 new (GetAllocator()) HAdd(DataType::Type::kInt32, idiom, constant100_), 0);
963 HInstruction* sub = InsertInstruction(
964 new (GetAllocator()) HSub(DataType::Type::kInt32, idiom, constant100_), 0);
965 HInstruction* mul = InsertInstruction(
966 new (GetAllocator()) HMul(DataType::Type::kInt32, idiom, constant100_), 0);
967 HInstruction* shl = InsertInstruction(
968 new (GetAllocator()) HShl(DataType::Type::kInt32, idiom, constant1_), 0);
969 HInstruction* neg2 = InsertInstruction(
970 new (GetAllocator()) HNeg(DataType::Type::kInt32, idiom), 0);
971 k_header->AddInput(idiom);
972 PerformInductionVarAnalysis();
973
974 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(k_header, 0).c_str());
975 EXPECT_STREQ("periodic((0), ( - (1))):Int32", GetInductionInfo(neg1, 0).c_str());
976 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(idiom, 0).c_str());
977 EXPECT_STREQ("periodic(((1) + (100)), (100)):Int32", GetInductionInfo(add, 0).c_str());
978 EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):Int32", GetInductionInfo(sub, 0).c_str());
979 EXPECT_STREQ("periodic((100), (0)):Int32", GetInductionInfo(mul, 0).c_str());
980 EXPECT_STREQ("periodic((2), (0)):Int32", GetInductionInfo(shl, 0).c_str());
981 EXPECT_STREQ("periodic(( - (1)), (0)):Int32", GetInductionInfo(neg2, 0).c_str());
982 }
983
TEST_F(InductionVarAnalysisTest,FindDeepLoopInduction)984 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
985 // Setup:
986 // k = 0;
987 // for (int i_0 = 0; i_0 < 100; i_0++) {
988 // ..
989 // for (int i_9 = 0; i_9 < 100; i_9++) {
990 // k = 1 + k;
991 // a[k] = 0;
992 // }
993 // ..
994 // }
995 BuildLoopNest(10);
996
997 HPhi* k_header[10];
998 for (int d = 0; d < 10; d++) {
999 k_header[d] = InsertLoopPhi(0, d);
1000 }
1001
1002 HInstruction* inc = InsertInstruction(
1003 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant1_, k_header[9]), 9);
1004 HInstruction* store = InsertArrayStore(inc, 9);
1005
1006 for (int d = 0; d < 10; d++) {
1007 k_header[d]->AddInput((d != 0) ? k_header[d - 1] : constant0_);
1008 k_header[d]->AddInput((d != 9) ? k_header[d + 1] : inc);
1009 }
1010 PerformInductionVarAnalysis();
1011
1012 // Avoid exact phi number, since that depends on the SSA building phase.
1013 std::regex r("\\(\\(1\\) \\* i \\+ "
1014 "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\):Int32");
1015
1016 for (int d = 0; d < 10; d++) {
1017 if (d == 9) {
1018 EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r));
1019 } else {
1020 EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
1021 }
1022 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[d], d).c_str());
1023 // Trip-count.
1024 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(d).c_str());
1025 }
1026 }
1027
TEST_F(InductionVarAnalysisTest,ByteInductionIntLoopControl)1028 TEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) {
1029 // Setup:
1030 // for (int i = 0; i < 100; i++) {
1031 // k = (byte) i;
1032 // a[k] = 0;
1033 // a[i] = 0;
1034 // }
1035 BuildLoopNest(1);
1036 HInstruction* conv = InsertInstruction(
1037 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, basic_[0], kNoDexPc), 0);
1038 HInstruction* store1 = InsertArrayStore(conv, 0);
1039 HInstruction* store2 = InsertArrayStore(basic_[0], 0);
1040 PerformInductionVarAnalysis();
1041
1042 // Regular int induction (i) is transferred over conversion into byte induction (k).
1043 EXPECT_STREQ("((1) * i + (0)):Int8", GetInductionInfo(store1->InputAt(1), 0).c_str());
1044 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(store2->InputAt(1), 0).c_str());
1045 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[0], 0).c_str());
1046
1047 // Narrowing detected.
1048 EXPECT_TRUE(IsNarrowingLinear(store1->InputAt(1)));
1049 EXPECT_FALSE(IsNarrowingLinear(store2->InputAt(1)));
1050
1051 // Type matters!
1052 EXPECT_FALSE(HaveSameInduction(store1->InputAt(1), store2->InputAt(1)));
1053
1054 // Trip-count.
1055 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(0).c_str());
1056 }
1057
TEST_F(InductionVarAnalysisTest,ByteInductionDerivedIntLoopControl)1058 TEST_F(InductionVarAnalysisTest, ByteInductionDerivedIntLoopControl) {
1059 // Setup:
1060 // for (int i = 0; i < 100; i++) {
1061 // k = (byte) i;
1062 // a[k] = 0;
1063 // k = k + 1
1064 // a[k] = 0;
1065 // }
1066 BuildLoopNest(1);
1067 HInstruction* conv = InsertInstruction(
1068 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, basic_[0], kNoDexPc), 0);
1069 HInstruction* store1 = InsertArrayStore(conv, 0);
1070 HInstruction* add = InsertInstruction(
1071 new (GetAllocator()) HAdd(DataType::Type::kInt32, conv, constant1_), 0);
1072 HInstruction* store2 = InsertArrayStore(add, 0);
1073
1074 PerformInductionVarAnalysis();
1075
1076 // Byte induction (k) is detected, but it does not transfer over the addition,
1077 // since this may yield out-of-type values.
1078 EXPECT_STREQ("((1) * i + (0)):Int8", GetInductionInfo(store1->InputAt(1), 0).c_str());
1079 EXPECT_STREQ("", GetInductionInfo(store2->InputAt(1), 0).c_str());
1080
1081 // Narrowing detected.
1082 EXPECT_TRUE(IsNarrowingLinear(store1->InputAt(1)));
1083 EXPECT_FALSE(IsNarrowingLinear(store2->InputAt(1))); // works for null
1084 }
1085
TEST_F(InductionVarAnalysisTest,ByteInduction)1086 TEST_F(InductionVarAnalysisTest, ByteInduction) {
1087 // Setup:
1088 // k = -128;
1089 // for (int i = 0; i < 100; i++) {
1090 // k = k + 1;
1091 // k = (byte) k;
1092 // }
1093 BuildLoopNest(1);
1094 HPhi* k_header = InsertLoopPhi(0, 0);
1095 k_header->AddInput(graph_->GetIntConstant(-128));
1096
1097 HInstruction* add = InsertInstruction(
1098 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0);
1099 HInstruction* conv = InsertInstruction(
1100 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, add, kNoDexPc), 0);
1101 k_header->AddInput(conv);
1102 PerformInductionVarAnalysis();
1103
1104 // Byte induction (k) is detected, but it does not transfer over the addition,
1105 // since this may yield out-of-type values.
1106 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(k_header, 0).c_str());
1107 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str());
1108
1109 // Narrowing detected.
1110 EXPECT_TRUE(IsNarrowingLinear(k_header));
1111 EXPECT_FALSE(IsNarrowingLinear(add)); // works for null
1112 }
1113
TEST_F(InductionVarAnalysisTest,NoByteInduction1)1114 TEST_F(InductionVarAnalysisTest, NoByteInduction1) {
1115 // Setup:
1116 // k = -129; / does not fit!
1117 // for (int i = 0; i < 100; i++) {
1118 // k = k + 1;
1119 // k = (byte) k;
1120 // }
1121 BuildLoopNest(1);
1122 HPhi* k_header = InsertLoopPhi(0, 0);
1123 k_header->AddInput(graph_->GetIntConstant(-129));
1124
1125 HInstruction* add = InsertInstruction(
1126 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0);
1127 HInstruction* conv = InsertInstruction(
1128 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, add, kNoDexPc), 0);
1129 k_header->AddInput(conv);
1130 PerformInductionVarAnalysis();
1131
1132 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str());
1133 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str());
1134 }
1135
TEST_F(InductionVarAnalysisTest,NoByteInduction2)1136 TEST_F(InductionVarAnalysisTest, NoByteInduction2) {
1137 // Setup:
1138 // k = 0;
1139 // for (int i = 0; i < 100; i++) {
1140 // k = (byte) k; // conversion not done last!
1141 // k = k + 1;
1142 // }
1143 BuildLoopNest(1);
1144 HPhi* k_header = InsertLoopPhi(0, 0);
1145 k_header->AddInput(constant0_);
1146
1147 HInstruction* conv = InsertInstruction(
1148 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, k_header, kNoDexPc), 0);
1149 HInstruction* add = InsertInstruction(
1150 new (GetAllocator()) HAdd(DataType::Type::kInt32, conv, constant1_), 0);
1151 k_header->AddInput(add);
1152 PerformInductionVarAnalysis();
1153
1154 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str());
1155 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str());
1156 }
1157
TEST_F(InductionVarAnalysisTest,ByteLoopControl1)1158 TEST_F(InductionVarAnalysisTest, ByteLoopControl1) {
1159 // Setup:
1160 // for (byte i = -128; i < 127; i++) { // just fits!
1161 // }
1162 BuildLoopNest(1);
1163 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0);
1164 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1165 ifs->ReplaceInput(graph_->GetIntConstant(127), 1);
1166 HInstruction* conv =
1167 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, increment_[0], kNoDexPc);
1168 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1169 basic_[0]->ReplaceInput(conv, 1);
1170 PerformInductionVarAnalysis();
1171
1172 // Recorded at the phi, but not transferred to increment.
1173 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(basic_[0], 0).c_str());
1174 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1175
1176 // Narrowing detected.
1177 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1178 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1179
1180 // Trip-count.
1181 EXPECT_STREQ("(((127) - (-128)) (TC-loop) ((-128) < (127)))", GetTripCount(0).c_str());
1182 }
1183
TEST_F(InductionVarAnalysisTest,ByteLoopControl2)1184 TEST_F(InductionVarAnalysisTest, ByteLoopControl2) {
1185 // Setup:
1186 // for (byte i = -128; i < 128; i++) { // infinite loop!
1187 // }
1188 BuildLoopNest(1);
1189 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0);
1190 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1191 ifs->ReplaceInput(graph_->GetIntConstant(128), 1);
1192 HInstruction* conv =
1193 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, increment_[0], kNoDexPc);
1194 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1195 basic_[0]->ReplaceInput(conv, 1);
1196 PerformInductionVarAnalysis();
1197
1198 // Recorded at the phi, but not transferred to increment.
1199 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(basic_[0], 0).c_str());
1200 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1201
1202 // Narrowing detected.
1203 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1204 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1205
1206 // Trip-count undefined.
1207 EXPECT_STREQ("", GetTripCount(0).c_str());
1208 }
1209
TEST_F(InductionVarAnalysisTest,ShortLoopControl1)1210 TEST_F(InductionVarAnalysisTest, ShortLoopControl1) {
1211 // Setup:
1212 // for (short i = -32768; i < 32767; i++) { // just fits!
1213 // }
1214 BuildLoopNest(1);
1215 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0);
1216 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1217 ifs->ReplaceInput(graph_->GetIntConstant(32767), 1);
1218 HInstruction* conv =
1219 new (GetAllocator()) HTypeConversion(DataType::Type::kInt16, increment_[0], kNoDexPc);
1220 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1221 basic_[0]->ReplaceInput(conv, 1);
1222 PerformInductionVarAnalysis();
1223
1224 // Recorded at the phi, but not transferred to increment.
1225 EXPECT_STREQ("((1) * i + (-32768)):Int16", GetInductionInfo(basic_[0], 0).c_str());
1226 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1227
1228 // Narrowing detected.
1229 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1230 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1231
1232 // Trip-count.
1233 EXPECT_STREQ("(((32767) - (-32768)) (TC-loop) ((-32768) < (32767)))", GetTripCount(0).c_str());
1234 }
1235
TEST_F(InductionVarAnalysisTest,ShortLoopControl2)1236 TEST_F(InductionVarAnalysisTest, ShortLoopControl2) {
1237 // Setup:
1238 // for (short i = -32768; i < 32768; i++) { // infinite loop!
1239 // }
1240 BuildLoopNest(1);
1241 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0);
1242 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1243 ifs->ReplaceInput(graph_->GetIntConstant(32768), 1);
1244 HInstruction* conv =
1245 new (GetAllocator()) HTypeConversion(DataType::Type::kInt16, increment_[0], kNoDexPc);
1246 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1247 basic_[0]->ReplaceInput(conv, 1);
1248 PerformInductionVarAnalysis();
1249
1250 // Recorded at the phi, but not transferred to increment.
1251 EXPECT_STREQ("((1) * i + (-32768)):Int16", GetInductionInfo(basic_[0], 0).c_str());
1252 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1253
1254 // Narrowing detected.
1255 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1256 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1257
1258 // Trip-count undefined.
1259 EXPECT_STREQ("", GetTripCount(0).c_str());
1260 }
1261
TEST_F(InductionVarAnalysisTest,CharLoopControl1)1262 TEST_F(InductionVarAnalysisTest, CharLoopControl1) {
1263 // Setup:
1264 // for (char i = 0; i < 65535; i++) { // just fits!
1265 // }
1266 BuildLoopNest(1);
1267 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1268 ifs->ReplaceInput(graph_->GetIntConstant(65535), 1);
1269 HInstruction* conv =
1270 new (GetAllocator()) HTypeConversion(DataType::Type::kUint16, increment_[0], kNoDexPc);
1271 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1272 basic_[0]->ReplaceInput(conv, 1);
1273 PerformInductionVarAnalysis();
1274
1275 // Recorded at the phi, but not transferred to increment.
1276 EXPECT_STREQ("((1) * i + (0)):Uint16", GetInductionInfo(basic_[0], 0).c_str());
1277 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1278
1279 // Narrowing detected.
1280 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1281 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1282
1283 // Trip-count.
1284 EXPECT_STREQ("((65535) (TC-loop) ((0) < (65535)))", GetTripCount(0).c_str());
1285 }
1286
TEST_F(InductionVarAnalysisTest,CharLoopControl2)1287 TEST_F(InductionVarAnalysisTest, CharLoopControl2) {
1288 // Setup:
1289 // for (char i = 0; i < 65536; i++) { // infinite loop!
1290 // }
1291 BuildLoopNest(1);
1292 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
1293 ifs->ReplaceInput(graph_->GetIntConstant(65536), 1);
1294 HInstruction* conv =
1295 new (GetAllocator()) HTypeConversion(DataType::Type::kUint16, increment_[0], kNoDexPc);
1296 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
1297 basic_[0]->ReplaceInput(conv, 1);
1298 PerformInductionVarAnalysis();
1299
1300 // Recorded at the phi, but not transferred to increment.
1301 EXPECT_STREQ("((1) * i + (0)):Uint16", GetInductionInfo(basic_[0], 0).c_str());
1302 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str());
1303
1304 // Narrowing detected.
1305 EXPECT_TRUE(IsNarrowingLinear(basic_[0]));
1306 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null
1307
1308 // Trip-count undefined.
1309 EXPECT_STREQ("", GetTripCount(0).c_str());
1310 }
1311
1312 } // namespace art
1313