LLVM  10.0.0svn
MustExecute.h
Go to the documentation of this file.
1 //===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===//
2 //
3 // 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
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// Contains a collection of routines for determining if a given instruction is
10 /// guaranteed to execute if a given point in control flow is reached. The most
11 /// common example is an instruction within a loop being provably executed if we
12 /// branch to the header of it's containing loop.
13 ///
14 /// There are two interfaces available to determine if an instruction is
15 /// executed once a given point in the control flow is reached:
16 /// 1) A loop-centric one derived from LoopSafetyInfo.
17 /// 2) A "must be executed context"-based one implemented in the
18 /// MustBeExecutedContextExplorer.
19 /// Please refer to the class comments for more information.
20 ///
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
24 #define LLVM_ANALYSIS_MUSTEXECUTE_H
25 
26 #include "llvm/ADT/DenseMap.h"
29 #include "llvm/Analysis/LoopInfo.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Instruction.h"
33 
34 namespace llvm {
35 
36 class Instruction;
37 class DominatorTree;
38 class Loop;
39 
40 /// Captures loop safety information.
41 /// It keep information for loop blocks may throw exception or otherwise
42 /// exit abnormaly on any iteration of the loop which might actually execute
43 /// at runtime. The primary way to consume this infromation is via
44 /// isGuaranteedToExecute below, but some callers bailout or fallback to
45 /// alternate reasoning if a loop contains any implicit control flow.
46 /// NOTE: LoopSafetyInfo contains cached information regarding loops and their
47 /// particular blocks. This information is only dropped on invocation of
48 /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
49 /// any thrower instructions have been added or removed from them, or if the
50 /// control flow has changed, or in case of other meaningful modifications, the
51 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
52 /// loop were made and the info wasn't recomputed properly, the behavior of all
53 /// methods except for computeLoopSafetyInfo is undefined.
55  // Used to update funclet bundle operands.
57 
58 protected:
59  /// Computes block colors.
60  void computeBlockColors(const Loop *CurLoop);
61 
62 public:
63  /// Returns block colors map that is used to update funclet operand bundles.
65 
66  /// Copy colors of block \p Old into the block \p New.
67  void copyColors(BasicBlock *New, BasicBlock *Old);
68 
69  /// Returns true iff the block \p BB potentially may throw exception. It can
70  /// be false-positive in cases when we want to avoid complex analysis.
71  virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
72 
73  /// Returns true iff any block of the loop for which this info is contains an
74  /// instruction that may throw or otherwise exit abnormally.
75  virtual bool anyBlockMayThrow() const = 0;
76 
77  /// Return true if we must reach the block \p BB under assumption that the
78  /// loop \p CurLoop is entered.
79  bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
80  const DominatorTree *DT) const;
81 
82  /// Computes safety information for a loop checks loop body & header for
83  /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
84  /// as argument. Updates safety information in LoopSafetyInfo argument.
85  /// Note: This is defined to clear and reinitialize an already initialized
86  /// LoopSafetyInfo. Some callers rely on this fact.
87  virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
88 
89  /// Returns true if the instruction in a loop is guaranteed to execute at
90  /// least once (under the assumption that the loop is entered).
91  virtual bool isGuaranteedToExecute(const Instruction &Inst,
92  const DominatorTree *DT,
93  const Loop *CurLoop) const = 0;
94 
95  LoopSafetyInfo() = default;
96 
97  virtual ~LoopSafetyInfo() = default;
98 };
99 
100 
101 /// Simple and conservative implementation of LoopSafetyInfo that can give
102 /// false-positive answers to its queries in order to avoid complicated
103 /// analysis.
105  bool MayThrow = false; // The current loop contains an instruction which
106  // may throw.
107  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
108 
109 public:
110  virtual bool blockMayThrow(const BasicBlock *BB) const;
111 
112  virtual bool anyBlockMayThrow() const;
113 
114  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
115 
116  virtual bool isGuaranteedToExecute(const Instruction &Inst,
117  const DominatorTree *DT,
118  const Loop *CurLoop) const;
119 
121 
122  virtual ~SimpleLoopSafetyInfo() {};
123 };
124 
125 /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
126 /// give precise answers on "may throw" queries. This implementation uses cache
127 /// that should be invalidated by calling the methods insertInstructionTo and
128 /// removeInstruction whenever we modify a basic block's contents by adding or
129 /// removing instructions.
131  bool MayThrow = false; // The current loop contains an instruction which
132  // may throw.
133  // Contains information about implicit control flow in this loop's blocks.
134  mutable ImplicitControlFlowTracking ICF;
135  // Contains information about instruction that may possibly write memory.
136  mutable MemoryWriteTracking MW;
137 
138 public:
139  virtual bool blockMayThrow(const BasicBlock *BB) const;
140 
141  virtual bool anyBlockMayThrow() const;
142 
143  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
144 
145  virtual bool isGuaranteedToExecute(const Instruction &Inst,
146  const DominatorTree *DT,
147  const Loop *CurLoop) const;
148 
149  /// Returns true if we could not execute a memory-modifying instruction before
150  /// we enter \p BB under assumption that \p CurLoop is entered.
151  bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
152  const;
153 
154  /// Returns true if we could not execute a memory-modifying instruction before
155  /// we execute \p I under assumption that \p CurLoop is entered.
156  bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
157  const;
158 
159  /// Inform the safety info that we are planning to insert a new instruction
160  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
161  /// it correct after this insertion.
162  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
163 
164  /// Inform safety info that we are planning to remove the instruction \p Inst
165  /// from its block. It will make all cache updates to keep it correct after
166  /// this removal.
167  void removeInstruction(const Instruction *Inst);
168 
169  ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
170 
171  virtual ~ICFLoopSafetyInfo() {};
172 };
173 
175 
176 /// Must be executed iterators visit stretches of instructions that are
177 /// guaranteed to be executed together, potentially with other instruction
178 /// executed in-between.
179 ///
180 /// Given the following code, and assuming all statements are single
181 /// instructions which transfer execution to the successor (see
182 /// isGuaranteedToTransferExecutionToSuccessor), there are two possible
183 /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
184 /// and E. If we start at C or D, we will visit all instructions A-E.
185 ///
186 /// \code
187 /// A;
188 /// B;
189 /// if (...) {
190 /// C;
191 /// D;
192 /// }
193 /// E;
194 /// \endcode
195 ///
196 ///
197 /// Below is the example extneded with instructions F and G. Now we assume F
198 /// might not transfer execution to it's successor G. As a result we get the
199 /// following visit sets:
200 ///
201 /// Start Instruction | Visit Set
202 /// A | A, B, E, F
203 /// B | A, B, E, F
204 /// C | A, B, C, D, E, F
205 /// D | A, B, C, D, E, F
206 /// E | A, B, E, F
207 /// F | A, B, E, F
208 /// G | A, B, E, F, G
209 ///
210 ///
211 /// \code
212 /// A;
213 /// B;
214 /// if (...) {
215 /// C;
216 /// D;
217 /// }
218 /// E;
219 /// F; // Might not transfer execution to its successor G.
220 /// G;
221 /// \endcode
222 ///
223 ///
224 /// A more complex example involving conditionals, loops, break, and continue
225 /// is shown below. We again assume all instructions will transmit control to
226 /// the successor and we assume we can prove the inner loop to be finite. We
227 /// omit non-trivial branch conditions as the exploration is oblivious to them.
228 /// Constant branches are assumed to be unconditional in the CFG. The resulting
229 /// visist sets are shown in the table below.
230 ///
231 /// \code
232 /// A;
233 /// while (true) {
234 /// B;
235 /// if (...)
236 /// C;
237 /// if (...)
238 /// continue;
239 /// D;
240 /// if (...)
241 /// break;
242 /// do {
243 /// if (...)
244 /// continue;
245 /// E;
246 /// } while (...);
247 /// F;
248 /// }
249 /// G;
250 /// \endcode
251 ///
252 /// Start Instruction | Visit Set
253 /// A | A, B
254 /// B | A, B
255 /// C | A, B, C
256 /// D | A, B, D
257 /// E | A, B, D, E, F
258 /// F | A, B, D, F
259 /// G | A, B, D, G
260 ///
261 ///
262 /// Note that the examples show optimal visist sets but not necessarily the ones
263 /// derived by the explorer depending on the available CFG analyses (see
264 /// MustBeExecutedContextExplorer). Also note that we, depending on the options,
265 /// the visit set can contain instructions from other functions.
267  /// Type declarations that make his class an input iterator.
268  ///{
269  typedef const Instruction *value_type;
270  typedef std::ptrdiff_t difference_type;
271  typedef const Instruction **pointer;
272  typedef const Instruction *&reference;
273  typedef std::input_iterator_tag iterator_category;
274  ///}
275 
277 
279  : Visited(Other.Visited), Explorer(Other.Explorer),
280  CurInst(Other.CurInst) {}
281 
283  : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
284  CurInst(Other.CurInst) {}
285 
287  if (this != &Other) {
288  std::swap(Visited, Other.Visited);
289  std::swap(CurInst, Other.CurInst);
290  }
291  return *this;
292  }
293 
295 
296  /// Pre- and post-increment operators.
297  ///{
299  CurInst = advance();
300  return *this;
301  }
302 
304  MustBeExecutedIterator tmp(*this);
305  operator++();
306  return tmp;
307  }
308  ///}
309 
310  /// Equality and inequality operators. Note that we ignore the history here.
311  ///{
312  bool operator==(const MustBeExecutedIterator &Other) const {
313  return CurInst == Other.CurInst;
314  }
315 
316  bool operator!=(const MustBeExecutedIterator &Other) const {
317  return !(*this == Other);
318  }
319  ///}
320 
321  /// Return the underlying instruction.
322  const Instruction *&operator*() { return CurInst; }
323  const Instruction *getCurrentInst() const { return CurInst; }
324 
325  /// Return true if \p I was encountered by this iterator already.
326  bool count(const Instruction *I) const { return Visited.count(I); }
327 
328 private:
330 
331  /// Private constructors.
332  MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
333 
334  /// Reset the iterator to its initial state pointing at \p I.
335  void reset(const Instruction *I);
336 
337  /// Try to advance one of the underlying positions (Head or Tail).
338  ///
339  /// \return The next instruction in the must be executed context, or nullptr
340  /// if none was found.
341  const Instruction *advance();
342 
343  /// A set to track the visited instructions in order to deal with endless
344  /// loops and recursion.
345  VisitedSetTy Visited;
346 
347  /// A reference to the explorer that created this iterator.
348  ExplorerTy &Explorer;
349 
350  /// The instruction we are currently exposing to the user. There is always an
351  /// instruction that we know is executed with the given program point,
352  /// initially the program point itself.
353  const Instruction *CurInst;
354 
356 };
357 
358 /// A "must be executed context" for a given program point PP is the set of
359 /// instructions, potentially before and after PP, that are executed always when
360 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
361 /// "must be executed contexts" in a module through the use of
362 /// MustBeExecutedIterator.
363 ///
364 /// The explorer exposes "must be executed iterators" that traverse the must be
365 /// executed context. There is little information sharing between iterators as
366 /// the expected use case involves few iterators for "far apart" instructions.
367 /// If that changes, we should consider caching more intermediate results.
369 
370  /// In the description of the parameters we use PP to denote a program point
371  /// for which the must be executed context is explored, or put differently,
372  /// for which the MustBeExecutedIterator is created.
373  ///
374  /// \param ExploreInterBlock Flag to indicate if instructions in blocks
375  /// other than the parent of PP should be
376  /// explored.
377  MustBeExecutedContextExplorer(bool ExploreInterBlock)
378  : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
379 
380  /// Clean up the dynamically allocated iterators.
382  DeleteContainerSeconds(InstructionIteratorMap);
383  }
384 
385  /// Iterator-based interface. \see MustBeExecutedIterator.
386  ///{
389 
390  /// Return an iterator to explore the context around \p PP.
391  iterator &begin(const Instruction *PP) {
392  auto *&It = InstructionIteratorMap[PP];
393  if (!It)
394  It = new iterator(*this, PP);
395  return *It;
396  }
397 
398  /// Return an iterator to explore the cached context around \p PP.
399  const_iterator &begin(const Instruction *PP) const {
400  return *InstructionIteratorMap.lookup(PP);
401  }
402 
403  /// Return an universal end iterator.
404  ///{
405  iterator &end() { return EndIterator; }
406  iterator &end(const Instruction *) { return EndIterator; }
407 
408  const_iterator &end() const { return EndIterator; }
409  const_iterator &end(const Instruction *) const { return EndIterator; }
410  ///}
411 
412  /// Return an iterator range to explore the context around \p PP.
414  return llvm::make_range(begin(PP), end(PP));
415  }
416 
417  /// Return an iterator range to explore the cached context around \p PP.
419  return llvm::make_range(begin(PP), end(PP));
420  }
421  ///}
422 
423  /// Return the next instruction that is guaranteed to be executed after \p PP.
424  ///
425  /// \param It The iterator that is used to traverse the must be
426  /// executed context.
427  /// \param PP The program point for which the next instruction
428  /// that is guaranteed to execute is determined.
429  const Instruction *
430  getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
431  const Instruction *PP);
432 
433  /// Parameter that limit the performed exploration. See the constructor for
434  /// their meaning.
435  ///{
436  const bool ExploreInterBlock;
437  ///}
438 
439 private:
440  /// Map from instructions to associated must be executed iterators.
442  InstructionIteratorMap;
443 
444  /// A unique end iterator.
445  MustBeExecutedIterator EndIterator;
446 };
447 
448 } // namespace llvm
449 
450 #endif
void DeleteContainerSeconds(Container &C)
In a container of pairs (usually a map) whose second element is a pointer, deletes the second element...
Definition: STLExtras.h:1137
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
std::input_iterator_tag iterator_category
Definition: MustExecute.h:273
iterator & end(const Instruction *)
Definition: MustExecute.h:406
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:282
iterator & end()
Return an universal end iterator.
Definition: MustExecute.h:405
const_iterator & end() const
Definition: MustExecute.h:408
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
virtual bool anyBlockMayThrow() const =0
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
const Instruction *& operator*()
}
Definition: MustExecute.h:322
~MustBeExecutedContextExplorer()
Clean up the dynamically allocated iterators.
Definition: MustExecute.h:381
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:104
Definition: BitVector.h:937
const Instruction * value_type
Type declarations that make his class an input iterator.
Definition: MustExecute.h:269
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:130
MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:286
const_iterator & begin(const Instruction *PP) const
Return an iterator to explore the cached context around PP.
Definition: MustExecute.h:399
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:413
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:266
const Instruction ** pointer
Definition: MustExecute.h:271
MustBeExecutedIterator & operator++()
Pre- and post-increment operators.
Definition: MustExecute.h:298
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:34
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const =0
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
ICFLoopSafetyInfo(DominatorTree *DT)
Definition: MustExecute.h:169
MustBeExecutedContextExplorer(bool ExploreInterBlock)
In the description of the parameters we use PP to denote a program point for which the must be execut...
Definition: MustExecute.h:377
MustBeExecutedIterator(const MustBeExecutedIterator &Other)
Definition: MustExecute.h:278
LoopSafetyInfo()=default
std::ptrdiff_t difference_type
Definition: MustExecute.h:270
bool operator==(const MustBeExecutedIterator &Other) const
}
Definition: MustExecute.h:312
llvm::iterator_range< const_iterator > range(const Instruction *PP) const
Return an iterator range to explore the cached context around PP.
Definition: MustExecute.h:418
virtual ~LoopSafetyInfo()=default
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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...
bool count(const Instruction *I) const
Return true if I was encountered by this iterator already.
Definition: MustExecute.h:326
MustBeExecutedIterator operator++(int)
Definition: MustExecute.h:303
const_iterator & end(const Instruction *) const
Definition: MustExecute.h:409
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
A range adaptor for a pair of iterators.
A "must be executed context" for a given program point PP is the set of instructions, potentially before and after PP, that are executed always when PP is reached.
Definition: MustExecute.h:368
virtual ~ICFLoopSafetyInfo()
Definition: MustExecute.h:171
bool operator!=(const MustBeExecutedIterator &Other) const
Definition: MustExecute.h:316
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:436
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
const Instruction * getCurrentInst() const
Definition: MustExecute.h:323
#define I(x, y, z)
Definition: MD5.cpp:58
Captures loop safety information.
Definition: MustExecute.h:54
This class allows to keep track on instructions with implicit control flow.
virtual void computeLoopSafetyInfo(const Loop *CurLoop)=0
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
const Instruction *& reference
Definition: MustExecute.h:272
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
Definition: MustExecute.h:391
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:30