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