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