ShadowStackGC.cpp revision 0b8c9a80f20772c3793201ab5b251d3520b9cea3
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" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/GCs.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/StringExtras.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/GCStrategy.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 3589c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif#include "llvm/Support/CallSite.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 /// 481afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner StructType *StackEntryTy; 491afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner StructType *FrameMapTy; 505c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// Roots - GC roots in the current function. Each is a pair of the 528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// intrinsic call and its corresponding alloca. 538fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen std::vector<std::pair<CallInst*,AllocaInst*> > Roots; 545c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 558fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen public: 565eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen ShadowStackGC(); 575c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 588fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool initializeCustomLowering(Module &M); 598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool performCustomLowering(Function &F); 605c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen private: 628fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen bool IsNullValue(Value *V); 638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *GetFrameMap(Function &F); 64db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type* GetConcreteStackEntryType(Function &F); 658fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen void CollectRoots(Function &F); 66e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson static GetElementPtrInst *CreateGEP(LLVMContext &Context, 679adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson IRBuilder<> &B, Value *BasePtr, 688fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int Idx1, const char *Name); 69e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson static GetElementPtrInst *CreateGEP(LLVMContext &Context, 709adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson IRBuilder<> &B, Value *BasePtr, 718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int Idx1, int Idx2, const char *Name); 728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 73844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 74844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 755c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 765eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenstatic GCRegistry::Add<ShadowStackGC> 775eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenX("shadow-stack", "Very portable GC for uncooperative code generators"); 785c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 79844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// EscapeEnumerator - This is a little algorithm to find all escape points 818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// from a function so that "finally"-style code can be inserted. In addition 828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// to finding the existing return and unwind instructions, it also (if 838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// necessary) transforms any call instructions into invokes and sends them to 848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// a landing pad. 855c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov /// 868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// It's wrapped up in a state machine using the same transform C# uses for 878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen /// 'yield return' enumerators, This transform allows it to be non-allocating. 886726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class EscapeEnumerator { 898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Function &F; 908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen const char *CleanupBBName; 915c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // State. 938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen int State; 948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Function::iterator StateBB, StateE; 957a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> Builder; 965c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen public: 988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EscapeEnumerator(Function &F, const char *N = "cleanup") 99e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson : F(F), CleanupBBName(N), State(0), Builder(F.getContext()) {} 1005c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1017a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> *Next() { 1028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen switch (State) { 1038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen default: 1048fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return 0; 1055c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen case 0: 1078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StateBB = F.begin(); 1088fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen StateE = F.end(); 1098fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen State = 1; 1105c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen case 1: 1123ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling // Find all 'return', 'resume', and 'unwind' instructions. 1138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (StateBB != StateE) { 1148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *CurBB = StateBB++; 1155c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 116dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling // Branches and invokes do not escape, only unwind, resume, and return 117dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling // do. 1188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen TerminatorInst *TI = CurBB->getTerminator(); 119aa5abe88d6aa445afa593476a665e3ab14b3524cBill Wendling if (!isa<ReturnInst>(TI) && !isa<ResumeInst>(TI)) 1208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen continue; 1215c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Builder.SetInsertPoint(TI->getParent(), TI); 1238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return &Builder; 1248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1255c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen State = 2; 1275c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1288fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find all 'call' instructions. 1298fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Instruction*,16> Calls; 1308fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (Function::iterator BB = F.begin(), 1318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen E = F.end(); BB != E; ++BB) 1328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (BasicBlock::iterator II = BB->begin(), 1338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EE = BB->end(); II != EE; ++II) 1348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (CallInst *CI = dyn_cast<CallInst>(II)) 1358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!CI->getCalledFunction() || 1368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen !CI->getCalledFunction()->getIntrinsicID()) 1378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Calls.push_back(CI); 1385c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Calls.empty()) 1408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return 0; 1415c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Create a cleanup block. 1433ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling LLVMContext &C = F.getContext(); 1443ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling BasicBlock *CleanupBB = BasicBlock::Create(C, CleanupBBName, &F); 1453ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling Type *ExnTy = StructType::get(Type::getInt8PtrTy(C), 1463ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling Type::getInt32Ty(C), NULL); 1473ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling Constant *PersFn = 1483ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling F.getParent()-> 149711395527e6b19d4bf26e22586f2c13591970ba6Bill Wendling getOrInsertFunction("__gcc_personality_v0", 1503ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling FunctionType::get(Type::getInt32Ty(C), true)); 1513ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling LandingPadInst *LPad = LandingPadInst::Create(ExnTy, PersFn, 1, 1523ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling "cleanup.lpad", 1533ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling CleanupBB); 1543ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling LPad->setCleanup(true); 1553ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling ResumeInst *RI = ResumeInst::Create(LPad, CleanupBB); 1565c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Transform the 'call' instructions into 'invoke's branching to the 1588fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // cleanup block. Go in reverse order to make prettier BB names. 1598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SmallVector<Value*,16> Args; 1608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = Calls.size(); I != 0; ) { 1618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallInst *CI = cast<CallInst>(Calls[--I]); 1625c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Split the basic block containing the function call. 1648fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *CallBB = CI->getParent(); 1658fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock *NewBB = 1668fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->splitBasicBlock(CI, CallBB->getName() + ".cont"); 1675c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1688fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Remove the unconditional branch inserted at the end of CallBB. 1698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CallBB->getInstList().pop_back(); 1708fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NewBB->getInstList().remove(CI); 1715c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Create a new invoke instruction. 1738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Args.clear(); 17489c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif CallSite CS(CI); 17589c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif Args.append(CS.arg_begin(), CS.arg_end()); 1765c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 177a9b2313c13a1bc8cbae751da03a9049ecaf0f918Gabor Greif InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), 178051a950000e21935165db56695e35bade668193bGabor Greif NewBB, CleanupBB, 179a3efbb15ddd5aa9006564cd79086723640084878Jay Foad Args, CI->getName(), CallBB); 1808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen II->setCallingConv(CI->getCallingConv()); 1810598866c052147c31b808391f58434ce3dbfb838Devang Patel II->setAttributes(CI->getAttributes()); 1828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CI->replaceAllUsesWith(II); 1838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen delete CI; 1848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1855c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 1863ca2ad11567f83883ae2719c5fac5afc30c7b3d1Bill Wendling Builder.SetInsertPoint(RI->getParent(), RI); 1878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return &Builder; 1888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 1908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 1918fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 1928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen// ----------------------------------------------------------------------------- 1948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1955eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid llvm::linkShadowStackGC() { } 1968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 1975eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenShadowStackGC::ShadowStackGC() : Head(0), StackEntryTy(0) { 1988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen InitRoots = true; 1998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CustomRoots = true; 2008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2025eca075b74d62c621b160aa216b4cd50829a2cc7Gordon HenriksenConstant *ShadowStackGC::GetFrameMap(Function &F) { 2038fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the abstract type of this value. 204db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *VoidPtr = Type::getInt8PtrTy(F.getContext()); 2055c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Truncate the ShadowStackDescriptor if some metadata is null. 2078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen unsigned NumMeta = 0; 208b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner SmallVector<Constant*, 16> Metadata; 2098fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0; I != Roots.size(); ++I) { 21089c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1)); 2118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!C->isNullValue()) 2128fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen NumMeta = I + 1; 2138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr)); 2148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 215267010864e139781ef5949939e081c41f954de0aJay Foad Metadata.resize(NumMeta); 2165c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 217db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Int32Ty = Type::getInt32Ty(F.getContext()); 218b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner 2198fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *BaseElts[] = { 220b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantInt::get(Int32Ty, Roots.size(), false), 221b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantInt::get(Int32Ty, NumMeta, false), 2228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2235c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Constant *DescriptorElts[] = { 2251afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner ConstantStruct::get(FrameMapTy, BaseElts), 226267010864e139781ef5949939e081c41f954de0aJay Foad ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata) 2278fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen }; 2285c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2291afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Type *EltTys[] = { DescriptorElts[0]->getType(),DescriptorElts[1]->getType()}; 2303ebb64946bc8e7c8feba1b2044e7a47f80b3a83fChris Lattner StructType *STy = StructType::create(EltTys, "gc_map."+utostr(NumMeta)); 2311afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 2321afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts); 2335c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems 2358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // that, short of multithreaded LLVM, it should be safe; all that is 2368fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // necessary is that a simple Module::iterator loop not be invalidated. 2378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Appending to the GlobalVariable list is safe in that sense. 2385c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // All of the output passes emit globals last. The ExecutionEngine 2408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // explicitly supports adding globals to the module after 2418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // initialization. 2425c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov // 2438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Still, if it isn't deemed acceptable, then this transformation needs 2448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // to be a ModulePass (which means it cannot be in the 'llc' pipeline 2458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // (which uses a FunctionPassManager (which segfaults (not asserts) if 2468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // provided a ModulePass))). 247e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true, 2488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen GlobalVariable::InternalLinkage, 249e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson FrameMap, "__gc_" + F.getName()); 2505c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2511d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant *GEPIndices[2] = { 2521d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(F.getContext()), 0), 2531d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(F.getContext()), 0) 2541d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson }; 255b4263a6ff4f9696fc84a8f75b5d09564ff06381fJay Foad return ConstantExpr::getGetElementPtr(GV, GEPIndices); 2568fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2578fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 258db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris LattnerType* ShadowStackGC::GetConcreteStackEntryType(Function &F) { 2598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // doInitialization creates the generic version of this type. 2601afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner std::vector<Type*> EltTys; 2618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(StackEntryTy); 2628fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (size_t I = 0; I != Roots.size(); I++) 2638fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(Roots[I].second->getAllocatedType()); 2641afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 2653ebb64946bc8e7c8feba1b2044e7a47f80b3a83fChris Lattner return StructType::create(EltTys, "gc_stackentry."+F.getName().str()); 2668fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 2678fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 2688fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// doInitialization - If this module uses the GC intrinsics, find them now. If 2698fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// not, exit fast. 2705eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::initializeCustomLowering(Module &M) { 2718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct FrameMap { 2728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumRoots; // Number of roots in stack frame. 2738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots. 2748fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Meta[]; // May be absent for roots without metadata. 2758fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2761afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner std::vector<Type*> EltTys; 2771d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson // 32 bits is ok up to a 32GB stack frame. :) 2781d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson EltTys.push_back(Type::getInt32Ty(M.getContext())); 2791d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson // Specifies length of variable length array. 2801d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson EltTys.push_back(Type::getInt32Ty(M.getContext())); 2813ebb64946bc8e7c8feba1b2044e7a47f80b3a83fChris Lattner FrameMapTy = StructType::create(EltTys, "gc_map"); 2828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy); 2835c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2848fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // struct StackEntry { 2858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // ShadowStackEntry *Next; // Caller's stack entry. 2868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap *Map; // Pointer to constant FrameMap. 2878fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // void *Roots[]; // Stack roots (in-place array, so we pretend). 2888fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // }; 2891afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 2903ebb64946bc8e7c8feba1b2044e7a47f80b3a83fChris Lattner StackEntryTy = StructType::create(M.getContext(), "gc_stackentry"); 2911afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 2928fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.clear(); 2931afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner EltTys.push_back(PointerType::getUnqual(StackEntryTy)); 2948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EltTys.push_back(FrameMapPtrTy); 2951afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner StackEntryTy->setBody(EltTys); 296db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy); 2975c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 2988fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Get the root chain if it already exists. 2998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Head = M.getGlobalVariable("llvm_gc_root_chain"); 3008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (!Head) { 3018fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If the root chain does not exist, insert a new one with linkonce 3028fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // linkage! 303e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson Head = new GlobalVariable(M, StackEntryPtrTy, false, 304667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands GlobalValue::LinkOnceAnyLinkage, 305a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant::getNullValue(StackEntryPtrTy), 306e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson "llvm_gc_root_chain"); 3078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } else if (Head->hasExternalLinkage() && Head->isDeclaration()) { 308a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Head->setInitializer(Constant::getNullValue(StackEntryPtrTy)); 309667d4b8de6dea70195ff12ef39a4deebffa2f5c7Duncan Sands Head->setLinkage(GlobalValue::LinkOnceAnyLinkage); 3108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3115c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3128fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 3138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3155eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::IsNullValue(Value *V) { 3168fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Constant *C = dyn_cast<Constant>(V)) 3178fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return C->isNullValue(); 3188fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3198fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3215eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenvoid ShadowStackGC::CollectRoots(Function &F) { 3228fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FIXME: Account for original alignment. Could fragment the root array. 3238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 1: Null initialize empty slots at runtime. Yuck. 3248fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Approach 2: Emit a map of the array instead of just a count. 3255c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3268fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen assert(Roots.empty() && "Not cleaned up?"); 3275c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 32889c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif SmallVector<std::pair<CallInst*, AllocaInst*>, 16> MetaRoots; 3295c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3308fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 3318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) 3328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 3338fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Function *F = CI->getCalledFunction()) 3348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (F->getIntrinsicID() == Intrinsic::gcroot) { 33589c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif std::pair<CallInst*, AllocaInst*> Pair = std::make_pair( 33689c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif CI, cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts())); 33789c4cead3c1448902f5fc6c266de5f20222c6b03Gabor Greif if (IsNullValue(CI->getArgOperand(1))) 3388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.push_back(Pair); 3398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen else 3408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen MetaRoots.push_back(Pair); 3418fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 3425c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Number roots with metadata (usually empty) at the beginning, so that the 3448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // FrameMap::Meta array can be elided. 3458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end()); 3468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 349e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3505eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, int Idx2, const char *Name) { 3511d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 3521d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx), 3531d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx2) }; 3540a2a60ace9b79164b71794ce7ff981171c61e442Jay Foad Value* Val = B.CreateGEP(BasePtr, Indices, Name); 3555c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 35689f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 3575c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 35889f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3598fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3608fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3618fa89291774a29ee30adb9d0fd01655c84eaac13Gordon HenriksenGetElementPtrInst * 362e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonShadowStackGC::CreateGEP(LLVMContext &Context, IRBuilder<> &B, Value *BasePtr, 3635eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen int Idx, const char *Name) { 3641d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *Indices[] = { ConstantInt::get(Type::getInt32Ty(Context), 0), 3651d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Context), Idx) }; 3660a2a60ace9b79164b71794ce7ff981171c61e442Jay Foad Value *Val = B.CreateGEP(BasePtr, Indices, Name); 3675c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 36889f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant"); 36989f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands 37089f6d88db334ba088672ae0753deb7d7b7509bacDuncan Sands return dyn_cast<GetElementPtrInst>(Val); 3718fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 3728fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen 3738fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen/// runOnFunction - Insert code to maintain the shadow stack. 3745eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksenbool ShadowStackGC::performCustomLowering(Function &F) { 375e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = F.getContext(); 3769adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 3778fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Find calls to llvm.gcroot. 3788fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen CollectRoots(F); 3795c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3808fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // If there are no roots in this function, then there is no need to add a 3818fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // stack map entry for it. 3828fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen if (Roots.empty()) 3838fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return false; 3845c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3858fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the constant map and figure the type of the shadow stack entry. 3868fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *FrameMap = GetFrameMap(F); 387db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F); 3885c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3898fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Build the shadow stack entry at the very start of the function. 3908fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen BasicBlock::iterator IP = F.getEntryBlock().begin(); 3917a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher IRBuilder<> AtEntry(IP->getParent(), IP); 3925c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3938fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *StackEntry = AtEntry.CreateAlloca(ConcreteStackEntryTy, 0, 3948fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame"); 3955c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3968fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<AllocaInst>(IP)) ++IP; 3978fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 3985c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 3998fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Initialize the map pointer and load the current head of the shadow stack. 4008fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Instruction *CurrentHead = AtEntry.CreateLoad(Head, "gc_currhead"); 4019adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, StackEntry, 4029adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson 0,1,"gc_frame.map"); 4031afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner AtEntry.CreateStore(FrameMap, EntryMapPtr); 4045c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4058fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // After all the allocas... 4068fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4078fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each root, find the corresponding slot in the aggregate... 4089adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Value *SlotPtr = CreateGEP(Context, AtEntry, StackEntry, 1 + I, "gc_root"); 4095c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4108fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // And use it in lieu of the alloca. 4118fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AllocaInst *OriginalAlloca = Roots[I].second; 4128fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen SlotPtr->takeName(OriginalAlloca); 4138fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen OriginalAlloca->replaceAllUsesWith(SlotPtr); 4148fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4155c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4165eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // Move past the original stores inserted by GCStrategy::InitRoots. This isn't 4175eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // really necessary (the collector would never see the intermediate state at 4185eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // runtime), but it's nicer not to push the half-initialized entry onto the 4195eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen // shadow stack. 4208fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen while (isa<StoreInst>(IP)) ++IP; 4218fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtEntry.SetInsertPoint(IP->getParent(), IP); 4225c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4238fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Push the entry onto the shadow stack. 4249adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, 4259adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry,0,0,"gc_frame.next"); 4269adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *NewHeadVal = CreateGEP(Context, AtEntry, 4279adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson StackEntry, 0, "gc_newhead"); 4289adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(CurrentHead, EntryNextPtr); 4299adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson AtEntry.CreateStore(NewHeadVal, Head); 4305c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4318fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // For each instruction that escapes... 4328fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen EscapeEnumerator EE(F, "gc_cleanup"); 4337a61d701c0870642e075e90b6a1ad03a8ac9bc67Eric Christopher while (IRBuilder<> *AtExit = EE.Next()) { 4348fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Pop the entry from the shadow stack. Don't reuse CurrentHead from 4358fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // AtEntry, since that would make the value live for the entire function. 4369adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson Instruction *EntryNextPtr2 = CreateGEP(Context, *AtExit, StackEntry, 0, 0, 4378fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen "gc_frame.next"); 4388fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Value *SavedHead = AtExit->CreateLoad(EntryNextPtr2, "gc_savedhead"); 4398fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen AtExit->CreateStore(SavedHead, Head); 4408fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4415c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4428fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // Delete the original allocas (which are no longer used) and the intrinsic 4438fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // calls (which are no longer valid). Doing this last avoids invalidating 4448fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen // iterators. 4458fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen for (unsigned I = 0, E = Roots.size(); I != E; ++I) { 4468fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].first->eraseFromParent(); 4478fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots[I].second->eraseFromParent(); 4488fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen } 4495c1799b29375fcd899f67a31fb4dda4ef3e2127fMikhail Glushenkov 4508fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen Roots.clear(); 4518fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen return true; 4528fa89291774a29ee30adb9d0fd01655c84eaac13Gordon Henriksen} 453