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