[DebugInfo] MCP: collect and update DBG_VALUEs encountered in local block

[jmorse]

Summary

The purpose of this patch is to remove a user of collectDebugValues (via changeDebugValuesDefReg): it currently assumes that all DBG_VALUEs immediately follow the specified instruction, which isn't necessarily true. This is going to become very often untrue when PR38754 work is merged. It also cannot be fixed by collectDebugValues iterating over register users because MCP runs after regalloc.

Instead of calling changeDebugValuesDefReg on an instruction to change its debug users, in this patch we instead collect DBG_VALUEs of copies as we iterate over insns, and update the debug users of copies that are made dead. This isn't a non-functional change, because MCP will now update DBG_VALUEs that aren't immediately after a copy, but refer to the same register. I've hijacked the regression test for PR38773 to test for this new behaviour, an entirely new test seemed overkill.

While fiddling with this patch an obvious question came to me, of "Why don't we copy-propagate the debug users just like other instructions?". The reason why is that DBG_VALUEs are re-generated after regalloc, and don't get the 'renameable' flag assigned to their register operands, preventing them from being renamed here. (Plus, debug users have no register class). Addressing that seemed like quite a large modification for a small issue.

[aprantl]

lib/CodeGen/MachineCopyPropagation.cpp

250

Could we just pass a MachineInstr& instead, or can it be null for the !IsDebug case?

[jmorse]

Pass MI reference to ReadRegister, avoiding the need for more assertions.

lib/CodeGen/MachineCopyPropagation.cpp

250

We can indeed, uploading a new version now.

[aprantl]

lib/CodeGen/MachineCopyPropagation.cpp

211

instead of an opaque optional parameter, we could also define

enum { DebugUse = false, RegularUse = true };

possibly with better names and explicitly pass it every time. Up to you.

[CarlosAlbertoEnciso]

lib/CodeGen/MachineCopyPropagation.cpp

222

May be a more descriptive comment; something like:

/// Keeps track of debug users for the current basic block.

246

May be change the logic to:

if (IsDebug)
  CopyDbgUsers[Copy].push_back(&Reader);
else {
  LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
  MaybeDeadCopies.remove(Copy);
}

625

As your intention is to replace the calls (direct and indirect) to collectDebugValues and changeDebugValuesDefReg, why not move the new code to a function that can be reused.

MaybeDead->someNewFunction(MaybeDead->getOperand(1).getReg(), CopyDbgUsers);

[CarlosAlbertoEnciso]

lib/CodeGen/MachineCopyPropagation.cpp

211

Same here.

[jmorse]

Use enumeration and explicit function arguments to disambiguate debug and regular register readers

[jmorse]

Revise a comment (missed in previous rev, whoops)

[jmorse]

lib/CodeGen/MachineCopyPropagation.cpp

625

I don't know that there's any useful abstraction occurring there -- once you've called MaybeDead->getOperand(1) (which is copy-instruction specific) the code ceases to be about any particular instruction. Possibly it could be a static MachineInstr function?

IMHO this is a direction to be avoided though: collectDebugValues gives the impression (via its name) that it's a function that works in the general case, but (IMHO again) all the users really have context-specific requirements. Repeating some code in these circumstances is useful to highlight the point that there's no easy (or general) solution.

[jmorse]

lib/CodeGen/MachineCopyPropagation.cpp

625

Reading back that doesn't sound great, what I meant was: "Let's not try too hard to de-duplicate when IMHO all the users of collectDebugValues have very context specific requirements"

[CarlosAlbertoEnciso]

lib/CodeGen/MachineCopyPropagation.cpp

625

What I am suggesting is to encapsulate just the map processing into a function. But to preserve the logic that uses it.

[jmorse]

Shift DBG_VALUE updating to a MachineRegisterInfo helper

[jmorse]

lib/CodeGen/MachineCopyPropagation.cpp

625

Now seeing this is about the loop rather than the rest -- hows about this helper method in MRI? (The operation seems more register-info related than instr related).

[jmorse]

Ping, @CarlosAlbertoEnciso how's the utility function?

