LLVM 19.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
32namespace llvm {
33
34namespace {
35template <typename T> using GetterTy = std::function<T *(const Function &F)>;
36}
37
38class BasicBlock;
39class DominatorTree;
40class Instruction;
41class Loop;
42class LoopInfo;
43class PostDominatorTree;
44class 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
64protected:
65 /// Computes block colors.
66 void computeBlockColors(const Loop *CurLoop);
67
68public:
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
115public:
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
140public:
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
172bool 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
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
301
302 /// Pre- and post-increment operators.
303 ///{
305 CurInst = advance();
306 return *this;
307 }
308
310 MustBeExecutedIterator tmp(*this);
311 operator++();
312 return tmp;
313 }
314 ///}
315
316 /// Equality and inequality operators. Note that we ignore the history here.
317 ///{
319 return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;
320 }
321
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
337private:
338 using VisitedSetTy =
340
341 /// Private constructors.
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.
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 ///{
519 ///}
520
521private:
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.
535
536 /// Map from instructions to associated must be executed iterators.
538 InstructionIteratorMap;
539
540 /// A unique end iterator.
541 MustBeExecutedIterator EndIterator;
542};
543
544class MustExecutePrinterPass : public PassInfoMixin<MustExecutePrinterPass> {
545 raw_ostream &OS;
546
547public:
550 static bool isRequired() { return true; }
551};
552
554 : public PassInfoMixin<MustBeExecutedContextPrinterPass> {
555 raw_ostream &OS;
556
557public:
560 static bool isRequired() { return true; }
561};
562
563} // namespace llvm
564
565#endif
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
raw_pwrite_stream & OS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:132
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:71
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...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:99
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...
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
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
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
This class allows to keep track on instructions with implicit control flow.
Captures loop safety information.
Definition: MustExecute.h:60
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.
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:36
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:32
virtual ~LoopSafetyInfo()=default
virtual void computeLoopSafetyInfo(const Loop *CurLoop)=0
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
LoopSafetyInfo()=default
virtual bool anyBlockMayThrow() const =0
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
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...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
MustBeExecutedContextPrinterPass(raw_ostream &OS)
Definition: MustExecute.h:558
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
MustExecutePrinterPass(raw_ostream &OS)
Definition: MustExecute.h:548
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:110
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.
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
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
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:42
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
An efficient, type-erasing, non-owning reference to a callable.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
@ Other
Any other memory.
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:1858
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
ExplorationDirection
Enum that allows us to spell out the direction.
Definition: MustExecute.h:177
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:386
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:516
const_iterator & begin(const Instruction *PP) const
Return an iterator to explore the cached context around PP.
Definition: MustExecute.h:428
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
iterator & end()
Return an universal end iterator.
Definition: MustExecute.h:434
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
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
Definition: MustExecute.h:470
const_iterator & end() const
Definition: MustExecute.h:437
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
Definition: MustExecute.h:420
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:442
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
bool checkForAllContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
}
Definition: MustExecute.h:456
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
const_iterator & end(const Instruction *) const
Definition: MustExecute.h:438
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
iterator & end(const Instruction *)
Definition: MustExecute.h:435
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
MustBeExecutedIterator iterator
Iterator-based interface.
Definition: MustExecute.h:416
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:272
bool operator!=(const MustBeExecutedIterator &Other) const
Definition: MustExecute.h:322
const Instruction * value_type
Type declarations that make his class an input iterator.
Definition: MustExecute.h:275
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
MustBeExecutedContextExplorer ExplorerTy
}
Definition: MustExecute.h:282
const Instruction *& reference
Definition: MustExecute.h:278
const Instruction ** pointer
Definition: MustExecute.h:277
const Instruction * getCurrentInst() const
Definition: MustExecute.h:329
bool operator==(const MustBeExecutedIterator &Other) const
}
Definition: MustExecute.h:318
std::input_iterator_tag iterator_category
Definition: MustExecute.h:279
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:286
std::ptrdiff_t difference_type
Definition: MustExecute.h:276
MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)
Definition: MustExecute.h:290
bool count(const Instruction *I) const
Return true if I was encountered by this iterator already.
Definition: MustExecute.h:332
MustBeExecutedIterator operator++(int)
Definition: MustExecute.h:309
friend struct MustBeExecutedContextExplorer
Definition: MustExecute.h:373
MustBeExecutedIterator & operator++()
Pre- and post-increment operators.
Definition: MustExecute.h:304
const Instruction *& operator*()
}
Definition: MustExecute.h:328
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91