4662 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the library calls simplifier. It does not implement10// any pass, but can be used by other passes to do simplifications.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Utils/SimplifyLibCalls.h"15#include "llvm/ADT/APFloat.h"16#include "llvm/ADT/APSInt.h"17#include "llvm/ADT/SmallString.h"18#include "llvm/ADT/StringExtras.h"19#include "llvm/Analysis/ConstantFolding.h"20#include "llvm/Analysis/Loads.h"21#include "llvm/Analysis/OptimizationRemarkEmitter.h"22#include "llvm/Analysis/TargetLibraryInfo.h"23#include "llvm/Analysis/Utils/Local.h"24#include "llvm/Analysis/ValueTracking.h"25#include "llvm/IR/AttributeMask.h"26#include "llvm/IR/DataLayout.h"27#include "llvm/IR/Function.h"28#include "llvm/IR/IRBuilder.h"29#include "llvm/IR/IntrinsicInst.h"30#include "llvm/IR/Intrinsics.h"31#include "llvm/IR/Module.h"32#include "llvm/IR/PatternMatch.h"33#include "llvm/Support/Casting.h"34#include "llvm/Support/CommandLine.h"35#include "llvm/Support/KnownBits.h"36#include "llvm/Support/KnownFPClass.h"37#include "llvm/Support/MathExtras.h"38#include "llvm/TargetParser/Triple.h"39#include "llvm/Transforms/Utils/BuildLibCalls.h"40#include "llvm/Transforms/Utils/Local.h"41#include "llvm/Transforms/Utils/SizeOpts.h"42 43#include <cmath>44 45using namespace llvm;46using namespace PatternMatch;47 48static cl::opt<bool>49 EnableUnsafeFPShrink("enable-double-float-shrink", cl::Hidden,50 cl::init(false),51 cl::desc("Enable unsafe double to float "52 "shrinking for math lib calls"));53 54// Enable conversion of operator new calls with a MemProf hot or cold hint55// to an operator new call that takes a hot/cold hint. Off by default since56// not all allocators currently support this extension.57static cl::opt<bool>58 OptimizeHotColdNew("optimize-hot-cold-new", cl::Hidden, cl::init(false),59 cl::desc("Enable hot/cold operator new library calls"));60static cl::opt<bool> OptimizeExistingHotColdNew(61 "optimize-existing-hot-cold-new", cl::Hidden, cl::init(false),62 cl::desc(63 "Enable optimization of existing hot/cold operator new library calls"));64static cl::opt<bool> OptimizeNoBuiltinHotColdNew(65 "optimize-nobuiltin-hot-cold-new-new", cl::Hidden, cl::init(false),66 cl::desc("Enable transformation of nobuiltin operator new library calls"));67 68namespace {69 70// Specialized parser to ensure the hint is an 8 bit value (we can't specify71// uint8_t to opt<> as that is interpreted to mean that we are passing a char72// option with a specific set of values.73struct HotColdHintParser : public cl::parser<unsigned> {74 HotColdHintParser(cl::Option &O) : cl::parser<unsigned>(O) {}75 76 bool parse(cl::Option &O, StringRef ArgName, StringRef Arg, unsigned &Value) {77 if (Arg.getAsInteger(0, Value))78 return O.error("'" + Arg + "' value invalid for uint argument!");79 80 if (Value > 255)81 return O.error("'" + Arg + "' value must be in the range [0, 255]!");82 83 return false;84 }85};86 87} // end anonymous namespace88 89// Hot/cold operator new takes an 8 bit hotness hint, where 0 is the coldest90// and 255 is the hottest. Default to 1 value away from the coldest and hottest91// hints, so that the compiler hinted allocations are slightly less strong than92// manually inserted hints at the two extremes.93static cl::opt<unsigned, false, HotColdHintParser> ColdNewHintValue(94 "cold-new-hint-value", cl::Hidden, cl::init(1),95 cl::desc("Value to pass to hot/cold operator new for cold allocation"));96static cl::opt<unsigned, false, HotColdHintParser>97 NotColdNewHintValue("notcold-new-hint-value", cl::Hidden, cl::init(128),98 cl::desc("Value to pass to hot/cold operator new for "99 "notcold (warm) allocation"));100static cl::opt<unsigned, false, HotColdHintParser> HotNewHintValue(101 "hot-new-hint-value", cl::Hidden, cl::init(254),102 cl::desc("Value to pass to hot/cold operator new for hot allocation"));103static cl::opt<unsigned, false, HotColdHintParser> AmbiguousNewHintValue(104 "ambiguous-new-hint-value", cl::Hidden, cl::init(222),105 cl::desc(106 "Value to pass to hot/cold operator new for ambiguous allocation"));107 108//===----------------------------------------------------------------------===//109// Helper Functions110//===----------------------------------------------------------------------===//111 112static bool ignoreCallingConv(LibFunc Func) {113 return Func == LibFunc_abs || Func == LibFunc_labs ||114 Func == LibFunc_llabs || Func == LibFunc_strlen;115}116 117/// Return true if it is only used in equality comparisons with With.118static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {119 for (User *U : V->users()) {120 if (ICmpInst *IC = dyn_cast<ICmpInst>(U))121 if (IC->isEquality() && IC->getOperand(1) == With)122 continue;123 // Unknown instruction.124 return false;125 }126 return true;127}128 129static bool callHasFloatingPointArgument(const CallInst *CI) {130 return any_of(CI->operands(), [](const Use &OI) {131 return OI->getType()->isFloatingPointTy();132 });133}134 135static bool callHasFP128Argument(const CallInst *CI) {136 return any_of(CI->operands(), [](const Use &OI) {137 return OI->getType()->isFP128Ty();138 });139}140 141// Convert the entire string Str representing an integer in Base, up to142// the terminating nul if present, to a constant according to the rules143// of strtoul[l] or, when AsSigned is set, of strtol[l]. On success144// return the result, otherwise null.145// The function assumes the string is encoded in ASCII and carefully146// avoids converting sequences (including "") that the corresponding147// library call might fail and set errno for.148static Value *convertStrToInt(CallInst *CI, StringRef &Str, Value *EndPtr,149 uint64_t Base, bool AsSigned, IRBuilderBase &B) {150 if (Base < 2 || Base > 36)151 if (Base != 0)152 // Fail for an invalid base (required by POSIX).153 return nullptr;154 155 // Current offset into the original string to reflect in EndPtr.156 size_t Offset = 0;157 // Strip leading whitespace.158 for ( ; Offset != Str.size(); ++Offset)159 if (!isSpace((unsigned char)Str[Offset])) {160 Str = Str.substr(Offset);161 break;162 }163 164 if (Str.empty())165 // Fail for empty subject sequences (POSIX allows but doesn't require166 // strtol[l]/strtoul[l] to fail with EINVAL).167 return nullptr;168 169 // Strip but remember the sign.170 bool Negate = Str[0] == '-';171 if (Str[0] == '-' || Str[0] == '+') {172 Str = Str.drop_front();173 if (Str.empty())174 // Fail for a sign with nothing after it.175 return nullptr;176 ++Offset;177 }178 179 // Set Max to the absolute value of the minimum (for signed), or180 // to the maximum (for unsigned) value representable in the type.181 Type *RetTy = CI->getType();182 unsigned NBits = RetTy->getPrimitiveSizeInBits();183 uint64_t Max = AsSigned && Negate ? 1 : 0;184 Max += AsSigned ? maxIntN(NBits) : maxUIntN(NBits);185 186 // Autodetect Base if it's zero and consume the "0x" prefix.187 if (Str.size() > 1) {188 if (Str[0] == '0') {189 if (toUpper((unsigned char)Str[1]) == 'X') {190 if (Str.size() == 2 || (Base && Base != 16))191 // Fail if Base doesn't allow the "0x" prefix or for the prefix192 // alone that implementations like BSD set errno to EINVAL for.193 return nullptr;194 195 Str = Str.drop_front(2);196 Offset += 2;197 Base = 16;198 }199 else if (Base == 0)200 Base = 8;201 } else if (Base == 0)202 Base = 10;203 }204 else if (Base == 0)205 Base = 10;206 207 // Convert the rest of the subject sequence, not including the sign,208 // to its uint64_t representation (this assumes the source character209 // set is ASCII).210 uint64_t Result = 0;211 for (unsigned i = 0; i != Str.size(); ++i) {212 unsigned char DigVal = Str[i];213 if (isDigit(DigVal))214 DigVal = DigVal - '0';215 else {216 DigVal = toUpper(DigVal);217 if (isAlpha(DigVal))218 DigVal = DigVal - 'A' + 10;219 else220 return nullptr;221 }222 223 if (DigVal >= Base)224 // Fail if the digit is not valid in the Base.225 return nullptr;226 227 // Add the digit and fail if the result is not representable in228 // the (unsigned form of the) destination type.229 bool VFlow;230 Result = SaturatingMultiplyAdd(Result, Base, (uint64_t)DigVal, &VFlow);231 if (VFlow || Result > Max)232 return nullptr;233 }234 235 if (EndPtr) {236 // Store the pointer to the end.237 Value *Off = B.getInt64(Offset + Str.size());238 Value *StrBeg = CI->getArgOperand(0);239 Value *StrEnd = B.CreateInBoundsGEP(B.getInt8Ty(), StrBeg, Off, "endptr");240 B.CreateStore(StrEnd, EndPtr);241 }242 243 if (Negate)244 // Unsigned negation doesn't overflow.245 Result = -Result;246 247 return ConstantInt::get(RetTy, Result);248}249 250static bool isOnlyUsedInComparisonWithZero(Value *V) {251 for (User *U : V->users()) {252 if (ICmpInst *IC = dyn_cast<ICmpInst>(U))253 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))254 if (C->isNullValue())255 continue;256 // Unknown instruction.257 return false;258 }259 return true;260}261 262static bool canTransformToMemCmp(CallInst *CI, Value *Str, uint64_t Len,263 const DataLayout &DL) {264 if (!isOnlyUsedInComparisonWithZero(CI))265 return false;266 267 if (!isDereferenceableAndAlignedPointer(Str, Align(1), APInt(64, Len), DL))268 return false;269 270 if (CI->getFunction()->hasFnAttribute(Attribute::SanitizeMemory))271 return false;272 273 return true;274}275 276static void annotateDereferenceableBytes(CallInst *CI,277 ArrayRef<unsigned> ArgNos,278 uint64_t DereferenceableBytes) {279 const Function *F = CI->getCaller();280 if (!F)281 return;282 for (unsigned ArgNo : ArgNos) {283 uint64_t DerefBytes = DereferenceableBytes;284 unsigned AS = CI->getArgOperand(ArgNo)->getType()->getPointerAddressSpace();285 if (!llvm::NullPointerIsDefined(F, AS) ||286 CI->paramHasAttr(ArgNo, Attribute::NonNull))287 DerefBytes = std::max(CI->getParamDereferenceableOrNullBytes(ArgNo),288 DereferenceableBytes);289 290 if (CI->getParamDereferenceableBytes(ArgNo) < DerefBytes) {291 CI->removeParamAttr(ArgNo, Attribute::Dereferenceable);292 if (!llvm::NullPointerIsDefined(F, AS) ||293 CI->paramHasAttr(ArgNo, Attribute::NonNull))294 CI->removeParamAttr(ArgNo, Attribute::DereferenceableOrNull);295 CI->addParamAttr(ArgNo, Attribute::getWithDereferenceableBytes(296 CI->getContext(), DerefBytes));297 }298 }299}300 301static void annotateNonNullNoUndefBasedOnAccess(CallInst *CI,302 ArrayRef<unsigned> ArgNos) {303 Function *F = CI->getCaller();304 if (!F)305 return;306 307 for (unsigned ArgNo : ArgNos) {308 if (!CI->paramHasAttr(ArgNo, Attribute::NoUndef))309 CI->addParamAttr(ArgNo, Attribute::NoUndef);310 311 if (!CI->paramHasAttr(ArgNo, Attribute::NonNull)) {312 unsigned AS =313 CI->getArgOperand(ArgNo)->getType()->getPointerAddressSpace();314 if (llvm::NullPointerIsDefined(F, AS))315 continue;316 CI->addParamAttr(ArgNo, Attribute::NonNull);317 }318 319 annotateDereferenceableBytes(CI, ArgNo, 1);320 }321}322 323static void annotateNonNullAndDereferenceable(CallInst *CI, ArrayRef<unsigned> ArgNos,324 Value *Size, const DataLayout &DL) {325 if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {326 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos);327 annotateDereferenceableBytes(CI, ArgNos, LenC->getZExtValue());328 } else if (isKnownNonZero(Size, DL)) {329 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos);330 uint64_t X, Y;331 uint64_t DerefMin = 1;332 if (match(Size, m_Select(m_Value(), m_ConstantInt(X), m_ConstantInt(Y)))) {333 DerefMin = std::min(X, Y);334 annotateDereferenceableBytes(CI, ArgNos, DerefMin);335 }336 }337}338 339// Copy CallInst "flags" like musttail, notail, and tail. Return New param for340// easier chaining. Calls to emit* and B.createCall should probably be wrapped341// in this function when New is created to replace Old. Callers should take342// care to check Old.isMustTailCall() if they aren't replacing Old directly343// with New.344static Value *copyFlags(const CallInst &Old, Value *New) {345 assert(!Old.isMustTailCall() && "do not copy musttail call flags");346 assert(!Old.isNoTailCall() && "do not copy notail call flags");347 if (auto *NewCI = dyn_cast_or_null<CallInst>(New))348 NewCI->setTailCallKind(Old.getTailCallKind());349 return New;350}351 352static Value *mergeAttributesAndFlags(CallInst *NewCI, const CallInst &Old) {353 NewCI->setAttributes(AttributeList::get(354 NewCI->getContext(), {NewCI->getAttributes(), Old.getAttributes()}));355 NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(356 NewCI->getType(), NewCI->getRetAttributes()));357 for (unsigned I = 0; I < NewCI->arg_size(); ++I)358 NewCI->removeParamAttrs(359 I, AttributeFuncs::typeIncompatible(NewCI->getArgOperand(I)->getType(),360 NewCI->getParamAttributes(I)));361 362 return copyFlags(Old, NewCI);363}364 365// Helper to avoid truncating the length if size_t is 32-bits.366static StringRef substr(StringRef Str, uint64_t Len) {367 return Len >= Str.size() ? Str : Str.substr(0, Len);368}369 370//===----------------------------------------------------------------------===//371// String and Memory Library Call Optimizations372//===----------------------------------------------------------------------===//373 374Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilderBase &B) {375 // Extract some information from the instruction376 Value *Dst = CI->getArgOperand(0);377 Value *Src = CI->getArgOperand(1);378 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});379 380 // See if we can get the length of the input string.381 uint64_t Len = GetStringLength(Src);382 if (Len)383 annotateDereferenceableBytes(CI, 1, Len);384 else385 return nullptr;386 --Len; // Unbias length.387 388 // Handle the simple, do-nothing case: strcat(x, "") -> x389 if (Len == 0)390 return Dst;391 392 return copyFlags(*CI, emitStrLenMemCpy(Src, Dst, Len, B));393}394 395Value *LibCallSimplifier::emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,396 IRBuilderBase &B) {397 // We need to find the end of the destination string. That's where the398 // memory is to be moved to. We just generate a call to strlen.399 Value *DstLen = emitStrLen(Dst, B, DL, TLI);400 if (!DstLen)401 return nullptr;402 403 // Now that we have the destination's length, we must index into the404 // destination's pointer to get the actual memcpy destination (end of405 // the string .. we're concatenating).406 Value *CpyDst = B.CreateInBoundsGEP(B.getInt8Ty(), Dst, DstLen, "endptr");407 408 // We have enough information to now generate the memcpy call to do the409 // concatenation for us. Make a memcpy to copy the nul byte with align = 1.410 B.CreateMemCpy(CpyDst, Align(1), Src, Align(1),411 TLI->getAsSizeT(Len + 1, *B.GetInsertBlock()->getModule()));412 return Dst;413}414 415Value *LibCallSimplifier::optimizeStrNCat(CallInst *CI, IRBuilderBase &B) {416 // Extract some information from the instruction.417 Value *Dst = CI->getArgOperand(0);418 Value *Src = CI->getArgOperand(1);419 Value *Size = CI->getArgOperand(2);420 uint64_t Len;421 annotateNonNullNoUndefBasedOnAccess(CI, 0);422 if (isKnownNonZero(Size, DL))423 annotateNonNullNoUndefBasedOnAccess(CI, 1);424 425 // We don't do anything if length is not constant.426 ConstantInt *LengthArg = dyn_cast<ConstantInt>(Size);427 if (LengthArg) {428 Len = LengthArg->getZExtValue();429 // strncat(x, c, 0) -> x430 if (!Len)431 return Dst;432 } else {433 return nullptr;434 }435 436 // See if we can get the length of the input string.437 uint64_t SrcLen = GetStringLength(Src);438 if (SrcLen) {439 annotateDereferenceableBytes(CI, 1, SrcLen);440 --SrcLen; // Unbias length.441 } else {442 return nullptr;443 }444 445 // strncat(x, "", c) -> x446 if (SrcLen == 0)447 return Dst;448 449 // We don't optimize this case.450 if (Len < SrcLen)451 return nullptr;452 453 // strncat(x, s, c) -> strcat(x, s)454 // s is constant so the strcat can be optimized further.455 return copyFlags(*CI, emitStrLenMemCpy(Src, Dst, SrcLen, B));456}457 458// Helper to transform memchr(S, C, N) == S to N && *S == C and, when459// NBytes is null, strchr(S, C) to *S == C. A precondition of the function460// is that either S is dereferenceable or the value of N is nonzero.461static Value* memChrToCharCompare(CallInst *CI, Value *NBytes,462 IRBuilderBase &B, const DataLayout &DL)463{464 Value *Src = CI->getArgOperand(0);465 Value *CharVal = CI->getArgOperand(1);466 467 // Fold memchr(A, C, N) == A to N && *A == C.468 Type *CharTy = B.getInt8Ty();469 Value *Char0 = B.CreateLoad(CharTy, Src);470 CharVal = B.CreateTrunc(CharVal, CharTy);471 Value *Cmp = B.CreateICmpEQ(Char0, CharVal, "char0cmp");472 473 if (NBytes) {474 Value *Zero = ConstantInt::get(NBytes->getType(), 0);475 Value *And = B.CreateICmpNE(NBytes, Zero);476 Cmp = B.CreateLogicalAnd(And, Cmp);477 }478 479 Value *NullPtr = Constant::getNullValue(CI->getType());480 return B.CreateSelect(Cmp, Src, NullPtr);481}482 483Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilderBase &B) {484 Value *SrcStr = CI->getArgOperand(0);485 Value *CharVal = CI->getArgOperand(1);486 annotateNonNullNoUndefBasedOnAccess(CI, 0);487 488 if (isOnlyUsedInEqualityComparison(CI, SrcStr))489 return memChrToCharCompare(CI, nullptr, B, DL);490 491 // If the second operand is non-constant, see if we can compute the length492 // of the input string and turn this into memchr.493 ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);494 if (!CharC) {495 uint64_t Len = GetStringLength(SrcStr);496 if (Len)497 annotateDereferenceableBytes(CI, 0, Len);498 else499 return nullptr;500 501 Function *Callee = CI->getCalledFunction();502 FunctionType *FT = Callee->getFunctionType();503 unsigned IntBits = TLI->getIntSize();504 if (!FT->getParamType(1)->isIntegerTy(IntBits)) // memchr needs 'int'.505 return nullptr;506 507 unsigned SizeTBits = TLI->getSizeTSize(*CI->getModule());508 Type *SizeTTy = IntegerType::get(CI->getContext(), SizeTBits);509 return copyFlags(*CI,510 emitMemChr(SrcStr, CharVal, // include nul.511 ConstantInt::get(SizeTTy, Len), B,512 DL, TLI));513 }514 515 if (CharC->isZero()) {516 Value *NullPtr = Constant::getNullValue(CI->getType());517 if (isOnlyUsedInEqualityComparison(CI, NullPtr))518 // Pre-empt the transformation to strlen below and fold519 // strchr(A, '\0') == null to false.520 return B.CreateIntToPtr(B.getTrue(), CI->getType());521 }522 523 // Otherwise, the character is a constant, see if the first argument is524 // a string literal. If so, we can constant fold.525 StringRef Str;526 if (!getConstantStringInfo(SrcStr, Str)) {527 if (CharC->isZero()) // strchr(p, 0) -> p + strlen(p)528 if (Value *StrLen = emitStrLen(SrcStr, B, DL, TLI))529 return B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, StrLen, "strchr");530 return nullptr;531 }532 533 // Compute the offset, make sure to handle the case when we're searching for534 // zero (a weird way to spell strlen).535 size_t I = (0xFF & CharC->getSExtValue()) == 0536 ? Str.size()537 : Str.find(CharC->getSExtValue());538 if (I == StringRef::npos) // Didn't find the char. strchr returns null.539 return Constant::getNullValue(CI->getType());540 541 // strchr(s+n,c) -> gep(s+n+i,c)542 return B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strchr");543}544 545Value *LibCallSimplifier::optimizeStrRChr(CallInst *CI, IRBuilderBase &B) {546 Value *SrcStr = CI->getArgOperand(0);547 Value *CharVal = CI->getArgOperand(1);548 ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);549 annotateNonNullNoUndefBasedOnAccess(CI, 0);550 551 StringRef Str;552 if (!getConstantStringInfo(SrcStr, Str)) {553 // strrchr(s, 0) -> strchr(s, 0)554 if (CharC && CharC->isZero())555 return copyFlags(*CI, emitStrChr(SrcStr, '\0', B, TLI));556 return nullptr;557 }558 559 unsigned SizeTBits = TLI->getSizeTSize(*CI->getModule());560 Type *SizeTTy = IntegerType::get(CI->getContext(), SizeTBits);561 562 // Try to expand strrchr to the memrchr nonstandard extension if it's563 // available, or simply fail otherwise.564 uint64_t NBytes = Str.size() + 1; // Include the terminating nul.565 Value *Size = ConstantInt::get(SizeTTy, NBytes);566 return copyFlags(*CI, emitMemRChr(SrcStr, CharVal, Size, B, DL, TLI));567}568 569Value *LibCallSimplifier::optimizeStrCmp(CallInst *CI, IRBuilderBase &B) {570 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);571 if (Str1P == Str2P) // strcmp(x,x) -> 0572 return ConstantInt::get(CI->getType(), 0);573 574 StringRef Str1, Str2;575 bool HasStr1 = getConstantStringInfo(Str1P, Str1);576 bool HasStr2 = getConstantStringInfo(Str2P, Str2);577 578 // strcmp(x, y) -> cnst (if both x and y are constant strings)579 if (HasStr1 && HasStr2)580 return ConstantInt::get(CI->getType(),581 std::clamp(Str1.compare(Str2), -1, 1));582 583 if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x584 return B.CreateNeg(B.CreateZExt(585 B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType()));586 587 if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x588 return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"),589 CI->getType());590 591 // strcmp(P, "x") -> memcmp(P, "x", 2)592 uint64_t Len1 = GetStringLength(Str1P);593 if (Len1)594 annotateDereferenceableBytes(CI, 0, Len1);595 uint64_t Len2 = GetStringLength(Str2P);596 if (Len2)597 annotateDereferenceableBytes(CI, 1, Len2);598 599 if (Len1 && Len2) {600 return copyFlags(601 *CI, emitMemCmp(Str1P, Str2P,602 TLI->getAsSizeT(std::min(Len1, Len2), *CI->getModule()),603 B, DL, TLI));604 }605 606 // strcmp to memcmp607 if (!HasStr1 && HasStr2) {608 if (canTransformToMemCmp(CI, Str1P, Len2, DL))609 return copyFlags(*CI, emitMemCmp(Str1P, Str2P,610 TLI->getAsSizeT(Len2, *CI->getModule()),611 B, DL, TLI));612 } else if (HasStr1 && !HasStr2) {613 if (canTransformToMemCmp(CI, Str2P, Len1, DL))614 return copyFlags(*CI, emitMemCmp(Str1P, Str2P,615 TLI->getAsSizeT(Len1, *CI->getModule()),616 B, DL, TLI));617 }618 619 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});620 return nullptr;621}622 623// Optimize a memcmp or, when StrNCmp is true, strncmp call CI with constant624// arrays LHS and RHS and nonconstant Size.625static Value *optimizeMemCmpVarSize(CallInst *CI, Value *LHS, Value *RHS,626 Value *Size, bool StrNCmp,627 IRBuilderBase &B, const DataLayout &DL);628 629Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilderBase &B) {630 Value *Str1P = CI->getArgOperand(0);631 Value *Str2P = CI->getArgOperand(1);632 Value *Size = CI->getArgOperand(2);633 if (Str1P == Str2P) // strncmp(x,x,n) -> 0634 return ConstantInt::get(CI->getType(), 0);635 636 if (isKnownNonZero(Size, DL))637 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});638 // Get the length argument if it is constant.639 uint64_t Length;640 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(Size))641 Length = LengthArg->getZExtValue();642 else643 return optimizeMemCmpVarSize(CI, Str1P, Str2P, Size, true, B, DL);644 645 if (Length == 0) // strncmp(x,y,0) -> 0646 return ConstantInt::get(CI->getType(), 0);647 648 if (Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)649 return copyFlags(*CI, emitMemCmp(Str1P, Str2P, Size, B, DL, TLI));650 651 StringRef Str1, Str2;652 bool HasStr1 = getConstantStringInfo(Str1P, Str1);653 bool HasStr2 = getConstantStringInfo(Str2P, Str2);654 655 // strncmp(x, y) -> cnst (if both x and y are constant strings)656 if (HasStr1 && HasStr2) {657 // Avoid truncating the 64-bit Length to 32 bits in ILP32.658 StringRef SubStr1 = substr(Str1, Length);659 StringRef SubStr2 = substr(Str2, Length);660 return ConstantInt::get(CI->getType(),661 std::clamp(SubStr1.compare(SubStr2), -1, 1));662 }663 664 if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x665 return B.CreateNeg(B.CreateZExt(666 B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType()));667 668 if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x669 return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"),670 CI->getType());671 672 uint64_t Len1 = GetStringLength(Str1P);673 if (Len1)674 annotateDereferenceableBytes(CI, 0, Len1);675 uint64_t Len2 = GetStringLength(Str2P);676 if (Len2)677 annotateDereferenceableBytes(CI, 1, Len2);678 679 // strncmp to memcmp680 if (!HasStr1 && HasStr2) {681 Len2 = std::min(Len2, Length);682 if (canTransformToMemCmp(CI, Str1P, Len2, DL))683 return copyFlags(*CI, emitMemCmp(Str1P, Str2P,684 TLI->getAsSizeT(Len2, *CI->getModule()),685 B, DL, TLI));686 } else if (HasStr1 && !HasStr2) {687 Len1 = std::min(Len1, Length);688 if (canTransformToMemCmp(CI, Str2P, Len1, DL))689 return copyFlags(*CI, emitMemCmp(Str1P, Str2P,690 TLI->getAsSizeT(Len1, *CI->getModule()),691 B, DL, TLI));692 }693 694 return nullptr;695}696 697Value *LibCallSimplifier::optimizeStrNDup(CallInst *CI, IRBuilderBase &B) {698 Value *Src = CI->getArgOperand(0);699 ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1));700 uint64_t SrcLen = GetStringLength(Src);701 if (SrcLen && Size) {702 annotateDereferenceableBytes(CI, 0, SrcLen);703 if (SrcLen <= Size->getZExtValue() + 1)704 return copyFlags(*CI, emitStrDup(Src, B, TLI));705 }706 707 return nullptr;708}709 710Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilderBase &B) {711 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);712 if (Dst == Src) // strcpy(x,x) -> x713 return Src;714 715 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});716 // See if we can get the length of the input string.717 uint64_t Len = GetStringLength(Src);718 if (Len)719 annotateDereferenceableBytes(CI, 1, Len);720 else721 return nullptr;722 723 // We have enough information to now generate the memcpy call to do the724 // copy for us. Make a memcpy to copy the nul byte with align = 1.725 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1),726 TLI->getAsSizeT(Len, *CI->getModule()));727 mergeAttributesAndFlags(NewCI, *CI);728 return Dst;729}730 731Value *LibCallSimplifier::optimizeStpCpy(CallInst *CI, IRBuilderBase &B) {732 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);733 734 // stpcpy(d,s) -> strcpy(d,s) if the result is not used.735 if (CI->use_empty())736 return copyFlags(*CI, emitStrCpy(Dst, Src, B, TLI));737 738 if (Dst == Src) { // stpcpy(x,x) -> x+strlen(x)739 Value *StrLen = emitStrLen(Src, B, DL, TLI);740 return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;741 }742 743 // See if we can get the length of the input string.744 uint64_t Len = GetStringLength(Src);745 if (Len)746 annotateDereferenceableBytes(CI, 1, Len);747 else748 return nullptr;749 750 Value *LenV = TLI->getAsSizeT(Len, *CI->getModule());751 Value *DstEnd = B.CreateInBoundsGEP(752 B.getInt8Ty(), Dst, TLI->getAsSizeT(Len - 1, *CI->getModule()));753 754 // We have enough information to now generate the memcpy call to do the755 // copy for us. Make a memcpy to copy the nul byte with align = 1.756 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1), LenV);757 mergeAttributesAndFlags(NewCI, *CI);758 return DstEnd;759}760 761// Optimize a call to size_t strlcpy(char*, const char*, size_t).762 763Value *LibCallSimplifier::optimizeStrLCpy(CallInst *CI, IRBuilderBase &B) {764 Value *Size = CI->getArgOperand(2);765 if (isKnownNonZero(Size, DL))766 // Like snprintf, the function stores into the destination only when767 // the size argument is nonzero.768 annotateNonNullNoUndefBasedOnAccess(CI, 0);769 // The function reads the source argument regardless of Size (it returns770 // its length).771 annotateNonNullNoUndefBasedOnAccess(CI, 1);772 773 uint64_t NBytes;774 if (ConstantInt *SizeC = dyn_cast<ConstantInt>(Size))775 NBytes = SizeC->getZExtValue();776 else777 return nullptr;778 779 Value *Dst = CI->getArgOperand(0);780 Value *Src = CI->getArgOperand(1);781 if (NBytes <= 1) {782 if (NBytes == 1)783 // For a call to strlcpy(D, S, 1) first store a nul in *D.784 B.CreateStore(B.getInt8(0), Dst);785 786 // Transform strlcpy(D, S, 0) to a call to strlen(S).787 return copyFlags(*CI, emitStrLen(Src, B, DL, TLI));788 }789 790 // Try to determine the length of the source, substituting its size791 // when it's not nul-terminated (as it's required to be) to avoid792 // reading past its end.793 StringRef Str;794 if (!getConstantStringInfo(Src, Str, /*TrimAtNul=*/false))795 return nullptr;796 797 uint64_t SrcLen = Str.find('\0');798 // Set if the terminating nul should be copied by the call to memcpy799 // below.800 bool NulTerm = SrcLen < NBytes;801 802 if (NulTerm)803 // Overwrite NBytes with the number of bytes to copy, including804 // the terminating nul.805 NBytes = SrcLen + 1;806 else {807 // Set the length of the source for the function to return to its808 // size, and cap NBytes at the same.809 SrcLen = std::min(SrcLen, uint64_t(Str.size()));810 NBytes = std::min(NBytes - 1, SrcLen);811 }812 813 if (SrcLen == 0) {814 // Transform strlcpy(D, "", N) to (*D = '\0, 0).815 B.CreateStore(B.getInt8(0), Dst);816 return ConstantInt::get(CI->getType(), 0);817 }818 819 // Transform strlcpy(D, S, N) to memcpy(D, S, N') where N' is the lower820 // bound on strlen(S) + 1 and N, optionally followed by a nul store to821 // D[N' - 1] if necessary.822 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1),823 TLI->getAsSizeT(NBytes, *CI->getModule()));824 mergeAttributesAndFlags(NewCI, *CI);825 826 if (!NulTerm) {827 Value *EndOff = ConstantInt::get(CI->getType(), NBytes);828 Value *EndPtr = B.CreateInBoundsGEP(B.getInt8Ty(), Dst, EndOff);829 B.CreateStore(B.getInt8(0), EndPtr);830 }831 832 // Like snprintf, strlcpy returns the number of nonzero bytes that would833 // have been copied if the bound had been sufficiently big (which in this834 // case is strlen(Src)).835 return ConstantInt::get(CI->getType(), SrcLen);836}837 838// Optimize a call CI to either stpncpy when RetEnd is true, or to strncpy839// otherwise.840Value *LibCallSimplifier::optimizeStringNCpy(CallInst *CI, bool RetEnd,841 IRBuilderBase &B) {842 Value *Dst = CI->getArgOperand(0);843 Value *Src = CI->getArgOperand(1);844 Value *Size = CI->getArgOperand(2);845 846 if (isKnownNonZero(Size, DL)) {847 // Both st{p,r}ncpy(D, S, N) access the source and destination arrays848 // only when N is nonzero.849 annotateNonNullNoUndefBasedOnAccess(CI, 0);850 annotateNonNullNoUndefBasedOnAccess(CI, 1);851 }852 853 // If the "bound" argument is known set N to it. Otherwise set it to854 // UINT64_MAX and handle it later.855 uint64_t N = UINT64_MAX;856 if (ConstantInt *SizeC = dyn_cast<ConstantInt>(Size))857 N = SizeC->getZExtValue();858 859 if (N == 0)860 // Fold st{p,r}ncpy(D, S, 0) to D.861 return Dst;862 863 if (N == 1) {864 Type *CharTy = B.getInt8Ty();865 Value *CharVal = B.CreateLoad(CharTy, Src, "stxncpy.char0");866 B.CreateStore(CharVal, Dst);867 if (!RetEnd)868 // Transform strncpy(D, S, 1) to return (*D = *S), D.869 return Dst;870 871 // Transform stpncpy(D, S, 1) to return (*D = *S) ? D + 1 : D.872 Value *ZeroChar = ConstantInt::get(CharTy, 0);873 Value *Cmp = B.CreateICmpEQ(CharVal, ZeroChar, "stpncpy.char0cmp");874 875 Value *Off1 = B.getInt32(1);876 Value *EndPtr = B.CreateInBoundsGEP(CharTy, Dst, Off1, "stpncpy.end");877 return B.CreateSelect(Cmp, Dst, EndPtr, "stpncpy.sel");878 }879 880 // If the length of the input string is known set SrcLen to it.881 uint64_t SrcLen = GetStringLength(Src);882 if (SrcLen)883 annotateDereferenceableBytes(CI, 1, SrcLen);884 else885 return nullptr;886 887 --SrcLen; // Unbias length.888 889 if (SrcLen == 0) {890 // Transform st{p,r}ncpy(D, "", N) to memset(D, '\0', N) for any N.891 Align MemSetAlign =892 CI->getAttributes().getParamAttrs(0).getAlignment().valueOrOne();893 CallInst *NewCI = B.CreateMemSet(Dst, B.getInt8('\0'), Size, MemSetAlign);894 AttrBuilder ArgAttrs(CI->getContext(), CI->getAttributes().getParamAttrs(0));895 NewCI->setAttributes(NewCI->getAttributes().addParamAttributes(896 CI->getContext(), 0, ArgAttrs));897 copyFlags(*CI, NewCI);898 return Dst;899 }900 901 if (N > SrcLen + 1) {902 if (N > 128)903 // Bail if N is large or unknown.904 return nullptr;905 906 // st{p,r}ncpy(D, "a", N) -> memcpy(D, "a\0\0\0", N) for N <= 128.907 StringRef Str;908 if (!getConstantStringInfo(Src, Str))909 return nullptr;910 std::string SrcStr = Str.str();911 // Create a bigger, nul-padded array with the same length, SrcLen,912 // as the original string.913 SrcStr.resize(N, '\0');914 Src = B.CreateGlobalString(SrcStr, "str", /*AddressSpace=*/0,915 /*M=*/nullptr, /*AddNull=*/false);916 }917 918 // st{p,r}ncpy(D, S, N) -> memcpy(align 1 D, align 1 S, N) when both919 // S and N are constant.920 CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1),921 TLI->getAsSizeT(N, *CI->getModule()));922 mergeAttributesAndFlags(NewCI, *CI);923 if (!RetEnd)924 return Dst;925 926 // stpncpy(D, S, N) returns the address of the first null in D if it writes927 // one, otherwise D + N.928 Value *Off = B.getInt64(std::min(SrcLen, N));929 return B.CreateInBoundsGEP(B.getInt8Ty(), Dst, Off, "endptr");930}931 932Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,933 unsigned CharSize,934 Value *Bound) {935 Value *Src = CI->getArgOperand(0);936 Type *CharTy = B.getIntNTy(CharSize);937 938 if (isOnlyUsedInZeroEqualityComparison(CI) &&939 (!Bound || isKnownNonZero(Bound, DL))) {940 // Fold strlen:941 // strlen(x) != 0 --> *x != 0942 // strlen(x) == 0 --> *x == 0943 // and likewise strnlen with constant N > 0:944 // strnlen(x, N) != 0 --> *x != 0945 // strnlen(x, N) == 0 --> *x == 0946 return B.CreateZExt(B.CreateLoad(CharTy, Src, "char0"),947 CI->getType());948 }949 950 if (Bound) {951 if (ConstantInt *BoundCst = dyn_cast<ConstantInt>(Bound)) {952 if (BoundCst->isZero())953 // Fold strnlen(s, 0) -> 0 for any s, constant or otherwise.954 return ConstantInt::get(CI->getType(), 0);955 956 if (BoundCst->isOne()) {957 // Fold strnlen(s, 1) -> *s ? 1 : 0 for any s.958 Value *CharVal = B.CreateLoad(CharTy, Src, "strnlen.char0");959 Value *ZeroChar = ConstantInt::get(CharTy, 0);960 Value *Cmp = B.CreateICmpNE(CharVal, ZeroChar, "strnlen.char0cmp");961 return B.CreateZExt(Cmp, CI->getType());962 }963 }964 }965 966 if (uint64_t Len = GetStringLength(Src, CharSize)) {967 Value *LenC = ConstantInt::get(CI->getType(), Len - 1);968 // Fold strlen("xyz") -> 3 and strnlen("xyz", 2) -> 2969 // and strnlen("xyz", Bound) -> min(3, Bound) for nonconstant Bound.970 if (Bound)971 return B.CreateBinaryIntrinsic(Intrinsic::umin, LenC, Bound);972 return LenC;973 }974 975 if (Bound)976 // Punt for strnlen for now.977 return nullptr;978 979 // If s is a constant pointer pointing to a string literal, we can fold980 // strlen(s + x) to strlen(s) - x, when x is known to be in the range981 // [0, strlen(s)] or the string has a single null terminator '\0' at the end.982 // We only try to simplify strlen when the pointer s points to an array983 // of CharSize elements. Otherwise, we would need to scale the offset x before984 // doing the subtraction. This will make the optimization more complex, and985 // it's not very useful because calling strlen for a pointer of other types is986 // very uncommon.987 if (GEPOperator *GEP = dyn_cast<GEPOperator>(Src)) {988 unsigned BW = DL.getIndexTypeSizeInBits(GEP->getType());989 SmallMapVector<Value *, APInt, 4> VarOffsets;990 APInt ConstOffset(BW, 0);991 assert(CharSize % 8 == 0 && "Expected a multiple of 8 sized CharSize");992 // Check the gep is a single variable offset.993 if (!GEP->collectOffset(DL, BW, VarOffsets, ConstOffset) ||994 VarOffsets.size() != 1 || ConstOffset != 0 ||995 VarOffsets.begin()->second != CharSize / 8)996 return nullptr;997 998 ConstantDataArraySlice Slice;999 if (getConstantDataArrayInfo(GEP->getOperand(0), Slice, CharSize)) {1000 uint64_t NullTermIdx;1001 if (Slice.Array == nullptr) {1002 NullTermIdx = 0;1003 } else {1004 NullTermIdx = ~((uint64_t)0);1005 for (uint64_t I = 0, E = Slice.Length; I < E; ++I) {1006 if (Slice.Array->getElementAsInteger(I + Slice.Offset) == 0) {1007 NullTermIdx = I;1008 break;1009 }1010 }1011 // If the string does not have '\0', leave it to strlen to compute1012 // its length.1013 if (NullTermIdx == ~((uint64_t)0))1014 return nullptr;1015 }1016 1017 Value *Offset = VarOffsets.begin()->first;1018 KnownBits Known = computeKnownBits(Offset, DL, nullptr, CI, nullptr);1019 1020 // If Offset is not provably in the range [0, NullTermIdx], we can still1021 // optimize if we can prove that the program has undefined behavior when1022 // Offset is outside that range. That is the case when GEP->getOperand(0)1023 // is a pointer to an object whose memory extent is NullTermIdx+1.1024 if ((Known.isNonNegative() && Known.getMaxValue().ule(NullTermIdx)) ||1025 (isa<GlobalVariable>(GEP->getOperand(0)) &&1026 NullTermIdx == Slice.Length - 1)) {1027 Offset = B.CreateSExtOrTrunc(Offset, CI->getType());1028 return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx),1029 Offset);1030 }1031 }1032 }1033 1034 // strlen(x?"foo":"bars") --> x ? 3 : 41035 if (SelectInst *SI = dyn_cast<SelectInst>(Src)) {1036 uint64_t LenTrue = GetStringLength(SI->getTrueValue(), CharSize);1037 uint64_t LenFalse = GetStringLength(SI->getFalseValue(), CharSize);1038 if (LenTrue && LenFalse) {1039 ORE.emit([&]() {1040 return OptimizationRemark("instcombine", "simplify-libcalls", CI)1041 << "folded strlen(select) to select of constants";1042 });1043 return B.CreateSelect(SI->getCondition(),1044 ConstantInt::get(CI->getType(), LenTrue - 1),1045 ConstantInt::get(CI->getType(), LenFalse - 1));1046 }1047 }1048 1049 return nullptr;1050}1051 1052Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilderBase &B) {1053 if (Value *V = optimizeStringLength(CI, B, 8))1054 return V;1055 annotateNonNullNoUndefBasedOnAccess(CI, 0);1056 return nullptr;1057}1058 1059Value *LibCallSimplifier::optimizeStrNLen(CallInst *CI, IRBuilderBase &B) {1060 Value *Bound = CI->getArgOperand(1);1061 if (Value *V = optimizeStringLength(CI, B, 8, Bound))1062 return V;1063 1064 if (isKnownNonZero(Bound, DL))1065 annotateNonNullNoUndefBasedOnAccess(CI, 0);1066 return nullptr;1067}1068 1069Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilderBase &B) {1070 Module &M = *CI->getModule();1071 unsigned WCharSize = TLI->getWCharSize(M) * 8;1072 // We cannot perform this optimization without wchar_size metadata.1073 if (WCharSize == 0)1074 return nullptr;1075 1076 return optimizeStringLength(CI, B, WCharSize);1077}1078 1079Value *LibCallSimplifier::optimizeStrPBrk(CallInst *CI, IRBuilderBase &B) {1080 StringRef S1, S2;1081 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);1082 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);1083 1084 // strpbrk(s, "") -> nullptr1085 // strpbrk("", s) -> nullptr1086 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))1087 return Constant::getNullValue(CI->getType());1088 1089 // Constant folding.1090 if (HasS1 && HasS2) {1091 size_t I = S1.find_first_of(S2);1092 if (I == StringRef::npos) // No match.1093 return Constant::getNullValue(CI->getType());1094 1095 return B.CreateInBoundsGEP(B.getInt8Ty(), CI->getArgOperand(0),1096 B.getInt64(I), "strpbrk");1097 }1098 1099 // strpbrk(s, "a") -> strchr(s, 'a')1100 if (HasS2 && S2.size() == 1)1101 return copyFlags(*CI, emitStrChr(CI->getArgOperand(0), S2[0], B, TLI));1102 1103 return nullptr;1104}1105 1106Value *LibCallSimplifier::optimizeStrTo(CallInst *CI, IRBuilderBase &B) {1107 Value *EndPtr = CI->getArgOperand(1);1108 if (isa<ConstantPointerNull>(EndPtr)) {1109 // With a null EndPtr, this function won't capture the main argument.1110 // It would be readonly too, except that it still may write to errno.1111 CI->addParamAttr(0, Attribute::getWithCaptureInfo(CI->getContext(),1112 CaptureInfo::none()));1113 }1114 1115 return nullptr;1116}1117 1118Value *LibCallSimplifier::optimizeStrSpn(CallInst *CI, IRBuilderBase &B) {1119 StringRef S1, S2;1120 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);1121 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);1122 1123 // strspn(s, "") -> 01124 // strspn("", s) -> 01125 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))1126 return Constant::getNullValue(CI->getType());1127 1128 // Constant folding.1129 if (HasS1 && HasS2) {1130 size_t Pos = S1.find_first_not_of(S2);1131 if (Pos == StringRef::npos)1132 Pos = S1.size();1133 return ConstantInt::get(CI->getType(), Pos);1134 }1135 1136 return nullptr;1137}1138 1139Value *LibCallSimplifier::optimizeStrCSpn(CallInst *CI, IRBuilderBase &B) {1140 StringRef S1, S2;1141 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);1142 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);1143 1144 // strcspn("", s) -> 01145 if (HasS1 && S1.empty())1146 return Constant::getNullValue(CI->getType());1147 1148 // Constant folding.1149 if (HasS1 && HasS2) {1150 size_t Pos = S1.find_first_of(S2);1151 if (Pos == StringRef::npos)1152 Pos = S1.size();1153 return ConstantInt::get(CI->getType(), Pos);1154 }1155 1156 // strcspn(s, "") -> strlen(s)1157 if (HasS2 && S2.empty())1158 return copyFlags(*CI, emitStrLen(CI->getArgOperand(0), B, DL, TLI));1159 1160 return nullptr;1161}1162 1163Value *LibCallSimplifier::optimizeStrStr(CallInst *CI, IRBuilderBase &B) {1164 // fold strstr(x, x) -> x.1165 if (CI->getArgOperand(0) == CI->getArgOperand(1))1166 return CI->getArgOperand(0);1167 1168 // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 01169 if (isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {1170 Value *StrLen = emitStrLen(CI->getArgOperand(1), B, DL, TLI);1171 if (!StrLen)1172 return nullptr;1173 Value *StrNCmp = emitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),1174 StrLen, B, DL, TLI);1175 if (!StrNCmp)1176 return nullptr;1177 for (User *U : llvm::make_early_inc_range(CI->users())) {1178 ICmpInst *Old = cast<ICmpInst>(U);1179 Value *Cmp =1180 B.CreateICmp(Old->getPredicate(), StrNCmp,1181 ConstantInt::getNullValue(StrNCmp->getType()), "cmp");1182 replaceAllUsesWith(Old, Cmp);1183 }1184 return CI;1185 }1186 1187 // See if either input string is a constant string.1188 StringRef SearchStr, ToFindStr;1189 bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);1190 bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);1191 1192 // fold strstr(x, "") -> x.1193 if (HasStr2 && ToFindStr.empty())1194 return CI->getArgOperand(0);1195 1196 // If both strings are known, constant fold it.1197 if (HasStr1 && HasStr2) {1198 size_t Offset = SearchStr.find(ToFindStr);1199 1200 if (Offset == StringRef::npos) // strstr("foo", "bar") -> null1201 return Constant::getNullValue(CI->getType());1202 1203 // strstr("abcd", "bc") -> gep((char*)"abcd", 1)1204 return B.CreateConstInBoundsGEP1_64(B.getInt8Ty(), CI->getArgOperand(0),1205 Offset, "strstr");1206 }1207 1208 // fold strstr(x, "y") -> strchr(x, 'y').1209 if (HasStr2 && ToFindStr.size() == 1) {1210 return emitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TLI);1211 }1212 1213 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});1214 return nullptr;1215}1216 1217Value *LibCallSimplifier::optimizeMemRChr(CallInst *CI, IRBuilderBase &B) {1218 Value *SrcStr = CI->getArgOperand(0);1219 Value *Size = CI->getArgOperand(2);1220 annotateNonNullAndDereferenceable(CI, 0, Size, DL);1221 Value *CharVal = CI->getArgOperand(1);1222 ConstantInt *LenC = dyn_cast<ConstantInt>(Size);1223 Value *NullPtr = Constant::getNullValue(CI->getType());1224 1225 if (LenC) {1226 if (LenC->isZero())1227 // Fold memrchr(x, y, 0) --> null.1228 return NullPtr;1229 1230 if (LenC->isOne()) {1231 // Fold memrchr(x, y, 1) --> *x == y ? x : null for any x and y,1232 // constant or otherwise.1233 Value *Val = B.CreateLoad(B.getInt8Ty(), SrcStr, "memrchr.char0");1234 // Slice off the character's high end bits.1235 CharVal = B.CreateTrunc(CharVal, B.getInt8Ty());1236 Value *Cmp = B.CreateICmpEQ(Val, CharVal, "memrchr.char0cmp");1237 return B.CreateSelect(Cmp, SrcStr, NullPtr, "memrchr.sel");1238 }1239 }1240 1241 StringRef Str;1242 if (!getConstantStringInfo(SrcStr, Str, /*TrimAtNul=*/false))1243 return nullptr;1244 1245 if (Str.size() == 0)1246 // If the array is empty fold memrchr(A, C, N) to null for any value1247 // of C and N on the basis that the only valid value of N is zero1248 // (otherwise the call is undefined).1249 return NullPtr;1250 1251 uint64_t EndOff = UINT64_MAX;1252 if (LenC) {1253 EndOff = LenC->getZExtValue();1254 if (Str.size() < EndOff)1255 // Punt out-of-bounds accesses to sanitizers and/or libc.1256 return nullptr;1257 }1258 1259 if (ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal)) {1260 // Fold memrchr(S, C, N) for a constant C.1261 size_t Pos = Str.rfind(CharC->getZExtValue(), EndOff);1262 if (Pos == StringRef::npos)1263 // When the character is not in the source array fold the result1264 // to null regardless of Size.1265 return NullPtr;1266 1267 if (LenC)1268 // Fold memrchr(s, c, N) --> s + Pos for constant N > Pos.1269 return B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos));1270 1271 if (Str.find(Str[Pos]) == Pos) {1272 // When there is just a single occurrence of C in S, i.e., the one1273 // in Str[Pos], fold1274 // memrchr(s, c, N) --> N <= Pos ? null : s + Pos1275 // for nonconstant N.1276 Value *Cmp = B.CreateICmpULE(Size, ConstantInt::get(Size->getType(), Pos),1277 "memrchr.cmp");1278 Value *SrcPlus = B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr,1279 B.getInt64(Pos), "memrchr.ptr_plus");1280 return B.CreateSelect(Cmp, NullPtr, SrcPlus, "memrchr.sel");1281 }1282 }1283 1284 // Truncate the string to search at most EndOff characters.1285 Str = Str.substr(0, EndOff);1286 if (Str.find_first_not_of(Str[0]) != StringRef::npos)1287 return nullptr;1288 1289 // If the source array consists of all equal characters, then for any1290 // C and N (whether in bounds or not), fold memrchr(S, C, N) to1291 // N != 0 && *S == C ? S + N - 1 : null1292 Type *SizeTy = Size->getType();1293 Type *Int8Ty = B.getInt8Ty();1294 Value *NNeZ = B.CreateICmpNE(Size, ConstantInt::get(SizeTy, 0));1295 // Slice off the sought character's high end bits.1296 CharVal = B.CreateTrunc(CharVal, Int8Ty);1297 Value *CEqS0 = B.CreateICmpEQ(ConstantInt::get(Int8Ty, Str[0]), CharVal);1298 Value *And = B.CreateLogicalAnd(NNeZ, CEqS0);1299 Value *SizeM1 = B.CreateSub(Size, ConstantInt::get(SizeTy, 1));1300 Value *SrcPlus =1301 B.CreateInBoundsGEP(Int8Ty, SrcStr, SizeM1, "memrchr.ptr_plus");1302 return B.CreateSelect(And, SrcPlus, NullPtr, "memrchr.sel");1303}1304 1305Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilderBase &B) {1306 Value *SrcStr = CI->getArgOperand(0);1307 Value *Size = CI->getArgOperand(2);1308 1309 if (isKnownNonZero(Size, DL)) {1310 annotateNonNullNoUndefBasedOnAccess(CI, 0);1311 if (isOnlyUsedInEqualityComparison(CI, SrcStr))1312 return memChrToCharCompare(CI, Size, B, DL);1313 }1314 1315 Value *CharVal = CI->getArgOperand(1);1316 ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);1317 ConstantInt *LenC = dyn_cast<ConstantInt>(Size);1318 Value *NullPtr = Constant::getNullValue(CI->getType());1319 1320 // memchr(x, y, 0) -> null1321 if (LenC) {1322 if (LenC->isZero())1323 return NullPtr;1324 1325 if (LenC->isOne()) {1326 // Fold memchr(x, y, 1) --> *x == y ? x : null for any x and y,1327 // constant or otherwise.1328 Value *Val = B.CreateLoad(B.getInt8Ty(), SrcStr, "memchr.char0");1329 // Slice off the character's high end bits.1330 CharVal = B.CreateTrunc(CharVal, B.getInt8Ty());1331 Value *Cmp = B.CreateICmpEQ(Val, CharVal, "memchr.char0cmp");1332 return B.CreateSelect(Cmp, SrcStr, NullPtr, "memchr.sel");1333 }1334 }1335 1336 StringRef Str;1337 if (!getConstantStringInfo(SrcStr, Str, /*TrimAtNul=*/false))1338 return nullptr;1339 1340 if (CharC) {1341 size_t Pos = Str.find(CharC->getZExtValue());1342 if (Pos == StringRef::npos)1343 // When the character is not in the source array fold the result1344 // to null regardless of Size.1345 return NullPtr;1346 1347 // Fold memchr(s, c, n) -> n <= Pos ? null : s + Pos1348 // When the constant Size is less than or equal to the character1349 // position also fold the result to null.1350 Value *Cmp = B.CreateICmpULE(Size, ConstantInt::get(Size->getType(), Pos),1351 "memchr.cmp");1352 Value *SrcPlus = B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos),1353 "memchr.ptr");1354 return B.CreateSelect(Cmp, NullPtr, SrcPlus);1355 }1356 1357 if (Str.size() == 0)1358 // If the array is empty fold memchr(A, C, N) to null for any value1359 // of C and N on the basis that the only valid value of N is zero1360 // (otherwise the call is undefined).1361 return NullPtr;1362 1363 if (LenC)1364 Str = substr(Str, LenC->getZExtValue());1365 1366 size_t Pos = Str.find_first_not_of(Str[0]);1367 if (Pos == StringRef::npos1368 || Str.find_first_not_of(Str[Pos], Pos) == StringRef::npos) {1369 // If the source array consists of at most two consecutive sequences1370 // of the same characters, then for any C and N (whether in bounds or1371 // not), fold memchr(S, C, N) to1372 // N != 0 && *S == C ? S : null1373 // or for the two sequences to:1374 // N != 0 && *S == C ? S : (N > Pos && S[Pos] == C ? S + Pos : null)1375 // ^Sel2 ^Sel1 are denoted above.1376 // The latter makes it also possible to fold strchr() calls with strings1377 // of the same characters.1378 Type *SizeTy = Size->getType();1379 Type *Int8Ty = B.getInt8Ty();1380 1381 // Slice off the sought character's high end bits.1382 CharVal = B.CreateTrunc(CharVal, Int8Ty);1383 1384 Value *Sel1 = NullPtr;1385 if (Pos != StringRef::npos) {1386 // Handle two consecutive sequences of the same characters.1387 Value *PosVal = ConstantInt::get(SizeTy, Pos);1388 Value *StrPos = ConstantInt::get(Int8Ty, Str[Pos]);1389 Value *CEqSPos = B.CreateICmpEQ(CharVal, StrPos);1390 Value *NGtPos = B.CreateICmp(ICmpInst::ICMP_UGT, Size, PosVal);1391 Value *And = B.CreateAnd(CEqSPos, NGtPos);1392 Value *SrcPlus = B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, PosVal);1393 Sel1 = B.CreateSelect(And, SrcPlus, NullPtr, "memchr.sel1");1394 }1395 1396 Value *Str0 = ConstantInt::get(Int8Ty, Str[0]);1397 Value *CEqS0 = B.CreateICmpEQ(Str0, CharVal);1398 Value *NNeZ = B.CreateICmpNE(Size, ConstantInt::get(SizeTy, 0));1399 Value *And = B.CreateAnd(NNeZ, CEqS0);1400 return B.CreateSelect(And, SrcStr, Sel1, "memchr.sel2");1401 }1402 1403 if (!LenC) {1404 if (isOnlyUsedInEqualityComparison(CI, SrcStr))1405 // S is dereferenceable so it's safe to load from it and fold1406 // memchr(S, C, N) == S to N && *S == C for any C and N.1407 // TODO: This is safe even for nonconstant S.1408 return memChrToCharCompare(CI, Size, B, DL);1409 1410 // From now on we need a constant length and constant array.1411 return nullptr;1412 }1413 1414 bool OptForSize = llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI,1415 PGSOQueryType::IRPass);1416 1417 // If the char is variable but the input str and length are not we can turn1418 // this memchr call into a simple bit field test. Of course this only works1419 // when the return value is only checked against null.1420 //1421 // It would be really nice to reuse switch lowering here but we can't change1422 // the CFG at this point.1423 //1424 // memchr("\r\n", C, 2) != nullptr -> (1 << C & ((1 << '\r') | (1 << '\n')))1425 // != 01426 // after bounds check.1427 if (OptForSize || Str.empty() || !isOnlyUsedInZeroEqualityComparison(CI))1428 return nullptr;1429 1430 unsigned char Max =1431 *std::max_element(reinterpret_cast<const unsigned char *>(Str.begin()),1432 reinterpret_cast<const unsigned char *>(Str.end()));1433 1434 // Make sure the bit field we're about to create fits in a register on the1435 // target.1436 // FIXME: On a 64 bit architecture this prevents us from using the1437 // interesting range of alpha ascii chars. We could do better by emitting1438 // two bitfields or shifting the range by 64 if no lower chars are used.1439 if (!DL.fitsInLegalInteger(Max + 1)) {1440 // Build chain of ORs1441 // Transform:1442 // memchr("abcd", C, 4) != nullptr1443 // to:1444 // (C == 'a' || C == 'b' || C == 'c' || C == 'd') != 01445 std::string SortedStr = Str.str();1446 llvm::sort(SortedStr);1447 // Compute the number of of non-contiguous ranges.1448 unsigned NonContRanges = 1;1449 for (size_t i = 1; i < SortedStr.size(); ++i) {1450 if (SortedStr[i] > SortedStr[i - 1] + 1) {1451 NonContRanges++;1452 }1453 }1454 1455 // Restrict this optimization to profitable cases with one or two range1456 // checks.1457 if (NonContRanges > 2)1458 return nullptr;1459 1460 // Slice off the character's high end bits.1461 CharVal = B.CreateTrunc(CharVal, B.getInt8Ty());1462 1463 SmallVector<Value *> CharCompares;1464 for (unsigned char C : SortedStr)1465 CharCompares.push_back(B.CreateICmpEQ(CharVal, B.getInt8(C)));1466 1467 return B.CreateIntToPtr(B.CreateOr(CharCompares), CI->getType());1468 }1469 1470 // For the bit field use a power-of-2 type with at least 8 bits to avoid1471 // creating unnecessary illegal types.1472 unsigned char Width = NextPowerOf2(std::max((unsigned char)7, Max));1473 1474 // Now build the bit field.1475 APInt Bitfield(Width, 0);1476 for (char C : Str)1477 Bitfield.setBit((unsigned char)C);1478 Value *BitfieldC = B.getInt(Bitfield);1479 1480 // Adjust width of "C" to the bitfield width, then mask off the high bits.1481 Value *C = B.CreateZExtOrTrunc(CharVal, BitfieldC->getType());1482 C = B.CreateAnd(C, B.getIntN(Width, 0xFF));1483 1484 // First check that the bit field access is within bounds.1485 Value *Bounds = B.CreateICmp(ICmpInst::ICMP_ULT, C, B.getIntN(Width, Width),1486 "memchr.bounds");1487 1488 // Create code that checks if the given bit is set in the field.1489 Value *Shl = B.CreateShl(B.getIntN(Width, 1ULL), C);1490 Value *Bits = B.CreateIsNotNull(B.CreateAnd(Shl, BitfieldC), "memchr.bits");1491 1492 // Finally merge both checks and cast to pointer type. The inttoptr1493 // implicitly zexts the i1 to intptr type.1494 return B.CreateIntToPtr(B.CreateLogicalAnd(Bounds, Bits, "memchr"),1495 CI->getType());1496}1497 1498// Optimize a memcmp or, when StrNCmp is true, strncmp call CI with constant1499// arrays LHS and RHS and nonconstant Size.1500static Value *optimizeMemCmpVarSize(CallInst *CI, Value *LHS, Value *RHS,1501 Value *Size, bool StrNCmp,1502 IRBuilderBase &B, const DataLayout &DL) {1503 if (LHS == RHS) // memcmp(s,s,x) -> 01504 return Constant::getNullValue(CI->getType());1505 1506 StringRef LStr, RStr;1507 if (!getConstantStringInfo(LHS, LStr, /*TrimAtNul=*/false) ||1508 !getConstantStringInfo(RHS, RStr, /*TrimAtNul=*/false))1509 return nullptr;1510 1511 // If the contents of both constant arrays are known, fold a call to1512 // memcmp(A, B, N) to1513 // N <= Pos ? 0 : (A < B ? -1 : B < A ? +1 : 0)1514 // where Pos is the first mismatch between A and B, determined below.1515 1516 uint64_t Pos = 0;1517 Value *Zero = ConstantInt::get(CI->getType(), 0);1518 for (uint64_t MinSize = std::min(LStr.size(), RStr.size()); ; ++Pos) {1519 if (Pos == MinSize ||1520 (StrNCmp && (LStr[Pos] == '\0' && RStr[Pos] == '\0'))) {1521 // One array is a leading part of the other of equal or greater1522 // size, or for strncmp, the arrays are equal strings.1523 // Fold the result to zero. Size is assumed to be in bounds, since1524 // otherwise the call would be undefined.1525 return Zero;1526 }1527 1528 if (LStr[Pos] != RStr[Pos])1529 break;1530 }1531 1532 // Normalize the result.1533 typedef unsigned char UChar;1534 int IRes = UChar(LStr[Pos]) < UChar(RStr[Pos]) ? -1 : 1;1535 Value *MaxSize = ConstantInt::get(Size->getType(), Pos);1536 Value *Cmp = B.CreateICmp(ICmpInst::ICMP_ULE, Size, MaxSize);1537 Value *Res = ConstantInt::get(CI->getType(), IRes);1538 return B.CreateSelect(Cmp, Zero, Res);1539}1540 1541// Optimize a memcmp call CI with constant size Len.1542static Value *optimizeMemCmpConstantSize(CallInst *CI, Value *LHS, Value *RHS,1543 uint64_t Len, IRBuilderBase &B,1544 const DataLayout &DL) {1545 if (Len == 0) // memcmp(s1,s2,0) -> 01546 return Constant::getNullValue(CI->getType());1547 1548 // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS1549 if (Len == 1) {1550 Value *LHSV = B.CreateZExt(B.CreateLoad(B.getInt8Ty(), LHS, "lhsc"),1551 CI->getType(), "lhsv");1552 Value *RHSV = B.CreateZExt(B.CreateLoad(B.getInt8Ty(), RHS, "rhsc"),1553 CI->getType(), "rhsv");1554 return B.CreateSub(LHSV, RHSV, "chardiff");1555 }1556 1557 // memcmp(S1,S2,N/8)==0 -> (*(intN_t*)S1 != *(intN_t*)S2)==01558 // TODO: The case where both inputs are constants does not need to be limited1559 // to legal integers or equality comparison. See block below this.1560 if (DL.isLegalInteger(Len * 8) && isOnlyUsedInZeroEqualityComparison(CI)) {1561 IntegerType *IntType = IntegerType::get(CI->getContext(), Len * 8);1562 Align PrefAlignment = DL.getPrefTypeAlign(IntType);1563 1564 // First, see if we can fold either argument to a constant.1565 Value *LHSV = nullptr;1566 if (auto *LHSC = dyn_cast<Constant>(LHS))1567 LHSV = ConstantFoldLoadFromConstPtr(LHSC, IntType, DL);1568 1569 Value *RHSV = nullptr;1570 if (auto *RHSC = dyn_cast<Constant>(RHS))1571 RHSV = ConstantFoldLoadFromConstPtr(RHSC, IntType, DL);1572 1573 // Don't generate unaligned loads. If either source is constant data,1574 // alignment doesn't matter for that source because there is no load.1575 if ((LHSV || getKnownAlignment(LHS, DL, CI) >= PrefAlignment) &&1576 (RHSV || getKnownAlignment(RHS, DL, CI) >= PrefAlignment)) {1577 if (!LHSV)1578 LHSV = B.CreateLoad(IntType, LHS, "lhsv");1579 if (!RHSV)1580 RHSV = B.CreateLoad(IntType, RHS, "rhsv");1581 return B.CreateZExt(B.CreateICmpNE(LHSV, RHSV), CI->getType(), "memcmp");1582 }1583 }1584 1585 return nullptr;1586}1587 1588// Most simplifications for memcmp also apply to bcmp.1589Value *LibCallSimplifier::optimizeMemCmpBCmpCommon(CallInst *CI,1590 IRBuilderBase &B) {1591 Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);1592 Value *Size = CI->getArgOperand(2);1593 1594 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL);1595 1596 if (Value *Res = optimizeMemCmpVarSize(CI, LHS, RHS, Size, false, B, DL))1597 return Res;1598 1599 // Handle constant Size.1600 ConstantInt *LenC = dyn_cast<ConstantInt>(Size);1601 if (!LenC)1602 return nullptr;1603 1604 return optimizeMemCmpConstantSize(CI, LHS, RHS, LenC->getZExtValue(), B, DL);1605}1606 1607Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilderBase &B) {1608 Module *M = CI->getModule();1609 if (Value *V = optimizeMemCmpBCmpCommon(CI, B))1610 return V;1611 1612 // memcmp(x, y, Len) == 0 -> bcmp(x, y, Len) == 01613 // bcmp can be more efficient than memcmp because it only has to know that1614 // there is a difference, not how different one is to the other.1615 if (isLibFuncEmittable(M, TLI, LibFunc_bcmp) &&1616 isOnlyUsedInZeroEqualityComparison(CI)) {1617 Value *LHS = CI->getArgOperand(0);1618 Value *RHS = CI->getArgOperand(1);1619 Value *Size = CI->getArgOperand(2);1620 return copyFlags(*CI, emitBCmp(LHS, RHS, Size, B, DL, TLI));1621 }1622 1623 return nullptr;1624}1625 1626Value *LibCallSimplifier::optimizeBCmp(CallInst *CI, IRBuilderBase &B) {1627 return optimizeMemCmpBCmpCommon(CI, B);1628}1629 1630Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilderBase &B) {1631 Value *Size = CI->getArgOperand(2);1632 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL);1633 if (isa<IntrinsicInst>(CI))1634 return nullptr;1635 1636 // memcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n)1637 CallInst *NewCI = B.CreateMemCpy(CI->getArgOperand(0), Align(1),1638 CI->getArgOperand(1), Align(1), Size);1639 mergeAttributesAndFlags(NewCI, *CI);1640 return CI->getArgOperand(0);1641}1642 1643Value *LibCallSimplifier::optimizeMemCCpy(CallInst *CI, IRBuilderBase &B) {1644 Value *Dst = CI->getArgOperand(0);1645 Value *Src = CI->getArgOperand(1);1646 ConstantInt *StopChar = dyn_cast<ConstantInt>(CI->getArgOperand(2));1647 ConstantInt *N = dyn_cast<ConstantInt>(CI->getArgOperand(3));1648 StringRef SrcStr;1649 if (CI->use_empty() && Dst == Src)1650 return Dst;1651 // memccpy(d, s, c, 0) -> nullptr1652 if (N) {1653 if (N->isNullValue())1654 return Constant::getNullValue(CI->getType());1655 if (!getConstantStringInfo(Src, SrcStr, /*TrimAtNul=*/false) ||1656 // TODO: Handle zeroinitializer.1657 !StopChar)1658 return nullptr;1659 } else {1660 return nullptr;1661 }1662 1663 // Wrap arg 'c' of type int to char1664 size_t Pos = SrcStr.find(StopChar->getSExtValue() & 0xFF);1665 if (Pos == StringRef::npos) {1666 if (N->getZExtValue() <= SrcStr.size()) {1667 copyFlags(*CI, B.CreateMemCpy(Dst, Align(1), Src, Align(1),1668 CI->getArgOperand(3)));1669 return Constant::getNullValue(CI->getType());1670 }1671 return nullptr;1672 }1673 1674 Value *NewN =1675 ConstantInt::get(N->getType(), std::min(uint64_t(Pos + 1), N->getZExtValue()));1676 // memccpy -> llvm.memcpy1677 copyFlags(*CI, B.CreateMemCpy(Dst, Align(1), Src, Align(1), NewN));1678 return Pos + 1 <= N->getZExtValue()1679 ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, NewN)1680 : Constant::getNullValue(CI->getType());1681}1682 1683Value *LibCallSimplifier::optimizeMemPCpy(CallInst *CI, IRBuilderBase &B) {1684 Value *Dst = CI->getArgOperand(0);1685 Value *N = CI->getArgOperand(2);1686 // mempcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n), x + n1687 CallInst *NewCI =1688 B.CreateMemCpy(Dst, Align(1), CI->getArgOperand(1), Align(1), N);1689 // Propagate attributes, but memcpy has no return value, so make sure that1690 // any return attributes are compliant.1691 // TODO: Attach return value attributes to the 1st operand to preserve them?1692 mergeAttributesAndFlags(NewCI, *CI);1693 return B.CreateInBoundsGEP(B.getInt8Ty(), Dst, N);1694}1695 1696Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilderBase &B) {1697 Value *Size = CI->getArgOperand(2);1698 annotateNonNullAndDereferenceable(CI, {0, 1}, Size, DL);1699 if (isa<IntrinsicInst>(CI))1700 return nullptr;1701 1702 // memmove(x, y, n) -> llvm.memmove(align 1 x, align 1 y, n)1703 CallInst *NewCI = B.CreateMemMove(CI->getArgOperand(0), Align(1),1704 CI->getArgOperand(1), Align(1), Size);1705 mergeAttributesAndFlags(NewCI, *CI);1706 return CI->getArgOperand(0);1707}1708 1709Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilderBase &B) {1710 Value *Size = CI->getArgOperand(2);1711 annotateNonNullAndDereferenceable(CI, 0, Size, DL);1712 if (isa<IntrinsicInst>(CI))1713 return nullptr;1714 1715 // memset(p, v, n) -> llvm.memset(align 1 p, v, n)1716 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);1717 CallInst *NewCI = B.CreateMemSet(CI->getArgOperand(0), Val, Size, Align(1));1718 mergeAttributesAndFlags(NewCI, *CI);1719 return CI->getArgOperand(0);1720}1721 1722Value *LibCallSimplifier::optimizeRealloc(CallInst *CI, IRBuilderBase &B) {1723 if (isa<ConstantPointerNull>(CI->getArgOperand(0)))1724 return copyFlags(*CI, emitMalloc(CI->getArgOperand(1), B, DL, TLI));1725 1726 return nullptr;1727}1728 1729// Optionally allow optimization of nobuiltin calls to operator new and its1730// variants.1731Value *LibCallSimplifier::maybeOptimizeNoBuiltinOperatorNew(CallInst *CI,1732 IRBuilderBase &B) {1733 if (!OptimizeHotColdNew)1734 return nullptr;1735 Function *Callee = CI->getCalledFunction();1736 if (!Callee)1737 return nullptr;1738 LibFunc Func;1739 if (!TLI->getLibFunc(*Callee, Func))1740 return nullptr;1741 switch (Func) {1742 case LibFunc_Znwm:1743 case LibFunc_ZnwmRKSt9nothrow_t:1744 case LibFunc_ZnwmSt11align_val_t:1745 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t:1746 case LibFunc_Znam:1747 case LibFunc_ZnamRKSt9nothrow_t:1748 case LibFunc_ZnamSt11align_val_t:1749 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t:1750 case LibFunc_size_returning_new:1751 case LibFunc_size_returning_new_aligned:1752 // By default normal operator new calls (not already passing a hot_cold_t1753 // parameter) are not mutated if the call is not marked builtin. Optionally1754 // enable that in cases where it is known to be safe.1755 if (!OptimizeNoBuiltinHotColdNew)1756 return nullptr;1757 break;1758 case LibFunc_Znwm12__hot_cold_t:1759 case LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t:1760 case LibFunc_ZnwmSt11align_val_t12__hot_cold_t:1761 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t:1762 case LibFunc_Znam12__hot_cold_t:1763 case LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t:1764 case LibFunc_ZnamSt11align_val_t12__hot_cold_t:1765 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t:1766 case LibFunc_size_returning_new_hot_cold:1767 case LibFunc_size_returning_new_aligned_hot_cold:1768 // If the nobuiltin call already passes a hot_cold_t parameter, allow update1769 // of that parameter when enabled.1770 if (!OptimizeExistingHotColdNew)1771 return nullptr;1772 break;1773 default:1774 return nullptr;1775 }1776 return optimizeNew(CI, B, Func);1777}1778 1779// When enabled, replace operator new() calls marked with a hot or cold memprof1780// attribute with an operator new() call that takes a __hot_cold_t parameter.1781// Currently this is supported by the open source version of tcmalloc, see:1782// https://github.com/google/tcmalloc/blob/master/tcmalloc/new_extension.h1783Value *LibCallSimplifier::optimizeNew(CallInst *CI, IRBuilderBase &B,1784 LibFunc &Func) {1785 if (!OptimizeHotColdNew)1786 return nullptr;1787 1788 uint8_t HotCold;1789 if (CI->getAttributes().getFnAttr("memprof").getValueAsString() == "cold")1790 HotCold = ColdNewHintValue;1791 else if (CI->getAttributes().getFnAttr("memprof").getValueAsString() ==1792 "notcold")1793 HotCold = NotColdNewHintValue;1794 else if (CI->getAttributes().getFnAttr("memprof").getValueAsString() == "hot")1795 HotCold = HotNewHintValue;1796 else if (CI->getAttributes().getFnAttr("memprof").getValueAsString() ==1797 "ambiguous")1798 HotCold = AmbiguousNewHintValue;1799 else1800 return nullptr;1801 1802 // For calls that already pass a hot/cold hint, only update the hint if1803 // directed by OptimizeExistingHotColdNew. For other calls to new, add a hint1804 // if cold or hot, and leave as-is for default handling if "notcold" aka warm.1805 // Note that in cases where we decide it is "notcold", it might be slightly1806 // better to replace the hinted call with a non hinted call, to avoid the1807 // extra parameter and the if condition check of the hint value in the1808 // allocator. This can be considered in the future.1809 Value *NewCall = nullptr;1810 switch (Func) {1811 case LibFunc_Znwm12__hot_cold_t:1812 if (OptimizeExistingHotColdNew)1813 NewCall = emitHotColdNew(CI->getArgOperand(0), B, TLI,1814 LibFunc_Znwm12__hot_cold_t, HotCold);1815 break;1816 case LibFunc_Znwm:1817 NewCall = emitHotColdNew(CI->getArgOperand(0), B, TLI,1818 LibFunc_Znwm12__hot_cold_t, HotCold);1819 break;1820 case LibFunc_Znam12__hot_cold_t:1821 if (OptimizeExistingHotColdNew)1822 NewCall = emitHotColdNew(CI->getArgOperand(0), B, TLI,1823 LibFunc_Znam12__hot_cold_t, HotCold);1824 break;1825 case LibFunc_Znam:1826 NewCall = emitHotColdNew(CI->getArgOperand(0), B, TLI,1827 LibFunc_Znam12__hot_cold_t, HotCold);1828 break;1829 case LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t:1830 if (OptimizeExistingHotColdNew)1831 NewCall = emitHotColdNewNoThrow(1832 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1833 LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t, HotCold);1834 break;1835 case LibFunc_ZnwmRKSt9nothrow_t:1836 NewCall = emitHotColdNewNoThrow(1837 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1838 LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t, HotCold);1839 break;1840 case LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t:1841 if (OptimizeExistingHotColdNew)1842 NewCall = emitHotColdNewNoThrow(1843 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1844 LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t, HotCold);1845 break;1846 case LibFunc_ZnamRKSt9nothrow_t:1847 NewCall = emitHotColdNewNoThrow(1848 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1849 LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t, HotCold);1850 break;1851 case LibFunc_ZnwmSt11align_val_t12__hot_cold_t:1852 if (OptimizeExistingHotColdNew)1853 NewCall = emitHotColdNewAligned(1854 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1855 LibFunc_ZnwmSt11align_val_t12__hot_cold_t, HotCold);1856 break;1857 case LibFunc_ZnwmSt11align_val_t:1858 NewCall = emitHotColdNewAligned(1859 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1860 LibFunc_ZnwmSt11align_val_t12__hot_cold_t, HotCold);1861 break;1862 case LibFunc_ZnamSt11align_val_t12__hot_cold_t:1863 if (OptimizeExistingHotColdNew)1864 NewCall = emitHotColdNewAligned(1865 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1866 LibFunc_ZnamSt11align_val_t12__hot_cold_t, HotCold);1867 break;1868 case LibFunc_ZnamSt11align_val_t:1869 NewCall = emitHotColdNewAligned(1870 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1871 LibFunc_ZnamSt11align_val_t12__hot_cold_t, HotCold);1872 break;1873 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t:1874 if (OptimizeExistingHotColdNew)1875 NewCall = emitHotColdNewAlignedNoThrow(1876 CI->getArgOperand(0), CI->getArgOperand(1), CI->getArgOperand(2), B,1877 TLI, LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t,1878 HotCold);1879 break;1880 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t:1881 NewCall = emitHotColdNewAlignedNoThrow(1882 CI->getArgOperand(0), CI->getArgOperand(1), CI->getArgOperand(2), B,1883 TLI, LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t, HotCold);1884 break;1885 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t:1886 if (OptimizeExistingHotColdNew)1887 NewCall = emitHotColdNewAlignedNoThrow(1888 CI->getArgOperand(0), CI->getArgOperand(1), CI->getArgOperand(2), B,1889 TLI, LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t,1890 HotCold);1891 break;1892 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t:1893 NewCall = emitHotColdNewAlignedNoThrow(1894 CI->getArgOperand(0), CI->getArgOperand(1), CI->getArgOperand(2), B,1895 TLI, LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t, HotCold);1896 break;1897 case LibFunc_size_returning_new:1898 NewCall = emitHotColdSizeReturningNew(CI->getArgOperand(0), B, TLI,1899 LibFunc_size_returning_new_hot_cold,1900 HotCold);1901 break;1902 case LibFunc_size_returning_new_hot_cold:1903 if (OptimizeExistingHotColdNew)1904 NewCall = emitHotColdSizeReturningNew(CI->getArgOperand(0), B, TLI,1905 LibFunc_size_returning_new_hot_cold,1906 HotCold);1907 break;1908 case LibFunc_size_returning_new_aligned:1909 NewCall = emitHotColdSizeReturningNewAligned(1910 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1911 LibFunc_size_returning_new_aligned_hot_cold, HotCold);1912 break;1913 case LibFunc_size_returning_new_aligned_hot_cold:1914 if (OptimizeExistingHotColdNew)1915 NewCall = emitHotColdSizeReturningNewAligned(1916 CI->getArgOperand(0), CI->getArgOperand(1), B, TLI,1917 LibFunc_size_returning_new_aligned_hot_cold, HotCold);1918 break;1919 default:1920 return nullptr;1921 }1922 1923 if (auto *NewCI = dyn_cast_or_null<Instruction>(NewCall))1924 NewCI->copyMetadata(*CI);1925 1926 return NewCall;1927}1928 1929//===----------------------------------------------------------------------===//1930// Math Library Optimizations1931//===----------------------------------------------------------------------===//1932 1933// Replace a libcall \p CI with a call to intrinsic \p IID1934static Value *replaceUnaryCall(CallInst *CI, IRBuilderBase &B,1935 Intrinsic::ID IID) {1936 CallInst *NewCall = B.CreateUnaryIntrinsic(IID, CI->getArgOperand(0), CI);1937 NewCall->takeName(CI);1938 return copyFlags(*CI, NewCall);1939}1940 1941/// Return a variant of Val with float type.1942/// Currently this works in two cases: If Val is an FPExtension of a float1943/// value to something bigger, simply return the operand.1944/// If Val is a ConstantFP but can be converted to a float ConstantFP without1945/// loss of precision do so.1946static Value *valueHasFloatPrecision(Value *Val) {1947 if (FPExtInst *Cast = dyn_cast<FPExtInst>(Val)) {1948 Value *Op = Cast->getOperand(0);1949 if (Op->getType()->isFloatTy())1950 return Op;1951 }1952 if (ConstantFP *Const = dyn_cast<ConstantFP>(Val)) {1953 APFloat F = Const->getValueAPF();1954 bool losesInfo;1955 (void)F.convert(APFloat::IEEEsingle(), APFloat::rmNearestTiesToEven,1956 &losesInfo);1957 if (!losesInfo)1958 return ConstantFP::get(Const->getContext(), F);1959 }1960 return nullptr;1961}1962 1963/// Shrink double -> float functions.1964static Value *optimizeDoubleFP(CallInst *CI, IRBuilderBase &B,1965 bool isBinary, const TargetLibraryInfo *TLI,1966 bool isPrecise = false) {1967 Function *CalleeFn = CI->getCalledFunction();1968 if (!CI->getType()->isDoubleTy() || !CalleeFn)1969 return nullptr;1970 1971 // If not all the uses of the function are converted to float, then bail out.1972 // This matters if the precision of the result is more important than the1973 // precision of the arguments.1974 if (isPrecise)1975 for (User *U : CI->users()) {1976 FPTruncInst *Cast = dyn_cast<FPTruncInst>(U);1977 if (!Cast || !Cast->getType()->isFloatTy())1978 return nullptr;1979 }1980 1981 // If this is something like 'g((double) float)', convert to 'gf(float)'.1982 Value *V[2];1983 V[0] = valueHasFloatPrecision(CI->getArgOperand(0));1984 V[1] = isBinary ? valueHasFloatPrecision(CI->getArgOperand(1)) : nullptr;1985 if (!V[0] || (isBinary && !V[1]))1986 return nullptr;1987 1988 // If call isn't an intrinsic, check that it isn't within a function with the1989 // same name as the float version of this call, otherwise the result is an1990 // infinite loop. For example, from MinGW-w64:1991 //1992 // float expf(float val) { return (float) exp((double) val); }1993 StringRef CalleeName = CalleeFn->getName();1994 bool IsIntrinsic = CalleeFn->isIntrinsic();1995 if (!IsIntrinsic) {1996 StringRef CallerName = CI->getFunction()->getName();1997 if (CallerName.ends_with('f') &&1998 CallerName.size() == (CalleeName.size() + 1) &&1999 CallerName.starts_with(CalleeName))2000 return nullptr;2001 }2002 2003 // Propagate the math semantics from the current function to the new function.2004 IRBuilderBase::FastMathFlagGuard Guard(B);2005 B.setFastMathFlags(CI->getFastMathFlags());2006 2007 // g((double) float) -> (double) gf(float)2008 Value *R;2009 if (IsIntrinsic) {2010 Intrinsic::ID IID = CalleeFn->getIntrinsicID();2011 R = isBinary ? B.CreateIntrinsic(IID, B.getFloatTy(), V)2012 : B.CreateIntrinsic(IID, B.getFloatTy(), V[0]);2013 } else {2014 AttributeList CalleeAttrs = CalleeFn->getAttributes();2015 R = isBinary ? emitBinaryFloatFnCall(V[0], V[1], TLI, CalleeName, B,2016 CalleeAttrs)2017 : emitUnaryFloatFnCall(V[0], TLI, CalleeName, B, CalleeAttrs);2018 }2019 return B.CreateFPExt(R, B.getDoubleTy());2020}2021 2022/// Shrink double -> float for unary functions.2023static Value *optimizeUnaryDoubleFP(CallInst *CI, IRBuilderBase &B,2024 const TargetLibraryInfo *TLI,2025 bool isPrecise = false) {2026 return optimizeDoubleFP(CI, B, false, TLI, isPrecise);2027}2028 2029/// Shrink double -> float for binary functions.2030static Value *optimizeBinaryDoubleFP(CallInst *CI, IRBuilderBase &B,2031 const TargetLibraryInfo *TLI,2032 bool isPrecise = false) {2033 return optimizeDoubleFP(CI, B, true, TLI, isPrecise);2034}2035 2036// cabs(z) -> sqrt((creal(z)*creal(z)) + (cimag(z)*cimag(z)))2037Value *LibCallSimplifier::optimizeCAbs(CallInst *CI, IRBuilderBase &B) {2038 Value *Real, *Imag;2039 2040 if (CI->arg_size() == 1) {2041 2042 if (!CI->isFast())2043 return nullptr;2044 2045 Value *Op = CI->getArgOperand(0);2046 assert(Op->getType()->isArrayTy() && "Unexpected signature for cabs!");2047 2048 Real = B.CreateExtractValue(Op, 0, "real");2049 Imag = B.CreateExtractValue(Op, 1, "imag");2050 2051 } else {2052 assert(CI->arg_size() == 2 && "Unexpected signature for cabs!");2053 2054 Real = CI->getArgOperand(0);2055 Imag = CI->getArgOperand(1);2056 2057 // if real or imaginary part is zero, simplify to abs(cimag(z))2058 // or abs(creal(z))2059 Value *AbsOp = nullptr;2060 if (ConstantFP *ConstReal = dyn_cast<ConstantFP>(Real)) {2061 if (ConstReal->isZero())2062 AbsOp = Imag;2063 2064 } else if (ConstantFP *ConstImag = dyn_cast<ConstantFP>(Imag)) {2065 if (ConstImag->isZero())2066 AbsOp = Real;2067 }2068 2069 if (AbsOp)2070 return copyFlags(2071 *CI, B.CreateUnaryIntrinsic(Intrinsic::fabs, AbsOp, CI, "cabs"));2072 2073 if (!CI->isFast())2074 return nullptr;2075 }2076 2077 // Propagate fast-math flags from the existing call to new instructions.2078 Value *RealReal = B.CreateFMulFMF(Real, Real, CI);2079 Value *ImagImag = B.CreateFMulFMF(Imag, Imag, CI);2080 return copyFlags(2081 *CI, B.CreateUnaryIntrinsic(Intrinsic::sqrt,2082 B.CreateFAddFMF(RealReal, ImagImag, CI), CI,2083 "cabs"));2084}2085 2086// Return a properly extended integer (DstWidth bits wide) if the operation is2087// an itofp.2088static Value *getIntToFPVal(Value *I2F, IRBuilderBase &B, unsigned DstWidth) {2089 if (isa<SIToFPInst>(I2F) || isa<UIToFPInst>(I2F)) {2090 Value *Op = cast<Instruction>(I2F)->getOperand(0);2091 // Make sure that the exponent fits inside an "int" of size DstWidth,2092 // thus avoiding any range issues that FP has not.2093 unsigned BitWidth = Op->getType()->getScalarSizeInBits();2094 if (BitWidth < DstWidth || (BitWidth == DstWidth && isa<SIToFPInst>(I2F))) {2095 Type *IntTy = Op->getType()->getWithNewBitWidth(DstWidth);2096 return isa<SIToFPInst>(I2F) ? B.CreateSExt(Op, IntTy)2097 : B.CreateZExt(Op, IntTy);2098 }2099 }2100 2101 return nullptr;2102}2103 2104/// Use exp{,2}(x * y) for pow(exp{,2}(x), y);2105/// ldexp(1.0, x) for pow(2.0, itofp(x)); exp2(n * x) for pow(2.0 ** n, x);2106/// exp10(x) for pow(10.0, x); exp2(log2(n) * x) for pow(n, x).2107Value *LibCallSimplifier::replacePowWithExp(CallInst *Pow, IRBuilderBase &B) {2108 Module *M = Pow->getModule();2109 Value *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);2110 Type *Ty = Pow->getType();2111 bool Ignored;2112 2113 // Evaluate special cases related to a nested function as the base.2114 2115 // pow(exp(x), y) -> exp(x * y)2116 // pow(exp2(x), y) -> exp2(x * y)2117 // If exp{,2}() is used only once, it is better to fold two transcendental2118 // math functions into one. If used again, exp{,2}() would still have to be2119 // called with the original argument, then keep both original transcendental2120 // functions. However, this transformation is only safe with fully relaxed2121 // math semantics, since, besides rounding differences, it changes overflow2122 // and underflow behavior quite dramatically. For example:2123 // pow(exp(1000), 0.001) = pow(inf, 0.001) = inf2124 // Whereas:2125 // exp(1000 * 0.001) = exp(1)2126 // TODO: Loosen the requirement for fully relaxed math semantics.2127 // TODO: Handle exp10() when more targets have it available.2128 CallInst *BaseFn = dyn_cast<CallInst>(Base);2129 if (BaseFn && BaseFn->hasOneUse() && BaseFn->isFast() && Pow->isFast()) {2130 LibFunc LibFn;2131 2132 Function *CalleeFn = BaseFn->getCalledFunction();2133 if (CalleeFn && TLI->getLibFunc(CalleeFn->getName(), LibFn) &&2134 isLibFuncEmittable(M, TLI, LibFn)) {2135 StringRef ExpName;2136 Intrinsic::ID ID;2137 Value *ExpFn;2138 LibFunc LibFnFloat, LibFnDouble, LibFnLongDouble;2139 2140 switch (LibFn) {2141 default:2142 return nullptr;2143 case LibFunc_expf:2144 case LibFunc_exp:2145 case LibFunc_expl:2146 ExpName = TLI->getName(LibFunc_exp);2147 ID = Intrinsic::exp;2148 LibFnFloat = LibFunc_expf;2149 LibFnDouble = LibFunc_exp;2150 LibFnLongDouble = LibFunc_expl;2151 break;2152 case LibFunc_exp2f:2153 case LibFunc_exp2:2154 case LibFunc_exp2l:2155 ExpName = TLI->getName(LibFunc_exp2);2156 ID = Intrinsic::exp2;2157 LibFnFloat = LibFunc_exp2f;2158 LibFnDouble = LibFunc_exp2;2159 LibFnLongDouble = LibFunc_exp2l;2160 break;2161 }2162 2163 // Create new exp{,2}() with the product as its argument.2164 Value *FMul = B.CreateFMul(BaseFn->getArgOperand(0), Expo, "mul");2165 ExpFn = BaseFn->doesNotAccessMemory()2166 ? B.CreateUnaryIntrinsic(ID, FMul, nullptr, ExpName)2167 : emitUnaryFloatFnCall(FMul, TLI, LibFnDouble, LibFnFloat,2168 LibFnLongDouble, B,2169 BaseFn->getAttributes());2170 2171 // Since the new exp{,2}() is different from the original one, dead code2172 // elimination cannot be trusted to remove it, since it may have side2173 // effects (e.g., errno). When the only consumer for the original2174 // exp{,2}() is pow(), then it has to be explicitly erased.2175 substituteInParent(BaseFn, ExpFn);2176 return ExpFn;2177 }2178 }2179 2180 // Evaluate special cases related to a constant base.2181 2182 const APFloat *BaseF;2183 if (!match(Base, m_APFloat(BaseF)))2184 return nullptr;2185 2186 AttributeList NoAttrs; // Attributes are only meaningful on the original call2187 2188 const bool UseIntrinsic = Pow->doesNotAccessMemory();2189 2190 // pow(2.0, itofp(x)) -> ldexp(1.0, x)2191 if ((UseIntrinsic || !Ty->isVectorTy()) && BaseF->isExactlyValue(2.0) &&2192 (isa<SIToFPInst>(Expo) || isa<UIToFPInst>(Expo)) &&2193 (UseIntrinsic ||2194 hasFloatFn(M, TLI, Ty, LibFunc_ldexp, LibFunc_ldexpf, LibFunc_ldexpl))) {2195 2196 // TODO: Shouldn't really need to depend on getIntToFPVal for intrinsic. Can2197 // just directly use the original integer type.2198 if (Value *ExpoI = getIntToFPVal(Expo, B, TLI->getIntSize())) {2199 Constant *One = ConstantFP::get(Ty, 1.0);2200 2201 if (UseIntrinsic) {2202 return copyFlags(*Pow, B.CreateIntrinsic(Intrinsic::ldexp,2203 {Ty, ExpoI->getType()},2204 {One, ExpoI}, Pow, "exp2"));2205 }2206 2207 return copyFlags(*Pow, emitBinaryFloatFnCall(2208 One, ExpoI, TLI, LibFunc_ldexp, LibFunc_ldexpf,2209 LibFunc_ldexpl, B, NoAttrs));2210 }2211 }2212 2213 // pow(2.0 ** n, x) -> exp2(n * x)2214 if (hasFloatFn(M, TLI, Ty, LibFunc_exp2, LibFunc_exp2f, LibFunc_exp2l)) {2215 APFloat BaseR = APFloat(1.0);2216 BaseR.convert(BaseF->getSemantics(), APFloat::rmTowardZero, &Ignored);2217 BaseR = BaseR / *BaseF;2218 bool IsInteger = BaseF->isInteger(), IsReciprocal = BaseR.isInteger();2219 const APFloat *NF = IsReciprocal ? &BaseR : BaseF;2220 APSInt NI(64, false);2221 if ((IsInteger || IsReciprocal) &&2222 NF->convertToInteger(NI, APFloat::rmTowardZero, &Ignored) ==2223 APFloat::opOK &&2224 NI > 1 && NI.isPowerOf2()) {2225 double N = NI.logBase2() * (IsReciprocal ? -1.0 : 1.0);2226 Value *FMul = B.CreateFMul(Expo, ConstantFP::get(Ty, N), "mul");2227 if (Pow->doesNotAccessMemory())2228 return copyFlags(*Pow, B.CreateUnaryIntrinsic(Intrinsic::exp2, FMul,2229 nullptr, "exp2"));2230 else2231 return copyFlags(*Pow, emitUnaryFloatFnCall(FMul, TLI, LibFunc_exp2,2232 LibFunc_exp2f,2233 LibFunc_exp2l, B, NoAttrs));2234 }2235 }2236 2237 // pow(10.0, x) -> exp10(x)2238 if (BaseF->isExactlyValue(10.0) &&2239 hasFloatFn(M, TLI, Ty, LibFunc_exp10, LibFunc_exp10f, LibFunc_exp10l)) {2240 2241 if (Pow->doesNotAccessMemory()) {2242 CallInst *NewExp10 =2243 B.CreateIntrinsic(Intrinsic::exp10, {Ty}, {Expo}, Pow, "exp10");2244 return copyFlags(*Pow, NewExp10);2245 }2246 2247 return copyFlags(*Pow, emitUnaryFloatFnCall(Expo, TLI, LibFunc_exp10,2248 LibFunc_exp10f, LibFunc_exp10l,2249 B, NoAttrs));2250 }2251 2252 // pow(x, y) -> exp2(log2(x) * y)2253 if (Pow->hasApproxFunc() && Pow->hasNoNaNs() && BaseF->isFiniteNonZero() &&2254 !BaseF->isNegative()) {2255 // pow(1, inf) is defined to be 1 but exp2(log2(1) * inf) evaluates to NaN.2256 // Luckily optimizePow has already handled the x == 1 case.2257 assert(!match(Base, m_FPOne()) &&2258 "pow(1.0, y) should have been simplified earlier!");2259 2260 Value *Log = nullptr;2261 if (Ty->isFloatTy())2262 Log = ConstantFP::get(Ty, std::log2(BaseF->convertToFloat()));2263 else if (Ty->isDoubleTy())2264 Log = ConstantFP::get(Ty, std::log2(BaseF->convertToDouble()));2265 2266 if (Log) {2267 Value *FMul = B.CreateFMul(Log, Expo, "mul");2268 if (Pow->doesNotAccessMemory())2269 return copyFlags(*Pow, B.CreateUnaryIntrinsic(Intrinsic::exp2, FMul,2270 nullptr, "exp2"));2271 else if (hasFloatFn(M, TLI, Ty, LibFunc_exp2, LibFunc_exp2f,2272 LibFunc_exp2l))2273 return copyFlags(*Pow, emitUnaryFloatFnCall(FMul, TLI, LibFunc_exp2,2274 LibFunc_exp2f,2275 LibFunc_exp2l, B, NoAttrs));2276 }2277 }2278 2279 return nullptr;2280}2281 2282static Value *getSqrtCall(Value *V, AttributeList Attrs, bool NoErrno,2283 Module *M, IRBuilderBase &B,2284 const TargetLibraryInfo *TLI) {2285 // If errno is never set, then use the intrinsic for sqrt().2286 if (NoErrno)2287 return B.CreateUnaryIntrinsic(Intrinsic::sqrt, V, nullptr, "sqrt");2288 2289 // Otherwise, use the libcall for sqrt().2290 if (hasFloatFn(M, TLI, V->getType(), LibFunc_sqrt, LibFunc_sqrtf,2291 LibFunc_sqrtl))2292 // TODO: We also should check that the target can in fact lower the sqrt()2293 // libcall. We currently have no way to ask this question, so we ask if2294 // the target has a sqrt() libcall, which is not exactly the same.2295 return emitUnaryFloatFnCall(V, TLI, LibFunc_sqrt, LibFunc_sqrtf,2296 LibFunc_sqrtl, B, Attrs);2297 2298 return nullptr;2299}2300 2301/// Use square root in place of pow(x, +/-0.5).2302Value *LibCallSimplifier::replacePowWithSqrt(CallInst *Pow, IRBuilderBase &B) {2303 Value *Sqrt, *Base = Pow->getArgOperand(0), *Expo = Pow->getArgOperand(1);2304 Module *Mod = Pow->getModule();2305 Type *Ty = Pow->getType();2306 2307 const APFloat *ExpoF;2308 if (!match(Expo, m_APFloat(ExpoF)) ||2309 (!ExpoF->isExactlyValue(0.5) && !ExpoF->isExactlyValue(-0.5)))2310 return nullptr;2311 2312 // Converting pow(X, -0.5) to 1/sqrt(X) may introduce an extra rounding step,2313 // so that requires fast-math-flags (afn or reassoc).2314 if (ExpoF->isNegative() && (!Pow->hasApproxFunc() && !Pow->hasAllowReassoc()))2315 return nullptr;2316 2317 // If we have a pow() library call (accesses memory) and we can't guarantee2318 // that the base is not an infinity, give up:2319 // pow(-Inf, 0.5) is optionally required to have a result of +Inf (not setting2320 // errno), but sqrt(-Inf) is required by various standards to set errno.2321 if (!Pow->doesNotAccessMemory() && !Pow->hasNoInfs() &&2322 !isKnownNeverInfinity(2323 Base, SimplifyQuery(DL, TLI, DT, AC, Pow, true, true, DC)))2324 return nullptr;2325 2326 Sqrt = getSqrtCall(Base, AttributeList(), Pow->doesNotAccessMemory(), Mod, B,2327 TLI);2328 if (!Sqrt)2329 return nullptr;2330 2331 // Handle signed zero base by expanding to fabs(sqrt(x)).2332 if (!Pow->hasNoSignedZeros())2333 Sqrt = B.CreateUnaryIntrinsic(Intrinsic::fabs, Sqrt, nullptr, "abs");2334 2335 Sqrt = copyFlags(*Pow, Sqrt);2336 2337 // Handle non finite base by expanding to2338 // (x == -infinity ? +infinity : sqrt(x)).2339 if (!Pow->hasNoInfs()) {2340 Value *PosInf = ConstantFP::getInfinity(Ty),2341 *NegInf = ConstantFP::getInfinity(Ty, true);2342 Value *FCmp = B.CreateFCmpOEQ(Base, NegInf, "isinf");2343 Sqrt = B.CreateSelect(FCmp, PosInf, Sqrt);2344 }2345 2346 // If the exponent is negative, then get the reciprocal.2347 if (ExpoF->isNegative())2348 Sqrt = B.CreateFDiv(ConstantFP::get(Ty, 1.0), Sqrt, "reciprocal");2349 2350 return Sqrt;2351}2352 2353static Value *createPowWithIntegerExponent(Value *Base, Value *Expo, Module *M,2354 IRBuilderBase &B) {2355 Value *Args[] = {Base, Expo};2356 Type *Types[] = {Base->getType(), Expo->getType()};2357 return B.CreateIntrinsic(Intrinsic::powi, Types, Args);2358}2359 2360Value *LibCallSimplifier::optimizePow(CallInst *Pow, IRBuilderBase &B) {2361 Value *Base = Pow->getArgOperand(0);2362 Value *Expo = Pow->getArgOperand(1);2363 Function *Callee = Pow->getCalledFunction();2364 StringRef Name = Callee->getName();2365 Type *Ty = Pow->getType();2366 Module *M = Pow->getModule();2367 bool AllowApprox = Pow->hasApproxFunc();2368 bool Ignored;2369 2370 // Propagate the math semantics from the call to any created instructions.2371 IRBuilderBase::FastMathFlagGuard Guard(B);2372 B.setFastMathFlags(Pow->getFastMathFlags());2373 // Evaluate special cases related to the base.2374 2375 // pow(1.0, x) -> 1.02376 if (match(Base, m_FPOne()))2377 return Base;2378 2379 if (Value *Exp = replacePowWithExp(Pow, B))2380 return Exp;2381 2382 // Evaluate special cases related to the exponent.2383 2384 // pow(x, -1.0) -> 1.0 / x2385 if (match(Expo, m_SpecificFP(-1.0)))2386 return B.CreateFDiv(ConstantFP::get(Ty, 1.0), Base, "reciprocal");2387 2388 // pow(x, +/-0.0) -> 1.02389 if (match(Expo, m_AnyZeroFP()))2390 return ConstantFP::get(Ty, 1.0);2391 2392 // pow(x, 1.0) -> x2393 if (match(Expo, m_FPOne()))2394 return Base;2395 2396 // pow(x, 2.0) -> x * x2397 if (match(Expo, m_SpecificFP(2.0)))2398 return B.CreateFMul(Base, Base, "square");2399 2400 if (Value *Sqrt = replacePowWithSqrt(Pow, B))2401 return Sqrt;2402 2403 // If we can approximate pow:2404 // pow(x, n) -> powi(x, n) * sqrt(x) if n has exactly a 0.5 fraction2405 // pow(x, n) -> powi(x, n) if n is a constant signed integer value2406 const APFloat *ExpoF;2407 if (AllowApprox && match(Expo, m_APFloat(ExpoF)) &&2408 !ExpoF->isExactlyValue(0.5) && !ExpoF->isExactlyValue(-0.5)) {2409 APFloat ExpoA(abs(*ExpoF));2410 APFloat ExpoI(*ExpoF);2411 Value *Sqrt = nullptr;2412 if (!ExpoA.isInteger()) {2413 APFloat Expo2 = ExpoA;2414 // To check if ExpoA is an integer + 0.5, we add it to itself. If there2415 // is no floating point exception and the result is an integer, then2416 // ExpoA == integer + 0.52417 if (Expo2.add(ExpoA, APFloat::rmNearestTiesToEven) != APFloat::opOK)2418 return nullptr;2419 2420 if (!Expo2.isInteger())2421 return nullptr;2422 2423 if (ExpoI.roundToIntegral(APFloat::rmTowardNegative) !=2424 APFloat::opInexact)2425 return nullptr;2426 if (!ExpoI.isInteger())2427 return nullptr;2428 ExpoF = &ExpoI;2429 2430 Sqrt = getSqrtCall(Base, AttributeList(), Pow->doesNotAccessMemory(), M,2431 B, TLI);2432 if (!Sqrt)2433 return nullptr;2434 }2435 2436 // 0.5 fraction is now optionally handled.2437 // Do pow -> powi for remaining integer exponent2438 APSInt IntExpo(TLI->getIntSize(), /*isUnsigned=*/false);2439 if (ExpoF->isInteger() &&2440 ExpoF->convertToInteger(IntExpo, APFloat::rmTowardZero, &Ignored) ==2441 APFloat::opOK) {2442 Value *PowI = copyFlags(2443 *Pow,2444 createPowWithIntegerExponent(2445 Base, ConstantInt::get(B.getIntNTy(TLI->getIntSize()), IntExpo),2446 M, B));2447 2448 if (PowI && Sqrt)2449 return B.CreateFMul(PowI, Sqrt);2450 2451 return PowI;2452 }2453 }2454 2455 // powf(x, itofp(y)) -> powi(x, y)2456 if (AllowApprox && (isa<SIToFPInst>(Expo) || isa<UIToFPInst>(Expo))) {2457 if (Value *ExpoI = getIntToFPVal(Expo, B, TLI->getIntSize()))2458 return copyFlags(*Pow, createPowWithIntegerExponent(Base, ExpoI, M, B));2459 }2460 2461 // Shrink pow() to powf() if the arguments are single precision,2462 // unless the result is expected to be double precision.2463 if (UnsafeFPShrink && Name == TLI->getName(LibFunc_pow) &&2464 hasFloatVersion(M, Name)) {2465 if (Value *Shrunk = optimizeBinaryDoubleFP(Pow, B, TLI, true))2466 return Shrunk;2467 }2468 2469 return nullptr;2470}2471 2472Value *LibCallSimplifier::optimizeExp2(CallInst *CI, IRBuilderBase &B) {2473 Module *M = CI->getModule();2474 Function *Callee = CI->getCalledFunction();2475 StringRef Name = Callee->getName();2476 Value *Ret = nullptr;2477 if (UnsafeFPShrink && Name == TLI->getName(LibFunc_exp2) &&2478 hasFloatVersion(M, Name))2479 Ret = optimizeUnaryDoubleFP(CI, B, TLI, true);2480 2481 // If we have an llvm.exp2 intrinsic, emit the llvm.ldexp intrinsic. If we2482 // have the libcall, emit the libcall.2483 //2484 // TODO: In principle we should be able to just always use the intrinsic for2485 // any doesNotAccessMemory callsite.2486 2487 const bool UseIntrinsic = Callee->isIntrinsic();2488 // Bail out for vectors because the code below only expects scalars.2489 Type *Ty = CI->getType();2490 if (!UseIntrinsic && Ty->isVectorTy())2491 return Ret;2492 2493 // exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= IntSize2494 // exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < IntSize2495 Value *Op = CI->getArgOperand(0);2496 if ((isa<SIToFPInst>(Op) || isa<UIToFPInst>(Op)) &&2497 (UseIntrinsic ||2498 hasFloatFn(M, TLI, Ty, LibFunc_ldexp, LibFunc_ldexpf, LibFunc_ldexpl))) {2499 if (Value *Exp = getIntToFPVal(Op, B, TLI->getIntSize())) {2500 Constant *One = ConstantFP::get(Ty, 1.0);2501 2502 if (UseIntrinsic) {2503 return copyFlags(*CI, B.CreateIntrinsic(Intrinsic::ldexp,2504 {Ty, Exp->getType()},2505 {One, Exp}, CI));2506 }2507 2508 IRBuilderBase::FastMathFlagGuard Guard(B);2509 B.setFastMathFlags(CI->getFastMathFlags());2510 return copyFlags(*CI, emitBinaryFloatFnCall(2511 One, Exp, TLI, LibFunc_ldexp, LibFunc_ldexpf,2512 LibFunc_ldexpl, B, AttributeList()));2513 }2514 }2515 2516 return Ret;2517}2518 2519Value *LibCallSimplifier::optimizeFMinFMax(CallInst *CI, IRBuilderBase &B) {2520 Module *M = CI->getModule();2521 2522 // If we can shrink the call to a float function rather than a double2523 // function, do that first.2524 Function *Callee = CI->getCalledFunction();2525 StringRef Name = Callee->getName();2526 if ((Name == "fmin" || Name == "fmax") && hasFloatVersion(M, Name))2527 if (Value *Ret = optimizeBinaryDoubleFP(CI, B, TLI))2528 return Ret;2529 2530 // The LLVM intrinsics minnum/maxnum correspond to fmin/fmax. Canonicalize to2531 // the intrinsics for improved optimization (for example, vectorization).2532 // No-signed-zeros is implied by the definitions of fmax/fmin themselves.2533 // From the C standard draft WG14/N1256:2534 // "Ideally, fmax would be sensitive to the sign of zero, for example2535 // fmax(-0.0, +0.0) would return +0; however, implementation in software2536 // might be impractical."2537 FastMathFlags FMF = CI->getFastMathFlags();2538 FMF.setNoSignedZeros();2539 2540 Intrinsic::ID IID = Callee->getName().starts_with("fmin") ? Intrinsic::minnum2541 : Intrinsic::maxnum;2542 return copyFlags(*CI, B.CreateBinaryIntrinsic(IID, CI->getArgOperand(0),2543 CI->getArgOperand(1), FMF));2544}2545 2546Value *LibCallSimplifier::optimizeLog(CallInst *Log, IRBuilderBase &B) {2547 Function *LogFn = Log->getCalledFunction();2548 StringRef LogNm = LogFn->getName();2549 Intrinsic::ID LogID = LogFn->getIntrinsicID();2550 Module *Mod = Log->getModule();2551 Type *Ty = Log->getType();2552 2553 if (UnsafeFPShrink && hasFloatVersion(Mod, LogNm))2554 if (Value *Ret = optimizeUnaryDoubleFP(Log, B, TLI, true))2555 return Ret;2556 2557 LibFunc LogLb, ExpLb, Exp2Lb, Exp10Lb, PowLb;2558 2559 // This is only applicable to log(), log2(), log10().2560 if (TLI->getLibFunc(LogNm, LogLb)) {2561 switch (LogLb) {2562 case LibFunc_logf:2563 LogID = Intrinsic::log;2564 ExpLb = LibFunc_expf;2565 Exp2Lb = LibFunc_exp2f;2566 Exp10Lb = LibFunc_exp10f;2567 PowLb = LibFunc_powf;2568 break;2569 case LibFunc_log:2570 LogID = Intrinsic::log;2571 ExpLb = LibFunc_exp;2572 Exp2Lb = LibFunc_exp2;2573 Exp10Lb = LibFunc_exp10;2574 PowLb = LibFunc_pow;2575 break;2576 case LibFunc_logl:2577 LogID = Intrinsic::log;2578 ExpLb = LibFunc_expl;2579 Exp2Lb = LibFunc_exp2l;2580 Exp10Lb = LibFunc_exp10l;2581 PowLb = LibFunc_powl;2582 break;2583 case LibFunc_log2f:2584 LogID = Intrinsic::log2;2585 ExpLb = LibFunc_expf;2586 Exp2Lb = LibFunc_exp2f;2587 Exp10Lb = LibFunc_exp10f;2588 PowLb = LibFunc_powf;2589 break;2590 case LibFunc_log2:2591 LogID = Intrinsic::log2;2592 ExpLb = LibFunc_exp;2593 Exp2Lb = LibFunc_exp2;2594 Exp10Lb = LibFunc_exp10;2595 PowLb = LibFunc_pow;2596 break;2597 case LibFunc_log2l:2598 LogID = Intrinsic::log2;2599 ExpLb = LibFunc_expl;2600 Exp2Lb = LibFunc_exp2l;2601 Exp10Lb = LibFunc_exp10l;2602 PowLb = LibFunc_powl;2603 break;2604 case LibFunc_log10f:2605 LogID = Intrinsic::log10;2606 ExpLb = LibFunc_expf;2607 Exp2Lb = LibFunc_exp2f;2608 Exp10Lb = LibFunc_exp10f;2609 PowLb = LibFunc_powf;2610 break;2611 case LibFunc_log10:2612 LogID = Intrinsic::log10;2613 ExpLb = LibFunc_exp;2614 Exp2Lb = LibFunc_exp2;2615 Exp10Lb = LibFunc_exp10;2616 PowLb = LibFunc_pow;2617 break;2618 case LibFunc_log10l:2619 LogID = Intrinsic::log10;2620 ExpLb = LibFunc_expl;2621 Exp2Lb = LibFunc_exp2l;2622 Exp10Lb = LibFunc_exp10l;2623 PowLb = LibFunc_powl;2624 break;2625 default:2626 return nullptr;2627 }2628 2629 // Convert libcall to intrinsic if the value is known > 0.2630 bool IsKnownNoErrno = Log->hasNoNaNs() && Log->hasNoInfs();2631 if (!IsKnownNoErrno) {2632 SimplifyQuery SQ(DL, TLI, DT, AC, Log, true, true, DC);2633 KnownFPClass Known = computeKnownFPClass(2634 Log->getOperand(0),2635 KnownFPClass::OrderedLessThanZeroMask | fcSubnormal, SQ);2636 Function *F = Log->getParent()->getParent();2637 const fltSemantics &FltSem = Ty->getScalarType()->getFltSemantics();2638 IsKnownNoErrno =2639 Known.cannotBeOrderedLessThanZero() &&2640 Known.isKnownNeverLogicalZero(F->getDenormalMode(FltSem));2641 }2642 if (IsKnownNoErrno) {2643 auto *NewLog = B.CreateUnaryIntrinsic(LogID, Log->getArgOperand(0), Log);2644 NewLog->copyMetadata(*Log);2645 return copyFlags(*Log, NewLog);2646 }2647 } else if (LogID == Intrinsic::log || LogID == Intrinsic::log2 ||2648 LogID == Intrinsic::log10) {2649 if (Ty->getScalarType()->isFloatTy()) {2650 ExpLb = LibFunc_expf;2651 Exp2Lb = LibFunc_exp2f;2652 Exp10Lb = LibFunc_exp10f;2653 PowLb = LibFunc_powf;2654 } else if (Ty->getScalarType()->isDoubleTy()) {2655 ExpLb = LibFunc_exp;2656 Exp2Lb = LibFunc_exp2;2657 Exp10Lb = LibFunc_exp10;2658 PowLb = LibFunc_pow;2659 } else2660 return nullptr;2661 } else2662 return nullptr;2663 2664 // The earlier call must also be 'fast' in order to do these transforms.2665 CallInst *Arg = dyn_cast<CallInst>(Log->getArgOperand(0));2666 if (!Log->isFast() || !Arg || !Arg->isFast() || !Arg->hasOneUse())2667 return nullptr;2668 2669 IRBuilderBase::FastMathFlagGuard Guard(B);2670 B.setFastMathFlags(FastMathFlags::getFast());2671 2672 Intrinsic::ID ArgID = Arg->getIntrinsicID();2673 LibFunc ArgLb = NotLibFunc;2674 TLI->getLibFunc(*Arg, ArgLb);2675 2676 // log(pow(x,y)) -> y*log(x)2677 AttributeList NoAttrs;2678 if (ArgLb == PowLb || ArgID == Intrinsic::pow || ArgID == Intrinsic::powi) {2679 Value *LogX =2680 Log->doesNotAccessMemory()2681 ? B.CreateUnaryIntrinsic(LogID, Arg->getOperand(0), nullptr, "log")2682 : emitUnaryFloatFnCall(Arg->getOperand(0), TLI, LogNm, B, NoAttrs);2683 Value *Y = Arg->getArgOperand(1);2684 // Cast exponent to FP if integer.2685 if (ArgID == Intrinsic::powi)2686 Y = B.CreateSIToFP(Y, Ty, "cast");2687 Value *MulY = B.CreateFMul(Y, LogX, "mul");2688 // Since pow() may have side effects, e.g. errno,2689 // dead code elimination may not be trusted to remove it.2690 substituteInParent(Arg, MulY);2691 return MulY;2692 }2693 2694 // log(exp{,2,10}(y)) -> y*log({e,2,10})2695 // TODO: There is no exp10() intrinsic yet.2696 if (ArgLb == ExpLb || ArgLb == Exp2Lb || ArgLb == Exp10Lb ||2697 ArgID == Intrinsic::exp || ArgID == Intrinsic::exp2) {2698 Constant *Eul;2699 if (ArgLb == ExpLb || ArgID == Intrinsic::exp)2700 // FIXME: Add more precise value of e for long double.2701 Eul = ConstantFP::get(Log->getType(), numbers::e);2702 else if (ArgLb == Exp2Lb || ArgID == Intrinsic::exp2)2703 Eul = ConstantFP::get(Log->getType(), 2.0);2704 else2705 Eul = ConstantFP::get(Log->getType(), 10.0);2706 Value *LogE = Log->doesNotAccessMemory()2707 ? B.CreateUnaryIntrinsic(LogID, Eul, nullptr, "log")2708 : emitUnaryFloatFnCall(Eul, TLI, LogNm, B, NoAttrs);2709 Value *MulY = B.CreateFMul(Arg->getArgOperand(0), LogE, "mul");2710 // Since exp() may have side effects, e.g. errno,2711 // dead code elimination may not be trusted to remove it.2712 substituteInParent(Arg, MulY);2713 return MulY;2714 }2715 2716 return nullptr;2717}2718 2719// sqrt(exp(X)) -> exp(X * 0.5)2720Value *LibCallSimplifier::mergeSqrtToExp(CallInst *CI, IRBuilderBase &B) {2721 if (!CI->hasAllowReassoc())2722 return nullptr;2723 2724 Function *SqrtFn = CI->getCalledFunction();2725 CallInst *Arg = dyn_cast<CallInst>(CI->getArgOperand(0));2726 if (!Arg || !Arg->hasAllowReassoc() || !Arg->hasOneUse())2727 return nullptr;2728 Intrinsic::ID ArgID = Arg->getIntrinsicID();2729 LibFunc ArgLb = NotLibFunc;2730 TLI->getLibFunc(*Arg, ArgLb);2731 2732 LibFunc SqrtLb, ExpLb, Exp2Lb, Exp10Lb;2733 2734 if (TLI->getLibFunc(SqrtFn->getName(), SqrtLb))2735 switch (SqrtLb) {2736 case LibFunc_sqrtf:2737 ExpLb = LibFunc_expf;2738 Exp2Lb = LibFunc_exp2f;2739 Exp10Lb = LibFunc_exp10f;2740 break;2741 case LibFunc_sqrt:2742 ExpLb = LibFunc_exp;2743 Exp2Lb = LibFunc_exp2;2744 Exp10Lb = LibFunc_exp10;2745 break;2746 case LibFunc_sqrtl:2747 ExpLb = LibFunc_expl;2748 Exp2Lb = LibFunc_exp2l;2749 Exp10Lb = LibFunc_exp10l;2750 break;2751 default:2752 return nullptr;2753 }2754 else if (SqrtFn->getIntrinsicID() == Intrinsic::sqrt) {2755 if (CI->getType()->getScalarType()->isFloatTy()) {2756 ExpLb = LibFunc_expf;2757 Exp2Lb = LibFunc_exp2f;2758 Exp10Lb = LibFunc_exp10f;2759 } else if (CI->getType()->getScalarType()->isDoubleTy()) {2760 ExpLb = LibFunc_exp;2761 Exp2Lb = LibFunc_exp2;2762 Exp10Lb = LibFunc_exp10;2763 } else2764 return nullptr;2765 } else2766 return nullptr;2767 2768 if (ArgLb != ExpLb && ArgLb != Exp2Lb && ArgLb != Exp10Lb &&2769 ArgID != Intrinsic::exp && ArgID != Intrinsic::exp2)2770 return nullptr;2771 2772 IRBuilderBase::InsertPointGuard Guard(B);2773 B.SetInsertPoint(Arg);2774 auto *ExpOperand = Arg->getOperand(0);2775 auto *FMul =2776 B.CreateFMulFMF(ExpOperand, ConstantFP::get(ExpOperand->getType(), 0.5),2777 CI, "merged.sqrt");2778 2779 Arg->setOperand(0, FMul);2780 return Arg;2781}2782 2783Value *LibCallSimplifier::optimizeSqrt(CallInst *CI, IRBuilderBase &B) {2784 Module *M = CI->getModule();2785 Function *Callee = CI->getCalledFunction();2786 Value *Ret = nullptr;2787 // TODO: Once we have a way (other than checking for the existince of the2788 // libcall) to tell whether our target can lower @llvm.sqrt, relax the2789 // condition below.2790 if (isLibFuncEmittable(M, TLI, LibFunc_sqrtf) &&2791 (Callee->getName() == "sqrt" ||2792 Callee->getIntrinsicID() == Intrinsic::sqrt))2793 Ret = optimizeUnaryDoubleFP(CI, B, TLI, true);2794 2795 if (Value *Opt = mergeSqrtToExp(CI, B))2796 return Opt;2797 2798 if (!CI->isFast())2799 return Ret;2800 2801 Instruction *I = dyn_cast<Instruction>(CI->getArgOperand(0));2802 if (!I || I->getOpcode() != Instruction::FMul || !I->isFast())2803 return Ret;2804 2805 // We're looking for a repeated factor in a multiplication tree,2806 // so we can do this fold: sqrt(x * x) -> fabs(x);2807 // or this fold: sqrt((x * x) * y) -> fabs(x) * sqrt(y).2808 Value *Op0 = I->getOperand(0);2809 Value *Op1 = I->getOperand(1);2810 Value *RepeatOp = nullptr;2811 Value *OtherOp = nullptr;2812 if (Op0 == Op1) {2813 // Simple match: the operands of the multiply are identical.2814 RepeatOp = Op0;2815 } else {2816 // Look for a more complicated pattern: one of the operands is itself2817 // a multiply, so search for a common factor in that multiply.2818 // Note: We don't bother looking any deeper than this first level or for2819 // variations of this pattern because instcombine's visitFMUL and/or the2820 // reassociation pass should give us this form.2821 Value *MulOp;2822 if (match(Op0, m_FMul(m_Value(MulOp), m_Deferred(MulOp))) &&2823 cast<Instruction>(Op0)->isFast()) {2824 // Pattern: sqrt((x * x) * z)2825 RepeatOp = MulOp;2826 OtherOp = Op1;2827 } else if (match(Op1, m_FMul(m_Value(MulOp), m_Deferred(MulOp))) &&2828 cast<Instruction>(Op1)->isFast()) {2829 // Pattern: sqrt(z * (x * x))2830 RepeatOp = MulOp;2831 OtherOp = Op0;2832 }2833 }2834 if (!RepeatOp)2835 return Ret;2836 2837 // Fast math flags for any created instructions should match the sqrt2838 // and multiply.2839 2840 // If we found a repeated factor, hoist it out of the square root and2841 // replace it with the fabs of that factor.2842 Value *FabsCall =2843 B.CreateUnaryIntrinsic(Intrinsic::fabs, RepeatOp, I, "fabs");2844 if (OtherOp) {2845 // If we found a non-repeated factor, we still need to get its square2846 // root. We then multiply that by the value that was simplified out2847 // of the square root calculation.2848 Value *SqrtCall =2849 B.CreateUnaryIntrinsic(Intrinsic::sqrt, OtherOp, I, "sqrt");2850 return copyFlags(*CI, B.CreateFMulFMF(FabsCall, SqrtCall, I));2851 }2852 return copyFlags(*CI, FabsCall);2853}2854 2855Value *LibCallSimplifier::optimizeFMod(CallInst *CI, IRBuilderBase &B) {2856 2857 // fmod(x,y) can set errno if y == 0 or x == +/-inf, and returns Nan in those2858 // case. If we know those do not happen, then we can convert the fmod into2859 // frem.2860 bool IsNoNan = CI->hasNoNaNs();2861 if (!IsNoNan) {2862 SimplifyQuery SQ(DL, TLI, DT, AC, CI, true, true, DC);2863 KnownFPClass Known0 = computeKnownFPClass(CI->getOperand(0), fcInf, SQ);2864 if (Known0.isKnownNeverInfinity()) {2865 KnownFPClass Known1 =2866 computeKnownFPClass(CI->getOperand(1), fcZero | fcSubnormal, SQ);2867 Function *F = CI->getParent()->getParent();2868 const fltSemantics &FltSem =2869 CI->getType()->getScalarType()->getFltSemantics();2870 IsNoNan = Known1.isKnownNeverLogicalZero(F->getDenormalMode(FltSem));2871 }2872 }2873 2874 if (IsNoNan) {2875 Value *FRem = B.CreateFRemFMF(CI->getOperand(0), CI->getOperand(1), CI);2876 if (auto *FRemI = dyn_cast<Instruction>(FRem))2877 FRemI->setHasNoNaNs(true);2878 return FRem;2879 }2880 return nullptr;2881}2882 2883Value *LibCallSimplifier::optimizeTrigInversionPairs(CallInst *CI,2884 IRBuilderBase &B) {2885 Module *M = CI->getModule();2886 Function *Callee = CI->getCalledFunction();2887 Value *Ret = nullptr;2888 StringRef Name = Callee->getName();2889 if (UnsafeFPShrink &&2890 (Name == "tan" || Name == "atanh" || Name == "sinh" || Name == "cosh" ||2891 Name == "asinh") &&2892 hasFloatVersion(M, Name))2893 Ret = optimizeUnaryDoubleFP(CI, B, TLI, true);2894 2895 Value *Op1 = CI->getArgOperand(0);2896 auto *OpC = dyn_cast<CallInst>(Op1);2897 if (!OpC)2898 return Ret;2899 2900 // Both calls must be 'fast' in order to remove them.2901 if (!CI->isFast() || !OpC->isFast())2902 return Ret;2903 2904 // tan(atan(x)) -> x2905 // atanh(tanh(x)) -> x2906 // sinh(asinh(x)) -> x2907 // asinh(sinh(x)) -> x2908 // cosh(acosh(x)) -> x2909 LibFunc Func;2910 Function *F = OpC->getCalledFunction();2911 if (F && TLI->getLibFunc(F->getName(), Func) &&2912 isLibFuncEmittable(M, TLI, Func)) {2913 LibFunc inverseFunc = llvm::StringSwitch<LibFunc>(Callee->getName())2914 .Case("tan", LibFunc_atan)2915 .Case("atanh", LibFunc_tanh)2916 .Case("sinh", LibFunc_asinh)2917 .Case("cosh", LibFunc_acosh)2918 .Case("tanf", LibFunc_atanf)2919 .Case("atanhf", LibFunc_tanhf)2920 .Case("sinhf", LibFunc_asinhf)2921 .Case("coshf", LibFunc_acoshf)2922 .Case("tanl", LibFunc_atanl)2923 .Case("atanhl", LibFunc_tanhl)2924 .Case("sinhl", LibFunc_asinhl)2925 .Case("coshl", LibFunc_acoshl)2926 .Case("asinh", LibFunc_sinh)2927 .Case("asinhf", LibFunc_sinhf)2928 .Case("asinhl", LibFunc_sinhl)2929 .Default(NotLibFunc); // Used as error value2930 if (Func == inverseFunc)2931 Ret = OpC->getArgOperand(0);2932 }2933 return Ret;2934}2935 2936static bool isTrigLibCall(CallInst *CI) {2937 // We can only hope to do anything useful if we can ignore things like errno2938 // and floating-point exceptions.2939 // We already checked the prototype.2940 return CI->doesNotThrow() && CI->doesNotAccessMemory();2941}2942 2943static bool insertSinCosCall(IRBuilderBase &B, Function *OrigCallee, Value *Arg,2944 bool UseFloat, Value *&Sin, Value *&Cos,2945 Value *&SinCos, const TargetLibraryInfo *TLI) {2946 Module *M = OrigCallee->getParent();2947 Type *ArgTy = Arg->getType();2948 Type *ResTy;2949 StringRef Name;2950 2951 Triple T(OrigCallee->getParent()->getTargetTriple());2952 if (UseFloat) {2953 Name = "__sincospif_stret";2954 2955 assert(T.getArch() != Triple::x86 && "x86 messy and unsupported for now");2956 // x86_64 can't use {float, float} since that would be returned in both2957 // xmm0 and xmm1, which isn't what a real struct would do.2958 ResTy = T.getArch() == Triple::x86_642959 ? static_cast<Type *>(FixedVectorType::get(ArgTy, 2))2960 : static_cast<Type *>(StructType::get(ArgTy, ArgTy));2961 } else {2962 Name = "__sincospi_stret";2963 ResTy = StructType::get(ArgTy, ArgTy);2964 }2965 2966 if (!isLibFuncEmittable(M, TLI, Name))2967 return false;2968 LibFunc TheLibFunc;2969 TLI->getLibFunc(Name, TheLibFunc);2970 FunctionCallee Callee = getOrInsertLibFunc(2971 M, *TLI, TheLibFunc, OrigCallee->getAttributes(), ResTy, ArgTy);2972 2973 if (Instruction *ArgInst = dyn_cast<Instruction>(Arg)) {2974 // If the argument is an instruction, it must dominate all uses so put our2975 // sincos call there.2976 B.SetInsertPoint(ArgInst->getParent(), ++ArgInst->getIterator());2977 } else {2978 // Otherwise (e.g. for a constant) the beginning of the function is as2979 // good a place as any.2980 BasicBlock &EntryBB = B.GetInsertBlock()->getParent()->getEntryBlock();2981 B.SetInsertPoint(&EntryBB, EntryBB.begin());2982 }2983 2984 SinCos = B.CreateCall(Callee, Arg, "sincospi");2985 2986 if (SinCos->getType()->isStructTy()) {2987 Sin = B.CreateExtractValue(SinCos, 0, "sinpi");2988 Cos = B.CreateExtractValue(SinCos, 1, "cospi");2989 } else {2990 Sin = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 0),2991 "sinpi");2992 Cos = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 1),2993 "cospi");2994 }2995 2996 return true;2997}2998 2999static Value *optimizeSymmetricCall(CallInst *CI, bool IsEven,3000 IRBuilderBase &B) {3001 Value *X;3002 Value *Src = CI->getArgOperand(0);3003 3004 if (match(Src, m_OneUse(m_FNeg(m_Value(X))))) {3005 auto *Call = B.CreateCall(CI->getCalledFunction(), {X});3006 Call->copyFastMathFlags(CI);3007 auto *CallInst = copyFlags(*CI, Call);3008 if (IsEven) {3009 // Even function: f(-x) = f(x)3010 return CallInst;3011 }3012 // Odd function: f(-x) = -f(x)3013 return B.CreateFNegFMF(CallInst, CI);3014 }3015 3016 // Even function: f(abs(x)) = f(x), f(copysign(x, y)) = f(x)3017 if (IsEven && (match(Src, m_FAbs(m_Value(X))) ||3018 match(Src, m_CopySign(m_Value(X), m_Value())))) {3019 auto *Call = B.CreateCall(CI->getCalledFunction(), {X});3020 Call->copyFastMathFlags(CI);3021 return copyFlags(*CI, Call);3022 }3023 3024 return nullptr;3025}3026 3027Value *LibCallSimplifier::optimizeSymmetric(CallInst *CI, LibFunc Func,3028 IRBuilderBase &B) {3029 switch (Func) {3030 case LibFunc_cos:3031 case LibFunc_cosf:3032 case LibFunc_cosl:3033 return optimizeSymmetricCall(CI, /*IsEven*/ true, B);3034 3035 case LibFunc_sin:3036 case LibFunc_sinf:3037 case LibFunc_sinl:3038 3039 case LibFunc_tan:3040 case LibFunc_tanf:3041 case LibFunc_tanl:3042 3043 case LibFunc_erf:3044 case LibFunc_erff:3045 case LibFunc_erfl:3046 return optimizeSymmetricCall(CI, /*IsEven*/ false, B);3047 3048 default:3049 return nullptr;3050 }3051}3052 3053Value *LibCallSimplifier::optimizeSinCosPi(CallInst *CI, bool IsSin, IRBuilderBase &B) {3054 // Make sure the prototype is as expected, otherwise the rest of the3055 // function is probably invalid and likely to abort.3056 if (!isTrigLibCall(CI))3057 return nullptr;3058 3059 Value *Arg = CI->getArgOperand(0);3060 if (isa<ConstantData>(Arg))3061 return nullptr;3062 3063 SmallVector<CallInst *, 1> SinCalls;3064 SmallVector<CallInst *, 1> CosCalls;3065 SmallVector<CallInst *, 1> SinCosCalls;3066 3067 bool IsFloat = Arg->getType()->isFloatTy();3068 3069 // Look for all compatible sinpi, cospi and sincospi calls with the same3070 // argument. If there are enough (in some sense) we can make the3071 // substitution.3072 Function *F = CI->getFunction();3073 for (User *U : Arg->users())3074 classifyArgUse(U, F, IsFloat, SinCalls, CosCalls, SinCosCalls);3075 3076 // It's only worthwhile if both sinpi and cospi are actually used.3077 if (SinCalls.empty() || CosCalls.empty())3078 return nullptr;3079 3080 Value *Sin, *Cos, *SinCos;3081 if (!insertSinCosCall(B, CI->getCalledFunction(), Arg, IsFloat, Sin, Cos,3082 SinCos, TLI))3083 return nullptr;3084 3085 auto replaceTrigInsts = [this](SmallVectorImpl<CallInst *> &Calls,3086 Value *Res) {3087 for (CallInst *C : Calls)3088 replaceAllUsesWith(C, Res);3089 };3090 3091 replaceTrigInsts(SinCalls, Sin);3092 replaceTrigInsts(CosCalls, Cos);3093 replaceTrigInsts(SinCosCalls, SinCos);3094 3095 return IsSin ? Sin : Cos;3096}3097 3098void LibCallSimplifier::classifyArgUse(3099 Value *Val, Function *F, bool IsFloat,3100 SmallVectorImpl<CallInst *> &SinCalls,3101 SmallVectorImpl<CallInst *> &CosCalls,3102 SmallVectorImpl<CallInst *> &SinCosCalls) {3103 auto *CI = dyn_cast<CallInst>(Val);3104 if (!CI || CI->use_empty())3105 return;3106 3107 // Don't consider calls in other functions.3108 if (CI->getFunction() != F)3109 return;3110 3111 Module *M = CI->getModule();3112 Function *Callee = CI->getCalledFunction();3113 LibFunc Func;3114 if (!Callee || !TLI->getLibFunc(*Callee, Func) ||3115 !isLibFuncEmittable(M, TLI, Func) ||3116 !isTrigLibCall(CI))3117 return;3118 3119 if (IsFloat) {3120 if (Func == LibFunc_sinpif)3121 SinCalls.push_back(CI);3122 else if (Func == LibFunc_cospif)3123 CosCalls.push_back(CI);3124 else if (Func == LibFunc_sincospif_stret)3125 SinCosCalls.push_back(CI);3126 } else {3127 if (Func == LibFunc_sinpi)3128 SinCalls.push_back(CI);3129 else if (Func == LibFunc_cospi)3130 CosCalls.push_back(CI);3131 else if (Func == LibFunc_sincospi_stret)3132 SinCosCalls.push_back(CI);3133 }3134}3135 3136/// Constant folds remquo3137Value *LibCallSimplifier::optimizeRemquo(CallInst *CI, IRBuilderBase &B) {3138 const APFloat *X, *Y;3139 if (!match(CI->getArgOperand(0), m_APFloat(X)) ||3140 !match(CI->getArgOperand(1), m_APFloat(Y)))3141 return nullptr;3142 3143 APFloat::opStatus Status;3144 APFloat Quot = *X;3145 Status = Quot.divide(*Y, APFloat::rmNearestTiesToEven);3146 if (Status != APFloat::opOK && Status != APFloat::opInexact)3147 return nullptr;3148 APFloat Rem = *X;3149 if (Rem.remainder(*Y) != APFloat::opOK)3150 return nullptr;3151 3152 // TODO: We can only keep at least the three of the last bits of x/y3153 unsigned IntBW = TLI->getIntSize();3154 APSInt QuotInt(IntBW, /*isUnsigned=*/false);3155 bool IsExact;3156 Status =3157 Quot.convertToInteger(QuotInt, APFloat::rmNearestTiesToEven, &IsExact);3158 if (Status != APFloat::opOK && Status != APFloat::opInexact)3159 return nullptr;3160 3161 B.CreateAlignedStore(3162 ConstantInt::get(B.getIntNTy(IntBW), QuotInt.getExtValue()),3163 CI->getArgOperand(2), CI->getParamAlign(2));3164 return ConstantFP::get(CI->getType(), Rem);3165}3166 3167/// Constant folds fdim3168Value *LibCallSimplifier::optimizeFdim(CallInst *CI, IRBuilderBase &B) {3169 // Cannot perform the fold unless the call has attribute memory(none)3170 if (!CI->doesNotAccessMemory())3171 return nullptr;3172 3173 // TODO : Handle undef values3174 // Propagate poison if any3175 if (isa<PoisonValue>(CI->getArgOperand(0)))3176 return CI->getArgOperand(0);3177 if (isa<PoisonValue>(CI->getArgOperand(1)))3178 return CI->getArgOperand(1);3179 3180 const APFloat *X, *Y;3181 // Check if both values are constants3182 if (!match(CI->getArgOperand(0), m_APFloat(X)) ||3183 !match(CI->getArgOperand(1), m_APFloat(Y)))3184 return nullptr;3185 3186 APFloat Difference = *X;3187 Difference.subtract(*Y, RoundingMode::NearestTiesToEven);3188 3189 APFloat MaxVal =3190 maximum(Difference, APFloat::getZero(CI->getType()->getFltSemantics()));3191 return ConstantFP::get(CI->getType(), MaxVal);3192}3193 3194//===----------------------------------------------------------------------===//3195// Integer Library Call Optimizations3196//===----------------------------------------------------------------------===//3197 3198Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilderBase &B) {3199 // All variants of ffs return int which need not be 32 bits wide.3200 // ffs{,l,ll}(x) -> x != 0 ? (int)llvm.cttz(x)+1 : 03201 Type *RetType = CI->getType();3202 Value *Op = CI->getArgOperand(0);3203 Type *ArgType = Op->getType();3204 Value *V = B.CreateIntrinsic(Intrinsic::cttz, {ArgType}, {Op, B.getTrue()},3205 nullptr, "cttz");3206 V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));3207 V = B.CreateIntCast(V, RetType, false);3208 3209 Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));3210 return B.CreateSelect(Cond, V, ConstantInt::get(RetType, 0));3211}3212 3213Value *LibCallSimplifier::optimizeFls(CallInst *CI, IRBuilderBase &B) {3214 // All variants of fls return int which need not be 32 bits wide.3215 // fls{,l,ll}(x) -> (int)(sizeInBits(x) - llvm.ctlz(x, false))3216 Value *Op = CI->getArgOperand(0);3217 Type *ArgType = Op->getType();3218 Value *V = B.CreateIntrinsic(Intrinsic::ctlz, {ArgType}, {Op, B.getFalse()},3219 nullptr, "ctlz");3220 V = B.CreateSub(ConstantInt::get(V->getType(), ArgType->getIntegerBitWidth()),3221 V);3222 return B.CreateIntCast(V, CI->getType(), false);3223}3224 3225Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilderBase &B) {3226 // abs(x) -> x <s 0 ? -x : x3227 // The negation has 'nsw' because abs of INT_MIN is undefined.3228 Value *X = CI->getArgOperand(0);3229 Value *IsNeg = B.CreateIsNeg(X);3230 Value *NegX = B.CreateNSWNeg(X, "neg");3231 return B.CreateSelect(IsNeg, NegX, X);3232}3233 3234Value *LibCallSimplifier::optimizeIsDigit(CallInst *CI, IRBuilderBase &B) {3235 // isdigit(c) -> (c-'0') <u 103236 Value *Op = CI->getArgOperand(0);3237 Type *ArgType = Op->getType();3238 Op = B.CreateSub(Op, ConstantInt::get(ArgType, '0'), "isdigittmp");3239 Op = B.CreateICmpULT(Op, ConstantInt::get(ArgType, 10), "isdigit");3240 return B.CreateZExt(Op, CI->getType());3241}3242 3243Value *LibCallSimplifier::optimizeIsAscii(CallInst *CI, IRBuilderBase &B) {3244 // isascii(c) -> c <u 1283245 Value *Op = CI->getArgOperand(0);3246 Type *ArgType = Op->getType();3247 Op = B.CreateICmpULT(Op, ConstantInt::get(ArgType, 128), "isascii");3248 return B.CreateZExt(Op, CI->getType());3249}3250 3251Value *LibCallSimplifier::optimizeToAscii(CallInst *CI, IRBuilderBase &B) {3252 // toascii(c) -> c & 0x7f3253 return B.CreateAnd(CI->getArgOperand(0),3254 ConstantInt::get(CI->getType(), 0x7F));3255}3256 3257// Fold calls to atoi, atol, and atoll.3258Value *LibCallSimplifier::optimizeAtoi(CallInst *CI, IRBuilderBase &B) {3259 StringRef Str;3260 if (!getConstantStringInfo(CI->getArgOperand(0), Str))3261 return nullptr;3262 3263 return convertStrToInt(CI, Str, nullptr, 10, /*AsSigned=*/true, B);3264}3265 3266// Fold calls to strtol, strtoll, strtoul, and strtoull.3267Value *LibCallSimplifier::optimizeStrToInt(CallInst *CI, IRBuilderBase &B,3268 bool AsSigned) {3269 Value *EndPtr = CI->getArgOperand(1);3270 if (isa<ConstantPointerNull>(EndPtr)) {3271 // With a null EndPtr, this function won't capture the main argument.3272 // It would be readonly too, except that it still may write to errno.3273 CI->addParamAttr(0, Attribute::getWithCaptureInfo(CI->getContext(),3274 CaptureInfo::none()));3275 EndPtr = nullptr;3276 } else if (!isKnownNonZero(EndPtr, DL))3277 return nullptr;3278 3279 StringRef Str;3280 if (!getConstantStringInfo(CI->getArgOperand(0), Str))3281 return nullptr;3282 3283 if (ConstantInt *CInt = dyn_cast<ConstantInt>(CI->getArgOperand(2))) {3284 return convertStrToInt(CI, Str, EndPtr, CInt->getSExtValue(), AsSigned, B);3285 }3286 3287 return nullptr;3288}3289 3290//===----------------------------------------------------------------------===//3291// Formatting and IO Library Call Optimizations3292//===----------------------------------------------------------------------===//3293 3294static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg);3295 3296Value *LibCallSimplifier::optimizeErrorReporting(CallInst *CI, IRBuilderBase &B,3297 int StreamArg) {3298 Function *Callee = CI->getCalledFunction();3299 // Error reporting calls should be cold, mark them as such.3300 // This applies even to non-builtin calls: it is only a hint and applies to3301 // functions that the frontend might not understand as builtins.3302 3303 // This heuristic was suggested in:3304 // Improving Static Branch Prediction in a Compiler3305 // Brian L. Deitrich, Ben-Chung Cheng, Wen-mei W. Hwu3306 // Proceedings of PACT'98, Oct. 1998, IEEE3307 if (!CI->hasFnAttr(Attribute::Cold) &&3308 isReportingError(Callee, CI, StreamArg)) {3309 CI->addFnAttr(Attribute::Cold);3310 }3311 3312 return nullptr;3313}3314 3315static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg) {3316 if (!Callee || !Callee->isDeclaration())3317 return false;3318 3319 if (StreamArg < 0)3320 return true;3321 3322 // These functions might be considered cold, but only if their stream3323 // argument is stderr.3324 3325 if (StreamArg >= (int)CI->arg_size())3326 return false;3327 LoadInst *LI = dyn_cast<LoadInst>(CI->getArgOperand(StreamArg));3328 if (!LI)3329 return false;3330 GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getPointerOperand());3331 if (!GV || !GV->isDeclaration())3332 return false;3333 return GV->getName() == "stderr";3334}3335 3336Value *LibCallSimplifier::optimizePrintFString(CallInst *CI, IRBuilderBase &B) {3337 // Check for a fixed format string.3338 StringRef FormatStr;3339 if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))3340 return nullptr;3341 3342 // Empty format string -> noop.3343 if (FormatStr.empty()) // Tolerate printf's declared void.3344 return CI->use_empty() ? (Value *)CI : ConstantInt::get(CI->getType(), 0);3345 3346 // Do not do any of the following transformations if the printf return value3347 // is used, in general the printf return value is not compatible with either3348 // putchar() or puts().3349 if (!CI->use_empty())3350 return nullptr;3351 3352 Type *IntTy = CI->getType();3353 // printf("x") -> putchar('x'), even for "%" and "%%".3354 if (FormatStr.size() == 1 || FormatStr == "%%") {3355 // Convert the character to unsigned char before passing it to putchar3356 // to avoid host-specific sign extension in the IR. Putchar converts3357 // it to unsigned char regardless.3358 Value *IntChar = ConstantInt::get(IntTy, (unsigned char)FormatStr[0]);3359 return copyFlags(*CI, emitPutChar(IntChar, B, TLI));3360 }3361 3362 // Try to remove call or emit putchar/puts.3363 if (FormatStr == "%s" && CI->arg_size() > 1) {3364 StringRef OperandStr;3365 if (!getConstantStringInfo(CI->getOperand(1), OperandStr))3366 return nullptr;3367 // printf("%s", "") --> NOP3368 if (OperandStr.empty())3369 return (Value *)CI;3370 // printf("%s", "a") --> putchar('a')3371 if (OperandStr.size() == 1) {3372 // Convert the character to unsigned char before passing it to putchar3373 // to avoid host-specific sign extension in the IR. Putchar converts3374 // it to unsigned char regardless.3375 Value *IntChar = ConstantInt::get(IntTy, (unsigned char)OperandStr[0]);3376 return copyFlags(*CI, emitPutChar(IntChar, B, TLI));3377 }3378 // printf("%s", str"\n") --> puts(str)3379 if (OperandStr.back() == '\n') {3380 OperandStr = OperandStr.drop_back();3381 Value *GV = B.CreateGlobalString(OperandStr, "str");3382 return copyFlags(*CI, emitPutS(GV, B, TLI));3383 }3384 return nullptr;3385 }3386 3387 // printf("foo\n") --> puts("foo")3388 if (FormatStr.back() == '\n' &&3389 !FormatStr.contains('%')) { // No format characters.3390 // Create a string literal with no \n on it. We expect the constant merge3391 // pass to be run after this pass, to merge duplicate strings.3392 FormatStr = FormatStr.drop_back();3393 Value *GV = B.CreateGlobalString(FormatStr, "str");3394 return copyFlags(*CI, emitPutS(GV, B, TLI));3395 }3396 3397 // Optimize specific format strings.3398 // printf("%c", chr) --> putchar(chr)3399 if (FormatStr == "%c" && CI->arg_size() > 1 &&3400 CI->getArgOperand(1)->getType()->isIntegerTy()) {3401 // Convert the argument to the type expected by putchar, i.e., int, which3402 // need not be 32 bits wide but which is the same as printf's return type.3403 Value *IntChar = B.CreateIntCast(CI->getArgOperand(1), IntTy, false);3404 return copyFlags(*CI, emitPutChar(IntChar, B, TLI));3405 }3406 3407 // printf("%s\n", str) --> puts(str)3408 if (FormatStr == "%s\n" && CI->arg_size() > 1 &&3409 CI->getArgOperand(1)->getType()->isPointerTy())3410 return copyFlags(*CI, emitPutS(CI->getArgOperand(1), B, TLI));3411 return nullptr;3412}3413 3414Value *LibCallSimplifier::optimizePrintF(CallInst *CI, IRBuilderBase &B) {3415 3416 Module *M = CI->getModule();3417 Function *Callee = CI->getCalledFunction();3418 FunctionType *FT = Callee->getFunctionType();3419 if (Value *V = optimizePrintFString(CI, B)) {3420 return V;3421 }3422 3423 annotateNonNullNoUndefBasedOnAccess(CI, 0);3424 3425 // printf(format, ...) -> iprintf(format, ...) if no floating point3426 // arguments.3427 if (isLibFuncEmittable(M, TLI, LibFunc_iprintf) &&3428 !callHasFloatingPointArgument(CI)) {3429 FunctionCallee IPrintFFn = getOrInsertLibFunc(M, *TLI, LibFunc_iprintf, FT,3430 Callee->getAttributes());3431 CallInst *New = cast<CallInst>(CI->clone());3432 New->setCalledFunction(IPrintFFn);3433 B.Insert(New);3434 return New;3435 }3436 3437 // printf(format, ...) -> __small_printf(format, ...) if no 128-bit floating point3438 // arguments.3439 if (isLibFuncEmittable(M, TLI, LibFunc_small_printf) &&3440 !callHasFP128Argument(CI)) {3441 auto SmallPrintFFn = getOrInsertLibFunc(M, *TLI, LibFunc_small_printf, FT,3442 Callee->getAttributes());3443 CallInst *New = cast<CallInst>(CI->clone());3444 New->setCalledFunction(SmallPrintFFn);3445 B.Insert(New);3446 return New;3447 }3448 3449 return nullptr;3450}3451 3452Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI,3453 IRBuilderBase &B) {3454 // Check for a fixed format string.3455 StringRef FormatStr;3456 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))3457 return nullptr;3458 3459 // If we just have a format string (nothing else crazy) transform it.3460 Value *Dest = CI->getArgOperand(0);3461 if (CI->arg_size() == 2) {3462 // Make sure there's no % in the constant array. We could try to handle3463 // %% -> % in the future if we cared.3464 if (FormatStr.contains('%'))3465 return nullptr; // we found a format specifier, bail out.3466 3467 // sprintf(str, fmt) -> llvm.memcpy(align 1 str, align 1 fmt, strlen(fmt)+1)3468 B.CreateMemCpy(Dest, Align(1), CI->getArgOperand(1), Align(1),3469 // Copy the null byte.3470 TLI->getAsSizeT(FormatStr.size() + 1, *CI->getModule()));3471 return ConstantInt::get(CI->getType(), FormatStr.size());3472 }3473 3474 // The remaining optimizations require the format string to be "%s" or "%c"3475 // and have an extra operand.3476 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3)3477 return nullptr;3478 3479 // Decode the second character of the format string.3480 if (FormatStr[1] == 'c') {3481 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 03482 if (!CI->getArgOperand(2)->getType()->isIntegerTy())3483 return nullptr;3484 Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");3485 Value *Ptr = Dest;3486 B.CreateStore(V, Ptr);3487 Ptr = B.CreateInBoundsGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");3488 B.CreateStore(B.getInt8(0), Ptr);3489 3490 return ConstantInt::get(CI->getType(), 1);3491 }3492 3493 if (FormatStr[1] == 's') {3494 // sprintf(dest, "%s", str) -> llvm.memcpy(align 1 dest, align 1 str,3495 // strlen(str)+1)3496 if (!CI->getArgOperand(2)->getType()->isPointerTy())3497 return nullptr;3498 3499 if (CI->use_empty())3500 // sprintf(dest, "%s", str) -> strcpy(dest, str)3501 return copyFlags(*CI, emitStrCpy(Dest, CI->getArgOperand(2), B, TLI));3502 3503 uint64_t SrcLen = GetStringLength(CI->getArgOperand(2));3504 if (SrcLen) {3505 B.CreateMemCpy(Dest, Align(1), CI->getArgOperand(2), Align(1),3506 TLI->getAsSizeT(SrcLen, *CI->getModule()));3507 // Returns total number of characters written without null-character.3508 return ConstantInt::get(CI->getType(), SrcLen - 1);3509 } else if (Value *V = emitStpCpy(Dest, CI->getArgOperand(2), B, TLI)) {3510 // sprintf(dest, "%s", str) -> stpcpy(dest, str) - dest3511 Value *PtrDiff = B.CreatePtrDiff(B.getInt8Ty(), V, Dest);3512 return B.CreateIntCast(PtrDiff, CI->getType(), false);3513 }3514 3515 if (llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI,3516 PGSOQueryType::IRPass))3517 return nullptr;3518 3519 Value *Len = emitStrLen(CI->getArgOperand(2), B, DL, TLI);3520 if (!Len)3521 return nullptr;3522 Value *IncLen =3523 B.CreateAdd(Len, ConstantInt::get(Len->getType(), 1), "leninc");3524 B.CreateMemCpy(Dest, Align(1), CI->getArgOperand(2), Align(1), IncLen);3525 3526 // The sprintf result is the unincremented number of bytes in the string.3527 return B.CreateIntCast(Len, CI->getType(), false);3528 }3529 return nullptr;3530}3531 3532Value *LibCallSimplifier::optimizeSPrintF(CallInst *CI, IRBuilderBase &B) {3533 Module *M = CI->getModule();3534 Function *Callee = CI->getCalledFunction();3535 FunctionType *FT = Callee->getFunctionType();3536 if (Value *V = optimizeSPrintFString(CI, B)) {3537 return V;3538 }3539 3540 annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});3541 3542 // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating3543 // point arguments.3544 if (isLibFuncEmittable(M, TLI, LibFunc_siprintf) &&3545 !callHasFloatingPointArgument(CI)) {3546 FunctionCallee SIPrintFFn = getOrInsertLibFunc(M, *TLI, LibFunc_siprintf,3547 FT, Callee->getAttributes());3548 CallInst *New = cast<CallInst>(CI->clone());3549 New->setCalledFunction(SIPrintFFn);3550 B.Insert(New);3551 return New;3552 }3553 3554 // sprintf(str, format, ...) -> __small_sprintf(str, format, ...) if no 128-bit3555 // floating point arguments.3556 if (isLibFuncEmittable(M, TLI, LibFunc_small_sprintf) &&3557 !callHasFP128Argument(CI)) {3558 auto SmallSPrintFFn = getOrInsertLibFunc(M, *TLI, LibFunc_small_sprintf, FT,3559 Callee->getAttributes());3560 CallInst *New = cast<CallInst>(CI->clone());3561 New->setCalledFunction(SmallSPrintFFn);3562 B.Insert(New);3563 return New;3564 }3565 3566 return nullptr;3567}3568 3569// Transform an snprintf call CI with the bound N to format the string Str3570// either to a call to memcpy, or to single character a store, or to nothing,3571// and fold the result to a constant. A nonnull StrArg refers to the string3572// argument being formatted. Otherwise the call is one with N < 2 and3573// the "%c" directive to format a single character.3574Value *LibCallSimplifier::emitSnPrintfMemCpy(CallInst *CI, Value *StrArg,3575 StringRef Str, uint64_t N,3576 IRBuilderBase &B) {3577 assert(StrArg || (N < 2 && Str.size() == 1));3578 3579 unsigned IntBits = TLI->getIntSize();3580 uint64_t IntMax = maxIntN(IntBits);3581 if (Str.size() > IntMax)3582 // Bail if the string is longer than INT_MAX. POSIX requires3583 // implementations to set errno to EOVERFLOW in this case, in3584 // addition to when N is larger than that (checked by the caller).3585 return nullptr;3586 3587 Value *StrLen = ConstantInt::get(CI->getType(), Str.size());3588 if (N == 0)3589 return StrLen;3590 3591 // Set to the number of bytes to copy fron StrArg which is also3592 // the offset of the terinating nul.3593 uint64_t NCopy;3594 if (N > Str.size())3595 // Copy the full string, including the terminating nul (which must3596 // be present regardless of the bound).3597 NCopy = Str.size() + 1;3598 else3599 NCopy = N - 1;3600 3601 Value *DstArg = CI->getArgOperand(0);3602 if (NCopy && StrArg)3603 // Transform the call to lvm.memcpy(dst, fmt, N).3604 copyFlags(*CI, B.CreateMemCpy(DstArg, Align(1), StrArg, Align(1),3605 TLI->getAsSizeT(NCopy, *CI->getModule())));3606 3607 if (N > Str.size())3608 // Return early when the whole format string, including the final nul,3609 // has been copied.3610 return StrLen;3611 3612 // Otherwise, when truncating the string append a terminating nul.3613 Type *Int8Ty = B.getInt8Ty();3614 Value *NulOff = B.getIntN(IntBits, NCopy);3615 Value *DstEnd = B.CreateInBoundsGEP(Int8Ty, DstArg, NulOff, "endptr");3616 B.CreateStore(ConstantInt::get(Int8Ty, 0), DstEnd);3617 return StrLen;3618}3619 3620Value *LibCallSimplifier::optimizeSnPrintFString(CallInst *CI,3621 IRBuilderBase &B) {3622 // Check for size3623 ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1));3624 if (!Size)3625 return nullptr;3626 3627 uint64_t N = Size->getZExtValue();3628 uint64_t IntMax = maxIntN(TLI->getIntSize());3629 if (N > IntMax)3630 // Bail if the bound exceeds INT_MAX. POSIX requires implementations3631 // to set errno to EOVERFLOW in this case.3632 return nullptr;3633 3634 Value *DstArg = CI->getArgOperand(0);3635 Value *FmtArg = CI->getArgOperand(2);3636 3637 // Check for a fixed format string.3638 StringRef FormatStr;3639 if (!getConstantStringInfo(FmtArg, FormatStr))3640 return nullptr;3641 3642 // If we just have a format string (nothing else crazy) transform it.3643 if (CI->arg_size() == 3) {3644 if (FormatStr.contains('%'))3645 // Bail if the format string contains a directive and there are3646 // no arguments. We could handle "%%" in the future.3647 return nullptr;3648 3649 return emitSnPrintfMemCpy(CI, FmtArg, FormatStr, N, B);3650 }3651 3652 // The remaining optimizations require the format string to be "%s" or "%c"3653 // and have an extra operand.3654 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() != 4)3655 return nullptr;3656 3657 // Decode the second character of the format string.3658 if (FormatStr[1] == 'c') {3659 if (N <= 1) {3660 // Use an arbitary string of length 1 to transform the call into3661 // either a nul store (N == 1) or a no-op (N == 0) and fold it3662 // to one.3663 StringRef CharStr("*");3664 return emitSnPrintfMemCpy(CI, nullptr, CharStr, N, B);3665 }3666 3667 // snprintf(dst, size, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 03668 if (!CI->getArgOperand(3)->getType()->isIntegerTy())3669 return nullptr;3670 Value *V = B.CreateTrunc(CI->getArgOperand(3), B.getInt8Ty(), "char");3671 Value *Ptr = DstArg;3672 B.CreateStore(V, Ptr);3673 Ptr = B.CreateInBoundsGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");3674 B.CreateStore(B.getInt8(0), Ptr);3675 return ConstantInt::get(CI->getType(), 1);3676 }3677 3678 if (FormatStr[1] != 's')3679 return nullptr;3680 3681 Value *StrArg = CI->getArgOperand(3);3682 // snprintf(dest, size, "%s", str) to llvm.memcpy(dest, str, len+1, 1)3683 StringRef Str;3684 if (!getConstantStringInfo(StrArg, Str))3685 return nullptr;3686 3687 return emitSnPrintfMemCpy(CI, StrArg, Str, N, B);3688}3689 3690Value *LibCallSimplifier::optimizeSnPrintF(CallInst *CI, IRBuilderBase &B) {3691 if (Value *V = optimizeSnPrintFString(CI, B)) {3692 return V;3693 }3694 3695 if (isKnownNonZero(CI->getOperand(1), DL))3696 annotateNonNullNoUndefBasedOnAccess(CI, 0);3697 return nullptr;3698}3699 3700Value *LibCallSimplifier::optimizeFPrintFString(CallInst *CI,3701 IRBuilderBase &B) {3702 optimizeErrorReporting(CI, B, 0);3703 3704 // All the optimizations depend on the format string.3705 StringRef FormatStr;3706 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))3707 return nullptr;3708 3709 // Do not do any of the following transformations if the fprintf return3710 // value is used, in general the fprintf return value is not compatible3711 // with fwrite(), fputc() or fputs().3712 if (!CI->use_empty())3713 return nullptr;3714 3715 // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)3716 if (CI->arg_size() == 2) {3717 // Could handle %% -> % if we cared.3718 if (FormatStr.contains('%'))3719 return nullptr; // We found a format specifier.3720 3721 return copyFlags(3722 *CI, emitFWrite(CI->getArgOperand(1),3723 TLI->getAsSizeT(FormatStr.size(), *CI->getModule()),3724 CI->getArgOperand(0), B, DL, TLI));3725 }3726 3727 // The remaining optimizations require the format string to be "%s" or "%c"3728 // and have an extra operand.3729 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3)3730 return nullptr;3731 3732 // Decode the second character of the format string.3733 if (FormatStr[1] == 'c') {3734 // fprintf(F, "%c", chr) --> fputc((int)chr, F)3735 if (!CI->getArgOperand(2)->getType()->isIntegerTy())3736 return nullptr;3737 Type *IntTy = B.getIntNTy(TLI->getIntSize());3738 Value *V = B.CreateIntCast(CI->getArgOperand(2), IntTy, /*isSigned*/ true,3739 "chari");3740 return copyFlags(*CI, emitFPutC(V, CI->getArgOperand(0), B, TLI));3741 }3742 3743 if (FormatStr[1] == 's') {3744 // fprintf(F, "%s", str) --> fputs(str, F)3745 if (!CI->getArgOperand(2)->getType()->isPointerTy())3746 return nullptr;3747 return copyFlags(3748 *CI, emitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TLI));3749 }3750 return nullptr;3751}3752 3753Value *LibCallSimplifier::optimizeFPrintF(CallInst *CI, IRBuilderBase &B) {3754 Module *M = CI->getModule();3755 Function *Callee = CI->getCalledFunction();3756 FunctionType *FT = Callee->getFunctionType();3757 if (Value *V = optimizeFPrintFString(CI, B)) {3758 return V;3759 }3760 3761 // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no3762 // floating point arguments.3763 if (isLibFuncEmittable(M, TLI, LibFunc_fiprintf) &&3764 !callHasFloatingPointArgument(CI)) {3765 FunctionCallee FIPrintFFn = getOrInsertLibFunc(M, *TLI, LibFunc_fiprintf,3766 FT, Callee->getAttributes());3767 CallInst *New = cast<CallInst>(CI->clone());3768 New->setCalledFunction(FIPrintFFn);3769 B.Insert(New);3770 return New;3771 }3772 3773 // fprintf(stream, format, ...) -> __small_fprintf(stream, format, ...) if no3774 // 128-bit floating point arguments.3775 if (isLibFuncEmittable(M, TLI, LibFunc_small_fprintf) &&3776 !callHasFP128Argument(CI)) {3777 auto SmallFPrintFFn =3778 getOrInsertLibFunc(M, *TLI, LibFunc_small_fprintf, FT,3779 Callee->getAttributes());3780 CallInst *New = cast<CallInst>(CI->clone());3781 New->setCalledFunction(SmallFPrintFFn);3782 B.Insert(New);3783 return New;3784 }3785 3786 return nullptr;3787}3788 3789Value *LibCallSimplifier::optimizeFWrite(CallInst *CI, IRBuilderBase &B) {3790 optimizeErrorReporting(CI, B, 3);3791 3792 // Get the element size and count.3793 ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));3794 ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));3795 if (SizeC && CountC) {3796 uint64_t Bytes = SizeC->getZExtValue() * CountC->getZExtValue();3797 3798 // If this is writing zero records, remove the call (it's a noop).3799 if (Bytes == 0)3800 return ConstantInt::get(CI->getType(), 0);3801 3802 // If this is writing one byte, turn it into fputc.3803 // This optimisation is only valid, if the return value is unused.3804 if (Bytes == 1 && CI->use_empty()) { // fwrite(S,1,1,F) -> fputc(S[0],F)3805 Value *Char = B.CreateLoad(B.getInt8Ty(), CI->getArgOperand(0), "char");3806 Type *IntTy = B.getIntNTy(TLI->getIntSize());3807 Value *Cast = B.CreateIntCast(Char, IntTy, /*isSigned*/ true, "chari");3808 Value *NewCI = emitFPutC(Cast, CI->getArgOperand(3), B, TLI);3809 return NewCI ? ConstantInt::get(CI->getType(), 1) : nullptr;3810 }3811 }3812 3813 return nullptr;3814}3815 3816Value *LibCallSimplifier::optimizeFPuts(CallInst *CI, IRBuilderBase &B) {3817 optimizeErrorReporting(CI, B, 1);3818 3819 // Don't rewrite fputs to fwrite when optimising for size because fwrite3820 // requires more arguments and thus extra MOVs are required.3821 if (llvm::shouldOptimizeForSize(CI->getParent(), PSI, BFI,3822 PGSOQueryType::IRPass))3823 return nullptr;3824 3825 // We can't optimize if return value is used.3826 if (!CI->use_empty())3827 return nullptr;3828 3829 // fputs(s,F) --> fwrite(s,strlen(s),1,F)3830 uint64_t Len = GetStringLength(CI->getArgOperand(0));3831 if (!Len)3832 return nullptr;3833 3834 // Known to have no uses (see above).3835 unsigned SizeTBits = TLI->getSizeTSize(*CI->getModule());3836 Type *SizeTTy = IntegerType::get(CI->getContext(), SizeTBits);3837 return copyFlags(3838 *CI,3839 emitFWrite(CI->getArgOperand(0),3840 ConstantInt::get(SizeTTy, Len - 1),3841 CI->getArgOperand(1), B, DL, TLI));3842}3843 3844Value *LibCallSimplifier::optimizePuts(CallInst *CI, IRBuilderBase &B) {3845 annotateNonNullNoUndefBasedOnAccess(CI, 0);3846 if (!CI->use_empty())3847 return nullptr;3848 3849 // Check for a constant string.3850 // puts("") -> putchar('\n')3851 StringRef Str;3852 if (getConstantStringInfo(CI->getArgOperand(0), Str) && Str.empty()) {3853 // putchar takes an argument of the same type as puts returns, i.e.,3854 // int, which need not be 32 bits wide.3855 Type *IntTy = CI->getType();3856 return copyFlags(*CI, emitPutChar(ConstantInt::get(IntTy, '\n'), B, TLI));3857 }3858 3859 return nullptr;3860}3861 3862Value *LibCallSimplifier::optimizeExit(CallInst *CI) {3863 3864 // Mark 'exit' as cold if its not exit(0) (success).3865 const APInt *C;3866 if (!CI->hasFnAttr(Attribute::Cold) &&3867 match(CI->getArgOperand(0), m_APInt(C)) && !C->isZero()) {3868 CI->addFnAttr(Attribute::Cold);3869 }3870 return nullptr;3871}3872 3873Value *LibCallSimplifier::optimizeBCopy(CallInst *CI, IRBuilderBase &B) {3874 // bcopy(src, dst, n) -> llvm.memmove(dst, src, n)3875 return copyFlags(*CI, B.CreateMemMove(CI->getArgOperand(1), Align(1),3876 CI->getArgOperand(0), Align(1),3877 CI->getArgOperand(2)));3878}3879 3880bool LibCallSimplifier::hasFloatVersion(const Module *M, StringRef FuncName) {3881 SmallString<20> FloatFuncName = FuncName;3882 FloatFuncName += 'f';3883 return isLibFuncEmittable(M, TLI, FloatFuncName);3884}3885 3886Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI,3887 IRBuilderBase &Builder) {3888 Module *M = CI->getModule();3889 LibFunc Func;3890 Function *Callee = CI->getCalledFunction();3891 3892 // Check for string/memory library functions.3893 if (TLI->getLibFunc(*Callee, Func) && isLibFuncEmittable(M, TLI, Func)) {3894 // Make sure we never change the calling convention.3895 assert(3896 (ignoreCallingConv(Func) ||3897 TargetLibraryInfoImpl::isCallingConvCCompatible(CI)) &&3898 "Optimizing string/memory libcall would change the calling convention");3899 switch (Func) {3900 case LibFunc_strcat:3901 return optimizeStrCat(CI, Builder);3902 case LibFunc_strncat:3903 return optimizeStrNCat(CI, Builder);3904 case LibFunc_strchr:3905 return optimizeStrChr(CI, Builder);3906 case LibFunc_strrchr:3907 return optimizeStrRChr(CI, Builder);3908 case LibFunc_strcmp:3909 return optimizeStrCmp(CI, Builder);3910 case LibFunc_strncmp:3911 return optimizeStrNCmp(CI, Builder);3912 case LibFunc_strcpy:3913 return optimizeStrCpy(CI, Builder);3914 case LibFunc_stpcpy:3915 return optimizeStpCpy(CI, Builder);3916 case LibFunc_strlcpy:3917 return optimizeStrLCpy(CI, Builder);3918 case LibFunc_stpncpy:3919 return optimizeStringNCpy(CI, /*RetEnd=*/true, Builder);3920 case LibFunc_strncpy:3921 return optimizeStringNCpy(CI, /*RetEnd=*/false, Builder);3922 case LibFunc_strlen:3923 return optimizeStrLen(CI, Builder);3924 case LibFunc_strnlen:3925 return optimizeStrNLen(CI, Builder);3926 case LibFunc_strpbrk:3927 return optimizeStrPBrk(CI, Builder);3928 case LibFunc_strndup:3929 return optimizeStrNDup(CI, Builder);3930 case LibFunc_strtol:3931 case LibFunc_strtod:3932 case LibFunc_strtof:3933 case LibFunc_strtoul:3934 case LibFunc_strtoll:3935 case LibFunc_strtold:3936 case LibFunc_strtoull:3937 return optimizeStrTo(CI, Builder);3938 case LibFunc_strspn:3939 return optimizeStrSpn(CI, Builder);3940 case LibFunc_strcspn:3941 return optimizeStrCSpn(CI, Builder);3942 case LibFunc_strstr:3943 return optimizeStrStr(CI, Builder);3944 case LibFunc_memchr:3945 return optimizeMemChr(CI, Builder);3946 case LibFunc_memrchr:3947 return optimizeMemRChr(CI, Builder);3948 case LibFunc_bcmp:3949 return optimizeBCmp(CI, Builder);3950 case LibFunc_memcmp:3951 return optimizeMemCmp(CI, Builder);3952 case LibFunc_memcpy:3953 return optimizeMemCpy(CI, Builder);3954 case LibFunc_memccpy:3955 return optimizeMemCCpy(CI, Builder);3956 case LibFunc_mempcpy:3957 return optimizeMemPCpy(CI, Builder);3958 case LibFunc_memmove:3959 return optimizeMemMove(CI, Builder);3960 case LibFunc_memset:3961 return optimizeMemSet(CI, Builder);3962 case LibFunc_realloc:3963 return optimizeRealloc(CI, Builder);3964 case LibFunc_wcslen:3965 return optimizeWcslen(CI, Builder);3966 case LibFunc_bcopy:3967 return optimizeBCopy(CI, Builder);3968 case LibFunc_Znwm:3969 case LibFunc_ZnwmRKSt9nothrow_t:3970 case LibFunc_ZnwmSt11align_val_t:3971 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t:3972 case LibFunc_Znam:3973 case LibFunc_ZnamRKSt9nothrow_t:3974 case LibFunc_ZnamSt11align_val_t:3975 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t:3976 case LibFunc_Znwm12__hot_cold_t:3977 case LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t:3978 case LibFunc_ZnwmSt11align_val_t12__hot_cold_t:3979 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t:3980 case LibFunc_Znam12__hot_cold_t:3981 case LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t:3982 case LibFunc_ZnamSt11align_val_t12__hot_cold_t:3983 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t:3984 case LibFunc_size_returning_new:3985 case LibFunc_size_returning_new_hot_cold:3986 case LibFunc_size_returning_new_aligned:3987 case LibFunc_size_returning_new_aligned_hot_cold:3988 return optimizeNew(CI, Builder, Func);3989 default:3990 break;3991 }3992 }3993 return nullptr;3994}3995 3996/// Constant folding nan/nanf/nanl.3997static Value *optimizeNaN(CallInst *CI) {3998 StringRef CharSeq;3999 if (!getConstantStringInfo(CI->getArgOperand(0), CharSeq))4000 return nullptr;4001 4002 APInt Fill;4003 // Treat empty strings as if they were zero.4004 if (CharSeq.empty())4005 Fill = APInt(32, 0);4006 else if (CharSeq.getAsInteger(0, Fill))4007 return nullptr;4008 4009 return ConstantFP::getQNaN(CI->getType(), /*Negative=*/false, &Fill);4010}4011 4012Value *LibCallSimplifier::optimizeFloatingPointLibCall(CallInst *CI,4013 LibFunc Func,4014 IRBuilderBase &Builder) {4015 const Module *M = CI->getModule();4016 4017 // Don't optimize calls that require strict floating point semantics.4018 if (CI->isStrictFP())4019 return nullptr;4020 4021 if (Value *V = optimizeSymmetric(CI, Func, Builder))4022 return V;4023 4024 switch (Func) {4025 case LibFunc_sinpif:4026 case LibFunc_sinpi:4027 return optimizeSinCosPi(CI, /*IsSin*/true, Builder);4028 case LibFunc_cospif:4029 case LibFunc_cospi:4030 return optimizeSinCosPi(CI, /*IsSin*/false, Builder);4031 case LibFunc_powf:4032 case LibFunc_pow:4033 case LibFunc_powl:4034 return optimizePow(CI, Builder);4035 case LibFunc_exp2l:4036 case LibFunc_exp2:4037 case LibFunc_exp2f:4038 return optimizeExp2(CI, Builder);4039 case LibFunc_fabsf:4040 case LibFunc_fabs:4041 case LibFunc_fabsl:4042 return replaceUnaryCall(CI, Builder, Intrinsic::fabs);4043 case LibFunc_sqrtf:4044 case LibFunc_sqrt:4045 case LibFunc_sqrtl:4046 return optimizeSqrt(CI, Builder);4047 case LibFunc_fmod:4048 case LibFunc_fmodf:4049 case LibFunc_fmodl:4050 return optimizeFMod(CI, Builder);4051 case LibFunc_logf:4052 case LibFunc_log:4053 case LibFunc_logl:4054 case LibFunc_log10f:4055 case LibFunc_log10:4056 case LibFunc_log10l:4057 case LibFunc_log1pf:4058 case LibFunc_log1p:4059 case LibFunc_log1pl:4060 case LibFunc_log2f:4061 case LibFunc_log2:4062 case LibFunc_log2l:4063 case LibFunc_logbf:4064 case LibFunc_logb:4065 case LibFunc_logbl:4066 return optimizeLog(CI, Builder);4067 case LibFunc_tan:4068 case LibFunc_tanf:4069 case LibFunc_tanl:4070 case LibFunc_sinh:4071 case LibFunc_sinhf:4072 case LibFunc_sinhl:4073 case LibFunc_asinh:4074 case LibFunc_asinhf:4075 case LibFunc_asinhl:4076 case LibFunc_cosh:4077 case LibFunc_coshf:4078 case LibFunc_coshl:4079 case LibFunc_atanh:4080 case LibFunc_atanhf:4081 case LibFunc_atanhl:4082 return optimizeTrigInversionPairs(CI, Builder);4083 case LibFunc_ceil:4084 return replaceUnaryCall(CI, Builder, Intrinsic::ceil);4085 case LibFunc_floor:4086 return replaceUnaryCall(CI, Builder, Intrinsic::floor);4087 case LibFunc_round:4088 return replaceUnaryCall(CI, Builder, Intrinsic::round);4089 case LibFunc_roundeven:4090 return replaceUnaryCall(CI, Builder, Intrinsic::roundeven);4091 case LibFunc_nearbyint:4092 return replaceUnaryCall(CI, Builder, Intrinsic::nearbyint);4093 case LibFunc_rint:4094 return replaceUnaryCall(CI, Builder, Intrinsic::rint);4095 case LibFunc_trunc:4096 return replaceUnaryCall(CI, Builder, Intrinsic::trunc);4097 case LibFunc_acos:4098 case LibFunc_acosh:4099 case LibFunc_asin:4100 case LibFunc_atan:4101 case LibFunc_cbrt:4102 case LibFunc_exp:4103 case LibFunc_exp10:4104 case LibFunc_expm1:4105 case LibFunc_cos:4106 case LibFunc_sin:4107 case LibFunc_tanh:4108 if (UnsafeFPShrink && hasFloatVersion(M, CI->getCalledFunction()->getName()))4109 return optimizeUnaryDoubleFP(CI, Builder, TLI, true);4110 return nullptr;4111 case LibFunc_copysign:4112 if (hasFloatVersion(M, CI->getCalledFunction()->getName()))4113 return optimizeBinaryDoubleFP(CI, Builder, TLI);4114 return nullptr;4115 case LibFunc_fdim:4116 case LibFunc_fdimf:4117 case LibFunc_fdiml:4118 return optimizeFdim(CI, Builder);4119 case LibFunc_fminf:4120 case LibFunc_fmin:4121 case LibFunc_fminl:4122 case LibFunc_fmaxf:4123 case LibFunc_fmax:4124 case LibFunc_fmaxl:4125 return optimizeFMinFMax(CI, Builder);4126 case LibFunc_cabs:4127 case LibFunc_cabsf:4128 case LibFunc_cabsl:4129 return optimizeCAbs(CI, Builder);4130 case LibFunc_remquo:4131 case LibFunc_remquof:4132 case LibFunc_remquol:4133 return optimizeRemquo(CI, Builder);4134 case LibFunc_nan:4135 case LibFunc_nanf:4136 case LibFunc_nanl:4137 return optimizeNaN(CI);4138 default:4139 return nullptr;4140 }4141}4142 4143Value *LibCallSimplifier::optimizeCall(CallInst *CI, IRBuilderBase &Builder) {4144 Module *M = CI->getModule();4145 assert(!CI->isMustTailCall() && "These transforms aren't musttail safe.");4146 4147 // TODO: Split out the code below that operates on FP calls so that4148 // we can all non-FP calls with the StrictFP attribute to be4149 // optimized.4150 if (CI->isNoBuiltin()) {4151 // Optionally update operator new calls.4152 return maybeOptimizeNoBuiltinOperatorNew(CI, Builder);4153 }4154 4155 LibFunc Func;4156 Function *Callee = CI->getCalledFunction();4157 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI);4158 4159 SmallVector<OperandBundleDef, 2> OpBundles;4160 CI->getOperandBundlesAsDefs(OpBundles);4161 4162 IRBuilderBase::OperandBundlesGuard Guard(Builder);4163 Builder.setDefaultOperandBundles(OpBundles);4164 4165 // Command-line parameter overrides instruction attribute.4166 // This can't be moved to optimizeFloatingPointLibCall() because it may be4167 // used by the intrinsic optimizations.4168 if (EnableUnsafeFPShrink.getNumOccurrences() > 0)4169 UnsafeFPShrink = EnableUnsafeFPShrink;4170 else if (isa<FPMathOperator>(CI) && CI->isFast())4171 UnsafeFPShrink = true;4172 4173 // First, check for intrinsics.4174 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {4175 if (!IsCallingConvC)4176 return nullptr;4177 // The FP intrinsics have corresponding constrained versions so we don't4178 // need to check for the StrictFP attribute here.4179 switch (II->getIntrinsicID()) {4180 case Intrinsic::pow:4181 return optimizePow(CI, Builder);4182 case Intrinsic::exp2:4183 return optimizeExp2(CI, Builder);4184 case Intrinsic::log:4185 case Intrinsic::log2:4186 case Intrinsic::log10:4187 return optimizeLog(CI, Builder);4188 case Intrinsic::sqrt:4189 return optimizeSqrt(CI, Builder);4190 case Intrinsic::memset:4191 return optimizeMemSet(CI, Builder);4192 case Intrinsic::memcpy:4193 return optimizeMemCpy(CI, Builder);4194 case Intrinsic::memmove:4195 return optimizeMemMove(CI, Builder);4196 case Intrinsic::sin:4197 case Intrinsic::cos:4198 if (UnsafeFPShrink)4199 return optimizeUnaryDoubleFP(CI, Builder, TLI, /*isPrecise=*/true);4200 return nullptr;4201 default:4202 return nullptr;4203 }4204 }4205 4206 // Also try to simplify calls to fortified library functions.4207 if (Value *SimplifiedFortifiedCI =4208 FortifiedSimplifier.optimizeCall(CI, Builder))4209 return SimplifiedFortifiedCI;4210 4211 // Then check for known library functions.4212 if (TLI->getLibFunc(*Callee, Func) && isLibFuncEmittable(M, TLI, Func)) {4213 // We never change the calling convention.4214 if (!ignoreCallingConv(Func) && !IsCallingConvC)4215 return nullptr;4216 if (Value *V = optimizeStringMemoryLibCall(CI, Builder))4217 return V;4218 if (Value *V = optimizeFloatingPointLibCall(CI, Func, Builder))4219 return V;4220 switch (Func) {4221 case LibFunc_ffs:4222 case LibFunc_ffsl:4223 case LibFunc_ffsll:4224 return optimizeFFS(CI, Builder);4225 case LibFunc_fls:4226 case LibFunc_flsl:4227 case LibFunc_flsll:4228 return optimizeFls(CI, Builder);4229 case LibFunc_abs:4230 case LibFunc_labs:4231 case LibFunc_llabs:4232 return optimizeAbs(CI, Builder);4233 case LibFunc_isdigit:4234 return optimizeIsDigit(CI, Builder);4235 case LibFunc_isascii:4236 return optimizeIsAscii(CI, Builder);4237 case LibFunc_toascii:4238 return optimizeToAscii(CI, Builder);4239 case LibFunc_atoi:4240 case LibFunc_atol:4241 case LibFunc_atoll:4242 return optimizeAtoi(CI, Builder);4243 case LibFunc_strtol:4244 case LibFunc_strtoll:4245 return optimizeStrToInt(CI, Builder, /*AsSigned=*/true);4246 case LibFunc_strtoul:4247 case LibFunc_strtoull:4248 return optimizeStrToInt(CI, Builder, /*AsSigned=*/false);4249 case LibFunc_printf:4250 return optimizePrintF(CI, Builder);4251 case LibFunc_sprintf:4252 return optimizeSPrintF(CI, Builder);4253 case LibFunc_snprintf:4254 return optimizeSnPrintF(CI, Builder);4255 case LibFunc_fprintf:4256 return optimizeFPrintF(CI, Builder);4257 case LibFunc_fwrite:4258 return optimizeFWrite(CI, Builder);4259 case LibFunc_fputs:4260 return optimizeFPuts(CI, Builder);4261 case LibFunc_puts:4262 return optimizePuts(CI, Builder);4263 case LibFunc_perror:4264 return optimizeErrorReporting(CI, Builder);4265 case LibFunc_vfprintf:4266 case LibFunc_fiprintf:4267 return optimizeErrorReporting(CI, Builder, 0);4268 case LibFunc_exit:4269 case LibFunc_Exit:4270 return optimizeExit(CI);4271 default:4272 return nullptr;4273 }4274 }4275 return nullptr;4276}4277 4278LibCallSimplifier::LibCallSimplifier(4279 const DataLayout &DL, const TargetLibraryInfo *TLI, DominatorTree *DT,4280 DomConditionCache *DC, AssumptionCache *AC, OptimizationRemarkEmitter &ORE,4281 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,4282 function_ref<void(Instruction *, Value *)> Replacer,4283 function_ref<void(Instruction *)> Eraser)4284 : FortifiedSimplifier(TLI), DL(DL), TLI(TLI), DT(DT), DC(DC), AC(AC),4285 ORE(ORE), BFI(BFI), PSI(PSI), Replacer(Replacer), Eraser(Eraser) {}4286 4287void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) {4288 // Indirect through the replacer used in this instance.4289 Replacer(I, With);4290}4291 4292void LibCallSimplifier::eraseFromParent(Instruction *I) {4293 Eraser(I);4294}4295 4296// TODO:4297// Additional cases that we need to add to this file:4298//4299// cbrt:4300// * cbrt(expN(X)) -> expN(x/3)4301// * cbrt(sqrt(x)) -> pow(x,1/6)4302// * cbrt(cbrt(x)) -> pow(x,1/9)4303//4304// exp, expf, expl:4305// * exp(log(x)) -> x4306//4307// log, logf, logl:4308// * log(exp(x)) -> x4309// * log(exp(y)) -> y*log(e)4310// * log(exp10(y)) -> y*log(10)4311// * log(sqrt(x)) -> 0.5*log(x)4312//4313// pow, powf, powl:4314// * pow(sqrt(x),y) -> pow(x,y*0.5)4315// * pow(pow(x,y),z)-> pow(x,y*z)4316//4317// signbit:4318// * signbit(cnst) -> cnst'4319// * signbit(nncst) -> 0 (if pstv is a non-negative constant)4320//4321// sqrt, sqrtf, sqrtl:4322// * sqrt(expN(x)) -> expN(x*0.5)4323// * sqrt(Nroot(x)) -> pow(x,1/(2*N))4324// * sqrt(pow(x,y)) -> pow(|x|,y*0.5)4325//4326 4327//===----------------------------------------------------------------------===//4328// Fortified Library Call Optimizations4329//===----------------------------------------------------------------------===//4330 4331bool FortifiedLibCallSimplifier::isFortifiedCallFoldable(4332 CallInst *CI, unsigned ObjSizeOp, std::optional<unsigned> SizeOp,4333 std::optional<unsigned> StrOp, std::optional<unsigned> FlagOp) {4334 // If this function takes a flag argument, the implementation may use it to4335 // perform extra checks. Don't fold into the non-checking variant.4336 if (FlagOp) {4337 ConstantInt *Flag = dyn_cast<ConstantInt>(CI->getArgOperand(*FlagOp));4338 if (!Flag || !Flag->isZero())4339 return false;4340 }4341 4342 if (SizeOp && CI->getArgOperand(ObjSizeOp) == CI->getArgOperand(*SizeOp))4343 return true;4344 4345 if (ConstantInt *ObjSizeCI =4346 dyn_cast<ConstantInt>(CI->getArgOperand(ObjSizeOp))) {4347 if (ObjSizeCI->isMinusOne())4348 return true;4349 // If the object size wasn't -1 (unknown), bail out if we were asked to.4350 if (OnlyLowerUnknownSize)4351 return false;4352 if (StrOp) {4353 uint64_t Len = GetStringLength(CI->getArgOperand(*StrOp));4354 // If the length is 0 we don't know how long it is and so we can't4355 // remove the check.4356 if (Len)4357 annotateDereferenceableBytes(CI, *StrOp, Len);4358 else4359 return false;4360 return ObjSizeCI->getZExtValue() >= Len;4361 }4362 4363 if (SizeOp) {4364 if (ConstantInt *SizeCI =4365 dyn_cast<ConstantInt>(CI->getArgOperand(*SizeOp)))4366 return ObjSizeCI->getZExtValue() >= SizeCI->getZExtValue();4367 }4368 }4369 return false;4370}4371 4372Value *FortifiedLibCallSimplifier::optimizeMemCpyChk(CallInst *CI,4373 IRBuilderBase &B) {4374 if (isFortifiedCallFoldable(CI, 3, 2)) {4375 CallInst *NewCI =4376 B.CreateMemCpy(CI->getArgOperand(0), Align(1), CI->getArgOperand(1),4377 Align(1), CI->getArgOperand(2));4378 mergeAttributesAndFlags(NewCI, *CI);4379 return CI->getArgOperand(0);4380 }4381 return nullptr;4382}4383 4384Value *FortifiedLibCallSimplifier::optimizeMemMoveChk(CallInst *CI,4385 IRBuilderBase &B) {4386 if (isFortifiedCallFoldable(CI, 3, 2)) {4387 CallInst *NewCI =4388 B.CreateMemMove(CI->getArgOperand(0), Align(1), CI->getArgOperand(1),4389 Align(1), CI->getArgOperand(2));4390 mergeAttributesAndFlags(NewCI, *CI);4391 return CI->getArgOperand(0);4392 }4393 return nullptr;4394}4395 4396Value *FortifiedLibCallSimplifier::optimizeMemSetChk(CallInst *CI,4397 IRBuilderBase &B) {4398 if (isFortifiedCallFoldable(CI, 3, 2)) {4399 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);4400 CallInst *NewCI = B.CreateMemSet(CI->getArgOperand(0), Val,4401 CI->getArgOperand(2), Align(1));4402 mergeAttributesAndFlags(NewCI, *CI);4403 return CI->getArgOperand(0);4404 }4405 return nullptr;4406}4407 4408Value *FortifiedLibCallSimplifier::optimizeMemPCpyChk(CallInst *CI,4409 IRBuilderBase &B) {4410 const DataLayout &DL = CI->getDataLayout();4411 if (isFortifiedCallFoldable(CI, 3, 2))4412 if (Value *Call = emitMemPCpy(CI->getArgOperand(0), CI->getArgOperand(1),4413 CI->getArgOperand(2), B, DL, TLI)) {4414 return mergeAttributesAndFlags(cast<CallInst>(Call), *CI);4415 }4416 return nullptr;4417}4418 4419Value *FortifiedLibCallSimplifier::optimizeStrpCpyChk(CallInst *CI,4420 IRBuilderBase &B,4421 LibFunc Func) {4422 const DataLayout &DL = CI->getDataLayout();4423 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1),4424 *ObjSize = CI->getArgOperand(2);4425 4426 // __stpcpy_chk(x,x,...) -> x+strlen(x)4427 if (Func == LibFunc_stpcpy_chk && !OnlyLowerUnknownSize && Dst == Src) {4428 Value *StrLen = emitStrLen(Src, B, DL, TLI);4429 return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;4430 }4431 4432 // If a) we don't have any length information, or b) we know this will4433 // fit then just lower to a plain st[rp]cpy. Otherwise we'll keep our4434 // st[rp]cpy_chk call which may fail at runtime if the size is too long.4435 // TODO: It might be nice to get a maximum length out of the possible4436 // string lengths for varying.4437 if (isFortifiedCallFoldable(CI, 2, std::nullopt, 1)) {4438 if (Func == LibFunc_strcpy_chk)4439 return copyFlags(*CI, emitStrCpy(Dst, Src, B, TLI));4440 else4441 return copyFlags(*CI, emitStpCpy(Dst, Src, B, TLI));4442 }4443 4444 if (OnlyLowerUnknownSize)4445 return nullptr;4446 4447 // Maybe we can stil fold __st[rp]cpy_chk to __memcpy_chk.4448 uint64_t Len = GetStringLength(Src);4449 if (Len)4450 annotateDereferenceableBytes(CI, 1, Len);4451 else4452 return nullptr;4453 4454 unsigned SizeTBits = TLI->getSizeTSize(*CI->getModule());4455 Type *SizeTTy = IntegerType::get(CI->getContext(), SizeTBits);4456 Value *LenV = ConstantInt::get(SizeTTy, Len);4457 Value *Ret = emitMemCpyChk(Dst, Src, LenV, ObjSize, B, DL, TLI);4458 // If the function was an __stpcpy_chk, and we were able to fold it into4459 // a __memcpy_chk, we still need to return the correct end pointer.4460 if (Ret && Func == LibFunc_stpcpy_chk)4461 return B.CreateInBoundsGEP(B.getInt8Ty(), Dst,4462 ConstantInt::get(SizeTTy, Len - 1));4463 return copyFlags(*CI, cast<CallInst>(Ret));4464}4465 4466Value *FortifiedLibCallSimplifier::optimizeStrLenChk(CallInst *CI,4467 IRBuilderBase &B) {4468 if (isFortifiedCallFoldable(CI, 1, std::nullopt, 0))4469 return copyFlags(*CI, emitStrLen(CI->getArgOperand(0), B,4470 CI->getDataLayout(), TLI));4471 return nullptr;4472}4473 4474Value *FortifiedLibCallSimplifier::optimizeStrpNCpyChk(CallInst *CI,4475 IRBuilderBase &B,4476 LibFunc Func) {4477 if (isFortifiedCallFoldable(CI, 3, 2)) {4478 if (Func == LibFunc_strncpy_chk)4479 return copyFlags(*CI,4480 emitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),4481 CI->getArgOperand(2), B, TLI));4482 else4483 return copyFlags(*CI,4484 emitStpNCpy(CI->getArgOperand(0), CI->getArgOperand(1),4485 CI->getArgOperand(2), B, TLI));4486 }4487 4488 return nullptr;4489}4490 4491Value *FortifiedLibCallSimplifier::optimizeMemCCpyChk(CallInst *CI,4492 IRBuilderBase &B) {4493 if (isFortifiedCallFoldable(CI, 4, 3))4494 return copyFlags(4495 *CI, emitMemCCpy(CI->getArgOperand(0), CI->getArgOperand(1),4496 CI->getArgOperand(2), CI->getArgOperand(3), B, TLI));4497 4498 return nullptr;4499}4500 4501Value *FortifiedLibCallSimplifier::optimizeSNPrintfChk(CallInst *CI,4502 IRBuilderBase &B) {4503 if (isFortifiedCallFoldable(CI, 3, 1, std::nullopt, 2)) {4504 SmallVector<Value *, 8> VariadicArgs(drop_begin(CI->args(), 5));4505 return copyFlags(*CI,4506 emitSNPrintf(CI->getArgOperand(0), CI->getArgOperand(1),4507 CI->getArgOperand(4), VariadicArgs, B, TLI));4508 }4509 4510 return nullptr;4511}4512 4513Value *FortifiedLibCallSimplifier::optimizeSPrintfChk(CallInst *CI,4514 IRBuilderBase &B) {4515 if (isFortifiedCallFoldable(CI, 2, std::nullopt, std::nullopt, 1)) {4516 SmallVector<Value *, 8> VariadicArgs(drop_begin(CI->args(), 4));4517 return copyFlags(*CI,4518 emitSPrintf(CI->getArgOperand(0), CI->getArgOperand(3),4519 VariadicArgs, B, TLI));4520 }4521 4522 return nullptr;4523}4524 4525Value *FortifiedLibCallSimplifier::optimizeStrCatChk(CallInst *CI,4526 IRBuilderBase &B) {4527 if (isFortifiedCallFoldable(CI, 2))4528 return copyFlags(4529 *CI, emitStrCat(CI->getArgOperand(0), CI->getArgOperand(1), B, TLI));4530 4531 return nullptr;4532}4533 4534Value *FortifiedLibCallSimplifier::optimizeStrLCat(CallInst *CI,4535 IRBuilderBase &B) {4536 if (isFortifiedCallFoldable(CI, 3))4537 return copyFlags(*CI,4538 emitStrLCat(CI->getArgOperand(0), CI->getArgOperand(1),4539 CI->getArgOperand(2), B, TLI));4540 4541 return nullptr;4542}4543 4544Value *FortifiedLibCallSimplifier::optimizeStrNCatChk(CallInst *CI,4545 IRBuilderBase &B) {4546 if (isFortifiedCallFoldable(CI, 3))4547 return copyFlags(*CI,4548 emitStrNCat(CI->getArgOperand(0), CI->getArgOperand(1),4549 CI->getArgOperand(2), B, TLI));4550 4551 return nullptr;4552}4553 4554Value *FortifiedLibCallSimplifier::optimizeStrLCpyChk(CallInst *CI,4555 IRBuilderBase &B) {4556 if (isFortifiedCallFoldable(CI, 3))4557 return copyFlags(*CI,4558 emitStrLCpy(CI->getArgOperand(0), CI->getArgOperand(1),4559 CI->getArgOperand(2), B, TLI));4560 4561 return nullptr;4562}4563 4564Value *FortifiedLibCallSimplifier::optimizeVSNPrintfChk(CallInst *CI,4565 IRBuilderBase &B) {4566 if (isFortifiedCallFoldable(CI, 3, 1, std::nullopt, 2))4567 return copyFlags(4568 *CI, emitVSNPrintf(CI->getArgOperand(0), CI->getArgOperand(1),4569 CI->getArgOperand(4), CI->getArgOperand(5), B, TLI));4570 4571 return nullptr;4572}4573 4574Value *FortifiedLibCallSimplifier::optimizeVSPrintfChk(CallInst *CI,4575 IRBuilderBase &B) {4576 if (isFortifiedCallFoldable(CI, 2, std::nullopt, std::nullopt, 1))4577 return copyFlags(*CI,4578 emitVSPrintf(CI->getArgOperand(0), CI->getArgOperand(3),4579 CI->getArgOperand(4), B, TLI));4580 4581 return nullptr;4582}4583 4584Value *FortifiedLibCallSimplifier::optimizeCall(CallInst *CI,4585 IRBuilderBase &Builder) {4586 // FIXME: We shouldn't be changing "nobuiltin" or TLI unavailable calls here.4587 // Some clang users checked for _chk libcall availability using:4588 // __has_builtin(__builtin___memcpy_chk)4589 // When compiling with -fno-builtin, this is always true.4590 // When passing -ffreestanding/-mkernel, which both imply -fno-builtin, we4591 // end up with fortified libcalls, which isn't acceptable in a freestanding4592 // environment which only provides their non-fortified counterparts.4593 //4594 // Until we change clang and/or teach external users to check for availability4595 // differently, disregard the "nobuiltin" attribute and TLI::has.4596 //4597 // PR23093.4598 4599 LibFunc Func;4600 Function *Callee = CI->getCalledFunction();4601 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI);4602 4603 SmallVector<OperandBundleDef, 2> OpBundles;4604 CI->getOperandBundlesAsDefs(OpBundles);4605 4606 IRBuilderBase::OperandBundlesGuard Guard(Builder);4607 Builder.setDefaultOperandBundles(OpBundles);4608 4609 // First, check that this is a known library functions and that the prototype4610 // is correct.4611 if (!TLI->getLibFunc(*Callee, Func))4612 return nullptr;4613 4614 // We never change the calling convention.4615 if (!ignoreCallingConv(Func) && !IsCallingConvC)4616 return nullptr;4617 4618 switch (Func) {4619 case LibFunc_memcpy_chk:4620 return optimizeMemCpyChk(CI, Builder);4621 case LibFunc_mempcpy_chk:4622 return optimizeMemPCpyChk(CI, Builder);4623 case LibFunc_memmove_chk:4624 return optimizeMemMoveChk(CI, Builder);4625 case LibFunc_memset_chk:4626 return optimizeMemSetChk(CI, Builder);4627 case LibFunc_stpcpy_chk:4628 case LibFunc_strcpy_chk:4629 return optimizeStrpCpyChk(CI, Builder, Func);4630 case LibFunc_strlen_chk:4631 return optimizeStrLenChk(CI, Builder);4632 case LibFunc_stpncpy_chk:4633 case LibFunc_strncpy_chk:4634 return optimizeStrpNCpyChk(CI, Builder, Func);4635 case LibFunc_memccpy_chk:4636 return optimizeMemCCpyChk(CI, Builder);4637 case LibFunc_snprintf_chk:4638 return optimizeSNPrintfChk(CI, Builder);4639 case LibFunc_sprintf_chk:4640 return optimizeSPrintfChk(CI, Builder);4641 case LibFunc_strcat_chk:4642 return optimizeStrCatChk(CI, Builder);4643 case LibFunc_strlcat_chk:4644 return optimizeStrLCat(CI, Builder);4645 case LibFunc_strncat_chk:4646 return optimizeStrNCatChk(CI, Builder);4647 case LibFunc_strlcpy_chk:4648 return optimizeStrLCpyChk(CI, Builder);4649 case LibFunc_vsnprintf_chk:4650 return optimizeVSNPrintfChk(CI, Builder);4651 case LibFunc_vsprintf_chk:4652 return optimizeVSPrintfChk(CI, Builder);4653 default:4654 break;4655 }4656 return nullptr;4657}4658 4659FortifiedLibCallSimplifier::FortifiedLibCallSimplifier(4660 const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize)4661 : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}4662