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
->getOperand(1), CI
->getOperand(3), CI
);
275 CI
->replaceAllUsesWith(St
);
276 CI
->eraseFromParent();
279 case Intrinsic::gcread
:
281 // Replace a read barrier with a simple load.
282 Value
*Ld
= new LoadInst(CI
->getOperand(2), "", CI
);
284 CI
->replaceAllUsesWith(Ld
);
285 CI
->eraseFromParent();
288 case Intrinsic::gcroot
:
290 // Initialize the GC root, but do not delete the intrinsic. The
291 // backend needs the intrinsic to flag the stack slot.
292 Roots
.push_back(cast
<AllocaInst
>(
293 CI
->getOperand(1)->stripPointerCasts()));
306 MadeChange
|= InsertRootInitializers(F
, Roots
.begin(), Roots
.size());
311 // -----------------------------------------------------------------------------
313 FunctionPass
*llvm::createGCMachineCodeAnalysisPass() {
314 return new MachineCodeAnalysis();
317 char MachineCodeAnalysis::ID
= 0;
319 MachineCodeAnalysis::MachineCodeAnalysis()
320 : MachineFunctionPass(&ID
) {}
322 const char *MachineCodeAnalysis::getPassName() const {
323 return "Analyze Machine Code For Garbage Collection";
326 void MachineCodeAnalysis::getAnalysisUsage(AnalysisUsage
&AU
) const {
327 MachineFunctionPass::getAnalysisUsage(AU
);
328 AU
.setPreservesAll();
329 AU
.addRequired
<MachineModuleInfo
>();
330 AU
.addRequired
<GCModuleInfo
>();
333 MCSymbol
*MachineCodeAnalysis::InsertLabel(MachineBasicBlock
&MBB
,
334 MachineBasicBlock::iterator MI
,
336 MCSymbol
*Label
= MBB
.getParent()->getContext().CreateTempSymbol();
337 BuildMI(MBB
, MI
, DL
, TII
->get(TargetOpcode::GC_LABEL
)).addSym(Label
);
341 void MachineCodeAnalysis::VisitCallPoint(MachineBasicBlock::iterator CI
) {
342 // Find the return address (next instruction), too, so as to bracket the call
344 MachineBasicBlock::iterator RAI
= CI
;
347 if (FI
->getStrategy().needsSafePoint(GC::PreCall
))
348 FI
->addSafePoint(GC::PreCall
, InsertLabel(*CI
->getParent(), CI
,
351 if (FI
->getStrategy().needsSafePoint(GC::PostCall
))
352 FI
->addSafePoint(GC::PostCall
, InsertLabel(*CI
->getParent(), RAI
,
356 void MachineCodeAnalysis::FindSafePoints(MachineFunction
&MF
) {
357 for (MachineFunction::iterator BBI
= MF
.begin(),
358 BBE
= MF
.end(); BBI
!= BBE
; ++BBI
)
359 for (MachineBasicBlock::iterator MI
= BBI
->begin(),
360 ME
= BBI
->end(); MI
!= ME
; ++MI
)
361 if (MI
->getDesc().isCall())
365 void MachineCodeAnalysis::FindStackOffsets(MachineFunction
&MF
) {
366 const TargetRegisterInfo
*TRI
= TM
->getRegisterInfo();
367 assert(TRI
&& "TargetRegisterInfo not available!");
369 for (GCFunctionInfo::roots_iterator RI
= FI
->roots_begin(),
370 RE
= FI
->roots_end(); RI
!= RE
; ++RI
)
371 RI
->StackOffset
= TRI
->getFrameIndexOffset(MF
, RI
->Num
);
374 bool MachineCodeAnalysis::runOnMachineFunction(MachineFunction
&MF
) {
375 // Quick exit for functions that do not use GC.
376 if (!MF
.getFunction()->hasGC())
379 FI
= &getAnalysis
<GCModuleInfo
>().getFunctionInfo(*MF
.getFunction());
380 if (!FI
->getStrategy().needsSafePoints())
383 TM
= &MF
.getTarget();
384 MMI
= &getAnalysis
<MachineModuleInfo
>();
385 TII
= TM
->getInstrInfo();
387 // Find the size of the stack frame.
388 FI
->setFrameSize(MF
.getFrameInfo()->getStackSize());
390 // Find all safe points.
393 // Find the stack offsets for all roots.
394 FindStackOffsets(MF
);