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

1 files changed, 6 insertions, 0 deletions

diff --git a/src/compiler/CompilerIR.h b/src/compiler/CompilerIR.h
index f981ccd167..317924b31e 100644
--- a/src/compiler/CompilerIR.h
+++ b/src/compiler/CompilerIR.h
@@ -147,6 +147,7 @@ typedef enum BlockListType {
 
 typedef struct BasicBlock {
     int id;
+    int dfsId;
     bool visited;
     bool hidden;
     bool catchEntry;
@@ -191,6 +192,8 @@ typedef enum AssemblerStatus {
     kRetryHalve
 } AssemblerStatus;
 
+#define NOTVISITED (-1)
+
 typedef struct CompilationUnit {
     int numInsts;
     int numBlocks;
@@ -265,9 +268,11 @@ typedef struct CompilationUnit {
     BasicBlock* curBlock;
     BasicBlock* nextCodegenBlock;       // for extended trace codegen
     GrowableList dfsOrder;
+    GrowableList dfsPostOrder;
     GrowableList domPostOrderTraversal;
     GrowableList throwLaunchpads;
     GrowableList suspendLaunchpads;
+    int* iDomList;
     ArenaBitVector* tryBlockAddr;
     ArenaBitVector** defBlockMatrix;    // numDalvikRegister x numBlocks
     ArenaBitVector* tempBlockV;
@@ -310,6 +315,7 @@ typedef struct CompilationUnit {
      GrowableList fillArrayData;
      const u2* insns;
      u4 insnsSize;
+     std::map<unsigned int, BasicBlock*> blockMap; // findBlock lookup cache
 } CompilationUnit;
 
 BasicBlock* oatNewBB(BBType blockType, int blockId);