[SPARC] Fix register reuse in leaf function remapping step

[LemonBoy]

Summary

Leaf functions allow the compiler to omit the setup and teardown of a frame pointer, therefore avoiding the exchange of the in/out register. According to the SPARC architecture manual every reference to %i0-%i5 should be replaced with %o0-o5, if the target register is already in use a further remapping step to %g1-%g7 is required to free the output register.

Add a simple check to make sure not to stomp on any output register that's already in use.

[koakuma]

Ping. Anything else that is need to be done for this?

[dcederman]

Hello!

It seems that this patch contains a rewrite of the remapRegsForLeafProc() function in addition to the new check described in the summary. Could you split it up into two patches, one with the rewrite and one with the added check?

Is the problem that the isLeafProc() does not detect the case when inline assembly clobbers one of the output registers or have you been able to trigger it in some other way? Does it make sense to put the extra check in isLeafProc() instead?

llvm/lib/Target/Sparc/SparcFrameLowering.cpp

394–396

Remove these tab characters.

[koakuma]

In D102342#3060935, @dcederman wrote:

Hello!

It seems that this patch contains a rewrite of the remapRegsForLeafProc() function in addition to the new check described in the summary. Could you split it up into two patches, one with the rewrite and one with the added check?

I'm not sure about this. The way I see it is that the checks need to be done together with the rewrite, so it probably cannot be split like that (?)

Is the problem that the isLeafProc() does not detect the case when inline assembly clobbers one of the output registers

No, the problem is that on functions with more than six parameters, when leaf function optimization is turned on, the function might be compiled in such a way that the loading of 7th-and-further parameters corrupts the value of other parameters.
This does not happen on functions with six or less parameters, even with inline assembly inside.

For example, on current LLVM, the testcase in the patch compiles to this:

leaf_proc_give_up:
    ld [%sp+2227], %o5 # The original value of %o5 is lost here
                       # causing the inline assembly to run with
                       # the wrong register values.
    mov     %o0, %g1
    mov     %o1, %o0
    mov     %o2, %o1
    mov     %o3, %o2
    mov     %o4, %o3
    mov     %o5, %o4
    !APP
    !NO_APP
    retl
    nop

As far as I can tell, there are three solutions for this: (1) reorder the code so the loads happen after the movs, (2) load the parameter to a temporary register first then move it to %o5 after all the other movs are done, or (3) simply bail out of the optimization entirely, as is done in this patch.

or have you been able to trigger it in some other way?

