blob: e82fe2c70d16883d21dfe210de131e3145fc986d [file] [log] [blame]
Reid Spencer9bbaa2a2005-04-25 03:59:26 +00001//===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
Reid Spencer39a762d2005-04-25 02:53:12 +00002//
3// The LLVM Compiler Infrastructure
4//
Reid Spencer9bbaa2a2005-04-25 03:59:26 +00005// This file was developed by Reid Spencer and is distributed under the
6// University of Illinois Open Source License. See LICENSE.TXT for details.
Reid Spencer39a762d2005-04-25 02:53:12 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a variety of small optimizations for calls to specific
11// well-known (e.g. runtime library) function calls. For example, a call to the
12// function "exit(3)" that occurs within the main() function can be transformed
Reid Spencer9bbaa2a2005-04-25 03:59:26 +000013// into a simple "return 3" instruction. Any optimization that takes this form
14// (replace call to library function with simpler code that provides same
15// result) belongs in this file.
Reid Spencer39a762d2005-04-25 02:53:12 +000016//
17//===----------------------------------------------------------------------===//
18
Reid Spencer18b99812005-04-26 23:05:17 +000019#define DEBUG_TYPE "simplify-libcalls"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000020#include "llvm/Constants.h"
21#include "llvm/DerivedTypes.h"
22#include "llvm/Instructions.h"
Reid Spencer39a762d2005-04-25 02:53:12 +000023#include "llvm/Module.h"
24#include "llvm/Pass.h"
Reid Spencer9bbaa2a2005-04-25 03:59:26 +000025#include "llvm/ADT/hash_map"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000026#include "llvm/ADT/Statistic.h"
27#include "llvm/Support/Debug.h"
Reid Spencerbb92b4f2005-04-26 19:13:17 +000028#include "llvm/Target/TargetData.h"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000029#include "llvm/Transforms/IPO.h"
Reid Spencerf2534c72005-04-25 21:11:48 +000030#include <iostream>
Reid Spencer39a762d2005-04-25 02:53:12 +000031using namespace llvm;
32
33namespace {
34 Statistic<> SimplifiedLibCalls("simplified-lib-calls",
35 "Number of well-known library calls simplified");
36
37 /// This class is the base class for a set of small but important
38 /// optimizations of calls to well-known functions, such as those in the c
39 /// library. This class provides the basic infrastructure for handling
40 /// runOnModule. Subclasses register themselves and provide two methods:
41 /// RecognizeCall and OptimizeCall. Whenever this class finds a function call,
42 /// it asks the subclasses to recognize the call. If it is recognized, then
43 /// the OptimizeCall method is called on that subclass instance. In this way
44 /// the subclasses implement the calling conditions on which they trigger and
45 /// the action to perform, making it easy to add new optimizations of this
46 /// form.
47 /// @brief A ModulePass for optimizing well-known function calls
48 struct SimplifyLibCalls : public ModulePass {
49
Reid Spencerbb92b4f2005-04-26 19:13:17 +000050 /// We need some target data for accurate signature details that are
51 /// target dependent. So we require target data in our AnalysisUsage.
52 virtual void getAnalysisUsage(AnalysisUsage& Info) const;
Reid Spencer39a762d2005-04-25 02:53:12 +000053
54 /// For this pass, process all of the function calls in the module, calling
55 /// RecognizeCall and OptimizeCall as appropriate.
56 virtual bool runOnModule(Module &M);
57
58 };
59
60 RegisterOpt<SimplifyLibCalls>
61 X("simplify-libcalls","Simplify well-known library calls");
62
63 struct CallOptimizer
64 {
65 /// @brief Constructor that registers the optimization
Reid Spencer9bbaa2a2005-04-25 03:59:26 +000066 CallOptimizer(const char * fname );
Reid Spencer39a762d2005-04-25 02:53:12 +000067
68 virtual ~CallOptimizer();
69
Reid Spencerf2534c72005-04-25 21:11:48 +000070 /// The implementation of this function in subclasses should determine if
71 /// \p F is suitable for the optimization. This method is called by
72 /// runOnModule to short circuit visiting all the call sites of such a
73 /// function if that function is not suitable in the first place.
74 /// If the called function is suitabe, this method should return true;
75 /// false, otherwise. This function should also perform any lazy
76 /// initialization that the CallOptimizer needs to do, if its to return
77 /// true. This avoids doing initialization until the optimizer is actually
78 /// going to be called upon to do some optimization.
79 virtual bool ValidateCalledFunction(
Reid Spencerbb92b4f2005-04-26 19:13:17 +000080 const Function* F, ///< The function that is the target of call sites
81 const TargetData& TD ///< Information about the target
Reid Spencer8ee5aac2005-04-26 03:26:15 +000082 ) = 0;
Reid Spencerf2534c72005-04-25 21:11:48 +000083
Reid Spencer39a762d2005-04-25 02:53:12 +000084 /// The implementations of this function in subclasses is the heart of the
85 /// SimplifyLibCalls algorithm. Sublcasses of this class implement
86 /// OptimizeCall to determine if (a) the conditions are right for optimizing
87 /// the call and (b) to perform the optimization. If an action is taken
88 /// against ci, the subclass is responsible for returning true and ensuring
89 /// that ci is erased from its parent.
90 /// @param ci the call instruction under consideration
91 /// @param f the function that ci calls.
92 /// @brief Optimize a call, if possible.
Reid Spencerf2534c72005-04-25 21:11:48 +000093 virtual bool OptimizeCall(
Reid Spencerbb92b4f2005-04-26 19:13:17 +000094 CallInst* ci, ///< The call instruction that should be optimized.
95 const TargetData& TD ///< Information about the target
Reid Spencer8ee5aac2005-04-26 03:26:15 +000096 ) = 0;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +000097
Reid Spencerf2534c72005-04-25 21:11:48 +000098 const char * getFunctionName() const { return func_name; }
Reid Spencere95a6472005-04-27 00:05:45 +000099
100#ifndef NDEBUG
101 void activate() { ++activations; }
102#endif
103
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000104 private:
Reid Spencerf2534c72005-04-25 21:11:48 +0000105 const char* func_name;
Reid Spencere95a6472005-04-27 00:05:45 +0000106#ifndef NDEBUG
107 Statistic<> activations;
108#endif
Reid Spencer39a762d2005-04-25 02:53:12 +0000109 };
110
111 /// @brief The list of optimizations deriving from CallOptimizer
Reid Spencerf2534c72005-04-25 21:11:48 +0000112
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000113 hash_map<std::string,CallOptimizer*> optlist;
Reid Spencer39a762d2005-04-25 02:53:12 +0000114
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000115 CallOptimizer::CallOptimizer(const char* fname)
116 : func_name(fname)
Reid Spencere95a6472005-04-27 00:05:45 +0000117#ifndef NDEBUG
118 , activations(fname,"Number of calls simplified")
119#endif
Reid Spencer39a762d2005-04-25 02:53:12 +0000120 {
121 // Register this call optimizer
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000122 optlist[func_name] = this;
Reid Spencer39a762d2005-04-25 02:53:12 +0000123 }
124
125 /// Make sure we get our virtual table in this file.
Reid Spencerfe91dfe2005-04-25 21:20:38 +0000126 CallOptimizer::~CallOptimizer() { }
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000127
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000128}
129
130ModulePass *llvm::createSimplifyLibCallsPass()
131{
132 return new SimplifyLibCalls();
133}
134
135void SimplifyLibCalls::getAnalysisUsage(AnalysisUsage& Info) const
136{
137 // Ask that the TargetData analysis be performed before us so we can use
138 // the target data.
139 Info.addRequired<TargetData>();
140}
141
142bool SimplifyLibCalls::runOnModule(Module &M)
143{
144 TargetData& TD = getAnalysis<TargetData>();
145
146 bool result = false;
147
148 // The call optimizations can be recursive. That is, the optimization might
149 // generate a call to another function which can also be optimized. This way
150 // we make the CallOptimizer instances very specific to the case they handle.
151 // It also means we need to keep running over the function calls in the module
152 // until we don't get any more optimizations possible.
153 bool found_optimization = false;
154 do
155 {
156 found_optimization = false;
157 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
158 {
159 // All the "well-known" functions are external and have external linkage
160 // because they live in a runtime library somewhere and were (probably)
161 // not compiled by LLVM. So, we only act on external functions that have
162 // external linkage and non-empty uses.
Reid Spencere95a6472005-04-27 00:05:45 +0000163 if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
164 continue;
165
166 // Get the optimization class that pertains to this function
167 CallOptimizer* CO = optlist[FI->getName().c_str()];
168 if (!CO)
169 continue;
170
171 // Make sure the called function is suitable for the optimization
172 if (!CO->ValidateCalledFunction(FI,TD))
173 continue;
174
175 // Loop over each of the uses of the function
176 for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
177 UI != UE ; )
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000178 {
Reid Spencere95a6472005-04-27 00:05:45 +0000179 // If the use of the function is a call instruction
180 if (CallInst* CI = dyn_cast<CallInst>(*UI++))
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000181 {
Reid Spencere95a6472005-04-27 00:05:45 +0000182 // Do the optimization on the CallOptimizer.
183 if (CO->OptimizeCall(CI,TD))
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000184 {
Reid Spencere95a6472005-04-27 00:05:45 +0000185 ++SimplifiedLibCalls;
186 found_optimization = result = true;
187#ifndef NDEBUG
188 CO->activate();
189#endif
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000190 }
191 }
192 }
193 }
194 } while (found_optimization);
195 return result;
196}
197
198namespace {
199
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000200 /// Provide some functions for accessing standard library prototypes and
201 /// caching them so we don't have to keep recomputing them
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000202 FunctionType* get_strlen(const Type* IntPtrTy)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000203 {
204 static FunctionType* strlen_type = 0;
205 if (!strlen_type)
206 {
207 std::vector<const Type*> args;
208 args.push_back(PointerType::get(Type::SByteTy));
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000209 strlen_type = FunctionType::get(IntPtrTy, args, false);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000210 }
211 return strlen_type;
212 }
213
214 FunctionType* get_memcpy()
215 {
216 static FunctionType* memcpy_type = 0;
217 if (!memcpy_type)
218 {
219 // Note: this is for llvm.memcpy intrinsic
220 std::vector<const Type*> args;
221 args.push_back(PointerType::get(Type::SByteTy));
222 args.push_back(PointerType::get(Type::SByteTy));
223 args.push_back(Type::IntTy);
224 args.push_back(Type::IntTy);
Reid Spenceraaca1702005-04-26 22:46:23 +0000225 memcpy_type = FunctionType::get(Type::VoidTy, args, false);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000226 }
227 return memcpy_type;
228 }
Reid Spencer76dab9a2005-04-26 05:24:00 +0000229
Reid Spencerb4f7b832005-04-26 07:45:18 +0000230 /// A function to compute the length of a null-terminated string of integers.
231 /// This function can't rely on the size of the constant array because there
232 /// could be a null terminator in the middle of the array. We also have to
233 /// bail out if we find a non-integer constant initializer of one of the
234 /// elements or if there is no null-terminator. The logic below checks
235 bool getConstantStringLength(Value* V, uint64_t& len )
Reid Spencer76dab9a2005-04-26 05:24:00 +0000236 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000237 assert(V != 0 && "Invalid args to getConstantStringLength");
Reid Spencerb4f7b832005-04-26 07:45:18 +0000238 len = 0; // make sure we initialize this
Reid Spencer76dab9a2005-04-26 05:24:00 +0000239 User* GEP = 0;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000240 // If the value is not a GEP instruction nor a constant expression with a
241 // GEP instruction, then return false because ConstantArray can't occur
242 // any other way
Reid Spencer76dab9a2005-04-26 05:24:00 +0000243 if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V))
244 GEP = GEPI;
245 else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V))
246 if (CE->getOpcode() == Instruction::GetElementPtr)
247 GEP = CE;
248 else
Reid Spencerb4f7b832005-04-26 07:45:18 +0000249 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000250 else
Reid Spencerb4f7b832005-04-26 07:45:18 +0000251 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000252
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000253 // Make sure the GEP has exactly three arguments.
254 if (GEP->getNumOperands() != 3)
255 return false;
256
Reid Spencer76dab9a2005-04-26 05:24:00 +0000257 // Check to make sure that the first operand of the GEP is an integer and
258 // has value 0 so that we are sure we're indexing into the initializer.
259 if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1)))
Reid Spencerb4f7b832005-04-26 07:45:18 +0000260 {
261 if (!op1->isNullValue())
Reid Spencer76dab9a2005-04-26 05:24:00 +0000262 return false;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000263 }
Reid Spencer76dab9a2005-04-26 05:24:00 +0000264 else
265 return false;
266
267 // Ensure that the second operand is a ConstantInt. If it isn't then this
268 // GEP is wonky and we're not really sure what were referencing into and
Reid Spencerb4f7b832005-04-26 07:45:18 +0000269 // better of not optimizing it. While we're at it, get the second index
270 // value. We'll need this later for indexing the ConstantArray.
271 uint64_t start_idx = 0;
272 if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
273 start_idx = CI->getRawValue();
274 else
275 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000276
277 // The GEP instruction, constant or instruction, must reference a global
278 // variable that is a constant and is initialized. The referenced constant
279 // initializer is the array that we'll use for optimization.
280 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
281 if (!GV || !GV->isConstant() || !GV->hasInitializer())
Reid Spencerb4f7b832005-04-26 07:45:18 +0000282 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000283
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000284 // Get the initializer.
Reid Spencerb4f7b832005-04-26 07:45:18 +0000285 Constant* INTLZR = GV->getInitializer();
Reid Spencer76dab9a2005-04-26 05:24:00 +0000286
Reid Spencerb4f7b832005-04-26 07:45:18 +0000287 // Handle the ConstantAggregateZero case
288 if (ConstantAggregateZero* CAZ = dyn_cast<ConstantAggregateZero>(INTLZR))
289 {
290 // This is a degenerate case. The initializer is constant zero so the
291 // length of the string must be zero.
292 len = 0;
293 return true;
294 }
295
296 // Must be a Constant Array
297 ConstantArray* A = dyn_cast<ConstantArray>(INTLZR);
298 if (!A)
299 return false;
300
301 // Get the number of elements in the array
302 uint64_t max_elems = A->getType()->getNumElements();
303
304 // Traverse the constant array from start_idx (derived above) which is
305 // the place the GEP refers to in the array.
306 for ( len = start_idx; len < max_elems; len++)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000307 {
308 if (ConstantInt* CI = dyn_cast<ConstantInt>(A->getOperand(len)))
309 {
310 // Check for the null terminator
311 if (CI->isNullValue())
312 break; // we found end of string
313 }
314 else
315 return false; // This array isn't suitable, non-int initializer
316 }
317 if (len >= max_elems)
318 return false; // This array isn't null terminated
Reid Spencerb4f7b832005-04-26 07:45:18 +0000319
320 // Subtract out the initial value from the length
321 len -= start_idx;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000322 return true; // success!
323 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000324
325/// This CallOptimizer will find instances of a call to "exit" that occurs
326/// within the "main" function and change it to a simple "ret" instruction with
327/// the same value as passed to the exit function. It assumes that the
328/// instructions after the call to exit(3) can be deleted since they are
329/// unreachable anyway.
330/// @brief Replace calls to exit in main with a simple return
331struct ExitInMainOptimization : public CallOptimizer
332{
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000333 ExitInMainOptimization() : CallOptimizer("exit") {}
334 virtual ~ExitInMainOptimization() {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000335
336 // Make sure the called function looks like exit (int argument, int return
337 // type, external linkage, not varargs).
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000338 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000339 {
Reid Spencerb4f7b832005-04-26 07:45:18 +0000340 if (f->arg_size() >= 1)
341 if (f->arg_begin()->getType()->isInteger())
342 return true;
Reid Spencerf2534c72005-04-25 21:11:48 +0000343 return false;
344 }
345
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000346 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000347 {
Reid Spencerf2534c72005-04-25 21:11:48 +0000348 // To be careful, we check that the call to exit is coming from "main", that
349 // main has external linkage, and the return type of main and the argument
350 // to exit have the same type.
351 Function *from = ci->getParent()->getParent();
352 if (from->hasExternalLinkage())
353 if (from->getReturnType() == ci->getOperand(1)->getType())
354 if (from->getName() == "main")
355 {
356 // Okay, time to actually do the optimization. First, get the basic
357 // block of the call instruction
358 BasicBlock* bb = ci->getParent();
Reid Spencer39a762d2005-04-25 02:53:12 +0000359
Reid Spencerf2534c72005-04-25 21:11:48 +0000360 // Create a return instruction that we'll replace the call with.
361 // Note that the argument of the return is the argument of the call
362 // instruction.
363 ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000364
Reid Spencerf2534c72005-04-25 21:11:48 +0000365 // Split the block at the call instruction which places it in a new
366 // basic block.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000367 bb->splitBasicBlock(ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000368
Reid Spencerf2534c72005-04-25 21:11:48 +0000369 // The block split caused a branch instruction to be inserted into
370 // the end of the original block, right after the return instruction
371 // that we put there. That's not a valid block, so delete the branch
372 // instruction.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000373 bb->getInstList().pop_back();
Reid Spencer39a762d2005-04-25 02:53:12 +0000374
Reid Spencerf2534c72005-04-25 21:11:48 +0000375 // Now we can finally get rid of the call instruction which now lives
376 // in the new basic block.
377 ci->eraseFromParent();
378
379 // Optimization succeeded, return true.
380 return true;
381 }
382 // We didn't pass the criteria for this optimization so return false
383 return false;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000384 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000385} ExitInMainOptimizer;
386
Reid Spencerf2534c72005-04-25 21:11:48 +0000387/// This CallOptimizer will simplify a call to the strcat library function. The
388/// simplification is possible only if the string being concatenated is a
389/// constant array or a constant expression that results in a constant array. In
390/// this case, if the array is small, we can generate a series of inline store
391/// instructions to effect the concatenation without calling strcat.
392/// @brief Simplify the strcat library function.
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000393struct StrCatOptimization : public CallOptimizer
394{
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000395private:
396 Function* strlen_func;
397 Function* memcpy_func;
398public:
399 StrCatOptimization()
400 : CallOptimizer("strcat")
401 , strlen_func(0)
402 , memcpy_func(0)
403 {}
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000404 virtual ~StrCatOptimization() {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000405
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000406 inline Function* get_strlen_func(Module*M,const Type* IntPtrTy)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000407 {
408 if (strlen_func)
409 return strlen_func;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000410 return strlen_func = M->getOrInsertFunction("strlen",get_strlen(IntPtrTy));
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000411 }
412
413 inline Function* get_memcpy_func(Module* M)
414 {
415 if (memcpy_func)
416 return memcpy_func;
417 return memcpy_func = M->getOrInsertFunction("llvm.memcpy",get_memcpy());
418 }
419
Reid Spencerf2534c72005-04-25 21:11:48 +0000420 /// @brief Make sure that the "strcat" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000421 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000422 {
423 if (f->getReturnType() == PointerType::get(Type::SByteTy))
424 if (f->arg_size() == 2)
425 {
426 Function::const_arg_iterator AI = f->arg_begin();
427 if (AI++->getType() == PointerType::get(Type::SByteTy))
428 if (AI->getType() == PointerType::get(Type::SByteTy))
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000429 {
430 // Invalidate the pre-computed strlen_func and memcpy_func Functions
431 // because, by definition, this method is only called when a new
432 // Module is being traversed. Invalidation causes re-computation for
433 // the new Module (if necessary).
434 strlen_func = 0;
435 memcpy_func = 0;
436
437 // Indicate this is a suitable call type.
Reid Spencerf2534c72005-04-25 21:11:48 +0000438 return true;
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000439 }
Reid Spencerf2534c72005-04-25 21:11:48 +0000440 }
441 return false;
442 }
443
444 /// Perform the optimization if the length of the string concatenated
445 /// is reasonably short and it is a constant array.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000446 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000447 {
Reid Spencer76dab9a2005-04-26 05:24:00 +0000448 // Extract the initializer (while making numerous checks) from the
449 // source operand of the call to strcat. If we get null back, one of
450 // a variety of checks in get_GVInitializer failed
Reid Spencerb4f7b832005-04-26 07:45:18 +0000451 uint64_t len = 0;
452 if (!getConstantStringLength(ci->getOperand(2),len))
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000453 return false;
454
Reid Spencerb4f7b832005-04-26 07:45:18 +0000455 // Handle the simple, do-nothing case
456 if (len == 0)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000457 {
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000458 ci->replaceAllUsesWith(ci->getOperand(1));
459 ci->eraseFromParent();
460 return true;
461 }
462
Reid Spencerb4f7b832005-04-26 07:45:18 +0000463 // Increment the length because we actually want to memcpy the null
464 // terminator as well.
465 len++;
Reid Spencerf2534c72005-04-25 21:11:48 +0000466
Reid Spencerb4f7b832005-04-26 07:45:18 +0000467 // Extract some information from the instruction
468 Module* M = ci->getParent()->getParent()->getParent();
469
470 // We need to find the end of the destination string. That's where the
471 // memory is to be moved to. We just generate a call to strlen (further
472 // optimized in another pass). Note that the get_strlen_func() call
473 // caches the Function* for us.
474 CallInst* strlen_inst =
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000475 new CallInst(get_strlen_func(M,TD.getIntPtrType()),
476 ci->getOperand(1),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000477
478 // Now that we have the destination's length, we must index into the
479 // destination's pointer to get the actual memcpy destination (end of
480 // the string .. we're concatenating).
481 std::vector<Value*> idx;
482 idx.push_back(strlen_inst);
483 GetElementPtrInst* gep =
484 new GetElementPtrInst(ci->getOperand(1),idx,"",ci);
485
486 // We have enough information to now generate the memcpy call to
487 // do the concatenation for us.
488 std::vector<Value*> vals;
489 vals.push_back(gep); // destination
490 vals.push_back(ci->getOperand(2)); // source
491 vals.push_back(ConstantSInt::get(Type::IntTy,len)); // length
492 vals.push_back(ConstantSInt::get(Type::IntTy,1)); // alignment
493 CallInst* memcpy_inst = new CallInst(get_memcpy_func(M), vals, "", ci);
494
495 // Finally, substitute the first operand of the strcat call for the
496 // strcat call itself since strcat returns its first operand; and,
497 // kill the strcat CallInst.
498 ci->replaceAllUsesWith(ci->getOperand(1));
499 ci->eraseFromParent();
500 return true;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000501 }
502} StrCatOptimizer;
503
Reid Spencer76dab9a2005-04-26 05:24:00 +0000504/// This CallOptimizer will simplify a call to the strlen library function by
505/// replacing it with a constant value if the string provided to it is a
506/// constant array.
507/// @brief Simplify the strlen library function.
508struct StrLenOptimization : public CallOptimizer
509{
510 StrLenOptimization() : CallOptimizer("strlen") {}
511 virtual ~StrLenOptimization() {}
512
513 /// @brief Make sure that the "strlen" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000514 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000515 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000516 if (f->getReturnType() == TD.getIntPtrType())
Reid Spencer76dab9a2005-04-26 05:24:00 +0000517 if (f->arg_size() == 1)
518 if (Function::const_arg_iterator AI = f->arg_begin())
519 if (AI->getType() == PointerType::get(Type::SByteTy))
520 return true;
521 return false;
522 }
523
524 /// @brief Perform the strlen optimization
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000525 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000526 {
Reid Spencerb4f7b832005-04-26 07:45:18 +0000527 // Get the length of the string
528 uint64_t len = 0;
529 if (!getConstantStringLength(ci->getOperand(1),len))
Reid Spencer76dab9a2005-04-26 05:24:00 +0000530 return false;
531
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000532 ci->replaceAllUsesWith(ConstantInt::get(TD.getIntPtrType(),len));
Reid Spencerb4f7b832005-04-26 07:45:18 +0000533 ci->eraseFromParent();
534 return true;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000535 }
536} StrLenOptimizer;
537
Reid Spencerf2534c72005-04-25 21:11:48 +0000538/// This CallOptimizer will simplify a call to the memcpy library function by
539/// expanding it out to a small set of stores if the copy source is a constant
540/// array.
541/// @brief Simplify the memcpy library function.
542struct MemCpyOptimization : public CallOptimizer
543{
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000544 MemCpyOptimization() : CallOptimizer("llvm.memcpy") {}
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000545protected:
546 MemCpyOptimization(const char* fname) : CallOptimizer(fname) {}
547public:
Reid Spencerf2534c72005-04-25 21:11:48 +0000548 virtual ~MemCpyOptimization() {}
549
550 /// @brief Make sure that the "memcpy" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000551 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000552 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000553 // Just make sure this has 4 arguments per LLVM spec.
Reid Spencer2bc7a4f2005-04-26 23:02:16 +0000554 return (f->arg_size() == 4);
Reid Spencerf2534c72005-04-25 21:11:48 +0000555 }
556
Reid Spencerb4f7b832005-04-26 07:45:18 +0000557 /// Because of alignment and instruction information that we don't have, we
558 /// leave the bulk of this to the code generators. The optimization here just
559 /// deals with a few degenerate cases where the length of the string and the
560 /// alignment match the sizes of our intrinsic types so we can do a load and
561 /// store instead of the memcpy call.
562 /// @brief Perform the memcpy optimization.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000563 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000564 {
Reid Spencer4855ebf2005-04-26 19:55:57 +0000565 // Make sure we have constant int values to work with
566 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
567 if (!LEN)
568 return false;
569 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
570 if (!ALIGN)
571 return false;
572
573 // If the length is larger than the alignment, we can't optimize
574 uint64_t len = LEN->getRawValue();
575 uint64_t alignment = ALIGN->getRawValue();
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000576 if (len > alignment)
Reid Spencerb4f7b832005-04-26 07:45:18 +0000577 return false;
578
579 Value* dest = ci->getOperand(1);
580 Value* src = ci->getOperand(2);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000581 CastInst* SrcCast = 0;
582 CastInst* DestCast = 0;
583 switch (len)
584 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000585 case 0:
Reid Spenceraaca1702005-04-26 22:46:23 +0000586 // The memcpy is a no-op so just dump its call.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000587 ci->eraseFromParent();
588 return true;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000589 case 1:
590 SrcCast = new CastInst(src,PointerType::get(Type::SByteTy),"",ci);
591 DestCast = new CastInst(dest,PointerType::get(Type::SByteTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000592 break;
593 case 2:
594 SrcCast = new CastInst(src,PointerType::get(Type::ShortTy),"",ci);
595 DestCast = new CastInst(dest,PointerType::get(Type::ShortTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000596 break;
597 case 4:
598 SrcCast = new CastInst(src,PointerType::get(Type::IntTy),"",ci);
599 DestCast = new CastInst(dest,PointerType::get(Type::IntTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000600 break;
601 case 8:
602 SrcCast = new CastInst(src,PointerType::get(Type::LongTy),"",ci);
603 DestCast = new CastInst(dest,PointerType::get(Type::LongTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000604 break;
605 default:
606 return false;
607 }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000608 LoadInst* LI = new LoadInst(SrcCast,"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000609 StoreInst* SI = new StoreInst(LI, DestCast, ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000610 ci->eraseFromParent();
611 return true;
Reid Spencerf2534c72005-04-25 21:11:48 +0000612 }
613} MemCpyOptimizer;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000614
615/// This CallOptimizer will simplify a call to the memmove library function. It
616/// is identical to MemCopyOptimization except for the name of the intrinsic.
617/// @brief Simplify the memmove library function.
618struct MemMoveOptimization : public MemCpyOptimization
619{
620 MemMoveOptimization() : MemCpyOptimization("llvm.memmove") {}
621
622} MemMoveOptimizer;
623
Reid Spencer39a762d2005-04-25 02:53:12 +0000624}