Go to the documentation of this file.
29 #define DEBUG_TYPE "must-execute"
39 ColorsForNewBlock = ColorsForOldBlock;
52 assert(CurLoop !=
nullptr &&
"CurLoop can't be null");
56 MayThrow = HeaderMayThrow;
61 "First block must be header");
80 assert(CurLoop !=
nullptr &&
"CurLoop can't be null");
85 for (
const auto &
BB : CurLoop->
blocks())
119 const Loop *CurLoop) {
124 assert(CurLoop->
contains(CondExitBlock) &&
"meaning of exit block");
125 auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
126 if (!BI || !BI->isConditional())
130 if (
auto *
Cond = dyn_cast<ConstantInt>(BI->getCondition()))
131 return BI->getSuccessor(
Cond->getZExtValue() ? 1 : 0) == ExitBlock;
132 auto *
Cond = dyn_cast<CmpInst>(BI->getCondition());
138 auto *
LHS = dyn_cast<PHINode>(
Cond->getOperand(0));
139 auto *
RHS =
Cond->getOperand(1);
148 auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
151 if (ExitBlock == BI->getSuccessor(0))
152 return SimpleCst->isZeroValue();
153 assert(ExitBlock == BI->getSuccessor(1) &&
"implied by above");
154 return SimpleCst->isAllOnesValue();
163 assert(Predecessors.
empty() &&
"Garbage in predecessors set?");
169 Predecessors.
insert(Pred);
170 WorkList.push_back(Pred);
172 while (!WorkList.empty()) {
174 assert(CurLoop->
contains(Pred) &&
"Should only reach loop blocks!");
185 if (Predecessors.
insert(PredPred).second)
186 WorkList.push_back(PredPred);
220 for (
const auto *Pred : Predecessors) {
231 if (CheckedSuccessors.
insert(Succ).second &&
232 Succ !=
BB && !Predecessors.count(Succ))
260 const Loop *CurLoop)
const {
269 return !HeaderMayThrow ||
279 const Loop *CurLoop)
const {
285 const Loop *CurLoop)
const {
298 for (
const auto *Pred : Predecessors)
305 const Loop *CurLoop)
const {
306 auto *
BB =
I.getParent();
326 struct MustBeExecutedContextPrinter :
public ModulePass {
336 bool runOnModule(
Module &M)
override;
342 "Instructions which execute on loop entry",
false,
true)
349 return new MustExecutePrinter();
354 "print-must-be-executed-contexts",
355 "print the must-be-executed-context for all instructions",
366 return new MustBeExecutedContextPrinter();
369 bool MustBeExecutedContextPrinter::runOnModule(
Module &M) {
376 GetterTy<LoopInfo> LIGetter = [&](
const Function &
F) {
377 DTs.push_back(std::make_unique<DominatorTree>(
const_cast<Function &
>(
F)));
378 LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
379 return LIs.back().get();
381 GetterTy<DominatorTree> DTGetter = [&](
const Function &
F) {
382 DTs.push_back(std::make_unique<DominatorTree>(
const_cast<Function&
>(
F)));
383 return DTs.back().get();
385 GetterTy<PostDominatorTree> PDTGetter = [&](
const Function &
F) {
387 std::make_unique<PostDominatorTree>(
const_cast<Function &
>(
F)));
388 return PDTs.back().get();
393 true, LIGetter, DTGetter, PDTGetter);
397 dbgs() <<
"-- Explore context of: " <<
I <<
"\n";
399 dbgs() <<
" [F: " << CI->getFunction()->getName() <<
"] " << *CI
424 MustExecuteAnnotatedWriter(
const Function &
F,
430 MustExec[&
I].push_back(L);
436 MustExecuteAnnotatedWriter(
const Module &M,
438 for (
const auto &
F : M)
443 MustExec[&
I].push_back(L);
452 if (!MustExec.
count(&V))
456 const auto NumLoops =
Loops.size();
458 OS <<
" ; (mustexec in " << NumLoops <<
" loops: ";
460 OS <<
" ; (mustexec in: ";
471 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
472 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
474 MustExecuteAnnotatedWriter Writer(
F, DT, LI);
475 F.print(
dbgs(), &Writer);
493 RPOTraversal FuncRPOT(&
F);
500 template <
typename K,
typename V,
typename FnTy,
typename... ArgsTy>
502 FnTy &&Fn, ArgsTy &&...
args) {
503 std::optional<V> &OptVal = Map[
Key];
505 OptVal = Fn(std::forward<ArgsTy>(
args)...);
515 << (LI ?
" [LI]" :
"") << (PDT ?
" [PDT]" :
""));
520 bool WillReturnAndNoThrow = (
F.hasFnAttribute(Attribute::WillReturn) ||
524 << (WillReturnAndNoThrow ?
" [WillReturn] [NoUnwind]" :
"")
531 bool IsLatch = SuccBB == HeaderBB;
534 if (!WillReturnAndNoThrow || !IsLatch)
535 Worklist.push_back(SuccBB);
537 LLVM_DEBUG(
dbgs() <<
"\t\t#Worklist: " << Worklist.size() <<
"\n");
540 if (Worklist.empty())
544 if (Worklist.size() == 1)
552 if (
const auto *InitNode = PDT->
getNode(InitBB))
553 if (
const auto *IDomNode = InitNode->getIDom())
554 JoinBB = IDomNode->getBlock();
556 if (!JoinBB && Worklist.size() == 2) {
561 if (Succ0UniqueSucc == InitBB) {
565 }
else if (Succ1UniqueSucc == InitBB) {
569 }
else if (Succ0 == Succ1UniqueSucc) {
573 }
else if (Succ1 == Succ0UniqueSucc) {
577 }
else if (Succ0UniqueSucc == Succ1UniqueSucc) {
580 JoinBB = Succ0UniqueSucc;
600 if (!
F.hasFnAttribute(Attribute::WillReturn) || !
F.doesNotThrow()) {
602 auto BlockTransfersExecutionToSuccessor = [](
const BasicBlock *
BB) {
607 while (!Worklist.empty()) {
613 if (!Visited.
insert(ToBB).second) {
614 if (!
F.hasFnAttribute(Attribute::WillReturn)) {
620 if (MayContainIrreducibleControl)
634 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
635 if (!TransfersExecution)
650 << (LI ?
" [LI]" :
"") << (DT ?
" [DT]" :
""));
656 if (
const auto *InitNode = DT->
getNode(InitBB))
657 if (
const auto *IDomNode = InitNode->getIDom())
658 return IDomNode->getBlock();
667 (PredBB == InitBB) || (HeaderBB == InitBB && L->
contains(PredBB));
671 Worklist.push_back(PredBB);
675 if (Worklist.empty())
679 if (Worklist.size() == 1)
683 if (Worklist.size() == 2) {
688 if (Pred0 == Pred1UniquePred) {
692 }
else if (Pred1 == Pred0UniquePred) {
696 }
else if (Pred0UniquePred == Pred1UniquePred) {
699 JoinBB = Pred0UniquePred;
717 LLVM_DEBUG(
dbgs() <<
"Find next instruction for " << *PP <<
"\n");
721 LLVM_DEBUG(
dbgs() <<
"\tReached terminator in intra-block mode, done\n");
729 if (!TransfersExecution)
738 LLVM_DEBUG(
dbgs() <<
"\tIntermediate instruction does transfer control\n");
755 dbgs() <<
"\tUnconditional terminator, continue with successor\n");
763 return &JoinBB->front();
777 << (IsFirst ?
" [IsFirst]" :
"") <<
"\n");
782 LLVM_DEBUG(
dbgs() <<
"\tReached block front in intra-block mode, done\n");
794 dbgs() <<
"\tIntermediate instruction, continue with previous\n");
804 return &JoinBB->back();
812 : Explorer(Explorer), CurInst(
I) {
816 void MustBeExecutedIterator::reset(
const Instruction *
I) {
821 void MustBeExecutedIterator::resetInstruction(
const Instruction *
I) {
823 Head = Tail =
nullptr;
832 const Instruction *MustBeExecutedIterator::advance() {
833 assert(CurInst &&
"Cannot advance an end iterator!");
835 if (Head && Visited.
insert({Head, ExplorationDirection ::FORWARD}).second)
840 if (Tail && Visited.
insert({Tail, ExplorationDirection ::BACKWARD}).second)
851 MustExecuteAnnotatedWriter Writer(
F, DT, LI);
852 F.print(OS, &Writer);
860 GetterTy<const LoopInfo> LIGetter = [&](
const Function &
F) {
863 GetterTy<const DominatorTree> DTGetter = [&](
const Function &
F) {
866 GetterTy<const PostDominatorTree> PDTGetter = [&](
const Function &
F) {
873 true, LIGetter, DTGetter, PDTGetter);
877 OS <<
"-- Explore context of: " <<
I <<
"\n";
879 OS <<
" [F: " << CI->getFunction()->getName() <<
"] " << *CI <<
"\n";
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
A set of analyses that are preserved following a run of a transformation pass.
FunctionPass * createMustExecutePrinter()
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
bool isTerminator() const
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
ModulePass * createMustBeExecutedContextPrinter()
This is an optimization pass for GlobalISel generic memory operations.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
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.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
llvm::iterator_range< iterator > range(const Instruction *PP)
}
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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)...
void initializeMustExecutePrinterPass(PassRegistry &)
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Represents a single loop in the control flow graph.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
const bool ExploreInterBlock
Parameter that limit the performed exploration.
auto successors(const MachineBasicBlock *BB)
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
The legacy pass manager's analysis pass to compute loop information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const bool ExploreCFGForward
std::pair< iterator, bool > insert(const ValueT &V)
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Represent the analysis usage information of a pass.
iterator_range< block_iterator > blocks() const
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can be
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Legacy analysis pass which computes a DominatorTree.
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
bool hasPersonalityFn() const
Check whether this function has a personality function.
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", "Instructions which execute on loop entry", false, true) INITIALIZE_PASS_END(MustExecutePrinter
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
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...
auto predecessors(const MachineBasicBlock *BB)
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
inst_range instructions(Function *F)
This is an important base class in LLVM.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
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 ...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
const bool ExploreCFGBackward
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Predicate all(Predicate P0, Predicate P1)
True iff P0 and P1 are true.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
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)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
void initializeMustBeExecutedContextPrinterPass(PassRegistry &)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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,...
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
print must be executed contexts
SmallVector< MachineOperand, 4 > Cond
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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 isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
StringRef getName() const
Return a constant reference to the value's name.
this could be done in SelectionDAGISel along with other special for
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
void clear()
Invalidates all information from this tracking.
const Instruction & front() const
static bool runOnFunction(Function &F, bool PostInlining)
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
void setPreservesAll()
Set by analyses that do not transform their input at all.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
BlockT * getHeader() const
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
static bool maybeEndlessLoop(const Loop &L)
Return true if L might be an endless loop.
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Analysis pass which computes a DominatorTree.
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
const BasicBlock * getParent() const
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
A container for analyses that lazily runs them and caches their results.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
FunctionPass class - This class is used to implement most global optimizations.
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...
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...
Analysis pass which computes a PostDominatorTree.
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.
AnalysisUsage & addRequired()
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
bool contains(ConstPtrType Ptr) const
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
LLVM Value Representation.
print Instructions which execute on loop entry
Analysis pass that exposes the LoopInfo for a function.
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.