Compile-time tuning
Specialized the dataflow iterators and did a few other minor tweaks.
Showing ~5% compile-time improvement in a single-threaded environment;
less in multi-threaded (presumably because we're blocked by something
else).
Change-Id: I2e2ed58d881414b9fc97e04cd0623e188259afd2
diff --git a/compiler/dex/dataflow_iterator.h b/compiler/dex/dataflow_iterator.h
index da44ffd..1dab54e 100644
--- a/compiler/dex/dataflow_iterator.h
+++ b/compiler/dex/dataflow_iterator.h
@@ -27,124 +27,130 @@
* interesting orders. Note that for efficiency, the visit orders have been pre-computed.
* The order itself will not change during the iteration. However, for some uses,
* auxiliary data associated with the basic blocks may be changed during the iteration,
- * necessitating another pass over the list.
- *
- * To support this usage, we have is_iterative_. If false, the iteration is a one-shot
- * pass through the pre-computed list using Next(). If true, the caller must tell the
- * iterator whether a change has been made that necessitates another pass. Use
- * Next(had_change) for this. The general idea is that the iterative_ use case means
- * that the iterator will keep repeating the full basic block list until a complete pass
- * is made through it with no changes. Note that calling Next(true) does not affect
- * the iteration order or short-curcuit the current pass - it simply tells the iterator
- * that once it has finished walking through the block list it should reset and do another
- * full pass through the list.
+ * necessitating another pass over the list. If this behavior is required, use the
+ * "Repeating" variant. For the repeating variant, the caller must tell the iterator
+ * whether a change has been made that necessitates another pass. Note that calling Next(true)
+ * does not affect the iteration order or short-circuit the current pass - it simply tells
+ * the iterator that once it has finished walking through the block list it should reset and
+ * do another full pass through the list.
*/
class DataflowIterator {
public:
virtual ~DataflowIterator() {}
- // Return the next BasicBlock* to visit.
- BasicBlock* Next() {
- DCHECK(!is_iterative_);
- return NextBody(false);
- }
-
- /*
- * Return the next BasicBlock* to visit, and tell the iterator whether any change
- * has occurred that requires another full pass over the block list.
- */
- BasicBlock* Next(bool had_change) {
- DCHECK(is_iterative_);
- return NextBody(had_change);
- }
-
protected:
- DataflowIterator(MIRGraph* mir_graph, bool is_iterative, int start_idx, int end_idx,
- bool reverse)
+ DataflowIterator(MIRGraph* mir_graph, int start_idx, int end_idx)
: mir_graph_(mir_graph),
- is_iterative_(is_iterative),
start_idx_(start_idx),
end_idx_(end_idx),
- reverse_(reverse),
block_id_list_(NULL),
idx_(0),
changed_(false) {}
- virtual BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
+ virtual BasicBlock* ForwardSingleNext() ALWAYS_INLINE;
+ virtual BasicBlock* ReverseSingleNext() ALWAYS_INLINE;
+ virtual BasicBlock* ForwardRepeatNext(bool had_change) ALWAYS_INLINE;
+ virtual BasicBlock* ReverseRepeatNext(bool had_change) ALWAYS_INLINE;
MIRGraph* const mir_graph_;
- const bool is_iterative_;
const int start_idx_;
const int end_idx_;
- const bool reverse_;
GrowableArray<int>* block_id_list_;
int idx_;
bool changed_;
}; // DataflowIterator
- class ReachableNodesIterator : public DataflowIterator {
- public:
- ReachableNodesIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative, 0,
- mir_graph->GetNumReachableBlocks(), false) {
- idx_ = start_idx_;
- block_id_list_ = mir_graph->GetDfsOrder();
- }
- };
-
class PreOrderDfsIterator : public DataflowIterator {
public:
- PreOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative, 0,
- mir_graph->GetNumReachableBlocks(), false) {
+ explicit PreOrderDfsIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsOrder();
}
+
+ BasicBlock* Next() {
+ return ForwardSingleNext();
+ }
};
- class PostOrderDfsIterator : public DataflowIterator {
+ class RepeatingPreOrderDfsIterator : public DataflowIterator {
public:
- PostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative, 0,
- mir_graph->GetNumReachableBlocks(), false) {
+ explicit RepeatingPreOrderDfsIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
+ idx_ = start_idx_;
+ block_id_list_ = mir_graph->GetDfsOrder();
+ }
+
+ BasicBlock* Next(bool had_change) {
+ return ForwardRepeatNext(had_change);
+ }
+ };
+
+ class RepeatingPostOrderDfsIterator : public DataflowIterator {
+ public:
+ explicit RepeatingPostOrderDfsIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsPostOrder();
}
+
+ BasicBlock* Next(bool had_change) {
+ return ForwardRepeatNext(had_change);
+ }
};
class ReversePostOrderDfsIterator : public DataflowIterator {
public:
- ReversePostOrderDfsIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative,
- mir_graph->GetNumReachableBlocks() -1, 0, true) {
+ explicit ReversePostOrderDfsIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) {
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDfsPostOrder();
}
+
+ BasicBlock* Next() {
+ return ReverseSingleNext();
+ }
+ };
+
+ class RepeatingReversePostOrderDfsIterator : public DataflowIterator {
+ public:
+ explicit RepeatingReversePostOrderDfsIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) {
+ idx_ = start_idx_;
+ block_id_list_ = mir_graph->GetDfsPostOrder();
+ }
+
+ BasicBlock* Next(bool had_change) {
+ return ReverseRepeatNext(had_change);
+ }
};
class PostOrderDOMIterator : public DataflowIterator {
public:
- PostOrderDOMIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative, 0,
- mir_graph->GetNumReachableBlocks(), false) {
+ explicit PostOrderDOMIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) {
idx_ = start_idx_;
block_id_list_ = mir_graph->GetDomPostOrder();
}
+
+ BasicBlock* Next() {
+ return ForwardSingleNext();
+ }
};
class AllNodesIterator : public DataflowIterator {
public:
- AllNodesIterator(MIRGraph* mir_graph, bool is_iterative)
- : DataflowIterator(mir_graph, is_iterative, 0, 0, false) {
- all_nodes_iterator_ =
- new (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator(mir_graph->GetBlockList());
+ explicit AllNodesIterator(MIRGraph* mir_graph)
+ : DataflowIterator(mir_graph, 0, 0) {
+ all_nodes_iterator_ = new
+ (mir_graph->GetArena()) GrowableArray<BasicBlock*>::Iterator(mir_graph->GetBlockList());
}
void Reset() {
all_nodes_iterator_->Reset();
}
- BasicBlock* NextBody(bool had_change) ALWAYS_INLINE;
+ BasicBlock* Next() ALWAYS_INLINE;
private:
GrowableArray<BasicBlock*>::Iterator* all_nodes_iterator_;