Restructure PEI code:

- moved shrink wrapping code from PrologEpilogInserter.cpp to
  new file ShrinkWrapping.cpp.

- moved PEI pass definition into new shared header PEI.h.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71588 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 1375 insertions, 1307 deletions

diff --git a/lib/CodeGen/PEI.h b/lib/CodeGen/PEI.h
new file mode 100644
index 0000000000..c158dd8ac2
--- /dev/null
+++ b/lib/CodeGen/PEI.h
@@ -0,0 +1,167 @@
+//===-- PrologEpilogInserter.h - Prolog/Epilog code insertion -*- C++ -* --===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass is responsible for finalizing the functions frame layout, saving
+// callee saved registers, and for emitting prolog & epilog code for the
+// function.
+//
+// This pass must be run after register allocation.  After this pass is
+// executed, it is illegal to construct MO_FrameIndex operands.
+//
+// This pass also implements a shrink wrapping variant of prolog/epilog
+// insertion.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PEI_H
+#define LLVM_CODEGEN_PEI_H
+
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/ADT/SparseBitVector.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace llvm {
+  class RegScavenger;
+  class MachineBasicBlock;
+
+  class PEI : public MachineFunctionPass {
+  public:
+    static char ID;
+    PEI() : MachineFunctionPass(&ID) {}
+
+    const char *getPassName() const {
+      return "Prolog/Epilog Insertion & Frame Finalization";
+    }
+
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+    /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
+    /// frame indexes with appropriate references.
+    ///
+    bool runOnMachineFunction(MachineFunction &Fn);
+
+  private:
+    RegScavenger *RS;
+
+    // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
+    // stack frame indexes.
+    unsigned MinCSFrameIndex, MaxCSFrameIndex;
+
+    // Analysis info for spill/restore placement.
+    // "CSR": "callee saved register".
+
+    // CSRegSet contains indices into the Callee Saved Register Info
+    // vector built by calculateCalleeSavedRegisters() and accessed
+    // via MF.getFrameInfo()->getCalleeSavedInfo().
+    typedef SparseBitVector<> CSRegSet;
+
+    // CSRegBlockMap maps MachineBasicBlocks to sets of callee
+    // saved register indices.
+    typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap;
+
+    // Set and maps for computing CSR spill/restore placement:
+    //  used in function (UsedCSRegs)
+    //  used in a basic block (CSRUsed)
+    //  anticipatable in a basic block (Antic{In,Out})
+    //  available in a basic block (Avail{In,Out})
+    //  to be spilled at the entry to a basic block (CSRSave)
+    //  to be restored at the end of a basic block (CSRRestore)
+    CSRegSet UsedCSRegs;
+    CSRegBlockMap CSRUsed;
+    CSRegBlockMap AnticIn, AnticOut;
+    CSRegBlockMap AvailIn, AvailOut;
+    CSRegBlockMap CSRSave;
+    CSRegBlockMap CSRRestore;
+
+    // Entry and return blocks of the current function.
+    MachineBasicBlock* EntryBlock;
+    SmallVector<MachineBasicBlock*, 4> ReturnBlocks;
+
+    // Map of MBBs to top level MachineLoops.
+    DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops;
+
+    // Flag to control shrink wrapping per-function:
+    // may choose to skip shrink wrapping for certain
+    // functions.
+    bool ShrinkWrapThisFunction;
+
+#ifndef NDEBUG
+    // Machine function handle.
+    MachineFunction* MF;
+
+    // Flag indicating that the current function
+    // has at least one "short" path in the machine
+    // CFG from the entry block to an exit block.
+    bool HasFastExitPath;
+#endif
+
+    bool calculateSets(MachineFunction &Fn);
+    bool calcAnticInOut(MachineBasicBlock* MBB);
+    bool calcAvailInOut(MachineBasicBlock* MBB);
+    void calculateAnticAvail(MachineFunction &Fn);
+    bool addUsesForMEMERegion(MachineBasicBlock* MBB,
+                              SmallVector<MachineBasicBlock*, 4>& blks);
+    bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks);
+    bool calcSpillPlacements(MachineBasicBlock* MBB,
+                             SmallVector<MachineBasicBlock*, 4> &blks,
+                             CSRegBlockMap &prevSpills);
+    bool calcRestorePlacements(MachineBasicBlock* MBB,
+                               SmallVector<MachineBasicBlock*, 4> &blks,
+                               CSRegBlockMap &prevRestores);
+    void placeSpillsAndRestores(MachineFunction &Fn);
+    void placeCSRSpillsAndRestores(MachineFunction &Fn);
+    void calculateCalleeSavedRegisters(MachineFunction &Fn);
+    void insertCSRSpillsAndRestores(MachineFunction &Fn);
+    void calculateFrameObjectOffsets(MachineFunction &Fn);
+    void replaceFrameIndices(MachineFunction &Fn);
+    void insertPrologEpilogCode(MachineFunction &Fn);
+
+    // Initialize DFA sets, called before iterations.
+    void clearAnticAvailSets();
+    // Clear all sets constructed by shrink wrapping.
+    void clearAllSets();
+
+    // Initialize all shrink wrapping data.
+    void initShrinkWrappingInfo();
+
+    // Convienences for dealing with machine loops.
+    MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP);
+    MachineLoop* getTopLevelLoopParent(MachineLoop *LP);
+
+    // Propgate CSRs used in MBB to all MBBs of loop LP.
+    void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
+
+    // Convenience for recognizing return blocks.
+    bool isReturnBlock(MachineBasicBlock* MBB);
+
+#ifndef NDEBUG
+    // Debugging methods.
+
+    // Mark this function as having fast exit paths.
+    void findFastExitPath();
+
+    // Verify placement of spills/restores.
+    void verifySpillRestorePlacement();
+
+    std::string getBasicBlockName(const MachineBasicBlock* MBB);
+    std::string stringifyCSRegSet(const CSRegSet& s);
+    void dumpSet(const CSRegSet& s);
+    void dumpUsed(MachineBasicBlock* MBB);
+    void dumpAllUsed();
+    void dumpSets(MachineBasicBlock* MBB);
+    void dumpSets1(MachineBasicBlock* MBB);
+    void dumpAllSets();
+    void dumpSRSets();
+#endif
+
+  };
+} // End llvm namespace
+#endif
diff --git a/lib/CodeGen/PrologEpilogInserter.cpp b/lib/CodeGen/PrologEpilogInserter.cpp
index 396254fb15..6f95d1c3cf 100644
--- a/lib/CodeGen/PrologEpilogInserter.cpp
+++ b/lib/CodeGen/PrologEpilogInserter.cpp
@@ -14,35 +14,14 @@
 // This pass must be run after register allocation.  After this pass is
 // executed, it is illegal to construct MO_FrameIndex operands.
 //
