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