GCStrategy.cpp revision 0b8c9a80f20772c3793201ab5b251d3520b9cea3 
1//===-- GCStrategy.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 target- and collector-independent garbage collection
11// infrastructure.
12//
13// GCMachineCodeAnalysis identifies the GC safe points in the machine code.
14// Roots are identified in SelectionDAGISel.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/GCStrategy.h"
19#include "llvm/Analysis/DominatorInternals.h"
20#include "llvm/Analysis/Dominators.h"
21#include "llvm/CodeGen/MachineFrameInfo.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstrBuilder.h"
24#include "llvm/CodeGen/MachineModuleInfo.h"
25#include "llvm/CodeGen/Passes.h"
26#include "llvm/IR/IntrinsicInst.h"
27#include "llvm/IR/Module.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/Target/TargetFrameLowering.h"
32#include "llvm/Target/TargetInstrInfo.h"
33#include "llvm/Target/TargetMachine.h"
34#include "llvm/Target/TargetRegisterInfo.h"
35
36using namespace llvm;
37
38namespace {
39
40  /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or
41  /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as
42  /// directed by the GCStrategy. It also performs automatic root initialization
43  /// and custom intrinsic lowering.
44  class LowerIntrinsics : public FunctionPass {
45    static bool NeedsDefaultLoweringPass(const GCStrategy &C);
46    static bool NeedsCustomLoweringPass(const GCStrategy &C);
47    static bool CouldBecomeSafePoint(Instruction *I);
48    bool PerformDefaultLowering(Function &F, GCStrategy &Coll);
49    static bool InsertRootInitializers(Function &F,
50                                       AllocaInst **Roots, unsigned Count);
51
52  public:
53    static char ID;
54
55    LowerIntrinsics();
56    const char *getPassName() const;
57    void getAnalysisUsage(AnalysisUsage &AU) const;
58
59    bool doInitialization(Module &M);
60    bool runOnFunction(Function &F);
61  };
62
63
64  /// GCMachineCodeAnalysis - This is a target-independent pass over the machine
65  /// function representation to identify safe points for the garbage collector
66  /// in the machine code. It inserts labels at safe points and populates a
67  /// GCMetadata record for each function.
68  class GCMachineCodeAnalysis : public MachineFunctionPass {
69    const TargetMachine *TM;
70    GCFunctionInfo *FI;
71    MachineModuleInfo *MMI;
72    const TargetInstrInfo *TII;
73
74    void FindSafePoints(MachineFunction &MF);
75    void VisitCallPoint(MachineBasicBlock::iterator MI);
76    MCSymbol *InsertLabel(MachineBasicBlock &MBB,
77                          MachineBasicBlock::iterator MI,
78                          DebugLoc DL) const;
79
80    void FindStackOffsets(MachineFunction &MF);
81
82  public:
83    static char ID;
84
85    GCMachineCodeAnalysis();
86    void getAnalysisUsage(AnalysisUsage &AU) const;
87
88    bool runOnMachineFunction(MachineFunction &MF);
89  };
90
91}
92
93// -----------------------------------------------------------------------------
94
95GCStrategy::GCStrategy() :
96  NeededSafePoints(0),
97  CustomReadBarriers(false),
98  CustomWriteBarriers(false),
99  CustomRoots(false),
100  CustomSafePoints(false),
101  InitRoots(true),
102  UsesMetadata(false)
103{}
104
105GCStrategy::~GCStrategy() {
106  for (iterator I = begin(), E = end(); I != E; ++I)
107    delete *I;
108
109  Functions.clear();
110}
111
112bool GCStrategy::initializeCustomLowering(Module &M) { return false; }
113
114bool GCStrategy::performCustomLowering(Function &F) {
115  dbgs() << "gc " << getName() << " must override performCustomLowering.\n";
116  llvm_unreachable("must override performCustomLowering");
117}
118
119
120bool GCStrategy::findCustomSafePoints(GCFunctionInfo& FI, MachineFunction &F) {
121  dbgs() << "gc " << getName() << " must override findCustomSafePoints.\n";
122  llvm_unreachable(0);
123}
124
125
126GCFunctionInfo *GCStrategy::insertFunctionInfo(const Function &F) {
127  GCFunctionInfo *FI = new GCFunctionInfo(F, *this);
128  Functions.push_back(FI);
129  return FI;
130}
131
132// -----------------------------------------------------------------------------
133
134INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering",
135                      false, false)
136INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)
137INITIALIZE_PASS_END(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false)
138
139FunctionPass *llvm::createGCLoweringPass() {
140  return new LowerIntrinsics();
141}
142
143char LowerIntrinsics::ID = 0;
144
145LowerIntrinsics::LowerIntrinsics()
146  : FunctionPass(ID) {
147    initializeLowerIntrinsicsPass(*PassRegistry::getPassRegistry());
148  }
149
150const char *LowerIntrinsics::getPassName() const {
151  return "Lower Garbage Collection Instructions";
152}
153
154void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const {
155  FunctionPass::getAnalysisUsage(AU);
156  AU.addRequired<GCModuleInfo>();
157  AU.addPreserved<DominatorTree>();
158}
159
160/// doInitialization - If this module uses the GC intrinsics, find them now.
161bool LowerIntrinsics::doInitialization(Module &M) {
162  // FIXME: This is rather antisocial in the context of a JIT since it performs
163  //        work against the entire module. But this cannot be done at
164  //        runFunction time (initializeCustomLowering likely needs to change
165  //        the module).
166  GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
167  assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
168  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
169    if (!I->isDeclaration() && I->hasGC())
170      MI->getFunctionInfo(*I); // Instantiate the GC strategy.
171
172  bool MadeChange = false;
173  for (GCModuleInfo::iterator I = MI->begin(), E = MI->end(); I != E; ++I)
174    if (NeedsCustomLoweringPass(**I))
175      if ((*I)->initializeCustomLowering(M))
176        MadeChange = true;
177
178  return MadeChange;
179}
180
181bool LowerIntrinsics::InsertRootInitializers(Function &F, AllocaInst **Roots,
182                                                          unsigned Count) {
183  // Scroll past alloca instructions.
184  BasicBlock::iterator IP = F.getEntryBlock().begin();
185  while (isa<AllocaInst>(IP)) ++IP;
186
187  // Search for initializers in the initial BB.
188  SmallPtrSet<AllocaInst*,16> InitedRoots;
189  for (; !CouldBecomeSafePoint(IP); ++IP)
190    if (StoreInst *SI = dyn_cast<StoreInst>(IP))
191      if (AllocaInst *AI =
192          dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts()))
193        InitedRoots.insert(AI);
194
195  // Add root initializers.
196  bool MadeChange = false;
197
198  for (AllocaInst **I = Roots, **E = Roots + Count; I != E; ++I)
199    if (!InitedRoots.count(*I)) {
200      StoreInst* SI = new StoreInst(ConstantPointerNull::get(cast<PointerType>(
201                        cast<PointerType>((*I)->getType())->getElementType())),
202                        *I);
203      SI->insertAfter(*I);
204      MadeChange = true;
205    }
206
207  return MadeChange;
208}
209
210bool LowerIntrinsics::NeedsDefaultLoweringPass(const GCStrategy &C) {
211  // Default lowering is necessary only if read or write barriers have a default
212  // action. The default for roots is no action.
213  return !C.customWriteBarrier()
214      || !C.customReadBarrier()
215      || C.initializeRoots();
216}
217
218bool LowerIntrinsics::NeedsCustomLoweringPass(const GCStrategy &C) {
219  // Custom lowering is only necessary if enabled for some action.
220  return C.customWriteBarrier()
221      || C.customReadBarrier()
222      || C.customRoots();
223}
224
225/// CouldBecomeSafePoint - Predicate to conservatively determine whether the
226/// instruction could introduce a safe point.
227bool LowerIntrinsics::CouldBecomeSafePoint(Instruction *I) {
228  // The natural definition of instructions which could introduce safe points
229  // are:
230  //
231  //   - call, invoke (AfterCall, BeforeCall)
232  //   - phis (Loops)
233  //   - invoke, ret, unwind (Exit)
234  //
235  // However, instructions as seemingly inoccuous as arithmetic can become
236  // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
237  // it is necessary to take a conservative approach.
238
239  if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) ||
240      isa<StoreInst>(I) || isa<LoadInst>(I))
241    return false;
242
243  // llvm.gcroot is safe because it doesn't do anything at runtime.
244  if (CallInst *CI = dyn_cast<CallInst>(I))
245    if (Function *F = CI->getCalledFunction())
246      if (unsigned IID = F->getIntrinsicID())
247        if (IID == Intrinsic::gcroot)
248          return false;
249
250  return true;
251}
252
253/// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
254/// Leave gcroot intrinsics; the code generator needs to see those.
255bool LowerIntrinsics::runOnFunction(Function &F) {
256  // Quick exit for functions that do not use GC.
257  if (!F.hasGC())
258    return false;
259
260  GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
261  GCStrategy &S = FI.getStrategy();
262
263  bool MadeChange = false;
264
265  if (NeedsDefaultLoweringPass(S))
266    MadeChange |= PerformDefaultLowering(F, S);
267
268  bool UseCustomLoweringPass = NeedsCustomLoweringPass(S);
269  if (UseCustomLoweringPass)
270    MadeChange |= S.performCustomLowering(F);
271
272  // Custom lowering may modify the CFG, so dominators must be recomputed.
273  if (UseCustomLoweringPass) {
274    if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>())
275      DT->DT->recalculate(F);
276  }
277
278  return MadeChange;
279}
280
281bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) {
282  bool LowerWr = !S.customWriteBarrier();
283  bool LowerRd = !S.customReadBarrier();
284  bool InitRoots = S.initializeRoots();
285
286  SmallVector<AllocaInst*, 32> Roots;
287
288  bool MadeChange = false;
289  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
290    for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
291      if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) {
292        Function *F = CI->getCalledFunction();
293        switch (F->getIntrinsicID()) {
294        case Intrinsic::gcwrite:
295          if (LowerWr) {
296            // Replace a write barrier with a simple store.
297            Value *St = new StoreInst(CI->getArgOperand(0),
298                                      CI->getArgOperand(2), CI);
299            CI->replaceAllUsesWith(St);
300            CI->eraseFromParent();
301          }
302          break;
303        case Intrinsic::gcread:
304          if (LowerRd) {
305            // Replace a read barrier with a simple load.
306            Value *Ld = new LoadInst(CI->getArgOperand(1), "", CI);
307            Ld->takeName(CI);
308            CI->replaceAllUsesWith(Ld);
309            CI->eraseFromParent();
310          }
311          break;
312        case Intrinsic::gcroot:
313          if (InitRoots) {
314            // Initialize the GC root, but do not delete the intrinsic. The
315            // backend needs the intrinsic to flag the stack slot.
316            Roots.push_back(cast<AllocaInst>(
317                              CI->getArgOperand(0)->stripPointerCasts()));
318          }
319          break;
320        default:
321          continue;
322        }
323
324        MadeChange = true;
325      }
326    }
327  }
328
329  if (Roots.size())
330    MadeChange |= InsertRootInitializers(F, Roots.begin(), Roots.size());
331
332  return MadeChange;
333}
334
335// -----------------------------------------------------------------------------
336
337char GCMachineCodeAnalysis::ID = 0;
338char &llvm::GCMachineCodeAnalysisID = GCMachineCodeAnalysis::ID;
339
340INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis",
341                "Analyze Machine Code For Garbage Collection", false, false)
342
343GCMachineCodeAnalysis::GCMachineCodeAnalysis()
344  : MachineFunctionPass(ID) {}
345
346void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
347  MachineFunctionPass::getAnalysisUsage(AU);
348  AU.setPreservesAll();
349  AU.addRequired<MachineModuleInfo>();
350  AU.addRequired<GCModuleInfo>();
351}
352
353MCSymbol *GCMachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
354                                             MachineBasicBlock::iterator MI,
355                                             DebugLoc DL) const {
356  MCSymbol *Label = MBB.getParent()->getContext().CreateTempSymbol();
357  BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label);
358  return Label;
359}
360
361void GCMachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
362  // Find the return address (next instruction), too, so as to bracket the call
363  // instruction.
364  MachineBasicBlock::iterator RAI = CI;
365  ++RAI;
366
367  if (FI->getStrategy().needsSafePoint(GC::PreCall)) {
368    MCSymbol* Label = InsertLabel(*CI->getParent(), CI, CI->getDebugLoc());
369    FI->addSafePoint(GC::PreCall, Label, CI->getDebugLoc());
370  }
371
372  if (FI->getStrategy().needsSafePoint(GC::PostCall)) {
373    MCSymbol* Label = InsertLabel(*CI->getParent(), RAI, CI->getDebugLoc());
374    FI->addSafePoint(GC::PostCall, Label, CI->getDebugLoc());
375  }
376}
377
378void GCMachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
379  for (MachineFunction::iterator BBI = MF.begin(),
380                                 BBE = MF.end(); BBI != BBE; ++BBI)
381    for (MachineBasicBlock::iterator MI = BBI->begin(),
382                                     ME = BBI->end(); MI != ME; ++MI)
383      if (MI->isCall())
384        VisitCallPoint(MI);
385}
386
387void GCMachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
388  const TargetFrameLowering *TFI = TM->getFrameLowering();
389  assert(TFI && "TargetRegisterInfo not available!");
390
391  for (GCFunctionInfo::roots_iterator RI = FI->roots_begin();
392       RI != FI->roots_end();) {
393    // If the root references a dead object, no need to keep it.
394    if (MF.getFrameInfo()->isDeadObjectIndex(RI->Num)) {
395      RI = FI->removeStackRoot(RI);
396    } else {
397      RI->StackOffset = TFI->getFrameIndexOffset(MF, RI->Num);
398      ++RI;
399    }
400  }
401}
402
403bool GCMachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
404  // Quick exit for functions that do not use GC.
405  if (!MF.getFunction()->hasGC())
406    return false;
407
408  FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction());
409  if (!FI->getStrategy().needsSafePoints())
410    return false;
411
412  TM = &MF.getTarget();
413  MMI = &getAnalysis<MachineModuleInfo>();
414  TII = TM->getInstrInfo();
415
416  // Find the size of the stack frame.
417  FI->setFrameSize(MF.getFrameInfo()->getStackSize());
418
419  // Find all safe points.
420  if (FI->getStrategy().customSafePoints()) {
421    FI->getStrategy().findCustomSafePoints(*FI, MF);
422  } else {
423    FindSafePoints(MF);
424  }
425
426  // Find the stack offsets for all roots.
427  FindStackOffsets(MF);
428
429  return false;
430}
431