LLVM API Documentation
00001 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a simple 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/Transforms/Scalar.h" 00022 #include "llvm/Intrinsics.h" 00023 #include "llvm/LLVMContext.h" 00024 #include "llvm/Module.h" 00025 #include "llvm/Pass.h" 00026 #include "llvm/Support/IRBuilder.h" 00027 #include "llvm/Analysis/ValueTracking.h" 00028 #include "llvm/Target/TargetData.h" 00029 #include "llvm/ADT/SmallPtrSet.h" 00030 #include "llvm/ADT/StringMap.h" 00031 #include "llvm/ADT/Statistic.h" 00032 #include "llvm/ADT/STLExtras.h" 00033 #include "llvm/Support/Compiler.h" 00034 #include "llvm/Support/Debug.h" 00035 #include "llvm/Support/raw_ostream.h" 00036 #include "llvm/Config/config.h" 00037 using namespace llvm; 00038 00039 STATISTIC(NumSimplified, "Number of library calls simplified"); 00040 STATISTIC(NumAnnotated, "Number of attributes added to library functions"); 00041 00042 //===----------------------------------------------------------------------===// 00043 // Optimizer Base Class 00044 //===----------------------------------------------------------------------===// 00045 00046 /// This class is the abstract base class for the set of optimizations that 00047 /// corresponds to one library call. 00048 namespace { 00049 class VISIBILITY_HIDDEN LibCallOptimization { 00050 protected: 00051 Function *Caller; 00052 const TargetData *TD; 00053 LLVMContext* Context; 00054 public: 00055 LibCallOptimization() { } 00056 virtual ~LibCallOptimization() {} 00057 00058 /// CallOptimizer - This pure virtual method is implemented by base classes to 00059 /// do various optimizations. If this returns null then no transformation was 00060 /// performed. If it returns CI, then it transformed the call and CI is to be 00061 /// deleted. If it returns something else, replace CI with the new value and 00062 /// delete CI. 00063 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) 00064 =0; 00065 00066 Value *OptimizeCall(CallInst *CI, const TargetData *TD, IRBuilder<> &B) { 00067 Caller = CI->getParent()->getParent(); 00068 this->TD = TD; 00069 if (CI->getCalledFunction()) 00070 Context = &CI->getCalledFunction()->getContext(); 00071 return CallOptimizer(CI->getCalledFunction(), CI, B); 00072 } 00073 00074 /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*. 00075 Value *CastToCStr(Value *V, IRBuilder<> &B); 00076 00077 /// EmitStrLen - Emit a call to the strlen function to the builder, for the 00078 /// specified pointer. Ptr is required to be some pointer type, and the 00079 /// return value has 'intptr_t' type. 00080 Value *EmitStrLen(Value *Ptr, IRBuilder<> &B); 00081 00082 /// EmitMemCpy - Emit a call to the memcpy function to the builder. This 00083 /// always expects that the size has type 'intptr_t' and Dst/Src are pointers. 00084 Value *EmitMemCpy(Value *Dst, Value *Src, Value *Len, 00085 unsigned Align, IRBuilder<> &B); 00086 00087 /// EmitMemChr - Emit a call to the memchr function. This assumes that Ptr is 00088 /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value. 00089 Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B); 00090 00091 /// EmitMemCmp - Emit a call to the memcmp function. 00092 Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B); 00093 00094 /// EmitMemSet - Emit a call to the memset function 00095 Value *EmitMemSet(Value *Dst, Value *Val, Value *Len, IRBuilder<> &B); 00096 00097 /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g. 00098 /// 'floor'). This function is known to take a single of type matching 'Op' 00099 /// and returns one value with the same type. If 'Op' is a long double, 'l' 00100 /// is added as the suffix of name, if 'Op' is a float, we add a 'f' suffix. 00101 Value *EmitUnaryFloatFnCall(Value *Op, const char *Name, IRBuilder<> &B); 00102 00103 /// EmitPutChar - Emit a call to the putchar function. This assumes that Char 00104 /// is an integer. 00105 void EmitPutChar(Value *Char, IRBuilder<> &B); 00106 00107 /// EmitPutS - Emit a call to the puts function. This assumes that Str is 00108 /// some pointer. 00109 void EmitPutS(Value *Str, IRBuilder<> &B); 00110 00111 /// EmitFPutC - Emit a call to the fputc function. This assumes that Char is 00112 /// an i32, and File is a pointer to FILE. 00113 void EmitFPutC(Value *Char, Value *File, IRBuilder<> &B); 00114 00115 /// EmitFPutS - Emit a call to the puts function. Str is required to be a 00116 /// pointer and File is a pointer to FILE. 00117 void EmitFPutS(Value *Str, Value *File, IRBuilder<> &B); 00118 00119 /// EmitFWrite - Emit a call to the fwrite function. This assumes that Ptr is 00120 /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE. 00121 void EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B); 00122 00123 }; 00124 } // End anonymous namespace. 00125 00126 /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*. 00127 Value *LibCallOptimization::CastToCStr(Value *V, IRBuilder<> &B) { 00128 return 00129 B.CreateBitCast(V, PointerType::getUnqual(Type::getInt8Ty(*Context)), "cstr"); 00130 } 00131 00132 /// EmitStrLen - Emit a call to the strlen function to the builder, for the 00133 /// specified pointer. This always returns an integer value of size intptr_t. 00134 Value *LibCallOptimization::EmitStrLen(Value *Ptr, IRBuilder<> &B) { 00135 Module *M = Caller->getParent(); 00136 AttributeWithIndex AWI[2]; 00137 AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture); 00138 AWI[1] = AttributeWithIndex::get(~0u, Attribute::ReadOnly | 00139 Attribute::NoUnwind); 00140 00141 Constant *StrLen =M->getOrInsertFunction("strlen", AttrListPtr::get(AWI, 2), 00142 TD->getIntPtrType(*Context), 00143 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00144 NULL); 00145 CallInst *CI = B.CreateCall(StrLen, CastToCStr(Ptr, B), "strlen"); 00146 if (const Function *F = dyn_cast<Function>(StrLen->stripPointerCasts())) 00147 CI->setCallingConv(F->getCallingConv()); 00148 00149 return CI; 00150 } 00151 00152 /// EmitMemCpy - Emit a call to the memcpy function to the builder. This always 00153 /// expects that the size has type 'intptr_t' and Dst/Src are pointers. 00154 Value *LibCallOptimization::EmitMemCpy(Value *Dst, Value *Src, Value *Len, 00155 unsigned Align, IRBuilder<> &B) { 00156 Module *M = Caller->getParent(); 00157 Intrinsic::ID IID = Intrinsic::memcpy; 00158 const Type *Tys[1]; 00159 Tys[0] = Len->getType(); 00160 Value *MemCpy = Intrinsic::getDeclaration(M, IID, Tys, 1); 00161 return B.CreateCall4(MemCpy, CastToCStr(Dst, B), CastToCStr(Src, B), Len, 00162 ConstantInt::get(Type::getInt32Ty(*Context), Align)); 00163 } 00164 00165 /// EmitMemChr - Emit a call to the memchr function. This assumes that Ptr is 00166 /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value. 00167 Value *LibCallOptimization::EmitMemChr(Value *Ptr, Value *Val, 00168 Value *Len, IRBuilder<> &B) { 00169 Module *M = Caller->getParent(); 00170 AttributeWithIndex AWI; 00171 AWI = AttributeWithIndex::get(~0u, Attribute::ReadOnly | Attribute::NoUnwind); 00172 00173 Value *MemChr = M->getOrInsertFunction("memchr", AttrListPtr::get(&AWI, 1), 00174 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00175 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00176 Type::getInt32Ty(*Context), TD->getIntPtrType(*Context), 00177 NULL); 00178 CallInst *CI = B.CreateCall3(MemChr, CastToCStr(Ptr, B), Val, Len, "memchr"); 00179 00180 if (const Function *F = dyn_cast<Function>(MemChr->stripPointerCasts())) 00181 CI->setCallingConv(F->getCallingConv()); 00182 00183 return CI; 00184 } 00185 00186 /// EmitMemCmp - Emit a call to the memcmp function. 00187 Value *LibCallOptimization::EmitMemCmp(Value *Ptr1, Value *Ptr2, 00188 Value *Len, IRBuilder<> &B) { 00189 Module *M = Caller->getParent(); 00190 AttributeWithIndex AWI[3]; 00191 AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture); 00192 AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture); 00193 AWI[2] = AttributeWithIndex::get(~0u, Attribute::ReadOnly | 00194 Attribute::NoUnwind); 00195 00196 Value *MemCmp = M->getOrInsertFunction("memcmp", AttrListPtr::get(AWI, 3), 00197 Type::getInt32Ty(*Context), 00198 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00199 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00200 TD->getIntPtrType(*Context), NULL); 00201 CallInst *CI = B.CreateCall3(MemCmp, CastToCStr(Ptr1, B), CastToCStr(Ptr2, B), 00202 Len, "memcmp"); 00203 00204 if (const Function *F = dyn_cast<Function>(MemCmp->stripPointerCasts())) 00205 CI->setCallingConv(F->getCallingConv()); 00206 00207 return CI; 00208 } 00209 00210 /// EmitMemSet - Emit a call to the memset function 00211 Value *LibCallOptimization::EmitMemSet(Value *Dst, Value *Val, 00212 Value *Len, IRBuilder<> &B) { 00213 Module *M = Caller->getParent(); 00214 Intrinsic::ID IID = Intrinsic::memset; 00215 const Type *Tys[1]; 00216 Tys[0] = Len->getType(); 00217 Value *MemSet = Intrinsic::getDeclaration(M, IID, Tys, 1); 00218 Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1); 00219 return B.CreateCall4(MemSet, CastToCStr(Dst, B), Val, Len, Align); 00220 } 00221 00222 /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g. 00223 /// 'floor'). This function is known to take a single of type matching 'Op' and 00224 /// returns one value with the same type. If 'Op' is a long double, 'l' is 00225 /// added as the suffix of name, if 'Op' is a float, we add a 'f' suffix. 00226 Value *LibCallOptimization::EmitUnaryFloatFnCall(Value *Op, const char *Name, 00227 IRBuilder<> &B) { 00228 char NameBuffer[20]; 00229 if (Op->getType() != Type::getDoubleTy(*Context)) { 00230 // If we need to add a suffix, copy into NameBuffer. 00231 unsigned NameLen = strlen(Name); 00232 assert(NameLen < sizeof(NameBuffer)-2); 00233 memcpy(NameBuffer, Name, NameLen); 00234 if (Op->getType() == Type::getFloatTy(*Context)) 00235 NameBuffer[NameLen] = 'f'; // floorf 00236 else 00237 NameBuffer[NameLen] = 'l'; // floorl 00238 NameBuffer[NameLen+1] = 0; 00239 Name = NameBuffer; 00240 } 00241 00242 Module *M = Caller->getParent(); 00243 Value *Callee = M->getOrInsertFunction(Name, Op->getType(), 00244 Op->getType(), NULL); 00245 CallInst *CI = B.CreateCall(Callee, Op, Name); 00246 00247 if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts())) 00248 CI->setCallingConv(F->getCallingConv()); 00249 00250 return CI; 00251 } 00252 00253 /// EmitPutChar - Emit a call to the putchar function. This assumes that Char 00254 /// is an integer. 00255 void LibCallOptimization::EmitPutChar(Value *Char, IRBuilder<> &B) { 00256 Module *M = Caller->getParent(); 00257 Value *PutChar = M->getOrInsertFunction("putchar", Type::getInt32Ty(*Context), 00258 Type::getInt32Ty(*Context), NULL); 00259 CallInst *CI = B.CreateCall(PutChar, 00260 B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari"), 00261 "putchar"); 00262 00263 if (const Function *F = dyn_cast<Function>(PutChar->stripPointerCasts())) 00264 CI->setCallingConv(F->getCallingConv()); 00265 } 00266 00267 /// EmitPutS - Emit a call to the puts function. This assumes that Str is 00268 /// some pointer. 00269 void LibCallOptimization::EmitPutS(Value *Str, IRBuilder<> &B) { 00270 Module *M = Caller->getParent(); 00271 AttributeWithIndex AWI[2]; 00272 AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture); 00273 AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); 00274 00275 Value *PutS = M->getOrInsertFunction("puts", AttrListPtr::get(AWI, 2), 00276 Type::getInt32Ty(*Context), 00277 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00278 NULL); 00279 CallInst *CI = B.CreateCall(PutS, CastToCStr(Str, B), "puts"); 00280 if (const Function *F = dyn_cast<Function>(PutS->stripPointerCasts())) 00281 CI->setCallingConv(F->getCallingConv()); 00282 00283 } 00284 00285 /// EmitFPutC - Emit a call to the fputc function. This assumes that Char is 00286 /// an integer and File is a pointer to FILE. 00287 void LibCallOptimization::EmitFPutC(Value *Char, Value *File, IRBuilder<> &B) { 00288 Module *M = Caller->getParent(); 00289 AttributeWithIndex AWI[2]; 00290 AWI[0] = AttributeWithIndex::get(2, Attribute::NoCapture); 00291 AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); 00292 Constant *F; 00293 if (isa<PointerType>(File->getType())) 00294 F = M->getOrInsertFunction("fputc", AttrListPtr::get(AWI, 2), Type::getInt32Ty(*Context), 00295 Type::getInt32Ty(*Context), File->getType(), NULL); 00296 else 00297 F = M->getOrInsertFunction("fputc", Type::getInt32Ty(*Context), Type::getInt32Ty(*Context), 00298 File->getType(), NULL); 00299 Char = B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari"); 00300 CallInst *CI = B.CreateCall2(F, Char, File, "fputc"); 00301 00302 if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts())) 00303 CI->setCallingConv(Fn->getCallingConv()); 00304 } 00305 00306 /// EmitFPutS - Emit a call to the puts function. Str is required to be a 00307 /// pointer and File is a pointer to FILE. 00308 void LibCallOptimization::EmitFPutS(Value *Str, Value *File, IRBuilder<> &B) { 00309 Module *M = Caller->getParent(); 00310 AttributeWithIndex AWI[3]; 00311 AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture); 00312 AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture); 00313 AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); 00314 Constant *F; 00315 if (isa<PointerType>(File->getType())) 00316 F = M->getOrInsertFunction("fputs", AttrListPtr::get(AWI, 3), Type::getInt32Ty(*Context), 00317 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00318 File->getType(), NULL); 00319 else 00320 F = M->getOrInsertFunction("fputs", Type::getInt32Ty(*Context), 00321 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00322 File->getType(), NULL); 00323 CallInst *CI = B.CreateCall2(F, CastToCStr(Str, B), File, "fputs"); 00324 00325 if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts())) 00326 CI->setCallingConv(Fn->getCallingConv()); 00327 } 00328 00329 /// EmitFWrite - Emit a call to the fwrite function. This assumes that Ptr is 00330 /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE. 00331 void LibCallOptimization::EmitFWrite(Value *Ptr, Value *Size, Value *File, 00332 IRBuilder<> &B) { 00333 Module *M = Caller->getParent(); 00334 AttributeWithIndex AWI[3]; 00335 AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture); 00336 AWI[1] = AttributeWithIndex::get(4, Attribute::NoCapture); 00337 AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); 00338 Constant *F; 00339 if (isa<PointerType>(File->getType())) 00340 F = M->getOrInsertFunction("fwrite", AttrListPtr::get(AWI, 3), 00341 TD->getIntPtrType(*Context), 00342 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00343 TD->getIntPtrType(*Context), TD->getIntPtrType(*Context), 00344 File->getType(), NULL); 00345 else 00346 F = M->getOrInsertFunction("fwrite", TD->getIntPtrType(*Context), 00347 PointerType::getUnqual(Type::getInt8Ty(*Context)), 00348 TD->getIntPtrType(*Context), TD->getIntPtrType(*Context), 00349 File->getType(), NULL); 00350 CallInst *CI = B.CreateCall4(F, CastToCStr(Ptr, B), Size, 00351 ConstantInt::get(TD->getIntPtrType(*Context), 1), File); 00352 00353 if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts())) 00354 CI->setCallingConv(Fn->getCallingConv()); 00355 } 00356 00357 //===----------------------------------------------------------------------===// 00358 // Helper Functions 00359 //===----------------------------------------------------------------------===// 00360 00361 /// GetStringLengthH - If we can compute the length of the string pointed to by 00362 /// the specified pointer, return 'len+1'. If we can't, return 0. 00363 static uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 00364 // Look through noop bitcast instructions. 00365 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 00366 return GetStringLengthH(BCI->getOperand(0), PHIs); 00367 00368 // If this is a PHI node, there are two cases: either we have already seen it 00369 // or we haven't. 00370 if (PHINode *PN = dyn_cast<PHINode>(V)) { 00371 if (!PHIs.insert(PN)) 00372 return ~0ULL; // already in the set. 00373 00374 // If it was new, see if all the input strings are the same length. 00375 uint64_t LenSoFar = ~0ULL; 00376 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 00377 uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 00378 if (Len == 0) return 0; // Unknown length -> unknown. 00379 00380 if (Len == ~0ULL) continue; 00381 00382 if (Len != LenSoFar && LenSoFar != ~0ULL) 00383 return 0; // Disagree -> unknown. 00384 LenSoFar = Len; 00385 } 00386 00387 // Success, all agree. 00388 return LenSoFar; 00389 } 00390 00391 // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 00392 if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 00393 uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 00394 if (Len1 == 0) return 0; 00395 uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 00396 if (Len2 == 0) return 0; 00397 if (Len1 == ~0ULL) return Len2; 00398 if (Len2 == ~0ULL) return Len1; 00399 if (Len1 != Len2) return 0; 00400 return Len1; 00401 } 00402 00403 // If the value is not a GEP instruction nor a constant expression with a 00404 // GEP instruction, then return unknown. 00405 User *GEP = 0; 00406 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 00407 GEP = GEPI; 00408 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 00409 if (CE->getOpcode() != Instruction::GetElementPtr) 00410 return 0; 00411 GEP = CE; 00412 } else { 00413 return 0; 00414 } 00415 00416 // Make sure the GEP has exactly three arguments. 00417 if (GEP->getNumOperands() != 3) 00418 return 0; 00419 00420 // Check to make sure that the first operand of the GEP is an integer and 00421 // has value 0 so that we are sure we're indexing into the initializer. 00422 if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) { 00423 if (!Idx->isZero()) 00424 return 0; 00425 } else 00426 return 0; 00427 00428 // If the second index isn't a ConstantInt, then this is a variable index 00429 // into the array. If this occurs, we can't say anything meaningful about 00430 // the string. 00431 uint64_t StartIdx = 0; 00432 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 00433 StartIdx = CI->getZExtValue(); 00434 else 00435 return 0; 00436 00437 // The GEP instruction, constant or instruction, must reference a global 00438 // variable that is a constant and is initialized. The referenced constant 00439 // initializer is the array that we'll use for optimization. 00440 GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 00441 if (!GV || !GV->isConstant() || !GV->hasInitializer() || 00442 GV->mayBeOverridden()) 00443 return 0; 00444 Constant *GlobalInit = GV->getInitializer(); 00445 00446 // Handle the ConstantAggregateZero case, which is a degenerate case. The 00447 // initializer is constant zero so the length of the string must be zero. 00448 if (isa<ConstantAggregateZero>(GlobalInit)) 00449 return 1; // Len = 0 offset by 1. 00450 00451 // Must be a Constant Array 00452 ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 00453 if (!Array || 00454 Array->getType()->getElementType() != Type::getInt8Ty(V->getContext())) 00455 return false; 00456 00457 // Get the number of elements in the array 00458 uint64_t NumElts = Array->getType()->getNumElements(); 00459 00460 // Traverse the constant array from StartIdx (derived above) which is 00461 // the place the GEP refers to in the array. 00462 for (unsigned i = StartIdx; i != NumElts; ++i) { 00463 Constant *Elt = Array->getOperand(i); 00464 ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 00465 if (!CI) // This array isn't suitable, non-int initializer. 00466 return 0; 00467 if (CI->isZero()) 00468 return i-StartIdx+1; // We found end of string, success! 00469 } 00470 00471 return 0; // The array isn't null terminated, conservatively return 'unknown'. 00472 } 00473 00474 /// GetStringLength - If we can compute the length of the string pointed to by 00475 /// the specified pointer, return 'len+1'. If we can't, return 0. 00476 static uint64_t GetStringLength(Value *V) { 00477 if (!isa<PointerType>(V->getType())) return 0; 00478 00479 SmallPtrSet<PHINode*, 32> PHIs; 00480 uint64_t Len = GetStringLengthH(V, PHIs); 00481 // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 00482 // an empty string as a length. 00483 return Len == ~0ULL ? 1 : Len; 00484 } 00485 00486 /// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the 00487 /// value is equal or not-equal to zero. 00488 static bool IsOnlyUsedInZeroEqualityComparison(Value *V) { 00489 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); 00490 UI != E; ++UI) { 00491 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI)) 00492 if (IC->isEquality()) 00493 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1))) 00494 if (C->isNullValue()) 00495 continue; 00496 // Unknown instruction. 00497 return false; 00498 } 00499 return true; 00500 } 00501 00502 //===----------------------------------------------------------------------===// 00503 // Miscellaneous LibCall Optimizations 00504 //===----------------------------------------------------------------------===// 00505 00506 namespace { 00507 //===---------------------------------------===// 00508 // 'exit' Optimizations 00509 00510 /// ExitOpt - int main() { exit(4); } --> int main() { return 4; } 00511 struct VISIBILITY_HIDDEN ExitOpt : public LibCallOptimization { 00512 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00513 // Verify we have a reasonable prototype for exit. 00514 if (Callee->arg_size() == 0 || !CI->use_empty()) 00515 return 0; 00516 00517 // Verify the caller is main, and that the result type of main matches the 00518 // argument type of exit. 00519 if (Caller->getName() != "main" || !Caller->hasExternalLinkage() || 00520 Caller->getReturnType() != CI->getOperand(1)->getType()) 00521 return 0; 00522 00523 TerminatorInst *OldTI = CI->getParent()->getTerminator(); 00524 00525 // Drop all successor phi node entries. 00526 for (unsigned i = 0, e = OldTI->getNumSuccessors(); i != e; ++i) 00527 OldTI->getSuccessor(i)->removePredecessor(CI->getParent()); 00528 00529 // Remove all instructions after the exit. 00530 BasicBlock::iterator Dead = CI, E = OldTI; ++Dead; 00531 while (Dead != E) { 00532 BasicBlock::iterator Next = next(Dead); 00533 if (Dead->getType() != Type::getVoidTy(*Context)) 00534 Dead->replaceAllUsesWith(UndefValue::get(Dead->getType())); 00535 Dead->eraseFromParent(); 00536 Dead = Next; 00537 } 00538 00539 // Insert a return instruction. 00540 OldTI->eraseFromParent(); 00541 B.SetInsertPoint(B.GetInsertBlock()); 00542 B.CreateRet(CI->getOperand(1)); 00543 00544 return CI; 00545 } 00546 }; 00547 00548 //===----------------------------------------------------------------------===// 00549 // String and Memory LibCall Optimizations 00550 //===----------------------------------------------------------------------===// 00551 00552 //===---------------------------------------===// 00553 // 'strcat' Optimizations 00554 00555 struct VISIBILITY_HIDDEN StrCatOpt : public LibCallOptimization { 00556 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00557 // Verify the "strcat" function prototype. 00558 const FunctionType *FT = Callee->getFunctionType(); 00559 if (FT->getNumParams() != 2 || 00560 FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00561 FT->getParamType(0) != FT->getReturnType() || 00562 FT->getParamType(1) != FT->getReturnType()) 00563 return 0; 00564 00565 // Extract some information from the instruction 00566 Value *Dst = CI->getOperand(1); 00567 Value *Src = CI->getOperand(2); 00568 00569 // See if we can get the length of the input string. 00570 uint64_t Len = GetStringLength(Src); 00571 if (Len == 0) return 0; 00572 --Len; // Unbias length. 00573 00574 // Handle the simple, do-nothing case: strcat(x, "") -> x 00575 if (Len == 0) 00576 return Dst; 00577 00578 // These optimizations require TargetData. 00579 if (!TD) return 0; 00580 00581 EmitStrLenMemCpy(Src, Dst, Len, B); 00582 return Dst; 00583 } 00584 00585 void EmitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B) { 00586 // We need to find the end of the destination string. That's where the 00587 // memory is to be moved to. We just generate a call to strlen. 00588 Value *DstLen = EmitStrLen(Dst, B); 00589 00590 // Now that we have the destination's length, we must index into the 00591 // destination's pointer to get the actual memcpy destination (end of 00592 // the string .. we're concatenating). 00593 Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr"); 00594 00595 // We have enough information to now generate the memcpy call to do the 00596 // concatenation for us. Make a memcpy to copy the nul byte with align = 1. 00597 EmitMemCpy(CpyDst, Src, 00598 ConstantInt::get(TD->getIntPtrType(*Context), Len+1), 1, B); 00599 } 00600 }; 00601 00602 //===---------------------------------------===// 00603 // 'strncat' Optimizations 00604 00605 struct VISIBILITY_HIDDEN StrNCatOpt : public StrCatOpt { 00606 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00607 // Verify the "strncat" function prototype. 00608 const FunctionType *FT = Callee->getFunctionType(); 00609 if (FT->getNumParams() != 3 || 00610 FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00611 FT->getParamType(0) != FT->getReturnType() || 00612 FT->getParamType(1) != FT->getReturnType() || 00613 !isa<IntegerType>(FT->getParamType(2))) 00614 return 0; 00615 00616 // Extract some information from the instruction 00617 Value *Dst = CI->getOperand(1); 00618 Value *Src = CI->getOperand(2); 00619 uint64_t Len; 00620 00621 // We don't do anything if length is not constant 00622 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3))) 00623 Len = LengthArg->getZExtValue(); 00624 else 00625 return 0; 00626 00627 // See if we can get the length of the input string. 00628 uint64_t SrcLen = GetStringLength(Src); 00629 if (SrcLen == 0) return 0; 00630 --SrcLen; // Unbias length. 00631 00632 // Handle the simple, do-nothing cases: 00633 // strncat(x, "", c) -> x 00634 // strncat(x, c, 0) -> x 00635 if (SrcLen == 0 || Len == 0) return Dst; 00636 00637 // These optimizations require TargetData. 00638 if (!TD) return 0; 00639 00640 // We don't optimize this case 00641 if (Len < SrcLen) return 0; 00642 00643 // strncat(x, s, c) -> strcat(x, s) 00644 // s is constant so the strcat can be optimized further 00645 EmitStrLenMemCpy(Src, Dst, SrcLen, B); 00646 return Dst; 00647 } 00648 }; 00649 00650 //===---------------------------------------===// 00651 // 'strchr' Optimizations 00652 00653 struct VISIBILITY_HIDDEN StrChrOpt : public LibCallOptimization { 00654 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00655 // Verify the "strchr" function prototype. 00656 const FunctionType *FT = Callee->getFunctionType(); 00657 if (FT->getNumParams() != 2 || 00658 FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00659 FT->getParamType(0) != FT->getReturnType()) 00660 return 0; 00661 00662 Value *SrcStr = CI->getOperand(1); 00663 00664 // If the second operand is non-constant, see if we can compute the length 00665 // of the input string and turn this into memchr. 00666 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getOperand(2)); 00667 if (CharC == 0) { 00668 // These optimizations require TargetData. 00669 if (!TD) return 0; 00670 00671 uint64_t Len = GetStringLength(SrcStr); 00672 if (Len == 0 || FT->getParamType(1) != Type::getInt32Ty(*Context)) // memchr needs i32. 00673 return 0; 00674 00675 return EmitMemChr(SrcStr, CI->getOperand(2), // include nul. 00676 ConstantInt::get(TD->getIntPtrType(*Context), Len), B); 00677 } 00678 00679 // Otherwise, the character is a constant, see if the first argument is 00680 // a string literal. If so, we can constant fold. 00681 std::string Str; 00682 if (!GetConstantStringInfo(SrcStr, Str)) 00683 return 0; 00684 00685 // strchr can find the nul character. 00686 Str += '\0'; 00687 char CharValue = CharC->getSExtValue(); 00688 00689 // Compute the offset. 00690 uint64_t i = 0; 00691 while (1) { 00692 if (i == Str.size()) // Didn't find the char. strchr returns null. 00693 return Constant::getNullValue(CI->getType()); 00694 // Did we find our match? 00695 if (Str[i] == CharValue) 00696 break; 00697 ++i; 00698 } 00699 00700 // strchr(s+n,c) -> gep(s+n+i,c) 00701 Value *Idx = ConstantInt::get(Type::getInt64Ty(*Context), i); 00702 return B.CreateGEP(SrcStr, Idx, "strchr"); 00703 } 00704 }; 00705 00706 //===---------------------------------------===// 00707 // 'strcmp' Optimizations 00708 00709 struct VISIBILITY_HIDDEN StrCmpOpt : public LibCallOptimization { 00710 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00711 // Verify the "strcmp" function prototype. 00712 const FunctionType *FT = Callee->getFunctionType(); 00713 if (FT->getNumParams() != 2 || FT->getReturnType() != Type::getInt32Ty(*Context) || 00714 FT->getParamType(0) != FT->getParamType(1) || 00715 FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context))) 00716 return 0; 00717 00718 Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2); 00719 if (Str1P == Str2P) // strcmp(x,x) -> 0 00720 return ConstantInt::get(CI->getType(), 0); 00721 00722 std::string Str1, Str2; 00723 bool HasStr1 = GetConstantStringInfo(Str1P, Str1); 00724 bool HasStr2 = GetConstantStringInfo(Str2P, Str2); 00725 00726 if (HasStr1 && Str1.empty()) // strcmp("", x) -> *x 00727 return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType()); 00728 00729 if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x 00730 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType()); 00731 00732 // strcmp(x, y) -> cnst (if both x and y are constant strings) 00733 if (HasStr1 && HasStr2) 00734 return ConstantInt::get(CI->getType(), 00735 strcmp(Str1.c_str(),Str2.c_str())); 00736 00737 // strcmp(P, "x") -> memcmp(P, "x", 2) 00738 uint64_t Len1 = GetStringLength(Str1P); 00739 uint64_t Len2 = GetStringLength(Str2P); 00740 if (Len1 && Len2) { 00741 // These optimizations require TargetData. 00742 if (!TD) return 0; 00743 00744 return EmitMemCmp(Str1P, Str2P, 00745 ConstantInt::get(TD->getIntPtrType(*Context), 00746 std::min(Len1, Len2)), B); 00747 } 00748 00749 return 0; 00750 } 00751 }; 00752 00753 //===---------------------------------------===// 00754 // 'strncmp' Optimizations 00755 00756 struct VISIBILITY_HIDDEN StrNCmpOpt : public LibCallOptimization { 00757 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00758 // Verify the "strncmp" function prototype. 00759 const FunctionType *FT = Callee->getFunctionType(); 00760 if (FT->getNumParams() != 3 || FT->getReturnType() != Type::getInt32Ty(*Context) || 00761 FT->getParamType(0) != FT->getParamType(1) || 00762 FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00763 !isa<IntegerType>(FT->getParamType(2))) 00764 return 0; 00765 00766 Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2); 00767 if (Str1P == Str2P) // strncmp(x,x,n) -> 0 00768 return ConstantInt::get(CI->getType(), 0); 00769 00770 // Get the length argument if it is constant. 00771 uint64_t Length; 00772 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3))) 00773 Length = LengthArg->getZExtValue(); 00774 else 00775 return 0; 00776 00777 if (Length == 0) // strncmp(x,y,0) -> 0 00778 return ConstantInt::get(CI->getType(), 0); 00779 00780 std::string Str1, Str2; 00781 bool HasStr1 = GetConstantStringInfo(Str1P, Str1); 00782 bool HasStr2 = GetConstantStringInfo(Str2P, Str2); 00783 00784 if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> *x 00785 return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType()); 00786 00787 if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x 00788 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType()); 00789 00790 // strncmp(x, y) -> cnst (if both x and y are constant strings) 00791 if (HasStr1 && HasStr2) 00792 return ConstantInt::get(CI->getType(), 00793 strncmp(Str1.c_str(), Str2.c_str(), Length)); 00794 return 0; 00795 } 00796 }; 00797 00798 00799 //===---------------------------------------===// 00800 // 'strcpy' Optimizations 00801 00802 struct VISIBILITY_HIDDEN StrCpyOpt : public LibCallOptimization { 00803 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00804 // Verify the "strcpy" function prototype. 00805 const FunctionType *FT = Callee->getFunctionType(); 00806 if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) || 00807 FT->getParamType(0) != FT->getParamType(1) || 00808 FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context))) 00809 return 0; 00810 00811 Value *Dst = CI->getOperand(1), *Src = CI->getOperand(2); 00812 if (Dst == Src) // strcpy(x,x) -> x 00813 return Src; 00814 00815 // These optimizations require TargetData. 00816 if (!TD) return 0; 00817 00818 // See if we can get the length of the input string. 00819 uint64_t Len = GetStringLength(Src); 00820 if (Len == 0) return 0; 00821 00822 // We have enough information to now generate the memcpy call to do the 00823 // concatenation for us. Make a memcpy to copy the nul byte with align = 1. 00824 EmitMemCpy(Dst, Src, 00825 ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B); 00826 return Dst; 00827 } 00828 }; 00829 00830 //===---------------------------------------===// 00831 // 'strncpy' Optimizations 00832 00833 struct VISIBILITY_HIDDEN StrNCpyOpt : public LibCallOptimization { 00834 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00835 const FunctionType *FT = Callee->getFunctionType(); 00836 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 00837 FT->getParamType(0) != FT->getParamType(1) || 00838 FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00839 !isa<IntegerType>(FT->getParamType(2))) 00840 return 0; 00841 00842 Value *Dst = CI->getOperand(1); 00843 Value *Src = CI->getOperand(2); 00844 Value *LenOp = CI->getOperand(3); 00845 00846 // See if we can get the length of the input string. 00847 uint64_t SrcLen = GetStringLength(Src); 00848 if (SrcLen == 0) return 0; 00849 --SrcLen; 00850 00851 if (SrcLen == 0) { 00852 // strncpy(x, "", y) -> memset(x, '\0', y, 1) 00853 EmitMemSet(Dst, ConstantInt::get(Type::getInt8Ty(*Context), '\0'), LenOp, B); 00854 return Dst; 00855 } 00856 00857 uint64_t Len; 00858 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp)) 00859 Len = LengthArg->getZExtValue(); 00860 else 00861 return 0; 00862 00863 if (Len == 0) return Dst; // strncpy(x, y, 0) -> x 00864 00865 // These optimizations require TargetData. 00866 if (!TD) return 0; 00867 00868 // Let strncpy handle the zero padding 00869 if (Len > SrcLen+1) return 0; 00870 00871 // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant] 00872 EmitMemCpy(Dst, Src, 00873 ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B); 00874 00875 return Dst; 00876 } 00877 }; 00878 00879 //===---------------------------------------===// 00880 // 'strlen' Optimizations 00881 00882 struct VISIBILITY_HIDDEN StrLenOpt : public LibCallOptimization { 00883 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00884 const FunctionType *FT = Callee->getFunctionType(); 00885 if (FT->getNumParams() != 1 || 00886 FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) || 00887 !isa<IntegerType>(FT->getReturnType())) 00888 return 0; 00889 00890 Value *Src = CI->getOperand(1); 00891 00892 // Constant folding: strlen("xyz") -> 3 00893 if (uint64_t Len = GetStringLength(Src)) 00894 return ConstantInt::get(CI->getType(), Len-1); 00895 00896 // Handle strlen(p) != 0. 00897 if (!IsOnlyUsedInZeroEqualityComparison(CI)) return 0; 00898 00899 // strlen(x) != 0 --> *x != 0 00900 // strlen(x) == 0 --> *x == 0 00901 return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType()); 00902 } 00903 }; 00904 00905 //===---------------------------------------===// 00906 // 'strto*' Optimizations 00907 00908 struct VISIBILITY_HIDDEN StrToOpt : public LibCallOptimization { 00909 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00910 const FunctionType *FT = Callee->getFunctionType(); 00911 if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) || 00912 !isa<PointerType>(FT->getParamType(0)) || 00913 !isa<PointerType>(FT->getParamType(1))) 00914 return 0; 00915 00916 Value *EndPtr = CI->getOperand(2); 00917 if (isa<ConstantPointerNull>(EndPtr)) { 00918 CI->setOnlyReadsMemory(); 00919 CI->addAttribute(1, Attribute::NoCapture); 00920 } 00921 00922 return 0; 00923 } 00924 }; 00925 00926 00927 //===---------------------------------------===// 00928 // 'memcmp' Optimizations 00929 00930 struct VISIBILITY_HIDDEN MemCmpOpt : public LibCallOptimization { 00931 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00932 const FunctionType *FT = Callee->getFunctionType(); 00933 if (FT->getNumParams() != 3 || !isa<PointerType>(FT->getParamType(0)) || 00934 !isa<PointerType>(FT->getParamType(1)) || 00935 FT->getReturnType() != Type::getInt32Ty(*Context)) 00936 return 0; 00937 00938 Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2); 00939 00940 if (LHS == RHS) // memcmp(s,s,x) -> 0 00941 return Constant::getNullValue(CI->getType()); 00942 00943 // Make sure we have a constant length. 00944 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3)); 00945 if (!LenC) return 0; 00946 uint64_t Len = LenC->getZExtValue(); 00947 00948 if (Len == 0) // memcmp(s1,s2,0) -> 0 00949 return Constant::getNullValue(CI->getType()); 00950 00951 if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS 00952 Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv"); 00953 Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv"); 00954 return B.CreateSExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType()); 00955 } 00956 00957 // memcmp(S1,S2,2) != 0 -> (*(short*)LHS ^ *(short*)RHS) != 0 00958 // memcmp(S1,S2,4) != 0 -> (*(int*)LHS ^ *(int*)RHS) != 0 00959 if ((Len == 2 || Len == 4) && IsOnlyUsedInZeroEqualityComparison(CI)) { 00960 const Type *PTy = PointerType::getUnqual(Len == 2 ? 00961 Type::getInt16Ty(*Context) : Type::getInt32Ty(*Context)); 00962 LHS = B.CreateBitCast(LHS, PTy, "tmp"); 00963 RHS = B.CreateBitCast(RHS, PTy, "tmp"); 00964 LoadInst *LHSV = B.CreateLoad(LHS, "lhsv"); 00965 LoadInst *RHSV = B.CreateLoad(RHS, "rhsv"); 00966 LHSV->setAlignment(1); RHSV->setAlignment(1); // Unaligned loads. 00967 return B.CreateZExt(B.CreateXor(LHSV, RHSV, "shortdiff"), CI->getType()); 00968 } 00969 00970 return 0; 00971 } 00972 }; 00973 00974 //===---------------------------------------===// 00975 // 'memcpy' Optimizations 00976 00977 struct VISIBILITY_HIDDEN MemCpyOpt : public LibCallOptimization { 00978 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 00979 // These optimizations require TargetData. 00980 if (!TD) return 0; 00981 00982 const FunctionType *FT = Callee->getFunctionType(); 00983 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 00984 !isa<PointerType>(FT->getParamType(0)) || 00985 !isa<PointerType>(FT->getParamType(1)) || 00986 FT->getParamType(2) != TD->getIntPtrType(*Context)) 00987 return 0; 00988 00989 // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1) 00990 EmitMemCpy(CI->getOperand(1), CI->getOperand(2), CI->getOperand(3), 1, B); 00991 return CI->getOperand(1); 00992 } 00993 }; 00994 00995 //===---------------------------------------===// 00996 // 'memmove' Optimizations 00997 00998 struct VISIBILITY_HIDDEN MemMoveOpt : public LibCallOptimization { 00999 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01000 // These optimizations require TargetData. 01001 if (!TD) return 0; 01002 01003 const FunctionType *FT = Callee->getFunctionType(); 01004 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 01005 !isa<PointerType>(FT->getParamType(0)) || 01006 !isa<PointerType>(FT->getParamType(1)) || 01007 FT->getParamType(2) != TD->getIntPtrType(*Context)) 01008 return 0; 01009 01010 // memmove(x, y, n) -> llvm.memmove(x, y, n, 1) 01011 Module *M = Caller->getParent(); 01012 Intrinsic::ID IID = Intrinsic::memmove; 01013 const Type *Tys[1]; 01014 Tys[0] = TD->getIntPtrType(*Context); 01015 Value *MemMove = Intrinsic::getDeclaration(M, IID, Tys, 1); 01016 Value *Dst = CastToCStr(CI->getOperand(1), B); 01017 Value *Src = CastToCStr(CI->getOperand(2), B); 01018 Value *Size = CI->getOperand(3); 01019 Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1); 01020 B.CreateCall4(MemMove, Dst, Src, Size, Align); 01021 return CI->getOperand(1); 01022 } 01023 }; 01024 01025 //===---------------------------------------===// 01026 // 'memset' Optimizations 01027 01028 struct VISIBILITY_HIDDEN MemSetOpt : public LibCallOptimization { 01029 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01030 // These optimizations require TargetData. 01031 if (!TD) return 0; 01032 01033 const FunctionType *FT = Callee->getFunctionType(); 01034 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 01035 !isa<PointerType>(FT->getParamType(0)) || 01036 !isa<IntegerType>(FT->getParamType(1)) || 01037 FT->getParamType(2) != TD->getIntPtrType(*Context)) 01038 return 0; 01039 01040 // memset(p, v, n) -> llvm.memset(p, v, n, 1) 01041 Value *Val = B.CreateIntCast(CI->getOperand(2), Type::getInt8Ty(*Context), false); 01042 EmitMemSet(CI->getOperand(1), Val, CI->getOperand(3), B); 01043 return CI->getOperand(1); 01044 } 01045 }; 01046 01047 //===----------------------------------------------------------------------===// 01048 // Math Library Optimizations 01049 //===----------------------------------------------------------------------===// 01050 01051 //===---------------------------------------===// 01052 // 'pow*' Optimizations 01053 01054 struct VISIBILITY_HIDDEN PowOpt : public LibCallOptimization { 01055 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01056 const FunctionType *FT = Callee->getFunctionType(); 01057 // Just make sure this has 2 arguments of the same FP type, which match the 01058 // result type. 01059 if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) || 01060 FT->getParamType(0) != FT->getParamType(1) || 01061 !FT->getParamType(0)->isFloatingPoint()) 01062 return 0; 01063 01064 Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2); 01065 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 01066 if (Op1C->isExactlyValue(1.0)) // pow(1.0, x) -> 1.0 01067 return Op1C; 01068 if (Op1C->isExactlyValue(2.0)) // pow(2.0, x) -> exp2(x) 01069 return EmitUnaryFloatFnCall(Op2, "exp2", B); 01070 } 01071 01072 ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2); 01073 if (Op2C == 0) return 0; 01074 01075 if (Op2C->getValueAPF().isZero()) // pow(x, 0.0) -> 1.0 01076 return ConstantFP::get(CI->getType(), 1.0); 01077 01078 if (Op2C->isExactlyValue(0.5)) { 01079 // FIXME: This is not safe for -0.0 and -inf. This can only be done when 01080 // 'unsafe' math optimizations are allowed. 01081 // x pow(x, 0.5) sqrt(x) 01082 // --------------------------------------------- 01083 // -0.0 +0.0 -0.0 01084 // -inf +inf NaN 01085 #if 0 01086 // pow(x, 0.5) -> sqrt(x) 01087 return B.CreateCall(get_sqrt(), Op1, "sqrt"); 01088 #endif 01089 } 01090 01091 if (Op2C->isExactlyValue(1.0)) // pow(x, 1.0) -> x 01092 return Op1; 01093 if (Op2C->isExactlyValue(2.0)) // pow(x, 2.0) -> x*x 01094 return B.CreateFMul(Op1, Op1, "pow2"); 01095 if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x 01096 return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0), 01097 Op1, "powrecip"); 01098 return 0; 01099 } 01100 }; 01101 01102 //===---------------------------------------===// 01103 // 'exp2' Optimizations 01104 01105 struct VISIBILITY_HIDDEN Exp2Opt : public LibCallOptimization { 01106 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01107 const FunctionType *FT = Callee->getFunctionType(); 01108 // Just make sure this has 1 argument of FP type, which matches the 01109 // result type. 01110 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) || 01111 !FT->getParamType(0)->isFloatingPoint()) 01112 return 0; 01113 01114 Value *Op = CI->getOperand(1); 01115 // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= 32 01116 // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < 32 01117 Value *LdExpArg = 0; 01118 if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) { 01119 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32) 01120 LdExpArg = B.CreateSExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp"); 01121 } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) { 01122 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32) 01123 LdExpArg = B.CreateZExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp"); 01124 } 01125 01126 if (LdExpArg) { 01127 const char *Name; 01128 if (Op->getType() == Type::getFloatTy(*Context)) 01129 Name = "ldexpf"; 01130 else if (Op->getType() == Type::getDoubleTy(*Context)) 01131 Name = "ldexp"; 01132 else 01133 Name = "ldexpl"; 01134 01135 Constant *One = ConstantFP::get(*Context, APFloat(1.0f)); 01136 if (Op->getType() != Type::getFloatTy(*Context)) 01137 One = ConstantExpr::getFPExtend(One, Op->getType()); 01138 01139 Module *M = Caller->getParent(); 01140 Value *Callee = M->getOrInsertFunction(Name, Op->getType(), 01141 Op->getType(), Type::getInt32Ty(*Context),NULL); 01142 CallInst *CI = B.CreateCall2(Callee, One, LdExpArg); 01143 if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts())) 01144 CI->setCallingConv(F->getCallingConv()); 01145 01146 return CI; 01147 } 01148 return 0; 01149 } 01150 }; 01151 01152 //===---------------------------------------===// 01153 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor' 01154 01155 struct VISIBILITY_HIDDEN UnaryDoubleFPOpt : public LibCallOptimization { 01156 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01157 const FunctionType *FT = Callee->getFunctionType(); 01158 if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getDoubleTy(*Context) || 01159 FT->getParamType(0) != Type::getDoubleTy(*Context)) 01160 return 0; 01161 01162 // If this is something like 'floor((double)floatval)', convert to floorf. 01163 FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1)); 01164 if (Cast == 0 || Cast->getOperand(0)->getType() != Type::getFloatTy(*Context)) 01165 return 0; 01166 01167 // floor((double)floatval) -> (double)floorf(floatval) 01168 Value *V = Cast->getOperand(0); 01169 V = EmitUnaryFloatFnCall(V, Callee->getName().data(), B); 01170 return B.CreateFPExt(V, Type::getDoubleTy(*Context)); 01171 } 01172 }; 01173 01174 //===----------------------------------------------------------------------===// 01175 // Integer Optimizations 01176 //===----------------------------------------------------------------------===// 01177 01178 //===---------------------------------------===// 01179 // 'ffs*' Optimizations 01180 01181 struct VISIBILITY_HIDDEN FFSOpt : public LibCallOptimization { 01182 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01183 const FunctionType *FT = Callee->getFunctionType(); 01184 // Just make sure this has 2 arguments of the same FP type, which match the 01185 // result type. 01186 if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getInt32Ty(*Context) || 01187 !isa<IntegerType>(FT->getParamType(0))) 01188 return 0; 01189 01190 Value *Op = CI->getOperand(1); 01191 01192 // Constant fold. 01193 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) { 01194 if (CI->getValue() == 0) // ffs(0) -> 0. 01195 return Constant::getNullValue(CI->getType()); 01196 return ConstantInt::get(Type::getInt32Ty(*Context), // ffs(c) -> cttz(c)+1 01197 CI->getValue().countTrailingZeros()+1); 01198 } 01199 01200 // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0 01201 const Type *ArgType = Op->getType(); 01202 Value *F = Intrinsic::getDeclaration(Callee->getParent(), 01203 Intrinsic::cttz, &ArgType, 1); 01204 Value *V = B.CreateCall(F, Op, "cttz"); 01205 V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1), "tmp"); 01206 V = B.CreateIntCast(V, Type::getInt32Ty(*Context), false, "tmp"); 01207 01208 Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp"); 01209 return B.CreateSelect(Cond, V, ConstantInt::get(Type::getInt32Ty(*Context), 0)); 01210 } 01211 }; 01212 01213 //===---------------------------------------===// 01214 // 'isdigit' Optimizations 01215 01216 struct VISIBILITY_HIDDEN IsDigitOpt : public LibCallOptimization { 01217 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01218 const FunctionType *FT = Callee->getFunctionType(); 01219 // We require integer(i32) 01220 if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) || 01221 FT->getParamType(0) != Type::getInt32Ty(*Context)) 01222 return 0; 01223 01224 // isdigit(c) -> (c-'0') <u 10 01225 Value *Op = CI->getOperand(1); 01226 Op = B.CreateSub(Op, ConstantInt::get(Type::getInt32Ty(*Context), '0'), 01227 "isdigittmp"); 01228 Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 10), 01229 "isdigit"); 01230 return B.CreateZExt(Op, CI->getType()); 01231 } 01232 }; 01233 01234 //===---------------------------------------===// 01235 // 'isascii' Optimizations 01236 01237 struct VISIBILITY_HIDDEN IsAsciiOpt : public LibCallOptimization { 01238 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01239 const FunctionType *FT = Callee->getFunctionType(); 01240 // We require integer(i32) 01241 if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) || 01242 FT->getParamType(0) != Type::getInt32Ty(*Context)) 01243 return 0; 01244 01245 // isascii(c) -> c <u 128 01246 Value *Op = CI->getOperand(1); 01247 Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 128), 01248 "isascii"); 01249 return B.CreateZExt(Op, CI->getType()); 01250 } 01251 }; 01252 01253 //===---------------------------------------===// 01254 // 'abs', 'labs', 'llabs' Optimizations 01255 01256 struct VISIBILITY_HIDDEN AbsOpt : public LibCallOptimization { 01257 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01258 const FunctionType *FT = Callee->getFunctionType(); 01259 // We require integer(integer) where the types agree. 01260 if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) || 01261 FT->getParamType(0) != FT->getReturnType()) 01262 return 0; 01263 01264 // abs(x) -> x >s -1 ? x : -x 01265 Value *Op = CI->getOperand(1); 01266 Value *Pos = B.CreateICmpSGT(Op, 01267 Constant::getAllOnesValue(Op->getType()), 01268 "ispos"); 01269 Value *Neg = B.CreateNeg(Op, "neg"); 01270 return B.CreateSelect(Pos, Op, Neg); 01271 } 01272 }; 01273 01274 01275 //===---------------------------------------===// 01276 // 'toascii' Optimizations 01277 01278 struct VISIBILITY_HIDDEN ToAsciiOpt : public LibCallOptimization { 01279 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01280 const FunctionType *FT = Callee->getFunctionType(); 01281 // We require i32(i32) 01282 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) || 01283 FT->getParamType(0) != Type::getInt32Ty(*Context)) 01284 return 0; 01285 01286 // isascii(c) -> c & 0x7f 01287 return B.CreateAnd(CI->getOperand(1), 01288 ConstantInt::get(CI->getType(),0x7F)); 01289 } 01290 }; 01291 01292 //===----------------------------------------------------------------------===// 01293 // Formatting and IO Optimizations 01294 //===----------------------------------------------------------------------===// 01295 01296 //===---------------------------------------===// 01297 // 'printf' Optimizations 01298 01299 struct VISIBILITY_HIDDEN PrintFOpt : public LibCallOptimization { 01300 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01301 // Require one fixed pointer argument and an integer/void result. 01302 const FunctionType *FT = Callee->getFunctionType(); 01303 if (FT->getNumParams() < 1 || !isa<PointerType>(FT->getParamType(0)) || 01304 !(isa<IntegerType>(FT->getReturnType()) || 01305 FT->getReturnType() == Type::getVoidTy(*Context))) 01306 return 0; 01307 01308 // Check for a fixed format string. 01309 std::string FormatStr; 01310 if (!GetConstantStringInfo(CI->getOperand(1), FormatStr)) 01311 return 0; 01312 01313 // Empty format string -> noop. 01314 if (FormatStr.empty()) // Tolerate printf's declared void. 01315 return CI->use_empty() ? (Value*)CI : 01316 ConstantInt::get(CI->getType(), 0); 01317 01318 // printf("x") -> putchar('x'), even for '%'. 01319 if (FormatStr.size() == 1) { 01320 EmitPutChar(ConstantInt::get(Type::getInt32Ty(*Context), FormatStr[0]), B); 01321 return CI->use_empty() ? (Value*)CI : 01322 ConstantInt::get(CI->getType(), 1); 01323 } 01324 01325 // printf("foo\n") --> puts("foo") 01326 if (FormatStr[FormatStr.size()-1] == '\n' && 01327 FormatStr.find('%') == std::string::npos) { // no format characters. 01328 // Create a string literal with no \n on it. We expect the constant merge 01329 // pass to be run after this pass, to merge duplicate strings. 01330 FormatStr.erase(FormatStr.end()-1); 01331 Constant *C = ConstantArray::get(*Context, FormatStr, true); 01332 C = new GlobalVariable(*Callee->getParent(), C->getType(), true, 01333 GlobalVariable::InternalLinkage, C, "str"); 01334 EmitPutS(C, B); 01335 return CI->use_empty() ? (Value*)CI : 01336 ConstantInt::get(CI->getType(), FormatStr.size()+1); 01337 } 01338 01339 // Optimize specific format strings. 01340 // printf("%c", chr) --> putchar(*(i8*)dst) 01341 if (FormatStr == "%c" && CI->getNumOperands() > 2 && 01342 isa<IntegerType>(CI->getOperand(2)->getType())) { 01343 EmitPutChar(CI->getOperand(2), B); 01344 return CI->use_empty() ? (Value*)CI : 01345 ConstantInt::get(CI->getType(), 1); 01346 } 01347 01348 // printf("%s\n", str) --> puts(str) 01349 if (FormatStr == "%s\n" && CI->getNumOperands() > 2 && 01350 isa<PointerType>(CI->getOperand(2)->getType()) && 01351 CI->use_empty()) { 01352 EmitPutS(CI->getOperand(2), B); 01353 return CI; 01354 } 01355 return 0; 01356 } 01357 }; 01358 01359 //===---------------------------------------===// 01360 // 'sprintf' Optimizations 01361 01362 struct VISIBILITY_HIDDEN SPrintFOpt : public LibCallOptimization { 01363 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01364 // Require two fixed pointer arguments and an integer result. 01365 const FunctionType *FT = Callee->getFunctionType(); 01366 if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) || 01367 !isa<PointerType>(FT->getParamType(1)) || 01368 !isa<IntegerType>(FT->getReturnType())) 01369 return 0; 01370 01371 // Check for a fixed format string. 01372 std::string FormatStr; 01373 if (!GetConstantStringInfo(CI->getOperand(2), FormatStr)) 01374 return 0; 01375 01376 // If we just have a format string (nothing else crazy) transform it. 01377 if (CI->getNumOperands() == 3) { 01378 // Make sure there's no % in the constant array. We could try to handle 01379 // %% -> % in the future if we cared. 01380 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i) 01381 if (FormatStr[i] == '%') 01382 return 0; // we found a format specifier, bail out. 01383 01384 // These optimizations require TargetData. 01385 if (!TD) return 0; 01386 01387 // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1) 01388 EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte. 01389 ConstantInt::get(TD->getIntPtrType(*Context), FormatStr.size()+1),1,B); 01390 return ConstantInt::get(CI->getType(), FormatStr.size()); 01391 } 01392 01393 // The remaining optimizations require the format string to be "%s" or "%c" 01394 // and have an extra operand. 01395 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4) 01396 return 0; 01397 01398 // Decode the second character of the format string. 01399 if (FormatStr[1] == 'c') { 01400 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0 01401 if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0; 01402 Value *V = B.CreateTrunc(CI->getOperand(3), Type::getInt8Ty(*Context), "char"); 01403 Value *Ptr = CastToCStr(CI->getOperand(1), B); 01404 B.CreateStore(V, Ptr); 01405 Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::getInt32Ty(*Context), 1), "nul"); 01406 B.CreateStore(Constant::getNullValue(Type::getInt8Ty(*Context)), Ptr); 01407 01408 return ConstantInt::get(CI->getType(), 1); 01409 } 01410 01411 if (FormatStr[1] == 's') { 01412 // These optimizations require TargetData. 01413 if (!TD) return 0; 01414 01415 // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1) 01416 if (!isa<PointerType>(CI->getOperand(3)->getType())) return 0; 01417 01418 Value *Len = EmitStrLen(CI->getOperand(3), B); 01419 Value *IncLen = B.CreateAdd(Len, 01420 ConstantInt::get(Len->getType(), 1), 01421 "leninc"); 01422 EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, B); 01423 01424 // The sprintf result is the unincremented number of bytes in the string. 01425 return B.CreateIntCast(Len, CI->getType(), false); 01426 } 01427 return 0; 01428 } 01429 }; 01430 01431 //===---------------------------------------===// 01432 // 'fwrite' Optimizations 01433 01434 struct VISIBILITY_HIDDEN FWriteOpt : public LibCallOptimization { 01435 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01436 // Require a pointer, an integer, an integer, a pointer, returning integer. 01437 const FunctionType *FT = Callee->getFunctionType(); 01438 if (FT->getNumParams() != 4 || !isa<PointerType>(FT->getParamType(0)) || 01439 !isa<IntegerType>(FT->getParamType(1)) || 01440 !isa<IntegerType>(FT->getParamType(2)) || 01441 !isa<PointerType>(FT->getParamType(3)) || 01442 !isa<IntegerType>(FT->getReturnType())) 01443 return 0; 01444 01445 // Get the element size and count. 01446 ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2)); 01447 ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3)); 01448 if (!SizeC || !CountC) return 0; 01449 uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue(); 01450 01451 // If this is writing zero records, remove the call (it's a noop). 01452 if (Bytes == 0) 01453 return ConstantInt::get(CI->getType(), 0); 01454 01455 // If this is writing one byte, turn it into fputc. 01456 if (Bytes == 1) { // fwrite(S,1,1,F) -> fputc(S[0],F) 01457 Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char"); 01458 EmitFPutC(Char, CI->getOperand(4), B); 01459 return ConstantInt::get(CI->getType(), 1); 01460 } 01461 01462 return 0; 01463 } 01464 }; 01465 01466 //===---------------------------------------===// 01467 // 'fputs' Optimizations 01468 01469 struct VISIBILITY_HIDDEN FPutsOpt : public LibCallOptimization { 01470 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01471 // These optimizations require TargetData. 01472 if (!TD) return 0; 01473 01474 // Require two pointers. Also, we can't optimize if return value is used. 01475 const FunctionType *FT = Callee->getFunctionType(); 01476 if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) || 01477 !isa<PointerType>(FT->getParamType(1)) || 01478 !CI->use_empty()) 01479 return 0; 01480 01481 // fputs(s,F) --> fwrite(s,1,strlen(s),F) 01482 uint64_t Len = GetStringLength(CI->getOperand(1)); 01483 if (!Len) return 0; 01484 EmitFWrite(CI->getOperand(1), 01485 ConstantInt::get(TD->getIntPtrType(*Context), Len-1), 01486 CI->getOperand(2), B); 01487 return CI; // Known to have no uses (see above). 01488 } 01489 }; 01490 01491 //===---------------------------------------===// 01492 // 'fprintf' Optimizations 01493 01494 struct VISIBILITY_HIDDEN FPrintFOpt : public LibCallOptimization { 01495 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 01496 // Require two fixed paramters as pointers and integer result. 01497 const FunctionType *FT = Callee->getFunctionType(); 01498 if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) || 01499 !isa<PointerType>(FT->getParamType(1)) || 01500 !isa<IntegerType>(FT->getReturnType())) 01501 return 0; 01502 01503 // All the optimizations depend on the format string. 01504 std::string FormatStr; 01505 if (!GetConstantStringInfo(CI->getOperand(2), FormatStr)) 01506 return 0; 01507 01508 // fprintf(F, "foo") --> fwrite("foo", 3, 1, F) 01509 if (CI->getNumOperands() == 3) { 01510 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i) 01511 if (FormatStr[i] == '%') // Could handle %% -> % if we cared. 01512 return 0; // We found a format specifier. 01513 01514 // These optimizations require TargetData. 01515 if (!TD) return 0; 01516 01517 EmitFWrite(CI->getOperand(2), ConstantInt::get(TD->getIntPtrType(*Context), 01518 FormatStr.size()), 01519 CI->getOperand(1), B); 01520 return ConstantInt::get(CI->getType(), FormatStr.size()); 01521 } 01522 01523 // The remaining optimizations require the format string to be "%s" or "%c" 01524 // and have an extra operand. 01525 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4) 01526 return 0; 01527 01528 // Decode the second character of the format string. 01529 if (FormatStr[1] == 'c') { 01530 // fprintf(F, "%c", chr) --> *(i8*)dst = chr 01531 if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0; 01532 EmitFPutC(CI->getOperand(3), CI->getOperand(1), B); 01533 return ConstantInt::get(CI->getType(), 1); 01534 } 01535 01536 if (FormatStr[1] == 's') { 01537 // fprintf(F, "%s", str) -> fputs(str, F) 01538 if (!isa<PointerType>(CI->getOperand(3)->getType()) || !CI->use_empty()) 01539 return 0; 01540 EmitFPutS(CI->getOperand(3), CI->getOperand(1), B); 01541 return CI; 01542 } 01543 return 0; 01544 } 01545 }; 01546 01547 } // end anonymous namespace. 01548 01549 //===----------------------------------------------------------------------===// 01550 // SimplifyLibCalls Pass Implementation 01551 //===----------------------------------------------------------------------===// 01552 01553 namespace { 01554 /// This pass optimizes well known library functions from libc and libm. 01555 /// 01556 class VISIBILITY_HIDDEN SimplifyLibCalls : public FunctionPass { 01557 StringMap<LibCallOptimization*> Optimizations; 01558 // Miscellaneous LibCall Optimizations 01559 ExitOpt Exit; 01560 // String and Memory LibCall Optimizations 01561 StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp; 01562 StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen; 01563 StrToOpt StrTo; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; 01564 MemSetOpt MemSet; 01565 // Math Library Optimizations 01566 PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP; 01567 // Integer Optimizations 01568 FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii; 01569 ToAsciiOpt ToAscii; 01570 // Formatting and IO Optimizations 01571 SPrintFOpt SPrintF; PrintFOpt PrintF; 01572 FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF; 01573 01574 bool Modified; // This is only used by doInitialization. 01575 public: 01576 static char ID; // Pass identification 01577 SimplifyLibCalls() : FunctionPass(&ID) {} 01578 01579 void InitOptimizations(); 01580 bool runOnFunction(Function &F); 01581 01582 void setDoesNotAccessMemory(Function &F); 01583 void setOnlyReadsMemory(Function &F); 01584 void setDoesNotThrow(Function &F); 01585 void setDoesNotCapture(Function &F, unsigned n); 01586 void setDoesNotAlias(Function &F, unsigned n); 01587 bool doInitialization(Module &M); 01588 01589 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 01590 } 01591 }; 01592 char SimplifyLibCalls::ID = 0; 01593 } // end anonymous namespace. 01594 01595 static RegisterPass<SimplifyLibCalls> 01596 X("simplify-libcalls", "Simplify well-known library calls"); 01597 01598 // Public interface to the Simplify LibCalls pass. 01599 FunctionPass *llvm::createSimplifyLibCallsPass() { 01600 return new SimplifyLibCalls(); 01601 } 01602 01603 /// Optimizations - Populate the Optimizations map with all the optimizations 01604 /// we know. 01605 void SimplifyLibCalls::InitOptimizations() { 01606 // Miscellaneous LibCall Optimizations 01607 Optimizations["exit"] = &Exit; 01608 01609 // String and Memory LibCall Optimizations 01610 Optimizations["strcat"] = &StrCat; 01611 Optimizations["strncat"] = &StrNCat; 01612 Optimizations["strchr"] = &StrChr; 01613 Optimizations["strcmp"] = &StrCmp; 01614 Optimizations["strncmp"] = &StrNCmp; 01615 Optimizations["strcpy"] = &StrCpy; 01616 Optimizations["strncpy"] = &StrNCpy; 01617 Optimizations["strlen"] = &StrLen; 01618 Optimizations["strtol"] = &StrTo; 01619 Optimizations["strtod"] = &StrTo; 01620 Optimizations["strtof"] = &StrTo; 01621 Optimizations["strtoul"] = &StrTo; 01622 Optimizations["strtoll"] = &StrTo; 01623 Optimizations["strtold"] = &StrTo; 01624 Optimizations["strtoull"] = &StrTo; 01625 Optimizations["memcmp"] = &MemCmp; 01626 Optimizations["memcpy"] = &MemCpy; 01627 Optimizations["memmove"] = &MemMove; 01628 Optimizations["memset"] = &MemSet; 01629 01630 // Math Library Optimizations 01631 Optimizations["powf"] = &Pow; 01632 Optimizations["pow"] = &Pow; 01633 Optimizations["powl"] = &Pow; 01634 Optimizations["llvm.pow.f32"] = &Pow; 01635 Optimizations["llvm.pow.f64"] = &Pow; 01636 Optimizations["llvm.pow.f80"] = &Pow; 01637 Optimizations["llvm.pow.f128"] = &Pow; 01638 Optimizations["llvm.pow.ppcf128"] = &Pow; 01639 Optimizations["exp2l"] = &Exp2; 01640 Optimizations["exp2"] = &Exp2; 01641 Optimizations["exp2f"] = &Exp2; 01642 Optimizations["llvm.exp2.ppcf128"] = &Exp2; 01643 Optimizations["llvm.exp2.f128"] = &Exp2; 01644 Optimizations["llvm.exp2.f80"] = &Exp2; 01645 Optimizations["llvm.exp2.f64"] = &Exp2; 01646 Optimizations["llvm.exp2.f32"] = &Exp2; 01647 01648 #ifdef HAVE_FLOORF 01649 Optimizations["floor"] = &UnaryDoubleFP; 01650 #endif 01651 #ifdef HAVE_CEILF 01652 Optimizations["ceil"] = &UnaryDoubleFP; 01653 #endif 01654 #ifdef HAVE_ROUNDF 01655 Optimizations["round"] = &UnaryDoubleFP; 01656 #endif 01657 #ifdef HAVE_RINTF 01658 Optimizations["rint"] = &UnaryDoubleFP; 01659 #endif 01660 #ifdef HAVE_NEARBYINTF 01661 Optimizations["nearbyint"] = &UnaryDoubleFP; 01662 #endif 01663 01664 // Integer Optimizations 01665 Optimizations["ffs"] = &FFS; 01666 Optimizations["ffsl"] = &FFS; 01667 Optimizations["ffsll"] = &FFS; 01668 Optimizations["abs"] = &Abs; 01669 Optimizations["labs"] = &Abs; 01670 Optimizations["llabs"] = &Abs; 01671 Optimizations["isdigit"] = &IsDigit; 01672 Optimizations["isascii"] = &IsAscii; 01673 Optimizations["toascii"] = &ToAscii; 01674 01675 // Formatting and IO Optimizations 01676 Optimizations["sprintf"] = &SPrintF; 01677 Optimizations["printf"] = &PrintF; 01678 Optimizations["fwrite"] = &FWrite; 01679 Optimizations["fputs"] = &FPuts; 01680 Optimizations["fprintf"] = &FPrintF; 01681 } 01682 01683 01684 /// runOnFunction - Top level algorithm. 01685 /// 01686 bool SimplifyLibCalls::runOnFunction(Function &F) { 01687 if (Optimizations.empty()) 01688 InitOptimizations(); 01689 01690 const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 01691 01692 IRBuilder<> Builder(F.getContext()); 01693 01694 bool Changed = false; 01695 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 01696 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 01697 // Ignore non-calls. 01698 CallInst *CI = dyn_cast<CallInst>(I++); 01699 if (!CI) continue; 01700 01701 // Ignore indirect calls and calls to non-external functions. 01702 Function *Callee = CI->getCalledFunction(); 01703 if (Callee == 0 || !Callee->isDeclaration() || 01704 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage())) 01705 continue; 01706 01707 // Ignore unknown calls. 01708 LibCallOptimization *LCO = Optimizations.lookup(Callee->getName()); 01709 if (!LCO) continue; 01710 01711 // Set the builder to the instruction after the call. 01712 Builder.SetInsertPoint(BB, I); 01713 01714 // Try to optimize this call. 01715 Value *Result = LCO->OptimizeCall(CI, TD, Builder); 01716 if (Result == 0) continue; 01717 01718 DEBUG(errs() << "SimplifyLibCalls simplified: " << *CI; 01719 errs() << " into: " << *Result << "\n"); 01720 01721 // Something changed! 01722 Changed = true; 01723 ++NumSimplified; 01724 01725 // Inspect the instruction after the call (which was potentially just 01726 // added) next. 01727 I = CI; ++I; 01728 01729 if (CI != Result && !CI->use_empty()) { 01730 CI->replaceAllUsesWith(Result); 01731 if (!Result->hasName()) 01732 Result->takeName(CI); 01733 } 01734 CI->eraseFromParent(); 01735 } 01736 } 01737 return Changed; 01738 } 01739 01740 // Utility methods for doInitialization. 01741 01742 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) { 01743 if (!F.doesNotAccessMemory()) { 01744 F.setDoesNotAccessMemory(); 01745 ++NumAnnotated; 01746 Modified = true; 01747 } 01748 } 01749 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) { 01750 if (!F.onlyReadsMemory()) { 01751 F.setOnlyReadsMemory(); 01752 ++NumAnnotated; 01753 Modified = true; 01754 } 01755 } 01756 void SimplifyLibCalls::setDoesNotThrow(Function &F) { 01757 if (!F.doesNotThrow()) { 01758 F.setDoesNotThrow(); 01759 ++NumAnnotated; 01760 Modified = true; 01761 } 01762 } 01763 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) { 01764 if (!F.doesNotCapture(n)) { 01765 F.setDoesNotCapture(n); 01766 ++NumAnnotated; 01767 Modified = true; 01768 } 01769 } 01770 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) { 01771 if (!F.doesNotAlias(n)) { 01772 F.setDoesNotAlias(n); 01773 ++NumAnnotated; 01774 Modified = true; 01775 } 01776 } 01777 01778 /// doInitialization - Add attributes to well-known functions. 01779 /// 01780 bool SimplifyLibCalls::doInitialization(Module &M) { 01781 Modified = false; 01782 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 01783 Function &F = *I; 01784 if (!F.isDeclaration()) 01785 continue; 01786 01787 if (!F.hasName()) 01788 continue; 01789 01790 const FunctionType *FTy = F.getFunctionType(); 01791 01792 StringRef Name = F.getName(); 01793 switch (Name[0]) { 01794 case 's': 01795 if (Name == "strlen") { 01796 if (FTy->getNumParams() != 1 || 01797 !isa<PointerType>(FTy->getParamType(0))) 01798 continue; 01799 setOnlyReadsMemory(F); 01800 setDoesNotThrow(F); 01801 setDoesNotCapture(F, 1); 01802 } else if (Name == "strcpy" || 01803 Name == "stpcpy" || 01804 Name == "strcat" || 01805 Name == "strtol" || 01806 Name == "strtod" || 01807 Name == "strtof" || 01808 Name == "strtoul" || 01809 Name == "strtoll" || 01810 Name == "strtold" || 01811 Name == "strncat" || 01812 Name == "strncpy" || 01813 Name == "strtoull") { 01814 if (FTy->getNumParams() < 2 || 01815 !isa<PointerType>(FTy->getParamType(1))) 01816 continue; 01817 setDoesNotThrow(F); 01818 setDoesNotCapture(F, 2); 01819 } else if (Name == "strxfrm") { 01820 if (FTy->getNumParams() != 3 || 01821 !isa<PointerType>(FTy->getParamType(0)) || 01822 !isa<PointerType>(FTy->getParamType(1))) 01823 continue; 01824 setDoesNotThrow(F); 01825 setDoesNotCapture(F, 1); 01826 setDoesNotCapture(F, 2); 01827 } else if (Name == "strcmp" || 01828 Name == "strspn" || 01829 Name == "strncmp" || 01830 Name ==" strcspn" || 01831 Name == "strcoll" || 01832 Name == "strcasecmp" || 01833 Name == "strncasecmp") { 01834 if (FTy->getNumParams() < 2 || 01835 !isa<PointerType>(FTy->getParamType(0)) || 01836 !isa<PointerType>(FTy->getParamType(1))) 01837 continue; 01838 setOnlyReadsMemory(F); 01839 setDoesNotThrow(F); 01840 setDoesNotCapture(F, 1); 01841 setDoesNotCapture(F, 2); 01842 } else if (Name == "strstr" || 01843 Name == "strpbrk") { 01844 if (FTy->getNumParams() != 2 || 01845 !isa<PointerType>(FTy->getParamType(1))) 01846 continue; 01847 setOnlyReadsMemory(F); 01848 setDoesNotThrow(F); 01849 setDoesNotCapture(F, 2); 01850 } else if (Name == "strtok" || 01851 Name == "strtok_r") { 01852 if (FTy->getNumParams() < 2 || 01853 !isa<PointerType>(FTy->getParamType(1))) 01854 continue; 01855 setDoesNotThrow(F); 01856 setDoesNotCapture(F, 2); 01857 } else if (Name == "scanf" || 01858 Name == "setbuf" || 01859 Name == "setvbuf") { 01860 if (FTy->getNumParams() < 1 || 01861 !isa<PointerType>(FTy->getParamType(0))) 01862 continue; 01863 setDoesNotThrow(F); 01864 setDoesNotCapture(F, 1); 01865 } else if (Name == "strdup" || 01866 Name == "strndup") { 01867 if (FTy->getNumParams() < 1 || 01868 !isa<PointerType>(FTy->getReturnType()) || 01869 !isa<PointerType>(FTy->getParamType(0))) 01870 continue; 01871 setDoesNotThrow(F); 01872 setDoesNotAlias(F, 0); 01873 setDoesNotCapture(F, 1); 01874 } else if (Name == "stat" || 01875 Name == "sscanf" || 01876 Name == "sprintf" || 01877 Name == "statvfs") { 01878 if (FTy->getNumParams() < 2 || 01879 !isa<PointerType>(FTy->getParamType(0)) || 01880 !isa<PointerType>(FTy->getParamType(1))) 01881 continue; 01882 setDoesNotThrow(F); 01883 setDoesNotCapture(F, 1); 01884 setDoesNotCapture(F, 2); 01885 } else if (Name == "snprintf") { 01886 if (FTy->getNumParams() != 3 || 01887 !isa<PointerType>(FTy->getParamType(0)) || 01888 !isa<PointerType>(FTy->getParamType(2))) 01889 continue; 01890 setDoesNotThrow(F); 01891 setDoesNotCapture(F, 1); 01892 setDoesNotCapture(F, 3); 01893 } else if (Name == "setitimer") { 01894 if (FTy->getNumParams() != 3 || 01895 !isa<PointerType>(FTy->getParamType(1)) || 01896 !isa<PointerType>(FTy->getParamType(2))) 01897 continue; 01898 setDoesNotThrow(F); 01899 setDoesNotCapture(F, 2); 01900 setDoesNotCapture(F, 3); 01901 } else if (Name == "system") { 01902 if (FTy->getNumParams() != 1 || 01903 !isa<PointerType>(FTy->getParamType(0))) 01904 continue; 01905 // May throw; "system" is a valid pthread cancellation point. 01906 setDoesNotCapture(F, 1); 01907 } 01908 break; 01909 case 'm': 01910 if (Name == "memcmp") { 01911 if (FTy->getNumParams() != 3 || 01912 !isa<PointerType>(FTy->getParamType(0)) || 01913 !isa<PointerType>(FTy->getParamType(1))) 01914 continue; 01915 setOnlyReadsMemory(F); 01916 setDoesNotThrow(F); 01917 setDoesNotCapture(F, 1); 01918 setDoesNotCapture(F, 2); 01919 } else if (Name == "memchr" || 01920 Name == "memrchr") { 01921 if (FTy->getNumParams() != 3) 01922 continue; 01923 setOnlyReadsMemory(F); 01924 setDoesNotThrow(F); 01925 } else if (Name == "modf" || 01926 Name == "modff" || 01927 Name == "modfl" || 01928 Name == "memcpy" || 01929 Name == "memccpy" || 01930 Name == "memmove") { 01931 if (FTy->getNumParams() < 2 || 01932 !isa<PointerType>(FTy->getParamType(1))) 01933 continue; 01934 setDoesNotThrow(F); 01935 setDoesNotCapture(F, 2); 01936 } else if (Name == "memalign") { 01937 if (!isa<PointerType>(FTy->getReturnType())) 01938 continue; 01939 setDoesNotAlias(F, 0); 01940 } else if (Name == "mkdir" || 01941 Name == "mktime") { 01942 if (FTy->getNumParams() == 0 || 01943 !isa<PointerType>(FTy->getParamType(0))) 01944 continue; 01945 setDoesNotThrow(F); 01946 setDoesNotCapture(F, 1); 01947 } 01948 break; 01949 case 'r': 01950 if (Name == "realloc") { 01951 if (FTy->getNumParams() != 2 || 01952 !isa<PointerType>(FTy->getParamType(0)) || 01953 !isa<PointerType>(FTy->getReturnType())) 01954 continue; 01955 setDoesNotThrow(F); 01956 setDoesNotAlias(F, 0); 01957 setDoesNotCapture(F, 1); 01958 } else if (Name == "read") { 01959 if (FTy->getNumParams() != 3 || 01960 !isa<PointerType>(FTy->getParamType(1))) 01961 continue; 01962 // May throw; "read" is a valid pthread cancellation point. 01963 setDoesNotCapture(F, 2); 01964 } else if (Name == "rmdir" || 01965 Name == "rewind" || 01966 Name == "remove" || 01967 Name == "realpath") { 01968 if (FTy->getNumParams() < 1 || 01969 !isa<PointerType>(FTy->getParamType(0))) 01970 continue; 01971 setDoesNotThrow(F); 01972 setDoesNotCapture(F, 1); 01973 } else if (Name == "rename" || 01974 Name == "readlink") { 01975 if (FTy->getNumParams() < 2 || 01976 !isa<PointerType>(FTy->getParamType(0)) || 01977 !isa<PointerType>(FTy->getParamType(1))) 01978 continue; 01979 setDoesNotThrow(F); 01980 setDoesNotCapture(F, 1); 01981 setDoesNotCapture(F, 2); 01982 } 01983 break; 01984 case 'w': 01985 if (Name == "write") { 01986 if (FTy->getNumParams() != 3 || 01987 !isa<PointerType>(FTy->getParamType(1))) 01988 continue; 01989 // May throw; "write" is a valid pthread cancellation point. 01990 setDoesNotCapture(F, 2); 01991 } 01992 break; 01993 case 'b': 01994 if (Name == "bcopy") { 01995 if (FTy->getNumParams() != 3 || 01996 !isa<PointerType>(FTy->getParamType(0)) || 01997 !isa<PointerType>(FTy->getParamType(1))) 01998 continue; 01999 setDoesNotThrow(F); 02000 setDoesNotCapture(F, 1); 02001 setDoesNotCapture(F, 2); 02002 } else if (Name == "bcmp") { 02003 if (FTy->getNumParams() != 3 || 02004 !isa<PointerType>(FTy->getParamType(0)) || 02005 !isa<PointerType>(FTy->getParamType(1))) 02006 continue; 02007 setDoesNotThrow(F); 02008 setOnlyReadsMemory(F); 02009 setDoesNotCapture(F, 1); 02010 setDoesNotCapture(F, 2); 02011 } else if (Name == "bzero") { 02012 if (FTy->getNumParams() != 2 || 02013 !isa<PointerType>(FTy->getParamType(0))) 02014 continue; 02015 setDoesNotThrow(F); 02016 setDoesNotCapture(F, 1); 02017 } 02018 break; 02019 case 'c': 02020 if (Name == "calloc") { 02021 if (FTy->getNumParams() != 2 || 02022 !isa<PointerType>(FTy->getReturnType())) 02023 continue; 02024 setDoesNotThrow(F); 02025 setDoesNotAlias(F, 0); 02026 } else if (Name == "chmod" || 02027 Name == "chown" || 02028 Name == "ctermid" || 02029 Name == "clearerr" || 02030 Name == "closedir") { 02031 if (FTy->getNumParams() == 0 || 02032 !isa<PointerType>(FTy->getParamType(0))) 02033 continue; 02034 setDoesNotThrow(F); 02035 setDoesNotCapture(F, 1); 02036 } 02037 break; 02038 case 'a': 02039 if (Name == "atoi" || 02040 Name == "atol" || 02041 Name == "atof" || 02042 Name == "atoll") { 02043 if (FTy->getNumParams() != 1 || 02044 !isa<PointerType>(FTy->getParamType(0))) 02045 continue; 02046 setDoesNotThrow(F); 02047 setOnlyReadsMemory(F); 02048 setDoesNotCapture(F, 1); 02049 } else if (Name == "access") { 02050 if (FTy->getNumParams() != 2 || 02051 !isa<PointerType>(FTy->getParamType(0))) 02052 continue; 02053 setDoesNotThrow(F); 02054 setDoesNotCapture(F, 1); 02055 } 02056 break; 02057 case 'f': 02058 if (Name == "fopen") { 02059 if (FTy->getNumParams() != 2 || 02060 !isa<PointerType>(FTy->getReturnType()) || 02061 !isa<PointerType>(FTy->getParamType(0)) || 02062 !isa<PointerType>(FTy->getParamType(1))) 02063 continue; 02064 setDoesNotThrow(F); 02065 setDoesNotAlias(F, 0); 02066 setDoesNotCapture(F, 1); 02067 setDoesNotCapture(F, 2); 02068 } else if (Name == "fdopen") { 02069 if (FTy->getNumParams() != 2 || 02070 !isa<PointerType>(FTy->getReturnType()) || 02071 !isa<PointerType>(FTy->getParamType(1))) 02072 continue; 02073 setDoesNotThrow(F); 02074 setDoesNotAlias(F, 0); 02075 setDoesNotCapture(F, 2); 02076 } else if (Name == "feof" || 02077 Name == "free" || 02078 Name == "fseek" || 02079 Name == "ftell" || 02080 Name == "fgetc" || 02081 Name == "fseeko" || 02082 Name == "ftello" || 02083 Name == "fileno" || 02084 Name == "fflush" || 02085 Name == "fclose" || 02086 Name == "fsetpos" || 02087 Name == "flockfile" || 02088 Name == "funlockfile" || 02089 Name == "ftrylockfile") { 02090 if (FTy->getNumParams() == 0 || 02091 !isa<PointerType>(FTy->getParamType(0))) 02092 continue; 02093 setDoesNotThrow(F); 02094 setDoesNotCapture(F, 1); 02095 } else if (Name == "ferror") { 02096 if (FTy->getNumParams() != 1 || 02097 !isa<PointerType>(FTy->getParamType(0))) 02098 continue; 02099 setDoesNotThrow(F); 02100 setDoesNotCapture(F, 1); 02101 setOnlyReadsMemory(F); 02102 } else if (Name == "fputc" || 02103 Name == "fstat" || 02104 Name == "frexp" || 02105 Name == "frexpf" || 02106 Name == "frexpl" || 02107 Name == "fstatvfs") { 02108 if (FTy->getNumParams() != 2 || 02109 !isa<PointerType>(FTy->getParamType(1))) 02110 continue; 02111 setDoesNotThrow(F); 02112 setDoesNotCapture(F, 2); 02113 } else if (Name == "fgets") { 02114 if (FTy->getNumParams() != 3 || 02115 !isa<PointerType>(FTy->getParamType(0)) || 02116 !isa<PointerType>(FTy->getParamType(2))) 02117 continue; 02118 setDoesNotThrow(F); 02119 setDoesNotCapture(F, 3); 02120 } else if (Name == "fread" || 02121 Name == "fwrite") { 02122 if (FTy->getNumParams() != 4 || 02123 !isa<PointerType>(FTy->getParamType(0)) || 02124 !isa<PointerType>(FTy->getParamType(3))) 02125 continue; 02126 setDoesNotThrow(F); 02127 setDoesNotCapture(F, 1); 02128 setDoesNotCapture(F, 4); 02129 } else if (Name == "fputs" || 02130 Name == "fscanf" || 02131 Name == "fprintf" || 02132 Name == "fgetpos") { 02133 if (FTy->getNumParams() < 2 || 02134 !isa<PointerType>(FTy->getParamType(0)) || 02135 !isa<PointerType>(FTy->getParamType(1))) 02136 continue; 02137 setDoesNotThrow(F); 02138 setDoesNotCapture(F, 1); 02139 setDoesNotCapture(F, 2); 02140 } 02141 break; 02142 case 'g': 02143 if (Name == "getc" || 02144 Name == "getlogin_r" || 02145 Name == "getc_unlocked") { 02146 if (FTy->getNumParams() == 0 || 02147 !isa<PointerType>(FTy->getParamType(0))) 02148 continue; 02149 setDoesNotThrow(F); 02150 setDoesNotCapture(F, 1); 02151 } else if (Name == "getenv") { 02152 if (FTy->getNumParams() != 1 || 02153 !isa<PointerType>(FTy->getParamType(0))) 02154 continue; 02155 setDoesNotThrow(F); 02156 setOnlyReadsMemory(F); 02157 setDoesNotCapture(F, 1); 02158 } else if (Name == "gets" || 02159 Name == "getchar") { 02160 setDoesNotThrow(F); 02161 } else if (Name == "getitimer") { 02162 if (FTy->getNumParams() != 2 || 02163 !isa<PointerType>(FTy->getParamType(1))) 02164 continue; 02165 setDoesNotThrow(F); 02166 setDoesNotCapture(F, 2); 02167 } else if (Name == "getpwnam") { 02168 if (FTy->getNumParams() != 1 || 02169 !isa<PointerType>(FTy->getParamType(0))) 02170 continue; 02171 setDoesNotThrow(F); 02172 setDoesNotCapture(F, 1); 02173 } 02174 break; 02175 case 'u': 02176 if (Name == "ungetc") { 02177 if (FTy->getNumParams() != 2 || 02178 !isa<PointerType>(FTy->getParamType(1))) 02179 continue; 02180 setDoesNotThrow(F); 02181 setDoesNotCapture(F, 2); 02182 } else if (Name == "uname" || 02183 Name == "unlink" || 02184 Name == "unsetenv") { 02185 if (FTy->getNumParams() != 1 || 02186 !isa<PointerType>(FTy->getParamType(0))) 02187 continue; 02188 setDoesNotThrow(F); 02189 setDoesNotCapture(F, 1); 02190 } else if (Name == "utime" || 02191 Name == "utimes") { 02192 if (FTy->getNumParams() != 2 || 02193 !isa<PointerType>(FTy->getParamType(0)) || 02194 !isa<PointerType>(FTy->getParamType(1))) 02195 continue; 02196 setDoesNotThrow(F); 02197 setDoesNotCapture(F, 1); 02198 setDoesNotCapture(F, 2); 02199 } 02200 break; 02201 case 'p': 02202 if (Name == "putc") { 02203 if (FTy->getNumParams() != 2 || 02204 !isa<PointerType>(FTy->getParamType(1))) 02205 continue; 02206 setDoesNotThrow(F); 02207 setDoesNotCapture(F, 2); 02208 } else if (Name == "puts" || 02209 Name == "printf" || 02210 Name == "perror") { 02211 if (FTy->getNumParams() != 1 || 02212 !isa<PointerType>(FTy->getParamType(0))) 02213 continue; 02214 setDoesNotThrow(F); 02215 setDoesNotCapture(F, 1); 02216 } else if (Name == "pread" || 02217 Name == "pwrite") { 02218 if (FTy->getNumParams() != 4 || 02219 !isa<PointerType>(FTy->getParamType(1))) 02220 continue; 02221 // May throw; these are valid pthread cancellation points. 02222 setDoesNotCapture(F, 2); 02223 } else if (Name == "putchar") { 02224 setDoesNotThrow(F); 02225 } else if (Name == "popen") { 02226 if (FTy->getNumParams() != 2 || 02227 !isa<PointerType>(FTy->getReturnType()) || 02228 !isa<PointerType>(FTy->getParamType(0)) || 02229 !isa<PointerType>(FTy->getParamType(1))) 02230 continue; 02231 setDoesNotThrow(F); 02232 setDoesNotAlias(F, 0); 02233 setDoesNotCapture(F, 1); 02234 setDoesNotCapture(F, 2); 02235 } else if (Name == "pclose") { 02236 if (FTy->getNumParams() != 1 || 02237 !isa<PointerType>(FTy->getParamType(0))) 02238 continue; 02239 setDoesNotThrow(F); 02240 setDoesNotCapture(F, 1); 02241 } 02242 break; 02243 case 'v': 02244 if (Name == "vscanf") { 02245 if (FTy->getNumParams() != 2 || 02246 !isa<PointerType>(FTy->getParamType(1))) 02247 continue; 02248 setDoesNotThrow(F); 02249 setDoesNotCapture(F, 1); 02250 } else if (Name == "vsscanf" || 02251 Name == "vfscanf") { 02252 if (FTy->getNumParams() != 3 || 02253 !isa<PointerType>(FTy->getParamType(1)) || 02254 !isa<PointerType>(FTy->getParamType(2))) 02255 continue; 02256 setDoesNotThrow(F); 02257 setDoesNotCapture(F, 1); 02258 setDoesNotCapture(F, 2); 02259 } else if (Name == "valloc") { 02260 if (!isa<PointerType>(FTy->getReturnType())) 02261 continue; 02262 setDoesNotThrow(F); 02263 setDoesNotAlias(F, 0); 02264 } else if (Name == "vprintf") { 02265 if (FTy->getNumParams() != 2 || 02266 !isa<PointerType>(FTy->getParamType(0))) 02267 continue; 02268 setDoesNotThrow(F); 02269 setDoesNotCapture(F, 1); 02270 } else if (Name == "vfprintf" || 02271 Name == "vsprintf") { 02272 if (FTy->getNumParams() != 3 || 02273 !isa<PointerType>(FTy->getParamType(0)) || 02274 !isa<PointerType>(FTy->getParamType(1))) 02275 continue; 02276 setDoesNotThrow(F); 02277 setDoesNotCapture(F, 1); 02278 setDoesNotCapture(F, 2); 02279 } else if (Name == "vsnprintf") { 02280 if (FTy->getNumParams() != 4 || 02281 !isa<PointerType>(FTy->getParamType(0)) || 02282 !isa<PointerType>(FTy->getParamType(2))) 02283 continue; 02284 setDoesNotThrow(F); 02285 setDoesNotCapture(F, 1); 02286 setDoesNotCapture(F, 3); 02287 } 02288 break; 02289 case 'o': 02290 if (Name == "open") { 02291 if (FTy->getNumParams() < 2 || 02292 !isa<PointerType>(FTy->getParamType(0))) 02293 continue; 02294 // May throw; "open" is a valid pthread cancellation point. 02295 setDoesNotCapture(F, 1); 02296 } else if (Name == "opendir") { 02297 if (FTy->getNumParams() != 1 || 02298 !isa<PointerType>(FTy->getReturnType()) || 02299 !isa<PointerType>(FTy->getParamType(0))) 02300 continue; 02301 setDoesNotThrow(F); 02302 setDoesNotAlias(F, 0); 02303 setDoesNotCapture(F, 1); 02304 } 02305 break; 02306 case 't': 02307 if (Name == "tmpfile") { 02308 if (!isa<PointerType>(FTy->getReturnType())) 02309 continue; 02310 setDoesNotThrow(F); 02311 setDoesNotAlias(F, 0); 02312 } else if (Name == "times") { 02313 if (FTy->getNumParams() != 1 || 02314 !isa<PointerType>(FTy->getParamType(0))) 02315 continue; 02316 setDoesNotThrow(F); 02317 setDoesNotCapture(F, 1); 02318 } 02319 break; 02320 case 'h': 02321 if (Name == "htonl" || 02322 Name == "htons") { 02323 setDoesNotThrow(F); 02324 setDoesNotAccessMemory(F); 02325 } 02326 break; 02327 case 'n': 02328 if (Name == "ntohl" || 02329 Name == "ntohs") { 02330 setDoesNotThrow(F); 02331 setDoesNotAccessMemory(F); 02332 } 02333 break; 02334 case 'l': 02335 if (Name == "lstat") { 02336 if (FTy->getNumParams() != 2 || 02337 !isa<PointerType>(FTy->getParamType(0)) || 02338 !isa<PointerType>(FTy->getParamType(1))) 02339 continue; 02340 setDoesNotThrow(F); 02341 setDoesNotCapture(F, 1); 02342 setDoesNotCapture(F, 2); 02343 } else if (Name == "lchown") { 02344 if (FTy->getNumParams() != 3 || 02345 !isa<PointerType>(FTy->getParamType(0))) 02346 continue; 02347 setDoesNotThrow(F); 02348 setDoesNotCapture(F, 1); 02349 } 02350 break; 02351 case 'q': 02352 if (Name == "qsort") { 02353 if (FTy->getNumParams() != 4 || 02354 !isa<PointerType>(FTy->getParamType(3))) 02355 continue; 02356 // May throw; places call through function pointer. 02357 setDoesNotCapture(F, 4); 02358 } 02359 break; 02360 case '_': 02361 if (Name == "__strdup" || 02362 Name == "__strndup") { 02363 if (FTy->getNumParams() < 1 || 02364 !isa<PointerType>(FTy->getReturnType()) || 02365 !isa<PointerType>(FTy->getParamType(0))) 02366 continue; 02367 setDoesNotThrow(F); 02368 setDoesNotAlias(F, 0); 02369 setDoesNotCapture(F, 1); 02370 } else if (Name == "__strtok_r") { 02371 if (FTy->getNumParams() != 3 || 02372 !isa<PointerType>(FTy->getParamType(1))) 02373 continue; 02374 setDoesNotThrow(F); 02375 setDoesNotCapture(F, 2); 02376 } else if (Name == "_IO_getc") { 02377 if (FTy->getNumParams() != 1 || 02378 !isa<PointerType>(FTy->getParamType(0))) 02379 continue; 02380 setDoesNotThrow(F); 02381 setDoesNotCapture(F, 1); 02382 } else if (Name == "_IO_putc") { 02383 if (FTy->getNumParams() != 2 || 02384 !isa<PointerType>(FTy->getParamType(1))) 02385 continue; 02386 setDoesNotThrow(F); 02387 setDoesNotCapture(F, 2); 02388 } 02389 break; 02390 case 1: 02391 if (Name == "\1__isoc99_scanf") { 02392 if (FTy->getNumParams() < 1 || 02393 !isa<PointerType>(FTy->getParamType(0))) 02394 continue; 02395 setDoesNotThrow(F); 02396 setDoesNotCapture(F, 1); 02397 } else if (Name == "\1stat64" || 02398 Name == "\1lstat64" || 02399 Name == "\1statvfs64" || 02400 Name == "\1__isoc99_sscanf") { 02401 if (FTy->getNumParams() < 1 || 02402 !isa<PointerType>(FTy->getParamType(0)) || 02403 !isa<PointerType>(FTy->getParamType(1))) 02404 continue; 02405 setDoesNotThrow(F); 02406 setDoesNotCapture(F, 1); 02407 setDoesNotCapture(F, 2); 02408 } else if (Name == "\1fopen64") { 02409 if (FTy->getNumParams() != 2 || 02410 !isa<PointerType>(FTy->getReturnType()) || 02411 !isa<PointerType>(FTy->getParamType(0)) || 02412 !isa<PointerType>(FTy->getParamType(1))) 02413 continue; 02414 setDoesNotThrow(F); 02415 setDoesNotAlias(F, 0); 02416 setDoesNotCapture(F, 1); 02417 setDoesNotCapture(F, 2); 02418 } else if (Name == "\1fseeko64" || 02419 Name == "\1ftello64") { 02420 if (FTy->getNumParams() == 0 || 02421 !isa<PointerType>(FTy->getParamType(0))) 02422 continue; 02423 setDoesNotThrow(F); 02424 setDoesNotCapture(F, 1); 02425 } else if (Name == "\1tmpfile64") { 02426 if (!isa<PointerType>(FTy->getReturnType())) 02427 continue; 02428 setDoesNotThrow(F); 02429 setDoesNotAlias(F, 0); 02430 } else if (Name == "\1fstat64" || 02431 Name == "\1fstatvfs64") { 02432 if (FTy->getNumParams() != 2 || 02433 !isa<PointerType>(FTy->getParamType(1))) 02434 continue; 02435 setDoesNotThrow(F); 02436 setDoesNotCapture(F, 2); 02437 } else if (Name == "\1open64") { 02438 if (FTy->getNumParams() < 2 || 02439 !isa<PointerType>(FTy->getParamType(0))) 02440 continue; 02441 // May throw; "open" is a valid pthread cancellation point. 02442 setDoesNotCapture(F, 1); 02443 } 02444 break; 02445 } 02446 } 02447 return Modified; 02448 } 02449 02450 // TODO: 02451 // Additional cases that we need to add to this file: 02452 // 02453 // cbrt: 02454 // * cbrt(expN(X)) -> expN(x/3) 02455 // * cbrt(sqrt(x)) -> pow(x,1/6) 02456 // * cbrt(sqrt(x)) -> pow(x,1/9) 02457 // 02458 // cos, cosf, cosl: 02459 // * cos(-x) -> cos(x) 02460 // 02461 // exp, expf, expl: 02462 // * exp(log(x)) -> x 02463 // 02464 // log, logf, logl: 02465 // * log(exp(x)) -> x 02466 // * log(x**y) -> y*log(x) 02467 // * log(exp(y)) -> y*log(e) 02468 // * log(exp2(y)) -> y*log(2) 02469 // * log(exp10(y)) -> y*log(10) 02470 // * log(sqrt(x)) -> 0.5*log(x) 02471 // * log(pow(x,y)) -> y*log(x) 02472 // 02473 // lround, lroundf, lroundl: 02474 // * lround(cnst) -> cnst' 02475 // 02476 // memcmp: 02477 // * memcmp(x,y,l) -> cnst 02478 // (if all arguments are constant and strlen(x) <= l and strlen(y) <= l) 02479 // 02480 // pow, powf, powl: 02481 // * pow(exp(x),y) -> exp(x*y) 02482 // * pow(sqrt(x),y) -> pow(x,y*0.5) 02483 // * pow(pow(x,y),z)-> pow(x,y*z) 02484 // 02485 // puts: 02486 // * puts("") -> putchar("\n") 02487 // 02488 // round, roundf, roundl: 02489 // * round(cnst) -> cnst' 02490 // 02491 // signbit: 02492 // * signbit(cnst) -> cnst' 02493 // * signbit(nncst) -> 0 (if pstv is a non-negative constant) 02494 // 02495 // sqrt, sqrtf, sqrtl: 02496 // * sqrt(expN(x)) -> expN(x*0.5) 02497 // * sqrt(Nroot(x)) -> pow(x,1/(2*N)) 02498 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5) 02499 // 02500 // stpcpy: 02501 // * stpcpy(str, "literal") -> 02502 // llvm.memcpy(str,"literal",strlen("literal")+1,1) 02503 // strrchr: 02504 // * strrchr(s,c) -> reverse_offset_of_in(c,s) 02505 // (if c is a constant integer and s is a constant string) 02506 // * strrchr(s1,0) -> strchr(s1,0) 02507 // 02508 // strpbrk: 02509 // * strpbrk(s,a) -> offset_in_for(s,a) 02510 // (if s and a are both constant strings) 02511 // * strpbrk(s,"") -> 0 02512 // * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1) 02513 // 02514 // strspn, strcspn: 02515 // * strspn(s,a) -> const_int (if both args are constant) 02516 // * strspn("",a) -> 0 02517 // * strspn(s,"") -> 0 02518 // * strcspn(s,a) -> const_int (if both args are constant) 02519 // * strcspn("",a) -> 0 02520 // * strcspn(s,"") -> strlen(a) 02521 // 02522 // strstr: 02523 // * strstr(x,x) -> x 02524 // * strstr(s1,s2) -> offset_of_s2_in(s1) 02525 // (if s1 and s2 are constant strings) 02526 // 02527 // tan, tanf, tanl: 02528 // * tan(atan(x)) -> x 02529 // 02530 // trunc, truncf, truncl: 02531 // * trunc(cnst) -> cnst' 02532 // 02533 //