commit f475bee067ae0f6dd2a022c823c642265f97b065
author Aart Bik <ajcbik@google.com> Wed Sep 16 12:50:25 2015 -0700
committer Aart Bik <ajcbik@google.com> Wed Sep 23 16:20:53 2015 -0700
tree a411acce47e6b60ef87bc2f873604aad1d31c318
parent 15ed726eae70a479f3179de68a643ef30c777cbb

Various improvements in finding induction variables.

Rationale:
(1) Analyze multi-way phis (requested by Nicolas, Igor, and Mingyao).
(2) Analyze trip count for restricted != loops
(3) Added unit test for public API of range analysis (static methods
    were already well-tested).

Change-Id: I9285d22d3bb927f141204cc4697ea6fe5120994d

compiler/optimizing/induction_var_analysis_test.cc

diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index fca1ca5..e519e77 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -20,6 +20,7 @@
 #include "builder.h"
 #include "gtest/gtest.h"
 #include "induction_var_analysis.h"
+#include "induction_var_range.h"
 #include "nodes.h"
 #include "optimizing_unit_test.h"
 
@@ -388,7 +389,7 @@
   HInstruction* store = InsertArrayStore(induc_, 0);
   InsertLocalStore(induc_, InsertLocalLoad(tmp_, 0), 0);
   HInstruction *sub = InsertInstruction(
-       new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(tmp_, sub, 0);
   PerformInductionVarAnalysis();
 
@@ -412,16 +413,16 @@
       new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, add, 0);
   HInstruction *sub = InsertInstruction(
-       new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, sub, 0);
   HInstruction *mul = InsertInstruction(
-       new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, mul, 0);
   HInstruction *shl = InsertInstruction(
-       new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+      new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
   InsertLocalStore(tmp_, shl, 0);
   HInstruction *neg = InsertInstruction(
-       new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+      new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
   InsertLocalStore(tmp_, neg, 0);
   InsertLocalStore(
       induc_,
@@ -471,7 +472,7 @@
   BuildLoopNest(1);
   HInstruction* store = InsertArrayStore(induc_, 0);
   HInstruction *sub = InsertInstruction(
-         new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
   InsertLocalStore(induc_, sub, 0);
   PerformInductionVarAnalysis();
 
@@ -497,19 +498,19 @@
                         HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0), 0);
   // Derived expressions.
   HInstruction *add = InsertInstruction(
-       new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, add, 0);
   HInstruction *sub = InsertInstruction(
-       new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, sub, 0);
   HInstruction *mul = InsertInstruction(
-       new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(tmp_, mul, 0);
   HInstruction *shl = InsertInstruction(
-       new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+      new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
   InsertLocalStore(tmp_, shl, 0);
   HInstruction *neg = InsertInstruction(
-       new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+      new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
   InsertLocalStore(tmp_, neg, 0);
   PerformInductionVarAnalysis();
 
@@ -520,6 +521,34 @@
   EXPECT_STREQ("periodic(( - (1)), (0))", GetInductionInfo(neg, 0).c_str());
 }
 
+TEST_F(InductionVarAnalysisTest, FindRange) {
+  // Setup:
+  // for (int i = 0; i < 100; i++) {
+  //   k = i << 1;
+  //   k = k + 1;
+  //   a[k] = 0;
+  // }
+  BuildLoopNest(1);
+  HInstruction *shl = InsertInstruction(
+      new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
+  InsertLocalStore(induc_, shl, 0);
+  HInstruction *add = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+  InsertLocalStore(induc_, add, 0);
+  HInstruction* store = InsertArrayStore(induc_, 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("((2) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
+
+  InductionVarRange range(iva_);
+  InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1));
+  InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1));
+  EXPECT_EQ(0, v_min.a_constant);
+  EXPECT_EQ(1, v_min.b_constant);
+  EXPECT_EQ(0, v_max.a_constant);
+  EXPECT_EQ(199, v_max.b_constant);
+}
+
 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
   // Setup:
   // k = 0;