blob: 20d83b87c3a2295e1a2c9bd1528d26d8f8290498 [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
Reid Spencerdc11db62005-04-27 00:20:23 +0000107 std::string stat_name;
Reid Spencere95a6472005-04-27 00:05:45 +0000108 Statistic<> activations;
109#endif
Reid Spencer39a762d2005-04-25 02:53:12 +0000110 };
111
112 /// @brief The list of optimizations deriving from CallOptimizer
Reid Spencerf2534c72005-04-25 21:11:48 +0000113
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000114 hash_map<std::string,CallOptimizer*> optlist;
Reid Spencer39a762d2005-04-25 02:53:12 +0000115
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000116 CallOptimizer::CallOptimizer(const char* fname)
117 : func_name(fname)
Reid Spencere95a6472005-04-27 00:05:45 +0000118#ifndef NDEBUG
Reid Spencerdc11db62005-04-27 00:20:23 +0000119 , stat_name(std::string("simplify-libcalls:")+fname)
120 , activations(stat_name.c_str(),"Number of calls simplified")
Reid Spencere95a6472005-04-27 00:05:45 +0000121#endif
Reid Spencer39a762d2005-04-25 02:53:12 +0000122 {
123 // Register this call optimizer
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000124 optlist[func_name] = this;
Reid Spencer39a762d2005-04-25 02:53:12 +0000125 }
126
127 /// Make sure we get our virtual table in this file.
Reid Spencerfe91dfe2005-04-25 21:20:38 +0000128 CallOptimizer::~CallOptimizer() { }
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000129
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000130}
131
132ModulePass *llvm::createSimplifyLibCallsPass()
133{
134 return new SimplifyLibCalls();
135}
136
137void SimplifyLibCalls::getAnalysisUsage(AnalysisUsage& Info) const
138{
139 // Ask that the TargetData analysis be performed before us so we can use
140 // the target data.
141 Info.addRequired<TargetData>();
142}
143
144bool SimplifyLibCalls::runOnModule(Module &M)
145{
146 TargetData& TD = getAnalysis<TargetData>();
147
148 bool result = false;
149
150 // The call optimizations can be recursive. That is, the optimization might
151 // generate a call to another function which can also be optimized. This way
152 // we make the CallOptimizer instances very specific to the case they handle.
153 // It also means we need to keep running over the function calls in the module
154 // until we don't get any more optimizations possible.
155 bool found_optimization = false;
156 do
157 {
158 found_optimization = false;
159 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
160 {
161 // All the "well-known" functions are external and have external linkage
162 // because they live in a runtime library somewhere and were (probably)
163 // not compiled by LLVM. So, we only act on external functions that have
164 // external linkage and non-empty uses.
Reid Spencere95a6472005-04-27 00:05:45 +0000165 if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
166 continue;
167
168 // Get the optimization class that pertains to this function
169 CallOptimizer* CO = optlist[FI->getName().c_str()];
170 if (!CO)
171 continue;
172
173 // Make sure the called function is suitable for the optimization
174 if (!CO->ValidateCalledFunction(FI,TD))
175 continue;
176
177 // Loop over each of the uses of the function
178 for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
179 UI != UE ; )
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000180 {
Reid Spencere95a6472005-04-27 00:05:45 +0000181 // If the use of the function is a call instruction
182 if (CallInst* CI = dyn_cast<CallInst>(*UI++))
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000183 {
Reid Spencere95a6472005-04-27 00:05:45 +0000184 // Do the optimization on the CallOptimizer.
185 if (CO->OptimizeCall(CI,TD))
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000186 {
Reid Spencere95a6472005-04-27 00:05:45 +0000187 ++SimplifiedLibCalls;
188 found_optimization = result = true;
189#ifndef NDEBUG
190 CO->activate();
191#endif
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000192 }
193 }
194 }
195 }
196 } while (found_optimization);
197 return result;
198}
199
200namespace {
201
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000202 /// Provide some functions for accessing standard library prototypes and
203 /// caching them so we don't have to keep recomputing them
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000204 FunctionType* get_strlen(const Type* IntPtrTy)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000205 {
206 static FunctionType* strlen_type = 0;
207 if (!strlen_type)
208 {
209 std::vector<const Type*> args;
210 args.push_back(PointerType::get(Type::SByteTy));
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000211 strlen_type = FunctionType::get(IntPtrTy, args, false);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000212 }
213 return strlen_type;
214 }
215
216 FunctionType* get_memcpy()
217 {
218 static FunctionType* memcpy_type = 0;
219 if (!memcpy_type)
220 {
221 // Note: this is for llvm.memcpy intrinsic
222 std::vector<const Type*> args;
223 args.push_back(PointerType::get(Type::SByteTy));
224 args.push_back(PointerType::get(Type::SByteTy));
225 args.push_back(Type::IntTy);
226 args.push_back(Type::IntTy);
Reid Spenceraaca1702005-04-26 22:46:23 +0000227 memcpy_type = FunctionType::get(Type::VoidTy, args, false);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000228 }
229 return memcpy_type;
230 }
Reid Spencer76dab9a2005-04-26 05:24:00 +0000231
Reid Spencerb4f7b832005-04-26 07:45:18 +0000232 /// A function to compute the length of a null-terminated string of integers.
233 /// This function can't rely on the size of the constant array because there
234 /// could be a null terminator in the middle of the array. We also have to
235 /// bail out if we find a non-integer constant initializer of one of the
236 /// elements or if there is no null-terminator. The logic below checks
237 bool getConstantStringLength(Value* V, uint64_t& len )
Reid Spencer76dab9a2005-04-26 05:24:00 +0000238 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000239 assert(V != 0 && "Invalid args to getConstantStringLength");
Reid Spencerb4f7b832005-04-26 07:45:18 +0000240 len = 0; // make sure we initialize this
Reid Spencer76dab9a2005-04-26 05:24:00 +0000241 User* GEP = 0;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000242 // If the value is not a GEP instruction nor a constant expression with a
243 // GEP instruction, then return false because ConstantArray can't occur
244 // any other way
Reid Spencer76dab9a2005-04-26 05:24:00 +0000245 if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V))
246 GEP = GEPI;
247 else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V))
248 if (CE->getOpcode() == Instruction::GetElementPtr)
249 GEP = CE;
250 else
Reid Spencerb4f7b832005-04-26 07:45:18 +0000251 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000252 else
Reid Spencerb4f7b832005-04-26 07:45:18 +0000253 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000254
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000255 // Make sure the GEP has exactly three arguments.
256 if (GEP->getNumOperands() != 3)
257 return false;
258
Reid Spencer76dab9a2005-04-26 05:24:00 +0000259 // Check to make sure that the first operand of the GEP is an integer and
260 // has value 0 so that we are sure we're indexing into the initializer.
261 if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1)))
Reid Spencerb4f7b832005-04-26 07:45:18 +0000262 {
263 if (!op1->isNullValue())
Reid Spencer76dab9a2005-04-26 05:24:00 +0000264 return false;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000265 }
Reid Spencer76dab9a2005-04-26 05:24:00 +0000266 else
267 return false;
268
269 // Ensure that the second operand is a ConstantInt. If it isn't then this
270 // GEP is wonky and we're not really sure what were referencing into and
Reid Spencerb4f7b832005-04-26 07:45:18 +0000271 // better of not optimizing it. While we're at it, get the second index
272 // value. We'll need this later for indexing the ConstantArray.
273 uint64_t start_idx = 0;
274 if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
275 start_idx = CI->getRawValue();
276 else
277 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000278
279 // The GEP instruction, constant or instruction, must reference a global
280 // variable that is a constant and is initialized. The referenced constant
281 // initializer is the array that we'll use for optimization.
282 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
283 if (!GV || !GV->isConstant() || !GV->hasInitializer())
Reid Spencerb4f7b832005-04-26 07:45:18 +0000284 return false;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000285
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000286 // Get the initializer.
Reid Spencerb4f7b832005-04-26 07:45:18 +0000287 Constant* INTLZR = GV->getInitializer();
Reid Spencer76dab9a2005-04-26 05:24:00 +0000288
Reid Spencerb4f7b832005-04-26 07:45:18 +0000289 // Handle the ConstantAggregateZero case
290 if (ConstantAggregateZero* CAZ = dyn_cast<ConstantAggregateZero>(INTLZR))
291 {
292 // This is a degenerate case. The initializer is constant zero so the
293 // length of the string must be zero.
294 len = 0;
295 return true;
296 }
297
298 // Must be a Constant Array
299 ConstantArray* A = dyn_cast<ConstantArray>(INTLZR);
300 if (!A)
301 return false;
302
303 // Get the number of elements in the array
304 uint64_t max_elems = A->getType()->getNumElements();
305
306 // Traverse the constant array from start_idx (derived above) which is
307 // the place the GEP refers to in the array.
308 for ( len = start_idx; len < max_elems; len++)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000309 {
310 if (ConstantInt* CI = dyn_cast<ConstantInt>(A->getOperand(len)))
311 {
312 // Check for the null terminator
313 if (CI->isNullValue())
314 break; // we found end of string
315 }
316 else
317 return false; // This array isn't suitable, non-int initializer
318 }
319 if (len >= max_elems)
320 return false; // This array isn't null terminated
Reid Spencerb4f7b832005-04-26 07:45:18 +0000321
322 // Subtract out the initial value from the length
323 len -= start_idx;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000324 return true; // success!
325 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000326
327/// This CallOptimizer will find instances of a call to "exit" that occurs
328/// within the "main" function and change it to a simple "ret" instruction with
329/// the same value as passed to the exit function. It assumes that the
330/// instructions after the call to exit(3) can be deleted since they are
331/// unreachable anyway.
332/// @brief Replace calls to exit in main with a simple return
333struct ExitInMainOptimization : public CallOptimizer
334{
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000335 ExitInMainOptimization() : CallOptimizer("exit") {}
336 virtual ~ExitInMainOptimization() {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000337
338 // Make sure the called function looks like exit (int argument, int return
339 // type, external linkage, not varargs).
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000340 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000341 {
Reid Spencerb4f7b832005-04-26 07:45:18 +0000342 if (f->arg_size() >= 1)
343 if (f->arg_begin()->getType()->isInteger())
344 return true;
Reid Spencerf2534c72005-04-25 21:11:48 +0000345 return false;
346 }
347
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000348 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000349 {
Reid Spencerf2534c72005-04-25 21:11:48 +0000350 // To be careful, we check that the call to exit is coming from "main", that
351 // main has external linkage, and the return type of main and the argument
352 // to exit have the same type.
353 Function *from = ci->getParent()->getParent();
354 if (from->hasExternalLinkage())
355 if (from->getReturnType() == ci->getOperand(1)->getType())
356 if (from->getName() == "main")
357 {
358 // Okay, time to actually do the optimization. First, get the basic
359 // block of the call instruction
360 BasicBlock* bb = ci->getParent();
Reid Spencer39a762d2005-04-25 02:53:12 +0000361
Reid Spencerf2534c72005-04-25 21:11:48 +0000362 // Create a return instruction that we'll replace the call with.
363 // Note that the argument of the return is the argument of the call
364 // instruction.
365 ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000366
Reid Spencerf2534c72005-04-25 21:11:48 +0000367 // Split the block at the call instruction which places it in a new
368 // basic block.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000369 bb->splitBasicBlock(ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000370
Reid Spencerf2534c72005-04-25 21:11:48 +0000371 // The block split caused a branch instruction to be inserted into
372 // the end of the original block, right after the return instruction
373 // that we put there. That's not a valid block, so delete the branch
374 // instruction.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000375 bb->getInstList().pop_back();
Reid Spencer39a762d2005-04-25 02:53:12 +0000376
Reid Spencerf2534c72005-04-25 21:11:48 +0000377 // Now we can finally get rid of the call instruction which now lives
378 // in the new basic block.
379 ci->eraseFromParent();
380
381 // Optimization succeeded, return true.
382 return true;
383 }
384 // We didn't pass the criteria for this optimization so return false
385 return false;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000386 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000387} ExitInMainOptimizer;
388
Reid Spencerf2534c72005-04-25 21:11:48 +0000389/// This CallOptimizer will simplify a call to the strcat library function. The
390/// simplification is possible only if the string being concatenated is a
391/// constant array or a constant expression that results in a constant array. In
392/// this case, if the array is small, we can generate a series of inline store
393/// instructions to effect the concatenation without calling strcat.
394/// @brief Simplify the strcat library function.
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000395struct StrCatOptimization : public CallOptimizer
396{
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000397private:
398 Function* strlen_func;
399 Function* memcpy_func;
400public:
401 StrCatOptimization()
402 : CallOptimizer("strcat")
403 , strlen_func(0)
404 , memcpy_func(0)
405 {}
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000406 virtual ~StrCatOptimization() {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000407
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000408 inline Function* get_strlen_func(Module*M,const Type* IntPtrTy)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000409 {
410 if (strlen_func)
411 return strlen_func;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000412 return strlen_func = M->getOrInsertFunction("strlen",get_strlen(IntPtrTy));
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000413 }
414
415 inline Function* get_memcpy_func(Module* M)
416 {
417 if (memcpy_func)
418 return memcpy_func;
419 return memcpy_func = M->getOrInsertFunction("llvm.memcpy",get_memcpy());
420 }
421
Reid Spencerf2534c72005-04-25 21:11:48 +0000422 /// @brief Make sure that the "strcat" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000423 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000424 {
425 if (f->getReturnType() == PointerType::get(Type::SByteTy))
426 if (f->arg_size() == 2)
427 {
428 Function::const_arg_iterator AI = f->arg_begin();
429 if (AI++->getType() == PointerType::get(Type::SByteTy))
430 if (AI->getType() == PointerType::get(Type::SByteTy))
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000431 {
432 // Invalidate the pre-computed strlen_func and memcpy_func Functions
433 // because, by definition, this method is only called when a new
434 // Module is being traversed. Invalidation causes re-computation for
435 // the new Module (if necessary).
436 strlen_func = 0;
437 memcpy_func = 0;
438
439 // Indicate this is a suitable call type.
Reid Spencerf2534c72005-04-25 21:11:48 +0000440 return true;
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000441 }
Reid Spencerf2534c72005-04-25 21:11:48 +0000442 }
443 return false;
444 }
445
446 /// Perform the optimization if the length of the string concatenated
447 /// is reasonably short and it is a constant array.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000448 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000449 {
Reid Spencer76dab9a2005-04-26 05:24:00 +0000450 // Extract the initializer (while making numerous checks) from the
451 // source operand of the call to strcat. If we get null back, one of
452 // a variety of checks in get_GVInitializer failed
Reid Spencerb4f7b832005-04-26 07:45:18 +0000453 uint64_t len = 0;
454 if (!getConstantStringLength(ci->getOperand(2),len))
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000455 return false;
456
Reid Spencerb4f7b832005-04-26 07:45:18 +0000457 // Handle the simple, do-nothing case
458 if (len == 0)
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000459 {
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000460 ci->replaceAllUsesWith(ci->getOperand(1));
461 ci->eraseFromParent();
462 return true;
463 }
464
Reid Spencerb4f7b832005-04-26 07:45:18 +0000465 // Increment the length because we actually want to memcpy the null
466 // terminator as well.
467 len++;
Reid Spencerf2534c72005-04-25 21:11:48 +0000468
Reid Spencerb4f7b832005-04-26 07:45:18 +0000469 // Extract some information from the instruction
470 Module* M = ci->getParent()->getParent()->getParent();
471
472 // We need to find the end of the destination string. That's where the
473 // memory is to be moved to. We just generate a call to strlen (further
474 // optimized in another pass). Note that the get_strlen_func() call
475 // caches the Function* for us.
476 CallInst* strlen_inst =
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000477 new CallInst(get_strlen_func(M,TD.getIntPtrType()),
478 ci->getOperand(1),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000479
480 // Now that we have the destination's length, we must index into the
481 // destination's pointer to get the actual memcpy destination (end of
482 // the string .. we're concatenating).
483 std::vector<Value*> idx;
484 idx.push_back(strlen_inst);
485 GetElementPtrInst* gep =
486 new GetElementPtrInst(ci->getOperand(1),idx,"",ci);
487
488 // We have enough information to now generate the memcpy call to
489 // do the concatenation for us.
490 std::vector<Value*> vals;
491 vals.push_back(gep); // destination
492 vals.push_back(ci->getOperand(2)); // source
493 vals.push_back(ConstantSInt::get(Type::IntTy,len)); // length
494 vals.push_back(ConstantSInt::get(Type::IntTy,1)); // alignment
495 CallInst* memcpy_inst = new CallInst(get_memcpy_func(M), vals, "", ci);
496
497 // Finally, substitute the first operand of the strcat call for the
498 // strcat call itself since strcat returns its first operand; and,
499 // kill the strcat CallInst.
500 ci->replaceAllUsesWith(ci->getOperand(1));
501 ci->eraseFromParent();
502 return true;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000503 }
504} StrCatOptimizer;
505
Reid Spencer76dab9a2005-04-26 05:24:00 +0000506/// This CallOptimizer will simplify a call to the strlen library function by
507/// replacing it with a constant value if the string provided to it is a
508/// constant array.
509/// @brief Simplify the strlen library function.
510struct StrLenOptimization : public CallOptimizer
511{
512 StrLenOptimization() : CallOptimizer("strlen") {}
513 virtual ~StrLenOptimization() {}
514
515 /// @brief Make sure that the "strlen" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000516 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000517 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000518 if (f->getReturnType() == TD.getIntPtrType())
Reid Spencer76dab9a2005-04-26 05:24:00 +0000519 if (f->arg_size() == 1)
520 if (Function::const_arg_iterator AI = f->arg_begin())
521 if (AI->getType() == PointerType::get(Type::SByteTy))
522 return true;
523 return false;
524 }
525
526 /// @brief Perform the strlen optimization
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000527 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencer76dab9a2005-04-26 05:24:00 +0000528 {
Reid Spencerb4f7b832005-04-26 07:45:18 +0000529 // Get the length of the string
530 uint64_t len = 0;
531 if (!getConstantStringLength(ci->getOperand(1),len))
Reid Spencer76dab9a2005-04-26 05:24:00 +0000532 return false;
533
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000534 ci->replaceAllUsesWith(ConstantInt::get(TD.getIntPtrType(),len));
Reid Spencerb4f7b832005-04-26 07:45:18 +0000535 ci->eraseFromParent();
536 return true;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000537 }
538} StrLenOptimizer;
539
Reid Spencerf2534c72005-04-25 21:11:48 +0000540/// This CallOptimizer will simplify a call to the memcpy library function by
541/// expanding it out to a small set of stores if the copy source is a constant
542/// array.
543/// @brief Simplify the memcpy library function.
544struct MemCpyOptimization : public CallOptimizer
545{
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000546 MemCpyOptimization() : CallOptimizer("llvm.memcpy") {}
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000547protected:
548 MemCpyOptimization(const char* fname) : CallOptimizer(fname) {}
549public:
Reid Spencerf2534c72005-04-25 21:11:48 +0000550 virtual ~MemCpyOptimization() {}
551
552 /// @brief Make sure that the "memcpy" function has the right prototype
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000553 virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000554 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000555 // Just make sure this has 4 arguments per LLVM spec.
Reid Spencer2bc7a4f2005-04-26 23:02:16 +0000556 return (f->arg_size() == 4);
Reid Spencerf2534c72005-04-25 21:11:48 +0000557 }
558
Reid Spencerb4f7b832005-04-26 07:45:18 +0000559 /// Because of alignment and instruction information that we don't have, we
560 /// leave the bulk of this to the code generators. The optimization here just
561 /// deals with a few degenerate cases where the length of the string and the
562 /// alignment match the sizes of our intrinsic types so we can do a load and
563 /// store instead of the memcpy call.
564 /// @brief Perform the memcpy optimization.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000565 virtual bool OptimizeCall(CallInst* ci, const TargetData& TD)
Reid Spencerf2534c72005-04-25 21:11:48 +0000566 {
Reid Spencer4855ebf2005-04-26 19:55:57 +0000567 // Make sure we have constant int values to work with
568 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
569 if (!LEN)
570 return false;
571 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
572 if (!ALIGN)
573 return false;
574
575 // If the length is larger than the alignment, we can't optimize
576 uint64_t len = LEN->getRawValue();
577 uint64_t alignment = ALIGN->getRawValue();
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000578 if (len > alignment)
Reid Spencerb4f7b832005-04-26 07:45:18 +0000579 return false;
580
581 Value* dest = ci->getOperand(1);
582 Value* src = ci->getOperand(2);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000583 CastInst* SrcCast = 0;
584 CastInst* DestCast = 0;
585 switch (len)
586 {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000587 case 0:
Reid Spenceraaca1702005-04-26 22:46:23 +0000588 // The memcpy is a no-op so just dump its call.
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000589 ci->eraseFromParent();
590 return true;
Reid Spencerb4f7b832005-04-26 07:45:18 +0000591 case 1:
592 SrcCast = new CastInst(src,PointerType::get(Type::SByteTy),"",ci);
593 DestCast = new CastInst(dest,PointerType::get(Type::SByteTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000594 break;
595 case 2:
596 SrcCast = new CastInst(src,PointerType::get(Type::ShortTy),"",ci);
597 DestCast = new CastInst(dest,PointerType::get(Type::ShortTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000598 break;
599 case 4:
600 SrcCast = new CastInst(src,PointerType::get(Type::IntTy),"",ci);
601 DestCast = new CastInst(dest,PointerType::get(Type::IntTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000602 break;
603 case 8:
604 SrcCast = new CastInst(src,PointerType::get(Type::LongTy),"",ci);
605 DestCast = new CastInst(dest,PointerType::get(Type::LongTy),"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000606 break;
607 default:
608 return false;
609 }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000610 LoadInst* LI = new LoadInst(SrcCast,"",ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000611 StoreInst* SI = new StoreInst(LI, DestCast, ci);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000612 ci->eraseFromParent();
613 return true;
Reid Spencerf2534c72005-04-25 21:11:48 +0000614 }
615} MemCpyOptimizer;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000616
617/// This CallOptimizer will simplify a call to the memmove library function. It
618/// is identical to MemCopyOptimization except for the name of the intrinsic.
619/// @brief Simplify the memmove library function.
620struct MemMoveOptimization : public MemCpyOptimization
621{
622 MemMoveOptimization() : MemCpyOptimization("llvm.memmove") {}
623
624} MemMoveOptimizer;
625
Reid Spencer39a762d2005-04-25 02:53:12 +0000626}