[MachineCopyPropagation] Eliminate spillage copies that might be caused by eviction chain

[lkail]

Summary

Remove spill-reload like copy chains. For example

r0 = COPY r1
r1 = COPY r2
r2 = COPY r3
r3 = COPY r4
<def-use r4>
r4 = COPY r3
r3 = COPY r2
r2 = COPY r1
r1 = COPY r0

will be folded into

r0 = COPY r1
r1 = COPY r4
<def-use r4>
r4 = COPY r1
r1 = COPY r0

[qcolombet]

At first glance it looks similar to what @aditya_nandakumar implemented internally to get rid of copies produced by eviction chains.

@aditya_nandakumar could you take a look?

[qcolombet]

Talked to Aditya offline (a while back actually) and he told me he doesn't expect to have time to look at this any time soon.
Adding myself as a reviewers.

[qcolombet]

Hi @lkail ,

Thanks for your patience.
This goes in the right direction.

I think we miss a few comments and some cleanups (clang-format, remove stall comments, use proper LLVM_DEBUG macros, etc.) and we're good to go!

Cheers,
-Quentin

llvm/lib/CodeGen/MachineCopyPropagation.cpp

1057

Add comments.
What this does: explain the algorithm at a high level.

1065

Not for this patch, but you may want to use isCopyInstr instead of isCopy to catch more cases.
That said, it probably won't make much of a difference, since in particular most copies you're trying to remove here comes from splitting in regalloc (i.e., we'll have plain COPY).

1065

To be on the safe side, you may want to check that the operation has no implicit operand.

1072

Instead of copying the chain, can we hold on to the reference until we're done with the processing?

1079

Maybe worth splitting the reload from the spill chain as this assert is strange at first glance.
Perhaps it wouldn't be as problematic when the method is properly documented.

Put differently, let's leave it like this for now, add a bunch of comments and we'll see if it still feels weird after that.

1082

We'll need to expand on that commet because naively, a 2 pairs chain would be beneficial to remove, but this is not something this code can do since we don't recolor outside of the spill chain.

I'd suggest putting something like: We need at least 3 pairs of copies for the transformation to apply, because the first outermost pair cannot be removed since we don't recolor outside of the chain and that we need at least one temporary spill slot to shorten the chain.
If we only have a chain of two pairs, we already have the shortest sequence this code can handle: the outermost pair for the temporary spill slot, and the pair that use that temporary spill slot for the other end of the chain.

1094

Here and other places where you have "debug" statements:
Put this in LLVM_DEBUG macros.
Or remove completely.

1099

Move that into its own helper function and call it from an assert.

static bool LLVM_ATTRIBUTE_UNUSED isValidChain(const SmallVectorImpl<MachineInstr *> &Chain) {
  // your checks here.
}
...
assert(isValidChain(Chain) && "Invalid chain to process");

1104

I feel that this is a bit late to check that.
We should not put a copy in the "candidate" chains if the copy is not foldable.

I would suggest to handle that in the main loop.

1111

By construction Chain[Len - 4]->getOperand(0) == Chain[Len - 3]->getOperand(1), so I would instead put that in a variable and use it in both places.

E.g., something like:

// Pull the last spill slot used only within the chain as the final spill slot.
MCRegister LastReusableRegSpillSlot = Chain[Len - 4]->getOperand(0).getReg()
// Update the chain to skip all the intermediate register spill slots:
// Spilling:
Chain[0]->getOperand(0).setReg(LastReusableRegSpillSlot);
// Reload:
Chain[1]->getOperand(1).setReg(LastReusableRegSpillSlot);

1113

Maybe be worth adding a comment here that although the variable is called MaybeDeadCopies, we really are going to remove the related instructions.

The fact that we use MaybeDeadCopies to do our code cleanup is slightly confusing because if we don't actually delete the intermediate copies (a.k.a. what remains of the chain at this point) the resulting code would be incorrect.

1178

At first it is strange to see that we look for a copy when Reg is a def, but I guess it makes sense because:

1. We are not going to recolor Reg
2. We need to consider this chain before it gets clobbered later in that same loop

Assuming I understood that correctly, it deserves its comment here.

1186

Use LeadRegs.find and avoid the double lookups (one in count and one in operator[]).

1196

I think this statement deserves its own comment.
IIUC here we unconditionally clobber all the registers (as opposed to only clobbering the definitions) because we only rewrite the chain itself (i.e., we don't attempt to rewrite uses after the chain).

BTW, you need to take into account regmasks too.

1196

Shouldn't we clear the SpillChains here for defs and not-preversed-by-regmasks regs at this point?

llvm/test/CodeGen/PowerPC/mcp-elim-eviction-chain.mir

135

Add a test with regmasks.

[lkail]

Hi @qcolombet , thanks for your detail comments. I have uploaded another patch which is very different from previous one. Not sure I have addressed all your comments.

[lkail]

Ping.

[lkail]

Gentle ping.

[qcolombet]

Hi @lkail,

I am halfway through.

I'm sharing my comments so far if you want to get started with some of the nitpicks.

Cheers,
-Quentin

llvm/lib/CodeGen/MachineCopyPropagation.cpp

108

Maybe rename in LastSeenUseInCopy.

Essentially, I would avoid LastUse alone as it carries a lot of expected semantic that I don't think apply here.

199

Use MI directly here instead of adding it line 200.

293

Could Current be const here?

312

If Def is clobbered between DefCopy and Current I would have expected that DefCopy would have been removed from Copies.

Put differently, I feel that if we have to check that here, the Copies map is holding hard-to-reason-about information.

Are we missing some call to clobberRegister?

1064

I think you can simplify this with a range based loop with rbegin/rend.

1065

That should be a simple range based loop:

for (const MachineInstr *MI: RC)
  MI->dump();

1084

Technically we could collapse this sequence to:

// r0 = COPY r4
// <def-use r4>
// r4 = COPY r0

I.e., I think it is worth explaining that the propagation doesn't check whether or not r0 can be altered outside of the chain and that's why we conservatively keep its value as it was before the rewrite. (Would be a nice follow-up fix BTW :)).

1087

Typo: until

1087

typo: chain uses

1100

typo: encountered

1105

That sounds weird.
Would you mind sharing the assertion?

1107

Could you add a comment on what the mappings hold (all three of them)?

I haven't read the code past this point yet, but for instance I would have expected that the key in these maps would be a Register not MachineInstr.

1108

typo: until

1110

Instead of tracking that, should we just invalidate the chain / stop it before that point?

1123

Maybe add a todo that if the outermost pair of copies modifies a register that is dead outside of that pair, we could eliminate one more pair.

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

199

Correct me if I'm woring, Copies.insert insert successfully only when the key doesn't exist before. Suppose we have

L0: R0 = COPY R1
L1: R2 = COPY R1

LastUseSeenInCopy should track MI in L1 rather than L0.

312

I can imagine there might be some RegMasks doesn't implicit def any registers, just clobber them. When we are traversing the MBB and are encountered with a RegMask without any other implicit-def, we don't know which register to clobber directly. I'm not sure we have a way to enumerate registers a RegMask clobbers. If there is such a way, I think we should clobber registers when we are traversing the MBB, not checking RegMask clobbers here.

1105

It hits DenseMapIterator's

  pointer operator->() const {
    assert(isHandleInSync() && "invalid iterator access!");
...
  }

I dived into it a bit, looks it's checking the validity of the iterator, i.e., if the container is updated, the iterator constructed before the update is invalid.
Code like

        auto Leader = ChainLeader.find(MaybePrevReload);
...
        ChainLeader.insert({MaybeSpill, Leader->second});
        ChainLeader.insert({&MI, Leader->second});

Should be avoided.

1107

I haven't read the code past this point yet, but for instance I would have expected that the key in these maps would be a Register not MachineInstr.

I separate the algorithm implementation in to two stages. stage1: Collect spill-reload chains. stage2: Fold the chains. If using Register, we are unable to track different spill-reload chains that share same registers.

1110

The implementation doesn't invalidate any chain in stage1. Compared to previous implementation, I think current one is easier to reason and easier to maintain. When we are iterating MI inside the MBB, we don't know which COPY might be one of the innermost spill-reload pair and we don't want to lose track of the innermost spill-reload pair. The Source of the innermost spill is allowed to be re-use and re-def between the innermost spill-reload pair.

[lkail]

Address comments.

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

1084

Maybe we can check if r0 is killed to remove one more COPY.

[qcolombet]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

199

Ah good point!

312

I think I see our misunderstanding.
Given the name of the function I would expect that this function only does some queries on the tracker, but you're actually using this function to do some bookkeeping as well.

So the conclusion is either rename this function to more accurately represents what it does (I don't have a good name for now) or move the bookkeeping in the main loop (i.e., I thought we were calling clobberRegister from the main loop already.)

Regarding your comment on RegMasks, I am not sure I follow:

• RegMasks always list all the registers they preserve/clobber
• Liveness sets at basic block boundaries are not represented with RegMasks, but anyway we don't care because the tracking is always purely local to a basic block in that pass. (Unless you've changed that and I missed it :)).

