Index: lib/Transforms/Scalar/EarlyCSE.cpp
===================================================================
--- lib/Transforms/Scalar/EarlyCSE.cpp
+++ lib/Transforms/Scalar/EarlyCSE.cpp
@@ -600,13 +600,6 @@
             DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
                   << CondInst->getName() << "' as " << *ConditionalConstant
                   << " in " << BB->getName() << "\n");
-            // Replace all dominated uses with the known value.
-            if (unsigned Count =
-                    replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
-                                             BasicBlockEdge(Pred, BB))) {
-              Changed = true;
-              NumCSECVP = NumCSECVP + Count;
-            }
           }
 
   /// LastStore - Keep track of the last non-volatile store that we saw... for
@@ -622,6 +615,23 @@
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     Instruction *Inst = &*I++;
 
+    // Use the available value table to replace any operands we can.  This
+    // kicks in when we've inferred a control dependent equivelence fact.  Note
+    // that this does make the algorithm O(I^2) in the worst case (a series of
+    // calls which each use the previous instructions), but this was already
+    // true given we have to hash all the operands as well.
+    for (Value *V : Inst->operands())
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        if (SimpleValue::canHandle(I))
+          // See if the instruction has an available value.  If so, use it.
+          if (Value *Rep = AvailableValues.lookup(I)) {
+            DEBUG(dbgs() << "EarlyCSE replaced operand" << *I
+                         << " with " << *Rep << " in " << *Inst << '\n');
+            Inst->replaceUsesOfWith(V, Rep);
+            Changed = true;
+            NumCSECVP++;
+          }
+
     // Dead instructions should just be removed.
     if (isInstructionTriviallyDead(Inst, &TLI)) {
       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
@@ -659,8 +669,14 @@
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
         // The condition we're on guarding here is true for all dominated
         // locations.
-        if (SimpleValue::canHandle(CondI))
-          AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+        if (SimpleValue::canHandle(CondI)) {
+          DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
+                << CondI->getName() << "' as true after "
+                << Inst->getName()  << "\n");
+
+          auto *True = ConstantInt::getTrue(BB->getContext());
+          AvailableValues.insert(CondI, True);
+        }
       }
 
       // Guard intrinsics read all memory, but don't write any memory.
Index: test/Transforms/EarlyCSE/guards.ll
===================================================================
--- test/Transforms/EarlyCSE/guards.ll
+++ test/Transforms/EarlyCSE/guards.ll
@@ -180,3 +180,20 @@
   store i32 600, i32* %ptr
   ret void
 }
+
+define i32 @test7(i32 %val) {
+; After a guard has executed the condition it was guarding is known to
+; be true.  Unlike test3, uses the same condition for both guards and 
+; return value.
+
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+; CHECK-NEXT:  ret i32 -1
+
+  %cond0 = icmp slt i32 %val, 40
+  call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+  call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+  %rval = sext i1 %cond0 to i32
+  ret i32 %rval
+}