[WebAssembly] Undef invalid DBG_VALUEs after RegColoring

[aheejin]

Summary

After register coalescing, some DBG_VALUEs can have incorrect info.
For example, if a DBG_VALUE has a register operand %0, but it
resides in a live range of %1, it has incorrect info after %0 and
%1 are coalesced. See the comments for more details.

This does not have meaningful changes on our variable debug info
coverage or compilation time, which is good news.

[aheejin]

Fix tests

[aheejin]

Make LLVM_ENABLE_EXPENSIVE_CHECKS work

[dschuff]

llvm/test/DebugInfo/WebAssembly/dbg-value-reg-coloring.mir

56

here's is a question to make sure I understand what's going on:
Because the live ranges of %0 and %1 don't overlap, they get coalesced (let's call the resulting wasm local local0). So if we left the DBG_VALUE in, the DWARF would say that local0 contains the value of %1 here even though it still contains %0. Hence we just undef it out.
Would it also be correct to move the DBG_VALUE down to below (or above?) the CONST instruction that materializes it? would that help in practice or is there usually just another DBG_VALUE for the same value?
I guess if you said this CL doesn't meaningfully move the coverage metric, then the answer is that it it doesn't matter much in practice...

58

why are the NOPs here?

[aheejin]

llvm/test/DebugInfo/WebAssembly/dbg-value-reg-coloring.mir

56

here's is a question to make sure I understand what's going on:
Because the live ranges of %0 and %1 don't overlap, they get coalesced (let's call the resulting wasm local local0). So if we left the DBG_VALUE in, the DWARF would say that local0 contains the value of %1 here even though it still contains %0. Hence we just undef it out.

I'm not sure if I understand what you're asking. I think I made the test confusing by using the same variable for both DBG_VALUEs. I changed it to use different variables now. Anyway, to rewrite the code here,

%0 = CONST_I32 0
DBG_VALUE %0, $noreg, !"var_a", ...
DBG_VALUE %1, $noreg, !"var_b", ...
use %0

DBG_VALUE %1, $noreg, !"var_b", ... means var_b at this point contains whatever %1 contains. That can be anything. We can have %1 = CONST_i32 999 somewhere above. This happens because DBG_VALUEs are not counted as 'uses' in live range analysis, so this DBG_VALUE %1 is not considered to be extending the life range of %1.

And after two regs are coalesced into %0:

%0 = CONST_I32 0
DBG_VALUE %0, $noreg, !"var_a", ...
DBG_VALUE %0, $noreg, !"var_b", ...
use %0

Now var_b contains 0, where it shouldn't. The situation doesn't change even if the two regs are coalesced into %1:

%1 = CONST_I32 0
DBG_VALUE %1, $noreg, !"var_a", ...
DBG_VALUE %1, $noreg, !"var_b", ...
use %1

var_b (incorrectly) contains 0 here too. So what I'm trying to do here is, if a DBG_VALUE has a register, let's say, %a, as its operand, and if %a and %b are coalesced, and if that DBG_VALUE is within %b's live range, it should be undefed. (It can't be both within %a and %b's live ranges, which means two registers' live ranges overlap, in which case they wouldn't have been selected as a coalescing candidates.)

Would it also be correct to move the DBG_VALUE down to below (or above?)

LLVM's DBG_VALUE update guideline recommends against moving DBG_VALUEs (https://llvm.org/docs/SourceLevelDebugging.html#instruction-scheduling) in order not to reorder assignment orders. One exception is when we sink a value, we can sink its DBG_VALUEs with it, but we should leave the original DBG_VALUE in place with its register set to undef. We do that here in WebAssemblyDebugValueManager, which is used in RegStackify: https://github.com/llvm/llvm-project/blob/c1fe1474d27f6fe7b8e5bfedcc9066e9a90ad85e/llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.cpp#L295-L335
But I don't think what we do in RegColoring qualifies for sinking or hoisting anyway.

the CONST instruction that materializes it? would that help in practice or is there usually just another DBG_VALUE for the same value?
I guess if you said this CL doesn't meaningfully move the coverage metric, then the answer is that it it doesn't matter much in practice...

We can consider rematerializing certain trivially rematerializable instructions as you suggested, like CONST_s, but I doubt it will matter much in practice, given that this doesn't really negatively affect Emscripten benchmark (-O1)'s coverage much.

58

Just to make it easier to read, in the way that above the NOP is %0's live range, below it is %1's live range. Deleting it doesn't change the test results (other than the NOP itself).

[aheejin]

Use different variables for different regs

[aheejin]

Gentle ping 😀

