[MCP] Invalidate copy for super register in copy source

[jrbyrnes]

Summary

We must also track the super sources of a copy, otherwise we introduce a sort of subtle bug.

Consider:

1. DEF r0:r1
2. USE r1
3. r6:r9 = COPY r10:r13
4. r14:15 = COPY r0:r1
5. USE r6

6.. r1:4 = COPY r6:9

BackwardCopyPropagateBlock processes the instructions from bottom up. After processing 6., we will have propagatable copy for r1-r4 and r6-r9. After 5., we invalidate and erase the propagatble copy for r1-r4 and r6 but not for r7-r9.

The issue is that when processing 3., data structures still say we have valid copies for dest regs r7-r9 (from 6.). The corresponding defs for these registers in 6. are r1:r4, which we mark as registers to invalidate. When invalidating, we find the copy that corresponds to r1 is 4. (this was added when processing 4.), and we say that r1 now maps to unpropagatable copies. Thus, when we process 2., we do not have a valid copy, but when we process 1. we do -- because the mapped copy for subregister r0 was never invalidated.

The net result is to propagate the copy from 4. to 1., and replace DEF r0:r1 with DEF r14:r15. Then, we have a use before def in 2.

The main issue is that we have an inconsitent state between which def regs and which src regs are valid. When processing 5., we mark all the defs in 6. as invalid, but only the subreg use as invalid. Either we must only invalidate the individual subreg for both uses and defs, or the super register for both.

[arsenm]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

191–192

Can we track all of this in regunits? Following registers is way more confusing

209

I don't see how SrcRegs is used any differently. Should this just use a more normal looking liveness scan where there's only one set and each def removes the live uses?

llvm/test/CodeGen/AMDGPU/mcp-use-before-def.mir

28–29

Leftover?

[lkail]

5: USE r6
6: r1:4 = COPY r6:9

Hi @jrbyrnes , do you know why MCP fails to invalidate r7:r9 at label 5? In my view, when we are invalidating r6 at label 5, we should also find the copy involving def or use of r6 which is label 6, and invalidate the regunits of both src operands(r6:r9) and dest operands(r1:r4), which is what invalidateRegister doing.

          RegsToInvalidate.insert(
              CopyOperands->Destination->getReg().asMCReg());
          RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
...
    for (MCRegister InvalidReg : RegsToInvalidate)
      for (MCRegUnit Unit : TRI.regunits(InvalidReg))
        Copies.erase(Unit);

[jrbyrnes]

In D157564#4575259, @lkail wrote:

5: USE r6
6: r1:4 = COPY r6:9

Hi @jrbyrnes , do you know why MCP fails to invalidate r7:r9 at label 5? In my view, when we are invalidating r6 at label 5, we should also find the copy involving def or use of r6 which is label 6, and invalidate the regunits of both src operands(r6:r9) and dest operands(r1:r4), which is what invalidateRegister doing.

          RegsToInvalidate.insert(
              CopyOperands->Destination->getReg().asMCReg());
          RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
...
    for (MCRegister InvalidReg : RegsToInvalidate)
      for (MCRegUnit Unit : TRI.regunits(InvalidReg))
        Copies.erase(Unit);

We only insert the MI corresponding to the copies for tracking the defs

for (MCRegUnit Unit : TRI.regunits(Def))
  Copies[Unit] = {MI, nullptr, {}, {}, true};

// Remember source that's copied to Def. Once it's clobbered, then
// it's no longer available for copy propagation.
for (MCRegUnit Unit : TRI.regunits(Src)) {
  auto I = Copies.insert({Unit, {nullptr, nullptr, {}, {}, false}});
  auto &Copy = I.first->second;
  if (!is_contained(Copy.DefRegs, Def))
    Copy.DefRegs.push_back(Def);
  if (!is_contained(Copy.SrcRegs, Src))
    Copy.SrcRegs.push_back(Src);
  Copy.LastSeenUseInCopy = MI;
}

