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
unsigned 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
new StoreInst(ConstantPointerNull::get(cast<PointerType>(
185
cast<PointerType>((*I)->getType())->getElementType())),
193
bool LowerIntrinsics::NeedsDefaultLoweringPass(const GCStrategy &C) {
194
// Default lowering is necessary only if read or write barriers have a default
195
// action. The default for roots is no action.
196
return !C.customWriteBarrier()
197
|| !C.customReadBarrier()
198
|| C.initializeRoots();
201
bool LowerIntrinsics::NeedsCustomLoweringPass(const GCStrategy &C) {
202
// Custom lowering is only necessary if enabled for some action.
203
return C.customWriteBarrier()
204
|| C.customReadBarrier()
208
/// CouldBecomeSafePoint - Predicate to conservatively determine whether the
209
/// instruction could introduce a safe point.
210
bool LowerIntrinsics::CouldBecomeSafePoint(Instruction *I) {
211
// The natural definition of instructions which could introduce safe points
214
// - call, invoke (AfterCall, BeforeCall)
216
// - invoke, ret, unwind (Exit)
218
// However, instructions as seemingly inoccuous as arithmetic can become
219
// libcalls upon lowering (e.g., div i64 on a 32-bit platform), so instead
220
// it is necessary to take a conservative approach.
222
if (isa<AllocaInst>(I) || isa<GetElementPtrInst>(I) ||
223
isa<StoreInst>(I) || isa<LoadInst>(I))
226
// llvm.gcroot is safe because it doesn't do anything at runtime.
227
if (CallInst *CI = dyn_cast<CallInst>(I))
228
if (Function *F = CI->getCalledFunction())
229
if (unsigned IID = F->getIntrinsicID())
230
if (IID == Intrinsic::gcroot)
236
/// runOnFunction - Replace gcread/gcwrite intrinsics with loads and stores.
237
/// Leave gcroot intrinsics; the code generator needs to see those.
238
bool LowerIntrinsics::runOnFunction(Function &F) {
239
// Quick exit for functions that do not use GC.
243
GCFunctionInfo &FI = getAnalysis<GCModuleInfo>().getFunctionInfo(F);
244
GCStrategy &S = FI.getStrategy();
246
bool MadeChange = false;
248
if (NeedsDefaultLoweringPass(S))
249
MadeChange |= PerformDefaultLowering(F, S);
251
if (NeedsCustomLoweringPass(S))
252
MadeChange |= S.performCustomLowering(F);
257
bool LowerIntrinsics::PerformDefaultLowering(Function &F, GCStrategy &S) {
258
bool LowerWr = !S.customWriteBarrier();
259
bool LowerRd = !S.customReadBarrier();
260
bool InitRoots = S.initializeRoots();
262
SmallVector<AllocaInst*,32> Roots;
264
bool MadeChange = false;
265
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
266
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
267
if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) {
268
Function *F = CI->getCalledFunction();
269
switch (F->getIntrinsicID()) {
270
case Intrinsic::gcwrite:
272
// Replace a write barrier with a simple store.
273
Value *St = new StoreInst(CI->getOperand(1), CI->getOperand(3), CI);
274
CI->replaceAllUsesWith(St);
275
CI->eraseFromParent();
278
case Intrinsic::gcread:
280
// Replace a read barrier with a simple load.
281
Value *Ld = new LoadInst(CI->getOperand(2), "", CI);
283
CI->replaceAllUsesWith(Ld);
284
CI->eraseFromParent();
287
case Intrinsic::gcroot:
289
// Initialize the GC root, but do not delete the intrinsic. The
290
// backend needs the intrinsic to flag the stack slot.
291
Roots.push_back(cast<AllocaInst>(
292
CI->getOperand(1)->stripPointerCasts()));
305
MadeChange |= InsertRootInitializers(F, Roots.begin(), Roots.size());
310
// -----------------------------------------------------------------------------
312
FunctionPass *llvm::createGCMachineCodeAnalysisPass() {
313
return new MachineCodeAnalysis();
316
char MachineCodeAnalysis::ID = 0;
318
MachineCodeAnalysis::MachineCodeAnalysis()
319
: MachineFunctionPass(&ID) {}
321
const char *MachineCodeAnalysis::getPassName() const {
322
return "Analyze Machine Code For Garbage Collection";
325
void MachineCodeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
326
MachineFunctionPass::getAnalysisUsage(AU);
327
AU.setPreservesAll();
328
AU.addRequired<MachineModuleInfo>();
329
AU.addRequired<GCModuleInfo>();
332
unsigned MachineCodeAnalysis::InsertLabel(MachineBasicBlock &MBB,
333
MachineBasicBlock::iterator MI,
335
unsigned Label = MMI->NextLabelID();
338
TII->get(TargetOpcode::GC_LABEL)).addImm(Label);
343
void MachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI) {
344
// Find the return address (next instruction), too, so as to bracket the call
346
MachineBasicBlock::iterator RAI = CI;
349
if (FI->getStrategy().needsSafePoint(GC::PreCall))
350
FI->addSafePoint(GC::PreCall, InsertLabel(*CI->getParent(), CI,
353
if (FI->getStrategy().needsSafePoint(GC::PostCall))
354
FI->addSafePoint(GC::PostCall, InsertLabel(*CI->getParent(), RAI,
358
void MachineCodeAnalysis::FindSafePoints(MachineFunction &MF) {
359
for (MachineFunction::iterator BBI = MF.begin(),
360
BBE = MF.end(); BBI != BBE; ++BBI)
361
for (MachineBasicBlock::iterator MI = BBI->begin(),
362
ME = BBI->end(); MI != ME; ++MI)
363
if (MI->getDesc().isCall())
367
void MachineCodeAnalysis::FindStackOffsets(MachineFunction &MF) {
368
const TargetRegisterInfo *TRI = TM->getRegisterInfo();
369
assert(TRI && "TargetRegisterInfo not available!");
371
for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
372
RE = FI->roots_end(); RI != RE; ++RI)
373
RI->StackOffset = TRI->getFrameIndexOffset(MF, RI->Num);
376
bool MachineCodeAnalysis::runOnMachineFunction(MachineFunction &MF) {
377
// Quick exit for functions that do not use GC.
378
if (!MF.getFunction()->hasGC())
381
FI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction());
382
if (!FI->getStrategy().needsSafePoints())
385
TM = &MF.getTarget();
386
MMI = &getAnalysis<MachineModuleInfo>();
387
TII = TM->getInstrInfo();
389
// Find the size of the stack frame.
390
FI->setFrameSize(MF.getFrameInfo()->getStackSize());
392
// Find all safe points.
395
// Find the stack offsets for all roots.
396
FindStackOffsets(MF);