1 //===-- LowerGC.cpp - Provide GC support for targets that don't -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements lowering for the llvm.gc* intrinsics for targets that do
11 // not natively support them (which includes the C backend). Note that the code
12 // generated is not as efficient as it would be for targets that natively
13 // support the GC intrinsics, but it is useful for getting new targets
14 // up-and-running quickly.
16 // This pass implements the code transformation described in this paper:
17 // "Accurate Garbage Collection in an Uncooperative Environment"
18 // Fergus Henderson, ISMM, 2002
20 //===----------------------------------------------------------------------===//
22 #define DEBUG_TYPE "lowergc"
23 #include "llvm/Transforms/Scalar.h"
24 #include "llvm/Constants.h"
25 #include "llvm/DerivedTypes.h"
26 #include "llvm/Instructions.h"
27 #include "llvm/Module.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Compiler.h"
30 #include "llvm/ADT/SmallVector.h"
34 class VISIBILITY_HIDDEN LowerGC : public FunctionPass {
35 /// GCRootInt, GCReadInt, GCWriteInt - The function prototypes for the
36 /// llvm.gcread/llvm.gcwrite/llvm.gcroot intrinsics.
37 Function *GCRootInt, *GCReadInt, *GCWriteInt;
39 /// GCRead/GCWrite - These are the functions provided by the garbage
40 /// collector for read/write barriers.
41 Constant *GCRead, *GCWrite;
43 /// RootChain - This is the global linked-list that contains the chain of GC
45 GlobalVariable *RootChain;
47 /// MainRootRecordType - This is the type for a function root entry if it
49 const Type *MainRootRecordType;
51 static char ID; // Pass identification, replacement for typeid
52 LowerGC() : FunctionPass((intptr_t)&ID),
53 GCRootInt(0), GCReadInt(0), GCWriteInt(0),
54 GCRead(0), GCWrite(0), RootChain(0), MainRootRecordType(0) {}
55 virtual bool doInitialization(Module &M);
56 virtual bool runOnFunction(Function &F);
59 const StructType *getRootRecordType(unsigned NumRoots);
64 X("lowergc", "Lower GC intrinsics, for GCless code generators");
67 /// createLowerGCPass - This function returns an instance of the "lowergc"
68 /// pass, which lowers garbage collection intrinsics to normal LLVM code.
69 FunctionPass *llvm::createLowerGCPass() {
73 /// getRootRecordType - This function creates and returns the type for a root
74 /// record containing 'NumRoots' roots.
75 const StructType *LowerGC::getRootRecordType(unsigned NumRoots) {
76 // Build a struct that is a type used for meta-data/root pairs.
77 std::vector<const Type *> ST;
78 ST.push_back(GCRootInt->getFunctionType()->getParamType(0));
79 ST.push_back(GCRootInt->getFunctionType()->getParamType(1));
80 StructType *PairTy = StructType::get(ST);
82 // Build the array of pairs.
83 ArrayType *PairArrTy = ArrayType::get(PairTy, NumRoots);
85 // Now build the recursive list type.
86 PATypeHolder RootListH =
87 MainRootRecordType ? (Type*)MainRootRecordType : (Type*)OpaqueType::get();
89 ST.push_back(PointerType::get(RootListH)); // Prev pointer
90 ST.push_back(Type::Int32Ty); // NumElements in array
91 ST.push_back(PairArrTy); // The pairs
92 StructType *RootList = StructType::get(ST);
93 if (MainRootRecordType)
96 assert(NumRoots == 0 && "The main struct type should have zero entries!");
97 cast<OpaqueType>((Type*)RootListH.get())->refineAbstractTypeTo(RootList);
98 MainRootRecordType = RootListH;
99 return cast<StructType>(RootListH.get());
102 /// doInitialization - If this module uses the GC intrinsics, find them now. If
103 /// not, this pass does not do anything.
104 bool LowerGC::doInitialization(Module &M) {
105 GCRootInt = M.getFunction("llvm.gcroot");
106 GCReadInt = M.getFunction("llvm.gcread");
107 GCWriteInt = M.getFunction("llvm.gcwrite");
108 if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
110 PointerType *VoidPtr = PointerType::get(Type::Int8Ty);
111 PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
113 // If the program is using read/write barriers, find the implementations of
114 // them from the GC runtime library.
115 if (GCReadInt) // Make: sbyte* %llvm_gc_read(sbyte**)
116 GCRead = M.getOrInsertFunction("llvm_gc_read", VoidPtr, VoidPtr, VoidPtrPtr,
118 if (GCWriteInt) // Make: void %llvm_gc_write(sbyte*, sbyte**)
119 GCWrite = M.getOrInsertFunction("llvm_gc_write", Type::VoidTy,
120 VoidPtr, VoidPtr, VoidPtrPtr, (Type *)0);
122 // If the program has GC roots, get or create the global root list.
124 const StructType *RootListTy = getRootRecordType(0);
125 const Type *PRLTy = PointerType::get(RootListTy);
126 M.addTypeName("llvm_gc_root_ty", RootListTy);
128 // Get the root chain if it already exists.
129 RootChain = M.getGlobalVariable("llvm_gc_root_chain", PRLTy);
130 if (RootChain == 0) {
131 // If the root chain does not exist, insert a new one with linkonce
133 RootChain = new GlobalVariable(PRLTy, false,
134 GlobalValue::LinkOnceLinkage,
135 Constant::getNullValue(PRLTy),
136 "llvm_gc_root_chain", &M);
137 } else if (RootChain->hasExternalLinkage() && RootChain->isDeclaration()) {
138 RootChain->setInitializer(Constant::getNullValue(PRLTy));
139 RootChain->setLinkage(GlobalValue::LinkOnceLinkage);
145 /// Coerce - If the specified operand number of the specified instruction does
146 /// not have the specified type, insert a cast. Note that this only uses BitCast
147 /// because the types involved are all pointers.
148 static void Coerce(Instruction *I, unsigned OpNum, Type *Ty) {
149 if (I->getOperand(OpNum)->getType() != Ty) {
150 if (Constant *C = dyn_cast<Constant>(I->getOperand(OpNum)))
151 I->setOperand(OpNum, ConstantExpr::getBitCast(C, Ty));
153 CastInst *CI = new BitCastInst(I->getOperand(OpNum), Ty, "", I);
154 I->setOperand(OpNum, CI);
159 /// runOnFunction - If the program is using GC intrinsics, replace any
160 /// read/write intrinsics with the appropriate read/write barrier calls, then
161 /// inline them. Finally, build the data structures for
162 bool LowerGC::runOnFunction(Function &F) {
163 // Quick exit for programs that are not using GC mechanisms.
164 if (!GCRootInt && !GCReadInt && !GCWriteInt) return false;
166 PointerType *VoidPtr = PointerType::get(Type::Int8Ty);
167 PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
169 // If there are read/write barriers in the program, perform a quick pass over
170 // the function eliminating them. While we are at it, remember where we see
171 // calls to llvm.gcroot.
172 std::vector<CallInst*> GCRoots;
173 std::vector<CallInst*> NormalCalls;
175 bool MadeChange = false;
176 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
177 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
178 if (CallInst *CI = dyn_cast<CallInst>(II++)) {
179 if (!CI->getCalledFunction() ||
180 !CI->getCalledFunction()->getIntrinsicID())
181 NormalCalls.push_back(CI); // Remember all normal function calls.
183 if (Function *F = CI->getCalledFunction())
185 GCRoots.push_back(CI);
186 else if (F == GCReadInt || F == GCWriteInt) {
187 if (F == GCWriteInt) {
188 // Change a llvm.gcwrite call to call llvm_gc_write instead.
189 CI->setOperand(0, GCWrite);
190 // Insert casts of the operands as needed.
191 Coerce(CI, 1, VoidPtr);
192 Coerce(CI, 2, VoidPtr);
193 Coerce(CI, 3, VoidPtrPtr);
195 Coerce(CI, 1, VoidPtr);
196 Coerce(CI, 2, VoidPtrPtr);
197 if (CI->getType() == VoidPtr) {
198 CI->setOperand(0, GCRead);
200 // Create a whole new call to replace the old one.
202 // It sure would be nice to pass op_begin()+1,
203 // op_begin()+2 but it runs into trouble with
204 // CallInst::init's &*ierator, which requires a
205 // conversion from Use* to Value*. The conversion
206 // from Use to Value * is not useful because the
207 // memory for Value * won't be contiguous.
208 SmallVector<Value *, 2> Args;
209 Args.push_back(CI->getOperand(1));
210 Args.push_back(CI->getOperand(2));
211 CallInst *NC = new CallInst(GCRead, Args.begin(),
214 // These functions only deal with ptr type results so BitCast
215 // is the correct kind of cast (no-op cast).
216 Value *NV = new BitCastInst(NC, CI->getType(), "", CI);
217 CI->replaceAllUsesWith(NV);
218 BB->getInstList().erase(CI);
227 // If there are no GC roots in this function, then there is no need to create
228 // a GC list record for it.
229 if (GCRoots.empty()) return MadeChange;
231 // Okay, there are GC roots in this function. On entry to the function, add a
232 // record to the llvm_gc_root_chain, and remove it on exit.
234 // Create the alloca, and zero it out.
235 const StructType *RootListTy = getRootRecordType(GCRoots.size());
236 AllocaInst *AI = new AllocaInst(RootListTy, 0, "gcroots", F.begin()->begin());
238 // Insert the memset call after all of the allocas in the function.
239 BasicBlock::iterator IP = AI;
240 while (isa<AllocaInst>(IP)) ++IP;
242 Constant *Zero = ConstantInt::get(Type::Int32Ty, 0);
243 Constant *One = ConstantInt::get(Type::Int32Ty, 1);
245 // Get a pointer to the prev pointer.
246 Value *PrevPtrPtr = new GetElementPtrInst(AI, Zero, Zero, "prevptrptr", IP);
248 // Load the previous pointer.
249 Value *PrevPtr = new LoadInst(RootChain, "prevptr", IP);
250 // Store the previous pointer into the prevptrptr
251 new StoreInst(PrevPtr, PrevPtrPtr, IP);
253 // Set the number of elements in this record.
254 Value *NumEltsPtr = new GetElementPtrInst(AI, Zero, One, "numeltsptr", IP);
255 new StoreInst(ConstantInt::get(Type::Int32Ty, GCRoots.size()), NumEltsPtr,IP);
259 Par[1] = ConstantInt::get(Type::Int32Ty, 2);
261 const PointerType *PtrLocTy =
262 cast<PointerType>(GCRootInt->getFunctionType()->getParamType(0));
263 Constant *Null = ConstantPointerNull::get(PtrLocTy);
265 // Initialize all of the gcroot records now, and eliminate them as we go.
266 for (unsigned i = 0, e = GCRoots.size(); i != e; ++i) {
267 // Initialize the meta-data pointer.
268 Par[2] = ConstantInt::get(Type::Int32Ty, i);
270 Value *MetaDataPtr = new GetElementPtrInst(AI, Par, 4, "MetaDataPtr", IP);
271 assert(isa<Constant>(GCRoots[i]->getOperand(2)) && "Must be a constant");
272 new StoreInst(GCRoots[i]->getOperand(2), MetaDataPtr, IP);
274 // Initialize the root pointer to null on entry to the function.
276 Value *RootPtrPtr = new GetElementPtrInst(AI, Par, 4, "RootEntPtr", IP);
277 new StoreInst(Null, RootPtrPtr, IP);
279 // Each occurrance of the llvm.gcroot intrinsic now turns into an
280 // initialization of the slot with the address and a zeroing out of the
281 // address specified.
282 new StoreInst(Constant::getNullValue(PtrLocTy->getElementType()),
283 GCRoots[i]->getOperand(1), GCRoots[i]);
284 new StoreInst(GCRoots[i]->getOperand(1), RootPtrPtr, GCRoots[i]);
285 GCRoots[i]->getParent()->getInstList().erase(GCRoots[i]);
288 // Now that the record is all initialized, store the pointer into the global
290 Value *C = new BitCastInst(AI, PointerType::get(MainRootRecordType), "", IP);
291 new StoreInst(C, RootChain, IP);
293 // On exit from the function we have to remove the entry from the GC root
294 // chain. Doing this is straight-forward for return and unwind instructions:
295 // just insert the appropriate copy.
296 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
297 if (isa<UnwindInst>(BB->getTerminator()) ||
298 isa<ReturnInst>(BB->getTerminator())) {
299 // We could reuse the PrevPtr loaded on entry to the function, but this
300 // would make the value live for the whole function, which is probably a
301 // bad idea. Just reload the value out of our stack entry.
302 PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", BB->getTerminator());
303 new StoreInst(PrevPtr, RootChain, BB->getTerminator());
306 // If an exception is thrown from a callee we have to make sure to
307 // unconditionally take the record off the stack. For this reason, we turn
308 // all call instructions into invoke whose cleanup pops the entry off the
309 // stack. We only insert one cleanup block, which is shared by all invokes.
310 if (!NormalCalls.empty()) {
311 // Create the shared cleanup block.
312 BasicBlock *Cleanup = new BasicBlock("gc_cleanup", &F);
313 UnwindInst *UI = new UnwindInst(Cleanup);
314 PrevPtr = new LoadInst(PrevPtrPtr, "prevptr", UI);
315 new StoreInst(PrevPtr, RootChain, UI);
317 // Loop over all of the function calls, turning them into invokes.
318 while (!NormalCalls.empty()) {
319 CallInst *CI = NormalCalls.back();
320 BasicBlock *CBB = CI->getParent();
321 NormalCalls.pop_back();
323 // Split the basic block containing the function call.
324 BasicBlock *NewBB = CBB->splitBasicBlock(CI, CBB->getName()+".cont");
326 // Remove the unconditional branch inserted at the end of the CBB.
327 CBB->getInstList().pop_back();
328 NewBB->getInstList().remove(CI);
330 // Create a new invoke instruction.
331 std::vector<Value*> Args(CI->op_begin()+1, CI->op_end());
333 Value *II = new InvokeInst(CI->getCalledValue(), NewBB, Cleanup,
334 &Args[0], Args.size(), CI->getName(), CBB);
335 CI->replaceAllUsesWith(II);