MachineLICM: Add new condition for hoisting of caller preserved registers

[lei]

Summary

On PPC, global variable access is done through the table of contents (TOC) which is always in register X2. The ABI reserves this register in any functions that have calls or access global variables. Furthermore, a call through a function pointer involves saving, changing and restoring the register around the call.

Currently MachineLICM is not able to hoist instructions used to get the TOC-based addresses out of a loop if there is a virtual function call within that loop. This is because X2 is (visibly) saved/restored by the caller around the call. MachineLICM sees the use of the X2 register but since it is NOT a constant physical register in this machine function, it deemed it unsafe and does not hoist it out of the loop. Of course, overriding isConstantPhysicalRegister() for X2 is not valid since there are visible defs of the register.

What is needed is a way to communicate to MachineLICM that even though the register isn't constant in the function, it is preserved between uses - i.e. ensure that any clobber of X2 will be followed by a restore before the next use. This patch adds such a query to the MachineRegisterInfo/TargetRegisterInfo.

SPEC perf run showed negligible differences in speedups.

[lei]

Specific to 64bit LE

[iteratee]

This looks fine to me.

[echristo]

Looks ok to me too, Matthias?

-eric

[MatzeB]

Instead of introducing yet another target callback, how about some simple heuristic like MRI.hasOneDef(Reg) && !MRI.getUsedPhysRegsMask().test(Reg)[1] allowing hoisting up to the point of that definition (which you can find out with MRI.def_instr_begin(Reg) or similar).

