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