LLVM  14.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"
32 
33 namespace llvm {
34 
35 namespace {
36 template <typename T> using GetterTy = std::function<T *(const Function &F)>;
37 }
38 
39 class BasicBlock;
40 class DominatorTree;
41 class Instruction;
42 class Loop;
43 class LoopInfo;
44 class PostDominatorTree;
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 
285  : Visited(Other.Visited), Explorer(Other.Explorer),
286  CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
287 
289  : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
290  CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
291 
293  if (this != &Other) {
294  std::swap(Visited, Other.Visited);
295  std::swap(CurInst, Other.CurInst);
296  std::swap(Head, Other.Head);
297  std::swap(Tail, Other.Tail);
298  }
299  return *this;
300  }
301 
303 
304  /// Pre- and post-increment operators.
305  ///{
307  CurInst = advance();
308  return *this;
309  }
310 
313  operator++();
314  return tmp;
315  }
316  ///}
317 
318  /// Equality and inequality operators. Note that we ignore the history here.
319  ///{
320  bool operator==(const MustBeExecutedIterator &Other) const {
321  return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;
322  }
323 
324  bool operator!=(const MustBeExecutedIterator &Other) const {
325  return !(*this == Other);
326  }
327  ///}
328 
329  /// Return the underlying instruction.
330  const Instruction *&operator*() { return CurInst; }
331  const Instruction *getCurrentInst() const { return CurInst; }
332 
333  /// Return true if \p I was encountered by this iterator already.
334  bool count(const Instruction *I) const {
335  return Visited.count({I, ExplorationDirection::FORWARD}) ||
336  Visited.count({I, ExplorationDirection::BACKWARD});
337  }
338 
339 private:
340  using VisitedSetTy =
342 
343  /// Private constructors.
344  MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
345 
346  /// Reset the iterator to its initial state pointing at \p I.
347  void reset(const Instruction *I);
348 
349  /// Reset the iterator to point at \p I, keep cached state.
350  void resetInstruction(const Instruction *I);
351 
352  /// Try to advance one of the underlying positions (Head or Tail).
353  ///
354  /// \return The next instruction in the must be executed context, or nullptr
355  /// if none was found.
356  const Instruction *advance();
357 
358  /// A set to track the visited instructions in order to deal with endless
359  /// loops and recursion.
360  VisitedSetTy Visited;
361 
362  /// A reference to the explorer that created this iterator.
363  ExplorerTy &Explorer;
364 
365  /// The instruction we are currently exposing to the user. There is always an
366  /// instruction that we know is executed with the given program point,
367  /// initially the program point itself.
368  const Instruction *CurInst;
369 
370  /// Two positions that mark the program points where this iterator will look
371  /// for the next instruction. Note that the current instruction is either the
372  /// one pointed to by Head, Tail, or both.
373  const Instruction *Head, *Tail;
374 
376 };
377 
378 /// A "must be executed context" for a given program point PP is the set of
379 /// instructions, potentially before and after PP, that are executed always when
380 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
381 /// "must be executed contexts" in a module through the use of
382 /// MustBeExecutedIterator.
383 ///
384 /// The explorer exposes "must be executed iterators" that traverse the must be
385 /// executed context. There is little information sharing between iterators as
386 /// the expected use case involves few iterators for "far apart" instructions.
387 /// If that changes, we should consider caching more intermediate results.
389 
390  /// In the description of the parameters we use PP to denote a program point
391  /// for which the must be executed context is explored, or put differently,
392  /// for which the MustBeExecutedIterator is created.
393  ///
394  /// \param ExploreInterBlock Flag to indicate if instructions in blocks
395  /// other than the parent of PP should be
396  /// explored.
397  /// \param ExploreCFGForward Flag to indicate if instructions located after
398  /// PP in the CFG, e.g., post-dominating PP,
399  /// should be explored.
400  /// \param ExploreCFGBackward Flag to indicate if instructions located
401  /// before PP in the CFG, e.g., dominating PP,
402  /// should be explored.
405  GetterTy<const LoopInfo> LIGetter =
406  [](const Function &) { return nullptr; },
407  GetterTy<const DominatorTree> DTGetter =
408  [](const Function &) { return nullptr; },
409  GetterTy<const PostDominatorTree> PDTGetter =
410  [](const Function &) { return nullptr; })
413  ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter),
414  DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
415 
416  /// Iterator-based interface. \see MustBeExecutedIterator.
417  ///{
420 
421  /// Return an iterator to explore the context around \p PP.
422  iterator &begin(const Instruction *PP) {
423  auto &It = InstructionIteratorMap[PP];
424  if (!It)
425  It.reset(new iterator(*this, PP));
426  return *It;
427  }
428 
429  /// Return an iterator to explore the cached context around \p PP.
430  const_iterator &begin(const Instruction *PP) const {
431  return *InstructionIteratorMap.find(PP)->second;
432  }
433 
434  /// Return an universal end iterator.
435  ///{
436  iterator &end() { return EndIterator; }
437  iterator &end(const Instruction *) { return EndIterator; }
438 
439  const_iterator &end() const { return EndIterator; }
440  const_iterator &end(const Instruction *) const { return EndIterator; }
441  ///}
442 
443  /// Return an iterator range to explore the context around \p PP.
445  return llvm::make_range(begin(PP), end(PP));
446  }
447 
448  /// Return an iterator range to explore the cached context around \p PP.
450  return llvm::make_range(begin(PP), end(PP));
451  }
452  ///}
453 
454  /// Check \p Pred on all instructions in the context.
455  ///
456  /// This method will evaluate \p Pred and return
457  /// true if \p Pred holds in every instruction.
459  function_ref<bool(const Instruction *)> Pred) {
460  for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; ++EIt)
461  if (!Pred(*EIt))
462  return false;
463  return true;
464  }
465 
466  /// Helper to look for \p I in the context of \p PP.
467  ///
468  /// The context is expanded until \p I was found or no more expansion is
469  /// possible.
470  ///
471  /// \returns True, iff \p I was found.
472  bool findInContextOf(const Instruction *I, const Instruction *PP) {
473  auto EIt = begin(PP), EEnd = end(PP);
474  return findInContextOf(I, EIt, EEnd);
475  }
476 
477  /// Helper to look for \p I in the context defined by \p EIt and \p EEnd.
478  ///
479  /// The context is expanded until \p I was found or no more expansion is
480  /// possible.
481  ///
482  /// \returns True, iff \p I was found.
483  bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd) {
484  bool Found = EIt.count(I);
485  while (!Found && EIt != EEnd)
486  Found = (++EIt).getCurrentInst() == I;
487  return Found;
488  }
489 
490  /// Return the next instruction that is guaranteed to be executed after \p PP.
491  ///
492  /// \param It The iterator that is used to traverse the must be
493  /// executed context.
494  /// \param PP The program point for which the next instruction
495  /// that is guaranteed to execute is determined.
496  const Instruction *
498  const Instruction *PP);
499  /// Return the previous instr. that is guaranteed to be executed before \p PP.
500  ///
501  /// \param It The iterator that is used to traverse the must be
502  /// executed context.
503  /// \param PP The program point for which the previous instr.
504  /// that is guaranteed to execute is determined.
505  const Instruction *
507  const Instruction *PP);
508 
509  /// Find the next join point from \p InitBB in forward direction.
510  const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB);
511 
512  /// Find the next join point from \p InitBB in backward direction.
513  const BasicBlock *findBackwardJoinPoint(const BasicBlock *InitBB);
514 
515  /// Parameter that limit the performed exploration. See the constructor for
516  /// their meaning.
517  ///{
518  const bool ExploreInterBlock;
519  const bool ExploreCFGForward;
520  const bool ExploreCFGBackward;
521  ///}
522 
523 private:
524  /// Getters for common CFG analyses: LoopInfo, DominatorTree, and
525  /// PostDominatorTree.
526  ///{
527  GetterTy<const LoopInfo> LIGetter;
528  GetterTy<const DominatorTree> DTGetter;
529  GetterTy<const PostDominatorTree> PDTGetter;
530  ///}
531 
532  /// Map to cache isGuaranteedToTransferExecutionToSuccessor results.
534 
535  /// Map to cache containsIrreducibleCFG results.
536  DenseMap<const Function*, Optional<bool>> IrreducibleControlMap;
537 
538  /// Map from instructions to associated must be executed iterators.
540  InstructionIteratorMap;
541 
542  /// A unique end iterator.
543  MustBeExecutedIterator EndIterator;
544 };
545 
546 class MustExecutePrinterPass : public PassInfoMixin<MustExecutePrinterPass> {
547  raw_ostream &OS;
548 
549 public:
552 };
553 
555  : public PassInfoMixin<MustBeExecutedContextPrinterPass> {
556  raw_ostream &OS;
557 
558 public:
561 };
562 
563 } // namespace llvm
564 
565 #endif
llvm::LoopSafetyInfo::computeBlockColors
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
Definition: MustExecute.cpp:106
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::MustBeExecutedIterator::operator*
const Instruction *& operator*()
}
Definition: MustExecute.h:330
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:706
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: AllocatorList.h:23
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:192
llvm::MustBeExecutedContextExplorer::range
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:444
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:73
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::MustBeExecutedIterator::~MustBeExecutedIterator
~MustBeExecutedIterator()
Definition: MustExecute.h:302
llvm::MustBeExecutedContextExplorer::ExploreInterBlock
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:518
llvm::MustExecutePrinterPass::MustExecutePrinterPass
MustExecutePrinterPass(raw_ostream &OS)
Definition: MustExecute.h:550
llvm::MustBeExecutedContextPrinterPass::MustBeExecutedContextPrinterPass
MustBeExecutedContextPrinterPass(raw_ostream &OS)
Definition: MustExecute.h:559
llvm::MustBeExecutedIterator::count
bool count(const Instruction *I) const
Return true if I was encountered by this iterator already.
Definition: MustExecute.h:334
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:151
DenseMap.h
EHPersonalities.h
llvm::MustBeExecutedIterator::pointer
const typedef Instruction ** pointer
Definition: MustExecute.h:277
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(const MustBeExecutedIterator &Other)
Definition: MustExecute.h:284
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:375
llvm::MustBeExecutedContextExplorer::ExploreCFGForward
const bool ExploreCFGForward
Definition: MustExecute.h:519
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:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:554
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:288
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:35
llvm::MustExecutePrinterPass
Definition: MustExecute.h:546
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:439
llvm::Instruction
Definition: Instruction.h:45
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:53
llvm::MustBeExecutedIterator::getCurrentInst
const Instruction * getCurrentInst() const
Definition: MustExecute.h:331
llvm::MemoryWriteTracking
Definition: InstructionPrecedenceTracking.h:121
llvm::MustBeExecutedContextExplorer::findInContextOf
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
Definition: MustExecute.h:472
llvm::MustBeExecutedContextExplorer::checkForAllContext
bool checkForAllContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
}
Definition: MustExecute.h:458
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
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:850
llvm::MustBeExecutedContextExplorer::iterator
MustBeExecutedIterator iterator
Iterator-based interface.
Definition: MustExecute.h:418
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:403
llvm::MustExecutePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MustExecute.cpp:839
llvm::MustBeExecutedContextExplorer::ExploreCFGBackward
const bool ExploreCFGBackward
Definition: MustExecute.h:520
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:77
llvm::MustBeExecutedContextExplorer::end
iterator & end(const Instruction *)
Definition: MustExecute.h:437
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:422
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:277
llvm::MustBeExecutedIterator::operator==
bool operator==(const MustBeExecutedIterator &Other) const
}
Definition: MustExecute.h:320
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:1658
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
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:54
llvm::MustBeExecutedContextExplorer
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:388
llvm::MustBeExecutedContextExplorer::end
iterator & end()
Return an universal end iterator.
Definition: MustExecute.h:436
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:483
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:95
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:50
llvm::MustBeExecutedIterator::operator=
MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:292
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:101
std
Definition: BitVector.h:838
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:39
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:763
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:449
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:81
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:45
llvm::MustBeExecutedIterator::operator++
MustBeExecutedIterator operator++(int)
Definition: MustExecute.h:311
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:270
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:251
llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
Definition: MustExecute.cpp:639
llvm::LoopSafetyInfo::~LoopSafetyInfo
virtual ~LoopSafetyInfo()=default
llvm::MustBeExecutedIterator::operator!=
bool operator!=(const MustBeExecutedIterator &Other) const
Definition: MustExecute.h:324
raw_ostream.h
llvm::MustBeExecutedContextExplorer::findForwardJoinPoint
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
Definition: MustExecute.cpp:503
llvm::MustBeExecutedContextExplorer::begin
const_iterator & begin(const Instruction *PP) const
Return an iterator to explore the cached context around PP.
Definition: MustExecute.h:430
llvm::mayContainIrreducibleControl
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
Definition: MustExecute.cpp:482
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:306
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1195
llvm::MustBeExecutedContextExplorer::end
const_iterator & end(const Instruction *) const
Definition: MustExecute.h:440