So far the only way I know to trigger this is with inline assembly (we encountered this when we're trying to write a system call wrapper for Linux).

Does it make sense to put the extra check in isLeafProc() instead?

I guess it is possible to do that by flagging all functions that has more than six parametes as nonleaf (so the optimization wouldn't be triggered), but I'm afraid that it'd be too aggressive.

[dcederman]

In D102342#3069943, @koakuma wrote:

In D102342#3060935, @dcederman wrote:

Hello!

It seems that this patch contains a rewrite of the remapRegsForLeafProc() function in addition to the new check described in the summary. Could you split it up into two patches, one with the rewrite and one with the added check?

I'm not sure about this. The way I see it is that the checks need to be done together with the rewrite, so it probably cannot be split like that (?)

The only functional change I can see is the check at line 345-348, and that should be in SparcFrameLowering::isLeafProc(). Then you do not need to rewrite determineCalleeSaves(). Or is there some functional change that I'm missing?

isLeafProc() checks if %L0 is used to determine if any of the %L or %O registers are used since the %I registers are allocated first. But it breaks if inline assembly code uses any of %L or %O. I ran into this bug before and fixed it by adding some code in tryInlineAsm() to mark the function as ineligible for leaf optimization if any of the %L or %O registers were used. So that is an alternative approach. But this approach is fine be me, but the check should be in isLeafProc().

[LemonBoy]

But this approach is fine be me, but the check should be in isLeafProc().

The section H.12 of the SPARC Architecture manual outlines the whole register remapping process that requires the re-allocation of %oN to free %gN registers if needed, I didn't implement the whole thing because of time/interest constraints but as it's written it should be relatively easy to add the missing steps.

[koakuma]

Ping.

In D102342#3129148, @LemonBoy wrote:

The section H.12 of the SPARC Architecture manual outlines the whole register remapping process that requires the re-allocation of %oN to free %gN registers if needed, I didn't implement the whole thing because of time/interest constraints but as it's written it should be relatively easy to add the missing steps.

I tried to implement this, but as far as I understand it, it's impossible (or at least very hard) to do when it's already this late because even if we manage to put the load result in a %gN register, there's no way to emit an extra mov to get the value into %o5.
Also, as an additional note, functions that does not contain inline assembly generates the correct code on unpatched LLVM, so I believe the existing register remapping is already mostly working as intended.

I propose keeping the remapRegsForLeafProc() as is and add a check to isLeafProc() so that it refuses to optimize a function if it contains inline assembly instead. To me, it seems that it's a less invasive option, what do you think?

[koakuma]

Ping? Anything else needs to be done for this?

[brad]

In D102342#3396043, @koakuma wrote:

Ping? Anything else needs to be done for this?

This needs to be rebased. Since you had a proposal for additional changes did you want to post your own diff?

llvm/lib/Target/Sparc/SparcFrameLowering.h

public:
 
   /// targetHandlesStackFrameRounding - Returns true if the target is
   /// responsible for rounding up the stack frame (probably at emitPrologue
   /// time).
   bool targetHandlesStackFrameRounding() const override { return true; }
 
 private:
   // Remap input registers to output registers for leaf procedure.
-  void remapRegsForLeafProc(MachineFunction &MF) const;
+  bool remapRegsForLeafProc(MachineFunction &MF) const;
 
   // Returns true if MF is a leaf procedure.
   bool isLeafProc(MachineFunction &MF) const;
 
 
   // Emits code for adjusting SP in function prologue/epilogue.
   void emitSPAdjustment(MachineFunction &MF,
                         MachineBasicBlock &MBB,
                         MachineBasicBlock::iterator MBBI,
                         int NumBytes, unsigned ADDrr, unsigned ADDri) const;
 
 };
 
 } // End llvm namespace
 
 #endif

llvm/lib/Target/Sparc/SparcFrameLowering.cpp

bool SparcFrameLowering::isLeafProc(MachineFunction &MF) const
   MachineFrameInfo    &MFI = MF.getFrameInfo();
 
   return !(MFI.hasCalls()                  // has calls
            || MRI.isPhysRegUsed(SP::L0)    // Too many registers needed
            || MRI.isPhysRegUsed(SP::O6)    // %sp is used
            || hasFP(MF));                  // need %fp
 }
 
