LLVM API Documentation
00001 //===-- ShadowStackGC.cpp - GC support for uncooperative targets ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements lowering for the llvm.gc* intrinsics for targets that do 00011 // not natively support them (which includes the C backend). Note that the code 00012 // generated is not quite as efficient as algorithms which generate stack maps 00013 // to identify roots. 00014 // 00015 // This pass implements the code transformation described in this paper: 00016 // "Accurate Garbage Collection in an Uncooperative Environment" 00017 // Fergus Henderson, ISMM, 2002 00018 // 00019 // In runtime/GC/SemiSpace.cpp is a prototype runtime which is compatible with 00020 // ShadowStackGC. 00021 // 00022 // In order to support this particular transformation, all stack roots are 00023 // coallocated in the stack. This allows a fully target-independent stack map 00024 // while introducing only minor runtime overhead. 00025 // 00026 //===----------------------------------------------------------------------===// 00027 00028 #define DEBUG_TYPE "shadowstackgc" 00029 #include "llvm/CodeGen/GCs.h" 00030 #include "llvm/ADT/StringExtras.h" 00031 #include "llvm/CodeGen/GCStrategy.h" 00032 #include "llvm/IntrinsicInst.h" 00033 #include "llvm/Module.h" 00034 #include "llvm/Support/Compiler.h" 00035 #include "llvm/Support/IRBuilder.h" 00036 00037 using namespace llvm; 00038 00039 namespace { 00040 00041 class VISIBILITY_HIDDEN ShadowStackGC : public GCStrategy { 00042 /// RootChain - This is the global linked-list that contains the chain of GC 00043 /// roots. 00044 GlobalVariable *Head; 00045 00046 /// StackEntryTy - Abstract type of a link in the shadow stack. 00047 /// 00048 const StructType *StackEntryTy; 00049 00050 /// Roots - GC roots in the current function. Each is a pair of the 00051 /// intrinsic call and its corresponding alloca. 00052 std::vector<std::pair<CallInst*,AllocaInst*> > Roots; 00053 00054 public: 00055 ShadowStackGC(); 00056 00057 bool initializeCustomLowering(Module &M); 00058 bool performCustomLowering(Function &F); 00059 00060 private: 00061 bool IsNullValue(Value *V); 00062 Constant *GetFrameMap(Function &F); 00063 const Type* GetConcreteStackEntryType(Function &F); 00064 void CollectRoots(Function &F); 00065 static GetElementPtrInst *CreateGEP(LLVMContext &Context, 00066 IRBuilder<> &B, Value *BasePtr, 00067 int Idx1, const char *Name); 00068 static GetElementPtrInst *CreateGEP(LLVMContext &Context, 00069 IRBuilder<> &B, Value *BasePtr, 00070 int Idx1, int Idx2, const char *Name); 00071 }; 00072 00073 } 00074 00075 static GCRegistry::Add<ShadowStackGC> 00076 X("shadow-stack", "Very portable GC for uncooperative code generators"); 00077 00078 namespace { 00079 /// EscapeEnumerator - This is a little algorithm to find all escape points 00080 /// from a function so that "finally"-style code can be inserted. In addition 00081 /// to finding the existing return and unwind instructions, it also (if 00082 /// necessary) transforms any call instructions into invokes and sends them to 00083 /// a landing pad. 00084 /// 00085 /// It's wrapped up in a state machine using the same transform C# uses for 00086 /// 'yield return' enumerators, This transform allows it to be non-allocating. 00087 class VISIBILITY_HIDDEN EscapeEnumerator { 00088 Function &F; 00089 const char *CleanupBBName; 00090 00091 // State. 00092 int State; 00093 Function::iterator StateBB, StateE; 00094 IRBuilder<> Builder; 00095 00096 public: 00097 EscapeEnumerator(Function &F, const char *N = "cleanup") 00098 : F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {} 00099 00100 IRBuilder<> *Next() { 00101 switch (State) { 00102 default: 00103 return 0; 00104 00105 case 0: 00106 StateBB = F.begin(); 00107 StateE = F.end(); 00108 State = 1; 00109 00110 case 1: 00111 // Find all 'return' and 'unwind' instructions. 00112 while (StateBB != StateE) { 00113 BasicBlock *CurBB = StateBB++; 00114 00115 // Branches and invokes do not escape, only unwind and return do. 00116 TerminatorInst *TI = CurBB->getTerminator(); 00117 if (!isa<UnwindInst>(TI) && !isa<ReturnInst>(TI)) 00118 continue; 00119 00120 Builder.SetInsertPoint(TI->getParent(), TI); 00121 return &Builder; 00122 } 00123 00124 State = 2; 00125 00126 // Find all 'call' instructions. 00127 SmallVector<Instruction*,16> Calls; 00128 for (Function::iterator BB = F.begin(), 00129 E = F.end(); BB != E; ++BB) 00130 for (BasicBlock::iterator II = BB->begin(), 00131 EE = BB->end(); II != EE; ++II) 00132 if (CallInst *CI = dyn_cast<CallInst>(II)) 00133 if (!CI->getCalledFunction() || 00134 !CI->getCalledFunction()->getIntrinsicID()) 00135 Calls.push_back(CI); 00136 00137 if (Calls.empty()) 00138 return 0; 00139 00140 // Create a cleanup block. 00141 BasicBlock *CleanupBB = BasicBlock::Create(F.getContext(), 00142 CleanupBBName, &F); 00143 UnwindInst *UI = new UnwindInst(F.getContext(), CleanupBB); 00144 00145 // Transform the 'call' instructions into 'invoke's branching to the 00146 // cleanup block. Go in reverse order to make prettier BB names. 00147 SmallVector<Value*,16> Args; 00148 for (unsigned I = Calls.size(); I != 0; ) { 00149 CallInst *CI = cast<CallInst>(Calls[--I]); 00150 00151 // Split the basic block containing the function call. 00152 BasicBlock *CallBB = CI->getParent(); 00153 BasicBlock *NewBB = 00154 CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont"); 00155 00156 // Remove the unconditional branch inserted at the end of CallBB. 00157 CallBB->getInstList().pop_back(); 00158 NewBB->getInstList().remove(CI); 00159 00160 // Create a new invoke instruction. 00161 Args.clear(); 00162 Args.append(CI->op_begin() + 1, CI->op_end()); 00163 00164 InvokeInst *II = InvokeInst::Create(CI->getOperand(0), 00165 NewBB, CleanupBB, 00166 Args.begin(), Args.end(), 00167 CI->getName(), CallBB); 00168 II->setCallingConv(CI->getCallingConv()); 00169 II->setAttributes(CI->getAttributes()); 00170 CI->replaceAllUsesWith(II); 00171 delete CI; 00172 } 00173 00174 Builder.SetInsertPoint(UI->getParent(), UI); 00175 return &Builder; 00176 } 00177 } 00178 }; 00179 } 00180 00181 // ----------------------------------------------------------------------------- 00182 00183 void llvm::linkShadowStackGC() { } 00184 00185 ShadowStackGC::ShadowStackGC() : Head(0), StackEntryTy(0) { 00186 InitRoots = true; 00187 CustomRoots = true; 00188 } 00189 00190 Constant *ShadowStackGC::GetFrameMap(Function &F) { 00191 // doInitialization creates the abstract type of this value. 00192 Type *VoidPtr = PointerType::getUnqual(Type::getInt8Ty(F.getContext())); 00193 00194 // Truncate the ShadowStackDescriptor if some metadata is null. 00195 unsigned NumMeta = 0; 00196 SmallVector<Constant*,16> Metadata; 00197 for (unsigned I = 0; I != Roots.size(); ++I) { 00198 Constant *C = cast<Constant>(Roots[I].first->getOperand(2)); 00199 if (!C->isNullValue()) 00200 NumMeta = I + 1; 00201 Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr)); 00202 } 00203 00204 Constant *BaseElts[] = { 00205 ConstantInt::get(Type::getInt32Ty(F.getContext()), Roots.size(), false), 00206 ConstantInt::get(Type::getInt32Ty(F.getContext()), NumMeta, false), 00207 }; 00208 00209 Constant *DescriptorElts[] = { 00210 ConstantStruct::get(F.getContext(), BaseElts, 2), 00211 ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), 00212 Metadata.begin(), NumMeta) 00213 }; 00214 00215 Constant *FrameMap = ConstantStruct::get(F.getContext(), DescriptorElts, 2); 00216 00217 std::string TypeName("gc_map."); 00218 TypeName += utostr(NumMeta); 00219 F.getParent()->addTypeName(TypeName, FrameMap->getType()); 00220 00221 // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems 00222 // that, short of multithreaded LLVM, it should be safe; all that is 00223 // necessary is that a simple Module::iterator loop not be invalidated. 00224 // Appending to the GlobalVariable list is safe in that sense. 00225 // 00226 // All of the output passes emit globals last. The ExecutionEngine 00227 // explicitly supports adding globals to the module after 00228 // initialization. 00229 // 00230 // Still, if it isn't deemed acceptable, then this transformation needs 00231 // to be a ModulePass (which means it cannot be in the 'llc' pipeline 00232 // (which uses a FunctionPassManager (which segfaults (not asserts) if 00233 // provided a ModulePass))). 00234 Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true, 00235 GlobalVariable::InternalLinkage, 00236 FrameMap, "__gc_" + F.getName()); 00237 00238 Constant *GEPIndices[2] = { 00239 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0), 00240 ConstantInt::get(Type::getInt32Ty(F.getContext()), 0) 00241 }; 00242 return ConstantExpr::getGetElementPtr(GV, GEPIndices, 2); 00243 } 00244 00245 const Type* ShadowStackGC::GetConcreteStackEntryType(Function &F) { 00246 // doInitialization creates the generic version of this type. 00247 std::vector<const Type*> EltTys; 00248 EltTys.push_back(StackEntryTy); 00249 for (size_t I = 0; I != Roots.size(); I++) 00250 EltTys.push_back(Roots[I].second->getAllocatedType()); 00251 Type *Ty = StructType::get(F.getContext(), EltTys); 00252 00253 std::string TypeName("gc_stackentry."); 00254 TypeName += F.getName(); 00255 F.getParent()->addTypeName(TypeName, Ty); 00256 00257 return Ty; 00258 } 00259 00260 /// doInitialization - If this module uses the GC intrinsics, find them now. If 00261 /// not, exit fast. 00262 bool ShadowStackGC::initializeCustomLowering(Module &M) { 00263 // struct FrameMap { 00264 // int32_t NumRoots; // Number of roots in stack frame. 00265 // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots. 00266 // void *Meta[]; // May be absent for roots without metadata. 00267 // }; 00268 std::vector<const Type*> EltTys; 00269 // 32 bits is ok up to a 32GB stack frame. :) 00270 EltTys.push_back(Type::getInt32Ty(M.getContext())); 00271 // Specifies length of variable length array. 00272 EltTys.push_back(Type::getInt32Ty(M.getContext())); 00273 StructType *FrameMapTy = StructType::get(M.getContext(), EltTys); 00274 M.addTypeName("gc_map", FrameMapTy); 00275 PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy); 00276 00277 // struct StackEntry { 00278 // ShadowStackEntry *Next; // Caller's stack entry. 00279 // FrameMap *Map; // Pointer to constant FrameMap. 00280 // void *Roots[]; // Stack roots (in-place array, so we pretend). 00281 // }; 00282 OpaqueType *RecursiveTy = OpaqueType::get(M.getContext()); 00283 00284 EltTys.clear(); 00285 EltTys.push_back(PointerType::getUnqual(RecursiveTy)); 00286 EltTys.push_back(FrameMapPtrTy); 00287 PATypeHolder LinkTyH = StructType::get(M.getContext(), EltTys); 00288 00289 RecursiveTy->refineAbstractTypeTo(LinkTyH.get()); 00290 StackEntryTy = cast<StructType>(LinkTyH.get()); 00291 const PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy); 00292 M.addTypeName("gc_stackentry", LinkTyH.get()); // FIXME: Is this safe from 00293 // a FunctionPass? 00294 00295 // Get the root chain if it already exists. 00296 Head = M.getGlobalVariable("llvm_gc_root_chain"); 00297 if (!Head) { 00298 // If the root chain does not exist, insert a new one with linkonce 00299 // linkage! 00300 Head = new GlobalVariable(M, StackEntryPtrTy, false, 00301 GlobalValue::LinkOnceAnyLinkage, 00302 Constant::getNullValue(StackEntryPtrTy), 00303 "llvm_gc_root_chain"); 00304 } else if (Head->hasExternalLinkage() && Head->isDeclaration()) { 00305 Head->setInitializer(Constant::getNullValue(StackEntryPtrTy)); 00306 Head->setLinkage(GlobalValue::LinkOnceAnyLinkage); 00307 } 00308 00309 return true; 00310 } 00311 00312 bool ShadowStackGC::IsNullValue(Value *V) { 00313 if (Constant *C = dyn_cast<Constant>(V)) 00314 return C->isNullValue(); 00315 return false; 00316 } 00317 00318 void ShadowStackGC::CollectRoots(Function &F) { 00319 // FIXME: Account for original alignment. Could fragment the root array. 00320 // Approach 1: Null initialize empty slots at runtime. Yuck. 00321 // Approach 2: Emit a map of the array instead of just a count. 00322 00323 assert(Roots.empty() && "Not cleaned up?"); 00324 00325 SmallVector<std::pair<CallInst*,AllocaInst*>,16> MetaRoots; 00326 00327 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 00328 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) 00329 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 00330 if (Function *F = CI->getCalledFunction()) 00331 if (F->getIntrinsicID() == Intrinsic::gcroot) { 00332 std::pair<CallInst*,AllocaInst*> Pair = std::make_pair( 00333 CI, cast<AllocaInst>(CI->getOperand(1)->stripPointerCasts())); 00334 if (IsNullValue(CI->getOperand(2))) 00335 Roots.push_back(Pair); 00336 else 00337 MetaRoots.push_back(Pair); 00338 } 00339 00340 // Number roots with metadata (usually empty) at the beginning, so that the 00341 // FrameMap::Meta array can be elided. 00342 Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end()); 00343 } 00344 00345 GetElementPtrInst * 00346 ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 00347 int Idx, int Idx2, const char *Name) { 00348 Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 00349 ConstantInt::get(Type::getInt32Ty(Context), Idx), 00350 ConstantInt::get(Type::getInt32Ty(Context), Idx2) }; 00351 Value* Val = B.CreateGEP(BasePtr, Indices, Indices + 3, Name); 00352 00353 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 00354 00355 return dyn_cast<GetElementPtrInst>(Val); 00356 } 00357 00358 GetElementPtrInst * 00359 ShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 00360 int Idx, const char *Name) { 00361 Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 00362 ConstantInt::get(Type::getInt32Ty(Context), Idx) }; 00363 Value *Val = B.CreateGEP(BasePtr, Indices, Indices + 2, Name); 00364 00365 assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 00366 00367 return dyn_cast<GetElementPtrInst>(Val); 00368 } 00369 00370 /// runOnFunction - Insert code to maintain the shadow stack. 00371 bool ShadowStackGC::performCustomLowering(Function &F) { 00372 LLVMContext &Context = F.getContext(); 00373 00374 // Find calls to llvm.gcroot. 00375 CollectRoots(F); 00376 00377 // If there are no roots in this function, then there is no need to add a 00378 // stack map entry for it. 00379 if (Roots.empty()) 00380 return false; 00381 00382 // Build the constant map and figure the type of the shadow stack entry. 00383 Value *FrameMap = GetFrameMap(F); 00384 const Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F); 00385 00386 // Build the shadow stack entry at the very start of the function. 00387 BasicBlock::iterator IP = F.getEntryBlock().begin(); 00388 IRBuilder<> AtEntry(IP->getParent(), IP); 00389 00390 Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, 0, 00391 "gc_frame"); 00392 00393 while (isa<AllocaInst>(IP)) ++IP; 00394 AtEntry.SetInsertPoint(IP->getParent(), IP); 00395 00396 // Initialize the map pointer and load the current head of the shadow stack. 00397 Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead"); 00398 Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, StackEntry, 00399 0,1,"gc_frame.map"); 00400 AtEntry.CreateStore(FrameMap, EntryMapPtr); 00401 00402 // After all the allocas... 00403 for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 00404 // For each root, find the corresponding slot in the aggregate... 00405 Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root"); 00406 00407 // And use it in lieu of the alloca. 00408 AllocaInst *OriginalAlloca = Roots[I].second; 00409 SlotPtr->takeName(OriginalAlloca); 00410 OriginalAlloca->replaceAllUsesWith(SlotPtr); 00411 } 00412 00413 // Move past the original stores inserted by GCStrategy::InitRoots. This isn't 00414 // really necessary (the collector would never see the intermediate state at 00415 // runtime), but it's nicer not to push the half-initialized entry onto the 00416 // shadow stack. 00417 while (isa<StoreInst>(IP)) ++IP; 00418 AtEntry.SetInsertPoint(IP->getParent(), IP); 00419 00420 // Push the entry onto the shadow stack. 00421 Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, 00422 StackEntry,0,0,"gc_frame.next"); 00423 Instruction *NewHeadVal = CreateGEP(Context, AtEntry, 00424 StackEntry, 0, "gc_newhead"); 00425 AtEntry.CreateStore(CurrentHead, EntryNextPtr); 00426 AtEntry.CreateStore(NewHeadVal, Head); 00427 00428 // For each instruction that escapes... 00429 EscapeEnumerator EE(F, "gc_cleanup"); 00430 while (IRBuilder<> *AtExit = EE.Next()) { 00431 // Pop the entry from the shadow stack. Don't reuse CurrentHead from 00432 // AtEntry, since that would make the value live for the entire function. 00433 Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0, 00434 "gc_frame.next"); 00435 Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead"); 00436 AtExit->CreateStore(SavedHead, Head); 00437 } 00438 00439 // Delete the original allocas (which are no longer used) and the intrinsic 00440 // calls (which are no longer valid). Doing this last avoids invalidating 00441 // iterators. 00442 for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 00443 Roots[I].first->eraseFromParent(); 00444 Roots[I].second->eraseFromParent(); 00445 } 00446 00447 Roots.clear(); 00448 return true; 00449 }