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

1 files changed, 30 insertions, 18 deletions

diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 0af41560ff..00aaa167f8 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -57,21 +57,19 @@ class InductionVarRange {
   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 @@ class InductionVarRange {
    */
   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 @@ class InductionVarRange {
                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 @@ class InductionVarRange {
   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 @@ class InductionVarRange {
                     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;