[LDV][RAGreedy] Inform LiveDebugVariables about new VRegs added by InlineSpiller

[bjope]

Summary

Make sure RAGreedy informs LiveDebugVariables about new VRegs
that is introduced at spill by InlineSpiller.

Consider this example

LDV: !"var" [48r;128r):0 Loc0=%2

48B %2 = ...
...
128B %7 = ADD %2, ...

If %2 is spilled the InlineSpiller will insert spill/reload
instructions and introduces some new vregs. So we get

48B %4 = ...
56B spill %4
...
120B reload %5
128B %3 = ADD %5, ...

In the past we did not inform LDV about this, and when reintroducing
DBG_VALUE instruction LDV still got information that "var" had the
location of the spilled register %2 for the interval [48r;128r).
The result was bad, since we mapped "var" to the spill slot even
before the spill happened:

%4 = ...
DBG_VALUE %spill.0, !"var"
spill %4 to %spill.0
...
reload %5
%3 = ADD %5, ...

This patch will inform LDV about the interval split introduced
due to spilling. So the location map in LDV will become

!"var" [48r;56r):1 [56r;120r):0 [120r;128r):2 Loc0=%2 Loc1=%4 Loc2=%5

And when inserting DBG_VALUE instructions we get

%4 = ...
DBG_VALUE %4, !"var"
spill %4 to %spill.0
DBG_VALUE %spill.0, !"var"
...
reload %5
DBG_VALUE %5, !"var"
%3 = ADD %5, ...

Fixes: https://bugs.llvm.org/show_bug.cgi?id=38899

[jmorse]

Ouch @ this category of error, thanks for the patch.

Looks good with some comment nitpicks inline.

llvm/lib/CodeGen/LiveDebugVariables.cpp

275

Thanks for the refactor!

1097–1098

It's unclear to me whether "then we will" is referring to the desired or undesired behaviour. To my mind the desired behaviour would be described:

"If an old vreg for example is spilled it might have been removed from LIS, in which case we should drop the old vreg from the locations vector"

But I may have missed something.

llvm/test/CodeGen/PowerPC/pr38899-split-register-at-spill.mir

18

Best to drop attributes if we can.

[bjope]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1097–1098

Agree that "will keep" was a bad wording here.

Old behavior was that we did not even update LDV. So in LDV we still had locations referring to the spilled vreg. But when dumping LIS that vreg does not exist any longer. IMHO this is a little bit weird. But it seems like LDV is updated later (by VirtualRegRewriter pass), mapping those old registers to spill slots (I think the VirtRegMap is involved in this).

I've not really changed the way it works to map a no longer existing vreg to a spill slot. This patch only adjusts the SlotIndexes for the old vreg to only cover the intervals where the register is spilled. And then we add intervals for the slots where we have introduced new vregs (just before the spill and after the reload).

I was kind of aiming for documenting that we have references in LDV to registers that have been removed from the code and that can't be looked up in LIS (something that I realized when working on this patch).

Maybe it is possible to do this differently in the future. Somehow letting NewRegs include spill slots, to identify that the old vreg has been spilled already when doing splitRegister/splitLocation.

I'll try to rewrite this comment to avoid the ambiguity related to "then we will". It should be clear that it is the current behavior that is described. So something like this perhaps:

Finally, remove OldLocNo unless it is still used by some interval in the locInts map. One case when OldLocNo still is in use is when the register has been spilled. In such situations the spilled register is kept as a location until rewriteLocations is called (VirtRegMap is mapping the old register to the spill slot). So for awhile we can have locations that map to virtual registers that have been removed from both the MachineFunction and from LiveIntervals.

[bjope]

Addressed review comments.

[jmorse]

LGTM; I wonder whether there are other places in the register allocator that need to notify LDV of what's happening, but I don't know enough about allocators.

[bjope]

In D69584#1727541, @jmorse wrote:

LGTM; I wonder whether there are other places in the register allocator that need to notify LDV of what's happening, but I don't know enough about allocators.

