Improvements in induction range analysis.
Rationale:
Uses range analysis while determining whether trip-counts
are "safe", which improves analysis of triangular loops.
Also implements more effective triangular loop analysis
by evaluating induction information only once and using
a top level hint (instead of the "iterative refinement"
that was used earlier). Also fixes analysis of triangular
trip counts that may wrap-around. All with tests.
Test: see induction_var_range_test/530-checker-loops*
BUG=27151190
Change-Id: I1877c8ce0c9a52005900eb9dfdbb1918df100278
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 0af4156..00aaa16 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -57,21 +57,19 @@
explicit InductionVarRange(HInductionVarAnalysis* induction);
/**
- * Given a context denoted by the first instruction, returns a possibly conservative
- * lower and upper bound on the instruction's value in the output parameters min_val
- * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test
- * is needed to protect the range evaluation inside its loop. Returns false on failure.
+ * Given a context denoted by the first instruction, returns a possibly conservative lower
+ * and upper bound on the instruction's value in the output parameters min_val and max_val,
+ * respectively. The need_finite_test flag denotes if an additional finite-test is needed
+ * to protect the range evaluation inside its loop. The parameter chase_hint defines an
+ * instruction at which chasing may stop. Returns false on failure.
*/
bool GetInductionRange(HInstruction* context,
HInstruction* instruction,
+ HInstruction* chase_hint,
/*out*/ Value* min_val,
/*out*/ Value* max_val,
/*out*/ bool* needs_finite_test);
- /** Refines the values with induction of next outer loop. Returns true on change. */
- bool RefineOuter(/*in-out*/ Value* min_val,
- /*in-out*/ Value* max_val) const;
-
/**
* Returns true if range analysis is able to generate code for the lower and upper
* bound expressions on the instruction in the given context. The need_finite_test
@@ -132,11 +130,20 @@
*/
bool IsConstant(HInductionVarAnalysis::InductionInfo* info,
ConstantRequest request,
- /*out*/ int64_t *value) const;
+ /*out*/ int64_t* value) const;
+ /** Returns whether induction information can be obtained. */
+ bool HasInductionInfo(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/ HLoopInformation** loop,
+ /*out*/ HInductionVarAnalysis::InductionInfo** info,
+ /*out*/ HInductionVarAnalysis::InductionInfo** trip) const;
+
+ bool HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const;
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
+ bool IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
Value GetLinear(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
@@ -161,8 +168,16 @@
bool in_body,
bool is_min) const;
- Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
- Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
+ Value MulRangeAndConstant(int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value DivRangeAndConstant(int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
Value AddValue(Value v1, Value v2) const;
Value SubValue(Value v1, Value v2) const;
@@ -171,12 +186,6 @@
Value MergeVal(Value v1, Value v2, bool is_min) const;
/**
- * Returns refined value using induction of next outer loop or the input value if no
- * further refinement is possible.
- */
- Value RefineOuter(Value val, bool is_min) const;
-
- /**
* Generates code for lower/upper/taken-test in the HIR. Returns true on success.
* With values nullptr, the method can be used to determine if code generation
* would be successful without generating actual code yet.
@@ -200,7 +209,10 @@
bool is_min) const;
/** Results of prior induction variable analysis. */
- HInductionVarAnalysis *induction_analysis_;
+ HInductionVarAnalysis* induction_analysis_;
+
+ /** Instruction at which chasing may stop. */
+ HInstruction* chase_hint_;
friend class HInductionVarAnalysis;
friend class InductionVarRangeTest;