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