LLVM 19.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
312static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
313 // TODO: merge these two routines. For the moment, we display the best
314 // result obtained by *either* implementation. This is a bit unfair since no
315 // caller actually gets the full power at the moment.
318 return LSI.isGuaranteedToExecute(I, DT, L) ||
320}
321
322namespace {
323/// An assembly annotator class to print must execute information in
324/// comments.
325class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
327
328public:
329 MustExecuteAnnotatedWriter(const Function &F,
330 DominatorTree &DT, LoopInfo &LI) {
331 for (const auto &I: instructions(F)) {
332 Loop *L = LI.getLoopFor(I.getParent());
333 while (L) {
334 if (isMustExecuteIn(I, L, &DT)) {
335 MustExec[&I].push_back(L);
336 }
337 L = L->getParentLoop();
338 };
339 }
340 }
341 MustExecuteAnnotatedWriter(const Module &M,
342 DominatorTree &DT, LoopInfo &LI) {
343 for (const auto &F : M)
344 for (const auto &I: instructions(F)) {
345 Loop *L = LI.getLoopFor(I.getParent());
346 while (L) {
347 if (isMustExecuteIn(I, L, &DT)) {
348 MustExec[&I].push_back(L);
349 }
350 L = L->getParentLoop();
351 };
352 }
353 }
354
355
356 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
357 if (!MustExec.count(&V))
358 return;
359
360 const auto &Loops = MustExec.lookup(&V);
361 const auto NumLoops = Loops.size();
362 if (NumLoops > 1)
363 OS << " ; (mustexec in " << NumLoops << " loops: ";
364 else
365 OS << " ; (mustexec in: ";
366
367 ListSeparator LS;
368 for (const Loop *L : Loops)
369 OS << LS << L->getHeader()->getName();
370 OS << ")";
371 }
372};
373} // namespace
374
375/// Return true if \p L might be an endless loop.
376static bool maybeEndlessLoop(const Loop &L) {
377 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
378 return false;
379 // TODO: Actually try to prove it is not.
380 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
381 return true;
382}
383
385 if (!LI)
386 return false;
388 RPOTraversal FuncRPOT(&F);
389 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
390 const LoopInfo>(FuncRPOT, *LI);
391}
392
393/// Lookup \p Key in \p Map and return the result, potentially after
394/// initializing the optional through \p Fn(\p args).
395template <typename K, typename V, typename FnTy, typename... ArgsTy>
396static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
397 FnTy &&Fn, ArgsTy &&...args) {
398 std::optional<V> &OptVal = Map[Key];
399 if (!OptVal)
400 OptVal = Fn(std::forward<ArgsTy>(args)...);
401 return *OptVal;
402}
403
404const BasicBlock *
406 const LoopInfo *LI = LIGetter(*InitBB->getParent());
407 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
408
409 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
410 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
411
412 const Function &F = *InitBB->getParent();
413 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
414 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
415 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
416 (L && !maybeEndlessLoop(*L))) &&
417 F.doesNotThrow();
418 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
419 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
420 << "\n");
421
422 // Determine the adjacent blocks in the given direction but exclude (self)
423 // loops under certain circumstances.
425 for (const BasicBlock *SuccBB : successors(InitBB)) {
426 bool IsLatch = SuccBB == HeaderBB;
427 // Loop latches are ignored in forward propagation if the loop cannot be
428 // endless and may not throw: control has to go somewhere.
429 if (!WillReturnAndNoThrow || !IsLatch)
430 Worklist.push_back(SuccBB);
431 }
432 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
433
434 // If there are no other adjacent blocks, there is no join point.
435 if (Worklist.empty())
436 return nullptr;
437
438 // If there is one adjacent block, it is the join point.
439 if (Worklist.size() == 1)
440 return Worklist[0];
441
442 // Try to determine a join block through the help of the post-dominance
443 // tree. If no tree was provided, we perform simple pattern matching for one
444 // block conditionals and one block loops only.
445 const BasicBlock *JoinBB = nullptr;
446 if (PDT)
447 if (const auto *InitNode = PDT->getNode(InitBB))
448 if (const auto *IDomNode = InitNode->getIDom())
449 JoinBB = IDomNode->getBlock();
450
451 if (!JoinBB && Worklist.size() == 2) {
452 const BasicBlock *Succ0 = Worklist[0];
453 const BasicBlock *Succ1 = Worklist[1];
454 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
455 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
456 if (Succ0UniqueSucc == InitBB) {
457 // InitBB -> Succ0 -> InitBB
458 // InitBB -> Succ1 = JoinBB
459 JoinBB = Succ1;
460 } else if (Succ1UniqueSucc == InitBB) {
461 // InitBB -> Succ1 -> InitBB
462 // InitBB -> Succ0 = JoinBB
463 JoinBB = Succ0;
464 } else if (Succ0 == Succ1UniqueSucc) {
465 // InitBB -> Succ0 = JoinBB
466 // InitBB -> Succ1 -> Succ0 = JoinBB
467 JoinBB = Succ0;
468 } else if (Succ1 == Succ0UniqueSucc) {
469 // InitBB -> Succ0 -> Succ1 = JoinBB
470 // InitBB -> Succ1 = JoinBB
471 JoinBB = Succ1;
472 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
473 // InitBB -> Succ0 -> JoinBB
474 // InitBB -> Succ1 -> JoinBB
475 JoinBB = Succ0UniqueSucc;
476 }
477 }
478
479 if (!JoinBB && L)
480 JoinBB = L->getUniqueExitBlock();
481
482 if (!JoinBB)
483 return nullptr;
484
485 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
486
487 // In forward direction we check if control will for sure reach JoinBB from
488 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
489 // are: infinite loops and instructions that do not necessarily transfer
490 // execution to their successor. To check for them we traverse the CFG from
491 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
492
493 // If we know the function is "will-return" and "no-throw" there is no need
494 // for futher checks.
495 if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
496
497 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
499 };
500
502 while (!Worklist.empty()) {
503 const BasicBlock *ToBB = Worklist.pop_back_val();
504 if (ToBB == JoinBB)
505 continue;
506
507 // Make sure all loops in-between are finite.
508 if (!Visited.insert(ToBB).second) {
509 if (!F.hasFnAttribute(Attribute::WillReturn)) {
510 if (!LI)
511 return nullptr;
512
513 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
514 &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
515 if (MayContainIrreducibleControl)
516 return nullptr;
517
518 const Loop *L = LI->getLoopFor(ToBB);
519 if (L && maybeEndlessLoop(*L))
520 return nullptr;
521 }
522
523 continue;
524 }
525
526 // Make sure the block has no instructions that could stop control
527 // transfer.
528 bool TransfersExecution = getOrCreateCachedOptional(
529 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
530 if (!TransfersExecution)
531 return nullptr;
532
533 append_range(Worklist, successors(ToBB));
534 }
535 }
536
537 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
538 return JoinBB;
539}
540const BasicBlock *
542 const LoopInfo *LI = LIGetter(*InitBB->getParent());
543 const DominatorTree *DT = DTGetter(*InitBB->getParent());
544 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
545 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
546
547 // Try to determine a join block through the help of the dominance tree. If no
548 // tree was provided, we perform simple pattern matching for one block
549 // conditionals only.
550 if (DT)
551 if (const auto *InitNode = DT->getNode(InitBB))
552 if (const auto *IDomNode = InitNode->getIDom())
553 return IDomNode->getBlock();
554
555 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
556 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
557
558 // Determine the predecessor blocks but ignore backedges.
560 for (const BasicBlock *PredBB : predecessors(InitBB)) {
561 bool IsBackedge =
562 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
563 // Loop backedges are ignored in backwards propagation: control has to come
564 // from somewhere.
565 if (!IsBackedge)
566 Worklist.push_back(PredBB);
567 }
568
569 // If there are no other predecessor blocks, there is no join point.
570 if (Worklist.empty())
571 return nullptr;
572
573 // If there is one predecessor block, it is the join point.
574 if (Worklist.size() == 1)
575 return Worklist[0];
576
577 const BasicBlock *JoinBB = nullptr;
578 if (Worklist.size() == 2) {
579 const BasicBlock *Pred0 = Worklist[0];
580 const BasicBlock *Pred1 = Worklist[1];
581 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
582 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
583 if (Pred0 == Pred1UniquePred) {
584 // InitBB <- Pred0 = JoinBB
585 // InitBB <- Pred1 <- Pred0 = JoinBB
586 JoinBB = Pred0;
587 } else if (Pred1 == Pred0UniquePred) {
588 // InitBB <- Pred0 <- Pred1 = JoinBB
589 // InitBB <- Pred1 = JoinBB
590 JoinBB = Pred1;
591 } else if (Pred0UniquePred == Pred1UniquePred) {
592 // InitBB <- Pred0 <- JoinBB
593 // InitBB <- Pred1 <- JoinBB
594 JoinBB = Pred0UniquePred;
595 }
596 }
597
598 if (!JoinBB && L)
599 JoinBB = L->getHeader();
600
601 // In backwards direction there is no need to show termination of previous
602 // instructions. If they do not terminate, the code afterward is dead, making
603 // any information/transformation correct anyway.
604 return JoinBB;
605}
606
607const Instruction *
609 MustBeExecutedIterator &It, const Instruction *PP) {
610 if (!PP)
611 return PP;
612 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
613
614 // If we explore only inside a given basic block we stop at terminators.
615 if (!ExploreInterBlock && PP->isTerminator()) {
616 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
617 return nullptr;
618 }
619
620 // If we do not traverse the call graph we check if we can make progress in
621 // the current function. First, check if the instruction is guaranteed to
622 // transfer execution to the successor.
623 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
624 if (!TransfersExecution)
625 return nullptr;
626
627 // If this is not a terminator we know that there is a single instruction
628 // after this one that is executed next if control is transfered. If not,
629 // we can try to go back to a call site we entered earlier. If none exists, we
630 // do not know any instruction that has to be executd next.
631 if (!PP->isTerminator()) {
632 const Instruction *NextPP = PP->getNextNode();
633 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
634 return NextPP;
635 }
636
637 // Finally, we have to handle terminators, trivial ones first.
638 assert(PP->isTerminator() && "Expected a terminator!");
639
640 // A terminator without a successor is not handled yet.
641 if (PP->getNumSuccessors() == 0) {
642 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
643 return nullptr;
644 }
645
646 // A terminator with a single successor, we will continue at the beginning of
647 // that one.
648 if (PP->getNumSuccessors() == 1) {
650 dbgs() << "\tUnconditional terminator, continue with successor\n");
651 return &PP->getSuccessor(0)->front();
652 }
653
654 // Multiple successors mean we need to find the join point where control flow
655 // converges again. We use the findForwardJoinPoint helper function with
656 // information about the function and helper analyses, if available.
657 if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
658 return &JoinBB->front();
659
660 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
661 return nullptr;
662}
663
664const Instruction *
666 MustBeExecutedIterator &It, const Instruction *PP) {
667 if (!PP)
668 return PP;
669
670 bool IsFirst = !(PP->getPrevNode());
671 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
672 << (IsFirst ? " [IsFirst]" : "") << "\n");
673
674 // If we explore only inside a given basic block we stop at the first
675 // instruction.
676 if (!ExploreInterBlock && IsFirst) {
677 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
678 return nullptr;
679 }
680
681 // The block and function that contains the current position.
682 const BasicBlock *PPBlock = PP->getParent();
683
684 // If we are inside a block we know what instruction was executed before, the
685 // previous one.
686 if (!IsFirst) {
687 const Instruction *PrevPP = PP->getPrevNode();
689 dbgs() << "\tIntermediate instruction, continue with previous\n");
690 // We did not enter a callee so we simply return the previous instruction.
691 return PrevPP;
692 }
693
694 // Finally, we have to handle the case where the program point is the first in
695 // a block but not in the function. We use the findBackwardJoinPoint helper
696 // function with information about the function and helper analyses, if
697 // available.
698 if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
699 return &JoinBB->back();
700
701 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
702 return nullptr;
703}
704
707 : Explorer(Explorer), CurInst(I) {
708 reset(I);
709}
710
711void MustBeExecutedIterator::reset(const Instruction *I) {
712 Visited.clear();
713 resetInstruction(I);
714}
715
716void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
717 CurInst = I;
718 Head = Tail = nullptr;
721 if (Explorer.ExploreCFGForward)
722 Head = I;
723 if (Explorer.ExploreCFGBackward)
724 Tail = I;
725}
726
727const Instruction *MustBeExecutedIterator::advance() {
728 assert(CurInst && "Cannot advance an end iterator!");
729 Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
730 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
731 return Head;
732 Head = nullptr;
733
734 Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
735 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
736 return Tail;
737 Tail = nullptr;
738 return nullptr;
739}
740
743 auto &LI = AM.getResult<LoopAnalysis>(F);
744 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
745
746 MustExecuteAnnotatedWriter Writer(F, DT, LI);
747 F.print(OS, &Writer);
748 return PreservedAnalyses::all();
749}
750
755 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
756 return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
757 };
758 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
759 return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
760 };
761 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
762 return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
763 };
764
766 /* ExploreInterBlock */ true,
767 /* ExploreCFGForward */ true,
768 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
769
770 for (Function &F : M) {
771 for (Instruction &I : instructions(F)) {
772 OS << "-- Explore context of: " << I << "\n";
773 for (const Instruction *CI : Explorer.range(&I))
774 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
775 }
776 }
777 return PreservedAnalyses::all();
778}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Hexagon Hardware Loops
Select target instructions out of generic instructions
#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...
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)...
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
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...
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.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
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:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction & front() const
Definition: BasicBlock.h:461
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:535
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:497
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:505
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:214
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:424
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:336
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:202
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:151
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:275
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:847
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1870
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:658
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:150
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool isTerminator() const
Definition: Instruction.h:253
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
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:44
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.
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.h:275
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
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:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:309
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:316
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:329
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 range R to container C.
Definition: STLExtras.h:2053
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
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)
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