LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 #include "llvm/Transforms/Utils/Cloning.h"
00030 using namespace llvm;
00031 
00032 namespace {
00033   class LowerGC : public FunctionPass {
00034     /// GCRootInt, GCReadInt, GCWriteInt - The function prototypes for the
00035     /// llvm.gcread/llvm.gcwrite/llvm.gcroot intrinsics.
00036     Function *GCRootInt, *GCReadInt, *GCWriteInt;
00037 
00038     /// GCRead/GCWrite - These are the functions provided by the garbage
00039     /// collector for read/write barriers.
00040     Function *GCRead, *GCWrite;
00041 
00042     /// RootChain - This is the global linked-list that contains the chain of GC
00043     /// roots.
00044     GlobalVariable *RootChain;
00045 
00046     /// MainRootRecordType - This is the type for a function root entry if it
00047     /// had zero roots.
00048     const Type *MainRootRecordType;
00049   public:
00050     LowerGC() : GCRootInt(0), GCReadInt(0), GCWriteInt(0), 
00051                 GCRead(0), GCWrite(0), RootChain(0), MainRootRecordType(0) {}
00052     virtual bool doInitialization(Module &M);
00053     virtual bool runOnFunction(Function &F);
00054 
00055   private:
00056     const StructType *getRootRecordType(unsigned NumRoots);
00057   };
00058 
00059   RegisterOpt<LowerGC>
00060   X("lowergc", "Lower GC intrinsics, for GCless code generators");
00061 }
00062 
00063 /// createLowerGCPass - This function returns an instance of the "lowergc"
00064 /// pass, which lowers garbage collection intrinsics to normal LLVM code.
00065 FunctionPass *llvm::createLowerGCPass() {
00066   return new LowerGC();
00067 }
00068 
00069 /// getRootRecordType - This function creates and returns the type for a root
00070 /// record containing 'NumRoots' roots.
00071 const StructType *LowerGC::getRootRecordType(unsigned NumRoots) {
00072   // Build a struct that is a type used for meta-data/root pairs.
00073   std::vector<const Type *> ST;
00074   ST.push_back(GCRootInt->getFunctionType()->getParamType(0));
00075   ST.push_back(GCRootInt->getFunctionType()->getParamType(1));
00076   StructType *PairTy = StructType::get(ST);
00077 
00078   // Build the array of pairs.
00079   ArrayType *PairArrTy = ArrayType::get(PairTy, NumRoots);
00080 
00081   // Now build the recursive list type.
00082   PATypeHolder RootListH =
00083     MainRootRecordType ? (Type*)MainRootRecordType : (Type*)OpaqueType::get();
00084   ST.clear();
00085   ST.push_back(PointerType::get(RootListH));         // Prev pointer
00086   ST.push_back(Type::UIntTy);                        // NumElements in array
00087   ST.push_back(PairArrTy);                           // The pairs
00088   StructType *RootList = StructType::get(ST);
00089   if (MainRootRecordType)
00090     return RootList;
00091 
00092   assert(NumRoots == 0 && "The main struct type should have zero entries!");
00093   cast<OpaqueType>((Type*)RootListH.get())->refineAbstractTypeTo(RootList);
00094   MainRootRecordType = RootListH;
00095   return cast<StructType>(RootListH.get());
00096 }
00097 
00098 /// doInitialization - If this module uses the GC intrinsics, find them now.  If
00099 /// not, this pass does not do anything.
00100 bool LowerGC::doInitialization(Module &M) {
00101   GCRootInt  = M.getNamedFunction("llvm.gcroot");
00102   GCReadInt  = M.getNamedFunction("llvm.gcread");
00103   GCWriteInt = M.getNamedFunction("llvm.gcwrite");
00104   if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
00105 
00106   PointerType *VoidPtr = PointerType::get(Type::SByteTy);
00107   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
00108 
00109   // If the program is using read/write barriers, find the implementations of
00110   // them from the GC runtime library.
00111   if (GCReadInt)        // Make:  sbyte* %llvm_gc_read(sbyte**)
00112     GCRead = M.getOrInsertFunction("llvm_gc_read", VoidPtr, VoidPtr, VoidPtrPtr, 0);
00113   if (GCWriteInt)       // Make:  void %llvm_gc_write(sbyte*, sbyte**)
00114     GCWrite = M.getOrInsertFunction("llvm_gc_write", Type::VoidTy,
00115                                     VoidPtr, VoidPtr, VoidPtrPtr, 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             // Now that we made the replacement, inline expand the call if
00206             // possible, otherwise things will be too horribly expensive.
00207             InlineFunction(CI);
00208             MadeChange = true;
00209           }
00210       }
00211   
00212   // If there are no GC roots in this function, then there is no need to create
00213   // a GC list record for it.
00214   if (GCRoots.empty()) return MadeChange;
00215 
00216   // Okay, there are GC roots in this function.  On entry to the function, add a
00217   // record to the llvm_gc_root_chain, and remove it on exit.
00218 
00219   // Create the alloca, and zero it out.
00220   const StructType *RootListTy = getRootRecordType(GCRoots.size());
00221   AllocaInst *AI = new AllocaInst(RootListTy, 0, "gcroots", F.begin()->begin());
00222 
00223   // Insert the memset call after all of the allocas in the function.
00224   BasicBlock::iterator IP = AI;
00225   while (isa<AllocaInst>(IP)) ++IP;
00226 
00227   Constant *Zero = ConstantUInt::get(Type::UIntTy, 0);
00228   Constant *One  = ConstantUInt::get(Type::UIntTy, 1);
00229 
00230   // Get a pointer to the prev pointer.
00231   std::vector<Value*> Par;
00232   Par.push_back(Zero);
00233   Par.push_back(Zero);
00234   Value *PrevPtrPtr = new GetElementPtrInst(AI, Par, "prevptrptr", IP);
00235 
00236   // Load the previous pointer.
00237   Value *PrevPtr = new LoadInst(RootChain, "prevptr", IP);
00238   // Store the previous pointer into the prevptrptr
00239   new StoreInst(PrevPtr, PrevPtrPtr, IP);
00240 
00241   // Set the number of elements in this record.
00242   Par[1] = ConstantUInt::get(Type::UIntTy, 1);
00243   Value *NumEltsPtr = new GetElementPtrInst(AI, Par, "numeltsptr", IP);
00244   new StoreInst(ConstantUInt::get(Type::UIntTy, GCRoots.size()), NumEltsPtr,IP);
00245 
00246   Par[1] = ConstantUInt::get(Type::UIntTy, 2);
00247   Par.resize(4);
00248 
00249   const PointerType *PtrLocTy =
00250     cast<PointerType>(GCRootInt->getFunctionType()->getParamType(0));
00251   Constant *Null = ConstantPointerNull::get(PtrLocTy);
00252 
00253   // Initialize all of the gcroot records now, and eliminate them as we go.
00254   for (unsigned i = 0, e = GCRoots.size(); i != e; ++i) {
00255     // Initialize the meta-data pointer.
00256     Par[2] = ConstantUInt::get(Type::UIntTy, i);
00257     Par[3] = One;
00258     Value *MetaDataPtr = new GetElementPtrInst(AI, Par, "MetaDataPtr", IP);
00259     assert(isa<Constant>(GCRoots[i]->getOperand(2)) && "Must be a constant");
00260     new StoreInst(GCRoots[i]->getOperand(2), MetaDataPtr, IP);
00261 
00262     // Initialize the root pointer to null on entry to the function.
00263     Par[3] = Zero;
00264     Value *RootPtrPtr = new GetElementPtrInst(AI, Par, "RootEntPtr", IP);
00265     new StoreInst(Null, RootPtrPtr, IP);
00266     
00267     // Each occurrance of the llvm.gcroot intrinsic now turns into an
00268     // initialization of the slot with the address and a zeroing out of the
00269     // address specified.
00270     new StoreInst(Constant::getNullValue(PtrLocTy->getElementType()),
00271                   GCRoots[i]->getOperand(1), GCRoots[i]);
00272     new StoreInst(GCRoots[i]->getOperand(1), RootPtrPtr, GCRoots[i]);
00273     GCRoots[i]->getParent()->getInstList().erase(GCRoots[i]);
00274   }
00275 
00276   // Now that the record is all initialized, store the pointer into the global
00277   // pointer.
00278   Value *C = new CastInst(AI, PointerType::get(MainRootRecordType), "", IP);
00279   new StoreInst(C, RootChain, IP);
00280 
00281   // On exit from the function we have to remove the entry from the GC root
00282   // chain.  Doing this is straight-forward for return and unwind instructions:
00283   // just insert the appropriate copy.
00284   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00285     if (isa<UnwindInst>(BB->getTerminator()) ||
00286         isa<ReturnInst>(BB->getTerminator())) {
00287       // We could reuse the PrevPtr loaded on entry to the function, but this
00288       // would make the value live for the whole function, which is probably a
00289       // bad idea.  Just reload the value out of our stack entry.
00290       PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", BB->getTerminator());
00291       new StoreInst(PrevPtr, RootChain, BB->getTerminator());
00292     }
00293 
00294   // If an exception is thrown from a callee we have to make sure to
00295   // unconditionally take the record off the stack.  For this reason, we turn
00296   // all call instructions into invoke whose cleanup pops the entry off the
00297   // stack.  We only insert one cleanup block, which is shared by all invokes.
00298   if (!NormalCalls.empty()) {
00299     // Create the shared cleanup block.
00300     BasicBlock *Cleanup = new BasicBlock("gc_cleanup", &F);
00301     UnwindInst *UI = new UnwindInst(Cleanup);
00302     PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", UI);
00303     new StoreInst(PrevPtr, RootChain, UI);
00304   
00305     // Loop over all of the function calls, turning them into invokes.
00306     while (!NormalCalls.empty()) {
00307       CallInst *CI = NormalCalls.back();
00308       BasicBlock *CBB = CI->getParent();
00309       NormalCalls.pop_back();
00310 
00311       // Split the basic block containing the function call.
00312       BasicBlock *NewBB = CBB->splitBasicBlock(CI, CBB->getName()+".cont");
00313 
00314       // Remove the unconditional branch inserted at the end of the CBB.
00315       CBB->getInstList().pop_back();
00316       NewBB->getInstList().remove(CI);
00317       
00318       // Create a new invoke instruction.
00319       Value *II = new InvokeInst(CI->getCalledValue(), NewBB, Cleanup,
00320                                  std::vector<Value*>(CI->op_begin()+1,
00321                                                      CI->op_end()),
00322                                  CI->getName(), CBB);
00323       CI->replaceAllUsesWith(II);
00324       delete CI;
00325     }
00326   }
00327 
00328   return true;
00329 }