Added polynomial induction variables analysis. With tests.

Rationale:
Information on polynomial sequences is nice to further enhance
BCE and last-value assignment. In this case, this CL enables more
loop optimizations for benchpress' Sum (80 x speedup). Also
changed rem-based geometric induction to wrap-around induction.

Test: test-art-host

Change-Id: Ie4d2659edefb814edda2c971c1f70ba400c31111

1 files changed, 10 insertions, 14 deletions

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 94afc71c3d..4720f2d61c 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -65,6 +65,7 @@ class HInductionVarAnalysis : public HOptimization {
     kNeg,
     kMul,
     kDiv,
+    kRem,
     kXor,
     kFetch,
     // Trip-counts.
@@ -85,10 +86,10 @@ class HInductionVarAnalysis : public HOptimization {
    *         op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch
    *   (2) linear:
    *         nop: a * i + b
-   *   (3) polynomial:                        // TODO: coming soon
-   *         nop: sum_i(a) + b, for linear a
+   *   (3) polynomial:
+   *         nop: sum_lt(a) + b, for linear a
    *   (4) geometric:
-   *         op: a * fetch^i + b, a * fetch^-i + b, a mod_i fetch + b
+   *         op: a * fetch^i + b, a * fetch^-i + b
    *   (5) wrap-around
    *         nop: a, then defined by b
    *   (6) periodic
@@ -177,17 +178,12 @@ class HInductionVarAnalysis : public HOptimization {
                              HInstruction* y,
                              InductionOp op,
                              bool is_first_call);  // possibly swaps x and y to try again
-  InductionInfo* SolveGeo(HLoopInformation* loop,
-                          HInstruction* entry_phi,
-                          HInstruction* instruction,
-                          HInstruction* x,
-                          HInstruction* y,
-                          InductionOp op);
-  InductionInfo* SolveXor(HLoopInformation* loop,
-                          HInstruction* entry_phi,
-                          HInstruction* instruction,
-                          HInstruction* x,
-                          HInstruction* y);
+  InductionInfo* SolveOp(HLoopInformation* loop,
+                         HInstruction* entry_phi,
+                         HInstruction* instruction,
+                         HInstruction* x,
+                         HInstruction* y,
+                         InductionOp op);
   InductionInfo* SolveTest(HLoopInformation* loop,
                            HInstruction* entry_phi,
                            HInstruction* instruction,