-// This pass implements a shrink wrapping variant of prolog/epilog insertion:
-// - Places callee saved register (CSR) spills and restores in the CFG to
-//   tightly surround uses so that execution paths that do not use CSRs do not
-//   pay the spill/restore penalty.
-//
-// - Avoiding placment of spills/restores in loops: if a CSR is used inside a
-//   loop(nest), the spills are placed in the loop preheader, and restores are
-//   placed in the loop exit nodes (the successors of the loop _exiting_ nodes).
-//
-// - Covering paths without CSR uses: e.g. if a restore is placed in a join
-//   block, a matching spill is added to the end of all immediate predecessor
-//   blocks that are not reached by a spill. Similarly for saves placed in
-//   branch blocks.
-//
-// Shrink wrapping uses an analysis similar to the one in GVNPRE to determine
-// which basic blocks require callee-saved register save/restore code.
-//
-// This pass uses MachineDominators and MachineLoopInfo. Loop information
-// is used to prevent shrink wrapping of callee-saved register save/restore
-// code into loops.
+// This pass provides an optional shrink wrapping variant of prolog/epilog
+// insertion, enabled via --shrink-wrap. See ShrinkWrapping.cpp.
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "shrink-wrap"
-
-#include "llvm/CodeGen/Passes.h"
+#include "PEI.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
@@ -52,1009 +31,91 @@
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetFrameInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/ADT/SparseBitVector.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
-#include "llvm/Support/Debug.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/Statistic.h"
 #include <climits>
-#include <sstream>
 
 using namespace llvm;
 
-STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");
-
-// Shrink Wrapping:
-static cl::opt<bool>
-ShrinkWrapping("shrink-wrap",
-               cl::desc("Shrink wrap callee-saved register spills/restores"));
-
-// Shrink wrap only the specified function, a debugging aid.
-static cl::opt<std::string>
-ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
-               cl::desc("Shrink wrap the specified function"),
-               cl::value_desc("funcname"),
-               cl::init(""));
-
-// Debugging level for shrink wrapping.
-enum ShrinkWrapDebugLevel {
-  None, BasicInfo, Iterations, Details
-};
-
-static cl::opt<enum ShrinkWrapDebugLevel>
-ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
-  cl::desc("Print shrink wrapping debugging information"),
-  cl::values(
-    clEnumVal(None      , "disable debug output"),
-    clEnumVal(BasicInfo , "print basic DF sets"),
-    clEnumVal(Iterations, "print SR sets for each iteration"),
-    clEnumVal(Details   , "print all DF sets"),
-    clEnumValEnd));
-
-
-namespace {
-  struct VISIBILITY_HIDDEN PEI : public MachineFunctionPass {
-    static char ID;
-    PEI() : MachineFunctionPass(&ID) {}
-
-    const char *getPassName() const {
-      return "Prolog/Epilog Insertion & Frame Finalization";
-    }
-
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesCFG();
-      if (ShrinkWrapping || ShrinkWrapFunc != "") {
-        AU.addRequired<MachineLoopInfo>();
-        AU.addRequired<MachineDominatorTree>();
-      }
-      AU.addPreserved<MachineLoopInfo>();
-      AU.addPreserved<MachineDominatorTree>();
-      MachineFunctionPass::getAnalysisUsage(AU);
-    }
-
-    /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
-    /// frame indexes with appropriate references.
-    ///
-    bool runOnMachineFunction(MachineFunction &Fn) {
-      const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
-      RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
-
-      DEBUG(MF = &Fn);
-
-      // Get MachineModuleInfo so that we can track the construction of the
-      // frame.
-      if (MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>())
-        Fn.getFrameInfo()->setMachineModuleInfo(MMI);
-
-      // Allow the target machine to make some adjustments to the function
-      // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
-      TRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
-
-      // Scan the function for modified callee saved registers and insert spill
-      // code for any callee saved registers that are modified.  Also calculate
-      // the MaxCallFrameSize and HasCalls variables for the function's frame
-      // information and eliminates call frame pseudo instructions.
-      calculateCalleeSavedRegisters(Fn);
-
-      // Determine placement of CSR spill/restore code:
-      //  - with shrink wrapping, place spills and restores to tightly
-      //    enclose regions in the Machine CFG of the function where
-      //    they are used. Without shrink wrapping
-      //  - default (no shrink wrapping), place all spills in the
-      //    entry block, all restores in return blocks.
-      placeCSRSpillsAndRestores(Fn);
-
-      // Add the code to save and restore the callee saved registers
-      insertCSRSpillsAndRestores(Fn);
-
-      // Allow the target machine to make final modifications to the function
-      // before the frame layout is finalized.
-      TRI->processFunctionBeforeFrameFinalized(Fn);
-
-      // Calculate actual frame offsets for all abstract stack objects...
-      calculateFrameObjectOffsets(Fn);
-
-      // Add prolog and epilog code to the function.  This function is required
-      // to align the stack frame as necessary for any stack variables or
-      // called functions.  Because of this, calculateCalleeSavedRegisters
-      // must be called before this function in order to set the HasCalls
-      // and MaxCallFrameSize variables.
-      insertPrologEpilogCode(Fn);
-
-      // Replace all MO_FrameIndex operands with physical register references
-      // and actual offsets.
-      //
-      replaceFrameIndices(Fn);
-
-      delete RS;
-      clearAllSets();
-      return true;
-    }
-
-  private:
-    RegScavenger *RS;
-
-    // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
-    // stack frame indexes.
-    unsigned MinCSFrameIndex, MaxCSFrameIndex;
-
-    // Analysis info for spill/restore placement.
-    // "CSR": "callee saved register".
-
-    // CSRegSet contains indices into the Callee Saved Register Info
-    // vector built by calculateCalleeSavedRegisters() and accessed
-    // via MF.getFrameInfo()->getCalleeSavedInfo().
-    typedef SparseBitVector<> CSRegSet;
-
-    // CSRegBlockMap maps MachineBasicBlocks to sets of callee
-    // saved register indices.
-    typedef DenseMap<MachineBasicBlock*, CSRegSet> CSRegBlockMap;
-
-    // Set and maps for computing CSR spill/restore placement:
-    //  used in function (UsedCSRegs)
-    //  used in a basic block (CSRUsed)
-    //  anticipatable in a basic block (Antic{In,Out})
-    //  available in a basic block (Avail{In,Out})
-    //  to be spilled at the entry to a basic block (CSRSave)
-    //  to be restored at the end of a basic block (CSRRestore)
-    CSRegSet UsedCSRegs;
-    CSRegBlockMap CSRUsed;
-    CSRegBlockMap AnticIn, AnticOut;
-    CSRegBlockMap AvailIn, AvailOut;
-    CSRegBlockMap CSRSave;
-    CSRegBlockMap CSRRestore;
-
-    // Entry and return blocks of the current function.
-    MachineBasicBlock* EntryBlock;
-    SmallVector<MachineBasicBlock*, 4> ReturnBlocks;
-
-    // Map of MBBs to top level MachineLoops.
-    DenseMap<MachineBasicBlock*, MachineLoop*> TLLoops;
-
-    // Flag to control shrink wrapping per-function:
-    // may choose to skip shrink wrapping for certain
-    // functions.
-    bool ShrinkWrapThisFunction;
-
-#ifndef NDEBUG
-    // Machine function handle.
-    MachineFunction* MF;
-
-    // Flag indicating that the current function
-    // has at least one "short" path in the machine
-    // CFG from the entry block to an exit block.
-    bool HasFastExitPath;
-#endif
-
-    bool calculateSets(MachineFunction &Fn);
-    bool calcAnticInOut(MachineBasicBlock* MBB);
-    bool calcAvailInOut(MachineBasicBlock* MBB);
-    void calculateAnticAvail(MachineFunction &Fn);
-    bool addUsesForMEMERegion(MachineBasicBlock* MBB,
-                              SmallVector<MachineBasicBlock*, 4>& blks);
-    bool addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks);
-    bool calcSpillPlacements(MachineBasicBlock* MBB,
-                             SmallVector<MachineBasicBlock*, 4> &blks,
-                             CSRegBlockMap &prevSpills);
-    bool calcRestorePlacements(MachineBasicBlock* MBB,
-                               SmallVector<MachineBasicBlock*, 4> &blks,
-                               CSRegBlockMap &prevRestores);
-    void placeSpillsAndRestores(MachineFunction &Fn);
-    void placeCSRSpillsAndRestores(MachineFunction &Fn);
-    void calculateCalleeSavedRegisters(MachineFunction &Fn);
-    void insertCSRSpillsAndRestores(MachineFunction &Fn);
-    void calculateFrameObjectOffsets(MachineFunction &Fn);
-    void replaceFrameIndices(MachineFunction &Fn);
-    void insertPrologEpilogCode(MachineFunction &Fn);
-
-    // Initialize DFA sets, called before iterations.
-    void clearAnticAvailSets();
-    // Clear all sets constructed by shrink wrapping.
-    void clearAllSets();
-
-    // Initialize all shrink wrapping data.
-    void initShrinkWrappingInfo();
-
-    // Convienences for dealing with machine loops.
-    MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP) {
-      assert(LP && "Machine loop is NULL.");
-      MachineBasicBlock* PHDR = LP->getLoopPreheader();
-      MachineLoop* PLP = LP->getParentLoop();
-      while (PLP) {
-        PHDR = PLP->getLoopPreheader();
-        PLP = PLP->getParentLoop();
-      }
-      return PHDR;
-    }
-
-    MachineLoop* getTopLevelLoopParent(MachineLoop *LP) {
-      if (LP == 0)
-        return 0;
-      MachineLoop* PLP = LP->getParentLoop();
-      while (PLP) {
-        LP = PLP;
-        PLP = PLP->getParentLoop();
-      }
-      return LP;
-    }
-
-    // Propgate CSRs used in MBB to all MBBs of loop LP.
-    void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
-
-    // Convenience for recognizing return blocks.
-    bool isReturnBlock(MachineBasicBlock* MBB) {
-      return (MBB && !MBB->empty() && MBB->back().getDesc().isReturn());
-    }
-
-#ifndef NDEBUG
-    // Debugging methods.
-
-    // Mark this function as having fast exit paths.
-    void findFastExitPath();
-
-    // Verify placement of spills/restores.
-    void verifySpillRestorePlacement();
-
-    std::string getBasicBlockName(const MachineBasicBlock* MBB);
-    std::string stringifyCSRegSet(const CSRegSet& s);
-    void dumpSet(const CSRegSet& s);
-    void dumpUsed(MachineBasicBlock* MBB);
-    void dumpAllUsed();
-    void dumpSets(MachineBasicBlock* MBB);
-    void dumpSets1(MachineBasicBlock* MBB);
-    void dumpAllSets();
-    void dumpSRSets();
-#endif
-
-  };
-  char PEI::ID = 0;
-}
-
-// Initialize shrink wrapping DFA sets, called before iterations.
-void PEI::clearAnticAvailSets() {
-  AnticIn.clear();
-  AnticOut.clear();
-  AvailIn.clear();
-  AvailOut.clear();
-}
-
-// Clear all sets constructed by shrink wrapping.
-void PEI::clearAllSets() {
-  ReturnBlocks.clear();
-  clearAnticAvailSets();
-  UsedCSRegs.clear();
-  CSRUsed.clear();
-  TLLoops.clear();
-  CSRSave.clear();
-  CSRRestore.clear();
-}
-
-// Initialize all shrink wrapping data.
-void PEI::initShrinkWrappingInfo() {
-  clearAllSets();
-  EntryBlock = 0;
-#ifndef NDEBUG
-  HasFastExitPath = false;
-#endif
-  ShrinkWrapThisFunction = ShrinkWrapping;
-  // DEBUG: enable or disable shrink wrapping for the current function
-  // via --shrink-wrap-func=<funcname>.
-#ifndef NDEBUG
-  if (ShrinkWrapFunc != "") {
-    std::string MFName = MF->getFunction()->getName();
-    ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
-  }
-#endif
-}
+char PEI::ID = 0;
 
