787 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/MustExecute.h"10#include "llvm/ADT/PostOrderIterator.h"11#include "llvm/ADT/StringExtras.h"12#include "llvm/Analysis/CFG.h"13#include "llvm/Analysis/InstructionSimplify.h"14#include "llvm/Analysis/LoopInfo.h"15#include "llvm/Analysis/PostDominators.h"16#include "llvm/Analysis/ValueTracking.h"17#include "llvm/IR/AssemblyAnnotationWriter.h"18#include "llvm/IR/Dominators.h"19#include "llvm/IR/InstIterator.h"20#include "llvm/IR/Module.h"21#include "llvm/IR/PassManager.h"22#include "llvm/Support/FormattedStream.h"23#include "llvm/Support/raw_ostream.h"24 25using namespace llvm;26 27#define DEBUG_TYPE "must-execute"28 29const DenseMap<BasicBlock *, ColorVector> &30LoopSafetyInfo::getBlockColors() const {31 return BlockColors;32}33 34void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {35 ColorVector &ColorsForNewBlock = BlockColors[New];36 ColorVector &ColorsForOldBlock = BlockColors[Old];37 ColorsForNewBlock = ColorsForOldBlock;38}39 40bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {41 (void)BB;42 return anyBlockMayThrow();43}44 45bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {46 return MayThrow;47}48 49void 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 (const BasicBlock *BB : llvm::drop_begin(CurLoop->blocks())) {61 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(BB);62 if (MayThrow)63 break;64 }65 66 computeBlockColors(CurLoop);67}68 69bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {70 return ICF.hasICF(BB);71}72 73bool ICFLoopSafetyInfo::anyBlockMayThrow() const {74 return MayThrow;75}76 77void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {78 assert(CurLoop != nullptr && "CurLoop can't be null");79 ICF.clear();80 MW.clear();81 MayThrow = false;82 // Figure out the fact that at least one block may throw.83 for (const auto &BB : CurLoop->blocks())84 if (ICF.hasICF(&*BB)) {85 MayThrow = true;86 break;87 }88 computeBlockColors(CurLoop);89}90 91void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,92 const BasicBlock *BB) {93 ICF.insertInstructionTo(Inst, BB);94 MW.insertInstructionTo(Inst, BB);95}96 97void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {98 ICF.removeInstruction(Inst);99 MW.removeInstruction(Inst);100}101 102void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {103 // Compute funclet colors if we might sink/hoist in a function with a funclet104 // personality routine.105 Function *Fn = CurLoop->getHeader()->getParent();106 if (Fn->hasPersonalityFn())107 if (Constant *PersonalityFn = Fn->getPersonalityFn())108 if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))109 BlockColors = colorEHFunclets(*Fn);110}111 112/// Return true if we can prove that the given ExitBlock is not reached on the113/// first iteration of the given loop. That is, the backedge of the loop must114/// be executed before the ExitBlock is executed in any dynamic execution trace.115static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,116 const DominatorTree *DT,117 const Loop *CurLoop) {118 auto *CondExitBlock = ExitBlock->getSinglePredecessor();119 if (!CondExitBlock)120 // expect unique exits121 return false;122 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");123 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());124 if (!BI || !BI->isConditional())125 return false;126 // If condition is constant and false leads to ExitBlock then we always127 // execute the true branch.128 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))129 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;130 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());131 if (!Cond)132 return false;133 // todo: this would be a lot more powerful if we used scev, but all the134 // plumbing is currently missing to pass a pointer in from the pass135 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known136 ICmpInst::Predicate Pred = Cond->getPredicate();137 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));138 auto *RHS = Cond->getOperand(1);139 if (!LHS || LHS->getParent() != CurLoop->getHeader()) {140 Pred = Cond->getSwappedPredicate();141 LHS = dyn_cast<PHINode>(Cond->getOperand(1));142 RHS = Cond->getOperand(0);143 if (!LHS || LHS->getParent() != CurLoop->getHeader())144 return false;145 }146 147 auto DL = ExitBlock->getModule()->getDataLayout();148 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());149 auto *SimpleValOrNull = simplifyCmpInst(150 Pred, IVStart, RHS, {DL, /*TLI*/ nullptr, DT, /*AC*/ nullptr, BI});151 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);152 if (!SimpleCst)153 return false;154 if (ExitBlock == BI->getSuccessor(0))155 return SimpleCst->isZeroValue();156 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");157 return SimpleCst->isAllOnesValue();158}159 160/// Collect all blocks from \p CurLoop which lie on all possible paths from161/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set162/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.163/// Note: It's possible that we encounter Irreducible control flow, due to164/// which, we may find that a few predecessors of \p BB are not a part of the165/// \p CurLoop. We only return Predecessors that are a part of \p CurLoop.166static void collectTransitivePredecessors(167 const Loop *CurLoop, const BasicBlock *BB,168 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {169 assert(Predecessors.empty() && "Garbage in predecessors set?");170 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");171 if (BB == CurLoop->getHeader())172 return;173 SmallVector<const BasicBlock *, 4> WorkList;174 for (const auto *Pred : predecessors(BB)) {175 if (!CurLoop->contains(Pred))176 continue;177 Predecessors.insert(Pred);178 WorkList.push_back(Pred);179 }180 while (!WorkList.empty()) {181 auto *Pred = WorkList.pop_back_val();182 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");183 // We are not interested in backedges and we don't want to leave loop.184 if (Pred == CurLoop->getHeader())185 continue;186 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all187 // blocks of this inner loop, even those that are always executed AFTER the188 // BB. It may make our analysis more conservative than it could be, see test189 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.190 // We can ignore backedge of all loops containing BB to get a sligtly more191 // optimistic result.192 for (const auto *PredPred : predecessors(Pred))193 if (CurLoop->contains(PredPred) && Predecessors.insert(PredPred).second)194 WorkList.push_back(PredPred);195 }196}197 198bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,199 const BasicBlock *BB,200 const DominatorTree *DT) const {201 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");202 203 // Fast path: header is always reached once the loop is entered.204 if (BB == CurLoop->getHeader())205 return true;206 207 // Collect all transitive predecessors of BB in the same loop. This set will208 // be a subset of the blocks within the loop.209 SmallPtrSet<const BasicBlock *, 4> Predecessors;210 collectTransitivePredecessors(CurLoop, BB, Predecessors);211 212 // Bail out if a latch block is part of the predecessor set. In this case213 // we may take the backedge to the header and not execute other latch214 // successors.215 for (const BasicBlock *Pred : predecessors(CurLoop->getHeader()))216 // Predecessors only contains loop blocks, so we don't have to worry about217 // preheader predecessors here.218 if (Predecessors.contains(Pred))219 return false;220 221 // Make sure that all successors of, all predecessors of BB which are not222 // dominated by BB, are either:223 // 1) BB,224 // 2) Also predecessors of BB,225 // 3) Exit blocks which are not taken on 1st iteration.226 // Memoize blocks we've already checked.227 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;228 for (const auto *Pred : Predecessors) {229 // Predecessor block may throw, so it has a side exit.230 if (blockMayThrow(Pred))231 return false;232 233 // BB dominates Pred, so if Pred runs, BB must run.234 // This is true when Pred is a loop latch.235 if (DT->dominates(BB, Pred))236 continue;237 238 for (const auto *Succ : successors(Pred))239 if (CheckedSuccessors.insert(Succ).second &&240 Succ != BB && !Predecessors.count(Succ))241 // By discharging conditions that are not executed on the 1st iteration,242 // we guarantee that *at least* on the first iteration all paths from243 // header that *may* execute will lead us to the block of interest. So244 // that if we had virtually peeled one iteration away, in this peeled245 // iteration the set of predecessors would contain only paths from246 // header to BB without any exiting edges that may execute.247 //248 // TODO: We only do it for exiting edges currently. We could use the249 // same function to skip some of the edges within the loop if we know250 // that they will not be taken on the 1st iteration.251 //252 // TODO: If we somehow know the number of iterations in loop, the same253 // check may be done for any arbitrary N-th iteration as long as N is254 // not greater than minimum number of iterations in this loop.255 if (CurLoop->contains(Succ) ||256 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))257 return false;258 }259 260 // All predecessors can only lead us to BB.261 return true;262}263 264/// Returns true if the instruction in a loop is guaranteed to execute at least265/// once.266bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,267 const DominatorTree *DT,268 const Loop *CurLoop) const {269 // If the instruction is in the header block for the loop (which is very270 // common), it is always guaranteed to dominate the exit blocks. Since this271 // is a common case, and can save some work, check it now.272 if (Inst.getParent() == CurLoop->getHeader())273 // If there's a throw in the header block, we can't guarantee we'll reach274 // Inst unless we can prove that Inst comes before the potential implicit275 // exit. At the moment, we use a (cheap) hack for the common case where276 // the instruction of interest is the first one in the block.277 return !HeaderMayThrow ||278 &*Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;279 280 // If there is a path from header to exit or latch that doesn't lead to our281 // instruction's block, return false.282 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);283}284 285bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,286 const DominatorTree *DT,287 const Loop *CurLoop) const {288 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&289 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);290}291 292bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,293 const Loop *CurLoop) const {294 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");295 296 // Fast path: there are no instructions before header.297 if (BB == CurLoop->getHeader())298 return true;299 300 // Collect all transitive predecessors of BB in the same loop. This set will301 // be a subset of the blocks within the loop.302 SmallPtrSet<const BasicBlock *, 4> Predecessors;303 collectTransitivePredecessors(CurLoop, BB, Predecessors);304 // Find if there any instruction in either predecessor that could write305 // to memory.306 for (const auto *Pred : Predecessors)307 if (MW.mayWriteToMemory(Pred))308 return false;309 return true;310}311 312bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,313 const Loop *CurLoop) const {314 auto *BB = I.getParent();315 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");316 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&317 doesNotWriteMemoryBefore(BB, CurLoop);318}319 320static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {321 // TODO: merge these two routines. For the moment, we display the best322 // result obtained by *either* implementation. This is a bit unfair since no323 // caller actually gets the full power at the moment.324 SimpleLoopSafetyInfo LSI;325 LSI.computeLoopSafetyInfo(L);326 return LSI.isGuaranteedToExecute(I, DT, L) ||327 isGuaranteedToExecuteForEveryIteration(&I, L);328}329 330namespace {331/// An assembly annotator class to print must execute information in332/// comments.333class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {334 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;335 336public:337 MustExecuteAnnotatedWriter(const Function &F,338 DominatorTree &DT, LoopInfo &LI) {339 for (const auto &I: instructions(F)) {340 Loop *L = LI.getLoopFor(I.getParent());341 while (L) {342 if (isMustExecuteIn(I, L, &DT)) {343 MustExec[&I].push_back(L);344 }345 L = L->getParentLoop();346 };347 }348 }349 MustExecuteAnnotatedWriter(const Module &M,350 DominatorTree &DT, LoopInfo &LI) {351 for (const auto &F : M)352 for (const auto &I: instructions(F)) {353 Loop *L = LI.getLoopFor(I.getParent());354 while (L) {355 if (isMustExecuteIn(I, L, &DT)) {356 MustExec[&I].push_back(L);357 }358 L = L->getParentLoop();359 };360 }361 }362 363 364 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {365 if (!MustExec.count(&V))366 return;367 368 const auto &Loops = MustExec.lookup(&V);369 const auto NumLoops = Loops.size();370 if (NumLoops > 1)371 OS << " ; (mustexec in " << NumLoops << " loops: ";372 else373 OS << " ; (mustexec in: ";374 375 ListSeparator LS;376 for (const Loop *L : Loops)377 OS << LS << L->getHeader()->getName();378 OS << ")";379 }380};381} // namespace382 383/// Return true if \p L might be an endless loop.384static bool maybeEndlessLoop(const Loop &L) {385 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))386 return false;387 // TODO: Actually try to prove it is not.388 // TODO: If maybeEndlessLoop is going to be expensive, cache it.389 return true;390}391 392bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {393 if (!LI)394 return false;395 using RPOTraversal = ReversePostOrderTraversal<const Function *>;396 RPOTraversal FuncRPOT(&F);397 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,398 const LoopInfo>(FuncRPOT, *LI);399}400 401/// Lookup \p Key in \p Map and return the result, potentially after402/// initializing the optional through \p Fn(\p args).403template <typename K, typename V, typename FnTy, typename... ArgsTy>404static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,405 FnTy &&Fn, ArgsTy &&...args) {406 std::optional<V> &OptVal = Map[Key];407 if (!OptVal)408 OptVal = Fn(std::forward<ArgsTy>(args)...);409 return *OptVal;410}411 412const BasicBlock *413MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {414 const LoopInfo *LI = LIGetter(*InitBB->getParent());415 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());416 417 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()418 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));419 420 const Function &F = *InitBB->getParent();421 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;422 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;423 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||424 (L && !maybeEndlessLoop(*L))) &&425 F.doesNotThrow();426 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")427 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")428 << "\n");429 430 // Determine the adjacent blocks in the given direction but exclude (self)431 // loops under certain circumstances.432 SmallVector<const BasicBlock *, 8> Worklist;433 for (const BasicBlock *SuccBB : successors(InitBB)) {434 bool IsLatch = SuccBB == HeaderBB;435 // Loop latches are ignored in forward propagation if the loop cannot be436 // endless and may not throw: control has to go somewhere.437 if (!WillReturnAndNoThrow || !IsLatch)438 Worklist.push_back(SuccBB);439 }440 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");441 442 // If there are no other adjacent blocks, there is no join point.443 if (Worklist.empty())444 return nullptr;445 446 // If there is one adjacent block, it is the join point.447 if (Worklist.size() == 1)448 return Worklist[0];449 450 // Try to determine a join block through the help of the post-dominance451 // tree. If no tree was provided, we perform simple pattern matching for one452 // block conditionals and one block loops only.453 const BasicBlock *JoinBB = nullptr;454 if (PDT)455 if (const auto *InitNode = PDT->getNode(InitBB))456 if (const auto *IDomNode = InitNode->getIDom())457 JoinBB = IDomNode->getBlock();458 459 if (!JoinBB && Worklist.size() == 2) {460 const BasicBlock *Succ0 = Worklist[0];461 const BasicBlock *Succ1 = Worklist[1];462 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();463 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();464 if (Succ0UniqueSucc == InitBB) {465 // InitBB -> Succ0 -> InitBB466 // InitBB -> Succ1 = JoinBB467 JoinBB = Succ1;468 } else if (Succ1UniqueSucc == InitBB) {469 // InitBB -> Succ1 -> InitBB470 // InitBB -> Succ0 = JoinBB471 JoinBB = Succ0;472 } else if (Succ0 == Succ1UniqueSucc) {473 // InitBB -> Succ0 = JoinBB474 // InitBB -> Succ1 -> Succ0 = JoinBB475 JoinBB = Succ0;476 } else if (Succ1 == Succ0UniqueSucc) {477 // InitBB -> Succ0 -> Succ1 = JoinBB478 // InitBB -> Succ1 = JoinBB479 JoinBB = Succ1;480 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {481 // InitBB -> Succ0 -> JoinBB482 // InitBB -> Succ1 -> JoinBB483 JoinBB = Succ0UniqueSucc;484 }485 }486 487 if (!JoinBB && L)488 JoinBB = L->getUniqueExitBlock();489 490 if (!JoinBB)491 return nullptr;492 493 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");494 495 // In forward direction we check if control will for sure reach JoinBB from496 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control497 // are: infinite loops and instructions that do not necessarily transfer498 // execution to their successor. To check for them we traverse the CFG from499 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.500 501 // If we know the function is "will-return" and "no-throw" there is no need502 // for futher checks.503 if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {504 505 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {506 return isGuaranteedToTransferExecutionToSuccessor(BB);507 };508 509 SmallPtrSet<const BasicBlock *, 16> Visited;510 while (!Worklist.empty()) {511 const BasicBlock *ToBB = Worklist.pop_back_val();512 if (ToBB == JoinBB)513 continue;514 515 // Make sure all loops in-between are finite.516 if (!Visited.insert(ToBB).second) {517 if (!F.hasFnAttribute(Attribute::WillReturn)) {518 if (!LI)519 return nullptr;520 521 bool MayContainIrreducibleControl = getOrCreateCachedOptional(522 &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);523 if (MayContainIrreducibleControl)524 return nullptr;525 526 const Loop *L = LI->getLoopFor(ToBB);527 if (L && maybeEndlessLoop(*L))528 return nullptr;529 }530 531 continue;532 }533 534 // Make sure the block has no instructions that could stop control535 // transfer.536 bool TransfersExecution = getOrCreateCachedOptional(537 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);538 if (!TransfersExecution)539 return nullptr;540 541 append_range(Worklist, successors(ToBB));542 }543 }544 545 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");546 return JoinBB;547}548const BasicBlock *549MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {550 const LoopInfo *LI = LIGetter(*InitBB->getParent());551 const DominatorTree *DT = DTGetter(*InitBB->getParent());552 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()553 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));554 555 // Try to determine a join block through the help of the dominance tree. If no556 // tree was provided, we perform simple pattern matching for one block557 // conditionals only.558 if (DT)559 if (const auto *InitNode = DT->getNode(InitBB))560 if (const auto *IDomNode = InitNode->getIDom())561 return IDomNode->getBlock();562 563 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;564 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;565 566 // Determine the predecessor blocks but ignore backedges.567 SmallVector<const BasicBlock *, 8> Worklist;568 for (const BasicBlock *PredBB : predecessors(InitBB)) {569 bool IsBackedge =570 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));571 // Loop backedges are ignored in backwards propagation: control has to come572 // from somewhere.573 if (!IsBackedge)574 Worklist.push_back(PredBB);575 }576 577 // If there are no other predecessor blocks, there is no join point.578 if (Worklist.empty())579 return nullptr;580 581 // If there is one predecessor block, it is the join point.582 if (Worklist.size() == 1)583 return Worklist[0];584 585 const BasicBlock *JoinBB = nullptr;586 if (Worklist.size() == 2) {587 const BasicBlock *Pred0 = Worklist[0];588 const BasicBlock *Pred1 = Worklist[1];589 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();590 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();591 if (Pred0 == Pred1UniquePred) {592 // InitBB <- Pred0 = JoinBB593 // InitBB <- Pred1 <- Pred0 = JoinBB594 JoinBB = Pred0;595 } else if (Pred1 == Pred0UniquePred) {596 // InitBB <- Pred0 <- Pred1 = JoinBB597 // InitBB <- Pred1 = JoinBB598 JoinBB = Pred1;599 } else if (Pred0UniquePred == Pred1UniquePred) {600 // InitBB <- Pred0 <- JoinBB601 // InitBB <- Pred1 <- JoinBB602 JoinBB = Pred0UniquePred;603 }604 }605 606 if (!JoinBB && L)607 JoinBB = L->getHeader();608 609 // In backwards direction there is no need to show termination of previous610 // instructions. If they do not terminate, the code afterward is dead, making611 // any information/transformation correct anyway.612 return JoinBB;613}614 615const Instruction *616MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(617 MustBeExecutedIterator &It, const Instruction *PP) {618 if (!PP)619 return PP;620 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");621 622 // If we explore only inside a given basic block we stop at terminators.623 if (!ExploreInterBlock && PP->isTerminator()) {624 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");625 return nullptr;626 }627 628 // If we do not traverse the call graph we check if we can make progress in629 // the current function. First, check if the instruction is guaranteed to630 // transfer execution to the successor.631 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);632 if (!TransfersExecution)633 return nullptr;634 635 // If this is not a terminator we know that there is a single instruction636 // after this one that is executed next if control is transfered. If not,637 // we can try to go back to a call site we entered earlier. If none exists, we638 // do not know any instruction that has to be executd next.639 if (!PP->isTerminator()) {640 const Instruction *NextPP = PP->getNextNode();641 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");642 return NextPP;643 }644 645 // Finally, we have to handle terminators, trivial ones first.646 assert(PP->isTerminator() && "Expected a terminator!");647 648 // A terminator without a successor is not handled yet.649 if (PP->getNumSuccessors() == 0) {650 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");651 return nullptr;652 }653 654 // A terminator with a single successor, we will continue at the beginning of655 // that one.656 if (PP->getNumSuccessors() == 1) {657 LLVM_DEBUG(658 dbgs() << "\tUnconditional terminator, continue with successor\n");659 return &PP->getSuccessor(0)->front();660 }661 662 // Multiple successors mean we need to find the join point where control flow663 // converges again. We use the findForwardJoinPoint helper function with664 // information about the function and helper analyses, if available.665 if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))666 return &JoinBB->front();667 668 LLVM_DEBUG(dbgs() << "\tNo join point found\n");669 return nullptr;670}671 672const Instruction *673MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(674 MustBeExecutedIterator &It, const Instruction *PP) {675 if (!PP)676 return PP;677 678 bool IsFirst = !(PP->getPrevNode());679 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP680 << (IsFirst ? " [IsFirst]" : "") << "\n");681 682 // If we explore only inside a given basic block we stop at the first683 // instruction.684 if (!ExploreInterBlock && IsFirst) {685 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");686 return nullptr;687 }688 689 // The block and function that contains the current position.690 const BasicBlock *PPBlock = PP->getParent();691 692 // If we are inside a block we know what instruction was executed before, the693 // previous one.694 if (!IsFirst) {695 const Instruction *PrevPP = PP->getPrevNode();696 LLVM_DEBUG(697 dbgs() << "\tIntermediate instruction, continue with previous\n");698 // We did not enter a callee so we simply return the previous instruction.699 return PrevPP;700 }701 702 // Finally, we have to handle the case where the program point is the first in703 // a block but not in the function. We use the findBackwardJoinPoint helper704 // function with information about the function and helper analyses, if705 // available.706 if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))707 return &JoinBB->back();708 709 LLVM_DEBUG(dbgs() << "\tNo join point found\n");710 return nullptr;711}712 713MustBeExecutedIterator::MustBeExecutedIterator(714 MustBeExecutedContextExplorer &Explorer, const Instruction *I)715 : Explorer(Explorer), CurInst(I) {716 reset(I);717}718 719void MustBeExecutedIterator::reset(const Instruction *I) {720 Visited.clear();721 resetInstruction(I);722}723 724void MustBeExecutedIterator::resetInstruction(const Instruction *I) {725 CurInst = I;726 Head = Tail = nullptr;727 Visited.insert({I, ExplorationDirection::FORWARD});728 Visited.insert({I, ExplorationDirection::BACKWARD});729 if (Explorer.ExploreCFGForward)730 Head = I;731 if (Explorer.ExploreCFGBackward)732 Tail = I;733}734 735const Instruction *MustBeExecutedIterator::advance() {736 assert(CurInst && "Cannot advance an end iterator!");737 Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);738 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)739 return Head;740 Head = nullptr;741 742 Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);743 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)744 return Tail;745 Tail = nullptr;746 return nullptr;747}748 749PreservedAnalyses MustExecutePrinterPass::run(Function &F,750 FunctionAnalysisManager &AM) {751 auto &LI = AM.getResult<LoopAnalysis>(F);752 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);753 754 MustExecuteAnnotatedWriter Writer(F, DT, LI);755 F.print(OS, &Writer);756 return PreservedAnalyses::all();757}758 759PreservedAnalyses760MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {761 FunctionAnalysisManager &FAM =762 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();763 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {764 return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));765 };766 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {767 return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));768 };769 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {770 return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));771 };772 773 MustBeExecutedContextExplorer Explorer(774 /* ExploreInterBlock */ true,775 /* ExploreCFGForward */ true,776 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);777 778 for (Function &F : M) {779 for (Instruction &I : instructions(F)) {780 OS << "-- Explore context of: " << I << "\n";781 for (const Instruction *CI : Explorer.range(&I))782 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";783 }784 }785 return PreservedAnalyses::all();786}787