diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index f1d0a9b..4f7df4f 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -99,15 +99,40 @@
       return SDOperand(N, 0);
     }
     
-    bool DemandedBitsAreZero(SDOperand Op, uint64_t DemandedMask) {
+    /// SimplifyDemandedBits - Check the specified integer node value to see if
+    /// it can be simplified or if things is uses can be simplified by bit
+    /// propagation.  If so, return true.
+    bool SimplifyDemandedBits(SDOperand Op) {
       TargetLowering::TargetLoweringOpt TLO(DAG);
       uint64_t KnownZero, KnownOne;
-      if (TLI.SimplifyDemandedBits(Op, DemandedMask, KnownZero, KnownOne, TLO)){
-        WorkList.push_back(Op.Val);
-        CombineTo(TLO.Old.Val, TLO.New);
-        return true;
-      }
-      return false;
+      uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType());
+      if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
+        return false;
+
+      // Revisit the node.
+      WorkList.push_back(Op.Val);
+      
+      // Replace the old value with the new one.
+      ++NodesCombined;
+      DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump();
+            std::cerr << "\nWith: "; TLO.New.Val->dump());
+
+      std::vector<SDNode*> NowDead;
+      DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead);
+      
+      // Push the new node and any (now) users onto the worklist.
+      WorkList.push_back(TLO.New.Val);
+      AddUsersToWorkList(TLO.New.Val);
+      
+      // Nodes can end up on the worklist more than once.  Make sure we do
+      // not process a node that has been replaced.
+      removeFromWorkList(TLO.Old.Val);
+      for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+        removeFromWorkList(NowDead[i]);
+      
+      // Finally, since the node is now dead, remove it from the graph.
+      DAG.DeleteNode(TLO.Old.Val);
+      return true;
     }
 
     SDOperand CombineTo(SDNode *N, SDOperand Res) {
@@ -985,7 +1010,7 @@
   }
   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
   // fold (and (sra)) -> (and (srl)) when possible.
-  if (DemandedBitsAreZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
+  if (SimplifyDemandedBits(SDOperand(N, 0)))
     return SDOperand();
   // fold (zext_inreg (extload x)) -> (zextload x)
   if (N0.getOpcode() == ISD::EXTLOAD) {
@@ -1267,7 +1292,7 @@
   // if (shl x, c) is known to be zero, return 0
   if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
     return DAG.getConstant(0, VT);
-  if (DemandedBitsAreZero(SDOperand(N,0), MVT::getIntVTBitMask(VT)))
+  if (SimplifyDemandedBits(SDOperand(N, 0)))
     return SDOperand();
   // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
   if (N1C && N0.getOpcode() == ISD::SHL && 
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 5fc0967..bb66825 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -21,6 +21,7 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include <iostream>
 #include <set>
@@ -2403,6 +2404,66 @@
   }
 }
 
+/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
+/// uses of other values produced by From.Val alone.  The Deleted vector is
+/// handled the same was as for ReplaceAllUsesWith.
+void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
+                                             std::vector<SDNode*> &Deleted) {
+  assert(From != To && "Cannot replace a value with itself");
+  // Handle the simple, trivial, case efficiently.
+  if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) {
+    ReplaceAllUsesWith(From, To, &Deleted);
+    return;
+  }
+  
+  // Get all of the users in a nice, deterministically ordered, uniqued set.
+  SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end());
+
+  while (!Users.empty()) {
+    // We know that this user uses some value of From.  If it is the right
+    // value, update it.
+    SDNode *User = Users.back();
+    Users.pop_back();
+    
+    for (SDOperand *Op = User->OperandList,
+         *E = User->OperandList+User->NumOperands; Op != E; ++Op) {
+      if (*Op == From) {
+        // Okay, we know this user needs to be updated.  Remove its old self
+        // from the CSE maps.
+        RemoveNodeFromCSEMaps(User);
+        
+        // Update all operands that match "From".
+        for (; Op != E; ++Op) {
+          if (*Op == From) {
+            From.Val->removeUser(User);
+            *Op = To;
+            To.Val->addUser(User);
+          }
+        }
+                   
+        // Now that we have modified User, add it back to the CSE maps.  If it
+        // already exists there, recursively merge the results together.
+        if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) {
+          unsigned NumDeleted = Deleted.size();
+          ReplaceAllUsesWith(User, Existing, &Deleted);
+          
+          // User is now dead.
+          Deleted.push_back(User);
+          DeleteNodeNotInCSEMaps(User);
+          
+          // We have to be careful here, because ReplaceAllUsesWith could have
+          // deleted a user of From, which means there may be dangling pointers
+          // in the "Users" setvector.  Scan over the deleted node pointers and
+          // remove them from the setvector.
+          for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i)
+            Users.remove(Deleted[i]);
+        }
+        break;   // Exit the operand scanning loop.
+      }
+    }
+  }
+}
+
 
 //===----------------------------------------------------------------------===//
 //                              SDNode Class