[loop idiom Recognition] support memcpy for multiple consecutive loads and stores

[DIVYA]

Summary

This pass converts multiple consecutive loads and stores inside a loop to memcpy operation.
For example, the stores and loads in the below code can be converted to a memcpy .

struct foo
{

int a;
int b;

} f,g;

for(int i=0;i<n;i++)
{

f[i].a  =  g[i].a;
f[i].b  =  g[i].b;

}

Worked in collaboration with Sebastian Pop and Aditya Kumar.

[mgrang]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

161 ↗

(On Diff #104483)

Extra newline.

371 ↗

(On Diff #104483)

Extra newline.

458 ↗

(On Diff #104483)

Ditto.

497 ↗

(On Diff #104483)

Ditto.

919 ↗

(On Diff #104483)

Use i != e instead of i < e.

951 ↗

(On Diff #104483)

This loop looks a bit hacky. Can this be re-written in a better way?

954 ↗

(On Diff #104483)

Check indentation.

1204 ↗

(On Diff #104483)

Newline removed.

1607 ↗

(On Diff #104483)

Newline removed.

test/Transforms/LoopIdiom/memcpy_structPattern.ll

12 ↗

(On Diff #104483)

Can the test case be simplified/minimized by removing unwanted/extra attributes?

[mgrang]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

901 ↗

(On Diff #104483)

Extra / in comments. Also check comment spacing.

test/Transforms/LoopIdiom/memcpy_structPattern.ll

1 ↗

(On Diff #104483)

Unit test names follow all lowercase naming convention: memcpy_struct_pattern.ll

[DIVYA]

• Removed Extra Newlines
• Added IndexQueue(SmallVector) for storing possible consecutive stores
• changed testcase filename

[haicheng]

Please check the inlined comment.

Is it possible to reuse the code of processLoopStores() and processLoopStridedStore()?

Haicheng

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

527 ↗

(On Diff #105328)

I think this comment should be changed.

900 ↗

(On Diff #105328)

I think we need to emphasize that loads and stores are consecutive.

930 ↗

(On Diff #105328)

What if FirstStoreLoad is nullptr?

968 ↗

(On Diff #105328)

Same thing here.

1070 ↗

(On Diff #105328)

Please check the format.

1077 ↗

(On Diff #105328)

memset?

1105 ↗

(On Diff #105328)

memset?

[DIVYA]

• Updated some comments

[haicheng]

Just a few more comments. Please use clang format on your code.

Haicheng

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

984 ↗

(On Diff #105428)

I think you can remove this one or change it to an assert.

At this point, I think we know the stores have the same strides and loads have the same strides as their users (stores), so the strides of the loads should be the same.

1151 ↗

(On Diff #105428)

What if some Loads/Stores are atomic and some are not?

[DIVYA]

• If there are multiple stores and loads ,which are consecutive, but if any of them is atomic , then it won't be converted to memcpy.
• isAtomicStoreLoad flag checks for any atomic store or load, when there are multiple stores and loads .
• If there is single store and load , then it will converted to memcpy or atomic memcpy depending on whether the store and load are atomic or not.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

981 ↗

(On Diff #105544)

Can we just return from here?

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

968 ↗

(On Diff #105328)

This will be checked in the isLegalStore() function itself.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

930 ↗

(On Diff #105328)

Then you can use cast instead of dyn_cast

[DIVYA]

• Changed dyn_cast to cast

[DIVYA]

ping

[haicheng]

I think you can refactor your code to reuse most of the implementation of processLoopStores() and processLoopStridedStore(). Maybe just add a flag to do the extra work for the loads.

[DIVYA]

• Refactored code to reuse implementation of processLoopStores() and processLoopStridedStore()
• Added ForMemcpy flag

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

134 ↗

(On Diff #110415)

I think you can pass in an enum which has value ForMemset, ForMemsetPattern, ForMemcpy like LegalStoreKind above or just use LegalStoreKind if possible.

651–675 ↗

(On Diff #110415)

I think code here can refactor with code above

737 ↗

(On Diff #110415)

I think processLoopStoreOfLoopLoad() can refactor with processLoopStridedStore(), then you don't need if...else... here.

[DIVYA]

• Used enum for ForMemcpy
• Refactored some code

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

737 ↗

(On Diff #110415)

processLoopStoreOfLoopLoad() function was already present,so I haven't refactored it with processLoopStridedStore() in this patch.I can do that in the next patch

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

646 ↗

(On Diff #110461)

Please add a comment to make it clear it is for memcpy.

or add if (memcpy)

or write this part as a switch.

669–674 ↗

(On Diff #110461)

clang-format here

737 ↗

(On Diff #110415)

I think you can go ahead.

[DIVYA]

• modified comment

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

737 ↗

(On Diff #110415)

So should I do it in this patch or next one?

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

737 ↗

(On Diff #110415)

I think in this patch.

[DIVYA]

• processLoopStoreOfLoopLoad() refactored with processLoopStridedStore(),

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

830 ↗

(On Diff #111030)

a space between stride and comma.

847–857 ↗

(On Diff #111030)

This part can be written as

if (Memset)
  SplatValue = 
else if (memsetpattern)
  Patternvalue =

966 ↗

(On Diff #111030)

This can be changed to

if (memset)

969 ↗

(On Diff #111030)

this can be changed to

else if (memset_pattern)

1022–1029 ↗

(On Diff #111030)

I think after creating newCall, setDebugLoc and debug dumping can be refactored too.

[DIVYA]

• setDebugLoc and debug dumping refactored

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

143 ↗

(On Diff #111184)

I think we should use MemIdiom and IsLoopMemset can be removed.

[DIVYA]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

143 ↗

(On Diff #111184)

But when processLoopStridedStore() is called from processLoopMemSet() function , then IsLoopMemset is set true and when it is called from processLoopStores() function , then IsLoopMemset is set false.Even though both can have MemIdiom set to LegalStoreKind::Memset .So using MemIdiom alone would not be sufficient.As, we need IsLoopMemset to indicate if memset which can be promoted to a large memset.

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

143 ↗

(On Diff #111184)

Yes, you are right. I think we can move the check avoidLIRForMultiBlockLoop() much earlier so that we don't need this flag and we can save compilation time. But, we can do that in the next patch.

965–968 ↗

(On Diff #111184)

I think here can be written as

if (Memset)
else if (MemsetPattern)
else (Memcpy)

not nested if

[DIVYA]

• Removed nested if

[haicheng]

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

577 ↗

(On Diff #111356)

SL[i]->getValueOperand() => FirstStoredVal

644 ↗

(On Diff #111356)

SL[k]->getValueOperand() => SecondStoredVal

943 ↗

(On Diff #111356)

not only memset here

[DIVYA]

• modified comment

[haicheng]

LGTM

Thanks for working on that. Please fully check the correctness before committing the patch.

[DIVYA]

lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::SimplifyMemTransfer(MemIntrinsic *MI) {
   unsigned MinAlign = std::min(DstAlign, SrcAlign);
   unsigned CopyAlign = MI->getAlignment();
 
   if (CopyAlign < MinAlign) {
     MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), MinAlign, false));
     return MI;
   }
 
-  // If MemCpyInst length is 1/2/4/8 bytes then replace memcpy with
-  // load/store.
   ConstantInt *MemOpLength = dyn_cast<ConstantInt>(MI->getArgOperand(2));
   if (!MemOpLength) return nullptr;
 
   // Source and destination pointer types are always "i8*" for intrinsic.  See
   // if the size is something we can handle with a single primitive load/store.
   // A single load+store correctly handles overlapping memory in the memmove
   // case.
   uint64_t Size = MemOpLength->getLimitedValue();
   assert(Size && "0-sized memory transferring should be removed already.");
 
-  if (Size > 8 || (Size&(Size-1)))
-    return nullptr;  // If not 1/2/4/8 bytes, exit.
+
+  // Since we don't have perfect knowledge here, make some assumptions: assume
+  // the maximum allowed stores for memcpy operation is the same size as the 
+  // largest legal integer size. 
+  unsigned LargestInt = DL.getLargestLegalIntTypeSizeInBits();
+  if (LargestInt == 0)
+    LargestInt = 32;
+
+  if (Size > LargestInt/8 || (Size&(Size-1)))
+    return nullptr;  
 
   // Use an integer load+store unless we can find something better.
   unsigned SrcAddrSp =
     cast<PointerType>(MI->getArgOperand(1)->getType())->getAddressSpace();
   unsigned DstAddrSp =
     cast<PointerType>(MI->getArgOperand(0)->getType())->getAddressSpace();
 
   IntegerType* IntType = IntegerType::get(MI->getContext(), Size<<3);

test/DebugInfo/X86/array2.ll

 ;   f(array);
 ;   return array[0];
 ; }
 ;
 ; RUN: opt %s -O2 -S -o - | FileCheck %s
 ; Test that we correctly lower dbg.declares for arrays.
 ;
 ; CHECK: define i32 @main
-; CHECK: call void @llvm.dbg.value(metadata i32 42, i64 0, metadata ![[ARRAY:[0-9]+]], metadata ![[EXPR:[0-9]+]])
-; CHECK: ![[ARRAY]] = !DILocalVariable(name: "array",{{.*}} line: 6
-; CHECK: ![[EXPR]] = !DIExpression(DW_OP_LLVM_fragment, 0, 32)
+; CHECK: tail call void @llvm.dbg.value(metadata i32 [[ARGC:%.*]], i64 0, metadata !22, metadata !12), !dbg !23
+; CHECK: tail call void @llvm.dbg.value(metadata i8** [[ARGV:%.*]], i64 0, metadata !24, metadata !12), !dbg !23
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.9.0"
 
 @main.array = private unnamed_addr constant [4 x i32] [i32 0, i32 1, i32 2, i32 3], align 16
 
 ; Function Attrs: nounwind ssp uwtable
 define void @f(i32* %p) #0 !dbg !4 {
 entry:

test/Transforms/InstCombine/alloca.ll

 declare i8* @llvm.stacksave()
 declare void @llvm.stackrestore(i8*)
 
 define void @test9(%struct_type* %a) {
 ; CHECK-LABEL: @test9(
 entry:
   %inalloca.save = call i8* @llvm.stacksave()
   %argmem = alloca inalloca <{ %struct_type }>
-; CHECK: alloca inalloca i64, align 8
   %0 = getelementptr inbounds <{ %struct_type }>, <{ %struct_type }>* %argmem, i32 0, i32 0
   %1 = bitcast %struct_type* %0 to i8*
   %2 = bitcast %struct_type* %a to i8*
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %1, i8* %2, i32 8, i32 4, i1 false)
   call void @test9_aux(<{ %struct_type }>* inalloca %argmem)
   call void @llvm.stackrestore(i8* %inalloca.save)
   ret void
 }

test/Transforms/InstCombine/memcpy-to-load.ll

 ; ALL-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 5, i32 1, i1 false)
 ; ALL-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %d, i8* %s, i32 5, i32 1, i1 false)
   ret void
 }
 
 define void @copy_8_bytes(i8* %d, i8* %s) {
-; ALL-LABEL: @copy_8_bytes(
-; ALL-NEXT:    [[TMP1:%.*]] = bitcast i8* [[S:%.*]] to i64*
-; ALL-NEXT:    [[TMP2:%.*]] = bitcast i8* [[D:%.*]] to i64*
-; ALL-NEXT:    [[TMP3:%.*]] = load i64, i64* [[TMP1]], align 1
-; ALL-NEXT:    store i64 [[TMP3]], i64* [[TMP2]], align 1
-; ALL-NEXT:    ret void
+; If there is no datalayout, then all memcpy of size less than 16 bytes (and power-of-2) will be expanded inline with load/store
+; NODL-LABEL: @copy_8_bytes(
+; NODL-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 8, i32 1, i1 false)
+; NODL-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 4 bytes, all memcpy with size less than 8 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I32-LABEL: @copy_8_bytes(
+; I32-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 8, i32 1, i1 false)
+; I32-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 8 bytes, all memcpy with size less than 16 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I64-LABEL: @copy_8_bytes(
+; I64-NEXT:    [[TMP1:%.*]] = bitcast i8* [[S:%.*]] to i64*
+; I64-NEXT:    [[TMP2:%.*]] = bitcast i8* [[D:%.*]] to i64*
+; I64-NEXT:    [[TMP3:%.*]] = load i64, i64* [[TMP1]], align 1
+; I64-NEXT:    store i64 [[TMP3]], i64* [[TMP2]], align 1
+; I64-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 16 bytes, all memcpy with size less than 32 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I128-LABEL: @copy_8_bytes(
+; I128-NEXT:    [[TMP1:%.*]] = bitcast i8* [[S:%.*]] to i64*
+; I128-NEXT:    [[TMP2:%.*]] = bitcast i8* [[D:%.*]] to i64*
+; I128-NEXT:    [[TMP3:%.*]] = load i64, i64* [[TMP1]], align 1
+; I128-NEXT:    store i64 [[TMP3]], i64* [[TMP2]], align 1
+; I128-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %d, i8* %s, i32 8, i32 1, i1 false)
   ret void
 }
 
 define void @copy_16_bytes(i8* %d, i8* %s) {
-; ALL-LABEL: @copy_16_bytes(
-; ALL-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 16, i32 1, i1 false)
-; ALL-NEXT:    ret void
+; If there is no datalayout, then all memcpy of size less than 16 bytes (and power-of-2) will be expanded inline with load/store
+; NODL-LABEL: @copy_16_bytes(
+; NODL-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 16, i32 1, i1 false)
+; NODL-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 4 bytes, all memcpy with size less than 8 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I32-LABEL: @copy_16_bytes(
+; I32-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 16, i32 1, i1 false)
+; I32-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 8 bytes, all memcpy with size less than 16 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I64-LABEL: @copy_16_bytes(
+; I64-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[D:%.*]], i8* [[S:%.*]], i32 16, i32 1, i1 false)
+; I64-NEXT:    ret void
+;
+; For datalayout with largest legal integer type size of 16 bytes, all memcpy with size less than 32 bytes (and power-of-2) will be expanded inline with load/store
+;
+; I128-LABEL: @copy_16_bytes(
+; I128-NEXT:    [[TMP1:%.*]] = bitcast i8* [[S:%.*]] to i128*
+; I128-NEXT:    [[TMP2:%.*]] = bitcast i8* [[D:%.*]] to i128*
+; I128-NEXT:    [[TMP3:%.*]] = load i128, i128* [[TMP1]], align 1
+; I128-NEXT:    store i128 [[TMP3]], i128* [[TMP2]], align 1
+; I128-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %d, i8* %s, i32 16, i32 1, i1 false)
   ret void
 }