[LiveDebugVariables] Use lexical scope to trim debug value live intervals

[rob.lougher]

Summary

This is a fix for PR33730.

The following program causes Live Debug Variables to emit unnecessary debug values:

extern int foobar(int, int, int, int, int);

int F(int i1, int i2, int i3, int i4, int i5) {
  return foobar(i1, i2, i3, i4, i5);
}

int foo(int a, int b, int c, int d, int e) {
  return F(a,b,c,d,e) +
         F(a,b,c,d,e) +
         F(a,b,c,d,e) +
         F(a,b,c,d,e);
}

$ clang foo.c -c -O2 -g -emit-llvm
$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 8:10

		DBG_VALUE %EBX, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:8:10 ]
		DBG_VALUE <fi#2>, 0, !"i4", <!17>; line no:3 inlined @[ foo.c:8:10 ]
		DBG_VALUE %EBP, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:8:10 ]

According to this the first inlined "i4" parameter is in 3 registers (in fact, on entry it is only in %EBX). This can also be seen in the DWARF output, where the debug location ends up with 3 entries:

0x00000110:     DW_TAG_inlined_subroutine [9] *
                  DW_AT_abstract_origin [DW_FORM_ref4]	(cu + 0x0061 => {0x00000061} "F")
                  DW_AT_low_pc [DW_FORM_addr]	(0x000000000000002f)
                  DW_AT_high_pc [DW_FORM_data4]	(0x00000009)
                  DW_AT_call_file [DW_FORM_data1]	("foo.c")
                  DW_AT_call_line [DW_FORM_data1]	(8)

0x0000013e:       DW_TAG_formal_parameter [10]  
                    DW_AT_location [DW_FORM_sec_offset]	(0x00000312)
                    DW_AT_abstract_origin [DW_FORM_ref4]	(cu + 0x008e => {0x0000008e} "i4")
...
.debug_loc contents:
...
0x00000312: Beginning address offset: 0x000000000000002f
               Ending address offset: 0x0000000000000046
                Location description: 53 

            Beginning address offset: 0x0000000000000046
               Ending address offset: 0x0000000000000065
                Location description: 77 0c 

            Beginning address offset: 0x0000000000000065
               Ending address offset: 0x000000000000009a
                Location description: 56

Similarly, "i4"s debug value for the second, third and fourth inlining also show the same 3 DBG_VALUES:

$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 9:10

		DBG_VALUE %EBX, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:9:10 ]
		DBG_VALUE <fi#2>, 0, !"i4", <!17>; line no:3 inlined @[ foo.c:9:10 ]
		DBG_VALUE %EBP, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:9:10 ]
...

The problem is caused by the live intervals assigned to the debug values by Live Debug Variables. All four inlined debug values for "i4" share the same virtual register. The live interval spans all the inlined callsites, although each inlined instance accounts for only a region of the full range. The register allocator later splits the virtual register, and as each debug value is associated with the entire live range they are also split, creating a number of intervals per value. Later, debug values are emitted for each of the intervals, although most of the intervals are outside the inlined instance.

Splitting of the debug values can also create a compile-time explosion. If the above program is modified to create 1500 inlined calls, the program takes over 40 minutes to compile with -g (3.5 GHz Core-i7) and Live Debug Variables inserts over 6 million DBG_VALUEs (see PR33730 for further details).

This patch fixes the problem by using the lexical scope of the inlined debug locations to "trim" the debug value live intervals. After this we generate a single debug value:

$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 8:10

		DBG_VALUE %EBX, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:8:10 ]

The DWARF also now contains a single entry in the debug location:

0x00000110:     DW_TAG_inlined_subroutine [9] *
                  DW_AT_abstract_origin [DW_FORM_ref4]	(cu + 0x0061 => {0x00000061} "F")
                  DW_AT_low_pc [DW_FORM_addr]	(0x000000000000002f)
                  DW_AT_high_pc [DW_FORM_data4]	(0x00000009)
                  DW_AT_call_file [DW_FORM_data1]	("foo.c")
                  DW_AT_call_line [DW_FORM_data1]	(8)

                    DW_AT_location [DW_FORM_sec_offset]	(0x0000017f)
                    DW_AT_abstract_origin [DW_FORM_ref4]	(cu + 0x008e => {0x0000008e} "i4")
...
.debug_loc contents:
...
0x0000017f: Beginning address offset: 0x000000000000002f
               Ending address offset: 0x000000000000004c
                Location description: 53

The other inlined debug values for "i4" now also show the correct values:

