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