[DebugInfo] Don't skip deletion of dead BasicBlocks because of debug-info instructions

[jmorse]

Summary

This patch fixes a debug-info-changes-codegen problem, reported here:

https://github.com/llvm/llvm-project/issues/50525

Where the unreachableblockelim pass wouldn't delete an empty unreachable block due to the presence of debug-info instructions. The solution, as ever, is to ignore the debug-info instructions. This particular function is different, in that it steps through the block backwards, and so existing filter functions aren't suitable as they all expect forward iterators. Thus, a help lambda is required.

The most worry part here is replacing a line that is:

BB->getInsnlist().pop_back()

With Instruction::eraseFromParent on a non-back instruction. I think this is fine: it's just that over time, the set of helper functions that LLVM uses has changed, and this line hasn't been changed since at least 2008: https://github.com/llvm/llvm-project/commit/bcc904a67c2f77b6a619d8ec9370af02e3a5ce02

[jryans]

Thanks, this looks good to me. 😄

[probinson]

I don't spend a lot of time mucking around with IR transforms, so I'm not clear how _preserving_ the debug instructions makes it _possible_ to delete the block. Intuitively that doesn't make sense.

[jmorse]

/me squints,

Actually, it turns out the test is sketchy -- because I was using the autogenerated check lines, it wasn't testing for the absence of any other blocks. It doesn't appear that unreachableblockelim is the culprit at all, that's just where a change in CFG happens, which had attracted my attention. More detail on the GH ticket.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

for (auto *BB : BBs) {
     // of their predecessors is going away.
     SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
     for (BasicBlock *Succ : successors(BB)) {
       Succ->removePredecessor(BB, KeepOneInputPHIs);
       if (Updates && UniqueSuccessors.insert(Succ).second)
         Updates->push_back({DominatorTree::Delete, BB, Succ});
     }
 
-    // Zap all the instructions in the block.
-    while (!BB->empty()) {
-      Instruction &I = BB->back();
+    // Helper lambda to find the last non-debug-info instruction in the block,
+    // or the rend iterator.
+    auto FindLastNonDbg = [&]() -> BasicBlock::reverse_iterator {
+      auto RIt = BB->rbegin();
+      while (RIt != BB->rend()) {
+        if (!isa<DbgInfoIntrinsic>(&*RIt))
+          break;
+        RIt = std::next(RIt);
+      }
+      return RIt;
+    };
+
+    // Zap all the non-debug-info instructions in the block.
+    while (true) {
+      auto RIt = FindLastNonDbg();
+      if (RIt == BB->rend())
+        break;
+      Instruction &I = *RIt;
       // If this instruction is used, replace uses with an arbitrary value.
       // Because control flow can't get here, we don't care what we replace the
       // value with.  Note that since this block is unreachable, and all values
       // contained within it must dominate their uses, that all uses will
       // eventually be removed (they are themselves dead).
       if (!I.use_empty())
         I.replaceAllUsesWith(UndefValue::get(I.getType()));
-      BB->getInstList().pop_back();
+      I.eraseFromParent();
     }
+
     new UnreachableInst(BB->getContext(), BB);
-    assert(BB->getInstList().size() == 1 &&
+    assert(BB->sizeWithoutDebug() == 1 &&
            isa<UnreachableInst>(BB->getTerminator()) &&
            "The successor list of BB isn't empty before "
            "applying corresponding DTU updates.");
   }
 }
 
 void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
                            bool KeepOneInputPHIs) {

llvm/test/DebugInfo/Generic/unreachable-block-elim.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -unreachableblockelim -o - -S | FileCheck %s
+
+; Test that the unreachable block below, %b, is eliminated by the unreachable
+; block elimination pass, even though it contains a debug-info instruction.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local i32 @main() #0 !dbg !8 {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RETVAL:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 0, ptr [[RETVAL]], align 4
+; CHECK-NEXT:    br label [[A:%.*]], !dbg [[DBG14:![0-9]+]]
+; CHECK:       a:
+; CHECK-NEXT:    call void @llvm.dbg.label(metadata [[META15:![0-9]+]]), !dbg [[DBG16:![0-9]+]]
+; CHECK-NEXT:    br label [[RETURN:%.*]], !dbg [[DBG17:![0-9]+]]
+; CHECK:       return:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[RETVAL]], align 4, !dbg [[DBG17]]
+; CHECK-NEXT:    ret i32 [[TMP0]], !dbg [[DBG17]]
+;
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, ptr %retval, align 4
+  br label %a, !dbg !14
+
+b:                                                ; No predecessors!
+  call void @llvm.dbg.label(metadata !15), !dbg !16
+  store i32 0, ptr %retval, align 4, !dbg !17
+  br label %return, !dbg !17
+
+a:                                                ; preds = %entry
+  call void @llvm.dbg.label(metadata !18), !dbg !19
+  br label %return, !dbg !20
+
+return:                                           ; preds = %a, %b
+  %0 = load i32, ptr %retval, align 4, !dbg !20
+  ret i32 %0, !dbg !20
+}
+
+declare void @llvm.dbg.label(metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5, !6}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "/tmp/test.c", directory: ".")
+!2 = !{i32 7, !"Dwarf Version", i32 5}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 7, !"uwtable", i32 2}
+!6 = !{i32 7, !"frame-pointer", i32 2}
+!7 = !{!"clang"}
+!8 = distinct !DISubprogram(name: "main", scope: !9, file: !9, line: 1, type: !10, scopeLine: 1, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !13)
+!9 = !DIFile(filename: "/tmp/test.c", directory: "")
+!10 = !DISubroutineType(types: !11)
+!11 = !{!12}
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = !{}
+!14 = !DILocation(line: 2, column: 3, scope: !8)
+!15 = !DILabel(scope: !8, name: "b", file: !9, line: 3)
+!16 = !DILocation(line: 3, column: 1, scope: !8)
+!17 = !DILocation(line: 4, column: 3, scope: !8)
+!18 = !DILabel(scope: !8, name: "a", file: !9, line: 5)
+!19 = !DILocation(line: 5, column: 1, scope: !8)
+!20 = !DILocation(line: 6, column: 1, scope: !8)