[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 ↗

(On Diff #180037)

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 ↗

(On Diff #180037)

We can indeed, uploading a new version now.

[aprantl]

lib/CodeGen/MachineCopyPropagation.cpp

211 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

May be a more descriptive comment; something like:

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

246 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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 ↗

(On Diff #180217)

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

603 ↗

(On Diff #181801)

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

llvm/trunk/include/llvm/CodeGen/MachineRegisterInfo.h

&getRegAllocationHints(unsigned VReg) const {
     return RegAllocHints[VReg];
   }
 
   /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
   /// specified register as undefined which causes the DBG_VALUE to be
   /// deleted during LiveDebugVariables analysis.
   void markUsesInDebugValueAsUndef(unsigned Reg) const;
 
+  /// updateDbgUsersToReg - Update a collection of DBG_VALUE instructions
+  /// to refer to the designated register.
+  void updateDbgUsersToReg(unsigned Reg,
+                           ArrayRef<MachineInstr*> Users) const {
+    for (MachineInstr *MI : Users) {
+      assert(MI->isDebugInstr());
+      assert(MI->getOperand(0).isReg());
+      MI->getOperand(0).setReg(Reg);
+    }
+  }
+
   /// Return true if the specified register is modified in this function.
   /// This checks that no defining machine operands exist for the register or
   /// any of its aliases. Definitions found on functions marked noreturn are
   /// ignored, to consider them pass 'true' for optional parameter
   /// SkipNoReturnDef. The register is also considered modified when it is set
   /// in the UsedPhysRegMask.
   bool isPhysRegModified(unsigned PhysReg, bool SkipNoReturnDef = false) const;
 

llvm/trunk/lib/CodeGen/MachineCopyPropagation.cpp

public:
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoVRegs);
   }
 
 private:
+  typedef enum { DebugUse = false, RegularUse = true } DebugType;
+
   void ClobberRegister(unsigned Reg);
-  void ReadRegister(unsigned Reg);
+  void ReadRegister(unsigned Reg, MachineInstr &Reader,
+                    DebugType DT);
   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;
 
+  /// Multimap tracking debug users in current BB
+  DenseMap<MachineInstr*, SmallVector<MachineInstr*, 2>> 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,
+                                          DebugType DT) {
   // 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 (DT == RegularUse) {
         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, RegularUse);
       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, RegularUse);
       }
 
       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, RegularUse);
         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(!Register::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() ? DebugUse : RegularUse);
     }
 
     // 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 =
void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
   // 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();
+      MRI->updateDbgUsersToReg(SrcReg, CopyDbgUsers[MaybeDead]);
 
       MaybeDead->eraseFromParent();
       Changed = true;
       ++NumDeletes;
     }
   }
 
   MaybeDeadCopies.clear();
+  CopyDbgUsers.clear();
   Tracker.clear();
 }
 
 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   Changed = false;

llvm/trunk/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
 
 ...