LLVM  16.0.0git
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"
27 #include "llvm/ADT/DenseSet.h"
30 #include "llvm/IR/PassManager.h"
31 
32 namespace llvm {
33 
34 namespace {
35 template <typename T> using GetterTy = std::function<T *(const Function &F)>;
36 }
37 
38 class BasicBlock;
39 class DominatorTree;
40 class Instruction;
41 class Loop;
42 class LoopInfo;
43 class PostDominatorTree;
44 class raw_ostream;
45 
46 /// Captures loop safety information.
47 /// It keep information for loop blocks may throw exception or otherwise
48 /// exit abnormally on any iteration of the loop which might actually execute
49 /// at runtime. The primary way to consume this information is via
50 /// isGuaranteedToExecute below, but some callers bailout or fallback to
51 /// alternate reasoning if a loop contains any implicit control flow.
52 /// NOTE: LoopSafetyInfo contains cached information regarding loops and their
53 /// particular blocks. This information is only dropped on invocation of
54 /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
55 /// any thrower instructions have been added or removed from them, or if the
56 /// control flow has changed, or in case of other meaningful modifications, the
57 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
58 /// loop were made and the info wasn't recomputed properly, the behavior of all
59 /// methods except for computeLoopSafetyInfo is undefined.
61  // Used to update funclet bundle operands.
63 
64 protected:
65  /// Computes block colors.
66  void computeBlockColors(const Loop *CurLoop);
67 
68 public:
69  /// Returns block colors map that is used to update funclet operand bundles.
71 
72  /// Copy colors of block \p Old into the block \p New.
73  void copyColors(BasicBlock *New, BasicBlock *Old);
74 
75  /// Returns true iff the block \p BB potentially may throw exception. It can
76  /// be false-positive in cases when we want to avoid complex analysis.
77  virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
78 
79  /// Returns true iff any block of the loop for which this info is contains an
80  /// instruction that may throw or otherwise exit abnormally.
81  virtual bool anyBlockMayThrow() const = 0;
82 
83  /// Return true if we must reach the block \p BB under assumption that the
84  /// loop \p CurLoop is entered.
85  bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
86  const DominatorTree *DT) const;
87 
88  /// Computes safety information for a loop checks loop body & header for
89  /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
90  /// as argument. Updates safety information in LoopSafetyInfo argument.
91  /// Note: This is defined to clear and reinitialize an already initialized
92  /// LoopSafetyInfo. Some callers rely on this fact.
93  virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
94 
95  /// Returns true if the instruction in a loop is guaranteed to execute at
96  /// least once (under the assumption that the loop is entered).
97  virtual bool isGuaranteedToExecute(const Instruction &Inst,
98  const DominatorTree *DT,
99  const Loop *CurLoop) const = 0;
100 
101  LoopSafetyInfo() = default;
102 
103  virtual ~LoopSafetyInfo() = default;
104 };
105 
106 
107 /// Simple and conservative implementation of LoopSafetyInfo that can give
108 /// false-positive answers to its queries in order to avoid complicated
109 /// analysis.
111  bool MayThrow = false; // The current loop contains an instruction which
112  // may throw.
113  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
114 
115 public:
116  bool blockMayThrow(const BasicBlock *BB) const override;
117 
118  bool anyBlockMayThrow() const override;
119 
120  void computeLoopSafetyInfo(const Loop *CurLoop) override;
121 
122  bool isGuaranteedToExecute(const Instruction &Inst,
123  const DominatorTree *DT,
124  const Loop *CurLoop) const override;
125 };
126 
127 /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
128 /// give precise answers on "may throw" queries. This implementation uses cache
129 /// that should be invalidated by calling the methods insertInstructionTo and
130 /// removeInstruction whenever we modify a basic block's contents by adding or
131 /// removing instructions.
133  bool MayThrow = false; // The current loop contains an instruction which
134  // may throw.
135  // Contains information about implicit control flow in this loop's blocks.
136  mutable ImplicitControlFlowTracking ICF;
137  // Contains information about instruction that may possibly write memory.
138  mutable MemoryWriteTracking MW;
139 
140 public:
141  bool blockMayThrow(const BasicBlock *BB) const override;
142 
143  bool anyBlockMayThrow() const override;
144 
145  void computeLoopSafetyInfo(const Loop *CurLoop) override;
146 
147  bool isGuaranteedToExecute(const Instruction &Inst,
148  const DominatorTree *DT,
149  const Loop *CurLoop) const override;
150 
151  /// Returns true if we could not execute a memory-modifying instruction before
152  /// we enter \p BB under assumption that \p CurLoop is entered.
153  bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
154  const;
155 
156  /// Returns true if we could not execute a memory-modifying instruction before
157  /// we execute \p I under assumption that \p CurLoop is entered.
158  bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
159  const;
160 
161  /// Inform the safety info that we are planning to insert a new instruction
162  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
163  /// it correct after this insertion.
164  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
165 
166  /// Inform safety info that we are planning to remove the instruction \p Inst
167  /// from its block. It will make all cache updates to keep it correct after
168  /// this removal.
169  void removeInstruction(const Instruction *Inst);
170 };
171 
172 bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI);
173 
175 
176 /// Enum that allows us to spell out the direction.
178  BACKWARD = 0,
179  FORWARD = 1,
180 };
181 
182 /// Must be executed iterators visit stretches of instructions that are
183 /// guaranteed to be executed together, potentially with other instruction
184 /// executed in-between.
185 ///
186 /// Given the following code, and assuming all statements are single
187 /// instructions which transfer execution to the successor (see
188 /// isGuaranteedToTransferExecutionToSuccessor), there are two possible
189 /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
190 /// and E. If we start at C or D, we will visit all instructions A-E.
191 ///
192 /// \code
193 /// A;
194 /// B;
195 /// if (...) {
196 /// C;
197 /// D;
198 /// }
199 /// E;
200 /// \endcode
201 ///
202 ///
203 /// Below is the example extneded with instructions F and G. Now we assume F
204 /// might not transfer execution to it's successor G. As a result we get the
205 /// following visit sets:
206 ///
207 /// Start Instruction | Visit Set
208 /// A | A, B, E, F
209 /// B | A, B, E, F
210 /// C | A, B, C, D, E, F
211 /// D | A, B, C, D, E, F
212 /// E | A, B, E, F
213 /// F | A, B, E, F
214 /// G | A, B, E, F, G
215 ///
216 ///
217 /// \code
218 /// A;
219 /// B;
220 /// if (...) {
221 /// C;
222 /// D;
223 /// }
224 /// E;
225 /// F; // Might not transfer execution to its successor G.
226 /// G;
227 /// \endcode
228 ///
229 ///
230 /// A more complex example involving conditionals, loops, break, and continue
231 /// is shown below. We again assume all instructions will transmit control to
232 /// the successor and we assume we can prove the inner loop to be finite. We
233 /// omit non-trivial branch conditions as the exploration is oblivious to them.
234 /// Constant branches are assumed to be unconditional in the CFG. The resulting
235 /// visist sets are shown in the table below.
236 ///
237 /// \code
238 /// A;
239 /// while (true) {
240 /// B;
241 /// if (...)
242 /// C;
243 /// if (...)
244 /// continue;
245 /// D;
246 /// if (...)
247 /// break;
248 /// do {
249 /// if (...)
250 /// continue;
251 /// E;
252 /// } while (...);
253 /// F;
254 /// }
255 /// G;
256 /// \endcode
257 ///
258 /// Start Instruction | Visit Set
259 /// A | A, B
260 /// B | A, B
261 /// C | A, B, C
262 /// D | A, B, D
263 /// E | A, B, D, E, F
264 /// F | A, B, D, F
265 /// G | A, B, D, G
266 ///
267 ///
268 /// Note that the examples show optimal visist sets but not necessarily the ones
269 /// derived by the explorer depending on the available CFG analyses (see
270 /// MustBeExecutedContextExplorer). Also note that we, depending on the options,
271 /// the visit set can contain instructions from other functions.
273  /// Type declarations that make his class an input iterator.
274  ///{
275  typedef const Instruction *value_type;
276  typedef std::ptrdiff_t difference_type;
277  typedef const Instruction **pointer;
278  typedef const Instruction *&reference;
279  typedef std::input_iterator_tag iterator_category;
280  ///}
281 
283 
284  MustBeExecutedIterator(const MustBeExecutedIterator &Other) = default;
285 
287  : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
288  CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
289 
291  if (this != &Other) {
292  std::swap(Visited, Other.Visited);
293  std::swap(CurInst, Other.CurInst);
294  std::swap(Head, Other.Head);
295  std::swap(Tail, Other.Tail);
296  }
297  return *this;
298  }
299 
300  ~MustBeExecutedIterator() = default;
301 
302  /// Pre- and post-increment operators.
303  ///{
305  CurInst = advance();
306  return *this;
307  }
308 
311  operator++();
312  return tmp;
313  }
314  ///}
315 
316  /// Equality and inequality operators. Note that we ignore the history here.
317  ///{
318  bool operator==(const MustBeExecutedIterator &Other) const {
319  return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;
320  }
321 
322  bool operator!=(const MustBeExecutedIterator &Other) const {
323  return !(*this == Other);
324  }
325  ///}
326 
327  /// Return the underlying instruction.
328  const Instruction *&operator*() { return CurInst; }
329  const Instruction *getCurrentInst() const { return CurInst; }
330 
331  /// Return true if \p I was encountered by this iterator already.
332  bool count(const Instruction *I) const {
333  return Visited.count({I, ExplorationDirection::FORWARD}) ||
334  Visited.count({I, ExplorationDirection::BACKWARD});
335  }
336 
337 private:
338  using VisitedSetTy =
340 
341  /// Private constructors.
342  MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
343 
344  /// Reset the iterator to its initial state pointing at \p I.
345  void reset(const Instruction *I);
346 
347  /// Reset the iterator to point at \p I, keep cached state.
348  void resetInstruction(const Instruction *I);
349 
350  /// Try to advance one of the underlying positions (Head or Tail).
351  ///
352  /// \return The next instruction in the must be executed context, or nullptr
353  /// if none was found.
354  const Instruction *advance();
355 
356  /// A set to track the visited instructions in order to deal with endless
357  /// loops and recursion.
358  VisitedSetTy Visited;
359 
360  /// A reference to the explorer that created this iterator.
361  ExplorerTy &Explorer;
362 
363  /// The instruction we are currently exposing to the user. There is always an
364  /// instruction that we know is executed with the given program point,
365  /// initially the program point itself.
366  const Instruction *CurInst;
367 
368  /// Two positions that mark the program points where this iterator will look
369  /// for the next instruction. Note that the current instruction is either the
370  /// one pointed to by Head, Tail, or both.
371  const Instruction *Head, *Tail;
372 
374 };
375 
376 /// A "must be executed context" for a given program point PP is the set of
377 /// instructions, potentially before and after PP, that are executed always when
378 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
379 /// "must be executed contexts" in a module through the use of
380 /// MustBeExecutedIterator.
381 ///
382 /// The explorer exposes "must be executed iterators" that traverse the must be
383 /// executed context. There is little information sharing between iterators as
384 /// the expected use case involves few iterators for "far apart" instructions.
385 /// If that changes, we should consider caching more intermediate results.
387 
388  /// In the description of the parameters we use PP to denote a program point
389  /// for which the must be executed context is explored, or put differently,
390  /// for which the MustBeExecutedIterator is created.
391  ///
392  /// \param ExploreInterBlock Flag to indicate if instructions in blocks
393  /// other than the parent of PP should be
394  /// explored.
395  /// \param ExploreCFGForward Flag to indicate if instructions located after
396  /// PP in the CFG, e.g., post-dominating PP,
397  /// should be explored.
398  /// \param ExploreCFGBackward Flag to indicate if instructions located
399  /// before PP in the CFG, e.g., dominating PP,
400  /// should be explored.
403  GetterTy<const LoopInfo> LIGetter =
404  [](const Function &) { return nullptr; },
405  GetterTy<const DominatorTree> DTGetter =
406  [](const Function &) { return nullptr; },
407  GetterTy<const PostDominatorTree> PDTGetter =
408  [](const Function &) { return nullptr; })
411  ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter),
412  DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
413 
414  /// Iterator-based interface. \see MustBeExecutedIterator.
415  ///{
418 
419  /// Return an iterator to explore the context around \p PP.
420  iterator &begin(const Instruction *PP) {
421  auto &It = InstructionIteratorMap[PP];
422  if (!It)
423  It.reset(new iterator(*this, PP));
424  return *It;
425  }
426 
427  /// Return an iterator to explore the cached context around \p PP.
428  const_iterator &begin(const Instruction *PP) const {
429  return *InstructionIteratorMap.find(PP)->second;
430  }
431 
432  /// Return an universal end iterator.
433  ///{
434  iterator &end() { return EndIterator; }
435  iterator &end(const Instruction *) { return EndIterator; }
436 
437  const_iterator &end() const { return EndIterator; }
438  const_iterator &end(const Instruction *) const { return EndIterator; }
439  ///}
440 
441  /// Return an iterator range to explore the context around \p PP.
443  return llvm::make_range(begin(PP), end(PP));
444  }
445 
446  /// Return an iterator range to explore the cached context around \p PP.
448  return llvm::make_range(begin(PP), end(PP));
449  }
450  ///}
451 
452  /// Check \p Pred on all instructions in the context.
453  ///
454  /// This method will evaluate \p Pred and return
455  /// true if \p Pred holds in every instruction.
457  function_ref<bool(const Instruction *)> Pred) {
458  for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; ++EIt)
459  if (!Pred(*EIt))
460  return false;
461  return true;
462  }
463 
464  /// Helper to look for \p I in the context of \p PP.
465  ///
466  /// The context is expanded until \p I was found or no more expansion is
467  /// possible.
468  ///
469  /// \returns True, iff \p I was found.
470  bool findInContextOf(const Instruction *I, const Instruction *PP) {
471  auto EIt = begin(PP), EEnd = end(PP);
472  return findInContextOf(I, EIt, EEnd);
473  }
474 
475  /// Helper to look for \p I in the context defined by \p EIt and \p EEnd.
476  ///
477  /// The context is expanded until \p I was found or no more expansion is
478  /// possible.
479  ///
480  /// \returns True, iff \p I was found.
481  bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd) {
482  bool Found = EIt.count(I);
483  while (!Found && EIt != EEnd)
484  Found = (++EIt).getCurrentInst() == I;
485  return Found;
486  }
487 
488  /// Return the next instruction that is guaranteed to be executed after \p PP.
489  ///
490  /// \param It The iterator that is used to traverse the must be
491  /// executed context.
492  /// \param PP The program point for which the next instruction
493  /// that is guaranteed to execute is determined.
494  const Instruction *
496  const Instruction *PP);
497  /// Return the previous instr. that is guaranteed to be executed before \p PP.
498  ///
499  /// \param It The iterator that is used to traverse the must be
500  /// executed context.
501  /// \param PP The program point for which the previous instr.
502  /// that is guaranteed to execute is determined.
503  const Instruction *
505  const Instruction *PP);
506 
507  /// Find the next join point from \p InitBB in forward direction.
508  const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB);
509 
510  /// Find the next join point from \p InitBB in backward direction.
511  const BasicBlock *findBackwardJoinPoint(const BasicBlock *InitBB);
512 
513  /// Parameter that limit the performed exploration. See the constructor for
514  /// their meaning.
515  ///{
516  const bool ExploreInterBlock;
517  const bool ExploreCFGForward;
518  const bool ExploreCFGBackward;
519  ///}
520 
521 private:
522  /// Getters for common CFG analyses: LoopInfo, DominatorTree, and
523  /// PostDominatorTree.
524  ///{
525  GetterTy<const LoopInfo> LIGetter;
526  GetterTy<const DominatorTree> DTGetter;
527  GetterTy<const PostDominatorTree> PDTGetter;
528  ///}
529 
530  /// Map to cache isGuaranteedToTransferExecutionToSuccessor results.
532 
533  /// Map to cache containsIrreducibleCFG results.
534  DenseMap<const Function*, Optional<bool>> IrreducibleControlMap;
535 
536  /// Map from instructions to associated must be executed iterators.
538  InstructionIteratorMap;
539 
540  /// A unique end iterator.
541  MustBeExecutedIterator EndIterator;
542 };
543 
544 class MustExecutePrinterPass : public PassInfoMixin<MustExecutePrinterPass> {
545  raw_ostream &OS;
546 
547 public:
550 };
551 
553  : public PassInfoMixin<MustBeExecutedContextPrinterPass> {
554  raw_ostream &OS;
555 
556 public:
559 };
560 
561 } // namespace llvm
562 
563 #endif
llvm::LoopSafetyInfo::computeBlockColors
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
Definition: MustExecute.cpp:104
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::MustBeExecutedIterator::operator*
const Instruction *& operator*()
}
Definition: MustExecute.h:328
llvm::MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
Definition: MustExecute.cpp:704
llvm::LoopSafetyInfo::isGuaranteedToExecute
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::ImplicitControlFlowTracking
This class allows to keep track on instructions with implicit control flow.
Definition: InstructionPrecedenceTracking.h:99
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopSafetyInfo::allLoopPathsLeadToBlock
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.
Definition: MustExecute.cpp:190
llvm::MustBeExecutedContextExplorer::range
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:442
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::ICFLoopSafetyInfo::blockMayThrow
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:71
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::MustBeExecutedContextExplorer::ExploreInterBlock
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:516
llvm::MustExecutePrinterPass::MustExecutePrinterPass
MustExecutePrinterPass(raw_ostream &OS)
Definition: MustExecute.h:548
llvm::MustBeExecutedContextPrinterPass::MustBeExecutedContextPrinterPass
MustBeExecutedContextPrinterPass(raw_ostream &OS)
Definition: MustExecute.h:557
llvm::MustBeExecutedIterator::count
bool count(const Instruction *I) const
Return true if I was encountered by this iterator already.
Definition: MustExecute.h:332
llvm::MustBeExecutedIterator::difference_type
std::ptrdiff_t difference_type
Definition: MustExecute.h:276
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
DenseMap.h
EHPersonalities.h
llvm::MustBeExecutedIterator::pointer
const typedef Instruction ** pointer
Definition: MustExecute.h:277
T
#define T
Definition: Mips16ISelLowering.cpp:341
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::MustBeExecutedIterator::MustBeExecutedContextExplorer
friend struct MustBeExecutedContextExplorer
Definition: MustExecute.h:373
llvm::MustBeExecutedContextExplorer::ExploreCFGForward
const bool ExploreCFGForward
Definition: MustExecute.h:517
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
llvm::SimpleLoopSafetyInfo
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:110
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MustBeExecutedIterator::value_type
const typedef Instruction * value_type
Type declarations that make his class an input iterator.
Definition: MustExecute.h:275
llvm::MustBeExecutedContextPrinterPass
Definition: MustExecute.h:552
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:286
llvm::LoopSafetyInfo
Captures loop safety information.
Definition: MustExecute.h:60
llvm::LoopSafetyInfo::getBlockColors
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:32
llvm::MustExecutePrinterPass
Definition: MustExecute.h:544
DenseSet.h
llvm::LoopSafetyInfo::computeLoopSafetyInfo
virtual void computeLoopSafetyInfo(const Loop *CurLoop)=0
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
llvm::MustBeExecutedContextExplorer::end
const_iterator & end() const
Definition: MustExecute.h:437
llvm::Instruction
Definition: Instruction.h:42
llvm::MustBeExecutedIterator
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:272
llvm::MustBeExecutedIterator::reference
const typedef Instruction *& reference
Definition: MustExecute.h:278
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::MustBeExecutedIterator::getCurrentInst
const Instruction * getCurrentInst() const
Definition: MustExecute.h:329
llvm::MemoryWriteTracking
Definition: InstructionPrecedenceTracking.h:121
llvm::MustBeExecutedIterator::~MustBeExecutedIterator
~MustBeExecutedIterator()=default
llvm::MustBeExecutedContextExplorer::findInContextOf
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
Definition: MustExecute.h:470
llvm::MustBeExecutedContextExplorer::checkForAllContext
bool checkForAllContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
}
Definition: MustExecute.h:456
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MustBeExecutedContextPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: MustExecute.cpp:848
llvm::MustBeExecutedContextExplorer::iterator
MustBeExecutedIterator iterator
Iterator-based interface.
Definition: MustExecute.h:416
llvm::MustBeExecutedContextExplorer::MustBeExecutedContextExplorer
MustBeExecutedContextExplorer(bool ExploreInterBlock, bool ExploreCFGForward, bool ExploreCFGBackward, GetterTy< const LoopInfo > LIGetter=[](const Function &) { return nullptr;}, GetterTy< const DominatorTree > DTGetter=[](const Function &) { return nullptr;}, GetterTy< const PostDominatorTree > PDTGetter=[](const Function &) { return nullptr;})
In the description of the parameters we use PP to denote a program point for which the must be execut...
Definition: MustExecute.h:401
llvm::MustExecutePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MustExecute.cpp:837
llvm::MustBeExecutedContextExplorer::ExploreCFGBackward
const bool ExploreCFGBackward
Definition: MustExecute.h:518
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ICFLoopSafetyInfo::anyBlockMayThrow
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:75
llvm::MustBeExecutedContextExplorer::end
iterator & end(const Instruction *)
Definition: MustExecute.h:435
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ExplorationDirection
ExplorationDirection
Enum that allows us to spell out the direction.
Definition: MustExecute.h:177
llvm::MustBeExecutedContextExplorer::begin
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
Definition: MustExecute.h:420
llvm::ICFLoopSafetyInfo::doesNotWriteMemoryBefore
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
Definition: MustExecute.cpp:275
llvm::MustBeExecutedIterator::operator==
bool operator==(const MustBeExecutedIterator &Other) const
}
Definition: MustExecute.h:318
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1666
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::SimpleLoopSafetyInfo::computeLoopSafetyInfo
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:51
llvm::MustBeExecutedContextExplorer
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:386
llvm::MustBeExecutedContextExplorer::end
iterator & end()
Return an universal end iterator.
Definition: MustExecute.h:434
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::MustBeExecutedContextExplorer::findInContextOf
bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd)
Helper to look for I in the context defined by EIt and EEnd.
Definition: MustExecute.h:481
llvm::LoopSafetyInfo::blockMayThrow
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
llvm::ICFLoopSafetyInfo::insertInstructionTo
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB.
Definition: MustExecute.cpp:93
llvm::SimpleLoopSafetyInfo::anyBlockMayThrow
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:47
llvm::MustBeExecutedIterator::operator=
MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:290
llvm::ICFLoopSafetyInfo::removeInstruction
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:99
std
Definition: BitVector.h:851
llvm::LoopSafetyInfo::anyBlockMayThrow
virtual bool anyBlockMayThrow() const =0
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
llvm::ICFLoopSafetyInfo
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:132
PassManager.h
llvm::LoopSafetyInfo::copyColors
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:36
llvm::MustBeExecutedIterator::iterator_category
std::input_iterator_tag iterator_category
Definition: MustExecute.h:279
InstructionPrecedenceTracking.h
llvm::ExplorationDirection::FORWARD
@ FORWARD
llvm::MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
Definition: MustExecute.cpp:761
llvm::MustBeExecutedContextExplorer::range
llvm::iterator_range< const_iterator > range(const Instruction *PP) const
Return an iterator range to explore the cached context around PP.
Definition: MustExecute.h:447
llvm::ICFLoopSafetyInfo::computeLoopSafetyInfo
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:79
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::ExplorationDirection::BACKWARD
@ BACKWARD
llvm::SimpleLoopSafetyInfo::blockMayThrow
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:42
llvm::MustBeExecutedIterator::operator++
MustBeExecutedIterator operator++(int)
Definition: MustExecute.h:309
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::ICFLoopSafetyInfo::isGuaranteedToExecute
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
Definition: MustExecute.cpp:268
llvm::SimpleLoopSafetyInfo::isGuaranteedToExecute
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
Definition: MustExecute.cpp:249
llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
Definition: MustExecute.cpp:637
llvm::LoopSafetyInfo::~LoopSafetyInfo
virtual ~LoopSafetyInfo()=default
llvm::MustBeExecutedIterator::operator!=
bool operator!=(const MustBeExecutedIterator &Other) const
Definition: MustExecute.h:322
llvm::MustBeExecutedContextExplorer::findForwardJoinPoint
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
Definition: MustExecute.cpp:501
llvm::MustBeExecutedContextExplorer::begin
const_iterator & begin(const Instruction *PP) const
Return an iterator to explore the cached context around PP.
Definition: MustExecute.h:428
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
llvm::mayContainIrreducibleControl
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
Definition: MustExecute.cpp:480
llvm::LoopSafetyInfo::LoopSafetyInfo
LoopSafetyInfo()=default
llvm::MustBeExecutedIterator::ExplorerTy
MustBeExecutedContextExplorer ExplorerTy
}
Definition: MustExecute.h:282
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::MustBeExecutedIterator::operator++
MustBeExecutedIterator & operator++()
Pre- and post-increment operators.
Definition: MustExecute.h:304
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1247
llvm::MustBeExecutedContextExplorer::end
const_iterator & end(const Instruction *) const
Definition: MustExecute.h:438