Index: lib/Transforms/Scalar/EarlyCSE.cpp
===================================================================
--- lib/Transforms/Scalar/EarlyCSE.cpp
+++ lib/Transforms/Scalar/EarlyCSE.cpp
@@ -54,18 +54,35 @@
 namespace {
 /// \brief Struct representing the available values in the scoped hash table.
 struct SimpleValue {
-  Instruction *Inst;
+  Value *Val;
 
-  SimpleValue(Instruction *I) : Inst(I) {
-    assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
+  SimpleValue(Value *V) : Val(V) {
+    assert((isSentinel() || canHandle(V)) && "Value can't be handled!");
   }
 
   bool isSentinel() const {
-    return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
-           Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
+    return Val == DenseMapInfo<Value *>::getEmptyKey() ||
+           Val == DenseMapInfo<Value *>::getTombstoneKey();
   }
 
-  static bool canHandle(Instruction *Inst) {
+  Instruction *getInst() const {
+    assert(isInst() && "This SimpleValue does not represent an instruction!");
+    return cast<Instruction>(Val);
+  }
+
+  Value *getValue() const {
+    return Val;
+  }
+
+  bool isInst() const {
+    return !isSentinel() && isa<Instruction>(Val);
+  }
+
+  static bool canHandle(Value *Val) {
+    Instruction *Inst = dyn_cast<Instruction>(Val);
+    // We can handle all non-instruction values.
+    if (!Inst)
+      return true;
     // This can only handle non-void readnone functions.
     if (CallInst *CI = dyn_cast<CallInst>(Inst))
       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
@@ -92,7 +109,9 @@
 }
 
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
-  Instruction *Inst = Val.Inst;
+  if (!Val.isInst())
+    return hash_combine(Val.getValue());
+  Instruction *Inst = Val.getInst();
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *LHS = BinOp->getOperand(0);
@@ -139,10 +158,16 @@
 }
 
 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
-  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
+  // Equal values are both either instructions or not.
+  if (LHS.isInst() != RHS.isInst())
+    return false;
 
-  if (LHS.isSentinel() || RHS.isSentinel())
-    return LHSI == RHSI;
+  // If they are not instructions, simply compare values.
+  if (!LHS.isInst() || LHS.isSentinel() || RHS.isSentinel())
+    return LHS.getValue() == RHS.getValue();
+
+  // Otherwise try to prove equality of instructions.
+  Instruction *LHSI = LHS.getInst(), *RHSI = RHS.getInst();
 
   if (LHSI->getOpcode() != RHSI->getOpcode())
     return false;
@@ -590,19 +615,19 @@
   if (BasicBlock *Pred = BB->getSinglePredecessor()) {
     auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
     if (BI && BI->isConditional()) {
-      auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
-      if (CondInst && SimpleValue::canHandle(CondInst)) {
+      auto *Cond = BI->getCondition();
+      if (SimpleValue::canHandle(Cond)) {
         assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
         auto *TorF = (BI->getSuccessor(0) == BB)
                          ? ConstantInt::getTrue(BB->getContext())
                          : ConstantInt::getFalse(BB->getContext());
-        AvailableValues.insert(CondInst, TorF);
+        AvailableValues.insert(Cond, TorF);
         DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
-                     << CondInst->getName() << "' as " << *TorF << " in "
+                     << Cond->getName() << "' as " << *TorF << " in "
                      << BB->getName() << "\n");
         // Replace all dominated uses with the known value.
         if (unsigned Count = replaceDominatedUsesWith(
-                CondInst, TorF, DT, BasicBlockEdge(Pred, BB))) {
+                Cond, TorF, DT, BasicBlockEdge(Pred, BB))) {
           Changed = true;
           NumCSECVP = NumCSECVP + Count;
         }
@@ -638,11 +663,10 @@
     // and this pass will not bother with its removal. However, we should mark
     // its condition as true for all dominated blocks.
     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
-      auto *CondI =
-          dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0));
-      if (CondI && SimpleValue::canHandle(CondI)) {
+      auto *Cond = cast<CallInst>(Inst)->getArgOperand(0);
+      if (SimpleValue::canHandle(Cond)) {
         DEBUG(dbgs() << "EarlyCSE considering assumption: " << *Inst << '\n');
-        AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+        AvailableValues.insert(Cond, ConstantInt::getTrue(BB->getContext()));
       } else
         DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
       continue;
@@ -662,27 +686,25 @@
       continue;
 
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
-      if (auto *CondI =
-              dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
-        if (SimpleValue::canHandle(CondI)) {
-          // Do we already know the actual value of this condition?
-          if (auto *KnownCond = AvailableValues.lookup(CondI)) {
-            // Is the condition known to be true?
-            if (isa<ConstantInt>(KnownCond) &&
-                cast<ConstantInt>(KnownCond)->isOneValue()) {
-              DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
-              removeMSSA(Inst);
-              Inst->eraseFromParent();
-              Changed = true;
-              continue;
-            } else
-              // Use the known value if it wasn't true.
-              cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
-          }
-          // The condition we're on guarding here is true for all dominated
-          // locations.
-          AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+      auto *Cond = cast<CallInst>(Inst)->getArgOperand(0);
+      if (SimpleValue::canHandle(Cond)) {
+        // Do we already know the actual value of this condition?
+        if (auto *KnownCond = AvailableValues.lookup(Cond)) {
+          // Is the condition known to be true?
+          if (isa<ConstantInt>(KnownCond) &&
+              cast<ConstantInt>(KnownCond)->isOneValue()) {
+            DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
+            removeMSSA(Inst);
+            Inst->eraseFromParent();
+            Changed = true;
+            continue;
+          } else
+            // Use the known value if it wasn't true.
+            cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
         }
+        // The condition we're on guarding here is true for all dominated
+        // locations.
+        AvailableValues.insert(Cond, ConstantInt::getTrue(BB->getContext()));
       }
 
       // 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
@@ -526,3 +526,141 @@
   call void @llvm.assume(i1 %c)
   ret void
 }
+
+define void @test19(i1 %c) {
+; Check that assume can mark a non-instruction value as true.
+
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:    call void @llvm.assume(i1 %c)
+; CHECK-NEXT:    ret void
+
+  call void @llvm.assume(i1 %c)
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  ret void
+}
+
+define void @test20(i1 %c) {
+; Check that guard can mark a non-instruction value as true.
+
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+; CHECK-NEXT:    ret void
+
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  ret void
+}
+
+define void @test21(i1 %c) {
+; Check that branching by a non-instruction condition allows to remove guards.
+
+; CHECK-LABEL: @test21(
+; CHECK:       entry:
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test22(i1 %cmp, i1 %c, i32* %ptr) {
+; Similar to test14, but with assumed condition being non-instruction.
+
+; CHECK-LABEL: @test22(
+; CHECK:       entry:
+; CHECK-NEXT:    call void @llvm.assume(i1 %cmp)
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 600, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  call void @llvm.assume(i1 %cmp)
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 500, i32* %ptr
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 600, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test23(i1 %cmp, i1 %c, i32* %ptr) {
+; Similar to test22, guard instead of assume.
+
+; CHECK-LABEL: @test23(
+; CHECK:       entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 600, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 500, i32* %ptr
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 600, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}