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/CompilerUtility.h b/src/compiler/CompilerUtility.h
index d7612ff..a68ee5f 100644
--- a/src/compiler/CompilerUtility.h
+++ b/src/compiler/CompilerUtility.h
@@ -58,8 +58,20 @@
*/
struct ArenaBitVector {
bool expandable; /* expand bitmap if we run out? */
+ bool firstDirty; /* when true, don't believe firstBitSet */
+ bool lastDirty; /* when true, don't believe lastBitSet */
u4 storageSize; /* current size, in 32-bit words */
u4* storage;
+ /*
+ * Opportunistically remember first and
+ * last set bits. This yeilds a performance
+ * advantage in cases where large
+ * sparse vectors are repeatedly scanned
+ * (something that can happen a lot during
+ * dataflow analysis.
+ */
+ int firstBitSet;
+ int lastBitSet;
};
/* Handy iterator to walk through the bit positions set to 1 */