1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/MustExecute.h"
11 #include "llvm/Analysis/InstructionSimplify.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/Passes.h"
14 #include "llvm/Analysis/ValueTracking.h"
15 #include "llvm/IR/AssemblyAnnotationWriter.h"
16 #include "llvm/IR/DataLayout.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/FormattedStream.h"
22 #include "llvm/Support/raw_ostream.h"
25 const DenseMap<BasicBlock *, ColorVector> &
26 LoopSafetyInfo::getBlockColors() const {
30 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
31 ColorVector &ColorsForNewBlock = BlockColors[New];
32 ColorVector &ColorsForOldBlock = BlockColors[Old];
33 ColorsForNewBlock = ColorsForOldBlock;
36 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
38 return anyBlockMayThrow();
41 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
45 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
46 assert(CurLoop != nullptr && "CurLoop can't be null");
47 BasicBlock *Header = CurLoop->getHeader();
48 // Iterate over header and compute safety info.
49 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
50 MayThrow = HeaderMayThrow;
51 // Iterate over loop instructions and compute safety info.
52 // Skip header as it has been computed and stored in HeaderMayThrow.
53 // The first block in loopinfo.Blocks is guaranteed to be the header.
54 assert(Header == *CurLoop->getBlocks().begin() &&
55 "First block must be header");
56 for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
57 BBE = CurLoop->block_end();
58 (BB != BBE) && !MayThrow; ++BB)
59 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
61 computeBlockColors(CurLoop);
64 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
65 return ICF.hasICF(BB);
68 bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
72 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
73 assert(CurLoop != nullptr && "CurLoop can't be null");
77 // Figure out the fact that at least one block may throw.
78 for (auto &BB : CurLoop->blocks())
79 if (ICF.hasICF(&*BB)) {
83 computeBlockColors(CurLoop);
86 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
87 const BasicBlock *BB) {
88 ICF.insertInstructionTo(Inst, BB);
89 MW.insertInstructionTo(Inst, BB);
92 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
93 ICF.removeInstruction(Inst);
94 MW.removeInstruction(Inst);
97 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
98 // Compute funclet colors if we might sink/hoist in a function with a funclet
99 // personality routine.
100 Function *Fn = CurLoop->getHeader()->getParent();
101 if (Fn->hasPersonalityFn())
102 if (Constant *PersonalityFn = Fn->getPersonalityFn())
103 if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
104 BlockColors = colorEHFunclets(*Fn);
107 /// Return true if we can prove that the given ExitBlock is not reached on the
108 /// first iteration of the given loop. That is, the backedge of the loop must
109 /// be executed before the ExitBlock is executed in any dynamic execution trace.
110 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
111 const DominatorTree *DT,
112 const Loop *CurLoop) {
113 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
115 // expect unique exits
117 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
118 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
119 if (!BI || !BI->isConditional())
121 // If condition is constant and false leads to ExitBlock then we always
122 // execute the true branch.
123 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
124 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
125 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
128 // todo: this would be a lot more powerful if we used scev, but all the
129 // plumbing is currently missing to pass a pointer in from the pass
130 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
131 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
132 auto *RHS = Cond->getOperand(1);
133 if (!LHS || LHS->getParent() != CurLoop->getHeader())
135 auto DL = ExitBlock->getModule()->getDataLayout();
136 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
137 auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
139 {DL, /*TLI*/ nullptr,
140 DT, /*AC*/ nullptr, BI});
141 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
144 if (ExitBlock == BI->getSuccessor(0))
145 return SimpleCst->isZeroValue();
146 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
147 return SimpleCst->isAllOnesValue();
150 /// Collect all blocks from \p CurLoop which lie on all possible paths from
151 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
152 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
153 static void collectTransitivePredecessors(
154 const Loop *CurLoop, const BasicBlock *BB,
155 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
156 assert(Predecessors.empty() && "Garbage in predecessors set?");
157 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
158 if (BB == CurLoop->getHeader())
160 SmallVector<const BasicBlock *, 4> WorkList;
161 for (auto *Pred : predecessors(BB)) {
162 Predecessors.insert(Pred);
163 WorkList.push_back(Pred);
165 while (!WorkList.empty()) {
166 auto *Pred = WorkList.pop_back_val();
167 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
168 // We are not interested in backedges and we don't want to leave loop.
169 if (Pred == CurLoop->getHeader())
171 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
172 // blocks of this inner loop, even those that are always executed AFTER the
173 // BB. It may make our analysis more conservative than it could be, see test
174 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
175 // We can ignore backedge of all loops containing BB to get a sligtly more
176 // optimistic result.
177 for (auto *PredPred : predecessors(Pred))
178 if (Predecessors.insert(PredPred).second)
179 WorkList.push_back(PredPred);
183 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
184 const BasicBlock *BB,
185 const DominatorTree *DT) const {
186 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
188 // Fast path: header is always reached once the loop is entered.
189 if (BB == CurLoop->getHeader())
192 // Collect all transitive predecessors of BB in the same loop. This set will
193 // be a subset of the blocks within the loop.
194 SmallPtrSet<const BasicBlock *, 4> Predecessors;
195 collectTransitivePredecessors(CurLoop, BB, Predecessors);
197 // Make sure that all successors of all predecessors of BB are either:
199 // 2) Also predecessors of BB,
200 // 3) Exit blocks which are not taken on 1st iteration.
201 // Memoize blocks we've already checked.
202 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
203 for (auto *Pred : Predecessors) {
204 // Predecessor block may throw, so it has a side exit.
205 if (blockMayThrow(Pred))
207 for (auto *Succ : successors(Pred))
208 if (CheckedSuccessors.insert(Succ).second &&
209 Succ != BB && !Predecessors.count(Succ))
210 // By discharging conditions that are not executed on the 1st iteration,
211 // we guarantee that *at least* on the first iteration all paths from
212 // header that *may* execute will lead us to the block of interest. So
213 // that if we had virtually peeled one iteration away, in this peeled
214 // iteration the set of predecessors would contain only paths from
215 // header to BB without any exiting edges that may execute.
217 // TODO: We only do it for exiting edges currently. We could use the
218 // same function to skip some of the edges within the loop if we know
219 // that they will not be taken on the 1st iteration.
221 // TODO: If we somehow know the number of iterations in loop, the same
222 // check may be done for any arbitrary N-th iteration as long as N is
223 // not greater than minimum number of iterations in this loop.
224 if (CurLoop->contains(Succ) ||
225 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
229 // All predecessors can only lead us to BB.
233 /// Returns true if the instruction in a loop is guaranteed to execute at least
235 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
236 const DominatorTree *DT,
237 const Loop *CurLoop) const {
238 // If the instruction is in the header block for the loop (which is very
239 // common), it is always guaranteed to dominate the exit blocks. Since this
240 // is a common case, and can save some work, check it now.
241 if (Inst.getParent() == CurLoop->getHeader())
242 // If there's a throw in the header block, we can't guarantee we'll reach
243 // Inst unless we can prove that Inst comes before the potential implicit
244 // exit. At the moment, we use a (cheap) hack for the common case where
245 // the instruction of interest is the first one in the block.
246 return !HeaderMayThrow ||
247 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
249 // If there is a path from header to exit or latch that doesn't lead to our
250 // instruction's block, return false.
251 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
254 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
255 const DominatorTree *DT,
256 const Loop *CurLoop) const {
257 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
258 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
261 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
262 const Loop *CurLoop) const {
263 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
265 // Fast path: there are no instructions before header.
266 if (BB == CurLoop->getHeader())
269 // Collect all transitive predecessors of BB in the same loop. This set will
270 // be a subset of the blocks within the loop.
271 SmallPtrSet<const BasicBlock *, 4> Predecessors;
272 collectTransitivePredecessors(CurLoop, BB, Predecessors);
273 // Find if there any instruction in either predecessor that could write
275 for (auto *Pred : Predecessors)
276 if (MW.mayWriteToMemory(Pred))
281 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
282 const Loop *CurLoop) const {
283 auto *BB = I.getParent();
284 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
285 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
286 doesNotWriteMemoryBefore(BB, CurLoop);
290 struct MustExecutePrinter : public FunctionPass {
292 static char ID; // Pass identification, replacement for typeid
293 MustExecutePrinter() : FunctionPass(ID) {
294 initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
296 void getAnalysisUsage(AnalysisUsage &AU) const override {
297 AU.setPreservesAll();
298 AU.addRequired<DominatorTreeWrapperPass>();
299 AU.addRequired<LoopInfoWrapperPass>();
301 bool runOnFunction(Function &F) override;
305 char MustExecutePrinter::ID = 0;
306 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
307 "Instructions which execute on loop entry", false, true)
308 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
309 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
310 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
311 "Instructions which execute on loop entry", false, true)
313 FunctionPass *llvm::createMustExecutePrinter() {
314 return new MustExecutePrinter();
317 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
318 // TODO: merge these two routines. For the moment, we display the best
319 // result obtained by *either* implementation. This is a bit unfair since no
320 // caller actually gets the full power at the moment.
321 SimpleLoopSafetyInfo LSI;
322 LSI.computeLoopSafetyInfo(L);
323 return LSI.isGuaranteedToExecute(I, DT, L) ||
324 isGuaranteedToExecuteForEveryIteration(&I, L);
328 /// An assembly annotator class to print must execute information in
330 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
331 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
334 MustExecuteAnnotatedWriter(const Function &F,
335 DominatorTree &DT, LoopInfo &LI) {
336 for (auto &I: instructions(F)) {
337 Loop *L = LI.getLoopFor(I.getParent());
339 if (isMustExecuteIn(I, L, &DT)) {
340 MustExec[&I].push_back(L);
342 L = L->getParentLoop();
346 MustExecuteAnnotatedWriter(const Module &M,
347 DominatorTree &DT, LoopInfo &LI) {
349 for (auto &I: instructions(F)) {
350 Loop *L = LI.getLoopFor(I.getParent());
352 if (isMustExecuteIn(I, L, &DT)) {
353 MustExec[&I].push_back(L);
355 L = L->getParentLoop();
361 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
362 if (!MustExec.count(&V))
365 const auto &Loops = MustExec.lookup(&V);
366 const auto NumLoops = Loops.size();
368 OS << " ; (mustexec in " << NumLoops << " loops: ";
370 OS << " ; (mustexec in: ";
373 for (const Loop *L : Loops) {
377 OS << L->getHeader()->getName();
384 bool MustExecutePrinter::runOnFunction(Function &F) {
385 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
386 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
388 MustExecuteAnnotatedWriter Writer(F, DT, LI);
389 F.print(dbgs(), &Writer);