LLVM 24.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
13#include "llvm/Analysis/CFG.h"
19#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PassManager.h"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "must-execute"
29
32 computeBlockColors();
33 return *BlockColors;
34}
35
37 // Nothing to update if colors have not been computed yet.
38 if (!BlockColors)
39 return;
40
41 ColorVector &ColorsForNewBlock = (*BlockColors)[New];
42 ColorVector &ColorsForOldBlock = (*BlockColors)[Old];
43 ColorsForNewBlock = ColorsForOldBlock;
44}
45
47 (void)BB;
48 return anyBlockMayThrow();
49}
50
52 return MayThrow;
53}
54
55void SimpleLoopSafetyInfo::computeLoopSafetyInfo() {
56 assert(CurLoop != nullptr && "CurLoop can't be null");
57 BasicBlock *Header = CurLoop->getHeader();
58 // Iterate over header and compute safety info.
59 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
60 MayThrow = HeaderMayThrow;
61 // Iterate over loop instructions and compute safety info.
62 // Skip header as it has been computed and stored in HeaderMayThrow.
63 // The first block in loopinfo.Blocks is guaranteed to be the header.
64 assert(Header == *CurLoop->getBlocks().begin() &&
65 "First block must be header");
66 for (const BasicBlock *BB : llvm::drop_begin(CurLoop->blocks())) {
68 if (MayThrow)
69 break;
70 }
71}
72
74 return ICF.hasICF(BB);
75}
76
78 return MayThrow;
79}
80
81void ICFLoopSafetyInfo::computeLoopSafetyInfo() {
82 assert(CurLoop != nullptr && "CurLoop can't be null");
83 ICF.clear();
84 MW.clear();
85 MayThrow = false;
86 // Figure out the fact that at least one block may throw.
87 for (const auto &BB : CurLoop->blocks())
88 if (ICF.hasICF(&*BB)) {
89 MayThrow = true;
90 break;
91 }
92}
93
95 const BasicBlock *BB) {
96 ICF.insertInstructionTo(Inst, BB);
97 MW.insertInstructionTo(Inst, BB);
98}
99
101 ICF.removeInstruction(Inst);
102 MW.removeInstruction(Inst);
103}
104
105void LoopSafetyInfo::computeBlockColors() const {
106 if (BlockColors)
107 return;
108 BlockColors.emplace();
109
110 // Compute funclet colors if we might sink/hoist in a function with a funclet
111 // personality routine.
113 if (Fn->hasPersonalityFn())
114 if (Constant *PersonalityFn = Fn->getPersonalityFn())
116 BlockColors = colorEHFunclets(*Fn);
117}
118
119/// Return true if we can prove that the given ExitBlock is not reached on the
120/// first iteration of the given loop. That is, the backedge of the loop must
121/// be executed before the ExitBlock is executed in any dynamic execution trace.
122static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
123 const DominatorTree *DT,
124 const Loop *CurLoop) {
125 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
126 if (!CondExitBlock)
127 // expect unique exits
128 return false;
129 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
130 auto *BI = dyn_cast<CondBrInst>(CondExitBlock->getTerminator());
131 if (!BI)
132 return false;
133 // If condition is constant and false leads to ExitBlock then we always
134 // execute the true branch.
135 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
136 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
137 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
138 if (!Cond)
139 return false;
140 // todo: this would be a lot more powerful if we used scev, but all the
141 // plumbing is currently missing to pass a pointer in from the pass
142 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
143 ICmpInst::Predicate Pred = Cond->getPredicate();
144 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
145 auto *RHS = Cond->getOperand(1);
146 if (!LHS || LHS->getParent() != CurLoop->getHeader()) {
147 Pred = Cond->getSwappedPredicate();
148 LHS = dyn_cast<PHINode>(Cond->getOperand(1));
149 RHS = Cond->getOperand(0);
150 if (!LHS || LHS->getParent() != CurLoop->getHeader())
151 return false;
152 }
153
154 // The induction variable starts at the value coming into the header from
155 // outside the loop. A loop that is not in simplified form has no preheader,
156 // but the header can still have a single predecessor outside the loop.
157 BasicBlock *Predecessor = CurLoop->getLoopPredecessor();
158 if (!Predecessor)
159 return false;
160
161 auto DL = ExitBlock->getDataLayout();
162 auto *IVStart = LHS->getIncomingValueForBlock(Predecessor);
163 auto *SimpleValOrNull = simplifyCmpInst(
164 Pred, IVStart, RHS, {DL, /*TLI*/ nullptr, DT, /*AC*/ nullptr, BI});
165 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
166 if (!SimpleCst)
167 return false;
168 if (ExitBlock == BI->getSuccessor(0))
169 return SimpleCst->isNullValue();
170 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
171 return SimpleCst->isAllOnesValue();
172}
173
174/// Collect all blocks from \p CurLoop which lie on all possible paths from
175/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
176/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
177/// Note: It's possible that we encounter Irreducible control flow, due to
178/// which, we may find that a few predecessors of \p BB are not a part of the
179/// \p CurLoop. We only return Predecessors that are a part of \p CurLoop.
181 const Loop *CurLoop, const BasicBlock *BB,
183 assert(Predecessors.empty() && "Garbage in predecessors set?");
184 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
185 if (BB == CurLoop->getHeader())
186 return;
188 for (const auto *Pred : predecessors(BB)) {
189 if (!CurLoop->contains(Pred))
190 continue;
191 Predecessors.insert(Pred);
192 WorkList.push_back(Pred);
193 }
194 while (!WorkList.empty()) {
195 auto *Pred = WorkList.pop_back_val();
196 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
197 // We are not interested in backedges and we don't want to leave loop.
198 if (Pred == CurLoop->getHeader())
199 continue;
200 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
201 // blocks of this inner loop, even those that are always executed AFTER the
202 // BB. It may make our analysis more conservative than it could be, see test
203 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
204 // We can ignore backedge of all loops containing BB to get a sligtly more
205 // optimistic result.
206 for (const auto *PredPred : predecessors(Pred))
207 if (CurLoop->contains(PredPred) && Predecessors.insert(PredPred).second)
208 WorkList.push_back(PredPred);
209 }
210}
211
213 const DominatorTree *DT) const {
214 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
215
216 // Fast path: header is always reached once the loop is entered.
217 if (BB == CurLoop->getHeader())
218 return true;
219
220 auto [It, Inserted] = GuaranteedToExecute.try_emplace(BB, false);
221 if (Inserted)
222 It->second = allLoopPathsLeadToBlockImpl(BB, DT);
223 return It->second;
224}
225
226bool LoopSafetyInfo::allLoopPathsLeadToBlockImpl(
227 const BasicBlock *BB, const DominatorTree *DT) const {
228 // Collect all transitive predecessors of BB in the same loop. This set will
229 // be a subset of the blocks within the loop.
231 collectTransitivePredecessors(CurLoop, BB, Predecessors);
232
233 // Bail out if a latch block is part of the predecessor set. In this case
234 // we may take the backedge to the header and not execute other latch
235 // successors.
236 for (const BasicBlock *Pred : predecessors(CurLoop->getHeader()))
237 // Predecessors only contains loop blocks, so we don't have to worry about
238 // preheader predecessors here.
239 if (Predecessors.contains(Pred))
240 return false;
241
242 // Make sure that all successors of, all predecessors of BB which are not
243 // dominated by BB, are either:
244 // 1) BB,
245 // 2) Also predecessors of BB,
246 // 3) Exit blocks which are not taken on 1st iteration.
247 // Memoize blocks we've already checked.
248 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
249 for (const auto *Pred : Predecessors) {
250 // Predecessor block may throw, so it has a side exit.
251 if (blockMayThrow(Pred))
252 return false;
253
254 // BB dominates Pred, so if Pred runs, BB must run.
255 // This is true when Pred is a loop latch.
256 if (DT->dominates(BB, Pred))
257 continue;
258
259 for (const auto *Succ : successors(Pred))
260 if (CheckedSuccessors.insert(Succ).second &&
261 Succ != BB && !Predecessors.count(Succ))
262 // By discharging conditions that are not executed on the 1st iteration,
263 // we guarantee that *at least* on the first iteration all paths from
264 // header that *may* execute will lead us to the block of interest. So
265 // that if we had virtually peeled one iteration away, in this peeled
266 // iteration the set of predecessors would contain only paths from
267 // header to BB without any exiting edges that may execute.
268 //
269 // TODO: We only do it for exiting edges currently. We could use the
270 // same function to skip some of the edges within the loop if we know
271 // that they will not be taken on the 1st iteration.
272 //
273 // TODO: If we somehow know the number of iterations in loop, the same
274 // check may be done for any arbitrary N-th iteration as long as N is
275 // not greater than minimum number of iterations in this loop.
276 if (CurLoop->contains(Succ) ||
278 return false;
279 }
280
281 // All predecessors can only lead us to BB.
282 return true;
283}
284
285/// Returns true if the instruction in a loop is guaranteed to execute at least
286/// once.
288 const Instruction &Inst, const DominatorTree *DT) const {
289 // If the instruction is in the header block for the loop (which is very
290 // common), it is always guaranteed to dominate the exit blocks. Since this
291 // is a common case, and can save some work, check it now.
292 if (Inst.getParent() == CurLoop->getHeader())
293 // If there's a throw in the header block, we can't guarantee we'll reach
294 // Inst unless we can prove that Inst comes before the potential implicit
295 // exit. At the moment, we use a (cheap) hack for the common case where
296 // the instruction of interest is the first one in the block.
297 return !HeaderMayThrow ||
298 &*Inst.getParent()->getFirstNonPHIOrPseudoProbe() == &Inst;
299
300 // If there is a path from header to exit or latch that doesn't lead to our
301 // instruction's block, return false.
302 return allLoopPathsLeadToBlock(Inst.getParent(), DT);
303}
304
306 const DominatorTree *DT) const {
307 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
309}
310
312 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
313
314 // Fast path: there are no instructions before header.
315 if (BB == CurLoop->getHeader())
316 return true;
317
318 // Collect all transitive predecessors of BB in the same loop. This set will
319 // be a subset of the blocks within the loop.
321 collectTransitivePredecessors(CurLoop, BB, Predecessors);
322 // Find if there any instruction in either predecessor that could write
323 // to memory.
324 for (const auto *Pred : Predecessors)
325 if (MW.mayWriteToMemory(Pred))
326 return false;
327 return true;
328}
329
331 auto *BB = I.getParent();
332 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
333 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
335}
336
337static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
338 // TODO: merge these two routines. For the moment, we display the best
339 // result obtained by *either* implementation. This is a bit unfair since no
340 // caller actually gets the full power at the moment.
342 return LSI.isGuaranteedToExecute(I, DT) ||
344}
345
346namespace {
347/// An assembly annotator class to print must execute information in
348/// comments.
349class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
350 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
351
352public:
353 MustExecuteAnnotatedWriter(const Function &F,
354 DominatorTree &DT, LoopInfo &LI) {
355 for (const auto &I: instructions(F)) {
356 Loop *L = LI.getLoopFor(I.getParent());
357 while (L) {
358 if (isMustExecuteIn(I, L, &DT)) {
359 MustExec[&I].push_back(L);
360 }
361 L = L->getParentLoop();
362 };
363 }
364 }
365 MustExecuteAnnotatedWriter(const Module &M,
366 DominatorTree &DT, LoopInfo &LI) {
367 for (const auto &F : M)
368 for (const auto &I: instructions(F)) {
369 Loop *L = LI.getLoopFor(I.getParent());
370 while (L) {
371 if (isMustExecuteIn(I, L, &DT)) {
372 MustExec[&I].push_back(L);
373 }
374 L = L->getParentLoop();
375 };
376 }
377 }
378
379
380 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
381 if (!MustExec.count(&V))
382 return;
383
384 const auto &Loops = MustExec.lookup(&V);
385 const auto NumLoops = Loops.size();
386 if (NumLoops > 1)
387 OS << " ; (mustexec in " << NumLoops << " loops: ";
388 else
389 OS << " ; (mustexec in: ";
390
391 ListSeparator LS;
392 for (const Loop *L : Loops)
393 OS << LS << L->getHeader()->getName();
394 OS << ")";
395 }
396};
397} // namespace
398
399/// Return true if \p L might be an endless loop.
400static bool maybeEndlessLoop(const Loop &L) {
401 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
402 return false;
403 // TODO: Actually try to prove it is not.
404 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
405 return true;
406}
407
409 if (!LI)
410 return false;
412 RPOTraversal FuncRPOT(&F);
413 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
414 const LoopInfo>(FuncRPOT, *LI);
415}
416
417/// Lookup \p Key in \p Map and return the result, potentially after
418/// initializing the optional through \p Fn(\p args).
419template <typename K, typename V, typename FnTy, typename... ArgsTy>
420static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
421 FnTy &&Fn, ArgsTy &&...args) {
422 std::optional<V> &OptVal = Map[Key];
423 if (!OptVal)
424 OptVal = Fn(std::forward<ArgsTy>(args)...);
425 return *OptVal;
426}
427
428const BasicBlock *
430 const LoopInfo *LI = LIGetter(*InitBB->getParent());
431 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
432
433 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
434 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
435
436 const Function &F = *InitBB->getParent();
437 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
438 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
439 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
440 (L && !maybeEndlessLoop(*L))) &&
441 F.doesNotThrow();
442 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
443 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
444 << "\n");
445
446 // Determine the adjacent blocks in the given direction but exclude (self)
447 // loops under certain circumstances.
449 for (const BasicBlock *SuccBB : successors(InitBB)) {
450 bool IsLatch = SuccBB == HeaderBB;
451 // Loop latches are ignored in forward propagation if the loop cannot be
452 // endless and may not throw: control has to go somewhere.
453 if (!WillReturnAndNoThrow || !IsLatch)
454 Worklist.push_back(SuccBB);
455 }
456 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
457
458 // If there are no other adjacent blocks, there is no join point.
459 if (Worklist.empty())
460 return nullptr;
461
462 // If there is one adjacent block, it is the join point.
463 if (Worklist.size() == 1)
464 return Worklist[0];
465
466 // Try to determine a join block through the help of the post-dominance
467 // tree. If no tree was provided, we perform simple pattern matching for one
468 // block conditionals and one block loops only.
469 const BasicBlock *JoinBB = nullptr;
470 if (PDT)
471 if (const auto *InitNode = PDT->getNode(InitBB))
472 if (const auto *IDomNode = InitNode->getIDom())
473 JoinBB = IDomNode->getBlock();
474
475 if (!JoinBB && Worklist.size() == 2) {
476 const BasicBlock *Succ0 = Worklist[0];
477 const BasicBlock *Succ1 = Worklist[1];
478 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
479 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
480 if (Succ0UniqueSucc == InitBB) {
481 // InitBB -> Succ0 -> InitBB
482 // InitBB -> Succ1 = JoinBB
483 JoinBB = Succ1;
484 } else if (Succ1UniqueSucc == InitBB) {
485 // InitBB -> Succ1 -> InitBB
486 // InitBB -> Succ0 = JoinBB
487 JoinBB = Succ0;
488 } else if (Succ0 == Succ1UniqueSucc) {
489 // InitBB -> Succ0 = JoinBB
490 // InitBB -> Succ1 -> Succ0 = JoinBB
491 JoinBB = Succ0;
492 } else if (Succ1 == Succ0UniqueSucc) {
493 // InitBB -> Succ0 -> Succ1 = JoinBB
494 // InitBB -> Succ1 = JoinBB
495 JoinBB = Succ1;
496 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
497 // InitBB -> Succ0 -> JoinBB
498 // InitBB -> Succ1 -> JoinBB
499 JoinBB = Succ0UniqueSucc;
500 }
501 }
502
503 if (!JoinBB && L)
504 JoinBB = L->getUniqueExitBlock();
505
506 if (!JoinBB)
507 return nullptr;
508
509 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
510
511 // In forward direction we check if control will for sure reach JoinBB from
512 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
513 // are: infinite loops and instructions that do not necessarily transfer
514 // execution to their successor. To check for them we traverse the CFG from
515 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
516
517 // If we know the function is "will-return" and "no-throw" there is no need
518 // for futher checks.
519 if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
520
521 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
523 };
524
526 while (!Worklist.empty()) {
527 const BasicBlock *ToBB = Worklist.pop_back_val();
528 if (ToBB == JoinBB)
529 continue;
530
531 // Make sure all loops in-between are finite.
532 if (!Visited.insert(ToBB).second) {
533 if (!F.hasFnAttribute(Attribute::WillReturn)) {
534 if (!LI)
535 return nullptr;
536
537 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
538 &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
539 if (MayContainIrreducibleControl)
540 return nullptr;
541
542 const Loop *L = LI->getLoopFor(ToBB);
543 if (L && maybeEndlessLoop(*L))
544 return nullptr;
545 }
546
547 continue;
548 }
549
550 // Make sure the block has no instructions that could stop control
551 // transfer.
552 bool TransfersExecution = getOrCreateCachedOptional(
553 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
554 if (!TransfersExecution)
555 return nullptr;
556
557 append_range(Worklist, successors(ToBB));
558 }
559 }
560
561 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
562 return JoinBB;
563}
564const BasicBlock *
566 const LoopInfo *LI = LIGetter(*InitBB->getParent());
567 const DominatorTree *DT = DTGetter(*InitBB->getParent());
568 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
569 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
570
571 // Try to determine a join block through the help of the dominance tree. If no
572 // tree was provided, we perform simple pattern matching for one block
573 // conditionals only.
574 if (DT)
575 if (const auto *InitNode = DT->getNode(InitBB))
576 if (const auto *IDomNode = InitNode->getIDom())
577 return IDomNode->getBlock();
578
579 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
580 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
581
582 // Determine the predecessor blocks but ignore backedges.
584 for (const BasicBlock *PredBB : predecessors(InitBB)) {
585 bool IsBackedge =
586 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
587 // Loop backedges are ignored in backwards propagation: control has to come
588 // from somewhere.
589 if (!IsBackedge)
590 Worklist.push_back(PredBB);
591 }
592
593 // If there are no other predecessor blocks, there is no join point.
594 if (Worklist.empty())
595 return nullptr;
596
597 // If there is one predecessor block, it is the join point.
598 if (Worklist.size() == 1)
599 return Worklist[0];
600
601 const BasicBlock *JoinBB = nullptr;
602 if (Worklist.size() == 2) {
603 const BasicBlock *Pred0 = Worklist[0];
604 const BasicBlock *Pred1 = Worklist[1];
605 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
606 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
607 if (Pred0 == Pred1UniquePred) {
608 // InitBB <- Pred0 = JoinBB
609 // InitBB <- Pred1 <- Pred0 = JoinBB
610 JoinBB = Pred0;
611 } else if (Pred1 == Pred0UniquePred) {
612 // InitBB <- Pred0 <- Pred1 = JoinBB
613 // InitBB <- Pred1 = JoinBB
614 JoinBB = Pred1;
615 } else if (Pred0UniquePred == Pred1UniquePred) {
616 // InitBB <- Pred0 <- JoinBB
617 // InitBB <- Pred1 <- JoinBB
618 JoinBB = Pred0UniquePred;
619 }
620 }
621
622 if (!JoinBB && L)
623 JoinBB = L->getHeader();
624
625 // In backwards direction there is no need to show termination of previous
626 // instructions. If they do not terminate, the code afterward is dead, making
627 // any information/transformation correct anyway.
628 return JoinBB;
629}
630
631const Instruction *
633 MustBeExecutedIterator &It, const Instruction *PP) {
634 if (!PP)
635 return PP;
636 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
637
638 // If we explore only inside a given basic block we stop at terminators.
639 if (!ExploreInterBlock && PP->isTerminator()) {
640 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
641 return nullptr;
642 }
643
644 // If we do not traverse the call graph we check if we can make progress in
645 // the current function. First, check if the instruction is guaranteed to
646 // transfer execution to the successor.
647 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
648 if (!TransfersExecution)
649 return nullptr;
650
651 // If this is not a terminator we know that there is a single instruction
652 // after this one that is executed next if control is transfered. If not,
653 // we can try to go back to a call site we entered earlier. If none exists, we
654 // do not know any instruction that has to be executd next.
655 if (!PP->isTerminator()) {
656 const Instruction *NextPP = PP->getNextNode();
657 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
658 return NextPP;
659 }
660
661 // Finally, we have to handle terminators, trivial ones first.
662 assert(PP->isTerminator() && "Expected a terminator!");
663
664 // A terminator without a successor is not handled yet.
665 if (PP->getNumSuccessors() == 0) {
666 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
667 return nullptr;
668 }
669
670 // A terminator with a single successor, we will continue at the beginning of
671 // that one.
672 if (PP->getNumSuccessors() == 1) {
674 dbgs() << "\tUnconditional terminator, continue with successor\n");
675 return &PP->getSuccessor(0)->front();
676 }
677
678 // Multiple successors mean we need to find the join point where control flow
679 // converges again. We use the findForwardJoinPoint helper function with
680 // information about the function and helper analyses, if available.
681 if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
682 return &JoinBB->front();
683
684 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
685 return nullptr;
686}
687
688const Instruction *
690 MustBeExecutedIterator &It, const Instruction *PP) {
691 if (!PP)
692 return PP;
693
694 bool IsFirst = !(PP->getPrevNode());
695 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
696 << (IsFirst ? " [IsFirst]" : "") << "\n");
697
698 // If we explore only inside a given basic block we stop at the first
699 // instruction.
700 if (!ExploreInterBlock && IsFirst) {
701 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
702 return nullptr;
703 }
704
705 // The block and function that contains the current position.
706 const BasicBlock *PPBlock = PP->getParent();
707
708 // If we are inside a block we know what instruction was executed before, the
709 // previous one.
710 if (!IsFirst) {
711 const Instruction *PrevPP = PP->getPrevNode();
713 dbgs() << "\tIntermediate instruction, continue with previous\n");
714 // We did not enter a callee so we simply return the previous instruction.
715 return PrevPP;
716 }
717
718 // Finally, we have to handle the case where the program point is the first in
719 // a block but not in the function. We use the findBackwardJoinPoint helper
720 // function with information about the function and helper analyses, if
721 // available.
722 if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
723 return &JoinBB->back();
724
725 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
726 return nullptr;
727}
728
729const Instruction *
730MustBeExecutedContextExplorer::getForwardStop(const Instruction *PP) {
731 const BasicBlock *BB = PP->getParent();
732 auto [It, Inserted] = NonTransferringMap.try_emplace(BB);
733 if (Inserted) {
734 for (const Instruction &I : *BB) {
736 It->second.push_back(&I);
737 }
738 }
739 ArrayRef<const Instruction *> NonTransferring = It->second;
740 auto Stop = llvm::lower_bound(NonTransferring, PP,
741 [](const Instruction *A, const Instruction *B) {
742 return A->comesBefore(B);
743 });
744 return Stop == NonTransferring.end() ? nullptr : *Stop;
745}
746
747const BasicBlock *
748MustBeExecutedContextExplorer::getForwardNextBlock(const BasicBlock *BB) {
749 auto [It, Inserted] = ForwardNextBlockMap.try_emplace(BB);
750 if (Inserted) {
751 const Instruction *Term = BB->getTerminator();
752 if (Term->getNumSuccessors() == 1)
753 It->second = Term->getSuccessor(0);
754 else if (Term->getNumSuccessors() > 1)
755 It->second = findForwardJoinPoint(BB);
756 }
757 return It->second;
758}
759
760const BasicBlock *
761MustBeExecutedContextExplorer::getBackwardNextBlock(const BasicBlock *BB) {
762 auto [It, Inserted] = BackwardNextBlockMap.try_emplace(BB);
763 if (Inserted)
764 It->second = findBackwardJoinPoint(BB);
765 return It->second;
766}
767
768const MustBeExecutedContextExplorer::ForwardContextTy &
769MustBeExecutedContextExplorer::getForwardContext(const BasicBlock *BB) {
770 auto &Context = ForwardContextMap[BB];
771 if (!Context) {
772 Context = std::make_unique<ForwardContextTy>();
773 for (const BasicBlock *CurBB = getForwardNextBlock(BB); CurBB;) {
774 const Instruction *Stop = getForwardStop(&CurBB->front());
775 if (!Context->try_emplace(CurBB, Stop).second)
776 break;
777 CurBB = Stop ? nullptr : getForwardNextBlock(CurBB);
778 }
779 }
780 return *Context;
781}
782
783const MustBeExecutedContextExplorer::BackwardContextTy &
784MustBeExecutedContextExplorer::getBackwardContext(const BasicBlock *BB) {
785 auto &Context = BackwardContextMap[BB];
786 if (!Context) {
787 Context = std::make_unique<BackwardContextTy>();
788 for (const BasicBlock *CurBB = getBackwardNextBlock(BB);
789 CurBB && Context->insert(CurBB);)
790 CurBB = getBackwardNextBlock(CurBB);
791 }
792 return *Context;
793}
794
796 const Instruction *PP) {
797 if (I == PP)
798 return true;
799 const BasicBlock *IBB = I->getParent();
800 const BasicBlock *PPBB = PP->getParent();
801 if (IBB->getParent() != PPBB->getParent())
802 return false;
803
804 if (ExploreCFGForward) {
805 // Forward, the context contains the instructions up to the first one that
806 // might not transfer execution. If there is none, it continues in the
807 // forward context of the next block.
808 const Instruction *Stop = getForwardStop(PP);
809 if (IBB == PPBB && PP->comesBefore(I) && (!Stop || !Stop->comesBefore(I)))
810 return true;
811 if (!Stop && ExploreInterBlock) {
812 const ForwardContextTy &Context = getForwardContext(PPBB);
813 auto It = Context.find(IBB);
814 if (It != Context.end() && (!It->second || !It->second->comesBefore(I)))
815 return true;
816 }
817 }
818
819 if (ExploreCFGBackward) {
820 // Backward, the context contains all prior instructions in the block and
821 // the backward context of the backward join point.
822 if (IBB == PPBB && I->comesBefore(PP))
823 return true;
824 if (ExploreInterBlock && getBackwardContext(PPBB).contains(IBB))
825 return true;
826 }
827 return false;
828}
829
831 const Instruction *PP, function_ref<bool(const Instruction *)> Pred) {
832 // Only the blocks of the forward and backward contexts of the block of PP
833 // can have terminators in the context.
835 auto CheckBlock = [&](const BasicBlock *BB) {
836 if (!Visited.insert(BB).second)
837 return true;
838 const Instruction *Term = BB->getTerminator();
839 return !isInContextOf(Term, PP) || Pred(Term);
840 };
841 const BasicBlock *PPBB = PP->getParent();
842 if (!CheckBlock(PPBB))
843 return false;
845 return true;
846 if (ExploreCFGForward && !getForwardStop(PP)) {
847 for (const auto &[BB, Stop] : getForwardContext(PPBB)) {
848 if (!CheckBlock(BB))
849 return false;
850 }
851 }
852 if (ExploreCFGBackward) {
853 for (const BasicBlock *BB : getBackwardContext(PPBB)) {
854 if (!CheckBlock(BB))
855 return false;
856 }
857 }
858 return true;
859}
860
863 : Explorer(Explorer), CurInst(I), Head(nullptr), Tail(nullptr) {
864 // The end iterator, without an instruction, never explores anything.
865 if (I)
866 reset(I);
867}
868
869void MustBeExecutedIterator::reset(const Instruction *I) {
870 Visited.clear();
871 resetInstruction(I);
872}
873
874void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
875 CurInst = I;
876 Head = Tail = nullptr;
877 Visited.insert({I, ExplorationDirection::FORWARD});
878 Visited.insert({I, ExplorationDirection::BACKWARD});
879 if (Explorer.ExploreCFGForward)
880 Head = I;
881 if (Explorer.ExploreCFGBackward)
882 Tail = I;
883}
884
885const Instruction *MustBeExecutedIterator::advance() {
886 assert(CurInst && "Cannot advance an end iterator!");
887 Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
888 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
889 return Head;
890 Head = nullptr;
891
892 Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
893 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
894 return Tail;
895 Tail = nullptr;
896 return nullptr;
897}
898
901 auto &LI = AM.getResult<LoopAnalysis>(F);
902 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
903
904 MustExecuteAnnotatedWriter Writer(F, DT, LI);
905 F.print(OS, &Writer);
906 return PreservedAnalyses::all();
907}
908
913 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
914 return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
915 };
916 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
917 return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
918 };
919 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
920 return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
921 };
922
924 /* ExploreInterBlock */ true,
925 /* ExploreCFGForward */ true,
926 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
927
928 for (Function &F : M) {
929 for (Instruction &I : instructions(F)) {
930 OS << "-- Explore context of: " << I << "\n";
931 for (const Instruction *CI : Explorer.range(&I))
932 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
933 }
934 }
935 return PreservedAnalyses::all();
936}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Hexagon Hardware Loops
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
Machine Check Debug Module
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 file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
SmallVector< MachineOperand, 4 > Cond
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition Value.cpp:479
This file defines the SmallPtrSet class.
This file contains some functions that are useful when dealing with strings.
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
iterator end() const
Definition ArrayRef.h:130
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
Definition BasicBlock.h:463
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
This is an important base class in LLVM.
Definition Constant.h:44
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:762
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
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:122
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition Function.h:899
Constant * getPersonalityFn() const
Get the personality function associated with this function.
bool doesNotWriteMemoryBefore(const BasicBlock *BB) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
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.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
LLVM_ABI void clear()
Invalidates all information from this tracking.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool isTerminator() const
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the 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.
LLVM_ABI void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
LLVM_ABI const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
LLVM_ABI bool allLoopPathsLeadToBlock(const BasicBlock *BB, const DominatorTree *DT) const
Return true if we must reach the block BB under assumption that the loop is entered.
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
const Loop * CurLoop
Definition MustExecute.h:73
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
LLVM_ABI 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:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition ilist_node.h:348
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
LLVM_ABI 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:2224
LLVM_ABI DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition CFG.h:154
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition STLExtras.h:2068
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
TinyPtrVector< BasicBlock * > ColorVector
auto predecessors(const MachineBasicBlock *BB)
LLVM_ABI Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition MIRParser.h:39
A "must be executed context" for a given program point PP is the set of instructions,...
const bool ExploreInterBlock
Parameter that limit the performed exploration.
LLVM_ABI const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
LLVM_ABI const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
LLVM_ABI bool checkForAllTerminatorsInContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
Check Pred on all terminators in the context of PP and return true if it holds for all of them.
llvm::iterator_range< iterator > range(const Instruction *PP)
}
LLVM_ABI bool isInContextOf(const Instruction *I, const Instruction *PP)
}
LLVM_ABI const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
LLVM_ABI 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...
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default