ShadowStackGC.cpp revision eed707b1e6097aac2bb6b3d47271f6300ace7f2e
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" 342388a588bdf32610e18a66c0c6ef248087fd1cdcMikhail Glushenkov#include "llvm/Support/Compiler.h" 3589f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands#include "llvm/Support/IRBuilder.h" 368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksenusing namespace llvm; 388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksennamespace { 405c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 415eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen class VISIBILITY_HIDDEN 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. 878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen class VISIBILITY_HIDDEN 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. 141051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock *CleanupBB = BasicBlock::Create(CleanupBBName, &F); 1428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen UnwindInst *UI = new UnwindInst(CleanupBB); 1435c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Transform the 'call' instructions into 'invoke's branching to the 1458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // cleanup block. Go in reverse order to make prettier BB names. 1468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Value*,16> Args; 1478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = Calls.size(); I != 0; ) { 1488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallInst *CI = cast<CallInst>(Calls[--I]); 1495c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Split the basic block containing the function call. 1518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *CallBB = CI->getParent(); 1528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *NewBB = 1538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont"); 1545c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1558fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Remove the unconditional branch inserted at the end of CallBB. 1568fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->getInstList().pop_back(); 1578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NewBB->getInstList().remove(CI); 1585c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Create a new invoke instruction. 1608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Args.clear(); 1618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Args.append(CI->op_begin() + 1, CI->op_end()); 1625c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 163051a950000e21935165db56695e35bade668193bGabor Greif InvokeInst *II = InvokeInst::Create(CI->getOperand(0), 164051a950000e21935165db56695e35bade668193bGabor Greif NewBB, CleanupBB, 165051a950000e21935165db56695e35bade668193bGabor Greif Args.begin(), Args.end(), 166051a950000e21935165db56695e35bade668193bGabor Greif CI->getName(), CallBB); 1678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen II->setCallingConv(CI->getCallingConv()); 1680598866c052147c31b808391f58434ce3dbfb838Devang Patel II->setAttributes(CI->getAttributes()); 1698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CI->replaceAllUsesWith(II); 1708fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen delete CI; 1718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1725c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Builder.SetInsertPoint(UI->getParent(), UI); 1748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return &Builder; 1758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1768fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1778fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 1788fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 1798fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// ----------------------------------------------------------------------------- 1818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1825eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid llvm::linkShadowStackGC() { } 1838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1845eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenShadowStackGC::ShadowStackGC() : Head(0), StackEntryTy(0) { 1858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen InitRoots = true; 1868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CustomRoots = true; 1878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 1888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1895eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenConstant *ShadowStackGC::GetFrameMap(Function &F) { 1908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the abstract type of this value. 191e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = F.getContext(); 1925c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Type *VoidPtr = PointerType::getUnqual(Type::Int8Ty); 1945c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1958fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Truncate the ShadowStackDescriptor if some metadata is null. 1968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen unsigned NumMeta = 0; 1978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Constant*,16> Metadata; 1988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0; I != Roots.size(); ++I) { 1998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *C = cast<Constant>(Roots[I].first->getOperand(2)); 2008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!C->isNullValue()) 2018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NumMeta = I + 1; 2028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr)); 2038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 2045c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2058fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *BaseElts[] = { 206eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, Roots.size(), false), 207eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, NumMeta, false), 2088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2095c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *DescriptorElts[] = { 211e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson Context.getConstantStruct(BaseElts, 2), 212e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson Context.getConstantArray(Context.getArrayType(VoidPtr, NumMeta), 2138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Metadata.begin(), NumMeta) 2148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2155c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 216e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson Constant *FrameMap = Context.getConstantStruct(DescriptorElts, 2); 2175c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::string TypeName("gc_map."); 2198fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TypeName += utostr(NumMeta); 2208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen F.getParent()->addTypeName(TypeName, FrameMap->getType()); 2215c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems 2238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // that, short of multithreaded LLVM, it should be safe; all that is 2248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // necessary is that a simple Module::iterator loop not be invalidated. 2258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Appending to the GlobalVariable list is safe in that sense. 2265c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // All of the output passes emit globals last. The ExecutionEngine 2288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // explicitly supports adding globals to the module after 2298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // initialization. 2305c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Still, if it isn't deemed acceptable, then this transformation needs 2328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // to be a ModulePass (which means it cannot be in the 'llc' pipeline 2338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // (which uses a FunctionPassManager (which segfaults (not asserts) if 2348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // provided a ModulePass))). 235e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true, 2368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen GlobalVariable::InternalLinkage, 237e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson FrameMap, "__gc_" + F.getName()); 2385c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 239eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Constant *GEPIndices[2] = { ConstantInt::get(Type::Int32Ty, 0), 240eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, 0) }; 241e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson return Context.getConstantExprGetElementPtr(GV, GEPIndices, 2); 2428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2445eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenconst Type* ShadowStackGC::GetConcreteStackEntryType(Function &F) { 2458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the generic version of this type. 2468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<const Type*> EltTys; 2478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(StackEntryTy); 2488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (size_t I = 0; I != Roots.size(); I++) 2498fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(Roots[I].second->getAllocatedType()); 2508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Type *Ty = StructType::get(EltTys); 2515c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::string TypeName("gc_stackentry."); 2538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TypeName += F.getName(); 2548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen F.getParent()->addTypeName(TypeName, Ty); 2555c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2568fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return Ty; 2578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2588fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// doInitialization - If this module uses the GC intrinsics, find them now. If 2608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// not, exit fast. 2615eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::initializeCustomLowering(Module &M) { 2628fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct FrameMap { 2638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumRoots; // Number of roots in stack frame. 2648fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots. 2658fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Meta[]; // May be absent for roots without metadata. 2668fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<const Type*> EltTys; 2688fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(Type::Int32Ty); // 32 bits is ok up to a 32GB stack frame. :) 2698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(Type::Int32Ty); // Specifies length of variable length array. 2708fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StructType *FrameMapTy = StructType::get(EltTys); 2718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen M.addTypeName("gc_map", FrameMapTy); 2728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy); 2735c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct StackEntry { 2758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // ShadowStackEntry *Next; // Caller's stack entry. 2768fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap *Map; // Pointer to constant FrameMap. 2778fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Roots[]; // Stack roots (in-place array, so we pretend). 2788fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2798fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen OpaqueType *RecursiveTy = OpaqueType::get(); 2805c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.clear(); 2828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(PointerType::getUnqual(RecursiveTy)); 2838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(FrameMapPtrTy); 2848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen PATypeHolder LinkTyH = StructType::get(EltTys); 2855c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen RecursiveTy->refineAbstractTypeTo(LinkTyH.get()); 2878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StackEntryTy = cast<StructType>(LinkTyH.get()); 2888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy); 2898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen M.addTypeName("gc_stackentry", LinkTyH.get()); // FIXME: Is this safe from 2908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // a FunctionPass? 2915c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Get the root chain if it already exists. 2938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Head = M.getGlobalVariable("llvm_gc_root_chain"); 2948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!Head) { 2958fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If the root chain does not exist, insert a new one with linkonce 2968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // linkage! 297e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Head = new GlobalVariable(M, StackEntryPtrTy, false, 298667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands GlobalValue::LinkOnceAnyLinkage, 2990a5372ed3e8cda10d724feda3c1a1c998db05ca0Owen Anderson M.getContext().getNullValue(StackEntryPtrTy), 300e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson "llvm_gc_root_chain"); 3018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } else if (Head->hasExternalLinkage() && Head->isDeclaration()) { 3020a5372ed3e8cda10d724feda3c1a1c998db05ca0Owen Anderson Head->setInitializer(M.getContext().getNullValue(StackEntryPtrTy)); 303667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands Head->setLinkage(GlobalValue::LinkOnceAnyLinkage); 3048fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3055c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 3078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3095eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::IsNullValue(Value *V) { 3108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Constant *C = dyn_cast<Constant>(V)) 3118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return C->isNullValue(); 3128fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3155eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid ShadowStackGC::CollectRoots(Function &F) { 3168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Account for original alignment. Could fragment the root array. 3178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 1: Null initialize empty slots at runtime. Yuck. 3188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 2: Emit a map of the array instead of just a count. 3195c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen assert(Roots.empty() && "Not cleaned up?"); 3215c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<std::pair<CallInst*,AllocaInst*>,16> MetaRoots; 3235c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 3258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) 3268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 3278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Function *F = CI->getCalledFunction()) 3288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (F->getIntrinsicID() == Intrinsic::gcroot) { 3298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::pair<CallInst*,AllocaInst*> Pair = std::make_pair( 3300b12ecf6ff6b5d3a144178257b6206f0c4788792Anton Korobeynikov CI, cast<AllocaInst>(CI->getOperand(1)->stripPointerCasts())); 3318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (IsNullValue(CI->getOperand(2))) 3328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.push_back(Pair); 3338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen else 3348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen MetaRoots.push_back(Pair); 3358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3365c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Number roots with metadata (usually empty) at the beginning, so that the 3388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap::Meta array can be elided. 3398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end()); 3408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 343e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3445eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, int Idx2, const char *Name) { 345eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *Indices[] = { ConstantInt::get(Type::Int32Ty, 0), 346eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, Idx), 347eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, Idx2) }; 34889f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands Value* Val = B.CreateGEP(BasePtr, Indices, Indices + 3, Name); 3495c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 35089f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 3515c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 35289f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3548fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3558fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 356e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3575eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, const char *Name) { 358eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *Indices[] = { ConstantInt::get(Type::Int32Ty, 0), 359eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Type::Int32Ty, Idx) }; 36089f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands Value *Val = B.CreateGEP(BasePtr, Indices, Indices + 2, Name); 3615c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 36289f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 36389f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands 36489f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3658fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3668fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// runOnFunction - Insert code to maintain the shadow stack. 3685eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::performCustomLowering(Function &F) { 369e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = F.getContext(); 3709adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 3718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find calls to llvm.gcroot. 3728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CollectRoots(F); 3735c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If there are no roots in this function, then there is no need to add a 3758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // stack map entry for it. 3768fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Roots.empty()) 3778fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3785c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3798fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the constant map and figure the type of the shadow stack entry. 3808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *FrameMap = GetFrameMap(F); 3818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F); 3825c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the shadow stack entry at the very start of the function. 3848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock::iterator IP = F.getEntryBlock().begin(); 3857a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> AtEntry(IP->getParent(), IP); 3865c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, 0, 3888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame"); 3895c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<AllocaInst>(IP)) ++IP; 3918fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 3925c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Initialize the map pointer and load the current head of the shadow stack. 3948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead"); 3959adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, StackEntry, 3969adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 0,1,"gc_frame.map"); 3978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.CreateStore(FrameMap, EntryMapPtr); 3985c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // After all the allocas... 4008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each root, find the corresponding slot in the aggregate... 4029adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root"); 4035c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4048fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // And use it in lieu of the alloca. 4058fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AllocaInst *OriginalAlloca = Roots[I].second; 4068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SlotPtr->takeName(OriginalAlloca); 4078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen OriginalAlloca->replaceAllUsesWith(SlotPtr); 4088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4095c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4105eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // Move past the original stores inserted by GCStrategy::InitRoots. This isn't 4115eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // really necessary (the collector would never see the intermediate state at 4125eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // runtime), but it's nicer not to push the half-initialized entry onto the 4135eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // shadow stack. 4148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<StoreInst>(IP)) ++IP; 4158fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 4165c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Push the entry onto the shadow stack. 4189adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, 4199adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry,0,0,"gc_frame.next"); 4209adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *NewHeadVal = CreateGEP(Context, AtEntry, 4219adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry, 0, "gc_newhead"); 4229adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(CurrentHead, EntryNextPtr); 4239adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(NewHeadVal, Head); 4245c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4258fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each instruction that escapes... 4268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EscapeEnumerator EE(F, "gc_cleanup"); 4277a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher while (IRBuilder<> *AtExit = EE.Next()) { 4288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Pop the entry from the shadow stack. Don't reuse CurrentHead from 4298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // AtEntry, since that would make the value live for the entire function. 4309adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0, 4318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame.next"); 4328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead"); 4338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtExit->CreateStore(SavedHead, Head); 4348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4355c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Delete the original allocas (which are no longer used) and the intrinsic 4378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // calls (which are no longer valid). Doing this last avoids invalidating 4388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // iterators. 4398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].first->eraseFromParent(); 4418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].second->eraseFromParent(); 4428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4435c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.clear(); 4458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 4468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 447