74#define DEBUG_TYPE "place-safepoints"
76STATISTIC(NumEntrySafepoints,
"Number of entry safepoints inserted");
77STATISTIC(NumBackedgeSafepoints,
"Number of backedge safepoints inserted");
80 "Number of loops without safepoints due to calls in loop");
82 "Number of loops without safepoints finite execution");
104class PlaceBackedgeSafepointsLegacyPass :
public FunctionPass {
110 std::vector<Instruction *> PollLocations;
114 bool CallSafepointsEnabled;
116 PlaceBackedgeSafepointsLegacyPass(
bool CallSafepoints =
false)
122 bool runOnLoop(Loop *);
124 void runOnLoopAndSubLoops(Loop *L) {
127 runOnLoopAndSubLoops(
I);
132 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
133 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
134 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
135 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
136 for (Loop *
I : *LI) {
137 runOnLoopAndSubLoops(
I);
142 void getAnalysisUsage(AnalysisUsage &AU)
const override {
153 ScalarEvolution *SE =
nullptr;
154 DominatorTree *DT =
nullptr;
155 LoopInfo *LI =
nullptr;
156 TargetLibraryInfo *TLI =
nullptr;
164char PlaceBackedgeSafepointsLegacyPass::ID = 0;
167 "place-backedge-safepoints-impl",
168 "Place Backedge Safepoints",
false,
false)
173 "place-backedge-safepoints-impl",
198bool PlaceBackedgeSafepointsLegacyPass::runOnLoop(
Loop *L) {
206 L->getLoopLatches(LoopLatches);
208 assert(L->contains(Pred));
215 LLVM_DEBUG(
dbgs() <<
"skipping safepoint placement in finite loop\n");
219 if (CallSafepointsEnabled &&
226 <<
"skipping safepoint placement due to unconditional call\n");
244 PollLocations.push_back(Term);
251 if (
F.isDeclaration() ||
F.empty()) {
283 std::vector<CallBase *> ParsePointNeeded;
294 auto *PBS =
new PlaceBackedgeSafepointsLegacyPass(CanAssumeCallSafepoints);
302 auto &PollLocations = PBS->PollLocations;
305 return a->
getParent()->getName() < b->getParent()->getName();
314 PollLocations.erase(
llvm::unique(PollLocations), PollLocations.end());
335 if (DT.
dominates(Succ, Term->getParent()))
337 assert(!Headers.
empty() &&
"poll location is not a loop latch?");
345 NumBackedgeSafepoints++;
350 NumBackedgeSafepoints++;
359 NumEntrySafepoints++;
368 std::vector<CallBase *> RuntimeCalls;
391 if (CI->isInlineAsm())
417 assert(DT.
dominates(Header, Pred) &&
"loop latch not dominated by header?");
433 if (Current == Header)
457 if (L->isLoopExiting(Pred)) {
471 std::vector<CallInst *> &Calls,
473 std::vector<BasicBlock *> &Worklist) {
476 BBI != BBE0 && BBI != BBE1; BBI++) {
482 "support for invokes in poll code needed");
486 if (BBI->isTerminator()) {
489 if (Seen.
insert(Succ).second) {
490 Worklist.push_back(Succ);
498 std::vector<CallInst *> &Calls,
501 std::vector<BasicBlock *> Worklist;
502 Seen.
insert(Start->getParent());
503 scanOneBB(Start, End, Calls, Seen, Worklist);
504 while (!Worklist.empty()) {
515 switch (
II->getIntrinsicID()) {
516 case Intrinsic::experimental_gc_statepoint:
517 case Intrinsic::experimental_patchpoint_void:
518 case Intrinsic::experimental_patchpoint:
549 if (!
I->isTerminator())
552 BasicBlock *nextBB =
I->getParent()->getUniqueSuccessor();
557 assert(HasNextInstruction(
I) &&
558 "first check if there is a next instruction!");
560 if (
I->isTerminator())
561 return &
I->getParent()->getUniqueSuccessor()->front();
562 return &*++
I->getIterator();
566 for (Cursor = &
F.getEntryBlock().front(); HasNextInstruction(Cursor);
567 Cursor = NextInstruction(Cursor)) {
583 assert((HasNextInstruction(Cursor) || Cursor->isTerminator()) &&
584 "either we stopped because of a call, or because of terminator");
601 const auto &FunctionGCName =
F.getGC();
602 const StringRef StatepointExampleName(
"statepoint-example");
604 return (StatepointExampleName == FunctionGCName) ||
605 (CoreCLRName == FunctionGCName);
621 std::vector<CallBase *> &ParsePointsNeeded ,
624 Module *M = InsertBefore->getModule();
625 assert(M &&
"must be part of a module");
632 assert(
F &&
"gc.safepoint_poll function is missing");
635 "gc.safepoint_poll declared with wrong type");
636 assert(!
F->empty() &&
"gc.safepoint_poll must be a non-empty function");
641 bool IsBegin =
false;
642 if (Before == OrigBB->
begin())
648 assert(After != OrigBB->
end() &&
"must have successor");
653 assert(InlineStatus &&
"inline must succeed");
659 std::vector<CallInst *> Calls;
669 "malformed poll function");
672 assert(!Calls.empty() &&
"slow path not found for safepoint poll");
678 assert(ParsePointsNeeded.empty());
679 for (
auto *CI : Calls) {
686 ParsePointsNeeded.push_back(CI);
688 assert(ParsePointsNeeded.size() <= Calls.size());
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool runOnFunction(Function &F, bool PostInlining)
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static void InsertSafepointPoll(BasicBlock::iterator InsertBefore, std::vector< CallBase * > &ParsePointsNeeded, const TargetLibraryInfo &TLI)
const char GCSafepointPollName[]
static cl::opt< bool > AllBackedges("spp-all-backedges", cl::Hidden, cl::init(false))
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, BasicBlock *Pred)
Returns true if this loop is known to terminate in a finite number of iterations.
static bool enableCallSafepoints(Function &F)
static bool enableEntrySafepoints(Function &F)
static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))
static bool isGCSafepointPoll(Function &F)
static bool shouldRewriteFunction(Function &F)
Returns true if this function should be rewritten to include safepoint polls and parseable call sites...
static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI)
static void scanInlinedCode(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen)
static Instruction * findLocationForEntrySafepoint(Function &F, DominatorTree &DT)
static cl::opt< bool > SplitBackedge("spp-split-backedge", cl::Hidden, cl::init(false))
place backedge safepoints Place Backedge static false bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header, BasicBlock *Pred, DominatorTree &DT, const TargetLibraryInfo &TLI)
Returns true if this loop is known to contain a call safepoint which must unconditionally execute on ...
static bool doesNotRequireEntrySafepointBefore(CallBase *Call)
Returns true if an entry safepoint is not required before this callsite in the caller function.
static cl::opt< bool > NoCall("spp-no-call", cl::Hidden, cl::init(false))
static cl::opt< bool > NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false))
static bool enableBackedgeSafepoints(Function &F)
static cl::opt< int > CountedLoopTripWidth("spp-counted-loop-trip-width", cl::Hidden, cl::init(32))
How narrow does the trip count of a loop have to be to have to be considered "counted"?
static void scanOneBB(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen, std::vector< BasicBlock * > &Worklist)
This file implements a set that has insertion order iteration characteristics.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Implements a dense probed hash-table based set.
DomTreeNodeBase * getIDom() const
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
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.
FunctionPass class - This class is used to implement most global optimizations.
static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
SmallVector< AllocaInst *, 4 > StaticAllocas
InlineFunction fills this in with all static allocas that get copied into the caller.
A wrapper class for inspecting calls to intrinsic functions.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, const TargetLibraryInfo &TLI)
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
A vector that has set insertion semantics.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
static LLVM_ABI Type * getVoidTy(LLVMContext &C)
std::pair< iterator, bool > insert(const ValueT &V)
const ParentTy * getParent() const
FunctionPassManager manages FunctionPasses.
bool run(Function &F)
run - Execute all of the passes scheduled for execution.
void add(Pass *P) override
Add a pass to the queue of passes to run.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, bool MergeAttributes=false, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
This function inlines the called function into the basic block of the caller.
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 void initializePlaceBackedgeSafepointsLegacyPassPass(PassRegistry &)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
auto unique(Range &&R, Predicate P)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
LLVM_ABI bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
LLVM_ABI bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Implement std::hash so that hash_code can be used in STL containers.