[AVR] Remove redundant dynalloca SP save/restore pass

[aykevl]

Summary

I think this pass was previously used under the assumption that most
functions would not need a frame pointer and it would be more efficient
to store the old stack pointer in a regular register pair.

Unfortunately, right now we're forced to always reserve the Y register
as a frame pointer: whether or not this is needed is only known after
regsiter allocation at which point it doesn't make sense anymore to mark
it as non-reserved. Therefore, it makes sense to use the Y register to
store the old stack pointer in functions with dynamic allocas (with a
variable size or not in the entry block). Knowing this can make the code
around dynamic allocas a lot simpler: simply save/restore the frame
pointer.

This is especially relevant in functions that have a frame pointer
anyway (for example, because they have stack spills). The stack restore
in the epilogue will implicitly restore the old stack pointer, so there
is no need to store the old stack pointer separately. It even reduces
register pressure as a side effect.

---

Warning: I haven't really tested this outside of the unit tests (and studying the output assembly). I'm not exactly sure how to test this, maybe by linking some test code with an existing program to check that it works as expected? However, the assembly looks good to me.
I checked compiler-rt and picolibc and both don't have any dynamic stack allocation (as I should have expected).

To be clear: this patch is meant as a refactor/cleanup, not as a codegen improvement (even though it is a codegen improvement).

[aykevl]

It looks like this is related to the following bug: https://bugs.llvm.org/show_bug.cgi?id=31349

[aykevl]

Ping?
I'm working on an optimization that appears to require this patch.

[benshi001]

So your patch only affects functions which has variable size objects,

1. Use frame pointer
2. Use the fixed frame pointer (Y register) instead of dynamically allocated register pair to store the old SP.

[benshi001]

I am OK with this change. But it seems you need to rebase your code.

llvm/lib/Target/AVR/AVR.h

 class FunctionPass;
 
 Pass *createAVRShiftExpandPass();
 FunctionPass *createAVRISelDag(AVRTargetMachine &TM,
                                CodeGenOpt::Level OptLevel);
 FunctionPass *createAVRExpandPseudoPass();
 FunctionPass *createAVRFrameAnalyzerPass();
 FunctionPass *createAVRRelaxMemPass();