1064

You should be able to use an even more compact form:

for (auto I : make_range(SC.rbegin(), SC.rend())

1084

Yep, but for that to be accurate we would need to flip the direction of the analysis (from top-down, to bottom-up) to get proper liveness construction.
(Or use the kill flag, but generally speaking we try to avoid relying on this.)

1105

Yep, every time you insert something in the dense map, you may invalidate the iterators.

1107

I see, make sense.

[lkail]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

312

RegMasks always list all the registers they preserve/clobber

Ah, I see. Is it a good idea to enumerate them via TRI->getNumRegs() and check RegMask to see if they are preserve/clobber?

For the origin question

If Def is clobbered between DefCopy and Current I would have expected that DefCopy would have been removed from Copies.

Does it imply we should not check RegMask and don't update bookkeeping by calling Tracker::clobberRegister here, checking if RegMask clobbers registers should already have been conducted in the main loop?

Correct me if I still fail to get your point.

[qcolombet]

llvm/lib/CodeGen/MachineCopyPropagation.cpp

312

Ah, I see. Is it a good idea to enumerate them via TRI->getNumRegs() and check RegMask to see if they are preserve/clobber?

That's the idea. Though we wouldn't need to enumerate all the registers, only the ones that you care about.
What you're doing here is already fine.

The thing that bothers me in the current code is the call to clobberRegister. This modifies the state of the tracker. Usually the find methods only query the RegMasks directly (with MachineOperand::clobbersPhysReg).

Correct me if I still fail to get your point.

You got the point.
Let's keep the code as is for now and let me do a full pass on the code so that I have a better model of how the whole things works.

I'll probably won't have time to do it before next week though.

[qcolombet]

Hi @lkail,

Thanks for your patience.

Looks mostly good to me.

The only thing that makes me uneasy is the potential impact on compile time of CheckCopyConstraint.
Do you know on average how many chains we see per function?

I know we have a bot tracking compile time. If that doesn't show anything significant, I guess we could enable it by default. I just don't know how extensive the tests are.

Alternatively, to avoid surprising everybody, we could add a way to enable/disable the new folding.
Either like what was done with UseCopyInstr or with a target hook (you can add a command line option too that would override what the target asked for for testing purposes).

Then only enabled it for your target and send an RFC asking people to try the new folding for their targets.

What do you think?

Cheers,
-Quentin

llvm/lib/CodeGen/MachineCopyPropagation.cpp

1118

Nit: const on MachineInstr*

1138

You should be able to use a range loop:

for (const MachineInstr *Spill : SC) {
    if (CopySourceInvalid.count(Spill))
            return;
}

1143

Nit: range loop

1149

That's going to be pretty expensive to walk all the register classes.
I'm guessing you're trying to check if the resulting copy is legal and unfortunately there's no good way to do that.

Did you see that showing up in compile time profile?

1179

Nit: range loop

1188

Nit: Here and other places where you use isCopyInstr: use the explicit type instead of auto. (The return type is hard to infer.)

[lkail]

Add target hook and command line option.

[lkail]

Do you know on average how many chains we see per function?

I have run llvm-test-suite, here's the stats

	functions	spill chain length	avg spill chain length per function	max spill chain length in one CU	number of spill chains	avg number of spill chains per function	max number of spill chains in one CU
powerpc64-ibm-aix	60426	308	0.005097143613676	52	27	0.000446827524576	3
x86_64-linux-gnu	185938	646	0.003474276371694	130	80	0.000430250943863	14

Compile time on powerpc64-ibm-aix

Tests: 1039
Metric: compile_time

Program                                       compile_time           
                                              baseline     experiment
SingleSour...sts/2002-10-09-ArrayResolution     0.07         0.50    
MultiSourc...marks/Trimaran/enc-pc1/enc-pc1     0.14         0.86    
SingleSour...e/UnitTests/2002-10-13-BadLoad     0.06         0.38    
SingleSour...UnitTests/2002-08-02-CastTest2     0.06         0.37    
SingleSour...nitTests/2002-04-17-PrintfChar     0.06         0.36    
SingleSour.../UnitTests/conditional-gnu-ext     0.07         0.23    
MultiSource/Benchmarks/llubenchmark/llu         0.10         0.35    
SingleSour...tTests/2003-08-05-CastFPToUint     0.06         0.22    
SingleSour...nitTests/2003-05-31-LongShifts     0.07         0.22    
SingleSour...e/UnitTests/Vector/Altivec/lde     0.21         0.68    
SingleSource/UnitTests/blockstret               0.06         0.18    
SingleSour...e/UnitTests/2002-05-03-NotTest     0.07         0.21    
SingleSour...UnitTests/2002-05-02-CastTest2     0.07         0.20    
SingleSour...UnitTests/2003-08-11-VaListArg     0.15         0.43    
SingleSource/UnitTests/StructModifyTest         0.07         0.19    
      compile_time             
run       baseline   experiment
count  1039.000000  1039.000000
mean   1.108578     1.102223   
std    4.496574     4.384102   
min    0.000000     0.000000   
25%    0.000000     0.000000   
50%    0.000000     0.000000   
75%    0.276350     0.278450   
max    80.927800    77.030800

Compile time on x86_64-linux-gnu

Tests: 2991
Metric: compile_time

Program                                       compile_time           
                                              baseline     experiment
UnitTests/...9-04-16-BitfieldInitialization     0.00         0.02    
UnitTests/2002-04-17-PrintfChar                 0.00         0.01    
UnitTests/2002-10-13-BadLoad                    0.00         0.01    
UnitTests/block-copied-in-cxxobj-1              0.00         0.01    
UnitTests/testcase-ExprConstant-1               0.01         0.02    
UnitTests/2010-05-24-BitfieldTest               0.00         0.01    
UnitTests/block-byref-test                      0.00         0.01    
UnitTests/testcase-Expr-1                       0.01         0.02    
UnitTests/byval-alignment                       0.01         0.02    
Benchmarks/Misc/pi                              0.01         0.02    
UnitTests/block-byref-cxxobj-test               0.01         0.01    
UnitTests/2020-01-06-coverage-008               0.01         0.02    
UnitTests/2002-08-02-CastTest2                  0.01         0.01    
UnitTests/2002-05-03-NotTest                    0.02         0.02    
UnitTests/2005-05-13-SDivTwo                    0.01         0.02    
      compile_time             
l/r       baseline   experiment
count  2991.000000  2991.000000
mean   0.291675     0.291211   
std    2.642554     2.642948   
min    0.000000     0.000000   
25%    0.000000     0.000000   
50%    0.000000     0.000000   
75%    0.000000     0.000000   
max    99.370200    99.510200

I don't see significant compile time regressions.

I just don't know how extensive the tests are.

I have tried bootstrapping stage3 and running llvm-test-suite on powerpc64-ibm-aix and x86_64-linux-gnu, no regression found. I'll follow your advice to send an RFC on discourse, currently I only enable it on PowerPC by default. https://reviews.llvm.org/D122118?id=485466 shows changes in other targets.

[nikic]

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=781eabeb40b8e47e3a46b0b927784e63f0aad9ab&to=0af2744a89bf0ed05e83ac1ed9d21d6d74cdfeca&stat=instructions%3Au

[lkail]

Use range loop.

[lkail]

In D122118#4019373, @nikic wrote:

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=781eabeb40b8e47e3a46b0b927784e63f0aad9ab&to=0af2744a89bf0ed05e83ac1ed9d21d6d74cdfeca&stat=instructions%3Au

Much appreciated for your profiling!

llvm/lib/CodeGen/MachineCopyPropagation.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-cp"
 
 STATISTIC(NumDeletes, "Number of dead copies deleted");
 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
+STATISTIC(NumFunctionsSeen, "Number of functions have seen by MCP");
+STATISTIC(SpillageChainsLength, "Length of spillage chains");
 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
               "Controls which register COPYs are forwarded");
 
 static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false),
                                      cl::Hidden);
 
 namespace {
 
 static std::optional<DestSourcePair> isCopyInstr(const MachineInstr &MI,
                                                  const TargetInstrInfo &TII,
                                                  bool UseCopyInstr) {
   if (UseCopyInstr)
     return TII.isCopyInstr(MI);
 
   if (MI.isCopy())
     return std::optional<DestSourcePair>(
         DestSourcePair{MI.getOperand(0), MI.getOperand(1)});
 
   return std::nullopt;
 }
 
 class CopyTracker {
   struct CopyInfo {
-    MachineInstr *MI;
+    MachineInstr *MI, *LastSeenUseInCopy;
     SmallVector<MCRegister, 4> DefRegs;
     bool Avail;
   };
 
   DenseMap<MCRegister, CopyInfo> Copies;
 
 public:
   /// Mark all of the given registers and their subregisters as unavailable for
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 (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI)
-      Copies[*RUI] = {MI, {}, true};
+      Copies[*RUI] = {MI, nullptr,  {}, true};
 
     // Remember source that's copied to Def. Once it's clobbered, then
     // it's no longer available for copy propagation.
     for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) {
-      auto I = Copies.insert({*RUI, {nullptr, {}, false}});
+      auto I = Copies.insert({*RUI, {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,
for (const MachineInstr &MI :
       for (const MachineOperand &MO : MI.operands())
         if (MO.isRegMask())
           if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
             return nullptr;
 
     return AvailCopy;
   }
 
+  // Find last COPY that defines Reg before Current MachineInstr.
+  MachineInstr *findLastSeenDefInCopy(const MachineInstr &Current,
+                                      MCRegister Reg,
+                                      const TargetRegisterInfo &TRI,
+                                      const TargetInstrInfo &TII,
+                                      bool UseCopyInstr) {
+    MCRegUnitIterator RUI(Reg, &TRI);
+    auto CI = Copies.find(*RUI);
+    if (CI == Copies.end() || !CI->second.Avail)
+      return nullptr;
+
+    MachineInstr *DefCopy = CI->second.MI;
+    std::optional<DestSourcePair> CopyOperands =
+        isCopyInstr(*DefCopy, TII, UseCopyInstr);
+    Register Def = CopyOperands->Destination->getReg();
+    if (!TRI.isSubRegisterEq(Def, Reg))
+      return nullptr;
+
+    for (const MachineInstr &MI :
+         make_range(static_cast<const MachineInstr *>(DefCopy)->getIterator(),
+                    Current.getIterator()))
+      for (const MachineOperand &MO : MI.operands())
+        if (MO.isRegMask())
+          if (MO.clobbersPhysReg(Def)) {
+            LLVM_DEBUG(dbgs() << "MCP: Removed tracking of "
+                              << printReg(Def, &TRI) << "\n");
+            return nullptr;
+          }
+
+    return DefCopy;
+  }
+
+  // Find last COPY that uses Reg.
+  MachineInstr *findLastSeenUseInCopy(MCRegister Reg,
+                                      const TargetRegisterInfo &TRI) {
+    MCRegUnitIterator RUI(Reg, &TRI);
+    auto CI = Copies.find(*RUI);
+    if (CI == Copies.end())
+      return nullptr;
+    return CI->second.LastSeenUseInCopy;
+  }
+
   void clear() {
     Copies.clear();
   }
 };
 
 class MachineCopyPropagation : public MachineFunctionPass {
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
public:
   }
 
 private:
   typedef enum { DebugUse = false, RegularUse = true } DebugType;
 
   void ReadRegister(MCRegister Reg, MachineInstr &Reader, DebugType DT);
   void ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
   void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
+  void EliminateSpillageCopies(MachineBasicBlock &MBB);
   bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
   void forwardUses(MachineInstr &MI);
   void propagateDefs(MachineInstr &MI);
   bool isForwardableRegClassCopy(const MachineInstr &Copy,
                                  const MachineInstr &UseI, unsigned UseIdx);
   bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
                                           const MachineInstr &UseI,
                                           unsigned UseIdx);
for (auto *Copy : MaybeDeadCopies) {
     ++NumDeletes;
   }
 
   MaybeDeadCopies.clear();
   CopyDbgUsers.clear();
   Tracker.clear();
 }
 
+static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain(
+    DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &SpillChain,
+    DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &ReloadChain,
+    MachineInstr *Leader) {
+  auto &SC = SpillChain[Leader];
+  auto &RC = ReloadChain[Leader];
+  for (auto I = SC.rbegin(), E = SC.rend(); I != E; ++I)
+    (*I)->dump();
+  for (MachineInstr *MI : RC)
+    MI->dump();
+}
+
+// Remove spill-reload like copy chains. For example
+// r0 = COPY r1
+// r1 = COPY r2
+// r2 = COPY r3
+// r3 = COPY r4
+// <def-use r4>
+// r4 = COPY r3
+// r3 = COPY r2
+// r2 = COPY r1
+// r1 = COPY r0
+// will be folded into
+// r0 = COPY r1
+// r1 = COPY r4
+// <def-use r4>
+// r4 = COPY r1
+// r1 = COPY r0
+// TODO: Currently we don't track usage of r0 outside the chain, so we
+// conservatively keep its value as it was before the rewrite.
+//
+// The algorithm is trying to keep
+// property#1: No Def of spill COPY in the chain is used or defined until the
+// paired reload COPY in the chain uses the Def.
+//
+// property#2: NO Source of COPY in the chain is used or defined until the next
+// COPY in the chain defines the Source, except the innermost spill-reload
+// pair.
+//
+// The algorithm is conducted by checking every COPY inside the MBB, assuming
+// the COPY is a reload COPY, then try to find paired spill COPY by searching
+// the COPY defines the Src of the reload COPY backward. If such pair is found,
+// it either belongs to an existing chain or a new chain depends on
+// last available COPY uses the Def of the reload COPY.
+// Implementation notes, we use CopyTracker::findLastDefCopy(Reg, ...) to find
+// out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...)
+// to find out last COPY that uses Reg. When we are encountered with a Non-COPY
+// instruction, we check registers in the operands of this instruction. If this
+// Reg is defined by a COPY, we untrack this Reg via
+// CopyTracker::clobberRegister(Reg, ...).
+void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) {
+  // ChainLeader maps MI inside a spill-reload chain to its innermost reload COPY.
+  // Thus we can track if a MI belongs to an existing spill-reload chain.
+  DenseMap<MachineInstr *, MachineInstr *> ChainLeader;
+  // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence
+  // of COPYs that forms spills of a spill-reload chain.
+  // ReloadChain maps innermost reload COPY of a spill-reload chain to a
+  // sequence of COPYs that forms reloads of a spill-reload chain.
+  DenseMap<MachineInstr *, SmallVector<MachineInstr *>> SpillChain, ReloadChain;
+  // If a COPY's Source has use or def until next COPY defines the Source,
+  // we put the COPY in this set to keep property#2.
+  DenseSet<MachineInstr *> CopySourceInvalid;
+
+  auto TryFoldSpillageCopies =
+      [&, this](const SmallVectorImpl<MachineInstr *> &SC,
+                const SmallVectorImpl<MachineInstr *> &RC) {
+        assert(SC.size() == RC.size() && "Spill-reload should be paired");
+
+        // We need at least 3 pairs of copies for the transformation to apply,
+        // because the first outermost pair cannot be removed since we don't
+        // recolor outside of the chain and that we need at least one temporary
+        // spill slot to shorten the chain. If we only have a chain of two
+        // pairs, we already have the shortest sequence this code can handle:
+        // the outermost pair for the temporary spill slot, and the pair that
+        // use that temporary spill slot for the other end of the chain.
+        // TODO: We might be able to simplify to one spill-reload pair if collecting
+        // more infomation about the outermost COPY.
+        if (SC.size() <= 2)
+          return;
+
+        // If violate property#2, we don't fold the chain.
+        for (size_t I = 1, N = SC.size(); I < N; ++I) {
+          if (CopySourceInvalid.count(SC[I]))
+            return;
+        }
+
+        for (size_t I = 0, N = RC.size() - 1; I < N; ++I) {
+          if (CopySourceInvalid.count(RC[I]))
+            return;
+        }
+
+        auto CheckCopyConstraint = [this](Register Def, Register Src) {
+          for (const TargetRegisterClass *RC : TRI->regclasses()) {
+            if (RC->contains(Def) && RC->contains(Src))
+              return true;
+          }
+          return false;
+        };
+
+        auto UpdateReg = [](MachineInstr *MI, const MachineOperand *Old,
+                            const MachineOperand *New) {
+          for (MachineOperand &MO : MI->operands()) {
+            if (&MO == Old)
+              MO.setReg(New->getReg());
+          }
+        };
+
+        std::optional<DestSourcePair> InnerMostSpillCopy =
+            isCopyInstr(*SC[0], *TII, UseCopyInstr);
+        std::optional<DestSourcePair> OuterMostSpillCopy =
+            isCopyInstr(*SC.back(), *TII, UseCopyInstr);
+        std::optional<DestSourcePair> InnerMostReloadCopy =
+            isCopyInstr(*RC[0], *TII, UseCopyInstr);
+        std::optional<DestSourcePair> OuterMostReloadCopy =
+            isCopyInstr(*RC.back(), *TII, UseCopyInstr);
+        if (!CheckCopyConstraint(OuterMostSpillCopy->Source->getReg(),
+                                 InnerMostSpillCopy->Source->getReg()) ||
+            !CheckCopyConstraint(InnerMostReloadCopy->Destination->getReg(),
+                                 OuterMostReloadCopy->Destination->getReg()))
+          return;
+
+        SpillageChainsLength += SC.size() + RC.size();
+        UpdateReg(SC[0], InnerMostSpillCopy->Destination,
+                  OuterMostSpillCopy->Source);
+        UpdateReg(RC[0], InnerMostReloadCopy->Source,
+                  OuterMostReloadCopy->Destination);
+
+        for (size_t I = 1; I < SC.size() - 1; ++I) {
+          SC[I]->eraseFromParent();
+          RC[I]->eraseFromParent();
+        }
+      };
+
+  auto IsFoldableCopy = [this](const MachineInstr &MaybeCopy) {
+    if (MaybeCopy.getNumImplicitOperands() > 0)
+      return false;
+    std::optional<DestSourcePair> CopyOperands =
+        isCopyInstr(MaybeCopy, *TII, UseCopyInstr);
+    if (!CopyOperands)
+      return false;
+    Register Src = CopyOperands->Source->getReg();
+    Register Def = CopyOperands->Destination->getReg();
+    return Src && Def && !TRI->regsOverlap(Src, Def) &&
+           CopyOperands->Source->isRenamable() &&
+           CopyOperands->Destination->isRenamable();
+  };
+
+  auto IsSpillReloadPair = [&, this](const MachineInstr &Spill,
+                                     const MachineInstr &Reload) {
+    if (!IsFoldableCopy(Spill) || !IsFoldableCopy(Reload))
+      return false;
+    std::optional<DestSourcePair> SpillCopy =
+        isCopyInstr(Spill, *TII, UseCopyInstr);
+    std::optional<DestSourcePair> ReloadCopy =
+        isCopyInstr(Reload, *TII, UseCopyInstr);
+    if (!SpillCopy || !ReloadCopy)
+      return false;
+    return SpillCopy->Source->getReg() == ReloadCopy->Destination->getReg() &&
+           SpillCopy->Destination->getReg() == ReloadCopy->Source->getReg();
+  };
+
+  auto IsChainedCopy = [&, this](const MachineInstr &Prev,
+                                 const MachineInstr &Current) {
+    if (!IsFoldableCopy(Prev) || !IsFoldableCopy(Current))
+      return false;
+    std::optional<DestSourcePair> PrevCopy =
+        isCopyInstr(Prev, *TII, UseCopyInstr);
+    std::optional<DestSourcePair> CurrentCopy =
+        isCopyInstr(Current, *TII, UseCopyInstr);
+    if (!PrevCopy || !CurrentCopy)
+      return false;
+    return PrevCopy->Source->getReg() == CurrentCopy->Destination->getReg();
+  };
+
+  for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {
+    std::optional<DestSourcePair> CopyOperands =
+        isCopyInstr(MI, *TII, UseCopyInstr);
+
+    // Update track information via non-copy instruction.
+    SmallSet<Register, 8> RegsToClobber;
+    if (!CopyOperands) {
+      for (const MachineOperand &MO : MI.operands()) {
+        if (!MO.isReg())
+          continue;
+        Register Reg = MO.getReg();
+        if (!Reg)
+          continue;
+        MachineInstr *LastUseCopy =
+            Tracker.findLastSeenUseInCopy(Reg.asMCReg(), *TRI);
+        if (LastUseCopy) {
+          LLVM_DEBUG(dbgs() << "MCP: Copy source of\n");
+          LLVM_DEBUG(LastUseCopy->dump());
+          LLVM_DEBUG(dbgs() << "might be invalidated by\n");
+          LLVM_DEBUG(MI.dump());
+          CopySourceInvalid.insert(LastUseCopy);
+        }
+        // Must be noted Tracker.clobberRegister(Reg, ...) removes tracking of
+        // Reg, i.e, COPY that defines Reg is removed from the mapping as well
+        // as marking COPYs that uses Reg unavailable.
+        // We don't invoke CopyTracker::clobberRegister(Reg, ...) if Reg is not
+        // defined by a previous COPY, since we don't want to make COPYs uses
+        // Reg unavailable.
+        if (Tracker.findLastSeenDefInCopy(MI, Reg.asMCReg(), *TRI, *TII,
+                                    UseCopyInstr))
+          // Thus we can keep the property#1.
+          RegsToClobber.insert(Reg);
+      }
+      for (Register Reg : RegsToClobber) {
+        Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
+        LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Reg, TRI)
+                          << "\n");
+      }
+      continue;
+    }
+
+    Register Src = CopyOperands->Source->getReg();
+    Register Def = CopyOperands->Destination->getReg();
+    // Check if we can find a pair spill-reload copy.
+    LLVM_DEBUG(dbgs() << "MCP: Searching paired spill for reload: ");
+    LLVM_DEBUG(MI.dump());
+    MachineInstr *MaybeSpill =
+        Tracker.findLastSeenDefInCopy(MI, Src.asMCReg(), *TRI, *TII, UseCopyInstr);
+    bool MaybeSpillIsChained = ChainLeader.count(MaybeSpill);
+    if (!MaybeSpillIsChained && MaybeSpill &&
+        IsSpillReloadPair(*MaybeSpill, MI)) {
+      // Check if we already have an existing chain. Now we have a
+      // spill-reload pair.
+      // L2: r2 = COPY r3
+      // L5: r3 = COPY r2
+      // Looking for a valid COPY before L5 which uses r3.
+      // This can be serverial cases.
+      // Case #1:
+      // No COPY is found, which can be r3 is def-use between (L2, L5), we
+      // create a new chain for L2 and L5.
+      // Case #2:
+      // L2: r2 = COPY r3
+      // L5: r3 = COPY r2
+      // Such COPY is found and is L2, we create a new chain for L2 and L5.
+      // Case #3:
+      // L2: r2 = COPY r3
+      // L3: r1 = COPY r3
+      // L5: r3 = COPY r2
+      // we create a new chain for L2 and L5.
+      // Case #4:
+      // L2: r2 = COPY r3
+      // L3: r1 = COPY r3
+      // L4: r3 = COPY r1
+      // L5: r3 = COPY r2
+      // Such COPY won't be found since L4 defines r3. we create a new chain
+      // for L2 and L5.
+      // Case #5:
+      // L2: r2 = COPY r3
+      // L3: r3 = COPY r1
+      // L4: r1 = COPY r3
+      // L5: r3 = COPY r2
+      // COPY is found and is L4 which belongs to an existing chain, we add
+      // L2 and L5 to this chain.
+      LLVM_DEBUG(dbgs() << "MCP: Found spill: ");
+      LLVM_DEBUG(MaybeSpill->dump());
+      MachineInstr *MaybePrevReload =
+          Tracker.findLastSeenUseInCopy(Def.asMCReg(), *TRI);
+      auto Leader = ChainLeader.find(MaybePrevReload);
+      MachineInstr *L = nullptr;
+      if (Leader == ChainLeader.end() ||
+          (MaybePrevReload && !IsChainedCopy(*MaybePrevReload, MI))) {
+        L = &MI;
+        assert(!SpillChain.count(L) &&
+               "SpillChain should not have contained newly found chain");
+      } else {
+        assert(MaybePrevReload &&
+               "Found a valid leader through nullptr should not happend");
+        L = Leader->second;
+        assert(SpillChain[L].size() > 0 &&
+               "Existing chain's length should be larger than zero");
+      }
+      assert(!ChainLeader.count(&MI) && !ChainLeader.count(MaybeSpill) &&
+             "Newly found paired spill-reload should not belong to any chain "
+             "at this point");
+      ChainLeader.insert({MaybeSpill, L});
+      ChainLeader.insert({&MI, L});
+      SpillChain[L].push_back(MaybeSpill);
+      ReloadChain[L].push_back(&MI);
+      LLVM_DEBUG(dbgs() << "MCP: Chain " << L << " now is:\n");
+      LLVM_DEBUG(printSpillReloadChain(SpillChain, ReloadChain, L));
+    } else if (MaybeSpill && !MaybeSpillIsChained) {
+      // MaybeSpill is unable to pair with MI. That's to say adding MI makes
+      // the chain invalid.
+      // The COPY defines Src is no longer considered as a candidate of a
+      // valid chain. Since we expect the Def of a spill copy isn't used by
+      // any COPY instruction until a reload copy. For example:
+      // L1: r1 = COPY r2
+      // L2: r3 = COPY r1
+      // If we later have
+      // L1: r1 = COPY r2
+      // L2: r3 = COPY r1
+      // L3: r2 = COPY r1
+      // L1 and L3 can't be a valid spill-reload pair.
+      // Thus we keep the property#1.
+      LLVM_DEBUG(dbgs() << "MCP: Not paired spill-reload:\n");
+      LLVM_DEBUG(MaybeSpill->dump());
+      LLVM_DEBUG(MI.dump());
+      Tracker.clobberRegister(Src.asMCReg(), *TRI, *TII, UseCopyInstr);
+      LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Src, TRI)
+                        << "\n");
+    }
+    Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
+  }
+
+  for (auto I = SpillChain.begin(), E = SpillChain.end(); I != E; ++I) {
+    auto &SC = I->second;
+    assert(ReloadChain.count(I->first) &&
+           "Reload chain of the same leader should exist");
+    auto &RC = ReloadChain[I->first];
+    TryFoldSpillageCopies(SC, RC);
+  }
+
+  MaybeDeadCopies.clear();
+  CopyDbgUsers.clear();
+  Tracker.clear();
+}
+
 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
