LLVM  13.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 
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
41 #include <cassert>
42 #include <cstddef>
43 #include <string>
44 #include <utility>
45 #include <vector>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "shadow-stack-gc-lowering"
50 
51 namespace {
52 
53 class ShadowStackGCLowering : public FunctionPass {
54  /// RootChain - This is the global linked-list that contains the chain of GC
55  /// roots.
56  GlobalVariable *Head = nullptr;
57 
58  /// StackEntryTy - Abstract type of a link in the shadow stack.
59  StructType *StackEntryTy = nullptr;
60  StructType *FrameMapTy = nullptr;
61 
62  /// Roots - GC roots in the current function. Each is a pair of the
63  /// intrinsic call and its corresponding alloca.
64  std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
65 
66 public:
67  static char ID;
68 
69  ShadowStackGCLowering();
70 
71  bool doInitialization(Module &M) override;
72  void getAnalysisUsage(AnalysisUsage &AU) const override;
73  bool runOnFunction(Function &F) override;
74 
75 private:
76  bool IsNullValue(Value *V);
77  Constant *GetFrameMap(Function &F);
78  Type *GetConcreteStackEntryType(Function &F);
79  void CollectRoots(Function &F);
80 
81  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
82  Type *Ty, Value *BasePtr, int Idx1,
83  const char *Name);
84  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
85  Type *Ty, Value *BasePtr, int Idx1, int Idx2,
86  const char *Name);
87 };
88 
89 } // end anonymous namespace
90 
92 
93 INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
94  "Shadow Stack GC Lowering", false, false)
97 INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
98  "Shadow Stack GC Lowering", false, false)
99 
100 FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
101 
102 ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
104 }
105 
106 Constant *ShadowStackGCLowering::GetFrameMap(Function &F) {
107  // doInitialization creates the abstract type of this value.
108  Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
109 
110  // Truncate the ShadowStackDescriptor if some metadata is null.
111  unsigned NumMeta = 0;
113  for (unsigned I = 0; I != Roots.size(); ++I) {
114  Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
115  if (!C->isNullValue())
116  NumMeta = I + 1;
117  Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
118  }
119  Metadata.resize(NumMeta);
120 
121  Type *Int32Ty = Type::getInt32Ty(F.getContext());
122 
123  Constant *BaseElts[] = {
124  ConstantInt::get(Int32Ty, Roots.size(), false),
125  ConstantInt::get(Int32Ty, NumMeta, false),
126  };
127 
128  Constant *DescriptorElts[] = {
129  ConstantStruct::get(FrameMapTy, BaseElts),
130  ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
131 
132  Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
133  StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
134 
135  Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
136 
137  // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
138  // that, short of multithreaded LLVM, it should be safe; all that is
139  // necessary is that a simple Module::iterator loop not be invalidated.
140  // Appending to the GlobalVariable list is safe in that sense.
141  //
142  // All of the output passes emit globals last. The ExecutionEngine
143  // explicitly supports adding globals to the module after
144  // initialization.
145  //
146  // Still, if it isn't deemed acceptable, then this transformation needs
147  // to be a ModulePass (which means it cannot be in the 'llc' pipeline
148  // (which uses a FunctionPassManager (which segfaults (not asserts) if
149  // provided a ModulePass))).
150  Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
151  GlobalVariable::InternalLinkage, FrameMap,
152  "__gc_" + F.getName());
153 
154  Constant *GEPIndices[2] = {
155  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
156  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
157  return ConstantExpr::getGetElementPtr(FrameMap->getType(), GV, GEPIndices);
158 }
159 
160 Type *ShadowStackGCLowering::GetConcreteStackEntryType(Function &F) {
161  // doInitialization creates the generic version of this type.
162  std::vector<Type *> EltTys;
163  EltTys.push_back(StackEntryTy);
164  for (size_t I = 0; I != Roots.size(); I++)
165  EltTys.push_back(Roots[I].second->getAllocatedType());
166 
167  return StructType::create(EltTys, ("gc_stackentry." + F.getName()).str());
168 }
169 
170 /// doInitialization - If this module uses the GC intrinsics, find them now. If
171 /// not, exit fast.
172 bool ShadowStackGCLowering::doInitialization(Module &M) {
173  bool Active = false;
174  for (Function &F : M) {
175  if (F.hasGC() && F.getGC() == std::string("shadow-stack")) {
176  Active = true;
177  break;
178  }
179  }
180  if (!Active)
181  return false;
182 
183  // struct FrameMap {
184  // int32_t NumRoots; // Number of roots in stack frame.
185  // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
186  // void *Meta[]; // May be absent for roots without metadata.
187  // };
188  std::vector<Type *> EltTys;
189  // 32 bits is ok up to a 32GB stack frame. :)
190  EltTys.push_back(Type::getInt32Ty(M.getContext()));
191  // Specifies length of variable length array.
192  EltTys.push_back(Type::getInt32Ty(M.getContext()));
193  FrameMapTy = StructType::create(EltTys, "gc_map");
194  PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
195 
196  // struct StackEntry {
197  // ShadowStackEntry *Next; // Caller's stack entry.
198  // FrameMap *Map; // Pointer to constant FrameMap.
199  // void *Roots[]; // Stack roots (in-place array, so we pretend).
200  // };
201 
202  StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
203 
204  EltTys.clear();
205  EltTys.push_back(PointerType::getUnqual(StackEntryTy));
206  EltTys.push_back(FrameMapPtrTy);
207  StackEntryTy->setBody(EltTys);
208  PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
209 
210  // Get the root chain if it already exists.
211  Head = M.getGlobalVariable("llvm_gc_root_chain");
212  if (!Head) {
213  // If the root chain does not exist, insert a new one with linkonce
214  // linkage!
215  Head = new GlobalVariable(
216  M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
217  Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
218  } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
219  Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
220  Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
221  }
222 
223  return true;
224 }
225 
226 bool ShadowStackGCLowering::IsNullValue(Value *V) {
227  if (Constant *C = dyn_cast<Constant>(V))
228  return C->isNullValue();
229  return false;
230 }
231 
232 void ShadowStackGCLowering::CollectRoots(Function &F) {
233  // FIXME: Account for original alignment. Could fragment the root array.
234  // Approach 1: Null initialize empty slots at runtime. Yuck.
235  // Approach 2: Emit a map of the array instead of just a count.
236 
237  assert(Roots.empty() && "Not cleaned up?");
238 
240 
241  for (BasicBlock &BB : F)
242  for (BasicBlock::iterator II = BB.begin(), E = BB.end(); II != E;)
243  if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
244  if (Function *F = CI->getCalledFunction())
245  if (F->getIntrinsicID() == Intrinsic::gcroot) {
246  std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
247  CI,
248  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
249  if (IsNullValue(CI->getArgOperand(1)))
250  Roots.push_back(Pair);
251  else
252  MetaRoots.push_back(Pair);
253  }
254 
255  // Number roots with metadata (usually empty) at the beginning, so that the
256  // FrameMap::Meta array can be elided.
257  Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
258 }
259 
260 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
261  IRBuilder<> &B, Type *Ty,
262  Value *BasePtr, int Idx,
263  int Idx2,
264  const char *Name) {
265  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
266  ConstantInt::get(Type::getInt32Ty(Context), Idx),
267  ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
268  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
269 
270  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
271 
272  return dyn_cast<GetElementPtrInst>(Val);
273 }
274 
275 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
276  IRBuilder<> &B, Type *Ty, Value *BasePtr,
277  int Idx, const char *Name) {
278  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
279  ConstantInt::get(Type::getInt32Ty(Context), Idx)};
280  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
281 
282  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
283 
284  return dyn_cast<GetElementPtrInst>(Val);
285 }
286 
287 void ShadowStackGCLowering::getAnalysisUsage(AnalysisUsage &AU) const {
289 }
290 
291 /// runOnFunction - Insert code to maintain the shadow stack.
293  // Quick exit for functions that do not use the shadow stack GC.
294  if (!F.hasGC() ||
295  F.getGC() != std::string("shadow-stack"))
296  return false;
297 
298  LLVMContext &Context = F.getContext();
299 
300  // Find calls to llvm.gcroot.
301  CollectRoots(F);
302 
303  // If there are no roots in this function, then there is no need to add a
304  // stack map entry for it.
305  if (Roots.empty())
306  return false;
307 
309  if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
310  DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
311 
312  // Build the constant map and figure the type of the shadow stack entry.
313  Value *FrameMap = GetFrameMap(F);
314  Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
315 
316  // Build the shadow stack entry at the very start of the function.
317  BasicBlock::iterator IP = F.getEntryBlock().begin();
318  IRBuilder<> AtEntry(IP->getParent(), IP);
319 
320  Instruction *StackEntry =
321  AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
322 
323  while (isa<AllocaInst>(IP))
324  ++IP;
325  AtEntry.SetInsertPoint(IP->getParent(), IP);
326 
327  // Initialize the map pointer and load the current head of the shadow stack.
328  Instruction *CurrentHead =
329  AtEntry.CreateLoad(StackEntryTy->getPointerTo(), Head, "gc_currhead");
330  Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
331  StackEntry, 0, 1, "gc_frame.map");
332  AtEntry.CreateStore(FrameMap, EntryMapPtr);
333 
334  // After all the allocas...
335  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
336  // For each root, find the corresponding slot in the aggregate...
337  Value *SlotPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
338  StackEntry, 1 + I, "gc_root");
339 
340  // And use it in lieu of the alloca.
341  AllocaInst *OriginalAlloca = Roots[I].second;
342  SlotPtr->takeName(OriginalAlloca);
343  OriginalAlloca->replaceAllUsesWith(SlotPtr);
344  }
345 
346  // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
347  // really necessary (the collector would never see the intermediate state at
348  // runtime), but it's nicer not to push the half-initialized entry onto the
349  // shadow stack.
350  while (isa<StoreInst>(IP))
351  ++IP;
352  AtEntry.SetInsertPoint(IP->getParent(), IP);
353 
354  // Push the entry onto the shadow stack.
355  Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
356  StackEntry, 0, 0, "gc_frame.next");
357  Instruction *NewHeadVal = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
358  StackEntry, 0, "gc_newhead");
359  AtEntry.CreateStore(CurrentHead, EntryNextPtr);
360  AtEntry.CreateStore(NewHeadVal, Head);
361 
362  // For each instruction that escapes...
363  EscapeEnumerator EE(F, "gc_cleanup", /*HandleExceptions=*/true,
364  DTU.hasValue() ? DTU.getPointer() : nullptr);
365  while (IRBuilder<> *AtExit = EE.Next()) {
366  // Pop the entry from the shadow stack. Don't reuse CurrentHead from
367  // AtEntry, since that would make the value live for the entire function.
368  Instruction *EntryNextPtr2 =
369  CreateGEP(Context, *AtExit, ConcreteStackEntryTy, StackEntry, 0, 0,
370  "gc_frame.next");
371  Value *SavedHead = AtExit->CreateLoad(StackEntryTy->getPointerTo(),
372  EntryNextPtr2, "gc_savedhead");
373  AtExit->CreateStore(SavedHead, Head);
374  }
375 
376  // Delete the original allocas (which are no longer used) and the intrinsic
377  // calls (which are no longer valid). Doing this last avoids invalidating
378  // iterators.
379  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
380  Roots[I].first->eraseFromParent();
381  Roots[I].second->eraseFromParent();
382  }
383 
384  Roots.clear();
385  return true;
386 }
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
Lowering
Shadow Stack GC Lowering
Definition: ShadowStackGCLowering.cpp:98
llvm
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
IntrinsicInst.h
llvm::EscapeEnumerator
EscapeEnumerator - This is a little algorithm to find all escape points from a function so that "fina...
Definition: EscapeEnumerator.h:29
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
Module.h
llvm::Optional
Definition: APInt.h:33
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ShadowStackGCLowering.cpp:49
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:278
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:286
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
GlobalValue.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::initializeShadowStackGCLoweringPass
void initializeShadowStackGCLoweringPass(PassRegistry &)
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
IP
Definition: NVPTXLowerArgs.cpp:166
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::createShadowStackGCLoweringPass
FunctionPass * createShadowStackGCLoweringPass()
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC.
Definition: ShadowStackGCLowering.cpp:100
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
Passes.h
BasicBlock.h
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE, "Shadow Stack GC Lowering", false, false) INITIALIZE_PASS_END(ShadowStackGCLowering
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:262
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
StringExtras.h
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:905
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:634
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:527
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
GlobalVariable.h
Casting.h
Function.h
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
Instructions.h
SmallVector.h
Dominators.h
EscapeEnumerator.h
DerivedTypes.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:377
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
Value.h
llvm::GCModuleInfo
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:152
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773