ShrinkWrap.cpp revision 321369
1//===-- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ---===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass looks for safe point where the prologue and epilogue can be 11// inserted. 12// The safe point for the prologue (resp. epilogue) is called Save 13// (resp. Restore). 14// A point is safe for prologue (resp. epilogue) if and only if 15// it 1) dominates (resp. post-dominates) all the frame related operations and 16// between 2) two executions of the Save (resp. Restore) point there is an 17// execution of the Restore (resp. Save) point. 18// 19// For instance, the following points are safe: 20// for (int i = 0; i < 10; ++i) { 21// Save 22// ... 23// Restore 24// } 25// Indeed, the execution looks like Save -> Restore -> Save -> Restore ... 26// And the following points are not: 27// for (int i = 0; i < 10; ++i) { 28// Save 29// ... 30// } 31// for (int i = 0; i < 10; ++i) { 32// ... 33// Restore 34// } 35// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore. 36// 37// This pass also ensures that the safe points are 3) cheaper than the regular 38// entry and exits blocks. 39// 40// Property #1 is ensured via the use of MachineDominatorTree and 41// MachinePostDominatorTree. 42// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both 43// points must be in the same loop. 44// Property #3 is ensured via the MachineBlockFrequencyInfo. 45// 46// If this pass found points matching all these properties, then 47// MachineFrameInfo is updated with this information. 48//===----------------------------------------------------------------------===// 49#include "llvm/ADT/BitVector.h" 50#include "llvm/ADT/PostOrderIterator.h" 51#include "llvm/ADT/SetVector.h" 52#include "llvm/ADT/Statistic.h" 53// To check for profitability. 54#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 55// For property #1 for Save. 56#include "llvm/CodeGen/MachineDominators.h" 57#include "llvm/CodeGen/MachineFunctionPass.h" 58// To record the result of the analysis. 59#include "llvm/CodeGen/MachineFrameInfo.h" 60// For property #2. 61#include "llvm/CodeGen/MachineLoopInfo.h" 62// For property #1 for Restore. 63#include "llvm/CodeGen/MachinePostDominators.h" 64#include "llvm/CodeGen/Passes.h" 65// To know about callee-saved. 66#include "llvm/CodeGen/RegisterClassInfo.h" 67#include "llvm/CodeGen/RegisterScavenging.h" 68#include "llvm/MC/MCAsmInfo.h" 69#include "llvm/Support/Debug.h" 70// To query the target about frame lowering. 71#include "llvm/Target/TargetFrameLowering.h" 72// To know about frame setup operation. 73#include "llvm/Target/TargetInstrInfo.h" 74#include "llvm/Target/TargetMachine.h" 75// To access TargetInstrInfo. 76#include "llvm/Target/TargetSubtargetInfo.h" 77 78#define DEBUG_TYPE "shrink-wrap" 79 80using namespace llvm; 81 82STATISTIC(NumFunc, "Number of functions"); 83STATISTIC(NumCandidates, "Number of shrink-wrapping candidates"); 84STATISTIC(NumCandidatesDropped, 85 "Number of shrink-wrapping candidates dropped because of frequency"); 86 87static cl::opt<cl::boolOrDefault> 88 EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, 89 cl::desc("enable the shrink-wrapping pass")); 90 91namespace { 92/// \brief Class to determine where the safe point to insert the 93/// prologue and epilogue are. 94/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the 95/// shrink-wrapping term for prologue/epilogue placement, this pass 96/// does not rely on expensive data-flow analysis. Instead we use the 97/// dominance properties and loop information to decide which point 98/// are safe for such insertion. 99class ShrinkWrap : public MachineFunctionPass { 100 /// Hold callee-saved information. 101 RegisterClassInfo RCI; 102 MachineDominatorTree *MDT; 103 MachinePostDominatorTree *MPDT; 104 /// Current safe point found for the prologue. 105 /// The prologue will be inserted before the first instruction 106 /// in this basic block. 107 MachineBasicBlock *Save; 108 /// Current safe point found for the epilogue. 109 /// The epilogue will be inserted before the first terminator instruction 110 /// in this basic block. 111 MachineBasicBlock *Restore; 112 /// Hold the information of the basic block frequency. 113 /// Use to check the profitability of the new points. 114 MachineBlockFrequencyInfo *MBFI; 115 /// Hold the loop information. Used to determine if Save and Restore 116 /// are in the same loop. 117 MachineLoopInfo *MLI; 118 /// Frequency of the Entry block. 119 uint64_t EntryFreq; 120 /// Current opcode for frame setup. 121 unsigned FrameSetupOpcode; 122 /// Current opcode for frame destroy. 123 unsigned FrameDestroyOpcode; 124 /// Entry block. 125 const MachineBasicBlock *Entry; 126 typedef SmallSetVector<unsigned, 16> SetOfRegs; 127 /// Registers that need to be saved for the current function. 128 mutable SetOfRegs CurrentCSRs; 129 /// Current MachineFunction. 130 MachineFunction *MachineFunc; 131 132 /// \brief Check if \p MI uses or defines a callee-saved register or 133 /// a frame index. If this is the case, this means \p MI must happen 134 /// after Save and before Restore. 135 bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const; 136 137 const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const { 138 if (CurrentCSRs.empty()) { 139 BitVector SavedRegs; 140 const TargetFrameLowering *TFI = 141 MachineFunc->getSubtarget().getFrameLowering(); 142 143 TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS); 144 145 for (int Reg = SavedRegs.find_first(); Reg != -1; 146 Reg = SavedRegs.find_next(Reg)) 147 CurrentCSRs.insert((unsigned)Reg); 148 } 149 return CurrentCSRs; 150 } 151 152 /// \brief Update the Save and Restore points such that \p MBB is in 153 /// the region that is dominated by Save and post-dominated by Restore 154 /// and Save and Restore still match the safe point definition. 155 /// Such point may not exist and Save and/or Restore may be null after 156 /// this call. 157 void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS); 158 159 /// \brief Initialize the pass for \p MF. 160 void init(MachineFunction &MF) { 161 RCI.runOnMachineFunction(MF); 162 MDT = &getAnalysis<MachineDominatorTree>(); 163 MPDT = &getAnalysis<MachinePostDominatorTree>(); 164 Save = nullptr; 165 Restore = nullptr; 166 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 167 MLI = &getAnalysis<MachineLoopInfo>(); 168 EntryFreq = MBFI->getEntryFreq(); 169 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); 170 FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 171 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 172 Entry = &MF.front(); 173 CurrentCSRs.clear(); 174 MachineFunc = &MF; 175 176 ++NumFunc; 177 } 178 179 /// Check whether or not Save and Restore points are still interesting for 180 /// shrink-wrapping. 181 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; } 182 183 /// \brief Check if shrink wrapping is enabled for this target and function. 184 static bool isShrinkWrapEnabled(const MachineFunction &MF); 185 186public: 187 static char ID; 188 189 ShrinkWrap() : MachineFunctionPass(ID) { 190 initializeShrinkWrapPass(*PassRegistry::getPassRegistry()); 191 } 192 193 void getAnalysisUsage(AnalysisUsage &AU) const override { 194 AU.setPreservesAll(); 195 AU.addRequired<MachineBlockFrequencyInfo>(); 196 AU.addRequired<MachineDominatorTree>(); 197 AU.addRequired<MachinePostDominatorTree>(); 198 AU.addRequired<MachineLoopInfo>(); 199 MachineFunctionPass::getAnalysisUsage(AU); 200 } 201 202 StringRef getPassName() const override { return "Shrink Wrapping analysis"; } 203 204 /// \brief Perform the shrink-wrapping analysis and update 205 /// the MachineFrameInfo attached to \p MF with the results. 206 bool runOnMachineFunction(MachineFunction &MF) override; 207}; 208} // End anonymous namespace. 209 210char ShrinkWrap::ID = 0; 211char &llvm::ShrinkWrapID = ShrinkWrap::ID; 212 213INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 214INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 215INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 216INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 217INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 218INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false) 219 220bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, 221 RegScavenger *RS) const { 222 if (MI.getOpcode() == FrameSetupOpcode || 223 MI.getOpcode() == FrameDestroyOpcode) { 224 DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); 225 return true; 226 } 227 for (const MachineOperand &MO : MI.operands()) { 228 bool UseOrDefCSR = false; 229 if (MO.isReg()) { 230 unsigned PhysReg = MO.getReg(); 231 if (!PhysReg) 232 continue; 233 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 234 "Unallocated register?!"); 235 UseOrDefCSR = RCI.getLastCalleeSavedAlias(PhysReg); 236 } else if (MO.isRegMask()) { 237 // Check if this regmask clobbers any of the CSRs. 238 for (unsigned Reg : getCurrentCSRs(RS)) { 239 if (MO.clobbersPhysReg(Reg)) { 240 UseOrDefCSR = true; 241 break; 242 } 243 } 244 } 245 if (UseOrDefCSR || MO.isFI()) { 246 DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI(" 247 << MO.isFI() << "): " << MI << '\n'); 248 return true; 249 } 250 } 251 return false; 252} 253 254/// \brief Helper function to find the immediate (post) dominator. 255template <typename ListOfBBs, typename DominanceAnalysis> 256static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, 257 DominanceAnalysis &Dom) { 258 MachineBasicBlock *IDom = &Block; 259 for (MachineBasicBlock *BB : BBs) { 260 IDom = Dom.findNearestCommonDominator(IDom, BB); 261 if (!IDom) 262 break; 263 } 264 if (IDom == &Block) 265 return nullptr; 266 return IDom; 267} 268 269void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB, 270 RegScavenger *RS) { 271 // Get rid of the easy cases first. 272 if (!Save) 273 Save = &MBB; 274 else 275 Save = MDT->findNearestCommonDominator(Save, &MBB); 276 277 if (!Save) { 278 DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); 279 return; 280 } 281 282 if (!Restore) 283 Restore = &MBB; 284 else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it 285 // means the block never returns. If that's the 286 // case, we don't want to call 287 // `findNearestCommonDominator`, which will 288 // return `Restore`. 289 Restore = MPDT->findNearestCommonDominator(Restore, &MBB); 290 else 291 Restore = nullptr; // Abort, we can't find a restore point in this case. 292 293 // Make sure we would be able to insert the restore code before the 294 // terminator. 295 if (Restore == &MBB) { 296 for (const MachineInstr &Terminator : MBB.terminators()) { 297 if (!useOrDefCSROrFI(Terminator, RS)) 298 continue; 299 // One of the terminator needs to happen before the restore point. 300 if (MBB.succ_empty()) { 301 Restore = nullptr; // Abort, we can't find a restore point in this case. 302 break; 303 } 304 // Look for a restore point that post-dominates all the successors. 305 // The immediate post-dominator is what we are looking for. 306 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 307 break; 308 } 309 } 310 311 if (!Restore) { 312 DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n"); 313 return; 314 } 315 316 // Make sure Save and Restore are suitable for shrink-wrapping: 317 // 1. all path from Save needs to lead to Restore before exiting. 318 // 2. all path to Restore needs to go through Save from Entry. 319 // We achieve that by making sure that: 320 // A. Save dominates Restore. 321 // B. Restore post-dominates Save. 322 // C. Save and Restore are in the same loop. 323 bool SaveDominatesRestore = false; 324 bool RestorePostDominatesSave = false; 325 while (Save && Restore && 326 (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) || 327 !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) || 328 // Post-dominance is not enough in loops to ensure that all uses/defs 329 // are after the prologue and before the epilogue at runtime. 330 // E.g., 331 // while(1) { 332 // Save 333 // Restore 334 // if (...) 335 // break; 336 // use/def CSRs 337 // } 338 // All the uses/defs of CSRs are dominated by Save and post-dominated 339 // by Restore. However, the CSRs uses are still reachable after 340 // Restore and before Save are executed. 341 // 342 // For now, just push the restore/save points outside of loops. 343 // FIXME: Refine the criteria to still find interesting cases 344 // for loops. 345 MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 346 // Fix (A). 347 if (!SaveDominatesRestore) { 348 Save = MDT->findNearestCommonDominator(Save, Restore); 349 continue; 350 } 351 // Fix (B). 352 if (!RestorePostDominatesSave) 353 Restore = MPDT->findNearestCommonDominator(Restore, Save); 354 355 // Fix (C). 356 if (Save && Restore && 357 (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 358 if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) { 359 // Push Save outside of this loop if immediate dominator is different 360 // from save block. If immediate dominator is not different, bail out. 361 Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 362 if (!Save) 363 break; 364 } else { 365 // If the loop does not exit, there is no point in looking 366 // for a post-dominator outside the loop. 367 SmallVector<MachineBasicBlock*, 4> ExitBlocks; 368 MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); 369 // Push Restore outside of this loop. 370 // Look for the immediate post-dominator of the loop exits. 371 MachineBasicBlock *IPdom = Restore; 372 for (MachineBasicBlock *LoopExitBB: ExitBlocks) { 373 IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); 374 if (!IPdom) 375 break; 376 } 377 // If the immediate post-dominator is not in a less nested loop, 378 // then we are stuck in a program with an infinite loop. 379 // In that case, we will not find a safe point, hence, bail out. 380 if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)) 381 Restore = IPdom; 382 else { 383 Restore = nullptr; 384 break; 385 } 386 } 387 } 388 } 389} 390 391/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI. 392/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the 393/// loop header. 394static bool isProperBackedge(const MachineLoopInfo &MLI, 395 const MachineBasicBlock *SrcBB, 396 const MachineBasicBlock *DestBB) { 397 for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop; 398 Loop = Loop->getParentLoop()) { 399 if (Loop->getHeader() == DestBB) 400 return true; 401 } 402 return false; 403} 404 405/// Check if the CFG of \p MF is irreducible. 406static bool isIrreducibleCFG(const MachineFunction &MF, 407 const MachineLoopInfo &MLI) { 408 const MachineBasicBlock *Entry = &*MF.begin(); 409 ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry); 410 BitVector VisitedBB(MF.getNumBlockIDs()); 411 for (const MachineBasicBlock *MBB : RPOT) { 412 VisitedBB.set(MBB->getNumber()); 413 for (const MachineBasicBlock *SuccBB : MBB->successors()) { 414 if (!VisitedBB.test(SuccBB->getNumber())) 415 continue; 416 // We already visited SuccBB, thus MBB->SuccBB must be a backedge. 417 // Check that the head matches what we have in the loop information. 418 // Otherwise, we have an irreducible graph. 419 if (!isProperBackedge(MLI, MBB, SuccBB)) 420 return true; 421 } 422 } 423 return false; 424} 425 426bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { 427 if (skipFunction(*MF.getFunction()) || MF.empty() || !isShrinkWrapEnabled(MF)) 428 return false; 429 430 DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 431 432 init(MF); 433 434 if (isIrreducibleCFG(MF, *MLI)) { 435 // If MF is irreducible, a block may be in a loop without 436 // MachineLoopInfo reporting it. I.e., we may use the 437 // post-dominance property in loops, which lead to incorrect 438 // results. Moreover, we may miss that the prologue and 439 // epilogue are not in the same loop, leading to unbalanced 440 // construction/deconstruction of the stack frame. 441 DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n"); 442 return false; 443 } 444 445 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 446 std::unique_ptr<RegScavenger> RS( 447 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr); 448 449 for (MachineBasicBlock &MBB : MF) { 450 DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName() 451 << '\n'); 452 453 if (MBB.isEHFuncletEntry()) { 454 DEBUG(dbgs() << "EH Funclets are not supported yet.\n"); 455 return false; 456 } 457 458 for (const MachineInstr &MI : MBB) { 459 if (!useOrDefCSROrFI(MI, RS.get())) 460 continue; 461 // Save (resp. restore) point must dominate (resp. post dominate) 462 // MI. Look for the proper basic block for those. 463 updateSaveRestorePoints(MBB, RS.get()); 464 // If we are at a point where we cannot improve the placement of 465 // save/restore instructions, just give up. 466 if (!ArePointsInteresting()) { 467 DEBUG(dbgs() << "No Shrink wrap candidate found\n"); 468 return false; 469 } 470 // No need to look for other instructions, this basic block 471 // will already be part of the handled region. 472 break; 473 } 474 } 475 if (!ArePointsInteresting()) { 476 // If the points are not interesting at this point, then they must be null 477 // because it means we did not encounter any frame/CSR related code. 478 // Otherwise, we would have returned from the previous loop. 479 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); 480 DEBUG(dbgs() << "Nothing to shrink-wrap\n"); 481 return false; 482 } 483 484 DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq 485 << '\n'); 486 487 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 488 do { 489 DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " 490 << Save->getNumber() << ' ' << Save->getName() << ' ' 491 << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: " 492 << Restore->getNumber() << ' ' << Restore->getName() << ' ' 493 << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); 494 495 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; 496 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && 497 EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) && 498 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) && 499 TFI->canUseAsEpilogue(*Restore))) 500 break; 501 DEBUG(dbgs() << "New points are too expensive or invalid for the target\n"); 502 MachineBasicBlock *NewBB; 503 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) { 504 Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 505 if (!Save) 506 break; 507 NewBB = Save; 508 } else { 509 // Restore is expensive. 510 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 511 if (!Restore) 512 break; 513 NewBB = Restore; 514 } 515 updateSaveRestorePoints(*NewBB, RS.get()); 516 } while (Save && Restore); 517 518 if (!ArePointsInteresting()) { 519 ++NumCandidatesDropped; 520 return false; 521 } 522 523 DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber() 524 << ' ' << Save->getName() << "\nRestore: " 525 << Restore->getNumber() << ' ' << Restore->getName() << '\n'); 526 527 MachineFrameInfo &MFI = MF.getFrameInfo(); 528 MFI.setSavePoint(Save); 529 MFI.setRestorePoint(Restore); 530 ++NumCandidates; 531 return false; 532} 533 534bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { 535 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 536 537 switch (EnableShrinkWrapOpt) { 538 case cl::BOU_UNSET: 539 return TFI->enableShrinkWrapping(MF) && 540 // Windows with CFI has some limitations that make it impossible 541 // to use shrink-wrapping. 542 !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() && 543 // Sanitizers look at the value of the stack at the location 544 // of the crash. Since a crash can happen anywhere, the 545 // frame must be lowered before anything else happen for the 546 // sanitizers to be able to get a correct stack frame. 547 !(MF.getFunction()->hasFnAttribute(Attribute::SanitizeAddress) || 548 MF.getFunction()->hasFnAttribute(Attribute::SanitizeThread) || 549 MF.getFunction()->hasFnAttribute(Attribute::SanitizeMemory)); 550 // If EnableShrinkWrap is set, it takes precedence on whatever the 551 // target sets. The rational is that we assume we want to test 552 // something related to shrink-wrapping. 553 case cl::BOU_TRUE: 554 return true; 555 case cl::BOU_FALSE: 556 return false; 557 } 558 llvm_unreachable("Invalid shrink-wrapping state"); 559} 560