xref: /aosp_15_r20/external/llvm/lib/CodeGen/PrologEpilogInserter.cpp (revision 9880d6810fe72a1726cb53787c6711e909410d58)
1*9880d681SAndroid Build Coastguard Worker //===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===//
2*9880d681SAndroid Build Coastguard Worker //
3*9880d681SAndroid Build Coastguard Worker //                     The LLVM Compiler Infrastructure
4*9880d681SAndroid Build Coastguard Worker //
5*9880d681SAndroid Build Coastguard Worker // This file is distributed under the University of Illinois Open Source
6*9880d681SAndroid Build Coastguard Worker // License. See LICENSE.TXT for details.
7*9880d681SAndroid Build Coastguard Worker //
8*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===//
9*9880d681SAndroid Build Coastguard Worker //
10*9880d681SAndroid Build Coastguard Worker // This pass is responsible for finalizing the functions frame layout, saving
11*9880d681SAndroid Build Coastguard Worker // callee saved registers, and for emitting prolog & epilog code for the
12*9880d681SAndroid Build Coastguard Worker // function.
13*9880d681SAndroid Build Coastguard Worker //
14*9880d681SAndroid Build Coastguard Worker // This pass must be run after register allocation.  After this pass is
15*9880d681SAndroid Build Coastguard Worker // executed, it is illegal to construct MO_FrameIndex operands.
16*9880d681SAndroid Build Coastguard Worker //
17*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===//
18*9880d681SAndroid Build Coastguard Worker 
19*9880d681SAndroid Build Coastguard Worker #include "llvm/ADT/STLExtras.h"
20*9880d681SAndroid Build Coastguard Worker #include "llvm/ADT/SetVector.h"
21*9880d681SAndroid Build Coastguard Worker #include "llvm/ADT/SmallSet.h"
22*9880d681SAndroid Build Coastguard Worker #include "llvm/ADT/Statistic.h"
23*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineDominators.h"
24*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineFrameInfo.h"
25*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineInstr.h"
26*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineLoopInfo.h"
27*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineModuleInfo.h"
28*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineRegisterInfo.h"
29*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/Passes.h"
30*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/RegisterScavenging.h"
31*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/StackProtector.h"
32*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/WinEHFuncInfo.h"
33*9880d681SAndroid Build Coastguard Worker #include "llvm/IR/DiagnosticInfo.h"
34*9880d681SAndroid Build Coastguard Worker #include "llvm/IR/InlineAsm.h"
35*9880d681SAndroid Build Coastguard Worker #include "llvm/IR/LLVMContext.h"
36*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/CommandLine.h"
37*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/Debug.h"
38*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/raw_ostream.h"
39*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetFrameLowering.h"
40*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetInstrInfo.h"
41*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetMachine.h"
42*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetRegisterInfo.h"
43*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetSubtargetInfo.h"
44*9880d681SAndroid Build Coastguard Worker #include <climits>
45*9880d681SAndroid Build Coastguard Worker 
46*9880d681SAndroid Build Coastguard Worker using namespace llvm;
47*9880d681SAndroid Build Coastguard Worker 
48*9880d681SAndroid Build Coastguard Worker #define DEBUG_TYPE "pei"
49*9880d681SAndroid Build Coastguard Worker 
50*9880d681SAndroid Build Coastguard Worker typedef SmallVector<MachineBasicBlock *, 4> MBBVector;
51*9880d681SAndroid Build Coastguard Worker static void doSpillCalleeSavedRegs(MachineFunction &MF, RegScavenger *RS,
52*9880d681SAndroid Build Coastguard Worker                                    unsigned &MinCSFrameIndex,
53*9880d681SAndroid Build Coastguard Worker                                    unsigned &MaxCXFrameIndex,
54*9880d681SAndroid Build Coastguard Worker                                    const MBBVector &SaveBlocks,
55*9880d681SAndroid Build Coastguard Worker                                    const MBBVector &RestoreBlocks);
56*9880d681SAndroid Build Coastguard Worker 
57*9880d681SAndroid Build Coastguard Worker static void doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS);
58*9880d681SAndroid Build Coastguard Worker 
59*9880d681SAndroid Build Coastguard Worker namespace {
60*9880d681SAndroid Build Coastguard Worker class PEI : public MachineFunctionPass {
61*9880d681SAndroid Build Coastguard Worker public:
62*9880d681SAndroid Build Coastguard Worker   static char ID;
PEI(const TargetMachine * TM=nullptr)63*9880d681SAndroid Build Coastguard Worker   explicit PEI(const TargetMachine *TM = nullptr) : MachineFunctionPass(ID) {
64*9880d681SAndroid Build Coastguard Worker     initializePEIPass(*PassRegistry::getPassRegistry());
65*9880d681SAndroid Build Coastguard Worker 
66*9880d681SAndroid Build Coastguard Worker     if (TM && (!TM->usesPhysRegsForPEI())) {
67*9880d681SAndroid Build Coastguard Worker       SpillCalleeSavedRegisters = [](MachineFunction &, RegScavenger *,
68*9880d681SAndroid Build Coastguard Worker                                      unsigned &, unsigned &, const MBBVector &,
69*9880d681SAndroid Build Coastguard Worker                                      const MBBVector &) {};
70*9880d681SAndroid Build Coastguard Worker       ScavengeFrameVirtualRegs = [](MachineFunction &, RegScavenger *) {};
71*9880d681SAndroid Build Coastguard Worker     } else {
72*9880d681SAndroid Build Coastguard Worker       SpillCalleeSavedRegisters = doSpillCalleeSavedRegs;
73*9880d681SAndroid Build Coastguard Worker       ScavengeFrameVirtualRegs = doScavengeFrameVirtualRegs;
74*9880d681SAndroid Build Coastguard Worker       UsesCalleeSaves = true;
75*9880d681SAndroid Build Coastguard Worker     }
76*9880d681SAndroid Build Coastguard Worker   }
77*9880d681SAndroid Build Coastguard Worker 
78*9880d681SAndroid Build Coastguard Worker   void getAnalysisUsage(AnalysisUsage &AU) const override;
79*9880d681SAndroid Build Coastguard Worker 
getRequiredProperties() const80*9880d681SAndroid Build Coastguard Worker   MachineFunctionProperties getRequiredProperties() const override {
81*9880d681SAndroid Build Coastguard Worker     MachineFunctionProperties MFP;
82*9880d681SAndroid Build Coastguard Worker     if (UsesCalleeSaves)
83*9880d681SAndroid Build Coastguard Worker       MFP.set(MachineFunctionProperties::Property::AllVRegsAllocated);
84*9880d681SAndroid Build Coastguard Worker     return MFP;
85*9880d681SAndroid Build Coastguard Worker   }
86*9880d681SAndroid Build Coastguard Worker 
87*9880d681SAndroid Build Coastguard Worker   /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
88*9880d681SAndroid Build Coastguard Worker   /// frame indexes with appropriate references.
89*9880d681SAndroid Build Coastguard Worker   ///
90*9880d681SAndroid Build Coastguard Worker   bool runOnMachineFunction(MachineFunction &Fn) override;
91*9880d681SAndroid Build Coastguard Worker 
92*9880d681SAndroid Build Coastguard Worker private:
93*9880d681SAndroid Build Coastguard Worker   std::function<void(MachineFunction &MF, RegScavenger *RS,
94*9880d681SAndroid Build Coastguard Worker                      unsigned &MinCSFrameIndex, unsigned &MaxCSFrameIndex,
95*9880d681SAndroid Build Coastguard Worker                      const MBBVector &SaveBlocks,
96*9880d681SAndroid Build Coastguard Worker                      const MBBVector &RestoreBlocks)>
97*9880d681SAndroid Build Coastguard Worker       SpillCalleeSavedRegisters;
98*9880d681SAndroid Build Coastguard Worker   std::function<void(MachineFunction &MF, RegScavenger *RS)>
99*9880d681SAndroid Build Coastguard Worker       ScavengeFrameVirtualRegs;
100*9880d681SAndroid Build Coastguard Worker 
101*9880d681SAndroid Build Coastguard Worker   bool UsesCalleeSaves = false;
102*9880d681SAndroid Build Coastguard Worker 
103*9880d681SAndroid Build Coastguard Worker   RegScavenger *RS;
104*9880d681SAndroid Build Coastguard Worker 
105*9880d681SAndroid Build Coastguard Worker   // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
106*9880d681SAndroid Build Coastguard Worker   // stack frame indexes.
107*9880d681SAndroid Build Coastguard Worker   unsigned MinCSFrameIndex = std::numeric_limits<unsigned>::max();
108*9880d681SAndroid Build Coastguard Worker   unsigned MaxCSFrameIndex = 0;
109*9880d681SAndroid Build Coastguard Worker 
110*9880d681SAndroid Build Coastguard Worker   // Save and Restore blocks of the current function. Typically there is a
111*9880d681SAndroid Build Coastguard Worker   // single save block, unless Windows EH funclets are involved.
112*9880d681SAndroid Build Coastguard Worker   MBBVector SaveBlocks;
113*9880d681SAndroid Build Coastguard Worker   MBBVector RestoreBlocks;
114*9880d681SAndroid Build Coastguard Worker 
115*9880d681SAndroid Build Coastguard Worker   // Flag to control whether to use the register scavenger to resolve
116*9880d681SAndroid Build Coastguard Worker   // frame index materialization registers. Set according to
117*9880d681SAndroid Build Coastguard Worker   // TRI->requiresFrameIndexScavenging() for the current function.
118*9880d681SAndroid Build Coastguard Worker   bool FrameIndexVirtualScavenging;
119*9880d681SAndroid Build Coastguard Worker 
120*9880d681SAndroid Build Coastguard Worker   void calculateCallFrameInfo(MachineFunction &Fn);
121*9880d681SAndroid Build Coastguard Worker   void calculateSaveRestoreBlocks(MachineFunction &Fn);
122*9880d681SAndroid Build Coastguard Worker 
123*9880d681SAndroid Build Coastguard Worker   void calculateFrameObjectOffsets(MachineFunction &Fn);
124*9880d681SAndroid Build Coastguard Worker   void replaceFrameIndices(MachineFunction &Fn);
125*9880d681SAndroid Build Coastguard Worker   void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
126*9880d681SAndroid Build Coastguard Worker                            int &SPAdj);
127*9880d681SAndroid Build Coastguard Worker   void insertPrologEpilogCode(MachineFunction &Fn);
128*9880d681SAndroid Build Coastguard Worker };
129*9880d681SAndroid Build Coastguard Worker } // namespace
130*9880d681SAndroid Build Coastguard Worker 
131*9880d681SAndroid Build Coastguard Worker char PEI::ID = 0;
132*9880d681SAndroid Build Coastguard Worker char &llvm::PrologEpilogCodeInserterID = PEI::ID;
133*9880d681SAndroid Build Coastguard Worker 
134*9880d681SAndroid Build Coastguard Worker static cl::opt<unsigned>
135*9880d681SAndroid Build Coastguard Worker WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
136*9880d681SAndroid Build Coastguard Worker               cl::desc("Warn for stack size bigger than the given"
137*9880d681SAndroid Build Coastguard Worker                        " number"));
138*9880d681SAndroid Build Coastguard Worker 
139*9880d681SAndroid Build Coastguard Worker INITIALIZE_TM_PASS_BEGIN(PEI, "prologepilog", "Prologue/Epilogue Insertion",
140*9880d681SAndroid Build Coastguard Worker                          false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)141*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
142*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
143*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_DEPENDENCY(StackProtector)
144*9880d681SAndroid Build Coastguard Worker INITIALIZE_TM_PASS_END(PEI, "prologepilog",
145*9880d681SAndroid Build Coastguard Worker                        "Prologue/Epilogue Insertion & Frame Finalization",
146*9880d681SAndroid Build Coastguard Worker                        false, false)
147*9880d681SAndroid Build Coastguard Worker 
148*9880d681SAndroid Build Coastguard Worker MachineFunctionPass *
149*9880d681SAndroid Build Coastguard Worker llvm::createPrologEpilogInserterPass(const TargetMachine *TM) {
150*9880d681SAndroid Build Coastguard Worker   return new PEI(TM);
151*9880d681SAndroid Build Coastguard Worker }
152*9880d681SAndroid Build Coastguard Worker 
153*9880d681SAndroid Build Coastguard Worker STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
154*9880d681SAndroid Build Coastguard Worker STATISTIC(NumBytesStackSpace,
155*9880d681SAndroid Build Coastguard Worker           "Number of bytes used for stack in all functions");
156*9880d681SAndroid Build Coastguard Worker 
getAnalysisUsage(AnalysisUsage & AU) const157*9880d681SAndroid Build Coastguard Worker void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
158*9880d681SAndroid Build Coastguard Worker   AU.setPreservesCFG();
159*9880d681SAndroid Build Coastguard Worker   AU.addPreserved<MachineLoopInfo>();
160*9880d681SAndroid Build Coastguard Worker   AU.addPreserved<MachineDominatorTree>();
161*9880d681SAndroid Build Coastguard Worker   AU.addRequired<StackProtector>();
162*9880d681SAndroid Build Coastguard Worker   MachineFunctionPass::getAnalysisUsage(AU);
163*9880d681SAndroid Build Coastguard Worker }
164*9880d681SAndroid Build Coastguard Worker 
165*9880d681SAndroid Build Coastguard Worker 
166*9880d681SAndroid Build Coastguard Worker /// StackObjSet - A set of stack object indexes
167*9880d681SAndroid Build Coastguard Worker typedef SmallSetVector<int, 8> StackObjSet;
168*9880d681SAndroid Build Coastguard Worker 
169*9880d681SAndroid Build Coastguard Worker /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
170*9880d681SAndroid Build Coastguard Worker /// frame indexes with appropriate references.
171*9880d681SAndroid Build Coastguard Worker ///
runOnMachineFunction(MachineFunction & Fn)172*9880d681SAndroid Build Coastguard Worker bool PEI::runOnMachineFunction(MachineFunction &Fn) {
173*9880d681SAndroid Build Coastguard Worker   const Function* F = Fn.getFunction();
174*9880d681SAndroid Build Coastguard Worker   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
175*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
176*9880d681SAndroid Build Coastguard Worker 
177*9880d681SAndroid Build Coastguard Worker   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : nullptr;
178*9880d681SAndroid Build Coastguard Worker   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
179*9880d681SAndroid Build Coastguard Worker 
180*9880d681SAndroid Build Coastguard Worker   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
181*9880d681SAndroid Build Coastguard Worker   // function's frame information. Also eliminates call frame pseudo
182*9880d681SAndroid Build Coastguard Worker   // instructions.
183*9880d681SAndroid Build Coastguard Worker   calculateCallFrameInfo(Fn);
184*9880d681SAndroid Build Coastguard Worker 
185*9880d681SAndroid Build Coastguard Worker   // Determine placement of CSR spill/restore code and prolog/epilog code:
186*9880d681SAndroid Build Coastguard Worker   // place all spills in the entry block, all restores in return blocks.
187*9880d681SAndroid Build Coastguard Worker   calculateSaveRestoreBlocks(Fn);
188*9880d681SAndroid Build Coastguard Worker 
189*9880d681SAndroid Build Coastguard Worker   // Handle CSR spilling and restoring, for targets that need it.
190*9880d681SAndroid Build Coastguard Worker   SpillCalleeSavedRegisters(Fn, RS, MinCSFrameIndex, MaxCSFrameIndex,
191*9880d681SAndroid Build Coastguard Worker                             SaveBlocks, RestoreBlocks);
192*9880d681SAndroid Build Coastguard Worker 
193*9880d681SAndroid Build Coastguard Worker   // Allow the target machine to make final modifications to the function
194*9880d681SAndroid Build Coastguard Worker   // before the frame layout is finalized.
195*9880d681SAndroid Build Coastguard Worker   TFI->processFunctionBeforeFrameFinalized(Fn, RS);
196*9880d681SAndroid Build Coastguard Worker 
197*9880d681SAndroid Build Coastguard Worker   // Calculate actual frame offsets for all abstract stack objects...
198*9880d681SAndroid Build Coastguard Worker   calculateFrameObjectOffsets(Fn);
199*9880d681SAndroid Build Coastguard Worker 
200*9880d681SAndroid Build Coastguard Worker   // Add prolog and epilog code to the function.  This function is required
201*9880d681SAndroid Build Coastguard Worker   // to align the stack frame as necessary for any stack variables or
202*9880d681SAndroid Build Coastguard Worker   // called functions.  Because of this, calculateCalleeSavedRegisters()
203*9880d681SAndroid Build Coastguard Worker   // must be called before this function in order to set the AdjustsStack
204*9880d681SAndroid Build Coastguard Worker   // and MaxCallFrameSize variables.
205*9880d681SAndroid Build Coastguard Worker   if (!F->hasFnAttribute(Attribute::Naked))
206*9880d681SAndroid Build Coastguard Worker     insertPrologEpilogCode(Fn);
207*9880d681SAndroid Build Coastguard Worker 
208*9880d681SAndroid Build Coastguard Worker   // Replace all MO_FrameIndex operands with physical register references
209*9880d681SAndroid Build Coastguard Worker   // and actual offsets.
210*9880d681SAndroid Build Coastguard Worker   //
211*9880d681SAndroid Build Coastguard Worker   replaceFrameIndices(Fn);
212*9880d681SAndroid Build Coastguard Worker 
213*9880d681SAndroid Build Coastguard Worker   // If register scavenging is needed, as we've enabled doing it as a
214*9880d681SAndroid Build Coastguard Worker   // post-pass, scavenge the virtual registers that frame index elimination
215*9880d681SAndroid Build Coastguard Worker   // inserted.
216*9880d681SAndroid Build Coastguard Worker   if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging) {
217*9880d681SAndroid Build Coastguard Worker       ScavengeFrameVirtualRegs(Fn, RS);
218*9880d681SAndroid Build Coastguard Worker 
219*9880d681SAndroid Build Coastguard Worker       // Clear any vregs created by virtual scavenging.
220*9880d681SAndroid Build Coastguard Worker       Fn.getRegInfo().clearVirtRegs();
221*9880d681SAndroid Build Coastguard Worker   }
222*9880d681SAndroid Build Coastguard Worker 
223*9880d681SAndroid Build Coastguard Worker   // Warn on stack size when we exceeds the given limit.
224*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = Fn.getFrameInfo();
225*9880d681SAndroid Build Coastguard Worker   uint64_t StackSize = MFI->getStackSize();
226*9880d681SAndroid Build Coastguard Worker   if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) {
227*9880d681SAndroid Build Coastguard Worker     DiagnosticInfoStackSize DiagStackSize(*F, StackSize);
228*9880d681SAndroid Build Coastguard Worker     F->getContext().diagnose(DiagStackSize);
229*9880d681SAndroid Build Coastguard Worker   }
230*9880d681SAndroid Build Coastguard Worker 
231*9880d681SAndroid Build Coastguard Worker   delete RS;
232*9880d681SAndroid Build Coastguard Worker   SaveBlocks.clear();
233*9880d681SAndroid Build Coastguard Worker   RestoreBlocks.clear();
234*9880d681SAndroid Build Coastguard Worker   MFI->setSavePoint(nullptr);
235*9880d681SAndroid Build Coastguard Worker   MFI->setRestorePoint(nullptr);
236*9880d681SAndroid Build Coastguard Worker   return true;
237*9880d681SAndroid Build Coastguard Worker }
238*9880d681SAndroid Build Coastguard Worker 
239*9880d681SAndroid Build Coastguard Worker /// Calculate the MaxCallFrameSize and AdjustsStack
240*9880d681SAndroid Build Coastguard Worker /// variables for the function's frame information and eliminate call frame
241*9880d681SAndroid Build Coastguard Worker /// pseudo instructions.
calculateCallFrameInfo(MachineFunction & Fn)242*9880d681SAndroid Build Coastguard Worker void PEI::calculateCallFrameInfo(MachineFunction &Fn) {
243*9880d681SAndroid Build Coastguard Worker   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
244*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
245*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = Fn.getFrameInfo();
246*9880d681SAndroid Build Coastguard Worker 
247*9880d681SAndroid Build Coastguard Worker   unsigned MaxCallFrameSize = 0;
248*9880d681SAndroid Build Coastguard Worker   bool AdjustsStack = MFI->adjustsStack();
249*9880d681SAndroid Build Coastguard Worker 
250*9880d681SAndroid Build Coastguard Worker   // Get the function call frame set-up and tear-down instruction opcode
251*9880d681SAndroid Build Coastguard Worker   unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
252*9880d681SAndroid Build Coastguard Worker   unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
253*9880d681SAndroid Build Coastguard Worker 
254*9880d681SAndroid Build Coastguard Worker   // Early exit for targets which have no call frame setup/destroy pseudo
255*9880d681SAndroid Build Coastguard Worker   // instructions.
256*9880d681SAndroid Build Coastguard Worker   if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)
257*9880d681SAndroid Build Coastguard Worker     return;
258*9880d681SAndroid Build Coastguard Worker 
259*9880d681SAndroid Build Coastguard Worker   std::vector<MachineBasicBlock::iterator> FrameSDOps;
260*9880d681SAndroid Build Coastguard Worker   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
261*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
262*9880d681SAndroid Build Coastguard Worker       if (I->getOpcode() == FrameSetupOpcode ||
263*9880d681SAndroid Build Coastguard Worker           I->getOpcode() == FrameDestroyOpcode) {
264*9880d681SAndroid Build Coastguard Worker         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
265*9880d681SAndroid Build Coastguard Worker                " instructions should have a single immediate argument!");
266*9880d681SAndroid Build Coastguard Worker         unsigned Size = I->getOperand(0).getImm();
267*9880d681SAndroid Build Coastguard Worker         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
268*9880d681SAndroid Build Coastguard Worker         AdjustsStack = true;
269*9880d681SAndroid Build Coastguard Worker         FrameSDOps.push_back(I);
270*9880d681SAndroid Build Coastguard Worker       } else if (I->isInlineAsm()) {
271*9880d681SAndroid Build Coastguard Worker         // Some inline asm's need a stack frame, as indicated by operand 1.
272*9880d681SAndroid Build Coastguard Worker         unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
273*9880d681SAndroid Build Coastguard Worker         if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
274*9880d681SAndroid Build Coastguard Worker           AdjustsStack = true;
275*9880d681SAndroid Build Coastguard Worker       }
276*9880d681SAndroid Build Coastguard Worker 
277*9880d681SAndroid Build Coastguard Worker   MFI->setAdjustsStack(AdjustsStack);
278*9880d681SAndroid Build Coastguard Worker   MFI->setMaxCallFrameSize(MaxCallFrameSize);
279*9880d681SAndroid Build Coastguard Worker 
280*9880d681SAndroid Build Coastguard Worker   for (std::vector<MachineBasicBlock::iterator>::iterator
281*9880d681SAndroid Build Coastguard Worker          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
282*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock::iterator I = *i;
283*9880d681SAndroid Build Coastguard Worker 
284*9880d681SAndroid Build Coastguard Worker     // If call frames are not being included as part of the stack frame, and
285*9880d681SAndroid Build Coastguard Worker     // the target doesn't indicate otherwise, remove the call frame pseudos
286*9880d681SAndroid Build Coastguard Worker     // here. The sub/add sp instruction pairs are still inserted, but we don't
287*9880d681SAndroid Build Coastguard Worker     // need to track the SP adjustment for frame index elimination.
288*9880d681SAndroid Build Coastguard Worker     if (TFI->canSimplifyCallFramePseudos(Fn))
289*9880d681SAndroid Build Coastguard Worker       TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
290*9880d681SAndroid Build Coastguard Worker   }
291*9880d681SAndroid Build Coastguard Worker }
292*9880d681SAndroid Build Coastguard Worker 
293*9880d681SAndroid Build Coastguard Worker /// Compute the sets of entry and return blocks for saving and restoring
294*9880d681SAndroid Build Coastguard Worker /// callee-saved registers, and placing prolog and epilog code.
calculateSaveRestoreBlocks(MachineFunction & Fn)295*9880d681SAndroid Build Coastguard Worker void PEI::calculateSaveRestoreBlocks(MachineFunction &Fn) {
296*9880d681SAndroid Build Coastguard Worker   const MachineFrameInfo *MFI = Fn.getFrameInfo();
297*9880d681SAndroid Build Coastguard Worker 
298*9880d681SAndroid Build Coastguard Worker   // Even when we do not change any CSR, we still want to insert the
299*9880d681SAndroid Build Coastguard Worker   // prologue and epilogue of the function.
300*9880d681SAndroid Build Coastguard Worker   // So set the save points for those.
301*9880d681SAndroid Build Coastguard Worker 
302*9880d681SAndroid Build Coastguard Worker   // Use the points found by shrink-wrapping, if any.
303*9880d681SAndroid Build Coastguard Worker   if (MFI->getSavePoint()) {
304*9880d681SAndroid Build Coastguard Worker     SaveBlocks.push_back(MFI->getSavePoint());
305*9880d681SAndroid Build Coastguard Worker     assert(MFI->getRestorePoint() && "Both restore and save must be set");
306*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock *RestoreBlock = MFI->getRestorePoint();
307*9880d681SAndroid Build Coastguard Worker     // If RestoreBlock does not have any successor and is not a return block
308*9880d681SAndroid Build Coastguard Worker     // then the end point is unreachable and we do not need to insert any
309*9880d681SAndroid Build Coastguard Worker     // epilogue.
310*9880d681SAndroid Build Coastguard Worker     if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())
311*9880d681SAndroid Build Coastguard Worker       RestoreBlocks.push_back(RestoreBlock);
312*9880d681SAndroid Build Coastguard Worker     return;
313*9880d681SAndroid Build Coastguard Worker   }
314*9880d681SAndroid Build Coastguard Worker 
315*9880d681SAndroid Build Coastguard Worker   // Save refs to entry and return blocks.
316*9880d681SAndroid Build Coastguard Worker   SaveBlocks.push_back(&Fn.front());
317*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock &MBB : Fn) {
318*9880d681SAndroid Build Coastguard Worker     if (MBB.isEHFuncletEntry())
319*9880d681SAndroid Build Coastguard Worker       SaveBlocks.push_back(&MBB);
320*9880d681SAndroid Build Coastguard Worker     if (MBB.isReturnBlock())
321*9880d681SAndroid Build Coastguard Worker       RestoreBlocks.push_back(&MBB);
322*9880d681SAndroid Build Coastguard Worker   }
323*9880d681SAndroid Build Coastguard Worker }
324*9880d681SAndroid Build Coastguard Worker 
assignCalleeSavedSpillSlots(MachineFunction & F,const BitVector & SavedRegs,unsigned & MinCSFrameIndex,unsigned & MaxCSFrameIndex)325*9880d681SAndroid Build Coastguard Worker static void assignCalleeSavedSpillSlots(MachineFunction &F,
326*9880d681SAndroid Build Coastguard Worker                                         const BitVector &SavedRegs,
327*9880d681SAndroid Build Coastguard Worker                                         unsigned &MinCSFrameIndex,
328*9880d681SAndroid Build Coastguard Worker                                         unsigned &MaxCSFrameIndex) {
329*9880d681SAndroid Build Coastguard Worker   if (SavedRegs.empty())
330*9880d681SAndroid Build Coastguard Worker     return;
331*9880d681SAndroid Build Coastguard Worker 
332*9880d681SAndroid Build Coastguard Worker   const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
333*9880d681SAndroid Build Coastguard Worker   const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(&F);
334*9880d681SAndroid Build Coastguard Worker 
335*9880d681SAndroid Build Coastguard Worker   std::vector<CalleeSavedInfo> CSI;
336*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0; CSRegs[i]; ++i) {
337*9880d681SAndroid Build Coastguard Worker     unsigned Reg = CSRegs[i];
338*9880d681SAndroid Build Coastguard Worker     if (SavedRegs.test(Reg))
339*9880d681SAndroid Build Coastguard Worker       CSI.push_back(CalleeSavedInfo(Reg));
340*9880d681SAndroid Build Coastguard Worker   }
341*9880d681SAndroid Build Coastguard Worker 
342*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
343*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = F.getFrameInfo();
344*9880d681SAndroid Build Coastguard Worker   if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
345*9880d681SAndroid Build Coastguard Worker     // If target doesn't implement this, use generic code.
346*9880d681SAndroid Build Coastguard Worker 
347*9880d681SAndroid Build Coastguard Worker     if (CSI.empty())
348*9880d681SAndroid Build Coastguard Worker       return; // Early exit if no callee saved registers are modified!
349*9880d681SAndroid Build Coastguard Worker 
350*9880d681SAndroid Build Coastguard Worker     unsigned NumFixedSpillSlots;
351*9880d681SAndroid Build Coastguard Worker     const TargetFrameLowering::SpillSlot *FixedSpillSlots =
352*9880d681SAndroid Build Coastguard Worker         TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
353*9880d681SAndroid Build Coastguard Worker 
354*9880d681SAndroid Build Coastguard Worker     // Now that we know which registers need to be saved and restored, allocate
355*9880d681SAndroid Build Coastguard Worker     // stack slots for them.
356*9880d681SAndroid Build Coastguard Worker     for (auto &CS : CSI) {
357*9880d681SAndroid Build Coastguard Worker       unsigned Reg = CS.getReg();
358*9880d681SAndroid Build Coastguard Worker       const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
359*9880d681SAndroid Build Coastguard Worker 
360*9880d681SAndroid Build Coastguard Worker       int FrameIdx;
361*9880d681SAndroid Build Coastguard Worker       if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
362*9880d681SAndroid Build Coastguard Worker         CS.setFrameIdx(FrameIdx);
363*9880d681SAndroid Build Coastguard Worker         continue;
364*9880d681SAndroid Build Coastguard Worker       }
365*9880d681SAndroid Build Coastguard Worker 
366*9880d681SAndroid Build Coastguard Worker       // Check to see if this physreg must be spilled to a particular stack slot
367*9880d681SAndroid Build Coastguard Worker       // on this target.
368*9880d681SAndroid Build Coastguard Worker       const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
369*9880d681SAndroid Build Coastguard Worker       while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
370*9880d681SAndroid Build Coastguard Worker              FixedSlot->Reg != Reg)
371*9880d681SAndroid Build Coastguard Worker         ++FixedSlot;
372*9880d681SAndroid Build Coastguard Worker 
373*9880d681SAndroid Build Coastguard Worker       if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
374*9880d681SAndroid Build Coastguard Worker         // Nope, just spill it anywhere convenient.
375*9880d681SAndroid Build Coastguard Worker         unsigned Align = RC->getAlignment();
376*9880d681SAndroid Build Coastguard Worker         unsigned StackAlign = TFI->getStackAlignment();
377*9880d681SAndroid Build Coastguard Worker 
378*9880d681SAndroid Build Coastguard Worker         // We may not be able to satisfy the desired alignment specification of
379*9880d681SAndroid Build Coastguard Worker         // the TargetRegisterClass if the stack alignment is smaller. Use the
380*9880d681SAndroid Build Coastguard Worker         // min.
381*9880d681SAndroid Build Coastguard Worker         Align = std::min(Align, StackAlign);
382*9880d681SAndroid Build Coastguard Worker         FrameIdx = MFI->CreateStackObject(RC->getSize(), Align, true);
383*9880d681SAndroid Build Coastguard Worker         if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
384*9880d681SAndroid Build Coastguard Worker         if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
385*9880d681SAndroid Build Coastguard Worker       } else {
386*9880d681SAndroid Build Coastguard Worker         // Spill it to the stack where we must.
387*9880d681SAndroid Build Coastguard Worker         FrameIdx =
388*9880d681SAndroid Build Coastguard Worker             MFI->CreateFixedSpillStackObject(RC->getSize(), FixedSlot->Offset);
389*9880d681SAndroid Build Coastguard Worker       }
390*9880d681SAndroid Build Coastguard Worker 
391*9880d681SAndroid Build Coastguard Worker       CS.setFrameIdx(FrameIdx);
392*9880d681SAndroid Build Coastguard Worker     }
393*9880d681SAndroid Build Coastguard Worker   }
394*9880d681SAndroid Build Coastguard Worker 
395*9880d681SAndroid Build Coastguard Worker   MFI->setCalleeSavedInfo(CSI);
396*9880d681SAndroid Build Coastguard Worker }
397*9880d681SAndroid Build Coastguard Worker 
398*9880d681SAndroid Build Coastguard Worker /// Helper function to update the liveness information for the callee-saved
399*9880d681SAndroid Build Coastguard Worker /// registers.
updateLiveness(MachineFunction & MF)400*9880d681SAndroid Build Coastguard Worker static void updateLiveness(MachineFunction &MF) {
401*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = MF.getFrameInfo();
402*9880d681SAndroid Build Coastguard Worker   // Visited will contain all the basic blocks that are in the region
403*9880d681SAndroid Build Coastguard Worker   // where the callee saved registers are alive:
404*9880d681SAndroid Build Coastguard Worker   // - Anything that is not Save or Restore -> LiveThrough.
405*9880d681SAndroid Build Coastguard Worker   // - Save -> LiveIn.
406*9880d681SAndroid Build Coastguard Worker   // - Restore -> LiveOut.
407*9880d681SAndroid Build Coastguard Worker   // The live-out is not attached to the block, so no need to keep
408*9880d681SAndroid Build Coastguard Worker   // Restore in this set.
409*9880d681SAndroid Build Coastguard Worker   SmallPtrSet<MachineBasicBlock *, 8> Visited;
410*9880d681SAndroid Build Coastguard Worker   SmallVector<MachineBasicBlock *, 8> WorkList;
411*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock *Entry = &MF.front();
412*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock *Save = MFI->getSavePoint();
413*9880d681SAndroid Build Coastguard Worker 
414*9880d681SAndroid Build Coastguard Worker   if (!Save)
415*9880d681SAndroid Build Coastguard Worker     Save = Entry;
416*9880d681SAndroid Build Coastguard Worker 
417*9880d681SAndroid Build Coastguard Worker   if (Entry != Save) {
418*9880d681SAndroid Build Coastguard Worker     WorkList.push_back(Entry);
419*9880d681SAndroid Build Coastguard Worker     Visited.insert(Entry);
420*9880d681SAndroid Build Coastguard Worker   }
421*9880d681SAndroid Build Coastguard Worker   Visited.insert(Save);
422*9880d681SAndroid Build Coastguard Worker 
423*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock *Restore = MFI->getRestorePoint();
424*9880d681SAndroid Build Coastguard Worker   if (Restore)
425*9880d681SAndroid Build Coastguard Worker     // By construction Restore cannot be visited, otherwise it
426*9880d681SAndroid Build Coastguard Worker     // means there exists a path to Restore that does not go
427*9880d681SAndroid Build Coastguard Worker     // through Save.
428*9880d681SAndroid Build Coastguard Worker     WorkList.push_back(Restore);
429*9880d681SAndroid Build Coastguard Worker 
430*9880d681SAndroid Build Coastguard Worker   while (!WorkList.empty()) {
431*9880d681SAndroid Build Coastguard Worker     const MachineBasicBlock *CurBB = WorkList.pop_back_val();
432*9880d681SAndroid Build Coastguard Worker     // By construction, the region that is after the save point is
433*9880d681SAndroid Build Coastguard Worker     // dominated by the Save and post-dominated by the Restore.
434*9880d681SAndroid Build Coastguard Worker     if (CurBB == Save && Save != Restore)
435*9880d681SAndroid Build Coastguard Worker       continue;
436*9880d681SAndroid Build Coastguard Worker     // Enqueue all the successors not already visited.
437*9880d681SAndroid Build Coastguard Worker     // Those are by construction either before Save or after Restore.
438*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock *SuccBB : CurBB->successors())
439*9880d681SAndroid Build Coastguard Worker       if (Visited.insert(SuccBB).second)
440*9880d681SAndroid Build Coastguard Worker         WorkList.push_back(SuccBB);
441*9880d681SAndroid Build Coastguard Worker   }
442*9880d681SAndroid Build Coastguard Worker 
443*9880d681SAndroid Build Coastguard Worker   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
444*9880d681SAndroid Build Coastguard Worker 
445*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
446*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock *MBB : Visited) {
447*9880d681SAndroid Build Coastguard Worker       MCPhysReg Reg = CSI[i].getReg();
448*9880d681SAndroid Build Coastguard Worker       // Add the callee-saved register as live-in.
449*9880d681SAndroid Build Coastguard Worker       // It's killed at the spill.
450*9880d681SAndroid Build Coastguard Worker       if (!MBB->isLiveIn(Reg))
451*9880d681SAndroid Build Coastguard Worker         MBB->addLiveIn(Reg);
452*9880d681SAndroid Build Coastguard Worker     }
453*9880d681SAndroid Build Coastguard Worker   }
454*9880d681SAndroid Build Coastguard Worker }
455*9880d681SAndroid Build Coastguard Worker 
456*9880d681SAndroid Build Coastguard Worker /// insertCSRSpillsAndRestores - Insert spill and restore code for
457*9880d681SAndroid Build Coastguard Worker /// callee saved registers used in the function.
458*9880d681SAndroid Build Coastguard Worker ///
insertCSRSpillsAndRestores(MachineFunction & Fn,const MBBVector & SaveBlocks,const MBBVector & RestoreBlocks)459*9880d681SAndroid Build Coastguard Worker static void insertCSRSpillsAndRestores(MachineFunction &Fn,
460*9880d681SAndroid Build Coastguard Worker                                        const MBBVector &SaveBlocks,
461*9880d681SAndroid Build Coastguard Worker                                        const MBBVector &RestoreBlocks) {
462*9880d681SAndroid Build Coastguard Worker   // Get callee saved register information.
463*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = Fn.getFrameInfo();
464*9880d681SAndroid Build Coastguard Worker   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
465*9880d681SAndroid Build Coastguard Worker 
466*9880d681SAndroid Build Coastguard Worker   MFI->setCalleeSavedInfoValid(true);
467*9880d681SAndroid Build Coastguard Worker 
468*9880d681SAndroid Build Coastguard Worker   // Early exit if no callee saved registers are modified!
469*9880d681SAndroid Build Coastguard Worker   if (CSI.empty())
470*9880d681SAndroid Build Coastguard Worker     return;
471*9880d681SAndroid Build Coastguard Worker 
472*9880d681SAndroid Build Coastguard Worker   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
473*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
474*9880d681SAndroid Build Coastguard Worker   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
475*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock::iterator I;
476*9880d681SAndroid Build Coastguard Worker 
477*9880d681SAndroid Build Coastguard Worker   // Spill using target interface.
478*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock *SaveBlock : SaveBlocks) {
479*9880d681SAndroid Build Coastguard Worker     I = SaveBlock->begin();
480*9880d681SAndroid Build Coastguard Worker     if (!TFI->spillCalleeSavedRegisters(*SaveBlock, I, CSI, TRI)) {
481*9880d681SAndroid Build Coastguard Worker       for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
482*9880d681SAndroid Build Coastguard Worker         // Insert the spill to the stack frame.
483*9880d681SAndroid Build Coastguard Worker         unsigned Reg = CSI[i].getReg();
484*9880d681SAndroid Build Coastguard Worker         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
485*9880d681SAndroid Build Coastguard Worker         TII.storeRegToStackSlot(*SaveBlock, I, Reg, true, CSI[i].getFrameIdx(),
486*9880d681SAndroid Build Coastguard Worker                                 RC, TRI);
487*9880d681SAndroid Build Coastguard Worker       }
488*9880d681SAndroid Build Coastguard Worker     }
489*9880d681SAndroid Build Coastguard Worker     // Update the live-in information of all the blocks up to the save point.
490*9880d681SAndroid Build Coastguard Worker     updateLiveness(Fn);
491*9880d681SAndroid Build Coastguard Worker   }
492*9880d681SAndroid Build Coastguard Worker 
493*9880d681SAndroid Build Coastguard Worker   // Restore using target interface.
494*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock *MBB : RestoreBlocks) {
495*9880d681SAndroid Build Coastguard Worker     I = MBB->end();
496*9880d681SAndroid Build Coastguard Worker 
497*9880d681SAndroid Build Coastguard Worker     // Skip over all terminator instructions, which are part of the return
498*9880d681SAndroid Build Coastguard Worker     // sequence.
499*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock::iterator I2 = I;
500*9880d681SAndroid Build Coastguard Worker     while (I2 != MBB->begin() && (--I2)->isTerminator())
501*9880d681SAndroid Build Coastguard Worker       I = I2;
502*9880d681SAndroid Build Coastguard Worker 
503*9880d681SAndroid Build Coastguard Worker     bool AtStart = I == MBB->begin();
504*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock::iterator BeforeI = I;
505*9880d681SAndroid Build Coastguard Worker     if (!AtStart)
506*9880d681SAndroid Build Coastguard Worker       --BeforeI;
507*9880d681SAndroid Build Coastguard Worker 
508*9880d681SAndroid Build Coastguard Worker     // Restore all registers immediately before the return and any
509*9880d681SAndroid Build Coastguard Worker     // terminators that precede it.
510*9880d681SAndroid Build Coastguard Worker     if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) {
511*9880d681SAndroid Build Coastguard Worker       for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
512*9880d681SAndroid Build Coastguard Worker         unsigned Reg = CSI[i].getReg();
513*9880d681SAndroid Build Coastguard Worker         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
514*9880d681SAndroid Build Coastguard Worker         TII.loadRegFromStackSlot(*MBB, I, Reg, CSI[i].getFrameIdx(), RC, TRI);
515*9880d681SAndroid Build Coastguard Worker         assert(I != MBB->begin() &&
516*9880d681SAndroid Build Coastguard Worker                "loadRegFromStackSlot didn't insert any code!");
517*9880d681SAndroid Build Coastguard Worker         // Insert in reverse order.  loadRegFromStackSlot can insert
518*9880d681SAndroid Build Coastguard Worker         // multiple instructions.
519*9880d681SAndroid Build Coastguard Worker         if (AtStart)
520*9880d681SAndroid Build Coastguard Worker           I = MBB->begin();
521*9880d681SAndroid Build Coastguard Worker         else {
522*9880d681SAndroid Build Coastguard Worker           I = BeforeI;
523*9880d681SAndroid Build Coastguard Worker           ++I;
524*9880d681SAndroid Build Coastguard Worker         }
525*9880d681SAndroid Build Coastguard Worker       }
526*9880d681SAndroid Build Coastguard Worker     }
527*9880d681SAndroid Build Coastguard Worker   }
528*9880d681SAndroid Build Coastguard Worker }
529*9880d681SAndroid Build Coastguard Worker 
doSpillCalleeSavedRegs(MachineFunction & Fn,RegScavenger * RS,unsigned & MinCSFrameIndex,unsigned & MaxCSFrameIndex,const MBBVector & SaveBlocks,const MBBVector & RestoreBlocks)530*9880d681SAndroid Build Coastguard Worker static void doSpillCalleeSavedRegs(MachineFunction &Fn, RegScavenger *RS,
531*9880d681SAndroid Build Coastguard Worker                                    unsigned &MinCSFrameIndex,
532*9880d681SAndroid Build Coastguard Worker                                    unsigned &MaxCSFrameIndex,
533*9880d681SAndroid Build Coastguard Worker                                    const MBBVector &SaveBlocks,
534*9880d681SAndroid Build Coastguard Worker                                    const MBBVector &RestoreBlocks) {
535*9880d681SAndroid Build Coastguard Worker   const Function *F = Fn.getFunction();
536*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
537*9880d681SAndroid Build Coastguard Worker   MinCSFrameIndex = std::numeric_limits<unsigned>::max();
538*9880d681SAndroid Build Coastguard Worker   MaxCSFrameIndex = 0;
539*9880d681SAndroid Build Coastguard Worker 
540*9880d681SAndroid Build Coastguard Worker   // Determine which of the registers in the callee save list should be saved.
541*9880d681SAndroid Build Coastguard Worker   BitVector SavedRegs;
542*9880d681SAndroid Build Coastguard Worker   TFI->determineCalleeSaves(Fn, SavedRegs, RS);
543*9880d681SAndroid Build Coastguard Worker 
544*9880d681SAndroid Build Coastguard Worker   // Assign stack slots for any callee-saved registers that must be spilled.
545*9880d681SAndroid Build Coastguard Worker   assignCalleeSavedSpillSlots(Fn, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
546*9880d681SAndroid Build Coastguard Worker 
547*9880d681SAndroid Build Coastguard Worker   // Add the code to save and restore the callee saved registers.
548*9880d681SAndroid Build Coastguard Worker   if (!F->hasFnAttribute(Attribute::Naked))
549*9880d681SAndroid Build Coastguard Worker     insertCSRSpillsAndRestores(Fn, SaveBlocks, RestoreBlocks);
550*9880d681SAndroid Build Coastguard Worker }
551*9880d681SAndroid Build Coastguard Worker 
552*9880d681SAndroid Build Coastguard Worker /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
553*9880d681SAndroid Build Coastguard Worker static inline void
AdjustStackOffset(MachineFrameInfo * MFI,int FrameIdx,bool StackGrowsDown,int64_t & Offset,unsigned & MaxAlign,unsigned Skew)554*9880d681SAndroid Build Coastguard Worker AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx,
555*9880d681SAndroid Build Coastguard Worker                   bool StackGrowsDown, int64_t &Offset,
556*9880d681SAndroid Build Coastguard Worker                   unsigned &MaxAlign, unsigned Skew) {
557*9880d681SAndroid Build Coastguard Worker   // If the stack grows down, add the object size to find the lowest address.
558*9880d681SAndroid Build Coastguard Worker   if (StackGrowsDown)
559*9880d681SAndroid Build Coastguard Worker     Offset += MFI->getObjectSize(FrameIdx);
560*9880d681SAndroid Build Coastguard Worker 
561*9880d681SAndroid Build Coastguard Worker   unsigned Align = MFI->getObjectAlignment(FrameIdx);
562*9880d681SAndroid Build Coastguard Worker 
563*9880d681SAndroid Build Coastguard Worker   // If the alignment of this object is greater than that of the stack, then
564*9880d681SAndroid Build Coastguard Worker   // increase the stack alignment to match.
565*9880d681SAndroid Build Coastguard Worker   MaxAlign = std::max(MaxAlign, Align);
566*9880d681SAndroid Build Coastguard Worker 
567*9880d681SAndroid Build Coastguard Worker   // Adjust to alignment boundary.
568*9880d681SAndroid Build Coastguard Worker   Offset = alignTo(Offset, Align, Skew);
569*9880d681SAndroid Build Coastguard Worker 
570*9880d681SAndroid Build Coastguard Worker   if (StackGrowsDown) {
571*9880d681SAndroid Build Coastguard Worker     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
572*9880d681SAndroid Build Coastguard Worker     MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
573*9880d681SAndroid Build Coastguard Worker   } else {
574*9880d681SAndroid Build Coastguard Worker     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
575*9880d681SAndroid Build Coastguard Worker     MFI->setObjectOffset(FrameIdx, Offset);
576*9880d681SAndroid Build Coastguard Worker     Offset += MFI->getObjectSize(FrameIdx);
577*9880d681SAndroid Build Coastguard Worker   }
578*9880d681SAndroid Build Coastguard Worker }
579*9880d681SAndroid Build Coastguard Worker 
580*9880d681SAndroid Build Coastguard Worker /// Compute which bytes of fixed and callee-save stack area are unused and keep
581*9880d681SAndroid Build Coastguard Worker /// track of them in StackBytesFree.
582*9880d681SAndroid Build Coastguard Worker ///
583*9880d681SAndroid Build Coastguard Worker static inline void
computeFreeStackSlots(MachineFrameInfo * MFI,bool StackGrowsDown,unsigned MinCSFrameIndex,unsigned MaxCSFrameIndex,int64_t FixedCSEnd,BitVector & StackBytesFree)584*9880d681SAndroid Build Coastguard Worker computeFreeStackSlots(MachineFrameInfo *MFI, bool StackGrowsDown,
585*9880d681SAndroid Build Coastguard Worker                       unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
586*9880d681SAndroid Build Coastguard Worker                       int64_t FixedCSEnd, BitVector &StackBytesFree) {
587*9880d681SAndroid Build Coastguard Worker   // Avoid undefined int64_t -> int conversion below in extreme case.
588*9880d681SAndroid Build Coastguard Worker   if (FixedCSEnd > std::numeric_limits<int>::max())
589*9880d681SAndroid Build Coastguard Worker     return;
590*9880d681SAndroid Build Coastguard Worker 
591*9880d681SAndroid Build Coastguard Worker   StackBytesFree.resize(FixedCSEnd, true);
592*9880d681SAndroid Build Coastguard Worker 
593*9880d681SAndroid Build Coastguard Worker   SmallVector<int, 16> AllocatedFrameSlots;
594*9880d681SAndroid Build Coastguard Worker   // Add fixed objects.
595*9880d681SAndroid Build Coastguard Worker   for (int i = MFI->getObjectIndexBegin(); i != 0; ++i)
596*9880d681SAndroid Build Coastguard Worker     AllocatedFrameSlots.push_back(i);
597*9880d681SAndroid Build Coastguard Worker   // Add callee-save objects.
598*9880d681SAndroid Build Coastguard Worker   for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)
599*9880d681SAndroid Build Coastguard Worker     AllocatedFrameSlots.push_back(i);
600*9880d681SAndroid Build Coastguard Worker 
601*9880d681SAndroid Build Coastguard Worker   for (int i : AllocatedFrameSlots) {
602*9880d681SAndroid Build Coastguard Worker     // These are converted from int64_t, but they should always fit in int
603*9880d681SAndroid Build Coastguard Worker     // because of the FixedCSEnd check above.
604*9880d681SAndroid Build Coastguard Worker     int ObjOffset = MFI->getObjectOffset(i);
605*9880d681SAndroid Build Coastguard Worker     int ObjSize = MFI->getObjectSize(i);
606*9880d681SAndroid Build Coastguard Worker     int ObjStart, ObjEnd;
607*9880d681SAndroid Build Coastguard Worker     if (StackGrowsDown) {
608*9880d681SAndroid Build Coastguard Worker       // ObjOffset is negative when StackGrowsDown is true.
609*9880d681SAndroid Build Coastguard Worker       ObjStart = -ObjOffset - ObjSize;
610*9880d681SAndroid Build Coastguard Worker       ObjEnd = -ObjOffset;
611*9880d681SAndroid Build Coastguard Worker     } else {
612*9880d681SAndroid Build Coastguard Worker       ObjStart = ObjOffset;
613*9880d681SAndroid Build Coastguard Worker       ObjEnd = ObjOffset + ObjSize;
614*9880d681SAndroid Build Coastguard Worker     }
615*9880d681SAndroid Build Coastguard Worker     // Ignore fixed holes that are in the previous stack frame.
616*9880d681SAndroid Build Coastguard Worker     if (ObjEnd > 0)
617*9880d681SAndroid Build Coastguard Worker       StackBytesFree.reset(ObjStart, ObjEnd);
618*9880d681SAndroid Build Coastguard Worker   }
619*9880d681SAndroid Build Coastguard Worker }
620*9880d681SAndroid Build Coastguard Worker 
621*9880d681SAndroid Build Coastguard Worker /// Assign frame object to an unused portion of the stack in the fixed stack
622*9880d681SAndroid Build Coastguard Worker /// object range.  Return true if the allocation was successful.
623*9880d681SAndroid Build Coastguard Worker ///
scavengeStackSlot(MachineFrameInfo * MFI,int FrameIdx,bool StackGrowsDown,unsigned MaxAlign,BitVector & StackBytesFree)624*9880d681SAndroid Build Coastguard Worker static inline bool scavengeStackSlot(MachineFrameInfo *MFI, int FrameIdx,
625*9880d681SAndroid Build Coastguard Worker                                      bool StackGrowsDown, unsigned MaxAlign,
626*9880d681SAndroid Build Coastguard Worker                                      BitVector &StackBytesFree) {
627*9880d681SAndroid Build Coastguard Worker   if (MFI->isVariableSizedObjectIndex(FrameIdx))
628*9880d681SAndroid Build Coastguard Worker     return false;
629*9880d681SAndroid Build Coastguard Worker 
630*9880d681SAndroid Build Coastguard Worker   if (StackBytesFree.none()) {
631*9880d681SAndroid Build Coastguard Worker     // clear it to speed up later scavengeStackSlot calls to
632*9880d681SAndroid Build Coastguard Worker     // StackBytesFree.none()
633*9880d681SAndroid Build Coastguard Worker     StackBytesFree.clear();
634*9880d681SAndroid Build Coastguard Worker     return false;
635*9880d681SAndroid Build Coastguard Worker   }
636*9880d681SAndroid Build Coastguard Worker 
637*9880d681SAndroid Build Coastguard Worker   unsigned ObjAlign = MFI->getObjectAlignment(FrameIdx);
638*9880d681SAndroid Build Coastguard Worker   if (ObjAlign > MaxAlign)
639*9880d681SAndroid Build Coastguard Worker     return false;
640*9880d681SAndroid Build Coastguard Worker 
641*9880d681SAndroid Build Coastguard Worker   int64_t ObjSize = MFI->getObjectSize(FrameIdx);
642*9880d681SAndroid Build Coastguard Worker   int FreeStart;
643*9880d681SAndroid Build Coastguard Worker   for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
644*9880d681SAndroid Build Coastguard Worker        FreeStart = StackBytesFree.find_next(FreeStart)) {
645*9880d681SAndroid Build Coastguard Worker 
646*9880d681SAndroid Build Coastguard Worker     // Check that free space has suitable alignment.
647*9880d681SAndroid Build Coastguard Worker     unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;
648*9880d681SAndroid Build Coastguard Worker     if (alignTo(ObjStart, ObjAlign) != ObjStart)
649*9880d681SAndroid Build Coastguard Worker       continue;
650*9880d681SAndroid Build Coastguard Worker 
651*9880d681SAndroid Build Coastguard Worker     if (FreeStart + ObjSize > StackBytesFree.size())
652*9880d681SAndroid Build Coastguard Worker       return false;
653*9880d681SAndroid Build Coastguard Worker 
654*9880d681SAndroid Build Coastguard Worker     bool AllBytesFree = true;
655*9880d681SAndroid Build Coastguard Worker     for (unsigned Byte = 0; Byte < ObjSize; ++Byte)
656*9880d681SAndroid Build Coastguard Worker       if (!StackBytesFree.test(FreeStart + Byte)) {
657*9880d681SAndroid Build Coastguard Worker         AllBytesFree = false;
658*9880d681SAndroid Build Coastguard Worker         break;
659*9880d681SAndroid Build Coastguard Worker       }
660*9880d681SAndroid Build Coastguard Worker     if (AllBytesFree)
661*9880d681SAndroid Build Coastguard Worker       break;
662*9880d681SAndroid Build Coastguard Worker   }
663*9880d681SAndroid Build Coastguard Worker 
664*9880d681SAndroid Build Coastguard Worker   if (FreeStart == -1)
665*9880d681SAndroid Build Coastguard Worker     return false;
666*9880d681SAndroid Build Coastguard Worker 
667*9880d681SAndroid Build Coastguard Worker   if (StackGrowsDown) {
668*9880d681SAndroid Build Coastguard Worker     int ObjStart = -(FreeStart + ObjSize);
669*9880d681SAndroid Build Coastguard Worker     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << ObjStart
670*9880d681SAndroid Build Coastguard Worker                  << "]\n");
671*9880d681SAndroid Build Coastguard Worker     MFI->setObjectOffset(FrameIdx, ObjStart);
672*9880d681SAndroid Build Coastguard Worker   } else {
673*9880d681SAndroid Build Coastguard Worker     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << FreeStart
674*9880d681SAndroid Build Coastguard Worker                  << "]\n");
675*9880d681SAndroid Build Coastguard Worker     MFI->setObjectOffset(FrameIdx, FreeStart);
676*9880d681SAndroid Build Coastguard Worker   }
677*9880d681SAndroid Build Coastguard Worker 
678*9880d681SAndroid Build Coastguard Worker   StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
679*9880d681SAndroid Build Coastguard Worker   return true;
680*9880d681SAndroid Build Coastguard Worker }
681*9880d681SAndroid Build Coastguard Worker 
682*9880d681SAndroid Build Coastguard Worker /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
683*9880d681SAndroid Build Coastguard Worker /// those required to be close to the Stack Protector) to stack offsets.
684*9880d681SAndroid Build Coastguard Worker static void
AssignProtectedObjSet(const StackObjSet & UnassignedObjs,SmallSet<int,16> & ProtectedObjs,MachineFrameInfo * MFI,bool StackGrowsDown,int64_t & Offset,unsigned & MaxAlign,unsigned Skew)685*9880d681SAndroid Build Coastguard Worker AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
686*9880d681SAndroid Build Coastguard Worker                       SmallSet<int, 16> &ProtectedObjs,
687*9880d681SAndroid Build Coastguard Worker                       MachineFrameInfo *MFI, bool StackGrowsDown,
688*9880d681SAndroid Build Coastguard Worker                       int64_t &Offset, unsigned &MaxAlign, unsigned Skew) {
689*9880d681SAndroid Build Coastguard Worker 
690*9880d681SAndroid Build Coastguard Worker   for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
691*9880d681SAndroid Build Coastguard Worker         E = UnassignedObjs.end(); I != E; ++I) {
692*9880d681SAndroid Build Coastguard Worker     int i = *I;
693*9880d681SAndroid Build Coastguard Worker     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
694*9880d681SAndroid Build Coastguard Worker     ProtectedObjs.insert(i);
695*9880d681SAndroid Build Coastguard Worker   }
696*9880d681SAndroid Build Coastguard Worker }
697*9880d681SAndroid Build Coastguard Worker 
698*9880d681SAndroid Build Coastguard Worker /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
699*9880d681SAndroid Build Coastguard Worker /// abstract stack objects.
700*9880d681SAndroid Build Coastguard Worker ///
calculateFrameObjectOffsets(MachineFunction & Fn)701*9880d681SAndroid Build Coastguard Worker void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
702*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
703*9880d681SAndroid Build Coastguard Worker   StackProtector *SP = &getAnalysis<StackProtector>();
704*9880d681SAndroid Build Coastguard Worker 
705*9880d681SAndroid Build Coastguard Worker   bool StackGrowsDown =
706*9880d681SAndroid Build Coastguard Worker     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
707*9880d681SAndroid Build Coastguard Worker 
708*9880d681SAndroid Build Coastguard Worker   // Loop over all of the stack objects, assigning sequential addresses...
709*9880d681SAndroid Build Coastguard Worker   MachineFrameInfo *MFI = Fn.getFrameInfo();
710*9880d681SAndroid Build Coastguard Worker 
711*9880d681SAndroid Build Coastguard Worker   // Start at the beginning of the local area.
712*9880d681SAndroid Build Coastguard Worker   // The Offset is the distance from the stack top in the direction
713*9880d681SAndroid Build Coastguard Worker   // of stack growth -- so it's always nonnegative.
714*9880d681SAndroid Build Coastguard Worker   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
715*9880d681SAndroid Build Coastguard Worker   if (StackGrowsDown)
716*9880d681SAndroid Build Coastguard Worker     LocalAreaOffset = -LocalAreaOffset;
717*9880d681SAndroid Build Coastguard Worker   assert(LocalAreaOffset >= 0
718*9880d681SAndroid Build Coastguard Worker          && "Local area offset should be in direction of stack growth");
719*9880d681SAndroid Build Coastguard Worker   int64_t Offset = LocalAreaOffset;
720*9880d681SAndroid Build Coastguard Worker 
721*9880d681SAndroid Build Coastguard Worker   // Skew to be applied to alignment.
722*9880d681SAndroid Build Coastguard Worker   unsigned Skew = TFI.getStackAlignmentSkew(Fn);
723*9880d681SAndroid Build Coastguard Worker 
724*9880d681SAndroid Build Coastguard Worker   // If there are fixed sized objects that are preallocated in the local area,
725*9880d681SAndroid Build Coastguard Worker   // non-fixed objects can't be allocated right at the start of local area.
726*9880d681SAndroid Build Coastguard Worker   // Adjust 'Offset' to point to the end of last fixed sized preallocated
727*9880d681SAndroid Build Coastguard Worker   // object.
728*9880d681SAndroid Build Coastguard Worker   for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) {
729*9880d681SAndroid Build Coastguard Worker     int64_t FixedOff;
730*9880d681SAndroid Build Coastguard Worker     if (StackGrowsDown) {
731*9880d681SAndroid Build Coastguard Worker       // The maximum distance from the stack pointer is at lower address of
732*9880d681SAndroid Build Coastguard Worker       // the object -- which is given by offset. For down growing stack
733*9880d681SAndroid Build Coastguard Worker       // the offset is negative, so we negate the offset to get the distance.
734*9880d681SAndroid Build Coastguard Worker       FixedOff = -MFI->getObjectOffset(i);
735*9880d681SAndroid Build Coastguard Worker     } else {
736*9880d681SAndroid Build Coastguard Worker       // The maximum distance from the start pointer is at the upper
737*9880d681SAndroid Build Coastguard Worker       // address of the object.
738*9880d681SAndroid Build Coastguard Worker       FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i);
739*9880d681SAndroid Build Coastguard Worker     }
740*9880d681SAndroid Build Coastguard Worker     if (FixedOff > Offset) Offset = FixedOff;
741*9880d681SAndroid Build Coastguard Worker   }
742*9880d681SAndroid Build Coastguard Worker 
743*9880d681SAndroid Build Coastguard Worker   // First assign frame offsets to stack objects that are used to spill
744*9880d681SAndroid Build Coastguard Worker   // callee saved registers.
745*9880d681SAndroid Build Coastguard Worker   if (StackGrowsDown) {
746*9880d681SAndroid Build Coastguard Worker     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
747*9880d681SAndroid Build Coastguard Worker       // If the stack grows down, we need to add the size to find the lowest
748*9880d681SAndroid Build Coastguard Worker       // address of the object.
749*9880d681SAndroid Build Coastguard Worker       Offset += MFI->getObjectSize(i);
750*9880d681SAndroid Build Coastguard Worker 
751*9880d681SAndroid Build Coastguard Worker       unsigned Align = MFI->getObjectAlignment(i);
752*9880d681SAndroid Build Coastguard Worker       // Adjust to alignment boundary
753*9880d681SAndroid Build Coastguard Worker       Offset = alignTo(Offset, Align, Skew);
754*9880d681SAndroid Build Coastguard Worker 
755*9880d681SAndroid Build Coastguard Worker       DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
756*9880d681SAndroid Build Coastguard Worker       MFI->setObjectOffset(i, -Offset);        // Set the computed offset
757*9880d681SAndroid Build Coastguard Worker     }
758*9880d681SAndroid Build Coastguard Worker   } else if (MaxCSFrameIndex >= MinCSFrameIndex) {
759*9880d681SAndroid Build Coastguard Worker     // Be careful about underflow in comparisons agains MinCSFrameIndex.
760*9880d681SAndroid Build Coastguard Worker     for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; --i) {
761*9880d681SAndroid Build Coastguard Worker       unsigned Align = MFI->getObjectAlignment(i);
762*9880d681SAndroid Build Coastguard Worker       // Adjust to alignment boundary
763*9880d681SAndroid Build Coastguard Worker       Offset = alignTo(Offset, Align, Skew);
764*9880d681SAndroid Build Coastguard Worker 
765*9880d681SAndroid Build Coastguard Worker       DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
766*9880d681SAndroid Build Coastguard Worker       MFI->setObjectOffset(i, Offset);
767*9880d681SAndroid Build Coastguard Worker       Offset += MFI->getObjectSize(i);
768*9880d681SAndroid Build Coastguard Worker     }
769*9880d681SAndroid Build Coastguard Worker   }
770*9880d681SAndroid Build Coastguard Worker 
771*9880d681SAndroid Build Coastguard Worker   // FixedCSEnd is the stack offset to the end of the fixed and callee-save
772*9880d681SAndroid Build Coastguard Worker   // stack area.
773*9880d681SAndroid Build Coastguard Worker   int64_t FixedCSEnd = Offset;
774*9880d681SAndroid Build Coastguard Worker   unsigned MaxAlign = MFI->getMaxAlignment();
775*9880d681SAndroid Build Coastguard Worker 
776*9880d681SAndroid Build Coastguard Worker   // Make sure the special register scavenging spill slot is closest to the
777*9880d681SAndroid Build Coastguard Worker   // incoming stack pointer if a frame pointer is required and is closer
778*9880d681SAndroid Build Coastguard Worker   // to the incoming rather than the final stack pointer.
779*9880d681SAndroid Build Coastguard Worker   const TargetRegisterInfo *RegInfo = Fn.getSubtarget().getRegisterInfo();
780*9880d681SAndroid Build Coastguard Worker   bool EarlyScavengingSlots = (TFI.hasFP(Fn) &&
781*9880d681SAndroid Build Coastguard Worker                                TFI.isFPCloseToIncomingSP() &&
782*9880d681SAndroid Build Coastguard Worker                                RegInfo->useFPForScavengingIndex(Fn) &&
783*9880d681SAndroid Build Coastguard Worker                                !RegInfo->needsStackRealignment(Fn));
784*9880d681SAndroid Build Coastguard Worker   if (RS && EarlyScavengingSlots) {
785*9880d681SAndroid Build Coastguard Worker     SmallVector<int, 2> SFIs;
786*9880d681SAndroid Build Coastguard Worker     RS->getScavengingFrameIndices(SFIs);
787*9880d681SAndroid Build Coastguard Worker     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
788*9880d681SAndroid Build Coastguard Worker            IE = SFIs.end(); I != IE; ++I)
789*9880d681SAndroid Build Coastguard Worker       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
790*9880d681SAndroid Build Coastguard Worker   }
791*9880d681SAndroid Build Coastguard Worker 
792*9880d681SAndroid Build Coastguard Worker   // FIXME: Once this is working, then enable flag will change to a target
793*9880d681SAndroid Build Coastguard Worker   // check for whether the frame is large enough to want to use virtual
794*9880d681SAndroid Build Coastguard Worker   // frame index registers. Functions which don't want/need this optimization
795*9880d681SAndroid Build Coastguard Worker   // will continue to use the existing code path.
796*9880d681SAndroid Build Coastguard Worker   if (MFI->getUseLocalStackAllocationBlock()) {
797*9880d681SAndroid Build Coastguard Worker     unsigned Align = MFI->getLocalFrameMaxAlign();
798*9880d681SAndroid Build Coastguard Worker 
799*9880d681SAndroid Build Coastguard Worker     // Adjust to alignment boundary.
800*9880d681SAndroid Build Coastguard Worker     Offset = alignTo(Offset, Align, Skew);
801*9880d681SAndroid Build Coastguard Worker 
802*9880d681SAndroid Build Coastguard Worker     DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
803*9880d681SAndroid Build Coastguard Worker 
804*9880d681SAndroid Build Coastguard Worker     // Resolve offsets for objects in the local block.
805*9880d681SAndroid Build Coastguard Worker     for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) {
806*9880d681SAndroid Build Coastguard Worker       std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i);
807*9880d681SAndroid Build Coastguard Worker       int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
808*9880d681SAndroid Build Coastguard Worker       DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
809*9880d681SAndroid Build Coastguard Worker             FIOffset << "]\n");
810*9880d681SAndroid Build Coastguard Worker       MFI->setObjectOffset(Entry.first, FIOffset);
811*9880d681SAndroid Build Coastguard Worker     }
812*9880d681SAndroid Build Coastguard Worker     // Allocate the local block
813*9880d681SAndroid Build Coastguard Worker     Offset += MFI->getLocalFrameSize();
814*9880d681SAndroid Build Coastguard Worker 
815*9880d681SAndroid Build Coastguard Worker     MaxAlign = std::max(Align, MaxAlign);
816*9880d681SAndroid Build Coastguard Worker   }
817*9880d681SAndroid Build Coastguard Worker 
818*9880d681SAndroid Build Coastguard Worker   // Retrieve the Exception Handler registration node.
819*9880d681SAndroid Build Coastguard Worker   int EHRegNodeFrameIndex = INT_MAX;
820*9880d681SAndroid Build Coastguard Worker   if (const WinEHFuncInfo *FuncInfo = Fn.getWinEHFuncInfo())
821*9880d681SAndroid Build Coastguard Worker     EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
822*9880d681SAndroid Build Coastguard Worker 
823*9880d681SAndroid Build Coastguard Worker   // Make sure that the stack protector comes before the local variables on the
824*9880d681SAndroid Build Coastguard Worker   // stack.
825*9880d681SAndroid Build Coastguard Worker   SmallSet<int, 16> ProtectedObjs;
826*9880d681SAndroid Build Coastguard Worker   if (MFI->getStackProtectorIndex() >= 0) {
827*9880d681SAndroid Build Coastguard Worker     StackObjSet LargeArrayObjs;
828*9880d681SAndroid Build Coastguard Worker     StackObjSet SmallArrayObjs;
829*9880d681SAndroid Build Coastguard Worker     StackObjSet AddrOfObjs;
830*9880d681SAndroid Build Coastguard Worker 
831*9880d681SAndroid Build Coastguard Worker     AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown,
832*9880d681SAndroid Build Coastguard Worker                       Offset, MaxAlign, Skew);
833*9880d681SAndroid Build Coastguard Worker 
834*9880d681SAndroid Build Coastguard Worker     // Assign large stack objects first.
835*9880d681SAndroid Build Coastguard Worker     for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
836*9880d681SAndroid Build Coastguard Worker       if (MFI->isObjectPreAllocated(i) &&
837*9880d681SAndroid Build Coastguard Worker           MFI->getUseLocalStackAllocationBlock())
838*9880d681SAndroid Build Coastguard Worker         continue;
839*9880d681SAndroid Build Coastguard Worker       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
840*9880d681SAndroid Build Coastguard Worker         continue;
841*9880d681SAndroid Build Coastguard Worker       if (RS && RS->isScavengingFrameIndex((int)i))
842*9880d681SAndroid Build Coastguard Worker         continue;
843*9880d681SAndroid Build Coastguard Worker       if (MFI->isDeadObjectIndex(i))
844*9880d681SAndroid Build Coastguard Worker         continue;
845*9880d681SAndroid Build Coastguard Worker       if (MFI->getStackProtectorIndex() == (int)i ||
846*9880d681SAndroid Build Coastguard Worker           EHRegNodeFrameIndex == (int)i)
847*9880d681SAndroid Build Coastguard Worker         continue;
848*9880d681SAndroid Build Coastguard Worker 
849*9880d681SAndroid Build Coastguard Worker       switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) {
850*9880d681SAndroid Build Coastguard Worker       case StackProtector::SSPLK_None:
851*9880d681SAndroid Build Coastguard Worker         continue;
852*9880d681SAndroid Build Coastguard Worker       case StackProtector::SSPLK_SmallArray:
853*9880d681SAndroid Build Coastguard Worker         SmallArrayObjs.insert(i);
854*9880d681SAndroid Build Coastguard Worker         continue;
855*9880d681SAndroid Build Coastguard Worker       case StackProtector::SSPLK_AddrOf:
856*9880d681SAndroid Build Coastguard Worker         AddrOfObjs.insert(i);
857*9880d681SAndroid Build Coastguard Worker         continue;
858*9880d681SAndroid Build Coastguard Worker       case StackProtector::SSPLK_LargeArray:
859*9880d681SAndroid Build Coastguard Worker         LargeArrayObjs.insert(i);
860*9880d681SAndroid Build Coastguard Worker         continue;
861*9880d681SAndroid Build Coastguard Worker       }
862*9880d681SAndroid Build Coastguard Worker       llvm_unreachable("Unexpected SSPLayoutKind.");
863*9880d681SAndroid Build Coastguard Worker     }
864*9880d681SAndroid Build Coastguard Worker 
865*9880d681SAndroid Build Coastguard Worker     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
866*9880d681SAndroid Build Coastguard Worker                           Offset, MaxAlign, Skew);
867*9880d681SAndroid Build Coastguard Worker     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
868*9880d681SAndroid Build Coastguard Worker                           Offset, MaxAlign, Skew);
869*9880d681SAndroid Build Coastguard Worker     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
870*9880d681SAndroid Build Coastguard Worker                           Offset, MaxAlign, Skew);
871*9880d681SAndroid Build Coastguard Worker   }
872*9880d681SAndroid Build Coastguard Worker 
873*9880d681SAndroid Build Coastguard Worker   SmallVector<int, 8> ObjectsToAllocate;
874*9880d681SAndroid Build Coastguard Worker 
875*9880d681SAndroid Build Coastguard Worker   // Then prepare to assign frame offsets to stack objects that are not used to
876*9880d681SAndroid Build Coastguard Worker   // spill callee saved registers.
877*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
878*9880d681SAndroid Build Coastguard Worker     if (MFI->isObjectPreAllocated(i) &&
879*9880d681SAndroid Build Coastguard Worker         MFI->getUseLocalStackAllocationBlock())
880*9880d681SAndroid Build Coastguard Worker       continue;
881*9880d681SAndroid Build Coastguard Worker     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
882*9880d681SAndroid Build Coastguard Worker       continue;
883*9880d681SAndroid Build Coastguard Worker     if (RS && RS->isScavengingFrameIndex((int)i))
884*9880d681SAndroid Build Coastguard Worker       continue;
885*9880d681SAndroid Build Coastguard Worker     if (MFI->isDeadObjectIndex(i))
886*9880d681SAndroid Build Coastguard Worker       continue;
887*9880d681SAndroid Build Coastguard Worker     if (MFI->getStackProtectorIndex() == (int)i ||
888*9880d681SAndroid Build Coastguard Worker         EHRegNodeFrameIndex == (int)i)
889*9880d681SAndroid Build Coastguard Worker       continue;
890*9880d681SAndroid Build Coastguard Worker     if (ProtectedObjs.count(i))
891*9880d681SAndroid Build Coastguard Worker       continue;
892*9880d681SAndroid Build Coastguard Worker 
893*9880d681SAndroid Build Coastguard Worker     // Add the objects that we need to allocate to our working set.
894*9880d681SAndroid Build Coastguard Worker     ObjectsToAllocate.push_back(i);
895*9880d681SAndroid Build Coastguard Worker   }
896*9880d681SAndroid Build Coastguard Worker 
897*9880d681SAndroid Build Coastguard Worker   // Allocate the EH registration node first if one is present.
898*9880d681SAndroid Build Coastguard Worker   if (EHRegNodeFrameIndex != INT_MAX)
899*9880d681SAndroid Build Coastguard Worker     AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
900*9880d681SAndroid Build Coastguard Worker                       MaxAlign, Skew);
901*9880d681SAndroid Build Coastguard Worker 
902*9880d681SAndroid Build Coastguard Worker   // Give the targets a chance to order the objects the way they like it.
903*9880d681SAndroid Build Coastguard Worker   if (Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
904*9880d681SAndroid Build Coastguard Worker       Fn.getTarget().Options.StackSymbolOrdering)
905*9880d681SAndroid Build Coastguard Worker     TFI.orderFrameObjects(Fn, ObjectsToAllocate);
906*9880d681SAndroid Build Coastguard Worker 
907*9880d681SAndroid Build Coastguard Worker   // Keep track of which bytes in the fixed and callee-save range are used so we
908*9880d681SAndroid Build Coastguard Worker   // can use the holes when allocating later stack objects.  Only do this if
909*9880d681SAndroid Build Coastguard Worker   // stack protector isn't being used and the target requests it and we're
910*9880d681SAndroid Build Coastguard Worker   // optimizing.
911*9880d681SAndroid Build Coastguard Worker   BitVector StackBytesFree;
912*9880d681SAndroid Build Coastguard Worker   if (!ObjectsToAllocate.empty() &&
913*9880d681SAndroid Build Coastguard Worker       Fn.getTarget().getOptLevel() != CodeGenOpt::None &&
914*9880d681SAndroid Build Coastguard Worker       MFI->getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(Fn))
915*9880d681SAndroid Build Coastguard Worker     computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
916*9880d681SAndroid Build Coastguard Worker                           FixedCSEnd, StackBytesFree);
917*9880d681SAndroid Build Coastguard Worker 
918*9880d681SAndroid Build Coastguard Worker   // Now walk the objects and actually assign base offsets to them.
919*9880d681SAndroid Build Coastguard Worker   for (auto &Object : ObjectsToAllocate)
920*9880d681SAndroid Build Coastguard Worker     if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
921*9880d681SAndroid Build Coastguard Worker                            StackBytesFree))
922*9880d681SAndroid Build Coastguard Worker       AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
923*9880d681SAndroid Build Coastguard Worker 
924*9880d681SAndroid Build Coastguard Worker   // Make sure the special register scavenging spill slot is closest to the
925*9880d681SAndroid Build Coastguard Worker   // stack pointer.
926*9880d681SAndroid Build Coastguard Worker   if (RS && !EarlyScavengingSlots) {
927*9880d681SAndroid Build Coastguard Worker     SmallVector<int, 2> SFIs;
928*9880d681SAndroid Build Coastguard Worker     RS->getScavengingFrameIndices(SFIs);
929*9880d681SAndroid Build Coastguard Worker     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
930*9880d681SAndroid Build Coastguard Worker            IE = SFIs.end(); I != IE; ++I)
931*9880d681SAndroid Build Coastguard Worker       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
932*9880d681SAndroid Build Coastguard Worker   }
933*9880d681SAndroid Build Coastguard Worker 
934*9880d681SAndroid Build Coastguard Worker   if (!TFI.targetHandlesStackFrameRounding()) {
935*9880d681SAndroid Build Coastguard Worker     // If we have reserved argument space for call sites in the function
936*9880d681SAndroid Build Coastguard Worker     // immediately on entry to the current function, count it as part of the
937*9880d681SAndroid Build Coastguard Worker     // overall stack size.
938*9880d681SAndroid Build Coastguard Worker     if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn))
939*9880d681SAndroid Build Coastguard Worker       Offset += MFI->getMaxCallFrameSize();
940*9880d681SAndroid Build Coastguard Worker 
941*9880d681SAndroid Build Coastguard Worker     // Round up the size to a multiple of the alignment.  If the function has
942*9880d681SAndroid Build Coastguard Worker     // any calls or alloca's, align to the target's StackAlignment value to
943*9880d681SAndroid Build Coastguard Worker     // ensure that the callee's frame or the alloca data is suitably aligned;
944*9880d681SAndroid Build Coastguard Worker     // otherwise, for leaf functions, align to the TransientStackAlignment
945*9880d681SAndroid Build Coastguard Worker     // value.
946*9880d681SAndroid Build Coastguard Worker     unsigned StackAlign;
947*9880d681SAndroid Build Coastguard Worker     if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
948*9880d681SAndroid Build Coastguard Worker         (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
949*9880d681SAndroid Build Coastguard Worker       StackAlign = TFI.getStackAlignment();
950*9880d681SAndroid Build Coastguard Worker     else
951*9880d681SAndroid Build Coastguard Worker       StackAlign = TFI.getTransientStackAlignment();
952*9880d681SAndroid Build Coastguard Worker 
953*9880d681SAndroid Build Coastguard Worker     // If the frame pointer is eliminated, all frame offsets will be relative to
954*9880d681SAndroid Build Coastguard Worker     // SP not FP. Align to MaxAlign so this works.
955*9880d681SAndroid Build Coastguard Worker     StackAlign = std::max(StackAlign, MaxAlign);
956*9880d681SAndroid Build Coastguard Worker     Offset = alignTo(Offset, StackAlign, Skew);
957*9880d681SAndroid Build Coastguard Worker   }
958*9880d681SAndroid Build Coastguard Worker 
959*9880d681SAndroid Build Coastguard Worker   // Update frame info to pretend that this is part of the stack...
960*9880d681SAndroid Build Coastguard Worker   int64_t StackSize = Offset - LocalAreaOffset;
961*9880d681SAndroid Build Coastguard Worker   MFI->setStackSize(StackSize);
962*9880d681SAndroid Build Coastguard Worker   NumBytesStackSpace += StackSize;
963*9880d681SAndroid Build Coastguard Worker }
964*9880d681SAndroid Build Coastguard Worker 
965*9880d681SAndroid Build Coastguard Worker /// insertPrologEpilogCode - Scan the function for modified callee saved
966*9880d681SAndroid Build Coastguard Worker /// registers, insert spill code for these callee saved registers, then add
967*9880d681SAndroid Build Coastguard Worker /// prolog and epilog code to the function.
968*9880d681SAndroid Build Coastguard Worker ///
insertPrologEpilogCode(MachineFunction & Fn)969*9880d681SAndroid Build Coastguard Worker void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
970*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
971*9880d681SAndroid Build Coastguard Worker 
972*9880d681SAndroid Build Coastguard Worker   // Add prologue to the function...
973*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock *SaveBlock : SaveBlocks)
974*9880d681SAndroid Build Coastguard Worker     TFI.emitPrologue(Fn, *SaveBlock);
975*9880d681SAndroid Build Coastguard Worker 
976*9880d681SAndroid Build Coastguard Worker   // Add epilogue to restore the callee-save registers in each exiting block.
977*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
978*9880d681SAndroid Build Coastguard Worker     TFI.emitEpilogue(Fn, *RestoreBlock);
979*9880d681SAndroid Build Coastguard Worker 
980*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock *SaveBlock : SaveBlocks)
981*9880d681SAndroid Build Coastguard Worker     TFI.inlineStackProbe(Fn, *SaveBlock);
982*9880d681SAndroid Build Coastguard Worker 
983*9880d681SAndroid Build Coastguard Worker   // Emit additional code that is required to support segmented stacks, if
984*9880d681SAndroid Build Coastguard Worker   // we've been asked for it.  This, when linked with a runtime with support
985*9880d681SAndroid Build Coastguard Worker   // for segmented stacks (libgcc is one), will result in allocating stack
986*9880d681SAndroid Build Coastguard Worker   // space in small chunks instead of one large contiguous block.
987*9880d681SAndroid Build Coastguard Worker   if (Fn.shouldSplitStack()) {
988*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock *SaveBlock : SaveBlocks)
989*9880d681SAndroid Build Coastguard Worker       TFI.adjustForSegmentedStacks(Fn, *SaveBlock);
990*9880d681SAndroid Build Coastguard Worker   }
991*9880d681SAndroid Build Coastguard Worker 
992*9880d681SAndroid Build Coastguard Worker   // Emit additional code that is required to explicitly handle the stack in
993*9880d681SAndroid Build Coastguard Worker   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
994*9880d681SAndroid Build Coastguard Worker   // approach is rather similar to that of Segmented Stacks, but it uses a
995*9880d681SAndroid Build Coastguard Worker   // different conditional check and another BIF for allocating more stack
996*9880d681SAndroid Build Coastguard Worker   // space.
997*9880d681SAndroid Build Coastguard Worker   if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE)
998*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock *SaveBlock : SaveBlocks)
999*9880d681SAndroid Build Coastguard Worker       TFI.adjustForHiPEPrologue(Fn, *SaveBlock);
1000*9880d681SAndroid Build Coastguard Worker }
1001*9880d681SAndroid Build Coastguard Worker 
1002*9880d681SAndroid Build Coastguard Worker /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
1003*9880d681SAndroid Build Coastguard Worker /// register references and actual offsets.
1004*9880d681SAndroid Build Coastguard Worker ///
replaceFrameIndices(MachineFunction & Fn)1005*9880d681SAndroid Build Coastguard Worker void PEI::replaceFrameIndices(MachineFunction &Fn) {
1006*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
1007*9880d681SAndroid Build Coastguard Worker   if (!TFI.needsFrameIndexResolution(Fn)) return;
1008*9880d681SAndroid Build Coastguard Worker 
1009*9880d681SAndroid Build Coastguard Worker   // Store SPAdj at exit of a basic block.
1010*9880d681SAndroid Build Coastguard Worker   SmallVector<int, 8> SPState;
1011*9880d681SAndroid Build Coastguard Worker   SPState.resize(Fn.getNumBlockIDs());
1012*9880d681SAndroid Build Coastguard Worker   SmallPtrSet<MachineBasicBlock*, 8> Reachable;
1013*9880d681SAndroid Build Coastguard Worker 
1014*9880d681SAndroid Build Coastguard Worker   // Iterate over the reachable blocks in DFS order.
1015*9880d681SAndroid Build Coastguard Worker   for (auto DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
1016*9880d681SAndroid Build Coastguard Worker        DFI != DFE; ++DFI) {
1017*9880d681SAndroid Build Coastguard Worker     int SPAdj = 0;
1018*9880d681SAndroid Build Coastguard Worker     // Check the exit state of the DFS stack predecessor.
1019*9880d681SAndroid Build Coastguard Worker     if (DFI.getPathLength() >= 2) {
1020*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1021*9880d681SAndroid Build Coastguard Worker       assert(Reachable.count(StackPred) &&
1022*9880d681SAndroid Build Coastguard Worker              "DFS stack predecessor is already visited.\n");
1023*9880d681SAndroid Build Coastguard Worker       SPAdj = SPState[StackPred->getNumber()];
1024*9880d681SAndroid Build Coastguard Worker     }
1025*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock *BB = *DFI;
1026*9880d681SAndroid Build Coastguard Worker     replaceFrameIndices(BB, Fn, SPAdj);
1027*9880d681SAndroid Build Coastguard Worker     SPState[BB->getNumber()] = SPAdj;
1028*9880d681SAndroid Build Coastguard Worker   }
1029*9880d681SAndroid Build Coastguard Worker 
1030*9880d681SAndroid Build Coastguard Worker   // Handle the unreachable blocks.
1031*9880d681SAndroid Build Coastguard Worker   for (auto &BB : Fn) {
1032*9880d681SAndroid Build Coastguard Worker     if (Reachable.count(&BB))
1033*9880d681SAndroid Build Coastguard Worker       // Already handled in DFS traversal.
1034*9880d681SAndroid Build Coastguard Worker       continue;
1035*9880d681SAndroid Build Coastguard Worker     int SPAdj = 0;
1036*9880d681SAndroid Build Coastguard Worker     replaceFrameIndices(&BB, Fn, SPAdj);
1037*9880d681SAndroid Build Coastguard Worker   }
1038*9880d681SAndroid Build Coastguard Worker }
1039*9880d681SAndroid Build Coastguard Worker 
replaceFrameIndices(MachineBasicBlock * BB,MachineFunction & Fn,int & SPAdj)1040*9880d681SAndroid Build Coastguard Worker void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
1041*9880d681SAndroid Build Coastguard Worker                               int &SPAdj) {
1042*9880d681SAndroid Build Coastguard Worker   assert(Fn.getSubtarget().getRegisterInfo() &&
1043*9880d681SAndroid Build Coastguard Worker          "getRegisterInfo() must be implemented!");
1044*9880d681SAndroid Build Coastguard Worker   const TargetInstrInfo &TII = *Fn.getSubtarget().getInstrInfo();
1045*9880d681SAndroid Build Coastguard Worker   const TargetRegisterInfo &TRI = *Fn.getSubtarget().getRegisterInfo();
1046*9880d681SAndroid Build Coastguard Worker   const TargetFrameLowering *TFI = Fn.getSubtarget().getFrameLowering();
1047*9880d681SAndroid Build Coastguard Worker   unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
1048*9880d681SAndroid Build Coastguard Worker   unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
1049*9880d681SAndroid Build Coastguard Worker 
1050*9880d681SAndroid Build Coastguard Worker   if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(*BB);
1051*9880d681SAndroid Build Coastguard Worker 
1052*9880d681SAndroid Build Coastguard Worker   bool InsideCallSequence = false;
1053*9880d681SAndroid Build Coastguard Worker 
1054*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
1055*9880d681SAndroid Build Coastguard Worker 
1056*9880d681SAndroid Build Coastguard Worker     if (I->getOpcode() == FrameSetupOpcode ||
1057*9880d681SAndroid Build Coastguard Worker         I->getOpcode() == FrameDestroyOpcode) {
1058*9880d681SAndroid Build Coastguard Worker       InsideCallSequence = (I->getOpcode() == FrameSetupOpcode);
1059*9880d681SAndroid Build Coastguard Worker       SPAdj += TII.getSPAdjust(*I);
1060*9880d681SAndroid Build Coastguard Worker 
1061*9880d681SAndroid Build Coastguard Worker       I = TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
1062*9880d681SAndroid Build Coastguard Worker       continue;
1063*9880d681SAndroid Build Coastguard Worker     }
1064*9880d681SAndroid Build Coastguard Worker 
1065*9880d681SAndroid Build Coastguard Worker     MachineInstr &MI = *I;
1066*9880d681SAndroid Build Coastguard Worker     bool DoIncr = true;
1067*9880d681SAndroid Build Coastguard Worker     bool DidFinishLoop = true;
1068*9880d681SAndroid Build Coastguard Worker     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1069*9880d681SAndroid Build Coastguard Worker       if (!MI.getOperand(i).isFI())
1070*9880d681SAndroid Build Coastguard Worker         continue;
1071*9880d681SAndroid Build Coastguard Worker 
1072*9880d681SAndroid Build Coastguard Worker       // Frame indices in debug values are encoded in a target independent
1073*9880d681SAndroid Build Coastguard Worker       // way with simply the frame index and offset rather than any
1074*9880d681SAndroid Build Coastguard Worker       // target-specific addressing mode.
1075*9880d681SAndroid Build Coastguard Worker       if (MI.isDebugValue()) {
1076*9880d681SAndroid Build Coastguard Worker         assert(i == 0 && "Frame indices can only appear as the first "
1077*9880d681SAndroid Build Coastguard Worker                          "operand of a DBG_VALUE machine instruction");
1078*9880d681SAndroid Build Coastguard Worker         unsigned Reg;
1079*9880d681SAndroid Build Coastguard Worker         MachineOperand &Offset = MI.getOperand(1);
1080*9880d681SAndroid Build Coastguard Worker         Offset.setImm(
1081*9880d681SAndroid Build Coastguard Worker             Offset.getImm() +
1082*9880d681SAndroid Build Coastguard Worker             TFI->getFrameIndexReference(Fn, MI.getOperand(0).getIndex(), Reg));
1083*9880d681SAndroid Build Coastguard Worker         MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
1084*9880d681SAndroid Build Coastguard Worker         continue;
1085*9880d681SAndroid Build Coastguard Worker       }
1086*9880d681SAndroid Build Coastguard Worker 
1087*9880d681SAndroid Build Coastguard Worker       // TODO: This code should be commoned with the code for
1088*9880d681SAndroid Build Coastguard Worker       // PATCHPOINT. There's no good reason for the difference in
1089*9880d681SAndroid Build Coastguard Worker       // implementation other than historical accident.  The only
1090*9880d681SAndroid Build Coastguard Worker       // remaining difference is the unconditional use of the stack
1091*9880d681SAndroid Build Coastguard Worker       // pointer as the base register.
1092*9880d681SAndroid Build Coastguard Worker       if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
1093*9880d681SAndroid Build Coastguard Worker         assert((!MI.isDebugValue() || i == 0) &&
1094*9880d681SAndroid Build Coastguard Worker                "Frame indicies can only appear as the first operand of a "
1095*9880d681SAndroid Build Coastguard Worker                "DBG_VALUE machine instruction");
1096*9880d681SAndroid Build Coastguard Worker         unsigned Reg;
1097*9880d681SAndroid Build Coastguard Worker         MachineOperand &Offset = MI.getOperand(i + 1);
1098*9880d681SAndroid Build Coastguard Worker         int refOffset = TFI->getFrameIndexReferencePreferSP(
1099*9880d681SAndroid Build Coastguard Worker             Fn, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
1100*9880d681SAndroid Build Coastguard Worker         Offset.setImm(Offset.getImm() + refOffset);
1101*9880d681SAndroid Build Coastguard Worker         MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
1102*9880d681SAndroid Build Coastguard Worker         continue;
1103*9880d681SAndroid Build Coastguard Worker       }
1104*9880d681SAndroid Build Coastguard Worker 
1105*9880d681SAndroid Build Coastguard Worker       // Some instructions (e.g. inline asm instructions) can have
1106*9880d681SAndroid Build Coastguard Worker       // multiple frame indices and/or cause eliminateFrameIndex
1107*9880d681SAndroid Build Coastguard Worker       // to insert more than one instruction. We need the register
1108*9880d681SAndroid Build Coastguard Worker       // scavenger to go through all of these instructions so that
1109*9880d681SAndroid Build Coastguard Worker       // it can update its register information. We keep the
1110*9880d681SAndroid Build Coastguard Worker       // iterator at the point before insertion so that we can
1111*9880d681SAndroid Build Coastguard Worker       // revisit them in full.
1112*9880d681SAndroid Build Coastguard Worker       bool AtBeginning = (I == BB->begin());
1113*9880d681SAndroid Build Coastguard Worker       if (!AtBeginning) --I;
1114*9880d681SAndroid Build Coastguard Worker 
1115*9880d681SAndroid Build Coastguard Worker       // If this instruction has a FrameIndex operand, we need to
1116*9880d681SAndroid Build Coastguard Worker       // use that target machine register info object to eliminate
1117*9880d681SAndroid Build Coastguard Worker       // it.
1118*9880d681SAndroid Build Coastguard Worker       TRI.eliminateFrameIndex(MI, SPAdj, i,
1119*9880d681SAndroid Build Coastguard Worker                               FrameIndexVirtualScavenging ?  nullptr : RS);
1120*9880d681SAndroid Build Coastguard Worker 
1121*9880d681SAndroid Build Coastguard Worker       // Reset the iterator if we were at the beginning of the BB.
1122*9880d681SAndroid Build Coastguard Worker       if (AtBeginning) {
1123*9880d681SAndroid Build Coastguard Worker         I = BB->begin();
1124*9880d681SAndroid Build Coastguard Worker         DoIncr = false;
1125*9880d681SAndroid Build Coastguard Worker       }
1126*9880d681SAndroid Build Coastguard Worker 
1127*9880d681SAndroid Build Coastguard Worker       DidFinishLoop = false;
1128*9880d681SAndroid Build Coastguard Worker       break;
1129*9880d681SAndroid Build Coastguard Worker     }
1130*9880d681SAndroid Build Coastguard Worker 
1131*9880d681SAndroid Build Coastguard Worker     // If we are looking at a call sequence, we need to keep track of
1132*9880d681SAndroid Build Coastguard Worker     // the SP adjustment made by each instruction in the sequence.
1133*9880d681SAndroid Build Coastguard Worker     // This includes both the frame setup/destroy pseudos (handled above),
1134*9880d681SAndroid Build Coastguard Worker     // as well as other instructions that have side effects w.r.t the SP.
1135*9880d681SAndroid Build Coastguard Worker     // Note that this must come after eliminateFrameIndex, because
1136*9880d681SAndroid Build Coastguard Worker     // if I itself referred to a frame index, we shouldn't count its own
1137*9880d681SAndroid Build Coastguard Worker     // adjustment.
1138*9880d681SAndroid Build Coastguard Worker     if (DidFinishLoop && InsideCallSequence)
1139*9880d681SAndroid Build Coastguard Worker       SPAdj += TII.getSPAdjust(MI);
1140*9880d681SAndroid Build Coastguard Worker 
1141*9880d681SAndroid Build Coastguard Worker     if (DoIncr && I != BB->end()) ++I;
1142*9880d681SAndroid Build Coastguard Worker 
1143*9880d681SAndroid Build Coastguard Worker     // Update register states.
1144*9880d681SAndroid Build Coastguard Worker     if (RS && !FrameIndexVirtualScavenging && DidFinishLoop)
1145*9880d681SAndroid Build Coastguard Worker       RS->forward(MI);
1146*9880d681SAndroid Build Coastguard Worker   }
1147*9880d681SAndroid Build Coastguard Worker }
1148*9880d681SAndroid Build Coastguard Worker 
1149*9880d681SAndroid Build Coastguard Worker /// doScavengeFrameVirtualRegs - Replace all frame index virtual registers
1150*9880d681SAndroid Build Coastguard Worker /// with physical registers. Use the register scavenger to find an
1151*9880d681SAndroid Build Coastguard Worker /// appropriate register to use.
1152*9880d681SAndroid Build Coastguard Worker ///
1153*9880d681SAndroid Build Coastguard Worker /// FIXME: Iterating over the instruction stream is unnecessary. We can simply
1154*9880d681SAndroid Build Coastguard Worker /// iterate over the vreg use list, which at this point only contains machine
1155*9880d681SAndroid Build Coastguard Worker /// operands for which eliminateFrameIndex need a new scratch reg.
1156*9880d681SAndroid Build Coastguard Worker static void
doScavengeFrameVirtualRegs(MachineFunction & MF,RegScavenger * RS)1157*9880d681SAndroid Build Coastguard Worker doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS) {
1158*9880d681SAndroid Build Coastguard Worker   // Run through the instructions and find any virtual registers.
1159*9880d681SAndroid Build Coastguard Worker   MachineRegisterInfo &MRI = MF.getRegInfo();
1160*9880d681SAndroid Build Coastguard Worker   for (MachineBasicBlock &MBB : MF) {
1161*9880d681SAndroid Build Coastguard Worker     RS->enterBasicBlock(MBB);
1162*9880d681SAndroid Build Coastguard Worker 
1163*9880d681SAndroid Build Coastguard Worker     int SPAdj = 0;
1164*9880d681SAndroid Build Coastguard Worker 
1165*9880d681SAndroid Build Coastguard Worker     // The instruction stream may change in the loop, so check MBB.end()
1166*9880d681SAndroid Build Coastguard Worker     // directly.
1167*9880d681SAndroid Build Coastguard Worker     for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
1168*9880d681SAndroid Build Coastguard Worker       // We might end up here again with a NULL iterator if we scavenged a
1169*9880d681SAndroid Build Coastguard Worker       // register for which we inserted spill code for definition by what was
1170*9880d681SAndroid Build Coastguard Worker       // originally the first instruction in MBB.
1171*9880d681SAndroid Build Coastguard Worker       if (I == MachineBasicBlock::iterator(nullptr))
1172*9880d681SAndroid Build Coastguard Worker         I = MBB.begin();
1173*9880d681SAndroid Build Coastguard Worker 
1174*9880d681SAndroid Build Coastguard Worker       const MachineInstr &MI = *I;
1175*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock::iterator J = std::next(I);
1176*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock::iterator P =
1177*9880d681SAndroid Build Coastguard Worker                          I == MBB.begin() ? MachineBasicBlock::iterator(nullptr)
1178*9880d681SAndroid Build Coastguard Worker                                           : std::prev(I);
1179*9880d681SAndroid Build Coastguard Worker 
1180*9880d681SAndroid Build Coastguard Worker       // RS should process this instruction before we might scavenge at this
1181*9880d681SAndroid Build Coastguard Worker       // location. This is because we might be replacing a virtual register
1182*9880d681SAndroid Build Coastguard Worker       // defined by this instruction, and if so, registers killed by this
1183*9880d681SAndroid Build Coastguard Worker       // instruction are available, and defined registers are not.
1184*9880d681SAndroid Build Coastguard Worker       RS->forward(I);
1185*9880d681SAndroid Build Coastguard Worker 
1186*9880d681SAndroid Build Coastguard Worker       for (const MachineOperand &MO : MI.operands()) {
1187*9880d681SAndroid Build Coastguard Worker         if (!MO.isReg())
1188*9880d681SAndroid Build Coastguard Worker           continue;
1189*9880d681SAndroid Build Coastguard Worker         unsigned Reg = MO.getReg();
1190*9880d681SAndroid Build Coastguard Worker         if (!TargetRegisterInfo::isVirtualRegister(Reg))
1191*9880d681SAndroid Build Coastguard Worker           continue;
1192*9880d681SAndroid Build Coastguard Worker 
1193*9880d681SAndroid Build Coastguard Worker         // When we first encounter a new virtual register, it
1194*9880d681SAndroid Build Coastguard Worker         // must be a definition.
1195*9880d681SAndroid Build Coastguard Worker         assert(MO.isDef() && "frame index virtual missing def!");
1196*9880d681SAndroid Build Coastguard Worker         // Scavenge a new scratch register
1197*9880d681SAndroid Build Coastguard Worker         const TargetRegisterClass *RC = MRI.getRegClass(Reg);
1198*9880d681SAndroid Build Coastguard Worker         unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
1199*9880d681SAndroid Build Coastguard Worker 
1200*9880d681SAndroid Build Coastguard Worker         ++NumScavengedRegs;
1201*9880d681SAndroid Build Coastguard Worker 
1202*9880d681SAndroid Build Coastguard Worker         // Replace this reference to the virtual register with the
1203*9880d681SAndroid Build Coastguard Worker         // scratch register.
1204*9880d681SAndroid Build Coastguard Worker         assert(ScratchReg && "Missing scratch register!");
1205*9880d681SAndroid Build Coastguard Worker         MRI.replaceRegWith(Reg, ScratchReg);
1206*9880d681SAndroid Build Coastguard Worker 
1207*9880d681SAndroid Build Coastguard Worker         // Because this instruction was processed by the RS before this
1208*9880d681SAndroid Build Coastguard Worker         // register was allocated, make sure that the RS now records the
1209*9880d681SAndroid Build Coastguard Worker         // register as being used.
1210*9880d681SAndroid Build Coastguard Worker         RS->setRegUsed(ScratchReg);
1211*9880d681SAndroid Build Coastguard Worker       }
1212*9880d681SAndroid Build Coastguard Worker 
1213*9880d681SAndroid Build Coastguard Worker       // If the scavenger needed to use one of its spill slots, the
1214*9880d681SAndroid Build Coastguard Worker       // spill code will have been inserted in between I and J. This is a
1215*9880d681SAndroid Build Coastguard Worker       // problem because we need the spill code before I: Move I to just
1216*9880d681SAndroid Build Coastguard Worker       // prior to J.
1217*9880d681SAndroid Build Coastguard Worker       if (I != std::prev(J)) {
1218*9880d681SAndroid Build Coastguard Worker         MBB.splice(J, &MBB, I);
1219*9880d681SAndroid Build Coastguard Worker 
1220*9880d681SAndroid Build Coastguard Worker         // Before we move I, we need to prepare the RS to visit I again.
1221*9880d681SAndroid Build Coastguard Worker         // Specifically, RS will assert if it sees uses of registers that
1222*9880d681SAndroid Build Coastguard Worker         // it believes are undefined. Because we have already processed
1223*9880d681SAndroid Build Coastguard Worker         // register kills in I, when it visits I again, it will believe that
1224*9880d681SAndroid Build Coastguard Worker         // those registers are undefined. To avoid this situation, unprocess
1225*9880d681SAndroid Build Coastguard Worker         // the instruction I.
1226*9880d681SAndroid Build Coastguard Worker         assert(RS->getCurrentPosition() == I &&
1227*9880d681SAndroid Build Coastguard Worker           "The register scavenger has an unexpected position");
1228*9880d681SAndroid Build Coastguard Worker         I = P;
1229*9880d681SAndroid Build Coastguard Worker         RS->unprocess(P);
1230*9880d681SAndroid Build Coastguard Worker       } else
1231*9880d681SAndroid Build Coastguard Worker         ++I;
1232*9880d681SAndroid Build Coastguard Worker     }
1233*9880d681SAndroid Build Coastguard Worker   }
1234*9880d681SAndroid Build Coastguard Worker }
1235