1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the library calls simplifier. It does not implement 10 // any pass, but can't be used by other passes to do simplifications. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Utils/SimplifyLibCalls.h" 15 #include "llvm/ADT/APSInt.h" 16 #include "llvm/ADT/SmallString.h" 17 #include "llvm/ADT/StringMap.h" 18 #include "llvm/ADT/Triple.h" 19 #include "llvm/Analysis/BlockFrequencyInfo.h" 20 #include "llvm/Analysis/ConstantFolding.h" 21 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 22 #include "llvm/Analysis/ProfileSummaryInfo.h" 23 #include "llvm/Transforms/Utils/Local.h" 24 #include "llvm/Analysis/ValueTracking.h" 25 #include "llvm/Analysis/CaptureTracking.h" 26 #include "llvm/Analysis/Loads.h" 27 #include "llvm/IR/DataLayout.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/IR/IRBuilder.h" 30 #include "llvm/IR/IntrinsicInst.h" 31 #include "llvm/IR/Intrinsics.h" 32 #include "llvm/IR/LLVMContext.h" 33 #include "llvm/IR/Module.h" 34 #include "llvm/IR/PatternMatch.h" 35 #include "llvm/Support/CommandLine.h" 36 #include "llvm/Support/KnownBits.h" 37 #include "llvm/Support/MathExtras.h" 38 #include "llvm/Transforms/Utils/BuildLibCalls.h" 39 #include "llvm/Transforms/Utils/SizeOpts.h" 40 41 using namespace llvm; 42 using namespace PatternMatch; 43 44 static cl::opt<bool> 45 EnableUnsafeFPShrink("enable-double-float-shrink", cl::Hidden, 46 cl::init(false), 47 cl::desc("Enable unsafe double to float " 48 "shrinking for math lib calls")); 49 50 //===----------------------------------------------------------------------===// 51 // Helper Functions 52 //===----------------------------------------------------------------------===// 53 54 static bool ignoreCallingConv(LibFunc Func) { 55 return Func == LibFunc_abs || Func == LibFunc_labs || 56 Func == LibFunc_llabs || Func == LibFunc_strlen; 57 } 58 59 /// Return true if it is only used in equality comparisons with With. 60 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) { 61 for (User *U : V->users()) { 62 if (ICmpInst *IC = dyn_cast<ICmpInst>(U)) 63 if (IC->isEquality() && IC->getOperand(1) == With) 64 continue; 65 // Unknown instruction. 66 return false; 67 } 68 return true; 69 } 70 71 static bool callHasFloatingPointArgument(const CallInst *CI) { 72 return any_of(CI->operands(), [](const Use &OI) { 73 return OI->getType()->isFloatingPointTy(); 74 }); 75 } 76 77 static bool callHasFP128Argument(const CallInst *CI) { 78 return any_of(CI->operands(), [](const Use &OI) { 79 return OI->getType()->isFP128Ty(); 80 }); 81 } 82 83 static Value *convertStrToNumber(CallInst *CI, StringRef &Str, int64_t Base) { 84 if (Base < 2 || Base > 36) 85 // handle special zero base 86 if (Base != 0) 87 return nullptr; 88 89 char *End; 90 std::string nptr = Str.str(); 91 errno = 0; 92 long long int Result = strtoll(nptr.c_str(), &End, Base); 93 if (errno) 94 return nullptr; 95 96 // if we assume all possible target locales are ASCII supersets, 97 // then if strtoll successfully parses a number on the host, 98 // it will also successfully parse the same way on the target 99 if (*End != '\0') 100 return nullptr; 101 102 if (!isIntN(CI->getType()->getPrimitiveSizeInBits(), Result)) 103 return nullptr; 104 105 return ConstantInt::get(CI->getType(), Result); 106 } 107 108 static bool isOnlyUsedInComparisonWithZero(Value *V) { 109 for (User *U : V->users()) { 110 if (ICmpInst *IC = dyn_cast<ICmpInst>(U)) 111 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1))) 112 if (C->isNullValue()) 113 continue; 114 // Unknown instruction. 115 return false; 116 } 117 return true; 118 } 119 120 static bool canTransformToMemCmp(CallInst *CI, Value *Str, uint64_t Len, 121 const DataLayout &DL) { 122 if (!isOnlyUsedInComparisonWithZero(CI)) 123 return false; 124 125 if (!isDereferenceableAndAlignedPointer(Str, Align(1), APInt(64, Len), DL)) 126 return false; 127 128 if (CI->getFunction()->hasFnAttribute(Attribute::SanitizeMemory)) 129 return false; 130 131 return true; 132 } 133 134 static void annotateDereferenceableBytes(CallInst *CI, 135 ArrayRef<unsigned> ArgNos, 136 uint64_t DereferenceableBytes) { 137 const Function *F = CI->getCaller(); 138 if (!F) 139 return; 140 for (unsigned ArgNo : ArgNos) { 141 uint64_t DerefBytes = DereferenceableBytes; 142 unsigned AS = CI->getArgOperand(ArgNo)->getType()->getPointerAddressSpace(); 143 if (!llvm::NullPointerIsDefined(F, AS) || 144 CI->paramHasAttr(ArgNo, Attribute::NonNull)) 145 DerefBytes = std::max(CI->getParamDereferenceableOrNullBytes(ArgNo), 146 DereferenceableBytes); 147 148 if (CI->getParamDereferenceableBytes(ArgNo) < DerefBytes) { 149 CI->removeParamAttr(ArgNo, Attribute::Dereferenceable); 150 if (!llvm::NullPointerIsDefined(F, AS) || 151 CI->paramHasAttr(ArgNo, Attribute::NonNull)) 152 CI->removeParamAttr(ArgNo, Attribute::DereferenceableOrNull); 153 CI->addParamAttr(ArgNo, Attribute::getWithDereferenceableBytes( 154 CI->getContext(), DerefBytes)); 155 } 156 } 157 } 158 159 static void annotateNonNullNoUndefBasedOnAccess(CallInst *CI, 160 ArrayRef<unsigned> ArgNos) { 161 Function *F = CI->getCaller(); 162 if (!F) 163 return; 164 165 for (unsigned ArgNo : ArgNos) { 166 if (!CI->paramHasAttr(ArgNo, Attribute::NoUndef)) 167 CI->addParamAttr(ArgNo, Attribute::NoUndef); 168 169 if (CI->paramHasAttr(ArgNo, Attribute::NonNull)) 170 continue; 171 unsigned AS = CI->getArgOperand(ArgNo)->getType()->getPointerAddressSpace(); 172 if (llvm::NullPointerIsDefined(F, AS)) 173 continue; 174 175 CI->addParamAttr(ArgNo, Attribute::NonNull); 176 annotateDereferenceableBytes(CI, ArgNo, 1); 177 } 178 } 179 180 static void annotateNonNullAndDereferenceable(CallInst *CI, ArrayRef<unsigned> ArgNos, 181 Value *Size, const DataLayout &DL) { 182 if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) { 183 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos); 184 annotateDereferenceableBytes(CI, ArgNos, LenC->getZExtValue()); 185 } else if (isKnownNonZero(Size, DL)) { 186 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos); 187 const APInt *X, *Y; 188 uint64_t DerefMin = 1; 189 if (match(Size, m_Select(m_Value(), m_APInt(X), m_APInt(Y)))) { 190 DerefMin = std::min(X->getZExtValue(), Y->getZExtValue()); 191 annotateDereferenceableBytes(CI, ArgNos, DerefMin); 192 } 193 } 194 } 195 196 // Copy CallInst "flags" like musttail, notail, and tail. Return New param for 197 // easier chaining. Calls to emit* and B.createCall should probably be wrapped 198 // in this function when New is created to replace Old. Callers should take 199 // care to check Old.isMustTailCall() if they aren't replacing Old directly 200 // with New. 201 static Value *copyFlags(const CallInst &Old, Value *New) { 202 assert(!Old.isMustTailCall() && "do not copy musttail call flags"); 203 assert(!Old.isNoTailCall() && "do not copy notail call flags"); 204 if (auto *NewCI = dyn_cast_or_null<CallInst>(New)) 205 NewCI->setTailCallKind(Old.getTailCallKind()); 206 return New; 207 } 208 209 //===----------------------------------------------------------------------===// 210 // String and Memory Library Call Optimizations 211 //===----------------------------------------------------------------------===// 212 213 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilderBase &B) { 214 // Extract some information from the instruction 215 Value *Dst = CI->getArgOperand(0); 216 Value *Src = CI->getArgOperand(1); 217 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 218 219 // See if we can get the length of the input string. 220 uint64_t Len = GetStringLength(Src); 221 if (Len) 222 annotateDereferenceableBytes(CI, 1, Len); 223 else 224 return nullptr; 225 --Len; // Unbias length. 226 227 // Handle the simple, do-nothing case: strcat(x, "") -> x 228 if (Len == 0) 229 return Dst; 230 231 return copyFlags(*CI, emitStrLenMemCpy(Src, Dst, Len, B)); 232 } 233 234 Value *LibCallSimplifier::emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, 235 IRBuilderBase &B) { 236 // We need to find the end of the destination string. That's where the 237 // memory is to be moved to. We just generate a call to strlen. 238 Value *DstLen = emitStrLen(Dst, B, DL, TLI); 239 if (!DstLen) 240 return nullptr; 241 242 // Now that we have the destination's length, we must index into the 243 // destination's pointer to get the actual memcpy destination (end of 244 // the string .. we're concatenating). 245 Value *CpyDst = B.CreateGEP(B.getInt8Ty(), Dst, DstLen, "endptr"); 246 247 // We have enough information to now generate the memcpy call to do the 248 // concatenation for us. Make a memcpy to copy the nul byte with align = 1. 249 B.CreateMemCpy( 250 CpyDst, Align(1), Src, Align(1), 251 ConstantInt::get(DL.getIntPtrType(Src->getContext()), Len + 1)); 252 return Dst; 253 } 254 255 Value *LibCallSimplifier::optimizeStrNCat(CallInst *CI, IRBuilderBase &B) { 256 // Extract some information from the instruction. 257 Value *Dst = CI->getArgOperand(0); 258 Value *Src = CI->getArgOperand(1); 259 Value *Size = CI->getArgOperand(2); 260 uint64_t Len; 261 annotateNonNullNoUndefBasedOnAccess(CI, 0); 262 if (isKnownNonZero(Size, DL)) 263 annotateNonNullNoUndefBasedOnAccess(CI, 1); 264 265 // We don't do anything if length is not constant. 266 ConstantInt *LengthArg = dyn_cast<ConstantInt>(Size); 267 if (LengthArg) { 268 Len = LengthArg->getZExtValue(); 269 // strncat(x, c, 0) -> x 270 if (!Len) 271 return Dst; 272 } else { 273 return nullptr; 274 } 275 276 // See if we can get the length of the input string. 277 uint64_t SrcLen = GetStringLength(Src); 278 if (SrcLen) { 279 annotateDereferenceableBytes(CI, 1, SrcLen); 280 --SrcLen; // Unbias length. 281 } else { 282 return nullptr; 283 } 284 285 // strncat(x, "", c) -> x 286 if (SrcLen == 0) 287 return Dst; 288 289 // We don't optimize this case. 290 if (Len < SrcLen) 291 return nullptr; 292 293 // strncat(x, s, c) -> strcat(x, s) 294 // s is constant so the strcat can be optimized further. 295 return copyFlags(*CI, emitStrLenMemCpy(Src, Dst, SrcLen, B)); 296 } 297 298 Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilderBase &B) { 299 Function *Callee = CI->getCalledFunction(); 300 FunctionType *FT = Callee->getFunctionType(); 301 Value *SrcStr = CI->getArgOperand(0); 302 annotateNonNullNoUndefBasedOnAccess(CI, 0); 303 304 // If the second operand is non-constant, see if we can compute the length 305 // of the input string and turn this into memchr. 306 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 307 if (!CharC) { 308 uint64_t Len = GetStringLength(SrcStr); 309 if (Len) 310 annotateDereferenceableBytes(CI, 0, Len); 311 else 312 return nullptr; 313 if (!FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32. 314 return nullptr; 315 316 return copyFlags( 317 *CI, 318 emitMemChr(SrcStr, CI->getArgOperand(1), // include nul. 319 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len), B, 320 DL, TLI)); 321 } 322 323 // Otherwise, the character is a constant, see if the first argument is 324 // a string literal. If so, we can constant fold. 325 StringRef Str; 326 if (!getConstantStringInfo(SrcStr, Str)) { 327 if (CharC->isZero()) // strchr(p, 0) -> p + strlen(p) 328 if (Value *StrLen = emitStrLen(SrcStr, B, DL, TLI)) 329 return B.CreateGEP(B.getInt8Ty(), SrcStr, StrLen, "strchr"); 330 return nullptr; 331 } 332 333 // Compute the offset, make sure to handle the case when we're searching for 334 // zero (a weird way to spell strlen). 335 size_t I = (0xFF & CharC->getSExtValue()) == 0 336 ? Str.size() 337 : Str.find(CharC->getSExtValue()); 338 if (I == StringRef::npos) // Didn't find the char. strchr returns null. 339 return Constant::getNullValue(CI->getType()); 340 341 // strchr(s+n,c) -> gep(s+n+i,c) 342 return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strchr"); 343 } 344 345 Value *LibCallSimplifier::optimizeStrRChr(CallInst *CI, IRBuilderBase &B) { 346 Value *SrcStr = CI->getArgOperand(0); 347 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 348 annotateNonNullNoUndefBasedOnAccess(CI, 0); 349 350 // Cannot fold anything if we're not looking for a constant. 351 if (!CharC) 352 return nullptr; 353 354 StringRef Str; 355 if (!getConstantStringInfo(SrcStr, Str)) { 356 // strrchr(s, 0) -> strchr(s, 0) 357 if (CharC->isZero()) 358 return copyFlags(*CI, emitStrChr(SrcStr, '\0', B, TLI)); 359 return nullptr; 360 } 361 362 // Compute the offset. 363 size_t I = (0xFF & CharC->getSExtValue()) == 0 364 ? Str.size() 365 : Str.rfind(CharC->getSExtValue()); 366 if (I == StringRef::npos) // Didn't find the char. Return null. 367 return Constant::getNullValue(CI->getType()); 368 369 // strrchr(s+n,c) -> gep(s+n+i,c) 370 return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strrchr"); 371 } 372 373 Value *LibCallSimplifier::optimizeStrCmp(CallInst *CI, IRBuilderBase &B) { 374 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1); 375 if (Str1P == Str2P) // strcmp(x,x) -> 0 376 return ConstantInt::get(CI->getType(), 0); 377 378 StringRef Str1, Str2; 379 bool HasStr1 = getConstantStringInfo(Str1P, Str1); 380 bool HasStr2 = getConstantStringInfo(Str2P, Str2); 381 382 // strcmp(x, y) -> cnst (if both x and y are constant strings) 383 if (HasStr1 && HasStr2) 384 return ConstantInt::get(CI->getType(), Str1.compare(Str2)); 385 386 if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x 387 return B.CreateNeg(B.CreateZExt( 388 B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType())); 389 390 if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x 391 return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"), 392 CI->getType()); 393 394 // strcmp(P, "x") -> memcmp(P, "x", 2) 395 uint64_t Len1 = GetStringLength(Str1P); 396 if (Len1) 397 annotateDereferenceableBytes(CI, 0, Len1); 398 uint64_t Len2 = GetStringLength(Str2P); 399 if (Len2) 400 annotateDereferenceableBytes(CI, 1, Len2); 401 402 if (Len1 && Len2) { 403 return copyFlags( 404 *CI, emitMemCmp(Str1P, Str2P, 405 ConstantInt::get(DL.getIntPtrType(CI->getContext()), 406 std::min(Len1, Len2)), 407 B, DL, TLI)); 408 } 409 410 // strcmp to memcmp 411 if (!HasStr1 && HasStr2) { 412 if (canTransformToMemCmp(CI, Str1P, Len2, DL)) 413 return copyFlags( 414 *CI, 415 emitMemCmp(Str1P, Str2P, 416 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len2), 417 B, DL, TLI)); 418 } else if (HasStr1 && !HasStr2) { 419 if (canTransformToMemCmp(CI, Str2P, Len1, DL)) 420 return copyFlags( 421 *CI, 422 emitMemCmp(Str1P, Str2P, 423 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len1), 424 B, DL, TLI)); 425 } 426 427 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 428 return nullptr; 429 } 430 431 Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilderBase &B) { 432 Value *Str1P = CI->getArgOperand(0); 433 Value *Str2P = CI->getArgOperand(1); 434 Value *Size = CI->getArgOperand(2); 435 if (Str1P == Str2P) // strncmp(x,x,n) -> 0 436 return ConstantInt::get(CI->getType(), 0); 437 438 if (isKnownNonZero(Size, DL)) 439 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 440 // Get the length argument if it is constant. 441 uint64_t Length; 442 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(Size)) 443 Length = LengthArg->getZExtValue(); 444 else 445 return nullptr; 446 447 if (Length == 0) // strncmp(x,y,0) -> 0 448 return ConstantInt::get(CI->getType(), 0); 449 450 if (Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1) 451 return copyFlags(*CI, emitMemCmp(Str1P, Str2P, Size, B, DL, TLI)); 452 453 StringRef Str1, Str2; 454 bool HasStr1 = getConstantStringInfo(Str1P, Str1); 455 bool HasStr2 = getConstantStringInfo(Str2P, Str2); 456 457 // strncmp(x, y) -> cnst (if both x and y are constant strings) 458 if (HasStr1 && HasStr2) { 459 StringRef SubStr1 = Str1.substr(0, Length); 460 StringRef SubStr2 = Str2.substr(0, Length); 461 return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2)); 462 } 463 464 if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x 465 return B.CreateNeg(B.CreateZExt( 466 B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType())); 467 468 if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x 469 return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"), 470 CI->getType()); 471 472 uint64_t Len1 = GetStringLength(Str1P); 473 if (Len1) 474 annotateDereferenceableBytes(CI, 0, Len1); 475 uint64_t Len2 = GetStringLength(Str2P); 476 if (Len2) 477 annotateDereferenceableBytes(CI, 1, Len2); 478 479 // strncmp to memcmp 480 if (!HasStr1 && HasStr2) { 481 Len2 = std::min(Len2, Length); 482 if (canTransformToMemCmp(CI, Str1P, Len2, DL)) 483 return copyFlags( 484 *CI, 485 emitMemCmp(Str1P, Str2P, 486 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len2), 487 B, DL, TLI)); 488 } else if (HasStr1 && !HasStr2) { 489 Len1 = std::min(Len1, Length); 490 if (canTransformToMemCmp(CI, Str2P, Len1, DL)) 491 return copyFlags( 492 *CI, 493 emitMemCmp(Str1P, Str2P, 494 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len1), 495 B, DL, TLI)); 496 } 497 498 return nullptr; 499 } 500 501 Value *LibCallSimplifier::optimizeStrNDup(CallInst *CI, IRBuilderBase &B) { 502 Value *Src = CI->getArgOperand(0); 503 ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 504 uint64_t SrcLen = GetStringLength(Src); 505 if (SrcLen && Size) { 506 annotateDereferenceableBytes(CI, 0, SrcLen); 507 if (SrcLen <= Size->getZExtValue() + 1) 508 return copyFlags(*CI, emitStrDup(Src, B, TLI)); 509 } 510 511 return nullptr; 512 } 513 514 Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilderBase &B) { 515 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1); 516 if (Dst == Src) // strcpy(x,x) -> x 517 return Src; 518 519 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 520 // See if we can get the length of the input string. 521 uint64_t Len = GetStringLength(Src); 522 if (Len) 523 annotateDereferenceableBytes(CI, 1, Len); 524 else 525 return nullptr; 526 527 // We have enough information to now generate the memcpy call to do the 528 // copy for us. Make a memcpy to copy the nul byte with align = 1. 529 CallInst *NewCI = 530 B.CreateMemCpy(Dst, Align(1), Src, Align(1), 531 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len)); 532 NewCI->setAttributes(CI->getAttributes()); 533 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 534 copyFlags(*CI, NewCI); 535 return Dst; 536 } 537 538 Value *LibCallSimplifier::optimizeStpCpy(CallInst *CI, IRBuilderBase &B) { 539 Function *Callee = CI->getCalledFunction(); 540 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1); 541 542 // stpcpy(d,s) -> strcpy(d,s) if the result is not used. 543 if (CI->use_empty()) 544 return copyFlags(*CI, emitStrCpy(Dst, Src, B, TLI)); 545 546 if (Dst == Src) { // stpcpy(x,x) -> x+strlen(x) 547 Value *StrLen = emitStrLen(Src, B, DL, TLI); 548 return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr; 549 } 550 551 // See if we can get the length of the input string. 552 uint64_t Len = GetStringLength(Src); 553 if (Len) 554 annotateDereferenceableBytes(CI, 1, Len); 555 else 556 return nullptr; 557 558 Type *PT = Callee->getFunctionType()->getParamType(0); 559 Value *LenV = ConstantInt::get(DL.getIntPtrType(PT), Len); 560 Value *DstEnd = B.CreateGEP(B.getInt8Ty(), Dst, 561 ConstantInt::get(DL.getIntPtrType(PT), Len - 1)); 562 563 // We have enough information to now generate the memcpy call to do the 564 // copy for us. Make a memcpy to copy the nul byte with align = 1. 565 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1), LenV); 566 NewCI->setAttributes(CI->getAttributes()); 567 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 568 copyFlags(*CI, NewCI); 569 return DstEnd; 570 } 571 572 Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilderBase &B) { 573 Function *Callee = CI->getCalledFunction(); 574 Value *Dst = CI->getArgOperand(0); 575 Value *Src = CI->getArgOperand(1); 576 Value *Size = CI->getArgOperand(2); 577 annotateNonNullNoUndefBasedOnAccess(CI, 0); 578 if (isKnownNonZero(Size, DL)) 579 annotateNonNullNoUndefBasedOnAccess(CI, 1); 580 581 uint64_t Len; 582 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(Size)) 583 Len = LengthArg->getZExtValue(); 584 else 585 return nullptr; 586 587 // strncpy(x, y, 0) -> x 588 if (Len == 0) 589 return Dst; 590 591 // See if we can get the length of the input string. 592 uint64_t SrcLen = GetStringLength(Src); 593 if (SrcLen) { 594 annotateDereferenceableBytes(CI, 1, SrcLen); 595 --SrcLen; // Unbias length. 596 } else { 597 return nullptr; 598 } 599 600 if (SrcLen == 0) { 601 // strncpy(x, "", y) -> memset(x, '\0', y) 602 Align MemSetAlign = 603 CI->getAttributes().getParamAttrs(0).getAlignment().valueOrOne(); 604 CallInst *NewCI = B.CreateMemSet(Dst, B.getInt8('\0'), Size, MemSetAlign); 605 AttrBuilder ArgAttrs(CI->getContext(), CI->getAttributes().getParamAttrs(0)); 606 NewCI->setAttributes(NewCI->getAttributes().addParamAttributes( 607 CI->getContext(), 0, ArgAttrs)); 608 copyFlags(*CI, NewCI); 609 return Dst; 610 } 611 612 // strncpy(a, "a", 4) - > memcpy(a, "a\0\0\0", 4) 613 if (Len > SrcLen + 1) { 614 if (Len <= 128) { 615 StringRef Str; 616 if (!getConstantStringInfo(Src, Str)) 617 return nullptr; 618 std::string SrcStr = Str.str(); 619 SrcStr.resize(Len, '\0'); 620 Src = B.CreateGlobalString(SrcStr, "str"); 621 } else { 622 return nullptr; 623 } 624 } 625 626 Type *PT = Callee->getFunctionType()->getParamType(0); 627 // strncpy(x, s, c) -> memcpy(align 1 x, align 1 s, c) [s and c are constant] 628 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1), 629 ConstantInt::get(DL.getIntPtrType(PT), Len)); 630 NewCI->setAttributes(CI->getAttributes()); 631 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 632 copyFlags(*CI, NewCI); 633 return Dst; 634 } 635 636 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B, 637 unsigned CharSize) { 638 Value *Src = CI->getArgOperand(0); 639 640 // Constant folding: strlen("xyz") -> 3 641 if (uint64_t Len = GetStringLength(Src, CharSize)) 642 return ConstantInt::get(CI->getType(), Len - 1); 643 644 // If s is a constant pointer pointing to a string literal, we can fold 645 // strlen(s + x) to strlen(s) - x, when x is known to be in the range 646 // [0, strlen(s)] or the string has a single null terminator '\0' at the end. 647 // We only try to simplify strlen when the pointer s points to an array 648 // of i8. Otherwise, we would need to scale the offset x before doing the 649 // subtraction. This will make the optimization more complex, and it's not 650 // very useful because calling strlen for a pointer of other types is 651 // very uncommon. 652 if (GEPOperator *GEP = dyn_cast<GEPOperator>(Src)) { 653 if (!isGEPBasedOnPointerToString(GEP, CharSize)) 654 return nullptr; 655 656 ConstantDataArraySlice Slice; 657 if (getConstantDataArrayInfo(GEP->getOperand(0), Slice, CharSize)) { 658 uint64_t NullTermIdx; 659 if (Slice.Array == nullptr) { 660 NullTermIdx = 0; 661 } else { 662 NullTermIdx = ~((uint64_t)0); 663 for (uint64_t I = 0, E = Slice.Length; I < E; ++I) { 664 if (Slice.Array->getElementAsInteger(I + Slice.Offset) == 0) { 665 NullTermIdx = I; 666 break; 667 } 668 } 669 // If the string does not have '\0', leave it to strlen to compute 670 // its length. 671 if (NullTermIdx == ~((uint64_t)0)) 672 return nullptr; 673 } 674 675 Value *Offset = GEP->getOperand(2); 676 KnownBits Known = computeKnownBits(Offset, DL, 0, nullptr, CI, nullptr); 677 Known.Zero.flipAllBits(); 678 uint64_t ArrSize = 679 cast<ArrayType>(GEP->getSourceElementType())->getNumElements(); 680 681 // KnownZero's bits are flipped, so zeros in KnownZero now represent 682 // bits known to be zeros in Offset, and ones in KnowZero represent 683 // bits unknown in Offset. Therefore, Offset is known to be in range 684 // [0, NullTermIdx] when the flipped KnownZero is non-negative and 685 // unsigned-less-than NullTermIdx. 686 // 687 // If Offset is not provably in the range [0, NullTermIdx], we can still 688 // optimize if we can prove that the program has undefined behavior when 689 // Offset is outside that range. That is the case when GEP->getOperand(0) 690 // is a pointer to an object whose memory extent is NullTermIdx+1. 691 if ((Known.Zero.isNonNegative() && Known.Zero.ule(NullTermIdx)) || 692 (GEP->isInBounds() && isa<GlobalVariable>(GEP->getOperand(0)) && 693 NullTermIdx == ArrSize - 1)) { 694 Offset = B.CreateSExtOrTrunc(Offset, CI->getType()); 695 return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx), 696 Offset); 697 } 698 } 699 } 700 701 // strlen(x?"foo":"bars") --> x ? 3 : 4 702 if (SelectInst *SI = dyn_cast<SelectInst>(Src)) { 703 uint64_t LenTrue = GetStringLength(SI->getTrueValue(), CharSize); 704 uint64_t LenFalse = GetStringLength(SI->getFalseValue(), CharSize); 705 if (LenTrue && LenFalse) { 706 ORE.emit([&]() { 707 return OptimizationRemark("instcombine", "simplify-libcalls", CI) 708 << "folded strlen(select) to select of constants"; 709 }); 710 return B.CreateSelect(SI->getCondition(), 711 ConstantInt::get(CI->getType(), LenTrue - 1), 712 ConstantInt::get(CI->getType(), LenFalse - 1)); 713 } 714 } 715 716 // strlen(x) != 0 --> *x != 0 717 // strlen(x) == 0 --> *x == 0 718 if (isOnlyUsedInZeroEqualityComparison(CI)) 719 return B.CreateZExt(B.CreateLoad(B.getIntNTy(CharSize), Src, "strlenfirst"), 720 CI->getType()); 721 722 return nullptr; 723 } 724 725 Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilderBase &B) { 726 if (Value *V = optimizeStringLength(CI, B, 8)) 727 return V; 728 annotateNonNullNoUndefBasedOnAccess(CI, 0); 729 return nullptr; 730 } 731 732 Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilderBase &B) { 733 Module &M = *CI->getModule(); 734 unsigned WCharSize = TLI->getWCharSize(M) * 8; 735 // We cannot perform this optimization without wchar_size metadata. 736 if (WCharSize == 0) 737 return nullptr; 738 739 return optimizeStringLength(CI, B, WCharSize); 740 } 741 742 Value *LibCallSimplifier::optimizeStrPBrk(CallInst *CI, IRBuilderBase &B) { 743 StringRef S1, S2; 744 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 745 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 746 747 // strpbrk(s, "") -> nullptr 748 // strpbrk("", s) -> nullptr 749 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty())) 750 return Constant::getNullValue(CI->getType()); 751 752 // Constant folding. 753 if (HasS1 && HasS2) { 754 size_t I = S1.find_first_of(S2); 755 if (I == StringRef::npos) // No match. 756 return Constant::getNullValue(CI->getType()); 757 758 return B.CreateGEP(B.getInt8Ty(), CI->getArgOperand(0), B.getInt64(I), 759 "strpbrk"); 760 } 761 762 // strpbrk(s, "a") -> strchr(s, 'a') 763 if (HasS2 && S2.size() == 1) 764 return copyFlags(*CI, emitStrChr(CI->getArgOperand(0), S2[0], B, TLI)); 765 766 return nullptr; 767 } 768 769 Value *LibCallSimplifier::optimizeStrTo(CallInst *CI, IRBuilderBase &B) { 770 Value *EndPtr = CI->getArgOperand(1); 771 if (isa<ConstantPointerNull>(EndPtr)) { 772 // With a null EndPtr, this function won't capture the main argument. 773 // It would be readonly too, except that it still may write to errno. 774 CI->addParamAttr(0, Attribute::NoCapture); 775 } 776 777 return nullptr; 778 } 779 780 Value *LibCallSimplifier::optimizeStrSpn(CallInst *CI, IRBuilderBase &B) { 781 StringRef S1, S2; 782 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 783 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 784 785 // strspn(s, "") -> 0 786 // strspn("", s) -> 0 787 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty())) 788 return Constant::getNullValue(CI->getType()); 789 790 // Constant folding. 791 if (HasS1 && HasS2) { 792 size_t Pos = S1.find_first_not_of(S2); 793 if (Pos == StringRef::npos) 794 Pos = S1.size(); 795 return ConstantInt::get(CI->getType(), Pos); 796 } 797 798 return nullptr; 799 } 800 801 Value *LibCallSimplifier::optimizeStrCSpn(CallInst *CI, IRBuilderBase &B) { 802 StringRef S1, S2; 803 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 804 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 805 806 // strcspn("", s) -> 0 807 if (HasS1 && S1.empty()) 808 return Constant::getNullValue(CI->getType()); 809 810 // Constant folding. 811 if (HasS1 && HasS2) { 812 size_t Pos = S1.find_first_of(S2); 813 if (Pos == StringRef::npos) 814 Pos = S1.size(); 815 return ConstantInt::get(CI->getType(), Pos); 816 } 817 818 // strcspn(s, "") -> strlen(s) 819 if (HasS2 && S2.empty()) 820 return copyFlags(*CI, emitStrLen(CI->getArgOperand(0), B, DL, TLI)); 821 822 return nullptr; 823 } 824 825 Value *LibCallSimplifier::optimizeStrStr(CallInst *CI, IRBuilderBase &B) { 826 // fold strstr(x, x) -> x. 827 if (CI->getArgOperand(0) == CI->getArgOperand(1)) 828 return B.CreateBitCast(CI->getArgOperand(0), CI->getType()); 829 830 // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0 831 if (isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) { 832 Value *StrLen = emitStrLen(CI->getArgOperand(1), B, DL, TLI); 833 if (!StrLen) 834 return nullptr; 835 Value *StrNCmp = emitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1), 836 StrLen, B, DL, TLI); 837 if (!StrNCmp) 838 return nullptr; 839 for (User *U : llvm::make_early_inc_range(CI->users())) { 840 ICmpInst *Old = cast<ICmpInst>(U); 841 Value *Cmp = 842 B.CreateICmp(Old->getPredicate(), StrNCmp, 843 ConstantInt::getNullValue(StrNCmp->getType()), "cmp"); 844 replaceAllUsesWith(Old, Cmp); 845 } 846 return CI; 847 } 848 849 // See if either input string is a constant string. 850 StringRef SearchStr, ToFindStr; 851 bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr); 852 bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr); 853 854 // fold strstr(x, "") -> x. 855 if (HasStr2 && ToFindStr.empty()) 856 return B.CreateBitCast(CI->getArgOperand(0), CI->getType()); 857 858 // If both strings are known, constant fold it. 859 if (HasStr1 && HasStr2) { 860 size_t Offset = SearchStr.find(ToFindStr); 861 862 if (Offset == StringRef::npos) // strstr("foo", "bar") -> null 863 return Constant::getNullValue(CI->getType()); 864 865 // strstr("abcd", "bc") -> gep((char*)"abcd", 1) 866 Value *Result = castToCStr(CI->getArgOperand(0), B); 867 Result = 868 B.CreateConstInBoundsGEP1_64(B.getInt8Ty(), Result, Offset, "strstr"); 869 return B.CreateBitCast(Result, CI->getType()); 870 } 871 872 // fold strstr(x, "y") -> strchr(x, 'y'). 873 if (HasStr2 && ToFindStr.size() == 1) { 874 Value *StrChr = emitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TLI); 875 return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : nullptr; 876 } 877 878 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 879 return nullptr; 880 } 881 882 Value *LibCallSimplifier::optimizeMemRChr(CallInst *CI, IRBuilderBase &B) { 883 if (isKnownNonZero(CI->getOperand(2), DL)) 884 annotateNonNullNoUndefBasedOnAccess(CI, 0); 885 return nullptr; 886 } 887 888 Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilderBase &B) { 889 Value *SrcStr = CI->getArgOperand(0); 890 Value *Size = CI->getArgOperand(2); 891 annotateNonNullAndDereferenceable(CI, 0, Size, DL); 892 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 893 ConstantInt *LenC = dyn_cast<ConstantInt>(Size); 894 895 // memchr(x, y, 0) -> null 896 if (LenC) { 897 if (LenC->isZero()) 898 return Constant::getNullValue(CI->getType()); 899 } else { 900 // From now on we need at least constant length and string. 901 return nullptr; 902 } 903 904 StringRef Str; 905 if (!getConstantStringInfo(SrcStr, Str, 0, /*TrimAtNul=*/false)) 906 return nullptr; 907 908 // Truncate the string to LenC. If Str is smaller than LenC we will still only 909 // scan the string, as reading past the end of it is undefined and we can just 910 // return null if we don't find the char. 911 Str = Str.substr(0, LenC->getZExtValue()); 912 913 // If the char is variable but the input str and length are not we can turn 914 // this memchr call into a simple bit field test. Of course this only works 915 // when the return value is only checked against null. 916 // 917 // It would be really nice to reuse switch lowering here but we can't change 918 // the CFG at this point. 919 // 920 // memchr("\r\n", C, 2) != nullptr -> (1 << C & ((1 << '\r') | (1 << '\n'))) 921 // != 0 922 // after bounds check. 923 if (!CharC && !Str.empty() && isOnlyUsedInZeroEqualityComparison(CI)) { 924 unsigned char Max = 925 *std::max_element(reinterpret_cast<const unsigned char *>(Str.begin()), 926 reinterpret_cast<const unsigned char *>(Str.end())); 927 928 // Make sure the bit field we're about to create fits in a register on the 929 // target. 930 // FIXME: On a 64 bit architecture this prevents us from using the 931 // interesting range of alpha ascii chars. We could do better by emitting 932 // two bitfields or shifting the range by 64 if no lower chars are used. 933 if (!DL.fitsInLegalInteger(Max + 1)) 934 return nullptr; 935 936 // For the bit field use a power-of-2 type with at least 8 bits to avoid 937 // creating unnecessary illegal types. 938 unsigned char Width = NextPowerOf2(std::max((unsigned char)7, Max)); 939 940 // Now build the bit field. 941 APInt Bitfield(Width, 0); 942 for (char C : Str) 943 Bitfield.setBit((unsigned char)C); 944 Value *BitfieldC = B.getInt(Bitfield); 945 946 // Adjust width of "C" to the bitfield width, then mask off the high bits. 947 Value *C = B.CreateZExtOrTrunc(CI->getArgOperand(1), BitfieldC->getType()); 948 C = B.CreateAnd(C, B.getIntN(Width, 0xFF)); 949 950 // First check that the bit field access is within bounds. 951 Value *Bounds = B.CreateICmp(ICmpInst::ICMP_ULT, C, B.getIntN(Width, Width), 952 "memchr.bounds"); 953 954 // Create code that checks if the given bit is set in the field. 955 Value *Shl = B.CreateShl(B.getIntN(Width, 1ULL), C); 956 Value *Bits = B.CreateIsNotNull(B.CreateAnd(Shl, BitfieldC), "memchr.bits"); 957 958 // Finally merge both checks and cast to pointer type. The inttoptr 959 // implicitly zexts the i1 to intptr type. 960 return B.CreateIntToPtr(B.CreateLogicalAnd(Bounds, Bits, "memchr"), 961 CI->getType()); 962 } 963 964 // Check if all arguments are constants. If so, we can constant fold. 965 if (!CharC) 966 return nullptr; 967 968 // Compute the offset. 969 size_t I = Str.find(CharC->getSExtValue() & 0xFF); 970 if (I == StringRef::npos) // Didn't find the char. memchr returns null. 971 return Constant::getNullValue(CI->getType()); 972 973 // memchr(s+n,c,l) -> gep(s+n+i,c) 974 return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "memchr"); 975 } 976 977 static Value *optimizeMemCmpConstantSize(CallInst *CI, Value *LHS, Value *RHS, 978 uint64_t Len, IRBuilderBase &B, 979 const DataLayout &DL) { 980 if (Len == 0) // memcmp(s1,s2,0) -> 0 981 return Constant::getNullValue(CI->getType()); 982 983 // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS 984 if (Len == 1) { 985 Value *LHSV = 986 B.CreateZExt(B.CreateLoad(B.getInt8Ty(), castToCStr(LHS, B), "lhsc"), 987 CI->getType(), "lhsv"); 988 Value *RHSV = 989 B.CreateZExt(B.CreateLoad(B.getInt8Ty(), castToCStr(RHS, B), "rhsc"), 990 CI->getType(), "rhsv"); 991 return B.CreateSub(LHSV, RHSV, "chardiff"); 992 } 993 994 // memcmp(S1,S2,N/8)==0 -> (*(intN_t*)S1 != *(intN_t*)S2)==0 995 // TODO: The case where both inputs are constants does not need to be limited 996 // to legal integers or equality comparison. See block below this. 997 if (DL.isLegalInteger(Len * 8) && isOnlyUsedInZeroEqualityComparison(CI)) { 998 IntegerType *IntType = IntegerType::get(CI->getContext(), Len * 8); 999 unsigned PrefAlignment = DL.getPrefTypeAlignment(IntType); 1000 1001 // First, see if we can fold either argument to a constant. 1002 Value *LHSV = nullptr; 1003 if (auto *LHSC = dyn_cast<Constant>(LHS)) { 1004 LHSC = ConstantExpr::getBitCast(LHSC, IntType->getPointerTo()); 1005 LHSV = ConstantFoldLoadFromConstPtr(LHSC, IntType, DL); 1006 } 1007 Value *RHSV = nullptr; 1008 if (auto *RHSC = dyn_cast<Constant>(RHS)) { 1009 RHSC = ConstantExpr::getBitCast(RHSC, IntType->getPointerTo()); 1010 RHSV = ConstantFoldLoadFromConstPtr(RHSC, IntType, DL); 1011 } 1012 1013 // Don't generate unaligned loads. If either source is constant data, 1014 // alignment doesn't matter for that source because there is no load. 1015 if ((LHSV || getKnownAlignment(LHS, DL, CI) >= PrefAlignment) && 1016 (RHSV || getKnownAlignment(RHS, DL, CI) >= PrefAlignment)) { 1017 if (!LHSV) { 1018 Type *LHSPtrTy = 1019 IntType->getPointerTo(LHS->getType()->getPointerAddressSpace()); 1020 LHSV = B.CreateLoad(IntType, B.CreateBitCast(LHS, LHSPtrTy), "lhsv"); 1021 } 1022 if (!RHSV) { 1023 Type *RHSPtrTy = 1024 IntType->getPointerTo(RHS->getType()->getPointerAddressSpace()); 1025 RHSV = B.CreateLoad(IntType, B.CreateBitCast(RHS, RHSPtrTy), "rhsv"); 1026 } 1027 return B.CreateZExt(B.CreateICmpNE(LHSV, RHSV), CI->getType(), "memcmp"); 1028 } 1029 } 1030 1031 // Constant folding: memcmp(x, y, Len) -> constant (all arguments are const). 1032 // TODO: This is limited to i8 arrays. 1033 StringRef LHSStr, RHSStr; 1034 if (getConstantStringInfo(LHS, LHSStr) && 1035 getConstantStringInfo(RHS, RHSStr)) { 1036 // Make sure we're not reading out-of-bounds memory. 1037 if (Len > LHSStr.size() || Len > RHSStr.size()) 1038 return nullptr; 1039 // Fold the memcmp and normalize the result. This way we get consistent 1040 // results across multiple platforms. 1041 uint64_t Ret = 0; 1042 int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len); 1043 if (Cmp < 0) 1044 Ret = -1; 1045 else if (Cmp > 0) 1046 Ret = 1; 1047 return ConstantInt::get(CI->getType(), Ret); 1048 } 1049 1050 return nullptr; 1051 } 1052 1053 // Most simplifications for memcmp also apply to bcmp. 1054 Value *LibCallSimplifier::optimizeMemCmpBCmpCommon(CallInst *CI, 1055 IRBuilderBase &B) { 1056 Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1); 1057 Value *Size = CI->getArgOperand(2); 1058 1059 if (LHS == RHS) // memcmp(s,s,x) -> 0 1060 return Constant::getNullValue(CI->getType()); 1061 1062 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL); 1063 // Handle constant lengths. 1064 ConstantInt *LenC = dyn_cast<ConstantInt>(Size); 1065 if (!LenC) 1066 return nullptr; 1067 1068 // memcmp(d,s,0) -> 0 1069 if (LenC->getZExtValue() == 0) 1070 return Constant::getNullValue(CI->getType()); 1071 1072 if (Value *Res = 1073 optimizeMemCmpConstantSize(CI, LHS, RHS, LenC->getZExtValue(), B, DL)) 1074 return Res; 1075 return nullptr; 1076 } 1077 1078 Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilderBase &B) { 1079 if (Value *V = optimizeMemCmpBCmpCommon(CI, B)) 1080 return V; 1081 1082 // memcmp(x, y, Len) == 0 -> bcmp(x, y, Len) == 0 1083 // bcmp can be more efficient than memcmp because it only has to know that 1084 // there is a difference, not how different one is to the other. 1085 if (TLI->has(LibFunc_bcmp) && isOnlyUsedInZeroEqualityComparison(CI)) { 1086 Value *LHS = CI->getArgOperand(0); 1087 Value *RHS = CI->getArgOperand(1); 1088 Value *Size = CI->getArgOperand(2); 1089 return copyFlags(*CI, emitBCmp(LHS, RHS, Size, B, DL, TLI)); 1090 } 1091 1092 return nullptr; 1093 } 1094 1095 Value *LibCallSimplifier::optimizeBCmp(CallInst *CI, IRBuilderBase &B) { 1096 return optimizeMemCmpBCmpCommon(CI, B); 1097 } 1098 1099 Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilderBase &B) { 1100 Value *Size = CI->getArgOperand(2); 1101 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL); 1102 if (isa<IntrinsicInst>(CI)) 1103 return nullptr; 1104 1105 // memcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n) 1106 CallInst *NewCI = B.CreateMemCpy(CI->getArgOperand(0), Align(1), 1107 CI->getArgOperand(1), Align(1), Size); 1108 NewCI->setAttributes(CI->getAttributes()); 1109 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 1110 copyFlags(*CI, NewCI); 1111 return CI->getArgOperand(0); 1112 } 1113 1114 Value *LibCallSimplifier::optimizeMemCCpy(CallInst *CI, IRBuilderBase &B) { 1115 Value *Dst = CI->getArgOperand(0); 1116 Value *Src = CI->getArgOperand(1); 1117 ConstantInt *StopChar = dyn_cast<ConstantInt>(CI->getArgOperand(2)); 1118 ConstantInt *N = dyn_cast<ConstantInt>(CI->getArgOperand(3)); 1119 StringRef SrcStr; 1120 if (CI->use_empty() && Dst == Src) 1121 return Dst; 1122 // memccpy(d, s, c, 0) -> nullptr 1123 if (N) { 1124 if (N->isNullValue()) 1125 return Constant::getNullValue(CI->getType()); 1126 if (!getConstantStringInfo(Src, SrcStr, /*Offset=*/0, 1127 /*TrimAtNul=*/false) || 1128 !StopChar) 1129 return nullptr; 1130 } else { 1131 return nullptr; 1132 } 1133 1134 // Wrap arg 'c' of type int to char 1135 size_t Pos = SrcStr.find(StopChar->getSExtValue() & 0xFF); 1136 if (Pos == StringRef::npos) { 1137 if (N->getZExtValue() <= SrcStr.size()) { 1138 copyFlags(*CI, B.CreateMemCpy(Dst, Align(1), Src, Align(1), 1139 CI->getArgOperand(3))); 1140 return Constant::getNullValue(CI->getType()); 1141 } 1142 return nullptr; 1143 } 1144 1145 Value *NewN = 1146 ConstantInt::get(N->getType(), std::min(uint64_t(Pos + 1), N->getZExtValue())); 1147 // memccpy -> llvm.memcpy 1148 copyFlags(*CI, B.CreateMemCpy(Dst, Align(1), Src, Align(1), NewN)); 1149 return Pos + 1 <= N->getZExtValue() 1150 ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, NewN) 1151 : Constant::getNullValue(CI->getType()); 1152 } 1153 1154 Value *LibCallSimplifier::optimizeMemPCpy(CallInst *CI, IRBuilderBase &B) { 1155 Value *Dst = CI->getArgOperand(0); 1156 Value *N = CI->getArgOperand(2); 1157 // mempcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n), x + n 1158 CallInst *NewCI = 1159 B.CreateMemCpy(Dst, Align(1), CI->getArgOperand(1), Align(1), N); 1160 // Propagate attributes, but memcpy has no return value, so make sure that 1161 // any return attributes are compliant. 1162 // TODO: Attach return value attributes to the 1st operand to preserve them? 1163 NewCI->setAttributes(CI->getAttributes()); 1164 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 1165 copyFlags(*CI, NewCI); 1166 return B.CreateInBoundsGEP(B.getInt8Ty(), Dst, N); 1167 } 1168 1169 Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilderBase &B) { 1170 Value *Size = CI->getArgOperand(2); 1171 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL); 1172 if (isa<IntrinsicInst>(CI)) 1173 return nullptr; 1174 1175 // memmove(x, y, n) -> llvm.memmove(align 1 x, align 1 y, n) 1176 CallInst *NewCI = B.CreateMemMove(CI->getArgOperand(0), Align(1), 1177 CI->getArgOperand(1), Align(1), Size); 1178 NewCI->setAttributes(CI->getAttributes()); 1179 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 1180 copyFlags(*CI, NewCI); 1181 return CI->getArgOperand(0); 1182 } 1183 1184 Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilderBase &B) { 1185 Value *Size = CI->getArgOperand(2); 1186 annotateNonNullAndDereferenceable(CI, 0, Size, DL); 1187 if (isa<IntrinsicInst>(CI)) 1188 return nullptr; 1189 1190 // memset(p, v, n) -> llvm.memset(align 1 p, v, n) 1191 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false); 1192 CallInst *NewCI = B.CreateMemSet(CI->getArgOperand(0), Val, Size, Align(1)); 1193 NewCI->setAttributes(CI->getAttributes()); 1194 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 1195 copyFlags(*CI, NewCI); 1196 return CI->getArgOperand(0); 1197 } 1198 1199 Value *LibCallSimplifier::optimizeRealloc(CallInst *CI, IRBuilderBase &B) { 1200 if (isa<ConstantPointerNull>(CI->getArgOperand(0))) 1201 return copyFlags(*CI, emitMalloc(CI->getArgOperand(1), B, DL, TLI)); 1202 1203 return nullptr; 1204 } 1205 1206 //===----------------------------------------------------------------------===// 1207 // Math Library Optimizations 1208 //===----------------------------------------------------------------------===// 1209 1210 // Replace a libcall \p CI with a call to intrinsic \p IID 1211 static Value *replaceUnaryCall(CallInst *CI, IRBuilderBase &B, 1212 Intrinsic::ID IID) { 1213 // Propagate fast-math flags from the existing call to the new call. 1214 IRBuilderBase::FastMathFlagGuard Guard(B); 1215 B.setFastMathFlags(CI->getFastMathFlags()); 1216 1217 Module *M = CI->getModule(); 1218 Value *V = CI->getArgOperand(0); 1219 Function *F = Intrinsic::getDeclaration(M, IID, CI->getType()); 1220 CallInst *NewCall = B.CreateCall(F, V); 1221 NewCall->takeName(CI); 1222 return copyFlags(*CI, NewCall); 1223 } 1224 1225 /// Return a variant of Val with float type. 1226 /// Currently this works in two cases: If Val is an FPExtension of a float 1227 /// value to something bigger, simply return the operand. 1228 /// If Val is a ConstantFP but can be converted to a float ConstantFP without 1229 /// loss of precision do so. 1230 static Value *valueHasFloatPrecision(Value *Val) { 1231 if (FPExtInst *Cast = dyn_cast<FPExtInst>(Val)) { 1232 Value *Op = Cast->getOperand(0); 1233 if (Op->getType()->isFloatTy()) 1234 return Op; 1235 } 1236 if (ConstantFP *Const = dyn_cast<ConstantFP>(Val)) { 1237 APFloat F = Const->getValueAPF(); 1238 bool losesInfo; 1239 (void)F.convert(APFloat::IEEEsingle(), APFloat::rmNearestTiesToEven, 1240 &losesInfo); 1241 if (!losesInfo) 1242 return ConstantFP::get(Const->getContext(), F); 1243 } 1244 return nullptr; 1245 } 1246 1247 /// Shrink double -> float functions. 1248 static Value *optimizeDoubleFP(CallInst *CI, IRBuilderBase &B, 1249 bool isBinary, bool isPrecise = false) { 1250 Function *CalleeFn = CI->getCalledFunction(); 1251 if (!CI->getType()->isDoubleTy() || !CalleeFn) 1252 return nullptr; 1253 1254 // If not all the uses of the function are converted to float, then bail out. 1255 // This matters if the precision of the result is more important than the 1256 // precision of the arguments. 1257 if (isPrecise) 1258 for (User *U : CI->users()) { 1259 FPTruncInst *Cast = dyn_cast<FPTruncInst>(U); 1260 if (!Cast || !Cast->getType()->isFloatTy()) 1261 return nullptr; 1262 } 1263 1264 // If this is something like 'g((double) float)', convert to 'gf(float)'. 1265 Value *V[2]; 1266 V[0] = valueHasFloatPrecision(CI->getArgOperand(0)); 1267 V[1] = isBinary ? valueHasFloatPrecision(CI->getArgOperand(1)) : nullptr; 1268 if (!V[0] || (isBinary && !V[1])) 1269 return nullptr; 1270 1271 // If call isn't an intrinsic, check that it isn't within a function with the 1272 // same name as the float version of this call, otherwise the result is an 1273 // infinite loop. For example, from MinGW-w64: 1274 // 1275 // float expf(float val) { return (float) exp((double) val); } 1276 StringRef CalleeName = CalleeFn->getName(); 1277 bool IsIntrinsic = CalleeFn->isIntrinsic(); 1278 if (!IsIntrinsic) { 1279 StringRef CallerName = CI->getFunction()->getName(); 1280 if (!CallerName.empty() && CallerName.back() == 'f' && 1281 CallerName.size() == (CalleeName.size() + 1) && 1282 CallerName.startswith(CalleeName)) 1283 return nullptr; 1284 } 1285 1286 // Propagate the math semantics from the current function to the new function. 1287 IRBuilderBase::FastMathFlagGuard Guard(B); 1288 B.setFastMathFlags(CI->getFastMathFlags()); 1289 1290 // g((double) float) -> (double) gf(float) 1291 Value *R; 1292 if (IsIntrinsic) { 1293 Module *M = CI->getModule(); 1294 Intrinsic::ID IID = CalleeFn->getIntrinsicID(); 1295 Function *Fn = Intrinsic::getDeclaration(M, IID, B.getFloatTy()); 1296 R = isBinary ? B.CreateCall(Fn, V) : B.CreateCall(Fn, V[0]); 1297 } else { 1298 AttributeList CalleeAttrs = CalleeFn->getAttributes(); 1299 R = isBinary ? emitBinaryFloatFnCall(V[0], V[1], CalleeName, B, CalleeAttrs) 1300 : emitUnaryFloatFnCall(V[0], CalleeName, B, CalleeAttrs); 1301 } 1302 return B.CreateFPExt(R, B.getDoubleTy()); 1303 } 1304 1305 /// Shrink double -> float for unary functions. 1306 static Value *optimizeUnaryDoubleFP(CallInst *CI, IRBuilderBase &B, 1307 bool isPrecise = false) { 1308 return optimizeDoubleFP(CI, B, false, isPrecise); 1309 } 1310 1311 /// Shrink double -> float for binary functions. 1312 static Value *optimizeBinaryDoubleFP(CallInst *CI, IRBuilderBase &B, 1313 bool isPrecise = false) { 1314 return optimizeDoubleFP(CI, B, true, isPrecise); 1315 } 1316 1317 // cabs(z) -> sqrt((creal(z)*creal(z)) + (cimag(z)*cimag(z))) 1318 Value *LibCallSimplifier::optimizeCAbs(CallInst *CI, IRBuilderBase &B) { 1319 if (!CI->isFast()) 1320 return nullptr; 1321 1322 // Propagate fast-math flags from the existing call to new instructions. 1323 IRBuilderBase::FastMathFlagGuard Guard(B); 1324 B.setFastMathFlags(CI->getFastMathFlags()); 1325 1326 Value *Real, *Imag; 1327 if (CI->arg_size() == 1) { 1328 Value *Op = CI->getArgOperand(0); 1329 assert(Op->getType()->isArrayTy() && "Unexpected signature for cabs!"); 1330 Real = B.CreateExtractValue(Op, 0, "real"); 1331 Imag = B.CreateExtractValue(Op, 1, "imag"); 1332 } else { 1333 assert(CI->arg_size() == 2 && "Unexpected signature for cabs!"); 1334 Real = CI->getArgOperand(0); 1335 Imag = CI->getArgOperand(1); 1336 } 1337 1338 Value *RealReal = B.CreateFMul(Real, Real); 1339 Value *ImagImag = B.CreateFMul(Imag, Imag); 1340 1341 Function *FSqrt = Intrinsic::getDeclaration(CI->getModule(), Intrinsic::sqrt, 1342 CI->getType()); 1343 return copyFlags( 1344 *CI, B.CreateCall(FSqrt, B.CreateFAdd(RealReal, ImagImag), "cabs")); 1345 } 1346 1347 static Value *optimizeTrigReflections(CallInst *Call, LibFunc Func, 1348 IRBuilderBase &B) { 1349 if (!isa<FPMathOperator>(Call)) 1350 return nullptr; 1351 1352 IRBuilderBase::FastMathFlagGuard Guard(B); 1353 B.setFastMathFlags(Call->getFastMathFlags()); 1354 1355 // TODO: Can this be shared to also handle LLVM intrinsics? 1356 Value *X; 1357 switch (Func) { 1358 case LibFunc_sin: 1359 case LibFunc_sinf: 1360 case LibFunc_sinl: 1361 case LibFunc_tan: 1362 case LibFunc_tanf: 1363 case LibFunc_tanl: 1364 // sin(-X) --> -sin(X) 1365 // tan(-X) --> -tan(X) 1366 if (match(Call->getArgOperand(0), m_OneUse(m_FNeg(m_Value(X))))) 1367 return B.CreateFNeg( 1368 copyFlags(*Call, B.CreateCall(Call->getCalledFunction(), X))); 1369 break; 1370 case LibFunc_cos: 1371 case LibFunc_cosf: 1372 case LibFunc_cosl: 1373 // cos(-X) --> cos(X) 1374 if (match(Call->getArgOperand(0), m_FNeg(m_Value(X)))) 1375 return copyFlags(*Call, 1376 B.CreateCall(Call->getCalledFunction(), X, "cos")); 1377 break; 1378 default: 1379 break; 1380 } 1381 return nullptr; 1382 } 1383 1384 static Value *getPow(Value *InnerChain[33], unsigned Exp, IRBuilderBase &B) { 1385 // Multiplications calculated using Addition Chains. 1386 // Refer: http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html 1387 1388 assert(Exp != 0 && "Incorrect exponent 0 not handled"); 1389 1390 if (InnerChain[Exp]) 1391 return InnerChain[Exp]; 1392 1393 static const unsigned AddChain[33][2] = { 1394 {0, 0}, // Unused. 1395 {0, 0}, // Unused (base case = pow1). 1396 {1, 1}, // Unused (pre-computed). 1397 {1, 2}, {2, 2}, {2, 3}, {3, 3}, {2, 5}, {4, 4}, 1398 {1, 8}, {5, 5}, {1, 10}, {6, 6}, {4, 9}, {7, 7}, 1399 {3, 12}, {8, 8}, {8, 9}, {2, 16}, {1, 18}, {10, 10}, 1400 {6, 15}, {11, 11}, {3, 20}, {12, 12}, {8, 17}, {13, 13}, 1401 {3, 24}, {14, 14}, {4, 25}, {15, 15}, {3, 28}, {16, 16}, 1402 }; 1403 1404 InnerChain[Exp] = B.CreateFMul(getPow(InnerChain, AddChain[Exp][0], B), 1405 getPow(InnerChain, AddChain[Exp][1], B)); 1406 return InnerChain[Exp]; 1407 } 1408 1409 // Return a properly extended integer (DstWidth bits wide) if the operation is 1410 // an itofp. 1411 static Value *getIntToFPVal(Value *I2F, IRBuilderBase &B, unsigned DstWidth) { 1412 if (isa<SIToFPInst>(I2F) || isa<UIToFPInst>(I2F)) { 1413 Value *Op = cast<Instruction>(I2F)->getOperand(0); 1414 // Make sure that the exponent fits inside an "int" of size DstWidth, 1415 // thus avoiding any range issues that FP has not. 1416 unsigned BitWidth = Op->getType()->getPrimitiveSizeInBits(); 1417 if (BitWidth < DstWidth || 1418 (BitWidth == DstWidth && isa<SIToFPInst>(I2F))) 1419 return isa<SIToFPInst>(I2F) ? B.CreateSExt(Op, B.getIntNTy(DstWidth)) 1420 : B.CreateZExt(Op, B.getIntNTy(DstWidth)); 1421 } 1422 1423 return nullptr; 1424 } 1425 1426 /// Use exp{,2}(x * y) for pow(exp{,2}(x), y); 1427 /// ldexp(1.0, x) for pow(2.0, itofp(x)); exp2(n * x) for pow(2.0 ** n, x); 1428 /// exp10(x) for pow(10.0, x); exp2(log2(n) * x) for pow(n, x). 1429 Value *LibCallSimplifier::replacePowWithExp(CallInst *Pow, IRBuilderBase &B) { 1430 Value *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1); 1431 AttributeList Attrs; // Attributes are only meaningful on the original call 1432 Module *Mod = Pow->getModule(); 1433 Type *Ty = Pow->getType(); 1434 bool Ignored; 1435 1436 // Evaluate special cases related to a nested function as the base. 1437 1438 // pow(exp(x), y) -> exp(x * y) 1439 // pow(exp2(x), y) -> exp2(x * y) 1440 // If exp{,2}() is used only once, it is better to fold two transcendental 1441 // math functions into one. If used again, exp{,2}() would still have to be 1442 // called with the original argument, then keep both original transcendental 1443 // functions. However, this transformation is only safe with fully relaxed 1444 // math semantics, since, besides rounding differences, it changes overflow 1445 // and underflow behavior quite dramatically. For example: 1446 // pow(exp(1000), 0.001) = pow(inf, 0.001) = inf 1447 // Whereas: 1448 // exp(1000 * 0.001) = exp(1) 1449 // TODO: Loosen the requirement for fully relaxed math semantics. 1450 // TODO: Handle exp10() when more targets have it available. 1451 CallInst *BaseFn = dyn_cast<CallInst>(Base); 1452 if (BaseFn && BaseFn->hasOneUse() && BaseFn->isFast() && Pow->isFast()) { 1453 LibFunc LibFn; 1454 1455 Function *CalleeFn = BaseFn->getCalledFunction(); 1456 if (CalleeFn && 1457 TLI->getLibFunc(CalleeFn->getName(), LibFn) && TLI->has(LibFn)) { 1458 StringRef ExpName; 1459 Intrinsic::ID ID; 1460 Value *ExpFn; 1461 LibFunc LibFnFloat, LibFnDouble, LibFnLongDouble; 1462 1463 switch (LibFn) { 1464 default: 1465 return nullptr; 1466 case LibFunc_expf: case LibFunc_exp: case LibFunc_expl: 1467 ExpName = TLI->getName(LibFunc_exp); 1468 ID = Intrinsic::exp; 1469 LibFnFloat = LibFunc_expf; 1470 LibFnDouble = LibFunc_exp; 1471 LibFnLongDouble = LibFunc_expl; 1472 break; 1473 case LibFunc_exp2f: case LibFunc_exp2: case LibFunc_exp2l: 1474 ExpName = TLI->getName(LibFunc_exp2); 1475 ID = Intrinsic::exp2; 1476 LibFnFloat = LibFunc_exp2f; 1477 LibFnDouble = LibFunc_exp2; 1478 LibFnLongDouble = LibFunc_exp2l; 1479 break; 1480 } 1481 1482 // Create new exp{,2}() with the product as its argument. 1483 Value *FMul = B.CreateFMul(BaseFn->getArgOperand(0), Expo, "mul"); 1484 ExpFn = BaseFn->doesNotAccessMemory() 1485 ? B.CreateCall(Intrinsic::getDeclaration(Mod, ID, Ty), 1486 FMul, ExpName) 1487 : emitUnaryFloatFnCall(FMul, TLI, LibFnDouble, LibFnFloat, 1488 LibFnLongDouble, B, 1489 BaseFn->getAttributes()); 1490 1491 // Since the new exp{,2}() is different from the original one, dead code 1492 // elimination cannot be trusted to remove it, since it may have side 1493 // effects (e.g., errno). When the only consumer for the original 1494 // exp{,2}() is pow(), then it has to be explicitly erased. 1495 substituteInParent(BaseFn, ExpFn); 1496 return ExpFn; 1497 } 1498 } 1499 1500 // Evaluate special cases related to a constant base. 1501 1502 const APFloat *BaseF; 1503 if (!match(Pow->getArgOperand(0), m_APFloat(BaseF))) 1504 return nullptr; 1505 1506 // pow(2.0, itofp(x)) -> ldexp(1.0, x) 1507 if (match(Base, m_SpecificFP(2.0)) && 1508 (isa<SIToFPInst>(Expo) || isa<UIToFPInst>(Expo)) && 1509 hasFloatFn(TLI, Ty, LibFunc_ldexp, LibFunc_ldexpf, LibFunc_ldexpl)) { 1510 if (Value *ExpoI = getIntToFPVal(Expo, B, TLI->getIntSize())) 1511 return copyFlags(*Pow, 1512 emitBinaryFloatFnCall(ConstantFP::get(Ty, 1.0), ExpoI, 1513 TLI, LibFunc_ldexp, LibFunc_ldexpf, 1514 LibFunc_ldexpl, B, Attrs)); 1515 } 1516 1517 // pow(2.0 ** n, x) -> exp2(n * x) 1518 if (hasFloatFn(TLI, Ty, LibFunc_exp2, LibFunc_exp2f, LibFunc_exp2l)) { 1519 APFloat BaseR = APFloat(1.0); 1520 BaseR.convert(BaseF->getSemantics(), APFloat::rmTowardZero, &Ignored); 1521 BaseR = BaseR / *BaseF; 1522 bool IsInteger = BaseF->isInteger(), IsReciprocal = BaseR.isInteger(); 1523 const APFloat *NF = IsReciprocal ? &BaseR : BaseF; 1524 APSInt NI(64, false); 1525 if ((IsInteger || IsReciprocal) && 1526 NF->convertToInteger(NI, APFloat::rmTowardZero, &Ignored) == 1527 APFloat::opOK && 1528 NI > 1 && NI.isPowerOf2()) { 1529 double N = NI.logBase2() * (IsReciprocal ? -1.0 : 1.0); 1530 Value *FMul = B.CreateFMul(Expo, ConstantFP::get(Ty, N), "mul"); 1531 if (Pow->doesNotAccessMemory()) 1532 return copyFlags(*Pow, B.CreateCall(Intrinsic::getDeclaration( 1533 Mod, Intrinsic::exp2, Ty), 1534 FMul, "exp2")); 1535 else 1536 return copyFlags(*Pow, emitUnaryFloatFnCall(FMul, TLI, LibFunc_exp2, 1537 LibFunc_exp2f, 1538 LibFunc_exp2l, B, Attrs)); 1539 } 1540 } 1541 1542 // pow(10.0, x) -> exp10(x) 1543 // TODO: There is no exp10() intrinsic yet, but some day there shall be one. 1544 if (match(Base, m_SpecificFP(10.0)) && 1545 hasFloatFn(TLI, Ty, LibFunc_exp10, LibFunc_exp10f, LibFunc_exp10l)) 1546 return copyFlags(*Pow, emitUnaryFloatFnCall(Expo, TLI, LibFunc_exp10, 1547 LibFunc_exp10f, LibFunc_exp10l, 1548 B, Attrs)); 1549 1550 // pow(x, y) -> exp2(log2(x) * y) 1551 if (Pow->hasApproxFunc() && Pow->hasNoNaNs() && BaseF->isFiniteNonZero() && 1552 !BaseF->isNegative()) { 1553 // pow(1, inf) is defined to be 1 but exp2(log2(1) * inf) evaluates to NaN. 1554 // Luckily optimizePow has already handled the x == 1 case. 1555 assert(!match(Base, m_FPOne()) && 1556 "pow(1.0, y) should have been simplified earlier!"); 1557 1558 Value *Log = nullptr; 1559 if (Ty->isFloatTy()) 1560 Log = ConstantFP::get(Ty, std::log2(BaseF->convertToFloat())); 1561 else if (Ty->isDoubleTy()) 1562 Log = ConstantFP::get(Ty, std::log2(BaseF->convertToDouble())); 1563 1564 if (Log) { 1565 Value *FMul = B.CreateFMul(Log, Expo, "mul"); 1566 if (Pow->doesNotAccessMemory()) 1567 return copyFlags(*Pow, B.CreateCall(Intrinsic::getDeclaration( 1568 Mod, Intrinsic::exp2, Ty), 1569 FMul, "exp2")); 1570 else if (hasFloatFn(TLI, Ty, LibFunc_exp2, LibFunc_exp2f, LibFunc_exp2l)) 1571 return copyFlags(*Pow, emitUnaryFloatFnCall(FMul, TLI, LibFunc_exp2, 1572 LibFunc_exp2f, 1573 LibFunc_exp2l, B, Attrs)); 1574 } 1575 } 1576 1577 return nullptr; 1578 } 1579 1580 static Value *getSqrtCall(Value *V, AttributeList Attrs, bool NoErrno, 1581 Module *M, IRBuilderBase &B, 1582 const TargetLibraryInfo *TLI) { 1583 // If errno is never set, then use the intrinsic for sqrt(). 1584 if (NoErrno) { 1585 Function *SqrtFn = 1586 Intrinsic::getDeclaration(M, Intrinsic::sqrt, V->getType()); 1587 return B.CreateCall(SqrtFn, V, "sqrt"); 1588 } 1589 1590 // Otherwise, use the libcall for sqrt(). 1591 if (hasFloatFn(TLI, V->getType(), LibFunc_sqrt, LibFunc_sqrtf, LibFunc_sqrtl)) 1592 // TODO: We also should check that the target can in fact lower the sqrt() 1593 // libcall. We currently have no way to ask this question, so we ask if 1594 // the target has a sqrt() libcall, which is not exactly the same. 1595 return emitUnaryFloatFnCall(V, TLI, LibFunc_sqrt, LibFunc_sqrtf, 1596 LibFunc_sqrtl, B, Attrs); 1597 1598 return nullptr; 1599 } 1600 1601 /// Use square root in place of pow(x, +/-0.5). 1602 Value *LibCallSimplifier::replacePowWithSqrt(CallInst *Pow, IRBuilderBase &B) { 1603 Value *Sqrt, *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1); 1604 AttributeList Attrs; // Attributes are only meaningful on the original call 1605 Module *Mod = Pow->getModule(); 1606 Type *Ty = Pow->getType(); 1607 1608 const APFloat *ExpoF; 1609 if (!match(Expo, m_APFloat(ExpoF)) || 1610 (!ExpoF->isExactlyValue(0.5) && !ExpoF->isExactlyValue(-0.5))) 1611 return nullptr; 1612 1613 // Converting pow(X, -0.5) to 1/sqrt(X) may introduce an extra rounding step, 1614 // so that requires fast-math-flags (afn or reassoc). 1615 if (ExpoF->isNegative() && (!Pow->hasApproxFunc() && !Pow->hasAllowReassoc())) 1616 return nullptr; 1617 1618 // If we have a pow() library call (accesses memory) and we can't guarantee 1619 // that the base is not an infinity, give up: 1620 // pow(-Inf, 0.5) is optionally required to have a result of +Inf (not setting 1621 // errno), but sqrt(-Inf) is required by various standards to set errno. 1622 if (!Pow->doesNotAccessMemory() && !Pow->hasNoInfs() && 1623 !isKnownNeverInfinity(Base, TLI)) 1624 return nullptr; 1625 1626 Sqrt = getSqrtCall(Base, Attrs, Pow->doesNotAccessMemory(), Mod, B, TLI); 1627 if (!Sqrt) 1628 return nullptr; 1629 1630 // Handle signed zero base by expanding to fabs(sqrt(x)). 1631 if (!Pow->hasNoSignedZeros()) { 1632 Function *FAbsFn = Intrinsic::getDeclaration(Mod, Intrinsic::fabs, Ty); 1633 Sqrt = B.CreateCall(FAbsFn, Sqrt, "abs"); 1634 } 1635 1636 Sqrt = copyFlags(*Pow, Sqrt); 1637 1638 // Handle non finite base by expanding to 1639 // (x == -infinity ? +infinity : sqrt(x)). 1640 if (!Pow->hasNoInfs()) { 1641 Value *PosInf = ConstantFP::getInfinity(Ty), 1642 *NegInf = ConstantFP::getInfinity(Ty, true); 1643 Value *FCmp = B.CreateFCmpOEQ(Base, NegInf, "isinf"); 1644 Sqrt = B.CreateSelect(FCmp, PosInf, Sqrt); 1645 } 1646 1647 // If the exponent is negative, then get the reciprocal. 1648 if (ExpoF->isNegative()) 1649 Sqrt = B.CreateFDiv(ConstantFP::get(Ty, 1.0), Sqrt, "reciprocal"); 1650 1651 return Sqrt; 1652 } 1653 1654 static Value *createPowWithIntegerExponent(Value *Base, Value *Expo, Module *M, 1655 IRBuilderBase &B) { 1656 Value *Args[] = {Base, Expo}; 1657 Type *Types[] = {Base->getType(), Expo->getType()}; 1658 Function *F = Intrinsic::getDeclaration(M, Intrinsic::powi, Types); 1659 return B.CreateCall(F, Args); 1660 } 1661 1662 Value *LibCallSimplifier::optimizePow(CallInst *Pow, IRBuilderBase &B) { 1663 Value *Base = Pow->getArgOperand(0); 1664 Value *Expo = Pow->getArgOperand(1); 1665 Function *Callee = Pow->getCalledFunction(); 1666 StringRef Name = Callee->getName(); 1667 Type *Ty = Pow->getType(); 1668 Module *M = Pow->getModule(); 1669 bool AllowApprox = Pow->hasApproxFunc(); 1670 bool Ignored; 1671 1672 // Propagate the math semantics from the call to any created instructions. 1673 IRBuilderBase::FastMathFlagGuard Guard(B); 1674 B.setFastMathFlags(Pow->getFastMathFlags()); 1675 // Evaluate special cases related to the base. 1676 1677 // pow(1.0, x) -> 1.0 1678 if (match(Base, m_FPOne())) 1679 return Base; 1680 1681 if (Value *Exp = replacePowWithExp(Pow, B)) 1682 return Exp; 1683 1684 // Evaluate special cases related to the exponent. 1685 1686 // pow(x, -1.0) -> 1.0 / x 1687 if (match(Expo, m_SpecificFP(-1.0))) 1688 return B.CreateFDiv(ConstantFP::get(Ty, 1.0), Base, "reciprocal"); 1689 1690 // pow(x, +/-0.0) -> 1.0 1691 if (match(Expo, m_AnyZeroFP())) 1692 return ConstantFP::get(Ty, 1.0); 1693 1694 // pow(x, 1.0) -> x 1695 if (match(Expo, m_FPOne())) 1696 return Base; 1697 1698 // pow(x, 2.0) -> x * x 1699 if (match(Expo, m_SpecificFP(2.0))) 1700 return B.CreateFMul(Base, Base, "square"); 1701 1702 if (Value *Sqrt = replacePowWithSqrt(Pow, B)) 1703 return Sqrt; 1704 1705 // pow(x, n) -> x * x * x * ... 1706 const APFloat *ExpoF; 1707 if (AllowApprox && match(Expo, m_APFloat(ExpoF)) && 1708 !ExpoF->isExactlyValue(0.5) && !ExpoF->isExactlyValue(-0.5)) { 1709 // We limit to a max of 7 multiplications, thus the maximum exponent is 32. 1710 // If the exponent is an integer+0.5 we generate a call to sqrt and an 1711 // additional fmul. 1712 // TODO: This whole transformation should be backend specific (e.g. some 1713 // backends might prefer libcalls or the limit for the exponent might 1714 // be different) and it should also consider optimizing for size. 1715 APFloat LimF(ExpoF->getSemantics(), 33), 1716 ExpoA(abs(*ExpoF)); 1717 if (ExpoA < LimF) { 1718 // This transformation applies to integer or integer+0.5 exponents only. 1719 // For integer+0.5, we create a sqrt(Base) call. 1720 Value *Sqrt = nullptr; 1721 if (!ExpoA.isInteger()) { 1722 APFloat Expo2 = ExpoA; 1723 // To check if ExpoA is an integer + 0.5, we add it to itself. If there 1724 // is no floating point exception and the result is an integer, then 1725 // ExpoA == integer + 0.5 1726 if (Expo2.add(ExpoA, APFloat::rmNearestTiesToEven) != APFloat::opOK) 1727 return nullptr; 1728 1729 if (!Expo2.isInteger()) 1730 return nullptr; 1731 1732 Sqrt = getSqrtCall(Base, Pow->getCalledFunction()->getAttributes(), 1733 Pow->doesNotAccessMemory(), M, B, TLI); 1734 if (!Sqrt) 1735 return nullptr; 1736 } 1737 1738 // We will memoize intermediate products of the Addition Chain. 1739 Value *InnerChain[33] = {nullptr}; 1740 InnerChain[1] = Base; 1741 InnerChain[2] = B.CreateFMul(Base, Base, "square"); 1742 1743 // We cannot readily convert a non-double type (like float) to a double. 1744 // So we first convert it to something which could be converted to double. 1745 ExpoA.convert(APFloat::IEEEdouble(), APFloat::rmTowardZero, &Ignored); 1746 Value *FMul = getPow(InnerChain, ExpoA.convertToDouble(), B); 1747 1748 // Expand pow(x, y+0.5) to pow(x, y) * sqrt(x). 1749 if (Sqrt) 1750 FMul = B.CreateFMul(FMul, Sqrt); 1751 1752 // If the exponent is negative, then get the reciprocal. 1753 if (ExpoF->isNegative()) 1754 FMul = B.CreateFDiv(ConstantFP::get(Ty, 1.0), FMul, "reciprocal"); 1755 1756 return FMul; 1757 } 1758 1759 APSInt IntExpo(TLI->getIntSize(), /*isUnsigned=*/false); 1760 // powf(x, n) -> powi(x, n) if n is a constant signed integer value 1761 if (ExpoF->isInteger() && 1762 ExpoF->convertToInteger(IntExpo, APFloat::rmTowardZero, &Ignored) == 1763 APFloat::opOK) { 1764 return copyFlags( 1765 *Pow, 1766 createPowWithIntegerExponent( 1767 Base, ConstantInt::get(B.getIntNTy(TLI->getIntSize()), IntExpo), 1768 M, B)); 1769 } 1770 } 1771 1772 // powf(x, itofp(y)) -> powi(x, y) 1773 if (AllowApprox && (isa<SIToFPInst>(Expo) || isa<UIToFPInst>(Expo))) { 1774 if (Value *ExpoI = getIntToFPVal(Expo, B, TLI->getIntSize())) 1775 return copyFlags(*Pow, createPowWithIntegerExponent(Base, ExpoI, M, B)); 1776 } 1777 1778 // Shrink pow() to powf() if the arguments are single precision, 1779 // unless the result is expected to be double precision. 1780 if (UnsafeFPShrink && Name == TLI->getName(LibFunc_pow) && 1781 hasFloatVersion(Name)) { 1782 if (Value *Shrunk = optimizeBinaryDoubleFP(Pow, B, true)) 1783 return Shrunk; 1784 } 1785 1786 return nullptr; 1787 } 1788 1789 Value *LibCallSimplifier::optimizeExp2(CallInst *CI, IRBuilderBase &B) { 1790 Function *Callee = CI->getCalledFunction(); 1791 AttributeList Attrs; // Attributes are only meaningful on the original call 1792 StringRef Name = Callee->getName(); 1793 Value *Ret = nullptr; 1794 if (UnsafeFPShrink && Name == TLI->getName(LibFunc_exp2) && 1795 hasFloatVersion(Name)) 1796 Ret = optimizeUnaryDoubleFP(CI, B, true); 1797 1798 Type *Ty = CI->getType(); 1799 Value *Op = CI->getArgOperand(0); 1800 1801 // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= IntSize 1802 // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < IntSize 1803 if ((isa<SIToFPInst>(Op) || isa<UIToFPInst>(Op)) && 1804 hasFloatFn(TLI, Ty, LibFunc_ldexp, LibFunc_ldexpf, LibFunc_ldexpl)) { 1805 if (Value *Exp = getIntToFPVal(Op, B, TLI->getIntSize())) 1806 return emitBinaryFloatFnCall(ConstantFP::get(Ty, 1.0), Exp, TLI, 1807 LibFunc_ldexp, LibFunc_ldexpf, LibFunc_ldexpl, 1808 B, Attrs); 1809 } 1810 1811 return Ret; 1812 } 1813 1814 Value *LibCallSimplifier::optimizeFMinFMax(CallInst *CI, IRBuilderBase &B) { 1815 // If we can shrink the call to a float function rather than a double 1816 // function, do that first. 1817 Function *Callee = CI->getCalledFunction(); 1818 StringRef Name = Callee->getName(); 1819 if ((Name == "fmin" || Name == "fmax") && hasFloatVersion(Name)) 1820 if (Value *Ret = optimizeBinaryDoubleFP(CI, B)) 1821 return Ret; 1822 1823 // The LLVM intrinsics minnum/maxnum correspond to fmin/fmax. Canonicalize to 1824 // the intrinsics for improved optimization (for example, vectorization). 1825 // No-signed-zeros is implied by the definitions of fmax/fmin themselves. 1826 // From the C standard draft WG14/N1256: 1827 // "Ideally, fmax would be sensitive to the sign of zero, for example 1828 // fmax(-0.0, +0.0) would return +0; however, implementation in software 1829 // might be impractical." 1830 IRBuilderBase::FastMathFlagGuard Guard(B); 1831 FastMathFlags FMF = CI->getFastMathFlags(); 1832 FMF.setNoSignedZeros(); 1833 B.setFastMathFlags(FMF); 1834 1835 Intrinsic::ID IID = Callee->getName().startswith("fmin") ? Intrinsic::minnum 1836 : Intrinsic::maxnum; 1837 Function *F = Intrinsic::getDeclaration(CI->getModule(), IID, CI->getType()); 1838 return copyFlags( 1839 *CI, B.CreateCall(F, {CI->getArgOperand(0), CI->getArgOperand(1)})); 1840 } 1841 1842 Value *LibCallSimplifier::optimizeLog(CallInst *Log, IRBuilderBase &B) { 1843 Function *LogFn = Log->getCalledFunction(); 1844 AttributeList Attrs; // Attributes are only meaningful on the original call 1845 StringRef LogNm = LogFn->getName(); 1846 Intrinsic::ID LogID = LogFn->getIntrinsicID(); 1847 Module *Mod = Log->getModule(); 1848 Type *Ty = Log->getType(); 1849 Value *Ret = nullptr; 1850 1851 if (UnsafeFPShrink && hasFloatVersion(LogNm)) 1852 Ret = optimizeUnaryDoubleFP(Log, B, true); 1853 1854 // The earlier call must also be 'fast' in order to do these transforms. 1855 CallInst *Arg = dyn_cast<CallInst>(Log->getArgOperand(0)); 1856 if (!Log->isFast() || !Arg || !Arg->isFast() || !Arg->hasOneUse()) 1857 return Ret; 1858 1859 LibFunc LogLb, ExpLb, Exp2Lb, Exp10Lb, PowLb; 1860 1861 // This is only applicable to log(), log2(), log10(). 1862 if (TLI->getLibFunc(LogNm, LogLb)) 1863 switch (LogLb) { 1864 case LibFunc_logf: 1865 LogID = Intrinsic::log; 1866 ExpLb = LibFunc_expf; 1867 Exp2Lb = LibFunc_exp2f; 1868 Exp10Lb = LibFunc_exp10f; 1869 PowLb = LibFunc_powf; 1870 break; 1871 case LibFunc_log: 1872 LogID = Intrinsic::log; 1873 ExpLb = LibFunc_exp; 1874 Exp2Lb = LibFunc_exp2; 1875 Exp10Lb = LibFunc_exp10; 1876 PowLb = LibFunc_pow; 1877 break; 1878 case LibFunc_logl: 1879 LogID = Intrinsic::log; 1880 ExpLb = LibFunc_expl; 1881 Exp2Lb = LibFunc_exp2l; 1882 Exp10Lb = LibFunc_exp10l; 1883 PowLb = LibFunc_powl; 1884 break; 1885 case LibFunc_log2f: 1886 LogID = Intrinsic::log2; 1887 ExpLb = LibFunc_expf; 1888 Exp2Lb = LibFunc_exp2f; 1889 Exp10Lb = LibFunc_exp10f; 1890 PowLb = LibFunc_powf; 1891 break; 1892 case LibFunc_log2: 1893 LogID = Intrinsic::log2; 1894 ExpLb = LibFunc_exp; 1895 Exp2Lb = LibFunc_exp2; 1896 Exp10Lb = LibFunc_exp10; 1897 PowLb = LibFunc_pow; 1898 break; 1899 case LibFunc_log2l: 1900 LogID = Intrinsic::log2; 1901 ExpLb = LibFunc_expl; 1902 Exp2Lb = LibFunc_exp2l; 1903 Exp10Lb = LibFunc_exp10l; 1904 PowLb = LibFunc_powl; 1905 break; 1906 case LibFunc_log10f: 1907 LogID = Intrinsic::log10; 1908 ExpLb = LibFunc_expf; 1909 Exp2Lb = LibFunc_exp2f; 1910 Exp10Lb = LibFunc_exp10f; 1911 PowLb = LibFunc_powf; 1912 break; 1913 case LibFunc_log10: 1914 LogID = Intrinsic::log10; 1915 ExpLb = LibFunc_exp; 1916 Exp2Lb = LibFunc_exp2; 1917 Exp10Lb = LibFunc_exp10; 1918 PowLb = LibFunc_pow; 1919 break; 1920 case LibFunc_log10l: 1921 LogID = Intrinsic::log10; 1922 ExpLb = LibFunc_expl; 1923 Exp2Lb = LibFunc_exp2l; 1924 Exp10Lb = LibFunc_exp10l; 1925 PowLb = LibFunc_powl; 1926 break; 1927 default: 1928 return Ret; 1929 } 1930 else if (LogID == Intrinsic::log || LogID == Intrinsic::log2 || 1931 LogID == Intrinsic::log10) { 1932 if (Ty->getScalarType()->isFloatTy()) { 1933 ExpLb = LibFunc_expf; 1934 Exp2Lb = LibFunc_exp2f; 1935 Exp10Lb = LibFunc_exp10f; 1936 PowLb = LibFunc_powf; 1937 } else if (Ty->getScalarType()->isDoubleTy()) { 1938 ExpLb = LibFunc_exp; 1939 Exp2Lb = LibFunc_exp2; 1940 Exp10Lb = LibFunc_exp10; 1941 PowLb = LibFunc_pow; 1942 } else 1943 return Ret; 1944 } else 1945 return Ret; 1946 1947 IRBuilderBase::FastMathFlagGuard Guard(B); 1948 B.setFastMathFlags(FastMathFlags::getFast()); 1949 1950 Intrinsic::ID ArgID = Arg->getIntrinsicID(); 1951 LibFunc ArgLb = NotLibFunc; 1952 TLI->getLibFunc(*Arg, ArgLb); 1953 1954 // log(pow(x,y)) -> y*log(x) 1955 if (ArgLb == PowLb || ArgID == Intrinsic::pow) { 1956 Value *LogX = 1957 Log->doesNotAccessMemory() 1958 ? B.CreateCall(Intrinsic::getDeclaration(Mod, LogID, Ty), 1959 Arg->getOperand(0), "log") 1960 : emitUnaryFloatFnCall(Arg->getOperand(0), LogNm, B, Attrs); 1961 Value *MulY = B.CreateFMul(Arg->getArgOperand(1), LogX, "mul"); 1962 // Since pow() may have side effects, e.g. errno, 1963 // dead code elimination may not be trusted to remove it. 1964 substituteInParent(Arg, MulY); 1965 return MulY; 1966 } 1967 1968 // log(exp{,2,10}(y)) -> y*log({e,2,10}) 1969 // TODO: There is no exp10() intrinsic yet. 1970 if (ArgLb == ExpLb || ArgLb == Exp2Lb || ArgLb == Exp10Lb || 1971 ArgID == Intrinsic::exp || ArgID == Intrinsic::exp2) { 1972 Constant *Eul; 1973 if (ArgLb == ExpLb || ArgID == Intrinsic::exp) 1974 // FIXME: Add more precise value of e for long double. 1975 Eul = ConstantFP::get(Log->getType(), numbers::e); 1976 else if (ArgLb == Exp2Lb || ArgID == Intrinsic::exp2) 1977 Eul = ConstantFP::get(Log->getType(), 2.0); 1978 else 1979 Eul = ConstantFP::get(Log->getType(), 10.0); 1980 Value *LogE = Log->doesNotAccessMemory() 1981 ? B.CreateCall(Intrinsic::getDeclaration(Mod, LogID, Ty), 1982 Eul, "log") 1983 : emitUnaryFloatFnCall(Eul, LogNm, B, Attrs); 1984 Value *MulY = B.CreateFMul(Arg->getArgOperand(0), LogE, "mul"); 1985 // Since exp() may have side effects, e.g. errno, 1986 // dead code elimination may not be trusted to remove it. 1987 substituteInParent(Arg, MulY); 1988 return MulY; 1989 } 1990 1991 return Ret; 1992 } 1993 1994 Value *LibCallSimplifier::optimizeSqrt(CallInst *CI, IRBuilderBase &B) { 1995 Function *Callee = CI->getCalledFunction(); 1996 Value *Ret = nullptr; 1997 // TODO: Once we have a way (other than checking for the existince of the 1998 // libcall) to tell whether our target can lower @llvm.sqrt, relax the 1999 // condition below. 2000 if (TLI->has(LibFunc_sqrtf) && (Callee->getName() == "sqrt" || 2001 Callee->getIntrinsicID() == Intrinsic::sqrt)) 2002 Ret = optimizeUnaryDoubleFP(CI, B, true); 2003 2004 if (!CI->isFast()) 2005 return Ret; 2006 2007 Instruction *I = dyn_cast<Instruction>(CI->getArgOperand(0)); 2008 if (!I || I->getOpcode() != Instruction::FMul || !I->isFast()) 2009 return Ret; 2010 2011 // We're looking for a repeated factor in a multiplication tree, 2012 // so we can do this fold: sqrt(x * x) -> fabs(x); 2013 // or this fold: sqrt((x * x) * y) -> fabs(x) * sqrt(y). 2014 Value *Op0 = I->getOperand(0); 2015 Value *Op1 = I->getOperand(1); 2016 Value *RepeatOp = nullptr; 2017 Value *OtherOp = nullptr; 2018 if (Op0 == Op1) { 2019 // Simple match: the operands of the multiply are identical. 2020 RepeatOp = Op0; 2021 } else { 2022 // Look for a more complicated pattern: one of the operands is itself 2023 // a multiply, so search for a common factor in that multiply. 2024 // Note: We don't bother looking any deeper than this first level or for 2025 // variations of this pattern because instcombine's visitFMUL and/or the 2026 // reassociation pass should give us this form. 2027 Value *OtherMul0, *OtherMul1; 2028 if (match(Op0, m_FMul(m_Value(OtherMul0), m_Value(OtherMul1)))) { 2029 // Pattern: sqrt((x * y) * z) 2030 if (OtherMul0 == OtherMul1 && cast<Instruction>(Op0)->isFast()) { 2031 // Matched: sqrt((x * x) * z) 2032 RepeatOp = OtherMul0; 2033 OtherOp = Op1; 2034 } 2035 } 2036 } 2037 if (!RepeatOp) 2038 return Ret; 2039 2040 // Fast math flags for any created instructions should match the sqrt 2041 // and multiply. 2042 IRBuilderBase::FastMathFlagGuard Guard(B); 2043 B.setFastMathFlags(I->getFastMathFlags()); 2044 2045 // If we found a repeated factor, hoist it out of the square root and 2046 // replace it with the fabs of that factor. 2047 Module *M = Callee->getParent(); 2048 Type *ArgType = I->getType(); 2049 Function *Fabs = Intrinsic::getDeclaration(M, Intrinsic::fabs, ArgType); 2050 Value *FabsCall = B.CreateCall(Fabs, RepeatOp, "fabs"); 2051 if (OtherOp) { 2052 // If we found a non-repeated factor, we still need to get its square 2053 // root. We then multiply that by the value that was simplified out 2054 // of the square root calculation. 2055 Function *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::sqrt, ArgType); 2056 Value *SqrtCall = B.CreateCall(Sqrt, OtherOp, "sqrt"); 2057 return copyFlags(*CI, B.CreateFMul(FabsCall, SqrtCall)); 2058 } 2059 return copyFlags(*CI, FabsCall); 2060 } 2061 2062 // TODO: Generalize to handle any trig function and its inverse. 2063 Value *LibCallSimplifier::optimizeTan(CallInst *CI, IRBuilderBase &B) { 2064 Function *Callee = CI->getCalledFunction(); 2065 Value *Ret = nullptr; 2066 StringRef Name = Callee->getName(); 2067 if (UnsafeFPShrink && Name == "tan" && hasFloatVersion(Name)) 2068 Ret = optimizeUnaryDoubleFP(CI, B, true); 2069 2070 Value *Op1 = CI->getArgOperand(0); 2071 auto *OpC = dyn_cast<CallInst>(Op1); 2072 if (!OpC) 2073 return Ret; 2074 2075 // Both calls must be 'fast' in order to remove them. 2076 if (!CI->isFast() || !OpC->isFast()) 2077 return Ret; 2078 2079 // tan(atan(x)) -> x 2080 // tanf(atanf(x)) -> x 2081 // tanl(atanl(x)) -> x 2082 LibFunc Func; 2083 Function *F = OpC->getCalledFunction(); 2084 if (F && TLI->getLibFunc(F->getName(), Func) && TLI->has(Func) && 2085 ((Func == LibFunc_atan && Callee->getName() == "tan") || 2086 (Func == LibFunc_atanf && Callee->getName() == "tanf") || 2087 (Func == LibFunc_atanl && Callee->getName() == "tanl"))) 2088 Ret = OpC->getArgOperand(0); 2089 return Ret; 2090 } 2091 2092 static bool isTrigLibCall(CallInst *CI) { 2093 // We can only hope to do anything useful if we can ignore things like errno 2094 // and floating-point exceptions. 2095 // We already checked the prototype. 2096 return CI->hasFnAttr(Attribute::NoUnwind) && 2097 CI->hasFnAttr(Attribute::ReadNone); 2098 } 2099 2100 static void insertSinCosCall(IRBuilderBase &B, Function *OrigCallee, Value *Arg, 2101 bool UseFloat, Value *&Sin, Value *&Cos, 2102 Value *&SinCos) { 2103 Type *ArgTy = Arg->getType(); 2104 Type *ResTy; 2105 StringRef Name; 2106 2107 Triple T(OrigCallee->getParent()->getTargetTriple()); 2108 if (UseFloat) { 2109 Name = "__sincospif_stret"; 2110 2111 assert(T.getArch() != Triple::x86 && "x86 messy and unsupported for now"); 2112 // x86_64 can't use {float, float} since that would be returned in both 2113 // xmm0 and xmm1, which isn't what a real struct would do. 2114 ResTy = T.getArch() == Triple::x86_64 2115 ? static_cast<Type *>(FixedVectorType::get(ArgTy, 2)) 2116 : static_cast<Type *>(StructType::get(ArgTy, ArgTy)); 2117 } else { 2118 Name = "__sincospi_stret"; 2119 ResTy = StructType::get(ArgTy, ArgTy); 2120 } 2121 2122 Module *M = OrigCallee->getParent(); 2123 FunctionCallee Callee = 2124 M->getOrInsertFunction(Name, OrigCallee->getAttributes(), ResTy, ArgTy); 2125 2126 if (Instruction *ArgInst = dyn_cast<Instruction>(Arg)) { 2127 // If the argument is an instruction, it must dominate all uses so put our 2128 // sincos call there. 2129 B.SetInsertPoint(ArgInst->getParent(), ++ArgInst->getIterator()); 2130 } else { 2131 // Otherwise (e.g. for a constant) the beginning of the function is as 2132 // good a place as any. 2133 BasicBlock &EntryBB = B.GetInsertBlock()->getParent()->getEntryBlock(); 2134 B.SetInsertPoint(&EntryBB, EntryBB.begin()); 2135 } 2136 2137 SinCos = B.CreateCall(Callee, Arg, "sincospi"); 2138 2139 if (SinCos->getType()->isStructTy()) { 2140 Sin = B.CreateExtractValue(SinCos, 0, "sinpi"); 2141 Cos = B.CreateExtractValue(SinCos, 1, "cospi"); 2142 } else { 2143 Sin = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 0), 2144 "sinpi"); 2145 Cos = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 1), 2146 "cospi"); 2147 } 2148 } 2149 2150 Value *LibCallSimplifier::optimizeSinCosPi(CallInst *CI, IRBuilderBase &B) { 2151 // Make sure the prototype is as expected, otherwise the rest of the 2152 // function is probably invalid and likely to abort. 2153 if (!isTrigLibCall(CI)) 2154 return nullptr; 2155 2156 Value *Arg = CI->getArgOperand(0); 2157 SmallVector<CallInst *, 1> SinCalls; 2158 SmallVector<CallInst *, 1> CosCalls; 2159 SmallVector<CallInst *, 1> SinCosCalls; 2160 2161 bool IsFloat = Arg->getType()->isFloatTy(); 2162 2163 // Look for all compatible sinpi, cospi and sincospi calls with the same 2164 // argument. If there are enough (in some sense) we can make the 2165 // substitution. 2166 Function *F = CI->getFunction(); 2167 for (User *U : Arg->users()) 2168 classifyArgUse(U, F, IsFloat, SinCalls, CosCalls, SinCosCalls); 2169 2170 // It's only worthwhile if both sinpi and cospi are actually used. 2171 if (SinCalls.empty() || CosCalls.empty()) 2172 return nullptr; 2173 2174 Value *Sin, *Cos, *SinCos; 2175 insertSinCosCall(B, CI->getCalledFunction(), Arg, IsFloat, Sin, Cos, SinCos); 2176 2177 auto replaceTrigInsts = [this](SmallVectorImpl<CallInst *> &Calls, 2178 Value *Res) { 2179 for (CallInst *C : Calls) 2180 replaceAllUsesWith(C, Res); 2181 }; 2182 2183 replaceTrigInsts(SinCalls, Sin); 2184 replaceTrigInsts(CosCalls, Cos); 2185 replaceTrigInsts(SinCosCalls, SinCos); 2186 2187 return nullptr; 2188 } 2189 2190 void LibCallSimplifier::classifyArgUse( 2191 Value *Val, Function *F, bool IsFloat, 2192 SmallVectorImpl<CallInst *> &SinCalls, 2193 SmallVectorImpl<CallInst *> &CosCalls, 2194 SmallVectorImpl<CallInst *> &SinCosCalls) { 2195 CallInst *CI = dyn_cast<CallInst>(Val); 2196 2197 if (!CI || CI->use_empty()) 2198 return; 2199 2200 // Don't consider calls in other functions. 2201 if (CI->getFunction() != F) 2202 return; 2203 2204 Function *Callee = CI->getCalledFunction(); 2205 LibFunc Func; 2206 if (!Callee || !TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) || 2207 !isTrigLibCall(CI)) 2208 return; 2209 2210 if (IsFloat) { 2211 if (Func == LibFunc_sinpif) 2212 SinCalls.push_back(CI); 2213 else if (Func == LibFunc_cospif) 2214 CosCalls.push_back(CI); 2215 else if (Func == LibFunc_sincospif_stret) 2216 SinCosCalls.push_back(CI); 2217 } else { 2218 if (Func == LibFunc_sinpi) 2219 SinCalls.push_back(CI); 2220 else if (Func == LibFunc_cospi) 2221 CosCalls.push_back(CI); 2222 else if (Func == LibFunc_sincospi_stret) 2223 SinCosCalls.push_back(CI); 2224 } 2225 } 2226 2227 //===----------------------------------------------------------------------===// 2228 // Integer Library Call Optimizations 2229 //===----------------------------------------------------------------------===// 2230 2231 Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilderBase &B) { 2232 // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0 2233 Value *Op = CI->getArgOperand(0); 2234 Type *ArgType = Op->getType(); 2235 Function *F = Intrinsic::getDeclaration(CI->getCalledFunction()->getParent(), 2236 Intrinsic::cttz, ArgType); 2237 Value *V = B.CreateCall(F, {Op, B.getTrue()}, "cttz"); 2238 V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1)); 2239 V = B.CreateIntCast(V, B.getInt32Ty(), false); 2240 2241 Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType)); 2242 return B.CreateSelect(Cond, V, B.getInt32(0)); 2243 } 2244 2245 Value *LibCallSimplifier::optimizeFls(CallInst *CI, IRBuilderBase &B) { 2246 // fls(x) -> (i32)(sizeInBits(x) - llvm.ctlz(x, false)) 2247 Value *Op = CI->getArgOperand(0); 2248 Type *ArgType = Op->getType(); 2249 Function *F = Intrinsic::getDeclaration(CI->getCalledFunction()->getParent(), 2250 Intrinsic::ctlz, ArgType); 2251 Value *V = B.CreateCall(F, {Op, B.getFalse()}, "ctlz"); 2252 V = B.CreateSub(ConstantInt::get(V->getType(), ArgType->getIntegerBitWidth()), 2253 V); 2254 return B.CreateIntCast(V, CI->getType(), false); 2255 } 2256 2257 Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilderBase &B) { 2258 // abs(x) -> x <s 0 ? -x : x 2259 // The negation has 'nsw' because abs of INT_MIN is undefined. 2260 Value *X = CI->getArgOperand(0); 2261 Value *IsNeg = B.CreateICmpSLT(X, Constant::getNullValue(X->getType())); 2262 Value *NegX = B.CreateNSWNeg(X, "neg"); 2263 return B.CreateSelect(IsNeg, NegX, X); 2264 } 2265 2266 Value *LibCallSimplifier::optimizeIsDigit(CallInst *CI, IRBuilderBase &B) { 2267 // isdigit(c) -> (c-'0') <u 10 2268 Value *Op = CI->getArgOperand(0); 2269 Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp"); 2270 Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit"); 2271 return B.CreateZExt(Op, CI->getType()); 2272 } 2273 2274 Value *LibCallSimplifier::optimizeIsAscii(CallInst *CI, IRBuilderBase &B) { 2275 // isascii(c) -> c <u 128 2276 Value *Op = CI->getArgOperand(0); 2277 Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii"); 2278 return B.CreateZExt(Op, CI->getType()); 2279 } 2280 2281 Value *LibCallSimplifier::optimizeToAscii(CallInst *CI, IRBuilderBase &B) { 2282 // toascii(c) -> c & 0x7f 2283 return B.CreateAnd(CI->getArgOperand(0), 2284 ConstantInt::get(CI->getType(), 0x7F)); 2285 } 2286 2287 Value *LibCallSimplifier::optimizeAtoi(CallInst *CI, IRBuilderBase &B) { 2288 StringRef Str; 2289 if (!getConstantStringInfo(CI->getArgOperand(0), Str)) 2290 return nullptr; 2291 2292 return convertStrToNumber(CI, Str, 10); 2293 } 2294 2295 Value *LibCallSimplifier::optimizeStrtol(CallInst *CI, IRBuilderBase &B) { 2296 StringRef Str; 2297 if (!getConstantStringInfo(CI->getArgOperand(0), Str)) 2298 return nullptr; 2299 2300 if (!isa<ConstantPointerNull>(CI->getArgOperand(1))) 2301 return nullptr; 2302 2303 if (ConstantInt *CInt = dyn_cast<ConstantInt>(CI->getArgOperand(2))) { 2304 return convertStrToNumber(CI, Str, CInt->getSExtValue()); 2305 } 2306 2307 return nullptr; 2308 } 2309 2310 //===----------------------------------------------------------------------===// 2311 // Formatting and IO Library Call Optimizations 2312 //===----------------------------------------------------------------------===// 2313 2314 static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg); 2315 2316 Value *LibCallSimplifier::optimizeErrorReporting(CallInst *CI, IRBuilderBase &B, 2317 int StreamArg) { 2318 Function *Callee = CI->getCalledFunction(); 2319 // Error reporting calls should be cold, mark them as such. 2320 // This applies even to non-builtin calls: it is only a hint and applies to 2321 // functions that the frontend might not understand as builtins. 2322 2323 // This heuristic was suggested in: 2324 // Improving Static Branch Prediction in a Compiler 2325 // Brian L. Deitrich, Ben-Chung Cheng, Wen-mei W. Hwu 2326 // Proceedings of PACT'98, Oct. 1998, IEEE 2327 if (!CI->hasFnAttr(Attribute::Cold) && 2328 isReportingError(Callee, CI, StreamArg)) { 2329 CI->addFnAttr(Attribute::Cold); 2330 } 2331 2332 return nullptr; 2333 } 2334 2335 static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg) { 2336 if (!Callee || !Callee->isDeclaration()) 2337 return false; 2338 2339 if (StreamArg < 0) 2340 return true; 2341 2342 // These functions might be considered cold, but only if their stream 2343 // argument is stderr. 2344 2345 if (StreamArg >= (int)CI->arg_size()) 2346 return false; 2347 LoadInst *LI = dyn_cast<LoadInst>(CI->getArgOperand(StreamArg)); 2348 if (!LI) 2349 return false; 2350 GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getPointerOperand()); 2351 if (!GV || !GV->isDeclaration()) 2352 return false; 2353 return GV->getName() == "stderr"; 2354 } 2355 2356 Value *LibCallSimplifier::optimizePrintFString(CallInst *CI, IRBuilderBase &B) { 2357 // Check for a fixed format string. 2358 StringRef FormatStr; 2359 if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr)) 2360 return nullptr; 2361 2362 // Empty format string -> noop. 2363 if (FormatStr.empty()) // Tolerate printf's declared void. 2364 return CI->use_empty() ? (Value *)CI : ConstantInt::get(CI->getType(), 0); 2365 2366 // Do not do any of the following transformations if the printf return value 2367 // is used, in general the printf return value is not compatible with either 2368 // putchar() or puts(). 2369 if (!CI->use_empty()) 2370 return nullptr; 2371 2372 // printf("x") -> putchar('x'), even for "%" and "%%". 2373 if (FormatStr.size() == 1 || FormatStr == "%%") 2374 return copyFlags(*CI, emitPutChar(B.getInt32(FormatStr[0]), B, TLI)); 2375 2376 // Try to remove call or emit putchar/puts. 2377 if (FormatStr == "%s" && CI->arg_size() > 1) { 2378 StringRef OperandStr; 2379 if (!getConstantStringInfo(CI->getOperand(1), OperandStr)) 2380 return nullptr; 2381 // printf("%s", "") --> NOP 2382 if (OperandStr.empty()) 2383 return (Value *)CI; 2384 // printf("%s", "a") --> putchar('a') 2385 if (OperandStr.size() == 1) 2386 return copyFlags(*CI, emitPutChar(B.getInt32(OperandStr[0]), B, TLI)); 2387 // printf("%s", str"\n") --> puts(str) 2388 if (OperandStr.back() == '\n') { 2389 OperandStr = OperandStr.drop_back(); 2390 Value *GV = B.CreateGlobalString(OperandStr, "str"); 2391 return copyFlags(*CI, emitPutS(GV, B, TLI)); 2392 } 2393 return nullptr; 2394 } 2395 2396 // printf("foo\n") --> puts("foo") 2397 if (FormatStr.back() == '\n' && 2398 !FormatStr.contains('%')) { // No format characters. 2399 // Create a string literal with no \n on it. We expect the constant merge 2400 // pass to be run after this pass, to merge duplicate strings. 2401 FormatStr = FormatStr.drop_back(); 2402 Value *GV = B.CreateGlobalString(FormatStr, "str"); 2403 return copyFlags(*CI, emitPutS(GV, B, TLI)); 2404 } 2405 2406 // Optimize specific format strings. 2407 // printf("%c", chr) --> putchar(chr) 2408 if (FormatStr == "%c" && CI->arg_size() > 1 && 2409 CI->getArgOperand(1)->getType()->isIntegerTy()) 2410 return copyFlags(*CI, emitPutChar(CI->getArgOperand(1), B, TLI)); 2411 2412 // printf("%s\n", str) --> puts(str) 2413 if (FormatStr == "%s\n" && CI->arg_size() > 1 && 2414 CI->getArgOperand(1)->getType()->isPointerTy()) 2415 return copyFlags(*CI, emitPutS(CI->getArgOperand(1), B, TLI)); 2416 return nullptr; 2417 } 2418 2419 Value *LibCallSimplifier::optimizePrintF(CallInst *CI, IRBuilderBase &B) { 2420 2421 Function *Callee = CI->getCalledFunction(); 2422 FunctionType *FT = Callee->getFunctionType(); 2423 if (Value *V = optimizePrintFString(CI, B)) { 2424 return V; 2425 } 2426 2427 // printf(format, ...) -> iprintf(format, ...) if no floating point 2428 // arguments. 2429 if (TLI->has(LibFunc_iprintf) && !callHasFloatingPointArgument(CI)) { 2430 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2431 FunctionCallee IPrintFFn = 2432 M->getOrInsertFunction("iprintf", FT, Callee->getAttributes()); 2433 CallInst *New = cast<CallInst>(CI->clone()); 2434 New->setCalledFunction(IPrintFFn); 2435 B.Insert(New); 2436 return New; 2437 } 2438 2439 // printf(format, ...) -> __small_printf(format, ...) if no 128-bit floating point 2440 // arguments. 2441 if (TLI->has(LibFunc_small_printf) && !callHasFP128Argument(CI)) { 2442 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2443 auto SmallPrintFFn = 2444 M->getOrInsertFunction(TLI->getName(LibFunc_small_printf), 2445 FT, Callee->getAttributes()); 2446 CallInst *New = cast<CallInst>(CI->clone()); 2447 New->setCalledFunction(SmallPrintFFn); 2448 B.Insert(New); 2449 return New; 2450 } 2451 2452 annotateNonNullNoUndefBasedOnAccess(CI, 0); 2453 return nullptr; 2454 } 2455 2456 Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI, 2457 IRBuilderBase &B) { 2458 // Check for a fixed format string. 2459 StringRef FormatStr; 2460 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr)) 2461 return nullptr; 2462 2463 // If we just have a format string (nothing else crazy) transform it. 2464 Value *Dest = CI->getArgOperand(0); 2465 if (CI->arg_size() == 2) { 2466 // Make sure there's no % in the constant array. We could try to handle 2467 // %% -> % in the future if we cared. 2468 if (FormatStr.contains('%')) 2469 return nullptr; // we found a format specifier, bail out. 2470 2471 // sprintf(str, fmt) -> llvm.memcpy(align 1 str, align 1 fmt, strlen(fmt)+1) 2472 B.CreateMemCpy( 2473 Dest, Align(1), CI->getArgOperand(1), Align(1), 2474 ConstantInt::get(DL.getIntPtrType(CI->getContext()), 2475 FormatStr.size() + 1)); // Copy the null byte. 2476 return ConstantInt::get(CI->getType(), FormatStr.size()); 2477 } 2478 2479 // The remaining optimizations require the format string to be "%s" or "%c" 2480 // and have an extra operand. 2481 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3) 2482 return nullptr; 2483 2484 // Decode the second character of the format string. 2485 if (FormatStr[1] == 'c') { 2486 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0 2487 if (!CI->getArgOperand(2)->getType()->isIntegerTy()) 2488 return nullptr; 2489 Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char"); 2490 Value *Ptr = castToCStr(Dest, B); 2491 B.CreateStore(V, Ptr); 2492 Ptr = B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul"); 2493 B.CreateStore(B.getInt8(0), Ptr); 2494 2495 return ConstantInt::get(CI->getType(), 1); 2496 } 2497 2498 if (FormatStr[1] == 's') { 2499 // sprintf(dest, "%s", str) -> llvm.memcpy(align 1 dest, align 1 str, 2500 // strlen(str)+1) 2501 if (!CI->getArgOperand(2)->getType()->isPointerTy()) 2502 return nullptr; 2503 2504 if (CI->use_empty()) 2505 // sprintf(dest, "%s", str) -> strcpy(dest, str) 2506 return copyFlags(*CI, emitStrCpy(Dest, CI->getArgOperand(2), B, TLI)); 2507 2508 uint64_t SrcLen = GetStringLength(CI->getArgOperand(2)); 2509 if (SrcLen) { 2510 B.CreateMemCpy( 2511 Dest, Align(1), CI->getArgOperand(2), Align(1), 2512 ConstantInt::get(DL.getIntPtrType(CI->getContext()), SrcLen)); 2513 // Returns total number of characters written without null-character. 2514 return ConstantInt::get(CI->getType(), SrcLen - 1); 2515 } else if (Value *V = emitStpCpy(Dest, CI->getArgOperand(2), B, TLI)) { 2516 // sprintf(dest, "%s", str) -> stpcpy(dest, str) - dest 2517 // Handle mismatched pointer types (goes away with typeless pointers?). 2518 V = B.CreatePointerCast(V, B.getInt8PtrTy()); 2519 Dest = B.CreatePointerCast(Dest, B.getInt8PtrTy()); 2520 Value *PtrDiff = B.CreatePtrDiff(B.getInt8Ty(), V, Dest); 2521 return B.CreateIntCast(PtrDiff, CI->getType(), false); 2522 } 2523 2524 bool OptForSize = CI->getFunction()->hasOptSize() || 2525 llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI, 2526 PGSOQueryType::IRPass); 2527 if (OptForSize) 2528 return nullptr; 2529 2530 Value *Len = emitStrLen(CI->getArgOperand(2), B, DL, TLI); 2531 if (!Len) 2532 return nullptr; 2533 Value *IncLen = 2534 B.CreateAdd(Len, ConstantInt::get(Len->getType(), 1), "leninc"); 2535 B.CreateMemCpy(Dest, Align(1), CI->getArgOperand(2), Align(1), IncLen); 2536 2537 // The sprintf result is the unincremented number of bytes in the string. 2538 return B.CreateIntCast(Len, CI->getType(), false); 2539 } 2540 return nullptr; 2541 } 2542 2543 Value *LibCallSimplifier::optimizeSPrintF(CallInst *CI, IRBuilderBase &B) { 2544 Function *Callee = CI->getCalledFunction(); 2545 FunctionType *FT = Callee->getFunctionType(); 2546 if (Value *V = optimizeSPrintFString(CI, B)) { 2547 return V; 2548 } 2549 2550 // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating 2551 // point arguments. 2552 if (TLI->has(LibFunc_siprintf) && !callHasFloatingPointArgument(CI)) { 2553 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2554 FunctionCallee SIPrintFFn = 2555 M->getOrInsertFunction("siprintf", FT, Callee->getAttributes()); 2556 CallInst *New = cast<CallInst>(CI->clone()); 2557 New->setCalledFunction(SIPrintFFn); 2558 B.Insert(New); 2559 return New; 2560 } 2561 2562 // sprintf(str, format, ...) -> __small_sprintf(str, format, ...) if no 128-bit 2563 // floating point arguments. 2564 if (TLI->has(LibFunc_small_sprintf) && !callHasFP128Argument(CI)) { 2565 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2566 auto SmallSPrintFFn = 2567 M->getOrInsertFunction(TLI->getName(LibFunc_small_sprintf), 2568 FT, Callee->getAttributes()); 2569 CallInst *New = cast<CallInst>(CI->clone()); 2570 New->setCalledFunction(SmallSPrintFFn); 2571 B.Insert(New); 2572 return New; 2573 } 2574 2575 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1}); 2576 return nullptr; 2577 } 2578 2579 Value *LibCallSimplifier::optimizeSnPrintFString(CallInst *CI, 2580 IRBuilderBase &B) { 2581 // Check for size 2582 ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 2583 if (!Size) 2584 return nullptr; 2585 2586 uint64_t N = Size->getZExtValue(); 2587 // Check for a fixed format string. 2588 StringRef FormatStr; 2589 if (!getConstantStringInfo(CI->getArgOperand(2), FormatStr)) 2590 return nullptr; 2591 2592 // If we just have a format string (nothing else crazy) transform it. 2593 if (CI->arg_size() == 3) { 2594 // Make sure there's no % in the constant array. We could try to handle 2595 // %% -> % in the future if we cared. 2596 if (FormatStr.contains('%')) 2597 return nullptr; // we found a format specifier, bail out. 2598 2599 if (N == 0) 2600 return ConstantInt::get(CI->getType(), FormatStr.size()); 2601 else if (N < FormatStr.size() + 1) 2602 return nullptr; 2603 2604 // snprintf(dst, size, fmt) -> llvm.memcpy(align 1 dst, align 1 fmt, 2605 // strlen(fmt)+1) 2606 copyFlags( 2607 *CI, 2608 B.CreateMemCpy( 2609 CI->getArgOperand(0), Align(1), CI->getArgOperand(2), Align(1), 2610 ConstantInt::get(DL.getIntPtrType(CI->getContext()), 2611 FormatStr.size() + 1))); // Copy the null byte. 2612 return ConstantInt::get(CI->getType(), FormatStr.size()); 2613 } 2614 2615 // The remaining optimizations require the format string to be "%s" or "%c" 2616 // and have an extra operand. 2617 if (FormatStr.size() == 2 && FormatStr[0] == '%' && CI->arg_size() == 4) { 2618 2619 // Decode the second character of the format string. 2620 if (FormatStr[1] == 'c') { 2621 if (N == 0) 2622 return ConstantInt::get(CI->getType(), 1); 2623 else if (N == 1) 2624 return nullptr; 2625 2626 // snprintf(dst, size, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0 2627 if (!CI->getArgOperand(3)->getType()->isIntegerTy()) 2628 return nullptr; 2629 Value *V = B.CreateTrunc(CI->getArgOperand(3), B.getInt8Ty(), "char"); 2630 Value *Ptr = castToCStr(CI->getArgOperand(0), B); 2631 B.CreateStore(V, Ptr); 2632 Ptr = B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul"); 2633 B.CreateStore(B.getInt8(0), Ptr); 2634 2635 return ConstantInt::get(CI->getType(), 1); 2636 } 2637 2638 if (FormatStr[1] == 's') { 2639 // snprintf(dest, size, "%s", str) to llvm.memcpy(dest, str, len+1, 1) 2640 StringRef Str; 2641 if (!getConstantStringInfo(CI->getArgOperand(3), Str)) 2642 return nullptr; 2643 2644 if (N == 0) 2645 return ConstantInt::get(CI->getType(), Str.size()); 2646 else if (N < Str.size() + 1) 2647 return nullptr; 2648 2649 copyFlags( 2650 *CI, B.CreateMemCpy(CI->getArgOperand(0), Align(1), 2651 CI->getArgOperand(3), Align(1), 2652 ConstantInt::get(CI->getType(), Str.size() + 1))); 2653 2654 // The snprintf result is the unincremented number of bytes in the string. 2655 return ConstantInt::get(CI->getType(), Str.size()); 2656 } 2657 } 2658 return nullptr; 2659 } 2660 2661 Value *LibCallSimplifier::optimizeSnPrintF(CallInst *CI, IRBuilderBase &B) { 2662 if (Value *V = optimizeSnPrintFString(CI, B)) { 2663 return V; 2664 } 2665 2666 if (isKnownNonZero(CI->getOperand(1), DL)) 2667 annotateNonNullNoUndefBasedOnAccess(CI, 0); 2668 return nullptr; 2669 } 2670 2671 Value *LibCallSimplifier::optimizeFPrintFString(CallInst *CI, 2672 IRBuilderBase &B) { 2673 optimizeErrorReporting(CI, B, 0); 2674 2675 // All the optimizations depend on the format string. 2676 StringRef FormatStr; 2677 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr)) 2678 return nullptr; 2679 2680 // Do not do any of the following transformations if the fprintf return 2681 // value is used, in general the fprintf return value is not compatible 2682 // with fwrite(), fputc() or fputs(). 2683 if (!CI->use_empty()) 2684 return nullptr; 2685 2686 // fprintf(F, "foo") --> fwrite("foo", 3, 1, F) 2687 if (CI->arg_size() == 2) { 2688 // Could handle %% -> % if we cared. 2689 if (FormatStr.contains('%')) 2690 return nullptr; // We found a format specifier. 2691 2692 return copyFlags( 2693 *CI, emitFWrite(CI->getArgOperand(1), 2694 ConstantInt::get(DL.getIntPtrType(CI->getContext()), 2695 FormatStr.size()), 2696 CI->getArgOperand(0), B, DL, TLI)); 2697 } 2698 2699 // The remaining optimizations require the format string to be "%s" or "%c" 2700 // and have an extra operand. 2701 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3) 2702 return nullptr; 2703 2704 // Decode the second character of the format string. 2705 if (FormatStr[1] == 'c') { 2706 // fprintf(F, "%c", chr) --> fputc(chr, F) 2707 if (!CI->getArgOperand(2)->getType()->isIntegerTy()) 2708 return nullptr; 2709 return copyFlags( 2710 *CI, emitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B, TLI)); 2711 } 2712 2713 if (FormatStr[1] == 's') { 2714 // fprintf(F, "%s", str) --> fputs(str, F) 2715 if (!CI->getArgOperand(2)->getType()->isPointerTy()) 2716 return nullptr; 2717 return copyFlags( 2718 *CI, emitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TLI)); 2719 } 2720 return nullptr; 2721 } 2722 2723 Value *LibCallSimplifier::optimizeFPrintF(CallInst *CI, IRBuilderBase &B) { 2724 Function *Callee = CI->getCalledFunction(); 2725 FunctionType *FT = Callee->getFunctionType(); 2726 if (Value *V = optimizeFPrintFString(CI, B)) { 2727 return V; 2728 } 2729 2730 // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no 2731 // floating point arguments. 2732 if (TLI->has(LibFunc_fiprintf) && !callHasFloatingPointArgument(CI)) { 2733 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2734 FunctionCallee FIPrintFFn = 2735 M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes()); 2736 CallInst *New = cast<CallInst>(CI->clone()); 2737 New->setCalledFunction(FIPrintFFn); 2738 B.Insert(New); 2739 return New; 2740 } 2741 2742 // fprintf(stream, format, ...) -> __small_fprintf(stream, format, ...) if no 2743 // 128-bit floating point arguments. 2744 if (TLI->has(LibFunc_small_fprintf) && !callHasFP128Argument(CI)) { 2745 Module *M = B.GetInsertBlock()->getParent()->getParent(); 2746 auto SmallFPrintFFn = 2747 M->getOrInsertFunction(TLI->getName(LibFunc_small_fprintf), 2748 FT, Callee->getAttributes()); 2749 CallInst *New = cast<CallInst>(CI->clone()); 2750 New->setCalledFunction(SmallFPrintFFn); 2751 B.Insert(New); 2752 return New; 2753 } 2754 2755 return nullptr; 2756 } 2757 2758 Value *LibCallSimplifier::optimizeFWrite(CallInst *CI, IRBuilderBase &B) { 2759 optimizeErrorReporting(CI, B, 3); 2760 2761 // Get the element size and count. 2762 ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 2763 ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2)); 2764 if (SizeC && CountC) { 2765 uint64_t Bytes = SizeC->getZExtValue() * CountC->getZExtValue(); 2766 2767 // If this is writing zero records, remove the call (it's a noop). 2768 if (Bytes == 0) 2769 return ConstantInt::get(CI->getType(), 0); 2770 2771 // If this is writing one byte, turn it into fputc. 2772 // This optimisation is only valid, if the return value is unused. 2773 if (Bytes == 1 && CI->use_empty()) { // fwrite(S,1,1,F) -> fputc(S[0],F) 2774 Value *Char = B.CreateLoad(B.getInt8Ty(), 2775 castToCStr(CI->getArgOperand(0), B), "char"); 2776 Value *NewCI = emitFPutC(Char, CI->getArgOperand(3), B, TLI); 2777 return NewCI ? ConstantInt::get(CI->getType(), 1) : nullptr; 2778 } 2779 } 2780 2781 return nullptr; 2782 } 2783 2784 Value *LibCallSimplifier::optimizeFPuts(CallInst *CI, IRBuilderBase &B) { 2785 optimizeErrorReporting(CI, B, 1); 2786 2787 // Don't rewrite fputs to fwrite when optimising for size because fwrite 2788 // requires more arguments and thus extra MOVs are required. 2789 bool OptForSize = CI->getFunction()->hasOptSize() || 2790 llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI, 2791 PGSOQueryType::IRPass); 2792 if (OptForSize) 2793 return nullptr; 2794 2795 // We can't optimize if return value is used. 2796 if (!CI->use_empty()) 2797 return nullptr; 2798 2799 // fputs(s,F) --> fwrite(s,strlen(s),1,F) 2800 uint64_t Len = GetStringLength(CI->getArgOperand(0)); 2801 if (!Len) 2802 return nullptr; 2803 2804 // Known to have no uses (see above). 2805 return copyFlags( 2806 *CI, 2807 emitFWrite(CI->getArgOperand(0), 2808 ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len - 1), 2809 CI->getArgOperand(1), B, DL, TLI)); 2810 } 2811 2812 Value *LibCallSimplifier::optimizePuts(CallInst *CI, IRBuilderBase &B) { 2813 annotateNonNullNoUndefBasedOnAccess(CI, 0); 2814 if (!CI->use_empty()) 2815 return nullptr; 2816 2817 // Check for a constant string. 2818 // puts("") -> putchar('\n') 2819 StringRef Str; 2820 if (getConstantStringInfo(CI->getArgOperand(0), Str) && Str.empty()) 2821 return copyFlags(*CI, emitPutChar(B.getInt32('\n'), B, TLI)); 2822 2823 return nullptr; 2824 } 2825 2826 Value *LibCallSimplifier::optimizeBCopy(CallInst *CI, IRBuilderBase &B) { 2827 // bcopy(src, dst, n) -> llvm.memmove(dst, src, n) 2828 return copyFlags(*CI, B.CreateMemMove(CI->getArgOperand(1), Align(1), 2829 CI->getArgOperand(0), Align(1), 2830 CI->getArgOperand(2))); 2831 } 2832 2833 bool LibCallSimplifier::hasFloatVersion(StringRef FuncName) { 2834 LibFunc Func; 2835 SmallString<20> FloatFuncName = FuncName; 2836 FloatFuncName += 'f'; 2837 if (TLI->getLibFunc(FloatFuncName, Func)) 2838 return TLI->has(Func); 2839 return false; 2840 } 2841 2842 Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI, 2843 IRBuilderBase &Builder) { 2844 LibFunc Func; 2845 Function *Callee = CI->getCalledFunction(); 2846 // Check for string/memory library functions. 2847 if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) { 2848 // Make sure we never change the calling convention. 2849 assert( 2850 (ignoreCallingConv(Func) || 2851 TargetLibraryInfoImpl::isCallingConvCCompatible(CI)) && 2852 "Optimizing string/memory libcall would change the calling convention"); 2853 switch (Func) { 2854 case LibFunc_strcat: 2855 return optimizeStrCat(CI, Builder); 2856 case LibFunc_strncat: 2857 return optimizeStrNCat(CI, Builder); 2858 case LibFunc_strchr: 2859 return optimizeStrChr(CI, Builder); 2860 case LibFunc_strrchr: 2861 return optimizeStrRChr(CI, Builder); 2862 case LibFunc_strcmp: 2863 return optimizeStrCmp(CI, Builder); 2864 case LibFunc_strncmp: 2865 return optimizeStrNCmp(CI, Builder); 2866 case LibFunc_strcpy: 2867 return optimizeStrCpy(CI, Builder); 2868 case LibFunc_stpcpy: 2869 return optimizeStpCpy(CI, Builder); 2870 case LibFunc_strncpy: 2871 return optimizeStrNCpy(CI, Builder); 2872 case LibFunc_strlen: 2873 return optimizeStrLen(CI, Builder); 2874 case LibFunc_strpbrk: 2875 return optimizeStrPBrk(CI, Builder); 2876 case LibFunc_strndup: 2877 return optimizeStrNDup(CI, Builder); 2878 case LibFunc_strtol: 2879 case LibFunc_strtod: 2880 case LibFunc_strtof: 2881 case LibFunc_strtoul: 2882 case LibFunc_strtoll: 2883 case LibFunc_strtold: 2884 case LibFunc_strtoull: 2885 return optimizeStrTo(CI, Builder); 2886 case LibFunc_strspn: 2887 return optimizeStrSpn(CI, Builder); 2888 case LibFunc_strcspn: 2889 return optimizeStrCSpn(CI, Builder); 2890 case LibFunc_strstr: 2891 return optimizeStrStr(CI, Builder); 2892 case LibFunc_memchr: 2893 return optimizeMemChr(CI, Builder); 2894 case LibFunc_memrchr: 2895 return optimizeMemRChr(CI, Builder); 2896 case LibFunc_bcmp: 2897 return optimizeBCmp(CI, Builder); 2898 case LibFunc_memcmp: 2899 return optimizeMemCmp(CI, Builder); 2900 case LibFunc_memcpy: 2901 return optimizeMemCpy(CI, Builder); 2902 case LibFunc_memccpy: 2903 return optimizeMemCCpy(CI, Builder); 2904 case LibFunc_mempcpy: 2905 return optimizeMemPCpy(CI, Builder); 2906 case LibFunc_memmove: 2907 return optimizeMemMove(CI, Builder); 2908 case LibFunc_memset: 2909 return optimizeMemSet(CI, Builder); 2910 case LibFunc_realloc: 2911 return optimizeRealloc(CI, Builder); 2912 case LibFunc_wcslen: 2913 return optimizeWcslen(CI, Builder); 2914 case LibFunc_bcopy: 2915 return optimizeBCopy(CI, Builder); 2916 default: 2917 break; 2918 } 2919 } 2920 return nullptr; 2921 } 2922 2923 Value *LibCallSimplifier::optimizeFloatingPointLibCall(CallInst *CI, 2924 LibFunc Func, 2925 IRBuilderBase &Builder) { 2926 // Don't optimize calls that require strict floating point semantics. 2927 if (CI->isStrictFP()) 2928 return nullptr; 2929 2930 if (Value *V = optimizeTrigReflections(CI, Func, Builder)) 2931 return V; 2932 2933 switch (Func) { 2934 case LibFunc_sinpif: 2935 case LibFunc_sinpi: 2936 case LibFunc_cospif: 2937 case LibFunc_cospi: 2938 return optimizeSinCosPi(CI, Builder); 2939 case LibFunc_powf: 2940 case LibFunc_pow: 2941 case LibFunc_powl: 2942 return optimizePow(CI, Builder); 2943 case LibFunc_exp2l: 2944 case LibFunc_exp2: 2945 case LibFunc_exp2f: 2946 return optimizeExp2(CI, Builder); 2947 case LibFunc_fabsf: 2948 case LibFunc_fabs: 2949 case LibFunc_fabsl: 2950 return replaceUnaryCall(CI, Builder, Intrinsic::fabs); 2951 case LibFunc_sqrtf: 2952 case LibFunc_sqrt: 2953 case LibFunc_sqrtl: 2954 return optimizeSqrt(CI, Builder); 2955 case LibFunc_logf: 2956 case LibFunc_log: 2957 case LibFunc_logl: 2958 case LibFunc_log10f: 2959 case LibFunc_log10: 2960 case LibFunc_log10l: 2961 case LibFunc_log1pf: 2962 case LibFunc_log1p: 2963 case LibFunc_log1pl: 2964 case LibFunc_log2f: 2965 case LibFunc_log2: 2966 case LibFunc_log2l: 2967 case LibFunc_logbf: 2968 case LibFunc_logb: 2969 case LibFunc_logbl: 2970 return optimizeLog(CI, Builder); 2971 case LibFunc_tan: 2972 case LibFunc_tanf: 2973 case LibFunc_tanl: 2974 return optimizeTan(CI, Builder); 2975 case LibFunc_ceil: 2976 return replaceUnaryCall(CI, Builder, Intrinsic::ceil); 2977 case LibFunc_floor: 2978 return replaceUnaryCall(CI, Builder, Intrinsic::floor); 2979 case LibFunc_round: 2980 return replaceUnaryCall(CI, Builder, Intrinsic::round); 2981 case LibFunc_roundeven: 2982 return replaceUnaryCall(CI, Builder, Intrinsic::roundeven); 2983 case LibFunc_nearbyint: 2984 return replaceUnaryCall(CI, Builder, Intrinsic::nearbyint); 2985 case LibFunc_rint: 2986 return replaceUnaryCall(CI, Builder, Intrinsic::rint); 2987 case LibFunc_trunc: 2988 return replaceUnaryCall(CI, Builder, Intrinsic::trunc); 2989 case LibFunc_acos: 2990 case LibFunc_acosh: 2991 case LibFunc_asin: 2992 case LibFunc_asinh: 2993 case LibFunc_atan: 2994 case LibFunc_atanh: 2995 case LibFunc_cbrt: 2996 case LibFunc_cosh: 2997 case LibFunc_exp: 2998 case LibFunc_exp10: 2999 case LibFunc_expm1: 3000 case LibFunc_cos: 3001 case LibFunc_sin: 3002 case LibFunc_sinh: 3003 case LibFunc_tanh: 3004 if (UnsafeFPShrink && hasFloatVersion(CI->getCalledFunction()->getName())) 3005 return optimizeUnaryDoubleFP(CI, Builder, true); 3006 return nullptr; 3007 case LibFunc_copysign: 3008 if (hasFloatVersion(CI->getCalledFunction()->getName())) 3009 return optimizeBinaryDoubleFP(CI, Builder); 3010 return nullptr; 3011 case LibFunc_fminf: 3012 case LibFunc_fmin: 3013 case LibFunc_fminl: 3014 case LibFunc_fmaxf: 3015 case LibFunc_fmax: 3016 case LibFunc_fmaxl: 3017 return optimizeFMinFMax(CI, Builder); 3018 case LibFunc_cabs: 3019 case LibFunc_cabsf: 3020 case LibFunc_cabsl: 3021 return optimizeCAbs(CI, Builder); 3022 default: 3023 return nullptr; 3024 } 3025 } 3026 3027 Value *LibCallSimplifier::optimizeCall(CallInst *CI, IRBuilderBase &Builder) { 3028 assert(!CI->isMustTailCall() && "These transforms aren't musttail safe."); 3029 3030 // TODO: Split out the code below that operates on FP calls so that 3031 // we can all non-FP calls with the StrictFP attribute to be 3032 // optimized. 3033 if (CI->isNoBuiltin()) 3034 return nullptr; 3035 3036 LibFunc Func; 3037 Function *Callee = CI->getCalledFunction(); 3038 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI); 3039 3040 SmallVector<OperandBundleDef, 2> OpBundles; 3041 CI->getOperandBundlesAsDefs(OpBundles); 3042 3043 IRBuilderBase::OperandBundlesGuard Guard(Builder); 3044 Builder.setDefaultOperandBundles(OpBundles); 3045 3046 // Command-line parameter overrides instruction attribute. 3047 // This can't be moved to optimizeFloatingPointLibCall() because it may be 3048 // used by the intrinsic optimizations. 3049 if (EnableUnsafeFPShrink.getNumOccurrences() > 0) 3050 UnsafeFPShrink = EnableUnsafeFPShrink; 3051 else if (isa<FPMathOperator>(CI) && CI->isFast()) 3052 UnsafeFPShrink = true; 3053 3054 // First, check for intrinsics. 3055 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 3056 if (!IsCallingConvC) 3057 return nullptr; 3058 // The FP intrinsics have corresponding constrained versions so we don't 3059 // need to check for the StrictFP attribute here. 3060 switch (II->getIntrinsicID()) { 3061 case Intrinsic::pow: 3062 return optimizePow(CI, Builder); 3063 case Intrinsic::exp2: 3064 return optimizeExp2(CI, Builder); 3065 case Intrinsic::log: 3066 case Intrinsic::log2: 3067 case Intrinsic::log10: 3068 return optimizeLog(CI, Builder); 3069 case Intrinsic::sqrt: 3070 return optimizeSqrt(CI, Builder); 3071 case Intrinsic::memset: 3072 return optimizeMemSet(CI, Builder); 3073 case Intrinsic::memcpy: 3074 return optimizeMemCpy(CI, Builder); 3075 case Intrinsic::memmove: 3076 return optimizeMemMove(CI, Builder); 3077 default: 3078 return nullptr; 3079 } 3080 } 3081 3082 // Also try to simplify calls to fortified library functions. 3083 if (Value *SimplifiedFortifiedCI = 3084 FortifiedSimplifier.optimizeCall(CI, Builder)) { 3085 // Try to further simplify the result. 3086 CallInst *SimplifiedCI = dyn_cast<CallInst>(SimplifiedFortifiedCI); 3087 if (SimplifiedCI && SimplifiedCI->getCalledFunction()) { 3088 // Ensure that SimplifiedCI's uses are complete, since some calls have 3089 // their uses analyzed. 3090 replaceAllUsesWith(CI, SimplifiedCI); 3091 3092 // Set insertion point to SimplifiedCI to guarantee we reach all uses 3093 // we might replace later on. 3094 IRBuilderBase::InsertPointGuard Guard(Builder); 3095 Builder.SetInsertPoint(SimplifiedCI); 3096 if (Value *V = optimizeStringMemoryLibCall(SimplifiedCI, Builder)) { 3097 // If we were able to further simplify, remove the now redundant call. 3098 substituteInParent(SimplifiedCI, V); 3099 return V; 3100 } 3101 } 3102 return SimplifiedFortifiedCI; 3103 } 3104 3105 // Then check for known library functions. 3106 if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) { 3107 // We never change the calling convention. 3108 if (!ignoreCallingConv(Func) && !IsCallingConvC) 3109 return nullptr; 3110 if (Value *V = optimizeStringMemoryLibCall(CI, Builder)) 3111 return V; 3112 if (Value *V = optimizeFloatingPointLibCall(CI, Func, Builder)) 3113 return V; 3114 switch (Func) { 3115 case LibFunc_ffs: 3116 case LibFunc_ffsl: 3117 case LibFunc_ffsll: 3118 return optimizeFFS(CI, Builder); 3119 case LibFunc_fls: 3120 case LibFunc_flsl: 3121 case LibFunc_flsll: 3122 return optimizeFls(CI, Builder); 3123 case LibFunc_abs: 3124 case LibFunc_labs: 3125 case LibFunc_llabs: 3126 return optimizeAbs(CI, Builder); 3127 case LibFunc_isdigit: 3128 return optimizeIsDigit(CI, Builder); 3129 case LibFunc_isascii: 3130 return optimizeIsAscii(CI, Builder); 3131 case LibFunc_toascii: 3132 return optimizeToAscii(CI, Builder); 3133 case LibFunc_atoi: 3134 case LibFunc_atol: 3135 case LibFunc_atoll: 3136 return optimizeAtoi(CI, Builder); 3137 case LibFunc_strtol: 3138 case LibFunc_strtoll: 3139 return optimizeStrtol(CI, Builder); 3140 case LibFunc_printf: 3141 return optimizePrintF(CI, Builder); 3142 case LibFunc_sprintf: 3143 return optimizeSPrintF(CI, Builder); 3144 case LibFunc_snprintf: 3145 return optimizeSnPrintF(CI, Builder); 3146 case LibFunc_fprintf: 3147 return optimizeFPrintF(CI, Builder); 3148 case LibFunc_fwrite: 3149 return optimizeFWrite(CI, Builder); 3150 case LibFunc_fputs: 3151 return optimizeFPuts(CI, Builder); 3152 case LibFunc_puts: 3153 return optimizePuts(CI, Builder); 3154 case LibFunc_perror: 3155 return optimizeErrorReporting(CI, Builder); 3156 case LibFunc_vfprintf: 3157 case LibFunc_fiprintf: 3158 return optimizeErrorReporting(CI, Builder, 0); 3159 default: 3160 return nullptr; 3161 } 3162 } 3163 return nullptr; 3164 } 3165 3166 LibCallSimplifier::LibCallSimplifier( 3167 const DataLayout &DL, const TargetLibraryInfo *TLI, 3168 OptimizationRemarkEmitter &ORE, 3169 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, 3170 function_ref<void(Instruction *, Value *)> Replacer, 3171 function_ref<void(Instruction *)> Eraser) 3172 : FortifiedSimplifier(TLI), DL(DL), TLI(TLI), ORE(ORE), BFI(BFI), PSI(PSI), 3173 UnsafeFPShrink(false), Replacer(Replacer), Eraser(Eraser) {} 3174 3175 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) { 3176 // Indirect through the replacer used in this instance. 3177 Replacer(I, With); 3178 } 3179 3180 void LibCallSimplifier::eraseFromParent(Instruction *I) { 3181 Eraser(I); 3182 } 3183 3184 // TODO: 3185 // Additional cases that we need to add to this file: 3186 // 3187 // cbrt: 3188 // * cbrt(expN(X)) -> expN(x/3) 3189 // * cbrt(sqrt(x)) -> pow(x,1/6) 3190 // * cbrt(cbrt(x)) -> pow(x,1/9) 3191 // 3192 // exp, expf, expl: 3193 // * exp(log(x)) -> x 3194 // 3195 // log, logf, logl: 3196 // * log(exp(x)) -> x 3197 // * log(exp(y)) -> y*log(e) 3198 // * log(exp10(y)) -> y*log(10) 3199 // * log(sqrt(x)) -> 0.5*log(x) 3200 // 3201 // pow, powf, powl: 3202 // * pow(sqrt(x),y) -> pow(x,y*0.5) 3203 // * pow(pow(x,y),z)-> pow(x,y*z) 3204 // 3205 // signbit: 3206 // * signbit(cnst) -> cnst' 3207 // * signbit(nncst) -> 0 (if pstv is a non-negative constant) 3208 // 3209 // sqrt, sqrtf, sqrtl: 3210 // * sqrt(expN(x)) -> expN(x*0.5) 3211 // * sqrt(Nroot(x)) -> pow(x,1/(2*N)) 3212 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5) 3213 // 3214 3215 //===----------------------------------------------------------------------===// 3216 // Fortified Library Call Optimizations 3217 //===----------------------------------------------------------------------===// 3218 3219 bool 3220 FortifiedLibCallSimplifier::isFortifiedCallFoldable(CallInst *CI, 3221 unsigned ObjSizeOp, 3222 Optional<unsigned> SizeOp, 3223 Optional<unsigned> StrOp, 3224 Optional<unsigned> FlagOp) { 3225 // If this function takes a flag argument, the implementation may use it to 3226 // perform extra checks. Don't fold into the non-checking variant. 3227 if (FlagOp) { 3228 ConstantInt *Flag = dyn_cast<ConstantInt>(CI->getArgOperand(*FlagOp)); 3229 if (!Flag || !Flag->isZero()) 3230 return false; 3231 } 3232 3233 if (SizeOp && CI->getArgOperand(ObjSizeOp) == CI->getArgOperand(*SizeOp)) 3234 return true; 3235 3236 if (ConstantInt *ObjSizeCI = 3237 dyn_cast<ConstantInt>(CI->getArgOperand(ObjSizeOp))) { 3238 if (ObjSizeCI->isMinusOne()) 3239 return true; 3240 // If the object size wasn't -1 (unknown), bail out if we were asked to. 3241 if (OnlyLowerUnknownSize) 3242 return false; 3243 if (StrOp) { 3244 uint64_t Len = GetStringLength(CI->getArgOperand(*StrOp)); 3245 // If the length is 0 we don't know how long it is and so we can't 3246 // remove the check. 3247 if (Len) 3248 annotateDereferenceableBytes(CI, *StrOp, Len); 3249 else 3250 return false; 3251 return ObjSizeCI->getZExtValue() >= Len; 3252 } 3253 3254 if (SizeOp) { 3255 if (ConstantInt *SizeCI = 3256 dyn_cast<ConstantInt>(CI->getArgOperand(*SizeOp))) 3257 return ObjSizeCI->getZExtValue() >= SizeCI->getZExtValue(); 3258 } 3259 } 3260 return false; 3261 } 3262 3263 Value *FortifiedLibCallSimplifier::optimizeMemCpyChk(CallInst *CI, 3264 IRBuilderBase &B) { 3265 if (isFortifiedCallFoldable(CI, 3, 2)) { 3266 CallInst *NewCI = 3267 B.CreateMemCpy(CI->getArgOperand(0), Align(1), CI->getArgOperand(1), 3268 Align(1), CI->getArgOperand(2)); 3269 NewCI->setAttributes(CI->getAttributes()); 3270 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 3271 copyFlags(*CI, NewCI); 3272 return CI->getArgOperand(0); 3273 } 3274 return nullptr; 3275 } 3276 3277 Value *FortifiedLibCallSimplifier::optimizeMemMoveChk(CallInst *CI, 3278 IRBuilderBase &B) { 3279 if (isFortifiedCallFoldable(CI, 3, 2)) { 3280 CallInst *NewCI = 3281 B.CreateMemMove(CI->getArgOperand(0), Align(1), CI->getArgOperand(1), 3282 Align(1), CI->getArgOperand(2)); 3283 NewCI->setAttributes(CI->getAttributes()); 3284 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 3285 copyFlags(*CI, NewCI); 3286 return CI->getArgOperand(0); 3287 } 3288 return nullptr; 3289 } 3290 3291 Value *FortifiedLibCallSimplifier::optimizeMemSetChk(CallInst *CI, 3292 IRBuilderBase &B) { 3293 if (isFortifiedCallFoldable(CI, 3, 2)) { 3294 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false); 3295 CallInst *NewCI = B.CreateMemSet(CI->getArgOperand(0), Val, 3296 CI->getArgOperand(2), Align(1)); 3297 NewCI->setAttributes(CI->getAttributes()); 3298 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 3299 copyFlags(*CI, NewCI); 3300 return CI->getArgOperand(0); 3301 } 3302 return nullptr; 3303 } 3304 3305 Value *FortifiedLibCallSimplifier::optimizeMemPCpyChk(CallInst *CI, 3306 IRBuilderBase &B) { 3307 const DataLayout &DL = CI->getModule()->getDataLayout(); 3308 if (isFortifiedCallFoldable(CI, 3, 2)) 3309 if (Value *Call = emitMemPCpy(CI->getArgOperand(0), CI->getArgOperand(1), 3310 CI->getArgOperand(2), B, DL, TLI)) { 3311 CallInst *NewCI = cast<CallInst>(Call); 3312 NewCI->setAttributes(CI->getAttributes()); 3313 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType())); 3314 return copyFlags(*CI, NewCI); 3315 } 3316 return nullptr; 3317 } 3318 3319 Value *FortifiedLibCallSimplifier::optimizeStrpCpyChk(CallInst *CI, 3320 IRBuilderBase &B, 3321 LibFunc Func) { 3322 const DataLayout &DL = CI->getModule()->getDataLayout(); 3323 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1), 3324 *ObjSize = CI->getArgOperand(2); 3325 3326 // __stpcpy_chk(x,x,...) -> x+strlen(x) 3327 if (Func == LibFunc_stpcpy_chk && !OnlyLowerUnknownSize && Dst == Src) { 3328 Value *StrLen = emitStrLen(Src, B, DL, TLI); 3329 return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr; 3330 } 3331 3332 // If a) we don't have any length information, or b) we know this will 3333 // fit then just lower to a plain st[rp]cpy. Otherwise we'll keep our 3334 // st[rp]cpy_chk call which may fail at runtime if the size is too long. 3335 // TODO: It might be nice to get a maximum length out of the possible 3336 // string lengths for varying. 3337 if (isFortifiedCallFoldable(CI, 2, None, 1)) { 3338 if (Func == LibFunc_strcpy_chk) 3339 return copyFlags(*CI, emitStrCpy(Dst, Src, B, TLI)); 3340 else 3341 return copyFlags(*CI, emitStpCpy(Dst, Src, B, TLI)); 3342 } 3343 3344 if (OnlyLowerUnknownSize) 3345 return nullptr; 3346 3347 // Maybe we can stil fold __st[rp]cpy_chk to __memcpy_chk. 3348 uint64_t Len = GetStringLength(Src); 3349 if (Len) 3350 annotateDereferenceableBytes(CI, 1, Len); 3351 else 3352 return nullptr; 3353 3354 // FIXME: There is really no guarantee that sizeof(size_t) is equal to 3355 // sizeof(int*) for every target. So the assumption used here to derive the 3356 // SizeTBits based on the size of an integer pointer in address space zero 3357 // isn't always valid. 3358 Type *SizeTTy = DL.getIntPtrType(CI->getContext(), /*AddressSpace=*/0); 3359 Value *LenV = ConstantInt::get(SizeTTy, Len); 3360 Value *Ret = emitMemCpyChk(Dst, Src, LenV, ObjSize, B, DL, TLI); 3361 // If the function was an __stpcpy_chk, and we were able to fold it into 3362 // a __memcpy_chk, we still need to return the correct end pointer. 3363 if (Ret && Func == LibFunc_stpcpy_chk) 3364 return B.CreateGEP(B.getInt8Ty(), Dst, ConstantInt::get(SizeTTy, Len - 1)); 3365 return copyFlags(*CI, cast<CallInst>(Ret)); 3366 } 3367 3368 Value *FortifiedLibCallSimplifier::optimizeStrLenChk(CallInst *CI, 3369 IRBuilderBase &B) { 3370 if (isFortifiedCallFoldable(CI, 1, None, 0)) 3371 return copyFlags(*CI, emitStrLen(CI->getArgOperand(0), B, 3372 CI->getModule()->getDataLayout(), TLI)); 3373 return nullptr; 3374 } 3375 3376 Value *FortifiedLibCallSimplifier::optimizeStrpNCpyChk(CallInst *CI, 3377 IRBuilderBase &B, 3378 LibFunc Func) { 3379 if (isFortifiedCallFoldable(CI, 3, 2)) { 3380 if (Func == LibFunc_strncpy_chk) 3381 return copyFlags(*CI, 3382 emitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1), 3383 CI->getArgOperand(2), B, TLI)); 3384 else 3385 return copyFlags(*CI, 3386 emitStpNCpy(CI->getArgOperand(0), CI->getArgOperand(1), 3387 CI->getArgOperand(2), B, TLI)); 3388 } 3389 3390 return nullptr; 3391 } 3392 3393 Value *FortifiedLibCallSimplifier::optimizeMemCCpyChk(CallInst *CI, 3394 IRBuilderBase &B) { 3395 if (isFortifiedCallFoldable(CI, 4, 3)) 3396 return copyFlags( 3397 *CI, emitMemCCpy(CI->getArgOperand(0), CI->getArgOperand(1), 3398 CI->getArgOperand(2), CI->getArgOperand(3), B, TLI)); 3399 3400 return nullptr; 3401 } 3402 3403 Value *FortifiedLibCallSimplifier::optimizeSNPrintfChk(CallInst *CI, 3404 IRBuilderBase &B) { 3405 if (isFortifiedCallFoldable(CI, 3, 1, None, 2)) { 3406 SmallVector<Value *, 8> VariadicArgs(drop_begin(CI->args(), 5)); 3407 return copyFlags(*CI, 3408 emitSNPrintf(CI->getArgOperand(0), CI->getArgOperand(1), 3409 CI->getArgOperand(4), VariadicArgs, B, TLI)); 3410 } 3411 3412 return nullptr; 3413 } 3414 3415 Value *FortifiedLibCallSimplifier::optimizeSPrintfChk(CallInst *CI, 3416 IRBuilderBase &B) { 3417 if (isFortifiedCallFoldable(CI, 2, None, None, 1)) { 3418 SmallVector<Value *, 8> VariadicArgs(drop_begin(CI->args(), 4)); 3419 return copyFlags(*CI, 3420 emitSPrintf(CI->getArgOperand(0), CI->getArgOperand(3), 3421 VariadicArgs, B, TLI)); 3422 } 3423 3424 return nullptr; 3425 } 3426 3427 Value *FortifiedLibCallSimplifier::optimizeStrCatChk(CallInst *CI, 3428 IRBuilderBase &B) { 3429 if (isFortifiedCallFoldable(CI, 2)) 3430 return copyFlags( 3431 *CI, emitStrCat(CI->getArgOperand(0), CI->getArgOperand(1), B, TLI)); 3432 3433 return nullptr; 3434 } 3435 3436 Value *FortifiedLibCallSimplifier::optimizeStrLCat(CallInst *CI, 3437 IRBuilderBase &B) { 3438 if (isFortifiedCallFoldable(CI, 3)) 3439 return copyFlags(*CI, 3440 emitStrLCat(CI->getArgOperand(0), CI->getArgOperand(1), 3441 CI->getArgOperand(2), B, TLI)); 3442 3443 return nullptr; 3444 } 3445 3446 Value *FortifiedLibCallSimplifier::optimizeStrNCatChk(CallInst *CI, 3447 IRBuilderBase &B) { 3448 if (isFortifiedCallFoldable(CI, 3)) 3449 return copyFlags(*CI, 3450 emitStrNCat(CI->getArgOperand(0), CI->getArgOperand(1), 3451 CI->getArgOperand(2), B, TLI)); 3452 3453 return nullptr; 3454 } 3455 3456 Value *FortifiedLibCallSimplifier::optimizeStrLCpyChk(CallInst *CI, 3457 IRBuilderBase &B) { 3458 if (isFortifiedCallFoldable(CI, 3)) 3459 return copyFlags(*CI, 3460 emitStrLCpy(CI->getArgOperand(0), CI->getArgOperand(1), 3461 CI->getArgOperand(2), B, TLI)); 3462 3463 return nullptr; 3464 } 3465 3466 Value *FortifiedLibCallSimplifier::optimizeVSNPrintfChk(CallInst *CI, 3467 IRBuilderBase &B) { 3468 if (isFortifiedCallFoldable(CI, 3, 1, None, 2)) 3469 return copyFlags( 3470 *CI, emitVSNPrintf(CI->getArgOperand(0), CI->getArgOperand(1), 3471 CI->getArgOperand(4), CI->getArgOperand(5), B, TLI)); 3472 3473 return nullptr; 3474 } 3475 3476 Value *FortifiedLibCallSimplifier::optimizeVSPrintfChk(CallInst *CI, 3477 IRBuilderBase &B) { 3478 if (isFortifiedCallFoldable(CI, 2, None, None, 1)) 3479 return copyFlags(*CI, 3480 emitVSPrintf(CI->getArgOperand(0), CI->getArgOperand(3), 3481 CI->getArgOperand(4), B, TLI)); 3482 3483 return nullptr; 3484 } 3485 3486 Value *FortifiedLibCallSimplifier::optimizeCall(CallInst *CI, 3487 IRBuilderBase &Builder) { 3488 // FIXME: We shouldn't be changing "nobuiltin" or TLI unavailable calls here. 3489 // Some clang users checked for _chk libcall availability using: 3490 // __has_builtin(__builtin___memcpy_chk) 3491 // When compiling with -fno-builtin, this is always true. 3492 // When passing -ffreestanding/-mkernel, which both imply -fno-builtin, we 3493 // end up with fortified libcalls, which isn't acceptable in a freestanding 3494 // environment which only provides their non-fortified counterparts. 3495 // 3496 // Until we change clang and/or teach external users to check for availability 3497 // differently, disregard the "nobuiltin" attribute and TLI::has. 3498 // 3499 // PR23093. 3500 3501 LibFunc Func; 3502 Function *Callee = CI->getCalledFunction(); 3503 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI); 3504 3505 SmallVector<OperandBundleDef, 2> OpBundles; 3506 CI->getOperandBundlesAsDefs(OpBundles); 3507 3508 IRBuilderBase::OperandBundlesGuard Guard(Builder); 3509 Builder.setDefaultOperandBundles(OpBundles); 3510 3511 // First, check that this is a known library functions and that the prototype 3512 // is correct. 3513 if (!TLI->getLibFunc(*Callee, Func)) 3514 return nullptr; 3515 3516 // We never change the calling convention. 3517 if (!ignoreCallingConv(Func) && !IsCallingConvC) 3518 return nullptr; 3519 3520 switch (Func) { 3521 case LibFunc_memcpy_chk: 3522 return optimizeMemCpyChk(CI, Builder); 3523 case LibFunc_mempcpy_chk: 3524 return optimizeMemPCpyChk(CI, Builder); 3525 case LibFunc_memmove_chk: 3526 return optimizeMemMoveChk(CI, Builder); 3527 case LibFunc_memset_chk: 3528 return optimizeMemSetChk(CI, Builder); 3529 case LibFunc_stpcpy_chk: 3530 case LibFunc_strcpy_chk: 3531 return optimizeStrpCpyChk(CI, Builder, Func); 3532 case LibFunc_strlen_chk: 3533 return optimizeStrLenChk(CI, Builder); 3534 case LibFunc_stpncpy_chk: 3535 case LibFunc_strncpy_chk: 3536 return optimizeStrpNCpyChk(CI, Builder, Func); 3537 case LibFunc_memccpy_chk: 3538 return optimizeMemCCpyChk(CI, Builder); 3539 case LibFunc_snprintf_chk: 3540 return optimizeSNPrintfChk(CI, Builder); 3541 case LibFunc_sprintf_chk: 3542 return optimizeSPrintfChk(CI, Builder); 3543 case LibFunc_strcat_chk: 3544 return optimizeStrCatChk(CI, Builder); 3545 case LibFunc_strlcat_chk: 3546 return optimizeStrLCat(CI, Builder); 3547 case LibFunc_strncat_chk: 3548 return optimizeStrNCatChk(CI, Builder); 3549 case LibFunc_strlcpy_chk: 3550 return optimizeStrLCpyChk(CI, Builder); 3551 case LibFunc_vsnprintf_chk: 3552 return optimizeVSNPrintfChk(CI, Builder); 3553 case LibFunc_vsprintf_chk: 3554 return optimizeVSPrintfChk(CI, Builder); 3555 default: 3556 break; 3557 } 3558 return nullptr; 3559 } 3560 3561 FortifiedLibCallSimplifier::FortifiedLibCallSimplifier( 3562 const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize) 3563 : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {} 3564