1
//===-- GCStrategy.cpp - Garbage collection infrastructure -----------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements target- and collector-independent garbage collection
13
// MachineCodeAnalysis identifies the GC safe points in the machine code. Roots
14
// are identified in SelectionDAGISel.
16
//===----------------------------------------------------------------------===//
18
#include "llvm/CodeGen/GCStrategy.h"
19
#include "llvm/CodeGen/Passes.h"
20
#include "llvm/IntrinsicInst.h"
21
#include "llvm/Module.h"
22
#include "llvm/CodeGen/MachineFrameInfo.h"
23
#include "llvm/CodeGen/MachineFunctionPass.h"
24
#include "llvm/CodeGen/MachineInstrBuilder.h"
25
#include "llvm/CodeGen/MachineModuleInfo.h"
26
#include "llvm/Target/TargetFrameInfo.h"
27
#include "llvm/Target/TargetInstrInfo.h"
28
#include "llvm/Target/TargetMachine.h"
29
#include "llvm/Target/TargetRegisterInfo.h"
30
#include "llvm/Support/Debug.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Support/raw_ostream.h"
38
/// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or
39
/// llvm.gcwrite intrinsics, replacing them with simple loads and stores as
40
/// directed by the GCStrategy. It also performs automatic root initialization
41
/// and custom intrinsic lowering.
42
class LowerIntrinsics : public FunctionPass {
43
static bool NeedsDefaultLoweringPass(const GCStrategy &C);
44
static bool NeedsCustomLoweringPass(const GCStrategy &C);
45
static bool CouldBecomeSafePoint(Instruction *I);
46
bool PerformDefaultLowering(Function &F, GCStrategy &Coll);
47
static bool InsertRootInitializers(Function &F,
48
AllocaInst **Roots, unsigned Count);
54
const char *getPassName() const;
55
void getAnalysisUsage(AnalysisUsage &AU) const;
57
bool doInitialization(Module &M);
58
bool runOnFunction(Function &F);
62
/// MachineCodeAnalysis - This is a target-independent pass over the machine
63
/// function representation to identify safe points for the garbage collector
64
/// in the machine code. It inserts labels at safe points and populates a
65
/// GCMetadata record for each function.
66
class MachineCodeAnalysis : public MachineFunctionPass {
67
const TargetMachine *TM;
69
MachineModuleInfo *MMI;
70
const TargetInstrInfo *TII;
72
void FindSafePoints(MachineFunction &MF);
73
void VisitCallPoint(MachineBasicBlock::iterator MI);
74
MCSymbol *InsertLabel(MachineBasicBlock &MBB,
75
MachineBasicBlock::iterator MI,
78
void FindStackOffsets(MachineFunction &MF);
83
MachineCodeAnalysis();
84
const char *getPassName() const;
85
void getAnalysisUsage(AnalysisUsage &AU) const;
87
bool runOnMachineFunction(MachineFunction &MF);
92
// -----------------------------------------------------------------------------
94
GCStrategy::GCStrategy() :
96
CustomReadBarriers(false),
97
CustomWriteBarriers(false),
103
GCStrategy::~GCStrategy() {
104
for (iterator I = begin(), E = end(); I != E; ++I)
110
bool GCStrategy::initializeCustomLowering(Module &M) { return false; }
112
bool GCStrategy::performCustomLowering(Function &F) {
113
dbgs() << "gc " << getName() << " must override performCustomLowering.\n";
118
GCFunctionInfo *GCStrategy::insertFunctionInfo(const Function &F) {
119
GCFunctionInfo *FI = new GCFunctionInfo(F, *this);
120
Functions.push_back(FI);
124
// -----------------------------------------------------------------------------
126
FunctionPass *llvm::createGCLoweringPass() {
127
return new LowerIntrinsics();
130
char LowerIntrinsics::ID = 0;
132
LowerIntrinsics::LowerIntrinsics()
133
: FunctionPass(ID) {}
135
const char *LowerIntrinsics::getPassName() const {
136
return "Lower Garbage Collection Instructions";
139
void LowerIntrinsics::getAnalysisUsage(AnalysisUsage &AU) const {
140
FunctionPass::getAnalysisUsage(AU);
141
AU.addRequired<GCModuleInfo>();
144
/// doInitialization - If this module uses the GC intrinsics, find them now.
145
bool LowerIntrinsics::doInitialization(Module &M) {
146
// FIXME: This is rather antisocial in the context of a JIT since it performs
147
// work against the entire module. But this cannot be done at
148
// runFunction time (initializeCustomLowering likely needs to change
150
GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
151
assert(MI && "LowerIntrinsics didn't require GCModuleInfo!?");
152
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
153
if (!I->isDeclaration() && I->hasGC())
154
MI->getFunctionInfo(*I); // Instantiate the GC strategy.
156
bool MadeChange = false;
157
for (GCModuleInfo::iterator I = MI->begin(), E = MI->end(); I != E; ++I)
158
if (NeedsCustomLoweringPass(**I))
159
if ((*I)->initializeCustomLowering(M))
165
bool LowerIntrinsics::InsertRootInitializers(Function &F, AllocaInst **Roots,
167
// Scroll past alloca instructions.
168
BasicBlock::iterator IP = F.getEntryBlock().begin();
169
while (isa<AllocaInst>(IP)) ++IP;
171
// Search for initializers in the initial BB.
172
SmallPtrSet<AllocaInst*,16> InitedRoots;
173
for (; !CouldBecomeSafePoint(IP); ++IP)
174
if (StoreInst *SI = dyn_cast<StoreInst>(IP))
176
dyn_cast<AllocaInst>(SI->getOperand(1)->stripPointerCasts()))
177
InitedRoots.insert(AI);
179
// Add root initializers.
180
bool MadeChange = false;
182
for (AllocaInst **I = Roots, **E = Roots + Count; I != E; ++I)
183
if (!InitedRoots.count(*I)) {
184
StoreInst* SI = new StoreInst(ConstantPointerNull::get(cast<PointerType>(
185
cast<PointerType>((*I)->getType())->getElementType())),
194
bool LowerIntrinsics::NeedsDefaultLoweringPass(const GCStrategy &C) {
195
// Default lowering is necessary only if read or write barriers have a default
196
// action. The default for roots is no action.
197
return !C.customWriteBarrier()
198
|| !C.customReadBarrier()
199
|| C.initializeRoots();
202
bool LowerIntrinsics::NeedsCustomLoweringPass(const GCStrategy &C) {
203
// Custom lowering is only necessary if enabled for some action.
204
return C.customWriteBarrier()
205
|| C.customReadBarrier()
209
/// CouldBecomeSafePoint - Predicate to conservatively determine whether the
210
/// instruction could introduce a safe point.
211
bool LowerIntrinsics::CouldBecomeSafePoint(Instruction *I) {
212
// The natural definition of instructions which could introduce safe points
215
// - call, invoke (AfterCall, BeforeCall)
217
// - invoke, ret, unwind (Exit)
219
// However, instructions as seemingly inoccuous as arithmetic can become
220
// libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
221
// it is necessary to take a conservative approach.
223
if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) ||
224
isa<StoreInst>(I) || isa<LoadInst>(I))
227
// llvm.gcroot is safe because it doesn't do anything at runtime.
228
if (CallInst *CI = dyn_cast<CallInst>(I))
229
if (Function *F = CI->getCalledFunction())
230
if (unsigned IID = F->getIntrinsicID())
231
if (IID == Intrinsic::gcroot)
237
/// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
238
/// Leave gcroot intrinsics; the code generator needs to see those.
239
bool LowerIntrinsics::runOnFunction(Function &F) {
240
// Quick exit for functions that do not use GC.
244
GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
245
GCStrategy &S = FI.getStrategy();
247
bool MadeChange = false;
249
if (NeedsDefaultLoweringPass(S))
250
MadeChange |= PerformDefaultLowering(F, S);
252
if (NeedsCustomLoweringPass(S))
253
MadeChange |= S.performCustomLowering(F);
258
bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) {
259
bool LowerWr = !S.customWriteBarrier();
260
bool LowerRd = !S.customReadBarrier();
261
bool InitRoots = S.initializeRoots();
263
SmallVector<AllocaInst*, 32> Roots;
265
bool MadeChange = false;
266
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
267
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
268
if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) {
269
Function *F = CI->getCalledFunction();
270
switch (F->getIntrinsicID()) {
271
case Intrinsic::gcwrite:
273
// Replace a write barrier with a simple store.
274
Value *St = new StoreInst(CI->getArgOperand(0),
275
CI->getArgOperand(2), CI);
276
CI->replaceAllUsesWith(St);
277
CI->eraseFromParent();
280
case Intrinsic::gcread:
282
// Replace a read barrier with a simple load.
283
Value *Ld = new LoadInst(CI->getArgOperand(1), "", CI);
285
CI->replaceAllUsesWith(Ld);
286
CI->eraseFromParent();
289
case Intrinsic::gcroot:
291
// Initialize the GC root, but do not delete the intrinsic. The
292
// backend needs the intrinsic to flag the stack slot.
293
Roots.push_back(cast<AllocaInst>(
294
CI->getArgOperand(0)->stripPointerCasts()));
307
MadeChange |= InsertRootInitializers(F, Roots.begin(), Roots.size());
312
// -----------------------------------------------------------------------------
314
FunctionPass *llvm::createGCMachineCodeAnalysisPass() {
315
return new MachineCodeAnalysis();
318
char MachineCodeAnalysis::ID = 0;
320
MachineCodeAnalysis::MachineCodeAnalysis()
321
: MachineFunctionPass(ID) {}
323
const char *MachineCodeAnalysis::getPassName() const {
324
return "Analyze Machine Code For Garbage Collection";
327
void MachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
328
MachineFunctionPass::getAnalysisUsage(AU);
329
AU.setPreservesAll();
330
AU.addRequired<MachineModuleInfo>();
331
AU.addRequired<GCModuleInfo>();
334
MCSymbol *MachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
335
MachineBasicBlock::iterator MI,
337
MCSymbol *Label = MBB.getParent()->getContext().CreateTempSymbol();
338
BuildMI(MBB, MI, DL, TII->get(TargetOpcode::GC_LABEL)).addSym(Label);
342
void MachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
343
// Find the return address (next instruction), too, so as to bracket the call
345
MachineBasicBlock::iterator RAI = CI;
348
if (FI->getStrategy().needsSafePoint(GC::PreCall))
349
FI->addSafePoint(GC::PreCall, InsertLabel(*CI->getParent(), CI,
352
if (FI->getStrategy().needsSafePoint(GC::PostCall))
353
FI->addSafePoint(GC::PostCall, InsertLabel(*CI->getParent(), RAI,
357
void MachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
358
for (MachineFunction::iterator BBI = MF.begin(),
359
BBE = MF.end(); BBI != BBE; ++BBI)
360
for (MachineBasicBlock::iterator MI = BBI->begin(),
361
ME = BBI->end(); MI != ME; ++MI)
362
if (MI->getDesc().isCall())
366
void MachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
367
const TargetRegisterInfo *TRI = TM->getRegisterInfo();
368
assert(TRI && "TargetRegisterInfo not available!");
370
for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
371
RE = FI->roots_end(); RI != RE; ++RI)
372
RI->StackOffset = TRI->getFrameIndexOffset(MF, RI->Num);
375
bool MachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
376
// Quick exit for functions that do not use GC.
377
if (!MF.getFunction()->hasGC())
380
FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction());
381
if (!FI->getStrategy().needsSafePoints())
384
TM = &MF.getTarget();
385
MMI = &getAnalysis<MachineModuleInfo>();
386
TII = TM->getInstrInfo();
388
// Find the size of the stack frame.
389
FI->setFrameSize(MF.getFrameInfo()->getStackSize());
391
// Find all safe points.
394
// Find the stack offsets for all roots.
395
FindStackOffsets(MF);