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/StringExtras.h"
12#include "llvm/Analysis/CFG.h"
13#include "llvm/Analysis/InstructionSimplify.h"
14#include "llvm/Analysis/LoopInfo.h"
15#include "llvm/Analysis/PostDominators.h"
16#include "llvm/Analysis/ValueTracking.h"
17#include "llvm/IR/AssemblyAnnotationWriter.h"
18#include "llvm/IR/Dominators.h"
19#include "llvm/IR/InstIterator.h"
20#include "llvm/IR/Module.h"
21#include "llvm/IR/PassManager.h"
22#include "llvm/Support/FormattedStream.h"
23#include "llvm/Support/raw_ostream.h"
24
25using namespace llvm;
26
27#define DEBUG_TYPE "must-execute"
28
29const DenseMap<BasicBlock *, ColorVector> &
30LoopSafetyInfo::getBlockColors() const {
31 return BlockColors;
32}
33
34void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
35 ColorVector &ColorsForNewBlock = BlockColors[New];
36 ColorVector &ColorsForOldBlock = BlockColors[Old];
37 ColorsForNewBlock = ColorsForOldBlock;
38}
39
40bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
41 (void)BB;
42 return anyBlockMayThrow();
43}
44
45bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
46 return MayThrow;
47}
48
49void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
50 assert(CurLoop != nullptr && "CurLoop can't be null");
51 BasicBlock *Header = CurLoop->getHeader();
52 // Iterate over header and compute safety info.
53 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(BB: Header);
54 MayThrow = HeaderMayThrow;
55 // Iterate over loop instructions and compute safety info.
56 // Skip header as it has been computed and stored in HeaderMayThrow.
57 // The first block in loopinfo.Blocks is guaranteed to be the header.
58 assert(Header == *CurLoop->getBlocks().begin() &&
59 "First block must be header");
60 for (const BasicBlock *BB : llvm::drop_begin(RangeOrContainer: CurLoop->blocks())) {
61 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(BB);
62 if (MayThrow)
63 break;
64 }
65
66 computeBlockColors(CurLoop);
67}
68
69bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
70 return ICF.hasICF(BB);
71}
72
73bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
74 return MayThrow;
75}
76
77void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
78 assert(CurLoop != nullptr && "CurLoop can't be null");
79 ICF.clear();
80 MW.clear();
81 MayThrow = false;
82 // Figure out the fact that at least one block may throw.
83 for (const auto &BB : CurLoop->blocks())
84 if (ICF.hasICF(BB: &*BB)) {
85 MayThrow = true;
86 break;
87 }
88 computeBlockColors(CurLoop);
89}
90
91void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
92 const BasicBlock *BB) {
93 ICF.insertInstructionTo(Inst, BB);
94 MW.insertInstructionTo(Inst, BB);
95}
96
97void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
98 ICF.removeInstruction(Inst);
99 MW.removeInstruction(Inst);
100}
101
102void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
103 // Compute funclet colors if we might sink/hoist in a function with a funclet
104 // personality routine.
105 Function *Fn = CurLoop->getHeader()->getParent();
106 if (Fn->hasPersonalityFn())
107 if (Constant *PersonalityFn = Fn->getPersonalityFn())
108 if (isScopedEHPersonality(Pers: classifyEHPersonality(Pers: PersonalityFn)))
109 BlockColors = colorEHFunclets(F&: *Fn);
110}
111
112/// Return true if we can prove that the given ExitBlock is not reached on the
113/// first iteration of the given loop. That is, the backedge of the loop must
114/// be executed before the ExitBlock is executed in any dynamic execution trace.
115static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
116 const DominatorTree *DT,
117 const Loop *CurLoop) {
118 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
119 if (!CondExitBlock)
120 // expect unique exits
121 return false;
122 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
123 auto *BI = dyn_cast<CondBrInst>(Val: CondExitBlock->getTerminator());
124 if (!BI)
125 return false;
126 // If condition is constant and false leads to ExitBlock then we always
127 // execute the true branch.
128 if (auto *Cond = dyn_cast<ConstantInt>(Val: BI->getCondition()))
129 return BI->getSuccessor(i: Cond->getZExtValue() ? 1 : 0) == ExitBlock;
130 auto *Cond = dyn_cast<CmpInst>(Val: BI->getCondition());
131 if (!Cond)
132 return false;
133 // todo: this would be a lot more powerful if we used scev, but all the
134 // plumbing is currently missing to pass a pointer in from the pass
135 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
136 ICmpInst::Predicate Pred = Cond->getPredicate();
137 auto *LHS = dyn_cast<PHINode>(Val: Cond->getOperand(i_nocapture: 0));
138 auto *RHS = Cond->getOperand(i_nocapture: 1);
139 if (!LHS || LHS->getParent() != CurLoop->getHeader()) {
140 Pred = Cond->getSwappedPredicate();
141 LHS = dyn_cast<PHINode>(Val: Cond->getOperand(i_nocapture: 1));
142 RHS = Cond->getOperand(i_nocapture: 0);
143 if (!LHS || LHS->getParent() != CurLoop->getHeader())
144 return false;
145 }
146
147 auto DL = ExitBlock->getModule()->getDataLayout();
148 auto *IVStart = LHS->getIncomingValueForBlock(BB: CurLoop->getLoopPreheader());
149 auto *SimpleValOrNull = simplifyCmpInst(
150 Predicate: Pred, LHS: IVStart, RHS, Q: {DL, /*TLI*/ nullptr, DT, /*AC*/ nullptr, BI});
151 auto *SimpleCst = dyn_cast_or_null<Constant>(Val: SimpleValOrNull);
152 if (!SimpleCst)
153 return false;
154 if (ExitBlock == BI->getSuccessor(i: 0))
155 return SimpleCst->isNullValue();
156 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
157 return SimpleCst->isAllOnesValue();
158}
159
160/// Collect all blocks from \p CurLoop which lie on all possible paths from
161/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
162/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
163/// Note: It's possible that we encounter Irreducible control flow, due to
164/// which, we may find that a few predecessors of \p BB are not a part of the
165/// \p CurLoop. We only return Predecessors that are a part of \p CurLoop.
166static void collectTransitivePredecessors(
167 const Loop *CurLoop, const BasicBlock *BB,
168 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
169 assert(Predecessors.empty() && "Garbage in predecessors set?");
170 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
171 if (BB == CurLoop->getHeader())
172 return;
173 SmallVector<const BasicBlock *, 4> WorkList;
174 for (const auto *Pred : predecessors(BB)) {
175 if (!CurLoop->contains(BB: Pred))
176 continue;
177 Predecessors.insert(Ptr: Pred);
178 WorkList.push_back(Elt: Pred);
179 }
180 while (!WorkList.empty()) {
181 auto *Pred = WorkList.pop_back_val();
182 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
183 // We are not interested in backedges and we don't want to leave loop.
184 if (Pred == CurLoop->getHeader())
185 continue;
186 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
187 // blocks of this inner loop, even those that are always executed AFTER the
188 // BB. It may make our analysis more conservative than it could be, see test
189 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
190 // We can ignore backedge of all loops containing BB to get a sligtly more
191 // optimistic result.
192 for (const auto *PredPred : predecessors(BB: Pred))
193 if (CurLoop->contains(BB: PredPred) && Predecessors.insert(Ptr: PredPred).second)
194 WorkList.push_back(Elt: PredPred);
195 }
196}
197
198bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
199 const BasicBlock *BB,
200 const DominatorTree *DT) const {
201 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
202
203 // Fast path: header is always reached once the loop is entered.
204 if (BB == CurLoop->getHeader())
205 return true;
206
207 auto [It, Inserted] = GuaranteedToExecute.try_emplace(Key: BB, Args: false);
208 if (Inserted)
209 It->second = allLoopPathsLeadToBlockImpl(CurLoop, BB, DT);
210 return It->second;
211}
212
213bool LoopSafetyInfo::allLoopPathsLeadToBlockImpl(
214 const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const {
215 // Collect all transitive predecessors of BB in the same loop. This set will
216 // be a subset of the blocks within the loop.
217 SmallPtrSet<const BasicBlock *, 4> Predecessors;
218 collectTransitivePredecessors(CurLoop, BB, Predecessors);
219
220 // Bail out if a latch block is part of the predecessor set. In this case
221 // we may take the backedge to the header and not execute other latch
222 // successors.
223 for (const BasicBlock *Pred : predecessors(BB: CurLoop->getHeader()))
224 // Predecessors only contains loop blocks, so we don't have to worry about
225 // preheader predecessors here.
226 if (Predecessors.contains(Ptr: Pred))
227 return false;
228
229 // Make sure that all successors of, all predecessors of BB which are not
230 // dominated by BB, are either:
231 // 1) BB,
232 // 2) Also predecessors of BB,
233 // 3) Exit blocks which are not taken on 1st iteration.
234 // Memoize blocks we've already checked.
235 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
236 for (const auto *Pred : Predecessors) {
237 // Predecessor block may throw, so it has a side exit.
238 if (blockMayThrow(BB: Pred))
239 return false;
240
241 // BB dominates Pred, so if Pred runs, BB must run.
242 // This is true when Pred is a loop latch.
243 if (DT->dominates(A: BB, B: Pred))
244 continue;
245
246 for (const auto *Succ : successors(BB: Pred))
247 if (CheckedSuccessors.insert(Ptr: Succ).second &&
248 Succ != BB && !Predecessors.count(Ptr: Succ))
249 // By discharging conditions that are not executed on the 1st iteration,
250 // we guarantee that *at least* on the first iteration all paths from
251 // header that *may* execute will lead us to the block of interest. So
252 // that if we had virtually peeled one iteration away, in this peeled
253 // iteration the set of predecessors would contain only paths from
254 // header to BB without any exiting edges that may execute.
255 //
256 // TODO: We only do it for exiting edges currently. We could use the
257 // same function to skip some of the edges within the loop if we know
258 // that they will not be taken on the 1st iteration.
259 //
260 // TODO: If we somehow know the number of iterations in loop, the same
261 // check may be done for any arbitrary N-th iteration as long as N is
262 // not greater than minimum number of iterations in this loop.
263 if (CurLoop->contains(BB: Succ) ||
264 !CanProveNotTakenFirstIteration(ExitBlock: Succ, DT, CurLoop))
265 return false;
266 }
267
268 // All predecessors can only lead us to BB.
269 return true;
270}
271
272/// Returns true if the instruction in a loop is guaranteed to execute at least
273/// once.
274bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
275 const DominatorTree *DT,
276 const Loop *CurLoop) const {
277 // If the instruction is in the header block for the loop (which is very
278 // common), it is always guaranteed to dominate the exit blocks. Since this
279 // is a common case, and can save some work, check it now.
280 if (Inst.getParent() == CurLoop->getHeader())
281 // If there's a throw in the header block, we can't guarantee we'll reach
282 // Inst unless we can prove that Inst comes before the potential implicit
283 // exit. At the moment, we use a (cheap) hack for the common case where
284 // the instruction of interest is the first one in the block.
285 return !HeaderMayThrow ||
286 &*Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
287
288 // If there is a path from header to exit or latch that doesn't lead to our
289 // instruction's block, return false.
290 return allLoopPathsLeadToBlock(CurLoop, BB: Inst.getParent(), DT);
291}
292
293bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
294 const DominatorTree *DT,
295 const Loop *CurLoop) const {
296 return !ICF.isDominatedByICFIFromSameBlock(Insn: &Inst) &&
297 allLoopPathsLeadToBlock(CurLoop, BB: Inst.getParent(), DT);
298}
299
300bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
301 const Loop *CurLoop) const {
302 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
303
304 // Fast path: there are no instructions before header.
305 if (BB == CurLoop->getHeader())
306 return true;
307
308 // Collect all transitive predecessors of BB in the same loop. This set will
309 // be a subset of the blocks within the loop.
310 SmallPtrSet<const BasicBlock *, 4> Predecessors;
311 collectTransitivePredecessors(CurLoop, BB, Predecessors);
312 // Find if there any instruction in either predecessor that could write
313 // to memory.
314 for (const auto *Pred : Predecessors)
315 if (MW.mayWriteToMemory(BB: Pred))
316 return false;
317 return true;
318}
319
320bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
321 const Loop *CurLoop) const {
322 auto *BB = I.getParent();
323 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
324 return !MW.isDominatedByMemoryWriteFromSameBlock(Insn: &I) &&
325 doesNotWriteMemoryBefore(BB, CurLoop);
326}
327
328static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
329 // TODO: merge these two routines. For the moment, we display the best
330 // result obtained by *either* implementation. This is a bit unfair since no
331 // caller actually gets the full power at the moment.
332 SimpleLoopSafetyInfo LSI;
333 LSI.computeLoopSafetyInfo(CurLoop: L);
334 return LSI.isGuaranteedToExecute(Inst: I, DT, CurLoop: L) ||
335 isGuaranteedToExecuteForEveryIteration(I: &I, L);
336}
337
338namespace {
339/// An assembly annotator class to print must execute information in
340/// comments.
341class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
342 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
343
344public:
345 MustExecuteAnnotatedWriter(const Function &F,
346 DominatorTree &DT, LoopInfo &LI) {
347 for (const auto &I: instructions(F)) {
348 Loop *L = LI.getLoopFor(BB: I.getParent());
349 while (L) {
350 if (isMustExecuteIn(I, L, DT: &DT)) {
351 MustExec[&I].push_back(Elt: L);
352 }
353 L = L->getParentLoop();
354 };
355 }
356 }
357 MustExecuteAnnotatedWriter(const Module &M,
358 DominatorTree &DT, LoopInfo &LI) {
359 for (const auto &F : M)
360 for (const auto &I: instructions(F)) {
361 Loop *L = LI.getLoopFor(BB: I.getParent());
362 while (L) {
363 if (isMustExecuteIn(I, L, DT: &DT)) {
364 MustExec[&I].push_back(Elt: L);
365 }
366 L = L->getParentLoop();
367 };
368 }
369 }
370
371
372 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
373 if (!MustExec.count(Val: &V))
374 return;
375
376 const auto &Loops = MustExec.lookup(Val: &V);
377 const auto NumLoops = Loops.size();
378 if (NumLoops > 1)
379 OS << " ; (mustexec in " << NumLoops << " loops: ";
380 else
381 OS << " ; (mustexec in: ";
382
383 ListSeparator LS;
384 for (const Loop *L : Loops)
385 OS << LS << L->getHeader()->getName();
386 OS << ")";
387 }
388};
389} // namespace
390
391/// Return true if \p L might be an endless loop.
392static bool maybeEndlessLoop(const Loop &L) {
393 if (L.getHeader()->getParent()->hasFnAttribute(Kind: Attribute::WillReturn))
394 return false;
395 // TODO: Actually try to prove it is not.
396 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
397 return true;
398}
399
400bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
401 if (!LI)
402 return false;
403 using RPOTraversal = ReversePostOrderTraversal<const Function *>;
404 RPOTraversal FuncRPOT(&F);
405 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
406 const LoopInfo>(RPOTraversal: FuncRPOT, LI: *LI);
407}
408
409/// Lookup \p Key in \p Map and return the result, potentially after
410/// initializing the optional through \p Fn(\p args).
411template <typename K, typename V, typename FnTy, typename... ArgsTy>
412static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
413 FnTy &&Fn, ArgsTy &&...args) {
414 std::optional<V> &OptVal = Map[Key];
415 if (!OptVal)
416 OptVal = Fn(std::forward<ArgsTy>(args)...);
417 return *OptVal;
418}
419
420const BasicBlock *
421MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
422 const LoopInfo *LI = LIGetter(*InitBB->getParent());
423 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
424
425 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
426 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
427
428 const Function &F = *InitBB->getParent();
429 const Loop *L = LI ? LI->getLoopFor(BB: InitBB) : nullptr;
430 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
431 bool WillReturnAndNoThrow = (F.hasFnAttribute(Kind: Attribute::WillReturn) ||
432 (L && !maybeEndlessLoop(L: *L))) &&
433 F.doesNotThrow();
434 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
435 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
436 << "\n");
437
438 // Determine the adjacent blocks in the given direction but exclude (self)
439 // loops under certain circumstances.
440 SmallVector<const BasicBlock *, 8> Worklist;
441 for (const BasicBlock *SuccBB : successors(BB: InitBB)) {
442 bool IsLatch = SuccBB == HeaderBB;
443 // Loop latches are ignored in forward propagation if the loop cannot be
444 // endless and may not throw: control has to go somewhere.
445 if (!WillReturnAndNoThrow || !IsLatch)
446 Worklist.push_back(Elt: SuccBB);
447 }
448 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
449
450 // If there are no other adjacent blocks, there is no join point.
451 if (Worklist.empty())
452 return nullptr;
453
454 // If there is one adjacent block, it is the join point.
455 if (Worklist.size() == 1)
456 return Worklist[0];
457
458 // Try to determine a join block through the help of the post-dominance
459 // tree. If no tree was provided, we perform simple pattern matching for one
460 // block conditionals and one block loops only.
461 const BasicBlock *JoinBB = nullptr;
462 if (PDT)
463 if (const auto *InitNode = PDT->getNode(BB: InitBB))
464 if (const auto *IDomNode = InitNode->getIDom())
465 JoinBB = IDomNode->getBlock();
466
467 if (!JoinBB && Worklist.size() == 2) {
468 const BasicBlock *Succ0 = Worklist[0];
469 const BasicBlock *Succ1 = Worklist[1];
470 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
471 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
472 if (Succ0UniqueSucc == InitBB) {
473 // InitBB -> Succ0 -> InitBB
474 // InitBB -> Succ1 = JoinBB
475 JoinBB = Succ1;
476 } else if (Succ1UniqueSucc == InitBB) {
477 // InitBB -> Succ1 -> InitBB
478 // InitBB -> Succ0 = JoinBB
479 JoinBB = Succ0;
480 } else if (Succ0 == Succ1UniqueSucc) {
481 // InitBB -> Succ0 = JoinBB
482 // InitBB -> Succ1 -> Succ0 = JoinBB
483 JoinBB = Succ0;
484 } else if (Succ1 == Succ0UniqueSucc) {
485 // InitBB -> Succ0 -> Succ1 = JoinBB
486 // InitBB -> Succ1 = JoinBB
487 JoinBB = Succ1;
488 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
489 // InitBB -> Succ0 -> JoinBB
490 // InitBB -> Succ1 -> JoinBB
491 JoinBB = Succ0UniqueSucc;
492 }
493 }
494
495 if (!JoinBB && L)
496 JoinBB = L->getUniqueExitBlock();
497
498 if (!JoinBB)
499 return nullptr;
500
501 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
502
503 // In forward direction we check if control will for sure reach JoinBB from
504 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
505 // are: infinite loops and instructions that do not necessarily transfer
506 // execution to their successor. To check for them we traverse the CFG from
507 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
508
509 // If we know the function is "will-return" and "no-throw" there is no need
510 // for futher checks.
511 if (!F.hasFnAttribute(Kind: Attribute::WillReturn) || !F.doesNotThrow()) {
512
513 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
514 return isGuaranteedToTransferExecutionToSuccessor(BB);
515 };
516
517 SmallPtrSet<const BasicBlock *, 16> Visited;
518 while (!Worklist.empty()) {
519 const BasicBlock *ToBB = Worklist.pop_back_val();
520 if (ToBB == JoinBB)
521 continue;
522
523 // Make sure all loops in-between are finite.
524 if (!Visited.insert(Ptr: ToBB).second) {
525 if (!F.hasFnAttribute(Kind: Attribute::WillReturn)) {
526 if (!LI)
527 return nullptr;
528
529 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
530 Key: &F, Map&: IrreducibleControlMap, Fn&: mayContainIrreducibleControl, args: F, args&: LI);
531 if (MayContainIrreducibleControl)
532 return nullptr;
533
534 const Loop *L = LI->getLoopFor(BB: ToBB);
535 if (L && maybeEndlessLoop(L: *L))
536 return nullptr;
537 }
538
539 continue;
540 }
541
542 // Make sure the block has no instructions that could stop control
543 // transfer.
544 bool TransfersExecution = getOrCreateCachedOptional(
545 Key: ToBB, Map&: BlockTransferMap, Fn&: BlockTransfersExecutionToSuccessor, args&: ToBB);
546 if (!TransfersExecution)
547 return nullptr;
548
549 append_range(C&: Worklist, R: successors(BB: ToBB));
550 }
551 }
552
553 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
554 return JoinBB;
555}
556const BasicBlock *
557MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
558 const LoopInfo *LI = LIGetter(*InitBB->getParent());
559 const DominatorTree *DT = DTGetter(*InitBB->getParent());
560 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
561 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
562
563 // Try to determine a join block through the help of the dominance tree. If no
564 // tree was provided, we perform simple pattern matching for one block
565 // conditionals only.
566 if (DT)
567 if (const auto *InitNode = DT->getNode(BB: InitBB))
568 if (const auto *IDomNode = InitNode->getIDom())
569 return IDomNode->getBlock();
570
571 const Loop *L = LI ? LI->getLoopFor(BB: InitBB) : nullptr;
572 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
573
574 // Determine the predecessor blocks but ignore backedges.
575 SmallVector<const BasicBlock *, 8> Worklist;
576 for (const BasicBlock *PredBB : predecessors(BB: InitBB)) {
577 bool IsBackedge =
578 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(BB: PredBB));
579 // Loop backedges are ignored in backwards propagation: control has to come
580 // from somewhere.
581 if (!IsBackedge)
582 Worklist.push_back(Elt: PredBB);
583 }
584
585 // If there are no other predecessor blocks, there is no join point.
586 if (Worklist.empty())
587 return nullptr;
588
589 // If there is one predecessor block, it is the join point.
590 if (Worklist.size() == 1)
591 return Worklist[0];
592
593 const BasicBlock *JoinBB = nullptr;
594 if (Worklist.size() == 2) {
595 const BasicBlock *Pred0 = Worklist[0];
596 const BasicBlock *Pred1 = Worklist[1];
597 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
598 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
599 if (Pred0 == Pred1UniquePred) {
600 // InitBB <- Pred0 = JoinBB
601 // InitBB <- Pred1 <- Pred0 = JoinBB
602 JoinBB = Pred0;
603 } else if (Pred1 == Pred0UniquePred) {
604 // InitBB <- Pred0 <- Pred1 = JoinBB
605 // InitBB <- Pred1 = JoinBB
606 JoinBB = Pred1;
607 } else if (Pred0UniquePred == Pred1UniquePred) {
608 // InitBB <- Pred0 <- JoinBB
609 // InitBB <- Pred1 <- JoinBB
610 JoinBB = Pred0UniquePred;
611 }
612 }
613
614 if (!JoinBB && L)
615 JoinBB = L->getHeader();
616
617 // In backwards direction there is no need to show termination of previous
618 // instructions. If they do not terminate, the code afterward is dead, making
619 // any information/transformation correct anyway.
620 return JoinBB;
621}
622
623const Instruction *
624MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
625 MustBeExecutedIterator &It, const Instruction *PP) {
626 if (!PP)
627 return PP;
628 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
629
630 // If we explore only inside a given basic block we stop at terminators.
631 if (!ExploreInterBlock && PP->isTerminator()) {
632 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
633 return nullptr;
634 }
635
636 // If we do not traverse the call graph we check if we can make progress in
637 // the current function. First, check if the instruction is guaranteed to
638 // transfer execution to the successor.
639 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(I: PP);
640 if (!TransfersExecution)
641 return nullptr;
642
643 // If this is not a terminator we know that there is a single instruction
644 // after this one that is executed next if control is transfered. If not,
645 // we can try to go back to a call site we entered earlier. If none exists, we
646 // do not know any instruction that has to be executd next.
647 if (!PP->isTerminator()) {
648 const Instruction *NextPP = PP->getNextNode();
649 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
650 return NextPP;
651 }
652
653 // Finally, we have to handle terminators, trivial ones first.
654 assert(PP->isTerminator() && "Expected a terminator!");
655
656 // A terminator without a successor is not handled yet.
657 if (PP->getNumSuccessors() == 0) {
658 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
659 return nullptr;
660 }
661
662 // A terminator with a single successor, we will continue at the beginning of
663 // that one.
664 if (PP->getNumSuccessors() == 1) {
665 LLVM_DEBUG(
666 dbgs() << "\tUnconditional terminator, continue with successor\n");
667 return &PP->getSuccessor(Idx: 0)->front();
668 }
669
670 // Multiple successors mean we need to find the join point where control flow
671 // converges again. We use the findForwardJoinPoint helper function with
672 // information about the function and helper analyses, if available.
673 if (const BasicBlock *JoinBB = findForwardJoinPoint(InitBB: PP->getParent()))
674 return &JoinBB->front();
675
676 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
677 return nullptr;
678}
679
680const Instruction *
681MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
682 MustBeExecutedIterator &It, const Instruction *PP) {
683 if (!PP)
684 return PP;
685
686 bool IsFirst = !(PP->getPrevNode());
687 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
688 << (IsFirst ? " [IsFirst]" : "") << "\n");
689
690 // If we explore only inside a given basic block we stop at the first
691 // instruction.
692 if (!ExploreInterBlock && IsFirst) {
693 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
694 return nullptr;
695 }
696
697 // The block and function that contains the current position.
698 const BasicBlock *PPBlock = PP->getParent();
699
700 // If we are inside a block we know what instruction was executed before, the
701 // previous one.
702 if (!IsFirst) {
703 const Instruction *PrevPP = PP->getPrevNode();
704 LLVM_DEBUG(
705 dbgs() << "\tIntermediate instruction, continue with previous\n");
706 // We did not enter a callee so we simply return the previous instruction.
707 return PrevPP;
708 }
709
710 // Finally, we have to handle the case where the program point is the first in
711 // a block but not in the function. We use the findBackwardJoinPoint helper
712 // function with information about the function and helper analyses, if
713 // available.
714 if (const BasicBlock *JoinBB = findBackwardJoinPoint(InitBB: PPBlock))
715 return &JoinBB->back();
716
717 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
718 return nullptr;
719}
720
721MustBeExecutedIterator::MustBeExecutedIterator(
722 MustBeExecutedContextExplorer &Explorer, const Instruction *I)
723 : Explorer(Explorer), CurInst(I) {
724 reset(I);
725}
726
727void MustBeExecutedIterator::reset(const Instruction *I) {
728 Visited.clear();
729 resetInstruction(I);
730}
731
732void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
733 CurInst = I;
734 Head = Tail = nullptr;
735 Visited.insert(V: {I, ExplorationDirection::FORWARD});
736 Visited.insert(V: {I, ExplorationDirection::BACKWARD});
737 if (Explorer.ExploreCFGForward)
738 Head = I;
739 if (Explorer.ExploreCFGBackward)
740 Tail = I;
741}
742
743const Instruction *MustBeExecutedIterator::advance() {
744 assert(CurInst && "Cannot advance an end iterator!");
745 Head = Explorer.getMustBeExecutedNextInstruction(It&: *this, PP: Head);
746 if (Head && Visited.insert(V: {Head, ExplorationDirection ::FORWARD}).second)
747 return Head;
748 Head = nullptr;
749
750 Tail = Explorer.getMustBeExecutedPrevInstruction(It&: *this, PP: Tail);
751 if (Tail && Visited.insert(V: {Tail, ExplorationDirection ::BACKWARD}).second)
752 return Tail;
753 Tail = nullptr;
754 return nullptr;
755}
756
757PreservedAnalyses MustExecutePrinterPass::run(Function &F,
758 FunctionAnalysisManager &AM) {
759 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
760 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
761
762 MustExecuteAnnotatedWriter Writer(F, DT, LI);
763 F.print(OS, AAW: &Writer);
764 return PreservedAnalyses::all();
765}
766
767PreservedAnalyses
768MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
769 FunctionAnalysisManager &FAM =
770 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
771 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
772 return &FAM.getResult<LoopAnalysis>(IR&: const_cast<Function &>(F));
773 };
774 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
775 return &FAM.getResult<DominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
776 };
777 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
778 return &FAM.getResult<PostDominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
779 };
780
781 MustBeExecutedContextExplorer Explorer(
782 /* ExploreInterBlock */ true,
783 /* ExploreCFGForward */ true,
784 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
785
786 for (Function &F : M) {
787 for (Instruction &I : instructions(F)) {
788 OS << "-- Explore context of: " << I << "\n";
789 for (const Instruction *CI : Explorer.range(PP: &I))
790 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
791 }
792 }
793 return PreservedAnalyses::all();
794}
795