Cost calculation for interleave load/store patterns {v8i8,v16i8,v32i8,v64i8}

[m_zuckerman]

Summary

This patch adds accurate instructions cost. The formula presents two cases(stride 3 and stride 4) and calculates the cost according to the VF and stride.

[delena]

lib/Target/X86/X86TargetTransformInfo.cpp

2552 ↗

(On Diff #118468)

returns true

2557 ↗

(On Diff #118468)

Why "optimize"? It is just calculation.

2574 ↗

(On Diff #118468)

I don't like hard-coded numbers inside functions. I suggest to use lookup tables with types.

[dorit]

My only main concerns are with respect to interleave-group with gaps (see below), and the fact that we don't distinguish the AVX2 from the AVX512 case (also see below). Just minor comments beyond that.

lib/Target/X86/X86TargetTransformInfo.cpp

2556 ↗

(On Diff #118468)

Can use \p when you refer to the function arguments.

Some phrasing suggestions:
"the Interleaved pass" --> the X86InterleavedAccess pass
"supports the interleaved" --> supports the specific interleaved access group at hand.
"If the interleaved is supported by the pass..." --> If it does, the function computes the cost of the optimized load/store+shuffle sequence that the X86InterleavedAccess pass will generate for this interleaved-access group.

2562 ↗

(On Diff #118468)

v64i8 is not a legal type for AVX2... will you be getting the right cost here for AVX2?

2563 ↗

(On Diff #118468)

Maybe add a comment here "Currently the X86InterleavedAccess pass supports only char accesses,"

2570 ↗

(On Diff #118468)

Would be nice if you could add some intuition to the numbers below...

2612 ↗

(On Diff #118468)

What if the interleave-group has gaps? does the X86InterleavedAccess pass still support it? (I think not, right?). In that case you want to move the call to the cost function to after this check.

2729 ↗

(On Diff #118468)

Why did you place the call to optimizeInterleaveCost specifically here, if it's not using the MemOpCost calculation?

2766 ↗

(On Diff #118468)

is this the right indentation? (same for the occurrence below)

[m_zuckerman]

lib/Target/X86/X86TargetTransformInfo.cpp

2562 ↗

(On Diff #118468)

according to what I saw in the code, only legal types pass into this section and therefore you don't need to care for that.

[dorit]

The AVX2 changes look ok to me now.
A couple comments about the AVX512 changes below.

lib/Target/X86/X86TargetTransformInfo.cpp

2660 ↗

(On Diff #119132)

I think the common practice here is to place such cost tables inside the function, exactly where it is used.

Also, does the cost in these two tables include the load/store instructions, or does it account only for the shuffles?
It looks like you don't add the MemOpCost to the cost that the table returns, so probably the load/store cost is already accounted for; is that intentional?
(If so, the semantics of this table is a bit different than that of the AVX2 counterpart above (see the description of the AVX2 tables above), so this should be documented. For example, the comments in the table should not have the "load" and "store" in parenthesis... ).

2708 ↗

(On Diff #119132)

Please add a comment here saying that if the X86InterleaveAccessPass supports the specific interleaved access group at hand, we return the hard coded cost of the shuffle sequence that the X86InterleaveAccessPass will generate. Otherwise we compute the cost of the (unoptimized) shuffle sequence (that would be a result of lowering each of the IR shuffles of the interleaved group independently).

[m_zuckerman]

lib/Target/X86/X86TargetTransformInfo.cpp

2660 ↗

(On Diff #119132)

In the mine computation, I check all the instructions include load and store. For the value of the table to be consistent with either avx2 code or avx512 I had to adapt the computation to the user code.

[dorit]

AVX512 side of things now also looks good to me (with the tiny comments below).

lib/Target/X86/X86TargetTransformInfo.cpp

2692 ↗

(On Diff #119277)

you can fit in more text in this line; and while you're touching this, maybe clarify this comment saying that the cost in the table accounts only for the shuffle sequence (the loads/stores are accounted for separately);

2765 ↗

(On Diff #119277)

"If entry" --> "[ ]If [an] entry"
(in both occurrences of this comment).

[dorit]

LGTM with the last couple of comments.

llvm/trunk/lib/Target/X86/X86TargetTransformInfo.cpp

int X86TTIImpl::getInterleavedMemoryOpCostAVX2(unsigned Opcode, Type *VecTy,
   // Factor (stride) and VectorType=VFxElemType.
   // The Cost accounts only for the shuffle sequence;
   // The cost of the loads/stores is accounted for separately.
   //
   static const CostTblEntry AVX2InterleavedLoadTbl[] = {
     { 3, MVT::v2i8,  10 }, //(load 6i8 and)  deinterleave into 3 x 2i8
     { 3, MVT::v4i8,  4 },  //(load 12i8 and) deinterleave into 3 x 4i8
     { 3, MVT::v8i8,  9 },  //(load 24i8 and) deinterleave into 3 x 8i8
-    { 3, MVT::v16i8, 18},  //(load 48i8 and) deinterleave into 3 x 16i8
-    { 3, MVT::v32i8, 42 }, //(load 96i8 and) deinterleave into 3 x 32i8
+    { 3, MVT::v16i8, 11},  //(load 48i8 and) deinterleave into 3 x 16i8
+    { 3, MVT::v32i8, 13},  //(load 96i8 and) deinterleave into 3 x 32i8
 
     { 4, MVT::v2i8,  12 }, //(load 8i8 and)   deinterleave into 4 x 2i8
     { 4, MVT::v4i8,  4 },  //(load 16i8 and)  deinterleave into 4 x 4i8
     { 4, MVT::v8i8,  20 }, //(load 32i8 and)  deinterleave into 4 x 8i8
     { 4, MVT::v16i8, 39 }, //(load 64i8 and)  deinterleave into 4 x 16i8
     { 4, MVT::v32i8, 80 }  //(load 128i8 and) deinterleave into 4 x 32i8
   };
 
   static const CostTblEntry AVX2InterleavedStoreTbl[] = {
     { 3, MVT::v2i8,  7 },  //interleave 3 x 2i8  into 6i8 (and store)
     { 3, MVT::v4i8,  8 },  //interleave 3 x 4i8  into 12i8 (and store)
     { 3, MVT::v8i8,  11 }, //interleave 3 x 8i8  into 24i8 (and store)
-    { 3, MVT::v16i8, 17 }, //interleave 3 x 16i8 into 48i8 (and store)
-    { 3, MVT::v32i8, 32 }, //interleave 3 x 32i8 into 96i8 (and store)
+    { 3, MVT::v16i8, 11 }, //interleave 3 x 16i8 into 48i8 (and store)
+    { 3, MVT::v32i8, 13 }, //interleave 3 x 32i8 into 96i8 (and store)
 
     { 4, MVT::v2i8,  12 }, //interleave 4 x 2i8  into 8i8 (and store)
     { 4, MVT::v4i8,  9 },  //interleave 4 x 4i8  into 16i8 (and store)
-    { 4, MVT::v8i8,  16 }, //interleave 4 x 8i8  into 32i8 (and store)
-    { 4, MVT::v16i8, 20 }, //interleave 4 x 16i8 into 64i8 (and store)
-    { 4, MVT::v32i8, 40 }  //interleave 4 x 32i8 into 128i8 (and store)
+    { 4, MVT::v8i8,  10 }, //interleave 4 x 8i8  into 32i8 (and store)
+    { 4, MVT::v16i8, 10 }, //interleave 4 x 16i8 into 64i8 (and store)
+    { 4, MVT::v32i8, 12 }  //interleave 4 x 32i8 into 128i8 (and store)
   };
 
   if (Opcode == Instruction::Load) {
     if (const auto *Entry =
             CostTableLookup(AVX2InterleavedLoadTbl, Factor, ETy.getSimpleVT()))
       return NumOfMemOps * MemOpCost + Entry->Cost;
   } else {
     assert(Opcode == Instruction::Store &&
int X86TTIImpl::getInterleavedMemoryOpCostAVX512(unsigned Opcode, Type *VecTy,
   unsigned NumOfMemOps = (VecTySize + LegalVTSize - 1) / LegalVTSize;
 
   // Get the cost of one memory operation.
   Type *SingleMemOpTy = VectorType::get(VecTy->getVectorElementType(),
                                         LegalVT.getVectorNumElements());
   unsigned MemOpCost =
       getMemoryOpCost(Opcode, SingleMemOpTy, Alignment, AddressSpace);
 
+  unsigned VF = VecTy->getVectorNumElements() / Factor;
+  MVT VT = MVT::getVectorVT(MVT::getVT(VecTy->getScalarType()), VF);
+
   if (Opcode == Instruction::Load) {
+    // The tables (AVX512InterleavedLoadTbl and AVX512InterleavedStoreTbl)
+    // contain the cost of the optimized shuffle sequence that the
+    // X86InterleavedAccess pass will generate.
+    // The cost of loads and stores are computed separately from the table.
+
+    // X86InterleavedAccess support only the following interleaved-access group.
+    static const CostTblEntry AVX512InterleavedLoadTbl[] = {
+        {3, MVT::v16i8, 12}, //(load 48i8 and) deinterleave into 3 x 16i8
+        {3, MVT::v32i8, 14}, //(load 96i8 and) deinterleave into 3 x 32i8
+        {3, MVT::v64i8, 22}, //(load 96i8 and) deinterleave into 3 x 32i8
+    };
+
+    if (const auto *Entry =
+            CostTableLookup(AVX512InterleavedLoadTbl, Factor, VT))
+      return NumOfMemOps * MemOpCost + Entry->Cost;
+    //If an entry does not exist, fallback to the default implementation.
+
     // Kind of shuffle depends on number of loaded values.
     // If we load the entire data in one register, we can use a 1-src shuffle.
     // Otherwise, we'll merge 2 sources in each operation.
     TTI::ShuffleKind ShuffleKind =
         (NumOfMemOps > 1) ? TTI::SK_PermuteTwoSrc : TTI::SK_PermuteSingleSrc;
 
     unsigned ShuffleCost =
         getShuffleCost(ShuffleKind, SingleMemOpTy, 0, nullptr);
int Cost = NumOfResults * NumOfShufflesPerResult * ShuffleCost +
                NumOfUnfoldedLoads * MemOpCost + NumOfMoves;
 
     return Cost;
   }
 
   // Store.
   assert(Opcode == Instruction::Store &&
          "Expected Store Instruction at this  point");
+  // X86InterleavedAccess support only the following interleaved-access group.
+  static const CostTblEntry AVX512InterleavedStoreTbl[] = {
+      {3, MVT::v16i8, 12}, // interleave 3 x 16i8 into 48i8 (and store)
+      {3, MVT::v32i8, 14}, // interleave 3 x 32i8 into 96i8 (and store)
+      {3, MVT::v64i8, 26}, // interleave 3 x 64i8 into 96i8 (and store)
+
+      {4, MVT::v8i8, 10},  // interleave 4 x 8i8  into 32i8  (and store)
+      {4, MVT::v16i8, 11}, // interleave 4 x 16i8 into 64i8  (and store)
+      {4, MVT::v32i8, 14}, // interleave 4 x 32i8 into 128i8 (and store)
+      {4, MVT::v64i8, 24}  // interleave 4 x 32i8 into 256i8 (and store)
+  };
+
+  if (const auto *Entry =
+          CostTableLookup(AVX512InterleavedStoreTbl, Factor, VT))
+    return NumOfMemOps * MemOpCost + Entry->Cost;
+  //If an entry does not exist, fallback to the default implementation.
 
   // There is no strided stores meanwhile. And store can't be folded in
   // shuffle.
   unsigned NumOfSources = Factor; // The number of values to be merged.
   unsigned ShuffleCost =
       getShuffleCost(TTI::SK_PermuteTwoSrc, SingleMemOpTy, 0, nullptr);
   unsigned NumOfShufflesPerStore = NumOfSources - 1;
 

llvm/trunk/test/Analysis/CostModel/X86/interleaved-load-i8.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-vectorize -S -mcpu=core-avx2 --debug-only=loop-vectorize -vectorizer-maximize-bandwidth < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: norecurse nounwind readonly uwtable
 define i32 @doit_stride3(i8* nocapture readonly %Ptr, i32 %Nels)  {
 ;CHECK: LV: Found an estimated cost of 1 for VF 1 For instruction:   %0 = load i8
 ;CHECK: LV: Found an estimated cost of 11 for VF 2 For instruction:   %0 = load i8
 ;CHECK: LV: Found an estimated cost of 5 for VF 4 For instruction:   %0 = load i8
 ;CHECK: LV: Found an estimated cost of 10 for VF 8 For instruction:   %0 = load i8
-;CHECK: LV: Found an estimated cost of 20 for VF 16 For instruction:   %0 = load i8
-;CHECK: LV: Found an estimated cost of 45 for VF 32 For instruction:   %0 = load i8
+;CHECK: LV: Found an estimated cost of 13 for VF 16 For instruction:   %0 = load i8
+;CHECK: LV: Found an estimated cost of 16 for VF 32 For instruction:   %0 = load i8
 entry:
   %cmp13 = icmp sgt i32 %Nels, 0
   br i1 %cmp13, label %for.body.preheader, label %for.end
 
 for.body.preheader:
   br label %for.body
 
 for.body:

llvm/trunk/test/Analysis/CostModel/X86/interleaved-store-i8.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-vectorize -S -mcpu=core-avx2 --debug-only=loop-vectorize -vectorizer-maximize-bandwidth < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: norecurse nounwind uwtable
 define void @doit_stride3(i8* nocapture %Ptr, i32 %Nels) local_unnamed_addr {
 ;CHECK: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %conv4
 ;CHECK: LV: Found an estimated cost of 8 for VF 2 For instruction:   store i8 %conv4
 ;CHECK: LV: Found an estimated cost of 9 for VF 4 For instruction:   store i8 %conv4
 ;CHECK: LV: Found an estimated cost of 12 for VF 8 For instruction:   store i8 %conv4
-;CHECK: LV: Found an estimated cost of 19 for VF 16 For instruction:   store i8 %conv4
-;CHECK: LV: Found an estimated cost of 35 for VF 32 For instruction:   store i8 %conv4
+;CHECK: LV: Found an estimated cost of 13 for VF 16 For instruction:   store i8 %conv4
+;CHECK: LV: Found an estimated cost of 16 for VF 32 For instruction:   store i8 %conv4
 entry:
   %cmp14 = icmp sgt i32 %Nels, 0
   br i1 %cmp14, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:
   %conv = trunc i32 %Nels to i8
   %conv1 = shl i8 %conv, 1
   %conv4 = shl i8 %conv, 2
for.end:
   ret void
 }
 
 ; Function Attrs: norecurse nounwind uwtable
 define void @doit_stride4(i8* nocapture %Ptr, i32 %Nels) local_unnamed_addr {
 ;CHECK: LV: Found an estimated cost of 1 for VF 1 For instruction:   store i8 %conv7
 ;CHECK: LV: Found an estimated cost of 13 for VF 2 For instruction:   store i8 %conv7
 ;CHECK: LV: Found an estimated cost of 10 for VF 4 For instruction:   store i8 %conv7
-;CHECK: LV: Found an estimated cost of 17 for VF 8 For instruction:   store i8 %conv7
-;CHECK: LV: Found an estimated cost of 22 for VF 16 For instruction:   store i8 %conv7
-;CHECK: LV: Found an estimated cost of 44 for VF 32 For instruction:   store i8 %conv7
+;CHECK: LV: Found an estimated cost of 11 for VF 8 For instruction:   store i8 %conv7
+;CHECK: LV: Found an estimated cost of 12 for VF 16 For instruction:   store i8 %conv7
+;CHECK: LV: Found an estimated cost of 16 for VF 32 For instruction:   store i8 %conv7
 entry:
   %cmp19 = icmp sgt i32 %Nels, 0
   br i1 %cmp19, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:
   %conv = trunc i32 %Nels to i8
   %conv1 = shl i8 %conv, 1
   %conv4 = shl i8 %conv, 2

llvm/trunk/test/Analysis/CostModel/X86/strided-load-i8.ll

 }
 
 define void @load_i8_stride3() {
 ;CHECK-LABEL: load_i8_stride3
 ;CHECK: Found an estimated cost of 1 for VF 1 For instruction:   %1 = load
 ;CHECK: Found an estimated cost of 1 for VF 2 For instruction:   %1 = load
 ;CHECK: Found an estimated cost of 1 for VF 4 For instruction:   %1 = load
 ;CHECK: Found an estimated cost of 3 for VF 8 For instruction:   %1 = load
-;CHECK: Found an estimated cost of 8 for VF 16 For instruction:   %1 = load
-;CHECK: Found an estimated cost of 20 for VF 32 For instruction:   %1 = load
-;CHECK: Found an estimated cost of 39 for VF 64 For instruction:   %1 = load
+;CHECK: Found an estimated cost of 13 for VF 16 For instruction:   %1 = load
+;CHECK: Found an estimated cost of 16 for VF 32 For instruction:   %1 = load
+;CHECK: Found an estimated cost of 25 for VF 64 For instruction:   %1 = load
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %0 = mul nsw i64 %indvars.iv, 3
   %arrayidx = getelementptr inbounds [10240 x i8], [10240 x i8]* @A, i64 0, i64 %0
   %1 = load i8, i8* %arrayidx, align 2