[DebugInfo][InstrRef] Terminate variable locations when overlapping fragments are assigned

[jmorse]

Summary

In todays episode of "uncommon corner cases that LiveDebugValues handles": overlapping fragments. The modified test checks that if we have a variable where its fragments are split into overlapping segments:

DBG_VALUE $ax, $noreg, !123, !DIExpression(DW_OP_LLVM_fragment_0, 16)
...
DBG_VALUE $eax, $noreg, !123, !DIExpression(DW_OP_LLVM_fragment_0, 32)

that we only propagate the most recently assigned fragment out of a block. The test only deals with live-in variable locations, as overlaps within blocks is DbgEntityHistoryCalculators domain.

InstrRefBasedLDV needs to preserve this behaviour: we've kept the accumulateFragmentMap method from VarLocBasedLDV, we just need it to recognise DBG_INSTR_REFs. Once it's produce a mapping of variable / fragments to the overlapped variable / fragments, VLocTracker uses it to identify when a debug instruction needs to terminate the other parts it overlaps with.

The changes to live-debug-values-fragments.mir are:

• $ax switches to $cx in two scenarios, because it's a value copied from one register to another, doesn't matter which is used,
• The order of DBG_VALUEs produced changes with instruction referencing.

[Orlando]

One nit and an inline question, otherwise LGTM. The issue (if I've correctly identified an issue and not missed something) could be resolved in a separate patch IMO, so I'll hit Accept now.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1660

nit: possibly worth rewording to "A previously unprocessed debug instruction"?

1675

Rather than having DILocalVariable as a key, shouldn't we be using {DILocalVariable, InlinedAt}? Otherwise, fragments of different inlined instances of the same variable may be considered overlapping, which is incorrect.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

731

See other comment re: inlined-at and overlaps. Because of how the overlap map is constructed I think you're going to be treating fragments of 2 inlined instances of a variable as overlapping here. If I'm correct about that, I think the fix should be in how the overlap map is constructed (see other comment).

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1675

Oooooo. That's right. And this is AFAIK the same code as in VarLocBasedLDV, so we're bug-for-bug compatible, as it were.

However, I suspect InstrRefBasedLDV is getting away with this OK:

• We identify each fragment of a variable independently in the variable-value transfer function builder,
• If a fragment of any variable at another inlining site overlaps, we'll try and terminate the overlapped fragments,
• If the other inlining-sites don't use those fragments, they won't be terminated.

To illustrate, imagine we have variable !1, with fragments (0, 32), (32, 32) at inlining site A, and (16, 32) at another inlining site B. Over in considerOverlaps, if we're building a transfer function that has already read something like:

{!1, A, (0, 32)} <- ValueIDNum(1, 0, 0)

And encounter a DBG_INSTR_REF for fragment (32, 32), then we'll first record the assignment to (32, 32), then terminate the location for the overlapped fragment. That makes the following transfer function:

{!1, A, (0, 32)} <- ValueIDNum(1, 0, 0)
{!1, A, (16, 32)} <- Undef
{!1, A, (32, 32)} <- ValueIDNum(1, 0, 1)

Because each fragment is solved independently: the (0, 32) and (32, 32) fragments will be propagated through the block to any successors, but an overlapping fragment in (16, 32) won't (if it even exists).

This definitely deserves an extra test at the very least, and some more docs as it violates the principle of least suprise. It also raises interesting questions on how we might integrate DbgEntityHistoryCalculator with LiveDebugValues, which I think is the ultimate outcome of all this refactoring.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

#endif
 
   /// Create a DBG_VALUE based on  machine location \p MLoc. Qualify it with the
   /// information in \pProperties, for variable Var. Don't insert it anywhere,
   /// just return the builder for it.
   MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
                               const DbgValueProperties &Properties);
 };
 
