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