Shrink wrapping in PEI:

- reduces _static_ callee saved register spills
  and restores similar to Chow's original algorithm.
- iterative implementation with simple heuristic
  limits to mitigate compile time impact.
- handles placing spills/restores for multi-entry,
  multi-exit regions in the Machine CFG without
  splitting edges.
- passes test-suite in LLCBETA mode.

Added contains() method to ADT/SparseBitVector.


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

1 files changed, 1066 insertions, 610 deletions

diff --git a/lib/CodeGen/PrologEpilogInserter.cpp b/lib/CodeGen/PrologEpilogInserter.cpp
index d3e1839d00..6015d74abe 100644
--- a/lib/CodeGen/PrologEpilogInserter.cpp
+++ b/lib/CodeGen/PrologEpilogInserter.cpp
@@ -60,15 +60,41 @@
 #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("Apply shrink wrapping to callee-saved register spills/restores"));
+               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 {
@@ -81,7 +107,7 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
-      if (ShrinkWrapping) {
+      if (ShrinkWrapping || ShrinkWrapFunc != "") {
         AU.addRequired<MachineLoopInfo>();
         AU.addRequired<MachineDominatorTree>();
       }
@@ -97,6 +123,8 @@ namespace {
       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>())
@@ -127,7 +155,7 @@ namespace {
       // before the frame layout is finalized.
       TRI->processFunctionBeforeFrameFinalized(Fn);
 
-      // Calculate actual frame offsets for all of the abstract stack objects...
+      // Calculate actual frame offsets for all abstract stack objects...
       calculateFrameObjectOffsets(Fn);
 
       // Add prolog and epilog code to the function.  This function is required
@@ -143,6 +171,7 @@ namespace {
       replaceFrameIndices(Fn);
 
       delete RS;
+      clearAllSets();
       return true;
     }
 
@@ -172,7 +201,6 @@ namespace {
     //  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;
@@ -184,22 +212,37 @@ namespace {
     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);
-    MachineBasicBlock* moveSpillsOutOfLoops(MachineFunction &Fn,
-                                            MachineBasicBlock* MBB);
-    void addRestoresForSBranchBlock(MachineFunction &Fn,
-                                    MachineBasicBlock* MBB);
-    void moveRestoresOutOfLoops(MachineFunction& Fn,
-                                MachineBasicBlock* MBB,
-                                std::vector<MachineBasicBlock*>& SBLKS);
-    void addSavesForRJoinBlocks(MachineFunction& Fn,
-                                std::vector<MachineBasicBlock*>& SBLKS);
+    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);
@@ -208,21 +251,13 @@ namespace {
     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() {
-      UsedCSRegs.clear();
-      CSRUsed.clear();
-      AnticIn.clear();
-      AnticOut.clear();
-      AvailIn.clear();
-      AvailOut.clear();
-      CSRSave.clear();
-      CSRRestore.clear();
-      EntryBlock = 0;
-      if (! ReturnBlocks.empty())
-        ReturnBlocks.clear();
-      ShrinkWrapThisFunction = ShrinkWrapping;
-    }
+    void initShrinkWrappingInfo();
 
     // Convienences for dealing with machine loops.
     MachineBasicBlock* getTopLevelLoopPreheader(MachineLoop* LP) {
@@ -247,60 +282,79 @@ namespace {
       return LP;
     }
 
-#ifndef NDEBUG
-    // Debugging methods.
-    static std::string getBasicBlockName(const MachineBasicBlock* MBB) {
-      std::ostringstream name;
-      if (MBB) {
-        if (MBB->getBasicBlock())
-          name << MBB->getBasicBlock()->getName();
-        else
-          name << "_MBB_" << MBB->getNumber();
-      }
-      return name.str();
-    }
-
-    static std::string stringifyCSRegSet(const CSRegSet& s,
-                                         MachineFunction &Fn) {
-      const TargetRegisterInfo* TRI = Fn.getTarget().getRegisterInfo();
-      const std::vector<CalleeSavedInfo> CSI =
-        Fn.getFrameInfo()->getCalleeSavedInfo();
+    // Propgate CSRs used in MBB to all MBBs of loop LP.
+    void propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP);
 
-      std::ostringstream srep;
-      if (CSI.size() == 0) {
-        srep << "[]";
-        return srep.str();
-      }
-      srep << "[";
-      CSRegSet::iterator I = s.begin(), E = s.end();
-      if (I != E) {
-        unsigned reg = CSI[*I].getReg();
-        srep << TRI->getName(reg);
-        for (++I; I != E; ++I) {
-          reg = CSI[*I].getReg();
-          srep << ",";
-          srep << TRI->getName(reg);
-        }
-      }
-      srep << "]";
-      return srep.str();
+    // Convenience for recognizing return blocks.
+    bool isReturnBlock(MachineBasicBlock* MBB) {
+      return (MBB && !MBB->empty() && MBB->back().getDesc().isReturn());
     }
 
-    static void dumpSet(const CSRegSet& s, MachineFunction &Fn) {
-      DOUT << stringifyCSRegSet(s, Fn) << "\n";
-    }
+#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;
+  HasFastExitPath = false;
+  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
+}
+
+
 /// 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
@@ -316,167 +370,222 @@ FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
 ///
 void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
 
-#ifndef NDEBUG
-  DOUT << "Place CSR spills/restores for "
-       << Fn.getFunction()->getName() << "\n";
-#endif
-
   initShrinkWrappingInfo();
 
+  DEBUG(if (ShrinkWrapThisFunction) {
+      DOUT << "Place CSR spills/restores for "
+           << MF->getFunction()->getName() << "\n";
+    });
+
   if (calculateSets(Fn))
     placeSpillsAndRestores(Fn);
 }
 
-/// calculateAnticAvail - helper for computing the data flow
-/// sets required for determining spill/restore placements.
+/// 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;
 
-      // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCC(MBB))
-      MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
-        SE = MBB->succ_end();
-      if (SI != SE) {
-        CSRegSet prevAnticOut = AnticOut[MBB];
-        MachineBasicBlock* SUCC = *SI;
-        AnticOut[MBB] = AnticIn[SUCC];
-        for (++SI; SI != SE; ++SI) {
-          SUCC = *SI;
-          AnticOut[MBB] &= AnticIn[SUCC];
-        }
-        if (prevAnticOut != AnticOut[MBB])
-          changed = true;
-      }
-      // AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
-      CSRegSet prevAnticIn = AnticIn[MBB];
-      AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
-      if (prevAnticIn |= AnticIn[MBB])
-        changed = true;
-
-      // AvailIn[MBB] = INTERSECT(AvailOut[S] for S in PRED(MBB))
-      MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-        PE = MBB->pred_end();
-      if (PI != PE) {
-        CSRegSet prevAvailIn = AvailIn[MBB];
-        MachineBasicBlock* PRED = *PI;
-        AvailIn[MBB] = AvailOut[PRED];
-        for (++PI; PI != PE; ++PI) {
-          PRED = *PI;
-          AvailIn[MBB] &= AvailOut[PRED];
-        }
-        if (prevAvailIn != AvailIn[MBB])
-          changed = true;
-      }
-      // AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
-      CSRegSet prevAvailOut = AvailOut[MBB];
-      AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
-      if (prevAvailOut |= AvailOut[MBB])
-        changed = true;
+      // 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);
     }
-    ++iterations;
   }
 
-  // EXP
-  AnticIn[EntryBlock].clear();
-  AnticOut[EntryBlock].clear();
+  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";
+    });
+}
 
