A first implementation of a loop optimization framework.
Rationale:
We are planning to add more and more loop related optimizations
and this framework provides the basis to do so. For starters,
the framework optimizes dead induction, induction that can be
replaced with a simpler closed-form, and eliminates dead loops
completely (either pre-existing or as a result of induction
removal).
Speedup on e.g. Benchpress Loop is 73x (17.5us. -> 0.24us.)
[with the potential for more exploiting outer loop too]
Test: 618-checker-induction et al.
Change-Id: If80a809acf943539bf6726b0030dcabd50c9babc
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 397abde..b0e61e6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -366,8 +366,8 @@
// is a throw-catch loop, i.e. the header is a catch block.
GraphAnalysisResult AnalyzeLoops() const;
- // Computes the linear order (should be called before using HLinearOrderIterator).
- // Linearizes the graph such that:
+ // Computes a linear order for the current graph (should be called before
+ // using HLinearOrderIterator). Linearizes the graph such that:
// (1): a block is always after its dominator,
// (2): blocks of loops are contiguous.
// This creates a natural and efficient ordering when visualizing live ranges.
@@ -586,7 +586,8 @@
// List of blocks to perform a reverse post order tree traversal.
ArenaVector<HBasicBlock*> reverse_post_order_;
- // List of blocks to perform a linear order tree traversal.
+ // List of blocks to perform a linear order tree traversal. Unlike the reverse
+ // post order, this order is not incrementally kept up-to-date.
ArenaVector<HBasicBlock*> linear_order_;
HBasicBlock* entry_block_;