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/Support/Debug.h"
16 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
17 #include <optional>
18 
19 #define DEBUG_TYPE "lower-mem-intrinsics"
20 
21 using namespace llvm;
22 
23 void llvm::createMemCpyLoopKnownSize(
24     Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr,
25     ConstantInt *CopyLen, Align SrcAlign, Align DstAlign, bool SrcIsVolatile,
26     bool DstIsVolatile, bool CanOverlap, const TargetTransformInfo &TTI,
27     std::optional<uint32_t> AtomicElementSize) {
28   // No need to expand zero length copies.
29   if (CopyLen->isZero())
30     return;
31 
32   BasicBlock *PreLoopBB = InsertBefore->getParent();
33   BasicBlock *PostLoopBB = nullptr;
34   Function *ParentFunc = PreLoopBB->getParent();
35   LLVMContext &Ctx = PreLoopBB->getContext();
36   const DataLayout &DL = ParentFunc->getParent()->getDataLayout();
37   MDBuilder MDB(Ctx);
38   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain");
39   StringRef Name = "MemCopyAliasScope";
40   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
41 
42   unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
43   unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
44 
45   Type *TypeOfCopyLen = CopyLen->getType();
46   Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
47       Ctx, CopyLen, SrcAS, DstAS, SrcAlign.value(), DstAlign.value(),
48       AtomicElementSize);
49   assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
50          "Atomic memcpy lowering is not supported for vector operand type");
51 
52   unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType);
53   assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
54       "Atomic memcpy lowering is not supported for selected operand size");
55 
56   uint64_t LoopEndCount = CopyLen->getZExtValue() / LoopOpSize;
57 
58   if (LoopEndCount != 0) {
59     // Split
60     PostLoopBB = PreLoopBB->splitBasicBlock(InsertBefore, "memcpy-split");
61     BasicBlock *LoopBB =
62         BasicBlock::Create(Ctx, "load-store-loop", ParentFunc, PostLoopBB);
63     PreLoopBB->getTerminator()->setSuccessor(0, LoopBB);
64 
65     IRBuilder<> PLBuilder(PreLoopBB->getTerminator());
66 
67     Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize));
68     Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize));
69 
70     IRBuilder<> LoopBuilder(LoopBB);
71     PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 2, "loop-index");
72     LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0U), PreLoopBB);
73     // Loop Body
74     Value *SrcGEP =
75         LoopBuilder.CreateInBoundsGEP(LoopOpType, SrcAddr, LoopIndex);
76     LoadInst *Load = LoopBuilder.CreateAlignedLoad(LoopOpType, SrcGEP,
77                                                    PartSrcAlign, SrcIsVolatile);
78     if (!CanOverlap) {
79       // Set alias scope for loads.
80       Load->setMetadata(LLVMContext::MD_alias_scope,
81                         MDNode::get(Ctx, NewScope));
82     }
83     Value *DstGEP =
84         LoopBuilder.CreateInBoundsGEP(LoopOpType, DstAddr, LoopIndex);
85     StoreInst *Store = LoopBuilder.CreateAlignedStore(
86         Load, DstGEP, PartDstAlign, DstIsVolatile);
87     if (!CanOverlap) {
88       // Indicate that stores don't overlap loads.
89       Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
90     }
91     if (AtomicElementSize) {
92       Load->setAtomic(AtomicOrdering::Unordered);
93       Store->setAtomic(AtomicOrdering::Unordered);
94     }
95     Value *NewIndex =
96         LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1U));
97     LoopIndex->addIncoming(NewIndex, LoopBB);
98 
99     // Create the loop branch condition.
100     Constant *LoopEndCI = ConstantInt::get(TypeOfCopyLen, LoopEndCount);
101     LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, LoopEndCI),
102                              LoopBB, PostLoopBB);
103   }
104 
105   uint64_t BytesCopied = LoopEndCount * LoopOpSize;
106   uint64_t RemainingBytes = CopyLen->getZExtValue() - BytesCopied;
107   if (RemainingBytes) {
108     IRBuilder<> RBuilder(PostLoopBB ? PostLoopBB->getFirstNonPHI()
109                                     : InsertBefore);
110 
111     SmallVector<Type *, 5> RemainingOps;
112     TTI.getMemcpyLoopResidualLoweringType(RemainingOps, Ctx, RemainingBytes,
113                                           SrcAS, DstAS, SrcAlign.value(),
114                                           DstAlign.value(), AtomicElementSize);
115 
116     for (auto *OpTy : RemainingOps) {
117       Align PartSrcAlign(commonAlignment(SrcAlign, BytesCopied));
118       Align PartDstAlign(commonAlignment(DstAlign, BytesCopied));
119 
120       // Calculate the new index
121       unsigned OperandSize = DL.getTypeStoreSize(OpTy);
122       assert(
123           (!AtomicElementSize || OperandSize % *AtomicElementSize == 0) &&
124           "Atomic memcpy lowering is not supported for selected operand size");
125 
126       uint64_t GepIndex = BytesCopied / OperandSize;
127       assert(GepIndex * OperandSize == BytesCopied &&
128              "Division should have no Remainder!");
129 
130       Value *SrcGEP = RBuilder.CreateInBoundsGEP(
131           OpTy, SrcAddr, ConstantInt::get(TypeOfCopyLen, GepIndex));
132       LoadInst *Load =
133           RBuilder.CreateAlignedLoad(OpTy, SrcGEP, PartSrcAlign, SrcIsVolatile);
134       if (!CanOverlap) {
135         // Set alias scope for loads.
136         Load->setMetadata(LLVMContext::MD_alias_scope,
137                           MDNode::get(Ctx, NewScope));
138       }
139       Value *DstGEP = RBuilder.CreateInBoundsGEP(
140           OpTy, DstAddr, ConstantInt::get(TypeOfCopyLen, GepIndex));
141       StoreInst *Store = RBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign,
142                                                      DstIsVolatile);
143       if (!CanOverlap) {
144         // Indicate that stores don't overlap loads.
145         Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
146       }
147       if (AtomicElementSize) {
148         Load->setAtomic(AtomicOrdering::Unordered);
149         Store->setAtomic(AtomicOrdering::Unordered);
150       }
151       BytesCopied += OperandSize;
152     }
153   }
154   assert(BytesCopied == CopyLen->getZExtValue() &&
155          "Bytes copied should match size in the call!");
156 }
157 
158 void llvm::createMemCpyLoopUnknownSize(
159     Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr, Value *CopyLen,
160     Align SrcAlign, Align DstAlign, bool SrcIsVolatile, bool DstIsVolatile,
161     bool CanOverlap, const TargetTransformInfo &TTI,
162     std::optional<uint32_t> AtomicElementSize) {
163   BasicBlock *PreLoopBB = InsertBefore->getParent();
164   BasicBlock *PostLoopBB =
165       PreLoopBB->splitBasicBlock(InsertBefore, "post-loop-memcpy-expansion");
166 
167   Function *ParentFunc = PreLoopBB->getParent();
168   const DataLayout &DL = ParentFunc->getParent()->getDataLayout();
169   LLVMContext &Ctx = PreLoopBB->getContext();
170   MDBuilder MDB(Ctx);
171   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("MemCopyDomain");
172   StringRef Name = "MemCopyAliasScope";
173   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
174 
175   unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
176   unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
177 
178   Type *LoopOpType = TTI.getMemcpyLoopLoweringType(
179       Ctx, CopyLen, SrcAS, DstAS, SrcAlign.value(), DstAlign.value(),
180       AtomicElementSize);
181   assert((!AtomicElementSize || !LoopOpType->isVectorTy()) &&
182          "Atomic memcpy lowering is not supported for vector operand type");
183   unsigned LoopOpSize = DL.getTypeStoreSize(LoopOpType);
184   assert((!AtomicElementSize || LoopOpSize % *AtomicElementSize == 0) &&
185          "Atomic memcpy lowering is not supported for selected operand size");
186 
187   IRBuilder<> PLBuilder(PreLoopBB->getTerminator());
188 
189   // Calculate the loop trip count, and remaining bytes to copy after the loop.
190   Type *CopyLenType = CopyLen->getType();
191   IntegerType *ILengthType = dyn_cast<IntegerType>(CopyLenType);
192   assert(ILengthType &&
193          "expected size argument to memcpy to be an integer type!");
194   Type *Int8Type = Type::getInt8Ty(Ctx);
195   bool LoopOpIsInt8 = LoopOpType == Int8Type;
196   ConstantInt *CILoopOpSize = ConstantInt::get(ILengthType, LoopOpSize);
197   Value *RuntimeLoopCount = LoopOpIsInt8 ?
198                             CopyLen :
199                             PLBuilder.CreateUDiv(CopyLen, CILoopOpSize);
200   BasicBlock *LoopBB =
201       BasicBlock::Create(Ctx, "loop-memcpy-expansion", ParentFunc, PostLoopBB);
202   IRBuilder<> LoopBuilder(LoopBB);
203 
204   Align PartSrcAlign(commonAlignment(SrcAlign, LoopOpSize));
205   Align PartDstAlign(commonAlignment(DstAlign, LoopOpSize));
206 
207   PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLenType, 2, "loop-index");
208   LoopIndex->addIncoming(ConstantInt::get(CopyLenType, 0U), PreLoopBB);
209 
210   Value *SrcGEP = LoopBuilder.CreateInBoundsGEP(LoopOpType, SrcAddr, LoopIndex);
211   LoadInst *Load = LoopBuilder.CreateAlignedLoad(LoopOpType, SrcGEP,
212                                                  PartSrcAlign, SrcIsVolatile);
213   if (!CanOverlap) {
214     // Set alias scope for loads.
215     Load->setMetadata(LLVMContext::MD_alias_scope, MDNode::get(Ctx, NewScope));
216   }
217   Value *DstGEP = LoopBuilder.CreateInBoundsGEP(LoopOpType, DstAddr, LoopIndex);
218   StoreInst *Store =
219       LoopBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign, DstIsVolatile);
220   if (!CanOverlap) {
221     // Indicate that stores don't overlap loads.
222     Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
223   }
224   if (AtomicElementSize) {
225     Load->setAtomic(AtomicOrdering::Unordered);
226     Store->setAtomic(AtomicOrdering::Unordered);
227   }
228   Value *NewIndex =
229       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLenType, 1U));
230   LoopIndex->addIncoming(NewIndex, LoopBB);
231 
232   bool requiresResidual =
233       !LoopOpIsInt8 && !(AtomicElementSize && LoopOpSize == AtomicElementSize);
234   if (requiresResidual) {
235     Type *ResLoopOpType = AtomicElementSize
236                               ? Type::getIntNTy(Ctx, *AtomicElementSize * 8)
237                               : Int8Type;
238     unsigned ResLoopOpSize = DL.getTypeStoreSize(ResLoopOpType);
239     assert((ResLoopOpSize == AtomicElementSize ? *AtomicElementSize : 1) &&
240            "Store size is expected to match type size");
241 
242     // Add in the
243     Value *RuntimeResidual = PLBuilder.CreateURem(CopyLen, CILoopOpSize);
244     Value *RuntimeBytesCopied = PLBuilder.CreateSub(CopyLen, RuntimeResidual);
245 
246     // Loop body for the residual copy.
247     BasicBlock *ResLoopBB = BasicBlock::Create(Ctx, "loop-memcpy-residual",
248                                                PreLoopBB->getParent(),
249                                                PostLoopBB);
250     // Residual loop header.
251     BasicBlock *ResHeaderBB = BasicBlock::Create(
252         Ctx, "loop-memcpy-residual-header", PreLoopBB->getParent(), nullptr);
253 
254     // Need to update the pre-loop basic block to branch to the correct place.
255     // branch to the main loop if the count is non-zero, branch to the residual
256     // loop if the copy size is smaller then 1 iteration of the main loop but
257     // non-zero and finally branch to after the residual loop if the memcpy
258     //  size is zero.
259     ConstantInt *Zero = ConstantInt::get(ILengthType, 0U);
260     PLBuilder.CreateCondBr(PLBuilder.CreateICmpNE(RuntimeLoopCount, Zero),
261                            LoopBB, ResHeaderBB);
262     PreLoopBB->getTerminator()->eraseFromParent();
263 
264     LoopBuilder.CreateCondBr(
265         LoopBuilder.CreateICmpULT(NewIndex, RuntimeLoopCount), LoopBB,
266         ResHeaderBB);
267 
268     // Determine if we need to branch to the residual loop or bypass it.
269     IRBuilder<> RHBuilder(ResHeaderBB);
270     RHBuilder.CreateCondBr(RHBuilder.CreateICmpNE(RuntimeResidual, Zero),
271                            ResLoopBB, PostLoopBB);
272 
273     // Copy the residual with single byte load/store loop.
274     IRBuilder<> ResBuilder(ResLoopBB);
275     PHINode *ResidualIndex =
276         ResBuilder.CreatePHI(CopyLenType, 2, "residual-loop-index");
277     ResidualIndex->addIncoming(Zero, ResHeaderBB);
278 
279     Value *FullOffset = ResBuilder.CreateAdd(RuntimeBytesCopied, ResidualIndex);
280     Value *SrcGEP =
281         ResBuilder.CreateInBoundsGEP(ResLoopOpType, SrcAddr, FullOffset);
282     LoadInst *Load = ResBuilder.CreateAlignedLoad(ResLoopOpType, SrcGEP,
283                                                   PartSrcAlign, SrcIsVolatile);
284     if (!CanOverlap) {
285       // Set alias scope for loads.
286       Load->setMetadata(LLVMContext::MD_alias_scope,
287                         MDNode::get(Ctx, NewScope));
288     }
289     Value *DstGEP =
290         ResBuilder.CreateInBoundsGEP(ResLoopOpType, DstAddr, FullOffset);
291     StoreInst *Store = ResBuilder.CreateAlignedStore(Load, DstGEP, PartDstAlign,
292                                                      DstIsVolatile);
293     if (!CanOverlap) {
294       // Indicate that stores don't overlap loads.
295       Store->setMetadata(LLVMContext::MD_noalias, MDNode::get(Ctx, NewScope));
296     }
297     if (AtomicElementSize) {
298       Load->setAtomic(AtomicOrdering::Unordered);
299       Store->setAtomic(AtomicOrdering::Unordered);
300     }
301     Value *ResNewIndex = ResBuilder.CreateAdd(
302         ResidualIndex, ConstantInt::get(CopyLenType, ResLoopOpSize));
303     ResidualIndex->addIncoming(ResNewIndex, ResLoopBB);
304 
305     // Create the loop branch condition.
306     ResBuilder.CreateCondBr(
307         ResBuilder.CreateICmpULT(ResNewIndex, RuntimeResidual), ResLoopBB,
308         PostLoopBB);
309   } else {
310     // In this case the loop operand type was a byte, and there is no need for a
311     // residual loop to copy the remaining memory after the main loop.
312     // We do however need to patch up the control flow by creating the
313     // terminators for the preloop block and the memcpy loop.
314     ConstantInt *Zero = ConstantInt::get(ILengthType, 0U);
315     PLBuilder.CreateCondBr(PLBuilder.CreateICmpNE(RuntimeLoopCount, Zero),
316                            LoopBB, PostLoopBB);
317     PreLoopBB->getTerminator()->eraseFromParent();
318     LoopBuilder.CreateCondBr(
319         LoopBuilder.CreateICmpULT(NewIndex, RuntimeLoopCount), LoopBB,
320         PostLoopBB);
321   }
322 }
323 
324 // Lower memmove to IR. memmove is required to correctly copy overlapping memory
325 // regions; therefore, it has to check the relative positions of the source and
326 // destination pointers and choose the copy direction accordingly.
327 //
328 // The code below is an IR rendition of this C function:
329 //
330 // void* memmove(void* dst, const void* src, size_t n) {
331 //   unsigned char* d = dst;
332 //   const unsigned char* s = src;
333 //   if (s < d) {
334 //     // copy backwards
335 //     while (n--) {
336 //       d[n] = s[n];
337 //     }
338 //   } else {
339 //     // copy forward
340 //     for (size_t i = 0; i < n; ++i) {
341 //       d[i] = s[i];
342 //     }
343 //   }
344 //   return dst;
345 // }
346 static void createMemMoveLoop(Instruction *InsertBefore, Value *SrcAddr,
347                               Value *DstAddr, Value *CopyLen, Align SrcAlign,
348                               Align DstAlign, bool SrcIsVolatile,
349                               bool DstIsVolatile,
350                               const TargetTransformInfo &TTI) {
351   Type *TypeOfCopyLen = CopyLen->getType();
352   BasicBlock *OrigBB = InsertBefore->getParent();
353   Function *F = OrigBB->getParent();
354   const DataLayout &DL = F->getParent()->getDataLayout();
355   // TODO: Use different element type if possible?
356   Type *EltTy = Type::getInt8Ty(F->getContext());
357 
358   // Create the a comparison of src and dst, based on which we jump to either
359   // the forward-copy part of the function (if src >= dst) or the backwards-copy
360   // part (if src < dst).
361   // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
362   // structure. Its block terminators (unconditional branches) are replaced by
363   // the appropriate conditional branches when the loop is built.
364   ICmpInst *PtrCompare = new ICmpInst(InsertBefore, ICmpInst::ICMP_ULT,
365                                       SrcAddr, DstAddr, "compare_src_dst");
366   Instruction *ThenTerm, *ElseTerm;
367   SplitBlockAndInsertIfThenElse(PtrCompare, InsertBefore, &ThenTerm,
368                                 &ElseTerm);
369 
370   // Each part of the function consists of two blocks:
371   //   copy_backwards:        used to skip the loop when n == 0
372   //   copy_backwards_loop:   the actual backwards loop BB
373   //   copy_forward:          used to skip the loop when n == 0
374   //   copy_forward_loop:     the actual forward loop BB
375   BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
376   CopyBackwardsBB->setName("copy_backwards");
377   BasicBlock *CopyForwardBB = ElseTerm->getParent();
378   CopyForwardBB->setName("copy_forward");
379   BasicBlock *ExitBB = InsertBefore->getParent();
380   ExitBB->setName("memmove_done");
381 
382   unsigned PartSize = DL.getTypeStoreSize(EltTy);
383   Align PartSrcAlign(commonAlignment(SrcAlign, PartSize));
384   Align PartDstAlign(commonAlignment(DstAlign, PartSize));
385 
386   // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
387   // between both backwards and forward copy clauses.
388   ICmpInst *CompareN =
389       new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
390                    ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
391 
392   // Copying backwards.
393   BasicBlock *LoopBB =
394     BasicBlock::Create(F->getContext(), "copy_backwards_loop", F, CopyForwardBB);
395   IRBuilder<> LoopBuilder(LoopBB);
396 
397   PHINode *LoopPhi = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
398   Value *IndexPtr = LoopBuilder.CreateSub(
399       LoopPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_ptr");
400   Value *Element = LoopBuilder.CreateAlignedLoad(
401       EltTy, LoopBuilder.CreateInBoundsGEP(EltTy, SrcAddr, IndexPtr),
402       PartSrcAlign, "element");
403   LoopBuilder.CreateAlignedStore(
404       Element, LoopBuilder.CreateInBoundsGEP(EltTy, DstAddr, IndexPtr),
405       PartDstAlign);
406   LoopBuilder.CreateCondBr(
407       LoopBuilder.CreateICmpEQ(IndexPtr, ConstantInt::get(TypeOfCopyLen, 0)),
408       ExitBB, LoopBB);
409   LoopPhi->addIncoming(IndexPtr, LoopBB);
410   LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
411   BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
412   ThenTerm->eraseFromParent();
413 
414   // Copying forward.
415   BasicBlock *FwdLoopBB =
416     BasicBlock::Create(F->getContext(), "copy_forward_loop", F, ExitBB);
417   IRBuilder<> FwdLoopBuilder(FwdLoopBB);
418   PHINode *FwdCopyPhi = FwdLoopBuilder.CreatePHI(TypeOfCopyLen, 0, "index_ptr");
419   Value *SrcGEP = FwdLoopBuilder.CreateInBoundsGEP(EltTy, SrcAddr, FwdCopyPhi);
420   Value *FwdElement =
421       FwdLoopBuilder.CreateAlignedLoad(EltTy, SrcGEP, PartSrcAlign, "element");
422   Value *DstGEP = FwdLoopBuilder.CreateInBoundsGEP(EltTy, DstAddr, FwdCopyPhi);
423   FwdLoopBuilder.CreateAlignedStore(FwdElement, DstGEP, PartDstAlign);
424   Value *FwdIndexPtr = FwdLoopBuilder.CreateAdd(
425       FwdCopyPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_increment");
426   FwdLoopBuilder.CreateCondBr(FwdLoopBuilder.CreateICmpEQ(FwdIndexPtr, CopyLen),
427                               ExitBB, FwdLoopBB);
428   FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
429   FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
430 
431   BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
432   ElseTerm->eraseFromParent();
433 }
434 
435 static void createMemSetLoop(Instruction *InsertBefore, Value *DstAddr,
436                              Value *CopyLen, Value *SetValue, Align DstAlign,
437                              bool IsVolatile) {
438   Type *TypeOfCopyLen = CopyLen->getType();
439   BasicBlock *OrigBB = InsertBefore->getParent();
440   Function *F = OrigBB->getParent();
441   const DataLayout &DL = F->getParent()->getDataLayout();
442   BasicBlock *NewBB =
443       OrigBB->splitBasicBlock(InsertBefore, "split");
444   BasicBlock *LoopBB
445     = BasicBlock::Create(F->getContext(), "loadstoreloop", F, NewBB);
446 
447   IRBuilder<> Builder(OrigBB->getTerminator());
448 
449   Builder.CreateCondBr(
450       Builder.CreateICmpEQ(ConstantInt::get(TypeOfCopyLen, 0), CopyLen), NewBB,
451       LoopBB);
452   OrigBB->getTerminator()->eraseFromParent();
453 
454   unsigned PartSize = DL.getTypeStoreSize(SetValue->getType());
455   Align PartAlign(commonAlignment(DstAlign, PartSize));
456 
457   IRBuilder<> LoopBuilder(LoopBB);
458   PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
459   LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
460 
461   LoopBuilder.CreateAlignedStore(
462       SetValue,
463       LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
464       PartAlign, IsVolatile);
465 
466   Value *NewIndex =
467       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
468   LoopIndex->addIncoming(NewIndex, LoopBB);
469 
470   LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
471                            NewBB);
472 }
473 
474 template <typename T>
475 static bool canOverlap(MemTransferBase<T> *Memcpy, ScalarEvolution *SE) {
476   if (SE) {
477     auto *SrcSCEV = SE->getSCEV(Memcpy->getRawSource());
478     auto *DestSCEV = SE->getSCEV(Memcpy->getRawDest());
479     if (SE->isKnownPredicateAt(CmpInst::ICMP_NE, SrcSCEV, DestSCEV, Memcpy))
480       return false;
481   }
482   return true;
483 }
484 
485 void llvm::expandMemCpyAsLoop(MemCpyInst *Memcpy,
486                               const TargetTransformInfo &TTI,
487                               ScalarEvolution *SE) {
488   bool CanOverlap = canOverlap(Memcpy, SE);
489   if (ConstantInt *CI = dyn_cast<ConstantInt>(Memcpy->getLength())) {
490     createMemCpyLoopKnownSize(
491         /* InsertBefore */ Memcpy,
492         /* SrcAddr */ Memcpy->getRawSource(),
493         /* DstAddr */ Memcpy->getRawDest(),
494         /* CopyLen */ CI,
495         /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(),
496         /* DestAlign */ Memcpy->getDestAlign().valueOrOne(),
497         /* SrcIsVolatile */ Memcpy->isVolatile(),
498         /* DstIsVolatile */ Memcpy->isVolatile(),
499         /* CanOverlap */ CanOverlap,
500         /* TargetTransformInfo */ TTI);
501   } else {
502     createMemCpyLoopUnknownSize(
503         /* InsertBefore */ Memcpy,
504         /* SrcAddr */ Memcpy->getRawSource(),
505         /* DstAddr */ Memcpy->getRawDest(),
506         /* CopyLen */ Memcpy->getLength(),
507         /* SrcAlign */ Memcpy->getSourceAlign().valueOrOne(),
508         /* DestAlign */ Memcpy->getDestAlign().valueOrOne(),
509         /* SrcIsVolatile */ Memcpy->isVolatile(),
510         /* DstIsVolatile */ Memcpy->isVolatile(),
511         /* CanOverlap */ CanOverlap,
512         /* TargetTransformInfo */ TTI);
513   }
514 }
515 
516 bool llvm::expandMemMoveAsLoop(MemMoveInst *Memmove,
517                                const TargetTransformInfo &TTI) {
518   Value *CopyLen = Memmove->getLength();
519   Value *SrcAddr = Memmove->getRawSource();
520   Value *DstAddr = Memmove->getRawDest();
521   Align SrcAlign = Memmove->getSourceAlign().valueOrOne();
522   Align DstAlign = Memmove->getDestAlign().valueOrOne();
523   bool SrcIsVolatile = Memmove->isVolatile();
524   bool DstIsVolatile = SrcIsVolatile;
525   IRBuilder<> CastBuilder(Memmove);
526 
527   unsigned SrcAS = SrcAddr->getType()->getPointerAddressSpace();
528   unsigned DstAS = DstAddr->getType()->getPointerAddressSpace();
529   if (SrcAS != DstAS) {
530     if (!TTI.addrspacesMayAlias(SrcAS, DstAS)) {
531       // We may not be able to emit a pointer comparison, but we don't have
532       // to. Expand as memcpy.
533       if (ConstantInt *CI = dyn_cast<ConstantInt>(CopyLen)) {
534         createMemCpyLoopKnownSize(/*InsertBefore=*/Memmove, SrcAddr, DstAddr,
535                                   CI, SrcAlign, DstAlign, SrcIsVolatile,
536                                   DstIsVolatile,
537                                   /*CanOverlap=*/false, TTI);
538       } else {
539         createMemCpyLoopUnknownSize(/*InsertBefore=*/Memmove, SrcAddr, DstAddr,
540                                     CopyLen, SrcAlign, DstAlign, SrcIsVolatile,
541                                     DstIsVolatile,
542                                     /*CanOverlap=*/false, TTI);
543       }
544 
545       return true;
546     }
547 
548     if (TTI.isValidAddrSpaceCast(DstAS, SrcAS))
549       DstAddr = CastBuilder.CreateAddrSpaceCast(DstAddr, SrcAddr->getType());
550     else if (TTI.isValidAddrSpaceCast(SrcAS, DstAS))
551       SrcAddr = CastBuilder.CreateAddrSpaceCast(SrcAddr, DstAddr->getType());
552     else {
553       // We don't know generically if it's legal to introduce an
554       // addrspacecast. We need to know either if it's legal to insert an
555       // addrspacecast, or if the address spaces cannot alias.
556       LLVM_DEBUG(
557           dbgs() << "Do not know how to expand memmove between different "
558                     "address spaces\n");
559       return false;
560     }
561   }
562 
563   createMemMoveLoop(
564       /*InsertBefore=*/Memmove, SrcAddr, DstAddr, CopyLen, SrcAlign, DstAlign,
565       SrcIsVolatile, DstIsVolatile, TTI);
566   return true;
567 }
568 
569 void llvm::expandMemSetAsLoop(MemSetInst *Memset) {
570   createMemSetLoop(/* InsertBefore */ Memset,
571                    /* DstAddr */ Memset->getRawDest(),
572                    /* CopyLen */ Memset->getLength(),
573                    /* SetValue */ Memset->getValue(),
574                    /* Alignment */ Memset->getDestAlign().valueOrOne(),
575                    Memset->isVolatile());
576 }
577 
578 void llvm::expandAtomicMemCpyAsLoop(AtomicMemCpyInst *AtomicMemcpy,
579                                     const TargetTransformInfo &TTI,
580                                     ScalarEvolution *SE) {
581   if (ConstantInt *CI = dyn_cast<ConstantInt>(AtomicMemcpy->getLength())) {
582     createMemCpyLoopKnownSize(
583         /* InsertBefore */ AtomicMemcpy,
584         /* SrcAddr */ AtomicMemcpy->getRawSource(),
585         /* DstAddr */ AtomicMemcpy->getRawDest(),
586         /* CopyLen */ CI,
587         /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(),
588         /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(),
589         /* SrcIsVolatile */ AtomicMemcpy->isVolatile(),
590         /* DstIsVolatile */ AtomicMemcpy->isVolatile(),
591         /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec.
592         /* TargetTransformInfo */ TTI,
593         /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes());
594   } else {
595     createMemCpyLoopUnknownSize(
596         /* InsertBefore */ AtomicMemcpy,
597         /* SrcAddr */ AtomicMemcpy->getRawSource(),
598         /* DstAddr */ AtomicMemcpy->getRawDest(),
599         /* CopyLen */ AtomicMemcpy->getLength(),
600         /* SrcAlign */ AtomicMemcpy->getSourceAlign().valueOrOne(),
601         /* DestAlign */ AtomicMemcpy->getDestAlign().valueOrOne(),
602         /* SrcIsVolatile */ AtomicMemcpy->isVolatile(),
603         /* DstIsVolatile */ AtomicMemcpy->isVolatile(),
604         /* CanOverlap */ false, // SrcAddr & DstAddr may not overlap by spec.
605         /* TargetTransformInfo */ TTI,
606         /* AtomicCpySize */ AtomicMemcpy->getElementSizeInBytes());
607   }
608 }
609