Go to the documentation of this file.
70 #define DEBUG_TYPE "safepoint-placement"
72 STATISTIC(NumEntrySafepoints,
"Number of entry safepoints inserted");
73 STATISTIC(NumBackedgeSafepoints,
"Number of backedge safepoints inserted");
76 "Number of loops without safepoints due to calls in loop");
78 "Number of loops without safepoints finite execution");
103 struct PlaceBackedgeSafepointsImpl :
public FunctionPass {
108 std::vector<Instruction *> PollLocations;
112 bool CallSafepointsEnabled;
119 PlaceBackedgeSafepointsImpl(
bool CallSafepoints =
false)
124 bool runOnLoop(
Loop *);
125 void runOnLoopAndSubLoops(
Loop *L) {
128 runOnLoopAndSubLoops(
I);
133 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
134 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
135 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
136 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
137 for (
Loop *
I : *LI) {
138 runOnLoopAndSubLoops(
I);
182 std::vector<CallBase *> &ParsePointsNeeded ,
188 if (
auto *CI = dyn_cast<CallInst>(Call)) {
189 if (CI->isInlineAsm())
193 return !(isa<GCStatepointInst>(Call) || isa<GCRelocateInst>(Call) ||
194 isa<GCResultInst>(Call));
215 assert(DT.
dominates(Header, Pred) &&
"loop latch not dominated by header?");
220 if (
auto *Call = dyn_cast<CallBase>(&
I))
231 if (Current == Header)
247 if (!isa<SCEVCouldNotCompute>(MaxTrips) &&
259 if (!isa<SCEVCouldNotCompute>(MaxExec) &&
269 std::vector<CallInst *> &Calls,
271 std::vector<BasicBlock *> &Worklist) {
274 BBI != BBE0 && BBI != BBE1; BBI++) {
275 if (
CallInst *CI = dyn_cast<CallInst>(&*BBI))
279 assert(!isa<InvokeInst>(&*BBI) &&
280 "support for invokes in poll code needed");
284 if (BBI->isTerminator()) {
287 if (Seen.
insert(Succ).second) {
288 Worklist.push_back(Succ);
296 std::vector<CallInst *> &Calls,
299 std::vector<BasicBlock *> Worklist;
300 Seen.
insert(Start->getParent());
301 scanOneBB(Start, End, Calls, Seen, Worklist);
302 while (!Worklist.empty()) {
305 scanOneBB(&*
BB->begin(), End, Calls, Seen, Worklist);
309 bool PlaceBackedgeSafepointsImpl::runOnLoop(
Loop *L) {
326 LLVM_DEBUG(
dbgs() <<
"skipping safepoint placement in finite loop\n");
330 if (CallSafepointsEnabled &&
337 <<
"skipping safepoint placement due to unconditional call\n");
355 PollLocations.push_back(
Term);
365 switch (II->getIntrinsicID()) {
366 case Intrinsic::experimental_gc_statepoint:
367 case Intrinsic::experimental_patchpoint_void:
368 case Intrinsic::experimental_patchpoint_i64:
399 if (!
I->isTerminator())
402 BasicBlock *nextBB =
I->getParent()->getUniqueSuccessor();
407 assert(HasNextInstruction(
I) &&
408 "first check if there is a next instruction!");
410 if (
I->isTerminator())
411 return &
I->getParent()->getUniqueSuccessor()->front();
412 return &*++
I->getIterator();
416 for (Cursor = &
F.getEntryBlock().front(); HasNextInstruction(Cursor);
417 Cursor = NextInstruction(Cursor)) {
426 if (
auto *Call = dyn_cast<CallBase>(Cursor)) {
434 "either we stopped because of a call, or because of terminator");
451 const auto &FunctionGCName =
F.getGC();
452 const StringRef StatepointExampleName(
"statepoint-example");
454 return (StatepointExampleName == FunctionGCName) ||
455 (CoreCLRName == FunctionGCName);
467 if (
F.isDeclaration() ||
F.empty()) {
484 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
502 std::vector<CallBase *> ParsePointNeeded;
511 auto *PBS =
new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
519 auto &PollLocations = PBS->PollLocations;
522 return a->getParent()->getName() <
b->getParent()->getName();
531 PollLocations.erase(
std::unique(PollLocations.begin(),
532 PollLocations.end()),
533 PollLocations.end());
553 for (
unsigned i = 0;
i <
Term->getNumSuccessors();
i++) {
559 assert(!Headers.
empty() &&
"poll location is not a loop latch?");
568 NumBackedgeSafepoints++;
572 PollsNeeded.push_back(
Term);
573 NumBackedgeSafepoints++;
580 PollsNeeded.push_back(Location);
582 NumEntrySafepoints++;
591 std::vector<CallBase *> RuntimeCalls;
603 return new PlaceSafepoints();
607 "place-backedge-safepoints-impl",
608 "Place Backedge Safepoints",
false,
false)
626 Module *
M = InsertBefore->getModule();
627 assert(
M &&
"must be part of a module");
634 assert(
F &&
"gc.safepoint_poll function is missing");
637 "gc.safepoint_poll declared with wrong type");
638 assert(!
F->empty() &&
"gc.safepoint_poll must be a non-empty function");
643 bool IsBegin =
false;
644 if (Before == OrigBB->
begin())
650 assert(After != OrigBB->
end() &&
"must have successor");
655 assert(InlineStatus &&
"inline must succeed");
661 std::vector<CallInst *> Calls;
671 "malformed poll function");
674 assert(!Calls.empty() &&
"slow path not found for safepoint poll");
680 assert(ParsePointsNeeded.empty());
681 for (
auto *CI : Calls) {
688 ParsePointsNeeded.push_back(CI);
690 assert(ParsePointsNeeded.size() <= Calls.size());
bool isTerminator() const
This is an optimization pass for GlobalISel generic memory operations.
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
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
Represents a single loop in the control flow graph.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
static void scanInlinedCode(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen)
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
place backedge safepoints Place Backedge Safepoints
static cl::opt< bool > SplitBackedge("spp-split-backedge", cl::Hidden, cl::init(false))
static cl::opt< bool > NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false))
FunctionPass * createPlaceSafepointsPass()
The main scalar evolution driver.
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.
static bool doesNotRequireEntrySafepointBefore(CallBase *Call)
Returns true if an entry safepoint is not required before this callsite in the caller function.
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
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.
STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted")
place backedge safepoints impl
auto successors(MachineBasicBlock *BB)
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(const ValueT &V)
static bool enableBackedgeSafepoints(Function &F)
LLVM Basic Block Representation.
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
const char GCSafepointPollName[]
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
place backedge safepoints Place Backedge false place safepoints
static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI)
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
iterator begin()
Instruction iterator methods.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Represent the analysis usage information of a pass.
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
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...
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Legacy analysis pass which computes a DominatorTree.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
static bool isGCSafepointPoll(Function &F)
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 ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first place
bool empty() const
Determine if the SetVector is empty or not.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Implements a dense probed hash-table based set.
This class represents an analyzed expression in the program.
static void scanOneBB(Instruction *Start, Instruction *End, std::vector< CallInst * > &Calls, DenseSet< BasicBlock * > &Seen, std::vector< BasicBlock * > &Worklist)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
static cl::opt< bool > AllBackedges("spp-all-backedges", cl::Hidden, cl::init(false))
initializer< Ty > init(const Ty &Val)
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A Module instance is used to store all the information related to an LLVM module.
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, BasicBlock *Pred)
Returns true if this loop is known to terminate in a finite number of iterations.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
StringRef - Represent a constant reference to a string, i.e.
static void InsertSafepointPoll(Instruction *InsertBefore, std::vector< CallBase * > &ParsePointsNeeded, const TargetLibraryInfo &TLI)
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.
static bool shouldRewriteFunction(Function &F)
Returns true if this function should be rewritten to include safepoint polls and parseable call sites...
static bool runOnFunction(Function &F, bool PostInlining)
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...
static Instruction * findLocationForEntrySafepoint(Function &F, DominatorTree &DT)
static bool enableCallSafepoints(Function &F)
void setPreservesAll()
Set by analyses that do not transform their input at all.
BlockT * getHeader() const
void sort(IteratorTy Start, IteratorTy End)
Provides information about what library functions are available for the current target.
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 ...
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
auto unique(Range &&R, Predicate P)
void initializePlaceSafepointsPass(PassRegistry &)
A wrapper class for inspecting calls to intrinsic functions.
static Type * getVoidTy(LLVMContext &C)
SmallVector< AllocaInst *, 4 > StaticAllocas
InlineFunction fills this in with all static allocas that get copied into the caller.
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"?...
FunctionPassManager manages FunctionPasses.
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...
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.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))
FunctionPass class - This class is used to implement most global optimizations.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
This class represents a function call, abstracting a target machine's calling convention.
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
AnalysisUsage & addRequired()
A vector that has set insertion semantics.
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl, "place-backedge-safepoints-impl", "Place Backedge Safepoints", false, false) INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl
static cl::opt< bool > NoCall("spp-no-call", cl::Hidden, cl::init(false))
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...
void initializePlaceBackedgeSafepointsImplPass(PassRegistry &)
static bool enableEntrySafepoints(Function &F)