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
25namespace art {
26
27/**
28 * Fixture class for the InductionVarAnalysis tests.
29 */
30class InductionVarAnalysisTest : public CommonCompilerTest {
31 public:
32  InductionVarAnalysisTest() : pool_(), allocator_(&pool_) {
33    graph_ = CreateGraph(&allocator_);
34  }
35
36  ~InductionVarAnalysisTest() { }
37
38  // Builds single for-loop at depth d.
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.
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.
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.
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.
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.
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.
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.
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).
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
202TEST_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
226TEST_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
246TEST_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
275TEST_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
303TEST_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
339TEST_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
366TEST_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
387TEST_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
413TEST_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
454TEST_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
482TEST_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
503TEST_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
542TEST_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
587TEST_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
614TEST_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
633TEST_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
651TEST_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
671TEST_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
690TEST_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
708TEST_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