Skip to content

Commit

Permalink
WIP: add flags to spill on normal/exception paths
Browse files Browse the repository at this point in the history 
TODO: Sort out what needs to be done in lowering so that clients can
recover base/derived information from stackmap if they need to.
Also add tests and verify existing tests still pass
  • Loading branch information
@JosephTremoulet
JosephTremoulet committed Feb 25, 2016
1 parent f6a7ea6 commit eea0ba7
Showing 1 changed file with 171 additions and 20 deletions.
191 changes: 171 additions & 20 deletions lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
View file
Expand Up @@ -71,6 +71,11 @@ static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
cl::location(ClobberNonLive),
cl::Hidden);

static cl::opt<bool> SpillOnExceptionPath("rs4gc-spill-on-exception-path",
cl::Hidden, cl::init(false));
static cl::opt<bool> SpillOnNormalPath("rs4gc-spill-on-normal-path", cl::Hidden,
cl::init(false));

static cl::opt<bool>
AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
cl::Hidden, cl::init(true));
Expand Down Expand Up @@ -185,6 +190,18 @@ struct PartiallyConstructedSafepointRecord {
/// They are not included into 'LiveSet' field.
/// Maps rematerialized copy to its original value.
ReconstitutedValueMapTy RematerializedValues;

/// Record fills where we spilled a live value instead of relocating.
/// They are not included into 'LiveSet' field.
/// Maps loaded copy to its original value.
ReconstitutedValueMapTy ReloadedValues;

/// Record spill slots holding live values spilled across this statepoint.
/// These need to be reported to the GC for relocation. Record bases and
/// sizes in parallel vectors.
SmallVector<Value *, 16> SpillSlots;
SmallVector<Value *, 16> BaseSpillSlots;
SmallVector<uint64_t, 16> SpillSizes;
};
}

Expand Down Expand Up @@ -1303,6 +1320,104 @@ class DeferredReplacement {
};
}

// Generate spill slots for values that get spilled rather than
// relocated/rematerialized.
typedef DenseMap<Value *, AllocaInst *> SpillMapTy;
static void StabilizeOrder(SmallVectorImpl<Value *> &LiveVec);
static void generateSpills(SpillMapTy &SpillMap, CallSite CS,
PartiallyConstructedSafepointRecord &Record) {
assert(SpillOnNormalPath || SpillOnExceptionPath);

// Calls have no exception path.
if (CS.isCall() && !SpillOnNormalPath)
return;

Function *F = CS.getInstruction()->getParent()->getParent();
Instruction *AllocaInsertBefore = &F->getEntryBlock().front();
const DataLayout &Layout = F->getParent()->getDataLayout();

// Copy the live set to a vector for "determinism" (see FIXME at
// StabilizeOrder).
// Convert to vector for efficient cross referencing.
SmallVector<Value *, 64> LiveVec;
LiveVec.reserve(Record.LiveSet.size());
LiveVec.append(Record.LiveSet.begin(), Record.LiveSet.end());
StabilizeOrder(LiveVec);

// First, generate spills.
auto getSpillSlot = [&](Value *Var) -> AllocaInst * {
AllocaInst *&SpillSlot = SpillMap[Var];
// When generating new spill slots, walk AllocaInsertBefore back
// to avoid mixing with stores if the first instruction in the
// function happens to be a statepoint.
if (!SpillSlot)
AllocaInsertBefore = SpillSlot =
new AllocaInst(Var->getType(), suffixed_name_or(Var, ".gc_spill", ""),
AllocaInsertBefore);
return SpillSlot;
};

// TODO: Be smarter about where spills are inserted to avoid redundant
// ones, and ideally consult profile weights to minimize store frequency.
Instruction *SpillInsertBefore = CS.getInstruction();
auto generateSpill = [&](Value *Var) {
AllocaInst *SpillSlot = getSpillSlot(Var);
new StoreInst(Var, SpillSlot, SpillInsertBefore);
// Record the spill,its base, and its size.
Record.SpillSlots.push_back(SpillSlot);
Value *Base = Record.PointerToBase[Var];
assert(Base && "Missing base for spilled pointer!");
Record.BaseSpillSlots.push_back(getSpillSlot(Base));
uint64_t Size = Layout.getTypeAllocSize(SpillSlot->getAllocatedType());
Record.SpillSizes.push_back(Size);
};

// TODO: Make the liveness information in the record more verbose for
// invokes so that, if spilling only across exception edges, we can
// spill only the values live into the EH pad.

// Spill all live-across values.
for (Value *Var : LiveVec)
generateSpill(Var);

// Next, generate fills.
auto generateFill = [&](Value *Var, Instruction *LoadInsertBefore) {
auto *Fill =
new LoadInst(SpillMap[Var], suffixed_name_or(Var, ".gc_reload", ""),
LoadInsertBefore);
Record.ReloadedValues[Fill] = Var;
};

// Generate normal-path fills if necessary
if (SpillOnNormalPath) {
Instruction *LoadInsertBefore;
if (CS.isCall())
LoadInsertBefore = CS.getInstruction()->getNextNode();
else
LoadInsertBefore =
&cast<InvokeInst>(CS.getInstruction())->getNormalDest()->front();
assert(!isa<PHINode>(LoadInsertBefore) &&
"Expected critical edges to be split");
for (Value *Var : LiveVec)
generateFill(Var, LoadInsertBefore);
}

// Generate exception-path fills if necessary
if (CS.isInvoke() && SpillOnExceptionPath) {
auto *Invoke = cast<InvokeInst>(CS.getInstruction());
BasicBlock *Pad = Invoke->getUnwindDest();
assert(Pad->getSinglePredecessor() &&
"Expected critical edges to be split");
for (Value *Var : LiveVec)
generateFill(Var, &*Pad->getFirstInsertionPt());
}

// If we've spilled on all paths, we don't need to generate any relocates,
// so clear the live set for this statepoint.
if (SpillOnNormalPath && (CS.isCall() || SpillOnExceptionPath))
Record.LiveSet.clear();
}

