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<BranchInst>(Val: CondExitBlock->getTerminator());
124 if (!BI || !BI->isConditional())
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->isZeroValue();
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 // Collect all transitive predecessors of BB in the same loop. This set will
208 // be a subset of the blocks within the loop.
209 SmallPtrSet<const BasicBlock *, 4> Predecessors;
210 collectTransitivePredecessors(CurLoop, BB, Predecessors);
211
212 // Bail out if a latch block is part of the predecessor set. In this case
213 // we may take the backedge to the header and not execute other latch
214 // successors.
215 for (const BasicBlock *Pred : predecessors(BB: CurLoop->getHeader()))
216 // Predecessors only contains loop blocks, so we don't have to worry about
217 // preheader predecessors here.
218 if (Predecessors.contains(Ptr: Pred))
219 return false;
220
221 // Make sure that all successors of, all predecessors of BB which are not
222 // dominated by BB, are either:
223 // 1) BB,
224 // 2) Also predecessors of BB,
225 // 3) Exit blocks which are not taken on 1st iteration.
226 // Memoize blocks we've already checked.
227 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
228 for (const auto *Pred : Predecessors) {
229 // Predecessor block may throw, so it has a side exit.
230 if (blockMayThrow(BB: Pred))
231 return false;
232
233 // BB dominates Pred, so if Pred runs, BB must run.
234 // This is true when Pred is a loop latch.
235 if (DT->dominates(A: BB, B: Pred))
236 continue;
237
238 for (const auto *Succ : successors(BB: Pred))
239 if (CheckedSuccessors.insert(Ptr: Succ).second &&
240 Succ != BB && !Predecessors.count(Ptr: Succ))
241 // By discharging conditions that are not executed on the 1st iteration,
242 // we guarantee that *at least* on the first iteration all paths from
243 // header that *may* execute will lead us to the block of interest. So
244 // that if we had virtually peeled one iteration away, in this peeled
245 // iteration the set of predecessors would contain only paths from
246 // header to BB without any exiting edges that may execute.
247 //
248 // TODO: We only do it for exiting edges currently. We could use the
249 // same function to skip some of the edges within the loop if we know
250 // that they will not be taken on the 1st iteration.
251 //
252 // TODO: If we somehow know the number of iterations in loop, the same
253 // check may be done for any arbitrary N-th iteration as long as N is
254 // not greater than minimum number of iterations in this loop.
255 if (CurLoop->contains(BB: Succ) ||
256 !CanProveNotTakenFirstIteration(ExitBlock: Succ, DT, CurLoop))
257 return false;
258 }
259
260 // All predecessors can only lead us to BB.
261 return true;
262}
263
264/// Returns true if the instruction in a loop is guaranteed to execute at least
265/// once.
266bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
267 const DominatorTree *DT,
268 const Loop *CurLoop) const {
269 // If the instruction is in the header block for the loop (which is very
270 // common), it is always guaranteed to dominate the exit blocks. Since this
271 // is a common case, and can save some work, check it now.
272 if (Inst.getParent() == CurLoop->getHeader())
273 // If there's a throw in the header block, we can't guarantee we'll reach
274 // Inst unless we can prove that Inst comes before the potential implicit
275 // exit. At the moment, we use a (cheap) hack for the common case where
276 // the instruction of interest is the first one in the block.
277 return !HeaderMayThrow ||
278 &*Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
279
280 // If there is a path from header to exit or latch that doesn't lead to our
281 // instruction's block, return false.
282 return allLoopPathsLeadToBlock(CurLoop, BB: Inst.getParent(), DT);
283}
284
285bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
286 const DominatorTree *DT,
287 const Loop *CurLoop) const {
288 return !ICF.isDominatedByICFIFromSameBlock(Insn: &Inst) &&
289 allLoopPathsLeadToBlock(CurLoop, BB: Inst.getParent(), DT);
290}
291
292bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
293 const Loop *CurLoop) const {
294 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
295
296 // Fast path: there are no instructions before header.
297 if (BB == CurLoop->getHeader())
298 return true;
299
300 // Collect all transitive predecessors of BB in the same loop. This set will
301 // be a subset of the blocks within the loop.
302 SmallPtrSet<const BasicBlock *, 4> Predecessors;
303 collectTransitivePredecessors(CurLoop, BB, Predecessors);
304 // Find if there any instruction in either predecessor that could write
305 // to memory.
306 for (const auto *Pred : Predecessors)
307 if (MW.mayWriteToMemory(BB: Pred))
308 return false;
309 return true;
310}
311
312bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
313 const Loop *CurLoop) const {
314 auto *BB = I.getParent();
315 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
316 return !MW.isDominatedByMemoryWriteFromSameBlock(Insn: &I) &&
317 doesNotWriteMemoryBefore(BB, CurLoop);
318}
319
320static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
321 // TODO: merge these two routines. For the moment, we display the best
322 // result obtained by *either* implementation. This is a bit unfair since no
323 // caller actually gets the full power at the moment.
324 SimpleLoopSafetyInfo LSI;
325 LSI.computeLoopSafetyInfo(CurLoop: L);
326 return LSI.isGuaranteedToExecute(Inst: I, DT, CurLoop: L) ||
327 isGuaranteedToExecuteForEveryIteration(I: &I, L);
328}
329
330namespace {
331/// An assembly annotator class to print must execute information in
332/// comments.
333class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
334 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
335
336public:
337 MustExecuteAnnotatedWriter(const Function &F,
338 DominatorTree &DT, LoopInfo &LI) {
339 for (const auto &I: instructions(F)) {
340 Loop *L = LI.getLoopFor(BB: I.getParent());
341 while (L) {
342 if (isMustExecuteIn(I, L, DT: &DT)) {
343 MustExec[&I].push_back(Elt: L);
344 }
345 L = L->getParentLoop();
346 };
347 }
348 }
349 MustExecuteAnnotatedWriter(const Module &M,
350 DominatorTree &DT, LoopInfo &LI) {
351 for (const auto &F : M)
352 for (const auto &I: instructions(F)) {
353 Loop *L = LI.getLoopFor(BB: I.getParent());
354 while (L) {
355 if (isMustExecuteIn(I, L, DT: &DT)) {
356 MustExec[&I].push_back(Elt: L);
357 }
358 L = L->getParentLoop();
359 };
360 }
361 }
362
363
364 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
365 if (!MustExec.count(Val: &V))
366 return;
367
368 const auto &Loops = MustExec.lookup(Val: &V);
369 const auto NumLoops = Loops.size();
370 if (NumLoops > 1)
371 OS << " ; (mustexec in " << NumLoops << " loops: ";
372 else
373 OS << " ; (mustexec in: ";
374
375 ListSeparator LS;
376 for (const Loop *L : Loops)
377 OS << LS << L->getHeader()->getName();
378 OS << ")";
379 }
380};
381} // namespace
382
383/// Return true if \p L might be an endless loop.
384static bool maybeEndlessLoop(const Loop &L) {
385 if (L.getHeader()->getParent()->hasFnAttribute(Kind: Attribute::WillReturn))
386 return false;
387 // TODO: Actually try to prove it is not.
388 // TODO: If maybeEndlessLoop is going to be expensive, cache it.
389 return true;
390}
391
392bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
393 if (!LI)
394 return false;
395 using RPOTraversal = ReversePostOrderTraversal<const Function *>;
396 RPOTraversal FuncRPOT(&F);
397 return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
398 const LoopInfo>(RPOTraversal: FuncRPOT, LI: *LI);
399}
400
401/// Lookup \p Key in \p Map and return the result, potentially after
402/// initializing the optional through \p Fn(\p args).
403template <typename K, typename V, typename FnTy, typename... ArgsTy>
404static V getOrCreateCachedOptional(K Key, DenseMap<K, std::optional<V>> &Map,
405 FnTy &&Fn, ArgsTy &&...args) {
406 std::optional<V> &OptVal = Map[Key];
407 if (!OptVal)
408 OptVal = Fn(std::forward<ArgsTy>(args)...);
409 return *OptVal;
410}
411
412const BasicBlock *
413MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
414 const LoopInfo *LI = LIGetter(*InitBB->getParent());
415 const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
416
417 LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
418 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
419
420 const Function &F = *InitBB->getParent();
421 const Loop *L = LI ? LI->getLoopFor(BB: InitBB) : nullptr;
422 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
423 bool WillReturnAndNoThrow = (F.hasFnAttribute(Kind: Attribute::WillReturn) ||
424 (L && !maybeEndlessLoop(L: *L))) &&
425 F.doesNotThrow();
426 LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
427 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
428 << "\n");
429
430 // Determine the adjacent blocks in the given direction but exclude (self)
431 // loops under certain circumstances.
432 SmallVector<const BasicBlock *, 8> Worklist;
433 for (const BasicBlock *SuccBB : successors(BB: InitBB)) {
434 bool IsLatch = SuccBB == HeaderBB;
435 // Loop latches are ignored in forward propagation if the loop cannot be
436 // endless and may not throw: control has to go somewhere.
437 if (!WillReturnAndNoThrow || !IsLatch)
438 Worklist.push_back(Elt: SuccBB);
439 }
440 LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
441
442 // If there are no other adjacent blocks, there is no join point.
443 if (Worklist.empty())
444 return nullptr;
445
446 // If there is one adjacent block, it is the join point.
447 if (Worklist.size() == 1)
448 return Worklist[0];
449
450 // Try to determine a join block through the help of the post-dominance
451 // tree. If no tree was provided, we perform simple pattern matching for one
452 // block conditionals and one block loops only.
453 const BasicBlock *JoinBB = nullptr;
454 if (PDT)
455 if (const auto *InitNode = PDT->getNode(BB: InitBB))
456 if (const auto *IDomNode = InitNode->getIDom())
457 JoinBB = IDomNode->getBlock();
458
459 if (!JoinBB && Worklist.size() == 2) {
460 const BasicBlock *Succ0 = Worklist[0];
461 const BasicBlock *Succ1 = Worklist[1];
462 const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
463 const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
464 if (Succ0UniqueSucc == InitBB) {
465 // InitBB -> Succ0 -> InitBB
466 // InitBB -> Succ1 = JoinBB
467 JoinBB = Succ1;
468 } else if (Succ1UniqueSucc == InitBB) {
469 // InitBB -> Succ1 -> InitBB
470 // InitBB -> Succ0 = JoinBB
471 JoinBB = Succ0;
472 } else if (Succ0 == Succ1UniqueSucc) {
473 // InitBB -> Succ0 = JoinBB
474 // InitBB -> Succ1 -> Succ0 = JoinBB
475 JoinBB = Succ0;
476 } else if (Succ1 == Succ0UniqueSucc) {
477 // InitBB -> Succ0 -> Succ1 = JoinBB
478 // InitBB -> Succ1 = JoinBB
479 JoinBB = Succ1;
480 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
481 // InitBB -> Succ0 -> JoinBB
482 // InitBB -> Succ1 -> JoinBB
483 JoinBB = Succ0UniqueSucc;
484 }
485 }
486
487 if (!JoinBB && L)
488 JoinBB = L->getUniqueExitBlock();
489
490 if (!JoinBB)
491 return nullptr;
492
493 LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
494
495 // In forward direction we check if control will for sure reach JoinBB from
496 // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
497 // are: infinite loops and instructions that do not necessarily transfer
498 // execution to their successor. To check for them we traverse the CFG from
499 // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
500
501 // If we know the function is "will-return" and "no-throw" there is no need
502 // for futher checks.
503 if (!F.hasFnAttribute(Kind: Attribute::WillReturn) || !F.doesNotThrow()) {
504
505 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
506 return isGuaranteedToTransferExecutionToSuccessor(BB);
507 };
508
509 SmallPtrSet<const BasicBlock *, 16> Visited;
510 while (!Worklist.empty()) {
511 const BasicBlock *ToBB = Worklist.pop_back_val();
512 if (ToBB == JoinBB)
513 continue;
514
515 // Make sure all loops in-between are finite.
516 if (!Visited.insert(Ptr: ToBB).second) {
517 if (!F.hasFnAttribute(Kind: Attribute::WillReturn)) {
518 if (!LI)
519 return nullptr;
520
521 bool MayContainIrreducibleControl = getOrCreateCachedOptional(
522 Key: &F, Map&: IrreducibleControlMap, Fn&: mayContainIrreducibleControl, args: F, args&: LI);
523 if (MayContainIrreducibleControl)
524 return nullptr;
525
526 const Loop *L = LI->getLoopFor(BB: ToBB);
527 if (L && maybeEndlessLoop(L: *L))
528 return nullptr;
529 }
530
531 continue;
532 }
533
534 // Make sure the block has no instructions that could stop control
535 // transfer.
536 bool TransfersExecution = getOrCreateCachedOptional(
537 Key: ToBB, Map&: BlockTransferMap, Fn&: BlockTransfersExecutionToSuccessor, args&: ToBB);
538 if (!TransfersExecution)
539 return nullptr;
540
541 append_range(C&: Worklist, R: successors(BB: ToBB));
542 }
543 }
544
545 LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
546 return JoinBB;
547}
548const BasicBlock *
549MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
550 const LoopInfo *LI = LIGetter(*InitBB->getParent());
551 const DominatorTree *DT = DTGetter(*InitBB->getParent());
552 LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
553 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
554
555 // Try to determine a join block through the help of the dominance tree. If no
556 // tree was provided, we perform simple pattern matching for one block
557 // conditionals only.
558 if (DT)
559 if (const auto *InitNode = DT->getNode(BB: InitBB))
560 if (const auto *IDomNode = InitNode->getIDom())
561 return IDomNode->getBlock();
562
563 const Loop *L = LI ? LI->getLoopFor(BB: InitBB) : nullptr;
564 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
565
566 // Determine the predecessor blocks but ignore backedges.
567 SmallVector<const BasicBlock *, 8> Worklist;
568 for (const BasicBlock *PredBB : predecessors(BB: InitBB)) {
569 bool IsBackedge =
570 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(BB: PredBB));
571 // Loop backedges are ignored in backwards propagation: control has to come
572 // from somewhere.
573 if (!IsBackedge)
574 Worklist.push_back(Elt: PredBB);
575 }
576
577 // If there are no other predecessor blocks, there is no join point.
578 if (Worklist.empty())
579 return nullptr;
580
581 // If there is one predecessor block, it is the join point.
582 if (Worklist.size() == 1)
583 return Worklist[0];
584
585 const BasicBlock *JoinBB = nullptr;
586 if (Worklist.size() == 2) {
587 const BasicBlock *Pred0 = Worklist[0];
588 const BasicBlock *Pred1 = Worklist[1];
589 const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
590 const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
591 if (Pred0 == Pred1UniquePred) {
592 // InitBB <- Pred0 = JoinBB
593 // InitBB <- Pred1 <- Pred0 = JoinBB
594 JoinBB = Pred0;
595 } else if (Pred1 == Pred0UniquePred) {
596 // InitBB <- Pred0 <- Pred1 = JoinBB
597 // InitBB <- Pred1 = JoinBB
598 JoinBB = Pred1;
599 } else if (Pred0UniquePred == Pred1UniquePred) {
600 // InitBB <- Pred0 <- JoinBB
601 // InitBB <- Pred1 <- JoinBB
602 JoinBB = Pred0UniquePred;
603 }
604 }
605
606 if (!JoinBB && L)
607 JoinBB = L->getHeader();
608
609 // In backwards direction there is no need to show termination of previous
610 // instructions. If they do not terminate, the code afterward is dead, making
611 // any information/transformation correct anyway.
612 return JoinBB;
613}
614
615const Instruction *
616MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
617 MustBeExecutedIterator &It, const Instruction *PP) {
618 if (!PP)
619 return PP;
620 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
621
622 // If we explore only inside a given basic block we stop at terminators.
623 if (!ExploreInterBlock && PP->isTerminator()) {
624 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
625 return nullptr;
626 }
627
628 // If we do not traverse the call graph we check if we can make progress in
629 // the current function. First, check if the instruction is guaranteed to
630 // transfer execution to the successor.
631 bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(I: PP);
632 if (!TransfersExecution)
633 return nullptr;
634
635 // If this is not a terminator we know that there is a single instruction
636 // after this one that is executed next if control is transfered. If not,
637 // we can try to go back to a call site we entered earlier. If none exists, we
638 // do not know any instruction that has to be executd next.
639 if (!PP->isTerminator()) {
640 const Instruction *NextPP = PP->getNextNode();
641 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
642 return NextPP;
643 }
644
645 // Finally, we have to handle terminators, trivial ones first.
646 assert(PP->isTerminator() && "Expected a terminator!");
647
648 // A terminator without a successor is not handled yet.
649 if (PP->getNumSuccessors() == 0) {
650 LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
651 return nullptr;
652 }
653
654 // A terminator with a single successor, we will continue at the beginning of
655 // that one.
656 if (PP->getNumSuccessors() == 1) {
657 LLVM_DEBUG(
658 dbgs() << "\tUnconditional terminator, continue with successor\n");
659 return &PP->getSuccessor(Idx: 0)->front();
660 }
661
662 // Multiple successors mean we need to find the join point where control flow
663 // converges again. We use the findForwardJoinPoint helper function with
664 // information about the function and helper analyses, if available.
665 if (const BasicBlock *JoinBB = findForwardJoinPoint(InitBB: PP->getParent()))
666 return &JoinBB->front();
667
668 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
669 return nullptr;
670}
671
672const Instruction *
673MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
674 MustBeExecutedIterator &It, const Instruction *PP) {
675 if (!PP)
676 return PP;
677
678 bool IsFirst = !(PP->getPrevNode());
679 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
680 << (IsFirst ? " [IsFirst]" : "") << "\n");
681
682 // If we explore only inside a given basic block we stop at the first
683 // instruction.
684 if (!ExploreInterBlock && IsFirst) {
685 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
686 return nullptr;
687 }
688
689 // The block and function that contains the current position.
690 const BasicBlock *PPBlock = PP->getParent();
691
692 // If we are inside a block we know what instruction was executed before, the
693 // previous one.
694 if (!IsFirst) {
695 const Instruction *PrevPP = PP->getPrevNode();
696 LLVM_DEBUG(
697 dbgs() << "\tIntermediate instruction, continue with previous\n");
698 // We did not enter a callee so we simply return the previous instruction.
699 return PrevPP;
700 }
701
702 // Finally, we have to handle the case where the program point is the first in
703 // a block but not in the function. We use the findBackwardJoinPoint helper
704 // function with information about the function and helper analyses, if
705 // available.
706 if (const BasicBlock *JoinBB = findBackwardJoinPoint(InitBB: PPBlock))
707 return &JoinBB->back();
708
709 LLVM_DEBUG(dbgs() << "\tNo join point found\n");
710 return nullptr;
711}
712
713MustBeExecutedIterator::MustBeExecutedIterator(
714 MustBeExecutedContextExplorer &Explorer, const Instruction *I)
715 : Explorer(Explorer), CurInst(I) {
716 reset(I);
717}
718
719void MustBeExecutedIterator::reset(const Instruction *I) {
720 Visited.clear();
721 resetInstruction(I);
722}
723
724void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
725 CurInst = I;
726 Head = Tail = nullptr;
727 Visited.insert(V: {I, ExplorationDirection::FORWARD});
728 Visited.insert(V: {I, ExplorationDirection::BACKWARD});
729 if (Explorer.ExploreCFGForward)
730 Head = I;
731 if (Explorer.ExploreCFGBackward)
732 Tail = I;
733}
734
735const Instruction *MustBeExecutedIterator::advance() {
736 assert(CurInst && "Cannot advance an end iterator!");
737 Head = Explorer.getMustBeExecutedNextInstruction(It&: *this, PP: Head);
738 if (Head && Visited.insert(V: {Head, ExplorationDirection ::FORWARD}).second)
739 return Head;
740 Head = nullptr;
741
742 Tail = Explorer.getMustBeExecutedPrevInstruction(It&: *this, PP: Tail);
743 if (Tail && Visited.insert(V: {Tail, ExplorationDirection ::BACKWARD}).second)
744 return Tail;
745 Tail = nullptr;
746 return nullptr;
747}
748
749PreservedAnalyses MustExecutePrinterPass::run(Function &F,
750 FunctionAnalysisManager &AM) {
751 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
752 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
753
754 MustExecuteAnnotatedWriter Writer(F, DT, LI);
755 F.print(OS, AAW: &Writer);
756 return PreservedAnalyses::all();
757}
758
759PreservedAnalyses
760MustBeExecutedContextPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
761 FunctionAnalysisManager &FAM =
762 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
763 GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
764 return &FAM.getResult<LoopAnalysis>(IR&: const_cast<Function &>(F));
765 };
766 GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
767 return &FAM.getResult<DominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
768 };
769 GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
770 return &FAM.getResult<PostDominatorTreeAnalysis>(IR&: const_cast<Function &>(F));
771 };
772
773 MustBeExecutedContextExplorer Explorer(
774 /* ExploreInterBlock */ true,
775 /* ExploreCFGForward */ true,
776 /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
777
778 for (Function &F : M) {
779 for (Instruction &I : instructions(F)) {
780 OS << "-- Explore context of: " << I << "\n";
781 for (const Instruction *CI : Explorer.range(PP: &I))
782 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
783 }
784 }
785 return PreservedAnalyses::all();
786}
787