[LiveDebugValues] Cleanup Transfers when removing Entry Value

If we encounter a new debug value, describing the same parameter,
we should stop tracking the parameter's Entry Value. At that point,
in some cases, the Transfer which uses the parameter's Entry Value,
is already emitted. Thanks to the RemoveRedundantDebugValues pass,
many problems with incorrect instruction order and number of DBG_VALUEs
are fixed. However, we still cannot rely on the rule that each new
debug value is set by the previous non-debug instruction in Machine
Basic Block.

When new parameter debug value triggers removal of Backup Entry Value
for the same parameter, do the cleanup of Transfers emitted from Backup
Entry Values. Get the Transfer Instruction which created the new debug
value and search for debug values already emitted from the to-be-deleted
Backup Entry Value and attached to the Transfer Instruction. If found,
delete the Transfer and remove "primary" Entry Value Var Loc from
OpenRanges.

This patch fixes PR47628.

Patch by Nikola Tesic.

Differential revision: https://reviews.llvm.org/D106856

1 files changed, 151 insertions, 61 deletions

diff --git a/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
index 977d3ed..2566907 100644
--- a/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
+++ b/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
@@ -155,6 +155,7 @@
 #include <cassert>
 #include <cstdint>
 #include <functional>
+#include <map>
 #include <queue>
 #include <tuple>
 #include <utility>
@@ -284,6 +285,8 @@ private:
   LexicalScopes LS;
   VarLocSet::Allocator Alloc;
 
+  const MachineInstr *LastNonDbgMI;
+
   enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
 
   using FragmentInfo = DIExpression::FragmentInfo;
@@ -789,6 +792,10 @@ private:
     LocIndex LocationID;        ///< Location number for the transfer dest.
   };
   using TransferMap = SmallVector<TransferDebugPair, 4>;
+  // Types for recording Entry Var Locations emitted by a single MachineInstr,
+  // as well as recording MachineInstr which last defined a register.
+  using InstToEntryLocMap = std::multimap<const MachineInstr *, LocIndex>;
+  using RegDefToInstMap = DenseMap<Register, MachineInstr *>;
 
   // Types for recording sets of variable fragments that overlap. For a given
   // local variable, we record all other fragments of that variable that could
@@ -962,13 +969,22 @@ private:
                                Register NewReg = Register());
 
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
-                          VarLocMap &VarLocIDs);
+                          VarLocMap &VarLocIDs,
+                          InstToEntryLocMap &EntryValTransfers,
+                          RegDefToInstMap &RegSetInstrs);
   void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                   VarLocMap &VarLocIDs, TransferMap &Transfers);
-  bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
-                        VarLocMap &VarLocIDs, const VarLoc &EntryVL);
+  void cleanupEntryValueTransfers(const MachineInstr *MI,
+                                  OpenRangesSet &OpenRanges,
+                                  VarLocMap &VarLocIDs, const VarLoc &EntryVL,
+                                  InstToEntryLocMap &EntryValTransfers);
+  void removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
+                        VarLocMap &VarLocIDs, const VarLoc &EntryVL,
+                        InstToEntryLocMap &EntryValTransfers,
+                        RegDefToInstMap &RegSetInstrs);
   void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                       VarLocMap &VarLocIDs, TransferMap &Transfers,
+                       VarLocMap &VarLocIDs,
+                       InstToEntryLocMap &EntryValTransfers,
                        VarLocsInRange &KillSet);
   void recordEntryValue(const MachineInstr &MI,
                         const DefinedRegsSet &DefinedRegs,
@@ -976,12 +992,16 @@ private:
   void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
                             VarLocMap &VarLocIDs, TransferMap &Transfers);
   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                           VarLocMap &VarLocIDs, TransferMap &Transfers);
+                           VarLocMap &VarLocIDs,
+                           InstToEntryLocMap &EntryValTransfers,
+                           RegDefToInstMap &RegSetInstrs);
   bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
                           VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
 
   void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
-               VarLocMap &VarLocIDs, TransferMap &Transfers);
+               VarLocMap &VarLocIDs, TransferMap &Transfers,
+               InstToEntryLocMap &EntryValTransfers,
+               RegDefToInstMap &RegSetInstrs);
 
   void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
                              OverlapMap &OLapMap);
