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