lib/CodeGen/PrologEpilogInserter.cpp

   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"
  27 #include "llvm/Support/Compiler.h"
  28 #include <climits>
  29 using namespace llvm;
  30
  31 namespace {
  32   struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
  33     const char *getPassName() const {
  34       return "Prolog/Epilog Insertion & Frame Finalization";
  35     }
  36
  37     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
  38     /// frame indexes with appropriate references.
  39     ///
  40     bool runOnMachineFunction(MachineFunction &Fn) {
  41       // Get MachineModuleInfo so that we can track the construction of the
  42       // frame.
  43       if (MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>()) {
  44         Fn.getFrameInfo()->setMachineModuleInfo(MMI);
  45       }
  46
  47       // Allow the target machine to make some adjustments to the function
  48       // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
  49       Fn.getTarget().getRegisterInfo()
  50         ->processFunctionBeforeCalleeSavedScan(Fn);
  51
  52       // Scan the function for modified callee saved registers and insert spill
  53       // code for any callee saved registers that are modified.  Also calculate
  54       // the MaxCallFrameSize and HasCalls variables for the function's frame
  55       // information and eliminates call frame pseudo instructions.
  56       calculateCalleeSavedRegisters(Fn);
  57
  58       // Add the code to save and restore the callee saved registers
  59       saveCalleeSavedRegisters(Fn);
  60
  61       // Allow the target machine to make final modifications to the function
  62       // before the frame layout is finalized.
  63       Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn);
  64
  65       // Calculate actual frame offsets for all of the abstract stack objects...
  66       calculateFrameObjectOffsets(Fn);
  67
  68       // Add prolog and epilog code to the function.  This function is required
  69       // to align the stack frame as necessary for any stack variables or
  70       // called functions.  Because of this, calculateCalleeSavedRegisters
  71       // must be called before this function in order to set the HasCalls
  72       // and MaxCallFrameSize variables.
  73       insertPrologEpilogCode(Fn);
  74
  75       // Replace all MO_FrameIndex operands with physical register references
  76       // and actual offsets.
  77       //
  78       replaceFrameIndices(Fn);
  79
  80       return true;
  81     }
  82
  83   private:
  84     // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
  85     // stack frame indexes.
  86     unsigned MinCSFrameIndex, MaxCSFrameIndex;
  87
  88     void calculateCalleeSavedRegisters(MachineFunction &Fn);
  89     void saveCalleeSavedRegisters(MachineFunction &Fn);
  90     void calculateFrameObjectOffsets(MachineFunction &Fn);
  91     void replaceFrameIndices(MachineFunction &Fn);
  92     void insertPrologEpilogCode(MachineFunction &Fn);
  93   };
  94 }
  95
  96
  97 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
  98 /// prolog and epilog code, and eliminates abstract frame references.
  99 ///
 100 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
 101
 102
 103 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
 104 /// registers.  Also calculate the MaxCallFrameSize and HasCalls variables for
 105 /// the function's frame information and eliminates call frame pseudo
 106 /// instructions.
 107 ///
 108 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
 109   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 110   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
 111
 112   // Get the callee saved register list...
 113   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
 114
 115   // Get the function call frame set-up and tear-down instruction opcode
 116   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
 117   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
 118
 119   // These are used to keep track the callee-save area. Initialize them.
 120   MinCSFrameIndex = INT_MAX;
 121   MaxCSFrameIndex = 0;
 122
 123   // Early exit for targets which have no callee saved registers and no call
 124   // frame setup/destroy pseudo instructions.
 125   if ((CSRegs == 0 || CSRegs[0] == 0) &&
 126       FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
 127     return;
 128
 129   unsigned MaxCallFrameSize = 0;
 130   bool HasCalls = false;
 131
 132   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
 133     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); )
 134       if (I->getOpcode() == FrameSetupOpcode ||
 135           I->getOpcode() == FrameDestroyOpcode) {
 136         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
 137                " instructions should have a single immediate argument!");
 138         unsigned Size = I->getOperand(0).getImmedValue();
 139         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
 140         HasCalls = true;
 141         RegInfo->eliminateCallFramePseudoInstr(Fn, *BB, I++);
 142       } else {
 143         ++I;
 144       }
 145
 146   MachineFrameInfo *FFI = Fn.getFrameInfo();
 147   FFI->setHasCalls(HasCalls);
 148   FFI->setMaxCallFrameSize(MaxCallFrameSize);
 149
 150   // Now figure out which *callee saved* registers are modified by the current
 151   // function, thus needing to be saved and restored in the prolog/epilog.
 152   //
 153   const bool *PhysRegsUsed = Fn.getUsedPhysregs();
 154   const TargetRegisterClass* const *CSRegClasses =
 155     RegInfo->getCalleeSavedRegClasses();
 156   std::vector<CalleeSavedInfo> CSI;
 157   for (unsigned i = 0; CSRegs[i]; ++i) {
 158     unsigned Reg = CSRegs[i];
 159     if (PhysRegsUsed[Reg]) {
 160         // If the reg is modified, save it!
 161       CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
 162     } else {
 163       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 164            *AliasSet; ++AliasSet) {  // Check alias registers too.
 165         if (PhysRegsUsed[*AliasSet]) {
 166           CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
 167           break;
 168         }
 169       }
 170     }
 171   }
 172
 173   if (CSI.empty())
 174     return;   // Early exit if no callee saved registers are modified!
 175
 176   unsigned NumFixedSpillSlots;
 177   const std::pair<unsigned,int> *FixedSpillSlots =
 178     TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
 179
 180   // Now that we know which registers need to be saved and restored, allocate
 181   // stack slots for them.
 182   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 183     unsigned Reg = CSI[i].getReg();
 184     const TargetRegisterClass *RC = CSI[i].getRegClass();
 185
 186     // Check to see if this physreg must be spilled to a particular stack slot
 187     // on this target.
 188     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
 189     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
 190            FixedSlot->first != Reg)
 191       ++FixedSlot;
 192
 193     int FrameIdx;
 194     if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
 195       // Nope, just spill it anywhere convenient.
 196       unsigned Align = RC->getAlignment();
 197       unsigned StackAlign = TFI->getStackAlignment();
 198       // We may not be able to sastify the desired alignment specification of
 199       // the TargetRegisterClass if the stack alignment is smaller. Use the min.
 200       Align = std::min(Align, StackAlign);
 201       FrameIdx = FFI->CreateStackObject(RC->getSize(), Align);
 202       if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
 203       if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
 204     } else {
 205       // Spill it to the stack where we must.
 206       FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
 207     }
 208     CSI[i].setFrameIdx(FrameIdx);
 209   }
 210
 211   FFI->setCalleeSavedInfo(CSI);
 212 }
 213
 214 /// saveCalleeSavedRegisters -  Insert spill code for any callee saved registers
 215 /// that are modified in the function.
 216 ///
 217 void PEI::saveCalleeSavedRegisters(MachineFunction &Fn) {
 218   // Get callee saved register information.
 219   MachineFrameInfo *FFI = Fn.getFrameInfo();
 220   const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo();
 221
 222   // Early exit if no callee saved registers are modified!
 223   if (CSI.empty())
 224     return;
 225
 226   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 227
 228   // Now that we have a stack slot for each register to be saved, insert spill
 229   // code into the entry block.
 230   MachineBasicBlock *MBB = Fn.begin();
 231   MachineBasicBlock::iterator I = MBB->begin();
 232   if (!RegInfo->spillCalleeSavedRegisters(*MBB, I, CSI)) {
 233     for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 234       // Insert the spill to the stack frame.
 235       RegInfo->storeRegToStackSlot(*MBB, I, CSI[i].getReg(),
 236                                    CSI[i].getFrameIdx(),
 237                                    CSI[i].getRegClass());
 238     }
 239   }
 240
 241   // Add code to restore the callee-save registers in each exiting block.
 242   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 243   for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI)
 244     // If last instruction is a return instruction, add an epilogue.
 245     if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) {
 246       MBB = FI;
 247       I = MBB->end(); --I;
 248
 249       // Skip over all terminator instructions, which are part of the return
 250       // sequence.
 251       MachineBasicBlock::iterator I2 = I;
 252       while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
 253         I = I2;
 254
 255       bool AtStart = I == MBB->begin();
 256       MachineBasicBlock::iterator BeforeI = I;
 257       if (!AtStart)
 258         --BeforeI;
 259
 260       // Restore all registers immediately before the return and any terminators
 261       // that preceed it.
 262       if (!RegInfo->restoreCalleeSavedRegisters(*MBB, I, CSI)) {
 263         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 264           RegInfo->loadRegFromStackSlot(*MBB, I, CSI[i].getReg(),
 265                                         CSI[i].getFrameIdx(),
 266                                         CSI[i].getRegClass());
 267           assert(I != MBB->begin() &&
 268                  "loadRegFromStackSlot didn't insert any code!");
 269           // Insert in reverse order.  loadRegFromStackSlot can insert multiple
 270           // instructions.
 271           if (AtStart)
 272             I = MBB->begin();
 273           else {
 274             I = BeforeI;
 275             ++I;
 276           }
 277         }
 278       }
 279     }
 280 }
 281
 282
 283 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
 284 /// abstract stack objects.
 285 ///
 286 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
 287   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
 288
 289   bool StackGrowsDown =
 290     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
 291
 292   // Loop over all of the stack objects, assigning sequential addresses...
 293   MachineFrameInfo *FFI = Fn.getFrameInfo();
 294
 295   unsigned MaxAlign = 0;
 296
 297   // Start at the beginning of the local area.
 298   // The Offset is the distance from the stack top in the direction
 299   // of stack growth -- so it's always positive.
 300   int Offset = TFI.getOffsetOfLocalArea();
 301   if (StackGrowsDown)
 302     Offset = -Offset;
 303   assert(Offset >= 0
 304          && "Local area offset should be in direction of stack growth");
 305
 306   // If there are fixed sized objects that are preallocated in the local area,
 307   // non-fixed objects can't be allocated right at the start of local area.
 308   // We currently don't support filling in holes in between fixed sized objects,
 309   // so we adjust 'Offset' to point to the end of last fixed sized
 310   // preallocated object.
 311   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
 312     int FixedOff;
 313     if (StackGrowsDown) {
 314       // The maximum distance from the stack pointer is at lower address of
 315       // the object -- which is given by offset. For down growing stack
 316       // the offset is negative, so we negate the offset to get the distance.
 317       FixedOff = -FFI->getObjectOffset(i);
 318     } else {
 319       // The maximum distance from the start pointer is at the upper
 320       // address of the object.
 321       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
 322     }
 323     if (FixedOff > Offset) Offset = FixedOff;
 324   }
 325
 326   // First assign frame offsets to stack objects that are used to spill
 327   // callee saved registers.
 328   if (StackGrowsDown) {
 329     for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
 330       if (i < MinCSFrameIndex || i > MaxCSFrameIndex)
 331         continue;
 332
 333       // If stack grows down, we need to add size of find the lowest
 334       // address of the object.
 335       Offset += FFI->getObjectSize(i);
 336
 337       unsigned Align = FFI->getObjectAlignment(i);
 338       // If the alignment of this object is greater than that of the stack, then
 339       // increase the stack alignment to match.
 340       MaxAlign = std::max(MaxAlign, Align);
 341       // Adjust to alignment boundary
 342       Offset = (Offset+Align-1)/Align*Align;
 343
 344       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
 345     }
 346   } else {
 347     for (int i = FFI->getObjectIndexEnd()-1; i >= 0; --i) {
 348       if ((unsigned)i < MinCSFrameIndex || (unsigned)i > MaxCSFrameIndex)
 349         continue;
 350
 351       unsigned Align = FFI->getObjectAlignment(i);
 352       // If the alignment of this object is greater than that of the stack, then
 353       // increase the stack alignment to match.
 354       MaxAlign = std::max(MaxAlign, Align);
 355       // Adjust to alignment boundary
 356       Offset = (Offset+Align-1)/Align*Align;
 357
 358       FFI->setObjectOffset(i, Offset);
 359       Offset += FFI->getObjectSize(i);
 360     }
 361   }
 362
 363   // Then assign frame offsets to stack objects that are not used to spill
 364   // callee saved registers.
 365   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
 366     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
 367       continue;
 368
 369     // If stack grows down, we need to add size of find the lowest
 370     // address of the object.
 371     if (StackGrowsDown)
 372       Offset += FFI->getObjectSize(i);
 373
 374     unsigned Align = FFI->getObjectAlignment(i);
 375     // If the alignment of this object is greater than that of the stack, then
 376     // increase the stack alignment to match.
 377     MaxAlign = std::max(MaxAlign, Align);
 378     // Adjust to alignment boundary
 379     Offset = (Offset+Align-1)/Align*Align;
 380
 381     if (StackGrowsDown) {
 382       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
 383     } else {
 384       FFI->setObjectOffset(i, Offset);
 385       Offset += FFI->getObjectSize(i);
 386     }
 387   }
 388
 389   // Round up the size to a multiple of the alignment, but only if there are
 390   // calls or alloca's in the function.  This ensures that any calls to
 391   // subroutines have their stack frames suitable aligned.
 392   const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 393   if (!RegInfo->targetHandlesStackFrameRounding() &&
 394       (FFI->hasCalls() || FFI->hasVarSizedObjects())) {
 395     // When we have no frame pointer, we reserve argument space for call sites
 396     // in the function immediately on entry to the current function. This
 397     // eliminates the need for add/sub sp brackets around call sites.
 398     if (!RegInfo->hasFP(Fn))
 399       Offset += FFI->getMaxCallFrameSize();
 400
 401     unsigned AlignMask = TFI.getStackAlignment() - 1;
 402     Offset = (Offset + AlignMask) & ~AlignMask;
 403   }
 404
 405   // Update frame info to pretend that this is part of the stack...
 406   FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
 407
 408   // Remember the required stack alignment in case targets need it to perform
 409   // dynamic stack alignment.
 410   assert(FFI->getMaxAlignment() == MaxAlign &&
 411          "Stack alignment calculation broken!");
 412 }
 413
 414
 415 /// insertPrologEpilogCode - Scan the function for modified callee saved
 416 /// registers, insert spill code for these callee saved registers, then add
 417 /// prolog and epilog code to the function.
 418 ///
 419 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
 420   // Add prologue to the function...
 421   Fn.getTarget().getRegisterInfo()->emitPrologue(Fn);
 422
 423   // Add epilogue to restore the callee-save registers in each exiting block
 424   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 425   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 426     // If last instruction is a return instruction, add an epilogue
 427     if (!I->empty() && TII.isReturn(I->back().getOpcode()))
 428       Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I);
 429   }
 430 }
 431
 432
 433 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
 434 /// register references and actual offsets.
 435 ///
 436 void PEI::replaceFrameIndices(MachineFunction &Fn) {
 437   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
 438
 439   const TargetMachine &TM = Fn.getTarget();
 440   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
 441   const MRegisterInfo &MRI = *TM.getRegisterInfo();
 442
 443   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
 444     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 445       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 446         if (I->getOperand(i).isFrameIndex()) {
 447           // If this instruction has a FrameIndex operand, we need to use that
 448           // target machine register info object to eliminate it.
 449           MRI.eliminateFrameIndex(I);
 450           break;
 451         }
 452 }