ShrinkWrap.cpp revision 283625
1145132Sanholt//===-- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ---===// 2145132Sanholt// 3152909Sanholt// The LLVM Compiler Infrastructure 4145132Sanholt// 5145132Sanholt// This file is distributed under the University of Illinois Open Source 6145132Sanholt// License. See LICENSE.TXT for details. 7152909Sanholt// 8152909Sanholt//===----------------------------------------------------------------------===// 9152909Sanholt// 10152909Sanholt// This pass looks for safe point where the prologue and epilogue can be 11152909Sanholt// inserted. 12152909Sanholt// The safe point for the prologue (resp. epilogue) is called Save 13152909Sanholt// (resp. Restore). 14152909Sanholt// A point is safe for prologue (resp. epilogue) if and only if 15152909Sanholt// it 1) dominates (resp. post-dominates) all the frame related operations and 16152909Sanholt// between 2) two executions of the Save (resp. Restore) point there is an 17152909Sanholt// execution of the Restore (resp. Save) point. 18152909Sanholt// 19152909Sanholt// For instance, the following points are safe: 20152909Sanholt// for (int i = 0; i < 10; ++i) { 21152909Sanholt// Save 22152909Sanholt// ... 23152909Sanholt// Restore 24152909Sanholt// } 25152909Sanholt// Indeed, the execution looks like Save -> Restore -> Save -> Restore ... 26152909Sanholt// And the following points are not: 27152909Sanholt// for (int i = 0; i < 10; ++i) { 28145132Sanholt// Save 29152909Sanholt// ... 30152909Sanholt// } 31145132Sanholt// for (int i = 0; i < 10; ++i) { 32152909Sanholt// ... 33152909Sanholt// Restore 34152909Sanholt// } 35152909Sanholt// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore. 36152909Sanholt// 37145132Sanholt// This pass also ensures that the safe points are 3) cheaper than the regular 38145132Sanholt// entry and exits blocks. 39145132Sanholt// 40145132Sanholt// Property #1 is ensured via the use of MachineDominatorTree and 41145132Sanholt// MachinePostDominatorTree. 42145132Sanholt// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both 43145132Sanholt// points must be in the same loop. 44145132Sanholt// Property #3 is ensured via the MachineBlockFrequencyInfo. 45145132Sanholt// 46145132Sanholt// If this pass found points matching all this properties, then 47145132Sanholt// MachineFrameInfo is updated this that information. 48145132Sanholt//===----------------------------------------------------------------------===// 49182080Srnoland#include "llvm/ADT/Statistic.h" 50145132Sanholt// To check for profitability. 51145132Sanholt#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 52145132Sanholt// For property #1 for Save. 53182080Srnoland#include "llvm/CodeGen/MachineDominators.h" 54145132Sanholt#include "llvm/CodeGen/MachineFunctionPass.h" 55145132Sanholt// To record the result of the analysis. 56145132Sanholt#include "llvm/CodeGen/MachineFrameInfo.h" 57145132Sanholt// For property #2. 58145132Sanholt#include "llvm/CodeGen/MachineLoopInfo.h" 59145132Sanholt// For property #1 for Restore. 60145132Sanholt#include "llvm/CodeGen/MachinePostDominators.h" 61145132Sanholt#include "llvm/CodeGen/Passes.h" 62145132Sanholt// To know about callee-saved. 63145132Sanholt#include "llvm/CodeGen/RegisterClassInfo.h" 64145132Sanholt#include "llvm/Support/Debug.h" 65145132Sanholt// To query the target about frame lowering. 66145132Sanholt#include "llvm/Target/TargetFrameLowering.h" 67145132Sanholt// To know about frame setup operation. 68145132Sanholt#include "llvm/Target/TargetInstrInfo.h" 69145132Sanholt// To access TargetInstrInfo. 70145132Sanholt#include "llvm/Target/TargetSubtargetInfo.h" 71145132Sanholt 72145132Sanholt#define DEBUG_TYPE "shrink-wrap" 73145132Sanholt 74145132Sanholtusing namespace llvm; 75145132Sanholt 76145132SanholtSTATISTIC(NumFunc, "Number of functions"); 77145132SanholtSTATISTIC(NumCandidates, "Number of shrink-wrapping candidates"); 78145132SanholtSTATISTIC(NumCandidatesDropped, 79145132Sanholt "Number of shrink-wrapping candidates dropped because of frequency"); 80145132Sanholt 81145132Sanholtnamespace { 82145132Sanholt/// \brief Class to determine where the safe point to insert the 83145132Sanholt/// prologue and epilogue are. 84145132Sanholt/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the 85145132Sanholt/// shrink-wrapping term for prologue/epilogue placement, this pass 86145132Sanholt/// does not rely on expensive data-flow analysis. Instead we use the 87145132Sanholt/// dominance properties and loop information to decide which point 88145132Sanholt/// are safe for such insertion. 89145132Sanholtclass ShrinkWrap : public MachineFunctionPass { 90145132Sanholt /// Hold callee-saved information. 91145132Sanholt RegisterClassInfo RCI; 92145132Sanholt MachineDominatorTree *MDT; 93145132Sanholt MachinePostDominatorTree *MPDT; 94145132Sanholt /// Current safe point found for the prologue. 95182080Srnoland /// The prologue will be inserted before the first instruction 96145132Sanholt /// in this basic block. 97145132Sanholt MachineBasicBlock *Save; 98145132Sanholt /// Current safe point found for the epilogue. 99145132Sanholt /// The epilogue will be inserted before the first terminator instruction 100145132Sanholt /// in this basic block. 101145132Sanholt MachineBasicBlock *Restore; 102145132Sanholt /// Hold the information of the basic block frequency. 103145132Sanholt /// Use to check the profitability of the new points. 104145132Sanholt MachineBlockFrequencyInfo *MBFI; 105182080Srnoland /// Hold the loop information. Used to determine if Save and Restore 106145132Sanholt /// are in the same loop. 107145132Sanholt MachineLoopInfo *MLI; 108145132Sanholt /// Frequency of the Entry block. 109145132Sanholt uint64_t EntryFreq; 110145132Sanholt /// Current opcode for frame setup. 111145132Sanholt unsigned FrameSetupOpcode; 112145132Sanholt /// Current opcode for frame destroy. 113145132Sanholt unsigned FrameDestroyOpcode; 114145132Sanholt /// Entry block. 115145132Sanholt const MachineBasicBlock *Entry; 116145132Sanholt 117145132Sanholt /// \brief Check if \p MI uses or defines a callee-saved register or 118145132Sanholt /// a frame index. If this is the case, this means \p MI must happen 119145132Sanholt /// after Save and before Restore. 120145132Sanholt bool useOrDefCSROrFI(const MachineInstr &MI) const; 121145132Sanholt 122182080Srnoland /// \brief Update the Save and Restore points such that \p MBB is in 123145132Sanholt /// the region that is dominated by Save and post-dominated by Restore 124145132Sanholt /// and Save and Restore still match the safe point definition. 125145132Sanholt /// Such point may not exist and Save and/or Restore may be null after 126145132Sanholt /// this call. 127145132Sanholt void updateSaveRestorePoints(MachineBasicBlock &MBB); 128145132Sanholt 129145132Sanholt /// \brief Initialize the pass for \p MF. 130145132Sanholt void init(MachineFunction &MF) { 131145132Sanholt RCI.runOnMachineFunction(MF); 132182080Srnoland MDT = &getAnalysis<MachineDominatorTree>(); 133145132Sanholt MPDT = &getAnalysis<MachinePostDominatorTree>(); 134145132Sanholt Save = nullptr; 135145132Sanholt Restore = nullptr; 136145132Sanholt MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 137182080Srnoland MLI = &getAnalysis<MachineLoopInfo>(); 138145132Sanholt EntryFreq = MBFI->getEntryFreq(); 139145132Sanholt const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); 140145132Sanholt FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 141145132Sanholt FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 142145132Sanholt Entry = &MF.front(); 143145132Sanholt 144182080Srnoland ++NumFunc; 145182080Srnoland } 146145132Sanholt 147145132Sanholt /// Check whether or not Save and Restore points are still interesting for 148145132Sanholt /// shrink-wrapping. 149145132Sanholt bool ArePointsInteresting() const { return Save != Entry && Save && Restore; } 150145132Sanholt 151145132Sanholtpublic: 152145132Sanholt static char ID; 153145132Sanholt 154145132Sanholt ShrinkWrap() : MachineFunctionPass(ID) { 155145132Sanholt initializeShrinkWrapPass(*PassRegistry::getPassRegistry()); 156145132Sanholt } 157145132Sanholt 158145132Sanholt void getAnalysisUsage(AnalysisUsage &AU) const override { 159145132Sanholt AU.setPreservesAll(); 160145132Sanholt AU.addRequired<MachineBlockFrequencyInfo>(); 161145132Sanholt AU.addRequired<MachineDominatorTree>(); 162145132Sanholt AU.addRequired<MachinePostDominatorTree>(); 163145132Sanholt AU.addRequired<MachineLoopInfo>(); 164182080Srnoland MachineFunctionPass::getAnalysisUsage(AU); 165145132Sanholt } 166182080Srnoland 167145132Sanholt const char *getPassName() const override { 168145132Sanholt return "Shrink Wrapping analysis"; 169182080Srnoland } 170145132Sanholt 171145132Sanholt /// \brief Perform the shrink-wrapping analysis and update 172145132Sanholt /// the MachineFrameInfo attached to \p MF with the results. 173145132Sanholt bool runOnMachineFunction(MachineFunction &MF) override; 174145132Sanholt}; 175145132Sanholt} // End anonymous namespace. 176145132Sanholt 177182080Srnolandchar ShrinkWrap::ID = 0; 178145132Sanholtchar &llvm::ShrinkWrapID = ShrinkWrap::ID; 179145132Sanholt 180145132SanholtINITIALIZE_PASS_BEGIN(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false, 181145132Sanholt false) 182145132SanholtINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 183145132SanholtINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 184145132SanholtINITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 185145132SanholtINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 186145132SanholtINITIALIZE_PASS_END(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false, false) 187145132Sanholt 188145132Sanholtbool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI) const { 189145132Sanholt if (MI.getOpcode() == FrameSetupOpcode || 190145132Sanholt MI.getOpcode() == FrameDestroyOpcode) { 191145132Sanholt DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); 192145132Sanholt return true; 193145132Sanholt } 194145132Sanholt for (const MachineOperand &MO : MI.operands()) { 195145132Sanholt bool UseCSR = false; 196145132Sanholt if (MO.isReg()) { 197145132Sanholt unsigned PhysReg = MO.getReg(); 198145132Sanholt if (!PhysReg) 199145132Sanholt continue; 200145132Sanholt assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 201145132Sanholt "Unallocated register?!"); 202145132Sanholt UseCSR = RCI.getLastCalleeSavedAlias(PhysReg); 203182080Srnoland } 204145132Sanholt // TODO: Handle regmask more accurately. 205145132Sanholt // For now, be conservative about them. 206145132Sanholt if (UseCSR || MO.isFI() || MO.isRegMask()) { 207182080Srnoland DEBUG(dbgs() << "Use or define CSR(" << UseCSR << ") or FI(" << MO.isFI() 208145132Sanholt << "): " << MI << '\n'); 209145132Sanholt return true; 210145132Sanholt } 211145132Sanholt } 212145132Sanholt return false; 213145132Sanholt} 214182080Srnoland 215182080Srnoland/// \brief Helper function to find the immediate (post) dominator. 216145132Sanholttemplate <typename ListOfBBs, typename DominanceAnalysis> 217145132SanholtMachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, 218145132Sanholt DominanceAnalysis &Dom) { 219145132Sanholt MachineBasicBlock *IDom = &Block; 220145132Sanholt for (MachineBasicBlock *BB : BBs) { 221145132Sanholt IDom = Dom.findNearestCommonDominator(IDom, BB); 222145132Sanholt if (!IDom) 223182080Srnoland break; 224182080Srnoland } 225145132Sanholt return IDom; 226145132Sanholt} 227145132Sanholt 228145132Sanholtvoid ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB) { 229182080Srnoland // Get rid of the easy cases first. 230145132Sanholt if (!Save) 231145132Sanholt Save = &MBB; 232145132Sanholt else 233182080Srnoland Save = MDT->findNearestCommonDominator(Save, &MBB); 234145132Sanholt 235145132Sanholt if (!Save) { 236145132Sanholt DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); 237145132Sanholt return; 238145132Sanholt } 239145132Sanholt 240145132Sanholt if (!Restore) 241145132Sanholt Restore = &MBB; 242145132Sanholt else 243145132Sanholt Restore = MPDT->findNearestCommonDominator(Restore, &MBB); 244145132Sanholt 245145132Sanholt // Make sure we would be able to insert the restore code before the 246145132Sanholt // terminator. 247145132Sanholt if (Restore == &MBB) { 248145132Sanholt for (const MachineInstr &Terminator : MBB.terminators()) { 249145132Sanholt if (!useOrDefCSROrFI(Terminator)) 250145132Sanholt continue; 251145132Sanholt // One of the terminator needs to happen before the restore point. 252145132Sanholt if (MBB.succ_empty()) { 253145132Sanholt Restore = nullptr; 254145132Sanholt break; 255145132Sanholt } 256145132Sanholt // Look for a restore point that post-dominates all the successors. 257145132Sanholt // The immediate post-dominator is what we are looking for. 258145132Sanholt Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 259145132Sanholt break; 260145132Sanholt } 261145132Sanholt } 262145132Sanholt 263145132Sanholt if (!Restore) { 264145132Sanholt DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n"); 265145132Sanholt return; 266145132Sanholt } 267145132Sanholt 268145132Sanholt // Make sure Save and Restore are suitable for shrink-wrapping: 269145132Sanholt // 1. all path from Save needs to lead to Restore before exiting. 270145132Sanholt // 2. all path to Restore needs to go through Save from Entry. 271145132Sanholt // We achieve that by making sure that: 272145132Sanholt // A. Save dominates Restore. 273145132Sanholt // B. Restore post-dominates Save. 274182080Srnoland // C. Save and Restore are in the same loop. 275182080Srnoland bool SaveDominatesRestore = false; 276145132Sanholt bool RestorePostDominatesSave = false; 277145132Sanholt while (Save && Restore && 278182080Srnoland (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) || 279145132Sanholt !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) || 280145132Sanholt MLI->getLoopFor(Save) != MLI->getLoopFor(Restore))) { 281145132Sanholt // Fix (A). 282182080Srnoland if (!SaveDominatesRestore) { 283182080Srnoland Save = MDT->findNearestCommonDominator(Save, Restore); 284145132Sanholt continue; 285145132Sanholt } 286182080Srnoland // Fix (B). 287145132Sanholt if (!RestorePostDominatesSave) 288182080Srnoland Restore = MPDT->findNearestCommonDominator(Restore, Save); 289145132Sanholt 290145132Sanholt // Fix (C). 291145132Sanholt if (Save && Restore && Save != Restore && 292145132Sanholt MLI->getLoopFor(Save) != MLI->getLoopFor(Restore)) { 293182080Srnoland if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) 294182080Srnoland // Push Save outside of this loop. 295145132Sanholt Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 296182080Srnoland else 297145132Sanholt // Push Restore outside of this loop. 298145132Sanholt Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 299182080Srnoland } 300145132Sanholt } 301145132Sanholt} 302145132Sanholt 303182080Srnolandbool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { 304182080Srnoland if (MF.empty()) 305145132Sanholt return false; 306182080Srnoland DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 307145132Sanholt 308145132Sanholt init(MF); 309145132Sanholt 310145132Sanholt for (MachineBasicBlock &MBB : MF) { 311145132Sanholt DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName() 312182080Srnoland << '\n'); 313182080Srnoland 314145132Sanholt for (const MachineInstr &MI : MBB) { 315145132Sanholt if (!useOrDefCSROrFI(MI)) 316182080Srnoland continue; 317145132Sanholt // Save (resp. restore) point must dominate (resp. post dominate) 318145132Sanholt // MI. Look for the proper basic block for those. 319145132Sanholt updateSaveRestorePoints(MBB); 320182080Srnoland // If we are at a point where we cannot improve the placement of 321182080Srnoland // save/restore instructions, just give up. 322145132Sanholt if (!ArePointsInteresting()) { 323145132Sanholt DEBUG(dbgs() << "No Shrink wrap candidate found\n"); 324182080Srnoland return false; 325145132Sanholt } 326182080Srnoland // No need to look for other instructions, this basic block 327145132Sanholt // will already be part of the handled region. 328182080Srnoland break; 329145132Sanholt } 330182080Srnoland } 331145132Sanholt if (!ArePointsInteresting()) { 332182080Srnoland // If the points are not interesting at this point, then they must be null 333182080Srnoland // because it means we did not encounter any frame/CSR related code. 334145132Sanholt // Otherwise, we would have returned from the previous loop. 335145132Sanholt assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); 336145132Sanholt DEBUG(dbgs() << "Nothing to shrink-wrap\n"); 337145132Sanholt return false; 338145132Sanholt } 339145132Sanholt 340182080Srnoland DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq 341182080Srnoland << '\n'); 342145132Sanholt 343145132Sanholt const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 344182080Srnoland do { 345145132Sanholt DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " 346145132Sanholt << Save->getNumber() << ' ' << Save->getName() << ' ' 347145132Sanholt << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: " 348182080Srnoland << Restore->getNumber() << ' ' << Restore->getName() << ' ' 349182080Srnoland << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); 350145132Sanholt 351145132Sanholt bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; 352182080Srnoland if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && 353145132Sanholt EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) && 354182080Srnoland ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) && 355145132Sanholt TFI->canUseAsEpilogue(*Restore))) 356145132Sanholt break; 357145132Sanholt DEBUG(dbgs() << "New points are too expensive or invalid for the target\n"); 358182080Srnoland MachineBasicBlock *NewBB; 359145132Sanholt if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) { 360145132Sanholt Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 361182080Srnoland if (!Save) 362145132Sanholt break; 363157617Sanholt NewBB = Save; 364182080Srnoland } else { 365182080Srnoland // Restore is expensive. 366157617Sanholt Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 367157617Sanholt if (!Restore) 368182080Srnoland break; 369157617Sanholt NewBB = Restore; 370157617Sanholt } 371157617Sanholt updateSaveRestorePoints(*NewBB); 372182080Srnoland } while (Save && Restore); 373182080Srnoland 374157617Sanholt if (!ArePointsInteresting()) { 375157617Sanholt ++NumCandidatesDropped; 376182080Srnoland return false; 377157617Sanholt } 378157617Sanholt 379182080Srnoland DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber() 380157617Sanholt << ' ' << Save->getName() << "\nRestore: " 381182080Srnoland << Restore->getNumber() << ' ' << Restore->getName() << '\n'); 382157617Sanholt 383157617Sanholt MachineFrameInfo *MFI = MF.getFrameInfo(); 384182080Srnoland MFI->setSavePoint(Save); 385157617Sanholt MFI->setRestorePoint(Restore); 386157617Sanholt ++NumCandidates; 387157617Sanholt return false; 388157617Sanholt} 389157617Sanholt