+/// Types for recording sets of variable fragments that overlap. For a given
+/// local variable, we record all other fragments of that variable that could
+/// overlap it, to reduce search time.
+using FragmentOfVar =
+    std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
+using OverlapMap =
+    DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
+
 /// Collection of DBG_VALUEs observed when traversing a block. Records each
 /// variable and the value the DBG_VALUE refers to. Requires the machine value
 /// location dataflow algorithm to have run already, so that values can be
 /// identified.
 class VLocTracker {
 public:
   /// Map DebugVariable to the latest Value it's defined to have.
   /// Needs to be a MapVector because we determine order-in-the-input-MIR from
   /// the order in this container.
   /// We only retain the last DbgValue in each block for each variable, to
   /// determine the blocks live-out variable value. The Vars container forms the
   /// transfer function for this block, as part of the dataflow analysis. The
   /// movement of values between locations inside of a block is handled at a
   /// much later stage, in the TransferTracker class.
   MapVector<DebugVariable, DbgValue> Vars;
   DenseMap<DebugVariable, const DILocation *> Scopes;
   MachineBasicBlock *MBB = nullptr;
+  const OverlapMap &OverlappingFragments;
+  DbgValueProperties EmptyProperties;
 
 public:
-  VLocTracker() {}
+  VLocTracker(const OverlapMap &O, const DIExpression *EmptyExpr)
+      : OverlappingFragments(O), EmptyProperties(EmptyExpr, false) {}
 
   void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
               Optional<ValueIDNum> ID) {
     assert(MI.isDebugValue() || MI.isDebugRef());
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
     DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
                         : DbgValue(Properties, DbgValue::Undef);
 
     // Attempt insertion; overwrite if it's already mapped.
     auto Result = Vars.insert(std::make_pair(Var, Rec));
     if (!Result.second)
       Result.first->second = Rec;
     Scopes[Var] = MI.getDebugLoc().get();
+
+    considerOverlaps(Var, MI.getDebugLoc().get());
   }
 
   void defVar(const MachineInstr &MI, const MachineOperand &MO) {
     // Only DBG_VALUEs can define constant-valued variables.
     assert(MI.isDebugValue());
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
     DbgValueProperties Properties(MI);
     DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);
 
     // Attempt insertion; overwrite if it's already mapped.
     auto Result = Vars.insert(std::make_pair(Var, Rec));
     if (!Result.second)
       Result.first->second = Rec;
     Scopes[Var] = MI.getDebugLoc().get();
+
+    considerOverlaps(Var, MI.getDebugLoc().get());
   }
-};
 
-/// Types for recording sets of variable fragments that overlap. For a given
-/// local variable, we record all other fragments of that variable that could
-/// overlap it, to reduce search time.
-using FragmentOfVar =
-    std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
-using OverlapMap =
-    DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
+  void considerOverlaps(const DebugVariable &Var, const DILocation *Loc) {
+    auto Overlaps = OverlappingFragments.find(
+        {Var.getVariable(), Var.getFragmentOrDefault()});
+    if (Overlaps == OverlappingFragments.end())
+      return;
+
+    // Otherwise: terminate any overlapped variable locations.
+    for (auto FragmentInfo : Overlaps->second) {
+      // The "empty" fragment is stored as DebugVariable::DefaultFragment, so
+      // that it overlaps with everything, however its cannonical representation
+      // in a DebugVariable is as "None".
+      Optional<DIExpression::FragmentInfo> OptFragmentInfo = FragmentInfo;
+      if (DebugVariable::isDefaultFragment(FragmentInfo))
+        OptFragmentInfo = None;
+
+      DebugVariable Overlapped(Var.getVariable(), OptFragmentInfo,
+                               Var.getInlinedAt());
+      DbgValue Rec = DbgValue(EmptyProperties, DbgValue::Undef);
+
+      // Attempt insertion; overwrite if it's already mapped.
+      auto Result = Vars.insert(std::make_pair(Overlapped, Rec));
+      if (!Result.second)
+        Result.first->second = Rec;
+      Scopes[Overlapped] = Loc;
+    }
+  }
+};
 
 // XXX XXX docs
 class InstrRefBasedLDV : public LDVImpl {
 public:
   friend class ::InstrRefLDVTest;
 
   using FragmentInfo = DIExpression::FragmentInfo;
   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
 
   return true;
 }
 
 /// Accumulate a mapping between each DILocalVariable fragment and other
 /// fragments of that DILocalVariable which overlap. This reduces work during
 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
 /// known-to-overlap fragments are present".
-/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
+/// \param MI A previously unprocessed debug instruction to analyze for
 ///           fragment usage.
 void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
+  assert(MI.isDebugValue() || MI.isDebugRef());
   DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
   FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
 
   // If this is the first sighting of this variable, then we are guaranteed
   // there are currently no overlapping fragments either. Initialize the set
   // of seen fragments, record no overlaps for the current one, and return.
   auto SeenIt = SeenFragments.find(MIVar.getVariable());
   if (SeenIt == SeenFragments.end()) {
     SmallSet<FragmentInfo, 4> OneFragment;
     OneFragment.insert(ThisFragment);
     SeenFragments.insert({MIVar.getVariable(), OneFragment});
 
     OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
     return;
   }
 
   // If this particular Variable/Fragment pair already exists in the overlap
   // map, it has already been accounted for.
   auto IsInOLapMap =
