CodeGen peephole: fold redundant phys reg copies

[jfb]

Summary

Code generation often exposes redundant physical register copies through
virtual registers such as:

%vreg = COPY %PHYSREG
...
%PHYSREG = COPY %vreg

There are cases where no intervening clobber of %PHYSREG occurs, and the
later copy could therefore be removed. In some cases this further allows
us to remove the initial copy.

This patch contains a motivating example which comes from the x86 build
of Chrome, specifically cc::ResourceProvider::UnlockForRead uses
libstdc++'s implementation of hash_map. That example has two tests live
at the same time, and after machine sinking LLVM has confused itself
enough and things spilling EFLAGS is a great idea even though it's
never restored and the comparison results are both live.

Before this patch we have:

DEC32m %RIP, 1, %noreg, <ga:@L>, %noreg, %EFLAGS<imp-def>
%vreg1<def> = COPY %EFLAGS; GR64:%vreg1
%EFLAGS<def> = COPY %vreg1; GR64:%vreg1
JNE_1 <BB#1>, %EFLAGS<imp-use>

Both copies are useless. This patch tries to eliminate the later copy in
a generic manner.

dec is especially confusing to LLVM when compared with sub.

I wrote this patch to treat all physical registers generically, but only
remove redundant copies of non-allocatable physical registers because
the allocatable ones caused issues (e.g. when calling conventions weren't
properly modeled) and should be handled later by the register allocator
anyways.

This works fine when there are intervening calls between flag generation and
flag usage (these calls clobber flags):

test/CodeGen/X86/cmpxchg-clobber-flags.ll

The following tests used to failed when the patch also replaced allocatable
registers:

CodeGen/X86/StackColoring.ll
CodeGen/X86/avx512-calling-conv.ll
CodeGen/X86/copy-propagation.ll
CodeGen/X86/inline-asm-fpstack.ll
CodeGen/X86/musttail-varargs.ll
CodeGen/X86/pop-stack-cleanup.ll
CodeGen/X86/preserve_mostcc64.ll
CodeGen/X86/tailcallstack64.ll
CodeGen/X86/this-return-64.ll

Note that all other backends' tests pass.

[jfb]

There's further complication around calling conventions, where it seems that the x86 backend doesn't fully model xmm registers as being caller-saved. This example:

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@I32 = external global i32

declare i32* @foo(i32*, i64)

declare i32* @bar(i32, i32)

declare double @D()

declare i32* @P32()

declare i32* @baz(double)

define hidden i32* @ExpressionFromLiteral(i32 %token) {
entry:
  switch i32 %token, label %return [
    i32 83, label %bb0
    i32 82, label %bb1
  ]

bb0:
  %I32.loaded = load i32, i32* @I32
  %call.foo = tail call i32* @foo(i32* nonnull @I32, i64 48)
  %call.bar = tail call i32* @bar(i32 %I32.loaded, i32 %I32.loaded)
  %call.foo.gep.40 = getelementptr inbounds i32, i32* %call.foo, i64 40
  %ptr.foo = bitcast i32* %call.foo.gep.40 to i32**
  store i32* %call.bar, i32** %ptr.foo
  br label %return

bb1:
  %call.D = tail call double @D()
  %call.P32 = tail call i32* @P32()
  %call.baz = tail call i32* @baz(double %call.D)
  %call.P32.gep.40 = getelementptr inbounds i32, i32* %call.P32, i64 40
  %ptr.P32 = bitcast i32* %call.P32.gep.40 to i32**
  store i32* %call.baz, i32** %ptr.P32
  br label %return

return:
  %retval.0 = phi i32* [ %call.P32, %bb1 ], [ %call.foo, %bb0 ], [ null, %entry ]
  ret i32* %retval.0
}

Confuses LLVM around the @D call because the double is returned in xmm0 and is live across a call, and passed to the next one. The code starts off as:

