1193323Sed//===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements a shrink wrapping variant of prolog/epilog insertion: 11193323Sed// - Spills and restores of callee-saved registers (CSRs) are placed in the 12193323Sed// machine CFG to tightly surround their uses so that execution paths that 13193323Sed// do not use CSRs do not pay the spill/restore penalty. 14193323Sed// 15193323Sed// - Avoiding placment of spills/restores in loops: if a CSR is used inside a 16193323Sed// loop the spills are placed in the loop preheader, and restores are 17193323Sed// placed in the loop exit nodes (the successors of loop _exiting_ nodes). 18193323Sed// 19193323Sed// - Covering paths without CSR uses: 20193323Sed// If a region in a CFG uses CSRs and has multiple entry and/or exit points, 21193323Sed// the use info for the CSRs inside the region is propagated outward in the 22193323Sed// CFG to ensure validity of the spill/restore placements. This decreases 23193323Sed// the effectiveness of shrink wrapping but does not require edge splitting 24193323Sed// in the machine CFG. 25193323Sed// 26193323Sed// This shrink wrapping implementation uses an iterative analysis to determine 27193323Sed// which basic blocks require spills and restores for CSRs. 28193323Sed// 29193323Sed// This pass uses MachineDominators and MachineLoopInfo. Loop information 30193323Sed// is used to prevent placement of callee-saved register spills/restores 31193323Sed// in the bodies of loops. 32193323Sed// 33193323Sed//===----------------------------------------------------------------------===// 34193323Sed 35193323Sed#define DEBUG_TYPE "shrink-wrap" 36193323Sed 37193323Sed#include "PrologEpilogInserter.h" 38249423Sdim#include "llvm/ADT/DenseMap.h" 39249423Sdim#include "llvm/ADT/PostOrderIterator.h" 40249423Sdim#include "llvm/ADT/STLExtras.h" 41249423Sdim#include "llvm/ADT/SparseBitVector.h" 42249423Sdim#include "llvm/ADT/Statistic.h" 43193323Sed#include "llvm/CodeGen/MachineDominators.h" 44249423Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 45249423Sdim#include "llvm/CodeGen/MachineInstr.h" 46193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 47193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 48193323Sed#include "llvm/Support/CommandLine.h" 49193323Sed#include "llvm/Support/Compiler.h" 50193323Sed#include "llvm/Support/Debug.h" 51249423Sdim#include "llvm/Target/TargetMachine.h" 52249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 53193323Sed#include <sstream> 54193323Sed 55193323Sedusing namespace llvm; 56193323Sed 57193323SedSTATISTIC(numSRReduced, "Number of CSR spills+restores reduced."); 58193323Sed 59193323Sed// Shrink Wrapping: 60193323Sedstatic cl::opt<bool> 61193323SedShrinkWrapping("shrink-wrap", 62193323Sed cl::desc("Shrink wrap callee-saved register spills/restores")); 63193323Sed 64193323Sed// Shrink wrap only the specified function, a debugging aid. 65193323Sedstatic cl::opt<std::string> 66193323SedShrinkWrapFunc("shrink-wrap-func", cl::Hidden, 67193323Sed cl::desc("Shrink wrap the specified function"), 68193323Sed cl::value_desc("funcname"), 69193323Sed cl::init("")); 70193323Sed 71193323Sed// Debugging level for shrink wrapping. 72193323Sedenum ShrinkWrapDebugLevel { 73251662Sdim Disabled, BasicInfo, Iterations, Details 74193323Sed}; 75193323Sed 76193323Sedstatic cl::opt<enum ShrinkWrapDebugLevel> 77193323SedShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden, 78193323Sed cl::desc("Print shrink wrapping debugging information"), 79193323Sed cl::values( 80251662Sdim clEnumVal(Disabled , "disable debug output"), 81193323Sed clEnumVal(BasicInfo , "print basic DF sets"), 82193323Sed clEnumVal(Iterations, "print SR sets for each iteration"), 83193323Sed clEnumVal(Details , "print all DF sets"), 84193323Sed clEnumValEnd)); 85193323Sed 86193323Sed 87193323Sedvoid PEI::getAnalysisUsage(AnalysisUsage &AU) const { 88193323Sed AU.setPreservesCFG(); 89193323Sed if (ShrinkWrapping || ShrinkWrapFunc != "") { 90193323Sed AU.addRequired<MachineLoopInfo>(); 91193323Sed AU.addRequired<MachineDominatorTree>(); 92193323Sed } 93193323Sed AU.addPreserved<MachineLoopInfo>(); 94193323Sed AU.addPreserved<MachineDominatorTree>(); 95234353Sdim AU.addRequired<TargetPassConfig>(); 96193323Sed MachineFunctionPass::getAnalysisUsage(AU); 97193323Sed} 98193323Sed 99193323Sed//===----------------------------------------------------------------------===// 100193323Sed// ShrinkWrapping implementation 101193323Sed//===----------------------------------------------------------------------===// 102193323Sed 103193323Sed// Convienences for dealing with machine loops. 104193323SedMachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) { 105193323Sed assert(LP && "Machine loop is NULL."); 106193323Sed MachineBasicBlock* PHDR = LP->getLoopPreheader(); 107193323Sed MachineLoop* PLP = LP->getParentLoop(); 108193323Sed while (PLP) { 109193323Sed PHDR = PLP->getLoopPreheader(); 110193323Sed PLP = PLP->getParentLoop(); 111193323Sed } 112193323Sed return PHDR; 113193323Sed} 114193323Sed 115193323SedMachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) { 116193323Sed if (LP == 0) 117193323Sed return 0; 118193323Sed MachineLoop* PLP = LP->getParentLoop(); 119193323Sed while (PLP) { 120193323Sed LP = PLP; 121193323Sed PLP = PLP->getParentLoop(); 122193323Sed } 123193323Sed return LP; 124193323Sed} 125193323Sed 126193323Sedbool PEI::isReturnBlock(MachineBasicBlock* MBB) { 127234353Sdim return (MBB && !MBB->empty() && MBB->back().isReturn()); 128193323Sed} 129193323Sed 130193323Sed// Initialize shrink wrapping DFA sets, called before iterations. 131193323Sedvoid PEI::clearAnticAvailSets() { 132193323Sed AnticIn.clear(); 133193323Sed AnticOut.clear(); 134193323Sed AvailIn.clear(); 135193323Sed AvailOut.clear(); 136193323Sed} 137193323Sed 138193323Sed// Clear all sets constructed by shrink wrapping. 139193323Sedvoid PEI::clearAllSets() { 140193323Sed ReturnBlocks.clear(); 141193323Sed clearAnticAvailSets(); 142193323Sed UsedCSRegs.clear(); 143193323Sed CSRUsed.clear(); 144193323Sed TLLoops.clear(); 145193323Sed CSRSave.clear(); 146193323Sed CSRRestore.clear(); 147193323Sed} 148193323Sed 149193323Sed// Initialize all shrink wrapping data. 150193323Sedvoid PEI::initShrinkWrappingInfo() { 151193323Sed clearAllSets(); 152193323Sed EntryBlock = 0; 153193323Sed#ifndef NDEBUG 154193323Sed HasFastExitPath = false; 155193323Sed#endif 156193323Sed ShrinkWrapThisFunction = ShrinkWrapping; 157193323Sed // DEBUG: enable or disable shrink wrapping for the current function 158193323Sed // via --shrink-wrap-func=<funcname>. 159193323Sed#ifndef NDEBUG 160193323Sed if (ShrinkWrapFunc != "") { 161243830Sdim std::string MFName = MF->getName().str(); 162193323Sed ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc); 163193323Sed } 164193323Sed#endif 165193323Sed} 166193323Sed 167193323Sed 168193323Sed/// placeCSRSpillsAndRestores - determine which MBBs of the function 169193323Sed/// need save, restore code for callee-saved registers by doing a DF analysis 170193323Sed/// similar to the one used in code motion (GVNPRE). This produces maps of MBBs 171193323Sed/// to sets of registers (CSRs) for saves and restores. MachineLoopInfo 172193323Sed/// is used to ensure that CSR save/restore code is not placed inside loops. 173193323Sed/// This function computes the maps of MBBs -> CSRs to spill and restore 174193323Sed/// in CSRSave, CSRRestore. 175193323Sed/// 176193323Sed/// If shrink wrapping is not being performed, place all spills in 177193323Sed/// the entry block, all restores in return blocks. In this case, 178193323Sed/// CSRSave has a single mapping, CSRRestore has mappings for each 179193323Sed/// return block. 180193323Sed/// 181193323Sedvoid PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) { 182193323Sed 183193323Sed DEBUG(MF = &Fn); 184193323Sed 185193323Sed initShrinkWrappingInfo(); 186193323Sed 187193323Sed DEBUG(if (ShrinkWrapThisFunction) { 188202375Srdivacky dbgs() << "Place CSR spills/restores for " 189243830Sdim << MF->getName() << "\n"; 190193323Sed }); 191193323Sed 192193323Sed if (calculateSets(Fn)) 193193323Sed placeSpillsAndRestores(Fn); 194193323Sed} 195193323Sed 196193323Sed/// calcAnticInOut - calculate the anticipated in/out reg sets 197193323Sed/// for the given MBB by looking forward in the MCFG at MBB's 198193323Sed/// successors. 199193323Sed/// 200193323Sedbool PEI::calcAnticInOut(MachineBasicBlock* MBB) { 201193323Sed bool changed = false; 202193323Sed 203193323Sed // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB)) 204193323Sed SmallVector<MachineBasicBlock*, 4> successors; 205193323Sed for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 206193323Sed SE = MBB->succ_end(); SI != SE; ++SI) { 207193323Sed MachineBasicBlock* SUCC = *SI; 208193323Sed if (SUCC != MBB) 209193323Sed successors.push_back(SUCC); 210193323Sed } 211193323Sed 212193323Sed unsigned i = 0, e = successors.size(); 213193323Sed if (i != e) { 214193323Sed CSRegSet prevAnticOut = AnticOut[MBB]; 215193323Sed MachineBasicBlock* SUCC = successors[i]; 216193323Sed 217193323Sed AnticOut[MBB] = AnticIn[SUCC]; 218193323Sed for (++i; i != e; ++i) { 219193323Sed SUCC = successors[i]; 220193323Sed AnticOut[MBB] &= AnticIn[SUCC]; 221193323Sed } 222193323Sed if (prevAnticOut != AnticOut[MBB]) 223193323Sed changed = true; 224193323Sed } 225193323Sed 226193323Sed // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]); 227193323Sed CSRegSet prevAnticIn = AnticIn[MBB]; 228193323Sed AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB]; 229218893Sdim if (prevAnticIn != AnticIn[MBB]) 230193323Sed changed = true; 231193323Sed return changed; 232193323Sed} 233193323Sed 234193323Sed/// calcAvailInOut - calculate the available in/out reg sets 235193323Sed/// for the given MBB by looking backward in the MCFG at MBB's 236193323Sed/// predecessors. 237193323Sed/// 238193323Sedbool PEI::calcAvailInOut(MachineBasicBlock* MBB) { 239193323Sed bool changed = false; 240193323Sed 241193323Sed // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB)) 242193323Sed SmallVector<MachineBasicBlock*, 4> predecessors; 243193323Sed for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 244193323Sed PE = MBB->pred_end(); PI != PE; ++PI) { 245193323Sed MachineBasicBlock* PRED = *PI; 246193323Sed if (PRED != MBB) 247193323Sed predecessors.push_back(PRED); 248193323Sed } 249193323Sed 250193323Sed unsigned i = 0, e = predecessors.size(); 251193323Sed if (i != e) { 252193323Sed CSRegSet prevAvailIn = AvailIn[MBB]; 253193323Sed MachineBasicBlock* PRED = predecessors[i]; 254193323Sed 255193323Sed AvailIn[MBB] = AvailOut[PRED]; 256193323Sed for (++i; i != e; ++i) { 257193323Sed PRED = predecessors[i]; 258193323Sed AvailIn[MBB] &= AvailOut[PRED]; 259193323Sed } 260193323Sed if (prevAvailIn != AvailIn[MBB]) 261193323Sed changed = true; 262193323Sed } 263193323Sed 264193323Sed // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]); 265193323Sed CSRegSet prevAvailOut = AvailOut[MBB]; 266193323Sed AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB]; 267218893Sdim if (prevAvailOut != AvailOut[MBB]) 268193323Sed changed = true; 269193323Sed return changed; 270193323Sed} 271193323Sed 272193323Sed/// calculateAnticAvail - build the sets anticipated and available 273193323Sed/// registers in the MCFG of the current function iteratively, 274193323Sed/// doing a combined forward and backward analysis. 275193323Sed/// 276193323Sedvoid PEI::calculateAnticAvail(MachineFunction &Fn) { 277193323Sed // Initialize data flow sets. 278193323Sed clearAnticAvailSets(); 279193323Sed 280221345Sdim // Calculate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG. 281193323Sed bool changed = true; 282193323Sed unsigned iterations = 0; 283193323Sed while (changed) { 284193323Sed changed = false; 285193323Sed ++iterations; 286193323Sed for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 287193323Sed MBBI != MBBE; ++MBBI) { 288193323Sed MachineBasicBlock* MBB = MBBI; 289193323Sed 290193323Sed // Calculate anticipated in, out regs at MBB from 291193323Sed // anticipated at successors of MBB. 292193323Sed changed |= calcAnticInOut(MBB); 293193323Sed 294193323Sed // Calculate available in, out regs at MBB from 295193323Sed // available at predecessors of MBB. 296193323Sed changed |= calcAvailInOut(MBB); 297193323Sed } 298193323Sed } 299193323Sed 300198090Srdivacky DEBUG({ 301198090Srdivacky if (ShrinkWrapDebugging >= Details) { 302202375Srdivacky dbgs() 303198090Srdivacky << "-----------------------------------------------------------\n" 304198090Srdivacky << " Antic/Avail Sets:\n" 305198090Srdivacky << "-----------------------------------------------------------\n" 306198090Srdivacky << "iterations = " << iterations << "\n" 307198090Srdivacky << "-----------------------------------------------------------\n" 308198090Srdivacky << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n" 309198090Srdivacky << "-----------------------------------------------------------\n"; 310198090Srdivacky 311198090Srdivacky for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 312198090Srdivacky MBBI != MBBE; ++MBBI) { 313198090Srdivacky MachineBasicBlock* MBB = MBBI; 314198090Srdivacky dumpSets(MBB); 315198090Srdivacky } 316198090Srdivacky 317202375Srdivacky dbgs() 318198090Srdivacky << "-----------------------------------------------------------\n"; 319193323Sed } 320193323Sed }); 321193323Sed} 322193323Sed 323193323Sed/// propagateUsesAroundLoop - copy used register info from MBB to all blocks 324193323Sed/// of the loop given by LP and its parent loops. This prevents spills/restores 325193323Sed/// from being placed in the bodies of loops. 326193323Sed/// 327193323Sedvoid PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) { 328193323Sed if (! MBB || !LP) 329193323Sed return; 330193323Sed 331193323Sed std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks(); 332193323Sed for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) { 333193323Sed MachineBasicBlock* LBB = loopBlocks[i]; 334193323Sed if (LBB == MBB) 335193323Sed continue; 336193323Sed if (CSRUsed[LBB].contains(CSRUsed[MBB])) 337193323Sed continue; 338193323Sed CSRUsed[LBB] |= CSRUsed[MBB]; 339193323Sed } 340193323Sed} 341193323Sed 342193323Sed/// calculateSets - collect the CSRs used in this function, compute 343193323Sed/// the DF sets that describe the initial minimal regions in the 344193323Sed/// Machine CFG around which CSR spills and restores must be placed. 345193323Sed/// 346193323Sed/// Additionally, this function decides if shrink wrapping should 347193323Sed/// be disabled for the current function, checking the following: 348193323Sed/// 1. the current function has more than 500 MBBs: heuristic limit 349193323Sed/// on function size to reduce compile time impact of the current 350193323Sed/// iterative algorithm. 351193323Sed/// 2. all CSRs are used in the entry block. 352193323Sed/// 3. all CSRs are used in all immediate successors of the entry block. 353193323Sed/// 4. all CSRs are used in a subset of blocks, each of which dominates 354193323Sed/// all return blocks. These blocks, taken as a subgraph of the MCFG, 355193323Sed/// are equivalent to the entry block since all execution paths pass 356193323Sed/// through them. 357193323Sed/// 358193323Sedbool PEI::calculateSets(MachineFunction &Fn) { 359193323Sed // Sets used to compute spill, restore placement sets. 360193323Sed const std::vector<CalleeSavedInfo> CSI = 361193323Sed Fn.getFrameInfo()->getCalleeSavedInfo(); 362193323Sed 363193323Sed // If no CSRs used, we are done. 364193323Sed if (CSI.empty()) { 365193323Sed DEBUG(if (ShrinkWrapThisFunction) 366243830Sdim dbgs() << "DISABLED: " << Fn.getName() 367198090Srdivacky << ": uses no callee-saved registers\n"); 368193323Sed return false; 369193323Sed } 370193323Sed 371193323Sed // Save refs to entry and return blocks. 372193323Sed EntryBlock = Fn.begin(); 373193323Sed for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end(); 374193323Sed MBB != E; ++MBB) 375193323Sed if (isReturnBlock(MBB)) 376193323Sed ReturnBlocks.push_back(MBB); 377193323Sed 378193323Sed // Determine if this function has fast exit paths. 379193323Sed DEBUG(if (ShrinkWrapThisFunction) 380193323Sed findFastExitPath()); 381193323Sed 382193323Sed // Limit shrink wrapping via the current iterative bit vector 383193323Sed // implementation to functions with <= 500 MBBs. 384193323Sed if (Fn.size() > 500) { 385193323Sed DEBUG(if (ShrinkWrapThisFunction) 386243830Sdim dbgs() << "DISABLED: " << Fn.getName() 387198090Srdivacky << ": too large (" << Fn.size() << " MBBs)\n"); 388193323Sed ShrinkWrapThisFunction = false; 389193323Sed } 390193323Sed 391193323Sed // Return now if not shrink wrapping. 392193323Sed if (! ShrinkWrapThisFunction) 393193323Sed return false; 394193323Sed 395193323Sed // Collect set of used CSRs. 396193323Sed for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) { 397193323Sed UsedCSRegs.set(inx); 398193323Sed } 399193323Sed 400193323Sed // Walk instructions in all MBBs, create CSRUsed[] sets, choose 401193323Sed // whether or not to shrink wrap this function. 402193323Sed MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>(); 403193323Sed MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>(); 404193323Sed const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 405193323Sed 406193323Sed bool allCSRUsesInEntryBlock = true; 407193323Sed for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 408193323Sed MBBI != MBBE; ++MBBI) { 409193323Sed MachineBasicBlock* MBB = MBBI; 410193323Sed for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) { 411193323Sed for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) { 412193323Sed unsigned Reg = CSI[inx].getReg(); 413193323Sed // If instruction I reads or modifies Reg, add it to UsedCSRegs, 414193323Sed // CSRUsed map for the current block. 415193323Sed for (unsigned opInx = 0, opEnd = I->getNumOperands(); 416193323Sed opInx != opEnd; ++opInx) { 417193323Sed const MachineOperand &MO = I->getOperand(opInx); 418193323Sed if (! (MO.isReg() && (MO.isUse() || MO.isDef()))) 419193323Sed continue; 420193323Sed unsigned MOReg = MO.getReg(); 421193323Sed if (!MOReg) 422193323Sed continue; 423193323Sed if (MOReg == Reg || 424193323Sed (TargetRegisterInfo::isPhysicalRegister(MOReg) && 425193323Sed TargetRegisterInfo::isPhysicalRegister(Reg) && 426193323Sed TRI->isSubRegister(Reg, MOReg))) { 427193323Sed // CSR Reg is defined/used in block MBB. 428193323Sed CSRUsed[MBB].set(inx); 429193323Sed // Check for uses in EntryBlock. 430193323Sed if (MBB != EntryBlock) 431193323Sed allCSRUsesInEntryBlock = false; 432193323Sed } 433193323Sed } 434193323Sed } 435193323Sed } 436193323Sed 437193323Sed if (CSRUsed[MBB].empty()) 438193323Sed continue; 439193323Sed 440193323Sed // Propagate CSRUsed[MBB] in loops 441193323Sed if (MachineLoop* LP = LI.getLoopFor(MBB)) { 442193323Sed // Add top level loop to work list. 443193323Sed MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP); 444193323Sed MachineLoop* PLP = getTopLevelLoopParent(LP); 445193323Sed 446193323Sed if (! HDR) { 447193323Sed HDR = PLP->getHeader(); 448193323Sed assert(HDR->pred_size() > 0 && "Loop header has no predecessors?"); 449193323Sed MachineBasicBlock::pred_iterator PI = HDR->pred_begin(); 450193323Sed HDR = *PI; 451193323Sed } 452193323Sed TLLoops[HDR] = PLP; 453193323Sed 454193323Sed // Push uses from inside loop to its parent loops, 455193323Sed // or to all other MBBs in its loop. 456193323Sed if (LP->getLoopDepth() > 1) { 457193323Sed for (MachineLoop* PLP = LP->getParentLoop(); PLP; 458193323Sed PLP = PLP->getParentLoop()) { 459193323Sed propagateUsesAroundLoop(MBB, PLP); 460193323Sed } 461193323Sed } else { 462193323Sed propagateUsesAroundLoop(MBB, LP); 463193323Sed } 464193323Sed } 465193323Sed } 466193323Sed 467193323Sed if (allCSRUsesInEntryBlock) { 468243830Sdim DEBUG(dbgs() << "DISABLED: " << Fn.getName() 469198090Srdivacky << ": all CSRs used in EntryBlock\n"); 470193323Sed ShrinkWrapThisFunction = false; 471193323Sed } else { 472193323Sed bool allCSRsUsedInEntryFanout = true; 473193323Sed for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(), 474193323Sed SE = EntryBlock->succ_end(); SI != SE; ++SI) { 475193323Sed MachineBasicBlock* SUCC = *SI; 476193323Sed if (CSRUsed[SUCC] != UsedCSRegs) 477193323Sed allCSRsUsedInEntryFanout = false; 478193323Sed } 479193323Sed if (allCSRsUsedInEntryFanout) { 480243830Sdim DEBUG(dbgs() << "DISABLED: " << Fn.getName() 481198090Srdivacky << ": all CSRs used in imm successors of EntryBlock\n"); 482193323Sed ShrinkWrapThisFunction = false; 483193323Sed } 484193323Sed } 485193323Sed 486193323Sed if (ShrinkWrapThisFunction) { 487193323Sed // Check if MBB uses CSRs and dominates all exit nodes. 488193323Sed // Such nodes are equiv. to the entry node w.r.t. 489193323Sed // CSR uses: every path through the function must 490193323Sed // pass through this node. If each CSR is used at least 491193323Sed // once by these nodes, shrink wrapping is disabled. 492193323Sed CSRegSet CSRUsedInChokePoints; 493193323Sed for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 494193323Sed MBBI != MBBE; ++MBBI) { 495193323Sed MachineBasicBlock* MBB = MBBI; 496193323Sed if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1) 497193323Sed continue; 498193323Sed bool dominatesExitNodes = true; 499193323Sed for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) 500193323Sed if (! DT.dominates(MBB, ReturnBlocks[ri])) { 501193323Sed dominatesExitNodes = false; 502193323Sed break; 503193323Sed } 504193323Sed if (dominatesExitNodes) { 505193323Sed CSRUsedInChokePoints |= CSRUsed[MBB]; 506193323Sed if (CSRUsedInChokePoints == UsedCSRegs) { 507243830Sdim DEBUG(dbgs() << "DISABLED: " << Fn.getName() 508198090Srdivacky << ": all CSRs used in choke point(s) at " 509198090Srdivacky << getBasicBlockName(MBB) << "\n"); 510193323Sed ShrinkWrapThisFunction = false; 511193323Sed break; 512193323Sed } 513193323Sed } 514193323Sed } 515193323Sed } 516193323Sed 517193323Sed // Return now if we have decided not to apply shrink wrapping 518193323Sed // to the current function. 519193323Sed if (! ShrinkWrapThisFunction) 520193323Sed return false; 521193323Sed 522193323Sed DEBUG({ 523243830Sdim dbgs() << "ENABLED: " << Fn.getName(); 524193323Sed if (HasFastExitPath) 525202375Srdivacky dbgs() << " (fast exit path)"; 526202375Srdivacky dbgs() << "\n"; 527193323Sed if (ShrinkWrapDebugging >= BasicInfo) { 528202375Srdivacky dbgs() << "------------------------------" 529193323Sed << "-----------------------------\n"; 530202375Srdivacky dbgs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n"; 531193323Sed if (ShrinkWrapDebugging >= Details) { 532202375Srdivacky dbgs() << "------------------------------" 533193323Sed << "-----------------------------\n"; 534193323Sed dumpAllUsed(); 535193323Sed } 536193323Sed } 537193323Sed }); 538193323Sed 539193323Sed // Build initial DF sets to determine minimal regions in the 540193323Sed // Machine CFG around which CSRs must be spilled and restored. 541193323Sed calculateAnticAvail(Fn); 542193323Sed 543193323Sed return true; 544193323Sed} 545193323Sed 546193323Sed/// addUsesForMEMERegion - add uses of CSRs spilled or restored in 547193323Sed/// multi-entry, multi-exit (MEME) regions so spill and restore 548193323Sed/// placement will not break code that enters or leaves a 549193323Sed/// shrink-wrapped region by inducing spills with no matching 550193323Sed/// restores or restores with no matching spills. A MEME region 551193323Sed/// is a subgraph of the MCFG with multiple entry edges, multiple 552193323Sed/// exit edges, or both. This code propagates use information 553193323Sed/// through the MCFG until all paths requiring spills and restores 554193323Sed/// _outside_ the computed minimal placement regions have been covered. 555193323Sed/// 556193323Sedbool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB, 557193323Sed SmallVector<MachineBasicBlock*, 4>& blks) { 558193323Sed if (MBB->succ_size() < 2 && MBB->pred_size() < 2) { 559193323Sed bool processThisBlock = false; 560193323Sed for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 561193323Sed SE = MBB->succ_end(); SI != SE; ++SI) { 562193323Sed MachineBasicBlock* SUCC = *SI; 563193323Sed if (SUCC->pred_size() > 1) { 564193323Sed processThisBlock = true; 565193323Sed break; 566193323Sed } 567193323Sed } 568193323Sed if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) { 569193323Sed for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 570193323Sed PE = MBB->pred_end(); PI != PE; ++PI) { 571193323Sed MachineBasicBlock* PRED = *PI; 572193323Sed if (PRED->succ_size() > 1) { 573193323Sed processThisBlock = true; 574193323Sed break; 575193323Sed } 576193323Sed } 577193323Sed } 578193323Sed if (! processThisBlock) 579193323Sed return false; 580193323Sed } 581193323Sed 582193323Sed CSRegSet prop; 583193323Sed if (!CSRSave[MBB].empty()) 584193323Sed prop = CSRSave[MBB]; 585193323Sed else if (!CSRRestore[MBB].empty()) 586193323Sed prop = CSRRestore[MBB]; 587193323Sed else 588193323Sed prop = CSRUsed[MBB]; 589193323Sed if (prop.empty()) 590193323Sed return false; 591193323Sed 592193323Sed // Propagate selected bits to successors, predecessors of MBB. 593193323Sed bool addedUses = false; 594193323Sed for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 595193323Sed SE = MBB->succ_end(); SI != SE; ++SI) { 596193323Sed MachineBasicBlock* SUCC = *SI; 597193323Sed // Self-loop 598193323Sed if (SUCC == MBB) 599193323Sed continue; 600193323Sed if (! CSRUsed[SUCC].contains(prop)) { 601193323Sed CSRUsed[SUCC] |= prop; 602193323Sed addedUses = true; 603193323Sed blks.push_back(SUCC); 604193323Sed DEBUG(if (ShrinkWrapDebugging >= Iterations) 605202375Srdivacky dbgs() << getBasicBlockName(MBB) 606193323Sed << "(" << stringifyCSRegSet(prop) << ")->" 607193323Sed << "successor " << getBasicBlockName(SUCC) << "\n"); 608193323Sed } 609193323Sed } 610193323Sed for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 611193323Sed PE = MBB->pred_end(); PI != PE; ++PI) { 612193323Sed MachineBasicBlock* PRED = *PI; 613193323Sed // Self-loop 614193323Sed if (PRED == MBB) 615193323Sed continue; 616193323Sed if (! CSRUsed[PRED].contains(prop)) { 617193323Sed CSRUsed[PRED] |= prop; 618193323Sed addedUses = true; 619193323Sed blks.push_back(PRED); 620193323Sed DEBUG(if (ShrinkWrapDebugging >= Iterations) 621202375Srdivacky dbgs() << getBasicBlockName(MBB) 622193323Sed << "(" << stringifyCSRegSet(prop) << ")->" 623193323Sed << "predecessor " << getBasicBlockName(PRED) << "\n"); 624193323Sed } 625193323Sed } 626193323Sed return addedUses; 627193323Sed} 628193323Sed 629193323Sed/// addUsesForTopLevelLoops - add uses for CSRs used inside top 630193323Sed/// level loops to the exit blocks of those loops. 631193323Sed/// 632193323Sedbool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) { 633193323Sed bool addedUses = false; 634193323Sed 635193323Sed // Place restores for top level loops where needed. 636193323Sed for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator 637193323Sed I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) { 638193323Sed MachineBasicBlock* MBB = I->first; 639193323Sed MachineLoop* LP = I->second; 640193323Sed MachineBasicBlock* HDR = LP->getHeader(); 641193323Sed SmallVector<MachineBasicBlock*, 4> exitBlocks; 642193323Sed CSRegSet loopSpills; 643193323Sed 644193323Sed loopSpills = CSRSave[MBB]; 645193323Sed if (CSRSave[MBB].empty()) { 646193323Sed loopSpills = CSRUsed[HDR]; 647193323Sed assert(!loopSpills.empty() && "No CSRs used in loop?"); 648193323Sed } else if (CSRRestore[MBB].contains(CSRSave[MBB])) 649193323Sed continue; 650193323Sed 651193323Sed LP->getExitBlocks(exitBlocks); 652193323Sed assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?"); 653193323Sed for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) { 654193323Sed MachineBasicBlock* EXB = exitBlocks[i]; 655193323Sed if (! CSRUsed[EXB].contains(loopSpills)) { 656193323Sed CSRUsed[EXB] |= loopSpills; 657193323Sed addedUses = true; 658193323Sed DEBUG(if (ShrinkWrapDebugging >= Iterations) 659202375Srdivacky dbgs() << "LOOP " << getBasicBlockName(MBB) 660193323Sed << "(" << stringifyCSRegSet(loopSpills) << ")->" 661193323Sed << getBasicBlockName(EXB) << "\n"); 662193323Sed if (EXB->succ_size() > 1 || EXB->pred_size() > 1) 663193323Sed blks.push_back(EXB); 664193323Sed } 665193323Sed } 666193323Sed } 667193323Sed return addedUses; 668193323Sed} 669193323Sed 670193323Sed/// calcSpillPlacements - determine which CSRs should be spilled 671193323Sed/// in MBB using AnticIn sets of MBB's predecessors, keeping track 672193323Sed/// of changes to spilled reg sets. Add MBB to the set of blocks 673193323Sed/// that need to be processed for propagating use info to cover 674193323Sed/// multi-entry/exit regions. 675193323Sed/// 676193323Sedbool PEI::calcSpillPlacements(MachineBasicBlock* MBB, 677193323Sed SmallVector<MachineBasicBlock*, 4> &blks, 678193323Sed CSRegBlockMap &prevSpills) { 679193323Sed bool placedSpills = false; 680193323Sed // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB) 681193323Sed CSRegSet anticInPreds; 682193323Sed SmallVector<MachineBasicBlock*, 4> predecessors; 683193323Sed for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 684193323Sed PE = MBB->pred_end(); PI != PE; ++PI) { 685193323Sed MachineBasicBlock* PRED = *PI; 686193323Sed if (PRED != MBB) 687193323Sed predecessors.push_back(PRED); 688193323Sed } 689193323Sed unsigned i = 0, e = predecessors.size(); 690193323Sed if (i != e) { 691193323Sed MachineBasicBlock* PRED = predecessors[i]; 692193323Sed anticInPreds = UsedCSRegs - AnticIn[PRED]; 693193323Sed for (++i; i != e; ++i) { 694193323Sed PRED = predecessors[i]; 695193323Sed anticInPreds &= (UsedCSRegs - AnticIn[PRED]); 696193323Sed } 697193323Sed } else { 698193323Sed // Handle uses in entry blocks (which have no predecessors). 699193323Sed // This is necessary because the DFA formulation assumes the 700193323Sed // entry and (multiple) exit nodes cannot have CSR uses, which 701193323Sed // is not the case in the real world. 702193323Sed anticInPreds = UsedCSRegs; 703193323Sed } 704193323Sed // Compute spills required at MBB: 705193323Sed CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds; 706193323Sed 707193323Sed if (! CSRSave[MBB].empty()) { 708193323Sed if (MBB == EntryBlock) { 709193323Sed for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) 710193323Sed CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB]; 711193323Sed } else { 712193323Sed // Reset all regs spilled in MBB that are also spilled in EntryBlock. 713193323Sed if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) { 714193323Sed CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock]; 715193323Sed } 716193323Sed } 717193323Sed } 718193323Sed placedSpills = (CSRSave[MBB] != prevSpills[MBB]); 719193323Sed prevSpills[MBB] = CSRSave[MBB]; 720193323Sed // Remember this block for adding restores to successor 721193323Sed // blocks for multi-entry region. 722193323Sed if (placedSpills) 723193323Sed blks.push_back(MBB); 724193323Sed 725193323Sed DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations) 726202375Srdivacky dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 727193323Sed << stringifyCSRegSet(CSRSave[MBB]) << "\n"); 728193323Sed 729193323Sed return placedSpills; 730193323Sed} 731193323Sed 732193323Sed/// calcRestorePlacements - determine which CSRs should be restored 733193323Sed/// in MBB using AvailOut sets of MBB's succcessors, keeping track 734193323Sed/// of changes to restored reg sets. Add MBB to the set of blocks 735193323Sed/// that need to be processed for propagating use info to cover 736193323Sed/// multi-entry/exit regions. 737193323Sed/// 738193323Sedbool PEI::calcRestorePlacements(MachineBasicBlock* MBB, 739193323Sed SmallVector<MachineBasicBlock*, 4> &blks, 740193323Sed CSRegBlockMap &prevRestores) { 741193323Sed bool placedRestores = false; 742193323Sed // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB) 743193323Sed CSRegSet availOutSucc; 744193323Sed SmallVector<MachineBasicBlock*, 4> successors; 745193323Sed for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 746193323Sed SE = MBB->succ_end(); SI != SE; ++SI) { 747193323Sed MachineBasicBlock* SUCC = *SI; 748193323Sed if (SUCC != MBB) 749193323Sed successors.push_back(SUCC); 750193323Sed } 751193323Sed unsigned i = 0, e = successors.size(); 752193323Sed if (i != e) { 753193323Sed MachineBasicBlock* SUCC = successors[i]; 754193323Sed availOutSucc = UsedCSRegs - AvailOut[SUCC]; 755193323Sed for (++i; i != e; ++i) { 756193323Sed SUCC = successors[i]; 757193323Sed availOutSucc &= (UsedCSRegs - AvailOut[SUCC]); 758193323Sed } 759193323Sed } else { 760193323Sed if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) { 761193323Sed // Handle uses in return blocks (which have no successors). 762193323Sed // This is necessary because the DFA formulation assumes the 763193323Sed // entry and (multiple) exit nodes cannot have CSR uses, which 764193323Sed // is not the case in the real world. 765193323Sed availOutSucc = UsedCSRegs; 766193323Sed } 767193323Sed } 768193323Sed // Compute restores required at MBB: 769193323Sed CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc; 770193323Sed 771193323Sed // Postprocess restore placements at MBB. 772193323Sed // Remove the CSRs that are restored in the return blocks. 773193323Sed // Lest this be confusing, note that: 774193323Sed // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks. 775193323Sed if (MBB->succ_size() && ! CSRRestore[MBB].empty()) { 776193323Sed if (! CSRSave[EntryBlock].empty()) 777193323Sed CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock]; 778193323Sed } 779193323Sed placedRestores = (CSRRestore[MBB] != prevRestores[MBB]); 780193323Sed prevRestores[MBB] = CSRRestore[MBB]; 781193323Sed // Remember this block for adding saves to predecessor 782193323Sed // blocks for multi-entry region. 783193323Sed if (placedRestores) 784193323Sed blks.push_back(MBB); 785193323Sed 786193323Sed DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations) 787202375Srdivacky dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = " 788193323Sed << stringifyCSRegSet(CSRRestore[MBB]) << "\n"); 789193323Sed 790193323Sed return placedRestores; 791193323Sed} 792193323Sed 793193323Sed/// placeSpillsAndRestores - place spills and restores of CSRs 794193323Sed/// used in MBBs in minimal regions that contain the uses. 795193323Sed/// 796193323Sedvoid PEI::placeSpillsAndRestores(MachineFunction &Fn) { 797193323Sed CSRegBlockMap prevCSRSave; 798193323Sed CSRegBlockMap prevCSRRestore; 799193323Sed SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks; 800193323Sed bool changed = true; 801193323Sed unsigned iterations = 0; 802193323Sed 803193323Sed // Iterate computation of spill and restore placements in the MCFG until: 804193323Sed // 1. CSR use info has been fully propagated around the MCFG, and 805193323Sed // 2. computation of CSRSave[], CSRRestore[] reach fixed points. 806193323Sed while (changed) { 807193323Sed changed = false; 808193323Sed ++iterations; 809193323Sed 810193323Sed DEBUG(if (ShrinkWrapDebugging >= Iterations) 811202375Srdivacky dbgs() << "iter " << iterations 812193323Sed << " --------------------------------------------------\n"); 813193323Sed 814193323Sed // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG, 815193323Sed // which determines the placements of spills and restores. 816193323Sed // Keep track of changes to spills, restores in each iteration to 817193323Sed // minimize the total iterations. 818193323Sed bool SRChanged = false; 819193323Sed for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 820193323Sed MBBI != MBBE; ++MBBI) { 821193323Sed MachineBasicBlock* MBB = MBBI; 822193323Sed 823193323Sed // Place spills for CSRs in MBB. 824193323Sed SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave); 825193323Sed 826193323Sed // Place restores for CSRs in MBB. 827193323Sed SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore); 828193323Sed } 829193323Sed 830193323Sed // Add uses of CSRs used inside loops where needed. 831193323Sed changed |= addUsesForTopLevelLoops(cvBlocks); 832193323Sed 833193323Sed // Add uses for CSRs spilled or restored at branch, join points. 834193323Sed if (changed || SRChanged) { 835193323Sed while (! cvBlocks.empty()) { 836193323Sed MachineBasicBlock* MBB = cvBlocks.pop_back_val(); 837193323Sed changed |= addUsesForMEMERegion(MBB, ncvBlocks); 838193323Sed } 839193323Sed if (! ncvBlocks.empty()) { 840193323Sed cvBlocks = ncvBlocks; 841193323Sed ncvBlocks.clear(); 842193323Sed } 843193323Sed } 844193323Sed 845193323Sed if (changed) { 846193323Sed calculateAnticAvail(Fn); 847193323Sed CSRSave.clear(); 848193323Sed CSRRestore.clear(); 849193323Sed } 850193323Sed } 851193323Sed 852193323Sed // Check for effectiveness: 853193323Sed // SR0 = {r | r in CSRSave[EntryBlock], CSRRestore[RB], RB in ReturnBlocks} 854193323Sed // numSRReduced = |(UsedCSRegs - SR0)|, approx. SR0 by CSRSave[EntryBlock] 855193323Sed // Gives a measure of how many CSR spills have been moved from EntryBlock 856193323Sed // to minimal regions enclosing their uses. 857193323Sed CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]); 858193323Sed unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count(); 859193323Sed numSRReduced += numSRReducedThisFunc; 860193323Sed DEBUG(if (ShrinkWrapDebugging >= BasicInfo) { 861202375Srdivacky dbgs() << "-----------------------------------------------------------\n"; 862202375Srdivacky dbgs() << "total iterations = " << iterations << " ( " 863243830Sdim << Fn.getName() 864193323Sed << " " << numSRReducedThisFunc 865193323Sed << " " << Fn.size() 866193323Sed << " )\n"; 867202375Srdivacky dbgs() << "-----------------------------------------------------------\n"; 868193323Sed dumpSRSets(); 869202375Srdivacky dbgs() << "-----------------------------------------------------------\n"; 870193323Sed if (numSRReducedThisFunc) 871193323Sed verifySpillRestorePlacement(); 872193323Sed }); 873193323Sed} 874193323Sed 875193323Sed// Debugging methods. 876193323Sed#ifndef NDEBUG 877193323Sed/// findFastExitPath - debugging method used to detect functions 878193323Sed/// with at least one path from the entry block to a return block 879193323Sed/// directly or which has a very small number of edges. 880193323Sed/// 881193323Sedvoid PEI::findFastExitPath() { 882193323Sed if (! EntryBlock) 883193323Sed return; 884193323Sed // Fina a path from EntryBlock to any return block that does not branch: 885193323Sed // Entry 886193323Sed // | ... 887193323Sed // v | 888193323Sed // B1<-----+ 889193323Sed // | 890193323Sed // v 891193323Sed // Return 892193323Sed for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(), 893193323Sed SE = EntryBlock->succ_end(); SI != SE; ++SI) { 894193323Sed MachineBasicBlock* SUCC = *SI; 895193323Sed 896193323Sed // Assume positive, disprove existence of fast path. 897193323Sed HasFastExitPath = true; 898193323Sed 899193323Sed // Check the immediate successors. 900193323Sed if (isReturnBlock(SUCC)) { 901193323Sed if (ShrinkWrapDebugging >= BasicInfo) 902202375Srdivacky dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock) 903193323Sed << "->" << getBasicBlockName(SUCC) << "\n"; 904193323Sed break; 905193323Sed } 906193323Sed // Traverse df from SUCC, look for a branch block. 907193323Sed std::string exitPath = getBasicBlockName(SUCC); 908193323Sed for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC), 909193323Sed BE = df_end(SUCC); BI != BE; ++BI) { 910193323Sed MachineBasicBlock* SBB = *BI; 911193323Sed // Reject paths with branch nodes. 912193323Sed if (SBB->succ_size() > 1) { 913193323Sed HasFastExitPath = false; 914193323Sed break; 915193323Sed } 916193323Sed exitPath += "->" + getBasicBlockName(SBB); 917193323Sed } 918193323Sed if (HasFastExitPath) { 919193323Sed if (ShrinkWrapDebugging >= BasicInfo) 920202375Srdivacky dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock) 921193323Sed << "->" << exitPath << "\n"; 922193323Sed break; 923193323Sed } 924193323Sed } 925193323Sed} 926193323Sed 927193323Sed/// verifySpillRestorePlacement - check the current spill/restore 928193323Sed/// sets for safety. Attempt to find spills without restores or 929193323Sed/// restores without spills. 930193323Sed/// Spills: walk df from each MBB in spill set ensuring that 931193323Sed/// all CSRs spilled at MMBB are restored on all paths 932193323Sed/// from MBB to all exit blocks. 933193323Sed/// Restores: walk idf from each MBB in restore set ensuring that 934193323Sed/// all CSRs restored at MBB are spilled on all paths 935193323Sed/// reaching MBB. 936193323Sed/// 937193323Sedvoid PEI::verifySpillRestorePlacement() { 938193323Sed unsigned numReturnBlocks = 0; 939193323Sed for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 940193323Sed MBBI != MBBE; ++MBBI) { 941193323Sed MachineBasicBlock* MBB = MBBI; 942193323Sed if (isReturnBlock(MBB) || MBB->succ_size() == 0) 943193323Sed ++numReturnBlocks; 944193323Sed } 945193323Sed for (CSRegBlockMap::iterator BI = CSRSave.begin(), 946193323Sed BE = CSRSave.end(); BI != BE; ++BI) { 947193323Sed MachineBasicBlock* MBB = BI->first; 948193323Sed CSRegSet spilled = BI->second; 949193323Sed CSRegSet restored; 950193323Sed 951193323Sed if (spilled.empty()) 952193323Sed continue; 953193323Sed 954202375Srdivacky DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 955198090Srdivacky << stringifyCSRegSet(spilled) 956198090Srdivacky << " RESTORE[" << getBasicBlockName(MBB) << "] = " 957198090Srdivacky << stringifyCSRegSet(CSRRestore[MBB]) << "\n"); 958193323Sed 959193323Sed if (CSRRestore[MBB].intersects(spilled)) { 960193323Sed restored |= (CSRRestore[MBB] & spilled); 961193323Sed } 962193323Sed 963193323Sed // Walk depth first from MBB to find restores of all CSRs spilled at MBB: 964193323Sed // we must find restores for all spills w/no intervening spills on all 965193323Sed // paths from MBB to all return blocks. 966193323Sed for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB), 967193323Sed BE = df_end(MBB); BI != BE; ++BI) { 968193323Sed MachineBasicBlock* SBB = *BI; 969193323Sed if (SBB == MBB) 970193323Sed continue; 971193323Sed // Stop when we encounter spills of any CSRs spilled at MBB that 972193323Sed // have not yet been seen to be restored. 973193323Sed if (CSRSave[SBB].intersects(spilled) && 974193323Sed !restored.contains(CSRSave[SBB] & spilled)) 975193323Sed break; 976193323Sed // Collect the CSRs spilled at MBB that are restored 977193323Sed // at this DF successor of MBB. 978193323Sed if (CSRRestore[SBB].intersects(spilled)) 979193323Sed restored |= (CSRRestore[SBB] & spilled); 980193323Sed // If we are at a retun block, check that the restores 981193323Sed // we have seen so far exhaust the spills at MBB, then 982193323Sed // reset the restores. 983193323Sed if (isReturnBlock(SBB) || SBB->succ_size() == 0) { 984193323Sed if (restored != spilled) { 985193323Sed CSRegSet notRestored = (spilled - restored); 986243830Sdim DEBUG(dbgs() << MF->getName() << ": " 987198090Srdivacky << stringifyCSRegSet(notRestored) 988198090Srdivacky << " spilled at " << getBasicBlockName(MBB) 989198090Srdivacky << " are never restored on path to return " 990198090Srdivacky << getBasicBlockName(SBB) << "\n"); 991193323Sed } 992193323Sed restored.clear(); 993193323Sed } 994193323Sed } 995193323Sed } 996193323Sed 997193323Sed // Check restore placements. 998193323Sed for (CSRegBlockMap::iterator BI = CSRRestore.begin(), 999193323Sed BE = CSRRestore.end(); BI != BE; ++BI) { 1000193323Sed MachineBasicBlock* MBB = BI->first; 1001193323Sed CSRegSet restored = BI->second; 1002193323Sed CSRegSet spilled; 1003193323Sed 1004193323Sed if (restored.empty()) 1005193323Sed continue; 1006193323Sed 1007202375Srdivacky DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 1008198090Srdivacky << stringifyCSRegSet(CSRSave[MBB]) 1009198090Srdivacky << " RESTORE[" << getBasicBlockName(MBB) << "] = " 1010198090Srdivacky << stringifyCSRegSet(restored) << "\n"); 1011193323Sed 1012193323Sed if (CSRSave[MBB].intersects(restored)) { 1013193323Sed spilled |= (CSRSave[MBB] & restored); 1014193323Sed } 1015193323Sed // Walk inverse depth first from MBB to find spills of all 1016193323Sed // CSRs restored at MBB: 1017193323Sed for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB), 1018193323Sed BE = idf_end(MBB); BI != BE; ++BI) { 1019193323Sed MachineBasicBlock* PBB = *BI; 1020193323Sed if (PBB == MBB) 1021193323Sed continue; 1022193323Sed // Stop when we encounter restores of any CSRs restored at MBB that 1023193323Sed // have not yet been seen to be spilled. 1024193323Sed if (CSRRestore[PBB].intersects(restored) && 1025193323Sed !spilled.contains(CSRRestore[PBB] & restored)) 1026193323Sed break; 1027193323Sed // Collect the CSRs restored at MBB that are spilled 1028193323Sed // at this DF predecessor of MBB. 1029193323Sed if (CSRSave[PBB].intersects(restored)) 1030193323Sed spilled |= (CSRSave[PBB] & restored); 1031193323Sed } 1032193323Sed if (spilled != restored) { 1033193323Sed CSRegSet notSpilled = (restored - spilled); 1034243830Sdim DEBUG(dbgs() << MF->getName() << ": " 1035198090Srdivacky << stringifyCSRegSet(notSpilled) 1036198090Srdivacky << " restored at " << getBasicBlockName(MBB) 1037198090Srdivacky << " are never spilled\n"); 1038193323Sed } 1039193323Sed } 1040193323Sed} 1041193323Sed 1042193323Sed// Debugging print methods. 1043193323Sedstd::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) { 1044198090Srdivacky if (!MBB) 1045198090Srdivacky return ""; 1046198090Srdivacky 1047198090Srdivacky if (MBB->getBasicBlock()) 1048234353Sdim return MBB->getBasicBlock()->getName().str(); 1049198090Srdivacky 1050193323Sed std::ostringstream name; 1051198090Srdivacky name << "_MBB_" << MBB->getNumber(); 1052193323Sed return name.str(); 1053193323Sed} 1054193323Sed 1055193323Sedstd::string PEI::stringifyCSRegSet(const CSRegSet& s) { 1056193323Sed const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); 1057193323Sed const std::vector<CalleeSavedInfo> CSI = 1058193323Sed MF->getFrameInfo()->getCalleeSavedInfo(); 1059193323Sed 1060193323Sed std::ostringstream srep; 1061193323Sed if (CSI.size() == 0) { 1062193323Sed srep << "[]"; 1063193323Sed return srep.str(); 1064193323Sed } 1065193323Sed srep << "["; 1066193323Sed CSRegSet::iterator I = s.begin(), E = s.end(); 1067193323Sed if (I != E) { 1068193323Sed unsigned reg = CSI[*I].getReg(); 1069193323Sed srep << TRI->getName(reg); 1070193323Sed for (++I; I != E; ++I) { 1071193323Sed reg = CSI[*I].getReg(); 1072193323Sed srep << ","; 1073193323Sed srep << TRI->getName(reg); 1074193323Sed } 1075193323Sed } 1076193323Sed srep << "]"; 1077193323Sed return srep.str(); 1078193323Sed} 1079193323Sed 1080193323Sedvoid PEI::dumpSet(const CSRegSet& s) { 1081202375Srdivacky DEBUG(dbgs() << stringifyCSRegSet(s) << "\n"); 1082193323Sed} 1083193323Sed 1084193323Sedvoid PEI::dumpUsed(MachineBasicBlock* MBB) { 1085198090Srdivacky DEBUG({ 1086198090Srdivacky if (MBB) 1087202375Srdivacky dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = " 1088198090Srdivacky << stringifyCSRegSet(CSRUsed[MBB]) << "\n"; 1089198090Srdivacky }); 1090193323Sed} 1091193323Sed 1092193323Sedvoid PEI::dumpAllUsed() { 1093193323Sed for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1094193323Sed MBBI != MBBE; ++MBBI) { 1095193323Sed MachineBasicBlock* MBB = MBBI; 1096193323Sed dumpUsed(MBB); 1097193323Sed } 1098193323Sed} 1099193323Sed 1100193323Sedvoid PEI::dumpSets(MachineBasicBlock* MBB) { 1101198090Srdivacky DEBUG({ 1102198090Srdivacky if (MBB) 1103202375Srdivacky dbgs() << getBasicBlockName(MBB) << " | " 1104198090Srdivacky << stringifyCSRegSet(CSRUsed[MBB]) << " | " 1105198090Srdivacky << stringifyCSRegSet(AnticIn[MBB]) << " | " 1106198090Srdivacky << stringifyCSRegSet(AnticOut[MBB]) << " | " 1107198090Srdivacky << stringifyCSRegSet(AvailIn[MBB]) << " | " 1108198090Srdivacky << stringifyCSRegSet(AvailOut[MBB]) << "\n"; 1109198090Srdivacky }); 1110193323Sed} 1111193323Sed 1112193323Sedvoid PEI::dumpSets1(MachineBasicBlock* MBB) { 1113198090Srdivacky DEBUG({ 1114198090Srdivacky if (MBB) 1115202375Srdivacky dbgs() << getBasicBlockName(MBB) << " | " 1116198090Srdivacky << stringifyCSRegSet(CSRUsed[MBB]) << " | " 1117198090Srdivacky << stringifyCSRegSet(AnticIn[MBB]) << " | " 1118198090Srdivacky << stringifyCSRegSet(AnticOut[MBB]) << " | " 1119198090Srdivacky << stringifyCSRegSet(AvailIn[MBB]) << " | " 1120198090Srdivacky << stringifyCSRegSet(AvailOut[MBB]) << " | " 1121198090Srdivacky << stringifyCSRegSet(CSRSave[MBB]) << " | " 1122198090Srdivacky << stringifyCSRegSet(CSRRestore[MBB]) << "\n"; 1123198090Srdivacky }); 1124193323Sed} 1125193323Sed 1126193323Sedvoid PEI::dumpAllSets() { 1127193323Sed for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1128193323Sed MBBI != MBBE; ++MBBI) { 1129193323Sed MachineBasicBlock* MBB = MBBI; 1130193323Sed dumpSets1(MBB); 1131193323Sed } 1132193323Sed} 1133193323Sed 1134193323Sedvoid PEI::dumpSRSets() { 1135198090Srdivacky DEBUG({ 1136198090Srdivacky for (MachineFunction::iterator MBB = MF->begin(), E = MF->end(); 1137198090Srdivacky MBB != E; ++MBB) { 1138198090Srdivacky if (!CSRSave[MBB].empty()) { 1139202375Srdivacky dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 1140198090Srdivacky << stringifyCSRegSet(CSRSave[MBB]); 1141198090Srdivacky if (CSRRestore[MBB].empty()) 1142202375Srdivacky dbgs() << '\n'; 1143198090Srdivacky } 1144198090Srdivacky 1145198090Srdivacky if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty()) 1146202375Srdivacky dbgs() << " " 1147198090Srdivacky << "RESTORE[" << getBasicBlockName(MBB) << "] = " 1148198090Srdivacky << stringifyCSRegSet(CSRRestore[MBB]) << "\n"; 1149198090Srdivacky } 1150198090Srdivacky }); 1151193323Sed} 1152193323Sed#endif 1153