lib/CodeGen/Collector.cpp

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