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