1 //===-- AVRFrameLowering.cpp - AVR Frame Information ----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the AVR implementation of TargetFrameLowering class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "AVRFrameLowering.h"
14 
15 #include "AVR.h"
16 #include "AVRInstrInfo.h"
17 #include "AVRMachineFunctionInfo.h"
18 #include "AVRTargetMachine.h"
19 #include "MCTargetDesc/AVRMCTargetDesc.h"
20 
21 #include "llvm/CodeGen/MachineFrameInfo.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineFunctionPass.h"
24 #include "llvm/CodeGen/MachineInstrBuilder.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/IR/Function.h"
27 
28 #include <vector>
29 
30 namespace llvm {
31 
32 AVRFrameLowering::AVRFrameLowering()
33     : TargetFrameLowering(TargetFrameLowering::StackGrowsDown, Align(1), -2) {}
34 
35 bool AVRFrameLowering::canSimplifyCallFramePseudos(
36     const MachineFunction &MF) const {
37   // Always simplify call frame pseudo instructions, even when
38   // hasReservedCallFrame is false.
39   return true;
40 }
41 
42 bool AVRFrameLowering::hasReservedCallFrame(const MachineFunction &MF) const {
43   // Reserve call frame memory in function prologue under the following
44   // conditions:
45   // - Y pointer is reserved to be the frame pointer.
46   // - The function does not contain variable sized objects.
47 
48   const MachineFrameInfo &MFI = MF.getFrameInfo();
49   return hasFP(MF) && !MFI.hasVarSizedObjects();
50 }
51 
52 void AVRFrameLowering::emitPrologue(MachineFunction &MF,
53                                     MachineBasicBlock &MBB) const {
54   MachineBasicBlock::iterator MBBI = MBB.begin();
55   DebugLoc DL = (MBBI != MBB.end()) ? MBBI->getDebugLoc() : DebugLoc();
56   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
57   const AVRInstrInfo &TII = *STI.getInstrInfo();
58   const AVRMachineFunctionInfo *AFI = MF.getInfo<AVRMachineFunctionInfo>();
59   bool HasFP = hasFP(MF);
60 
61   // Interrupt handlers re-enable interrupts in function entry.
62   if (AFI->isInterruptHandler()) {
63     BuildMI(MBB, MBBI, DL, TII.get(AVR::BSETs))
64         .addImm(0x07)
65         .setMIFlag(MachineInstr::FrameSetup);
66   }
67 
68   // Emit special prologue code to save R1, R0 and SREG in interrupt/signal
69   // handlers before saving any other registers.
70   if (AFI->isInterruptOrSignalHandler()) {
71     BuildMI(MBB, MBBI, DL, TII.get(AVR::PUSHWRr))
72         .addReg(AVR::R1R0, RegState::Kill)
73         .setMIFlag(MachineInstr::FrameSetup);
74 
75     BuildMI(MBB, MBBI, DL, TII.get(AVR::INRdA), AVR::R0)
76         .addImm(0x3f)
77         .setMIFlag(MachineInstr::FrameSetup);
78     BuildMI(MBB, MBBI, DL, TII.get(AVR::PUSHRr))
79         .addReg(AVR::R0, RegState::Kill)
80         .setMIFlag(MachineInstr::FrameSetup);
81     BuildMI(MBB, MBBI, DL, TII.get(AVR::EORRdRr))
82         .addReg(AVR::R0, RegState::Define)
83         .addReg(AVR::R0, RegState::Kill)
84         .addReg(AVR::R0, RegState::Kill)
85         .setMIFlag(MachineInstr::FrameSetup);
86   }
87 
88   // Early exit if the frame pointer is not needed in this function.
89   if (!HasFP) {
90     return;
91   }
92 
93   const MachineFrameInfo &MFI = MF.getFrameInfo();
94   unsigned FrameSize = MFI.getStackSize() - AFI->getCalleeSavedFrameSize();
95 
96   // Skip the callee-saved push instructions.
97   while (
98       (MBBI != MBB.end()) && MBBI->getFlag(MachineInstr::FrameSetup) &&
99       (MBBI->getOpcode() == AVR::PUSHRr || MBBI->getOpcode() == AVR::PUSHWRr)) {
100     ++MBBI;
101   }
102 
103   // Update Y with the new base value.
104   BuildMI(MBB, MBBI, DL, TII.get(AVR::SPREAD), AVR::R29R28)
105       .addReg(AVR::SP)
106       .setMIFlag(MachineInstr::FrameSetup);
107 
108   // Mark the FramePtr as live-in in every block except the entry.
109   for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
110        I != E; ++I) {
111     I->addLiveIn(AVR::R29R28);
112   }
113 
114   if (!FrameSize) {
115     return;
116   }
117 
118   // Reserve the necessary frame memory by doing FP -= <size>.
119   unsigned Opcode = (isUInt<6>(FrameSize)) ? AVR::SBIWRdK : AVR::SUBIWRdK;
120 
121   MachineInstr *MI = BuildMI(MBB, MBBI, DL, TII.get(Opcode), AVR::R29R28)
122                          .addReg(AVR::R29R28, RegState::Kill)
123                          .addImm(FrameSize)
124                          .setMIFlag(MachineInstr::FrameSetup);
125   // The SREG implicit def is dead.
126   MI->getOperand(3).setIsDead();
127 
128   // Write back R29R28 to SP and temporarily disable interrupts.
129   BuildMI(MBB, MBBI, DL, TII.get(AVR::SPWRITE), AVR::SP)
130       .addReg(AVR::R29R28)
131       .setMIFlag(MachineInstr::FrameSetup);
132 }
133 
134 void AVRFrameLowering::emitEpilogue(MachineFunction &MF,
135                                     MachineBasicBlock &MBB) const {
136   const AVRMachineFunctionInfo *AFI = MF.getInfo<AVRMachineFunctionInfo>();
137 
138   // Early exit if the frame pointer is not needed in this function except for
139   // signal/interrupt handlers where special code generation is required.
140   if (!hasFP(MF) && !AFI->isInterruptOrSignalHandler()) {
141     return;
142   }
143 
144   MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
145   assert(MBBI->getDesc().isReturn() &&
146          "Can only insert epilog into returning blocks");
147 
148   DebugLoc DL = MBBI->getDebugLoc();
149   const MachineFrameInfo &MFI = MF.getFrameInfo();
150   unsigned FrameSize = MFI.getStackSize() - AFI->getCalleeSavedFrameSize();
151   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
152   const AVRInstrInfo &TII = *STI.getInstrInfo();
153 
154   // Emit special epilogue code to restore R1, R0 and SREG in interrupt/signal
155   // handlers at the very end of the function, just before reti.
156   if (AFI->isInterruptOrSignalHandler()) {
157     BuildMI(MBB, MBBI, DL, TII.get(AVR::POPRd), AVR::R0);
158     BuildMI(MBB, MBBI, DL, TII.get(AVR::OUTARr))
159         .addImm(0x3f)
160         .addReg(AVR::R0, RegState::Kill);
161     BuildMI(MBB, MBBI, DL, TII.get(AVR::POPWRd), AVR::R1R0);
162   }
163 
164   // Early exit if there is no need to restore the frame pointer.
165   if (!FrameSize) {
166     return;
167   }
168 
169   // Skip the callee-saved pop instructions.
170   while (MBBI != MBB.begin()) {
171     MachineBasicBlock::iterator PI = std::prev(MBBI);
172     int Opc = PI->getOpcode();
173 
174     if (Opc != AVR::POPRd && Opc != AVR::POPWRd && !PI->isTerminator()) {
175       break;
176     }
177 
178     --MBBI;
179   }
180 
181   unsigned Opcode;
182 
183   // Select the optimal opcode depending on how big it is.
184   if (isUInt<6>(FrameSize)) {
185     Opcode = AVR::ADIWRdK;
186   } else {
187     Opcode = AVR::SUBIWRdK;
188     FrameSize = -FrameSize;
189   }
190 
191   // Restore the frame pointer by doing FP += <size>.
192   MachineInstr *MI = BuildMI(MBB, MBBI, DL, TII.get(Opcode), AVR::R29R28)
193                          .addReg(AVR::R29R28, RegState::Kill)
194                          .addImm(FrameSize);
195   // The SREG implicit def is dead.
196   MI->getOperand(3).setIsDead();
197 
198   // Write back R29R28 to SP and temporarily disable interrupts.
199   BuildMI(MBB, MBBI, DL, TII.get(AVR::SPWRITE), AVR::SP)
200       .addReg(AVR::R29R28, RegState::Kill);
201 }
202 
203 // Return true if the specified function should have a dedicated frame
204 // pointer register. This is true if the function meets any of the following
205 // conditions:
206 //  - a register has been spilled
207 //  - has allocas
208 //  - input arguments are passed using the stack
209 //
210 // Notice that strictly this is not a frame pointer because it contains SP after
211 // frame allocation instead of having the original SP in function entry.
212 bool AVRFrameLowering::hasFP(const MachineFunction &MF) const {
213   const AVRMachineFunctionInfo *FuncInfo = MF.getInfo<AVRMachineFunctionInfo>();
214 
215   return (FuncInfo->getHasSpills() || FuncInfo->getHasAllocas() ||
216           FuncInfo->getHasStackArgs());
217 }
218 
219 bool AVRFrameLowering::spillCalleeSavedRegisters(
220     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
221     ArrayRef<CalleeSavedInfo> CSI, const TargetRegisterInfo *TRI) const {
222   if (CSI.empty()) {
223     return false;
224   }
225 
226   unsigned CalleeFrameSize = 0;
227   DebugLoc DL = MBB.findDebugLoc(MI);
228   MachineFunction &MF = *MBB.getParent();
229   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
230   const TargetInstrInfo &TII = *STI.getInstrInfo();
231   AVRMachineFunctionInfo *AVRFI = MF.getInfo<AVRMachineFunctionInfo>();
232 
233   for (unsigned i = CSI.size(); i != 0; --i) {
234     unsigned Reg = CSI[i - 1].getReg();
235     bool IsNotLiveIn = !MBB.isLiveIn(Reg);
236 
237     assert(TRI->getRegSizeInBits(*TRI->getMinimalPhysRegClass(Reg)) == 8 &&
238            "Invalid register size");
239 
240     // Add the callee-saved register as live-in only if it is not already a
241     // live-in register, this usually happens with arguments that are passed
242     // through callee-saved registers.
243     if (IsNotLiveIn) {
244       MBB.addLiveIn(Reg);
245     }
246 
247     // Do not kill the register when it is an input argument.
248     BuildMI(MBB, MI, DL, TII.get(AVR::PUSHRr))
249         .addReg(Reg, getKillRegState(IsNotLiveIn))
250         .setMIFlag(MachineInstr::FrameSetup);
251     ++CalleeFrameSize;
252   }
253 
254   AVRFI->setCalleeSavedFrameSize(CalleeFrameSize);
255 
256   return true;
257 }
258 
259 bool AVRFrameLowering::restoreCalleeSavedRegisters(
260     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
261     MutableArrayRef<CalleeSavedInfo> CSI, const TargetRegisterInfo *TRI) const {
262   if (CSI.empty()) {
263     return false;
264   }
265 
266   DebugLoc DL = MBB.findDebugLoc(MI);
267   const MachineFunction &MF = *MBB.getParent();
268   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
269   const TargetInstrInfo &TII = *STI.getInstrInfo();
270 
271   for (const CalleeSavedInfo &CCSI : CSI) {
272     unsigned Reg = CCSI.getReg();
273 
274     assert(TRI->getRegSizeInBits(*TRI->getMinimalPhysRegClass(Reg)) == 8 &&
275            "Invalid register size");
276 
277     BuildMI(MBB, MI, DL, TII.get(AVR::POPRd), Reg);
278   }
279 
280   return true;
281 }
282 
283 /// Replace pseudo store instructions that pass arguments through the stack with
284 /// real instructions.
285 static void fixStackStores(MachineBasicBlock &MBB,
286                            MachineBasicBlock::iterator MI,
287                            const TargetInstrInfo &TII, Register FP) {
288   // Iterate through the BB until we hit a call instruction or we reach the end.
289   for (auto I = MI, E = MBB.end(); I != E && !I->isCall();) {
290     MachineBasicBlock::iterator NextMI = std::next(I);
291     MachineInstr &MI = *I;
292     unsigned Opcode = I->getOpcode();
293 
294     // Only care of pseudo store instructions where SP is the base pointer.
295     if (Opcode != AVR::STDSPQRr && Opcode != AVR::STDWSPQRr) {
296       I = NextMI;
297       continue;
298     }
299 
300     assert(MI.getOperand(0).getReg() == AVR::SP &&
301            "Invalid register, should be SP!");
302 
303     // Replace this instruction with a regular store. Use Y as the base
304     // pointer since it is guaranteed to contain a copy of SP.
305     unsigned STOpc =
306         (Opcode == AVR::STDWSPQRr) ? AVR::STDWPtrQRr : AVR::STDPtrQRr;
307 
308     MI.setDesc(TII.get(STOpc));
309     MI.getOperand(0).setReg(FP);
310 
311     I = NextMI;
312   }
313 }
314 
315 MachineBasicBlock::iterator AVRFrameLowering::eliminateCallFramePseudoInstr(
316     MachineFunction &MF, MachineBasicBlock &MBB,
317     MachineBasicBlock::iterator MI) const {
318   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
319   const AVRInstrInfo &TII = *STI.getInstrInfo();
320 
321   // There is nothing to insert when the call frame memory is allocated during
322   // function entry. Delete the call frame pseudo and replace all pseudo stores
323   // with real store instructions.
324   if (hasReservedCallFrame(MF)) {
325     fixStackStores(MBB, MI, TII, AVR::R29R28);
326     return MBB.erase(MI);
327   }
328 
329   DebugLoc DL = MI->getDebugLoc();
330   unsigned int Opcode = MI->getOpcode();
331   int Amount = TII.getFrameSize(*MI);
332 
333   // ADJCALLSTACKUP and ADJCALLSTACKDOWN are converted to adiw/subi
334   // instructions to read and write the stack pointer in I/O space.
335   if (Amount != 0) {
336     assert(getStackAlign() == Align(1) && "Unsupported stack alignment");
337 
338     if (Opcode == TII.getCallFrameSetupOpcode()) {
339       // Update the stack pointer.
340       // In many cases this can be done far more efficiently by pushing the
341       // relevant values directly to the stack. However, doing that correctly
342       // (in the right order, possibly skipping some empty space for undef
343       // values, etc) is tricky and thus left to be optimized in the future.
344       BuildMI(MBB, MI, DL, TII.get(AVR::SPREAD), AVR::R31R30).addReg(AVR::SP);
345 
346       MachineInstr *New = BuildMI(MBB, MI, DL, TII.get(AVR::SUBIWRdK), AVR::R31R30)
347                               .addReg(AVR::R31R30, RegState::Kill)
348                               .addImm(Amount);
349       New->getOperand(3).setIsDead();
350 
351       BuildMI(MBB, MI, DL, TII.get(AVR::SPWRITE), AVR::SP)
352           .addReg(AVR::R31R30, RegState::Kill);
353 
354       // Make sure the remaining stack stores are converted to real store
355       // instructions.
356       fixStackStores(MBB, MI, TII, AVR::R31R30);
357     } else {
358       assert(Opcode == TII.getCallFrameDestroyOpcode());
359 
360       // Note that small stack changes could be implemented more efficiently
361       // with a few pop instructions instead of the 8-9 instructions now
362       // required.
363 
364       // Select the best opcode to adjust SP based on the offset size.
365       unsigned addOpcode;
366       if (isUInt<6>(Amount)) {
367         addOpcode = AVR::ADIWRdK;
368       } else {
369         addOpcode = AVR::SUBIWRdK;
370         Amount = -Amount;
371       }
372 
373       // Build the instruction sequence.
374       BuildMI(MBB, MI, DL, TII.get(AVR::SPREAD), AVR::R31R30).addReg(AVR::SP);
375 
376       MachineInstr *New = BuildMI(MBB, MI, DL, TII.get(addOpcode), AVR::R31R30)
377                               .addReg(AVR::R31R30, RegState::Kill)
378                               .addImm(Amount);
379       New->getOperand(3).setIsDead();
380 
381       BuildMI(MBB, MI, DL, TII.get(AVR::SPWRITE), AVR::SP)
382           .addReg(AVR::R31R30, RegState::Kill);
383     }
384   }
385 
386   return MBB.erase(MI);
387 }
388 
389 void AVRFrameLowering::determineCalleeSaves(MachineFunction &MF,
390                                             BitVector &SavedRegs,
391                                             RegScavenger *RS) const {
392   TargetFrameLowering::determineCalleeSaves(MF, SavedRegs, RS);
393 
394   // If we have a frame pointer, the Y register needs to be saved as well.
395   if (hasFP(MF)) {
396     SavedRegs.set(AVR::R29);
397     SavedRegs.set(AVR::R28);
398   }
399 }
400 /// The frame analyzer pass.
401 ///
402 /// Scans the function for allocas and used arguments
403 /// that are passed through the stack.
404 struct AVRFrameAnalyzer : public MachineFunctionPass {
405   static char ID;
406   AVRFrameAnalyzer() : MachineFunctionPass(ID) {}
407 
408   bool runOnMachineFunction(MachineFunction &MF) override {
409     const MachineFrameInfo &MFI = MF.getFrameInfo();
410     AVRMachineFunctionInfo *FuncInfo = MF.getInfo<AVRMachineFunctionInfo>();
411 
412     // If there are no fixed frame indexes during this stage it means there
413     // are allocas present in the function.
414     if (MFI.getNumObjects() != MFI.getNumFixedObjects()) {
415       // Check for the type of allocas present in the function. We only care
416       // about fixed size allocas so do not give false positives if only
417       // variable sized allocas are present.
418       for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
419         // Variable sized objects have size 0.
420         if (MFI.getObjectSize(i)) {
421           FuncInfo->setHasAllocas(true);
422           break;
423         }
424       }
425     }
426 
427     // If there are fixed frame indexes present, scan the function to see if
428     // they are really being used.
429     if (MFI.getNumFixedObjects() == 0) {
430       return false;
431     }
432 
433     // Ok fixed frame indexes present, now scan the function to see if they
434     // are really being used, otherwise we can ignore them.
435     for (const MachineBasicBlock &BB : MF) {
436       for (const MachineInstr &MI : BB) {
437         int Opcode = MI.getOpcode();
438 
439         if ((Opcode != AVR::LDDRdPtrQ) && (Opcode != AVR::LDDWRdPtrQ) &&
440             (Opcode != AVR::STDPtrQRr) && (Opcode != AVR::STDWPtrQRr)) {
441           continue;
442         }
443 
444         for (const MachineOperand &MO : MI.operands()) {
445           if (!MO.isFI()) {
446             continue;
447           }
448 
449           if (MFI.isFixedObjectIndex(MO.getIndex())) {
450             FuncInfo->setHasStackArgs(true);
451             return false;
452           }
453         }
454       }
455     }
456 
457     return false;
458   }
459 
460   StringRef getPassName() const override { return "AVR Frame Analyzer"; }
461 };
462 
463 char AVRFrameAnalyzer::ID = 0;
464 
465 /// Creates instance of the frame analyzer pass.
466 FunctionPass *createAVRFrameAnalyzerPass() { return new AVRFrameAnalyzer(); }
467 
468 /// Create the Dynalloca Stack Pointer Save/Restore pass.
469 /// Insert a copy of SP before allocating the dynamic stack memory and restore
470 /// it in function exit to restore the original SP state. This avoids the need
471 /// of reserving a register pair for a frame pointer.
472 struct AVRDynAllocaSR : public MachineFunctionPass {
473   static char ID;
474   AVRDynAllocaSR() : MachineFunctionPass(ID) {}
475 
476   bool runOnMachineFunction(MachineFunction &MF) override {
477     // Early exit when there are no variable sized objects in the function.
478     if (!MF.getFrameInfo().hasVarSizedObjects()) {
479       return false;
480     }
481 
482     const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
483     const TargetInstrInfo &TII = *STI.getInstrInfo();
484     MachineBasicBlock &EntryMBB = MF.front();
485     MachineBasicBlock::iterator MBBI = EntryMBB.begin();
486     DebugLoc DL = EntryMBB.findDebugLoc(MBBI);
487 
488     Register SPCopy =
489         MF.getRegInfo().createVirtualRegister(&AVR::DREGSRegClass);
490 
491     // Create a copy of SP in function entry before any dynallocas are
492     // inserted.
493     BuildMI(EntryMBB, MBBI, DL, TII.get(AVR::COPY), SPCopy).addReg(AVR::SP);
494 
495     // Restore SP in all exit basic blocks.
496     for (MachineBasicBlock &MBB : MF) {
497       // If last instruction is a return instruction, add a restore copy.
498       if (!MBB.empty() && MBB.back().isReturn()) {
499         MBBI = MBB.getLastNonDebugInstr();
500         DL = MBBI->getDebugLoc();
501         BuildMI(MBB, MBBI, DL, TII.get(AVR::COPY), AVR::SP)
502             .addReg(SPCopy, RegState::Kill);
503       }
504     }
505 
506     return true;
507   }
508 
509   StringRef getPassName() const override {
510     return "AVR dynalloca stack pointer save/restore";
511   }
512 };
513 
514 char AVRDynAllocaSR::ID = 0;
515 
516 /// createAVRDynAllocaSRPass - returns an instance of the dynalloca stack
517 /// pointer save/restore pass.
518 FunctionPass *createAVRDynAllocaSRPass() { return new AVRDynAllocaSR(); }
519 
520 } // end of namespace llvm
521 
522