PlaceSafepoints.cpp [plain text]
#include "llvm/Pass.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.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::Hidden,
cl::init(false));
static cl::opt<int> CountedLoopTripWidth("spp-counted-loop-trip-width",
cl::Hidden, cl::init(32));
static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
cl::init(false));
static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false));
namespace {
struct PlaceBackedgeSafepointsImpl : public FunctionPass {
static char ID;
std::vector<TerminatorInst *> PollLocations;
bool CallSafepointsEnabled;
ScalarEvolution *SE = nullptr;
DominatorTree *DT = nullptr;
LoopInfo *LI = nullptr;
PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
: FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {
initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
}
bool runOnLoop(Loop *);
void runOnLoopAndSubLoops(Loop *L) {
for (auto I = L->begin(), E = L->end(); I != E; I++)
runOnLoopAndSubLoops(*I);
runOnLoop(L);
}
bool runOnFunction(Function &F) override {
SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
for (auto I = LI->begin(), E = LI->end(); I != E; I++) {
runOnLoopAndSubLoops(*I);
}
return false;
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<LoopInfoWrapperPass>();
AU.setPreservesAll();
}
};
}
static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
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));
namespace {
struct PlaceSafepoints : public FunctionPass {
static char ID;
PlaceSafepoints() : FunctionPass(ID) {
initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
}
};
}
static void
InsertSafepointPoll(Instruction *InsertBefore,
std::vector<CallSite> &ParsePointsNeeded );
static bool needsStatepoint(const CallSite &CS) {
if (callsGCLeafFunction(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 (auto CS = CallSite(&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 SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
if (MaxTrips != SE->getCouldNotCompute() &&
SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(
CountedLoopTripWidth))
return true;
if (L->isLoopExiting(Pred)) {
const SCEV *MaxExec = SE->getExitCount(L, Pred);
if (MaxExec != SE->getCouldNotCompute() &&
SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(
CountedLoopTripWidth))
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 (BasicBlock *Succ : successors(BB)) {
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) {
BasicBlock *header = L->getHeader();
SmallVector<BasicBlock*, 16> LoopLatches;
L->getLoopLatches(LoopLatches);
for (BasicBlock *pred : LoopLatches) {
assert(L->contains(pred));
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;
}
}
TerminatorInst *term = pred->getTerminator();
if (TraceLSP) {
errs() << "[LSP] terminator instruction: ";
term->dump();
}
PollLocations.push_back(term);
}
return false;
}
static bool doesNotRequireEntrySafepointBefore(const CallSite &CS) {
Instruction *Inst = CS.getInstruction();
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
switch (II->getIntrinsicID()) {
case Intrinsic::experimental_gc_statepoint:
case Intrinsic::experimental_patchpoint_void:
case Intrinsic::experimental_patchpoint_i64:
return false;
default:
return true;
}
}
return false;
}
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()->front();
} else {
return &*++I->getIterator();
}
};
Instruction *cursor = nullptr;
for (cursor = &F.getEntryBlock().front(); hasNextInstruction(cursor);
cursor = nextInstruction(cursor)) {
if (auto CS = CallSite(cursor)) {
if (doesNotRequireEntrySafepointBefore(CS))
continue;
break;
}
}
assert((hasNextInstruction(cursor) || cursor->isTerminator()) &&
"either we stopped because of a call, or because of terminator");
return cursor;
}
static void findCallSafepoints(Function &F,
std::vector<CallSite> &Found ) {
assert(Found.empty() && "must be empty!");
for (Instruction &I : instructions(F)) {
Instruction *inst = &I;
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);
}
}
}
static const char *const GCSafepointPollName = "gc.safepoint_poll";
static bool isGCSafepointPoll(Function &F) {
return F.getName().equals(GCSafepointPollName);
}
static bool shouldRewriteFunction(Function &F) {
if (F.hasGC()) {
const char *FunctionGCName = F.getGC();
const StringRef StatepointExampleName("statepoint-example");
const StringRef CoreCLRName("coreclr");
return (StatepointExampleName == FunctionGCName) ||
(CoreCLRName == FunctionGCName);
} else
return false;
}
static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
static bool enableCallSafepoints(Function &F) { return !NoCall; }
static BasicBlock *normalizeForInvokeSafepoint(BasicBlock *BB,
BasicBlock *InvokeParent) {
BasicBlock *ret = BB;
if (!BB->getUniquePredecessor()) {
ret = SplitBlockPredecessors(BB, InvokeParent, "");
}
FoldSingleEntryPHINodes(ret);
assert(!isa<PHINode>(ret->begin()));
return ret;
}
bool PlaceSafepoints::runOnFunction(Function &F) {
if (F.isDeclaration() || F.empty()) {
return false;
}
if (isGCSafepointPoll(F)) {
return false;
}
if (!shouldRewriteFunction(F))
return false;
bool modified = false;
modified |= removeUnreachableBlocks(F);
DominatorTree DT;
DT.recalculate(F);
SmallVector<Instruction *, 16> PollsNeeded;
std::vector<CallSite> ParsePointNeeded;
if (enableBackedgeSafepoints(F)) {
legacy::FunctionPassManager FPM(F.getParent());
bool CanAssumeCallSafepoints = enableCallSafepoints(F);
PlaceBackedgeSafepointsImpl *PBS =
new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
FPM.add(PBS);
FPM.run(F);
DT.recalculate(F);
auto &PollLocations = PBS->PollLocations;
auto OrderByBBName = [](Instruction *a, Instruction *b) {
return a->getParent()->getName() < b->getParent()->getName();
};
std::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
PollLocations.erase(std::unique(PollLocations.begin(),
PollLocations.end()),
PollLocations.end());
for (TerminatorInst *Term : PollLocations) {
modified = true;
if (SplitBackedge) {
SetVector<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?");
SetVector<BasicBlock *> SplitBackedges;
for (BasicBlock *Header : Headers) {
BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, &DT);
PollsNeeded.push_back(NewBB->getTerminator());
NumBackedgeSafepoints++;
}
} else {
PollsNeeded.push_back(Term);
NumBackedgeSafepoints++;
}
}
}
if (enableEntrySafepoints(F)) {
Instruction *Location = findLocationForEntrySafepoint(F, DT);
if (!Location) {
} else {
PollsNeeded.push_back(Location);
modified = true;
NumEntrySafepoints++;
}
}
for (Instruction *PollLocation : PollsNeeded) {
std::vector<CallSite> RuntimeCalls;
InsertSafepointPoll(PollLocation, RuntimeCalls);
ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
RuntimeCalls.end());
}
PollsNeeded.clear(); DT.recalculate(F);
if (enableCallSafepoints(F)) {
std::vector<CallSite> Calls;
findCallSafepoints(F, Calls);
NumCallSafepoints += Calls.size();
ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end());
}
unique_unsorted(ParsePointNeeded);
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];
if (InvokeInst *Invoke = dyn_cast<InvokeInst>(CS.getInstruction())) {
normalizeForInvokeSafepoint(Invoke->getNormalDest(),
Invoke->getParent());
}
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) {
assert(CS.isCall() || !isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
CS.getInstruction()->replaceAllUsesWith(GCResult);
}
CS.getInstruction()->eraseFromParent();
}
return modified;
}
char PlaceBackedgeSafepointsImpl::ID = 0;
char PlaceSafepoints::ID = 0;
FunctionPass *llvm::createPlaceSafepointsPass() {
return new PlaceSafepoints();
}
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
"place-backedge-safepoints-impl",
"Place Backedge Safepoints", false, false)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
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 void
InsertSafepointPoll(Instruction *InsertBefore,
std::vector<CallSite> &ParsePointsNeeded ) {
BasicBlock *OrigBB = InsertBefore->getParent();
Module *M = InsertBefore->getModule();
assert(M && "must be part of a module");
auto *F = M->getFunction(GCSafepointPollName);
assert(F->getType()->getElementType() ==
FunctionType::get(Type::getVoidTy(M->getContext()), false) &&
"gc.safepoint_poll declared with wrong type");
assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
CallInst *PollCall = CallInst::Create(F, "", InsertBefore);
BasicBlock::iterator before(PollCall), after(PollCall);
bool isBegin(false);
if (before == OrigBB->begin()) {
isBegin = true;
} else {
before--;
}
after++;
assert(after != OrigBB->end() && "must have successor");
InlineFunctionInfo IFI;
bool InlineStatus = InlineFunction(PollCall, 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);
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 Value *ReplaceWithStatepoint(const CallSite &CS,
Pass *P) {
assert(CS.getInstruction()->getParent()->getParent()->getParent() &&
"must be set");
IRBuilder<> Builder(CS.getInstruction());
Instruction *Token = nullptr;
uint64_t ID;
uint32_t NumPatchBytes;
AttributeSet OriginalAttrs = CS.getAttributes();
Attribute AttrID =
OriginalAttrs.getAttribute(AttributeSet::FunctionIndex, "statepoint-id");
Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute(
AttributeSet::FunctionIndex, "statepoint-num-patch-bytes");
AttrBuilder AttrsToRemove;
bool HasID = AttrID.isStringAttribute() &&
!AttrID.getValueAsString().getAsInteger(10, ID);
if (HasID)
AttrsToRemove.addAttribute("statepoint-id");
else
ID = 0xABCDEF00;
bool HasNumPatchBytes =
AttrNumPatchBytes.isStringAttribute() &&
!AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes);
if (HasNumPatchBytes)
AttrsToRemove.addAttribute("statepoint-num-patch-bytes");
else
NumPatchBytes = 0;
OriginalAttrs = OriginalAttrs.removeAttributes(
CS.getInstruction()->getContext(), AttributeSet::FunctionIndex,
AttrsToRemove);
if (CS.isCall()) {
CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
CallInst *Call = Builder.CreateGCStatepointCall(
ID, NumPatchBytes, CS.getCalledValue(),
makeArrayRef(CS.arg_begin(), CS.arg_end()), None, None,
"safepoint_token");
Call->setTailCall(ToReplace->isTailCall());
Call->setCallingConv(ToReplace->getCallingConv());
Call->setAttributes(OriginalAttrs.getFnAttributes());
Token = Call;
assert(ToReplace->getNextNode() && "not a terminator, must have next");
Builder.SetInsertPoint(ToReplace->getNextNode());
Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
} else if (CS.isInvoke()) {
InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
Builder.SetInsertPoint(ToReplace->getParent());
InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
ID, NumPatchBytes, CS.getCalledValue(), ToReplace->getNormalDest(),
ToReplace->getUnwindDest(), makeArrayRef(CS.arg_begin(), CS.arg_end()),
None, None, "safepoint_token");
Invoke->setCallingConv(ToReplace->getCallingConv());
Invoke->setAttributes(OriginalAttrs.getFnAttributes());
Token = Invoke;
BasicBlock *NormalDest = ToReplace->getNormalDest();
assert(!isa<PHINode>(NormalDest->begin()));
Instruction *IP = &*(NormalDest->getFirstInsertionPt());
Builder.SetInsertPoint(IP);
} else {
llvm_unreachable("unexpect type of CallSite");
}
assert(Token);
if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
std::string TakenName =
CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), TakenName);
GCResult->setAttributes(OriginalAttrs.getRetAttributes());
return GCResult;
} else {
return nullptr;
}
}