| //===- LowerMemIntrinsics.cpp ----------------------------------*- C++ -*--===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Utils/LowerMemIntrinsics.h" |
| #include "llvm/Analysis/ScalarEvolution.h" |
| #include "llvm/Analysis/TargetTransformInfo.h" |
| #include "llvm/IR/IRBuilder.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/MDBuilder.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| #include <optional> |
| |
| #define DEBUG_TYPE "lower-mem-intrinsics" |
| |
| using namespace llvm; |
| |
| /// \returns \p Len urem \p OpSize, checking for optimization opportunities. |
| /// \p OpSizeVal must be the integer value of the \c ConstantInt \p OpSize. |
| static Value *getRuntimeLoopRemainder(IRBuilderBase &B, Value *Len, |
| Value *OpSize, unsigned OpSizeVal) { |
| // For powers of 2, we can and by (OpSizeVal - 1) instead of using urem. |
| if (isPowerOf2_32(OpSizeVal)) |
| return B.CreateAnd(Len, OpSizeVal - 1); |
| return B.CreateURem(Len, OpSize); |
| } |
| |
| /// \returns (\p Len udiv \p OpSize) mul \p OpSize, checking for optimization |
| /// opportunities. |
| /// If \p RTLoopRemainder is provided, it must be the result of |
| /// \c getRuntimeLoopRemainder() with the same arguments. |
| static Value *getRuntimeLoopUnits(IRBuilderBase &B, Value *Len, Value *OpSize, |
| unsigned OpSizeVal, |
| Value *RTLoopRemainder = nullptr) { |
| if (!RTLoopRemainder) |
| RTLoopRemainder = getRuntimeLoopRemainder(B, Len, OpSize, OpSizeVal); |
| return B.CreateSub(Len, RTLoopRemainder); |
| } |
| |
| namespace { |
| /// Container for the return values of insertLoopExpansion. |
| struct LoopExpansionInfo { |
| /// The instruction at the end of the main loop body. |
| Instruction *MainLoopIP = nullptr; |
| |
| /// The unit index in the main loop body. |
| Value *MainLoopIndex = nullptr; |
| |
| /// The instruction at the end of the residual loop body. Can be nullptr if no |
| /// residual is required. |
| Instruction *ResidualLoopIP = nullptr; |
| |
| /// The unit index in the residual loop body. Can be nullptr if no residual is |
| /// required. |
| Value *ResidualLoopIndex = nullptr; |
| }; |
| } // namespace |
| |
| /// Insert the control flow and loop counters for a memcpy/memset loop |
| /// expansion. |
| /// |
| /// This function inserts IR corresponding to the following C code before |
| /// \p InsertBefore: |
| /// \code |
| /// LoopUnits = (Len / MainLoopStep) * MainLoopStep; |
| /// ResidualUnits = Len - LoopUnits; |
| /// MainLoopIndex = 0; |
| /// if (LoopUnits > 0) { |
| /// do { |
| /// // MainLoopIP |
| /// MainLoopIndex += MainLoopStep; |
| /// } while (MainLoopIndex < LoopUnits); |
| /// } |
| /// for (size_t i = 0; i < ResidualUnits; i += ResidualLoopStep) { |
| /// ResidualLoopIndex = LoopUnits + i; |
| /// // ResidualLoopIP |
| /// } |
| /// \endcode |
| /// |
| /// \p MainLoopStep and \p ResidualLoopStep determine by how many "units" the |
| /// loop index is increased in each iteration of the main and residual loops, |
| /// respectively. In most cases, the "unit" will be bytes, but larger units are |
| /// useful for lowering memset.pattern. |
| /// |
| /// The computation of \c LoopUnits and \c ResidualUnits is performed at compile |
| /// time if \p Len is a \c ConstantInt. |
| /// The second (residual) loop is omitted if \p ResidualLoopStep is 0 or equal |
| /// to \p MainLoopStep. |
| /// The generated \c MainLoopIP, \c MainLoopIndex, \c ResidualLoopIP, and |
| /// \c ResidualLoopIndex are returned in a \c LoopExpansionInfo object. |
| static LoopExpansionInfo insertLoopExpansion(Instruction *InsertBefore, |
| Value *Len, unsigned MainLoopStep, |
| unsigned ResidualLoopStep, |
| StringRef BBNamePrefix) { |
| assert((ResidualLoopStep == 0 || MainLoopStep % ResidualLoopStep == 0) && |
| "ResidualLoopStep must divide MainLoopStep if specified"); |
| assert(ResidualLoopStep <= MainLoopStep && |
| "ResidualLoopStep cannot be larger than MainLoopStep"); |
| assert(MainLoopStep > 0 && "MainLoopStep must be non-zero"); |
| LoopExpansionInfo LEI; |
| BasicBlock *PreLoopBB = InsertBefore->getParent(); |
| BasicBlock *PostLoopBB = PreLoopBB->splitBasicBlock( |
| InsertBefore, BBNamePrefix + "-post-expansion"); |
| Function *ParentFunc = PreLoopBB->getParent(); |
| LLVMContext &Ctx = PreLoopBB->getContext(); |
| IRBuilder<> PreLoopBuilder(PreLoopBB->getTerminator()); |
| |
| // Calculate the main loop trip count and remaining units to cover after the |
| // loop. |
| Type *LenType = Len->getType(); |
| IntegerType *ILenType = cast<IntegerType>(LenType); |
| ConstantInt *CIMainLoopStep = ConstantInt::get(ILenType, MainLoopStep); |
| |
| Value *LoopUnits = Len; |
| Value *ResidualUnits = nullptr; |
| // We can make a conditional branch unconditional if we know that the |
| // MainLoop must be executed at least once. |
| bool MustTakeMainLoop = false; |
| if (MainLoopStep != 1) { |
| if (auto *CLen = dyn_cast<ConstantInt>(Len)) { |
| uint64_t TotalUnits = CLen->getZExtValue(); |
| uint64_t LoopEndCount = alignDown(TotalUnits, MainLoopStep); |
| uint64_t ResidualCount = TotalUnits - LoopEndCount; |
| LoopUnits = ConstantInt::get(LenType, LoopEndCount); |
| ResidualUnits = ConstantInt::get(LenType, ResidualCount); |
| MustTakeMainLoop = LoopEndCount > 0; |
| // As an optimization, we could skip generating the residual loop if |
| // ResidualCount is known to be 0. However, current uses of this function |
| // don't request a residual loop if the length is constant (they generate |
| // a (potentially empty) sequence of loads and stores instead), so this |
| // optimization would have no effect here. |
| } else { |
| ResidualUnits = getRuntimeLoopRemainder(PreLoopBuilder, Len, |
| CIMainLoopStep, MainLoopStep); |
| LoopUnits = getRuntimeLoopUnits(PreLoopBuilder, Len, CIMainLoopStep, |
| MainLoopStep, ResidualUnits); |
| } |
| } else if (auto *CLen = dyn_cast<ConstantInt>(Len)) { |
| MustTakeMainLoop = CLen->getZExtValue() > 0; |
| } |
| |
| BasicBlock *MainLoopBB = BasicBlock::Create( |
| Ctx, BBNamePrefix + "-expansion-main-body", ParentFunc, PostLoopBB); |
| IRBuilder<> LoopBuilder(MainLoopBB); |
| |
| PHINode *LoopIndex = LoopBuilder.CreatePHI(LenType, 2, "loop-index"); |
| LEI.MainLoopIndex = LoopIndex; |
| LoopIndex->addIncoming(ConstantInt::get(LenType, 0U), PreLoopBB); |
| |
| Value *NewIndex = |
| LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(LenType, MainLoopStep)); |
| LoopIndex->addIncoming(NewIndex, MainLoopBB); |
| |
| // One argument of the addition is a loop-variant PHI, so it must be an |
| // Instruction (i.e., it cannot be a Constant). |
| LEI.MainLoopIP = cast<Instruction>(NewIndex); |
| |
| if (ResidualLoopStep > 0 && ResidualLoopStep < MainLoopStep) { |
| // Loop body for the residual accesses. |
| BasicBlock *ResLoopBB = |
| BasicBlock::Create(Ctx, BBNamePrefix + "-expansion-residual-body", |
| PreLoopBB->getParent(), PostLoopBB); |
| // BB to check if the residual loop is needed. |
| BasicBlock *ResidualCondBB = |
| BasicBlock::Create(Ctx, BBNamePrefix + "-expansion-residual-cond", |
| PreLoopBB->getParent(), ResLoopBB); |
| |
| // Enter the MainLoop unless no main loop iteration is required. |
| ConstantInt *Zero = ConstantInt::get(ILenType, 0U); |
| if (MustTakeMainLoop) |
| PreLoopBuilder.CreateBr(MainLoopBB); |
| else |
| PreLoopBuilder.CreateCondBr(PreLoopBuilder.CreateICmpNE(LoopUnits, Zero), |
| MainLoopBB, ResidualCondBB); |
| PreLoopBB->getTerminator()->eraseFromParent(); |
| |
| // Stay in the MainLoop until we have handled all the LoopUnits. Then go to |
| // the residual condition BB. |
| LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, LoopUnits), |
| MainLoopBB, ResidualCondBB); |
| |
| // Determine if we need to branch to the residual loop or bypass it. |
| IRBuilder<> RCBuilder(ResidualCondBB); |
| RCBuilder.CreateCondBr(RCBuilder.CreateICmpNE(ResidualUnits, Zero), |
| ResLoopBB, PostLoopBB); |
| |
| IRBuilder<> ResBuilder(ResLoopBB); |
| PHINode *ResidualIndex = |
| ResBuilder.CreatePHI(LenType, 2, "residual-loop-index"); |
| ResidualIndex->addIncoming(Zero, ResidualCondBB); |
| |
| // Add the offset at the end of the main loop to the loop counter of the |
| // residual loop to get the proper index. |
| Value *FullOffset = ResBuilder.CreateAdd(LoopUnits, ResidualIndex); |
| LEI.ResidualLoopIndex = FullOffset; |
| |
| Value *ResNewIndex = ResBuilder.CreateAdd( |
| ResidualIndex, ConstantInt::get(LenType, ResidualLoopStep)); |
| ResidualIndex->addIncoming(ResNewIndex, ResLoopBB); |
| |
| // One argument of the addition is a loop-variant PHI, so it must be an |
| // Instruction (i.e., it cannot be a Constant). |
| LEI.ResidualLoopIP = cast<Instruction>(ResNewIndex); |
| |
| // Stay in the residual loop until all ResidualUnits are handled. |
| ResBuilder.CreateCondBr( |
| ResBuilder.CreateICmpULT(ResNewIndex, ResidualUnits), ResLoopBB, |
| PostLoopBB); |
| } else { |
| // There is no need for a residual loop after the main loop. We do however |
| // need to patch up the control flow by creating the terminators for the |
| // preloop block and the main loop. |
| |
| // Enter the MainLoop unless no main loop iteration is required. |
| if (MustTakeMainLoop) { |
| PreLoopBuilder.CreateBr(MainLoopBB); |
| } else { |
| ConstantInt *Zero = ConstantInt::get(ILenType, 0U); |
| PreLoopBuilder.CreateCondBr(PreLoopBuilder.CreateICmpNE(LoopUnits, Zero), |
| MainLoopBB, PostLoopBB); |
| } |
| PreLoopBB->getTerminator()->eraseFromParent(); |
| // Stay in the MainLoop until we have handled all the LoopUnits. |
| LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, LoopUnits), |
| MainLoopBB, PostLoopBB); |
| } |
| return LEI; |
| } |
| |
| void llvm::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) { |
| // No need to expand zero length copies. |
| if (CopyLen->isZero()) |
| return; |
| |
| BasicBlock *PreLoopBB = InsertBefore->getParent(); |
| Function *ParentFunc = PreLoopBB->getParent(); |
| LLVMContext &Ctx = PreLoopBB->getContext(); |
| const DataLayout &DL = ParentFunc->getDataLayout(); |
| MDBuilder MDB(Ctx); |
| MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain"); |
| StringRef Name = "MemCopyAliasScope"; |
| MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name); |
| |
| unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace(); |
| unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace(); |
| |
| Type *TypeOfCopyLen = CopyLen->getType(); |
| Type *LoopOpType = TTI.getMemcpyLoopLoweringType( |
| Ctx, CopyLen, SrcAS, DstAS, SrcAlign, DstAlign, AtomicElementSize); |
| assert((!AtomicElementSize || !LoopOpType->isVectorTy()) && |
| "Atomic memcpy lowering is not supported for vector operand type"); |
| |
| Type *Int8Type = Type::getInt8Ty(Ctx); |
| unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType); |
| assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) && |
| "Atomic memcpy lowering is not supported for selected operand size"); |
| |
| uint64_t LoopEndCount = alignDown(CopyLen->getZExtValue(), LoopOpSize); |
| |
| // Skip the loop expansion entirely if the loop would never be taken. |
| if (LoopEndCount != 0) { |
| LoopExpansionInfo LEI = insertLoopExpansion(InsertBefore, CopyLen, |
| LoopOpSize, 0, "static-memcpy"); |
| |
| // Fill MainLoopBB |
| IRBuilder<> MainLoopBuilder(LEI.MainLoopIP); |
| Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize)); |
| Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize)); |
| |
| // If we used LoopOpType as GEP element type, we would iterate over the |
| // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e., |
| // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use |
| // byte offsets computed from the TypeStoreSize. |
| Value *SrcGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, LEI.MainLoopIndex); |
| LoadInst *Load = MainLoopBuilder.CreateAlignedLoad( |
| LoopOpType, SrcGEP, PartSrcAlign, SrcIsVolatile); |
| if (!CanOverlap) { |
| // Set alias scope for loads. |
| Load->setMetadata(LLVMContext::MD_alias_scope, |
| MDNode::get(Ctx, NewScope)); |
| } |
| Value *DstGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, LEI.MainLoopIndex); |
| StoreInst *Store = MainLoopBuilder.CreateAlignedStore( |
| Load, DstGEP, PartDstAlign, DstIsVolatile); |
| if (!CanOverlap) { |
| // Indicate that stores don't overlap loads. |
| Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope)); |
| } |
| if (AtomicElementSize) { |
| Load->setAtomic(AtomicOrdering::Unordered); |
| Store->setAtomic(AtomicOrdering::Unordered); |
| } |
| assert(!LEI.ResidualLoopIP && !LEI.ResidualLoopIndex && |
| "No residual loop was requested"); |
| } |
| |
| // Copy the remaining bytes with straight-line code. |
| uint64_t BytesCopied = LoopEndCount; |
| uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopied; |
| if (RemainingBytes == 0) |
| return; |
| |
| IRBuilder<> RBuilder(InsertBefore); |
| SmallVector<Type *, 5> RemainingOps; |
| TTI.getMemcpyLoopResidualLoweringType(RemainingOps, Ctx, RemainingBytes, |
| SrcAS, DstAS, SrcAlign, DstAlign, |
| AtomicElementSize); |
| |
| for (auto *OpTy : RemainingOps) { |
| Align PartSrcAlign(commonAlignment(SrcAlign, BytesCopied)); |
| Align PartDstAlign(commonAlignment(DstAlign, BytesCopied)); |
| |
| unsigned OperandSize = DL.getTypeStoreSize(OpTy); |
| assert((!AtomicElementSize || OperandSize % *AtomicElementSize == 0) && |
| "Atomic memcpy lowering is not supported for selected operand size"); |
| |
| Value *SrcGEP = RBuilder.CreateInBoundsGEP( |
| Int8Type, SrcAddr, ConstantInt::get(TypeOfCopyLen, BytesCopied)); |
| LoadInst *Load = |
| RBuilder.CreateAlignedLoad(OpTy, SrcGEP, PartSrcAlign, SrcIsVolatile); |
| if (!CanOverlap) { |
| // Set alias scope for loads. |
| Load->setMetadata(LLVMContext::MD_alias_scope, |
| MDNode::get(Ctx, NewScope)); |
| } |
| Value *DstGEP = RBuilder.CreateInBoundsGEP( |
| Int8Type, DstAddr, ConstantInt::get(TypeOfCopyLen, BytesCopied)); |
| StoreInst *Store = |
| RBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign, DstIsVolatile); |
| if (!CanOverlap) { |
| // Indicate that stores don't overlap loads. |
| Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope)); |
| } |
| if (AtomicElementSize) { |
| Load->setAtomic(AtomicOrdering::Unordered); |
| Store->setAtomic(AtomicOrdering::Unordered); |
| } |
| BytesCopied += OperandSize; |
| } |
| assert(BytesCopied == CopyLen->getZExtValue() && |
| "Bytes copied should match size in the call!"); |
| } |
| |
| void llvm::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) { |
| BasicBlock *PreLoopBB = InsertBefore->getParent(); |
| Function *ParentFunc = PreLoopBB->getParent(); |
| const DataLayout &DL = ParentFunc->getDataLayout(); |
| LLVMContext &Ctx = PreLoopBB->getContext(); |
| MDBuilder MDB(Ctx); |
| MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain"); |
| StringRef Name = "MemCopyAliasScope"; |
| MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name); |
| |
| unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace(); |
| unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace(); |
| |
| Type *LoopOpType = TTI.getMemcpyLoopLoweringType( |
| Ctx, CopyLen, SrcAS, DstAS, SrcAlign, DstAlign, AtomicElementSize); |
| assert((!AtomicElementSize || !LoopOpType->isVectorTy()) && |
| "Atomic memcpy lowering is not supported for vector operand type"); |
| unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType); |
| assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) && |
| "Atomic memcpy lowering is not supported for selected operand size"); |
| |
| Type *Int8Type = Type::getInt8Ty(Ctx); |
| |
| Type *ResidualLoopOpType = AtomicElementSize |
| ? Type::getIntNTy(Ctx, *AtomicElementSize * 8) |
| : Int8Type; |
| unsigned ResidualLoopOpSize = DL.getTypeStoreSize(ResidualLoopOpType); |
| assert(ResidualLoopOpSize == (AtomicElementSize ? *AtomicElementSize : 1) && |
| "Store size is expected to match type size"); |
| |
| LoopExpansionInfo LEI = insertLoopExpansion( |
| InsertBefore, CopyLen, LoopOpSize, ResidualLoopOpSize, "dynamic-memcpy"); |
| |
| // Fill MainLoopBB |
| IRBuilder<> MainLoopBuilder(LEI.MainLoopIP); |
| Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize)); |
| Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize)); |
| |
| // If we used LoopOpType as GEP element type, we would iterate over the |
| // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e., |
| // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use byte |
| // offsets computed from the TypeStoreSize. |
| Value *SrcGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, LEI.MainLoopIndex); |
| LoadInst *Load = MainLoopBuilder.CreateAlignedLoad( |
| LoopOpType, SrcGEP, PartSrcAlign, SrcIsVolatile); |
| if (!CanOverlap) { |
| // Set alias scope for loads. |
| Load->setMetadata(LLVMContext::MD_alias_scope, MDNode::get(Ctx, NewScope)); |
| } |
| Value *DstGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, LEI.MainLoopIndex); |
| StoreInst *Store = MainLoopBuilder.CreateAlignedStore( |
| Load, DstGEP, PartDstAlign, DstIsVolatile); |
| if (!CanOverlap) { |
| // Indicate that stores don't overlap loads. |
| Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope)); |
| } |
| if (AtomicElementSize) { |
| Load->setAtomic(AtomicOrdering::Unordered); |
| Store->setAtomic(AtomicOrdering::Unordered); |
| } |
| |
| // Fill ResidualLoopBB. |
| if (!LEI.ResidualLoopIP) |
| return; |
| |
| Align ResSrcAlign(commonAlignment(PartSrcAlign, ResidualLoopOpSize)); |
| Align ResDstAlign(commonAlignment(PartDstAlign, ResidualLoopOpSize)); |
| |
| IRBuilder<> ResLoopBuilder(LEI.ResidualLoopIP); |
| Value *ResSrcGEP = ResLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, |
| LEI.ResidualLoopIndex); |
| LoadInst *ResLoad = ResLoopBuilder.CreateAlignedLoad( |
| ResidualLoopOpType, ResSrcGEP, ResSrcAlign, SrcIsVolatile); |
| if (!CanOverlap) { |
| // Set alias scope for loads. |
| ResLoad->setMetadata(LLVMContext::MD_alias_scope, |
| MDNode::get(Ctx, NewScope)); |
| } |
| Value *ResDstGEP = ResLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, |
| LEI.ResidualLoopIndex); |
| StoreInst *ResStore = ResLoopBuilder.CreateAlignedStore( |
| ResLoad, ResDstGEP, ResDstAlign, DstIsVolatile); |
| if (!CanOverlap) { |
| // Indicate that stores don't overlap loads. |
| ResStore->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope)); |
| } |
| if (AtomicElementSize) { |
| ResLoad->setAtomic(AtomicOrdering::Unordered); |
| ResStore->setAtomic(AtomicOrdering::Unordered); |
| } |
| } |
| |
| // If \p Addr1 and \p Addr2 are pointers to different address spaces, create an |
| // addresspacecast to obtain a pair of pointers in the same addressspace. The |
| // caller needs to ensure that addrspacecasting is possible. |
| // No-op if the pointers are in the same address space. |
| static std::pair<Value *, Value *> |
| tryInsertCastToCommonAddrSpace(IRBuilderBase &B, Value *Addr1, Value *Addr2, |
| const TargetTransformInfo &TTI) { |
| Value *ResAddr1 = Addr1; |
| Value *ResAddr2 = Addr2; |
| |
| unsigned AS1 = cast<PointerType>(Addr1->getType())->getAddressSpace(); |
| unsigned AS2 = cast<PointerType>(Addr2->getType())->getAddressSpace(); |
| if (AS1 != AS2) { |
| if (TTI.isValidAddrSpaceCast(AS2, AS1)) |
| ResAddr2 = B.CreateAddrSpaceCast(Addr2, Addr1->getType()); |
| else if (TTI.isValidAddrSpaceCast(AS1, AS2)) |
| ResAddr1 = B.CreateAddrSpaceCast(Addr1, Addr2->getType()); |
| else |
| llvm_unreachable("Can only lower memmove between address spaces if they " |
| "support addrspacecast"); |
| } |
| return {ResAddr1, ResAddr2}; |
| } |
| |
| // Lower memmove to IR. memmove is required to correctly copy overlapping memory |
| // regions; therefore, it has to check the relative positions of the source and |
| // destination pointers and choose the copy direction accordingly. |
| // |
| // The code below is an IR rendition of this C function: |
| // |
| // void* memmove(void* dst, const void* src, size_t n) { |
| // unsigned char* d = dst; |
| // const unsigned char* s = src; |
| // if (s < d) { |
| // // copy backwards |
| // while (n--) { |
| // d[n] = s[n]; |
| // } |
| // } else { |
| // // copy forward |
| // for (size_t i = 0; i < n; ++i) { |
| // d[i] = s[i]; |
| // } |
| // } |
| // return dst; |
| // } |
| // |
| // If the TargetTransformInfo specifies a wider MemcpyLoopLoweringType, it is |
| // used for the memory accesses in the loops. Then, additional loops with |
| // byte-wise accesses are added for the remaining bytes. |
| static void createMemMoveLoopUnknownSize(Instruction *InsertBefore, |
| Value *SrcAddr, Value *DstAddr, |
| Value *CopyLen, Align SrcAlign, |
| Align DstAlign, bool SrcIsVolatile, |
| bool DstIsVolatile, |
| const TargetTransformInfo &TTI) { |
| Type *TypeOfCopyLen = CopyLen->getType(); |
| BasicBlock *OrigBB = InsertBefore->getParent(); |
| Function *F = OrigBB->getParent(); |
| const DataLayout &DL = F->getDataLayout(); |
| LLVMContext &Ctx = OrigBB->getContext(); |
| unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace(); |
| unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace(); |
| |
| Type *LoopOpType = TTI.getMemcpyLoopLoweringType(Ctx, CopyLen, SrcAS, DstAS, |
| SrcAlign, DstAlign); |
| unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType); |
| Type *Int8Type = Type::getInt8Ty(Ctx); |
| bool LoopOpIsInt8 = LoopOpType == Int8Type; |
| |
| // If the memory accesses are wider than one byte, residual loops with |
| // i8-accesses are required to move remaining bytes. |
| bool RequiresResidual = !LoopOpIsInt8; |
| |
| Type *ResidualLoopOpType = Int8Type; |
| unsigned ResidualLoopOpSize = DL.getTypeStoreSize(ResidualLoopOpType); |
| |
| // Calculate the loop trip count and remaining bytes to copy after the loop. |
| IntegerType *ILengthType = cast<IntegerType>(TypeOfCopyLen); |
| ConstantInt *CILoopOpSize = ConstantInt::get(ILengthType, LoopOpSize); |
| ConstantInt *CIResidualLoopOpSize = |
| ConstantInt::get(ILengthType, ResidualLoopOpSize); |
| ConstantInt *Zero = ConstantInt::get(ILengthType, 0); |
| |
| IRBuilder<> PLBuilder(InsertBefore); |
| |
| Value *RuntimeLoopBytes = CopyLen; |
| Value *RuntimeLoopRemainder = nullptr; |
| Value *SkipResidualCondition = nullptr; |
| if (RequiresResidual) { |
| RuntimeLoopRemainder = |
| getRuntimeLoopRemainder(PLBuilder, CopyLen, CILoopOpSize, LoopOpSize); |
| RuntimeLoopBytes = getRuntimeLoopUnits(PLBuilder, CopyLen, CILoopOpSize, |
| LoopOpSize, RuntimeLoopRemainder); |
| SkipResidualCondition = |
| PLBuilder.CreateICmpEQ(RuntimeLoopRemainder, Zero, "skip_residual"); |
| } |
| Value *SkipMainCondition = |
| PLBuilder.CreateICmpEQ(RuntimeLoopBytes, Zero, "skip_main"); |
| |
| // Create the a comparison of src and dst, based on which we jump to either |
| // the forward-copy part of the function (if src >= dst) or the backwards-copy |
| // part (if src < dst). |
| // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else |
| // structure. Its block terminators (unconditional branches) are replaced by |
| // the appropriate conditional branches when the loop is built. |
| // If the pointers are in different address spaces, they need to be converted |
| // to a compatible one. Cases where memory ranges in the different address |
| // spaces cannot overlap are lowered as memcpy and not handled here. |
| auto [CmpSrcAddr, CmpDstAddr] = |
| tryInsertCastToCommonAddrSpace(PLBuilder, SrcAddr, DstAddr, TTI); |
| Value *PtrCompare = |
| PLBuilder.CreateICmpULT(CmpSrcAddr, CmpDstAddr, "compare_src_dst"); |
| Instruction *ThenTerm, *ElseTerm; |
| SplitBlockAndInsertIfThenElse(PtrCompare, InsertBefore->getIterator(), |
| &ThenTerm, &ElseTerm); |
| |
| // If the LoopOpSize is greater than 1, each part of the function consists of |
| // four blocks: |
| // memmove_copy_backwards: |
| // skip the residual loop when 0 iterations are required |
| // memmove_bwd_residual_loop: |
| // copy the last few bytes individually so that the remaining length is |
| // a multiple of the LoopOpSize |
| // memmove_bwd_middle: skip the main loop when 0 iterations are required |
| // memmove_bwd_main_loop: the actual backwards loop BB with wide accesses |
| // memmove_copy_forward: skip the main loop when 0 iterations are required |
| // memmove_fwd_main_loop: the actual forward loop BB with wide accesses |
| // memmove_fwd_middle: skip the residual loop when 0 iterations are required |
| // memmove_fwd_residual_loop: copy the last few bytes individually |
| // |
| // The main and residual loop are switched between copying forward and |
| // backward so that the residual loop always operates on the end of the moved |
| // range. This is based on the assumption that buffers whose start is aligned |
| // with the LoopOpSize are more common than buffers whose end is. |
| // |
| // If the LoopOpSize is 1, each part of the function consists of two blocks: |
| // memmove_copy_backwards: skip the loop when 0 iterations are required |
| // memmove_bwd_main_loop: the actual backwards loop BB |
| // memmove_copy_forward: skip the loop when 0 iterations are required |
| // memmove_fwd_main_loop: the actual forward loop BB |
| BasicBlock *CopyBackwardsBB = ThenTerm->getParent(); |
| CopyBackwardsBB->setName("memmove_copy_backwards"); |
| BasicBlock *CopyForwardBB = ElseTerm->getParent(); |
| CopyForwardBB->setName("memmove_copy_forward"); |
| BasicBlock *ExitBB = InsertBefore->getParent(); |
| ExitBB->setName("memmove_done"); |
| |
| Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize)); |
| Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize)); |
| |
| // Accesses in the residual loops do not share the same alignment as those in |
| // the main loops. |
| Align ResidualSrcAlign(commonAlignment(PartSrcAlign, ResidualLoopOpSize)); |
| Align ResidualDstAlign(commonAlignment(PartDstAlign, ResidualLoopOpSize)); |
| |
| // Copying backwards. |
| { |
| BasicBlock *MainLoopBB = BasicBlock::Create( |
| F->getContext(), "memmove_bwd_main_loop", F, CopyForwardBB); |
| |
| // The predecessor of the memmove_bwd_main_loop. Updated in the |
| // following if a residual loop is emitted first. |
| BasicBlock *PredBB = CopyBackwardsBB; |
| |
| if (RequiresResidual) { |
| // backwards residual loop |
| BasicBlock *ResidualLoopBB = BasicBlock::Create( |
| F->getContext(), "memmove_bwd_residual_loop", F, MainLoopBB); |
| IRBuilder<> ResidualLoopBuilder(ResidualLoopBB); |
| PHINode *ResidualLoopPhi = ResidualLoopBuilder.CreatePHI(ILengthType, 0); |
| Value *ResidualIndex = ResidualLoopBuilder.CreateSub( |
| ResidualLoopPhi, CIResidualLoopOpSize, "bwd_residual_index"); |
| // If we used LoopOpType as GEP element type, we would iterate over the |
| // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, |
| // i.e., we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, |
| // use byte offsets computed from the TypeStoreSize. |
| Value *LoadGEP = ResidualLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, |
| ResidualIndex); |
| Value *Element = ResidualLoopBuilder.CreateAlignedLoad( |
| ResidualLoopOpType, LoadGEP, ResidualSrcAlign, SrcIsVolatile, |
| "element"); |
| Value *StoreGEP = ResidualLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, |
| ResidualIndex); |
| ResidualLoopBuilder.CreateAlignedStore(Element, StoreGEP, |
| ResidualDstAlign, DstIsVolatile); |
| |
| // After the residual loop, go to an intermediate block. |
| BasicBlock *IntermediateBB = BasicBlock::Create( |
| F->getContext(), "memmove_bwd_middle", F, MainLoopBB); |
| // Later code expects a terminator in the PredBB. |
| IRBuilder<> IntermediateBuilder(IntermediateBB); |
| IntermediateBuilder.CreateUnreachable(); |
| ResidualLoopBuilder.CreateCondBr( |
| ResidualLoopBuilder.CreateICmpEQ(ResidualIndex, RuntimeLoopBytes), |
| IntermediateBB, ResidualLoopBB); |
| |
| ResidualLoopPhi->addIncoming(ResidualIndex, ResidualLoopBB); |
| ResidualLoopPhi->addIncoming(CopyLen, CopyBackwardsBB); |
| |
| // How to get to the residual: |
| BranchInst::Create(IntermediateBB, ResidualLoopBB, SkipResidualCondition, |
| ThenTerm->getIterator()); |
| ThenTerm->eraseFromParent(); |
| |
| PredBB = IntermediateBB; |
| } |
| |
| // main loop |
| IRBuilder<> MainLoopBuilder(MainLoopBB); |
| PHINode *MainLoopPhi = MainLoopBuilder.CreatePHI(ILengthType, 0); |
| Value *MainIndex = |
| MainLoopBuilder.CreateSub(MainLoopPhi, CILoopOpSize, "bwd_main_index"); |
| Value *LoadGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, MainIndex); |
| Value *Element = MainLoopBuilder.CreateAlignedLoad( |
| LoopOpType, LoadGEP, PartSrcAlign, SrcIsVolatile, "element"); |
| Value *StoreGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, MainIndex); |
| MainLoopBuilder.CreateAlignedStore(Element, StoreGEP, PartDstAlign, |
| DstIsVolatile); |
| MainLoopBuilder.CreateCondBr(MainLoopBuilder.CreateICmpEQ(MainIndex, Zero), |
| ExitBB, MainLoopBB); |
| MainLoopPhi->addIncoming(MainIndex, MainLoopBB); |
| MainLoopPhi->addIncoming(RuntimeLoopBytes, PredBB); |
| |
| // How to get to the main loop: |
| Instruction *PredBBTerm = PredBB->getTerminator(); |
| BranchInst::Create(ExitBB, MainLoopBB, SkipMainCondition, |
| PredBBTerm->getIterator()); |
| PredBBTerm->eraseFromParent(); |
| } |
| |
| // Copying forward. |
| // main loop |
| { |
| BasicBlock *MainLoopBB = |
| BasicBlock::Create(F->getContext(), "memmove_fwd_main_loop", F, ExitBB); |
| IRBuilder<> MainLoopBuilder(MainLoopBB); |
| PHINode *MainLoopPhi = |
| MainLoopBuilder.CreatePHI(ILengthType, 0, "fwd_main_index"); |
| Value *LoadGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, MainLoopPhi); |
| Value *Element = MainLoopBuilder.CreateAlignedLoad( |
| LoopOpType, LoadGEP, PartSrcAlign, SrcIsVolatile, "element"); |
| Value *StoreGEP = |
| MainLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, MainLoopPhi); |
| MainLoopBuilder.CreateAlignedStore(Element, StoreGEP, PartDstAlign, |
| DstIsVolatile); |
| Value *MainIndex = MainLoopBuilder.CreateAdd(MainLoopPhi, CILoopOpSize); |
| MainLoopPhi->addIncoming(MainIndex, MainLoopBB); |
| MainLoopPhi->addIncoming(Zero, CopyForwardBB); |
| |
| Instruction *CopyFwdBBTerm = CopyForwardBB->getTerminator(); |
| BasicBlock *SuccessorBB = ExitBB; |
| if (RequiresResidual) |
| SuccessorBB = |
| BasicBlock::Create(F->getContext(), "memmove_fwd_middle", F, ExitBB); |
| |
| // leaving or staying in the main loop |
| MainLoopBuilder.CreateCondBr( |
| MainLoopBuilder.CreateICmpEQ(MainIndex, RuntimeLoopBytes), SuccessorBB, |
| MainLoopBB); |
| |
| // getting in or skipping the main loop |
| BranchInst::Create(SuccessorBB, MainLoopBB, SkipMainCondition, |
| CopyFwdBBTerm->getIterator()); |
| CopyFwdBBTerm->eraseFromParent(); |
| |
| if (RequiresResidual) { |
| BasicBlock *IntermediateBB = SuccessorBB; |
| IRBuilder<> IntermediateBuilder(IntermediateBB); |
| BasicBlock *ResidualLoopBB = BasicBlock::Create( |
| F->getContext(), "memmove_fwd_residual_loop", F, ExitBB); |
| IntermediateBuilder.CreateCondBr(SkipResidualCondition, ExitBB, |
| ResidualLoopBB); |
| |
| // Residual loop |
| IRBuilder<> ResidualLoopBuilder(ResidualLoopBB); |
| PHINode *ResidualLoopPhi = |
| ResidualLoopBuilder.CreatePHI(ILengthType, 0, "fwd_residual_index"); |
| Value *LoadGEP = ResidualLoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, |
| ResidualLoopPhi); |
| Value *Element = ResidualLoopBuilder.CreateAlignedLoad( |
| ResidualLoopOpType, LoadGEP, ResidualSrcAlign, SrcIsVolatile, |
| "element"); |
| Value *StoreGEP = ResidualLoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, |
| ResidualLoopPhi); |
| ResidualLoopBuilder.CreateAlignedStore(Element, StoreGEP, |
| ResidualDstAlign, DstIsVolatile); |
| Value *ResidualIndex = |
| ResidualLoopBuilder.CreateAdd(ResidualLoopPhi, CIResidualLoopOpSize); |
| ResidualLoopBuilder.CreateCondBr( |
| ResidualLoopBuilder.CreateICmpEQ(ResidualIndex, CopyLen), ExitBB, |
| ResidualLoopBB); |
| ResidualLoopPhi->addIncoming(ResidualIndex, ResidualLoopBB); |
| ResidualLoopPhi->addIncoming(RuntimeLoopBytes, IntermediateBB); |
| } |
| } |
| } |
| |
| // Similar to createMemMoveLoopUnknownSize, only the trip counts are computed at |
| // compile time, obsolete loops and branches are omitted, and the residual code |
| // is straight-line code instead of a loop. |
| static void createMemMoveLoopKnownSize(Instruction *InsertBefore, |
| Value *SrcAddr, Value *DstAddr, |
| ConstantInt *CopyLen, Align SrcAlign, |
| Align DstAlign, bool SrcIsVolatile, |
| bool DstIsVolatile, |
| const TargetTransformInfo &TTI) { |
| // No need to expand zero length moves. |
| if (CopyLen->isZero()) |
| return; |
| |
| Type *TypeOfCopyLen = CopyLen->getType(); |
| BasicBlock *OrigBB = InsertBefore->getParent(); |
| Function *F = OrigBB->getParent(); |
| const DataLayout &DL = F->getDataLayout(); |
| LLVMContext &Ctx = OrigBB->getContext(); |
| unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace(); |
| unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace(); |
| |
| Type *LoopOpType = TTI.getMemcpyLoopLoweringType(Ctx, CopyLen, SrcAS, DstAS, |
| SrcAlign, DstAlign); |
| unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType); |
| Type *Int8Type = Type::getInt8Ty(Ctx); |
| |
| // Calculate the loop trip count and remaining bytes to copy after the loop. |
| uint64_t BytesCopiedInLoop = alignDown(CopyLen->getZExtValue(), LoopOpSize); |
| uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopiedInLoop; |
| |
| IntegerType *ILengthType = cast<IntegerType>(TypeOfCopyLen); |
| ConstantInt *Zero = ConstantInt::get(ILengthType, 0); |
| ConstantInt *LoopBound = ConstantInt::get(ILengthType, BytesCopiedInLoop); |
| ConstantInt *CILoopOpSize = ConstantInt::get(ILengthType, LoopOpSize); |
| |
| IRBuilder<> PLBuilder(InsertBefore); |
| |
| auto [CmpSrcAddr, CmpDstAddr] = |
| tryInsertCastToCommonAddrSpace(PLBuilder, SrcAddr, DstAddr, TTI); |
| Value *PtrCompare = |
| PLBuilder.CreateICmpULT(CmpSrcAddr, CmpDstAddr, "compare_src_dst"); |
| Instruction *ThenTerm, *ElseTerm; |
| SplitBlockAndInsertIfThenElse(PtrCompare, InsertBefore->getIterator(), |
| &ThenTerm, &ElseTerm); |
| |
| BasicBlock *CopyBackwardsBB = ThenTerm->getParent(); |
| BasicBlock *CopyForwardBB = ElseTerm->getParent(); |
| BasicBlock *ExitBB = InsertBefore->getParent(); |
| ExitBB->setName("memmove_done"); |
| |
| Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize)); |
| Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize)); |
| |
| // Helper function to generate a load/store pair of a given type in the |
| // residual. Used in the forward and backward branches. |
| auto GenerateResidualLdStPair = [&](Type *OpTy, IRBuilderBase &Builder, |
| uint64_t &BytesCopied) { |
| Align ResSrcAlign(commonAlignment(SrcAlign, BytesCopied)); |
| Align ResDstAlign(commonAlignment(DstAlign, BytesCopied)); |
| |
| unsigned OperandSize = DL.getTypeStoreSize(OpTy); |
| |
| // If we used LoopOpType as GEP element type, we would iterate over the |
| // buffers in TypeStoreSize strides while copying TypeAllocSize bytes, i.e., |
| // we would miss bytes if TypeStoreSize != TypeAllocSize. Therefore, use |
| // byte offsets computed from the TypeStoreSize. |
| Value *SrcGEP = Builder.CreateInBoundsGEP( |
| Int8Type, SrcAddr, ConstantInt::get(TypeOfCopyLen, BytesCopied)); |
| LoadInst *Load = |
| Builder.CreateAlignedLoad(OpTy, SrcGEP, ResSrcAlign, SrcIsVolatile); |
| Value *DstGEP = Builder.CreateInBoundsGEP( |
| Int8Type, DstAddr, ConstantInt::get(TypeOfCopyLen, BytesCopied)); |
| Builder.CreateAlignedStore(Load, DstGEP, ResDstAlign, DstIsVolatile); |
| BytesCopied += OperandSize; |
| }; |
| |
| // Copying backwards. |
| if (RemainingBytes != 0) { |
| CopyBackwardsBB->setName("memmove_bwd_residual"); |
| uint64_t BytesCopied = BytesCopiedInLoop; |
| |
| // Residual code is required to move the remaining bytes. We need the same |
| // instructions as in the forward case, only in reverse. So we generate code |
| // the same way, except that we change the IRBuilder insert point for each |
| // load/store pair so that each one is inserted before the previous one |
| // instead of after it. |
| IRBuilder<> BwdResBuilder(CopyBackwardsBB, |
| CopyBackwardsBB->getFirstNonPHIIt()); |
| SmallVector<Type *, 5> RemainingOps; |
| TTI.getMemcpyLoopResidualLoweringType(RemainingOps, Ctx, RemainingBytes, |
| SrcAS, DstAS, PartSrcAlign, |
| PartDstAlign); |
| for (auto *OpTy : RemainingOps) { |
| // reverse the order of the emitted operations |
| BwdResBuilder.SetInsertPoint(CopyBackwardsBB, |
| CopyBackwardsBB->getFirstNonPHIIt()); |
| GenerateResidualLdStPair(OpTy, BwdResBuilder, BytesCopied); |
| } |
| } |
| if (BytesCopiedInLoop != 0) { |
| BasicBlock *LoopBB = CopyBackwardsBB; |
| BasicBlock *PredBB = OrigBB; |
| if (RemainingBytes != 0) { |
| // if we introduce residual code, it needs its separate BB |
| LoopBB = CopyBackwardsBB->splitBasicBlock( |
| CopyBackwardsBB->getTerminator(), "memmove_bwd_loop"); |
| PredBB = CopyBackwardsBB; |
| } else { |
| CopyBackwardsBB->setName("memmove_bwd_loop"); |
| } |
| IRBuilder<> LoopBuilder(LoopBB->getTerminator()); |
| PHINode *LoopPhi = LoopBuilder.CreatePHI(ILengthType, 0); |
| Value *Index = LoopBuilder.CreateSub(LoopPhi, CILoopOpSize, "bwd_index"); |
| Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, Index); |
| Value *Element = LoopBuilder.CreateAlignedLoad( |
| LoopOpType, LoadGEP, PartSrcAlign, SrcIsVolatile, "element"); |
| Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, Index); |
| LoopBuilder.CreateAlignedStore(Element, StoreGEP, PartDstAlign, |
| DstIsVolatile); |
| |
| // Replace the unconditional branch introduced by |
| // SplitBlockAndInsertIfThenElse to turn LoopBB into a loop. |
| Instruction *UncondTerm = LoopBB->getTerminator(); |
| LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpEQ(Index, Zero), ExitBB, |
| LoopBB); |
| UncondTerm->eraseFromParent(); |
| |
| LoopPhi->addIncoming(Index, LoopBB); |
| LoopPhi->addIncoming(LoopBound, PredBB); |
| } |
| |
| // Copying forward. |
| BasicBlock *FwdResidualBB = CopyForwardBB; |
| if (BytesCopiedInLoop != 0) { |
| CopyForwardBB->setName("memmove_fwd_loop"); |
| BasicBlock *LoopBB = CopyForwardBB; |
| BasicBlock *SuccBB = ExitBB; |
| if (RemainingBytes != 0) { |
| // if we introduce residual code, it needs its separate BB |
| SuccBB = CopyForwardBB->splitBasicBlock(CopyForwardBB->getTerminator(), |
| "memmove_fwd_residual"); |
| FwdResidualBB = SuccBB; |
| } |
| IRBuilder<> LoopBuilder(LoopBB->getTerminator()); |
| PHINode *LoopPhi = LoopBuilder.CreatePHI(ILengthType, 0, "fwd_index"); |
| Value *LoadGEP = LoopBuilder.CreateInBoundsGEP(Int8Type, SrcAddr, LoopPhi); |
| Value *Element = LoopBuilder.CreateAlignedLoad( |
| LoopOpType, LoadGEP, PartSrcAlign, SrcIsVolatile, "element"); |
| Value *StoreGEP = LoopBuilder.CreateInBoundsGEP(Int8Type, DstAddr, LoopPhi); |
| LoopBuilder.CreateAlignedStore(Element, StoreGEP, PartDstAlign, |
| DstIsVolatile); |
| Value *Index = LoopBuilder.CreateAdd(LoopPhi, CILoopOpSize); |
| LoopPhi->addIncoming(Index, LoopBB); |
| LoopPhi->addIncoming(Zero, OrigBB); |
| |
| // Replace the unconditional branch to turn LoopBB into a loop. |
| Instruction *UncondTerm = LoopBB->getTerminator(); |
| LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpEQ(Index, LoopBound), SuccBB, |
| LoopBB); |
| UncondTerm->eraseFromParent(); |
| } |
| |
| if (RemainingBytes != 0) { |
| uint64_t BytesCopied = BytesCopiedInLoop; |
| |
| // Residual code is required to move the remaining bytes. In the forward |
| // case, we emit it in the normal order. |
| IRBuilder<> FwdResBuilder(FwdResidualBB->getTerminator()); |
| SmallVector<Type *, 5> RemainingOps; |
| TTI.getMemcpyLoopResidualLoweringType(RemainingOps, Ctx, RemainingBytes, |
| SrcAS, DstAS, PartSrcAlign, |
| PartDstAlign); |
| for (auto *OpTy : RemainingOps) |
| GenerateResidualLdStPair(OpTy, FwdResBuilder, BytesCopied); |
| } |
| } |
| |
| static void createMemSetLoop(Instruction *InsertBefore, Value *DstAddr, |
| Value *CopyLen, Value *SetValue, Align DstAlign, |
| bool IsVolatile) { |
| Type *TypeOfCopyLen = CopyLen->getType(); |
| BasicBlock *OrigBB = InsertBefore->getParent(); |
| Function *F = OrigBB->getParent(); |
| const DataLayout &DL = F->getDataLayout(); |
| BasicBlock *NewBB = |
| OrigBB->splitBasicBlock(InsertBefore, "split"); |
| BasicBlock *LoopBB |
| = BasicBlock::Create(F->getContext(), "loadstoreloop", F, NewBB); |
| |
| IRBuilder<> Builder(OrigBB->getTerminator()); |
| |
| Builder.CreateCondBr( |
| Builder.CreateICmpEQ(ConstantInt::get(TypeOfCopyLen, 0), CopyLen), NewBB, |
| LoopBB); |
| OrigBB->getTerminator()->eraseFromParent(); |
| |
| unsigned PartSize = DL.getTypeStoreSize(SetValue->getType()); |
| Align PartAlign(commonAlignment(DstAlign, PartSize)); |
| |
| IRBuilder<> LoopBuilder(LoopBB); |
| PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0); |
| LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB); |
| |
| LoopBuilder.CreateAlignedStore( |
| SetValue, |
| LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex), |
| PartAlign, IsVolatile); |
| |
| Value *NewIndex = |
| LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1)); |
| LoopIndex->addIncoming(NewIndex, LoopBB); |
| |
| LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB, |
| NewBB); |
| } |
| |
| template <typename T> |
| static bool canOverlap(MemTransferBase<T> *Memcpy, ScalarEvolution *SE) { |
| if (SE) { |
| const SCEV *SrcSCEV = SE->getSCEV(Memcpy->getRawSource()); |
| const SCEV *DestSCEV = SE->getSCEV(Memcpy->getRawDest()); |
| if (SE->isKnownPredicateAt(CmpInst::ICMP_NE, SrcSCEV, DestSCEV, Memcpy)) |
| return false; |
| } |
| return true; |
| } |
| |
| void llvm::expandMemCpyAsLoop(MemCpyInst *Memcpy, |
| const TargetTransformInfo &TTI, |
| ScalarEvolution *SE) { |
| bool CanOverlap = canOverlap(Memcpy, SE); |
| if (ConstantInt *CI = dyn_cast<ConstantInt>(Memcpy->getLength())) { |
| createMemCpyLoopKnownSize( |
| /* InsertBefore */ Memcpy, |
| /* SrcAddr */ Memcpy->getRawSource(), |
| /* DstAddr */ Memcpy->getRawDest(), |
| /* CopyLen */ CI, |
| /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(), |
| /* DestAlign */ Memcpy->getDestAlign().valueOrOne(), |
| /* SrcIsVolatile */ Memcpy->isVolatile(), |
| /* DstIsVolatile */ Memcpy->isVolatile(), |
| /* CanOverlap */ CanOverlap, |
| /* TargetTransformInfo */ TTI); |
| } else { |
| createMemCpyLoopUnknownSize( |
| /* InsertBefore */ Memcpy, |
| /* SrcAddr */ Memcpy->getRawSource(), |
| /* DstAddr */ Memcpy->getRawDest(), |
| /* CopyLen */ Memcpy->getLength(), |
| /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(), |
| /* DestAlign */ Memcpy->getDestAlign().valueOrOne(), |
| /* SrcIsVolatile */ Memcpy->isVolatile(), |
| /* DstIsVolatile */ Memcpy->isVolatile(), |
| /* CanOverlap */ CanOverlap, |
| /* TargetTransformInfo */ TTI); |
| } |
| } |
| |
| bool llvm::expandMemMoveAsLoop(MemMoveInst *Memmove, |
| const TargetTransformInfo &TTI) { |
| Value *CopyLen = Memmove->getLength(); |
| Value *SrcAddr = Memmove->getRawSource(); |
| Value *DstAddr = Memmove->getRawDest(); |
| Align SrcAlign = Memmove->getSourceAlign().valueOrOne(); |
| Align DstAlign = Memmove->getDestAlign().valueOrOne(); |
| bool SrcIsVolatile = Memmove->isVolatile(); |
| bool DstIsVolatile = SrcIsVolatile; |
| IRBuilder<> CastBuilder(Memmove); |
| |
| unsigned SrcAS = SrcAddr->getType()->getPointerAddressSpace(); |
| unsigned DstAS = DstAddr->getType()->getPointerAddressSpace(); |
| if (SrcAS != DstAS) { |
| if (!TTI.addrspacesMayAlias(SrcAS, DstAS)) { |
| // We may not be able to emit a pointer comparison, but we don't have |
| // to. Expand as memcpy. |
| if (ConstantInt *CI = dyn_cast<ConstantInt>(CopyLen)) { |
| createMemCpyLoopKnownSize(/*InsertBefore=*/Memmove, SrcAddr, DstAddr, |
| CI, SrcAlign, DstAlign, SrcIsVolatile, |
| DstIsVolatile, |
| /*CanOverlap=*/false, TTI); |
| } else { |
| createMemCpyLoopUnknownSize(/*InsertBefore=*/Memmove, SrcAddr, DstAddr, |
| CopyLen, SrcAlign, DstAlign, SrcIsVolatile, |
| DstIsVolatile, |
| /*CanOverlap=*/false, TTI); |
| } |
| |
| return true; |
| } |
| |
| if (!(TTI.isValidAddrSpaceCast(DstAS, SrcAS) || |
| TTI.isValidAddrSpaceCast(SrcAS, DstAS))) { |
| // We don't know generically if it's legal to introduce an |
| // addrspacecast. We need to know either if it's legal to insert an |
| // addrspacecast, or if the address spaces cannot alias. |
| LLVM_DEBUG( |
| dbgs() << "Do not know how to expand memmove between different " |
| "address spaces\n"); |
| return false; |
| } |
| } |
| |
| if (ConstantInt *CI = dyn_cast<ConstantInt>(CopyLen)) { |
| createMemMoveLoopKnownSize( |
| /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CI, SrcAlign, DstAlign, |
| SrcIsVolatile, DstIsVolatile, TTI); |
| } else { |
| createMemMoveLoopUnknownSize( |
| /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign, DstAlign, |
| SrcIsVolatile, DstIsVolatile, TTI); |
| } |
| return true; |
| } |
| |
| void llvm::expandMemSetAsLoop(MemSetInst *Memset) { |
| createMemSetLoop(/* InsertBefore */ Memset, |
| /* DstAddr */ Memset->getRawDest(), |
| /* CopyLen */ Memset->getLength(), |
| /* SetValue */ Memset->getValue(), |
| /* Alignment */ Memset->getDestAlign().valueOrOne(), |
| Memset->isVolatile()); |
| } |
| |
| void llvm::expandMemSetPatternAsLoop(MemSetPatternInst *Memset) { |
| createMemSetLoop(/* InsertBefore=*/Memset, |
| /* DstAddr=*/Memset->getRawDest(), |
| /* CopyLen=*/Memset->getLength(), |
| /* SetValue=*/Memset->getValue(), |
| /* Alignment=*/Memset->getDestAlign().valueOrOne(), |
| Memset->isVolatile()); |
| } |
| |
| void llvm::expandAtomicMemCpyAsLoop(AnyMemCpyInst *AtomicMemcpy, |
| const TargetTransformInfo &TTI, |
| ScalarEvolution *SE) { |
| assert(AtomicMemcpy->isAtomic()); |
| if (ConstantInt *CI = dyn_cast<ConstantInt>(AtomicMemcpy->getLength())) { |
| createMemCpyLoopKnownSize( |
| /* InsertBefore */ AtomicMemcpy, |
| /* SrcAddr */ AtomicMemcpy->getRawSource(), |
| /* DstAddr */ AtomicMemcpy->getRawDest(), |
| /* CopyLen */ CI, |
| /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(), |
| /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(), |
| /* SrcIsVolatile */ AtomicMemcpy->isVolatile(), |
| /* DstIsVolatile */ AtomicMemcpy->isVolatile(), |
| /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec. |
| /* TargetTransformInfo */ TTI, |
| /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes()); |
| } else { |
| createMemCpyLoopUnknownSize( |
| /* InsertBefore */ AtomicMemcpy, |
| /* SrcAddr */ AtomicMemcpy->getRawSource(), |
| /* DstAddr */ AtomicMemcpy->getRawDest(), |
| /* CopyLen */ AtomicMemcpy->getLength(), |
| /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(), |
| /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(), |
| /* SrcIsVolatile */ AtomicMemcpy->isVolatile(), |
| /* DstIsVolatile */ AtomicMemcpy->isVolatile(), |
| /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec. |
| /* TargetTransformInfo */ TTI, |
| /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes()); |
| } |
| } |
