1 //===-- GCRootLowering.cpp - Garbage collection infrastructure ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the lowering for the gc.root mechanism. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/GCMetadata.h" 14 #include "llvm/CodeGen/GCStrategy.h" 15 #include "llvm/CodeGen/MachineFrameInfo.h" 16 #include "llvm/CodeGen/MachineFunctionPass.h" 17 #include "llvm/CodeGen/MachineInstrBuilder.h" 18 #include "llvm/CodeGen/MachineModuleInfo.h" 19 #include "llvm/CodeGen/Passes.h" 20 #include "llvm/CodeGen/TargetFrameLowering.h" 21 #include "llvm/CodeGen/TargetInstrInfo.h" 22 #include "llvm/CodeGen/TargetRegisterInfo.h" 23 #include "llvm/CodeGen/TargetSubtargetInfo.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/IntrinsicInst.h" 26 #include "llvm/IR/Module.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/ErrorHandling.h" 30 #include "llvm/Support/raw_ostream.h" 31 32 using namespace llvm; 33 34 namespace { 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 LowerIntrinsics : public FunctionPass { 41 bool DoLowering(Function &F, GCStrategy &S); 42 43 public: 44 static char ID; 45 46 LowerIntrinsics(); 47 StringRef getPassName() const override; 48 void getAnalysisUsage(AnalysisUsage &AU) const override; 49 50 bool doInitialization(Module &M) override; 51 bool runOnFunction(Function &F) override; 52 }; 53 54 /// GCMachineCodeAnalysis - This is a target-independent pass over the machine 55 /// function representation to identify safe points for the garbage collector 56 /// in the machine code. It inserts labels at safe points and populates a 57 /// GCMetadata record for each function. 58 class GCMachineCodeAnalysis : public MachineFunctionPass { 59 GCFunctionInfo *FI; 60 MachineModuleInfo *MMI; 61 const TargetInstrInfo *TII; 62 63 void FindSafePoints(MachineFunction &MF); 64 void VisitCallPoint(MachineBasicBlock::iterator CI); 65 MCSymbol *InsertLabel(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 66 const DebugLoc &DL) const; 67 68 void FindStackOffsets(MachineFunction &MF); 69 70 public: 71 static char ID; 72 73 GCMachineCodeAnalysis(); 74 void getAnalysisUsage(AnalysisUsage &AU) const override; 75 76 bool runOnMachineFunction(MachineFunction &MF) override; 77 }; 78 } 79 80 // ----------------------------------------------------------------------------- 81 82 INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false, 83 false) 84 INITIALIZE_PASS_DEPENDENCY(GCModuleInfo) 85 INITIALIZE_PASS_END(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false) 86 87 FunctionPass *llvm::createGCLoweringPass() { return new LowerIntrinsics(); } 88 89 char LowerIntrinsics::ID = 0; 90 91 LowerIntrinsics::LowerIntrinsics() : FunctionPass(ID) { 92 initializeLowerIntrinsicsPass(*PassRegistry::getPassRegistry()); 93 } 94 95 StringRef LowerIntrinsics::getPassName() const { 96 return "Lower Garbage Collection Instructions"; 97 } 98 99 void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const { 100 FunctionPass::getAnalysisUsage(AU); 101 AU.addRequired<GCModuleInfo>(); 102 AU.addPreserved<DominatorTreeWrapperPass>(); 103 } 104 105 /// doInitialization - If this module uses the GC intrinsics, find them now. 106 bool LowerIntrinsics::doInitialization(Module &M) { 107 GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>(); 108 assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?"); 109 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 110 if (!I->isDeclaration() && I->hasGC()) 111 MI->getFunctionInfo(*I); // Instantiate the GC strategy. 112 113 return false; 114 } 115 116 /// CouldBecomeSafePoint - Predicate to conservatively determine whether the 117 /// instruction could introduce a safe point. 118 static bool CouldBecomeSafePoint(Instruction *I) { 119 // The natural definition of instructions which could introduce safe points 120 // are: 121 // 122 // - call, invoke (AfterCall, BeforeCall) 123 // - phis (Loops) 124 // - invoke, ret, unwind (Exit) 125 // 126 // However, instructions as seemingly inoccuous as arithmetic can become 127 // libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead 128 // it is necessary to take a conservative approach. 129 130 if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) || isa<StoreInst>(I) || 131 isa<LoadInst>(I)) 132 return false; 133 134 // llvm.gcroot is safe because it doesn't do anything at runtime. 135 if (CallInst *CI = dyn_cast<CallInst>(I)) 136 if (Function *F = CI->getCalledFunction()) 137 if (Intrinsic::ID IID = F->getIntrinsicID()) 138 if (IID == Intrinsic::gcroot) 139 return false; 140 141 return true; 142 } 143 144 static bool InsertRootInitializers(Function &F, ArrayRef<AllocaInst *> Roots) { 145 // Scroll past alloca instructions. 146 BasicBlock::iterator IP = F.getEntryBlock().begin(); 147 while (isa<AllocaInst>(IP)) 148 ++IP; 149 150 // Search for initializers in the initial BB. 151 SmallPtrSet<AllocaInst *, 16> InitedRoots; 152 for (; !CouldBecomeSafePoint(&*IP); ++IP) 153 if (StoreInst *SI = dyn_cast<StoreInst>(IP)) 154 if (AllocaInst *AI = 155 dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts())) 156 InitedRoots.insert(AI); 157 158 // Add root initializers. 159 bool MadeChange = false; 160 161 for (AllocaInst *Root : Roots) 162 if (!InitedRoots.count(Root)) { 163 StoreInst *SI = new StoreInst( 164 ConstantPointerNull::get(cast<PointerType>(Root->getAllocatedType())), 165 Root); 166 SI->insertAfter(Root); 167 MadeChange = true; 168 } 169 170 return MadeChange; 171 } 172 173 /// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores. 174 /// Leave gcroot intrinsics; the code generator needs to see those. 175 bool LowerIntrinsics::runOnFunction(Function &F) { 176 // Quick exit for functions that do not use GC. 177 if (!F.hasGC()) 178 return false; 179 180 GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F); 181 GCStrategy &S = FI.getStrategy(); 182 183 return DoLowering(F, S); 184 } 185 186 /// Lower barriers out of existance (if the associated GCStrategy hasn't 187 /// already done so...), and insert initializing stores to roots as a defensive 188 /// measure. Given we're going to report all roots live at all safepoints, we 189 /// need to be able to ensure each root has been initialized by the point the 190 /// first safepoint is reached. This really should have been done by the 191 /// frontend, but the old API made this non-obvious, so we do a potentially 192 /// redundant store just in case. 193 bool LowerIntrinsics::DoLowering(Function &F, GCStrategy &S) { 194 SmallVector<AllocaInst *, 32> Roots; 195 196 bool MadeChange = false; 197 for (BasicBlock &BB : F) 198 for (BasicBlock::iterator II = BB.begin(), E = BB.end(); II != E;) { 199 IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++); 200 if (!CI) 201 continue; 202 203 Function *F = CI->getCalledFunction(); 204 switch (F->getIntrinsicID()) { 205 default: break; 206 case Intrinsic::gcwrite: { 207 // Replace a write barrier with a simple store. 208 Value *St = new StoreInst(CI->getArgOperand(0), 209 CI->getArgOperand(2), CI); 210 CI->replaceAllUsesWith(St); 211 CI->eraseFromParent(); 212 MadeChange = true; 213 break; 214 } 215 case Intrinsic::gcread: { 216 // Replace a read barrier with a simple load. 217 Value *Ld = new LoadInst(CI->getType(), CI->getArgOperand(1), "", CI); 218 Ld->takeName(CI); 219 CI->replaceAllUsesWith(Ld); 220 CI->eraseFromParent(); 221 MadeChange = true; 222 break; 223 } 224 case Intrinsic::gcroot: { 225 // Initialize the GC root, but do not delete the intrinsic. The 226 // backend needs the intrinsic to flag the stack slot. 227 Roots.push_back( 228 cast<AllocaInst>(CI->getArgOperand(0)->stripPointerCasts())); 229 break; 230 } 231 } 232 } 233 234 if (Roots.size()) 235 MadeChange |= InsertRootInitializers(F, Roots); 236 237 return MadeChange; 238 } 239 240 // ----------------------------------------------------------------------------- 241 242 char GCMachineCodeAnalysis::ID = 0; 243 char &llvm::GCMachineCodeAnalysisID = GCMachineCodeAnalysis::ID; 244 245 INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis", 246 "Analyze Machine Code For Garbage Collection", false, false) 247 248 GCMachineCodeAnalysis::GCMachineCodeAnalysis() : MachineFunctionPass(ID) {} 249 250 void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 251 MachineFunctionPass::getAnalysisUsage(AU); 252 AU.setPreservesAll(); 253 AU.addRequired<MachineModuleInfoWrapperPass>(); 254 AU.addRequired<GCModuleInfo>(); 255 } 256 257 MCSymbol *GCMachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB, 258 MachineBasicBlock::iterator MI, 259 const DebugLoc &DL) const { 260 MCSymbol *Label = MBB.getParent()->getContext().createTempSymbol(); 261 BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label); 262 return Label; 263 } 264 265 void GCMachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) { 266 // Find the return address (next instruction), since that's what will be on 267 // the stack when the call is suspended and we need to inspect the stack. 268 MachineBasicBlock::iterator RAI = CI; 269 ++RAI; 270 271 MCSymbol *Label = InsertLabel(*CI->getParent(), RAI, CI->getDebugLoc()); 272 FI->addSafePoint(Label, CI->getDebugLoc()); 273 } 274 275 void GCMachineCodeAnalysis::FindSafePoints(MachineFunction &MF) { 276 for (MachineBasicBlock &MBB : MF) 277 for (MachineBasicBlock::iterator MI = MBB.begin(), ME = MBB.end(); 278 MI != ME; ++MI) 279 if (MI->isCall()) { 280 // Do not treat tail or sibling call sites as safe points. This is 281 // legal since any arguments passed to the callee which live in the 282 // remnants of the callers frame will be owned and updated by the 283 // callee if required. 284 if (MI->isTerminator()) 285 continue; 286 VisitCallPoint(MI); 287 } 288 } 289 290 void GCMachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) { 291 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); 292 assert(TFI && "TargetRegisterInfo not available!"); 293 294 for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(); 295 RI != FI->roots_end();) { 296 // If the root references a dead object, no need to keep it. 297 if (MF.getFrameInfo().isDeadObjectIndex(RI->Num)) { 298 RI = FI->removeStackRoot(RI); 299 } else { 300 unsigned FrameReg; // FIXME: surely GCRoot ought to store the 301 // register that the offset is from? 302 RI->StackOffset = TFI->getFrameIndexReference(MF, RI->Num, FrameReg); 303 ++RI; 304 } 305 } 306 } 307 308 bool GCMachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) { 309 // Quick exit for functions that do not use GC. 310 if (!MF.getFunction().hasGC()) 311 return false; 312 313 FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(MF.getFunction()); 314 MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); 315 TII = MF.getSubtarget().getInstrInfo(); 316 317 // Find the size of the stack frame. There may be no correct static frame 318 // size, we use UINT64_MAX to represent this. 319 const MachineFrameInfo &MFI = MF.getFrameInfo(); 320 const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo(); 321 const bool DynamicFrameSize = MFI.hasVarSizedObjects() || 322 RegInfo->needsStackRealignment(MF); 323 FI->setFrameSize(DynamicFrameSize ? UINT64_MAX : MFI.getStackSize()); 324 325 // Find all safe points. 326 if (FI->getStrategy().needsSafePoints()) 327 FindSafePoints(MF); 328 329 // Find the concrete stack offsets for all roots (stack slots) 330 FindStackOffsets(MF); 331 332 return false; 333 } 334