Split alloca liveness propagation into separate forward and backward phases.

This makes the code simpler, and avoids problems with the two directions
interfering with each other. This fixes asm2.test_sqlite and other failures.

2 files changed, 34 insertions, 26 deletions

diff --git a/lib/Target/JSBackend/AllocaManager.cpp b/lib/Target/JSBackend/AllocaManager.cpp
index aac7abdec3..2218732a25 100644
--- a/lib/Target/JSBackend/AllocaManager.cpp
+++ b/lib/Target/JSBackend/AllocaManager.cpp
@@ -206,7 +206,7 @@ void AllocaManager::collectBlocks() {
     if (BLI.LiveOut.any()) {
       for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
            SI != SE; ++SI) {
-        InterBlockWorklist.insert(*SI);
+        InterBlockTopDownWorklist.insert(*SI);
       }
     }
 
@@ -218,7 +218,7 @@ void AllocaManager::collectBlocks() {
     if (BLI.LiveIn.any()) {
       for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
            PI != PE; ++PI) {
-        InterBlockWorklist.insert(*PI);
+        InterBlockBottomUpWorklist.insert(*PI);
       }
     }
   }
@@ -233,30 +233,11 @@ void AllocaManager::computeInterBlockLiveness() {
 
   BitVector Temp(AllocaCount);
 
-  // This is currently using a very simple-minded bi-directional liveness
-  // propagation algorithm. Numerous opportunities for compile time
-  // speedups here.
-  while (!InterBlockWorklist.empty()) {
-    const BasicBlock *BB = InterBlockWorklist.pop_back_val();
+  // Proporgate liveness backwards.
+  while (!InterBlockBottomUpWorklist.empty()) {
+    const BasicBlock *BB = InterBlockBottomUpWorklist.pop_back_val();
     BlockLifetimeInfo &BLI = BlockLiveness[BB];
 
-    // Compute the new live-in set.
-    for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
-         PI != PE; ++PI) {
-      Temp |= BlockLiveness[*PI].LiveOut;
-    }
-
-    // If it contains new live blocks, prepare to propagate them.
-    Temp.reset(BLI.End);
-    if (Temp.test(BLI.LiveOut)) {
-      BLI.LiveOut |= Temp;
-      for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
-           SI != SE; ++SI) {
-        InterBlockWorklist.insert(*SI);
-      }
-    }
-    Temp.reset();
-
     // Compute the new live-out set.
     for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
          SI != SE; ++SI) {
@@ -270,7 +251,33 @@ void AllocaManager::computeInterBlockLiveness() {
       BLI.LiveIn |= Temp;
       for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
            PI != PE; ++PI) {
-        InterBlockWorklist.insert(*PI);
+        InterBlockBottomUpWorklist.insert(*PI);
+      }
+    }
+    Temp.reset();
+  }
+
+  // Proporgate liveness forwards.
+  while (!InterBlockTopDownWorklist.empty()) {
+    const BasicBlock *BB = InterBlockTopDownWorklist.pop_back_val();
+    BlockLifetimeInfo &BLI = BlockLiveness[BB];
+
+    // Compute the new live-in set.
+    for (const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+         PI != PE; ++PI) {
+      Temp |= BlockLiveness[*PI].LiveOut;
+    }
+
+    // Also record the live-in values.
+    BLI.LiveIn |= Temp;
+
+    // If it contains new live blocks, prepare to propagate them.
+    Temp.reset(BLI.End);
+    if (Temp.test(BLI.LiveOut)) {
+      BLI.LiveOut |= Temp;
+      for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
+           SI != SE; ++SI) {
+        InterBlockTopDownWorklist.insert(*SI);
       }
     }
     Temp.reset();
diff --git a/lib/Target/JSBackend/AllocaManager.h b/lib/Target/JSBackend/AllocaManager.h
index 44b07981bc..fc2a7998a2 100644
--- a/lib/Target/JSBackend/AllocaManager.h
+++ b/lib/Target/JSBackend/AllocaManager.h
@@ -46,7 +46,8 @@ class AllocaManager {
 
   // Worklist for inter-block liveness analysis.
   typedef SmallSetVector<const BasicBlock *, 8> InterBlockWorklistVec;
-  InterBlockWorklistVec InterBlockWorklist;
+  InterBlockWorklistVec InterBlockTopDownWorklist;
+  InterBlockWorklistVec InterBlockBottomUpWorklist;
 
   // Map allocas to their index in AllocasByIndex.
   typedef DenseMap<const AllocaInst *, size_t> AllocaMap;