LLVM  8.0.0svn
MustExecute.cpp
Go to the documentation of this file.
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 
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/Passes.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"
23 using namespace llvm;
24 
26  return HeaderMayThrow;
27 }
28 
30  return MayThrow;
31 }
32 
34  assert(CurLoop != nullptr && "CurLoop can't be null");
35  BasicBlock *Header = CurLoop->getHeader();
36  // Iterate over header and compute safety info.
37  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
38  MayThrow = HeaderMayThrow;
39  // Iterate over loop instructions and compute safety info.
40  // Skip header as it has been computed and stored in HeaderMayThrow.
41  // The first block in loopinfo.Blocks is guaranteed to be the header.
42  assert(Header == *CurLoop->getBlocks().begin() &&
43  "First block must be header");
44  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
45  BBE = CurLoop->block_end();
46  (BB != BBE) && !MayThrow; ++BB)
48 
49  // Compute funclet colors if we might sink/hoist in a function with a funclet
50  // personality routine.
51  Function *Fn = CurLoop->getHeader()->getParent();
52  if (Fn->hasPersonalityFn())
53  if (Constant *PersonalityFn = Fn->getPersonalityFn())
54  if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
56 }
57 
58 /// Return true if we can prove that the given ExitBlock is not reached on the
59 /// first iteration of the given loop. That is, the backedge of the loop must
60 /// be executed before the ExitBlock is executed in any dynamic execution trace.
61 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
62  const DominatorTree *DT,
63  const Loop *CurLoop) {
64  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
65  if (!CondExitBlock)
66  // expect unique exits
67  return false;
68  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
69  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
70  if (!BI || !BI->isConditional())
71  return false;
72  // If condition is constant and false leads to ExitBlock then we always
73  // execute the true branch.
74  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
75  return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
76  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
77  if (!Cond)
78  return false;
79  // todo: this would be a lot more powerful if we used scev, but all the
80  // plumbing is currently missing to pass a pointer in from the pass
81  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
82  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
83  auto *RHS = Cond->getOperand(1);
84  if (!LHS || LHS->getParent() != CurLoop->getHeader())
85  return false;
86  auto DL = ExitBlock->getModule()->getDataLayout();
87  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
88  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
89  IVStart, RHS,
90  {DL, /*TLI*/ nullptr,
91  DT, /*AC*/ nullptr, BI});
92  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
93  if (!SimpleCst)
94  return false;
95  if (ExitBlock == BI->getSuccessor(0))
96  return SimpleCst->isZeroValue();
97  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
98  return SimpleCst->isAllOnesValue();
99 }
100 
101 void LoopSafetyInfo::collectTransitivePredecessors(
102  const Loop *CurLoop, const BasicBlock *BB,
103  SmallPtrSetImpl<const BasicBlock *> &Predecessors) const {
104  assert(Predecessors.empty() && "Garbage in predecessors set?");
105  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
106  if (BB == CurLoop->getHeader())
107  return;
109  for (auto *Pred : predecessors(BB)) {
110  Predecessors.insert(Pred);
111  WorkList.push_back(Pred);
112  }
113  while (!WorkList.empty()) {
114  auto *Pred = WorkList.pop_back_val();
115  assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
116  // We are not interested in backedges and we don't want to leave loop.
117  if (Pred == CurLoop->getHeader())
118  continue;
119  // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
120  // blocks of this inner loop, even those that are always executed AFTER the
121  // BB. It may make our analysis more conservative than it could be, see test
122  // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
123  // We can ignore backedge of all loops containing BB to get a sligtly more
124  // optimistic result.
125  for (auto *PredPred : predecessors(Pred))
126  if (Predecessors.insert(PredPred).second)
127  WorkList.push_back(PredPred);
128  }
129 }
130 
132  const BasicBlock *BB,
133  const DominatorTree *DT) const {
134  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
135 
136  // Fast path: header is always reached once the loop is entered.
137  if (BB == CurLoop->getHeader())
138  return true;
139 
140  // Collect all transitive predecessors of BB in the same loop. This set will
141  // be a subset of the blocks within the loop.
143  collectTransitivePredecessors(CurLoop, BB, Predecessors);
144 
145  // Make sure that all successors of all predecessors of BB are either:
146  // 1) BB,
147  // 2) Also predecessors of BB,
148  // 3) Exit blocks which are not taken on 1st iteration.
149  // Memoize blocks we've already checked.
150  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
151  for (auto *Pred : Predecessors)
152  for (auto *Succ : successors(Pred))
153  if (CheckedSuccessors.insert(Succ).second &&
154  Succ != BB && !Predecessors.count(Succ))
155  // By discharging conditions that are not executed on the 1st iteration,
156  // we guarantee that *at least* on the first iteration all paths from
157  // header that *may* execute will lead us to the block of interest. So
158  // that if we had virtually peeled one iteration away, in this peeled
159  // iteration the set of predecessors would contain only paths from
160  // header to BB without any exiting edges that may execute.
161  //
162  // TODO: We only do it for exiting edges currently. We could use the
163  // same function to skip some of the edges within the loop if we know
164  // that they will not be taken on the 1st iteration.
165  //
166  // TODO: If we somehow know the number of iterations in loop, the same
167  // check may be done for any arbitrary N-th iteration as long as N is
168  // not greater than minimum number of iterations in this loop.
169  if (CurLoop->contains(Succ) ||
170  !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
171  return false;
172 
173  // All predecessors can only lead us to BB.
174  return true;
175 }
176 
177 /// Returns true if the instruction in a loop is guaranteed to execute at least
178 /// once.
180  const DominatorTree *DT, const Loop *CurLoop,
181  const LoopSafetyInfo *SafetyInfo) {
182  // We have to check to make sure that the instruction dominates all
183  // of the exit blocks. If it doesn't, then there is a path out of the loop
184  // which does not execute this instruction, so we can't hoist it.
185 
186  // If the instruction is in the header block for the loop (which is very
187  // common), it is always guaranteed to dominate the exit blocks. Since this
188  // is a common case, and can save some work, check it now.
189  if (Inst.getParent() == CurLoop->getHeader())
190  // If there's a throw in the header block, we can't guarantee we'll reach
191  // Inst unless we can prove that Inst comes before the potential implicit
192  // exit. At the moment, we use a (cheap) hack for the common case where
193  // the instruction of interest is the first one in the block.
194  return !SafetyInfo->headerMayThrow() ||
195  Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
196 
197  // Somewhere in this loop there is an instruction which may throw and make us
198  // exit the loop.
199  if (SafetyInfo->anyBlockMayThrow())
200  return false;
201 
202  // If there is a path from header to exit or latch that doesn't lead to our
203  // instruction's block, return false.
204  if (!SafetyInfo->allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT))
205  return false;
206 
207  return true;
208 }
209 
210 
211 namespace {
212  struct MustExecutePrinter : public FunctionPass {
213 
214  static char ID; // Pass identification, replacement for typeid
215  MustExecutePrinter() : FunctionPass(ID) {
217  }
218  void getAnalysisUsage(AnalysisUsage &AU) const override {
219  AU.setPreservesAll();
222  }
223  bool runOnFunction(Function &F) override;
224  };
225 }
226 
227 char MustExecutePrinter::ID = 0;
228 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
229  "Instructions which execute on loop entry", false, true)
232 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
233  "Instructions which execute on loop entry", false, true)
234 
236  return new MustExecutePrinter();
237 }
238 
239 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
240  // TODO: merge these two routines. For the moment, we display the best
241  // result obtained by *either* implementation. This is a bit unfair since no
242  // caller actually gets the full power at the moment.
243  LoopSafetyInfo LSI;
244  LSI.computeLoopSafetyInfo(L);
245  return isGuaranteedToExecute(I, DT, L, &LSI) ||
247 }
248 
249 namespace {
250 /// An assembly annotator class to print must execute information in
251 /// comments.
252 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
254 
255 public:
256  MustExecuteAnnotatedWriter(const Function &F,
257  DominatorTree &DT, LoopInfo &LI) {
258  for (auto &I: instructions(F)) {
259  Loop *L = LI.getLoopFor(I.getParent());
260  while (L) {
261  if (isMustExecuteIn(I, L, &DT)) {
262  MustExec[&I].push_back(L);
263  }
264  L = L->getParentLoop();
265  };
266  }
267  }
268  MustExecuteAnnotatedWriter(const Module &M,
269  DominatorTree &DT, LoopInfo &LI) {
270  for (auto &F : M)
271  for (auto &I: instructions(F)) {
272  Loop *L = LI.getLoopFor(I.getParent());
273  while (L) {
274  if (isMustExecuteIn(I, L, &DT)) {
275  MustExec[&I].push_back(L);
276  }
277  L = L->getParentLoop();
278  };
279  }
280  }
281 
282 
283  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
284  if (!MustExec.count(&V))
285  return;
286 
287  const auto &Loops = MustExec.lookup(&V);
288  const auto NumLoops = Loops.size();
289  if (NumLoops > 1)
290  OS << " ; (mustexec in " << NumLoops << " loops: ";
291  else
292  OS << " ; (mustexec in: ";
293 
294  bool first = true;
295  for (const Loop *L : Loops) {
296  if (!first)
297  OS << ", ";
298  first = false;
299  OS << L->getHeader()->getName();
300  }
301  OS << ")";
302  }
303 };
304 } // namespace
305 
307  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
308  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
309 
310  MustExecuteAnnotatedWriter Writer(F, DT, LI);
311  F.print(dbgs(), &Writer);
312 
313  return false;
314 }
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:675
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop)
Return true if we can prove that the given ExitBlock is not reached on the first iteration of the giv...
Definition: MustExecute.cpp:61
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
BasicBlock * getSuccessor(unsigned i) const
F(f)
block Block Frequency true
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Hexagon Hardware Loops
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:363
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
BlockT * getHeader() const
Definition: LoopInfo.h:100
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch, catchpad/ret, and cleanuppad/ret.
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the function to an output stream with an optional AssemblyAnnotationWriter. ...
Definition: AsmWriter.cpp:4001
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:702
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
Value * getOperand(unsigned i) const
Definition: User.h:170
FunctionPass * createMustExecutePrinter()
static bool runOnFunction(Function &F, bool PostInlining)
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:235
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Conditional or Unconditional Branch instruction.
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", "Instructions which execute on loop entry", false, true) INITIALIZE_PASS_END(MustExecutePrinter
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned first
bool anyBlockMayThrow() const
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:29
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const
Return true if we must reach the block BB under assumption that the loop CurLoop is entered and no in...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
DenseMap< BasicBlock *, ColorVector > BlockColors
Definition: MustExecute.h:61
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:123
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void setPreservesAll()
Set by analyses that do not transform their input at all.
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
print mustexecute
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
bool headerMayThrow() const
Returns true iff the header block of the loop for which this info is calculated contains an instructi...
Definition: MustExecute.cpp:25
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
block_iterator block_end() const
Definition: LoopInfo.h:155
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
Captures loop safety information.
Definition: MustExecute.h:47
void computeLoopSafetyInfo(Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:33
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:141
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:181
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1302
succ_range successors(Instruction *I)
Definition: CFG.h:262
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
print Instructions which execute on loop entry
inst_range instructions(Function *F)
Definition: InstIterator.h:134
void initializeMustExecutePrinterPass(PassRegistry &)
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:196
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo)
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
block_iterator block_begin() const
Definition: LoopInfo.h:154
const BasicBlock * getParent() const
Definition: Instruction.h:67