73#define DEBUG_TYPE "place-safepoints"
75STATISTIC(NumEntrySafepoints,
"Number of entry safepoints inserted");
76STATISTIC(NumBackedgeSafepoints,
"Number of backedge safepoints inserted");
79 "Number of loops without safepoints due to calls in loop");
81 "Number of loops without safepoints finite execution");
103class PlaceBackedgeSafepointsLegacyPass :
public FunctionPass {
109 std::vector<Instruction *> PollLocations;
113 bool CallSafepointsEnabled;
115 PlaceBackedgeSafepointsLegacyPass(
bool CallSafepoints =
false)
121 bool runOnLoop(
Loop *);
123 void runOnLoopAndSubLoops(
Loop *L) {
126 runOnLoopAndSubLoops(
I);
131 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
132 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
133 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
134 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
135 for (
Loop *
I : *LI) {
136 runOnLoopAndSubLoops(
I);
163char PlaceBackedgeSafepointsLegacyPass::ID = 0;
166 "place-backedge-safepoints-impl",
167 "Place Backedge Safepoints",
false,
false)
197bool PlaceBackedgeSafepointsLegacyPass::runOnLoop(
Loop *L) {
205 L->getLoopLatches(LoopLatches);
207 assert(L->contains(Pred));
214 LLVM_DEBUG(
dbgs() <<
"skipping safepoint placement in finite loop\n");
218 if (CallSafepointsEnabled &&
225 <<
"skipping safepoint placement due to unconditional call\n");
243 PollLocations.push_back(Term);
274char PlaceSafepointsLegacyPass::ID = 0;
277 "Place Safepoints",
false,
false)
283 return new PlaceSafepointsLegacyPass();
286bool PlaceSafepointsLegacyPass::runOnFunction(
Function &
F) {
290 LLVM_DEBUG(
dbgs() <<
"********** Begin Safepoint Placement **********\n");
294 Impl.runImpl(
F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F));
297 LLVM_DEBUG(
dbgs() <<
"********** Function after Safepoint Placement: "
298 <<
F.getName() <<
'\n');
301 LLVM_DEBUG(
dbgs() <<
"********** End Safepoint Placement **********\n");
307 if (
F.isDeclaration() ||
F.empty()) {
339 std::vector<CallBase *> ParsePointNeeded;
348 auto *PBS =
new PlaceBackedgeSafepointsLegacyPass(CanAssumeCallSafepoints);
356 auto &PollLocations = PBS->PollLocations;
368 PollLocations.erase(std::unique(PollLocations.begin(), PollLocations.end()),
369 PollLocations.end());
389 for (
unsigned i = 0; i < Term->getNumSuccessors(); i++) {
391 if (DT.
dominates(Succ, Term->getParent())) {
395 assert(!Headers.
empty() &&
"poll location is not a loop latch?");
404 NumBackedgeSafepoints++;
409 NumBackedgeSafepoints++;
418 NumEntrySafepoints++;
427 std::vector<CallBase *> RuntimeCalls;
449 if (
auto *CI = dyn_cast<CallInst>(Call)) {
450 if (CI->isInlineAsm())
454 return !(isa<GCStatepointInst>(Call) || isa<GCRelocateInst>(Call) ||
455 isa<GCResultInst>(Call));
476 assert(DT.
dominates(Header, Pred) &&
"loop latch not dominated by header?");
481 if (
auto *Call = dyn_cast<CallBase>(&
I))
492 if (Current == Header)
508 if (!isa<SCEVCouldNotCompute>(MaxTrips) &&
516 if (L->isLoopExiting(Pred)) {
520 if (!isa<SCEVCouldNotCompute>(MaxExec) &&
530 std::vector<CallInst *> &Calls,
532 std::vector<BasicBlock *> &Worklist) {
535 BBI != BBE0 && BBI != BBE1; BBI++) {
536 if (
CallInst *CI = dyn_cast<CallInst>(&*BBI))
540 assert(!isa<InvokeInst>(&*BBI) &&
541 "support for invokes in poll code needed");
545 if (BBI->isTerminator()) {
548 if (Seen.
insert(Succ).second) {
549 Worklist.push_back(Succ);
557 std::vector<CallInst *> &Calls,
560 std::vector<BasicBlock *> Worklist;
561 Seen.
insert(Start->getParent());
562 scanOneBB(Start, End, Calls, Seen, Worklist);
563 while (!Worklist.empty()) {
574 switch (II->getIntrinsicID()) {
575 case Intrinsic::experimental_gc_statepoint:
576 case Intrinsic::experimental_patchpoint_void:
577 case Intrinsic::experimental_patchpoint_i64:
608 if (!
I->isTerminator())
611 BasicBlock *nextBB =
I->getParent()->getUniqueSuccessor();
616 assert(HasNextInstruction(
I) &&
617 "first check if there is a next instruction!");
619 if (
I->isTerminator())
620 return &
I->getParent()->getUniqueSuccessor()->front();
621 return &*++
I->getIterator();
625 for (Cursor = &
F.getEntryBlock().front(); HasNextInstruction(Cursor);
626 Cursor = NextInstruction(Cursor)) {
635 if (
auto *Call = dyn_cast<CallBase>(Cursor)) {
643 "either we stopped because of a call, or because of terminator");
660 const auto &FunctionGCName =
F.getGC();
661 const StringRef StatepointExampleName(
"statepoint-example");
663 return (StatepointExampleName == FunctionGCName) ||
664 (CoreCLRName == FunctionGCName);
680 std::vector<CallBase *> &ParsePointsNeeded ,
684 assert(M &&
"must be part of a module");
691 assert(
F &&
"gc.safepoint_poll function is missing");
694 "gc.safepoint_poll declared with wrong type");
695 assert(!
F->empty() &&
"gc.safepoint_poll must be a non-empty function");
700 bool IsBegin =
false;
701 if (Before == OrigBB->
begin())
707 assert(After != OrigBB->
end() &&
"must have successor");
712 assert(InlineStatus &&
"inline must succeed");
718 std::vector<CallInst *> Calls;
728 "malformed poll function");
731 assert(!Calls.empty() &&
"slow path not found for safepoint poll");
737 assert(ParsePointsNeeded.empty());
738 for (
auto *CI : Calls) {
745 ParsePointsNeeded.push_back(CI);
747 assert(ParsePointsNeeded.size() <= Calls.size());
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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))
place backedge safepoints Place Backedge Safepoints
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 InsertSafepointPoll(Instruction *InsertBefore, std::vector< CallBase * > &ParsePointsNeeded, 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))
place backedge safepoints impl
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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
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 BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
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...
const Instruction & back() const
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="", Instruction *InsertBefore=nullptr)
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.
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.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
static 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.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
bool isTerminator() const
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 PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
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.
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 insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
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 Type * getVoidTy(LLVMContext &C)
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
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.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
void initializePlaceSafepointsLegacyPassPass(PassRegistry &)
void initializePlaceBackedgeSafepointsLegacyPassPass(PassRegistry &)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, bool MergeAttributes=false, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr)
This function inlines the called function into the basic block of the caller.
FunctionPass * createPlaceSafepointsPass()
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...
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
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...