LLVM  7.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 
25 /// Computes loop safety information, checks loop body & header
26 /// for the possibility of may throw exception.
27 ///
28 void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
29  assert(CurLoop != nullptr && "CurLoop cant be null");
30  BasicBlock *Header = CurLoop->getHeader();
31  // Setting default safety values.
32  SafetyInfo->MayThrow = false;
33  SafetyInfo->HeaderMayThrow = false;
34  // Iterate over header and compute safety info.
35  SafetyInfo->HeaderMayThrow =
37 
38  SafetyInfo->MayThrow = SafetyInfo->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) && !SafetyInfo->MayThrow; ++BB)
47  SafetyInfo->MayThrow |=
49 
50  // Compute funclet colors if we might sink/hoist in a function with a funclet
51  // personality routine.
52  Function *Fn = CurLoop->getHeader()->getParent();
53  if (Fn->hasPersonalityFn())
54  if (Constant *PersonalityFn = Fn->getPersonalityFn())
55  if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
56  SafetyInfo->BlockColors = colorEHFunclets(*Fn);
57 }
58 
59 /// Return true if we can prove that the given ExitBlock is not reached on the
60 /// first iteration of the given loop. That is, the backedge of the loop must
61 /// be executed before the ExitBlock is executed in any dynamic execution trace.
63  const DominatorTree *DT,
64  const Loop *CurLoop) {
65  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
66  if (!CondExitBlock)
67  // expect unique exits
68  return false;
69  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
70  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
71  if (!BI || !BI->isConditional())
72  return false;
73  // If condition is constant and false leads to ExitBlock then we always
74  // execute the true branch.
75  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
76  return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
77  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
78  if (!Cond)
79  return false;
80  // todo: this would be a lot more powerful if we used scev, but all the
81  // plumbing is currently missing to pass a pointer in from the pass
82  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
83  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
84  auto *RHS = Cond->getOperand(1);
85  if (!LHS || LHS->getParent() != CurLoop->getHeader())
86  return false;
87  auto DL = ExitBlock->getModule()->getDataLayout();
88  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
89  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
90  IVStart, RHS,
91  {DL, /*TLI*/ nullptr,
92  DT, /*AC*/ nullptr, BI});
93  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
94  if (!SimpleCst)
95  return false;
96  if (ExitBlock == BI->getSuccessor(0))
97  return SimpleCst->isZeroValue();
98  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
99  return SimpleCst->isAllOnesValue();
100 }
101 
102 /// Returns true if the instruction in a loop is guaranteed to execute at least
103 /// once.
105  const DominatorTree *DT, const Loop *CurLoop,
106  const LoopSafetyInfo *SafetyInfo) {
107  // We have to check to make sure that the instruction dominates all
108  // of the exit blocks. If it doesn't, then there is a path out of the loop
109  // which does not execute this instruction, so we can't hoist it.
110 
111  // If the instruction is in the header block for the loop (which is very
112  // common), it is always guaranteed to dominate the exit blocks. Since this
113  // is a common case, and can save some work, check it now.
114  if (Inst.getParent() == CurLoop->getHeader())
115  // If there's a throw in the header block, we can't guarantee we'll reach
116  // Inst unless we can prove that Inst comes before the potential implicit
117  // exit. At the moment, we use a (cheap) hack for the common case where
118  // the instruction of interest is the first one in the block.
119  return !SafetyInfo->HeaderMayThrow ||
120  Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
121 
122  // Somewhere in this loop there is an instruction which may throw and make us
123  // exit the loop.
124  if (SafetyInfo->MayThrow)
125  return false;
126 
127  // Note: There are two styles of reasoning intermixed below for
128  // implementation efficiency reasons. They are:
129  // 1) If we can prove that the instruction dominates all exit blocks, then we
130  // know the instruction must have executed on *some* iteration before we
131  // exit. We do not prove *which* iteration the instruction must execute on.
132  // 2) If we can prove that the instruction dominates the latch and all exits
133  // which might be taken on the first iteration, we know the instruction must
134  // execute on the first iteration. This second style allows a conditional
135  // exit before the instruction of interest which is provably not taken on the
136  // first iteration. This is a quite common case for range check like
137  // patterns. TODO: support loops with multiple latches.
138 
139  const bool InstDominatesLatch =
140  CurLoop->getLoopLatch() != nullptr &&
141  DT->dominates(Inst.getParent(), CurLoop->getLoopLatch());
142 
143  // Get the exit blocks for the current loop.
144  SmallVector<BasicBlock *, 8> ExitBlocks;
145  CurLoop->getExitBlocks(ExitBlocks);
146 
147  // Verify that the block dominates each of the exit blocks of the loop.
148  for (BasicBlock *ExitBlock : ExitBlocks)
149  if (!DT->dominates(Inst.getParent(), ExitBlock))
150  if (!InstDominatesLatch ||
151  !CanProveNotTakenFirstIteration(ExitBlock, DT, CurLoop))
152  return false;
153 
154  // As a degenerate case, if the loop is statically infinite then we haven't
155  // proven anything since there are no exit blocks.
156  if (ExitBlocks.empty())
157  return false;
158 
159  // FIXME: In general, we have to prove that the loop isn't an infinite loop.
160  // See http::llvm.org/PR24078 . (The "ExitBlocks.empty()" check above is
161  // just a special case of this.)
162  return true;
163 }
164 
165 
166 namespace {
167  struct MustExecutePrinter : public FunctionPass {
168 
169  static char ID; // Pass identification, replacement for typeid
170  MustExecutePrinter() : FunctionPass(ID) {
172  }
173  void getAnalysisUsage(AnalysisUsage &AU) const override {
174  AU.setPreservesAll();
177  }
178  bool runOnFunction(Function &F) override;
179  };
180 }
181 
182 char MustExecutePrinter::ID = 0;
183 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
184  "Instructions which execute on loop entry", false, true)
187 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
188  "Instructions which execute on loop entry", false, true)
189 
191  return new MustExecutePrinter();
192 }
193 
194 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
195  // TODO: merge these two routines. For the moment, we display the best
196  // result obtained by *either* implementation. This is a bit unfair since no
197  // caller actually gets the full power at the moment.
198  LoopSafetyInfo LSI;
199  computeLoopSafetyInfo(&LSI, L);
200  return isGuaranteedToExecute(I, DT, L, &LSI) ||
202 }
203 
204 namespace {
205 /// An assembly annotator class to print must execute information in
206 /// comments.
207 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
209 
210 public:
211  MustExecuteAnnotatedWriter(const Function &F,
212  DominatorTree &DT, LoopInfo &LI) {
213  for (auto &I: instructions(F)) {
214  Loop *L = LI.getLoopFor(I.getParent());
215  while (L) {
216  if (isMustExecuteIn(I, L, &DT)) {
217  MustExec[&I].push_back(L);
218  }
219  L = L->getParentLoop();
220  };
221  }
222  }
223  MustExecuteAnnotatedWriter(const Module &M,
224  DominatorTree &DT, LoopInfo &LI) {
225  for (auto &F : M)
226  for (auto &I: instructions(F)) {
227  Loop *L = LI.getLoopFor(I.getParent());
228  while (L) {
229  if (isMustExecuteIn(I, L, &DT)) {
230  MustExec[&I].push_back(L);
231  }
232  L = L->getParentLoop();
233  };
234  }
235  }
236 
237 
238  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
239  if (!MustExec.count(&V))
240  return;
241 
242  const auto &Loops = MustExec.lookup(&V);
243  const auto NumLoops = Loops.size();
244  if (NumLoops > 1)
245  OS << " ; (mustexec in " << NumLoops << " loops: ";
246  else
247  OS << " ; (mustexec in: ";
248 
249  bool first = true;
250  for (const Loop *L : Loops) {
251  if (!first)
252  OS << ", ";
253  first = false;
254  OS << L->getHeader()->getName();
255  }
256  OS << ")";
257  }
258 };
259 } // namespace
260 
262  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
263  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
264 
265  MustExecuteAnnotatedWriter Writer(F, DT, LI);
266  F.print(dbgs(), &Writer);
267 
268  return false;
269 }
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:875
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
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
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)
DenseMap< BasicBlock *, ColorVector > BlockColors
Definition: MustExecute.h:44
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:361
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.
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:63
void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:28
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:3972
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:688
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
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
static bool CanProveNotTakenFirstIteration(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:62
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 contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:244
Module.h This file contains the declarations for the Module class.
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
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
Basic Alias true
print mustexecute
Captures loop safety information.
Definition: MustExecute.h:39
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 ...
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:1288
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:254
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