PrologEpilogInserter.cpp revision 8fb040e584606f048b85d87363a52baf5ff9c1c7
1//===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass is responsible for finalizing the functions frame layout, saving 11// callee saved registers, and for emitting prolog & epilog code for the 12// function. 13// 14// This pass must be run after register allocation. After this pass is 15// executed, it is illegal to construct MO_FrameIndex operands. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/CodeGen/MachineFunctionPass.h" 21#include "llvm/CodeGen/MachineInstr.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/Target/MRegisterInfo.h" 25#include "llvm/Target/TargetFrameInfo.h" 26#include "llvm/Target/TargetInstrInfo.h" 27using namespace llvm; 28 29namespace { 30 struct PEI : public MachineFunctionPass { 31 const char *getPassName() const { 32 return "Prolog/Epilog Insertion & Frame Finalization"; 33 } 34 35 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract 36 /// frame indexes with appropriate references. 37 /// 38 bool runOnMachineFunction(MachineFunction &Fn) { 39 // Scan the function for modified caller saved registers and insert spill 40 // code for any caller saved registers that are modified. Also calculate 41 // the MaxCallFrameSize and HasCalls variables for the function's frame 42 // information and eliminates call frame pseudo instructions. 43 calculateCallerSavedRegisters(Fn); 44 45 // Add the code to save and restore the caller saved registers 46 saveCallerSavedRegisters(Fn); 47 48 // Allow the target machine to make final modifications to the function 49 // before the frame layout is finalized. 50 Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn); 51 52 // Calculate actual frame offsets for all of the abstract stack objects... 53 calculateFrameObjectOffsets(Fn); 54 55 // Add prolog and epilog code to the function. This function is required 56 // to align the stack frame as necessary for any stack variables or 57 // called functions. Because of this, calculateCallerSavedRegisters 58 // must be called before this function in order to set the HasCalls 59 // and MaxCallFrameSize variables. 60 insertPrologEpilogCode(Fn); 61 62 // Replace all MO_FrameIndex operands with physical register references 63 // and actual offsets. 64 // 65 replaceFrameIndices(Fn); 66 67 RegsToSave.clear(); 68 StackSlots.clear(); 69 return true; 70 } 71 72 private: 73 std::vector<std::pair<unsigned, const TargetRegisterClass*> > RegsToSave; 74 std::vector<int> StackSlots; 75 76 void calculateCallerSavedRegisters(MachineFunction &Fn); 77 void saveCallerSavedRegisters(MachineFunction &Fn); 78 void calculateFrameObjectOffsets(MachineFunction &Fn); 79 void replaceFrameIndices(MachineFunction &Fn); 80 void insertPrologEpilogCode(MachineFunction &Fn); 81 }; 82} 83 84 85/// createPrologEpilogCodeInserter - This function returns a pass that inserts 86/// prolog and epilog code, and eliminates abstract frame references. 87/// 88FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); } 89 90 91/// calculateCallerSavedRegisters - Scan the function for modified caller saved 92/// registers. Also calculate the MaxCallFrameSize and HasCalls variables for 93/// the function's frame information and eliminates call frame pseudo 94/// instructions. 95/// 96void PEI::calculateCallerSavedRegisters(MachineFunction &Fn) { 97 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 98 const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo(); 99 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 100 101 // Get the callee saved register list... 102 const unsigned *CSRegs = RegInfo->getCalleeSaveRegs(); 103 104 // Get the function call frame set-up and tear-down instruction opcode 105 int FrameSetupOpcode = RegInfo->getCallFrameSetupOpcode(); 106 int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode(); 107 108 // Early exit for targets which have no callee saved registers and no call 109 // frame setup/destroy pseudo instructions. 110 if ((CSRegs == 0 || CSRegs[0] == 0) && 111 FrameSetupOpcode == -1 && FrameDestroyOpcode == -1) 112 return; 113 114 unsigned MaxCallFrameSize = 0; 115 bool HasCalls = false; 116 117 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) 118 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) 119 if (I->getOpcode() == FrameSetupOpcode || 120 I->getOpcode() == FrameDestroyOpcode) { 121 assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo" 122 " instructions should have a single immediate argument!"); 123 unsigned Size = I->getOperand(0).getImmedValue(); 124 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size; 125 HasCalls = true; 126 RegInfo->eliminateCallFramePseudoInstr(Fn, *BB, I++); 127 } else { 128 ++I; 129 } 130 131 MachineFrameInfo *FFI = Fn.getFrameInfo(); 132 FFI->setHasCalls(HasCalls); 133 FFI->setMaxCallFrameSize(MaxCallFrameSize); 134 135 // Now figure out which *callee saved* registers are modified by the current 136 // function, thus needing to be saved and restored in the prolog/epilog. 137 // 138 const bool *PhysRegsUsed = Fn.getUsedPhysregs(); 139 const TargetRegisterClass* const *CSRegClasses = 140 RegInfo->getCalleeSaveRegClasses(); 141 for (unsigned i = 0; CSRegs[i]; ++i) { 142 unsigned Reg = CSRegs[i]; 143 if (PhysRegsUsed[Reg]) { 144 // If the reg is modified, save it! 145 RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i])); 146 } else { 147 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 148 *AliasSet; ++AliasSet) { // Check alias registers too. 149 if (PhysRegsUsed[*AliasSet]) { 150 RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i])); 151 break; 152 } 153 } 154 } 155 } 156 157 if (RegsToSave.empty()) 158 return; // Early exit if no caller saved registers are modified! 159 160 unsigned NumFixedSpillSlots; 161 const std::pair<unsigned,int> *FixedSpillSlots = 162 TFI->getCalleeSaveSpillSlots(NumFixedSpillSlots); 163 164 // Now that we know which registers need to be saved and restored, allocate 165 // stack slots for them. 166 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 167 unsigned Reg = RegsToSave[i].first; 168 const TargetRegisterClass *RC = RegsToSave[i].second; 169 170 // Check to see if this physreg must be spilled to a particular stack slot 171 // on this target. 172 const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots; 173 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots && 174 FixedSlot->first != Reg) 175 ++FixedSlot; 176 177 int FrameIdx; 178 if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) { 179 // Nope, just spill it anywhere convenient. 180 FrameIdx = FFI->CreateStackObject(RC->getSize(), RC->getAlignment()); 181 } else { 182 // Spill it to the stack where we must. 183 FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second); 184 } 185 StackSlots.push_back(FrameIdx); 186 } 187} 188 189/// saveCallerSavedRegisters - Insert spill code for any caller saved registers 190/// that are modified in the function. 191/// 192void PEI::saveCallerSavedRegisters(MachineFunction &Fn) { 193 // Early exit if no caller saved registers are modified! 194 if (RegsToSave.empty()) 195 return; 196 197 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 198 199 // Now that we have a stack slot for each register to be saved, insert spill 200 // code into the entry block. 201 MachineBasicBlock *MBB = Fn.begin(); 202 MachineBasicBlock::iterator I = MBB->begin(); 203 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 204 // Insert the spill to the stack frame. 205 RegInfo->storeRegToStackSlot(*MBB, I, RegsToSave[i].first, StackSlots[i], 206 RegsToSave[i].second); 207 } 208 209 // Add code to restore the callee-save registers in each exiting block. 210 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 211 for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI) 212 // If last instruction is a return instruction, add an epilogue. 213 if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) { 214 MBB = FI; 215 I = MBB->end(); --I; 216 217 // Skip over all terminator instructions, which are part of the return 218 // sequence. 219 MachineBasicBlock::iterator I2 = I; 220 while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode())) 221 I = I2; 222 223 bool AtStart = I == MBB->begin(); 224 MachineBasicBlock::iterator BeforeI = I; 225 if (!AtStart) 226 --BeforeI; 227 228 // Restore all registers immediately before the return and any terminators 229 // that preceed it. 230 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 231 RegInfo->loadRegFromStackSlot(*MBB, I, RegsToSave[i].first, 232 StackSlots[i], RegsToSave[i].second); 233 assert(I != MBB->begin() && 234 "loadRegFromStackSlot didn't insert any code!"); 235 // Insert in reverse order. loadRegFromStackSlot can insert multiple 236 // instructions. 237 if (AtStart) 238 I = MBB->begin(); 239 else { 240 I = BeforeI; 241 ++I; 242 } 243 } 244 } 245} 246 247 248/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 249/// abstract stack objects. 250/// 251void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 252 const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo(); 253 254 bool StackGrowsDown = 255 TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown; 256 257 // Loop over all of the stack objects, assigning sequential addresses... 258 MachineFrameInfo *FFI = Fn.getFrameInfo(); 259 260 unsigned StackAlignment = TFI.getStackAlignment(); 261 262 // Start at the beginning of the local area. 263 // The Offset is the distance from the stack top in the direction 264 // of stack growth -- so it's always positive. 265 int Offset = TFI.getOffsetOfLocalArea(); 266 if (StackGrowsDown) 267 Offset = -Offset; 268 assert(Offset >= 0 269 && "Local area offset should be in direction of stack growth"); 270 271 // If there are fixed sized objects that are preallocated in the local area, 272 // non-fixed objects can't be allocated right at the start of local area. 273 // We currently don't support filling in holes in between fixed sized objects, 274 // so we adjust 'Offset' to point to the end of last fixed sized 275 // preallocated object. 276 for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) { 277 int FixedOff; 278 if (StackGrowsDown) { 279 // The maximum distance from the stack pointer is at lower address of 280 // the object -- which is given by offset. For down growing stack 281 // the offset is negative, so we negate the offset to get the distance. 282 FixedOff = -FFI->getObjectOffset(i); 283 } else { 284 // The maximum distance from the start pointer is at the upper 285 // address of the object. 286 FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i); 287 } 288 if (FixedOff > Offset) Offset = FixedOff; 289 } 290 291 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) { 292 // If stack grows down, we need to add size of find the lowest 293 // address of the object. 294 if (StackGrowsDown) 295 Offset += FFI->getObjectSize(i); 296 297 unsigned Align = FFI->getObjectAlignment(i); 298 assert(Align <= StackAlignment && "Cannot align stack object to higher " 299 "alignment boundary than the stack itself!"); 300 Offset = (Offset+Align-1)/Align*Align; // Adjust to Alignment boundary... 301 302 if (StackGrowsDown) { 303 FFI->setObjectOffset(i, -Offset); // Set the computed offset 304 } else { 305 FFI->setObjectOffset(i, Offset); 306 Offset += FFI->getObjectSize(i); 307 } 308 } 309 310 // Align the final stack pointer offset, but only if there are calls in the 311 // function. This ensures that any calls to subroutines have their stack 312 // frames suitable aligned. 313 if (FFI->hasCalls()) 314 Offset = (Offset+StackAlignment-1)/StackAlignment*StackAlignment; 315 316 // Set the final value of the stack pointer... 317 FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea()); 318} 319 320 321/// insertPrologEpilogCode - Scan the function for modified caller saved 322/// registers, insert spill code for these caller saved registers, then add 323/// prolog and epilog code to the function. 324/// 325void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 326 // Add prologue to the function... 327 Fn.getTarget().getRegisterInfo()->emitPrologue(Fn); 328 329 // Add epilogue to restore the callee-save registers in each exiting block 330 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 331 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 332 // If last instruction is a return instruction, add an epilogue 333 if (!I->empty() && TII.isReturn(I->back().getOpcode())) 334 Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I); 335 } 336} 337 338 339/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 340/// register references and actual offsets. 341/// 342void PEI::replaceFrameIndices(MachineFunction &Fn) { 343 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 344 345 const TargetMachine &TM = Fn.getTarget(); 346 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 347 const MRegisterInfo &MRI = *TM.getRegisterInfo(); 348 349 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) 350 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) 351 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 352 if (I->getOperand(i).isFrameIndex()) { 353 // If this instruction has a FrameIndex operand, we need to use that 354 // target machine register info object to eliminate it. 355 MRI.eliminateFrameIndex(I); 356 break; 357 } 358} 359