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 CommonCompilerTest {
31 public:
InductionVarAnalysisTest()32 InductionVarAnalysisTest() : pool_(), allocator_(&pool_) {
33 graph_ = CreateGraph(&allocator_);
34 }
35
~InductionVarAnalysisTest()36 ~InductionVarAnalysisTest() { }
37
38 // Builds single for-loop at depth d.
BuildForLoop(int d,int n)39 void BuildForLoop(int d, int n) {
40 ASSERT_LT(d, n);
41 loop_preheader_[d] = new (&allocator_) HBasicBlock(graph_);
42 graph_->AddBlock(loop_preheader_[d]);
43 loop_header_[d] = new (&allocator_) HBasicBlock(graph_);
44 graph_->AddBlock(loop_header_[d]);
45 loop_preheader_[d]->AddSuccessor(loop_header_[d]);
46 if (d < (n - 1)) {
47 BuildForLoop(d + 1, n);
48 }
49 loop_body_[d] = new (&allocator_) HBasicBlock(graph_);
50 graph_->AddBlock(loop_body_[d]);
51 loop_body_[d]->AddSuccessor(loop_header_[d]);
52 if (d < (n - 1)) {
53 loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]);
54 loop_header_[d + 1]->AddSuccessor(loop_body_[d]);
55 } else {
56 loop_header_[d]->AddSuccessor(loop_body_[d]);
57 }
58 }
59
60 // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n
61 // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further
62 // populate the loop with instructions to set up interesting scenarios.
BuildLoopNest(int n)63 void BuildLoopNest(int n) {
64 ASSERT_LE(n, 10);
65 graph_->SetNumberOfVRegs(n + 3);
66
67 // Build basic blocks with entry, nested loop, exit.
68 entry_ = new (&allocator_) HBasicBlock(graph_);
69 graph_->AddBlock(entry_);
70 BuildForLoop(0, n);
71 return_ = new (&allocator_) HBasicBlock(graph_);
72 graph_->AddBlock(return_);
73 exit_ = new (&allocator_) HBasicBlock(graph_);
74 graph_->AddBlock(exit_);
75 entry_->AddSuccessor(loop_preheader_[0]);
76 loop_header_[0]->AddSuccessor(return_);
77 return_->AddSuccessor(exit_);
78 graph_->SetEntryBlock(entry_);
79 graph_->SetExitBlock(exit_);
80
81 // Provide entry and exit instructions.
82 parameter_ = new (&allocator_) HParameterValue(
83 graph_->GetDexFile(), 0, 0, Primitive::kPrimNot, true);
84 entry_->AddInstruction(parameter_);
85 constant0_ = graph_->GetIntConstant(0);
86 constant1_ = graph_->GetIntConstant(1);
87 constant100_ = graph_->GetIntConstant(100);
88 float_constant0_ = graph_->GetFloatConstant(0.0f);
89 return_->AddInstruction(new (&allocator_) HReturnVoid());
90 exit_->AddInstruction(new (&allocator_) HExit());
91
92 // Provide loop instructions.
93 for (int d = 0; d < n; d++) {
94 basic_[d] = new (&allocator_) HPhi(&allocator_, d, 0, Primitive::kPrimInt);
95 loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto());
96 loop_header_[d]->AddPhi(basic_[d]);
97 HInstruction* compare = new (&allocator_) HLessThan(basic_[d], constant100_);
98 loop_header_[d]->AddInstruction(compare);
99 loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare));
100 increment_[d] = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[d], constant1_);
101 loop_body_[d]->AddInstruction(increment_[d]);
102 loop_body_[d]->AddInstruction(new (&allocator_) HGoto());
103
104 basic_[d]->AddInput(constant0_);
105 basic_[d]->AddInput(increment_[d]);
106 }
107 }
108
109 // Builds if-statement at depth d.
BuildIf(int d,HBasicBlock ** ifT,HBasicBlock ** ifF)110 HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) {
111 HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_);
112 HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_);
113 HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_);
114 graph_->AddBlock(cond);
115 graph_->AddBlock(ifTrue);
116 graph_->AddBlock(ifFalse);
117 // Conditional split.
118 loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond);
119 cond->AddSuccessor(ifTrue);
120 cond->AddSuccessor(ifFalse);
121 ifTrue->AddSuccessor(loop_body_[d]);
122 ifFalse->AddSuccessor(loop_body_[d]);
123 cond->AddInstruction(new (&allocator_) HIf(parameter_));
124 *ifT = ifTrue;
125 *ifF = ifFalse;
126
127 HPhi* select_phi = new (&allocator_) HPhi(&allocator_, -1, 0, Primitive::kPrimInt);
128 loop_body_[d]->AddPhi(select_phi);
129 return select_phi;
130 }
131
132 // Inserts instruction right before increment at depth d.
InsertInstruction(HInstruction * instruction,int d)133 HInstruction* InsertInstruction(HInstruction* instruction, int d) {
134 loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]);
135 return instruction;
136 }
137
138 // Inserts a phi to loop header at depth d and returns it.
InsertLoopPhi(int vreg,int d)139 HPhi* InsertLoopPhi(int vreg, int d) {
140 HPhi* phi = new (&allocator_) HPhi(&allocator_, vreg, 0, Primitive::kPrimInt);
141 loop_header_[d]->AddPhi(phi);
142 return phi;
143 }
144
145 // Inserts an array store with given `subscript` at depth d to
146 // enable tests to inspect the computed induction at that point easily.
InsertArrayStore(HInstruction * subscript,int d)147 HInstruction* InsertArrayStore(HInstruction* subscript, int d) {
148 // ArraySet is given a float value in order to avoid SsaBuilder typing
149 // it from the array's non-existent reference type info.
150 return InsertInstruction(new (&allocator_) HArraySet(
151 parameter_, subscript, float_constant0_, Primitive::kPrimFloat, 0), d);
152 }
153
154 // Returns induction information of instruction in loop at depth d.
GetInductionInfo(HInstruction * instruction,int d)155 std::string GetInductionInfo(HInstruction* instruction, int d) {
156 return HInductionVarAnalysis::InductionToString(
157 iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction));
158 }
159
160 // Returns true if instructions have identical induction.
HaveSameInduction(HInstruction * instruction1,HInstruction * instruction2)161 bool HaveSameInduction(HInstruction* instruction1, HInstruction* instruction2) {
162 return HInductionVarAnalysis::InductionEqual(
163 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction1),
164 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction2));
165 }
166
167 // Performs InductionVarAnalysis (after proper set up).
PerformInductionVarAnalysis()168 void PerformInductionVarAnalysis() {
169 graph_->BuildDominatorTree();
170 iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
171 iva_->Run();
172 }
173
174 // General building fields.
175 ArenaPool pool_;
176 ArenaAllocator allocator_;
177 HGraph* graph_;
178 HInductionVarAnalysis* iva_;
179
180 // Fixed basic blocks and instructions.
181 HBasicBlock* entry_;
182 HBasicBlock* return_;
183 HBasicBlock* exit_;
184 HInstruction* parameter_; // "this"
185 HInstruction* constant0_;
186 HInstruction* constant1_;
187 HInstruction* constant100_;
188 HInstruction* float_constant0_;
189
190 // Loop specifics.
191 HBasicBlock* loop_preheader_[10];
192 HBasicBlock* loop_header_[10];
193 HBasicBlock* loop_body_[10];
194 HInstruction* increment_[10];
195 HPhi* basic_[10]; // "vreg_d", the "i_d"
196 };
197
198 //
199 // The actual InductionVarAnalysis tests.
200 //
201
TEST_F(InductionVarAnalysisTest,ProperLoopSetup)202 TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
203 // Setup:
204 // for (int i_0 = 0; i_0 < 100; i_0++) {
205 // ..
206 // for (int i_9 = 0; i_9 < 100; i_9++) {
207 // }
208 // ..
209 // }
210 BuildLoopNest(10);
211 graph_->BuildDominatorTree();
212
213 ASSERT_EQ(entry_->GetLoopInformation(), nullptr);
214 for (int d = 0; d < 1; d++) {
215 ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
216 (d == 0) ? nullptr
217 : loop_header_[d - 1]->GetLoopInformation());
218 ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr);
219 ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr);
220 ASSERT_EQ(loop_header_[d]->GetLoopInformation(),
221 loop_body_[d]->GetLoopInformation());
222 }
223 ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
224 }
225
TEST_F(InductionVarAnalysisTest,FindBasicInduction)226 TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
227 // Setup:
228 // for (int i = 0; i < 100; i++) {
229 // a[i] = 0;
230 // }
231 BuildLoopNest(1);
232 HInstruction* store = InsertArrayStore(basic_[0], 0);
233 PerformInductionVarAnalysis();
234
235 EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
236 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str());
237
238 // Offset matters!
239 EXPECT_FALSE(HaveSameInduction(store->InputAt(1), increment_[0]));
240
241 // Trip-count.
242 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))",
243 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
244 }
245
TEST_F(InductionVarAnalysisTest,FindDerivedInduction)246 TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
247 // Setup:
248 // for (int i = 0; i < 100; i++) {
249 // k = 100 + i;
250 // k = 100 - i;
251 // k = 100 * i;
252 // k = i << 1;
253 // k = - i;
254 // }
255 BuildLoopNest(1);
256 HInstruction *add = InsertInstruction(
257 new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, basic_[0]), 0);
258 HInstruction *sub = InsertInstruction(
259 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0);
260 HInstruction *mul = InsertInstruction(
261 new (&allocator_) HMul(Primitive::kPrimInt, constant100_, basic_[0]), 0);
262 HInstruction *shl = InsertInstruction(
263 new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0);
264 HInstruction *neg = InsertInstruction(
265 new (&allocator_) HNeg(Primitive::kPrimInt, basic_[0]), 0);
266 PerformInductionVarAnalysis();
267
268 EXPECT_STREQ("((1) * i + (100)):PrimInt", GetInductionInfo(add, 0).c_str());
269 EXPECT_STREQ("(( - (1)) * i + (100)):PrimInt", GetInductionInfo(sub, 0).c_str());
270 EXPECT_STREQ("((100) * i + (0)):PrimInt", GetInductionInfo(mul, 0).c_str());
271 EXPECT_STREQ("((2) * i + (0)):PrimInt", GetInductionInfo(shl, 0).c_str());
272 EXPECT_STREQ("(( - (1)) * i + (0)):PrimInt", GetInductionInfo(neg, 0).c_str());
273 }
274
TEST_F(InductionVarAnalysisTest,FindChainInduction)275 TEST_F(InductionVarAnalysisTest, FindChainInduction) {
276 // Setup:
277 // k = 0;
278 // for (int i = 0; i < 100; i++) {
279 // k = k + 100;
280 // a[k] = 0;
281 // k = k - 1;
282 // a[k] = 0;
283 // }
284 BuildLoopNest(1);
285 HPhi* k = InsertLoopPhi(0, 0);
286 k->AddInput(constant0_);
287
288 HInstruction *add = InsertInstruction(
289 new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
290 HInstruction* store1 = InsertArrayStore(add, 0);
291 HInstruction *sub = InsertInstruction(
292 new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0);
293 HInstruction* store2 = InsertArrayStore(sub, 0);
294 k->AddInput(sub);
295 PerformInductionVarAnalysis();
296
297 EXPECT_STREQ("(((100) - (1)) * i + (100)):PrimInt",
298 GetInductionInfo(store1->InputAt(1), 0).c_str());
299 EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):PrimInt",
300 GetInductionInfo(store2->InputAt(1), 0).c_str());
301 }
302
TEST_F(InductionVarAnalysisTest,FindTwoWayBasicInduction)303 TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) {
304 // Setup:
305 // k = 0;
306 // for (int i = 0; i < 100; i++) {
307 // if () k = k + 1;
308 // else k = k + 1;
309 // a[k] = 0;
310 // }
311 BuildLoopNest(1);
312 HPhi* k_header = InsertLoopPhi(0, 0);
313 k_header->AddInput(constant0_);
314
315 HBasicBlock* ifTrue;
316 HBasicBlock* ifFalse;
317 HPhi* k_body = BuildIf(0, &ifTrue, &ifFalse);
318
319 // True-branch.
320 HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_);
321 ifTrue->AddInstruction(inc1);
322 k_body->AddInput(inc1);
323 // False-branch.
324 HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_);
325 ifFalse->AddInstruction(inc2);
326 k_body->AddInput(inc2);
327 // Merge over a phi.
328 HInstruction* store = InsertArrayStore(k_body, 0);
329 k_header->AddInput(k_body);
330 PerformInductionVarAnalysis();
331
332 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
333
334 // Both increments get same induction.
335 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1));
336 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2));
337 }
338
TEST_F(InductionVarAnalysisTest,FindTwoWayDerivedInduction)339 TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
340 // Setup:
341 // for (int i = 0; i < 100; i++) {
342 // if () k = i + 1;
343 // else k = i + 1;
344 // a[k] = 0;
345 // }
346 BuildLoopNest(1);
347 HBasicBlock* ifTrue;
348 HBasicBlock* ifFalse;
349 HPhi* k = BuildIf(0, &ifTrue, &ifFalse);
350
351 // True-branch.
352 HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_);
353 ifTrue->AddInstruction(inc1);
354 k->AddInput(inc1);
355 // False-branch.
356 HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_);
357 ifFalse->AddInstruction(inc2);
358 k->AddInput(inc2);
359 // Merge over a phi.
360 HInstruction* store = InsertArrayStore(k, 0);
361 PerformInductionVarAnalysis();
362
363 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
364 }
365
TEST_F(InductionVarAnalysisTest,FindFirstOrderWrapAroundInduction)366 TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
367 // Setup:
368 // k = 0;
369 // for (int i = 0; i < 100; i++) {
370 // a[k] = 0;
371 // k = 100 - i;
372 // }
373 BuildLoopNest(1);
374 HPhi* k = InsertLoopPhi(0, 0);
375 k->AddInput(constant0_);
376
377 HInstruction* store = InsertArrayStore(k, 0);
378 HInstruction *sub = InsertInstruction(
379 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0);
380 k->AddInput(sub);
381 PerformInductionVarAnalysis();
382
383 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):PrimInt):PrimInt",
384 GetInductionInfo(store->InputAt(1), 0).c_str());
385 }
386
TEST_F(InductionVarAnalysisTest,FindSecondOrderWrapAroundInduction)387 TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
388 // Setup:
389 // k = 0;
390 // t = 100;
391 // for (int i = 0; i < 100; i++) {
392 // a[k] = 0;
393 // k = t;
394 // t = 100 - i;
395 // }
396 BuildLoopNest(1);
397 HPhi* k = InsertLoopPhi(0, 0);
398 k->AddInput(constant0_);
399 HPhi* t = InsertLoopPhi(1, 0);
400 t->AddInput(constant100_);
401
402 HInstruction* store = InsertArrayStore(k, 0);
403 k->AddInput(t);
404 HInstruction *sub = InsertInstruction(
405 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0);
406 t->AddInput(sub);
407 PerformInductionVarAnalysis();
408
409 EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100)):PrimInt):PrimInt):PrimInt",
410 GetInductionInfo(store->InputAt(1), 0).c_str());
411 }
412
TEST_F(InductionVarAnalysisTest,FindWrapAroundDerivedInduction)413 TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
414 // Setup:
415 // k = 0;
416 // for (int i = 0; i < 100; i++) {
417 // t = k + 100;
418 // t = k - 100;
419 // t = k * 100;
420 // t = k << 1;
421 // t = - k;
422 // k = i << 1;
423 // }
424 BuildLoopNest(1);
425 HPhi* k = InsertLoopPhi(0, 0);
426 k->AddInput(constant0_);
427
428 HInstruction *add = InsertInstruction(
429 new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
430 HInstruction *sub = InsertInstruction(
431 new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0);
432 HInstruction *mul = InsertInstruction(
433 new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0);
434 HInstruction *shl = InsertInstruction(
435 new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0);
436 HInstruction *neg = InsertInstruction(
437 new (&allocator_) HNeg(Primitive::kPrimInt, k), 0);
438 k->AddInput(
439 InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0));
440 PerformInductionVarAnalysis();
441
442 EXPECT_STREQ("wrap((100), ((2) * i + (100)):PrimInt):PrimInt",
443 GetInductionInfo(add, 0).c_str());
444 EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))):PrimInt):PrimInt",
445 GetInductionInfo(sub, 0).c_str());
446 EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):PrimInt):PrimInt",
447 GetInductionInfo(mul, 0).c_str());
448 EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):PrimInt):PrimInt",
449 GetInductionInfo(shl, 0).c_str());
450 EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):PrimInt):PrimInt",
451 GetInductionInfo(neg, 0).c_str());
452 }
453
TEST_F(InductionVarAnalysisTest,FindPeriodicInduction)454 TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
455 // Setup:
456 // k = 0;
457 // t = 100;
458 // for (int i = 0; i < 100; i++) {
459 // a[k] = 0;
460 // a[t] = 0;
461 // // Swap t <-> k.
462 // d = t;
463 // t = k;
464 // k = d;
465 // }
466 BuildLoopNest(1);
467 HPhi* k = InsertLoopPhi(0, 0);
468 k->AddInput(constant0_);
469 HPhi* t = InsertLoopPhi(1, 0);
470 t->AddInput(constant100_);
471
472 HInstruction* store1 = InsertArrayStore(k, 0);
473 HInstruction* store2 = InsertArrayStore(t, 0);
474 k->AddInput(t);
475 t->AddInput(k);
476 PerformInductionVarAnalysis();
477
478 EXPECT_STREQ("periodic((0), (100)):PrimInt", GetInductionInfo(store1->InputAt(1), 0).c_str());
479 EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str());
480 }
481
TEST_F(InductionVarAnalysisTest,FindIdiomaticPeriodicInduction)482 TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) {
483 // Setup:
484 // k = 0;
485 // for (int i = 0; i < 100; i++) {
486 // a[k] = 0;
487 // k = 1 - k;
488 // }
489 BuildLoopNest(1);
490 HPhi* k = InsertLoopPhi(0, 0);
491 k->AddInput(constant0_);
492
493 HInstruction* store = InsertArrayStore(k, 0);
494 HInstruction *sub = InsertInstruction(
495 new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0);
496 k->AddInput(sub);
497 PerformInductionVarAnalysis();
498
499 EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
500 EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(sub, 0).c_str());
501 }
502
TEST_F(InductionVarAnalysisTest,FindDerivedPeriodicInduction)503 TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
504 // Setup:
505 // k = 0;
506 // for (int i = 0; i < 100; i++) {
507 // k = 1 - k;
508 // t = k + 100;
509 // t = k - 100;
510 // t = k * 100;
511 // t = k << 1;
512 // t = - k;
513 // }
514 BuildLoopNest(1);
515 HPhi* k_header = InsertLoopPhi(0, 0);
516 k_header->AddInput(constant0_);
517
518 HInstruction* k_body = InsertInstruction(
519 new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k_header), 0);
520 k_header->AddInput(k_body);
521
522 // Derived expressions.
523 HInstruction *add = InsertInstruction(
524 new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0);
525 HInstruction *sub = InsertInstruction(
526 new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0);
527 HInstruction *mul = InsertInstruction(
528 new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0);
529 HInstruction *shl = InsertInstruction(
530 new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0);
531 HInstruction *neg = InsertInstruction(
532 new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0);
533 PerformInductionVarAnalysis();
534
535 EXPECT_STREQ("periodic(((1) + (100)), (100)):PrimInt", GetInductionInfo(add, 0).c_str());
536 EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):PrimInt", GetInductionInfo(sub, 0).c_str());
537 EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(mul, 0).c_str());
538 EXPECT_STREQ("periodic((2), (0)):PrimInt", GetInductionInfo(shl, 0).c_str());
539 EXPECT_STREQ("periodic(( - (1)), (0)):PrimInt", GetInductionInfo(neg, 0).c_str());
540 }
541
TEST_F(InductionVarAnalysisTest,FindDeepLoopInduction)542 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
543 // Setup:
544 // k = 0;
545 // for (int i_0 = 0; i_0 < 100; i_0++) {
546 // ..
547 // for (int i_9 = 0; i_9 < 100; i_9++) {
548 // k = 1 + k;
549 // a[k] = 0;
550 // }
551 // ..
552 // }
553 BuildLoopNest(10);
554
555 HPhi* k[10];
556 for (int d = 0; d < 10; d++) {
557 k[d] = InsertLoopPhi(0, d);
558 }
559
560 HInstruction *inc = InsertInstruction(
561 new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9);
562 HInstruction* store = InsertArrayStore(inc, 9);
563
564 for (int d = 0; d < 10; d++) {
565 k[d]->AddInput((d != 0) ? k[d - 1] : constant0_);
566 k[d]->AddInput((d != 9) ? k[d + 1] : inc);
567 }
568 PerformInductionVarAnalysis();
569
570 // Avoid exact phi number, since that depends on the SSA building phase.
571 std::regex r("\\(\\(1\\) \\* i \\+ "
572 "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\):PrimInt");
573
574 for (int d = 0; d < 10; d++) {
575 if (d == 9) {
576 EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r));
577 } else {
578 EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
579 }
580 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[d], d).c_str());
581 // Trip-count.
582 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))",
583 GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str());
584 }
585 }
586
TEST_F(InductionVarAnalysisTest,ByteInductionIntLoopControl)587 TEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) {
588 // Setup:
589 // for (int i = 0; i < 100; i++) {
590 // k = (byte) i;
591 // a[k] = 0;
592 // a[i] = 0;
593 // }
594 BuildLoopNest(1);
595 HInstruction *conv = InsertInstruction(
596 new (&allocator_) HTypeConversion(Primitive::kPrimByte, basic_[0], -1), 0);
597 HInstruction* store1 = InsertArrayStore(conv, 0);
598 HInstruction* store2 = InsertArrayStore(basic_[0], 0);
599 PerformInductionVarAnalysis();
600
601 // Regular int induction (i) is "transferred" over conversion into byte induction (k).
602 EXPECT_STREQ("((1) * i + (0)):PrimByte", GetInductionInfo(store1->InputAt(1), 0).c_str());
603 EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str());
604 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str());
605
606 // Type matters!
607 EXPECT_FALSE(HaveSameInduction(store1->InputAt(1), store2->InputAt(1)));
608
609 // Trip-count.
610 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))",
611 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
612 }
613
TEST_F(InductionVarAnalysisTest,ByteLoopControl1)614 TEST_F(InductionVarAnalysisTest, ByteLoopControl1) {
615 // Setup:
616 // for (byte i = -128; i < 127; i++) { // just fits!
617 // }
618 BuildLoopNest(1);
619 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0);
620 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
621 ifs->ReplaceInput(graph_->GetIntConstant(127), 1);
622 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1);
623 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
624 basic_[0]->ReplaceInput(conv, 1);
625 PerformInductionVarAnalysis();
626
627 EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str());
628 // Trip-count.
629 EXPECT_STREQ("(((127) - (-128)) (TC-loop) ((-128) < (127)))",
630 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
631 }
632
TEST_F(InductionVarAnalysisTest,ByteLoopControl2)633 TEST_F(InductionVarAnalysisTest, ByteLoopControl2) {
634 // Setup:
635 // for (byte i = -128; i < 128; i++) { // infinite loop!
636 // }
637 BuildLoopNest(1);
638 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0);
639 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
640 ifs->ReplaceInput(graph_->GetIntConstant(128), 1);
641 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1);
642 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
643 basic_[0]->ReplaceInput(conv, 1);
644 PerformInductionVarAnalysis();
645
646 EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str());
647 // Trip-count undefined.
648 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
649 }
650
TEST_F(InductionVarAnalysisTest,ShortLoopControl1)651 TEST_F(InductionVarAnalysisTest, ShortLoopControl1) {
652 // Setup:
653 // for (short i = -32768; i < 32767; i++) { // just fits!
654 // }
655 BuildLoopNest(1);
656 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0);
657 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
658 ifs->ReplaceInput(graph_->GetIntConstant(32767), 1);
659 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1);
660 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
661 basic_[0]->ReplaceInput(conv, 1);
662 PerformInductionVarAnalysis();
663
664 EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort",
665 GetInductionInfo(increment_[0], 0).c_str());
666 // Trip-count.
667 EXPECT_STREQ("(((32767) - (-32768)) (TC-loop) ((-32768) < (32767)))",
668 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
669 }
670
TEST_F(InductionVarAnalysisTest,ShortLoopControl2)671 TEST_F(InductionVarAnalysisTest, ShortLoopControl2) {
672 // Setup:
673 // for (short i = -32768; i < 32768; i++) { // infinite loop!
674 // }
675 BuildLoopNest(1);
676 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0);
677 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
678 ifs->ReplaceInput(graph_->GetIntConstant(32768), 1);
679 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1);
680 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
681 basic_[0]->ReplaceInput(conv, 1);
682 PerformInductionVarAnalysis();
683
684 EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort",
685 GetInductionInfo(increment_[0], 0).c_str());
686 // Trip-count undefined.
687 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
688 }
689
TEST_F(InductionVarAnalysisTest,CharLoopControl1)690 TEST_F(InductionVarAnalysisTest, CharLoopControl1) {
691 // Setup:
692 // for (char i = 0; i < 65535; i++) { // just fits!
693 // }
694 BuildLoopNest(1);
695 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
696 ifs->ReplaceInput(graph_->GetIntConstant(65535), 1);
697 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1);
698 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
699 basic_[0]->ReplaceInput(conv, 1);
700 PerformInductionVarAnalysis();
701
702 EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str());
703 // Trip-count.
704 EXPECT_STREQ("((65535) (TC-loop) ((0) < (65535)))",
705 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
706 }
707
TEST_F(InductionVarAnalysisTest,CharLoopControl2)708 TEST_F(InductionVarAnalysisTest, CharLoopControl2) {
709 // Setup:
710 // for (char i = 0; i < 65536; i++) { // infinite loop!
711 // }
712 BuildLoopNest(1);
713 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious();
714 ifs->ReplaceInput(graph_->GetIntConstant(65536), 1);
715 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1);
716 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext());
717 basic_[0]->ReplaceInput(conv, 1);
718 PerformInductionVarAnalysis();
719
720 EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str());
721 // Trip-count undefined.
722 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
723 }
724
725 } // namespace art
726