@@ -1214,62 +1234,100 @@ VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
   return {Reg, Offset};
 }
 
+/// Do cleanup of \p EntryValTransfers created by \p TRInst, by removing the
+/// Transfer, which uses the to-be-deleted \p EntryVL.
+void VarLocBasedLDV::cleanupEntryValueTransfers(
+    const MachineInstr *TRInst, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
+    const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers) {
+  if (EntryValTransfers.empty() || TRInst == nullptr)
+    return;
+
+  auto TransRange = EntryValTransfers.equal_range(TRInst);
+  for (auto TDPair : llvm::make_range(TransRange.first, TransRange.second)) {
+    const VarLoc &EmittedEV = VarLocIDs[TDPair.second];
+    if (std::tie(EntryVL.Var, EntryVL.Locs[0].Value.RegNo, EntryVL.Expr) ==
+        std::tie(EmittedEV.Var, EmittedEV.Locs[0].Value.RegNo,
+                 EmittedEV.Expr)) {
+      OpenRanges.erase(EmittedEV);
+      EntryValTransfers.erase(TRInst);
+      break;
+    }
+  }
+}
+
 /// Try to salvage the debug entry value if we encounter a new debug value
 /// describing the same parameter, otherwise stop tracking the value. Return
-/// true if we should stop tracking the entry value, otherwise return false.
-bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
-                                       OpenRangesSet &OpenRanges,
-                                       VarLocMap &VarLocIDs,
-                                       const VarLoc &EntryVL) {
+/// true if we should stop tracking the entry value and do the cleanup of
+/// emitted Entry Value Transfers, otherwise return false.
+void VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
+                                      OpenRangesSet &OpenRanges,
+                                      VarLocMap &VarLocIDs,
+                                      const VarLoc &EntryVL,
+                                      InstToEntryLocMap &EntryValTransfers,
+                                      RegDefToInstMap &RegSetInstrs) {
   // Skip the DBG_VALUE which is the debug entry value itself.
-  if (MI.isIdenticalTo(EntryVL.MI))
-    return false;
+  if (&MI == &EntryVL.MI)
+    return;
 
   // If the parameter's location is not register location, we can not track
-  // the entry value any more. In addition, if the debug expression from the
-  // DBG_VALUE is not empty, we can assume the parameter's value has changed
-  // indicating that we should stop tracking its entry value as well.
-  if (!MI.getDebugOperand(0).isReg() ||
-      MI.getDebugExpression()->getNumElements() != 0)
-    return true;
-
-  // If the DBG_VALUE comes from a copy instruction that copies the entry value,
-  // it means the parameter's value has not changed and we should be able to use
-  // its entry value.
+  // the entry value any more. It doesn't have the TransferInst which defines
+  // register, so no Entry Value Transfers have been emitted already.
+  if (!MI.getDebugOperand(0).isReg())
+    return;
+
+  // Try to get non-debug instruction responsible for the DBG_VALUE.
+  const MachineInstr *TransferInst = nullptr;
   Register Reg = MI.getDebugOperand(0).getReg();
-  auto I = std::next(MI.getReverseIterator());
-  const MachineOperand *SrcRegOp, *DestRegOp;
-  if (I != MI.getParent()->rend()) {
+  if (Reg.isValid() && RegSetInstrs.find(Reg) != RegSetInstrs.end())
+    TransferInst = RegSetInstrs.find(Reg)->second;
 
+  // Case of the parameter's DBG_VALUE at the start of entry MBB.
+  if (!TransferInst && !LastNonDbgMI && MI.getParent()->isEntryBlock())
+    return;
+
+  // If the debug expression from the DBG_VALUE is not empty, we can assume the
+  // parameter's value has changed indicating that we should stop tracking its
+  // entry value as well.
+  if (MI.getDebugExpression()->getNumElements() == 0 && TransferInst) {
+    // If the DBG_VALUE comes from a copy instruction that copies the entry
+    // value, it means the parameter's value has not changed and we should be
+    // able to use its entry value.
     // TODO: Try to keep tracking of an entry value if we encounter a propagated
     // DBG_VALUE describing the copy of the entry value. (Propagated entry value
     // does not indicate the parameter modification.)
-    auto DestSrc = TII->isCopyInstr(*I);
-    if (!DestSrc)
-      return true;
-
-    SrcRegOp = DestSrc->Source;
-    DestRegOp = DestSrc->Destination;
-    if (Reg != DestRegOp->getReg())
-      return true;
-
-    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
-      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
-      if (VL.isEntryValueCopyBackupReg(Reg) &&
-          // Entry Values should not be variadic.
-          VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
-        return false;
+    auto DestSrc = TII->isCopyInstr(*TransferInst);
+    if (DestSrc) {
+      const MachineOperand *SrcRegOp, *DestRegOp;
+      SrcRegOp = DestSrc->Source;
+      DestRegOp = DestSrc->Destination;
+      if (Reg == DestRegOp->getReg()) {
+        for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
+          const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
+          if (VL.isEntryValueCopyBackupReg(Reg) &&
+              // Entry Values should not be variadic.
+              VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
+            return;
+        }
+      }
     }
   }
 
-  return true;
+  LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
+             MI.print(dbgs(), /*IsStandalone*/ false,
+                      /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
+                      /*AddNewLine*/ true, TII));
+  cleanupEntryValueTransfers(TransferInst, OpenRanges, VarLocIDs, EntryVL,
+                             EntryValTransfers);
+  OpenRanges.erase(EntryVL);
 }
 
 /// End all previous ranges related to @MI and start a new range from @MI
 /// if it is a DBG_VALUE instr.
 void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
-                                         OpenRangesSet &OpenRanges,
-                                         VarLocMap &VarLocIDs) {
+                                        OpenRangesSet &OpenRanges,
+                                        VarLocMap &VarLocIDs,
+                                        InstToEntryLocMap &EntryValTransfers,
+                                        RegDefToInstMap &RegSetInstrs) {
   if (!MI.isDebugValue())
     return;
   const DILocalVariable *Var = MI.getDebugVariable();
@@ -1286,13 +1344,8 @@ void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
   auto EntryValBackupID = OpenRanges.getEntryValueBackup(V);
   if (Var->isParameter() && EntryValBackupID) {
     const VarLoc &EntryVL = VarLocIDs[EntryValBackupID->back()];
-    if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) {
-      LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
-                 MI.print(dbgs(), /*IsStandalone*/ false,
-                          /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
-                          /*AddNewLine*/ true, TII));
-      OpenRanges.erase(EntryVL);
-    }
+    removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL, EntryValTransfers,
+                     RegSetInstrs);
   }
 
   if (all_of(MI.debug_operands(), [](const MachineOperand &MO) {
@@ -1340,7 +1393,7 @@ void VarLocBasedLDV::collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
 void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
                                      OpenRangesSet &OpenRanges,
                                      VarLocMap &VarLocIDs,
-                                     TransferMap &Transfers,
+                                     InstToEntryLocMap &EntryValTransfers,
                                      VarLocsInRange &KillSet) {
   // Do not insert entry value locations after a terminator.
   if (MI.isTerminator())
@@ -1366,7 +1419,9 @@ void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
     VarLoc EntryLoc = VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr,
                                              EntryVL.Locs[0].Value.RegNo);
     LocIndices EntryValueIDs = VarLocIDs.insert(EntryLoc);
-    Transfers.push_back({&MI, EntryValueIDs.back()});
+    assert(EntryValueIDs.size() == 1 &&
+           "EntryValue loc should not be variadic");
+    EntryValTransfers.insert({&MI, EntryValueIDs.back()});
     OpenRanges.insert(EntryValueIDs, EntryLoc);
   }
 }
