lib/Transforms/Scalar/LowerGC.cpp

   1 //===-- LowerGC.cpp - Provide GC support for targets that don't -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  15 //
  16 // This pass implements the code transformation described in this paper:
  17 //   "Accurate Garbage Collection in an Uncooperative Environment"
  18 //   Fergus Henderson, ISMM, 2002
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  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"
  31 using namespace llvm;
  32
  33 namespace {
  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;
  38
  39     /// GCRead/GCWrite - These are the functions provided by the garbage
  40     /// collector for read/write barriers.
  41     Constant *GCRead, *GCWrite;
  42
  43     /// RootChain - This is the global linked-list that contains the chain of GC
  44     /// roots.
  45     GlobalVariable *RootChain;
  46
  47     /// MainRootRecordType - This is the type for a function root entry if it
  48     /// had zero roots.
  49     const Type *MainRootRecordType;
  50   public:
  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);
  57
  58   private:
  59     const StructType *getRootRecordType(unsigned NumRoots);
  60   };
  61
  62   char LowerGC::ID = 0;
  63   RegisterPass<LowerGC>
  64   X("lowergc", "Lower GC intrinsics, for GCless code generators");
  65 }
  66
  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() {
  70   return new LowerGC();
  71 }
  72
  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);
  81
  82   // Build the array of pairs.
  83   ArrayType *PairArrTy = ArrayType::get(PairTy, NumRoots);
  84
  85   // Now build the recursive list type.
  86   PATypeHolder RootListH =
  87     MainRootRecordType ? (Type*)MainRootRecordType : (Type*)OpaqueType::get();
  88   ST.clear();
  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)
  94     return RootList;
  95
  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());
 100 }
 101
 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;
 109
 110   PointerType *VoidPtr = PointerType::get(Type::Int8Ty);
 111   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
 112
 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,
 117                                    (Type *)0);
 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);
 121
 122   // If the program has GC roots, get or create the global root list.
 123   if (GCRootInt) {
 124     const StructType *RootListTy = getRootRecordType(0);
 125     const Type *PRLTy = PointerType::get(RootListTy);
 126     M.addTypeName("llvm_gc_root_ty", RootListTy);
 127
 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
 132       // linkage!
 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);
 140     }
 141   }
 142   return true;
 143 }
 144
 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));
 152     else {
 153       CastInst *CI = new BitCastInst(I->getOperand(OpNum), Ty, "", I);
 154       I->setOperand(OpNum, CI);
 155     }
 156   }
 157 }
 158
 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;
 165
 166   PointerType *VoidPtr    = PointerType::get(Type::Int8Ty);
 167   PointerType *VoidPtrPtr = PointerType::get(VoidPtr);
 168
 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;
 174
 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.
 182
 183         if (Function *F = CI->getCalledFunction())
 184           if (F == GCRootInt)
 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);
 194             } else {
 195               Coerce(CI, 1, VoidPtr);
 196               Coerce(CI, 2, VoidPtrPtr);
 197               if (CI->getType() == VoidPtr) {
 198                 CI->setOperand(0, GCRead);
 199               } else {
 200                 // Create a whole new call to replace the old one.
 201
 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 &*iterator, 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                 Value* Args[] = {
 209                   CI->getOperand(1),
 210                   CI->getOperand(2)
 211                 };
 212                 CallInst *NC = new CallInst(GCRead, Args, Args + 2,
 213                                             CI->getName(), CI);
 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);
 219                 CI = NC;
 220               }
 221             }
 222
 223             MadeChange = true;
 224           }
 225       }
 226
 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;
 230
 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.
 233
 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());
 237
 238   // Insert the memset call after all of the allocas in the function.
 239   BasicBlock::iterator IP = AI;
 240   while (isa<AllocaInst>(IP)) ++IP;
 241
 242   Constant *Zero = ConstantInt::get(Type::Int32Ty, 0);
 243   Constant *One  = ConstantInt::get(Type::Int32Ty, 1);
 244
 245   // Get a pointer to the prev pointer.
 246   Value *PrevPtrPtr = new GetElementPtrInst(AI, Zero, Zero, "prevptrptr", IP);
 247
 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);
 252
 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);
 256
 257   Value* Par[4];
 258   Par[0] = Zero;
 259   Par[1] = ConstantInt::get(Type::Int32Ty, 2);
 260
 261   const PointerType *PtrLocTy =
 262     cast<PointerType>(GCRootInt->getFunctionType()->getParamType(0));
 263   Constant *Null = ConstantPointerNull::get(PtrLocTy);
 264
 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);
 269     Par[3] = One;
 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);
 273
 274     // Initialize the root pointer to null on entry to the function.
 275     Par[3] = Zero;
 276     Value *RootPtrPtr = new GetElementPtrInst(AI, Par, 4, "RootEntPtr", IP);
 277     new StoreInst(Null, RootPtrPtr, IP);
 278
 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]);
 286   }
 287
 288   // Now that the record is all initialized, store the pointer into the global
 289   // pointer.
 290   Value *C = new BitCastInst(AI, PointerType::get(MainRootRecordType), "", IP);
 291   new StoreInst(C, RootChain, IP);
 292
 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());
 304     }
 305
 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);
 316
 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();
 322
 323       // Split the basic block containing the function call.
 324       BasicBlock *NewBB = CBB->splitBasicBlock(CI, CBB->getName()+".cont");
 325
 326       // Remove the unconditional branch inserted at the end of the CBB.
 327       CBB->getInstList().pop_back();
 328       NewBB->getInstList().remove(CI);
 329
 330       // Create a new invoke instruction.
 331       std::vector<Value*> Args(CI->op_begin()+1, CI->op_end());
 332
 333       Value *II = new InvokeInst(CI->getCalledValue(), NewBB, Cleanup,
 334                                  &Args[0], Args.size(), CI->getName(), CBB);
 335       CI->replaceAllUsesWith(II);
 336       delete CI;
 337     }
 338   }
 339
 340   return true;
 341 }