109467b48Spatrick //===- LowerMemIntrinsics.cpp ----------------------------------*- C++ -*--===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick
909467b48Spatrick #include "llvm/Transforms/Utils/LowerMemIntrinsics.h"
10*d415bd75Srobert #include "llvm/Analysis/ScalarEvolution.h"
1109467b48Spatrick #include "llvm/Analysis/TargetTransformInfo.h"
1209467b48Spatrick #include "llvm/IR/IRBuilder.h"
1309467b48Spatrick #include "llvm/IR/IntrinsicInst.h"
14*d415bd75Srobert #include "llvm/IR/MDBuilder.h"
1509467b48Spatrick #include "llvm/Transforms/Utils/BasicBlockUtils.h"
16*d415bd75Srobert #include <optional>
1709467b48Spatrick
1809467b48Spatrick using namespace llvm;
1909467b48Spatrick
createMemCpyLoopKnownSize(Instruction * InsertBefore,Value * SrcAddr,Value * DstAddr,ConstantInt * CopyLen,Align SrcAlign,Align DstAlign,bool SrcIsVolatile,bool DstIsVolatile,bool CanOverlap,const TargetTransformInfo & TTI,std::optional<uint32_t> AtomicElementSize)20*d415bd75Srobert void llvm::createMemCpyLoopKnownSize(
21*d415bd75Srobert Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr,
22*d415bd75Srobert ConstantInt *CopyLen, Align SrcAlign, Align DstAlign, bool SrcIsVolatile,
23*d415bd75Srobert bool DstIsVolatile, bool CanOverlap, const TargetTransformInfo &TTI,
24*d415bd75Srobert std::optional<uint32_t> AtomicElementSize) {
2509467b48Spatrick // No need to expand zero length copies.
2609467b48Spatrick if (CopyLen->isZero())
2709467b48Spatrick return;
2809467b48Spatrick
2909467b48Spatrick BasicBlock *PreLoopBB = InsertBefore->getParent();
3009467b48Spatrick BasicBlock *PostLoopBB = nullptr;
3109467b48Spatrick Function *ParentFunc = PreLoopBB->getParent();
3209467b48Spatrick LLVMContext &Ctx = PreLoopBB->getContext();
33097a140dSpatrick const DataLayout &DL = ParentFunc->getParent()->getDataLayout();
34*d415bd75Srobert MDBuilder MDB(Ctx);
35*d415bd75Srobert MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain");
36*d415bd75Srobert StringRef Name = "MemCopyAliasScope";
37*d415bd75Srobert MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
3809467b48Spatrick
3909467b48Spatrick unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
4009467b48Spatrick unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
4109467b48Spatrick
42097a140dSpatrick Type *TypeOfCopyLen = CopyLen->getType();
43097a140dSpatrick Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
44*d415bd75Srobert Ctx, CopyLen, SrcAS, DstAS, SrcAlign.value(), DstAlign.value(),
45*d415bd75Srobert AtomicElementSize);
46*d415bd75Srobert assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
47*d415bd75Srobert "Atomic memcpy lowering is not supported for vector operand type");
48097a140dSpatrick
49097a140dSpatrick unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType);
50*d415bd75Srobert assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
51*d415bd75Srobert "Atomic memcpy lowering is not supported for selected operand size");
52*d415bd75Srobert
53097a140dSpatrick uint64_t LoopEndCount = CopyLen->getZExtValue() / LoopOpSize;
54097a140dSpatrick
5509467b48Spatrick if (LoopEndCount != 0) {
5609467b48Spatrick // Split
5709467b48Spatrick PostLoopBB = PreLoopBB->splitBasicBlock(InsertBefore, "memcpy-split");
5809467b48Spatrick BasicBlock *LoopBB =
5909467b48Spatrick BasicBlock::Create(Ctx, "load-store-loop", ParentFunc, PostLoopBB);
6009467b48Spatrick PreLoopBB->getTerminator()->setSuccessor(0, LoopBB);
6109467b48Spatrick
6209467b48Spatrick IRBuilder<> PLBuilder(PreLoopBB->getTerminator());
6309467b48Spatrick
6409467b48Spatrick // Cast the Src and Dst pointers to pointers to the loop operand type (if
6509467b48Spatrick // needed).
6609467b48Spatrick PointerType *SrcOpType = PointerType::get(LoopOpType, SrcAS);
6709467b48Spatrick PointerType *DstOpType = PointerType::get(LoopOpType, DstAS);
6809467b48Spatrick if (SrcAddr->getType() != SrcOpType) {
6909467b48Spatrick SrcAddr = PLBuilder.CreateBitCast(SrcAddr, SrcOpType);
7009467b48Spatrick }
7109467b48Spatrick if (DstAddr->getType() != DstOpType) {
7209467b48Spatrick DstAddr = PLBuilder.CreateBitCast(DstAddr, DstOpType);
7309467b48Spatrick }
7409467b48Spatrick
75097a140dSpatrick Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize));
76097a140dSpatrick Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize));
77097a140dSpatrick
7809467b48Spatrick IRBuilder<> LoopBuilder(LoopBB);
7909467b48Spatrick PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 2, "loop-index");
8009467b48Spatrick LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0U), PreLoopBB);
8109467b48Spatrick // Loop Body
8209467b48Spatrick Value *SrcGEP =
8309467b48Spatrick LoopBuilder.CreateInBoundsGEP(LoopOpType, SrcAddr, LoopIndex);
84*d415bd75Srobert LoadInst *Load = LoopBuilder.CreateAlignedLoad(LoopOpType, SrcGEP,
85097a140dSpatrick PartSrcAlign, SrcIsVolatile);
86*d415bd75Srobert if (!CanOverlap) {
87*d415bd75Srobert // Set alias scope for loads.
88*d415bd75Srobert Load->setMetadata(LLVMContext::MD_alias_scope,
89*d415bd75Srobert MDNode::get(Ctx, NewScope));
90*d415bd75Srobert }
9109467b48Spatrick Value *DstGEP =
9209467b48Spatrick LoopBuilder.CreateInBoundsGEP(LoopOpType, DstAddr, LoopIndex);
93*d415bd75Srobert StoreInst *Store = LoopBuilder.CreateAlignedStore(
94*d415bd75Srobert Load, DstGEP, PartDstAlign, DstIsVolatile);
95*d415bd75Srobert if (!CanOverlap) {
96*d415bd75Srobert // Indicate that stores don't overlap loads.
97*d415bd75Srobert Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
98*d415bd75Srobert }
99*d415bd75Srobert if (AtomicElementSize) {
100*d415bd75Srobert Load->setAtomic(AtomicOrdering::Unordered);
101*d415bd75Srobert Store->setAtomic(AtomicOrdering::Unordered);
102*d415bd75Srobert }
10309467b48Spatrick Value *NewIndex =
10409467b48Spatrick LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1U));
10509467b48Spatrick LoopIndex->addIncoming(NewIndex, LoopBB);
10609467b48Spatrick
10709467b48Spatrick // Create the loop branch condition.
10809467b48Spatrick Constant *LoopEndCI = ConstantInt::get(TypeOfCopyLen, LoopEndCount);
10909467b48Spatrick LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, LoopEndCI),
11009467b48Spatrick LoopBB, PostLoopBB);
11109467b48Spatrick }
11209467b48Spatrick
11309467b48Spatrick uint64_t BytesCopied = LoopEndCount * LoopOpSize;
11409467b48Spatrick uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopied;
11509467b48Spatrick if (RemainingBytes) {
11609467b48Spatrick IRBuilder<> RBuilder(PostLoopBB ? PostLoopBB->getFirstNonPHI()
11709467b48Spatrick : InsertBefore);
11809467b48Spatrick
11909467b48Spatrick SmallVector<Type *, 5> RemainingOps;
12009467b48Spatrick TTI.getMemcpyLoopResidualLoweringType(RemainingOps, Ctx, RemainingBytes,
121097a140dSpatrick SrcAS, DstAS, SrcAlign.value(),
122*d415bd75Srobert DstAlign.value(), AtomicElementSize);
12309467b48Spatrick
124*d415bd75Srobert for (auto *OpTy : RemainingOps) {
125097a140dSpatrick Align PartSrcAlign(commonAlignment(SrcAlign, BytesCopied));
126097a140dSpatrick Align PartDstAlign(commonAlignment(DstAlign, BytesCopied));
127097a140dSpatrick
128*d415bd75Srobert // Calculate the new index
129097a140dSpatrick unsigned OperandSize = DL.getTypeStoreSize(OpTy);
130*d415bd75Srobert assert(
131*d415bd75Srobert (!AtomicElementSize || OperandSize % *AtomicElementSize == 0) &&
132*d415bd75Srobert "Atomic memcpy lowering is not supported for selected operand size");
133*d415bd75Srobert
13409467b48Spatrick uint64_t GepIndex = BytesCopied / OperandSize;
13509467b48Spatrick assert(GepIndex * OperandSize == BytesCopied &&
13609467b48Spatrick "Division should have no Remainder!");
13709467b48Spatrick // Cast source to operand type and load
13809467b48Spatrick PointerType *SrcPtrType = PointerType::get(OpTy, SrcAS);
13909467b48Spatrick Value *CastedSrc = SrcAddr->getType() == SrcPtrType
14009467b48Spatrick ? SrcAddr
14109467b48Spatrick : RBuilder.CreateBitCast(SrcAddr, SrcPtrType);
14209467b48Spatrick Value *SrcGEP = RBuilder.CreateInBoundsGEP(
14309467b48Spatrick OpTy, CastedSrc, ConstantInt::get(TypeOfCopyLen, GepIndex));
144*d415bd75Srobert LoadInst *Load =
145097a140dSpatrick RBuilder.CreateAlignedLoad(OpTy, SrcGEP, PartSrcAlign, SrcIsVolatile);
146*d415bd75Srobert if (!CanOverlap) {
147*d415bd75Srobert // Set alias scope for loads.
148*d415bd75Srobert Load->setMetadata(LLVMContext::MD_alias_scope,
149*d415bd75Srobert MDNode::get(Ctx, NewScope));
150*d415bd75Srobert }
15109467b48Spatrick // Cast destination to operand type and store.
15209467b48Spatrick PointerType *DstPtrType = PointerType::get(OpTy, DstAS);
15309467b48Spatrick Value *CastedDst = DstAddr->getType() == DstPtrType
15409467b48Spatrick ? DstAddr
15509467b48Spatrick : RBuilder.CreateBitCast(DstAddr, DstPtrType);
15609467b48Spatrick Value *DstGEP = RBuilder.CreateInBoundsGEP(
15709467b48Spatrick OpTy, CastedDst, ConstantInt::get(TypeOfCopyLen, GepIndex));
158*d415bd75Srobert StoreInst *Store = RBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign,
159*d415bd75Srobert DstIsVolatile);
160*d415bd75Srobert if (!CanOverlap) {
161*d415bd75Srobert // Indicate that stores don't overlap loads.
162*d415bd75Srobert Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
163*d415bd75Srobert }
164*d415bd75Srobert if (AtomicElementSize) {
165*d415bd75Srobert Load->setAtomic(AtomicOrdering::Unordered);
166*d415bd75Srobert Store->setAtomic(AtomicOrdering::Unordered);
167*d415bd75Srobert }
16809467b48Spatrick BytesCopied += OperandSize;
16909467b48Spatrick }
17009467b48Spatrick }
17109467b48Spatrick assert(BytesCopied == CopyLen->getZExtValue() &&
17209467b48Spatrick "Bytes copied should match size in the call!");
17309467b48Spatrick }
17409467b48Spatrick
createMemCpyLoopUnknownSize(Instruction * InsertBefore,Value * SrcAddr,Value * DstAddr,Value * CopyLen,Align SrcAlign,Align DstAlign,bool SrcIsVolatile,bool DstIsVolatile,bool CanOverlap,const TargetTransformInfo & TTI,std::optional<uint32_t> AtomicElementSize)175*d415bd75Srobert void llvm::createMemCpyLoopUnknownSize(
176*d415bd75Srobert Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr, Value *CopyLen,
177*d415bd75Srobert Align SrcAlign, Align DstAlign, bool SrcIsVolatile, bool DstIsVolatile,
178*d415bd75Srobert bool CanOverlap, const TargetTransformInfo &TTI,
179*d415bd75Srobert std::optional<uint32_t> AtomicElementSize) {
18009467b48Spatrick BasicBlock *PreLoopBB = InsertBefore->getParent();
18109467b48Spatrick BasicBlock *PostLoopBB =
18209467b48Spatrick PreLoopBB->splitBasicBlock(InsertBefore, "post-loop-memcpy-expansion");
18309467b48Spatrick
18409467b48Spatrick Function *ParentFunc = PreLoopBB->getParent();
185097a140dSpatrick const DataLayout &DL = ParentFunc->getParent()->getDataLayout();
18609467b48Spatrick LLVMContext &Ctx = PreLoopBB->getContext();
187*d415bd75Srobert MDBuilder MDB(Ctx);
188*d415bd75Srobert MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain");
189*d415bd75Srobert StringRef Name = "MemCopyAliasScope";
190*d415bd75Srobert MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
191*d415bd75Srobert
192097a140dSpatrick unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
193097a140dSpatrick unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
19409467b48Spatrick
195097a140dSpatrick Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
196*d415bd75Srobert Ctx, CopyLen, SrcAS, DstAS, SrcAlign.value(), DstAlign.value(),
197*d415bd75Srobert AtomicElementSize);
198*d415bd75Srobert assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
199*d415bd75Srobert "Atomic memcpy lowering is not supported for vector operand type");
200097a140dSpatrick unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType);
201*d415bd75Srobert assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
202*d415bd75Srobert "Atomic memcpy lowering is not supported for selected operand size");
20309467b48Spatrick
20409467b48Spatrick IRBuilder<> PLBuilder(PreLoopBB->getTerminator());
20509467b48Spatrick
20609467b48Spatrick PointerType *SrcOpType = PointerType::get(LoopOpType, SrcAS);
20709467b48Spatrick PointerType *DstOpType = PointerType::get(LoopOpType, DstAS);
20809467b48Spatrick if (SrcAddr->getType() != SrcOpType) {
20909467b48Spatrick SrcAddr = PLBuilder.CreateBitCast(SrcAddr, SrcOpType);
21009467b48Spatrick }
21109467b48Spatrick if (DstAddr->getType() != DstOpType) {
21209467b48Spatrick DstAddr = PLBuilder.CreateBitCast(DstAddr, DstOpType);
21309467b48Spatrick }
21409467b48Spatrick
21509467b48Spatrick // Calculate the loop trip count, and remaining bytes to copy after the loop.
21609467b48Spatrick Type *CopyLenType = CopyLen->getType();
21709467b48Spatrick IntegerType *ILengthType = dyn_cast<IntegerType>(CopyLenType);
21809467b48Spatrick assert(ILengthType &&
21909467b48Spatrick "expected size argument to memcpy to be an integer type!");
22009467b48Spatrick Type *Int8Type = Type::getInt8Ty(Ctx);
22109467b48Spatrick bool LoopOpIsInt8 = LoopOpType == Int8Type;
22209467b48Spatrick ConstantInt *CILoopOpSize = ConstantInt::get(ILengthType, LoopOpSize);
22309467b48Spatrick Value *RuntimeLoopCount = LoopOpIsInt8 ?
22409467b48Spatrick CopyLen :
22509467b48Spatrick PLBuilder.CreateUDiv(CopyLen, CILoopOpSize);
22609467b48Spatrick BasicBlock *LoopBB =
22709467b48Spatrick BasicBlock::Create(Ctx, "loop-memcpy-expansion", ParentFunc, PostLoopBB);
22809467b48Spatrick IRBuilder<> LoopBuilder(LoopBB);
22909467b48Spatrick
230097a140dSpatrick Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize));
231097a140dSpatrick Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize));
232097a140dSpatrick
23309467b48Spatrick PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLenType, 2, "loop-index");
23409467b48Spatrick LoopIndex->addIncoming(ConstantInt::get(CopyLenType, 0U), PreLoopBB);
23509467b48Spatrick
23609467b48Spatrick Value *SrcGEP = LoopBuilder.CreateInBoundsGEP(LoopOpType, SrcAddr, LoopIndex);
237*d415bd75Srobert LoadInst *Load = LoopBuilder.CreateAlignedLoad(LoopOpType, SrcGEP,
238*d415bd75Srobert PartSrcAlign, SrcIsVolatile);
239*d415bd75Srobert if (!CanOverlap) {
240*d415bd75Srobert // Set alias scope for loads.
241*d415bd75Srobert Load->setMetadata(LLVMContext::MD_alias_scope, MDNode::get(Ctx, NewScope));
242*d415bd75Srobert }
24309467b48Spatrick Value *DstGEP = LoopBuilder.CreateInBoundsGEP(LoopOpType, DstAddr, LoopIndex);
244*d415bd75Srobert StoreInst *Store =
245097a140dSpatrick LoopBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign, DstIsVolatile);
246*d415bd75Srobert if (!CanOverlap) {
247*d415bd75Srobert // Indicate that stores don't overlap loads.
248*d415bd75Srobert Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
249*d415bd75Srobert }
250*d415bd75Srobert if (AtomicElementSize) {
251*d415bd75Srobert Load->setAtomic(AtomicOrdering::Unordered);
252*d415bd75Srobert Store->setAtomic(AtomicOrdering::Unordered);
253*d415bd75Srobert }
25409467b48Spatrick Value *NewIndex =
25509467b48Spatrick LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLenType, 1U));
25609467b48Spatrick LoopIndex->addIncoming(NewIndex, LoopBB);
25709467b48Spatrick
258*d415bd75Srobert bool requiresResidual =
259*d415bd75Srobert !LoopOpIsInt8 && !(AtomicElementSize && LoopOpSize == AtomicElementSize);
260*d415bd75Srobert if (requiresResidual) {
261*d415bd75Srobert Type *ResLoopOpType = AtomicElementSize
262*d415bd75Srobert ? Type::getIntNTy(Ctx, *AtomicElementSize * 8)
263*d415bd75Srobert : Int8Type;
264*d415bd75Srobert unsigned ResLoopOpSize = DL.getTypeStoreSize(ResLoopOpType);
265*d415bd75Srobert assert((ResLoopOpSize == AtomicElementSize ? *AtomicElementSize : 1) &&
266*d415bd75Srobert "Store size is expected to match type size");
267*d415bd75Srobert
26809467b48Spatrick // Add in the
26909467b48Spatrick Value *RuntimeResidual = PLBuilder.CreateURem(CopyLen, CILoopOpSize);
27009467b48Spatrick Value *RuntimeBytesCopied = PLBuilder.CreateSub(CopyLen, RuntimeResidual);
27109467b48Spatrick
27209467b48Spatrick // Loop body for the residual copy.
27309467b48Spatrick BasicBlock *ResLoopBB = BasicBlock::Create(Ctx, "loop-memcpy-residual",
27409467b48Spatrick PreLoopBB->getParent(),
27509467b48Spatrick PostLoopBB);
27609467b48Spatrick // Residual loop header.
27709467b48Spatrick BasicBlock *ResHeaderBB = BasicBlock::Create(
27809467b48Spatrick Ctx, "loop-memcpy-residual-header", PreLoopBB->getParent(), nullptr);
27909467b48Spatrick
28009467b48Spatrick // Need to update the pre-loop basic block to branch to the correct place.
28109467b48Spatrick // branch to the main loop if the count is non-zero, branch to the residual
28209467b48Spatrick // loop if the copy size is smaller then 1 iteration of the main loop but
28309467b48Spatrick // non-zero and finally branch to after the residual loop if the memcpy
28409467b48Spatrick // size is zero.
28509467b48Spatrick ConstantInt *Zero = ConstantInt::get(ILengthType, 0U);
28609467b48Spatrick PLBuilder.CreateCondBr(PLBuilder.CreateICmpNE(RuntimeLoopCount, Zero),
28709467b48Spatrick LoopBB, ResHeaderBB);
28809467b48Spatrick PreLoopBB->getTerminator()->eraseFromParent();
28909467b48Spatrick
29009467b48Spatrick LoopBuilder.CreateCondBr(
29109467b48Spatrick LoopBuilder.CreateICmpULT(NewIndex, RuntimeLoopCount), LoopBB,
29209467b48Spatrick ResHeaderBB);
29309467b48Spatrick
29409467b48Spatrick // Determine if we need to branch to the residual loop or bypass it.
29509467b48Spatrick IRBuilder<> RHBuilder(ResHeaderBB);
29609467b48Spatrick RHBuilder.CreateCondBr(RHBuilder.CreateICmpNE(RuntimeResidual, Zero),
29709467b48Spatrick ResLoopBB, PostLoopBB);
29809467b48Spatrick
29909467b48Spatrick // Copy the residual with single byte load/store loop.
30009467b48Spatrick IRBuilder<> ResBuilder(ResLoopBB);
30109467b48Spatrick PHINode *ResidualIndex =
30209467b48Spatrick ResBuilder.CreatePHI(CopyLenType, 2, "residual-loop-index");
30309467b48Spatrick ResidualIndex->addIncoming(Zero, ResHeaderBB);
30409467b48Spatrick
305*d415bd75Srobert Value *SrcAsResLoopOpType = ResBuilder.CreateBitCast(
306*d415bd75Srobert SrcAddr, PointerType::get(ResLoopOpType, SrcAS));
307*d415bd75Srobert Value *DstAsResLoopOpType = ResBuilder.CreateBitCast(
308*d415bd75Srobert DstAddr, PointerType::get(ResLoopOpType, DstAS));
30909467b48Spatrick Value *FullOffset = ResBuilder.CreateAdd(RuntimeBytesCopied, ResidualIndex);
310*d415bd75Srobert Value *SrcGEP = ResBuilder.CreateInBoundsGEP(
311*d415bd75Srobert ResLoopOpType, SrcAsResLoopOpType, FullOffset);
312*d415bd75Srobert LoadInst *Load = ResBuilder.CreateAlignedLoad(ResLoopOpType, SrcGEP,
313*d415bd75Srobert PartSrcAlign, SrcIsVolatile);
314*d415bd75Srobert if (!CanOverlap) {
315*d415bd75Srobert // Set alias scope for loads.
316*d415bd75Srobert Load->setMetadata(LLVMContext::MD_alias_scope,
317*d415bd75Srobert MDNode::get(Ctx, NewScope));
318*d415bd75Srobert }
319*d415bd75Srobert Value *DstGEP = ResBuilder.CreateInBoundsGEP(
320*d415bd75Srobert ResLoopOpType, DstAsResLoopOpType, FullOffset);
321*d415bd75Srobert StoreInst *Store = ResBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign,
322*d415bd75Srobert DstIsVolatile);
323*d415bd75Srobert if (!CanOverlap) {
324*d415bd75Srobert // Indicate that stores don't overlap loads.
325*d415bd75Srobert Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
326*d415bd75Srobert }
327*d415bd75Srobert if (AtomicElementSize) {
328*d415bd75Srobert Load->setAtomic(AtomicOrdering::Unordered);
329*d415bd75Srobert Store->setAtomic(AtomicOrdering::Unordered);
330*d415bd75Srobert }
331*d415bd75Srobert Value *ResNewIndex = ResBuilder.CreateAdd(
332*d415bd75Srobert ResidualIndex, ConstantInt::get(CopyLenType, ResLoopOpSize));
33309467b48Spatrick ResidualIndex->addIncoming(ResNewIndex, ResLoopBB);
33409467b48Spatrick
33509467b48Spatrick // Create the loop branch condition.
33609467b48Spatrick ResBuilder.CreateCondBr(
33709467b48Spatrick ResBuilder.CreateICmpULT(ResNewIndex, RuntimeResidual), ResLoopBB,
33809467b48Spatrick PostLoopBB);
33909467b48Spatrick } else {
34009467b48Spatrick // In this case the loop operand type was a byte, and there is no need for a
34109467b48Spatrick // residual loop to copy the remaining memory after the main loop.
34209467b48Spatrick // We do however need to patch up the control flow by creating the
34309467b48Spatrick // terminators for the preloop block and the memcpy loop.
34409467b48Spatrick ConstantInt *Zero = ConstantInt::get(ILengthType, 0U);
34509467b48Spatrick PLBuilder.CreateCondBr(PLBuilder.CreateICmpNE(RuntimeLoopCount, Zero),
34609467b48Spatrick LoopBB, PostLoopBB);
34709467b48Spatrick PreLoopBB->getTerminator()->eraseFromParent();
34809467b48Spatrick LoopBuilder.CreateCondBr(
34909467b48Spatrick LoopBuilder.CreateICmpULT(NewIndex, RuntimeLoopCount), LoopBB,
35009467b48Spatrick PostLoopBB);
35109467b48Spatrick }
35209467b48Spatrick }
35309467b48Spatrick
35409467b48Spatrick // Lower memmove to IR. memmove is required to correctly copy overlapping memory
35509467b48Spatrick // regions; therefore, it has to check the relative positions of the source and
35609467b48Spatrick // destination pointers and choose the copy direction accordingly.
35709467b48Spatrick //
35809467b48Spatrick // The code below is an IR rendition of this C function:
35909467b48Spatrick //
36009467b48Spatrick // void* memmove(void* dst, const void* src, size_t n) {
36109467b48Spatrick // unsigned char* d = dst;
36209467b48Spatrick // const unsigned char* s = src;
36309467b48Spatrick // if (s < d) {
36409467b48Spatrick // // copy backwards
36509467b48Spatrick // while (n--) {
36609467b48Spatrick // d[n] = s[n];
36709467b48Spatrick // }
36809467b48Spatrick // } else {
36909467b48Spatrick // // copy forward
37009467b48Spatrick // for (size_t i = 0; i < n; ++i) {
37109467b48Spatrick // d[i] = s[i];
37209467b48Spatrick // }
37309467b48Spatrick // }
37409467b48Spatrick // return dst;
37509467b48Spatrick // }
createMemMoveLoop(Instruction * InsertBefore,Value * SrcAddr,Value * DstAddr,Value * CopyLen,Align SrcAlign,Align DstAlign,bool SrcIsVolatile,bool DstIsVolatile)376097a140dSpatrick static void createMemMoveLoop(Instruction *InsertBefore, Value *SrcAddr,
377097a140dSpatrick Value *DstAddr, Value *CopyLen, Align SrcAlign,
378097a140dSpatrick Align DstAlign, bool SrcIsVolatile,
379097a140dSpatrick bool DstIsVolatile) {
38009467b48Spatrick Type *TypeOfCopyLen = CopyLen->getType();
38109467b48Spatrick BasicBlock *OrigBB = InsertBefore->getParent();
38209467b48Spatrick Function *F = OrigBB->getParent();
383097a140dSpatrick const DataLayout &DL = F->getParent()->getDataLayout();
38409467b48Spatrick
385*d415bd75Srobert // TODO: Use different element type if possible?
386*d415bd75Srobert IRBuilder<> CastBuilder(InsertBefore);
387*d415bd75Srobert Type *EltTy = CastBuilder.getInt8Ty();
388*d415bd75Srobert Type *PtrTy =
389*d415bd75Srobert CastBuilder.getInt8PtrTy(SrcAddr->getType()->getPointerAddressSpace());
390*d415bd75Srobert SrcAddr = CastBuilder.CreateBitCast(SrcAddr, PtrTy);
391*d415bd75Srobert DstAddr = CastBuilder.CreateBitCast(DstAddr, PtrTy);
39209467b48Spatrick
39309467b48Spatrick // Create the a comparison of src and dst, based on which we jump to either
39409467b48Spatrick // the forward-copy part of the function (if src >= dst) or the backwards-copy
39509467b48Spatrick // part (if src < dst).
39609467b48Spatrick // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
39709467b48Spatrick // structure. Its block terminators (unconditional branches) are replaced by
39809467b48Spatrick // the appropriate conditional branches when the loop is built.
39909467b48Spatrick ICmpInst *PtrCompare = new ICmpInst(InsertBefore, ICmpInst::ICMP_ULT,
40009467b48Spatrick SrcAddr, DstAddr, "compare_src_dst");
40109467b48Spatrick Instruction *ThenTerm, *ElseTerm;
40209467b48Spatrick SplitBlockAndInsertIfThenElse(PtrCompare, InsertBefore, &ThenTerm,
40309467b48Spatrick &ElseTerm);
40409467b48Spatrick
40509467b48Spatrick // Each part of the function consists of two blocks:
40609467b48Spatrick // copy_backwards: used to skip the loop when n == 0
40709467b48Spatrick // copy_backwards_loop: the actual backwards loop BB
40809467b48Spatrick // copy_forward: used to skip the loop when n == 0
40909467b48Spatrick // copy_forward_loop: the actual forward loop BB
41009467b48Spatrick BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
41109467b48Spatrick CopyBackwardsBB->setName("copy_backwards");
41209467b48Spatrick BasicBlock *CopyForwardBB = ElseTerm->getParent();
41309467b48Spatrick CopyForwardBB->setName("copy_forward");
41409467b48Spatrick BasicBlock *ExitBB = InsertBefore->getParent();
41509467b48Spatrick ExitBB->setName("memmove_done");
41609467b48Spatrick
417097a140dSpatrick unsigned PartSize = DL.getTypeStoreSize(EltTy);
418097a140dSpatrick Align PartSrcAlign(commonAlignment(SrcAlign, PartSize));
419097a140dSpatrick Align PartDstAlign(commonAlignment(DstAlign, PartSize));
420097a140dSpatrick
42109467b48Spatrick // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
42209467b48Spatrick // between both backwards and forward copy clauses.
42309467b48Spatrick ICmpInst *CompareN =
42409467b48Spatrick new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
42509467b48Spatrick ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
42609467b48Spatrick
42709467b48Spatrick // Copying backwards.
42809467b48Spatrick BasicBlock *LoopBB =
42909467b48Spatrick BasicBlock::Create(F->getContext(), "copy_backwards_loop", F, CopyForwardBB);
43009467b48Spatrick IRBuilder<> LoopBuilder(LoopBB);
43109467b48Spatrick PHINode *LoopPhi = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
43209467b48Spatrick Value *IndexPtr = LoopBuilder.CreateSub(
43309467b48Spatrick LoopPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_ptr");
434097a140dSpatrick Value *Element = LoopBuilder.CreateAlignedLoad(
43509467b48Spatrick EltTy, LoopBuilder.CreateInBoundsGEP(EltTy, SrcAddr, IndexPtr),
436097a140dSpatrick PartSrcAlign, "element");
437097a140dSpatrick LoopBuilder.CreateAlignedStore(
438097a140dSpatrick Element, LoopBuilder.CreateInBoundsGEP(EltTy, DstAddr, IndexPtr),
439097a140dSpatrick PartDstAlign);
44009467b48Spatrick LoopBuilder.CreateCondBr(
44109467b48Spatrick LoopBuilder.CreateICmpEQ(IndexPtr, ConstantInt::get(TypeOfCopyLen, 0)),
44209467b48Spatrick ExitBB, LoopBB);
44309467b48Spatrick LoopPhi->addIncoming(IndexPtr, LoopBB);
44409467b48Spatrick LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
44509467b48Spatrick BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
44609467b48Spatrick ThenTerm->eraseFromParent();
44709467b48Spatrick
44809467b48Spatrick // Copying forward.
44909467b48Spatrick BasicBlock *FwdLoopBB =
45009467b48Spatrick BasicBlock::Create(F->getContext(), "copy_forward_loop", F, ExitBB);
45109467b48Spatrick IRBuilder<> FwdLoopBuilder(FwdLoopBB);
45209467b48Spatrick PHINode *FwdCopyPhi = FwdLoopBuilder.CreatePHI(TypeOfCopyLen, 0, "index_ptr");
453097a140dSpatrick Value *SrcGEP = FwdLoopBuilder.CreateInBoundsGEP(EltTy, SrcAddr, FwdCopyPhi);
454097a140dSpatrick Value *FwdElement =
455097a140dSpatrick FwdLoopBuilder.CreateAlignedLoad(EltTy, SrcGEP, PartSrcAlign, "element");
456097a140dSpatrick Value *DstGEP = FwdLoopBuilder.CreateInBoundsGEP(EltTy, DstAddr, FwdCopyPhi);
457097a140dSpatrick FwdLoopBuilder.CreateAlignedStore(FwdElement, DstGEP, PartDstAlign);
45809467b48Spatrick Value *FwdIndexPtr = FwdLoopBuilder.CreateAdd(
45909467b48Spatrick FwdCopyPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_increment");
46009467b48Spatrick FwdLoopBuilder.CreateCondBr(FwdLoopBuilder.CreateICmpEQ(FwdIndexPtr, CopyLen),
46109467b48Spatrick ExitBB, FwdLoopBB);
46209467b48Spatrick FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
46309467b48Spatrick FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
46409467b48Spatrick
46509467b48Spatrick BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
46609467b48Spatrick ElseTerm->eraseFromParent();
46709467b48Spatrick }
46809467b48Spatrick
createMemSetLoop(Instruction * InsertBefore,Value * DstAddr,Value * CopyLen,Value * SetValue,Align DstAlign,bool IsVolatile)469097a140dSpatrick static void createMemSetLoop(Instruction *InsertBefore, Value *DstAddr,
470097a140dSpatrick Value *CopyLen, Value *SetValue, Align DstAlign,
471097a140dSpatrick bool IsVolatile) {
47209467b48Spatrick Type *TypeOfCopyLen = CopyLen->getType();
47309467b48Spatrick BasicBlock *OrigBB = InsertBefore->getParent();
47409467b48Spatrick Function *F = OrigBB->getParent();
475097a140dSpatrick const DataLayout &DL = F->getParent()->getDataLayout();
47609467b48Spatrick BasicBlock *NewBB =
47709467b48Spatrick OrigBB->splitBasicBlock(InsertBefore, "split");
47809467b48Spatrick BasicBlock *LoopBB
47909467b48Spatrick = BasicBlock::Create(F->getContext(), "loadstoreloop", F, NewBB);
48009467b48Spatrick
48109467b48Spatrick IRBuilder<> Builder(OrigBB->getTerminator());
48209467b48Spatrick
48309467b48Spatrick // Cast pointer to the type of value getting stored
48409467b48Spatrick unsigned dstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
48509467b48Spatrick DstAddr = Builder.CreateBitCast(DstAddr,
48609467b48Spatrick PointerType::get(SetValue->getType(), dstAS));
48709467b48Spatrick
48809467b48Spatrick Builder.CreateCondBr(
48909467b48Spatrick Builder.CreateICmpEQ(ConstantInt::get(TypeOfCopyLen, 0), CopyLen), NewBB,
49009467b48Spatrick LoopBB);
49109467b48Spatrick OrigBB->getTerminator()->eraseFromParent();
49209467b48Spatrick
493097a140dSpatrick unsigned PartSize = DL.getTypeStoreSize(SetValue->getType());
494097a140dSpatrick Align PartAlign(commonAlignment(DstAlign, PartSize));
495097a140dSpatrick
49609467b48Spatrick IRBuilder<> LoopBuilder(LoopBB);
49709467b48Spatrick PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
49809467b48Spatrick LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
49909467b48Spatrick
500097a140dSpatrick LoopBuilder.CreateAlignedStore(
50109467b48Spatrick SetValue,
50209467b48Spatrick LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
503097a140dSpatrick PartAlign, IsVolatile);
50409467b48Spatrick
50509467b48Spatrick Value *NewIndex =
50609467b48Spatrick LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
50709467b48Spatrick LoopIndex->addIncoming(NewIndex, LoopBB);
50809467b48Spatrick
50909467b48Spatrick LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
51009467b48Spatrick NewBB);
51109467b48Spatrick }
51209467b48Spatrick
513*d415bd75Srobert template <typename T>
canOverlap(MemTransferBase<T> * Memcpy,ScalarEvolution * SE)514*d415bd75Srobert static bool canOverlap(MemTransferBase<T> *Memcpy, ScalarEvolution *SE) {
515*d415bd75Srobert if (SE) {
516*d415bd75Srobert auto *SrcSCEV = SE->getSCEV(Memcpy->getRawSource());
517*d415bd75Srobert auto *DestSCEV = SE->getSCEV(Memcpy->getRawDest());
518*d415bd75Srobert if (SE->isKnownPredicateAt(CmpInst::ICMP_NE, SrcSCEV, DestSCEV, Memcpy))
519*d415bd75Srobert return false;
520*d415bd75Srobert }
521*d415bd75Srobert return true;
522*d415bd75Srobert }
523*d415bd75Srobert
expandMemCpyAsLoop(MemCpyInst * Memcpy,const TargetTransformInfo & TTI,ScalarEvolution * SE)52409467b48Spatrick void llvm::expandMemCpyAsLoop(MemCpyInst *Memcpy,
525*d415bd75Srobert const TargetTransformInfo &TTI,
526*d415bd75Srobert ScalarEvolution *SE) {
527*d415bd75Srobert bool CanOverlap = canOverlap(Memcpy, SE);
52809467b48Spatrick if (ConstantInt *CI = dyn_cast<ConstantInt>(Memcpy->getLength())) {
529097a140dSpatrick createMemCpyLoopKnownSize(
530097a140dSpatrick /* InsertBefore */ Memcpy,
53109467b48Spatrick /* SrcAddr */ Memcpy->getRawSource(),
53209467b48Spatrick /* DstAddr */ Memcpy->getRawDest(),
53309467b48Spatrick /* CopyLen */ CI,
534097a140dSpatrick /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(),
535097a140dSpatrick /* DestAlign */ Memcpy->getDestAlign().valueOrOne(),
53609467b48Spatrick /* SrcIsVolatile */ Memcpy->isVolatile(),
53709467b48Spatrick /* DstIsVolatile */ Memcpy->isVolatile(),
538*d415bd75Srobert /* CanOverlap */ CanOverlap,
53909467b48Spatrick /* TargetTransformInfo */ TTI);
54009467b48Spatrick } else {
541097a140dSpatrick createMemCpyLoopUnknownSize(
542097a140dSpatrick /* InsertBefore */ Memcpy,
54309467b48Spatrick /* SrcAddr */ Memcpy->getRawSource(),
54409467b48Spatrick /* DstAddr */ Memcpy->getRawDest(),
54509467b48Spatrick /* CopyLen */ Memcpy->getLength(),
546097a140dSpatrick /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(),
547097a140dSpatrick /* DestAlign */ Memcpy->getDestAlign().valueOrOne(),
54809467b48Spatrick /* SrcIsVolatile */ Memcpy->isVolatile(),
54909467b48Spatrick /* DstIsVolatile */ Memcpy->isVolatile(),
550*d415bd75Srobert /* CanOverlap */ CanOverlap,
551*d415bd75Srobert /* TargetTransformInfo */ TTI);
55209467b48Spatrick }
55309467b48Spatrick }
55409467b48Spatrick
expandMemMoveAsLoop(MemMoveInst * Memmove)55509467b48Spatrick void llvm::expandMemMoveAsLoop(MemMoveInst *Memmove) {
55609467b48Spatrick createMemMoveLoop(/* InsertBefore */ Memmove,
55709467b48Spatrick /* SrcAddr */ Memmove->getRawSource(),
55809467b48Spatrick /* DstAddr */ Memmove->getRawDest(),
55909467b48Spatrick /* CopyLen */ Memmove->getLength(),
560097a140dSpatrick /* SrcAlign */ Memmove->getSourceAlign().valueOrOne(),
561097a140dSpatrick /* DestAlign */ Memmove->getDestAlign().valueOrOne(),
56209467b48Spatrick /* SrcIsVolatile */ Memmove->isVolatile(),
56309467b48Spatrick /* DstIsVolatile */ Memmove->isVolatile());
56409467b48Spatrick }
56509467b48Spatrick
expandMemSetAsLoop(MemSetInst * Memset)56609467b48Spatrick void llvm::expandMemSetAsLoop(MemSetInst *Memset) {
56709467b48Spatrick createMemSetLoop(/* InsertBefore */ Memset,
56809467b48Spatrick /* DstAddr */ Memset->getRawDest(),
56909467b48Spatrick /* CopyLen */ Memset->getLength(),
57009467b48Spatrick /* SetValue */ Memset->getValue(),
571097a140dSpatrick /* Alignment */ Memset->getDestAlign().valueOrOne(),
57209467b48Spatrick Memset->isVolatile());
57309467b48Spatrick }
574*d415bd75Srobert
expandAtomicMemCpyAsLoop(AtomicMemCpyInst * AtomicMemcpy,const TargetTransformInfo & TTI,ScalarEvolution * SE)575*d415bd75Srobert void llvm::expandAtomicMemCpyAsLoop(AtomicMemCpyInst *AtomicMemcpy,
576*d415bd75Srobert const TargetTransformInfo &TTI,
577*d415bd75Srobert ScalarEvolution *SE) {
578*d415bd75Srobert if (ConstantInt *CI = dyn_cast<ConstantInt>(AtomicMemcpy->getLength())) {
579*d415bd75Srobert createMemCpyLoopKnownSize(
580*d415bd75Srobert /* InsertBefore */ AtomicMemcpy,
581*d415bd75Srobert /* SrcAddr */ AtomicMemcpy->getRawSource(),
582*d415bd75Srobert /* DstAddr */ AtomicMemcpy->getRawDest(),
583*d415bd75Srobert /* CopyLen */ CI,
584*d415bd75Srobert /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(),
585*d415bd75Srobert /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(),
586*d415bd75Srobert /* SrcIsVolatile */ AtomicMemcpy->isVolatile(),
587*d415bd75Srobert /* DstIsVolatile */ AtomicMemcpy->isVolatile(),
588*d415bd75Srobert /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec.
589*d415bd75Srobert /* TargetTransformInfo */ TTI,
590*d415bd75Srobert /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes());
591*d415bd75Srobert } else {
592*d415bd75Srobert createMemCpyLoopUnknownSize(
593*d415bd75Srobert /* InsertBefore */ AtomicMemcpy,
594*d415bd75Srobert /* SrcAddr */ AtomicMemcpy->getRawSource(),
595*d415bd75Srobert /* DstAddr */ AtomicMemcpy->getRawDest(),
596*d415bd75Srobert /* CopyLen */ AtomicMemcpy->getLength(),
597*d415bd75Srobert /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(),
598*d415bd75Srobert /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(),
599*d415bd75Srobert /* SrcIsVolatile */ AtomicMemcpy->isVolatile(),
600*d415bd75Srobert /* DstIsVolatile */ AtomicMemcpy->isVolatile(),
601*d415bd75Srobert /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec.
602*d415bd75Srobert /* TargetTransformInfo */ TTI,
603*d415bd75Srobert /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes());
604*d415bd75Srobert }
605*d415bd75Srobert }
606