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