BB#2: derived from LLVM BB %bb1
    Predecessors according to CFG: BB#0
	ADJCALLSTACKDOWN64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	CALL64pcrel32 <ga:@D>, <regmask %BH %BL %BP %BPL %BX %EBP %EBX %RBP %RBX %R12 %R13 %R14 %R15 %R12B %R13B %R14B %R15B %R12D %R13D %R14D %R15D %R12W %R13W %R14W %R15W>, %RSP<imp-use>, %RSP<imp-def>, %XMM0<imp-def>
	ADJCALLSTACKUP64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	%vreg8<def> = COPY %XMM0; FR64:%vreg8
	ADJCALLSTACKDOWN64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	CALL64pcrel32 <ga:@P32>, <regmask %BH %BL %BP %BPL %BX %EBP %EBX %RBP %RBX %R12 %R13 %R14 %R15 %R12B %R13B %R14B %R15B %R12D %R13D %R14D %R15D %R12W %R13W %R14W %R15W>, %RSP<imp-use>, %RSP<imp-def>, %RAX<imp-def>
	ADJCALLSTACKUP64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	%vreg9<def> = COPY %RAX; GR64:%vreg9
	%vreg1<def> = COPY %vreg9; GR64:%vreg1,%vreg9
	ADJCALLSTACKDOWN64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	%XMM0<def> = COPY %vreg8; FR64:%vreg8
	CALL64pcrel32 <ga:@baz>, <regmask %BH %BL %BP %BPL %BX %EBP %EBX %RBP %RBX %R12 %R13 %R14 %R15 %R12B %R13B %R14B %R15B %R12D %R13D %R14D %R15D %R12W %R13W %R14W %R15W>, %RSP<imp-use>, %XMM0<imp-use>, %RSP<imp-def>, %RAX<imp-def>
	ADJCALLSTACKUP64 0, 0, %RSP<imp-def,dead>, %EFLAGS<imp-def,dead>, %RSP<imp-use>
	%vreg10<def> = COPY %RAX; GR64:%vreg10
	MOV64mr %vreg9, 1, %noreg, 160, %noreg, %vreg10; mem:ST8[%ptr.P32] GR64:%vreg9,%vreg10
    Successors according to CFG: BB#3(?%)

Note how xmm0 is implicitly defined, then (with available information) needlessly copied to vreg8 and back, then implicitly used. My patch deletes %XMM0<def> = COPY %vreg8, which then allows %vreg8<def> = COPY %XMM0 to be deleted.

This could be fixed by being either:

• Being smarter about calling conventions in my code.
• Marking all calls as having modeled side-effects (which would lose some potential optimizations).
• Marking xmm registers as clobbered in calls such as @P32 above.

That problem doesn't really need to be tackled until I figure out how to fix the other one, though. It's just extra :-)

[qcolombet]

Hi,

We purposely don’t remove such copies because it over constrains the coloring later on.
The idea is that if the coalescing is possible, then the register allocator should prefer it. However, I reckon that in your motivating example that’s not going to happen since this is a cross register bank copy.

Anyway, the peephole optimizer happens too early IMO for this to be a reasonable solution. I would instead encourage you to look at fixing this into the CopyPropagation pass.

Cheers,
-Quentin

[qcolombet]

Note: The transformation would make sense in the peephole optimizer if we do it only for not allocatable registers.

[jfb]

In D15157#300551, @qcolombet wrote:

Note: The transformation would make sense in the peephole optimizer if we do it only for not allocatable registers.

Interesting proposal, that does seem to make sense. Let me look into it, thanks!

[jfb]

NFC: rename PhysCopy to ConstPhysCopy

First step in applying qcolombet's suggestion of only applying this optimization
to constant physical register (he suggested to affect non-allocatable only, but
that would include pinned ones too, whereas constant physical registers seem
more conservative).

[jfb]

Restrict to non-allocatable physical registers.

I tried using MachineRegisterInfo::isConstantPhysReg instead but that's too
conservative and doesn't include the main motivator for this patch: EFLAGS.

This implements the change qcolombet suggested and passes all x86 tests,
including the new test I added incdec-and-branch.ll.

[jfb]

This now passes all tests with ninja check on a build with all backends, and seems to do what I want! I'll clean up the code a bit, test it on Chrome some more (including the issue I posted above).

[jfb]

Clean up code.

[jfb]

I cleaned up the code, it passes all the tests and does what I wanted to achieve for the one Chrome usecase. @qcolombet would you mind taking another look?

[qcolombet]

Hi,

Looks almost good.
Two main remarks:

1. Check for regmask in the operands as well
2. Try to add more test cases for coverage

Thanks,
-Quentin

lib/CodeGen/PeepholeOptimizer.cpp

1423

Put a message in the assert, even an obvious one :).

1531

I’ll make a function out of it and you have to check the reg mask operand as well.
For instance, if we have a pure (side effect free) function call, you may clobber the register and we will miss it.

test/CodeGen/X86/incdec-and-branch.ll

17

Could we have some “positive” testing as well, i.e. CHECK lines not just CHECK-NOT?

Also, I would rename the file into peephole-na-copy-folding or something and add more test cases where you check the inline asm case, the definition in the middle, etc.
Anyhow, you get it, something that improves the coverage.
I understand this can be difficult to come with additional test cases, just give it a try and if you can’t find some, then you can’t :).

[jfb]

Address qcolombet's comments:

