LLVM API Documentation

SimplifyLibCalls.cpp

Go to the documentation of this file.
00001 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Reid Spencer and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a module pass that applies a variety of small
00011 // optimizations for calls to specific well-known function calls (e.g. runtime
00012 // library functions). For example, a call to the function "exit(3)" that
00013 // occurs within the main() function can be transformed into a simple "return 3"
00014 // instruction. Any optimization that takes this form (replace call to library
00015 // function with simpler code that provides the same result) belongs in this
00016 // file.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "simplify-libcalls"
00021 #include "llvm/Constants.h"
00022 #include "llvm/DerivedTypes.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/Module.h"
00025 #include "llvm/Pass.h"
00026 #include "llvm/ADT/hash_map"
00027 #include "llvm/ADT/Statistic.h"
00028 #include "llvm/Config/config.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/Target/TargetData.h"
00031 #include "llvm/Transforms/IPO.h"
00032 using namespace llvm;
00033 
00034 namespace {
00035 
00036 /// This statistic keeps track of the total number of library calls that have
00037 /// been simplified regardless of which call it is.
00038 Statistic<> SimplifiedLibCalls("simplify-libcalls",
00039   "Number of library calls simplified");
00040 
00041 // Forward declarations
00042 class LibCallOptimization;
00043 class SimplifyLibCalls;
00044 
00045 /// This list is populated by the constructor for LibCallOptimization class.
00046 /// Therefore all subclasses are registered here at static initialization time
00047 /// and this list is what the SimplifyLibCalls pass uses to apply the individual
00048 /// optimizations to the call sites.
00049 /// @brief The list of optimizations deriving from LibCallOptimization
00050 static LibCallOptimization *OptList = 0;
00051 
00052 /// This class is the abstract base class for the set of optimizations that
00053 /// corresponds to one library call. The SimplifyLibCalls pass will call the
00054 /// ValidateCalledFunction method to ask the optimization if a given Function
00055 /// is the kind that the optimization can handle. If the subclass returns true,
00056 /// then SImplifyLibCalls will also call the OptimizeCall method to perform,
00057 /// or attempt to perform, the optimization(s) for the library call. Otherwise,
00058 /// OptimizeCall won't be called. Subclasses are responsible for providing the
00059 /// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization
00060 /// constructor. This is used to efficiently select which call instructions to
00061 /// optimize. The criteria for a "lib call" is "anything with well known
00062 /// semantics", typically a library function that is defined by an international
00063 /// standard. Because the semantics are well known, the optimizations can
00064 /// generally short-circuit actually calling the function if there's a simpler
00065 /// way (e.g. strlen(X) can be reduced to a constant if X is a constant global).
00066 /// @brief Base class for library call optimizations
00067 class LibCallOptimization {
00068   LibCallOptimization **Prev, *Next;
00069   const char *FunctionName; ///< Name of the library call we optimize
00070 #ifndef NDEBUG
00071   Statistic<> occurrences; ///< debug statistic (-debug-only=simplify-libcalls)
00072 #endif
00073 public:
00074   /// The \p fname argument must be the name of the library function being
00075   /// optimized by the subclass.
00076   /// @brief Constructor that registers the optimization.
00077   LibCallOptimization(const char *FName, const char *Description)
00078     : FunctionName(FName)
00079 #ifndef NDEBUG
00080     , occurrences("simplify-libcalls", Description)
00081 #endif
00082   {
00083     // Register this optimizer in the list of optimizations.
00084     Next = OptList;
00085     OptList = this;
00086     Prev = &OptList;
00087     if (Next) Next->Prev = &Next;
00088   }
00089   
00090   /// getNext - All libcall optimizations are chained together into a list,
00091   /// return the next one in the list.
00092   LibCallOptimization *getNext() { return Next; }
00093 
00094   /// @brief Deregister from the optlist
00095   virtual ~LibCallOptimization() {
00096     *Prev = Next;
00097     if (Next) Next->Prev = Prev;
00098   }
00099 
00100   /// The implementation of this function in subclasses should determine if
00101   /// \p F is suitable for the optimization. This method is called by
00102   /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
00103   /// sites of such a function if that function is not suitable in the first
00104   /// place.  If the called function is suitabe, this method should return true;
00105   /// false, otherwise. This function should also perform any lazy
00106   /// initialization that the LibCallOptimization needs to do, if its to return
00107   /// true. This avoids doing initialization until the optimizer is actually
00108   /// going to be called upon to do some optimization.
00109   /// @brief Determine if the function is suitable for optimization
00110   virtual bool ValidateCalledFunction(
00111     const Function* F,    ///< The function that is the target of call sites
00112     SimplifyLibCalls& SLC ///< The pass object invoking us
00113   ) = 0;
00114 
00115   /// The implementations of this function in subclasses is the heart of the
00116   /// SimplifyLibCalls algorithm. Sublcasses of this class implement
00117   /// OptimizeCall to determine if (a) the conditions are right for optimizing
00118   /// the call and (b) to perform the optimization. If an action is taken
00119   /// against ci, the subclass is responsible for returning true and ensuring
00120   /// that ci is erased from its parent.
00121   /// @brief Optimize a call, if possible.
00122   virtual bool OptimizeCall(
00123     CallInst* ci,          ///< The call instruction that should be optimized.
00124     SimplifyLibCalls& SLC  ///< The pass object invoking us
00125   ) = 0;
00126 
00127   /// @brief Get the name of the library call being optimized
00128   const char *getFunctionName() const { return FunctionName; }
00129 
00130   /// @brief Called by SimplifyLibCalls to update the occurrences statistic.
00131   void succeeded() {
00132 #ifndef NDEBUG
00133     DEBUG(++occurrences);
00134 #endif
00135   }
00136 };
00137 
00138 /// This class is an LLVM Pass that applies each of the LibCallOptimization
00139 /// instances to all the call sites in a module, relatively efficiently. The
00140 /// purpose of this pass is to provide optimizations for calls to well-known
00141 /// functions with well-known semantics, such as those in the c library. The
00142 /// class provides the basic infrastructure for handling runOnModule.  Whenever
00143 /// this pass finds a function call, it asks the appropriate optimizer to
00144 /// validate the call (ValidateLibraryCall). If it is validated, then
00145 /// the OptimizeCall method is also called.
00146 /// @brief A ModulePass for optimizing well-known function calls.
00147 class SimplifyLibCalls : public ModulePass {
00148 public:
00149   /// We need some target data for accurate signature details that are
00150   /// target dependent. So we require target data in our AnalysisUsage.
00151   /// @brief Require TargetData from AnalysisUsage.
00152   virtual void getAnalysisUsage(AnalysisUsage& Info) const {
00153     // Ask that the TargetData analysis be performed before us so we can use
00154     // the target data.
00155     Info.addRequired<TargetData>();
00156   }
00157 
00158   /// For this pass, process all of the function calls in the module, calling
00159   /// ValidateLibraryCall and OptimizeCall as appropriate.
00160   /// @brief Run all the lib call optimizations on a Module.
00161   virtual bool runOnModule(Module &M) {
00162     reset(M);
00163 
00164     bool result = false;
00165     hash_map<std::string, LibCallOptimization*> OptznMap;
00166     for (LibCallOptimization *Optzn = OptList; Optzn; Optzn = Optzn->getNext())
00167       OptznMap[Optzn->getFunctionName()] = Optzn;
00168 
00169     // The call optimizations can be recursive. That is, the optimization might
00170     // generate a call to another function which can also be optimized. This way
00171     // we make the LibCallOptimization instances very specific to the case they
00172     // handle. It also means we need to keep running over the function calls in
00173     // the module until we don't get any more optimizations possible.
00174     bool found_optimization = false;
00175     do {
00176       found_optimization = false;
00177       for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
00178         // All the "well-known" functions are external and have external linkage
00179         // because they live in a runtime library somewhere and were (probably)
00180         // not compiled by LLVM.  So, we only act on external functions that
00181         // have external linkage and non-empty uses.
00182         if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
00183           continue;
00184 
00185         // Get the optimization class that pertains to this function
00186         hash_map<std::string, LibCallOptimization*>::iterator OMI =
00187           OptznMap.find(FI->getName());
00188         if (OMI == OptznMap.end()) continue;
00189         
00190         LibCallOptimization *CO = OMI->second;
00191 
00192         // Make sure the called function is suitable for the optimization
00193         if (!CO->ValidateCalledFunction(FI, *this))
00194           continue;
00195 
00196         // Loop over each of the uses of the function
00197         for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
00198              UI != UE ; ) {
00199           // If the use of the function is a call instruction
00200           if (CallInst* CI = dyn_cast<CallInst>(*UI++)) {
00201             // Do the optimization on the LibCallOptimization.
00202             if (CO->OptimizeCall(CI, *this)) {
00203               ++SimplifiedLibCalls;
00204               found_optimization = result = true;
00205               CO->succeeded();
00206             }
00207           }
00208         }
00209       }
00210     } while (found_optimization);
00211     
00212     return result;
00213   }
00214 
00215   /// @brief Return the *current* module we're working on.
00216   Module* getModule() const { return M; }
00217 
00218   /// @brief Return the *current* target data for the module we're working on.
00219   TargetData* getTargetData() const { return TD; }
00220 
00221   /// @brief Return the size_t type -- syntactic shortcut
00222   const Type* getIntPtrType() const { return TD->getIntPtrType(); }
00223 
00224   /// @brief Return a Function* for the putchar libcall
00225   Function* get_putchar() {
00226     if (!putchar_func)
00227       putchar_func = M->getOrInsertFunction("putchar", Type::IntTy, Type::IntTy,
00228                                             NULL);
00229     return putchar_func;
00230   }
00231 
00232   /// @brief Return a Function* for the puts libcall
00233   Function* get_puts() {
00234     if (!puts_func)
00235       puts_func = M->getOrInsertFunction("puts", Type::IntTy,
00236                                          PointerType::get(Type::SByteTy),
00237                                          NULL);
00238     return puts_func;
00239   }
00240 
00241   /// @brief Return a Function* for the fputc libcall
00242   Function* get_fputc(const Type* FILEptr_type) {
00243     if (!fputc_func)
00244       fputc_func = M->getOrInsertFunction("fputc", Type::IntTy, Type::IntTy,
00245                                           FILEptr_type, NULL);
00246     return fputc_func;
00247   }
00248 
00249   /// @brief Return a Function* for the fputs libcall
00250   Function* get_fputs(const Type* FILEptr_type) {
00251     if (!fputs_func)
00252       fputs_func = M->getOrInsertFunction("fputs", Type::IntTy,
00253                                           PointerType::get(Type::SByteTy),
00254                                           FILEptr_type, NULL);
00255     return fputs_func;
00256   }
00257 
00258   /// @brief Return a Function* for the fwrite libcall
00259   Function* get_fwrite(const Type* FILEptr_type) {
00260     if (!fwrite_func)
00261       fwrite_func = M->getOrInsertFunction("fwrite", TD->getIntPtrType(),
00262                                            PointerType::get(Type::SByteTy),
00263                                            TD->getIntPtrType(),
00264                                            TD->getIntPtrType(),
00265                                            FILEptr_type, NULL);
00266     return fwrite_func;
00267   }
00268 
00269   /// @brief Return a Function* for the sqrt libcall
00270   Function* get_sqrt() {
00271     if (!sqrt_func)
00272       sqrt_func = M->getOrInsertFunction("sqrt", Type::DoubleTy, 
00273                                          Type::DoubleTy, NULL);
00274     return sqrt_func;
00275   }
00276 
00277   /// @brief Return a Function* for the strlen libcall
00278   Function* get_strcpy() {
00279     if (!strcpy_func)
00280       strcpy_func = M->getOrInsertFunction("strcpy",
00281                                            PointerType::get(Type::SByteTy),
00282                                            PointerType::get(Type::SByteTy),
00283                                            PointerType::get(Type::SByteTy),
00284                                            NULL);
00285     return strcpy_func;
00286   }
00287 
00288   /// @brief Return a Function* for the strlen libcall
00289   Function* get_strlen() {
00290     if (!strlen_func)
00291       strlen_func = M->getOrInsertFunction("strlen", TD->getIntPtrType(),
00292                                            PointerType::get(Type::SByteTy),
00293                                            NULL);
00294     return strlen_func;
00295   }
00296 
00297   /// @brief Return a Function* for the memchr libcall
00298   Function* get_memchr() {
00299     if (!memchr_func)
00300       memchr_func = M->getOrInsertFunction("memchr",
00301                                            PointerType::get(Type::SByteTy),
00302                                            PointerType::get(Type::SByteTy),
00303                                            Type::IntTy, TD->getIntPtrType(),
00304                                            NULL);
00305     return memchr_func;
00306   }
00307 
00308   /// @brief Return a Function* for the memcpy libcall
00309   Function* get_memcpy() {
00310     if (!memcpy_func) {
00311       const Type *SBP = PointerType::get(Type::SByteTy);
00312       const char *N = TD->getIntPtrType() == Type::UIntTy ?
00313                             "llvm.memcpy.i32" : "llvm.memcpy.i64";
00314       memcpy_func = M->getOrInsertFunction(N, Type::VoidTy, SBP, SBP,
00315                                            TD->getIntPtrType(), Type::UIntTy,
00316                                            NULL);
00317     }
00318     return memcpy_func;
00319   }
00320 
00321   Function *getUnaryFloatFunction(const char *Name, Function *&Cache) {
00322     if (!Cache)
00323       Cache = M->getOrInsertFunction(Name, Type::FloatTy, Type::FloatTy, NULL);
00324     return Cache;
00325   }
00326   
00327   Function *get_floorf() { return getUnaryFloatFunction("floorf", floorf_func);}
00328   Function *get_ceilf()  { return getUnaryFloatFunction( "ceilf",  ceilf_func);}
00329   Function *get_roundf() { return getUnaryFloatFunction("roundf", roundf_func);}
00330   Function *get_rintf()  { return getUnaryFloatFunction( "rintf",  rintf_func);}
00331   Function *get_nearbyintf() { return getUnaryFloatFunction("nearbyintf",
00332                                                             nearbyintf_func); }
00333 private:
00334   /// @brief Reset our cached data for a new Module
00335   void reset(Module& mod) {
00336     M = &mod;
00337     TD = &getAnalysis<TargetData>();
00338     putchar_func = 0;
00339     puts_func = 0;
00340     fputc_func = 0;
00341     fputs_func = 0;
00342     fwrite_func = 0;
00343     memcpy_func = 0;
00344     memchr_func = 0;
00345     sqrt_func   = 0;
00346     strcpy_func = 0;
00347     strlen_func = 0;
00348     floorf_func = 0;
00349     ceilf_func = 0;
00350     roundf_func = 0;
00351     rintf_func = 0;
00352     nearbyintf_func = 0;
00353   }
00354 
00355 private:
00356   /// Caches for function pointers.
00357   Function *putchar_func, *puts_func;
00358   Function *fputc_func, *fputs_func, *fwrite_func;
00359   Function *memcpy_func, *memchr_func;
00360   Function* sqrt_func;
00361   Function *strcpy_func, *strlen_func;
00362   Function *floorf_func, *ceilf_func, *roundf_func;
00363   Function *rintf_func, *nearbyintf_func;
00364   Module *M;             ///< Cached Module
00365   TargetData *TD;        ///< Cached TargetData
00366 };
00367 
00368 // Register the pass
00369 RegisterOpt<SimplifyLibCalls>
00370 X("simplify-libcalls","Simplify well-known library calls");
00371 
00372 } // anonymous namespace
00373 
00374 // The only public symbol in this file which just instantiates the pass object
00375 ModulePass *llvm::createSimplifyLibCallsPass() {
00376   return new SimplifyLibCalls();
00377 }
00378 
00379 // Classes below here, in the anonymous namespace, are all subclasses of the
00380 // LibCallOptimization class, each implementing all optimizations possible for a
00381 // single well-known library call. Each has a static singleton instance that
00382 // auto registers it into the "optlist" global above.
00383 namespace {
00384 
00385 // Forward declare utility functions.
00386 bool getConstantStringLength(Value* V, uint64_t& len, ConstantArray** A = 0 );
00387 Value *CastToCStr(Value *V, Instruction &IP);
00388 
00389 /// This LibCallOptimization will find instances of a call to "exit" that occurs
00390 /// within the "main" function and change it to a simple "ret" instruction with
00391 /// the same value passed to the exit function. When this is done, it splits the
00392 /// basic block at the exit(3) call and deletes the call instruction.
00393 /// @brief Replace calls to exit in main with a simple return
00394 struct ExitInMainOptimization : public LibCallOptimization {
00395   ExitInMainOptimization() : LibCallOptimization("exit",
00396       "Number of 'exit' calls simplified") {}
00397 
00398   // Make sure the called function looks like exit (int argument, int return
00399   // type, external linkage, not varargs).
00400   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
00401     return F->arg_size() >= 1 && F->arg_begin()->getType()->isInteger();
00402   }
00403 
00404   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
00405     // To be careful, we check that the call to exit is coming from "main", that
00406     // main has external linkage, and the return type of main and the argument
00407     // to exit have the same type.
00408     Function *from = ci->getParent()->getParent();
00409     if (from->hasExternalLinkage())
00410       if (from->getReturnType() == ci->getOperand(1)->getType())
00411         if (from->getName() == "main") {
00412           // Okay, time to actually do the optimization. First, get the basic
00413           // block of the call instruction
00414           BasicBlock* bb = ci->getParent();
00415 
00416           // Create a return instruction that we'll replace the call with.
00417           // Note that the argument of the return is the argument of the call
00418           // instruction.
00419           new ReturnInst(ci->getOperand(1), ci);
00420 
00421           // Split the block at the call instruction which places it in a new
00422           // basic block.
00423           bb->splitBasicBlock(ci);
00424 
00425           // The block split caused a branch instruction to be inserted into
00426           // the end of the original block, right after the return instruction
00427           // that we put there. That's not a valid block, so delete the branch
00428           // instruction.
00429           bb->getInstList().pop_back();
00430 
00431           // Now we can finally get rid of the call instruction which now lives
00432           // in the new basic block.
00433           ci->eraseFromParent();
00434 
00435           // Optimization succeeded, return true.
00436           return true;
00437         }
00438     // We didn't pass the criteria for this optimization so return false
00439     return false;
00440   }
00441 } ExitInMainOptimizer;
00442 
00443 /// This LibCallOptimization will simplify a call to the strcat library
00444 /// function. The simplification is possible only if the string being
00445 /// concatenated is a constant array or a constant expression that results in
00446 /// a constant string. In this case we can replace it with strlen + llvm.memcpy
00447 /// of the constant string. Both of these calls are further reduced, if possible
00448 /// on subsequent passes.
00449 /// @brief Simplify the strcat library function.
00450 struct StrCatOptimization : public LibCallOptimization {
00451 public:
00452   /// @brief Default constructor
00453   StrCatOptimization() : LibCallOptimization("strcat",
00454       "Number of 'strcat' calls simplified") {}
00455 
00456 public:
00457 
00458   /// @brief Make sure that the "strcat" function has the right prototype
00459   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
00460     if (f->getReturnType() == PointerType::get(Type::SByteTy))
00461       if (f->arg_size() == 2)
00462       {
00463         Function::const_arg_iterator AI = f->arg_begin();
00464         if (AI++->getType() == PointerType::get(Type::SByteTy))
00465           if (AI->getType() == PointerType::get(Type::SByteTy))
00466           {
00467             // Indicate this is a suitable call type.
00468             return true;
00469           }
00470       }
00471     return false;
00472   }
00473 
00474   /// @brief Optimize the strcat library function
00475   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
00476     // Extract some information from the instruction
00477     Value* dest = ci->getOperand(1);
00478     Value* src  = ci->getOperand(2);
00479 
00480     // Extract the initializer (while making numerous checks) from the
00481     // source operand of the call to strcat. If we get null back, one of
00482     // a variety of checks in get_GVInitializer failed
00483     uint64_t len = 0;
00484     if (!getConstantStringLength(src,len))
00485       return false;
00486 
00487     // Handle the simple, do-nothing case
00488     if (len == 0) {
00489       ci->replaceAllUsesWith(dest);
00490       ci->eraseFromParent();
00491       return true;
00492     }
00493 
00494     // Increment the length because we actually want to memcpy the null
00495     // terminator as well.
00496     len++;
00497 
00498     // We need to find the end of the destination string.  That's where the
00499     // memory is to be moved to. We just generate a call to strlen (further
00500     // optimized in another pass).  Note that the SLC.get_strlen() call
00501     // caches the Function* for us.
00502     CallInst* strlen_inst =
00503       new CallInst(SLC.get_strlen(), dest, dest->getName()+".len",ci);
00504 
00505     // Now that we have the destination's length, we must index into the
00506     // destination's pointer to get the actual memcpy destination (end of
00507     // the string .. we're concatenating).
00508     std::vector<Value*> idx;
00509     idx.push_back(strlen_inst);
00510     GetElementPtrInst* gep =
00511       new GetElementPtrInst(dest,idx,dest->getName()+".indexed",ci);
00512 
00513     // We have enough information to now generate the memcpy call to
00514     // do the concatenation for us.
00515     std::vector<Value*> vals;
00516     vals.push_back(gep); // destination
00517     vals.push_back(ci->getOperand(2)); // source
00518     vals.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); // length
00519     vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
00520     new CallInst(SLC.get_memcpy(), vals, "", ci);
00521 
00522     // Finally, substitute the first operand of the strcat call for the
00523     // strcat call itself since strcat returns its first operand; and,
00524     // kill the strcat CallInst.
00525     ci->replaceAllUsesWith(dest);
00526     ci->eraseFromParent();
00527     return true;
00528   }
00529 } StrCatOptimizer;
00530 
00531 /// This LibCallOptimization will simplify a call to the strchr library
00532 /// function.  It optimizes out cases where the arguments are both constant
00533 /// and the result can be determined statically.
00534 /// @brief Simplify the strcmp library function.
00535 struct StrChrOptimization : public LibCallOptimization {
00536 public:
00537   StrChrOptimization() : LibCallOptimization("strchr",
00538       "Number of 'strchr' calls simplified") {}
00539 
00540   /// @brief Make sure that the "strchr" function has the right prototype
00541   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
00542     if (f->getReturnType() == PointerType::get(Type::SByteTy) &&
00543         f->arg_size() == 2)
00544       return true;
00545     return false;
00546   }
00547 
00548   /// @brief Perform the strchr optimizations
00549   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
00550     // If there aren't three operands, bail
00551     if (ci->getNumOperands() != 3)
00552       return false;
00553 
00554     // Check that the first argument to strchr is a constant array of sbyte.
00555     // If it is, get the length and data, otherwise return false.
00556     uint64_t len = 0;
00557     ConstantArray* CA;
00558     if (!getConstantStringLength(ci->getOperand(1),len,&CA))
00559       return false;
00560 
00561     // Check that the second argument to strchr is a constant int, return false
00562     // if it isn't
00563     ConstantSInt* CSI = dyn_cast<ConstantSInt>(ci->getOperand(2));
00564     if (!CSI) {
00565       // Just lower this to memchr since we know the length of the string as
00566       // it is constant.
00567       Function* f = SLC.get_memchr();
00568       std::vector<Value*> args;
00569       args.push_back(ci->getOperand(1));
00570       args.push_back(ci->getOperand(2));
00571       args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
00572       ci->replaceAllUsesWith( new CallInst(f,args,ci->getName(),ci));
00573       ci->eraseFromParent();
00574       return true;
00575     }
00576 
00577     // Get the character we're looking for
00578     int64_t chr = CSI->getValue();
00579 
00580     // Compute the offset
00581     uint64_t offset = 0;
00582     bool char_found = false;
00583     for (uint64_t i = 0; i < len; ++i) {
00584       if (ConstantSInt* CI = dyn_cast<ConstantSInt>(CA->getOperand(i))) {
00585         // Check for the null terminator
00586         if (CI->isNullValue())
00587           break; // we found end of string
00588         else if (CI->getValue() == chr) {
00589           char_found = true;
00590           offset = i;
00591           break;
00592         }
00593       }
00594     }
00595 
00596     // strchr(s,c)  -> offset_of_in(c,s)
00597     //    (if c is a constant integer and s is a constant string)
00598     if (char_found) {
00599       std::vector<Value*> indices;
00600       indices.push_back(ConstantUInt::get(Type::ULongTy,offset));
00601       GetElementPtrInst* GEP = new GetElementPtrInst(ci->getOperand(1),indices,
00602           ci->getOperand(1)->getName()+".strchr",ci);
00603       ci->replaceAllUsesWith(GEP);
00604     } else {
00605       ci->replaceAllUsesWith(
00606           ConstantPointerNull::get(PointerType::get(Type::SByteTy)));
00607     }
00608     ci->eraseFromParent();
00609     return true;
00610   }
00611 } StrChrOptimizer;
00612 
00613 /// This LibCallOptimization will simplify a call to the strcmp library
00614 /// function.  It optimizes out cases where one or both arguments are constant
00615 /// and the result can be determined statically.
00616 /// @brief Simplify the strcmp library function.
00617 struct StrCmpOptimization : public LibCallOptimization {
00618 public:
00619   StrCmpOptimization() : LibCallOptimization("strcmp",
00620       "Number of 'strcmp' calls simplified") {}
00621 
00622   /// @brief Make sure that the "strcmp" function has the right prototype
00623   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
00624     return F->getReturnType() == Type::IntTy && F->arg_size() == 2;
00625   }
00626 
00627   /// @brief Perform the strcmp optimization
00628   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
00629     // First, check to see if src and destination are the same. If they are,
00630     // then the optimization is to replace the CallInst with a constant 0
00631     // because the call is a no-op.
00632     Value* s1 = ci->getOperand(1);
00633     Value* s2 = ci->getOperand(2);
00634     if (s1 == s2) {
00635       // strcmp(x,x)  -> 0
00636       ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
00637       ci->eraseFromParent();
00638       return true;
00639     }
00640 
00641     bool isstr_1 = false;
00642     uint64_t len_1 = 0;
00643     ConstantArray* A1;
00644     if (getConstantStringLength(s1,len_1,&A1)) {
00645       isstr_1 = true;
00646       if (len_1 == 0) {
00647         // strcmp("",x) -> *x
00648         LoadInst* load =
00649           new LoadInst(CastToCStr(s2,*ci), ci->getName()+".load",ci);
00650         CastInst* cast =
00651           new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
00652         ci->replaceAllUsesWith(cast);
00653         ci->eraseFromParent();
00654         return true;
00655       }
00656     }
00657 
00658     bool isstr_2 = false;
00659     uint64_t len_2 = 0;
00660     ConstantArray* A2;
00661     if (getConstantStringLength(s2, len_2, &A2)) {
00662       isstr_2 = true;
00663       if (len_2 == 0) {
00664         // strcmp(x,"") -> *x
00665         LoadInst* load =
00666           new LoadInst(CastToCStr(s1,*ci),ci->getName()+".val",ci);
00667         CastInst* cast =
00668           new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
00669         ci->replaceAllUsesWith(cast);
00670         ci->eraseFromParent();
00671         return true;
00672       }
00673     }
00674 
00675     if (isstr_1 && isstr_2) {
00676       // strcmp(x,y)  -> cnst  (if both x and y are constant strings)
00677       std::string str1 = A1->getAsString();
00678       std::string str2 = A2->getAsString();
00679       int result = strcmp(str1.c_str(), str2.c_str());
00680       ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result));
00681       ci->eraseFromParent();
00682       return true;
00683     }
00684     return false;
00685   }
00686 } StrCmpOptimizer;
00687 
00688 /// This LibCallOptimization will simplify a call to the strncmp library
00689 /// function.  It optimizes out cases where one or both arguments are constant
00690 /// and the result can be determined statically.
00691 /// @brief Simplify the strncmp library function.
00692 struct StrNCmpOptimization : public LibCallOptimization {
00693 public:
00694   StrNCmpOptimization() : LibCallOptimization("strncmp",
00695       "Number of 'strncmp' calls simplified") {}
00696 
00697   /// @brief Make sure that the "strncmp" function has the right prototype
00698   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
00699     if (f->getReturnType() == Type::IntTy && f->arg_size() == 3)
00700       return true;
00701     return false;
00702   }
00703 
00704   /// @brief Perform the strncpy optimization
00705   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
00706     // First, check to see if src and destination are the same. If they are,
00707     // then the optimization is to replace the CallInst with a constant 0
00708     // because the call is a no-op.
00709     Value* s1 = ci->getOperand(1);
00710     Value* s2 = ci->getOperand(2);
00711     if (s1 == s2) {
00712       // strncmp(x,x,l)  -> 0
00713       ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
00714       ci->eraseFromParent();
00715       return true;
00716     }
00717 
00718     // Check the length argument, if it is Constant zero then the strings are
00719     // considered equal.
00720     uint64_t len_arg = 0;
00721     bool len_arg_is_const = false;
00722     if (ConstantInt* len_CI = dyn_cast<ConstantInt>(ci->getOperand(3))) {
00723       len_arg_is_const = true;
00724       len_arg = len_CI->getRawValue();
00725       if (len_arg == 0) {
00726         // strncmp(x,y,0)   -> 0
00727         ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
00728         ci->eraseFromParent();
00729         return true;
00730       }
00731     }
00732 
00733     bool isstr_1 = false;
00734     uint64_t len_1 = 0;
00735     ConstantArray* A1;
00736     if (getConstantStringLength(s1, len_1, &A1)) {
00737       isstr_1 = true;
00738       if (len_1 == 0) {
00739         // strncmp("",x) -> *x
00740         LoadInst* load = new LoadInst(s1,ci->getName()+".load",ci);
00741         CastInst* cast =
00742           new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
00743         ci->replaceAllUsesWith(cast);
00744         ci->eraseFromParent();
00745         return true;
00746       }
00747     }
00748 
00749     bool isstr_2 = false;
00750     uint64_t len_2 = 0;
00751     ConstantArray* A2;
00752     if (getConstantStringLength(s2,len_2,&A2)) {
00753       isstr_2 = true;
00754       if (len_2 == 0) {
00755         // strncmp(x,"") -> *x
00756         LoadInst* load = new LoadInst(s2,ci->getName()+".val",ci);
00757         CastInst* cast =
00758           new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
00759         ci->replaceAllUsesWith(cast);
00760         ci->eraseFromParent();
00761         return true;
00762       }
00763     }
00764 
00765     if (isstr_1 && isstr_2 && len_arg_is_const) {
00766       // strncmp(x,y,const) -> constant
00767       std::string str1 = A1->getAsString();
00768       std::string str2 = A2->getAsString();
00769       int result = strncmp(str1.c_str(), str2.c_str(), len_arg);
00770       ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result));
00771       ci->eraseFromParent();
00772       return true;
00773     }
00774     return false;
00775   }
00776 } StrNCmpOptimizer;
00777 
00778 /// This LibCallOptimization will simplify a call to the strcpy library
00779 /// function.  Two optimizations are possible:
00780 /// (1) If src and dest are the same and not volatile, just return dest
00781 /// (2) If the src is a constant then we can convert to llvm.memmove
00782 /// @brief Simplify the strcpy library function.
00783 struct StrCpyOptimization : public LibCallOptimization {
00784 public:
00785   StrCpyOptimization() : LibCallOptimization("strcpy",
00786       "Number of 'strcpy' calls simplified") {}
00787 
00788   /// @brief Make sure that the "strcpy" function has the right prototype
00789   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
00790     if (f->getReturnType() == PointerType::get(Type::SByteTy))
00791       if (f->arg_size() == 2) {
00792         Function::const_arg_iterator AI = f->arg_begin();
00793         if (AI++->getType() == PointerType::get(Type::SByteTy))
00794           if (AI->getType() == PointerType::get(Type::SByteTy)) {
00795             // Indicate this is a suitable call type.
00796             return true;
00797           }
00798       }
00799     return false;
00800   }
00801 
00802   /// @brief Perform the strcpy optimization
00803   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
00804     // First, check to see if src and destination are the same. If they are,
00805     // then the optimization is to replace the CallInst with the destination
00806     // because the call is a no-op. Note that this corresponds to the
00807     // degenerate strcpy(X,X) case which should have "undefined" results
00808     // according to the C specification. However, it occurs sometimes and
00809     // we optimize it as a no-op.
00810     Value* dest = ci->getOperand(1);
00811     Value* src = ci->getOperand(2);
00812     if (dest == src) {
00813       ci->replaceAllUsesWith(dest);
00814       ci->eraseFromParent();
00815       return true;
00816     }
00817 
00818     // Get the length of the constant string referenced by the second operand,
00819     // the "src" parameter. Fail the optimization if we can't get the length
00820     // (note that getConstantStringLength does lots of checks to make sure this
00821     // is valid).
00822     uint64_t len = 0;
00823     if (!getConstantStringLength(ci->getOperand(2),len))
00824       return false;
00825 
00826     // If the constant string's length is zero we can optimize this by just
00827     // doing a store of 0 at the first byte of the destination
00828     if (len == 0) {
00829       new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci);
00830       ci->replaceAllUsesWith(dest);
00831       ci->eraseFromParent();
00832       return true;
00833     }
00834 
00835     // Increment the length because we actually want to memcpy the null
00836     // terminator as well.
00837     len++;
00838 
00839     // We have enough information to now generate the memcpy call to
00840     // do the concatenation for us.
00841     std::vector<Value*> vals;
00842     vals.push_back(dest); // destination
00843     vals.push_back(src); // source
00844     vals.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); // length
00845     vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
00846     new CallInst(SLC.get_memcpy(), vals, "", ci);
00847 
00848     // Finally, substitute the first operand of the strcat call for the
00849     // strcat call itself since strcat returns its first operand; and,
00850     // kill the strcat CallInst.
00851     ci->replaceAllUsesWith(dest);
00852     ci->eraseFromParent();
00853     return true;
00854   }
00855 } StrCpyOptimizer;
00856 
00857 /// This LibCallOptimization will simplify a call to the strlen library
00858 /// function by replacing it with a constant value if the string provided to
00859 /// it is a constant array.
00860 /// @brief Simplify the strlen library function.
00861 struct StrLenOptimization : public LibCallOptimization {
00862   StrLenOptimization() : LibCallOptimization("strlen",
00863       "Number of 'strlen' calls simplified") {}
00864 
00865   /// @brief Make sure that the "strlen" function has the right prototype
00866   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
00867   {
00868     if (f->getReturnType() == SLC.getTargetData()->getIntPtrType())
00869       if (f->arg_size() == 1)
00870         if (Function::const_arg_iterator AI = f->arg_begin())
00871           if (AI->getType() == PointerType::get(Type::SByteTy))
00872             return true;
00873     return false;
00874   }
00875 
00876   /// @brief Perform the strlen optimization
00877   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
00878   {
00879     // Make sure we're dealing with an sbyte* here.
00880     Value* str = ci->getOperand(1);
00881     if (str->getType() != PointerType::get(Type::SByteTy))
00882       return false;
00883 
00884     // Does the call to strlen have exactly one use?
00885     if (ci->hasOneUse())
00886       // Is that single use a binary operator?
00887       if (BinaryOperator* bop = dyn_cast<BinaryOperator>(ci->use_back()))
00888         // Is it compared against a constant integer?
00889         if (ConstantInt* CI = dyn_cast<ConstantInt>(bop->getOperand(1)))
00890         {
00891           // Get the value the strlen result is compared to
00892           uint64_t val = CI->getRawValue();
00893 
00894           // If its compared against length 0 with == or !=
00895           if (val == 0 &&
00896               (bop->getOpcode() == Instruction::SetEQ ||
00897                bop->getOpcode() == Instruction::SetNE))
00898           {
00899             // strlen(x) != 0 -> *x != 0
00900             // strlen(x) == 0 -> *x == 0
00901             LoadInst* load = new LoadInst(str,str->getName()+".first",ci);
00902             BinaryOperator* rbop = BinaryOperator::create(bop->getOpcode(),
00903               load, ConstantSInt::get(Type::SByteTy,0),
00904               bop->getName()+".strlen", ci);
00905             bop->replaceAllUsesWith(rbop);
00906             bop->eraseFromParent();
00907             ci->eraseFromParent();
00908             return true;
00909           }
00910         }
00911 
00912     // Get the length of the constant string operand
00913     uint64_t len = 0;
00914     if (!getConstantStringLength(ci->getOperand(1),len))
00915       return false;
00916 
00917     // strlen("xyz") -> 3 (for example)
00918     const Type *Ty = SLC.getTargetData()->getIntPtrType();
00919     if (Ty->isSigned())
00920       ci->replaceAllUsesWith(ConstantSInt::get(Ty, len));
00921     else
00922       ci->replaceAllUsesWith(ConstantUInt::get(Ty, len));
00923      
00924     ci->eraseFromParent();
00925     return true;
00926   }
00927 } StrLenOptimizer;
00928 
00929 /// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value
00930 /// is equal or not-equal to zero. 
00931 static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) {
00932   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
00933        UI != E; ++UI) {
00934     Instruction *User = cast<Instruction>(*UI);
00935     if (User->getOpcode() == Instruction::SetNE ||
00936         User->getOpcode() == Instruction::SetEQ) {
00937       if (isa<Constant>(User->getOperand(1)) && 
00938           cast<Constant>(User->getOperand(1))->isNullValue())
00939         continue;
00940     } else if (CastInst *CI = dyn_cast<CastInst>(User))
00941       if (CI->getType() == Type::BoolTy)
00942         continue;
00943     // Unknown instruction.
00944     return false;
00945   }
00946   return true;
00947 }
00948 
00949 /// This memcmpOptimization will simplify a call to the memcmp library
00950 /// function.
00951 struct memcmpOptimization : public LibCallOptimization {
00952   /// @brief Default Constructor
00953   memcmpOptimization()
00954     : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {}
00955   
00956   /// @brief Make sure that the "memcmp" function has the right prototype
00957   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
00958     Function::const_arg_iterator AI = F->arg_begin();
00959     if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false;
00960     if (!isa<PointerType>((++AI)->getType())) return false;
00961     if (!(++AI)->getType()->isInteger()) return false;
00962     if (!F->getReturnType()->isInteger()) return false;
00963     return true;
00964   }
00965   
00966   /// Because of alignment and instruction information that we don't have, we
00967   /// leave the bulk of this to the code generators.
00968   ///
00969   /// Note that we could do much more if we could force alignment on otherwise
00970   /// small aligned allocas, or if we could indicate that loads have a small
00971   /// alignment.
00972   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) {
00973     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
00974 
00975     // If the two operands are the same, return zero.
00976     if (LHS == RHS) {
00977       // memcmp(s,s,x) -> 0
00978       CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
00979       CI->eraseFromParent();
00980       return true;
00981     }
00982     
00983     // Make sure we have a constant length.
00984     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
00985     if (!LenC) return false;
00986     uint64_t Len = LenC->getRawValue();
00987       
00988     // If the length is zero, this returns 0.
00989     switch (Len) {
00990     case 0:
00991       // memcmp(s1,s2,0) -> 0
00992       CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
00993       CI->eraseFromParent();
00994       return true;
00995     case 1: {
00996       // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2
00997       const Type *UCharPtr = PointerType::get(Type::UByteTy);
00998       CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
00999       CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
01000       Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI);
01001       Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI);
01002       Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI);
01003       if (RV->getType() != CI->getType())
01004         RV = new CastInst(RV, CI->getType(), RV->getName(), CI);
01005       CI->replaceAllUsesWith(RV);
01006       CI->eraseFromParent();
01007       return true;
01008     }
01009     case 2:
01010       if (IsOnlyUsedInEqualsZeroComparison(CI)) {
01011         // TODO: IF both are aligned, use a short load/compare.
01012       
01013         // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters
01014         const Type *UCharPtr = PointerType::get(Type::UByteTy);
01015         CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
01016         CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
01017         Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI);
01018         Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI);
01019         Value *D1 = BinaryOperator::createSub(S1V1, S2V1,
01020                                               CI->getName()+".d1", CI);
01021         Constant *One = ConstantInt::get(Type::IntTy, 1);
01022         Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI);
01023         Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI);
01024         Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI);
01025         Value *S2V2 = new LoadInst(G2, RHS->getName()+".val2", CI);
01026         Value *D2 = BinaryOperator::createSub(S1V2, S2V2,
01027                                               CI->getName()+".d1", CI);
01028         Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI);
01029         if (Or->getType() != CI->getType())
01030           Or = new CastInst(Or, CI->getType(), Or->getName(), CI);
01031         CI->replaceAllUsesWith(Or);
01032         CI->eraseFromParent();
01033         return true;
01034       }
01035       break;
01036     default:
01037       break;
01038     }
01039     
01040     return false;
01041   }
01042 } memcmpOptimizer;
01043 
01044 
01045 /// This LibCallOptimization will simplify a call to the memcpy library
01046 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
01047 /// bytes depending on the length of the string and the alignment. Additional
01048 /// optimizations are possible in code generation (sequence of immediate store)
01049 /// @brief Simplify the memcpy library function.
01050 struct LLVMMemCpyMoveOptzn : public LibCallOptimization {
01051   LLVMMemCpyMoveOptzn(const char* fname, const char* desc)
01052   : LibCallOptimization(fname, desc) {}
01053 
01054   /// @brief Make sure that the "memcpy" function has the right prototype
01055   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD) {
01056     // Just make sure this has 4 arguments per LLVM spec.
01057     return (f->arg_size() == 4);
01058   }
01059 
01060   /// Because of alignment and instruction information that we don't have, we
01061   /// leave the bulk of this to the code generators. The optimization here just
01062   /// deals with a few degenerate cases where the length of the string and the
01063   /// alignment match the sizes of our intrinsic types so we can do a load and
01064   /// store instead of the memcpy call.
01065   /// @brief Perform the memcpy optimization.
01066   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& TD) {
01067     // Make sure we have constant int values to work with
01068     ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
01069     if (!LEN)
01070       return false;
01071     ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
01072     if (!ALIGN)
01073       return false;
01074 
01075     // If the length is larger than the alignment, we can't optimize
01076     uint64_t len = LEN->getRawValue();
01077     uint64_t alignment = ALIGN->getRawValue();
01078     if (alignment == 0)
01079       alignment = 1; // Alignment 0 is identity for alignment 1
01080     if (len > alignment)
01081       return false;
01082 
01083     // Get the type we will cast to, based on size of the string
01084     Value* dest = ci->getOperand(1);
01085     Value* src = ci->getOperand(2);
01086     Type* castType = 0;
01087     switch (len)
01088     {
01089       case 0:
01090         // memcpy(d,s,0,a) -> noop
01091         ci->eraseFromParent();
01092         return true;
01093       case 1: castType = Type::SByteTy; break;
01094       case 2: castType = Type::ShortTy; break;
01095       case 4: castType = Type::IntTy; break;
01096       case 8: castType = Type::LongTy; break;
01097       default:
01098         return false;
01099     }
01100 
01101     // Cast source and dest to the right sized primitive and then load/store
01102     CastInst* SrcCast =
01103       new CastInst(src,PointerType::get(castType),src->getName()+".cast",ci);
01104     CastInst* DestCast =
01105       new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
01106     LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci);
01107     StoreInst* SI = new StoreInst(LI, DestCast, ci);
01108     ci->eraseFromParent();
01109     return true;
01110   }
01111 };
01112 
01113 /// This LibCallOptimization will simplify a call to the memcpy/memmove library
01114 /// functions.
01115 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer32("llvm.memcpy.i32",
01116                                     "Number of 'llvm.memcpy' calls simplified");
01117 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer64("llvm.memcpy.i64",
01118                                    "Number of 'llvm.memcpy' calls simplified");
01119 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer32("llvm.memmove.i32",
01120                                    "Number of 'llvm.memmove' calls simplified");
01121 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer64("llvm.memmove.i64",
01122                                    "Number of 'llvm.memmove' calls simplified");
01123 
01124 /// This LibCallOptimization will simplify a call to the memset library
01125 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
01126 /// bytes depending on the length argument.
01127 struct LLVMMemSetOptimization : public LibCallOptimization {
01128   /// @brief Default Constructor
01129   LLVMMemSetOptimization(const char *Name) : LibCallOptimization(Name,
01130       "Number of 'llvm.memset' calls simplified") {}
01131 
01132   /// @brief Make sure that the "memset" function has the right prototype
01133   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
01134     // Just make sure this has 3 arguments per LLVM spec.
01135     return F->arg_size() == 4;
01136   }
01137 
01138   /// Because of alignment and instruction information that we don't have, we
01139   /// leave the bulk of this to the code generators. The optimization here just
01140   /// deals with a few degenerate cases where the length parameter is constant
01141   /// and the alignment matches the sizes of our intrinsic types so we can do
01142   /// store instead of the memcpy call. Other calls are transformed into the
01143   /// llvm.memset intrinsic.
01144   /// @brief Perform the memset optimization.
01145   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &TD) {
01146     // Make sure we have constant int values to work with
01147     ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
01148     if (!LEN)
01149       return false;
01150     ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
01151     if (!ALIGN)
01152       return false;
01153 
01154     // Extract the length and alignment
01155     uint64_t len = LEN->getRawValue();
01156     uint64_t alignment = ALIGN->getRawValue();
01157 
01158     // Alignment 0 is identity for alignment 1
01159     if (alignment == 0)
01160       alignment = 1;
01161 
01162     // If the length is zero, this is a no-op
01163     if (len == 0) {
01164       // memset(d,c,0,a) -> noop
01165       ci->eraseFromParent();
01166       return true;
01167     }
01168 
01169     // If the length is larger than the alignment, we can't optimize
01170     if (len > alignment)
01171       return false;
01172 
01173     // Make sure we have a constant ubyte to work with so we can extract
01174     // the value to be filled.
01175     ConstantUInt* FILL = dyn_cast<ConstantUInt>(ci->getOperand(2));
01176     if (!FILL)
01177       return false;
01178     if (FILL->getType() != Type::UByteTy)
01179       return false;
01180 
01181     // memset(s,c,n) -> store s, c (for n=1,2,4,8)
01182 
01183     // Extract the fill character
01184     uint64_t fill_char = FILL->getValue();
01185     uint64_t fill_value = fill_char;
01186 
01187     // Get the type we will cast to, based on size of memory area to fill, and
01188     // and the value we will store there.
01189     Value* dest = ci->getOperand(1);
01190     Type* castType = 0;
01191     switch (len) {
01192       case 1:
01193         castType = Type::UByteTy;
01194         break;
01195       case 2:
01196         castType = Type::UShortTy;
01197         fill_value |= fill_char << 8;
01198         break;
01199       case 4:
01200         castType = Type::UIntTy;
01201         fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
01202         break;
01203       case 8:
01204         castType = Type::ULongTy;
01205         fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
01206         fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48;
01207         fill_value |= fill_char << 56;
01208         break;
01209       default:
01210         return false;
01211     }
01212 
01213     // Cast dest to the right sized primitive and then load/store
01214     CastInst* DestCast =
01215       new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
01216     new StoreInst(ConstantUInt::get(castType,fill_value),DestCast, ci);
01217     ci->eraseFromParent();
01218     return true;
01219   }
01220 };
01221 
01222 LLVMMemSetOptimization MemSet32Optimizer("llvm.memset.i32");
01223 LLVMMemSetOptimization MemSet64Optimizer("llvm.memset.i64");
01224 
01225 
01226 /// This LibCallOptimization will simplify calls to the "pow" library
01227 /// function. It looks for cases where the result of pow is well known and
01228 /// substitutes the appropriate value.
01229 /// @brief Simplify the pow library function.
01230 struct PowOptimization : public LibCallOptimization {
01231 public:
01232   /// @brief Default Constructor
01233   PowOptimization() : LibCallOptimization("pow",
01234       "Number of 'pow' calls simplified") {}
01235 
01236   /// @brief Make sure that the "pow" function has the right prototype
01237   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
01238     // Just make sure this has 2 arguments
01239     return (f->arg_size() == 2);
01240   }
01241 
01242   /// @brief Perform the pow optimization.
01243   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
01244     const Type *Ty = cast<Function>(ci->getOperand(0))->getReturnType();
01245     Value* base = ci->getOperand(1);
01246     Value* expn = ci->getOperand(2);
01247     if (ConstantFP *Op1 = dyn_cast<ConstantFP>(base)) {
01248       double Op1V = Op1->getValue();
01249       if (Op1V == 1.0) {
01250         // pow(1.0,x) -> 1.0
01251         ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0));
01252         ci->eraseFromParent();
01253         return true;
01254       }
01255     }  else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn)) {
01256       double Op2V = Op2->getValue();
01257       if (Op2V == 0.0) {
01258         // pow(x,0.0) -> 1.0
01259         ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0));
01260         ci->eraseFromParent();
01261         return true;
01262       } else if (Op2V == 0.5) {
01263         // pow(x,0.5) -> sqrt(x)
01264         CallInst* sqrt_inst = new CallInst(SLC.get_sqrt(), base,
01265             ci->getName()+".pow",ci);
01266         ci->replaceAllUsesWith(sqrt_inst);
01267         ci->eraseFromParent();
01268         return true;
01269       } else if (Op2V == 1.0) {
01270         // pow(x,1.0) -> x
01271         ci->replaceAllUsesWith(base);
01272         ci->eraseFromParent();
01273         return true;
01274       } else if (Op2V == -1.0) {
01275         // pow(x,-1.0)    -> 1.0/x
01276         BinaryOperator* div_inst= BinaryOperator::createDiv(
01277           ConstantFP::get(Ty,1.0), base, ci->getName()+".pow", ci);
01278         ci->replaceAllUsesWith(div_inst);
01279         ci->eraseFromParent();
01280         return true;
01281       }
01282     }
01283     return false; // opt failed
01284   }
01285 } PowOptimizer;
01286 
01287 /// This LibCallOptimization will simplify calls to the "printf" library
01288 /// function. It looks for cases where the result of printf is not used and the
01289 /// operation can be reduced to something simpler.
01290 /// @brief Simplify the printf library function.
01291 struct PrintfOptimization : public LibCallOptimization {
01292 public:
01293   /// @brief Default Constructor
01294   PrintfOptimization() : LibCallOptimization("printf",
01295       "Number of 'printf' calls simplified") {}
01296 
01297   /// @brief Make sure that the "printf" function has the right prototype
01298   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
01299     // Just make sure this has at least 1 arguments
01300     return (f->arg_size() >= 1);
01301   }
01302 
01303   /// @brief Perform the printf optimization.
01304   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
01305     // If the call has more than 2 operands, we can't optimize it
01306     if (ci->getNumOperands() > 3 || ci->getNumOperands() <= 2)
01307       return false;
01308 
01309     // If the result of the printf call is used, none of these optimizations
01310     // can be made.
01311     if (!ci->use_empty())
01312       return false;
01313 
01314     // All the optimizations depend on the length of the first argument and the
01315     // fact that it is a constant string array. Check that now
01316     uint64_t len = 0;
01317     ConstantArray* CA = 0;
01318     if (!getConstantStringLength(ci->getOperand(1), len, &CA))
01319       return false;
01320 
01321     if (len != 2 && len != 3)
01322       return false;
01323 
01324     // The first character has to be a %
01325     if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0)))
01326       if (CI->getRawValue() != '%')
01327         return false;
01328 
01329     // Get the second character and switch on its value
01330     ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
01331     switch (CI->getRawValue()) {
01332       case 's':
01333       {
01334         if (len != 3 ||
01335             dyn_cast<ConstantInt>(CA->getOperand(2))->getRawValue() != '\n')
01336           return false;
01337 
01338         // printf("%s\n",str) -> puts(str)
01339         Function* puts_func = SLC.get_puts();
01340         if (!puts_func)
01341           return false;
01342         std::vector<Value*> args;
01343         args.push_back(CastToCStr(ci->getOperand(2), *ci));
01344         new CallInst(puts_func,args,ci->getName(),ci);
01345         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
01346         break;
01347       }
01348       case 'c':
01349       {
01350         // printf("%c",c) -> putchar(c)
01351         if (len != 2)
01352           return false;
01353 
01354         Function* putchar_func = SLC.get_putchar();
01355         if (!putchar_func)
01356           return false;
01357         CastInst* cast = new CastInst(ci->getOperand(2), Type::IntTy,
01358                                       CI->getName()+".int", ci);
01359         new CallInst(putchar_func, cast, "", ci);
01360         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy, 1));
01361         break;
01362       }
01363       default:
01364         return false;
01365     }
01366     ci->eraseFromParent();
01367     return true;
01368   }
01369 } PrintfOptimizer;
01370 
01371 /// This LibCallOptimization will simplify calls to the "fprintf" library
01372 /// function. It looks for cases where the result of fprintf is not used and the
01373 /// operation can be reduced to something simpler.
01374 /// @brief Simplify the fprintf library function.
01375 struct FPrintFOptimization : public LibCallOptimization {
01376 public:
01377   /// @brief Default Constructor
01378   FPrintFOptimization() : LibCallOptimization("fprintf",
01379       "Number of 'fprintf' calls simplified") {}
01380 
01381   /// @brief Make sure that the "fprintf" function has the right prototype
01382   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
01383     // Just make sure this has at least 2 arguments
01384     return (f->arg_size() >= 2);
01385   }
01386 
01387   /// @brief Perform the fprintf optimization.
01388   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
01389     // If the call has more than 3 operands, we can't optimize it
01390     if (ci->getNumOperands() > 4 || ci->getNumOperands() <= 2)
01391       return false;
01392 
01393     // If the result of the fprintf call is used, none of these optimizations
01394     // can be made.
01395     if (!ci->use_empty())
01396       return false;
01397 
01398     // All the optimizations depend on the length of the second argument and the
01399     // fact that it is a constant string array. Check that now
01400     uint64_t len = 0;
01401     ConstantArray* CA = 0;
01402     if (!getConstantStringLength(ci->getOperand(2), len, &CA))
01403       return false;
01404 
01405     if (ci->getNumOperands() == 3) {
01406       // Make sure there's no % in the constant array
01407       for (unsigned i = 0; i < len; ++i) {
01408         if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) {
01409           // Check for the null terminator
01410           if (CI->getRawValue() == '%')
01411             return false; // we found end of string
01412         } else {
01413           return false;
01414         }
01415       }
01416 
01417       // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file)
01418       const Type* FILEptr_type = ci->getOperand(1)->getType();
01419       Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
01420       if (!fwrite_func)
01421         return false;
01422 
01423       // Make sure that the fprintf() and fwrite() functions both take the
01424       // same type of char pointer.
01425       if (ci->getOperand(2)->getType() !=
01426           fwrite_func->getFunctionType()->getParamType(0))
01427         return false;
01428 
01429       std::vector<Value*> args;
01430       args.push_back(ci->getOperand(2));
01431       args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
01432       args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
01433       args.push_back(ci->getOperand(1));
01434       new CallInst(fwrite_func,args,ci->getName(),ci);
01435       ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
01436       ci->eraseFromParent();
01437       return true;
01438     }
01439 
01440     // The remaining optimizations require the format string to be length 2
01441     // "%s" or "%c".
01442     if (len != 2)
01443       return false;
01444 
01445     // The first character has to be a %
01446     if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0)))
01447       if (CI->getRawValue() != '%')
01448         return false;
01449 
01450     // Get the second character and switch on its value
01451     ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
01452     switch (CI->getRawValue()) {
01453       case 's':
01454       {
01455         uint64_t len = 0;
01456         ConstantArray* CA = 0;
01457         if (getConstantStringLength(ci->getOperand(3), len, &CA)) {
01458           // fprintf(file,"%s",str) -> fwrite(str,strlen(str),1,file)
01459           const Type* FILEptr_type = ci->getOperand(1)->getType();
01460           Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
01461           if (!fwrite_func)
01462             return false;
01463           std::vector<Value*> args;
01464           args.push_back(CastToCStr(ci->getOperand(3), *ci));
01465           args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
01466           args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
01467           args.push_back(ci->getOperand(1));
01468           new CallInst(fwrite_func,args,ci->getName(),ci);
01469           ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
01470         } else {
01471           // fprintf(file,"%s",str) -> fputs(str,file)
01472           const Type* FILEptr_type = ci->getOperand(1)->getType();
01473           Function* fputs_func = SLC.get_fputs(FILEptr_type);
01474           if (!fputs_func)
01475             return false;
01476           std::vector<Value*> args;
01477           args.push_back(CastToCStr(ci->getOperand(3), *ci));
01478           args.push_back(ci->getOperand(1));
01479           new CallInst(fputs_func,args,ci->getName(),ci);
01480           ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
01481         }
01482         break;
01483       }
01484       case 'c':
01485       {
01486         // fprintf(file,"%c",c) -> fputc(c,file)
01487         const Type* FILEptr_type = ci->getOperand(1)->getType();
01488         Function* fputc_func = SLC.get_fputc(FILEptr_type);
01489         if (!fputc_func)
01490           return false;
01491         CastInst* cast = new CastInst(ci->getOperand(3), Type::IntTy,
01492                                       CI->getName()+".int", ci);
01493         new CallInst(fputc_func,cast,ci->getOperand(1),"",ci);
01494         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
01495         break;
01496       }
01497       default:
01498         return false;
01499     }
01500     ci->eraseFromParent();
01501     return true;
01502   }
01503 } FPrintFOptimizer;
01504 
01505 /// This LibCallOptimization will simplify calls to the "sprintf" library
01506 /// function. It looks for cases where the result of sprintf is not used and the
01507 /// operation can be reduced to something simpler.
01508 /// @brief Simplify the sprintf library function.
01509 struct SPrintFOptimization : public LibCallOptimization {
01510 public:
01511   /// @brief Default Constructor
01512   SPrintFOptimization() : LibCallOptimization("sprintf",
01513       "Number of 'sprintf' calls simplified") {}
01514 
01515   /// @brief Make sure that the "fprintf" function has the right prototype
01516   virtual bool ValidateCalledFunction(const Function *f, SimplifyLibCalls &SLC){
01517     // Just make sure this has at least 2 arguments
01518     return (f->getReturnType() == Type::IntTy && f->arg_size() >= 2);
01519   }
01520 
01521   /// @brief Perform the sprintf optimization.
01522   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
01523     // If the call has more than 3 operands, we can't optimize it
01524     if (ci->getNumOperands() > 4 || ci->getNumOperands() < 3)
01525       return false;
01526 
01527     // All the optimizations depend on the length of the second argument and the
01528     // fact that it is a constant string array. Check that now
01529     uint64_t len = 0;
01530     ConstantArray* CA = 0;
01531     if (!getConstantStringLength(ci->getOperand(2), len, &CA))
01532       return false;
01533 
01534     if (ci->getNumOperands() == 3) {
01535       if (len == 0) {
01536         // If the length is 0, we just need to store a null byte
01537         new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci);
01538         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0));
01539         ci->eraseFromParent();
01540         return true;
01541       }
01542 
01543       // Make sure there's no % in the constant array
01544       for (unsigned i = 0; i < len; ++i) {
01545         if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) {
01546           // Check for the null terminator
01547           if (CI->getRawValue() == '%')
01548             return false; // we found a %, can't optimize
01549         } else {
01550           return false; // initializer is not constant int, can't optimize
01551         }
01552       }
01553 
01554       // Increment length because we want to copy the null byte too
01555       len++;
01556 
01557       // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
01558       Function* memcpy_func = SLC.get_memcpy();
01559       if (!memcpy_func)
01560         return false;
01561       std::vector<Value*> args;
01562       args.push_back(ci->getOperand(1));
01563       args.push_back(ci->getOperand(2));
01564       args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
01565       args.push_back(ConstantUInt::get(Type::UIntTy,1));
01566       new CallInst(memcpy_func,args,"",ci);
01567       ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
01568       ci->eraseFromParent();
01569       return true;
01570     }
01571 
01572     // The remaining optimizations require the format string to be length 2
01573     // "%s" or "%c".
01574     if (len != 2)
01575       return false;
01576 
01577     // The first character has to be a %
01578     if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0)))
01579       if (CI->getRawValue() != '%')
01580         return false;
01581 
01582     // Get the second character and switch on its value
01583     ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
01584     switch (CI->getRawValue()) {
01585     case 's': {
01586       // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
01587       Function* strlen_func = SLC.get_strlen();
01588       Function* memcpy_func = SLC.get_memcpy();
01589       if (!strlen_func || !memcpy_func)
01590         return false;
01591       
01592       Value *Len = new CallInst(strlen_func, CastToCStr(ci->getOperand(3), *ci),
01593                                 ci->getOperand(3)->getName()+".len", ci);
01594       Value *Len1 = BinaryOperator::createAdd(Len,
01595                                             ConstantInt::get(Len->getType(), 1),
01596                                               Len->getName()+"1", ci);
01597       if (Len1->getType() != SLC.getIntPtrType())
01598         Len1 = new CastInst(Len1, SLC.getIntPtrType(), Len1->getName(), ci);
01599       std::vector<Value*> args;
01600       args.push_back(CastToCStr(ci->getOperand(1), *ci));
01601       args.push_back(CastToCStr(ci->getOperand(3), *ci));
01602       args.push_back(Len1);
01603       args.push_back(ConstantUInt::get(Type::UIntTy,1));
01604       new CallInst(memcpy_func, args, "", ci);
01605       
01606       // The strlen result is the unincremented number of bytes in the string.
01607       if (!ci->use_empty()) {
01608         if (Len->getType() != ci->getType())
01609           Len = new CastInst(Len, ci->getType(), Len->getName(), ci);
01610         ci->replaceAllUsesWith(Len);
01611       }
01612       ci->eraseFromParent();
01613       return true;
01614     }
01615     case 'c': {
01616       // sprintf(dest,"%c",chr) -> store chr, dest
01617       CastInst* cast = new CastInst(ci->getOperand(3),Type::SByteTy,"char",ci);
01618       new StoreInst(cast, ci->getOperand(1), ci);
01619       GetElementPtrInst* gep = new GetElementPtrInst(ci->getOperand(1),
01620         ConstantUInt::get(Type::UIntTy,1),ci->getOperand(1)->getName()+".end",
01621         ci);
01622       new StoreInst(ConstantInt::get(Type::SByteTy,0),gep,ci);
01623       ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
01624       ci->eraseFromParent();
01625       return true;
01626     }
01627     }
01628     return false;
01629   }
01630 } SPrintFOptimizer;
01631 
01632 /// This LibCallOptimization will simplify calls to the "fputs" library
01633 /// function. It looks for cases where the result of fputs is not used and the
01634 /// operation can be reduced to something simpler.
01635 /// @brief Simplify the puts library function.
01636 struct PutsOptimization : public LibCallOptimization {
01637 public:
01638   /// @brief Default Constructor
01639   PutsOptimization() : LibCallOptimization("fputs",
01640       "Number of 'fputs' calls simplified") {}
01641 
01642   /// @brief Make sure that the "fputs" function has the right prototype
01643   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
01644     // Just make sure this has 2 arguments
01645     return F->arg_size() == 2;
01646   }
01647 
01648   /// @brief Perform the fputs optimization.
01649   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
01650     // If the result is used, none of these optimizations work
01651     if (!ci->use_empty())
01652       return false;
01653 
01654     // All the optimizations depend on the length of the first argument and the
01655     // fact that it is a constant string array. Check that now
01656     uint64_t len = 0;
01657     if (!getConstantStringLength(ci->getOperand(1), len))
01658       return false;
01659 
01660     switch (len) {
01661       case 0:
01662         // fputs("",F) -> noop
01663         break;
01664       case 1:
01665       {
01666         // fputs(s,F)  -> fputc(s[0],F)  (if s is constant and strlen(s) == 1)
01667         const Type* FILEptr_type = ci->getOperand(2)->getType();
01668         Function* fputc_func = SLC.get_fputc(FILEptr_type);
01669         if (!fputc_func)
01670           return false;
01671         LoadInst* loadi = new LoadInst(ci->getOperand(1),
01672           ci->getOperand(1)->getName()+".byte",ci);
01673         CastInst* casti = new CastInst(loadi,Type::IntTy,
01674           loadi->getName()+".int",ci);
01675         new CallInst(fputc_func,casti,ci->getOperand(2),"",ci);
01676         break;
01677       }
01678       default:
01679       {
01680         // fputs(s,F)  -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1)
01681         const Type* FILEptr_type = ci->getOperand(2)->getType();
01682         Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
01683         if (!fwrite_func)
01684           return false;
01685         std::vector<Value*> parms;
01686         parms.push_back(ci->getOperand(1));
01687         parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
01688         parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
01689         parms.push_back(ci->getOperand(2));
01690         new CallInst(fwrite_func,parms,"",ci);
01691         break;
01692       }
01693     }
01694     ci->eraseFromParent();
01695     return true; // success
01696   }
01697 } PutsOptimizer;
01698 
01699 /// This LibCallOptimization will simplify calls to the "isdigit" library
01700 /// function. It simply does range checks the parameter explicitly.
01701 /// @brief Simplify the isdigit library function.
01702 struct isdigitOptimization : public LibCallOptimization {
01703 public:
01704   isdigitOptimization() : LibCallOptimization("isdigit",
01705       "Number of 'isdigit' calls simplified") {}
01706 
01707   /// @brief Make sure that the "isdigit" function has the right prototype
01708   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
01709     // Just make sure this has 1 argument
01710     return (f->arg_size() == 1);
01711   }
01712 
01713   /// @brief Perform the toascii optimization.
01714   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
01715     if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1))) {
01716       // isdigit(c)   -> 0 or 1, if 'c' is constant
01717       uint64_t val = CI->getRawValue();
01718       if (val >= '0' && val <='9')
01719         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
01720       else
01721         ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0));
01722       ci->eraseFromParent();
01723       return true;
01724     }
01725 
01726     // isdigit(c)   -> (unsigned)c - '0' <= 9
01727     CastInst* cast =
01728       new CastInst(ci->getOperand(1),Type::UIntTy,
01729         ci->getOperand(1)->getName()+".uint",ci);
01730     BinaryOperator* sub_inst = BinaryOperator::createSub(cast,
01731         ConstantUInt::get(Type::UIntTy,0x30),
01732         ci->getOperand(1)->getName()+".sub",ci);
01733     SetCondInst* setcond_inst = new SetCondInst(Instruction::SetLE,sub_inst,
01734         ConstantUInt::get(Type::UIntTy,9),
01735         ci->getOperand(1)->getName()+".cmp",ci);
01736     CastInst* c2 =
01737       new CastInst(setcond_inst,Type::IntTy,
01738         ci->getOperand(1)->getName()+".isdigit",ci);
01739     ci->replaceAllUsesWith(c2);
01740     ci->eraseFromParent();
01741     return true;
01742   }
01743 } isdigitOptimizer;
01744 
01745 struct isasciiOptimization : public LibCallOptimization {
01746 public:
01747   isasciiOptimization()
01748     : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {}
01749   
01750   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
01751     return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() && 
01752            F->getReturnType()->isInteger();
01753   }
01754   
01755   /// @brief Perform the isascii optimization.
01756   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01757     // isascii(c)   -> (unsigned)c < 128
01758     Value *V = CI->getOperand(1);
01759     if (V->getType()->isSigned())
01760       V = new CastInst(V, V->getType()->getUnsignedVersion(), V->getName(), CI);
01761     Value *Cmp = BinaryOperator::createSetLT(V, ConstantUInt::get(V->getType(),
01762                                                                   128),
01763                                              V->getName()+".isascii", CI);
01764     if (Cmp->getType() != CI->getType())
01765       Cmp = new CastInst(Cmp, CI->getType(), Cmp->getName(), CI);
01766     CI->replaceAllUsesWith(Cmp);
01767     CI->eraseFromParent();
01768     return true;
01769   }
01770 } isasciiOptimizer;
01771 
01772 
01773 /// This LibCallOptimization will simplify calls to the "toascii" library
01774 /// function. It simply does the corresponding and operation to restrict the
01775 /// range of values to the ASCII character set (0-127).
01776 /// @brief Simplify the toascii library function.
01777 struct ToAsciiOptimization : public LibCallOptimization {
01778 public:
01779   /// @brief Default Constructor
01780   ToAsciiOptimization() : LibCallOptimization("toascii",
01781       "Number of 'toascii' calls simplified") {}
01782 
01783   /// @brief Make sure that the "fputs" function has the right prototype
01784   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
01785     // Just make sure this has 2 arguments
01786     return (f->arg_size() == 1);
01787   }
01788 
01789   /// @brief Perform the toascii optimization.
01790   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
01791     // toascii(c)   -> (c & 0x7f)
01792     Value* chr = ci->getOperand(1);
01793     BinaryOperator* and_inst = BinaryOperator::createAnd(chr,
01794         ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci);
01795     ci->replaceAllUsesWith(and_inst);
01796     ci->eraseFromParent();
01797     return true;
01798   }
01799 } ToAsciiOptimizer;
01800 
01801 /// This LibCallOptimization will simplify calls to the "ffs" library
01802 /// calls which find the first set bit in an int, long, or long long. The
01803 /// optimization is to compute the result at compile time if the argument is
01804 /// a constant.
01805 /// @brief Simplify the ffs library function.
01806 struct FFSOptimization : public LibCallOptimization {
01807 protected:
01808   /// @brief Subclass Constructor
01809   FFSOptimization(const char* funcName, const char* description)
01810     : LibCallOptimization(funcName, description) {}
01811 
01812 public:
01813   /// @brief Default Constructor
01814   FFSOptimization() : LibCallOptimization("ffs",
01815       "Number of 'ffs' calls simplified") {}
01816 
01817   /// @brief Make sure that the "ffs" function has the right prototype
01818   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
01819     // Just make sure this has 2 arguments
01820     return F->arg_size() == 1 && F->getReturnType() == Type::IntTy;
01821   }
01822 
01823   /// @brief Perform the ffs optimization.
01824   virtual bool OptimizeCall(CallInst *TheCall, SimplifyLibCalls &SLC) {
01825     if (ConstantInt *CI = dyn_cast<ConstantInt>(TheCall->getOperand(1))) {
01826       // ffs(cnst)  -> bit#
01827       // ffsl(cnst) -> bit#
01828       // ffsll(cnst) -> bit#
01829       uint64_t val = CI->getRawValue();
01830       int result = 0;
01831       if (val) {
01832         ++result;
01833         while ((val & 1) == 0) {
01834           ++result;
01835           val >>= 1;
01836         }
01837       }
01838       TheCall->replaceAllUsesWith(ConstantSInt::get(Type::IntTy, result));
01839       TheCall->eraseFromParent();
01840       return true;
01841     }
01842 
01843     // ffs(x)   -> x == 0 ? 0 : llvm.cttz(x)+1
01844     // ffsl(x)  -> x == 0 ? 0 : llvm.cttz(x)+1
01845     // ffsll(x) -> x == 0 ? 0 : llvm.cttz(x)+1
01846     const Type *ArgType = TheCall->getOperand(1)->getType();
01847     ArgType = ArgType->getUnsignedVersion();
01848     const char *CTTZName;
01849     switch (ArgType->getTypeID()) {
01850     default: assert(0 && "Unknown unsigned type!");
01851     case Type::UByteTyID : CTTZName = "llvm.cttz.i8" ; break;
01852     case Type::UShortTyID: CTTZName = "llvm.cttz.i16"; break;
01853     case Type::UIntTyID  : CTTZName = "llvm.cttz.i32"; break;
01854     case Type::ULongTyID : CTTZName = "llvm.cttz.i64"; break;
01855     }
01856     
01857     Function *F = SLC.getModule()->getOrInsertFunction(CTTZName, ArgType,
01858                                                        ArgType, NULL);
01859     Value *V = new CastInst(TheCall->getOperand(1), ArgType, "tmp", TheCall);
01860     Value *V2 = new CallInst(F, V, "tmp", TheCall);
01861     V2 = new CastInst(V2, Type::IntTy, "tmp", TheCall);
01862     V2 = BinaryOperator::createAdd(V2, ConstantSInt::get(Type::IntTy, 1),
01863                                    "tmp", TheCall);
01864     Value *Cond = 
01865       BinaryOperator::createSetEQ(V, Constant::getNullValue(V->getType()),
01866                                   "tmp", TheCall);
01867     V2 = new SelectInst(Cond, ConstantInt::get(Type::IntTy, 0), V2,
01868                         TheCall->getName(), TheCall);
01869     TheCall->replaceAllUsesWith(V2);
01870     TheCall->eraseFromParent();
01871     return true;
01872   }
01873 } FFSOptimizer;
01874 
01875 /// This LibCallOptimization will simplify calls to the "ffsl" library
01876 /// calls. It simply uses FFSOptimization for which the transformation is
01877 /// identical.
01878 /// @brief Simplify the ffsl library function.
01879 struct FFSLOptimization : public FFSOptimization {
01880 public:
01881   /// @brief Default Constructor
01882   FFSLOptimization() : FFSOptimization("ffsl",
01883       "Number of 'ffsl' calls simplified") {}
01884 
01885 } FFSLOptimizer;
01886 
01887 /// This LibCallOptimization will simplify calls to the "ffsll" library
01888 /// calls. It simply uses FFSOptimization for which the transformation is
01889 /// identical.
01890 /// @brief Simplify the ffsl library function.
01891 struct FFSLLOptimization : public FFSOptimization {
01892 public:
01893   /// @brief Default Constructor
01894   FFSLLOptimization() : FFSOptimization("ffsll",
01895       "Number of 'ffsll' calls simplified") {}
01896 
01897 } FFSLLOptimizer;
01898 
01899 /// This optimizes unary functions that take and return doubles.
01900 struct UnaryDoubleFPOptimizer : public LibCallOptimization {
01901   UnaryDoubleFPOptimizer(const char *Fn, const char *Desc)
01902   : LibCallOptimization(Fn, Desc) {}
01903   
01904   // Make sure that this function has the right prototype
01905   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
01906     return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy &&
01907            F->getReturnType() == Type::DoubleTy;
01908   }
01909 
01910   /// ShrinkFunctionToFloatVersion - If the input to this function is really a
01911   /// float, strength reduce this to a float version of the function,
01912   /// e.g. floor((double)FLT) -> (double)floorf(FLT).  This can only be called
01913   /// when the target supports the destination function and where there can be
01914   /// no precision loss.
01915   static bool ShrinkFunctionToFloatVersion(CallInst *CI, SimplifyLibCalls &SLC,
01916                                            Function *(SimplifyLibCalls::*FP)()){
01917     if (CastInst *Cast = dyn_cast<CastInst>(CI->getOperand(1)))
01918       if (Cast->getOperand(0)->getType() == Type::FloatTy) {
01919         Value *New = new CallInst((SLC.*FP)(), Cast->getOperand(0),
01920                                   CI->getName(), CI);
01921         New = new CastInst(New, Type::DoubleTy, CI->getName(), CI);
01922         CI->replaceAllUsesWith(New);
01923         CI->eraseFromParent();
01924         if (Cast->use_empty())
01925           Cast->eraseFromParent();
01926         return true;
01927       }
01928     return false;
01929   }
01930 };
01931 
01932 
01933 struct FloorOptimization : public UnaryDoubleFPOptimizer {
01934   FloorOptimization()
01935     : UnaryDoubleFPOptimizer("floor", "Number of 'floor' calls simplified") {}
01936   
01937   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01938 #ifdef HAVE_FLOORF
01939     // If this is a float argument passed in, convert to floorf.
01940     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_floorf))
01941       return true;
01942 #endif
01943     return false; // opt failed
01944   }
01945 } FloorOptimizer;
01946 
01947 struct CeilOptimization : public UnaryDoubleFPOptimizer {
01948   CeilOptimization()
01949   : UnaryDoubleFPOptimizer("ceil", "Number of 'ceil' calls simplified") {}
01950   
01951   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01952 #ifdef HAVE_CEILF
01953     // If this is a float argument passed in, convert to ceilf.
01954     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_ceilf))
01955       return true;
01956 #endif
01957     return false; // opt failed
01958   }
01959 } CeilOptimizer;
01960 
01961 struct RoundOptimization : public UnaryDoubleFPOptimizer {
01962   RoundOptimization()
01963   : UnaryDoubleFPOptimizer("round", "Number of 'round' calls simplified") {}
01964   
01965   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01966 #ifdef HAVE_ROUNDF
01967     // If this is a float argument passed in, convert to roundf.
01968     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_roundf))
01969       return true;
01970 #endif
01971     return false; // opt failed
01972   }
01973 } RoundOptimizer;
01974 
01975 struct RintOptimization : public UnaryDoubleFPOptimizer {
01976   RintOptimization()
01977   : UnaryDoubleFPOptimizer("rint", "Number of 'rint' calls simplified") {}
01978   
01979   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01980 #ifdef HAVE_RINTF
01981     // If this is a float argument passed in, convert to rintf.
01982     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_rintf))
01983       return true;
01984 #endif
01985     return false; // opt failed
01986   }
01987 } RintOptimizer;
01988 
01989 struct NearByIntOptimization : public UnaryDoubleFPOptimizer {
01990   NearByIntOptimization()
01991   : UnaryDoubleFPOptimizer("nearbyint",
01992                            "Number of 'nearbyint' calls simplified") {}
01993   
01994   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
01995 #ifdef HAVE_NEARBYINTF
01996     // If this is a float argument passed in, convert to nearbyintf.
01997     if (ShrinkFunctionToFloatVersion(CI, SLC,&SimplifyLibCalls::get_nearbyintf))
01998       return true;
01999 #endif
02000     return false; // opt failed
02001   }
02002 } NearByIntOptimizer;
02003 
02004 /// A function to compute the length of a null-terminated constant array of
02005 /// integers.  This function can't rely on the size of the constant array
02006 /// because there could be a null terminator in the middle of the array.
02007 /// We also have to bail out if we find a non-integer constant initializer
02008 /// of one of the elements or if there is no null-terminator. The logic
02009 /// below checks each of these conditions and will return true only if all
02010 /// conditions are met. In that case, the \p len parameter is set to the length
02011 /// of the null-terminated string. If false is returned, the conditions were
02012 /// not met and len is set to 0.
02013 /// @brief Get the length of a constant string (null-terminated array).
02014 bool getConstantStringLength(Value *V, uint64_t &len, ConstantArray **CA) {
02015   assert(V != 0 && "Invalid args to getConstantStringLength");
02016   len = 0; // make sure we initialize this
02017   User* GEP = 0;
02018   // If the value is not a GEP instruction nor a constant expression with a
02019   // GEP instruction, then return false because ConstantArray can't occur
02020   // any other way
02021   if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V))
02022     GEP = GEPI;
02023   else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V))
02024     if (CE->getOpcode() == Instruction::GetElementPtr)
02025       GEP = CE;
02026     else
02027       return false;
02028   else
02029     return false;
02030 
02031   // Make sure the GEP has exactly three arguments.
02032   if (GEP->getNumOperands() != 3)
02033     return false;
02034 
02035   // Check to make sure that the first operand of the GEP is an integer and
02036   // has value 0 so that we are sure we're indexing into the initializer.
02037   if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
02038     if (!op1->isNullValue())
02039       return false;
02040   } else
02041     return false;
02042 
02043   // Ensure that the second operand is a ConstantInt. If it isn't then this
02044   // GEP is wonky and we're not really sure what were referencing into and
02045   // better of not optimizing it. While we're at it, get the second index
02046   // value. We'll need this later for indexing the ConstantArray.
02047   uint64_t start_idx = 0;
02048   if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
02049     start_idx = CI->getRawValue();
02050   else
02051     return false;
02052 
02053   // The GEP instruction, constant or instruction, must reference a global
02054   // variable that is a constant and is initialized. The referenced constant
02055   // initializer is the array that we'll use for optimization.
02056   GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
02057   if (!GV || !GV->isConstant() || !GV->hasInitializer())
02058     return false;
02059 
02060   // Get the initializer.
02061   Constant* INTLZR = GV->getInitializer();
02062 
02063   // Handle the ConstantAggregateZero case
02064   if (ConstantAggregateZero *CAZ = dyn_cast<ConstantAggregateZero>(INTLZR)) {
02065     // This is a degenerate case. The initializer is constant zero so the
02066     // length of the string must be zero.
02067     len = 0;
02068     return true;
02069   }
02070 
02071   // Must be a Constant Array
02072   ConstantArray* A = dyn_cast<ConstantArray>(INTLZR);
02073   if (!A)
02074     return false;
02075 
02076   // Get the number of elements in the array
02077   uint64_t max_elems = A->getType()->getNumElements();
02078 
02079   // Traverse the constant array from start_idx (derived above) which is
02080   // the place the GEP refers to in the array.
02081   for (len = start_idx; len < max_elems; len++) {
02082     if (ConstantInt *CI = dyn_cast<ConstantInt>(A->getOperand(len))) {
02083       // Check for the null terminator
02084       if (CI->isNullValue())
02085         break; // we found end of string
02086     } else
02087       return false; // This array isn't suitable, non-int initializer
02088   }
02089   
02090   if (len >= max_elems)
02091     return false; // This array isn't null terminated
02092 
02093   // Subtract out the initial value from the length
02094   len -= start_idx;
02095   if (CA)
02096     *CA = A;
02097   return true; // success!
02098 }
02099 
02100 /// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*,
02101 /// inserting the cast before IP, and return the cast.
02102 /// @brief Cast a value to a "C" string.
02103 Value *CastToCStr(Value *V, Instruction &IP) {
02104   const Type *SBPTy = PointerType::get(Type::SByteTy);
02105   if (V->getType() != SBPTy)
02106     return new CastInst(V, SBPTy, V->getName(), &IP);
02107   return V;
02108 }
02109 
02110 // TODO:
02111 //   Additional cases that we need to add to this file:
02112 //
02113 // cbrt:
02114 //   * cbrt(expN(X))  -> expN(x/3)
02115 //   * cbrt(sqrt(x))  -> pow(x,1/6)
02116 //   * cbrt(sqrt(x))  -> pow(x,1/9)
02117 //
02118 // cos, cosf, cosl:
02119 //   * cos(-x)  -> cos(x)
02120 //
02121 // exp, expf, expl:
02122 //   * exp(log(x))  -> x
02123 //
02124 // log, logf, logl:
02125 //   * log(exp(x))   -> x
02126 //   * log(x**y)     -> y*log(x)
02127 //   * log(exp(y))   -> y*log(e)
02128 //   * log(exp2(y))  -> y*log(2)
02129 //   * log(exp10(y)) -> y*log(10)
02130 //   * log(sqrt(x))  -> 0.5*log(x)
02131 //   * log(pow(x,y)) -> y*log(x)
02132 //
02133 // lround, lroundf, lroundl:
02134 //   * lround(cnst) -> cnst'
02135 //
02136 // memcmp:
02137 //   * memcmp(x,y,l)   -> cnst
02138 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
02139 //
02140 // memmove:
02141 //   * memmove(d,s,l,a) -> memcpy(d,s,l,a)
02142 //       (if s is a global constant array)
02143 //
02144 // pow, powf, powl:
02145 //   * pow(exp(x),y)  -> exp(x*y)
02146 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
02147 //   * pow(pow(x,y),z)-> pow(x,y*z)
02148 //
02149 // puts:
02150 //   * puts("") -> fputc("\n",stdout) (how do we get "stdout"?)
02151 //
02152 // round, roundf, roundl:
02153 //   * round(cnst) -> cnst'
02154 //
02155 // signbit:
02156 //   * signbit(cnst) -> cnst'
02157 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
02158 //
02159 // sqrt, sqrtf, sqrtl:
02160 //   * sqrt(expN(x))  -> expN(x*0.5)
02161 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
02162 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
02163 //
02164 // stpcpy:
02165 //   * stpcpy(str, "literal") ->
02166 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
02167 // strrchr:
02168 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
02169 //      (if c is a constant integer and s is a constant string)
02170 //   * strrchr(s1,0) -> strchr(s1,0)
02171 //
02172 // strncat:
02173 //   * strncat(x,y,0) -> x
02174 //   * strncat(x,y,0) -> x (if strlen(y) = 0)
02175 //   * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y))
02176 //
02177 // strncpy:
02178 //   * strncpy(d,s,0) -> d
02179 //   * strncpy(d,s,l) -> memcpy(d,s,l,1)
02180 //      (if s and l are constants)
02181 //
02182 // strpbrk:
02183 //   * strpbrk(s,a) -> offset_in_for(s,a)
02184 //      (if s and a are both constant strings)
02185 //   * strpbrk(s,"") -> 0
02186 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
02187 //
02188 // strspn, strcspn:
02189 //   * strspn(s,a)   -> const_int (if both args are constant)
02190 //   * strspn("",a)  -> 0
02191 //   * strspn(s,"")  -> 0
02192 //   * strcspn(s,a)  -> const_int (if both args are constant)
02193 //   * strcspn("",a) -> 0
02194 //   * strcspn(s,"") -> strlen(a)
02195 //
02196 // strstr:
02197 //   * strstr(x,x)  -> x
02198 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
02199 //       (if s1 and s2 are constant strings)
02200 //
02201 // tan, tanf, tanl:
02202 //   * tan(atan(x)) -> x
02203 //
02204 // trunc, truncf, truncl:
02205 //   * trunc(cnst) -> cnst'
02206 //
02207 //
02208 }