blob: e22831cd6a9271eee52a43278e1f24a242b593c9 [file] [log] [blame]
Philip Reames89f22412018-03-20 17:09:21 +00001//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Philip Reames89f22412018-03-20 17:09:21 +00006//
7//===----------------------------------------------------------------------===//
8
Philip Reamese4b728e2018-03-29 19:22:12 +00009#include "llvm/Analysis/MustExecute.h"
Philip Reames23aed5e2018-03-20 22:45:23 +000010#include "llvm/Analysis/InstructionSimplify.h"
Philip Reames89f22412018-03-20 17:09:21 +000011#include "llvm/Analysis/LoopInfo.h"
12#include "llvm/Analysis/Passes.h"
13#include "llvm/Analysis/ValueTracking.h"
Philip Reamesce998ad2018-03-20 18:43:44 +000014#include "llvm/IR/AssemblyAnnotationWriter.h"
Philip Reames89f22412018-03-20 17:09:21 +000015#include "llvm/IR/DataLayout.h"
16#include "llvm/IR/InstIterator.h"
17#include "llvm/IR/LLVMContext.h"
18#include "llvm/IR/Module.h"
19#include "llvm/Support/ErrorHandling.h"
Philip Reamesce998ad2018-03-20 18:43:44 +000020#include "llvm/Support/FormattedStream.h"
Philip Reames89f22412018-03-20 17:09:21 +000021#include "llvm/Support/raw_ostream.h"
Philip Reames89f22412018-03-20 17:09:21 +000022using namespace llvm;
23
Max Kazantsev8d56be72018-10-16 08:07:14 +000024const DenseMap<BasicBlock *, ColorVector> &
25LoopSafetyInfo::getBlockColors() const {
26 return BlockColors;
27}
28
29void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
30 ColorVector &ColorsForNewBlock = BlockColors[New];
31 ColorVector &ColorsForOldBlock = BlockColors[Old];
32 ColorsForNewBlock = ColorsForOldBlock;
33}
34
Max Kazantsev9c90ec22018-10-16 08:31:05 +000035bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
Max Kazantsev6a4f5e22018-10-16 07:50:14 +000036 (void)BB;
37 return anyBlockMayThrow();
38}
39
Max Kazantsev9c90ec22018-10-16 08:31:05 +000040bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
Max Kazantsev530b8d12018-08-15 05:55:43 +000041 return MayThrow;
42}
43
Max Kazantsev9c90ec22018-10-16 08:31:05 +000044void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
Shoaib Meenaia57d7132018-07-19 19:11:29 +000045 assert(CurLoop != nullptr && "CurLoop can't be null");
Philip Reames23aed5e2018-03-20 22:45:23 +000046 BasicBlock *Header = CurLoop->getHeader();
Philip Reames23aed5e2018-03-20 22:45:23 +000047 // Iterate over header and compute safety info.
Max Kazantsev530b8d12018-08-15 05:55:43 +000048 HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
49 MayThrow = HeaderMayThrow;
Philip Reames23aed5e2018-03-20 22:45:23 +000050 // Iterate over loop instructions and compute safety info.
51 // Skip header as it has been computed and stored in HeaderMayThrow.
52 // The first block in loopinfo.Blocks is guaranteed to be the header.
53 assert(Header == *CurLoop->getBlocks().begin() &&
54 "First block must be header");
55 for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
56 BBE = CurLoop->block_end();
Max Kazantsev530b8d12018-08-15 05:55:43 +000057 (BB != BBE) && !MayThrow; ++BB)
58 MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
Philip Reames23aed5e2018-03-20 22:45:23 +000059
Max Kazantsev8d56be72018-10-16 08:07:14 +000060 computeBlockColors(CurLoop);
61}
62
Max Kazantsev5f9acd22018-10-16 09:58:09 +000063bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
64 return ICF.hasICF(BB);
65}
66
67bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
68 return MayThrow;
69}
70
71void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
72 assert(CurLoop != nullptr && "CurLoop can't be null");
73 ICF.clear();
Max Kazantsev7d49a3a2018-11-12 09:29:58 +000074 MW.clear();
Max Kazantsev5f9acd22018-10-16 09:58:09 +000075 MayThrow = false;
76 // Figure out the fact that at least one block may throw.
77 for (auto &BB : CurLoop->blocks())
78 if (ICF.hasICF(&*BB)) {
79 MayThrow = true;
80 break;
81 }
82 computeBlockColors(CurLoop);
83}
84
Max Kazantsev4615a502019-01-09 07:28:13 +000085void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
86 const BasicBlock *BB) {
87 ICF.insertInstructionTo(Inst, BB);
88 MW.insertInstructionTo(Inst, BB);
Max Kazantsev5f9acd22018-10-16 09:58:09 +000089}
90
Max Kazantsevbb844072018-11-01 10:16:06 +000091void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
Max Kazantsev4615a502019-01-09 07:28:13 +000092 ICF.removeInstruction(Inst);
93 MW.removeInstruction(Inst);
Max Kazantsevbb844072018-11-01 10:16:06 +000094}
95
Max Kazantsev8d56be72018-10-16 08:07:14 +000096void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
Philip Reames23aed5e2018-03-20 22:45:23 +000097 // Compute funclet colors if we might sink/hoist in a function with a funclet
98 // personality routine.
99 Function *Fn = CurLoop->getHeader()->getParent();
100 if (Fn->hasPersonalityFn())
101 if (Constant *PersonalityFn = Fn->getPersonalityFn())
Heejin Ahnb4be38f2018-05-17 20:52:03 +0000102 if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
Max Kazantsev530b8d12018-08-15 05:55:43 +0000103 BlockColors = colorEHFunclets(*Fn);
Philip Reames23aed5e2018-03-20 22:45:23 +0000104}
105
106/// Return true if we can prove that the given ExitBlock is not reached on the
107/// first iteration of the given loop. That is, the backedge of the loop must
108/// be executed before the ExitBlock is executed in any dynamic execution trace.
Max Kazantseva7415872018-08-16 06:28:04 +0000109static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
Philip Reames23aed5e2018-03-20 22:45:23 +0000110 const DominatorTree *DT,
111 const Loop *CurLoop) {
112 auto *CondExitBlock = ExitBlock->getSinglePredecessor();
113 if (!CondExitBlock)
114 // expect unique exits
115 return false;
116 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
117 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
118 if (!BI || !BI->isConditional())
119 return false;
Serguei Katkov50958832018-05-18 04:56:28 +0000120 // If condition is constant and false leads to ExitBlock then we always
121 // execute the true branch.
122 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
123 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
Philip Reames23aed5e2018-03-20 22:45:23 +0000124 auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
125 if (!Cond)
126 return false;
127 // todo: this would be a lot more powerful if we used scev, but all the
128 // plumbing is currently missing to pass a pointer in from the pass
129 // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
130 auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
131 auto *RHS = Cond->getOperand(1);
132 if (!LHS || LHS->getParent() != CurLoop->getHeader())
133 return false;
134 auto DL = ExitBlock->getModule()->getDataLayout();
135 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
136 auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
137 IVStart, RHS,
138 {DL, /*TLI*/ nullptr,
139 DT, /*AC*/ nullptr, BI});
140 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
141 if (!SimpleCst)
142 return false;
143 if (ExitBlock == BI->getSuccessor(0))
144 return SimpleCst->isZeroValue();
145 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
146 return SimpleCst->isAllOnesValue();
147}
148
Max Kazantsev4855b742018-11-06 09:07:03 +0000149/// Collect all blocks from \p CurLoop which lie on all possible paths from
150/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
151/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
152static void collectTransitivePredecessors(
Max Kazantsevbfbd4d12018-08-21 07:15:06 +0000153 const Loop *CurLoop, const BasicBlock *BB,
Max Kazantsev4855b742018-11-06 09:07:03 +0000154 SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
Max Kazantsevbfbd4d12018-08-21 07:15:06 +0000155 assert(Predecessors.empty() && "Garbage in predecessors set?");
Max Kazantsev7b78d392018-08-17 06:19:17 +0000156 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
Max Kazantsev7b78d392018-08-17 06:19:17 +0000157 if (BB == CurLoop->getHeader())
Max Kazantsevbfbd4d12018-08-21 07:15:06 +0000158 return;
Max Kazantsev7b78d392018-08-17 06:19:17 +0000159 SmallVector<const BasicBlock *, 4> WorkList;
160 for (auto *Pred : predecessors(BB)) {
161 Predecessors.insert(Pred);
162 WorkList.push_back(Pred);
163 }
164 while (!WorkList.empty()) {
165 auto *Pred = WorkList.pop_back_val();
166 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
167 // We are not interested in backedges and we don't want to leave loop.
168 if (Pred == CurLoop->getHeader())
169 continue;
170 // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
171 // blocks of this inner loop, even those that are always executed AFTER the
172 // BB. It may make our analysis more conservative than it could be, see test
173 // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
174 // We can ignore backedge of all loops containing BB to get a sligtly more
175 // optimistic result.
176 for (auto *PredPred : predecessors(Pred))
177 if (Predecessors.insert(PredPred).second)
178 WorkList.push_back(PredPred);
179 }
Max Kazantsevbfbd4d12018-08-21 07:15:06 +0000180}
181
182bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
183 const BasicBlock *BB,
184 const DominatorTree *DT) const {
185 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
186
187 // Fast path: header is always reached once the loop is entered.
188 if (BB == CurLoop->getHeader())
189 return true;
190
191 // Collect all transitive predecessors of BB in the same loop. This set will
192 // be a subset of the blocks within the loop.
193 SmallPtrSet<const BasicBlock *, 4> Predecessors;
194 collectTransitivePredecessors(CurLoop, BB, Predecessors);
Max Kazantsev7b78d392018-08-17 06:19:17 +0000195
196 // Make sure that all successors of all predecessors of BB are either:
197 // 1) BB,
198 // 2) Also predecessors of BB,
199 // 3) Exit blocks which are not taken on 1st iteration.
200 // Memoize blocks we've already checked.
201 SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
Max Kazantsev6a4f5e22018-10-16 07:50:14 +0000202 for (auto *Pred : Predecessors) {
203 // Predecessor block may throw, so it has a side exit.
204 if (blockMayThrow(Pred))
205 return false;
Max Kazantsev7b78d392018-08-17 06:19:17 +0000206 for (auto *Succ : successors(Pred))
207 if (CheckedSuccessors.insert(Succ).second &&
208 Succ != BB && !Predecessors.count(Succ))
209 // By discharging conditions that are not executed on the 1st iteration,
210 // we guarantee that *at least* on the first iteration all paths from
211 // header that *may* execute will lead us to the block of interest. So
212 // that if we had virtually peeled one iteration away, in this peeled
213 // iteration the set of predecessors would contain only paths from
214 // header to BB without any exiting edges that may execute.
215 //
216 // TODO: We only do it for exiting edges currently. We could use the
217 // same function to skip some of the edges within the loop if we know
218 // that they will not be taken on the 1st iteration.
219 //
220 // TODO: If we somehow know the number of iterations in loop, the same
221 // check may be done for any arbitrary N-th iteration as long as N is
222 // not greater than minimum number of iterations in this loop.
223 if (CurLoop->contains(Succ) ||
224 !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
225 return false;
Max Kazantsev6a4f5e22018-10-16 07:50:14 +0000226 }
Max Kazantsev7b78d392018-08-17 06:19:17 +0000227
228 // All predecessors can only lead us to BB.
229 return true;
230}
231
Philip Reames23aed5e2018-03-20 22:45:23 +0000232/// Returns true if the instruction in a loop is guaranteed to execute at least
233/// once.
Max Kazantsev9c90ec22018-10-16 08:31:05 +0000234bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
235 const DominatorTree *DT,
236 const Loop *CurLoop) const {
Philip Reames23aed5e2018-03-20 22:45:23 +0000237 // If the instruction is in the header block for the loop (which is very
238 // common), it is always guaranteed to dominate the exit blocks. Since this
239 // is a common case, and can save some work, check it now.
240 if (Inst.getParent() == CurLoop->getHeader())
241 // If there's a throw in the header block, we can't guarantee we'll reach
Philip Reamese4ec4732018-04-27 20:44:01 +0000242 // Inst unless we can prove that Inst comes before the potential implicit
243 // exit. At the moment, we use a (cheap) hack for the common case where
244 // the instruction of interest is the first one in the block.
Max Kazantsev87de55a2018-10-16 09:11:25 +0000245 return !HeaderMayThrow ||
Max Kazantsevc8466f92018-10-16 06:34:53 +0000246 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
Philip Reames23aed5e2018-03-20 22:45:23 +0000247
Max Kazantsev7b78d392018-08-17 06:19:17 +0000248 // If there is a path from header to exit or latch that doesn't lead to our
249 // instruction's block, return false.
Max Kazantsev87de55a2018-10-16 09:11:25 +0000250 return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
Philip Reames23aed5e2018-03-20 22:45:23 +0000251}
252
Max Kazantsev5f9acd22018-10-16 09:58:09 +0000253bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
254 const DominatorTree *DT,
255 const Loop *CurLoop) const {
256 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
257 allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
258}
Philip Reames23aed5e2018-03-20 22:45:23 +0000259
Max Kazantsev7d49a3a2018-11-12 09:29:58 +0000260bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
261 const Loop *CurLoop) const {
262 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
263
264 // Fast path: there are no instructions before header.
265 if (BB == CurLoop->getHeader())
266 return true;
267
268 // Collect all transitive predecessors of BB in the same loop. This set will
269 // be a subset of the blocks within the loop.
270 SmallPtrSet<const BasicBlock *, 4> Predecessors;
271 collectTransitivePredecessors(CurLoop, BB, Predecessors);
272 // Find if there any instruction in either predecessor that could write
273 // to memory.
274 for (auto *Pred : Predecessors)
275 if (MW.mayWriteToMemory(Pred))
276 return false;
277 return true;
278}
279
280bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
281 const Loop *CurLoop) const {
282 auto *BB = I.getParent();
283 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
284 return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
285 doesNotWriteMemoryBefore(BB, CurLoop);
286}
287
Philip Reames89f22412018-03-20 17:09:21 +0000288namespace {
289 struct MustExecutePrinter : public FunctionPass {
Philip Reames89f22412018-03-20 17:09:21 +0000290
291 static char ID; // Pass identification, replacement for typeid
292 MustExecutePrinter() : FunctionPass(ID) {
293 initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
294 }
295 void getAnalysisUsage(AnalysisUsage &AU) const override {
296 AU.setPreservesAll();
297 AU.addRequired<DominatorTreeWrapperPass>();
298 AU.addRequired<LoopInfoWrapperPass>();
299 }
300 bool runOnFunction(Function &F) override;
Philip Reames89f22412018-03-20 17:09:21 +0000301 };
302}
303
304char MustExecutePrinter::ID = 0;
305INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
306 "Instructions which execute on loop entry", false, true)
307INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
308INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
309INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
310 "Instructions which execute on loop entry", false, true)
311
312FunctionPass *llvm::createMustExecutePrinter() {
313 return new MustExecutePrinter();
314}
315
Benjamin Kramer1fc0da42018-04-04 11:45:11 +0000316static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
Philip Reames37a1a292018-03-20 23:00:54 +0000317 // TODO: merge these two routines. For the moment, we display the best
318 // result obtained by *either* implementation. This is a bit unfair since no
319 // caller actually gets the full power at the moment.
Max Kazantsev9c90ec22018-10-16 08:31:05 +0000320 SimpleLoopSafetyInfo LSI;
Max Kazantsev530b8d12018-08-15 05:55:43 +0000321 LSI.computeLoopSafetyInfo(L);
Max Kazantsevc8466f92018-10-16 06:34:53 +0000322 return LSI.isGuaranteedToExecute(I, DT, L) ||
Philip Reames37a1a292018-03-20 23:00:54 +0000323 isGuaranteedToExecuteForEveryIteration(&I, L);
Philip Reames89f22412018-03-20 17:09:21 +0000324}
325
Benjamin Kramer1fc0da42018-04-04 11:45:11 +0000326namespace {
Adrian Prantl5f8f34e42018-05-01 15:54:18 +0000327/// An assembly annotator class to print must execute information in
Philip Reamesce998ad2018-03-20 18:43:44 +0000328/// comments.
329class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
330 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
Philip Reames89f22412018-03-20 17:09:21 +0000331
Philip Reamesce998ad2018-03-20 18:43:44 +0000332public:
333 MustExecuteAnnotatedWriter(const Function &F,
334 DominatorTree &DT, LoopInfo &LI) {
335 for (auto &I: instructions(F)) {
336 Loop *L = LI.getLoopFor(I.getParent());
337 while (L) {
338 if (isMustExecuteIn(I, L, &DT)) {
339 MustExec[&I].push_back(L);
340 }
341 L = L->getParentLoop();
342 };
343 }
344 }
345 MustExecuteAnnotatedWriter(const Module &M,
346 DominatorTree &DT, LoopInfo &LI) {
347 for (auto &F : M)
348 for (auto &I: instructions(F)) {
349 Loop *L = LI.getLoopFor(I.getParent());
350 while (L) {
351 if (isMustExecuteIn(I, L, &DT)) {
352 MustExec[&I].push_back(L);
353 }
354 L = L->getParentLoop();
355 };
356 }
357 }
358
359
Fangrui Songf78650a2018-07-30 19:41:25 +0000360 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
Philip Reamesce998ad2018-03-20 18:43:44 +0000361 if (!MustExec.count(&V))
362 return;
363
364 const auto &Loops = MustExec.lookup(&V);
365 const auto NumLoops = Loops.size();
Philip Reames89f22412018-03-20 17:09:21 +0000366 if (NumLoops > 1)
Philip Reamesce998ad2018-03-20 18:43:44 +0000367 OS << " ; (mustexec in " << NumLoops << " loops: ";
Philip Reames89f22412018-03-20 17:09:21 +0000368 else
Philip Reamesce998ad2018-03-20 18:43:44 +0000369 OS << " ; (mustexec in: ";
Fangrui Songf78650a2018-07-30 19:41:25 +0000370
Philip Reames89f22412018-03-20 17:09:21 +0000371 bool first = true;
Philip Reamesce998ad2018-03-20 18:43:44 +0000372 for (const Loop *L : Loops) {
Philip Reames89f22412018-03-20 17:09:21 +0000373 if (!first)
374 OS << ", ";
375 first = false;
376 OS << L->getHeader()->getName();
377 }
Philip Reamesce998ad2018-03-20 18:43:44 +0000378 OS << ")";
Philip Reames89f22412018-03-20 17:09:21 +0000379 }
Philip Reamesce998ad2018-03-20 18:43:44 +0000380};
Benjamin Kramer1fc0da42018-04-04 11:45:11 +0000381} // namespace
Philip Reamesce998ad2018-03-20 18:43:44 +0000382
383bool MustExecutePrinter::runOnFunction(Function &F) {
384 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
385 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
386
387 MustExecuteAnnotatedWriter Writer(F, DT, LI);
388 F.print(dbgs(), &Writer);
Fangrui Songf78650a2018-07-30 19:41:25 +0000389
Philip Reamesce998ad2018-03-20 18:43:44 +0000390 return false;
Philip Reames89f22412018-03-20 17:09:21 +0000391}