for (auto &MBB : MF) {
     // production only, this signifies the live-in value to the block.
     MTracker->reset();
     MTracker->setMPhis(CurBB);
 
     // Step through each instruction in this block.
     for (auto &MI : MBB) {
       process(MI);
       // Also accumulate fragment map.
-      if (MI.isDebugValue())
+      if (MI.isDebugValue() || MI.isDebugRef())
         accumulateFragmentMap(MI);
 
       // Create a map from the instruction number (if present) to the
       // MachineInstr and its position.
       if (uint64_t InstrNo = MI.peekDebugInstrNum()) {
         auto InstrAndPos = std::make_pair(&MI, CurInst);
         auto InsertResult =
             DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
 
   int MaxNumBlocks = -1;
   for (auto &MBB : MF)
     MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);
   assert(MaxNumBlocks >= 0);
   ++MaxNumBlocks;
 
   MLocTransfer.resize(MaxNumBlocks);
-  vlocs.resize(MaxNumBlocks);
+  vlocs.resize(MaxNumBlocks, VLocTracker(OverlapFragments, EmptyExpr));
   SavedLiveIns.resize(MaxNumBlocks);
 
   initialSetup(MF);
 
   produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
 
   // Allocate and initialize two array-of-arrays for the live-in and live-out
   // machine values. The outer dimension is the block number; while the inner
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   TTracker = nullptr;
 
   ArtificialBlocks.clear();
   OrderToBB.clear();
   BBToOrder.clear();
   BBNumToRPO.clear();
   DebugInstrNumToInstr.clear();
   DebugPHINumToValue.clear();
+  OverlapFragments.clear();
+  SeenFragments.clear();
 
   return Changed;
 }
 
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }
 

llvm/test/DebugInfo/MIR/X86/live-debug-values-fragments.mir

-# RUN: llc %s -o - -run-pass=livedebugvalues -experimental-debug-variable-locations=false | FileCheck %s
+# RUN: llc %s -o - -run-pass=livedebugvalues -experimental-debug-variable-locations=true | FileCheck %s
 #
 # The first func tests that, for two independent variable fragments defined in
 # blocks 1 and 2, _both_ their locations are propagated into the exit block.
 # LiveDebugValues previously ignored fragments and only propagated the last
 # variable location seen.
 #
 # The second func tests that overlapping variable fragments are handled
 # correctly -- that the redefinition of a particular fragment also clobbers
 # any overlaps. The dbg value of $cx in block one should not be propagated to
 # block two, because an overlapping dbg value inst has been encountered.
 #
 # The third function checks that DBG_VALUEs without fragments are seen as
 # overlapping any DBG_VALUE with a fragment.
 #
 # CHECK-LABEL: foo
 # CHECK-LABEL: bb.3.bb3:
-# CHECK:      DBG_VALUE $ebx, $noreg, !{{[0-9]+}},
-# CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 32, 32)
-# CHECK-NEXT: DBG_VALUE $eax, $noreg, !{{[0-9]+}},
+# CHECK:      DBG_VALUE $ecx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 0, 32)
+# CHECK-NEXT: DBG_VALUE $ebx, $noreg, !{{[0-9]+}},
+# CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 # CHECK-NEXT: XOR32rr
 # CHECK-NEXT: RET64
 #
 # CHECK-LABEL: bar
 # CHECK-LABEL: bb.0.entry:
 # CHECK:      DBG_VALUE $cx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 0, 16)
 
 # CHECK-LABEL: bb.1.bb1:
 # CHECK:      DBG_VALUE $cx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 0, 16)
 # CHECK-NEXT: MOV32rr
 # CHECK-NEXT: DBG_VALUE $ax, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 8, 16)
 # CHECK-NEXT: JMP_1
 
 # CHECK-LABEL: bb.2.bb2:
 # CHECK-NOT:  DBG_VALUE
-# CHECK:      DBG_VALUE $ax, $noreg, !{{[0-9]+}},
+# CHECK:      DBG_VALUE $cx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 8, 16)
 # CHECK-NEXT: MOV32rr
 # CHECK-NEXT: ADD32ri8
 # CHECK-NEXT: DBG_VALUE $ebx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 # CHECK-NEXT: JMP_1
 
 # CHECK-LABEL: bb.3.bb3:
-# CHECK:      DBG_VALUE $ebx, $noreg, !{{[0-9]+}},
-# CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 32, 32)
-# CHECK-NEXT: DBG_VALUE $ax, $noreg, !{{[0-9]+}},
+# CHECK:      DBG_VALUE $cx, $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 8, 16)
+# CHECK-NEXT: DBG_VALUE $ebx, $noreg, !{{[0-9]+}},
+# CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 # CHECK-NEXT: XOR32rr
 # CHECK-NEXT: RET64
 
 # CHECK-LABEL: baz
 # CHECK-LABEL: bb.0.entry:
 # CHECK:      DBG_VALUE $cx,  $noreg, !{{[0-9]+}},
 # CHECK-SAME:                 !DIExpression(DW_OP_LLVM_fragment, 0, 16)
 # CHECK-NEXT: JMP_1 %bb.1

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

