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 PerformDefaultLowering(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 static bool NeedsDefaultLoweringPass(const GCStrategy &C) {
106  // Default lowering is necessary only if read or write barriers have a default
107  // action. The default for roots is no action.
108  return !C.customWriteBarrier() || !C.customReadBarrier() ||
109  C.initializeRoots();
110 }
111 
112 /// doInitialization - If this module uses the GC intrinsics, find them now.
113 bool LowerIntrinsics::doInitialization(Module &M) {
114  GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
115  assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
116  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
117  if (!I->isDeclaration() && I->hasGC())
118  MI->getFunctionInfo(*I); // Instantiate the GC strategy.
119 
120  return false;
121 }
122 
123 /// CouldBecomeSafePoint - Predicate to conservatively determine whether the
124 /// instruction could introduce a safe point.
126  // The natural definition of instructions which could introduce safe points
127  // are:
128  //
129  // - call, invoke (AfterCall, BeforeCall)
130  // - phis (Loops)
131  // - invoke, ret, unwind (Exit)
132  //
133  // However, instructions as seemingly inoccuous as arithmetic can become
134  // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
135  // it is necessary to take a conservative approach.
136 
137  if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) || isa<StoreInst>(I) ||
138  isa<LoadInst>(I))
139  return false;
140 
141  // llvm.gcroot is safe because it doesn't do anything at runtime.
142  if (CallInst *CI = dyn_cast<CallInst>(I))
143  if (Function *F = CI->getCalledFunction())
144  if (Intrinsic::ID IID = F->getIntrinsicID())
145  if (IID == Intrinsic::gcroot)
146  return false;
147 
148  return true;
149 }
150 
152  unsigned Count) {
153  // Scroll past alloca instructions.
155  while (isa<AllocaInst>(IP))
156  ++IP;
157 
158  // Search for initializers in the initial BB.
159  SmallPtrSet<AllocaInst *, 16> InitedRoots;
160  for (; !CouldBecomeSafePoint(&*IP); ++IP)
161  if (StoreInst *SI = dyn_cast<StoreInst>(IP))
162  if (AllocaInst *AI =
163  dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts()))
164  InitedRoots.insert(AI);
165 
166  // Add root initializers.
167  bool MadeChange = false;
168 
169  for (AllocaInst **I = Roots, **E = Roots + Count; I != E; ++I)
170  if (!InitedRoots.count(*I)) {
171  StoreInst *SI = new StoreInst(
172  ConstantPointerNull::get(cast<PointerType>((*I)->getAllocatedType())),
173  *I);
174  SI->insertAfter(*I);
175  MadeChange = true;
176  }
177 
178  return MadeChange;
179 }
180 
181 /// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
182 /// Leave gcroot intrinsics; the code generator needs to see those.
184  // Quick exit for functions that do not use GC.
185  if (!F.hasGC())
186  return false;
187 
188  GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
189  GCStrategy &S = FI.getStrategy();
190 
191  bool MadeChange = false;
192 
194  MadeChange |= PerformDefaultLowering(F, S);
195 
196  return MadeChange;
197 }
198 
199 bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) {
200  bool LowerWr = !S.customWriteBarrier();
201  bool LowerRd = !S.customReadBarrier();
202  bool InitRoots = S.initializeRoots();
203 
205 
206  bool MadeChange = false;
207  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
208  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
209  if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) {
210  Function *F = CI->getCalledFunction();
211  switch (F->getIntrinsicID()) {
212  case Intrinsic::gcwrite:
213  if (LowerWr) {
214  // Replace a write barrier with a simple store.
215  Value *St =
216  new StoreInst(CI->getArgOperand(0), CI->getArgOperand(2), CI);
217  CI->replaceAllUsesWith(St);
218  CI->eraseFromParent();
219  }
220  break;
221  case Intrinsic::gcread:
222  if (LowerRd) {
223  // Replace a read barrier with a simple load.
224  Value *Ld = new LoadInst(CI->getArgOperand(1), "", CI);
225  Ld->takeName(CI);
226  CI->replaceAllUsesWith(Ld);
227  CI->eraseFromParent();
228  }
229  break;
230  case Intrinsic::gcroot:
231  if (InitRoots) {
232  // Initialize the GC root, but do not delete the intrinsic. The
233  // backend needs the intrinsic to flag the stack slot.
234  Roots.push_back(
235  cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts()));
236  }
237  break;
238  default:
239  continue;
240  }
241 
242  MadeChange = true;
243  }
244  }
245  }
246 
247  if (Roots.size())
248  MadeChange |= InsertRootInitializers(F, Roots.begin(), Roots.size());
249 
250  return MadeChange;
251 }
252 
253 // -----------------------------------------------------------------------------
254 
257 
258 INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis",
259  "Analyze Machine Code For Garbage Collection", false, false)
260 
261 GCMachineCodeAnalysis::GCMachineCodeAnalysis() : MachineFunctionPass(ID) {}
262 
263 void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
265  AU.setPreservesAll();
268 }
269 
270 MCSymbol *GCMachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
272  const DebugLoc &DL) const {
273  MCSymbol *Label = MBB.getParent()->getContext().createTempSymbol();
274  BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label);
275  return Label;
276 }
277 
278 void GCMachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
279  // Find the return address (next instruction), too, so as to bracket the call
280  // instruction.
282  ++RAI;
283 
284  if (FI->getStrategy().needsSafePoint(GC::PreCall)) {
285  MCSymbol *Label = InsertLabel(*CI->getParent(), CI, CI->getDebugLoc());
286  FI->addSafePoint(GC::PreCall, Label, CI->getDebugLoc());
287  }
288 
289  if (FI->getStrategy().needsSafePoint(GC::PostCall)) {
290  MCSymbol *Label = InsertLabel(*CI->getParent(), RAI, CI->getDebugLoc());
291  FI->addSafePoint(GC::PostCall, Label, CI->getDebugLoc());
292  }
293 }
294 
295 void GCMachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
296  for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end(); BBI != BBE;
297  ++BBI)
298  for (MachineBasicBlock::iterator MI = BBI->begin(), ME = BBI->end();
299  MI != ME; ++MI)
300  if (MI->isCall()) {
301  // Do not treat tail or sibling call sites as safe points. This is
302  // legal since any arguments passed to the callee which live in the
303  // remnants of the callers frame will be owned and updated by the
304  // callee if required.
305  if (MI->isTerminator())
306  continue;
307  VisitCallPoint(MI);
308  }
309 }
310 
311 void GCMachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
313  assert(TFI && "TargetRegisterInfo not available!");
314 
315  for (GCFunctionInfo::roots_iterator RI = FI->roots_begin();
316  RI != FI->roots_end();) {
317  // If the root references a dead object, no need to keep it.
318  if (MF.getFrameInfo().isDeadObjectIndex(RI->Num)) {
319  RI = FI->removeStackRoot(RI);
320  } else {
321  unsigned FrameReg; // FIXME: surely GCRoot ought to store the
322  // register that the offset is from?
323  RI->StackOffset = TFI->getFrameIndexReference(MF, RI->Num, FrameReg);
324  ++RI;
325  }
326  }
327 }
328 
329 bool GCMachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
330  // Quick exit for functions that do not use GC.
331  if (!MF.getFunction().hasGC())
332  return false;
333 
334  FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(MF.getFunction());
335  MMI = &getAnalysis<MachineModuleInfo>();
336  TII = MF.getSubtarget().getInstrInfo();
337 
338  // Find the size of the stack frame. There may be no correct static frame
339  // size, we use UINT64_MAX to represent this.
340  const MachineFrameInfo &MFI = MF.getFrameInfo();
341  const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
342  const bool DynamicFrameSize = MFI.hasVarSizedObjects() ||
343  RegInfo->needsStackRealignment(MF);
344  FI->setFrameSize(DynamicFrameSize ? UINT64_MAX : MFI.getStackSize());
345 
346  // Find all safe points.
347  if (FI->getStrategy().needsSafePoints())
348  FindSafePoints(MF);
349 
350  // Find the concrete stack offsets for all roots (stack slots)
351  FindStackOffsets(MF);
352 
353  return false;
354 }
INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis", "Analyze Machine Code For Garbage Collection", false, false) GCMachineCodeAnalysis
uint64_t CallInst * C
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...
Compute iterated dominance frontiers using a linear time algorithm.
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:64
Shadow Stack GC Lowering
iterator end()
Definition: Function.h:658
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.
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:264
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.
bool customReadBarrier() const
By default, read barriers are replaced with simple load instructions.
Definition: GCStrategy.h:114
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:154
#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
bool customWriteBarrier() const
By default, write barriers are replaced with simple store instructions.
Definition: GCStrategy.h:109
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:439
virtual const TargetInstrInfo * getInstrInfo() const
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
iterator begin()
Definition: Function.h:656
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:1378
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")
Instr is the return address of a call.
Definition: GCStrategy.h:70
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:110
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
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:82
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.
static bool NeedsDefaultLoweringPass(const GCStrategy &C)
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
static bool InsertRootInitializers(Function &F, AllocaInst **Roots, unsigned Count)
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:80
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:587
bool initializeRoots() const
If set, gcroot intrinsics should initialize their allocas to null before the first use...
Definition: GCStrategy.h:156
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:585
Instr is a call instruction.
Definition: GCStrategy.h:69
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:79
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