diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 45d3d4e..e3e4cb7 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -80,63 +80,93 @@
 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
 
-  // 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 (isa<PHINode>(Succ->front())) {
-    SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
-    for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
-         PI != PE; ++PI)
-      if (BBPreds.count(*PI)) {
-        // 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...
+  DOUT << "Looking to fold " << BB->getNameStart() << " into " 
+       << Succ->getNameStart() << "\n";
+  // Shortcut, if there is only a single predecessor is must be BB and merging
+  // is always safe
+  if (Succ->getSinglePredecessor()) return true;
+
+  typedef SmallPtrSet<Instruction*, 16> InstrSet;
+  InstrSet BBPHIs;
+
+  // Make a list of all phi nodes in BB
+  BasicBlock::iterator BBI = BB->begin();
+  while (isa<PHINode>(*BBI)) BBPHIs.insert(BBI++);
+
+  // Make a list of the predecessors of BB
+  typedef SmallPtrSet<BasicBlock*, 16> BlockSet;
+  BlockSet BBPreds(pred_begin(BB), pred_end(BB));
+
+  // Use that list to make another list of common predecessors of BB and Succ
+  BlockSet CommonPreds;
+  for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
+        PI != PE; ++PI)
+    if (BBPreds.count(*PI))
+      CommonPreds.insert(*PI);
+
+  // Shortcut, if there are no common predecessors, merging is always safe
+  if (CommonPreds.begin() == CommonPreds.end())
+    return true;
+  
+  // Look at all the phi nodes in Succ, to see if they present a conflict when
+  // merging these blocks
+  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
+    PHINode *PN = cast<PHINode>(I);
+
+    // If the incoming value from BB is again a PHINode in
+    // BB which has the same incoming value for *PI as PN does, we can
+    // merge the phi nodes and then the blocks can still be merged
+    PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
+    if (BBPN && BBPN->getParent() == BB) {
+      for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end();
+            PI != PE; PI++) {
+        if (BBPN->getIncomingValueForBlock(*PI) 
+              != PN->getIncomingValueForBlock(*PI)) {
+          DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " 
+               << Succ->getNameStart() << " is conflicting with " 
+               << BBPN->getNameStart() << " with regard to common predecessor "
+               << (*PI)->getNameStart() << "\n";
+          return false;
         }
       }
-  }
-    
-  // 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, handle it.
-  bool IsSafe = true;
-  for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI)
-    if (*PI != BB) {
-      IsSafe = false;
-      break;
+      // Remove this phinode from the list of phis in BB, since it has been
+      // handled.
+      BBPHIs.erase(BBPN);
+    } else {
+      Value* Val = PN->getIncomingValueForBlock(BB);
+      for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end();
+            PI != PE; PI++) {
+        // See if the incoming value for the common predecessor is equal to the
+        // one for BB, in which case this phi node will not prevent the merging
+        // of the block.
+        if (Val != PN->getIncomingValueForBlock(*PI)) {
+          DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " 
+          << Succ->getNameStart() << " is conflicting with regard to common "
+          << "predecessor " << (*PI)->getNameStart() << "\n";
+          return false;
+        }
+      }
     }
-  if (IsSafe) return true;
-  
-  // If the PHI nodes in BB are only used by instructions in Succ, we are ok if
-  // BB and Succ have no common predecessors.
-  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++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)
-        return false;
   }
-  
-  // Scan the predecessor sets of BB and Succ, making sure there are no common
-  // predecessors.  Common predecessors would cause us to build a phi node with
-  // differing incoming values, which is not legal.
-  SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
-  for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI)
-    if (BBPreds.count(*PI))
-      return false;
-    
+
+  // If there are any other phi nodes in BB that don't have a phi node in Succ
+  // to merge with, they must be moved to Succ completely. However, for any
+  // predecessors of Succ, branches will be added to the phi node that just
+  // point to itself. So, for any common predecessors, this must not cause
+  // conflicts.
+  for (InstrSet::iterator I = BBPHIs.begin(), E = BBPHIs.end();
+        I != E; I++) {
+    PHINode *PN = cast<PHINode>(*I);
+    for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end();
+          PI != PE; PI++)
+      if (PN->getIncomingValueForBlock(*PI) != PN) {
+        DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " 
+             << BB->getNameStart() << " is conflicting with regard to common "
+             << "predecessor " << (*PI)->getNameStart() << "\n";
+        return false;
+      }
+  }
+
   return true;
 }
 
