lib/Transforms/IPO/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Reid Spencer and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a module pass that applies a variety of small
  11 // optimizations for calls to specific well-known function calls (e.g. runtime
  12 // library functions). For example, a call to the function "exit(3)" that
  13 // occurs within the main() function can be transformed into a simple "return 3"
  14 // instruction. Any optimization that takes this form (replace call to library
  15 // function with simpler code that provides the same result) belongs in this
  16 // file.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "simplify-libcalls"
  21 #include "llvm/Constants.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Module.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/ADT/hash_map"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/Config/config.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Target/TargetData.h"
  32 #include "llvm/Transforms/IPO.h"
  33 using namespace llvm;
  34
  35 /// This statistic keeps track of the total number of library calls that have
  36 /// been simplified regardless of which call it is.
  37 STATISTIC(SimplifiedLibCalls, "Number of library calls simplified");
  38
  39 namespace {
  40   // Forward declarations
  41   class LibCallOptimization;
  42   class SimplifyLibCalls;
  43
  44 /// This list is populated by the constructor for LibCallOptimization class.
  45 /// Therefore all subclasses are registered here at static initialization time
  46 /// and this list is what the SimplifyLibCalls pass uses to apply the individual
  47 /// optimizations to the call sites.
  48 /// @brief The list of optimizations deriving from LibCallOptimization
  49 static LibCallOptimization *OptList = 0;
  50
  51 /// This class is the abstract base class for the set of optimizations that
  52 /// corresponds to one library call. The SimplifyLibCalls pass will call the
  53 /// ValidateCalledFunction method to ask the optimization if a given Function
  54 /// is the kind that the optimization can handle. If the subclass returns true,
  55 /// then SImplifyLibCalls will also call the OptimizeCall method to perform,
  56 /// or attempt to perform, the optimization(s) for the library call. Otherwise,
  57 /// OptimizeCall won't be called. Subclasses are responsible for providing the
  58 /// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization
  59 /// constructor. This is used to efficiently select which call instructions to
  60 /// optimize. The criteria for a "lib call" is "anything with well known
  61 /// semantics", typically a library function that is defined by an international
  62 /// standard. Because the semantics are well known, the optimizations can
  63 /// generally short-circuit actually calling the function if there's a simpler
  64 /// way (e.g. strlen(X) can be reduced to a constant if X is a constant global).
  65 /// @brief Base class for library call optimizations
  66 class VISIBILITY_HIDDEN LibCallOptimization {
  67   LibCallOptimization **Prev, *Next;
  68   const char *FunctionName; ///< Name of the library call we optimize
  69 #ifndef NDEBUG
  70   Statistic occurrences; ///< debug statistic (-debug-only=simplify-libcalls)
  71 #endif
  72 public:
  73   /// The \p fname argument must be the name of the library function being
  74   /// optimized by the subclass.
  75   /// @brief Constructor that registers the optimization.
  76   LibCallOptimization(const char *FName, const char *Description)
  77     : FunctionName(FName) {
  78
  79 #ifndef NDEBUG
  80     occurrences.construct("simplify-libcalls", Description);
  81 #endif
  82     // Register this optimizer in the list of optimizations.
  83     Next = OptList;
  84     OptList = this;
  85     Prev = &OptList;
  86     if (Next) Next->Prev = &Next;
  87   }
  88
  89   /// getNext - All libcall optimizations are chained together into a list,
  90   /// return the next one in the list.
  91   LibCallOptimization *getNext() { return Next; }
  92
  93   /// @brief Deregister from the optlist
  94   virtual ~LibCallOptimization() {
  95     *Prev = Next;
  96     if (Next) Next->Prev = Prev;
  97   }
  98
  99   /// The implementation of this function in subclasses should determine if
 100   /// \p F is suitable for the optimization. This method is called by
 101   /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
 102   /// sites of such a function if that function is not suitable in the first
 103   /// place.  If the called function is suitabe, this method should return true;
 104   /// false, otherwise. This function should also perform any lazy
 105   /// initialization that the LibCallOptimization needs to do, if its to return
 106   /// true. This avoids doing initialization until the optimizer is actually
 107   /// going to be called upon to do some optimization.
 108   /// @brief Determine if the function is suitable for optimization
 109   virtual bool ValidateCalledFunction(
 110     const Function* F,    ///< The function that is the target of call sites
 111     SimplifyLibCalls& SLC ///< The pass object invoking us
 112   ) = 0;
 113
 114   /// The implementations of this function in subclasses is the heart of the
 115   /// SimplifyLibCalls algorithm. Sublcasses of this class implement
 116   /// OptimizeCall to determine if (a) the conditions are right for optimizing
 117   /// the call and (b) to perform the optimization. If an action is taken
 118   /// against ci, the subclass is responsible for returning true and ensuring
 119   /// that ci is erased from its parent.
 120   /// @brief Optimize a call, if possible.
 121   virtual bool OptimizeCall(
 122     CallInst* ci,          ///< The call instruction that should be optimized.
 123     SimplifyLibCalls& SLC  ///< The pass object invoking us
 124   ) = 0;
 125
 126   /// @brief Get the name of the library call being optimized
 127   const char *getFunctionName() const { return FunctionName; }
 128
 129   bool ReplaceCallWith(CallInst *CI, Value *V) {
 130     if (!CI->use_empty())
 131       CI->replaceAllUsesWith(V);
 132     CI->eraseFromParent();
 133     return true;
 134   }
 135
 136   /// @brief Called by SimplifyLibCalls to update the occurrences statistic.
 137   void succeeded() {
 138 #ifndef NDEBUG
 139     DEBUG(++occurrences);
 140 #endif
 141   }
 142 };
 143
 144 /// This class is an LLVM Pass that applies each of the LibCallOptimization
 145 /// instances to all the call sites in a module, relatively efficiently. The
 146 /// purpose of this pass is to provide optimizations for calls to well-known
 147 /// functions with well-known semantics, such as those in the c library. The
 148 /// class provides the basic infrastructure for handling runOnModule.  Whenever
 149 /// this pass finds a function call, it asks the appropriate optimizer to
 150 /// validate the call (ValidateLibraryCall). If it is validated, then
 151 /// the OptimizeCall method is also called.
 152 /// @brief A ModulePass for optimizing well-known function calls.
 153 class VISIBILITY_HIDDEN SimplifyLibCalls : public ModulePass {
 154 public:
 155   /// We need some target data for accurate signature details that are
 156   /// target dependent. So we require target data in our AnalysisUsage.
 157   /// @brief Require TargetData from AnalysisUsage.
 158   virtual void getAnalysisUsage(AnalysisUsage& Info) const {
 159     // Ask that the TargetData analysis be performed before us so we can use
 160     // the target data.
 161     Info.addRequired<TargetData>();
 162   }
 163
 164   /// For this pass, process all of the function calls in the module, calling
 165   /// ValidateLibraryCall and OptimizeCall as appropriate.
 166   /// @brief Run all the lib call optimizations on a Module.
 167   virtual bool runOnModule(Module &M) {
 168     reset(M);
 169
 170     bool result = false;
 171     hash_map<std::string, LibCallOptimization*> OptznMap;
 172     for (LibCallOptimization *Optzn = OptList; Optzn; Optzn = Optzn->getNext())
 173       OptznMap[Optzn->getFunctionName()] = Optzn;
 174
 175     // The call optimizations can be recursive. That is, the optimization might
 176     // generate a call to another function which can also be optimized. This way
 177     // we make the LibCallOptimization instances very specific to the case they
 178     // handle. It also means we need to keep running over the function calls in
 179     // the module until we don't get any more optimizations possible.
 180     bool found_optimization = false;
 181     do {
 182       found_optimization = false;
 183       for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
 184         // All the "well-known" functions are external and have external linkage
 185         // because they live in a runtime library somewhere and were (probably)
 186         // not compiled by LLVM.  So, we only act on external functions that
 187         // have external or dllimport linkage and non-empty uses.
 188         if (!FI->isDeclaration() ||
 189             !(FI->hasExternalLinkage() || FI->hasDLLImportLinkage()) ||
 190             FI->use_empty())
 191           continue;
 192
 193         // Get the optimization class that pertains to this function
 194         hash_map<std::string, LibCallOptimization*>::iterator OMI =
 195           OptznMap.find(FI->getName());
 196         if (OMI == OptznMap.end()) continue;
 197
 198         LibCallOptimization *CO = OMI->second;
 199
 200         // Make sure the called function is suitable for the optimization
 201         if (!CO->ValidateCalledFunction(FI, *this))
 202           continue;
 203
 204         // Loop over each of the uses of the function
 205         for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
 206              UI != UE ; ) {
 207           // If the use of the function is a call instruction
 208           if (CallInst* CI = dyn_cast<CallInst>(*UI++)) {
 209             // Do the optimization on the LibCallOptimization.
 210             if (CO->OptimizeCall(CI, *this)) {
 211               ++SimplifiedLibCalls;
 212               found_optimization = result = true;
 213               CO->succeeded();
 214             }
 215           }
 216         }
 217       }
 218     } while (found_optimization);
 219
 220     return result;
 221   }
 222
 223   /// @brief Return the *current* module we're working on.
 224   Module* getModule() const { return M; }
 225
 226   /// @brief Return the *current* target data for the module we're working on.
 227   TargetData* getTargetData() const { return TD; }
 228
 229   /// @brief Return the size_t type -- syntactic shortcut
 230   const Type* getIntPtrType() const { return TD->getIntPtrType(); }
 231
 232   /// @brief Return a Function* for the putchar libcall
 233   Constant *get_putchar() {
 234     if (!putchar_func)
 235       putchar_func =
 236         M->getOrInsertFunction("putchar", Type::Int32Ty, Type::Int32Ty, NULL);
 237     return putchar_func;
 238   }
 239
 240   /// @brief Return a Function* for the puts libcall
 241   Constant *get_puts() {
 242     if (!puts_func)
 243       puts_func = M->getOrInsertFunction("puts", Type::Int32Ty,
 244                                          PointerType::get(Type::Int8Ty),
 245                                          NULL);
 246     return puts_func;
 247   }
 248
 249   /// @brief Return a Function* for the fputc libcall
 250   Constant *get_fputc(const Type* FILEptr_type) {
 251     if (!fputc_func)
 252       fputc_func = M->getOrInsertFunction("fputc", Type::Int32Ty, Type::Int32Ty,
 253                                           FILEptr_type, NULL);
 254     return fputc_func;
 255   }
 256
 257   /// @brief Return a Function* for the fputs libcall
 258   Constant *get_fputs(const Type* FILEptr_type) {
 259     if (!fputs_func)
 260       fputs_func = M->getOrInsertFunction("fputs", Type::Int32Ty,
 261                                           PointerType::get(Type::Int8Ty),
 262                                           FILEptr_type, NULL);
 263     return fputs_func;
 264   }
 265
 266   /// @brief Return a Function* for the fwrite libcall
 267   Constant *get_fwrite(const Type* FILEptr_type) {
 268     if (!fwrite_func)
 269       fwrite_func = M->getOrInsertFunction("fwrite", TD->getIntPtrType(),
 270                                            PointerType::get(Type::Int8Ty),
 271                                            TD->getIntPtrType(),
 272                                            TD->getIntPtrType(),
 273                                            FILEptr_type, NULL);
 274     return fwrite_func;
 275   }
 276
 277   /// @brief Return a Function* for the sqrt libcall
 278   Constant *get_sqrt() {
 279     if (!sqrt_func)
 280       sqrt_func = M->getOrInsertFunction("sqrt", Type::DoubleTy,
 281                                          Type::DoubleTy, NULL);
 282     return sqrt_func;
 283   }
 284
 285   /// @brief Return a Function* for the strcpy libcall
 286   Constant *get_strcpy() {
 287     if (!strcpy_func)
 288       strcpy_func = M->getOrInsertFunction("strcpy",
 289                                            PointerType::get(Type::Int8Ty),
 290                                            PointerType::get(Type::Int8Ty),
 291                                            PointerType::get(Type::Int8Ty),
 292                                            NULL);
 293     return strcpy_func;
 294   }
 295
 296   /// @brief Return a Function* for the strlen libcall
 297   Constant *get_strlen() {
 298     if (!strlen_func)
 299       strlen_func = M->getOrInsertFunction("strlen", TD->getIntPtrType(),
 300                                            PointerType::get(Type::Int8Ty),
 301                                            NULL);
 302     return strlen_func;
 303   }
 304
 305   /// @brief Return a Function* for the memchr libcall
 306   Constant *get_memchr() {
 307     if (!memchr_func)
 308       memchr_func = M->getOrInsertFunction("memchr",
 309                                            PointerType::get(Type::Int8Ty),
 310                                            PointerType::get(Type::Int8Ty),
 311                                            Type::Int32Ty, TD->getIntPtrType(),
 312                                            NULL);
 313     return memchr_func;
 314   }
 315
 316   /// @brief Return a Function* for the memcpy libcall
 317   Constant *get_memcpy() {
 318     if (!memcpy_func) {
 319       const Type *SBP = PointerType::get(Type::Int8Ty);
 320       const char *N = TD->getIntPtrType() == Type::Int32Ty ?
 321                             "llvm.memcpy.i32" : "llvm.memcpy.i64";
 322       memcpy_func = M->getOrInsertFunction(N, Type::VoidTy, SBP, SBP,
 323                                            TD->getIntPtrType(), Type::Int32Ty,
 324                                            NULL);
 325     }
 326     return memcpy_func;
 327   }
 328
 329   Constant *getUnaryFloatFunction(const char *Name, Constant *&Cache) {
 330     if (!Cache)
 331       Cache = M->getOrInsertFunction(Name, Type::FloatTy, Type::FloatTy, NULL);
 332     return Cache;
 333   }
 334
 335   Constant *get_floorf() { return getUnaryFloatFunction("floorf", floorf_func);}
 336   Constant *get_ceilf()  { return getUnaryFloatFunction( "ceilf",  ceilf_func);}
 337   Constant *get_roundf() { return getUnaryFloatFunction("roundf", roundf_func);}
 338   Constant *get_rintf()  { return getUnaryFloatFunction( "rintf",  rintf_func);}
 339   Constant *get_nearbyintf() { return getUnaryFloatFunction("nearbyintf",
 340                                                             nearbyintf_func); }
 341 private:
 342   /// @brief Reset our cached data for a new Module
 343   void reset(Module& mod) {
 344     M = &mod;
 345     TD = &getAnalysis<TargetData>();
 346     putchar_func = 0;
 347     puts_func = 0;
 348     fputc_func = 0;
 349     fputs_func = 0;
 350     fwrite_func = 0;
 351     memcpy_func = 0;
 352     memchr_func = 0;
 353     sqrt_func   = 0;
 354     strcpy_func = 0;
 355     strlen_func = 0;
 356     floorf_func = 0;
 357     ceilf_func = 0;
 358     roundf_func = 0;
 359     rintf_func = 0;
 360     nearbyintf_func = 0;
 361   }
 362
 363 private:
 364   /// Caches for function pointers.
 365   Constant *putchar_func, *puts_func;
 366   Constant *fputc_func, *fputs_func, *fwrite_func;
 367   Constant *memcpy_func, *memchr_func;
 368   Constant *sqrt_func;
 369   Constant *strcpy_func, *strlen_func;
 370   Constant *floorf_func, *ceilf_func, *roundf_func;
 371   Constant *rintf_func, *nearbyintf_func;
 372   Module *M;             ///< Cached Module
 373   TargetData *TD;        ///< Cached TargetData
 374 };
 375
 376 // Register the pass
 377 RegisterPass<SimplifyLibCalls>
 378 X("simplify-libcalls", "Simplify well-known library calls");
 379
 380 } // anonymous namespace
 381
 382 // The only public symbol in this file which just instantiates the pass object
 383 ModulePass *llvm::createSimplifyLibCallsPass() {
 384   return new SimplifyLibCalls();
 385 }
 386
 387 // Classes below here, in the anonymous namespace, are all subclasses of the
 388 // LibCallOptimization class, each implementing all optimizations possible for a
 389 // single well-known library call. Each has a static singleton instance that
 390 // auto registers it into the "optlist" global above.
 391 namespace {
 392
 393 // Forward declare utility functions.
 394 static bool GetConstantStringInfo(Value *V, std::string &Str);
 395 static Value *CastToCStr(Value *V, Instruction *IP);
 396
 397 /// This LibCallOptimization will find instances of a call to "exit" that occurs
 398 /// within the "main" function and change it to a simple "ret" instruction with
 399 /// the same value passed to the exit function. When this is done, it splits the
 400 /// basic block at the exit(3) call and deletes the call instruction.
 401 /// @brief Replace calls to exit in main with a simple return
 402 struct VISIBILITY_HIDDEN ExitInMainOptimization : public LibCallOptimization {
 403   ExitInMainOptimization() : LibCallOptimization("exit",
 404       "Number of 'exit' calls simplified") {}
 405
 406   // Make sure the called function looks like exit (int argument, int return
 407   // type, external linkage, not varargs).
 408   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 409     return F->arg_size() >= 1 && F->arg_begin()->getType()->isInteger();
 410   }
 411
 412   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
 413     // To be careful, we check that the call to exit is coming from "main", that
 414     // main has external linkage, and the return type of main and the argument
 415     // to exit have the same type.
 416     Function *from = ci->getParent()->getParent();
 417     if (from->hasExternalLinkage())
 418       if (from->getReturnType() == ci->getOperand(1)->getType())
 419         if (from->getName() == "main") {
 420           // Okay, time to actually do the optimization. First, get the basic
 421           // block of the call instruction
 422           BasicBlock* bb = ci->getParent();
 423
 424           // Create a return instruction that we'll replace the call with.
 425           // Note that the argument of the return is the argument of the call
 426           // instruction.
 427           new ReturnInst(ci->getOperand(1), ci);
 428
 429           // Split the block at the call instruction which places it in a new
 430           // basic block.
 431           bb->splitBasicBlock(ci);
 432
 433           // The block split caused a branch instruction to be inserted into
 434           // the end of the original block, right after the return instruction
 435           // that we put there. That's not a valid block, so delete the branch
 436           // instruction.
 437           bb->getInstList().pop_back();
 438
 439           // Now we can finally get rid of the call instruction which now lives
 440           // in the new basic block.
 441           ci->eraseFromParent();
 442
 443           // Optimization succeeded, return true.
 444           return true;
 445         }
 446     // We didn't pass the criteria for this optimization so return false
 447     return false;
 448   }
 449 } ExitInMainOptimizer;
 450
 451 /// This LibCallOptimization will simplify a call to the strcat library
 452 /// function. The simplification is possible only if the string being
 453 /// concatenated is a constant array or a constant expression that results in
 454 /// a constant string. In this case we can replace it with strlen + llvm.memcpy
 455 /// of the constant string. Both of these calls are further reduced, if possible
 456 /// on subsequent passes.
 457 /// @brief Simplify the strcat library function.
 458 struct VISIBILITY_HIDDEN StrCatOptimization : public LibCallOptimization {
 459 public:
 460   /// @brief Default constructor
 461   StrCatOptimization() : LibCallOptimization("strcat",
 462       "Number of 'strcat' calls simplified") {}
 463
 464 public:
 465
 466   /// @brief Make sure that the "strcat" function has the right prototype
 467   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 468     const FunctionType *FT = F->getFunctionType();
 469     return FT->getNumParams() == 2 &&
 470            FT->getReturnType() == PointerType::get(Type::Int8Ty) &&
 471            FT->getParamType(0) == FT->getReturnType() &&
 472            FT->getParamType(1) == FT->getReturnType();
 473   }
 474
 475   /// @brief Optimize the strcat library function
 476   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 477     // Extract some information from the instruction
 478     Value *Dst = CI->getOperand(1);
 479     Value *Src = CI->getOperand(2);
 480
 481     // Extract the initializer (while making numerous checks) from the
 482     // source operand of the call to strcat.
 483     std::string SrcStr;
 484     if (!GetConstantStringInfo(Src, SrcStr))
 485       return false;
 486
 487     // Handle the simple, do-nothing case
 488     if (SrcStr.empty())
 489       return ReplaceCallWith(CI, Dst);
 490
 491     // We need to find the end of the destination string.  That's where the
 492     // memory is to be moved to. We just generate a call to strlen.
 493     CallInst *DstLen = new CallInst(SLC.get_strlen(), Dst,
 494                                     Dst->getName()+".len", CI);
 495
 496     // Now that we have the destination's length, we must index into the
 497     // destination's pointer to get the actual memcpy destination (end of
 498     // the string .. we're concatenating).
 499     Dst = new GetElementPtrInst(Dst, DstLen, Dst->getName()+".indexed", CI);
 500
 501     // We have enough information to now generate the memcpy call to
 502     // do the concatenation for us.
 503     Value *Vals[] = {
 504       Dst, Src,
 505       ConstantInt::get(SLC.getIntPtrType(), SrcStr.size()+1), // copy nul byte.
 506       ConstantInt::get(Type::Int32Ty, 1)  // alignment
 507     };
 508     new CallInst(SLC.get_memcpy(), Vals, 4, "", CI);
 509
 510     return ReplaceCallWith(CI, Dst);
 511   }
 512 } StrCatOptimizer;
 513
 514 /// This LibCallOptimization will simplify a call to the strchr library
 515 /// function.  It optimizes out cases where the arguments are both constant
 516 /// and the result can be determined statically.
 517 /// @brief Simplify the strcmp library function.
 518 struct VISIBILITY_HIDDEN StrChrOptimization : public LibCallOptimization {
 519 public:
 520   StrChrOptimization() : LibCallOptimization("strchr",
 521       "Number of 'strchr' calls simplified") {}
 522
 523   /// @brief Make sure that the "strchr" function has the right prototype
 524   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 525     const FunctionType *FT = F->getFunctionType();
 526     return FT->getNumParams() == 2 &&
 527            FT->getReturnType() == PointerType::get(Type::Int8Ty) &&
 528            FT->getParamType(0) == FT->getReturnType() &&
 529            isa<IntegerType>(FT->getParamType(1));
 530   }
 531
 532   /// @brief Perform the strchr optimizations
 533   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 534     // Check that the first argument to strchr is a constant array of sbyte.
 535     std::string Str;
 536     if (!GetConstantStringInfo(CI->getOperand(1), Str))
 537       return false;
 538
 539     // If the second operand is not constant, just lower this to memchr since we
 540     // know the length of the input string.
 541     ConstantInt *CSI = dyn_cast<ConstantInt>(CI->getOperand(2));
 542     if (!CSI) {
 543       Value *Args[3] = {
 544         CI->getOperand(1),
 545         CI->getOperand(2),
 546         ConstantInt::get(SLC.getIntPtrType(), Str.size()+1)
 547       };
 548       return ReplaceCallWith(CI, new CallInst(SLC.get_memchr(), Args, 3,
 549                                               CI->getName(), CI));
 550     }
 551
 552     // strchr can find the nul character.
 553     Str += '\0';
 554
 555     // Get the character we're looking for
 556     char CharValue = CSI->getSExtValue();
 557
 558     // Compute the offset
 559     uint64_t i = 0;
 560     while (1) {
 561       if (i == Str.size())    // Didn't find the char.  strchr returns null.
 562         return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
 563       // Did we find our match?
 564       if (Str[i] == CharValue)
 565         break;
 566       ++i;
 567     }
 568
 569     // strchr(s+n,c)  -> gep(s+n+i,c)
 570     //    (if c is a constant integer and s is a constant string)
 571     Value *Idx = ConstantInt::get(Type::Int64Ty, i);
 572     Value *GEP = new GetElementPtrInst(CI->getOperand(1), Idx,
 573                                        CI->getOperand(1)->getName() +
 574                                        ".strchr", CI);
 575     return ReplaceCallWith(CI, GEP);
 576   }
 577 } StrChrOptimizer;
 578
 579 /// This LibCallOptimization will simplify a call to the strcmp library
 580 /// function.  It optimizes out cases where one or both arguments are constant
 581 /// and the result can be determined statically.
 582 /// @brief Simplify the strcmp library function.
 583 struct VISIBILITY_HIDDEN StrCmpOptimization : public LibCallOptimization {
 584 public:
 585   StrCmpOptimization() : LibCallOptimization("strcmp",
 586       "Number of 'strcmp' calls simplified") {}
 587
 588   /// @brief Make sure that the "strcmp" function has the right prototype
 589   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 590     const FunctionType *FT = F->getFunctionType();
 591     return FT->getReturnType() == Type::Int32Ty && FT->getNumParams() == 2 &&
 592            FT->getParamType(0) == FT->getParamType(1) &&
 593            FT->getParamType(0) == PointerType::get(Type::Int8Ty);
 594   }
 595
 596   /// @brief Perform the strcmp optimization
 597   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 598     // First, check to see if src and destination are the same. If they are,
 599     // then the optimization is to replace the CallInst with a constant 0
 600     // because the call is a no-op.
 601     Value *Str1P = CI->getOperand(1);
 602     Value *Str2P = CI->getOperand(2);
 603     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 604       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
 605
 606     std::string Str1;
 607     if (!GetConstantStringInfo(Str1P, Str1))
 608       return false;
 609     if (Str1.empty()) {
 610       // strcmp("", x) -> *x
 611       Value *V = new LoadInst(Str2P, CI->getName()+".load", CI);
 612       V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
 613       return ReplaceCallWith(CI, V);
 614     }
 615
 616     std::string Str2;
 617     if (!GetConstantStringInfo(Str2P, Str2))
 618       return false;
 619     if (Str2.empty()) {
 620       // strcmp(x,"") -> *x
 621       Value *V = new LoadInst(Str1P, CI->getName()+".load", CI);
 622       V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
 623       return ReplaceCallWith(CI, V);
 624     }
 625
 626     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 627     int R = strcmp(Str1.c_str(), Str2.c_str());
 628     return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), R));
 629   }
 630 } StrCmpOptimizer;
 631
 632 /// This LibCallOptimization will simplify a call to the strncmp library
 633 /// function.  It optimizes out cases where one or both arguments are constant
 634 /// and the result can be determined statically.
 635 /// @brief Simplify the strncmp library function.
 636 struct VISIBILITY_HIDDEN StrNCmpOptimization : public LibCallOptimization {
 637 public:
 638   StrNCmpOptimization() : LibCallOptimization("strncmp",
 639       "Number of 'strncmp' calls simplified") {}
 640
 641   /// @brief Make sure that the "strncmp" function has the right prototype
 642   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 643     const FunctionType *FT = F->getFunctionType();
 644     return FT->getReturnType() == Type::Int32Ty && FT->getNumParams() == 3 &&
 645            FT->getParamType(0) == FT->getParamType(1) &&
 646            FT->getParamType(0) == PointerType::get(Type::Int8Ty) &&
 647            isa<IntegerType>(FT->getParamType(2));
 648     return false;
 649   }
 650
 651   /// @brief Perform the strncmp optimization
 652   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 653     // First, check to see if src and destination are the same. If they are,
 654     // then the optimization is to replace the CallInst with a constant 0
 655     // because the call is a no-op.
 656     Value *Str1P = CI->getOperand(1);
 657     Value *Str2P = CI->getOperand(2);
 658     if (Str1P == Str2P)  // strncmp(x,x, n)  -> 0
 659       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
 660
 661     // Check the length argument, if it is Constant zero then the strings are
 662     // considered equal.
 663     uint64_t Length;
 664     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
 665       Length = LengthArg->getZExtValue();
 666     else
 667       return false;
 668
 669     if (Length == 0) // strncmp(x,y,0)   -> 0
 670       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
 671
 672     std::string Str1;
 673     if (!GetConstantStringInfo(Str1P, Str1))
 674       return false;
 675     if (Str1.empty()) {
 676       // strncmp("", x, n) -> *x
 677       Value *V = new LoadInst(Str2P, CI->getName()+".load", CI);
 678       V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
 679       return ReplaceCallWith(CI, V);
 680     }
 681
 682     std::string Str2;
 683     if (!GetConstantStringInfo(Str2P, Str2))
 684       return false;
 685     if (Str2.empty()) {
 686       // strncmp(x, "", n) -> *x
 687       Value *V = new LoadInst(Str1P, CI->getName()+".load", CI);
 688       V = new ZExtInst(V, CI->getType(), CI->getName()+".int", CI);
 689       return ReplaceCallWith(CI, V);
 690     }
 691
 692     // strncmp(x, y, n)  -> cnst  (if both x and y are constant strings)
 693     int R = strncmp(Str1.c_str(), Str2.c_str(), Length);
 694     return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), R));
 695   }
 696 } StrNCmpOptimizer;
 697
 698 /// This LibCallOptimization will simplify a call to the strcpy library
 699 /// function.  Two optimizations are possible:
 700 /// (1) If src and dest are the same and not volatile, just return dest
 701 /// (2) If the src is a constant then we can convert to llvm.memmove
 702 /// @brief Simplify the strcpy library function.
 703 struct VISIBILITY_HIDDEN StrCpyOptimization : public LibCallOptimization {
 704 public:
 705   StrCpyOptimization() : LibCallOptimization("strcpy",
 706       "Number of 'strcpy' calls simplified") {}
 707
 708   /// @brief Make sure that the "strcpy" function has the right prototype
 709   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 710     const FunctionType *FT = F->getFunctionType();
 711     return FT->getNumParams() == 2 &&
 712            FT->getParamType(0) == FT->getParamType(1) &&
 713            FT->getReturnType() == FT->getParamType(0) &&
 714            FT->getParamType(0) == PointerType::get(Type::Int8Ty);
 715   }
 716
 717   /// @brief Perform the strcpy optimization
 718   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 719     // First, check to see if src and destination are the same. If they are,
 720     // then the optimization is to replace the CallInst with the destination
 721     // because the call is a no-op. Note that this corresponds to the
 722     // degenerate strcpy(X,X) case which should have "undefined" results
 723     // according to the C specification. However, it occurs sometimes and
 724     // we optimize it as a no-op.
 725     Value *Dst = CI->getOperand(1);
 726     Value *Src = CI->getOperand(2);
 727     if (Dst == Src) {
 728       // strcpy(x, x) -> x
 729       return ReplaceCallWith(CI, Dst);
 730     }
 731
 732     // Get the length of the constant string referenced by the Src operand.
 733     std::string SrcStr;
 734     if (!GetConstantStringInfo(Src, SrcStr))
 735       return false;
 736
 737     // If the constant string's length is zero we can optimize this by just
 738     // doing a store of 0 at the first byte of the destination
 739     if (SrcStr.size() == 0) {
 740       new StoreInst(ConstantInt::get(Type::Int8Ty, 0), Dst, CI);
 741       return ReplaceCallWith(CI, Dst);
 742     }
 743
 744     // We have enough information to now generate the memcpy call to
 745     // do the concatenation for us.
 746     Value *MemcpyOps[] = {
 747       Dst, Src, // Pass length including nul byte.
 748       ConstantInt::get(SLC.getIntPtrType(), SrcStr.size()+1),
 749       ConstantInt::get(Type::Int32Ty, 1) // alignment
 750     };
 751     new CallInst(SLC.get_memcpy(), MemcpyOps, 4, "", CI);
 752
 753     return ReplaceCallWith(CI, Dst);
 754   }
 755 } StrCpyOptimizer;
 756
 757 /// This LibCallOptimization will simplify a call to the strlen library
 758 /// function by replacing it with a constant value if the string provided to
 759 /// it is a constant array.
 760 /// @brief Simplify the strlen library function.
 761 struct VISIBILITY_HIDDEN StrLenOptimization : public LibCallOptimization {
 762   StrLenOptimization() : LibCallOptimization("strlen",
 763       "Number of 'strlen' calls simplified") {}
 764
 765   /// @brief Make sure that the "strlen" function has the right prototype
 766   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
 767     const FunctionType *FT = F->getFunctionType();
 768     return FT->getNumParams() == 1 &&
 769            FT->getParamType(0) == PointerType::get(Type::Int8Ty) &&
 770            isa<IntegerType>(FT->getReturnType());
 771   }
 772
 773   /// @brief Perform the strlen optimization
 774   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
 775     // Make sure we're dealing with an sbyte* here.
 776     Value *Src = CI->getOperand(1);
 777
 778     // Does the call to strlen have exactly one use?
 779     if (CI->hasOneUse()) {
 780       // Is that single use a icmp operator?
 781       if (ICmpInst *Cmp = dyn_cast<ICmpInst>(CI->use_back()))
 782         // Is it compared against a constant integer?
 783         if (ConstantInt *Cst = dyn_cast<ConstantInt>(Cmp->getOperand(1))) {
 784           // If its compared against length 0 with == or !=
 785           if (Cst->getZExtValue() == 0 && Cmp->isEquality()) {
 786             // strlen(x) != 0 -> *x != 0
 787             // strlen(x) == 0 -> *x == 0
 788             Value *V = new LoadInst(Src, Src->getName()+".first", CI);
 789             V = new ICmpInst(Cmp->getPredicate(), V,
 790                              ConstantInt::get(Type::Int8Ty, 0),
 791                              Cmp->getName()+".strlen", CI);
 792             Cmp->replaceAllUsesWith(V);
 793             Cmp->eraseFromParent();
 794             return ReplaceCallWith(CI, 0);  // no uses.
 795           }
 796         }
 797     }
 798
 799     // Get the length of the constant string operand
 800     std::string Str;
 801     if (!GetConstantStringInfo(Src, Str))
 802       return false;
 803
 804     // strlen("xyz") -> 3 (for example)
 805     return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), Str.size()));
 806   }
 807 } StrLenOptimizer;
 808
 809 /// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value
 810 /// is equal or not-equal to zero.
 811 static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) {
 812   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 813        UI != E; ++UI) {
 814     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
 815       if (IC->isEquality())
 816         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
 817           if (C->isNullValue())
 818             continue;
 819     // Unknown instruction.
 820     return false;
 821   }
 822   return true;
 823 }
 824
 825 /// This memcmpOptimization will simplify a call to the memcmp library
 826 /// function.
 827 struct VISIBILITY_HIDDEN memcmpOptimization : public LibCallOptimization {
 828   /// @brief Default Constructor
 829   memcmpOptimization()
 830     : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {}
 831
 832   /// @brief Make sure that the "memcmp" function has the right prototype
 833   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
 834     Function::const_arg_iterator AI = F->arg_begin();
 835     if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false;
 836     if (!isa<PointerType>((++AI)->getType())) return false;
 837     if (!(++AI)->getType()->isInteger()) return false;
 838     if (!F->getReturnType()->isInteger()) return false;
 839     return true;
 840   }
 841
 842   /// Because of alignment and instruction information that we don't have, we
 843   /// leave the bulk of this to the code generators.
 844   ///
 845   /// Note that we could do much more if we could force alignment on otherwise
 846   /// small aligned allocas, or if we could indicate that loads have a small
 847   /// alignment.
 848   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) {
 849     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
 850
 851     // If the two operands are the same, return zero.
 852     if (LHS == RHS) {
 853       // memcmp(s,s,x) -> 0
 854       return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
 855     }
 856
 857     // Make sure we have a constant length.
 858     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
 859     if (!LenC) return false;
 860     uint64_t Len = LenC->getZExtValue();
 861
 862     // If the length is zero, this returns 0.
 863     switch (Len) {
 864     case 0:
 865       // memcmp(s1,s2,0) -> 0
 866       return ReplaceCallWith(CI, Constant::getNullValue(CI->getType()));
 867     case 1: {
 868       // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2
 869       const Type *UCharPtr = PointerType::get(Type::Int8Ty);
 870       CastInst *Op1Cast = CastInst::create(
 871           Instruction::BitCast, LHS, UCharPtr, LHS->getName(), CI);
 872       CastInst *Op2Cast = CastInst::create(
 873           Instruction::BitCast, RHS, UCharPtr, RHS->getName(), CI);
 874       Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI);
 875       Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI);
 876       Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI);
 877       if (RV->getType() != CI->getType())
 878         RV = CastInst::createIntegerCast(RV, CI->getType(), false,
 879                                          RV->getName(), CI);
 880       return ReplaceCallWith(CI, RV);
 881     }
 882     case 2:
 883       if (IsOnlyUsedInEqualsZeroComparison(CI)) {
 884         // TODO: IF both are aligned, use a short load/compare.
 885
 886         // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters
 887         const Type *UCharPtr = PointerType::get(Type::Int8Ty);
 888         CastInst *Op1Cast = CastInst::create(
 889             Instruction::BitCast, LHS, UCharPtr, LHS->getName(), CI);
 890         CastInst *Op2Cast = CastInst::create(
 891             Instruction::BitCast, RHS, UCharPtr, RHS->getName(), CI);
 892         Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI);
 893         Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI);
 894         Value *D1 = BinaryOperator::createSub(S1V1, S2V1,
 895                                               CI->getName()+".d1", CI);
 896         Constant *One = ConstantInt::get(Type::Int32Ty, 1);
 897         Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI);
 898         Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI);
 899         Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI);
 900         Value *S2V2 = new LoadInst(G2, RHS->getName()+".val2", CI);
 901         Value *D2 = BinaryOperator::createSub(S1V2, S2V2,
 902                                               CI->getName()+".d1", CI);
 903         Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI);
 904         if (Or->getType() != CI->getType())
 905           Or = CastInst::createIntegerCast(Or, CI->getType(), false /*ZExt*/,
 906                                            Or->getName(), CI);
 907         return ReplaceCallWith(CI, Or);
 908       }
 909       break;
 910     default:
 911       break;
 912     }
 913
 914     return false;
 915   }
 916 } memcmpOptimizer;
 917
 918
 919 /// This LibCallOptimization will simplify a call to the memcpy library
 920 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
 921 /// bytes depending on the length of the string and the alignment. Additional
 922 /// optimizations are possible in code generation (sequence of immediate store)
 923 /// @brief Simplify the memcpy library function.
 924 struct VISIBILITY_HIDDEN LLVMMemCpyMoveOptzn : public LibCallOptimization {
 925   LLVMMemCpyMoveOptzn(const char* fname, const char* desc)
 926   : LibCallOptimization(fname, desc) {}
 927
 928   /// @brief Make sure that the "memcpy" function has the right prototype
 929   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD) {
 930     // Just make sure this has 4 arguments per LLVM spec.
 931     return (f->arg_size() == 4);
 932   }
 933
 934   /// Because of alignment and instruction information that we don't have, we
 935   /// leave the bulk of this to the code generators. The optimization here just
 936   /// deals with a few degenerate cases where the length of the string and the
 937   /// alignment match the sizes of our intrinsic types so we can do a load and
 938   /// store instead of the memcpy call.
 939   /// @brief Perform the memcpy optimization.
 940   virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& TD) {
 941     // Make sure we have constant int values to work with
 942     ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
 943     if (!LEN)
 944       return false;
 945     ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
 946     if (!ALIGN)
 947       return false;
 948
 949     // If the length is larger than the alignment, we can't optimize
 950     uint64_t len = LEN->getZExtValue();
 951     uint64_t alignment = ALIGN->getZExtValue();
 952     if (alignment == 0)
 953       alignment = 1; // Alignment 0 is identity for alignment 1
 954     if (len > alignment)
 955       return false;
 956
 957     // Get the type we will cast to, based on size of the string
 958     Value* dest = ci->getOperand(1);
 959     Value* src = ci->getOperand(2);
 960     const Type* castType = 0;
 961     switch (len) {
 962       case 0:
 963         // memcpy(d,s,0,a) -> d
 964         return ReplaceCallWith(ci, 0);
 965       case 1: castType = Type::Int8Ty; break;
 966       case 2: castType = Type::Int16Ty; break;
 967       case 4: castType = Type::Int32Ty; break;
 968       case 8: castType = Type::Int64Ty; break;
 969       default:
 970         return false;
 971     }
 972
 973     // Cast source and dest to the right sized primitive and then load/store
 974     CastInst* SrcCast = CastInst::create(Instruction::BitCast,
 975         src, PointerType::get(castType), src->getName()+".cast", ci);
 976     CastInst* DestCast = CastInst::create(Instruction::BitCast,
 977         dest, PointerType::get(castType),dest->getName()+".cast", ci);
 978     LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci);
 979     new StoreInst(LI, DestCast, ci);
 980     return ReplaceCallWith(ci, 0);
 981   }
 982 };
 983
 984 /// This LibCallOptimization will simplify a call to the memcpy/memmove library
 985 /// functions.
 986 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer32("llvm.memcpy.i32",
 987                                     "Number of 'llvm.memcpy' calls simplified");
 988 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer64("llvm.memcpy.i64",
 989                                    "Number of 'llvm.memcpy' calls simplified");
 990 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer32("llvm.memmove.i32",
 991                                    "Number of 'llvm.memmove' calls simplified");
 992 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer64("llvm.memmove.i64",
 993                                    "Number of 'llvm.memmove' calls simplified");
 994
 995 /// This LibCallOptimization will simplify a call to the memset library
 996 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
 997 /// bytes depending on the length argument.
 998 struct VISIBILITY_HIDDEN LLVMMemSetOptimization : public LibCallOptimization {
 999   /// @brief Default Constructor
1000   LLVMMemSetOptimization(const char *Name) : LibCallOptimization(Name,
1001       "Number of 'llvm.memset' calls simplified") {}
1002
1003   /// @brief Make sure that the "memset" function has the right prototype
1004   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
1005     // Just make sure this has 3 arguments per LLVM spec.
1006     return F->arg_size() == 4;
1007   }
1008
1009   /// Because of alignment and instruction information that we don't have, we
1010   /// leave the bulk of this to the code generators. The optimization here just
1011   /// deals with a few degenerate cases where the length parameter is constant
1012   /// and the alignment matches the sizes of our intrinsic types so we can do
1013   /// store instead of the memcpy call. Other calls are transformed into the
1014   /// llvm.memset intrinsic.
1015   /// @brief Perform the memset optimization.
1016   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &TD) {
1017     // Make sure we have constant int values to work with
1018     ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
1019     if (!LEN)
1020       return false;
1021     ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
1022     if (!ALIGN)
1023       return false;
1024
1025     // Extract the length and alignment
1026     uint64_t len = LEN->getZExtValue();
1027     uint64_t alignment = ALIGN->getZExtValue();
1028
1029     // Alignment 0 is identity for alignment 1
1030     if (alignment == 0)
1031       alignment = 1;
1032
1033     // If the length is zero, this is a no-op
1034     if (len == 0) {
1035       // memset(d,c,0,a) -> noop
1036       return ReplaceCallWith(ci, 0);
1037     }
1038
1039     // If the length is larger than the alignment, we can't optimize
1040     if (len > alignment)
1041       return false;
1042
1043     // Make sure we have a constant ubyte to work with so we can extract
1044     // the value to be filled.
1045     ConstantInt* FILL = dyn_cast<ConstantInt>(ci->getOperand(2));
1046     if (!FILL)
1047       return false;
1048     if (FILL->getType() != Type::Int8Ty)
1049       return false;
1050
1051     // memset(s,c,n) -> store s, c (for n=1,2,4,8)
1052
1053     // Extract the fill character
1054     uint64_t fill_char = FILL->getZExtValue();
1055     uint64_t fill_value = fill_char;
1056
1057     // Get the type we will cast to, based on size of memory area to fill, and
1058     // and the value we will store there.
1059     Value* dest = ci->getOperand(1);
1060     const Type* castType = 0;
1061     switch (len) {
1062       case 1:
1063         castType = Type::Int8Ty;
1064         break;
1065       case 2:
1066         castType = Type::Int16Ty;
1067         fill_value |= fill_char << 8;
1068         break;
1069       case 4:
1070         castType = Type::Int32Ty;
1071         fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1072         break;
1073       case 8:
1074         castType = Type::Int64Ty;
1075         fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1076         fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48;
1077         fill_value |= fill_char << 56;
1078         break;
1079       default:
1080         return false;
1081     }
1082
1083     // Cast dest to the right sized primitive and then load/store
1084     CastInst* DestCast = new BitCastInst(dest, PointerType::get(castType),
1085                                          dest->getName()+".cast", ci);
1086     new StoreInst(ConstantInt::get(castType,fill_value),DestCast, ci);
1087     return ReplaceCallWith(ci, 0);
1088   }
1089 };
1090
1091 LLVMMemSetOptimization MemSet32Optimizer("llvm.memset.i32");
1092 LLVMMemSetOptimization MemSet64Optimizer("llvm.memset.i64");
1093
1094
1095 /// This LibCallOptimization will simplify calls to the "pow" library
1096 /// function. It looks for cases where the result of pow is well known and
1097 /// substitutes the appropriate value.
1098 /// @brief Simplify the pow library function.
1099 struct VISIBILITY_HIDDEN PowOptimization : public LibCallOptimization {
1100 public:
1101   /// @brief Default Constructor
1102   PowOptimization() : LibCallOptimization("pow",
1103       "Number of 'pow' calls simplified") {}
1104
1105   /// @brief Make sure that the "pow" function has the right prototype
1106   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1107     // Just make sure this has 2 arguments
1108     return (f->arg_size() == 2);
1109   }
1110
1111   /// @brief Perform the pow optimization.
1112   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1113     const Type *Ty = cast<Function>(ci->getOperand(0))->getReturnType();
1114     Value* base = ci->getOperand(1);
1115     Value* expn = ci->getOperand(2);
1116     if (ConstantFP *Op1 = dyn_cast<ConstantFP>(base)) {
1117       double Op1V = Op1->getValue();
1118       if (Op1V == 1.0) // pow(1.0,x) -> 1.0
1119         return ReplaceCallWith(ci, ConstantFP::get(Ty, 1.0));
1120     }  else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn)) {
1121       double Op2V = Op2->getValue();
1122       if (Op2V == 0.0) {
1123         // pow(x,0.0) -> 1.0
1124         return ReplaceCallWith(ci, ConstantFP::get(Ty,1.0));
1125       } else if (Op2V == 0.5) {
1126         // pow(x,0.5) -> sqrt(x)
1127         CallInst* sqrt_inst = new CallInst(SLC.get_sqrt(), base,
1128             ci->getName()+".pow",ci);
1129         return ReplaceCallWith(ci, sqrt_inst);
1130       } else if (Op2V == 1.0) {
1131         // pow(x,1.0) -> x
1132         return ReplaceCallWith(ci, base);
1133       } else if (Op2V == -1.0) {
1134         // pow(x,-1.0)    -> 1.0/x
1135         Value *div_inst =
1136           BinaryOperator::createFDiv(ConstantFP::get(Ty, 1.0), base,
1137                                      ci->getName()+".pow", ci);
1138         return ReplaceCallWith(ci, div_inst);
1139       }
1140     }
1141     return false; // opt failed
1142   }
1143 } PowOptimizer;
1144
1145 /// This LibCallOptimization will simplify calls to the "printf" library
1146 /// function. It looks for cases where the result of printf is not used and the
1147 /// operation can be reduced to something simpler.
1148 /// @brief Simplify the printf library function.
1149 struct VISIBILITY_HIDDEN PrintfOptimization : public LibCallOptimization {
1150 public:
1151   /// @brief Default Constructor
1152   PrintfOptimization() : LibCallOptimization("printf",
1153       "Number of 'printf' calls simplified") {}
1154
1155   /// @brief Make sure that the "printf" function has the right prototype
1156   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1157     // Just make sure this has at least 1 arguments
1158     return F->arg_size() >= 1;
1159   }
1160
1161   /// @brief Perform the printf optimization.
1162   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1163     // If the call has more than 2 operands, we can't optimize it
1164     if (CI->getNumOperands() != 3)
1165       return false;
1166
1167     // All the optimizations depend on the length of the first argument and the
1168     // fact that it is a constant string array. Check that now
1169     std::string FormatStr;
1170     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
1171       return false;
1172
1173     // Only support %c or "%s\n" for now.
1174     if (FormatStr.size() < 2 || FormatStr[0] != '%')
1175       return false;
1176
1177     // Get the second character and switch on its value
1178     switch (FormatStr[1]) {
1179     default:  return false;
1180     case 's':
1181       if (FormatStr != "%s\n" ||
1182           // TODO: could insert strlen call to compute string length.
1183           !CI->use_empty())
1184         return false;
1185
1186       // printf("%s\n",str) -> puts(str)
1187       new CallInst(SLC.get_puts(), CastToCStr(CI->getOperand(2), CI),
1188                    CI->getName(), CI);
1189       return ReplaceCallWith(CI, 0);
1190     case 'c': {
1191       // printf("%c",c) -> putchar(c)
1192       if (FormatStr.size() != 2)
1193         return false;
1194
1195       Value *V = CI->getOperand(2);
1196       if (!isa<IntegerType>(V->getType()) ||
1197           cast<IntegerType>(V->getType())->getBitWidth() > 32)
1198         return false;
1199
1200       V = CastInst::createZExtOrBitCast(V, Type::Int32Ty, CI->getName()+".int",
1201                                         CI);
1202       new CallInst(SLC.get_putchar(), V, "", CI);
1203       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1204     }
1205     }
1206   }
1207 } PrintfOptimizer;
1208
1209 /// This LibCallOptimization will simplify calls to the "fprintf" library
1210 /// function. It looks for cases where the result of fprintf is not used and the
1211 /// operation can be reduced to something simpler.
1212 /// @brief Simplify the fprintf library function.
1213 struct VISIBILITY_HIDDEN FPrintFOptimization : public LibCallOptimization {
1214 public:
1215   /// @brief Default Constructor
1216   FPrintFOptimization() : LibCallOptimization("fprintf",
1217       "Number of 'fprintf' calls simplified") {}
1218
1219   /// @brief Make sure that the "fprintf" function has the right prototype
1220   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1221     const FunctionType *FT = F->getFunctionType();
1222     return FT->getNumParams() == 2 &&  // two fixed arguments.
1223            FT->getParamType(1) == PointerType::get(Type::Int8Ty) &&
1224            isa<PointerType>(FT->getParamType(0)) &&
1225            isa<IntegerType>(FT->getReturnType());
1226   }
1227
1228   /// @brief Perform the fprintf optimization.
1229   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1230     // If the call has more than 3 operands, we can't optimize it
1231     if (CI->getNumOperands() != 3 && CI->getNumOperands() != 4)
1232       return false;
1233
1234     // All the optimizations depend on the format string.
1235     std::string FormatStr;
1236     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1237       return false;
1238
1239     // If this is just a format string, turn it into fwrite.
1240     if (CI->getNumOperands() == 3) {
1241       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1242         if (FormatStr[i] == '%')
1243           return false; // we found a format specifier
1244
1245       // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file)
1246       const Type *FILEty = CI->getOperand(1)->getType();
1247
1248       Value *FWriteArgs[] = {
1249         CI->getOperand(2),
1250         ConstantInt::get(SLC.getIntPtrType(), FormatStr.size()),
1251         ConstantInt::get(SLC.getIntPtrType(), 1),
1252         CI->getOperand(1)
1253       };
1254       new CallInst(SLC.get_fwrite(FILEty), FWriteArgs, 4, CI->getName(), CI);
1255       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(),
1256                                                   FormatStr.size()));
1257     }
1258
1259     // The remaining optimizations require the format string to be length 2:
1260     // "%s" or "%c".
1261     if (FormatStr.size() != 2 || FormatStr[0] != '%')
1262       return false;
1263
1264     // Get the second character and switch on its value
1265     switch (FormatStr[1]) {
1266     case 'c': {
1267       // fprintf(file,"%c",c) -> fputc(c,file)
1268       const Type *FILETy = CI->getOperand(1)->getType();
1269       Value *C = CastInst::createZExtOrBitCast(CI->getOperand(3), Type::Int32Ty,
1270                                                CI->getName()+".int", CI);
1271       new CallInst(SLC.get_fputc(FILETy), C, CI->getOperand(1), "", CI);
1272       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1273     }
1274     case 's': {
1275       const Type *FILETy = CI->getOperand(1)->getType();
1276
1277       // If the result of the fprintf call is used, we can't do this.
1278       // TODO: we should insert a strlen call.
1279       if (!CI->use_empty())
1280         return false;
1281
1282       // fprintf(file,"%s",str) -> fputs(str,file)
1283       new CallInst(SLC.get_fputs(FILETy), CastToCStr(CI->getOperand(3), CI),
1284                    CI->getOperand(1), CI->getName(), CI);
1285       return ReplaceCallWith(CI, 0);
1286     }
1287     default:
1288       return false;
1289     }
1290   }
1291 } FPrintFOptimizer;
1292
1293 /// This LibCallOptimization will simplify calls to the "sprintf" library
1294 /// function. It looks for cases where the result of sprintf is not used and the
1295 /// operation can be reduced to something simpler.
1296 /// @brief Simplify the sprintf library function.
1297 struct VISIBILITY_HIDDEN SPrintFOptimization : public LibCallOptimization {
1298 public:
1299   /// @brief Default Constructor
1300   SPrintFOptimization() : LibCallOptimization("sprintf",
1301       "Number of 'sprintf' calls simplified") {}
1302
1303   /// @brief Make sure that the "sprintf" function has the right prototype
1304   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1305     const FunctionType *FT = F->getFunctionType();
1306     return FT->getNumParams() == 2 &&  // two fixed arguments.
1307            FT->getParamType(1) == PointerType::get(Type::Int8Ty) &&
1308            FT->getParamType(0) == FT->getParamType(1) &&
1309            isa<IntegerType>(FT->getReturnType());
1310   }
1311
1312   /// @brief Perform the sprintf optimization.
1313   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1314     // If the call has more than 3 operands, we can't optimize it
1315     if (CI->getNumOperands() != 3 && CI->getNumOperands() != 4)
1316       return false;
1317
1318     std::string FormatStr;
1319     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1320       return false;
1321
1322     if (CI->getNumOperands() == 3) {
1323       // Make sure there's no % in the constant array
1324       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1325         if (FormatStr[i] == '%')
1326           return false; // we found a format specifier
1327
1328       // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
1329       Value *MemCpyArgs[] = {
1330         CI->getOperand(1), CI->getOperand(2),
1331         ConstantInt::get(SLC.getIntPtrType(),
1332                          FormatStr.size()+1), // Copy the nul byte.
1333         ConstantInt::get(Type::Int32Ty, 1)
1334       };
1335       new CallInst(SLC.get_memcpy(), MemCpyArgs, 4, "", CI);
1336       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(),
1337                                                   FormatStr.size()));
1338     }
1339
1340     // The remaining optimizations require the format string to be "%s" or "%c".
1341     if (FormatStr.size() != 2 || FormatStr[0] != '%')
1342       return false;
1343
1344     // Get the second character and switch on its value
1345     switch (FormatStr[1]) {
1346     case 'c': {
1347       // sprintf(dest,"%c",chr) -> store chr, dest
1348       Value *V = CastInst::createTruncOrBitCast(CI->getOperand(3),
1349                                                 Type::Int8Ty, "char", CI);
1350       new StoreInst(V, CI->getOperand(1), CI);
1351       Value *Ptr = new GetElementPtrInst(CI->getOperand(1),
1352                                          ConstantInt::get(Type::Int32Ty, 1),
1353                                          CI->getOperand(1)->getName()+".end",
1354                                          CI);
1355       new StoreInst(ConstantInt::get(Type::Int8Ty,0), Ptr, CI);
1356       return ReplaceCallWith(CI, ConstantInt::get(Type::Int32Ty, 1));
1357     }
1358     case 's': {
1359       // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1360       Value *Len = new CallInst(SLC.get_strlen(),
1361                                 CastToCStr(CI->getOperand(3), CI),
1362                                 CI->getOperand(3)->getName()+".len", CI);
1363       Value *UnincLen = Len;
1364       Len = BinaryOperator::createAdd(Len, ConstantInt::get(Len->getType(), 1),
1365                                       Len->getName()+"1", CI);
1366       Value *MemcpyArgs[4] = {
1367         CI->getOperand(1),
1368         CastToCStr(CI->getOperand(3), CI),
1369         Len,
1370         ConstantInt::get(Type::Int32Ty, 1)
1371       };
1372       new CallInst(SLC.get_memcpy(), MemcpyArgs, 4, "", CI);
1373
1374       // The strlen result is the unincremented number of bytes in the string.
1375       if (!CI->use_empty()) {
1376         if (UnincLen->getType() != CI->getType())
1377           UnincLen = CastInst::createIntegerCast(UnincLen, CI->getType(), false,
1378                                                  Len->getName(), CI);
1379         CI->replaceAllUsesWith(UnincLen);
1380       }
1381       return ReplaceCallWith(CI, 0);
1382     }
1383     }
1384     return false;
1385   }
1386 } SPrintFOptimizer;
1387
1388 /// This LibCallOptimization will simplify calls to the "fputs" library
1389 /// function. It looks for cases where the result of fputs is not used and the
1390 /// operation can be reduced to something simpler.
1391 /// @brief Simplify the fputs library function.
1392 struct VISIBILITY_HIDDEN FPutsOptimization : public LibCallOptimization {
1393 public:
1394   /// @brief Default Constructor
1395   FPutsOptimization() : LibCallOptimization("fputs",
1396       "Number of 'fputs' calls simplified") {}
1397
1398   /// @brief Make sure that the "fputs" function has the right prototype
1399   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1400     // Just make sure this has 2 arguments
1401     return F->arg_size() == 2;
1402   }
1403
1404   /// @brief Perform the fputs optimization.
1405   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1406     // If the result is used, none of these optimizations work.
1407     if (!CI->use_empty())
1408       return false;
1409
1410     // All the optimizations depend on the length of the first argument and the
1411     // fact that it is a constant string array. Check that now
1412     std::string Str;
1413     if (!GetConstantStringInfo(CI->getOperand(1), Str))
1414       return false;
1415
1416     const Type *FILETy = CI->getOperand(2)->getType();
1417     // fputs(s,F)  -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1)
1418     Value *FWriteParms[4] = {
1419       CI->getOperand(1),
1420       ConstantInt::get(SLC.getIntPtrType(), Str.size()),
1421       ConstantInt::get(SLC.getIntPtrType(), 1),
1422       CI->getOperand(2)
1423     };
1424     new CallInst(SLC.get_fwrite(FILETy), FWriteParms, 4, "", CI);
1425     return ReplaceCallWith(CI, 0);  // Known to have no uses (see above).
1426   }
1427 } FPutsOptimizer;
1428
1429 /// This LibCallOptimization will simplify calls to the "fwrite" function.
1430 struct VISIBILITY_HIDDEN FWriteOptimization : public LibCallOptimization {
1431 public:
1432   /// @brief Default Constructor
1433   FWriteOptimization() : LibCallOptimization("fwrite",
1434                                        "Number of 'fwrite' calls simplified") {}
1435
1436   /// @brief Make sure that the "fputs" function has the right prototype
1437   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1438     const FunctionType *FT = F->getFunctionType();
1439     return FT->getNumParams() == 4 &&
1440            FT->getParamType(0) == PointerType::get(Type::Int8Ty) &&
1441            FT->getParamType(1) == FT->getParamType(2) &&
1442            isa<IntegerType>(FT->getParamType(1)) &&
1443            isa<PointerType>(FT->getParamType(3)) &&
1444            isa<IntegerType>(FT->getReturnType());
1445   }
1446
1447   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1448     // Get the element size and count.
1449     uint64_t EltSize, EltCount;
1450     if (ConstantInt *C = dyn_cast<ConstantInt>(CI->getOperand(2)))
1451       EltSize = C->getZExtValue();
1452     else
1453       return false;
1454     if (ConstantInt *C = dyn_cast<ConstantInt>(CI->getOperand(3)))
1455       EltCount = C->getZExtValue();
1456     else
1457       return false;
1458
1459     // If this is writing zero records, remove the call (it's a noop).
1460     if (EltSize * EltCount == 0)
1461       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 0));
1462
1463     // If this is writing one byte, turn it into fputc.
1464     if (EltSize == 1 && EltCount == 1) {
1465       // fwrite(s,1,1,F) -> fputc(s[0],F)
1466       Value *Ptr = CI->getOperand(1);
1467       Value *Val = new LoadInst(Ptr, Ptr->getName()+".byte", CI);
1468       Val = new ZExtInst(Val, Type::Int32Ty, Val->getName()+".int", CI);
1469       const Type *FILETy = CI->getOperand(4)->getType();
1470       new CallInst(SLC.get_fputc(FILETy), Val, CI->getOperand(4), "", CI);
1471       return ReplaceCallWith(CI, ConstantInt::get(CI->getType(), 1));
1472     }
1473     return false;
1474   }
1475 } FWriteOptimizer;
1476
1477 /// This LibCallOptimization will simplify calls to the "isdigit" library
1478 /// function. It simply does range checks the parameter explicitly.
1479 /// @brief Simplify the isdigit library function.
1480 struct VISIBILITY_HIDDEN isdigitOptimization : public LibCallOptimization {
1481 public:
1482   isdigitOptimization() : LibCallOptimization("isdigit",
1483       "Number of 'isdigit' calls simplified") {}
1484
1485   /// @brief Make sure that the "isdigit" function has the right prototype
1486   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1487     // Just make sure this has 1 argument
1488     return (f->arg_size() == 1);
1489   }
1490
1491   /// @brief Perform the toascii optimization.
1492   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1493     if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1))) {
1494       // isdigit(c)   -> 0 or 1, if 'c' is constant
1495       uint64_t val = CI->getZExtValue();
1496       if (val >= '0' && val <= '9')
1497         return ReplaceCallWith(ci, ConstantInt::get(Type::Int32Ty, 1));
1498       else
1499         return ReplaceCallWith(ci, ConstantInt::get(Type::Int32Ty, 0));
1500     }
1501
1502     // isdigit(c)   -> (unsigned)c - '0' <= 9
1503     CastInst* cast = CastInst::createIntegerCast(ci->getOperand(1),
1504         Type::Int32Ty, false/*ZExt*/, ci->getOperand(1)->getName()+".uint", ci);
1505     BinaryOperator* sub_inst = BinaryOperator::createSub(cast,
1506         ConstantInt::get(Type::Int32Ty,0x30),
1507         ci->getOperand(1)->getName()+".sub",ci);
1508     ICmpInst* setcond_inst = new ICmpInst(ICmpInst::ICMP_ULE,sub_inst,
1509         ConstantInt::get(Type::Int32Ty,9),
1510         ci->getOperand(1)->getName()+".cmp",ci);
1511     CastInst* c2 = new ZExtInst(setcond_inst, Type::Int32Ty,
1512         ci->getOperand(1)->getName()+".isdigit", ci);
1513     return ReplaceCallWith(ci, c2);
1514   }
1515 } isdigitOptimizer;
1516
1517 struct VISIBILITY_HIDDEN isasciiOptimization : public LibCallOptimization {
1518 public:
1519   isasciiOptimization()
1520     : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {}
1521
1522   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1523     return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() &&
1524            F->getReturnType()->isInteger();
1525   }
1526
1527   /// @brief Perform the isascii optimization.
1528   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1529     // isascii(c)   -> (unsigned)c < 128
1530     Value *V = CI->getOperand(1);
1531     Value *Cmp = new ICmpInst(ICmpInst::ICMP_ULT, V,
1532                               ConstantInt::get(V->getType(), 128),
1533                               V->getName()+".isascii", CI);
1534     if (Cmp->getType() != CI->getType())
1535       Cmp = new BitCastInst(Cmp, CI->getType(), Cmp->getName(), CI);
1536     return ReplaceCallWith(CI, Cmp);
1537   }
1538 } isasciiOptimizer;
1539
1540
1541 /// This LibCallOptimization will simplify calls to the "toascii" library
1542 /// function. It simply does the corresponding and operation to restrict the
1543 /// range of values to the ASCII character set (0-127).
1544 /// @brief Simplify the toascii library function.
1545 struct VISIBILITY_HIDDEN ToAsciiOptimization : public LibCallOptimization {
1546 public:
1547   /// @brief Default Constructor
1548   ToAsciiOptimization() : LibCallOptimization("toascii",
1549       "Number of 'toascii' calls simplified") {}
1550
1551   /// @brief Make sure that the "fputs" function has the right prototype
1552   virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1553     // Just make sure this has 2 arguments
1554     return (f->arg_size() == 1);
1555   }
1556
1557   /// @brief Perform the toascii optimization.
1558   virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1559     // toascii(c)   -> (c & 0x7f)
1560     Value *chr = ci->getOperand(1);
1561     Value *and_inst = BinaryOperator::createAnd(chr,
1562         ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci);
1563     return ReplaceCallWith(ci, and_inst);
1564   }
1565 } ToAsciiOptimizer;
1566
1567 /// This LibCallOptimization will simplify calls to the "ffs" library
1568 /// calls which find the first set bit in an int, long, or long long. The
1569 /// optimization is to compute the result at compile time if the argument is
1570 /// a constant.
1571 /// @brief Simplify the ffs library function.
1572 struct VISIBILITY_HIDDEN FFSOptimization : public LibCallOptimization {
1573 protected:
1574   /// @brief Subclass Constructor
1575   FFSOptimization(const char* funcName, const char* description)
1576     : LibCallOptimization(funcName, description) {}
1577
1578 public:
1579   /// @brief Default Constructor
1580   FFSOptimization() : LibCallOptimization("ffs",
1581       "Number of 'ffs' calls simplified") {}
1582
1583   /// @brief Make sure that the "ffs" function has the right prototype
1584   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1585     // Just make sure this has 2 arguments
1586     return F->arg_size() == 1 && F->getReturnType() == Type::Int32Ty;
1587   }
1588
1589   /// @brief Perform the ffs optimization.
1590   virtual bool OptimizeCall(CallInst *TheCall, SimplifyLibCalls &SLC) {
1591     if (ConstantInt *CI = dyn_cast<ConstantInt>(TheCall->getOperand(1))) {
1592       // ffs(cnst)  -> bit#
1593       // ffsl(cnst) -> bit#
1594       // ffsll(cnst) -> bit#
1595       uint64_t val = CI->getZExtValue();
1596       int result = 0;
1597       if (val) {
1598         ++result;
1599         while ((val & 1) == 0) {
1600           ++result;
1601           val >>= 1;
1602         }
1603       }
1604       return ReplaceCallWith(TheCall, ConstantInt::get(Type::Int32Ty, result));
1605     }
1606
1607     // ffs(x)   -> x == 0 ? 0 : llvm.cttz(x)+1
1608     // ffsl(x)  -> x == 0 ? 0 : llvm.cttz(x)+1
1609     // ffsll(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1610     const Type *ArgType = TheCall->getOperand(1)->getType();
1611     const char *CTTZName;
1612     assert(ArgType->getTypeID() == Type::IntegerTyID &&
1613            "llvm.cttz argument is not an integer?");
1614     unsigned BitWidth = cast<IntegerType>(ArgType)->getBitWidth();
1615     if (BitWidth == 8)
1616       CTTZName = "llvm.cttz.i8";
1617     else if (BitWidth == 16)
1618       CTTZName = "llvm.cttz.i16";
1619     else if (BitWidth == 32)
1620       CTTZName = "llvm.cttz.i32";
1621     else {
1622       assert(BitWidth == 64 && "Unknown bitwidth");
1623       CTTZName = "llvm.cttz.i64";
1624     }
1625
1626     Constant *F = SLC.getModule()->getOrInsertFunction(CTTZName, ArgType,
1627                                                        ArgType, NULL);
1628     Value *V = CastInst::createIntegerCast(TheCall->getOperand(1), ArgType,
1629                                            false/*ZExt*/, "tmp", TheCall);
1630     Value *V2 = new CallInst(F, V, "tmp", TheCall);
1631     V2 = CastInst::createIntegerCast(V2, Type::Int32Ty, false/*ZExt*/,
1632                                      "tmp", TheCall);
1633     V2 = BinaryOperator::createAdd(V2, ConstantInt::get(Type::Int32Ty, 1),
1634                                    "tmp", TheCall);
1635     Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, V,
1636                                Constant::getNullValue(V->getType()), "tmp",
1637                                TheCall);
1638     V2 = new SelectInst(Cond, ConstantInt::get(Type::Int32Ty, 0), V2,
1639                         TheCall->getName(), TheCall);
1640     return ReplaceCallWith(TheCall, V2);
1641   }
1642 } FFSOptimizer;
1643
1644 /// This LibCallOptimization will simplify calls to the "ffsl" library
1645 /// calls. It simply uses FFSOptimization for which the transformation is
1646 /// identical.
1647 /// @brief Simplify the ffsl library function.
1648 struct VISIBILITY_HIDDEN FFSLOptimization : public FFSOptimization {
1649 public:
1650   /// @brief Default Constructor
1651   FFSLOptimization() : FFSOptimization("ffsl",
1652       "Number of 'ffsl' calls simplified") {}
1653
1654 } FFSLOptimizer;
1655
1656 /// This LibCallOptimization will simplify calls to the "ffsll" library
1657 /// calls. It simply uses FFSOptimization for which the transformation is
1658 /// identical.
1659 /// @brief Simplify the ffsl library function.
1660 struct VISIBILITY_HIDDEN FFSLLOptimization : public FFSOptimization {
1661 public:
1662   /// @brief Default Constructor
1663   FFSLLOptimization() : FFSOptimization("ffsll",
1664       "Number of 'ffsll' calls simplified") {}
1665
1666 } FFSLLOptimizer;
1667
1668 /// This optimizes unary functions that take and return doubles.
1669 struct UnaryDoubleFPOptimizer : public LibCallOptimization {
1670   UnaryDoubleFPOptimizer(const char *Fn, const char *Desc)
1671   : LibCallOptimization(Fn, Desc) {}
1672
1673   // Make sure that this function has the right prototype
1674   virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1675     return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy &&
1676            F->getReturnType() == Type::DoubleTy;
1677   }
1678
1679   /// ShrinkFunctionToFloatVersion - If the input to this function is really a
1680   /// float, strength reduce this to a float version of the function,
1681   /// e.g. floor((double)FLT) -> (double)floorf(FLT).  This can only be called
1682   /// when the target supports the destination function and where there can be
1683   /// no precision loss.
1684   static bool ShrinkFunctionToFloatVersion(CallInst *CI, SimplifyLibCalls &SLC,
1685                                            Constant *(SimplifyLibCalls::*FP)()){
1686     if (FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1)))
1687       if (Cast->getOperand(0)->getType() == Type::FloatTy) {
1688         Value *New = new CallInst((SLC.*FP)(), Cast->getOperand(0),
1689                                   CI->getName(), CI);
1690         New = new FPExtInst(New, Type::DoubleTy, CI->getName(), CI);
1691         CI->replaceAllUsesWith(New);
1692         CI->eraseFromParent();
1693         if (Cast->use_empty())
1694           Cast->eraseFromParent();
1695         return true;
1696       }
1697     return false;
1698   }
1699 };
1700
1701
1702 struct VISIBILITY_HIDDEN FloorOptimization : public UnaryDoubleFPOptimizer {
1703   FloorOptimization()
1704     : UnaryDoubleFPOptimizer("floor", "Number of 'floor' calls simplified") {}
1705
1706   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1707 #ifdef HAVE_FLOORF
1708     // If this is a float argument passed in, convert to floorf.
1709     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_floorf))
1710       return true;
1711 #endif
1712     return false; // opt failed
1713   }
1714 } FloorOptimizer;
1715
1716 struct VISIBILITY_HIDDEN CeilOptimization : public UnaryDoubleFPOptimizer {
1717   CeilOptimization()
1718   : UnaryDoubleFPOptimizer("ceil", "Number of 'ceil' calls simplified") {}
1719
1720   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1721 #ifdef HAVE_CEILF
1722     // If this is a float argument passed in, convert to ceilf.
1723     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_ceilf))
1724       return true;
1725 #endif
1726     return false; // opt failed
1727   }
1728 } CeilOptimizer;
1729
1730 struct VISIBILITY_HIDDEN RoundOptimization : public UnaryDoubleFPOptimizer {
1731   RoundOptimization()
1732   : UnaryDoubleFPOptimizer("round", "Number of 'round' calls simplified") {}
1733
1734   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1735 #ifdef HAVE_ROUNDF
1736     // If this is a float argument passed in, convert to roundf.
1737     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_roundf))
1738       return true;
1739 #endif
1740     return false; // opt failed
1741   }
1742 } RoundOptimizer;
1743
1744 struct VISIBILITY_HIDDEN RintOptimization : public UnaryDoubleFPOptimizer {
1745   RintOptimization()
1746   : UnaryDoubleFPOptimizer("rint", "Number of 'rint' calls simplified") {}
1747
1748   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1749 #ifdef HAVE_RINTF
1750     // If this is a float argument passed in, convert to rintf.
1751     if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_rintf))
1752       return true;
1753 #endif
1754     return false; // opt failed
1755   }
1756 } RintOptimizer;
1757
1758 struct VISIBILITY_HIDDEN NearByIntOptimization : public UnaryDoubleFPOptimizer {
1759   NearByIntOptimization()
1760   : UnaryDoubleFPOptimizer("nearbyint",
1761                            "Number of 'nearbyint' calls simplified") {}
1762
1763   virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1764 #ifdef HAVE_NEARBYINTF
1765     // If this is a float argument passed in, convert to nearbyintf.
1766     if (ShrinkFunctionToFloatVersion(CI, SLC,&SimplifyLibCalls::get_nearbyintf))
1767       return true;
1768 #endif
1769     return false; // opt failed
1770   }
1771 } NearByIntOptimizer;
1772
1773 /// GetConstantStringInfo - This function computes the length of a
1774 /// null-terminated constant array of integers.  This function can't rely on the
1775 /// size of the constant array because there could be a null terminator in the
1776 /// middle of the array.
1777 ///
1778 /// We also have to bail out if we find a non-integer constant initializer
1779 /// of one of the elements or if there is no null-terminator. The logic
1780 /// below checks each of these conditions and will return true only if all
1781 /// conditions are met.  If the conditions aren't met, this returns false.
1782 ///
1783 /// If successful, the \p Array param is set to the constant array being
1784 /// indexed, the \p Length parameter is set to the length of the null-terminated
1785 /// string pointed to by V, the \p StartIdx value is set to the first
1786 /// element of the Array that V points to, and true is returned.
1787 static bool GetConstantStringInfo(Value *V, std::string &Str) {
1788   // Look through noop bitcast instructions.
1789   if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1790     if (BCI->getType() == BCI->getOperand(0)->getType())
1791       return GetConstantStringInfo(BCI->getOperand(0), Str);
1792     return false;
1793   }
1794
1795   // If the value is not a GEP instruction nor a constant expression with a
1796   // GEP instruction, then return false because ConstantArray can't occur
1797   // any other way
1798   User *GEP = 0;
1799   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) {
1800     GEP = GEPI;
1801   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
1802     if (CE->getOpcode() != Instruction::GetElementPtr)
1803       return false;
1804     GEP = CE;
1805   } else {
1806     return false;
1807   }
1808
1809   // Make sure the GEP has exactly three arguments.
1810   if (GEP->getNumOperands() != 3)
1811     return false;
1812
1813   // Check to make sure that the first operand of the GEP is an integer and
1814   // has value 0 so that we are sure we're indexing into the initializer.
1815   if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
1816     if (!Idx->isZero())
1817       return false;
1818   } else
1819     return false;
1820
1821   // If the second index isn't a ConstantInt, then this is a variable index
1822   // into the array.  If this occurs, we can't say anything meaningful about
1823   // the string.
1824   uint64_t StartIdx = 0;
1825   if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
1826     StartIdx = CI->getZExtValue();
1827   else
1828     return false;
1829
1830   // The GEP instruction, constant or instruction, must reference a global
1831   // variable that is a constant and is initialized. The referenced constant
1832   // initializer is the array that we'll use for optimization.
1833   GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
1834   if (!GV || !GV->isConstant() || !GV->hasInitializer())
1835     return false;
1836   Constant *GlobalInit = GV->getInitializer();
1837
1838   // Handle the ConstantAggregateZero case
1839   if (isa<ConstantAggregateZero>(GlobalInit)) {
1840     // This is a degenerate case. The initializer is constant zero so the
1841     // length of the string must be zero.
1842     Str.clear();
1843     return true;
1844   }
1845
1846   // Must be a Constant Array
1847   ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit);
1848   if (!Array) return false;
1849
1850   // Get the number of elements in the array
1851   uint64_t NumElts = Array->getType()->getNumElements();
1852
1853   // Traverse the constant array from StartIdx (derived above) which is
1854   // the place the GEP refers to in the array.
1855   for (unsigned i = StartIdx; i < NumElts; ++i) {
1856     Constant *Elt = Array->getOperand(i);
1857     ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
1858     if (!CI) // This array isn't suitable, non-int initializer.
1859       return false;
1860     if (CI->isZero())
1861       return true; // we found end of string, success!
1862     Str += (char)CI->getZExtValue();
1863   }
1864
1865   return false; // The array isn't null terminated.
1866 }
1867
1868 /// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*,
1869 /// inserting the cast before IP, and return the cast.
1870 /// @brief Cast a value to a "C" string.
1871 static Value *CastToCStr(Value *V, Instruction *IP) {
1872   assert(isa<PointerType>(V->getType()) &&
1873          "Can't cast non-pointer type to C string type");
1874   const Type *SBPTy = PointerType::get(Type::Int8Ty);
1875   if (V->getType() != SBPTy)
1876     return new BitCastInst(V, SBPTy, V->getName(), IP);
1877   return V;
1878 }
1879
1880 // TODO:
1881 //   Additional cases that we need to add to this file:
1882 //
1883 // cbrt:
1884 //   * cbrt(expN(X))  -> expN(x/3)
1885 //   * cbrt(sqrt(x))  -> pow(x,1/6)
1886 //   * cbrt(sqrt(x))  -> pow(x,1/9)
1887 //
1888 // cos, cosf, cosl:
1889 //   * cos(-x)  -> cos(x)
1890 //
1891 // exp, expf, expl:
1892 //   * exp(log(x))  -> x
1893 //
1894 // log, logf, logl:
1895 //   * log(exp(x))   -> x
1896 //   * log(x**y)     -> y*log(x)
1897 //   * log(exp(y))   -> y*log(e)
1898 //   * log(exp2(y))  -> y*log(2)
1899 //   * log(exp10(y)) -> y*log(10)
1900 //   * log(sqrt(x))  -> 0.5*log(x)
1901 //   * log(pow(x,y)) -> y*log(x)
1902 //
1903 // lround, lroundf, lroundl:
1904 //   * lround(cnst) -> cnst'
1905 //
1906 // memcmp:
1907 //   * memcmp(x,y,l)   -> cnst
1908 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
1909 //
1910 // memmove:
1911 //   * memmove(d,s,l,a) -> memcpy(d,s,l,a)
1912 //       (if s is a global constant array)
1913 //
1914 // pow, powf, powl:
1915 //   * pow(exp(x),y)  -> exp(x*y)
1916 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
1917 //   * pow(pow(x,y),z)-> pow(x,y*z)
1918 //
1919 // puts:
1920 //   * puts("") -> fputc("\n",stdout) (how do we get "stdout"?)
1921 //
1922 // round, roundf, roundl:
1923 //   * round(cnst) -> cnst'
1924 //
1925 // signbit:
1926 //   * signbit(cnst) -> cnst'
1927 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1928 //
1929 // sqrt, sqrtf, sqrtl:
1930 //   * sqrt(expN(x))  -> expN(x*0.5)
1931 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1932 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1933 //
1934 // stpcpy:
1935 //   * stpcpy(str, "literal") ->
1936 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
1937 // strrchr:
1938 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
1939 //      (if c is a constant integer and s is a constant string)
1940 //   * strrchr(s1,0) -> strchr(s1,0)
1941 //
1942 // strncat:
1943 //   * strncat(x,y,0) -> x
1944 //   * strncat(x,y,0) -> x (if strlen(y) = 0)
1945 //   * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y))
1946 //
1947 // strncpy:
1948 //   * strncpy(d,s,0) -> d
1949 //   * strncpy(d,s,l) -> memcpy(d,s,l,1)
1950 //      (if s and l are constants)
1951 //
1952 // strpbrk:
1953 //   * strpbrk(s,a) -> offset_in_for(s,a)
1954 //      (if s and a are both constant strings)
1955 //   * strpbrk(s,"") -> 0
1956 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
1957 //
1958 // strspn, strcspn:
1959 //   * strspn(s,a)   -> const_int (if both args are constant)
1960 //   * strspn("",a)  -> 0
1961 //   * strspn(s,"")  -> 0
1962 //   * strcspn(s,a)  -> const_int (if both args are constant)
1963 //   * strcspn("",a) -> 0
1964 //   * strcspn(s,"") -> strlen(a)
1965 //
1966 // strstr:
1967 //   * strstr(x,x)  -> x
1968 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
1969 //       (if s1 and s2 are constant strings)
1970 //
1971 // tan, tanf, tanl:
1972 //   * tan(atan(x)) -> x
1973 //
1974 // trunc, truncf, truncl:
1975 //   * trunc(cnst) -> cnst'
1976 //
1977 //
1978 }