[dschuff]

oops sorry, LGTM, thanks for the explanation

llvm/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp

static float computeWeight(const MachineRegisterInfo *MRI,
                            unsigned VReg) {
   float Weight = 0.0f;
   for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg))
     Weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI,
                                             *MO.getParent());
   return Weight;
 }
 
+// Create a map of "Register -> vector of <SlotIndex, DBG_VALUE>".
+// The SlotIndex is the slot index of the next non-debug instruction or the end
+// of a BB, because DBG_VALUE's don't have slot index themselves.
+// Adapted from RegisterCoalescer::buildVRegToDbgValueMap.
+static DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
+buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness) {
+  DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
+      DbgVRegToValues;
+  const SlotIndexes *Slots = Liveness->getSlotIndexes();
+  SmallVector<MachineInstr *, 8> ToInsert;
+
+  // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
+  // map.
+  auto CloseNewDVRange = [&DbgVRegToValues, &ToInsert](SlotIndex Slot) {
+    for (auto *X : ToInsert) {
+      for (const auto &Op : X->debug_operands()) {
+        if (Op.isReg() && Op.getReg().isVirtual())
+          DbgVRegToValues[Op.getReg()].push_back({Slot, X});
+      }
+    }
+
+    ToInsert.clear();
+  };
+
+  // Iterate over all instructions, collecting them into the ToInsert vector.
+  // Once a non-debug instruction is found, record the slot index of the
+  // collected DBG_VALUEs.
+  for (auto &MBB : MF) {
+    SlotIndex CurrentSlot = Slots->getMBBStartIdx(&MBB);
+
+    for (auto &MI : MBB) {
+      if (MI.isDebugValue()) {
+        if (any_of(MI.debug_operands(), [](const MachineOperand &MO) {
+              return MO.isReg() && MO.getReg().isVirtual();
+            }))
+          ToInsert.push_back(&MI);
+      } else if (!MI.isDebugOrPseudoInstr()) {
+        CurrentSlot = Slots->getInstructionIndex(MI);
+        CloseNewDVRange(CurrentSlot);
+      }
+    }
+
+    // Close range of DBG_VALUEs at the end of blocks.
+    CloseNewDVRange(Slots->getMBBEndIdx(&MBB));
+  }
+
+  // Sort all DBG_VALUEs we've seen by slot number.
+  for (auto &Pair : DbgVRegToValues)
+    llvm::sort(Pair.second);
+  return DbgVRegToValues;
+}
+
+// After register coalescing, some DBG_VALUEs will be invalid. Set them undef.
+// This function has to run before the actual coalescing, i.e., the register
+// changes.
+static void undefInvalidDbgValues(
+    const LiveIntervals *Liveness,
+    const ArrayRef<SmallVector<LiveInterval *, 4>> &Assignments,
+    DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
+        &DbgVRegToValues) {
+#ifndef NDEBUG
+  DenseSet<Register> SeenRegs;
+#endif
+  for (size_t I = 0, E = Assignments.size(); I < E; ++I) {
+    const auto &CoalescedIntervals = Assignments[I];
+    if (CoalescedIntervals.empty())
+      continue;
+    for (LiveInterval *LI : CoalescedIntervals) {
+      Register Reg = LI->reg();
+#ifndef NDEBUG
+      // Ensure we don't process the same register twice
+      assert(SeenRegs.insert(Reg).second);
+#endif
+      auto RegMapIt = DbgVRegToValues.find(Reg);
+      if (RegMapIt == DbgVRegToValues.end())
+        continue;
+      SlotIndex LastSlot;
+      bool LastUndefResult = false;
+      for (auto [Slot, DbgValue] : RegMapIt->second) {
+        // All consecutive DBG_VALUEs have the same slot because the slot
+        // indices they have is the one for the first non-debug instruction
+        // after it, because DBG_VALUEs don't have slot index themselves. Before
+        // doing live range queries, quickly check if the current DBG_VALUE has
+        // the same slot index as the previous one, in which case we should do
+        // the same. Note that RegMapIt->second, the vector of {SlotIndex,
+        // DBG_VALUE}, is sorted by SlotIndex, which is necessary for this
+        // check.
+        if (Slot == LastSlot) {
+          if (LastUndefResult) {
+            LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n");
+            DbgValue->setDebugValueUndef();
+          }
+          continue;
+        }
+        LastSlot = Slot;
+        LastUndefResult = false;
+        for (LiveInterval *OtherLI : CoalescedIntervals) {
+          if (LI == OtherLI)
+            continue;
+
+          // This DBG_VALUE has 'Reg' (the current LiveInterval's register) as
+          // its operand. If this DBG_VALUE's slot index is within other
+          // registers' live ranges, this DBG_VALUE should be undefed. For
+          // example, suppose %0 and %1 are to be coalesced into %0.
+          //   ; %0's live range starts
+          //   %0 = value_0
+          //   DBG_VALUE %0, !"a", ...      (a)
+          //   DBG_VALUE %1, !"b", ...      (b)
+          //   use %0
+          //   ; %0's live range ends
+          //   ...
+          //   ; %1's live range starts
+          //   %1 = value_1
+          //   DBG_VALUE %0, !"c", ...      (c)
+          //   DBG_VALUE %1, !"d", ...      (d)
+          //   use %1
+          //   ; %1's live range ends
+          //
+          // In this code, (b) and (c) should be set to undef. After the two
+          // registers are coalesced, (b) will incorrectly say the variable
+          // "b"'s value is 'value_0', and (c) will also incorrectly say the
+          // variable "c"'s value is value_1. Note it doesn't actually matter
+          // which register they are coalesced into (%0 or %1); (b) and (c)
+          // should be set to undef as well if they are coalesced into %1.
+          //
+          // This happens DBG_VALUEs are not included when computing live
+          // ranges.
+          //
+          // Note that it is not possible for this DBG_VALUE to be
+          // simultaneously within 'Reg''s live range and one of other coalesced
+          // registers' live ranges because if their live ranges overlapped they
+          // would have not been selected as a coalescing candidate in the first
+          // place.
+          auto *SegmentIt = OtherLI->find(Slot);
+          if (SegmentIt != OtherLI->end() && SegmentIt->contains(Slot)) {
+            LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n");
+            DbgValue->setDebugValueUndef();
+            LastUndefResult = true;
+            break;
+          }
+        }
+      }
+    }
+  }
+}
+
 bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG({
     dbgs() << "********** Register Coloring **********\n"
            << "********** Function: " << MF.getName() << '\n';
   });
 
   // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
   // registers could be modified before the longjmp is executed, resulting in
   // the wrong value being used afterwards. (See <rdar://problem/8007500>.)
   // TODO: Does WebAssembly need to care about setjmp for register coloring?
   if (MF.exposesReturnsTwice())
     return false;
 
   MachineRegisterInfo *MRI = &MF.getRegInfo();
   LiveIntervals *Liveness = &getAnalysis<LiveIntervals>();
   const MachineBlockFrequencyInfo *MBFI =
       &getAnalysis<MachineBlockFrequencyInfo>();
   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
 
