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
9#include "llvm/Analysis/MustExecute.h"
10#include "llvm/ADT/PostOrderIterator.h"
11#include "llvm/ADT/SmallPtrSet.h"
12#include "llvm/ADT/StringExtras.h"
13#include "llvm/Analysis/CFG.h"
14#include "llvm/Analysis/InstructionSimplify.h"
15#include "llvm/Analysis/LoopInfo.h"
16#include "llvm/Analysis/PostDominators.h"
17#include "llvm/Analysis/ValueTracking.h"
18#include "llvm/IR/AssemblyAnnotationWriter.h"
19#include "llvm/IR/Dominators.h"
20#include "llvm/IR/InstIterator.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PassManager.h"
23#include "llvm/Support/FormattedStream.h"
24#include "llvm/Support/raw_ostream.h"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "must-execute"
29
30const DenseMap<BasicBlock *, ColorVector> &
31LoopSafetyInfo::getBlockColors() const {
32 computeBlockColors();
33 return *BlockColors;
34}
35
36void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
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
46bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
47 (void)BB;
48 return anyBlockMayThrow();
49}
50
51bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
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(BB: 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(RangeOrContainer: CurLoop->blocks())) {
67 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(BB);
68 if (MayThrow)
69 break;
70 }
71}
72
73bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
74 return ICF.hasICF(BB);
75}
76
77bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
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: &*BB)) {
89 MayThrow = true;
90 break;
91 }
92}
93
94void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
95 const BasicBlock *BB) {
96 ICF.insertInstructionTo(Inst, BB);
97 MW.insertInstructionTo(Inst, BB);
98}
99
100void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
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.
112 Function *Fn = CurLoop->getHeader()->getParent();
113 if (Fn->hasPersonalityFn())
114 if (Constant *PersonalityFn = Fn->getPersonalityFn())
115 if (isScopedEHPersonality(Pers: classifyEHPersonality(Pers: PersonalityFn)))
116 BlockColors = colorEHFunclets(F&: *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>(Val: 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>(Val: BI->getCondition()))
136 return BI->getSuccessor(i: Cond->getZExtValue() ? 1 : 0) == ExitBlock;
137 auto *Cond = dyn_cast<CmpInst>(Val: 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>(Val: Cond->getOperand(i_nocapture: 0));
145 auto *RHS = Cond->getOperand(i_nocapture: 1);
146 if (!LHS || LHS->getParent() != CurLoop->getHeader()) {
147 Pred = Cond->getSwappedPredicate();
148 LHS = dyn_cast<PHINode>(Val: Cond->getOperand(i_nocapture: 1));
149 RHS = Cond->getOperand(i_nocapture: 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(BB: Predecessor);
163 auto *SimpleValOrNull = simplifyCmpInst(
164 Predicate: Pred, LHS: IVStart, RHS, Q: {DL, /*TLI*/ nullptr, DT, /*AC*/ nullptr, BI});
165 auto *SimpleCst = dyn_cast_or_null<Constant>(Val: SimpleValOrNull);
166 if (!SimpleCst)
167 return false;
168 if (ExitBlock == BI->getSuccessor(i: 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.
180static void collectTransitivePredecessors(
181 const Loop *CurLoop, const BasicBlock *BB,
182 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
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;
187 SmallVector<const BasicBlock *, 4> WorkList;
188 for (const auto *Pred : predecessors(BB)) {
189 if (!CurLoop->contains(BB: Pred))
190 continue;
191 Predecessors.insert(Ptr: Pred);
192 WorkList.push_back(Elt: 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(BB: Pred))
207 if (CurLoop->contains(BB: PredPred) && Predecessors.insert(Ptr: PredPred).second)
208 WorkList.push_back(Elt: PredPred);
209 }
210}
211
212bool LoopSafetyInfo::allLoopPathsLeadToBlock(const BasicBlock *BB,
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(Key: BB, Args: 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.
230 SmallPtrSet<const BasicBlock *, 4> Predecessors;
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(BB: CurLoop->getHeader()))
237 // Predecessors only contains loop blocks, so we don't have to worry about
238 // preheader predecessors here.
239 if (Predecessors.contains(Ptr: 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(BB: 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(A: BB, B: Pred))
257 continue;
258
259 for (const auto *Succ : successors(BB: Pred))
260 if (CheckedSuccessors.insert(Ptr: Succ).second &&
261 Succ != BB && !Predecessors.count(Ptr: 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(BB: Succ) ||
277 !CanProveNotTakenFirstIteration(ExitBlock: Succ, DT, CurLoop))
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.
287bool SimpleLoopSafetyInfo::isGuaranteedToExecute(
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(BB: Inst.getParent(), DT);
303}
304
305bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
306 const DominatorTree *DT) const {
307 return !ICF.isDominatedByICFIFromSameBlock(Insn: &Inst) &&
308 allLoopPathsLeadToBlock(BB: Inst.getParent(), DT);
309}
310
311bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB) const {
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.
320 SmallPtrSet<const BasicBlock *, 4> Predecessors;
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(BB: Pred))
326 return false;
327 return true;
328}
329
330bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I) const {
331 auto *BB = I.getParent();
332 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
333 return !MW.isDominatedByMemoryWriteFromSameBlock(Insn: &I) &&
334 doesNotWriteMemoryBefore(BB);
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.
341 SimpleLoopSafetyInfo LSI(L);
342 return LSI.isGuaranteedToExecute(Inst: I, DT) ||
343 isGuaranteedToExecuteForEveryIteration(I: &I, L);
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(BB: I.getParent());
357 while (L) {
358 if (isMustExecuteIn(I, L, DT: &DT)) {
359 MustExec[&I].push_back(Elt: 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(BB: I.getParent());
370 while (L) {
371 if (isMustExecuteIn(I, L, DT: &DT)) {
372 MustExec[&I].push_back(Elt: 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(Val: &V))
382 return;
383
384 const auto &Loops = MustExec.lookup(Val: &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(Kind: 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
408bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
409 if (!LI)
410 return false;
411 using RPOTraversal = ReversePostOrderTraversal<const Function *>;
412 RPOTraversal FuncRPOT(&F);
413 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
414 const LoopInfo>(RPOTraversal: FuncRPOT, LI: *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 *
429MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
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(BB: InitBB) : nullptr;
438 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
439 bool WillReturnAndNoThrow = (F.hasFnAttribute(Kind: Attribute::WillReturn) ||
440 (L && !maybeEndlessLoop(L: *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.
448 SmallVector<const BasicBlock *, 8> Worklist;
449 for (const BasicBlock *SuccBB : successors(BB: 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(Elt: 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(BB: 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(Kind: Attribute::WillReturn) || !F.doesNotThrow()) {
520
521 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
522 return isGuaranteedToTransferExecutionToSuccessor(BB);
523 };
524
525 SmallPtrSet<const BasicBlock *, 16> Visited;
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(Ptr: ToBB).second) {
533 if (!F.hasFnAttribute(Kind: Attribute::WillReturn)) {
534 if (!LI)
535 return nullptr;
536
537 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
538 Key: &F, Map&: IrreducibleControlMap, Fn&: mayContainIrreducibleControl, args: F, args&: LI);
539 if (MayContainIrreducibleControl)
540 return nullptr;
541
542 const Loop *L = LI->getLoopFor(BB: ToBB);
543 if (L && maybeEndlessLoop(L: *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 Key: ToBB, Map&: BlockTransferMap, Fn&: BlockTransfersExecutionToSuccessor, args&: ToBB);
554 if (!TransfersExecution)
555 return nullptr;
556
557 append_range(C&: Worklist, R: successors(BB: ToBB));
558 }
559 }
560
561 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
562 return JoinBB;
563}
564const BasicBlock *
565MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
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(BB: InitBB))
576 if (const auto *IDomNode = InitNode->getIDom())
577 return IDomNode->getBlock();
578
579 const Loop *L = LI ? LI->getLoopFor(BB: InitBB) : nullptr;
580 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
581
582 // Determine the predecessor blocks but ignore backedges.
583 SmallVector<const BasicBlock *, 8> Worklist;
584 for (const BasicBlock *PredBB : predecessors(BB: InitBB)) {
585 bool IsBackedge =
586 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(BB: PredBB));
587 // Loop backedges are ignored in backwards propagation: control has to come
588 // from somewhere.
589 if (!IsBackedge)
590 Worklist.push_back(Elt: 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 *
632MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
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(I: 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) {
673 LLVM_DEBUG(
674 dbgs() << "\tUnconditional terminator, continue with successor\n");
675 return &PP->getSuccessor(Idx: 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(InitBB: PP->getParent()))
682 return &JoinBB->front();
683
684 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
685 return nullptr;
686}
687
688const Instruction *
689MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
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();
712 LLVM_DEBUG(
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(InitBB: 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(Key: BB);
733 if (Inserted) {
734 for (const Instruction &I : *BB) {
735 if (!isGuaranteedToTransferExecutionToSuccessor(I: &I))
736 It->second.push_back(Elt: &I);
737 }
738 }
739 ArrayRef<const Instruction *> NonTransferring = It->second;
740 auto Stop = llvm::lower_bound(Range&: NonTransferring, Value&: PP,
741 C: [](const Instruction *A, const Instruction *B) {
742 return A->comesBefore(Other: 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(Key: BB);
750 if (Inserted) {
751 const Instruction *Term = BB->getTerminator();
752 if (Term->getNumSuccessors() == 1)
753 It->second = Term->getSuccessor(Idx: 0);
754 else if (Term->getNumSuccessors() > 1)
755 It->second = findForwardJoinPoint(InitBB: BB);
756 }
757 return It->second;
758}
759
760const BasicBlock *
761MustBeExecutedContextExplorer::getBackwardNextBlock(const BasicBlock *BB) {
762 auto [It, Inserted] = BackwardNextBlockMap.try_emplace(Key: BB);
763 if (Inserted)
764 It->second = findBackwardJoinPoint(InitBB: 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(PP: &CurBB->front());
775 if (!Context->try_emplace(Key: CurBB, Args&: Stop).second)
776 break;
777 CurBB = Stop ? nullptr : getForwardNextBlock(BB: 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(X: CurBB);)
790 CurBB = getBackwardNextBlock(BB: CurBB);
791 }
792 return *Context;
793}
794
795bool MustBeExecutedContextExplorer::isInContextOf(const Instruction *I,
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(Other: I) && (!Stop || !Stop->comesBefore(Other: I)))
810 return true;
811 if (!Stop && ExploreInterBlock) {
812 const ForwardContextTy &Context = getForwardContext(BB: PPBB);
813 auto It = Context.find(Key: IBB);
814 if (It != Context.end() && (!It->second || !It->second->comesBefore(Other: 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(Other: PP))
823 return true;
824 if (ExploreInterBlock && getBackwardContext(BB: PPBB).contains(key: IBB))
825 return true;
826 }
827 return false;
828}
829
830bool MustBeExecutedContextExplorer::checkForAllTerminatorsInContext(
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.
834 SmallPtrSet<const BasicBlock *, 16> Visited;
835 auto CheckBlock = [&](const BasicBlock *BB) {
836 if (!Visited.insert(Ptr: BB).second)
837 return true;
838 const Instruction *Term = BB->getTerminator();
839 return !isInContextOf(I: Term, PP) || Pred(Term);
840 };
841 const BasicBlock *PPBB = PP->getParent();
842 if (!CheckBlock(PPBB))
843 return false;
844 if (!ExploreInterBlock)
845 return true;
846 if (ExploreCFGForward && !getForwardStop(PP)) {
847 for (const auto &[BB, Stop] : getForwardContext(BB: PPBB)) {
848 if (!CheckBlock(BB))
849 return false;
850 }
851 }
852 if (ExploreCFGBackward) {
853 for (const BasicBlock *BB : getBackwardContext(BB: PPBB)) {
854 if (!CheckBlock(BB))
855 return false;
856 }
857 }
858 return true;
859}
860
861MustBeExecutedIterator::MustBeExecutedIterator(
862 MustBeExecutedContextExplorer &Explorer, const Instruction *I)
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(V: {I, ExplorationDirection::FORWARD});
878 Visited.insert(V: {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(It&: *this, PP: Head);
888 if (Head && Visited.insert(V: {Head, ExplorationDirection ::FORWARD}).second)
889 return Head;
890 Head = nullptr;
891
892 Tail = Explorer.getMustBeExecutedPrevInstruction(It&: *this, PP: Tail);
893 if (Tail && Visited.insert(V: {Tail, ExplorationDirection ::BACKWARD}).second)
894 return Tail;
895 Tail = nullptr;
896 return nullptr;
897}
898
899PreservedAnalyses MustExecutePrinterPass::run(Function &F,
900 FunctionAnalysisManager &AM) {
901 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
902 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
903
904 MustExecuteAnnotatedWriter Writer(F, DT, LI);
905 F.print(OS, AAW: &Writer);
906 return PreservedAnalyses::all();
907}
908
909PreservedAnalyses
910MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
911 FunctionAnalysisManager &FAM =
912 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
913 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
914 return &FAM.getResult<LoopAnalysis>(IR&: const_cast<Function &>(F));
915 };
916 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
917 return &FAM.getResult<DominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
918 };
919 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
920 return &FAM.getResult<PostDominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
921 };
922
923 MustBeExecutedContextExplorer Explorer(
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(PP: &I))
932 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
933 }
934 }
935 return PreservedAnalyses::all();
936}
937