[jmorse]

Ancient-ping on this, with the aim of it helping the placeDbgValues patch in. To re-summarise: this collects DBG_VALUEs to rewrite while walking through MachineCopyPropagation, rather than relying on the all-dbg-values-follow-the-defining-inst assumption.

[vsk]

Lgtm, thanks for working on this. I haven't touched MCP myself, so could you wait for another +1? + @bogner in case he has time to take a look.

include/llvm/CodeGen/MachineRegisterInfo.h

819 ↗

(On Diff #181801)

nit: consider ArrayRef? It's a bit more flexible and this is a widely-used class.

lib/CodeGen/MachineCopyPropagation.cpp

601

Wdyt of leaving a comment here about erasing CopyDbgUsers[MaybeDead] to save memory? There's probably a cpu-time tradeoff so it'd need profiling.

[bogner]

Seems reasonable to me

lib/CodeGen/MachineCopyPropagation.cpp

public:
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoVRegs);
   }
 
 private:
   void ClobberRegister(unsigned Reg);
-  void ReadRegister(unsigned Reg);
+  void ReadRegister(unsigned Reg, MachineInstr &Reader,
+                    bool IsDebug = false);
   void CopyPropagateBlock(MachineBasicBlock &MBB);
   bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
   void forwardUses(MachineInstr &MI);
   bool isForwardableRegClassCopy(const MachineInstr &Copy,
                                  const MachineInstr &UseI, unsigned UseIdx);
   bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
 
   /// Candidates for deletion.
   SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
 
+  /// Copy -> DbgUsers multimap.
+  DenseMap<MachineInstr*, TinyPtrVector<MachineInstr*>> CopyDbgUsers;
+
   CopyTracker Tracker;
 
   bool Changed;
 };
 
 } // end anonymous namespace
 
 char MachineCopyPropagation::ID = 0;
 
 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
 
 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
                 "Machine Copy Propagation Pass", false, false)
 
-void MachineCopyPropagation::ReadRegister(unsigned Reg) {
+void MachineCopyPropagation::ReadRegister(unsigned Reg, MachineInstr &Reader,
+                                          bool IsDebug) {
   // If 'Reg' is defined by a copy, the copy is no longer a candidate
-  // for elimination.
+  // for elimination. If a copy is "read" by a debug user, record the user
+  // for propagation.
   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
     if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
+      if (!IsDebug) {
         LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
         MaybeDeadCopies.remove(Copy);
+      } else {
+        CopyDbgUsers[Copy].push_back(&Reader);
+      }
     }
   }
 }
 
 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
 /// This fact may have been obscured by sub register usage or may not be true at
 /// all even though Src and Def are subregisters of the registers used in
 /// PreviousCopy. e.g.
if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(),
 
       forwardUses(*MI);
 
       // Src may have been changed by forwardUses()
       Src = MI->getOperand(1).getReg();
 
       // If Src is defined by a previous copy, the previous copy cannot be
       // eliminated.
-      ReadRegister(Src);
+      ReadRegister(Src, *MI);
       for (const MachineOperand &MO : MI->implicit_operands()) {
         if (!MO.isReg() || !MO.readsReg())
           continue;
         unsigned Reg = MO.getReg();
         if (!Reg)
           continue;
-        ReadRegister(Reg);
+        ReadRegister(Reg, *MI);
       }
 
       LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
 
       // Copy is now a candidate for deletion.
       if (!MRI->isReserved(Def))
         MaybeDeadCopies.insert(MI);
 
