Finally, add the required constraint checks to fix Transforms/SimplifyCFG/2005-08...

[oota-llvm.git] / lib / Transforms / Utils / SimplifyCFG.cpp

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index abe229d7edcf473a9f8f637a131e3d4d8bfb7d16..742efe6184420fc3ec657fa4ca59d036ca7d800a 100644 (file)
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -75,17 +75,58 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
 
-  if (!isa<PHINode>(Succ->front()))
-    return true;  // We can make the transformation, no problem.
-
   // Check to see if one of the predecessors of BB is already a predecessor of
   // Succ.  If so, we cannot do the transformation if there are any PHI nodes
   // with incompatible values coming in from the two edges!
   //
-  if (!SafeToMergeTerminators(BB->getTerminator(), Succ->getTerminator()))
-    return false;   // Cannot merge.
-
-  return true;
+  if (isa<PHINode>(Succ->front())) {
+    std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
+    for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);\
+         PI != PE; ++PI)
+      if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
+        // Loop over all of the PHI nodes checking to see if there are
+        // incompatible values coming in.
+        for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+          PHINode *PN = cast<PHINode>(I);
+          // Loop up the entries in the PHI node for BB and for *PI if the
+          // values coming in are non-equal, we cannot merge these two blocks
+          // (instead we should insert a conditional move or something, then
+          // merge the blocks).
+          if (PN->getIncomingValueForBlock(BB) !=
+              PN->getIncomingValueForBlock(*PI))
+            return false;  // Values are not equal...
+        }
+      }
+  }
+    
+  // Finally, if BB has PHI nodes that are used by things other than the PHIs in
+  // Succ and Succ has predecessors that are not Succ and not Pred, we cannot
+  // fold these blocks, as we don't know whether BB dominates Succ or not to
+  // update the PHI nodes correctly.
+  if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true;
+
+  // If the predecessors of Succ are only BB and Succ itself, we can handle this.
+  bool IsSafe = true;
+  for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI)
+    if (*PI != Succ && *PI != BB) {
+      IsSafe = false;
+      break;
+    }
+  if (IsSafe) return true;
+  
+  // If the PHI nodes in BB are only used by instructions in Succ, we are ok.
+  IsSafe = true;
+  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I) && IsSafe; ++I) {
+    PHINode *PN = cast<PHINode>(I);
+    for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E;
+         ++UI)
+      if (cast<Instruction>(*UI)->getParent() != Succ) {
+        IsSafe = false;
+        break;
+      }
+  }
+  
+  return IsSafe;
 }
 
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional
@@ -114,8 +155,8 @@ static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
       Value *OldVal = PN->removeIncomingValue(BB, false);
       assert(OldVal && "No entry in PHI for Pred BB!");
       
-      // If this incoming value is one of the PHI nodes in BB, the new entries in
-      // the PHI node are the entries from the old PHI.
+      // If this incoming value is one of the PHI nodes in BB, the new entries
+      // in the PHI node are the entries from the old PHI.
       if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
         PHINode *OldValPN = cast<PHINode>(OldVal);
         for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
@@ -138,15 +179,10 @@ static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
     // Move all PHI nodes in BB to Succ if they are alive, otherwise
     // delete them.
     while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
-      if (PN->use_empty() /*|| Succ->getSinglePredecessor() == 0*/) {
-        // We can only move the PHI node into Succ if BB dominates Succ.
-        // Since BB only has a single successor (Succ), the PHI nodes
-        // will dominate Succ, unless Succ has multiple predecessors.  In
-        // this case, the PHIs are either dead, or have references in dead
-        // blocks.  In either case, we can just remove them.
-        if (!PN->use_empty())   // Uses in dead block?
-          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
-        PN->eraseFromParent();  // Nuke instruction.
+      if (PN->use_empty()) {
+        // Just remove the dead phi.  This happens if Succ's PHIs were the only
+        // users of the PHI nodes.
+        PN->eraseFromParent();
       } else {
         // The instruction is alive, so this means that Succ must have
         // *ONLY* had BB as a predecessor, and the PHI node is still valid