static void
makeStatepointExplicitImpl(const CallSite CS, /* to replace */
const SmallVectorImpl<Value *> &BasePtrs,
Expand Down Expand Up @@ -1351,8 +1466,8 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */
CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
CallInst *Call = Builder.CreateGCStatepointCall(
StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
TransitionArgs, DeoptArgs, None, None, None, GCPointers,
"safepoint_token");
TransitionArgs, DeoptArgs, Result.SpillSlots, Result.BaseSpillSlots,
Result.SpillSizes, GCPointers, "safepoint_token");

Call->setTailCall(ToReplace->isTailCall());
Call->setCallingConv(ToReplace->getCallingConv());
Expand Down Expand Up @@ -1381,7 +1496,8 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */
InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
StatepointID, NumPatchBytes, CallTarget, ToReplace->getNormalDest(),
ToReplace->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,
None, None, None, GCPointers, "statepoint_token");
Result.SpillSlots, Result.BaseSpillSlots, Result.SpillSizes, GCPointers,
"statepoint_token");

Invoke->setCallingConv(ToReplace->getCallingConv());

Expand All @@ -1396,21 +1512,25 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */
Token = Invoke;

// Generate gc relocates in exceptional path
BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
assert(!isa<PHINode>(UnwindBlock->begin()) &&
UnwindBlock->getUniquePredecessor() &&
"can't safely insert in this block!");
if (SpillOnExceptionPath) {
Result.UnwindToken = nullptr;
} else {
BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
assert(!isa<PHINode>(UnwindBlock->begin()) &&
UnwindBlock->getUniquePredecessor() &&
"can't safely insert in this block!");

Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());

// Attach exceptional gc relocates to the landingpad.
Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
Result.UnwindToken = ExceptionalToken;
// Attach exceptional gc relocates to the landingpad.
Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
Result.UnwindToken = ExceptionalToken;

const unsigned LiveStartIdx = Statepoint(Token).gcPtrsStartIdx();
CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken,
Builder);
const unsigned LiveStartIdx = Statepoint(Token).gcPtrsStartIdx();
CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken,
Builder);
}

// Generate gc relocates and returns for normal block
BasicBlock *NormalDest = ToReplace->getNormalDest();
Expand Down Expand Up @@ -1450,6 +1570,13 @@ makeStatepointExplicitImpl(const CallSite CS, /* to replace */
CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder);
}