-FunctionPass *createAVRDynAllocaSRPass();
 FunctionPass *createAVRBranchSelectionPass();
 
 void initializeAVRShiftExpandPass(PassRegistry &);
 void initializeAVRExpandPseudoPass(PassRegistry &);
 void initializeAVRRelaxMemPass(PassRegistry &);
 
 /// Contains the AVR backend.
 namespace AVR {

llvm/lib/Target/AVR/AVRFrameLowering.cpp

void AVRFrameLowering::emitEpilogue(MachineFunction &MF,
 
   DebugLoc DL = MBBI->getDebugLoc();
   const MachineFrameInfo &MFI = MF.getFrameInfo();
   unsigned FrameSize = MFI.getStackSize() - AFI->getCalleeSavedFrameSize();
   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
   const AVRInstrInfo &TII = *STI.getInstrInfo();
 
   // Early exit if there is no need to restore the frame pointer.
-  if (!FrameSize) {
+  if (!FrameSize && !MF.getFrameInfo().hasVarSizedObjects()) {
     restoreStatusRegister(MF, MBB);
     return;
   }
 
   // Skip the callee-saved pop instructions.
   while (MBBI != MBB.begin()) {
     MachineBasicBlock::iterator PI = std::prev(MBBI);
     int Opc = PI->getOpcode();
 
     if (Opc != AVR::POPRd && Opc != AVR::POPWRd && !PI->isTerminator()) {
       break;
     }
 
     --MBBI;
   }
 
+  if (FrameSize) {
     unsigned Opcode;
 
     // Select the optimal opcode depending on how big it is.
     if (isUInt<6>(FrameSize)) {
       Opcode = AVR::ADIWRdK;
     } else {
       Opcode = AVR::SUBIWRdK;
       FrameSize = -FrameSize;
     }
 
     // Restore the frame pointer by doing FP += <size>.
     MachineInstr *MI = BuildMI(MBB, MBBI, DL, TII.get(Opcode), AVR::R29R28)
                           .addReg(AVR::R29R28, RegState::Kill)
                           .addImm(FrameSize);
     // The SREG implicit def is dead.
     MI->getOperand(3).setIsDead();
+  }
 
   // Write back R29R28 to SP and temporarily disable interrupts.
   BuildMI(MBB, MBBI, DL, TII.get(AVR::SPWRITE), AVR::SP)
       .addReg(AVR::R29R28, RegState::Kill);
 
   restoreStatusRegister(MF, MBB);
 }
 
 // Return true if the specified function should have a dedicated frame
 // pointer register. This is true if the function meets any of the following
 // conditions:
 //  - a register has been spilled
 //  - has allocas
 //  - input arguments are passed using the stack
 //
 // Notice that strictly this is not a frame pointer because it contains SP after
 // frame allocation instead of having the original SP in function entry.
 bool AVRFrameLowering::hasFP(const MachineFunction &MF) const {
   const AVRMachineFunctionInfo *FuncInfo = MF.getInfo<AVRMachineFunctionInfo>();
 
   return (FuncInfo->getHasSpills() || FuncInfo->getHasAllocas() ||
-          FuncInfo->getHasStackArgs());
+          FuncInfo->getHasStackArgs() ||
+          MF.getFrameInfo().hasVarSizedObjects());
 }
 
 bool AVRFrameLowering::spillCalleeSavedRegisters(
     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
     ArrayRef<CalleeSavedInfo> CSI, const TargetRegisterInfo *TRI) const {
   if (CSI.empty()) {
     return false;
   }
struct AVRFrameAnalyzer : public MachineFunctionPass {
   StringRef getPassName() const override { return "AVR Frame Analyzer"; }
 };
 
 char AVRFrameAnalyzer::ID = 0;
 
 /// Creates instance of the frame analyzer pass.
 FunctionPass *createAVRFrameAnalyzerPass() { return new AVRFrameAnalyzer(); }
 
-/// Create the Dynalloca Stack Pointer Save/Restore pass.
-/// Insert a copy of SP before allocating the dynamic stack memory and restore
-/// it in function exit to restore the original SP state. This avoids the need
-/// of reserving a register pair for a frame pointer.
-struct AVRDynAllocaSR : public MachineFunctionPass {
-  static char ID;
-  AVRDynAllocaSR() : MachineFunctionPass(ID) {}
-
-  bool runOnMachineFunction(MachineFunction &MF) override {
-    // Early exit when there are no variable sized objects in the function.
-    if (!MF.getFrameInfo().hasVarSizedObjects()) {
-      return false;
-    }
-
-    const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
-    const TargetInstrInfo &TII = *STI.getInstrInfo();
-    MachineBasicBlock &EntryMBB = MF.front();
-    MachineBasicBlock::iterator MBBI = EntryMBB.begin();
-    DebugLoc DL = EntryMBB.findDebugLoc(MBBI);
-
-    Register SPCopy =
-        MF.getRegInfo().createVirtualRegister(&AVR::DREGSRegClass);
-
-    // Create a copy of SP in function entry before any dynallocas are
-    // inserted.
-    BuildMI(EntryMBB, MBBI, DL, TII.get(AVR::COPY), SPCopy).addReg(AVR::SP);
-
-    // Restore SP in all exit basic blocks.
-    for (MachineBasicBlock &MBB : MF) {
-      // If last instruction is a return instruction, add a restore copy.
-      if (!MBB.empty() && MBB.back().isReturn()) {
-        MBBI = MBB.getLastNonDebugInstr();
-        DL = MBBI->getDebugLoc();
-        BuildMI(MBB, MBBI, DL, TII.get(AVR::COPY), AVR::SP)
-            .addReg(SPCopy, RegState::Kill);
-      }
-    }
-
-    return true;
-  }
-
-  StringRef getPassName() const override {
-    return "AVR dynalloca stack pointer save/restore";
-  }
-};
-
-char AVRDynAllocaSR::ID = 0;
-
-/// createAVRDynAllocaSRPass - returns an instance of the dynalloca stack
-/// pointer save/restore pass.
-FunctionPass *createAVRDynAllocaSRPass() { return new AVRDynAllocaSR(); }
-
 } // end of namespace llvm

llvm/lib/Target/AVR/AVRTargetMachine.cpp

public:
   AVRTargetMachine &getAVRTargetMachine() const {
     return getTM<AVRTargetMachine>();
   }
 
   void addIRPasses() override;
   bool addInstSelector() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
-  void addPreRegAlloc() override;
 };
 } // namespace
 
 TargetPassConfig *AVRTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new AVRPassConfig(*this, PM);
 }
 
 void AVRPassConfig::addIRPasses() {
bool AVRPassConfig::addInstSelector() {
   // Install an instruction selector.
   addPass(createAVRISelDag(getAVRTargetMachine(), getOptLevel()));
   // Create the frame analyzer pass used by the PEI pass.
   addPass(createAVRFrameAnalyzerPass());
 
   return false;
 }
 
-void AVRPassConfig::addPreRegAlloc() {
-  // Create the dynalloc SP save/restore pass to handle variable sized allocas.
-  addPass(createAVRDynAllocaSRPass());
-}
-
 void AVRPassConfig::addPreSched2() {
   addPass(createAVRRelaxMemPass());
   addPass(createAVRExpandPseudoPass());
 }
 
 void AVRPassConfig::addPreEmitPass() {
   // Must run branch selection immediately preceding the asm printer.
   addPass(&BranchRelaxationPassID);
 }
 
 } // end of namespace llvm

