MachineCopyPropagation: remove some more copys when they are not needed

[jonpa]

Summary

I was experimenting with the Loop Unroller, and found a benchmark that regressed for no obvious reason as relating to the unrolling of loops. However, I found in a loop with four outer loops, an extra unneeded copy of a register.

It was clear that the COPY was not needed, however not so clear how it should be handled. Comparing the two compilations, the regcoalescer results were identical. It was the greedy regalloc that behaved a bit differently (there were more live intervals in the unrolled loop), for one reason or other.

I looked at MCP, and found that it was missing this very simple case. I am not sure if MCP should really be a simple pass and instead the regalloc should be fixed, but I guessed that MCP has some purpose of cleaning up after regalloc, and experimented with extending it to handle my regression. Here is my patch:

1. If a register use is defined by a COPY, and the COPY source reg could be used directly, use it instead if it seems that the COPY may be removable then.
2. Whenever an instruction defines (clobbers) any register, remove any COPY that is tracked in MaybeDeadCopies, just like it was done for RegMask operands.

This was needed to handle:
%R4D<def> = LGR %R12D
%R7D<def> = LGR %R9D<kill>
%R1D<def> = SLLG %R14D, %noreg, 2
%R0H<def> = LFH %R4D<kill>, 0, %R1D<kill>; mem:LD4[%arrayidx35.i.i](tbaa=!6)
%R1D<def> = LGR %R5D
%R4D<def> = LGR %R3D
The COPY of R12D to R4D is unnecessary. R4D could be replaced with R12D in the LFH instruction (first point above). The COPY itself can be removed when the last instruction redefines R4D (point two above).

