LLVM API Documentation

ShrinkWrapping.cpp

Go to the documentation of this file.
00001 //===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a shrink wrapping variant of prolog/epilog insertion:
00011 // - Spills and restores of callee-saved registers (CSRs) are placed in the
00012 //   machine CFG to tightly surround their uses so that execution paths that
00013 //   do not use CSRs do not pay the spill/restore penalty.
00014 //
00015 // - Avoiding placment of spills/restores in loops: if a CSR is used inside a
00016 //   loop the spills are placed in the loop preheader, and restores are
00017 //   placed in the loop exit nodes (the successors of loop _exiting_ nodes).
00018 //
00019 // - Covering paths without CSR uses:
00020 //   If a region in a CFG uses CSRs and has multiple entry and/or exit points,
00021 //   the use info for the CSRs inside the region is propagated outward in the
00022 //   CFG to ensure validity of the spill/restore placements. This decreases
00023 //   the effectiveness of shrink wrapping but does not require edge splitting
00024 //   in the machine CFG.
00025 //
00026 // This shrink wrapping implementation uses an iterative analysis to determine
00027 // which basic blocks require spills and restores for CSRs.
00028 //
00029 // This pass uses MachineDominators and MachineLoopInfo. Loop information
00030 // is used to prevent placement of callee-saved register spills/restores
00031 // in the bodies of loops.
00032 //
00033 //===----------------------------------------------------------------------===//
00034 
00035 #define DEBUG_TYPE "shrink-wrap"
00036 
00037 #include "PrologEpilogInserter.h"
00038 #include "llvm/CodeGen/MachineDominators.h"
00039 #include "llvm/CodeGen/MachineLoopInfo.h"
00040 #include "llvm/CodeGen/MachineInstr.h"
00041 #include "llvm/CodeGen/MachineFrameInfo.h"
00042 #include "llvm/CodeGen/MachineRegisterInfo.h"
00043 #include "llvm/Target/TargetMachine.h"
00044 #include "llvm/Target/TargetRegisterInfo.h"
00045 #include "llvm/ADT/SparseBitVector.h"
00046 #include "llvm/ADT/DenseMap.h"
00047 #include "llvm/ADT/PostOrderIterator.h"
00048 #include "llvm/ADT/Statistic.h"
00049 #include "llvm/Support/CommandLine.h"
00050 #include "llvm/Support/Compiler.h"
00051 #include "llvm/Support/Debug.h"
00052 #include "llvm/ADT/STLExtras.h"
00053 #include "llvm/ADT/Statistic.h"
00054 #include <sstream>
00055 
00056 using namespace llvm;
00057 
00058 STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");
00059 
00060 // Shrink Wrapping:
00061 static cl::opt<bool>
00062 ShrinkWrapping("shrink-wrap",
00063                cl::desc("Shrink wrap callee-saved register spills/restores"));
00064 
00065 // Shrink wrap only the specified function, a debugging aid.
00066 static cl::opt<std::string>
00067 ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
00068                cl::desc("Shrink wrap the specified function"),
00069                cl::value_desc("funcname"),
00070                cl::init(""));
00071 
00072 // Debugging level for shrink wrapping.
00073 enum ShrinkWrapDebugLevel {
00074   None, BasicInfo, Iterations, Details
00075 };
00076 
00077 static cl::opt<enum ShrinkWrapDebugLevel>
00078 ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
00079   cl::desc("Print shrink wrapping debugging information"),
00080   cl::values(
00081     clEnumVal(None      , "disable debug output"),
00082     clEnumVal(BasicInfo , "print basic DF sets"),
00083     clEnumVal(Iterations, "print SR sets for each iteration"),
00084     clEnumVal(Details   , "print all DF sets"),
00085     clEnumValEnd));
00086 
00087 
00088 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
00089   AU.setPreservesCFG();
00090   if (ShrinkWrapping || ShrinkWrapFunc != "") {
00091     AU.addRequired<MachineLoopInfo>();
00092     AU.addRequired<MachineDominatorTree>();
00093   }
00094   AU.addPreserved<MachineLoopInfo>();
00095   AU.addPreserved<MachineDominatorTree>();
00096   MachineFunctionPass::getAnalysisUsage(AU);
00097 }
00098 
00099 //===----------------------------------------------------------------------===//
00100 //  ShrinkWrapping implementation
00101 //===----------------------------------------------------------------------===//
00102 
00103 // Convienences for dealing with machine loops.
00104 MachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) {
00105   assert(LP && "Machine loop is NULL.");
00106   MachineBasicBlock* PHDR = LP->getLoopPreheader();
00107   MachineLoop* PLP = LP->getParentLoop();
00108   while (PLP) {
00109     PHDR = PLP->getLoopPreheader();
00110     PLP = PLP->getParentLoop();
00111   }
00112   return PHDR;
00113 }
00114 
00115 MachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) {
00116   if (LP == 0)
00117     return 0;
00118   MachineLoop* PLP = LP->getParentLoop();
00119   while (PLP) {
00120     LP = PLP;
00121     PLP = PLP->getParentLoop();
00122   }
00123   return LP;
00124 }
00125 
00126 bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
00127   return (MBB && !MBB->empty() && MBB->back().getDesc().isReturn());
00128 }
00129 
00130 // Initialize shrink wrapping DFA sets, called before iterations.
00131 void PEI::clearAnticAvailSets() {
00132   AnticIn.clear();
00133   AnticOut.clear();
00134   AvailIn.clear();
00135   AvailOut.clear();
00136 }
00137 
00138 // Clear all sets constructed by shrink wrapping.
00139 void PEI::clearAllSets() {
00140   ReturnBlocks.clear();
00141   clearAnticAvailSets();
00142   UsedCSRegs.clear();
00143   CSRUsed.clear();
00144   TLLoops.clear();
00145   CSRSave.clear();
00146   CSRRestore.clear();
00147 }
00148 
00149 // Initialize all shrink wrapping data.
00150 void PEI::initShrinkWrappingInfo() {
00151   clearAllSets();
00152   EntryBlock = 0;
00153 #ifndef NDEBUG
00154   HasFastExitPath = false;
00155 #endif
00156   ShrinkWrapThisFunction = ShrinkWrapping;
00157   // DEBUG: enable or disable shrink wrapping for the current function
00158   // via --shrink-wrap-func=<funcname>.
00159 #ifndef NDEBUG
00160   if (ShrinkWrapFunc != "") {
00161     std::string MFName = MF->getFunction()->getNameStr();
00162     ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
00163   }
00164 #endif
00165 }
00166 
00167 
00168 /// placeCSRSpillsAndRestores - determine which MBBs of the function
00169 /// need save, restore code for callee-saved registers by doing a DF analysis
00170 /// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
00171 /// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
00172 /// is used to ensure that CSR save/restore code is not placed inside loops.
00173 /// This function computes the maps of MBBs -> CSRs to spill and restore
00174 /// in CSRSave, CSRRestore.
00175 ///
00176 /// If shrink wrapping is not being performed, place all spills in
00177 /// the entry block, all restores in return blocks. In this case,
00178 /// CSRSave has a single mapping, CSRRestore has mappings for each
00179 /// return block.
00180 ///
00181 void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
00182 
00183   DEBUG(MF = &Fn);
00184 
00185   initShrinkWrappingInfo();
00186 
00187   DEBUG(if (ShrinkWrapThisFunction) {
00188       errs() << "Place CSR spills/restores for "
00189              << MF->getFunction()->getName() << "\n";
00190     });
00191 
00192   if (calculateSets(Fn))
00193     placeSpillsAndRestores(Fn);
00194 }
00195 
00196 /// calcAnticInOut - calculate the anticipated in/out reg sets
00197 /// for the given MBB by looking forward in the MCFG at MBB's
00198 /// successors.
00199 ///
00200 bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
00201   bool changed = false;
00202 
00203   // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB))
00204   SmallVector<MachineBasicBlock*, 4> successors;
00205   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00206          SE = MBB->succ_end(); SI != SE; ++SI) {
00207     MachineBasicBlock* SUCC = *SI;
00208     if (SUCC != MBB)
00209       successors.push_back(SUCC);
00210   }
00211 
00212   unsigned i = 0, e = successors.size();
00213   if (i != e) {
00214     CSRegSet prevAnticOut = AnticOut[MBB];
00215     MachineBasicBlock* SUCC = successors[i];
00216 
00217     AnticOut[MBB] = AnticIn[SUCC];
00218     for (++i; i != e; ++i) {
00219       SUCC = successors[i];
00220       AnticOut[MBB] &= AnticIn[SUCC];
00221     }
00222     if (prevAnticOut != AnticOut[MBB])
00223       changed = true;
00224   }
00225 
00226   // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]);
00227   CSRegSet prevAnticIn = AnticIn[MBB];
00228   AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
00229   if (prevAnticIn |= AnticIn[MBB])
00230     changed = true;
00231   return changed;
00232 }
00233 
00234 /// calcAvailInOut - calculate the available in/out reg sets
00235 /// for the given MBB by looking backward in the MCFG at MBB's
00236 /// predecessors.
00237 ///
00238 bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
00239   bool changed = false;
00240 
00241   // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB))
00242   SmallVector<MachineBasicBlock*, 4> predecessors;
00243   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00244          PE = MBB->pred_end(); PI != PE; ++PI) {
00245     MachineBasicBlock* PRED = *PI;
00246     if (PRED != MBB)
00247       predecessors.push_back(PRED);
00248   }
00249 
00250   unsigned i = 0, e = predecessors.size();
00251   if (i != e) {
00252     CSRegSet prevAvailIn = AvailIn[MBB];
00253     MachineBasicBlock* PRED = predecessors[i];
00254 
00255     AvailIn[MBB] = AvailOut[PRED];
00256     for (++i; i != e; ++i) {
00257       PRED = predecessors[i];
00258       AvailIn[MBB] &= AvailOut[PRED];
00259     }
00260     if (prevAvailIn != AvailIn[MBB])
00261       changed = true;
00262   }
00263 
00264   // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]);
00265   CSRegSet prevAvailOut = AvailOut[MBB];
00266   AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
00267   if (prevAvailOut |= AvailOut[MBB])
00268     changed = true;
00269   return changed;
00270 }
00271 
00272 /// calculateAnticAvail - build the sets anticipated and available
00273 /// registers in the MCFG of the current function iteratively,
00274 /// doing a combined forward and backward analysis.
00275 ///
00276 void PEI::calculateAnticAvail(MachineFunction &Fn) {
00277   // Initialize data flow sets.
00278   clearAnticAvailSets();
00279 
00280   // Calulate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG.
00281   bool changed = true;
00282   unsigned iterations = 0;
00283   while (changed) {
00284     changed = false;
00285     ++iterations;
00286     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
00287          MBBI != MBBE; ++MBBI) {
00288       MachineBasicBlock* MBB = MBBI;
00289 
00290       // Calculate anticipated in, out regs at MBB from
00291       // anticipated at successors of MBB.
00292       changed |= calcAnticInOut(MBB);
00293 
00294       // Calculate available in, out regs at MBB from
00295       // available at predecessors of MBB.
00296       changed |= calcAvailInOut(MBB);
00297     }
00298   }
00299 
00300   DEBUG(if (ShrinkWrapDebugging >= Details) {
00301       DOUT << "-----------------------------------------------------------\n";
00302       DOUT << " Antic/Avail Sets:\n";
00303       DOUT << "-----------------------------------------------------------\n";
00304       DOUT << "iterations = " << iterations << "\n";
00305       DOUT << "-----------------------------------------------------------\n";
00306       DOUT << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n";
00307       DOUT << "-----------------------------------------------------------\n";
00308       for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
00309            MBBI != MBBE; ++MBBI) {
00310         MachineBasicBlock* MBB = MBBI;
00311         dumpSets(MBB);
00312       }
00313       DOUT << "-----------------------------------------------------------\n";
00314     });
00315 }
00316 
00317 /// propagateUsesAroundLoop - copy used register info from MBB to all blocks
00318 /// of the loop given by LP and its parent loops. This prevents spills/restores
00319 /// from being placed in the bodies of loops.
00320 ///
00321 void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
00322   if (! MBB || !LP)
00323     return;
00324 
00325   std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks();
00326   for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) {
00327     MachineBasicBlock* LBB = loopBlocks[i];
00328     if (LBB == MBB)
00329       continue;
00330     if (CSRUsed[LBB].contains(CSRUsed[MBB]))
00331       continue;
00332     CSRUsed[LBB] |= CSRUsed[MBB];
00333   }
00334 }
00335 
00336 /// calculateSets - collect the CSRs used in this function, compute
00337 /// the DF sets that describe the initial minimal regions in the
00338 /// Machine CFG around which CSR spills and restores must be placed.
00339 ///
00340 /// Additionally, this function decides if shrink wrapping should
00341 /// be disabled for the current function, checking the following:
00342 ///  1. the current function has more than 500 MBBs: heuristic limit
00343 ///     on function size to reduce compile time impact of the current
00344 ///     iterative algorithm.
00345 ///  2. all CSRs are used in the entry block.
00346 ///  3. all CSRs are used in all immediate successors of the entry block.
00347 ///  4. all CSRs are used in a subset of blocks, each of which dominates
00348 ///     all return blocks. These blocks, taken as a subgraph of the MCFG,
00349 ///     are equivalent to the entry block since all execution paths pass
00350 ///     through them.
00351 ///
00352 bool PEI::calculateSets(MachineFunction &Fn) {
00353   // Sets used to compute spill, restore placement sets.
00354   const std::vector<CalleeSavedInfo> CSI =
00355     Fn.getFrameInfo()->getCalleeSavedInfo();
00356 
00357   // If no CSRs used, we are done.
00358   if (CSI.empty()) {
00359     DEBUG(if (ShrinkWrapThisFunction)
00360             errs() << "DISABLED: " << Fn.getFunction()->getName()
00361                    << ": uses no callee-saved registers\n");
00362     return false;
00363   }
00364 
00365   // Save refs to entry and return blocks.
00366   EntryBlock = Fn.begin();
00367   for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
00368        MBB != E; ++MBB)
00369     if (isReturnBlock(MBB))
00370       ReturnBlocks.push_back(MBB);
00371 
00372   // Determine if this function has fast exit paths.
00373   DEBUG(if (ShrinkWrapThisFunction)
00374           findFastExitPath());
00375 
00376   // Limit shrink wrapping via the current iterative bit vector
00377   // implementation to functions with <= 500 MBBs.
00378   if (Fn.size() > 500) {
00379     DEBUG(if (ShrinkWrapThisFunction)
00380             errs() << "DISABLED: " << Fn.getFunction()->getName()
00381                    << ": too large (" << Fn.size() << " MBBs)\n");
00382     ShrinkWrapThisFunction = false;
00383   }
00384 
00385   // Return now if not shrink wrapping.
00386   if (! ShrinkWrapThisFunction)
00387     return false;
00388 
00389   // Collect set of used CSRs.
00390   for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
00391     UsedCSRegs.set(inx);
00392   }
00393 
00394   // Walk instructions in all MBBs, create CSRUsed[] sets, choose
00395   // whether or not to shrink wrap this function.
00396   MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
00397   MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>();
00398   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
00399 
00400   bool allCSRUsesInEntryBlock = true;
00401   for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
00402        MBBI != MBBE; ++MBBI) {
00403     MachineBasicBlock* MBB = MBBI;
00404     for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
00405       for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
00406         unsigned Reg = CSI[inx].getReg();
00407         // If instruction I reads or modifies Reg, add it to UsedCSRegs,
00408         // CSRUsed map for the current block.
00409         for (unsigned opInx = 0, opEnd = I->getNumOperands();
00410              opInx != opEnd; ++opInx) {
00411           const MachineOperand &MO = I->getOperand(opInx);
00412           if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
00413             continue;
00414           unsigned MOReg = MO.getReg();
00415           if (!MOReg)
00416             continue;
00417           if (MOReg == Reg ||
00418               (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
00419                TargetRegisterInfo::isPhysicalRegister(Reg) &&
00420                TRI->isSubRegister(Reg, MOReg))) {
00421             // CSR Reg is defined/used in block MBB.
00422             CSRUsed[MBB].set(inx);
00423             // Check for uses in EntryBlock.
00424             if (MBB != EntryBlock)
00425               allCSRUsesInEntryBlock = false;
00426           }
00427         }
00428       }
00429     }
00430 
00431     if (CSRUsed[MBB].empty())
00432       continue;
00433 
00434     // Propagate CSRUsed[MBB] in loops
00435     if (MachineLoop* LP = LI.getLoopFor(MBB)) {
00436       // Add top level loop to work list.
00437       MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP);
00438       MachineLoop* PLP = getTopLevelLoopParent(LP);
00439 
00440       if (! HDR) {
00441         HDR = PLP->getHeader();
00442         assert(HDR->pred_size() > 0 && "Loop header has no predecessors?");
00443         MachineBasicBlock::pred_iterator PI = HDR->pred_begin();
00444         HDR = *PI;
00445       }
00446       TLLoops[HDR] = PLP;
00447 
00448       // Push uses from inside loop to its parent loops,
00449       // or to all other MBBs in its loop.
00450       if (LP->getLoopDepth() > 1) {
00451         for (MachineLoop* PLP = LP->getParentLoop(); PLP;
00452              PLP = PLP->getParentLoop()) {
00453           propagateUsesAroundLoop(MBB, PLP);
00454         }
00455       } else {
00456         propagateUsesAroundLoop(MBB, LP);
00457       }
00458     }
00459   }
00460 
00461   if (allCSRUsesInEntryBlock) {
00462     DEBUG(errs() << "DISABLED: " << Fn.getFunction()->getName()
00463           << ": all CSRs used in EntryBlock\n");
00464     ShrinkWrapThisFunction = false;
00465   } else {
00466     bool allCSRsUsedInEntryFanout = true;
00467     for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
00468            SE = EntryBlock->succ_end(); SI != SE; ++SI) {
00469       MachineBasicBlock* SUCC = *SI;
00470       if (CSRUsed[SUCC] != UsedCSRegs)
00471         allCSRsUsedInEntryFanout = false;
00472     }
00473     if (allCSRsUsedInEntryFanout) {
00474       DEBUG(errs() << "DISABLED: " << Fn.getFunction()->getName()
00475             << ": all CSRs used in imm successors of EntryBlock\n");
00476       ShrinkWrapThisFunction = false;
00477     }
00478   }
00479 
00480   if (ShrinkWrapThisFunction) {
00481     // Check if MBB uses CSRs and dominates all exit nodes.
00482     // Such nodes are equiv. to the entry node w.r.t.
00483     // CSR uses: every path through the function must
00484     // pass through this node. If each CSR is used at least
00485     // once by these nodes, shrink wrapping is disabled.
00486     CSRegSet CSRUsedInChokePoints;
00487     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
00488          MBBI != MBBE; ++MBBI) {
00489       MachineBasicBlock* MBB = MBBI;
00490       if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
00491         continue;
00492       bool dominatesExitNodes = true;
00493       for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
00494         if (! DT.dominates(MBB, ReturnBlocks[ri])) {
00495           dominatesExitNodes = false;
00496           break;
00497         }
00498       if (dominatesExitNodes) {
00499         CSRUsedInChokePoints |= CSRUsed[MBB];
00500         if (CSRUsedInChokePoints == UsedCSRegs) {
00501           DEBUG(errs() << "DISABLED: " << Fn.getFunction()->getName()
00502                 << ": all CSRs used in choke point(s) at "
00503                 << getBasicBlockName(MBB) << "\n");
00504           ShrinkWrapThisFunction = false;
00505           break;
00506         }
00507       }
00508     }
00509   }
00510 
00511   // Return now if we have decided not to apply shrink wrapping
00512   // to the current function.
00513   if (! ShrinkWrapThisFunction)
00514     return false;
00515 
00516   DEBUG({
00517       errs() << "ENABLED: " << Fn.getFunction()->getName();
00518       if (HasFastExitPath)
00519         errs() << " (fast exit path)";
00520       errs() << "\n";
00521       if (ShrinkWrapDebugging >= BasicInfo) {
00522         errs() << "------------------------------"
00523              << "-----------------------------\n";
00524         errs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n";
00525         if (ShrinkWrapDebugging >= Details) {
00526           errs() << "------------------------------"
00527                << "-----------------------------\n";
00528           dumpAllUsed();
00529         }
00530       }
00531     });
00532 
00533   // Build initial DF sets to determine minimal regions in the
00534   // Machine CFG around which CSRs must be spilled and restored.
00535   calculateAnticAvail(Fn);
00536 
00537   return true;
00538 }
00539 
00540 /// addUsesForMEMERegion - add uses of CSRs spilled or restored in
00541 /// multi-entry, multi-exit (MEME) regions so spill and restore
00542 /// placement will not break code that enters or leaves a
00543 /// shrink-wrapped region by inducing spills with no matching
00544 /// restores or restores with no matching spills. A MEME region
00545 /// is a subgraph of the MCFG with multiple entry edges, multiple
00546 /// exit edges, or both. This code propagates use information
00547 /// through the MCFG until all paths requiring spills and restores
00548 /// _outside_ the computed minimal placement regions have been covered.
00549 ///
00550 bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
00551                                SmallVector<MachineBasicBlock*, 4>& blks) {
00552   if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
00553     bool processThisBlock = false;
00554     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00555            SE = MBB->succ_end(); SI != SE; ++SI) {
00556       MachineBasicBlock* SUCC = *SI;
00557       if (SUCC->pred_size() > 1) {
00558         processThisBlock = true;
00559         break;
00560       }
00561     }
00562     if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
00563       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00564              PE = MBB->pred_end(); PI != PE; ++PI) {
00565         MachineBasicBlock* PRED = *PI;
00566         if (PRED->succ_size() > 1) {
00567           processThisBlock = true;
00568           break;
00569         }
00570       }
00571     }
00572     if (! processThisBlock)
00573       return false;
00574   }
00575 
00576   CSRegSet prop;
00577   if (!CSRSave[MBB].empty())
00578     prop = CSRSave[MBB];
00579   else if (!CSRRestore[MBB].empty())
00580     prop = CSRRestore[MBB];
00581   else
00582     prop = CSRUsed[MBB];
00583   if (prop.empty())
00584     return false;
00585 
00586   // Propagate selected bits to successors, predecessors of MBB.
00587   bool addedUses = false;
00588   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00589          SE = MBB->succ_end(); SI != SE; ++SI) {
00590     MachineBasicBlock* SUCC = *SI;
00591     // Self-loop
00592     if (SUCC == MBB)
00593       continue;
00594     if (! CSRUsed[SUCC].contains(prop)) {
00595       CSRUsed[SUCC] |= prop;
00596       addedUses = true;
00597       blks.push_back(SUCC);
00598       DEBUG(if (ShrinkWrapDebugging >= Iterations)
00599               errs() << getBasicBlockName(MBB)
00600                    << "(" << stringifyCSRegSet(prop) << ")->"
00601                    << "successor " << getBasicBlockName(SUCC) << "\n");
00602     }
00603   }
00604   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00605          PE = MBB->pred_end(); PI != PE; ++PI) {
00606     MachineBasicBlock* PRED = *PI;
00607     // Self-loop
00608     if (PRED == MBB)
00609       continue;
00610     if (! CSRUsed[PRED].contains(prop)) {
00611       CSRUsed[PRED] |= prop;
00612       addedUses = true;
00613       blks.push_back(PRED);
00614       DEBUG(if (ShrinkWrapDebugging >= Iterations)
00615               errs() << getBasicBlockName(MBB)
00616                    << "(" << stringifyCSRegSet(prop) << ")->"
00617                    << "predecessor " << getBasicBlockName(PRED) << "\n");
00618     }
00619   }
00620   return addedUses;
00621 }
00622 
00623 /// addUsesForTopLevelLoops - add uses for CSRs used inside top
00624 /// level loops to the exit blocks of those loops.
00625 ///
00626 bool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) {
00627   bool addedUses = false;
00628 
00629   // Place restores for top level loops where needed.
00630   for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator
00631          I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) {
00632     MachineBasicBlock* MBB = I->first;
00633     MachineLoop* LP = I->second;
00634     MachineBasicBlock* HDR = LP->getHeader();
00635     SmallVector<MachineBasicBlock*, 4> exitBlocks;
00636     CSRegSet loopSpills;
00637 
00638     loopSpills = CSRSave[MBB];
00639     if (CSRSave[MBB].empty()) {
00640       loopSpills = CSRUsed[HDR];
00641       assert(!loopSpills.empty() && "No CSRs used in loop?");
00642     } else if (CSRRestore[MBB].contains(CSRSave[MBB]))
00643       continue;
00644 
00645     LP->getExitBlocks(exitBlocks);
00646     assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?");
00647     for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
00648       MachineBasicBlock* EXB = exitBlocks[i];
00649       if (! CSRUsed[EXB].contains(loopSpills)) {
00650         CSRUsed[EXB] |= loopSpills;
00651         addedUses = true;
00652         DEBUG(if (ShrinkWrapDebugging >= Iterations)
00653                 errs() << "LOOP " << getBasicBlockName(MBB)
00654                      << "(" << stringifyCSRegSet(loopSpills) << ")->"
00655                      << getBasicBlockName(EXB) << "\n");
00656         if (EXB->succ_size() > 1 || EXB->pred_size() > 1)
00657           blks.push_back(EXB);
00658       }
00659     }
00660   }
00661   return addedUses;
00662 }
00663 
00664 /// calcSpillPlacements - determine which CSRs should be spilled
00665 /// in MBB using AnticIn sets of MBB's predecessors, keeping track
00666 /// of changes to spilled reg sets. Add MBB to the set of blocks
00667 /// that need to be processed for propagating use info to cover
00668 /// multi-entry/exit regions.
00669 ///
00670 bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
00671                               SmallVector<MachineBasicBlock*, 4> &blks,
00672                               CSRegBlockMap &prevSpills) {
00673   bool placedSpills = false;
00674   // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB)
00675   CSRegSet anticInPreds;
00676   SmallVector<MachineBasicBlock*, 4> predecessors;
00677   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
00678          PE = MBB->pred_end(); PI != PE; ++PI) {
00679     MachineBasicBlock* PRED = *PI;
00680     if (PRED != MBB)
00681       predecessors.push_back(PRED);
00682   }
00683   unsigned i = 0, e = predecessors.size();
00684   if (i != e) {
00685     MachineBasicBlock* PRED = predecessors[i];
00686     anticInPreds = UsedCSRegs - AnticIn[PRED];
00687     for (++i; i != e; ++i) {
00688       PRED = predecessors[i];
00689       anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
00690     }
00691   } else {
00692     // Handle uses in entry blocks (which have no predecessors).
00693     // This is necessary because the DFA formulation assumes the
00694     // entry and (multiple) exit nodes cannot have CSR uses, which
00695     // is not the case in the real world.
00696     anticInPreds = UsedCSRegs;
00697   }
00698   // Compute spills required at MBB:
00699   CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
00700 
00701   if (! CSRSave[MBB].empty()) {
00702     if (MBB == EntryBlock) {
00703       for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
00704         CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
00705     } else {
00706       // Reset all regs spilled in MBB that are also spilled in EntryBlock.
00707       if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
00708         CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
00709       }
00710     }
00711   }
00712   placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
00713   prevSpills[MBB] = CSRSave[MBB];
00714   // Remember this block for adding restores to successor
00715   // blocks for multi-entry region.
00716   if (placedSpills)
00717     blks.push_back(MBB);
00718 
00719   DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
00720           errs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
00721                << stringifyCSRegSet(CSRSave[MBB]) << "\n");
00722 
00723   return placedSpills;
00724 }
00725 
00726 /// calcRestorePlacements - determine which CSRs should be restored
00727 /// in MBB using AvailOut sets of MBB's succcessors, keeping track
00728 /// of changes to restored reg sets. Add MBB to the set of blocks
00729 /// that need to be processed for propagating use info to cover
00730 /// multi-entry/exit regions.
00731 ///
00732 bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
00733                                 SmallVector<MachineBasicBlock*, 4> &blks,
00734                                 CSRegBlockMap &prevRestores) {
00735   bool placedRestores = false;
00736   // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB)
00737   CSRegSet availOutSucc;
00738   SmallVector<MachineBasicBlock*, 4> successors;
00739   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00740          SE = MBB->succ_end(); SI != SE; ++SI) {
00741     MachineBasicBlock* SUCC = *SI;
00742     if (SUCC != MBB)
00743       successors.push_back(SUCC);
00744   }
00745   unsigned i = 0, e = successors.size();
00746   if (i != e) {
00747     MachineBasicBlock* SUCC = successors[i];
00748     availOutSucc = UsedCSRegs - AvailOut[SUCC];
00749     for (++i; i != e; ++i) {
00750       SUCC = successors[i];
00751       availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
00752     }
00753   } else {
00754     if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
00755       // Handle uses in return blocks (which have no successors).
00756       // This is necessary because the DFA formulation assumes the
00757       // entry and (multiple) exit nodes cannot have CSR uses, which
00758       // is not the case in the real world.
00759       availOutSucc = UsedCSRegs;
00760     }
00761   }
00762   // Compute restores required at MBB:
00763   CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
00764 
00765   // Postprocess restore placements at MBB.
00766   // Remove the CSRs that are restored in the return blocks.
00767   // Lest this be confusing, note that:
00768   // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks.
00769   if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
00770     if (! CSRSave[EntryBlock].empty())
00771       CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
00772   }
00773   placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
00774   prevRestores[MBB] = CSRRestore[MBB];
00775   // Remember this block for adding saves to predecessor
00776   // blocks for multi-entry region.
00777   if (placedRestores)
00778     blks.push_back(MBB);
00779 
00780   DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
00781           errs() << "RESTORE[" << getBasicBlockName(MBB) << "] = "
00782                << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
00783 
00784   return placedRestores;
00785 }
00786 
00787 /// placeSpillsAndRestores - place spills and restores of CSRs
00788 /// used in MBBs in minimal regions that contain the uses.
00789 ///
00790 void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
00791   CSRegBlockMap prevCSRSave;
00792   CSRegBlockMap prevCSRRestore;
00793   SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks;
00794   bool changed = true;
00795   unsigned iterations = 0;
00796 
00797   // Iterate computation of spill and restore placements in the MCFG until:
00798   //   1. CSR use info has been fully propagated around the MCFG, and
00799   //   2. computation of CSRSave[], CSRRestore[] reach fixed points.
00800   while (changed) {
00801     changed = false;
00802     ++iterations;
00803 
00804     DEBUG(if (ShrinkWrapDebugging >= Iterations)
00805             errs() << "iter " << iterations
00806                  << " --------------------------------------------------\n");
00807 
00808     // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG,
00809     // which determines the placements of spills and restores.
00810     // Keep track of changes to spills, restores in each iteration to
00811     // minimize the total iterations.
00812     bool SRChanged = false;
00813     for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
00814          MBBI != MBBE; ++MBBI) {
00815       MachineBasicBlock* MBB = MBBI;
00816 
00817       // Place spills for CSRs in MBB.
00818       SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
00819 
00820       // Place restores for CSRs in MBB.
00821       SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
00822     }
00823 
00824     // Add uses of CSRs used inside loops where needed.
00825     changed |= addUsesForTopLevelLoops(cvBlocks);
00826 
00827     // Add uses for CSRs spilled or restored at branch, join points.
00828     if (changed || SRChanged) {
00829       while (! cvBlocks.empty()) {
00830         MachineBasicBlock* MBB = cvBlocks.pop_back_val();
00831         changed |= addUsesForMEMERegion(MBB, ncvBlocks);
00832       }
00833       if (! ncvBlocks.empty()) {
00834         cvBlocks = ncvBlocks;
00835         ncvBlocks.clear();
00836       }
00837     }
00838 
00839     if (changed) {
00840       calculateAnticAvail(Fn);
00841       CSRSave.clear();
00842       CSRRestore.clear();
00843     }
00844   }
00845 
00846   // Check for effectiveness:
00847   //  SR0 = {r | r in CSRSave[EntryBlock], CSRRestore[RB], RB in ReturnBlocks}
00848   //  numSRReduced = |(UsedCSRegs - SR0)|, approx. SR0 by CSRSave[EntryBlock]
00849   // Gives a measure of how many CSR spills have been moved from EntryBlock
00850   // to minimal regions enclosing their uses.
00851   CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]);
00852   unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count();
00853   numSRReduced += numSRReducedThisFunc;
00854   DEBUG(if (ShrinkWrapDebugging >= BasicInfo) {
00855       errs() << "-----------------------------------------------------------\n";
00856       errs() << "total iterations = " << iterations << " ( "
00857            << Fn.getFunction()->getName()
00858            << " " << numSRReducedThisFunc
00859            << " " << Fn.size()
00860            << " )\n";
00861       errs() << "-----------------------------------------------------------\n";
00862       dumpSRSets();
00863       errs() << "-----------------------------------------------------------\n";
00864       if (numSRReducedThisFunc)
00865         verifySpillRestorePlacement();
00866     });
00867 }
00868 
00869 // Debugging methods.
00870 #ifndef NDEBUG
00871 /// findFastExitPath - debugging method used to detect functions
00872 /// with at least one path from the entry block to a return block
00873 /// directly or which has a very small number of edges.
00874 ///
00875 void PEI::findFastExitPath() {
00876   if (! EntryBlock)
00877     return;
00878   // Fina a path from EntryBlock to any return block that does not branch:
00879   //        Entry
00880   //          |     ...
00881   //          v      |
00882   //         B1<-----+
00883   //          |
00884   //          v
00885   //       Return
00886   for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
00887          SE = EntryBlock->succ_end(); SI != SE; ++SI) {
00888     MachineBasicBlock* SUCC = *SI;
00889 
00890     // Assume positive, disprove existence of fast path.
00891     HasFastExitPath = true;
00892 
00893     // Check the immediate successors.
00894     if (isReturnBlock(SUCC)) {
00895       if (ShrinkWrapDebugging >= BasicInfo)
00896         errs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
00897              << "->" << getBasicBlockName(SUCC) << "\n";
00898       break;
00899     }
00900     // Traverse df from SUCC, look for a branch block.
00901     std::string exitPath = getBasicBlockName(SUCC);
00902     for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
00903            BE = df_end(SUCC); BI != BE; ++BI) {
00904       MachineBasicBlock* SBB = *BI;
00905       // Reject paths with branch nodes.
00906       if (SBB->succ_size() > 1) {
00907         HasFastExitPath = false;
00908         break;
00909       }
00910       exitPath += "->" + getBasicBlockName(SBB);
00911     }
00912     if (HasFastExitPath) {
00913       if (ShrinkWrapDebugging >= BasicInfo)
00914         errs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
00915              << "->" << exitPath << "\n";
00916       break;
00917     }
00918   }
00919 }
00920 
00921 /// verifySpillRestorePlacement - check the current spill/restore
00922 /// sets for safety. Attempt to find spills without restores or
00923 /// restores without spills.
00924 /// Spills: walk df from each MBB in spill set ensuring that
00925 ///         all CSRs spilled at MMBB are restored on all paths
00926 ///         from MBB to all exit blocks.
00927 /// Restores: walk idf from each MBB in restore set ensuring that
00928 ///           all CSRs restored at MBB are spilled on all paths
00929 ///           reaching MBB.
00930 ///
00931 void PEI::verifySpillRestorePlacement() {
00932   unsigned numReturnBlocks = 0;
00933   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
00934        MBBI != MBBE; ++MBBI) {
00935     MachineBasicBlock* MBB = MBBI;
00936     if (isReturnBlock(MBB) || MBB->succ_size() == 0)
00937       ++numReturnBlocks;
00938   }
00939   for (CSRegBlockMap::iterator BI = CSRSave.begin(),
00940          BE = CSRSave.end(); BI != BE; ++BI) {
00941     MachineBasicBlock* MBB = BI->first;
00942     CSRegSet spilled = BI->second;
00943     CSRegSet restored;
00944 
00945     if (spilled.empty())
00946       continue;
00947 
00948     DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
00949          << stringifyCSRegSet(spilled)
00950          << "  RESTORE[" << getBasicBlockName(MBB) << "] = "
00951          << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
00952 
00953     if (CSRRestore[MBB].intersects(spilled)) {
00954       restored |= (CSRRestore[MBB] & spilled);
00955     }
00956 
00957     // Walk depth first from MBB to find restores of all CSRs spilled at MBB:
00958     // we must find restores for all spills w/no intervening spills on all
00959     // paths from MBB to all return blocks.
00960     for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB),
00961            BE = df_end(MBB); BI != BE; ++BI) {
00962       MachineBasicBlock* SBB = *BI;
00963       if (SBB == MBB)
00964         continue;
00965       // Stop when we encounter spills of any CSRs spilled at MBB that
00966       // have not yet been seen to be restored.
00967       if (CSRSave[SBB].intersects(spilled) &&
00968           !restored.contains(CSRSave[SBB] & spilled))
00969         break;
00970       // Collect the CSRs spilled at MBB that are restored
00971       // at this DF successor of MBB.
00972       if (CSRRestore[SBB].intersects(spilled))
00973         restored |= (CSRRestore[SBB] & spilled);
00974       // If we are at a retun block, check that the restores
00975       // we have seen so far exhaust the spills at MBB, then
00976       // reset the restores.
00977       if (isReturnBlock(SBB) || SBB->succ_size() == 0) {
00978         if (restored != spilled) {
00979           CSRegSet notRestored = (spilled - restored);
00980           DEBUG(errs() << MF->getFunction()->getName() << ": "
00981                 << stringifyCSRegSet(notRestored)
00982                 << " spilled at " << getBasicBlockName(MBB)
00983                 << " are never restored on path to return "
00984                 << getBasicBlockName(SBB) << "\n");
00985         }
00986         restored.clear();
00987       }
00988     }
00989   }
00990 
00991   // Check restore placements.
00992   for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
00993          BE = CSRRestore.end(); BI != BE; ++BI) {
00994     MachineBasicBlock* MBB = BI->first;
00995     CSRegSet restored = BI->second;
00996     CSRegSet spilled;
00997 
00998     if (restored.empty())
00999       continue;
01000 
01001     DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
01002          << stringifyCSRegSet(CSRSave[MBB])
01003          << "  RESTORE[" << getBasicBlockName(MBB) << "] = "
01004          << stringifyCSRegSet(restored) << "\n";
01005 
01006     if (CSRSave[MBB].intersects(restored)) {
01007       spilled |= (CSRSave[MBB] & restored);
01008     }
01009     // Walk inverse depth first from MBB to find spills of all
01010     // CSRs restored at MBB:
01011     for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB),
01012            BE = idf_end(MBB); BI != BE; ++BI) {
01013       MachineBasicBlock* PBB = *BI;
01014       if (PBB == MBB)
01015         continue;
01016       // Stop when we encounter restores of any CSRs restored at MBB that
01017       // have not yet been seen to be spilled.
01018       if (CSRRestore[PBB].intersects(restored) &&
01019           !spilled.contains(CSRRestore[PBB] & restored))
01020         break;
01021       // Collect the CSRs restored at MBB that are spilled
01022       // at this DF predecessor of MBB.
01023       if (CSRSave[PBB].intersects(restored))
01024         spilled |= (CSRSave[PBB] & restored);
01025     }
01026     if (spilled != restored) {
01027       CSRegSet notSpilled = (restored - spilled);
01028       DEBUG(errs() << MF->getFunction()->getName() << ": "
01029             << stringifyCSRegSet(notSpilled)
01030             << " restored at " << getBasicBlockName(MBB)
01031             << " are never spilled\n");
01032     }
01033   }
01034 }
01035 
01036 // Debugging print methods.
01037 std::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) {
01038   if (!MBB)
01039     return "";
01040 
01041   if (MBB->getBasicBlock())
01042     return MBB->getBasicBlock()->getNameStr();
01043 
01044   std::ostringstream name;
01045   name << "_MBB_" << MBB->getNumber();
01046   return name.str();
01047 }
01048 
01049 std::string PEI::stringifyCSRegSet(const CSRegSet& s) {
01050   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
01051   const std::vector<CalleeSavedInfo> CSI =
01052     MF->getFrameInfo()->getCalleeSavedInfo();
01053 
01054   std::ostringstream srep;
01055   if (CSI.size() == 0) {
01056     srep << "[]";
01057     return srep.str();
01058   }
01059   srep << "[";
01060   CSRegSet::iterator I = s.begin(), E = s.end();
01061   if (I != E) {
01062     unsigned reg = CSI[*I].getReg();
01063     srep << TRI->getName(reg);
01064     for (++I; I != E; ++I) {
01065       reg = CSI[*I].getReg();
01066       srep << ",";
01067       srep << TRI->getName(reg);
01068     }
01069   }
01070   srep << "]";
01071   return srep.str();
01072 }
01073 
01074 void PEI::dumpSet(const CSRegSet& s) {
01075   DOUT << stringifyCSRegSet(s) << "\n";
01076 }
01077 
01078 void PEI::dumpUsed(MachineBasicBlock* MBB) {
01079   if (MBB) {
01080     DOUT << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
01081          << stringifyCSRegSet(CSRUsed[MBB])  << "\n";
01082   }
01083 }
01084 
01085 void PEI::dumpAllUsed() {
01086     for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
01087          MBBI != MBBE; ++MBBI) {
01088       MachineBasicBlock* MBB = MBBI;
01089       dumpUsed(MBB);
01090     }
01091 }
01092 
01093 void PEI::dumpSets(MachineBasicBlock* MBB) {
01094   if (MBB) {
01095     DOUT << getBasicBlockName(MBB)           << " | "
01096          << stringifyCSRegSet(CSRUsed[MBB])  << " | "
01097          << stringifyCSRegSet(AnticIn[MBB])  << " | "
01098          << stringifyCSRegSet(AnticOut[MBB]) << " | "
01099          << stringifyCSRegSet(AvailIn[MBB])  << " | "
01100          << stringifyCSRegSet(AvailOut[MBB]) << "\n";
01101   }
01102 }
01103 
01104 void PEI::dumpSets1(MachineBasicBlock* MBB) {
01105   if (MBB) {
01106     DOUT << getBasicBlockName(MBB)             << " | "
01107          << stringifyCSRegSet(CSRUsed[MBB])    << " | "
01108          << stringifyCSRegSet(AnticIn[MBB])    << " | "
01109          << stringifyCSRegSet(AnticOut[MBB])   << " | "
01110          << stringifyCSRegSet(AvailIn[MBB])    << " | "
01111          << stringifyCSRegSet(AvailOut[MBB])   << " | "
01112          << stringifyCSRegSet(CSRSave[MBB])    << " | "
01113          << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
01114   }
01115 }
01116 
01117 void PEI::dumpAllSets() {
01118     for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
01119          MBBI != MBBE; ++MBBI) {
01120       MachineBasicBlock* MBB = MBBI;
01121       dumpSets1(MBB);
01122     }
01123 }
01124 
01125 void PEI::dumpSRSets() {
01126   for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
01127        MBB != E; ++MBB) {
01128     if (! CSRSave[MBB].empty()) {
01129       DOUT << "SAVE[" << getBasicBlockName(MBB) << "] = "
01130            << stringifyCSRegSet(CSRSave[MBB]);
01131       if (CSRRestore[MBB].empty())
01132         DOUT << "\n";
01133     }
01134     if (! CSRRestore[MBB].empty()) {
01135       if (! CSRSave[MBB].empty())
01136         DOUT << "    ";
01137       DOUT << "RESTORE[" << getBasicBlockName(MBB) << "] = "
01138            << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
01139     }
01140   }
01141 }
01142 #endif