+  NumFunctionsSeen += 1;
   Changed = false;
 
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
   MRI = &MF.getRegInfo();
 
   for (MachineBasicBlock &MBB : MF) {
+    EliminateSpillageCopies(MBB);
     BackwardCopyPropagateBlock(MBB);
     ForwardCopyPropagateBlock(MBB);
   }
 
   return Changed;
 }
 
 MachineFunctionPass *
 llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) {
   return new MachineCopyPropagation(UseCopyInstr);
 }

llvm/test/CodeGen/PowerPC/mcp-elim-eviction-chain.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -O3 -verify-machineinstrs -mtriple=powerpc64-unknown-unknown \
+# RUN:   -simplify-mir -run-pass=machine-cp %s -o - | FileCheck %s
+
+--- |
+  declare void @foo()
+  define void @test0() {
+  entry:
+    ret void
+  }
+
+  define void @test1() {
+  entry:
+    ret void
+  }
+
+  define void @test2() {
+  entry:
+    ret void
+  }
+
+  define void @test3() {
+  entry:
+    ret void
+  }
+
+  define void @test4() {
+  entry:
+    ret void
+  }
+
+  define void @test5() {
+  entry:
+    ret void
+  }
+
+  define void @test6() {
+  entry:
+    ret void
+  }
+
+...
+---
+name: test0
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x4, $x5, $x20, $x21, $x22
+    ; CHECK-LABEL: name: test0
+    ; CHECK: liveins: $x4, $x5, $x20, $x21, $x22
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x24 = COPY $x4
+    ; CHECK-NEXT: $x23 = COPY renamable $x20
+    ; CHECK-NEXT: renamable $x20 = ADD8 $x4, $x5
+    ; CHECK-NEXT: renamable $x4 = COPY renamable $x20
+    ; CHECK-NEXT: renamable $x20 = COPY $x23
+    ; CHECK-NEXT: renamable $x23 = COPY renamable $x24
+    ; CHECK-NEXT: $x3 = COPY renamable $x4
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x20, implicit $x21, implicit $x22, implicit $x23
+    renamable $x23 = COPY renamable $x4
+    renamable $x24 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x21
+    renamable $x21 = COPY renamable $x20
+    renamable $x20 = ADD8 $x4, $x5
+    renamable $x4 = COPY renamable $x20
+    renamable $x20 = COPY renamable $x21
+    renamable $x21 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x24
+    $x3 = COPY renamable $x4
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x20, implicit $x21, implicit $x22, implicit $x23
+
+...
+
+# Duplicated pairs.
+---
+name: test1
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x3, $x20, $x21, $x22, $x23
+    ; CHECK-LABEL: name: test1
+    ; CHECK: liveins: $x3, $x20, $x21, $x22, $x23
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x24 = COPY $x3
+    ; CHECK-NEXT: renamable $x23 = COPY renamable $x22
+    ; CHECK-NEXT: renamable $x22 = COPY renamable $x21
+    ; CHECK-NEXT: renamable $x21 = COPY renamable $x20
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24
+    renamable $x23 = COPY $x3
+    renamable $x24 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x21
+    renamable $x21 = COPY renamable $x20
+    renamable $x20 = COPY renamable $x21
+    renamable $x21 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x24
+    renamable $x24 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x21
+    renamable $x21 = COPY renamable $x20
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24
+
+...
+
+# Chain one after one.
+---
+name: test2
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x3, $x18, $x19, $x20, $x21, $x22, $x23, $x24
+    ; CHECK-LABEL: name: test2
+    ; CHECK: liveins: $x3, $x18, $x19, $x20, $x21, $x22, $x23, $x24
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x21 = COPY renamable $x20
+    ; CHECK-NEXT: renamable $x20 = COPY renamable $x21
+    ; CHECK-NEXT: renamable $x25 = COPY renamable $x24
+    ; CHECK-NEXT: renamable $x24 = COPY renamable $x25
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x18, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25
+    renamable $x21 = COPY renamable $x20
+    renamable $x20 = COPY renamable $x19
+    renamable $x19 = COPY renamable $x18
+    renamable $x18 = COPY renamable $x19
+    renamable $x19 = COPY renamable $x20
+    renamable $x20 = COPY renamable $x21
+    renamable $x25 = COPY renamable $x24
+    renamable $x24 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x22
+    renamable $x22 = COPY renamable $x23
+    renamable $x23 = COPY renamable $x24
+    renamable $x24 = COPY renamable $x25
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x18, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25
+
+...
+
+# Reorder code in test2, thus we have two chains in build simultaneously.
+---
+name: test3
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x3, $x18, $x19, $x20, $x21, $x22, $x23, $x24
+    ; CHECK-LABEL: name: test3
+    ; CHECK: liveins: $x3, $x18, $x19, $x20, $x21, $x22, $x23, $x24
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x21 = COPY renamable $x20
+    ; CHECK-NEXT: renamable $x25 = COPY renamable $x24
+    ; CHECK-NEXT: renamable $x20 = COPY renamable $x21
+    ; CHECK-NEXT: renamable $x24 = COPY renamable $x25
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x18, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25
+    renamable $x21 = COPY renamable $x20
+    renamable $x25 = COPY renamable $x24
+    renamable $x20 = COPY renamable $x19
+    renamable $x24 = COPY renamable $x23
+    renamable $x19 = COPY renamable $x18
+    renamable $x23 = COPY renamable $x22
+    renamable $x18 = COPY renamable $x19
+    renamable $x22 = COPY renamable $x23
+    renamable $x19 = COPY renamable $x20
+    renamable $x23 = COPY renamable $x24
+    renamable $x20 = COPY renamable $x21
+    renamable $x24 = COPY renamable $x25
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x18, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25
+
+...
+
+---
+name: test4
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x3, $x4, $x5
+    ; CHECK-LABEL: name: test4
+    ; CHECK: liveins: $x3, $x4, $x5
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
+    renamable $x5 = COPY renamable $x3
+    renamable $x4 = COPY renamable $x3
+    renamable $x2 = COPY renamable $x3
+    renamable $x3 = COPY renamable $x2
+    renamable $x3 = COPY renamable $x4
+    renamable $x3 = COPY renamable $x5
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3
+
+...
+
+# Chain across regmask.
+---
+name: test5
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x17, $x16, $x15, $x14, $x3
+    ; CHECK-LABEL: name: test5
+    ; CHECK: liveins: $x17, $x16, $x15, $x14, $x3
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x18 = COPY renamable $x17
+    ; CHECK-NEXT: $x17 = COPY renamable $x3
+    ; CHECK-NEXT: BL8_NOP @foo, csr_ppc64, implicit-def dead $lr8, implicit $rm, implicit-def $x3, implicit $x3
+    ; CHECK-NEXT: renamable $x3 = COPY $x17
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3
+    renamable $x18 = COPY renamable $x17
+    renamable $x17 = COPY renamable $x16
+    renamable $x16 = COPY renamable $x15
+    renamable $x15 = COPY renamable $x14
+    renamable $x14 = COPY renamable $x3
+    BL8_NOP @foo, csr_ppc64, implicit-def dead $lr8, implicit $rm, implicit-def $x3, implicit $x3
+    renamable $x3 = COPY renamable $x14
+    renamable $x14 = COPY renamable $x15
+    renamable $x15 = COPY renamable $x16
+    renamable $x16 = COPY renamable $x17
+    renamable $x17 = COPY renamable $x18
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3
+
+...
+
+# Two chains across regmask.
+---
+name: test6
+alignment: 4
+tracksRegLiveness: true
+body: |
+  bb.0.entry:
+    liveins: $x20, $x19, $x17, $x16, $x15, $x14, $x3, $x4
+    ; CHECK-LABEL: name: test6
+    ; CHECK: liveins: $x20, $x19, $x17, $x16, $x15, $x14, $x3, $x4
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $x21 = COPY renamable $x20
+    ; CHECK-NEXT: renamable $x18 = COPY renamable $x17
+    ; CHECK-NEXT: $x17 = COPY renamable $x3
+    ; CHECK-NEXT: $x20 = COPY renamable $x4
+    ; CHECK-NEXT: BL8_NOP @foo, csr_ppc64, implicit-def dead $lr8, implicit $rm, implicit-def $x3, implicit $x3, implicit-def $x4, implicit $x4
+    ; CHECK-NEXT: renamable $x3 = COPY $x17
+    ; CHECK-NEXT: renamable $x4 = COPY $x20
+    ; CHECK-NEXT: BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x4
+    renamable $x21 = COPY renamable $x20
+    renamable $x18 = COPY renamable $x17
+    renamable $x17 = COPY renamable $x16
+    renamable $x16 = COPY renamable $x15
+    renamable $x20 = COPY renamable $x19
+    renamable $x15 = COPY renamable $x14
+    renamable $x14 = COPY renamable $x3
+    renamable $x19 = COPY renamable $x4
+    BL8_NOP @foo, csr_ppc64, implicit-def dead $lr8, implicit $rm, implicit-def $x3, implicit $x3, implicit-def $x4, implicit $x4
+    renamable $x3 = COPY renamable $x14
+    renamable $x14 = COPY renamable $x15
+    renamable $x4 = COPY renamable $x19
+    renamable $x15 = COPY renamable $x16
+    renamable $x19 = COPY renamable $x20
+    renamable $x16 = COPY renamable $x17
+    renamable $x20 = COPY renamable $x21
+    renamable $x17 = COPY renamable $x18
+    BLR8 implicit $lr8, implicit undef $rm, implicit $x3, implicit $x4
+
+...
+

