LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ShadowStackGC.cpp
Go to the documentation of this file.
1 //===-- ShadowStackGC.cpp - GC support for uncooperative targets ----------===//
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 implements lowering for the llvm.gc* intrinsics for targets that do
11 // not natively support them (which includes the C backend). Note that the code
12 // generated is not quite as efficient as algorithms which generate stack maps
13 // to identify roots.
14 //
15 // This pass implements the code transformation described in this paper:
16 // "Accurate Garbage Collection in an Uncooperative Environment"
17 // Fergus Henderson, ISMM, 2002
18 //
19 // In runtime/GC/SemiSpace.cpp is a prototype runtime which is compatible with
20 // ShadowStackGC.
21 //
22 // In order to support this particular transformation, all stack roots are
23 // coallocated in the stack. This allows a fully target-independent stack map
24 // while introducing only minor runtime overhead.
25 //
26 //===----------------------------------------------------------------------===//
27 
28 #define DEBUG_TYPE "shadowstackgc"
29 #include "llvm/CodeGen/GCs.h"
30 #include "llvm/ADT/StringExtras.h"
32 #include "llvm/IR/IRBuilder.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/Support/CallSite.h"
36 
37 using namespace llvm;
38 
39 namespace {
40 
41  class ShadowStackGC : public GCStrategy {
42  /// RootChain - This is the global linked-list that contains the chain of GC
43  /// roots.
44  GlobalVariable *Head;
45 
46  /// StackEntryTy - Abstract type of a link in the shadow stack.
47  ///
48  StructType *StackEntryTy;
49  StructType *FrameMapTy;
50 
51  /// Roots - GC roots in the current function. Each is a pair of the
52  /// intrinsic call and its corresponding alloca.
53  std::vector<std::pair<CallInst*,AllocaInst*> > Roots;
54 
55  public:
56  ShadowStackGC();
57 
58  bool initializeCustomLowering(Module &M);
59  bool performCustomLowering(Function &F);
60 
61  private:
62  bool IsNullValue(Value *V);
63  Constant *GetFrameMap(Function &F);
64  Type* GetConcreteStackEntryType(Function &F);
65  void CollectRoots(Function &F);
66  static GetElementPtrInst *CreateGEP(LLVMContext &Context,
67  IRBuilder<> &B, Value *BasePtr,
68  int Idx1, const char *Name);
69  static GetElementPtrInst *CreateGEP(LLVMContext &Context,
70  IRBuilder<> &B, Value *BasePtr,
71  int Idx1, int Idx2, const char *Name);
72  };
73 
74 }
75 
77 X("shadow-stack", "Very portable GC for uncooperative code generators");
78 
79 namespace {
80  /// EscapeEnumerator - This is a little algorithm to find all escape points
81  /// from a function so that "finally"-style code can be inserted. In addition
82  /// to finding the existing return and unwind instructions, it also (if
83  /// necessary) transforms any call instructions into invokes and sends them to
84  /// a landing pad.
85  ///
86  /// It's wrapped up in a state machine using the same transform C# uses for
87  /// 'yield return' enumerators, This transform allows it to be non-allocating.
88  class EscapeEnumerator {
89  Function &F;
90  const char *CleanupBBName;
91 
92  // State.
93  int State;
94  Function::iterator StateBB, StateE;
95  IRBuilder<> Builder;
96 
97  public:
98  EscapeEnumerator(Function &F, const char *N = "cleanup")
99  : F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {}
100 
101  IRBuilder<> *Next() {
102  switch (State) {
103  default:
104  return 0;
105 
106  case 0:
107  StateBB = F.begin();
108  StateE = F.end();
109  State = 1;
110 
111  case 1:
112  // Find all 'return', 'resume', and 'unwind' instructions.
113  while (StateBB != StateE) {
114  BasicBlock *CurBB = StateBB++;
115 
116  // Branches and invokes do not escape, only unwind, resume, and return
117  // do.
118  TerminatorInst *TI = CurBB->getTerminator();
119  if (!isa<ReturnInst>(TI) && !isa<ResumeInst>(TI))
120  continue;
121 
122  Builder.SetInsertPoint(TI->getParent(), TI);
123  return &Builder;
124  }
125 
126  State = 2;
127 
128  // Find all 'call' instructions.
130  for (Function::iterator BB = F.begin(),
131  E = F.end(); BB != E; ++BB)
132  for (BasicBlock::iterator II = BB->begin(),
133  EE = BB->end(); II != EE; ++II)
134  if (CallInst *CI = dyn_cast<CallInst>(II))
135  if (!CI->getCalledFunction() ||
136  !CI->getCalledFunction()->getIntrinsicID())
137  Calls.push_back(CI);
138 
139  if (Calls.empty())
140  return 0;
141 
142  // Create a cleanup block.
143  LLVMContext &C = F.getContext();
144  BasicBlock *CleanupBB = BasicBlock::Create(C, CleanupBBName, &F);
146  Type::getInt32Ty(C), NULL);
147  Constant *PersFn =
148  F.getParent()->
149  getOrInsertFunction("__gcc_personality_v0",
151  LandingPadInst *LPad = LandingPadInst::Create(ExnTy, PersFn, 1,
152  "cleanup.lpad",
153  CleanupBB);
154  LPad->setCleanup(true);
155  ResumeInst *RI = ResumeInst::Create(LPad, CleanupBB);
156 
157  // Transform the 'call' instructions into 'invoke's branching to the
158  // cleanup block. Go in reverse order to make prettier BB names.
160  for (unsigned I = Calls.size(); I != 0; ) {
161  CallInst *CI = cast<CallInst>(Calls[--I]);
162 
163  // Split the basic block containing the function call.
164  BasicBlock *CallBB = CI->getParent();
165  BasicBlock *NewBB =
166  CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont");
167 
168  // Remove the unconditional branch inserted at the end of CallBB.
169  CallBB->getInstList().pop_back();
170  NewBB->getInstList().remove(CI);
171 
172  // Create a new invoke instruction.
173  Args.clear();
174  CallSite CS(CI);
175  Args.append(CS.arg_begin(), CS.arg_end());
176 
178  NewBB, CleanupBB,
179  Args, CI->getName(), CallBB);
180  II->setCallingConv(CI->getCallingConv());
181  II->setAttributes(CI->getAttributes());
182  CI->replaceAllUsesWith(II);
183  delete CI;
184  }
185 
186  Builder.SetInsertPoint(RI->getParent(), RI);
187  return &Builder;
188  }
189  }
190  };
191 }
192 
193 // -----------------------------------------------------------------------------
194 
196 
197 ShadowStackGC::ShadowStackGC() : Head(0), StackEntryTy(0) {
198  InitRoots = true;
199  CustomRoots = true;
200 }
201 
202 Constant *ShadowStackGC::GetFrameMap(Function &F) {
203  // doInitialization creates the abstract type of this value.
204  Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
205 
206  // Truncate the ShadowStackDescriptor if some metadata is null.
207  unsigned NumMeta = 0;
209  for (unsigned I = 0; I != Roots.size(); ++I) {
210  Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
211  if (!C->isNullValue())
212  NumMeta = I + 1;
213  Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
214  }
215  Metadata.resize(NumMeta);
216 
217  Type *Int32Ty = Type::getInt32Ty(F.getContext());
218 
219  Constant *BaseElts[] = {
220  ConstantInt::get(Int32Ty, Roots.size(), false),
221  ConstantInt::get(Int32Ty, NumMeta, false),
222  };
223 
224  Constant *DescriptorElts[] = {
225  ConstantStruct::get(FrameMapTy, BaseElts),
226  ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)
227  };
228 
229  Type *EltTys[] = { DescriptorElts[0]->getType(),DescriptorElts[1]->getType()};
230  StructType *STy = StructType::create(EltTys, "gc_map."+utostr(NumMeta));
231 
232  Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
233 
234  // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
235  // that, short of multithreaded LLVM, it should be safe; all that is
236  // necessary is that a simple Module::iterator loop not be invalidated.
237  // Appending to the GlobalVariable list is safe in that sense.
238  //
239  // All of the output passes emit globals last. The ExecutionEngine
240  // explicitly supports adding globals to the module after
241  // initialization.
242  //
243  // Still, if it isn't deemed acceptable, then this transformation needs
244  // to be a ModulePass (which means it cannot be in the 'llc' pipeline
245  // (which uses a FunctionPassManager (which segfaults (not asserts) if
246  // provided a ModulePass))).
247  Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
248  GlobalVariable::InternalLinkage,
249  FrameMap, "__gc_" + F.getName());
250 
251  Constant *GEPIndices[2] = {
252  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
253  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)
254  };
255  return ConstantExpr::getGetElementPtr(GV, GEPIndices);
256 }
257 
258 Type* ShadowStackGC::GetConcreteStackEntryType(Function &F) {
259  // doInitialization creates the generic version of this type.
260  std::vector<Type*> EltTys;
261  EltTys.push_back(StackEntryTy);
262  for (size_t I = 0; I != Roots.size(); I++)
263  EltTys.push_back(Roots[I].second->getAllocatedType());
264 
265  return StructType::create(EltTys, "gc_stackentry."+F.getName().str());
266 }
267 
268 /// doInitialization - If this module uses the GC intrinsics, find them now. If
269 /// not, exit fast.
270 bool ShadowStackGC::initializeCustomLowering(Module &M) {
271  // struct FrameMap {
272  // int32_t NumRoots; // Number of roots in stack frame.
273  // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
274  // void *Meta[]; // May be absent for roots without metadata.
275  // };
276  std::vector<Type*> EltTys;
277  // 32 bits is ok up to a 32GB stack frame. :)
278  EltTys.push_back(Type::getInt32Ty(M.getContext()));
279  // Specifies length of variable length array.
280  EltTys.push_back(Type::getInt32Ty(M.getContext()));
281  FrameMapTy = StructType::create(EltTys, "gc_map");
282  PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
283 
284  // struct StackEntry {
285  // ShadowStackEntry *Next; // Caller's stack entry.
286  // FrameMap *Map; // Pointer to constant FrameMap.
287  // void *Roots[]; // Stack roots (in-place array, so we pretend).
288  // };
289 
290  StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
291 
292  EltTys.clear();
293  EltTys.push_back(PointerType::getUnqual(StackEntryTy));
294  EltTys.push_back(FrameMapPtrTy);
295  StackEntryTy->setBody(EltTys);
296  PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
297 
298  // Get the root chain if it already exists.
299  Head = M.getGlobalVariable("llvm_gc_root_chain");
300  if (!Head) {
301  // If the root chain does not exist, insert a new one with linkonce
302  // linkage!
303  Head = new GlobalVariable(M, StackEntryPtrTy, false,
304  GlobalValue::LinkOnceAnyLinkage,
305  Constant::getNullValue(StackEntryPtrTy),
306  "llvm_gc_root_chain");
307  } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
308  Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
309  Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
310  }
311 
312  return true;
313 }
314 
315 bool ShadowStackGC::IsNullValue(Value *V) {
316  if (Constant *C = dyn_cast<Constant>(V))
317  return C->isNullValue();
318  return false;
319 }
320 
321 void ShadowStackGC::CollectRoots(Function &F) {
322  // FIXME: Account for original alignment. Could fragment the root array.
323  // Approach 1: Null initialize empty slots at runtime. Yuck.
324  // Approach 2: Emit a map of the array instead of just a count.
325 
326  assert(Roots.empty() && "Not cleaned up?");
327 
329 
330  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
331  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
332  if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
333  if (Function *F = CI->getCalledFunction())
334  if (F->getIntrinsicID() == Intrinsic::gcroot) {
335  std::pair<CallInst*, AllocaInst*> Pair = std::make_pair(
336  CI, cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
337  if (IsNullValue(CI->getArgOperand(1)))
338  Roots.push_back(Pair);
339  else
340  MetaRoots.push_back(Pair);
341  }
342 
343  // Number roots with metadata (usually empty) at the beginning, so that the
344  // FrameMap::Meta array can be elided.
345  Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
346 }
347 
349 ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr,
350  int Idx, int Idx2, const char *Name) {
351  Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0),
352  ConstantInt::get(Type::getInt32Ty(Context), Idx),
353  ConstantInt::get(Type::getInt32Ty(Context), Idx2) };
354  Value* Val = B.CreateGEP(BasePtr, Indices, Name);
355 
356  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
357 
358  return dyn_cast<GetElementPtrInst>(Val);
359 }
360 
362 ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr,
363  int Idx, const char *Name) {
364  Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0),
365  ConstantInt::get(Type::getInt32Ty(Context), Idx) };
366  Value *Val = B.CreateGEP(BasePtr, Indices, Name);
367 
368  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
369 
370  return dyn_cast<GetElementPtrInst>(Val);
371 }
372 
373 /// runOnFunction - Insert code to maintain the shadow stack.
374 bool ShadowStackGC::performCustomLowering(Function &F) {
375  LLVMContext &Context = F.getContext();
376 
377  // Find calls to llvm.gcroot.
378  CollectRoots(F);
379 
380  // If there are no roots in this function, then there is no need to add a
381  // stack map entry for it.
382  if (Roots.empty())
383  return false;
384 
385  // Build the constant map and figure the type of the shadow stack entry.
386  Value *FrameMap = GetFrameMap(F);
387  Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
388 
389  // Build the shadow stack entry at the very start of the function.
391  IRBuilder<> AtEntry(IP->getParent(), IP);
392 
393  Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, 0,
394  "gc_frame");
395 
396  while (isa<AllocaInst>(IP)) ++IP;
397  AtEntry.SetInsertPoint(IP->getParent(), IP);
398 
399  // Initialize the map pointer and load the current head of the shadow stack.
400  Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead");
401  Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, StackEntry,
402  0,1,"gc_frame.map");
403  AtEntry.CreateStore(FrameMap, EntryMapPtr);
404 
405  // After all the allocas...
406  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
407  // For each root, find the corresponding slot in the aggregate...
408  Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root");
409 
410  // And use it in lieu of the alloca.
411  AllocaInst *OriginalAlloca = Roots[I].second;
412  SlotPtr->takeName(OriginalAlloca);
413  OriginalAlloca->replaceAllUsesWith(SlotPtr);
414  }
415 
416  // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
417  // really necessary (the collector would never see the intermediate state at
418  // runtime), but it's nicer not to push the half-initialized entry onto the
419  // shadow stack.
420  while (isa<StoreInst>(IP)) ++IP;
421  AtEntry.SetInsertPoint(IP->getParent(), IP);
422 
423  // Push the entry onto the shadow stack.
424  Instruction *EntryNextPtr = CreateGEP(Context, AtEntry,
425  StackEntry,0,0,"gc_frame.next");
426  Instruction *NewHeadVal = CreateGEP(Context, AtEntry,
427  StackEntry, 0, "gc_newhead");
428  AtEntry.CreateStore(CurrentHead, EntryNextPtr);
429  AtEntry.CreateStore(NewHeadVal, Head);
430 
431  // For each instruction that escapes...
432  EscapeEnumerator EE(F, "gc_cleanup");
433  while (IRBuilder<> *AtExit = EE.Next()) {
434  // Pop the entry from the shadow stack. Don't reuse CurrentHead from
435  // AtEntry, since that would make the value live for the entire function.
436  Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0,
437  "gc_frame.next");
438  Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead");
439  AtExit->CreateStore(SavedHead, Head);
440  }
441 
442  // Delete the original allocas (which are no longer used) and the intrinsic
443  // calls (which are no longer valid). Doing this last avoids invalidating
444  // iterators.
445  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
446  Roots[I].first->eraseFromParent();
447  Roots[I].second->eraseFromParent();
448  }
449 
450  Roots.clear();
451  return true;
452 }
Value * CreateGEP(Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Definition: IRBuilder.h:931
const Value * getCalledValue() const
void setAttributes(const AttributeSet &Attrs)
LLVMContext & getContext() const
Definition: Function.cpp:167
void pop_back()
Definition: ilist.h:559
The main container class for the LLVM Intermediate Representation.
Definition: Module.h:112
iterator end()
Definition: Function.h:397
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:266
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:181
F(f)
const GlobalVariable * getGlobalVariable(StringRef Name, bool AllowInternal=false) const
Definition: Module.h:355
StringRef getName() const
Definition: Value.cpp:167
iterator begin()
Definition: BasicBlock.h:193
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:421
void setCleanup(bool V)
setCleanup - Indicate that this landingpad instruction is a cleanup.
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
Definition: SmallVector.h:56
static LandingPadInst * Create(Type *RetTy, Value *PersonalityFn, unsigned NumReservedClauses, const Twine &NameStr="", Instruction *InsertBefore=0)
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
Definition: Type.cpp:361
static std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:88
void replaceAllUsesWith(Value *V)
Definition: Value.cpp:303
void takeName(Value *V)
Definition: Value.cpp:239
iterator begin()
Definition: Function.h:395
LLVM Basic Block Representation.
Definition: BasicBlock.h:72
Type * Int32Ty
unsigned getIntrinsicID() const LLVM_READONLY
Definition: Function.cpp:371
LLVM Constant Representation.
Definition: Constant.h:41
static InvokeInst * Create(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr="", Instruction *InsertBefore=0)
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:214
void append(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:445
void linkShadowStackGC()
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:284
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
Definition: Type.cpp:405
Type * getType() const
Definition: Value.h:111
Value * stripPointerCasts()
Strips off any unneeded pointer casts, all-zero GEPs and aliases from the specified value...
Definition: Value.cpp:385
Function * getCalledFunction() const
const BasicBlock & getEntryBlock() const
Definition: Function.h:380
bool isNullValue() const
Definition: Constants.cpp:75
Value * getArgOperand(unsigned i) const
const AttributeSet & getAttributes() const
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:241
#define I(x, y, z)
Definition: MD5.cpp:54
#define N
TerminatorInst * getTerminator()
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void resize(unsigned N)
Definition: SmallVector.h:401
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=0, BasicBlock *InsertBefore=0)
Creates a new BasicBlock.
Definition: BasicBlock.h:109
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:298
Module * getParent()
Definition: GlobalValue.h:286
LLVM Value Representation.
Definition: Value.h:66
void setCallingConv(CallingConv::ID CC)
CallingConv::ID getCallingConv() const
NodeTy * remove(iterator &IT)
Definition: ilist.h:435
static ResumeInst * Create(Value *Exn, Instruction *InsertBefore=0)
static RegisterPass< NVPTXAllocaHoisting > X("alloca-hoisting","Hoisting alloca instructions in non-entry ""blocks to the entry block")
const BasicBlock * getParent() const
Definition: Instruction.h:52
LLVMContext & getContext() const
Definition: Module.h:249