Improved and simplified loop optimizations.

Rationale:
This CL merges some common cases into one, thereby simplifying
the code quite a bit. It also prepares for more general induction
cycles (rather than the simple phi-add currently used). Finally,
it generalizes the closed form elimination with empty loops.
As a result of the latter, elaborate but weird code like:

  private static int waterFall() {
    int i = 0;
    for (; i < 10; i++);
    for (; i < 20; i++);
    for (; i < 30; i++);
    for (; i < 40; i++);
    for (; i < 50; i++);
    return i;
  }

now becomes just this (on x86)!

    mov eax, 50
    ret

Change-Id: I8d22ce63ce9696918f57bb90f64d9a9303a4791d
Test: m test-art-host

1 files changed, 11 insertions, 3 deletions

diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index 6092955221..b2bf1c8507 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -63,9 +63,13 @@ class HLoopOptimization : public HOptimization {
   void SimplifyInduction(LoopNode* node);
   void RemoveIfEmptyLoop(LoopNode* node);
 
-  void ReplaceAllUses(HInstruction* instruction,
-                      HInstruction* replacement,
-                      HInstruction* exclusion);
+  bool IsOnlyUsedAfterLoop(const HLoopInformation& loop_info,
+                           HInstruction* instruction,
+                           /*out*/ int32_t* use_count);
+  void ReplaceAllUses(HInstruction* instruction, HInstruction* replacement);
+  bool TryReplaceWithLastValue(HInstruction* instruction,
+                               int32_t use_count,
+                               HBasicBlock* block);
 
   // Range information based on prior induction variable analysis.
   InductionVarRange induction_range_;
@@ -79,6 +83,10 @@ class HLoopOptimization : public HOptimization {
   LoopNode* top_loop_;
   LoopNode* last_loop_;
 
+  // Temporary bookkeeping of a set of instructions.
+  // Contents reside in phase-local heap memory.
+  ArenaSet<HInstruction*>* iset_;
+
   friend class LoopOptimizationTest;
 
   DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);