Home | History | Annotate | Download | only in CodeGen
      1 //===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===//
      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 file implements a shrink wrapping variant of prolog/epilog insertion:
     11 // - Spills and restores of callee-saved registers (CSRs) are placed in the
     12 //   machine CFG to tightly surround their uses so that execution paths that
     13 //   do not use CSRs do not pay the spill/restore penalty.
     14 //
     15 // - Avoiding placment of spills/restores in loops: if a CSR is used inside a
     16 //   loop the spills are placed in the loop preheader, and restores are
     17 //   placed in the loop exit nodes (the successors of loop _exiting_ nodes).
     18 //
     19 // - Covering paths without CSR uses:
     20 //   If a region in a CFG uses CSRs and has multiple entry and/or exit points,
     21 //   the use info for the CSRs inside the region is propagated outward in the
     22 //   CFG to ensure validity of the spill/restore placements. This decreases
     23 //   the effectiveness of shrink wrapping but does not require edge splitting
     24 //   in the machine CFG.
     25 //
     26 // This shrink wrapping implementation uses an iterative analysis to determine
     27 // which basic blocks require spills and restores for CSRs.
     28 //
     29 // This pass uses MachineDominators and MachineLoopInfo. Loop information
     30 // is used to prevent placement of callee-saved register spills/restores
     31 // in the bodies of loops.
     32 //
     33 //===----------------------------------------------------------------------===//
     34 
     35 #define DEBUG_TYPE "shrink-wrap"
     36 
     37 #include "PrologEpilogInserter.h"
     38 #include "llvm/ADT/DenseMap.h"
     39 #include "llvm/ADT/PostOrderIterator.h"
     40 #include "llvm/ADT/STLExtras.h"
     41 #include "llvm/ADT/SparseBitVector.h"
     42 #include "llvm/ADT/Statistic.h"
     43 #include "llvm/CodeGen/MachineDominators.h"
     44 #include "llvm/CodeGen/MachineFrameInfo.h"
     45 #include "llvm/CodeGen/MachineInstr.h"
     46 #include "llvm/CodeGen/MachineLoopInfo.h"
     47 #include "llvm/CodeGen/MachineRegisterInfo.h"
     48 #include "llvm/Support/CommandLine.h"
     49 #include "llvm/Support/Compiler.h"
     50 #include "llvm/Support/Debug.h"
     51 #include "llvm/Target/TargetMachine.h"
     52 #include "llvm/Target/TargetRegisterInfo.h"
     53 #include <sstream>
     54 
     55 using namespace llvm;
     56 
     57 STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");
     58 
     59 // Shrink Wrapping:
     60 static cl::opt<bool>
     61 ShrinkWrapping("shrink-wrap",
     62                cl::desc("Shrink wrap callee-saved register spills/restores"));
     63 
     64 // Shrink wrap only the specified function, a debugging aid.
     65 static cl::opt<std::string>
     66 ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
     67                cl::desc("Shrink wrap the specified function"),
     68                cl::value_desc("funcname"),
     69                cl::init(""));
     70 
     71 // Debugging level for shrink wrapping.
     72 enum ShrinkWrapDebugLevel {
     73   None, BasicInfo, Iterations, Details
     74 };
     75 
     76 static cl::opt<enum ShrinkWrapDebugLevel>
     77 ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
     78   cl::desc("Print shrink wrapping debugging information"),
     79   cl::values(
     80     clEnumVal(None      , "disable debug output"),
     81     clEnumVal(BasicInfo , "print basic DF sets"),
     82     clEnumVal(Iterations, "print SR sets for each iteration"),
     83     clEnumVal(Details   , "print all DF sets"),
     84     clEnumValEnd));
     85 
     86 
     87 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
     88   AU.setPreservesCFG();
     89   if (ShrinkWrapping || ShrinkWrapFunc != "") {
     90     AU.addRequired<MachineLoopInfo>();
     91     AU.addRequired<MachineDominatorTree>();
     92   }
     93   AU.addPreserved<MachineLoopInfo>();
     94   AU.addPreserved<MachineDominatorTree>();
     95   AU.addRequired<TargetPassConfig>();
     96   MachineFunctionPass::getAnalysisUsage(AU);
     97 }
     98 
     99 //===----------------------------------------------------------------------===//
    100 //  ShrinkWrapping implementation
    101 //===----------------------------------------------------------------------===//
    102 
    103 // Convienences for dealing with machine loops.
    104 MachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) {
    105   assert(LP && "Machine loop is NULL.");
    106   MachineBasicBlock* PHDR = LP->getLoopPreheader();
    107   MachineLoop* PLP = LP->getParentLoop();
    108   while (PLP) {
    109     PHDR = PLP->getLoopPreheader();
    110     PLP = PLP->getParentLoop();
    111   }
    112   return PHDR;
    113 }
    114 
    115 MachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) {
    116   if (LP == 0)
    117     return 0;
    118   MachineLoop* PLP = LP->getParentLoop();
    119   while (PLP) {
    120     LP = PLP;
    121     PLP = PLP->getParentLoop();
    122   }
    123   return LP;
    124 }
    125 
    126 bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
    127   return (MBB && !MBB->empty() && MBB->back().isReturn());
    128 }
    129 
    130 // Initialize shrink wrapping DFA sets, called before iterations.
    131 void PEI::clearAnticAvailSets() {
    132   AnticIn.clear();
    133   AnticOut.clear();
    134   AvailIn.clear();
    135   AvailOut.clear();
    136 }
    137 
    138 // Clear all sets constructed by shrink wrapping.
    139 void PEI::clearAllSets() {
    140   ReturnBlocks.clear();
    141   clearAnticAvailSets();
    142   UsedCSRegs.clear();
    143   CSRUsed.clear();
    144   TLLoops.clear();
    145   CSRSave.clear();
    146   CSRRestore.clear();
    147 }
    148 
    149 // Initialize all shrink wrapping data.
    150 void PEI::initShrinkWrappingInfo() {
    151   clearAllSets();
    152   EntryBlock = 0;
    153 #ifndef NDEBUG
    154   HasFastExitPath = false;
    155 #endif
    156   ShrinkWrapThisFunction = ShrinkWrapping;
    157   // DEBUG: enable or disable shrink wrapping for the current function
    158   // via --shrink-wrap-func=<funcname>.
    159 #ifndef NDEBUG
    160   if (ShrinkWrapFunc != "") {
    161     std::string MFName = MF->getName().str();
    162     ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
    163   }
    164 #endif
    165 }
    166 
    167 
    168 /// placeCSRSpillsAndRestores - determine which MBBs of the function
    169 /// need save, restore code for callee-saved registers by doing a DF analysis
    170 /// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
    171 /// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
    172 /// is used to ensure that CSR save/restore code is not placed inside loops.
    173 /// This function computes the maps of MBBs -> CSRs to spill and restore
    174 /// in CSRSave, CSRRestore.
    175 ///
    176 /// If shrink wrapping is not being performed, place all spills in
    177 /// the entry block, all restores in return blocks. In this case,
    178 /// CSRSave has a single mapping, CSRRestore has mappings for each
    179 /// return block.
    180 ///
    181 void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
    182 
    183   DEBUG(MF = &Fn);
    184 
    185   initShrinkWrappingInfo();
    186 
    187   DEBUG(if (ShrinkWrapThisFunction) {
    188       dbgs() << "Place CSR spills/restores for "
    189              << MF->getName() << "\n";
    190     });
    191 
    192   if (calculateSets(Fn))
    193     placeSpillsAndRestores(Fn);
    194 }
    195 
    196 /// calcAnticInOut - calculate the anticipated in/out reg sets
    197 /// for the given MBB by looking forward in the MCFG at MBB's
    198 /// successors.
    199 ///
    200 bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
    201   bool changed = false;
    202 
    203   // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB))
    204   SmallVector<MachineBasicBlock*, 4> successors;
    205   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
    206          SE = MBB->succ_end(); SI != SE; ++SI) {
    207     MachineBasicBlock* SUCC = *SI;
    208     if (SUCC != MBB)
    209       successors.push_back(SUCC);
    210   }
    211 
    212   unsigned i = 0, e = successors.size();
    213   if (i != e) {
    214     CSRegSet prevAnticOut = AnticOut[MBB];
    215     MachineBasicBlock* SUCC = successors[i];
    216 
    217     AnticOut[MBB] = AnticIn[SUCC];
    218     for (++i; i != e; ++i) {
    219       SUCC = successors[i];
    220       AnticOut[MBB] &= AnticIn[SUCC];
    221     }
    222     if (prevAnticOut != AnticOut[MBB])
    223       changed = true;
    224   }
    225 
    226   // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]);
    227   CSRegSet prevAnticIn = AnticIn[MBB];
    228   AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
    229   if (prevAnticIn != AnticIn[MBB])
    230     changed = true;
    231   return changed;
    232 }
    233 
    234 /// calcAvailInOut - calculate the available in/out reg sets
    235 /// for the given MBB by looking backward in the MCFG at MBB's
    236 /// predecessors.
    237 ///
    238 bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
    239   bool changed = false;
    240 
    241   // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB))
    242   SmallVector<MachineBasicBlock*, 4> predecessors;
    243   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
    244          PE = MBB->pred_end(); PI != PE; ++PI) {
    245     MachineBasicBlock* PRED = *PI;
    246     if (PRED != MBB)
    247       predecessors.push_back(PRED);
    248   }
    249 
    250   unsigned i = 0, e = predecessors.size();
    251   if (i != e) {
    252     CSRegSet prevAvailIn = AvailIn[MBB];
    253     MachineBasicBlock* PRED = predecessors[i];
    254 
    255     AvailIn[MBB] = AvailOut[PRED];
    256     for (++i; i != e; ++i) {
    257       PRED = predecessors[i];
    258       AvailIn[MBB] &= AvailOut[PRED];
    259     }
    260     if (prevAvailIn != AvailIn[MBB])
    261       changed = true;
    262   }
    263 
    264   // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]);
    265   CSRegSet prevAvailOut = AvailOut[MBB];
    266   AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
    267   if (prevAvailOut != AvailOut[MBB])
    268     changed = true;
    269   return changed;
    270 }
    271 
    272 /// calculateAnticAvail - build the sets anticipated and available
    273 /// registers in the MCFG of the current function iteratively,
    274 /// doing a combined forward and backward analysis.
    275 ///
    276 void PEI::calculateAnticAvail(MachineFunction &Fn) {
    277   // Initialize data flow sets.
    278   clearAnticAvailSets();
    279 
    280   // Calculate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG.
    281   bool changed = true;
    282   unsigned iterations = 0;
    283   while (changed) {
    284     changed = false;
    285     ++iterations;
    286     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
    287          MBBI != MBBE; ++MBBI) {
    288       MachineBasicBlock* MBB = MBBI;
    289 
    290       // Calculate anticipated in, out regs at MBB from
    291       // anticipated at successors of MBB.
    292       changed |= calcAnticInOut(MBB);
    293 
    294       // Calculate available in, out regs at MBB from
    295       // available at predecessors of MBB.
    296       changed |= calcAvailInOut(MBB);
    297     }
    298   }
    299 
    300   DEBUG({
    301       if (ShrinkWrapDebugging >= Details) {
    302         dbgs()
    303           << "-----------------------------------------------------------\n"
    304           << " Antic/Avail Sets:\n"
    305           << "-----------------------------------------------------------\n"
    306           << "iterations = " << iterations << "\n"
    307           << "-----------------------------------------------------------\n"
    308           << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n"
    309           << "-----------------------------------------------------------\n";
    310 
    311         for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
    312              MBBI != MBBE; ++MBBI) {
    313           MachineBasicBlock* MBB = MBBI;
    314           dumpSets(MBB);
    315         }
    316 
    317         dbgs()
    318           << "-----------------------------------------------------------\n";
    319       }
    320     });
    321 }
    322 
    323 /// propagateUsesAroundLoop - copy used register info from MBB to all blocks
    324 /// of the loop given by LP and its parent loops. This prevents spills/restores
    325 /// from being placed in the bodies of loops.
    326 ///
    327 void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
    328   if (! MBB || !LP)
    329     return;
    330 
    331   std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks();
    332   for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) {
    333     MachineBasicBlock* LBB = loopBlocks[i];
    334     if (LBB == MBB)
    335       continue;
    336     if (CSRUsed[LBB].contains(CSRUsed[MBB]))
    337       continue;
    338     CSRUsed[LBB] |= CSRUsed[MBB];
    339   }
    340 }
    341 
    342 /// calculateSets - collect the CSRs used in this function, compute
    343 /// the DF sets that describe the initial minimal regions in the
    344 /// Machine CFG around which CSR spills and restores must be placed.
    345 ///
    346 /// Additionally, this function decides if shrink wrapping should
    347 /// be disabled for the current function, checking the following:
    348 ///  1. the current function has more than 500 MBBs: heuristic limit
    349 ///     on function size to reduce compile time impact of the current
    350 ///     iterative algorithm.
    351 ///  2. all CSRs are used in the entry block.
    352 ///  3. all CSRs are used in all immediate successors of the entry block.
    353 ///  4. all CSRs are used in a subset of blocks, each of which dominates
    354 ///     all return blocks. These blocks, taken as a subgraph of the MCFG,
    355 ///     are equivalent to the entry block since all execution paths pass
    356 ///     through them.
    357 ///
    358 bool PEI::calculateSets(MachineFunction &Fn) {
    359   // Sets used to compute spill, restore placement sets.
    360   const std::vector<CalleeSavedInfo> CSI =
    361     Fn.getFrameInfo()->getCalleeSavedInfo();
    362 
    363   // If no CSRs used, we are done.
    364   if (CSI.empty()) {
    365     DEBUG(if (ShrinkWrapThisFunction)
    366             dbgs() << "DISABLED: " << Fn.getName()
    367                    << ": uses no callee-saved registers\n");
    368     return false;
    369   }
    370 
    371   // Save refs to entry and return blocks.
    372   EntryBlock = Fn.begin();
    373   for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
    374        MBB != E; ++MBB)
    375     if (isReturnBlock(MBB))
    376       ReturnBlocks.push_back(MBB);
    377 
    378   // Determine if this function has fast exit paths.
    379   DEBUG(if (ShrinkWrapThisFunction)
    380           findFastExitPath());
    381 
    382   // Limit shrink wrapping via the current iterative bit vector
    383   // implementation to functions with <= 500 MBBs.
    384   if (Fn.size() > 500) {
    385     DEBUG(if (ShrinkWrapThisFunction)
    386             dbgs() << "DISABLED: " << Fn.getName()
    387                    << ": too large (" << Fn.size() << " MBBs)\n");
    388     ShrinkWrapThisFunction = false;
    389   }
    390 
    391   // Return now if not shrink wrapping.
    392   if (! ShrinkWrapThisFunction)
    393     return false;
    394 
    395   // Collect set of used CSRs.
    396   for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
    397     UsedCSRegs.set(inx);
    398   }
    399 
    400   // Walk instructions in all MBBs, create CSRUsed[] sets, choose
    401   // whether or not to shrink wrap this function.
    402   MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
    403   MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>();
    404   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
    405 
    406   bool allCSRUsesInEntryBlock = true;
    407   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
    408        MBBI != MBBE; ++MBBI) {
    409     MachineBasicBlock* MBB = MBBI;
    410     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
    411       for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
    412         unsigned Reg = CSI[inx].getReg();
    413         // If instruction I reads or modifies Reg, add it to UsedCSRegs,
    414         // CSRUsed map for the current block.
    415         for (unsigned opInx = 0, opEnd = I->getNumOperands();
    416              opInx != opEnd; ++opInx) {
    417           const MachineOperand &MO = I->getOperand(opInx);
    418           if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
    419             continue;
    420           unsigned MOReg = MO.getReg();
    421           if (!MOReg)
    422             continue;
    423           if (MOReg == Reg ||
    424               (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
    425                TargetRegisterInfo::isPhysicalRegister(Reg) &&
    426                TRI->isSubRegister(Reg, MOReg))) {
    427             // CSR Reg is defined/used in block MBB.
    428             CSRUsed[MBB].set(inx);
    429             // Check for uses in EntryBlock.
    430             if (MBB != EntryBlock)
    431               allCSRUsesInEntryBlock = false;
    432           }
    433         }
    434       }
    435     }
    436 
    437     if (CSRUsed[MBB].empty())
    438       continue;
    439 
    440     // Propagate CSRUsed[MBB] in loops
    441     if (MachineLoop* LP = LI.getLoopFor(MBB)) {
    442       // Add top level loop to work list.
    443       MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP);
    444       MachineLoop* PLP = getTopLevelLoopParent(LP);
    445 
    446       if (! HDR) {
    447         HDR = PLP->getHeader();
    448         assert(HDR->pred_size() > 0 && "Loop header has no predecessors?");
    449         MachineBasicBlock::pred_iterator PI = HDR->pred_begin();
    450         HDR = *PI;
    451       }
    452       TLLoops[HDR] = PLP;
    453 
    454       // Push uses from inside loop to its parent loops,
    455       // or to all other MBBs in its loop.
    456       if (LP->getLoopDepth() > 1) {
    457         for (MachineLoop* PLP = LP->getParentLoop(); PLP;
    458              PLP = PLP->getParentLoop()) {
    459           propagateUsesAroundLoop(MBB, PLP);
    460         }
    461       } else {
    462         propagateUsesAroundLoop(MBB, LP);
    463       }
    464     }
    465   }
    466 
    467   if (allCSRUsesInEntryBlock) {
    468     DEBUG(dbgs() << "DISABLED: " << Fn.getName()
    469                  << ": all CSRs used in EntryBlock\n");
    470     ShrinkWrapThisFunction = false;
    471   } else {
    472     bool allCSRsUsedInEntryFanout = true;
    473     for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
    474            SE = EntryBlock->succ_end(); SI != SE; ++SI) {
    475       MachineBasicBlock* SUCC = *SI;
    476       if (CSRUsed[SUCC] != UsedCSRegs)
    477         allCSRsUsedInEntryFanout = false;
    478     }
    479     if (allCSRsUsedInEntryFanout) {
    480       DEBUG(dbgs() << "DISABLED: " << Fn.getName()
    481                    << ": all CSRs used in imm successors of EntryBlock\n");
    482       ShrinkWrapThisFunction = false;
    483     }
    484   }
    485 
    486   if (ShrinkWrapThisFunction) {
    487     // Check if MBB uses CSRs and dominates all exit nodes.
    488     // Such nodes are equiv. to the entry node w.r.t.
    489     // CSR uses: every path through the function must
    490     // pass through this node. If each CSR is used at least
    491     // once by these nodes, shrink wrapping is disabled.
    492     CSRegSet CSRUsedInChokePoints;
    493     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
    494          MBBI != MBBE; ++MBBI) {
    495       MachineBasicBlock* MBB = MBBI;
    496       if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
    497         continue;
    498       bool dominatesExitNodes = true;
    499       for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
    500         if (! DT.dominates(MBB, ReturnBlocks[ri])) {
    501           dominatesExitNodes = false;
    502           break;
    503         }
    504       if (dominatesExitNodes) {
    505         CSRUsedInChokePoints |= CSRUsed[MBB];
    506         if (CSRUsedInChokePoints == UsedCSRegs) {
    507           DEBUG(dbgs() << "DISABLED: " << Fn.getName()
    508                        << ": all CSRs used in choke point(s) at "
    509                        << getBasicBlockName(MBB) << "\n");
    510           ShrinkWrapThisFunction = false;
    511           break;
    512         }
    513       }
    514     }
    515   }
    516 
    517   // Return now if we have decided not to apply shrink wrapping
    518   // to the current function.
    519   if (! ShrinkWrapThisFunction)
    520     return false;
    521 
    522   DEBUG({
    523       dbgs() << "ENABLED: " << Fn.getName();
    524       if (HasFastExitPath)
    525         dbgs() << " (fast exit path)";
    526       dbgs() << "\n";
    527       if (ShrinkWrapDebugging >= BasicInfo) {
    528         dbgs() << "------------------------------"
    529              << "-----------------------------\n";
    530         dbgs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n";
    531         if (ShrinkWrapDebugging >= Details) {
    532           dbgs() << "------------------------------"
    533                << "-----------------------------\n";
    534           dumpAllUsed();
    535         }
    536       }
    537     });
    538 
    539   // Build initial DF sets to determine minimal regions in the
    540   // Machine CFG around which CSRs must be spilled and restored.
    541   calculateAnticAvail(Fn);
    542 
    543   return true;
    544 }
    545 
    546 /// addUsesForMEMERegion - add uses of CSRs spilled or restored in
    547 /// multi-entry, multi-exit (MEME) regions so spill and restore
    548 /// placement will not break code that enters or leaves a
    549 /// shrink-wrapped region by inducing spills with no matching
    550 /// restores or restores with no matching spills. A MEME region
    551 /// is a subgraph of the MCFG with multiple entry edges, multiple
    552 /// exit edges, or both. This code propagates use information
    553 /// through the MCFG until all paths requiring spills and restores
    554 /// _outside_ the computed minimal placement regions have been covered.
    555 ///
    556 bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
    557                                SmallVector<MachineBasicBlock*, 4>& blks) {
    558   if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
    559     bool processThisBlock = false;
    560     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
    561            SE = MBB->succ_end(); SI != SE; ++SI) {
    562       MachineBasicBlock* SUCC = *SI;
    563       if (SUCC->pred_size() > 1) {
    564         processThisBlock = true;
    565         break;
    566       }
    567     }
    568     if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
    569       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
    570              PE = MBB->pred_end(); PI != PE; ++PI) {
    571         MachineBasicBlock* PRED = *PI;
    572         if (PRED->succ_size() > 1) {
    573           processThisBlock = true;
    574           break;
    575         }
    576       }
    577     }
    578     if (! processThisBlock)
    579       return false;
    580   }
    581 
    582   CSRegSet prop;
    583   if (!CSRSave[MBB].empty())
    584     prop = CSRSave[MBB];
    585   else if (!CSRRestore[MBB].empty())
    586     prop = CSRRestore[MBB];
    587   else
    588     prop = CSRUsed[MBB];
    589   if (prop.empty())
    590     return false;
    591 
    592   // Propagate selected bits to successors, predecessors of MBB.
    593   bool addedUses = false;
    594   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
    595          SE = MBB->succ_end(); SI != SE; ++SI) {
    596     MachineBasicBlock* SUCC = *SI;
    597     // Self-loop
    598     if (SUCC == MBB)
    599       continue;
    600     if (! CSRUsed[SUCC].contains(prop)) {
    601       CSRUsed[SUCC] |= prop;
    602       addedUses = true;
    603       blks.push_back(SUCC);
    604       DEBUG(if (ShrinkWrapDebugging >= Iterations)
    605               dbgs() << getBasicBlockName(MBB)
    606                    << "(" << stringifyCSRegSet(prop) << ")->"
    607                    << "successor " << getBasicBlockName(SUCC) << "\n");
    608     }
    609   }
    610   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
    611          PE = MBB->pred_end(); PI != PE; ++PI) {
    612     MachineBasicBlock* PRED = *PI;
    613     // Self-loop
    614     if (PRED == MBB)
    615       continue;
    616     if (! CSRUsed[PRED].contains(prop)) {
    617       CSRUsed[PRED] |= prop;
    618       addedUses = true;
    619       blks.push_back(PRED);
    620       DEBUG(if (ShrinkWrapDebugging >= Iterations)
    621               dbgs() << getBasicBlockName(MBB)
    622                    << "(" << stringifyCSRegSet(prop) << ")->"
    623                    << "predecessor " << getBasicBlockName(PRED) << "\n");
    624     }
    625   }
    626   return addedUses;
    627 }
    628 
    629 /// addUsesForTopLevelLoops - add uses for CSRs used inside top
    630 /// level loops to the exit blocks of those loops.
    631 ///
    632 bool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) {
    633   bool addedUses = false;
    634 
    635   // Place restores for top level loops where needed.
    636   for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator
    637          I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) {
    638     MachineBasicBlock* MBB = I->first;
    639     MachineLoop* LP = I->second;
    640     MachineBasicBlock* HDR = LP->getHeader();
    641     SmallVector<MachineBasicBlock*, 4> exitBlocks;
    642     CSRegSet loopSpills;
    643 
    644     loopSpills = CSRSave[MBB];
    645     if (CSRSave[MBB].empty()) {
    646       loopSpills = CSRUsed[HDR];
    647       assert(!loopSpills.empty() && "No CSRs used in loop?");
    648     } else if (CSRRestore[MBB].contains(CSRSave[MBB]))
    649       continue;
    650 
    651     LP->getExitBlocks(exitBlocks);
    652     assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?");
    653     for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
    654       MachineBasicBlock* EXB = exitBlocks[i];
    655       if (! CSRUsed[EXB].contains(loopSpills)) {
    656         CSRUsed[EXB] |= loopSpills;
    657         addedUses = true;
    658         DEBUG(if (ShrinkWrapDebugging >= Iterations)
    659                 dbgs() << "LOOP " << getBasicBlockName(MBB)
    660                      << "(" << stringifyCSRegSet(loopSpills) << ")->"
    661                      << getBasicBlockName(EXB) << "\n");
    662         if (EXB->succ_size() > 1 || EXB->pred_size() > 1)
    663           blks.push_back(EXB);
    664       }
    665     }
    666   }
    667   return addedUses;
    668 }
    669 
    670 /// calcSpillPlacements - determine which CSRs should be spilled
    671 /// in MBB using AnticIn sets of MBB's predecessors, keeping track
    672 /// of changes to spilled reg sets. Add MBB to the set of blocks
    673 /// that need to be processed for propagating use info to cover
    674 /// multi-entry/exit regions.
    675 ///
    676 bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
    677                               SmallVector<MachineBasicBlock*, 4> &blks,
    678                               CSRegBlockMap &prevSpills) {
    679   bool placedSpills = false;
    680   // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB)
    681   CSRegSet anticInPreds;
    682   SmallVector<MachineBasicBlock*, 4> predecessors;
    683   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
    684          PE = MBB->pred_end(); PI != PE; ++PI) {
    685     MachineBasicBlock* PRED = *PI;
    686     if (PRED != MBB)
    687       predecessors.push_back(PRED);
    688   }
    689   unsigned i = 0, e = predecessors.size();
    690   if (i != e) {
    691     MachineBasicBlock* PRED = predecessors[i];
    692     anticInPreds = UsedCSRegs - AnticIn[PRED];
    693     for (++i; i != e; ++i) {
    694       PRED = predecessors[i];
    695       anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
    696     }
    697   } else {
    698     // Handle uses in entry blocks (which have no predecessors).
    699     // This is necessary because the DFA formulation assumes the
    700     // entry and (multiple) exit nodes cannot have CSR uses, which
    701     // is not the case in the real world.
    702     anticInPreds = UsedCSRegs;
    703   }
    704   // Compute spills required at MBB:
    705   CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
    706 
    707   if (! CSRSave[MBB].empty()) {
    708     if (MBB == EntryBlock) {
    709       for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
    710         CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
    711     } else {
    712       // Reset all regs spilled in MBB that are also spilled in EntryBlock.
    713       if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
    714         CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
    715       }
    716     }
    717   }
    718   placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
    719   prevSpills[MBB] = CSRSave[MBB];
    720   // Remember this block for adding restores to successor
    721   // blocks for multi-entry region.
    722   if (placedSpills)
    723     blks.push_back(MBB);
    724 
    725   DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
    726           dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
    727                << stringifyCSRegSet(CSRSave[MBB]) << "\n");
    728 
    729   return placedSpills;
    730 }
    731 
    732 /// calcRestorePlacements - determine which CSRs should be restored
    733 /// in MBB using AvailOut sets of MBB's succcessors, keeping track
    734 /// of changes to restored reg sets. Add MBB to the set of blocks
    735 /// that need to be processed for propagating use info to cover
    736 /// multi-entry/exit regions.
    737 ///
    738 bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
    739                                 SmallVector<MachineBasicBlock*, 4> &blks,
    740                                 CSRegBlockMap &prevRestores) {
    741   bool placedRestores = false;
    742   // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB)
    743   CSRegSet availOutSucc;
    744   SmallVector<MachineBasicBlock*, 4> successors;
    745   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
    746          SE = MBB->succ_end(); SI != SE; ++SI) {
    747     MachineBasicBlock* SUCC = *SI;
    748     if (SUCC != MBB)
    749       successors.push_back(SUCC);
    750   }
    751   unsigned i = 0, e = successors.size();
    752   if (i != e) {
    753     MachineBasicBlock* SUCC = successors[i];
    754     availOutSucc = UsedCSRegs - AvailOut[SUCC];
    755     for (++i; i != e; ++i) {
    756       SUCC = successors[i];
    757       availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
    758     }
    759   } else {
    760     if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
    761       // Handle uses in return blocks (which have no successors).
    762       // This is necessary because the DFA formulation assumes the
    763       // entry and (multiple) exit nodes cannot have CSR uses, which
    764       // is not the case in the real world.
    765       availOutSucc = UsedCSRegs;
    766     }
    767   }
    768   // Compute restores required at MBB:
    769   CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
    770 
    771   // Postprocess restore placements at MBB.
    772   // Remove the CSRs that are restored in the return blocks.
    773   // Lest this be confusing, note that:
    774   // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks.
    775   if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
    776     if (! CSRSave[EntryBlock].empty())
    777       CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
    778   }
    779   placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
    780   prevRestores[MBB] = CSRRestore[MBB];
    781   // Remember this block for adding saves to predecessor
    782   // blocks for multi-entry region.
    783   if (placedRestores)
    784     blks.push_back(MBB);
    785 
    786   DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
    787           dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = "
    788                << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
    789 
    790   return placedRestores;
    791 }
    792 
    793 /// placeSpillsAndRestores - place spills and restores of CSRs
    794 /// used in MBBs in minimal regions that contain the uses.
    795 ///
    796 void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
    797   CSRegBlockMap prevCSRSave;
    798   CSRegBlockMap prevCSRRestore;
    799   SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks;
    800   bool changed = true;
    801   unsigned iterations = 0;
    802 
    803   // Iterate computation of spill and restore placements in the MCFG until:
    804   //   1. CSR use info has been fully propagated around the MCFG, and
    805   //   2. computation of CSRSave[], CSRRestore[] reach fixed points.
    806   while (changed) {
    807     changed = false;
    808     ++iterations;
    809 
    810     DEBUG(if (ShrinkWrapDebugging >= Iterations)
    811             dbgs() << "iter " << iterations
    812                  << " --------------------------------------------------\n");
    813 
    814     // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG,
    815     // which determines the placements of spills and restores.
    816     // Keep track of changes to spills, restores in each iteration to
    817     // minimize the total iterations.
    818     bool SRChanged = false;
    819     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
    820          MBBI != MBBE; ++MBBI) {
    821       MachineBasicBlock* MBB = MBBI;
    822 
    823       // Place spills for CSRs in MBB.
    824       SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
    825 
    826       // Place restores for CSRs in MBB.
    827       SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
    828     }
    829 
    830     // Add uses of CSRs used inside loops where needed.
    831     changed |= addUsesForTopLevelLoops(cvBlocks);
    832 
    833     // Add uses for CSRs spilled or restored at branch, join points.
    834     if (changed || SRChanged) {
    835       while (! cvBlocks.empty()) {
    836         MachineBasicBlock* MBB = cvBlocks.pop_back_val();
    837         changed |= addUsesForMEMERegion(MBB, ncvBlocks);
    838       }
    839       if (! ncvBlocks.empty()) {
    840         cvBlocks = ncvBlocks;
    841         ncvBlocks.clear();
    842       }
    843     }
    844 
    845     if (changed) {
    846       calculateAnticAvail(Fn);
    847       CSRSave.clear();
    848       CSRRestore.clear();
    849     }
    850   }
    851 
    852   // Check for effectiveness:
    853   //  SR0 = {r | r in CSRSave[EntryBlock], CSRRestore[RB], RB in ReturnBlocks}
    854   //  numSRReduced = |(UsedCSRegs - SR0)|, approx. SR0 by CSRSave[EntryBlock]
    855   // Gives a measure of how many CSR spills have been moved from EntryBlock
    856   // to minimal regions enclosing their uses.
    857   CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]);
    858   unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count();
    859   numSRReduced += numSRReducedThisFunc;
    860   DEBUG(if (ShrinkWrapDebugging >= BasicInfo) {
    861       dbgs() << "-----------------------------------------------------------\n";
    862       dbgs() << "total iterations = " << iterations << " ( "
    863            << Fn.getName()
    864            << " " << numSRReducedThisFunc
    865            << " " << Fn.size()
    866            << " )\n";
    867       dbgs() << "-----------------------------------------------------------\n";
    868       dumpSRSets();
    869       dbgs() << "-----------------------------------------------------------\n";
    870       if (numSRReducedThisFunc)
    871         verifySpillRestorePlacement();
    872     });
    873 }
    874 
    875 // Debugging methods.
    876 #ifndef NDEBUG
    877 /// findFastExitPath - debugging method used to detect functions
    878 /// with at least one path from the entry block to a return block
    879 /// directly or which has a very small number of edges.
    880 ///
    881 void PEI::findFastExitPath() {
    882   if (! EntryBlock)
    883     return;
    884   // Fina a path from EntryBlock to any return block that does not branch:
    885   //        Entry
    886   //          |     ...
    887   //          v      |
    888   //         B1<-----+
    889   //          |
    890   //          v
    891   //       Return
    892   for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
    893          SE = EntryBlock->succ_end(); SI != SE; ++SI) {
    894     MachineBasicBlock* SUCC = *SI;
    895 
    896     // Assume positive, disprove existence of fast path.
    897     HasFastExitPath = true;
    898 
    899     // Check the immediate successors.
    900     if (isReturnBlock(SUCC)) {
    901       if (ShrinkWrapDebugging >= BasicInfo)
    902         dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
    903              << "->" << getBasicBlockName(SUCC) << "\n";
    904       break;
    905     }
    906     // Traverse df from SUCC, look for a branch block.
    907     std::string exitPath = getBasicBlockName(SUCC);
    908     for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
    909            BE = df_end(SUCC); BI != BE; ++BI) {
    910       MachineBasicBlock* SBB = *BI;
    911       // Reject paths with branch nodes.
    912       if (SBB->succ_size() > 1) {
    913         HasFastExitPath = false;
    914         break;
    915       }
    916       exitPath += "->" + getBasicBlockName(SBB);
    917     }
    918     if (HasFastExitPath) {
    919       if (ShrinkWrapDebugging >= BasicInfo)
    920         dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
    921              << "->" << exitPath << "\n";
    922       break;
    923     }
    924   }
    925 }
    926 
    927 /// verifySpillRestorePlacement - check the current spill/restore
    928 /// sets for safety. Attempt to find spills without restores or
    929 /// restores without spills.
    930 /// Spills: walk df from each MBB in spill set ensuring that
    931 ///         all CSRs spilled at MMBB are restored on all paths
    932 ///         from MBB to all exit blocks.
    933 /// Restores: walk idf from each MBB in restore set ensuring that
    934 ///           all CSRs restored at MBB are spilled on all paths
    935 ///           reaching MBB.
    936 ///
    937 void PEI::verifySpillRestorePlacement() {
    938   unsigned numReturnBlocks = 0;
    939   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
    940        MBBI != MBBE; ++MBBI) {
    941     MachineBasicBlock* MBB = MBBI;
    942     if (isReturnBlock(MBB) || MBB->succ_size() == 0)
    943       ++numReturnBlocks;
    944   }
    945   for (CSRegBlockMap::iterator BI = CSRSave.begin(),
    946          BE = CSRSave.end(); BI != BE; ++BI) {
    947     MachineBasicBlock* MBB = BI->first;
    948     CSRegSet spilled = BI->second;
    949     CSRegSet restored;
    950 
    951     if (spilled.empty())
    952       continue;
    953 
    954     DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
    955                  << stringifyCSRegSet(spilled)
    956                  << "  RESTORE[" << getBasicBlockName(MBB) << "] = "
    957                  << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
    958 
    959     if (CSRRestore[MBB].intersects(spilled)) {
    960       restored |= (CSRRestore[MBB] & spilled);
    961     }
    962 
    963     // Walk depth first from MBB to find restores of all CSRs spilled at MBB:
    964     // we must find restores for all spills w/no intervening spills on all
    965     // paths from MBB to all return blocks.
    966     for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB),
    967            BE = df_end(MBB); BI != BE; ++BI) {
    968       MachineBasicBlock* SBB = *BI;
    969       if (SBB == MBB)
    970         continue;
    971       // Stop when we encounter spills of any CSRs spilled at MBB that
    972       // have not yet been seen to be restored.
    973       if (CSRSave[SBB].intersects(spilled) &&
    974           !restored.contains(CSRSave[SBB] & spilled))
    975         break;
    976       // Collect the CSRs spilled at MBB that are restored
    977       // at this DF successor of MBB.
    978       if (CSRRestore[SBB].intersects(spilled))
    979         restored |= (CSRRestore[SBB] & spilled);
    980       // If we are at a retun block, check that the restores
    981       // we have seen so far exhaust the spills at MBB, then
    982       // reset the restores.
    983       if (isReturnBlock(SBB) || SBB->succ_size() == 0) {
    984         if (restored != spilled) {
    985           CSRegSet notRestored = (spilled - restored);
    986           DEBUG(dbgs() << MF->getName() << ": "
    987                        << stringifyCSRegSet(notRestored)
    988                        << " spilled at " << getBasicBlockName(MBB)
    989                        << " are never restored on path to return "
    990                        << getBasicBlockName(SBB) << "\n");
    991         }
    992         restored.clear();
    993       }
    994     }
    995   }
    996 
    997   // Check restore placements.
    998   for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
    999          BE = CSRRestore.end(); BI != BE; ++BI) {
   1000     MachineBasicBlock* MBB = BI->first;
   1001     CSRegSet restored = BI->second;
   1002     CSRegSet spilled;
   1003 
   1004     if (restored.empty())
   1005       continue;
   1006 
   1007     DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
   1008                  << stringifyCSRegSet(CSRSave[MBB])
   1009                  << "  RESTORE[" << getBasicBlockName(MBB) << "] = "
   1010                  << stringifyCSRegSet(restored) << "\n");
   1011 
   1012     if (CSRSave[MBB].intersects(restored)) {
   1013       spilled |= (CSRSave[MBB] & restored);
   1014     }
   1015     // Walk inverse depth first from MBB to find spills of all
   1016     // CSRs restored at MBB:
   1017     for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB),
   1018            BE = idf_end(MBB); BI != BE; ++BI) {
   1019       MachineBasicBlock* PBB = *BI;
   1020       if (PBB == MBB)
   1021         continue;
   1022       // Stop when we encounter restores of any CSRs restored at MBB that
   1023       // have not yet been seen to be spilled.
   1024       if (CSRRestore[PBB].intersects(restored) &&
   1025           !spilled.contains(CSRRestore[PBB] & restored))
   1026         break;
   1027       // Collect the CSRs restored at MBB that are spilled
   1028       // at this DF predecessor of MBB.
   1029       if (CSRSave[PBB].intersects(restored))
   1030         spilled |= (CSRSave[PBB] & restored);
   1031     }
   1032     if (spilled != restored) {
   1033       CSRegSet notSpilled = (restored - spilled);
   1034       DEBUG(dbgs() << MF->getName() << ": "
   1035                    << stringifyCSRegSet(notSpilled)
   1036                    << " restored at " << getBasicBlockName(MBB)
   1037                    << " are never spilled\n");
   1038     }
   1039   }
   1040 }
   1041 
   1042 // Debugging print methods.
   1043 std::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) {
   1044   if (!MBB)
   1045     return "";
   1046 
   1047   if (MBB->getBasicBlock())
   1048     return MBB->getBasicBlock()->getName().str();
   1049 
   1050   std::ostringstream name;
   1051   name << "_MBB_" << MBB->getNumber();
   1052   return name.str();
   1053 }
   1054 
   1055 std::string PEI::stringifyCSRegSet(const CSRegSet& s) {
   1056   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
   1057   const std::vector<CalleeSavedInfo> CSI =
   1058     MF->getFrameInfo()->getCalleeSavedInfo();
   1059 
   1060   std::ostringstream srep;
   1061   if (CSI.size() == 0) {
   1062     srep << "[]";
   1063     return srep.str();
   1064   }
   1065   srep << "[";
   1066   CSRegSet::iterator I = s.begin(), E = s.end();
   1067   if (I != E) {
   1068     unsigned reg = CSI[*I].getReg();
   1069     srep << TRI->getName(reg);
   1070     for (++I; I != E; ++I) {
   1071       reg = CSI[*I].getReg();
   1072       srep << ",";
   1073       srep << TRI->getName(reg);
   1074     }
   1075   }
   1076   srep << "]";
   1077   return srep.str();
   1078 }
   1079 
   1080 void PEI::dumpSet(const CSRegSet& s) {
   1081   DEBUG(dbgs() << stringifyCSRegSet(s) << "\n");
   1082 }
   1083 
   1084 void PEI::dumpUsed(MachineBasicBlock* MBB) {
   1085   DEBUG({
   1086       if (MBB)
   1087         dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
   1088                << stringifyCSRegSet(CSRUsed[MBB])  << "\n";
   1089     });
   1090 }
   1091 
   1092 void PEI::dumpAllUsed() {
   1093     for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
   1094          MBBI != MBBE; ++MBBI) {
   1095       MachineBasicBlock* MBB = MBBI;
   1096       dumpUsed(MBB);
   1097     }
   1098 }
   1099 
   1100 void PEI::dumpSets(MachineBasicBlock* MBB) {
   1101   DEBUG({
   1102       if (MBB)
   1103         dbgs() << getBasicBlockName(MBB)           << " | "
   1104                << stringifyCSRegSet(CSRUsed[MBB])  << " | "
   1105                << stringifyCSRegSet(AnticIn[MBB])  << " | "
   1106                << stringifyCSRegSet(AnticOut[MBB]) << " | "
   1107                << stringifyCSRegSet(AvailIn[MBB])  << " | "
   1108                << stringifyCSRegSet(AvailOut[MBB]) << "\n";
   1109     });
   1110 }
   1111 
   1112 void PEI::dumpSets1(MachineBasicBlock* MBB) {
   1113   DEBUG({
   1114       if (MBB)
   1115         dbgs() << getBasicBlockName(MBB)             << " | "
   1116                << stringifyCSRegSet(CSRUsed[MBB])    << " | "
   1117                << stringifyCSRegSet(AnticIn[MBB])    << " | "
   1118                << stringifyCSRegSet(AnticOut[MBB])   << " | "
   1119                << stringifyCSRegSet(AvailIn[MBB])    << " | "
   1120                << stringifyCSRegSet(AvailOut[MBB])   << " | "
   1121                << stringifyCSRegSet(CSRSave[MBB])    << " | "
   1122                << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
   1123     });
   1124 }
   1125 
   1126 void PEI::dumpAllSets() {
   1127     for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
   1128          MBBI != MBBE; ++MBBI) {
   1129       MachineBasicBlock* MBB = MBBI;
   1130       dumpSets1(MBB);
   1131     }
   1132 }
   1133 
   1134 void PEI::dumpSRSets() {
   1135   DEBUG({
   1136       for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
   1137            MBB != E; ++MBB) {
   1138         if (!CSRSave[MBB].empty()) {
   1139           dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
   1140                  << stringifyCSRegSet(CSRSave[MBB]);
   1141           if (CSRRestore[MBB].empty())
   1142             dbgs() << '\n';
   1143         }
   1144 
   1145         if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty())
   1146           dbgs() << "    "
   1147                  << "RESTORE[" << getBasicBlockName(MBB) << "] = "
   1148                  << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
   1149       }
   1150     });
   1151 }
   1152 #endif
   1153