LLVM  10.0.0svn
GCRootLowering.cpp
Go to the documentation of this file.
1 //===-- GCRootLowering.cpp - Garbage collection infrastructure ------------===//
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 implements the lowering for the gc.root mechanism.
10 //
11 //===----------------------------------------------------------------------===//
12 
19 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/Support/Debug.h"
30 
31 using namespace llvm;
32 
33 namespace {
34 
35 /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or
36 /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as
37 /// directed by the GCStrategy. It also performs automatic root initialization
38 /// and custom intrinsic lowering.
39 class LowerIntrinsics : public FunctionPass {
40  bool DoLowering(Function &F, GCStrategy &S);
41 
42 public:
43  static char ID;
44 
45  LowerIntrinsics();
46  StringRef getPassName() const override;
47  void getAnalysisUsage(AnalysisUsage &AU) const override;
48 
49  bool doInitialization(Module &M) override;
50  bool runOnFunction(Function &F) override;
51 };
52 
53 /// GCMachineCodeAnalysis - This is a target-independent pass over the machine
54 /// function representation to identify safe points for the garbage collector
55 /// in the machine code. It inserts labels at safe points and populates a
56 /// GCMetadata record for each function.
57 class GCMachineCodeAnalysis : public MachineFunctionPass {
58  GCFunctionInfo *FI;
59  MachineModuleInfo *MMI;
60  const TargetInstrInfo *TII;
61 
62  void FindSafePoints(MachineFunction &MF);
63  void VisitCallPoint(MachineBasicBlock::iterator CI);
65  const DebugLoc &DL) const;
66 
67  void FindStackOffsets(MachineFunction &MF);
68 
69 public:
70  static char ID;
71 
72  GCMachineCodeAnalysis();
73  void getAnalysisUsage(AnalysisUsage &AU) const override;
74 
75  bool runOnMachineFunction(MachineFunction &MF) override;
76 };
77 }
78 
79 // -----------------------------------------------------------------------------
80 
81 INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false,
82  false)
84 INITIALIZE_PASS_END(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false)
85 
86 FunctionPass *llvm::createGCLoweringPass() { return new LowerIntrinsics(); }
87 
88 char LowerIntrinsics::ID = 0;
89 
90 LowerIntrinsics::LowerIntrinsics() : FunctionPass(ID) {
92 }
93 
94 StringRef LowerIntrinsics::getPassName() const {
95  return "Lower Garbage Collection Instructions";
96 }
97 
98 void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const {
102 }
103 
104 /// doInitialization - If this module uses the GC intrinsics, find them now.
105 bool LowerIntrinsics::doInitialization(Module &M) {
106  GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
107  assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
108  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
109  if (!I->isDeclaration() && I->hasGC())
110  MI->getFunctionInfo(*I); // Instantiate the GC strategy.
111 
112  return false;
113 }
114 
115 /// CouldBecomeSafePoint - Predicate to conservatively determine whether the
116 /// instruction could introduce a safe point.
118  // The natural definition of instructions which could introduce safe points
119  // are:
120  //
121  // - call, invoke (AfterCall, BeforeCall)
122  // - phis (Loops)
123  // - invoke, ret, unwind (Exit)
124  //
125  // However, instructions as seemingly inoccuous as arithmetic can become
126  // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
127  // it is necessary to take a conservative approach.
128 
129  if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) || isa<StoreInst>(I) ||
130  isa<LoadInst>(I))
131  return false;
132 
133  // llvm.gcroot is safe because it doesn't do anything at runtime.
134  if (CallInst *CI = dyn_cast<CallInst>(I))
135  if (Function *F = CI->getCalledFunction())
136  if (Intrinsic::ID IID = F->getIntrinsicID())
137  if (IID == Intrinsic::gcroot)
138  return false;
139 
140  return true;
141 }
142 
144  // Scroll past alloca instructions.
146  while (isa<AllocaInst>(IP))
147  ++IP;
148 
149  // Search for initializers in the initial BB.
150  SmallPtrSet<AllocaInst *, 16> InitedRoots;
151  for (; !CouldBecomeSafePoint(&*IP); ++IP)
152  if (StoreInst *SI = dyn_cast<StoreInst>(IP))
153  if (AllocaInst *AI =
154  dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts()))
155  InitedRoots.insert(AI);
156 
157  // Add root initializers.
158  bool MadeChange = false;
159 
160  for (AllocaInst *Root : Roots)
161  if (!InitedRoots.count(Root)) {
162  StoreInst *SI = new StoreInst(
163  ConstantPointerNull::get(cast<PointerType>(Root->getAllocatedType())),
164  Root);
165  SI->insertAfter(Root);
166  MadeChange = true;
167  }
168 
169  return MadeChange;
170 }
171 
172 /// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
173 /// Leave gcroot intrinsics; the code generator needs to see those.
175  // Quick exit for functions that do not use GC.
176  if (!F.hasGC())
177  return false;
178 
179  GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
180  GCStrategy &S = FI.getStrategy();
181 
182  return DoLowering(F, S);
183 }
184 
185 /// Lower barriers out of existance (if the associated GCStrategy hasn't
186 /// already done so...), and insert initializing stores to roots as a defensive
187 /// measure. Given we're going to report all roots live at all safepoints, we
188 /// need to be able to ensure each root has been initialized by the point the
189 /// first safepoint is reached. This really should have been done by the
190 /// frontend, but the old API made this non-obvious, so we do a potentially
191 /// redundant store just in case.
192 bool LowerIntrinsics::DoLowering(Function &F, GCStrategy &S) {
194 
195  bool MadeChange = false;
196  for (BasicBlock &BB : F)
197  for (BasicBlock::iterator II = BB.begin(), E = BB.end(); II != E;) {
198  IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++);
199  if (!CI)
200  continue;
201 
202  Function *F = CI->getCalledFunction();
203  switch (F->getIntrinsicID()) {
204  default: break;
205  case Intrinsic::gcwrite: {
206  // Replace a write barrier with a simple store.
207  Value *St = new StoreInst(CI->getArgOperand(0),
208  CI->getArgOperand(2), CI);
209  CI->replaceAllUsesWith(St);
210  CI->eraseFromParent();
211  MadeChange = true;
212  break;
213  }
214  case Intrinsic::gcread: {
215  // Replace a read barrier with a simple load.
216  Value *Ld = new LoadInst(CI->getType(), CI->getArgOperand(1), "", CI);
217  Ld->takeName(CI);
218  CI->replaceAllUsesWith(Ld);
219  CI->eraseFromParent();
220  MadeChange = true;
221  break;
222  }
223  case Intrinsic::gcroot: {
224  // Initialize the GC root, but do not delete the intrinsic. The
225  // backend needs the intrinsic to flag the stack slot.
226  Roots.push_back(
227  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
228  break;
229  }
230  }
231  }
232 
233  if (Roots.size())
234  MadeChange |= InsertRootInitializers(F, Roots);
235 
236  return MadeChange;
237 }
238 
239 // -----------------------------------------------------------------------------
240 
243 
244 INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis",
245  "Analyze Machine Code For Garbage Collection", false, false)
246 
247 GCMachineCodeAnalysis::GCMachineCodeAnalysis() : MachineFunctionPass(ID) {}
248 
249 void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
251  AU.setPreservesAll();
254 }
255 
256 MCSymbol *GCMachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
258  const DebugLoc &DL) const {
259  MCSymbol *Label = MBB.getParent()->getContext().createTempSymbol();
260  BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label);
261  return Label;
262 }
263 
264 void GCMachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
265  // Find the return address (next instruction), since that's what will be on
266  // the stack when the call is suspended and we need to inspect the stack.
268  ++RAI;
269 
270  MCSymbol *Label = InsertLabel(*CI->getParent(), RAI, CI->getDebugLoc());
271  FI->addSafePoint(Label, CI->getDebugLoc());
272 }
273 
274 void GCMachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
275  for (MachineBasicBlock &MBB : MF)
276  for (MachineBasicBlock::iterator MI = MBB.begin(), ME = MBB.end();
277  MI != ME; ++MI)
278  if (MI->isCall()) {
279  // Do not treat tail or sibling call sites as safe points. This is
280  // legal since any arguments passed to the callee which live in the
281  // remnants of the callers frame will be owned and updated by the
282  // callee if required.
283  if (MI->isTerminator())
284  continue;
285  VisitCallPoint(MI);
286  }
287 }
288 
289 void GCMachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
291  assert(TFI && "TargetRegisterInfo not available!");
292 
293  for (GCFunctionInfo::roots_iterator RI = FI->roots_begin();
294  RI != FI->roots_end();) {
295  // If the root references a dead object, no need to keep it.
296  if (MF.getFrameInfo().isDeadObjectIndex(RI->Num)) {
297  RI = FI->removeStackRoot(RI);
298  } else {
299  unsigned FrameReg; // FIXME: surely GCRoot ought to store the
300  // register that the offset is from?
301  RI->StackOffset = TFI->getFrameIndexReference(MF, RI->Num, FrameReg);
302  ++RI;
303  }
304  }
305 }
306 
307 bool GCMachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
308  // Quick exit for functions that do not use GC.
309  if (!MF.getFunction().hasGC())
310  return false;
311 
312  FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(MF.getFunction());
313  MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
314  TII = MF.getSubtarget().getInstrInfo();
315 
316  // Find the size of the stack frame. There may be no correct static frame
317  // size, we use UINT64_MAX to represent this.
318  const MachineFrameInfo &MFI = MF.getFrameInfo();
319  const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
320  const bool DynamicFrameSize = MFI.hasVarSizedObjects() ||
321  RegInfo->needsStackRealignment(MF);
322  FI->setFrameSize(DynamicFrameSize ? UINT64_MAX : MFI.getStackSize());
323 
324  // Find all safe points.
325  if (FI->getStrategy().needsSafePoints())
326  FindSafePoints(MF);
327 
328  // Find the concrete stack offsets for all roots (stack slots)
329  FindStackOffsets(MF);
330 
331  return false;
332 }
INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis", "Analyze Machine Code For Garbage Collection", false, false) GCMachineCodeAnalysis
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
Shadow Stack GC Lowering
virtual int getFrameIndexReference(const MachineFunction &MF, int FI, unsigned &FrameReg) const
getFrameIndexReference - This method should return the base register and offset used to reference a f...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
static bool InsertRootInitializers(Function &F, ArrayRef< AllocaInst *> Roots)
This class represents a function call, abstracting a target machine&#39;s calling convention.
static bool CouldBecomeSafePoint(Instruction *I)
CouldBecomeSafePoint - Predicate to conservatively determine whether the instruction could introduce ...
A debug info location.
Definition: DebugLoc.h:33
F(f)
An instruction for reading from memory.
Definition: Instructions.h:169
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
FunctionPass * createGCLoweringPass()
GCLowering Pass - Used by gc.root to perform its default lowering operations.
GCFunctionInfo & getFunctionInfo(const Function &F)
get - Look up function metadata.
Definition: GCMetadata.cpp:66
void initializeLowerIntrinsicsPass(PassRegistry &)
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
bool hasVarSizedObjects() const
This method may be called any time after instruction selection is complete to determine if the stack ...
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:152
#define UINT64_MAX
Definition: DataTypes.h:83
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:96
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
An instruction for storing to memory.
Definition: Instructions.h:325
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
virtual const TargetInstrInfo * getInstrInfo() const
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
TargetInstrInfo - Interface to description of machine instruction set.
MCContext & getContext() const
const BasicBlock & getEntryBlock() const
Definition: Function.h:669
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static bool runOnFunction(Function &F, bool PostInlining)
MCSymbol * createTempSymbol(bool CanBeUnnamed=true)
Create and return a new assembler temporary symbol with a unique but unspecified name.
Definition: MCContext.cpp:225
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1432
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
GCStrategy & getStrategy()
getStrategy - Return the GC strategy for the function.
Definition: GCMetadata.h:108
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
rewrite statepoints for gc
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:529
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
std::vector< GCRoot >::iterator roots_iterator
Definition: GCMetadata.h:80
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Information about stack frame layout on the target.
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
const Function & getFunction() const
Return the LLVM function that this machine code represents.
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
GCStrategy describes a garbage collector algorithm&#39;s code generation requirements, and provides overridable hooks for those needs which cannot be abstractly described.
Definition: GCStrategy.h:66
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:354
char & GCMachineCodeAnalysisID
GCMachineCodeAnalysis - Target-independent pass to mark safe points in machine code.
iterator end()
Definition: Module.h:601
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:79
#define I(x, y, z)
Definition: MD5.cpp:58
virtual const TargetFrameLowering * getFrameLowering() const
iterator begin()
Definition: Module.h:599
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool needsStackRealignment(const MachineFunction &MF) const
True if storage within the function requires the stack pointer to be aligned more than the normal cal...
LLVM Value Representation.
Definition: Value.h:74
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Garbage collection metadata for a single function.
Definition: GCMetadata.h:77
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false) FunctionPass *llvm
amdgpu printf runtime AMDGPU Printf lowering
uint64_t getStackSize() const
Return the number of bytes that must be allocated to hold all of the fixed size frame objects...
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
This class contains meta information specific to a module.
an instruction to allocate memory on the stack
Definition: Instructions.h:59