llvm/test/CodeGen/RISCV/wide-scalar-shift-by-byte-multiple-legalization.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=ALL,RV64I
-; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=ALL,RV32I
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=RV64I
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=RV32I
 
 define void @lshr_4bytes(ptr %src.ptr, ptr %byteOff.ptr, ptr %dst) nounwind {
 ; RV64I-LABEL: lshr_4bytes:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    lbu a3, 1(a0)
 ; RV64I-NEXT:    lbu a4, 0(a0)
 ; RV64I-NEXT:    lbu a5, 2(a0)
 ; RV64I-NEXT:    slli a3, a3, 8

 ; RV32I-NEXT:    lw s8, 40(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    bltz s8, .LBB11_54
 ; RV32I-NEXT:  .LBB11_56:
 ; RV32I-NEXT:    mv s8, s9
 ; RV32I-NEXT:    bgeu s3, t1, .LBB11_58
 ; RV32I-NEXT:  .LBB11_57:
 ; RV32I-NEXT:    slti s8, s5, 0
 ; RV32I-NEXT:    mv t1, a4
-; RV32I-NEXT:    mv a4, t2
-; RV32I-NEXT:    mv t2, s6
-; RV32I-NEXT:    mv s6, s1
-; RV32I-NEXT:    mv s1, ra
+; RV32I-NEXT:    mv a4, ra
 ; RV32I-NEXT:    srl ra, a3, s3
 ; RV32I-NEXT:    neg s8, s8
 ; RV32I-NEXT:    and s8, s8, ra
-; RV32I-NEXT:    mv ra, s1
-; RV32I-NEXT:    mv s1, s6
-; RV32I-NEXT:    mv s6, t2
-; RV32I-NEXT:    mv t2, a4
+; RV32I-NEXT:    mv ra, a4
 ; RV32I-NEXT:    mv a4, t1
 ; RV32I-NEXT:    li t1, 64
 ; RV32I-NEXT:    or s8, s8, s7
 ; RV32I-NEXT:  .LBB11_58:
 ; RV32I-NEXT:    mv s7, a3
 ; RV32I-NEXT:    bnez s3, .LBB11_65
 ; RV32I-NEXT:  # %bb.59:
 ; RV32I-NEXT:    li s8, 128

 ; RV32I-NEXT:    ret
   %src = load i256, ptr %src.ptr, align 1
   %byteOff = load i256, ptr %byteOff.ptr, align 1
   %bitOff = shl i256 %byteOff, 3
   %res = ashr i256 %src, %bitOff
   store i256 %res, ptr %dst, align 1
   ret void
 }
-;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
-; ALL: {{.*}}

llvm/test/CodeGen/RISCV/wide-scalar-shift-legalization.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=ALL,RV64I
-; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=ALL,RV32I
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=RV64I
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s -check-prefixes=RV32I
 
 define void @lshr_4bytes(ptr %src.ptr, ptr %bitOff.ptr, ptr %dst) nounwind {
 ; RV64I-LABEL: lshr_4bytes:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    lbu a3, 1(a0)
 ; RV64I-NEXT:    lbu a4, 0(a0)
 ; RV64I-NEXT:    lbu a5, 2(a0)
 ; RV64I-NEXT:    slli a3, a3, 8

 ; RV32I-NEXT:    lw s8, 40(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    bltz s8, .LBB11_54
 ; RV32I-NEXT:  .LBB11_56:
 ; RV32I-NEXT:    mv s8, s9
 ; RV32I-NEXT:    bgeu s3, t1, .LBB11_58
 ; RV32I-NEXT:  .LBB11_57:
 ; RV32I-NEXT:    slti s8, s5, 0
 ; RV32I-NEXT:    mv t1, t2
-; RV32I-NEXT:    mv t2, s6
-; RV32I-NEXT:    mv s6, s1
-; RV32I-NEXT:    mv s1, ra
+; RV32I-NEXT:    mv t2, ra
 ; RV32I-NEXT:    srl ra, a3, s3
 ; RV32I-NEXT:    neg s8, s8
 ; RV32I-NEXT:    and s8, s8, ra
-; RV32I-NEXT:    mv ra, s1
-; RV32I-NEXT:    mv s1, s6
-; RV32I-NEXT:    mv s6, t2
+; RV32I-NEXT:    mv ra, t2
 ; RV32I-NEXT:    mv t2, t1
 ; RV32I-NEXT:    li t1, 64
 ; RV32I-NEXT:    or s8, s8, s7
 ; RV32I-NEXT:  .LBB11_58:
 ; RV32I-NEXT:    mv s7, a3
 ; RV32I-NEXT:    bnez s3, .LBB11_65
 ; RV32I-NEXT:  # %bb.59:
 ; RV32I-NEXT:    li s8, 128

 ; RV32I-NEXT:    addi sp, sp, 128
 ; RV32I-NEXT:    ret
   %src = load i256, ptr %src.ptr, align 1
   %bitOff = load i256, ptr %bitOff.ptr, align 1
   %res = ashr i256 %src, %bitOff
   store i256 %res, ptr %dst, align 1
   ret void
 }
-;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
-; ALL: {{.*}}

llvm/test/CodeGen/Thumb2/LowOverheadLoops/spillingmove.ll

 ; CHECK-NEXT:    vshr.u16 q1, q0, #3
 ; CHECK-NEXT:    vand q1, q1, q2
 ; CHECK-NEXT:    vmov q2, q4
 ; CHECK-NEXT:    vmla.i16 q2, q1, r2
 ; CHECK-NEXT:    vshr.u16 q1, q2, #5
 ; CHECK-NEXT:    vshl.i16 q2, q0, #3
 ; CHECK-NEXT:    vand q3, q1, q5
 ; CHECK-NEXT:    vmov q1, q7
-; CHECK-NEXT:    vand q2, q2, q6
-; CHECK-NEXT:    vmov q7, q6
-; CHECK-NEXT:    vmov q6, q5
-; CHECK-NEXT:    vmov q5, q4
+; CHECK-NEXT:    vmov q7, q4
 ; CHECK-NEXT:    vldrw.u32 q4, [sp, #48] @ 16-byte Reload
+; CHECK-NEXT:    vand q2, q2, q6
 ; CHECK-NEXT:    vshr.u16 q0, q0, #9
 ; CHECK-NEXT:    vmla.i16 q4, q2, r2
 ; CHECK-NEXT:    vshr.u16 q2, q4, #11
-; CHECK-NEXT:    vmov q4, q5
-; CHECK-NEXT:    vmov q5, q6
-; CHECK-NEXT:    vmov q6, q7
+; CHECK-NEXT:    vmov q4, q7
 ; CHECK-NEXT:    vmov q7, q1
 ; CHECK-NEXT:    vorr q1, q3, q2
 ; CHECK-NEXT:    vldrw.u32 q2, [sp, #16] @ 16-byte Reload
 ; CHECK-NEXT:    vand q0, q0, q7
 ; CHECK-NEXT:    vmla.i16 q2, q0, r2
 ; CHECK-NEXT:    vldrw.u32 q0, [sp] @ 16-byte Reload
 ; CHECK-NEXT:    vand q0, q2, q0
 ; CHECK-NEXT:    vldrw.u32 q2, [sp, #32] @ 16-byte Reload

llvm/test/CodeGen/Thumb2/mve-postinc-dct.ll

 ; CHECK-NEXT:    vfmat.f32 q5, q0, q7
 ; CHECK-NEXT:    vldrwt.u32 q0, [r10]
 ; CHECK-NEXT:    add.w r6, r11, r5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q6, q0, q7
 ; CHECK-NEXT:    vldrwt.u32 q0, [r11]
 ; CHECK-NEXT:    vstrw.32 q6, [sp, #40] @ 16-byte Spill
 ; CHECK-NEXT:    vmov q6, q5
-; CHECK-NEXT:    vpst
+; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q1, q0, q7
-; CHECK-NEXT:    vmov q5, q4
-; CHECK-NEXT:    vmov q4, q3
-; CHECK-NEXT:    vmov q3, q1
-; CHECK-NEXT:    vpst
 ; CHECK-NEXT:    vldrwt.u32 q0, [r6]
+; CHECK-NEXT:    vmov q5, q1
 ; CHECK-NEXT:    vldrw.u32 q1, [sp, #56] @ 16-byte Reload
 ; CHECK-NEXT:    adds r7, r6, r5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q1, q0, q7
 ; CHECK-NEXT:    vldrwt.u32 q0, [r7]
 ; CHECK-NEXT:    adds r6, r7, r5
 ; CHECK-NEXT:    vstrw.32 q1, [sp, #56] @ 16-byte Spill
-; CHECK-NEXT:    vmov q1, q3
-; CHECK-NEXT:    vmov q3, q4
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q3, q0, q7
 ; CHECK-NEXT:    vldrwt.u32 q0, [r6]
-; CHECK-NEXT:    vmov q4, q5
 ; CHECK-NEXT:    adds r7, r6, r5
+; CHECK-NEXT:    vmov q1, q5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q4, q0, q7
 ; CHECK-NEXT:    vldrwt.u32 q0, [r7]
 ; CHECK-NEXT:    vmov q5, q6
 ; CHECK-NEXT:    vldrw.u32 q6, [sp, #40] @ 16-byte Reload
 ; CHECK-NEXT:    vpst
 ; CHECK-NEXT:    vfmat.f32 q2, q0, q7
 ; CHECK-NEXT:    le lr, .LBB6_3

 ; CHECK-NEXT:    sub.w r10, r10, #4
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q6, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r11]
 ; CHECK-NEXT:    vstrw.32 q6, [sp, #40] @ 16-byte Spill
 ; CHECK-NEXT:    vmov q6, q5
 ; CHECK-NEXT:    vpst
 ; CHECK-NEXT:    vfmat.f32 q7, q1, q0
-; CHECK-NEXT:    vmov q5, q3
-; CHECK-NEXT:    vmov q3, q4
-; CHECK-NEXT:    vmov q4, q2
+; CHECK-NEXT:    vmov q5, q2
 ; CHECK-NEXT:    vpst
 ; CHECK-NEXT:    vldrwt.u32 q1, [r6]
 ; CHECK-NEXT:    vldrw.u32 q2, [sp, #56] @ 16-byte Reload
 ; CHECK-NEXT:    adds r7, r6, r5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q2, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r7]
 ; CHECK-NEXT:    vstrw.32 q2, [sp, #56] @ 16-byte Spill
 ; CHECK-NEXT:    vldrw.u32 q2, [sp, #72] @ 16-byte Reload
 ; CHECK-NEXT:    adds r6, r7, r5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q2, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r6]
 ; CHECK-NEXT:    adds r7, r6, r5
 ; CHECK-NEXT:    vstrw.32 q2, [sp, #72] @ 16-byte Spill
-; CHECK-NEXT:    vmov q2, q4
-; CHECK-NEXT:    vmov q4, q3
+; CHECK-NEXT:    vmov q2, q5
+; CHECK-NEXT:    adds r6, r7, r5
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q2, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r7]
-; CHECK-NEXT:    adds r6, r7, r5
-; CHECK-NEXT:    vmov q3, q5
+; CHECK-NEXT:    vmov q5, q6
+; CHECK-NEXT:    vldrw.u32 q6, [sp, #40] @ 16-byte Reload
 ; CHECK-NEXT:    vpstt
 ; CHECK-NEXT:    vfmat.f32 q4, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r6]
-; CHECK-NEXT:    vmov q5, q6
 ; CHECK-NEXT:    add r6, r5
-; CHECK-NEXT:    vpstt
+; CHECK-NEXT:    vpsttt
 ; CHECK-NEXT:    vfmat.f32 q5, q1, q0
 ; CHECK-NEXT:    vldrwt.u32 q1, [r6]
-; CHECK-NEXT:    vldrw.u32 q6, [sp, #40] @ 16-byte Reload
-; CHECK-NEXT:    vpst
 ; CHECK-NEXT:    vfmat.f32 q3, q1, q0
 ; CHECK-NEXT:    le lr, .LBB7_3
 ; CHECK-NEXT:  @ %bb.4: @ %middle.block
 ; CHECK-NEXT:    @ in Loop: Header=BB7_2 Depth=1
 ; CHECK-NEXT:    vadd.f32 s0, s30, s31
 ; CHECK-NEXT:    add.w r1, r2, r1, lsl #2
 ; CHECK-NEXT:    vadd.f32 s2, s28, s29
 ; CHECK-NEXT:    vadd.f32 s4, s26, s27