Improve the effectiveness of ADCE's debug info salvaging

[aprantl]

Summary

This patch improves the effectiveness of ADCE's debug info salvaging by processing the instructions in reverse order and delaying dropAllReferences until after debug info salvaging. This allows salvaging of entire chains of deleted instructions!

Previously we would remove all references from an instruction, which would make it impossible to use that instruction to salvage a later instruction in the instruction stream, because its operands were already removed.

[djtodoro]

Cool, thanks!

Can we apply the same for other places where we are salvaging the debugging info, for example - https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/BDCE.cpp#L109 ?

[aprantl]

In D110462#3023800, @djtodoro wrote:

Cool, thanks!

Can we apply the same for other places where we are salvaging the debugging info, for example - https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/BDCE.cpp#L109 ?

Yes! https://reviews.llvm.org/D110568

[djtodoro]

lgtm (please run clang-format), thanks!

llvm/lib/Transforms/Scalar/ADCE.cpp

for (Instruction &I : instructions(F)) {
       }
     }
   });
 
   // The inverse of the live set is the dead set.  These are those instructions
   // that have no side effects and do not influence the control flow or return
   // value of the function, and may therefore be deleted safely.
   // NOTE: We reuse the Worklist vector here for memory efficiency.
-  for (Instruction &I : instructions(F)) {
+  for (Instruction &I : llvm::reverse(instructions(F))) {
     // Check if the instruction is alive.
     if (isLive(&I))
       continue;
 
     if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
       // Check if the scope of this variable location is alive.
       if (AliveScopes.count(DII->getDebugLoc()->getScope()))
         continue;
 
       // Fallthrough and drop the intrinsic.
     }
 
     // Prepare to delete.
     Worklist.push_back(&I);
     salvageDebugInfo(I);
-    I.dropAllReferences();
   }
 
+  for (Instruction *&I : Worklist)
+    I->dropAllReferences();
+
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
   }
 
   return !Worklist.empty() || RegionsUpdated;
 }
 

llvm/test/Transforms/Util/salvage-debuginfo.ll

 ; RUN: opt -adce %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 {
 entry:
   %p_x = inttoptr i32 %0 to i8*
   %i_x = ptrtoint i8* %p_x to i32
-  ; CHECK: call void @llvm.dbg.value(metadata i8* undef,
-  ; CHECK-SAME: !DIExpression(DW_OP_LLVM_convert, 64, DW_ATE_unsigned,
+  ; CHECK: call void @llvm.dbg.value(metadata i32 %0,
+  ; CHECK-SAME: !DIExpression(DW_OP_LLVM_convert, 32, DW_ATE_unsigned,
+  ; CHECK-SAME:               DW_OP_LLVM_convert, 64, DW_ATE_unsigned,
+  ; CHECK-SAME:               DW_OP_LLVM_convert, 64, DW_ATE_unsigned,
   ; CHECK-SAME:               DW_OP_LLVM_convert, 32, DW_ATE_unsigned, DW_OP_stack_value))
   call void @llvm.dbg.value(metadata i32 %i_x, metadata !11, metadata !DIExpression()), !dbg !13
   ret void, !dbg !13
 }
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!3, !4}