$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 9:10

		DBG_VALUE %EBX, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:9:10 ]
		DBG_VALUE <fi#2>, 0, !"i4", <!17>; line no:3 inlined @[ foo.c:9:10 ]

$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 10:10

		DBG_VALUE <fi#2>, 0, !"i4", <!17>; line no:3 inlined @[ foo.c:10:10 ]
		DBG_VALUE %EBP, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:10:10 ]

$ llc foo.bc -print-after virtregrewriter 2>&1 | grep DBG_VALUE | grep i4 | grep 11:10

		DBG_VALUE %EBP, %noreg, !"i4", <!17>; line no:3 inlined @[ foo.c:11:10 ]

[aprantl]

lib/CodeGen/LiveDebugVariables.cpp

692 ↗

(On Diff #108492)

I would personally prefer a short summary of the problem over a reference to a PR.

[aprantl]

lib/CodeGen/LiveDebugVariables.cpp

107 ↗

(On Diff #108492)

///

694 ↗

(On Diff #108492)

Why only do this for inlined variables? Couldn't non-inlined variables also benefit from being trimmed at their lexical scope's end? Or is this situation impossible for non-inlined variables?

704 ↗

(On Diff #108492)

Can you add a high-level comment here what the loop is doing?

[probinson]

lib/CodeGen/LiveDebugVariables.cpp

25 ↗

(On Diff #108492)

Not in alphabetical order.

32 ↗

(On Diff #108492)

Not in alphabetical order.

[aprantl]

lib/CodeGen/LiveDebugVariables.cpp

707 ↗

(On Diff #108492)

could you run the patch through clang-format?

[rob.lougher]

Address review comments. Now enabled for non-inlined variables. This required fixing a test to make it more resilient (it checks that we get the expected number of debug values, but was also enforcing a specific order). I've also changed where the LexicalScopes are generated, as they're only needed when computing the intervals.

[aprantl]

Small nitpick on the test, but otherwise this looks good now, thanks!

test/DebugInfo/X86/live-debug-variables.ll

24 ↗

(On Diff #109160)

If you are only checking for i4, why are all the other dbg.values necessary? I would expect that we either check for them, too, or that we can remove them to keep the test simple.

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

 // Allow the data structure to be updated during register allocation when values
 // are moved between registers and stack slots. Finally emit new DBG_VALUE
 // instructions after register allocation is complete.
 //
 //===----------------------------------------------------------------------===//
 
 #include "LiveDebugVariables.h"
 #include "llvm/ADT/IntervalMap.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LexicalScopes.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/IR/Constants.h"
class UserValue {
   UserValue *next;        ///< Next value in equivalence class, or null.
 
   /// Numbered locations referenced by locmap.
   SmallVector<MachineOperand, 4> locations;
 
   /// Map of slot indices where this value is live.
   LocMap locInts;
 
+  /// Set of interval start indexes that have been trimmed to the
+  /// lexical scope.
+  SmallSet<SlotIndex, 2> trimmedDefs;
+
   /// coalesceLocation - After LocNo was changed, check if it has become
   /// identical to another location, and coalesce them. This may cause LocNo or
   /// a later location to be erased, but no earlier location will be erased.
   void coalesceLocation(unsigned LocNo);
 
   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
                         LiveIntervals &LIS, const TargetInstrInfo &TII);
void addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
                       const SmallVectorImpl<SlotIndex> &Kills,
                       SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
                       MachineRegisterInfo &MRI,
                       LiveIntervals &LIS);
 
   /// computeIntervals - Compute the live intervals of all locations after
   /// collecting all their def points.
   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
-                        LiveIntervals &LIS);
+                        LiveIntervals &LIS, LexicalScopes &LS);
 
   /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
   /// live. Returns true if any changes were made.
   bool splitRegister(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
   /// rewriteLocations - Rewrite virtual register locations according to the
   /// provided virtual register map.
for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
       I.insert(Idx, Idx.getNextSlot(), LocNo);
       NewDefs.push_back(std::make_pair(Idx, LocNo));
       break;
     }
   }
 }
 
-void
-UserValue::computeIntervals(MachineRegisterInfo &MRI,
+void UserValue::computeIntervals(MachineRegisterInfo &MRI,
                                  const TargetRegisterInfo &TRI,
-                            LiveIntervals &LIS) {
+                                 LiveIntervals &LIS, LexicalScopes &LS) {
   SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
 
   // Collect all defs to be extended (Skipping undefs).
   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
     if (I.value() != ~0u)
       Defs.push_back(std::make_pair(I.start(), I.value()));
 
   // Extend all defs, and possibly add new ones along the way.
for (unsigned i = 0; i != Defs.size(); ++i) {
     // For physregs, use the live range of the first regunit as a guide.
     unsigned Unit = *MCRegUnitIterator(Loc.getReg(), &TRI);
     LiveRange *LR = &LIS.getRegUnit(Unit);
     const VNInfo *VNI = LR->getVNInfoAt(Idx);
     // Don't track copies from physregs, it is too expensive.
     extendDef(Idx, LocNo, LR, VNI, nullptr, LIS);
   }
 
-  // Finally, erase all the undefs.
+  // Erase all the undefs.
   for (LocMap::iterator I = locInts.begin(); I.valid();)
     if (I.value() == ~0u)
       I.erase();
     else
       ++I;
+
+  // The computed intervals may extend beyond the range of the debug
+  // location's lexical scope. In this case, splitting of an interval
+  // can result in an interval outside of the scope being created,
+  // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
+  // this, trim the intervals to the lexical scope.
+
+  LexicalScope *Scope = LS.findLexicalScope(dl);
+  if (!Scope)
+    return;
+
+  SlotIndex PrevEnd;
+  LocMap::iterator I = locInts.begin();
+
+  // Iterate over the lexical scope ranges. Each time round the loop
+  // we check the intervals for overlap with the end of the previous
+  // range and the start of the next. The first range is handled as
+  // a special case where there is no PrevEnd.
+  for (const InsnRange &Range : Scope->getRanges()) {
+    SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
+    SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
+
+    // At the start of each iteration I has been advanced so that
+    // I.stop() >= PrevEnd. Check for overlap.
+    if (PrevEnd && I.start() < PrevEnd) {
+      SlotIndex IStop = I.stop();
+      unsigned LocNo = I.value();
+
+      // Stop overlaps previous end - trim the end of the interval to
+      // the scope range.
+      I.setStopUnchecked(PrevEnd);
+      ++I;
+
+      // If the interval also overlaps the start of the "next" (i.e.
+      // current) range create a new interval for the remainder (which
+      // may be further trimmed).
+      if (RStart < IStop)
+        I.insert(RStart, IStop, LocNo);
+    }
+
+    // Advance I so that I.stop() >= RStart, and check for overlap.
+    I.advanceTo(RStart);
+    if (!I.valid())
+      return;
+
+    if (I.start() < RStart) {
+      // Interval start overlaps range - trim to the scope range.
+      I.setStartUnchecked(RStart);
+      // Remember that this interval was trimmed.
+      trimmedDefs.insert(RStart);
+    }
+
+    // The end of a lexical scope range is the last instruction in the
+    // range. To convert to an interval we need the index of the
+    // instruction after it.
+    REnd = REnd.getNextIndex();
+
+    // Advance I to first interval outside current range.
+    I.advanceTo(REnd);
+    if (!I.valid())
+      return;
+
+    PrevEnd = REnd;
+  }
+
+  // Check for overlap with end of final range.
+  if (PrevEnd && I.start() < PrevEnd)
+    I.setStopUnchecked(PrevEnd);
 }
 
 void LDVImpl::computeIntervals() {
+  LexicalScopes LS;
+  LS.initialize(*MF);
+
   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
-    userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS);
+    userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
     userValues[i]->mapVirtRegs(this);
   }
 }
 
 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
   clear();
   MF = &mf;
   LIS = &pass.getAnalysis<LiveIntervals>();

 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
                                 const TargetInstrInfo &TII) {
   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 
   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
     SlotIndex Start = I.start();
     SlotIndex Stop = I.stop();
     unsigned LocNo = I.value();
+
+    // If the interval start was trimmed to the lexical scope insert the
+    // DBG_VALUE at the previous index (otherwise it appears after the
+    // first instruction in the range).
+    if (trimmedDefs.count(Start))
+      Start = Start.getPrevIndex();
+
     DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
 
     DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
     insertDebugValue(&*MBB, Start, LocNo, LIS, TII);
     // This interval may span multiple basic blocks.
     // Insert a DBG_VALUE into each one.

llvm/trunk/test/DebugInfo/X86/dbg-value-dag-combine.ll

 ; RUN: llc < %s | FileCheck %s
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32"
 target triple = "i686-apple-darwin"
 ; PR 9817
 
 ; There should be a DEBUG_VALUE for each call to llvm.dbg.value
 
-; CHECK:  ##DEBUG_VALUE: __OpenCL_test_kernel:ip <- 
-; CHECK:  ##DEBUG_VALUE: xxx <- 0
-; CHECK:  ##DEBUG_VALUE: gid <- %E{{..$}}
-; CHECK:  ##DEBUG_VALUE: idx <- %E{{..$}}
+; CHECK-LABEL: __OpenCL_test_kernel:
+; CHECK-DAG:  ##DEBUG_VALUE: __OpenCL_test_kernel:ip <- 
+; CHECK-DAG:  ##DEBUG_VALUE: xxx <- 0
+; CHECK-DAG:  ##DEBUG_VALUE: gid <- %E{{..$}}
+; CHECK-DAG:  ##DEBUG_VALUE: idx <- %E{{..$}}
 ; CHECK-NOT:  ##DEBUG_VALUE:
 
 declare <4 x i32> @__amdil_get_global_id_int()
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 define void @__OpenCL_test_kernel(i32 addrspace(1)* %ip) nounwind !dbg !0 {
 entry:
   call void @llvm.dbg.value(metadata i32 addrspace(1)* %ip, metadata !7, metadata !DIExpression()), !dbg !8
   %0 = call <4 x i32> @__amdil_get_global_id_int() nounwind

llvm/trunk/test/DebugInfo/X86/live-debug-variables.ll

+; RUN: llc -mtriple=x86_64-linux-gnu -filetype=obj -o - %s | llvm-dwarfdump -debug-dump=loc - | FileCheck %s
+
+; The test inlines the function F four times, with each inlined variable for
+; "i4" sharing the same virtual register. This means the live interval of the
+; register spans all of the inlined callsites, extending beyond the lexical
+; scope of each. Later during register allocation the live interval is split
+; into multiple intervals. Check that this does not generate multiple entries
+; within the debug location (see PR33730).
+;
+; Generated from:
+;
+; extern int foobar(int, int, int, int, int);
+; 
+; int F(int i1, int i2, int i3, int i4, int i5) {
+;   return foobar(i1, i2, i3, i4, i5);
+; }
+; 
+; int foo(int a, int b, int c, int d, int e) {
+;   return F(a,b,c,d,e) +
+;          F(a,b,c,d,e) +
+;          F(a,b,c,d,e) +
+;          F(a,b,c,d,e);
+; }
+
+; CHECK: Beginning address offset
+; CHECK-NOT: Beginning address offset
+
+declare i32 @foobar(i32, i32, i32, i32, i32)
+
+define i32 @foo(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) !dbg !25 {
+entry:
+  tail call void @llvm.dbg.value(metadata i32 %d, i64 0, metadata !15, metadata !17) #3, !dbg !41
+  %call.i = tail call i32 @foobar(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) #3, !dbg !43
+  %call.i21 = tail call i32 @foobar(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) #3, !dbg !50
+  %add = add nsw i32 %call.i21, %call.i, !dbg !51
+  %call.i22 = tail call i32 @foobar(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) #3, !dbg !58
+  %add3 = add nsw i32 %add, %call.i22, !dbg !59
+  %call.i23 = tail call i32 @foobar(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) #3, !dbg !66
+  %add5 = add nsw i32 %add3, %call.i23, !dbg !67
+  ret i32 %add5, !dbg !68
+}
+
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0 (trunk 308976)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "foo.c", 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 6.0.0 (trunk 308976)"}
+!7 = distinct !DISubprogram(name: "F", scope: !1, file: !1, line: 3, type: !8, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !11)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !10, !10, !10, !10, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !{!15}
+!15 = !DILocalVariable(name: "i4", arg: 4, scope: !7, file: !1, line: 3, type: !10)
+!17 = !DIExpression()
+!25 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 7, type: !8, isLocal: false, isDefinition: true, scopeLine: 7, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !26)
+!26 = !{}
+!38 = distinct !DILocation(line: 8, column: 10, scope: !25)
+!41 = !DILocation(line: 3, column: 35, scope: !7, inlinedAt: !38)
+!43 = !DILocation(line: 4, column: 10, scope: !7, inlinedAt: !38)
+!45 = distinct !DILocation(line: 9, column: 10, scope: !25)
+!50 = !DILocation(line: 4, column: 10, scope: !7, inlinedAt: !45)
+!51 = !DILocation(line: 8, column: 23, scope: !25)
+!53 = distinct !DILocation(line: 10, column: 10, scope: !25)
+!58 = !DILocation(line: 4, column: 10, scope: !7, inlinedAt: !53)
+!59 = !DILocation(line: 9, column: 23, scope: !25)
+!61 = distinct !DILocation(line: 11, column: 10, scope: !25)
+!66 = !DILocation(line: 4, column: 10, scope: !7, inlinedAt: !61)
+!67 = !DILocation(line: 10, column: 23, scope: !25)
+!68 = !DILocation(line: 8, column: 3, scope: !25)