This is an archive of the discontinued LLVM Phabricator instance.

Differential D7218

Remove gc.roots performCustomLowering
ClosedPublic

Authored by reames on Jan 27 2015, 6:02 PM.

Details

Reviewers
whitequark
artagnon
mjacob
Commits
rG23cf2e2f9712: Remove gc.root's performCustomLowering
rL227351: Remove gc.root's performCustomLowering
Summary

This is a refactoring to restructure the single user of performCustomLowering as a specific lowering pass and remove the custom lowering hook entirely.

Before this change, the LowerIntrinsics pass (note to self: rename!) was essentially acting as a pass manager, but without being structured in terms of passes. Instead, it proxied calls to a set of GCStrategies internally. This adds a lot of conceptual complexity (i.e. GCStrategies are stateful!) for very little benefit. Since there's been interest in keeping the ShadowStackGC working, I extracting it's custom lowering pass into a dedicated pass and just added that to the pass order. It will only run for functions which opt-in to that gc.

I wasn't able to find an easy way to preserve the runtime registration of custom lowering functionality. Given that no user of this exists that I'm aware of, I made the choice to just remove that. If someone really cares, we can look at restoring it via dynamic pass registration in the future.

Note that despite the large diff, none of the lowering code actual changes. I added the framing needed to make it a pass and rename the class, but that's it.

Diff Detail

Repository
rL LLVM

Event Timeline

reames updated this revision to Diff 18871.Jan 27 2015, 6:02 PM
reames retitled this revision from to Remove gc.roots performCustomLowering.
reames updated this object.
reames edited the test plan for this revision. (Show Details)
reames added reviewers: whitequark, mjacob, artagnon.
reames added a subscriber: Unknown Object (MLST).
whitequark accepted this revision.Jan 27 2015, 6:26 PM
whitequark edited edge metadata.

LGTM

This revision is now accepted and ready to land.Jan 27 2015, 6:26 PM
mjacob edited edge metadata.Jan 28 2015, 4:22 AM

I like the direction of this patch. Probably medium-term the feature to add custom lowering passes should be re-added, but I'm fine if we ignore that for now.

