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