Index: lib/Transforms/Scalar/BDCE.cpp
===================================================================
--- lib/Transforms/Scalar/BDCE.cpp
+++ lib/Transforms/Scalar/BDCE.cpp
@@ -15,6 +15,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/BDCE.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DemandedBits.h"
@@ -35,6 +36,28 @@
 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
 
+/// If an instruction is trivialized (dead), then users of that instruction need
+/// to be cleared of assumptions that can no longer be guaranteed correct. This
+/// recursively visits all subsequent users.
+static void
+clearAssumptionsOfUsers(Instruction *I,
+                        SmallPtrSetImpl<Instruction *> &VisitedInsts) {
+  // If we've already seen this instruction, we're done.
+  if (!VisitedInsts.insert(I).second)
+    return;
+
+  for (User *U : I->users()) {
+    if (auto *UserInst = dyn_cast<Instruction>(U)) {
+      // NSW/NUW and exact are based on operands that might have changed.
+      UserInst->dropPoisonGeneratingFlags();
+
+      // FIXME: llvm.assume and metadata may also be invalid now.
+
+      clearAssumptionsOfUsers(UserInst, VisitedInsts);
+    }
+  }
+}
+
 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   SmallVector<Instruction*, 128> Worklist;
   bool Changed = false;
@@ -51,6 +74,10 @@
       // replacing all uses with something else. Then, if they don't need to
       // remain live (because they have side effects, etc.) we can remove them.
       DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
+
+      SmallPtrSet<Instruction *, 16> VisitedInsts;
+      clearAssumptionsOfUsers(&I, VisitedInsts);
+
       // FIXME: In theory we could substitute undef here instead of zero.
       // This should be reconsidered once we settle on the semantics of
       // undef, poison, etc.
Index: test/Transforms/BDCE/invalidate-assumptions.ll
===================================================================
--- test/Transforms/BDCE/invalidate-assumptions.ll
+++ test/Transforms/BDCE/invalidate-assumptions.ll
@@ -1,6 +1,6 @@
 ; RUN: opt -bdce %s -S | FileCheck %s
 
-; FIXME: The 'nuw' on the subtract allows us to deduce that %setbit is not demanded.
+; The 'nuw' on the subtract allows us to deduce that %setbit is not demanded.
 ; But if we change that value to '0', then the 'nuw' is no longer valid. If we don't
 ; remove the 'nuw', another pass (-instcombine) may make a transform based on an
 ; that incorrect assumption and we can miscompile:
@@ -11,7 +11,7 @@
 ; CHECK-NEXT:    [[SETBIT:%.*]] = or i8 %x, 64
 ; CHECK-NEXT:    [[LITTLE_NUMBER:%.*]] = zext i1 %b to i8
 ; CHECK-NEXT:    [[BIG_NUMBER:%.*]] = shl i8 0, 1
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]]
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[SUB]] to i1
 ; CHECK-NEXT:    ret i1 [[TRUNC]]
 ;
@@ -23,7 +23,7 @@
   ret i1 %trunc
 }
 
-; FIXME: Similar to above, but now with more no-wrap.
+; Similar to above, but now with more no-wrap.
 ; https://bugs.llvm.org/show_bug.cgi?id=34037
 
 define i64 @PR34037(i64 %m, i32 %r, i64 %j, i1 %b, i32 %k, i64 %p) {
@@ -34,9 +34,9 @@
 ; CHECK-NEXT:    [[OR:%.*]] = or i64 %j, 0
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i64 0, 29
 ; CHECK-NEXT:    [[CONV1:%.*]] = select i1 %b, i64 7, i64 0
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i64 [[SHL]], [[CONV1]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[SHL]], [[CONV1]]
 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i32 %k to i64
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[SUB]], [[CONV2]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[SUB]], [[CONV2]]
 ; CHECK-NEXT:    [[CONV4:%.*]] = and i64 %p, 65535
 ; CHECK-NEXT:    [[AND5:%.*]] = and i64 [[MUL]], [[CONV4]]
 ; CHECK-NEXT:    ret i64 [[AND5]]