docs/GarbageCollection.rst
751 ↗(On Diff #18871)

I think these three points can stay in because they're still valid.

include/llvm/CodeGen/Passes.h
520 ↗(On Diff #18871)

s/it's/its/

lib/CodeGen/GCRootLowering.cpp
119 ↗(On Diff #18871)

This comment isn't true since there's no initializeCustomLowering anymore.

lib/CodeGen/ShadowStackGCLowering.cpp
234 ↗(On Diff #18871)

I think it's now possible to add ModulePasses to the llc pass pipeline, so changing this pass to be a ModulePass should be possible.

reames added a comment.Jan 28 2015, 10:44 AM

Responding to comments. (Those not specifically responded to will be fixed before submission.)

docs/GarbageCollection.rst
751 ↗(On Diff #18871)

They're also covered elsewhere in the same file already.

lib/CodeGen/ShadowStackGCLowering.cpp
234 ↗(On Diff #18871)

I think this comment is just stale. Given I didn't touch any of this code, I'll leave it as is for now.

Closed by commit rL227351: Remove gc.root's performCustomLowering (authored by reames). · Explain WhyJan 28 2015, 11:29 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
docs/
75 lines
include/
llvm/
CodeGen/
28 lines
10 lines
1 line
lib/
CodeGen/
1 line
28 lines
3 lines
396 lines
457 lines

Diff 18911

llvm/trunk/docs/GarbageCollection.rst

Show First 20 Lines • Show All 715 Lines • ▼ Show 20 Lines
Since LLVM does not yet compute liveness information, there is no means of Since LLVM does not yet compute liveness information, there is no means of
distinguishing an uninitialized stack root from an initialized one. Therefore, distinguishing an uninitialized stack root from an initialized one. Therefore,
this feature should be used by all GC plugins. It is enabled by default. this feature should be used by all GC plugins. It is enabled by default.
Custom lowering of intrinsics: ``CustomRoots``, ``CustomReadBarriers``, and ``CustomWriteBarriers`` Custom lowering of intrinsics: ``CustomRoots``, ``CustomReadBarriers``, and ``CustomWriteBarriers``
--------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------
For GCs which use barriers or unusual treatment of stack roots, these flags For GCs which use barriers or unusual treatment of stack roots, these
allow the collector to perform arbitrary transformations of the LLVM IR: flags allow the collector to perform arbitrary transformations of the
LLVM IR:
.. code-block:: c++ .. code-block:: c++
class MyGC : public GCStrategy { class MyGC : public GCStrategy {
public: public:
MyGC() { MyGC() {
CustomRoots = true; CustomRoots = true;
CustomReadBarriers = true; CustomReadBarriers = true;
CustomWriteBarriers = true; CustomWriteBarriers = true;
} }
virtual bool initializeCustomLowering(Module &M);
virtual bool performCustomLowering(Function &F);
}; };
If any of these flags are set, then LLVM suppresses its default lowering for the If any of these flags are set, LLVM suppresses its default lowering for
corresponding intrinsics and instead calls ``performCustomLowering``. the corresponding intrinsics. Instead, you must provide a custom Pass
which lowers the intrinsics as desired. If you have opted in to custom
LLVM's default action for each intrinsic is as follows: lowering of a particular intrinsic your pass **must** eliminate all
instances of the corresponding intrinsic in functions which opt in to
* ``llvm.gcroot``: Leave it alone. The code generator must see it or the stack your GC. The best example of such a pass is the ShadowStackGC and it's
map will not be computed. ShadowStackGCLowering pass.
* ``llvm.gcread``: Substitute a ``load`` instruction.
* ``llvm.gcwrite``: Substitute a ``store`` instruction.
If ``CustomReadBarriers`` or ``CustomWriteBarriers`` are specified, then There is currently no way to register such a custom lowering pass
``performCustomLowering`` **must** eliminate the corresponding barriers. without building a custom copy of LLVM.
``performCustomLowering`` must comply with the same restrictions as
:ref:`FunctionPass::runOnFunction <writing-an-llvm-pass-runOnFunction>`
Likewise, ``initializeCustomLowering`` has the same semantics as
:ref:`Pass::doInitialization(Module&)
<writing-an-llvm-pass-doInitialization-mod>`
The following can be used as a template:
.. code-block:: c++
#include "llvm/IR/Module.h"
#include "llvm/IR/IntrinsicInst.h"
bool MyGC::initializeCustomLowering(Module &M) {
return false;
}
bool MyGC::performCustomLowering(Function &F) {
bool MadeChange = false;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; )
if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
if (Function *F = CI->getCalledFunction())
switch (F->getIntrinsicID()) {
case Intrinsic::gcwrite:
// Handle llvm.gcwrite.
CI->eraseFromParent();
MadeChange = true;
break;
case Intrinsic::gcread:
// Handle llvm.gcread.
CI->eraseFromParent();
MadeChange = true;
break;
case Intrinsic::gcroot:
// Handle llvm.gcroot.
CI->eraseFromParent();
MadeChange = true;
break;
}
return MadeChange;
}
.. _safe-points: .. _safe-points:
Generating safe points: ``NeededSafePoints`` Generating safe points: ``NeededSafePoints``
-------------------------------------------- --------------------------------------------
LLVM can compute four kinds of safe points: LLVM can compute four kinds of safe points:
▲ Show 20 Lines • Show All 207 Lines • Show Last 20 Lines

llvm/trunk/include/llvm/CodeGen/GCStrategy.h

Show First 20 Lines • Show All 95 Lines • ▼ Show 20 Linespublic:
GCStrategy(); GCStrategy();
virtual ~GCStrategy() {} virtual ~GCStrategy() {}
/// Return the name of the GC strategy. This is the value of the collector /// Return the name of the GC strategy. This is the value of the collector
/// name string specified on functions which use this strategy. /// name string specified on functions which use this strategy.
const std::string &getName() const { return Name; } const std::string &getName() const { return Name; }
/// By default, write barriers are replaced with simple store /// By default, write barriers are replaced with simple store
/// instructions. If true, then performCustomLowering must instead lower /// instructions. If true, you must provide a custom pass to lower
/// them. /// calls to @llvm.gcwrite.
bool customWriteBarrier() const { return CustomWriteBarriers; } bool customWriteBarrier() const { return CustomWriteBarriers; }
/// By default, read barriers are replaced with simple load /// By default, read barriers are replaced with simple load
/// instructions. If true, then performCustomLowering must instead lower /// instructions. If true, you must provide a custom pass to lower
/// them. /// calls to @llvm.gcread.
bool customReadBarrier() const { return CustomReadBarriers; } bool customReadBarrier() const { return CustomReadBarriers; }
/// Returns true if this strategy is expecting the use of gc.statepoints, /// Returns true if this strategy is expecting the use of gc.statepoints,
/// and false otherwise. /// and false otherwise.
bool useStatepoints() const { return UseStatepoints; } bool useStatepoints() const { return UseStatepoints; }
/** @name Statepoint Specific Properties */ /** @name Statepoint Specific Properties */
///@{ ///@{
Show All 19 Linespublic:
/// True if the given kind of safe point is required. By default, none are /// True if the given kind of safe point is required. By default, none are
/// recorded. /// recorded.
bool needsSafePoint(GC::PointKind Kind) const { bool needsSafePoint(GC::PointKind Kind) const {
return (NeededSafePoints & 1 << Kind) != 0; return (NeededSafePoints & 1 << Kind) != 0;
} }
/// By default, roots are left for the code generator so it can generate a /// By default, roots are left for the code generator so it can generate a
/// stack map. If true, then performCustomLowering must delete them. /// stack map. If true, you must provide a custom pass to lower
/// calls to @llvm.gcroot.
bool customRoots() const { return CustomRoots; } bool customRoots() const { return CustomRoots; }
/// If set, gcroot intrinsics should initialize their allocas to null /// If set, gcroot intrinsics should initialize their allocas to null
/// before the first use. This is necessary for most GCs and is enabled by /// before the first use. This is necessary for most GCs and is enabled by
/// default. /// default.
bool initializeRoots() const { return InitRoots; } bool initializeRoots() const { return InitRoots; }
/// If set, appropriate metadata tables must be emitted by the back-end /// If set, appropriate metadata tables must be emitted by the back-end
/// (assembler, JIT, or otherwise). For statepoint, this method is /// (assembler, JIT, or otherwise). For statepoint, this method is
/// currently unsupported. The stackmap information can be found in the /// currently unsupported. The stackmap information can be found in the
/// StackMap section as described in the documentation. /// StackMap section as described in the documentation.
bool usesMetadata() const { return UsesMetadata; } bool usesMetadata() const { return UsesMetadata; }
///@} ///@}
/// initializeCustomLowering/performCustomLowering - If any of the actions
/// are set to custom, performCustomLowering must be overriden to transform
/// the corresponding actions to LLVM IR. initializeCustomLowering is
/// optional to override. These are the only GCStrategy methods through
/// which the LLVM IR can be modified. These methods apply mostly to
/// gc.root based implementations, but can be overriden to provide custom
/// barrier lowerings with gc.statepoint as well.
///@{
virtual bool initializeCustomLowering(Module &F) {
// No changes made
return false;
}
virtual bool performCustomLowering(Function &F) {
llvm_unreachable("GCStrategy subclass specified a configuration which"
"requires a custom lowering without providing one");
}
}; };
/// Subclasses of GCStrategy are made available for use during compilation by /// Subclasses of GCStrategy are made available for use during compilation by
/// adding them to the global GCRegistry. This can done either within the /// adding them to the global GCRegistry. This can done either within the
/// LLVM source tree or via a loadable plugin. An example registeration /// LLVM source tree or via a loadable plugin. An example registeration
/// would be: /// would be:
/// static GCRegistry::Add<CustomGC> X("custom-name", /// static GCRegistry::Add<CustomGC> X("custom-name",
/// "my custom supper fancy gc strategy"); /// "my custom supper fancy gc strategy");
/// ///
/// Note that to use a custom GCMetadataPrinter w/gc.roots, you must also /// Note that to use a custom GCMetadataPrinter w/gc.roots, you must also
/// register your GCMetadataPrinter subclass with the /// register your GCMetadataPrinter subclass with the
/// GCMetadataPrinterRegistery as well. /// GCMetadataPrinterRegistery as well.
typedef Registry<GCStrategy> GCRegistry; typedef Registry<GCStrategy> GCRegistry;
} }
#endif #endif

llvm/trunk/include/llvm/CodeGen/Passes.h

Show First 20 Lines • Show All 511 Lines • ▼ Show 20 Lines/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
/// probabilities. /// probabilities.
extern char &MachineBlockPlacementID; extern char &MachineBlockPlacementID;
/// MachineBlockPlacementStats - This pass collects statistics about the /// MachineBlockPlacementStats - This pass collects statistics about the
/// basic block placement using branch probabilities and block frequency /// basic block placement using branch probabilities and block frequency
/// information. /// information.
extern char &MachineBlockPlacementStatsID; extern char &MachineBlockPlacementStatsID;
/// GCLowering Pass - Performs target-independent LLVM IR transformations for /// GCLowering Pass - Used by gc.root to perform its default lowering
/// highly portable strategies. /// operations.
///
FunctionPass *createGCLoweringPass(); FunctionPass *createGCLoweringPass();
/// ShadowStackGCLowering - Implements the custom lowering mechanism
/// used by the shadow stack GC. Only runs on functions which opt in to
/// the shadow stack collector.
FunctionPass *createShadowStackGCLoweringPass();
/// GCMachineCodeAnalysis - Target-independent pass to mark safe points /// GCMachineCodeAnalysis - Target-independent pass to mark safe points
/// in machine code. Must be added very late during code generation, just /// in machine code. Must be added very late during code generation, just
/// prior to output, and importantly after all CFG transformations (such as /// prior to output, and importantly after all CFG transformations (such as
/// branch folding). /// branch folding).
extern char &GCMachineCodeAnalysisID; extern char &GCMachineCodeAnalysisID;
/// Creates a pass to print GC metadata. /// Creates a pass to print GC metadata.
/// ///
▲ Show 20 Lines • Show All 99 Lines • Show Last 20 Lines

llvm/trunk/include/llvm/InitializePasses.h

Show First 20 Lines • Show All 239 Lines • ▼ Show 20 Lines
void initializeRegionViewerPass(PassRegistry&); void initializeRegionViewerPass(PassRegistry&);
void initializeSCCPPass(PassRegistry&); void initializeSCCPPass(PassRegistry&);
void initializeSROAPass(PassRegistry&); void initializeSROAPass(PassRegistry&);
void initializeSROA_DTPass(PassRegistry&); void initializeSROA_DTPass(PassRegistry&);
void initializeSROA_SSAUpPass(PassRegistry&); void initializeSROA_SSAUpPass(PassRegistry&);
void initializeScalarEvolutionAliasAnalysisPass(PassRegistry&); void initializeScalarEvolutionAliasAnalysisPass(PassRegistry&);
void initializeScalarEvolutionPass(PassRegistry&); void initializeScalarEvolutionPass(PassRegistry&);
void initializeSimpleInlinerPass(PassRegistry&); void initializeSimpleInlinerPass(PassRegistry&);
void initializeShadowStackGCLoweringPass(PassRegistry&);
void initializeRegisterCoalescerPass(PassRegistry&); void initializeRegisterCoalescerPass(PassRegistry&);
void initializeSingleLoopExtractorPass(PassRegistry&); void initializeSingleLoopExtractorPass(PassRegistry&);
void initializeSinkingPass(PassRegistry&); void initializeSinkingPass(PassRegistry&);
void initializeSeparateConstOffsetFromGEPPass(PassRegistry &); void initializeSeparateConstOffsetFromGEPPass(PassRegistry &);
void initializeSlotIndexesPass(PassRegistry&); void initializeSlotIndexesPass(PassRegistry&);
void initializeSpillPlacementPass(PassRegistry&); void initializeSpillPlacementPass(PassRegistry&);
void initializeStackProtectorPass(PassRegistry&); void initializeStackProtectorPass(PassRegistry&);
void initializeStackColoringPass(PassRegistry&); void initializeStackColoringPass(PassRegistry&);
Show All 38 Lines

llvm/trunk/lib/CodeGen/CMakeLists.txt

Show First 20 Lines • Show All 90 Lines • ▼ Show 20 Linesadd_llvm_library(LLVMCodeGen
RegisterCoalescer.cpp RegisterCoalescer.cpp
RegisterPressure.cpp RegisterPressure.cpp
RegisterScavenging.cpp RegisterScavenging.cpp
ScheduleDAG.cpp ScheduleDAG.cpp
ScheduleDAGInstrs.cpp ScheduleDAGInstrs.cpp
ScheduleDAGPrinter.cpp ScheduleDAGPrinter.cpp
ScoreboardHazardRecognizer.cpp ScoreboardHazardRecognizer.cpp
ShadowStackGC.cpp ShadowStackGC.cpp
ShadowStackGCLowering.cpp
SjLjEHPrepare.cpp SjLjEHPrepare.cpp
SlotIndexes.cpp SlotIndexes.cpp
SpillPlacement.cpp SpillPlacement.cpp
SplitKit.cpp SplitKit.cpp
StackColoring.cpp StackColoring.cpp
StackProtector.cpp StackProtector.cpp
StackSlotColoring.cpp StackSlotColoring.cpp
StackMapLivenessAnalysis.cpp StackMapLivenessAnalysis.cpp
Show All 19 Lines

llvm/trunk/lib/CodeGen/GCRootLowering.cpp

Show First 20 Lines • Show All 105 Lines • ▼ Show 20 Lines
static bool NeedsDefaultLoweringPass(const GCStrategy &C) { static bool NeedsDefaultLoweringPass(const GCStrategy &C) {
// Default lowering is necessary only if read or write barriers have a default // Default lowering is necessary only if read or write barriers have a default
// action. The default for roots is no action. // action. The default for roots is no action.
return !C.customWriteBarrier() || !C.customReadBarrier() || return !C.customWriteBarrier() || !C.customReadBarrier() ||
C.initializeRoots(); C.initializeRoots();
} }
static bool NeedsCustomLoweringPass(const GCStrategy &C) {
// Custom lowering is only necessary if enabled for some action.
return C.customWriteBarrier() || C.customReadBarrier() || C.customRoots();
}
/// doInitialization - If this module uses the GC intrinsics, find them now. /// doInitialization - If this module uses the GC intrinsics, find them now.
bool LowerIntrinsics::doInitialization(Module &M) { bool LowerIntrinsics::doInitialization(Module &M) {
// FIXME: This is rather antisocial in the context of a JIT since it performs
// work against the entire module. But this cannot be done at
// runFunction time (initializeCustomLowering likely needs to change
// the module).
GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>(); GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?"); assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isDeclaration() && I->hasGC()) if (!I->isDeclaration() && I->hasGC())
MI->getFunctionInfo(*I); // Instantiate the GC strategy. MI->getFunctionInfo(*I); // Instantiate the GC strategy.
bool MadeChange = false; return false;
for (GCModuleInfo::iterator I = MI->begin(), E = MI->end(); I != E; ++I)
if (NeedsCustomLoweringPass(**I))
if ((*I)->initializeCustomLowering(M))
MadeChange = true;
return MadeChange;
} }
/// CouldBecomeSafePoint - Predicate to conservatively determine whether the /// CouldBecomeSafePoint - Predicate to conservatively determine whether the
/// instruction could introduce a safe point. /// instruction could introduce a safe point.
static bool CouldBecomeSafePoint(Instruction *I) { static bool CouldBecomeSafePoint(Instruction *I) {
// The natural definition of instructions which could introduce safe points // The natural definition of instructions which could introduce safe points
// are: // are:
// //
▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Linesbool LowerIntrinsics::runOnFunction(Function &F) {
GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F); GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
GCStrategy &S = FI.getStrategy(); GCStrategy &S = FI.getStrategy();
bool MadeChange = false; bool MadeChange = false;
if (NeedsDefaultLoweringPass(S)) if (NeedsDefaultLoweringPass(S))
MadeChange |= PerformDefaultLowering(F, S); MadeChange |= PerformDefaultLowering(F, S);
bool UseCustomLoweringPass = NeedsCustomLoweringPass(S);
if (UseCustomLoweringPass)
MadeChange |= S.performCustomLowering(F);
// Custom lowering may modify the CFG, so dominators must be recomputed.
if (UseCustomLoweringPass) {
if (DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>())
DTWP->getDomTree().recalculate(F);
}
return MadeChange; return MadeChange;
} }
bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) { bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) {
bool LowerWr = !S.customWriteBarrier(); bool LowerWr = !S.customWriteBarrier();
bool LowerRd = !S.customReadBarrier(); bool LowerRd = !S.customReadBarrier();
bool InitRoots = S.initializeRoots(); bool InitRoots = S.initializeRoots();
▲ Show 20 Lines • Show All 147 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/Passes.cpp

Show First 20 Lines • Show All 413 Lines • ▼ Show 20 Linesvoid TargetPassConfig::addIRPasses() {
// Run loop strength reduction before anything else. // Run loop strength reduction before anything else.
if (getOptLevel() != CodeGenOpt::None && !DisableLSR) { if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
addPass(createLoopStrengthReducePass()); addPass(createLoopStrengthReducePass());
if (PrintLSR) if (PrintLSR)
addPass(createPrintFunctionPass(dbgs(), "\n\n*** Code after LSR ***\n")); addPass(createPrintFunctionPass(dbgs(), "\n\n*** Code after LSR ***\n"));
} }
// Run GC lowering passes for builtin collectors
// TODO: add a pass insertion point here
addPass(createGCLoweringPass()); addPass(createGCLoweringPass());
addPass(createShadowStackGCLoweringPass());
// Make sure that no unreachable blocks are instruction selected. // Make sure that no unreachable blocks are instruction selected.
addPass(createUnreachableBlockEliminationPass()); addPass(createUnreachableBlockEliminationPass());
// Prepare expensive constants for SelectionDAG. // Prepare expensive constants for SelectionDAG.
if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting) if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting)
addPass(createConstantHoistingPass()); addPass(createConstantHoistingPass());
▲ Show 20 Lines • Show All 371 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/ShadowStackGC.cpp

