[LiveDebugValues] Extend var ranges through artificial blocks

[vsk]

Summary

ASan often introduces basic blocks consisting exclusively of
instructions without debug locations, or with line 0 debug locations.

LiveDebugValues needs to extend variable ranges through these artificial
blocks. Otherwise, a lot of variables disappear -- even at -O0.

Typically, LiveDebugValues does not extend a variable's range into a
block unless the block is essentially "part of" the variable's scope
(for a precise definition, see LexicalScopes::dominates). This patch
relaxes the lexical dominance check for artificial blocks.

This makes the following Swift program debuggable at -O0:

1| var x = 100
2| print("x = \(x)")

rdar://39127144

[NikolaPrica]

Looks good to me. Just one question, why didn't you use MIR as test file?

[aprantl]

Good find! We spent a considerable amount of time tweaking the performance of this pass. Before the scope checking was added functions would often have thousands of dead dbg.values inserted.

May I ask you to do a time ninja clang of both an ASANified/UBSANified clang and a RelWithDebInfo clang to make sure this doesn't regress performance? It would also be good to spot-check the memory usage (but runtime is likely a good proxy).

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

772

For readability I think I would prefer this to be in a separate collect/initCompilerGeneratedBlocks helper function.

[vsk]

Address review feedback.

• @NikolaPrica The MIR parser has bugs causing it to be extremely sensitive around comments. I couldn't write a reasonable a set of CHECK lines the MIR parser would accept.
• Split out logic to label artificial blocks from the initialization step.

[vsk]

@aprantl I built stage2 ASan+UBsan+RelWithDebInfo versions of clang with unpatched and patched versions of clang.

The unpatched clang finished in 936 seconds with a peak RSS of 999,268 KB (0.95 GB). The patched clang finished in 853 seconds with a peak RSS of 999,952 KB (0.95 GB). I made measurements by sampling ps x -o rss,command | grep clang every second and keeping track of the entry with max RSS. I can share the measurement script if there’s interest.

I’m confident that these measurements show this patch doesn’t cause unbounded memory consumption. I don’t know what we can say about the compile-time impact due to the low sample size (2 builds). However, I expect compile times to improve. Instead of spending time re-checking instruction locations in LexicalScopes::dominates(), this patch just does a set lookup.

I looked at the final dSYMs to see what happens to the debug info. This patch increases the percentage of scope bytes covered by 1% (expected). It doesn’t really increase the number of variables with locations (also expected; their ranges simply grow).

[aprantl]

Thanks, looks like we didn't accidentally introduce a regression!

llvm/lib/CodeGen/LiveDebugValues.cpp

#endif
   bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
   bool process(MachineInstr &MI, OpenRangesSet &OpenRanges,
                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
                TransferMap &Transfers, bool transferChanges);
 
   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
             const VarLocMap &VarLocIDs,
-            SmallPtrSet<const MachineBasicBlock *, 16> &Visited);
+            SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
+            SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
 
   bool ExtendRanges(MachineFunction &MF);
 
 public:
   static char ID;
 
   /// Default construct and initialize the pass.
   LiveDebugValues();
bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
   }
   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
   return Changed;
 }
 
 /// This routine joins the analysis results of all incoming edges in @MBB by
 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 /// source variable in all the predecessors of @MBB reside in the same location.
-bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
-                           VarLocInMBB &InLocs, const VarLocMap &VarLocIDs,
-                           SmallPtrSet<const MachineBasicBlock *, 16> &Visited) {
+bool LiveDebugValues::join(
+    MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
+    const VarLocMap &VarLocIDs,
+    SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
+    SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
   bool Changed = false;
 
   VarLocSet InLocsT; // Temporary incoming locations.
 
   // For all predecessors of this MBB, find the set of VarLocs that
   // can be joined.
   int NumVisited = 0;
LLVM_DEBUG({
       }
     });
 
     NumVisited++;
   }
 
   // Filter out DBG_VALUES that are out of scope.
   VarLocSet KillSet;
+  bool IsArtificial = ArtificialBlocks.count(&MBB);
+  if (!IsArtificial) {
     for (auto ID : InLocsT) {
       if (!VarLocIDs[ID].dominates(MBB)) {
         KillSet.set(ID);
         LLVM_DEBUG({
           auto Name = VarLocIDs[ID].Var.getVar()->getName();
           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
         });
       }
     }
+  }
   InLocsT.intersectWithComplement(KillSet);
 
   // As we are processing blocks in reverse post-order we
   // should have processed at least one predecessor, unless it
   // is the entry block which has no predecessor.
   assert((NumVisited || MBB.pred_empty()) &&
          "Should have processed at least one predecessor");
   if (InLocsT.empty())
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   bool MBBJoined = false;
 
   VarLocMap VarLocIDs;      // Map VarLoc<>unique ID for use in bitvectors.
   OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;      // Ranges that exist beyond bb.
   VarLocInMBB InLocs;       // Ranges that are incoming after joining.
   TransferMap Transfers;    // DBG_VALUEs associated with spills.
 
