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