Index: llvm/lib/CodeGen/CodeGenPrepare.cpp
===================================================================
--- llvm/lib/CodeGen/CodeGenPrepare.cpp
+++ llvm/lib/CodeGen/CodeGenPrepare.cpp
@@ -713,6 +713,79 @@
   return EverMadeChange;
 }
 
+// The utility function collects all transitively reachable users of I.
+// If all users would be trivially dead in case they would not have users then
+// this function returns true and Closure contains I with all found users.
+// Otherwise function returns false and Closure content is not specified.
+// For the purpose of this function llvm.assume is considered as
+// trivially dead instruction.
+static bool findClosureOfWouldBeTriviallyDeadInstructions(
+    Instruction *I, SmallPtrSetImpl<Instruction *> &Closure,
+    const TargetLibraryInfo *TLInfo) {
+  assert(wouldInstructionBeTriviallyDead(I, TLInfo) && "expect trivially dead");
+  Closure.insert(I);
+  // Simple Case. no users.
+  if (I->use_empty())
+    return true;
+
+  SmallVector<Instruction *, 4> Worklist;
+  Worklist.push_back(I);
+  while (!Worklist.empty()) {
+    Instruction *Curr = Worklist.pop_back_val();
+    for (auto *U : Curr->users()) {
+      auto *UI = dyn_cast<Instruction>(U);
+      if (!UI)
+        return false;
+      if (!Closure.insert(UI).second)
+        continue;
+      if (isa<AssumeInst>(UI) || wouldInstructionBeTriviallyDead(UI, TLInfo))
+        Worklist.push_back(UI);
+      else
+        return false;
+    }
+  }
+  return true;
+}
+
+// For the given trivially dead instruction if no uses, collect all instructions
+// which can be removed together with it.
+static void findInstructionsToRemoveWithAssumeOperand(
+    Instruction *OperandInst, SmallPtrSetImpl<Instruction *> &ToRemove,
+    const TargetLibraryInfo *TLInfo) {
+  // Keeps the operands of already marked to remove instructions.
+  // Contains only instructions would be trivial dead if no uses.
+  SmallPtrSet<Instruction *, 4> Candidates;
+  Candidates.insert(OperandInst);
+
+  // For a given set of instructions, mark them to be removed, their operands
+  // are erased from instructions and are added to Candidates set if they
+  // would be trivially dead if no uses.
+  auto AddToRemove = [&](SmallPtrSetImpl<Instruction *> &ISet) {
+    ToRemove.insert(ISet.begin(), ISet.end());
+    for (auto *I : ISet) {
+      for (Use &OpU : I->operands()) {
+        if (Value *OpV = OpU.get()) {
+          OpU.set(nullptr);
+          if (auto *OpI = dyn_cast<Instruction>(OpV))
+            if (!ToRemove.count(OpI) &&
+                wouldInstructionBeTriviallyDead(OpI, TLInfo))
+              Candidates.insert(OpI);
+        }
+      }
+    }
+  };
+
+  SmallPtrSet<Instruction *, 8> ClosureOfDeadInstructions;
+  while (!Candidates.empty()) {
+    Instruction *Cand = *Candidates.begin();
+    Candidates.erase(Cand);
+    if (findClosureOfWouldBeTriviallyDeadInstructions(
+            Cand, ClosureOfDeadInstructions, TLInfo))
+      AddToRemove(ClosureOfDeadInstructions);
+    ClosureOfDeadInstructions.clear();
+  }
+}
+
 bool CodeGenPrepare::eliminateAssumptions(Function &F) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
@@ -725,7 +798,20 @@
         Assume->eraseFromParent();
 
         resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
-          RecursivelyDeleteTriviallyDeadInstructions(Operand, TLInfo, nullptr);
+          auto *OperandInst = dyn_cast<Instruction>(Operand);
+          if (!OperandInst ||
+              !wouldInstructionBeTriviallyDead(OperandInst, TLInfo))
+            return;
+          // Set of dead instructions after assume has been erased.
+          SmallPtrSet<Instruction *, 4> ToRemove;
+          findInstructionsToRemoveWithAssumeOperand(OperandInst, ToRemove,
+                                                    TLInfo);
+          // Remove everything we found.
+          for (auto *TR : ToRemove) {
+            assert(TR->use_empty() && "Expected no uses!");
+            salvageDebugInfo(*TR);
+            TR->eraseFromParent();
+          }
         });
       }
     }
Index: llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll
===================================================================
--- llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll
+++ llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll
@@ -32,9 +32,7 @@
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
@@ -63,9 +61,7 @@
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
@@ -95,9 +91,7 @@
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit: