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