-#ifndef NDEBUG
-  DOUT << "-----------------------------------------------------------\n";
-  DOUT << "iterations = " << iterations << "\n";
-  DOUT << "-----------------------------------------------------------\n";
-  DOUT << "MBB | 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;
+/// 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.
+///
+void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
+  if (! MBB || !LP)
+    return;
 
-    DOUT << getBasicBlockName(MBB) << " | "
-         << stringifyCSRegSet(AnticIn[MBB], Fn)
-         << " | "
-         << stringifyCSRegSet(AnticOut[MBB], Fn)
-         << " | "
-         << stringifyCSRegSet(AvailIn[MBB], Fn)
-         << " | "
-         << stringifyCSRegSet(AvailOut[MBB], Fn)
-         << "\n";
+  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];
   }
-#endif
 }
 
-/// calculateSets - helper function for placeCSRSpillsAndRestores,
-/// collect the CSRs used in this function, develop the DF sets that
-/// describe the minimal regions in the Machine CFG around which spills,
-/// restores must be placed.
+/// 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.
 ///
-/// This function decides if shrink wrapping should actually be done:
-///   if all CSR uses are in the entry block, no shrink wrapping is possible,
-///   so ShrinkWrapping is turned off (for the current function) and the
-///   function returns false.
+/// 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()) {
-#ifndef NDEBUG
-    DOUT << Fn.getFunction()->getName()
-         << " uses no callee-saved registers.\n";
-#endif
+    DEBUG(if (ShrinkWrapThisFunction)
+            DOUT << "DISABLED: " << Fn.getFunction()->getName()
+                 << ": uses no callee-saved registers\n");
     return false;
   }
 
