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