28#define DEBUG_TYPE "must-execute"
41 ColorVector &ColorsForNewBlock = (*BlockColors)[New];
42 ColorVector &ColorsForOldBlock = (*BlockColors)[Old];
43 ColorsForNewBlock = ColorsForOldBlock;
55void SimpleLoopSafetyInfo::computeLoopSafetyInfo() {
60 MayThrow = HeaderMayThrow;
65 "First block must be header");
74 return ICF.hasICF(BB);
81void ICFLoopSafetyInfo::computeLoopSafetyInfo() {
96 ICF.insertInstructionTo(Inst, BB);
97 MW.insertInstructionTo(Inst, BB);
101 ICF.removeInstruction(Inst);
102 MW.removeInstruction(Inst);
105void LoopSafetyInfo::computeBlockColors()
const {
108 BlockColors.emplace();
124 const Loop *CurLoop) {
129 assert(CurLoop->
contains(CondExitBlock) &&
"meaning of exit block");
136 return BI->getSuccessor(
Cond->getZExtValue() ? 1 : 0) == ExitBlock;
145 auto *
RHS =
Cond->getOperand(1);
162 auto *IVStart =
LHS->getIncomingValueForBlock(Predecessor);
164 Pred, IVStart,
RHS, {
DL,
nullptr, DT,
nullptr, BI});
168 if (ExitBlock == BI->getSuccessor(0))
169 return SimpleCst->isNullValue();
170 assert(ExitBlock == BI->getSuccessor(1) &&
"implied by above");
171 return SimpleCst->isAllOnesValue();
183 assert(Predecessors.
empty() &&
"Garbage in predecessors set?");
184 assert(CurLoop->
contains(BB) &&
"Should only be called for loop blocks!");
194 while (!WorkList.
empty()) {
207 if (CurLoop->
contains(PredPred) && Predecessors.
insert(PredPred).second)
214 assert(
CurLoop->contains(BB) &&
"Should only be called for loop blocks!");
217 if (BB ==
CurLoop->getHeader())
220 auto [It, Inserted] = GuaranteedToExecute.try_emplace(BB,
false);
222 It->second = allLoopPathsLeadToBlockImpl(BB, DT);
226bool LoopSafetyInfo::allLoopPathsLeadToBlockImpl(
249 for (
const auto *Pred : Predecessors) {
260 if (CheckedSuccessors.
insert(Succ).second &&
261 Succ != BB && !Predecessors.count(Succ))
297 return !HeaderMayThrow ||
298 &*Inst.
getParent()->getFirstNonPHIOrPseudoProbe() == &Inst;
307 return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
312 assert(
CurLoop->contains(BB) &&
"Should only be called for loop blocks!");
315 if (BB ==
CurLoop->getHeader())
324 for (
const auto *Pred : Predecessors)
325 if (MW.mayWriteToMemory(Pred))
331 auto *BB =
I.getParent();
332 assert(
CurLoop->contains(BB) &&
"Should only be called for loop blocks!");
333 return !MW.isDominatedByMemoryWriteFromSameBlock(&
I) &&
350 DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
353 MustExecuteAnnotatedWriter(
const Function &
F,
354 DominatorTree &DT, LoopInfo &LI) {
359 MustExec[&
I].push_back(L);
361 L =
L->getParentLoop();
365 MustExecuteAnnotatedWriter(
const Module &M,
366 DominatorTree &DT, LoopInfo &LI) {
367 for (
const auto &
F : M)
372 MustExec[&
I].push_back(L);
374 L =
L->getParentLoop();
380 void printInfoComment(
const Value &
V, formatted_raw_ostream &OS)
override {
385 const auto NumLoops =
Loops.size();
387 OS <<
" ; (mustexec in " << NumLoops <<
" loops: ";
389 OS <<
" ; (mustexec in: ";
393 OS <<
LS <<
L->getHeader()->getName();
401 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
412 RPOTraversal FuncRPOT(&
F);
419template <
typename K,
typename V,
typename FnTy,
typename... ArgsTy>
421 FnTy &&Fn, ArgsTy &&...
args) {
422 std::optional<V> &OptVal = Map[
Key];
424 OptVal = Fn(std::forward<ArgsTy>(
args)...);
434 << (LI ?
" [LI]" :
"") << (PDT ?
" [PDT]" :
""));
438 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
439 bool WillReturnAndNoThrow = (
F.hasFnAttribute(Attribute::WillReturn) ||
443 << (WillReturnAndNoThrow ?
" [WillReturn] [NoUnwind]" :
"")
450 bool IsLatch = SuccBB == HeaderBB;
453 if (!WillReturnAndNoThrow || !IsLatch)
459 if (Worklist.
empty())
463 if (Worklist.
size() == 1)
471 if (
const auto *InitNode = PDT->
getNode(InitBB))
472 if (
const auto *IDomNode = InitNode->getIDom())
473 JoinBB = IDomNode->getBlock();
475 if (!JoinBB && Worklist.
size() == 2) {
480 if (Succ0UniqueSucc == InitBB) {
484 }
else if (Succ1UniqueSucc == InitBB) {
488 }
else if (Succ0 == Succ1UniqueSucc) {
492 }
else if (Succ1 == Succ0UniqueSucc) {
496 }
else if (Succ0UniqueSucc == Succ1UniqueSucc) {
499 JoinBB = Succ0UniqueSucc;
504 JoinBB = L->getUniqueExitBlock();
519 if (!
F.hasFnAttribute(Attribute::WillReturn) || !
F.doesNotThrow()) {
521 auto BlockTransfersExecutionToSuccessor = [](
const BasicBlock *BB) {
526 while (!Worklist.
empty()) {
532 if (!Visited.
insert(ToBB).second) {
533 if (!
F.hasFnAttribute(Attribute::WillReturn)) {
539 if (MayContainIrreducibleControl)
553 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
554 if (!TransfersExecution)
569 << (LI ?
" [LI]" :
"") << (DT ?
" [DT]" :
""));
575 if (
const auto *InitNode = DT->
getNode(InitBB))
576 if (
const auto *IDomNode = InitNode->getIDom())
577 return IDomNode->getBlock();
580 const BasicBlock *HeaderBB = L ? L->getHeader() :
nullptr;
586 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
594 if (Worklist.
empty())
598 if (Worklist.
size() == 1)
602 if (Worklist.
size() == 2) {
607 if (Pred0 == Pred1UniquePred) {
611 }
else if (Pred1 == Pred0UniquePred) {
615 }
else if (Pred0UniquePred == Pred1UniquePred) {
618 JoinBB = Pred0UniquePred;
623 JoinBB = L->getHeader();
636 LLVM_DEBUG(
dbgs() <<
"Find next instruction for " << *PP <<
"\n");
640 LLVM_DEBUG(
dbgs() <<
"\tReached terminator in intra-block mode, done\n");
648 if (!TransfersExecution)
657 LLVM_DEBUG(
dbgs() <<
"\tIntermediate instruction does transfer control\n");
674 dbgs() <<
"\tUnconditional terminator, continue with successor\n");
682 return &JoinBB->front();
696 << (IsFirst ?
" [IsFirst]" :
"") <<
"\n");
701 LLVM_DEBUG(
dbgs() <<
"\tReached block front in intra-block mode, done\n");
713 dbgs() <<
"\tIntermediate instruction, continue with previous\n");
723 return &JoinBB->back();
730MustBeExecutedContextExplorer::getForwardStop(
const Instruction *PP) {
732 auto [It, Inserted] = NonTransferringMap.try_emplace(BB);
736 It->second.push_back(&
I);
741 [](
const Instruction *
A,
const Instruction *
B) {
742 return A->comesBefore(
B);
744 return Stop == NonTransferring.
end() ? nullptr : *Stop;
748MustBeExecutedContextExplorer::getForwardNextBlock(
const BasicBlock *BB) {
749 auto [It,
Inserted] = ForwardNextBlockMap.try_emplace(BB);
752 if (
Term->getNumSuccessors() == 1)
753 It->second =
Term->getSuccessor(0);
754 else if (
Term->getNumSuccessors() > 1)
761MustBeExecutedContextExplorer::getBackwardNextBlock(
const BasicBlock *BB) {
762 auto [It,
Inserted] = BackwardNextBlockMap.try_emplace(BB);
768const MustBeExecutedContextExplorer::ForwardContextTy &
769MustBeExecutedContextExplorer::getForwardContext(
const BasicBlock *BB) {
770 auto &
Context = ForwardContextMap[BB];
772 Context = std::make_unique<ForwardContextTy>();
773 for (
const BasicBlock *CurBB = getForwardNextBlock(BB); CurBB;) {
774 const Instruction *Stop = getForwardStop(&CurBB->front());
775 if (!
Context->try_emplace(CurBB, Stop).second)
777 CurBB = Stop ? nullptr : getForwardNextBlock(CurBB);
783const MustBeExecutedContextExplorer::BackwardContextTy &
784MustBeExecutedContextExplorer::getBackwardContext(
const BasicBlock *BB) {
785 auto &
Context = BackwardContextMap[BB];
787 Context = std::make_unique<BackwardContextTy>();
788 for (
const BasicBlock *CurBB = getBackwardNextBlock(BB);
789 CurBB &&
Context->insert(CurBB);)
790 CurBB = getBackwardNextBlock(CurBB);
812 const ForwardContextTy &Context = getForwardContext(PPBB);
813 auto It = Context.find(IBB);
814 if (It != Context.end() && (!It->second || !It->second->comesBefore(
I)))
822 if (IBB == PPBB &&
I->comesBefore(PP))
836 if (!Visited.
insert(BB).second)
842 if (!CheckBlock(PPBB))
847 for (
const auto &[BB, Stop] : getForwardContext(PPBB)) {
853 for (
const BasicBlock *BB : getBackwardContext(PPBB)) {
863 : Explorer(Explorer), CurInst(
I), Head(nullptr), Tail(nullptr) {
869void MustBeExecutedIterator::reset(
const Instruction *
I) {
874void MustBeExecutedIterator::resetInstruction(
const Instruction *
I) {
876 Head = Tail =
nullptr;
879 if (Explorer.ExploreCFGForward)
881 if (Explorer.ExploreCFGBackward)
885const Instruction *MustBeExecutedIterator::advance() {
886 assert(CurInst &&
"Cannot advance an end iterator!");
887 Head = Explorer.getMustBeExecutedNextInstruction(*
this, Head);
888 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
892 Tail = Explorer.getMustBeExecutedPrevInstruction(*
this, Tail);
893 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
904 MustExecuteAnnotatedWriter Writer(
F, DT, LI);
905 F.print(OS, &Writer);
913 GetterTy<const LoopInfo> LIGetter = [&](
const Function &
F) {
916 GetterTy<const DominatorTree> DTGetter = [&](
const Function &
F) {
919 GetterTy<const PostDominatorTree> PDTGetter = [&](
const Function &
F) {
926 true, LIGetter, DTGetter, PDTGetter);
930 OS <<
"-- Explore context of: " <<
I <<
"\n";
932 OS <<
" [F: " << CI->getFunction()->getName() <<
"] " << *CI <<
"\n";
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
Machine Check Debug Module
static void collectTransitivePredecessors(const Loop *CurLoop, const BasicBlock *BB, SmallPtrSetImpl< const BasicBlock * > &Predecessors)
Collect all blocks from CurLoop which lie on all possible paths from the header of CurLoop (inclusive...
static bool maybeEndlessLoop(const Loop &L)
Return true if L might be an endless loop.
static V getOrCreateCachedOptional(K Key, DenseMap< K, std::optional< V > > &Map, FnTy &&Fn, ArgsTy &&...args)
Lookup Key in Map and return the result, potentially after initializing the optional through Fn(args)...
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop)
Return true if we can prove that the given ExitBlock is not reached on the first iteration of the giv...
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
FunctionAnalysisManager FAM
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
SmallVector< MachineOperand, 4 > Cond
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
This file defines the SmallPtrSet class.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is an important base class in LLVM.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
bool hasPersonalityFn() const
Check whether this function has a personality function.
Constant * getPersonalityFn() const
Get the personality function associated with this function.
bool doesNotWriteMemoryBefore(const BasicBlock *BB) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
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 hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
LLVM_ABI void clear()
Invalidates all information from this tracking.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool isTerminator() const
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
LLVM_ABI void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
LLVM_ABI const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
LLVM_ABI bool allLoopPathsLeadToBlock(const BasicBlock *BB, const DominatorTree *DT) const
Return true if we must reach the block BB under assumption that the loop is entered.
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
LLVM_ABI bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
auto dyn_cast_or_null(const Y &Val)
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
TinyPtrVector< BasicBlock * > ColorVector
auto predecessors(const MachineBasicBlock *BB)
LLVM_ABI Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
A "must be executed context" for a given program point PP is the set of instructions,...
const bool ExploreInterBlock
Parameter that limit the performed exploration.
LLVM_ABI const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
LLVM_ABI const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
const bool ExploreCFGBackward
const bool ExploreCFGForward
LLVM_ABI bool checkForAllTerminatorsInContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)
Check Pred on all terminators in the context of PP and return true if it holds for all of them.
llvm::iterator_range< iterator > range(const Instruction *PP)
}
LLVM_ABI bool isInContextOf(const Instruction *I, const Instruction *PP)
}
LLVM_ABI const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
LLVM_ABI const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default