LLVM 17.0.0git
MustExecute.cpp
Go to the documentation of this file.
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
12#include "llvm/Analysis/CFG.h"
19#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PassManager.h"
26
27using namespace llvm;
28
29#define DEBUG_TYPE "must-execute"
30
33 return BlockColors;
34}
35
37 ColorVector &ColorsForNewBlock = BlockColors[New];
38 ColorVector &ColorsForOldBlock = BlockColors[Old];
39 ColorsForNewBlock = ColorsForOldBlock;
40}
41
43 (void)BB;
44 return anyBlockMayThrow();
45}
46
48 return MayThrow;
49}
50
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 (const BasicBlock *BB : llvm::drop_begin(CurLoop->blocks())) {
64 if (MayThrow)
65 break;
66 }
67
68 computeBlockColors(CurLoop);
69}
70
72 return ICF.hasICF(BB);
73}
74
76 return MayThrow;
77}
78
80 assert(CurLoop != nullptr && "CurLoop can't be null");
81 ICF.clear();
82 MW.clear();
83 MayThrow = false;
84 // Figure out the fact that at least one block may throw.
85 for (const auto &BB : CurLoop->blocks())
86 if (ICF.hasICF(&*BB)) {
87 MayThrow = true;
88 break;
89 }
90 computeBlockColors(CurLoop);
91}
92
94 const BasicBlock *BB) {
95 ICF.insertInstructionTo(Inst, BB);
96 MW.insertInstructionTo(Inst, BB);
97}
98
100 ICF.removeInstruction(Inst);
101 MW.removeInstruction(Inst);
102}
103
105 // Compute funclet colors if we might sink/hoist in a function with a funclet
106 // personality routine.
107 Function *Fn = CurLoop->getHeader()->getParent();
108 if (Fn->hasPersonalityFn())
109 if (Constant *PersonalityFn = Fn->getPersonalityFn())
111 BlockColors = colorEHFunclets(*Fn);
112}
113
114/// Return true if we can prove that the given ExitBlock is not reached on the
115/// first iteration of the given loop. That is, the backedge of the loop must
116/// be executed before the ExitBlock is executed in any dynamic execution trace.
117static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
118 const DominatorTree *DT,
119 const Loop *CurLoop) {
120 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
121 if (!CondExitBlock)
122 // expect unique exits
123 return false;
124 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
125 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
126 if (!BI || !BI->isConditional())
127 return false;
128 // If condition is constant and false leads to ExitBlock then we always
129 // execute the true branch.
130 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
131 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
132 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
133 if (!Cond)
134 return false;
135 // todo: this would be a lot more powerful if we used scev, but all the
136 // plumbing is currently missing to pass a pointer in from the pass
137 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
138 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
139 auto *RHS = Cond->getOperand(1);
140 if (!LHS || LHS->getParent() != CurLoop->getHeader())
141 return false;
142 auto DL = ExitBlock->getModule()->getDataLayout();
143 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
144 auto *SimpleValOrNull = simplifyCmpInst(Cond->getPredicate(),
145 IVStart, RHS,
146 {DL, /*TLI*/ nullptr,
147 DT, /*AC*/ nullptr, BI});
148 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
149 if (!SimpleCst)
150 return false;
151 if (ExitBlock == BI->getSuccessor(0))
152 return SimpleCst->isZeroValue();
153 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
154 return SimpleCst->isAllOnesValue();
155}
156
157/// Collect all blocks from \p CurLoop which lie on all possible paths from
158/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
159/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
161 const Loop *CurLoop, const BasicBlock *BB,
163 assert(Predecessors.empty() && "Garbage in predecessors set?");
164 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
165 if (BB == CurLoop->getHeader())
166 return;
168 for (const auto *Pred : predecessors(BB)) {
169 Predecessors.insert(Pred);
170 WorkList.push_back(Pred);
171 }
172 while (!WorkList.empty()) {
173 auto *Pred = WorkList.pop_back_val();
174 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
175 // We are not interested in backedges and we don't want to leave loop.
176 if (Pred == CurLoop->getHeader())
177 continue;
178 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
179 // blocks of this inner loop, even those that are always executed AFTER the
180 // BB. It may make our analysis more conservative than it could be, see test
181 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
182 // We can ignore backedge of all loops containing BB to get a sligtly more
183 // optimistic result.
184 for (const auto *PredPred : predecessors(Pred))
185 if (Predecessors.insert(PredPred).second)
186 WorkList.push_back(PredPred);
187 }
188}
189
191 const BasicBlock *BB,
192 const DominatorTree *DT) const {
193 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
194
195 // Fast path: header is always reached once the loop is entered.
196 if (BB == CurLoop->getHeader())
197 return true;
198
199 // Collect all transitive predecessors of BB in the same loop. This set will
200 // be a subset of the blocks within the loop.
202 collectTransitivePredecessors(CurLoop, BB, Predecessors);
203
204 // Bail out if a latch block is part of the predecessor set. In this case
205 // we may take the backedge to the header and not execute other latch
206 // successors.
207 for (const BasicBlock *Pred : predecessors(CurLoop->getHeader()))
208 // Predecessors only contains loop blocks, so we don't have to worry about
209 // preheader predecessors here.
210 if (Predecessors.contains(Pred))
211 return false;
212
213 // Make sure that all successors of, all predecessors of BB which are not
214 // dominated by BB, are either:
215 // 1) BB,
216 // 2) Also predecessors of BB,
217 // 3) Exit blocks which are not taken on 1st iteration.
218 // Memoize blocks we've already checked.
219 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
220 for (const auto *Pred : Predecessors) {
221 // Predecessor block may throw, so it has a side exit.
222 if (blockMayThrow(Pred))
223 return false;
224
225 // BB dominates Pred, so if Pred runs, BB must run.
226 // This is true when Pred is a loop latch.
227 if (DT->dominates(BB, Pred))
228 continue;
229
230 for (const auto *Succ : successors(Pred))
231 if (CheckedSuccessors.insert(Succ).second &&
232 Succ != BB && !Predecessors.count(Succ))
233 // By discharging conditions that are not executed on the 1st iteration,
234 // we guarantee that *at least* on the first iteration all paths from
235 // header that *may* execute will lead us to the block of interest. So
236 // that if we had virtually peeled one iteration away, in this peeled
237 // iteration the set of predecessors would contain only paths from
238 // header to BB without any exiting edges that may execute.
239 //
240 // TODO: We only do it for exiting edges currently. We could use the
241 // same function to skip some of the edges within the loop if we know
242 // that they will not be taken on the 1st iteration.
243 //
244 // TODO: If we somehow know the number of iterations in loop, the same
245 // check may be done for any arbitrary N-th iteration as long as N is
246 // not greater than minimum number of iterations in this loop.
247 if (CurLoop->contains(Succ) ||
248 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
249 return false;
250 }
251
252 // All predecessors can only lead us to BB.
253 return true;
254}
255
256/// Returns true if the instruction in a loop is guaranteed to execute at least
257/// once.
259 const DominatorTree *DT,
260 const Loop *CurLoop) const {
261 // If the instruction is in the header block for the loop (which is very
262 // common), it is always guaranteed to dominate the exit blocks. Since this
263 // is a common case, and can save some work, check it now.
264 if (Inst.getParent() == CurLoop->getHeader())
265 // If there's a throw in the header block, we can't guarantee we'll reach
266 // Inst unless we can prove that Inst comes before the potential implicit
267 // exit. At the moment, we use a (cheap) hack for the common case where
268 // the instruction of interest is the first one in the block.
269 return !HeaderMayThrow ||
270 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
271
272 // If there is a path from header to exit or latch that doesn't lead to our
273 // instruction's block, return false.
274 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
275}
276
278 const DominatorTree *DT,
279 const Loop *CurLoop) const {
280 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
281 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
282}
283
285 const Loop *CurLoop) const {
286 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
287
288 // Fast path: there are no instructions before header.
289 if (BB == CurLoop->getHeader())
290 return true;
291
292 // Collect all transitive predecessors of BB in the same loop. This set will
293 // be a subset of the blocks within the loop.
295 collectTransitivePredecessors(CurLoop, BB, Predecessors);
296 // Find if there any instruction in either predecessor that could write
297 // to memory.
298 for (const auto *Pred : Predecessors)
299 if (MW.mayWriteToMemory(Pred))
300 return false;
301 return true;
302}
303
305 const Loop *CurLoop) const {
306 auto *BB = I.getParent();
307 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
309 doesNotWriteMemoryBefore(BB, CurLoop);
310}
311
312namespace {
313struct MustExecutePrinter : public FunctionPass {
314
315 static char ID; // Pass identification, replacement for typeid
316 MustExecutePrinter() : FunctionPass(ID) {
318 }
319 void getAnalysisUsage(AnalysisUsage &AU) const override {
320 AU.setPreservesAll();
323 }
324 bool runOnFunction(Function &F) override;
325};
326struct MustBeExecutedContextPrinter : public ModulePass {
327 static char ID;
328
329 MustBeExecutedContextPrinter() : ModulePass(ID) {
332 }
333 void getAnalysisUsage(AnalysisUsage &AU) const override {
334 AU.setPreservesAll();
335 }
336 bool runOnModule(Module &M) override;
337};
338}
339
340char MustExecutePrinter::ID = 0;
341INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
342 "Instructions which execute on loop entry", false, true)
346 "Instructions which execute on loop entry", false, true)
347
349 return new MustExecutePrinter();
350}
351
352char MustBeExecutedContextPrinter::ID = 0;
353INITIALIZE_PASS_BEGIN(MustBeExecutedContextPrinter,
354 "print-must-be-executed-contexts",
355 "print the must-be-executed-context for all instructions",
356 false, true)
360INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
361 "print-must-be-executed-contexts",
362 "print the must-be-executed-context for all instructions",
363 false, true)
364
366 return new MustBeExecutedContextPrinter();
367}
368
369bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
370 // We provide non-PM analysis here because the old PM doesn't like to query
371 // function passes from a module pass.
375
376 GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
377 DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
378 LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
379 return LIs.back().get();
380 };
381 GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
382 DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
383 return DTs.back().get();
384 };
385 GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
386 PDTs.push_back(
387 std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
388 return PDTs.back().get();
389 };
391 /* ExploreInterBlock */ true,
392 /* ExploreCFGForward */ true,
393 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
394
395 for (Function &F : M) {
396 for (Instruction &I : instructions(F)) {
397 dbgs() << "-- Explore context of: " << I << "\n";
398 for (const Instruction *CI : Explorer.range(&I))
399 dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
400 << "\n";
401 }
402 }
403
404 return false;
405}
406
407static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
408 // TODO: merge these two routines. For the moment, we display the best
409 // result obtained by *either* implementation. This is a bit unfair since no
410 // caller actually gets the full power at the moment.
413 return LSI.isGuaranteedToExecute(I, DT, L) ||
415}
416
417namespace {
418/// An assembly annotator class to print must execute information in
419/// comments.
420class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
422
423public:
424 MustExecuteAnnotatedWriter(const Function &F,
425 DominatorTree &DT, LoopInfo &LI) {
426 for (const auto &I: instructions(F)) {
427 Loop *L = LI.getLoopFor(I.getParent());
428 while (L) {
429 if (isMustExecuteIn(I, L, &DT)) {
430 MustExec[&I].push_back(L);
431 }
432 L = L->getParentLoop();
433 };
434 }
435 }
436 MustExecuteAnnotatedWriter(const Module &M,
437 DominatorTree &DT, LoopInfo &LI) {
438 for (const auto &F : M)
439 for (const auto &I: instructions(F)) {
440 Loop *L = LI.getLoopFor(I.getParent());
441 while (L) {
442 if (isMustExecuteIn(I, L, &DT)) {
443 MustExec[&I].push_back(L);
444 }
445 L = L->getParentLoop();
446 };
447 }
448 }
449
450
451 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
452 if (!MustExec.count(&V))
453 return;
454
455 const auto &Loops = MustExec.lookup(&V);
456 const auto NumLoops = Loops.size();
457 if (NumLoops > 1)
458 OS << " ; (mustexec in " << NumLoops << " loops: ";
459 else
460 OS << " ; (mustexec in: ";
461
462 ListSeparator LS;
463 for (const Loop *L : Loops)
464 OS << LS << L->getHeader()->getName();
465 OS << ")";
466 }
467};
468} // namespace
469
470bool MustExecutePrinter::runOnFunction(Function &F) {
471 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
472 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
473
474 MustExecuteAnnotatedWriter Writer(F, DT, LI);
475 F.print(dbgs(), &Writer);
476
477 return false;
478}
479
480/// Return true if \p L might be an endless loop.
481static bool maybeEndlessLoop(const Loop &L) {
482 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
483 return false;
484 // TODO: Actually try to prove it is not.
485 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
486 return true;
487}
488
490 if (!LI)
491 return false;
493 RPOTraversal FuncRPOT(&F);
494 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
495 const LoopInfo>(FuncRPOT, *LI);
496}
497
498/// Lookup \p Key in \p Map and return the result, potentially after
499/// initializing the optional through \p Fn(\p args).
500template <typename K, typename V, typename FnTy, typename... ArgsTy>
501static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
502 FnTy &&Fn, ArgsTy &&...args) {
503 std::optional<V> &OptVal = Map[Key];
504 if (!OptVal)
505 OptVal = Fn(std::forward<ArgsTy>(args)...);
506 return *OptVal;
507}
508
509const BasicBlock *
511 const LoopInfo *LI = LIGetter(*InitBB->getParent());
512 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
513
514 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
515 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
516
517 const Function &F = *InitBB->getParent();
518 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
519 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
520 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
521 (L && !maybeEndlessLoop(*L))) &&
522 F.doesNotThrow();
523 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
524 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
525 << "\n");
526
527 // Determine the adjacent blocks in the given direction but exclude (self)
528 // loops under certain circumstances.
530 for (const BasicBlock *SuccBB : successors(InitBB)) {
531 bool IsLatch = SuccBB == HeaderBB;
532 // Loop latches are ignored in forward propagation if the loop cannot be
533 // endless and may not throw: control has to go somewhere.
534 if (!WillReturnAndNoThrow || !IsLatch)
535 Worklist.push_back(SuccBB);
536 }
537 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
538
539 // If there are no other adjacent blocks, there is no join point.
540 if (Worklist.empty())
541 return nullptr;
542
543 // If there is one adjacent block, it is the join point.
544 if (Worklist.size() == 1)
545 return Worklist[0];
546
547 // Try to determine a join block through the help of the post-dominance
548 // tree. If no tree was provided, we perform simple pattern matching for one
549 // block conditionals and one block loops only.
550 const BasicBlock *JoinBB = nullptr;
551 if (PDT)
552 if (const auto *InitNode = PDT->getNode(InitBB))
553 if (const auto *IDomNode = InitNode->getIDom())
554 JoinBB = IDomNode->getBlock();
555
556 if (!JoinBB && Worklist.size() == 2) {
557 const BasicBlock *Succ0 = Worklist[0];
558 const BasicBlock *Succ1 = Worklist[1];
559 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
560 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
561 if (Succ0UniqueSucc == InitBB) {
562 // InitBB -> Succ0 -> InitBB
563 // InitBB -> Succ1 = JoinBB
564 JoinBB = Succ1;
565 } else if (Succ1UniqueSucc == InitBB) {
566 // InitBB -> Succ1 -> InitBB
567 // InitBB -> Succ0 = JoinBB
568 JoinBB = Succ0;
569 } else if (Succ0 == Succ1UniqueSucc) {
570 // InitBB -> Succ0 = JoinBB
571 // InitBB -> Succ1 -> Succ0 = JoinBB
572 JoinBB = Succ0;
573 } else if (Succ1 == Succ0UniqueSucc) {
574 // InitBB -> Succ0 -> Succ1 = JoinBB
575 // InitBB -> Succ1 = JoinBB
576 JoinBB = Succ1;
577 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
578 // InitBB -> Succ0 -> JoinBB
579 // InitBB -> Succ1 -> JoinBB
580 JoinBB = Succ0UniqueSucc;
581 }
582 }
583
584 if (!JoinBB && L)
585 JoinBB = L->getUniqueExitBlock();
586
587 if (!JoinBB)
588 return nullptr;
589
590 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
591
592 // In forward direction we check if control will for sure reach JoinBB from
593 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
594 // are: infinite loops and instructions that do not necessarily transfer
595 // execution to their successor. To check for them we traverse the CFG from
596 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
597
598 // If we know the function is "will-return" and "no-throw" there is no need
599 // for futher checks.
600 if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
601
602 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
604 };
605
607 while (!Worklist.empty()) {
608 const BasicBlock *ToBB = Worklist.pop_back_val();
609 if (ToBB == JoinBB)
610 continue;
611
612 // Make sure all loops in-between are finite.
613 if (!Visited.insert(ToBB).second) {
614 if (!F.hasFnAttribute(Attribute::WillReturn)) {
615 if (!LI)
616 return nullptr;
617
618 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
619 &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
620 if (MayContainIrreducibleControl)
621 return nullptr;
622
623 const Loop *L = LI->getLoopFor(ToBB);
624 if (L && maybeEndlessLoop(*L))
625 return nullptr;
626 }
627
628 continue;
629 }
630
631 // Make sure the block has no instructions that could stop control
632 // transfer.
633 bool TransfersExecution = getOrCreateCachedOptional(
634 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
635 if (!TransfersExecution)
636 return nullptr;
637
638 append_range(Worklist, successors(ToBB));
639 }
640 }
641
642 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
643 return JoinBB;
644}
645const BasicBlock *
647 const LoopInfo *LI = LIGetter(*InitBB->getParent());
648 const DominatorTree *DT = DTGetter(*InitBB->getParent());
649 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
650 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
651
652 // Try to determine a join block through the help of the dominance tree. If no
653 // tree was provided, we perform simple pattern matching for one block
654 // conditionals only.
655 if (DT)
656 if (const auto *InitNode = DT->getNode(InitBB))
657 if (const auto *IDomNode = InitNode->getIDom())
658 return IDomNode->getBlock();
659
660 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
661 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
662
663 // Determine the predecessor blocks but ignore backedges.
665 for (const BasicBlock *PredBB : predecessors(InitBB)) {
666 bool IsBackedge =
667 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
668 // Loop backedges are ignored in backwards propagation: control has to come
669 // from somewhere.
670 if (!IsBackedge)
671 Worklist.push_back(PredBB);
672 }
673
674 // If there are no other predecessor blocks, there is no join point.
675 if (Worklist.empty())
676 return nullptr;
677
678 // If there is one predecessor block, it is the join point.
679 if (Worklist.size() == 1)
680 return Worklist[0];
681
682 const BasicBlock *JoinBB = nullptr;
683 if (Worklist.size() == 2) {
684 const BasicBlock *Pred0 = Worklist[0];
685 const BasicBlock *Pred1 = Worklist[1];
686 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
687 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
688 if (Pred0 == Pred1UniquePred) {
689 // InitBB <- Pred0 = JoinBB
690 // InitBB <- Pred1 <- Pred0 = JoinBB
691 JoinBB = Pred0;
692 } else if (Pred1 == Pred0UniquePred) {
693 // InitBB <- Pred0 <- Pred1 = JoinBB
694 // InitBB <- Pred1 = JoinBB
695 JoinBB = Pred1;
696 } else if (Pred0UniquePred == Pred1UniquePred) {
697 // InitBB <- Pred0 <- JoinBB
698 // InitBB <- Pred1 <- JoinBB
699 JoinBB = Pred0UniquePred;
700 }
701 }
702
703 if (!JoinBB && L)
704 JoinBB = L->getHeader();
705
706 // In backwards direction there is no need to show termination of previous
707 // instructions. If they do not terminate, the code afterward is dead, making
708 // any information/transformation correct anyway.
709 return JoinBB;
710}
711
712const Instruction *
714 MustBeExecutedIterator &It, const Instruction *PP) {
715 if (!PP)
716 return PP;
717 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
718
719 // If we explore only inside a given basic block we stop at terminators.
720 if (!ExploreInterBlock && PP->isTerminator()) {
721 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
722 return nullptr;
723 }
724
725 // If we do not traverse the call graph we check if we can make progress in
726 // the current function. First, check if the instruction is guaranteed to
727 // transfer execution to the successor.
728 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
729 if (!TransfersExecution)
730 return nullptr;
731
732 // If this is not a terminator we know that there is a single instruction
733 // after this one that is executed next if control is transfered. If not,
734 // we can try to go back to a call site we entered earlier. If none exists, we
735 // do not know any instruction that has to be executd next.
736 if (!PP->isTerminator()) {
737 const Instruction *NextPP = PP->getNextNode();
738 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
739 return NextPP;
740 }
741
742 // Finally, we have to handle terminators, trivial ones first.
743 assert(PP->isTerminator() && "Expected a terminator!");
744
745 // A terminator without a successor is not handled yet.
746 if (PP->getNumSuccessors() == 0) {
747 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
748 return nullptr;
749 }
750
751 // A terminator with a single successor, we will continue at the beginning of
752 // that one.
753 if (PP->getNumSuccessors() == 1) {
755 dbgs() << "\tUnconditional terminator, continue with successor\n");
756 return &PP->getSuccessor(0)->front();
757 }
758
759 // Multiple successors mean we need to find the join point where control flow
760 // converges again. We use the findForwardJoinPoint helper function with
761 // information about the function and helper analyses, if available.
762 if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
763 return &JoinBB->front();
764
765 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
766 return nullptr;
767}
768
769const Instruction *
771 MustBeExecutedIterator &It, const Instruction *PP) {
772 if (!PP)
773 return PP;
774
775 bool IsFirst = !(PP->getPrevNode());
776 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
777 << (IsFirst ? " [IsFirst]" : "") << "\n");
778
779 // If we explore only inside a given basic block we stop at the first
780 // instruction.
781 if (!ExploreInterBlock && IsFirst) {
782 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
783 return nullptr;
784 }
785
786 // The block and function that contains the current position.
787 const BasicBlock *PPBlock = PP->getParent();
788
789 // If we are inside a block we know what instruction was executed before, the
790 // previous one.
791 if (!IsFirst) {
792 const Instruction *PrevPP = PP->getPrevNode();
794 dbgs() << "\tIntermediate instruction, continue with previous\n");
795 // We did not enter a callee so we simply return the previous instruction.
796 return PrevPP;
797 }
798
799 // Finally, we have to handle the case where the program point is the first in
800 // a block but not in the function. We use the findBackwardJoinPoint helper
801 // function with information about the function and helper analyses, if
802 // available.
803 if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
804 return &JoinBB->back();
805
806 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
807 return nullptr;
808}
809
812 : Explorer(Explorer), CurInst(I) {
813 reset(I);
814}
815
816void MustBeExecutedIterator::reset(const Instruction *I) {
817 Visited.clear();
818 resetInstruction(I);
819}
820
821void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
822 CurInst = I;
823 Head = Tail = nullptr;
826 if (Explorer.ExploreCFGForward)
827 Head = I;
828 if (Explorer.ExploreCFGBackward)
829 Tail = I;
830}
831
832const Instruction *MustBeExecutedIterator::advance() {
833 assert(CurInst && "Cannot advance an end iterator!");
834 Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
835 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
836 return Head;
837 Head = nullptr;
838
839 Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
840 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
841 return Tail;
842 Tail = nullptr;
843 return nullptr;
844}
845
848 auto &LI = AM.getResult<LoopAnalysis>(F);
849 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
850
851 MustExecuteAnnotatedWriter Writer(F, DT, LI);
852 F.print(OS, &Writer);
853 return PreservedAnalyses::all();
854}
855
860 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
861 return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
862 };
863 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
864 return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
865 };
866 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
867 return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
868 };
869
871 /* ExploreInterBlock */ true,
872 /* ExploreCFGForward */ true,
873 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
874
875 for (Function &F : M) {
876 for (Instruction &I : instructions(F)) {
877 OS << "-- Explore context of: " << I << "\n";
878 for (const Instruction *CI : Explorer.range(&I))
879 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
880 }
881 }
882 return PreservedAnalyses::all();
883}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
for(auto &MBB :MF)
SmallVector< MachineOperand, 4 > Cond
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool runOnFunction(Function &F, bool PostInlining)
Hexagon Hardware Loops
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
static void collectTransitivePredecessors(const Loop *CurLoop, const BasicBlock *BB, SmallPtrSetImpl< const BasicBlock * > &Predecessors)
Collect all blocks from CurLoop which lie on all possible paths from the header of CurLoop (inclusive...
print must be executed print the must be executed context for all instructions
static bool maybeEndlessLoop(const Loop &L)
Return true if L might be an endless loop.
static V getOrCreateCachedOptional(K Key, DenseMap< K, std::optional< V > > &Map, FnTy &&Fn, ArgsTy &&...args)
Lookup Key in Map and return the result, potentially after initializing the optional through Fn(args)...
print mustexecute
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
print Instructions which execute on loop entry
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop)
Return true if we can prove that the given ExitBlock is not reached on the first iteration of the giv...
print must be executed contexts
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
nvptx lower args
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some functions that are useful when dealing with strings.
Value * RHS
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Instruction & front() const
Definition: BasicBlock.h:326
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:322
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:284
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:292
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:215
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:146
This is an important base class in LLVM.
Definition: Constant.h:41
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:803
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1995
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:640
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:71
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:99
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:75
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:79
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB.
Definition: MustExecute.cpp:93
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:933
void clear()
Invalidates all information from this tracking.
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
Definition: Instruction.h:90
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool isTerminator() const
Definition: Instruction.h:171
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
BlockT * getHeader() const
Definition: LoopInfo.h:105
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const
Return true if we must reach the block BB under assumption that the loop CurLoop is entered.
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:36
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:32
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:110
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:51
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:47
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:42
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:29
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:386
ModulePass * createMustBeExecutedContextPrinter()
auto successors(const MachineBasicBlock *BB)
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
void initializeMustBeExecutedContextPrinterPass(PassRegistry &)
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:136
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto predecessors(const MachineBasicBlock *BB)
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
void initializeMustExecutePrinterPass(PassRegistry &)
FunctionPass * createMustExecutePrinter()
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:386
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:516
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:442
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:272
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default