[BranchFolding] Salvage DBG_VALUE instructions from empty blocks

[bjope]

Summary

This patch will introduce copying of DBG_VALUE instructions
from an otherwise empty basic block to predecessor/successor
blocks in case the empty block is eliminated/bypassed. It
is currently only done in one identified situation in the
BranchFolding pass, before optimizing on empty block.
It can be seen as a light variant of the propagation done
by the LiveDebugValues pass, which unfortunately is executed
after the BranchFolding pass.

We only propagate (copy) DBG_VALUE instructions in a limited
number of situations:
a) If the empty BB is the only predecessor of a successor

we can copy the DBG_VALUE instruction to the beginning of
the successor (because the DBG_VALUE instruction is always
part of the flow between the blocks).

b) If the empty BB is the only successor of a predecessor

we can copy the DBG_VALUE instruction to the end of the
predecessor (because the DBG_VALUE instruction is always
part of the flow between the blocks). In this case we add
the DBG_VALUE just before the first terminator (assuming
that the terminators do not impact the DBG_VALUE).

A future solution, to handle more situations, could perhaps
be to run the LiveDebugValues pass before branch folding?

This fix is related to PR37234. It is expected to resolve
the problem seen, when applied together with the fix in
SelectionDAG from here: https://reviews.llvm.org/D46129

[aprantl]

Have you thought about just changing the scheduling of the LiveDebugValues pass to run earlier instead? Would that be an overall improvement?

[bjope]

In D46184#1081160, @aprantl wrote:

Have you thought about just changing the scheduling of the LiveDebugValues pass to run earlier instead? Would that be an overall improvement?

Not more than mentioned in the summary:
"A future solution, to handle more situations, could perhaps be to run the LiveDebugValues pass before branch folding?"

I think it would be an interesting thing to test. Does anybody know if there are some known restrictions, explaining why the LiveDebugValues pass is run so late today?

I see one potential risk with populating the code with lots of DBG_VALUE instructions not really related to the preceeding MI.
Currently a DBG_VALUE basically follows the preceeding MI around when scheduling in our out-of-tree VLIW-scheduler (I think it is quite similar with the in-tree MIScheduler). So if there are lots of DBG_VALUE instructions that aren't describing what happened in the preceeding instruction, then the result after scheduling will be bad. So scheduling is a major problem for us when it comes to debug-info. We do MI scheduling late in the pipeline, including VLIW bundling and we haven't yet found a way to teach the scheduler how to handle debug-info properly, while still ignoring debug-info since the codegen should be the same with and without debug-info.

[aprantl]

Thanks for the analysis! It sounds like running LiveDebugValues after MI scheduling is the right way to go at this point in time. Assuming that scheduling happens after branch folding, let's do this patch for now. Also, LiveDebugValues wouldn't do the kind of backwards propagation that you are doing here, so I'd consider this a cheap enabler for LiveDebugValues to be more effective.

lib/CodeGen/BranchFolding.cpp

1392

ditto

1397

s/should be possible/ is legal/

lib/CodeGen/BranchFolding.cpp

 /// instructions on the block.
 static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) {
   MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr();
   if (I != MBB.end() && I->isBranch())
     return I->getDebugLoc();
   return DebugLoc();
 }
 