Then, when calling invalidateRegister for the r6 in label 5, it is unable to find an MI in the CopyTracker. Thus

if (MachineInstr *MI = I->second.MI) {
  std::optional<DestSourcePair> CopyOperands =
      isCopyInstr(*MI, TII, UseCopyInstr);
  assert(CopyOperands && "Expect copy");

  RegsToInvalidate.insert(
      CopyOperands->Destination->getReg().asMCReg());
  RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
}

is never reached. I don't claim to understand why it was designed this way, but, from the perspective of this example, it seems that we should also be tracking this.

[lkail]

We only insert the MI corresponding to the copies for tracking the defs

I see. I think the semantic of Copy[Unit].MI is the COPY defines Unit, forward propagation should be relying on this semantic.

Instead, Can Copy[Unit].LastSeenUseInCopy, which has the semantic of the most recent COPY tracked uses the Unit, help this case? In invalidateRegister,

if (MachineInstr *MI = I->second.MI) {...}
if (MachineInstr *MI = I->second.LastSeenUseInCopy) {...}

[jrbyrnes]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

209

I don't see how SrcRegs is used any differently.

MCP currently works s.t. if a source or dest of some MI partially overlaps the source or dest of an active, then we say that the copy is no longer active across all its def regunits. In other words, we don't allow partial copy propagation. This is what Copy.DefRegs is used for, if we come across an MI with regunit that partially overlaps with some previous copy, we query the map to get the Copy structure, then we invalidate it for all the RegUnit in Def where Def is just the dest register in the actual copy.

However, we don't do the same for the src RegUnits of the copy. Enabling such is the intention behind Copy.SrcRegs. As is, if an MI has registers (B) which partially overlaps the source of a Copy (A), a subsequent MI will find that Copy is still active if it has registers that are in the difference A - B.

In short, Copy.SrcRegs holds the Source Reg of the copy, so that when we mark a copy as invalid, we can do so across all regunits in its source.

Should this just use a more normal looking liveness scan where there's only one set and each def removes the live uses

The tracker for backwardCopyProp really needs to track 3 things:

1. "Activeness" of the uses of the copies. This is really just liveness, however any partial clobbering should say the full set of RegUnits involved in the use is inactive.
2. Validity of propagation --
   1. Uses of copy uses - if we want to propagate a copy backwards, then we will replace DEF A; B = COPY A with -> DEF B. But, if there are any uses of A between the DEF and the COPY then the propagation is not longer valid.
   2. Uses of copy defs - If we have done the above propagation, and there is a user of B between the propagation site and the COPY, then we will have clobbered.

I think we can identify 1 and 2A with a tracker that does something that looks like a backwards liveness scan, however, I don't think we can capture 2B.

[jrbyrnes]

Use LastSeenUseInCopy + use regunits in more places.

llvm/lib/CodeGen/MachineCopyPropagation.cpp

191–192

There are many places that use register MCRegister equality / isSubRegisterEq on CopyOperands->Destination / Source. In order to prove equality for regunits, we would need to iteratively do set equality which seems like it would make things more complicated. Maybe I've missed something?

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

153–154

diff
@@ -137,18 +137,20 @@ public:
     // and invalidate all of them.
     SmallSet<MCRegister, 8> RegsToInvalidate;
     RegsToInvalidate.insert(Reg);
