LLVM  6.0.0svn
ShadowStackGCLowering.cpp
Go to the documentation of this file.
1 //===- ShadowStackGCLowering.cpp - Custom lowering for shadow-stack gc ----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains the custom lowering code required by the shadow-stack GC
11 // strategy.
12 //
13 // This pass implements the code transformation described in this paper:
14 // "Accurate Garbage Collection in an Uncooperative Environment"
15 // Fergus Henderson, ISMM, 2002
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/ADT/SmallVector.h"
20 #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/Function.h"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/GlobalVariable.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/Intrinsics.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/Casting.h"
39 #include <cassert>
40 #include <cstddef>
41 #include <string>
42 #include <utility>
43 #include <vector>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "shadow-stack-gc-lowering"
48 
49 namespace {
50 
51 class ShadowStackGCLowering : public FunctionPass {
52  /// RootChain - This is the global linked-list that contains the chain of GC
53  /// roots.
54  GlobalVariable *Head = nullptr;
55 
56  /// StackEntryTy - Abstract type of a link in the shadow stack.
57  StructType *StackEntryTy = nullptr;
58  StructType *FrameMapTy = nullptr;
59 
60  /// Roots - GC roots in the current function. Each is a pair of the
61  /// intrinsic call and its corresponding alloca.
62  std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
63 
64 public:
65  static char ID;
66 
67  ShadowStackGCLowering();
68 
69  bool doInitialization(Module &M) override;
70  bool runOnFunction(Function &F) override;
71 
72 private:
73  bool IsNullValue(Value *V);
74  Constant *GetFrameMap(Function &F);
75  Type *GetConcreteStackEntryType(Function &F);
76  void CollectRoots(Function &F);
77 
78  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
79  Type *Ty, Value *BasePtr, int Idx1,
80  const char *Name);
81  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
82  Type *Ty, Value *BasePtr, int Idx1, int Idx2,
83  const char *Name);
84 };
85 
86 } // end anonymous namespace
87 
89 
90 INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
91  "Shadow Stack GC Lowering", false, false)
93 INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
94  "Shadow Stack GC Lowering", false, false)
95 
96 FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
97 
98 ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
100 }
101 
102 Constant *ShadowStackGCLowering::GetFrameMap(Function &F) {
103  // doInitialization creates the abstract type of this value.
104  Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
105 
106  // Truncate the ShadowStackDescriptor if some metadata is null.
107  unsigned NumMeta = 0;
109  for (unsigned I = 0; I != Roots.size(); ++I) {
110  Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
111  if (!C->isNullValue())
112  NumMeta = I + 1;
113  Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
114  }
115  Metadata.resize(NumMeta);
116 
118 
119  Constant *BaseElts[] = {
120  ConstantInt::get(Int32Ty, Roots.size(), false),
121  ConstantInt::get(Int32Ty, NumMeta, false),
122  };
123 
124  Constant *DescriptorElts[] = {
125  ConstantStruct::get(FrameMapTy, BaseElts),
126  ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
127 
128  Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
129  StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
130 
131  Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
132 
133  // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
134  // that, short of multithreaded LLVM, it should be safe; all that is
135  // necessary is that a simple Module::iterator loop not be invalidated.
136  // Appending to the GlobalVariable list is safe in that sense.
137  //
138  // All of the output passes emit globals last. The ExecutionEngine
139  // explicitly supports adding globals to the module after
140  // initialization.
141  //
142  // Still, if it isn't deemed acceptable, then this transformation needs
143  // to be a ModulePass (which means it cannot be in the 'llc' pipeline
144  // (which uses a FunctionPassManager (which segfaults (not asserts) if
145  // provided a ModulePass))).
146  Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
148  "__gc_" + F.getName());
149 
150  Constant *GEPIndices[2] = {
153  return ConstantExpr::getGetElementPtr(FrameMap->getType(), GV, GEPIndices);
154 }
155 
156 Type *ShadowStackGCLowering::GetConcreteStackEntryType(Function &F) {
157  // doInitialization creates the generic version of this type.
158  std::vector<Type *> EltTys;
159  EltTys.push_back(StackEntryTy);
160  for (size_t I = 0; I != Roots.size(); I++)
161  EltTys.push_back(Roots[I].second->getAllocatedType());
162 
163  return StructType::create(EltTys, ("gc_stackentry." + F.getName()).str());
164 }
165 
166 /// doInitialization - If this module uses the GC intrinsics, find them now. If
167 /// not, exit fast.
168 bool ShadowStackGCLowering::doInitialization(Module &M) {
169  bool Active = false;
170  for (Function &F : M) {
171  if (F.hasGC() && F.getGC() == std::string("shadow-stack")) {
172  Active = true;
173  break;
174  }
175  }
176  if (!Active)
177  return false;
178 
179  // struct FrameMap {
180  // int32_t NumRoots; // Number of roots in stack frame.
181  // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
182  // void *Meta[]; // May be absent for roots without metadata.
183  // };
184  std::vector<Type *> EltTys;
185  // 32 bits is ok up to a 32GB stack frame. :)
186  EltTys.push_back(Type::getInt32Ty(M.getContext()));
187  // Specifies length of variable length array.
188  EltTys.push_back(Type::getInt32Ty(M.getContext()));
189  FrameMapTy = StructType::create(EltTys, "gc_map");
190  PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
191 
192  // struct StackEntry {
193  // ShadowStackEntry *Next; // Caller's stack entry.
194  // FrameMap *Map; // Pointer to constant FrameMap.
195  // void *Roots[]; // Stack roots (in-place array, so we pretend).
196  // };
197 
198  StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
199 
200  EltTys.clear();
201  EltTys.push_back(PointerType::getUnqual(StackEntryTy));
202  EltTys.push_back(FrameMapPtrTy);
203  StackEntryTy->setBody(EltTys);
204  PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
205 
206  // Get the root chain if it already exists.
207  Head = M.getGlobalVariable("llvm_gc_root_chain");
208  if (!Head) {
209  // If the root chain does not exist, insert a new one with linkonce
210  // linkage!
211  Head = new GlobalVariable(
212  M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
213  Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
214  } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
215  Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
216  Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
217  }
218 
219  return true;
220 }
221 
222 bool ShadowStackGCLowering::IsNullValue(Value *V) {
223  if (Constant *C = dyn_cast<Constant>(V))
224  return C->isNullValue();
225  return false;
226 }
227 
228 void ShadowStackGCLowering::CollectRoots(Function &F) {
229  // FIXME: Account for original alignment. Could fragment the root array.
230  // Approach 1: Null initialize empty slots at runtime. Yuck.
231  // Approach 2: Emit a map of the array instead of just a count.
232 
233  assert(Roots.empty() && "Not cleaned up?");
234 
236 
237  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
238  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
239  if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
240  if (Function *F = CI->getCalledFunction())
241  if (F->getIntrinsicID() == Intrinsic::gcroot) {
242  std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
243  CI,
244  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
245  if (IsNullValue(CI->getArgOperand(1)))
246  Roots.push_back(Pair);
247  else
248  MetaRoots.push_back(Pair);
249  }
250 
251  // Number roots with metadata (usually empty) at the beginning, so that the
252  // FrameMap::Meta array can be elided.
253  Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
254 }
255 
256 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
257  IRBuilder<> &B, Type *Ty,
258  Value *BasePtr, int Idx,
259  int Idx2,
260  const char *Name) {
261  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
262  ConstantInt::get(Type::getInt32Ty(Context), Idx),
263  ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
264  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
265 
266  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
267 
268  return dyn_cast<GetElementPtrInst>(Val);
269 }
270 
271 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
272  IRBuilder<> &B, Type *Ty, Value *BasePtr,
273  int Idx, const char *Name) {
274  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
275  ConstantInt::get(Type::getInt32Ty(Context), Idx)};
276  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
277 
278  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
279 
280  return dyn_cast<GetElementPtrInst>(Val);
281 }
282 
283 /// runOnFunction - Insert code to maintain the shadow stack.
285  // Quick exit for functions that do not use the shadow stack GC.
286  if (!F.hasGC() ||
287  F.getGC() != std::string("shadow-stack"))
288  return false;
289 
290  LLVMContext &Context = F.getContext();
291 
292  // Find calls to llvm.gcroot.
293  CollectRoots(F);
294 
295  // If there are no roots in this function, then there is no need to add a
296  // stack map entry for it.
297  if (Roots.empty())
298  return false;
299 
300  // Build the constant map and figure the type of the shadow stack entry.
301  Value *FrameMap = GetFrameMap(F);
302  Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
303 
304  // Build the shadow stack entry at the very start of the function.
306  IRBuilder<> AtEntry(IP->getParent(), IP);
307 
308  Instruction *StackEntry =
309  AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
310 
311  while (isa<AllocaInst>(IP))
312  ++IP;
313  AtEntry.SetInsertPoint(IP->getParent(), IP);
314 
315  // Initialize the map pointer and load the current head of the shadow stack.
316  Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead");
317  Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
318  StackEntry, 0, 1, "gc_frame.map");
319  AtEntry.CreateStore(FrameMap, EntryMapPtr);
320 
321  // After all the allocas...
322  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
323  // For each root, find the corresponding slot in the aggregate...
324  Value *SlotPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
325  StackEntry, 1 + I, "gc_root");
326 
327  // And use it in lieu of the alloca.
328  AllocaInst *OriginalAlloca = Roots[I].second;
329  SlotPtr->takeName(OriginalAlloca);
330  OriginalAlloca->replaceAllUsesWith(SlotPtr);
331  }
332 
333  // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
334  // really necessary (the collector would never see the intermediate state at
335  // runtime), but it's nicer not to push the half-initialized entry onto the
336  // shadow stack.
337  while (isa<StoreInst>(IP))
338  ++IP;
339  AtEntry.SetInsertPoint(IP->getParent(), IP);
340 
341  // Push the entry onto the shadow stack.
342  Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
343  StackEntry, 0, 0, "gc_frame.next");
344  Instruction *NewHeadVal = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
345  StackEntry, 0, "gc_newhead");
346  AtEntry.CreateStore(CurrentHead, EntryNextPtr);
347  AtEntry.CreateStore(NewHeadVal, Head);
348 
349  // For each instruction that escapes...
350  EscapeEnumerator EE(F, "gc_cleanup");
351  while (IRBuilder<> *AtExit = EE.Next()) {
352  // Pop the entry from the shadow stack. Don't reuse CurrentHead from
353  // AtEntry, since that would make the value live for the entire function.
354  Instruction *EntryNextPtr2 =
355  CreateGEP(Context, *AtExit, ConcreteStackEntryTy, StackEntry, 0, 0,
356  "gc_frame.next");
357  Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead");
358  AtExit->CreateStore(SavedHead, Head);
359  }
360 
361  // Delete the original allocas (which are no longer used) and the intrinsic
362  // calls (which are no longer valid). Doing this last avoids invalidating
363  // iterators.
364  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
365  Roots[I].first->eraseFromParent();
366  Roots[I].second->eraseFromParent();
367  }
368 
369  Roots.clear();
370  return true;
371 }
uint64_t CallInst * C
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant *> IdxList, bool InBounds=false, Optional< unsigned > InRangeIndex=None, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1115
Shadow Stack GC Lowering
iterator end()
Definition: Function.h:590
void initializeShadowStackGCLoweringPass(PassRegistry &)
F(f)
FunctionPass * createShadowStackGCLoweringPass()
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC...
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:888
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
EscapeEnumerator - This is a little algorithm to find all escape points from a function so that "fina...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Class to represent struct types.
Definition: DerivedTypes.h:201
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:154
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:86
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
const std::string & getGC() const
Definition: Function.cpp:444
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE, "Shadow Stack GC Lowering", false, false) INITIALIZE_PASS_END(ShadowStackGCLowering
void setBody(ArrayRef< Type *> Elements, bool isPacked=false)
Specify a body for an opaque identified type.
Definition: Type.cpp:356
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
iterator begin()
Definition: Function.h:588
Class to represent pointers.
Definition: DerivedTypes.h:467
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1678
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:949
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1227
Iterator for intrusive lists based on ilist_node.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the generic address space (address sp...
Definition: DerivedTypes.h:482
#define DEBUG_TYPE
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Keep one copy of function when linking (inline)
Definition: GlobalValue.h:51
Module.h This file contains the declarations for the Module class.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:174
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:175
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:286
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
#define I(x, y, z)
Definition: MD5.cpp:58
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:568
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:556
LLVM Value Representation.
Definition: Value.h:73
static StructType * create(LLVMContext &Context, StringRef Name)
This creates an identified struct.
Definition: Type.cpp:424
std::vector< uint32_t > Metadata
PAL metadata represented as a vector.
IntegerType * Int32Ty
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
an instruction to allocate memory on the stack
Definition: Instructions.h:60
void resize(size_type N)
Definition: SmallVector.h:355