+static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII,
+                                       MachineBasicBlock &MBB,
+                                       MachineBasicBlock &PredMBB) {
+  auto InsertBefore = PredMBB.getFirstTerminator();
+  for (MachineInstr &MI : MBB.instrs())
+    if (MI.isDebugValue()) {
+      TII->duplicate(PredMBB, InsertBefore, MI);
+      DEBUG(dbgs() << "Copied debug value from empty block to pred: " << MI);
+    }
+}
+
+static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII,
+                                     MachineBasicBlock &MBB,
+                                     MachineBasicBlock &SuccMBB) {
+  auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
+  for (MachineInstr &MI : MBB.instrs())
+    if (MI.isDebugValue()) {
+      TII->duplicate(SuccMBB, InsertBefore, MI);
+      DEBUG(dbgs() << "Copied debug value from empty block to succ: " << MI);
+    }
+}
+
+// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
+// a basic block is removed we would lose the debug information unless we have
+// copied the information to a predecessor/successor.
+//
+// TODO: This function only handles some simple cases. An alternative would be
+// to run a heavier analysis, such as the LiveDebugValues pass, before we do
+// branch folding.
+static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII,
+                                           MachineBasicBlock &MBB) {
+  assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
+  // If this MBB is the only predecessor of a successor it should be
+  // possible to copy DBG_VALUE instructions to the beginning of the
+  // successor.
+  for (MachineBasicBlock *SuccBB : MBB.successors())
+    if (SuccBB->pred_size() == 1)
+      copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
+  // If this MBB is the only successor of a predecessor it should be
+  // possible to copy the DBG_VALUE instructions to the end of the
+  // predecessor (just before the terminators, assuming that the
+  // terminator isn't affecting the DBG_VALUE).
+  for (MachineBasicBlock *PredBB : MBB.predecessors())
+    if (PredBB->succ_size() == 1)
+      copyDebugInfoToPredecessor(TII, MBB, *PredBB);
+}
+
 bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
   bool MadeChange = false;
   MachineFunction &MF = *MBB->getParent();
 ReoptimizeBlock:
 
   MachineFunction::iterator FallThrough = MBB->getIterator();
   ++FallThrough;
 
   // Make sure MBB and FallThrough belong to the same funclet.
   bool SameFunclet = true;
   if (!FuncletMembership.empty() && FallThrough != MF.end()) {
     auto MBBFunclet = FuncletMembership.find(MBB);
     assert(MBBFunclet != FuncletMembership.end());
     auto FallThroughFunclet = FuncletMembership.find(&*FallThrough);
     assert(FallThroughFunclet != FuncletMembership.end());
     SameFunclet = MBBFunclet->second == FallThroughFunclet->second;
   }
 
   // If this block is empty, make everyone use its fall-through, not the block
   // explicitly.  Landing pads should not do this since the landing-pad table
   // points to this block.  Blocks with their addresses taken shouldn't be
   // optimized away.
   if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
       SameFunclet) {
+    salvageDebugInfoFromEmptyBlock(TII, *MBB);
     // Dead block?  Leave for cleanup later.
     if (MBB->pred_empty()) return MadeChange;
 
     if (FallThrough == MF.end()) {
       // TODO: Simplify preds to not branch here if possible!
     } else if (FallThrough->isEHPad()) {
       // Don't rewrite to a landing pad fallthough.  That could lead to the case
       // where a BB jumps to more than one landing pad.

test/DebugInfo/X86/PR37234.ll

+; RUN: llc %s -o - | FileCheck %s
+
+; This test case was generated by running
+;
+;   clang++ -O2 -g PR37234.cpp -S -save-temps
+;   opt -O2 -S PR37234.bc -o PR37234.ll
+;
+; using the following PR37234.cpp program
+;
+;    int main() {
+;            const char* buffer = "aaa";
+;            unsigned aa = 0;
+;            while (char c = *buffer++) {
+;                    if (c == 'a')
+;                            ++aa;  // DexWatch('aa')
+;            }
+;            return aa;
+;    }
+
+
+; CHECK-LABEL: # %bb.{{.*}}:
+; CHECK:        #DEBUG_VALUE: main:aa <- 0
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG:[0-9a-z]+]]
+; CHECK:  jmp .LBB0_1
+; CHECK: .LBB0_3:
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:  incl  %[[REG]]
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK: .LBB0_1:
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:  je  .LBB0_4
+; CHECK: # %bb.{{.*}}:
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:  jne .LBB0_1
+; CHECK:  jmp .LBB0_3
+; CHECK: .LBB0_4:
+; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:  retq
+
+source_filename = "PR37234.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [4 x i8] c"aaa\00", align 1
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define dso_local i32 @main() local_unnamed_addr #0 !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !19
+  br label %while.cond.outer, !dbg !20
+
+while.cond.outer:                                 ; preds = %if.then, %entry
+  %buffer.0.ph = phi i8* [ %incdec.ptr, %if.then ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), %entry ]
+  %aa.0.ph = phi i32 [ %inc, %if.then ], [ 0, %entry ]
+  br label %while.cond, !dbg !21
+
+while.cond:                                       ; preds = %while.cond.outer, %while.cond
+  %buffer.0 = phi i8* [ %incdec.ptr, %while.cond ], [ %buffer.0.ph, %while.cond.outer ], !dbg !22
+  call void @llvm.dbg.value(metadata i32 %aa.0.ph, metadata !16, metadata !DIExpression()), !dbg !19
+  call void @llvm.dbg.value(metadata i8* %buffer.0, metadata !12, metadata !DIExpression()), !dbg !23
+  %incdec.ptr = getelementptr inbounds i8, i8* %buffer.0, i64 1, !dbg !21
+  call void @llvm.dbg.value(metadata i8* %incdec.ptr, metadata !12, metadata !DIExpression()), !dbg !23
+  %0 = load i8, i8* %buffer.0, align 1, !dbg !24, !tbaa !25
+  call void @llvm.dbg.value(metadata i8 %0, metadata !18, metadata !DIExpression()), !dbg !28
+  switch i8 %0, label %while.cond [
+    i8 0, label %while.end
+    i8 97, label %if.then
+  ], !dbg !20
+
+if.then:                                          ; preds = %while.cond
+  %inc = add i32 %aa.0.ph, 1, !dbg !29
+  call void @llvm.dbg.value(metadata i32 %inc, metadata !16, metadata !DIExpression()), !dbg !19
+  br label %while.cond.outer, !dbg !29
+
+while.end:                                        ; preds = %while.cond
+  call void @llvm.dbg.value(metadata i32 %aa.0.ph, metadata !16, metadata !DIExpression()), !dbg !19
+  call void @llvm.dbg.value(metadata i32 %aa.0.ph, metadata !16, metadata !DIExpression()), !dbg !19
+  call void @llvm.dbg.value(metadata i32 %aa.0.ph, metadata !16, metadata !DIExpression()), !dbg !19
+  call void @llvm.dbg.value(metadata i32 %aa.0.ph, metadata !16, metadata !DIExpression()), !dbg !19
+  ret i32 %aa.0.ph, !dbg !32
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+attributes #0 = { norecurse nounwind readonly uwtable }
+attributes #1 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 7.0.0 (trunk 330946) (llvm/trunk 330952)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "PR37234.cpp", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 7.0.0 (trunk 330946) (llvm/trunk 330952)"}
+!7 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 1, type: !8, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !11)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !{!12, !16, !18}
+!12 = !DILocalVariable(name: "buffer", scope: !7, file: !1, line: 2, type: !13)
+!13 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !14, size: 64)
+!14 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !15)
+!15 = !DIBasicType(name: "char", size: 8, encoding: DW_ATE_signed_char)
+!16 = !DILocalVariable(name: "aa", scope: !7, file: !1, line: 3, type: !17)
+!17 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+!18 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 4, type: !15)
+!19 = !DILocation(line: 3, column: 18, scope: !7)
+!20 = !DILocation(line: 4, column: 9, scope: !7)
+!21 = !DILocation(line: 4, column: 32, scope: !7)
+!22 = !DILocation(line: 0, scope: !7)
+!23 = !DILocation(line: 2, column: 21, scope: !7)
+!24 = !DILocation(line: 4, column: 25, scope: !7)
+!25 = !{!26, !26, i64 0}
+!26 = !{!"omnipotent char", !27, i64 0}
+!27 = !{!"Simple C++ TBAA"}
+!28 = !DILocation(line: 4, column: 21, scope: !7)
+!29 = !DILocation(line: 6, column: 25, scope: !30)
+!30 = distinct !DILexicalBlock(scope: !31, file: !1, line: 5, column: 21)
+!31 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 36)
+!32 = !DILocation(line: 9, column: 1, scope: !7)