LLVM 19.0.0git
ShadowStackGCLowering.cpp
Go to the documentation of this file.
1//===- ShadowStackGCLowering.cpp - Custom lowering for shadow-stack gc ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains the custom lowering code required by the shadow-stack GC
10// strategy.
11//
12// This pass implements the code transformation described in this paper:
13// "Accurate Garbage Collection in an Uncooperative Environment"
14// Fergus Henderson, ISMM, 2002
15//
16//===----------------------------------------------------------------------===//
17
23#include "llvm/CodeGen/Passes.h"
24#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/Constant.h"
26#include "llvm/IR/Constants.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/GlobalValue.h"
32#include "llvm/IR/IRBuilder.h"
35#include "llvm/IR/Intrinsics.h"
36#include "llvm/IR/Module.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
40#include "llvm/Pass.h"
43#include <cassert>
44#include <optional>
45#include <string>
46#include <utility>
47#include <vector>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "shadow-stack-gc-lowering"
52
53namespace {
54
55class ShadowStackGCLoweringImpl {
56 /// RootChain - This is the global linked-list that contains the chain of GC
57 /// roots.
58 GlobalVariable *Head = nullptr;
59
60 /// StackEntryTy - Abstract type of a link in the shadow stack.
61 StructType *StackEntryTy = nullptr;
62 StructType *FrameMapTy = nullptr;
63
64 /// Roots - GC roots in the current function. Each is a pair of the
65 /// intrinsic call and its corresponding alloca.
66 std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
67
68public:
69 ShadowStackGCLoweringImpl() = default;
70
71 bool doInitialization(Module &M);
73
74private:
75 bool IsNullValue(Value *V);
76 Constant *GetFrameMap(Function &F);
77 Type *GetConcreteStackEntryType(Function &F);
78 void CollectRoots(Function &F);
79
81 Type *Ty, Value *BasePtr, int Idx1,
82 const char *Name);
84 Type *Ty, Value *BasePtr, int Idx1, int Idx2,
85 const char *Name);
86};
87
88class ShadowStackGCLowering : public FunctionPass {
89 ShadowStackGCLoweringImpl Impl;
90
91public:
92 static char ID;
93
94 ShadowStackGCLowering();
95
96 bool doInitialization(Module &M) override { return Impl.doInitialization(M); }
97 void getAnalysisUsage(AnalysisUsage &AU) const override {
99 }
100 bool runOnFunction(Function &F) override {
101 std::optional<DomTreeUpdater> DTU;
102 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
103 DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
104 return Impl.runOnFunction(F, DTU ? &*DTU : nullptr);
105 }
106};
107
108} // end anonymous namespace
109
113 if (Map.StrategyMap.contains("shadow-stack"))
114 return PreservedAnalyses::all();
115
116 ShadowStackGCLoweringImpl Impl;
117 bool Changed = Impl.doInitialization(M);
118 for (auto &F : M) {
119 auto &FAM =
123 Changed |= Impl.runOnFunction(F, DT ? &DTU : nullptr);
124 }
125
126 if (!Changed)
127 return PreservedAnalyses::all();
130 return PA;
131}
132
133char ShadowStackGCLowering::ID = 0;
134char &llvm::ShadowStackGCLoweringID = ShadowStackGCLowering::ID;
135
136INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
137 "Shadow Stack GC Lowering", false, false)
140INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
141 "Shadow Stack GC Lowering", false, false)
142
143FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
144
145ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
147}
148
149Constant *ShadowStackGCLoweringImpl::GetFrameMap(Function &F) {
150 // doInitialization creates the abstract type of this value.
151 Type *VoidPtr = PointerType::getUnqual(F.getContext());
152
153 // Truncate the ShadowStackDescriptor if some metadata is null.
154 unsigned NumMeta = 0;
156 for (unsigned I = 0; I != Roots.size(); ++I) {
157 Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
158 if (!C->isNullValue())
159 NumMeta = I + 1;
160 Metadata.push_back(C);
161 }
162 Metadata.resize(NumMeta);
163
164 Type *Int32Ty = Type::getInt32Ty(F.getContext());
165
166 Constant *BaseElts[] = {
167 ConstantInt::get(Int32Ty, Roots.size(), false),
168 ConstantInt::get(Int32Ty, NumMeta, false),
169 };
170
171 Constant *DescriptorElts[] = {
172 ConstantStruct::get(FrameMapTy, BaseElts),
173 ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
174
175 Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
176 StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
177
178 Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
179
180 // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
181 // that, short of multithreaded LLVM, it should be safe; all that is
182 // necessary is that a simple Module::iterator loop not be invalidated.
183 // Appending to the GlobalVariable list is safe in that sense.
184 //
185 // All of the output passes emit globals last. The ExecutionEngine
186 // explicitly supports adding globals to the module after
187 // initialization.
188 //
189 // Still, if it isn't deemed acceptable, then this transformation needs
190 // to be a ModulePass (which means it cannot be in the 'llc' pipeline
191 // (which uses a FunctionPassManager (which segfaults (not asserts) if
192 // provided a ModulePass))).
193 Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
194 GlobalVariable::InternalLinkage, FrameMap,
195 "__gc_" + F.getName());
196
197 Constant *GEPIndices[2] = {
198 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
199 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
200 return ConstantExpr::getGetElementPtr(FrameMap->getType(), GV, GEPIndices);
201}
202
203Type *ShadowStackGCLoweringImpl::GetConcreteStackEntryType(Function &F) {
204 // doInitialization creates the generic version of this type.
205 std::vector<Type *> EltTys;
206 EltTys.push_back(StackEntryTy);
207 for (const std::pair<CallInst *, AllocaInst *> &Root : Roots)
208 EltTys.push_back(Root.second->getAllocatedType());
209
210 return StructType::create(EltTys, ("gc_stackentry." + F.getName()).str());
211}
212
213/// doInitialization - If this module uses the GC intrinsics, find them now. If
214/// not, exit fast.
215bool ShadowStackGCLoweringImpl::doInitialization(Module &M) {
216 bool Active = false;
217 for (Function &F : M) {
218 if (F.hasGC() && F.getGC() == "shadow-stack") {
219 Active = true;
220 break;
221 }
222 }
223 if (!Active)
224 return false;
225
226 // struct FrameMap {
227 // int32_t NumRoots; // Number of roots in stack frame.
228 // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
229 // void *Meta[]; // May be absent for roots without metadata.
230 // };
231 std::vector<Type *> EltTys;
232 // 32 bits is ok up to a 32GB stack frame. :)
233 EltTys.push_back(Type::getInt32Ty(M.getContext()));
234 // Specifies length of variable length array.
235 EltTys.push_back(Type::getInt32Ty(M.getContext()));
236 FrameMapTy = StructType::create(EltTys, "gc_map");
237 PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
238
239 // struct StackEntry {
240 // ShadowStackEntry *Next; // Caller's stack entry.
241 // FrameMap *Map; // Pointer to constant FrameMap.
242 // void *Roots[]; // Stack roots (in-place array, so we pretend).
243 // };
244
245 StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
246
247 EltTys.clear();
248 EltTys.push_back(PointerType::getUnqual(StackEntryTy));
249 EltTys.push_back(FrameMapPtrTy);
250 StackEntryTy->setBody(EltTys);
251 PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
252
253 // Get the root chain if it already exists.
254 Head = M.getGlobalVariable("llvm_gc_root_chain");
255 if (!Head) {
256 // If the root chain does not exist, insert a new one with linkonce
257 // linkage!
258 Head = new GlobalVariable(
259 M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
260 Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
261 } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
262 Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
263 Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
264 }
265
266 return true;
267}
268
269bool ShadowStackGCLoweringImpl::IsNullValue(Value *V) {
270 if (Constant *C = dyn_cast<Constant>(V))
271 return C->isNullValue();
272 return false;
273}
274
275void ShadowStackGCLoweringImpl::CollectRoots(Function &F) {
276 // FIXME: Account for original alignment. Could fragment the root array.
277 // Approach 1: Null initialize empty slots at runtime. Yuck.
278 // Approach 2: Emit a map of the array instead of just a count.
279
280 assert(Roots.empty() && "Not cleaned up?");
281
283
284 for (BasicBlock &BB : F)
285 for (Instruction &I : BB)
286 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(&I))
287 if (Function *F = CI->getCalledFunction())
288 if (F->getIntrinsicID() == Intrinsic::gcroot) {
289 std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
290 CI,
291 cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
292 if (IsNullValue(CI->getArgOperand(1)))
293 Roots.push_back(Pair);
294 else
295 MetaRoots.push_back(Pair);
296 }
297
298 // Number roots with metadata (usually empty) at the beginning, so that the
299 // FrameMap::Meta array can be elided.
300 Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
301}
302
304ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context, IRBuilder<> &B,
305 Type *Ty, Value *BasePtr, int Idx,
306 int Idx2, const char *Name) {
307 Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
308 ConstantInt::get(Type::getInt32Ty(Context), Idx),
309 ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
310 Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
311
312 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
313
314 return dyn_cast<GetElementPtrInst>(Val);
315}
316
317GetElementPtrInst *ShadowStackGCLoweringImpl::CreateGEP(LLVMContext &Context,
318 IRBuilder<> &B,
319 Type *Ty,
320 Value *BasePtr, int Idx,
321 const char *Name) {
322 Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
323 ConstantInt::get(Type::getInt32Ty(Context), Idx)};
324 Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
325
326 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
327
328 return dyn_cast<GetElementPtrInst>(Val);
329}
330
331/// runOnFunction - Insert code to maintain the shadow stack.
332bool ShadowStackGCLoweringImpl::runOnFunction(Function &F,
333 DomTreeUpdater *DTU) {
334 // Quick exit for functions that do not use the shadow stack GC.
335 if (!F.hasGC() || F.getGC() != "shadow-stack")
336 return false;
337
338 LLVMContext &Context = F.getContext();
339
340 // Find calls to llvm.gcroot.
341 CollectRoots(F);
342
343 // If there are no roots in this function, then there is no need to add a
344 // stack map entry for it.
345 if (Roots.empty())
346 return false;
347
348 // Build the constant map and figure the type of the shadow stack entry.
349 Value *FrameMap = GetFrameMap(F);
350 Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
351
352 // Build the shadow stack entry at the very start of the function.
353 BasicBlock::iterator IP = F.getEntryBlock().begin();
354 IRBuilder<> AtEntry(IP->getParent(), IP);
355
356 Instruction *StackEntry =
357 AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
358
359 AtEntry.SetInsertPointPastAllocas(&F);
360 IP = AtEntry.GetInsertPoint();
361
362 // Initialize the map pointer and load the current head of the shadow stack.
363 Instruction *CurrentHead =
364 AtEntry.CreateLoad(AtEntry.getPtrTy(), Head, "gc_currhead");
365 Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
366 StackEntry, 0, 1, "gc_frame.map");
367 AtEntry.CreateStore(FrameMap, EntryMapPtr);
368
369 // After all the allocas...
370 for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
371 // For each root, find the corresponding slot in the aggregate...
372 Value *SlotPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
373 StackEntry, 1 + I, "gc_root");
374
375 // And use it in lieu of the alloca.
376 AllocaInst *OriginalAlloca = Roots[I].second;
377 SlotPtr->takeName(OriginalAlloca);
378 OriginalAlloca->replaceAllUsesWith(SlotPtr);
379 }
380
381 // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
382 // really necessary (the collector would never see the intermediate state at
383 // runtime), but it's nicer not to push the half-initialized entry onto the
384 // shadow stack.
385 while (isa<StoreInst>(IP))
386 ++IP;
387 AtEntry.SetInsertPoint(IP->getParent(), IP);
388
389 // Push the entry onto the shadow stack.
390 Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
391 StackEntry, 0, 0, "gc_frame.next");
392 Instruction *NewHeadVal = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
393 StackEntry, 0, "gc_newhead");
394 AtEntry.CreateStore(CurrentHead, EntryNextPtr);
395 AtEntry.CreateStore(NewHeadVal, Head);
396
397 // For each instruction that escapes...
398 EscapeEnumerator EE(F, "gc_cleanup", /*HandleExceptions=*/true, DTU);
399 while (IRBuilder<> *AtExit = EE.Next()) {
400 // Pop the entry from the shadow stack. Don't reuse CurrentHead from
401 // AtEntry, since that would make the value live for the entire function.
402 Instruction *EntryNextPtr2 =
403 CreateGEP(Context, *AtExit, ConcreteStackEntryTy, StackEntry, 0, 0,
404 "gc_frame.next");
405 Value *SavedHead =
406 AtExit->CreateLoad(AtExit->getPtrTy(), EntryNextPtr2, "gc_savedhead");
407 AtExit->CreateStore(SavedHead, Head);
408 }
409
410 // Delete the original allocas (which are no longer used) and the intrinsic
411 // calls (which are no longer valid). Doing this last avoids invalidating
412 // iterators.
413 for (std::pair<CallInst *, AllocaInst *> &Root : Roots) {
414 Root.first->eraseFromParent();
415 Root.second->eraseFromParent();
416 }
417
418 Roots.clear();
419 return true;
420}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
std::string Name
static bool runOnFunction(Function &F, bool PostInlining)
#define DEBUG_TYPE
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
IntegerType * Int32Ty
LLVMContext & Context
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
pre isel intrinsic Pre ISel Intrinsic Lowering
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file contains some functions that are useful when dealing with strings.
an instruction to allocate memory on the stack
Definition: Instructions.h:59
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:168
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1291
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, std::optional< unsigned > InRangeIndex=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1201
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1356
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
EscapeEnumerator - This is a little algorithm to find all escape points from a function so that "fina...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:203
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:973
@ LinkOnceAnyLinkage
Keep one copy of function when linking (inline)
Definition: GlobalValue.h:54
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Root of the metadata hierarchy.
Definition: Metadata.h:62
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:119
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM)
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Class to represent struct types.
Definition: DerivedTypes.h:216
static StructType * create(LLVMContext &Context, StringRef Name)
This creates an identified struct.
Definition: Type.cpp:513
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt32Ty(LLVMContext &C)
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
char & ShadowStackGCLoweringID
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC.
void initializeShadowStackGCLoweringPass(PassRegistry &)
FunctionPass * createShadowStackGCLoweringPass()
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC.