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
1945/// Return a variant of Val with float type.
1946/// Currently this works in two cases: If Val is an FPExtension of a float
1947/// value to something bigger, simply return the operand.
1948/// If Val is a ConstantFP but can be converted to a float ConstantFP without
1949/// loss of precision do so.
1950static Value *valueHasFloatPrecision(Value *Val) {
1951 if (FPExtInst *Cast = dyn_cast<FPExtInst>(Val)) {
1952 Value *Op = Cast->getOperand(i_nocapture: 0);
1953 if (Op->getType()->isFloatTy())
1954 return Op;
1955 }
1956 if (ConstantFP *Const = dyn_cast<ConstantFP>(Val)) {
1957 APFloat F = Const->getValueAPF();
1958 bool losesInfo;
1959 (void)F.convert(ToSemantics: APFloat::IEEEsingle(), RM: APFloat::rmNearestTiesToEven,
1960 losesInfo: &losesInfo);
1961 if (!losesInfo)
1962 return ConstantFP::get(Context&: Const->getContext(), V: F);
1963 }
1964 return nullptr;
1965}
1966
1967/// Shrink double -> float functions.
1968static Value *optimizeDoubleFP(CallInst *CI, IRBuilderBase &B,
1969 bool isBinary, const TargetLibraryInfo *TLI,
1970 bool isPrecise = false) {
1971 Function *CalleeFn = CI->getCalledFunction();
1972 if (!CI->getType()->isDoubleTy() || !CalleeFn)
1973 return nullptr;
1974
1975 // If not all the uses of the function are converted to float, then bail out.
1976 // This matters if the precision of the result is more important than the
1977 // precision of the arguments.
1978 if (isPrecise)
1979 for (User *U : CI->users()) {
1980 FPTruncInst *Cast = dyn_cast<FPTruncInst>(Val: U);
1981 if (!Cast || !Cast->getType()->isFloatTy())
1982 return nullptr;
1983 }
1984
1985 // If this is something like 'g((double) float)', convert to 'gf(float)'.
1986 Value *V[2];
1987 V[0] = valueHasFloatPrecision(Val: CI->getArgOperand(i: 0));
1988 V[1] = isBinary ? valueHasFloatPrecision(Val: CI->getArgOperand(i: 1)) : nullptr;
1989 if (!V[0] || (isBinary && !V[1]))
1990 return nullptr;
1991
1992 // If call isn't an intrinsic, check that it isn't within a function with the
1993 // same name as the float version of this call, otherwise the result is an
1994 // infinite loop. For example, from MinGW-w64:
1995 //
1996 // float expf(float val) { return (float) exp((double) val); }
1997 StringRef CalleeName = CalleeFn->getName();
1998 bool IsIntrinsic = CalleeFn->isIntrinsic();
1999 if (!IsIntrinsic) {
2000 StringRef CallerName = CI->getFunction()->getName();
2001 if (CallerName.ends_with(Suffix: 'f') &&
2002 CallerName.size() == (CalleeName.size() + 1) &&
2003 CallerName.starts_with(Prefix: CalleeName))
2004 return nullptr;
2005 }
2006
2007 // Propagate the math semantics from the current function to the new function.
2008 IRBuilderBase::FastMathFlagGuard Guard(B);
2009 B.setFastMathFlags(CI->getFastMathFlags());
2010
2011 // g((double) float) -> (double) gf(float)
2012 Value *R;
2013 if (IsIntrinsic) {
2014 Intrinsic::ID IID = CalleeFn->getIntrinsicID();
2015 R = isBinary ? B.CreateIntrinsic(ID: IID, Types: B.getFloatTy(), Args: V)
2016 : B.CreateIntrinsic(ID: IID, Types: B.getFloatTy(), Args: V[0]);
2017 } else {
2018 AttributeList CalleeAttrs = CalleeFn->getAttributes();
2019 R = isBinary ? emitBinaryFloatFnCall(Op1: V[0], Op2: V[1], TLI, Name: CalleeName, B,
2020 Attrs: CalleeAttrs)
2021 : emitUnaryFloatFnCall(Op: V[0], TLI, Name: CalleeName, B, Attrs: CalleeAttrs);
2022 }
2023 return B.CreateFPExt(V: R, DestTy: B.getDoubleTy());
2024}
2025
2026/// Shrink double -> float for unary functions.
2027static Value *optimizeUnaryDoubleFP(CallInst *CI, IRBuilderBase &B,
2028 const TargetLibraryInfo *TLI,
2029 bool isPrecise = false) {
2030 return optimizeDoubleFP(CI, B, isBinary: false, TLI, isPrecise);
2031}
2032
2033/// Shrink double -> float for binary functions.
2034static Value *optimizeBinaryDoubleFP(CallInst *CI, IRBuilderBase &B,
2035 const TargetLibraryInfo *TLI,
2036 bool isPrecise = false) {
2037 return optimizeDoubleFP(CI, B, isBinary: true, TLI, isPrecise);
2038}
2039
2040// cabs(z) -> sqrt((creal(z)*creal(z)) + (cimag(z)*cimag(z)))
2041Value *LibCallSimplifier::optimizeCAbs(CallInst *CI, IRBuilderBase &B) {
2042 Value *Real, *Imag;
2043
2044 if (CI->arg_size() == 1) {
2045
2046 if (!CI->isFast())
2047 return nullptr;
2048
2049 Value *Op = CI->getArgOperand(i: 0);
2050 assert(Op->getType()->isArrayTy() && "Unexpected signature for cabs!");
2051
2052 Real = B.CreateExtractValue(Agg: Op, Idxs: 0, Name: "real");
2053 Imag = B.CreateExtractValue(Agg: Op, Idxs: 1, Name: "imag");
2054
2055 } else {
2056 assert(CI->arg_size() == 2 && "Unexpected signature for cabs!");
2057
2058 Real = CI->getArgOperand(i: 0);
2059 Imag = CI->getArgOperand(i: 1);
2060
2061 // if real or imaginary part is zero, simplify to abs(cimag(z))
2062 // or abs(creal(z))
2063 Value *AbsOp = nullptr;
2064 if (ConstantFP *ConstReal = dyn_cast<ConstantFP>(Val: Real)) {
2065 if (ConstReal->isZero())
2066 AbsOp = Imag;
2067
2068 } else if (ConstantFP *ConstImag = dyn_cast<ConstantFP>(Val: Imag)) {
2069 if (ConstImag->isZero())
2070 AbsOp = Real;
2071 }
2072
2073 if (AbsOp)
2074 return copyFlags(
2075 Old: *CI, New: B.CreateUnaryIntrinsic(ID: Intrinsic::fabs, V: AbsOp, FMFSource: CI, Name: "cabs"));
2076
2077 if (!CI->isFast())
2078 return nullptr;
2079 }
2080
2081 // Propagate fast-math flags from the existing call to new instructions.
2082 Value *RealReal = B.CreateFMulFMF(L: Real, R: Real, FMFSource: CI);
2083 Value *ImagImag = B.CreateFMulFMF(L: Imag, R: Imag, FMFSource: CI);
2084 return copyFlags(
2085 Old: *CI, New: B.CreateUnaryIntrinsic(ID: Intrinsic::sqrt,
2086 V: B.CreateFAddFMF(L: RealReal, R: ImagImag, FMFSource: CI), FMFSource: CI,
2087 Name: "cabs"));
2088}
2089
2090// Return a properly extended integer (DstWidth bits wide) if the operation is
2091// an itofp.
2092static Value *getIntToFPVal(Value *I2F, IRBuilderBase &B, unsigned DstWidth) {
2093 if (isa<SIToFPInst>(Val: I2F) || isa<UIToFPInst>(Val: I2F)) {
2094 Value *Op = cast<Instruction>(Val: I2F)->getOperand(i: 0);
2095 // Make sure that the exponent fits inside an "int" of size DstWidth,
2096 // thus avoiding any range issues that FP has not.
2097 unsigned BitWidth = Op->getType()->getScalarSizeInBits();
2098 if (BitWidth < DstWidth || (BitWidth == DstWidth && isa<SIToFPInst>(Val: I2F))) {
2099 Type *IntTy = Op->getType()->getWithNewBitWidth(NewBitWidth: DstWidth);
2100 return isa<SIToFPInst>(Val: I2F) ? B.CreateSExt(V: Op, DestTy: IntTy)
2101 : B.CreateZExt(V: Op, DestTy: IntTy);
2102 }
2103 }
2104
2105 return nullptr;
2106}
2107
2108/// Use exp{,2}(x * y) for pow(exp{,2}(x), y);
2109/// ldexp(1.0, x) for pow(2.0, itofp(x)); exp2(n * x) for pow(2.0 ** n, x);
2110/// exp10(x) for pow(10.0, x); exp2(log2(n) * x) for pow(n, x).
2111Value *LibCallSimplifier::replacePowWithExp(CallInst *Pow, IRBuilderBase &B) {
2112 Module *M = Pow->getModule();
2113 Value *Base = Pow->getArgOperand(i: 0), *Expo = Pow->getArgOperand(i: 1);
2114 Type *Ty = Pow->getType();
2115 bool Ignored;
2116
2117 // Evaluate special cases related to a nested function as the base.
2118
2119 // pow(exp(x), y) -> exp(x * y)
2120 // pow(exp2(x), y) -> exp2(x * y)
2121 // If exp{,2}() is used only once, it is better to fold two transcendental
2122 // math functions into one. If used again, exp{,2}() would still have to be
2123 // called with the original argument, then keep both original transcendental
2124 // functions. However, this transformation is only safe with fully relaxed
2125 // math semantics, since, besides rounding differences, it changes overflow
2126 // and underflow behavior quite dramatically. For example:
2127 // pow(exp(1000), 0.001) = pow(inf, 0.001) = inf
2128 // Whereas:
2129 // exp(1000 * 0.001) = exp(1)
2130 // TODO: Loosen the requirement for fully relaxed math semantics.
2131 // TODO: Handle exp10() when more targets have it available.
2132 CallInst *BaseFn = dyn_cast<CallInst>(Val: Base);
2133 if (BaseFn && BaseFn->hasOneUse() && BaseFn->isFast() && Pow->isFast()) {
2134 LibFunc LibFn;
2135
2136 Function *CalleeFn = BaseFn->getCalledFunction();
2137 if (CalleeFn && TLI->getLibFunc(funcName: CalleeFn->getName(), F&: LibFn) &&
2138 isLibFuncEmittable(M, TLI, TheLibFunc: LibFn)) {
2139 StringRef ExpName;
2140 Intrinsic::ID ID;
2141 Value *ExpFn;
2142 LibFunc LibFnFloat, LibFnDouble, LibFnLongDouble;
2143
2144 switch (LibFn) {
2145 default:
2146 return nullptr;
2147 case LibFunc_expf:
2148 case LibFunc_exp:
2149 case LibFunc_expl:
2150 ExpName = TLI->getName(F: LibFunc_exp);
2151 ID = Intrinsic::exp;
2152 LibFnFloat = LibFunc_expf;
2153 LibFnDouble = LibFunc_exp;
2154 LibFnLongDouble = LibFunc_expl;
2155 break;
2156 case LibFunc_exp2f:
2157 case LibFunc_exp2:
2158 case LibFunc_exp2l:
2159 ExpName = TLI->getName(F: LibFunc_exp2);
2160 ID = Intrinsic::exp2;
2161 LibFnFloat = LibFunc_exp2f;
2162 LibFnDouble = LibFunc_exp2;
2163 LibFnLongDouble = LibFunc_exp2l;
2164 break;
2165 }
2166
2167 // Create new exp{,2}() with the product as its argument.
2168 Value *FMul = B.CreateFMul(L: BaseFn->getArgOperand(i: 0), R: Expo, Name: "mul");
2169 ExpFn = BaseFn->doesNotAccessMemory()
2170 ? B.CreateUnaryIntrinsic(ID, V: FMul, FMFSource: nullptr, Name: ExpName)
2171 : emitUnaryFloatFnCall(Op: FMul, TLI, DoubleFn: LibFnDouble, FloatFn: LibFnFloat,
2172 LongDoubleFn: LibFnLongDouble, B,
2173 Attrs: BaseFn->getAttributes());
2174
2175 // Since the new exp{,2}() is different from the original one, dead code
2176 // elimination cannot be trusted to remove it, since it may have side
2177 // effects (e.g., errno). When the only consumer for the original
2178 // exp{,2}() is pow(), then it has to be explicitly erased.
2179 substituteInParent(I: BaseFn, With: ExpFn);
2180 return ExpFn;
2181 }
2182 }
2183
2184 // Evaluate special cases related to a constant base.
2185
2186 const APFloat *BaseF;
2187 if (!match(V: Base, P: m_APFloat(Res&: BaseF)))
2188 return nullptr;
2189
2190 AttributeList NoAttrs; // Attributes are only meaningful on the original call
2191
2192 const bool UseIntrinsic = Pow->doesNotAccessMemory();
2193
2194 // pow(2.0, itofp(x)) -> ldexp(1.0, x)
2195 if ((UseIntrinsic || !Ty->isVectorTy()) && BaseF->isExactlyValue(V: 2.0) &&
2196 (isa<SIToFPInst>(Val: Expo) || isa<UIToFPInst>(Val: Expo)) &&
2197 (UseIntrinsic ||
2198 hasFloatFn(M, TLI, Ty, DoubleFn: LibFunc_ldexp, FloatFn: LibFunc_ldexpf, LongDoubleFn: LibFunc_ldexpl))) {
2199
2200 // TODO: Shouldn't really need to depend on getIntToFPVal for intrinsic. Can
2201 // just directly use the original integer type.
2202 if (Value *ExpoI = getIntToFPVal(I2F: Expo, B, DstWidth: TLI->getIntSize())) {
2203 Constant *One = ConstantFP::get(Ty, V: 1.0);
2204
2205 if (UseIntrinsic) {
2206 return copyFlags(Old: *Pow, New: B.CreateIntrinsic(ID: Intrinsic::ldexp,
2207 Types: {Ty, ExpoI->getType()},
2208 Args: {One, ExpoI}, FMFSource: Pow, Name: "exp2"));
2209 }
2210
2211 return copyFlags(Old: *Pow, New: emitBinaryFloatFnCall(
2212 Op1: One, Op2: ExpoI, TLI, DoubleFn: LibFunc_ldexp, FloatFn: LibFunc_ldexpf,
2213 LongDoubleFn: LibFunc_ldexpl, B, Attrs: NoAttrs));
2214 }
2215 }
2216
2217 // pow(2.0 ** n, x) -> exp2(n * x)
2218 if (hasFloatFn(M, TLI, Ty, DoubleFn: LibFunc_exp2, FloatFn: LibFunc_exp2f, LongDoubleFn: LibFunc_exp2l)) {
2219 APFloat BaseR = APFloat(1.0);
2220 BaseR.convert(ToSemantics: BaseF->getSemantics(), RM: APFloat::rmTowardZero, losesInfo: &Ignored);
2221 BaseR = BaseR / *BaseF;
2222 bool IsInteger = BaseF->isInteger(), IsReciprocal = BaseR.isInteger();
2223 const APFloat *NF = IsReciprocal ? &BaseR : BaseF;
2224 APSInt NI(64, false);
2225 if ((IsInteger || IsReciprocal) &&
2226 NF->convertToInteger(Result&: NI, RM: APFloat::rmTowardZero, IsExact: &Ignored) ==
2227 APFloat::opOK &&
2228 NI > 1 && NI.isPowerOf2()) {
2229 double N = NI.logBase2() * (IsReciprocal ? -1.0 : 1.0);
2230 Value *FMul = B.CreateFMul(L: Expo, R: ConstantFP::get(Ty, V: N), Name: "mul");
2231 if (Pow->doesNotAccessMemory())
2232 return copyFlags(Old: *Pow, New: B.CreateUnaryIntrinsic(ID: Intrinsic::exp2, V: FMul,
2233 FMFSource: nullptr, Name: "exp2"));
2234 else
2235 return copyFlags(Old: *Pow, New: emitUnaryFloatFnCall(Op: FMul, TLI, DoubleFn: LibFunc_exp2,
2236 FloatFn: LibFunc_exp2f,
2237 LongDoubleFn: LibFunc_exp2l, B, Attrs: NoAttrs));
2238 }
2239 }
2240
2241 // pow(10.0, x) -> exp10(x)
2242 if (BaseF->isExactlyValue(V: 10.0) &&
2243 hasFloatFn(M, TLI, Ty, DoubleFn: LibFunc_exp10, FloatFn: LibFunc_exp10f, LongDoubleFn: LibFunc_exp10l)) {
2244
2245 if (Pow->doesNotAccessMemory()) {
2246 CallInst *NewExp10 =
2247 B.CreateIntrinsic(ID: Intrinsic::exp10, Types: {Ty}, Args: {Expo}, FMFSource: Pow, Name: "exp10");
2248 return copyFlags(Old: *Pow, New: NewExp10);
2249 }
2250
2251 return copyFlags(Old: *Pow, New: emitUnaryFloatFnCall(Op: Expo, TLI, DoubleFn: LibFunc_exp10,
2252 FloatFn: LibFunc_exp10f, LongDoubleFn: LibFunc_exp10l,
2253 B, Attrs: NoAttrs));
2254 }
2255
2256 // pow(x, y) -> exp2(log2(x) * y)
2257 if (Pow->hasApproxFunc() && Pow->hasNoNaNs() && BaseF->isFiniteNonZero() &&
2258 !BaseF->isNegative()) {
2259 // pow(1, inf) is defined to be 1 but exp2(log2(1) * inf) evaluates to NaN.
2260 // Luckily optimizePow has already handled the x == 1 case.
2261 assert(!match(Base, m_FPOne()) &&
2262 "pow(1.0, y) should have been simplified earlier!");
2263
2264 Value *Log = nullptr;
2265 if (Ty->isFloatTy())
2266 Log = ConstantFP::get(Ty, V: std::log2(x: BaseF->convertToFloat()));
2267 else if (Ty->isDoubleTy())
2268 Log = ConstantFP::get(Ty, V: std::log2(x: BaseF->convertToDouble()));
2269
2270 if (Log) {
2271 Value *FMul = B.CreateFMul(L: Log, R: Expo, Name: "mul");
2272 if (Pow->doesNotAccessMemory())
2273 return copyFlags(Old: *Pow, New: B.CreateUnaryIntrinsic(ID: Intrinsic::exp2, V: FMul,
2274 FMFSource: nullptr, Name: "exp2"));
2275 else if (hasFloatFn(M, TLI, Ty, DoubleFn: LibFunc_exp2, FloatFn: LibFunc_exp2f,
2276 LongDoubleFn: LibFunc_exp2l))
2277 return copyFlags(Old: *Pow, New: emitUnaryFloatFnCall(Op: FMul, TLI, DoubleFn: LibFunc_exp2,
2278 FloatFn: LibFunc_exp2f,
2279 LongDoubleFn: LibFunc_exp2l, B, Attrs: NoAttrs));
2280 }
2281 }
2282
2283 return nullptr;
2284}
2285
2286static Value *getSqrtCall(Value *V, AttributeList Attrs, bool NoErrno,
2287 Module *M, IRBuilderBase &B,
2288 const TargetLibraryInfo *TLI) {
2289 // If errno is never set, then use the intrinsic for sqrt().
2290 if (NoErrno)
2291 return B.CreateUnaryIntrinsic(ID: Intrinsic::sqrt, V, FMFSource: nullptr, Name: "sqrt");
2292
2293 // Otherwise, use the libcall for sqrt().
2294 if (hasFloatFn(M, TLI, Ty: V->getType(), DoubleFn: LibFunc_sqrt, FloatFn: LibFunc_sqrtf,
2295 LongDoubleFn: LibFunc_sqrtl))
2296 // TODO: We also should check that the target can in fact lower the sqrt()
2297 // libcall. We currently have no way to ask this question, so we ask if
2298 // the target has a sqrt() libcall, which is not exactly the same.
2299 return emitUnaryFloatFnCall(Op: V, TLI, DoubleFn: LibFunc_sqrt, FloatFn: LibFunc_sqrtf,
2300 LongDoubleFn: LibFunc_sqrtl, B, Attrs);
2301
2302 return nullptr;
2303}
2304
2305/// Use square root in place of pow(x, +/-0.5).
2306Value *LibCallSimplifier::replacePowWithSqrt(CallInst *Pow, IRBuilderBase &B) {
2307 Value *Sqrt, *Base = Pow->getArgOperand(i: 0), *Expo = Pow->getArgOperand(i: 1);
2308 Module *Mod = Pow->getModule();
2309 Type *Ty = Pow->getType();
2310
2311 const APFloat *ExpoF;
2312 if (!match(V: Expo, P: m_APFloat(Res&: ExpoF)) ||
2313 (!ExpoF->isExactlyValue(V: 0.5) && !ExpoF->isExactlyValue(V: -0.5)))
2314 return nullptr;
2315
2316 // Converting pow(X, -0.5) to 1/sqrt(X) may introduce an extra rounding step,
2317 // so that requires fast-math-flags (afn or reassoc).
2318 if (ExpoF->isNegative() && (!Pow->hasApproxFunc() && !Pow->hasAllowReassoc()))
2319 return nullptr;
2320
2321 // If we have a pow() library call (accesses memory) and we can't guarantee
2322 // that the base is not an infinity, give up:
2323 // pow(-Inf, 0.5) is optionally required to have a result of +Inf (not setting
2324 // errno), but sqrt(-Inf) is required by various standards to set errno.
2325 if (!Pow->doesNotAccessMemory() && !Pow->hasNoInfs() &&
2326 !isKnownNeverInfinity(
2327 V: Base, SQ: SimplifyQuery(DL, TLI, DT, AC, Pow, true, true, DC)))
2328 return nullptr;
2329
2330 Sqrt = getSqrtCall(V: Base, Attrs: AttributeList(), NoErrno: Pow->doesNotAccessMemory(), M: Mod, B,
2331 TLI);
2332 if (!Sqrt)
2333 return nullptr;
2334
2335 // Handle signed zero base by expanding to fabs(sqrt(x)).
2336 if (!Pow->hasNoSignedZeros())
2337 Sqrt = B.CreateUnaryIntrinsic(ID: Intrinsic::fabs, V: Sqrt, FMFSource: nullptr, Name: "abs");
2338
2339 Sqrt = copyFlags(Old: *Pow, New: Sqrt);
2340
2341 // Handle non finite base by expanding to
2342 // (x == -infinity ? +infinity : sqrt(x)).
2343 if (!Pow->hasNoInfs()) {
2344 Value *PosInf = ConstantFP::getInfinity(Ty),
2345 *NegInf = ConstantFP::getInfinity(Ty, Negative: true);
2346 Value *FCmp = B.CreateFCmpOEQ(LHS: Base, RHS: NegInf, Name: "isinf");
2347 Sqrt = B.CreateSelect(C: FCmp, True: PosInf, False: Sqrt);
2348 }
2349
2350 // If the exponent is negative, then get the reciprocal.
2351 if (ExpoF->isNegative())
2352 Sqrt = B.CreateFDiv(L: ConstantFP::get(Ty, V: 1.0), R: Sqrt, Name: "reciprocal");
2353
2354 return Sqrt;
2355}
2356
2357static Value *createPowWithIntegerExponent(Value *Base, Value *Expo, Module *M,
2358 IRBuilderBase &B) {
2359 Value *Args[] = {Base, Expo};
2360 Type *Types[] = {Base->getType(), Expo->getType()};
2361 return B.CreateIntrinsic(ID: Intrinsic::powi, Types, Args);
2362}
2363
2364Value *LibCallSimplifier::optimizePow(CallInst *Pow, IRBuilderBase &B) {
2365 Value *Base = Pow->getArgOperand(i: 0);
2366 Value *Expo = Pow->getArgOperand(i: 1);
2367 Function *Callee = Pow->getCalledFunction();
2368 StringRef Name = Callee->getName();
2369 Type *Ty = Pow->getType();
2370 Module *M = Pow->getModule();
2371 bool AllowApprox = Pow->hasApproxFunc();
2372 bool Ignored;
2373
2374 // Propagate the math semantics from the call to any created instructions.
2375 IRBuilderBase::FastMathFlagGuard Guard(B);
2376 B.setFastMathFlags(Pow->getFastMathFlags());
2377 // Evaluate special cases related to the base.
2378
2379 // pow(1.0, x) -> 1.0
2380 if (match(V: Base, P: m_FPOne()))
2381 return Base;
2382
2383 if (Value *Exp = replacePowWithExp(Pow, B))
2384 return Exp;
2385
2386 // Evaluate special cases related to the exponent.
2387
2388 // pow(x, -1.0) -> 1.0 / x
2389 if (match(V: Expo, P: m_SpecificFP(V: -1.0)))
2390 return B.CreateFDiv(L: ConstantFP::get(Ty, V: 1.0), R: Base, Name: "reciprocal");
2391
2392 // pow(x, +/-0.0) -> 1.0
2393 if (match(V: Expo, P: m_AnyZeroFP()))
2394 return ConstantFP::get(Ty, V: 1.0);
2395
2396 // pow(x, 1.0) -> x
2397 if (match(V: Expo, P: m_FPOne()))
2398 return Base;
2399
2400 // pow(x, 2.0) -> x * x
2401 if (match(V: Expo, P: m_SpecificFP(V: 2.0)))
2402 return B.CreateFMul(L: Base, R: Base, Name: "square");
2403
2404 if (Value *Sqrt = replacePowWithSqrt(Pow, B))
2405 return Sqrt;
2406
2407 // If we can approximate pow:
2408 // pow(x, n) -> powi(x, n) * sqrt(x) if n has exactly a 0.5 fraction
2409 // pow(x, n) -> powi(x, n) if n is a constant signed integer value
2410 const APFloat *ExpoF;
2411 if (AllowApprox && match(V: Expo, P: m_APFloat(Res&: ExpoF)) &&
2412 !ExpoF->isExactlyValue(V: 0.5) && !ExpoF->isExactlyValue(V: -0.5)) {
2413 APFloat ExpoA(abs(X: *ExpoF));
2414 APFloat ExpoI(*ExpoF);
2415 Value *Sqrt = nullptr;
2416 if (!ExpoA.isInteger()) {
2417 APFloat Expo2 = ExpoA;
2418 // To check if ExpoA is an integer + 0.5, we add it to itself. If there
2419 // is no floating point exception and the result is an integer, then
2420 // ExpoA == integer + 0.5
2421 if (Expo2.add(RHS: ExpoA, RM: APFloat::rmNearestTiesToEven) != APFloat::opOK)
2422 return nullptr;
2423
2424 if (!Expo2.isInteger())
2425 return nullptr;
2426
2427 if (ExpoI.roundToIntegral(RM: APFloat::rmTowardNegative) !=
2428 APFloat::opInexact)
2429 return nullptr;
2430 if (!ExpoI.isInteger())
2431 return nullptr;
2432 ExpoF = &ExpoI;
2433
2434 Sqrt = getSqrtCall(V: Base, Attrs: AttributeList(), NoErrno: Pow->doesNotAccessMemory(), M,
2435 B, TLI);
2436 if (!Sqrt)
2437 return nullptr;
2438 }
2439
2440 // 0.5 fraction is now optionally handled.
2441 // Do pow -> powi for remaining integer exponent
2442 APSInt IntExpo(TLI->getIntSize(), /*isUnsigned=*/false);
2443 if (ExpoF->isInteger() &&
2444 ExpoF->convertToInteger(Result&: IntExpo, RM: APFloat::rmTowardZero, IsExact: &Ignored) ==
2445 APFloat::opOK) {
2446 Value *PowI = copyFlags(
2447 Old: *Pow,
2448 New: createPowWithIntegerExponent(
2449 Base, Expo: ConstantInt::get(Ty: B.getIntNTy(N: TLI->getIntSize()), V: IntExpo),
2450 M, B));
2451
2452 if (PowI && Sqrt)
2453 return B.CreateFMul(L: PowI, R: Sqrt);
2454
2455 return PowI;
2456 }
2457 }
2458
2459 // powf(x, itofp(y)) -> powi(x, y)
2460 if (AllowApprox && (isa<SIToFPInst>(Val: Expo) || isa<UIToFPInst>(Val: Expo))) {
2461 if (Value *ExpoI = getIntToFPVal(I2F: Expo, B, DstWidth: TLI->getIntSize()))
2462 return copyFlags(Old: *Pow, New: createPowWithIntegerExponent(Base, Expo: ExpoI, M, B));
2463 }
2464
2465 // Shrink pow() to powf() if the arguments are single precision,
2466 // unless the result is expected to be double precision.
2467 if (UnsafeFPShrink && Name == TLI->getName(F: LibFunc_pow) &&
2468 hasFloatVersion(M, FuncName: Name)) {
2469 if (Value *Shrunk = optimizeBinaryDoubleFP(CI: Pow, B, TLI, isPrecise: true))
2470 return Shrunk;
2471 }
2472
2473 return nullptr;
2474}
2475
2476Value *LibCallSimplifier::optimizeExp2(CallInst *CI, IRBuilderBase &B) {
2477 Module *M = CI->getModule();
2478 Function *Callee = CI->getCalledFunction();
2479 StringRef Name = Callee->getName();
2480 Value *Ret = nullptr;
2481 if (UnsafeFPShrink && Name == TLI->getName(F: LibFunc_exp2) &&
2482 hasFloatVersion(M, FuncName: Name))
2483 Ret = optimizeUnaryDoubleFP(CI, B, TLI, isPrecise: true);
2484
2485 // If we have an llvm.exp2 intrinsic, emit the llvm.ldexp intrinsic. If we
2486 // have the libcall, emit the libcall.
2487 //
2488 // TODO: In principle we should be able to just always use the intrinsic for
2489 // any doesNotAccessMemory callsite.
2490
2491 const bool UseIntrinsic = Callee->isIntrinsic();
2492 // Bail out for vectors because the code below only expects scalars.
2493 Type *Ty = CI->getType();
2494 if (!UseIntrinsic && Ty->isVectorTy())
2495 return Ret;
2496
2497 // exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= IntSize
2498 // exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < IntSize
2499 Value *Op = CI->getArgOperand(i: 0);
2500 if ((isa<SIToFPInst>(Val: Op) || isa<UIToFPInst>(Val: Op)) &&
2501 (UseIntrinsic ||
2502 hasFloatFn(M, TLI, Ty, DoubleFn: LibFunc_ldexp, FloatFn: LibFunc_ldexpf, LongDoubleFn: LibFunc_ldexpl))) {
2503 if (Value *Exp = getIntToFPVal(I2F: Op, B, DstWidth: TLI->getIntSize())) {
2504 Constant *One = ConstantFP::get(Ty, V: 1.0);
2505
2506 if (UseIntrinsic) {
2507 return copyFlags(Old: *CI, New: B.CreateIntrinsic(ID: Intrinsic::ldexp,
2508 Types: {Ty, Exp->getType()},
2509 Args: {One, Exp}, FMFSource: CI));
2510 }
2511
2512 IRBuilderBase::FastMathFlagGuard Guard(B);
2513 B.setFastMathFlags(CI->getFastMathFlags());
2514 return copyFlags(Old: *CI, New: emitBinaryFloatFnCall(
2515 Op1: One, Op2: Exp, TLI, DoubleFn: LibFunc_ldexp, FloatFn: LibFunc_ldexpf,
2516 LongDoubleFn: LibFunc_ldexpl, B, Attrs: AttributeList()));
2517 }
2518 }
2519
2520 return Ret;
2521}
2522
2523Value *LibCallSimplifier::optimizeFMinFMax(CallInst *CI, IRBuilderBase &B) {
2524 Module *M = CI->getModule();
2525
2526 // If we can shrink the call to a float function rather than a double
2527 // function, do that first.
2528 Function *Callee = CI->getCalledFunction();
2529 StringRef Name = Callee->getName();
2530 if ((Name == "fmin" || Name == "fmax") && hasFloatVersion(M, FuncName: Name))
2531 if (Value *Ret = optimizeBinaryDoubleFP(CI, B, TLI))
2532 return Ret;
2533
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
2544 Intrinsic::ID IID = Callee->getName().starts_with(Prefix: "fmin") ? Intrinsic::minnum
2545 : Intrinsic::maxnum;
2546 return copyFlags(Old: *CI, New: B.CreateBinaryIntrinsic(ID: IID, LHS: CI->getArgOperand(i: 0),
2547 RHS: CI->getArgOperand(i: 1), FMFSource: FMF));
2548}
2549
2550Value *LibCallSimplifier::optimizeFMinimumnumFMaximumnum(CallInst *CI,
2551 IRBuilderBase &B) {
2552 Module *M = CI->getModule();
2553
2554 // If we can shrink the call to a float function rather than a double
2555 // function, do that first.
2556 Function *Callee = CI->getCalledFunction();
2557 StringRef Name = Callee->getName();
2558 if ((Name == "fminimum_num" || Name == "fmaximum_num") &&
2559 hasFloatVersion(M, FuncName: Name))
2560 if (Value *Ret = optimizeBinaryDoubleFP(CI, B, TLI))
2561 return Ret;
2562
2563 // The new fminimum_num/fmaximum_num functions, unlike fmin/fmax, *are*
2564 // sensitive to the sign of zero, so we don't change the fast-math flags like
2565 // we did for those.
2566
2567 Intrinsic::ID IID = Callee->getName().starts_with(Prefix: "fminimum_num")
2568 ? Intrinsic::minimumnum
2569 : Intrinsic::maximumnum;
2570 return copyFlags(Old: *CI, New: B.CreateBinaryIntrinsic(ID: IID, LHS: CI->getArgOperand(i: 0),
2571 RHS: CI->getArgOperand(i: 1), FMFSource: CI));
2572}
2573
2574Value *LibCallSimplifier::optimizeLog(CallInst *Log, IRBuilderBase &B) {
2575 Function *LogFn = Log->getCalledFunction();
2576 StringRef LogNm = LogFn->getName();
2577 Intrinsic::ID LogID = LogFn->getIntrinsicID();
2578 Module *Mod = Log->getModule();
2579 Type *Ty = Log->getType();
2580
2581 if (UnsafeFPShrink && hasFloatVersion(M: Mod, FuncName: LogNm))
2582 if (Value *Ret = optimizeUnaryDoubleFP(CI: Log, B, TLI, isPrecise: true))
2583 return Ret;
2584
2585 LibFunc LogLb, ExpLb, Exp2Lb, Exp10Lb, PowLb;
2586
2587 // This is only applicable to log(), log2(), log10().
2588 if (TLI->getLibFunc(funcName: LogNm, F&: LogLb)) {
2589 switch (LogLb) {
2590 case LibFunc_logf:
2591 LogID = Intrinsic::log;
2592 ExpLb = LibFunc_expf;
2593 Exp2Lb = LibFunc_exp2f;
2594 Exp10Lb = LibFunc_exp10f;
2595 PowLb = LibFunc_powf;
2596 break;
2597 case LibFunc_log:
2598 LogID = Intrinsic::log;
2599 ExpLb = LibFunc_exp;
2600 Exp2Lb = LibFunc_exp2;
2601 Exp10Lb = LibFunc_exp10;
2602 PowLb = LibFunc_pow;
2603 break;
2604 case LibFunc_logl:
2605 LogID = Intrinsic::log;
2606 ExpLb = LibFunc_expl;
2607 Exp2Lb = LibFunc_exp2l;
2608 Exp10Lb = LibFunc_exp10l;
2609 PowLb = LibFunc_powl;
2610 break;
2611 case LibFunc_log2f:
2612 LogID = Intrinsic::log2;
2613 ExpLb = LibFunc_expf;
2614 Exp2Lb = LibFunc_exp2f;
2615 Exp10Lb = LibFunc_exp10f;
2616 PowLb = LibFunc_powf;
2617 break;
2618 case LibFunc_log2:
2619 LogID = Intrinsic::log2;
2620 ExpLb = LibFunc_exp;
2621 Exp2Lb = LibFunc_exp2;
2622 Exp10Lb = LibFunc_exp10;
2623 PowLb = LibFunc_pow;
2624 break;
2625 case LibFunc_log2l:
2626 LogID = Intrinsic::log2;
2627 ExpLb = LibFunc_expl;
2628 Exp2Lb = LibFunc_exp2l;
2629 Exp10Lb = LibFunc_exp10l;
2630 PowLb = LibFunc_powl;
2631 break;
2632 case LibFunc_log10f:
2633 LogID = Intrinsic::log10;
2634 ExpLb = LibFunc_expf;
2635 Exp2Lb = LibFunc_exp2f;
2636 Exp10Lb = LibFunc_exp10f;
2637 PowLb = LibFunc_powf;
2638 break;
2639 case LibFunc_log10:
2640 LogID = Intrinsic::log10;
2641 ExpLb = LibFunc_exp;
2642 Exp2Lb = LibFunc_exp2;
2643 Exp10Lb = LibFunc_exp10;
2644 PowLb = LibFunc_pow;
2645 break;
2646 case LibFunc_log10l:
2647 LogID = Intrinsic::log10;
2648 ExpLb = LibFunc_expl;
2649 Exp2Lb = LibFunc_exp2l;
2650 Exp10Lb = LibFunc_exp10l;
2651 PowLb = LibFunc_powl;
2652 break;
2653 default:
2654 return nullptr;
2655 }
2656
2657 // Convert libcall to intrinsic if the value is known > 0.
2658 bool IsKnownNoErrno = Log->hasNoNaNs() && Log->hasNoInfs();
2659 if (!IsKnownNoErrno) {
2660 SimplifyQuery SQ(DL, TLI, DT, AC, Log, true, true, DC);
2661 KnownFPClass Known = computeKnownFPClass(
2662 V: Log->getOperand(i_nocapture: 0),
2663 InterestedClasses: KnownFPClass::OrderedLessThanZeroMask | fcSubnormal, SQ);
2664 Function *F = Log->getParent()->getParent();
2665 const fltSemantics &FltSem = Ty->getScalarType()->getFltSemantics();
2666 IsKnownNoErrno =
2667 Known.cannotBeOrderedLessThanZero() &&
2668 Known.isKnownNeverLogicalZero(Mode: F->getDenormalMode(FPType: FltSem));
2669 }
2670 if (IsKnownNoErrno) {
2671 auto *NewLog = B.CreateUnaryIntrinsic(ID: LogID, V: Log->getArgOperand(i: 0), FMFSource: Log);
2672 NewLog->copyMetadata(SrcInst: *Log);
2673 return copyFlags(Old: *Log, New: NewLog);
2674 }
2675 } else if (LogID == Intrinsic::log || LogID == Intrinsic::log2 ||
2676 LogID == Intrinsic::log10) {
2677 if (Ty->getScalarType()->isFloatTy()) {
2678 ExpLb = LibFunc_expf;
2679 Exp2Lb = LibFunc_exp2f;
2680 Exp10Lb = LibFunc_exp10f;
2681 PowLb = LibFunc_powf;
2682 } else if (Ty->getScalarType()->isDoubleTy()) {
2683 ExpLb = LibFunc_exp;
2684 Exp2Lb = LibFunc_exp2;
2685 Exp10Lb = LibFunc_exp10;
2686 PowLb = LibFunc_pow;
2687 } else
2688 return nullptr;
2689 } else
2690 return nullptr;
2691
2692 // The earlier call must also be 'fast' in order to do these transforms.
2693 CallInst *Arg = dyn_cast<CallInst>(Val: Log->getArgOperand(i: 0));
2694 if (!Log->isFast() || !Arg || !Arg->isFast() || !Arg->hasOneUse())
2695 return nullptr;
2696
2697 IRBuilderBase::FastMathFlagGuard Guard(B);
2698 B.setFastMathFlags(FastMathFlags::getFast());
2699
2700 Intrinsic::ID ArgID = Arg->getIntrinsicID();
2701 LibFunc ArgLb = NotLibFunc;
2702 TLI->getLibFunc(CB: *Arg, F&: ArgLb);
2703
2704 // log(pow(x,y)) -> y*log(x)
2705 AttributeList NoAttrs;
2706 if (ArgLb == PowLb || ArgID == Intrinsic::pow || ArgID == Intrinsic::powi) {
2707 Value *LogX =
2708 Log->doesNotAccessMemory()
2709 ? B.CreateUnaryIntrinsic(ID: LogID, V: Arg->getOperand(i_nocapture: 0), FMFSource: nullptr, Name: "log")
2710 : emitUnaryFloatFnCall(Op: Arg->getOperand(i_nocapture: 0), TLI, Name: LogNm, B, Attrs: NoAttrs);
2711 Value *Y = Arg->getArgOperand(i: 1);
2712 // Cast exponent to FP if integer.
2713 if (ArgID == Intrinsic::powi)
2714 Y = B.CreateSIToFP(V: Y, DestTy: Ty, Name: "cast");
2715 Value *MulY = B.CreateFMul(L: Y, R: LogX, Name: "mul");
2716 // Since pow() may have side effects, e.g. errno,
2717 // dead code elimination may not be trusted to remove it.
2718 substituteInParent(I: Arg, With: MulY);
2719 return MulY;
2720 }
2721
2722 // log(exp{,2,10}(y)) -> y*log({e,2,10})
2723 // TODO: There is no exp10() intrinsic yet.
2724 if (ArgLb == ExpLb || ArgLb == Exp2Lb || ArgLb == Exp10Lb ||
2725 ArgID == Intrinsic::exp || ArgID == Intrinsic::exp2) {
2726 Constant *Eul;
2727 if (ArgLb == ExpLb || ArgID == Intrinsic::exp)
2728 // FIXME: Add more precise value of e for long double.
2729 Eul = ConstantFP::get(Ty: Log->getType(), V: numbers::e);
2730 else if (ArgLb == Exp2Lb || ArgID == Intrinsic::exp2)
2731 Eul = ConstantFP::get(Ty: Log->getType(), V: 2.0);
2732 else
2733 Eul = ConstantFP::get(Ty: Log->getType(), V: 10.0);
2734 Value *LogE = Log->doesNotAccessMemory()
2735 ? B.CreateUnaryIntrinsic(ID: LogID, V: Eul, FMFSource: nullptr, Name: "log")
2736 : emitUnaryFloatFnCall(Op: Eul, TLI, Name: LogNm, B, Attrs: NoAttrs);
2737 Value *MulY = B.CreateFMul(L: Arg->getArgOperand(i: 0), R: LogE, Name: "mul");
2738 // Since exp() may have side effects, e.g. errno,
2739 // dead code elimination may not be trusted to remove it.
2740 substituteInParent(I: Arg, With: MulY);
2741 return MulY;
2742 }
2743
2744 return nullptr;
2745}
2746
2747// sqrt(exp(X)) -> exp(X * 0.5)
2748Value *LibCallSimplifier::mergeSqrtToExp(CallInst *CI, IRBuilderBase &B) {
2749 if (!CI->hasAllowReassoc())
2750 return nullptr;
2751
2752 Function *SqrtFn = CI->getCalledFunction();
2753 CallInst *Arg = dyn_cast<CallInst>(Val: CI->getArgOperand(i: 0));
2754 if (!Arg || !Arg->hasAllowReassoc() || !Arg->hasOneUse())
2755 return nullptr;
2756 Intrinsic::ID ArgID = Arg->getIntrinsicID();
2757 LibFunc ArgLb = NotLibFunc;
2758 TLI->getLibFunc(CB: *Arg, F&: ArgLb);
2759
2760 LibFunc SqrtLb, ExpLb, Exp2Lb, Exp10Lb;
2761
2762 if (TLI->getLibFunc(funcName: SqrtFn->getName(), F&: SqrtLb))
2763 switch (SqrtLb) {
2764 case LibFunc_sqrtf:
2765 ExpLb = LibFunc_expf;
2766 Exp2Lb = LibFunc_exp2f;
2767 Exp10Lb = LibFunc_exp10f;
2768 break;
2769 case LibFunc_sqrt:
2770 ExpLb = LibFunc_exp;
2771 Exp2Lb = LibFunc_exp2;
2772 Exp10Lb = LibFunc_exp10;
2773 break;
2774 case LibFunc_sqrtl:
2775 ExpLb = LibFunc_expl;
2776 Exp2Lb = LibFunc_exp2l;
2777 Exp10Lb = LibFunc_exp10l;
2778 break;
2779 default:
2780 return nullptr;
2781 }
2782 else if (SqrtFn->getIntrinsicID() == Intrinsic::sqrt) {
2783 if (CI->getType()->getScalarType()->isFloatTy()) {
2784 ExpLb = LibFunc_expf;
2785 Exp2Lb = LibFunc_exp2f;
2786 Exp10Lb = LibFunc_exp10f;
2787 } else if (CI->getType()->getScalarType()->isDoubleTy()) {
2788 ExpLb = LibFunc_exp;
2789 Exp2Lb = LibFunc_exp2;
2790 Exp10Lb = LibFunc_exp10;
2791 } else
2792 return nullptr;
2793 } else
2794 return nullptr;
2795
2796 if (ArgLb != ExpLb && ArgLb != Exp2Lb && ArgLb != Exp10Lb &&
2797 ArgID != Intrinsic::exp && ArgID != Intrinsic::exp2)
2798 return nullptr;
2799
2800 IRBuilderBase::InsertPointGuard Guard(B);
2801 B.SetInsertPoint(Arg);
2802 auto *ExpOperand = Arg->getOperand(i_nocapture: 0);
2803 auto *FMul =
2804 B.CreateFMulFMF(L: ExpOperand, R: ConstantFP::get(Ty: ExpOperand->getType(), V: 0.5),
2805 FMFSource: CI, Name: "merged.sqrt");
2806
2807 Arg->setOperand(i_nocapture: 0, Val_nocapture: FMul);
2808 return Arg;
2809}
2810
2811Value *LibCallSimplifier::optimizeSqrt(CallInst *CI, IRBuilderBase &B) {
2812 Module *M = CI->getModule();
2813 Function *Callee = CI->getCalledFunction();
2814 Value *Ret = nullptr;
2815 // TODO: Once we have a way (other than checking for the existince of the
2816 // libcall) to tell whether our target can lower @llvm.sqrt, relax the
2817 // condition below.
2818 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_sqrtf) &&
2819 (Callee->getName() == "sqrt" ||
2820 Callee->getIntrinsicID() == Intrinsic::sqrt))
2821 Ret = optimizeUnaryDoubleFP(CI, B, TLI, isPrecise: true);
2822
2823 if (Value *Opt = mergeSqrtToExp(CI, B))
2824 return Opt;
2825
2826 if (!CI->isFast())
2827 return Ret;
2828
2829 Instruction *I = dyn_cast<Instruction>(Val: CI->getArgOperand(i: 0));
2830 if (!I || I->getOpcode() != Instruction::FMul || !I->isFast())
2831 return Ret;
2832
2833 // We're looking for a repeated factor in a multiplication tree,
2834 // so we can do this fold: sqrt(x * x) -> fabs(x);
2835 // or this fold: sqrt((x * x) * y) -> fabs(x) * sqrt(y).
2836 Value *Op0 = I->getOperand(i: 0);
2837 Value *Op1 = I->getOperand(i: 1);
2838 Value *RepeatOp = nullptr;
2839 Value *OtherOp = nullptr;
2840 if (Op0 == Op1) {
2841 // Simple match: the operands of the multiply are identical.
2842 RepeatOp = Op0;
2843 } else {
2844 // Look for a more complicated pattern: one of the operands is itself
2845 // a multiply, so search for a common factor in that multiply.
2846 // Note: We don't bother looking any deeper than this first level or for
2847 // variations of this pattern because instcombine's visitFMUL and/or the
2848 // reassociation pass should give us this form.
2849 Value *MulOp;
2850 if (match(V: Op0, P: m_FMul(L: m_Value(V&: MulOp), R: m_Deferred(V: MulOp))) &&
2851 cast<Instruction>(Val: Op0)->isFast()) {
2852 // Pattern: sqrt((x * x) * z)
2853 RepeatOp = MulOp;
2854 OtherOp = Op1;
2855 } else if (match(V: Op1, P: m_FMul(L: m_Value(V&: MulOp), R: m_Deferred(V: MulOp))) &&
2856 cast<Instruction>(Val: Op1)->isFast()) {
2857 // Pattern: sqrt(z * (x * x))
2858 RepeatOp = MulOp;
2859 OtherOp = Op0;
2860 }
2861 }
2862 if (!RepeatOp)
2863 return Ret;
2864
2865 // Fast math flags for any created instructions should match the sqrt
2866 // and multiply.
2867
2868 // If we found a repeated factor, hoist it out of the square root and
2869 // replace it with the fabs of that factor.
2870 Value *FabsCall =
2871 B.CreateUnaryIntrinsic(ID: Intrinsic::fabs, V: RepeatOp, FMFSource: I, Name: "fabs");
2872 if (OtherOp) {
2873 // If we found a non-repeated factor, we still need to get its square
2874 // root. We then multiply that by the value that was simplified out
2875 // of the square root calculation.
2876 Value *SqrtCall =
2877 B.CreateUnaryIntrinsic(ID: Intrinsic::sqrt, V: OtherOp, FMFSource: I, Name: "sqrt");
2878 return copyFlags(Old: *CI, New: B.CreateFMulFMF(L: FabsCall, R: SqrtCall, FMFSource: I));
2879 }
2880 return copyFlags(Old: *CI, New: FabsCall);
2881}
2882
2883Value *LibCallSimplifier::optimizeFMod(CallInst *CI, IRBuilderBase &B) {
2884
2885 // fmod(x,y) can set errno if y == 0 or x == +/-inf, and returns Nan in those
2886 // case. If we know those do not happen, then we can convert the fmod into
2887 // frem.
2888 bool IsNoNan = CI->hasNoNaNs();
2889 if (!IsNoNan) {
2890 SimplifyQuery SQ(DL, TLI, DT, AC, CI, true, true, DC);
2891 KnownFPClass Known0 = computeKnownFPClass(V: CI->getOperand(i_nocapture: 0), InterestedClasses: fcInf, SQ);
2892 if (Known0.isKnownNeverInfinity()) {
2893 KnownFPClass Known1 =
2894 computeKnownFPClass(V: CI->getOperand(i_nocapture: 1), InterestedClasses: fcZero | fcSubnormal, SQ);
2895 Function *F = CI->getParent()->getParent();
2896 const fltSemantics &FltSem =
2897 CI->getType()->getScalarType()->getFltSemantics();
2898 IsNoNan = Known1.isKnownNeverLogicalZero(Mode: F->getDenormalMode(FPType: FltSem));
2899 }
2900 }
2901
2902 if (IsNoNan) {
2903 Value *FRem = B.CreateFRemFMF(L: CI->getOperand(i_nocapture: 0), R: CI->getOperand(i_nocapture: 1), FMFSource: CI);
2904 if (auto *FRemI = dyn_cast<Instruction>(Val: FRem))
2905 FRemI->setHasNoNaNs(true);
2906 return FRem;
2907 }
2908 return nullptr;
2909}
2910
2911Value *LibCallSimplifier::optimizeTrigInversionPairs(CallInst *CI,
2912 IRBuilderBase &B) {
2913 Module *M = CI->getModule();
2914 Function *Callee = CI->getCalledFunction();
2915 Value *Ret = nullptr;
2916 StringRef Name = Callee->getName();
2917 if (UnsafeFPShrink &&
2918 (Name == "tan" || Name == "atanh" || Name == "sinh" || Name == "cosh" ||
2919 Name == "asinh") &&
2920 hasFloatVersion(M, FuncName: Name))
2921 Ret = optimizeUnaryDoubleFP(CI, B, TLI, isPrecise: true);
2922
2923 Value *Op1 = CI->getArgOperand(i: 0);
2924 auto *OpC = dyn_cast<CallInst>(Val: Op1);
2925 if (!OpC)
2926 return Ret;
2927
2928 // Both calls must be 'fast' in order to remove them.
2929 if (!CI->isFast() || !OpC->isFast())
2930 return Ret;
2931
2932 // tan(atan(x)) -> x
2933 // atanh(tanh(x)) -> x
2934 // sinh(asinh(x)) -> x
2935 // asinh(sinh(x)) -> x
2936 // cosh(acosh(x)) -> x
2937 LibFunc Func;
2938 Function *F = OpC->getCalledFunction();
2939 if (F && TLI->getLibFunc(funcName: F->getName(), F&: Func) &&
2940 isLibFuncEmittable(M, TLI, TheLibFunc: Func)) {
2941 LibFunc inverseFunc = llvm::StringSwitch<LibFunc>(Callee->getName())
2942 .Case(S: "tan", Value: LibFunc_atan)
2943 .Case(S: "atanh", Value: LibFunc_tanh)
2944 .Case(S: "sinh", Value: LibFunc_asinh)
2945 .Case(S: "cosh", Value: LibFunc_acosh)
2946 .Case(S: "tanf", Value: LibFunc_atanf)
2947 .Case(S: "atanhf", Value: LibFunc_tanhf)
2948 .Case(S: "sinhf", Value: LibFunc_asinhf)
2949 .Case(S: "coshf", Value: LibFunc_acoshf)
2950 .Case(S: "tanl", Value: LibFunc_atanl)
2951 .Case(S: "atanhl", Value: LibFunc_tanhl)
2952 .Case(S: "sinhl", Value: LibFunc_asinhl)
2953 .Case(S: "coshl", Value: LibFunc_acoshl)
2954 .Case(S: "asinh", Value: LibFunc_sinh)
2955 .Case(S: "asinhf", Value: LibFunc_sinhf)
2956 .Case(S: "asinhl", Value: LibFunc_sinhl)
2957 .Default(Value: NotLibFunc); // Used as error value
2958 if (Func == inverseFunc)
2959 Ret = OpC->getArgOperand(i: 0);
2960 }
2961 return Ret;
2962}
2963
2964static bool isTrigLibCall(CallInst *CI) {
2965 // We can only hope to do anything useful if we can ignore things like errno
2966 // and floating-point exceptions.
2967 // We already checked the prototype.
2968 return CI->doesNotThrow() && CI->doesNotAccessMemory();
2969}
2970
2971static bool insertSinCosCall(IRBuilderBase &B, Function *OrigCallee, Value *Arg,
2972 bool UseFloat, Value *&Sin, Value *&Cos,
2973 Value *&SinCos, const TargetLibraryInfo *TLI) {
2974 Module *M = OrigCallee->getParent();
2975 Type *ArgTy = Arg->getType();
2976 Type *ResTy;
2977 StringRef Name;
2978
2979 Triple T(OrigCallee->getParent()->getTargetTriple());
2980 if (UseFloat) {
2981 Name = "__sincospif_stret";
2982
2983 assert(T.getArch() != Triple::x86 && "x86 messy and unsupported for now");
2984 // x86_64 can't use {float, float} since that would be returned in both
2985 // xmm0 and xmm1, which isn't what a real struct would do.
2986 ResTy = T.getArch() == Triple::x86_64
2987 ? static_cast<Type *>(FixedVectorType::get(ElementType: ArgTy, NumElts: 2))
2988 : static_cast<Type *>(StructType::get(elt1: ArgTy, elts: ArgTy));
2989 } else {
2990 Name = "__sincospi_stret";
2991 ResTy = StructType::get(elt1: ArgTy, elts: ArgTy);
2992 }
2993
2994 if (!isLibFuncEmittable(M, TLI, Name))
2995 return false;
2996 LibFunc TheLibFunc;
2997 TLI->getLibFunc(funcName: Name, F&: TheLibFunc);
2998 FunctionCallee Callee = getOrInsertLibFunc(
2999 M, TLI: *TLI, TheLibFunc, AttributeList: OrigCallee->getAttributes(), RetTy: ResTy, Args: ArgTy);
3000
3001 if (Instruction *ArgInst = dyn_cast<Instruction>(Val: Arg)) {
3002 // If the argument is an instruction, it must dominate all uses so put our
3003 // sincos call there.
3004 B.SetInsertPoint(TheBB: ArgInst->getParent(), IP: ++ArgInst->getIterator());
3005 } else {
3006 // Otherwise (e.g. for a constant) the beginning of the function is as
3007 // good a place as any.
3008 BasicBlock &EntryBB = B.GetInsertBlock()->getParent()->getEntryBlock();
3009 B.SetInsertPoint(TheBB: &EntryBB, IP: EntryBB.begin());
3010 }
3011
3012 SinCos = B.CreateCall(Callee, Args: Arg, Name: "sincospi");
3013
3014 if (SinCos->getType()->isStructTy()) {
3015 Sin = B.CreateExtractValue(Agg: SinCos, Idxs: 0, Name: "sinpi");
3016 Cos = B.CreateExtractValue(Agg: SinCos, Idxs: 1, Name: "cospi");
3017 } else {
3018 Sin = B.CreateExtractElement(Vec: SinCos, Idx: ConstantInt::get(Ty: B.getInt32Ty(), V: 0),
3019 Name: "sinpi");
3020 Cos = B.CreateExtractElement(Vec: SinCos, Idx: ConstantInt::get(Ty: B.getInt32Ty(), V: 1),
3021 Name: "cospi");
3022 }
3023
3024 return true;
3025}
3026
3027static Value *optimizeSymmetricCall(CallInst *CI, bool IsEven,
3028 IRBuilderBase &B) {
3029 Value *X;
3030 Value *Src = CI->getArgOperand(i: 0);
3031
3032 if (match(V: Src, P: m_OneUse(SubPattern: m_FNeg(X: m_Value(V&: X))))) {
3033 auto *Call = B.CreateCall(Callee: CI->getCalledFunction(), Args: {X});
3034 Call->copyFastMathFlags(I: CI);
3035 auto *CallInst = copyFlags(Old: *CI, New: Call);
3036 if (IsEven) {
3037 // Even function: f(-x) = f(x)
3038 return CallInst;
3039 }
3040 // Odd function: f(-x) = -f(x)
3041 return B.CreateFNegFMF(V: CallInst, FMFSource: CI);
3042 }
3043
3044 // Even function: f(abs(x)) = f(x), f(copysign(x, y)) = f(x)
3045 if (IsEven && (match(V: Src, P: m_FAbs(Op0: m_Value(V&: X))) ||
3046 match(V: Src, P: m_CopySign(Op0: m_Value(V&: X), Op1: m_Value())))) {
3047 auto *Call = B.CreateCall(Callee: CI->getCalledFunction(), Args: {X});
3048 Call->copyFastMathFlags(I: CI);
3049 return copyFlags(Old: *CI, New: Call);
3050 }
3051
3052 return nullptr;
3053}
3054
3055Value *LibCallSimplifier::optimizeSymmetric(CallInst *CI, LibFunc Func,
3056 IRBuilderBase &B) {
3057 switch (Func) {
3058 case LibFunc_cos:
3059 case LibFunc_cosf:
3060 case LibFunc_cosl:
3061 return optimizeSymmetricCall(CI, /*IsEven*/ true, B);
3062
3063 case LibFunc_sin:
3064 case LibFunc_sinf:
3065 case LibFunc_sinl:
3066
3067 case LibFunc_tan:
3068 case LibFunc_tanf:
3069 case LibFunc_tanl:
3070
3071 case LibFunc_erf:
3072 case LibFunc_erff:
3073 case LibFunc_erfl:
3074 return optimizeSymmetricCall(CI, /*IsEven*/ false, B);
3075
3076 default:
3077 return nullptr;
3078 }
3079}
3080
3081Value *LibCallSimplifier::optimizeSinCosPi(CallInst *CI, bool IsSin, IRBuilderBase &B) {
3082 // Make sure the prototype is as expected, otherwise the rest of the
3083 // function is probably invalid and likely to abort.
3084 if (!isTrigLibCall(CI))
3085 return nullptr;
3086
3087 Value *Arg = CI->getArgOperand(i: 0);
3088 if (isa<ConstantData>(Val: Arg))
3089 return nullptr;
3090
3091 SmallVector<CallInst *, 1> SinCalls;
3092 SmallVector<CallInst *, 1> CosCalls;
3093 SmallVector<CallInst *, 1> SinCosCalls;
3094
3095 bool IsFloat = Arg->getType()->isFloatTy();
3096
3097 // Look for all compatible sinpi, cospi and sincospi calls with the same
3098 // argument. If there are enough (in some sense) we can make the
3099 // substitution.
3100 Function *F = CI->getFunction();
3101 for (User *U : Arg->users())
3102 classifyArgUse(Val: U, F, IsFloat, SinCalls, CosCalls, SinCosCalls);
3103
3104 // It's only worthwhile if both sinpi and cospi are actually used.
3105 if (SinCalls.empty() || CosCalls.empty())
3106 return nullptr;
3107
3108 Value *Sin, *Cos, *SinCos;
3109 if (!insertSinCosCall(B, OrigCallee: CI->getCalledFunction(), Arg, UseFloat: IsFloat, Sin, Cos,
3110 SinCos, TLI))
3111 return nullptr;
3112
3113 auto replaceTrigInsts = [this](SmallVectorImpl<CallInst *> &Calls,
3114 Value *Res) {
3115 for (CallInst *C : Calls)
3116 replaceAllUsesWith(I: C, With: Res);
3117 };
3118
3119 replaceTrigInsts(SinCalls, Sin);
3120 replaceTrigInsts(CosCalls, Cos);
3121 replaceTrigInsts(SinCosCalls, SinCos);
3122
3123 return IsSin ? Sin : Cos;
3124}
3125
3126void LibCallSimplifier::classifyArgUse(
3127 Value *Val, Function *F, bool IsFloat,
3128 SmallVectorImpl<CallInst *> &SinCalls,
3129 SmallVectorImpl<CallInst *> &CosCalls,
3130 SmallVectorImpl<CallInst *> &SinCosCalls) {
3131 auto *CI = dyn_cast<CallInst>(Val);
3132 if (!CI || CI->use_empty())
3133 return;
3134
3135 // Don't consider calls in other functions.
3136 if (CI->getFunction() != F)
3137 return;
3138
3139 Module *M = CI->getModule();
3140 Function *Callee = CI->getCalledFunction();
3141 LibFunc Func;
3142 if (!Callee || !TLI->getLibFunc(FDecl: *Callee, F&: Func) ||
3143 !isLibFuncEmittable(M, TLI, TheLibFunc: Func) ||
3144 !isTrigLibCall(CI))
3145 return;
3146
3147 if (IsFloat) {
3148 if (Func == LibFunc_sinpif)
3149 SinCalls.push_back(Elt: CI);
3150 else if (Func == LibFunc_cospif)
3151 CosCalls.push_back(Elt: CI);
3152 else if (Func == LibFunc_sincospif_stret)
3153 SinCosCalls.push_back(Elt: CI);
3154 } else {
3155 if (Func == LibFunc_sinpi)
3156 SinCalls.push_back(Elt: CI);
3157 else if (Func == LibFunc_cospi)
3158 CosCalls.push_back(Elt: CI);
3159 else if (Func == LibFunc_sincospi_stret)
3160 SinCosCalls.push_back(Elt: CI);
3161 }
3162}
3163
3164/// Constant folds remquo
3165Value *LibCallSimplifier::optimizeRemquo(CallInst *CI, IRBuilderBase &B) {
3166 const APFloat *X, *Y;
3167 if (!match(V: CI->getArgOperand(i: 0), P: m_APFloat(Res&: X)) ||
3168 !match(V: CI->getArgOperand(i: 1), P: m_APFloat(Res&: Y)))
3169 return nullptr;
3170
3171 APFloat::opStatus Status;
3172 APFloat Quot = *X;
3173 Status = Quot.divide(RHS: *Y, RM: APFloat::rmNearestTiesToEven);
3174 if (Status != APFloat::opOK && Status != APFloat::opInexact)
3175 return nullptr;
3176 APFloat Rem = *X;
3177 if (Rem.remainder(RHS: *Y) != APFloat::opOK)
3178 return nullptr;
3179
3180 // TODO: We can only keep at least the three of the last bits of x/y
3181 unsigned IntBW = TLI->getIntSize();
3182 APSInt QuotInt(IntBW, /*isUnsigned=*/false);
3183 bool IsExact;
3184 Status =
3185 Quot.convertToInteger(Result&: QuotInt, RM: APFloat::rmNearestTiesToEven, IsExact: &IsExact);
3186 if (Status != APFloat::opOK && Status != APFloat::opInexact)
3187 return nullptr;
3188
3189 B.CreateAlignedStore(
3190 Val: ConstantInt::getSigned(Ty: B.getIntNTy(N: IntBW), V: QuotInt.getExtValue()),
3191 Ptr: CI->getArgOperand(i: 2), Align: CI->getParamAlign(ArgNo: 2));
3192 return ConstantFP::get(Ty: CI->getType(), V: Rem);
3193}
3194
3195/// Constant folds fdim
3196Value *LibCallSimplifier::optimizeFdim(CallInst *CI, IRBuilderBase &B) {
3197 // Cannot perform the fold unless the call has attribute memory(none)
3198 if (!CI->doesNotAccessMemory())
3199 return nullptr;
3200
3201 // TODO : Handle undef values
3202 // Propagate poison if any
3203 if (isa<PoisonValue>(Val: CI->getArgOperand(i: 0)))
3204 return CI->getArgOperand(i: 0);
3205 if (isa<PoisonValue>(Val: CI->getArgOperand(i: 1)))
3206 return CI->getArgOperand(i: 1);
3207
3208 const APFloat *X, *Y;
3209 // Check if both values are constants
3210 if (!match(V: CI->getArgOperand(i: 0), P: m_APFloat(Res&: X)) ||
3211 !match(V: CI->getArgOperand(i: 1), P: m_APFloat(Res&: Y)))
3212 return nullptr;
3213
3214 APFloat Difference = *X;
3215 Difference.subtract(RHS: *Y, RM: RoundingMode::NearestTiesToEven);
3216
3217 APFloat MaxVal =
3218 maximum(A: Difference, B: APFloat::getZero(Sem: CI->getType()->getFltSemantics()));
3219 return ConstantFP::get(Ty: CI->getType(), V: MaxVal);
3220}
3221
3222//===----------------------------------------------------------------------===//
3223// Integer Library Call Optimizations
3224//===----------------------------------------------------------------------===//
3225
3226Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilderBase &B) {
3227 // All variants of ffs return int which need not be 32 bits wide.
3228 // ffs{,l,ll}(x) -> x != 0 ? (int)llvm.cttz(x)+1 : 0
3229 Type *RetType = CI->getType();
3230 Value *Op = CI->getArgOperand(i: 0);
3231 Type *ArgType = Op->getType();
3232 Value *V = B.CreateIntrinsic(ID: Intrinsic::cttz, Types: {ArgType}, Args: {Op, B.getTrue()},
3233 FMFSource: nullptr, Name: "cttz");
3234 V = B.CreateAdd(LHS: V, RHS: ConstantInt::get(Ty: V->getType(), V: 1));
3235 V = B.CreateIntCast(V, DestTy: RetType, isSigned: false);
3236
3237 Value *Cond = B.CreateICmpNE(LHS: Op, RHS: Constant::getNullValue(Ty: ArgType));
3238 return B.CreateSelect(C: Cond, True: V, False: ConstantInt::get(Ty: RetType, V: 0));
3239}
3240
3241Value *LibCallSimplifier::optimizeFls(CallInst *CI, IRBuilderBase &B) {
3242 // All variants of fls return int which need not be 32 bits wide.
3243 // fls{,l,ll}(x) -> (int)(sizeInBits(x) - llvm.ctlz(x, false))
3244 Value *Op = CI->getArgOperand(i: 0);
3245 Type *ArgType = Op->getType();
3246 Value *V = B.CreateIntrinsic(ID: Intrinsic::ctlz, Types: {ArgType}, Args: {Op, B.getFalse()},
3247 FMFSource: nullptr, Name: "ctlz");
3248 V = B.CreateSub(LHS: ConstantInt::get(Ty: V->getType(), V: ArgType->getIntegerBitWidth()),
3249 RHS: V);
3250 return B.CreateIntCast(V, DestTy: CI->getType(), isSigned: false);
3251}
3252
3253Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilderBase &B) {
3254 // abs(x) -> x <s 0 ? -x : x
3255 // The negation has 'nsw' because abs of INT_MIN is undefined.
3256 Value *X = CI->getArgOperand(i: 0);
3257 Value *IsNeg = B.CreateIsNeg(Arg: X);
3258 Value *NegX = B.CreateNSWNeg(V: X, Name: "neg");
3259 return B.CreateSelect(C: IsNeg, True: NegX, False: X);
3260}
3261
3262Value *LibCallSimplifier::optimizeIsDigit(CallInst *CI, IRBuilderBase &B) {
3263 // isdigit(c) -> (c-'0') <u 10
3264 Value *Op = CI->getArgOperand(i: 0);
3265 Type *ArgType = Op->getType();
3266 Op = B.CreateSub(LHS: Op, RHS: ConstantInt::get(Ty: ArgType, V: '0'), Name: "isdigittmp");
3267 Op = B.CreateICmpULT(LHS: Op, RHS: ConstantInt::get(Ty: ArgType, V: 10), Name: "isdigit");
3268 return B.CreateZExt(V: Op, DestTy: CI->getType());
3269}
3270
3271Value *LibCallSimplifier::optimizeIsAscii(CallInst *CI, IRBuilderBase &B) {
3272 // isascii(c) -> c <u 128
3273 Value *Op = CI->getArgOperand(i: 0);
3274 Type *ArgType = Op->getType();
3275 Op = B.CreateICmpULT(LHS: Op, RHS: ConstantInt::get(Ty: ArgType, V: 128), Name: "isascii");
3276 return B.CreateZExt(V: Op, DestTy: CI->getType());
3277}
3278
3279Value *LibCallSimplifier::optimizeToAscii(CallInst *CI, IRBuilderBase &B) {
3280 // toascii(c) -> c & 0x7f
3281 return B.CreateAnd(LHS: CI->getArgOperand(i: 0),
3282 RHS: ConstantInt::get(Ty: CI->getType(), V: 0x7F));
3283}
3284
3285// Fold calls to atoi, atol, and atoll.
3286Value *LibCallSimplifier::optimizeAtoi(CallInst *CI, IRBuilderBase &B) {
3287 StringRef Str;
3288 if (!getConstantStringInfo(V: CI->getArgOperand(i: 0), Str))
3289 return nullptr;
3290
3291 return convertStrToInt(CI, Str, EndPtr: nullptr, Base: 10, /*AsSigned=*/true, B);
3292}
3293
3294// Fold calls to strtol, strtoll, strtoul, and strtoull.
3295Value *LibCallSimplifier::optimizeStrToInt(CallInst *CI, IRBuilderBase &B,
3296 bool AsSigned) {
3297 Value *EndPtr = CI->getArgOperand(i: 1);
3298 if (isa<ConstantPointerNull>(Val: EndPtr)) {
3299 // With a null EndPtr, this function won't capture the main argument.
3300 // It would be readonly too, except that it still may write to errno.
3301 CI->addParamAttr(ArgNo: 0, Attr: Attribute::getWithCaptureInfo(Context&: CI->getContext(),
3302 CI: CaptureInfo::none()));
3303 EndPtr = nullptr;
3304 } else if (!isKnownNonZero(V: EndPtr, Q: DL))
3305 return nullptr;
3306
3307 StringRef Str;
3308 if (!getConstantStringInfo(V: CI->getArgOperand(i: 0), Str))
3309 return nullptr;
3310
3311 if (ConstantInt *CInt = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 2))) {
3312 return convertStrToInt(CI, Str, EndPtr, Base: CInt->getSExtValue(), AsSigned, B);
3313 }
3314
3315 return nullptr;
3316}
3317
3318//===----------------------------------------------------------------------===//
3319// Formatting and IO Library Call Optimizations
3320//===----------------------------------------------------------------------===//
3321
3322static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg);
3323
3324Value *LibCallSimplifier::optimizeErrorReporting(CallInst *CI, IRBuilderBase &B,
3325 int StreamArg) {
3326 Function *Callee = CI->getCalledFunction();
3327 // Error reporting calls should be cold, mark them as such.
3328 // This applies even to non-builtin calls: it is only a hint and applies to
3329 // functions that the frontend might not understand as builtins.
3330
3331 // This heuristic was suggested in:
3332 // Improving Static Branch Prediction in a Compiler
3333 // Brian L. Deitrich, Ben-Chung Cheng, Wen-mei W. Hwu
3334 // Proceedings of PACT'98, Oct. 1998, IEEE
3335 if (!CI->hasFnAttr(Kind: Attribute::Cold) &&
3336 isReportingError(Callee, CI, StreamArg)) {
3337 CI->addFnAttr(Kind: Attribute::Cold);
3338 }
3339
3340 return nullptr;
3341}
3342
3343static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg) {
3344 if (!Callee || !Callee->isDeclaration())
3345 return false;
3346
3347 if (StreamArg < 0)
3348 return true;
3349
3350 // These functions might be considered cold, but only if their stream
3351 // argument is stderr.
3352
3353 if (StreamArg >= (int)CI->arg_size())
3354 return false;
3355 LoadInst *LI = dyn_cast<LoadInst>(Val: CI->getArgOperand(i: StreamArg));
3356 if (!LI)
3357 return false;
3358 GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: LI->getPointerOperand());
3359 if (!GV || !GV->isDeclaration())
3360 return false;
3361 return GV->getName() == "stderr";
3362}
3363
3364Value *LibCallSimplifier::optimizePrintFString(CallInst *CI, IRBuilderBase &B) {
3365 // Check for a fixed format string.
3366 StringRef FormatStr;
3367 if (!getConstantStringInfo(V: CI->getArgOperand(i: 0), Str&: FormatStr))
3368 return nullptr;
3369
3370 // Empty format string -> noop.
3371 if (FormatStr.empty()) // Tolerate printf's declared void.
3372 return CI->use_empty() ? (Value *)CI : ConstantInt::get(Ty: CI->getType(), V: 0);
3373
3374 // Do not do any of the following transformations if the printf return value
3375 // is used, in general the printf return value is not compatible with either
3376 // putchar() or puts().
3377 if (!CI->use_empty())
3378 return nullptr;
3379
3380 Type *IntTy = CI->getType();
3381 // printf("x") -> putchar('x'), even for "%" and "%%".
3382 if (FormatStr.size() == 1 || FormatStr == "%%") {
3383 // Convert the character to unsigned char before passing it to putchar
3384 // to avoid host-specific sign extension in the IR. Putchar converts
3385 // it to unsigned char regardless.
3386 Value *IntChar = ConstantInt::get(Ty: IntTy, V: (unsigned char)FormatStr[0]);
3387 return copyFlags(Old: *CI, New: emitPutChar(Char: IntChar, B, TLI));
3388 }
3389
3390 // Try to remove call or emit putchar/puts.
3391 if (FormatStr == "%s" && CI->arg_size() > 1) {
3392 StringRef OperandStr;
3393 if (!getConstantStringInfo(V: CI->getOperand(i_nocapture: 1), Str&: OperandStr))
3394 return nullptr;
3395 // printf("%s", "") --> NOP
3396 if (OperandStr.empty())
3397 return (Value *)CI;
3398 // printf("%s", "a") --> putchar('a')
3399 if (OperandStr.size() == 1) {
3400 // Convert the character to unsigned char before passing it to putchar
3401 // to avoid host-specific sign extension in the IR. Putchar converts
3402 // it to unsigned char regardless.
3403 Value *IntChar = ConstantInt::get(Ty: IntTy, V: (unsigned char)OperandStr[0]);
3404 return copyFlags(Old: *CI, New: emitPutChar(Char: IntChar, B, TLI));
3405 }
3406 // printf("%s", str"\n") --> puts(str)
3407 if (OperandStr.back() == '\n') {
3408 OperandStr = OperandStr.drop_back();
3409 Value *GV = B.CreateGlobalString(Str: OperandStr, Name: "str");
3410 return copyFlags(Old: *CI, New: emitPutS(Str: GV, B, TLI));
3411 }
3412 return nullptr;
3413 }
3414
3415 // printf("foo\n") --> puts("foo")
3416 if (FormatStr.back() == '\n' &&
3417 !FormatStr.contains(C: '%')) { // No format characters.
3418 // Create a string literal with no \n on it. We expect the constant merge
3419 // pass to be run after this pass, to merge duplicate strings.
3420 FormatStr = FormatStr.drop_back();
3421 Value *GV = B.CreateGlobalString(Str: FormatStr, Name: "str");
3422 return copyFlags(Old: *CI, New: emitPutS(Str: GV, B, TLI));
3423 }
3424
3425 // Optimize specific format strings.
3426 // printf("%c", chr) --> putchar(chr)
3427 if (FormatStr == "%c" && CI->arg_size() > 1 &&
3428 CI->getArgOperand(i: 1)->getType()->isIntegerTy()) {
3429 // Convert the argument to the type expected by putchar, i.e., int, which
3430 // need not be 32 bits wide but which is the same as printf's return type.
3431 Value *IntChar = B.CreateIntCast(V: CI->getArgOperand(i: 1), DestTy: IntTy, isSigned: false);
3432 return copyFlags(Old: *CI, New: emitPutChar(Char: IntChar, B, TLI));
3433 }
3434
3435 // printf("%s\n", str) --> puts(str)
3436 if (FormatStr == "%s\n" && CI->arg_size() > 1 &&
3437 CI->getArgOperand(i: 1)->getType()->isPointerTy())
3438 return copyFlags(Old: *CI, New: emitPutS(Str: CI->getArgOperand(i: 1), B, TLI));
3439 return nullptr;
3440}
3441
3442Value *LibCallSimplifier::optimizePrintF(CallInst *CI, IRBuilderBase &B) {
3443
3444 Module *M = CI->getModule();
3445 Function *Callee = CI->getCalledFunction();
3446 FunctionType *FT = Callee->getFunctionType();
3447 if (Value *V = optimizePrintFString(CI, B)) {
3448 return V;
3449 }
3450
3451 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos: 0);
3452
3453 // printf(format, ...) -> iprintf(format, ...) if no floating point
3454 // arguments.
3455 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_iprintf) &&
3456 !callHasFloatingPointArgument(CI)) {
3457 FunctionCallee IPrintFFn = getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_iprintf, T: FT,
3458 AttributeList: Callee->getAttributes());
3459 CallInst *New = cast<CallInst>(Val: CI->clone());
3460 New->setCalledFunction(IPrintFFn);
3461 B.Insert(I: New);
3462 return New;
3463 }
3464
3465 // printf(format, ...) -> __small_printf(format, ...) if no 128-bit floating point
3466 // arguments.
3467 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_small_printf) &&
3468 !callHasFP128Argument(CI)) {
3469 auto SmallPrintFFn = getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_small_printf, T: FT,
3470 AttributeList: Callee->getAttributes());
3471 CallInst *New = cast<CallInst>(Val: CI->clone());
3472 New->setCalledFunction(SmallPrintFFn);
3473 B.Insert(I: New);
3474 return New;
3475 }
3476
3477 return nullptr;
3478}
3479
3480Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI,
3481 IRBuilderBase &B) {
3482 // Check for a fixed format string.
3483 StringRef FormatStr;
3484 if (!getConstantStringInfo(V: CI->getArgOperand(i: 1), Str&: FormatStr))
3485 return nullptr;
3486
3487 // If we just have a format string (nothing else crazy) transform it.
3488 Value *Dest = CI->getArgOperand(i: 0);
3489 if (CI->arg_size() == 2) {
3490 // Make sure there's no % in the constant array. We could try to handle
3491 // %% -> % in the future if we cared.
3492 if (FormatStr.contains(C: '%'))
3493 return nullptr; // we found a format specifier, bail out.
3494
3495 // sprintf(str, fmt) -> llvm.memcpy(align 1 str, align 1 fmt, strlen(fmt)+1)
3496 B.CreateMemCpy(Dst: Dest, DstAlign: Align(1), Src: CI->getArgOperand(i: 1), SrcAlign: Align(1),
3497 // Copy the null byte.
3498 Size: TLI->getAsSizeT(V: FormatStr.size() + 1, M: *CI->getModule()));
3499 return ConstantInt::get(Ty: CI->getType(), V: FormatStr.size());
3500 }
3501
3502 // The remaining optimizations require the format string to be "%s" or "%c"
3503 // and have an extra operand.
3504 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3)
3505 return nullptr;
3506
3507 // Decode the second character of the format string.
3508 if (FormatStr[1] == 'c') {
3509 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
3510 if (!CI->getArgOperand(i: 2)->getType()->isIntegerTy())
3511 return nullptr;
3512 Value *V = B.CreateTrunc(V: CI->getArgOperand(i: 2), DestTy: B.getInt8Ty(), Name: "char");
3513 Value *Ptr = Dest;
3514 B.CreateStore(Val: V, Ptr);
3515 Ptr = B.CreateInBoundsGEP(Ty: B.getInt8Ty(), Ptr, IdxList: B.getInt32(C: 1), Name: "nul");
3516 B.CreateStore(Val: B.getInt8(C: 0), Ptr);
3517
3518 return ConstantInt::get(Ty: CI->getType(), V: 1);
3519 }
3520
3521 if (FormatStr[1] == 's') {
3522 // sprintf(dest, "%s", str) -> llvm.memcpy(align 1 dest, align 1 str,
3523 // strlen(str)+1)
3524 if (!CI->getArgOperand(i: 2)->getType()->isPointerTy())
3525 return nullptr;
3526
3527 if (CI->use_empty())
3528 // sprintf(dest, "%s", str) -> strcpy(dest, str)
3529 return copyFlags(Old: *CI, New: emitStrCpy(Dst: Dest, Src: CI->getArgOperand(i: 2), B, TLI));
3530
3531 uint64_t SrcLen = GetStringLength(V: CI->getArgOperand(i: 2));
3532 if (SrcLen) {
3533 B.CreateMemCpy(Dst: Dest, DstAlign: Align(1), Src: CI->getArgOperand(i: 2), SrcAlign: Align(1),
3534 Size: TLI->getAsSizeT(V: SrcLen, M: *CI->getModule()));
3535 // Returns total number of characters written without null-character.
3536 return ConstantInt::get(Ty: CI->getType(), V: SrcLen - 1);
3537 } else if (Value *V = emitStpCpy(Dst: Dest, Src: CI->getArgOperand(i: 2), B, TLI)) {
3538 // sprintf(dest, "%s", str) -> stpcpy(dest, str) - dest
3539 Value *PtrDiff = B.CreatePtrDiff(ElemTy: B.getInt8Ty(), LHS: V, RHS: Dest);
3540 return B.CreateIntCast(V: PtrDiff, DestTy: CI->getType(), isSigned: false);
3541 }
3542
3543 if (llvm::shouldOptimizeForSize(BB: CI->getParent(), PSI, BFI,
3544 QueryType: PGSOQueryType::IRPass))
3545 return nullptr;
3546
3547 Value *Len = emitStrLen(Ptr: CI->getArgOperand(i: 2), B, DL, TLI);
3548 if (!Len)
3549 return nullptr;
3550 Value *IncLen =
3551 B.CreateAdd(LHS: Len, RHS: ConstantInt::get(Ty: Len->getType(), V: 1), Name: "leninc");
3552 B.CreateMemCpy(Dst: Dest, DstAlign: Align(1), Src: CI->getArgOperand(i: 2), SrcAlign: Align(1), Size: IncLen);
3553
3554 // The sprintf result is the unincremented number of bytes in the string.
3555 return B.CreateIntCast(V: Len, DestTy: CI->getType(), isSigned: false);
3556 }
3557 return nullptr;
3558}
3559
3560Value *LibCallSimplifier::optimizeSPrintF(CallInst *CI, IRBuilderBase &B) {
3561 Module *M = CI->getModule();
3562 Function *Callee = CI->getCalledFunction();
3563 FunctionType *FT = Callee->getFunctionType();
3564 if (Value *V = optimizeSPrintFString(CI, B)) {
3565 return V;
3566 }
3567
3568 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos: {0, 1});
3569
3570 // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
3571 // point arguments.
3572 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_siprintf) &&
3573 !callHasFloatingPointArgument(CI)) {
3574 FunctionCallee SIPrintFFn = getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_siprintf,
3575 T: FT, AttributeList: Callee->getAttributes());
3576 CallInst *New = cast<CallInst>(Val: CI->clone());
3577 New->setCalledFunction(SIPrintFFn);
3578 B.Insert(I: New);
3579 return New;
3580 }
3581
3582 // sprintf(str, format, ...) -> __small_sprintf(str, format, ...) if no 128-bit
3583 // floating point arguments.
3584 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_small_sprintf) &&
3585 !callHasFP128Argument(CI)) {
3586 auto SmallSPrintFFn = getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_small_sprintf, T: FT,
3587 AttributeList: Callee->getAttributes());
3588 CallInst *New = cast<CallInst>(Val: CI->clone());
3589 New->setCalledFunction(SmallSPrintFFn);
3590 B.Insert(I: New);
3591 return New;
3592 }
3593
3594 return nullptr;
3595}
3596
3597// Transform an snprintf call CI with the bound N to format the string Str
3598// either to a call to memcpy, or to single character a store, or to nothing,
3599// and fold the result to a constant. A nonnull StrArg refers to the string
3600// argument being formatted. Otherwise the call is one with N < 2 and
3601// the "%c" directive to format a single character.
3602Value *LibCallSimplifier::emitSnPrintfMemCpy(CallInst *CI, Value *StrArg,
3603 StringRef Str, uint64_t N,
3604 IRBuilderBase &B) {
3605 assert(StrArg || (N < 2 && Str.size() == 1));
3606
3607 unsigned IntBits = TLI->getIntSize();
3608 uint64_t IntMax = maxIntN(N: IntBits);
3609 if (Str.size() > IntMax)
3610 // Bail if the string is longer than INT_MAX. POSIX requires
3611 // implementations to set errno to EOVERFLOW in this case, in
3612 // addition to when N is larger than that (checked by the caller).
3613 return nullptr;
3614
3615 Value *StrLen = ConstantInt::get(Ty: CI->getType(), V: Str.size());
3616 if (N == 0)
3617 return StrLen;
3618
3619 // Set to the number of bytes to copy fron StrArg which is also
3620 // the offset of the terinating nul.
3621 uint64_t NCopy;
3622 if (N > Str.size())
3623 // Copy the full string, including the terminating nul (which must
3624 // be present regardless of the bound).
3625 NCopy = Str.size() + 1;
3626 else
3627 NCopy = N - 1;
3628
3629 Value *DstArg = CI->getArgOperand(i: 0);
3630 if (NCopy && StrArg)
3631 // Transform the call to lvm.memcpy(dst, fmt, N).
3632 copyFlags(Old: *CI, New: B.CreateMemCpy(Dst: DstArg, DstAlign: Align(1), Src: StrArg, SrcAlign: Align(1),
3633 Size: TLI->getAsSizeT(V: NCopy, M: *CI->getModule())));
3634
3635 if (N > Str.size())
3636 // Return early when the whole format string, including the final nul,
3637 // has been copied.
3638 return StrLen;
3639
3640 // Otherwise, when truncating the string append a terminating nul.
3641 Type *Int8Ty = B.getInt8Ty();
3642 Value *NulOff = B.getIntN(N: IntBits, C: NCopy);
3643 Value *DstEnd = B.CreateInBoundsGEP(Ty: Int8Ty, Ptr: DstArg, IdxList: NulOff, Name: "endptr");
3644 B.CreateStore(Val: ConstantInt::get(Ty: Int8Ty, V: 0), Ptr: DstEnd);
3645 return StrLen;
3646}
3647
3648Value *LibCallSimplifier::optimizeSnPrintFString(CallInst *CI,
3649 IRBuilderBase &B) {
3650 // Check for size
3651 ConstantInt *Size = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 1));
3652 if (!Size)
3653 return nullptr;
3654
3655 uint64_t N = Size->getZExtValue();
3656 uint64_t IntMax = maxIntN(N: TLI->getIntSize());
3657 if (N > IntMax)
3658 // Bail if the bound exceeds INT_MAX. POSIX requires implementations
3659 // to set errno to EOVERFLOW in this case.
3660 return nullptr;
3661
3662 Value *DstArg = CI->getArgOperand(i: 0);
3663 Value *FmtArg = CI->getArgOperand(i: 2);
3664
3665 // Check for a fixed format string.
3666 StringRef FormatStr;
3667 if (!getConstantStringInfo(V: FmtArg, Str&: FormatStr))
3668 return nullptr;
3669
3670 // If we just have a format string (nothing else crazy) transform it.
3671 if (CI->arg_size() == 3) {
3672 if (FormatStr.contains(C: '%'))
3673 // Bail if the format string contains a directive and there are
3674 // no arguments. We could handle "%%" in the future.
3675 return nullptr;
3676
3677 return emitSnPrintfMemCpy(CI, StrArg: FmtArg, Str: FormatStr, N, B);
3678 }
3679
3680 // The remaining optimizations require the format string to be "%s" or "%c"
3681 // and have an extra operand.
3682 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() != 4)
3683 return nullptr;
3684
3685 // Decode the second character of the format string.
3686 if (FormatStr[1] == 'c') {
3687 if (N <= 1) {
3688 // Use an arbitary string of length 1 to transform the call into
3689 // either a nul store (N == 1) or a no-op (N == 0) and fold it
3690 // to one.
3691 StringRef CharStr("*");
3692 return emitSnPrintfMemCpy(CI, StrArg: nullptr, Str: CharStr, N, B);
3693 }
3694
3695 // snprintf(dst, size, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
3696 if (!CI->getArgOperand(i: 3)->getType()->isIntegerTy())
3697 return nullptr;
3698 Value *V = B.CreateTrunc(V: CI->getArgOperand(i: 3), DestTy: B.getInt8Ty(), Name: "char");
3699 Value *Ptr = DstArg;
3700 B.CreateStore(Val: V, Ptr);
3701 Ptr = B.CreateInBoundsGEP(Ty: B.getInt8Ty(), Ptr, IdxList: B.getInt32(C: 1), Name: "nul");
3702 B.CreateStore(Val: B.getInt8(C: 0), Ptr);
3703 return ConstantInt::get(Ty: CI->getType(), V: 1);
3704 }
3705
3706 if (FormatStr[1] != 's')
3707 return nullptr;
3708
3709 Value *StrArg = CI->getArgOperand(i: 3);
3710 // snprintf(dest, size, "%s", str) to llvm.memcpy(dest, str, len+1, 1)
3711 StringRef Str;
3712 if (!getConstantStringInfo(V: StrArg, Str))
3713 return nullptr;
3714
3715 return emitSnPrintfMemCpy(CI, StrArg, Str, N, B);
3716}
3717
3718Value *LibCallSimplifier::optimizeSnPrintF(CallInst *CI, IRBuilderBase &B) {
3719 if (Value *V = optimizeSnPrintFString(CI, B)) {
3720 return V;
3721 }
3722
3723 if (isKnownNonZero(V: CI->getOperand(i_nocapture: 1), Q: DL))
3724 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos: 0);
3725 return nullptr;
3726}
3727
3728Value *LibCallSimplifier::optimizeFPrintFString(CallInst *CI,
3729 IRBuilderBase &B) {
3730 optimizeErrorReporting(CI, B, StreamArg: 0);
3731
3732 // All the optimizations depend on the format string.
3733 StringRef FormatStr;
3734 if (!getConstantStringInfo(V: CI->getArgOperand(i: 1), Str&: FormatStr))
3735 return nullptr;
3736
3737 // Do not do any of the following transformations if the fprintf return
3738 // value is used, in general the fprintf return value is not compatible
3739 // with fwrite(), fputc() or fputs().
3740 if (!CI->use_empty())
3741 return nullptr;
3742
3743 // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
3744 if (CI->arg_size() == 2) {
3745 // Could handle %% -> % if we cared.
3746 if (FormatStr.contains(C: '%'))
3747 return nullptr; // We found a format specifier.
3748
3749 return copyFlags(
3750 Old: *CI, New: emitFWrite(Ptr: CI->getArgOperand(i: 1),
3751 Size: TLI->getAsSizeT(V: FormatStr.size(), M: *CI->getModule()),
3752 File: CI->getArgOperand(i: 0), B, DL, TLI));
3753 }
3754
3755 // The remaining optimizations require the format string to be "%s" or "%c"
3756 // and have an extra operand.
3757 if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->arg_size() < 3)
3758 return nullptr;
3759
3760 // Decode the second character of the format string.
3761 if (FormatStr[1] == 'c') {
3762 // fprintf(F, "%c", chr) --> fputc((int)chr, F)
3763 if (!CI->getArgOperand(i: 2)->getType()->isIntegerTy())
3764 return nullptr;
3765 Type *IntTy = B.getIntNTy(N: TLI->getIntSize());
3766 Value *V = B.CreateIntCast(V: CI->getArgOperand(i: 2), DestTy: IntTy, /*isSigned*/ true,
3767 Name: "chari");
3768 return copyFlags(Old: *CI, New: emitFPutC(Char: V, File: CI->getArgOperand(i: 0), B, TLI));
3769 }
3770
3771 if (FormatStr[1] == 's') {
3772 // fprintf(F, "%s", str) --> fputs(str, F)
3773 if (!CI->getArgOperand(i: 2)->getType()->isPointerTy())
3774 return nullptr;
3775 return copyFlags(
3776 Old: *CI, New: emitFPutS(Str: CI->getArgOperand(i: 2), File: CI->getArgOperand(i: 0), B, TLI));
3777 }
3778 return nullptr;
3779}
3780
3781Value *LibCallSimplifier::optimizeFPrintF(CallInst *CI, IRBuilderBase &B) {
3782 Module *M = CI->getModule();
3783 Function *Callee = CI->getCalledFunction();
3784 FunctionType *FT = Callee->getFunctionType();
3785 if (Value *V = optimizeFPrintFString(CI, B)) {
3786 return V;
3787 }
3788
3789 // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
3790 // floating point arguments.
3791 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_fiprintf) &&
3792 !callHasFloatingPointArgument(CI)) {
3793 FunctionCallee FIPrintFFn = getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_fiprintf,
3794 T: FT, AttributeList: Callee->getAttributes());
3795 CallInst *New = cast<CallInst>(Val: CI->clone());
3796 New->setCalledFunction(FIPrintFFn);
3797 B.Insert(I: New);
3798 return New;
3799 }
3800
3801 // fprintf(stream, format, ...) -> __small_fprintf(stream, format, ...) if no
3802 // 128-bit floating point arguments.
3803 if (isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_small_fprintf) &&
3804 !callHasFP128Argument(CI)) {
3805 auto SmallFPrintFFn =
3806 getOrInsertLibFunc(M, TLI: *TLI, TheLibFunc: LibFunc_small_fprintf, T: FT,
3807 AttributeList: Callee->getAttributes());
3808 CallInst *New = cast<CallInst>(Val: CI->clone());
3809 New->setCalledFunction(SmallFPrintFFn);
3810 B.Insert(I: New);
3811 return New;
3812 }
3813
3814 return nullptr;
3815}
3816
3817Value *LibCallSimplifier::optimizeFWrite(CallInst *CI, IRBuilderBase &B) {
3818 optimizeErrorReporting(CI, B, StreamArg: 3);
3819
3820 // Get the element size and count.
3821 ConstantInt *SizeC = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 1));
3822 ConstantInt *CountC = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 2));
3823 if (SizeC && CountC) {
3824 uint64_t Bytes = SizeC->getZExtValue() * CountC->getZExtValue();
3825
3826 // If this is writing zero records, remove the call (it's a noop).
3827 if (Bytes == 0)
3828 return ConstantInt::get(Ty: CI->getType(), V: 0);
3829
3830 // If this is writing one byte, turn it into fputc.
3831 // This optimisation is only valid, if the return value is unused.
3832 if (Bytes == 1 && CI->use_empty()) { // fwrite(S,1,1,F) -> fputc(S[0],F)
3833 Value *Char = B.CreateLoad(Ty: B.getInt8Ty(), Ptr: CI->getArgOperand(i: 0), Name: "char");
3834 Type *IntTy = B.getIntNTy(N: TLI->getIntSize());
3835 Value *Cast = B.CreateIntCast(V: Char, DestTy: IntTy, /*isSigned*/ true, Name: "chari");
3836 Value *NewCI = emitFPutC(Char: Cast, File: CI->getArgOperand(i: 3), B, TLI);
3837 return NewCI ? ConstantInt::get(Ty: CI->getType(), V: 1) : nullptr;
3838 }
3839 }
3840
3841 return nullptr;
3842}
3843
3844Value *LibCallSimplifier::optimizeFPuts(CallInst *CI, IRBuilderBase &B) {
3845 optimizeErrorReporting(CI, B, StreamArg: 1);
3846
3847 // Don't rewrite fputs to fwrite when optimising for size because fwrite
3848 // requires more arguments and thus extra MOVs are required.
3849 if (llvm::shouldOptimizeForSize(BB: CI->getParent(), PSI, BFI,
3850 QueryType: PGSOQueryType::IRPass))
3851 return nullptr;
3852
3853 // We can't optimize if return value is used.
3854 if (!CI->use_empty())
3855 return nullptr;
3856
3857 // fputs(s,F) --> fwrite(s,strlen(s),1,F)
3858 uint64_t Len = GetStringLength(V: CI->getArgOperand(i: 0));
3859 if (!Len)
3860 return nullptr;
3861
3862 // Known to have no uses (see above).
3863 unsigned SizeTBits = TLI->getSizeTSize(M: *CI->getModule());
3864 Type *SizeTTy = IntegerType::get(C&: CI->getContext(), NumBits: SizeTBits);
3865 return copyFlags(
3866 Old: *CI,
3867 New: emitFWrite(Ptr: CI->getArgOperand(i: 0),
3868 Size: ConstantInt::get(Ty: SizeTTy, V: Len - 1),
3869 File: CI->getArgOperand(i: 1), B, DL, TLI));
3870}
3871
3872Value *LibCallSimplifier::optimizePuts(CallInst *CI, IRBuilderBase &B) {
3873 annotateNonNullNoUndefBasedOnAccess(CI, ArgNos: 0);
3874 if (!CI->use_empty())
3875 return nullptr;
3876
3877 // Check for a constant string.
3878 // puts("") -> putchar('\n')
3879 StringRef Str;
3880 if (getConstantStringInfo(V: CI->getArgOperand(i: 0), Str) && Str.empty()) {
3881 // putchar takes an argument of the same type as puts returns, i.e.,
3882 // int, which need not be 32 bits wide.
3883 Type *IntTy = CI->getType();
3884 return copyFlags(Old: *CI, New: emitPutChar(Char: ConstantInt::get(Ty: IntTy, V: '\n'), B, TLI));
3885 }
3886
3887 return nullptr;
3888}
3889
3890Value *LibCallSimplifier::optimizeExit(CallInst *CI) {
3891
3892 // Mark 'exit' as cold if its not exit(0) (success).
3893 const APInt *C;
3894 if (!CI->hasFnAttr(Kind: Attribute::Cold) &&
3895 match(V: CI->getArgOperand(i: 0), P: m_APInt(Res&: C)) && !C->isZero()) {
3896 CI->addFnAttr(Kind: Attribute::Cold);
3897 }
3898 return nullptr;
3899}
3900
3901Value *LibCallSimplifier::optimizeBCopy(CallInst *CI, IRBuilderBase &B) {
3902 // bcopy(src, dst, n) -> llvm.memmove(dst, src, n)
3903 return copyFlags(Old: *CI, New: B.CreateMemMove(Dst: CI->getArgOperand(i: 1), DstAlign: Align(1),
3904 Src: CI->getArgOperand(i: 0), SrcAlign: Align(1),
3905 Size: CI->getArgOperand(i: 2)));
3906}
3907
3908bool LibCallSimplifier::hasFloatVersion(const Module *M, StringRef FuncName) {
3909 SmallString<20> FloatFuncName = FuncName;
3910 FloatFuncName += 'f';
3911 return isLibFuncEmittable(M, TLI, Name: FloatFuncName);
3912}
3913
3914Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI,
3915 IRBuilderBase &Builder) {
3916 Module *M = CI->getModule();
3917 LibFunc Func;
3918 Function *Callee = CI->getCalledFunction();
3919
3920 // Check for string/memory library functions.
3921 if (TLI->getLibFunc(FDecl: *Callee, F&: Func) && isLibFuncEmittable(M, TLI, TheLibFunc: Func)) {
3922 // Make sure we never change the calling convention.
3923 assert(
3924 (ignoreCallingConv(Func) ||
3925 TargetLibraryInfoImpl::isCallingConvCCompatible(CI)) &&
3926 "Optimizing string/memory libcall would change the calling convention");
3927 switch (Func) {
3928 case LibFunc_strcat:
3929 return optimizeStrCat(CI, B&: Builder);
3930 case LibFunc_strncat:
3931 return optimizeStrNCat(CI, B&: Builder);
3932 case LibFunc_strchr:
3933 return optimizeStrChr(CI, B&: Builder);
3934 case LibFunc_strrchr:
3935 return optimizeStrRChr(CI, B&: Builder);
3936 case LibFunc_strcmp:
3937 return optimizeStrCmp(CI, B&: Builder);
3938 case LibFunc_strncmp:
3939 return optimizeStrNCmp(CI, B&: Builder);
3940 case LibFunc_strcpy:
3941 return optimizeStrCpy(CI, B&: Builder);
3942 case LibFunc_stpcpy:
3943 return optimizeStpCpy(CI, B&: Builder);
3944 case LibFunc_strlcpy:
3945 return optimizeStrLCpy(CI, B&: Builder);
3946 case LibFunc_stpncpy:
3947 return optimizeStringNCpy(CI, /*RetEnd=*/true, B&: Builder);
3948 case LibFunc_strncpy:
3949 return optimizeStringNCpy(CI, /*RetEnd=*/false, B&: Builder);
3950 case LibFunc_strlen:
3951 return optimizeStrLen(CI, B&: Builder);
3952 case LibFunc_strnlen:
3953 return optimizeStrNLen(CI, B&: Builder);
3954 case LibFunc_strpbrk:
3955 return optimizeStrPBrk(CI, B&: Builder);
3956 case LibFunc_strndup:
3957 return optimizeStrNDup(CI, B&: Builder);
3958 case LibFunc_strtol:
3959 case LibFunc_strtod:
3960 case LibFunc_strtof:
3961 case LibFunc_strtoul:
3962 case LibFunc_strtoll:
3963 case LibFunc_strtold:
3964 case LibFunc_strtoull:
3965 return optimizeStrTo(CI, B&: Builder);
3966 case LibFunc_strspn:
3967 return optimizeStrSpn(CI, B&: Builder);
3968 case LibFunc_strcspn:
3969 return optimizeStrCSpn(CI, B&: Builder);
3970 case LibFunc_strstr:
3971 return optimizeStrStr(CI, B&: Builder);
3972 case LibFunc_memchr:
3973 return optimizeMemChr(CI, B&: Builder);
3974 case LibFunc_memrchr:
3975 return optimizeMemRChr(CI, B&: Builder);
3976 case LibFunc_bcmp:
3977 return optimizeBCmp(CI, B&: Builder);
3978 case LibFunc_memcmp:
3979 return optimizeMemCmp(CI, B&: Builder);
3980 case LibFunc_memcpy:
3981 return optimizeMemCpy(CI, B&: Builder);
3982 case LibFunc_memccpy:
3983 return optimizeMemCCpy(CI, B&: Builder);
3984 case LibFunc_mempcpy:
3985 return optimizeMemPCpy(CI, B&: Builder);
3986 case LibFunc_memmove:
3987 return optimizeMemMove(CI, B&: Builder);
3988 case LibFunc_memset:
3989 return optimizeMemSet(CI, B&: Builder);
3990 case LibFunc_realloc:
3991 return optimizeRealloc(CI, B&: Builder);
3992 case LibFunc_wcslen:
3993 return optimizeWcslen(CI, B&: Builder);
3994 case LibFunc_bcopy:
3995 return optimizeBCopy(CI, B&: Builder);
3996 case LibFunc_Znwm:
3997 case LibFunc_ZnwmRKSt9nothrow_t:
3998 case LibFunc_ZnwmSt11align_val_t:
3999 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t:
4000 case LibFunc_Znam:
4001 case LibFunc_ZnamRKSt9nothrow_t:
4002 case LibFunc_ZnamSt11align_val_t:
4003 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t:
4004 case LibFunc_Znwm12__hot_cold_t:
4005 case LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t:
4006 case LibFunc_ZnwmSt11align_val_t12__hot_cold_t:
4007 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t:
4008 case LibFunc_Znam12__hot_cold_t:
4009 case LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t:
4010 case LibFunc_ZnamSt11align_val_t12__hot_cold_t:
4011 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t:
4012 case LibFunc_size_returning_new:
4013 case LibFunc_size_returning_new_hot_cold:
4014 case LibFunc_size_returning_new_aligned:
4015 case LibFunc_size_returning_new_aligned_hot_cold:
4016 return optimizeNew(CI, B&: Builder, Func);
4017 default:
4018 break;
4019 }
4020 }
4021 return nullptr;
4022}
4023
4024/// Constant folding nan/nanf/nanl.
4025static Value *optimizeNaN(CallInst *CI) {
4026 StringRef CharSeq;
4027 if (!getConstantStringInfo(V: CI->getArgOperand(i: 0), Str&: CharSeq))
4028 return nullptr;
4029
4030 APInt Fill;
4031 // Treat empty strings as if they were zero.
4032 if (CharSeq.empty())
4033 Fill = APInt(32, 0);
4034 else if (CharSeq.getAsInteger(Radix: 0, Result&: Fill))
4035 return nullptr;
4036
4037 return ConstantFP::getQNaN(Ty: CI->getType(), /*Negative=*/false, Payload: &Fill);
4038}
4039
4040Value *LibCallSimplifier::optimizeFloatingPointLibCall(CallInst *CI,
4041 LibFunc Func,
4042 IRBuilderBase &Builder) {
4043 const Module *M = CI->getModule();
4044
4045 // Don't optimize calls that require strict floating point semantics.
4046 if (CI->isStrictFP())
4047 return nullptr;
4048
4049 if (Value *V = optimizeSymmetric(CI, Func, B&: Builder))
4050 return V;
4051
4052 switch (Func) {
4053 case LibFunc_sinpif:
4054 case LibFunc_sinpi:
4055 return optimizeSinCosPi(CI, /*IsSin*/true, B&: Builder);
4056 case LibFunc_cospif:
4057 case LibFunc_cospi:
4058 return optimizeSinCosPi(CI, /*IsSin*/false, B&: Builder);
4059 case LibFunc_powf:
4060 case LibFunc_pow:
4061 case LibFunc_powl:
4062 return optimizePow(Pow: CI, B&: Builder);
4063 case LibFunc_exp2l:
4064 case LibFunc_exp2:
4065 case LibFunc_exp2f:
4066 return optimizeExp2(CI, B&: Builder);
4067 case LibFunc_fabsf:
4068 case LibFunc_fabs:
4069 case LibFunc_fabsl:
4070 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::fabs);
4071 case LibFunc_sqrtf:
4072 case LibFunc_sqrt:
4073 case LibFunc_sqrtl:
4074 return optimizeSqrt(CI, B&: Builder);
4075 case LibFunc_fmod:
4076 case LibFunc_fmodf:
4077 case LibFunc_fmodl:
4078 return optimizeFMod(CI, B&: Builder);
4079 case LibFunc_logf:
4080 case LibFunc_log:
4081 case LibFunc_logl:
4082 case LibFunc_log10f:
4083 case LibFunc_log10:
4084 case LibFunc_log10l:
4085 case LibFunc_log1pf:
4086 case LibFunc_log1p:
4087 case LibFunc_log1pl:
4088 case LibFunc_log2f:
4089 case LibFunc_log2:
4090 case LibFunc_log2l:
4091 case LibFunc_logbf:
4092 case LibFunc_logb:
4093 case LibFunc_logbl:
4094 return optimizeLog(Log: CI, B&: Builder);
4095 case LibFunc_tan:
4096 case LibFunc_tanf:
4097 case LibFunc_tanl:
4098 case LibFunc_sinh:
4099 case LibFunc_sinhf:
4100 case LibFunc_sinhl:
4101 case LibFunc_asinh:
4102 case LibFunc_asinhf:
4103 case LibFunc_asinhl:
4104 case LibFunc_cosh:
4105 case LibFunc_coshf:
4106 case LibFunc_coshl:
4107 case LibFunc_atanh:
4108 case LibFunc_atanhf:
4109 case LibFunc_atanhl:
4110 return optimizeTrigInversionPairs(CI, B&: Builder);
4111 case LibFunc_ceil:
4112 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::ceil);
4113 case LibFunc_floor:
4114 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::floor);
4115 case LibFunc_round:
4116 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::round);
4117 case LibFunc_roundeven:
4118 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::roundeven);
4119 case LibFunc_nearbyint:
4120 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::nearbyint);
4121 case LibFunc_rint:
4122 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::rint);
4123 case LibFunc_trunc:
4124 return replaceUnaryCall(CI, B&: Builder, IID: Intrinsic::trunc);
4125 case LibFunc_acos:
4126 case LibFunc_acosh:
4127 case LibFunc_asin:
4128 case LibFunc_atan:
4129 case LibFunc_cbrt:
4130 case LibFunc_exp:
4131 case LibFunc_exp10:
4132 case LibFunc_expm1:
4133 case LibFunc_cos:
4134 case LibFunc_sin:
4135 case LibFunc_tanh:
4136 if (UnsafeFPShrink && hasFloatVersion(M, FuncName: CI->getCalledFunction()->getName()))
4137 return optimizeUnaryDoubleFP(CI, B&: Builder, TLI, isPrecise: true);
4138 return nullptr;
4139 case LibFunc_copysign:
4140 if (hasFloatVersion(M, FuncName: CI->getCalledFunction()->getName()))
4141 return optimizeBinaryDoubleFP(CI, B&: Builder, TLI);
4142 return nullptr;
4143 case LibFunc_fdim:
4144 case LibFunc_fdimf:
4145 case LibFunc_fdiml:
4146 return optimizeFdim(CI, B&: Builder);
4147 case LibFunc_fminf:
4148 case LibFunc_fmin:
4149 case LibFunc_fminl:
4150 case LibFunc_fmaxf:
4151 case LibFunc_fmax:
4152 case LibFunc_fmaxl:
4153 return optimizeFMinFMax(CI, B&: Builder);
4154 case LibFunc_fminimum_numf:
4155 case LibFunc_fminimum_num:
4156 case LibFunc_fminimum_numl:
4157 case LibFunc_fmaximum_numf:
4158 case LibFunc_fmaximum_num:
4159 case LibFunc_fmaximum_numl:
4160 return optimizeFMinimumnumFMaximumnum(CI, B&: Builder);
4161 case LibFunc_cabs:
4162 case LibFunc_cabsf:
4163 case LibFunc_cabsl:
4164 return optimizeCAbs(CI, B&: Builder);
4165 case LibFunc_remquo:
4166 case LibFunc_remquof:
4167 case LibFunc_remquol:
4168 return optimizeRemquo(CI, B&: Builder);
4169 case LibFunc_nan:
4170 case LibFunc_nanf:
4171 case LibFunc_nanl:
4172 return optimizeNaN(CI);
4173 default:
4174 return nullptr;
4175 }
4176}
4177
4178Value *LibCallSimplifier::optimizeCall(CallInst *CI, IRBuilderBase &Builder) {
4179 Module *M = CI->getModule();
4180 assert(!CI->isMustTailCall() && "These transforms aren't musttail safe.");
4181
4182 // TODO: Split out the code below that operates on FP calls so that
4183 // we can all non-FP calls with the StrictFP attribute to be
4184 // optimized.
4185 if (CI->isNoBuiltin()) {
4186 // Optionally update operator new calls.
4187 return maybeOptimizeNoBuiltinOperatorNew(CI, B&: Builder);
4188 }
4189
4190 LibFunc Func;
4191 Function *Callee = CI->getCalledFunction();
4192 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI);
4193
4194 SmallVector<OperandBundleDef, 2> OpBundles;
4195 CI->getOperandBundlesAsDefs(Defs&: OpBundles);
4196
4197 IRBuilderBase::OperandBundlesGuard Guard(Builder);
4198 Builder.setDefaultOperandBundles(OpBundles);
4199
4200 // Command-line parameter overrides instruction attribute.
4201 // This can't be moved to optimizeFloatingPointLibCall() because it may be
4202 // used by the intrinsic optimizations.
4203 if (EnableUnsafeFPShrink.getNumOccurrences() > 0)
4204 UnsafeFPShrink = EnableUnsafeFPShrink;
4205 else if (isa<FPMathOperator>(Val: CI) && CI->isFast())
4206 UnsafeFPShrink = true;
4207
4208 // First, check for intrinsics.
4209 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: CI)) {
4210 if (!IsCallingConvC)
4211 return nullptr;
4212 // The FP intrinsics have corresponding constrained versions so we don't
4213 // need to check for the StrictFP attribute here.
4214 switch (II->getIntrinsicID()) {
4215 case Intrinsic::pow:
4216 return optimizePow(Pow: CI, B&: Builder);
4217 case Intrinsic::exp2:
4218 return optimizeExp2(CI, B&: Builder);
4219 case Intrinsic::log:
4220 case Intrinsic::log2:
4221 case Intrinsic::log10:
4222 return optimizeLog(Log: CI, B&: Builder);
4223 case Intrinsic::sqrt:
4224 return optimizeSqrt(CI, B&: Builder);
4225 case Intrinsic::memset:
4226 return optimizeMemSet(CI, B&: Builder);
4227 case Intrinsic::memcpy:
4228 return optimizeMemCpy(CI, B&: Builder);
4229 case Intrinsic::memmove:
4230 return optimizeMemMove(CI, B&: Builder);
4231 case Intrinsic::sin:
4232 case Intrinsic::cos:
4233 if (UnsafeFPShrink)
4234 return optimizeUnaryDoubleFP(CI, B&: Builder, TLI, /*isPrecise=*/true);
4235 return nullptr;
4236 default:
4237 return nullptr;
4238 }
4239 }
4240
4241 // Also try to simplify calls to fortified library functions.
4242 if (Value *SimplifiedFortifiedCI =
4243 FortifiedSimplifier.optimizeCall(CI, B&: Builder))
4244 return SimplifiedFortifiedCI;
4245
4246 // Then check for known library functions.
4247 if (TLI->getLibFunc(FDecl: *Callee, F&: Func) && isLibFuncEmittable(M, TLI, TheLibFunc: Func)) {
4248 // We never change the calling convention.
4249 if (!ignoreCallingConv(Func) && !IsCallingConvC)
4250 return nullptr;
4251 if (Value *V = optimizeStringMemoryLibCall(CI, Builder))
4252 return V;
4253 if (Value *V = optimizeFloatingPointLibCall(CI, Func, Builder))
4254 return V;
4255 switch (Func) {
4256 case LibFunc_ffs:
4257 case LibFunc_ffsl:
4258 case LibFunc_ffsll:
4259 return optimizeFFS(CI, B&: Builder);
4260 case LibFunc_fls:
4261 case LibFunc_flsl:
4262 case LibFunc_flsll:
4263 return optimizeFls(CI, B&: Builder);
4264 case LibFunc_abs:
4265 case LibFunc_labs:
4266 case LibFunc_llabs:
4267 return optimizeAbs(CI, B&: Builder);
4268 case LibFunc_isdigit:
4269 return optimizeIsDigit(CI, B&: Builder);
4270 case LibFunc_isascii:
4271 return optimizeIsAscii(CI, B&: Builder);
4272 case LibFunc_toascii:
4273 return optimizeToAscii(CI, B&: Builder);
4274 case LibFunc_atoi:
4275 case LibFunc_atol:
4276 case LibFunc_atoll:
4277 return optimizeAtoi(CI, B&: Builder);
4278 case LibFunc_strtol:
4279 case LibFunc_strtoll:
4280 return optimizeStrToInt(CI, B&: Builder, /*AsSigned=*/true);
4281 case LibFunc_strtoul:
4282 case LibFunc_strtoull:
4283 return optimizeStrToInt(CI, B&: Builder, /*AsSigned=*/false);
4284 case LibFunc_printf:
4285 return optimizePrintF(CI, B&: Builder);
4286 case LibFunc_sprintf:
4287 return optimizeSPrintF(CI, B&: Builder);
4288 case LibFunc_snprintf:
4289 return optimizeSnPrintF(CI, B&: Builder);
4290 case LibFunc_fprintf:
4291 return optimizeFPrintF(CI, B&: Builder);
4292 case LibFunc_fwrite:
4293 return optimizeFWrite(CI, B&: Builder);
4294 case LibFunc_fputs:
4295 return optimizeFPuts(CI, B&: Builder);
4296 case LibFunc_puts:
4297 return optimizePuts(CI, B&: Builder);
4298 case LibFunc_perror:
4299 return optimizeErrorReporting(CI, B&: Builder);
4300 case LibFunc_vfprintf:
4301 case LibFunc_fiprintf:
4302 return optimizeErrorReporting(CI, B&: Builder, StreamArg: 0);
4303 case LibFunc_exit:
4304 case LibFunc_Exit:
4305 return optimizeExit(CI);
4306 default:
4307 return nullptr;
4308 }
4309 }
4310 return nullptr;
4311}
4312
4313LibCallSimplifier::LibCallSimplifier(
4314 const DataLayout &DL, const TargetLibraryInfo *TLI, DominatorTree *DT,
4315 DomConditionCache *DC, AssumptionCache *AC, OptimizationRemarkEmitter &ORE,
4316 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
4317 function_ref<void(Instruction *, Value *)> Replacer,
4318 function_ref<void(Instruction *)> Eraser)
4319 : FortifiedSimplifier(TLI), DL(DL), TLI(TLI), DT(DT), DC(DC), AC(AC),
4320 ORE(ORE), BFI(BFI), PSI(PSI), Replacer(Replacer), Eraser(Eraser) {}
4321
4322void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) {
4323 // Indirect through the replacer used in this instance.
4324 Replacer(I, With);
4325}
4326
4327void LibCallSimplifier::eraseFromParent(Instruction *I) {
4328 Eraser(I);
4329}
4330
4331// TODO:
4332// Additional cases that we need to add to this file:
4333//
4334// cbrt:
4335// * cbrt(expN(X)) -> expN(x/3)
4336// * cbrt(sqrt(x)) -> pow(x,1/6)
4337// * cbrt(cbrt(x)) -> pow(x,1/9)
4338//
4339// exp, expf, expl:
4340// * exp(log(x)) -> x
4341//
4342// log, logf, logl:
4343// * log(exp(x)) -> x
4344// * log(exp(y)) -> y*log(e)
4345// * log(exp10(y)) -> y*log(10)
4346// * log(sqrt(x)) -> 0.5*log(x)
4347//
4348// pow, powf, powl:
4349// * pow(sqrt(x),y) -> pow(x,y*0.5)
4350// * pow(pow(x,y),z)-> pow(x,y*z)
4351//
4352// signbit:
4353// * signbit(cnst) -> cnst'
4354// * signbit(nncst) -> 0 (if pstv is a non-negative constant)
4355//
4356// sqrt, sqrtf, sqrtl:
4357// * sqrt(expN(x)) -> expN(x*0.5)
4358// * sqrt(Nroot(x)) -> pow(x,1/(2*N))
4359// * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
4360//
4361
4362//===----------------------------------------------------------------------===//
4363// Fortified Library Call Optimizations
4364//===----------------------------------------------------------------------===//
4365
4366bool FortifiedLibCallSimplifier::isFortifiedCallFoldable(
4367 CallInst *CI, unsigned ObjSizeOp, std::optional<unsigned> SizeOp,
4368 std::optional<unsigned> StrOp, std::optional<unsigned> FlagOp) {
4369 // If this function takes a flag argument, the implementation may use it to
4370 // perform extra checks. Don't fold into the non-checking variant.
4371 if (FlagOp) {
4372 ConstantInt *Flag = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: *FlagOp));
4373 if (!Flag || !Flag->isZero())
4374 return false;
4375 }
4376
4377 if (SizeOp && CI->getArgOperand(i: ObjSizeOp) == CI->getArgOperand(i: *SizeOp))
4378 return true;
4379
4380 if (ConstantInt *ObjSizeCI =
4381 dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: ObjSizeOp))) {
4382 if (ObjSizeCI->isMinusOne())
4383 return true;
4384 // If the object size wasn't -1 (unknown), bail out if we were asked to.
4385 if (OnlyLowerUnknownSize)
4386 return false;
4387 if (StrOp) {
4388 uint64_t Len = GetStringLength(V: CI->getArgOperand(i: *StrOp));
4389 // If the length is 0 we don't know how long it is and so we can't
4390 // remove the check.
4391 if (Len)
4392 annotateDereferenceableBytes(CI, ArgNos: *StrOp, DereferenceableBytes: Len);
4393 else
4394 return false;
4395 return ObjSizeCI->getZExtValue() >= Len;
4396 }
4397
4398 if (SizeOp) {
4399 if (ConstantInt *SizeCI =
4400 dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: *SizeOp)))
4401 return ObjSizeCI->getZExtValue() >= SizeCI->getZExtValue();
4402 }
4403 }
4404 return false;
4405}
4406
4407Value *FortifiedLibCallSimplifier::optimizeMemCpyChk(CallInst *CI,
4408 IRBuilderBase &B) {
4409 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 2)) {
4410 CallInst *NewCI =
4411 B.CreateMemCpy(Dst: CI->getArgOperand(i: 0), DstAlign: Align(1), Src: CI->getArgOperand(i: 1),
4412 SrcAlign: Align(1), Size: CI->getArgOperand(i: 2));
4413 mergeAttributesAndFlags(NewCI, Old: *CI);
4414 return CI->getArgOperand(i: 0);
4415 }
4416 return nullptr;
4417}
4418
4419Value *FortifiedLibCallSimplifier::optimizeMemMoveChk(CallInst *CI,
4420 IRBuilderBase &B) {
4421 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 2)) {
4422 CallInst *NewCI =
4423 B.CreateMemMove(Dst: CI->getArgOperand(i: 0), DstAlign: Align(1), Src: CI->getArgOperand(i: 1),
4424 SrcAlign: Align(1), Size: CI->getArgOperand(i: 2));
4425 mergeAttributesAndFlags(NewCI, Old: *CI);
4426 return CI->getArgOperand(i: 0);
4427 }
4428 return nullptr;
4429}
4430
4431Value *FortifiedLibCallSimplifier::optimizeMemSetChk(CallInst *CI,
4432 IRBuilderBase &B) {
4433 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 2)) {
4434 Value *Val = B.CreateIntCast(V: CI->getArgOperand(i: 1), DestTy: B.getInt8Ty(), isSigned: false);
4435 CallInst *NewCI = B.CreateMemSet(Ptr: CI->getArgOperand(i: 0), Val,
4436 Size: CI->getArgOperand(i: 2), Align: Align(1));
4437 mergeAttributesAndFlags(NewCI, Old: *CI);
4438 return CI->getArgOperand(i: 0);
4439 }
4440 return nullptr;
4441}
4442
4443Value *FortifiedLibCallSimplifier::optimizeMemPCpyChk(CallInst *CI,
4444 IRBuilderBase &B) {
4445 const DataLayout &DL = CI->getDataLayout();
4446 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 2))
4447 if (Value *Call = emitMemPCpy(Dst: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4448 Len: CI->getArgOperand(i: 2), B, DL, TLI)) {
4449 return mergeAttributesAndFlags(NewCI: cast<CallInst>(Val: Call), Old: *CI);
4450 }
4451 return nullptr;
4452}
4453
4454Value *FortifiedLibCallSimplifier::optimizeStrpCpyChk(CallInst *CI,
4455 IRBuilderBase &B,
4456 LibFunc Func) {
4457 const DataLayout &DL = CI->getDataLayout();
4458 Value *Dst = CI->getArgOperand(i: 0), *Src = CI->getArgOperand(i: 1),
4459 *ObjSize = CI->getArgOperand(i: 2);
4460
4461 // __stpcpy_chk(x,x,...) -> x+strlen(x)
4462 if (Func == LibFunc_stpcpy_chk && !OnlyLowerUnknownSize && Dst == Src) {
4463 Value *StrLen = emitStrLen(Ptr: Src, B, DL, TLI);
4464 return StrLen ? B.CreateInBoundsGEP(Ty: B.getInt8Ty(), Ptr: Dst, IdxList: StrLen) : nullptr;
4465 }
4466
4467 // If a) we don't have any length information, or b) we know this will
4468 // fit then just lower to a plain st[rp]cpy. Otherwise we'll keep our
4469 // st[rp]cpy_chk call which may fail at runtime if the size is too long.
4470 // TODO: It might be nice to get a maximum length out of the possible
4471 // string lengths for varying.
4472 if (isFortifiedCallFoldable(CI, ObjSizeOp: 2, SizeOp: std::nullopt, StrOp: 1)) {
4473 if (Func == LibFunc_strcpy_chk)
4474 return copyFlags(Old: *CI, New: emitStrCpy(Dst, Src, B, TLI));
4475 else
4476 return copyFlags(Old: *CI, New: emitStpCpy(Dst, Src, B, TLI));
4477 }
4478
4479 if (OnlyLowerUnknownSize)
4480 return nullptr;
4481
4482 // Maybe we can stil fold __st[rp]cpy_chk to __memcpy_chk.
4483 uint64_t Len = GetStringLength(V: Src);
4484 if (Len)
4485 annotateDereferenceableBytes(CI, ArgNos: 1, DereferenceableBytes: Len);
4486 else
4487 return nullptr;
4488
4489 unsigned SizeTBits = TLI->getSizeTSize(M: *CI->getModule());
4490 Type *SizeTTy = IntegerType::get(C&: CI->getContext(), NumBits: SizeTBits);
4491 Value *LenV = ConstantInt::get(Ty: SizeTTy, V: Len);
4492 Value *Ret = emitMemCpyChk(Dst, Src, Len: LenV, ObjSize, B, DL, TLI);
4493 // If the function was an __stpcpy_chk, and we were able to fold it into
4494 // a __memcpy_chk, we still need to return the correct end pointer.
4495 if (Ret && Func == LibFunc_stpcpy_chk)
4496 return B.CreateInBoundsGEP(Ty: B.getInt8Ty(), Ptr: Dst,
4497 IdxList: ConstantInt::get(Ty: SizeTTy, V: Len - 1));
4498 return copyFlags(Old: *CI, New: cast<CallInst>(Val: Ret));
4499}
4500
4501Value *FortifiedLibCallSimplifier::optimizeStrLenChk(CallInst *CI,
4502 IRBuilderBase &B) {
4503 if (isFortifiedCallFoldable(CI, ObjSizeOp: 1, SizeOp: std::nullopt, StrOp: 0))
4504 return copyFlags(Old: *CI, New: emitStrLen(Ptr: CI->getArgOperand(i: 0), B,
4505 DL: CI->getDataLayout(), TLI));
4506 return nullptr;
4507}
4508
4509Value *FortifiedLibCallSimplifier::optimizeStrpNCpyChk(CallInst *CI,
4510 IRBuilderBase &B,
4511 LibFunc Func) {
4512 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 2)) {
4513 if (Func == LibFunc_strncpy_chk)
4514 return copyFlags(Old: *CI,
4515 New: emitStrNCpy(Dst: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4516 Len: CI->getArgOperand(i: 2), B, TLI));
4517 else
4518 return copyFlags(Old: *CI,
4519 New: emitStpNCpy(Dst: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4520 Len: CI->getArgOperand(i: 2), B, TLI));
4521 }
4522
4523 return nullptr;
4524}
4525
4526Value *FortifiedLibCallSimplifier::optimizeMemCCpyChk(CallInst *CI,
4527 IRBuilderBase &B) {
4528 if (isFortifiedCallFoldable(CI, ObjSizeOp: 4, SizeOp: 3))
4529 return copyFlags(
4530 Old: *CI, New: emitMemCCpy(Ptr1: CI->getArgOperand(i: 0), Ptr2: CI->getArgOperand(i: 1),
4531 Val: CI->getArgOperand(i: 2), Len: CI->getArgOperand(i: 3), B, TLI));
4532
4533 return nullptr;
4534}
4535
4536Value *FortifiedLibCallSimplifier::optimizeSNPrintfChk(CallInst *CI,
4537 IRBuilderBase &B) {
4538 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 1, StrOp: std::nullopt, FlagOp: 2)) {
4539 SmallVector<Value *, 8> VariadicArgs(drop_begin(RangeOrContainer: CI->args(), N: 5));
4540 return copyFlags(Old: *CI,
4541 New: emitSNPrintf(Dest: CI->getArgOperand(i: 0), Size: CI->getArgOperand(i: 1),
4542 Fmt: CI->getArgOperand(i: 4), Args: VariadicArgs, B, TLI));
4543 }
4544
4545 return nullptr;
4546}
4547
4548Value *FortifiedLibCallSimplifier::optimizeSPrintfChk(CallInst *CI,
4549 IRBuilderBase &B) {
4550 if (isFortifiedCallFoldable(CI, ObjSizeOp: 2, SizeOp: std::nullopt, StrOp: std::nullopt, FlagOp: 1)) {
4551 SmallVector<Value *, 8> VariadicArgs(drop_begin(RangeOrContainer: CI->args(), N: 4));
4552 return copyFlags(Old: *CI,
4553 New: emitSPrintf(Dest: CI->getArgOperand(i: 0), Fmt: CI->getArgOperand(i: 3),
4554 VariadicArgs, B, TLI));
4555 }
4556
4557 return nullptr;
4558}
4559
4560Value *FortifiedLibCallSimplifier::optimizeStrCatChk(CallInst *CI,
4561 IRBuilderBase &B) {
4562 if (isFortifiedCallFoldable(CI, ObjSizeOp: 2))
4563 return copyFlags(
4564 Old: *CI, New: emitStrCat(Dest: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1), B, TLI));
4565
4566 return nullptr;
4567}
4568
4569Value *FortifiedLibCallSimplifier::optimizeStrLCat(CallInst *CI,
4570 IRBuilderBase &B) {
4571 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3))
4572 return copyFlags(Old: *CI,
4573 New: emitStrLCat(Dest: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4574 Size: CI->getArgOperand(i: 2), B, TLI));
4575
4576 return nullptr;
4577}
4578
4579Value *FortifiedLibCallSimplifier::optimizeStrNCatChk(CallInst *CI,
4580 IRBuilderBase &B) {
4581 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3))
4582 return copyFlags(Old: *CI,
4583 New: emitStrNCat(Dest: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4584 Size: CI->getArgOperand(i: 2), B, TLI));
4585
4586 return nullptr;
4587}
4588
4589Value *FortifiedLibCallSimplifier::optimizeStrLCpyChk(CallInst *CI,
4590 IRBuilderBase &B) {
4591 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3))
4592 return copyFlags(Old: *CI,
4593 New: emitStrLCpy(Dest: CI->getArgOperand(i: 0), Src: CI->getArgOperand(i: 1),
4594 Size: CI->getArgOperand(i: 2), B, TLI));
4595
4596 return nullptr;
4597}
4598
4599Value *FortifiedLibCallSimplifier::optimizeVSNPrintfChk(CallInst *CI,
4600 IRBuilderBase &B) {
4601 if (isFortifiedCallFoldable(CI, ObjSizeOp: 3, SizeOp: 1, StrOp: std::nullopt, FlagOp: 2))
4602 return copyFlags(
4603 Old: *CI, New: emitVSNPrintf(Dest: CI->getArgOperand(i: 0), Size: CI->getArgOperand(i: 1),
4604 Fmt: CI->getArgOperand(i: 4), VAList: CI->getArgOperand(i: 5), B, TLI));
4605
4606 return nullptr;
4607}
4608
4609Value *FortifiedLibCallSimplifier::optimizeVSPrintfChk(CallInst *CI,
4610 IRBuilderBase &B) {
4611 if (isFortifiedCallFoldable(CI, ObjSizeOp: 2, SizeOp: std::nullopt, StrOp: std::nullopt, FlagOp: 1))
4612 return copyFlags(Old: *CI,
4613 New: emitVSPrintf(Dest: CI->getArgOperand(i: 0), Fmt: CI->getArgOperand(i: 3),
4614 VAList: CI->getArgOperand(i: 4), B, TLI));
4615
4616 return nullptr;
4617}
4618
4619Value *FortifiedLibCallSimplifier::optimizeCall(CallInst *CI,
4620 IRBuilderBase &Builder) {
4621 // FIXME: We shouldn't be changing "nobuiltin" or TLI unavailable calls here.
4622 // Some clang users checked for _chk libcall availability using:
4623 // __has_builtin(__builtin___memcpy_chk)
4624 // When compiling with -fno-builtin, this is always true.
4625 // When passing -ffreestanding/-mkernel, which both imply -fno-builtin, we
4626 // end up with fortified libcalls, which isn't acceptable in a freestanding
4627 // environment which only provides their non-fortified counterparts.
4628 //
4629 // Until we change clang and/or teach external users to check for availability
4630 // differently, disregard the "nobuiltin" attribute and TLI::has.
4631 //
4632 // PR23093.
4633
4634 LibFunc Func;
4635 Function *Callee = CI->getCalledFunction();
4636 bool IsCallingConvC = TargetLibraryInfoImpl::isCallingConvCCompatible(CI);
4637
4638 SmallVector<OperandBundleDef, 2> OpBundles;
4639 CI->getOperandBundlesAsDefs(Defs&: OpBundles);
4640
4641 IRBuilderBase::OperandBundlesGuard Guard(Builder);
4642 Builder.setDefaultOperandBundles(OpBundles);
4643
4644 // First, check that this is a known library functions and that the prototype
4645 // is correct.
4646 if (!TLI->getLibFunc(FDecl: *Callee, F&: Func))
4647 return nullptr;
4648
4649 // We never change the calling convention.
4650 if (!ignoreCallingConv(Func) && !IsCallingConvC)
4651 return nullptr;
4652
4653 switch (Func) {
4654 case LibFunc_memcpy_chk:
4655 return optimizeMemCpyChk(CI, B&: Builder);
4656 case LibFunc_mempcpy_chk:
4657 return optimizeMemPCpyChk(CI, B&: Builder);
4658 case LibFunc_memmove_chk:
4659 return optimizeMemMoveChk(CI, B&: Builder);
4660 case LibFunc_memset_chk:
4661 return optimizeMemSetChk(CI, B&: Builder);
4662 case LibFunc_stpcpy_chk:
4663 case LibFunc_strcpy_chk:
4664 return optimizeStrpCpyChk(CI, B&: Builder, Func);
4665 case LibFunc_strlen_chk:
4666 return optimizeStrLenChk(CI, B&: Builder);
4667 case LibFunc_stpncpy_chk:
4668 case LibFunc_strncpy_chk:
4669 return optimizeStrpNCpyChk(CI, B&: Builder, Func);
4670 case LibFunc_memccpy_chk:
4671 return optimizeMemCCpyChk(CI, B&: Builder);
4672 case LibFunc_snprintf_chk:
4673 return optimizeSNPrintfChk(CI, B&: Builder);
4674 case LibFunc_sprintf_chk:
4675 return optimizeSPrintfChk(CI, B&: Builder);
4676 case LibFunc_strcat_chk:
4677 return optimizeStrCatChk(CI, B&: Builder);
4678 case LibFunc_strlcat_chk:
4679 return optimizeStrLCat(CI, B&: Builder);
4680 case LibFunc_strncat_chk:
4681 return optimizeStrNCatChk(CI, B&: Builder);
4682 case LibFunc_strlcpy_chk:
4683 return optimizeStrLCpyChk(CI, B&: Builder);
4684 case LibFunc_vsnprintf_chk:
4685 return optimizeVSNPrintfChk(CI, B&: Builder);
4686 case LibFunc_vsprintf_chk:
4687 return optimizeVSPrintfChk(CI, B&: Builder);
4688 default:
4689 break;
4690 }
4691 return nullptr;
4692}
4693
4694FortifiedLibCallSimplifier::FortifiedLibCallSimplifier(
4695 const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize)
4696 : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}
4697