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