Show All 32 Lines
#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h" #include "llvm/IR/Module.h"
using namespace llvm; using namespace llvm;
#define DEBUG_TYPE "shadowstackgc" #define DEBUG_TYPE "shadowstackgc"
namespace { namespace {
class ShadowStackGC : public GCStrategy { class ShadowStackGC : public GCStrategy {
/// RootChain - This is the global linked-list that contains the chain of GC
/// roots.
GlobalVariable *Head;
/// StackEntryTy - Abstract type of a link in the shadow stack.
///
StructType *StackEntryTy;
StructType *FrameMapTy;
/// Roots - GC roots in the current function. Each is a pair of the
/// intrinsic call and its corresponding alloca.
std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
public: public:
ShadowStackGC(); ShadowStackGC();
bool initializeCustomLowering(Module &M) override;
bool performCustomLowering(Function &F) override;
private:
bool IsNullValue(Value *V);
Constant *GetFrameMap(Function &F);
Type *GetConcreteStackEntryType(Function &F);
void CollectRoots(Function &F);
static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
Value *BasePtr, int Idx1,
const char *Name);
static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
Value *BasePtr, int Idx1, int Idx2,
const char *Name);
}; };
} }
static GCRegistry::Add<ShadowStackGC> static GCRegistry::Add<ShadowStackGC>
X("shadow-stack", "Very portable GC for uncooperative code generators"); X("shadow-stack", "Very portable GC for uncooperative code generators");
namespace {
/// EscapeEnumerator - This is a little algorithm to find all escape points
/// from a function so that "finally"-style code can be inserted. In addition
/// to finding the existing return and unwind instructions, it also (if
/// necessary) transforms any call instructions into invokes and sends them to
/// a landing pad.
///
/// It's wrapped up in a state machine using the same transform C# uses for
/// 'yield return' enumerators, This transform allows it to be non-allocating.
class EscapeEnumerator {
Function &F;
const char *CleanupBBName;
// State.
int State;
Function::iterator StateBB, StateE;
IRBuilder<> Builder;
public:
EscapeEnumerator(Function &F, const char *N = "cleanup")
: F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {}
IRBuilder<> *Next() {
switch (State) {
default:
return nullptr;
case 0:
StateBB = F.begin();
StateE = F.end();
State = 1;
case 1:
// Find all 'return', 'resume', and 'unwind' instructions.
while (StateBB != StateE) {
BasicBlock *CurBB = StateBB++;
// Branches and invokes do not escape, only unwind, resume, and return
// do.
TerminatorInst *TI = CurBB->getTerminator();
if (!isa<ReturnInst>(TI) && !isa<ResumeInst>(TI))
continue;
Builder.SetInsertPoint(TI->getParent(), TI);
return &Builder;
}
State = 2;
// Find all 'call' instructions.
SmallVector<Instruction *, 16> Calls;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
for (BasicBlock::iterator II = BB->begin(), EE = BB->end(); II != EE;
++II)
if (CallInst *CI = dyn_cast<CallInst>(II))
if (!CI->getCalledFunction() ||
!CI->getCalledFunction()->getIntrinsicID())
Calls.push_back(CI);
if (Calls.empty())
return nullptr;
// Create a cleanup block.
LLVMContext &C = F.getContext();
BasicBlock *CleanupBB = BasicBlock::Create(C, CleanupBBName, &F);
Type *ExnTy =
StructType::get(Type::getInt8PtrTy(C), Type::getInt32Ty(C), nullptr);
Constant *PersFn = F.getParent()->getOrInsertFunction(
"__gcc_personality_v0", FunctionType::get(Type::getInt32Ty(C), true));
LandingPadInst *LPad =
LandingPadInst::Create(ExnTy, PersFn, 1, "cleanup.lpad", CleanupBB);
LPad->setCleanup(true);
ResumeInst *RI = ResumeInst::Create(LPad, CleanupBB);
// Transform the 'call' instructions into 'invoke's branching to the
// cleanup block. Go in reverse order to make prettier BB names.
SmallVector<Value *, 16> Args;
for (unsigned I = Calls.size(); I != 0;) {
CallInst *CI = cast<CallInst>(Calls[--I]);
// Split the basic block containing the function call.
BasicBlock *CallBB = CI->getParent();
BasicBlock *NewBB =
CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont");
// Remove the unconditional branch inserted at the end of CallBB.
CallBB->getInstList().pop_back();
NewBB->getInstList().remove(CI);
// Create a new invoke instruction.
Args.clear();
CallSite CS(CI);
Args.append(CS.arg_begin(), CS.arg_end());
InvokeInst *II =
InvokeInst::Create(CI->getCalledValue(), NewBB, CleanupBB, Args,
CI->getName(), CallBB);
II->setCallingConv(CI->getCallingConv());
II->setAttributes(CI->getAttributes());
CI->replaceAllUsesWith(II);
delete CI;
}
Builder.SetInsertPoint(RI->getParent(), RI);
return &Builder;
}
}
};
}
// -----------------------------------------------------------------------------
void llvm::linkShadowStackGC() {} void llvm::linkShadowStackGC() {}
ShadowStackGC::ShadowStackGC() : Head(nullptr), StackEntryTy(nullptr) { ShadowStackGC::ShadowStackGC() {
InitRoots = true; InitRoots = true;
CustomRoots = true; CustomRoots = true;
} }
Constant *ShadowStackGC::GetFrameMap(Function &F) {
// doInitialization creates the abstract type of this value.
Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
// Truncate the ShadowStackDescriptor if some metadata is null.
unsigned NumMeta = 0;
SmallVector<Constant *, 16> Metadata;
for (unsigned I = 0; I != Roots.size(); ++I) {
Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
if (!C->isNullValue())
NumMeta = I + 1;
Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
}
Metadata.resize(NumMeta);
Type *Int32Ty = Type::getInt32Ty(F.getContext());
Constant *BaseElts[] = {
ConstantInt::get(Int32Ty, Roots.size(), false),
ConstantInt::get(Int32Ty, NumMeta, false),
};
Constant *DescriptorElts[] = {
ConstantStruct::get(FrameMapTy, BaseElts),
ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
// FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
// that, short of multithreaded LLVM, it should be safe; all that is
// necessary is that a simple Module::iterator loop not be invalidated.
// Appending to the GlobalVariable list is safe in that sense.
//
// All of the output passes emit globals last. The ExecutionEngine
// explicitly supports adding globals to the module after
// initialization.
//
// Still, if it isn't deemed acceptable, then this transformation needs
// to be a ModulePass (which means it cannot be in the 'llc' pipeline
// (which uses a FunctionPassManager (which segfaults (not asserts) if
// provided a ModulePass))).
Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
GlobalVariable::InternalLinkage, FrameMap,
"__gc_" + F.getName());
Constant *GEPIndices[2] = {
ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
return ConstantExpr::getGetElementPtr(GV, GEPIndices);
}
Type *ShadowStackGC::GetConcreteStackEntryType(Function &F) {
// doInitialization creates the generic version of this type.
std::vector<Type *> EltTys;
EltTys.push_back(StackEntryTy);
for (size_t I = 0; I != Roots.size(); I++)
EltTys.push_back(Roots[I].second->getAllocatedType());
return StructType::create(EltTys, "gc_stackentry." + F.getName().str());
}
/// doInitialization - If this module uses the GC intrinsics, find them now. If
/// not, exit fast.
bool ShadowStackGC::initializeCustomLowering(Module &M) {
// struct FrameMap {
// int32_t NumRoots; // Number of roots in stack frame.
// int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
// void *Meta[]; // May be absent for roots without metadata.
// };
std::vector<Type *> EltTys;
// 32 bits is ok up to a 32GB stack frame. :)
EltTys.push_back(Type::getInt32Ty(M.getContext()));
// Specifies length of variable length array.
EltTys.push_back(Type::getInt32Ty(M.getContext()));
FrameMapTy = StructType::create(EltTys, "gc_map");
PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
// struct StackEntry {
// ShadowStackEntry *Next; // Caller's stack entry.
// FrameMap *Map; // Pointer to constant FrameMap.
// void *Roots[]; // Stack roots (in-place array, so we pretend).
// };
StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
EltTys.clear();
EltTys.push_back(PointerType::getUnqual(StackEntryTy));
EltTys.push_back(FrameMapPtrTy);
StackEntryTy->setBody(EltTys);
PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
// Get the root chain if it already exists.
Head = M.getGlobalVariable("llvm_gc_root_chain");
if (!Head) {
// If the root chain does not exist, insert a new one with linkonce
// linkage!
Head = new GlobalVariable(
M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
} else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
}
return true;
}
bool ShadowStackGC::IsNullValue(Value *V) {
if (Constant *C = dyn_cast<Constant>(V))
return C->isNullValue();
return false;
}
void ShadowStackGC::CollectRoots(Function &F) {
// FIXME: Account for original alignment. Could fragment the root array.
// Approach 1: Null initialize empty slots at runtime. Yuck.
// Approach 2: Emit a map of the array instead of just a count.
assert(Roots.empty() && "Not cleaned up?");
SmallVector<std::pair<CallInst *, AllocaInst *>, 16> MetaRoots;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
if (Function *F = CI->getCalledFunction())
if (F->getIntrinsicID() == Intrinsic::gcroot) {
std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
CI,
cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
if (IsNullValue(CI->getArgOperand(1)))
Roots.push_back(Pair);
else
MetaRoots.push_back(Pair);
}
// Number roots with metadata (usually empty) at the beginning, so that the
// FrameMap::Meta array can be elided.
Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
}
GetElementPtrInst *ShadowStackGC::CreateGEP(LLVMContext &Context,
IRBuilder<> &B, Value *BasePtr,
int Idx, int Idx2,
const char *Name) {
Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
ConstantInt::get(Type::getInt32Ty(Context), Idx),
ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
Value *Val = B.CreateGEP(BasePtr, Indices, Name);
assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
return dyn_cast<GetElementPtrInst>(Val);
}
GetElementPtrInst *ShadowStackGC::CreateGEP(LLVMContext &Context,
IRBuilder<> &B, Value *BasePtr,
int Idx, const char *Name) {
Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
ConstantInt::get(Type::getInt32Ty(Context), Idx)};
Value *Val = B.CreateGEP(BasePtr, Indices, Name);
assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
return dyn_cast<GetElementPtrInst>(Val);
}
/// runOnFunction - Insert code to maintain the shadow stack.
bool ShadowStackGC::performCustomLowering(Function &F) {
LLVMContext &Context = F.getContext();
// Find calls to llvm.gcroot.
CollectRoots(F);
// If there are no roots in this function, then there is no need to add a
// stack map entry for it.
if (Roots.empty())
return false;
// Build the constant map and figure the type of the shadow stack entry.
Value *FrameMap = GetFrameMap(F);
Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
// Build the shadow stack entry at the very start of the function.
BasicBlock::iterator IP = F.getEntryBlock().begin();
IRBuilder<> AtEntry(IP->getParent(), IP);
Instruction *StackEntry =
AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
while (isa<AllocaInst>(IP))
++IP;
AtEntry.SetInsertPoint(IP->getParent(), IP);
// Initialize the map pointer and load the current head of the shadow stack.
Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead");
Instruction *EntryMapPtr =
CreateGEP(Context, AtEntry, StackEntry, 0, 1, "gc_frame.map");
AtEntry.CreateStore(FrameMap, EntryMapPtr);
// After all the allocas...
for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
// For each root, find the corresponding slot in the aggregate...
Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root");
// And use it in lieu of the alloca.
AllocaInst *OriginalAlloca = Roots[I].second;
SlotPtr->takeName(OriginalAlloca);
OriginalAlloca->replaceAllUsesWith(SlotPtr);
}
// Move past the original stores inserted by GCStrategy::InitRoots. This isn't
// really necessary (the collector would never see the intermediate state at
// runtime), but it's nicer not to push the half-initialized entry onto the
// shadow stack.
while (isa<StoreInst>(IP))
++IP;
AtEntry.SetInsertPoint(IP->getParent(), IP);
// Push the entry onto the shadow stack.
Instruction *EntryNextPtr =
CreateGEP(Context, AtEntry, StackEntry, 0, 0, "gc_frame.next");
Instruction *NewHeadVal =
CreateGEP(Context, AtEntry, StackEntry, 0, "gc_newhead");
AtEntry.CreateStore(CurrentHead, EntryNextPtr);
AtEntry.CreateStore(NewHeadVal, Head);
// For each instruction that escapes...
EscapeEnumerator EE(F, "gc_cleanup");
while (IRBuilder<> *AtExit = EE.Next()) {
// Pop the entry from the shadow stack. Don't reuse CurrentHead from
// AtEntry, since that would make the value live for the entire function.
Instruction *EntryNextPtr2 =
CreateGEP(Context, *AtExit, StackEntry, 0, 0, "gc_frame.next");
Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead");
AtExit->CreateStore(SavedHead, Head);
}
// Delete the original allocas (which are no longer used) and the intrinsic
// calls (which are no longer valid). Doing this last avoids invalidating
// iterators.
for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
Roots[I].first->eraseFromParent();
Roots[I].second->eraseFromParent();
}
Roots.clear();
return true;
}

