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
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 180d1f7..8eccf92 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -126,7 +126,7 @@
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 @@
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 @@
ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
friend class InductionVarAnalysisTest;
+ friend class InductionVarRange;
+ friend class InductionVarRangeTest;
DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
};