Induction variable range analysis.

Rationale: by computing an upper bound on the trip count of each
           loop after induction var analysis has completed, a
	   simple range analysis yields lower and upper bounds on
	   all induced expressions in a loop; this analysis
	   plugs directly into BCE (follow-up CL).

Change-Id: I46a3fe48721ca372547199b39a3498c47992597d

1 files changed, 19 insertions, 1 deletions

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 180d1f7148..8eccf925c1 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -126,7 +126,7 @@ class HInductionVarAnalysis : public HOptimization {
   InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
-  InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type t);
+  InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
   InductionInfo* TransferNeg(InductionInfo* a);
 
   // Solvers.
@@ -142,9 +142,25 @@ class HInductionVarAnalysis : public HOptimization {
                              bool is_first_call);
   InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
 
+  // Trip count information.
+  void VisitControl(HLoopInformation* loop);
+  void VisitCondition(HLoopInformation* loop,
+                      InductionInfo* a,
+                      InductionInfo* b,
+                      Primitive::Type type,
+                      IfCondition cmp);
+  void VisitTripCount(HLoopInformation* loop,
+                      InductionInfo* lo_val,
+                      InductionInfo* hi_val,
+                      InductionInfo* stride,
+                      int32_t stride_value,
+                      Primitive::Type type,
+                      bool is_strict);
+
   // Assign and lookup.
   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+  InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
 
   // Helpers.
@@ -168,6 +184,8 @@ class HInductionVarAnalysis : public HOptimization {
   ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
 
   friend class InductionVarAnalysisTest;
+  friend class InductionVarRange;
+  friend class InductionVarRangeTest;
 
   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
 };