• Rename test file.
• Add more tests.
• Make the tests positive.
• Document asserts.
• Also test for reg mask clobbering.

[jfb]

Comments addressed.

lib/CodeGen/PeepholeOptimizer.cpp

1531

I added regmask.

I'm not sure I understand what you mean with "pure". Do you mean readonly? That still has to observe the calling convention and declare its clobbers, no?

[qcolombet]

LGTM.

Thanks,
Q.

lib/CodeGen/PeepholeOptimizer.cpp

1531

Yes, I mean readonly :).
Yes, it has to declare its clobbers.

What I meant was that if we do not check for the regmask operand, the check "MI->hasUnmodeledSideEffects()” was not enough to ensure we won’t clobber the registers.

test/CodeGen/X86/peephole-na-phys-copy-folding.ll

6 ↗

(On Diff #41812)

s/whne/when

[jfb]

• Typo.

lib/CodeGen/PeepholeOptimizer.cpp

 static cl::opt<bool>
 DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
                 cl::desc("Disable the peephole optimizer"));
 
 static cl::opt<bool>
 DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false),
                   cl::desc("Disable advanced copy optimization"));
 
+static cl::opt<bool> DisableConstPhysCopyOpt(
+    "disable-const-phys-copy-opt", cl::Hidden, cl::init(false),
+    cl::desc("Disable constant physical register copy optimization"));
+
 // Limit the number of PHI instructions to process
 // in PeepholeOptimizer::getNextSource.
 static cl::opt<unsigned> RewritePHILimit(
     "rewrite-phi-limit", cl::Hidden, cl::init(10),
     cl::desc("Limit the length of PHI chains to lookup"));
 
 STATISTIC(NumReuse,      "Number of extension results reused");
 STATISTIC(NumCmps,       "Number of compares eliminated");
 STATISTIC(NumImmFold,    "Number of move immediate folded");
 STATISTIC(NumLoadFold,   "Number of loads folded");
 STATISTIC(NumSelects,    "Number of selects optimized");
 STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized");
 STATISTIC(NumRewrittenCopies, "Number of copies rewritten");
