[DebugInfo] Re-instate scope trimming in LiveDebugVariables

[jmorse]

Summary

In D62650 / rL362750, Alexey removed some code that trimmed the beginning range of variable locations, as this was accidentally cutting ranges too far. At the time, no-one could think up a good reason for it to continue existing. However, we've since run across an (internal) example of where this trimming is necessary:

• Have a massive basic block in a global constructor, with lots of functions inlined into it,
• Somewhat due to PR41583 [0], SelectionDAG places large volumes of DBG_VALUEs at the start of the block, almost all out of their lexical scope,
• LiveDebugVariables ends up trying to track every variable (including all inlined) for every instruction in the block,

The net effect of which is that a (large) 24,000 instruction block gets expanded to 770,000 instructions, mostly DBG_VALUEs. This ends up swallowing huge amounts of compile time, for variable locations that are all out of scope. With this patch applied to re-instate the trimming, this blow-up does not occur, and variables are only tracked inside their lexical scope.

To address the fault Alexey encountered, I've added a clause that, if a variable location starts at the first instruction of a block, uses the block-start SlotIndex instead of the instructions SlotIndex. Consider the example in the regression test from D62650, where before regalloc in the loop we have:

512B    bb.2.for.body:
        ; predecessors: %bb.0, %bb.2
          successors: %bb.1(0x04000000), %bb.2(0x7c000000); %bb.1(3.12%), %bb.2(96.88%)

          DBG_VALUE somethingorother
544B      STRWroX %38:gpr32, %36:gpr64common, %35:gpr64common, 0, 1, debug-location !50 :: (store 4 into %ir.scevgep); test_debug_val.cpp:16:17

In the faulty behaviour, a DBG_VALUE before the STRWroX would attach itself to the SlotIndex 544B, and then after regalloc we would see:

512B    bb.2.for.body:
        ; predecessors: %bb.0, %bb.2
          successors: %bb.1(0x04000000), %bb.2(0x7c000000); %bb.1(3.12%), %bb.2(96.88%)

520B      %36:gpr64common = MOVaddr target-flags(aarch64-page) @array, target-flags(aarch64-pageoff, aarch64-nc) @array, debug-location !50; test_debug_val.cpp:16:17
524B      %38:gpr32 = MOVi32imm 56, debug-location !50; test_debug_val.cpp:16:17
          DBG_VALUE somethingorother
544B      STRWroX %38:gpr32, %36:gpr64common, %35:gpr64common, 0, 1, debug-location !50 :: (store 4 into %ir.scevgep); test_debug_val.cpp:16:17

The DBG_VALUE would be placed before the STRWroX, and despite being at the start of the block pre-regalloc, would not be afterwards, meaning a debugger stepping into this block would not see this location.

My fix for this moves any variable location pointing at 544B (i.e. the first instruction) to 512B, the block start. That way anything inserted during regalloc is covered by the DBG_VALUE.

I haven't added a test (does LLVM have compile-time performance testing?), my proof that this works is that Alexeys regression test keeps on working. The change to live-debug-variables.ll is because a location list is trimmed to not cover the prologue of a function.

[0] https://bugs.llvm.org/show_bug.cgi?id=41583

[jmorse]

llvm/lib/CodeGen/LiveDebugVariables.cpp

921

^^^ this hunk is my addition, everything else here is a revert of D62650

[avl]

@jmorse this lgtm for me. Thank you for doing it right.

[vsk]

Seems reasonable to me, but I don’t have much experience in this area. Orlando has looked at this more recently and is probably more qualified to review ;)

We (llvm) used to have bots tracking CTMark performance but they’ve been dead for a while, I think. I run CTMark through llvm-test-suite all the time though and find it quite useful.

[Orlando]

Orlando has looked at this more recently and is probably more qualified to review ;)

Ha I'm not sure about that, but as far as I understand what's going on here this looks good.

llvm/lib/CodeGen/LiveDebugVariables.cpp

class UserValue {
   UserValue *next = nullptr; ///< 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;
+
   /// Insert a DBG_VALUE into MBB at Idx for LocNo.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
                         SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
                         unsigned SpillOffset, LiveIntervals &LIS,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI);
 
   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
void UserValue::computeIntervals(MachineRegisterInfo &MRI,
   // 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);
 
+    // Variable locations at the first instruction of a block should be
+    // based on the block's SlotIndex, not the first instruction's index.
+    if (Range.first == Range.first->getParent()->begin())
+      RStart = LIS.getSlotIndexes()->getIndexBefore(*Range.first);
+
     // 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();
       DbgValueLocation Loc = 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
+      // current) range create a new interval for the remainder (which
+      // may be further trimmed).
       if (RStart < IStop)
         I.insert(RStart, IStop, Loc);
     }
 
     // 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())
for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
     SlotIndex Start = I.start();
     SlotIndex Stop = I.stop();
     DbgValueLocation Loc = I.value();
     auto SpillIt =
         !Loc.isUndef() ? SpillOffsets.find(Loc.locNo()) : SpillOffsets.end();
     bool Spilled = SpillIt != SpillOffsets.end();
     unsigned SpillOffset = Spilled ? SpillIt->second : 0;
 
+    // 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();
+
     LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
 
     LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
     insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
                      TRI);
     // This interval may span multiple basic blocks.

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

 ;          F(a,b,c,d,e) +
 ;          F(a,b,c,d,e) +
 ;          F(a,b,c,d,e);
 ; }
 
 ; CHECK:      .debug_loc contents:
 ; CHECK-NEXT: 0x00000000:
 ;   We currently emit an entry for the function prologue, too, which could be optimized away.
-; CHECK:              (0x0000000000000010, 0x0000000000000072): DW_OP_reg3 RBX
+; CHECK:              (0x0000000000000018, 0x0000000000000072): DW_OP_reg3 RBX
 ;   We should only have one entry inside the function.
 ; CHECK-NOT: :
 
 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