Mercurial > projects > ldc

comparison gen/passes/GarbageCollect2Stack.cpp @ 1297:8e8552601ecd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Stack promotion for _d_newarrayvT. Array literals, concatenations (a ~ b) and such are eligible for stack-allocation now.
author Frits van Bommel <fvbommel wxs.nl>
date Sun, 03 May 2009 18:01:45 +0200
parents 0e79fb40c4d0
children 7e303f9f16c7
comparison
equal deleted inserted replaced
1296:79b201533cf8 1297:8e8552601ecd
27 #include "llvm/Module.h" 27 #include "llvm/Module.h"
28 #include "llvm/Support/CallSite.h" 28 #include "llvm/Support/CallSite.h"
29 #include "llvm/Support/CommandLine.h" 29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/IRBuilder.h" 30 #include "llvm/Support/IRBuilder.h"
31 #include "llvm/Analysis/CaptureTracking.h" 31 #include "llvm/Analysis/CaptureTracking.h"
32 #include "llvm/Analysis/ValueTracking.h"
32 #include "llvm/Analysis/LoopInfo.h" 33 #include "llvm/Analysis/LoopInfo.h"
33 #include "llvm/Target/TargetData.h" 34 #include "llvm/Target/TargetData.h"
34 #include "llvm/ADT/StringMap.h" 35 #include "llvm/ADT/StringMap.h"
35 #include "llvm/ADT/Statistic.h" 36 #include "llvm/ADT/Statistic.h"
36 #include "llvm/Support/Compiler.h" 37 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/Debug.h"
38 using namespace llvm; 39 using namespace llvm;
39 40
40 STATISTIC(NumGcToStack, "Number of GC calls promoted to stack allocations"); 41 STATISTIC(NumGcToStack, "Number of calls promoted to constant-size allocas");
42 STATISTIC(NumToDynSize, "Number of calls promoted to dynamically-sized allocas");
41 STATISTIC(NumDeleted, "Number of GC calls deleted because the return value was unused"); 43 STATISTIC(NumDeleted, "Number of GC calls deleted because the return value was unused");
42 44
43 //===----------------------------------------------------------------------===// 45 //===----------------------------------------------------------------------===//
44 // GarbageCollect2Stack Pass Implementation 46 // GarbageCollect2Stack Pass Implementation
45 //===----------------------------------------------------------------------===// 47 //===----------------------------------------------------------------------===//
46 48
47 namespace { 49 namespace {
48 struct FunctionInfo { 50 struct FunctionInfo {
49 unsigned TypeInfoArgNr; 51 unsigned TypeInfoArgNr;
52 int ArrSizeArgNr;
50 bool SafeToDelete; 53 bool SafeToDelete;
51 54
52 FunctionInfo(unsigned typeInfoArgNr, bool safeToDelete) 55 FunctionInfo(unsigned typeInfoArgNr, int arrSizeArgNr, bool safeToDelete)
53 : TypeInfoArgNr(typeInfoArgNr), SafeToDelete(safeToDelete) {} 56 : TypeInfoArgNr(typeInfoArgNr), ArrSizeArgNr(arrSizeArgNr),
54 57 SafeToDelete(safeToDelete) {}
55 Value* getArraySize(CallSite CS) {
56 return 0;
57 }
58 }; 58 };
59 59
60 /// This pass replaces GC calls with alloca's 60 /// This pass replaces GC calls with alloca's
61 /// 61 ///
62 class VISIBILITY_HIDDEN GarbageCollect2Stack : public FunctionPass { 62 class VISIBILITY_HIDDEN GarbageCollect2Stack : public FunctionPass {
90 return new GarbageCollect2Stack(); 90 return new GarbageCollect2Stack();
91 } 91 }
92 92
93 bool GarbageCollect2Stack::doInitialization(Module &M) { 93 bool GarbageCollect2Stack::doInitialization(Module &M) {
94 this->M = &M; 94 this->M = &M;
95 KnownFunctions["_d_allocmemoryT"] = new FunctionInfo(0, true); 95 KnownFunctions["_d_allocmemoryT"] = new FunctionInfo(0, -1, true);
96 KnownFunctions["_d_newarrayvT"] = new FunctionInfo(0, 1, true);
96 } 97 }
97 98
98 /// runOnFunction - Top level algorithm. 99 /// runOnFunction - Top level algorithm.
99 /// 100 ///
100 bool GarbageCollect2Stack::runOnFunction(Function &F) { 101 bool GarbageCollect2Stack::runOnFunction(Function &F) {
101 DEBUG(DOUT << "Running -dgc2stack on function " << F.getName() << '\n'); 102 DEBUG(DOUT << "Running -dgc2stack on function " << F.getName() << '\n');
102 103
103 const TargetData &TD = getAnalysis<TargetData>(); 104 TargetData &TD = getAnalysis<TargetData>();
104 const LoopInfo &LI = getAnalysis<LoopInfo>(); 105 const LoopInfo &LI = getAnalysis<LoopInfo>();
105 106
106 BasicBlock& Entry = F.getEntryBlock(); 107 BasicBlock& Entry = F.getEntryBlock();
107 108
108 IRBuilder<> AllocaBuilder(&Entry, Entry.begin()); 109 IRBuilder<> AllocaBuilder(&Entry, Entry.begin());
159 const Type* Ty = getTypeFor(TypeInfo); 160 const Type* Ty = getTypeFor(TypeInfo);
160 if (!Ty) { 161 if (!Ty) {
161 continue; 162 continue;
162 } 163 }
163 164
165 Value* arrSize = 0;
166 if (info->ArrSizeArgNr != -1) {
167 arrSize = CS.getArgument(info->ArrSizeArgNr);
168 const IntegerType* SizeType =
169 dyn_cast<IntegerType>(arrSize->getType());
170 if (!SizeType)
171 continue;
172 unsigned bits = SizeType->getBitWidth();
173 if (bits > 32) {
174 // The array size of an alloca must be an i32, so make sure
175 // the conversion is safe.
176 APInt Mask = APInt::getHighBitsSet(bits, bits - 32);
177 APInt KnownZero(bits, 0), KnownOne(bits, 0);
178 ComputeMaskedBits(arrSize, Mask, KnownZero, KnownOne, &TD);
179 if ((KnownZero & Mask) != Mask)
180 continue;
181 }
182 // Extract the element type from the array type.
183 const StructType* ArrTy = dyn_cast<StructType>(Ty);
184 assert(ArrTy && "Dynamic array type not a struct?");
185 assert(isa<IntegerType>(ArrTy->getElementType(0)));
186 const PointerType* PtrTy =
187 cast<PointerType>(ArrTy->getElementType(1));
188 Ty = PtrTy->getElementType();
189 }
190
164 // Let's alloca this! 191 // Let's alloca this!
165 Changed = true; 192 Changed = true;
166 NumGcToStack++; 193
167 194 IRBuilder<> Builder(BB, I);
168 Value* arrSize = info->getArraySize(CS); 195
169 Value* newVal = AllocaBuilder.CreateAlloca(Ty, arrSize, ".nongc_mem"); 196 // If the allocation is of constant size it's best to put it in the
170 197 // entry block, so do so if we're not already there.
198 // For dynamically-sized allocations it's best to avoid the overhead
199 // of allocating them if possible, so leave those where they are.
200 // While we're at it, update statistics too.
201 if (!arrSize || isa<Constant>(arrSize)) {
202 if (&*BB != &Entry)
203 Builder = AllocaBuilder;
204 NumGcToStack++;
205 } else {
206 NumToDynSize++;
207 }
208
209 // Convert array size to 32 bits if necessary
210 if (arrSize)
211 arrSize = Builder.CreateIntCast(arrSize, Type::Int32Ty, false);
212
213 Value* newVal = Builder.CreateAlloca(Ty, arrSize, ".nongc_mem");
214
215 // Make sure the type is the same as it was before, and replace all
216 // uses of the runtime call with the alloca.
171 if (newVal->getType() != Inst->getType()) 217 if (newVal->getType() != Inst->getType())
172 newVal = AllocaBuilder.CreateBitCast(newVal, Inst->getType()); 218 newVal = Builder.CreateBitCast(newVal, Inst->getType());
173
174 Inst->replaceAllUsesWith(newVal); 219 Inst->replaceAllUsesWith(newVal);
175 220
221 // If this was an invoke instruction, update the control flow.
176 if (InvokeInst* Invoke = dyn_cast<InvokeInst>(Inst)) { 222 if (InvokeInst* Invoke = dyn_cast<InvokeInst>(Inst)) {
223 // Notify the exception landing pad block that we won't be
224 // going there anymore.
177 Invoke->getUnwindDest()->removePredecessor(Invoke->getParent()); 225 Invoke->getUnwindDest()->removePredecessor(Invoke->getParent());
178 // Create a branch to the "normal" destination. 226 // Create a branch to the "normal" destination.
179 BranchInst::Create(Invoke->getNormalDest(), Invoke->getParent()); 227 BranchInst::Create(Invoke->getNormalDest(), Invoke->getParent());
180 } 228 }
229
230 // Finally, remove the runtime call.
181 Inst->eraseFromParent(); 231 Inst->eraseFromParent();
182 } 232 }
183 } 233 }
234
184 return Changed; 235 return Changed;
185 } 236 }
186 237
187 const Type* GarbageCollect2Stack::getTypeFor(Value* typeinfo) { 238 const Type* GarbageCollect2Stack::getTypeFor(Value* typeinfo) {
188 GlobalVariable* ti_global = dyn_cast<GlobalVariable>(typeinfo->stripPointerCasts()); 239 GlobalVariable* ti_global = dyn_cast<GlobalVariable>(typeinfo->stripPointerCasts());