@@ -145,11 +175,8 @@
 /// branch.  If possible, eliminate BB.
 static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
                                                     BasicBlock *Succ) {
-  // If our successor has PHI nodes, then we need to update them to include
-  // entries for BB's predecessors, not for BB itself.  Be careful though,
-  // if this transformation fails (returns true) then we cannot do this
-  // transformation!
-  //
+  // Check to see if merging these blocks would cause conflicts for any of the
+  // phi nodes in BB or Succ. If not, we can safely merge.
   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
   
   DOUT << "Killing Trivial BB: \n" << *BB;
@@ -171,6 +198,11 @@
       if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
         PHINode *OldValPN = cast<PHINode>(OldVal);
         for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
+          // Note that, since we are merging phi nodes and BB and Succ might
+          // have common predecessors, we could end up with a phi node with
+          // identical incoming branches. This will be cleaned up later (and
+          // will trigger asserts if we try to clean it up now, without also
+          // simplifying the corresponding conditional branch).
           PN->addIncoming(OldValPN->getIncomingValue(i),
                           OldValPN->getIncomingBlock(i));
       } else {
@@ -193,19 +225,21 @@
         // 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
-        // now.  Simply move it into Succ, because we know that BB
-        // strictly dominated Succ.
+        // The instruction is alive, so this means that BB must dominate all
+        // predecessors of Succ (Since all uses of the PN are after its
+        // definition, so in Succ or a block dominated by Succ. If a predecessor
+        // of Succ would not be dominated by BB, PN would violate the def before
+        // use SSA demand). Therefore, we can simply move the phi node to the
+        // next block.
         Succ->getInstList().splice(Succ->begin(),
                                    BB->getInstList(), BB->begin());
         
         // We need to add new entries for the PHI node to account for
         // predecessors of Succ that the PHI node does not take into
-        // account.  At this point, since we know that BB dominated succ,
-        // this means that we should any newly added incoming edges should
-        // use the PHI node as the value for these edges, because they are
-        // loop back edges.
+        // account.  At this point, since we know that BB dominated succ and all
+        // of its predecessors, this means that we should any newly added
+        // incoming edges should use the PHI node itself as the value for these
+        // edges, because they are loop back edges.
         for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
           if (OldSuccPreds[i] != BB)
             PN->addIncoming(PN, OldSuccPreds[i]);
diff --git a/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll b/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
new file mode 100644
index 0000000..8af2640
--- /dev/null
+++ b/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
@@ -0,0 +1,131 @@
+; RUN: llvm-as < %s | opt -simplifycfg | llvm-dis > %t
+; RUN: not grep {^BB.tomerge} %t
+; RUN  grep {^BB.nomerge} %t | count 2
+
+; ModuleID = '<stdin>' 
+declare i1 @foo()
+
+declare i1 @bar(i32)
+
+; This function can't be merged
+define void @a() {
+entry:
+	br label %BB.nomerge
+
+BB.nomerge:		; preds = %Common, %entry
+        ; This phi has a conflicting value (0) with below phi (2), so blocks
+        ; can't be merged.
+	%a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
+	br label %Succ
+
+Succ:		; preds = %Common, %BB.nomerge
+	%b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
+	%conde = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %conde, label %Common, label %Exit
+
+Common:		; preds = %Succ
+	%cond = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %cond, label %BB.nomerge, label %Succ
+
+Exit:		; preds = %Succ
+	ret void
+}
+
+; This function can't be merged
+define void @b() {
+entry:
+	br label %BB.nomerge
+
+BB.nomerge:		; preds = %Common, %entry
+	br label %Succ
+
+Succ:		; preds = %Common, %BB.nomerge
+        ; This phi has confliction values for Common and (through BB) Common,
+        ; blocks can't be merged
+	%b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
+	%conde = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %conde, label %Common, label %Exit
+
+Common:		; preds = %Succ
+	%cond = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %cond, label %BB.nomerge, label %Succ
+
+Exit:		; preds = %Succ
+	ret void
+}
+
+; This function can be merged
+define void @c() {
+entry:
+	br label %BB.tomerge
+
+BB.tomerge:		; preds = %Common, %entry
+	br label %Succ
+
+Succ:		; preds = %Common, %BB.tomerge, %Pre-Exit
+        ; This phi has identical values for Common and (through BB) Common,
+        ; blocks can't be merged
+	%b = phi i32 [ 1, %BB.tomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
+	%conde = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %conde, label %Common, label %Pre-Exit
+
+Common:		; preds = %Succ
+	%cond = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %cond, label %BB.tomerge, label %Succ
+
+Pre-Exit:       ; preds = %Succ
+        ; This adds a backedge, so the %b phi node gets a third branch and is
+        ; not completely trivial
+	%cond2 = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %cond2, label %Succ, label %Exit
+        
+Exit:		; preds = %Pre-Exit
+	ret void
+}
+
+; This function can be merged
+define void @d() {
+entry:
+	br label %BB.tomerge
+
+BB.tomerge:		; preds = %Common, %entry
+        ; This phi has a matching value (0) with below phi (0), so blocks
+        ; can be merged.
+	%a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
+	br label %Succ
+
+Succ:		; preds = %Common, %BB.tomerge
+	%b = phi i32 [ %a, %BB.tomerge ], [ 0, %Common ]		; <i32> [#uses=0]
+	%conde = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %conde, label %Common, label %Exit
+
+Common:		; preds = %Succ
+	%cond = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %cond, label %BB.tomerge, label %Succ
+
+Exit:		; preds = %Succ
+	ret void
+}
+
+; This function can be merged
+define void @e() {
+entry:
+	br label %BB.tomerge
+
+BB.tomerge:		; preds = %Use, %entry
+        ; This phi is used somewhere else than Succ, but this should not prevent
+        ; merging this block
+	%a = phi i32 [ 1, %entry ], [ 0, %Use ]		; <i32> [#uses=1]
+	br label %Succ
+
+Succ:		; preds = %BB.tomerge
+	%conde = call i1 @foo( )		; <i1> [#uses=1]
+	br i1 %conde, label %Use, label %Exit
+
+Use:		; preds = %Succ
+	%cond = call i1 @bar( i32 %a )		; <i1> [#uses=1]
+	br i1 %cond, label %BB.tomerge, label %Exit
+
+Exit:		; preds = %Use, %Succ
+	ret void
+}