1378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===// 2378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 3378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// The LLVM Compiler Infrastructure 4378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 5378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This file is distributed under the University of Illinois Open Source 6378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// License. See LICENSE.TXT for details. 7378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 8378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 9378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 10378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This file implements a shrink wrapping variant of prolog/epilog insertion: 11378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// - Spills and restores of callee-saved registers (CSRs) are placed in the 12378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// machine CFG to tightly surround their uses so that execution paths that 13378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// do not use CSRs do not pay the spill/restore penalty. 14378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 15378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// - Avoiding placment of spills/restores in loops: if a CSR is used inside a 16378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// loop the spills are placed in the loop preheader, and restores are 17378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// placed in the loop exit nodes (the successors of loop _exiting_ nodes). 18378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 19378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// - Covering paths without CSR uses: 20378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// If a region in a CFG uses CSRs and has multiple entry and/or exit points, 21378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// the use info for the CSRs inside the region is propagated outward in the 22378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// CFG to ensure validity of the spill/restore placements. This decreases 23378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// the effectiveness of shrink wrapping but does not require edge splitting 24378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// in the machine CFG. 25378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 26378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This shrink wrapping implementation uses an iterative analysis to determine 27378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// which basic blocks require spills and restores for CSRs. 28378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 29378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// This pass uses MachineDominators and MachineLoopInfo. Loop information 30378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// is used to prevent placement of callee-saved register spills/restores 31378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// in the bodies of loops. 32378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// 33378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 34378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 35378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#define DEBUG_TYPE "shrink-wrap" 36378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 37752c1df73949438ef6fa86a86363ee7091aa2532John Mosby#include "PrologEpilogInserter.h" 38378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/ADT/DenseMap.h" 39378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/ADT/PostOrderIterator.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 41d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SparseBitVector.h" 42378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/ADT/Statistic.h" 43d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineDominators.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 45d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstr.h" 46d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 47d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 48378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/Support/CommandLine.h" 49378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/Support/Compiler.h" 50378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include "llvm/Support/Debug.h" 51d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 52d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 53378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#include <sstream> 54378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 55378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyusing namespace llvm; 56378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 57378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbySTATISTIC(numSRReduced, "Number of CSR spills+restores reduced."); 58378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 59378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Shrink Wrapping: 60378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbystatic cl::opt<bool> 61378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbyShrinkWrapping("shrink-wrap", 62378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::desc("Shrink wrap callee-saved register spills/restores")); 63378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 64378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Shrink wrap only the specified function, a debugging aid. 65378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbystatic cl::opt<std::string> 66378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbyShrinkWrapFunc("shrink-wrap-func", cl::Hidden, 67378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::desc("Shrink wrap the specified function"), 68378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::value_desc("funcname"), 69378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::init("")); 70378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 71378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Debugging level for shrink wrapping. 72378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyenum ShrinkWrapDebugLevel { 73378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby None, BasicInfo, Iterations, Details 74378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby}; 75378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 76378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbystatic cl::opt<enum ShrinkWrapDebugLevel> 77378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbyShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden, 78378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::desc("Print shrink wrapping debugging information"), 79378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cl::values( 80378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clEnumVal(None , "disable debug output"), 81378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clEnumVal(BasicInfo , "print basic DF sets"), 82378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clEnumVal(Iterations, "print SR sets for each iteration"), 83378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clEnumVal(Details , "print all DF sets"), 84378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clEnumValEnd)); 85378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 86378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 87378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::getAnalysisUsage(AnalysisUsage &AU) const { 88378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AU.setPreservesCFG(); 89378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapping || ShrinkWrapFunc != "") { 90378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AU.addRequired<MachineLoopInfo>(); 91378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AU.addRequired<MachineDominatorTree>(); 92378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 93378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AU.addPreserved<MachineLoopInfo>(); 94378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AU.addPreserved<MachineDominatorTree>(); 9525600cf50df79a6e7f8365a3ca7e940592e8ca74Andrew Trick AU.addRequired<TargetPassConfig>(); 96378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineFunctionPass::getAnalysisUsage(AU); 97378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 98378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 99378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 100378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// ShrinkWrapping implementation 101378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby//===----------------------------------------------------------------------===// 102378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 103378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Convienences for dealing with machine loops. 104378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbyMachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) { 105378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby assert(LP && "Machine loop is NULL."); 106378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PHDR = LP->getLoopPreheader(); 107378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoop* PLP = LP->getParentLoop(); 108378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby while (PLP) { 109378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PHDR = PLP->getLoopPreheader(); 110378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PLP = PLP->getParentLoop(); 111378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 112378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return PHDR; 113378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 114378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 115378553cb079aba2b8dee5d52b5166316d4132d5aJohn MosbyMachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) { 116378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (LP == 0) 117378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return 0; 118378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoop* PLP = LP->getParentLoop(); 119378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby while (PLP) { 120378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby LP = PLP; 121378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PLP = PLP->getParentLoop(); 122378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 123378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return LP; 124378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 125378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 126378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::isReturnBlock(MachineBasicBlock* MBB) { 1275a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return (MBB && !MBB->empty() && MBB->back().isReturn()); 128378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 129378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 130378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Initialize shrink wrapping DFA sets, called before iterations. 131378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::clearAnticAvailSets() { 132378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AnticIn.clear(); 133378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AnticOut.clear(); 134378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AvailIn.clear(); 135378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AvailOut.clear(); 136378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 137378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 138378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Clear all sets constructed by shrink wrapping. 139378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::clearAllSets() { 140378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ReturnBlocks.clear(); 141378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clearAnticAvailSets(); 142378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby UsedCSRegs.clear(); 143378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed.clear(); 144378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby TLLoops.clear(); 145378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRSave.clear(); 146378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRRestore.clear(); 147378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 148378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 149378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Initialize all shrink wrapping data. 150378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::initShrinkWrappingInfo() { 151378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clearAllSets(); 152378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby EntryBlock = 0; 153378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef NDEBUG 154378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby HasFastExitPath = false; 155378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 156378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = ShrinkWrapping; 157378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // DEBUG: enable or disable shrink wrapping for the current function 158378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // via --shrink-wrap-func=<funcname>. 159378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef NDEBUG 160378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapFunc != "") { 16196601ca332ab388754ca4673be8973396fea2dddCraig Topper std::string MFName = MF->getName().str(); 162378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc); 163378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 164378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 165378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 166378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 167378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 168378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// placeCSRSpillsAndRestores - determine which MBBs of the function 169378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// need save, restore code for callee-saved registers by doing a DF analysis 170378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// similar to the one used in code motion (GVNPRE). This produces maps of MBBs 171378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// to sets of registers (CSRs) for saves and restores. MachineLoopInfo 172378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// is used to ensure that CSR save/restore code is not placed inside loops. 173378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// This function computes the maps of MBBs -> CSRs to spill and restore 174378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// in CSRSave, CSRRestore. 175378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 176378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// If shrink wrapping is not being performed, place all spills in 177378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// the entry block, all restores in return blocks. In this case, 178378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// CSRSave has a single mapping, CSRRestore has mappings for each 179378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// return block. 180378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 181378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) { 182378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 183378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(MF = &Fn); 184378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 185378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby initShrinkWrappingInfo(); 186378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 187378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapThisFunction) { 1880d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "Place CSR spills/restores for " 18996601ca332ab388754ca4673be8973396fea2dddCraig Topper << MF->getName() << "\n"; 190378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby }); 191378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 192378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (calculateSets(Fn)) 193378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby placeSpillsAndRestores(Fn); 194378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 195378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 196378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calcAnticInOut - calculate the anticipated in/out reg sets 197378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// for the given MBB by looking forward in the MCFG at MBB's 198378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// successors. 199378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 200378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::calcAnticInOut(MachineBasicBlock* MBB) { 201378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool changed = false; 202378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 203378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // AnticOut[MBB] = INTERSECT(AnticIn[S] for S in SUCCESSORS(MBB)) 204378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> successors; 205378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 206378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = MBB->succ_end(); SI != SE; ++SI) { 207378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 208378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SUCC != MBB) 209378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby successors.push_back(SUCC); 210378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 211378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 212378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned i = 0, e = successors.size(); 213378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (i != e) { 214378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet prevAnticOut = AnticOut[MBB]; 215378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = successors[i]; 216378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 217378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AnticOut[MBB] = AnticIn[SUCC]; 218378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (++i; i != e; ++i) { 219378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SUCC = successors[i]; 220378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AnticOut[MBB] &= AnticIn[SUCC]; 221378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 222378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (prevAnticOut != AnticOut[MBB]) 223378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = true; 224378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 225378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 226378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // AnticIn[MBB] = UNION(CSRUsed[MBB], AnticOut[MBB]); 227378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet prevAnticIn = AnticIn[MBB]; 228378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB]; 229b7683c06cb4ec7554d68704e2ca74ad75415a1d5Jakob Stoklund Olesen if (prevAnticIn != AnticIn[MBB]) 230378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = true; 231378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return changed; 232378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 233378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 234378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calcAvailInOut - calculate the available in/out reg sets 235378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// for the given MBB by looking backward in the MCFG at MBB's 236378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// predecessors. 237378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 238378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::calcAvailInOut(MachineBasicBlock* MBB) { 239378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool changed = false; 240378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 241378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // AvailIn[MBB] = INTERSECT(AvailOut[P] for P in PREDECESSORS(MBB)) 242378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> predecessors; 243378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 244378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PE = MBB->pred_end(); PI != PE; ++PI) { 245378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = *PI; 246378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (PRED != MBB) 247378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby predecessors.push_back(PRED); 248378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 249378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 250378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned i = 0, e = predecessors.size(); 251378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (i != e) { 252378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet prevAvailIn = AvailIn[MBB]; 253378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = predecessors[i]; 254378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 255378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AvailIn[MBB] = AvailOut[PRED]; 256378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (++i; i != e; ++i) { 257378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PRED = predecessors[i]; 258378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AvailIn[MBB] &= AvailOut[PRED]; 259378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 260378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (prevAvailIn != AvailIn[MBB]) 261378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = true; 262378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 263378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 264378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // AvailOut[MBB] = UNION(CSRUsed[MBB], AvailIn[MBB]); 265378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet prevAvailOut = AvailOut[MBB]; 266378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB]; 267b7683c06cb4ec7554d68704e2ca74ad75415a1d5Jakob Stoklund Olesen if (prevAvailOut != AvailOut[MBB]) 268378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = true; 269378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return changed; 270378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 271378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 272378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calculateAnticAvail - build the sets anticipated and available 273378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// registers in the MCFG of the current function iteratively, 274378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// doing a combined forward and backward analysis. 275378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 276378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::calculateAnticAvail(MachineFunction &Fn) { 277378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Initialize data flow sets. 278378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby clearAnticAvailSets(); 279378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 2807a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Calculate Antic{In,Out} and Avail{In,Out} iteratively on the MCFG. 281378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool changed = true; 282378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned iterations = 0; 283378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby while (changed) { 284378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = false; 285378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ++iterations; 286378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 287378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 288378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 289378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 290378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Calculate anticipated in, out regs at MBB from 291378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // anticipated at successors of MBB. 292378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed |= calcAnticInOut(MBB); 293378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 294378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Calculate available in, out regs at MBB from 295378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // available at predecessors of MBB. 296378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed |= calcAvailInOut(MBB); 297378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 298378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 299378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 3009c52affd374e20b212d3266050f13d87ba80e36dBill Wendling DEBUG({ 3019c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (ShrinkWrapDebugging >= Details) { 3020d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() 3039c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "-----------------------------------------------------------\n" 3049c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " Antic/Avail Sets:\n" 3059c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "-----------------------------------------------------------\n" 3069c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "iterations = " << iterations << "\n" 3079c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "-----------------------------------------------------------\n" 3089c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n" 3099c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "-----------------------------------------------------------\n"; 3109c52affd374e20b212d3266050f13d87ba80e36dBill Wendling 3119c52affd374e20b212d3266050f13d87ba80e36dBill Wendling for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 3129c52affd374e20b212d3266050f13d87ba80e36dBill Wendling MBBI != MBBE; ++MBBI) { 3139c52affd374e20b212d3266050f13d87ba80e36dBill Wendling MachineBasicBlock* MBB = MBBI; 3149c52affd374e20b212d3266050f13d87ba80e36dBill Wendling dumpSets(MBB); 3159c52affd374e20b212d3266050f13d87ba80e36dBill Wendling } 3169c52affd374e20b212d3266050f13d87ba80e36dBill Wendling 3170d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() 3189c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "-----------------------------------------------------------\n"; 319378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 320378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby }); 321378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 322378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 323378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// propagateUsesAroundLoop - copy used register info from MBB to all blocks 324378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// of the loop given by LP and its parent loops. This prevents spills/restores 325378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// from being placed in the bodies of loops. 326378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 327378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) { 328378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! MBB || !LP) 329378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return; 330378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 331378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks(); 332378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) { 333378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* LBB = loopBlocks[i]; 334378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (LBB == MBB) 335378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 336378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRUsed[LBB].contains(CSRUsed[MBB])) 337378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 338378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed[LBB] |= CSRUsed[MBB]; 339378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 340378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 341378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 342378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calculateSets - collect the CSRs used in this function, compute 343378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// the DF sets that describe the initial minimal regions in the 344378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// Machine CFG around which CSR spills and restores must be placed. 345378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 346378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// Additionally, this function decides if shrink wrapping should 347378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// be disabled for the current function, checking the following: 348378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 1. the current function has more than 500 MBBs: heuristic limit 349378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// on function size to reduce compile time impact of the current 350378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// iterative algorithm. 351378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 2. all CSRs are used in the entry block. 352378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 3. all CSRs are used in all immediate successors of the entry block. 353378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 4. all CSRs are used in a subset of blocks, each of which dominates 354378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// all return blocks. These blocks, taken as a subgraph of the MCFG, 355378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// are equivalent to the entry block since all execution paths pass 356378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// through them. 357378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 358378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::calculateSets(MachineFunction &Fn) { 359378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Sets used to compute spill, restore placement sets. 360378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby const std::vector<CalleeSavedInfo> CSI = 361378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby Fn.getFrameInfo()->getCalleeSavedInfo(); 362378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 363378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // If no CSRs used, we are done. 364378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSI.empty()) { 365378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapThisFunction) 36696601ca332ab388754ca4673be8973396fea2dddCraig Topper dbgs() << "DISABLED: " << Fn.getName() 367ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << ": uses no callee-saved registers\n"); 368378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return false; 369378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 370378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 371378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Save refs to entry and return blocks. 372378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby EntryBlock = Fn.begin(); 373378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end(); 374378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBB != E; ++MBB) 375378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (isReturnBlock(MBB)) 376378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ReturnBlocks.push_back(MBB); 377378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 378378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Determine if this function has fast exit paths. 379378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapThisFunction) 380378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby findFastExitPath()); 381378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 382378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Limit shrink wrapping via the current iterative bit vector 383378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // implementation to functions with <= 500 MBBs. 384378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (Fn.size() > 500) { 385378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapThisFunction) 38696601ca332ab388754ca4673be8973396fea2dddCraig Topper dbgs() << "DISABLED: " << Fn.getName() 387ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << ": too large (" << Fn.size() << " MBBs)\n"); 388378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = false; 389378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 390378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 391378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Return now if not shrink wrapping. 392378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! ShrinkWrapThisFunction) 393378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return false; 394378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 395378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Collect set of used CSRs. 396378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) { 397378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby UsedCSRegs.set(inx); 398378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 399378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 400378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Walk instructions in all MBBs, create CSRUsed[] sets, choose 401378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // whether or not to shrink wrap this function. 402378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>(); 403378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>(); 404378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 405378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 406378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool allCSRUsesInEntryBlock = true; 407378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 408378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 409378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 410378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) { 411378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) { 412378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned Reg = CSI[inx].getReg(); 413378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // If instruction I reads or modifies Reg, add it to UsedCSRegs, 414378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSRUsed map for the current block. 415378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned opInx = 0, opEnd = I->getNumOperands(); 416378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby opInx != opEnd; ++opInx) { 417378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby const MachineOperand &MO = I->getOperand(opInx); 418378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! (MO.isReg() && (MO.isUse() || MO.isDef()))) 419378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 420378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned MOReg = MO.getReg(); 421378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (!MOReg) 422378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 423378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MOReg == Reg || 424378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby (TargetRegisterInfo::isPhysicalRegister(MOReg) && 425378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby TargetRegisterInfo::isPhysicalRegister(Reg) && 426378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby TRI->isSubRegister(Reg, MOReg))) { 427378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSR Reg is defined/used in block MBB. 428378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed[MBB].set(inx); 429378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Check for uses in EntryBlock. 430378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MBB != EntryBlock) 431378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby allCSRUsesInEntryBlock = false; 432378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 433378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 434378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 435378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 436378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 437378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRUsed[MBB].empty()) 438378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 439378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 440378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Propagate CSRUsed[MBB] in loops 441378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MachineLoop* LP = LI.getLoopFor(MBB)) { 442378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Add top level loop to work list. 443378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP); 444378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoop* PLP = getTopLevelLoopParent(LP); 445378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 446378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! HDR) { 447378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby HDR = PLP->getHeader(); 448378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby assert(HDR->pred_size() > 0 && "Loop header has no predecessors?"); 449378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock::pred_iterator PI = HDR->pred_begin(); 450378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby HDR = *PI; 451378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 452378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby TLLoops[HDR] = PLP; 453378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 454378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Push uses from inside loop to its parent loops, 455378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // or to all other MBBs in its loop. 456378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (LP->getLoopDepth() > 1) { 457378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineLoop* PLP = LP->getParentLoop(); PLP; 458378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PLP = PLP->getParentLoop()) { 459378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby propagateUsesAroundLoop(MBB, PLP); 460378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 461378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else { 462378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby propagateUsesAroundLoop(MBB, LP); 463378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 464378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 465378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 466378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 467378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (allCSRUsesInEntryBlock) { 46896601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "DISABLED: " << Fn.getName() 4699c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << ": all CSRs used in EntryBlock\n"); 470378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = false; 471378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else { 472378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool allCSRsUsedInEntryFanout = true; 473378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(), 474378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = EntryBlock->succ_end(); SI != SE; ++SI) { 475378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 476378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRUsed[SUCC] != UsedCSRegs) 477378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby allCSRsUsedInEntryFanout = false; 478378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 479378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (allCSRsUsedInEntryFanout) { 48096601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "DISABLED: " << Fn.getName() 4819c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << ": all CSRs used in imm successors of EntryBlock\n"); 482378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = false; 483378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 484378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 485378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 486378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapThisFunction) { 487378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Check if MBB uses CSRs and dominates all exit nodes. 488378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Such nodes are equiv. to the entry node w.r.t. 489378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSR uses: every path through the function must 490378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // pass through this node. If each CSR is used at least 491378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // once by these nodes, shrink wrapping is disabled. 492378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet CSRUsedInChokePoints; 493378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 494378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 495378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 496378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1) 497378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 498378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool dominatesExitNodes = true; 499378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) 500378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! DT.dominates(MBB, ReturnBlocks[ri])) { 501378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby dominatesExitNodes = false; 502378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 503378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 504378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (dominatesExitNodes) { 505378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsedInChokePoints |= CSRUsed[MBB]; 506378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRUsedInChokePoints == UsedCSRegs) { 50796601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "DISABLED: " << Fn.getName() 5089c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << ": all CSRs used in choke point(s) at " 5099c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << getBasicBlockName(MBB) << "\n"); 510378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ShrinkWrapThisFunction = false; 511378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 512378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 513378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 514378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 515378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 516378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 517378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Return now if we have decided not to apply shrink wrapping 518378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // to the current function. 519378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! ShrinkWrapThisFunction) 520378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return false; 521378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 522378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG({ 52396601ca332ab388754ca4673be8973396fea2dddCraig Topper dbgs() << "ENABLED: " << Fn.getName(); 524378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (HasFastExitPath) 5250d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << " (fast exit path)"; 5260d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "\n"; 527378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapDebugging >= BasicInfo) { 5280d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "------------------------------" 529378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "-----------------------------\n"; 5300d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n"; 531378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapDebugging >= Details) { 5320d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "------------------------------" 533378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "-----------------------------\n"; 534378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby dumpAllUsed(); 535378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 536378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 537378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby }); 538378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 539378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Build initial DF sets to determine minimal regions in the 540378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Machine CFG around which CSRs must be spilled and restored. 541378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby calculateAnticAvail(Fn); 542378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 543378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return true; 544378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 545378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 546378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// addUsesForMEMERegion - add uses of CSRs spilled or restored in 547378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// multi-entry, multi-exit (MEME) regions so spill and restore 548378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// placement will not break code that enters or leaves a 549378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// shrink-wrapped region by inducing spills with no matching 550378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// restores or restores with no matching spills. A MEME region 551378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// is a subgraph of the MCFG with multiple entry edges, multiple 552378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// exit edges, or both. This code propagates use information 553378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// through the MCFG until all paths requiring spills and restores 554378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// _outside_ the computed minimal placement regions have been covered. 555378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 556378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB, 557378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4>& blks) { 558378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MBB->succ_size() < 2 && MBB->pred_size() < 2) { 559378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool processThisBlock = false; 560378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 561378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = MBB->succ_end(); SI != SE; ++SI) { 562378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 563378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SUCC->pred_size() > 1) { 564378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby processThisBlock = true; 565378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 566378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 567378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 568378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) { 569378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 570378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PE = MBB->pred_end(); PI != PE; ++PI) { 571378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = *PI; 572378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (PRED->succ_size() > 1) { 573378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby processThisBlock = true; 574378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 575378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 576378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 577378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 578378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! processThisBlock) 579378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return false; 580378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 581378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 582378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet prop; 583378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (!CSRSave[MBB].empty()) 584378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby prop = CSRSave[MBB]; 585378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby else if (!CSRRestore[MBB].empty()) 586378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby prop = CSRRestore[MBB]; 587378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby else 588378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby prop = CSRUsed[MBB]; 589378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (prop.empty()) 590378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return false; 591378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 592378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Propagate selected bits to successors, predecessors of MBB. 593378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool addedUses = false; 594378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 595378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = MBB->succ_end(); SI != SE; ++SI) { 596378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 597378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Self-loop 598378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SUCC == MBB) 599378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 600378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRUsed[SUCC].contains(prop)) { 601378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed[SUCC] |= prop; 602378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby addedUses = true; 603378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby blks.push_back(SUCC); 604378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapDebugging >= Iterations) 6050d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << getBasicBlockName(MBB) 606378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "(" << stringifyCSRegSet(prop) << ")->" 607378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "successor " << getBasicBlockName(SUCC) << "\n"); 608378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 609378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 610378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 611378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PE = MBB->pred_end(); PI != PE; ++PI) { 612378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = *PI; 613378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Self-loop 614378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (PRED == MBB) 615378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 616378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRUsed[PRED].contains(prop)) { 617378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed[PRED] |= prop; 618378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby addedUses = true; 619378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby blks.push_back(PRED); 620378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapDebugging >= Iterations) 6210d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << getBasicBlockName(MBB) 622378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "(" << stringifyCSRegSet(prop) << ")->" 623378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "predecessor " << getBasicBlockName(PRED) << "\n"); 624378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 625378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 626378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return addedUses; 627378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 628378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 629378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// addUsesForTopLevelLoops - add uses for CSRs used inside top 630378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// level loops to the exit blocks of those loops. 631378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 632378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) { 633378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool addedUses = false; 634378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 635378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Place restores for top level loops where needed. 636378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator 637378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) { 638378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = I->first; 639378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineLoop* LP = I->second; 640378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* HDR = LP->getHeader(); 641378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> exitBlocks; 642378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet loopSpills; 643378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 644378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby loopSpills = CSRSave[MBB]; 645378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRSave[MBB].empty()) { 646378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby loopSpills = CSRUsed[HDR]; 647378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby assert(!loopSpills.empty() && "No CSRs used in loop?"); 648378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else if (CSRRestore[MBB].contains(CSRSave[MBB])) 649378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 650378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 651378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby LP->getExitBlocks(exitBlocks); 652378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?"); 653378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) { 654378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* EXB = exitBlocks[i]; 655378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRUsed[EXB].contains(loopSpills)) { 656378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRUsed[EXB] |= loopSpills; 657378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby addedUses = true; 658378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapDebugging >= Iterations) 6590d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "LOOP " << getBasicBlockName(MBB) 660378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "(" << stringifyCSRegSet(loopSpills) << ")->" 661378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << getBasicBlockName(EXB) << "\n"); 662378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (EXB->succ_size() > 1 || EXB->pred_size() > 1) 663378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby blks.push_back(EXB); 664378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 665378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 666378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 667378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return addedUses; 668378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 669378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 670378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calcSpillPlacements - determine which CSRs should be spilled 671378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// in MBB using AnticIn sets of MBB's predecessors, keeping track 672378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// of changes to spilled reg sets. Add MBB to the set of blocks 673378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// that need to be processed for propagating use info to cover 674378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// multi-entry/exit regions. 675378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 676378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::calcSpillPlacements(MachineBasicBlock* MBB, 677378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> &blks, 678378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap &prevSpills) { 679378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool placedSpills = false; 680378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Intersect (CSRegs - AnticIn[P]) for P in Predecessors(MBB) 681378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet anticInPreds; 682378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> predecessors; 683378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 684378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PE = MBB->pred_end(); PI != PE; ++PI) { 685378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = *PI; 686378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (PRED != MBB) 687378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby predecessors.push_back(PRED); 688378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 689378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned i = 0, e = predecessors.size(); 690378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (i != e) { 691378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PRED = predecessors[i]; 692378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby anticInPreds = UsedCSRegs - AnticIn[PRED]; 693378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (++i; i != e; ++i) { 694378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby PRED = predecessors[i]; 695378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby anticInPreds &= (UsedCSRegs - AnticIn[PRED]); 696378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 697378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else { 698378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Handle uses in entry blocks (which have no predecessors). 699378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // This is necessary because the DFA formulation assumes the 700378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // entry and (multiple) exit nodes cannot have CSR uses, which 701378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // is not the case in the real world. 702378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby anticInPreds = UsedCSRegs; 703378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 704378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Compute spills required at MBB: 705378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds; 706378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 707378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRSave[MBB].empty()) { 708378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MBB == EntryBlock) { 709378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) 710378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB]; 711378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else { 712378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Reset all regs spilled in MBB that are also spilled in EntryBlock. 713378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) { 714378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock]; 715378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 716378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 717378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 718378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby placedSpills = (CSRSave[MBB] != prevSpills[MBB]); 719378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby prevSpills[MBB] = CSRSave[MBB]; 720378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Remember this block for adding restores to successor 721378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // blocks for multi-entry region. 722378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (placedSpills) 723378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby blks.push_back(MBB); 724378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 725378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations) 7260d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 727378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << stringifyCSRegSet(CSRSave[MBB]) << "\n"); 728378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 729378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return placedSpills; 730378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 731378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 732378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// calcRestorePlacements - determine which CSRs should be restored 733378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// in MBB using AvailOut sets of MBB's succcessors, keeping track 734378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// of changes to restored reg sets. Add MBB to the set of blocks 735378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// that need to be processed for propagating use info to cover 736378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// multi-entry/exit regions. 737378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 738378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbybool PEI::calcRestorePlacements(MachineBasicBlock* MBB, 739378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> &blks, 740378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap &prevRestores) { 741378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool placedRestores = false; 742378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Intersect (CSRegs - AvailOut[S]) for S in Successors(MBB) 743378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet availOutSucc; 744378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> successors; 745378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 746378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = MBB->succ_end(); SI != SE; ++SI) { 747378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 748378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SUCC != MBB) 749378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby successors.push_back(SUCC); 750378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 751378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned i = 0, e = successors.size(); 752378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (i != e) { 753378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = successors[i]; 754378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby availOutSucc = UsedCSRegs - AvailOut[SUCC]; 755378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (++i; i != e; ++i) { 756378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SUCC = successors[i]; 757378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby availOutSucc &= (UsedCSRegs - AvailOut[SUCC]); 758378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 759378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } else { 760378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) { 761378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Handle uses in return blocks (which have no successors). 762378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // This is necessary because the DFA formulation assumes the 763378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // entry and (multiple) exit nodes cannot have CSR uses, which 764378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // is not the case in the real world. 765378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby availOutSucc = UsedCSRegs; 766378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 767378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 768378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Compute restores required at MBB: 769378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc; 770378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 771378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Postprocess restore placements at MBB. 772378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Remove the CSRs that are restored in the return blocks. 773378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Lest this be confusing, note that: 774378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSRSave[EntryBlock] == CSRRestore[B] for all B in ReturnBlocks. 775378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (MBB->succ_size() && ! CSRRestore[MBB].empty()) { 776378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! CSRSave[EntryBlock].empty()) 777378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock]; 778378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 779378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby placedRestores = (CSRRestore[MBB] != prevRestores[MBB]); 780378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby prevRestores[MBB] = CSRRestore[MBB]; 781378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Remember this block for adding saves to predecessor 782378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // blocks for multi-entry region. 783378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (placedRestores) 784378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby blks.push_back(MBB); 785378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 786378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations) 7870d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = " 788378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << stringifyCSRegSet(CSRRestore[MBB]) << "\n"); 789378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 790378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return placedRestores; 791378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 792378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 793378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// placeSpillsAndRestores - place spills and restores of CSRs 794378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// used in MBBs in minimal regions that contain the uses. 795378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 796378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::placeSpillsAndRestores(MachineFunction &Fn) { 797378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap prevCSRSave; 798378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegBlockMap prevCSRRestore; 799378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks; 800378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool changed = true; 801378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned iterations = 0; 802378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 803378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Iterate computation of spill and restore placements in the MCFG until: 804378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // 1. CSR use info has been fully propagated around the MCFG, and 805378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // 2. computation of CSRSave[], CSRRestore[] reach fixed points. 806378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby while (changed) { 807378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed = false; 808378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ++iterations; 809378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 810378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapDebugging >= Iterations) 8110d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "iter " << iterations 812378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << " --------------------------------------------------\n"); 813378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 814378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Calculate CSR{Save,Restore} sets using Antic, Avail on the MCFG, 815378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // which determines the placements of spills and restores. 816378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Keep track of changes to spills, restores in each iteration to 817378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // minimize the total iterations. 818378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby bool SRChanged = false; 819378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end(); 820378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 821378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 822378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 823378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Place spills for CSRs in MBB. 824378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave); 825378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 826378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Place restores for CSRs in MBB. 827378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore); 828378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 829378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 830378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Add uses of CSRs used inside loops where needed. 831378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed |= addUsesForTopLevelLoops(cvBlocks); 832378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 833378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Add uses for CSRs spilled or restored at branch, join points. 834378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (changed || SRChanged) { 835378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby while (! cvBlocks.empty()) { 836378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = cvBlocks.pop_back_val(); 837378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby changed |= addUsesForMEMERegion(MBB, ncvBlocks); 838378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 839378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! ncvBlocks.empty()) { 840378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby cvBlocks = ncvBlocks; 841378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ncvBlocks.clear(); 842378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 843378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 844378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 845378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (changed) { 846378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby calculateAnticAvail(Fn); 847378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRSave.clear(); 848378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRRestore.clear(); 849378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 850378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 851378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 852378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Check for effectiveness: 853378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // SR0 = {r | r in CSRSave[EntryBlock], CSRRestore[RB], RB in ReturnBlocks} 854378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // numSRReduced = |(UsedCSRegs - SR0)|, approx. SR0 by CSRSave[EntryBlock] 855378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Gives a measure of how many CSR spills have been moved from EntryBlock 856378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // to minimal regions enclosing their uses. 857378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]); 858378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count(); 859378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby numSRReduced += numSRReducedThisFunc; 860378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby DEBUG(if (ShrinkWrapDebugging >= BasicInfo) { 8610d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "-----------------------------------------------------------\n"; 8620d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "total iterations = " << iterations << " ( " 86396601ca332ab388754ca4673be8973396fea2dddCraig Topper << Fn.getName() 864378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << " " << numSRReducedThisFunc 865378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << " " << Fn.size() 866378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << " )\n"; 8670d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "-----------------------------------------------------------\n"; 868378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby dumpSRSets(); 8690d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "-----------------------------------------------------------\n"; 870378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (numSRReducedThisFunc) 871378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby verifySpillRestorePlacement(); 872378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby }); 873378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 874378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 875378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Debugging methods. 876378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#ifndef NDEBUG 877378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// findFastExitPath - debugging method used to detect functions 878378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// with at least one path from the entry block to a return block 879378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// directly or which has a very small number of edges. 880378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 881378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::findFastExitPath() { 882378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (! EntryBlock) 883378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return; 884378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Fina a path from EntryBlock to any return block that does not branch: 885378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Entry 886378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // | ... 887378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // v | 888378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // B1<-----+ 889378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // | 890378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // v 891378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Return 892378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(), 893378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby SE = EntryBlock->succ_end(); SI != SE; ++SI) { 894378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SUCC = *SI; 895378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 896378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Assume positive, disprove existence of fast path. 897378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby HasFastExitPath = true; 898378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 899378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Check the immediate successors. 900378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (isReturnBlock(SUCC)) { 901378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapDebugging >= BasicInfo) 9020d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock) 903378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "->" << getBasicBlockName(SUCC) << "\n"; 904378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 905378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 906378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Traverse df from SUCC, look for a branch block. 907378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::string exitPath = getBasicBlockName(SUCC); 908378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC), 909378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby BE = df_end(SUCC); BI != BE; ++BI) { 910378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SBB = *BI; 911378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Reject paths with branch nodes. 912378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SBB->succ_size() > 1) { 913378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby HasFastExitPath = false; 914378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 915378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 916378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby exitPath += "->" + getBasicBlockName(SBB); 917378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 918378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (HasFastExitPath) { 919378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (ShrinkWrapDebugging >= BasicInfo) 9200d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock) 921378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby << "->" << exitPath << "\n"; 922378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 923378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 924378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 925378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 926378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 927378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// verifySpillRestorePlacement - check the current spill/restore 928378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// sets for safety. Attempt to find spills without restores or 929378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// restores without spills. 930378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// Spills: walk df from each MBB in spill set ensuring that 931378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// all CSRs spilled at MMBB are restored on all paths 932378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// from MBB to all exit blocks. 933378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// Restores: walk idf from each MBB in restore set ensuring that 934378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// all CSRs restored at MBB are spilled on all paths 935378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// reaching MBB. 936378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby/// 937378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::verifySpillRestorePlacement() { 938378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned numReturnBlocks = 0; 939378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 940378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 941378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 942378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (isReturnBlock(MBB) || MBB->succ_size() == 0) 943378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby ++numReturnBlocks; 944378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 945378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (CSRegBlockMap::iterator BI = CSRSave.begin(), 946378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby BE = CSRSave.end(); BI != BE; ++BI) { 947378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = BI->first; 948378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet spilled = BI->second; 949378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet restored; 950378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 951378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (spilled.empty()) 952378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 953378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 9540d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 9559c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(spilled) 9569c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " RESTORE[" << getBasicBlockName(MBB) << "] = " 9579c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRRestore[MBB]) << "\n"); 958378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 959378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRRestore[MBB].intersects(spilled)) { 960378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby restored |= (CSRRestore[MBB] & spilled); 961378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 962378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 963378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Walk depth first from MBB to find restores of all CSRs spilled at MBB: 964378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // we must find restores for all spills w/no intervening spills on all 965378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // paths from MBB to all return blocks. 966378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB), 967378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby BE = df_end(MBB); BI != BE; ++BI) { 968378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* SBB = *BI; 969378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (SBB == MBB) 970378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 971378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Stop when we encounter spills of any CSRs spilled at MBB that 972378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // have not yet been seen to be restored. 973378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRSave[SBB].intersects(spilled) && 974378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby !restored.contains(CSRSave[SBB] & spilled)) 975378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 976378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Collect the CSRs spilled at MBB that are restored 977378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // at this DF successor of MBB. 978378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRRestore[SBB].intersects(spilled)) 979378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby restored |= (CSRRestore[SBB] & spilled); 980378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // If we are at a retun block, check that the restores 981378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // we have seen so far exhaust the spills at MBB, then 982378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // reset the restores. 983378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (isReturnBlock(SBB) || SBB->succ_size() == 0) { 984378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (restored != spilled) { 985378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet notRestored = (spilled - restored); 98696601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << MF->getName() << ": " 9879c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(notRestored) 9889c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " spilled at " << getBasicBlockName(MBB) 9899c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " are never restored on path to return " 9909c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << getBasicBlockName(SBB) << "\n"); 991378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 992378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby restored.clear(); 993378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 994378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 995378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 996378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 997378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Check restore placements. 998378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (CSRegBlockMap::iterator BI = CSRRestore.begin(), 999378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby BE = CSRRestore.end(); BI != BE; ++BI) { 1000378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = BI->first; 1001378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet restored = BI->second; 1002378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet spilled; 1003378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1004378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (restored.empty()) 1005378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 1006378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 10070d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 10089c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRSave[MBB]) 10099c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " RESTORE[" << getBasicBlockName(MBB) << "] = " 10109c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(restored) << "\n"); 1011378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1012378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRSave[MBB].intersects(restored)) { 1013378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby spilled |= (CSRSave[MBB] & restored); 1014378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1015378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Walk inverse depth first from MBB to find spills of all 1016378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // CSRs restored at MBB: 1017378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB), 1018378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby BE = idf_end(MBB); BI != BE; ++BI) { 1019378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* PBB = *BI; 1020378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (PBB == MBB) 1021378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby continue; 1022378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Stop when we encounter restores of any CSRs restored at MBB that 1023378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // have not yet been seen to be spilled. 1024378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRRestore[PBB].intersects(restored) && 1025378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby !spilled.contains(CSRRestore[PBB] & restored)) 1026378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby break; 1027378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // Collect the CSRs restored at MBB that are spilled 1028378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby // at this DF predecessor of MBB. 1029378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSRSave[PBB].intersects(restored)) 1030378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby spilled |= (CSRSave[PBB] & restored); 1031378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1032378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (spilled != restored) { 1033378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet notSpilled = (restored - spilled); 103496601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << MF->getName() << ": " 10359c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(notSpilled) 10369c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " restored at " << getBasicBlockName(MBB) 10379c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << " are never spilled\n"); 1038378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1039378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1040378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1041378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1042378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby// Debugging print methods. 1043378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbystd::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) { 1044ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar if (!MBB) 1045ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar return ""; 1046ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar 1047ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar if (MBB->getBasicBlock()) 1048a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer return MBB->getBasicBlock()->getName().str(); 1049ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar 1050378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::ostringstream name; 1051ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar name << "_MBB_" << MBB->getNumber(); 1052378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return name.str(); 1053378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1054378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1055378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbystd::string PEI::stringifyCSRegSet(const CSRegSet& s) { 1056378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); 1057378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby const std::vector<CalleeSavedInfo> CSI = 1058378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MF->getFrameInfo()->getCalleeSavedInfo(); 1059378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1060378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby std::ostringstream srep; 1061378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (CSI.size() == 0) { 1062378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << "[]"; 1063378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return srep.str(); 1064378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1065378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << "["; 1066378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby CSRegSet::iterator I = s.begin(), E = s.end(); 1067378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby if (I != E) { 1068378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby unsigned reg = CSI[*I].getReg(); 1069378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << TRI->getName(reg); 1070378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (++I; I != E; ++I) { 1071378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby reg = CSI[*I].getReg(); 1072378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << ","; 1073378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << TRI->getName(reg); 1074378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1075378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1076378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby srep << "]"; 1077378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby return srep.str(); 1078378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1079378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1080378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpSet(const CSRegSet& s) { 10810d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene DEBUG(dbgs() << stringifyCSRegSet(s) << "\n"); 1082378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1083378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1084378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpUsed(MachineBasicBlock* MBB) { 10859c52affd374e20b212d3266050f13d87ba80e36dBill Wendling DEBUG({ 10869c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (MBB) 10870d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = " 10889c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRUsed[MBB]) << "\n"; 10899c52affd374e20b212d3266050f13d87ba80e36dBill Wendling }); 1090378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1091378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1092378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpAllUsed() { 1093378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1094378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 1095378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 1096378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby dumpUsed(MBB); 1097378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1098378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1099378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1100378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpSets(MachineBasicBlock* MBB) { 11019c52affd374e20b212d3266050f13d87ba80e36dBill Wendling DEBUG({ 11029c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (MBB) 11030d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << getBasicBlockName(MBB) << " | " 11049c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRUsed[MBB]) << " | " 11059c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AnticIn[MBB]) << " | " 11069c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AnticOut[MBB]) << " | " 11079c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AvailIn[MBB]) << " | " 11089c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AvailOut[MBB]) << "\n"; 11099c52affd374e20b212d3266050f13d87ba80e36dBill Wendling }); 1110378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1111378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1112378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpSets1(MachineBasicBlock* MBB) { 11139c52affd374e20b212d3266050f13d87ba80e36dBill Wendling DEBUG({ 11149c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (MBB) 11150d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << getBasicBlockName(MBB) << " | " 11169c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRUsed[MBB]) << " | " 11179c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AnticIn[MBB]) << " | " 11189c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AnticOut[MBB]) << " | " 11199c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AvailIn[MBB]) << " | " 11209c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(AvailOut[MBB]) << " | " 11219c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRSave[MBB]) << " | " 11229c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRRestore[MBB]) << "\n"; 11239c52affd374e20b212d3266050f13d87ba80e36dBill Wendling }); 1124378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1125378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1126378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpAllSets() { 1127378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1128378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MBBI != MBBE; ++MBBI) { 1129378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby MachineBasicBlock* MBB = MBBI; 1130378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby dumpSets1(MBB); 1131378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby } 1132378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1133378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby 1134378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosbyvoid PEI::dumpSRSets() { 11359c52affd374e20b212d3266050f13d87ba80e36dBill Wendling DEBUG({ 11369c52affd374e20b212d3266050f13d87ba80e36dBill Wendling for (MachineFunction::iterator MBB = MF->begin(), E = MF->end(); 11379c52affd374e20b212d3266050f13d87ba80e36dBill Wendling MBB != E; ++MBB) { 11389c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (!CSRSave[MBB].empty()) { 11390d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = " 11409c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRSave[MBB]); 11419c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (CSRRestore[MBB].empty()) 11420d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << '\n'; 11439c52affd374e20b212d3266050f13d87ba80e36dBill Wendling } 11449c52affd374e20b212d3266050f13d87ba80e36dBill Wendling 11459c52affd374e20b212d3266050f13d87ba80e36dBill Wendling if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty()) 11460d5c06e0b66d31f1488b4f0791d9a135d22cb422David Greene dbgs() << " " 11479c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << "RESTORE[" << getBasicBlockName(MBB) << "] = " 11489c52affd374e20b212d3266050f13d87ba80e36dBill Wendling << stringifyCSRegSet(CSRRestore[MBB]) << "\n"; 11499c52affd374e20b212d3266050f13d87ba80e36dBill Wendling } 11509c52affd374e20b212d3266050f13d87ba80e36dBill Wendling }); 1151378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby} 1152378553cb079aba2b8dee5d52b5166316d4132d5aJohn Mosby#endif 1153