1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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
18 //===----------------------------------------------------------------------===//
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"
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");
41 // Forward declarations
42 class LibCallOptimization;
43 class SimplifyLibCalls;
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;
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 {
69 /// The \p fname argument must be the name of the library function being
70 /// optimized by the subclass.
71 /// @brief Constructor that registers the optimization.
72 LibCallOptimization(const char* fname, const char* description )
75 , occurrences("simplify-libcalls",description)
78 // Register this call optimizer in the optlist (a hash_map)
79 optlist[fname] = this;
82 /// @brief Deregister from the optlist
83 virtual ~LibCallOptimization() { optlist.erase(func_name); }
85 /// The implementation of this function in subclasses should determine if
86 /// \p F is suitable for the optimization. This method is called by
87 /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
88 /// sites of such a function if that function is not suitable in the first
89 /// place. If the called function is suitabe, this method should return true;
90 /// false, otherwise. This function should also perform any lazy
91 /// initialization that the LibCallOptimization needs to do, if its to return
92 /// true. This avoids doing initialization until the optimizer is actually
93 /// going to be called upon to do some optimization.
94 /// @brief Determine if the function is suitable for optimization
95 virtual bool ValidateCalledFunction(
96 const Function* F, ///< The function that is the target of call sites
97 SimplifyLibCalls& SLC ///< The pass object invoking us
100 /// The implementations of this function in subclasses is the heart of the
101 /// SimplifyLibCalls algorithm. Sublcasses of this class implement
102 /// OptimizeCall to determine if (a) the conditions are right for optimizing
103 /// the call and (b) to perform the optimization. If an action is taken
104 /// against ci, the subclass is responsible for returning true and ensuring
105 /// that ci is erased from its parent.
106 /// @brief Optimize a call, if possible.
107 virtual bool OptimizeCall(
108 CallInst* ci, ///< The call instruction that should be optimized.
109 SimplifyLibCalls& SLC ///< The pass object invoking us
112 /// @brief Get the name of the library call being optimized
113 const char * getFunctionName() const { return func_name; }
116 /// @brief Called by SimplifyLibCalls to update the occurrences statistic.
117 void succeeded() { DEBUG(++occurrences); }
121 const char* func_name; ///< Name of the library call we optimize
123 Statistic<> occurrences; ///< debug statistic (-debug-only=simplify-libcalls)
127 /// This class is an LLVM Pass that applies each of the LibCallOptimization
128 /// instances to all the call sites in a module, relatively efficiently. The
129 /// purpose of this pass is to provide optimizations for calls to well-known
130 /// functions with well-known semantics, such as those in the c library. The
131 /// class provides the basic infrastructure for handling runOnModule. Whenever
132 /// this pass finds a function call, it asks the appropriate optimizer to
133 /// validate the call (ValidateLibraryCall). If it is validated, then
134 /// the OptimizeCall method is also called.
135 /// @brief A ModulePass for optimizing well-known function calls.
136 class SimplifyLibCalls : public ModulePass {
138 /// We need some target data for accurate signature details that are
139 /// target dependent. So we require target data in our AnalysisUsage.
140 /// @brief Require TargetData from AnalysisUsage.
141 virtual void getAnalysisUsage(AnalysisUsage& Info) const {
142 // Ask that the TargetData analysis be performed before us so we can use
144 Info.addRequired<TargetData>();
147 /// For this pass, process all of the function calls in the module, calling
148 /// ValidateLibraryCall and OptimizeCall as appropriate.
149 /// @brief Run all the lib call optimizations on a Module.
150 virtual bool runOnModule(Module &M) {
155 // The call optimizations can be recursive. That is, the optimization might
156 // generate a call to another function which can also be optimized. This way
157 // we make the LibCallOptimization instances very specific to the case they
158 // handle. It also means we need to keep running over the function calls in
159 // the module until we don't get any more optimizations possible.
160 bool found_optimization = false;
162 found_optimization = false;
163 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
164 // All the "well-known" functions are external and have external linkage
165 // because they live in a runtime library somewhere and were (probably)
166 // not compiled by LLVM. So, we only act on external functions that
167 // have external linkage and non-empty uses.
168 if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
171 // Get the optimization class that pertains to this function
172 LibCallOptimization* CO = optlist[FI->getName().c_str()];
176 // Make sure the called function is suitable for the optimization
177 if (!CO->ValidateCalledFunction(FI,*this))
180 // Loop over each of the uses of the function
181 for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
183 // If the use of the function is a call instruction
184 if (CallInst* CI = dyn_cast<CallInst>(*UI++)) {
185 // Do the optimization on the LibCallOptimization.
186 if (CO->OptimizeCall(CI, *this)) {
187 ++SimplifiedLibCalls;
188 found_optimization = result = true;
196 } while (found_optimization);
200 /// @brief Return the *current* module we're working on.
201 Module* getModule() const { return M; }
203 /// @brief Return the *current* target data for the module we're working on.
204 TargetData* getTargetData() const { return TD; }
206 /// @brief Return the size_t type -- syntactic shortcut
207 const Type* getIntPtrType() const { return TD->getIntPtrType(); }
209 /// @brief Return a Function* for the fputc libcall
210 Function* get_fputc(const Type* FILEptr_type) {
212 fputc_func = M->getOrInsertFunction("fputc", Type::IntTy, Type::IntTy,
217 /// @brief Return a Function* for the fwrite libcall
218 Function* get_fwrite(const Type* FILEptr_type) {
220 fwrite_func = M->getOrInsertFunction("fwrite", TD->getIntPtrType(),
221 PointerType::get(Type::SByteTy),
228 /// @brief Return a Function* for the sqrt libcall
229 Function* get_sqrt() {
231 sqrt_func = M->getOrInsertFunction("sqrt", Type::DoubleTy,
232 Type::DoubleTy, NULL);
236 /// @brief Return a Function* for the strlen libcall
237 Function* get_strcpy() {
239 strcpy_func = M->getOrInsertFunction("strcpy",
240 PointerType::get(Type::SByteTy),
241 PointerType::get(Type::SByteTy),
242 PointerType::get(Type::SByteTy),
247 /// @brief Return a Function* for the strlen libcall
248 Function* get_strlen() {
250 strlen_func = M->getOrInsertFunction("strlen", TD->getIntPtrType(),
251 PointerType::get(Type::SByteTy),
256 /// @brief Return a Function* for the memchr libcall
257 Function* get_memchr() {
259 memchr_func = M->getOrInsertFunction("memchr",
260 PointerType::get(Type::SByteTy),
261 PointerType::get(Type::SByteTy),
262 Type::IntTy, TD->getIntPtrType(),
267 /// @brief Return a Function* for the memcpy libcall
268 Function* get_memcpy() {
270 const Type *SBP = PointerType::get(Type::SByteTy);
271 memcpy_func = M->getOrInsertFunction("llvm.memcpy", Type::VoidTy,SBP, SBP,
272 Type::UIntTy, Type::UIntTy, NULL);
277 Function* get_floorf() {
279 floorf_func = M->getOrInsertFunction("floorf", Type::FloatTy,
280 Type::FloatTy, NULL);
285 /// @brief Reset our cached data for a new Module
286 void reset(Module& mod) {
288 TD = &getAnalysis<TargetData>();
300 Function* fputc_func; ///< Cached fputc function
301 Function* fwrite_func; ///< Cached fwrite function
302 Function* memcpy_func; ///< Cached llvm.memcpy function
303 Function* memchr_func; ///< Cached memchr function
304 Function* sqrt_func; ///< Cached sqrt function
305 Function* strcpy_func; ///< Cached strcpy function
306 Function* strlen_func; ///< Cached strlen function
307 Function* floorf_func; ///< Cached floorf function
308 Module* M; ///< Cached Module
309 TargetData* TD; ///< Cached TargetData
313 RegisterOpt<SimplifyLibCalls>
314 X("simplify-libcalls","Simplify well-known library calls");
316 } // anonymous namespace
318 // The only public symbol in this file which just instantiates the pass object
319 ModulePass *llvm::createSimplifyLibCallsPass() {
320 return new SimplifyLibCalls();
323 // Classes below here, in the anonymous namespace, are all subclasses of the
324 // LibCallOptimization class, each implementing all optimizations possible for a
325 // single well-known library call. Each has a static singleton instance that
326 // auto registers it into the "optlist" global above.
329 // Forward declare utility functions.
330 bool getConstantStringLength(Value* V, uint64_t& len, ConstantArray** A = 0 );
331 Value *CastToCStr(Value *V, Instruction &IP);
333 /// This LibCallOptimization will find instances of a call to "exit" that occurs
334 /// within the "main" function and change it to a simple "ret" instruction with
335 /// the same value passed to the exit function. When this is done, it splits the
336 /// basic block at the exit(3) call and deletes the call instruction.
337 /// @brief Replace calls to exit in main with a simple return
338 struct ExitInMainOptimization : public LibCallOptimization {
339 ExitInMainOptimization() : LibCallOptimization("exit",
340 "Number of 'exit' calls simplified") {}
342 // Make sure the called function looks like exit (int argument, int return
343 // type, external linkage, not varargs).
344 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
345 return F->arg_size() >= 1 && F->arg_begin()->getType()->isInteger();
348 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
349 // To be careful, we check that the call to exit is coming from "main", that
350 // main has external linkage, and the return type of main and the argument
351 // to exit have the same type.
352 Function *from = ci->getParent()->getParent();
353 if (from->hasExternalLinkage())
354 if (from->getReturnType() == ci->getOperand(1)->getType())
355 if (from->getName() == "main") {
356 // Okay, time to actually do the optimization. First, get the basic
357 // block of the call instruction
358 BasicBlock* bb = ci->getParent();
360 // Create a return instruction that we'll replace the call with.
361 // Note that the argument of the return is the argument of the call
363 ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci);
365 // Split the block at the call instruction which places it in a new
367 bb->splitBasicBlock(ci);
369 // The block split caused a branch instruction to be inserted into
370 // the end of the original block, right after the return instruction
371 // that we put there. That's not a valid block, so delete the branch
373 bb->getInstList().pop_back();
375 // Now we can finally get rid of the call instruction which now lives
376 // in the new basic block.
377 ci->eraseFromParent();
379 // Optimization succeeded, return true.
382 // We didn't pass the criteria for this optimization so return false
385 } ExitInMainOptimizer;
387 /// This LibCallOptimization will simplify a call to the strcat library
388 /// function. The simplification is possible only if the string being
389 /// concatenated is a constant array or a constant expression that results in
390 /// a constant string. In this case we can replace it with strlen + llvm.memcpy
391 /// of the constant string. Both of these calls are further reduced, if possible
392 /// on subsequent passes.
393 /// @brief Simplify the strcat library function.
394 struct StrCatOptimization : public LibCallOptimization {
396 /// @brief Default constructor
397 StrCatOptimization() : LibCallOptimization("strcat",
398 "Number of 'strcat' calls simplified") {}
402 /// @brief Make sure that the "strcat" function has the right prototype
403 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
404 if (f->getReturnType() == PointerType::get(Type::SByteTy))
405 if (f->arg_size() == 2)
407 Function::const_arg_iterator AI = f->arg_begin();
408 if (AI++->getType() == PointerType::get(Type::SByteTy))
409 if (AI->getType() == PointerType::get(Type::SByteTy))
411 // Indicate this is a suitable call type.
418 /// @brief Optimize the strcat library function
419 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
420 // Extract some information from the instruction
421 Module* M = ci->getParent()->getParent()->getParent();
422 Value* dest = ci->getOperand(1);
423 Value* src = ci->getOperand(2);
425 // Extract the initializer (while making numerous checks) from the
426 // source operand of the call to strcat. If we get null back, one of
427 // a variety of checks in get_GVInitializer failed
429 if (!getConstantStringLength(src,len))
432 // Handle the simple, do-nothing case
434 ci->replaceAllUsesWith(dest);
435 ci->eraseFromParent();
439 // Increment the length because we actually want to memcpy the null
440 // terminator as well.
443 // We need to find the end of the destination string. That's where the
444 // memory is to be moved to. We just generate a call to strlen (further
445 // optimized in another pass). Note that the SLC.get_strlen() call
446 // caches the Function* for us.
447 CallInst* strlen_inst =
448 new CallInst(SLC.get_strlen(), dest, dest->getName()+".len",ci);
450 // Now that we have the destination's length, we must index into the
451 // destination's pointer to get the actual memcpy destination (end of
452 // the string .. we're concatenating).
453 std::vector<Value*> idx;
454 idx.push_back(strlen_inst);
455 GetElementPtrInst* gep =
456 new GetElementPtrInst(dest,idx,dest->getName()+".indexed",ci);
458 // We have enough information to now generate the memcpy call to
459 // do the concatenation for us.
460 std::vector<Value*> vals;
461 vals.push_back(gep); // destination
462 vals.push_back(ci->getOperand(2)); // source
463 vals.push_back(ConstantUInt::get(Type::UIntTy,len)); // length
464 vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
465 new CallInst(SLC.get_memcpy(), vals, "", ci);
467 // Finally, substitute the first operand of the strcat call for the
468 // strcat call itself since strcat returns its first operand; and,
469 // kill the strcat CallInst.
470 ci->replaceAllUsesWith(dest);
471 ci->eraseFromParent();
476 /// This LibCallOptimization will simplify a call to the strchr library
477 /// function. It optimizes out cases where the arguments are both constant
478 /// and the result can be determined statically.
479 /// @brief Simplify the strcmp library function.
480 struct StrChrOptimization : public LibCallOptimization {
482 StrChrOptimization() : LibCallOptimization("strchr",
483 "Number of 'strchr' calls simplified") {}
485 /// @brief Make sure that the "strchr" function has the right prototype
486 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
487 if (f->getReturnType() == PointerType::get(Type::SByteTy) &&
493 /// @brief Perform the strchr optimizations
494 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
495 // If there aren't three operands, bail
496 if (ci->getNumOperands() != 3)
499 // Check that the first argument to strchr is a constant array of sbyte.
500 // If it is, get the length and data, otherwise return false.
503 if (!getConstantStringLength(ci->getOperand(1),len,&CA))
506 // Check that the second argument to strchr is a constant int, return false
508 ConstantSInt* CSI = dyn_cast<ConstantSInt>(ci->getOperand(2));
510 // Just lower this to memchr since we know the length of the string as
512 Function* f = SLC.get_memchr();
513 std::vector<Value*> args;
514 args.push_back(ci->getOperand(1));
515 args.push_back(ci->getOperand(2));
516 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
517 ci->replaceAllUsesWith( new CallInst(f,args,ci->getName(),ci));
518 ci->eraseFromParent();
522 // Get the character we're looking for
523 int64_t chr = CSI->getValue();
525 // Compute the offset
527 bool char_found = false;
528 for (uint64_t i = 0; i < len; ++i) {
529 if (ConstantSInt* CI = dyn_cast<ConstantSInt>(CA->getOperand(i))) {
530 // Check for the null terminator
531 if (CI->isNullValue())
532 break; // we found end of string
533 else if (CI->getValue() == chr) {
541 // strchr(s,c) -> offset_of_in(c,s)
542 // (if c is a constant integer and s is a constant string)
544 std::vector<Value*> indices;
545 indices.push_back(ConstantUInt::get(Type::ULongTy,offset));
546 GetElementPtrInst* GEP = new GetElementPtrInst(ci->getOperand(1),indices,
547 ci->getOperand(1)->getName()+".strchr",ci);
548 ci->replaceAllUsesWith(GEP);
550 ci->replaceAllUsesWith(
551 ConstantPointerNull::get(PointerType::get(Type::SByteTy)));
553 ci->eraseFromParent();
558 /// This LibCallOptimization will simplify a call to the strcmp library
559 /// function. It optimizes out cases where one or both arguments are constant
560 /// and the result can be determined statically.
561 /// @brief Simplify the strcmp library function.
562 struct StrCmpOptimization : public LibCallOptimization {
564 StrCmpOptimization() : LibCallOptimization("strcmp",
565 "Number of 'strcmp' calls simplified") {}
567 /// @brief Make sure that the "strcmp" function has the right prototype
568 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
569 return F->getReturnType() == Type::IntTy && F->arg_size() == 2;
572 /// @brief Perform the strcmp optimization
573 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
574 // First, check to see if src and destination are the same. If they are,
575 // then the optimization is to replace the CallInst with a constant 0
576 // because the call is a no-op.
577 Value* s1 = ci->getOperand(1);
578 Value* s2 = ci->getOperand(2);
581 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
582 ci->eraseFromParent();
586 bool isstr_1 = false;
589 if (getConstantStringLength(s1,len_1,&A1)) {
592 // strcmp("",x) -> *x
594 new LoadInst(CastToCStr(s2,*ci), ci->getName()+".load",ci);
596 new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
597 ci->replaceAllUsesWith(cast);
598 ci->eraseFromParent();
603 bool isstr_2 = false;
606 if (getConstantStringLength(s2, len_2, &A2)) {
609 // strcmp(x,"") -> *x
611 new LoadInst(CastToCStr(s1,*ci),ci->getName()+".val",ci);
613 new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
614 ci->replaceAllUsesWith(cast);
615 ci->eraseFromParent();
620 if (isstr_1 && isstr_2) {
621 // strcmp(x,y) -> cnst (if both x and y are constant strings)
622 std::string str1 = A1->getAsString();
623 std::string str2 = A2->getAsString();
624 int result = strcmp(str1.c_str(), str2.c_str());
625 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result));
626 ci->eraseFromParent();
633 /// This LibCallOptimization will simplify a call to the strncmp library
634 /// function. It optimizes out cases where one or both arguments are constant
635 /// and the result can be determined statically.
636 /// @brief Simplify the strncmp library function.
637 struct StrNCmpOptimization : public LibCallOptimization {
639 StrNCmpOptimization() : LibCallOptimization("strncmp",
640 "Number of 'strncmp' calls simplified") {}
642 /// @brief Make sure that the "strncmp" function has the right prototype
643 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
644 if (f->getReturnType() == Type::IntTy && f->arg_size() == 3)
649 /// @brief Perform the strncpy optimization
650 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
651 // First, check to see if src and destination are the same. If they are,
652 // then the optimization is to replace the CallInst with a constant 0
653 // because the call is a no-op.
654 Value* s1 = ci->getOperand(1);
655 Value* s2 = ci->getOperand(2);
657 // strncmp(x,x,l) -> 0
658 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
659 ci->eraseFromParent();
663 // Check the length argument, if it is Constant zero then the strings are
665 uint64_t len_arg = 0;
666 bool len_arg_is_const = false;
667 if (ConstantInt* len_CI = dyn_cast<ConstantInt>(ci->getOperand(3))) {
668 len_arg_is_const = true;
669 len_arg = len_CI->getRawValue();
671 // strncmp(x,y,0) -> 0
672 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
673 ci->eraseFromParent();
678 bool isstr_1 = false;
681 if (getConstantStringLength(s1, len_1, &A1)) {
684 // strncmp("",x) -> *x
685 LoadInst* load = new LoadInst(s1,ci->getName()+".load",ci);
687 new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
688 ci->replaceAllUsesWith(cast);
689 ci->eraseFromParent();
694 bool isstr_2 = false;
697 if (getConstantStringLength(s2,len_2,&A2)) {
700 // strncmp(x,"") -> *x
701 LoadInst* load = new LoadInst(s2,ci->getName()+".val",ci);
703 new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
704 ci->replaceAllUsesWith(cast);
705 ci->eraseFromParent();
710 if (isstr_1 && isstr_2 && len_arg_is_const) {
711 // strncmp(x,y,const) -> constant
712 std::string str1 = A1->getAsString();
713 std::string str2 = A2->getAsString();
714 int result = strncmp(str1.c_str(), str2.c_str(), len_arg);
715 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result));
716 ci->eraseFromParent();
723 /// This LibCallOptimization will simplify a call to the strcpy library
724 /// function. Two optimizations are possible:
725 /// (1) If src and dest are the same and not volatile, just return dest
726 /// (2) If the src is a constant then we can convert to llvm.memmove
727 /// @brief Simplify the strcpy library function.
728 struct StrCpyOptimization : public LibCallOptimization {
730 StrCpyOptimization() : LibCallOptimization("strcpy",
731 "Number of 'strcpy' calls simplified") {}
733 /// @brief Make sure that the "strcpy" function has the right prototype
734 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
735 if (f->getReturnType() == PointerType::get(Type::SByteTy))
736 if (f->arg_size() == 2) {
737 Function::const_arg_iterator AI = f->arg_begin();
738 if (AI++->getType() == PointerType::get(Type::SByteTy))
739 if (AI->getType() == PointerType::get(Type::SByteTy)) {
740 // Indicate this is a suitable call type.
747 /// @brief Perform the strcpy optimization
748 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
749 // First, check to see if src and destination are the same. If they are,
750 // then the optimization is to replace the CallInst with the destination
751 // because the call is a no-op. Note that this corresponds to the
752 // degenerate strcpy(X,X) case which should have "undefined" results
753 // according to the C specification. However, it occurs sometimes and
754 // we optimize it as a no-op.
755 Value* dest = ci->getOperand(1);
756 Value* src = ci->getOperand(2);
758 ci->replaceAllUsesWith(dest);
759 ci->eraseFromParent();
763 // Get the length of the constant string referenced by the second operand,
764 // the "src" parameter. Fail the optimization if we can't get the length
765 // (note that getConstantStringLength does lots of checks to make sure this
768 if (!getConstantStringLength(ci->getOperand(2),len))
771 // If the constant string's length is zero we can optimize this by just
772 // doing a store of 0 at the first byte of the destination
774 new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci);
775 ci->replaceAllUsesWith(dest);
776 ci->eraseFromParent();
780 // Increment the length because we actually want to memcpy the null
781 // terminator as well.
784 // Extract some information from the instruction
785 Module* M = ci->getParent()->getParent()->getParent();
787 // We have enough information to now generate the memcpy call to
788 // do the concatenation for us.
789 std::vector<Value*> vals;
790 vals.push_back(dest); // destination
791 vals.push_back(src); // source
792 vals.push_back(ConstantUInt::get(Type::UIntTy,len)); // length
793 vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
794 new CallInst(SLC.get_memcpy(), vals, "", ci);
796 // Finally, substitute the first operand of the strcat call for the
797 // strcat call itself since strcat returns its first operand; and,
798 // kill the strcat CallInst.
799 ci->replaceAllUsesWith(dest);
800 ci->eraseFromParent();
805 /// This LibCallOptimization will simplify a call to the strlen library
806 /// function by replacing it with a constant value if the string provided to
807 /// it is a constant array.
808 /// @brief Simplify the strlen library function.
809 struct StrLenOptimization : public LibCallOptimization {
810 StrLenOptimization() : LibCallOptimization("strlen",
811 "Number of 'strlen' calls simplified") {}
813 /// @brief Make sure that the "strlen" function has the right prototype
814 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
816 if (f->getReturnType() == SLC.getTargetData()->getIntPtrType())
817 if (f->arg_size() == 1)
818 if (Function::const_arg_iterator AI = f->arg_begin())
819 if (AI->getType() == PointerType::get(Type::SByteTy))
824 /// @brief Perform the strlen optimization
825 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
827 // Make sure we're dealing with an sbyte* here.
828 Value* str = ci->getOperand(1);
829 if (str->getType() != PointerType::get(Type::SByteTy))
832 // Does the call to strlen have exactly one use?
834 // Is that single use a binary operator?
835 if (BinaryOperator* bop = dyn_cast<BinaryOperator>(ci->use_back()))
836 // Is it compared against a constant integer?
837 if (ConstantInt* CI = dyn_cast<ConstantInt>(bop->getOperand(1)))
839 // Get the value the strlen result is compared to
840 uint64_t val = CI->getRawValue();
842 // If its compared against length 0 with == or !=
844 (bop->getOpcode() == Instruction::SetEQ ||
845 bop->getOpcode() == Instruction::SetNE))
847 // strlen(x) != 0 -> *x != 0
848 // strlen(x) == 0 -> *x == 0
849 LoadInst* load = new LoadInst(str,str->getName()+".first",ci);
850 BinaryOperator* rbop = BinaryOperator::create(bop->getOpcode(),
851 load, ConstantSInt::get(Type::SByteTy,0),
852 bop->getName()+".strlen", ci);
853 bop->replaceAllUsesWith(rbop);
854 bop->eraseFromParent();
855 ci->eraseFromParent();
860 // Get the length of the constant string operand
862 if (!getConstantStringLength(ci->getOperand(1),len))
865 // strlen("xyz") -> 3 (for example)
866 const Type *Ty = SLC.getTargetData()->getIntPtrType();
868 ci->replaceAllUsesWith(ConstantSInt::get(Ty, len));
870 ci->replaceAllUsesWith(ConstantUInt::get(Ty, len));
872 ci->eraseFromParent();
877 /// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value
878 /// is equal or not-equal to zero.
879 static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) {
880 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
882 Instruction *User = cast<Instruction>(*UI);
883 if (User->getOpcode() == Instruction::SetNE ||
884 User->getOpcode() == Instruction::SetEQ) {
885 if (isa<Constant>(User->getOperand(1)) &&
886 cast<Constant>(User->getOperand(1))->isNullValue())
888 } else if (CastInst *CI = dyn_cast<CastInst>(User))
889 if (CI->getType() == Type::BoolTy)
891 // Unknown instruction.
897 /// This memcmpOptimization will simplify a call to the memcmp library
899 struct memcmpOptimization : public LibCallOptimization {
900 /// @brief Default Constructor
902 : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {}
904 /// @brief Make sure that the "memcmp" function has the right prototype
905 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
906 Function::const_arg_iterator AI = F->arg_begin();
907 if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false;
908 if (!isa<PointerType>((++AI)->getType())) return false;
909 if (!(++AI)->getType()->isInteger()) return false;
910 if (!F->getReturnType()->isInteger()) return false;
914 /// Because of alignment and instruction information that we don't have, we
915 /// leave the bulk of this to the code generators.
917 /// Note that we could do much more if we could force alignment on otherwise
918 /// small aligned allocas, or if we could indicate that loads have a small
920 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) {
921 Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
923 // If the two operands are the same, return zero.
925 // memcmp(s,s,x) -> 0
926 CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
927 CI->eraseFromParent();
931 // Make sure we have a constant length.
932 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
933 if (!LenC) return false;
934 uint64_t Len = LenC->getRawValue();
936 // If the length is zero, this returns 0.
939 // memcmp(s1,s2,0) -> 0
940 CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
941 CI->eraseFromParent();
944 // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2
945 const Type *UCharPtr = PointerType::get(Type::UByteTy);
946 CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
947 CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
948 Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI);
949 Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI);
950 Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI);
951 if (RV->getType() != CI->getType())
952 RV = new CastInst(RV, CI->getType(), RV->getName(), CI);
953 CI->replaceAllUsesWith(RV);
954 CI->eraseFromParent();
958 if (IsOnlyUsedInEqualsZeroComparison(CI)) {
959 // TODO: IF both are aligned, use a short load/compare.
961 // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters
962 const Type *UCharPtr = PointerType::get(Type::UByteTy);
963 CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
964 CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
965 Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI);
966 Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI);
967 Value *D1 = BinaryOperator::createSub(S1V1, S2V1,
968 CI->getName()+".d1", CI);
969 Constant *One = ConstantInt::get(Type::IntTy, 1);
970 Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI);
971 Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI);
972 Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI);
973 Value *S2V2 = new LoadInst(G1, RHS->getName()+".val2", CI);
974 Value *D2 = BinaryOperator::createSub(S1V2, S2V2,
975 CI->getName()+".d1", CI);
976 Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI);
977 if (Or->getType() != CI->getType())
978 Or = new CastInst(Or, CI->getType(), Or->getName(), CI);
979 CI->replaceAllUsesWith(Or);
980 CI->eraseFromParent();
993 /// This LibCallOptimization will simplify a call to the memcpy library
994 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
995 /// bytes depending on the length of the string and the alignment. Additional
996 /// optimizations are possible in code generation (sequence of immediate store)
997 /// @brief Simplify the memcpy library function.
998 struct LLVMMemCpyOptimization : public LibCallOptimization {
999 /// @brief Default Constructor
1000 LLVMMemCpyOptimization() : LibCallOptimization("llvm.memcpy",
1001 "Number of 'llvm.memcpy' calls simplified") {}
1004 /// @brief Subclass Constructor
1005 LLVMMemCpyOptimization(const char* fname, const char* desc)
1006 : LibCallOptimization(fname, desc) {}
1009 /// @brief Make sure that the "memcpy" function has the right prototype
1010 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD) {
1011 // Just make sure this has 4 arguments per LLVM spec.
1012 return (f->arg_size() == 4);
1015 /// Because of alignment and instruction information that we don't have, we
1016 /// leave the bulk of this to the code generators. The optimization here just
1017 /// deals with a few degenerate cases where the length of the string and the
1018 /// alignment match the sizes of our intrinsic types so we can do a load and
1019 /// store instead of the memcpy call.
1020 /// @brief Perform the memcpy optimization.
1021 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& TD) {
1022 // Make sure we have constant int values to work with
1023 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
1026 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
1030 // If the length is larger than the alignment, we can't optimize
1031 uint64_t len = LEN->getRawValue();
1032 uint64_t alignment = ALIGN->getRawValue();
1034 alignment = 1; // Alignment 0 is identity for alignment 1
1035 if (len > alignment)
1038 // Get the type we will cast to, based on size of the string
1039 Value* dest = ci->getOperand(1);
1040 Value* src = ci->getOperand(2);
1045 // memcpy(d,s,0,a) -> noop
1046 ci->eraseFromParent();
1048 case 1: castType = Type::SByteTy; break;
1049 case 2: castType = Type::ShortTy; break;
1050 case 4: castType = Type::IntTy; break;
1051 case 8: castType = Type::LongTy; break;
1056 // Cast source and dest to the right sized primitive and then load/store
1058 new CastInst(src,PointerType::get(castType),src->getName()+".cast",ci);
1059 CastInst* DestCast =
1060 new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
1061 LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci);
1062 StoreInst* SI = new StoreInst(LI, DestCast, ci);
1063 ci->eraseFromParent();
1066 } LLVMMemCpyOptimizer;
1068 /// This LibCallOptimization will simplify a call to the memmove library
1069 /// function. It is identical to MemCopyOptimization except for the name of
1071 /// @brief Simplify the memmove library function.
1072 struct LLVMMemMoveOptimization : public LLVMMemCpyOptimization {
1073 /// @brief Default Constructor
1074 LLVMMemMoveOptimization() : LLVMMemCpyOptimization("llvm.memmove",
1075 "Number of 'llvm.memmove' calls simplified") {}
1077 } LLVMMemMoveOptimizer;
1079 /// This LibCallOptimization will simplify a call to the memset library
1080 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
1081 /// bytes depending on the length argument.
1082 struct LLVMMemSetOptimization : public LibCallOptimization {
1083 /// @brief Default Constructor
1084 LLVMMemSetOptimization() : LibCallOptimization("llvm.memset",
1085 "Number of 'llvm.memset' calls simplified") {}
1088 /// @brief Make sure that the "memset" function has the right prototype
1089 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
1090 // Just make sure this has 3 arguments per LLVM spec.
1091 return F->arg_size() == 4;
1094 /// Because of alignment and instruction information that we don't have, we
1095 /// leave the bulk of this to the code generators. The optimization here just
1096 /// deals with a few degenerate cases where the length parameter is constant
1097 /// and the alignment matches the sizes of our intrinsic types so we can do
1098 /// store instead of the memcpy call. Other calls are transformed into the
1099 /// llvm.memset intrinsic.
1100 /// @brief Perform the memset optimization.
1101 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &TD) {
1102 // Make sure we have constant int values to work with
1103 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3));
1106 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4));
1110 // Extract the length and alignment
1111 uint64_t len = LEN->getRawValue();
1112 uint64_t alignment = ALIGN->getRawValue();
1114 // Alignment 0 is identity for alignment 1
1118 // If the length is zero, this is a no-op
1120 // memset(d,c,0,a) -> noop
1121 ci->eraseFromParent();
1125 // If the length is larger than the alignment, we can't optimize
1126 if (len > alignment)
1129 // Make sure we have a constant ubyte to work with so we can extract
1130 // the value to be filled.
1131 ConstantUInt* FILL = dyn_cast<ConstantUInt>(ci->getOperand(2));
1134 if (FILL->getType() != Type::UByteTy)
1137 // memset(s,c,n) -> store s, c (for n=1,2,4,8)
1139 // Extract the fill character
1140 uint64_t fill_char = FILL->getValue();
1141 uint64_t fill_value = fill_char;
1143 // Get the type we will cast to, based on size of memory area to fill, and
1144 // and the value we will store there.
1145 Value* dest = ci->getOperand(1);
1149 castType = Type::UByteTy;
1152 castType = Type::UShortTy;
1153 fill_value |= fill_char << 8;
1156 castType = Type::UIntTy;
1157 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1160 castType = Type::ULongTy;
1161 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
1162 fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48;
1163 fill_value |= fill_char << 56;
1169 // Cast dest to the right sized primitive and then load/store
1170 CastInst* DestCast =
1171 new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
1172 new StoreInst(ConstantUInt::get(castType,fill_value),DestCast, ci);
1173 ci->eraseFromParent();
1176 } LLVMMemSetOptimizer;
1178 /// This LibCallOptimization will simplify calls to the "pow" library
1179 /// function. It looks for cases where the result of pow is well known and
1180 /// substitutes the appropriate value.
1181 /// @brief Simplify the pow library function.
1182 struct PowOptimization : public LibCallOptimization {
1184 /// @brief Default Constructor
1185 PowOptimization() : LibCallOptimization("pow",
1186 "Number of 'pow' calls simplified") {}
1188 /// @brief Make sure that the "pow" function has the right prototype
1189 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1190 // Just make sure this has 2 arguments
1191 return (f->arg_size() == 2);
1194 /// @brief Perform the pow optimization.
1195 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1196 const Type *Ty = cast<Function>(ci->getOperand(0))->getReturnType();
1197 Value* base = ci->getOperand(1);
1198 Value* expn = ci->getOperand(2);
1199 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(base)) {
1200 double Op1V = Op1->getValue();
1202 // pow(1.0,x) -> 1.0
1203 ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0));
1204 ci->eraseFromParent();
1207 } else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn)) {
1208 double Op2V = Op2->getValue();
1210 // pow(x,0.0) -> 1.0
1211 ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0));
1212 ci->eraseFromParent();
1214 } else if (Op2V == 0.5) {
1215 // pow(x,0.5) -> sqrt(x)
1216 CallInst* sqrt_inst = new CallInst(SLC.get_sqrt(), base,
1217 ci->getName()+".pow",ci);
1218 ci->replaceAllUsesWith(sqrt_inst);
1219 ci->eraseFromParent();
1221 } else if (Op2V == 1.0) {
1223 ci->replaceAllUsesWith(base);
1224 ci->eraseFromParent();
1226 } else if (Op2V == -1.0) {
1227 // pow(x,-1.0) -> 1.0/x
1228 BinaryOperator* div_inst= BinaryOperator::createDiv(
1229 ConstantFP::get(Ty,1.0), base, ci->getName()+".pow", ci);
1230 ci->replaceAllUsesWith(div_inst);
1231 ci->eraseFromParent();
1235 return false; // opt failed
1239 /// This LibCallOptimization will simplify calls to the "fprintf" library
1240 /// function. It looks for cases where the result of fprintf is not used and the
1241 /// operation can be reduced to something simpler.
1242 /// @brief Simplify the pow library function.
1243 struct FPrintFOptimization : public LibCallOptimization {
1245 /// @brief Default Constructor
1246 FPrintFOptimization() : LibCallOptimization("fprintf",
1247 "Number of 'fprintf' calls simplified") {}
1249 /// @brief Make sure that the "fprintf" function has the right prototype
1250 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1251 // Just make sure this has at least 2 arguments
1252 return (f->arg_size() >= 2);
1255 /// @brief Perform the fprintf optimization.
1256 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
1257 // If the call has more than 3 operands, we can't optimize it
1258 if (ci->getNumOperands() > 4 || ci->getNumOperands() <= 2)
1261 // If the result of the fprintf call is used, none of these optimizations
1263 if (!ci->use_empty())
1266 // All the optimizations depend on the length of the second argument and the
1267 // fact that it is a constant string array. Check that now
1269 ConstantArray* CA = 0;
1270 if (!getConstantStringLength(ci->getOperand(2), len, &CA))
1273 if (ci->getNumOperands() == 3) {
1274 // Make sure there's no % in the constant array
1275 for (unsigned i = 0; i < len; ++i) {
1276 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) {
1277 // Check for the null terminator
1278 if (CI->getRawValue() == '%')
1279 return false; // we found end of string
1285 // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file)
1286 const Type* FILEptr_type = ci->getOperand(1)->getType();
1287 Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
1291 // Make sure that the fprintf() and fwrite() functions both take the
1292 // same type of char pointer.
1293 if (ci->getOperand(2)->getType() !=
1294 fwrite_func->getFunctionType()->getParamType(0))
1297 std::vector<Value*> args;
1298 args.push_back(ci->getOperand(2));
1299 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
1300 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
1301 args.push_back(ci->getOperand(1));
1302 new CallInst(fwrite_func,args,ci->getName(),ci);
1303 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
1304 ci->eraseFromParent();
1308 // The remaining optimizations require the format string to be length 2
1313 // The first character has to be a %
1314 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0)))
1315 if (CI->getRawValue() != '%')
1318 // Get the second character and switch on its value
1319 ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
1320 switch (CI->getRawValue()) {
1324 ConstantArray* CA = 0;
1325 if (!getConstantStringLength(ci->getOperand(3), len, &CA))
1328 // fprintf(file,"%s",str) -> fwrite(fmt,strlen(fmt),1,file)
1329 const Type* FILEptr_type = ci->getOperand(1)->getType();
1330 Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
1333 std::vector<Value*> args;
1334 args.push_back(CastToCStr(ci->getOperand(3), *ci));
1335 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
1336 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
1337 args.push_back(ci->getOperand(1));
1338 new CallInst(fwrite_func,args,ci->getName(),ci);
1339 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
1344 ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(3));
1348 const Type* FILEptr_type = ci->getOperand(1)->getType();
1349 Function* fputc_func = SLC.get_fputc(FILEptr_type);
1352 CastInst* cast = new CastInst(CI,Type::IntTy,CI->getName()+".int",ci);
1353 new CallInst(fputc_func,cast,ci->getOperand(1),"",ci);
1354 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
1360 ci->eraseFromParent();
1365 /// This LibCallOptimization will simplify calls to the "sprintf" library
1366 /// function. It looks for cases where the result of sprintf is not used and the
1367 /// operation can be reduced to something simpler.
1368 /// @brief Simplify the pow library function.
1369 struct SPrintFOptimization : public LibCallOptimization {
1371 /// @brief Default Constructor
1372 SPrintFOptimization() : LibCallOptimization("sprintf",
1373 "Number of 'sprintf' calls simplified") {}
1375 /// @brief Make sure that the "fprintf" function has the right prototype
1376 virtual bool ValidateCalledFunction(const Function *f, SimplifyLibCalls &SLC){
1377 // Just make sure this has at least 2 arguments
1378 return (f->getReturnType() == Type::IntTy && f->arg_size() >= 2);
1381 /// @brief Perform the sprintf optimization.
1382 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1383 // If the call has more than 3 operands, we can't optimize it
1384 if (ci->getNumOperands() > 4 || ci->getNumOperands() < 3)
1387 // All the optimizations depend on the length of the second argument and the
1388 // fact that it is a constant string array. Check that now
1390 ConstantArray* CA = 0;
1391 if (!getConstantStringLength(ci->getOperand(2), len, &CA))
1394 if (ci->getNumOperands() == 3) {
1396 // If the length is 0, we just need to store a null byte
1397 new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci);
1398 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0));
1399 ci->eraseFromParent();
1403 // Make sure there's no % in the constant array
1404 for (unsigned i = 0; i < len; ++i) {
1405 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) {
1406 // Check for the null terminator
1407 if (CI->getRawValue() == '%')
1408 return false; // we found a %, can't optimize
1410 return false; // initializer is not constant int, can't optimize
1414 // Increment length because we want to copy the null byte too
1417 // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
1418 Function* memcpy_func = SLC.get_memcpy();
1421 std::vector<Value*> args;
1422 args.push_back(ci->getOperand(1));
1423 args.push_back(ci->getOperand(2));
1424 args.push_back(ConstantUInt::get(Type::UIntTy,len));
1425 args.push_back(ConstantUInt::get(Type::UIntTy,1));
1426 new CallInst(memcpy_func,args,"",ci);
1427 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
1428 ci->eraseFromParent();
1432 // The remaining optimizations require the format string to be length 2
1437 // The first character has to be a %
1438 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0)))
1439 if (CI->getRawValue() != '%')
1442 // Get the second character and switch on its value
1443 ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
1444 switch (CI->getRawValue()) {
1446 // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1447 Function* strlen_func = SLC.get_strlen();
1448 Function* memcpy_func = SLC.get_memcpy();
1449 if (!strlen_func || !memcpy_func)
1452 Value *Len = new CallInst(strlen_func, CastToCStr(ci->getOperand(3), *ci),
1453 ci->getOperand(3)->getName()+".len", ci);
1454 Value *Len1 = BinaryOperator::createAdd(Len,
1455 ConstantInt::get(Len->getType(), 1),
1456 Len->getName()+"1", ci);
1457 if (Len1->getType() != Type::UIntTy)
1458 Len1 = new CastInst(Len1, Type::UIntTy, Len1->getName(), ci);
1459 std::vector<Value*> args;
1460 args.push_back(CastToCStr(ci->getOperand(1), *ci));
1461 args.push_back(CastToCStr(ci->getOperand(3), *ci));
1462 args.push_back(Len1);
1463 args.push_back(ConstantUInt::get(Type::UIntTy,1));
1464 new CallInst(memcpy_func, args, "", ci);
1466 // The strlen result is the unincremented number of bytes in the string.
1467 if (!ci->use_empty()) {
1468 if (Len->getType() != ci->getType())
1469 Len = new CastInst(Len, ci->getType(), Len->getName(), ci);
1470 ci->replaceAllUsesWith(Len);
1472 ci->eraseFromParent();
1476 // sprintf(dest,"%c",chr) -> store chr, dest
1477 CastInst* cast = new CastInst(ci->getOperand(3),Type::SByteTy,"char",ci);
1478 new StoreInst(cast, ci->getOperand(1), ci);
1479 GetElementPtrInst* gep = new GetElementPtrInst(ci->getOperand(1),
1480 ConstantUInt::get(Type::UIntTy,1),ci->getOperand(1)->getName()+".end",
1482 new StoreInst(ConstantInt::get(Type::SByteTy,0),gep,ci);
1483 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
1484 ci->eraseFromParent();
1492 /// This LibCallOptimization will simplify calls to the "fputs" library
1493 /// function. It looks for cases where the result of fputs is not used and the
1494 /// operation can be reduced to something simpler.
1495 /// @brief Simplify the pow library function.
1496 struct PutsOptimization : public LibCallOptimization {
1498 /// @brief Default Constructor
1499 PutsOptimization() : LibCallOptimization("fputs",
1500 "Number of 'fputs' calls simplified") {}
1502 /// @brief Make sure that the "fputs" function has the right prototype
1503 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1504 // Just make sure this has 2 arguments
1505 return F->arg_size() == 2;
1508 /// @brief Perform the fputs optimization.
1509 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) {
1510 // If the result is used, none of these optimizations work
1511 if (!ci->use_empty())
1514 // All the optimizations depend on the length of the first argument and the
1515 // fact that it is a constant string array. Check that now
1517 if (!getConstantStringLength(ci->getOperand(1), len))
1522 // fputs("",F) -> noop
1526 // fputs(s,F) -> fputc(s[0],F) (if s is constant and strlen(s) == 1)
1527 const Type* FILEptr_type = ci->getOperand(2)->getType();
1528 Function* fputc_func = SLC.get_fputc(FILEptr_type);
1531 LoadInst* loadi = new LoadInst(ci->getOperand(1),
1532 ci->getOperand(1)->getName()+".byte",ci);
1533 CastInst* casti = new CastInst(loadi,Type::IntTy,
1534 loadi->getName()+".int",ci);
1535 new CallInst(fputc_func,casti,ci->getOperand(2),"",ci);
1540 // fputs(s,F) -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1)
1541 const Type* FILEptr_type = ci->getOperand(2)->getType();
1542 Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
1545 std::vector<Value*> parms;
1546 parms.push_back(ci->getOperand(1));
1547 parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
1548 parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
1549 parms.push_back(ci->getOperand(2));
1550 new CallInst(fwrite_func,parms,"",ci);
1554 ci->eraseFromParent();
1555 return true; // success
1559 /// This LibCallOptimization will simplify calls to the "isdigit" library
1560 /// function. It simply does range checks the parameter explicitly.
1561 /// @brief Simplify the isdigit library function.
1562 struct isdigitOptimization : public LibCallOptimization {
1564 isdigitOptimization() : LibCallOptimization("isdigit",
1565 "Number of 'isdigit' calls simplified") {}
1567 /// @brief Make sure that the "isdigit" function has the right prototype
1568 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1569 // Just make sure this has 1 argument
1570 return (f->arg_size() == 1);
1573 /// @brief Perform the toascii optimization.
1574 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1575 if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1))) {
1576 // isdigit(c) -> 0 or 1, if 'c' is constant
1577 uint64_t val = CI->getRawValue();
1578 if (val >= '0' && val <='9')
1579 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
1581 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0));
1582 ci->eraseFromParent();
1586 // isdigit(c) -> (unsigned)c - '0' <= 9
1588 new CastInst(ci->getOperand(1),Type::UIntTy,
1589 ci->getOperand(1)->getName()+".uint",ci);
1590 BinaryOperator* sub_inst = BinaryOperator::createSub(cast,
1591 ConstantUInt::get(Type::UIntTy,0x30),
1592 ci->getOperand(1)->getName()+".sub",ci);
1593 SetCondInst* setcond_inst = new SetCondInst(Instruction::SetLE,sub_inst,
1594 ConstantUInt::get(Type::UIntTy,9),
1595 ci->getOperand(1)->getName()+".cmp",ci);
1597 new CastInst(setcond_inst,Type::IntTy,
1598 ci->getOperand(1)->getName()+".isdigit",ci);
1599 ci->replaceAllUsesWith(c2);
1600 ci->eraseFromParent();
1605 struct isasciiOptimization : public LibCallOptimization {
1607 isasciiOptimization()
1608 : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {}
1610 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1611 return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() &&
1612 F->getReturnType()->isInteger();
1615 /// @brief Perform the isascii optimization.
1616 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1617 // isascii(c) -> (unsigned)c < 128
1618 Value *V = CI->getOperand(1);
1619 if (V->getType()->isSigned())
1620 V = new CastInst(V, V->getType()->getUnsignedVersion(), V->getName(), CI);
1621 Value *Cmp = BinaryOperator::createSetLT(V, ConstantUInt::get(V->getType(),
1623 V->getName()+".isascii", CI);
1624 if (Cmp->getType() != CI->getType())
1625 Cmp = new CastInst(Cmp, CI->getType(), Cmp->getName(), CI);
1626 CI->replaceAllUsesWith(Cmp);
1627 CI->eraseFromParent();
1633 /// This LibCallOptimization will simplify calls to the "toascii" library
1634 /// function. It simply does the corresponding and operation to restrict the
1635 /// range of values to the ASCII character set (0-127).
1636 /// @brief Simplify the toascii library function.
1637 struct ToAsciiOptimization : public LibCallOptimization {
1639 /// @brief Default Constructor
1640 ToAsciiOptimization() : LibCallOptimization("toascii",
1641 "Number of 'toascii' calls simplified") {}
1643 /// @brief Make sure that the "fputs" function has the right prototype
1644 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){
1645 // Just make sure this has 2 arguments
1646 return (f->arg_size() == 1);
1649 /// @brief Perform the toascii optimization.
1650 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) {
1651 // toascii(c) -> (c & 0x7f)
1652 Value* chr = ci->getOperand(1);
1653 BinaryOperator* and_inst = BinaryOperator::createAnd(chr,
1654 ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci);
1655 ci->replaceAllUsesWith(and_inst);
1656 ci->eraseFromParent();
1661 /// This LibCallOptimization will simplify calls to the "ffs" library
1662 /// calls which find the first set bit in an int, long, or long long. The
1663 /// optimization is to compute the result at compile time if the argument is
1665 /// @brief Simplify the ffs library function.
1666 struct FFSOptimization : public LibCallOptimization {
1668 /// @brief Subclass Constructor
1669 FFSOptimization(const char* funcName, const char* description)
1670 : LibCallOptimization(funcName, description) {}
1673 /// @brief Default Constructor
1674 FFSOptimization() : LibCallOptimization("ffs",
1675 "Number of 'ffs' calls simplified") {}
1677 /// @brief Make sure that the "ffs" function has the right prototype
1678 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1679 // Just make sure this has 2 arguments
1680 return F->arg_size() == 1 && F->getReturnType() == Type::IntTy;
1683 /// @brief Perform the ffs optimization.
1684 virtual bool OptimizeCall(CallInst *TheCall, SimplifyLibCalls &SLC) {
1685 if (ConstantInt *CI = dyn_cast<ConstantInt>(TheCall->getOperand(1))) {
1686 // ffs(cnst) -> bit#
1687 // ffsl(cnst) -> bit#
1688 // ffsll(cnst) -> bit#
1689 uint64_t val = CI->getRawValue();
1693 while ((val & 1) == 0) {
1698 TheCall->replaceAllUsesWith(ConstantSInt::get(Type::IntTy, result));
1699 TheCall->eraseFromParent();
1703 // ffs(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1704 // ffsl(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1705 // ffsll(x) -> x == 0 ? 0 : llvm.cttz(x)+1
1706 const Type *ArgType = TheCall->getOperand(1)->getType();
1707 ArgType = ArgType->getUnsignedVersion();
1708 const char *CTTZName;
1709 switch (ArgType->getTypeID()) {
1710 default: assert(0 && "Unknown unsigned type!");
1711 case Type::UByteTyID : CTTZName = "llvm.cttz.i8" ; break;
1712 case Type::UShortTyID: CTTZName = "llvm.cttz.i16"; break;
1713 case Type::UIntTyID : CTTZName = "llvm.cttz.i32"; break;
1714 case Type::ULongTyID : CTTZName = "llvm.cttz.i64"; break;
1717 Function *F = SLC.getModule()->getOrInsertFunction(CTTZName, ArgType,
1719 Value *V = new CastInst(TheCall->getOperand(1), ArgType, "tmp", TheCall);
1720 Value *V2 = new CallInst(F, V, "tmp", TheCall);
1721 V2 = new CastInst(V2, Type::IntTy, "tmp", TheCall);
1722 V2 = BinaryOperator::createAdd(V2, ConstantSInt::get(Type::IntTy, 1),
1725 BinaryOperator::createSetEQ(V, Constant::getNullValue(V->getType()),
1727 V2 = new SelectInst(Cond, ConstantInt::get(Type::IntTy, 0), V2,
1728 TheCall->getName(), TheCall);
1729 TheCall->replaceAllUsesWith(V2);
1730 TheCall->eraseFromParent();
1735 /// This LibCallOptimization will simplify calls to the "ffsl" library
1736 /// calls. It simply uses FFSOptimization for which the transformation is
1738 /// @brief Simplify the ffsl library function.
1739 struct FFSLOptimization : public FFSOptimization {
1741 /// @brief Default Constructor
1742 FFSLOptimization() : FFSOptimization("ffsl",
1743 "Number of 'ffsl' calls simplified") {}
1747 /// This LibCallOptimization will simplify calls to the "ffsll" library
1748 /// calls. It simply uses FFSOptimization for which the transformation is
1750 /// @brief Simplify the ffsl library function.
1751 struct FFSLLOptimization : public FFSOptimization {
1753 /// @brief Default Constructor
1754 FFSLLOptimization() : FFSOptimization("ffsll",
1755 "Number of 'ffsll' calls simplified") {}
1760 /// This LibCallOptimization will simplify calls to the "floor" library
1762 /// @brief Simplify the floor library function.
1763 struct FloorOptimization : public LibCallOptimization {
1765 : LibCallOptimization("floor", "Number of 'floor' calls simplified") {}
1767 /// @brief Make sure that the "floor" function has the right prototype
1768 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
1769 return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy &&
1770 F->getReturnType() == Type::DoubleTy;
1773 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
1774 // If this is a float argument passed in, convert to floorf.
1775 // e.g. floor((double)FLT) -> (double)floorf(FLT). There can be no loss of
1776 // precision due to this.
1777 if (CastInst *Cast = dyn_cast<CastInst>(CI->getOperand(1)))
1778 if (Cast->getOperand(0)->getType() == Type::FloatTy) {
1779 Value *New = new CallInst(SLC.get_floorf(), Cast->getOperand(0),
1781 New = new CastInst(New, Type::DoubleTy, CI->getName(), CI);
1782 CI->replaceAllUsesWith(New);
1783 CI->eraseFromParent();
1784 if (Cast->use_empty())
1785 Cast->eraseFromParent();
1788 return false; // opt failed
1793 FloorOptimization FloorOptimizer;
1798 /// A function to compute the length of a null-terminated constant array of
1799 /// integers. This function can't rely on the size of the constant array
1800 /// because there could be a null terminator in the middle of the array.
1801 /// We also have to bail out if we find a non-integer constant initializer
1802 /// of one of the elements or if there is no null-terminator. The logic
1803 /// below checks each of these conditions and will return true only if all
1804 /// conditions are met. In that case, the \p len parameter is set to the length
1805 /// of the null-terminated string. If false is returned, the conditions were
1806 /// not met and len is set to 0.
1807 /// @brief Get the length of a constant string (null-terminated array).
1808 bool getConstantStringLength(Value *V, uint64_t &len, ConstantArray **CA) {
1809 assert(V != 0 && "Invalid args to getConstantStringLength");
1810 len = 0; // make sure we initialize this
1812 // If the value is not a GEP instruction nor a constant expression with a
1813 // GEP instruction, then return false because ConstantArray can't occur
1815 if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V))
1817 else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V))
1818 if (CE->getOpcode() == Instruction::GetElementPtr)
1825 // Make sure the GEP has exactly three arguments.
1826 if (GEP->getNumOperands() != 3)
1829 // Check to make sure that the first operand of the GEP is an integer and
1830 // has value 0 so that we are sure we're indexing into the initializer.
1831 if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
1832 if (!op1->isNullValue())
1837 // Ensure that the second operand is a ConstantInt. If it isn't then this
1838 // GEP is wonky and we're not really sure what were referencing into and
1839 // better of not optimizing it. While we're at it, get the second index
1840 // value. We'll need this later for indexing the ConstantArray.
1841 uint64_t start_idx = 0;
1842 if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
1843 start_idx = CI->getRawValue();
1847 // The GEP instruction, constant or instruction, must reference a global
1848 // variable that is a constant and is initialized. The referenced constant
1849 // initializer is the array that we'll use for optimization.
1850 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
1851 if (!GV || !GV->isConstant() || !GV->hasInitializer())
1854 // Get the initializer.
1855 Constant* INTLZR = GV->getInitializer();
1857 // Handle the ConstantAggregateZero case
1858 if (ConstantAggregateZero *CAZ = dyn_cast<ConstantAggregateZero>(INTLZR)) {
1859 // This is a degenerate case. The initializer is constant zero so the
1860 // length of the string must be zero.
1865 // Must be a Constant Array
1866 ConstantArray* A = dyn_cast<ConstantArray>(INTLZR);
1870 // Get the number of elements in the array
1871 uint64_t max_elems = A->getType()->getNumElements();
1873 // Traverse the constant array from start_idx (derived above) which is
1874 // the place the GEP refers to in the array.
1875 for (len = start_idx; len < max_elems; len++) {
1876 if (ConstantInt *CI = dyn_cast<ConstantInt>(A->getOperand(len))) {
1877 // Check for the null terminator
1878 if (CI->isNullValue())
1879 break; // we found end of string
1881 return false; // This array isn't suitable, non-int initializer
1884 if (len >= max_elems)
1885 return false; // This array isn't null terminated
1887 // Subtract out the initial value from the length
1891 return true; // success!
1894 /// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*,
1895 /// inserting the cast before IP, and return the cast.
1896 /// @brief Cast a value to a "C" string.
1897 Value *CastToCStr(Value *V, Instruction &IP) {
1898 const Type *SBPTy = PointerType::get(Type::SByteTy);
1899 if (V->getType() != SBPTy)
1900 return new CastInst(V, SBPTy, V->getName(), &IP);
1905 // Additional cases that we need to add to this file:
1908 // * cbrt(expN(X)) -> expN(x/3)
1909 // * cbrt(sqrt(x)) -> pow(x,1/6)
1910 // * cbrt(sqrt(x)) -> pow(x,1/9)
1913 // * cos(-x) -> cos(x)
1916 // * exp(log(x)) -> x
1919 // * log(exp(x)) -> x
1920 // * log(x**y) -> y*log(x)
1921 // * log(exp(y)) -> y*log(e)
1922 // * log(exp2(y)) -> y*log(2)
1923 // * log(exp10(y)) -> y*log(10)
1924 // * log(sqrt(x)) -> 0.5*log(x)
1925 // * log(pow(x,y)) -> y*log(x)
1927 // lround, lroundf, lroundl:
1928 // * lround(cnst) -> cnst'
1931 // * memcmp(x,y,l) -> cnst
1932 // (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
1935 // * memmove(d,s,l,a) -> memcpy(d,s,l,a)
1936 // (if s is a global constant array)
1939 // * pow(exp(x),y) -> exp(x*y)
1940 // * pow(sqrt(x),y) -> pow(x,y*0.5)
1941 // * pow(pow(x,y),z)-> pow(x,y*z)
1944 // * puts("") -> fputc("\n",stdout) (how do we get "stdout"?)
1946 // round, roundf, roundl:
1947 // * round(cnst) -> cnst'
1950 // * signbit(cnst) -> cnst'
1951 // * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1953 // sqrt, sqrtf, sqrtl:
1954 // * sqrt(expN(x)) -> expN(x*0.5)
1955 // * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1956 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1959 // * stpcpy(str, "literal") ->
1960 // llvm.memcpy(str,"literal",strlen("literal")+1,1)
1962 // * strrchr(s,c) -> reverse_offset_of_in(c,s)
1963 // (if c is a constant integer and s is a constant string)
1964 // * strrchr(s1,0) -> strchr(s1,0)
1967 // * strncat(x,y,0) -> x
1968 // * strncat(x,y,0) -> x (if strlen(y) = 0)
1969 // * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y))
1972 // * strncpy(d,s,0) -> d
1973 // * strncpy(d,s,l) -> memcpy(d,s,l,1)
1974 // (if s and l are constants)
1977 // * strpbrk(s,a) -> offset_in_for(s,a)
1978 // (if s and a are both constant strings)
1979 // * strpbrk(s,"") -> 0
1980 // * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
1983 // * strspn(s,a) -> const_int (if both args are constant)
1984 // * strspn("",a) -> 0
1985 // * strspn(s,"") -> 0
1986 // * strcspn(s,a) -> const_int (if both args are constant)
1987 // * strcspn("",a) -> 0
1988 // * strcspn(s,"") -> strlen(a)
1991 // * strstr(x,x) -> x
1992 // * strstr(s1,s2) -> offset_of_s2_in(s1)
1993 // (if s1 and s2 are constant strings)
1996 // * tan(atan(x)) -> x
1998 // trunc, truncf, truncl:
1999 // * trunc(cnst) -> cnst'