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 #include "llvm/Support/Visibility.h"
00030 using namespace llvm;
00031 
00032 namespace {
00033   class VISIBILITY_HIDDEN 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,
00113                                    (Type *)0);
00114   if (GCWriteInt)       // Make:  void %llvm_gc_write(sbyte*, sbyte**)
00115     GCWrite = M.getOrInsertFunction("llvm_gc_write", Type::VoidTy,
00116                                     VoidPtr, VoidPtr, VoidPtrPtr, (Type *)0);
00117 
00118   // If the program has GC roots, get or create the global root list.
00119   if (GCRootInt) {
00120     const StructType *RootListTy = getRootRecordType(0);
00121     const Type *PRLTy = PointerType::get(RootListTy);
00122     M.addTypeName("llvm_gc_root_ty", RootListTy);
00123 
00124     // Get the root chain if it already exists.
00125     RootChain = M.getGlobalVariable("llvm_gc_root_chain", PRLTy);
00126     if (RootChain == 0) {
00127       // If the root chain does not exist, insert a new one with linkonce
00128       // linkage!
00129       RootChain = new GlobalVariable(PRLTy, false,
00130                                      GlobalValue::LinkOnceLinkage,
00131                                      Constant::getNullValue(PRLTy),
00132                                      "llvm_gc_root_chain", &M);
00133     } else if (RootChain->hasExternalLinkage() && RootChain->isExternal()) {
00134       RootChain->setInitializer(Constant::getNullValue(PRLTy));
00135       RootChain->setLinkage(GlobalValue::LinkOnceLinkage);
00136     }
00137   }
00138   return true;
00139 }
00140 
00141 /// Coerce - If the specified operand number of the specified instruction does
00142 /// not have the specified type, insert a cast.
00143 static void Coerce(Instruction *I, unsigned OpNum, Type *Ty) {
00144   if (I->getOperand(OpNum)->getType() != Ty) {
00145     if (Constant *C = dyn_cast<Constant>(I->getOperand(OpNum)))
00146       I->setOperand(OpNum, ConstantExpr::getCast(C, Ty));
00147     else {
00148       CastInst *CI = new CastInst(I->getOperand(OpNum), Ty, "", I);
00149       I->setOperand(OpNum, CI);
00150     }
00151   }
00152 }
00153 
00154 /// runOnFunction - If the program is using GC intrinsics, replace any
00155 /// read/write intrinsics with the appropriate read/write barrier calls, then
00156 /// inline them.  Finally, build the data structures for
00157 bool LowerGC::runOnFunction(Function &F) {
00158   // Quick exit for programs that are not using GC mechanisms.
00159   if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
00160 
00161   PointerType *VoidPtr    = PointerType::get(Type::SByteTy);
00162   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
00163 
00164   // If there are read/write barriers in the program, perform a quick pass over
00165   // the function eliminating them.  While we are at it, remember where we see
00166   // calls to llvm.gcroot.
00167   std::vector<CallInst*> GCRoots;
00168   std::vector<CallInst*> NormalCalls;
00169 
00170   bool MadeChange = false;
00171   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00172     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
00173       if (CallInst *CI = dyn_cast<CallInst>(II++)) {
00174         if (!CI->getCalledFunction() ||
00175             !CI->getCalledFunction()->getIntrinsicID())
00176           NormalCalls.push_back(CI);   // Remember all normal function calls.
00177 
00178         if (Function *F = CI->getCalledFunction())
00179           if (F == GCRootInt)
00180             GCRoots.push_back(CI);
00181           else if (F == GCReadInt || F == GCWriteInt) {
00182             if (F == GCWriteInt) {
00183               // Change a llvm.gcwrite call to call llvm_gc_write instead.
00184               CI->setOperand(0, GCWrite);
00185               // Insert casts of the operands as needed.
00186               Coerce(CI, 1, VoidPtr);
00187               Coerce(CI, 2, VoidPtr);
00188               Coerce(CI, 3, VoidPtrPtr);
00189             } else {
00190               Coerce(CI, 1, VoidPtr);
00191               Coerce(CI, 2, VoidPtrPtr);
00192               if (CI->getType() == VoidPtr) {
00193                 CI->setOperand(0, GCRead);
00194               } else {
00195                 // Create a whole new call to replace the old one.
00196                 CallInst *NC = new CallInst(GCRead, CI->getOperand(1),
00197                                             CI->getOperand(2),
00198                                             CI->getName(), CI);
00199                 Value *NV = new CastInst(NC, CI->getType(), "", CI);
00200                 CI->replaceAllUsesWith(NV);
00201                 BB->getInstList().erase(CI);
00202                 CI = NC;
00203               }
00204             }
00205 
00206             MadeChange = true;
00207           }
00208       }
00209 
00210   // If there are no GC roots in this function, then there is no need to create
00211   // a GC list record for it.
00212   if (GCRoots.empty()) return MadeChange;
00213 
00214   // Okay, there are GC roots in this function.  On entry to the function, add a
00215   // record to the llvm_gc_root_chain, and remove it on exit.
00216 
00217   // Create the alloca, and zero it out.
00218   const StructType *RootListTy = getRootRecordType(GCRoots.size());
00219   AllocaInst *AI = new AllocaInst(RootListTy, 0, "gcroots", F.begin()->begin());
00220 
00221   // Insert the memset call after all of the allocas in the function.
00222   BasicBlock::iterator IP = AI;
00223   while (isa<AllocaInst>(IP)) ++IP;
00224 
00225   Constant *Zero = ConstantUInt::get(Type::UIntTy, 0);
00226   Constant *One  = ConstantUInt::get(Type::UIntTy, 1);
00227 
00228   // Get a pointer to the prev pointer.
00229   std::vector<Value*> Par;
00230   Par.push_back(Zero);
00231   Par.push_back(Zero);
00232   Value *PrevPtrPtr = new GetElementPtrInst(AI, Par, "prevptrptr", IP);
00233 
00234   // Load the previous pointer.
00235   Value *PrevPtr = new LoadInst(RootChain, "prevptr", IP);
00236   // Store the previous pointer into the prevptrptr
00237   new StoreInst(PrevPtr, PrevPtrPtr, IP);
00238 
00239   // Set the number of elements in this record.
00240   Par[1] = ConstantUInt::get(Type::UIntTy, 1);
00241   Value *NumEltsPtr = new GetElementPtrInst(AI, Par, "numeltsptr", IP);
00242   new StoreInst(ConstantUInt::get(Type::UIntTy, GCRoots.size()), NumEltsPtr,IP);
00243 
00244   Par[1] = ConstantUInt::get(Type::UIntTy, 2);
00245   Par.resize(4);
00246 
00247   const PointerType *PtrLocTy =
00248     cast<PointerType>(GCRootInt->getFunctionType()->getParamType(0));
00249   Constant *Null = ConstantPointerNull::get(PtrLocTy);
00250 
00251   // Initialize all of the gcroot records now, and eliminate them as we go.
00252   for (unsigned i = 0, e = GCRoots.size(); i != e; ++i) {
00253     // Initialize the meta-data pointer.
00254     Par[2] = ConstantUInt::get(Type::UIntTy, i);
00255     Par[3] = One;
00256     Value *MetaDataPtr = new GetElementPtrInst(AI, Par, "MetaDataPtr", IP);
00257     assert(isa<Constant>(GCRoots[i]->getOperand(2)) && "Must be a constant");
00258     new StoreInst(GCRoots[i]->getOperand(2), MetaDataPtr, IP);
00259 
00260     // Initialize the root pointer to null on entry to the function.
00261     Par[3] = Zero;
00262     Value *RootPtrPtr = new GetElementPtrInst(AI, Par, "RootEntPtr", IP);
00263     new StoreInst(Null, RootPtrPtr, IP);
00264 
00265     // Each occurrance of the llvm.gcroot intrinsic now turns into an
00266     // initialization of the slot with the address and a zeroing out of the
00267     // address specified.
00268     new StoreInst(Constant::getNullValue(PtrLocTy->getElementType()),
00269                   GCRoots[i]->getOperand(1), GCRoots[i]);
00270     new StoreInst(GCRoots[i]->getOperand(1), RootPtrPtr, GCRoots[i]);
00271     GCRoots[i]->getParent()->getInstList().erase(GCRoots[i]);
00272   }
00273 
00274   // Now that the record is all initialized, store the pointer into the global
00275   // pointer.
00276   Value *C = new CastInst(AI, PointerType::get(MainRootRecordType), "", IP);
00277   new StoreInst(C, RootChain, IP);
00278 
00279   // On exit from the function we have to remove the entry from the GC root
00280   // chain.  Doing this is straight-forward for return and unwind instructions:
00281   // just insert the appropriate copy.
00282   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00283     if (isa<UnwindInst>(BB->getTerminator()) ||
00284         isa<ReturnInst>(BB->getTerminator())) {
00285       // We could reuse the PrevPtr loaded on entry to the function, but this
00286       // would make the value live for the whole function, which is probably a
00287       // bad idea.  Just reload the value out of our stack entry.
00288       PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", BB->getTerminator());
00289       new StoreInst(PrevPtr, RootChain, BB->getTerminator());
00290     }
00291 
00292   // If an exception is thrown from a callee we have to make sure to
00293   // unconditionally take the record off the stack.  For this reason, we turn
00294   // all call instructions into invoke whose cleanup pops the entry off the
00295   // stack.  We only insert one cleanup block, which is shared by all invokes.
00296   if (!NormalCalls.empty()) {
00297     // Create the shared cleanup block.
00298     BasicBlock *Cleanup = new BasicBlock("gc_cleanup", &F);
00299     UnwindInst *UI = new UnwindInst(Cleanup);
00300     PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", UI);
00301     new StoreInst(PrevPtr, RootChain, UI);
00302 
00303     // Loop over all of the function calls, turning them into invokes.
00304     while (!NormalCalls.empty()) {
00305       CallInst *CI = NormalCalls.back();
00306       BasicBlock *CBB = CI->getParent();
00307       NormalCalls.pop_back();
00308 
00309       // Split the basic block containing the function call.
00310       BasicBlock *NewBB = CBB->splitBasicBlock(CI, CBB->getName()+".cont");
00311 
00312       // Remove the unconditional branch inserted at the end of the CBB.
00313       CBB->getInstList().pop_back();
00314       NewBB->getInstList().remove(CI);
00315 
00316       // Create a new invoke instruction.
00317       Value *II = new InvokeInst(CI->getCalledValue(), NewBB, Cleanup,
00318                                  std::vector<Value*>(CI->op_begin()+1,
00319                                                      CI->op_end()),
00320                                  CI->getName(), CBB);
00321       CI->replaceAllUsesWith(II);
00322       delete CI;
00323     }
00324   }
00325 
00326   return true;
00327 }