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