+  // Blocks which are artificial, i.e. blocks which exclusively contain
+  // instructions without locations, or with line 0 locations.
+  SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
+
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Pending;
 
   enum : bool { dontTransferChanges = false, transferChanges = true };
 
   // Initialize every mbb with OutLocs.
   // We are not looking at any spill instructions during the initial pass
   // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
   // instructions for spills of registers that are known to be user variables
   // within the BB in which the spill occurs.
   for (auto &MBB : MF)
     for (auto &MI : MBB)
       process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
               dontTransferChanges);
 
+  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
+    if (const DebugLoc &DL = MI.getDebugLoc())
+      return DL.getLine() != 0;
+    return false;
+  };
+  for (auto &MBB : MF)
+    if (none_of(MBB.instrs(), hasNonArtificialLocation))
+      ArtificialBlocks.insert(&MBB);
+
   LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
                               "OutLocs after initialization", dbgs()));
 
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   unsigned int RPONumber = 0;
   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
     OrderToBB[RPONumber] = *RI;
     BBToOrder[*RI] = RPONumber;
while (!Worklist.empty() || !Pending.empty()) {
     // We track what is on the pending worklist to avoid inserting the same
     // thing twice.  We could avoid this with a custom priority queue, but this
     // is probably not worth it.
     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
     while (!Worklist.empty()) {
       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
       Worklist.pop();
-      MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited);
+      MBBJoined =
+          join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks);
       Visited.insert(MBB);
       if (MBBJoined) {
         MBBJoined = false;
         Changed = true;
         // Now that we have started to extend ranges across BBs we need to
         // examine spill instructions to see whether they spill registers that
         // correspond to user variables.
         for (auto &MI : *MBB)

llvm/test/DebugInfo/AArch64/compiler-gen-bbs-livedebugvalues.ll

+; RUN: llc -O0 -regalloc=fast -stop-after=livedebugvalues -o - < %s | \
+; RUN:   FileCheck %s -implicit-check-not=DBG_VALUE
+
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+target triple = "arm64-apple-ios12.1.0"
+
+declare void @use(i32 %x)
+
+define void @f1(i32 %x) !dbg !6 {
+; CHECK-LABEL: name: f1
+entry:
+; CHECK-LABEL: bb.0.entry:
+  %var = add i32 %x, 1, !dbg !12
+  call void @llvm.dbg.value(metadata i32 %var, metadata !9, metadata !DIExpression()), !dbg !12
+; CHECK: DBG_VALUE debug-use renamable $w0, debug-use $noreg, !9, !DIExpression(), debug-location !12
+; CHECK-NEXT: STRWui killed $w0, $sp, 3 :: (store 4 into %stack.0)
+; CHECK-NEXT: DBG_VALUE debug-use $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
+
+  br label %artificial-bb-1, !dbg !13
+
+artificial-bb-1:                                  ; preds = %entry
+; CHECK-LABEL: bb.1.artificial-bb-1:
+; CHECK: DBG_VALUE debug-use $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
+
+  br label %artificial-bb-2
+
+artificial-bb-2:                                  ; preds = %artificial-bb-1
+; CHECK-LABEL: bb.2.artificial-bb-2:
+; CHECK: DBG_VALUE debug-use $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
+
+  %invisible = add i32 %var, 1
+  br label %return, !dbg !14
+
+return:                                           ; preds = %artificial-bb-2
+; CHECK-LABEL: bb.3.return:
+; CHECK: DBG_VALUE debug-use $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
+
+  call void @use(i32 %var)
+  ret void, !dbg !15
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.debugify = !{!3, !4}
+!llvm.module.flags = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "compiler-gen-bbs-livedebugvalues.ll", directory: "/")
+!2 = !{}
+!3 = !{i32 6}
+!4 = !{i32 2}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = distinct !DISubprogram(name: "f1", linkageName: "f1", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !8)
+!7 = !DISubroutineType(types: !2)
+!8 = !{!9, !11}
+!9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10)
+!10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_unsigned)
+!11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 4, type: !10)
+!12 = !DILocation(line: 1, column: 1, scope: !6)
+!13 = !DILocation(line: 2, column: 1, scope: !6)
+!14 = !DILocation(line: 0, column: 1, scope: !6)
+!15 = !DILocation(line: 4, column: 1, scope: !6)