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
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 94afc71..4720f2d 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -65,6 +65,7 @@
kNeg,
kMul,
kDiv,
+ kRem,
kXor,
kFetch,
// Trip-counts.
@@ -85,10 +86,10 @@
* 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 @@
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,