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