lib/CodeGen/Collector.cpp

   1 //===-- Collector.cpp - Garbage collection infrastructure -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Gordon Henriksen and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements target- and collector-independent garbage collection
  11 // infrastructure.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/Collector.h"
  16 #include "llvm/IntrinsicInst.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/PassManager.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/Target/TargetFrameInfo.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Support/Compiler.h"
  27
  28 using namespace llvm;
  29
  30 namespace {
  31
  32   /// This pass rewrites calls to the llvm.gcread or llvm.gcwrite intrinsics,
  33   /// replacing them with simple loads and stores as directed by the Collector.
  34   /// This is useful for most garbage collectors.
  35   class VISIBILITY_HIDDEN LowerIntrinsics : public FunctionPass {
  36     const Collector &Coll;
  37
  38     /// GCRootInt, GCReadInt, GCWriteInt - The function prototypes for the
  39     /// llvm.gc* intrinsics.
  40     Function *GCRootInt, *GCReadInt, *GCWriteInt;
  41
  42     static bool CouldBecomeSafePoint(Instruction *I);
  43     static void InsertRootInitializers(Function &F,
  44                                        AllocaInst **Roots, unsigned Count);
  45
  46   public:
  47     static char ID;
  48
  49     LowerIntrinsics(const Collector &GC);
  50     const char *getPassName() const;
  51
  52     bool doInitialization(Module &M);
  53     bool runOnFunction(Function &F);
  54   };
  55
  56
  57   /// This is a target-independent pass over the machine function representation
  58   /// to identify safe points for the garbage collector in the machine code. It
  59   /// inserts labels at safe points and populates the GCInfo class.
  60   class VISIBILITY_HIDDEN MachineCodeAnalysis : public MachineFunctionPass {
  61     const Collector &Coll;
  62     const TargetMachine &Targ;
  63
  64     CollectorMetadata *MD;
  65     MachineModuleInfo *MMI;
  66     const TargetInstrInfo *TII;
  67     MachineFrameInfo *MFI;
  68
  69     void FindSafePoints(MachineFunction &MF);
  70     void VisitCallPoint(MachineBasicBlock::iterator MI);
  71     unsigned InsertLabel(MachineBasicBlock &MBB,
  72                          MachineBasicBlock::iterator MI) const;
  73
  74     void FindStackOffsets(MachineFunction &MF);
  75
  76   public:
  77     static char ID;
  78
  79     MachineCodeAnalysis(const Collector &C, const TargetMachine &T);
  80     const char *getPassName() const;
  81     void getAnalysisUsage(AnalysisUsage &AU) const;
  82
  83     bool runOnMachineFunction(MachineFunction &MF);
  84   };
  85
  86 }
  87
  88 // -----------------------------------------------------------------------------
  89
  90 const Collector *llvm::TheCollector = 0;
  91
  92 Collector::Collector() :
  93   NeededSafePoints(0),
  94   CustomReadBarriers(false),
  95   CustomWriteBarriers(false),
  96   CustomRoots(false),
  97   InitRoots(true)
  98 {}
  99
 100 Collector::~Collector() {}
 101
 102 void Collector::addLoweringPasses(FunctionPassManager &PM) const {
 103   if (NeedsDefaultLoweringPass())
 104     PM.add(new LowerIntrinsics(*this));
 105
 106   if (NeedsCustomLoweringPass())
 107     PM.add(createCustomLoweringPass());
 108 }
 109
 110 void Collector::addLoweringPasses(PassManager &PM) const {
 111   if (NeedsDefaultLoweringPass())
 112     PM.add(new LowerIntrinsics(*this));
 113
 114   if (NeedsCustomLoweringPass())
 115     PM.add(createCustomLoweringPass());
 116 }
 117
 118 void Collector::addGenericMachineCodePass(FunctionPassManager &PM,
 119                                           const TargetMachine &TM,
 120                                           bool Fast) const {
 121   if (needsSafePoints())
 122     PM.add(new MachineCodeAnalysis(*this, TM));
 123 }
 124
 125 bool Collector::NeedsDefaultLoweringPass() const {
 126   // Default lowering is necessary only if read or write barriers have a default
 127   // action. The default for roots is no action.
 128   return !customWriteBarrier()
 129       || !customReadBarrier()
 130       || initializeRoots();
 131 }
 132
 133 bool Collector::NeedsCustomLoweringPass() const {
 134   // Custom lowering is only necessary if enabled for some action.
 135   return customWriteBarrier()
 136       || customReadBarrier()
 137       || customRoots();
 138 }
 139
 140 Pass *Collector::createCustomLoweringPass() const {
 141   cerr << "Collector must override createCustomLoweringPass.\n";
 142   abort();
 143   return 0;
 144 }
 145
 146 void Collector::beginAssembly(Module &M, std::ostream &OS, AsmPrinter &AP,
 147                               const TargetAsmInfo &TAI) const {
 148   // Default is no action.
 149 }
 150
 151 void Collector::finishAssembly(Module &M, CollectorModuleMetadata &CMM,
 152                                std::ostream &OS, AsmPrinter &AP,
 153                                const TargetAsmInfo &TAI) const {
 154   // Default is no action.
 155 }
 156
 157 // -----------------------------------------------------------------------------
 158
 159 char LowerIntrinsics::ID = 0;
 160
 161 LowerIntrinsics::LowerIntrinsics(const Collector &C)
 162   : FunctionPass((intptr_t)&ID), Coll(C),
 163     GCRootInt(0), GCReadInt(0), GCWriteInt(0) {}
 164
 165 const char *LowerIntrinsics::getPassName() const {
 166   return "Lower Garbage Collection Instructions";
 167 }
 168
 169 /// doInitialization - If this module uses the GC intrinsics, find them now. If
 170 /// not, this pass does not do anything.
 171 bool LowerIntrinsics::doInitialization(Module &M) {
 172   GCReadInt  = M.getFunction("llvm.gcread");
 173   GCWriteInt = M.getFunction("llvm.gcwrite");
 174   GCRootInt  = M.getFunction("llvm.gcroot");
 175   return false;
 176 }
 177
 178 void LowerIntrinsics::InsertRootInitializers(Function &F, AllocaInst **Roots,
 179                                                           unsigned Count) {
 180   // Scroll past alloca instructions.
 181   BasicBlock::iterator IP = F.getEntryBlock().begin();
 182   while (isa<AllocaInst>(IP)) ++IP;
 183
 184   // Search for initializers in the initial BB.
 185   SmallPtrSet<AllocaInst*,16> InitedRoots;
 186   for (; !CouldBecomeSafePoint(IP); ++IP)
 187     if (StoreInst *SI = dyn_cast<StoreInst>(IP))
 188       if (AllocaInst *AI = dyn_cast<AllocaInst>(
 189             IntrinsicInst::StripPointerCasts(SI->getOperand(1))))
 190         InitedRoots.insert(AI);
 191
 192   // Add root initializers.
 193   for (AllocaInst **I = Roots, **E = Roots + Count; I != E; ++I)
 194     if (!InitedRoots.count(*I))
 195       new StoreInst(ConstantPointerNull::get(cast<PointerType>(
 196                       cast<PointerType>((*I)->getType())->getElementType())),
 197                     *I, IP);
 198 }
 199
 200 /// CouldBecomeSafePoint - Predicate to conservatively determine whether the
 201 /// instruction could introduce a safe point.
 202 bool LowerIntrinsics::CouldBecomeSafePoint(Instruction *I) {
 203   // The natural definition of instructions which could introduce safe points
 204   // are:
 205   //
 206   //   - call, invoke (AfterCall, BeforeCall)
 207   //   - phis (Loops)
 208   //   - invoke, ret, unwind (Exit)
 209   //
 210   // However, instructions as seemingly inoccuous as arithmetic can become
 211   // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
 212   // it is necessary to take a conservative approach.
 213
 214   if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) ||
 215       isa<StoreInst>(I) || isa<LoadInst>(I))
 216     return false;
 217
 218   // llvm.gcroot is safe because it doesn't do anything at runtime.
 219   if (CallInst *CI = dyn_cast<CallInst>(I))
 220     if (Function *F = CI->getCalledFunction())
 221       if (unsigned IID = F->getIntrinsicID())
 222         if (IID == Intrinsic::gcroot)
 223           return false;
 224
 225   return true;
 226 }
 227
 228 /// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
 229 /// Leave gcroot intrinsics; the code generator needs to see those.
 230 bool LowerIntrinsics::runOnFunction(Function &F) {
 231   // Quick exit for programs that do not declare the intrinsics.
 232   if (!GCReadInt && !GCWriteInt && !GCRootInt) return false;
 233
 234   bool LowerWr = !Coll.customWriteBarrier();
 235   bool LowerRd = !Coll.customReadBarrier();
 236   bool InitRoots = Coll.initializeRoots();
 237
 238   SmallVector<AllocaInst*,32> Roots;
 239
 240   bool MadeChange = false;
 241   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 242     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
 243       if (CallInst *CI = dyn_cast<CallInst>(II++)) {
 244         Function *F = CI->getCalledFunction();
 245         if (F == GCWriteInt && LowerWr) {
 246           // Replace a write barrier with a simple store.
 247           Value *St = new StoreInst(CI->getOperand(1), CI->getOperand(3), CI);
 248           CI->replaceAllUsesWith(St);
 249           CI->eraseFromParent();
 250         } else if (F == GCReadInt && LowerRd) {
 251           // Replace a read barrier with a simple load.
 252           Value *Ld = new LoadInst(CI->getOperand(2), "", CI);
 253           Ld->takeName(CI);
 254           CI->replaceAllUsesWith(Ld);
 255           CI->eraseFromParent();
 256         } else if (F == GCRootInt && InitRoots) {
 257           // Initialize the GC root, but do not delete the intrinsic. The
 258           // backend needs the intrinsic to flag the stack slot.
 259           Roots.push_back(cast<AllocaInst>(
 260             IntrinsicInst::StripPointerCasts(CI->getOperand(1))));
 261         } else {
 262           continue;
 263         }
 264
 265         MadeChange = true;
 266       }
 267     }
 268   }
 269
 270   if (Roots.size())
 271     InsertRootInitializers(F, Roots.begin(), Roots.size());
 272
 273   return MadeChange;
 274 }
 275
 276 // -----------------------------------------------------------------------------
 277
 278 char MachineCodeAnalysis::ID = 0;
 279
 280 MachineCodeAnalysis::MachineCodeAnalysis(const Collector &C, const TargetMachine &T)
 281   : MachineFunctionPass(intptr_t(&ID)), Coll(C), Targ(T) {}
 282
 283 const char *MachineCodeAnalysis::getPassName() const {
 284   return "Analyze Machine Code For Garbage Collection";
 285 }
 286
 287 void MachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 288   MachineFunctionPass::getAnalysisUsage(AU);
 289   AU.setPreservesAll();
 290   AU.addRequired<MachineModuleInfo>();
 291   AU.addRequired<CollectorModuleMetadata>();
 292 }
 293
 294 unsigned MachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
 295                                      MachineBasicBlock::iterator MI) const {
 296   unsigned Label = MMI->NextLabelID();
 297   BuildMI(MBB, MI, TII->get(TargetInstrInfo::LABEL)).addImm(Label);
 298   return Label;
 299 }
 300
 301 void MachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
 302   // Find the return address (next instruction), too, so as to bracket the call
 303   // instruction.
 304   MachineBasicBlock::iterator RAI = CI;
 305   ++RAI;
 306
 307   if (Coll.needsSafePoint(GC::PreCall))
 308     MD->addSafePoint(GC::PreCall, InsertLabel(*CI->getParent(), CI));
 309
 310   if (Coll.needsSafePoint(GC::PostCall))
 311     MD->addSafePoint(GC::PostCall, InsertLabel(*CI->getParent(), RAI));
 312 }
 313
 314 void MachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
 315   for (MachineFunction::iterator BBI = MF.begin(),
 316                                  BBE = MF.end(); BBI != BBE; ++BBI)
 317     for (MachineBasicBlock::iterator MI = BBI->begin(),
 318                                      ME = BBI->end(); MI != ME; ++MI)
 319       if (TII->isCall(MI->getOpcode()))
 320         VisitCallPoint(*MI);
 321 }
 322
 323 void MachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
 324   uint64_t StackSize = MFI->getStackSize();
 325   uint64_t OffsetAdjustment = MFI->getOffsetAdjustment();
 326   uint64_t OffsetOfLocalArea = Targ.getFrameInfo()->getOffsetOfLocalArea();
 327
 328   for (CollectorMetadata::roots_iterator RI = MD->roots_begin(),
 329                                          RE = MD->roots_end(); RI != RE; ++RI)
 330     RI->StackOffset = MFI->getObjectOffset(RI->Num) + StackSize
 331                       - OffsetOfLocalArea + OffsetAdjustment;
 332 }
 333
 334 bool MachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
 335   if (!Coll.needsSafePoints())
 336     return false;
 337
 338   MD = getAnalysis<CollectorModuleMetadata>().get(MF.getFunction());
 339   MMI = &getAnalysis<MachineModuleInfo>();
 340   TII = MF.getTarget().getInstrInfo();
 341   MFI = MF.getFrameInfo();
 342
 343   // Find the size of the stack frame.
 344   MD->setFrameSize(MFI->getStackSize());
 345
 346   // Find all safe points.
 347   FindSafePoints(MF);
 348
 349   // Find the stack offsets for all roots.
 350   FindStackOffsets(MF);
 351
 352   return false;
 353 }