+static RegisterPass<PEI>
+X("prologepilog", "Prologue/Epilogue Insertion");
 
 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
 /// prolog and epilog code, and eliminates abstract frame references.
 ///
 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
 
-/// placeCSRSpillsAndRestores - determine which MBBs of the function
-/// need save, restore code for callee-saved registers by doing a DF analysis
-/// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
-/// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
-/// is used to ensure that CSR save/restore code is not placed inside loops.
-/// This function computes the maps of MBBs -> CSRs to spill and restore
-/// in CSRSave, CSRRestore.
-///
-/// If shrink wrapping is not being performed, place all spills in
-/// the entry block, all restores in return blocks. In this case,
-/// CSRSave has a single mapping, CSRRestore has mappings for each
-/// return block.
-///
-void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
-
-  initShrinkWrappingInfo();
-
-  DEBUG(if (ShrinkWrapThisFunction) {
-      DOUT << "Place CSR spills/restores for "
-           << MF->getFunction()->getName() << "\n";
-    });
-
-  if (calculateSets(Fn))
-    placeSpillsAndRestores(Fn);
-}
-
-/// calcAnticInOut - calculate the anticipated in/out reg sets
-/// for the given MBB by looking forward in the MCFG at MBB's
-/// successors.
-///
-bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
-  bool changed = false;
-
-  // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB))
-  SmallVector<MachineBasicBlock*, 4> successors;
-  for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
-         SE = MBB->succ_end(); SI != SE; ++SI) {
-    MachineBasicBlock* SUCC = *SI;
-    if (SUCC != MBB)
-      successors.push_back(SUCC);
-  }
-
-  unsigned i = 0, e = successors.size();
-  if (i != e) {
-    CSRegSet prevAnticOut = AnticOut[MBB];
-    MachineBasicBlock* SUCC = successors[i];
-
-    AnticOut[MBB] = AnticIn[SUCC];
-    for (++i; i != e; ++i) {
-      SUCC = successors[i];
-      AnticOut[MBB] &= AnticIn[SUCC];
-    }
-    if (prevAnticOut != AnticOut[MBB])
-      changed = true;
-  }
-
-  // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]);
-  CSRegSet prevAnticIn = AnticIn[MBB];
-  AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
-  if (prevAnticIn |= AnticIn[MBB])
-    changed = true;
-  return changed;
-}
-
-/// calcAvailInOut - calculate the available in/out reg sets
-/// for the given MBB by looking backward in the MCFG at MBB's
-/// predecessors.
-///
-bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
-  bool changed = false;
-
-  // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB))
-  SmallVector<MachineBasicBlock*, 4> predecessors;
-  for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-         PE = MBB->pred_end(); PI != PE; ++PI) {
-    MachineBasicBlock* PRED = *PI;
-    if (PRED != MBB)
-      predecessors.push_back(PRED);
-  }
-
-  unsigned i = 0, e = predecessors.size();
-  if (i != e) {
-    CSRegSet prevAvailIn = AvailIn[MBB];
-    MachineBasicBlock* PRED = predecessors[i];
-
-    AvailIn[MBB] = AvailOut[PRED];
-    for (++i; i != e; ++i) {
-      PRED = predecessors[i];
-      AvailIn[MBB] &= AvailOut[PRED];
-    }
-    if (prevAvailIn != AvailIn[MBB])
-      changed = true;
-  }
-
-  // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]);
-  CSRegSet prevAvailOut = AvailOut[MBB];
-  AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
-  if (prevAvailOut |= AvailOut[MBB])
-    changed = true;
-  return changed;
-}
-
-/// calculateAnticAvail - build the sets anticipated and available
-/// registers in the MCFG of the current function iteratively,
-/// doing a combined forward and backward analysis.
-///
-void PEI::calculateAnticAvail(MachineFunction &Fn) {
-  // Initialize data flow sets.
-  clearAnticAvailSets();
-
-  // Calulate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG.
-  bool changed = true;
-  unsigned iterations = 0;
-  while (changed) {
-    changed = false;
-    ++iterations;
-    for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
-         MBBI != MBBE; ++MBBI) {
-      MachineBasicBlock* MBB = MBBI;
-
-      // Calculate anticipated in, out regs at MBB from
-      // anticipated at successors of MBB.
-      changed |= calcAnticInOut(MBB);
-
-      // Calculate available in, out regs at MBB from
-      // available at predecessors of MBB.
-      changed |= calcAvailInOut(MBB);
-    }
-  }
-
-  DEBUG(if (ShrinkWrapDebugging >= Details) {
-      DOUT << "-----------------------------------------------------------\n";
-      DOUT << " Antic/Avail Sets:\n";
-      DOUT << "-----------------------------------------------------------\n";
-      DOUT << "iterations = " << iterations << "\n";
-      DOUT << "-----------------------------------------------------------\n";
-      DOUT << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n";
-      DOUT << "-----------------------------------------------------------\n";
-      for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
-           MBBI != MBBE; ++MBBI) {
-        MachineBasicBlock* MBB = MBBI;
-        dumpSets(MBB);
-      }
-      DOUT << "-----------------------------------------------------------\n";
-    });
-}
-
-/// propagateUsesAroundLoop - copy used register info from MBB to all blocks
-/// of the loop given by LP and its parent loops. This prevents spills/restores
-/// from being placed in the bodies of loops.
+/// runOnMachineFunction - Insert prolog/epilog code and replace abstract
+/// frame indexes with appropriate references.
 ///
