LLVM API Documentation

LowerGC.cpp

Go to the documentation of this file.
00001 //===-- LowerGC.cpp - Provide GC support for targets that don't -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements lowering for the llvm.gc* intrinsics for targets that do
00011 // not natively support them (which includes the C backend).  Note that the code
00012 // generated is not as efficient as it would be for targets that natively
00013 // support the GC intrinsics, but it is useful for getting new targets
00014 // up-and-running quickly.
00015 //
00016 // This pass implements the code transformation described in this paper:
00017 //   "Accurate Garbage Collection in an Uncooperative Environment"
00018 //   Fergus Henderson, ISMM, 2002
00019 //
00020 //===----------------------------------------------------------------------===//
00021 
00022 #define DEBUG_TYPE "lowergc"
00023 #include "llvm/Transforms/Scalar.h"
00024 #include "llvm/Constants.h"
00025 #include "llvm/DerivedTypes.h"
00026 #include "llvm/Instructions.h"
00027 #include "llvm/Module.h"
00028 #include "llvm/Pass.h"
00029 using namespace llvm;
00030 
00031 namespace {
00032   class LowerGC : public FunctionPass {
00033     /// GCRootInt, GCReadInt, GCWriteInt - The function prototypes for the
00034     /// llvm.gcread/llvm.gcwrite/llvm.gcroot intrinsics.
00035     Function *GCRootInt, *GCReadInt, *GCWriteInt;
00036 
00037     /// GCRead/GCWrite - These are the functions provided by the garbage
00038     /// collector for read/write barriers.
00039     Function *GCRead, *GCWrite;
00040 
00041     /// RootChain - This is the global linked-list that contains the chain of GC
00042     /// roots.
00043     GlobalVariable *RootChain;
00044 
00045     /// MainRootRecordType - This is the type for a function root entry if it
00046     /// had zero roots.
00047     const Type *MainRootRecordType;
00048   public:
00049     LowerGC() : GCRootInt(0), GCReadInt(0), GCWriteInt(0),
00050                 GCRead(0), GCWrite(0), RootChain(0), MainRootRecordType(0) {}
00051     virtual bool doInitialization(Module &M);
00052     virtual bool runOnFunction(Function &F);
00053 
00054   private:
00055     const StructType *getRootRecordType(unsigned NumRoots);
00056   };
00057 
00058   RegisterOpt<LowerGC>
00059   X("lowergc", "Lower GC intrinsics, for GCless code generators");
00060 }
00061 
00062 /// createLowerGCPass - This function returns an instance of the "lowergc"
00063 /// pass, which lowers garbage collection intrinsics to normal LLVM code.
00064 FunctionPass *llvm::createLowerGCPass() {
00065   return new LowerGC();
00066 }
00067 
00068 /// getRootRecordType - This function creates and returns the type for a root
00069 /// record containing 'NumRoots' roots.
00070 const StructType *LowerGC::getRootRecordType(unsigned NumRoots) {
00071   // Build a struct that is a type used for meta-data/root pairs.
00072   std::vector<const Type *> ST;
00073   ST.push_back(GCRootInt->getFunctionType()->getParamType(0));
00074   ST.push_back(GCRootInt->getFunctionType()->getParamType(1));
00075   StructType *PairTy = StructType::get(ST);
00076 
00077   // Build the array of pairs.
00078   ArrayType *PairArrTy = ArrayType::get(PairTy, NumRoots);
00079 
00080   // Now build the recursive list type.
00081   PATypeHolder RootListH =
00082     MainRootRecordType ? (Type*)MainRootRecordType : (Type*)OpaqueType::get();
00083   ST.clear();
00084   ST.push_back(PointerType::get(RootListH));         // Prev pointer
00085   ST.push_back(Type::UIntTy);                        // NumElements in array
00086   ST.push_back(PairArrTy);                           // The pairs
00087   StructType *RootList = StructType::get(ST);
00088   if (MainRootRecordType)
00089     return RootList;
00090 
00091   assert(NumRoots == 0 && "The main struct type should have zero entries!");
00092   cast<OpaqueType>((Type*)RootListH.get())->refineAbstractTypeTo(RootList);
00093   MainRootRecordType = RootListH;
00094   return cast<StructType>(RootListH.get());
00095 }
00096 
00097 /// doInitialization - If this module uses the GC intrinsics, find them now.  If
00098 /// not, this pass does not do anything.
00099 bool LowerGC::doInitialization(Module &M) {
00100   GCRootInt  = M.getNamedFunction("llvm.gcroot");
00101   GCReadInt  = M.getNamedFunction("llvm.gcread");
00102   GCWriteInt = M.getNamedFunction("llvm.gcwrite");
00103   if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
00104 
00105   PointerType *VoidPtr = PointerType::get(Type::SByteTy);
00106   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
00107 
00108   // If the program is using read/write barriers, find the implementations of
00109   // them from the GC runtime library.
00110   if (GCReadInt)        // Make:  sbyte* %llvm_gc_read(sbyte**)
00111     GCRead = M.getOrInsertFunction("llvm_gc_read", VoidPtr, VoidPtr, VoidPtrPtr,
00112                                    (Type *)0);
00113   if (GCWriteInt)       // Make:  void %llvm_gc_write(sbyte*, sbyte**)
00114     GCWrite = M.getOrInsertFunction("llvm_gc_write", Type::VoidTy,
00115                                     VoidPtr, VoidPtr, VoidPtrPtr, (Type *)0);
00116 
00117   // If the program has GC roots, get or create the global root list.
00118   if (GCRootInt) {
00119     const StructType *RootListTy = getRootRecordType(0);
00120     const Type *PRLTy = PointerType::get(RootListTy);
00121     M.addTypeName("llvm_gc_root_ty", RootListTy);
00122 
00123     // Get the root chain if it already exists.
00124     RootChain = M.getGlobalVariable("llvm_gc_root_chain", PRLTy);
00125     if (RootChain == 0) {
00126       // If the root chain does not exist, insert a new one with linkonce
00127       // linkage!
00128       RootChain = new GlobalVariable(PRLTy, false,
00129                                      GlobalValue::LinkOnceLinkage,
00130                                      Constant::getNullValue(PRLTy),
00131                                      "llvm_gc_root_chain", &M);
00132     } else if (RootChain->hasExternalLinkage() && RootChain->isExternal()) {
00133       RootChain->setInitializer(Constant::getNullValue(PRLTy));
00134       RootChain->setLinkage(GlobalValue::LinkOnceLinkage);
00135     }
00136   }
00137   return true;
00138 }
00139 
00140 /// Coerce - If the specified operand number of the specified instruction does
00141 /// not have the specified type, insert a cast.
00142 static void Coerce(Instruction *I, unsigned OpNum, Type *Ty) {
00143   if (I->getOperand(OpNum)->getType() != Ty) {
00144     if (Constant *C = dyn_cast<Constant>(I->getOperand(OpNum)))
00145       I->setOperand(OpNum, ConstantExpr::getCast(C, Ty));
00146     else {
00147       CastInst *CI = new CastInst(I->getOperand(OpNum), Ty, "", I);
00148       I->setOperand(OpNum, CI);
00149     }
00150   }
00151 }
00152 
00153 /// runOnFunction - If the program is using GC intrinsics, replace any
00154 /// read/write intrinsics with the appropriate read/write barrier calls, then
00155 /// inline them.  Finally, build the data structures for
00156 bool LowerGC::runOnFunction(Function &F) {
00157   // Quick exit for programs that are not using GC mechanisms.
00158   if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
00159 
00160   PointerType *VoidPtr    = PointerType::get(Type::SByteTy);
00161   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
00162 
00163   // If there are read/write barriers in the program, perform a quick pass over
00164   // the function eliminating them.  While we are at it, remember where we see
00165   // calls to llvm.gcroot.
00166   std::vector<CallInst*> GCRoots;
00167   std::vector<CallInst*> NormalCalls;
00168 
00169   bool MadeChange = false;
00170   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00171     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
00172       if (CallInst *CI = dyn_cast<CallInst>(II++)) {
00173         if (!CI->getCalledFunction() ||
00174             !CI->getCalledFunction()->getIntrinsicID())
00175           NormalCalls.push_back(CI);   // Remember all normal function calls.
00176 
00177         if (Function *F = CI->getCalledFunction())
00178           if (F == GCRootInt)
00179             GCRoots.push_back(CI);
00180           else if (F == GCReadInt || F == GCWriteInt) {
00181             if (F == GCWriteInt) {
00182               // Change a llvm.gcwrite call to call llvm_gc_write instead.
00183               CI->setOperand(0, GCWrite);
00184               // Insert casts of the operands as needed.
00185               Coerce(CI, 1, VoidPtr);
00186               Coerce(CI, 2, VoidPtr);
00187               Coerce(CI, 3, VoidPtrPtr);
00188             } else {
00189               Coerce(CI, 1, VoidPtr);
00190               Coerce(CI, 2, VoidPtrPtr);
00191               if (CI->getType() == VoidPtr) {
00192                 CI->setOperand(0, GCRead);
00193               } else {
00194                 // Create a whole new call to replace the old one.
00195                 CallInst *NC = new CallInst(GCRead, CI->getOperand(1),
00196                                             CI->getOperand(2),
00197                                             CI->getName(), CI);
00198                 Value *NV = new CastInst(NC, CI->getType(), "", CI);
00199                 CI->replaceAllUsesWith(NV);
00200                 BB->getInstList().erase(CI);
00201                 CI = NC;
00202               }
00203             }
00204 
00205             MadeChange = true;
00206           }
00207       }
00208 
00209   // If there are no GC roots in this function, then there is no need to create
00210   // a GC list record for it.
00211   if (GCRoots.empty()) return MadeChange;
00212 
00213   // Okay, there are GC roots in this function.  On entry to the function, add a
00214   // record to the llvm_gc_root_chain, and remove it on exit.
00215 
00216   // Create the alloca, and zero it out.
00217   const StructType *RootListTy = getRootRecordType(GCRoots.size());
00218   AllocaInst *AI = new AllocaInst(RootListTy, 0, "gcroots", F.begin()->begin());
00219 
00220   // Insert the memset call after all of the allocas in the function.
00221   BasicBlock::iterator IP = AI;
00222   while (isa<AllocaInst>(IP)) ++IP;
00223 
00224   Constant *Zero = ConstantUInt::get(Type::UIntTy, 0);
00225   Constant *One  = ConstantUInt::get(Type::UIntTy, 1);
00226 
00227   // Get a pointer to the prev pointer.
00228   std::vector<Value*> Par;
00229   Par.push_back(Zero);
00230   Par.push_back(Zero);
00231   Value *PrevPtrPtr = new GetElementPtrInst(AI, Par, "prevptrptr", IP);
00232 
00233   // Load the previous pointer.
00234   Value *PrevPtr = new LoadInst(RootChain, "prevptr", IP);
00235   // Store the previous pointer into the prevptrptr
00236   new StoreInst(PrevPtr, PrevPtrPtr, IP);
00237 
00238   // Set the number of elements in this record.
00239   Par[1] = ConstantUInt::get(Type::UIntTy, 1);
00240   Value *NumEltsPtr = new GetElementPtrInst(AI, Par, "numeltsptr", IP);
00241   new StoreInst(ConstantUInt::get(Type::UIntTy, GCRoots.size()), NumEltsPtr,IP);
00242 
00243   Par[1] = ConstantUInt::get(Type::UIntTy, 2);
00244   Par.resize(4);
00245 
00246   const PointerType *PtrLocTy =
00247     cast<PointerType>(GCRootInt->getFunctionType()->getParamType(0));
00248   Constant *Null = ConstantPointerNull::get(PtrLocTy);
00249 
00250   // Initialize all of the gcroot records now, and eliminate them as we go.
00251   for (unsigned i = 0, e = GCRoots.size(); i != e; ++i) {
00252     // Initialize the meta-data pointer.
00253     Par[2] = ConstantUInt::get(Type::UIntTy, i);
00254     Par[3] = One;
00255     Value *MetaDataPtr = new GetElementPtrInst(AI, Par, "MetaDataPtr", IP);
00256     assert(isa<Constant>(GCRoots[i]->getOperand(2)) && "Must be a constant");
00257     new StoreInst(GCRoots[i]->getOperand(2), MetaDataPtr, IP);
00258 
00259     // Initialize the root pointer to null on entry to the function.
00260     Par[3] = Zero;
00261     Value *RootPtrPtr = new GetElementPtrInst(AI, Par, "RootEntPtr", IP);
00262     new StoreInst(Null, RootPtrPtr, IP);
00263 
00264     // Each occurrance of the llvm.gcroot intrinsic now turns into an
00265     // initialization of the slot with the address and a zeroing out of the
00266     // address specified.
00267     new StoreInst(Constant::getNullValue(PtrLocTy->getElementType()),
00268                   GCRoots[i]->getOperand(1), GCRoots[i]);
00269     new StoreInst(GCRoots[i]->getOperand(1), RootPtrPtr, GCRoots[i]);
00270     GCRoots[i]->getParent()->getInstList().erase(GCRoots[i]);
00271   }
00272 
00273   // Now that the record is all initialized, store the pointer into the global
00274   // pointer.
00275   Value *C = new CastInst(AI, PointerType::get(MainRootRecordType), "", IP);
00276   new StoreInst(C, RootChain, IP);
00277 
00278   // On exit from the function we have to remove the entry from the GC root
00279   // chain.  Doing this is straight-forward for return and unwind instructions:
00280   // just insert the appropriate copy.
00281   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00282     if (isa<UnwindInst>(BB->getTerminator()) ||
00283         isa<ReturnInst>(BB->getTerminator())) {
00284       // We could reuse the PrevPtr loaded on entry to the function, but this
00285       // would make the value live for the whole function, which is probably a
00286       // bad idea.  Just reload the value out of our stack entry.
00287       PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", BB->getTerminator());
00288       new StoreInst(PrevPtr, RootChain, BB->getTerminator());
00289     }
00290 
00291   // If an exception is thrown from a callee we have to make sure to
00292   // unconditionally take the record off the stack.  For this reason, we turn
00293   // all call instructions into invoke whose cleanup pops the entry off the
00294   // stack.  We only insert one cleanup block, which is shared by all invokes.
00295   if (!NormalCalls.empty()) {
00296     // Create the shared cleanup block.
00297     BasicBlock *Cleanup = new BasicBlock("gc_cleanup", &F);
00298     UnwindInst *UI = new UnwindInst(Cleanup);
00299     PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", UI);
00300     new StoreInst(PrevPtr, RootChain, UI);
00301 
00302     // Loop over all of the function calls, turning them into invokes.
00303     while (!NormalCalls.empty()) {
00304       CallInst *CI = NormalCalls.back();
00305       BasicBlock *CBB = CI->getParent();
00306       NormalCalls.pop_back();
00307 
00308       // Split the basic block containing the function call.
00309       BasicBlock *NewBB = CBB->splitBasicBlock(CI, CBB->getName()+".cont");
00310 
00311       // Remove the unconditional branch inserted at the end of the CBB.
00312       CBB->getInstList().pop_back();
00313       NewBB->getInstList().remove(CI);
00314 
00315       // Create a new invoke instruction.
00316       Value *II = new InvokeInst(CI->getCalledValue(), NewBB, Cleanup,
00317                                  std::vector<Value*>(CI->op_begin()+1,
00318                                                      CI->op_end()),
00319                                  CI->getName(), CBB);
00320       CI->replaceAllUsesWith(II);
00321       delete CI;
00322     }
00323   }
00324 
00325   return true;
00326 }