@@ -1443,9 +1498,11 @@ void VarLocBasedLDV::insertTransferDebugPair(
 }
 
 /// A definition of a register may mark the end of a range.
-void VarLocBasedLDV::transferRegisterDef(
-    MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
-    TransferMap &Transfers) {
+void VarLocBasedLDV::transferRegisterDef(MachineInstr &MI,
+                                         OpenRangesSet &OpenRanges,
+                                         VarLocMap &VarLocIDs,
+                                         InstToEntryLocMap &EntryValTransfers,
+                                         RegDefToInstMap &RegSetInstrs) {
 
   // Meta Instructions do not affect the debug liveness of any register they
   // define.
@@ -1468,6 +1525,9 @@ void VarLocBasedLDV::transferRegisterDef(
       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
         // FIXME: Can we break out of this loop early if no insertion occurs?
         DeadRegs.insert(*RAI);
+      if (RegSetInstrs.find(MO.getReg()) != RegSetInstrs.end())
+        RegSetInstrs.erase(MO.getReg());
+      RegSetInstrs.insert({MO.getReg(), &MI});
     } else if (MO.isRegMask()) {
       RegMasks.push_back(MO.getRegMask());
     }
@@ -1494,6 +1554,11 @@ void VarLocBasedLDV::transferRegisterDef(
           });
       if (AnyRegMaskKillsReg)
         DeadRegs.insert(Reg);
+      if (AnyRegMaskKillsReg) {
+        if (RegSetInstrs.find(Reg) != RegSetInstrs.end())
+          RegSetInstrs.erase(Reg);
+        RegSetInstrs.insert({Reg, &MI});
+      }
     }
   }
 
