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 28using namespace llvm; 29 30namespace { 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. 36class LowerIntrinsics : public FunctionPass { 37 bool DoLowering(Function &F, GCStrategy &S); 38 39public: 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. 54class 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 65public: 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 77INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false, 78 false) 79INITIALIZE_PASS_DEPENDENCY(GCModuleInfo) 80INITIALIZE_PASS_END(LowerIntrinsics, "gc-lowering", "GC Lowering", false, false) 81 82FunctionPass *llvm::createGCLoweringPass() { return new LowerIntrinsics(); } 83 84char LowerIntrinsics::ID = 0; 85char &llvm::GCLoweringID = LowerIntrinsics::ID; 86 87LowerIntrinsics::LowerIntrinsics() : FunctionPass(ID) { 88 initializeLowerIntrinsicsPass(*PassRegistry::getPassRegistry()); 89} 90 91StringRef LowerIntrinsics::getPassName() const { 92 return "Lower Garbage Collection Instructions"; 93} 94 95void 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. 102bool 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. 114static 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 140static 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. 170bool 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. 188bool 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 237char GCMachineCodeAnalysis::ID = 0; 238char &llvm::GCMachineCodeAnalysisID = GCMachineCodeAnalysis::ID; 239 240INITIALIZE_PASS(GCMachineCodeAnalysis, "gc-analysis", 241 "Analyze Machine Code For Garbage Collection", false, false) 242 243GCMachineCodeAnalysis::GCMachineCodeAnalysis() : MachineFunctionPass(ID) {} 244 245void GCMachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 246 MachineFunctionPass::getAnalysisUsage(AU); 247 AU.setPreservesAll(); 248 AU.addRequired<GCModuleInfo>(); 249} 250 251MCSymbol *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 259void 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 269void 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 283void 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 304bool 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