69 #define DEBUG_TYPE "safepoint-placement" 71 STATISTIC(NumEntrySafepoints,
"Number of entry safepoints inserted");
72 STATISTIC(NumBackedgeSafepoints,
"Number of backedge safepoints inserted");
75 "Number of loops without safepoints due to calls in loop");
77 "Number of loops without safepoints finite execution");
102 struct PlaceBackedgeSafepointsImpl :
public FunctionPass {
107 std::vector<Instruction *> PollLocations;
111 bool CallSafepointsEnabled;
118 PlaceBackedgeSafepointsImpl(
bool CallSafepoints =
false)
123 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);
181 std::vector<CallBase *> &ParsePointsNeeded ,
187 if (
auto *CI = dyn_cast<CallInst>(Call)) {
188 if (CI->isInlineAsm())
192 return !(isa<GCStatepointInst>(Call) || isa<GCRelocateInst>(Call) ||
193 isa<GCResultInst>(Call));
214 assert(DT.
dominates(Header, Pred) &&
"loop latch not dominated by header?");
219 if (
auto *Call = dyn_cast<CallBase>(&
I))
230 if (Current == Header)
246 if (!isa<SCEVCouldNotCompute>(MaxTrips) &&
258 if (!isa<SCEVCouldNotCompute>(MaxExec) &&
268 std::vector<CallInst *> &Calls,
270 std::vector<BasicBlock *> &Worklist) {
273 BBI != BBE0 && BBI != BBE1; BBI++) {
274 if (
CallInst *CI = dyn_cast<CallInst>(&*BBI))
278 assert(!isa<InvokeInst>(&*BBI) &&
279 "support for invokes in poll code needed");
283 if (BBI->isTerminator()) {
286 if (Seen.
insert(Succ).second) {
287 Worklist.push_back(Succ);
295 std::vector<CallInst *> &Calls,
298 std::vector<BasicBlock *> Worklist;
299 Seen.
insert(Start->getParent());
300 scanOneBB(Start, End, Calls, Seen, Worklist);
301 while (!Worklist.empty()) {
308 bool PlaceBackedgeSafepointsImpl::runOnLoop(
Loop *L) {
325 LLVM_DEBUG(
dbgs() <<
"skipping safepoint placement in finite loop\n");
329 if (CallSafepointsEnabled &&
336 <<
"skipping safepoint placement due to unconditional call\n");
354 PollLocations.push_back(Term);
364 switch (II->getIntrinsicID()) {
365 case Intrinsic::experimental_gc_statepoint:
366 case Intrinsic::experimental_patchpoint_void:
367 case Intrinsic::experimental_patchpoint_i64:
398 if (!
I->isTerminator())
401 BasicBlock *nextBB =
I->getParent()->getUniqueSuccessor();
406 assert(HasNextInstruction(
I) &&
407 "first check if there is a next instruction!");
409 if (
I->isTerminator())
410 return &
I->getParent()->getUniqueSuccessor()->front();
411 return &*++
I->getIterator();
415 for (Cursor = &
F.getEntryBlock().front(); HasNextInstruction(Cursor);
416 Cursor = NextInstruction(Cursor)) {
425 if (
auto *Call = dyn_cast<CallBase>(Cursor)) {
433 "either we stopped because of a call, or because of terminator");
450 const auto &FunctionGCName =
F.getGC();
451 const StringRef StatepointExampleName(
"statepoint-example");
453 return (StatepointExampleName == FunctionGCName) ||
454 (CoreCLRName == FunctionGCName);
466 if (
F.isDeclaration() ||
F.empty()) {
483 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
501 std::vector<CallBase *> ParsePointNeeded;
510 auto *PBS =
new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
518 auto &PollLocations = PBS->PollLocations;
530 PollLocations.erase(std::unique(PollLocations.begin(),
531 PollLocations.end()),
532 PollLocations.end());
558 assert(!Headers.
empty() &&
"poll location is not a loop latch?");
567 NumBackedgeSafepoints++;
572 NumBackedgeSafepoints++;
581 NumEntrySafepoints++;
590 std::vector<CallBase *> RuntimeCalls;
602 return new PlaceSafepoints();
606 "place-backedge-safepoints-impl",
607 "Place Backedge Safepoints",
false,
false)
625 Module *M = InsertBefore->getModule();
626 assert(M &&
"must be part of a module");
633 assert(
F &&
"gc.safepoint_poll function is missing");
636 "gc.safepoint_poll declared with wrong type");
637 assert(!
F->empty() &&
"gc.safepoint_poll must be a non-empty function");
642 bool IsBegin =
false;
643 if (Before == OrigBB->
begin())
649 assert(After != OrigBB->
end() &&
"must have successor");
654 assert(InlineStatus &&
"inline must succeed");
658 assert(IFI.StaticAllocas.empty() &&
"can't have allocs");
660 std::vector<CallInst *> Calls;
670 "malformed poll function");
673 assert(!Calls.empty() &&
"slow path not found for safepoint poll");
679 assert(ParsePointsNeeded.empty());
680 for (
auto *CI : Calls) {
687 ParsePointsNeeded.push_back(CI);
689 assert(ParsePointsNeeded.size() <= Calls.size());
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, BasicBlock *Pred)
Returns true if this loop is known to terminate in a finite number of iterations.
STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted")
InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr)
This function inlines the called function into the basic block of the caller.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool shouldRewriteFunction(Function &F)
Returns true if this function should be rewritten to include safepoint polls and parseable call sites...
This class represents lattice values for constants.
A Module instance is used to store all the information related to an LLVM module.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
const char GCSafepointPollName[]
Implements a dense probed hash-table based set.
void push_back(const T &Elt)
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
The main scalar evolution driver.
This class represents a function call, abstracting a target machine's calling convention.
bool isTerminator() const
void initializePlaceSafepointsPass(PassRegistry &)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
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...
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
iterator begin()
Instruction iterator methods.
AnalysisUsage & addRequired()
static cl::opt< bool > NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false))
BlockT * getHeader() const
place backedge safepoints impl
static bool doesNotRequireEntrySafepointBefore(CallBase *Call)
Returns true if an entry safepoint is not required before this callsite in the caller function.
static bool enableCallSafepoints(Function &F)
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl, "place-backedge-safepoints-impl", "Place Backedge Safepoints", false, false) INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl
bool insert(const value_type &X)
Insert a new element into the SetVector.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
void initializePlaceBackedgeSafepointsImplPass(PassRegistry &)
static cl::opt< bool > SplitBackedge("spp-split-backedge", cl::Hidden, cl::init(false))
static Instruction * findLocationForEntrySafepoint(Function &F, DominatorTree &DT)
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
static bool enableEntrySafepoints(Function &F)
FunctionPass * createPlaceSafepointsPass()
LLVM Basic Block Representation.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
DomTreeNodeBase * getIDom() const
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...
std::pair< iterator, bool > insert(const ValueT &V)
static cl::opt< bool > NoCall("spp-no-call", cl::Hidden, cl::init(false))
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
static cl::opt< bool > AllBackedges("spp-all-backedges", cl::Hidden, cl::init(false))
const Instruction & back() const
bool dominates(const Value *Def, const Use &U) const
Return true if value Def dominates use U, in the sense that Def is available at U,...
static void scanOneBB(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen, std::vector< BasicBlock * > &Worklist)
FunctionPass class - This class is used to implement most global optimizations.
static void InsertSafepointPoll(Instruction *InsertBefore, std::vector< CallBase * > &ParsePointsNeeded, const TargetLibraryInfo &TLI)
void sort(IteratorTy Start, IteratorTy End)
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
place backedge safepoints Place Backedge Safepoints
FunctionPassManager manages FunctionPasses.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool isGCSafepointPoll(Function &F)
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...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Iterator for intrusive lists based on ilist_node.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static void scanInlinedCode(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen)
void setPreservesAll()
Set by analyses that do not transform their input at all.
static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))
InstListType::iterator iterator
Instruction iterators...
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"?...
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
This class represents an analyzed expression in the program.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
Represents a single loop in the control flow graph.
StringRef getName() const
Return a constant reference to the value's name.
const Function * getParent() const
Return the enclosing method, or null if none.
bool empty() const
Determine if the SetVector is empty or not.
place backedge safepoints Place Backedge false place safepoints
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
static bool enableBackedgeSafepoints(Function &F)
static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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...
A vector that has set insertion semantics.
succ_range successors(Instruction *I)
static 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 ...
The legacy pass manager's analysis pass to compute loop information.
StringRef - Represent a constant reference to a string, i.e.
Legacy analysis pass which computes a DominatorTree.
A wrapper class for inspecting calls to intrinsic functions.
const BasicBlock * getParent() const
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)