1 //===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a shrink wrapping variant of prolog/epilog insertion:
11 // - Spills and restores of callee-saved registers (CSRs) are placed in the
12 // machine CFG to tightly surround their uses so that execution paths that
13 // do not use CSRs do not pay the spill/restore penalty.
15 // - Avoiding placment of spills/restores in loops: if a CSR is used inside a
16 // loop the spills are placed in the loop preheader, and restores are
17 // placed in the loop exit nodes (the successors of loop _exiting_ nodes).
19 // - Covering paths without CSR uses:
20 // If a region in a CFG uses CSRs and has multiple entry and/or exit points,
21 // the use info for the CSRs inside the region is propagated outward in the
22 // CFG to ensure validity of the spill/restore placements. This decreases
23 // the effectiveness of shrink wrapping but does not require edge splitting
24 // in the machine CFG.
26 // This shrink wrapping implementation uses an iterative analysis to determine
27 // which basic blocks require spills and restores for CSRs.
29 // This pass uses MachineDominators and MachineLoopInfo. Loop information
30 // is used to prevent placement of callee-saved register spills/restores
31 // in the bodies of loops.
33 //===----------------------------------------------------------------------===//
35 #define DEBUG_TYPE "shrink-wrap"
37 #include "PrologEpilogInserter.h"
38 #include "llvm/ADT/DenseMap.h"
39 #include "llvm/ADT/PostOrderIterator.h"
40 #include "llvm/ADT/STLExtras.h"
41 #include "llvm/ADT/SparseBitVector.h"
42 #include "llvm/ADT/Statistic.h"
43 #include "llvm/CodeGen/MachineDominators.h"
44 #include "llvm/CodeGen/MachineFrameInfo.h"
45 #include "llvm/CodeGen/MachineInstr.h"
46 #include "llvm/CodeGen/MachineLoopInfo.h"
47 #include "llvm/CodeGen/MachineRegisterInfo.h"
48 #include "llvm/Support/CommandLine.h"
49 #include "llvm/Support/Compiler.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Target/TargetMachine.h"
52 #include "llvm/Target/TargetRegisterInfo.h"
57 STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");
61 ShrinkWrapping("shrink-wrap",
62 cl::desc("Shrink wrap callee-saved register spills/restores"));
64 // Shrink wrap only the specified function, a debugging aid.
65 static cl::opt<std::string>
66 ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
67 cl::desc("Shrink wrap the specified function"),
68 cl::value_desc("funcname"),
71 // Debugging level for shrink wrapping.
72 enum ShrinkWrapDebugLevel {
73 None, BasicInfo, Iterations, Details
76 static cl::opt<enum ShrinkWrapDebugLevel>
77 ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
78 cl::desc("Print shrink wrapping debugging information"),
80 clEnumVal(None , "disable debug output"),
81 clEnumVal(BasicInfo , "print basic DF sets"),
82 clEnumVal(Iterations, "print SR sets for each iteration"),
83 clEnumVal(Details , "print all DF sets"),
87 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
89 if (ShrinkWrapping || ShrinkWrapFunc != "") {
90 AU.addRequired<MachineLoopInfo>();
91 AU.addRequired<MachineDominatorTree>();
93 AU.addPreserved<MachineLoopInfo>();
94 AU.addPreserved<MachineDominatorTree>();
95 AU.addRequired<TargetPassConfig>();
96 MachineFunctionPass::getAnalysisUsage(AU);
99 //===----------------------------------------------------------------------===//
100 // ShrinkWrapping implementation
101 //===----------------------------------------------------------------------===//
103 // Convienences for dealing with machine loops.
104 MachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) {
105 assert(LP && "Machine loop is NULL.");
106 MachineBasicBlock* PHDR = LP->getLoopPreheader();
107 MachineLoop* PLP = LP->getParentLoop();
109 PHDR = PLP->getLoopPreheader();
110 PLP = PLP->getParentLoop();
115 MachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) {
118 MachineLoop* PLP = LP->getParentLoop();
121 PLP = PLP->getParentLoop();
126 bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
127 return (MBB && !MBB->empty() && MBB->back().isReturn());
130 // Initialize shrink wrapping DFA sets, called before iterations.
131 void PEI::clearAnticAvailSets() {
138 // Clear all sets constructed by shrink wrapping.
139 void PEI::clearAllSets() {
140 ReturnBlocks.clear();
141 clearAnticAvailSets();
149 // Initialize all shrink wrapping data.
150 void PEI::initShrinkWrappingInfo() {
154 HasFastExitPath = false;
156 ShrinkWrapThisFunction = ShrinkWrapping;
157 // DEBUG: enable or disable shrink wrapping for the current function
158 // via --shrink-wrap-func=<funcname>.
160 if (ShrinkWrapFunc != "") {
161 std::string MFName = MF->getName().str();
162 ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
168 /// placeCSRSpillsAndRestores - determine which MBBs of the function
169 /// need save, restore code for callee-saved registers by doing a DF analysis
170 /// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
171 /// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
172 /// is used to ensure that CSR save/restore code is not placed inside loops.
173 /// This function computes the maps of MBBs -> CSRs to spill and restore
174 /// in CSRSave, CSRRestore.
176 /// If shrink wrapping is not being performed, place all spills in
177 /// the entry block, all restores in return blocks. In this case,
178 /// CSRSave has a single mapping, CSRRestore has mappings for each
181 void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
185 initShrinkWrappingInfo();
187 DEBUG(if (ShrinkWrapThisFunction) {
188 dbgs() << "Place CSR spills/restores for "
189 << MF->getName() << "\n";
192 if (calculateSets(Fn))
193 placeSpillsAndRestores(Fn);
196 /// calcAnticInOut - calculate the anticipated in/out reg sets
197 /// for the given MBB by looking forward in the MCFG at MBB's
200 bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
201 bool changed = false;
203 // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB))
204 SmallVector<MachineBasicBlock*, 4> successors;
205 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
206 SE = MBB->succ_end(); SI != SE; ++SI) {
207 MachineBasicBlock* SUCC = *SI;
209 successors.push_back(SUCC);
212 unsigned i = 0, e = successors.size();
214 CSRegSet prevAnticOut = AnticOut[MBB];
215 MachineBasicBlock* SUCC = successors[i];
217 AnticOut[MBB] = AnticIn[SUCC];
218 for (++i; i != e; ++i) {
219 SUCC = successors[i];
220 AnticOut[MBB] &= AnticIn[SUCC];
222 if (prevAnticOut != AnticOut[MBB])
226 // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]);
227 CSRegSet prevAnticIn = AnticIn[MBB];
228 AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
229 if (prevAnticIn != AnticIn[MBB])
234 /// calcAvailInOut - calculate the available in/out reg sets
235 /// for the given MBB by looking backward in the MCFG at MBB's
238 bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
239 bool changed = false;
241 // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB))
242 SmallVector<MachineBasicBlock*, 4> predecessors;
243 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
244 PE = MBB->pred_end(); PI != PE; ++PI) {
245 MachineBasicBlock* PRED = *PI;
247 predecessors.push_back(PRED);
250 unsigned i = 0, e = predecessors.size();
252 CSRegSet prevAvailIn = AvailIn[MBB];
253 MachineBasicBlock* PRED = predecessors[i];
255 AvailIn[MBB] = AvailOut[PRED];
256 for (++i; i != e; ++i) {
257 PRED = predecessors[i];
258 AvailIn[MBB] &= AvailOut[PRED];
260 if (prevAvailIn != AvailIn[MBB])
264 // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]);
265 CSRegSet prevAvailOut = AvailOut[MBB];
266 AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
267 if (prevAvailOut != AvailOut[MBB])
272 /// calculateAnticAvail - build the sets anticipated and available
273 /// registers in the MCFG of the current function iteratively,
274 /// doing a combined forward and backward analysis.
276 void PEI::calculateAnticAvail(MachineFunction &Fn) {
277 // Initialize data flow sets.
278 clearAnticAvailSets();
280 // Calculate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG.
282 unsigned iterations = 0;
286 for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
287 MBBI != MBBE; ++MBBI) {
288 MachineBasicBlock* MBB = MBBI;
290 // Calculate anticipated in, out regs at MBB from
291 // anticipated at successors of MBB.
292 changed |= calcAnticInOut(MBB);
294 // Calculate available in, out regs at MBB from
295 // available at predecessors of MBB.
296 changed |= calcAvailInOut(MBB);
301 if (ShrinkWrapDebugging >= Details) {
303 << "-----------------------------------------------------------\n"
304 << " Antic/Avail Sets:\n"
305 << "-----------------------------------------------------------\n"
306 << "iterations = " << iterations << "\n"
307 << "-----------------------------------------------------------\n"
308 << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n"
309 << "-----------------------------------------------------------\n";
311 for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
312 MBBI != MBBE; ++MBBI) {
313 MachineBasicBlock* MBB = MBBI;
318 << "-----------------------------------------------------------\n";
323 /// propagateUsesAroundLoop - copy used register info from MBB to all blocks
324 /// of the loop given by LP and its parent loops. This prevents spills/restores
325 /// from being placed in the bodies of loops.
327 void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
331 std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks();
332 for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) {
333 MachineBasicBlock* LBB = loopBlocks[i];
336 if (CSRUsed[LBB].contains(CSRUsed[MBB]))
338 CSRUsed[LBB] |= CSRUsed[MBB];
342 /// calculateSets - collect the CSRs used in this function, compute
343 /// the DF sets that describe the initial minimal regions in the
344 /// Machine CFG around which CSR spills and restores must be placed.
346 /// Additionally, this function decides if shrink wrapping should
347 /// be disabled for the current function, checking the following:
348 /// 1. the current function has more than 500 MBBs: heuristic limit
349 /// on function size to reduce compile time impact of the current
350 /// iterative algorithm.
351 /// 2. all CSRs are used in the entry block.
352 /// 3. all CSRs are used in all immediate successors of the entry block.
353 /// 4. all CSRs are used in a subset of blocks, each of which dominates
354 /// all return blocks. These blocks, taken as a subgraph of the MCFG,
355 /// are equivalent to the entry block since all execution paths pass
358 bool PEI::calculateSets(MachineFunction &Fn) {
359 // Sets used to compute spill, restore placement sets.
360 const std::vector<CalleeSavedInfo> CSI =
361 Fn.getFrameInfo()->getCalleeSavedInfo();
363 // If no CSRs used, we are done.
365 DEBUG(if (ShrinkWrapThisFunction)
366 dbgs() << "DISABLED: " << Fn.getName()
367 << ": uses no callee-saved registers\n");
371 // Save refs to entry and return blocks.
372 EntryBlock = Fn.begin();
373 for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
375 if (isReturnBlock(MBB))
376 ReturnBlocks.push_back(MBB);
378 // Determine if this function has fast exit paths.
379 DEBUG(if (ShrinkWrapThisFunction)
382 // Limit shrink wrapping via the current iterative bit vector
383 // implementation to functions with <= 500 MBBs.
384 if (Fn.size() > 500) {
385 DEBUG(if (ShrinkWrapThisFunction)
386 dbgs() << "DISABLED: " << Fn.getName()
387 << ": too large (" << Fn.size() << " MBBs)\n");
388 ShrinkWrapThisFunction = false;
391 // Return now if not shrink wrapping.
392 if (! ShrinkWrapThisFunction)
395 // Collect set of used CSRs.
396 for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
400 // Walk instructions in all MBBs, create CSRUsed[] sets, choose
401 // whether or not to shrink wrap this function.
402 MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
403 MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>();
404 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
406 bool allCSRUsesInEntryBlock = true;
407 for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
408 MBBI != MBBE; ++MBBI) {
409 MachineBasicBlock* MBB = MBBI;
410 for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
411 for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
412 unsigned Reg = CSI[inx].getReg();
413 // If instruction I reads or modifies Reg, add it to UsedCSRegs,
414 // CSRUsed map for the current block.
415 for (unsigned opInx = 0, opEnd = I->getNumOperands();
416 opInx != opEnd; ++opInx) {
417 const MachineOperand &MO = I->getOperand(opInx);
418 if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
420 unsigned MOReg = MO.getReg();
424 (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
425 TargetRegisterInfo::isPhysicalRegister(Reg) &&
426 TRI->isSubRegister(Reg, MOReg))) {
427 // CSR Reg is defined/used in block MBB.
428 CSRUsed[MBB].set(inx);
429 // Check for uses in EntryBlock.
430 if (MBB != EntryBlock)
431 allCSRUsesInEntryBlock = false;
437 if (CSRUsed[MBB].empty())
440 // Propagate CSRUsed[MBB] in loops
441 if (MachineLoop* LP = LI.getLoopFor(MBB)) {
442 // Add top level loop to work list.
443 MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP);
444 MachineLoop* PLP = getTopLevelLoopParent(LP);
447 HDR = PLP->getHeader();
448 assert(HDR->pred_size() > 0 && "Loop header has no predecessors?");
449 MachineBasicBlock::pred_iterator PI = HDR->pred_begin();
454 // Push uses from inside loop to its parent loops,
455 // or to all other MBBs in its loop.
456 if (LP->getLoopDepth() > 1) {
457 for (MachineLoop* PLP = LP->getParentLoop(); PLP;
458 PLP = PLP->getParentLoop()) {
459 propagateUsesAroundLoop(MBB, PLP);
462 propagateUsesAroundLoop(MBB, LP);
467 if (allCSRUsesInEntryBlock) {
468 DEBUG(dbgs() << "DISABLED: " << Fn.getName()
469 << ": all CSRs used in EntryBlock\n");
470 ShrinkWrapThisFunction = false;
472 bool allCSRsUsedInEntryFanout = true;
473 for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
474 SE = EntryBlock->succ_end(); SI != SE; ++SI) {
475 MachineBasicBlock* SUCC = *SI;
476 if (CSRUsed[SUCC] != UsedCSRegs)
477 allCSRsUsedInEntryFanout = false;
479 if (allCSRsUsedInEntryFanout) {
480 DEBUG(dbgs() << "DISABLED: " << Fn.getName()
481 << ": all CSRs used in imm successors of EntryBlock\n");
482 ShrinkWrapThisFunction = false;
486 if (ShrinkWrapThisFunction) {
487 // Check if MBB uses CSRs and dominates all exit nodes.
488 // Such nodes are equiv. to the entry node w.r.t.
489 // CSR uses: every path through the function must
490 // pass through this node. If each CSR is used at least
491 // once by these nodes, shrink wrapping is disabled.
492 CSRegSet CSRUsedInChokePoints;
493 for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
494 MBBI != MBBE; ++MBBI) {
495 MachineBasicBlock* MBB = MBBI;
496 if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
498 bool dominatesExitNodes = true;
499 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
500 if (! DT.dominates(MBB, ReturnBlocks[ri])) {
501 dominatesExitNodes = false;
504 if (dominatesExitNodes) {
505 CSRUsedInChokePoints |= CSRUsed[MBB];
506 if (CSRUsedInChokePoints == UsedCSRegs) {
507 DEBUG(dbgs() << "DISABLED: " << Fn.getName()
508 << ": all CSRs used in choke point(s) at "
509 << getBasicBlockName(MBB) << "\n");
510 ShrinkWrapThisFunction = false;
517 // Return now if we have decided not to apply shrink wrapping
518 // to the current function.
519 if (! ShrinkWrapThisFunction)
523 dbgs() << "ENABLED: " << Fn.getName();
525 dbgs() << " (fast exit path)";
527 if (ShrinkWrapDebugging >= BasicInfo) {
528 dbgs() << "------------------------------"
529 << "-----------------------------\n";
530 dbgs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n";
531 if (ShrinkWrapDebugging >= Details) {
532 dbgs() << "------------------------------"
533 << "-----------------------------\n";
539 // Build initial DF sets to determine minimal regions in the
540 // Machine CFG around which CSRs must be spilled and restored.
541 calculateAnticAvail(Fn);
546 /// addUsesForMEMERegion - add uses of CSRs spilled or restored in
547 /// multi-entry, multi-exit (MEME) regions so spill and restore
548 /// placement will not break code that enters or leaves a
549 /// shrink-wrapped region by inducing spills with no matching
550 /// restores or restores with no matching spills. A MEME region
551 /// is a subgraph of the MCFG with multiple entry edges, multiple
552 /// exit edges, or both. This code propagates use information
553 /// through the MCFG until all paths requiring spills and restores
554 /// _outside_ the computed minimal placement regions have been covered.
556 bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
557 SmallVector<MachineBasicBlock*, 4>& blks) {
558 if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
559 bool processThisBlock = false;
560 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
561 SE = MBB->succ_end(); SI != SE; ++SI) {
562 MachineBasicBlock* SUCC = *SI;
563 if (SUCC->pred_size() > 1) {
564 processThisBlock = true;
568 if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
569 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
570 PE = MBB->pred_end(); PI != PE; ++PI) {
571 MachineBasicBlock* PRED = *PI;
572 if (PRED->succ_size() > 1) {
573 processThisBlock = true;
578 if (! processThisBlock)
583 if (!CSRSave[MBB].empty())
585 else if (!CSRRestore[MBB].empty())
586 prop = CSRRestore[MBB];
592 // Propagate selected bits to successors, predecessors of MBB.
593 bool addedUses = false;
594 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
595 SE = MBB->succ_end(); SI != SE; ++SI) {
596 MachineBasicBlock* SUCC = *SI;
600 if (! CSRUsed[SUCC].contains(prop)) {
601 CSRUsed[SUCC] |= prop;
603 blks.push_back(SUCC);
604 DEBUG(if (ShrinkWrapDebugging >= Iterations)
605 dbgs() << getBasicBlockName(MBB)
606 << "(" << stringifyCSRegSet(prop) << ")->"
607 << "successor " << getBasicBlockName(SUCC) << "\n");
610 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
611 PE = MBB->pred_end(); PI != PE; ++PI) {
612 MachineBasicBlock* PRED = *PI;
616 if (! CSRUsed[PRED].contains(prop)) {
617 CSRUsed[PRED] |= prop;
619 blks.push_back(PRED);
620 DEBUG(if (ShrinkWrapDebugging >= Iterations)
621 dbgs() << getBasicBlockName(MBB)
622 << "(" << stringifyCSRegSet(prop) << ")->"
623 << "predecessor " << getBasicBlockName(PRED) << "\n");
629 /// addUsesForTopLevelLoops - add uses for CSRs used inside top
630 /// level loops to the exit blocks of those loops.
632 bool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) {
633 bool addedUses = false;
635 // Place restores for top level loops where needed.
636 for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator
637 I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) {
638 MachineBasicBlock* MBB = I->first;
639 MachineLoop* LP = I->second;
640 MachineBasicBlock* HDR = LP->getHeader();
641 SmallVector<MachineBasicBlock*, 4> exitBlocks;
644 loopSpills = CSRSave[MBB];
645 if (CSRSave[MBB].empty()) {
646 loopSpills = CSRUsed[HDR];
647 assert(!loopSpills.empty() && "No CSRs used in loop?");
648 } else if (CSRRestore[MBB].contains(CSRSave[MBB]))
651 LP->getExitBlocks(exitBlocks);
652 assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?");
653 for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
654 MachineBasicBlock* EXB = exitBlocks[i];
655 if (! CSRUsed[EXB].contains(loopSpills)) {
656 CSRUsed[EXB] |= loopSpills;
658 DEBUG(if (ShrinkWrapDebugging >= Iterations)
659 dbgs() << "LOOP " << getBasicBlockName(MBB)
660 << "(" << stringifyCSRegSet(loopSpills) << ")->"
661 << getBasicBlockName(EXB) << "\n");
662 if (EXB->succ_size() > 1 || EXB->pred_size() > 1)
670 /// calcSpillPlacements - determine which CSRs should be spilled
671 /// in MBB using AnticIn sets of MBB's predecessors, keeping track
672 /// of changes to spilled reg sets. Add MBB to the set of blocks
673 /// that need to be processed for propagating use info to cover
674 /// multi-entry/exit regions.
676 bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
677 SmallVector<MachineBasicBlock*, 4> &blks,
678 CSRegBlockMap &prevSpills) {
679 bool placedSpills = false;
680 // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB)
681 CSRegSet anticInPreds;
682 SmallVector<MachineBasicBlock*, 4> predecessors;
683 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
684 PE = MBB->pred_end(); PI != PE; ++PI) {
685 MachineBasicBlock* PRED = *PI;
687 predecessors.push_back(PRED);
689 unsigned i = 0, e = predecessors.size();
691 MachineBasicBlock* PRED = predecessors[i];
692 anticInPreds = UsedCSRegs - AnticIn[PRED];
693 for (++i; i != e; ++i) {
694 PRED = predecessors[i];
695 anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
698 // Handle uses in entry blocks (which have no predecessors).
699 // This is necessary because the DFA formulation assumes the
700 // entry and (multiple) exit nodes cannot have CSR uses, which
701 // is not the case in the real world.
702 anticInPreds = UsedCSRegs;
704 // Compute spills required at MBB:
705 CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
707 if (! CSRSave[MBB].empty()) {
708 if (MBB == EntryBlock) {
709 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
710 CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
712 // Reset all regs spilled in MBB that are also spilled in EntryBlock.
713 if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
714 CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
718 placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
719 prevSpills[MBB] = CSRSave[MBB];
720 // Remember this block for adding restores to successor
721 // blocks for multi-entry region.
725 DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
726 dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
727 << stringifyCSRegSet(CSRSave[MBB]) << "\n");
732 /// calcRestorePlacements - determine which CSRs should be restored
733 /// in MBB using AvailOut sets of MBB's succcessors, keeping track
734 /// of changes to restored reg sets. Add MBB to the set of blocks
735 /// that need to be processed for propagating use info to cover
736 /// multi-entry/exit regions.
738 bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
739 SmallVector<MachineBasicBlock*, 4> &blks,
740 CSRegBlockMap &prevRestores) {
741 bool placedRestores = false;
742 // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB)
743 CSRegSet availOutSucc;
744 SmallVector<MachineBasicBlock*, 4> successors;
745 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
746 SE = MBB->succ_end(); SI != SE; ++SI) {
747 MachineBasicBlock* SUCC = *SI;
749 successors.push_back(SUCC);
751 unsigned i = 0, e = successors.size();
753 MachineBasicBlock* SUCC = successors[i];
754 availOutSucc = UsedCSRegs - AvailOut[SUCC];
755 for (++i; i != e; ++i) {
756 SUCC = successors[i];
757 availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
760 if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
761 // Handle uses in return blocks (which have no successors).
762 // This is necessary because the DFA formulation assumes the
763 // entry and (multiple) exit nodes cannot have CSR uses, which
764 // is not the case in the real world.
765 availOutSucc = UsedCSRegs;
768 // Compute restores required at MBB:
769 CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
771 // Postprocess restore placements at MBB.
772 // Remove the CSRs that are restored in the return blocks.
773 // Lest this be confusing, note that:
774 // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks.
775 if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
776 if (! CSRSave[EntryBlock].empty())
777 CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
779 placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
780 prevRestores[MBB] = CSRRestore[MBB];
781 // Remember this block for adding saves to predecessor
782 // blocks for multi-entry region.
786 DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
787 dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = "
788 << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
790 return placedRestores;
793 /// placeSpillsAndRestores - place spills and restores of CSRs
794 /// used in MBBs in minimal regions that contain the uses.
796 void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
797 CSRegBlockMap prevCSRSave;
798 CSRegBlockMap prevCSRRestore;
799 SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks;
801 unsigned iterations = 0;
803 // Iterate computation of spill and restore placements in the MCFG until:
804 // 1. CSR use info has been fully propagated around the MCFG, and
805 // 2. computation of CSRSave[], CSRRestore[] reach fixed points.
810 DEBUG(if (ShrinkWrapDebugging >= Iterations)
811 dbgs() << "iter " << iterations
812 << " --------------------------------------------------\n");
814 // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG,
815 // which determines the placements of spills and restores.
816 // Keep track of changes to spills, restores in each iteration to
817 // minimize the total iterations.
818 bool SRChanged = false;
819 for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
820 MBBI != MBBE; ++MBBI) {
821 MachineBasicBlock* MBB = MBBI;
823 // Place spills for CSRs in MBB.
824 SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
826 // Place restores for CSRs in MBB.
827 SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
830 // Add uses of CSRs used inside loops where needed.
831 changed |= addUsesForTopLevelLoops(cvBlocks);
833 // Add uses for CSRs spilled or restored at branch, join points.
834 if (changed || SRChanged) {
835 while (! cvBlocks.empty()) {
836 MachineBasicBlock* MBB = cvBlocks.pop_back_val();
837 changed |= addUsesForMEMERegion(MBB, ncvBlocks);
839 if (! ncvBlocks.empty()) {
840 cvBlocks = ncvBlocks;
846 calculateAnticAvail(Fn);
852 // Check for effectiveness:
853 // SR0 = {r | r in CSRSave[EntryBlock], CSRRestore[RB], RB in ReturnBlocks}
854 // numSRReduced = |(UsedCSRegs - SR0)|, approx. SR0 by CSRSave[EntryBlock]
855 // Gives a measure of how many CSR spills have been moved from EntryBlock
856 // to minimal regions enclosing their uses.
857 CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]);
858 unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count();
859 numSRReduced += numSRReducedThisFunc;
860 DEBUG(if (ShrinkWrapDebugging >= BasicInfo) {
861 dbgs() << "-----------------------------------------------------------\n";
862 dbgs() << "total iterations = " << iterations << " ( "
864 << " " << numSRReducedThisFunc
867 dbgs() << "-----------------------------------------------------------\n";
869 dbgs() << "-----------------------------------------------------------\n";
870 if (numSRReducedThisFunc)
871 verifySpillRestorePlacement();
875 // Debugging methods.
877 /// findFastExitPath - debugging method used to detect functions
878 /// with at least one path from the entry block to a return block
879 /// directly or which has a very small number of edges.
881 void PEI::findFastExitPath() {
884 // Fina a path from EntryBlock to any return block that does not branch:
892 for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
893 SE = EntryBlock->succ_end(); SI != SE; ++SI) {
894 MachineBasicBlock* SUCC = *SI;
896 // Assume positive, disprove existence of fast path.
897 HasFastExitPath = true;
899 // Check the immediate successors.
900 if (isReturnBlock(SUCC)) {
901 if (ShrinkWrapDebugging >= BasicInfo)
902 dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
903 << "->" << getBasicBlockName(SUCC) << "\n";
906 // Traverse df from SUCC, look for a branch block.
907 std::string exitPath = getBasicBlockName(SUCC);
908 for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
909 BE = df_end(SUCC); BI != BE; ++BI) {
910 MachineBasicBlock* SBB = *BI;
911 // Reject paths with branch nodes.
912 if (SBB->succ_size() > 1) {
913 HasFastExitPath = false;
916 exitPath += "->" + getBasicBlockName(SBB);
918 if (HasFastExitPath) {
919 if (ShrinkWrapDebugging >= BasicInfo)
920 dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
921 << "->" << exitPath << "\n";
927 /// verifySpillRestorePlacement - check the current spill/restore
928 /// sets for safety. Attempt to find spills without restores or
929 /// restores without spills.
930 /// Spills: walk df from each MBB in spill set ensuring that
931 /// all CSRs spilled at MMBB are restored on all paths
932 /// from MBB to all exit blocks.
933 /// Restores: walk idf from each MBB in restore set ensuring that
934 /// all CSRs restored at MBB are spilled on all paths
937 void PEI::verifySpillRestorePlacement() {
938 unsigned numReturnBlocks = 0;
939 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
940 MBBI != MBBE; ++MBBI) {
941 MachineBasicBlock* MBB = MBBI;
942 if (isReturnBlock(MBB) || MBB->succ_size() == 0)
945 for (CSRegBlockMap::iterator BI = CSRSave.begin(),
946 BE = CSRSave.end(); BI != BE; ++BI) {
947 MachineBasicBlock* MBB = BI->first;
948 CSRegSet spilled = BI->second;
954 DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
955 << stringifyCSRegSet(spilled)
956 << " RESTORE[" << getBasicBlockName(MBB) << "] = "
957 << stringifyCSRegSet(CSRRestore[MBB]) << "\n");
959 if (CSRRestore[MBB].intersects(spilled)) {
960 restored |= (CSRRestore[MBB] & spilled);
963 // Walk depth first from MBB to find restores of all CSRs spilled at MBB:
964 // we must find restores for all spills w/no intervening spills on all
965 // paths from MBB to all return blocks.
966 for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB),
967 BE = df_end(MBB); BI != BE; ++BI) {
968 MachineBasicBlock* SBB = *BI;
971 // Stop when we encounter spills of any CSRs spilled at MBB that
972 // have not yet been seen to be restored.
973 if (CSRSave[SBB].intersects(spilled) &&
974 !restored.contains(CSRSave[SBB] & spilled))
976 // Collect the CSRs spilled at MBB that are restored
977 // at this DF successor of MBB.
978 if (CSRRestore[SBB].intersects(spilled))
979 restored |= (CSRRestore[SBB] & spilled);
980 // If we are at a retun block, check that the restores
981 // we have seen so far exhaust the spills at MBB, then
982 // reset the restores.
983 if (isReturnBlock(SBB) || SBB->succ_size() == 0) {
984 if (restored != spilled) {
985 CSRegSet notRestored = (spilled - restored);
986 DEBUG(dbgs() << MF->getName() << ": "
987 << stringifyCSRegSet(notRestored)
988 << " spilled at " << getBasicBlockName(MBB)
989 << " are never restored on path to return "
990 << getBasicBlockName(SBB) << "\n");
997 // Check restore placements.
998 for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
999 BE = CSRRestore.end(); BI != BE; ++BI) {
1000 MachineBasicBlock* MBB = BI->first;
1001 CSRegSet restored = BI->second;
1004 if (restored.empty())
1007 DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
1008 << stringifyCSRegSet(CSRSave[MBB])
1009 << " RESTORE[" << getBasicBlockName(MBB) << "] = "
1010 << stringifyCSRegSet(restored) << "\n");
1012 if (CSRSave[MBB].intersects(restored)) {
1013 spilled |= (CSRSave[MBB] & restored);
1015 // Walk inverse depth first from MBB to find spills of all
1016 // CSRs restored at MBB:
1017 for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB),
1018 BE = idf_end(MBB); BI != BE; ++BI) {
1019 MachineBasicBlock* PBB = *BI;
1022 // Stop when we encounter restores of any CSRs restored at MBB that
1023 // have not yet been seen to be spilled.
1024 if (CSRRestore[PBB].intersects(restored) &&
1025 !spilled.contains(CSRRestore[PBB] & restored))
1027 // Collect the CSRs restored at MBB that are spilled
1028 // at this DF predecessor of MBB.
1029 if (CSRSave[PBB].intersects(restored))
1030 spilled |= (CSRSave[PBB] & restored);
1032 if (spilled != restored) {
1033 CSRegSet notSpilled = (restored - spilled);
1034 DEBUG(dbgs() << MF->getName() << ": "
1035 << stringifyCSRegSet(notSpilled)
1036 << " restored at " << getBasicBlockName(MBB)
1037 << " are never spilled\n");
1042 // Debugging print methods.
1043 std::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) {
1047 if (MBB->getBasicBlock())
1048 return MBB->getBasicBlock()->getName().str();
1050 std::ostringstream name;
1051 name << "_MBB_" << MBB->getNumber();
1055 std::string PEI::stringifyCSRegSet(const CSRegSet& s) {
1056 const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
1057 const std::vector<CalleeSavedInfo> CSI =
1058 MF->getFrameInfo()->getCalleeSavedInfo();
1060 std::ostringstream srep;
1061 if (CSI.size() == 0) {
1066 CSRegSet::iterator I = s.begin(), E = s.end();
1068 unsigned reg = CSI[*I].getReg();
1069 srep << TRI->getName(reg);
1070 for (++I; I != E; ++I) {
1071 reg = CSI[*I].getReg();
1073 srep << TRI->getName(reg);
1080 void PEI::dumpSet(const CSRegSet& s) {
1081 DEBUG(dbgs() << stringifyCSRegSet(s) << "\n");
1084 void PEI::dumpUsed(MachineBasicBlock* MBB) {
1087 dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
1088 << stringifyCSRegSet(CSRUsed[MBB]) << "\n";
1092 void PEI::dumpAllUsed() {
1093 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1094 MBBI != MBBE; ++MBBI) {
1095 MachineBasicBlock* MBB = MBBI;
1100 void PEI::dumpSets(MachineBasicBlock* MBB) {
1103 dbgs() << getBasicBlockName(MBB) << " | "
1104 << stringifyCSRegSet(CSRUsed[MBB]) << " | "
1105 << stringifyCSRegSet(AnticIn[MBB]) << " | "
1106 << stringifyCSRegSet(AnticOut[MBB]) << " | "
1107 << stringifyCSRegSet(AvailIn[MBB]) << " | "
1108 << stringifyCSRegSet(AvailOut[MBB]) << "\n";
1112 void PEI::dumpSets1(MachineBasicBlock* MBB) {
1115 dbgs() << getBasicBlockName(MBB) << " | "
1116 << stringifyCSRegSet(CSRUsed[MBB]) << " | "
1117 << stringifyCSRegSet(AnticIn[MBB]) << " | "
1118 << stringifyCSRegSet(AnticOut[MBB]) << " | "
1119 << stringifyCSRegSet(AvailIn[MBB]) << " | "
1120 << stringifyCSRegSet(AvailOut[MBB]) << " | "
1121 << stringifyCSRegSet(CSRSave[MBB]) << " | "
1122 << stringifyCSRegSet(CSRRestore[MBB]) << "\n";
1126 void PEI::dumpAllSets() {
1127 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1128 MBBI != MBBE; ++MBBI) {
1129 MachineBasicBlock* MBB = MBBI;
1134 void PEI::dumpSRSets() {
1136 for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
1138 if (!CSRSave[MBB].empty()) {
1139 dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
1140 << stringifyCSRegSet(CSRSave[MBB]);
1141 if (CSRRestore[MBB].empty())
1145 if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty())
1147 << "RESTORE[" << getBasicBlockName(MBB) << "] = "
1148 << stringifyCSRegSet(CSRRestore[MBB]) << "\n";