ShrinkWrap.cpp revision 314564
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, "shrink-wrap", "Shrink Wrap Pass", false, 214 false) 215INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 216INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 217INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 218INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 219INITIALIZE_PASS_END(ShrinkWrap, "shrink-wrap", "Shrink Wrap Pass", false, false) 220 221bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, 222 RegScavenger *RS) const { 223 if (MI.getOpcode() == FrameSetupOpcode || 224 MI.getOpcode() == FrameDestroyOpcode) { 225 DEBUG(dbgs() << "Frame instruction: " << MI << '\n'); 226 return true; 227 } 228 for (const MachineOperand &MO : MI.operands()) { 229 bool UseOrDefCSR = false; 230 if (MO.isReg()) { 231 unsigned PhysReg = MO.getReg(); 232 if (!PhysReg) 233 continue; 234 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && 235 "Unallocated register?!"); 236 UseOrDefCSR = RCI.getLastCalleeSavedAlias(PhysReg); 237 } else if (MO.isRegMask()) { 238 // Check if this regmask clobbers any of the CSRs. 239 for (unsigned Reg : getCurrentCSRs(RS)) { 240 if (MO.clobbersPhysReg(Reg)) { 241 UseOrDefCSR = true; 242 break; 243 } 244 } 245 } 246 if (UseOrDefCSR || MO.isFI()) { 247 DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI(" 248 << MO.isFI() << "): " << MI << '\n'); 249 return true; 250 } 251 } 252 return false; 253} 254 255/// \brief Helper function to find the immediate (post) dominator. 256template <typename ListOfBBs, typename DominanceAnalysis> 257static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs, 258 DominanceAnalysis &Dom) { 259 MachineBasicBlock *IDom = &Block; 260 for (MachineBasicBlock *BB : BBs) { 261 IDom = Dom.findNearestCommonDominator(IDom, BB); 262 if (!IDom) 263 break; 264 } 265 if (IDom == &Block) 266 return nullptr; 267 return IDom; 268} 269 270void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB, 271 RegScavenger *RS) { 272 // Get rid of the easy cases first. 273 if (!Save) 274 Save = &MBB; 275 else 276 Save = MDT->findNearestCommonDominator(Save, &MBB); 277 278 if (!Save) { 279 DEBUG(dbgs() << "Found a block that is not reachable from Entry\n"); 280 return; 281 } 282 283 if (!Restore) 284 Restore = &MBB; 285 else 286 Restore = MPDT->findNearestCommonDominator(Restore, &MBB); 287 288 // Make sure we would be able to insert the restore code before the 289 // terminator. 290 if (Restore == &MBB) { 291 for (const MachineInstr &Terminator : MBB.terminators()) { 292 if (!useOrDefCSROrFI(Terminator, RS)) 293 continue; 294 // One of the terminator needs to happen before the restore point. 295 if (MBB.succ_empty()) { 296 Restore = nullptr; 297 break; 298 } 299 // Look for a restore point that post-dominates all the successors. 300 // The immediate post-dominator is what we are looking for. 301 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 302 break; 303 } 304 } 305 306 if (!Restore) { 307 DEBUG(dbgs() << "Restore point needs to be spanned on several blocks\n"); 308 return; 309 } 310 311 // Make sure Save and Restore are suitable for shrink-wrapping: 312 // 1. all path from Save needs to lead to Restore before exiting. 313 // 2. all path to Restore needs to go through Save from Entry. 314 // We achieve that by making sure that: 315 // A. Save dominates Restore. 316 // B. Restore post-dominates Save. 317 // C. Save and Restore are in the same loop. 318 bool SaveDominatesRestore = false; 319 bool RestorePostDominatesSave = false; 320 while (Save && Restore && 321 (!(SaveDominatesRestore = MDT->dominates(Save, Restore)) || 322 !(RestorePostDominatesSave = MPDT->dominates(Restore, Save)) || 323 // Post-dominance is not enough in loops to ensure that all uses/defs 324 // are after the prologue and before the epilogue at runtime. 325 // E.g., 326 // while(1) { 327 // Save 328 // Restore 329 // if (...) 330 // break; 331 // use/def CSRs 332 // } 333 // All the uses/defs of CSRs are dominated by Save and post-dominated 334 // by Restore. However, the CSRs uses are still reachable after 335 // Restore and before Save are executed. 336 // 337 // For now, just push the restore/save points outside of loops. 338 // FIXME: Refine the criteria to still find interesting cases 339 // for loops. 340 MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 341 // Fix (A). 342 if (!SaveDominatesRestore) { 343 Save = MDT->findNearestCommonDominator(Save, Restore); 344 continue; 345 } 346 // Fix (B). 347 if (!RestorePostDominatesSave) 348 Restore = MPDT->findNearestCommonDominator(Restore, Save); 349 350 // Fix (C). 351 if (Save && Restore && 352 (MLI->getLoopFor(Save) || MLI->getLoopFor(Restore))) { 353 if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) { 354 // Push Save outside of this loop if immediate dominator is different 355 // from save block. If immediate dominator is not different, bail out. 356 Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 357 if (!Save) 358 break; 359 } else { 360 // If the loop does not exit, there is no point in looking 361 // for a post-dominator outside the loop. 362 SmallVector<MachineBasicBlock*, 4> ExitBlocks; 363 MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); 364 // Push Restore outside of this loop. 365 // Look for the immediate post-dominator of the loop exits. 366 MachineBasicBlock *IPdom = Restore; 367 for (MachineBasicBlock *LoopExitBB: ExitBlocks) { 368 IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); 369 if (!IPdom) 370 break; 371 } 372 // If the immediate post-dominator is not in a less nested loop, 373 // then we are stuck in a program with an infinite loop. 374 // In that case, we will not find a safe point, hence, bail out. 375 if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)) 376 Restore = IPdom; 377 else { 378 Restore = nullptr; 379 break; 380 } 381 } 382 } 383 } 384} 385 386/// Check whether the edge (\p SrcBB, \p DestBB) is a backedge according to MLI. 387/// I.e., check if it exists a loop that contains SrcBB and where DestBB is the 388/// loop header. 389static bool isProperBackedge(const MachineLoopInfo &MLI, 390 const MachineBasicBlock *SrcBB, 391 const MachineBasicBlock *DestBB) { 392 for (const MachineLoop *Loop = MLI.getLoopFor(SrcBB); Loop; 393 Loop = Loop->getParentLoop()) { 394 if (Loop->getHeader() == DestBB) 395 return true; 396 } 397 return false; 398} 399 400/// Check if the CFG of \p MF is irreducible. 401static bool isIrreducibleCFG(const MachineFunction &MF, 402 const MachineLoopInfo &MLI) { 403 const MachineBasicBlock *Entry = &*MF.begin(); 404 ReversePostOrderTraversal<const MachineBasicBlock *> RPOT(Entry); 405 BitVector VisitedBB(MF.getNumBlockIDs()); 406 for (const MachineBasicBlock *MBB : RPOT) { 407 VisitedBB.set(MBB->getNumber()); 408 for (const MachineBasicBlock *SuccBB : MBB->successors()) { 409 if (!VisitedBB.test(SuccBB->getNumber())) 410 continue; 411 // We already visited SuccBB, thus MBB->SuccBB must be a backedge. 412 // Check that the head matches what we have in the loop information. 413 // Otherwise, we have an irreducible graph. 414 if (!isProperBackedge(MLI, MBB, SuccBB)) 415 return true; 416 } 417 } 418 return false; 419} 420 421bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) { 422 if (MF.empty() || !isShrinkWrapEnabled(MF)) 423 return false; 424 425 DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 426 427 init(MF); 428 429 if (isIrreducibleCFG(MF, *MLI)) { 430 // If MF is irreducible, a block may be in a loop without 431 // MachineLoopInfo reporting it. I.e., we may use the 432 // post-dominance property in loops, which lead to incorrect 433 // results. Moreover, we may miss that the prologue and 434 // epilogue are not in the same loop, leading to unbalanced 435 // construction/deconstruction of the stack frame. 436 DEBUG(dbgs() << "Irreducible CFGs are not supported yet\n"); 437 return false; 438 } 439 440 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 441 std::unique_ptr<RegScavenger> RS( 442 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr); 443 444 for (MachineBasicBlock &MBB : MF) { 445 DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' ' << MBB.getName() 446 << '\n'); 447 448 if (MBB.isEHFuncletEntry()) { 449 DEBUG(dbgs() << "EH Funclets are not supported yet.\n"); 450 return false; 451 } 452 453 for (const MachineInstr &MI : MBB) { 454 if (!useOrDefCSROrFI(MI, RS.get())) 455 continue; 456 // Save (resp. restore) point must dominate (resp. post dominate) 457 // MI. Look for the proper basic block for those. 458 updateSaveRestorePoints(MBB, RS.get()); 459 // If we are at a point where we cannot improve the placement of 460 // save/restore instructions, just give up. 461 if (!ArePointsInteresting()) { 462 DEBUG(dbgs() << "No Shrink wrap candidate found\n"); 463 return false; 464 } 465 // No need to look for other instructions, this basic block 466 // will already be part of the handled region. 467 break; 468 } 469 } 470 if (!ArePointsInteresting()) { 471 // If the points are not interesting at this point, then they must be null 472 // because it means we did not encounter any frame/CSR related code. 473 // Otherwise, we would have returned from the previous loop. 474 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!"); 475 DEBUG(dbgs() << "Nothing to shrink-wrap\n"); 476 return false; 477 } 478 479 DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq 480 << '\n'); 481 482 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 483 do { 484 DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: " 485 << Save->getNumber() << ' ' << Save->getName() << ' ' 486 << MBFI->getBlockFreq(Save).getFrequency() << "\nRestore: " 487 << Restore->getNumber() << ' ' << Restore->getName() << ' ' 488 << MBFI->getBlockFreq(Restore).getFrequency() << '\n'); 489 490 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false; 491 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) && 492 EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()) && 493 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save)) && 494 TFI->canUseAsEpilogue(*Restore))) 495 break; 496 DEBUG(dbgs() << "New points are too expensive or invalid for the target\n"); 497 MachineBasicBlock *NewBB; 498 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) { 499 Save = FindIDom<>(*Save, Save->predecessors(), *MDT); 500 if (!Save) 501 break; 502 NewBB = Save; 503 } else { 504 // Restore is expensive. 505 Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT); 506 if (!Restore) 507 break; 508 NewBB = Restore; 509 } 510 updateSaveRestorePoints(*NewBB, RS.get()); 511 } while (Save && Restore); 512 513 if (!ArePointsInteresting()) { 514 ++NumCandidatesDropped; 515 return false; 516 } 517 518 DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: " << Save->getNumber() 519 << ' ' << Save->getName() << "\nRestore: " 520 << Restore->getNumber() << ' ' << Restore->getName() << '\n'); 521 522 MachineFrameInfo &MFI = MF.getFrameInfo(); 523 MFI.setSavePoint(Save); 524 MFI.setRestorePoint(Restore); 525 ++NumCandidates; 526 return false; 527} 528 529bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { 530 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 531 532 switch (EnableShrinkWrapOpt) { 533 case cl::BOU_UNSET: 534 return TFI->enableShrinkWrapping(MF) && 535 // Windows with CFI has some limitations that make it impossible 536 // to use shrink-wrapping. 537 !MF.getTarget().getMCAsmInfo()->usesWindowsCFI() && 538 // Sanitizers look at the value of the stack at the location 539 // of the crash. Since a crash can happen anywhere, the 540 // frame must be lowered before anything else happen for the 541 // sanitizers to be able to get a correct stack frame. 542 !(MF.getFunction()->hasFnAttribute(Attribute::SanitizeAddress) || 543 MF.getFunction()->hasFnAttribute(Attribute::SanitizeThread) || 544 MF.getFunction()->hasFnAttribute(Attribute::SanitizeMemory)); 545 // If EnableShrinkWrap is set, it takes precedence on whatever the 546 // target sets. The rational is that we assume we want to test 547 // something related to shrink-wrapping. 548 case cl::BOU_TRUE: 549 return true; 550 case cl::BOU_FALSE: 551 return false; 552 } 553 llvm_unreachable("Invalid shrink-wrapping state"); 554} 555