-#ifndef NDEBUG
-  DOUT << "-----------------------------------------------------------\n";
-#endif
-
-  const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
-  bool allCSRUsesInEntryBlock = true;
-
-  // Initialize UsedCSRegs set, CSRUsed map.
-  // At the same time, put entry block directly into
-  // CSRSave, CSRRestore sets if any CSRs are used.
-  //
-  // Quick exit option (not implemented):
-  //   Given N CSR uses in entry block,
-  //   revert to default behavior, skip the placement
-  //   step and put all saves in entry, restores in
-  //   return blocks.
-
-  // Set up entry and return blocks.
+  // Save refs to entry and return blocks.
   EntryBlock = Fn.begin();
   for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
        MBB != E; ++MBB)
-    if (!MBB->empty() && MBB->back().getDesc().isReturn())
+    if (isReturnBlock(MBB))
       ReturnBlocks.push_back(MBB);
 
-  // TODO -- check for a use of a CSR in each imm. successor of EntryBlock,
-  // do not shrink wrap this function if this is the case.
+  // 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;
+  }
 
-  // If not shrink wrapping (this function) at this point, set bits in
-  // CSR{Save,Restore}[] and UsedCSRegs, then return.
-  if (! ShrinkWrapThisFunction) {
-    for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
-      UsedCSRegs.set(inx);
-      CSRSave[EntryBlock].set(inx);
-      for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
-        CSRRestore[ReturnBlocks[ri]].set(inx);
-    }
+  // 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 basic sets, choose
+  // 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>();
+  const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
+
+  bool allCSRUsesInEntryBlock = true;
   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
        MBBI != MBBE; ++MBBI) {
     MachineBasicBlock* MBB = MBBI;
@@ -496,357 +605,453 @@ bool PEI::calculateSets(MachineFunction &Fn) {
           if (MOReg == Reg ||
               (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
                TargetRegisterInfo::isPhysicalRegister(Reg) &&
-               TRI->isSubRegister(MOReg, Reg))) {
+               TRI->isSubRegister(Reg, MOReg))) {
             // CSR Reg is defined/used in block MBB.
-            UsedCSRegs.set(inx);
             CSRUsed[MBB].set(inx);
-            // Short-circuit analysis for entry, return blocks:
-            // if a CSR is used in the entry block, add it directly
-            // to CSRSave[EntryBlock] and to CSRRestore[R] for R
-            // in ReturnBlocks. Note CSR uses in non-entry blocks.
-            if (ShrinkWrapThisFunction) {
-              if (MBB == EntryBlock) {
-                CSRSave[MBB].set(inx);
-                for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
-                  CSRRestore[ReturnBlocks[ri]].set(inx);
-              } else
-                allCSRUsesInEntryBlock = false;
-            } else {
-              // Not shrink wrapping => ensure saves/restores are correctly
-              // added for entry, return blocks.
-              CSRSave[EntryBlock].set(inx);
-              for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
-                CSRRestore[ReturnBlocks[ri]].set(inx);
-            }
+            // Check for uses in EntryBlock.
+            if (MBB != EntryBlock)
+              allCSRUsesInEntryBlock = false;
           }
         }
       }
     }
