LLVM  14.0.0git
ShadowStackGCLowering.cpp
Go to the documentation of this file.
1 //===- ShadowStackGCLowering.cpp - Custom lowering for shadow-stack gc ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the custom lowering code required by the shadow-stack GC
10 // strategy.
11 //
12 // This pass implements the code transformation described in this paper:
13 // "Accurate Garbage Collection in an Uncooperative Environment"
14 // Fergus Henderson, ISMM, 2002
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
41 #include <cassert>
42 #include <cstddef>
43 #include <string>
44 #include <utility>
45 #include <vector>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "shadow-stack-gc-lowering"
50 
51 namespace {
52 
53 class ShadowStackGCLowering : public FunctionPass {
54  /// RootChain - This is the global linked-list that contains the chain of GC
55  /// roots.
56  GlobalVariable *Head = nullptr;
57 
58  /// StackEntryTy - Abstract type of a link in the shadow stack.
59  StructType *StackEntryTy = nullptr;
60  StructType *FrameMapTy = nullptr;
61 
62  /// Roots - GC roots in the current function. Each is a pair of the
63  /// intrinsic call and its corresponding alloca.
64  std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
65 
66 public:
67  static char ID;
68 
69  ShadowStackGCLowering();
70 
71  bool doInitialization(Module &M) override;
72  void getAnalysisUsage(AnalysisUsage &AU) const override;
73  bool runOnFunction(Function &F) override;
74 
75 private:
76  bool IsNullValue(Value *V);
77  Constant *GetFrameMap(Function &F);
78  Type *GetConcreteStackEntryType(Function &F);
79  void CollectRoots(Function &F);
80 
81  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
82  Type *Ty, Value *BasePtr, int Idx1,
83  const char *Name);
84  static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
85  Type *Ty, Value *BasePtr, int Idx1, int Idx2,
86  const char *Name);
87 };
88 
89 } // end anonymous namespace
90 
93 
94 INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE,
95  "Shadow Stack GC Lowering", false, false)
98 INITIALIZE_PASS_END(ShadowStackGCLowering, DEBUG_TYPE,
99  "Shadow Stack GC Lowering", false, false)
100 
101 FunctionPass *llvm::createShadowStackGCLoweringPass() { return new ShadowStackGCLowering(); }
102 
103 ShadowStackGCLowering::ShadowStackGCLowering() : FunctionPass(ID) {
105 }
106 
107 Constant *ShadowStackGCLowering::GetFrameMap(Function &F) {
108  // doInitialization creates the abstract type of this value.
109  Type *VoidPtr = Type::getInt8PtrTy(F.getContext());
110 
111  // Truncate the ShadowStackDescriptor if some metadata is null.
112  unsigned NumMeta = 0;
114  for (unsigned I = 0; I != Roots.size(); ++I) {
115  Constant *C = cast<Constant>(Roots[I].first->getArgOperand(1));
116  if (!C->isNullValue())
117  NumMeta = I + 1;
118  Metadata.push_back(ConstantExpr::getBitCast(C, VoidPtr));
119  }
120  Metadata.resize(NumMeta);
121 
122  Type *Int32Ty = Type::getInt32Ty(F.getContext());
123 
124  Constant *BaseElts[] = {
125  ConstantInt::get(Int32Ty, Roots.size(), false),
126  ConstantInt::get(Int32Ty, NumMeta, false),
127  };
128 
129  Constant *DescriptorElts[] = {
130  ConstantStruct::get(FrameMapTy, BaseElts),
131  ConstantArray::get(ArrayType::get(VoidPtr, NumMeta), Metadata)};
132 
133  Type *EltTys[] = {DescriptorElts[0]->getType(), DescriptorElts[1]->getType()};
134  StructType *STy = StructType::create(EltTys, "gc_map." + utostr(NumMeta));
135 
136  Constant *FrameMap = ConstantStruct::get(STy, DescriptorElts);
137 
138  // FIXME: Is this actually dangerous as WritingAnLLVMPass.html claims? Seems
139  // that, short of multithreaded LLVM, it should be safe; all that is
140  // necessary is that a simple Module::iterator loop not be invalidated.
141  // Appending to the GlobalVariable list is safe in that sense.
142  //
143  // All of the output passes emit globals last. The ExecutionEngine
144  // explicitly supports adding globals to the module after
145  // initialization.
146  //
147  // Still, if it isn't deemed acceptable, then this transformation needs
148  // to be a ModulePass (which means it cannot be in the 'llc' pipeline
149  // (which uses a FunctionPassManager (which segfaults (not asserts) if
150  // provided a ModulePass))).
151  Constant *GV = new GlobalVariable(*F.getParent(), FrameMap->getType(), true,
152  GlobalVariable::InternalLinkage, FrameMap,
153  "__gc_" + F.getName());
154 
155  Constant *GEPIndices[2] = {
156  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0),
157  ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)};
158  return ConstantExpr::getGetElementPtr(FrameMap->getType(), GV, GEPIndices);
159 }
160 
161 Type *ShadowStackGCLowering::GetConcreteStackEntryType(Function &F) {
162  // doInitialization creates the generic version of this type.
163  std::vector<Type *> EltTys;
164  EltTys.push_back(StackEntryTy);
165  for (size_t I = 0; I != Roots.size(); I++)
166  EltTys.push_back(Roots[I].second->getAllocatedType());
167 
168  return StructType::create(EltTys, ("gc_stackentry." + F.getName()).str());
169 }
170 
171 /// doInitialization - If this module uses the GC intrinsics, find them now. If
172 /// not, exit fast.
173 bool ShadowStackGCLowering::doInitialization(Module &M) {
174  bool Active = false;
175  for (Function &F : M) {
176  if (F.hasGC() && F.getGC() == std::string("shadow-stack")) {
177  Active = true;
178  break;
179  }
180  }
181  if (!Active)
182  return false;
183 
184  // struct FrameMap {
185  // int32_t NumRoots; // Number of roots in stack frame.
186  // int32_t NumMeta; // Number of metadata descriptors. May be < NumRoots.
187  // void *Meta[]; // May be absent for roots without metadata.
188  // };
189  std::vector<Type *> EltTys;
190  // 32 bits is ok up to a 32GB stack frame. :)
191  EltTys.push_back(Type::getInt32Ty(M.getContext()));
192  // Specifies length of variable length array.
193  EltTys.push_back(Type::getInt32Ty(M.getContext()));
194  FrameMapTy = StructType::create(EltTys, "gc_map");
195  PointerType *FrameMapPtrTy = PointerType::getUnqual(FrameMapTy);
196 
197  // struct StackEntry {
198  // ShadowStackEntry *Next; // Caller's stack entry.
199  // FrameMap *Map; // Pointer to constant FrameMap.
200  // void *Roots[]; // Stack roots (in-place array, so we pretend).
201  // };
202 
203  StackEntryTy = StructType::create(M.getContext(), "gc_stackentry");
204 
205  EltTys.clear();
206  EltTys.push_back(PointerType::getUnqual(StackEntryTy));
207  EltTys.push_back(FrameMapPtrTy);
208  StackEntryTy->setBody(EltTys);
209  PointerType *StackEntryPtrTy = PointerType::getUnqual(StackEntryTy);
210 
211  // Get the root chain if it already exists.
212  Head = M.getGlobalVariable("llvm_gc_root_chain");
213  if (!Head) {
214  // If the root chain does not exist, insert a new one with linkonce
215  // linkage!
216  Head = new GlobalVariable(
217  M, StackEntryPtrTy, false, GlobalValue::LinkOnceAnyLinkage,
218  Constant::getNullValue(StackEntryPtrTy), "llvm_gc_root_chain");
219  } else if (Head->hasExternalLinkage() && Head->isDeclaration()) {
220  Head->setInitializer(Constant::getNullValue(StackEntryPtrTy));
221  Head->setLinkage(GlobalValue::LinkOnceAnyLinkage);
222  }
223 
224  return true;
225 }
226 
227 bool ShadowStackGCLowering::IsNullValue(Value *V) {
228  if (Constant *C = dyn_cast<Constant>(V))
229  return C->isNullValue();
230  return false;
231 }
232 
233 void ShadowStackGCLowering::CollectRoots(Function &F) {
234  // FIXME: Account for original alignment. Could fragment the root array.
235  // Approach 1: Null initialize empty slots at runtime. Yuck.
236  // Approach 2: Emit a map of the array instead of just a count.
237 
238  assert(Roots.empty() && "Not cleaned up?");
239 
241 
242  for (BasicBlock &BB : F)
243  for (BasicBlock::iterator II = BB.begin(), E = BB.end(); II != E;)
244  if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++))
245  if (Function *F = CI->getCalledFunction())
246  if (F->getIntrinsicID() == Intrinsic::gcroot) {
247  std::pair<CallInst *, AllocaInst *> Pair = std::make_pair(
248  CI,
249  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
250  if (IsNullValue(CI->getArgOperand(1)))
251  Roots.push_back(Pair);
252  else
253  MetaRoots.push_back(Pair);
254  }
255 
256  // Number roots with metadata (usually empty) at the beginning, so that the
257  // FrameMap::Meta array can be elided.
258  Roots.insert(Roots.begin(), MetaRoots.begin(), MetaRoots.end());
259 }
260 
261 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
262  IRBuilder<> &B, Type *Ty,
263  Value *BasePtr, int Idx,
264  int Idx2,
265  const char *Name) {
266  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
267  ConstantInt::get(Type::getInt32Ty(Context), Idx),
268  ConstantInt::get(Type::getInt32Ty(Context), Idx2)};
269  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
270 
271  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
272 
273  return dyn_cast<GetElementPtrInst>(Val);
274 }
275 
276 GetElementPtrInst *ShadowStackGCLowering::CreateGEP(LLVMContext &Context,
277  IRBuilder<> &B, Type *Ty, Value *BasePtr,
278  int Idx, const char *Name) {
279  Value *Indices[] = {ConstantInt::get(Type::getInt32Ty(Context), 0),
280  ConstantInt::get(Type::getInt32Ty(Context), Idx)};
281  Value *Val = B.CreateGEP(Ty, BasePtr, Indices, Name);
282 
283  assert(isa<GetElementPtrInst>(Val) && "Unexpected folded constant");
284 
285  return dyn_cast<GetElementPtrInst>(Val);
286 }
287 
288 void ShadowStackGCLowering::getAnalysisUsage(AnalysisUsage &AU) const {
290 }
291 
292 /// runOnFunction - Insert code to maintain the shadow stack.
294  // Quick exit for functions that do not use the shadow stack GC.
295  if (!F.hasGC() ||
296  F.getGC() != std::string("shadow-stack"))
297  return false;
298 
299  LLVMContext &Context = F.getContext();
300 
301  // Find calls to llvm.gcroot.
302  CollectRoots(F);
303 
304  // If there are no roots in this function, then there is no need to add a
305  // stack map entry for it.
306  if (Roots.empty())
307  return false;
308 
310  if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
311  DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
312 
313  // Build the constant map and figure the type of the shadow stack entry.
314  Value *FrameMap = GetFrameMap(F);
315  Type *ConcreteStackEntryTy = GetConcreteStackEntryType(F);
316 
317  // Build the shadow stack entry at the very start of the function.
318  BasicBlock::iterator IP = F.getEntryBlock().begin();
319  IRBuilder<> AtEntry(IP->getParent(), IP);
320 
321  Instruction *StackEntry =
322  AtEntry.CreateAlloca(ConcreteStackEntryTy, nullptr, "gc_frame");
323 
324  while (isa<AllocaInst>(IP))
325  ++IP;
326  AtEntry.SetInsertPoint(IP->getParent(), IP);
327 
328  // Initialize the map pointer and load the current head of the shadow stack.
329  Instruction *CurrentHead =
330  AtEntry.CreateLoad(StackEntryTy->getPointerTo(), Head, "gc_currhead");
331  Instruction *EntryMapPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
332  StackEntry, 0, 1, "gc_frame.map");
333  AtEntry.CreateStore(FrameMap, EntryMapPtr);
334 
335  // After all the allocas...
336  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
337  // For each root, find the corresponding slot in the aggregate...
338  Value *SlotPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
339  StackEntry, 1 + I, "gc_root");
340 
341  // And use it in lieu of the alloca.
342  AllocaInst *OriginalAlloca = Roots[I].second;
343  SlotPtr->takeName(OriginalAlloca);
344  OriginalAlloca->replaceAllUsesWith(SlotPtr);
345  }
346 
347  // Move past the original stores inserted by GCStrategy::InitRoots. This isn't
348  // really necessary (the collector would never see the intermediate state at
349  // runtime), but it's nicer not to push the half-initialized entry onto the
350  // shadow stack.
351  while (isa<StoreInst>(IP))
352  ++IP;
353  AtEntry.SetInsertPoint(IP->getParent(), IP);
354 
355  // Push the entry onto the shadow stack.
356  Instruction *EntryNextPtr = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
357  StackEntry, 0, 0, "gc_frame.next");
358  Instruction *NewHeadVal = CreateGEP(Context, AtEntry, ConcreteStackEntryTy,
359  StackEntry, 0, "gc_newhead");
360  AtEntry.CreateStore(CurrentHead, EntryNextPtr);
361  AtEntry.CreateStore(NewHeadVal, Head);
362 
363  // For each instruction that escapes...
364  EscapeEnumerator EE(F, "gc_cleanup", /*HandleExceptions=*/true,
365  DTU.hasValue() ? DTU.getPointer() : nullptr);
366  while (IRBuilder<> *AtExit = EE.Next()) {
367  // Pop the entry from the shadow stack. Don't reuse CurrentHead from
368  // AtEntry, since that would make the value live for the entire function.
369  Instruction *EntryNextPtr2 =
370  CreateGEP(Context, *AtExit, ConcreteStackEntryTy, StackEntry, 0, 0,
371  "gc_frame.next");
372  Value *SavedHead = AtExit->CreateLoad(StackEntryTy->getPointerTo(),
373  EntryNextPtr2, "gc_savedhead");
374  AtExit->CreateStore(SavedHead, Head);
375  }
376 
377  // Delete the original allocas (which are no longer used) and the intrinsic
378  // calls (which are no longer valid). Doing this last avoids invalidating
379  // iterators.
380  for (unsigned I = 0, E = Roots.size(); I != E; ++I) {
381  Roots[I].first->eraseFromParent();
382  Roots[I].second->eraseFromParent();
383  }
384 
385  Roots.clear();
386  return true;
387 }
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
Lowering
Shadow Stack GC Lowering
Definition: ShadowStackGCLowering.cpp:99
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
IntrinsicInst.h
llvm::EscapeEnumerator
EscapeEnumerator - This is a little algorithm to find all escape points from a function so that "fina...
Definition: EscapeEnumerator.h:29
llvm::Function
Definition: Function.h:62
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::ShadowStackGCLoweringID
char & ShadowStackGCLoweringID
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC.
Definition: ShadowStackGCLowering.cpp:92
llvm::Optional
Definition: APInt.h:33
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ShadowStackGCLowering.cpp:49
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:280
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
GlobalValue.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::initializeShadowStackGCLoweringPass
void initializeShadowStackGCLoweringPass(PassRegistry &)
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
IP
Definition: NVPTXLowerArgs.cpp:166
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::createShadowStackGCLoweringPass
FunctionPass * createShadowStackGCLoweringPass()
ShadowStackGCLowering - Implements the custom lowering mechanism used by the shadow stack GC.
Definition: ShadowStackGCLowering.cpp:101
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
Passes.h
BasicBlock.h
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ShadowStackGCLowering, DEBUG_TYPE, "Shadow Stack GC Lowering", false, false) INITIALIZE_PASS_END(ShadowStackGCLowering
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:264
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
StringExtras.h
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
GlobalVariable.h
Casting.h
Function.h
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
Instructions.h
SmallVector.h
Dominators.h
EscapeEnumerator.h
DerivedTypes.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:382
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
Value.h
llvm::GCModuleInfo
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:152
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773