1//===--- ExpandMemCmp.cpp - Expand memcmp() to load/stores ----------------===//
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 pass tries to expand memcmp() calls into optimally-sized loads and
10// compares for the target.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Scalar/ExpandMemCmp.h"
15#include "ScalarOptions.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/ConstantFolding.h"
18#include "llvm/Analysis/DomTreeUpdater.h"
19#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
20#include "llvm/Analysis/ProfileSummaryInfo.h"
21#include "llvm/Analysis/TargetLibraryInfo.h"
22#include "llvm/Analysis/TargetTransformInfo.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/IR/Dominators.h"
25#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/InstIterator.h"
27#include "llvm/IR/PatternMatch.h"
28#include "llvm/IR/ProfDataUtils.h"
29#include "llvm/Transforms/Utils/BasicBlockUtils.h"
30#include "llvm/Transforms/Utils/Local.h"
31#include "llvm/Transforms/Utils/SizeOpts.h"
32#include <optional>
33
34using namespace llvm;
35using namespace llvm::PatternMatch;
36
37#define DEBUG_TYPE "expand-memcmp"
38
39STATISTIC(NumMemCmpCalls, "Number of memcmp calls");
40STATISTIC(NumMemCmpNotConstant, "Number of memcmp calls without constant size");
41STATISTIC(NumMemCmpGreaterThanMax,
42 "Number of memcmp calls with size greater than max size");
43STATISTIC(NumMemCmpInlined, "Number of inlined memcmp calls");
44
45namespace {
46
47// Return the known alignment of the pointer argument \p ArgNo of \p CI,
48// combining the alignment of the underlying pointer value with any align
49// attribute on the call site itself.
50static Align getMemCmpArgAlignment(const CallInst *CI, unsigned ArgNo,
51 const DataLayout &DL) {
52 Align A = CI->getArgOperand(i: ArgNo)->getPointerAlignment(DL);
53 if (MaybeAlign ParamAlign = CI->getParamAlign(ArgNo))
54 A = std::max(a: A, b: *ParamAlign);
55 return A;
56}
57
58// This class provides helper functions to expand a memcmp library call into an
59// inline expansion.
60class MemCmpExpansion {
61 struct LoadPair {
62 Value *Lhs = nullptr;
63 Value *Rhs = nullptr;
64 };
65
66 struct ResultBlock {
67 BasicBlock *BB = nullptr;
68 PHINode *PhiSrc1 = nullptr;
69 PHINode *PhiSrc2 = nullptr;
70
71 ResultBlock() = default;
72 };
73
74 CallInst *const CI = nullptr;
75 ResultBlock ResBlock;
76 const uint64_t Size;
77 unsigned MaxLoadSize = 0;
78 const uint64_t NumLoadsPerBlock;
79 const unsigned MaxBytesPerBlock;
80 unsigned MaxBlockSize = 0;
81 std::vector<BasicBlock *> LoadCmpBlocks;
82 BasicBlock *EndBlock = nullptr;
83 PHINode *PhiRes = nullptr;
84 const bool IsUsedForZeroCmp;
85 const DataLayout &DL;
86 const TargetTransformInfo &TTI;
87 // The known common alignment of the two source pointers.
88 const Align CommonAlign;
89 DomTreeUpdater *DTU = nullptr;
90 IRBuilder<> Builder;
91 // Represents the decomposition in blocks of the expansion. For example,
92 // comparing 33 bytes on X86+sse can be done with 2x16-byte loads and
93 // 1x1-byte load, which would be represented as [{16, 0}, {16, 16}, {1, 32}.
94 struct LoadEntry {
95 LoadEntry(unsigned LoadSize, uint64_t Offset)
96 : LoadSize(LoadSize), Offset(Offset) {
97 }
98
99 // The size of the load for this block, in bytes.
100 unsigned LoadSize;
101 // The offset of this load from the base pointer, in bytes.
102 uint64_t Offset;
103 };
104 using LoadEntryVector = SmallVector<LoadEntry, 8>;
105 LoadEntryVector LoadSequence;
106
107 void createLoadCmpBlocks();
108 void createResultBlock();
109 void setupResultBlockPHINodes();
110 void setupEndBlockPHINodes();
111 Value *getCompareLoadPairs(unsigned BlockIndex, unsigned &LoadIndex);
112 LoadPair getPackedLoadPair(unsigned BlockIndex, unsigned &LoadIndex);
113 void emitLoadCompareBlock(unsigned BlockIndex, unsigned &LoadIndex);
114 void emitLoadCompareBlockMultipleLoads(unsigned BlockIndex,
115 unsigned &LoadIndex);
116 void emitLoadCompareByteBlock(unsigned BlockIndex, unsigned OffsetBytes);
117 void emitMemCmpResultBlock();
118 Value *getMemCmpExpansionZeroCase();
119 Value *getMemCmpEqZeroOneBlock();
120 Value *getMemCmpOneBlock();
121 Value *getMemCmpOneBlockMultipleLoads();
122 Value *getMemCmpResult(const LoadPair &Loads);
123 LoadPair getLoadPair(Type *LoadSizeType, Type *BSwapSizeType,
124 Type *CmpSizeType, unsigned OffsetBytes);
125
126 // Return true if a load of `LoadSize` bytes at `Offset` from the base
127 // pointers is accessible on the target: either it is naturally aligned given
128 // the known common base alignment, or the target allows a misaligned access
129 // of that width.
130 bool isAccessAllowed(unsigned LoadSize, uint64_t Offset) const;
131
132 static LoadEntryVector
133 computeGreedyLoadSequence(uint64_t Size, llvm::ArrayRef<unsigned> LoadSizes,
134 unsigned MaxNumLoads);
135 LoadEntryVector computeOverlappingLoadSequence(uint64_t Size,
136 unsigned MaxLoadSize,
137 unsigned MaxNumLoads) const;
138
139 void optimiseLoadSequence(
140 LoadEntryVector &LoadSequence,
141 const TargetTransformInfo::MemCmpExpansionOptions &Options,
142 bool IsUsedForZeroCmp) const;
143
144public:
145 MemCmpExpansion(CallInst *CI, uint64_t Size,
146 const TargetTransformInfo::MemCmpExpansionOptions &Options,
147 const bool IsUsedForZeroCmp, const DataLayout &TheDataLayout,
148 DomTreeUpdater *DTU, const TargetTransformInfo &TTI,
149 Align CommonAlign, unsigned MaxBytesPerBlock);
150
151 unsigned getNumBlocks();
152 unsigned getNumLoadsInBlock(unsigned LoadIndex) const;
153 unsigned getNumBytesInBlock(unsigned LoadIndex, unsigned NumLoads) const;
154 uint64_t getNumLoads() const { return LoadSequence.size(); }
155
156 Value *getMemCmpExpansion();
157};
158
159// Return true if a load of `LoadSize` bytes at `Offset` from the base pointers
160// is accessible on the target: either it is naturally aligned given the known
161// common base alignment, or the target allows a misaligned access of that
162// width. We query whether the access is *allowed*, not whether it is *fast*,
163// matching the historical behavior of forming unaligned loads whenever the
164// target permits them.
165static bool isAccessAllowed(const CallInst *CI, const TargetTransformInfo &TTI,
166 Align CommonAlign, unsigned LoadSize,
167 uint64_t Offset) {
168 // The access is naturally aligned when the known alignment is at least the
169 // load width. LoadSize is not necessarily a power of two here: some targets
170 // like RISC-V add non-power-of-two load sizes for vector memcmp, so compare
171 // against the raw width rather than constructing an Align, which would
172 // require a power of two.
173 Align AccessAlign = commonAlignment(A: CommonAlign, Offset);
174 if (AccessAlign.value() >= LoadSize)
175 return true;
176 unsigned AS = CI->getArgOperand(i: 0)->getType()->getPointerAddressSpace();
177 return TTI.allowsMisalignedMemoryAccesses(Context&: CI->getContext(), BitWidth: LoadSize * 8, AddressSpace: AS,
178 Alignment: AccessAlign);
179}
180
181// Return true if a load of `LoadSize` bytes at `Offset` from the base pointers
182// is accessible on the target given the known common base alignment. This gates
183// the (power-of-two) overlapping loads; tail expansions are always legalized by
184// the backend and skip this check.
185bool MemCmpExpansion::isAccessAllowed(unsigned LoadSize,
186 uint64_t Offset) const {
187 return ::isAccessAllowed(CI, TTI, CommonAlign, LoadSize, Offset);
188}
189
190MemCmpExpansion::LoadEntryVector
191MemCmpExpansion::computeGreedyLoadSequence(uint64_t Size,
192 llvm::ArrayRef<unsigned> LoadSizes,
193 const unsigned MaxNumLoads) {
194 LoadEntryVector LoadSequence;
195 uint64_t Offset = 0;
196 while (Size && !LoadSizes.empty()) {
197 const unsigned LoadSize = LoadSizes.front();
198 const uint64_t NumLoadsForThisSize = Size / LoadSize;
199 if (LoadSequence.size() + NumLoadsForThisSize > MaxNumLoads) {
200 // Do not expand if the total number of loads is larger than what the
201 // target allows. Note that it's important that we exit before completing
202 // the expansion to avoid using a ton of memory to store the expansion for
203 // large sizes.
204 return {};
205 }
206 if (NumLoadsForThisSize > 0) {
207 for (uint64_t I = 0; I < NumLoadsForThisSize; ++I) {
208 LoadSequence.push_back(Elt: {LoadSize, Offset});
209 Offset += LoadSize;
210 }
211 Size = Size % LoadSize;
212 }
213 LoadSizes = LoadSizes.drop_front();
214 }
215 return LoadSequence;
216}
217
218MemCmpExpansion::LoadEntryVector
219MemCmpExpansion::computeOverlappingLoadSequence(
220 uint64_t Size, const unsigned MaxLoadSize,
221 const unsigned MaxNumLoads) const {
222 // These are already handled by the greedy approach.
223 if (Size < 2 || MaxLoadSize < 2)
224 return {};
225
226 // We try to do as many non-overlapping loads as possible starting from the
227 // beginning.
228 const uint64_t NumNonOverlappingLoads = Size / MaxLoadSize;
229 assert(NumNonOverlappingLoads && "there must be at least one load");
230 // There remain 0 to (MaxLoadSize - 1) bytes to load, this will be done with
231 // an overlapping load.
232 Size = Size - NumNonOverlappingLoads * MaxLoadSize;
233 // Bail if we do not need an overloapping store, this is already handled by
234 // the greedy approach.
235 if (Size == 0)
236 return {};
237 // Bail if the number of loads (non-overlapping + potential overlapping one)
238 // is larger than the max allowed.
239 if ((NumNonOverlappingLoads + 1) > MaxNumLoads)
240 return {};
241
242 // Add non-overlapping loads.
243 LoadEntryVector LoadSequence;
244 uint64_t Offset = 0;
245 for (uint64_t I = 0; I < NumNonOverlappingLoads; ++I) {
246 LoadSequence.push_back(Elt: {MaxLoadSize, Offset});
247 Offset += MaxLoadSize;
248 }
249
250 // Add the last overlapping load. Its offset is not a multiple of the load
251 // size, so it may be misaligned; bail if the target cannot access it.
252 assert(Size > 0 && Size < MaxLoadSize && "broken invariant");
253 uint64_t OverlapOffset = Offset - (MaxLoadSize - Size);
254 if (!isAccessAllowed(LoadSize: MaxLoadSize, Offset: OverlapOffset))
255 return {};
256
257 LoadSequence.push_back(Elt: {MaxLoadSize, OverlapOffset});
258 return LoadSequence;
259}
260
261void MemCmpExpansion::optimiseLoadSequence(
262 LoadEntryVector &LoadSequence,
263 const TargetTransformInfo::MemCmpExpansionOptions &Options,
264 bool IsUsedForZeroCmp) const {
265 // This part of code attempts to optimize the LoadSequence by merging allowed
266 // subsequences into single loads of allowed sizes from
267 // `MemCmpExpansionOptions::AllowedTailExpansions`. If it is for zero
268 // comparison or if no allowed tail expansions are specified, we exit early.
269 if (IsUsedForZeroCmp || Options.AllowedTailExpansions.empty())
270 return;
271
272 while (LoadSequence.size() >= 2) {
273 auto Last = LoadSequence[LoadSequence.size() - 1];
274 auto PreLast = LoadSequence[LoadSequence.size() - 2];
275
276 // Exit the loop if the two sequences are not contiguous
277 if (PreLast.Offset + PreLast.LoadSize != Last.Offset)
278 break;
279
280 auto LoadSize = Last.LoadSize + PreLast.LoadSize;
281 if (find(Range: Options.AllowedTailExpansions, Val: LoadSize) ==
282 Options.AllowedTailExpansions.end())
283 break;
284
285 // A merged load wider than MaxLoadSize can only be emitted when it is the
286 // sole load (getMemCmpOneBlock); in a multi-block expansion
287 // emitLoadCompareBlock requires every load to fit in MaxLoadSize (the
288 // result-block phis are sized to it). The per-call-site alignment filter
289 // can shrink MaxLoadSize, so stop merging when the result would still be
290 // multi-block and the merged load exceeds it.
291 if (LoadSize > MaxLoadSize && LoadSequence.size() > 2)
292 break;
293
294 // Remove the last two sequences and replace with the combined sequence
295 LoadSequence.pop_back();
296 LoadSequence.pop_back();
297 LoadSequence.emplace_back(Args&: LoadSize, Args&: PreLast.Offset);
298 }
299}
300
301// Initialize the basic block structure required for expansion of memcmp call
302// with given maximum load size and memcmp size parameter.
303// This structure includes:
304// 1. A list of load compare blocks - LoadCmpBlocks.
305// 2. An EndBlock, split from original instruction point, which is the block to
306// return from.
307// 3. ResultBlock, block to branch to for early exit when a
308// LoadCmpBlock finds a difference.
309MemCmpExpansion::MemCmpExpansion(
310 CallInst *const CI, uint64_t Size,
311 const TargetTransformInfo::MemCmpExpansionOptions &Options,
312 const bool IsUsedForZeroCmp, const DataLayout &TheDataLayout,
313 DomTreeUpdater *DTU, const TargetTransformInfo &TTI, Align CommonAlign,
314 unsigned MaxBytesPerBlock)
315 : CI(CI), Size(Size), NumLoadsPerBlock(Options.NumLoadsPerBlock),
316 MaxBytesPerBlock(MaxBytesPerBlock), IsUsedForZeroCmp(IsUsedForZeroCmp),
317 DL(TheDataLayout), TTI(TTI), CommonAlign(CommonAlign), DTU(DTU),
318 Builder(CI) {
319 Builder.disableGEPCanonicalization();
320 assert(Size > 0 && "zero blocks");
321 assert(NumLoadsPerBlock > 0 && "zero loads per block");
322 // Scale the max size down if the target can load more bytes than we need.
323 llvm::ArrayRef<unsigned> LoadSizes(Options.LoadSizes);
324 while (!LoadSizes.empty() && LoadSizes.front() > Size) {
325 LoadSizes = LoadSizes.drop_front();
326 }
327 assert(!LoadSizes.empty() && "cannot load Size bytes");
328 MaxLoadSize = LoadSizes.front();
329 // Compute the decomposition.
330 LoadSequence =
331 computeGreedyLoadSequence(Size, LoadSizes, MaxNumLoads: Options.MaxNumLoads);
332 assert(LoadSequence.size() <= Options.MaxNumLoads && "broken invariant");
333 // If we allow overlapping loads and the load sequence is not already optimal,
334 // use overlapping loads.
335 if (Options.AllowOverlappingLoads &&
336 (LoadSequence.empty() || LoadSequence.size() > 2)) {
337 auto OverlappingLoads =
338 computeOverlappingLoadSequence(Size, MaxLoadSize, MaxNumLoads: Options.MaxNumLoads);
339 if (!OverlappingLoads.empty() &&
340 (LoadSequence.empty() ||
341 OverlappingLoads.size() < LoadSequence.size())) {
342 LoadSequence = OverlappingLoads;
343 }
344 }
345 assert(LoadSequence.size() <= Options.MaxNumLoads && "broken invariant");
346 optimiseLoadSequence(LoadSequence, Options, IsUsedForZeroCmp);
347
348 unsigned LoadIndex = 0;
349 while (LoadIndex < getNumLoads()) {
350 unsigned NumLoads = getNumLoadsInBlock(LoadIndex);
351 MaxBlockSize =
352 std::max(a: MaxBlockSize, b: getNumBytesInBlock(LoadIndex, NumLoads));
353 LoadIndex += NumLoads;
354 }
355 if (MaxBlockSize)
356 MaxBlockSize = PowerOf2Ceil(A: MaxBlockSize);
357}
358
359unsigned MemCmpExpansion::getNumLoadsInBlock(unsigned LoadIndex) const {
360 if (IsUsedForZeroCmp)
361 return std::min<uint64_t>(a: getNumLoads() - LoadIndex, b: NumLoadsPerBlock);
362
363 unsigned NumLoads = 0;
364 unsigned NumBytes = 0;
365 while (LoadIndex + NumLoads < getNumLoads() && NumLoads < NumLoadsPerBlock &&
366 NumBytes + LoadSequence[LoadIndex + NumLoads].LoadSize <=
367 MaxBytesPerBlock) {
368 NumBytes += LoadSequence[LoadIndex + NumLoads].LoadSize;
369 ++NumLoads;
370 }
371 assert(NumLoads && "at least one load must fit in a block");
372 return NumLoads;
373}
374
375unsigned MemCmpExpansion::getNumBytesInBlock(unsigned LoadIndex,
376 unsigned NumLoads) const {
377 unsigned NumBytes = 0;
378 for (unsigned I = 0; I != NumLoads; ++I)
379 NumBytes += LoadSequence[LoadIndex + I].LoadSize;
380 return NumBytes;
381}
382
383unsigned MemCmpExpansion::getNumBlocks() {
384 unsigned NumBlocks = 0;
385 for (unsigned LoadIndex = 0; LoadIndex < getNumLoads(); ++NumBlocks)
386 LoadIndex += getNumLoadsInBlock(LoadIndex);
387 return NumBlocks;
388}
389
390void MemCmpExpansion::createLoadCmpBlocks() {
391 for (unsigned i = 0; i < getNumBlocks(); i++) {
392 BasicBlock *BB = BasicBlock::Create(Context&: CI->getContext(), Name: "loadbb",
393 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
394 LoadCmpBlocks.push_back(x: BB);
395 }
396}
397
398void MemCmpExpansion::createResultBlock() {
399 ResBlock.BB = BasicBlock::Create(Context&: CI->getContext(), Name: "res_block",
400 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
401}
402
403MemCmpExpansion::LoadPair MemCmpExpansion::getLoadPair(Type *LoadSizeType,
404 Type *BSwapSizeType,
405 Type *CmpSizeType,
406 unsigned OffsetBytes) {
407 // Get the memory source at offset `OffsetBytes`.
408 Value *LhsSource = CI->getArgOperand(i: 0);
409 Value *RhsSource = CI->getArgOperand(i: 1);
410 Align LhsAlign = getMemCmpArgAlignment(CI, ArgNo: 0, DL);
411 Align RhsAlign = getMemCmpArgAlignment(CI, ArgNo: 1, DL);
412 if (OffsetBytes > 0) {
413 auto *ByteType = Type::getInt8Ty(C&: CI->getContext());
414 LhsSource = Builder.CreateConstGEP1_64(Ty: ByteType, Ptr: LhsSource, Idx0: OffsetBytes);
415 RhsSource = Builder.CreateConstGEP1_64(Ty: ByteType, Ptr: RhsSource, Idx0: OffsetBytes);
416 LhsAlign = commonAlignment(A: LhsAlign, Offset: OffsetBytes);
417 RhsAlign = commonAlignment(A: RhsAlign, Offset: OffsetBytes);
418 }
419
420 // Create a constant or a load from the source.
421 Value *Lhs = nullptr;
422 if (auto *C = dyn_cast<Constant>(Val: LhsSource))
423 Lhs = ConstantFoldLoadFromConstPtr(C, Ty: LoadSizeType, DL);
424 if (!Lhs)
425 Lhs = Builder.CreateAlignedLoad(Ty: LoadSizeType, Ptr: LhsSource, Align: LhsAlign);
426
427 Value *Rhs = nullptr;
428 if (auto *C = dyn_cast<Constant>(Val: RhsSource))
429 Rhs = ConstantFoldLoadFromConstPtr(C, Ty: LoadSizeType, DL);
430 if (!Rhs)
431 Rhs = Builder.CreateAlignedLoad(Ty: LoadSizeType, Ptr: RhsSource, Align: RhsAlign);
432
433 // Zero extend if Byte Swap intrinsic has different type
434 if (BSwapSizeType && LoadSizeType != BSwapSizeType) {
435 Lhs = Builder.CreateZExt(V: Lhs, DestTy: BSwapSizeType);
436 Rhs = Builder.CreateZExt(V: Rhs, DestTy: BSwapSizeType);
437 }
438
439 // Swap bytes if required.
440 if (BSwapSizeType) {
441 Function *Bswap = Intrinsic::getOrInsertDeclaration(
442 M: CI->getModule(), id: Intrinsic::bswap, OverloadTys: BSwapSizeType);
443 Lhs = Builder.CreateCall(Callee: Bswap, Args: Lhs);
444 Rhs = Builder.CreateCall(Callee: Bswap, Args: Rhs);
445 }
446
447 // Zero extend if required.
448 if (CmpSizeType != nullptr && CmpSizeType != Lhs->getType()) {
449 Lhs = Builder.CreateZExt(V: Lhs, DestTy: CmpSizeType);
450 Rhs = Builder.CreateZExt(V: Rhs, DestTy: CmpSizeType);
451 }
452 return {.Lhs: Lhs, .Rhs: Rhs};
453}
454
455// This function creates the IR instructions for loading and comparing 1 byte.
456// It loads 1 byte from each source of the memcmp parameters with the given
457// GEPIndex. It then subtracts the two loaded values and adds this result to the
458// final phi node for selecting the memcmp result.
459void MemCmpExpansion::emitLoadCompareByteBlock(unsigned BlockIndex,
460 unsigned OffsetBytes) {
461 BasicBlock *BB = LoadCmpBlocks[BlockIndex];
462 Builder.SetInsertPoint(BB);
463 const LoadPair Loads =
464 getLoadPair(LoadSizeType: Type::getInt8Ty(C&: CI->getContext()), BSwapSizeType: nullptr,
465 CmpSizeType: Type::getInt32Ty(C&: CI->getContext()), OffsetBytes);
466 Value *Diff = Builder.CreateSub(LHS: Loads.Lhs, RHS: Loads.Rhs);
467
468 PhiRes->addIncoming(V: Diff, BB);
469
470 if (BlockIndex < (LoadCmpBlocks.size() - 1)) {
471 // Early exit branch if difference found to EndBlock. Otherwise, continue to
472 // next LoadCmpBlock,
473 Value *Cmp = Builder.CreateICmp(P: ICmpInst::ICMP_NE, LHS: Diff,
474 RHS: ConstantInt::get(Ty: Diff->getType(), V: 0));
475 Builder.CreateCondBr(Cond: Cmp, True: EndBlock, False: LoadCmpBlocks[BlockIndex + 1]);
476 if (DTU)
477 DTU->applyUpdates(
478 Updates: {{DominatorTree::Insert, BB, EndBlock},
479 {DominatorTree::Insert, BB, LoadCmpBlocks[BlockIndex + 1]}});
480 } else {
481 // The last block has an unconditional branch to EndBlock.
482 Builder.CreateBr(Dest: EndBlock);
483 if (DTU)
484 DTU->applyUpdates(Updates: {{DominatorTree::Insert, BB, EndBlock}});
485 }
486}
487
488/// Generate an equality comparison for one or more pairs of loaded values.
489/// This is used in the case where the memcmp() call is compared equal or not
490/// equal to zero.
491Value *MemCmpExpansion::getCompareLoadPairs(unsigned BlockIndex,
492 unsigned &LoadIndex) {
493 assert(LoadIndex < getNumLoads() &&
494 "getCompareLoadPairs() called with no remaining loads");
495 std::vector<Value *> XorList, OrList;
496 Value *Diff = nullptr;
497
498 const unsigned NumLoads = getNumLoadsInBlock(LoadIndex);
499
500 // For a single-block expansion, start inserting before the memcmp call.
501 if (LoadCmpBlocks.empty())
502 Builder.SetInsertPoint(CI);
503 else
504 Builder.SetInsertPoint(LoadCmpBlocks[BlockIndex]);
505
506 Value *Cmp = nullptr;
507 // If we have multiple loads per block, we need to generate a composite
508 // comparison using xor+or. The type for the combinations is the largest load
509 // type.
510 IntegerType *const MaxLoadType =
511 NumLoads == 1 ? nullptr
512 : IntegerType::get(C&: CI->getContext(), NumBits: MaxLoadSize * 8);
513
514 for (unsigned i = 0; i < NumLoads; ++i, ++LoadIndex) {
515 const LoadEntry &CurLoadEntry = LoadSequence[LoadIndex];
516 const LoadPair Loads = getLoadPair(
517 LoadSizeType: IntegerType::get(C&: CI->getContext(), NumBits: CurLoadEntry.LoadSize * 8), BSwapSizeType: nullptr,
518 CmpSizeType: MaxLoadType, OffsetBytes: CurLoadEntry.Offset);
519
520 if (NumLoads != 1) {
521 // If we have multiple loads per block, we need to generate a composite
522 // comparison using xor+or.
523 Diff = Builder.CreateXor(LHS: Loads.Lhs, RHS: Loads.Rhs);
524 Diff = Builder.CreateZExt(V: Diff, DestTy: MaxLoadType);
525 XorList.push_back(x: Diff);
526 } else {
527 // If there's only one load per block, we just compare the loaded values.
528 Cmp = Builder.CreateICmpNE(LHS: Loads.Lhs, RHS: Loads.Rhs);
529 }
530 }
531
532 auto pairWiseOr = [&](std::vector<Value *> &InList) -> std::vector<Value *> {
533 std::vector<Value *> OutList;
534 for (unsigned i = 0; i < InList.size() - 1; i = i + 2) {
535 Value *Or = Builder.CreateOr(LHS: InList[i], RHS: InList[i + 1]);
536 OutList.push_back(x: Or);
537 }
538 if (InList.size() % 2 != 0)
539 OutList.push_back(x: InList.back());
540 return OutList;
541 };
542
543 if (!Cmp) {
544 // Pairwise OR the XOR results.
545 OrList = pairWiseOr(XorList);
546
547 // Pairwise OR the OR results until one result left.
548 while (OrList.size() != 1) {
549 OrList = pairWiseOr(OrList);
550 }
551
552 assert(Diff && "Failed to find comparison diff");
553 Cmp = Builder.CreateICmpNE(LHS: OrList[0], RHS: ConstantInt::get(Ty: Diff->getType(), V: 0));
554 }
555
556 return Cmp;
557}
558
559MemCmpExpansion::LoadPair
560MemCmpExpansion::getPackedLoadPair(unsigned BlockIndex, unsigned &LoadIndex) {
561 assert(LoadIndex < getNumLoads() &&
562 "getPackedLoadPair() called with no remaining loads");
563 if (LoadCmpBlocks.empty())
564 Builder.SetInsertPoint(CI);
565 else
566 Builder.SetInsertPoint(LoadCmpBlocks[BlockIndex]);
567
568 const unsigned NumLoads = getNumLoadsInBlock(LoadIndex);
569 const unsigned NumBytes = getNumBytesInBlock(LoadIndex, NumLoads);
570 // Pack the loads so that the byte at the lowest address occupies the most
571 // significant bits. An unsigned comparison of the packed values therefore
572 // has the same lexicographic ordering as memcmp.
573 auto *BlockType = IntegerType::get(C&: CI->getContext(), NumBits: MaxBlockSize * 8);
574 Value *PackedLhs = ConstantInt::get(Ty: BlockType, V: 0);
575 Value *PackedRhs = ConstantInt::get(Ty: BlockType, V: 0);
576 unsigned RemainingBytes = NumBytes;
577
578 for (unsigned I = 0; I != NumLoads; ++I, ++LoadIndex) {
579 const LoadEntry &Entry = LoadSequence[LoadIndex];
580 auto *LoadType = IntegerType::get(C&: CI->getContext(), NumBits: Entry.LoadSize * 8);
581 auto *BSwapType = DL.isLittleEndian() && Entry.LoadSize != 1
582 ? IntegerType::get(C&: CI->getContext(),
583 NumBits: PowerOf2Ceil(A: Entry.LoadSize * 8))
584 : nullptr;
585 LoadPair Loads = getLoadPair(LoadSizeType: LoadType, BSwapSizeType: BSwapType, CmpSizeType: BlockType, OffsetBytes: Entry.Offset);
586
587 if (BSwapType && BSwapType->getIntegerBitWidth() != Entry.LoadSize * 8) {
588 unsigned Padding = BSwapType->getIntegerBitWidth() - Entry.LoadSize * 8;
589 Loads.Lhs = Builder.CreateLShr(LHS: Loads.Lhs, RHS: Padding);
590 Loads.Rhs = Builder.CreateLShr(LHS: Loads.Rhs, RHS: Padding);
591 }
592
593 RemainingBytes -= Entry.LoadSize;
594 unsigned Shift = RemainingBytes * 8;
595 PackedLhs =
596 Builder.CreateOr(LHS: PackedLhs, RHS: Builder.CreateShl(LHS: Loads.Lhs, RHS: Shift));
597 PackedRhs =
598 Builder.CreateOr(LHS: PackedRhs, RHS: Builder.CreateShl(LHS: Loads.Rhs, RHS: Shift));
599 }
600
601 return {.Lhs: PackedLhs, .Rhs: PackedRhs};
602}
603
604void MemCmpExpansion::emitLoadCompareBlockMultipleLoads(unsigned BlockIndex,
605 unsigned &LoadIndex) {
606 Value *Cmp = getCompareLoadPairs(BlockIndex, LoadIndex);
607
608 BasicBlock *NextBB = (BlockIndex == (LoadCmpBlocks.size() - 1))
609 ? EndBlock
610 : LoadCmpBlocks[BlockIndex + 1];
611 // Early exit branch if difference found to ResultBlock. Otherwise,
612 // continue to next LoadCmpBlock or EndBlock.
613 BasicBlock *BB = Builder.GetInsertBlock();
614 CondBrInst *CmpBr = Builder.CreateCondBr(Cond: Cmp, True: ResBlock.BB, False: NextBB);
615 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *CmpBr, DEBUG_TYPE,
616 F: CI->getFunction());
617 if (DTU)
618 DTU->applyUpdates(Updates: {{DominatorTree::Insert, BB, ResBlock.BB},
619 {DominatorTree::Insert, BB, NextBB}});
620
621 // Add a phi edge for the last LoadCmpBlock to Endblock with a value of 0
622 // since early exit to ResultBlock was not taken (no difference was found in
623 // any of the bytes).
624 if (BlockIndex == LoadCmpBlocks.size() - 1) {
625 Value *Zero = ConstantInt::get(Ty: Type::getInt32Ty(C&: CI->getContext()), V: 0);
626 PhiRes->addIncoming(V: Zero, BB: LoadCmpBlocks[BlockIndex]);
627 }
628}
629
630// This function creates the IR instructions for loading and comparing using the
631// given LoadSize. It loads the number of bytes specified by LoadSize from each
632// source of the memcmp parameters. It then does a subtract to see if there was
633// a difference in the loaded values. If a difference is found, it branches
634// with an early exit to the ResultBlock for calculating which source was
635// larger. Otherwise, it falls through to the either the next LoadCmpBlock or
636// the EndBlock if this is the last LoadCmpBlock. Loading 1 byte is handled with
637// a special case through emitLoadCompareByteBlock. The special handling can
638// simply subtract the loaded values and add it to the result phi node.
639void MemCmpExpansion::emitLoadCompareBlock(unsigned BlockIndex,
640 unsigned &LoadIndex) {
641 const unsigned NumLoads = getNumLoadsInBlock(LoadIndex);
642 if (NumLoads == 1 && LoadSequence[LoadIndex].LoadSize == 1) {
643 MemCmpExpansion::emitLoadCompareByteBlock(BlockIndex,
644 OffsetBytes: LoadSequence[LoadIndex].Offset);
645 ++LoadIndex;
646 return;
647 }
648
649 LoadPair Loads;
650 if (NumLoads == 1) {
651 const LoadEntry &Entry = LoadSequence[LoadIndex++];
652 auto *LoadType = IntegerType::get(C&: CI->getContext(), NumBits: Entry.LoadSize * 8);
653 auto *BSwapType = DL.isLittleEndian()
654 ? IntegerType::get(C&: CI->getContext(),
655 NumBits: PowerOf2Ceil(A: Entry.LoadSize * 8))
656 : nullptr;
657 auto *CmpType = IntegerType::get(C&: CI->getContext(), NumBits: MaxBlockSize * 8);
658 Builder.SetInsertPoint(LoadCmpBlocks[BlockIndex]);
659 Loads = getLoadPair(LoadSizeType: LoadType, BSwapSizeType: BSwapType, CmpSizeType: CmpType, OffsetBytes: Entry.Offset);
660 } else {
661 Loads = getPackedLoadPair(BlockIndex, LoadIndex);
662 }
663
664 // Add the loaded values to the phi nodes for calculating memcmp result only
665 // if result is not used in a zero equality.
666 if (!IsUsedForZeroCmp) {
667 ResBlock.PhiSrc1->addIncoming(V: Loads.Lhs, BB: LoadCmpBlocks[BlockIndex]);
668 ResBlock.PhiSrc2->addIncoming(V: Loads.Rhs, BB: LoadCmpBlocks[BlockIndex]);
669 }
670
671 Value *Cmp = Builder.CreateICmp(P: ICmpInst::ICMP_EQ, LHS: Loads.Lhs, RHS: Loads.Rhs);
672 BasicBlock *NextBB = (BlockIndex == (LoadCmpBlocks.size() - 1))
673 ? EndBlock
674 : LoadCmpBlocks[BlockIndex + 1];
675 // Early exit branch if difference found to ResultBlock. Otherwise, continue
676 // to next LoadCmpBlock or EndBlock.
677 BasicBlock *BB = Builder.GetInsertBlock();
678 CondBrInst *CmpBr = Builder.CreateCondBr(Cond: Cmp, True: NextBB, False: ResBlock.BB);
679 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *CmpBr, DEBUG_TYPE,
680 F: CI->getFunction());
681 if (DTU)
682 DTU->applyUpdates(Updates: {{DominatorTree::Insert, BB, NextBB},
683 {DominatorTree::Insert, BB, ResBlock.BB}});
684
685 // Add a phi edge for the last LoadCmpBlock to Endblock with a value of 0
686 // since early exit to ResultBlock was not taken (no difference was found in
687 // any of the bytes).
688 if (BlockIndex == LoadCmpBlocks.size() - 1) {
689 Value *Zero = ConstantInt::get(Ty: Type::getInt32Ty(C&: CI->getContext()), V: 0);
690 PhiRes->addIncoming(V: Zero, BB: LoadCmpBlocks[BlockIndex]);
691 }
692}
693
694// This function populates the ResultBlock with a sequence to calculate the
695// memcmp result. It compares the two loaded source values and returns -1 if
696// src1 < src2 and 1 if src1 > src2.
697void MemCmpExpansion::emitMemCmpResultBlock() {
698 // Special case: if memcmp result is used in a zero equality, result does not
699 // need to be calculated and can simply return 1.
700 if (IsUsedForZeroCmp) {
701 BasicBlock::iterator InsertPt = ResBlock.BB->getFirstInsertionPt();
702 Builder.SetInsertPoint(InsertPt);
703 Value *Res = ConstantInt::get(Ty: Type::getInt32Ty(C&: CI->getContext()), V: 1);
704 PhiRes->addIncoming(V: Res, BB: ResBlock.BB);
705 Builder.CreateBr(Dest: EndBlock);
706 if (DTU)
707 DTU->applyUpdates(Updates: {{DominatorTree::Insert, ResBlock.BB, EndBlock}});
708 return;
709 }
710 BasicBlock::iterator InsertPt = ResBlock.BB->getFirstInsertionPt();
711 Builder.SetInsertPoint(InsertPt);
712
713 Value *Cmp = Builder.CreateICmp(P: ICmpInst::ICMP_ULT, LHS: ResBlock.PhiSrc1,
714 RHS: ResBlock.PhiSrc2);
715
716 Value *Res =
717 Builder.CreateSelect(C: Cmp, True: Constant::getAllOnesValue(Ty: Builder.getInt32Ty()),
718 False: ConstantInt::get(Ty: Builder.getInt32Ty(), V: 1));
719 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *cast<Instruction>(Val: Res),
720 DEBUG_TYPE, F: CI->getFunction());
721
722 PhiRes->addIncoming(V: Res, BB: ResBlock.BB);
723 Builder.CreateBr(Dest: EndBlock);
724 if (DTU)
725 DTU->applyUpdates(Updates: {{DominatorTree::Insert, ResBlock.BB, EndBlock}});
726}
727
728void MemCmpExpansion::setupResultBlockPHINodes() {
729 Type *MaxLoadType = IntegerType::get(C&: CI->getContext(), NumBits: MaxBlockSize * 8);
730 Builder.SetInsertPoint(ResBlock.BB);
731 ResBlock.PhiSrc1 = Builder.CreatePHI(Ty: MaxLoadType, NumReservedValues: getNumBlocks(), Name: "phi.src1");
732 ResBlock.PhiSrc2 = Builder.CreatePHI(Ty: MaxLoadType, NumReservedValues: getNumBlocks(), Name: "phi.src2");
733}
734
735void MemCmpExpansion::setupEndBlockPHINodes() {
736 Builder.SetInsertPoint(EndBlock->begin());
737 PhiRes = Builder.CreatePHI(Ty: Type::getInt32Ty(C&: CI->getContext()), NumReservedValues: 2, Name: "phi.res");
738}
739
740Value *MemCmpExpansion::getMemCmpExpansionZeroCase() {
741 unsigned LoadIndex = 0;
742 // This loop populates each of the LoadCmpBlocks with the IR sequence to
743 // handle multiple loads per block.
744 for (unsigned I = 0; I < getNumBlocks(); ++I) {
745 emitLoadCompareBlockMultipleLoads(BlockIndex: I, LoadIndex);
746 }
747
748 emitMemCmpResultBlock();
749 return PhiRes;
750}
751
752/// A memcmp expansion that compares equality with 0 and only has one block of
753/// load and compare can bypass the compare, branch, and phi IR that is required
754/// in the general case.
755Value *MemCmpExpansion::getMemCmpEqZeroOneBlock() {
756 unsigned LoadIndex = 0;
757 Value *Cmp = getCompareLoadPairs(BlockIndex: 0, LoadIndex);
758 assert(LoadIndex == getNumLoads() && "some entries were not consumed");
759 return Builder.CreateZExt(V: Cmp, DestTy: Type::getInt32Ty(C&: CI->getContext()));
760}
761
762/// A memcmp expansion that only has one block of load and compare can bypass
763/// the compare, branch, and phi IR that is required in the general case.
764/// This function also analyses users of memcmp, and if there is only one user
765/// from which we can conclude that only 2 out of 3 memcmp outcomes really
766/// matter, then it generates more efficient code with only one comparison.
767Value *MemCmpExpansion::getMemCmpOneBlock() {
768 bool NeedsBSwap = DL.isLittleEndian() && Size != 1;
769 Type *LoadSizeType = IntegerType::get(C&: CI->getContext(), NumBits: Size * 8);
770 Type *BSwapSizeType =
771 NeedsBSwap ? IntegerType::get(C&: CI->getContext(), NumBits: PowerOf2Ceil(A: Size * 8))
772 : nullptr;
773 Type *MaxLoadType =
774 IntegerType::get(C&: CI->getContext(),
775 NumBits: std::max(a: MaxLoadSize, b: (unsigned)PowerOf2Ceil(A: Size)) * 8);
776
777 // The i8 and i16 cases don't need compares. We zext the loaded values and
778 // subtract them to get the suitable negative, zero, or positive i32 result.
779 if (Size == 1 || Size == 2) {
780 const LoadPair Loads = getLoadPair(LoadSizeType, BSwapSizeType,
781 CmpSizeType: Builder.getInt32Ty(), /*Offset*/ OffsetBytes: 0);
782 return Builder.CreateSub(LHS: Loads.Lhs, RHS: Loads.Rhs);
783 }
784
785 const LoadPair Loads = getLoadPair(LoadSizeType, BSwapSizeType, CmpSizeType: MaxLoadType,
786 /*Offset*/ OffsetBytes: 0);
787
788 return getMemCmpResult(Loads);
789}
790
791Value *MemCmpExpansion::getMemCmpOneBlockMultipleLoads() {
792 unsigned LoadIndex = 0;
793 LoadPair Loads = getPackedLoadPair(/*BlockIndex=*/0, LoadIndex);
794 assert(LoadIndex == getNumLoads() && "some entries were not consumed");
795 return getMemCmpResult(Loads);
796}
797
798Value *MemCmpExpansion::getMemCmpResult(const LoadPair &Loads) {
799 // If a user of memcmp cares only about two outcomes, for example:
800 // bool result = memcmp(a, b, NBYTES) > 0;
801 // We can generate more optimal code with a smaller number of operations
802 if (CI->hasOneUser()) {
803 auto *UI = cast<Instruction>(Val: *CI->user_begin());
804 CmpPredicate Pred = ICmpInst::Predicate::BAD_ICMP_PREDICATE;
805 bool NeedsZExt = false;
806 // This is a special case because instead of checking if the result is less
807 // than zero:
808 // bool result = memcmp(a, b, NBYTES) < 0;
809 // Compiler is clever enough to generate the following code:
810 // bool result = memcmp(a, b, NBYTES) >> 31;
811 if (match(V: UI,
812 P: m_LShr(L: m_Value(),
813 R: m_SpecificInt(V: CI->getType()->getIntegerBitWidth() - 1)))) {
814 Pred = ICmpInst::ICMP_SLT;
815 NeedsZExt = true;
816 } else if (match(V: UI, P: m_SpecificICmp(MatchPred: ICmpInst::ICMP_SGT, L: m_Specific(V: CI),
817 R: m_AllOnes()))) {
818 // Adjust predicate as if it compared with 0.
819 Pred = ICmpInst::ICMP_SGE;
820 } else if (match(V: UI, P: m_SpecificICmp(MatchPred: ICmpInst::ICMP_SLT, L: m_Specific(V: CI),
821 R: m_One()))) {
822 // Adjust predicate as if it compared with 0.
823 Pred = ICmpInst::ICMP_SLE;
824 } else {
825 // In case of a successful match this call will set `Pred` variable
826 match(V: UI, P: m_ICmp(Pred, L: m_Specific(V: CI), R: m_Zero()));
827 }
828 // Generate new code and remove the original memcmp call and the user
829 if (ICmpInst::isSigned(Pred)) {
830 Value *Cmp = Builder.CreateICmp(P: ICmpInst::getUnsignedPredicate(Pred),
831 LHS: Loads.Lhs, RHS: Loads.Rhs);
832 auto *Result = NeedsZExt ? Builder.CreateZExt(V: Cmp, DestTy: UI->getType()) : Cmp;
833 UI->replaceAllUsesWith(V: Result);
834 UI->eraseFromParent();
835 CI->eraseFromParent();
836 return nullptr;
837 }
838 }
839
840 // The result of memcmp is negative, zero, or positive.
841 return Builder.CreateIntrinsic(RetTy: Builder.getInt32Ty(), ID: Intrinsic::ucmp,
842 Args: {Loads.Lhs, Loads.Rhs});
843}
844
845// This function expands the memcmp call into an inline expansion and returns
846// the memcmp result. Returns nullptr if the memcmp is already replaced.
847Value *MemCmpExpansion::getMemCmpExpansion() {
848 // Create the basic block framework for a multi-block expansion.
849 if (getNumBlocks() != 1) {
850 BasicBlock *StartBlock = CI->getParent();
851 EndBlock = SplitBlock(Old: StartBlock, SplitPt: CI, DTU, /*LI=*/nullptr,
852 /*MSSAU=*/nullptr, BBName: "endblock");
853 setupEndBlockPHINodes();
854 createResultBlock();
855
856 // If return value of memcmp is not used in a zero equality, we need to
857 // calculate which source was larger. The calculation requires the
858 // two loaded source values of each load compare block.
859 // These will be saved in the phi nodes created by setupResultBlockPHINodes.
860 if (!IsUsedForZeroCmp) setupResultBlockPHINodes();
861
862 // Create the number of required load compare basic blocks.
863 createLoadCmpBlocks();
864
865 // Update the terminator added by SplitBlock to branch to the first
866 // LoadCmpBlock.
867 StartBlock->getTerminator()->setSuccessor(Idx: 0, BB: LoadCmpBlocks[0]);
868 if (DTU)
869 DTU->applyUpdates(Updates: {{DominatorTree::Insert, StartBlock, LoadCmpBlocks[0]},
870 {DominatorTree::Delete, StartBlock, EndBlock}});
871 }
872
873 Builder.SetCurrentDebugLocation(CI->getDebugLoc());
874
875 if (IsUsedForZeroCmp)
876 return getNumBlocks() == 1 ? getMemCmpEqZeroOneBlock()
877 : getMemCmpExpansionZeroCase();
878
879 if (getNumBlocks() == 1)
880 return getNumLoads() == 1 ? getMemCmpOneBlock()
881 : getMemCmpOneBlockMultipleLoads();
882
883 unsigned LoadIndex = 0;
884 for (unsigned I = 0; I < getNumBlocks(); ++I) {
885 emitLoadCompareBlock(BlockIndex: I, LoadIndex);
886 }
887
888 emitMemCmpResultBlock();
889 return PhiRes;
890}
891
892// This function checks to see if an expansion of memcmp can be generated.
893// It checks for constant compare size that is less than the max inline size.
894// If an expansion cannot occur, returns false to leave as a library call.
895// Otherwise, the library call is replaced with a new IR instruction sequence.
896/// We want to transform:
897/// %call = call signext i32 @memcmp(i8* %0, i8* %1, i64 15)
898/// To:
899/// loadbb:
900/// %0 = bitcast i32* %buffer2 to i8*
901/// %1 = bitcast i32* %buffer1 to i8*
902/// %2 = bitcast i8* %1 to i64*
903/// %3 = bitcast i8* %0 to i64*
904/// %4 = load i64, i64* %2
905/// %5 = load i64, i64* %3
906/// %6 = call i64 @llvm.bswap.i64(i64 %4)
907/// %7 = call i64 @llvm.bswap.i64(i64 %5)
908/// %8 = sub i64 %6, %7
909/// %9 = icmp ne i64 %8, 0
910/// br i1 %9, label %res_block, label %loadbb1
911/// res_block: ; preds = %loadbb2,
912/// %loadbb1, %loadbb
913/// %phi.src1 = phi i64 [ %6, %loadbb ], [ %22, %loadbb1 ], [ %36, %loadbb2 ]
914/// %phi.src2 = phi i64 [ %7, %loadbb ], [ %23, %loadbb1 ], [ %37, %loadbb2 ]
915/// %10 = icmp ult i64 %phi.src1, %phi.src2
916/// %11 = select i1 %10, i32 -1, i32 1
917/// br label %endblock
918/// loadbb1: ; preds = %loadbb
919/// %12 = bitcast i32* %buffer2 to i8*
920/// %13 = bitcast i32* %buffer1 to i8*
921/// %14 = bitcast i8* %13 to i32*
922/// %15 = bitcast i8* %12 to i32*
923/// %16 = getelementptr i32, i32* %14, i32 2
924/// %17 = getelementptr i32, i32* %15, i32 2
925/// %18 = load i32, i32* %16
926/// %19 = load i32, i32* %17
927/// %20 = call i32 @llvm.bswap.i32(i32 %18)
928/// %21 = call i32 @llvm.bswap.i32(i32 %19)
929/// %22 = zext i32 %20 to i64
930/// %23 = zext i32 %21 to i64
931/// %24 = sub i64 %22, %23
932/// %25 = icmp ne i64 %24, 0
933/// br i1 %25, label %res_block, label %loadbb2
934/// loadbb2: ; preds = %loadbb1
935/// %26 = bitcast i32* %buffer2 to i8*
936/// %27 = bitcast i32* %buffer1 to i8*
937/// %28 = bitcast i8* %27 to i16*
938/// %29 = bitcast i8* %26 to i16*
939/// %30 = getelementptr i16, i16* %28, i16 6
940/// %31 = getelementptr i16, i16* %29, i16 6
941/// %32 = load i16, i16* %30
942/// %33 = load i16, i16* %31
943/// %34 = call i16 @llvm.bswap.i16(i16 %32)
944/// %35 = call i16 @llvm.bswap.i16(i16 %33)
945/// %36 = zext i16 %34 to i64
946/// %37 = zext i16 %35 to i64
947/// %38 = sub i64 %36, %37
948/// %39 = icmp ne i64 %38, 0
949/// br i1 %39, label %res_block, label %loadbb3
950/// loadbb3: ; preds = %loadbb2
951/// %40 = bitcast i32* %buffer2 to i8*
952/// %41 = bitcast i32* %buffer1 to i8*
953/// %42 = getelementptr i8, i8* %41, i8 14
954/// %43 = getelementptr i8, i8* %40, i8 14
955/// %44 = load i8, i8* %42
956/// %45 = load i8, i8* %43
957/// %46 = zext i8 %44 to i32
958/// %47 = zext i8 %45 to i32
959/// %48 = sub i32 %46, %47
960/// br label %endblock
961/// endblock: ; preds = %res_block,
962/// %loadbb3
963/// %phi.res = phi i32 [ %48, %loadbb3 ], [ %11, %res_block ]
964/// ret i32 %phi.res
965static bool expandMemCmp(const ScalarOptions &Opts, CallInst *CI,
966 const TargetTransformInfo *TTI, const DataLayout *DL,
967 ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI,
968 DomTreeUpdater *DTU, const bool IsBCmp) {
969 NumMemCmpCalls++;
970
971 // Early exit from expansion if -Oz.
972 if (CI->getFunction()->hasMinSize())
973 return false;
974
975 // Early exit from expansion if size is not a constant.
976 ConstantInt *SizeCast = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 2));
977 if (!SizeCast) {
978 NumMemCmpNotConstant++;
979 return false;
980 }
981 const uint64_t SizeVal = SizeCast->getZExtValue();
982
983 if (SizeVal == 0) {
984 return false;
985 }
986 // TTI call to check if target would like to expand memcmp. Also, get the
987 // available load sizes.
988 const bool IsUsedForZeroCmp =
989 IsBCmp || isOnlyUsedInZeroEqualityComparison(CtxI: CI);
990 bool OptForSize = llvm::shouldOptimizeForSize(BB: CI->getParent(), PSI, BFI);
991 auto Options = TTI->enableMemCmpExpansion(OptSize: OptForSize,
992 IsZeroCmp: IsUsedForZeroCmp);
993 if (!Options) return false;
994
995 if (Opts.memcmp_num_loads_per_block)
996 Options.NumLoadsPerBlock = *Opts.memcmp_num_loads_per_block;
997
998 if (OptForSize && Opts.max_loads_per_memcmp_opt_size)
999 Options.MaxNumLoads = *Opts.max_loads_per_memcmp_opt_size;
1000
1001 if (!OptForSize && Opts.max_loads_per_memcmp)
1002 Options.MaxNumLoads = *Opts.max_loads_per_memcmp;
1003
1004 // Keep only the load sizes the target can access at the base alignment:
1005 // either the access is naturally aligned, or the target allows a misaligned
1006 // access of that width. This lets strict-alignment targets expand compares
1007 // whose pointers happen to be sufficiently aligned, while still falling back
1008 // to the libcall when no load size fits. Because the greedy load sequence
1009 // only places a load of size S at an offset that is a multiple of S, a size
1010 // kept here is always accessible in that sequence; overlapping loads and
1011 // merged tail expansions are checked separately against their actual offsets
1012 // in MemCmpExpansion.
1013 const Align CommonAlign = std::min(a: getMemCmpArgAlignment(CI, ArgNo: 0, DL: *DL),
1014 b: getMemCmpArgAlignment(CI, ArgNo: 1, DL: *DL));
1015 // Remember the target's preferred load width before filtering inaccessible
1016 // sizes. It is also the maximum width of the value formed by packing the
1017 // surviving loads in one ordering-compare block.
1018 const unsigned MaxBytesPerBlock = Options.LoadSizes.front();
1019 llvm::erase_if(C&: Options.LoadSizes, P: [&](unsigned LoadSize) {
1020 return !isAccessAllowed(CI, TTI: *TTI, CommonAlign, LoadSize, /*Offset=*/0);
1021 });
1022 // If the filter removed every load size, bail out to the libcall: the
1023 // MemCmpExpansion constructor asserts that at least one load size remains.
1024 // In practice all in-tree targets include a byte load size, which is
1025 // accessible at any alignment and therefore always survives the filter.
1026 if (Options.LoadSizes.empty())
1027 return false;
1028
1029 MemCmpExpansion Expansion(CI, SizeVal, Options, IsUsedForZeroCmp, *DL, DTU,
1030 *TTI, CommonAlign, MaxBytesPerBlock);
1031
1032 // Don't expand if this will require more loads than desired by the target.
1033 if (Expansion.getNumLoads() == 0) {
1034 NumMemCmpGreaterThanMax++;
1035 return false;
1036 }
1037
1038 NumMemCmpInlined++;
1039
1040 if (Value *Res = Expansion.getMemCmpExpansion()) {
1041 // Replace call with result of expansion and erase call.
1042 CI->replaceAllUsesWith(V: Res);
1043 CI->eraseFromParent();
1044 }
1045
1046 return true;
1047}
1048
1049static PreservedAnalyses runImpl(Function &F, const TargetLibraryInfo *TLI,
1050 const TargetTransformInfo *TTI,
1051 ProfileSummaryInfo *PSI,
1052 BlockFrequencyInfo *BFI, DominatorTree *DT) {
1053 std::optional<DomTreeUpdater> DTU;
1054 if (DT)
1055 DTU.emplace(args&: DT, args: DomTreeUpdater::UpdateStrategy::Lazy);
1056
1057 const DataLayout& DL = F.getDataLayout();
1058 SmallVector<std::pair<CallInst *, LibFunc>, 8> MemCmpCalls;
1059 for (Instruction &I : instructions(F)) {
1060 if (auto *CI = dyn_cast<CallInst>(Val: &I)) {
1061 LibFunc Func = TLI->getLibFunc(CB: *CI);
1062 if (Func == LibFunc_memcmp || Func == LibFunc_bcmp)
1063 MemCmpCalls.push_back(Elt: {CI, Func});
1064 }
1065 }
1066
1067 const ScalarOptions &Opts = getScalarOptions(F);
1068 bool MadeChanges = false;
1069 for (const auto &[CI, Func] : MemCmpCalls) {
1070 if (expandMemCmp(Opts, CI, TTI, DL: &DL, PSI, BFI, DTU: DTU ? &*DTU : nullptr,
1071 IsBCmp: Func == LibFunc_bcmp))
1072 MadeChanges = true;
1073 }
1074
1075 if (MadeChanges)
1076 for (BasicBlock &BB : F)
1077 SimplifyInstructionsInBlock(BB: &BB);
1078 if (!MadeChanges)
1079 return PreservedAnalyses::all();
1080 PreservedAnalyses PA;
1081 PA.preserve<DominatorTreeAnalysis>();
1082 return PA;
1083}
1084
1085} // namespace
1086
1087PreservedAnalyses ExpandMemCmpPass::run(Function &F,
1088 FunctionAnalysisManager &FAM) {
1089 // Don't expand memcmp in sanitized functions — sanitizers intercept memcmp
1090 // calls to check for memory errors, and expanding would bypass that.
1091 if (F.hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
1092 F.hasFnAttribute(Kind: Attribute::SanitizeMemory) ||
1093 F.hasFnAttribute(Kind: Attribute::SanitizeThread) ||
1094 F.hasFnAttribute(Kind: Attribute::SanitizeConcurrency) ||
1095 F.hasFnAttribute(Kind: Attribute::SanitizeHWAddress))
1096 return PreservedAnalyses::all();
1097
1098 const auto &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
1099 const auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
1100 auto *PSI = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F)
1101 .getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
1102 BlockFrequencyInfo *BFI = (PSI && PSI->hasProfileSummary())
1103 ? &FAM.getResult<BlockFrequencyAnalysis>(IR&: F)
1104 : nullptr;
1105 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
1106
1107 return runImpl(F, TLI: &TLI, TTI: &TTI, PSI, BFI, DT);
1108}
1109