GCStrategy.cpp revision b9dcef2a00f1ac35442393c951c21272527c8625
1//===-- GCStrategy.cpp - Garbage collection infrastructure -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements target- and collector-independent garbage collection 11// infrastructure. 12// 13// MachineCodeAnalysis identifies the GC safe points in the machine code. Roots 14// are identified in SelectionDAGISel. 15// 16//===----------------------------------------------------------------------===// 17 18#include "llvm/CodeGen/GCStrategy.h" 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/IntrinsicInst.h" 21#include "llvm/Module.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunctionPass.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineModuleInfo.h" 26#include "llvm/Target/TargetFrameInfo.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30#include "llvm/Support/Compiler.h" 31 32using namespace llvm; 33 34namespace { 35 36 /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or 37 /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as 38 /// directed by the GCStrategy. It also performs automatic root initialization 39 /// and custom intrinsic lowering. 40 class VISIBILITY_HIDDEN LowerIntrinsics : public FunctionPass { 41 static bool NeedsDefaultLoweringPass(const GCStrategy &C); 42 static bool NeedsCustomLoweringPass(const GCStrategy &C); 43 static bool CouldBecomeSafePoint(Instruction *I); 44 bool PerformDefaultLowering(Function &F, GCStrategy &Coll); 45 static bool InsertRootInitializers(Function &F, 46 AllocaInst **Roots, unsigned Count); 47 48 public: 49 static char ID; 50 51 LowerIntrinsics(); 52 const char *getPassName() const; 53 void getAnalysisUsage(AnalysisUsage &AU) const; 54 55 bool doInitialization(Module &M); 56 bool runOnFunction(Function &F); 57 }; 58 59 60 /// MachineCodeAnalysis - This is a target-independent pass over the machine 61 /// function representation to identify safe points for the garbage collector 62 /// in the machine code. It inserts labels at safe points and populates a 63 /// GCMetadata record for each function. 64 class VISIBILITY_HIDDEN MachineCodeAnalysis : public MachineFunctionPass { 65 const TargetMachine *TM; 66 GCFunctionInfo *FI; 67 MachineModuleInfo *MMI; 68 const TargetInstrInfo *TII; 69 70 void FindSafePoints(MachineFunction &MF); 71 void VisitCallPoint(MachineBasicBlock::iterator MI); 72 unsigned InsertLabel(MachineBasicBlock &MBB, 73 MachineBasicBlock::iterator MI) const; 74 75 void FindStackOffsets(MachineFunction &MF); 76 77 public: 78 static char ID; 79 80 MachineCodeAnalysis(); 81 const char *getPassName() const; 82 void getAnalysisUsage(AnalysisUsage &AU) const; 83 84 bool runOnMachineFunction(MachineFunction &MF); 85 }; 86 87} 88 89// ----------------------------------------------------------------------------- 90 91GCStrategy::GCStrategy() : 92 NeededSafePoints(0), 93 CustomReadBarriers(false), 94 CustomWriteBarriers(false), 95 CustomRoots(false), 96 InitRoots(true), 97 UsesMetadata(false) 98{} 99 100GCStrategy::~GCStrategy() { 101 for (iterator I = begin(), E = end(); I != E; ++I) 102 delete *I; 103 104 Functions.clear(); 105} 106 107bool GCStrategy::initializeCustomLowering(Module &M) { return false; } 108 109bool GCStrategy::performCustomLowering(Function &F) { 110 cerr << "gc " << getName() << " must override performCustomLowering.\n"; 111 abort(); 112 return 0; 113} 114 115GCFunctionInfo *GCStrategy::insertFunctionInfo(const Function &F) { 116 GCFunctionInfo *FI = new GCFunctionInfo(F, *this); 117 Functions.push_back(FI); 118 return FI; 119} 120 121// ----------------------------------------------------------------------------- 122 123FunctionPass *llvm::createGCLoweringPass() { 124 return new LowerIntrinsics(); 125} 126 127char LowerIntrinsics::ID = 0; 128 129LowerIntrinsics::LowerIntrinsics() 130 : FunctionPass(&ID) {} 131 132const char *LowerIntrinsics::getPassName() const { 133 return "Lower Garbage Collection Instructions"; 134} 135 136void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const { 137 FunctionPass::getAnalysisUsage(AU); 138 AU.addRequired<GCModuleInfo>(); 139} 140 141/// doInitialization - If this module uses the GC intrinsics, find them now. 142bool LowerIntrinsics::doInitialization(Module &M) { 143 // FIXME: This is rather antisocial in the context of a JIT since it performs 144 // work against the entire module. But this cannot be done at 145 // runFunction time (initializeCustomLowering likely needs to change 146 // the module). 147 GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>(); 148 assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?"); 149 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 150 if (!I->isDeclaration() && I->hasGC()) 151 MI->getFunctionInfo(*I); // Instantiate the GC strategy. 152 153 bool MadeChange = false; 154 for (GCModuleInfo::iterator I = MI->begin(), E = MI->end(); I != E; ++I) 155 if (NeedsCustomLoweringPass(**I)) 156 if ((*I)->initializeCustomLowering(M)) 157 MadeChange = true; 158 159 return MadeChange; 160} 161 162bool LowerIntrinsics::InsertRootInitializers(Function &F, AllocaInst **Roots, 163 unsigned Count) { 164 // Scroll past alloca instructions. 165 BasicBlock::iterator IP = F.getEntryBlock().begin(); 166 while (isa<AllocaInst>(IP)) ++IP; 167 168 // Search for initializers in the initial BB. 169 SmallPtrSet<AllocaInst*,16> InitedRoots; 170 for (; !CouldBecomeSafePoint(IP); ++IP) 171 if (StoreInst *SI = dyn_cast<StoreInst>(IP)) 172 if (AllocaInst *AI = 173 dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts())) 174 InitedRoots.insert(AI); 175 176 // Add root initializers. 177 bool MadeChange = false; 178 179 for (AllocaInst **I = Roots, **E = Roots + Count; I != E; ++I) 180 if (!InitedRoots.count(*I)) { 181 new StoreInst(ConstantPointerNull::get(cast<PointerType>( 182 cast<PointerType>((*I)->getType())->getElementType())), 183 *I, IP); 184 MadeChange = true; 185 } 186 187 return MadeChange; 188} 189 190bool LowerIntrinsics::NeedsDefaultLoweringPass(const GCStrategy &C) { 191 // Default lowering is necessary only if read or write barriers have a default 192 // action. The default for roots is no action. 193 return !C.customWriteBarrier() 194 || !C.customReadBarrier() 195 || C.initializeRoots(); 196} 197 198bool LowerIntrinsics::NeedsCustomLoweringPass(const GCStrategy &C) { 199 // Custom lowering is only necessary if enabled for some action. 200 return C.customWriteBarrier() 201 || C.customReadBarrier() 202 || C.customRoots(); 203} 204 205/// CouldBecomeSafePoint - Predicate to conservatively determine whether the 206/// instruction could introduce a safe point. 207bool LowerIntrinsics::CouldBecomeSafePoint(Instruction *I) { 208 // The natural definition of instructions which could introduce safe points 209 // are: 210 // 211 // - call, invoke (AfterCall, BeforeCall) 212 // - phis (Loops) 213 // - invoke, ret, unwind (Exit) 214 // 215 // However, instructions as seemingly inoccuous as arithmetic can become 216 // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead 217 // it is necessary to take a conservative approach. 218 219 if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) || 220 isa<StoreInst>(I) || isa<LoadInst>(I)) 221 return false; 222 223 // llvm.gcroot is safe because it doesn't do anything at runtime. 224 if (CallInst *CI = dyn_cast<CallInst>(I)) 225 if (Function *F = CI->getCalledFunction()) 226 if (unsigned IID = F->getIntrinsicID()) 227 if (IID == Intrinsic::gcroot) 228 return false; 229 230 return true; 231} 232 233/// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores. 234/// Leave gcroot intrinsics; the code generator needs to see those. 235bool LowerIntrinsics::runOnFunction(Function &F) { 236 // Quick exit for functions that do not use GC. 237 if (!F.hasGC()) 238 return false; 239 240 GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F); 241 GCStrategy &S = FI.getStrategy(); 242 243 bool MadeChange = false; 244 245 if (NeedsDefaultLoweringPass(S)) 246 MadeChange |= PerformDefaultLowering(F, S); 247 248 if (NeedsCustomLoweringPass(S)) 249 MadeChange |= S.performCustomLowering(F); 250 251 return MadeChange; 252} 253 254bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) { 255 bool LowerWr = !S.customWriteBarrier(); 256 bool LowerRd = !S.customReadBarrier(); 257 bool InitRoots = S.initializeRoots(); 258 259 SmallVector<AllocaInst*,32> Roots; 260 261 bool MadeChange = false; 262 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 263 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) { 264 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) { 265 Function *F = CI->getCalledFunction(); 266 switch (F->getIntrinsicID()) { 267 case Intrinsic::gcwrite: 268 if (LowerWr) { 269 // Replace a write barrier with a simple store. 270 Value *St = new StoreInst(CI->getOperand(1), CI->getOperand(3), CI); 271 CI->replaceAllUsesWith(St); 272 CI->eraseFromParent(); 273 } 274 break; 275 case Intrinsic::gcread: 276 if (LowerRd) { 277 // Replace a read barrier with a simple load. 278 Value *Ld = new LoadInst(CI->getOperand(2), "", CI); 279 Ld->takeName(CI); 280 CI->replaceAllUsesWith(Ld); 281 CI->eraseFromParent(); 282 } 283 break; 284 case Intrinsic::gcroot: 285 if (InitRoots) { 286 // Initialize the GC root, but do not delete the intrinsic. The 287 // backend needs the intrinsic to flag the stack slot. 288 Roots.push_back(cast<AllocaInst>( 289 CI->getOperand(1)->stripPointerCasts())); 290 } 291 break; 292 default: 293 continue; 294 } 295 296 MadeChange = true; 297 } 298 } 299 } 300 301 if (Roots.size()) 302 MadeChange |= InsertRootInitializers(F, Roots.begin(), Roots.size()); 303 304 return MadeChange; 305} 306 307// ----------------------------------------------------------------------------- 308 309FunctionPass *llvm::createGCMachineCodeAnalysisPass() { 310 return new MachineCodeAnalysis(); 311} 312 313char MachineCodeAnalysis::ID = 0; 314 315MachineCodeAnalysis::MachineCodeAnalysis() 316 : MachineFunctionPass(intptr_t(&ID)) {} 317 318const char *MachineCodeAnalysis::getPassName() const { 319 return "Analyze Machine Code For Garbage Collection"; 320} 321 322void MachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 323 MachineFunctionPass::getAnalysisUsage(AU); 324 AU.setPreservesAll(); 325 AU.addRequired<MachineModuleInfo>(); 326 AU.addRequired<GCModuleInfo>(); 327} 328 329unsigned MachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB, 330 MachineBasicBlock::iterator MI) const { 331 unsigned Label = MMI->NextLabelID(); 332 // N.B. we assume that MI is *not* equal to the "end()" iterator. 333 BuildMI(MBB, MI, MI->getDebugLoc(), 334 TII->get(TargetInstrInfo::GC_LABEL)).addImm(Label); 335 return Label; 336} 337 338void MachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) { 339 // Find the return address (next instruction), too, so as to bracket the call 340 // instruction. 341 MachineBasicBlock::iterator RAI = CI; 342 ++RAI; 343 344 if (FI->getStrategy().needsSafePoint(GC::PreCall)) 345 FI->addSafePoint(GC::PreCall, InsertLabel(*CI->getParent(), CI)); 346 347 if (FI->getStrategy().needsSafePoint(GC::PostCall)) 348 FI->addSafePoint(GC::PostCall, InsertLabel(*CI->getParent(), RAI)); 349} 350 351void MachineCodeAnalysis::FindSafePoints(MachineFunction &MF) { 352 for (MachineFunction::iterator BBI = MF.begin(), 353 BBE = MF.end(); BBI != BBE; ++BBI) 354 for (MachineBasicBlock::iterator MI = BBI->begin(), 355 ME = BBI->end(); MI != ME; ++MI) 356 if (MI->getDesc().isCall()) 357 VisitCallPoint(MI); 358} 359 360void MachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) { 361 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 362 assert(TRI && "TargetRegisterInfo not available!"); 363 364 for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(), 365 RE = FI->roots_end(); RI != RE; ++RI) 366 RI->StackOffset = TRI->getFrameIndexOffset(MF, RI->Num); 367} 368 369bool MachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) { 370 // Quick exit for functions that do not use GC. 371 if (!MF.getFunction()->hasGC()) 372 return false; 373 374 FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction()); 375 if (!FI->getStrategy().needsSafePoints()) 376 return false; 377 378 TM = &MF.getTarget(); 379 MMI = &getAnalysis<MachineModuleInfo>(); 380 TII = TM->getInstrInfo(); 381 382 // Find the size of the stack frame. 383 FI->setFrameSize(MF.getFrameInfo()->getStackSize()); 384 385 // Find all safe points. 386 FindSafePoints(MF); 387 388 // Find the stack offsets for all roots. 389 FindStackOffsets(MF); 390 391 return false; 392} 393