Go to the documentation of this file.
23 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
24 #define LLVM_ANALYSIS_MUSTEXECUTE_H
43 class PostDominatorTree;
99 const Loop *CurLoop)
const = 0;
111 bool MayThrow =
false;
113 bool HeaderMayThrow =
false;
124 const Loop *CurLoop)
const override;
133 bool MayThrow =
false;
149 const Loop *CurLoop)
const override;
291 if (
this != &
Other) {
319 return CurInst ==
Other.CurInst && Head ==
Other.Head && Tail ==
Other.Tail;
323 return !(*
this ==
Other);
334 Visited.
count({I, ExplorationDirection::BACKWARD});
358 VisitedSetTy Visited;
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; })
412 DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*
this,
nullptr) {}
421 auto &It = InstructionIteratorMap[PP];
429 return *InstructionIteratorMap.find(PP)->second;
458 for (
auto EIt =
begin(PP), EEnd =
end(PP); EIt != EEnd; ++EIt)
471 auto EIt =
begin(PP), EEnd =
end(PP);
482 bool Found = EIt.
count(
I);
483 while (!Found && EIt != EEnd)
484 Found = (++EIt).getCurrentInst() ==
I;
525 GetterTy<const LoopInfo> LIGetter;
526 GetterTy<const DominatorTree> DTGetter;
527 GetterTy<const PostDominatorTree> PDTGetter;
538 InstructionIteratorMap;
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
A set of analyses that are preserved following a run of a transformation pass.
const Instruction *& operator*()
}
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
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...
This class allows to keep track on instructions with implicit control flow.
This is an optimization pass for GlobalISel generic memory operations.
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.
llvm::iterator_range< iterator > range(const Instruction *PP)
}
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Represents a single loop in the control flow graph.
const bool ExploreInterBlock
Parameter that limit the performed exploration.
MustExecutePrinterPass(raw_ostream &OS)
MustBeExecutedContextPrinterPass(raw_ostream &OS)
bool count(const Instruction *I) const
Return true if I was encountered by this iterator already.
std::ptrdiff_t difference_type
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
const typedef Instruction ** pointer
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
friend struct MustBeExecutedContextExplorer
const bool ExploreCFGForward
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
LLVM Basic Block Representation.
const typedef Instruction * value_type
Type declarations that make his class an input iterator.
MustBeExecutedIterator(MustBeExecutedIterator &&Other)
Captures loop safety information.
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
virtual void computeLoopSafetyInfo(const Loop *CurLoop)=0
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
const_iterator & end() const
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
const typedef Instruction *& reference
This class implements an extremely fast bulk output stream that can only output to a stream.
const Instruction * getCurrentInst() const
~MustBeExecutedIterator()=default
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
bool checkForAllContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
}
An efficient, type-erasing, non-owning reference to a callable.
Implements a dense probed hash-table based set.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
MustBeExecutedIterator iterator
Iterator-based interface.
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...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
const bool ExploreCFGBackward
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
iterator & end(const Instruction *)
ExplorationDirection
Enum that allows us to spell out the direction.
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
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...
bool operator==(const MustBeExecutedIterator &Other) const
}
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
@ BasicBlock
Various leaf nodes.
print Print MemDeps of function
A Module instance is used to store all the information related to an LLVM module.
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
A "must be executed context" for a given program point PP is the set of instructions,...
iterator & end()
Return an universal end iterator.
bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd)
Helper to look for I in the context defined by EIt and EEnd.
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
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.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
virtual bool anyBlockMayThrow() const =0
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
std::input_iterator_tag iterator_category
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
llvm::iterator_range< const_iterator > range(const Instruction *PP) const
Return an iterator range to explore the cached context around PP.
std::optional< std::vector< StOtherPiece > > Other
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
A range adaptor for a pair of iterators.
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
MustBeExecutedIterator operator++(int)
A container for analyses that lazily runs them and caches their results.
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
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 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.
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
virtual ~LoopSafetyInfo()=default
bool operator!=(const MustBeExecutedIterator &Other) const
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
const_iterator & begin(const Instruction *PP) const
Return an iterator to explore the cached context around PP.
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
MustBeExecutedContextExplorer ExplorerTy
}
MustBeExecutedIterator & operator++()
Pre- and post-increment operators.
const_iterator & end(const Instruction *) const