blob: f4be9704b7a8936ebe4bae111cc014c880eface6 [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//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Reid Spencer39a762d2005-04-25 02:53:12 +00007//
8//===----------------------------------------------------------------------===//
9//
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000010// This file implements a module pass that applies a variety of small
11// optimizations for calls to specific well-known function calls (e.g. runtime
12// library functions). For example, a call to the function "exit(3)" that
Reid Spencer0b13cda2005-05-21 00:57:44 +000013// occurs within the main() function can be transformed into a simple "return 3"
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000014// instruction. Any optimization that takes this form (replace call to library
15// function with simpler code that provides the same result) belongs in this
16// file.
Reid Spencer39a762d2005-04-25 02:53:12 +000017//
18//===----------------------------------------------------------------------===//
19
Reid Spencer18b99812005-04-26 23:05:17 +000020#define DEBUG_TYPE "simplify-libcalls"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000021#include "llvm/Constants.h"
22#include "llvm/DerivedTypes.h"
23#include "llvm/Instructions.h"
Reid Spencer39a762d2005-04-25 02:53:12 +000024#include "llvm/Module.h"
25#include "llvm/Pass.h"
Anton Korobeynikov6f74afe2008-02-20 11:27:49 +000026#include "llvm/ADT/StringMap.h"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000027#include "llvm/ADT/Statistic.h"
Reid Spencerade18212006-01-19 08:36:56 +000028#include "llvm/Config/config.h"
Reid Spencer557ab152007-02-05 23:32:05 +000029#include "llvm/Support/Compiler.h"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000030#include "llvm/Support/Debug.h"
Reid Spencerbb92b4f2005-04-26 19:13:17 +000031#include "llvm/Target/TargetData.h"
Reid Spencer2bc7a4f2005-04-26 23:02:16 +000032#include "llvm/Transforms/IPO.h"
Anton Korobeynikov579f0712008-02-20 11:08:44 +000033#include <cstring>
Reid Spencer39a762d2005-04-25 02:53:12 +000034using namespace llvm;
35
Reid Spencere249a822005-04-27 07:54:40 +000036/// This statistic keeps track of the total number of library calls that have
37/// been simplified regardless of which call it is.
Chris Lattner1631bcb2006-12-19 22:09:18 +000038STATISTIC(SimplifiedLibCalls, "Number of library calls simplified");
Reid Spencer39a762d2005-04-25 02:53:12 +000039
Chris Lattner1631bcb2006-12-19 22:09:18 +000040namespace {
41 // Forward declarations
42 class LibCallOptimization;
43 class SimplifyLibCalls;
44
Chris Lattner33081b42006-01-22 23:10:26 +000045/// This list is populated by the constructor for LibCallOptimization class.
Reid Spencer9fbad132005-05-21 01:27:04 +000046/// Therefore all subclasses are registered here at static initialization time
47/// and this list is what the SimplifyLibCalls pass uses to apply the individual
48/// optimizations to the call sites.
Reid Spencer7ddcfb32005-04-27 21:29:20 +000049/// @brief The list of optimizations deriving from LibCallOptimization
Chris Lattner33081b42006-01-22 23:10:26 +000050static LibCallOptimization *OptList = 0;
Reid Spencer39a762d2005-04-25 02:53:12 +000051
Reid Spencere249a822005-04-27 07:54:40 +000052/// This class is the abstract base class for the set of optimizations that
Reid Spencer7ddcfb32005-04-27 21:29:20 +000053/// corresponds to one library call. The SimplifyLibCalls pass will call the
Reid Spencere249a822005-04-27 07:54:40 +000054/// ValidateCalledFunction method to ask the optimization if a given Function
Reid Spencer7ddcfb32005-04-27 21:29:20 +000055/// is the kind that the optimization can handle. If the subclass returns true,
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000056/// then SImplifyLibCalls will also call the OptimizeCall method to perform,
Reid Spencer7ddcfb32005-04-27 21:29:20 +000057/// or attempt to perform, the optimization(s) for the library call. Otherwise,
58/// OptimizeCall won't be called. Subclasses are responsible for providing the
59/// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization
60/// constructor. This is used to efficiently select which call instructions to
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000061/// optimize. The criteria for a "lib call" is "anything with well known
Reid Spencer7ddcfb32005-04-27 21:29:20 +000062/// semantics", typically a library function that is defined by an international
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000063/// standard. Because the semantics are well known, the optimizations can
Reid Spencer7ddcfb32005-04-27 21:29:20 +000064/// generally short-circuit actually calling the function if there's a simpler
65/// way (e.g. strlen(X) can be reduced to a constant if X is a constant global).
Reid Spencere249a822005-04-27 07:54:40 +000066/// @brief Base class for library call optimizations
Reid Spencer557ab152007-02-05 23:32:05 +000067class VISIBILITY_HIDDEN LibCallOptimization {
Chris Lattner33081b42006-01-22 23:10:26 +000068 LibCallOptimization **Prev, *Next;
69 const char *FunctionName; ///< Name of the library call we optimize
70#ifndef NDEBUG
Chris Lattner700b8732006-12-06 17:46:33 +000071 Statistic occurrences; ///< debug statistic (-debug-only=simplify-libcalls)
Chris Lattner33081b42006-01-22 23:10:26 +000072#endif
Jeff Cohen4bc952f2005-04-29 03:05:44 +000073public:
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +000074 /// The \p fname argument must be the name of the library function being
Reid Spencer7ddcfb32005-04-27 21:29:20 +000075 /// optimized by the subclass.
76 /// @brief Constructor that registers the optimization.
Chris Lattner33081b42006-01-22 23:10:26 +000077 LibCallOptimization(const char *FName, const char *Description)
Chris Lattner575d3212006-12-19 23:16:47 +000078 : FunctionName(FName) {
79
Reid Spencere95a6472005-04-27 00:05:45 +000080#ifndef NDEBUG
Chris Lattner575d3212006-12-19 23:16:47 +000081 occurrences.construct("simplify-libcalls", Description);
Reid Spencere95a6472005-04-27 00:05:45 +000082#endif
Chris Lattner33081b42006-01-22 23:10:26 +000083 // Register this optimizer in the list of optimizations.
84 Next = OptList;
85 OptList = this;
86 Prev = &OptList;
87 if (Next) Next->Prev = &Next;
Reid Spencer39a762d2005-04-25 02:53:12 +000088 }
Chris Lattner33081b42006-01-22 23:10:26 +000089
90 /// getNext - All libcall optimizations are chained together into a list,
91 /// return the next one in the list.
92 LibCallOptimization *getNext() { return Next; }
Reid Spencer39a762d2005-04-25 02:53:12 +000093
Reid Spencer7ddcfb32005-04-27 21:29:20 +000094 /// @brief Deregister from the optlist
Chris Lattner33081b42006-01-22 23:10:26 +000095 virtual ~LibCallOptimization() {
96 *Prev = Next;
97 if (Next) Next->Prev = Prev;
98 }
Reid Spencer8ee5aac2005-04-26 03:26:15 +000099
Reid Spencere249a822005-04-27 07:54:40 +0000100 /// The implementation of this function in subclasses should determine if
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000101 /// \p F is suitable for the optimization. This method is called by
102 /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
103 /// sites of such a function if that function is not suitable in the first
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000104 /// place. If the called function is suitabe, this method should return true;
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000105 /// false, otherwise. This function should also perform any lazy
106 /// initialization that the LibCallOptimization needs to do, if its to return
Reid Spencere249a822005-04-27 07:54:40 +0000107 /// true. This avoids doing initialization until the optimizer is actually
108 /// going to be called upon to do some optimization.
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000109 /// @brief Determine if the function is suitable for optimization
Reid Spencere249a822005-04-27 07:54:40 +0000110 virtual bool ValidateCalledFunction(
111 const Function* F, ///< The function that is the target of call sites
112 SimplifyLibCalls& SLC ///< The pass object invoking us
113 ) = 0;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000114
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000115 /// The implementations of this function in subclasses is the heart of the
116 /// SimplifyLibCalls algorithm. Sublcasses of this class implement
Reid Spencere249a822005-04-27 07:54:40 +0000117 /// OptimizeCall to determine if (a) the conditions are right for optimizing
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000118 /// the call and (b) to perform the optimization. If an action is taken
Reid Spencere249a822005-04-27 07:54:40 +0000119 /// against ci, the subclass is responsible for returning true and ensuring
120 /// that ci is erased from its parent.
Reid Spencere249a822005-04-27 07:54:40 +0000121 /// @brief Optimize a call, if possible.
122 virtual bool OptimizeCall(
123 CallInst* ci, ///< The call instruction that should be optimized.
124 SimplifyLibCalls& SLC ///< The pass object invoking us
125 ) = 0;
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000126
Reid Spencere249a822005-04-27 07:54:40 +0000127 /// @brief Get the name of the library call being optimized
Chris Lattner33081b42006-01-22 23:10:26 +0000128 const char *getFunctionName() const { return FunctionName; }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000129
Chris Lattner485b6412007-04-07 00:42:32 +0000130 bool ReplaceCallWith(CallInst *CI, Value *V) {
131 if (!CI->use_empty())
132 CI->replaceAllUsesWith(V);
133 CI->eraseFromParent();
134 return true;
135 }
136
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000137 /// @brief Called by SimplifyLibCalls to update the occurrences statistic.
Chris Lattner33081b42006-01-22 23:10:26 +0000138 void succeeded() {
Reid Spencere249a822005-04-27 07:54:40 +0000139#ifndef NDEBUG
Chris Lattner33081b42006-01-22 23:10:26 +0000140 DEBUG(++occurrences);
Reid Spencere249a822005-04-27 07:54:40 +0000141#endif
Chris Lattner33081b42006-01-22 23:10:26 +0000142 }
Reid Spencere249a822005-04-27 07:54:40 +0000143};
144
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000145/// This class is an LLVM Pass that applies each of the LibCallOptimization
Reid Spencere249a822005-04-27 07:54:40 +0000146/// instances to all the call sites in a module, relatively efficiently. The
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000147/// purpose of this pass is to provide optimizations for calls to well-known
Reid Spencere249a822005-04-27 07:54:40 +0000148/// functions with well-known semantics, such as those in the c library. The
Chris Lattner4201cd12005-08-24 17:22:17 +0000149/// class provides the basic infrastructure for handling runOnModule. Whenever
150/// this pass finds a function call, it asks the appropriate optimizer to
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000151/// validate the call (ValidateLibraryCall). If it is validated, then
152/// the OptimizeCall method is also called.
Reid Spencere249a822005-04-27 07:54:40 +0000153/// @brief A ModulePass for optimizing well-known function calls.
Reid Spencer557ab152007-02-05 23:32:05 +0000154class VISIBILITY_HIDDEN SimplifyLibCalls : public ModulePass {
Jeff Cohen4bc952f2005-04-29 03:05:44 +0000155public:
Nick Lewyckye7da2d62007-05-06 13:37:16 +0000156 static char ID; // Pass identification, replacement for typeid
Devang Patel09f162c2007-05-01 21:15:47 +0000157 SimplifyLibCalls() : ModulePass((intptr_t)&ID) {}
158
Reid Spencere249a822005-04-27 07:54:40 +0000159 /// We need some target data for accurate signature details that are
160 /// target dependent. So we require target data in our AnalysisUsage.
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000161 /// @brief Require TargetData from AnalysisUsage.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000162 virtual void getAnalysisUsage(AnalysisUsage& Info) const {
Reid Spencere249a822005-04-27 07:54:40 +0000163 // Ask that the TargetData analysis be performed before us so we can use
164 // the target data.
165 Info.addRequired<TargetData>();
166 }
167
168 /// For this pass, process all of the function calls in the module, calling
169 /// ValidateLibraryCall and OptimizeCall as appropriate.
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000170 /// @brief Run all the lib call optimizations on a Module.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000171 virtual bool runOnModule(Module &M) {
Reid Spencere249a822005-04-27 07:54:40 +0000172 reset(M);
173
174 bool result = false;
Anton Korobeynikov6f74afe2008-02-20 11:27:49 +0000175 StringMap<LibCallOptimization*> OptznMap;
Chris Lattner33081b42006-01-22 23:10:26 +0000176 for (LibCallOptimization *Optzn = OptList; Optzn; Optzn = Optzn->getNext())
177 OptznMap[Optzn->getFunctionName()] = Optzn;
Reid Spencere249a822005-04-27 07:54:40 +0000178
179 // The call optimizations can be recursive. That is, the optimization might
180 // generate a call to another function which can also be optimized. This way
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000181 // we make the LibCallOptimization instances very specific to the case they
182 // handle. It also means we need to keep running over the function calls in
Reid Spencere249a822005-04-27 07:54:40 +0000183 // the module until we don't get any more optimizations possible.
184 bool found_optimization = false;
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000185 do {
Reid Spencere249a822005-04-27 07:54:40 +0000186 found_optimization = false;
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000187 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
Reid Spencere249a822005-04-27 07:54:40 +0000188 // All the "well-known" functions are external and have external linkage
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000189 // because they live in a runtime library somewhere and were (probably)
190 // not compiled by LLVM. So, we only act on external functions that
Anton Korobeynikovd61d39e2006-09-14 18:23:27 +0000191 // have external or dllimport linkage and non-empty uses.
Reid Spencer5301e7c2007-01-30 20:08:39 +0000192 if (!FI->isDeclaration() ||
Anton Korobeynikovd61d39e2006-09-14 18:23:27 +0000193 !(FI->hasExternalLinkage() || FI->hasDLLImportLinkage()) ||
194 FI->use_empty())
Reid Spencere249a822005-04-27 07:54:40 +0000195 continue;
196
197 // Get the optimization class that pertains to this function
Anton Korobeynikov6f74afe2008-02-20 11:27:49 +0000198 StringMap<LibCallOptimization*>::iterator OMI =
Chris Lattner33081b42006-01-22 23:10:26 +0000199 OptznMap.find(FI->getName());
200 if (OMI == OptznMap.end()) continue;
201
202 LibCallOptimization *CO = OMI->second;
Reid Spencere249a822005-04-27 07:54:40 +0000203
204 // Make sure the called function is suitable for the optimization
Chris Lattner33081b42006-01-22 23:10:26 +0000205 if (!CO->ValidateCalledFunction(FI, *this))
Reid Spencere249a822005-04-27 07:54:40 +0000206 continue;
207
208 // Loop over each of the uses of the function
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000209 for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000210 UI != UE ; ) {
Reid Spencere249a822005-04-27 07:54:40 +0000211 // If the use of the function is a call instruction
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000212 if (CallInst* CI = dyn_cast<CallInst>(*UI++)) {
Reid Spencere249a822005-04-27 07:54:40 +0000213 // Do the optimization on the LibCallOptimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000214 if (CO->OptimizeCall(CI, *this)) {
Reid Spencere249a822005-04-27 07:54:40 +0000215 ++SimplifiedLibCalls;
216 found_optimization = result = true;
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000217 CO->succeeded();
Reid Spencere249a822005-04-27 07:54:40 +0000218 }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000219 }
220 }
221 }
Reid Spencere249a822005-04-27 07:54:40 +0000222 } while (found_optimization);
Chris Lattner33081b42006-01-22 23:10:26 +0000223
Reid Spencere249a822005-04-27 07:54:40 +0000224 return result;
225 }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000226
Reid Spencere249a822005-04-27 07:54:40 +0000227 /// @brief Return the *current* module we're working on.
Reid Spencer93616972005-04-29 09:39:47 +0000228 Module* getModule() const { return M; }
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000229
Reid Spencere249a822005-04-27 07:54:40 +0000230 /// @brief Return the *current* target data for the module we're working on.
Reid Spencer93616972005-04-29 09:39:47 +0000231 TargetData* getTargetData() const { return TD; }
232
233 /// @brief Return the size_t type -- syntactic shortcut
234 const Type* getIntPtrType() const { return TD->getIntPtrType(); }
235
Evan Cheng1fc40252006-06-16 08:36:35 +0000236 /// @brief Return a Function* for the putchar libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000237 Constant *get_putchar() {
Evan Cheng1fc40252006-06-16 08:36:35 +0000238 if (!putchar_func)
Reid Spencerc635f472006-12-31 05:48:39 +0000239 putchar_func =
240 M->getOrInsertFunction("putchar", Type::Int32Ty, Type::Int32Ty, NULL);
Evan Cheng1fc40252006-06-16 08:36:35 +0000241 return putchar_func;
242 }
243
244 /// @brief Return a Function* for the puts libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000245 Constant *get_puts() {
Evan Cheng1fc40252006-06-16 08:36:35 +0000246 if (!puts_func)
Reid Spencerc635f472006-12-31 05:48:39 +0000247 puts_func = M->getOrInsertFunction("puts", Type::Int32Ty,
Christopher Lambedf07882007-12-17 01:12:55 +0000248 PointerType::getUnqual(Type::Int8Ty),
Evan Cheng1fc40252006-06-16 08:36:35 +0000249 NULL);
250 return puts_func;
251 }
252
Reid Spencer93616972005-04-29 09:39:47 +0000253 /// @brief Return a Function* for the fputc libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000254 Constant *get_fputc(const Type* FILEptr_type) {
Reid Spencer93616972005-04-29 09:39:47 +0000255 if (!fputc_func)
Reid Spencerc635f472006-12-31 05:48:39 +0000256 fputc_func = M->getOrInsertFunction("fputc", Type::Int32Ty, Type::Int32Ty,
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000257 FILEptr_type, NULL);
Reid Spencer93616972005-04-29 09:39:47 +0000258 return fputc_func;
259 }
260
Evan Chengf2ea5872006-06-16 04:52:30 +0000261 /// @brief Return a Function* for the fputs libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000262 Constant *get_fputs(const Type* FILEptr_type) {
Evan Chengf2ea5872006-06-16 04:52:30 +0000263 if (!fputs_func)
Reid Spencerc635f472006-12-31 05:48:39 +0000264 fputs_func = M->getOrInsertFunction("fputs", Type::Int32Ty,
Christopher Lambedf07882007-12-17 01:12:55 +0000265 PointerType::getUnqual(Type::Int8Ty),
Evan Chengf2ea5872006-06-16 04:52:30 +0000266 FILEptr_type, NULL);
267 return fputs_func;
268 }
269
Reid Spencer93616972005-04-29 09:39:47 +0000270 /// @brief Return a Function* for the fwrite libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000271 Constant *get_fwrite(const Type* FILEptr_type) {
Reid Spencer93616972005-04-29 09:39:47 +0000272 if (!fwrite_func)
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000273 fwrite_func = M->getOrInsertFunction("fwrite", TD->getIntPtrType(),
Christopher Lambedf07882007-12-17 01:12:55 +0000274 PointerType::getUnqual(Type::Int8Ty),
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000275 TD->getIntPtrType(),
276 TD->getIntPtrType(),
277 FILEptr_type, NULL);
Reid Spencer93616972005-04-29 09:39:47 +0000278 return fwrite_func;
279 }
280
281 /// @brief Return a Function* for the sqrt libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000282 Constant *get_sqrt() {
Reid Spencer93616972005-04-29 09:39:47 +0000283 if (!sqrt_func)
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000284 sqrt_func = M->getOrInsertFunction("sqrt", Type::DoubleTy,
285 Type::DoubleTy, NULL);
Reid Spencer93616972005-04-29 09:39:47 +0000286 return sqrt_func;
287 }
Reid Spencere249a822005-04-27 07:54:40 +0000288
Owen Andersondfd79ad2007-01-20 10:07:23 +0000289 /// @brief Return a Function* for the strcpy libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000290 Constant *get_strcpy() {
Reid Spencer1e520fd2005-05-04 03:20:21 +0000291 if (!strcpy_func)
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000292 strcpy_func = M->getOrInsertFunction("strcpy",
Christopher Lambedf07882007-12-17 01:12:55 +0000293 PointerType::getUnqual(Type::Int8Ty),
294 PointerType::getUnqual(Type::Int8Ty),
295 PointerType::getUnqual(Type::Int8Ty),
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000296 NULL);
Reid Spencer1e520fd2005-05-04 03:20:21 +0000297 return strcpy_func;
298 }
299
300 /// @brief Return a Function* for the strlen libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000301 Constant *get_strlen() {
Reid Spencere249a822005-04-27 07:54:40 +0000302 if (!strlen_func)
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000303 strlen_func = M->getOrInsertFunction("strlen", TD->getIntPtrType(),
Christopher Lambedf07882007-12-17 01:12:55 +0000304 PointerType::getUnqual(Type::Int8Ty),
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000305 NULL);
Reid Spencere249a822005-04-27 07:54:40 +0000306 return strlen_func;
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000307 }
308
Reid Spencer38cabd72005-05-03 07:23:44 +0000309 /// @brief Return a Function* for the memchr libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000310 Constant *get_memchr() {
Reid Spencer38cabd72005-05-03 07:23:44 +0000311 if (!memchr_func)
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000312 memchr_func = M->getOrInsertFunction("memchr",
Christopher Lambedf07882007-12-17 01:12:55 +0000313 PointerType::getUnqual(Type::Int8Ty),
314 PointerType::getUnqual(Type::Int8Ty),
Reid Spencerc635f472006-12-31 05:48:39 +0000315 Type::Int32Ty, TD->getIntPtrType(),
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000316 NULL);
Reid Spencer38cabd72005-05-03 07:23:44 +0000317 return memchr_func;
318 }
319
Reid Spencere249a822005-04-27 07:54:40 +0000320 /// @brief Return a Function* for the memcpy libcall
Chris Lattner34acba42007-01-07 08:12:01 +0000321 Constant *get_memcpy() {
Chris Lattner4201cd12005-08-24 17:22:17 +0000322 if (!memcpy_func) {
Christopher Lambedf07882007-12-17 01:12:55 +0000323 const Type *SBP = PointerType::getUnqual(Type::Int8Ty);
Reid Spencerc635f472006-12-31 05:48:39 +0000324 const char *N = TD->getIntPtrType() == Type::Int32Ty ?
Chris Lattnerea7986a2006-03-03 01:30:23 +0000325 "llvm.memcpy.i32" : "llvm.memcpy.i64";
326 memcpy_func = M->getOrInsertFunction(N, Type::VoidTy, SBP, SBP,
Reid Spencerc635f472006-12-31 05:48:39 +0000327 TD->getIntPtrType(), Type::Int32Ty,
Chris Lattnerea7986a2006-03-03 01:30:23 +0000328 NULL);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000329 }
Reid Spencere249a822005-04-27 07:54:40 +0000330 return memcpy_func;
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000331 }
Reid Spencer76dab9a2005-04-26 05:24:00 +0000332
Chris Lattner34acba42007-01-07 08:12:01 +0000333 Constant *getUnaryFloatFunction(const char *Name, Constant *&Cache) {
Chris Lattner57740402006-01-23 06:24:46 +0000334 if (!Cache)
335 Cache = M->getOrInsertFunction(Name, Type::FloatTy, Type::FloatTy, NULL);
336 return Cache;
Chris Lattner4201cd12005-08-24 17:22:17 +0000337 }
338
Chris Lattner34acba42007-01-07 08:12:01 +0000339 Constant *get_floorf() { return getUnaryFloatFunction("floorf", floorf_func);}
340 Constant *get_ceilf() { return getUnaryFloatFunction( "ceilf", ceilf_func);}
341 Constant *get_roundf() { return getUnaryFloatFunction("roundf", roundf_func);}
342 Constant *get_rintf() { return getUnaryFloatFunction( "rintf", rintf_func);}
343 Constant *get_nearbyintf() { return getUnaryFloatFunction("nearbyintf",
Chris Lattner57740402006-01-23 06:24:46 +0000344 nearbyintf_func); }
Reid Spencere249a822005-04-27 07:54:40 +0000345private:
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000346 /// @brief Reset our cached data for a new Module
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000347 void reset(Module& mod) {
Reid Spencere249a822005-04-27 07:54:40 +0000348 M = &mod;
349 TD = &getAnalysis<TargetData>();
Evan Cheng1fc40252006-06-16 08:36:35 +0000350 putchar_func = 0;
351 puts_func = 0;
Reid Spencer93616972005-04-29 09:39:47 +0000352 fputc_func = 0;
Evan Chengf2ea5872006-06-16 04:52:30 +0000353 fputs_func = 0;
Reid Spencer93616972005-04-29 09:39:47 +0000354 fwrite_func = 0;
Reid Spencere249a822005-04-27 07:54:40 +0000355 memcpy_func = 0;
Reid Spencer38cabd72005-05-03 07:23:44 +0000356 memchr_func = 0;
Reid Spencer93616972005-04-29 09:39:47 +0000357 sqrt_func = 0;
Reid Spencer1e520fd2005-05-04 03:20:21 +0000358 strcpy_func = 0;
Reid Spencere249a822005-04-27 07:54:40 +0000359 strlen_func = 0;
Chris Lattner4201cd12005-08-24 17:22:17 +0000360 floorf_func = 0;
Chris Lattner57740402006-01-23 06:24:46 +0000361 ceilf_func = 0;
362 roundf_func = 0;
363 rintf_func = 0;
364 nearbyintf_func = 0;
Reid Spencer76dab9a2005-04-26 05:24:00 +0000365 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000366
Reid Spencere249a822005-04-27 07:54:40 +0000367private:
Chris Lattner57740402006-01-23 06:24:46 +0000368 /// Caches for function pointers.
Chris Lattner34acba42007-01-07 08:12:01 +0000369 Constant *putchar_func, *puts_func;
370 Constant *fputc_func, *fputs_func, *fwrite_func;
371 Constant *memcpy_func, *memchr_func;
372 Constant *sqrt_func;
373 Constant *strcpy_func, *strlen_func;
374 Constant *floorf_func, *ceilf_func, *roundf_func;
375 Constant *rintf_func, *nearbyintf_func;
Chris Lattner57740402006-01-23 06:24:46 +0000376 Module *M; ///< Cached Module
377 TargetData *TD; ///< Cached TargetData
Reid Spencere249a822005-04-27 07:54:40 +0000378};
379
Devang Patel8c78a0b2007-05-03 01:11:54 +0000380char SimplifyLibCalls::ID = 0;
Reid Spencere249a822005-04-27 07:54:40 +0000381// Register the pass
Chris Lattnerc2d3d312006-08-27 22:42:52 +0000382RegisterPass<SimplifyLibCalls>
383X("simplify-libcalls", "Simplify well-known library calls");
Reid Spencere249a822005-04-27 07:54:40 +0000384
385} // anonymous namespace
386
387// The only public symbol in this file which just instantiates the pass object
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000388ModulePass *llvm::createSimplifyLibCallsPass() {
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000389 return new SimplifyLibCalls();
Reid Spencere249a822005-04-27 07:54:40 +0000390}
391
392// Classes below here, in the anonymous namespace, are all subclasses of the
393// LibCallOptimization class, each implementing all optimizations possible for a
394// single well-known library call. Each has a static singleton instance that
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000395// auto registers it into the "optlist" global above.
Reid Spencere249a822005-04-27 07:54:40 +0000396namespace {
397
Reid Spencera7828ba2005-06-18 17:46:28 +0000398// Forward declare utility functions.
Chris Lattner182a9452007-04-07 21:58:02 +0000399static bool GetConstantStringInfo(Value *V, std::string &Str);
Chris Lattnerbed184c2007-04-07 21:04:50 +0000400static Value *CastToCStr(Value *V, Instruction *IP);
Reid Spencere249a822005-04-27 07:54:40 +0000401
402/// This LibCallOptimization will find instances of a call to "exit" that occurs
Reid Spencer39a762d2005-04-25 02:53:12 +0000403/// within the "main" function and change it to a simple "ret" instruction with
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000404/// the same value passed to the exit function. When this is done, it splits the
405/// basic block at the exit(3) call and deletes the call instruction.
Reid Spencer39a762d2005-04-25 02:53:12 +0000406/// @brief Replace calls to exit in main with a simple return
Reid Spencer557ab152007-02-05 23:32:05 +0000407struct VISIBILITY_HIDDEN ExitInMainOptimization : public LibCallOptimization {
Reid Spencer95d8efd2005-05-03 02:54:54 +0000408 ExitInMainOptimization() : LibCallOptimization("exit",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000409 "Number of 'exit' calls simplified") {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000410
411 // Make sure the called function looks like exit (int argument, int return
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000412 // type, external linkage, not varargs).
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000413 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Chris Lattner03c49532007-01-15 02:27:26 +0000414 return F->arg_size() >= 1 && F->arg_begin()->getType()->isInteger();
Reid Spencerf2534c72005-04-25 21:11:48 +0000415 }
416
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000417 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
Reid Spencerf2534c72005-04-25 21:11:48 +0000418 // To be careful, we check that the call to exit is coming from "main", that
419 // main has external linkage, and the return type of main and the argument
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000420 // to exit have the same type.
Reid Spencerf2534c72005-04-25 21:11:48 +0000421 Function *from = ci->getParent()->getParent();
422 if (from->hasExternalLinkage())
423 if (from->getReturnType() == ci->getOperand(1)->getType())
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000424 if (from->getName() == "main") {
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000425 // Okay, time to actually do the optimization. First, get the basic
Reid Spencerf2534c72005-04-25 21:11:48 +0000426 // block of the call instruction
427 BasicBlock* bb = ci->getParent();
Reid Spencer39a762d2005-04-25 02:53:12 +0000428
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000429 // Create a return instruction that we'll replace the call with.
430 // Note that the argument of the return is the argument of the call
Reid Spencerf2534c72005-04-25 21:11:48 +0000431 // instruction.
Chris Lattnercd60d382006-05-12 23:35:26 +0000432 new ReturnInst(ci->getOperand(1), ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000433
Reid Spencerf2534c72005-04-25 21:11:48 +0000434 // Split the block at the call instruction which places it in a new
435 // basic block.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000436 bb->splitBasicBlock(ci);
Reid Spencer39a762d2005-04-25 02:53:12 +0000437
Reid Spencerf2534c72005-04-25 21:11:48 +0000438 // The block split caused a branch instruction to be inserted into
439 // the end of the original block, right after the return instruction
440 // that we put there. That's not a valid block, so delete the branch
441 // instruction.
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000442 bb->getInstList().pop_back();
Reid Spencer39a762d2005-04-25 02:53:12 +0000443
Reid Spencerf2534c72005-04-25 21:11:48 +0000444 // Now we can finally get rid of the call instruction which now lives
445 // in the new basic block.
446 ci->eraseFromParent();
447
448 // Optimization succeeded, return true.
449 return true;
450 }
451 // We didn't pass the criteria for this optimization so return false
452 return false;
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000453 }
Reid Spencer39a762d2005-04-25 02:53:12 +0000454} ExitInMainOptimizer;
455
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000456/// This LibCallOptimization will simplify a call to the strcat library
457/// function. The simplification is possible only if the string being
458/// concatenated is a constant array or a constant expression that results in
459/// a constant string. In this case we can replace it with strlen + llvm.memcpy
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000460/// of the constant string. Both of these calls are further reduced, if possible
461/// on subsequent passes.
Reid Spencerf2534c72005-04-25 21:11:48 +0000462/// @brief Simplify the strcat library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000463struct VISIBILITY_HIDDEN StrCatOptimization : public LibCallOptimization {
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000464public:
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000465 /// @brief Default constructor
Reid Spencer95d8efd2005-05-03 02:54:54 +0000466 StrCatOptimization() : LibCallOptimization("strcat",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000467 "Number of 'strcat' calls simplified") {}
Reid Spencere249a822005-04-27 07:54:40 +0000468
469public:
Reid Spencerf2534c72005-04-25 21:11:48 +0000470
471 /// @brief Make sure that the "strcat" function has the right prototype
Chris Lattner182a9452007-04-07 21:58:02 +0000472 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
473 const FunctionType *FT = F->getFunctionType();
474 return FT->getNumParams() == 2 &&
Christopher Lambedf07882007-12-17 01:12:55 +0000475 FT->getReturnType() == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattner182a9452007-04-07 21:58:02 +0000476 FT->getParamType(0) == FT->getReturnType() &&
477 FT->getParamType(1) == FT->getReturnType();
Reid Spencerf2534c72005-04-25 21:11:48 +0000478 }
479
Reid Spencere249a822005-04-27 07:54:40 +0000480 /// @brief Optimize the strcat library function
Chris Lattner56b7fc72007-04-06 22:59:33 +0000481 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer08b49402005-04-27 17:46:54 +0000482 // Extract some information from the instruction
Chris Lattner56b7fc72007-04-06 22:59:33 +0000483 Value *Dst = CI->getOperand(1);
484 Value *Src = CI->getOperand(2);
Reid Spencer08b49402005-04-27 17:46:54 +0000485
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000486 // Extract the initializer (while making numerous checks) from the
Chris Lattner56b7fc72007-04-06 22:59:33 +0000487 // source operand of the call to strcat.
Chris Lattner182a9452007-04-07 21:58:02 +0000488 std::string SrcStr;
489 if (!GetConstantStringInfo(Src, SrcStr))
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000490 return false;
491
Reid Spencerb4f7b832005-04-26 07:45:18 +0000492 // Handle the simple, do-nothing case
Chris Lattner182a9452007-04-07 21:58:02 +0000493 if (SrcStr.empty())
Chris Lattner485b6412007-04-07 00:42:32 +0000494 return ReplaceCallWith(CI, Dst);
Reid Spencer8ee5aac2005-04-26 03:26:15 +0000495
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000496 // We need to find the end of the destination string. That's where the
Chris Lattner182a9452007-04-07 21:58:02 +0000497 // memory is to be moved to. We just generate a call to strlen.
Chris Lattner56b7fc72007-04-06 22:59:33 +0000498 CallInst *DstLen = new CallInst(SLC.get_strlen(), Dst,
499 Dst->getName()+".len", CI);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000500
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000501 // Now that we have the destination's length, we must index into the
Reid Spencerb4f7b832005-04-26 07:45:18 +0000502 // destination's pointer to get the actual memcpy destination (end of
503 // the string .. we're concatenating).
Chris Lattner56b7fc72007-04-06 22:59:33 +0000504 Dst = new GetElementPtrInst(Dst, DstLen, Dst->getName()+".indexed", CI);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000505
506 // We have enough information to now generate the memcpy call to
507 // do the concatenation for us.
Chris Lattner56b7fc72007-04-06 22:59:33 +0000508 Value *Vals[] = {
509 Dst, Src,
Chris Lattner182a9452007-04-07 21:58:02 +0000510 ConstantInt::get(SLC.getIntPtrType(), SrcStr.size()+1), // copy nul byte.
Chris Lattner56b7fc72007-04-06 22:59:33 +0000511 ConstantInt::get(Type::Int32Ty, 1) // alignment
512 };
David Greene17a5dfe2007-08-01 03:43:44 +0000513 new CallInst(SLC.get_memcpy(), Vals, Vals + 4, "", CI);
Reid Spencerb4f7b832005-04-26 07:45:18 +0000514
Chris Lattner485b6412007-04-07 00:42:32 +0000515 return ReplaceCallWith(CI, Dst);
Reid Spencer9bbaa2a2005-04-25 03:59:26 +0000516 }
517} StrCatOptimizer;
518
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000519/// This LibCallOptimization will simplify a call to the strchr library
Reid Spencer38cabd72005-05-03 07:23:44 +0000520/// function. It optimizes out cases where the arguments are both constant
521/// and the result can be determined statically.
522/// @brief Simplify the strcmp library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000523struct VISIBILITY_HIDDEN StrChrOptimization : public LibCallOptimization {
Reid Spencer38cabd72005-05-03 07:23:44 +0000524public:
525 StrChrOptimization() : LibCallOptimization("strchr",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000526 "Number of 'strchr' calls simplified") {}
Reid Spencer38cabd72005-05-03 07:23:44 +0000527
528 /// @brief Make sure that the "strchr" function has the right prototype
Chris Lattner39f0bb92007-04-06 23:38:55 +0000529 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
530 const FunctionType *FT = F->getFunctionType();
531 return FT->getNumParams() == 2 &&
Christopher Lambedf07882007-12-17 01:12:55 +0000532 FT->getReturnType() == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattner39f0bb92007-04-06 23:38:55 +0000533 FT->getParamType(0) == FT->getReturnType() &&
534 isa<IntegerType>(FT->getParamType(1));
Reid Spencer38cabd72005-05-03 07:23:44 +0000535 }
536
Chris Lattnerf8053ce2005-05-20 22:22:25 +0000537 /// @brief Perform the strchr optimizations
Chris Lattner39f0bb92007-04-06 23:38:55 +0000538 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer38cabd72005-05-03 07:23:44 +0000539 // Check that the first argument to strchr is a constant array of sbyte.
Chris Lattner182a9452007-04-07 21:58:02 +0000540 std::string Str;
541 if (!GetConstantStringInfo(CI->getOperand(1), Str))
Reid Spencer38cabd72005-05-03 07:23:44 +0000542 return false;
543
Chris Lattner39f0bb92007-04-06 23:38:55 +0000544 // If the second operand is not constant, just lower this to memchr since we
545 // know the length of the input string.
546 ConstantInt *CSI = dyn_cast<ConstantInt>(CI->getOperand(2));
Reid Spencerc635f472006-12-31 05:48:39 +0000547 if (!CSI) {
Chris Lattner39f0bb92007-04-06 23:38:55 +0000548 Value *Args[3] = {
549 CI->getOperand(1),
550 CI->getOperand(2),
Chris Lattner182a9452007-04-07 21:58:02 +0000551 ConstantInt::get(SLC.getIntPtrType(), Str.size()+1)
Chris Lattnerade1c2b2007-02-13 05:58:53 +0000552 };
David Greene17a5dfe2007-08-01 03:43:44 +0000553 return ReplaceCallWith(CI, new CallInst(SLC.get_memchr(), Args, Args + 3,
Chris Lattner485b6412007-04-07 00:42:32 +0000554 CI->getName(), CI));
Reid Spencer38cabd72005-05-03 07:23:44 +0000555 }
556
Chris Lattner182a9452007-04-07 21:58:02 +0000557 // strchr can find the nul character.
558 Str += '\0';
Chris Lattner39f0bb92007-04-06 23:38:55 +0000559
Chris Lattner182a9452007-04-07 21:58:02 +0000560 // Get the character we're looking for
561 char CharValue = CSI->getSExtValue();
562
Reid Spencer38cabd72005-05-03 07:23:44 +0000563 // Compute the offset
Chris Lattner39f0bb92007-04-06 23:38:55 +0000564 uint64_t i = 0;
565 while (1) {
Chris Lattner182a9452007-04-07 21:58:02 +0000566 if (i == Str.size()) // Didn't find the char. strchr returns null.
567 return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
568 // Did we find our match?
569 if (Str[i] == CharValue)
570 break;
Chris Lattner39f0bb92007-04-06 23:38:55 +0000571 ++i;
Reid Spencer38cabd72005-05-03 07:23:44 +0000572 }
573
Chris Lattner39f0bb92007-04-06 23:38:55 +0000574 // strchr(s+n,c) -> gep(s+n+i,c)
Reid Spencer38cabd72005-05-03 07:23:44 +0000575 // (if c is a constant integer and s is a constant string)
Chris Lattner39f0bb92007-04-06 23:38:55 +0000576 Value *Idx = ConstantInt::get(Type::Int64Ty, i);
577 Value *GEP = new GetElementPtrInst(CI->getOperand(1), Idx,
578 CI->getOperand(1)->getName() +
579 ".strchr", CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000580 return ReplaceCallWith(CI, GEP);
Reid Spencer38cabd72005-05-03 07:23:44 +0000581 }
582} StrChrOptimizer;
583
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000584/// This LibCallOptimization will simplify a call to the strcmp library
Reid Spencer4c444fe2005-04-30 03:17:54 +0000585/// function. It optimizes out cases where one or both arguments are constant
586/// and the result can be determined statically.
587/// @brief Simplify the strcmp library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000588struct VISIBILITY_HIDDEN StrCmpOptimization : public LibCallOptimization {
Reid Spencer4c444fe2005-04-30 03:17:54 +0000589public:
Reid Spencer95d8efd2005-05-03 02:54:54 +0000590 StrCmpOptimization() : LibCallOptimization("strcmp",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000591 "Number of 'strcmp' calls simplified") {}
Reid Spencer4c444fe2005-04-30 03:17:54 +0000592
Chris Lattnerf8053ce2005-05-20 22:22:25 +0000593 /// @brief Make sure that the "strcmp" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000594 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Chris Lattnerc9ccc302007-04-07 00:01:51 +0000595 const FunctionType *FT = F->getFunctionType();
596 return FT->getReturnType() == Type::Int32Ty && FT->getNumParams() == 2 &&
597 FT->getParamType(0) == FT->getParamType(1) &&
Christopher Lambedf07882007-12-17 01:12:55 +0000598 FT->getParamType(0) == PointerType::getUnqual(Type::Int8Ty);
Reid Spencer4c444fe2005-04-30 03:17:54 +0000599 }
600
Chris Lattnerf8053ce2005-05-20 22:22:25 +0000601 /// @brief Perform the strcmp optimization
Chris Lattnerc9ccc302007-04-07 00:01:51 +0000602 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer4c444fe2005-04-30 03:17:54 +0000603 // First, check to see if src and destination are the same. If they are,
Reid Spencer16449a92005-04-30 06:45:47 +0000604 // then the optimization is to replace the CallInst with a constant 0
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000605 // because the call is a no-op.
Chris Lattnerc9ccc302007-04-07 00:01:51 +0000606 Value *Str1P = CI->getOperand(1);
607 Value *Str2P = CI->getOperand(2);
Chris Lattner485b6412007-04-07 00:42:32 +0000608 if (Str1P == Str2P) // strcmp(x,x) -> 0
609 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
Reid Spencer4c444fe2005-04-30 03:17:54 +0000610
Chris Lattner182a9452007-04-07 21:58:02 +0000611 std::string Str1;
612 if (!GetConstantStringInfo(Str1P, Str1))
613 return false;
614 if (Str1.empty()) {
Chris Lattnerc9ccc302007-04-07 00:01:51 +0000615 // strcmp("", x) -> *x
616 Value *V = new LoadInst(Str2P, CI->getName()+".load", CI);
617 V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000618 return ReplaceCallWith(CI, V);
Reid Spencer4c444fe2005-04-30 03:17:54 +0000619 }
620
Chris Lattner182a9452007-04-07 21:58:02 +0000621 std::string Str2;
622 if (!GetConstantStringInfo(Str2P, Str2))
623 return false;
624 if (Str2.empty()) {
Chris Lattnerc9ccc302007-04-07 00:01:51 +0000625 // strcmp(x,"") -> *x
626 Value *V = new LoadInst(Str1P, CI->getName()+".load", CI);
627 V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000628 return ReplaceCallWith(CI, V);
Reid Spencer4c444fe2005-04-30 03:17:54 +0000629 }
630
Chris Lattner182a9452007-04-07 21:58:02 +0000631 // strcmp(x, y) -> cnst (if both x and y are constant strings)
632 int R = strcmp(Str1.c_str(), Str2.c_str());
633 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), R));
Reid Spencer4c444fe2005-04-30 03:17:54 +0000634 }
635} StrCmpOptimizer;
636
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000637/// This LibCallOptimization will simplify a call to the strncmp library
Reid Spencer49fa07042005-05-03 01:43:45 +0000638/// function. It optimizes out cases where one or both arguments are constant
639/// and the result can be determined statically.
640/// @brief Simplify the strncmp library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000641struct VISIBILITY_HIDDEN StrNCmpOptimization : public LibCallOptimization {
Reid Spencer49fa07042005-05-03 01:43:45 +0000642public:
Reid Spencer95d8efd2005-05-03 02:54:54 +0000643 StrNCmpOptimization() : LibCallOptimization("strncmp",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000644 "Number of 'strncmp' calls simplified") {}
Reid Spencer49fa07042005-05-03 01:43:45 +0000645
Chris Lattnerf8053ce2005-05-20 22:22:25 +0000646 /// @brief Make sure that the "strncmp" function has the right prototype
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000647 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
648 const FunctionType *FT = F->getFunctionType();
649 return FT->getReturnType() == Type::Int32Ty && FT->getNumParams() == 3 &&
650 FT->getParamType(0) == FT->getParamType(1) &&
Christopher Lambedf07882007-12-17 01:12:55 +0000651 FT->getParamType(0) == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000652 isa<IntegerType>(FT->getParamType(2));
Reid Spencer49fa07042005-05-03 01:43:45 +0000653 return false;
654 }
655
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000656 /// @brief Perform the strncmp optimization
657 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer49fa07042005-05-03 01:43:45 +0000658 // First, check to see if src and destination are the same. If they are,
659 // then the optimization is to replace the CallInst with a constant 0
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000660 // because the call is a no-op.
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000661 Value *Str1P = CI->getOperand(1);
662 Value *Str2P = CI->getOperand(2);
Chris Lattner182a9452007-04-07 21:58:02 +0000663 if (Str1P == Str2P) // strncmp(x,x, n) -> 0
Chris Lattner485b6412007-04-07 00:42:32 +0000664 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000665
Reid Spencer49fa07042005-05-03 01:43:45 +0000666 // Check the length argument, if it is Constant zero then the strings are
667 // considered equal.
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000668 uint64_t Length;
669 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
670 Length = LengthArg->getZExtValue();
671 else
672 return false;
673
Chris Lattner182a9452007-04-07 21:58:02 +0000674 if (Length == 0) // strncmp(x,y,0) -> 0
Chris Lattner485b6412007-04-07 00:42:32 +0000675 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000676
Chris Lattner182a9452007-04-07 21:58:02 +0000677 std::string Str1;
678 if (!GetConstantStringInfo(Str1P, Str1))
679 return false;
680 if (Str1.empty()) {
681 // strncmp("", x, n) -> *x
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000682 Value *V = new LoadInst(Str2P, CI->getName()+".load", CI);
683 V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000684 return ReplaceCallWith(CI, V);
Reid Spencer49fa07042005-05-03 01:43:45 +0000685 }
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000686
Chris Lattner182a9452007-04-07 21:58:02 +0000687 std::string Str2;
688 if (!GetConstantStringInfo(Str2P, Str2))
689 return false;
690 if (Str2.empty()) {
691 // strncmp(x, "", n) -> *x
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000692 Value *V = new LoadInst(Str1P, CI->getName()+".load", CI);
693 V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000694 return ReplaceCallWith(CI, V);
Reid Spencer49fa07042005-05-03 01:43:45 +0000695 }
Chris Lattnerf9ee6472007-04-07 00:06:57 +0000696
Chris Lattner182a9452007-04-07 21:58:02 +0000697 // strncmp(x, y, n) -> cnst (if both x and y are constant strings)
698 int R = strncmp(Str1.c_str(), Str2.c_str(), Length);
699 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), R));
Reid Spencer49fa07042005-05-03 01:43:45 +0000700 }
701} StrNCmpOptimizer;
702
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000703/// This LibCallOptimization will simplify a call to the strcpy library
704/// function. Two optimizations are possible:
Reid Spencere249a822005-04-27 07:54:40 +0000705/// (1) If src and dest are the same and not volatile, just return dest
706/// (2) If the src is a constant then we can convert to llvm.memmove
707/// @brief Simplify the strcpy library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000708struct VISIBILITY_HIDDEN StrCpyOptimization : public LibCallOptimization {
Reid Spencere249a822005-04-27 07:54:40 +0000709public:
Reid Spencer95d8efd2005-05-03 02:54:54 +0000710 StrCpyOptimization() : LibCallOptimization("strcpy",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000711 "Number of 'strcpy' calls simplified") {}
Reid Spencere249a822005-04-27 07:54:40 +0000712
713 /// @brief Make sure that the "strcpy" function has the right prototype
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000714 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
715 const FunctionType *FT = F->getFunctionType();
716 return FT->getNumParams() == 2 &&
717 FT->getParamType(0) == FT->getParamType(1) &&
718 FT->getReturnType() == FT->getParamType(0) &&
Christopher Lambedf07882007-12-17 01:12:55 +0000719 FT->getParamType(0) == PointerType::getUnqual(Type::Int8Ty);
Reid Spencere249a822005-04-27 07:54:40 +0000720 }
721
722 /// @brief Perform the strcpy optimization
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000723 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencere249a822005-04-27 07:54:40 +0000724 // First, check to see if src and destination are the same. If they are,
725 // then the optimization is to replace the CallInst with the destination
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000726 // because the call is a no-op. Note that this corresponds to the
Reid Spencere249a822005-04-27 07:54:40 +0000727 // degenerate strcpy(X,X) case which should have "undefined" results
728 // according to the C specification. However, it occurs sometimes and
729 // we optimize it as a no-op.
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000730 Value *Dst = CI->getOperand(1);
731 Value *Src = CI->getOperand(2);
732 if (Dst == Src) {
733 // strcpy(x, x) -> x
Chris Lattner485b6412007-04-07 00:42:32 +0000734 return ReplaceCallWith(CI, Dst);
Reid Spencere249a822005-04-27 07:54:40 +0000735 }
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000736
737 // Get the length of the constant string referenced by the Src operand.
Chris Lattner182a9452007-04-07 21:58:02 +0000738 std::string SrcStr;
739 if (!GetConstantStringInfo(Src, SrcStr))
Reid Spencere249a822005-04-27 07:54:40 +0000740 return false;
Chris Lattner182a9452007-04-07 21:58:02 +0000741
Reid Spencere249a822005-04-27 07:54:40 +0000742 // If the constant string's length is zero we can optimize this by just
743 // doing a store of 0 at the first byte of the destination
Dan Gohman70de4cb2008-01-29 13:02:09 +0000744 if (SrcStr.empty()) {
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000745 new StoreInst(ConstantInt::get(Type::Int8Ty, 0), Dst, CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000746 return ReplaceCallWith(CI, Dst);
Reid Spencere249a822005-04-27 07:54:40 +0000747 }
748
Reid Spencere249a822005-04-27 07:54:40 +0000749 // We have enough information to now generate the memcpy call to
750 // do the concatenation for us.
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000751 Value *MemcpyOps[] = {
Chris Lattner182a9452007-04-07 21:58:02 +0000752 Dst, Src, // Pass length including nul byte.
753 ConstantInt::get(SLC.getIntPtrType(), SrcStr.size()+1),
Chris Lattnerade1c2b2007-02-13 05:58:53 +0000754 ConstantInt::get(Type::Int32Ty, 1) // alignment
755 };
David Greene17a5dfe2007-08-01 03:43:44 +0000756 new CallInst(SLC.get_memcpy(), MemcpyOps, MemcpyOps + 4, "", CI);
Reid Spencere249a822005-04-27 07:54:40 +0000757
Chris Lattner485b6412007-04-07 00:42:32 +0000758 return ReplaceCallWith(CI, Dst);
Reid Spencere249a822005-04-27 07:54:40 +0000759 }
760} StrCpyOptimizer;
761
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000762/// This LibCallOptimization will simplify a call to the strlen library
763/// function by replacing it with a constant value if the string provided to
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000764/// it is a constant array.
Reid Spencer76dab9a2005-04-26 05:24:00 +0000765/// @brief Simplify the strlen library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000766struct VISIBILITY_HIDDEN StrLenOptimization : public LibCallOptimization {
Reid Spencer95d8efd2005-05-03 02:54:54 +0000767 StrLenOptimization() : LibCallOptimization("strlen",
Reid Spencer170ae7f2005-05-07 20:15:59 +0000768 "Number of 'strlen' calls simplified") {}
Reid Spencer76dab9a2005-04-26 05:24:00 +0000769
770 /// @brief Make sure that the "strlen" function has the right prototype
Chris Lattner6a6c1f12007-04-07 00:26:18 +0000771 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Chris Lattnere8829aa2007-04-07 01:02:00 +0000772 const FunctionType *FT = F->getFunctionType();
773 return FT->getNumParams() == 1 &&
Christopher Lambedf07882007-12-17 01:12:55 +0000774 FT->getParamType(0) == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattnere8829aa2007-04-07 01:02:00 +0000775 isa<IntegerType>(FT->getReturnType());
Reid Spencer76dab9a2005-04-26 05:24:00 +0000776 }
777
778 /// @brief Perform the strlen optimization
Chris Lattnere8829aa2007-04-07 01:02:00 +0000779 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer170ae7f2005-05-07 20:15:59 +0000780 // Make sure we're dealing with an sbyte* here.
Chris Lattner182a9452007-04-07 21:58:02 +0000781 Value *Src = CI->getOperand(1);
Reid Spencer170ae7f2005-05-07 20:15:59 +0000782
783 // Does the call to strlen have exactly one use?
Chris Lattnere8829aa2007-04-07 01:02:00 +0000784 if (CI->hasOneUse()) {
Reid Spencer266e42b2006-12-23 06:05:41 +0000785 // Is that single use a icmp operator?
Chris Lattnere8829aa2007-04-07 01:02:00 +0000786 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(CI->use_back()))
Reid Spencer170ae7f2005-05-07 20:15:59 +0000787 // Is it compared against a constant integer?
Chris Lattnere8829aa2007-04-07 01:02:00 +0000788 if (ConstantInt *Cst = dyn_cast<ConstantInt>(Cmp->getOperand(1))) {
Reid Spencer170ae7f2005-05-07 20:15:59 +0000789 // If its compared against length 0 with == or !=
Chris Lattnere8829aa2007-04-07 01:02:00 +0000790 if (Cst->getZExtValue() == 0 && Cmp->isEquality()) {
Reid Spencer170ae7f2005-05-07 20:15:59 +0000791 // strlen(x) != 0 -> *x != 0
792 // strlen(x) == 0 -> *x == 0
Chris Lattner182a9452007-04-07 21:58:02 +0000793 Value *V = new LoadInst(Src, Src->getName()+".first", CI);
Chris Lattnere8829aa2007-04-07 01:02:00 +0000794 V = new ICmpInst(Cmp->getPredicate(), V,
795 ConstantInt::get(Type::Int8Ty, 0),
796 Cmp->getName()+".strlen", CI);
797 Cmp->replaceAllUsesWith(V);
798 Cmp->eraseFromParent();
799 return ReplaceCallWith(CI, 0); // no uses.
Reid Spencer170ae7f2005-05-07 20:15:59 +0000800 }
801 }
Chris Lattnere8829aa2007-04-07 01:02:00 +0000802 }
Reid Spencer170ae7f2005-05-07 20:15:59 +0000803
804 // Get the length of the constant string operand
Chris Lattner182a9452007-04-07 21:58:02 +0000805 std::string Str;
806 if (!GetConstantStringInfo(Src, Str))
Reid Spencer76dab9a2005-04-26 05:24:00 +0000807 return false;
Chris Lattner182a9452007-04-07 21:58:02 +0000808
Reid Spencer170ae7f2005-05-07 20:15:59 +0000809 // strlen("xyz") -> 3 (for example)
Chris Lattner182a9452007-04-07 21:58:02 +0000810 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), Str.size()));
Reid Spencer76dab9a2005-04-26 05:24:00 +0000811 }
812} StrLenOptimizer;
813
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000814/// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value
815/// is equal or not-equal to zero.
816static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) {
817 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
818 UI != E; ++UI) {
Chris Lattner6a36d632007-04-07 01:03:46 +0000819 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
820 if (IC->isEquality())
821 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
822 if (C->isNullValue())
823 continue;
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000824 // Unknown instruction.
825 return false;
826 }
827 return true;
828}
829
830/// This memcmpOptimization will simplify a call to the memcmp library
831/// function.
Reid Spencer557ab152007-02-05 23:32:05 +0000832struct VISIBILITY_HIDDEN memcmpOptimization : public LibCallOptimization {
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000833 /// @brief Default Constructor
834 memcmpOptimization()
835 : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {}
836
837 /// @brief Make sure that the "memcmp" function has the right prototype
838 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
839 Function::const_arg_iterator AI = F->arg_begin();
840 if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false;
841 if (!isa<PointerType>((++AI)->getType())) return false;
Chris Lattner03c49532007-01-15 02:27:26 +0000842 if (!(++AI)->getType()->isInteger()) return false;
843 if (!F->getReturnType()->isInteger()) return false;
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000844 return true;
845 }
846
847 /// Because of alignment and instruction information that we don't have, we
848 /// leave the bulk of this to the code generators.
849 ///
850 /// Note that we could do much more if we could force alignment on otherwise
851 /// small aligned allocas, or if we could indicate that loads have a small
852 /// alignment.
853 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) {
854 Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
855
856 // If the two operands are the same, return zero.
857 if (LHS == RHS) {
858 // memcmp(s,s,x) -> 0
Chris Lattner485b6412007-04-07 00:42:32 +0000859 return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000860 }
861
862 // Make sure we have a constant length.
863 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
864 if (!LenC) return false;
Reid Spencere0fc4df2006-10-20 07:07:24 +0000865 uint64_t Len = LenC->getZExtValue();
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000866
867 // If the length is zero, this returns 0.
868 switch (Len) {
869 case 0:
870 // memcmp(s1,s2,0) -> 0
Chris Lattner485b6412007-04-07 00:42:32 +0000871 return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000872 case 1: {
873 // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2
Christopher Lambedf07882007-12-17 01:12:55 +0000874 const Type *UCharPtr = PointerType::getUnqual(Type::Int8Ty);
Reid Spencer6c38f0b2006-11-27 01:05:10 +0000875 CastInst *Op1Cast = CastInst::create(
876 Instruction::BitCast, LHS, UCharPtr, LHS->getName(), CI);
877 CastInst *Op2Cast = CastInst::create(
878 Instruction::BitCast, RHS, UCharPtr, RHS->getName(), CI);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000879 Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI);
880 Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI);
881 Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI);
882 if (RV->getType() != CI->getType())
Reid Spencerbfe26ff2006-12-13 00:50:17 +0000883 RV = CastInst::createIntegerCast(RV, CI->getType(), false,
884 RV->getName(), CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000885 return ReplaceCallWith(CI, RV);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000886 }
887 case 2:
888 if (IsOnlyUsedInEqualsZeroComparison(CI)) {
889 // TODO: IF both are aligned, use a short load/compare.
890
891 // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters
Christopher Lambedf07882007-12-17 01:12:55 +0000892 const Type *UCharPtr = PointerType::getUnqual(Type::Int8Ty);
Reid Spencer6c38f0b2006-11-27 01:05:10 +0000893 CastInst *Op1Cast = CastInst::create(
894 Instruction::BitCast, LHS, UCharPtr, LHS->getName(), CI);
895 CastInst *Op2Cast = CastInst::create(
896 Instruction::BitCast, RHS, UCharPtr, RHS->getName(), CI);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000897 Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI);
898 Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI);
899 Value *D1 = BinaryOperator::createSub(S1V1, S2V1,
900 CI->getName()+".d1", CI);
Reid Spencerc635f472006-12-31 05:48:39 +0000901 Constant *One = ConstantInt::get(Type::Int32Ty, 1);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000902 Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI);
903 Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI);
904 Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI);
Chris Lattnercd60d382006-05-12 23:35:26 +0000905 Value *S2V2 = new LoadInst(G2, RHS->getName()+".val2", CI);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000906 Value *D2 = BinaryOperator::createSub(S1V2, S2V2,
907 CI->getName()+".d1", CI);
908 Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI);
909 if (Or->getType() != CI->getType())
Reid Spencerbfe26ff2006-12-13 00:50:17 +0000910 Or = CastInst::createIntegerCast(Or, CI->getType(), false /*ZExt*/,
911 Or->getName(), CI);
Chris Lattner485b6412007-04-07 00:42:32 +0000912 return ReplaceCallWith(CI, Or);
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000913 }
914 break;
915 default:
916 break;
917 }
918
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000919 return false;
920 }
921} memcmpOptimizer;
922
Chris Lattnera8b4a562008-01-28 04:41:43 +0000923/// This LibCallOptimization will simplify a call to the memcpy library
924/// function. It simply converts them into calls to llvm.memcpy.*;
925/// the resulting call should be optimized later.
926/// @brief Simplify the memcpy library function.
927struct VISIBILITY_HIDDEN MemCpyOptimization : public LibCallOptimization {
928public:
929 MemCpyOptimization() : LibCallOptimization("memcpy",
930 "Number of 'memcpy' calls simplified") {}
931
932 /// @brief Make sure that the "memcpy" function has the right prototype
933 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
934 const FunctionType *FT = F->getFunctionType();
935 const Type* voidPtr = PointerType::getUnqual(Type::Int8Ty);
936 return FT->getReturnType() == voidPtr && FT->getNumParams() == 3 &&
937 FT->getParamType(0) == voidPtr &&
938 FT->getParamType(1) == voidPtr &&
939 FT->getParamType(2) == SLC.getIntPtrType();
940 }
941
942 /// @brief Perform the memcpy optimization
943 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
944 Value *MemcpyOps[] = {
945 CI->getOperand(1), CI->getOperand(2), CI->getOperand(3),
946 ConstantInt::get(Type::Int32Ty, 1) // align = 1 always.
947 };
948 new CallInst(SLC.get_memcpy(), MemcpyOps, MemcpyOps + 4, "", CI);
949 // memcpy always returns the destination
950 return ReplaceCallWith(CI, CI->getOperand(1));
951 }
952} MemCpyOptimizer;
Chris Lattnerc244e7c2005-09-29 04:54:20 +0000953
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +0000954/// This LibCallOptimization will simplify a call to the memcpy library
955/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
Reid Spencer7ddcfb32005-04-27 21:29:20 +0000956/// bytes depending on the length of the string and the alignment. Additional
957/// optimizations are possible in code generation (sequence of immediate store)
Reid Spencerf2534c72005-04-25 21:11:48 +0000958/// @brief Simplify the memcpy library function.
Reid Spencer557ab152007-02-05 23:32:05 +0000959struct VISIBILITY_HIDDEN LLVMMemCpyMoveOptzn : public LibCallOptimization {
Chris Lattnerea7986a2006-03-03 01:30:23 +0000960 LLVMMemCpyMoveOptzn(const char* fname, const char* desc)
961 : LibCallOptimization(fname, desc) {}
Reid Spencerf2534c72005-04-25 21:11:48 +0000962
963 /// @brief Make sure that the "memcpy" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000964 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD) {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000965 // Just make sure this has 4 arguments per LLVM spec.
Reid Spencer2bc7a4f2005-04-26 23:02:16 +0000966 return (f->arg_size() == 4);
Reid Spencerf2534c72005-04-25 21:11:48 +0000967 }
968
Reid Spencerb4f7b832005-04-26 07:45:18 +0000969 /// Because of alignment and instruction information that we don't have, we
970 /// leave the bulk of this to the code generators. The optimization here just
971 /// deals with a few degenerate cases where the length of the string and the
972 /// alignment match the sizes of our intrinsic types so we can do a load and
973 /// store instead of the memcpy call.
974 /// @brief Perform the memcpy optimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +0000975 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& TD) {
Reid Spencer4855ebf2005-04-26 19:55:57 +0000976 // Make sure we have constant int values to work with
977 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
978 if (!LEN)
979 return false;
980 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
981 if (!ALIGN)
982 return false;
983
984 // If the length is larger than the alignment, we can't optimize
Reid Spencere0fc4df2006-10-20 07:07:24 +0000985 uint64_t len = LEN->getZExtValue();
986 uint64_t alignment = ALIGN->getZExtValue();
Reid Spencer38cabd72005-05-03 07:23:44 +0000987 if (alignment == 0)
988 alignment = 1; // Alignment 0 is identity for alignment 1
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000989 if (len > alignment)
Reid Spencerb4f7b832005-04-26 07:45:18 +0000990 return false;
991
Reid Spencer08b49402005-04-27 17:46:54 +0000992 // Get the type we will cast to, based on size of the string
Reid Spencerb4f7b832005-04-26 07:45:18 +0000993 Value* dest = ci->getOperand(1);
994 Value* src = ci->getOperand(2);
Reid Spencer4f98e622007-01-07 21:45:41 +0000995 const Type* castType = 0;
Chris Lattner485b6412007-04-07 00:42:32 +0000996 switch (len) {
Reid Spencerbb92b4f2005-04-26 19:13:17 +0000997 case 0:
Chris Lattner485b6412007-04-07 00:42:32 +0000998 // memcpy(d,s,0,a) -> d
999 return ReplaceCallWith(ci, 0);
Reid Spencerc635f472006-12-31 05:48:39 +00001000 case 1: castType = Type::Int8Ty; break;
1001 case 2: castType = Type::Int16Ty; break;
1002 case 4: castType = Type::Int32Ty; break;
1003 case 8: castType = Type::Int64Ty; break;
Reid Spencerb4f7b832005-04-26 07:45:18 +00001004 default:
1005 return false;
1006 }
Reid Spencer08b49402005-04-27 17:46:54 +00001007
1008 // Cast source and dest to the right sized primitive and then load/store
Reid Spencer6c38f0b2006-11-27 01:05:10 +00001009 CastInst* SrcCast = CastInst::create(Instruction::BitCast,
Christopher Lambedf07882007-12-17 01:12:55 +00001010 src, PointerType::getUnqual(castType), src->getName()+".cast", ci);
Reid Spencer6c38f0b2006-11-27 01:05:10 +00001011 CastInst* DestCast = CastInst::create(Instruction::BitCast,
Christopher Lambedf07882007-12-17 01:12:55 +00001012 dest, PointerType::getUnqual(castType),dest->getName()+".cast", ci);
Reid Spencer08b49402005-04-27 17:46:54 +00001013 LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci);
Reid Spencerde46e482006-11-02 20:25:50 +00001014 new StoreInst(LI, DestCast, ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001015 return ReplaceCallWith(ci, 0);
Reid Spencerf2534c72005-04-25 21:11:48 +00001016 }
Chris Lattnerea7986a2006-03-03 01:30:23 +00001017};
Reid Spencerbb92b4f2005-04-26 19:13:17 +00001018
Chris Lattnerea7986a2006-03-03 01:30:23 +00001019/// This LibCallOptimization will simplify a call to the memcpy/memmove library
1020/// functions.
1021LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer32("llvm.memcpy.i32",
1022 "Number of 'llvm.memcpy' calls simplified");
1023LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer64("llvm.memcpy.i64",
1024 "Number of 'llvm.memcpy' calls simplified");
1025LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer32("llvm.memmove.i32",
1026 "Number of 'llvm.memmove' calls simplified");
1027LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer64("llvm.memmove.i64",
1028 "Number of 'llvm.memmove' calls simplified");
Reid Spencer38cabd72005-05-03 07:23:44 +00001029
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001030/// This LibCallOptimization will simplify a call to the memset library
1031/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
1032/// bytes depending on the length argument.
Reid Spencer557ab152007-02-05 23:32:05 +00001033struct VISIBILITY_HIDDEN LLVMMemSetOptimization : public LibCallOptimization {
Reid Spencer38cabd72005-05-03 07:23:44 +00001034 /// @brief Default Constructor
Chris Lattnerea7986a2006-03-03 01:30:23 +00001035 LLVMMemSetOptimization(const char *Name) : LibCallOptimization(Name,
Reid Spencer38cabd72005-05-03 07:23:44 +00001036 "Number of 'llvm.memset' calls simplified") {}
Reid Spencer38cabd72005-05-03 07:23:44 +00001037
1038 /// @brief Make sure that the "memset" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001039 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
Reid Spencer38cabd72005-05-03 07:23:44 +00001040 // Just make sure this has 3 arguments per LLVM spec.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001041 return F->arg_size() == 4;
Reid Spencer38cabd72005-05-03 07:23:44 +00001042 }
1043
1044 /// Because of alignment and instruction information that we don't have, we
1045 /// leave the bulk of this to the code generators. The optimization here just
1046 /// deals with a few degenerate cases where the length parameter is constant
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001047 /// and the alignment matches the sizes of our intrinsic types so we can do
Reid Spencer38cabd72005-05-03 07:23:44 +00001048 /// store instead of the memcpy call. Other calls are transformed into the
1049 /// llvm.memset intrinsic.
1050 /// @brief Perform the memset optimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001051 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &TD) {
Reid Spencer38cabd72005-05-03 07:23:44 +00001052 // Make sure we have constant int values to work with
1053 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
1054 if (!LEN)
1055 return false;
1056 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
1057 if (!ALIGN)
1058 return false;
1059
1060 // Extract the length and alignment
Reid Spencere0fc4df2006-10-20 07:07:24 +00001061 uint64_t len = LEN->getZExtValue();
1062 uint64_t alignment = ALIGN->getZExtValue();
Reid Spencer38cabd72005-05-03 07:23:44 +00001063
1064 // Alignment 0 is identity for alignment 1
1065 if (alignment == 0)
1066 alignment = 1;
1067
1068 // If the length is zero, this is a no-op
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001069 if (len == 0) {
Reid Spencer38cabd72005-05-03 07:23:44 +00001070 // memset(d,c,0,a) -> noop
Chris Lattner485b6412007-04-07 00:42:32 +00001071 return ReplaceCallWith(ci, 0);
Reid Spencer38cabd72005-05-03 07:23:44 +00001072 }
1073
1074 // If the length is larger than the alignment, we can't optimize
1075 if (len > alignment)
1076 return false;
1077
1078 // Make sure we have a constant ubyte to work with so we can extract
1079 // the value to be filled.
Reid Spencere0fc4df2006-10-20 07:07:24 +00001080 ConstantInt* FILL = dyn_cast<ConstantInt>(ci->getOperand(2));
Reid Spencer38cabd72005-05-03 07:23:44 +00001081 if (!FILL)
1082 return false;
Reid Spencerc635f472006-12-31 05:48:39 +00001083 if (FILL->getType() != Type::Int8Ty)
Reid Spencer38cabd72005-05-03 07:23:44 +00001084 return false;
1085
1086 // memset(s,c,n) -> store s, c (for n=1,2,4,8)
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001087
Reid Spencer38cabd72005-05-03 07:23:44 +00001088 // Extract the fill character
Reid Spencere0fc4df2006-10-20 07:07:24 +00001089 uint64_t fill_char = FILL->getZExtValue();
Reid Spencer38cabd72005-05-03 07:23:44 +00001090 uint64_t fill_value = fill_char;
1091
1092 // Get the type we will cast to, based on size of memory area to fill, and
1093 // and the value we will store there.
1094 Value* dest = ci->getOperand(1);
Reid Spencer4f98e622007-01-07 21:45:41 +00001095 const Type* castType = 0;
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001096 switch (len) {
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001097 case 1:
Reid Spencerc635f472006-12-31 05:48:39 +00001098 castType = Type::Int8Ty;
Reid Spencer38cabd72005-05-03 07:23:44 +00001099 break;
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001100 case 2:
Reid Spencerc635f472006-12-31 05:48:39 +00001101 castType = Type::Int16Ty;
Reid Spencer38cabd72005-05-03 07:23:44 +00001102 fill_value |= fill_char << 8;
1103 break;
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001104 case 4:
Reid Spencerc635f472006-12-31 05:48:39 +00001105 castType = Type::Int32Ty;
Reid Spencer38cabd72005-05-03 07:23:44 +00001106 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1107 break;
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001108 case 8:
Reid Spencerc635f472006-12-31 05:48:39 +00001109 castType = Type::Int64Ty;
Reid Spencer38cabd72005-05-03 07:23:44 +00001110 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1111 fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48;
1112 fill_value |= fill_char << 56;
1113 break;
1114 default:
1115 return false;
1116 }
1117
1118 // Cast dest to the right sized primitive and then load/store
Christopher Lambedf07882007-12-17 01:12:55 +00001119 CastInst* DestCast = new BitCastInst(dest, PointerType::getUnqual(castType),
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001120 dest->getName()+".cast", ci);
Reid Spencere0fc4df2006-10-20 07:07:24 +00001121 new StoreInst(ConstantInt::get(castType,fill_value),DestCast, ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001122 return ReplaceCallWith(ci, 0);
Reid Spencer38cabd72005-05-03 07:23:44 +00001123 }
Chris Lattnerea7986a2006-03-03 01:30:23 +00001124};
1125
1126LLVMMemSetOptimization MemSet32Optimizer("llvm.memset.i32");
1127LLVMMemSetOptimization MemSet64Optimizer("llvm.memset.i64");
1128
Reid Spencerbb92b4f2005-04-26 19:13:17 +00001129
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001130/// This LibCallOptimization will simplify calls to the "pow" library
1131/// function. It looks for cases where the result of pow is well known and
Reid Spencer93616972005-04-29 09:39:47 +00001132/// substitutes the appropriate value.
1133/// @brief Simplify the pow library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001134struct VISIBILITY_HIDDEN PowOptimization : public LibCallOptimization {
Reid Spencer93616972005-04-29 09:39:47 +00001135public:
1136 /// @brief Default Constructor
Reid Spencer95d8efd2005-05-03 02:54:54 +00001137 PowOptimization() : LibCallOptimization("pow",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001138 "Number of 'pow' calls simplified") {}
Reid Spencer95d8efd2005-05-03 02:54:54 +00001139
Reid Spencer93616972005-04-29 09:39:47 +00001140 /// @brief Make sure that the "pow" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001141 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
Reid Spencer93616972005-04-29 09:39:47 +00001142 // Just make sure this has 2 arguments
1143 return (f->arg_size() == 2);
1144 }
1145
1146 /// @brief Perform the pow optimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001147 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
Reid Spencer93616972005-04-29 09:39:47 +00001148 const Type *Ty = cast<Function>(ci->getOperand(0))->getReturnType();
Dale Johannesen6bf69ed2007-09-28 18:06:58 +00001149 if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy)
1150 return false; // FIXME long double not yet supported
Reid Spencer93616972005-04-29 09:39:47 +00001151 Value* base = ci->getOperand(1);
1152 Value* expn = ci->getOperand(2);
1153 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(base)) {
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001154 if (Op1->isExactlyValue(1.0)) // pow(1.0,x) -> 1.0
1155 return ReplaceCallWith(ci, ConstantFP::get(Ty,
1156 Ty==Type::FloatTy ? APFloat(1.0f) : APFloat(1.0)));
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001157 } else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn)) {
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001158 if (Op2->getValueAPF().isZero()) {
Reid Spencer93616972005-04-29 09:39:47 +00001159 // pow(x,0.0) -> 1.0
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001160 return ReplaceCallWith(ci, ConstantFP::get(Ty,
1161 Ty==Type::FloatTy ? APFloat(1.0f) : APFloat(1.0)));
1162 } else if (Op2->isExactlyValue(0.5)) {
Reid Spencer93616972005-04-29 09:39:47 +00001163 // pow(x,0.5) -> sqrt(x)
1164 CallInst* sqrt_inst = new CallInst(SLC.get_sqrt(), base,
1165 ci->getName()+".pow",ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001166 return ReplaceCallWith(ci, sqrt_inst);
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001167 } else if (Op2->isExactlyValue(1.0)) {
Reid Spencer93616972005-04-29 09:39:47 +00001168 // pow(x,1.0) -> x
Chris Lattner485b6412007-04-07 00:42:32 +00001169 return ReplaceCallWith(ci, base);
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001170 } else if (Op2->isExactlyValue(-1.0)) {
Reid Spencer93616972005-04-29 09:39:47 +00001171 // pow(x,-1.0) -> 1.0/x
Chris Lattner485b6412007-04-07 00:42:32 +00001172 Value *div_inst =
Dale Johannesenbed9dc42007-09-06 18:13:44 +00001173 BinaryOperator::createFDiv(ConstantFP::get(Ty,
1174 Ty==Type::FloatTy ? APFloat(1.0f) : APFloat(1.0)),
1175 base, ci->getName()+".pow", ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001176 return ReplaceCallWith(ci, div_inst);
Reid Spencer93616972005-04-29 09:39:47 +00001177 }
1178 }
1179 return false; // opt failed
1180 }
1181} PowOptimizer;
1182
Evan Cheng1fc40252006-06-16 08:36:35 +00001183/// This LibCallOptimization will simplify calls to the "printf" library
1184/// function. It looks for cases where the result of printf is not used and the
1185/// operation can be reduced to something simpler.
1186/// @brief Simplify the printf library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001187struct VISIBILITY_HIDDEN PrintfOptimization : public LibCallOptimization {
Evan Cheng1fc40252006-06-16 08:36:35 +00001188public:
1189 /// @brief Default Constructor
1190 PrintfOptimization() : LibCallOptimization("printf",
1191 "Number of 'printf' calls simplified") {}
1192
1193 /// @brief Make sure that the "printf" function has the right prototype
Chris Lattner0f150952007-04-07 01:18:36 +00001194 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Chris Lattner49fa8d22007-04-14 01:17:48 +00001195 // Just make sure this has at least 1 argument and returns an integer or
1196 // void type.
1197 const FunctionType *FT = F->getFunctionType();
1198 return FT->getNumParams() >= 1 &&
1199 (isa<IntegerType>(FT->getReturnType()) ||
1200 FT->getReturnType() == Type::VoidTy);
Evan Cheng1fc40252006-06-16 08:36:35 +00001201 }
1202
1203 /// @brief Perform the printf optimization.
Chris Lattner0f150952007-04-07 01:18:36 +00001204 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Evan Cheng1fc40252006-06-16 08:36:35 +00001205 // All the optimizations depend on the length of the first argument and the
1206 // fact that it is a constant string array. Check that now
Chris Lattner182a9452007-04-07 21:58:02 +00001207 std::string FormatStr;
1208 if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
Evan Cheng1fc40252006-06-16 08:36:35 +00001209 return false;
Chris Lattner49fa8d22007-04-14 01:17:48 +00001210
1211 // If this is a simple constant string with no format specifiers that ends
1212 // with a \n, turn it into a puts call.
1213 if (FormatStr.empty()) {
1214 // Tolerate printf's declared void.
1215 if (CI->use_empty()) return ReplaceCallWith(CI, 0);
1216 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
1217 }
1218
1219 if (FormatStr.size() == 1) {
1220 // Turn this into a putchar call, even if it is a %.
1221 Value *V = ConstantInt::get(Type::Int32Ty, FormatStr[0]);
1222 new CallInst(SLC.get_putchar(), V, "", CI);
1223 if (CI->use_empty()) return ReplaceCallWith(CI, 0);
1224 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1225 }
Evan Cheng1fc40252006-06-16 08:36:35 +00001226
Chris Lattner49fa8d22007-04-14 01:17:48 +00001227 // Check to see if the format str is something like "foo\n", in which case
1228 // we convert it to a puts call. We don't allow it to contain any format
1229 // characters.
1230 if (FormatStr[FormatStr.size()-1] == '\n' &&
1231 FormatStr.find('%') == std::string::npos) {
1232 // Create a string literal with no \n on it. We expect the constant merge
1233 // pass to be run after this pass, to merge duplicate strings.
1234 FormatStr.erase(FormatStr.end()-1);
1235 Constant *Init = ConstantArray::get(FormatStr, true);
1236 Constant *GV = new GlobalVariable(Init->getType(), true,
1237 GlobalVariable::InternalLinkage,
1238 Init, "str",
1239 CI->getParent()->getParent()->getParent());
1240 // Cast GV to be a pointer to char.
Christopher Lambedf07882007-12-17 01:12:55 +00001241 GV = ConstantExpr::getBitCast(GV, PointerType::getUnqual(Type::Int8Ty));
Chris Lattner49fa8d22007-04-14 01:17:48 +00001242 new CallInst(SLC.get_puts(), GV, "", CI);
1243
1244 if (CI->use_empty()) return ReplaceCallWith(CI, 0);
Dale Johannesen4d063912007-10-24 20:14:50 +00001245 // The return value from printf includes the \n we just removed, so +1.
Chris Lattner49fa8d22007-04-14 01:17:48 +00001246 return ReplaceCallWith(CI,
Dale Johannesen4d063912007-10-24 20:14:50 +00001247 ConstantInt::get(CI->getType(),
1248 FormatStr.size()+1));
Chris Lattner49fa8d22007-04-14 01:17:48 +00001249 }
1250
1251
Chris Lattner182a9452007-04-07 21:58:02 +00001252 // Only support %c or "%s\n" for now.
1253 if (FormatStr.size() < 2 || FormatStr[0] != '%')
Chris Lattner0f150952007-04-07 01:18:36 +00001254 return false;
Evan Cheng1fc40252006-06-16 08:36:35 +00001255
1256 // Get the second character and switch on its value
Chris Lattner182a9452007-04-07 21:58:02 +00001257 switch (FormatStr[1]) {
Chris Lattner0f150952007-04-07 01:18:36 +00001258 default: return false;
Chris Lattner182a9452007-04-07 21:58:02 +00001259 case 's':
Chris Lattner49fa8d22007-04-14 01:17:48 +00001260 if (FormatStr != "%s\n" || CI->getNumOperands() < 3 ||
Chris Lattner182a9452007-04-07 21:58:02 +00001261 // TODO: could insert strlen call to compute string length.
1262 !CI->use_empty())
Evan Cheng1fc40252006-06-16 08:36:35 +00001263 return false;
Chris Lattner0f150952007-04-07 01:18:36 +00001264
1265 // printf("%s\n",str) -> puts(str)
Chris Lattnerbed184c2007-04-07 21:04:50 +00001266 new CallInst(SLC.get_puts(), CastToCStr(CI->getOperand(2), CI),
Chris Lattner0f150952007-04-07 01:18:36 +00001267 CI->getName(), CI);
1268 return ReplaceCallWith(CI, 0);
Chris Lattner0f150952007-04-07 01:18:36 +00001269 case 'c': {
1270 // printf("%c",c) -> putchar(c)
Chris Lattner49fa8d22007-04-14 01:17:48 +00001271 if (FormatStr.size() != 2 || CI->getNumOperands() < 3)
Chris Lattner0f150952007-04-07 01:18:36 +00001272 return false;
1273
1274 Value *V = CI->getOperand(2);
1275 if (!isa<IntegerType>(V->getType()) ||
Chris Lattner182a9452007-04-07 21:58:02 +00001276 cast<IntegerType>(V->getType())->getBitWidth() > 32)
Chris Lattner0f150952007-04-07 01:18:36 +00001277 return false;
1278
Chris Lattner182a9452007-04-07 21:58:02 +00001279 V = CastInst::createZExtOrBitCast(V, Type::Int32Ty, CI->getName()+".int",
Chris Lattner0f150952007-04-07 01:18:36 +00001280 CI);
1281 new CallInst(SLC.get_putchar(), V, "", CI);
Chris Lattner182a9452007-04-07 21:58:02 +00001282 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
Chris Lattner0f150952007-04-07 01:18:36 +00001283 }
1284 }
Evan Cheng1fc40252006-06-16 08:36:35 +00001285 }
1286} PrintfOptimizer;
1287
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001288/// This LibCallOptimization will simplify calls to the "fprintf" library
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001289/// function. It looks for cases where the result of fprintf is not used and the
1290/// operation can be reduced to something simpler.
Evan Cheng1fc40252006-06-16 08:36:35 +00001291/// @brief Simplify the fprintf library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001292struct VISIBILITY_HIDDEN FPrintFOptimization : public LibCallOptimization {
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001293public:
1294 /// @brief Default Constructor
Reid Spencer95d8efd2005-05-03 02:54:54 +00001295 FPrintFOptimization() : LibCallOptimization("fprintf",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001296 "Number of 'fprintf' calls simplified") {}
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001297
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001298 /// @brief Make sure that the "fprintf" function has the right prototype
Chris Lattnerbed184c2007-04-07 21:04:50 +00001299 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1300 const FunctionType *FT = F->getFunctionType();
1301 return FT->getNumParams() == 2 && // two fixed arguments.
Christopher Lambedf07882007-12-17 01:12:55 +00001302 FT->getParamType(1) == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattnerbed184c2007-04-07 21:04:50 +00001303 isa<PointerType>(FT->getParamType(0)) &&
1304 isa<IntegerType>(FT->getReturnType());
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001305 }
1306
1307 /// @brief Perform the fprintf optimization.
Chris Lattnerbed184c2007-04-07 21:04:50 +00001308 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001309 // If the call has more than 3 operands, we can't optimize it
Chris Lattnerbed184c2007-04-07 21:04:50 +00001310 if (CI->getNumOperands() != 3 && CI->getNumOperands() != 4)
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001311 return false;
1312
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001313 // All the optimizations depend on the format string.
Chris Lattner182a9452007-04-07 21:58:02 +00001314 std::string FormatStr;
1315 if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001316 return false;
1317
Chris Lattner182a9452007-04-07 21:58:02 +00001318 // If this is just a format string, turn it into fwrite.
Chris Lattnerbed184c2007-04-07 21:04:50 +00001319 if (CI->getNumOperands() == 3) {
Chris Lattner182a9452007-04-07 21:58:02 +00001320 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1321 if (FormatStr[i] == '%')
Chris Lattnerbed184c2007-04-07 21:04:50 +00001322 return false; // we found a format specifier
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001323
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001324 // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file)
Chris Lattnerbed184c2007-04-07 21:04:50 +00001325 const Type *FILEty = CI->getOperand(1)->getType();
John Criswell4642afd2005-06-29 15:03:18 +00001326
Chris Lattnerbed184c2007-04-07 21:04:50 +00001327 Value *FWriteArgs[] = {
1328 CI->getOperand(2),
Chris Lattner182a9452007-04-07 21:58:02 +00001329 ConstantInt::get(SLC.getIntPtrType(), FormatStr.size()),
Chris Lattnerbed184c2007-04-07 21:04:50 +00001330 ConstantInt::get(SLC.getIntPtrType(), 1),
1331 CI->getOperand(1)
Chris Lattnerade1c2b2007-02-13 05:58:53 +00001332 };
David Greene17a5dfe2007-08-01 03:43:44 +00001333 new CallInst(SLC.get_fwrite(FILEty), FWriteArgs, FWriteArgs + 4, CI->getName(), CI);
Chris Lattner182a9452007-04-07 21:58:02 +00001334 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(),
1335 FormatStr.size()));
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001336 }
Chris Lattnerbed184c2007-04-07 21:04:50 +00001337
1338 // The remaining optimizations require the format string to be length 2:
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001339 // "%s" or "%c".
Chris Lattner182a9452007-04-07 21:58:02 +00001340 if (FormatStr.size() != 2 || FormatStr[0] != '%')
Chris Lattnerbed184c2007-04-07 21:04:50 +00001341 return false;
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001342
1343 // Get the second character and switch on its value
Chris Lattner182a9452007-04-07 21:58:02 +00001344 switch (FormatStr[1]) {
Chris Lattnerbed184c2007-04-07 21:04:50 +00001345 case 'c': {
1346 // fprintf(file,"%c",c) -> fputc(c,file)
1347 const Type *FILETy = CI->getOperand(1)->getType();
1348 Value *C = CastInst::createZExtOrBitCast(CI->getOperand(3), Type::Int32Ty,
1349 CI->getName()+".int", CI);
David Greene17a5dfe2007-08-01 03:43:44 +00001350 SmallVector<Value *, 2> Args;
1351 Args.push_back(C);
1352 Args.push_back(CI->getOperand(1));
1353 new CallInst(SLC.get_fputc(FILETy), Args.begin(), Args.end(), "", CI);
Chris Lattnerbed184c2007-04-07 21:04:50 +00001354 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1355 }
1356 case 's': {
1357 const Type *FILETy = CI->getOperand(1)->getType();
Chris Lattnerbed184c2007-04-07 21:04:50 +00001358
1359 // If the result of the fprintf call is used, we can't do this.
Chris Lattner182a9452007-04-07 21:58:02 +00001360 // TODO: we should insert a strlen call.
Chris Lattnerbed184c2007-04-07 21:04:50 +00001361 if (!CI->use_empty())
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001362 return false;
Chris Lattnerbed184c2007-04-07 21:04:50 +00001363
1364 // fprintf(file,"%s",str) -> fputs(str,file)
David Greene17a5dfe2007-08-01 03:43:44 +00001365 SmallVector<Value *, 2> Args;
1366 Args.push_back(CastToCStr(CI->getOperand(3), CI));
1367 Args.push_back(CI->getOperand(1));
1368 new CallInst(SLC.get_fputs(FILETy), Args.begin(),
1369 Args.end(), CI->getName(), CI);
Chris Lattnerbed184c2007-04-07 21:04:50 +00001370 return ReplaceCallWith(CI, 0);
1371 }
1372 default:
1373 return false;
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001374 }
Reid Spencer2d5c7be2005-05-02 23:59:26 +00001375 }
1376} FPrintFOptimizer;
1377
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001378/// This LibCallOptimization will simplify calls to the "sprintf" library
Reid Spencer1e520fd2005-05-04 03:20:21 +00001379/// function. It looks for cases where the result of sprintf is not used and the
1380/// operation can be reduced to something simpler.
Evan Cheng1fc40252006-06-16 08:36:35 +00001381/// @brief Simplify the sprintf library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001382struct VISIBILITY_HIDDEN SPrintFOptimization : public LibCallOptimization {
Reid Spencer1e520fd2005-05-04 03:20:21 +00001383public:
1384 /// @brief Default Constructor
1385 SPrintFOptimization() : LibCallOptimization("sprintf",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001386 "Number of 'sprintf' calls simplified") {}
Reid Spencer1e520fd2005-05-04 03:20:21 +00001387
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001388 /// @brief Make sure that the "sprintf" function has the right prototype
1389 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1390 const FunctionType *FT = F->getFunctionType();
1391 return FT->getNumParams() == 2 && // two fixed arguments.
Christopher Lambedf07882007-12-17 01:12:55 +00001392 FT->getParamType(1) == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001393 FT->getParamType(0) == FT->getParamType(1) &&
1394 isa<IntegerType>(FT->getReturnType());
Reid Spencer1e520fd2005-05-04 03:20:21 +00001395 }
1396
1397 /// @brief Perform the sprintf optimization.
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001398 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Reid Spencer1e520fd2005-05-04 03:20:21 +00001399 // If the call has more than 3 operands, we can't optimize it
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001400 if (CI->getNumOperands() != 3 && CI->getNumOperands() != 4)
Reid Spencer1e520fd2005-05-04 03:20:21 +00001401 return false;
1402
Chris Lattner182a9452007-04-07 21:58:02 +00001403 std::string FormatStr;
1404 if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
Reid Spencer1e520fd2005-05-04 03:20:21 +00001405 return false;
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001406
1407 if (CI->getNumOperands() == 3) {
Reid Spencer1e520fd2005-05-04 03:20:21 +00001408 // Make sure there's no % in the constant array
Chris Lattner182a9452007-04-07 21:58:02 +00001409 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1410 if (FormatStr[i] == '%')
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001411 return false; // we found a format specifier
1412
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001413 // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001414 Value *MemCpyArgs[] = {
1415 CI->getOperand(1), CI->getOperand(2),
Chris Lattner182a9452007-04-07 21:58:02 +00001416 ConstantInt::get(SLC.getIntPtrType(),
1417 FormatStr.size()+1), // Copy the nul byte.
Chris Lattnerade1c2b2007-02-13 05:58:53 +00001418 ConstantInt::get(Type::Int32Ty, 1)
1419 };
David Greene17a5dfe2007-08-01 03:43:44 +00001420 new CallInst(SLC.get_memcpy(), MemCpyArgs, MemCpyArgs + 4, "", CI);
Chris Lattner182a9452007-04-07 21:58:02 +00001421 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(),
1422 FormatStr.size()));
Reid Spencer1e520fd2005-05-04 03:20:21 +00001423 }
1424
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001425 // The remaining optimizations require the format string to be "%s" or "%c".
Chris Lattner182a9452007-04-07 21:58:02 +00001426 if (FormatStr.size() != 2 || FormatStr[0] != '%')
Reid Spencer1e520fd2005-05-04 03:20:21 +00001427 return false;
1428
Reid Spencer1e520fd2005-05-04 03:20:21 +00001429 // Get the second character and switch on its value
Chris Lattneraa8ad102007-04-08 18:11:26 +00001430 switch (FormatStr[1]) {
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001431 case 'c': {
1432 // sprintf(dest,"%c",chr) -> store chr, dest
1433 Value *V = CastInst::createTruncOrBitCast(CI->getOperand(3),
1434 Type::Int8Ty, "char", CI);
1435 new StoreInst(V, CI->getOperand(1), CI);
1436 Value *Ptr = new GetElementPtrInst(CI->getOperand(1),
1437 ConstantInt::get(Type::Int32Ty, 1),
1438 CI->getOperand(1)->getName()+".end",
1439 CI);
1440 new StoreInst(ConstantInt::get(Type::Int8Ty,0), Ptr, CI);
1441 return ReplaceCallWith(CI, ConstantInt::get(Type::Int32Ty, 1));
1442 }
Chris Lattner175463a2005-09-24 22:17:06 +00001443 case 's': {
1444 // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
Chris Lattner34acba42007-01-07 08:12:01 +00001445 Value *Len = new CallInst(SLC.get_strlen(),
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001446 CastToCStr(CI->getOperand(3), CI),
1447 CI->getOperand(3)->getName()+".len", CI);
1448 Value *UnincLen = Len;
1449 Len = BinaryOperator::createAdd(Len, ConstantInt::get(Len->getType(), 1),
1450 Len->getName()+"1", CI);
1451 Value *MemcpyArgs[4] = {
1452 CI->getOperand(1),
1453 CastToCStr(CI->getOperand(3), CI),
1454 Len,
1455 ConstantInt::get(Type::Int32Ty, 1)
Chris Lattnerade1c2b2007-02-13 05:58:53 +00001456 };
David Greene17a5dfe2007-08-01 03:43:44 +00001457 new CallInst(SLC.get_memcpy(), MemcpyArgs, MemcpyArgs + 4, "", CI);
Chris Lattner175463a2005-09-24 22:17:06 +00001458
1459 // The strlen result is the unincremented number of bytes in the string.
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001460 if (!CI->use_empty()) {
1461 if (UnincLen->getType() != CI->getType())
1462 UnincLen = CastInst::createIntegerCast(UnincLen, CI->getType(), false,
1463 Len->getName(), CI);
1464 CI->replaceAllUsesWith(UnincLen);
Chris Lattnerf4877682005-09-25 07:06:48 +00001465 }
Chris Lattner08c0b8b32007-04-07 21:17:51 +00001466 return ReplaceCallWith(CI, 0);
Chris Lattner175463a2005-09-24 22:17:06 +00001467 }
1468 }
1469 return false;
Reid Spencer1e520fd2005-05-04 03:20:21 +00001470 }
1471} SPrintFOptimizer;
1472
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001473/// This LibCallOptimization will simplify calls to the "fputs" library
Reid Spencer93616972005-04-29 09:39:47 +00001474/// function. It looks for cases where the result of fputs is not used and the
1475/// operation can be reduced to something simpler.
Chris Lattner57179812007-04-08 07:00:35 +00001476/// @brief Simplify the fputs library function.
Chris Lattner182a9452007-04-07 21:58:02 +00001477struct VISIBILITY_HIDDEN FPutsOptimization : public LibCallOptimization {
Reid Spencer93616972005-04-29 09:39:47 +00001478public:
1479 /// @brief Default Constructor
Chris Lattner182a9452007-04-07 21:58:02 +00001480 FPutsOptimization() : LibCallOptimization("fputs",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001481 "Number of 'fputs' calls simplified") {}
Reid Spencer93616972005-04-29 09:39:47 +00001482
Reid Spencer93616972005-04-29 09:39:47 +00001483 /// @brief Make sure that the "fputs" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001484 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Reid Spencer93616972005-04-29 09:39:47 +00001485 // Just make sure this has 2 arguments
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001486 return F->arg_size() == 2;
Reid Spencer93616972005-04-29 09:39:47 +00001487 }
1488
1489 /// @brief Perform the fputs optimization.
Chris Lattner182a9452007-04-07 21:58:02 +00001490 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1491 // If the result is used, none of these optimizations work.
1492 if (!CI->use_empty())
Reid Spencer93616972005-04-29 09:39:47 +00001493 return false;
1494
1495 // All the optimizations depend on the length of the first argument and the
1496 // fact that it is a constant string array. Check that now
Chris Lattner182a9452007-04-07 21:58:02 +00001497 std::string Str;
1498 if (!GetConstantStringInfo(CI->getOperand(1), Str))
Reid Spencer93616972005-04-29 09:39:47 +00001499 return false;
1500
Chris Lattner182a9452007-04-07 21:58:02 +00001501 const Type *FILETy = CI->getOperand(2)->getType();
Chris Lattner57179812007-04-08 07:00:35 +00001502 // fputs(s,F) -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1)
1503 Value *FWriteParms[4] = {
1504 CI->getOperand(1),
1505 ConstantInt::get(SLC.getIntPtrType(), Str.size()),
1506 ConstantInt::get(SLC.getIntPtrType(), 1),
1507 CI->getOperand(2)
1508 };
David Greene17a5dfe2007-08-01 03:43:44 +00001509 new CallInst(SLC.get_fwrite(FILETy), FWriteParms, FWriteParms + 4, "", CI);
Chris Lattner182a9452007-04-07 21:58:02 +00001510 return ReplaceCallWith(CI, 0); // Known to have no uses (see above).
Reid Spencer93616972005-04-29 09:39:47 +00001511 }
Chris Lattner57179812007-04-08 07:00:35 +00001512} FPutsOptimizer;
1513
1514/// This LibCallOptimization will simplify calls to the "fwrite" function.
1515struct VISIBILITY_HIDDEN FWriteOptimization : public LibCallOptimization {
1516public:
1517 /// @brief Default Constructor
1518 FWriteOptimization() : LibCallOptimization("fwrite",
1519 "Number of 'fwrite' calls simplified") {}
1520
1521 /// @brief Make sure that the "fputs" function has the right prototype
1522 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1523 const FunctionType *FT = F->getFunctionType();
1524 return FT->getNumParams() == 4 &&
Christopher Lambedf07882007-12-17 01:12:55 +00001525 FT->getParamType(0) == PointerType::getUnqual(Type::Int8Ty) &&
Chris Lattner57179812007-04-08 07:00:35 +00001526 FT->getParamType(1) == FT->getParamType(2) &&
1527 isa<IntegerType>(FT->getParamType(1)) &&
1528 isa<PointerType>(FT->getParamType(3)) &&
1529 isa<IntegerType>(FT->getReturnType());
1530 }
1531
1532 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1533 // Get the element size and count.
1534 uint64_t EltSize, EltCount;
1535 if (ConstantInt *C = dyn_cast<ConstantInt>(CI->getOperand(2)))
1536 EltSize = C->getZExtValue();
1537 else
1538 return false;
1539 if (ConstantInt *C = dyn_cast<ConstantInt>(CI->getOperand(3)))
1540 EltCount = C->getZExtValue();
1541 else
1542 return false;
1543
1544 // If this is writing zero records, remove the call (it's a noop).
1545 if (EltSize * EltCount == 0)
1546 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
1547
1548 // If this is writing one byte, turn it into fputc.
1549 if (EltSize == 1 && EltCount == 1) {
David Greene17a5dfe2007-08-01 03:43:44 +00001550 SmallVector<Value *, 2> Args;
Chris Lattner57179812007-04-08 07:00:35 +00001551 // fwrite(s,1,1,F) -> fputc(s[0],F)
1552 Value *Ptr = CI->getOperand(1);
1553 Value *Val = new LoadInst(Ptr, Ptr->getName()+".byte", CI);
David Greene17a5dfe2007-08-01 03:43:44 +00001554 Args.push_back(new ZExtInst(Val, Type::Int32Ty, Val->getName()+".int", CI));
1555 Args.push_back(CI->getOperand(4));
Chris Lattner57179812007-04-08 07:00:35 +00001556 const Type *FILETy = CI->getOperand(4)->getType();
David Greene17a5dfe2007-08-01 03:43:44 +00001557 new CallInst(SLC.get_fputc(FILETy), Args.begin(), Args.end(), "", CI);
Chris Lattner57179812007-04-08 07:00:35 +00001558 return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1559 }
1560 return false;
1561 }
1562} FWriteOptimizer;
Reid Spencer93616972005-04-29 09:39:47 +00001563
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001564/// This LibCallOptimization will simplify calls to the "isdigit" library
Reid Spencer282d0572005-05-04 18:58:28 +00001565/// function. It simply does range checks the parameter explicitly.
1566/// @brief Simplify the isdigit library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001567struct VISIBILITY_HIDDEN isdigitOptimization : public LibCallOptimization {
Reid Spencer282d0572005-05-04 18:58:28 +00001568public:
Chris Lattner5f6035f2005-09-29 06:16:11 +00001569 isdigitOptimization() : LibCallOptimization("isdigit",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001570 "Number of 'isdigit' calls simplified") {}
Reid Spencer282d0572005-05-04 18:58:28 +00001571
Chris Lattner5f6035f2005-09-29 06:16:11 +00001572 /// @brief Make sure that the "isdigit" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001573 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
Reid Spencer282d0572005-05-04 18:58:28 +00001574 // Just make sure this has 1 argument
1575 return (f->arg_size() == 1);
1576 }
1577
1578 /// @brief Perform the toascii optimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001579 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1580 if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1))) {
Reid Spencer282d0572005-05-04 18:58:28 +00001581 // isdigit(c) -> 0 or 1, if 'c' is constant
Reid Spencere0fc4df2006-10-20 07:07:24 +00001582 uint64_t val = CI->getZExtValue();
Chris Lattner485b6412007-04-07 00:42:32 +00001583 if (val >= '0' && val <= '9')
1584 return ReplaceCallWith(ci, ConstantInt::get(Type::Int32Ty, 1));
Reid Spencer282d0572005-05-04 18:58:28 +00001585 else
Chris Lattner485b6412007-04-07 00:42:32 +00001586 return ReplaceCallWith(ci, ConstantInt::get(Type::Int32Ty, 0));
Reid Spencer282d0572005-05-04 18:58:28 +00001587 }
1588
1589 // isdigit(c) -> (unsigned)c - '0' <= 9
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001590 CastInst* cast = CastInst::createIntegerCast(ci->getOperand(1),
Reid Spencerc635f472006-12-31 05:48:39 +00001591 Type::Int32Ty, false/*ZExt*/, ci->getOperand(1)->getName()+".uint", ci);
Chris Lattner4201cd12005-08-24 17:22:17 +00001592 BinaryOperator* sub_inst = BinaryOperator::createSub(cast,
Reid Spencerc635f472006-12-31 05:48:39 +00001593 ConstantInt::get(Type::Int32Ty,0x30),
Reid Spencer282d0572005-05-04 18:58:28 +00001594 ci->getOperand(1)->getName()+".sub",ci);
Reid Spencer266e42b2006-12-23 06:05:41 +00001595 ICmpInst* setcond_inst = new ICmpInst(ICmpInst::ICMP_ULE,sub_inst,
Reid Spencerc635f472006-12-31 05:48:39 +00001596 ConstantInt::get(Type::Int32Ty,9),
Reid Spencer282d0572005-05-04 18:58:28 +00001597 ci->getOperand(1)->getName()+".cmp",ci);
Reid Spencerc635f472006-12-31 05:48:39 +00001598 CastInst* c2 = new ZExtInst(setcond_inst, Type::Int32Ty,
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001599 ci->getOperand(1)->getName()+".isdigit", ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001600 return ReplaceCallWith(ci, c2);
Reid Spencer282d0572005-05-04 18:58:28 +00001601 }
Chris Lattner5f6035f2005-09-29 06:16:11 +00001602} isdigitOptimizer;
1603
Reid Spencer557ab152007-02-05 23:32:05 +00001604struct VISIBILITY_HIDDEN isasciiOptimization : public LibCallOptimization {
Chris Lattner87ef9432005-09-29 06:17:27 +00001605public:
1606 isasciiOptimization()
1607 : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {}
1608
1609 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Chris Lattner03c49532007-01-15 02:27:26 +00001610 return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() &&
1611 F->getReturnType()->isInteger();
Chris Lattner87ef9432005-09-29 06:17:27 +00001612 }
1613
1614 /// @brief Perform the isascii optimization.
1615 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1616 // isascii(c) -> (unsigned)c < 128
1617 Value *V = CI->getOperand(1);
Reid Spencer266e42b2006-12-23 06:05:41 +00001618 Value *Cmp = new ICmpInst(ICmpInst::ICMP_ULT, V,
1619 ConstantInt::get(V->getType(), 128),
1620 V->getName()+".isascii", CI);
Chris Lattner87ef9432005-09-29 06:17:27 +00001621 if (Cmp->getType() != CI->getType())
Chris Lattnerf8a7bf32007-04-15 05:38:40 +00001622 Cmp = new ZExtInst(Cmp, CI->getType(), Cmp->getName(), CI);
Chris Lattner485b6412007-04-07 00:42:32 +00001623 return ReplaceCallWith(CI, Cmp);
Chris Lattner87ef9432005-09-29 06:17:27 +00001624 }
1625} isasciiOptimizer;
Chris Lattner5f6035f2005-09-29 06:16:11 +00001626
Reid Spencer282d0572005-05-04 18:58:28 +00001627
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001628/// This LibCallOptimization will simplify calls to the "toascii" library
Reid Spencer4c444fe2005-04-30 03:17:54 +00001629/// function. It simply does the corresponding and operation to restrict the
1630/// range of values to the ASCII character set (0-127).
1631/// @brief Simplify the toascii library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001632struct VISIBILITY_HIDDEN ToAsciiOptimization : public LibCallOptimization {
Reid Spencer4c444fe2005-04-30 03:17:54 +00001633public:
1634 /// @brief Default Constructor
Reid Spencer95d8efd2005-05-03 02:54:54 +00001635 ToAsciiOptimization() : LibCallOptimization("toascii",
Reid Spencer170ae7f2005-05-07 20:15:59 +00001636 "Number of 'toascii' calls simplified") {}
Reid Spencer4c444fe2005-04-30 03:17:54 +00001637
Reid Spencer4c444fe2005-04-30 03:17:54 +00001638 /// @brief Make sure that the "fputs" function has the right prototype
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001639 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
Reid Spencer4c444fe2005-04-30 03:17:54 +00001640 // Just make sure this has 2 arguments
1641 return (f->arg_size() == 1);
1642 }
1643
1644 /// @brief Perform the toascii optimization.
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001645 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
Reid Spencer4c444fe2005-04-30 03:17:54 +00001646 // toascii(c) -> (c & 0x7f)
Chris Lattner485b6412007-04-07 00:42:32 +00001647 Value *chr = ci->getOperand(1);
1648 Value *and_inst = BinaryOperator::createAnd(chr,
Reid Spencer4c444fe2005-04-30 03:17:54 +00001649 ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci);
Chris Lattner485b6412007-04-07 00:42:32 +00001650 return ReplaceCallWith(ci, and_inst);
Reid Spencer4c444fe2005-04-30 03:17:54 +00001651 }
1652} ToAsciiOptimizer;
1653
Reid Spencerb195fcd2005-05-14 16:42:52 +00001654/// This LibCallOptimization will simplify calls to the "ffs" library
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001655/// calls which find the first set bit in an int, long, or long long. The
Reid Spencerb195fcd2005-05-14 16:42:52 +00001656/// optimization is to compute the result at compile time if the argument is
1657/// a constant.
1658/// @brief Simplify the ffs library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001659struct VISIBILITY_HIDDEN FFSOptimization : public LibCallOptimization {
Reid Spencerb195fcd2005-05-14 16:42:52 +00001660protected:
1661 /// @brief Subclass Constructor
1662 FFSOptimization(const char* funcName, const char* description)
Chris Lattner801f4752006-01-17 18:27:17 +00001663 : LibCallOptimization(funcName, description) {}
Reid Spencerb195fcd2005-05-14 16:42:52 +00001664
1665public:
1666 /// @brief Default Constructor
1667 FFSOptimization() : LibCallOptimization("ffs",
1668 "Number of 'ffs' calls simplified") {}
1669
Chris Lattner801f4752006-01-17 18:27:17 +00001670 /// @brief Make sure that the "ffs" function has the right prototype
1671 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
Reid Spencerb195fcd2005-05-14 16:42:52 +00001672 // Just make sure this has 2 arguments
Reid Spencerc635f472006-12-31 05:48:39 +00001673 return F->arg_size() == 1 && F->getReturnType() == Type::Int32Ty;
Reid Spencerb195fcd2005-05-14 16:42:52 +00001674 }
1675
1676 /// @brief Perform the ffs optimization.
Chris Lattner801f4752006-01-17 18:27:17 +00001677 virtual bool OptimizeCall(CallInst *TheCall, SimplifyLibCalls &SLC) {
1678 if (ConstantInt *CI = dyn_cast<ConstantInt>(TheCall->getOperand(1))) {
Reid Spencerb195fcd2005-05-14 16:42:52 +00001679 // ffs(cnst) -> bit#
1680 // ffsl(cnst) -> bit#
Reid Spencer17f77842005-05-15 21:19:45 +00001681 // ffsll(cnst) -> bit#
Reid Spencere0fc4df2006-10-20 07:07:24 +00001682 uint64_t val = CI->getZExtValue();
Reid Spencer17f77842005-05-15 21:19:45 +00001683 int result = 0;
Chris Lattner801f4752006-01-17 18:27:17 +00001684 if (val) {
1685 ++result;
1686 while ((val & 1) == 0) {
1687 ++result;
1688 val >>= 1;
1689 }
Reid Spencer17f77842005-05-15 21:19:45 +00001690 }
Chris Lattner485b6412007-04-07 00:42:32 +00001691 return ReplaceCallWith(TheCall, ConstantInt::get(Type::Int32Ty, result));
Reid Spencerb195fcd2005-05-14 16:42:52 +00001692 }
Reid Spencer17f77842005-05-15 21:19:45 +00001693
Chris Lattner801f4752006-01-17 18:27:17 +00001694 // ffs(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1695 // ffsl(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1696 // ffsll(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1697 const Type *ArgType = TheCall->getOperand(1)->getType();
Chris Lattner801f4752006-01-17 18:27:17 +00001698 const char *CTTZName;
Reid Spencer7a9c62b2007-01-12 07:05:14 +00001699 assert(ArgType->getTypeID() == Type::IntegerTyID &&
1700 "llvm.cttz argument is not an integer?");
1701 unsigned BitWidth = cast<IntegerType>(ArgType)->getBitWidth();
Chris Lattner3b6058c2007-01-12 22:49:11 +00001702 if (BitWidth == 8)
Reid Spencer7a9c62b2007-01-12 07:05:14 +00001703 CTTZName = "llvm.cttz.i8";
Chris Lattner3b6058c2007-01-12 22:49:11 +00001704 else if (BitWidth == 16)
Reid Spencer7a9c62b2007-01-12 07:05:14 +00001705 CTTZName = "llvm.cttz.i16";
Chris Lattner3b6058c2007-01-12 22:49:11 +00001706 else if (BitWidth == 32)
Reid Spencer7a9c62b2007-01-12 07:05:14 +00001707 CTTZName = "llvm.cttz.i32";
Chris Lattner3b6058c2007-01-12 22:49:11 +00001708 else {
1709 assert(BitWidth == 64 && "Unknown bitwidth");
Reid Spencer7a9c62b2007-01-12 07:05:14 +00001710 CTTZName = "llvm.cttz.i64";
Chris Lattner3b6058c2007-01-12 22:49:11 +00001711 }
Chris Lattner801f4752006-01-17 18:27:17 +00001712
Chris Lattner34acba42007-01-07 08:12:01 +00001713 Constant *F = SLC.getModule()->getOrInsertFunction(CTTZName, ArgType,
Chris Lattner801f4752006-01-17 18:27:17 +00001714 ArgType, NULL);
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001715 Value *V = CastInst::createIntegerCast(TheCall->getOperand(1), ArgType,
1716 false/*ZExt*/, "tmp", TheCall);
Chris Lattner801f4752006-01-17 18:27:17 +00001717 Value *V2 = new CallInst(F, V, "tmp", TheCall);
Reid Spencerc635f472006-12-31 05:48:39 +00001718 V2 = CastInst::createIntegerCast(V2, Type::Int32Ty, false/*ZExt*/,
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001719 "tmp", TheCall);
Reid Spencerc635f472006-12-31 05:48:39 +00001720 V2 = BinaryOperator::createAdd(V2, ConstantInt::get(Type::Int32Ty, 1),
Chris Lattner801f4752006-01-17 18:27:17 +00001721 "tmp", TheCall);
Reid Spencer266e42b2006-12-23 06:05:41 +00001722 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, V,
1723 Constant::getNullValue(V->getType()), "tmp",
1724 TheCall);
Reid Spencerc635f472006-12-31 05:48:39 +00001725 V2 = new SelectInst(Cond, ConstantInt::get(Type::Int32Ty, 0), V2,
Chris Lattner801f4752006-01-17 18:27:17 +00001726 TheCall->getName(), TheCall);
Chris Lattner485b6412007-04-07 00:42:32 +00001727 return ReplaceCallWith(TheCall, V2);
Reid Spencerb195fcd2005-05-14 16:42:52 +00001728 }
1729} FFSOptimizer;
1730
1731/// This LibCallOptimization will simplify calls to the "ffsl" library
1732/// calls. It simply uses FFSOptimization for which the transformation is
1733/// identical.
1734/// @brief Simplify the ffsl library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001735struct VISIBILITY_HIDDEN FFSLOptimization : public FFSOptimization {
Reid Spencerb195fcd2005-05-14 16:42:52 +00001736public:
1737 /// @brief Default Constructor
1738 FFSLOptimization() : FFSOptimization("ffsl",
1739 "Number of 'ffsl' calls simplified") {}
1740
1741} FFSLOptimizer;
1742
1743/// This LibCallOptimization will simplify calls to the "ffsll" library
1744/// calls. It simply uses FFSOptimization for which the transformation is
1745/// identical.
1746/// @brief Simplify the ffsl library function.
Reid Spencer557ab152007-02-05 23:32:05 +00001747struct VISIBILITY_HIDDEN FFSLLOptimization : public FFSOptimization {
Reid Spencerb195fcd2005-05-14 16:42:52 +00001748public:
1749 /// @brief Default Constructor
1750 FFSLLOptimization() : FFSOptimization("ffsll",
1751 "Number of 'ffsll' calls simplified") {}
1752
1753} FFSLLOptimizer;
1754
Chris Lattner57a28632006-01-23 05:57:36 +00001755/// This optimizes unary functions that take and return doubles.
1756struct UnaryDoubleFPOptimizer : public LibCallOptimization {
1757 UnaryDoubleFPOptimizer(const char *Fn, const char *Desc)
1758 : LibCallOptimization(Fn, Desc) {}
Chris Lattner4201cd12005-08-24 17:22:17 +00001759
Chris Lattner57a28632006-01-23 05:57:36 +00001760 // Make sure that this function has the right prototype
Chris Lattner4201cd12005-08-24 17:22:17 +00001761 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1762 return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy &&
1763 F->getReturnType() == Type::DoubleTy;
1764 }
Chris Lattner57a28632006-01-23 05:57:36 +00001765
1766 /// ShrinkFunctionToFloatVersion - If the input to this function is really a
1767 /// float, strength reduce this to a float version of the function,
1768 /// e.g. floor((double)FLT) -> (double)floorf(FLT). This can only be called
1769 /// when the target supports the destination function and where there can be
1770 /// no precision loss.
1771 static bool ShrinkFunctionToFloatVersion(CallInst *CI, SimplifyLibCalls &SLC,
Chris Lattner34acba42007-01-07 08:12:01 +00001772 Constant *(SimplifyLibCalls::*FP)()){
Chris Lattner485b6412007-04-07 00:42:32 +00001773 if (FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1)))
Chris Lattner4201cd12005-08-24 17:22:17 +00001774 if (Cast->getOperand(0)->getType() == Type::FloatTy) {
Chris Lattner57a28632006-01-23 05:57:36 +00001775 Value *New = new CallInst((SLC.*FP)(), Cast->getOperand(0),
Chris Lattner4201cd12005-08-24 17:22:17 +00001776 CI->getName(), CI);
Reid Spencer6c38f0b2006-11-27 01:05:10 +00001777 New = new FPExtInst(New, Type::DoubleTy, CI->getName(), CI);
Chris Lattner4201cd12005-08-24 17:22:17 +00001778 CI->replaceAllUsesWith(New);
1779 CI->eraseFromParent();
1780 if (Cast->use_empty())
1781 Cast->eraseFromParent();
1782 return true;
1783 }
Chris Lattner57a28632006-01-23 05:57:36 +00001784 return false;
Chris Lattner4201cd12005-08-24 17:22:17 +00001785 }
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001786};
1787
Chris Lattner57a28632006-01-23 05:57:36 +00001788
Reid Spencer557ab152007-02-05 23:32:05 +00001789struct VISIBILITY_HIDDEN FloorOptimization : public UnaryDoubleFPOptimizer {
Chris Lattner57a28632006-01-23 05:57:36 +00001790 FloorOptimization()
1791 : UnaryDoubleFPOptimizer("floor", "Number of 'floor' calls simplified") {}
1792
1793 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001794#ifdef HAVE_FLOORF
Chris Lattner57a28632006-01-23 05:57:36 +00001795 // If this is a float argument passed in, convert to floorf.
1796 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_floorf))
1797 return true;
Reid Spencerade18212006-01-19 08:36:56 +00001798#endif
Chris Lattner57a28632006-01-23 05:57:36 +00001799 return false; // opt failed
1800 }
1801} FloorOptimizer;
Chris Lattner4201cd12005-08-24 17:22:17 +00001802
Reid Spencer557ab152007-02-05 23:32:05 +00001803struct VISIBILITY_HIDDEN CeilOptimization : public UnaryDoubleFPOptimizer {
Chris Lattner57740402006-01-23 06:24:46 +00001804 CeilOptimization()
1805 : UnaryDoubleFPOptimizer("ceil", "Number of 'ceil' calls simplified") {}
1806
1807 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1808#ifdef HAVE_CEILF
1809 // If this is a float argument passed in, convert to ceilf.
1810 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_ceilf))
1811 return true;
1812#endif
1813 return false; // opt failed
1814 }
1815} CeilOptimizer;
Chris Lattner4201cd12005-08-24 17:22:17 +00001816
Reid Spencer557ab152007-02-05 23:32:05 +00001817struct VISIBILITY_HIDDEN RoundOptimization : public UnaryDoubleFPOptimizer {
Chris Lattner57740402006-01-23 06:24:46 +00001818 RoundOptimization()
1819 : UnaryDoubleFPOptimizer("round", "Number of 'round' calls simplified") {}
1820
1821 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1822#ifdef HAVE_ROUNDF
1823 // If this is a float argument passed in, convert to roundf.
1824 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_roundf))
1825 return true;
1826#endif
1827 return false; // opt failed
1828 }
1829} RoundOptimizer;
1830
Reid Spencer557ab152007-02-05 23:32:05 +00001831struct VISIBILITY_HIDDEN RintOptimization : public UnaryDoubleFPOptimizer {
Chris Lattner57740402006-01-23 06:24:46 +00001832 RintOptimization()
1833 : UnaryDoubleFPOptimizer("rint", "Number of 'rint' calls simplified") {}
1834
1835 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1836#ifdef HAVE_RINTF
1837 // If this is a float argument passed in, convert to rintf.
1838 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_rintf))
1839 return true;
1840#endif
1841 return false; // opt failed
1842 }
1843} RintOptimizer;
1844
Reid Spencer557ab152007-02-05 23:32:05 +00001845struct VISIBILITY_HIDDEN NearByIntOptimization : public UnaryDoubleFPOptimizer {
Chris Lattner57740402006-01-23 06:24:46 +00001846 NearByIntOptimization()
1847 : UnaryDoubleFPOptimizer("nearbyint",
1848 "Number of 'nearbyint' calls simplified") {}
1849
1850 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1851#ifdef HAVE_NEARBYINTF
1852 // If this is a float argument passed in, convert to nearbyintf.
1853 if (ShrinkFunctionToFloatVersion(CI, SLC,&SimplifyLibCalls::get_nearbyintf))
1854 return true;
1855#endif
1856 return false; // opt failed
1857 }
1858} NearByIntOptimizer;
Chris Lattner4201cd12005-08-24 17:22:17 +00001859
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001860/// GetConstantStringInfo - This function computes the length of a
1861/// null-terminated constant array of integers. This function can't rely on the
1862/// size of the constant array because there could be a null terminator in the
1863/// middle of the array.
1864///
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001865/// We also have to bail out if we find a non-integer constant initializer
1866/// of one of the elements or if there is no null-terminator. The logic
Reid Spencer7ddcfb32005-04-27 21:29:20 +00001867/// below checks each of these conditions and will return true only if all
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001868/// conditions are met. If the conditions aren't met, this returns false.
1869///
1870/// If successful, the \p Array param is set to the constant array being
1871/// indexed, the \p Length parameter is set to the length of the null-terminated
1872/// string pointed to by V, the \p StartIdx value is set to the first
1873/// element of the Array that V points to, and true is returned.
Chris Lattner182a9452007-04-07 21:58:02 +00001874static bool GetConstantStringInfo(Value *V, std::string &Str) {
1875 // Look through noop bitcast instructions.
1876 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1877 if (BCI->getType() == BCI->getOperand(0)->getType())
1878 return GetConstantStringInfo(BCI->getOperand(0), Str);
1879 return false;
1880 }
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001881
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001882 // If the value is not a GEP instruction nor a constant expression with a
1883 // GEP instruction, then return false because ConstantArray can't occur
Reid Spencere249a822005-04-27 07:54:40 +00001884 // any other way
Chris Lattner182a9452007-04-07 21:58:02 +00001885 User *GEP = 0;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001886 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) {
Reid Spencere249a822005-04-27 07:54:40 +00001887 GEP = GEPI;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001888 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
1889 if (CE->getOpcode() != Instruction::GetElementPtr)
Reid Spencere249a822005-04-27 07:54:40 +00001890 return false;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001891 GEP = CE;
1892 } else {
Reid Spencere249a822005-04-27 07:54:40 +00001893 return false;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001894 }
Reid Spencere249a822005-04-27 07:54:40 +00001895
1896 // Make sure the GEP has exactly three arguments.
1897 if (GEP->getNumOperands() != 3)
1898 return false;
1899
1900 // Check to make sure that the first operand of the GEP is an integer and
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001901 // has value 0 so that we are sure we're indexing into the initializer.
Chris Lattner182a9452007-04-07 21:58:02 +00001902 if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
1903 if (!Idx->isZero())
Reid Spencere249a822005-04-27 07:54:40 +00001904 return false;
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001905 } else
Reid Spencere249a822005-04-27 07:54:40 +00001906 return false;
1907
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001908 // If the second index isn't a ConstantInt, then this is a variable index
1909 // into the array. If this occurs, we can't say anything meaningful about
1910 // the string.
Chris Lattner182a9452007-04-07 21:58:02 +00001911 uint64_t StartIdx = 0;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001912 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
1913 StartIdx = CI->getZExtValue();
Reid Spencere249a822005-04-27 07:54:40 +00001914 else
1915 return false;
1916
1917 // The GEP instruction, constant or instruction, must reference a global
1918 // variable that is a constant and is initialized. The referenced constant
1919 // initializer is the array that we'll use for optimization.
1920 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
1921 if (!GV || !GV->isConstant() || !GV->hasInitializer())
1922 return false;
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001923 Constant *GlobalInit = GV->getInitializer();
Reid Spencere249a822005-04-27 07:54:40 +00001924
1925 // Handle the ConstantAggregateZero case
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001926 if (isa<ConstantAggregateZero>(GlobalInit)) {
Reid Spencere249a822005-04-27 07:54:40 +00001927 // This is a degenerate case. The initializer is constant zero so the
1928 // length of the string must be zero.
Chris Lattner182a9452007-04-07 21:58:02 +00001929 Str.clear();
Reid Spencere249a822005-04-27 07:54:40 +00001930 return true;
1931 }
1932
1933 // Must be a Constant Array
Chris Lattner182a9452007-04-07 21:58:02 +00001934 ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit);
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001935 if (!Array) return false;
Reid Spencere249a822005-04-27 07:54:40 +00001936
1937 // Get the number of elements in the array
Chris Lattner9b2b8ab2007-04-06 22:54:17 +00001938 uint64_t NumElts = Array->getType()->getNumElements();
Reid Spencere249a822005-04-27 07:54:40 +00001939
Chris Lattner182a9452007-04-07 21:58:02 +00001940 // Traverse the constant array from StartIdx (derived above) which is
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001941 // the place the GEP refers to in the array.
Chris Lattner182a9452007-04-07 21:58:02 +00001942 for (unsigned i = StartIdx; i < NumElts; ++i) {
1943 Constant *Elt = Array->getOperand(i);
1944 ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
1945 if (!CI) // This array isn't suitable, non-int initializer.
1946 return false;
1947 if (CI->isZero())
1948 return true; // we found end of string, success!
1949 Str += (char)CI->getZExtValue();
Reid Spencere249a822005-04-27 07:54:40 +00001950 }
Chris Lattner0d4ebfc2006-01-22 22:35:08 +00001951
Chris Lattner182a9452007-04-07 21:58:02 +00001952 return false; // The array isn't null terminated.
Reid Spencere249a822005-04-27 07:54:40 +00001953}
1954
Reid Spencera7828ba2005-06-18 17:46:28 +00001955/// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*,
1956/// inserting the cast before IP, and return the cast.
1957/// @brief Cast a value to a "C" string.
Chris Lattnerbed184c2007-04-07 21:04:50 +00001958static Value *CastToCStr(Value *V, Instruction *IP) {
Reid Spencera730cf82006-12-13 08:04:32 +00001959 assert(isa<PointerType>(V->getType()) &&
Reid Spencerbfe26ff2006-12-13 00:50:17 +00001960 "Can't cast non-pointer type to C string type");
Christopher Lambedf07882007-12-17 01:12:55 +00001961 const Type *SBPTy = PointerType::getUnqual(Type::Int8Ty);
Reid Spencera7828ba2005-06-18 17:46:28 +00001962 if (V->getType() != SBPTy)
Chris Lattnerbed184c2007-04-07 21:04:50 +00001963 return new BitCastInst(V, SBPTy, V->getName(), IP);
Reid Spencera7828ba2005-06-18 17:46:28 +00001964 return V;
1965}
1966
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001967// TODO:
Reid Spencer649ac282005-04-28 04:40:06 +00001968// Additional cases that we need to add to this file:
1969//
Reid Spencer649ac282005-04-28 04:40:06 +00001970// cbrt:
Reid Spencer649ac282005-04-28 04:40:06 +00001971// * cbrt(expN(X)) -> expN(x/3)
1972// * cbrt(sqrt(x)) -> pow(x,1/6)
1973// * cbrt(sqrt(x)) -> pow(x,1/9)
1974//
Reid Spencer649ac282005-04-28 04:40:06 +00001975// cos, cosf, cosl:
Reid Spencer16983ca2005-04-28 18:05:16 +00001976// * cos(-x) -> cos(x)
Reid Spencer649ac282005-04-28 04:40:06 +00001977//
1978// exp, expf, expl:
Reid Spencer649ac282005-04-28 04:40:06 +00001979// * exp(log(x)) -> x
1980//
Reid Spencer649ac282005-04-28 04:40:06 +00001981// log, logf, logl:
Reid Spencer649ac282005-04-28 04:40:06 +00001982// * log(exp(x)) -> x
1983// * log(x**y) -> y*log(x)
1984// * log(exp(y)) -> y*log(e)
1985// * log(exp2(y)) -> y*log(2)
1986// * log(exp10(y)) -> y*log(10)
1987// * log(sqrt(x)) -> 0.5*log(x)
1988// * log(pow(x,y)) -> y*log(x)
1989//
1990// lround, lroundf, lroundl:
1991// * lround(cnst) -> cnst'
1992//
1993// memcmp:
Reid Spencer649ac282005-04-28 04:40:06 +00001994// * memcmp(x,y,l) -> cnst
1995// (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
Reid Spencer649ac282005-04-28 04:40:06 +00001996//
Reid Spencer649ac282005-04-28 04:40:06 +00001997// memmove:
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001998// * memmove(d,s,l,a) -> memcpy(d,s,l,a)
Reid Spencer649ac282005-04-28 04:40:06 +00001999// (if s is a global constant array)
2000//
Reid Spencer649ac282005-04-28 04:40:06 +00002001// pow, powf, powl:
Reid Spencer649ac282005-04-28 04:40:06 +00002002// * pow(exp(x),y) -> exp(x*y)
2003// * pow(sqrt(x),y) -> pow(x,y*0.5)
2004// * pow(pow(x,y),z)-> pow(x,y*z)
2005//
2006// puts:
Chris Lattner49fa8d22007-04-14 01:17:48 +00002007// * puts("") -> putchar("\n")
Reid Spencer649ac282005-04-28 04:40:06 +00002008//
2009// round, roundf, roundl:
2010// * round(cnst) -> cnst'
2011//
2012// signbit:
2013// * signbit(cnst) -> cnst'
2014// * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2015//
Reid Spencer649ac282005-04-28 04:40:06 +00002016// sqrt, sqrtf, sqrtl:
Reid Spencer649ac282005-04-28 04:40:06 +00002017// * sqrt(expN(x)) -> expN(x*0.5)
2018// * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2019// * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2020//
Reid Spencer170ae7f2005-05-07 20:15:59 +00002021// stpcpy:
2022// * stpcpy(str, "literal") ->
2023// llvm.memcpy(str,"literal",strlen("literal")+1,1)
Reid Spencer38cabd72005-05-03 07:23:44 +00002024// strrchr:
Reid Spencer649ac282005-04-28 04:40:06 +00002025// * strrchr(s,c) -> reverse_offset_of_in(c,s)
2026// (if c is a constant integer and s is a constant string)
2027// * strrchr(s1,0) -> strchr(s1,0)
2028//
Reid Spencer649ac282005-04-28 04:40:06 +00002029// strncat:
2030// * strncat(x,y,0) -> x
2031// * strncat(x,y,0) -> x (if strlen(y) = 0)
2032// * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y))
2033//
Reid Spencer649ac282005-04-28 04:40:06 +00002034// strncpy:
2035// * strncpy(d,s,0) -> d
2036// * strncpy(d,s,l) -> memcpy(d,s,l,1)
2037// (if s and l are constants)
2038//
2039// strpbrk:
2040// * strpbrk(s,a) -> offset_in_for(s,a)
2041// (if s and a are both constant strings)
2042// * strpbrk(s,"") -> 0
2043// * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
2044//
2045// strspn, strcspn:
2046// * strspn(s,a) -> const_int (if both args are constant)
2047// * strspn("",a) -> 0
2048// * strspn(s,"") -> 0
2049// * strcspn(s,a) -> const_int (if both args are constant)
2050// * strcspn("",a) -> 0
2051// * strcspn(s,"") -> strlen(a)
2052//
2053// strstr:
2054// * strstr(x,x) -> x
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00002055// * strstr(s1,s2) -> offset_of_s2_in(s1)
Reid Spencer649ac282005-04-28 04:40:06 +00002056// (if s1 and s2 are constant strings)
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00002057//
Reid Spencer649ac282005-04-28 04:40:06 +00002058// tan, tanf, tanl:
Reid Spencer649ac282005-04-28 04:40:06 +00002059// * tan(atan(x)) -> x
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00002060//
Reid Spencer649ac282005-04-28 04:40:06 +00002061// trunc, truncf, truncl:
2062// * trunc(cnst) -> cnst'
2063//
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00002064//
Reid Spencer39a762d2005-04-25 02:53:12 +00002065}