1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
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
7 //===----------------------------------------------------------------------===//
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/Passes.h"
16 #include "llvm/Analysis/PostDominators.h"
17 #include "llvm/Analysis/ValueTracking.h"
18 #include "llvm/IR/AssemblyAnnotationWriter.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/InstIterator.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Support/FormattedStream.h"
25 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "must-execute"
31 const DenseMap<BasicBlock *, ColorVector> &
32 LoopSafetyInfo::getBlockColors() const {
36 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
37 ColorVector &ColorsForNewBlock = BlockColors[New];
38 ColorVector &ColorsForOldBlock = BlockColors[Old];
39 ColorsForNewBlock = ColorsForOldBlock;
42 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
44 return anyBlockMayThrow();
47 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
51 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
52 assert(CurLoop != nullptr && "CurLoop can't be null");
53 BasicBlock *Header = CurLoop->getHeader();
54 // Iterate over header and compute safety info.
55 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
56 MayThrow = HeaderMayThrow;
57 // Iterate over loop instructions and compute safety info.
58 // Skip header as it has been computed and stored in HeaderMayThrow.
59 // The first block in loopinfo.Blocks is guaranteed to be the header.
60 assert(Header == *CurLoop->getBlocks().begin() &&
61 "First block must be header");
62 for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
63 BBE = CurLoop->block_end();
64 (BB != BBE) && !MayThrow; ++BB)
65 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
67 computeBlockColors(CurLoop);
70 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
71 return ICF.hasICF(BB);
74 bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
78 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
79 assert(CurLoop != nullptr && "CurLoop can't be null");
83 // Figure out the fact that at least one block may throw.
84 for (const auto &BB : CurLoop->blocks())
85 if (ICF.hasICF(&*BB)) {
89 computeBlockColors(CurLoop);
92 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
93 const BasicBlock *BB) {
94 ICF.insertInstructionTo(Inst, BB);
95 MW.insertInstructionTo(Inst, BB);
98 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
99 ICF.removeInstruction(Inst);
100 MW.removeInstruction(Inst);
103 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
104 // Compute funclet colors if we might sink/hoist in a function with a funclet
105 // personality routine.
106 Function *Fn = CurLoop->getHeader()->getParent();
107 if (Fn->hasPersonalityFn())
108 if (Constant *PersonalityFn = Fn->getPersonalityFn())
109 if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
110 BlockColors = colorEHFunclets(*Fn);
113 /// Return true if we can prove that the given ExitBlock is not reached on the
114 /// first iteration of the given loop. That is, the backedge of the loop must
115 /// be executed before the ExitBlock is executed in any dynamic execution trace.
116 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
117 const DominatorTree *DT,
118 const Loop *CurLoop) {
119 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
121 // expect unique exits
123 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
124 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
125 if (!BI || !BI->isConditional())
127 // If condition is constant and false leads to ExitBlock then we always
128 // execute the true branch.
129 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
130 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
131 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
134 // todo: this would be a lot more powerful if we used scev, but all the
135 // plumbing is currently missing to pass a pointer in from the pass
136 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
137 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
138 auto *RHS = Cond->getOperand(1);
139 if (!LHS || LHS->getParent() != CurLoop->getHeader())
141 auto DL = ExitBlock->getModule()->getDataLayout();
142 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
143 auto *SimpleValOrNull = simplifyCmpInst(Cond->getPredicate(),
145 {DL, /*TLI*/ nullptr,
146 DT, /*AC*/ nullptr, BI});
147 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
150 if (ExitBlock == BI->getSuccessor(0))
151 return SimpleCst->isZeroValue();
152 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
153 return SimpleCst->isAllOnesValue();
156 /// Collect all blocks from \p CurLoop which lie on all possible paths from
157 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
158 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
159 static void collectTransitivePredecessors(
160 const Loop *CurLoop, const BasicBlock *BB,
161 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
162 assert(Predecessors.empty() && "Garbage in predecessors set?");
163 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
164 if (BB == CurLoop->getHeader())
166 SmallVector<const BasicBlock *, 4> WorkList;
167 for (const auto *Pred : predecessors(BB)) {
168 Predecessors.insert(Pred);
169 WorkList.push_back(Pred);
171 while (!WorkList.empty()) {
172 auto *Pred = WorkList.pop_back_val();
173 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
174 // We are not interested in backedges and we don't want to leave loop.
175 if (Pred == CurLoop->getHeader())
177 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
178 // blocks of this inner loop, even those that are always executed AFTER the
179 // BB. It may make our analysis more conservative than it could be, see test
180 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
181 // We can ignore backedge of all loops containing BB to get a sligtly more
182 // optimistic result.
183 for (const auto *PredPred : predecessors(Pred))
184 if (Predecessors.insert(PredPred).second)
185 WorkList.push_back(PredPred);
189 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
190 const BasicBlock *BB,
191 const DominatorTree *DT) const {
192 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
194 // Fast path: header is always reached once the loop is entered.
195 if (BB == CurLoop->getHeader())
198 // Collect all transitive predecessors of BB in the same loop. This set will
199 // be a subset of the blocks within the loop.
200 SmallPtrSet<const BasicBlock *, 4> Predecessors;
201 collectTransitivePredecessors(CurLoop, BB, Predecessors);
203 // Make sure that all successors of, all predecessors of BB which are not
204 // dominated by BB, are either:
206 // 2) Also predecessors of BB,
207 // 3) Exit blocks which are not taken on 1st iteration.
208 // Memoize blocks we've already checked.
209 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
210 for (const auto *Pred : Predecessors) {
211 // Predecessor block may throw, so it has a side exit.
212 if (blockMayThrow(Pred))
215 // BB dominates Pred, so if Pred runs, BB must run.
216 // This is true when Pred is a loop latch.
217 if (DT->dominates(BB, Pred))
220 for (const auto *Succ : successors(Pred))
221 if (CheckedSuccessors.insert(Succ).second &&
222 Succ != BB && !Predecessors.count(Succ))
223 // By discharging conditions that are not executed on the 1st iteration,
224 // we guarantee that *at least* on the first iteration all paths from
225 // header that *may* execute will lead us to the block of interest. So
226 // that if we had virtually peeled one iteration away, in this peeled
227 // iteration the set of predecessors would contain only paths from
228 // header to BB without any exiting edges that may execute.
230 // TODO: We only do it for exiting edges currently. We could use the
231 // same function to skip some of the edges within the loop if we know
232 // that they will not be taken on the 1st iteration.
234 // TODO: If we somehow know the number of iterations in loop, the same
235 // check may be done for any arbitrary N-th iteration as long as N is
236 // not greater than minimum number of iterations in this loop.
237 if (CurLoop->contains(Succ) ||
238 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
242 // All predecessors can only lead us to BB.
246 /// Returns true if the instruction in a loop is guaranteed to execute at least
248 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
249 const DominatorTree *DT,
250 const Loop *CurLoop) const {
251 // If the instruction is in the header block for the loop (which is very
252 // common), it is always guaranteed to dominate the exit blocks. Since this
253 // is a common case, and can save some work, check it now.
254 if (Inst.getParent() == CurLoop->getHeader())
255 // If there's a throw in the header block, we can't guarantee we'll reach
256 // Inst unless we can prove that Inst comes before the potential implicit
257 // exit. At the moment, we use a (cheap) hack for the common case where
258 // the instruction of interest is the first one in the block.
259 return !HeaderMayThrow ||
260 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
262 // If there is a path from header to exit or latch that doesn't lead to our
263 // instruction's block, return false.
264 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
267 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
268 const DominatorTree *DT,
269 const Loop *CurLoop) const {
270 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
271 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
274 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
275 const Loop *CurLoop) const {
276 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
278 // Fast path: there are no instructions before header.
279 if (BB == CurLoop->getHeader())
282 // Collect all transitive predecessors of BB in the same loop. This set will
283 // be a subset of the blocks within the loop.
284 SmallPtrSet<const BasicBlock *, 4> Predecessors;
285 collectTransitivePredecessors(CurLoop, BB, Predecessors);
286 // Find if there any instruction in either predecessor that could write
288 for (const auto *Pred : Predecessors)
289 if (MW.mayWriteToMemory(Pred))
294 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
295 const Loop *CurLoop) const {
296 auto *BB = I.getParent();
297 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
298 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
299 doesNotWriteMemoryBefore(BB, CurLoop);
303 struct MustExecutePrinter : public FunctionPass {
305 static char ID; // Pass identification, replacement for typeid
306 MustExecutePrinter() : FunctionPass(ID) {
307 initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
309 void getAnalysisUsage(AnalysisUsage &AU) const override {
310 AU.setPreservesAll();
311 AU.addRequired<DominatorTreeWrapperPass>();
312 AU.addRequired<LoopInfoWrapperPass>();
314 bool runOnFunction(Function &F) override;
316 struct MustBeExecutedContextPrinter : public ModulePass {
319 MustBeExecutedContextPrinter() : ModulePass(ID) {
320 initializeMustBeExecutedContextPrinterPass(
321 *PassRegistry::getPassRegistry());
323 void getAnalysisUsage(AnalysisUsage &AU) const override {
324 AU.setPreservesAll();
326 bool runOnModule(Module &M) override;
330 char MustExecutePrinter::ID = 0;
331 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
332 "Instructions which execute on loop entry", false, true)
333 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
334 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
335 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
336 "Instructions which execute on loop entry", false, true)
338 FunctionPass *llvm::createMustExecutePrinter() {
339 return new MustExecutePrinter();
342 char MustBeExecutedContextPrinter::ID = 0;
343 INITIALIZE_PASS_BEGIN(MustBeExecutedContextPrinter,
344 "print-must-be-executed-contexts",
345 "print the must-be-executed-context for all instructions",
347 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
348 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
349 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
350 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
351 "print-must-be-executed-contexts",
352 "print the must-be-executed-context for all instructions",
355 ModulePass *llvm::createMustBeExecutedContextPrinter() {
356 return new MustBeExecutedContextPrinter();
359 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
360 // We provide non-PM analysis here because the old PM doesn't like to query
361 // function passes from a module pass.
362 SmallVector<std::unique_ptr<PostDominatorTree>, 8> PDTs;
363 SmallVector<std::unique_ptr<DominatorTree>, 8> DTs;
364 SmallVector<std::unique_ptr<LoopInfo>, 8> LIs;
366 GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
367 DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
368 LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
369 return LIs.back().get();
371 GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
372 DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
373 return DTs.back().get();
375 GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
377 std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
378 return PDTs.back().get();
380 MustBeExecutedContextExplorer Explorer(
381 /* ExploreInterBlock */ true,
382 /* ExploreCFGForward */ true,
383 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
385 for (Function &F : M) {
386 for (Instruction &I : instructions(F)) {
387 dbgs() << "-- Explore context of: " << I << "\n";
388 for (const Instruction *CI : Explorer.range(&I))
389 dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
397 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
398 // TODO: merge these two routines. For the moment, we display the best
399 // result obtained by *either* implementation. This is a bit unfair since no
400 // caller actually gets the full power at the moment.
401 SimpleLoopSafetyInfo LSI;
402 LSI.computeLoopSafetyInfo(L);
403 return LSI.isGuaranteedToExecute(I, DT, L) ||
404 isGuaranteedToExecuteForEveryIteration(&I, L);
408 /// An assembly annotator class to print must execute information in
410 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
411 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
414 MustExecuteAnnotatedWriter(const Function &F,
415 DominatorTree &DT, LoopInfo &LI) {
416 for (const auto &I: instructions(F)) {
417 Loop *L = LI.getLoopFor(I.getParent());
419 if (isMustExecuteIn(I, L, &DT)) {
420 MustExec[&I].push_back(L);
422 L = L->getParentLoop();
426 MustExecuteAnnotatedWriter(const Module &M,
427 DominatorTree &DT, LoopInfo &LI) {
428 for (const auto &F : M)
429 for (const auto &I: instructions(F)) {
430 Loop *L = LI.getLoopFor(I.getParent());
432 if (isMustExecuteIn(I, L, &DT)) {
433 MustExec[&I].push_back(L);
435 L = L->getParentLoop();
441 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
442 if (!MustExec.count(&V))
445 const auto &Loops = MustExec.lookup(&V);
446 const auto NumLoops = Loops.size();
448 OS << " ; (mustexec in " << NumLoops << " loops: ";
450 OS << " ; (mustexec in: ";
453 for (const Loop *L : Loops)
454 OS << LS << L->getHeader()->getName();
460 bool MustExecutePrinter::runOnFunction(Function &F) {
461 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
462 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
464 MustExecuteAnnotatedWriter Writer(F, DT, LI);
465 F.print(dbgs(), &Writer);
470 /// Return true if \p L might be an endless loop.
471 static bool maybeEndlessLoop(const Loop &L) {
472 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
474 // TODO: Actually try to prove it is not.
475 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
479 bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
482 using RPOTraversal = ReversePostOrderTraversal<const Function *>;
483 RPOTraversal FuncRPOT(&F);
484 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
485 const LoopInfo>(FuncRPOT, *LI);
488 /// Lookup \p Key in \p Map and return the result, potentially after
489 /// initializing the optional through \p Fn(\p args).
490 template <typename K, typename V, typename FnTy, typename... ArgsTy>
491 static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map,
492 FnTy &&Fn, ArgsTy&&... args) {
493 Optional<V> &OptVal = Map[Key];
495 OptVal = Fn(std::forward<ArgsTy>(args)...);
496 return OptVal.value();
500 MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
501 const LoopInfo *LI = LIGetter(*InitBB->getParent());
502 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
504 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
505 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
507 const Function &F = *InitBB->getParent();
508 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
509 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
510 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
511 (L && !maybeEndlessLoop(*L))) &&
513 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
514 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
517 // Determine the adjacent blocks in the given direction but exclude (self)
518 // loops under certain circumstances.
519 SmallVector<const BasicBlock *, 8> Worklist;
520 for (const BasicBlock *SuccBB : successors(InitBB)) {
521 bool IsLatch = SuccBB == HeaderBB;
522 // Loop latches are ignored in forward propagation if the loop cannot be
523 // endless and may not throw: control has to go somewhere.
524 if (!WillReturnAndNoThrow || !IsLatch)
525 Worklist.push_back(SuccBB);
527 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
529 // If there are no other adjacent blocks, there is no join point.
530 if (Worklist.empty())
533 // If there is one adjacent block, it is the join point.
534 if (Worklist.size() == 1)
537 // Try to determine a join block through the help of the post-dominance
538 // tree. If no tree was provided, we perform simple pattern matching for one
539 // block conditionals and one block loops only.
540 const BasicBlock *JoinBB = nullptr;
542 if (const auto *InitNode = PDT->getNode(InitBB))
543 if (const auto *IDomNode = InitNode->getIDom())
544 JoinBB = IDomNode->getBlock();
546 if (!JoinBB && Worklist.size() == 2) {
547 const BasicBlock *Succ0 = Worklist[0];
548 const BasicBlock *Succ1 = Worklist[1];
549 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
550 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
551 if (Succ0UniqueSucc == InitBB) {
552 // InitBB -> Succ0 -> InitBB
553 // InitBB -> Succ1 = JoinBB
555 } else if (Succ1UniqueSucc == InitBB) {
556 // InitBB -> Succ1 -> InitBB
557 // InitBB -> Succ0 = JoinBB
559 } else if (Succ0 == Succ1UniqueSucc) {
560 // InitBB -> Succ0 = JoinBB
561 // InitBB -> Succ1 -> Succ0 = JoinBB
563 } else if (Succ1 == Succ0UniqueSucc) {
564 // InitBB -> Succ0 -> Succ1 = JoinBB
565 // InitBB -> Succ1 = JoinBB
567 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
568 // InitBB -> Succ0 -> JoinBB
569 // InitBB -> Succ1 -> JoinBB
570 JoinBB = Succ0UniqueSucc;
575 JoinBB = L->getUniqueExitBlock();
580 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
582 // In forward direction we check if control will for sure reach JoinBB from
583 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
584 // are: infinite loops and instructions that do not necessarily transfer
585 // execution to their successor. To check for them we traverse the CFG from
586 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
588 // If we know the function is "will-return" and "no-throw" there is no need
589 // for futher checks.
590 if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
592 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
593 return isGuaranteedToTransferExecutionToSuccessor(BB);
596 SmallPtrSet<const BasicBlock *, 16> Visited;
597 while (!Worklist.empty()) {
598 const BasicBlock *ToBB = Worklist.pop_back_val();
602 // Make sure all loops in-between are finite.
603 if (!Visited.insert(ToBB).second) {
604 if (!F.hasFnAttribute(Attribute::WillReturn)) {
608 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
609 &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
610 if (MayContainIrreducibleControl)
613 const Loop *L = LI->getLoopFor(ToBB);
614 if (L && maybeEndlessLoop(*L))
621 // Make sure the block has no instructions that could stop control
623 bool TransfersExecution = getOrCreateCachedOptional(
624 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
625 if (!TransfersExecution)
628 append_range(Worklist, successors(ToBB));
632 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
636 MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
637 const LoopInfo *LI = LIGetter(*InitBB->getParent());
638 const DominatorTree *DT = DTGetter(*InitBB->getParent());
639 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
640 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
642 // Try to determine a join block through the help of the dominance tree. If no
643 // tree was provided, we perform simple pattern matching for one block
644 // conditionals only.
646 if (const auto *InitNode = DT->getNode(InitBB))
647 if (const auto *IDomNode = InitNode->getIDom())
648 return IDomNode->getBlock();
650 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
651 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
653 // Determine the predecessor blocks but ignore backedges.
654 SmallVector<const BasicBlock *, 8> Worklist;
655 for (const BasicBlock *PredBB : predecessors(InitBB)) {
657 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
658 // Loop backedges are ignored in backwards propagation: control has to come
661 Worklist.push_back(PredBB);
664 // If there are no other predecessor blocks, there is no join point.
665 if (Worklist.empty())
668 // If there is one predecessor block, it is the join point.
669 if (Worklist.size() == 1)
672 const BasicBlock *JoinBB = nullptr;
673 if (Worklist.size() == 2) {
674 const BasicBlock *Pred0 = Worklist[0];
675 const BasicBlock *Pred1 = Worklist[1];
676 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
677 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
678 if (Pred0 == Pred1UniquePred) {
679 // InitBB <- Pred0 = JoinBB
680 // InitBB <- Pred1 <- Pred0 = JoinBB
682 } else if (Pred1 == Pred0UniquePred) {
683 // InitBB <- Pred0 <- Pred1 = JoinBB
684 // InitBB <- Pred1 = JoinBB
686 } else if (Pred0UniquePred == Pred1UniquePred) {
687 // InitBB <- Pred0 <- JoinBB
688 // InitBB <- Pred1 <- JoinBB
689 JoinBB = Pred0UniquePred;
694 JoinBB = L->getHeader();
696 // In backwards direction there is no need to show termination of previous
697 // instructions. If they do not terminate, the code afterward is dead, making
698 // any information/transformation correct anyway.
703 MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
704 MustBeExecutedIterator &It, const Instruction *PP) {
707 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
709 // If we explore only inside a given basic block we stop at terminators.
710 if (!ExploreInterBlock && PP->isTerminator()) {
711 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
715 // If we do not traverse the call graph we check if we can make progress in
716 // the current function. First, check if the instruction is guaranteed to
717 // transfer execution to the successor.
718 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
719 if (!TransfersExecution)
722 // If this is not a terminator we know that there is a single instruction
723 // after this one that is executed next if control is transfered. If not,
724 // we can try to go back to a call site we entered earlier. If none exists, we
725 // do not know any instruction that has to be executd next.
726 if (!PP->isTerminator()) {
727 const Instruction *NextPP = PP->getNextNode();
728 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
732 // Finally, we have to handle terminators, trivial ones first.
733 assert(PP->isTerminator() && "Expected a terminator!");
735 // A terminator without a successor is not handled yet.
736 if (PP->getNumSuccessors() == 0) {
737 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
741 // A terminator with a single successor, we will continue at the beginning of
743 if (PP->getNumSuccessors() == 1) {
745 dbgs() << "\tUnconditional terminator, continue with successor\n");
746 return &PP->getSuccessor(0)->front();
749 // Multiple successors mean we need to find the join point where control flow
750 // converges again. We use the findForwardJoinPoint helper function with
751 // information about the function and helper analyses, if available.
752 if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
753 return &JoinBB->front();
755 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
760 MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
761 MustBeExecutedIterator &It, const Instruction *PP) {
765 bool IsFirst = !(PP->getPrevNode());
766 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
767 << (IsFirst ? " [IsFirst]" : "") << "\n");
769 // If we explore only inside a given basic block we stop at the first
771 if (!ExploreInterBlock && IsFirst) {
772 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
776 // The block and function that contains the current position.
777 const BasicBlock *PPBlock = PP->getParent();
779 // If we are inside a block we know what instruction was executed before, the
782 const Instruction *PrevPP = PP->getPrevNode();
784 dbgs() << "\tIntermediate instruction, continue with previous\n");
785 // We did not enter a callee so we simply return the previous instruction.
789 // Finally, we have to handle the case where the program point is the first in
790 // a block but not in the function. We use the findBackwardJoinPoint helper
791 // function with information about the function and helper analyses, if
793 if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
794 return &JoinBB->back();
796 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
800 MustBeExecutedIterator::MustBeExecutedIterator(
801 MustBeExecutedContextExplorer &Explorer, const Instruction *I)
802 : Explorer(Explorer), CurInst(I) {
806 void MustBeExecutedIterator::reset(const Instruction *I) {
811 void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
813 Head = Tail = nullptr;
814 Visited.insert({I, ExplorationDirection::FORWARD});
815 Visited.insert({I, ExplorationDirection::BACKWARD});
816 if (Explorer.ExploreCFGForward)
818 if (Explorer.ExploreCFGBackward)
822 const Instruction *MustBeExecutedIterator::advance() {
823 assert(CurInst && "Cannot advance an end iterator!");
824 Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
825 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
829 Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
830 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
836 PreservedAnalyses MustExecutePrinterPass::run(Function &F,
837 FunctionAnalysisManager &AM) {
838 auto &LI = AM.getResult<LoopAnalysis>(F);
839 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
841 MustExecuteAnnotatedWriter Writer(F, DT, LI);
842 F.print(OS, &Writer);
843 return PreservedAnalyses::all();
847 MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
848 FunctionAnalysisManager &FAM =
849 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
850 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
851 return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
853 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
854 return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
856 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
857 return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
860 MustBeExecutedContextExplorer Explorer(
861 /* ExploreInterBlock */ true,
862 /* ExploreCFGForward */ true,
863 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
865 for (Function &F : M) {
866 for (Instruction &I : instructions(F)) {
867 OS << "-- Explore context of: " << I << "\n";
868 for (const Instruction *CI : Explorer.range(&I))
869 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
872 return PreservedAnalyses::all();