RAGreedy is calling splitRegister is several other places already. This was at least one place in the code where it seemed to be missing (I've kind of quickly browsed through other uses of LiveRangeEdit in RAGreedy and at other places it seemed like we ended up in calls to splitRegister sooner or later). All those calls dates back to 2013 or something (maybe it was 2011), and maybe the call to InlineSpiller here didn't even exist back in those days.

I don't know much about RABasic, but it might have similar problems (at least it got a pass dependency toward LiveDebugVariables). The PR was for RAGreedy so I simply focused on that.

llvm/lib/CodeGen/LiveDebugVariables.cpp

unsigned getLocationNo(const MachineOperand &LocMO) {
     if (locations.back().isReg()) {
       if (locations.back().isDef())
         locations.back().setIsDead(false);
       locations.back().setIsUse();
     }
     return locations.size() - 1;
   }
 
+  /// Remove (recycle) a location number. If \p LocNo still is used by the
+  /// locInts nothing is done.
+  void removeLocationIfUnused(unsigned LocNo) {
+    // Bail out if LocNo still is used.
+    for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
+      DbgValueLocation Loc = I.value();
+      if (Loc.locNo() == LocNo)
+        return;
+    }
+    // Remove the entry in the locations vector, and adjust all references to
+    // location numbers above the removed entry.
+    locations.erase(locations.begin() + LocNo);
+    for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
+      DbgValueLocation Loc = I.value();
+      if (!Loc.isUndef() && Loc.locNo() > LocNo)
+        I.setValueUnchecked(Loc.changeLocNo(Loc.locNo() - 1));
+    }
+  }
+
   /// Ensure that all virtual register locations are mapped.
   void mapVirtRegs(LDVImpl *LDV);
 
   /// Add a definition point to this value.
   void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
     DbgValueLocation Loc(getLocationNo(LocMO));
     // Add a singular (Idx,Idx) -> Loc mapping.
     LocMap::iterator I = locInts.find(Idx);
while (LocMapI.valid() && LII != LIE) {
         ++LocMapI;
         if (!LocMapI.valid())
           break;
         LII = LI->advanceTo(LII, LocMapI.start());
       }
     }
   }
 
-  // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
-  locations.erase(locations.begin() + OldLocNo);
-  LocMapI.goToBegin();
-  while (LocMapI.valid()) {
-    DbgValueLocation v = LocMapI.value();
-    if (v.locNo() == OldLocNo) {
-      LLVM_DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
-                        << LocMapI.stop() << ")\n");
-      LocMapI.erase();
-    } else {
-      // Undef values always have location number UndefLocNo, so don't change
-      // locNo in that case. See getLocationNo().
-      if (!v.isUndef() && v.locNo() > OldLocNo)
-        LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
-      ++LocMapI;
-    }
-  }
+  // Finally, remove OldLocNo unless it is still used by some interval in the
+  // locInts map. One case when OldLocNo still is in use is when the register
+  // has been spilled. In such situations the spilled register is kept as a
+  // location until rewriteLocations is called (VirtRegMap is mapping the old
+  // register to the spill slot). So for a while we can have locations that map
+  // to virtual registers that have been removed from both the MachineFunction
+  // and from LiveIntervals.
+  removeLocationIfUnused(OldLocNo);
 
   LLVM_DEBUG({
     dbgs() << "Split result: \t";
     print(dbgs(), nullptr);
   });
   return DidChange;
 }
 

llvm/lib/CodeGen/RegAllocGreedy.cpp

if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
     NewVRegs.push_back(VirtReg.reg);
   } else {
     NamedRegionTimer T("spill", "Spiller", TimerGroupName,
                        TimerGroupDescription, TimePassesIsEnabled);
     LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
     spiller().spill(LRE);
     setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
 
+    // Tell LiveDebugVariables about the new ranges. Ranges not being covered by
+    // the new regs are kept in LDV (still mapping to the old register), until
+    // we rewrite spilled locations in LDV at a later stage.
+    DebugVars->splitRegister(VirtReg.reg, LRE.regs(), *LIS);
+
     if (VerifyEnabled)
       MF->verify(this, "After spilling");
   }
 
   // The live virtual register requesting allocation was spilled, so tell
   // the caller not to allocate anything during this round.
   return 0;
 }

llvm/test/CodeGen/PowerPC/pr38899-split-register-at-spill.mir