+STATISTIC(NumConstPhysCopies, "Number of constant physical copies removed");
 
 namespace {
   class ValueTrackerResult;
 
   class PeepholeOptimizer : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     MachineRegisterInfo   *MRI;
private:
     bool isMoveImmediate(MachineInstr *MI,
                          SmallSet<unsigned, 4> &ImmDefRegs,
                          DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
     bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
                        SmallSet<unsigned, 4> &ImmDefRegs,
                        DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
 
     /// \brief If copy instruction \p MI is a virtual register copy, track it in
-    /// the set \p CopiedFromRegs and \p CopyMIs. If this virtual register was
+    /// the set \p CopySrcRegs and \p CopyMIs. If this virtual register was
     /// previously seen as a copy, replace the uses of this copy with the
     /// previously seen copy's destination register.
     bool foldRedundantCopy(MachineInstr *MI,
-                           SmallSet<unsigned, 4> &CopiedFromRegs,
-                           DenseMap<unsigned, MachineInstr*> &CopyMIs);
+                           SmallSet<unsigned, 4> &CopySrcRegs,
+                           DenseMap<unsigned, MachineInstr *> &CopyMIs);
 
+    /// \brief If copy instruction \p MI is a constant virtual<->physical
+    /// register copy, track it in the \p ConstPhysToVirtMIs map. If this
+    /// constant physical register was previously copied to a virtual registered
+    /// and hasn't been clobbered, the virt->phys copy can be deleted.
+    bool foldRedundantConstPhysCopy(
+        MachineInstr *MI,
+        DenseMap<unsigned, MachineInstr *> &ConstPhysToVirtMIs);
+
     bool isLoadFoldable(MachineInstr *MI,
                         SmallSet<unsigned, 16> &FoldAsLoadDefCandidates);
 
     /// \brief Check whether \p MI is understood by the register coalescer
     /// but may require some rewriting.
     bool isCoalescableCopy(const MachineInstr &MI) {
       // SubregToRegs are not interesting, because they are already register
       // coalescer friendly.

 // only the first copy is considered.
 //
 // e.g.
 // %vreg1 = COPY %vreg0
 // %vreg2 = COPY %vreg0:sub1
 //
 // Should replace %vreg2 uses with %vreg1:sub1
 bool PeepholeOptimizer::foldRedundantCopy(
     MachineInstr *MI,
     SmallSet<unsigned, 4> &CopySrcRegs,
     DenseMap<unsigned, MachineInstr *> &CopyMIs) {
   assert(MI->isCopy());
 
   unsigned SrcReg = MI->getOperand(1).getReg();
   if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
     return false;
 
   unsigned DstReg = MI->getOperand(0).getReg();
   if (!TargetRegisterInfo::isVirtualRegister(DstReg))
bool PeepholeOptimizer::foldRedundantCopy(
 
   MRI->replaceRegWith(DstReg, PrevDstReg);
 
   // Lifetime of the previous copy has been extended.
   MRI->clearKillFlags(PrevDstReg);
   return true;
 }
 
+bool PeepholeOptimizer::foldRedundantConstPhysCopy(
+    MachineInstr *MI, DenseMap<unsigned, MachineInstr *> &ConstPhysToVirtMIs) {
+  assert(MI->isCopy());
+
+  if (DisableConstPhysCopyOpt)
+    return false;
+
+  unsigned DstReg = MI->getOperand(0).getReg();
+  unsigned SrcReg = MI->getOperand(1).getReg();
+  if (TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
+      TargetRegisterInfo::isVirtualRegister(DstReg)) {
+    DEBUG(dbgs() << "%vreg = COPY %PHYSREG::: " << *MI << '\n');
+    // %vreg = COPY %PHYSREG
+    // Avoid using a datastructure which can track multiple live
+    // constant phys->virt copies since LLVM doesn't seem to do this.
+    ConstPhysToVirtMIs.insert({SrcReg, MI});
+    return false;
+  }
+
+  if (!(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
+        TargetRegisterInfo::isPhysicalRegister(DstReg)))
+    return false;
+
+  DEBUG(dbgs() << "%PHYSREG = COPY %vreg::: " << *MI << '\n');
+  // %PHYSREG = COPY %vreg
+  auto PrevCopy = ConstPhysToVirtMIs.find(DstReg);
+  if (PrevCopy == ConstPhysToVirtMIs.end()) {
+    // We can't remove the copy: there was an intervening clobber of the
+    // constant physical register after the copy to virtual.
+    DEBUG(dbgs() << "*** Can't erase " << *MI << '\n');
+    return false;
+  }
+
+  unsigned PrevDstReg = PrevCopy->second->getOperand(0).getReg();
+  if (PrevDstReg == SrcReg) {
+    // Remove the virt->phys copy: we saw the virtual register definition, and
+    // the constant physical register's state hasn't changed since then.
+    DEBUG(dbgs() << "*** Erasing " << *MI << '\n');
+    ++NumConstPhysCopies;
+    return true;
+  }
+
+  // Potential missed optimization opportunity: we saw a different virtual
+  // register get a copy of the constant physical register, and we only track
+  // one such copy. Avoid getting confused by this new constant physical
+  // register definition, and remove it from the tracked copies.
+  DEBUG(dbgs() << "*** Missed opportunity " << *MI << '\n');
+  ConstPhysToVirtMIs.erase(PrevCopy);
+  return false;
+}
+
 bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
   if (skipOptnoneFunction(*MF.getFunction()))
     return false;
 
   DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
   DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n');
 
   if (DisablePeephole)
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
     // To perform this, the following set keeps track of the MIs already seen
     // during the scan, if a MI is not in the set, it is assumed to be located
     // after. Newly created MIs have to be inserted in the set as well.
     SmallPtrSet<MachineInstr*, 16> LocalMIs;
     SmallSet<unsigned, 4> ImmDefRegs;
     DenseMap<unsigned, MachineInstr*> ImmDefMIs;
     SmallSet<unsigned, 16> FoldAsLoadDefCandidates;
 
+    // Track when a constant physical register is copied to a virtual register
+    // so that useless moves can be removed.
+    //
+    // %PHYSREG is the map index; MI is the last valid `%vreg = COPY %PHYSREG`
+    // without any intervening re-definition of %PHYSREG.
+    DenseMap<unsigned, MachineInstr *> ConstPhysToVirtMIs;
+
     // Set of virtual registers that are copied from.
     SmallSet<unsigned, 4> CopySrcRegs;
     DenseMap<unsigned, MachineInstr *> CopySrcMIs;
 
     for (MachineBasicBlock::iterator
            MII = I->begin(), MIE = I->end(); MII != MIE; ) {
       MachineInstr *MI = &*MII;
       // We may be erasing MI below, increment MII now.
       ++MII;
       LocalMIs.insert(MI);
 
       // Skip debug values. They should not affect this peephole optimization.
       if (MI->isDebugValue())
           continue;
 
       // If we run into an instruction we can't fold across, discard
       // the load candidates.
       if (MI->isLoadFoldBarrier())
         FoldAsLoadDefCandidates.clear();
 
-      if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() ||
-          MI->isKill() || MI->isInlineAsm() ||
-          MI->hasUnmodeledSideEffects())
+      if (MI->isPosition() || MI->isPHI())
+        continue;
+
+      if (!MI->isCopy()) {
+        DEBUG(dbgs() << "Looking at operands for " << *MI << '\n');
+        for (const auto &Op : MI->operands()) {
+          DEBUG(dbgs() << "  "
+                       << " reg=" << Op.isReg()
+                       << " def=" << (Op.isReg() ? Op.isDef() : false)
+                       << " imp=" << (Op.isReg() ? Op.isImplicit() : false)
+                       << '\n');
+          // Visit all operands: definitions can be implicit or explicit.
+          if (Op.isReg()) {
+            unsigned Reg = Op.getReg();
+            if (Op.isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) {
+              const auto &Def = ConstPhysToVirtMIs.find(Reg);
+              if (Def != ConstPhysToVirtMIs.end()) {
+                // A new definition of the constant physical register
+                // invalidates previous copies.
+                DEBUG(dbgs() << "  ------ Invalidating ^^^\n");
+                ConstPhysToVirtMIs.erase(Def);
+              }
+            }
+          }
+        }
+      }
+
+      if (MI->isImplicitDef() || MI->isKill())
+        continue;
+
+      if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) {
+        // Blow away all constant physical registers knowledge since we don't
+        // know what's correct anymore.
+        //
+        // FIXME: handle explicit asm clobbers.
+        DEBUG(dbgs()
+              << "*** Inline asm or side effects, blowing away phys to virt\n");
+        ConstPhysToVirtMIs.clear();
         continue;
+      }
 
       if ((isUncoalescableCopy(*MI) &&
            optimizeUncoalescableCopy(MI, LocalMIs)) ||
           (MI->isCompare() && optimizeCmpInstr(MI, MBB)) ||
           (MI->isSelect() && optimizeSelect(MI, LocalMIs))) {
         // MI is deleted.
         LocalMIs.erase(MI);
         Changed = true;
         continue;
       }
 
       if (MI->isConditionalBranch() && optimizeCondBranch(MI)) {
         Changed = true;
         continue;
       }
 
       if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(MI)) {
         // MI is just rewritten.
         Changed = true;
         continue;
       }
 
-      if (MI->isCopy() && foldRedundantCopy(MI, CopySrcRegs, CopySrcMIs)) {
+      if (MI->isCopy() &&
+          (foldRedundantCopy(MI, CopySrcRegs, CopySrcMIs) ||
+           foldRedundantConstPhysCopy(MI, ConstPhysToVirtMIs))) {
         LocalMIs.erase(MI);
         MI->eraseFromParent();
         Changed = true;
         continue;
       }
 
       if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
         SeenMoveImm = true;

test/CodeGen/X86/incdec-and-branch.ll

+; RUN: llc -verify-machineinstrs -mtriple=i386-linux-gnu %s -o - | FileCheck %s
+; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu %s -o - | FileCheck %s
+
+; inc / dec generate flags which can be used to branch. Make sure the flags are
+; used directly, instead of needlessly using lahf.
+
+@L = external global i32
+@M = external global i8
+
+; TODO other sizes?
+
+; CHECK-NOT: seto
+; CHECK-NOT: lahf
+; CHECK-NOT: sahf
+; CHECK-NOT: pushf
+; CHECK-NOT: popf
+
+define i1 @plus_one() {
+entry:
+  %loaded_L = load i32, i32* @L
+  %val = add nsw i32 %loaded_L, 1 ; N.B.
+  store i32 %val, i32* @L
+  %loaded_M = load i8, i8* @M
+  %masked = and i8 %loaded_M, 8
+  %M_is_true = icmp ne i8 %masked, 0
+  %L_is_false = icmp eq i32 %val, 0
+  %cond = and i1 %L_is_false, %M_is_true
+  br i1 %cond, label %exit2, label %exit
+
+exit:
+  ret i1 true
+
+exit2:
+  ret i1 false
+}
+
+define i1 @minus_one() {
+entry:
+  %loaded_L = load i32, i32* @L
+  %val = add nsw i32 %loaded_L, -1 ; N.B.
+  store i32 %val, i32* @L
+  %loaded_M = load i8, i8* @M
+  %masked = and i8 %loaded_M, 8
+  %M_is_true = icmp ne i8 %masked, 0
+  %L_is_false = icmp eq i32 %val, 0
+  %cond = and i1 %L_is_false, %M_is_true
+  br i1 %cond, label %exit2, label %exit
+
+exit:
+  ret i1 true
+
+exit2:
+  ret i1 false
+}