+  // We don't preserve SSA form.
+  MRI->leaveSSA();
+
   // Gather all register intervals into a list and sort them.
   unsigned NumVRegs = MRI->getNumVirtRegs();
   SmallVector<LiveInterval *, 0> SortedIntervals;
   SortedIntervals.reserve(NumVRegs);
 
+  // Record DBG_VALUEs and their SlotIndexes.
+  auto DbgVRegToValues = buildVRegToDbgValueMap(MF, Liveness);
+
   LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
   for (unsigned I = 0; I < NumVRegs; ++I) {
     Register VReg = Register::index2VirtReg(I);
     if (MFI.isVRegStackified(VReg))
       continue;
     // Skip unused registers, which can use $drop.
     if (MRI->use_empty(VReg))
       continue;
for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
     if (Old != New && MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Old)
       MFI.setFrameBaseVreg(New);
     LLVM_DEBUG(dbgs() << "Assigning vreg" << Register::virtReg2Index(LI->reg())
                       << " to vreg" << Register::virtReg2Index(New) << "\n");
   }
   if (!Changed)
     return false;
 
+  // Set DBG_VALUEs that will be invalid after coalescing to undef.
+  undefInvalidDbgValues(Liveness, Assignments, DbgVRegToValues);
+
   // Rewrite register operands.
   for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
     Register Old = SortedIntervals[I]->reg();
     unsigned New = SlotMapping[I];
     if (Old != New)
       MRI->replaceRegWith(Old, New);
   }
   return true;
 }

llvm/test/DebugInfo/WebAssembly/dbg-value-reg-coloring.mir

