Line data Source code
1 : //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
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"
23 : using namespace llvm;
24 :
25 : const DenseMap<BasicBlock *, ColorVector> &
26 1082613 : LoopSafetyInfo::getBlockColors() const {
27 1082613 : return BlockColors;
28 : }
29 :
30 4 : void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
31 4 : ColorVector &ColorsForNewBlock = BlockColors[New];
32 : ColorVector &ColorsForOldBlock = BlockColors[Old];
33 4 : ColorsForNewBlock = ColorsForOldBlock;
34 4 : }
35 :
36 4806 : bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
37 : (void)BB;
38 4806 : return anyBlockMayThrow();
39 : }
40 :
41 8267 : bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
42 8267 : return MayThrow;
43 : }
44 :
45 16228 : 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 16228 : HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
50 16228 : 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 25235 : for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
57 : BBE = CurLoop->block_end();
58 41463 : (BB != BBE) && !MayThrow; ++BB)
59 25235 : MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
60 :
61 16228 : computeBlockColors(CurLoop);
62 16228 : }
63 :
64 0 : bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
65 0 : return ICF.hasICF(BB);
66 : }
67 :
68 0 : bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
69 0 : return MayThrow;
70 : }
71 :
72 0 : void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
73 : assert(CurLoop != nullptr && "CurLoop can't be null");
74 0 : ICF.clear();
75 0 : MayThrow = false;
76 : // Figure out the fact that at least one block may throw.
77 0 : for (auto &BB : CurLoop->blocks())
78 0 : if (ICF.hasICF(&*BB)) {
79 0 : MayThrow = true;
80 0 : break;
81 : }
82 0 : computeBlockColors(CurLoop);
83 0 : }
84 :
85 0 : void ICFLoopSafetyInfo::dropCachedInfo(const BasicBlock *BB) {
86 0 : ICF.invalidateBlock(BB);
87 0 : }
88 :
89 32456 : void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
90 : // Compute funclet colors if we might sink/hoist in a function with a funclet
91 : // personality routine.
92 16228 : Function *Fn = CurLoop->getHeader()->getParent();
93 16228 : if (Fn->hasPersonalityFn())
94 6964 : if (Constant *PersonalityFn = Fn->getPersonalityFn())
95 6964 : if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
96 26 : BlockColors = colorEHFunclets(*Fn);
97 16228 : }
98 :
99 : /// Return true if we can prove that the given ExitBlock is not reached on the
100 : /// first iteration of the given loop. That is, the backedge of the loop must
101 : /// be executed before the ExitBlock is executed in any dynamic execution trace.
102 856 : static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
103 : const DominatorTree *DT,
104 : const Loop *CurLoop) {
105 856 : auto *CondExitBlock = ExitBlock->getSinglePredecessor();
106 856 : if (!CondExitBlock)
107 : // expect unique exits
108 : return false;
109 : assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
110 789 : auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
111 789 : if (!BI || !BI->isConditional())
112 : return false;
113 : // If condition is constant and false leads to ExitBlock then we always
114 : // execute the true branch.
115 : if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
116 68 : return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
117 : auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
118 : if (!Cond)
119 : return false;
120 : // todo: this would be a lot more powerful if we used scev, but all the
121 : // plumbing is currently missing to pass a pointer in from the pass
122 : // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
123 : auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
124 : auto *RHS = Cond->getOperand(1);
125 755 : if (!LHS || LHS->getParent() != CurLoop->getHeader())
126 : return false;
127 26 : auto DL = ExitBlock->getModule()->getDataLayout();
128 13 : auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
129 13 : auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
130 : IVStart, RHS,
131 : {DL, /*TLI*/ nullptr,
132 : DT, /*AC*/ nullptr, BI});
133 : auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
134 : if (!SimpleCst)
135 : return false;
136 2 : if (ExitBlock == BI->getSuccessor(0))
137 0 : return SimpleCst->isZeroValue();
138 : assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
139 2 : return SimpleCst->isAllOnesValue();
140 : }
141 :
142 2394 : void LoopSafetyInfo::collectTransitivePredecessors(
143 : const Loop *CurLoop, const BasicBlock *BB,
144 : SmallPtrSetImpl<const BasicBlock *> &Predecessors) const {
145 : assert(Predecessors.empty() && "Garbage in predecessors set?");
146 : assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
147 2394 : if (BB == CurLoop->getHeader())
148 0 : return;
149 : SmallVector<const BasicBlock *, 4> WorkList;
150 5197 : for (auto *Pred : predecessors(BB)) {
151 2803 : Predecessors.insert(Pred);
152 2803 : WorkList.push_back(Pred);
153 : }
154 21569 : while (!WorkList.empty()) {
155 : auto *Pred = WorkList.pop_back_val();
156 : assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
157 : // We are not interested in backedges and we don't want to leave loop.
158 19175 : if (Pred == CurLoop->getHeader())
159 : continue;
160 : // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
161 : // blocks of this inner loop, even those that are always executed AFTER the
162 : // BB. It may make our analysis more conservative than it could be, see test
163 : // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
164 : // We can ignore backedge of all loops containing BB to get a sligtly more
165 : // optimistic result.
166 38477 : for (auto *PredPred : predecessors(Pred))
167 21696 : if (Predecessors.insert(PredPred).second)
168 16372 : WorkList.push_back(PredPred);
169 : }
170 : }
171 :
172 2394 : bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
173 : const BasicBlock *BB,
174 : const DominatorTree *DT) const {
175 : assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
176 :
177 : // Fast path: header is always reached once the loop is entered.
178 2394 : if (BB == CurLoop->getHeader())
179 : return true;
180 :
181 : // Collect all transitive predecessors of BB in the same loop. This set will
182 : // be a subset of the blocks within the loop.
183 : SmallPtrSet<const BasicBlock *, 4> Predecessors;
184 2394 : collectTransitivePredecessors(CurLoop, BB, Predecessors);
185 :
186 : // Make sure that all successors of all predecessors of BB are either:
187 : // 1) BB,
188 : // 2) Also predecessors of BB,
189 : // 3) Exit blocks which are not taken on 1st iteration.
190 : // Memoize blocks we've already checked.
191 : SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
192 4906 : for (auto *Pred : Predecessors) {
193 : // Predecessor block may throw, so it has a side exit.
194 4806 : if (blockMayThrow(Pred))
195 2294 : return false;
196 13522 : for (auto *Succ : successors(Pred))
197 17996 : if (CheckedSuccessors.insert(Succ).second &&
198 11533 : Succ != BB && !Predecessors.count(Succ))
199 : // By discharging conditions that are not executed on the 1st iteration,
200 : // we guarantee that *at least* on the first iteration all paths from
201 : // header that *may* execute will lead us to the block of interest. So
202 : // that if we had virtually peeled one iteration away, in this peeled
203 : // iteration the set of predecessors would contain only paths from
204 : // header to BB without any exiting edges that may execute.
205 : //
206 : // TODO: We only do it for exiting edges currently. We could use the
207 : // same function to skip some of the edges within the loop if we know
208 : // that they will not be taken on the 1st iteration.
209 : //
210 : // TODO: If we somehow know the number of iterations in loop, the same
211 : // check may be done for any arbitrary N-th iteration as long as N is
212 : // not greater than minimum number of iterations in this loop.
213 2920 : if (CurLoop->contains(Succ) ||
214 856 : !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
215 : return false;
216 : }
217 :
218 : // All predecessors can only lead us to BB.
219 100 : return true;
220 : }
221 :
222 : /// Returns true if the instruction in a loop is guaranteed to execute at least
223 : /// once.
224 3073 : bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
225 : const DominatorTree *DT,
226 : const Loop *CurLoop) const {
227 : // If the instruction is in the header block for the loop (which is very
228 : // common), it is always guaranteed to dominate the exit blocks. Since this
229 : // is a common case, and can save some work, check it now.
230 6146 : if (Inst.getParent() == CurLoop->getHeader())
231 : // If there's a throw in the header block, we can't guarantee we'll reach
232 : // Inst unless we can prove that Inst comes before the potential implicit
233 : // exit. At the moment, we use a (cheap) hack for the common case where
234 : // the instruction of interest is the first one in the block.
235 737 : return !HeaderMayThrow ||
236 58 : Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
237 :
238 : // If there is a path from header to exit or latch that doesn't lead to our
239 : // instruction's block, return false.
240 2394 : return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
241 : }
242 :
243 0 : bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
244 : const DominatorTree *DT,
245 : const Loop *CurLoop) const {
246 0 : return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
247 0 : allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
248 : }
249 :
250 : namespace {
251 : struct MustExecutePrinter : public FunctionPass {
252 :
253 : static char ID; // Pass identification, replacement for typeid
254 3 : MustExecutePrinter() : FunctionPass(ID) {
255 3 : initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
256 : }
257 3 : void getAnalysisUsage(AnalysisUsage &AU) const override {
258 : AU.setPreservesAll();
259 : AU.addRequired<DominatorTreeWrapperPass>();
260 : AU.addRequired<LoopInfoWrapperPass>();
261 3 : }
262 : bool runOnFunction(Function &F) override;
263 : };
264 : }
265 :
266 : char MustExecutePrinter::ID = 0;
267 10756 : INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
268 : "Instructions which execute on loop entry", false, true)
269 10756 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
270 10756 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
271 21515 : INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
272 : "Instructions which execute on loop entry", false, true)
273 :
274 0 : FunctionPass *llvm::createMustExecutePrinter() {
275 0 : return new MustExecutePrinter();
276 : }
277 :
278 67 : static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
279 : // TODO: merge these two routines. For the moment, we display the best
280 : // result obtained by *either* implementation. This is a bit unfair since no
281 : // caller actually gets the full power at the moment.
282 : SimpleLoopSafetyInfo LSI;
283 67 : LSI.computeLoopSafetyInfo(L);
284 93 : return LSI.isGuaranteedToExecute(I, DT, L) ||
285 26 : isGuaranteedToExecuteForEveryIteration(&I, L);
286 : }
287 :
288 : namespace {
289 : /// An assembly annotator class to print must execute information in
290 : /// comments.
291 : class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
292 : DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
293 :
294 : public:
295 9 : MustExecuteAnnotatedWriter(const Function &F,
296 9 : DominatorTree &DT, LoopInfo &LI) {
297 80 : for (auto &I: instructions(F)) {
298 160 : Loop *L = LI.getLoopFor(I.getParent());
299 147 : while (L) {
300 67 : if (isMustExecuteIn(I, L, &DT)) {
301 43 : MustExec[&I].push_back(L);
302 : }
303 67 : L = L->getParentLoop();
304 : };
305 : }
306 9 : }
307 : MustExecuteAnnotatedWriter(const Module &M,
308 : DominatorTree &DT, LoopInfo &LI) {
309 : for (auto &F : M)
310 : for (auto &I: instructions(F)) {
311 : Loop *L = LI.getLoopFor(I.getParent());
312 : while (L) {
313 : if (isMustExecuteIn(I, L, &DT)) {
314 : MustExec[&I].push_back(L);
315 : }
316 : L = L->getParentLoop();
317 : };
318 : }
319 : }
320 :
321 :
322 80 : void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
323 80 : if (!MustExec.count(&V))
324 37 : return;
325 :
326 43 : const auto &Loops = MustExec.lookup(&V);
327 43 : const auto NumLoops = Loops.size();
328 43 : if (NumLoops > 1)
329 0 : OS << " ; (mustexec in " << NumLoops << " loops: ";
330 : else
331 43 : OS << " ; (mustexec in: ";
332 :
333 : bool first = true;
334 86 : for (const Loop *L : Loops) {
335 43 : if (!first)
336 0 : OS << ", ";
337 : first = false;
338 86 : OS << L->getHeader()->getName();
339 : }
340 43 : OS << ")";
341 : }
342 : };
343 : } // namespace
344 :
345 9 : bool MustExecutePrinter::runOnFunction(Function &F) {
346 9 : auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
347 9 : auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
348 :
349 18 : MustExecuteAnnotatedWriter Writer(F, DT, LI);
350 9 : F.print(dbgs(), &Writer);
351 :
352 9 : return false;
353 : }
|
