Mercurial > projects > ldc
comparison gen/passes/SimplifyDRuntimeCalls.cpp @ 1275:bedf0bfb8fdb
Implement first D-specific optimization pass: -simplify-drtcalls.
It uses the machinery of the standard -simplify-libcalls pass, but optimizes
calls to the D runtime instead of calls to C libraries.
At the moment, these optimizations are implemented by this pass:
- Avoid the runtime call for `arr.length = newlen` if it can determine that
the new length isn't longer than the old one.
- Ditto for `cast(T[]) arr` if it will clearly always succeed.
(e.g. if the length of the original array is zero, or if the old element
size is a multiple of the new element size)
author | Frits van Bommel <fvbommel wxs.nl> |
---|---|
date | Tue, 28 Apr 2009 21:58:06 +0200 |
parents | |
children | 23b23b74e326 |
comparison
equal
deleted
inserted
replaced
1274:4ff9ab0d472c | 1275:bedf0bfb8fdb |
---|---|
1 //===- SimplifyDRuntimeCalls - Optimize calls to the D runtime library ----===// | |
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 implements a simple pass that applies a variety of small | |
11 // optimizations for calls to specific functions in the D runtime. | |
12 // | |
13 // The machinery was copied from the standard -simplify-libcalls LLVM pass. | |
14 // | |
15 //===----------------------------------------------------------------------===// | |
16 | |
17 #define DEBUG_TYPE "simplify-drtcalls" | |
18 | |
19 #include "Passes.h" | |
20 | |
21 #include "llvm/Pass.h" | |
22 #include "llvm/Support/IRBuilder.h" | |
23 #include "llvm/Analysis/ValueTracking.h" | |
24 #include "llvm/Target/TargetData.h" | |
25 #include "llvm/ADT/StringMap.h" | |
26 #include "llvm/ADT/Statistic.h" | |
27 #include "llvm/Support/Compiler.h" | |
28 #include "llvm/Support/Debug.h" | |
29 using namespace llvm; | |
30 | |
31 STATISTIC(NumSimplified, "Number of runtime calls simplified"); | |
32 | |
33 //===----------------------------------------------------------------------===// | |
34 // Optimizer Base Class | |
35 //===----------------------------------------------------------------------===// | |
36 | |
37 /// This class is the abstract base class for the set of optimizations that | |
38 /// corresponds to one library call. | |
39 namespace { | |
40 class VISIBILITY_HIDDEN LibCallOptimization { | |
41 protected: | |
42 Function *Caller; | |
43 const TargetData *TD; | |
44 public: | |
45 LibCallOptimization() { } | |
46 virtual ~LibCallOptimization() {} | |
47 | |
48 /// CallOptimizer - This pure virtual method is implemented by base classes to | |
49 /// do various optimizations. If this returns null then no transformation was | |
50 /// performed. If it returns CI, then it transformed the call and CI is to be | |
51 /// deleted. If it returns something else, replace CI with the new value and | |
52 /// delete CI. | |
53 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)=0; | |
54 | |
55 Value *OptimizeCall(CallInst *CI, const TargetData &TD, IRBuilder<> &B) { | |
56 Caller = CI->getParent()->getParent(); | |
57 this->TD = &TD; | |
58 return CallOptimizer(CI->getCalledFunction(), CI, B); | |
59 } | |
60 }; | |
61 } // End anonymous namespace. | |
62 | |
63 | |
64 //===----------------------------------------------------------------------===// | |
65 // Miscellaneous LibCall Optimizations | |
66 //===----------------------------------------------------------------------===// | |
67 | |
68 namespace { | |
69 //===---------------------------------------===// | |
70 // '_d_arraysetlengthT'/'_d_arraysetlengthiT' Optimizations | |
71 | |
72 /// ArraySetLengthOpt - remove libcall for arr.length = N if N <= arr.length | |
73 struct VISIBILITY_HIDDEN ArraySetLengthOpt : public LibCallOptimization { | |
74 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { | |
75 // Verify we have a reasonable prototype for _d_arraysetlength[i]T | |
76 const FunctionType *FT = Callee->getFunctionType(); | |
77 if (Callee->arg_size() != 4 || !isa<PointerType>(FT->getReturnType()) || | |
78 !isa<IntegerType>(FT->getParamType(1)) || | |
79 FT->getParamType(1) != FT->getParamType(2) || | |
80 FT->getParamType(3) != FT->getReturnType()) | |
81 return 0; | |
82 | |
83 Value* NewLen = CI->getOperand(2); | |
84 if (Constant* NewCst = dyn_cast<Constant>(NewLen)) { | |
85 Value* Data = CI->getOperand(4); | |
86 | |
87 // For now, we just catch the simplest of cases. | |
88 // | |
89 // TODO: Implement a more general way to compare old and new | |
90 // lengths, to catch cases like "arr.length = arr.length - 1;" | |
91 // (But beware of unsigned overflow! For example, we can't | |
92 // safely transform that example if arr.length may be 0) | |
93 | |
94 // Setting length to 0 never reallocates, so replace by data argument | |
95 if (NewCst->isNullValue()) | |
96 return Data; | |
97 | |
98 // If both lengths are constant integers, see if NewLen <= OldLen | |
99 Value* OldLen = CI->getOperand(3); | |
100 if (ConstantInt* OldInt = dyn_cast<ConstantInt>(OldLen)) | |
101 if (ConstantInt* NewInt = dyn_cast<ConstantInt>(NewCst)) | |
102 if (NewInt->getValue().ule(OldInt->getValue())) | |
103 return Data; | |
104 } | |
105 return 0; | |
106 } | |
107 }; | |
108 | |
109 /// ArrayCastLenOpt - remove libcall for cast(T[]) arr if it's safe to do so. | |
110 struct VISIBILITY_HIDDEN ArrayCastLenOpt : public LibCallOptimization { | |
111 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { | |
112 // Verify we have a reasonable prototype for _d_array_cast_len | |
113 const FunctionType *FT = Callee->getFunctionType(); | |
114 const Type* RetTy = FT->getReturnType(); | |
115 if (Callee->arg_size() != 3 || !isa<IntegerType>(RetTy) || | |
116 FT->getParamType(1) != RetTy || FT->getParamType(2) != RetTy) | |
117 return 0; | |
118 | |
119 Value* OldLen = CI->getOperand(1); | |
120 Value* OldSize = CI->getOperand(2); | |
121 Value* NewSize = CI->getOperand(3); | |
122 | |
123 // If the old length was zero, always return zero. | |
124 if (Constant* LenCst = dyn_cast<Constant>(OldLen)) | |
125 if (LenCst->isNullValue()) | |
126 return OldLen; | |
127 | |
128 // Equal sizes are much faster to check for, so do so now. | |
129 if (OldSize == NewSize) | |
130 return OldLen; | |
131 | |
132 // If both sizes are constant integers, see if OldSize is a multiple of NewSize | |
133 if (ConstantInt* OldInt = dyn_cast<ConstantInt>(OldSize)) | |
134 if (ConstantInt* NewInt = dyn_cast<ConstantInt>(NewSize)) { | |
135 // Don't crash on NewSize == 0, even though it shouldn't happen. | |
136 if (NewInt->isNullValue()) | |
137 return 0; | |
138 | |
139 APInt Quot, Rem; | |
140 APInt::udivrem(OldInt->getValue(), NewInt->getValue(), Quot, Rem); | |
141 if (Rem == 0) | |
142 return B.CreateMul(OldLen, ConstantInt::get(Quot)); | |
143 } | |
144 return 0; | |
145 } | |
146 }; | |
147 | |
148 // TODO: More optimizations! :) | |
149 | |
150 } // end anonymous namespace. | |
151 | |
152 //===----------------------------------------------------------------------===// | |
153 // SimplifyDRuntimeCalls Pass Implementation | |
154 //===----------------------------------------------------------------------===// | |
155 | |
156 namespace { | |
157 /// This pass optimizes library functions from the D runtime as used by LDC. | |
158 /// | |
159 class VISIBILITY_HIDDEN SimplifyDRuntimeCalls : public FunctionPass { | |
160 StringMap<LibCallOptimization*> Optimizations; | |
161 | |
162 // Array operations | |
163 ArraySetLengthOpt ArraySetLength; | |
164 ArrayCastLenOpt ArrayCastLen; | |
165 | |
166 public: | |
167 static char ID; // Pass identification | |
168 SimplifyDRuntimeCalls() : FunctionPass(&ID) {} | |
169 | |
170 void InitOptimizations(); | |
171 bool runOnFunction(Function &F); | |
172 | |
173 virtual void getAnalysisUsage(AnalysisUsage &AU) const { | |
174 AU.addRequired<TargetData>(); | |
175 } | |
176 }; | |
177 char SimplifyDRuntimeCalls::ID = 0; | |
178 } // end anonymous namespace. | |
179 | |
180 static RegisterPass<SimplifyDRuntimeCalls> | |
181 X("simplify-drtcalls", "Simplify calls to D runtime"); | |
182 | |
183 // Public interface to the pass. | |
184 FunctionPass *createSimplifyDRuntimeCalls() { | |
185 return new SimplifyDRuntimeCalls(); | |
186 } | |
187 | |
188 /// Optimizations - Populate the Optimizations map with all the optimizations | |
189 /// we know. | |
190 void SimplifyDRuntimeCalls::InitOptimizations() { | |
191 Optimizations["_d_arraysetlengthT"] = &ArraySetLength; | |
192 Optimizations["_d_arraysetlengthiT"] = &ArraySetLength; | |
193 Optimizations["_d_array_cast_len"] = &ArrayCastLen; | |
194 } | |
195 | |
196 | |
197 /// runOnFunction - Top level algorithm. | |
198 /// | |
199 bool SimplifyDRuntimeCalls::runOnFunction(Function &F) { | |
200 if (Optimizations.empty()) | |
201 InitOptimizations(); | |
202 | |
203 const TargetData &TD = getAnalysis<TargetData>(); | |
204 | |
205 IRBuilder<> Builder; | |
206 | |
207 bool Changed = false; | |
208 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { | |
209 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { | |
210 // Ignore non-calls. | |
211 CallInst *CI = dyn_cast<CallInst>(I++); | |
212 if (!CI) continue; | |
213 | |
214 // Ignore indirect calls and calls to non-external functions. | |
215 Function *Callee = CI->getCalledFunction(); | |
216 if (Callee == 0 || !Callee->isDeclaration() || | |
217 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage())) | |
218 continue; | |
219 | |
220 DEBUG(DOUT << "SimplifyDRuntimeCalls inspecting: " << *CI); | |
221 | |
222 // Ignore unknown calls. | |
223 const char *CalleeName = Callee->getNameStart(); | |
224 StringMap<LibCallOptimization*>::iterator OMI = | |
225 Optimizations.find(CalleeName, CalleeName+Callee->getNameLen()); | |
226 if (OMI == Optimizations.end()) continue; | |
227 | |
228 // Set the builder to the instruction after the call. | |
229 Builder.SetInsertPoint(BB, I); | |
230 | |
231 // Try to optimize this call. | |
232 Value *Result = OMI->second->OptimizeCall(CI, TD, Builder); | |
233 if (Result == 0) continue; | |
234 | |
235 DEBUG(DOUT << "SimplifyDRuntimeCalls simplified: " << *CI; | |
236 DOUT << " into: " << *Result << "\n"); | |
237 | |
238 // Something changed! | |
239 Changed = true; | |
240 ++NumSimplified; | |
241 | |
242 // Inspect the instruction after the call (which was potentially just | |
243 // added) next. | |
244 I = CI; ++I; | |
245 | |
246 if (CI != Result && !CI->use_empty()) { | |
247 CI->replaceAllUsesWith(Result); | |
248 if (!Result->hasName()) | |
249 Result->takeName(CI); | |
250 } | |
251 CI->eraseFromParent(); | |
252 } | |
253 } | |
254 return Changed; | |
255 } |