public:
   DIFile *OurFile;
   DISubprogram *OurFunc;
   DILexicalBlock *OurBlock, *AnotherBlock;
   DISubprogram *ToInlineFunc;
   DILexicalBlock *ToInlineBlock;
   DILocalVariable *FuncVariable;
   DIBasicType *LongInt;
   DIExpression *EmptyExpr;
+  LiveDebugValues::OverlapMap Overlaps;
 
   DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc;
 
   MachineBasicBlock *MBB0, *MBB1, *MBB2, *MBB3, *MBB4;
 
   std::unique_ptr<InstrRefBasedLDV> LDV;
   std::unique_ptr<MLocTracker> MTracker;
   std::unique_ptr<VLocTracker> VTracker;
void addMTracker(MachineFunction *MF) {
     const TargetSubtargetInfo &STI = MF->getSubtarget();
     MTracker = std::make_unique<MLocTracker>(
           *MF, *LDV->TII, *LDV->TRI, *STI.getTargetLowering());
     LDV->MTracker = &*MTracker;
   }
 
   void addVTracker() {
     ASSERT_TRUE(LDV);
-    VTracker = std::make_unique<VLocTracker>();
+    VTracker = std::make_unique<VLocTracker>(Overlaps, EmptyExpr);
     LDV->VTracker = &*VTracker;
   }
 
   // Some routines for bouncing into LDV,
   void buildMLocValueMap(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
                          SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
     LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer);
   }
TEST_F(InstrRefLDVTest, VLocSingleBlock) {
   // Mild hack: rather than constructing machine instructions in each block
   // and creating lexical scopes across them, instead just tell
   // buildVLocValueMap that there's an assignment in every block. That makes
   // every block in scope.
   SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
   AssignBlocks.insert(MBB0);
 
   SmallVector<VLocTracker, 1> VLocs;
-  VLocs.resize(1);
+  VLocs.resize(1, VLocTracker(Overlaps, EmptyExpr));
 
   InstrRefBasedLDV::LiveInsT Output;
 
   // Test that, with no assignments at all, no mappings are created for the
   // variable in this function.
   buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
                     OutLocsPtr, InLocsPtr, VLocs);
   EXPECT_EQ(Output.size(), 0ul);
TEST_F(InstrRefLDVTest, VLocDiamondBlocks) {
   // every block in scope.
   SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
   AssignBlocks.insert(MBB0);
   AssignBlocks.insert(MBB1);
   AssignBlocks.insert(MBB2);
   AssignBlocks.insert(MBB3);
 
   SmallVector<VLocTracker, 1> VLocs;
-  VLocs.resize(4);
+  VLocs.resize(4, VLocTracker(Overlaps, EmptyExpr));
 
   InstrRefBasedLDV::LiveInsT Output;
 
   // Start off with LiveInRsp in every location.
   for (unsigned int I = 0; I < 4; ++I) {
     InLocs[I][0] = InLocs[I][1] = LiveInRsp;
     OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
   }
TEST_F(InstrRefLDVTest, VLocSimpleLoop) {
   AllVars.insert(Var);
 
   SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
   AssignBlocks.insert(MBB0);
   AssignBlocks.insert(MBB1);
   AssignBlocks.insert(MBB2);
 
   SmallVector<VLocTracker, 3> VLocs;
-  VLocs.resize(3);
+  VLocs.resize(3, VLocTracker(Overlaps, EmptyExpr));
 
   InstrRefBasedLDV::LiveInsT Output;
 
   // Start off with LiveInRsp in every location.
   for (unsigned int I = 0; I < 3; ++I) {
     InLocs[I][0] = InLocs[I][1] = LiveInRsp;
     OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
   }
TEST_F(InstrRefLDVTest, VLocNestedLoop) {
   SmallPtrSet<MachineBasicBlock *, 5> AssignBlocks;
   AssignBlocks.insert(MBB0);
   AssignBlocks.insert(MBB1);
   AssignBlocks.insert(MBB2);
   AssignBlocks.insert(MBB3);
   AssignBlocks.insert(MBB4);
 
   SmallVector<VLocTracker, 5> VLocs;
-  VLocs.resize(5);
+  VLocs.resize(5, VLocTracker(Overlaps, EmptyExpr));
 
   InstrRefBasedLDV::LiveInsT Output;
 
   // Start off with LiveInRsp in every location.
   for (unsigned int I = 0; I < 5; ++I) {
     InLocs[I][0] = InLocs[I][1] = LiveInRsp;
     OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
   }