-#ifndef NDEBUG
-    DOUT << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
-         << stringifyCSRegSet(CSRUsed[MBB], Fn) << "\n";
-#endif
-  }
 
-#ifndef NDEBUG
-  DOUT << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs, Fn) << "\n";
-#endif
+    if (CSRUsed[MBB].empty())
+      continue;
 
-  // Early exit:
-  // 1. Not asked to do shrink wrapping => just "place" all spills(restores)
-  //    in the entry(return) block(s), already done above.
-  // 2. All CSR uses in entry block => same as case 1, but say we will
-  //    not shrink wrap the current function.
-  ShrinkWrapThisFunction = (ShrinkWrapping &&
-                            ShrinkWrapThisFunction &&
-                            ! allCSRUsesInEntryBlock);
-  if (! ShrinkWrapThisFunction) {
-    return false;
+    // 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);
+      }
+    }
   }
 
-  calculateAnticAvail(Fn);
+  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;
+    }
+  }
 
-  return true;
-}
+  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;
+        }
+      }
+    }
+  }
 
-/// moveSpillsOutOfLoops - helper for placeSpillsAndRestores() which
-/// relocates a spill from a subgraph in a loop to the loop preheader.
-/// Returns the MBB to which saves have been moved, or the given MBB
-/// if it is a branch point.
-///
-MachineBasicBlock* PEI::moveSpillsOutOfLoops(MachineFunction &Fn,
-                                             MachineBasicBlock* MBB) {
-  if (MBB == 0 || CSRSave[MBB].empty())
-    return 0;
+  // Return now if we have decided not to apply shrink wrapping
+  // to the current function.
+  if (! ShrinkWrapThisFunction)
+    return false;
 
-  // Block to which saves are moved.
-  MachineBasicBlock* DEST = 0;
-  MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
+  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();
+        }
+      }
+    });
 
-  if (MachineLoop* LP = LI.getLoopFor(MBB)) {
-    MachineBasicBlock* LPH = getTopLevelLoopPreheader(LP);
-    assert(LPH && "Loop has no top level preheader?");
+  // Build initial DF sets to determine minimal regions in the
+  // Machine CFG around which CSRs must be spilled and restored.
+  calculateAnticAvail(Fn);
 
-#ifndef NDEBUG
-    DOUT << "Moving saves of "
-         << stringifyCSRegSet(CSRSave[MBB], Fn)
-         << " from " << getBasicBlockName(MBB)
-         << " to " << getBasicBlockName(LPH) << "\n";
-#endif
-    // Add CSRegSet from MBB to LPH, empty out MBB's CSRegSet.
-    CSRSave[LPH] |= CSRSave[MBB];
-    // If saves moved to entry block, add restores to returns.
-    if (LPH == EntryBlock) {
-      for (unsigned i = 0, e = ReturnBlocks.size(); i != e; ++i)
-        CSRRestore[ReturnBlocks[i]] |= CSRSave[MBB];
-    } else {
-      // Remember where we moved the save so we can add
-      // restores on successor paths if necessary.
-      if (LPH->succ_size() > 1)
-        DEST = LPH;
-    }
-    CSRSave[MBB].clear();
-  } else if (MBB->succ_size() > 1)
-    DEST = MBB;
-  return DEST;
+  return true;
 }
 
-/// addRestoresForSBranchBlock - helper for placeSpillsAndRestores() which
-/// adds restores of CSRs saved in branch point MBBs to the front of any
-/// successor blocks connected to regions with no uses of the saved CSRs.
+/// 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 restores with no matching spills. A MEME region
+/// is a subgraph of the MCFG with multiple entry edges, multiple
+/// exit edges, or both. This code propagates use information
+/// through the MCFG until all paths requiring spills and restores
+/// _outside_ the computed minimal placement regions have been covered.
 ///
