LLVM  8.0.0svn
GCRootLowering.cpp
Go to the documentation of this file.
1 //===-- GCRootLowering.cpp - Garbage collection infrastructure ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the lowering for the gc.root mechanism.
11 //
12 //===----------------------------------------------------------------------===//
13 
20 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/Support/Debug.h"
31 
32 using namespace llvm;
33 
34 namespace {
35 
36 /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or
37 /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as
38 /// directed by the GCStrategy. It also performs automatic root initialization
39 /// and custom intrinsic lowering.
40 class LowerIntrinsics : public FunctionPass {
41  bool DoLowering(Function &F, GCStrategy &S);
42 
43 public:
44  static char ID;
45 
46  LowerIntrinsics();
47  StringRef getPassName() const override;
48  void getAnalysisUsage(AnalysisUsage &AU) const override;
49 
50  bool doInitialization(Module &M) override;
51  bool runOnFunction(Function &F) override;
52 };
53 
54 /// GCMachineCodeAnalysis - This is a target-independent pass over the machine
55 /// function representation to identify safe points for the garbage collector
56 /// in the machine code. It inserts labels at safe points and populates a
57 /// GCMetadata record for each function.
58 class GCMachineCodeAnalysis : public MachineFunctionPass {
59  GCFunctionInfo *FI;
60  MachineModuleInfo *MMI;
61  const TargetInstrInfo *TII;
62 
63  void FindSafePoints(MachineFunction &MF);
64  void VisitCallPoint(MachineBasicBlock::iterator CI);
66  const DebugLoc &DL) const;
67 
68  void FindStackOffsets(MachineFunction &MF);
69 
70 public:
71  static char ID;
72 
73  GCMachineCodeAnalysis();
74  void getAnalysisUsage(AnalysisUsage &AU) const override;
75 
76  bool runOnMachineFunction(MachineFunction &MF) override;
77 };
78 }
79 
80 // -----------------------------------------------------------------------------
81 
82 INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false,
83  false)
85 INITIALIZE_PASS_END(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false)
86 
87 FunctionPass *llvm::createGCLoweringPass() { return new LowerIntrinsics(); }
88 
89 char LowerIntrinsics::ID = 0;
90 
91 LowerIntrinsics::LowerIntrinsics() : FunctionPass(ID) {
93 }
94 
95 StringRef LowerIntrinsics::getPassName() const {
96  return "Lower Garbage Collection Instructions";
97 }
98 
99 void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const {
103 }
104 
105 /// doInitialization - If this module uses the GC intrinsics, find them now.
106 bool LowerIntrinsics::doInitialization(Module &M) {
107  GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
108  assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
109  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
110  if (!I->isDeclaration() && I->hasGC())
111  MI->getFunctionInfo(*I); // Instantiate the GC strategy.
112 
113  return false;
114 }
115 
116 /// CouldBecomeSafePoint - Predicate to conservatively determine whether the
117 /// instruction could introduce a safe point.
119  // The natural definition of instructions which could introduce safe points
120  // are:
121  //
122  // - call, invoke (AfterCall, BeforeCall)
123  // - phis (Loops)
124  // - invoke, ret, unwind (Exit)
125  //
126  // However, instructions as seemingly inoccuous as arithmetic can become
127  // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
128  // it is necessary to take a conservative approach.
129 
130  if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) || isa<StoreInst>(I) ||
131  isa<LoadInst>(I))
132  return false;
133 
134  // llvm.gcroot is safe because it doesn't do anything at runtime.
135  if (CallInst *CI = dyn_cast<CallInst>(I))
136  if (Function *F = CI->getCalledFunction())
137  if (Intrinsic::ID IID = F->getIntrinsicID())
138  if (IID == Intrinsic::gcroot)
139  return false;
140 
141  return true;
142 }
143 
145  // Scroll past alloca instructions.
147  while (isa<AllocaInst>(IP))
148  ++IP;
149 
150  // Search for initializers in the initial BB.
151  SmallPtrSet<AllocaInst *, 16> InitedRoots;
152  for (; !CouldBecomeSafePoint(&*IP); ++IP)
153  if (StoreInst *SI = dyn_cast<StoreInst>(IP))
154  if (AllocaInst *AI =
155  dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts()))
156  InitedRoots.insert(AI);
157 
158  // Add root initializers.
159  bool MadeChange = false;
160 
161  for (AllocaInst *Root : Roots)
162  if (!InitedRoots.count(Root)) {
163  StoreInst *SI = new StoreInst(
164  ConstantPointerNull::get(cast<PointerType>(Root->getAllocatedType())),
165  Root);
166  SI->insertAfter(Root);
167  MadeChange = true;
168  }
169 
170  return MadeChange;
171 }
172 
173 /// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
174 /// Leave gcroot intrinsics; the code generator needs to see those.
176  // Quick exit for functions that do not use GC.
177  if (!F.hasGC())
178  return false;
179 
180  GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
181  GCStrategy &S = FI.getStrategy();
182 
183  return DoLowering(F, S);
184 }
185 
186 /// Lower barriers out of existance (if the associated GCStrategy hasn't
187 /// already done so...), and insert initializing stores to roots as a defensive
188 /// measure. Given we're going to report all roots live at all safepoints, we
189 /// need to be able to ensure each root has been initialized by the point the
190 /// first safepoint is reached. This really should have been done by the
191 /// frontend, but the old API made this non-obvious, so we do a potentially
192 /// redundant store just in case.
193 bool LowerIntrinsics::DoLowering(Function &F, GCStrategy &S) {
195 
196  bool MadeChange = false;
197  for (BasicBlock &BB : F)
198  for (BasicBlock::iterator II = BB.begin(), E = BB.end(); II != E;) {
199  IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++);
200  if (!CI)
201  continue;
202 
203  Function *F = CI->getCalledFunction();
204  switch (F->getIntrinsicID()) {
205  default: break;
206  case Intrinsic::gcwrite: {
207  // Replace a write barrier with a simple store.
208  Value *St = new StoreInst(CI->getArgOperand(0),
209  CI->getArgOperand(2), CI);
210  CI->replaceAllUsesWith(St);
211  CI->eraseFromParent();
212  MadeChange = true;
213  break;
214  }
215  case Intrinsic::gcread: {
216  // Replace a read barrier with a simple load.
217  Value *Ld = new LoadInst(CI->getArgOperand(1), "", CI);
218  Ld->takeName(CI);
219  CI->replaceAllUsesWith(Ld);
220  CI->eraseFromParent();
221  MadeChange = true;
222  break;
223  }
224  case Intrinsic::gcroot: {
225  // Initialize the GC root, but do not delete the intrinsic. The
226  // backend needs the intrinsic to flag the stack slot.
227  Roots.push_back(
228  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
229  break;
230  }
231  }
232  }
233 
234  if (Roots.size())
235  MadeChange |= InsertRootInitializers(F, Roots);
236 
237  return MadeChange;
238 }
239 
240 // -----------------------------------------------------------------------------
241 
244 
245 INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis",
246  "Analyze Machine Code For Garbage Collection", false, false)
247 
248 GCMachineCodeAnalysis::GCMachineCodeAnalysis() : MachineFunctionPass(ID) {}
249 
250 void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
252  AU.setPreservesAll();
255 }
256 
257 MCSymbol *GCMachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
259  const DebugLoc &DL) const {
260  MCSymbol *Label = MBB.getParent()->getContext().createTempSymbol();
261  BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label);
262  return Label;
263 }
264 
265 void GCMachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
266  // Find the return address (next instruction), since that's what will be on
267  // the stack when the call is suspended and we need to inspect the stack.
269  ++RAI;
270 
271  MCSymbol *Label = InsertLabel(*CI->getParent(), RAI, CI->getDebugLoc());
272  FI->addSafePoint(Label, CI->getDebugLoc());
273 }
274 
275 void GCMachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
276  for (MachineBasicBlock &MBB : MF)
277  for (MachineBasicBlock::iterator MI = MBB.begin(), ME = MBB.end();
278  MI != ME; ++MI)
279  if (MI->isCall()) {
280  // Do not treat tail or sibling call sites as safe points. This is
281  // legal since any arguments passed to the callee which live in the
282  // remnants of the callers frame will be owned and updated by the
283  // callee if required.
284  if (MI->isTerminator())
285  continue;
286  VisitCallPoint(MI);
287  }
288 }
289 
290 void GCMachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
292  assert(TFI && "TargetRegisterInfo not available!");
293 
294  for (GCFunctionInfo::roots_iterator RI = FI->roots_begin();
295  RI != FI->roots_end();) {
296  // If the root references a dead object, no need to keep it.
297  if (MF.getFrameInfo().isDeadObjectIndex(RI->Num)) {
298  RI = FI->removeStackRoot(RI);
299  } else {
300  unsigned FrameReg; // FIXME: surely GCRoot ought to store the
301  // register that the offset is from?
302  RI->StackOffset = TFI->getFrameIndexReference(MF, RI->Num, FrameReg);
303  ++RI;
304  }
305  }
306 }
307 
308 bool GCMachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
309  // Quick exit for functions that do not use GC.
310  if (!MF.getFunction().hasGC())
311  return false;
312 
313  FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(MF.getFunction());
314  MMI = &getAnalysis<MachineModuleInfo>();
315  TII = MF.getSubtarget().getInstrInfo();
316 
317  // Find the size of the stack frame. There may be no correct static frame
318  // size, we use UINT64_MAX to represent this.
319  const MachineFrameInfo &MFI = MF.getFrameInfo();
320  const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
321  const bool DynamicFrameSize = MFI.hasVarSizedObjects() ||
322  RegInfo->needsStackRealignment(MF);
323  FI->setFrameSize(DynamicFrameSize ? UINT64_MAX : MFI.getStackSize());
324 
325  // Find all safe points.
326  if (FI->getStrategy().needsSafePoints())
327  FindSafePoints(MF);
328 
329  // Find the concrete stack offsets for all roots (stack slots)
330  FindStackOffsets(MF);
331 
332  return false;
333 }
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:68
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:24
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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.
X86 EFLAGS copy lowering
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:34
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1079
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
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:67
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:153
#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:92
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
An instruction for storing to memory.
Definition: Instructions.h:310
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
virtual const TargetInstrInfo * getInstrInfo() const
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
TargetInstrInfo - Interface to description of machine instruction set.
MCContext & getContext() const
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
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:217
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1401
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:371
GCStrategy & getStrategy()
getStrategy - Return the GC strategy for the function.
Definition: GCMetadata.h:109
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
rewrite statepoints for gc
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:530
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:53
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:81
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:418
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:194
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:67
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:349
char & GCMachineCodeAnalysisID
GCMachineCodeAnalysis - Target-independent pass to mark safe points in machine code.
iterator end()
Definition: Module.h:588
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1112
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:80
#define I(x, y, z)
Definition: MD5.cpp:58
virtual const TargetFrameLowering * getFrameLowering() const
iterator begin()
Definition: Module.h:586
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:323
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:73
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Garbage collection metadata for a single function.
Definition: GCMetadata.h:78
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false) FunctionPass *llvm
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:44
This class contains meta information specific to a module.
an instruction to allocate memory on the stack
Definition: Instructions.h:60