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 implements a shrink wrapping variant of prolog/epilog insertion:
  18 // - Places callee saved register (CSR) spills and restores in the CFG to
  19 //   tightly surround uses so that execution paths that do not use CSRs do not
  20 //   pay the spill/restore penalty.
  21 //
  22 // - Avoiding placment of spills/restores in loops: if a CSR is used inside a
  23 //   loop(nest), the spills are placed in the loop preheader, and restores are
  24 //   placed in the loop exit nodes (the successors of the loop _exiting_ nodes).
  25 //
  26 // - Covering paths without CSR uses: e.g. if a restore is placed in a join
  27 //   block, a matching spill is added to the end of all immediate predecessor
  28 //   blocks that are not reached by a spill. Similarly for saves placed in
  29 //   branch blocks.
  30 //
  31 // Shrink wrapping uses an analysis similar to the one in GVNPRE to determine
  32 // which basic blocks require callee-saved register save/restore code.
  33 //
  34 // This pass uses MachineDominators and MachineLoopInfo. Loop information
  35 // is used to prevent shrink wrapping of callee-saved register save/restore
  36 // code into loops.
  37 //
  38 //===----------------------------------------------------------------------===//
  39
  40 #define DEBUG_TYPE "shrink-wrap"
  41
  42 #include "llvm/CodeGen/Passes.h"
  43 #include "llvm/CodeGen/MachineDominators.h"
  44 #include "llvm/CodeGen/MachineLoopInfo.h"
  45 #include "llvm/CodeGen/MachineFunctionPass.h"
  46 #include "llvm/CodeGen/MachineInstr.h"
  47 #include "llvm/CodeGen/MachineFrameInfo.h"
  48 #include "llvm/CodeGen/MachineModuleInfo.h"
  49 #include "llvm/CodeGen/MachineRegisterInfo.h"
  50 #include "llvm/CodeGen/RegisterScavenging.h"
  51 #include "llvm/Target/TargetMachine.h"
  52 #include "llvm/Target/TargetRegisterInfo.h"
  53 #include "llvm/Target/TargetFrameInfo.h"
  54 #include "llvm/Target/TargetInstrInfo.h"
  55 #include "llvm/ADT/SparseBitVector.h"
  56 #include "llvm/ADT/DenseMap.h"
  57 #include "llvm/ADT/PostOrderIterator.h"
  58 #include "llvm/ADT/Statistic.h"
  59 #include "llvm/Support/CommandLine.h"
  60 #include "llvm/Support/Compiler.h"
  61 #include "llvm/Support/Debug.h"
  62 #include "llvm/ADT/STLExtras.h"
  63 #include <climits>
  64 #include <sstream>
  65
  66 using namespace llvm;
  67
  68 // Shrink Wrapping:
  69 static cl::opt<bool>
  70 ShrinkWrapping("shrink-wrap",
  71   cl::desc("Apply shrink wrapping to callee-saved register spills/restores"));
  72
  73 namespace {
  74   struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
  75     static char ID;
  76     PEI() : MachineFunctionPass(&ID) {}
  77
  78     const char *getPassName() const {
  79       return "Prolog/Epilog Insertion & Frame Finalization";
  80     }
  81
  82     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  83       AU.setPreservesCFG();
  84       if (ShrinkWrapping) {
  85         AU.addRequired<MachineLoopInfo>();
  86         AU.addRequired<MachineDominatorTree>();
  87       }
  88       AU.addPreserved<MachineLoopInfo>();
  89       AU.addPreserved<MachineDominatorTree>();
  90       MachineFunctionPass::getAnalysisUsage(AU);
  91     }
  92
  93     /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
  94     /// frame indexes with appropriate references.
  95     ///
  96     bool runOnMachineFunction(MachineFunction &Fn) {
  97       const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
  98       RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
  99
 100       // Get MachineModuleInfo so that we can track the construction of the
 101       // frame.
 102       if (MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>())
 103         Fn.getFrameInfo()->setMachineModuleInfo(MMI);
 104
 105       // Allow the target machine to make some adjustments to the function
 106       // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
 107       TRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
 108
 109       // Scan the function for modified callee saved registers and insert spill
 110       // code for any callee saved registers that are modified.  Also calculate
 111       // the MaxCallFrameSize and HasCalls variables for the function's frame
 112       // information and eliminates call frame pseudo instructions.
 113       calculateCalleeSavedRegisters(Fn);
 114
 115       // Determine placement of CSR spill/restore code:
 116       //  - with shrink wrapping, place spills and restores to tightly
 117       //    enclose regions in the Machine CFG of the function where
 118       //    they are used. Without shrink wrapping
 119       //  - default (no shrink wrapping), place all spills in the
 120       //    entry block, all restores in return blocks.
 121       placeCSRSpillsAndRestores(Fn);
 122
 123       // Add the code to save and restore the callee saved registers
 124       insertCSRSpillsAndRestores(Fn);
 125
 126       // Allow the target machine to make final modifications to the function
 127       // before the frame layout is finalized.
 128       TRI->processFunctionBeforeFrameFinalized(Fn);
 129
 130       // Calculate actual frame offsets for all of the abstract stack objects...
 131       calculateFrameObjectOffsets(Fn);
 132
 133       // Add prolog and epilog code to the function.  This function is required
 134       // to align the stack frame as necessary for any stack variables or
 135       // called functions.  Because of this, calculateCalleeSavedRegisters
 136       // must be called before this function in order to set the HasCalls
 137       // and MaxCallFrameSize variables.
 138       insertPrologEpilogCode(Fn);
 139
 140       // Replace all MO_FrameIndex operands with physical register references
 141       // and actual offsets.
 142       //
 143       replaceFrameIndices(Fn);
 144
 145       delete RS;
 146       return true;
 147     }
 148
 149   private:
 150     RegScavenger *RS;
 151
 152     // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
 153     // stack frame indexes.
 154     unsigned MinCSFrameIndex, MaxCSFrameIndex;
 155
 156     // Analysis info for spill/restore placement.
 157     // "CSR": "callee saved register".
 158
 159     // CSRegSet contains indices into the Callee Saved Register Info
 160     // vector built by calculateCalleeSavedRegisters() and accessed
 161     // via MF.getFrameInfo()->getCalleeSavedInfo().
 162     typedef SparseBitVector<> CSRegSet;
 163
 164     // CSRegBlockMap maps MachineBasicBlocks to sets of callee
 165     // saved register indices.
 166     typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap;
 167
 168     // Set and maps for computing CSR spill/restore placement:
 169     //  used in function (UsedCSRegs)
 170     //  used in a basic block (CSRUsed)
 171     //  anticipatable in a basic block (Antic{In,Out})
 172     //  available in a basic block (Avail{In,Out})
 173     //  to be spilled at the entry to a basic block (CSRSave)
 174     //  to be restored at the end of a basic block (CSRRestore)
 175
 176     CSRegSet UsedCSRegs;
 177     CSRegBlockMap CSRUsed;
 178     CSRegBlockMap AnticIn, AnticOut;
 179     CSRegBlockMap AvailIn, AvailOut;
 180     CSRegBlockMap CSRSave;
 181     CSRegBlockMap CSRRestore;
 182
 183     // Entry and return blocks of the current function.
 184     MachineBasicBlock* EntryBlock;
 185     SmallVector<MachineBasicBlock*, 4> ReturnBlocks;
 186
 187     // Flag to control shrink wrapping per-function:
 188     // may choose to skip shrink wrapping for certain
 189     // functions.
 190     bool ShrinkWrapThisFunction;
 191
 192     bool calculateSets(MachineFunction &Fn);
 193     void calculateAnticAvail(MachineFunction &Fn);
 194     MachineBasicBlock* moveSpillsOutOfLoops(MachineFunction &Fn,
 195                                             MachineBasicBlock* MBB);
 196     void addRestoresForSBranchBlock(MachineFunction &Fn,
 197                                     MachineBasicBlock* MBB);
 198     void moveRestoresOutOfLoops(MachineFunction& Fn,
 199                                 MachineBasicBlock* MBB,
 200                                 std::vector<MachineBasicBlock*>& SBLKS);
 201     void addSavesForRJoinBlocks(MachineFunction& Fn,
 202                                 std::vector<MachineBasicBlock*>& SBLKS);
 203     void placeSpillsAndRestores(MachineFunction &Fn);
 204     void placeCSRSpillsAndRestores(MachineFunction &Fn);
 205     void calculateCalleeSavedRegisters(MachineFunction &Fn);
 206     void insertCSRSpillsAndRestores(MachineFunction &Fn);
 207     void calculateFrameObjectOffsets(MachineFunction &Fn);
 208     void replaceFrameIndices(MachineFunction &Fn);
 209     void insertPrologEpilogCode(MachineFunction &Fn);
 210
 211     // Initialize all shrink wrapping data.
 212     void initShrinkWrappingInfo() {
 213       UsedCSRegs.clear();
 214       CSRUsed.clear();
 215       AnticIn.clear();
 216       AnticOut.clear();
 217       AvailIn.clear();
 218       AvailOut.clear();
 219       CSRSave.clear();
 220       CSRRestore.clear();
 221       EntryBlock = 0;
 222       if (! ReturnBlocks.empty())
 223         ReturnBlocks.clear();
 224       ShrinkWrapThisFunction = ShrinkWrapping;
 225     }
 226
 227     // Convienences for dealing with machine loops.
 228     MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP) {
 229       assert(LP && "Machine loop is NULL.");
 230       MachineBasicBlock* PHDR = LP->getLoopPreheader();
 231       MachineLoop* PLP = LP->getParentLoop();
 232       while (PLP) {
 233         PHDR = PLP->getLoopPreheader();
 234         PLP = PLP->getParentLoop();
 235       }
 236       return PHDR;
 237     }
 238
 239     MachineLoop* getTopLevelLoopParent(MachineLoop *LP) {
 240       if (LP == 0)
 241         return 0;
 242       MachineLoop* PLP = LP->getParentLoop();
 243       while (PLP) {
 244         LP = PLP;
 245         PLP = PLP->getParentLoop();
 246       }
 247       return LP;
 248     }
 249
 250 #ifndef NDEBUG
 251     // Debugging methods.
 252     static std::string getBasicBlockName(const MachineBasicBlock* MBB) {
 253       std::ostringstream name;
 254       if (MBB) {
 255         if (MBB->getBasicBlock())
 256           name << MBB->getBasicBlock()->getName();
 257         else
 258           name << "_MBB_" << MBB->getNumber();
 259       }
 260       return name.str();
 261     }
 262
 263     static std::string stringifyCSRegSet(const CSRegSet& s,
 264                                          MachineFunction &Fn) {
 265       const TargetRegisterInfo* TRI = Fn.getTarget().getRegisterInfo();
 266       const std::vector<CalleeSavedInfo> CSI =
 267         Fn.getFrameInfo()->getCalleeSavedInfo();
 268
 269       std::ostringstream srep;
 270       if (CSI.size() == 0) {
 271         srep << "[]";
 272         return srep.str();
 273       }
 274       srep << "[";
 275       CSRegSet::iterator I = s.begin(), E = s.end();
 276       if (I != E) {
 277         unsigned reg = CSI[*I].getReg();
 278         srep << TRI->getName(reg);
 279         for (++I; I != E; ++I) {
 280           reg = CSI[*I].getReg();
 281           srep << ",";
 282           srep << TRI->getName(reg);
 283         }
 284       }
 285       srep << "]";
 286       return srep.str();
 287     }
 288
 289     static void dumpSet(const CSRegSet& s, MachineFunction &Fn) {
 290       DOUT << stringifyCSRegSet(s, Fn) << "\n";
 291     }
 292 #endif
 293
 294   };
 295   char PEI::ID = 0;
 296 }
 297
 298 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
 299 /// prolog and epilog code, and eliminates abstract frame references.
 300 ///
 301 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
 302
 303
 304 /// placeCSRSpillsAndRestores - determine which MBBs of the function
 305 /// need save, restore code for callee-saved registers by doing a DF analysis
 306 /// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
 307 /// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
 308 /// is used to ensure that CSR save/restore code is not placed inside loops.
 309 /// This function computes the maps of MBBs -> CSRs to spill and restore
 310 /// in CSRSave, CSRRestore.
 311 ///
 312 /// If shrink wrapping is not being performed, place all spills in
 313 /// the entry block, all restores in return blocks. In this case,
 314 /// CSRSave has a single mapping, CSRRestore has mappings for each
 315 /// return block.
 316 ///
 317 void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
 318
 319 #ifndef NDEBUG
 320   DOUT << "Place CSR spills/restores for "
 321        << Fn.getFunction()->getName() << "\n";
 322 #endif
 323
 324   initShrinkWrappingInfo();
 325
 326   if (calculateSets(Fn))
 327     placeSpillsAndRestores(Fn);
 328 }
 329
 330 /// calculateAnticAvail - helper for computing the data flow
 331 /// sets required for determining spill/restore placements.
 332 ///
 333 void PEI::calculateAnticAvail(MachineFunction &Fn) {
 334
 335   // Calulate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG.
 336   bool changed = true;
 337   unsigned iterations = 0;
 338   while (changed) {
 339     changed = false;
 340     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
 341          MBBI != MBBE; ++MBBI) {
 342       MachineBasicBlock* MBB = MBBI;
 343
 344       // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCC(MBB))
 345       MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 346         SE = MBB->succ_end();
 347       if (SI != SE) {
 348         CSRegSet prevAnticOut = AnticOut[MBB];
 349         MachineBasicBlock* SUCC = *SI;
 350         AnticOut[MBB] = AnticIn[SUCC];
 351         for (++SI; SI != SE; ++SI) {
 352           SUCC = *SI;
 353           AnticOut[MBB] &= AnticIn[SUCC];
 354         }
 355         if (prevAnticOut != AnticOut[MBB])
 356           changed = true;
 357       }
 358       // AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
 359       CSRegSet prevAnticIn = AnticIn[MBB];
 360       AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
 361       if (prevAnticIn |= AnticIn[MBB])
 362         changed = true;
 363
 364       // AvailIn[MBB] = INTERSECT(AvailOut[S] for S in PRED(MBB))
 365       MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 366         PE = MBB->pred_end();
 367       if (PI != PE) {
 368         CSRegSet prevAvailIn = AvailIn[MBB];
 369         MachineBasicBlock* PRED = *PI;
 370         AvailIn[MBB] = AvailOut[PRED];
 371         for (++PI; PI != PE; ++PI) {
 372           PRED = *PI;
 373           AvailIn[MBB] &= AvailOut[PRED];
 374         }
 375         if (prevAvailIn != AvailIn[MBB])
 376           changed = true;
 377       }
 378       // AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
 379       CSRegSet prevAvailOut = AvailOut[MBB];
 380       AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
 381       if (prevAvailOut |= AvailOut[MBB])
 382         changed = true;
 383     }
 384     ++iterations;
 385   }
 386
 387   // EXP
 388   AnticIn[EntryBlock].clear();
 389   AnticOut[EntryBlock].clear();
 390
 391 #ifndef NDEBUG
 392   DOUT << "-----------------------------------------------------------\n";
 393   DOUT << "iterations = " << iterations << "\n";
 394   DOUT << "-----------------------------------------------------------\n";
 395   DOUT << "MBB | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n";
 396   DOUT << "-----------------------------------------------------------\n";
 397   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
 398        MBBI != MBBE; ++MBBI) {
 399     MachineBasicBlock* MBB = MBBI;
 400
 401     DOUT << getBasicBlockName(MBB) << " | "
 402          << stringifyCSRegSet(AnticIn[MBB], Fn)
 403          << " | "
 404          << stringifyCSRegSet(AnticOut[MBB], Fn)
 405          << " | "
 406          << stringifyCSRegSet(AvailIn[MBB], Fn)
 407          << " | "
 408          << stringifyCSRegSet(AvailOut[MBB], Fn)
 409          << "\n";
 410   }
 411 #endif
 412 }
 413
 414 /// calculateSets - helper function for placeCSRSpillsAndRestores,
 415 /// collect the CSRs used in this function, develop the DF sets that
 416 /// describe the minimal regions in the Machine CFG around which spills,
 417 /// restores must be placed.
 418 ///
 419 /// This function decides if shrink wrapping should actually be done:
 420 ///   if all CSR uses are in the entry block, no shrink wrapping is possible,
 421 ///   so ShrinkWrapping is turned off (for the current function) and the
 422 ///   function returns false.
 423 ///
 424 bool PEI::calculateSets(MachineFunction &Fn) {
 425
 426   // Sets used to compute spill, restore placement sets.
 427   const std::vector<CalleeSavedInfo> CSI =
 428     Fn.getFrameInfo()->getCalleeSavedInfo();
 429
 430   // If no CSRs used, we are done.
 431   if (CSI.empty()) {
 432 #ifndef NDEBUG
 433     DOUT << Fn.getFunction()->getName()
 434          << " uses no callee-saved registers.\n";
 435 #endif
 436     return false;
 437   }
 438
 439 #ifndef NDEBUG
 440   DOUT << "-----------------------------------------------------------\n";
 441 #endif
 442
 443   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
 444   bool allCSRUsesInEntryBlock = true;
 445
 446   // Initialize UsedCSRegs set, CSRUsed map.
 447   // At the same time, put entry block directly into
 448   // CSRSave, CSRRestore sets if any CSRs are used.
 449   //
 450   // Quick exit option (not implemented):
 451   //   Given N CSR uses in entry block,
 452   //   revert to default behavior, skip the placement
 453   //   step and put all saves in entry, restores in
 454   //   return blocks.
 455
 456   // Set up entry and return blocks.
 457   EntryBlock = Fn.begin();
 458   for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
 459        MBB != E; ++MBB)
 460     if (!MBB->empty() && MBB->back().getDesc().isReturn())
 461       ReturnBlocks.push_back(MBB);
 462
 463   // TODO -- check for a use of a CSR in each imm. successor of EntryBlock,
 464   // do not shrink wrap this function if this is the case.
 465
 466   // If not shrink wrapping (this function) at this point, set bits in
 467   // CSR{Save,Restore}[] and UsedCSRegs, then return.
 468   if (! ShrinkWrapThisFunction) {
 469     for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
 470       UsedCSRegs.set(inx);
 471       CSRSave[EntryBlock].set(inx);
 472       for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
 473         CSRRestore[ReturnBlocks[ri]].set(inx);
 474     }
 475     return false;
 476   }
 477
 478   // Walk instructions in all MBBs, create basic sets, choose
 479   // whether or not to shrink wrap this function.
 480   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
 481        MBBI != MBBE; ++MBBI) {
 482     MachineBasicBlock* MBB = MBBI;
 483     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
 484       for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
 485         unsigned Reg = CSI[inx].getReg();
 486         // If instruction I reads or modifies Reg, add it to UsedCSRegs,
 487         // CSRUsed map for the current block.
 488         for (unsigned opInx = 0, opEnd = I->getNumOperands();
 489              opInx != opEnd; ++opInx) {
 490           const MachineOperand &MO = I->getOperand(opInx);
 491           if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
 492             continue;
 493           unsigned MOReg = MO.getReg();
 494           if (!MOReg)
 495             continue;
 496           if (MOReg == Reg ||
 497               (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
 498                TargetRegisterInfo::isPhysicalRegister(Reg) &&
 499                TRI->isSubRegister(MOReg, Reg))) {
 500             // CSR Reg is defined/used in block MBB.
 501             UsedCSRegs.set(inx);
 502             CSRUsed[MBB].set(inx);
 503             // Short-circuit analysis for entry, return blocks:
 504             // if a CSR is used in the entry block, add it directly
 505             // to CSRSave[EntryBlock] and to CSRRestore[R] for R
 506             // in ReturnBlocks. Note CSR uses in non-entry blocks.
 507             if (ShrinkWrapThisFunction) {
 508               if (MBB == EntryBlock) {
 509                 CSRSave[MBB].set(inx);
 510                 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
 511                   CSRRestore[ReturnBlocks[ri]].set(inx);
 512               } else
 513                 allCSRUsesInEntryBlock = false;
 514             } else {
 515               // Not shrink wrapping => ensure saves/restores are correctly
 516               // added for entry, return blocks.
 517               CSRSave[EntryBlock].set(inx);
 518               for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
 519                 CSRRestore[ReturnBlocks[ri]].set(inx);
 520             }
 521           }
 522         }
 523       }
 524     }
 525 #ifndef NDEBUG
 526     DOUT << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
 527          << stringifyCSRegSet(CSRUsed[MBB], Fn) << "\n";
 528 #endif
 529   }
 530
 531 #ifndef NDEBUG
 532   DOUT << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs, Fn) << "\n";
 533 #endif
 534
 535   // Early exit:
 536   // 1. Not asked to do shrink wrapping => just "place" all spills(restores)
 537   //    in the entry(return) block(s), already done above.
 538   // 2. All CSR uses in entry block => same as case 1, but say we will
 539   //    not shrink wrap the current function.
 540   ShrinkWrapThisFunction = (ShrinkWrapping &&
 541                             ShrinkWrapThisFunction &&
 542                             ! allCSRUsesInEntryBlock);
 543   if (! ShrinkWrapThisFunction) {
 544     return false;
 545   }
 546
 547   calculateAnticAvail(Fn);
 548
 549   return true;
 550 }
 551
 552 /// moveSpillsOutOfLoops - helper for placeSpillsAndRestores() which
 553 /// relocates a spill from a subgraph in a loop to the loop preheader.
 554 /// Returns the MBB to which saves have been moved, or the given MBB
 555 /// if it is a branch point.
 556 ///
 557 MachineBasicBlock* PEI::moveSpillsOutOfLoops(MachineFunction &Fn,
 558                                              MachineBasicBlock* MBB) {
 559   if (MBB == 0 || CSRSave[MBB].empty())
 560     return 0;
 561
 562   // Block to which saves are moved.
 563   MachineBasicBlock* DEST = 0;
 564   MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
 565
 566   if (MachineLoop* LP = LI.getLoopFor(MBB)) {
 567     MachineBasicBlock* LPH = getTopLevelLoopPreheader(LP);
 568     assert(LPH && "Loop has no top level preheader?");
 569
 570 #ifndef NDEBUG
 571     DOUT << "Moving saves of "
 572          << stringifyCSRegSet(CSRSave[MBB], Fn)
 573          << " from " << getBasicBlockName(MBB)
 574          << " to " << getBasicBlockName(LPH) << "\n";
 575 #endif
 576     // Add CSRegSet from MBB to LPH, empty out MBB's CSRegSet.
 577     CSRSave[LPH] |= CSRSave[MBB];
 578     // If saves moved to entry block, add restores to returns.
 579     if (LPH == EntryBlock) {
 580       for (unsigned i = 0, e = ReturnBlocks.size(); i != e; ++i)
 581         CSRRestore[ReturnBlocks[i]] |= CSRSave[MBB];
 582     } else {
 583       // Remember where we moved the save so we can add
 584       // restores on successor paths if necessary.
 585       if (LPH->succ_size() > 1)
 586         DEST = LPH;
 587     }
 588     CSRSave[MBB].clear();
 589   } else if (MBB->succ_size() > 1)
 590     DEST = MBB;
 591   return DEST;
 592 }
 593
 594 /// addRestoresForSBranchBlock - helper for placeSpillsAndRestores() which
 595 /// adds restores of CSRs saved in branch point MBBs to the front of any
 596 /// successor blocks connected to regions with no uses of the saved CSRs.
 597 ///
 598 void PEI::addRestoresForSBranchBlock(MachineFunction &Fn,
 599                                      MachineBasicBlock* MBB) {
 600
 601   if (MBB == 0 || CSRSave[MBB].empty() || MBB->succ_size() < 2)
 602     return;
 603
 604   // Add restores of CSRs saved in branch point MBBs to the
 605   // front of any succ blocks flowing into regions that
 606   // have no uses of MBB's CSRs.
 607   bool hasCSRUses = false;
 608   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 609          SE = MBB->succ_end(); SI != SE; ++SI) {
 610     MachineBasicBlock* SUCC = *SI;
 611     bool needsRestore = false;
 612     if (CSRUsed[SUCC].intersects(CSRSave[MBB])) {
 613       hasCSRUses = true;
 614       continue;
 615     }
 616     needsRestore = true;
 617     for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
 618            BE = df_end(SUCC); BI != BE; ++BI) {
 619       MachineBasicBlock* SBB = *BI;
 620       if (CSRUsed[SBB].intersects(CSRSave[MBB])) {
 621         hasCSRUses = true;
 622         needsRestore = false;
 623         break;
 624       }
 625     }
 626     // Additional restores are needed for SUCC iff there is at least
 627     // one CSR use reachable from the successors of MBB and there
 628     // are no uses in or below SUCC.
 629     if (needsRestore && hasCSRUses) {
 630 #ifndef NDEBUG
 631       DOUT << "MBB " << getBasicBlockName(MBB)
 632            << " needs a restore on path to successor "
 633            << getBasicBlockName(SUCC) << "\n";
 634 #endif
 635       // Add restores to SUCC for all CSRs saved in MBB...
 636       CSRRestore[SUCC] = CSRSave[MBB];
 637     }
 638   }
 639 }
 640
 641 /// moveRestoresOutOfLoops - helper for placeSpillsAndRestores() which
 642 /// relocates restores from a subgraph in a loop to the loop exit blocks.
 643 /// This function records the MBBs to which restores have been moved in
 644 /// SBLKS. If no restores are moved, SBLKS contains the input MBB if it
 645 /// is a join point in the Machine CFG.
 646 ///
 647 void PEI::moveRestoresOutOfLoops(MachineFunction& Fn,
 648                                  MachineBasicBlock* MBB,
 649                                  std::vector<MachineBasicBlock*>& SBLKS) {
 650
 651   SBLKS.clear();
 652   if (MBB == 0 || CSRRestore[MBB].empty())
 653     return;
 654
 655   MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
 656
 657   if (MachineLoop* LP = LI.getLoopFor(MBB)) {
 658     LP = getTopLevelLoopParent(LP);
 659     assert(LP && "Loop with no top level parent?");
 660
 661     SmallVector<MachineBasicBlock*, 4> exitBlocks;
 662
 663     LP->getExitBlocks(exitBlocks);
 664     assert(exitBlocks.size() > 0 &&
 665            "Loop has no top level exit blocks?");
 666     for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
 667       MachineBasicBlock* EXB = exitBlocks[i];
 668
 669 #ifndef NDEBUG
 670       DOUT << "Moving restores of "
 671            << stringifyCSRegSet(CSRRestore[MBB], Fn)
 672            << " from " << getBasicBlockName(MBB)
 673            << " to " << getBasicBlockName(EXB) << "\n";
 674 #endif
 675
 676       // Add CSRegSet from MBB to LPE, empty out MBB's CSRegSet.
 677       CSRRestore[EXB] |= CSRRestore[MBB];
 678       if (EXB->pred_size() > 1)
 679         SBLKS.push_back(EXB);
 680     }
 681     CSRRestore[MBB].clear();
 682   } else if (MBB->pred_size() > 1)
 683     SBLKS.push_back(MBB);
 684 }
 685
 686 /// addSavesForRJoinBlocks - Add saves of CSRs restored in join point MBBs
 687 /// to the ends of any pred blocks that flow into MBB from regions that
 688 /// have no uses of MBB's CSRs.
 689 ///
 690 void PEI::addSavesForRJoinBlocks(MachineFunction& Fn,
 691                                  std::vector<MachineBasicBlock*>& SBLKS) {
 692
 693   if (SBLKS.empty())
 694     return;
 695
 696   for (unsigned i = 0, e = SBLKS.size(); i != e; ++i) {
 697     MachineBasicBlock* MBB = SBLKS[i];
 698     if (MBB->pred_size() > 1) {
 699       bool needsSave = false;
 700       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 701              PE = MBB->pred_end(); PI != PE; ++PI) {
 702         MachineBasicBlock* PRED = *PI;
 703
 704         // Walk back up in the CFG from the preds of MBB, look for
 705         // a block that uses any CSR that is restored in MBB.
 706         if (CSRUsed[PRED].intersects(CSRRestore[MBB]))
 707           continue;
 708         needsSave = true;
 709         for (idf_iterator<MachineBasicBlock*> PPI = idf_begin(PRED),
 710                PPE = idf_end(PRED); PPI != PPE; ++PPI) {
 711           MachineBasicBlock* PBB = *PPI;
 712           if (CSRUsed[PBB].intersects(CSRRestore[MBB])) {
 713             needsSave = false;
 714             break;
 715           }
 716         }
 717         if (needsSave) {
 718           // Add saves to PRED for all CSRs restored in MBB...
 719 #ifndef NDEBUG
 720           DOUT << "MBB " << getBasicBlockName(MBB)
 721                << " needs a save on path from predecessor "
 722                << getBasicBlockName(PRED) << "\n";
 723 #endif
 724           CSRSave[PRED] = CSRRestore[MBB];
 725         }
 726       }
 727     }
 728   }
 729 }
 730
 731 /// placeSpillsAndRestores - decide which MBBs need spills, restores
 732 /// of CSRs.
 733 ///
 734 void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
 735
 736 #ifndef NDEBUG
 737   DOUT << "-----------------------------------------------------------\n";
 738 #endif
 739
 740   // Calculate CSR{Save,Restore} using Antic, Avail on the Machine-CFG.
 741   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
 742        MBBI != MBBE; ++MBBI) {
 743     MachineBasicBlock* MBB = MBBI;
 744     // Entry block saves are recorded in UsedCSRegs pass above.
 745     if (MBB != EntryBlock) {
 746       // Intersect (CSRegs - AnticIn[P]) for all predecessors P of MBB
 747       CSRegSet anticInPreds;
 748       MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 749         PE = MBB->pred_end();
 750       if (PI != PE) {
 751         MachineBasicBlock* PRED = *PI;
 752         anticInPreds = UsedCSRegs - AnticIn[PRED];
 753         for (++PI; PI != PE; ++PI) {
 754           PRED = *PI;
 755           // Handle self loop.
 756           if (PRED != MBB)
 757             anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
 758         }
 759       }
 760       // CSRSave[MBB] = (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds
 761       CSRSave[MBB] = (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
 762
 763       // Remove the CSRs that are saved in the entry block
 764       if (! CSRSave[MBB].empty() && ! CSRSave[EntryBlock].empty())
 765         CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
 766
 767       // Move saves inside loops to the preheaders of the outermost
 768       // containing loops, add restores to blocks reached by saves
 769       // placed at branch points where necessary.
 770       if (MachineBasicBlock* DESTBB = moveSpillsOutOfLoops(Fn, MBB)) {
 771         // Add restores to blocks reached by saves placed at branch
 772         // points where necessary.
 773         addRestoresForSBranchBlock(Fn, DESTBB);
 774       }
 775     }
 776
 777 #ifndef NDEBUG
 778     if (! CSRSave[MBB].empty())
 779       DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
 780            << stringifyCSRegSet(CSRSave[MBB], Fn) << "\n";
 781 #endif
 782
 783     // Compute CSRRestore, which may already be set for return blocks.
 784     if (! CSRRestore[MBB].empty() || MBB->pred_size() == 0)
 785       continue;
 786
 787     // Intersect (CSRegs - AvailOut[S]) for all successors S of MBB
 788     CSRegSet availOutSucc;
 789     MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 790       SE = MBB->succ_end();
 791     if (SI != SE) {
 792       MachineBasicBlock* SUCC = *SI;
 793       availOutSucc = UsedCSRegs - AvailOut[SUCC];
 794       for (++SI; SI != SE; ++SI) {
 795         SUCC = *SI;
 796         // Handle self loop.
 797         if (SUCC != MBB)
 798           availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
 799       }
 800     } else if (! CSRUsed[MBB].empty()) {
 801       // Take care of uses in return blocks (which have no successors).
 802       availOutSucc = UsedCSRegs;
 803     }
 804     // CSRRestore[MBB] = (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc
 805     CSRRestore[MBB] = (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
 806
 807     // Remove the CSRs that are restored in the return blocks.
 808     // Lest this be confusing, note that:
 809     // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks.
 810     if (! CSRRestore[MBB].empty() && ! CSRSave[EntryBlock].empty())
 811       CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
 812
 813     // Move restores inside loops to the exits of the outermost (top level)
 814     // containing loops.
 815     std::vector<MachineBasicBlock*> saveBlocks;
 816     moveRestoresOutOfLoops(Fn, MBB, saveBlocks);
 817
 818     // Add saves of CSRs restored in join point MBBs to the ends
 819     // of any pred blocks that flow into MBB from regions that
 820     // have no uses of MBB's CSRs.
 821     addSavesForRJoinBlocks(Fn, saveBlocks);
 822
 823 #ifndef NDEBUG
 824     if (! CSRRestore[MBB].empty())
 825       DOUT << "RESTORE[" << getBasicBlockName(MBB) << "] = "
 826            << stringifyCSRegSet(CSRRestore[MBB], Fn) << "\n";
 827 #endif
 828   }
 829
 830 #ifndef NDEBUG
 831   DOUT << "-----------------------------------------------------------\n";
 832   DOUT << "Final SAVE, RESTORE:\n";
 833   DOUT << "-----------------------------------------------------------\n";
 834   for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
 835        MBB != E; ++MBB) {
 836     if (! CSRSave[MBB].empty()) {
 837       DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
 838            << stringifyCSRegSet(CSRSave[MBB], Fn);
 839       if (CSRRestore[MBB].empty())
 840         DOUT << "\n";
 841     }
 842     if (! CSRRestore[MBB].empty()) {
 843       if (! CSRSave[MBB].empty())
 844         DOUT << "    ";
 845       DOUT << "RESTORE[" << getBasicBlockName(MBB) << "] = "
 846            << stringifyCSRegSet(CSRRestore[MBB], Fn) << "\n";
 847     }
 848   }
 849 #endif
 850 }
 851
 852 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
 853 /// registers.  Also calculate the MaxCallFrameSize and HasCalls variables for
 854 /// the function's frame information and eliminates call frame pseudo
 855 /// instructions.
 856 ///
 857 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
 858   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 859   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
 860
 861   // Get the callee saved register list...
 862   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(&Fn);
 863
 864   // Get the function call frame set-up and tear-down instruction opcode
 865   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
 866   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
 867
 868   // These are used to keep track the callee-save area. Initialize them.
 869   MinCSFrameIndex = INT_MAX;
 870   MaxCSFrameIndex = 0;
 871
 872   // Early exit for targets which have no callee saved registers and no call
 873   // frame setup/destroy pseudo instructions.
 874   if ((CSRegs == 0 || CSRegs[0] == 0) &&
 875       FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
 876     return;
 877
 878   unsigned MaxCallFrameSize = 0;
 879   bool HasCalls = false;
 880
 881   std::vector<MachineBasicBlock::iterator> FrameSDOps;
 882   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
 883     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 884       if (I->getOpcode() == FrameSetupOpcode ||
 885           I->getOpcode() == FrameDestroyOpcode) {
 886         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
 887                " instructions should have a single immediate argument!");
 888         unsigned Size = I->getOperand(0).getImm();
 889         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
 890         HasCalls = true;
 891         FrameSDOps.push_back(I);
 892       }
 893
 894   MachineFrameInfo *FFI = Fn.getFrameInfo();
 895   FFI->setHasCalls(HasCalls);
 896   FFI->setMaxCallFrameSize(MaxCallFrameSize);
 897
 898   for (unsigned i = 0, e = FrameSDOps.size(); i != e; ++i) {
 899     MachineBasicBlock::iterator I = FrameSDOps[i];
 900     // If call frames are not being included as part of the stack frame,
 901     // and there is no dynamic allocation (therefore referencing frame slots
 902     // off sp), leave the pseudo ops alone. We'll eliminate them later.
 903     if (RegInfo->hasReservedCallFrame(Fn) || RegInfo->hasFP(Fn))
 904       RegInfo->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
 905   }
 906
 907   // Now figure out which *callee saved* registers are modified by the current
 908   // function, thus needing to be saved and restored in the prolog/epilog.
 909   //
 910   const TargetRegisterClass* const *CSRegClasses =
 911     RegInfo->getCalleeSavedRegClasses(&Fn);
 912   std::vector<CalleeSavedInfo> CSI;
 913   for (unsigned i = 0; CSRegs[i]; ++i) {
 914     unsigned Reg = CSRegs[i];
 915     if (Fn.getRegInfo().isPhysRegUsed(Reg)) {
 916         // If the reg is modified, save it!
 917       CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
 918     } else {
 919       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 920            *AliasSet; ++AliasSet) {  // Check alias registers too.
 921         if (Fn.getRegInfo().isPhysRegUsed(*AliasSet)) {
 922           CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
 923           break;
 924         }
 925       }
 926     }
 927   }
 928
 929   if (CSI.empty())
 930     return;   // Early exit if no callee saved registers are modified!
 931
 932   unsigned NumFixedSpillSlots;
 933   const std::pair<unsigned,int> *FixedSpillSlots =
 934     TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
 935
 936   // Now that we know which registers need to be saved and restored, allocate
 937   // stack slots for them.
 938   for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 939     unsigned Reg = CSI[i].getReg();
 940     const TargetRegisterClass *RC = CSI[i].getRegClass();
 941
 942     // Check to see if this physreg must be spilled to a particular stack slot
 943     // on this target.
 944     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
 945     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
 946            FixedSlot->first != Reg)
 947       ++FixedSlot;
 948
 949     int FrameIdx;
 950     if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) {
 951       // Nope, just spill it anywhere convenient.
 952       unsigned Align = RC->getAlignment();
 953       unsigned StackAlign = TFI->getStackAlignment();
 954       // We may not be able to sastify the desired alignment specification of
 955       // the TargetRegisterClass if the stack alignment is smaller.
 956       // Use the min.
 957       Align = std::min(Align, StackAlign);
 958       FrameIdx = FFI->CreateStackObject(RC->getSize(), Align);
 959       if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
 960       if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
 961     } else {
 962       // Spill it to the stack where we must.
 963       FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
 964     }
 965     CSI[i].setFrameIdx(FrameIdx);
 966   }
 967
 968   FFI->setCalleeSavedInfo(CSI);
 969 }
 970
 971 /// insertCSRSpillsAndRestores - Insert spill and restore code for
 972 /// callee saved registers used in the function, handling shrink wrapping.
 973 ///
 974 void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) {
 975   // Get callee saved register information.
 976   MachineFrameInfo *FFI = Fn.getFrameInfo();
 977   const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo();
 978
 979   // Early exit if no callee saved registers are modified!
 980   if (CSI.empty())
 981     return;
 982
 983   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 984   MachineBasicBlock::iterator I;
 985   std::vector<CalleeSavedInfo> blockCSI;
 986
 987 #ifndef NDEBUG
 988   DOUT << "Inserting spill/restore code for CSRs in function "
 989        << Fn.getFunction()->getName() << "\n";
 990 #endif
 991
 992   // Insert spills.
 993   for (CSRegBlockMap::iterator
 994          BI = CSRSave.begin(), BE = CSRSave.end(); BI != BE; ++BI) {
 995     MachineBasicBlock* MBB = BI->first;
 996     CSRegSet save = BI->second;
 997
 998     if (save.empty())
 999       continue;
1000
1001     if (! ShrinkWrapThisFunction) {
1002       // Spill using target interface.
1003       I = MBB->begin();
1004       if (!TII.spillCalleeSavedRegisters(*MBB, I, CSI)) {
1005         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
1006           // Add the callee-saved register as live-in. It's killed at the spill.
1007           MBB->addLiveIn(CSI[i].getReg());
1008
1009           // Insert the spill to the stack frame.
1010           TII.storeRegToStackSlot(*MBB, I, CSI[i].getReg(), true,
1011                                   CSI[i].getFrameIdx(), CSI[i].getRegClass());
1012         }
1013       }
1014     } else {
1015 #ifndef NDEBUG
1016       DOUT << "CSRSave[" << getBasicBlockName(MBB) << "] = "
1017            << stringifyCSRegSet(save, Fn) << "\n";
1018 #endif
1019
1020       blockCSI.clear();
1021       for (CSRegSet::iterator RI = save.begin(),
1022              RE = save.end(); RI != RE; ++RI) {
1023         blockCSI.push_back(CSI[*RI]);
1024       }
1025       assert(blockCSI.size() > 0 &&
1026              "Could not collect callee saved register info");
1027
1028       // If MBB has no uses of CSRs being saved, this means saves
1029       // must be inserted at the _end_.
1030       if (! MBB->empty() && ! CSRUsed[MBB].intersects(save)) {
1031         I = MBB->end();
1032         --I;
1033         if (I->getDesc().isCall()) {
1034           ++I;
1035         } else {
1036           MachineBasicBlock::iterator I2 = I;
1037           while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
1038             I = I2;
1039         }
1040       } else {
1041         I = MBB->begin();
1042       }
1043
1044       // When shrink wrapping, use stack slot stores/loads.
1045       for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
1046         // Add the callee-saved register as live-in.
1047         // It's killed at the spill.
1048         MBB->addLiveIn(blockCSI[i].getReg());
1049
1050         // Insert the spill to the stack frame.
1051         TII.storeRegToStackSlot(*MBB, I, blockCSI[i].getReg(),
1052                                 true,
1053                                 blockCSI[i].getFrameIdx(),
1054                                 blockCSI[i].getRegClass());
1055       }
1056     }
1057   }
1058   // Use CSRRestore to add code to restore the callee-saved registers in
1059   // each block.
1060   for (CSRegBlockMap::iterator
1061          BI = CSRRestore.begin(), BE = CSRRestore.end(); BI != BE; ++BI) {
1062     MachineBasicBlock* MBB = BI->first;
1063     CSRegSet restore = BI->second;
1064
1065     if (restore.empty())
1066       continue;
1067     if (! ShrinkWrapThisFunction) {
1068       // Restore using target interface.
1069       I = MBB->end(); --I;
1070
1071       // Skip over all terminator instructions, which are part of the return
1072       // sequence.
1073       MachineBasicBlock::iterator I2 = I;
1074       while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
1075         I = I2;
1076
1077       bool AtStart = I == MBB->begin();
1078       MachineBasicBlock::iterator BeforeI = I;
1079       if (!AtStart)
1080         --BeforeI;
1081
1082       // Restore all registers immediately before the return and any
1083       // terminators that preceed it.
1084       if (!TII.restoreCalleeSavedRegisters(*MBB, I, CSI)) {
1085         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
1086           TII.loadRegFromStackSlot(*MBB, I, CSI[i].getReg(),
1087                                    CSI[i].getFrameIdx(),
1088                                    CSI[i].getRegClass());
1089           assert(I != MBB->begin() &&
1090                  "loadRegFromStackSlot didn't insert any code!");
1091           // Insert in reverse order.  loadRegFromStackSlot can insert
1092           // multiple instructions.
1093           if (AtStart)
1094             I = MBB->begin();
1095           else {
1096             I = BeforeI;
1097             ++I;
1098           }
1099         }
1100       }
1101     } else {
1102 #ifndef NDEBUG
1103       DOUT << "CSRRestore[" << getBasicBlockName(MBB) << "] = "
1104            << stringifyCSRegSet(restore, Fn) << "\n";
1105 #endif
1106
1107       blockCSI.clear();
1108       for (CSRegSet::iterator RI = restore.begin(),
1109              RE = restore.end(); RI != RE; ++RI) {
1110         blockCSI.push_back(CSI[*RI]);
1111       }
1112       assert(blockCSI.size() > 0 &&
1113              "Could not find callee saved register info");
1114
1115       // If MBB uses no CSRs but has restores, this means
1116       // it must have restores inserted at the _beginning_.
1117       // N.B. -- not necessary if edge splitting done.
1118       if (MBB->empty() || ! CSRUsed[MBB].intersects(restore)) {
1119         I = MBB->begin();
1120       } else {
1121         I = MBB->end();
1122         --I;
1123
1124         // EXP iff spill/restore implemented with push/pop:
1125         // append restore to block unless it ends in a
1126         // barrier terminator instruction.
1127
1128         // Skip over all terminator instructions, which are part of the
1129         // return sequence.
1130         if (I->getDesc().isCall()) {
1131           ++I;
1132         } else {
1133           MachineBasicBlock::iterator I2 = I;
1134           while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
1135             I = I2;
1136         }
1137       }
1138
1139       bool AtStart = I == MBB->begin();
1140       MachineBasicBlock::iterator BeforeI = I;
1141       if (!AtStart)
1142         --BeforeI;
1143
1144 #ifndef NDEBUG
1145       if (! MBB->empty() && ! CSRUsed[MBB].intersects(restore)) {
1146         MachineInstr* MI = BeforeI;
1147         DOUT << "adding restore after ";
1148         DEBUG(MI->dump());
1149       } else {
1150         DOUT << "adding restore to beginning of "
1151              << getBasicBlockName(MBB) << "\n";
1152       }
1153 #endif
1154
1155       // Restore all registers immediately before the return and any
1156       // terminators that preceed it.
1157       for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
1158         TII.loadRegFromStackSlot(*MBB, I, blockCSI[i].getReg(),
1159                                  blockCSI[i].getFrameIdx(),
1160                                  blockCSI[i].getRegClass());
1161         assert(I != MBB->begin() &&
1162                "loadRegFromStackSlot didn't insert any code!");
1163         // Insert in reverse order.  loadRegFromStackSlot can insert
1164         // multiple instructions.
1165         if (AtStart)
1166           I = MBB->begin();
1167         else {
1168           I = BeforeI;
1169           ++I;
1170         }
1171       }
1172     }
1173   }
1174 }
1175
1176 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
1177 static inline void
1178 AdjustStackOffset(MachineFrameInfo *FFI, int FrameIdx,
1179                   bool StackGrowsDown, int64_t &Offset,
1180                   unsigned &MaxAlign) {
1181   // If stack grows down, we need to add size of find the lowest address of the
1182   // object.
1183   if (StackGrowsDown)
1184     Offset += FFI->getObjectSize(FrameIdx);
1185
1186   unsigned Align = FFI->getObjectAlignment(FrameIdx);
1187
1188   // If the alignment of this object is greater than that of the stack, then
1189   // increase the stack alignment to match.
1190   MaxAlign = std::max(MaxAlign, Align);
1191
1192   // Adjust to alignment boundary.
1193   Offset = (Offset + Align - 1) / Align * Align;
1194
1195   if (StackGrowsDown) {
1196     FFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
1197   } else {
1198     FFI->setObjectOffset(FrameIdx, Offset);
1199     Offset += FFI->getObjectSize(FrameIdx);
1200   }
1201 }
1202
1203 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
1204 /// abstract stack objects.
1205 ///
1206 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
1207   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
1208
1209   bool StackGrowsDown =
1210     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
1211
1212   // Loop over all of the stack objects, assigning sequential addresses...
1213   MachineFrameInfo *FFI = Fn.getFrameInfo();
1214
1215   unsigned MaxAlign = FFI->getMaxAlignment();
1216
1217   // Start at the beginning of the local area.
1218   // The Offset is the distance from the stack top in the direction
1219   // of stack growth -- so it's always nonnegative.
1220   int64_t Offset = TFI.getOffsetOfLocalArea();
1221   if (StackGrowsDown)
1222     Offset = -Offset;
1223   assert(Offset >= 0
1224          && "Local area offset should be in direction of stack growth");
1225
1226   // If there are fixed sized objects that are preallocated in the local area,
1227   // non-fixed objects can't be allocated right at the start of local area.
1228   // We currently don't support filling in holes in between fixed sized
1229   // objects, so we adjust 'Offset' to point to the end of last fixed sized
1230   // preallocated object.
1231   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
1232     int64_t FixedOff;
1233     if (StackGrowsDown) {
1234       // The maximum distance from the stack pointer is at lower address of
1235       // the object -- which is given by offset. For down growing stack
1236       // the offset is negative, so we negate the offset to get the distance.
1237       FixedOff = -FFI->getObjectOffset(i);
1238     } else {
1239       // The maximum distance from the start pointer is at the upper
1240       // address of the object.
1241       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
1242     }
1243     if (FixedOff > Offset) Offset = FixedOff;
1244   }
1245
1246   // First assign frame offsets to stack objects that are used to spill
1247   // callee saved registers.
1248   if (StackGrowsDown) {
1249     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
1250       // If stack grows down, we need to add size of find the lowest
1251       // address of the object.
1252       Offset += FFI->getObjectSize(i);
1253
1254       unsigned Align = FFI->getObjectAlignment(i);
1255       // If the alignment of this object is greater than that of the stack,
1256       // then increase the stack alignment to match.
1257       MaxAlign = std::max(MaxAlign, Align);
1258       // Adjust to alignment boundary
1259       Offset = (Offset+Align-1)/Align*Align;
1260
1261       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
1262     }
1263   } else {
1264     int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex;
1265     for (int i = MaxCSFI; i >= MinCSFI ; --i) {
1266       unsigned Align = FFI->getObjectAlignment(i);
1267       // If the alignment of this object is greater than that of the stack,
1268       // then increase the stack alignment to match.
1269       MaxAlign = std::max(MaxAlign, Align);
1270       // Adjust to alignment boundary
1271       Offset = (Offset+Align-1)/Align*Align;
1272
1273       FFI->setObjectOffset(i, Offset);
1274       Offset += FFI->getObjectSize(i);
1275     }
1276   }
1277
1278   // Make sure the special register scavenging spill slot is closest to the
1279   // frame pointer if a frame pointer is required.
1280   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
1281   if (RS && RegInfo->hasFP(Fn)) {
1282     int SFI = RS->getScavengingFrameIndex();
1283     if (SFI >= 0)
1284       AdjustStackOffset(FFI, SFI, StackGrowsDown, Offset, MaxAlign);
1285   }
1286
1287   // Make sure that the stack protector comes before the local variables on the
1288   // stack.
1289   if (FFI->getStackProtectorIndex() >= 0)
1290     AdjustStackOffset(FFI, FFI->getStackProtectorIndex(), StackGrowsDown,
1291                       Offset, MaxAlign);
1292
1293   // Then assign frame offsets to stack objects that are not used to spill
1294   // callee saved registers.
1295   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
1296     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
1297       continue;
1298     if (RS && (int)i == RS->getScavengingFrameIndex())
1299       continue;
1300     if (FFI->isDeadObjectIndex(i))
1301       continue;
1302     if (FFI->getStackProtectorIndex() == (int)i)
1303       continue;
1304
1305     AdjustStackOffset(FFI, i, StackGrowsDown, Offset, MaxAlign);
1306   }
1307
1308   // Make sure the special register scavenging spill slot is closest to the
1309   // stack pointer.
1310   if (RS && !RegInfo->hasFP(Fn)) {
1311     int SFI = RS->getScavengingFrameIndex();
1312     if (SFI >= 0)
1313       AdjustStackOffset(FFI, SFI, StackGrowsDown, Offset, MaxAlign);
1314   }
1315
1316   // Round up the size to a multiple of the alignment, but only if there are
1317   // calls or alloca's in the function.  This ensures that any calls to
1318   // subroutines have their stack frames suitable aligned.
1319   // Also do this if we need runtime alignment of the stack.  In this case
1320   // offsets will be relative to SP not FP; round up the stack size so this
1321   // works.
1322   if (!RegInfo->targetHandlesStackFrameRounding() &&
1323       (FFI->hasCalls() || FFI->hasVarSizedObjects() ||
1324        (RegInfo->needsStackRealignment(Fn) &&
1325         FFI->getObjectIndexEnd() != 0))) {
1326     // If we have reserved argument space for call sites in the function
1327     // immediately on entry to the current function, count it as part of the
1328     // overall stack size.
1329     if (RegInfo->hasReservedCallFrame(Fn))
1330       Offset += FFI->getMaxCallFrameSize();
1331
1332     unsigned AlignMask = std::max(TFI.getStackAlignment(),MaxAlign) - 1;
1333     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
1334   }
1335
1336   // Update frame info to pretend that this is part of the stack...
1337   FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea());
1338
1339   // Remember the required stack alignment in case targets need it to perform
1340   // dynamic stack alignment.
1341   FFI->setMaxAlignment(MaxAlign);
1342 }
1343
1344
1345 /// insertPrologEpilogCode - Scan the function for modified callee saved
1346 /// registers, insert spill code for these callee saved registers, then add
1347 /// prolog and epilog code to the function.
1348 ///
1349 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
1350   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
1351
1352   // Add prologue to the function...
1353   TRI->emitPrologue(Fn);
1354
1355   // Add epilogue to restore the callee-save registers in each exiting block
1356   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
1357     // If last instruction is a return instruction, add an epilogue
1358     if (!I->empty() && I->back().getDesc().isReturn())
1359       TRI->emitEpilogue(Fn, *I);
1360   }
1361 }
1362
1363
1364 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
1365 /// register references and actual offsets.
1366 ///
1367 void PEI::replaceFrameIndices(MachineFunction &Fn) {
1368   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
1369
1370   const TargetMachine &TM = Fn.getTarget();
1371   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
1372   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
1373   const TargetFrameInfo *TFI = TM.getFrameInfo();
1374   bool StackGrowsDown =
1375     TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
1376   int FrameSetupOpcode   = TRI.getCallFrameSetupOpcode();
1377   int FrameDestroyOpcode = TRI.getCallFrameDestroyOpcode();
1378
1379   for (MachineFunction::iterator BB = Fn.begin(),
1380          E = Fn.end(); BB != E; ++BB) {
1381     int SPAdj = 0;  // SP offset due to call frame setup / destroy.
1382     if (RS) RS->enterBasicBlock(BB);
1383
1384     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
1385       if (I->getOpcode() == TargetInstrInfo::DECLARE) {
1386         // Ignore it.
1387         ++I;
1388         continue;
1389       }
1390
1391       if (I->getOpcode() == FrameSetupOpcode ||
1392           I->getOpcode() == FrameDestroyOpcode) {
1393         // Remember how much SP has been adjusted to create the call
1394         // frame.
1395         int Size = I->getOperand(0).getImm();
1396
1397         if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
1398             (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
1399           Size = -Size;
1400
1401         SPAdj += Size;
1402
1403         MachineBasicBlock::iterator PrevI = BB->end();
1404         if (I != BB->begin()) PrevI = prior(I);
1405         TRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
1406
1407         // Visit the instructions created by eliminateCallFramePseudoInstr().
1408         if (PrevI == BB->end())
1409           I = BB->begin();     // The replaced instr was the first in the block.
1410         else
1411           I = next(PrevI);
1412         continue;
1413       }
1414
1415       MachineInstr *MI = I;
1416       bool DoIncr = true;
1417       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
1418         if (MI->getOperand(i).isFI()) {
1419           // Some instructions (e.g. inline asm instructions) can have
1420           // multiple frame indices and/or cause eliminateFrameIndex
1421           // to insert more than one instruction. We need the register
1422           // scavenger to go through all of these instructions so that
1423           // it can update its register information. We keep the
1424           // iterator at the point before insertion so that we can
1425           // revisit them in full.
1426           bool AtBeginning = (I == BB->begin());
1427           if (!AtBeginning) --I;
1428
1429           // If this instruction has a FrameIndex operand, we need to
1430           // use that target machine register info object to eliminate
1431           // it.
1432
1433           TRI.eliminateFrameIndex(MI, SPAdj, RS);
1434
1435           // Reset the iterator if we were at the beginning of the BB.
1436           if (AtBeginning) {
1437             I = BB->begin();
1438             DoIncr = false;
1439           }
1440
1441           MI = 0;
1442           break;
1443         }
1444
1445       if (DoIncr && I != BB->end()) ++I;
1446
1447       // Update register states.
1448       if (RS && MI) RS->forward(MI);
1449     }
1450
1451     assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?");
1452   }
1453 }