1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/MustExecute.h" 10 #include "llvm/ADT/PostOrderIterator.h" 11 #include "llvm/Analysis/CFG.h" 12 #include "llvm/Analysis/InstructionSimplify.h" 13 #include "llvm/Analysis/LoopInfo.h" 14 #include "llvm/Analysis/Passes.h" 15 #include "llvm/Analysis/ValueTracking.h" 16 #include "llvm/IR/AssemblyAnnotationWriter.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/IR/InstIterator.h" 19 #include "llvm/IR/LLVMContext.h" 20 #include "llvm/IR/Module.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include "llvm/Support/FormattedStream.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 using namespace llvm; 26 27 #define DEBUG_TYPE "must-execute" 28 29 const DenseMap<BasicBlock *, ColorVector> & 30 LoopSafetyInfo::getBlockColors() const { 31 return BlockColors; 32 } 33 34 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) { 35 ColorVector &ColorsForNewBlock = BlockColors[New]; 36 ColorVector &ColorsForOldBlock = BlockColors[Old]; 37 ColorsForNewBlock = ColorsForOldBlock; 38 } 39 40 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { 41 (void)BB; 42 return anyBlockMayThrow(); 43 } 44 45 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const { 46 return MayThrow; 47 } 48 49 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { 50 assert(CurLoop != nullptr && "CurLoop can't be null"); 51 BasicBlock *Header = CurLoop->getHeader(); 52 // Iterate over header and compute safety info. 53 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header); 54 MayThrow = HeaderMayThrow; 55 // Iterate over loop instructions and compute safety info. 56 // Skip header as it has been computed and stored in HeaderMayThrow. 57 // The first block in loopinfo.Blocks is guaranteed to be the header. 58 assert(Header == *CurLoop->getBlocks().begin() && 59 "First block must be header"); 60 for (Loop::block_iterator BB = std::next(CurLoop->block_begin()), 61 BBE = CurLoop->block_end(); 62 (BB != BBE) && !MayThrow; ++BB) 63 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB); 64 65 computeBlockColors(CurLoop); 66 } 67 68 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { 69 return ICF.hasICF(BB); 70 } 71 72 bool ICFLoopSafetyInfo::anyBlockMayThrow() const { 73 return MayThrow; 74 } 75 76 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { 77 assert(CurLoop != nullptr && "CurLoop can't be null"); 78 ICF.clear(); 79 MW.clear(); 80 MayThrow = false; 81 // Figure out the fact that at least one block may throw. 82 for (auto &BB : CurLoop->blocks()) 83 if (ICF.hasICF(&*BB)) { 84 MayThrow = true; 85 break; 86 } 87 computeBlockColors(CurLoop); 88 } 89 90 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst, 91 const BasicBlock *BB) { 92 ICF.insertInstructionTo(Inst, BB); 93 MW.insertInstructionTo(Inst, BB); 94 } 95 96 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) { 97 ICF.removeInstruction(Inst); 98 MW.removeInstruction(Inst); 99 } 100 101 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) { 102 // Compute funclet colors if we might sink/hoist in a function with a funclet 103 // personality routine. 104 Function *Fn = CurLoop->getHeader()->getParent(); 105 if (Fn->hasPersonalityFn()) 106 if (Constant *PersonalityFn = Fn->getPersonalityFn()) 107 if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn))) 108 BlockColors = colorEHFunclets(*Fn); 109 } 110 111 /// Return true if we can prove that the given ExitBlock is not reached on the 112 /// first iteration of the given loop. That is, the backedge of the loop must 113 /// be executed before the ExitBlock is executed in any dynamic execution trace. 114 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, 115 const DominatorTree *DT, 116 const Loop *CurLoop) { 117 auto *CondExitBlock = ExitBlock->getSinglePredecessor(); 118 if (!CondExitBlock) 119 // expect unique exits 120 return false; 121 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block"); 122 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator()); 123 if (!BI || !BI->isConditional()) 124 return false; 125 // If condition is constant and false leads to ExitBlock then we always 126 // execute the true branch. 127 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) 128 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock; 129 auto *Cond = dyn_cast<CmpInst>(BI->getCondition()); 130 if (!Cond) 131 return false; 132 // todo: this would be a lot more powerful if we used scev, but all the 133 // plumbing is currently missing to pass a pointer in from the pass 134 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known 135 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0)); 136 auto *RHS = Cond->getOperand(1); 137 if (!LHS || LHS->getParent() != CurLoop->getHeader()) 138 return false; 139 auto DL = ExitBlock->getModule()->getDataLayout(); 140 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader()); 141 auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(), 142 IVStart, RHS, 143 {DL, /*TLI*/ nullptr, 144 DT, /*AC*/ nullptr, BI}); 145 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull); 146 if (!SimpleCst) 147 return false; 148 if (ExitBlock == BI->getSuccessor(0)) 149 return SimpleCst->isZeroValue(); 150 assert(ExitBlock == BI->getSuccessor(1) && "implied by above"); 151 return SimpleCst->isAllOnesValue(); 152 } 153 154 /// Collect all blocks from \p CurLoop which lie on all possible paths from 155 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set 156 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty. 157 static void collectTransitivePredecessors( 158 const Loop *CurLoop, const BasicBlock *BB, 159 SmallPtrSetImpl<const BasicBlock *> &Predecessors) { 160 assert(Predecessors.empty() && "Garbage in predecessors set?"); 161 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); 162 if (BB == CurLoop->getHeader()) 163 return; 164 SmallVector<const BasicBlock *, 4> WorkList; 165 for (auto *Pred : predecessors(BB)) { 166 Predecessors.insert(Pred); 167 WorkList.push_back(Pred); 168 } 169 while (!WorkList.empty()) { 170 auto *Pred = WorkList.pop_back_val(); 171 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!"); 172 // We are not interested in backedges and we don't want to leave loop. 173 if (Pred == CurLoop->getHeader()) 174 continue; 175 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all 176 // blocks of this inner loop, even those that are always executed AFTER the 177 // BB. It may make our analysis more conservative than it could be, see test 178 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll. 179 // We can ignore backedge of all loops containing BB to get a sligtly more 180 // optimistic result. 181 for (auto *PredPred : predecessors(Pred)) 182 if (Predecessors.insert(PredPred).second) 183 WorkList.push_back(PredPred); 184 } 185 } 186 187 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop, 188 const BasicBlock *BB, 189 const DominatorTree *DT) const { 190 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); 191 192 // Fast path: header is always reached once the loop is entered. 193 if (BB == CurLoop->getHeader()) 194 return true; 195 196 // Collect all transitive predecessors of BB in the same loop. This set will 197 // be a subset of the blocks within the loop. 198 SmallPtrSet<const BasicBlock *, 4> Predecessors; 199 collectTransitivePredecessors(CurLoop, BB, Predecessors); 200 201 // Make sure that all successors of, all predecessors of BB which are not 202 // dominated by BB, are either: 203 // 1) BB, 204 // 2) Also predecessors of BB, 205 // 3) Exit blocks which are not taken on 1st iteration. 206 // Memoize blocks we've already checked. 207 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors; 208 for (auto *Pred : Predecessors) { 209 // Predecessor block may throw, so it has a side exit. 210 if (blockMayThrow(Pred)) 211 return false; 212 213 // BB dominates Pred, so if Pred runs, BB must run. 214 // This is true when Pred is a loop latch. 215 if (DT->dominates(BB, Pred)) 216 continue; 217 218 for (auto *Succ : successors(Pred)) 219 if (CheckedSuccessors.insert(Succ).second && 220 Succ != BB && !Predecessors.count(Succ)) 221 // By discharging conditions that are not executed on the 1st iteration, 222 // we guarantee that *at least* on the first iteration all paths from 223 // header that *may* execute will lead us to the block of interest. So 224 // that if we had virtually peeled one iteration away, in this peeled 225 // iteration the set of predecessors would contain only paths from 226 // header to BB without any exiting edges that may execute. 227 // 228 // TODO: We only do it for exiting edges currently. We could use the 229 // same function to skip some of the edges within the loop if we know 230 // that they will not be taken on the 1st iteration. 231 // 232 // TODO: If we somehow know the number of iterations in loop, the same 233 // check may be done for any arbitrary N-th iteration as long as N is 234 // not greater than minimum number of iterations in this loop. 235 if (CurLoop->contains(Succ) || 236 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop)) 237 return false; 238 } 239 240 // All predecessors can only lead us to BB. 241 return true; 242 } 243 244 /// Returns true if the instruction in a loop is guaranteed to execute at least 245 /// once. 246 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst, 247 const DominatorTree *DT, 248 const Loop *CurLoop) const { 249 // If the instruction is in the header block for the loop (which is very 250 // common), it is always guaranteed to dominate the exit blocks. Since this 251 // is a common case, and can save some work, check it now. 252 if (Inst.getParent() == CurLoop->getHeader()) 253 // If there's a throw in the header block, we can't guarantee we'll reach 254 // Inst unless we can prove that Inst comes before the potential implicit 255 // exit. At the moment, we use a (cheap) hack for the common case where 256 // the instruction of interest is the first one in the block. 257 return !HeaderMayThrow || 258 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst; 259 260 // If there is a path from header to exit or latch that doesn't lead to our 261 // instruction's block, return false. 262 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT); 263 } 264 265 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst, 266 const DominatorTree *DT, 267 const Loop *CurLoop) const { 268 return !ICF.isDominatedByICFIFromSameBlock(&Inst) && 269 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT); 270 } 271 272 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB, 273 const Loop *CurLoop) const { 274 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); 275 276 // Fast path: there are no instructions before header. 277 if (BB == CurLoop->getHeader()) 278 return true; 279 280 // Collect all transitive predecessors of BB in the same loop. This set will 281 // be a subset of the blocks within the loop. 282 SmallPtrSet<const BasicBlock *, 4> Predecessors; 283 collectTransitivePredecessors(CurLoop, BB, Predecessors); 284 // Find if there any instruction in either predecessor that could write 285 // to memory. 286 for (auto *Pred : Predecessors) 287 if (MW.mayWriteToMemory(Pred)) 288 return false; 289 return true; 290 } 291 292 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I, 293 const Loop *CurLoop) const { 294 auto *BB = I.getParent(); 295 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); 296 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) && 297 doesNotWriteMemoryBefore(BB, CurLoop); 298 } 299 300 namespace { 301 struct MustExecutePrinter : public FunctionPass { 302 303 static char ID; // Pass identification, replacement for typeid 304 MustExecutePrinter() : FunctionPass(ID) { 305 initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry()); 306 } 307 void getAnalysisUsage(AnalysisUsage &AU) const override { 308 AU.setPreservesAll(); 309 AU.addRequired<DominatorTreeWrapperPass>(); 310 AU.addRequired<LoopInfoWrapperPass>(); 311 } 312 bool runOnFunction(Function &F) override; 313 }; 314 struct MustBeExecutedContextPrinter : public ModulePass { 315 static char ID; 316 317 MustBeExecutedContextPrinter() : ModulePass(ID) { 318 initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry()); 319 } 320 void getAnalysisUsage(AnalysisUsage &AU) const override { 321 AU.setPreservesAll(); 322 } 323 bool runOnModule(Module &M) override; 324 }; 325 } 326 327 char MustExecutePrinter::ID = 0; 328 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", 329 "Instructions which execute on loop entry", false, true) 330 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 331 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 332 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute", 333 "Instructions which execute on loop entry", false, true) 334 335 FunctionPass *llvm::createMustExecutePrinter() { 336 return new MustExecutePrinter(); 337 } 338 339 char MustBeExecutedContextPrinter::ID = 0; 340 INITIALIZE_PASS_BEGIN( 341 MustBeExecutedContextPrinter, "print-must-be-executed-contexts", 342 "print the must-be-executed-contexed for all instructions", false, true) 343 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 344 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 345 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 346 INITIALIZE_PASS_END(MustBeExecutedContextPrinter, 347 "print-must-be-executed-contexts", 348 "print the must-be-executed-contexed for all instructions", 349 false, true) 350 351 ModulePass *llvm::createMustBeExecutedContextPrinter() { 352 return new MustBeExecutedContextPrinter(); 353 } 354 355 bool MustBeExecutedContextPrinter::runOnModule(Module &M) { 356 MustBeExecutedContextExplorer Explorer(true); 357 for (Function &F : M) { 358 for (Instruction &I : instructions(F)) { 359 dbgs() << "-- Explore context of: " << I << "\n"; 360 for (const Instruction *CI : Explorer.range(&I)) 361 dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI 362 << "\n"; 363 } 364 } 365 366 return false; 367 } 368 369 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) { 370 // TODO: merge these two routines. For the moment, we display the best 371 // result obtained by *either* implementation. This is a bit unfair since no 372 // caller actually gets the full power at the moment. 373 SimpleLoopSafetyInfo LSI; 374 LSI.computeLoopSafetyInfo(L); 375 return LSI.isGuaranteedToExecute(I, DT, L) || 376 isGuaranteedToExecuteForEveryIteration(&I, L); 377 } 378 379 namespace { 380 /// An assembly annotator class to print must execute information in 381 /// comments. 382 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter { 383 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec; 384 385 public: 386 MustExecuteAnnotatedWriter(const Function &F, 387 DominatorTree &DT, LoopInfo &LI) { 388 for (auto &I: instructions(F)) { 389 Loop *L = LI.getLoopFor(I.getParent()); 390 while (L) { 391 if (isMustExecuteIn(I, L, &DT)) { 392 MustExec[&I].push_back(L); 393 } 394 L = L->getParentLoop(); 395 }; 396 } 397 } 398 MustExecuteAnnotatedWriter(const Module &M, 399 DominatorTree &DT, LoopInfo &LI) { 400 for (auto &F : M) 401 for (auto &I: instructions(F)) { 402 Loop *L = LI.getLoopFor(I.getParent()); 403 while (L) { 404 if (isMustExecuteIn(I, L, &DT)) { 405 MustExec[&I].push_back(L); 406 } 407 L = L->getParentLoop(); 408 }; 409 } 410 } 411 412 413 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override { 414 if (!MustExec.count(&V)) 415 return; 416 417 const auto &Loops = MustExec.lookup(&V); 418 const auto NumLoops = Loops.size(); 419 if (NumLoops > 1) 420 OS << " ; (mustexec in " << NumLoops << " loops: "; 421 else 422 OS << " ; (mustexec in: "; 423 424 bool first = true; 425 for (const Loop *L : Loops) { 426 if (!first) 427 OS << ", "; 428 first = false; 429 OS << L->getHeader()->getName(); 430 } 431 OS << ")"; 432 } 433 }; 434 } // namespace 435 436 bool MustExecutePrinter::runOnFunction(Function &F) { 437 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 438 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 439 440 MustExecuteAnnotatedWriter Writer(F, DT, LI); 441 F.print(dbgs(), &Writer); 442 443 return false; 444 } 445 446 const Instruction * 447 MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( 448 MustBeExecutedIterator &It, const Instruction *PP) { 449 if (!PP) 450 return PP; 451 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n"); 452 453 // If we explore only inside a given basic block we stop at terminators. 454 if (!ExploreInterBlock && PP->isTerminator()) { 455 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n"); 456 return nullptr; 457 } 458 459 // If we do not traverse the call graph we check if we can make progress in 460 // the current function. First, check if the instruction is guaranteed to 461 // transfer execution to the successor. 462 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP); 463 if (!TransfersExecution) 464 return nullptr; 465 466 // If this is not a terminator we know that there is a single instruction 467 // after this one that is executed next if control is transfered. If not, 468 // we can try to go back to a call site we entered earlier. If none exists, we 469 // do not know any instruction that has to be executd next. 470 if (!PP->isTerminator()) { 471 const Instruction *NextPP = PP->getNextNode(); 472 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n"); 473 return NextPP; 474 } 475 476 // Finally, we have to handle terminators, trivial ones first. 477 assert(PP->isTerminator() && "Expected a terminator!"); 478 479 // A terminator without a successor is not handled yet. 480 if (PP->getNumSuccessors() == 0) { 481 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n"); 482 return nullptr; 483 } 484 485 // A terminator with a single successor, we will continue at the beginning of 486 // that one. 487 if (PP->getNumSuccessors() == 1) { 488 LLVM_DEBUG( 489 dbgs() << "\tUnconditional terminator, continue with successor\n"); 490 return &PP->getSuccessor(0)->front(); 491 } 492 493 LLVM_DEBUG(dbgs() << "\tNo join point found\n"); 494 return nullptr; 495 } 496 497 MustBeExecutedIterator::MustBeExecutedIterator( 498 MustBeExecutedContextExplorer &Explorer, const Instruction *I) 499 : Explorer(Explorer), CurInst(I) { 500 reset(I); 501 } 502 503 void MustBeExecutedIterator::reset(const Instruction *I) { 504 CurInst = I; 505 Visited.clear(); 506 Visited.insert(I); 507 } 508 509 const Instruction *MustBeExecutedIterator::advance() { 510 assert(CurInst && "Cannot advance an end iterator!"); 511 const Instruction *Next = 512 Explorer.getMustBeExecutedNextInstruction(*this, CurInst); 513 if (Next && !Visited.insert(Next).second) 514 Next = nullptr; 515 return Next; 516 } 517