llvm/trunk/lib/CodeGen/ShadowStackGCLowering.cpp

//===-- ShadowStackGCLowering.cpp - Custom lowering for shadow-stack gc ---===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains the custom lowering code required by the shadow-stack GC
// strategy.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
using namespace llvm;
#define DEBUG_TYPE "shadowstackgclowering"
namespace {
class ShadowStackGCLowering : public FunctionPass {
/// RootChain - This is the global linked-list that contains the chain of GC
/// roots.
GlobalVariable *Head;
/// StackEntryTy - Abstract type of a link in the shadow stack.
///
StructType *StackEntryTy;
StructType *FrameMapTy;
/// Roots - GC roots in the current function. Each is a pair of the
/// intrinsic call and its corresponding alloca.
std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
public:
static char ID;
ShadowStackGCLowering();
bool doInitialization(Module &M) override;
bool runOnFunction(Function &F) override;
private:
bool IsNullValue(Value *V);
Constant *GetFrameMap(Function &F);
Type *GetConcreteStackEntryType(Function &F);
void CollectRoots(Function &F);
static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
Value *BasePtr, int Idx1,
const char *Name);
static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
Value *BasePtr, int Idx1, int Idx2,
const char *Name);
};
}
INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, "shadow-stack-gc-lowering",
"Shadow Stack GC Lowering", false, false)
INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)
INITIALIZE_PASS_END(ShadowStackGCLowering, "shadow-stack-gc-lowering",
"Shadow Stack GC Lowering", false, false)
FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
char ShadowStackGCLowering::ID = 0;
ShadowStackGCLowering::ShadowStackGCLowering()
: FunctionPass(ID), Head(nullptr), StackEntryTy(nullptr),
FrameMapTy(nullptr) {
initializeShadowStackGCLoweringPass(*PassRegistry::getPassRegistry());
}
namespace {
/// EscapeEnumerator - This is a little algorithm to find all escape points
/// from a function so that "finally"-style code can be inserted. In addition
/// to finding the existing return and unwind instructions, it also (if
/// necessary) transforms any call instructions into invokes and sends them to
/// a landing pad.
///
/// It's wrapped up in a state machine using the same transform C# uses for
/// 'yield return' enumerators, This transform allows it to be non-allocating.
class EscapeEnumerator {
Function &F;
const char *CleanupBBName;
// State.
int State;
Function::iterator StateBB, StateE;
IRBuilder<> Builder;
public:
EscapeEnumerator(Function &F, const char *N = "cleanup")
: F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {}
IRBuilder<> *Next() {
switch (State) {
default:
return nullptr;
case 0:
StateBB = F.begin();
StateE = F.end();
State = 1;
case 1:
// Find all 'return', 'resume', and 'unwind' instructions.
while (StateBB != StateE) {
BasicBlock *CurBB = StateBB++;
// Branches and invokes do not escape, only unwind, resume, and return
// do.
TerminatorInst *TI = CurBB->getTerminator();
if (!isa<ReturnInst>(TI) && !isa<ResumeInst>(TI))
continue;
Builder.SetInsertPoint(TI->getParent(), TI);
return &Builder;
}
State = 2;
// Find all 'call' instructions.
SmallVector<Instruction *, 16> Calls;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
for (BasicBlock::iterator II = BB->begin(), EE = BB->end(); II != EE;
++II)
if (CallInst *CI = dyn_cast<CallInst>(II))
if (!CI->getCalledFunction() ||
!CI->getCalledFunction()->getIntrinsicID())
Calls.push_back(CI);
if (Calls.empty())
return nullptr;
// Create a cleanup block.
LLVMContext &C = F.getContext();
BasicBlock *CleanupBB = BasicBlock::Create(C, CleanupBBName, &F);
Type *ExnTy =
StructType::get(Type::getInt8PtrTy(C), Type::getInt32Ty(C), nullptr);
Constant *PersFn = F.getParent()->getOrInsertFunction(
"__gcc_personality_v0", FunctionType::get(Type::getInt32Ty(C), true));
LandingPadInst *LPad =
LandingPadInst::Create(ExnTy, PersFn, 1, "cleanup.lpad", CleanupBB);
LPad->setCleanup(true);
ResumeInst *RI = ResumeInst::Create(LPad, CleanupBB);
// Transform the 'call' instructions into 'invoke's branching to the
// cleanup block. Go in reverse order to make prettier BB names.
SmallVector<Value *, 16> Args;
for (unsigned I = Calls.size(); I != 0;) {
CallInst *CI = cast<CallInst>(Calls[--I]);
// Split the basic block containing the function call.
BasicBlock *CallBB = CI->getParent();
BasicBlock *NewBB =
CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont");
// Remove the unconditional branch inserted at the end of CallBB.
CallBB->getInstList().pop_back();
NewBB->getInstList().remove(CI);
// Create a new invoke instruction.
Args.clear();
CallSite CS(CI);
Args.append(CS.arg_begin(), CS.arg_end());
InvokeInst *II =
InvokeInst::Create(CI->getCalledValue(), NewBB, CleanupBB, Args,
CI->getName(), CallBB);
II->setCallingConv(CI->getCallingConv());
II->setAttributes(CI->getAttributes());
CI->replaceAllUsesWith(II);
delete CI;
}
Builder.SetInsertPoint(RI->getParent(), RI);
return &Builder;
}
}
};
}
Constant *ShadowStackGCLowering::GetFrameMap(Function &F) {
// doInitialization creates the abstract type of this value.
Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
// Truncate the ShadowStackDescriptor if some metadata is null.
unsigned NumMeta = 0;
SmallVector<Constant *, 16> Metadata;
for (unsigned I = 0; I != Roots.size(); ++I) {
Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
if (!C->isNullValue())
NumMeta = I + 1;
Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
}
Metadata.resize(NumMeta);
Type *Int32Ty = Type::getInt32Ty(F.getContext());
Constant *BaseElts[] = {
ConstantInt::get(Int32Ty, Roots.size(), false),
ConstantInt::get(Int32Ty, NumMeta, false),
};
Constant *DescriptorElts[] = {
ConstantStruct::get(FrameMapTy, BaseElts),
ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
// FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
// that, short of multithreaded LLVM, it should be safe; all that is
// necessary is that a simple Module::iterator loop not be invalidated.
// Appending to the GlobalVariable list is safe in that sense.
//
// All of the output passes emit globals last. The ExecutionEngine
// explicitly supports adding globals to the module after
// initialization.
//
// Still, if it isn't deemed acceptable, then this transformation needs
// to be a ModulePass (which means it cannot be in the 'llc' pipeline
// (which uses a FunctionPassManager (which segfaults (not asserts) if
// provided a ModulePass))).
Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
GlobalVariable::InternalLinkage, FrameMap,
"__gc_" + F.getName());
Constant *GEPIndices[2] = {
ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
return ConstantExpr::getGetElementPtr(GV, GEPIndices);
}
Type *ShadowStackGCLowering::GetConcreteStackEntryType(Function &F) {
// doInitialization creates the generic version of this type.
std::vector<Type *> EltTys;
EltTys.push_back(StackEntryTy);
for (size_t I = 0; I != Roots.size(); I++)
EltTys.push_back(Roots[I].second->getAllocatedType());
return StructType::create(EltTys, "gc_stackentry." + F.getName().str());
}
/// doInitialization - If this module uses the GC intrinsics, find them now. If
/// not, exit fast.
bool ShadowStackGCLowering::doInitialization(Module &M) {
bool Active = false;
for (Function &F : M) {
if (F.hasGC() && F.getGC() == std::string("shadow-stack")) {
Active = true;
break;
}
}
if (!Active)
return false;
// struct FrameMap {
// int32_t NumRoots; // Number of roots in stack frame.
// int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
// void *Meta[]; // May be absent for roots without metadata.
// };
std::vector<Type *> EltTys;
// 32 bits is ok up to a 32GB stack frame. :)
EltTys.push_back(Type::getInt32Ty(M.getContext()));
// Specifies length of variable length array.
EltTys.push_back(Type::getInt32Ty(M.getContext()));
FrameMapTy = StructType::create(EltTys, "gc_map");
PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
// struct StackEntry {
// ShadowStackEntry *Next; // Caller's stack entry.
// FrameMap *Map; // Pointer to constant FrameMap.
// void *Roots[]; // Stack roots (in-place array, so we pretend).
// };
StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
EltTys.clear();
EltTys.push_back(PointerType::getUnqual(StackEntryTy));
EltTys.push_back(FrameMapPtrTy);
StackEntryTy->setBody(EltTys);
PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
// Get the root chain if it already exists.
Head = M.getGlobalVariable("llvm_gc_root_chain");
if (!Head) {
// If the root chain does not exist, insert a new one with linkonce
// linkage!
Head = new GlobalVariable(
M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
} else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
}
return true;
}
bool ShadowStackGCLowering::IsNullValue(Value *V) {
if (Constant *C = dyn_cast<Constant>(V))
return C->isNullValue();
return false;
}
void ShadowStackGCLowering::CollectRoots(Function &F) {
// FIXME: Account for original alignment. Could fragment the root array.
// Approach 1: Null initialize empty slots at runtime. Yuck.
// Approach 2: Emit a map of the array instead of just a count.
assert(Roots.empty() && "Not cleaned up?");
SmallVector<std::pair<CallInst *, AllocaInst *>, 16> MetaRoots;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
if (Function *F = CI->getCalledFunction())
if (F->getIntrinsicID() == Intrinsic::gcroot) {
std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
CI,
cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
if (IsNullValue(CI->getArgOperand(1)))
Roots.push_back(Pair);
else
MetaRoots.push_back(Pair);
}
// Number roots with metadata (usually empty) at the beginning, so that the
// FrameMap::Meta array can be elided.
Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
}
GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
IRBuilder<> &B, Value *BasePtr,
int Idx, int Idx2,
const char *Name) {
Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
ConstantInt::get(Type::getInt32Ty(Context), Idx),
ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
Value *Val = B.CreateGEP(BasePtr, Indices, Name);
assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
return dyn_cast<GetElementPtrInst>(Val);
}
GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
IRBuilder<> &B, Value *BasePtr,
int Idx, const char *Name) {
Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
ConstantInt::get(Type::getInt32Ty(Context), Idx)};
Value *Val = B.CreateGEP(BasePtr, Indices, Name);
assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
return dyn_cast<GetElementPtrInst>(Val);
}
/// runOnFunction - Insert code to maintain the shadow stack.
bool ShadowStackGCLowering::runOnFunction(Function &F) {
// Quick exit for functions that do not use the shadow stack GC.
if (!F.hasGC() ||
F.getGC() != std::string("shadow-stack"))
return false;
LLVMContext &Context = F.getContext();
// Find calls to llvm.gcroot.
CollectRoots(F);
// If there are no roots in this function, then there is no need to add a
// stack map entry for it.
if (Roots.empty())
return false;
// Build the constant map and figure the type of the shadow stack entry.
Value *FrameMap = GetFrameMap(F);
Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
// Build the shadow stack entry at the very start of the function.
BasicBlock::iterator IP = F.getEntryBlock().begin();
IRBuilder<> AtEntry(IP->getParent(), IP);
Instruction *StackEntry =
AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
while (isa<AllocaInst>(IP))
++IP;
AtEntry.SetInsertPoint(IP->getParent(), IP);
// Initialize the map pointer and load the current head of the shadow stack.
Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead");
Instruction *EntryMapPtr =
CreateGEP(Context, AtEntry, StackEntry, 0, 1, "gc_frame.map");
AtEntry.CreateStore(FrameMap, EntryMapPtr);
// After all the allocas...
for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
// For each root, find the corresponding slot in the aggregate...
Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root");
// And use it in lieu of the alloca.
AllocaInst *OriginalAlloca = Roots[I].second;
SlotPtr->takeName(OriginalAlloca);
OriginalAlloca->replaceAllUsesWith(SlotPtr);
}
// Move past the original stores inserted by GCStrategy::InitRoots. This isn't
// really necessary (the collector would never see the intermediate state at
// runtime), but it's nicer not to push the half-initialized entry onto the
// shadow stack.
while (isa<StoreInst>(IP))
++IP;
AtEntry.SetInsertPoint(IP->getParent(), IP);
// Push the entry onto the shadow stack.
Instruction *EntryNextPtr =
CreateGEP(Context, AtEntry, StackEntry, 0, 0, "gc_frame.next");
Instruction *NewHeadVal =
CreateGEP(Context, AtEntry, StackEntry, 0, "gc_newhead");
AtEntry.CreateStore(CurrentHead, EntryNextPtr);
AtEntry.CreateStore(NewHeadVal, Head);
// For each instruction that escapes...
EscapeEnumerator EE(F, "gc_cleanup");
while (IRBuilder<> *AtExit = EE.Next()) {
// Pop the entry from the shadow stack. Don't reuse CurrentHead from
// AtEntry, since that would make the value live for the entire function.
Instruction *EntryNextPtr2 =
CreateGEP(Context, *AtExit, StackEntry, 0, 0, "gc_frame.next");
Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead");
AtExit->CreateStore(SavedHead, Head);
}
// Delete the original allocas (which are no longer used) and the intrinsic
// calls (which are no longer valid). Doing this last avoids invalidating
// iterators.
for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
Roots[I].first->eraseFromParent();
Roots[I].second->eraseFromParent();
}
Roots.clear();
return true;
}