PlaceSafepoints.cpp [plain text]
#include "llvm/Pass.h"
#include "llvm/PassManager.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#define DEBUG_TYPE "safepoint-placement"
STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
STATISTIC(NumCallSafepoints, "Number of call safepoints inserted");
STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop");
STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution");
using namespace llvm;
static cl::opt<bool> AllBackedges("spp-all-backedges", cl::init(false));
static cl::opt<bool> SkipCounted("spp-counted", cl::init(true));
static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::init(false));
static cl::opt<bool> TraceLSP("spp-trace", cl::init(false));
namespace {
struct PlaceBackedgeSafepointsImpl : public LoopPass {
static char ID;
std::vector<TerminatorInst *> PollLocations;
bool CallSafepointsEnabled;
PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
: LoopPass(ID), CallSafepointsEnabled(CallSafepoints) {
initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
}
bool runOnLoop(Loop *, LPPassManager &LPM) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<ScalarEvolution>();
AU.addRequiredID(LoopSimplifyID);
AU.setPreservesAll();
}
};
}
static cl::opt<bool> NoEntry("spp-no-entry", cl::init(false));
static cl::opt<bool> NoCall("spp-no-call", cl::init(false));
static cl::opt<bool> NoBackedge("spp-no-backedge", cl::init(false));
namespace {
struct PlaceSafepoints : public ModulePass {
static char ID;
bool EnableEntrySafepoints;
bool EnableBackedgeSafepoints;
bool EnableCallSafepoints;
PlaceSafepoints() : ModulePass(ID) {
initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
EnableEntrySafepoints = !NoEntry;
EnableBackedgeSafepoints = !NoBackedge;
EnableCallSafepoints = !NoCall;
}
bool runOnModule(Module &M) override {
bool modified = false;
for (Function &F : M) {
modified |= runOnFunction(F);
}
return modified;
}
bool runOnFunction(Function &F);
void getAnalysisUsage(AnalysisUsage &AU) const override {
}
};
}
static void
InsertSafepointPoll(DominatorTree &DT, Instruction *after,
std::vector<CallSite> &ParsePointsNeeded );
static bool isGCLeafFunction(const CallSite &CS);
static bool needsStatepoint(const CallSite &CS) {
if (isGCLeafFunction(CS))
return false;
if (CS.isCall()) {
CallInst *call = cast<CallInst>(CS.getInstruction());
if (call->isInlineAsm())
return false;
}
if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) {
return false;
}
return true;
}
static Value *ReplaceWithStatepoint(const CallSite &CS, Pass *P);
static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
BasicBlock *Pred,
DominatorTree &DT) {
assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
BasicBlock *Current = Pred;
while (true) {
for (Instruction &I : *Current) {
if (CallSite CS = &I)
if (needsStatepoint(CS))
return true;
}
if (Current == Header)
break;
Current = DT.getNode(Current)->getIDom()->getBlock();
}
return false;
}
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
BasicBlock *Pred) {
const unsigned upperTripBound = 8192;
const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
if (MaxTrips != SE->getCouldNotCompute()) {
if (SE->getUnsignedRange(MaxTrips).getUnsignedMax().ult(upperTripBound))
return true;
if (SkipCounted &&
SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(32))
return true;
}
if (L->isLoopExiting(Pred)) {
const SCEV *MaxExec = SE->getExitCount(L, Pred);
if (MaxExec != SE->getCouldNotCompute()) {
if (SE->getUnsignedRange(MaxExec).getUnsignedMax().ult(upperTripBound))
return true;
if (SkipCounted &&
SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(32))
return true;
}
}
return false;
}
static void scanOneBB(Instruction *start, Instruction *end,
std::vector<CallInst *> &calls,
std::set<BasicBlock *> &seen,
std::vector<BasicBlock *> &worklist) {
for (BasicBlock::iterator itr(start);
itr != start->getParent()->end() && itr != BasicBlock::iterator(end);
itr++) {
if (CallInst *CI = dyn_cast<CallInst>(&*itr)) {
calls.push_back(CI);
}
assert(!dyn_cast<InvokeInst>(&*itr) &&
"support for invokes in poll code needed");
if (itr->isTerminator()) {
BasicBlock *BB = itr->getParent();
for (succ_iterator PI = succ_begin(BB), E = succ_end(BB); PI != E; ++PI) {
BasicBlock *Succ = *PI;
if (seen.count(Succ) == 0) {
worklist.push_back(Succ);
seen.insert(Succ);
}
}
}
}
}
static void scanInlinedCode(Instruction *start, Instruction *end,
std::vector<CallInst *> &calls,
std::set<BasicBlock *> &seen) {
calls.clear();
std::vector<BasicBlock *> worklist;
seen.insert(start->getParent());
scanOneBB(start, end, calls, seen, worklist);
while (!worklist.empty()) {
BasicBlock *BB = worklist.back();
worklist.pop_back();
scanOneBB(&*BB->begin(), end, calls, seen, worklist);
}
}
bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) {
ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
BasicBlock *header = L->getHeader();
DominatorTree DT;
DT.recalculate(*header->getParent());
bool modified = false;
for (pred_iterator PI = pred_begin(header), E = pred_end(header); PI != E;
PI++) {
BasicBlock *pred = *PI;
if (!L->contains(pred)) {
continue;
}
if (!AllBackedges) {
if (mustBeFiniteCountedLoop(L, SE, pred)) {
if (TraceLSP)
errs() << "skipping safepoint placement in finite loop\n";
FiniteExecution++;
continue;
}
if (CallSafepointsEnabled &&
containsUnconditionalCallSafepoint(L, header, pred, DT)) {
if (TraceLSP)
errs() << "skipping safepoint placement due to unconditional call\n";
CallInLoop++;
continue;
}
}
modified = true;
TerminatorInst *term = pred->getTerminator();
if (TraceLSP) {
errs() << "[LSP] terminator instruction: ";
term->dump();
}
PollLocations.push_back(term);
}
return modified;
}
static Instruction *findLocationForEntrySafepoint(Function &F,
DominatorTree &DT) {
auto hasNextInstruction = [](Instruction *I) {
if (!I->isTerminator()) {
return true;
}
BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
return nextBB && (nextBB->getUniquePredecessor() != nullptr);
};
auto nextInstruction = [&hasNextInstruction](Instruction *I) {
assert(hasNextInstruction(I) &&
"first check if there is a next instruction!");
if (I->isTerminator()) {
return I->getParent()->getUniqueSuccessor()->begin();
} else {
return std::next(BasicBlock::iterator(I));
}
};
Instruction *cursor = nullptr;
for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor);
cursor = nextInstruction(cursor)) {
if (CallSite CS = cursor) {
(void)CS; if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(cursor)) {
if (II->getIntrinsicID() == Intrinsic::assume) {
continue;
}
}
break;
}
}
assert((hasNextInstruction(cursor) || cursor->isTerminator()) &&
"either we stopped because of a call, or because of terminator");
if (cursor->isTerminator()) {
return cursor;
}
BasicBlock *BB = cursor->getParent();
SplitBlock(BB, cursor, nullptr);
DT.recalculate(F);
DEBUG(DT.verifyDomTree());
return BB->getTerminator();
}
static void findCallSafepoints(Function &F,
std::vector<CallSite> &Found ) {
assert(Found.empty() && "must be empty!");
for (inst_iterator itr = inst_begin(F), end = inst_end(F); itr != end;
itr++) {
Instruction *inst = &*itr;
if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
CallSite CS(inst);
if (!needsStatepoint(CS)) {
continue;
}
Found.push_back(CS);
}
}
}
template <typename T> static void unique_unsorted(std::vector<T> &vec) {
std::set<T> seen;
std::vector<T> tmp;
vec.reserve(vec.size());
std::swap(tmp, vec);
for (auto V : tmp) {
if (seen.insert(V).second) {
vec.push_back(V);
}
}
}
bool PlaceSafepoints::runOnFunction(Function &F) {
if (F.isDeclaration() || F.empty()) {
return false;
}
bool modified = false;
modified |= removeUnreachableBlocks(F);
DominatorTree DT;
std::vector<CallSite> ParsePointNeeded;
if (EnableBackedgeSafepoints) {
FunctionPassManager FPM(F.getParent());
PlaceBackedgeSafepointsImpl *PBS =
new PlaceBackedgeSafepointsImpl(EnableCallSafepoints);
FPM.add(PBS);
FPM.run(F);
DT.recalculate(F);
for (size_t i = 0; i < PBS->PollLocations.size(); i++) {
modified = true;
TerminatorInst *Term = PBS->PollLocations[i];
std::vector<CallSite> ParsePoints;
if (SplitBackedge) {
DenseSet<BasicBlock *> Headers;
for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
BasicBlock *Succ = Term->getSuccessor(i);
if (DT.dominates(Succ, Term->getParent())) {
Headers.insert(Succ);
}
}
assert(!Headers.empty() && "poll location is not a loop latch?");
DenseSet<BasicBlock *> SplitBackedges;
for (BasicBlock *Header : Headers) {
BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr);
SplitBackedges.insert(NewBB);
}
DT.recalculate(F);
for (BasicBlock *NewBB : SplitBackedges) {
InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints);
NumBackedgeSafepoints++;
}
} else {
InsertSafepointPoll(DT, Term, ParsePoints);
NumBackedgeSafepoints++;
}
ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(),
ParsePoints.end());
}
}
if (EnableEntrySafepoints) {
DT.recalculate(F);
Instruction *term = findLocationForEntrySafepoint(F, DT);
if (!term) {
} else {
std::vector<CallSite> RuntimeCalls;
InsertSafepointPoll(DT, term, RuntimeCalls);
modified = true;
NumEntrySafepoints++;
ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
RuntimeCalls.end());
}
}
if (EnableCallSafepoints) {
DT.recalculate(F);
std::vector<CallSite> Calls;
findCallSafepoints(F, Calls);
NumCallSafepoints += Calls.size();
ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end());
}
unique_unsorted(ParsePointNeeded);
DT.recalculate(F);
if (!ParsePointNeeded.empty())
modified = true;
std::vector<Value *> Results;
Results.reserve(ParsePointNeeded.size());
for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
CallSite &CS = ParsePointNeeded[i];
Value *GCResult = ReplaceWithStatepoint(CS, nullptr);
Results.push_back(GCResult);
}
assert(Results.size() == ParsePointNeeded.size());
for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
CallSite &CS = ParsePointNeeded[i];
Value *GCResult = Results[i];
if (GCResult) {
if (CS.isInvoke()) {
FoldSingleEntryPHINodes(cast<Instruction>(GCResult)->getParent(),
nullptr);
assert(
!isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
}
CS.getInstruction()->replaceAllUsesWith(GCResult);
}
CS.getInstruction()->eraseFromParent();
}
return modified;
}
char PlaceBackedgeSafepointsImpl::ID = 0;
char PlaceSafepoints::ID = 0;
ModulePass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); }
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
"place-backedge-safepoints-impl",
"Place Backedge Safepoints", false, false)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
"place-backedge-safepoints-impl",
"Place Backedge Safepoints", false, false)
INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
false, false)
INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
false, false)
static bool isGCLeafFunction(const CallSite &CS) {
Instruction *inst = CS.getInstruction();
if (isa<IntrinsicInst>(inst)) {
return true;
}
const Function *F = CS.getCalledFunction();
bool isLeaf =
F &&
F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true");
if (isLeaf) {
return true;
}
return false;
}
static void
InsertSafepointPoll(DominatorTree &DT, Instruction *term,
std::vector<CallSite> &ParsePointsNeeded ) {
Module *M = term->getParent()->getParent()->getParent();
assert(M);
FunctionType *ftype =
FunctionType::get(Type::getVoidTy(M->getContext()), false);
assert(ftype && "null?");
Function *F =
dyn_cast<Function>(M->getOrInsertFunction("gc.safepoint_poll", ftype));
assert(F && !F->empty() && "definition must exist");
CallInst *poll = CallInst::Create(F, "", term);
BasicBlock *OrigBB = term->getParent();
BasicBlock::iterator before(poll), after(poll);
bool isBegin(false);
if (before == term->getParent()->begin()) {
isBegin = true;
} else {
before--;
}
after++;
assert(after != poll->getParent()->end() && "must have successor");
assert(DT.dominates(before, after) && "trivially true");
InlineFunctionInfo IFI;
bool inlineStatus = InlineFunction(poll, IFI);
assert(inlineStatus && "inline must succeed");
(void)inlineStatus;
assert(IFI.StaticAllocas.empty() && "can't have allocs");
std::vector<CallInst *> calls; std::set<BasicBlock *> BBs; BasicBlock::iterator start;
if (isBegin) {
start = OrigBB->begin();
} else {
start = before;
start++;
}
assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) &&
"malformed poll function");
scanInlinedCode(&*(start), &*(after), calls, BBs);
DT.recalculate(*after->getParent()->getParent());
assert(!calls.empty() && "slow path not found for safepoint poll");
assert(ParsePointsNeeded.empty());
for (size_t i = 0; i < calls.size(); i++) {
if (!needsStatepoint(calls[i])) {
continue;
}
ParsePointsNeeded.push_back(CallSite(calls[i]));
}
assert(ParsePointsNeeded.size() <= calls.size());
}
static BasicBlock *normalizeBBForInvokeSafepoint(BasicBlock *BB,
BasicBlock *InvokeParent) {
BasicBlock *ret = BB;
if (!BB->getUniquePredecessor()) {
ret = SplitBlockPredecessors(BB, InvokeParent, "");
}
return ret;
}
static Value *ReplaceWithStatepoint(const CallSite &CS,
Pass *P) {
BasicBlock *BB = CS.getInstruction()->getParent();
Function *F = BB->getParent();
Module *M = F->getParent();
assert(M && "must be set");
std::vector<Type *> argTypes;
argTypes.push_back(CS.getCalledValue()->getType());
Function *gc_statepoint_decl = Intrinsic::getDeclaration(
M, Intrinsic::experimental_gc_statepoint, argTypes);
Instruction *insertBefore = CS.getInstruction();
IRBuilder<> Builder(insertBefore);
std::vector<llvm::Value *> args;
Value *Target = CS.getCalledValue();
args.push_back(Target);
int callArgSize = CS.arg_size();
args.push_back(
ConstantInt::get(Type::getInt32Ty(M->getContext()), callArgSize));
args.push_back(ConstantInt::get(Type::getInt32Ty(M->getContext()), 0));
args.insert(args.end(), CS.arg_begin(), CS.arg_end());
Instruction *token = nullptr;
AttributeSet return_attributes;
if (CS.isCall()) {
CallInst *toReplace = cast<CallInst>(CS.getInstruction());
CallInst *call =
Builder.CreateCall(gc_statepoint_decl, args, "safepoint_token");
call->setTailCall(toReplace->isTailCall());
call->setCallingConv(toReplace->getCallingConv());
AttributeSet new_attrs = toReplace->getAttributes();
call->setAttributes(new_attrs.getFnAttributes());
return_attributes = new_attrs.getRetAttributes();
token = call;
BasicBlock::iterator next(toReplace);
assert(BB->end() != next && "not a terminator, must have next");
next++;
Instruction *IP = &*(next);
Builder.SetInsertPoint(IP);
Builder.SetCurrentDebugLocation(IP->getDebugLoc());
} else if (CS.isInvoke()) {
InvokeInst *toReplace = cast<InvokeInst>(CS.getInstruction());
InvokeInst *invoke = InvokeInst::Create(
gc_statepoint_decl, toReplace->getNormalDest(),
toReplace->getUnwindDest(), args, "", toReplace->getParent());
invoke->setCallingConv(toReplace->getCallingConv());
AttributeSet new_attrs = toReplace->getAttributes();
invoke->setAttributes(new_attrs.getFnAttributes());
return_attributes = new_attrs.getRetAttributes();
token = invoke;
BasicBlock *normalDest = normalizeBBForInvokeSafepoint(
toReplace->getNormalDest(), invoke->getParent());
Instruction *IP = &*(normalDest->getFirstInsertionPt());
Builder.SetInsertPoint(IP);
} else {
llvm_unreachable("unexpect type of CallSite");
}
assert(token);
if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
Instruction *gc_result = nullptr;
std::vector<Type *> types; types.push_back(CS.getType()); auto get_gc_result_id = [&](Type &Ty) {
if (Ty.isIntegerTy()) {
return Intrinsic::experimental_gc_result_int;
} else if (Ty.isFloatingPointTy()) {
return Intrinsic::experimental_gc_result_float;
} else if (Ty.isPointerTy()) {
return Intrinsic::experimental_gc_result_ptr;
} else {
llvm_unreachable("non java type encountered");
}
};
Intrinsic::ID Id = get_gc_result_id(*CS.getType());
Value *gc_result_func = Intrinsic::getDeclaration(M, Id, types);
std::vector<Value *> args;
args.push_back(token);
gc_result = Builder.CreateCall(
gc_result_func, args,
CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "");
cast<CallInst>(gc_result)->setAttributes(return_attributes);
return gc_result;
} else {
return nullptr;
}
}