llvm/test/CodeGen/AVR/dynalloca.ll

 ; RUN: llc < %s -march=avr | FileCheck %s
 
 declare void @foo(i16*, i16*, i8*)
 
 define void @test1(i16 %x) {
 ; CHECK-LABEL: test1:
+; Frame setup, with frame pointer
+; CHECK: in r28, 61
+; CHECK: in r29, 62
 ; CHECK: out 61, r28
-; SP copy
-; CHECK-NEXT: in [[SPCOPY1:r[0-9]+]], 61
-; CHECK-NEXT: in [[SPCOPY2:r[0-9]+]], 62
 ; allocate first dynalloca
 ; CHECK: in {{.*}}, 61
 ; CHECK: in {{.*}}, 62
 ; CHECK: sub
 ; CHECK: sbc
 ; CHECK: in r0, 63
 ; CHECK-NEXT: cli
 ; CHECK-NEXT: out 62, {{.*}}
 ; CHECK-NEXT: out 63, r0
 ; CHECK-NEXT: out 61, {{.*}}
 ; Test writes
 ; CHECK: std Z+12, {{.*}}
 ; CHECK: std Z+13, {{.*}}
 ; CHECK: std Z+7, {{.*}}
 ; CHECK-NOT: std
 ; Test SP restore
 ; CHECK: in r0, 63
 ; CHECK-NEXT: cli
-; CHECK-NEXT: out 62, [[SPCOPY2]]
+; CHECK-NEXT: out 62, r29
 ; CHECK-NEXT: out 63, r0
-; CHECK-NEXT: out 61, [[SPCOPY1]]
+; CHECK-NEXT: out 61, r28
   %a = alloca [8 x i16]
   %vla = alloca i16, i16 %x
   %add = shl nsw i16 %x, 1
   %vla1 = alloca i8, i16 %add
   %arrayidx = getelementptr inbounds [8 x i16], [8 x i16]* %a, i16 0, i16 2
   store i16 3, i16* %arrayidx
   %arrayidx2 = getelementptr inbounds i16, i16* %vla, i16 6
   store i16 4, i16* %arrayidx2
   %arrayidx3 = getelementptr inbounds i8, i8* %vla1, i16 7
   store i8 44, i8* %arrayidx3
   %arraydecay = getelementptr inbounds [8 x i16], [8 x i16]* %a, i16 0, i16 0
   call void @foo(i16* %arraydecay, i16* %vla, i8* %vla1)
   ret void
 }
 
 declare void @foo2(i16*, i64, i64, i64)
 
 ; Test that arguments are passed through pushes into the call instead of
 ; allocating the call frame space in the prologue. Also test that SP is restored
 ; after the call frame is restored and not before.
 define void @dynalloca2(i16 %x) {
 ; CHECK-LABEL: dynalloca2:
-; CHECK: in [[SPCOPY1:r[0-9]+]], 61
-; CHECK: in [[SPCOPY2:r[0-9]+]], 62
+; CHECK: in r28, 61
+; CHECK: in r29, 62
 ; Allocate stack space for call
 ; CHECK: in {{.*}}, 61
 ; CHECK: in {{.*}}, 62
 ; CHECK: subi
 ; CHECK: sbci
 ; CHECK: in r0, 63
 ; CHECK-NEXT: cli
 ; CHECK-NEXT: out 62, {{.*}}

 ; CHECK-NEXT: in r0, 63
 ; CHECK-NEXT: cli
 ; CHECK-NEXT: out 62, r31
 ; CHECK-NEXT: out 63, r0
 ; CHECK-NEXT: out 61, r30
 ; SP restore
 ; CHECK: in r0, 63
 ; CHECK-NEXT: cli
-; CHECK-NEXT: out 62, r7
+; CHECK-NEXT: out 62, r29
 ; CHECK-NEXT: out 63, r0
-; CHECK-NEXT: out 61, r6
+; CHECK-NEXT: out 61, r28
   %vla = alloca i16, i16 %x
   call void @foo2(i16* %vla, i64 0, i64 0, i64 0)
   ret void
 }
+
+; Test a function with a variable sized object but without any other need for a
+; frame pointer.
+; Allocas that are not placed in the entry block are considered variable sized
+; (they could be in a loop).
+define void @dynalloca3() {
+; CHECK-LABEL: dynalloca3:
+; Read frame pointer
+; CHECK:      in r28, 61
+; CHECK-NEXT: in r29, 62
+; Allocate memory for the alloca
+; CHECK-NEXT: in r24, 61
+; CHECK-NEXT: in r25, 62
+; CHECK-NEXT: sbiw r24, 8
+; CHECK-NEXT: in r0, 63
+; CHECK-NEXT: cli
+; CHECK-NEXT: out 62, r25
+; CHECK-NEXT: out 63, r0
+; CHECK-NEXT: out 61, r24
+; Restore frame pointer
+; CHECK-NEXT: in r0, 63
+; CHECK-NEXT: cli
+; CHECK-NEXT: out 62, r29
+; CHECK-NEXT: out 63, r0
+; CHECK-NEXT: out 61, r28
+  br label %1
+1:
+  %a = alloca i64
+  ret void
+}