for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
     // Clobber any earlyclobber regs first.
     for (const MachineOperand &MO : MI->operands())
       if (MO.isReg() && MO.isEarlyClobber()) {
         unsigned Reg = MO.getReg();
         // If we have a tied earlyclobber, that means it is also read by this
         // instruction, so we need to make sure we don't remove it as dead
         // later.
         if (MO.isTied())
-          ReadRegister(Reg);
+          ReadRegister(Reg, *MI);
         Tracker.clobberRegister(Reg, *TRI);
       }
 
     forwardUses(*MI);
 
     // Not a copy.
     SmallVector<unsigned, 2> Defs;
     const MachineOperand *RegMask = nullptr;
     for (const MachineOperand &MO : MI->operands()) {
       if (MO.isRegMask())
         RegMask = &MO;
       if (!MO.isReg())
         continue;
       unsigned Reg = MO.getReg();
       if (!Reg)
         continue;
 
       assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
              "MachineCopyPropagation should be run after register allocation!");
 
       if (MO.isDef() && !MO.isEarlyClobber()) {
         Defs.push_back(Reg);
         continue;
-      } else if (!MO.isDebug() && MO.readsReg())
-        ReadRegister(Reg);
+      } else if (MO.readsReg())
+        ReadRegister(Reg, *MI, MO.isDebug());
     }
 
     // The instruction has a register mask operand which means that it clobbers
     // a large set of registers.  Treat clobbered registers the same way as
     // defined registers.
     if (RegMask) {
       // Erase any MaybeDeadCopies whose destination register is clobbered.
       for (SmallSetVector<MachineInstr *, 8>::iterator DI =
if (RegMask) {
         LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
                    MaybeDead->dump());
 
         // Make sure we invalidate any entries in the copy maps before erasing
         // the instruction.
         Tracker.clobberRegister(Reg, *TRI);
 
         // erase() will return the next valid iterator pointing to the next
         // element after the erased one.
         DI = MaybeDeadCopies.erase(DI);
         MaybeDead->eraseFromParent();
         Changed = true;
         ++NumDeletes;
       }
     }
 
     // Any previous copy definition or reading the Defs is no longer available.
     for (unsigned Reg : Defs)
       Tracker.clobberRegister(Reg, *TRI);
   }
 
   // If MBB doesn't have successors, delete the copies whose defs are not used.
   // If MBB does have successors, then conservative assume the defs are live-out
   // since we don't want to trust live-in lists.
   if (MBB.succ_empty()) {
     for (MachineInstr *MaybeDead : MaybeDeadCopies) {
       LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
                  MaybeDead->dump());
       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
 
-      // Update matching debug values.
+      // Update matching debug values, if any.
       assert(MaybeDead->isCopy());
-      MaybeDead->changeDebugValuesDefReg(MaybeDead->getOperand(1).getReg());
+      unsigned SrcReg = MaybeDead->getOperand(1).getReg();
+      for (auto DbgUser : CopyDbgUsers[MaybeDead]) {
+        assert(DbgUser->getOperand(0).isReg());
+        DbgUser->getOperand(0).setReg(SrcReg);
+      }
 
       MaybeDead->eraseFromParent();
       Changed = true;
       ++NumDeletes;
     }
   }
 
   MaybeDeadCopies.clear();
+  CopyDbgUsers.clear();
   Tracker.clear();
 }
 
 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   Changed = false;

test/CodeGen/MIR/X86/pr38773.mir

bb.2.sw.bb1:
   
     $eax = MOV32ri 4
     $edx = MOV32r0 implicit-def dead $eflags
     IDIV32r killed renamable $ecx, implicit-def $eax, implicit-def dead $edx, implicit-def dead $eflags, implicit $eax, implicit killed $edx
     renamable $ecx = COPY $eax
     ; CHECK:        IDIV32r killed renamable $ecx
     ; CHECK-NEXT:   DBG_VALUE $eax, $noreg, !12, !DIExpression(), debug-location !13
     DBG_VALUE $ecx, $noreg, !12, !DIExpression(), debug-location !13
+    ; The following mov and DBG_VALUE have been inserted after the PR was
+    ; resolved to check that MCP will update debug users that are not
+    ; immediately after the dead copy.
+    ; CHECK-NEXT:   $edx = MOV32r0
+    $edx = MOV32r0 implicit-def dead $eflags
+    ; CHECK-NEXT:   DBG_VALUE $eax, $noreg, !12, !DIExpression(), debug-location !13
+    DBG_VALUE $ecx, $noreg, !12, !DIExpression(), debug-location !13
     $eax = COPY killed renamable $ecx
     RET 0, $eax
 
 ...