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