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