// FIXME: This gives nondeterministic output when values are nameless
static void StabilizeOrder(SmallVectorImpl<Value *> &LiveVec) {
std::sort(LiveVec.begin(), LiveVec.end(), [](const Value *L, const Value *R) {
return L->getName() < R->getName();
});
}
// FIXME: This gives nondeterministic output when values are nameless
static void StabilizeOrder(SmallVectorImpl<Value *> &BaseVec,
SmallVectorImpl<Value *> &LiveVec) {
assert(BaseVec.size() == LiveVec.size());
Expand Down Expand Up @@ -1550,7 +1677,8 @@ insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs,
}

// Helper function for the "relocationViaAlloca". Similar to the
// "insertRelocationStores" but works for reconstituted values.
// "insertRelocationStores" but works for reconstituted values
// (i.e. rematerialized values and reloads of spilled values).
static void
insertReconstitutionStores(const ReconstitutedValueMapTy &ReconstitutedValues,
DenseMap<Value *, Value *> &AllocaMap,
Expand Down Expand Up @@ -1592,6 +1720,7 @@ static void relocationViaAlloca(
SmallVector<AllocaInst *, 200> PromotableAllocas;
// Used later to chack that we have enough allocas to store all values
std::size_t NumRematerializedValues = 0;
std::size_t NumSpilledValues = 0;
PromotableAllocas.reserve(Live.size());

// Emit alloca for "LiveValue" and record it in "allocaMap" and
Expand All @@ -1607,8 +1736,8 @@ static void relocationViaAlloca(
for (Value *V : Live)
emitAllocaFor(V);

// Emit allocas for rematerialized values
for (const auto &Info : Records)
// Emit allocas for reconstituted values
for (const auto &Info : Records) {
for (auto RematerializedValuePair : Info.RematerializedValues) {
Value *OriginalValue = RematerializedValuePair.second;
if (AllocaMap.count(OriginalValue) != 0)
Expand All @@ -1618,6 +1747,16 @@ static void relocationViaAlloca(
++NumRematerializedValues;
}

for (auto SpilledValuePair : Info.ReloadedValues) {
Value *OriginalValue = SpilledValuePair.second;
if (AllocaMap.count(OriginalValue) != 0)
continue;

emitAllocaFor(OriginalValue);
++NumSpilledValues;
}
}

// The next two loops are part of the same conceptual operation. We need to
// insert a store to the alloca after the original def and at each
// redefinition. We need to insert a load before each use. These are split
Expand All @@ -1638,7 +1777,7 @@ static void relocationViaAlloca(

// In case if it was invoke statepoint
// we will insert stores for exceptional path gc relocates.
if (isa<InvokeInst>(Statepoint)) {
if (isa<InvokeInst>(Statepoint) && Info.UnwindToken) {
insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
VisitedLiveValues);
}
Expand All @@ -1647,6 +1786,10 @@ static void relocationViaAlloca(
insertReconstitutionStores(Info.RematerializedValues, AllocaMap,
VisitedLiveValues);

// And with reloads
insertReconstitutionStores(Info.ReloadedValues, AllocaMap,
VisitedLiveValues);

if (ClobberNonLive) {
// As a debugging aid, pretend that an unrelocated pointer becomes null at
// the gc.statepoint. This will turn some subtle GC problems into
Expand Down Expand Up @@ -1749,7 +1892,8 @@ static void relocationViaAlloca(
}
}

assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
assert(PromotableAllocas.size() ==
Live.size() + NumRematerializedValues + NumSpilledValues &&
"we must have the same allocas with lives");
if (!PromotableAllocas.empty()) {
// Apply mem2reg to promote alloca to SSA
Expand Down Expand Up @@ -2135,6 +2279,13 @@ static bool insertParsePoints(Function &F, DominatorTree &DT,
for (size_t i = 0; i < Records.size(); i++)
rematerializeLiveValues(ToUpdate[i], Records[i], TTI);

// Generate spills/fills dictated by the strategy.
if (SpillOnNormalPath || SpillOnExceptionPath) {
SpillMapTy SpillMap;
for (size_t I = 0; I < Records.size(); ++I)
generateSpills(SpillMap, ToUpdate[I], Records[I]);
}

// We need this to safely RAUW and delete call or invoke return values that
// may themselves be live over a statepoint. For details, please see usage in
// makeStatepointExplicitImpl.
Expand Down

0 comments on commit eea0ba7

Please sign in to comment.