+# RUN: llc -mtriple=powerpc64le-unknown-unknown -start-before=greedy -stop-after=virtregrewriter -o - %s | FileCheck %s
+
+--- |
+  ; Function Attrs: nounwind
+  define signext i32 @test1(i32 signext %a, i32 signext %b) local_unnamed_addr !dbg !8 {
+  entry:
+    %mul = mul nsw i32 %b, %a, !dbg !18
+    call void @llvm.dbg.value(metadata i32 %mul, metadata !15, metadata !DIExpression()), !dbg !19
+    tail call void asm sideeffect "", "~{r0},~{r1},~{r2},~{r3},~{r4},~{r5},~{r6},~{r7},~{r8},~{r9},~{r10},~{r11},~{r12},~{r13},~{r14},~{r15},~{r16},~{r17},~{r18},~{r19},~{r20},~{r21},~{r22},~{r23},~{r24},~{r25},~{r26},~{r27},~{r28},~{r29},~{r30},~{r31}"() #2, !dbg !20, !srcloc !25
+    ret i32 %mul, !dbg !26
+  }
+
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5, !6}
+  !llvm.ident = !{!7}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 8.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+  !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 = !{i32 7, !"PIC Level", i32 2}
+  !7 = !{!"clang version 8.0.0"}
+  !8 = distinct !DISubprogram(name: "test1", scope: !1, file: !1, line: 8, type: !9, scopeLine: 8, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12)
+  !9 = !DISubroutineType(types: !10)
+  !10 = !{!11, !11, !11}
+  !11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !12 = !{!15}
+  !15 = !DILocalVariable(name: "c", scope: !8, file: !1, line: 9, type: !11)
+  !16 = !DILocation(line: 8, column: 14, scope: !8)
+  !17 = !DILocation(line: 8, column: 21, scope: !8)
+  !18 = !DILocation(line: 9, column: 13, scope: !8)
+  !19 = !DILocation(line: 9, column: 7, scope: !8)
+  !20 = !DILocation(line: 2, column: 3, scope: !21, inlinedAt: !24)
+  !21 = distinct !DISubprogram(name: "force_spill", scope: !1, file: !1, line: 1, type: !22, scopeLine: 1, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+  !22 = !DISubroutineType(types: !23)
+  !23 = !{null}
+  !24 = distinct !DILocation(line: 10, column: 3, scope: !8)
+  !25 = !{i32 55}
+  !26 = !DILocation(line: 11, column: 3, scope: !8)
+
+...
+---
+name:            test1
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x3, $x4
+
+    %4:gprc = nsw MULLW $r4, $r3, debug-location !18
+    DBG_VALUE %4, $noreg, !15, !DIExpression(), debug-location !19
+    INLINEASM &"", 1, 12, implicit-def dead early-clobber $r0, 12, implicit-def early-clobber $r1, 12, implicit-def early-clobber $r2, 12, implicit-def dead early-clobber $r3, 12, implicit-def dead early-clobber $r4, 12, implicit-def dead early-clobber $r5, 12, implicit-def dead early-clobber $r6, 12, implicit-def dead early-clobber $r7, 12, implicit-def dead early-clobber $r8, 12, implicit-def dead early-clobber $r9, 12, implicit-def dead early-clobber $r10, 12, implicit-def dead early-clobber $r11, 12, implicit-def dead early-clobber $r12, 12, implicit-def early-clobber $r13, 12, implicit-def dead early-clobber $r14, 12, implicit-def dead early-clobber $r15, 12, implicit-def dead early-clobber $r16, 12, implicit-def dead early-clobber $r17, 12, implicit-def dead early-clobber $r18, 12, implicit-def dead early-clobber $r19, 12, implicit-def dead early-clobber $r20, 12, implicit-def dead early-clobber $r21, 12, implicit-def dead early-clobber $r22, 12, implicit-def dead early-clobber $r23, 12, implicit-def dead early-clobber $r24, 12, implicit-def dead early-clobber $r25, 12, implicit-def dead early-clobber $r26, 12, implicit-def dead early-clobber $r27, 12, implicit-def dead early-clobber $r28, 12, implicit-def dead early-clobber $r29, 12, implicit-def dead early-clobber $r30, 12, implicit-def early-clobber $r31, !25, debug-location !20
+    %5:g8rc = EXTSW_32_64 %4, debug-location !26
+    $x3 = COPY %5, debug-location !26
+    BLR8 implicit $lr8, implicit $rm, implicit $x3, debug-location !26
+
+...
+
+# Verify that we get three DBG_VALUE instructions. One between the MULLW and
+# the spill, one between the spill and reload, and one after the reload.
+#
+# CHECK-LABEL: name:            test1
+# CHECK:         renamable [[REG1:\$r[0-9]+]] = nsw MULLW
+# CHECK-NEXT:    DBG_VALUE [[REG1]], $noreg, [[VAR:![0-9]+]], !DIExpression(),
+# CHECK-NEXT:    STW killed renamable [[REG1]], 0, %stack.0 ::
+# CHECK-NEXT:    DBG_VALUE %stack.0, 0, [[VAR]], !DIExpression(),
+# CHECK-NEXT:    INLINEASM
+# CHECK-NEXT:    renamable [[REG2:\$r[0-9]+]] = LWZ 0, %stack.0,
+# CHECK-NEXT:    DBG_VALUE [[REG2]], $noreg, [[VAR]], !DIExpression(),
+# CHECK-NEXT:    EXTSW_32_64 killed renamable [[REG2]],