+# RUN: llc -run-pass wasm-reg-coloring %s -o - | FileCheck %s
+
+# Tests for invalid DBG_VALUE set to undef after in RegColoring
+
+--- |
+  target triple = "wasm32-unknown-unknown"
+
+  declare void @use(i32)
+
+  define void @coalesce_test_0() {
+    call void @llvm.dbg.value(metadata i32 0, metadata !5, metadata !DIExpression()), !dbg !10
+    ret void
+  }
+  define void @coalesce_test_1() {
+    unreachable
+  }
+  define void @coalesce_test_2() {
+    unreachable
+  }
+  define void @coalesce_test_3() {
+    unreachable
+  }
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!2, !3, !4}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, emissionKind: FullDebug)
+  !1 = !DIFile(filename: "test.c", directory: "")
+  !2 = !{i32 7, !"Dwarf Version", i32 5}
+  !3 = !{i32 2, !"Debug Info Version", i32 3}
+  !4 = !{i32 1, !"wchar_size", i32 4}
+  !5 = !DILocalVariable(name: "var_a", scope: !6, file: !1, line: 2, type: !9)
+  !6 = distinct !DISubprogram(name: "coalesce_test_0", scope: !1, file: !1, line: 1, type: !7, scopeLine: 1, unit: !0)
+  !7 = !DISubroutineType(types: !8)
+  !8 = !{null}
+  !9 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !10 = !DILocation(line: 0, scope: !6)
+...
+
+---
+# %0 and %1 are coalesced in this test
+# CHECK-LABEL: name: coalesce_test_0
+name: coalesce_test_0
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    ; This should remain the same
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    ; This should be set to undef, because this is within %0's live range
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %0, implicit-def $arguments
+    NOP implicit-def $arguments
+    %1:i32 = CONST_I32 1, implicit-def $arguments
+    ; This should be set to undef, because this is within %1's live range
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    ; This should remain the same
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %1, implicit-def $arguments
+    RETURN implicit-def $arguments
+
+  ; CHECK:      %0:i32 = CONST_I32 0
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: NOP
+  ; CHECK-NEXT: %0:i32 = CONST_I32 1
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: RETURN implicit-def $arguments
+...
+
+---
+# A similar test with above, only with more consecutive DBG_VALUEs. These
+# consecutive DBG_VALUEs will be handled with a quick last result check.
+# CHECK-LABEL: name: coalesce_test_1
+name: coalesce_test_1
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    ; All DBG_VALUE %1s in %0's live range will be set to undef
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %0, implicit-def $arguments
+    NOP implicit-def $arguments
+    %1:i32 = CONST_I32 1, implicit-def $arguments
+    ; All DBG_VALUE %0s in %1's live range will be set to undef
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %1, implicit-def $arguments
+    RETURN implicit-def $arguments
+
+  ; CHECK:      %0:i32 = CONST_I32 0
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: NOP
+  ; CHECK-NEXT: %0:i32 = CONST_I32 1
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: RETURN implicit-def $arguments
+...
+
+---
+# The same with coalesce_test_0, but the two registers' live ranges are in
+# different BBs.
+# CHECK-LABEL: name: coalesce_test_2
+name: coalesce_test_2
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %0, implicit-def $arguments
+    BR %bb.1, implicit-def $arguments
+
+  ; CHECK: bb.0:
+  ; CHECK:      %0:i32 = CONST_I32 0
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: BR %bb.1
+
+  bb.1:
+    %1:i32 = CONST_I32 1, implicit-def $arguments
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %1, implicit-def $arguments
+    RETURN implicit-def $arguments
+
+  ; CHECK: bb.1:
+  ; CHECK-NEXT: %0:i32 = CONST_I32 1
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: RETURN implicit-def $arguments
+...
+
+---
+# Same test with three registers.
+# CHECK-LABEL: name: coalesce_test_3
+name: coalesce_test_3
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %2, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %0, implicit-def $arguments
+    NOP implicit-def $arguments
+    %1:i32 = CONST_I32 1, implicit-def $arguments
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %2, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %1, implicit-def $arguments
+    NOP implicit-def $arguments
+    %2:i32 = CONST_I32 2, implicit-def $arguments
+    DBG_VALUE %0, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %1, $noreg, !5, !DIExpression(), debug-location !10
+    DBG_VALUE %2, $noreg, !5, !DIExpression(), debug-location !10
+    CALL @use, %2, implicit-def $arguments
+    RETURN implicit-def $arguments
+
+  ; CHECK:      %0:i32 = CONST_I32 0
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: NOP
+  ; CHECK-NEXT: %0:i32 = CONST_I32 1
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: NOP
+  ; CHECK-NEXT: %0:i32 = CONST_I32 2
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE $noreg, $noreg
+  ; CHECK-NEXT: DBG_VALUE %0, $noreg
+  ; CHECK-NEXT: CALL @use, %0
+  ; CHECK-NEXT: RETURN implicit-def $arguments
+---