Dataflow analysis rework
Rework key portions of the dataflow analysis code to avoid the
massive slowdowns we're seeing with methods containing more than
20,000 basic blocks.
Add a somewhat hacky lookup cache in front of findBlock. Later
we'll want to rework the "GrowableList" mechanism to incorporate
this properly.
Add memory to the bit vector utilities to speed up the iterators
for large sparse vectors. (Similarly, in the future we'll want
to include a rewrite of the home-grown bit-vector manipluation
utilites to be better with large ones).
With this CL, compilation speed on the degenerate cases is > 10x
faster. Compilation of typically-sized methods will see a smallish
improvement.
Change-Id: I7f086c1229dd4fe62f0a5fc361234bf204ebc2b1
diff --git a/src/compiler/Dataflow.cc b/src/compiler/Dataflow.cc
index 211cffb..3f88ea5 100644
--- a/src/compiler/Dataflow.cc
+++ b/src/compiler/Dataflow.cc
@@ -1509,82 +1509,104 @@
while (change) {
change = false;
+ switch (dfaMode) {
/* Scan all blocks and perform the operations specified in func */
- if (dfaMode == kAllNodes) {
- GrowableListIterator iterator;
- oatGrowableListIteratorInit(&cUnit->blockList, &iterator);
- while (true) {
- BasicBlock* bb =
- (BasicBlock *) oatGrowableListIteratorNext(&iterator);
- if (bb == NULL) break;
- if (bb->hidden == true) continue;
- change |= (*func)(cUnit, bb);
+ case kAllNodes:
+ {
+ GrowableListIterator iterator;
+ oatGrowableListIteratorInit(&cUnit->blockList, &iterator);
+ while (true) {
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListIteratorNext(&iterator);
+ if (bb == NULL) break;
+ if (bb->hidden == true) continue;
+ change |= (*func)(cUnit, bb);
+ }
}
- }
- /*
- * Scan all reachable blocks and perform the operations specified in
- * func.
- */
- else if (dfaMode == kReachableNodes) {
- int numReachableBlocks = cUnit->numReachableBlocks;
- int idx;
- const GrowableList *blockList = &cUnit->blockList;
+ break;
+ /* Scan reachable blocks and perform the ops specified in func. */
+ case kReachableNodes:
+ {
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
- for (idx = 0; idx < numReachableBlocks; idx++) {
- int blockIdx = cUnit->dfsOrder.elemList[idx];
- BasicBlock* bb =
- (BasicBlock *) oatGrowableListGetElement(blockList,
- blockIdx);
- change |= (*func)(cUnit, bb);
+ for (idx = 0; idx < numReachableBlocks; idx++) {
+ int blockIdx = cUnit->dfsOrder.elemList[idx];
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListGetElement(blockList,
+ blockIdx);
+ change |= (*func)(cUnit, bb);
+ }
}
- }
- /*
- * Scan all reachable blocks by the pre-order in the depth-first-search
- * CFG and perform the operations specified in func.
- */
- else if (dfaMode == kPreOrderDFSTraversal) {
- int numReachableBlocks = cUnit->numReachableBlocks;
- int idx;
- const GrowableList *blockList = &cUnit->blockList;
+ break;
- for (idx = 0; idx < numReachableBlocks; idx++) {
- int dfsIdx = cUnit->dfsOrder.elemList[idx];
- BasicBlock* bb =
- (BasicBlock *) oatGrowableListGetElement(blockList, dfsIdx);
- change |= (*func)(cUnit, bb);
- }
- }
- /*
- * Scan all reachable blocks by the post-order in the depth-first-search
- * CFG and perform the operations specified in func.
- */
- else if (dfaMode == kPostOrderDFSTraversal) {
- int numReachableBlocks = cUnit->numReachableBlocks;
- int idx;
- const GrowableList *blockList = &cUnit->blockList;
+ /* Scan reachable blocks by pre-order dfs and invoke func on each. */
+ case kPreOrderDFSTraversal:
+ {
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
- for (idx = numReachableBlocks - 1; idx >= 0; idx--) {
- int dfsIdx = cUnit->dfsOrder.elemList[idx];
- BasicBlock* bb =
- (BasicBlock *) oatGrowableListGetElement(blockList, dfsIdx);
- change |= (*func)(cUnit, bb);
+ for (idx = 0; idx < numReachableBlocks; idx++) {
+ int dfsIdx = cUnit->dfsOrder.elemList[idx];
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListGetElement(blockList,
+ dfsIdx);
+ change |= (*func)(cUnit, bb);
+ }
}
- }
- /*
- * Scan all reachable blocks by the post-order in the dominator tree
- * and perform the operations specified in func.
- */
- else if (dfaMode == kPostOrderDOMTraversal) {
- int numReachableBlocks = cUnit->numReachableBlocks;
- int idx;
- const GrowableList *blockList = &cUnit->blockList;
+ break;
+ /* Scan reachable blocks post-order dfs and invoke func on each. */
+ case kPostOrderDFSTraversal:
+ {
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
- for (idx = 0; idx < numReachableBlocks; idx++) {
- int domIdx = cUnit->domPostOrderTraversal.elemList[idx];
- BasicBlock* bb =
- (BasicBlock *) oatGrowableListGetElement(blockList, domIdx);
- change |= (*func)(cUnit, bb);
+ for (idx = numReachableBlocks - 1; idx >= 0; idx--) {
+ int dfsIdx = cUnit->dfsOrder.elemList[idx];
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListGetElement(blockList,
+ dfsIdx);
+ change |= (*func)(cUnit, bb);
+ }
}
+ break;
+ /* Scan reachable post-order dom tree and invoke func on each. */
+ case kPostOrderDOMTraversal:
+ {
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
+
+ for (idx = 0; idx < numReachableBlocks; idx++) {
+ int domIdx = cUnit->domPostOrderTraversal.elemList[idx];
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListGetElement(blockList,
+ domIdx);
+ change |= (*func)(cUnit, bb);
+ }
+ }
+ break;
+ /* Scan reachable blocks reverse post-order dfs, invoke func on each */
+ case kReversePostOrderTraversal:
+ {
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
+
+ for (idx = numReachableBlocks - 1; idx >= 0; idx--) {
+ int revIdx = cUnit->dfsPostOrder.elemList[idx];
+ BasicBlock* bb =
+ (BasicBlock *) oatGrowableListGetElement(blockList,
+ revIdx);
+ change |= (*func)(cUnit, bb);
+ }
+ }
+ break;
+ default:
+ LOG(FATAL) << "Unknown traversal mode " << (int)dfaMode;
}
/* If isIterative is false, exit the loop after the first iteration */
change &= isIterative;