-void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
-  if (! MBB || !LP)
-    return;
-
-  std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks();
-  for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) {
-    MachineBasicBlock* LBB = loopBlocks[i];
-    if (LBB == MBB)
-      continue;
-    if (CSRUsed[LBB].contains(CSRUsed[MBB]))
-      continue;
-    CSRUsed[LBB] |= CSRUsed[MBB];
-  }
-}
-
-/// calculateSets - collect the CSRs used in this function, compute
-/// the DF sets that describe the initial minimal regions in the
-/// Machine CFG around which CSR spills and restores must be placed.
-///
-/// Additionally, this function decides if shrink wrapping should
-/// be disabled for the current function, checking the following:
-///  1. the current function has more than 500 MBBs: heuristic limit
-///     on function size to reduce compile time impact of the current
-///     iterative algorithm.
-///  2. all CSRs are used in the entry block.
-///  3. all CSRs are used in all immediate successors of the entry block.
-///  4. all CSRs are used in a subset of blocks, each of which dominates
-///     all return blocks. These blocks, taken as a subgraph of the MCFG,
-///     are equivalent to the entry block since all execution paths pass
-///     through them.
-///
-bool PEI::calculateSets(MachineFunction &Fn) {
-  // Sets used to compute spill, restore placement sets.
-  const std::vector<CalleeSavedInfo> CSI =
-    Fn.getFrameInfo()->getCalleeSavedInfo();
-
-  // If no CSRs used, we are done.
-  if (CSI.empty()) {
-    DEBUG(if (ShrinkWrapThisFunction)
-            DOUT << "DISABLED: " << Fn.getFunction()->getName()
-                 << ": uses no callee-saved registers\n");
-    return false;
-  }
-
-  // Save refs to entry and return blocks.
-  EntryBlock = Fn.begin();
-  for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
-       MBB != E; ++MBB)
-    if (isReturnBlock(MBB))
-      ReturnBlocks.push_back(MBB);
-
-  // Determine if this function has fast exit paths.
-  DEBUG(if (ShrinkWrapThisFunction)
-          findFastExitPath());
-
-  // Limit shrink wrapping via the current iterative bit vector
-  // implementation to functions with <= 500 MBBs.
-  if (Fn.size() > 500) {
-    DEBUG(if (ShrinkWrapThisFunction)
-            DOUT << "DISABLED: " << Fn.getFunction()->getName()
-                 << ": too large (" << Fn.size() << " MBBs)\n");
-    ShrinkWrapThisFunction = false;
-  }
-
-  // Return now if not shrink wrapping.
-  if (! ShrinkWrapThisFunction)
-    return false;
-
-  // Collect set of used CSRs.
-  for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
-    UsedCSRegs.set(inx);
-  }
-
-  // Walk instructions in all MBBs, create CSRUsed[] sets, choose
-  // whether or not to shrink wrap this function.
-  MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
-  MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>();
+bool PEI::runOnMachineFunction(MachineFunction &Fn) {
   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
+  RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
+
+  // Get MachineModuleInfo so that we can track the construction of the
+  // frame.
+  if (MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>())
+    Fn.getFrameInfo()->setMachineModuleInfo(MMI);
+
+  // Allow the target machine to make some adjustments to the function
+  // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
+  TRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
+
+  // Scan the function for modified callee saved registers and insert spill
+  // code for any callee saved registers that are modified.  Also calculate
+  // the MaxCallFrameSize and HasCalls variables for the function's frame
+  // information and eliminates call frame pseudo instructions.
+  calculateCalleeSavedRegisters(Fn);
+
+  // Determine placement of CSR spill/restore code:
+  //  - with shrink wrapping, place spills and restores to tightly
+  //    enclose regions in the Machine CFG of the function where
+  //    they are used. Without shrink wrapping
+  //  - default (no shrink wrapping), place all spills in the
+  //    entry block, all restores in return blocks.
+  placeCSRSpillsAndRestores(Fn);
+
+  // Add the code to save and restore the callee saved registers
+  insertCSRSpillsAndRestores(Fn);
+
+  // Allow the target machine to make final modifications to the function
+  // before the frame layout is finalized.
+  TRI->processFunctionBeforeFrameFinalized(Fn);
+
+  // Calculate actual frame offsets for all abstract stack objects...
+  calculateFrameObjectOffsets(Fn);
+
+  // Add prolog and epilog code to the function.  This function is required
+  // to align the stack frame as necessary for any stack variables or
+  // called functions.  Because of this, calculateCalleeSavedRegisters
+  // must be called before this function in order to set the HasCalls
+  // and MaxCallFrameSize variables.
+  insertPrologEpilogCode(Fn);
+
+  // Replace all MO_FrameIndex operands with physical register references
+  // and actual offsets.
+  //
+  replaceFrameIndices(Fn);
 
-  bool allCSRUsesInEntryBlock = true;
-  for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
-       MBBI != MBBE; ++MBBI) {
-    MachineBasicBlock* MBB = MBBI;
-    for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
-      for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
-        unsigned Reg = CSI[inx].getReg();
-        // If instruction I reads or modifies Reg, add it to UsedCSRegs,
-        // CSRUsed map for the current block.
-        for (unsigned opInx = 0, opEnd = I->getNumOperands();
-             opInx != opEnd; ++opInx) {
-          const MachineOperand &MO = I->getOperand(opInx);
-          if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
-            continue;
-          unsigned MOReg = MO.getReg();
-          if (!MOReg)
-            continue;
-          if (MOReg == Reg ||
-              (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
-               TargetRegisterInfo::isPhysicalRegister(Reg) &&
-               TRI->isSubRegister(Reg, MOReg))) {
-            // CSR Reg is defined/used in block MBB.
-            CSRUsed[MBB].set(inx);
-            // Check for uses in EntryBlock.
-            if (MBB != EntryBlock)
-              allCSRUsesInEntryBlock = false;
-          }
-        }
-      }
-    }
-
-    if (CSRUsed[MBB].empty())
-      continue;
-
-    // Propagate CSRUsed[MBB] in loops
-    if (MachineLoop* LP = LI.getLoopFor(MBB)) {
-      // Add top level loop to work list.
-      MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP);
-      MachineLoop* PLP = getTopLevelLoopParent(LP);
-
-      if (! HDR) {
-        HDR = PLP->getHeader();
-        assert(HDR->pred_size() > 0 && "Loop header has no predecessors?");
-        MachineBasicBlock::pred_iterator PI = HDR->pred_begin();
-        HDR = *PI;
-      }
-      TLLoops[HDR] = PLP;
-
-      // Push uses from inside loop to its parent loops,
-      // or to all other MBBs in its loop.
-      if (LP->getLoopDepth() > 1) {
-        for (MachineLoop* PLP = LP->getParentLoop(); PLP;
-             PLP = PLP->getParentLoop()) {
-          propagateUsesAroundLoop(MBB, PLP);
-        }
-      } else {
-        propagateUsesAroundLoop(MBB, LP);
-      }
-    }
-  }
-
-  if (allCSRUsesInEntryBlock) {
-    DEBUG(DOUT << "DISABLED: " << Fn.getFunction()->getName()
-          << ": all CSRs used in EntryBlock\n");
-    ShrinkWrapThisFunction = false;
-  } else {
-    bool allCSRsUsedInEntryFanout = true;
-    for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
-           SE = EntryBlock->succ_end(); SI != SE; ++SI) {
-      MachineBasicBlock* SUCC = *SI;
-      if (CSRUsed[SUCC] != UsedCSRegs)
-        allCSRsUsedInEntryFanout = false;
-    }
-    if (allCSRsUsedInEntryFanout) {
-      DEBUG(DOUT << "DISABLED: " << Fn.getFunction()->getName()
-            << ": all CSRs used in imm successors of EntryBlock\n");
-      ShrinkWrapThisFunction = false;
-    }
-  }
-
-  if (ShrinkWrapThisFunction) {
-    // Check if MBB uses CSRs and dominates all exit nodes.
-    // Such nodes are equiv. to the entry node w.r.t.
-    // CSR uses: every path through the function must
-    // pass through this node. If each CSR is used at least
-    // once by these nodes, shrink wrapping is disabled.
-    CSRegSet CSRUsedInChokePoints;
-    for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
-         MBBI != MBBE; ++MBBI) {
-      MachineBasicBlock* MBB = MBBI;
-      if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
-        continue;
-      bool dominatesExitNodes = true;
-      for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
-        if (! DT.dominates(MBB, ReturnBlocks[ri])) {
-          dominatesExitNodes = false;
-          break;
-        }
-      if (dominatesExitNodes) {
-        CSRUsedInChokePoints |= CSRUsed[MBB];
-        if (CSRUsedInChokePoints == UsedCSRegs) {
-          DEBUG(DOUT << "DISABLED: " << Fn.getFunction()->getName()
-                << ": all CSRs used in choke point(s) at "
-                << getBasicBlockName(MBB) << "\n");
-          ShrinkWrapThisFunction = false;
-          break;
-        }
-      }
-    }
-  }
-
-  // Return now if we have decided not to apply shrink wrapping
-  // to the current function.
-  if (! ShrinkWrapThisFunction)
-    return false;
-
-  DEBUG({
-      DOUT << "ENABLED: " << Fn.getFunction()->getName();
-      if (HasFastExitPath)
-        DOUT << " (fast exit path)";
-      DOUT << "\n";
-      if (ShrinkWrapDebugging >= BasicInfo) {
-        DOUT << "------------------------------"
-             << "-----------------------------\n";
-        DOUT << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n";
-        if (ShrinkWrapDebugging >= Details) {
-          DOUT << "------------------------------"
-               << "-----------------------------\n";
-          dumpAllUsed();
-        }
-      }
-    });
-
-  // Build initial DF sets to determine minimal regions in the
-  // Machine CFG around which CSRs must be spilled and restored.
-  calculateAnticAvail(Fn);
-
+  delete RS;
+  clearAllSets();
   return true;
 }
 
-/// addUsesForMEMERegion - add uses of CSRs spilled or restored in
-/// multi-entry, multi-exit (MEME) regions so spill and restore
-/// placement will not break code that enters or leaves a
-/// shrink-wrapped region by inducing spills with no matching
-/// restores or rest