Mercurial > projects > ldc

comparison gen/passes/GarbageCollect2Stack.cpp @ 1285:91d9386d4a5a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement another D-specific pass: -dgc2stack This one promotes GC allocations to stack memory when it can determine it's safe to do so. Not all GC calls are recognized yet (in fact only one *is* recognized for now). Needs metadata, so disabled for LLVM versions that don't support it.
author Frits van Bommel <fvbommel wxs.nl>
date Sat, 02 May 2009 11:58:50 +0200
parents
children 875afb7a93b6
comparison
equal deleted inserted replaced
1284:5851c18e4c6d 1285:91d9386d4a5a
1 //===- GarbageCollect2Stack - Optimize calls to the D garbage collector ---===//
2 //
3 // The LLVM D Compiler
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file attempts to turn allocations on the garbage-collected heap into
11 // stack allocations.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "gen/metadata.h"
16
17 // This pass doesn't work without metadata, so #ifdef it out entirely if the
18 // LLVM version in use doesn't support it.
19 #ifdef USE_METADATA
20
21
22 #define DEBUG_TYPE "dgc2stack"
23
24 #include "Passes.h"
25
26 #include "llvm/Pass.h"
27 #include "llvm/Module.h"
28 #include "llvm/Support/CallSite.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/IRBuilder.h"
31 #include "llvm/Analysis/CaptureTracking.h"
32 #include "llvm/Analysis/LoopInfo.h"
33 #include "llvm/Target/TargetData.h"
34 #include "llvm/ADT/StringMap.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/Debug.h"
38 using namespace llvm;
39
40 STATISTIC(NumGcToStack, "Number of GC calls promoted to stack allocations");
41 STATISTIC(NumDeleted, "Number of GC calls deleted because the return value was unused");
42
43 //===----------------------------------------------------------------------===//
44 // GarbageCollect2Stack Pass Implementation
45 //===----------------------------------------------------------------------===//
46
47 namespace {
48 struct FunctionInfo {
49 unsigned TypeInfoArgNr;
50 bool SafeToDelete;
51
52 FunctionInfo(unsigned typeInfoArgNr, bool safeToDelete)
53 : TypeInfoArgNr(typeInfoArgNr), SafeToDelete(safeToDelete) {}
54
55 Value* getArraySize(CallSite CS) {
56 return 0;
57 }
58 };
59
60 /// This pass replaces GC calls with alloca's
61 ///
62 class VISIBILITY_HIDDEN GarbageCollect2Stack : public FunctionPass {
63 StringMap<FunctionInfo*> KnownFunctions;
64 Module* M;
65
66 public:
67 static char ID; // Pass identification
68 GarbageCollect2Stack() : FunctionPass(&ID) {}
69
70 bool doInitialization(Module &M);
71
72 bool runOnFunction(Function &F);
73
74 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
75 AU.addRequired<TargetData>();
76 AU.addRequired<LoopInfo>();
77 }
78
79 private:
80 const Type* getTypeFor(Value* typeinfo);
81 };
82 char GarbageCollect2Stack::ID = 0;
83 } // end anonymous namespace.
84
85 static RegisterPass<GarbageCollect2Stack>
86 X("dgc2stack", "Promote (GC'ed) heap allocations to stack");
87
88 // Public interface to the pass.
89 FunctionPass *createGarbageCollect2Stack() {
90 return new GarbageCollect2Stack();
91 }
92
93 bool GarbageCollect2Stack::doInitialization(Module &M) {
94 this->M = &M;
95 KnownFunctions["_d_allocmemoryT"] = new FunctionInfo(0, true);
96 }
97
98 /// runOnFunction - Top level algorithm.
99 ///
100 bool GarbageCollect2Stack::runOnFunction(Function &F) {
101 DEBUG(DOUT << "Running on function " << F.getName() << '\n');
102
103 const TargetData &TD = getAnalysis<TargetData>();
104 const LoopInfo &LI = getAnalysis<LoopInfo>();
105
106 BasicBlock& Entry = F.getEntryBlock();
107
108 IRBuilder<> AllocaBuilder(&Entry, Entry.begin());
109
110 bool Changed = false;
111 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
112 // We don't yet have sufficient analysis to properly determine if
113 // allocations will be unreferenced when the loop returns to their
114 // allocation point, so we're playing it safe by ignoring allocations
115 // in loops.
116 // TODO: Analyze loops too...
117 if (LI.getLoopFor(BB)) {
118 DEBUG(DOUT << "Skipping loop block " << *BB << '\n');
119 continue;
120 }
121
122 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
123 // Ignore non-calls.
124 Instruction* Inst = I++;
125 CallSite CS = CallSite::get(Inst);
126 if (!CS.getInstruction())
127 continue;
128
129 // Ignore indirect calls and calls to non-external functions.
130 Function *Callee = CS.getCalledFunction();
131 if (Callee == 0 || !Callee->isDeclaration() ||
132 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
133 continue;
134
135 // Ignore unknown calls.
136 const char *CalleeName = Callee->getNameStart();
137 StringMap<FunctionInfo*>::iterator OMI =
138 KnownFunctions.find(CalleeName, CalleeName+Callee->getNameLen());
139 if (OMI == KnownFunctions.end()) continue;
140
141 assert(isa<PointerType>(Inst->getType())
142 && "GC function doesn't return a pointer?");
143
144 FunctionInfo* info = OMI->getValue();
145
146 if (Inst->use_empty() && info->SafeToDelete) {
147 Changed = true;
148 NumDeleted++;
149 Inst->eraseFromParent();
150 continue;
151 }
152
153 DEBUG(DOUT << "GarbageCollect2Stack inspecting: " << *Inst);
154
155 if (PointerMayBeCaptured(Inst, true)) {
156 DEBUG(DOUT << ">> is captured :(\n");
157 continue;
158 }
159 DEBUG(DOUT << ">> is not captured :)\n");
160
161 Value* TypeInfo = CS.getArgument(info->TypeInfoArgNr);
162 const Type* Ty = getTypeFor(TypeInfo);
163 if (!Ty) {
164 DEBUG(DOUT << ">> Couldn't find valid TypeInfo metadata :(\n");
165 continue;
166 }
167
168 // Let's alloca this!
169 Changed = true;
170 NumGcToStack++;
171
172 Value* arrSize = info->getArraySize(CS);
173 Value* newVal = AllocaBuilder.CreateAlloca(Ty, arrSize, ".nongc_mem");
174
175 if (newVal->getType() != Inst->getType())
176 newVal = AllocaBuilder.CreateBitCast(newVal, Inst->getType());
177
178 Inst->replaceAllUsesWith(newVal);
179
180 if (InvokeInst* Invoke = dyn_cast<InvokeInst>(Inst)) {
181 Invoke->getUnwindDest()->removePredecessor(Invoke->getParent());
182 // Create a branch to the "normal" destination.
183 BranchInst::Create(Invoke->getNormalDest(), Invoke->getParent());
184 }
185 Inst->eraseFromParent();
186 }
187 }
188 return Changed;
189 }
190
191 const Type* GarbageCollect2Stack::getTypeFor(Value* typeinfo) {
192 GlobalVariable* ti_global = dyn_cast<GlobalVariable>(typeinfo->stripPointerCasts());
193 if (!ti_global)
194 return NULL;
195
196 DEBUG(DOUT << ">> Found typeinfo init\n";
197 DOUT << ">> Value: " << *ti_global << "\n";
198 DOUT << ">> Name: " << ti_global->getNameStr() << "\n");
199
200 std::string metaname = "llvm.ldc.typeinfo.";
201 metaname.append(ti_global->getNameStart(), ti_global->getNameEnd());
202
203 DEBUG(DOUT << ">> Looking for global named " << metaname << "\n");
204
205 GlobalVariable* global = M->getGlobalVariable(metaname);
206 DEBUG(DOUT << ">> global: " << global->getInitializer() << "\n");
207 if (!global || !global->hasInitializer())
208 return NULL;
209
210 DEBUG(DOUT << ">> Found metadata global\n");
211
212 MDNode* node = dyn_cast<MDNode>(global->getInitializer());
213 if (!node)
214 return NULL;
215
216 DEBUG(DOUT << ">> Found metadata node\n");
217
218 if (node->getNumOperands() != 2 ||
219 node->getOperand(0)->stripPointerCasts() != ti_global)
220 return NULL;
221
222 DEBUG(DOUT << ">> Validated metadata node\n");
223
224 return node->getOperand(1)->getType();
225 }
226
227
228 #endif //USE_METADATA