-void SparcFrameLowering::remapRegsForLeafProc(MachineFunction &MF) const {
+bool SparcFrameLowering::remapRegsForLeafProc(MachineFunction &MF) const {
   MachineRegisterInfo &MRI = MF.getRegInfo();
+
+  // Registers to remap.
+  const Register InRegs[7] = {
+      SP::I0, SP::I1, SP::I2, SP::I3, SP::I4, SP::I5, SP::I7,
+  };
+
+  auto PairReg = [](Register R) -> Register {
+    return (R - SP::I0) / 2 + SP::I0_I1;
+  };
+  auto OutReg = [](Register R, bool Pair = false) -> Register {
+    if (Pair)
+      return (R - SP::I0) / 2 + SP::O0_O1;
+    return R - SP::I0 + SP::O0;
+  };
+
+  // Remap every use of %iN to %oN, but only if the destination register is
+  // free. We could handle that case by remapping the occupied output registers
+  // into some free %gN ones, but here we simply give up instead.
+  for (Register Reg : InRegs) {
+    if (MRI.isPhysRegUsed(Reg) && MRI.isPhysRegUsed(OutReg(Reg)))
+      return false;
+  }
+
   // Remap %i[0-7] to %o[0-7].
-  for (unsigned reg = SP::I0; reg <= SP::I7; ++reg) {
-    if (!MRI.isPhysRegUsed(reg))
+  for (Register Reg : InRegs) {
+    if (!MRI.isPhysRegUsed(Reg))
       continue;
 
-    unsigned mapped_reg = reg - SP::I0 + SP::O0;
-
     // Replace I register with O register.
-    MRI.replaceRegWith(reg, mapped_reg);
+    MRI.replaceRegWith(Reg, OutReg(Reg));
 
     // Also replace register pair super-registers.
-    if ((reg - SP::I0) % 2 == 0) {
-      unsigned preg = (reg - SP::I0) / 2 + SP::I0_I1;
-      unsigned mapped_preg = preg - SP::I0_I1 + SP::O0_O1;
-      MRI.replaceRegWith(preg, mapped_preg);
+    if ((Reg - SP::I0) % 2 == 0) {
+      MRI.replaceRegWith(PairReg(Reg), OutReg(Reg, true));
     }
   }
 
   // Rewrite MBB's Live-ins.
-  for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
-       MBB != E; ++MBB) {
-    for (unsigned reg = SP::I0_I1; reg <= SP::I6_I7; ++reg) {
-      if (!MBB->isLiveIn(reg))
+  for (MachineBasicBlock &MBB : MF) {
+    for (unsigned Reg = SP::I0_I1; Reg <= SP::I6_I7; ++Reg) {
+      if (!MBB.isLiveIn(Reg))
         continue;
-      MBB->removeLiveIn(reg);
-      MBB->addLiveIn(reg - SP::I0_I1 + SP::O0_O1);
+      MBB.removeLiveIn(Reg);
+      MBB.addLiveIn(OutReg(Reg, true));
     }
-    for (unsigned reg = SP::I0; reg <= SP::I7; ++reg) {
-      if (!MBB->isLiveIn(reg))
+    for (unsigned Reg = SP::I0; Reg <= SP::I7; ++Reg) {
+      if (!MBB.isLiveIn(Reg))
         continue;
-      MBB->removeLiveIn(reg);
-      MBB->addLiveIn(reg - SP::I0 + SP::O0);
+      MBB.removeLiveIn(Reg);
+      MBB.addLiveIn(OutReg(Reg));
     }
   }
 
   assert(verifyLeafProcRegUse(&MRI));
 #ifdef EXPENSIVE_CHECKS
   MF.verify(0, "After LeafProc Remapping");
 #endif
+
+  return true;
 }
 
 void SparcFrameLowering::determineCalleeSaves(MachineFunction &MF,
                                               BitVector &SavedRegs,
                                               RegScavenger *RS) const {
   TargetFrameLowering::determineCalleeSaves(MF, SavedRegs, RS);
   if (!DisableLeafProc && isLeafProc(MF)) {
+    if (remapRegsForLeafProc(MF)) {
       SparcMachineFunctionInfo *MFI = MF.getInfo<SparcMachineFunctionInfo>();
       MFI->setLeafProc(true);
-
-    remapRegsForLeafProc(MF);
     }
-
+  }
 }

llvm/test/CodeGen/SPARC/leafproc.ll

entry:
   %1 = getelementptr inbounds [2 x i32], [2 x i32]* %array, i32 0, i32 0
   store i32 1, i32* %1, align 4
   %2 = getelementptr inbounds [2 x i32], [2 x i32]* %array, i32 0, i32 1
   store i32 2, i32* %2, align 4
   %3 = getelementptr inbounds [2 x i32], [2 x i32]* %array, i32 0, i32 %a
   %4 = load i32, i32* %3, align 4
   ret i32 %4
 }
+
+; Here we have a leaf function where all the in and out registers are used and
+; where the register allocator is loading the sixth argument into %o5, making
+; the register renumbering fail.
+; As a result the function is not marked as being a leaf one.
+
+; CHECK-LABEL: leaf_proc_give_up
+; CHECK: save %sp, -96, %sp
+; CHECK: ld [%fp+92], %o5
+; CHECK: mov %i0, %g1
+; CHECK: mov %i1, %o0
+; CHECK: mov %i2, %o1
+; CHECK: mov %i3, %o2
+; CHECK: mov %i4, %o3
+; CHECK: mov %i5, %o4
+; CHECK: ret
+; CHECK-NEXT: restore %g0, %o0, %o0
+
+define i32 @leaf_proc_give_up(i32 %0, i32 %1, i32 %2, i32 %3, i32 %4, i32 %5, i32 %6) {
+Entry:
+  %g = call i32 asm sideeffect "", "={o0},{g1},{o0},{o1},{o2},{o3},{o4},{o5}"(i32 %0, i32 %1, i32 %2, i32 %3, i32 %4, i32 %5, i32 %6)
+  ret i32 %g
+}