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

source code of llvm/lib/CodeGen/GCRootLowering.cpp