LLVM API Documentation
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