Why is this pass so simple? It is not trusting live-in lists, and not recomputing liveness -- is this something "todo", or? My first thought was that liveness could be checked with a reaching phys defs algorithm (see http://reviews.llvm.org/D17257), and basically the pass could be doing a bit more work then. After working with this benchmark, it became clear that even a single COPY could make a noticable difference (SPEC/bzip2).

Greatful for any feedback on this!

[junbuml]

lib/CodeGen/MachineCopyPropagation.cpp

275

insted -> instead

277

You may intended this continue in outside of this for loop ?

282

I doubt if you can simply replace MO with PrevCopySrc whenever the register class is matched. What if either MO or PrevCopySrc is reserved ?

331–334

Cann't you use MI->definesRegister() here instead of tracking defs through Clobbers.

[MatzeB]

I haven't looked at the change yet, but this is how I see MCPs role:

Why is this pass so simple? It is not trusting live-in lists, and not recomputing liveness -- is this something "todo", or? My first thought was that liveness could be checked with a reaching phys defs algorithm (see http://reviews.llvm.org/D17257), and basically the pass could be doing a bit more work then. After working with this benchmark, it became clear that even a single COPY could make a noticable difference (SPEC/bzip2).

The MachineCopyPropagation started as an ad-hoc fix for some cases that the register allocator did not handle. I assume we simply never tried to use something more sophisticated. While we probably would have no problem with a more sophisticated MCP pass the question we really should answer first is why all the other mechanisms failed to eliminate the copy:
There is the aggressive and extensive RegisterCoalescer pass, the PeepholeOptimizer removes cross register bank copies and the allocator has hinting mechanism for the few cases we cannot remove in the RegisterCoalescer. So before extending the MCP pass we should try to understand why you ended up with that copy. My first guess would be that the RegisterCoalescer should remove the COPY from your example (though it's hard to judge from the limited context).

[jonpa]

Thanks for feedback and review Matthias and Jun!

I have done a little further investigation on this, and it seems that

• If MCP would trust the live-in lists, about 40% more COPYs would be removed, or ~2 COPYs per file.
• This patch is nowhere near that. It fixed my particular problem, but little more (only one change per every 15 files or so).

Matthias: at least in this case, the code seemed identical after regcoalescer, but it was some merging of live intervals by the GreedyRegAlloc that somehow kept the copy propagation from happening.

I see an effective Copy propagation pass as at least a first step towards a final solution, since

• Regalloc passes are complex and difficult to improve. RAGreedy gets rid of nearly all the COPYs, but not all. This last part might be tricky to get in place.
• By turning off such a CopyProp pass, it would be easy to get many test cases for improving regalloc copy propagation. Eventually, perhaps regalloc could do it all.
• Copy propagation is simple and standard on its own. Even one single copy in a tight loop could make a noticable difference. This makes it important for stability during development of other optimisations, so as to not get a regression because of this.

So instead of continuing with this current patch, I wonder if it wouldn't be even better to try to use the ReachingPhysDefs utility and try a more aggressive algorithm with global liveness analysis.

What are your thoughts on this?

[jonpa]

Patch updated according to review, and also added handling of a COPY's second implit-def with ClobberRegister().

[qcolombet]

Hi Jonas,

Couple of comment:

If a register use is defined by a COPY, and the COPY source reg could be used directly, use it instead if it seems that the COPY may be removable then.

That is not generally safe. In particular, if the definition is required by the ABI, you cannot eliminate that copy.

What are your thoughts on this?

Improving MachineCopyPropagation to handle more cases seem reasonable to me.
For more complex cases, even if I believe the ReachingPhysDefs would help (BTW, I think it needs you to make some changes for faster convergence), it sounds more like we should improve our regalloc heuristic to not have to deal with those cases in the first place.

Cheers,
-Quentin

[jonpa]

If a register use is defined by a COPY, and the COPY source reg could be used directly, use it instead if it seems that the COPY may be removable then.

That is not generally safe. In particular, if the definition is required by the ABI, you cannot eliminate that copy.

What are the exact checks that need to be done? The only one I know of is the involvement of a reserved register.

[qcolombet]

Hi Jonas,

What are the exact checks that need to be done?

That’s the thing, you can’t really know at this stage.
An approximation would be to do this transformation for explicit uses only. But I would rather stay out of that game to be safe.

Right now, this pass is about removing no-op copies. It does not try to do recoloring, which is what your patch aim for.

If we want to go for recoloring, we need to handle that before the virtual registers are rewritten, because at this point, we can assume that all present physical registers are ABI constraints.

Cheers,
-Quentin

[MatzeB]

Hi Jonas,

I just realized that I was working on pretty much the same thing (d'oh). I just didn't realize at first as I had a different motivation: When I change:

%x = COPY %y
  use %x

to

%x = COPY %y
  use %y

then both instructions can be scheduled independently by the post-ra scheduler.

As Quentin already mentioned it is indeed sketchy to rename physregs as it is not clear whether there are additional architectural constraints forcing the use of a specific register. While ABI constraints should not be touched (because you MCInstrDesc doesn't specify a register class for those implicit def and use operands), this still doesn't universally work.

In my experiments the renaming was fine on aarch64, but AMDGPU for example breaks after renaming because apparently some physregs cannot be used multiple times on the same instruction.
A fact that is not visible to the MachineCopyPropagation pass. I "solved" this by requiring the target to explicitely opt-in to the behaviour for now.

I'll upload my version shortly for reference after incorporating some of the things you did here.

[MatzeB]

Comparing with http://reviews.llvm.org/D21455 I realized two details:

lib/CodeGen/MachineCopyPropagation.cpp

234–236

This looks strange. In theory we can see any number of additional implicit operands on a COPY. I assume we were just to not hit any issues because in todays practice we only add implicit defs and uses of the superregister when a subregister was used (see code in VirtRegRewriter).

Do you actually need this bugfix as part of this patch? As far as I can see COPY instructions are not renamed here so we should not run into any new problems here.

(It would still be good to upstream this fix in a separate commit through and use a loop so we also catch the case with 4 operands when we had a subregister def and use at the COPY).

284–291

I found that there are examples where you can only rename some of the operands (the reg may be used multiple times, but on of the inputs is tied to an output and cannot be renamed). It is semantically questionable to rename only parts of the operands (and you will not get any scheduling benefits or dead copy removal opportunities anyway in this case).

[jonpa]

lib/CodeGen/MachineCopyPropagation.cpp

234–236

I thought that it was kind of a bug to not ignore an implicit-def operand regardless of anything else.

As I recall, it was also necessary to handle during my experiments, either because the MachineVerifier complained that a register was used without a def (if that COPY was removed), or because I wanted to avoid bothering with subregisters all together (changing just one subregister is not a good idea). Not sure exactly which of these I ran into.

lib/CodeGen/MachineCopyPropagation.cpp

 
 void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
   DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
 
   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
     MachineInstr *MI = &*I;
     ++I;
 
+    const MachineOperand *RegMask = nullptr;
+
     if (MI->isCopy()) {
       unsigned Def = MI->getOperand(0).getReg();
       unsigned Src = MI->getOperand(1).getReg();
 
       assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
              !TargetRegisterInfo::isVirtualRegister(Src) &&
              "MachineCopyPropagation should be run after register allocation!");
 
if (MI->isCopy()) {
       // If 'Def' is previously source of another copy, then this earlier copy's
       // source is no longer available. e.g.
       // %xmm9<def> = copy %xmm2
       // ...
       // %xmm2<def> = copy %xmm0
       // ...
       // %xmm2<def> = copy %xmm9
       ClobberRegister(Def);
+      // Handle any second implicit def operand.
+      if (MI->getNumOperands() == 3 && MI->getOperand(2).isDef())
+        ClobberRegister(MI->getOperand(2).getReg());
 
       // Remember Def is defined by the copy.
       for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
            ++SR) {
         CopyMap[*SR] = MI;
         AvailCopyMap[*SR] = MI;
       }
 
       // Remember source that's copied to Def. Once it's clobbered, then
       // it's no longer available for copy propagation.
       RegList &DestList = SrcMap[Src];
       if (std::find(DestList.begin(), DestList.end(), Def) == DestList.end())
         DestList.push_back(Def);
-
-      continue;
     }
-
+    else {
       // Not a copy.
       SmallVector<unsigned, 2> Defs;
-    const MachineOperand *RegMask = nullptr;
-    for (const MachineOperand &MO : MI->operands()) {
+      for (unsigned MOIdx = 0; MOIdx < MI->getNumOperands() ; ++MOIdx) {
+        MachineOperand &MO = MI->getOperand(MOIdx);
         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!");
+               "MachineCopyPropagation should be run after register "
+               "allocation!");
 
         if (MO.isDef()) {
           Defs.push_back(Reg);
           continue;
         }
 
+        // If 'Reg' is killed and is defined by a previous copy of a
+        // register that is also in the right register class, use that
+        // earlier source register instead. This may make that previous
+        // copy removable. Skipping subregs and multiple uses for now.
+        if (!MRI->isReserved(Reg) &&
+            MO.readsReg() && MO.isKill() && !MO.isTied() &&
+            !TII->isGenericOpcode(MI->getOpcode())) {
+          Reg2MIMap::iterator CI = AvailCopyMap.find(MO.getReg());
+          if (CI != AvailCopyMap.end()) {
+            MachineInstr &PrevCopy = *CI->second;
+            MachineOperand &PrevCopySrc = PrevCopy.getOperand(1);
+            const TargetRegisterClass *RC =
+              TII->getRegClass(MI->getDesc(), MOIdx, TRI, *MBB.getParent());
+            if (!MRI->isReserved(PrevCopySrc.getReg()) &&
+                !PrevCopySrc.getSubReg() &&
+                RC != nullptr && RC->contains(PrevCopySrc.getReg())) {
+              MO.setReg(PrevCopySrc.getReg());
+              continue;
+            }
+          }
+        }
+
         // If 'Reg' is defined by a copy, the copy is no longer a candidate
         // for elimination.
         for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
           Reg2MIMap::iterator CI = CopyMap.find(*AI);
           if (CI != CopyMap.end()) {
             DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump());
             MaybeDeadCopies.remove(CI->second);
           }
         }
         // Treat undef use like defs for copy propagation but not for
         // dead copy. We would need to do a liveness check to be sure the copy
         // is dead for undef uses.
         // The backends are allowed to do whatever they want with undef value
         // and we cannot be sure this register will not be rewritten to break
         // some false dependencies for the hardware for instance.
         if (MO.isUndef())
           Defs.push_back(Reg);
       }
 
-    // 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 =
-               MaybeDeadCopies.begin();
-           DI != MaybeDeadCopies.end();) {
-        MachineInstr *MaybeDead = *DI;
-        unsigned Reg = MaybeDead->getOperand(0).getReg();
-        assert(!MRI->isReserved(Reg));
-
-        if (!RegMask->clobbersPhysReg(Reg)) {
-          ++DI;
-          continue;
-        }
+      // Any previous copy definition or reading the Defs is no longer available.
+      for (unsigned Reg : Defs)
+        ClobberRegister(Reg);
+    }
+
+    // Erase any MaybeDeadCopies whose destination register was clobbered.
+      if (MaybeDead == MI) {
+      unsigned Reg = MaybeDead->getOperand(0).getReg();
+      assert(!MRI->isReserved(Reg));
 
+      if (MI->definesRegister(Reg, TRI))
+        DEBUG(dbgs() << "MCP: Removing copy due to def: ";
+              MaybeDead->dump());
+      else if (RegMask && RegMask->clobbersPhysReg(Reg))
         DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
               MaybeDead->dump());
+      else {
+        ++DI;
+        continue;
+      }
 
-        // 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;
-      }
 
+    if (RegMask) {
       removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
       removeClobberedRegsFromMap(CopyMap, *RegMask);
       for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
            I != E; I = Next) {
         Next = std::next(I);
         if (RegMask->clobbersPhysReg(I->first)) {
           removeRegsFromMap(AvailCopyMap, I->second, *TRI);
           SrcMap.erase(I);
         }
       }
     }
-
-    // Any previous copy definition or reading the Defs is no longer available.
-    for (unsigned Reg : Defs)
-      ClobberRegister(Reg);
   }
 
   // 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) {
       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));