1//===- LowerMemIntrinsics.cpp ----------------------------------*- C++ -*--===//
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#include "llvm/Transforms/Utils/LowerMemIntrinsics.h"
10#include "llvm/Analysis/ScalarEvolution.h"
11#include "llvm/Analysis/TargetTransformInfo.h"
12#include "llvm/IR/IRBuilder.h"
13#include "llvm/IR/IntrinsicInst.h"
14#include "llvm/IR/MDBuilder.h"
15#include "llvm/IR/ProfDataUtils.h"
16#include "llvm/ProfileData/InstrProf.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/KnownBits.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Transforms/Utils/BasicBlockUtils.h"
21#include "llvm/Transforms/Utils/LoopUtils.h"
22#include <cmath>
23#include <limits>
24#include <optional>
25
26#define DEBUG_TYPE "lower-mem-intrinsics"
27
28using namespace llvm;
29
30/// \returns \p Len urem \p OpSize, checking for optimization opportunities.
31/// \p OpSizeVal must be the integer value of the \c ConstantInt \p OpSize.
32static Value *getRuntimeLoopRemainder(IRBuilderBase &B, Value *Len,
33 Value *OpSize, unsigned OpSizeVal) {
34 // For powers of 2, we can and by (OpSizeVal - 1) instead of using urem.
35 if (isPowerOf2_32(Value: OpSizeVal))
36 return B.CreateAnd(LHS: Len, RHS: OpSizeVal - 1);
37 return B.CreateURem(LHS: Len, RHS: OpSize);
38}
39
40/// \returns (\p Len udiv \p OpSize) mul \p OpSize, checking for optimization
41/// opportunities.
42/// If \p RTLoopRemainder is provided, it must be the result of
43/// \c getRuntimeLoopRemainder() with the same arguments.
44static Value *getRuntimeLoopUnits(IRBuilderBase &B, Value *Len, Value *OpSize,
45 unsigned OpSizeVal,
46 Value *RTLoopRemainder = nullptr) {
47 if (!RTLoopRemainder)
48 RTLoopRemainder = getRuntimeLoopRemainder(B, Len, OpSize, OpSizeVal);
49 return B.CreateSub(LHS: Len, RHS: RTLoopRemainder);
50}
51
52namespace {
53/// Container for the return values of insertLoopExpansion.
54struct LoopExpansionInfo {
55 /// The instruction at the end of the main loop body.
56 Instruction *MainLoopIP = nullptr;
57
58 /// The unit index in the main loop body.
59 Value *MainLoopIndex = nullptr;
60
61 /// The instruction at the end of the residual loop body. Can be nullptr if no
62 /// residual is required.
63 Instruction *ResidualLoopIP = nullptr;
64
65 /// The unit index in the residual loop body. Can be nullptr if no residual is
66 /// required.
67 Value *ResidualLoopIndex = nullptr;
68};
69
70std::optional<uint64_t> getAverageMemOpLoopTripCount(const MemIntrinsic &I) {
71 if (std::optional<uint64_t> EC = I.getFunction()->getEntryCount();
72 !EC || *EC == 0)
73 return std::nullopt;
74 if (const auto Len = I.getLengthInBytes())
75 return Len->getZExtValue();
76 uint64_t Total = 0;
77 SmallVector<InstrProfValueData> ProfData =
78 getValueProfDataFromInst(Inst: I, ValueKind: InstrProfValueKind::IPVK_MemOPSize,
79 MaxNumValueData: std::numeric_limits<uint32_t>::max(), TotalC&: Total);
80 if (!Total)
81 return std::nullopt;
82 uint64_t TripCount = 0;
83 for (const auto &P : ProfData)
84 TripCount += P.Count * P.Value;
85 return std::round(x: 1.0 * TripCount / Total);
86}
87
88} // namespace
89
90/// Insert the control flow and loop counters for a memcpy/memset loop
91/// expansion.
92///
93/// This function inserts IR corresponding to the following C code before
94/// \p InsertBefore:
95/// \code
96/// LoopUnits = (Len / MainLoopStep) * MainLoopStep;
97/// ResidualUnits = Len - LoopUnits;
98/// MainLoopIndex = 0;
99/// if (LoopUnits > 0) {
100/// do {
101/// // MainLoopIP
102/// MainLoopIndex += MainLoopStep;
103/// } while (MainLoopIndex < LoopUnits);
104/// }
105/// for (size_t i = 0; i < ResidualUnits; i += ResidualLoopStep) {
106/// ResidualLoopIndex = LoopUnits + i;
107/// // ResidualLoopIP
108/// }
109/// \endcode
110///
111/// \p MainLoopStep and \p ResidualLoopStep determine by how many "units" the
112/// loop index is increased in each iteration of the main and residual loops,
113/// respectively. In most cases, the "unit" will be bytes, but larger units are
114/// useful for lowering memset.pattern.
115///
116/// The computation of \c LoopUnits and \c ResidualUnits is performed at compile
117/// time if \p Len is a \c ConstantInt.
118/// The second (residual) loop is omitted if \p ResidualLoopStep is 0 or equal
119/// to \p MainLoopStep.
120/// The generated \c MainLoopIP, \c MainLoopIndex, \c ResidualLoopIP, and
121/// \c ResidualLoopIndex are returned in a \c LoopExpansionInfo object.
122///
123/// If provided, \p ExpectedUnits is used as the expected number of units
124/// handled by the loop expansion when computing branch weights.
125static LoopExpansionInfo
126insertLoopExpansion(Instruction *InsertBefore, Value *Len,
127 unsigned MainLoopStep, unsigned ResidualLoopStep,
128 StringRef BBNamePrefix,
129 std::optional<uint64_t> ExpectedUnits) {
130 assert((ResidualLoopStep == 0 || MainLoopStep % ResidualLoopStep == 0) &&
131 "ResidualLoopStep must divide MainLoopStep if specified");
132 assert(ResidualLoopStep <= MainLoopStep &&
133 "ResidualLoopStep cannot be larger than MainLoopStep");
134 assert(MainLoopStep > 0 && "MainLoopStep must be non-zero");
135 LoopExpansionInfo LEI;
136
137 // If the length is known to be zero, there is nothing to do.
138 if (auto *CLen = dyn_cast<ConstantInt>(Val: Len))
139 if (CLen->isZero())
140 return LEI;
141
142 BasicBlock *PreLoopBB = InsertBefore->getParent();
143 BasicBlock *PostLoopBB = PreLoopBB->splitBasicBlock(
144 I: InsertBefore, BBName: BBNamePrefix + "-post-expansion");
145 Function *ParentFunc = PreLoopBB->getParent();
146 LLVMContext &Ctx = PreLoopBB->getContext();
147 const DebugLoc &DbgLoc = InsertBefore->getDebugLoc();
148 IRBuilder<> PreLoopBuilder(PreLoopBB->getTerminator());
149 PreLoopBuilder.SetCurrentDebugLocation(DbgLoc);
150
151 // Calculate the main loop trip count and remaining units to cover after the
152 // loop.
153 Type *LenType = Len->getType();
154 IntegerType *ILenType = cast<IntegerType>(Val: LenType);
155 ConstantInt *CIMainLoopStep = ConstantInt::get(Ty: ILenType, V: MainLoopStep);
156 ConstantInt *Zero = ConstantInt::get(Ty: ILenType, V: 0U);
157
158 // We can avoid conditional branches and/or entire loops if we know any of the
159 // following:
160 // - that the main loop must be executed at least once
161 // - that the main loop will not be executed at all
162 // - that the residual loop must be executed at least once
163 // - that the residual loop will not be executed at all
164 bool MustTakeMainLoop = false;
165 bool MayTakeMainLoop = true;
166 bool MustTakeResidualLoop = false;
167 bool MayTakeResidualLoop = true;
168
169 Value *LoopUnits = Len;
170 Value *ResidualUnits = nullptr;
171 if (MainLoopStep != 1) {
172 if (auto *CLen = dyn_cast<ConstantInt>(Val: Len)) {
173 uint64_t TotalUnits = CLen->getZExtValue();
174 uint64_t LoopEndCount = alignDown(Value: TotalUnits, Align: MainLoopStep);
175 uint64_t ResidualCount = TotalUnits - LoopEndCount;
176 LoopUnits = ConstantInt::get(Ty: LenType, V: LoopEndCount);
177 ResidualUnits = ConstantInt::get(Ty: LenType, V: ResidualCount);
178 MustTakeMainLoop = LoopEndCount > 0;
179 MayTakeMainLoop = MustTakeMainLoop;
180 MustTakeResidualLoop = ResidualCount > 0;
181 MayTakeResidualLoop = MustTakeResidualLoop;
182 // TODO: This could also use known bits to check if a non-constant loop
183 // count is guaranteed to be a multiple of MainLoopStep, in which case we
184 // could omit the residual loop. It's unclear if that is worthwhile.
185 } else {
186 ResidualUnits = getRuntimeLoopRemainder(B&: PreLoopBuilder, Len,
187 OpSize: CIMainLoopStep, OpSizeVal: MainLoopStep);
188 LoopUnits = getRuntimeLoopUnits(B&: PreLoopBuilder, Len, OpSize: CIMainLoopStep,
189 OpSizeVal: MainLoopStep, RTLoopRemainder: ResidualUnits);
190 }
191 } else if (auto *CLen = dyn_cast<ConstantInt>(Val: Len)) {
192 MustTakeMainLoop = CLen->getZExtValue() > 0;
193 MayTakeMainLoop = MustTakeMainLoop;
194 }
195
196 // The case where both loops are omitted (i.e., the length is known zero) is
197 // already handled at the beginning of this function.
198 assert((MayTakeMainLoop || MayTakeResidualLoop) &&
199 "At least one of the loops must be generated");
200
201 BasicBlock *MainLoopBB = nullptr;
202 CondBrInst *MainLoopBr = nullptr;
203
204 // Construct the main loop unless we statically known that it is not taken.
205 if (MayTakeMainLoop) {
206 MainLoopBB = BasicBlock::Create(Context&: Ctx, Name: BBNamePrefix + "-expansion-main-body",
207 Parent: ParentFunc, InsertBefore: PostLoopBB);
208 IRBuilder<> LoopBuilder(MainLoopBB);
209 LoopBuilder.SetCurrentDebugLocation(DbgLoc);
210
211 PHINode *LoopIndex = LoopBuilder.CreatePHI(Ty: LenType, NumReservedValues: 2, Name: "loop-index");
212 LEI.MainLoopIndex = LoopIndex;
213 LoopIndex->addIncoming(V: ConstantInt::get(Ty: LenType, V: 0U), BB: PreLoopBB);
214
215 Value *NewIndex = LoopBuilder.CreateAdd(
216 LHS: LoopIndex, RHS: ConstantInt::get(Ty: LenType, V: MainLoopStep));
217 LoopIndex->addIncoming(V: NewIndex, BB: MainLoopBB);
218
219 // One argument of the addition is a loop-variant PHI, so it must be an
220 // Instruction (i.e., it cannot be a Constant).
221 LEI.MainLoopIP = cast<Instruction>(Val: NewIndex);
222
223 // Stay in the MainLoop until we have handled all the LoopUnits. The False
224 // target is adjusted below if a residual is generated.
225 MainLoopBr = LoopBuilder.CreateCondBr(
226 Cond: LoopBuilder.CreateICmpULT(LHS: NewIndex, RHS: LoopUnits), True: MainLoopBB, False: PostLoopBB);
227
228 if (ExpectedUnits.has_value()) {
229 uint64_t BackedgeTakenCount = ExpectedUnits.value() / MainLoopStep;
230 if (BackedgeTakenCount > 0)
231 BackedgeTakenCount -= 1; // The last iteration goes to the False target.
232 MDBuilder MDB(ParentFunc->getContext());
233 setFittedBranchWeights(I&: *MainLoopBr, Weights: {BackedgeTakenCount, 1},
234 /*IsExpected=*/false);
235 } else {
236 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *MainLoopBr, DEBUG_TYPE);
237 }
238 }
239
240 // Construct the residual loop if it is requested from the caller unless we
241 // statically know that it won't be taken.
242 bool ResidualLoopRequested =
243 ResidualLoopStep > 0 && ResidualLoopStep < MainLoopStep;
244 BasicBlock *ResidualLoopBB = nullptr;
245 BasicBlock *ResidualCondBB = nullptr;
246 if (ResidualLoopRequested && MayTakeResidualLoop) {
247 ResidualLoopBB =
248 BasicBlock::Create(Context&: Ctx, Name: BBNamePrefix + "-expansion-residual-body",
249 Parent: PreLoopBB->getParent(), InsertBefore: PostLoopBB);
250
251 // The residual loop body is either reached from the ResidualCondBB (which
252 // checks if the residual loop needs to be executed), from the main loop
253 // body if we know statically that the residual must be executed, or from
254 // the pre-loop BB (conditionally or unconditionally) if the main loop is
255 // omitted.
256 BasicBlock *PredOfResLoopBody = PreLoopBB;
257 if (MainLoopBB) {
258 // If it's statically known that the residual must be executed, we don't
259 // need to create a preheader BB.
260 if (MustTakeResidualLoop) {
261 MainLoopBr->setSuccessor(idx: 1, NewSucc: ResidualLoopBB);
262 PredOfResLoopBody = MainLoopBB;
263 } else {
264 // Construct a preheader BB to check if the residual loop is executed.
265 ResidualCondBB =
266 BasicBlock::Create(Context&: Ctx, Name: BBNamePrefix + "-expansion-residual-cond",
267 Parent: PreLoopBB->getParent(), InsertBefore: ResidualLoopBB);
268
269 // Determine if we need to branch to the residual loop or bypass it.
270 IRBuilder<> RCBuilder(ResidualCondBB);
271 RCBuilder.SetCurrentDebugLocation(DbgLoc);
272 auto *BR =
273 RCBuilder.CreateCondBr(Cond: RCBuilder.CreateICmpNE(LHS: ResidualUnits, RHS: Zero),
274 True: ResidualLoopBB, False: PostLoopBB);
275 if (ExpectedUnits.has_value()) {
276 MDBuilder MDB(ParentFunc->getContext());
277 BR->setMetadata(KindID: LLVMContext::MD_prof,
278 Node: MDB.createLikelyBranchWeights());
279 } else {
280 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
281 }
282
283 MainLoopBr->setSuccessor(idx: 1, NewSucc: ResidualCondBB);
284 PredOfResLoopBody = ResidualCondBB;
285 }
286 }
287
288 IRBuilder<> ResBuilder(ResidualLoopBB);
289 ResBuilder.SetCurrentDebugLocation(DbgLoc);
290 PHINode *ResidualIndex =
291 ResBuilder.CreatePHI(Ty: LenType, NumReservedValues: 2, Name: "residual-loop-index");
292 ResidualIndex->addIncoming(V: Zero, BB: PredOfResLoopBody);
293
294 // Add the offset at the end of the main loop to the loop counter of the
295 // residual loop to get the proper index. If the main loop was omitted, we
296 // can also omit the addition.
297 if (MainLoopBB)
298 LEI.ResidualLoopIndex = ResBuilder.CreateAdd(LHS: LoopUnits, RHS: ResidualIndex);
299 else
300 LEI.ResidualLoopIndex = ResidualIndex;
301
302 Value *ResNewIndex = ResBuilder.CreateAdd(
303 LHS: ResidualIndex, RHS: ConstantInt::get(Ty: LenType, V: ResidualLoopStep));
304 ResidualIndex->addIncoming(V: ResNewIndex, BB: ResidualLoopBB);
305
306 // One argument of the addition is a loop-variant PHI, so it must be an
307 // Instruction (i.e., it cannot be a Constant).
308 LEI.ResidualLoopIP = cast<Instruction>(Val: ResNewIndex);
309
310 // Stay in the residual loop until all ResidualUnits are handled.
311 CondBrInst *BR = ResBuilder.CreateCondBr(
312 Cond: ResBuilder.CreateICmpULT(LHS: ResNewIndex, RHS: ResidualUnits), True: ResidualLoopBB,
313 False: PostLoopBB);
314
315 if (ExpectedUnits.has_value()) {
316 uint64_t BackedgeTakenCount =
317 (ExpectedUnits.value() % MainLoopStep) / ResidualLoopStep;
318 if (BackedgeTakenCount > 0)
319 BackedgeTakenCount -= 1; // The last iteration goes to the False target.
320 MDBuilder MDB(ParentFunc->getContext());
321 setFittedBranchWeights(I&: *BR, Weights: {BackedgeTakenCount, 1},
322 /*IsExpected=*/false);
323 } else {
324 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
325 }
326 }
327
328 // Create the branch in the pre-loop block.
329 if (MustTakeMainLoop) {
330 // Go unconditionally to the main loop if it's statically known that it must
331 // be executed.
332 assert(MainLoopBB);
333 PreLoopBuilder.CreateBr(Dest: MainLoopBB);
334 } else if (!MainLoopBB && ResidualLoopBB) {
335 if (MustTakeResidualLoop) {
336 // If the main loop is omitted and the residual loop is statically known
337 // to be executed, go there unconditionally.
338 PreLoopBuilder.CreateBr(Dest: ResidualLoopBB);
339 } else {
340 // If the main loop is omitted and we don't know if the residual loop is
341 // executed, go there if necessary. The PreLoopBB takes the role of the
342 // preheader for the residual loop in this case.
343 auto *BR = PreLoopBuilder.CreateCondBr(
344 Cond: PreLoopBuilder.CreateICmpNE(LHS: ResidualUnits, RHS: Zero), True: ResidualLoopBB,
345 False: PostLoopBB);
346 if (ExpectedUnits.has_value()) {
347 MDBuilder MDB(ParentFunc->getContext());
348 BR->setMetadata(KindID: LLVMContext::MD_prof, Node: MDB.createLikelyBranchWeights());
349 } else {
350 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
351 }
352 }
353 } else {
354 // Otherwise, go conditionally to the main loop or its successor.
355 // If there is no residual loop, the successor is the post-loop BB.
356 BasicBlock *FalseBB = PostLoopBB;
357 if (ResidualCondBB) {
358 // If we constructed a pre-header for the residual loop, that is the
359 // successor.
360 FalseBB = ResidualCondBB;
361 } else if (ResidualLoopBB) {
362 // If there is a residual loop but the preheader is omitted (because the
363 // residual loop is statically known to be executed), the successor
364 // is the residual loop body.
365 assert(MustTakeResidualLoop);
366 FalseBB = ResidualLoopBB;
367 }
368
369 auto *BR = PreLoopBuilder.CreateCondBr(
370 Cond: PreLoopBuilder.CreateICmpNE(LHS: LoopUnits, RHS: Zero), True: MainLoopBB, False: FalseBB);
371
372 if (ExpectedUnits.has_value()) {
373 MDBuilder MDB(ParentFunc->getContext());
374 BR->setMetadata(KindID: LLVMContext::MD_prof, Node: MDB.createLikelyBranchWeights());
375 } else {
376 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *BR, DEBUG_TYPE);
377 }
378 }
379 // Delete the unconditional branch inserted by splitBasicBlock.
380 PreLoopBB->getTerminator()->eraseFromParent();
381
382 return LEI;
383}
384
385void llvm::createMemCpyLoopKnownSize(Instruction *InsertBefore, Value *SrcAddr,
386 Value *DstAddr, ConstantInt *CopyLen,
387 Align SrcAlign, Align DstAlign,
388 bool SrcIsVolatile, bool DstIsVolatile,
389 bool CanOverlap,
390 const TargetTransformInfo &TTI,
391 std::optional<uint32_t> AtomicElementSize,
392 std::optional<uint64_t> AverageTripCount) {
393 // No need to expand zero length copies.
394 if (CopyLen->isZero())
395 return;
396
397 BasicBlock *PreLoopBB = InsertBefore->getParent();
398 Function *ParentFunc = PreLoopBB->getParent();
399 LLVMContext &Ctx = PreLoopBB->getContext();
400 const DataLayout &DL = ParentFunc->getDataLayout();
401 MDBuilder MDB(Ctx);
402 MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain(Description: "MemCopyDomain");
403 StringRef Name = "MemCopyAliasScope";
404 MDNode *NewScope = MDB.createAnonymousAliasScope(Domain: NewDomain, Name);
405
406 unsigned SrcAS = cast<PointerType>(Val: SrcAddr->getType())->getAddressSpace();
407 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
408
409 Type *TypeOfCopyLen = CopyLen->getType();
410 Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
411 Context&: Ctx, Length: CopyLen, SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign, DestAlign: DstAlign, AtomicElementSize);
412 assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
413 "Atomic memcpy lowering is not supported for vector operand type");
414
415 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
416 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
417 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
418 assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
419 "Atomic memcpy lowering is not supported for selected operand size");
420
421 uint64_t LoopEndCount =
422 alignDown(Value: CopyLen->getZExtValue(), Align: LoopOpSize.getFixedValue());
423
424 // Skip the loop expansion entirely if the loop would never be taken.
425 if (LoopEndCount != 0) {
426 LoopExpansionInfo LEI =
427 insertLoopExpansion(InsertBefore, Len: CopyLen, MainLoopStep: LoopOpSize, ResidualLoopStep: 0,
428 BBNamePrefix: "static-memcpy", ExpectedUnits: AverageTripCount);
429 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
430 "Main loop should be generated for non-zero loop count");
431
432 // Fill MainLoopBB
433 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
434 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
435 Align PartSrcAlign(commonAlignment(A: SrcAlign, Offset: LoopOpSize));
436
437 // If we used LoopOpType as GEP element type, we would iterate over the
438 // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e.,
439 // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use
440 // byte offsets computed from the TypeStoreSize.
441 Value *SrcGEP =
442 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: LEI.MainLoopIndex);
443 LoadInst *Load = MainLoopBuilder.CreateAlignedLoad(
444 Ty: LoopOpType, Ptr: SrcGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile);
445 if (!CanOverlap) {
446 // Set alias scope for loads.
447 Load->setMetadata(KindID: LLVMContext::MD_alias_scope,
448 Node: MDNode::get(Context&: Ctx, MDs: NewScope));
449 }
450 Value *DstGEP =
451 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
452 StoreInst *Store = MainLoopBuilder.CreateAlignedStore(
453 Val: Load, Ptr: DstGEP, Align: PartDstAlign, isVolatile: DstIsVolatile);
454 if (!CanOverlap) {
455 // Indicate that stores don't overlap loads.
456 Store->setMetadata(KindID: LLVMContext::MD_noalias, Node: MDNode::get(Context&: Ctx, MDs: NewScope));
457 }
458 if (AtomicElementSize) {
459 Load->setAtomic(Ordering: AtomicOrdering::Unordered);
460 Store->setAtomic(Ordering: AtomicOrdering::Unordered);
461 }
462 assert(!LEI.ResidualLoopIP && !LEI.ResidualLoopIndex &&
463 "No residual loop was requested");
464 }
465
466 // Copy the remaining bytes with straight-line code.
467 uint64_t BytesCopied = LoopEndCount;
468 uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopied;
469 if (RemainingBytes == 0)
470 return;
471
472 IRBuilder<> RBuilder(InsertBefore);
473 SmallVector<Type *, 5> RemainingOps;
474 TTI.getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
475 SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign, DestAlign: DstAlign,
476 AtomicCpySize: AtomicElementSize);
477
478 for (auto *OpTy : RemainingOps) {
479 Align PartSrcAlign(commonAlignment(A: SrcAlign, Offset: BytesCopied));
480 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: BytesCopied));
481
482 TypeSize OperandSize = DL.getTypeStoreSize(Ty: OpTy);
483 assert((!AtomicElementSize || OperandSize % *AtomicElementSize == 0) &&
484 "Atomic memcpy lowering is not supported for selected operand size");
485
486 Value *SrcGEP = RBuilder.CreateInBoundsGEP(
487 Ty: Int8Type, Ptr: SrcAddr, IdxList: ConstantInt::get(Ty: TypeOfCopyLen, V: BytesCopied));
488 LoadInst *Load =
489 RBuilder.CreateAlignedLoad(Ty: OpTy, Ptr: SrcGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile);
490 if (!CanOverlap) {
491 // Set alias scope for loads.
492 Load->setMetadata(KindID: LLVMContext::MD_alias_scope,
493 Node: MDNode::get(Context&: Ctx, MDs: NewScope));
494 }
495 Value *DstGEP = RBuilder.CreateInBoundsGEP(
496 Ty: Int8Type, Ptr: DstAddr, IdxList: ConstantInt::get(Ty: TypeOfCopyLen, V: BytesCopied));
497 StoreInst *Store =
498 RBuilder.CreateAlignedStore(Val: Load, Ptr: DstGEP, Align: PartDstAlign, isVolatile: DstIsVolatile);
499 if (!CanOverlap) {
500 // Indicate that stores don't overlap loads.
501 Store->setMetadata(KindID: LLVMContext::MD_noalias, Node: MDNode::get(Context&: Ctx, MDs: NewScope));
502 }
503 if (AtomicElementSize) {
504 Load->setAtomic(Ordering: AtomicOrdering::Unordered);
505 Store->setAtomic(Ordering: AtomicOrdering::Unordered);
506 }
507 BytesCopied += OperandSize;
508 }
509 assert(BytesCopied == CopyLen->getZExtValue() &&
510 "Bytes copied should match size in the call!");
511}
512
513void llvm::createMemCpyLoopUnknownSize(
514 Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr, Value *CopyLen,
515 Align SrcAlign, Align DstAlign, bool SrcIsVolatile, bool DstIsVolatile,
516 bool CanOverlap, const TargetTransformInfo &TTI,
517 std::optional<uint32_t> AtomicElementSize,
518 std::optional<uint64_t> AverageTripCount) {
519 BasicBlock *PreLoopBB = InsertBefore->getParent();
520 Function *ParentFunc = PreLoopBB->getParent();
521 const DataLayout &DL = ParentFunc->getDataLayout();
522 LLVMContext &Ctx = PreLoopBB->getContext();
523 MDBuilder MDB(Ctx);
524 MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain(Description: "MemCopyDomain");
525 StringRef Name = "MemCopyAliasScope";
526 MDNode *NewScope = MDB.createAnonymousAliasScope(Domain: NewDomain, Name);
527
528 unsigned SrcAS = cast<PointerType>(Val: SrcAddr->getType())->getAddressSpace();
529 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
530
531 Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
532 Context&: Ctx, Length: CopyLen, SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign, DestAlign: DstAlign, AtomicElementSize);
533 assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
534 "Atomic memcpy lowering is not supported for vector operand type");
535 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
536 assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
537 "Atomic memcpy lowering is not supported for selected operand size");
538
539 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
540
541 Type *ResidualLoopOpType = AtomicElementSize
542 ? Type::getIntNTy(C&: Ctx, N: *AtomicElementSize * 8)
543 : Int8Type;
544 TypeSize ResidualLoopOpSize = DL.getTypeStoreSize(Ty: ResidualLoopOpType);
545 assert(ResidualLoopOpSize == (AtomicElementSize ? *AtomicElementSize : 1) &&
546 "Store size is expected to match type size");
547
548 LoopExpansionInfo LEI =
549 insertLoopExpansion(InsertBefore, Len: CopyLen, MainLoopStep: LoopOpSize, ResidualLoopStep: ResidualLoopOpSize,
550 BBNamePrefix: "dynamic-memcpy", ExpectedUnits: AverageTripCount);
551 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
552 "Main loop should be generated for unknown size copy");
553
554 // Fill MainLoopBB
555 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
556 Align PartSrcAlign(commonAlignment(A: SrcAlign, Offset: LoopOpSize));
557 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
558
559 // If we used LoopOpType as GEP element type, we would iterate over the
560 // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e.,
561 // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use byte
562 // offsets computed from the TypeStoreSize.
563 Value *SrcGEP =
564 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: LEI.MainLoopIndex);
565 LoadInst *Load = MainLoopBuilder.CreateAlignedLoad(
566 Ty: LoopOpType, Ptr: SrcGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile);
567 if (!CanOverlap) {
568 // Set alias scope for loads.
569 Load->setMetadata(KindID: LLVMContext::MD_alias_scope, Node: MDNode::get(Context&: Ctx, MDs: NewScope));
570 }
571 Value *DstGEP =
572 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
573 StoreInst *Store = MainLoopBuilder.CreateAlignedStore(
574 Val: Load, Ptr: DstGEP, Align: PartDstAlign, isVolatile: DstIsVolatile);
575 if (!CanOverlap) {
576 // Indicate that stores don't overlap loads.
577 Store->setMetadata(KindID: LLVMContext::MD_noalias, Node: MDNode::get(Context&: Ctx, MDs: NewScope));
578 }
579 if (AtomicElementSize) {
580 Load->setAtomic(Ordering: AtomicOrdering::Unordered);
581 Store->setAtomic(Ordering: AtomicOrdering::Unordered);
582 }
583
584 // Fill ResidualLoopBB.
585 if (!LEI.ResidualLoopIP)
586 return;
587
588 Align ResSrcAlign(commonAlignment(A: PartSrcAlign, Offset: ResidualLoopOpSize));
589 Align ResDstAlign(commonAlignment(A: PartDstAlign, Offset: ResidualLoopOpSize));
590
591 IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP);
592 Value *ResSrcGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr,
593 IdxList: LEI.ResidualLoopIndex);
594 LoadInst *ResLoad = ResLoopBuilder.CreateAlignedLoad(
595 Ty: ResidualLoopOpType, Ptr: ResSrcGEP, Align: ResSrcAlign, isVolatile: SrcIsVolatile);
596 if (!CanOverlap) {
597 // Set alias scope for loads.
598 ResLoad->setMetadata(KindID: LLVMContext::MD_alias_scope,
599 Node: MDNode::get(Context&: Ctx, MDs: NewScope));
600 }
601 Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr,
602 IdxList: LEI.ResidualLoopIndex);
603 StoreInst *ResStore = ResLoopBuilder.CreateAlignedStore(
604 Val: ResLoad, Ptr: ResDstGEP, Align: ResDstAlign, isVolatile: DstIsVolatile);
605 if (!CanOverlap) {
606 // Indicate that stores don't overlap loads.
607 ResStore->setMetadata(KindID: LLVMContext::MD_noalias, Node: MDNode::get(Context&: Ctx, MDs: NewScope));
608 }
609 if (AtomicElementSize) {
610 ResLoad->setAtomic(Ordering: AtomicOrdering::Unordered);
611 ResStore->setAtomic(Ordering: AtomicOrdering::Unordered);
612 }
613}
614
615// If \p Addr1 and \p Addr2 are pointers to different address spaces, create an
616// addresspacecast to obtain a pair of pointers in the same addressspace. The
617// caller needs to ensure that addrspacecasting is possible.
618// No-op if the pointers are in the same address space.
619static std::pair<Value *, Value *>
620tryInsertCastToCommonAddrSpace(IRBuilderBase &B, Value *Addr1, Value *Addr2,
621 const TargetTransformInfo &TTI) {
622 Value *ResAddr1 = Addr1;
623 Value *ResAddr2 = Addr2;
624
625 unsigned AS1 = cast<PointerType>(Val: Addr1->getType())->getAddressSpace();
626 unsigned AS2 = cast<PointerType>(Val: Addr2->getType())->getAddressSpace();
627 if (AS1 != AS2) {
628 if (TTI.isValidAddrSpaceCast(FromAS: AS2, ToAS: AS1))
629 ResAddr2 = B.CreateAddrSpaceCast(V: Addr2, DestTy: Addr1->getType());
630 else if (TTI.isValidAddrSpaceCast(FromAS: AS1, ToAS: AS2))
631 ResAddr1 = B.CreateAddrSpaceCast(V: Addr1, DestTy: Addr2->getType());
632 else
633 llvm_unreachable("Can only lower memmove between address spaces if they "
634 "support addrspacecast");
635 }
636 return {ResAddr1, ResAddr2};
637}
638
639// Lower memmove to IR. memmove is required to correctly copy overlapping memory
640// regions; therefore, it has to check the relative positions of the source and
641// destination pointers and choose the copy direction accordingly.
642//
643// The code below is an IR rendition of this C function:
644//
645// void* memmove(void* dst, const void* src, size_t n) {
646// unsigned char* d = dst;
647// const unsigned char* s = src;
648// if (s < d) {
649// // copy backwards
650// while (n--) {
651// d[n] = s[n];
652// }
653// } else {
654// // copy forward
655// for (size_t i = 0; i < n; ++i) {
656// d[i] = s[i];
657// }
658// }
659// return dst;
660// }
661//
662// If the TargetTransformInfo specifies a wider MemcpyLoopLoweringType, it is
663// used for the memory accesses in the loops. Then, additional loops with
664// byte-wise accesses are added for the remaining bytes.
665static void createMemMoveLoopUnknownSize(Instruction *InsertBefore,
666 Value *SrcAddr, Value *DstAddr,
667 Value *CopyLen, Align SrcAlign,
668 Align DstAlign, bool SrcIsVolatile,
669 bool DstIsVolatile,
670 const TargetTransformInfo &TTI) {
671 Type *TypeOfCopyLen = CopyLen->getType();
672 BasicBlock *OrigBB = InsertBefore->getParent();
673 Function *F = OrigBB->getParent();
674 const DataLayout &DL = F->getDataLayout();
675 LLVMContext &Ctx = OrigBB->getContext();
676 unsigned SrcAS = cast<PointerType>(Val: SrcAddr->getType())->getAddressSpace();
677 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
678
679 Type *LoopOpType = TTI.getMemcpyLoopLoweringType(Context&: Ctx, Length: CopyLen, SrcAddrSpace: SrcAS, DestAddrSpace: DstAS,
680 SrcAlign, DestAlign: DstAlign);
681 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
682 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
683 bool LoopOpIsInt8 = LoopOpType == Int8Type;
684
685 // If the memory accesses are wider than one byte, residual loops with
686 // i8-accesses are required to move remaining bytes.
687 bool RequiresResidual = !LoopOpIsInt8;
688
689 Type *ResidualLoopOpType = Int8Type;
690 TypeSize ResidualLoopOpSize = DL.getTypeStoreSize(Ty: ResidualLoopOpType);
691
692 // Calculate the loop trip count and remaining bytes to copy after the loop.
693 IntegerType *ILengthType = cast<IntegerType>(Val: TypeOfCopyLen);
694 ConstantInt *CILoopOpSize = ConstantInt::get(Ty: ILengthType, V: LoopOpSize);
695 ConstantInt *CIResidualLoopOpSize =
696 ConstantInt::get(Ty: ILengthType, V: ResidualLoopOpSize);
697 ConstantInt *Zero = ConstantInt::get(Ty: ILengthType, V: 0);
698
699 const DebugLoc &DbgLoc = InsertBefore->getDebugLoc();
700 IRBuilder<> PLBuilder(InsertBefore);
701 PLBuilder.SetCurrentDebugLocation(DbgLoc);
702
703 Value *RuntimeLoopBytes = CopyLen;
704 Value *RuntimeLoopRemainder = nullptr;
705 Value *SkipResidualCondition = nullptr;
706 if (RequiresResidual) {
707 RuntimeLoopRemainder =
708 getRuntimeLoopRemainder(B&: PLBuilder, Len: CopyLen, OpSize: CILoopOpSize, OpSizeVal: LoopOpSize);
709 RuntimeLoopBytes = getRuntimeLoopUnits(B&: PLBuilder, Len: CopyLen, OpSize: CILoopOpSize,
710 OpSizeVal: LoopOpSize, RTLoopRemainder: RuntimeLoopRemainder);
711 SkipResidualCondition =
712 PLBuilder.CreateICmpEQ(LHS: RuntimeLoopRemainder, RHS: Zero, Name: "skip_residual");
713 }
714 Value *SkipMainCondition =
715 PLBuilder.CreateICmpEQ(LHS: RuntimeLoopBytes, RHS: Zero, Name: "skip_main");
716
717 // Create the a comparison of src and dst, based on which we jump to either
718 // the forward-copy part of the function (if src >= dst) or the backwards-copy
719 // part (if src < dst).
720 // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
721 // structure. Its block terminators (unconditional branches) are replaced by
722 // the appropriate conditional branches when the loop is built.
723 // If the pointers are in different address spaces, they need to be converted
724 // to a compatible one. Cases where memory ranges in the different address
725 // spaces cannot overlap are lowered as memcpy and not handled here.
726 auto [CmpSrcAddr, CmpDstAddr] =
727 tryInsertCastToCommonAddrSpace(B&: PLBuilder, Addr1: SrcAddr, Addr2: DstAddr, TTI);
728 Value *PtrCompare =
729 PLBuilder.CreateICmpULT(LHS: CmpSrcAddr, RHS: CmpDstAddr, Name: "compare_src_dst");
730 Instruction *ThenTerm, *ElseTerm;
731 SplitBlockAndInsertIfThenElse(Cond: PtrCompare, SplitBefore: InsertBefore->getIterator(),
732 ThenTerm: &ThenTerm, ElseTerm: &ElseTerm);
733
734 // If the LoopOpSize is greater than 1, each part of the function consists of
735 // four blocks:
736 // memmove_copy_backwards:
737 // skip the residual loop when 0 iterations are required
738 // memmove_bwd_residual_loop:
739 // copy the last few bytes individually so that the remaining length is
740 // a multiple of the LoopOpSize
741 // memmove_bwd_middle: skip the main loop when 0 iterations are required
742 // memmove_bwd_main_loop: the actual backwards loop BB with wide accesses
743 // memmove_copy_forward: skip the main loop when 0 iterations are required
744 // memmove_fwd_main_loop: the actual forward loop BB with wide accesses
745 // memmove_fwd_middle: skip the residual loop when 0 iterations are required
746 // memmove_fwd_residual_loop: copy the last few bytes individually
747 //
748 // The main and residual loop are switched between copying forward and
749 // backward so that the residual loop always operates on the end of the moved
750 // range. This is based on the assumption that buffers whose start is aligned
751 // with the LoopOpSize are more common than buffers whose end is.
752 //
753 // If the LoopOpSize is 1, each part of the function consists of two blocks:
754 // memmove_copy_backwards: skip the loop when 0 iterations are required
755 // memmove_bwd_main_loop: the actual backwards loop BB
756 // memmove_copy_forward: skip the loop when 0 iterations are required
757 // memmove_fwd_main_loop: the actual forward loop BB
758 BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
759 CopyBackwardsBB->setName("memmove_copy_backwards");
760 BasicBlock *CopyForwardBB = ElseTerm->getParent();
761 CopyForwardBB->setName("memmove_copy_forward");
762 BasicBlock *ExitBB = InsertBefore->getParent();
763 ExitBB->setName("memmove_done");
764
765 Align PartSrcAlign(commonAlignment(A: SrcAlign, Offset: LoopOpSize));
766 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
767
768 // Accesses in the residual loops do not share the same alignment as those in
769 // the main loops.
770 Align ResidualSrcAlign(commonAlignment(A: PartSrcAlign, Offset: ResidualLoopOpSize));
771 Align ResidualDstAlign(commonAlignment(A: PartDstAlign, Offset: ResidualLoopOpSize));
772
773 // Copying backwards.
774 {
775 BasicBlock *MainLoopBB = BasicBlock::Create(
776 Context&: F->getContext(), Name: "memmove_bwd_main_loop", Parent: F, InsertBefore: CopyForwardBB);
777
778 // The predecessor of the memmove_bwd_main_loop. Updated in the
779 // following if a residual loop is emitted first.
780 BasicBlock *PredBB = CopyBackwardsBB;
781
782 if (RequiresResidual) {
783 // backwards residual loop
784 BasicBlock *ResidualLoopBB = BasicBlock::Create(
785 Context&: F->getContext(), Name: "memmove_bwd_residual_loop", Parent: F, InsertBefore: MainLoopBB);
786 IRBuilder<> ResidualLoopBuilder(ResidualLoopBB);
787 ResidualLoopBuilder.SetCurrentDebugLocation(DbgLoc);
788 PHINode *ResidualLoopPhi = ResidualLoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0);
789 Value *ResidualIndex = ResidualLoopBuilder.CreateSub(
790 LHS: ResidualLoopPhi, RHS: CIResidualLoopOpSize, Name: "bwd_residual_index");
791 // If we used LoopOpType as GEP element type, we would iterate over the
792 // buffers in TypeStoreSize strides while copying TypeAllocSize bytes,
793 // i.e., we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore,
794 // use byte offsets computed from the TypeStoreSize.
795 Value *LoadGEP = ResidualLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr,
796 IdxList: ResidualIndex);
797 Value *Element = ResidualLoopBuilder.CreateAlignedLoad(
798 Ty: ResidualLoopOpType, Ptr: LoadGEP, Align: ResidualSrcAlign, isVolatile: SrcIsVolatile,
799 Name: "element");
800 Value *StoreGEP = ResidualLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr,
801 IdxList: ResidualIndex);
802 ResidualLoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP,
803 Align: ResidualDstAlign, isVolatile: DstIsVolatile);
804
805 // After the residual loop, go to an intermediate block.
806 BasicBlock *IntermediateBB = BasicBlock::Create(
807 Context&: F->getContext(), Name: "memmove_bwd_middle", Parent: F, InsertBefore: MainLoopBB);
808 // Later code expects a terminator in the PredBB.
809 IRBuilder<> IntermediateBuilder(IntermediateBB);
810 IntermediateBuilder.SetCurrentDebugLocation(DbgLoc);
811 IntermediateBuilder.CreateUnreachable();
812 ResidualLoopBuilder.CreateCondBr(
813 Cond: ResidualLoopBuilder.CreateICmpEQ(LHS: ResidualIndex, RHS: RuntimeLoopBytes),
814 True: IntermediateBB, False: ResidualLoopBB);
815
816 ResidualLoopPhi->addIncoming(V: ResidualIndex, BB: ResidualLoopBB);
817 ResidualLoopPhi->addIncoming(V: CopyLen, BB: CopyBackwardsBB);
818
819 // How to get to the residual:
820 CondBrInst *BrInst =
821 CondBrInst::Create(Cond: SkipResidualCondition, IfTrue: IntermediateBB,
822 IfFalse: ResidualLoopBB, InsertBefore: ThenTerm->getIterator());
823 BrInst->setDebugLoc(DbgLoc);
824 ThenTerm->eraseFromParent();
825
826 PredBB = IntermediateBB;
827 }
828
829 // main loop
830 IRBuilder<> MainLoopBuilder(MainLoopBB);
831 MainLoopBuilder.SetCurrentDebugLocation(DbgLoc);
832 PHINode *MainLoopPhi = MainLoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0);
833 Value *MainIndex =
834 MainLoopBuilder.CreateSub(LHS: MainLoopPhi, RHS: CILoopOpSize, Name: "bwd_main_index");
835 Value *LoadGEP =
836 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: MainIndex);
837 Value *Element = MainLoopBuilder.CreateAlignedLoad(
838 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
839 Value *StoreGEP =
840 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: MainIndex);
841 MainLoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
842 isVolatile: DstIsVolatile);
843 MainLoopBuilder.CreateCondBr(Cond: MainLoopBuilder.CreateICmpEQ(LHS: MainIndex, RHS: Zero),
844 True: ExitBB, False: MainLoopBB);
845 MainLoopPhi->addIncoming(V: MainIndex, BB: MainLoopBB);
846 MainLoopPhi->addIncoming(V: RuntimeLoopBytes, BB: PredBB);
847
848 // How to get to the main loop:
849 Instruction *PredBBTerm = PredBB->getTerminator();
850 CondBrInst *BrInst = CondBrInst::Create(
851 Cond: SkipMainCondition, IfTrue: ExitBB, IfFalse: MainLoopBB, InsertBefore: PredBBTerm->getIterator());
852 BrInst->setDebugLoc(DbgLoc);
853 PredBBTerm->eraseFromParent();
854 }
855
856 // Copying forward.
857 // main loop
858 {
859 BasicBlock *MainLoopBB =
860 BasicBlock::Create(Context&: F->getContext(), Name: "memmove_fwd_main_loop", Parent: F, InsertBefore: ExitBB);
861 IRBuilder<> MainLoopBuilder(MainLoopBB);
862 MainLoopBuilder.SetCurrentDebugLocation(DbgLoc);
863 PHINode *MainLoopPhi =
864 MainLoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0, Name: "fwd_main_index");
865 Value *LoadGEP =
866 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: MainLoopPhi);
867 Value *Element = MainLoopBuilder.CreateAlignedLoad(
868 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
869 Value *StoreGEP =
870 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: MainLoopPhi);
871 MainLoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
872 isVolatile: DstIsVolatile);
873 Value *MainIndex = MainLoopBuilder.CreateAdd(LHS: MainLoopPhi, RHS: CILoopOpSize);
874 MainLoopPhi->addIncoming(V: MainIndex, BB: MainLoopBB);
875 MainLoopPhi->addIncoming(V: Zero, BB: CopyForwardBB);
876
877 Instruction *CopyFwdBBTerm = CopyForwardBB->getTerminator();
878 BasicBlock *SuccessorBB = ExitBB;
879 if (RequiresResidual)
880 SuccessorBB =
881 BasicBlock::Create(Context&: F->getContext(), Name: "memmove_fwd_middle", Parent: F, InsertBefore: ExitBB);
882
883 // leaving or staying in the main loop
884 MainLoopBuilder.CreateCondBr(
885 Cond: MainLoopBuilder.CreateICmpEQ(LHS: MainIndex, RHS: RuntimeLoopBytes), True: SuccessorBB,
886 False: MainLoopBB);
887
888 // getting in or skipping the main loop
889 CondBrInst *BrInst =
890 CondBrInst::Create(Cond: SkipMainCondition, IfTrue: SuccessorBB, IfFalse: MainLoopBB,
891 InsertBefore: CopyFwdBBTerm->getIterator());
892 BrInst->setDebugLoc(DbgLoc);
893 CopyFwdBBTerm->eraseFromParent();
894
895 if (RequiresResidual) {
896 BasicBlock *IntermediateBB = SuccessorBB;
897 IRBuilder<> IntermediateBuilder(IntermediateBB);
898 IntermediateBuilder.SetCurrentDebugLocation(DbgLoc);
899 BasicBlock *ResidualLoopBB = BasicBlock::Create(
900 Context&: F->getContext(), Name: "memmove_fwd_residual_loop", Parent: F, InsertBefore: ExitBB);
901 IntermediateBuilder.CreateCondBr(Cond: SkipResidualCondition, True: ExitBB,
902 False: ResidualLoopBB);
903
904 // Residual loop
905 IRBuilder<> ResidualLoopBuilder(ResidualLoopBB);
906 ResidualLoopBuilder.SetCurrentDebugLocation(DbgLoc);
907 PHINode *ResidualLoopPhi =
908 ResidualLoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0, Name: "fwd_residual_index");
909 Value *LoadGEP = ResidualLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr,
910 IdxList: ResidualLoopPhi);
911 Value *Element = ResidualLoopBuilder.CreateAlignedLoad(
912 Ty: ResidualLoopOpType, Ptr: LoadGEP, Align: ResidualSrcAlign, isVolatile: SrcIsVolatile,
913 Name: "element");
914 Value *StoreGEP = ResidualLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr,
915 IdxList: ResidualLoopPhi);
916 ResidualLoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP,
917 Align: ResidualDstAlign, isVolatile: DstIsVolatile);
918 Value *ResidualIndex =
919 ResidualLoopBuilder.CreateAdd(LHS: ResidualLoopPhi, RHS: CIResidualLoopOpSize);
920 ResidualLoopBuilder.CreateCondBr(
921 Cond: ResidualLoopBuilder.CreateICmpEQ(LHS: ResidualIndex, RHS: CopyLen), True: ExitBB,
922 False: ResidualLoopBB);
923 ResidualLoopPhi->addIncoming(V: ResidualIndex, BB: ResidualLoopBB);
924 ResidualLoopPhi->addIncoming(V: RuntimeLoopBytes, BB: IntermediateBB);
925 }
926 }
927}
928
929// Similar to createMemMoveLoopUnknownSize, only the trip counts are computed at
930// compile time, obsolete loops and branches are omitted, and the residual code
931// is straight-line code instead of a loop.
932static void createMemMoveLoopKnownSize(Instruction *InsertBefore,
933 Value *SrcAddr, Value *DstAddr,
934 ConstantInt *CopyLen, Align SrcAlign,
935 Align DstAlign, bool SrcIsVolatile,
936 bool DstIsVolatile,
937 const TargetTransformInfo &TTI) {
938 // No need to expand zero length moves.
939 if (CopyLen->isZero())
940 return;
941
942 Type *TypeOfCopyLen = CopyLen->getType();
943 BasicBlock *OrigBB = InsertBefore->getParent();
944 Function *F = OrigBB->getParent();
945 const DataLayout &DL = F->getDataLayout();
946 LLVMContext &Ctx = OrigBB->getContext();
947 unsigned SrcAS = cast<PointerType>(Val: SrcAddr->getType())->getAddressSpace();
948 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
949
950 Type *LoopOpType = TTI.getMemcpyLoopLoweringType(Context&: Ctx, Length: CopyLen, SrcAddrSpace: SrcAS, DestAddrSpace: DstAS,
951 SrcAlign, DestAlign: DstAlign);
952 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
953 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
954 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
955
956 // Calculate the loop trip count and remaining bytes to copy after the loop.
957 uint64_t BytesCopiedInLoop =
958 alignDown(Value: CopyLen->getZExtValue(), Align: LoopOpSize.getFixedValue());
959 uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopiedInLoop;
960
961 IntegerType *ILengthType = cast<IntegerType>(Val: TypeOfCopyLen);
962 ConstantInt *Zero = ConstantInt::get(Ty: ILengthType, V: 0);
963 ConstantInt *LoopBound = ConstantInt::get(Ty: ILengthType, V: BytesCopiedInLoop);
964 ConstantInt *CILoopOpSize = ConstantInt::get(Ty: ILengthType, V: LoopOpSize);
965
966 const DebugLoc &DbgLoc = InsertBefore->getDebugLoc();
967 IRBuilder<> PLBuilder(InsertBefore);
968 PLBuilder.SetCurrentDebugLocation(DbgLoc);
969
970 auto [CmpSrcAddr, CmpDstAddr] =
971 tryInsertCastToCommonAddrSpace(B&: PLBuilder, Addr1: SrcAddr, Addr2: DstAddr, TTI);
972 Value *PtrCompare =
973 PLBuilder.CreateICmpULT(LHS: CmpSrcAddr, RHS: CmpDstAddr, Name: "compare_src_dst");
974 Instruction *ThenTerm, *ElseTerm;
975 SplitBlockAndInsertIfThenElse(Cond: PtrCompare, SplitBefore: InsertBefore->getIterator(),
976 ThenTerm: &ThenTerm, ElseTerm: &ElseTerm);
977
978 BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
979 BasicBlock *CopyForwardBB = ElseTerm->getParent();
980 BasicBlock *ExitBB = InsertBefore->getParent();
981 ExitBB->setName("memmove_done");
982
983 Align PartSrcAlign(commonAlignment(A: SrcAlign, Offset: LoopOpSize));
984 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
985
986 // Helper function to generate a load/store pair of a given type in the
987 // residual. Used in the forward and backward branches.
988 auto GenerateResidualLdStPair = [&](Type *OpTy, IRBuilderBase &Builder,
989 uint64_t &BytesCopied) {
990 Align ResSrcAlign(commonAlignment(A: SrcAlign, Offset: BytesCopied));
991 Align ResDstAlign(commonAlignment(A: DstAlign, Offset: BytesCopied));
992
993 TypeSize OperandSize = DL.getTypeStoreSize(Ty: OpTy);
994
995 // If we used LoopOpType as GEP element type, we would iterate over the
996 // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e.,
997 // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use
998 // byte offsets computed from the TypeStoreSize.
999 Value *SrcGEP = Builder.CreateInBoundsGEP(
1000 Ty: Int8Type, Ptr: SrcAddr, IdxList: ConstantInt::get(Ty: TypeOfCopyLen, V: BytesCopied));
1001 LoadInst *Load =
1002 Builder.CreateAlignedLoad(Ty: OpTy, Ptr: SrcGEP, Align: ResSrcAlign, isVolatile: SrcIsVolatile);
1003 Value *DstGEP = Builder.CreateInBoundsGEP(
1004 Ty: Int8Type, Ptr: DstAddr, IdxList: ConstantInt::get(Ty: TypeOfCopyLen, V: BytesCopied));
1005 Builder.CreateAlignedStore(Val: Load, Ptr: DstGEP, Align: ResDstAlign, isVolatile: DstIsVolatile);
1006 BytesCopied += OperandSize;
1007 };
1008
1009 // Copying backwards.
1010 if (RemainingBytes != 0) {
1011 CopyBackwardsBB->setName("memmove_bwd_residual");
1012 uint64_t BytesCopied = BytesCopiedInLoop;
1013
1014 // Residual code is required to move the remaining bytes. We need the same
1015 // instructions as in the forward case, only in reverse. So we generate code
1016 // the same way, except that we change the IRBuilder insert point for each
1017 // load/store pair so that each one is inserted before the previous one
1018 // instead of after it.
1019 IRBuilder<> BwdResBuilder(CopyBackwardsBB->getFirstNonPHIIt());
1020 BwdResBuilder.SetCurrentDebugLocation(DbgLoc);
1021 SmallVector<Type *, 5> RemainingOps;
1022 TTI.getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1023 SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign: PartSrcAlign,
1024 DestAlign: PartDstAlign);
1025 for (auto *OpTy : RemainingOps) {
1026 // reverse the order of the emitted operations
1027 BwdResBuilder.SetInsertPoint(CopyBackwardsBB->getFirstNonPHIIt());
1028 GenerateResidualLdStPair(OpTy, BwdResBuilder, BytesCopied);
1029 }
1030 }
1031 if (BytesCopiedInLoop != 0) {
1032 BasicBlock *LoopBB = CopyBackwardsBB;
1033 BasicBlock *PredBB = OrigBB;
1034 if (RemainingBytes != 0) {
1035 // if we introduce residual code, it needs its separate BB
1036 LoopBB = CopyBackwardsBB->splitBasicBlock(
1037 I: CopyBackwardsBB->getTerminator(), BBName: "memmove_bwd_loop");
1038 PredBB = CopyBackwardsBB;
1039 } else {
1040 CopyBackwardsBB->setName("memmove_bwd_loop");
1041 }
1042 IRBuilder<> LoopBuilder(LoopBB->getTerminator());
1043 LoopBuilder.SetCurrentDebugLocation(DbgLoc);
1044 PHINode *LoopPhi = LoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0);
1045 Value *Index = LoopBuilder.CreateSub(LHS: LoopPhi, RHS: CILoopOpSize, Name: "bwd_index");
1046 Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: Index);
1047 Value *Element = LoopBuilder.CreateAlignedLoad(
1048 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
1049 Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: Index);
1050 LoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
1051 isVolatile: DstIsVolatile);
1052
1053 // Replace the unconditional branch introduced by
1054 // SplitBlockAndInsertIfThenElse to turn LoopBB into a loop.
1055 Instruction *UncondTerm = LoopBB->getTerminator();
1056 LoopBuilder.CreateCondBr(Cond: LoopBuilder.CreateICmpEQ(LHS: Index, RHS: Zero), True: ExitBB,
1057 False: LoopBB);
1058 UncondTerm->eraseFromParent();
1059
1060 LoopPhi->addIncoming(V: Index, BB: LoopBB);
1061 LoopPhi->addIncoming(V: LoopBound, BB: PredBB);
1062 }
1063
1064 // Copying forward.
1065 BasicBlock *FwdResidualBB = CopyForwardBB;
1066 if (BytesCopiedInLoop != 0) {
1067 CopyForwardBB->setName("memmove_fwd_loop");
1068 BasicBlock *LoopBB = CopyForwardBB;
1069 BasicBlock *SuccBB = ExitBB;
1070 if (RemainingBytes != 0) {
1071 // if we introduce residual code, it needs its separate BB
1072 SuccBB = CopyForwardBB->splitBasicBlock(I: CopyForwardBB->getTerminator(),
1073 BBName: "memmove_fwd_residual");
1074 FwdResidualBB = SuccBB;
1075 }
1076 IRBuilder<> LoopBuilder(LoopBB->getTerminator());
1077 LoopBuilder.SetCurrentDebugLocation(DbgLoc);
1078 PHINode *LoopPhi = LoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0, Name: "fwd_index");
1079 Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: LoopPhi);
1080 Value *Element = LoopBuilder.CreateAlignedLoad(
1081 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
1082 Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LoopPhi);
1083 LoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
1084 isVolatile: DstIsVolatile);
1085 Value *Index = LoopBuilder.CreateAdd(LHS: LoopPhi, RHS: CILoopOpSize);
1086 LoopPhi->addIncoming(V: Index, BB: LoopBB);
1087 LoopPhi->addIncoming(V: Zero, BB: OrigBB);
1088
1089 // Replace the unconditional branch to turn LoopBB into a loop.
1090 Instruction *UncondTerm = LoopBB->getTerminator();
1091 LoopBuilder.CreateCondBr(Cond: LoopBuilder.CreateICmpEQ(LHS: Index, RHS: LoopBound), True: SuccBB,
1092 False: LoopBB);
1093 UncondTerm->eraseFromParent();
1094 }
1095
1096 if (RemainingBytes != 0) {
1097 uint64_t BytesCopied = BytesCopiedInLoop;
1098
1099 // Residual code is required to move the remaining bytes. In the forward
1100 // case, we emit it in the normal order.
1101 IRBuilder<> FwdResBuilder(FwdResidualBB->getTerminator());
1102 FwdResBuilder.SetCurrentDebugLocation(DbgLoc);
1103 SmallVector<Type *, 5> RemainingOps;
1104 TTI.getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1105 SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign: PartSrcAlign,
1106 DestAlign: PartDstAlign);
1107 for (auto *OpTy : RemainingOps)
1108 GenerateResidualLdStPair(OpTy, FwdResBuilder, BytesCopied);
1109 }
1110}
1111
1112/// Create a Value of \p DstType that consists of a sequence of copies of
1113/// \p SetValue, using bitcasts and a vector splat.
1114static Value *createMemSetSplat(const DataLayout &DL, IRBuilderBase &B,
1115 Value *SetValue, Type *DstType) {
1116 TypeSize DstSize = DL.getTypeStoreSize(Ty: DstType);
1117 Type *SetValueType = SetValue->getType();
1118 TypeSize SetValueSize = DL.getTypeStoreSize(Ty: SetValueType);
1119 assert(SetValueSize == DL.getTypeAllocSize(SetValueType) &&
1120 "Store size and alloc size of SetValue's type must match");
1121 assert(SetValueSize != 0 && DstSize % SetValueSize == 0 &&
1122 "DstType size must be a multiple of SetValue size");
1123
1124 Value *Result = SetValue;
1125 if (DstSize != SetValueSize) {
1126 if (!SetValueType->isIntegerTy() && !SetValueType->isFloatingPointTy()) {
1127 // If the type cannot be put into a vector, bitcast to iN first.
1128 LLVMContext &Ctx = SetValue->getContext();
1129 Result = B.CreateBitCast(V: Result, DestTy: Type::getIntNTy(C&: Ctx, N: SetValueSize * 8),
1130 Name: "setvalue.toint");
1131 }
1132 // Form a sufficiently large vector consisting of SetValue, repeated.
1133 Result =
1134 B.CreateVectorSplat(NumElts: DstSize / SetValueSize, V: Result, Name: "setvalue.splat");
1135 }
1136
1137 // The value has the right size, but we might have to bitcast it to the right
1138 // type.
1139 Result = B.CreateBitCast(V: Result, DestTy: DstType, Name: "setvalue.splat.cast");
1140 return Result;
1141}
1142
1143static Value *createBoundedMemSetSplat(IRBuilderBase &B, Value *SetValue,
1144 uint64_t Size) {
1145 if (Size == 1)
1146 return SetValue;
1147 if (Size <= 8) {
1148 Type *IntTy = B.getIntNTy(N: Size * 8);
1149 return B.CreateMul(
1150 LHS: B.CreateZExt(V: SetValue, DestTy: IntTy, Name: "setvalue.zext"),
1151 RHS: ConstantInt::get(Ty: IntTy, V: APInt::getSplat(NewLen: Size * 8, V: APInt(8, 1))),
1152 Name: "setvalue.splat");
1153 }
1154 return B.CreateVectorSplat(NumElts: Size, V: SetValue, Name: "setvalue.splat");
1155}
1156
1157static void
1158createMemSetLoopKnownSize(Instruction *InsertBefore, Value *DstAddr,
1159 ConstantInt *Len, Value *SetValue, Align DstAlign,
1160 bool IsVolatile, const TargetTransformInfo *TTI,
1161 std::optional<uint64_t> AverageTripCount) {
1162 // No need to expand zero length memsets.
1163 if (Len->isZero())
1164 return;
1165
1166 BasicBlock *PreLoopBB = InsertBefore->getParent();
1167 Function *ParentFunc = PreLoopBB->getParent();
1168 const DataLayout &DL = ParentFunc->getDataLayout();
1169 LLVMContext &Ctx = PreLoopBB->getContext();
1170
1171 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1172
1173 Type *TypeOfLen = Len->getType();
1174 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
1175 assert(SetValue->getType() == Int8Type && "Can only set bytes");
1176
1177 Type *LoopOpType = Int8Type;
1178 if (TTI) {
1179 // Use the same memory access type as for a memcpy with the same Dst and Src
1180 // alignment and address space.
1181 LoopOpType = TTI->getMemcpyLoopLoweringType(
1182 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1183 }
1184 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
1185 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
1186
1187 uint64_t LoopEndCount =
1188 alignDown(Value: Len->getZExtValue(), Align: LoopOpSize.getFixedValue());
1189
1190 if (LoopEndCount != 0) {
1191 Value *SplatSetValue = nullptr;
1192 {
1193 IRBuilder<> PreLoopBuilder(InsertBefore);
1194 SplatSetValue =
1195 createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: LoopOpType);
1196 }
1197
1198 // Don't generate a residual loop, the remaining bytes are set with
1199 // straight-line code.
1200 LoopExpansionInfo LEI = insertLoopExpansion(
1201 InsertBefore, Len, MainLoopStep: LoopOpSize, ResidualLoopStep: 0, BBNamePrefix: "static-memset", ExpectedUnits: AverageTripCount);
1202 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
1203 "Main loop should be generated for non-zero loop count");
1204
1205 // Fill MainLoopBB
1206 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1207 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
1208
1209 Value *DstGEP =
1210 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
1211
1212 MainLoopBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1213 isVolatile: IsVolatile);
1214
1215 assert(!LEI.ResidualLoopIP && !LEI.ResidualLoopIndex &&
1216 "No residual loop was requested");
1217 }
1218
1219 uint64_t BytesSet = LoopEndCount;
1220 uint64_t RemainingBytes = Len->getZExtValue() - BytesSet;
1221 if (RemainingBytes == 0)
1222 return;
1223
1224 IRBuilder<> RBuilder(InsertBefore);
1225
1226 assert(TTI && "there cannot be a residual loop without TTI");
1227 SmallVector<Type *, 5> RemainingOps;
1228 TTI->getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1229 SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign,
1230 AtomicCpySize: std::nullopt);
1231
1232 Type *PreviousOpTy = nullptr;
1233 Value *SplatSetValue = nullptr;
1234 for (auto *OpTy : RemainingOps) {
1235 TypeSize OperandSize = DL.getTypeStoreSize(Ty: OpTy);
1236 assert(OperandSize.isFixed() &&
1237 "Operand types cannot be scalable vector types");
1238 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: BytesSet));
1239
1240 // Avoid recomputing the splat SetValue if it's the same as for the last
1241 // iteration.
1242 if (OpTy != PreviousOpTy)
1243 SplatSetValue = createMemSetSplat(DL, B&: RBuilder, SetValue, DstType: OpTy);
1244
1245 Value *DstGEP = RBuilder.CreateInBoundsGEP(
1246 Ty: Int8Type, Ptr: DstAddr, IdxList: ConstantInt::get(Ty: TypeOfLen, V: BytesSet));
1247 RBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1248 isVolatile: IsVolatile);
1249 BytesSet += OperandSize;
1250 PreviousOpTy = OpTy;
1251 }
1252 assert(BytesSet == Len->getZExtValue() &&
1253 "Bytes set should match size in the call!");
1254}
1255
1256static void
1257createMemSetLoopUnknownSize(Instruction *InsertBefore, Value *DstAddr,
1258 Value *Len, Value *SetValue, Align DstAlign,
1259 bool IsVolatile, const TargetTransformInfo *TTI,
1260 std::optional<uint64_t> AverageTripCount) {
1261 BasicBlock *PreLoopBB = InsertBefore->getParent();
1262 Function *ParentFunc = PreLoopBB->getParent();
1263 const DataLayout &DL = ParentFunc->getDataLayout();
1264 LLVMContext &Ctx = PreLoopBB->getContext();
1265
1266 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1267
1268 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
1269 assert(SetValue->getType() == Int8Type && "Can only set bytes");
1270
1271 Type *LoopOpType = Int8Type;
1272 if (TTI) {
1273 LoopOpType = TTI->getMemcpyLoopLoweringType(
1274 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1275 }
1276 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
1277 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
1278
1279 Type *ResidualLoopOpType = Int8Type;
1280 TypeSize ResidualLoopOpSize = DL.getTypeStoreSize(Ty: ResidualLoopOpType);
1281
1282 Value *SplatSetValue = SetValue;
1283 {
1284 IRBuilder<> PreLoopBuilder(InsertBefore);
1285 SplatSetValue = createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: LoopOpType);
1286 }
1287
1288 LoopExpansionInfo LEI =
1289 insertLoopExpansion(InsertBefore, Len, MainLoopStep: LoopOpSize, ResidualLoopStep: ResidualLoopOpSize,
1290 BBNamePrefix: "dynamic-memset", ExpectedUnits: AverageTripCount);
1291 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
1292 "Main loop should be generated for unknown size memset");
1293
1294 // Fill MainLoopBB
1295 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1296 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
1297
1298 Value *DstGEP =
1299 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
1300 MainLoopBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1301 isVolatile: IsVolatile);
1302
1303 // Fill ResidualLoopBB
1304 if (!LEI.ResidualLoopIP)
1305 return;
1306
1307 Align ResDstAlign(commonAlignment(A: PartDstAlign, Offset: ResidualLoopOpSize));
1308
1309 IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP);
1310
1311 Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr,
1312 IdxList: LEI.ResidualLoopIndex);
1313 ResLoopBuilder.CreateAlignedStore(Val: SetValue, Ptr: ResDstGEP, Align: ResDstAlign,
1314 isVolatile: IsVolatile);
1315}
1316
1317static void createMemSetPatternLoop(Instruction *InsertBefore, Value *DstAddr,
1318 Value *Len, Value *SetValue, Align DstAlign,
1319 bool IsVolatile,
1320 const TargetTransformInfo *TTI,
1321 std::optional<uint64_t> AverageTripCount) {
1322 // No need to expand zero length memset.pattern.
1323 if (auto *CLen = dyn_cast<ConstantInt>(Val: Len))
1324 if (CLen->isZero())
1325 return;
1326
1327 BasicBlock *PreLoopBB = InsertBefore->getParent();
1328 Function *ParentFunc = PreLoopBB->getParent();
1329 const DataLayout &DL = ParentFunc->getDataLayout();
1330 LLVMContext &Ctx = PreLoopBB->getContext();
1331
1332 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1333
1334 Type *PreferredLoopOpType = SetValue->getType();
1335 if (TTI) {
1336 PreferredLoopOpType = TTI->getMemcpyLoopLoweringType(
1337 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1338 }
1339 TypeSize PreferredLoopOpStoreSize = DL.getTypeStoreSize(Ty: PreferredLoopOpType);
1340 assert(PreferredLoopOpStoreSize.isFixed() &&
1341 "PreferredLoopOpType cannot be a scalable vector type");
1342
1343 TypeSize PreferredLoopOpAllocSize = DL.getTypeAllocSize(Ty: PreferredLoopOpType);
1344
1345 Type *OriginalType = SetValue->getType();
1346 TypeSize OriginalTypeStoreSize = DL.getTypeStoreSize(Ty: OriginalType);
1347 TypeSize OriginalTypeAllocSize = DL.getTypeAllocSize(Ty: OriginalType);
1348
1349 // The semantics of memset.pattern restrict what vectorization we can do: It
1350 // has to behave like a series of stores of the SetValue type at offsets that
1351 // are spaced by the alloc size of the SetValue type. If store and alloc size
1352 // of the SetValue type don't match, the bytes that aren't covered by these
1353 // stores must not be overwritten. We therefore only vectorize memset.pattern
1354 // if the store and alloc sizes of the SetValue are equal and properly divide
1355 // the size of the preferred lowering type (and only if store and alloc size
1356 // for the preferred lowering type are also equal).
1357
1358 unsigned MainLoopStep = 1;
1359 Type *MainLoopType = OriginalType;
1360 TypeSize MainLoopAllocSize = OriginalTypeAllocSize;
1361 unsigned ResidualLoopStep = 0;
1362 Type *ResidualLoopType = nullptr;
1363
1364 if (PreferredLoopOpStoreSize == PreferredLoopOpAllocSize &&
1365 OriginalTypeStoreSize == OriginalTypeAllocSize &&
1366 OriginalTypeStoreSize < PreferredLoopOpStoreSize &&
1367 PreferredLoopOpStoreSize % OriginalTypeStoreSize == 0) {
1368 // Multiple instances of SetValue can be combined to reach the preferred
1369 // loop op size.
1370 MainLoopStep = PreferredLoopOpStoreSize / OriginalTypeStoreSize;
1371 MainLoopType = PreferredLoopOpType;
1372 MainLoopAllocSize = PreferredLoopOpStoreSize;
1373
1374 ResidualLoopStep = 1;
1375 ResidualLoopType = OriginalType;
1376 }
1377
1378 // The step arguments here are in terms of the alloc size of the SetValue, not
1379 // in terms of bytes.
1380 LoopExpansionInfo LEI =
1381 insertLoopExpansion(InsertBefore, Len, MainLoopStep, ResidualLoopStep,
1382 BBNamePrefix: "memset.pattern", ExpectedUnits: AverageTripCount);
1383
1384 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: MainLoopAllocSize));
1385
1386 if (LEI.MainLoopIP) {
1387 // Create the loop-invariant splat value before the loop.
1388 IRBuilder<> PreLoopBuilder(PreLoopBB->getTerminator());
1389 Value *MainLoopSetValue = SetValue;
1390 if (MainLoopType != OriginalType)
1391 MainLoopSetValue =
1392 createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: MainLoopType);
1393
1394 // Fill MainLoopBB
1395 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1396 Value *DstGEP = MainLoopBuilder.CreateInBoundsGEP(Ty: MainLoopType, Ptr: DstAddr,
1397 IdxList: LEI.MainLoopIndex);
1398 MainLoopBuilder.CreateAlignedStore(Val: MainLoopSetValue, Ptr: DstGEP, Align: PartDstAlign,
1399 isVolatile: IsVolatile);
1400 }
1401
1402 if (!LEI.ResidualLoopIP)
1403 return;
1404
1405 // Fill ResidualLoopBB
1406 Align ResDstAlign(
1407 commonAlignment(A: PartDstAlign, Offset: DL.getTypeAllocSize(Ty: ResidualLoopType)));
1408
1409 IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP);
1410 Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: ResidualLoopType, Ptr: DstAddr,
1411 IdxList: LEI.ResidualLoopIndex);
1412 ResLoopBuilder.CreateAlignedStore(Val: SetValue, Ptr: ResDstGEP, Align: ResDstAlign,
1413 isVolatile: IsVolatile);
1414}
1415
1416template <typename T>
1417static bool canOverlap(MemTransferBase<T> *Memcpy, ScalarEvolution *SE) {
1418 if (SE) {
1419 const SCEV *SrcSCEV = SE->getSCEV(V: Memcpy->getRawSource());
1420 const SCEV *DestSCEV = SE->getSCEV(V: Memcpy->getRawDest());
1421 if (SE->isKnownPredicateAt(Pred: CmpInst::ICMP_NE, LHS: SrcSCEV, RHS: DestSCEV, CtxI: Memcpy))
1422 return false;
1423 }
1424 return true;
1425}
1426
1427void llvm::expandMemCpyAsLoop(MemCpyInst *Memcpy,
1428 const TargetTransformInfo &TTI,
1429 ScalarEvolution *SE) {
1430 bool CanOverlap = canOverlap(Memcpy, SE);
1431 auto TripCount = getAverageMemOpLoopTripCount(I: *Memcpy);
1432 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Memcpy->getLength())) {
1433 createMemCpyLoopKnownSize(
1434 /*InsertBefore=*/Memcpy,
1435 /*SrcAddr=*/Memcpy->getRawSource(),
1436 /*DstAddr=*/Memcpy->getRawDest(),
1437 /*CopyLen=*/CI,
1438 /*SrcAlign=*/Memcpy->getSourceAlign().valueOrOne(),
1439 /*DstAlign=*/Memcpy->getDestAlign().valueOrOne(),
1440 /*SrcIsVolatile=*/Memcpy->isVolatile(),
1441 /*DstIsVolatile=*/Memcpy->isVolatile(),
1442 /*CanOverlap=*/CanOverlap,
1443 /*TTI=*/TTI,
1444 /*AtomicElementSize=*/std::nullopt,
1445 /*AverageTripCount=*/TripCount);
1446 } else {
1447 createMemCpyLoopUnknownSize(
1448 /*InsertBefore=*/Memcpy,
1449 /*SrcAddr=*/Memcpy->getRawSource(),
1450 /*DstAddr=*/Memcpy->getRawDest(),
1451 /*CopyLen=*/Memcpy->getLength(),
1452 /*SrcAlign=*/Memcpy->getSourceAlign().valueOrOne(),
1453 /*DstAlign=*/Memcpy->getDestAlign().valueOrOne(),
1454 /*SrcIsVolatile=*/Memcpy->isVolatile(),
1455 /*DstIsVolatile=*/Memcpy->isVolatile(),
1456 /*CanOverlap=*/CanOverlap,
1457 /*TTI=*/TTI,
1458 /*AtomicElementSize=*/std::nullopt,
1459 /*AverageTripCount=*/TripCount);
1460 }
1461}
1462
1463bool llvm::expandMemMoveAsLoop(MemMoveInst *Memmove,
1464 const TargetTransformInfo &TTI) {
1465 Value *CopyLen = Memmove->getLength();
1466 Value *SrcAddr = Memmove->getRawSource();
1467 Value *DstAddr = Memmove->getRawDest();
1468 Align SrcAlign = Memmove->getSourceAlign().valueOrOne();
1469 Align DstAlign = Memmove->getDestAlign().valueOrOne();
1470 bool SrcIsVolatile = Memmove->isVolatile();
1471 bool DstIsVolatile = SrcIsVolatile;
1472 IRBuilder<> CastBuilder(Memmove);
1473 CastBuilder.SetCurrentDebugLocation(Memmove->getDebugLoc());
1474
1475 unsigned SrcAS = SrcAddr->getType()->getPointerAddressSpace();
1476 unsigned DstAS = DstAddr->getType()->getPointerAddressSpace();
1477 if (SrcAS != DstAS) {
1478 if (!TTI.addrspacesMayAlias(AS0: SrcAS, AS1: DstAS)) {
1479 // We may not be able to emit a pointer comparison, but we don't have
1480 // to. Expand as memcpy.
1481 auto AverageTripCount = getAverageMemOpLoopTripCount(I: *Memmove);
1482 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: CopyLen)) {
1483 createMemCpyLoopKnownSize(
1484 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen: CI, SrcAlign, DstAlign,
1485 SrcIsVolatile, DstIsVolatile,
1486 /*CanOverlap=*/false, TTI, AtomicElementSize: std::nullopt, AverageTripCount);
1487 } else {
1488 createMemCpyLoopUnknownSize(
1489 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign,
1490 DstAlign, SrcIsVolatile, DstIsVolatile,
1491 /*CanOverlap=*/false, TTI, AtomicElementSize: std::nullopt, AverageTripCount);
1492 }
1493
1494 return true;
1495 }
1496
1497 if (!(TTI.isValidAddrSpaceCast(FromAS: DstAS, ToAS: SrcAS) ||
1498 TTI.isValidAddrSpaceCast(FromAS: SrcAS, ToAS: DstAS))) {
1499 // We don't know generically if it's legal to introduce an
1500 // addrspacecast. We need to know either if it's legal to insert an
1501 // addrspacecast, or if the address spaces cannot alias.
1502 LLVM_DEBUG(
1503 dbgs() << "Do not know how to expand memmove between different "
1504 "address spaces\n");
1505 return false;
1506 }
1507 }
1508
1509 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: CopyLen)) {
1510 createMemMoveLoopKnownSize(
1511 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen: CI, SrcAlign, DstAlign,
1512 SrcIsVolatile, DstIsVolatile, TTI);
1513 } else {
1514 createMemMoveLoopUnknownSize(
1515 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign, DstAlign,
1516 SrcIsVolatile, DstIsVolatile, TTI);
1517 }
1518 return true;
1519}
1520
1521void llvm::expandMemSetAsLoop(MemSetInst *Memset,
1522 const TargetTransformInfo *TTI) {
1523 auto AverageTripCount = getAverageMemOpLoopTripCount(I: *Memset);
1524 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Memset->getLength())) {
1525 createMemSetLoopKnownSize(
1526 /*InsertBefore=*/Memset,
1527 /*DstAddr=*/Memset->getRawDest(),
1528 /*Len=*/CI,
1529 /*SetValue=*/Memset->getValue(),
1530 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1531 /*IsVolatile=*/Memset->isVolatile(),
1532 /*TTI=*/TTI,
1533 /*AverageTripCount=*/AverageTripCount);
1534 } else {
1535 createMemSetLoopUnknownSize(
1536 /*InsertBefore=*/Memset,
1537 /*DstAddr=*/Memset->getRawDest(),
1538 /*Len=*/Memset->getLength(),
1539 /*SetValue=*/Memset->getValue(),
1540 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1541 /*IsVolatile=*/Memset->isVolatile(),
1542 /*TTI=*/TTI,
1543 /*AverageTripCount=*/AverageTripCount);
1544 }
1545}
1546
1547void llvm::expandMemSetAsLoop(MemSetInst *MemSet,
1548 const TargetTransformInfo &TTI) {
1549 expandMemSetAsLoop(Memset: MemSet, TTI: &TTI);
1550}
1551
1552static MDNode *
1553getBoundedMemSetBranchWeights(uint64_t Size,
1554 ArrayRef<InstrProfValueData> MemSetPrefixSum,
1555 LLVMContext &Context, Function &F) {
1556 if (MemSetPrefixSum.empty() || ProfcheckDisableMetadataFixes)
1557 return getExplicitlyUnknownBranchWeightsIfProfiled(F, DEBUG_TYPE);
1558 auto *LowerBound = lower_bound(
1559 Range&: MemSetPrefixSum, Value&: Size,
1560 C: [&](const InstrProfValueData &A, uint64_t B) { return A.Value < B; });
1561 uint64_t LowerBoundCount = 0;
1562 if (LowerBound != MemSetPrefixSum.begin()) {
1563 --LowerBound;
1564 LowerBoundCount = LowerBound->Count;
1565 }
1566 auto *UpperBound = lower_bound(
1567 Range&: MemSetPrefixSum, Value: Size * 2,
1568 C: [](const InstrProfValueData &A, uint64_t B) { return A.Value < B; });
1569 uint64_t UpperBoundCount = 0;
1570 if (UpperBound != MemSetPrefixSum.begin()) {
1571 --UpperBound;
1572 UpperBoundCount = UpperBound->Count;
1573 }
1574 uint64_t TrueWeight = UpperBoundCount - LowerBoundCount;
1575 uint64_t FalseWeight = LowerBoundCount;
1576 if (TrueWeight == 0 && FalseWeight == 0)
1577 return getExplicitlyUnknownBranchWeightsIfProfiled(F, DEBUG_TYPE);
1578 MDNode *BranchWeights = MDBuilder(Context).createBranchWeights(
1579 Weights: fitWeights(Weights: {TrueWeight, FalseWeight}));
1580 return BranchWeights;
1581}
1582
1583void llvm::expandBoundedMemSet(MemSetInst *MemSet, uint64_t MinLen,
1584 uint64_t MaxLen, const KnownBits &LenKnown) {
1585 assert(MinLen <= MaxLen && "Invalid length bounds");
1586 assert(!MemSet->isVolatile() && "Cannot split a volatile memset");
1587
1588 // Known bits make the length a multiple of MinStoreSize, so no smaller store
1589 // is needed, and a length below it can only be zero.
1590 uint64_t MinStoreSize = uint64_t(1)
1591 << std::min(a: LenKnown.countMinTrailingZeros(), b: 63u);
1592 if (MaxLen < MinStoreSize)
1593 return;
1594
1595 Value *Dst = MemSet->getRawDest();
1596 Value *Len = MemSet->getLength();
1597 Value *SetValue = MemSet->getValue();
1598 Type *LenTy = Len->getType();
1599 Align DstAlign = MemSet->getDestAlign().valueOrOne();
1600 Align TailAlign = commonAlignment(A: DstAlign, Offset: MinStoreSize);
1601
1602 // Branch to the largest power-of-two Size not exceeding Len. A length in
1603 // [Size, 2 * Size] is covered by a store of Size bytes at the start and one
1604 // at the end, which may overlap. E.g. for a length of 0, 4, 8 or 12:
1605 //
1606 // %len.ge8 = icmp uge i64 %len, 8
1607 // br i1 %len.ge8, label %memset_store8, label %memset_lt8
1608 // memset_store8: ; length 8 or 12
1609 // store i64 0, ptr %dst
1610 // %tail.off = sub i64 %len, 8
1611 // %tail = getelementptr inbounds i8, ptr %dst, i64 %tail.off
1612 // store i64 0, ptr %tail ; <<< may overlap!
1613 // br label %memset_done
1614 // memset_lt8:
1615 // %len.ge4 = icmp uge i64 %len, 4
1616 // br i1 %len.ge4, label %memset_store4, label %memset_done
1617 // memset_store4: ; length 4, so no tail store
1618 // store i32 0, ptr %dst
1619 // br label %memset_done
1620 //
1621 // And for a length in [0, 16] with no known bits:
1622 //
1623 // %len.ge16 = icmp uge i64 %len, 16
1624 // br i1 %len.ge16, label %memset_store16, label %memset_lt16
1625 // memset_store16: ; length 16, so no tail store
1626 // store <16 x i8> zeroinitializer, ptr %dst
1627 // br label %memset_done
1628 // memset_lt16:
1629 // %len.ge8 = icmp uge i64 %len, 8
1630 // br i1 %len.ge8, label %memset_store8, label %memset_lt8
1631 // memset_store8: ; length 8 to 15
1632 // store i64 0, ptr %dst
1633 // %tail.off = sub i64 %len, 8
1634 // %tail = getelementptr inbounds i8, ptr %dst, i64 %tail.off
1635 // store i64 0, ptr %tail ; <<< may overlap!
1636 // br label %memset_done
1637 // ...
1638 // memset_lt2:
1639 // %len.ge1 = icmp uge i64 %len, 1
1640 // br i1 %len.ge1, label %memset_store1, label %memset_done
1641 // memset_store1: ; length 1
1642 // store i8 0, ptr %dst
1643 // br label %memset_done
1644 uint64_t TopSize = llvm::bit_floor(Value: MaxLen);
1645 Instruction *InsertBefore = MemSet;
1646 uint64_t TotalCount = 0;
1647 SmallVector<InstrProfValueData> ProfData = getValueProfDataFromInst(
1648 Inst: *MemSet, ValueKind: InstrProfValueKind::IPVK_MemOPSize,
1649 /*MaxNumValueData=*/std::numeric_limits<uint32_t>::max(), TotalC&: TotalCount);
1650 llvm::sort(C&: ProfData,
1651 Comp: [](const InstrProfValueData &A, const InstrProfValueData &B) {
1652 return A.Value < B.Value;
1653 });
1654 SmallVector<InstrProfValueData> MemSetPrefixSum;
1655 uint64_t TotalSeenWeight = 0;
1656 for (const InstrProfValueData &SizeWeight : ProfData) {
1657 if (SizeWeight.Value > MaxLen || SizeWeight.Value < MinLen ||
1658 (SizeWeight.Value != 0 && SizeWeight.Value < MinStoreSize))
1659 continue;
1660 TotalSeenWeight = SaturatingAdd(X: SizeWeight.Count, Y: TotalSeenWeight);
1661 MemSetPrefixSum.push_back(Elt: {.Value: SizeWeight.Value, .Count: TotalSeenWeight});
1662 }
1663 for (uint64_t Size = TopSize; Size >= MinStoreSize; Size /= 2) {
1664 Instruction *StoreBefore = InsertBefore;
1665 if (MinLen < Size) {
1666 IRBuilder<> B(InsertBefore);
1667 Value *Cond = B.CreateICmpUGE(LHS: Len, RHS: ConstantInt::get(Ty: LenTy, V: Size),
1668 Name: "len.ge" + Twine(Size));
1669 MDNode *BranchWeights = getBoundedMemSetBranchWeights(
1670 Size, MemSetPrefixSum, Context&: B.getContext(), F&: *MemSet->getFunction());
1671 if (Size == MinStoreSize) {
1672 StoreBefore =
1673 SplitBlockAndInsertIfThen(Cond, SplitBefore: InsertBefore, Unreachable: false, BranchWeights);
1674 } else {
1675 Instruction *ElseTerm;
1676 SplitBlockAndInsertIfThenElse(Cond, SplitBefore: InsertBefore, ThenTerm: &StoreBefore,
1677 ElseTerm: &ElseTerm, BranchWeights);
1678 ElseTerm->getParent()->setName("memset_lt" + Twine(Size));
1679 InsertBefore = ElseTerm;
1680 }
1681 StoreBefore->getParent()->setName("memset_store" + Twine(Size));
1682 }
1683
1684 // Do the Size-sized store
1685 IRBuilder<> B(StoreBefore);
1686 Value *Val = createBoundedMemSetSplat(B, SetValue, Size);
1687 B.CreateAlignedStore(Val, Ptr: Dst, Align: DstAlign);
1688
1689 // The possibly-overlapping "remainder" store
1690 uint64_t MaxLenForSize = Size == TopSize ? MaxLen : 2 * Size - MinStoreSize;
1691 if (MaxLenForSize > Size) {
1692 Value *TailOff =
1693 B.CreateSub(LHS: Len, RHS: ConstantInt::get(Ty: LenTy, V: Size), Name: "tail.off");
1694 Value *TailPtr = B.CreateInBoundsGEP(Ty: B.getInt8Ty(), Ptr: Dst, IdxList: TailOff, Name: "tail");
1695 B.CreateAlignedStore(Val, Ptr: TailPtr, Align: TailAlign);
1696 }
1697
1698 if (MinLen >= Size)
1699 break;
1700 }
1701
1702 MemSet->getParent()->setName("memset_done");
1703}
1704
1705void llvm::expandMemSetPatternAsLoop(MemSetPatternInst *Memset,
1706 const TargetTransformInfo *TTI) {
1707 createMemSetPatternLoop(
1708 /*InsertBefore=*/Memset,
1709 /*DstAddr=*/Memset->getRawDest(),
1710 /*Len=*/Memset->getLength(),
1711 /*SetValue=*/Memset->getValue(),
1712 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1713 /*IsVolatile=*/Memset->isVolatile(),
1714 /*TTI=*/TTI,
1715 /*AverageTripCount=*/getAverageMemOpLoopTripCount(I: *Memset));
1716}
1717
1718void llvm::expandMemSetPatternAsLoop(MemSetPatternInst *MemSet,
1719 const TargetTransformInfo &TTI) {
1720 expandMemSetPatternAsLoop(Memset: MemSet, TTI: &TTI);
1721}
1722
1723void llvm::expandAtomicMemCpyAsLoop(AnyMemCpyInst *AtomicMemcpy,
1724 const TargetTransformInfo &TTI,
1725 ScalarEvolution *SE) {
1726 assert(AtomicMemcpy->isAtomic());
1727 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: AtomicMemcpy->getLength())) {
1728 createMemCpyLoopKnownSize(
1729 /*InsertBefore=*/AtomicMemcpy,
1730 /*SrcAddr=*/AtomicMemcpy->getRawSource(),
1731 /*DstAddr=*/AtomicMemcpy->getRawDest(),
1732 /*CopyLen=*/CI,
1733 /*SrcAlign=*/AtomicMemcpy->getSourceAlign().valueOrOne(),
1734 /*DstAlign=*/AtomicMemcpy->getDestAlign().valueOrOne(),
1735 /*SrcIsVolatile=*/AtomicMemcpy->isVolatile(),
1736 /*DstIsVolatile=*/AtomicMemcpy->isVolatile(),
1737 /*CanOverlap=*/false, // SrcAddr & DstAddr may not overlap by spec.
1738 /*TTI=*/TTI,
1739 /*AtomicElementSize=*/AtomicMemcpy->getElementSizeInBytes());
1740 } else {
1741 createMemCpyLoopUnknownSize(
1742 /*InsertBefore=*/AtomicMemcpy,
1743 /*SrcAddr=*/AtomicMemcpy->getRawSource(),
1744 /*DstAddr=*/AtomicMemcpy->getRawDest(),
1745 /*CopyLen=*/AtomicMemcpy->getLength(),
1746 /*SrcAlign=*/AtomicMemcpy->getSourceAlign().valueOrOne(),
1747 /*DstAlign=*/AtomicMemcpy->getDestAlign().valueOrOne(),
1748 /*SrcIsVolatile=*/AtomicMemcpy->isVolatile(),
1749 /*DstIsVolatile=*/AtomicMemcpy->isVolatile(),
1750 /*CanOverlap=*/false, // SrcAddr & DstAddr may not overlap by spec.
1751 /*TargetTransformInfo=*/TTI,
1752 /*AtomicElementSize=*/AtomicMemcpy->getElementSizeInBytes());
1753 }
1754}
1755