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->getDebugLoc();
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(Description: "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(Description: "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->getDebugLoc();
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->getDebugLoc();
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->getFirstNonPHIIt());
1019 BwdResBuilder.SetCurrentDebugLocation(DbgLoc);
1020 SmallVector<Type *, 5> RemainingOps;
1021 TTI.getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1022 SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign: PartSrcAlign,
1023 DestAlign: PartDstAlign);
1024 for (auto *OpTy : RemainingOps) {
1025 // reverse the order of the emitted operations
1026 BwdResBuilder.SetInsertPoint(CopyBackwardsBB->getFirstNonPHIIt());
1027 GenerateResidualLdStPair(OpTy, BwdResBuilder, BytesCopied);
1028 }
1029 }
1030 if (BytesCopiedInLoop != 0) {
1031 BasicBlock *LoopBB = CopyBackwardsBB;
1032 BasicBlock *PredBB = OrigBB;
1033 if (RemainingBytes != 0) {
1034 // if we introduce residual code, it needs its separate BB
1035 LoopBB = CopyBackwardsBB->splitBasicBlock(
1036 I: CopyBackwardsBB->getTerminator(), BBName: "memmove_bwd_loop");
1037 PredBB = CopyBackwardsBB;
1038 } else {
1039 CopyBackwardsBB->setName("memmove_bwd_loop");
1040 }
1041 IRBuilder<> LoopBuilder(LoopBB->getTerminator());
1042 LoopBuilder.SetCurrentDebugLocation(DbgLoc);
1043 PHINode *LoopPhi = LoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0);
1044 Value *Index = LoopBuilder.CreateSub(LHS: LoopPhi, RHS: CILoopOpSize, Name: "bwd_index");
1045 Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: Index);
1046 Value *Element = LoopBuilder.CreateAlignedLoad(
1047 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
1048 Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: Index);
1049 LoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
1050 isVolatile: DstIsVolatile);
1051
1052 // Replace the unconditional branch introduced by
1053 // SplitBlockAndInsertIfThenElse to turn LoopBB into a loop.
1054 Instruction *UncondTerm = LoopBB->getTerminator();
1055 LoopBuilder.CreateCondBr(Cond: LoopBuilder.CreateICmpEQ(LHS: Index, RHS: Zero), True: ExitBB,
1056 False: LoopBB);
1057 UncondTerm->eraseFromParent();
1058
1059 LoopPhi->addIncoming(V: Index, BB: LoopBB);
1060 LoopPhi->addIncoming(V: LoopBound, BB: PredBB);
1061 }
1062
1063 // Copying forward.
1064 BasicBlock *FwdResidualBB = CopyForwardBB;
1065 if (BytesCopiedInLoop != 0) {
1066 CopyForwardBB->setName("memmove_fwd_loop");
1067 BasicBlock *LoopBB = CopyForwardBB;
1068 BasicBlock *SuccBB = ExitBB;
1069 if (RemainingBytes != 0) {
1070 // if we introduce residual code, it needs its separate BB
1071 SuccBB = CopyForwardBB->splitBasicBlock(I: CopyForwardBB->getTerminator(),
1072 BBName: "memmove_fwd_residual");
1073 FwdResidualBB = SuccBB;
1074 }
1075 IRBuilder<> LoopBuilder(LoopBB->getTerminator());
1076 LoopBuilder.SetCurrentDebugLocation(DbgLoc);
1077 PHINode *LoopPhi = LoopBuilder.CreatePHI(Ty: ILengthType, NumReservedValues: 0, Name: "fwd_index");
1078 Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: SrcAddr, IdxList: LoopPhi);
1079 Value *Element = LoopBuilder.CreateAlignedLoad(
1080 Ty: LoopOpType, Ptr: LoadGEP, Align: PartSrcAlign, isVolatile: SrcIsVolatile, Name: "element");
1081 Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LoopPhi);
1082 LoopBuilder.CreateAlignedStore(Val: Element, Ptr: StoreGEP, Align: PartDstAlign,
1083 isVolatile: DstIsVolatile);
1084 Value *Index = LoopBuilder.CreateAdd(LHS: LoopPhi, RHS: CILoopOpSize);
1085 LoopPhi->addIncoming(V: Index, BB: LoopBB);
1086 LoopPhi->addIncoming(V: Zero, BB: OrigBB);
1087
1088 // Replace the unconditional branch to turn LoopBB into a loop.
1089 Instruction *UncondTerm = LoopBB->getTerminator();
1090 LoopBuilder.CreateCondBr(Cond: LoopBuilder.CreateICmpEQ(LHS: Index, RHS: LoopBound), True: SuccBB,
1091 False: LoopBB);
1092 UncondTerm->eraseFromParent();
1093 }
1094
1095 if (RemainingBytes != 0) {
1096 uint64_t BytesCopied = BytesCopiedInLoop;
1097
1098 // Residual code is required to move the remaining bytes. In the forward
1099 // case, we emit it in the normal order.
1100 IRBuilder<> FwdResBuilder(FwdResidualBB->getTerminator());
1101 FwdResBuilder.SetCurrentDebugLocation(DbgLoc);
1102 SmallVector<Type *, 5> RemainingOps;
1103 TTI.getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1104 SrcAddrSpace: SrcAS, DestAddrSpace: DstAS, SrcAlign: PartSrcAlign,
1105 DestAlign: PartDstAlign);
1106 for (auto *OpTy : RemainingOps)
1107 GenerateResidualLdStPair(OpTy, FwdResBuilder, BytesCopied);
1108 }
1109}
1110
1111/// Create a Value of \p DstType that consists of a sequence of copies of
1112/// \p SetValue, using bitcasts and a vector splat.
1113static Value *createMemSetSplat(const DataLayout &DL, IRBuilderBase &B,
1114 Value *SetValue, Type *DstType) {
1115 TypeSize DstSize = DL.getTypeStoreSize(Ty: DstType);
1116 Type *SetValueType = SetValue->getType();
1117 TypeSize SetValueSize = DL.getTypeStoreSize(Ty: SetValueType);
1118 assert(SetValueSize == DL.getTypeAllocSize(SetValueType) &&
1119 "Store size and alloc size of SetValue's type must match");
1120 assert(SetValueSize != 0 && DstSize % SetValueSize == 0 &&
1121 "DstType size must be a multiple of SetValue size");
1122
1123 Value *Result = SetValue;
1124 if (DstSize != SetValueSize) {
1125 if (!SetValueType->isIntegerTy() && !SetValueType->isFloatingPointTy()) {
1126 // If the type cannot be put into a vector, bitcast to iN first.
1127 LLVMContext &Ctx = SetValue->getContext();
1128 Result = B.CreateBitCast(V: Result, DestTy: Type::getIntNTy(C&: Ctx, N: SetValueSize * 8),
1129 Name: "setvalue.toint");
1130 }
1131 // Form a sufficiently large vector consisting of SetValue, repeated.
1132 Result =
1133 B.CreateVectorSplat(NumElts: DstSize / SetValueSize, V: Result, Name: "setvalue.splat");
1134 }
1135
1136 // The value has the right size, but we might have to bitcast it to the right
1137 // type.
1138 Result = B.CreateBitCast(V: Result, DestTy: DstType, Name: "setvalue.splat.cast");
1139 return Result;
1140}
1141
1142static void
1143createMemSetLoopKnownSize(Instruction *InsertBefore, Value *DstAddr,
1144 ConstantInt *Len, Value *SetValue, Align DstAlign,
1145 bool IsVolatile, const TargetTransformInfo *TTI,
1146 std::optional<uint64_t> AverageTripCount) {
1147 // No need to expand zero length memsets.
1148 if (Len->isZero())
1149 return;
1150
1151 BasicBlock *PreLoopBB = InsertBefore->getParent();
1152 Function *ParentFunc = PreLoopBB->getParent();
1153 const DataLayout &DL = ParentFunc->getDataLayout();
1154 LLVMContext &Ctx = PreLoopBB->getContext();
1155
1156 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1157
1158 Type *TypeOfLen = Len->getType();
1159 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
1160 assert(SetValue->getType() == Int8Type && "Can only set bytes");
1161
1162 Type *LoopOpType = Int8Type;
1163 if (TTI) {
1164 // Use the same memory access type as for a memcpy with the same Dst and Src
1165 // alignment and address space.
1166 LoopOpType = TTI->getMemcpyLoopLoweringType(
1167 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1168 }
1169 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
1170 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
1171
1172 uint64_t LoopEndCount =
1173 alignDown(Value: Len->getZExtValue(), Align: LoopOpSize.getFixedValue());
1174
1175 if (LoopEndCount != 0) {
1176 Value *SplatSetValue = nullptr;
1177 {
1178 IRBuilder<> PreLoopBuilder(InsertBefore);
1179 SplatSetValue =
1180 createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: LoopOpType);
1181 }
1182
1183 // Don't generate a residual loop, the remaining bytes are set with
1184 // straight-line code.
1185 LoopExpansionInfo LEI = insertLoopExpansion(
1186 InsertBefore, Len, MainLoopStep: LoopOpSize, ResidualLoopStep: 0, BBNamePrefix: "static-memset", ExpectedUnits: AverageTripCount);
1187 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
1188 "Main loop should be generated for non-zero loop count");
1189
1190 // Fill MainLoopBB
1191 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1192 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
1193
1194 Value *DstGEP =
1195 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
1196
1197 MainLoopBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1198 isVolatile: IsVolatile);
1199
1200 assert(!LEI.ResidualLoopIP && !LEI.ResidualLoopIndex &&
1201 "No residual loop was requested");
1202 }
1203
1204 uint64_t BytesSet = LoopEndCount;
1205 uint64_t RemainingBytes = Len->getZExtValue() - BytesSet;
1206 if (RemainingBytes == 0)
1207 return;
1208
1209 IRBuilder<> RBuilder(InsertBefore);
1210
1211 assert(TTI && "there cannot be a residual loop without TTI");
1212 SmallVector<Type *, 5> RemainingOps;
1213 TTI->getMemcpyLoopResidualLoweringType(OpsOut&: RemainingOps, Context&: Ctx, RemainingBytes,
1214 SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign,
1215 AtomicCpySize: std::nullopt);
1216
1217 Type *PreviousOpTy = nullptr;
1218 Value *SplatSetValue = nullptr;
1219 for (auto *OpTy : RemainingOps) {
1220 TypeSize OperandSize = DL.getTypeStoreSize(Ty: OpTy);
1221 assert(OperandSize.isFixed() &&
1222 "Operand types cannot be scalable vector types");
1223 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: BytesSet));
1224
1225 // Avoid recomputing the splat SetValue if it's the same as for the last
1226 // iteration.
1227 if (OpTy != PreviousOpTy)
1228 SplatSetValue = createMemSetSplat(DL, B&: RBuilder, SetValue, DstType: OpTy);
1229
1230 Value *DstGEP = RBuilder.CreateInBoundsGEP(
1231 Ty: Int8Type, Ptr: DstAddr, IdxList: ConstantInt::get(Ty: TypeOfLen, V: BytesSet));
1232 RBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1233 isVolatile: IsVolatile);
1234 BytesSet += OperandSize;
1235 PreviousOpTy = OpTy;
1236 }
1237 assert(BytesSet == Len->getZExtValue() &&
1238 "Bytes set should match size in the call!");
1239}
1240
1241static void
1242createMemSetLoopUnknownSize(Instruction *InsertBefore, Value *DstAddr,
1243 Value *Len, Value *SetValue, Align DstAlign,
1244 bool IsVolatile, const TargetTransformInfo *TTI,
1245 std::optional<uint64_t> AverageTripCount) {
1246 BasicBlock *PreLoopBB = InsertBefore->getParent();
1247 Function *ParentFunc = PreLoopBB->getParent();
1248 const DataLayout &DL = ParentFunc->getDataLayout();
1249 LLVMContext &Ctx = PreLoopBB->getContext();
1250
1251 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1252
1253 Type *Int8Type = Type::getInt8Ty(C&: Ctx);
1254 assert(SetValue->getType() == Int8Type && "Can only set bytes");
1255
1256 Type *LoopOpType = Int8Type;
1257 if (TTI) {
1258 LoopOpType = TTI->getMemcpyLoopLoweringType(
1259 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1260 }
1261 TypeSize LoopOpSize = DL.getTypeStoreSize(Ty: LoopOpType);
1262 assert(LoopOpSize.isFixed() && "LoopOpType cannot be a scalable vector type");
1263
1264 Type *ResidualLoopOpType = Int8Type;
1265 TypeSize ResidualLoopOpSize = DL.getTypeStoreSize(Ty: ResidualLoopOpType);
1266
1267 Value *SplatSetValue = SetValue;
1268 {
1269 IRBuilder<> PreLoopBuilder(InsertBefore);
1270 SplatSetValue = createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: LoopOpType);
1271 }
1272
1273 LoopExpansionInfo LEI =
1274 insertLoopExpansion(InsertBefore, Len, MainLoopStep: LoopOpSize, ResidualLoopStep: ResidualLoopOpSize,
1275 BBNamePrefix: "dynamic-memset", ExpectedUnits: AverageTripCount);
1276 assert(LEI.MainLoopIP && LEI.MainLoopIndex &&
1277 "Main loop should be generated for unknown size memset");
1278
1279 // Fill MainLoopBB
1280 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1281 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: LoopOpSize));
1282
1283 Value *DstGEP =
1284 MainLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr, IdxList: LEI.MainLoopIndex);
1285 MainLoopBuilder.CreateAlignedStore(Val: SplatSetValue, Ptr: DstGEP, Align: PartDstAlign,
1286 isVolatile: IsVolatile);
1287
1288 // Fill ResidualLoopBB
1289 if (!LEI.ResidualLoopIP)
1290 return;
1291
1292 Align ResDstAlign(commonAlignment(A: PartDstAlign, Offset: ResidualLoopOpSize));
1293
1294 IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP);
1295
1296 Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: Int8Type, Ptr: DstAddr,
1297 IdxList: LEI.ResidualLoopIndex);
1298 ResLoopBuilder.CreateAlignedStore(Val: SetValue, Ptr: ResDstGEP, Align: ResDstAlign,
1299 isVolatile: IsVolatile);
1300}
1301
1302static void createMemSetPatternLoop(Instruction *InsertBefore, Value *DstAddr,
1303 Value *Len, Value *SetValue, Align DstAlign,
1304 bool IsVolatile,
1305 const TargetTransformInfo *TTI,
1306 std::optional<uint64_t> AverageTripCount) {
1307 // No need to expand zero length memset.pattern.
1308 if (auto *CLen = dyn_cast<ConstantInt>(Val: Len))
1309 if (CLen->isZero())
1310 return;
1311
1312 BasicBlock *PreLoopBB = InsertBefore->getParent();
1313 Function *ParentFunc = PreLoopBB->getParent();
1314 const DataLayout &DL = ParentFunc->getDataLayout();
1315 LLVMContext &Ctx = PreLoopBB->getContext();
1316
1317 unsigned DstAS = cast<PointerType>(Val: DstAddr->getType())->getAddressSpace();
1318
1319 Type *PreferredLoopOpType = SetValue->getType();
1320 if (TTI) {
1321 PreferredLoopOpType = TTI->getMemcpyLoopLoweringType(
1322 Context&: Ctx, Length: Len, SrcAddrSpace: DstAS, DestAddrSpace: DstAS, SrcAlign: DstAlign, DestAlign: DstAlign, AtomicElementSize: std::nullopt);
1323 }
1324 TypeSize PreferredLoopOpStoreSize = DL.getTypeStoreSize(Ty: PreferredLoopOpType);
1325 assert(PreferredLoopOpStoreSize.isFixed() &&
1326 "PreferredLoopOpType cannot be a scalable vector type");
1327
1328 TypeSize PreferredLoopOpAllocSize = DL.getTypeAllocSize(Ty: PreferredLoopOpType);
1329
1330 Type *OriginalType = SetValue->getType();
1331 TypeSize OriginalTypeStoreSize = DL.getTypeStoreSize(Ty: OriginalType);
1332 TypeSize OriginalTypeAllocSize = DL.getTypeAllocSize(Ty: OriginalType);
1333
1334 // The semantics of memset.pattern restrict what vectorization we can do: It
1335 // has to behave like a series of stores of the SetValue type at offsets that
1336 // are spaced by the alloc size of the SetValue type. If store and alloc size
1337 // of the SetValue type don't match, the bytes that aren't covered by these
1338 // stores must not be overwritten. We therefore only vectorize memset.pattern
1339 // if the store and alloc sizes of the SetValue are equal and properly divide
1340 // the size of the preferred lowering type (and only if store and alloc size
1341 // for the preferred lowering type are also equal).
1342
1343 unsigned MainLoopStep = 1;
1344 Type *MainLoopType = OriginalType;
1345 TypeSize MainLoopAllocSize = OriginalTypeAllocSize;
1346 unsigned ResidualLoopStep = 0;
1347 Type *ResidualLoopType = nullptr;
1348
1349 if (PreferredLoopOpStoreSize == PreferredLoopOpAllocSize &&
1350 OriginalTypeStoreSize == OriginalTypeAllocSize &&
1351 OriginalTypeStoreSize < PreferredLoopOpStoreSize &&
1352 PreferredLoopOpStoreSize % OriginalTypeStoreSize == 0) {
1353 // Multiple instances of SetValue can be combined to reach the preferred
1354 // loop op size.
1355 MainLoopStep = PreferredLoopOpStoreSize / OriginalTypeStoreSize;
1356 MainLoopType = PreferredLoopOpType;
1357 MainLoopAllocSize = PreferredLoopOpStoreSize;
1358
1359 ResidualLoopStep = 1;
1360 ResidualLoopType = OriginalType;
1361 }
1362
1363 // The step arguments here are in terms of the alloc size of the SetValue, not
1364 // in terms of bytes.
1365 LoopExpansionInfo LEI =
1366 insertLoopExpansion(InsertBefore, Len, MainLoopStep, ResidualLoopStep,
1367 BBNamePrefix: "memset.pattern", ExpectedUnits: AverageTripCount);
1368
1369 Align PartDstAlign(commonAlignment(A: DstAlign, Offset: MainLoopAllocSize));
1370
1371 if (LEI.MainLoopIP) {
1372 // Create the loop-invariant splat value before the loop.
1373 IRBuilder<> PreLoopBuilder(PreLoopBB->getTerminator());
1374 Value *MainLoopSetValue = SetValue;
1375 if (MainLoopType != OriginalType)
1376 MainLoopSetValue =
1377 createMemSetSplat(DL, B&: PreLoopBuilder, SetValue, DstType: MainLoopType);
1378
1379 // Fill MainLoopBB
1380 IRBuilder<> MainLoopBuilder(LEI.MainLoopIP);
1381 Value *DstGEP = MainLoopBuilder.CreateInBoundsGEP(Ty: MainLoopType, Ptr: DstAddr,
1382 IdxList: LEI.MainLoopIndex);
1383 MainLoopBuilder.CreateAlignedStore(Val: MainLoopSetValue, Ptr: DstGEP, Align: PartDstAlign,
1384 isVolatile: IsVolatile);
1385 }
1386
1387 if (!LEI.ResidualLoopIP)
1388 return;
1389
1390 // Fill ResidualLoopBB
1391 Align ResDstAlign(
1392 commonAlignment(A: PartDstAlign, Offset: DL.getTypeAllocSize(Ty: ResidualLoopType)));
1393
1394 IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP);
1395 Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Ty: ResidualLoopType, Ptr: DstAddr,
1396 IdxList: LEI.ResidualLoopIndex);
1397 ResLoopBuilder.CreateAlignedStore(Val: SetValue, Ptr: ResDstGEP, Align: ResDstAlign,
1398 isVolatile: IsVolatile);
1399}
1400
1401template <typename T>
1402static bool canOverlap(MemTransferBase<T> *Memcpy, ScalarEvolution *SE) {
1403 if (SE) {
1404 const SCEV *SrcSCEV = SE->getSCEV(V: Memcpy->getRawSource());
1405 const SCEV *DestSCEV = SE->getSCEV(V: Memcpy->getRawDest());
1406 if (SE->isKnownPredicateAt(Pred: CmpInst::ICMP_NE, LHS: SrcSCEV, RHS: DestSCEV, CtxI: Memcpy))
1407 return false;
1408 }
1409 return true;
1410}
1411
1412void llvm::expandMemCpyAsLoop(MemCpyInst *Memcpy,
1413 const TargetTransformInfo &TTI,
1414 ScalarEvolution *SE) {
1415 bool CanOverlap = canOverlap(Memcpy, SE);
1416 auto TripCount = getAverageMemOpLoopTripCount(I: *Memcpy);
1417 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Memcpy->getLength())) {
1418 createMemCpyLoopKnownSize(
1419 /*InsertBefore=*/Memcpy,
1420 /*SrcAddr=*/Memcpy->getRawSource(),
1421 /*DstAddr=*/Memcpy->getRawDest(),
1422 /*CopyLen=*/CI,
1423 /*SrcAlign=*/Memcpy->getSourceAlign().valueOrOne(),
1424 /*DstAlign=*/Memcpy->getDestAlign().valueOrOne(),
1425 /*SrcIsVolatile=*/Memcpy->isVolatile(),
1426 /*DstIsVolatile=*/Memcpy->isVolatile(),
1427 /*CanOverlap=*/CanOverlap,
1428 /*TTI=*/TTI,
1429 /*AtomicElementSize=*/std::nullopt,
1430 /*AverageTripCount=*/TripCount);
1431 } else {
1432 createMemCpyLoopUnknownSize(
1433 /*InsertBefore=*/Memcpy,
1434 /*SrcAddr=*/Memcpy->getRawSource(),
1435 /*DstAddr=*/Memcpy->getRawDest(),
1436 /*CopyLen=*/Memcpy->getLength(),
1437 /*SrcAlign=*/Memcpy->getSourceAlign().valueOrOne(),
1438 /*DstAlign=*/Memcpy->getDestAlign().valueOrOne(),
1439 /*SrcIsVolatile=*/Memcpy->isVolatile(),
1440 /*DstIsVolatile=*/Memcpy->isVolatile(),
1441 /*CanOverlap=*/CanOverlap,
1442 /*TTI=*/TTI,
1443 /*AtomicElementSize=*/std::nullopt,
1444 /*AverageTripCount=*/TripCount);
1445 }
1446}
1447
1448bool llvm::expandMemMoveAsLoop(MemMoveInst *Memmove,
1449 const TargetTransformInfo &TTI) {
1450 Value *CopyLen = Memmove->getLength();
1451 Value *SrcAddr = Memmove->getRawSource();
1452 Value *DstAddr = Memmove->getRawDest();
1453 Align SrcAlign = Memmove->getSourceAlign().valueOrOne();
1454 Align DstAlign = Memmove->getDestAlign().valueOrOne();
1455 bool SrcIsVolatile = Memmove->isVolatile();
1456 bool DstIsVolatile = SrcIsVolatile;
1457 IRBuilder<> CastBuilder(Memmove);
1458 CastBuilder.SetCurrentDebugLocation(Memmove->getDebugLoc());
1459
1460 unsigned SrcAS = SrcAddr->getType()->getPointerAddressSpace();
1461 unsigned DstAS = DstAddr->getType()->getPointerAddressSpace();
1462 if (SrcAS != DstAS) {
1463 if (!TTI.addrspacesMayAlias(AS0: SrcAS, AS1: DstAS)) {
1464 // We may not be able to emit a pointer comparison, but we don't have
1465 // to. Expand as memcpy.
1466 auto AverageTripCount = getAverageMemOpLoopTripCount(I: *Memmove);
1467 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: CopyLen)) {
1468 createMemCpyLoopKnownSize(
1469 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen: CI, SrcAlign, DstAlign,
1470 SrcIsVolatile, DstIsVolatile,
1471 /*CanOverlap=*/false, TTI, AtomicElementSize: std::nullopt, AverageTripCount);
1472 } else {
1473 createMemCpyLoopUnknownSize(
1474 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign,
1475 DstAlign, SrcIsVolatile, DstIsVolatile,
1476 /*CanOverlap=*/false, TTI, AtomicElementSize: std::nullopt, AverageTripCount);
1477 }
1478
1479 return true;
1480 }
1481
1482 if (!(TTI.isValidAddrSpaceCast(FromAS: DstAS, ToAS: SrcAS) ||
1483 TTI.isValidAddrSpaceCast(FromAS: SrcAS, ToAS: DstAS))) {
1484 // We don't know generically if it's legal to introduce an
1485 // addrspacecast. We need to know either if it's legal to insert an
1486 // addrspacecast, or if the address spaces cannot alias.
1487 LLVM_DEBUG(
1488 dbgs() << "Do not know how to expand memmove between different "
1489 "address spaces\n");
1490 return false;
1491 }
1492 }
1493
1494 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: CopyLen)) {
1495 createMemMoveLoopKnownSize(
1496 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen: CI, SrcAlign, DstAlign,
1497 SrcIsVolatile, DstIsVolatile, TTI);
1498 } else {
1499 createMemMoveLoopUnknownSize(
1500 /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign, DstAlign,
1501 SrcIsVolatile, DstIsVolatile, TTI);
1502 }
1503 return true;
1504}
1505
1506void llvm::expandMemSetAsLoop(MemSetInst *Memset,
1507 const TargetTransformInfo *TTI) {
1508 auto AverageTripCount = getAverageMemOpLoopTripCount(I: *Memset);
1509 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Memset->getLength())) {
1510 createMemSetLoopKnownSize(
1511 /*InsertBefore=*/Memset,
1512 /*DstAddr=*/Memset->getRawDest(),
1513 /*Len=*/CI,
1514 /*SetValue=*/Memset->getValue(),
1515 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1516 /*IsVolatile=*/Memset->isVolatile(),
1517 /*TTI=*/TTI,
1518 /*AverageTripCount=*/AverageTripCount);
1519 } else {
1520 createMemSetLoopUnknownSize(
1521 /*InsertBefore=*/Memset,
1522 /*DstAddr=*/Memset->getRawDest(),
1523 /*Len=*/Memset->getLength(),
1524 /*SetValue=*/Memset->getValue(),
1525 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1526 /*IsVolatile=*/Memset->isVolatile(),
1527 /*TTI=*/TTI,
1528 /*AverageTripCount=*/AverageTripCount);
1529 }
1530}
1531
1532void llvm::expandMemSetAsLoop(MemSetInst *MemSet,
1533 const TargetTransformInfo &TTI) {
1534 expandMemSetAsLoop(Memset: MemSet, TTI: &TTI);
1535}
1536
1537void llvm::expandMemSetPatternAsLoop(MemSetPatternInst *Memset,
1538 const TargetTransformInfo *TTI) {
1539 createMemSetPatternLoop(
1540 /*InsertBefore=*/Memset,
1541 /*DstAddr=*/Memset->getRawDest(),
1542 /*Len=*/Memset->getLength(),
1543 /*SetValue=*/Memset->getValue(),
1544 /*DstAlign=*/Memset->getDestAlign().valueOrOne(),
1545 /*IsVolatile=*/Memset->isVolatile(),
1546 /*TTI=*/TTI,
1547 /*AverageTripCount=*/getAverageMemOpLoopTripCount(I: *Memset));
1548}
1549
1550void llvm::expandMemSetPatternAsLoop(MemSetPatternInst *MemSet,
1551 const TargetTransformInfo &TTI) {
1552 expandMemSetPatternAsLoop(Memset: MemSet, TTI: &TTI);
1553}
1554
1555void llvm::expandAtomicMemCpyAsLoop(AnyMemCpyInst *AtomicMemcpy,
1556 const TargetTransformInfo &TTI,
1557 ScalarEvolution *SE) {
1558 assert(AtomicMemcpy->isAtomic());
1559 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: AtomicMemcpy->getLength())) {
1560 createMemCpyLoopKnownSize(
1561 /*InsertBefore=*/AtomicMemcpy,
1562 /*SrcAddr=*/AtomicMemcpy->getRawSource(),
1563 /*DstAddr=*/AtomicMemcpy->getRawDest(),
1564 /*CopyLen=*/CI,
1565 /*SrcAlign=*/AtomicMemcpy->getSourceAlign().valueOrOne(),
1566 /*DstAlign=*/AtomicMemcpy->getDestAlign().valueOrOne(),
1567 /*SrcIsVolatile=*/AtomicMemcpy->isVolatile(),
1568 /*DstIsVolatile=*/AtomicMemcpy->isVolatile(),
1569 /*CanOverlap=*/false, // SrcAddr & DstAddr may not overlap by spec.
1570 /*TTI=*/TTI,
1571 /*AtomicElementSize=*/AtomicMemcpy->getElementSizeInBytes());
1572 } else {
1573 createMemCpyLoopUnknownSize(
1574 /*InsertBefore=*/AtomicMemcpy,
1575 /*SrcAddr=*/AtomicMemcpy->getRawSource(),
1576 /*DstAddr=*/AtomicMemcpy->getRawDest(),
1577 /*CopyLen=*/AtomicMemcpy->getLength(),
1578 /*SrcAlign=*/AtomicMemcpy->getSourceAlign().valueOrOne(),
1579 /*DstAlign=*/AtomicMemcpy->getDestAlign().valueOrOne(),
1580 /*SrcIsVolatile=*/AtomicMemcpy->isVolatile(),
1581 /*DstIsVolatile=*/AtomicMemcpy->isVolatile(),
1582 /*CanOverlap=*/false, // SrcAddr & DstAddr may not overlap by spec.
1583 /*TargetTransformInfo=*/TTI,
1584 /*AtomicElementSize=*/AtomicMemcpy->getElementSizeInBytes());
1585 }
1586}
1587