-void PEI::addRestoresForSBranchBlock(MachineFunction &Fn,
-                                     MachineBasicBlock* MBB) {
+bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
+                               SmallVector<MachineBasicBlock*, 4>& blks) {
+  if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
+    bool processThisBlock = false;
+    for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
+           SE = MBB->succ_end(); SI != SE; ++SI) {
+      MachineBasicBlock* SUCC = *SI;
+      if (SUCC->pred_size() > 1) {
+        processThisBlock = true;
+        break;
+      }
+    }
+    if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
+      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
+             PE = MBB->pred_end(); PI != PE; ++PI) {
+        MachineBasicBlock* PRED = *PI;
+        if (PRED->succ_size() > 1) {
+          processThisBlock = true;
+          break;
+        }
+      }
+    }
+    if (! processThisBlock)
+      return false;
+  }
 
-  if (MBB == 0 || CSRSave[MBB].empty() || MBB->succ_size() < 2)
-    return;
+  CSRegSet prop;
+  if (!CSRSave[MBB].empty())
+    prop = CSRSave[MBB];
+  else if (!CSRRestore[MBB].empty())
+    prop = CSRRestore[MBB];
+  else
+    prop = CSRUsed[MBB];
+  if (prop.empty())
+    return false;
 
-  // Add restores of CSRs saved in branch point MBBs to the
-  // front of any succ blocks flowing into regions that
-  // have no uses of MBB's CSRs.
-  bool hasCSRUses = false;
+  // Propagate selected bits to successors, predecessors of MBB.
+  bool addedUses = false;
   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
          SE = MBB->succ_end(); SI != SE; ++SI) {
     MachineBasicBlock* SUCC = *SI;
-    bool needsRestore = false;
-    if (CSRUsed[SUCC].intersects(CSRSave[MBB])) {
-      hasCSRUses = true;
+    // Self-loop
+    if (SUCC == MBB)
       continue;
+    if (! CSRUsed[SUCC].contains(prop)) {
+      CSRUsed[SUCC] |= prop;
+      addedUses = true;
+      blks.push_back(SUCC);
+      DEBUG(if (ShrinkWrapDebugging >= Iterations)
+              DOUT << getBasicBlockName(MBB)
+                   << "(" << stringifyCSRegSet(prop) << ")->"
+                   << "successor " << getBasicBlockName(SUCC) << "\n");
     }
-    needsRestore = true;
-    for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
-           BE = df_end(SUCC); BI != BE; ++BI) {
-      MachineBasicBlock* SBB = *BI;
-      if (CSRUsed[SBB].intersects(CSRSave[MBB])) {
-        hasCSRUses = true;
-        needsRestore = false;
-        break;
-      }
-    }
-    // Additional restores are needed for SUCC iff there is at least
-    // one CSR use reachable from the successors of MBB and there
-    // are no uses in or below SUCC.
-    if (needsRestore && hasCSRUses) {
-#ifndef NDEBUG
-      DOUT << "MBB " << getBasicBlockName(MBB)
-           << " needs a restore on path to successor "
-           << getBasicBlockName(SUCC) << "\n";
-#endif
-      // Add restores to SUCC for all CSRs saved in MBB...
-      CSRRestore[SUCC] = CSRSave[MBB];
+  }
+  for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
+         PE = MBB->pred_end(); PI != PE; ++PI) {
+    MachineBasicBlock* PRED = *PI;
+    // Self-loop
+    if (PRED == MBB)
+      continue;
+    if (! CSRUsed[PRED].contains(prop)) {
+      CSRUsed[PRED] |= prop;
+      addedUses = true;
+      blks.push_back(PRED);
+      DEBUG(if (ShrinkWrapDebugging >= Iterations)
+              DOUT << getBasicBlockName(MBB)
+                   << "(" << stringifyCSRegSet(prop) << ")->"
+                   << "predecessor " << getBasicBlockName(PRED) << "\n");
     }