@@ -1507,7 +1572,7 @@ void VarLocBasedLDV::transferRegisterDef(
   if (TPC) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.ShouldEmitDebugEntryValues())
-      emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
+      emitEntryValues(MI, OpenRanges, VarLocIDs, EntryValTransfers, KillSet);
   }
 }
 
@@ -1840,9 +1905,15 @@ void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
 
 /// This routine creates OpenRanges.
 void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                              VarLocMap &VarLocIDs, TransferMap &Transfers) {
-  transferDebugValue(MI, OpenRanges, VarLocIDs);
-  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers);
+                             VarLocMap &VarLocIDs, TransferMap &Transfers,
+                             InstToEntryLocMap &EntryValTransfers,
+                             RegDefToInstMap &RegSetInstrs) {
+  if (!MI.isDebugInstr())
+    LastNonDbgMI = &MI;
+  transferDebugValue(MI, OpenRanges, VarLocIDs, EntryValTransfers,
+                     RegSetInstrs);
+  transferRegisterDef(MI, OpenRanges, VarLocIDs, EntryValTransfers,
+                      RegSetInstrs);
   transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
   transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
 }
@@ -2070,6 +2141,10 @@ bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
   VarLocInMBB InLocs;         // Ranges that are incoming after joining.
   TransferMap Transfers;      // DBG_VALUEs associated with transfers (such as
                               // spills, copies and restores).
+  // Map responsible MI to attached Transfer emitted from Backup Entry Value.
+  InstToEntryLocMap EntryValTransfers;
+  // Map a Register to the last MI which clobbered it.
+  RegDefToInstMap RegSetInstrs;
 
   VarToFragments SeenFragments;
 
@@ -2166,8 +2241,11 @@ bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
         // operate with registers that correspond to user variables.
         // First load any pending inlocs.
         OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs);
+        LastNonDbgMI = nullptr;
+        RegSetInstrs.clear();
         for (auto &MI : *MBB)
-          process(MI, OpenRanges, VarLocIDs, Transfers);
+          process(MI, OpenRanges, VarLocIDs, Transfers, EntryValTransfers,
+                  RegSetInstrs);
         OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
 
         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
@@ -2201,6 +2279,18 @@ bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC,
   }
   Transfers.clear();
 
+  // Add DBG_VALUEs created using Backup Entry Value location.
+  for (auto &TR : EntryValTransfers) {
+    MachineInstr *TRInst = const_cast<MachineInstr *>(TR.first);
+    assert(!TRInst->isTerminator() &&
+           "Cannot insert DBG_VALUE after terminator");
+    MachineBasicBlock *MBB = TRInst->getParent();
+    const VarLoc &VL = VarLocIDs[TR.second];
+    MachineInstr *MI = VL.BuildDbgValue(MF);
+    MBB->insertAfterBundle(TRInst->getIterator(), MI);
+  }
+  EntryValTransfers.clear();
+
   // Deferred inlocs will not have had any DBG_VALUE insts created; do
   // that now.
   flushPendingLocs(InLocs, VarLocIDs);