ShadowStackGC.cpp revision 267010864e139781ef5949939e081c41f954de0a
15eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen//===-- ShadowStackGC.cpp - GC support for uncooperative targets ----------===// 28fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 38fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// The LLVM Compiler Infrastructure 48fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 58fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// This file is distributed under the University of Illinois Open Source 68fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// License. See LICENSE.TXT for details. 78fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 88fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen//===----------------------------------------------------------------------===// 98fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// This file implements lowering for the llvm.gc* intrinsics for targets that do 118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// not natively support them (which includes the C backend). Note that the code 125eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen// generated is not quite as efficient as algorithms which generate stack maps 138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// to identify roots. 148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 158fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// This pass implements the code transformation described in this paper: 168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// "Accurate Garbage Collection in an Uncooperative Environment" 178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// Fergus Henderson, ISMM, 2002 188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 198fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// In runtime/GC/SemiSpace.cpp is a prototype runtime which is compatible with 205eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen// ShadowStackGC. 218fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// In order to support this particular transformation, all stack roots are 238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// coallocated in the stack. This allows a fully target-independent stack map 248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// while introducing only minor runtime overhead. 258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// 268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen//===----------------------------------------------------------------------===// 278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen#define DEBUG_TYPE "shadowstackgc" 295a29c9eed157af51a8d338b5a225b146881819e8Gordon Henriksen#include "llvm/CodeGen/GCs.h" 308fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen#include "llvm/ADT/StringExtras.h" 315a29c9eed157af51a8d338b5a225b146881819e8Gordon Henriksen#include "llvm/CodeGen/GCStrategy.h" 328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen#include "llvm/IntrinsicInst.h" 338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen#include "llvm/Module.h" 3489c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif#include "llvm/Support/CallSite.h" 3589f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands#include "llvm/Support/IRBuilder.h" 368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksenusing namespace llvm; 388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksennamespace { 405c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 416726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class ShadowStackGC : public GCStrategy { 428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// RootChain - This is the global linked-list that contains the chain of GC 438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// roots. 448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen GlobalVariable *Head; 455c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// StackEntryTy - Abstract type of a link in the shadow stack. 475c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov /// 488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const StructType *StackEntryTy; 495c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// Roots - GC roots in the current function. Each is a pair of the 518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// intrinsic call and its corresponding alloca. 528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<std::pair<CallInst*,AllocaInst*> > Roots; 535c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen public: 555eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen ShadowStackGC(); 565c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool initializeCustomLowering(Module &M); 588fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool performCustomLowering(Function &F); 595c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen private: 618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool IsNullValue(Value *V); 628fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *GetFrameMap(Function &F); 638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const Type* GetConcreteStackEntryType(Function &F); 648fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen void CollectRoots(Function &F); 65e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson static GetElementPtrInst *CreateGEP(LLVMContext &Context, 669adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson IRBuilder<> &B, Value *BasePtr, 678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int Idx1, const char *Name); 68e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson static GetElementPtrInst *CreateGEP(LLVMContext &Context, 699adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson IRBuilder<> &B, Value *BasePtr, 708fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int Idx1, int Idx2, const char *Name); 718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 72844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 73844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 745c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 755eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenstatic GCRegistry::Add<ShadowStackGC> 765eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenX("shadow-stack", "Very portable GC for uncooperative code generators"); 775c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 78844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 798fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// EscapeEnumerator - This is a little algorithm to find all escape points 808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// from a function so that "finally"-style code can be inserted. In addition 818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// to finding the existing return and unwind instructions, it also (if 828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// necessary) transforms any call instructions into invokes and sends them to 838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// a landing pad. 845c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov /// 858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// It's wrapped up in a state machine using the same transform C# uses for 868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// 'yield return' enumerators, This transform allows it to be non-allocating. 876726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class EscapeEnumerator { 888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Function &F; 898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const char *CleanupBBName; 905c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 918fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // State. 928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int State; 938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Function::iterator StateBB, StateE; 947a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> Builder; 955c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen public: 978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EscapeEnumerator(Function &F, const char *N = "cleanup") 98e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson : F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {} 995c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1007a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> *Next() { 1018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen switch (State) { 1028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen default: 1038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return 0; 1045c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1058fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen case 0: 1068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StateBB = F.begin(); 1078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StateE = F.end(); 1088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen State = 1; 1095c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen case 1: 1118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find all 'return' and 'unwind' instructions. 1128fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (StateBB != StateE) { 1138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *CurBB = StateBB++; 1145c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1158fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Branches and invokes do not escape, only unwind and return do. 1168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TerminatorInst *TI = CurBB->getTerminator(); 1178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!isa<UnwindInst>(TI) && !isa<ReturnInst>(TI)) 1188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen continue; 1195c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Builder.SetInsertPoint(TI->getParent(), TI); 1218fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return &Builder; 1228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1235c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen State = 2; 1255c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find all 'call' instructions. 1278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Instruction*,16> Calls; 1288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (Function::iterator BB = F.begin(), 1298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen E = F.end(); BB != E; ++BB) 1308fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (BasicBlock::iterator II = BB->begin(), 1318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EE = BB->end(); II != EE; ++II) 1328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (CallInst *CI = dyn_cast<CallInst>(II)) 1338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!CI->getCalledFunction() || 1348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen !CI->getCalledFunction()->getIntrinsicID()) 1358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Calls.push_back(CI); 1365c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Calls.empty()) 1388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return 0; 1395c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Create a cleanup block. 1411d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *CleanupBB = BasicBlock::Create(F.getContext(), 1421d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson CleanupBBName, &F); 1431d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson UnwindInst *UI = new UnwindInst(F.getContext(), CleanupBB); 1445c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Transform the 'call' instructions into 'invoke's branching to the 1468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // cleanup block. Go in reverse order to make prettier BB names. 1478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Value*,16> Args; 1488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = Calls.size(); I != 0; ) { 1498fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallInst *CI = cast<CallInst>(Calls[--I]); 1505c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Split the basic block containing the function call. 1528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *CallBB = CI->getParent(); 1538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *NewBB = 1548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont"); 1555c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1568fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Remove the unconditional branch inserted at the end of CallBB. 1578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->getInstList().pop_back(); 1588fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NewBB->getInstList().remove(CI); 1595c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Create a new invoke instruction. 1618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Args.clear(); 16289c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif CallSite CS(CI); 16389c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif Args.append(CS.arg_begin(), CS.arg_end()); 1645c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 165a9b2313c13a1bc8cbae751da03a9049ecaf0f918Gabor Greif InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), 166051a950000e21935165db56695e35bade668193bGabor Greif NewBB, CleanupBB, 167051a950000e21935165db56695e35bade668193bGabor Greif Args.begin(), Args.end(), 168051a950000e21935165db56695e35bade668193bGabor Greif CI->getName(), CallBB); 1698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen II->setCallingConv(CI->getCallingConv()); 1700598866c052147c31b808391f58434ce3dbfb838Devang Patel II->setAttributes(CI->getAttributes()); 1718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CI->replaceAllUsesWith(II); 1728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen delete CI; 1738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1745c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Builder.SetInsertPoint(UI->getParent(), UI); 1768fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return &Builder; 1778fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1788fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1798fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 1808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 1818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// ----------------------------------------------------------------------------- 1838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1845eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid llvm::linkShadowStackGC() { } 1858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1865eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenShadowStackGC::ShadowStackGC() : Head(0), StackEntryTy(0) { 1878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen InitRoots = true; 1888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CustomRoots = true; 1898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 1908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1915eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenConstant *ShadowStackGC::GetFrameMap(Function &F) { 1928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the abstract type of this value. 193ac53a0b272452013124bfc70480aea5e41b60f40Duncan Sands const Type *VoidPtr = Type::getInt8PtrTy(F.getContext()); 1945c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1958fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Truncate the ShadowStackDescriptor if some metadata is null. 1968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen unsigned NumMeta = 0; 197b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner SmallVector<Constant*, 16> Metadata; 1988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0; I != Roots.size(); ++I) { 19989c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1)); 2008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!C->isNullValue()) 2018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NumMeta = I + 1; 2028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr)); 2038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 204267010864e139781ef5949939e081c41f954de0aJay Foad Metadata.resize(NumMeta); 2055c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 206b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner const Type *Int32Ty = Type::getInt32Ty(F.getContext()); 207b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner 2088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *BaseElts[] = { 209b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantInt::get(Int32Ty, Roots.size(), false), 210b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantInt::get(Int32Ty, NumMeta, false), 2118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2125c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *DescriptorElts[] = { 214b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantStruct::get(StructType::get(Int32Ty, Int32Ty, NULL), BaseElts), 215267010864e139781ef5949939e081c41f954de0aJay Foad ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata) 2168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2175c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 218b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner Constant *FrameMap = 219b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantStruct::get(StructType::get(DescriptorElts[0]->getType(), 220b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner DescriptorElts[1]->getType(), NULL), 221b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner DescriptorElts); 2225c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::string TypeName("gc_map."); 2248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TypeName += utostr(NumMeta); 2258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen F.getParent()->addTypeName(TypeName, FrameMap->getType()); 2265c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems 2288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // that, short of multithreaded LLVM, it should be safe; all that is 2298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // necessary is that a simple Module::iterator loop not be invalidated. 2308fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Appending to the GlobalVariable list is safe in that sense. 2315c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // All of the output passes emit globals last. The ExecutionEngine 2338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // explicitly supports adding globals to the module after 2348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // initialization. 2355c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Still, if it isn't deemed acceptable, then this transformation needs 2378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // to be a ModulePass (which means it cannot be in the 'llc' pipeline 2388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // (which uses a FunctionPassManager (which segfaults (not asserts) if 2398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // provided a ModulePass))). 240e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true, 2418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen GlobalVariable::InternalLinkage, 242e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson FrameMap, "__gc_" + F.getName()); 2435c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2441d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant *GEPIndices[2] = { 2451d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(F.getContext()), 0), 2461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(F.getContext()), 0) 2471d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson }; 248baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson return ConstantExpr::getGetElementPtr(GV, GEPIndices, 2); 2498fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2515eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenconst Type* ShadowStackGC::GetConcreteStackEntryType(Function &F) { 2528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the generic version of this type. 2538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<const Type*> EltTys; 2548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(StackEntryTy); 2558fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (size_t I = 0; I != Roots.size(); I++) 2568fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(Roots[I].second->getAllocatedType()); 257d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson Type *Ty = StructType::get(F.getContext(), EltTys); 2585c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::string TypeName("gc_stackentry."); 2608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TypeName += F.getName(); 2618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen F.getParent()->addTypeName(TypeName, Ty); 2625c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return Ty; 2648fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2658fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2668fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// doInitialization - If this module uses the GC intrinsics, find them now. If 2678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// not, exit fast. 2685eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::initializeCustomLowering(Module &M) { 2698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct FrameMap { 2708fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumRoots; // Number of roots in stack frame. 2718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots. 2728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Meta[]; // May be absent for roots without metadata. 2738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<const Type*> EltTys; 2751d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson // 32 bits is ok up to a 32GB stack frame. :) 2761d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson EltTys.push_back(Type::getInt32Ty(M.getContext())); 2771d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson // Specifies length of variable length array. 2781d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson EltTys.push_back(Type::getInt32Ty(M.getContext())); 279d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson StructType *FrameMapTy = StructType::get(M.getContext(), EltTys); 2808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen M.addTypeName("gc_map", FrameMapTy); 2818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy); 2825c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct StackEntry { 2848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // ShadowStackEntry *Next; // Caller's stack entry. 2858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap *Map; // Pointer to constant FrameMap. 2868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Roots[]; // Stack roots (in-place array, so we pretend). 2878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2880e275dc53880a7f14f8b8c83cc6e0290a215492dOwen Anderson OpaqueType *RecursiveTy = OpaqueType::get(M.getContext()); 2895c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.clear(); 2918fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(PointerType::getUnqual(RecursiveTy)); 2928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(FrameMapPtrTy); 293d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson PATypeHolder LinkTyH = StructType::get(M.getContext(), EltTys); 2945c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2958fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen RecursiveTy->refineAbstractTypeTo(LinkTyH.get()); 2968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StackEntryTy = cast<StructType>(LinkTyH.get()); 2978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy); 2988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen M.addTypeName("gc_stackentry", LinkTyH.get()); // FIXME: Is this safe from 2998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // a FunctionPass? 3005c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Get the root chain if it already exists. 3028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Head = M.getGlobalVariable("llvm_gc_root_chain"); 3038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!Head) { 3048fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If the root chain does not exist, insert a new one with linkonce 3058fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // linkage! 306e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Head = new GlobalVariable(M, StackEntryPtrTy, false, 307667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands GlobalValue::LinkOnceAnyLinkage, 308a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant::getNullValue(StackEntryPtrTy), 309e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson "llvm_gc_root_chain"); 3108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } else if (Head->hasExternalLinkage() && Head->isDeclaration()) { 311a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Head->setInitializer(Constant::getNullValue(StackEntryPtrTy)); 312667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands Head->setLinkage(GlobalValue::LinkOnceAnyLinkage); 3138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3145c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3158fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 3168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3185eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::IsNullValue(Value *V) { 3198fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Constant *C = dyn_cast<Constant>(V)) 3208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return C->isNullValue(); 3218fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3245eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid ShadowStackGC::CollectRoots(Function &F) { 3258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Account for original alignment. Could fragment the root array. 3268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 1: Null initialize empty slots at runtime. Yuck. 3278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 2: Emit a map of the array instead of just a count. 3285c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen assert(Roots.empty() && "Not cleaned up?"); 3305c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 33189c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif SmallVector<std::pair<CallInst*, AllocaInst*>, 16> MetaRoots; 3325c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 3348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) 3358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 3368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Function *F = CI->getCalledFunction()) 3378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (F->getIntrinsicID() == Intrinsic::gcroot) { 33889c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif std::pair<CallInst*, AllocaInst*> Pair = std::make_pair( 33989c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif CI, cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts())); 34089c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif if (IsNullValue(CI->getArgOperand(1))) 3418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.push_back(Pair); 3428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen else 3438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen MetaRoots.push_back(Pair); 3448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3455c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Number roots with metadata (usually empty) at the beginning, so that the 3478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap::Meta array can be elided. 3488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end()); 3498fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 352e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3535eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, int Idx2, const char *Name) { 3541d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 3551d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx), 3561d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx2) }; 35789f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands Value* Val = B.CreateGEP(BasePtr, Indices, Indices + 3, Name); 3585c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 35989f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 3605c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 36189f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3628fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3648fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 365e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3665eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, const char *Name) { 3671d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 3681d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx) }; 36989f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands Value *Val = B.CreateGEP(BasePtr, Indices, Indices + 2, Name); 3705c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 37189f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 37289f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands 37389f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3768fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// runOnFunction - Insert code to maintain the shadow stack. 3775eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::performCustomLowering(Function &F) { 378e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = F.getContext(); 3799adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 3808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find calls to llvm.gcroot. 3818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CollectRoots(F); 3825c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If there are no roots in this function, then there is no need to add a 3848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // stack map entry for it. 3858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Roots.empty()) 3868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3875c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the constant map and figure the type of the shadow stack entry. 3898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *FrameMap = GetFrameMap(F); 3908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F); 3915c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the shadow stack entry at the very start of the function. 3938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock::iterator IP = F.getEntryBlock().begin(); 3947a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> AtEntry(IP->getParent(), IP); 3955c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, 0, 3978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame"); 3985c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<AllocaInst>(IP)) ++IP; 4008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 4015c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Initialize the map pointer and load the current head of the shadow stack. 4038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead"); 4049adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, StackEntry, 4059adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 0,1,"gc_frame.map"); 4068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.CreateStore(FrameMap, EntryMapPtr); 4075c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // After all the allocas... 4098fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each root, find the corresponding slot in the aggregate... 4119adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root"); 4125c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // And use it in lieu of the alloca. 4148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AllocaInst *OriginalAlloca = Roots[I].second; 4158fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SlotPtr->takeName(OriginalAlloca); 4168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen OriginalAlloca->replaceAllUsesWith(SlotPtr); 4178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4185c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4195eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // Move past the original stores inserted by GCStrategy::InitRoots. This isn't 4205eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // really necessary (the collector would never see the intermediate state at 4215eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // runtime), but it's nicer not to push the half-initialized entry onto the 4225eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // shadow stack. 4238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<StoreInst>(IP)) ++IP; 4248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 4255c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Push the entry onto the shadow stack. 4279adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, 4289adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry,0,0,"gc_frame.next"); 4299adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *NewHeadVal = CreateGEP(Context, AtEntry, 4309adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry, 0, "gc_newhead"); 4319adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(CurrentHead, EntryNextPtr); 4329adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(NewHeadVal, Head); 4335c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each instruction that escapes... 4358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EscapeEnumerator EE(F, "gc_cleanup"); 4367a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher while (IRBuilder<> *AtExit = EE.Next()) { 4378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Pop the entry from the shadow stack. Don't reuse CurrentHead from 4388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // AtEntry, since that would make the value live for the entire function. 4399adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0, 4408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame.next"); 4418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead"); 4428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtExit->CreateStore(SavedHead, Head); 4438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4445c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Delete the original allocas (which are no longer used) and the intrinsic 4468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // calls (which are no longer valid). Doing this last avoids invalidating 4478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // iterators. 4488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4498fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].first->eraseFromParent(); 4508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].second->eraseFromParent(); 4518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4525c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.clear(); 4548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 4558fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 456