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