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