+    auto invalidate = [&](MachineInstr *MI) {
+      std::optional<DestSourcePair> CopyOperands =
+          isCopyInstr(*MI, TII, UseCopyInstr);
+      assert(CopyOperands && "Expect copy");
+      RegsToInvalidate.insert(CopyOperands->Destination->getReg().asMCReg());
+      RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
+    };
     for (MCRegUnit Unit : TRI.regunits(Reg)) {
       auto I = Copies.find(Unit);
       if (I != Copies.end()) {
-        if (MachineInstr *MI = I->second.MI) {
-          std::optional<DestSourcePair> CopyOperands =
-              isCopyInstr(*MI, TII, UseCopyInstr);
-          assert(CopyOperands && "Expect copy");
-
-          RegsToInvalidate.insert(
-              CopyOperands->Destination->getReg().asMCReg());
-          RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
-        }
+        if (MachineInstr *MI = I->second.MI)
+          invalidate(MI);
+        if (MachineInstr *MI = I->second.LastSeenUseInCopy)
+          invalidate(MI);
         RegsToInvalidate.insert(I->second.DefRegs.begin(),
                                 I->second.DefRegs.end());
       }

We should check both of I->second.MI and I->second.LastSeenUseInCopy.

191–192

I agree with that we should track at regunit basis. Maybe we can do that in another NFC patch.

[jrbyrnes]

Always try to invalidate both the LastSeenUseInCopy and CopyInfo->MI.

With regard to the regunits conversion --- Should we keep the partial work in this patch, or save it all for a separate patch?

[lkail]

Should we keep the partial work in this patch, or save it all for a separate patch?

We'd better use another NFC patch to track at regunit basis.

[jrbyrnes]

Delete partial conversion to regunits

[jrbyrnes]

Convert RegsToInvalidate back to MCRegister as well.

[lkail]

LGTM with nit.

llvm/lib/CodeGen/MachineCopyPropagation.cpp

139

nit: RegsToInvalidate -> RegUnitsToInvalidate.

[jrbyrnes]

RegUnitsToInvalidate

[jrbyrnes]

f76ffc1f406ecdb5a8329e8a10a56f0ce2f6220c

llvm/lib/CodeGen/MachineCopyPropagation.cpp

void markRegsUnavailable(ArrayRef<MCRegister> Regs,
     }
   }
 
   /// Remove register from copy maps.
   void invalidateRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
                           const TargetInstrInfo &TII, bool UseCopyInstr) {
     // Since Reg might be a subreg of some registers, only invalidate Reg is not
     // enough. We have to find the COPY defines Reg or registers defined by Reg
-    // and invalidate all of them.
-    SmallSet<MCRegister, 8> RegsToInvalidate;
-    RegsToInvalidate.insert(Reg);
-    for (MCRegUnit Unit : TRI.regunits(Reg)) {
-      auto I = Copies.find(Unit);
-      if (I != Copies.end()) {
-        if (MachineInstr *MI = I->second.MI) {
-          std::optional<DestSourcePair> CopyOperands =
-              isCopyInstr(*MI, TII, UseCopyInstr);
-          assert(CopyOperands && "Expect copy");
+    // and invalidate all of them. Similarly, we must invalidate all of the
+    // the subregisters used in the source of the COPY.
+    SmallSet<MCRegUnit, 8> RegUnitsToInvalidate;
+    auto InvalidateCopy = [&](MachineInstr *MI) {
 
-          RegsToInvalidate.insert(
-              CopyOperands->Destination->getReg().asMCReg());
-          RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
-        }
-        RegsToInvalidate.insert(I->second.DefRegs.begin(),
-                                I->second.DefRegs.end());
+      auto Dest = TRI.regunits(CopyOperands->Destination->getReg().asMCReg());
+      auto Src = TRI.regunits(CopyOperands->Source->getReg().asMCReg());
+      RegUnitsToInvalidate.insert(Dest.begin(), Dest.end());
+      RegUnitsToInvalidate.insert(Src.begin(), Src.end());
+    };
+
+    for (MCRegUnit Unit : TRI.regunits(Reg)) {
+      auto I = Copies.find(Unit);
+      if (I != Copies.end()) {
+        if (MachineInstr *MI = I->second.MI)
+          InvalidateCopy(MI);
+        if (MachineInstr *MI = I->second.LastSeenUseInCopy)
+          InvalidateCopy(MI);
       }
     }
-    for (MCRegister InvalidReg : RegsToInvalidate)
-      for (MCRegUnit Unit : TRI.regunits(InvalidReg))
-        Copies.erase(Unit);
+    for (MCRegUnit Unit : RegUnitsToInvalidate)
   }
 
   /// Clobber a single register, removing it from the tracker's copy maps.
   void clobberRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
                        const TargetInstrInfo &TII, bool UseCopyInstr) {
     for (MCRegUnit Unit : TRI.regunits(Reg)) {
       auto I = Copies.find(Unit);
       if (I != Copies.end()) {
public:
 
   /// Add this copy's registers into the tracker's copy maps.
   void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI,
                  const TargetInstrInfo &TII, bool UseCopyInstr) {
     std::optional<DestSourcePair> CopyOperands =
         isCopyInstr(*MI, TII, UseCopyInstr);
     assert(CopyOperands && "Tracking non-copy?");
 
     MCRegister Src = CopyOperands->Source->getReg().asMCReg();
     MCRegister Def = CopyOperands->Destination->getReg().asMCReg();
 
     // Remember Def is defined by the copy.
     for (MCRegUnit Unit : TRI.regunits(Def))
       Copies[Unit] = {MI, nullptr, {}, true};
 
     // Remember source that's copied to Def. Once it's clobbered, then
     // it's no longer available for copy propagation.
     for (MCRegUnit Unit : TRI.regunits(Src)) {
       auto I = Copies.insert({Unit, {nullptr, nullptr, {}, false}});
       auto &Copy = I.first->second;
       if (!is_contained(Copy.DefRegs, Def))
         Copy.DefRegs.push_back(Def);
       Copy.LastSeenUseInCopy = MI;
     }
   }
 
   bool hasAnyCopies() {
     return !Copies.empty();
   }
 
   MachineInstr *findCopyForUnit(MCRegister RegUnit,
                                 const TargetRegisterInfo &TRI,

llvm/test/CodeGen/AMDGPU/mcp-use-before-def.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=amdgcn-amd-amdhsa -verify-machineinstrs  -run-pass=machine-cp -o - %s | FileCheck %s
+
+# machine copy prop should not introduce use before def
+---
+name: back_copy_block
+body:           |
+  bb.0:
+    ; CHECK-LABEL: name: back_copy_block
+    ; CHECK: $vgpr20_vgpr21_vgpr22_vgpr23 = IMPLICIT_DEF
+    ; CHECK-NEXT: $vgpr10_vgpr11_vgpr12_vgpr13 = IMPLICIT_DEF
+    ; CHECK-NEXT: renamable $vgpr0_vgpr1 = V_MOV_B64_e64 killed $vgpr20_vgpr21, implicit $exec
+    ; CHECK-NEXT: renamable $vgpr20 = V_MOV_B32_e32 killed $vgpr1, implicit $exec
+    ; CHECK-NEXT: renamable $vgpr6_vgpr7_vgpr8_vgpr9 = COPY renamable $vgpr10_vgpr11_vgpr12_vgpr13
+    ; CHECK-NEXT: renamable $vgpr20 = V_MOV_B32_e32 killed $vgpr6, implicit $exec
+    ; CHECK-NEXT: S_ENDPGM 0, amdgpu_allvgprs
+    $vgpr20_vgpr21_vgpr22_vgpr23 = IMPLICIT_DEF
+    $vgpr10_vgpr11_vgpr12_vgpr13 = IMPLICIT_DEF
+    renamable $vgpr0_vgpr1 = V_MOV_B64_e64 killed renamable $vgpr20_vgpr21, implicit $exec
+    renamable $vgpr20 = V_MOV_B32_e32 killed renamable $vgpr1, implicit $exec
+    renamable $vgpr6_vgpr7_vgpr8_vgpr9 = COPY killed renamable $vgpr10_vgpr11_vgpr12_vgpr13
+    renamable $vgpr14_vgpr15 = COPY killed renamable $vgpr0_vgpr1
+    renamable $vgpr20 = V_MOV_B32_e32 killed renamable $vgpr6, implicit $exec
+    renamable $vgpr1_vgpr2_vgpr3_vgpr4 = COPY killed renamable $vgpr6_vgpr7_vgpr8_vgpr9
+    S_ENDPGM 0, amdgpu_allvgprs
+...