LLVM API Documentation
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 }