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