lib/CodeGen/PrologEpilogInserter.cpp

   1 //===-- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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 // This pass provides an optional shrink wrapping variant of prolog/epilog
  18 // insertion, enabled via --shrink-wrap. See ShrinkWrapping.cpp.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #define DEBUG_TYPE "pei"
  23 #include "PrologEpilogInserter.h"
  24 #include "llvm/CodeGen/MachineDominators.h"
  25 #include "llvm/CodeGen/MachineLoopInfo.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineFrameInfo.h"
  28 #include "llvm/CodeGen/MachineRegisterInfo.h"
  29 #include "llvm/CodeGen/RegisterScavenging.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetFrameInfo.h"
  33 #include "llvm/Target/TargetInstrInfo.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Compiler.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/ADT/IndexedMap.h"
  38 #include "llvm/ADT/SmallSet.h"
  39 #include "llvm/ADT/Statistic.h"
  40 #include "llvm/ADT/STLExtras.h"
  41 #include <climits>
  42
  43 using namespace llvm;
  44
  45 char PEI::ID = 0;
  46
  47 INITIALIZE_PASS_BEGIN(PEI, "prologepilog",
  48                 "Prologue/Epilogue Insertion", false, false)
  49 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  50 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  51 INITIALIZE_PASS_END(PEI, "prologepilog",
  52                 "Prologue/Epilogue Insertion", false, false)
  53
  54 STATISTIC(NumVirtualFrameRegs, "Number of virtual frame regs encountered");
  55 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
  56
  57 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
  58 /// prolog and epilog code, and eliminates abstract frame references.
  59 ///
  60 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
  61
  62 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
  63 /// frame indexes with appropriate references.
  64 ///
  65 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
  66   const Function* F = Fn.getFunction();
  67   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
  68   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
  69
  70   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
  71   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
  72
  73   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
  74   // function's frame information. Also eliminates call frame pseudo
  75   // instructions.
  76   calculateCallsInformation(Fn);
  77
  78   // Allow the target machine to make some adjustments to the function
  79   // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
  80   TFI->processFunctionBeforeCalleeSavedScan(Fn, RS);
  81
  82   // Scan the function for modified callee saved registers and insert spill code
  83   // for any callee saved registers that are modified.
  84   calculateCalleeSavedRegisters(Fn);
  85
  86   // Determine placement of CSR spill/restore code:
  87   //  - With shrink wrapping, place spills and restores to tightly
  88   //    enclose regions in the Machine CFG of the function where
  89   //    they are used.
  90   //  - Without shink wrapping (default), place all spills in the
  91   //    entry block, all restores in return blocks.
  92   placeCSRSpillsAndRestores(Fn);
  93
  94   // Add the code to save and restore the callee saved registers
  95   if (!F->hasFnAttr(Attribute::Naked))
  96     insertCSRSpillsAndRestores(Fn);
  97
  98   // Allow the target machine to make final modifications to the function
  99   // before the frame layout is finalized.
 100   TFI->processFunctionBeforeFrameFinalized(Fn);
 101
 102   // Calculate actual frame offsets for all abstract stack objects...
 103   calculateFrameObjectOffsets(Fn);
 104
 105   // Add prolog and epilog code to the function.  This function is required
 106   // to align the stack frame as necessary for any stack variables or
 107   // called functions.  Because of this, calculateCalleeSavedRegisters()
 108   // must be called before this function in order to set the AdjustsStack
 109   // and MaxCallFrameSize variables.
 110   if (!F->hasFnAttr(Attribute::Naked))
 111     insertPrologEpilogCode(Fn);
 112
 113   // Replace all MO_FrameIndex operands with physical register references
 114   // and actual offsets.
 115   //
 116   replaceFrameIndices(Fn);
 117
 118   // If register scavenging is needed, as we've enabled doing it as a
 119   // post-pass, scavenge the virtual registers that frame index elimiation
 120   // inserted.
 121   if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
 122     scavengeFrameVirtualRegs(Fn);
 123
 124   delete RS;
 125   clearAllSets();
 126   return true;
 127 }
 128
 129 #if 0
 130 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
 131   AU.setPreservesCFG();
 132   if (ShrinkWrapping || ShrinkWrapFunc != "") {
 133     AU.addRequired<MachineLoopInfo>();
 134     AU.addRequired<MachineDominatorTree>();
 135   }
 136   AU.addPreserved<MachineLoopInfo>();
 137   AU.addPreserved<MachineDominatorTree>();
 138   MachineFunctionPass::getAnalysisUsage(AU);
 139 }
 140 #endif
 141
 142 /// calculateCallsInformation - Calculate the MaxCallFrameSize and AdjustsStack
 143 /// variables for the function's frame information and eliminate call frame
 144 /// pseudo instructions.
 145 void PEI::calculateCallsInformation(MachineFunction &Fn) {
 146   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 147   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
 148   MachineFrameInfo *MFI = Fn.getFrameInfo();
 149
 150   unsigned MaxCallFrameSize = 0;
 151   bool AdjustsStack = MFI->adjustsStack();
 152
 153   // Get the function call frame set-up and tear-down instruction opcode
 154   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
 155   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
 156
 157   // Early exit for targets which have no call frame setup/destroy pseudo
 158   // instructions.
 159   if (FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
 160     return;
 161
 162   std::vector<MachineBasicBlock::iterator> FrameSDOps;
 163   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
 164     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 165       if (I->getOpcode() == FrameSetupOpcode ||
 166           I->getOpcode() == FrameDestroyOpcode) {
 167         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
 168                " instructions should have a single immediate argument!");
 169         unsigned Size = I->getOperand(0).getImm();
 170         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
 171         AdjustsStack = true;
 172         FrameSDOps.push_back(I);
 173       } else if (I->isInlineAsm()) {
 174         // Some inline asm's need a stack frame, as indicated by operand 1.
 175         if (I->getOperand(1).getImm())
 176           AdjustsStack = true;
 177       }
 178
 179   MFI->setAdjustsStack(AdjustsStack);
 180   MFI->setMaxCallFrameSize(MaxCallFrameSize);
 181
 182   for (std::vector<MachineBasicBlock::iterator>::iterator
 183          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
 184     MachineBasicBlock::iterator I = *i;
 185
 186     // If call frames are not being included as part of the stack frame, and
 187     // the target doesn't indicate otherwise, remove the call frame pseudos
 188     // here. The sub/add sp instruction pairs are still inserted, but we don't
 189     // need to track the SP adjustment for frame index elimination.
 190     if (TFI->canSimplifyCallFramePseudos(Fn))
 191       RegInfo->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
 192   }
 193 }
 194
 195
 196 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
 197 /// registers.
 198 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
 199   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 200   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
 201   MachineFrameInfo *MFI = Fn.getFrameInfo();
 202
 203   // Get the callee saved register list...
 204   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(&Fn);
 205
 206   // These are used to keep track the callee-save area. Initialize them.
 207   MinCSFrameIndex = INT_MAX;
 208   MaxCSFrameIndex = 0;
 209
 210   // Early exit for targets which have no callee saved registers.
 211   if (CSRegs == 0 || CSRegs[0] == 0)
 212     return;
 213
 214   // In Naked functions we aren't going to save any registers.
 215   if (Fn.getFunction()->hasFnAttr(Attribute::Naked))
 216     return;
 217
 218   std::vector<CalleeSavedInfo> CSI;
 219   for (unsigned i = 0; CSRegs[i]; ++i) {
 220     unsigned Reg = CSRegs[i];
 221     if (Fn.getRegInfo().isPhysRegUsed(Reg)) {
 222       // If the reg is modified, save it!
 223       CSI.push_back(CalleeSavedInfo(Reg));
 224     } else {
 225       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 226            *AliasSet; ++AliasSet) {  // Check alias registers too.
 227         if (Fn.getRegInfo().isPhysRegUsed(*AliasSet)) {
 228           CSI.push_back(CalleeSavedInfo(Reg));
 229           break;
 230         }
 231       }
 232     }
 233   }
 234
 235   if (CSI.empty())
 236     return;   // Early exit if no callee saved registers are modified!
 237
 238   unsigned NumFixedSpillSlots;
 239   const TargetFrameInfo::SpillSlot *FixedSpillSlots =
 240     TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
 241
 242   // Now that we know which registers need to be saved and restored, allocate
 243   // stack slots for them.
 244   for (std::vector<CalleeSavedInfo>::iterator
 245          I = CSI.begin(), E = CSI.end(); I != E; ++I) {
 246     unsigned Reg = I->getReg();
 247     const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
 248
 249     int FrameIdx;
 250     if (RegInfo->hasReservedSpillSlot(Fn, Reg, FrameIdx)) {
 251       I->setFrameIdx(FrameIdx);
 252       continue;
 253     }
 254
 255     // Check to see if this physreg must be spilled to a particular stack slot
 256     // on this target.
 257     const TargetFrameInfo::SpillSlot *FixedSlot = FixedSpillSlots;
 258     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
 259            FixedSlot->Reg != Reg)
 260       ++FixedSlot;
 261
 262     if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
 263       // Nope, just spill it anywhere convenient.
 264       unsigned Align = RC->getAlignment();
 265       unsigned StackAlign = TFI->getStackAlignment();
 266
 267       // We may not be able to satisfy the desired alignment specification of
 268       // the TargetRegisterClass if the stack alignment is smaller. Use the
 269       // min.
 270       Align = std::min(Align, StackAlign);
 271       FrameIdx = MFI->CreateStackObject(RC->getSize(), Align, true);
 272       if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
 273       if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
 274     } else {
 275       // Spill it to the stack where we must.
 276       FrameIdx = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset, true);
 277     }
 278
 279     I->setFrameIdx(FrameIdx);
 280   }
 281
 282   MFI->setCalleeSavedInfo(CSI);
 283 }
 284
 285 /// insertCSRSpillsAndRestores - Insert spill and restore code for
 286 /// callee saved registers used in the function, handling shrink wrapping.
 287 ///
 288 void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) {
 289   // Get callee saved register information.
 290   MachineFrameInfo *MFI = Fn.getFrameInfo();
 291   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 292
 293   MFI->setCalleeSavedInfoValid(true);
 294
 295   // Early exit if no callee saved registers are modified!
 296   if (CSI.empty())
 297     return;
 298
 299   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 300   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
 301   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
 302   MachineBasicBlock::iterator I;
 303
 304   if (! ShrinkWrapThisFunction) {
 305     // Spill using target interface.
 306     I = EntryBlock->begin();
 307     if (!TFI->spillCalleeSavedRegisters(*EntryBlock, I, CSI, TRI)) {
 308       for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 309         // Add the callee-saved register as live-in.
 310         // It's killed at the spill.
 311         EntryBlock->addLiveIn(CSI[i].getReg());
 312
 313         // Insert the spill to the stack frame.
 314         unsigned Reg = CSI[i].getReg();
 315         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 316         TII.storeRegToStackSlot(*EntryBlock, I, Reg, true,
 317                                 CSI[i].getFrameIdx(), RC, TRI);
 318       }
 319     }
 320
 321     // Restore using target interface.
 322     for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) {
 323       MachineBasicBlock* MBB = ReturnBlocks[ri];
 324       I = MBB->end(); --I;
 325
 326       // Skip over all terminator instructions, which are part of the return
 327       // sequence.
 328       MachineBasicBlock::iterator I2 = I;
 329       while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
 330         I = I2;
 331
 332       bool AtStart = I == MBB->begin();
 333       MachineBasicBlock::iterator BeforeI = I;
 334       if (!AtStart)
 335         --BeforeI;
 336
 337       // Restore all registers immediately before the return and any
 338       // terminators that preceed it.
 339       if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) {
 340         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 341           unsigned Reg = CSI[i].getReg();
 342           const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 343           TII.loadRegFromStackSlot(*MBB, I, Reg,
 344                                    CSI[i].getFrameIdx(),
 345                                    RC, TRI);
 346           assert(I != MBB->begin() &&
 347                  "loadRegFromStackSlot didn't insert any code!");
 348           // Insert in reverse order.  loadRegFromStackSlot can insert
 349           // multiple instructions.
 350           if (AtStart)
 351             I = MBB->begin();
 352           else {
 353             I = BeforeI;
 354             ++I;
 355           }
 356         }
 357       }
 358     }
 359     return;
 360   }
 361
 362   // Insert spills.
 363   std::vector<CalleeSavedInfo> blockCSI;
 364   for (CSRegBlockMap::iterator BI = CSRSave.begin(),
 365          BE = CSRSave.end(); BI != BE; ++BI) {
 366     MachineBasicBlock* MBB = BI->first;
 367     CSRegSet save = BI->second;
 368
 369     if (save.empty())
 370       continue;
 371
 372     blockCSI.clear();
 373     for (CSRegSet::iterator RI = save.begin(),
 374            RE = save.end(); RI != RE; ++RI) {
 375       blockCSI.push_back(CSI[*RI]);
 376     }
 377     assert(blockCSI.size() > 0 &&
 378            "Could not collect callee saved register info");
 379
 380     I = MBB->begin();
 381
 382     // When shrink wrapping, use stack slot stores/loads.
 383     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
 384       // Add the callee-saved register as live-in.
 385       // It's killed at the spill.
 386       MBB->addLiveIn(blockCSI[i].getReg());
 387
 388       // Insert the spill to the stack frame.
 389       unsigned Reg = blockCSI[i].getReg();
 390       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 391       TII.storeRegToStackSlot(*MBB, I, Reg,
 392                               true,
 393                               blockCSI[i].getFrameIdx(),
 394                               RC, TRI);
 395     }
 396   }
 397
 398   for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
 399          BE = CSRRestore.end(); BI != BE; ++BI) {
 400     MachineBasicBlock* MBB = BI->first;
 401     CSRegSet restore = BI->second;
 402
 403     if (restore.empty())
 404       continue;
 405
 406     blockCSI.clear();
 407     for (CSRegSet::iterator RI = restore.begin(),
 408            RE = restore.end(); RI != RE; ++RI) {
 409       blockCSI.push_back(CSI[*RI]);
 410     }
 411     assert(blockCSI.size() > 0 &&
 412            "Could not find callee saved register info");
 413
 414     // If MBB is empty and needs restores, insert at the _beginning_.
 415     if (MBB->empty()) {
 416       I = MBB->begin();
 417     } else {
 418       I = MBB->end();
 419       --I;
 420
 421       // Skip over all terminator instructions, which are part of the
 422       // return sequence.
 423       if (! I->getDesc().isTerminator()) {
 424         ++I;
 425       } else {
 426         MachineBasicBlock::iterator I2 = I;
 427         while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
 428           I = I2;
 429       }
 430     }
 431
 432     bool AtStart = I == MBB->begin();
 433     MachineBasicBlock::iterator BeforeI = I;
 434     if (!AtStart)
 435       --BeforeI;
 436
 437     // Restore all registers immediately before the return and any
 438     // terminators that preceed it.
 439     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
 440       unsigned Reg = blockCSI[i].getReg();
 441       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 442       TII.loadRegFromStackSlot(*MBB, I, Reg,
 443                                blockCSI[i].getFrameIdx(),
 444                                RC, TRI);
 445       assert(I != MBB->begin() &&
 446              "loadRegFromStackSlot didn't insert any code!");
 447       // Insert in reverse order.  loadRegFromStackSlot can insert
 448       // multiple instructions.
 449       if (AtStart)
 450         I = MBB->begin();
 451       else {
 452         I = BeforeI;
 453         ++I;
 454       }
 455     }
 456   }
 457 }
 458
 459 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
 460 static inline void
 461 AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx,
 462                   bool StackGrowsDown, int64_t &Offset,
 463                   unsigned &MaxAlign) {
 464   // If the stack grows down, add the object size to find the lowest address.
 465   if (StackGrowsDown)
 466     Offset += MFI->getObjectSize(FrameIdx);
 467
 468   unsigned Align = MFI->getObjectAlignment(FrameIdx);
 469
 470   // If the alignment of this object is greater than that of the stack, then
 471   // increase the stack alignment to match.
 472   MaxAlign = std::max(MaxAlign, Align);
 473
 474   // Adjust to alignment boundary.
 475   Offset = (Offset + Align - 1) / Align * Align;
 476
 477   if (StackGrowsDown) {
 478     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
 479     MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
 480   } else {
 481     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
 482     MFI->setObjectOffset(FrameIdx, Offset);
 483     Offset += MFI->getObjectSize(FrameIdx);
 484   }
 485 }
 486
 487 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
 488 /// abstract stack objects.
 489 ///
 490 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
 491   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
 492
 493   bool StackGrowsDown =
 494     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
 495
 496   // Loop over all of the stack objects, assigning sequential addresses...
 497   MachineFrameInfo *MFI = Fn.getFrameInfo();
 498
 499   // Start at the beginning of the local area.
 500   // The Offset is the distance from the stack top in the direction
 501   // of stack growth -- so it's always nonnegative.
 502   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
 503   if (StackGrowsDown)
 504     LocalAreaOffset = -LocalAreaOffset;
 505   assert(LocalAreaOffset >= 0
 506          && "Local area offset should be in direction of stack growth");
 507   int64_t Offset = LocalAreaOffset;
 508
 509   // If there are fixed sized objects that are preallocated in the local area,
 510   // non-fixed objects can't be allocated right at the start of local area.
 511   // We currently don't support filling in holes in between fixed sized
 512   // objects, so we adjust 'Offset' to point to the end of last fixed sized
 513   // preallocated object.
 514   for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) {
 515     int64_t FixedOff;
 516     if (StackGrowsDown) {
 517       // The maximum distance from the stack pointer is at lower address of
 518       // the object -- which is given by offset. For down growing stack
 519       // the offset is negative, so we negate the offset to get the distance.
 520       FixedOff = -MFI->getObjectOffset(i);
 521     } else {
 522       // The maximum distance from the start pointer is at the upper
 523       // address of the object.
 524       FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i);
 525     }
 526     if (FixedOff > Offset) Offset = FixedOff;
 527   }
 528
 529   // First assign frame offsets to stack objects that are used to spill
 530   // callee saved registers.
 531   if (StackGrowsDown) {
 532     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
 533       // If the stack grows down, we need to add the size to find the lowest
 534       // address of the object.
 535       Offset += MFI->getObjectSize(i);
 536
 537       unsigned Align = MFI->getObjectAlignment(i);
 538       // Adjust to alignment boundary
 539       Offset = (Offset+Align-1)/Align*Align;
 540
 541       MFI->setObjectOffset(i, -Offset);        // Set the computed offset
 542     }
 543   } else {
 544     int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex;
 545     for (int i = MaxCSFI; i >= MinCSFI ; --i) {
 546       unsigned Align = MFI->getObjectAlignment(i);
 547       // Adjust to alignment boundary
 548       Offset = (Offset+Align-1)/Align*Align;
 549
 550       MFI->setObjectOffset(i, Offset);
 551       Offset += MFI->getObjectSize(i);
 552     }
 553   }
 554
 555   unsigned MaxAlign = MFI->getMaxAlignment();
 556
 557   // Make sure the special register scavenging spill slot is closest to the
 558   // frame pointer if a frame pointer is required.
 559   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 560   if (RS && TFI.hasFP(Fn) && !RegInfo->needsStackRealignment(Fn)) {
 561     int SFI = RS->getScavengingFrameIndex();
 562     if (SFI >= 0)
 563       AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign);
 564   }
 565
 566   // FIXME: Once this is working, then enable flag will change to a target
 567   // check for whether the frame is large enough to want to use virtual
 568   // frame index registers. Functions which don't want/need this optimization
 569   // will continue to use the existing code path.
 570   if (MFI->getUseLocalStackAllocationBlock()) {
 571     unsigned Align = MFI->getLocalFrameMaxAlign();
 572
 573     // Adjust to alignment boundary.
 574     Offset = (Offset + Align - 1) / Align * Align;
 575
 576     DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
 577
 578     // Resolve offsets for objects in the local block.
 579     for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) {
 580       std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i);
 581       int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;
 582       DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" <<
 583             FIOffset << "]\n");
 584       MFI->setObjectOffset(Entry.first, FIOffset);
 585     }
 586     // Allocate the local block
 587     Offset += MFI->getLocalFrameSize();
 588
 589     MaxAlign = std::max(Align, MaxAlign);
 590   }
 591
 592   // Make sure that the stack protector comes before the local variables on the
 593   // stack.
 594   SmallSet<int, 16> LargeStackObjs;
 595   if (MFI->getStackProtectorIndex() >= 0) {
 596     AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown,
 597                       Offset, MaxAlign);
 598
 599     // Assign large stack objects first.
 600     for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
 601       if (MFI->isObjectPreAllocated(i) &&
 602           MFI->getUseLocalStackAllocationBlock())
 603         continue;
 604       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
 605         continue;
 606       if (RS && (int)i == RS->getScavengingFrameIndex())
 607         continue;
 608       if (MFI->isDeadObjectIndex(i))
 609         continue;
 610       if (MFI->getStackProtectorIndex() == (int)i)
 611         continue;
 612       if (!MFI->MayNeedStackProtector(i))
 613         continue;
 614
 615       AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
 616       LargeStackObjs.insert(i);
 617     }
 618   }
 619
 620   // Then assign frame offsets to stack objects that are not used to spill
 621   // callee saved registers.
 622   for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
 623     if (MFI->isObjectPreAllocated(i) &&
 624         MFI->getUseLocalStackAllocationBlock())
 625       continue;
 626     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
 627       continue;
 628     if (RS && (int)i == RS->getScavengingFrameIndex())
 629       continue;
 630     if (MFI->isDeadObjectIndex(i))
 631       continue;
 632     if (MFI->getStackProtectorIndex() == (int)i)
 633       continue;
 634     if (LargeStackObjs.count(i))
 635       continue;
 636
 637     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
 638   }
 639
 640   // Make sure the special register scavenging spill slot is closest to the
 641   // stack pointer.
 642   if (RS && (!TFI.hasFP(Fn) || RegInfo->needsStackRealignment(Fn))) {
 643     int SFI = RS->getScavengingFrameIndex();
 644     if (SFI >= 0)
 645       AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign);
 646   }
 647
 648   if (!TFI.targetHandlesStackFrameRounding()) {
 649     // If we have reserved argument space for call sites in the function
 650     // immediately on entry to the current function, count it as part of the
 651     // overall stack size.
 652     if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn))
 653       Offset += MFI->getMaxCallFrameSize();
 654
 655     // Round up the size to a multiple of the alignment.  If the function has
 656     // any calls or alloca's, align to the target's StackAlignment value to
 657     // ensure that the callee's frame or the alloca data is suitably aligned;
 658     // otherwise, for leaf functions, align to the TransientStackAlignment
 659     // value.
 660     unsigned StackAlign;
 661     if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
 662         (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
 663       StackAlign = TFI.getStackAlignment();
 664     else
 665       StackAlign = TFI.getTransientStackAlignment();
 666
 667     // If the frame pointer is eliminated, all frame offsets will be relative to
 668     // SP not FP. Align to MaxAlign so this works.
 669     StackAlign = std::max(StackAlign, MaxAlign);
 670     unsigned AlignMask = StackAlign - 1;
 671     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
 672   }
 673
 674   // Update frame info to pretend that this is part of the stack...
 675   MFI->setStackSize(Offset - LocalAreaOffset);
 676 }
 677
 678 /// insertPrologEpilogCode - Scan the function for modified callee saved
 679 /// registers, insert spill code for these callee saved registers, then add
 680 /// prolog and epilog code to the function.
 681 ///
 682 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
 683   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
 684
 685   // Add prologue to the function...
 686   TFI.emitPrologue(Fn);
 687
 688   // Add epilogue to restore the callee-save registers in each exiting block
 689   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 690     // If last instruction is a return instruction, add an epilogue
 691     if (!I->empty() && I->back().getDesc().isReturn())
 692       TFI.emitEpilogue(Fn, *I);
 693   }
 694 }
 695
 696 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
 697 /// register references and actual offsets.
 698 ///
 699 void PEI::replaceFrameIndices(MachineFunction &Fn) {
 700   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
 701
 702   const TargetMachine &TM = Fn.getTarget();
 703   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
 704   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
 705   const TargetFrameInfo *TFI = TM.getFrameInfo();
 706   bool StackGrowsDown =
 707     TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
 708   int FrameSetupOpcode   = TRI.getCallFrameSetupOpcode();
 709   int FrameDestroyOpcode = TRI.getCallFrameDestroyOpcode();
 710
 711   for (MachineFunction::iterator BB = Fn.begin(),
 712          E = Fn.end(); BB != E; ++BB) {
 713 #ifndef NDEBUG
 714     int SPAdjCount = 0; // frame setup / destroy count.
 715 #endif
 716     int SPAdj = 0;  // SP offset due to call frame setup / destroy.
 717     if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
 718
 719     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
 720
 721       if (I->getOpcode() == FrameSetupOpcode ||
 722           I->getOpcode() == FrameDestroyOpcode) {
 723 #ifndef NDEBUG
 724         // Track whether we see even pairs of them
 725         SPAdjCount += I->getOpcode() == FrameSetupOpcode ? 1 : -1;
 726 #endif
 727         // Remember how much SP has been adjusted to create the call
 728         // frame.
 729         int Size = I->getOperand(0).getImm();
 730
 731         if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
 732             (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
 733           Size = -Size;
 734
 735         SPAdj += Size;
 736
 737         MachineBasicBlock::iterator PrevI = BB->end();
 738         if (I != BB->begin()) PrevI = prior(I);
 739         TRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
 740
 741         // Visit the instructions created by eliminateCallFramePseudoInstr().
 742         if (PrevI == BB->end())
 743           I = BB->begin();     // The replaced instr was the first in the block.
 744         else
 745           I = llvm::next(PrevI);
 746         continue;
 747       }
 748
 749       MachineInstr *MI = I;
 750       bool DoIncr = true;
 751       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 752         if (MI->getOperand(i).isFI()) {
 753           // Some instructions (e.g. inline asm instructions) can have
 754           // multiple frame indices and/or cause eliminateFrameIndex
 755           // to insert more than one instruction. We need the register
 756           // scavenger to go through all of these instructions so that
 757           // it can update its register information. We keep the
 758           // iterator at the point before insertion so that we can
 759           // revisit them in full.
 760           bool AtBeginning = (I == BB->begin());
 761           if (!AtBeginning) --I;
 762
 763           // If this instruction has a FrameIndex operand, we need to
 764           // use that target machine register info object to eliminate
 765           // it.
 766           TRI.eliminateFrameIndex(MI, SPAdj,
 767                                   FrameIndexVirtualScavenging ?  NULL : RS);
 768
 769           // Reset the iterator if we were at the beginning of the BB.
 770           if (AtBeginning) {
 771             I = BB->begin();
 772             DoIncr = false;
 773           }
 774
 775           MI = 0;
 776           break;
 777         }
 778
 779       if (DoIncr && I != BB->end()) ++I;
 780
 781       // Update register states.
 782       if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
 783     }
 784
 785     // If we have evenly matched pairs of frame setup / destroy instructions,
 786     // make sure the adjustments come out to zero. If we don't have matched
 787     // pairs, we can't be sure the missing bit isn't in another basic block
 788     // due to a custom inserter playing tricks, so just asserting SPAdj==0
 789     // isn't sufficient. See tMOVCC on Thumb1, for example.
 790     assert((SPAdjCount || SPAdj == 0) &&
 791            "Unbalanced call frame setup / destroy pairs?");
 792   }
 793 }
 794
 795 /// scavengeFrameVirtualRegs - Replace all frame index virtual registers
 796 /// with physical registers. Use the register scavenger to find an
 797 /// appropriate register to use.
 798 void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
 799   // Run through the instructions and find any virtual registers.
 800   for (MachineFunction::iterator BB = Fn.begin(),
 801        E = Fn.end(); BB != E; ++BB) {
 802     RS->enterBasicBlock(BB);
 803
 804     unsigned VirtReg = 0;
 805     unsigned ScratchReg = 0;
 806     int SPAdj = 0;
 807
 808     // The instruction stream may change in the loop, so check BB->end()
 809     // directly.
 810     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
 811       MachineInstr *MI = I;
 812       bool DoIncr = true;
 813       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 814         if (MI->getOperand(i).isReg()) {
 815           MachineOperand &MO = MI->getOperand(i);
 816           unsigned Reg = MO.getReg();
 817           if (Reg == 0)
 818             continue;
 819           if (!TargetRegisterInfo::isVirtualRegister(Reg))
 820             continue;
 821
 822           ++NumVirtualFrameRegs;
 823
 824           // Have we already allocated a scratch register for this virtual?
 825           if (Reg != VirtReg) {
 826             // When we first encounter a new virtual register, it
 827             // must be a definition.
 828             assert(MI->getOperand(i).isDef() &&
 829                    "frame index virtual missing def!");
 830             // Scavenge a new scratch register
 831             VirtReg = Reg;
 832             const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
 833             ScratchReg = RS->scavengeRegister(RC, I, SPAdj);
 834             ++NumScavengedRegs;
 835           }
 836           // Replace this reference to the virtual register with the
 837           // scratch register.
 838           assert (ScratchReg && "Missing scratch register!");
 839           MI->getOperand(i).setReg(ScratchReg);
 840
 841         }
 842       }
 843       if (DoIncr) {
 844         RS->forward(I);
 845         ++I;
 846       }
 847     }
 848   }
 849 }