LLVM API Documentation
00001 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Reid Spencer and is distributed under the 00006 // University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a module pass that applies a variety of small 00011 // optimizations for calls to specific well-known function calls (e.g. runtime 00012 // library functions). For example, a call to the function "exit(3)" that 00013 // occurs within the main() function can be transformed into a simple "return 3" 00014 // instruction. Any optimization that takes this form (replace call to library 00015 // function with simpler code that provides the same result) belongs in this 00016 // file. 00017 // 00018 //===----------------------------------------------------------------------===// 00019 00020 #define DEBUG_TYPE "simplify-libcalls" 00021 #include "llvm/Constants.h" 00022 #include "llvm/DerivedTypes.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Module.h" 00025 #include "llvm/Pass.h" 00026 #include "llvm/ADT/hash_map" 00027 #include "llvm/ADT/Statistic.h" 00028 #include "llvm/Config/config.h" 00029 #include "llvm/Support/Debug.h" 00030 #include "llvm/Target/TargetData.h" 00031 #include "llvm/Transforms/IPO.h" 00032 using namespace llvm; 00033 00034 namespace { 00035 00036 /// This statistic keeps track of the total number of library calls that have 00037 /// been simplified regardless of which call it is. 00038 Statistic<> SimplifiedLibCalls("simplify-libcalls", 00039 "Number of library calls simplified"); 00040 00041 // Forward declarations 00042 class LibCallOptimization; 00043 class SimplifyLibCalls; 00044 00045 /// This list is populated by the constructor for LibCallOptimization class. 00046 /// Therefore all subclasses are registered here at static initialization time 00047 /// and this list is what the SimplifyLibCalls pass uses to apply the individual 00048 /// optimizations to the call sites. 00049 /// @brief The list of optimizations deriving from LibCallOptimization 00050 static LibCallOptimization *OptList = 0; 00051 00052 /// This class is the abstract base class for the set of optimizations that 00053 /// corresponds to one library call. The SimplifyLibCalls pass will call the 00054 /// ValidateCalledFunction method to ask the optimization if a given Function 00055 /// is the kind that the optimization can handle. If the subclass returns true, 00056 /// then SImplifyLibCalls will also call the OptimizeCall method to perform, 00057 /// or attempt to perform, the optimization(s) for the library call. Otherwise, 00058 /// OptimizeCall won't be called. Subclasses are responsible for providing the 00059 /// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization 00060 /// constructor. This is used to efficiently select which call instructions to 00061 /// optimize. The criteria for a "lib call" is "anything with well known 00062 /// semantics", typically a library function that is defined by an international 00063 /// standard. Because the semantics are well known, the optimizations can 00064 /// generally short-circuit actually calling the function if there's a simpler 00065 /// way (e.g. strlen(X) can be reduced to a constant if X is a constant global). 00066 /// @brief Base class for library call optimizations 00067 class LibCallOptimization { 00068 LibCallOptimization **Prev, *Next; 00069 const char *FunctionName; ///< Name of the library call we optimize 00070 #ifndef NDEBUG 00071 Statistic<> occurrences; ///< debug statistic (-debug-only=simplify-libcalls) 00072 #endif 00073 public: 00074 /// The \p fname argument must be the name of the library function being 00075 /// optimized by the subclass. 00076 /// @brief Constructor that registers the optimization. 00077 LibCallOptimization(const char *FName, const char *Description) 00078 : FunctionName(FName) 00079 #ifndef NDEBUG 00080 , occurrences("simplify-libcalls", Description) 00081 #endif 00082 { 00083 // Register this optimizer in the list of optimizations. 00084 Next = OptList; 00085 OptList = this; 00086 Prev = &OptList; 00087 if (Next) Next->Prev = &Next; 00088 } 00089 00090 /// getNext - All libcall optimizations are chained together into a list, 00091 /// return the next one in the list. 00092 LibCallOptimization *getNext() { return Next; } 00093 00094 /// @brief Deregister from the optlist 00095 virtual ~LibCallOptimization() { 00096 *Prev = Next; 00097 if (Next) Next->Prev = Prev; 00098 } 00099 00100 /// The implementation of this function in subclasses should determine if 00101 /// \p F is suitable for the optimization. This method is called by 00102 /// SimplifyLibCalls::runOnModule to short circuit visiting all the call 00103 /// sites of such a function if that function is not suitable in the first 00104 /// place. If the called function is suitabe, this method should return true; 00105 /// false, otherwise. This function should also perform any lazy 00106 /// initialization that the LibCallOptimization needs to do, if its to return 00107 /// true. This avoids doing initialization until the optimizer is actually 00108 /// going to be called upon to do some optimization. 00109 /// @brief Determine if the function is suitable for optimization 00110 virtual bool ValidateCalledFunction( 00111 const Function* F, ///< The function that is the target of call sites 00112 SimplifyLibCalls& SLC ///< The pass object invoking us 00113 ) = 0; 00114 00115 /// The implementations of this function in subclasses is the heart of the 00116 /// SimplifyLibCalls algorithm. Sublcasses of this class implement 00117 /// OptimizeCall to determine if (a) the conditions are right for optimizing 00118 /// the call and (b) to perform the optimization. If an action is taken 00119 /// against ci, the subclass is responsible for returning true and ensuring 00120 /// that ci is erased from its parent. 00121 /// @brief Optimize a call, if possible. 00122 virtual bool OptimizeCall( 00123 CallInst* ci, ///< The call instruction that should be optimized. 00124 SimplifyLibCalls& SLC ///< The pass object invoking us 00125 ) = 0; 00126 00127 /// @brief Get the name of the library call being optimized 00128 const char *getFunctionName() const { return FunctionName; } 00129 00130 /// @brief Called by SimplifyLibCalls to update the occurrences statistic. 00131 void succeeded() { 00132 #ifndef NDEBUG 00133 DEBUG(++occurrences); 00134 #endif 00135 } 00136 }; 00137 00138 /// This class is an LLVM Pass that applies each of the LibCallOptimization 00139 /// instances to all the call sites in a module, relatively efficiently. The 00140 /// purpose of this pass is to provide optimizations for calls to well-known 00141 /// functions with well-known semantics, such as those in the c library. The 00142 /// class provides the basic infrastructure for handling runOnModule. Whenever 00143 /// this pass finds a function call, it asks the appropriate optimizer to 00144 /// validate the call (ValidateLibraryCall). If it is validated, then 00145 /// the OptimizeCall method is also called. 00146 /// @brief A ModulePass for optimizing well-known function calls. 00147 class SimplifyLibCalls : public ModulePass { 00148 public: 00149 /// We need some target data for accurate signature details that are 00150 /// target dependent. So we require target data in our AnalysisUsage. 00151 /// @brief Require TargetData from AnalysisUsage. 00152 virtual void getAnalysisUsage(AnalysisUsage& Info) const { 00153 // Ask that the TargetData analysis be performed before us so we can use 00154 // the target data. 00155 Info.addRequired<TargetData>(); 00156 } 00157 00158 /// For this pass, process all of the function calls in the module, calling 00159 /// ValidateLibraryCall and OptimizeCall as appropriate. 00160 /// @brief Run all the lib call optimizations on a Module. 00161 virtual bool runOnModule(Module &M) { 00162 reset(M); 00163 00164 bool result = false; 00165 hash_map<std::string, LibCallOptimization*> OptznMap; 00166 for (LibCallOptimization *Optzn = OptList; Optzn; Optzn = Optzn->getNext()) 00167 OptznMap[Optzn->getFunctionName()] = Optzn; 00168 00169 // The call optimizations can be recursive. That is, the optimization might 00170 // generate a call to another function which can also be optimized. This way 00171 // we make the LibCallOptimization instances very specific to the case they 00172 // handle. It also means we need to keep running over the function calls in 00173 // the module until we don't get any more optimizations possible. 00174 bool found_optimization = false; 00175 do { 00176 found_optimization = false; 00177 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) { 00178 // All the "well-known" functions are external and have external linkage 00179 // because they live in a runtime library somewhere and were (probably) 00180 // not compiled by LLVM. So, we only act on external functions that 00181 // have external linkage and non-empty uses. 00182 if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty()) 00183 continue; 00184 00185 // Get the optimization class that pertains to this function 00186 hash_map<std::string, LibCallOptimization*>::iterator OMI = 00187 OptznMap.find(FI->getName()); 00188 if (OMI == OptznMap.end()) continue; 00189 00190 LibCallOptimization *CO = OMI->second; 00191 00192 // Make sure the called function is suitable for the optimization 00193 if (!CO->ValidateCalledFunction(FI, *this)) 00194 continue; 00195 00196 // Loop over each of the uses of the function 00197 for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end(); 00198 UI != UE ; ) { 00199 // If the use of the function is a call instruction 00200 if (CallInst* CI = dyn_cast<CallInst>(*UI++)) { 00201 // Do the optimization on the LibCallOptimization. 00202 if (CO->OptimizeCall(CI, *this)) { 00203 ++SimplifiedLibCalls; 00204 found_optimization = result = true; 00205 CO->succeeded(); 00206 } 00207 } 00208 } 00209 } 00210 } while (found_optimization); 00211 00212 return result; 00213 } 00214 00215 /// @brief Return the *current* module we're working on. 00216 Module* getModule() const { return M; } 00217 00218 /// @brief Return the *current* target data for the module we're working on. 00219 TargetData* getTargetData() const { return TD; } 00220 00221 /// @brief Return the size_t type -- syntactic shortcut 00222 const Type* getIntPtrType() const { return TD->getIntPtrType(); } 00223 00224 /// @brief Return a Function* for the fputc libcall 00225 Function* get_fputc(const Type* FILEptr_type) { 00226 if (!fputc_func) 00227 fputc_func = M->getOrInsertFunction("fputc", Type::IntTy, Type::IntTy, 00228 FILEptr_type, NULL); 00229 return fputc_func; 00230 } 00231 00232 /// @brief Return a Function* for the fwrite libcall 00233 Function* get_fwrite(const Type* FILEptr_type) { 00234 if (!fwrite_func) 00235 fwrite_func = M->getOrInsertFunction("fwrite", TD->getIntPtrType(), 00236 PointerType::get(Type::SByteTy), 00237 TD->getIntPtrType(), 00238 TD->getIntPtrType(), 00239 FILEptr_type, NULL); 00240 return fwrite_func; 00241 } 00242 00243 /// @brief Return a Function* for the sqrt libcall 00244 Function* get_sqrt() { 00245 if (!sqrt_func) 00246 sqrt_func = M->getOrInsertFunction("sqrt", Type::DoubleTy, 00247 Type::DoubleTy, NULL); 00248 return sqrt_func; 00249 } 00250 00251 /// @brief Return a Function* for the strlen libcall 00252 Function* get_strcpy() { 00253 if (!strcpy_func) 00254 strcpy_func = M->getOrInsertFunction("strcpy", 00255 PointerType::get(Type::SByteTy), 00256 PointerType::get(Type::SByteTy), 00257 PointerType::get(Type::SByteTy), 00258 NULL); 00259 return strcpy_func; 00260 } 00261 00262 /// @brief Return a Function* for the strlen libcall 00263 Function* get_strlen() { 00264 if (!strlen_func) 00265 strlen_func = M->getOrInsertFunction("strlen", TD->getIntPtrType(), 00266 PointerType::get(Type::SByteTy), 00267 NULL); 00268 return strlen_func; 00269 } 00270 00271 /// @brief Return a Function* for the memchr libcall 00272 Function* get_memchr() { 00273 if (!memchr_func) 00274 memchr_func = M->getOrInsertFunction("memchr", 00275 PointerType::get(Type::SByteTy), 00276 PointerType::get(Type::SByteTy), 00277 Type::IntTy, TD->getIntPtrType(), 00278 NULL); 00279 return memchr_func; 00280 } 00281 00282 /// @brief Return a Function* for the memcpy libcall 00283 Function* get_memcpy() { 00284 if (!memcpy_func) { 00285 const Type *SBP = PointerType::get(Type::SByteTy); 00286 const char *N = TD->getIntPtrType() == Type::UIntTy ? 00287 "llvm.memcpy.i32" : "llvm.memcpy.i64"; 00288 memcpy_func = M->getOrInsertFunction(N, Type::VoidTy, SBP, SBP, 00289 TD->getIntPtrType(), Type::UIntTy, 00290 NULL); 00291 } 00292 return memcpy_func; 00293 } 00294 00295 Function *getUnaryFloatFunction(const char *Name, Function *&Cache) { 00296 if (!Cache) 00297 Cache = M->getOrInsertFunction(Name, Type::FloatTy, Type::FloatTy, NULL); 00298 return Cache; 00299 } 00300 00301 Function *get_floorf() { return getUnaryFloatFunction("floorf", floorf_func);} 00302 Function *get_ceilf() { return getUnaryFloatFunction( "ceilf", ceilf_func);} 00303 Function *get_roundf() { return getUnaryFloatFunction("roundf", roundf_func);} 00304 Function *get_rintf() { return getUnaryFloatFunction( "rintf", rintf_func);} 00305 Function *get_nearbyintf() { return getUnaryFloatFunction("nearbyintf", 00306 nearbyintf_func); } 00307 private: 00308 /// @brief Reset our cached data for a new Module 00309 void reset(Module& mod) { 00310 M = &mod; 00311 TD = &getAnalysis<TargetData>(); 00312 fputc_func = 0; 00313 fwrite_func = 0; 00314 memcpy_func = 0; 00315 memchr_func = 0; 00316 sqrt_func = 0; 00317 strcpy_func = 0; 00318 strlen_func = 0; 00319 floorf_func = 0; 00320 ceilf_func = 0; 00321 roundf_func = 0; 00322 rintf_func = 0; 00323 nearbyintf_func = 0; 00324 } 00325 00326 private: 00327 /// Caches for function pointers. 00328 Function *fputc_func, *fwrite_func; 00329 Function *memcpy_func, *memchr_func; 00330 Function* sqrt_func; 00331 Function *strcpy_func, *strlen_func; 00332 Function *floorf_func, *ceilf_func, *roundf_func; 00333 Function *rintf_func, *nearbyintf_func; 00334 Module *M; ///< Cached Module 00335 TargetData *TD; ///< Cached TargetData 00336 }; 00337 00338 // Register the pass 00339 RegisterOpt<SimplifyLibCalls> 00340 X("simplify-libcalls","Simplify well-known library calls"); 00341 00342 } // anonymous namespace 00343 00344 // The only public symbol in this file which just instantiates the pass object 00345 ModulePass *llvm::createSimplifyLibCallsPass() { 00346 return new SimplifyLibCalls(); 00347 } 00348 00349 // Classes below here, in the anonymous namespace, are all subclasses of the 00350 // LibCallOptimization class, each implementing all optimizations possible for a 00351 // single well-known library call. Each has a static singleton instance that 00352 // auto registers it into the "optlist" global above. 00353 namespace { 00354 00355 // Forward declare utility functions. 00356 bool getConstantStringLength(Value* V, uint64_t& len, ConstantArray** A = 0 ); 00357 Value *CastToCStr(Value *V, Instruction &IP); 00358 00359 /// This LibCallOptimization will find instances of a call to "exit" that occurs 00360 /// within the "main" function and change it to a simple "ret" instruction with 00361 /// the same value passed to the exit function. When this is done, it splits the 00362 /// basic block at the exit(3) call and deletes the call instruction. 00363 /// @brief Replace calls to exit in main with a simple return 00364 struct ExitInMainOptimization : public LibCallOptimization { 00365 ExitInMainOptimization() : LibCallOptimization("exit", 00366 "Number of 'exit' calls simplified") {} 00367 00368 // Make sure the called function looks like exit (int argument, int return 00369 // type, external linkage, not varargs). 00370 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 00371 return F->arg_size() >= 1 && F->arg_begin()->getType()->isInteger(); 00372 } 00373 00374 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 00375 // To be careful, we check that the call to exit is coming from "main", that 00376 // main has external linkage, and the return type of main and the argument 00377 // to exit have the same type. 00378 Function *from = ci->getParent()->getParent(); 00379 if (from->hasExternalLinkage()) 00380 if (from->getReturnType() == ci->getOperand(1)->getType()) 00381 if (from->getName() == "main") { 00382 // Okay, time to actually do the optimization. First, get the basic 00383 // block of the call instruction 00384 BasicBlock* bb = ci->getParent(); 00385 00386 // Create a return instruction that we'll replace the call with. 00387 // Note that the argument of the return is the argument of the call 00388 // instruction. 00389 ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci); 00390 00391 // Split the block at the call instruction which places it in a new 00392 // basic block. 00393 bb->splitBasicBlock(ci); 00394 00395 // The block split caused a branch instruction to be inserted into 00396 // the end of the original block, right after the return instruction 00397 // that we put there. That's not a valid block, so delete the branch 00398 // instruction. 00399 bb->getInstList().pop_back(); 00400 00401 // Now we can finally get rid of the call instruction which now lives 00402 // in the new basic block. 00403 ci->eraseFromParent(); 00404 00405 // Optimization succeeded, return true. 00406 return true; 00407 } 00408 // We didn't pass the criteria for this optimization so return false 00409 return false; 00410 } 00411 } ExitInMainOptimizer; 00412 00413 /// This LibCallOptimization will simplify a call to the strcat library 00414 /// function. The simplification is possible only if the string being 00415 /// concatenated is a constant array or a constant expression that results in 00416 /// a constant string. In this case we can replace it with strlen + llvm.memcpy 00417 /// of the constant string. Both of these calls are further reduced, if possible 00418 /// on subsequent passes. 00419 /// @brief Simplify the strcat library function. 00420 struct StrCatOptimization : public LibCallOptimization { 00421 public: 00422 /// @brief Default constructor 00423 StrCatOptimization() : LibCallOptimization("strcat", 00424 "Number of 'strcat' calls simplified") {} 00425 00426 public: 00427 00428 /// @brief Make sure that the "strcat" function has the right prototype 00429 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 00430 if (f->getReturnType() == PointerType::get(Type::SByteTy)) 00431 if (f->arg_size() == 2) 00432 { 00433 Function::const_arg_iterator AI = f->arg_begin(); 00434 if (AI++->getType() == PointerType::get(Type::SByteTy)) 00435 if (AI->getType() == PointerType::get(Type::SByteTy)) 00436 { 00437 // Indicate this is a suitable call type. 00438 return true; 00439 } 00440 } 00441 return false; 00442 } 00443 00444 /// @brief Optimize the strcat library function 00445 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 00446 // Extract some information from the instruction 00447 Module* M = ci->getParent()->getParent()->getParent(); 00448 Value* dest = ci->getOperand(1); 00449 Value* src = ci->getOperand(2); 00450 00451 // Extract the initializer (while making numerous checks) from the 00452 // source operand of the call to strcat. If we get null back, one of 00453 // a variety of checks in get_GVInitializer failed 00454 uint64_t len = 0; 00455 if (!getConstantStringLength(src,len)) 00456 return false; 00457 00458 // Handle the simple, do-nothing case 00459 if (len == 0) { 00460 ci->replaceAllUsesWith(dest); 00461 ci->eraseFromParent(); 00462 return true; 00463 } 00464 00465 // Increment the length because we actually want to memcpy the null 00466 // terminator as well. 00467 len++; 00468 00469 // We need to find the end of the destination string. That's where the 00470 // memory is to be moved to. We just generate a call to strlen (further 00471 // optimized in another pass). Note that the SLC.get_strlen() call 00472 // caches the Function* for us. 00473 CallInst* strlen_inst = 00474 new CallInst(SLC.get_strlen(), dest, dest->getName()+".len",ci); 00475 00476 // Now that we have the destination's length, we must index into the 00477 // destination's pointer to get the actual memcpy destination (end of 00478 // the string .. we're concatenating). 00479 std::vector<Value*> idx; 00480 idx.push_back(strlen_inst); 00481 GetElementPtrInst* gep = 00482 new GetElementPtrInst(dest,idx,dest->getName()+".indexed",ci); 00483 00484 // We have enough information to now generate the memcpy call to 00485 // do the concatenation for us. 00486 std::vector<Value*> vals; 00487 vals.push_back(gep); // destination 00488 vals.push_back(ci->getOperand(2)); // source 00489 vals.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); // length 00490 vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment 00491 new CallInst(SLC.get_memcpy(), vals, "", ci); 00492 00493 // Finally, substitute the first operand of the strcat call for the 00494 // strcat call itself since strcat returns its first operand; and, 00495 // kill the strcat CallInst. 00496 ci->replaceAllUsesWith(dest); 00497 ci->eraseFromParent(); 00498 return true; 00499 } 00500 } StrCatOptimizer; 00501 00502 /// This LibCallOptimization will simplify a call to the strchr library 00503 /// function. It optimizes out cases where the arguments are both constant 00504 /// and the result can be determined statically. 00505 /// @brief Simplify the strcmp library function. 00506 struct StrChrOptimization : public LibCallOptimization { 00507 public: 00508 StrChrOptimization() : LibCallOptimization("strchr", 00509 "Number of 'strchr' calls simplified") {} 00510 00511 /// @brief Make sure that the "strchr" function has the right prototype 00512 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 00513 if (f->getReturnType() == PointerType::get(Type::SByteTy) && 00514 f->arg_size() == 2) 00515 return true; 00516 return false; 00517 } 00518 00519 /// @brief Perform the strchr optimizations 00520 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 00521 // If there aren't three operands, bail 00522 if (ci->getNumOperands() != 3) 00523 return false; 00524 00525 // Check that the first argument to strchr is a constant array of sbyte. 00526 // If it is, get the length and data, otherwise return false. 00527 uint64_t len = 0; 00528 ConstantArray* CA; 00529 if (!getConstantStringLength(ci->getOperand(1),len,&CA)) 00530 return false; 00531 00532 // Check that the second argument to strchr is a constant int, return false 00533 // if it isn't 00534 ConstantSInt* CSI = dyn_cast<ConstantSInt>(ci->getOperand(2)); 00535 if (!CSI) { 00536 // Just lower this to memchr since we know the length of the string as 00537 // it is constant. 00538 Function* f = SLC.get_memchr(); 00539 std::vector<Value*> args; 00540 args.push_back(ci->getOperand(1)); 00541 args.push_back(ci->getOperand(2)); 00542 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); 00543 ci->replaceAllUsesWith( new CallInst(f,args,ci->getName(),ci)); 00544 ci->eraseFromParent(); 00545 return true; 00546 } 00547 00548 // Get the character we're looking for 00549 int64_t chr = CSI->getValue(); 00550 00551 // Compute the offset 00552 uint64_t offset = 0; 00553 bool char_found = false; 00554 for (uint64_t i = 0; i < len; ++i) { 00555 if (ConstantSInt* CI = dyn_cast<ConstantSInt>(CA->getOperand(i))) { 00556 // Check for the null terminator 00557 if (CI->isNullValue()) 00558 break; // we found end of string 00559 else if (CI->getValue() == chr) { 00560 char_found = true; 00561 offset = i; 00562 break; 00563 } 00564 } 00565 } 00566 00567 // strchr(s,c) -> offset_of_in(c,s) 00568 // (if c is a constant integer and s is a constant string) 00569 if (char_found) { 00570 std::vector<Value*> indices; 00571 indices.push_back(ConstantUInt::get(Type::ULongTy,offset)); 00572 GetElementPtrInst* GEP = new GetElementPtrInst(ci->getOperand(1),indices, 00573 ci->getOperand(1)->getName()+".strchr",ci); 00574 ci->replaceAllUsesWith(GEP); 00575 } else { 00576 ci->replaceAllUsesWith( 00577 ConstantPointerNull::get(PointerType::get(Type::SByteTy))); 00578 } 00579 ci->eraseFromParent(); 00580 return true; 00581 } 00582 } StrChrOptimizer; 00583 00584 /// This LibCallOptimization will simplify a call to the strcmp library 00585 /// function. It optimizes out cases where one or both arguments are constant 00586 /// and the result can be determined statically. 00587 /// @brief Simplify the strcmp library function. 00588 struct StrCmpOptimization : public LibCallOptimization { 00589 public: 00590 StrCmpOptimization() : LibCallOptimization("strcmp", 00591 "Number of 'strcmp' calls simplified") {} 00592 00593 /// @brief Make sure that the "strcmp" function has the right prototype 00594 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 00595 return F->getReturnType() == Type::IntTy && F->arg_size() == 2; 00596 } 00597 00598 /// @brief Perform the strcmp optimization 00599 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 00600 // First, check to see if src and destination are the same. If they are, 00601 // then the optimization is to replace the CallInst with a constant 0 00602 // because the call is a no-op. 00603 Value* s1 = ci->getOperand(1); 00604 Value* s2 = ci->getOperand(2); 00605 if (s1 == s2) { 00606 // strcmp(x,x) -> 0 00607 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0)); 00608 ci->eraseFromParent(); 00609 return true; 00610 } 00611 00612 bool isstr_1 = false; 00613 uint64_t len_1 = 0; 00614 ConstantArray* A1; 00615 if (getConstantStringLength(s1,len_1,&A1)) { 00616 isstr_1 = true; 00617 if (len_1 == 0) { 00618 // strcmp("",x) -> *x 00619 LoadInst* load = 00620 new LoadInst(CastToCStr(s2,*ci), ci->getName()+".load",ci); 00621 CastInst* cast = 00622 new CastInst(load,Type::IntTy,ci->getName()+".int",ci); 00623 ci->replaceAllUsesWith(cast); 00624 ci->eraseFromParent(); 00625 return true; 00626 } 00627 } 00628 00629 bool isstr_2 = false; 00630 uint64_t len_2 = 0; 00631 ConstantArray* A2; 00632 if (getConstantStringLength(s2, len_2, &A2)) { 00633 isstr_2 = true; 00634 if (len_2 == 0) { 00635 // strcmp(x,"") -> *x 00636 LoadInst* load = 00637 new LoadInst(CastToCStr(s1,*ci),ci->getName()+".val",ci); 00638 CastInst* cast = 00639 new CastInst(load,Type::IntTy,ci->getName()+".int",ci); 00640 ci->replaceAllUsesWith(cast); 00641 ci->eraseFromParent(); 00642 return true; 00643 } 00644 } 00645 00646 if (isstr_1 && isstr_2) { 00647 // strcmp(x,y) -> cnst (if both x and y are constant strings) 00648 std::string str1 = A1->getAsString(); 00649 std::string str2 = A2->getAsString(); 00650 int result = strcmp(str1.c_str(), str2.c_str()); 00651 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result)); 00652 ci->eraseFromParent(); 00653 return true; 00654 } 00655 return false; 00656 } 00657 } StrCmpOptimizer; 00658 00659 /// This LibCallOptimization will simplify a call to the strncmp library 00660 /// function. It optimizes out cases where one or both arguments are constant 00661 /// and the result can be determined statically. 00662 /// @brief Simplify the strncmp library function. 00663 struct StrNCmpOptimization : public LibCallOptimization { 00664 public: 00665 StrNCmpOptimization() : LibCallOptimization("strncmp", 00666 "Number of 'strncmp' calls simplified") {} 00667 00668 /// @brief Make sure that the "strncmp" function has the right prototype 00669 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 00670 if (f->getReturnType() == Type::IntTy && f->arg_size() == 3) 00671 return true; 00672 return false; 00673 } 00674 00675 /// @brief Perform the strncpy optimization 00676 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 00677 // First, check to see if src and destination are the same. If they are, 00678 // then the optimization is to replace the CallInst with a constant 0 00679 // because the call is a no-op. 00680 Value* s1 = ci->getOperand(1); 00681 Value* s2 = ci->getOperand(2); 00682 if (s1 == s2) { 00683 // strncmp(x,x,l) -> 0 00684 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0)); 00685 ci->eraseFromParent(); 00686 return true; 00687 } 00688 00689 // Check the length argument, if it is Constant zero then the strings are 00690 // considered equal. 00691 uint64_t len_arg = 0; 00692 bool len_arg_is_const = false; 00693 if (ConstantInt* len_CI = dyn_cast<ConstantInt>(ci->getOperand(3))) { 00694 len_arg_is_const = true; 00695 len_arg = len_CI->getRawValue(); 00696 if (len_arg == 0) { 00697 // strncmp(x,y,0) -> 0 00698 ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0)); 00699 ci->eraseFromParent(); 00700 return true; 00701 } 00702 } 00703 00704 bool isstr_1 = false; 00705 uint64_t len_1 = 0; 00706 ConstantArray* A1; 00707 if (getConstantStringLength(s1, len_1, &A1)) { 00708 isstr_1 = true; 00709 if (len_1 == 0) { 00710 // strncmp("",x) -> *x 00711 LoadInst* load = new LoadInst(s1,ci->getName()+".load",ci); 00712 CastInst* cast = 00713 new CastInst(load,Type::IntTy,ci->getName()+".int",ci); 00714 ci->replaceAllUsesWith(cast); 00715 ci->eraseFromParent(); 00716 return true; 00717 } 00718 } 00719 00720 bool isstr_2 = false; 00721 uint64_t len_2 = 0; 00722 ConstantArray* A2; 00723 if (getConstantStringLength(s2,len_2,&A2)) { 00724 isstr_2 = true; 00725 if (len_2 == 0) { 00726 // strncmp(x,"") -> *x 00727 LoadInst* load = new LoadInst(s2,ci->getName()+".val",ci); 00728 CastInst* cast = 00729 new CastInst(load,Type::IntTy,ci->getName()+".int",ci); 00730 ci->replaceAllUsesWith(cast); 00731 ci->eraseFromParent(); 00732 return true; 00733 } 00734 } 00735 00736 if (isstr_1 && isstr_2 && len_arg_is_const) { 00737 // strncmp(x,y,const) -> constant 00738 std::string str1 = A1->getAsString(); 00739 std::string str2 = A2->getAsString(); 00740 int result = strncmp(str1.c_str(), str2.c_str(), len_arg); 00741 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,result)); 00742 ci->eraseFromParent(); 00743 return true; 00744 } 00745 return false; 00746 } 00747 } StrNCmpOptimizer; 00748 00749 /// This LibCallOptimization will simplify a call to the strcpy library 00750 /// function. Two optimizations are possible: 00751 /// (1) If src and dest are the same and not volatile, just return dest 00752 /// (2) If the src is a constant then we can convert to llvm.memmove 00753 /// @brief Simplify the strcpy library function. 00754 struct StrCpyOptimization : public LibCallOptimization { 00755 public: 00756 StrCpyOptimization() : LibCallOptimization("strcpy", 00757 "Number of 'strcpy' calls simplified") {} 00758 00759 /// @brief Make sure that the "strcpy" function has the right prototype 00760 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 00761 if (f->getReturnType() == PointerType::get(Type::SByteTy)) 00762 if (f->arg_size() == 2) { 00763 Function::const_arg_iterator AI = f->arg_begin(); 00764 if (AI++->getType() == PointerType::get(Type::SByteTy)) 00765 if (AI->getType() == PointerType::get(Type::SByteTy)) { 00766 // Indicate this is a suitable call type. 00767 return true; 00768 } 00769 } 00770 return false; 00771 } 00772 00773 /// @brief Perform the strcpy optimization 00774 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 00775 // First, check to see if src and destination are the same. If they are, 00776 // then the optimization is to replace the CallInst with the destination 00777 // because the call is a no-op. Note that this corresponds to the 00778 // degenerate strcpy(X,X) case which should have "undefined" results 00779 // according to the C specification. However, it occurs sometimes and 00780 // we optimize it as a no-op. 00781 Value* dest = ci->getOperand(1); 00782 Value* src = ci->getOperand(2); 00783 if (dest == src) { 00784 ci->replaceAllUsesWith(dest); 00785 ci->eraseFromParent(); 00786 return true; 00787 } 00788 00789 // Get the length of the constant string referenced by the second operand, 00790 // the "src" parameter. Fail the optimization if we can't get the length 00791 // (note that getConstantStringLength does lots of checks to make sure this 00792 // is valid). 00793 uint64_t len = 0; 00794 if (!getConstantStringLength(ci->getOperand(2),len)) 00795 return false; 00796 00797 // If the constant string's length is zero we can optimize this by just 00798 // doing a store of 0 at the first byte of the destination 00799 if (len == 0) { 00800 new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci); 00801 ci->replaceAllUsesWith(dest); 00802 ci->eraseFromParent(); 00803 return true; 00804 } 00805 00806 // Increment the length because we actually want to memcpy the null 00807 // terminator as well. 00808 len++; 00809 00810 // Extract some information from the instruction 00811 Module* M = ci->getParent()->getParent()->getParent(); 00812 00813 // We have enough information to now generate the memcpy call to 00814 // do the concatenation for us. 00815 std::vector<Value*> vals; 00816 vals.push_back(dest); // destination 00817 vals.push_back(src); // source 00818 vals.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); // length 00819 vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment 00820 new CallInst(SLC.get_memcpy(), vals, "", ci); 00821 00822 // Finally, substitute the first operand of the strcat call for the 00823 // strcat call itself since strcat returns its first operand; and, 00824 // kill the strcat CallInst. 00825 ci->replaceAllUsesWith(dest); 00826 ci->eraseFromParent(); 00827 return true; 00828 } 00829 } StrCpyOptimizer; 00830 00831 /// This LibCallOptimization will simplify a call to the strlen library 00832 /// function by replacing it with a constant value if the string provided to 00833 /// it is a constant array. 00834 /// @brief Simplify the strlen library function. 00835 struct StrLenOptimization : public LibCallOptimization { 00836 StrLenOptimization() : LibCallOptimization("strlen", 00837 "Number of 'strlen' calls simplified") {} 00838 00839 /// @brief Make sure that the "strlen" function has the right prototype 00840 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC) 00841 { 00842 if (f->getReturnType() == SLC.getTargetData()->getIntPtrType()) 00843 if (f->arg_size() == 1) 00844 if (Function::const_arg_iterator AI = f->arg_begin()) 00845 if (AI->getType() == PointerType::get(Type::SByteTy)) 00846 return true; 00847 return false; 00848 } 00849 00850 /// @brief Perform the strlen optimization 00851 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) 00852 { 00853 // Make sure we're dealing with an sbyte* here. 00854 Value* str = ci->getOperand(1); 00855 if (str->getType() != PointerType::get(Type::SByteTy)) 00856 return false; 00857 00858 // Does the call to strlen have exactly one use? 00859 if (ci->hasOneUse()) 00860 // Is that single use a binary operator? 00861 if (BinaryOperator* bop = dyn_cast<BinaryOperator>(ci->use_back())) 00862 // Is it compared against a constant integer? 00863 if (ConstantInt* CI = dyn_cast<ConstantInt>(bop->getOperand(1))) 00864 { 00865 // Get the value the strlen result is compared to 00866 uint64_t val = CI->getRawValue(); 00867 00868 // If its compared against length 0 with == or != 00869 if (val == 0 && 00870 (bop->getOpcode() == Instruction::SetEQ || 00871 bop->getOpcode() == Instruction::SetNE)) 00872 { 00873 // strlen(x) != 0 -> *x != 0 00874 // strlen(x) == 0 -> *x == 0 00875 LoadInst* load = new LoadInst(str,str->getName()+".first",ci); 00876 BinaryOperator* rbop = BinaryOperator::create(bop->getOpcode(), 00877 load, ConstantSInt::get(Type::SByteTy,0), 00878 bop->getName()+".strlen", ci); 00879 bop->replaceAllUsesWith(rbop); 00880 bop->eraseFromParent(); 00881 ci->eraseFromParent(); 00882 return true; 00883 } 00884 } 00885 00886 // Get the length of the constant string operand 00887 uint64_t len = 0; 00888 if (!getConstantStringLength(ci->getOperand(1),len)) 00889 return false; 00890 00891 // strlen("xyz") -> 3 (for example) 00892 const Type *Ty = SLC.getTargetData()->getIntPtrType(); 00893 if (Ty->isSigned()) 00894 ci->replaceAllUsesWith(ConstantSInt::get(Ty, len)); 00895 else 00896 ci->replaceAllUsesWith(ConstantUInt::get(Ty, len)); 00897 00898 ci->eraseFromParent(); 00899 return true; 00900 } 00901 } StrLenOptimizer; 00902 00903 /// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value 00904 /// is equal or not-equal to zero. 00905 static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) { 00906 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00907 UI != E; ++UI) { 00908 Instruction *User = cast<Instruction>(*UI); 00909 if (User->getOpcode() == Instruction::SetNE || 00910 User->getOpcode() == Instruction::SetEQ) { 00911 if (isa<Constant>(User->getOperand(1)) && 00912 cast<Constant>(User->getOperand(1))->isNullValue()) 00913 continue; 00914 } else if (CastInst *CI = dyn_cast<CastInst>(User)) 00915 if (CI->getType() == Type::BoolTy) 00916 continue; 00917 // Unknown instruction. 00918 return false; 00919 } 00920 return true; 00921 } 00922 00923 /// This memcmpOptimization will simplify a call to the memcmp library 00924 /// function. 00925 struct memcmpOptimization : public LibCallOptimization { 00926 /// @brief Default Constructor 00927 memcmpOptimization() 00928 : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {} 00929 00930 /// @brief Make sure that the "memcmp" function has the right prototype 00931 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) { 00932 Function::const_arg_iterator AI = F->arg_begin(); 00933 if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false; 00934 if (!isa<PointerType>((++AI)->getType())) return false; 00935 if (!(++AI)->getType()->isInteger()) return false; 00936 if (!F->getReturnType()->isInteger()) return false; 00937 return true; 00938 } 00939 00940 /// Because of alignment and instruction information that we don't have, we 00941 /// leave the bulk of this to the code generators. 00942 /// 00943 /// Note that we could do much more if we could force alignment on otherwise 00944 /// small aligned allocas, or if we could indicate that loads have a small 00945 /// alignment. 00946 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) { 00947 Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2); 00948 00949 // If the two operands are the same, return zero. 00950 if (LHS == RHS) { 00951 // memcmp(s,s,x) -> 0 00952 CI->replaceAllUsesWith(Constant::getNullValue(CI->getType())); 00953 CI->eraseFromParent(); 00954 return true; 00955 } 00956 00957 // Make sure we have a constant length. 00958 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3)); 00959 if (!LenC) return false; 00960 uint64_t Len = LenC->getRawValue(); 00961 00962 // If the length is zero, this returns 0. 00963 switch (Len) { 00964 case 0: 00965 // memcmp(s1,s2,0) -> 0 00966 CI->replaceAllUsesWith(Constant::getNullValue(CI->getType())); 00967 CI->eraseFromParent(); 00968 return true; 00969 case 1: { 00970 // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2 00971 const Type *UCharPtr = PointerType::get(Type::UByteTy); 00972 CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI); 00973 CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI); 00974 Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI); 00975 Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI); 00976 Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI); 00977 if (RV->getType() != CI->getType()) 00978 RV = new CastInst(RV, CI->getType(), RV->getName(), CI); 00979 CI->replaceAllUsesWith(RV); 00980 CI->eraseFromParent(); 00981 return true; 00982 } 00983 case 2: 00984 if (IsOnlyUsedInEqualsZeroComparison(CI)) { 00985 // TODO: IF both are aligned, use a short load/compare. 00986 00987 // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters 00988 const Type *UCharPtr = PointerType::get(Type::UByteTy); 00989 CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI); 00990 CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI); 00991 Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI); 00992 Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI); 00993 Value *D1 = BinaryOperator::createSub(S1V1, S2V1, 00994 CI->getName()+".d1", CI); 00995 Constant *One = ConstantInt::get(Type::IntTy, 1); 00996 Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI); 00997 Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI); 00998 Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI); 00999 Value *S2V2 = new LoadInst(G1, RHS->getName()+".val2", CI); 01000 Value *D2 = BinaryOperator::createSub(S1V2, S2V2, 01001 CI->getName()+".d1", CI); 01002 Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI); 01003 if (Or->getType() != CI->getType()) 01004 Or = new CastInst(Or, CI->getType(), Or->getName(), CI); 01005 CI->replaceAllUsesWith(Or); 01006 CI->eraseFromParent(); 01007 return true; 01008 } 01009 break; 01010 default: 01011 break; 01012 } 01013 01014 return false; 01015 } 01016 } memcmpOptimizer; 01017 01018 01019 /// This LibCallOptimization will simplify a call to the memcpy library 01020 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8 01021 /// bytes depending on the length of the string and the alignment. Additional 01022 /// optimizations are possible in code generation (sequence of immediate store) 01023 /// @brief Simplify the memcpy library function. 01024 struct LLVMMemCpyMoveOptzn : public LibCallOptimization { 01025 LLVMMemCpyMoveOptzn(const char* fname, const char* desc) 01026 : LibCallOptimization(fname, desc) {} 01027 01028 /// @brief Make sure that the "memcpy" function has the right prototype 01029 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD) { 01030 // Just make sure this has 4 arguments per LLVM spec. 01031 return (f->arg_size() == 4); 01032 } 01033 01034 /// Because of alignment and instruction information that we don't have, we 01035 /// leave the bulk of this to the code generators. The optimization here just 01036 /// deals with a few degenerate cases where the length of the string and the 01037 /// alignment match the sizes of our intrinsic types so we can do a load and 01038 /// store instead of the memcpy call. 01039 /// @brief Perform the memcpy optimization. 01040 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& TD) { 01041 // Make sure we have constant int values to work with 01042 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3)); 01043 if (!LEN) 01044 return false; 01045 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4)); 01046 if (!ALIGN) 01047 return false; 01048 01049 // If the length is larger than the alignment, we can't optimize 01050 uint64_t len = LEN->getRawValue(); 01051 uint64_t alignment = ALIGN->getRawValue(); 01052 if (alignment == 0) 01053 alignment = 1; // Alignment 0 is identity for alignment 1 01054 if (len > alignment) 01055 return false; 01056 01057 // Get the type we will cast to, based on size of the string 01058 Value* dest = ci->getOperand(1); 01059 Value* src = ci->getOperand(2); 01060 Type* castType = 0; 01061 switch (len) 01062 { 01063 case 0: 01064 // memcpy(d,s,0,a) -> noop 01065 ci->eraseFromParent(); 01066 return true; 01067 case 1: castType = Type::SByteTy; break; 01068 case 2: castType = Type::ShortTy; break; 01069 case 4: castType = Type::IntTy; break; 01070 case 8: castType = Type::LongTy; break; 01071 default: 01072 return false; 01073 } 01074 01075 // Cast source and dest to the right sized primitive and then load/store 01076 CastInst* SrcCast = 01077 new CastInst(src,PointerType::get(castType),src->getName()+".cast",ci); 01078 CastInst* DestCast = 01079 new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci); 01080 LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci); 01081 StoreInst* SI = new StoreInst(LI, DestCast, ci); 01082 ci->eraseFromParent(); 01083 return true; 01084 } 01085 }; 01086 01087 /// This LibCallOptimization will simplify a call to the memcpy/memmove library 01088 /// functions. 01089 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer32("llvm.memcpy.i32", 01090 "Number of 'llvm.memcpy' calls simplified"); 01091 LLVMMemCpyMoveOptzn LLVMMemCpyOptimizer64("llvm.memcpy.i64", 01092 "Number of 'llvm.memcpy' calls simplified"); 01093 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer32("llvm.memmove.i32", 01094 "Number of 'llvm.memmove' calls simplified"); 01095 LLVMMemCpyMoveOptzn LLVMMemMoveOptimizer64("llvm.memmove.i64", 01096 "Number of 'llvm.memmove' calls simplified"); 01097 01098 /// This LibCallOptimization will simplify a call to the memset library 01099 /// function by expanding it out to a single store of size 0, 1, 2, 4, or 8 01100 /// bytes depending on the length argument. 01101 struct LLVMMemSetOptimization : public LibCallOptimization { 01102 /// @brief Default Constructor 01103 LLVMMemSetOptimization(const char *Name) : LibCallOptimization(Name, 01104 "Number of 'llvm.memset' calls simplified") {} 01105 01106 /// @brief Make sure that the "memset" function has the right prototype 01107 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) { 01108 // Just make sure this has 3 arguments per LLVM spec. 01109 return F->arg_size() == 4; 01110 } 01111 01112 /// Because of alignment and instruction information that we don't have, we 01113 /// leave the bulk of this to the code generators. The optimization here just 01114 /// deals with a few degenerate cases where the length parameter is constant 01115 /// and the alignment matches the sizes of our intrinsic types so we can do 01116 /// store instead of the memcpy call. Other calls are transformed into the 01117 /// llvm.memset intrinsic. 01118 /// @brief Perform the memset optimization. 01119 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &TD) { 01120 // Make sure we have constant int values to work with 01121 ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3)); 01122 if (!LEN) 01123 return false; 01124 ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4)); 01125 if (!ALIGN) 01126 return false; 01127 01128 // Extract the length and alignment 01129 uint64_t len = LEN->getRawValue(); 01130 uint64_t alignment = ALIGN->getRawValue(); 01131 01132 // Alignment 0 is identity for alignment 1 01133 if (alignment == 0) 01134 alignment = 1; 01135 01136 // If the length is zero, this is a no-op 01137 if (len == 0) { 01138 // memset(d,c,0,a) -> noop 01139 ci->eraseFromParent(); 01140 return true; 01141 } 01142 01143 // If the length is larger than the alignment, we can't optimize 01144 if (len > alignment) 01145 return false; 01146 01147 // Make sure we have a constant ubyte to work with so we can extract 01148 // the value to be filled. 01149 ConstantUInt* FILL = dyn_cast<ConstantUInt>(ci->getOperand(2)); 01150 if (!FILL) 01151 return false; 01152 if (FILL->getType() != Type::UByteTy) 01153 return false; 01154 01155 // memset(s,c,n) -> store s, c (for n=1,2,4,8) 01156 01157 // Extract the fill character 01158 uint64_t fill_char = FILL->getValue(); 01159 uint64_t fill_value = fill_char; 01160 01161 // Get the type we will cast to, based on size of memory area to fill, and 01162 // and the value we will store there. 01163 Value* dest = ci->getOperand(1); 01164 Type* castType = 0; 01165 switch (len) { 01166 case 1: 01167 castType = Type::UByteTy; 01168 break; 01169 case 2: 01170 castType = Type::UShortTy; 01171 fill_value |= fill_char << 8; 01172 break; 01173 case 4: 01174 castType = Type::UIntTy; 01175 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24; 01176 break; 01177 case 8: 01178 castType = Type::ULongTy; 01179 fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24; 01180 fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48; 01181 fill_value |= fill_char << 56; 01182 break; 01183 default: 01184 return false; 01185 } 01186 01187 // Cast dest to the right sized primitive and then load/store 01188 CastInst* DestCast = 01189 new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci); 01190 new StoreInst(ConstantUInt::get(castType,fill_value),DestCast, ci); 01191 ci->eraseFromParent(); 01192 return true; 01193 } 01194 }; 01195 01196 LLVMMemSetOptimization MemSet32Optimizer("llvm.memset.i32"); 01197 LLVMMemSetOptimization MemSet64Optimizer("llvm.memset.i64"); 01198 01199 01200 /// This LibCallOptimization will simplify calls to the "pow" library 01201 /// function. It looks for cases where the result of pow is well known and 01202 /// substitutes the appropriate value. 01203 /// @brief Simplify the pow library function. 01204 struct PowOptimization : public LibCallOptimization { 01205 public: 01206 /// @brief Default Constructor 01207 PowOptimization() : LibCallOptimization("pow", 01208 "Number of 'pow' calls simplified") {} 01209 01210 /// @brief Make sure that the "pow" function has the right prototype 01211 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 01212 // Just make sure this has 2 arguments 01213 return (f->arg_size() == 2); 01214 } 01215 01216 /// @brief Perform the pow optimization. 01217 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 01218 const Type *Ty = cast<Function>(ci->getOperand(0))->getReturnType(); 01219 Value* base = ci->getOperand(1); 01220 Value* expn = ci->getOperand(2); 01221 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(base)) { 01222 double Op1V = Op1->getValue(); 01223 if (Op1V == 1.0) { 01224 // pow(1.0,x) -> 1.0 01225 ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0)); 01226 ci->eraseFromParent(); 01227 return true; 01228 } 01229 } else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn)) { 01230 double Op2V = Op2->getValue(); 01231 if (Op2V == 0.0) { 01232 // pow(x,0.0) -> 1.0 01233 ci->replaceAllUsesWith(ConstantFP::get(Ty,1.0)); 01234 ci->eraseFromParent(); 01235 return true; 01236 } else if (Op2V == 0.5) { 01237 // pow(x,0.5) -> sqrt(x) 01238 CallInst* sqrt_inst = new CallInst(SLC.get_sqrt(), base, 01239 ci->getName()+".pow",ci); 01240 ci->replaceAllUsesWith(sqrt_inst); 01241 ci->eraseFromParent(); 01242 return true; 01243 } else if (Op2V == 1.0) { 01244 // pow(x,1.0) -> x 01245 ci->replaceAllUsesWith(base); 01246 ci->eraseFromParent(); 01247 return true; 01248 } else if (Op2V == -1.0) { 01249 // pow(x,-1.0) -> 1.0/x 01250 BinaryOperator* div_inst= BinaryOperator::createDiv( 01251 ConstantFP::get(Ty,1.0), base, ci->getName()+".pow", ci); 01252 ci->replaceAllUsesWith(div_inst); 01253 ci->eraseFromParent(); 01254 return true; 01255 } 01256 } 01257 return false; // opt failed 01258 } 01259 } PowOptimizer; 01260 01261 /// This LibCallOptimization will simplify calls to the "fprintf" library 01262 /// function. It looks for cases where the result of fprintf is not used and the 01263 /// operation can be reduced to something simpler. 01264 /// @brief Simplify the pow library function. 01265 struct FPrintFOptimization : public LibCallOptimization { 01266 public: 01267 /// @brief Default Constructor 01268 FPrintFOptimization() : LibCallOptimization("fprintf", 01269 "Number of 'fprintf' calls simplified") {} 01270 01271 /// @brief Make sure that the "fprintf" function has the right prototype 01272 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 01273 // Just make sure this has at least 2 arguments 01274 return (f->arg_size() >= 2); 01275 } 01276 01277 /// @brief Perform the fprintf optimization. 01278 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 01279 // If the call has more than 3 operands, we can't optimize it 01280 if (ci->getNumOperands() > 4 || ci->getNumOperands() <= 2) 01281 return false; 01282 01283 // If the result of the fprintf call is used, none of these optimizations 01284 // can be made. 01285 if (!ci->use_empty()) 01286 return false; 01287 01288 // All the optimizations depend on the length of the second argument and the 01289 // fact that it is a constant string array. Check that now 01290 uint64_t len = 0; 01291 ConstantArray* CA = 0; 01292 if (!getConstantStringLength(ci->getOperand(2), len, &CA)) 01293 return false; 01294 01295 if (ci->getNumOperands() == 3) { 01296 // Make sure there's no % in the constant array 01297 for (unsigned i = 0; i < len; ++i) { 01298 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) { 01299 // Check for the null terminator 01300 if (CI->getRawValue() == '%') 01301 return false; // we found end of string 01302 } else { 01303 return false; 01304 } 01305 } 01306 01307 // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file) 01308 const Type* FILEptr_type = ci->getOperand(1)->getType(); 01309 Function* fwrite_func = SLC.get_fwrite(FILEptr_type); 01310 if (!fwrite_func) 01311 return false; 01312 01313 // Make sure that the fprintf() and fwrite() functions both take the 01314 // same type of char pointer. 01315 if (ci->getOperand(2)->getType() != 01316 fwrite_func->getFunctionType()->getParamType(0)) 01317 return false; 01318 01319 std::vector<Value*> args; 01320 args.push_back(ci->getOperand(2)); 01321 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); 01322 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1)); 01323 args.push_back(ci->getOperand(1)); 01324 new CallInst(fwrite_func,args,ci->getName(),ci); 01325 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len)); 01326 ci->eraseFromParent(); 01327 return true; 01328 } 01329 01330 // The remaining optimizations require the format string to be length 2 01331 // "%s" or "%c". 01332 if (len != 2) 01333 return false; 01334 01335 // The first character has to be a % 01336 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0))) 01337 if (CI->getRawValue() != '%') 01338 return false; 01339 01340 // Get the second character and switch on its value 01341 ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1)); 01342 switch (CI->getRawValue()) { 01343 case 's': 01344 { 01345 uint64_t len = 0; 01346 ConstantArray* CA = 0; 01347 if (!getConstantStringLength(ci->getOperand(3), len, &CA)) 01348 return false; 01349 01350 // fprintf(file,"%s",str) -> fwrite(fmt,strlen(fmt),1,file) 01351 const Type* FILEptr_type = ci->getOperand(1)->getType(); 01352 Function* fwrite_func = SLC.get_fwrite(FILEptr_type); 01353 if (!fwrite_func) 01354 return false; 01355 std::vector<Value*> args; 01356 args.push_back(CastToCStr(ci->getOperand(3), *ci)); 01357 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); 01358 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1)); 01359 args.push_back(ci->getOperand(1)); 01360 new CallInst(fwrite_func,args,ci->getName(),ci); 01361 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len)); 01362 break; 01363 } 01364 case 'c': 01365 { 01366 ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(3)); 01367 if (!CI) 01368 return false; 01369 01370 const Type* FILEptr_type = ci->getOperand(1)->getType(); 01371 Function* fputc_func = SLC.get_fputc(FILEptr_type); 01372 if (!fputc_func) 01373 return false; 01374 CastInst* cast = new CastInst(CI,Type::IntTy,CI->getName()+".int",ci); 01375 new CallInst(fputc_func,cast,ci->getOperand(1),"",ci); 01376 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1)); 01377 break; 01378 } 01379 default: 01380 return false; 01381 } 01382 ci->eraseFromParent(); 01383 return true; 01384 } 01385 } FPrintFOptimizer; 01386 01387 /// This LibCallOptimization will simplify calls to the "sprintf" library 01388 /// function. It looks for cases where the result of sprintf is not used and the 01389 /// operation can be reduced to something simpler. 01390 /// @brief Simplify the pow library function. 01391 struct SPrintFOptimization : public LibCallOptimization { 01392 public: 01393 /// @brief Default Constructor 01394 SPrintFOptimization() : LibCallOptimization("sprintf", 01395 "Number of 'sprintf' calls simplified") {} 01396 01397 /// @brief Make sure that the "fprintf" function has the right prototype 01398 virtual bool ValidateCalledFunction(const Function *f, SimplifyLibCalls &SLC){ 01399 // Just make sure this has at least 2 arguments 01400 return (f->getReturnType() == Type::IntTy && f->arg_size() >= 2); 01401 } 01402 01403 /// @brief Perform the sprintf optimization. 01404 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 01405 // If the call has more than 3 operands, we can't optimize it 01406 if (ci->getNumOperands() > 4 || ci->getNumOperands() < 3) 01407 return false; 01408 01409 // All the optimizations depend on the length of the second argument and the 01410 // fact that it is a constant string array. Check that now 01411 uint64_t len = 0; 01412 ConstantArray* CA = 0; 01413 if (!getConstantStringLength(ci->getOperand(2), len, &CA)) 01414 return false; 01415 01416 if (ci->getNumOperands() == 3) { 01417 if (len == 0) { 01418 // If the length is 0, we just need to store a null byte 01419 new StoreInst(ConstantInt::get(Type::SByteTy,0),ci->getOperand(1),ci); 01420 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0)); 01421 ci->eraseFromParent(); 01422 return true; 01423 } 01424 01425 // Make sure there's no % in the constant array 01426 for (unsigned i = 0; i < len; ++i) { 01427 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(i))) { 01428 // Check for the null terminator 01429 if (CI->getRawValue() == '%') 01430 return false; // we found a %, can't optimize 01431 } else { 01432 return false; // initializer is not constant int, can't optimize 01433 } 01434 } 01435 01436 // Increment length because we want to copy the null byte too 01437 len++; 01438 01439 // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1) 01440 Function* memcpy_func = SLC.get_memcpy(); 01441 if (!memcpy_func) 01442 return false; 01443 std::vector<Value*> args; 01444 args.push_back(ci->getOperand(1)); 01445 args.push_back(ci->getOperand(2)); 01446 args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); 01447 args.push_back(ConstantUInt::get(Type::UIntTy,1)); 01448 new CallInst(memcpy_func,args,"",ci); 01449 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len)); 01450 ci->eraseFromParent(); 01451 return true; 01452 } 01453 01454 // The remaining optimizations require the format string to be length 2 01455 // "%s" or "%c". 01456 if (len != 2) 01457 return false; 01458 01459 // The first character has to be a % 01460 if (ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(0))) 01461 if (CI->getRawValue() != '%') 01462 return false; 01463 01464 // Get the second character and switch on its value 01465 ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1)); 01466 switch (CI->getRawValue()) { 01467 case 's': { 01468 // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1) 01469 Function* strlen_func = SLC.get_strlen(); 01470 Function* memcpy_func = SLC.get_memcpy(); 01471 if (!strlen_func || !memcpy_func) 01472 return false; 01473 01474 Value *Len = new CallInst(strlen_func, CastToCStr(ci->getOperand(3), *ci), 01475 ci->getOperand(3)->getName()+".len", ci); 01476 Value *Len1 = BinaryOperator::createAdd(Len, 01477 ConstantInt::get(Len->getType(), 1), 01478 Len->getName()+"1", ci); 01479 if (Len1->getType() != SLC.getIntPtrType()) 01480 Len1 = new CastInst(Len1, SLC.getIntPtrType(), Len1->getName(), ci); 01481 std::vector<Value*> args; 01482 args.push_back(CastToCStr(ci->getOperand(1), *ci)); 01483 args.push_back(CastToCStr(ci->getOperand(3), *ci)); 01484 args.push_back(Len1); 01485 args.push_back(ConstantUInt::get(Type::UIntTy,1)); 01486 new CallInst(memcpy_func, args, "", ci); 01487 01488 // The strlen result is the unincremented number of bytes in the string. 01489 if (!ci->use_empty()) { 01490 if (Len->getType() != ci->getType()) 01491 Len = new CastInst(Len, ci->getType(), Len->getName(), ci); 01492 ci->replaceAllUsesWith(Len); 01493 } 01494 ci->eraseFromParent(); 01495 return true; 01496 } 01497 case 'c': { 01498 // sprintf(dest,"%c",chr) -> store chr, dest 01499 CastInst* cast = new CastInst(ci->getOperand(3),Type::SByteTy,"char",ci); 01500 new StoreInst(cast, ci->getOperand(1), ci); 01501 GetElementPtrInst* gep = new GetElementPtrInst(ci->getOperand(1), 01502 ConstantUInt::get(Type::UIntTy,1),ci->getOperand(1)->getName()+".end", 01503 ci); 01504 new StoreInst(ConstantInt::get(Type::SByteTy,0),gep,ci); 01505 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1)); 01506 ci->eraseFromParent(); 01507 return true; 01508 } 01509 } 01510 return false; 01511 } 01512 } SPrintFOptimizer; 01513 01514 /// This LibCallOptimization will simplify calls to the "fputs" library 01515 /// function. It looks for cases where the result of fputs is not used and the 01516 /// operation can be reduced to something simpler. 01517 /// @brief Simplify the pow library function. 01518 struct PutsOptimization : public LibCallOptimization { 01519 public: 01520 /// @brief Default Constructor 01521 PutsOptimization() : LibCallOptimization("fputs", 01522 "Number of 'fputs' calls simplified") {} 01523 01524 /// @brief Make sure that the "fputs" function has the right prototype 01525 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 01526 // Just make sure this has 2 arguments 01527 return F->arg_size() == 2; 01528 } 01529 01530 /// @brief Perform the fputs optimization. 01531 virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC) { 01532 // If the result is used, none of these optimizations work 01533 if (!ci->use_empty()) 01534 return false; 01535 01536 // All the optimizations depend on the length of the first argument and the 01537 // fact that it is a constant string array. Check that now 01538 uint64_t len = 0; 01539 if (!getConstantStringLength(ci->getOperand(1), len)) 01540 return false; 01541 01542 switch (len) { 01543 case 0: 01544 // fputs("",F) -> noop 01545 break; 01546 case 1: 01547 { 01548 // fputs(s,F) -> fputc(s[0],F) (if s is constant and strlen(s) == 1) 01549 const Type* FILEptr_type = ci->getOperand(2)->getType(); 01550 Function* fputc_func = SLC.get_fputc(FILEptr_type); 01551 if (!fputc_func) 01552 return false; 01553 LoadInst* loadi = new LoadInst(ci->getOperand(1), 01554 ci->getOperand(1)->getName()+".byte",ci); 01555 CastInst* casti = new CastInst(loadi,Type::IntTy, 01556 loadi->getName()+".int",ci); 01557 new CallInst(fputc_func,casti,ci->getOperand(2),"",ci); 01558 break; 01559 } 01560 default: 01561 { 01562 // fputs(s,F) -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1) 01563 const Type* FILEptr_type = ci->getOperand(2)->getType(); 01564 Function* fwrite_func = SLC.get_fwrite(FILEptr_type); 01565 if (!fwrite_func) 01566 return false; 01567 std::vector<Value*> parms; 01568 parms.push_back(ci->getOperand(1)); 01569 parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),len)); 01570 parms.push_back(ConstantUInt::get(SLC.getIntPtrType(),1)); 01571 parms.push_back(ci->getOperand(2)); 01572 new CallInst(fwrite_func,parms,"",ci); 01573 break; 01574 } 01575 } 01576 ci->eraseFromParent(); 01577 return true; // success 01578 } 01579 } PutsOptimizer; 01580 01581 /// This LibCallOptimization will simplify calls to the "isdigit" library 01582 /// function. It simply does range checks the parameter explicitly. 01583 /// @brief Simplify the isdigit library function. 01584 struct isdigitOptimization : public LibCallOptimization { 01585 public: 01586 isdigitOptimization() : LibCallOptimization("isdigit", 01587 "Number of 'isdigit' calls simplified") {} 01588 01589 /// @brief Make sure that the "isdigit" function has the right prototype 01590 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 01591 // Just make sure this has 1 argument 01592 return (f->arg_size() == 1); 01593 } 01594 01595 /// @brief Perform the toascii optimization. 01596 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 01597 if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1))) { 01598 // isdigit(c) -> 0 or 1, if 'c' is constant 01599 uint64_t val = CI->getRawValue(); 01600 if (val >= '0' && val <='9') 01601 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1)); 01602 else 01603 ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0)); 01604 ci->eraseFromParent(); 01605 return true; 01606 } 01607 01608 // isdigit(c) -> (unsigned)c - '0' <= 9 01609 CastInst* cast = 01610 new CastInst(ci->getOperand(1),Type::UIntTy, 01611 ci->getOperand(1)->getName()+".uint",ci); 01612 BinaryOperator* sub_inst = BinaryOperator::createSub(cast, 01613 ConstantUInt::get(Type::UIntTy,0x30), 01614 ci->getOperand(1)->getName()+".sub",ci); 01615 SetCondInst* setcond_inst = new SetCondInst(Instruction::SetLE,sub_inst, 01616 ConstantUInt::get(Type::UIntTy,9), 01617 ci->getOperand(1)->getName()+".cmp",ci); 01618 CastInst* c2 = 01619 new CastInst(setcond_inst,Type::IntTy, 01620 ci->getOperand(1)->getName()+".isdigit",ci); 01621 ci->replaceAllUsesWith(c2); 01622 ci->eraseFromParent(); 01623 return true; 01624 } 01625 } isdigitOptimizer; 01626 01627 struct isasciiOptimization : public LibCallOptimization { 01628 public: 01629 isasciiOptimization() 01630 : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {} 01631 01632 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 01633 return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() && 01634 F->getReturnType()->isInteger(); 01635 } 01636 01637 /// @brief Perform the isascii optimization. 01638 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01639 // isascii(c) -> (unsigned)c < 128 01640 Value *V = CI->getOperand(1); 01641 if (V->getType()->isSigned()) 01642 V = new CastInst(V, V->getType()->getUnsignedVersion(), V->getName(), CI); 01643 Value *Cmp = BinaryOperator::createSetLT(V, ConstantUInt::get(V->getType(), 01644 128), 01645 V->getName()+".isascii", CI); 01646 if (Cmp->getType() != CI->getType()) 01647 Cmp = new CastInst(Cmp, CI->getType(), Cmp->getName(), CI); 01648 CI->replaceAllUsesWith(Cmp); 01649 CI->eraseFromParent(); 01650 return true; 01651 } 01652 } isasciiOptimizer; 01653 01654 01655 /// This LibCallOptimization will simplify calls to the "toascii" library 01656 /// function. It simply does the corresponding and operation to restrict the 01657 /// range of values to the ASCII character set (0-127). 01658 /// @brief Simplify the toascii library function. 01659 struct ToAsciiOptimization : public LibCallOptimization { 01660 public: 01661 /// @brief Default Constructor 01662 ToAsciiOptimization() : LibCallOptimization("toascii", 01663 "Number of 'toascii' calls simplified") {} 01664 01665 /// @brief Make sure that the "fputs" function has the right prototype 01666 virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC){ 01667 // Just make sure this has 2 arguments 01668 return (f->arg_size() == 1); 01669 } 01670 01671 /// @brief Perform the toascii optimization. 01672 virtual bool OptimizeCall(CallInst *ci, SimplifyLibCalls &SLC) { 01673 // toascii(c) -> (c & 0x7f) 01674 Value* chr = ci->getOperand(1); 01675 BinaryOperator* and_inst = BinaryOperator::createAnd(chr, 01676 ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci); 01677 ci->replaceAllUsesWith(and_inst); 01678 ci->eraseFromParent(); 01679 return true; 01680 } 01681 } ToAsciiOptimizer; 01682 01683 /// This LibCallOptimization will simplify calls to the "ffs" library 01684 /// calls which find the first set bit in an int, long, or long long. The 01685 /// optimization is to compute the result at compile time if the argument is 01686 /// a constant. 01687 /// @brief Simplify the ffs library function. 01688 struct FFSOptimization : public LibCallOptimization { 01689 protected: 01690 /// @brief Subclass Constructor 01691 FFSOptimization(const char* funcName, const char* description) 01692 : LibCallOptimization(funcName, description) {} 01693 01694 public: 01695 /// @brief Default Constructor 01696 FFSOptimization() : LibCallOptimization("ffs", 01697 "Number of 'ffs' calls simplified") {} 01698 01699 /// @brief Make sure that the "ffs" function has the right prototype 01700 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 01701 // Just make sure this has 2 arguments 01702 return F->arg_size() == 1 && F->getReturnType() == Type::IntTy; 01703 } 01704 01705 /// @brief Perform the ffs optimization. 01706 virtual bool OptimizeCall(CallInst *TheCall, SimplifyLibCalls &SLC) { 01707 if (ConstantInt *CI = dyn_cast<ConstantInt>(TheCall->getOperand(1))) { 01708 // ffs(cnst) -> bit# 01709 // ffsl(cnst) -> bit# 01710 // ffsll(cnst) -> bit# 01711 uint64_t val = CI->getRawValue(); 01712 int result = 0; 01713 if (val) { 01714 ++result; 01715 while ((val & 1) == 0) { 01716 ++result; 01717 val >>= 1; 01718 } 01719 } 01720 TheCall->replaceAllUsesWith(ConstantSInt::get(Type::IntTy, result)); 01721 TheCall->eraseFromParent(); 01722 return true; 01723 } 01724 01725 // ffs(x) -> x == 0 ? 0 : llvm.cttz(x)+1 01726 // ffsl(x) -> x == 0 ? 0 : llvm.cttz(x)+1 01727 // ffsll(x) -> x == 0 ? 0 : llvm.cttz(x)+1 01728 const Type *ArgType = TheCall->getOperand(1)->getType(); 01729 ArgType = ArgType->getUnsignedVersion(); 01730 const char *CTTZName; 01731 switch (ArgType->getTypeID()) { 01732 default: assert(0 && "Unknown unsigned type!"); 01733 case Type::UByteTyID : CTTZName = "llvm.cttz.i8" ; break; 01734 case Type::UShortTyID: CTTZName = "llvm.cttz.i16"; break; 01735 case Type::UIntTyID : CTTZName = "llvm.cttz.i32"; break; 01736 case Type::ULongTyID : CTTZName = "llvm.cttz.i64"; break; 01737 } 01738 01739 Function *F = SLC.getModule()->getOrInsertFunction(CTTZName, ArgType, 01740 ArgType, NULL); 01741 Value *V = new CastInst(TheCall->getOperand(1), ArgType, "tmp", TheCall); 01742 Value *V2 = new CallInst(F, V, "tmp", TheCall); 01743 V2 = new CastInst(V2, Type::IntTy, "tmp", TheCall); 01744 V2 = BinaryOperator::createAdd(V2, ConstantSInt::get(Type::IntTy, 1), 01745 "tmp", TheCall); 01746 Value *Cond = 01747 BinaryOperator::createSetEQ(V, Constant::getNullValue(V->getType()), 01748 "tmp", TheCall); 01749 V2 = new SelectInst(Cond, ConstantInt::get(Type::IntTy, 0), V2, 01750 TheCall->getName(), TheCall); 01751 TheCall->replaceAllUsesWith(V2); 01752 TheCall->eraseFromParent(); 01753 return true; 01754 } 01755 } FFSOptimizer; 01756 01757 /// This LibCallOptimization will simplify calls to the "ffsl" library 01758 /// calls. It simply uses FFSOptimization for which the transformation is 01759 /// identical. 01760 /// @brief Simplify the ffsl library function. 01761 struct FFSLOptimization : public FFSOptimization { 01762 public: 01763 /// @brief Default Constructor 01764 FFSLOptimization() : FFSOptimization("ffsl", 01765 "Number of 'ffsl' calls simplified") {} 01766 01767 } FFSLOptimizer; 01768 01769 /// This LibCallOptimization will simplify calls to the "ffsll" library 01770 /// calls. It simply uses FFSOptimization for which the transformation is 01771 /// identical. 01772 /// @brief Simplify the ffsl library function. 01773 struct FFSLLOptimization : public FFSOptimization { 01774 public: 01775 /// @brief Default Constructor 01776 FFSLLOptimization() : FFSOptimization("ffsll", 01777 "Number of 'ffsll' calls simplified") {} 01778 01779 } FFSLLOptimizer; 01780 01781 /// This optimizes unary functions that take and return doubles. 01782 struct UnaryDoubleFPOptimizer : public LibCallOptimization { 01783 UnaryDoubleFPOptimizer(const char *Fn, const char *Desc) 01784 : LibCallOptimization(Fn, Desc) {} 01785 01786 // Make sure that this function has the right prototype 01787 virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){ 01788 return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy && 01789 F->getReturnType() == Type::DoubleTy; 01790 } 01791 01792 /// ShrinkFunctionToFloatVersion - If the input to this function is really a 01793 /// float, strength reduce this to a float version of the function, 01794 /// e.g. floor((double)FLT) -> (double)floorf(FLT). This can only be called 01795 /// when the target supports the destination function and where there can be 01796 /// no precision loss. 01797 static bool ShrinkFunctionToFloatVersion(CallInst *CI, SimplifyLibCalls &SLC, 01798 Function *(SimplifyLibCalls::*FP)()){ 01799 if (CastInst *Cast = dyn_cast<CastInst>(CI->getOperand(1))) 01800 if (Cast->getOperand(0)->getType() == Type::FloatTy) { 01801 Value *New = new CallInst((SLC.*FP)(), Cast->getOperand(0), 01802 CI->getName(), CI); 01803 New = new CastInst(New, Type::DoubleTy, CI->getName(), CI); 01804 CI->replaceAllUsesWith(New); 01805 CI->eraseFromParent(); 01806 if (Cast->use_empty()) 01807 Cast->eraseFromParent(); 01808 return true; 01809 } 01810 return false; 01811 } 01812 }; 01813 01814 01815 struct FloorOptimization : public UnaryDoubleFPOptimizer { 01816 FloorOptimization() 01817 : UnaryDoubleFPOptimizer("floor", "Number of 'floor' calls simplified") {} 01818 01819 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01820 #ifdef HAVE_FLOORF 01821 // If this is a float argument passed in, convert to floorf. 01822 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_floorf)) 01823 return true; 01824 #endif 01825 return false; // opt failed 01826 } 01827 } FloorOptimizer; 01828 01829 struct CeilOptimization : public UnaryDoubleFPOptimizer { 01830 CeilOptimization() 01831 : UnaryDoubleFPOptimizer("ceil", "Number of 'ceil' calls simplified") {} 01832 01833 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01834 #ifdef HAVE_CEILF 01835 // If this is a float argument passed in, convert to ceilf. 01836 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_ceilf)) 01837 return true; 01838 #endif 01839 return false; // opt failed 01840 } 01841 } CeilOptimizer; 01842 01843 struct RoundOptimization : public UnaryDoubleFPOptimizer { 01844 RoundOptimization() 01845 : UnaryDoubleFPOptimizer("round", "Number of 'round' calls simplified") {} 01846 01847 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01848 #ifdef HAVE_ROUNDF 01849 // If this is a float argument passed in, convert to roundf. 01850 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_roundf)) 01851 return true; 01852 #endif 01853 return false; // opt failed 01854 } 01855 } RoundOptimizer; 01856 01857 struct RintOptimization : public UnaryDoubleFPOptimizer { 01858 RintOptimization() 01859 : UnaryDoubleFPOptimizer("rint", "Number of 'rint' calls simplified") {} 01860 01861 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01862 #ifdef HAVE_RINTF 01863 // If this is a float argument passed in, convert to rintf. 01864 if (ShrinkFunctionToFloatVersion(CI, SLC, &SimplifyLibCalls::get_rintf)) 01865 return true; 01866 #endif 01867 return false; // opt failed 01868 } 01869 } RintOptimizer; 01870 01871 struct NearByIntOptimization : public UnaryDoubleFPOptimizer { 01872 NearByIntOptimization() 01873 : UnaryDoubleFPOptimizer("nearbyint", 01874 "Number of 'nearbyint' calls simplified") {} 01875 01876 virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) { 01877 #ifdef HAVE_NEARBYINTF 01878 // If this is a float argument passed in, convert to nearbyintf. 01879 if (ShrinkFunctionToFloatVersion(CI, SLC,&SimplifyLibCalls::get_nearbyintf)) 01880 return true; 01881 #endif 01882 return false; // opt failed 01883 } 01884 } NearByIntOptimizer; 01885 01886 /// A function to compute the length of a null-terminated constant array of 01887 /// integers. This function can't rely on the size of the constant array 01888 /// because there could be a null terminator in the middle of the array. 01889 /// We also have to bail out if we find a non-integer constant initializer 01890 /// of one of the elements or if there is no null-terminator. The logic 01891 /// below checks each of these conditions and will return true only if all 01892 /// conditions are met. In that case, the \p len parameter is set to the length 01893 /// of the null-terminated string. If false is returned, the conditions were 01894 /// not met and len is set to 0. 01895 /// @brief Get the length of a constant string (null-terminated array). 01896 bool getConstantStringLength(Value *V, uint64_t &len, ConstantArray **CA) { 01897 assert(V != 0 && "Invalid args to getConstantStringLength"); 01898 len = 0; // make sure we initialize this 01899 User* GEP = 0; 01900 // If the value is not a GEP instruction nor a constant expression with a 01901 // GEP instruction, then return false because ConstantArray can't occur 01902 // any other way 01903 if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V)) 01904 GEP = GEPI; 01905 else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V)) 01906 if (CE->getOpcode() == Instruction::GetElementPtr) 01907 GEP = CE; 01908 else 01909 return false; 01910 else 01911 return false; 01912 01913 // Make sure the GEP has exactly three arguments. 01914 if (GEP->getNumOperands() != 3) 01915 return false; 01916 01917 // Check to make sure that the first operand of the GEP is an integer and 01918 // has value 0 so that we are sure we're indexing into the initializer. 01919 if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1))) { 01920 if (!op1->isNullValue()) 01921 return false; 01922 } else 01923 return false; 01924 01925 // Ensure that the second operand is a ConstantInt. If it isn't then this 01926 // GEP is wonky and we're not really sure what were referencing into and 01927 // better of not optimizing it. While we're at it, get the second index 01928 // value. We'll need this later for indexing the ConstantArray. 01929 uint64_t start_idx = 0; 01930 if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 01931 start_idx = CI->getRawValue(); 01932 else 01933 return false; 01934 01935 // The GEP instruction, constant or instruction, must reference a global 01936 // variable that is a constant and is initialized. The referenced constant 01937 // initializer is the array that we'll use for optimization. 01938 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 01939 if (!GV || !GV->isConstant() || !GV->hasInitializer()) 01940 return false; 01941 01942 // Get the initializer. 01943 Constant* INTLZR = GV->getInitializer(); 01944 01945 // Handle the ConstantAggregateZero case 01946 if (ConstantAggregateZero *CAZ = dyn_cast<ConstantAggregateZero>(INTLZR)) { 01947 // This is a degenerate case. The initializer is constant zero so the 01948 // length of the string must be zero. 01949 len = 0; 01950 return true; 01951 } 01952 01953 // Must be a Constant Array 01954 ConstantArray* A = dyn_cast<ConstantArray>(INTLZR); 01955 if (!A) 01956 return false; 01957 01958 // Get the number of elements in the array 01959 uint64_t max_elems = A->getType()->getNumElements(); 01960 01961 // Traverse the constant array from start_idx (derived above) which is 01962 // the place the GEP refers to in the array. 01963 for (len = start_idx; len < max_elems; len++) { 01964 if (ConstantInt *CI = dyn_cast<ConstantInt>(A->getOperand(len))) { 01965 // Check for the null terminator 01966 if (CI->isNullValue()) 01967 break; // we found end of string 01968 } else 01969 return false; // This array isn't suitable, non-int initializer 01970 } 01971 01972 if (len >= max_elems) 01973 return false; // This array isn't null terminated 01974 01975 // Subtract out the initial value from the length 01976 len -= start_idx; 01977 if (CA) 01978 *CA = A; 01979 return true; // success! 01980 } 01981 01982 /// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*, 01983 /// inserting the cast before IP, and return the cast. 01984 /// @brief Cast a value to a "C" string. 01985 Value *CastToCStr(Value *V, Instruction &IP) { 01986 const Type *SBPTy = PointerType::get(Type::SByteTy); 01987 if (V->getType() != SBPTy) 01988 return new CastInst(V, SBPTy, V->getName(), &IP); 01989 return V; 01990 } 01991 01992 // TODO: 01993 // Additional cases that we need to add to this file: 01994 // 01995 // cbrt: 01996 // * cbrt(expN(X)) -> expN(x/3) 01997 // * cbrt(sqrt(x)) -> pow(x,1/6) 01998 // * cbrt(sqrt(x)) -> pow(x,1/9) 01999 // 02000 // cos, cosf, cosl: 02001 // * cos(-x) -> cos(x) 02002 // 02003 // exp, expf, expl: 02004 // * exp(log(x)) -> x 02005 // 02006 // log, logf, logl: 02007 // * log(exp(x)) -> x 02008 // * log(x**y) -> y*log(x) 02009 // * log(exp(y)) -> y*log(e) 02010 // * log(exp2(y)) -> y*log(2) 02011 // * log(exp10(y)) -> y*log(10) 02012 // * log(sqrt(x)) -> 0.5*log(x) 02013 // * log(pow(x,y)) -> y*log(x) 02014 // 02015 // lround, lroundf, lroundl: 02016 // * lround(cnst) -> cnst' 02017 // 02018 // memcmp: 02019 // * memcmp(x,y,l) -> cnst 02020 // (if all arguments are constant and strlen(x) <= l and strlen(y) <= l) 02021 // 02022 // memmove: 02023 // * memmove(d,s,l,a) -> memcpy(d,s,l,a) 02024 // (if s is a global constant array) 02025 // 02026 // pow, powf, powl: 02027 // * pow(exp(x),y) -> exp(x*y) 02028 // * pow(sqrt(x),y) -> pow(x,y*0.5) 02029 // * pow(pow(x,y),z)-> pow(x,y*z) 02030 // 02031 // puts: 02032 // * puts("") -> fputc("\n",stdout) (how do we get "stdout"?) 02033 // 02034 // round, roundf, roundl: 02035 // * round(cnst) -> cnst' 02036 // 02037 // signbit: 02038 // * signbit(cnst) -> cnst' 02039 // * signbit(nncst) -> 0 (if pstv is a non-negative constant) 02040 // 02041 // sqrt, sqrtf, sqrtl: 02042 // * sqrt(expN(x)) -> expN(x*0.5) 02043 // * sqrt(Nroot(x)) -> pow(x,1/(2*N)) 02044 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5) 02045 // 02046 // stpcpy: 02047 // * stpcpy(str, "literal") -> 02048 // llvm.memcpy(str,"literal",strlen("literal")+1,1) 02049 // strrchr: 02050 // * strrchr(s,c) -> reverse_offset_of_in(c,s) 02051 // (if c is a constant integer and s is a constant string) 02052 // * strrchr(s1,0) -> strchr(s1,0) 02053 // 02054 // strncat: 02055 // * strncat(x,y,0) -> x 02056 // * strncat(x,y,0) -> x (if strlen(y) = 0) 02057 // * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y)) 02058 // 02059 // strncpy: 02060 // * strncpy(d,s,0) -> d 02061 // * strncpy(d,s,l) -> memcpy(d,s,l,1) 02062 // (if s and l are constants) 02063 // 02064 // strpbrk: 02065 // * strpbrk(s,a) -> offset_in_for(s,a) 02066 // (if s and a are both constant strings) 02067 // * strpbrk(s,"") -> 0 02068 // * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1) 02069 // 02070 // strspn, strcspn: 02071 // * strspn(s,a) -> const_int (if both args are constant) 02072 // * strspn("",a) -> 0 02073 // * strspn(s,"") -> 0 02074 // * strcspn(s,a) -> const_int (if both args are constant) 02075 // * strcspn("",a) -> 0 02076 // * strcspn(s,"") -> strlen(a) 02077 // 02078 // strstr: 02079 // * strstr(x,x) -> x 02080 // * strstr(s1,s2) -> offset_of_s2_in(s1) 02081 // (if s1 and s2 are constant strings) 02082 // 02083 // tan, tanf, tanl: 02084 // * tan(atan(x)) -> x 02085 // 02086 // trunc, truncf, truncl: 02087 // * trunc(cnst) -> cnst' 02088 // 02089 // 02090 }