commit 5b53710b4abcf8f35c91a963a475b72cb34757e6
author buzbee <buzbee@google.com> Tue Jan 17 17:33:47 2012 -0800
committer buzbee <buzbee@google.com> Tue Jan 24 06:00:32 2012 -0800
tree 9f10f49fd09798a8f07ebffb4ee357c135e56f9f
parent cf044318c5638df0c400b731e94fab948ebd5ccb

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

src/compiler/Utility.cc

diff --git a/src/compiler/Utility.cc b/src/compiler/Utility.cc
index 8d70136..c76143b 100644
--- a/src/compiler/Utility.cc
+++ b/src/compiler/Utility.cc
@@ -231,6 +231,8 @@
     bv->storageSize = count;
     bv->expandable = expandable;
     bv->storage = (u4*) oatNew(count * sizeof(u4), true);
+    bv->firstDirty = true;
+    bv->lastDirty = true;
     return bv;
 }
 
@@ -252,6 +254,8 @@
 {
     unsigned int count = pBits->storageSize;
     memset(pBits->storage, 0, count * sizeof(u4));
+    pBits->firstDirty = true;
+    pBits->lastDirty = true;
 }
 
 /*
@@ -281,6 +285,12 @@
     }
 
     pBits->storage[num >> 5] |= checkMasks[num & 0x1f];
+    if (!pBits->firstDirty && ((int)num < pBits->firstBitSet)) {
+        pBits->firstBitSet = num;
+    }
+    if (!pBits->lastDirty && ((int)num > pBits->lastBitSet)) {
+        pBits->lastBitSet = num;
+    }
     return true;
 }
 
@@ -299,6 +309,8 @@
     }
 
     pBits->storage[num >> 5] &= ~checkMasks[num & 0x1f];
+    pBits->firstDirty = true;
+    pBits->lastDirty = true;
     return true;
 }
 
@@ -309,6 +321,8 @@
 {
     int value = set ? -1 : 0;
     memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4));
+    pBits->firstDirty = true;
+    pBits->lastDirty = true;
 }
 
 void oatDebugBitVector(char* msg, const ArenaBitVector* bv, int length)
@@ -374,6 +388,10 @@
     checkSizes(dest, src);
 
     memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
+    dest->firstDirty = src->firstDirty;
+    dest->firstBitSet = src->firstBitSet;
+    dest->lastDirty = src->lastDirty;
+    dest->lastBitSet = src->lastBitSet;
 }
 
 /*
@@ -395,6 +413,8 @@
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
     }
+    dest->firstDirty = true;
+    dest->lastDirty = true;
     return true;
 }
 
@@ -416,6 +436,8 @@
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] | src2->storage[idx];
     }
+    dest->firstDirty = true;
+    dest->lastDirty = true;
     return true;
 }
 
@@ -466,18 +488,36 @@
 /* Return the next position set to 1. -1 means end-of-element reached */
 int oatBitVectorIteratorNext(ArenaBitVectorIterator* iterator)
 {
-    const ArenaBitVector* pBits = iterator->pBits;
+    ArenaBitVector* pBits = iterator->pBits;
     u4 bitIndex = iterator->idx;
 
     DCHECK_EQ(iterator->bitSize, pBits->storageSize * sizeof(u4) * 8);
     if (bitIndex >= iterator->bitSize) return -1;
 
+    /* If we know, skip past leading zeros */
+    if (!pBits->firstDirty && ((int)bitIndex < pBits->firstBitSet)) {
+        iterator->idx = pBits->firstBitSet + 1;
+        return pBits->firstBitSet;
+    }
+
+    /* If we know, skip past trailing zeroes */
+    if (!pBits->lastDirty && ((int)bitIndex > pBits->lastBitSet)) {
+        iterator->idx = iterator->bitSize;
+        return -1;
+    }
+
+    bool firstPass = (bitIndex == 0);
+    u4 startIndex = bitIndex;
     for (; bitIndex < iterator->bitSize;) {
         unsigned int wordIndex = bitIndex >> 5;
         unsigned int bitPos = bitIndex & 0x1f;
         unsigned int word = pBits->storage[wordIndex];
         if (word & checkMasks[bitPos]) {
             iterator->idx = bitIndex+1;
+            if (firstPass && pBits->firstDirty) {
+                pBits->firstBitSet = bitIndex;
+                pBits->firstDirty = false;
+            }
             return bitIndex;
         }
         if (word == 0) {
@@ -488,6 +528,14 @@
         }
     }
     /* No more set bits */
+    if (firstPass) {
+        // Empty
+        pBits->firstBitSet = -1;
+        pBits->firstDirty = false;
+    } else {
+        pBits->lastBitSet = startIndex - 1;
+        pBits->lastDirty = false;
+    }
     return -1;
 }
 
@@ -507,6 +555,8 @@
     if (remNumBits) {
         pBits->storage[idx] = (1 << remNumBits) - 1;
     }
+    pBits->firstDirty = true;
+    pBits->lastDirty = true;
 }
 
 void oatGetBlockName(BasicBlock* bb, char* name)