Index: llvm/lib/Transforms/Scalar/BDCE.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/BDCE.cpp
+++ llvm/lib/Transforms/Scalar/BDCE.cpp
@@ -93,7 +93,7 @@
 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   SmallVector<Instruction*, 128> Worklist;
   bool Changed = false;
-  for (Instruction &I : instructions(F)) {
+  for (Instruction &I : llvm::reverse(instructions(F))) {
     // If the instruction has side effects and no non-dbg uses,
     // skip it. This way we avoid computing known bits on an instruction
     // that will not help us.
@@ -108,7 +108,6 @@
          wouldInstructionBeTriviallyDead(&I))) {
       salvageDebugInfo(I);
       Worklist.push_back(&I);
-      I.dropAllReferences();
       Changed = true;
       continue;
     }
@@ -155,6 +154,9 @@
     }
   }
 
+  for (Instruction *&I : Worklist)
+    I->dropAllReferences();
+
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
Index: llvm/test/Transforms/Util/salvage-debuginfo.ll
===================================================================
--- llvm/test/Transforms/Util/salvage-debuginfo.ll
+++ llvm/test/Transforms/Util/salvage-debuginfo.ll
@@ -1,4 +1,5 @@
 ; RUN: opt -adce %s -S -o - | FileCheck %s
+; RUN: opt -bdce %s -S -o - | FileCheck %s
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx"
 define void @f(i32) !dbg !8 {