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