[1] We really oughta rename UsedPhysRegMask to something that makes sense (it's simply the union of call regmask operands in the function).

[nemanjai]

In D33562#766121, @MatzeB wrote:

Instead of introducing yet another target callback, how about some simple heuristic like MRI.hasOneDef(Reg) && !MRI.getUsedPhysRegsMask().test(Reg)[1] allowing hoisting up to the point of that definition (which you can find out with MRI.def_instr_begin(Reg) or similar).

[1] We really oughta rename UsedPhysRegMask to something that makes sense (it's simply the union of call regmask operands in the function).

If that does the job, I think it would be great to not have to add another target hook. But to be honest, it doesn't really sound like it will solve this problem. Namely, the call through a function pointer does clobber X2 (but restores it on return). So a call of that sort being in the loop will presumably still prevent the global address calculation (which uses X2) from being hoisted out of the loop.

[MatzeB]

In D33562#766872, @nemanjai wrote:

In D33562#766121, @MatzeB wrote:

Instead of introducing yet another target callback, how about some simple heuristic like MRI.hasOneDef(Reg) && !MRI.getUsedPhysRegsMask().test(Reg)[1] allowing hoisting up to the point of that definition (which you can find out with MRI.def_instr_begin(Reg) or similar).

[1] We really oughta rename UsedPhysRegMask to something that makes sense (it's simply the union of call regmask operands in the function).

If that does the job, I think it would be great to not have to add another target hook. But to be honest, it doesn't really sound like it will solve this problem. Namely, the call through a function pointer does clobber X2 (but restores it on return). So a call of that sort being in the loop will presumably still prevent the global address calculation (which uses X2) from being hoisted out of the loop.

You talk about a call instruction? Is X2 saved and restored in the called function? Then it's just a CSR and should not be mentioned in the clobber list so no problem with my proposal above.

[nemanjai]

You talk about a call instruction? Is X2 saved and restored in the called function? Then it's just a CSR and should not be mentioned in the clobber list so no problem with my proposal above.

But it is the caller that saves and restores it, not the callee. The sequence is essentially this (all in the caller of course):

• Save X2 to it's stack slot
• Update X2 prior to the call
• Call the function through a pointer
• Restore X2 immediately after the call

[lei]

Matthias (@MatzeB), do you have any additional comments for this patch?

[iteratee]

In D33562#766989, @nemanjai wrote:

You talk about a call instruction? Is X2 saved and restored in the called function? Then it's just a CSR and should not be mentioned in the clobber list so no problem with my proposal above.

But it is the caller that saves and restores it, not the callee. The sequence is essentially this (all in the caller of course):

• Save X2 to it's stack slot
• Update X2 prior to the call
• Call the function through a pointer
• Restore X2 immediately after the call

But all of that occurs via the linker.
X2 is saved by a trampoline if necessary, and restored in the nop slot if necessary.
As far as the surrounding code is concerned, the trampoline is the callee, (the nop slot may be considered part of the trampoline.)
Treating X2 as callee saved makes perfect sense as far as llvm is concerned.

[sfertile]

In D33562#767893, @iteratee wrote:

In D33562#766989, @nemanjai wrote:

You talk about a call instruction? Is X2 saved and restored in the called function? Then it's just a CSR and should not be mentioned in the clobber list so no problem with my proposal above.

But it is the caller that saves and restores it, not the callee. The sequence is essentially this (all in the caller of course):

• Save X2 to it's stack slot
• Update X2 prior to the call
• Call the function through a pointer
• Restore X2 immediately after the call

But all of that occurs via the linker.
X2 is saved by a trampoline if necessary, and restored in the nop slot if necessary.
As far as the surrounding code is concerned, the trampoline is the callee, (the nop slot may be considered part of the trampoline.)
Treating X2 as callee saved makes perfect sense as far as llvm is concerned.

For a normal call the linker inserts the save and restore. When calling through a function pointer the compiler inserts the save/restore of the TOC pointer, and that is what is causing the address calculations not to get hoisted.

[MatzeB]

include/llvm/CodeGen/MachineRegisterInfo.h

584–586

No need to add this to MachineRegisterInfo.

include/llvm/Target/TargetRegisterInfo.h

500–501

Please improve upon the description. Currently this sounds like a check where PhysReg is a CSR register, which you just explained to me in the review is not the case!

test/CodeGen/PowerPC/licm-tocReg.ll

2

• Can you write a .mir test that is better targetted at the problem?
• Please add a sentence or two to describe what you are testing.

[nemanjai]

In D33562#767911, @sfertile wrote:

In D33562#767893, @iteratee wrote:

In D33562#766989, @nemanjai wrote:

You talk about a call instruction? Is X2 saved and restored in the called function? Then it's just a CSR and should not be mentioned in the clobber list so no problem with my proposal above.

But it is the caller that saves and restores it, not the callee. The sequence is essentially this (all in the caller of course):

• Save X2 to it's stack slot
• Update X2 prior to the call
• Call the function through a pointer
• Restore X2 immediately after the call

But all of that occurs via the linker.
X2 is saved by a trampoline if necessary, and restored in the nop slot if necessary.
As far as the surrounding code is concerned, the trampoline is the callee, (the nop slot may be considered part of the trampoline.)
Treating X2 as callee saved makes perfect sense as far as llvm is concerned.

For a normal call the linker inserts the save and restore. When calling through a function pointer the compiler inserts the save/restore of the TOC pointer, and that is what is causing the address calculations not to get hoisted.

Just for reference... Here's what Machine LICM sees for the call through a function ptr:

BCTRL8_LDinto_toc 24, %X1, <regmask %CR2 %CR3 %CR4 %F14 %F15 %F16 %F17 %F18 %F19 %F20 %F21 %F22 %F23 %F24 %F25 %F26 %F27 %F28 %F29 %F30 %F31 %R14 %R15 %R16 %R17 %R18 %R19 %R20 %R21 %R22 %R23 %R24 %R25 %R26 %R27 %R28 %R29 %R30 %R31 %V20 %V21 %V22 %V23 %V24 %V25 %V26 %V27 %V28 %V29 %V30 %V31 %VF20 %VF21 %VF22 %VF23 %VF24 %VF25 %VF26 %VF27 %VF28 %VF29 %VF30 %VF31 %X14 %X15 %X16 %X17 %X18 %X19 %X20 %X21 %X22 %X23 %X24 %X25 %X26 %X27 %X28 %X29 %X30 %X31 %CR2EQ %CR3EQ %CR4EQ %CR2GT %CR3GT %CR4GT %CR2LT %CR3LT %CR4LT %CR2UN %CR3UN %CR4UN>, %LR8<imp-def,dead>, %X2<imp-def,dead>, %CTR8<imp-use>, %RM<imp-use>, %X3<imp-use>, %X12<imp-use>, %X2<imp-use>, %R1<imp-def>, %X3<imp-def>

And of course, this "instruction" will emit both the branch on the count register and the load into X2 to restore the TOC pointer. Of course, previously to this, prepareCall() will have emitted a store of the TOC pointer to the stack.

So it really is the caller that saves and restores the TOC ptr. So X2 is not a CSR - the caller modifies it so it is of course not a "constant physical register". The only thing that makes this situation special is that what needs to be communicated to Machine LICM is that this modification is guaranteed to give X2 the same value it had before the call.

[lei]

include/llvm/CodeGen/MachineRegisterInfo.h

584–586

k

include/llvm/Target/TargetRegisterInfo.h

500–501

k

test/CodeGen/PowerPC/licm-tocReg.ll

2

When I tried to create a .mir test I get machine verifier errors. Since there are no passes invoked that identify the TOC access in the function, we don't reserve X2.
The problem is that MachineFunctionInfo isn't saved/dumped as part of emitting .mir. So any passes that rely on a previously populated MFI run the risk of failing. Specifically, this is an issue with TOC access which is what I'm trying to test. The proper solution would be to emit MFI data .mir, but that is beyond the scope of this patch.

Would an IR test with -stop-before/-stop-after checks be a reasonable compromise?

[MatzeB]

test/CodeGen/PowerPC/licm-tocReg.ll

2

That's unfortunate. In that case I'd rather leave the test as is (this is about late MachineLICM so there's not that many passes coming after it anyway that could destabilize the test).
My point about documenting the test a bit still stands though (for example add a comment, which of the instructions was hoisted out of the loop and which call was blocking it before this patch).

[lei]

test/CodeGen/PowerPC/licm-tocReg.ll

2

Will do

[lei]

Addressed all comments.

[lei]

Hi Matthias (@MatzeB), any additional comments?

[lei]

@MatzeB ?

[MatzeB]

LGTM with nitpicks.

include/llvm/Target/TargetRegisterInfo.h

505

The last sentence is not true anymore.

lib/CodeGen/MachineLICM.cpp

895–898

Could you move this check below the !isConstantPhysReg check as I expect this to be a rare case.

[lei]

include/llvm/Target/TargetRegisterInfo.h

505

will remove.

lib/CodeGen/MachineLICM.cpp

895–898

This needs to be above !isConstantPhysReg which is an early function exit check where as this is just an loop exit check. MRI->isConstantPhysReg(X2) will return false which will cause this function to exit with false. I could combine the two into:

if (!MRI->isConstantPhysReg(Reg) && !(TRI->isCallerPreservedPhysReg(Reg, *I.getParent()->getParent())))
   return false;

[lei]

Update as per comments

[MatzeB]

lib/CodeGen/MachineLICM.cpp

895–898

yes of course, my point was to check the ConstantPhysReg condition first and then the isCallerPreservedPhysReg which this does fine.

include/llvm/CodeGen/MachineRegisterInfo.h

 #ifndef NDEBUG
   void dumpUses(unsigned RegNo) const;
 #endif
 
   /// Returns true if PhysReg is unallocatable and constant throughout the
   /// function. Writing to a constant register has no effect.
   bool isConstantPhysReg(unsigned PhysReg) const;
 
+  /// Returns true if PhysReg is always preserved by the caller.
+  bool isCallerPreservedPhysReg(unsigned PhysReg) const;
+
   /// Get an iterator over the pressure sets affected by the given physical or
   /// virtual register. If RegUnit is physical, it must be a register unit (from
   /// MCRegUnitIterator).
   PSetIterator getPressureSets(unsigned RegUnit) const;
 
   //===--------------------------------------------------------------------===//
   // Virtual Register Info
   //===--------------------------------------------------------------------===//

include/llvm/Target/TargetRegisterInfo.h

public:
   /// register as well, to avoid them getting allocated indirectly. You may use
   /// markSuperRegs() and checkAllSuperRegsMarked() in this case.
   virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0;
 
   /// Returns true if PhysReg is unallocatable and constant throughout the
   /// function.  Used by MachineRegisterInfo::isConstantPhysReg().
   virtual bool isConstantPhysReg(unsigned PhysReg) const { return false; }
 
+  /// Returns true if PhysReg is always caller saved.  
+  /// Used by MachineRegisterInfo::isCallerPreservedPhysReg().
+  virtual bool isCallerPreservedPhysReg(unsigned PhysReg,
+                                        const MachineFunction &MF) const {
+    return false;
+  }
+
   /// Prior to adding the live-out mask to a stackmap or patchpoint
   /// instruction, provide the target the opportunity to adjust it (mainly to
   /// remove pseudo-registers that should be ignored).
   virtual void adjustStackMapLiveOutMask(uint32_t *Mask) const { }
 
   /// Return a super-register of the specified register
   /// Reg so its sub-register of index SubIdx is Reg.
   unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx,

lib/CodeGen/MachineLICM.cpp

if (!MO.isReg())
       continue;
 
     unsigned Reg = MO.getReg();
     if (Reg == 0) continue;
 
     // Don't hoist an instruction that uses or defines a physical register.
     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
       if (MO.isUse()) {
+        // If the physreg is known to always be caller saved/restored then
+        // this use is safe to hoist
+        if (MRI->isCallerPreservedPhysReg(Reg))
+          continue;
         // If the physreg has no defs anywhere, it's just an ambient register
         // and we can freely move its uses. Alternatively, if it's allocatable,
         // it could get allocated to something with a def during allocation.
         if (!MRI->isConstantPhysReg(Reg))
           return false;
         // Otherwise it's safe to move.
         continue;
       } else if (!MO.isDead()) {

lib/CodeGen/MachineRegisterInfo.cpp

bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg) const {
   // used later.
   for (MCRegAliasIterator AI(PhysReg, TRI, true);
        AI.isValid(); ++AI)
     if (!def_empty(*AI) || isAllocatable(*AI))
       return false;
   return true;
 }
 
+bool MachineRegisterInfo::isCallerPreservedPhysReg(unsigned PhysReg) const {
+  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg));
+  return getTargetRegisterInfo()->isCallerPreservedPhysReg(PhysReg, *MF);
+}
+
 /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
 /// specified register as undefined which causes the DBG_VALUE to be
 /// deleted during LiveDebugVariables analysis.
 void MachineRegisterInfo::markUsesInDebugValueAsUndef(unsigned Reg) const {
   // Mark any DBG_VALUE that uses Reg as undef (but don't delete it.)
   MachineRegisterInfo::use_instr_iterator nextI;
   for (use_instr_iterator I = use_instr_begin(Reg), E = use_instr_end();
        I != E; I = nextI) {

lib/Target/PowerPC/PPCRegisterInfo.h

public:
   const MCPhysReg *getCalleeSavedRegsViaCopy(const MachineFunction *MF) const;
   const uint32_t *getCallPreservedMask(const MachineFunction &MF,
                                        CallingConv::ID CC) const override;
   const uint32_t *getNoPreservedMask() const override;
 
   void adjustStackMapLiveOutMask(uint32_t *Mask) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
+  bool isCallerPreservedPhysReg(unsigned PhysReg, const MachineFunction &MF) const override;
 
   /// We require the register scavenger.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
 
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override {
     return true;

lib/Target/PowerPC/PPCRegisterInfo.cpp

if (!Subtarget.hasAltivec())
     for (TargetRegisterClass::iterator I = PPC::VRRCRegClass.begin(),
          IE = PPC::VRRCRegClass.end(); I != IE; ++I)
       markSuperRegs(Reserved, *I);
 
   assert(checkAllSuperRegsMarked(Reserved));
   return Reserved;
 }
 
+bool PPCRegisterInfo::isCallerPreservedPhysReg(unsigned PhysReg,
+                                               const MachineFunction &MF) const {
+  if (PhysReg == PPC::X2) {
+    // X2 is guaranteed to be preserved within a function if it is reserved.
+    // The reason it's reserved is that it's the TOC pointer (and the function
+    // uses the TOC). In functions where it isn't reserved (i.e. leaf functions
+    // with no TOC access), we can't claim that it is preserved.
+    return (getReservedRegs(MF).test(PPC::X2));
+  } else {
+    return false;
+  }
+}
+
 unsigned PPCRegisterInfo::getRegPressureLimit(const TargetRegisterClass *RC,
                                               MachineFunction &MF) const {
   const PPCFrameLowering *TFI = getFrameLowering(MF);
   const unsigned DefaultSafety = 1;
 
   switch (RC->getID()) {
   default:
     return 0;

test/CodeGen/PowerPC/licm-tocReg.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
+
+@ga = external global i32, align 4
+@gb = external global i32, align 4
+
+; Function Attrs: nounwind
+define signext i32 @test(i32 (i32)* nocapture %FP) local_unnamed_addr #0 {
+; CHECK-LABEL: test:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    addis 4, 2, .LC0@toc@ha
+; CHECK-NEXT:    addis 5, 2, .LC1@toc@ha
+; CHECK-NEXT:    ld 4, .LC0@toc@l(4)
+; CHECK-NEXT:    ld 5, .LC1@toc@l(5)
+; CHECK-NEXT:    lwz 6, 0(4)
+; CHECK-NEXT:    lwz 5, 0(5)
+; CHECK-NEXT:    cmpw 6, 5
+; CHECK-NEXT:    lwz 5, 0(4)
+; CHECK-NEXT:    mr 4, 3
+; CHECK-NEXT:    bgt 0, .LBB0_3
+; CHECK-NEXT:  # BB#1:
+; CHECK-NEXT:    addis 3, 2, .LC0@toc@ha
+; CHECK-NEXT:    addis 6, 2, .LC1@toc@ha
+; CHECK-NEXT:    ld 3, .LC0@toc@l(3)
+; CHECK-NEXT:    ld 6, .LC1@toc@l(6)
+; CHECK-NEXT:    .p2align 5
+; CHECK-NEXT:  .LBB0_2: # %if.end
+; CHECK-NOT:    addis {{[0-9]+}}, 2, .LC0@toc@ha
+; CHECK-NOT:    addis {{[0-9]+}}, 2, .LC1@toc@ha
+; CHECK:    blr
+entry:
+  %0 = load volatile i32, i32* @ga, align 4
+  %1 = load volatile i32, i32* @gb, align 4
+  %cmp1 = icmp sgt i32 %0, %1
+  %2 = load volatile i32, i32* @ga, align 4
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %if.end, %entry
+  %.lcssa = phi i32 [ %2, %entry ], [ %6, %if.end ]
+  %call = tail call signext i32 %FP(i32 signext %.lcssa) #1
+  ret i32 %call
+
+if.end:                                           ; preds = %entry, %if.end
+  %3 = phi i32 [ %6, %if.end ], [ %2, %entry ]
+  %inc = add nsw i32 %3, 1
+  store volatile i32 %inc, i32* @ga, align 4
+  %4 = load volatile i32, i32* @ga, align 4
+  %5 = load volatile i32, i32* @gb, align 4
+  %cmp = icmp sgt i32 %4, %5
+  %6 = load volatile i32, i32* @ga, align 4
+  br i1 %cmp, label %if.then, label %if.end
+}