diff --git a/llvm/include/llvm/CodeGen/BasicTTIImpl.h b/llvm/include/llvm/CodeGen/BasicTTIImpl.h --- a/llvm/include/llvm/CodeGen/BasicTTIImpl.h +++ b/llvm/include/llvm/CodeGen/BasicTTIImpl.h @@ -1123,18 +1123,24 @@ for (unsigned Index : Indices) { assert(Index < Factor && "Invalid index for interleaved memory op"); + // Compute cost for extracting/inserting elements individually and using + // shuffles. Choose the minimum cost. + unsigned ExtractInsertCost = 0; // Extract elements from loaded vector for each sub vector. for (unsigned i = 0; i < NumSubElts; i++) - Cost += thisT()->getVectorInstrCost(Instruction::ExtractElement, VT, - Index + i * Factor); - } + ExtractInsertCost += thisT()->getVectorInstrCost( + Instruction::ExtractElement, VT, Index + i * Factor); + for (unsigned i = 0; i < NumSubElts; i++) + ExtractInsertCost += + thisT()->getVectorInstrCost(Instruction::InsertElement, SubVT, i); - unsigned InsSubCost = 0; - for (unsigned i = 0; i < NumSubElts; i++) - InsSubCost += - thisT()->getVectorInstrCost(Instruction::InsertElement, SubVT, i); + unsigned ShuffleCost = thisT()->getShuffleCost( + TTI::SK_PermuteSingleSrc, VT, Index, + FixedVectorType::get(VT->getElementType(), + VT->getNumElements() / 2)); - Cost += Indices.size() * InsSubCost; + Cost += std::min(ExtractInsertCost, ShuffleCost); + } } else { // The interleave cost is extract all elements from sub vectors, and // insert them into the wide vector. @@ -1149,11 +1155,19 @@ for (unsigned i = 0; i < NumSubElts; i++) ExtSubCost += thisT()->getVectorInstrCost(Instruction::ExtractElement, SubVT, i); - Cost += ExtSubCost * Factor; - + unsigned InsertExtractCost = ExtSubCost * Factor; for (unsigned i = 0; i < NumElts; i++) - Cost += static_cast(this) - ->getVectorInstrCost(Instruction::InsertElement, VT, i); + InsertExtractCost += static_cast(this)->getVectorInstrCost( + Instruction::InsertElement, VT, i); + + // Compute cost of shuffle as inserting the elements of the sub-vectors + // into the destination vector. The indices are not consecutive. + unsigned ShuffleCost = + Factor * thisT()->getShuffleCost( + TTI::SK_PermuteTwoSrc, VT, 0, + FixedVectorType::get(VT->getElementType(), + VT->getNumElements() / 2)); + Cost += std::min(ShuffleCost, InsertExtractCost); } if (!UseMaskForCond) diff --git a/llvm/test/Transforms/LoopVectorize/X86/interleaving.ll b/llvm/test/Transforms/LoopVectorize/X86/interleaving.ll --- a/llvm/test/Transforms/LoopVectorize/X86/interleaving.ll +++ b/llvm/test/Transforms/LoopVectorize/X86/interleaving.ll @@ -1,30 +1,50 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine < %s | FileCheck %s --check-prefix=SSE ; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=sandybridge < %s | FileCheck %s --check-prefix=AVX -; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=haswell < %s | FileCheck %s --check-prefix=AVX +; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=haswell < %s | FileCheck %s --check-prefix=HASWELL ; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=slm < %s | FileCheck %s --check-prefix=SSE -; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=atom < %s | FileCheck %s --check-prefix=SSE +; RUN: opt -S -mtriple=x86_64-pc_linux -loop-vectorize -instcombine -mcpu=atom < %s | FileCheck %s --check-prefix=ATOM define void @foo(i32* noalias nocapture %a, i32* noalias nocapture readonly %b) { ; SSE-LABEL: @foo( ; SSE-NEXT: entry: +; SSE-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] +; SSE: vector.ph: +; SSE-NEXT: br label [[VECTOR_BODY:%.*]] +; SSE: vector.body: +; SSE-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] +; SSE-NEXT: [[TMP0:%.*]] = shl nsw i64 [[INDEX]], 1 +; SSE-NEXT: [[TMP1:%.*]] = shl i64 [[INDEX]], 1 +; SSE-NEXT: [[TMP2:%.*]] = or i64 [[TMP1]], 8 +; SSE-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[TMP0]] +; SSE-NEXT: [[TMP4:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP2]] +; SSE-NEXT: [[TMP5:%.*]] = bitcast i32* [[TMP3]] to <8 x i32>* +; SSE-NEXT: [[TMP6:%.*]] = bitcast i32* [[TMP4]] to <8 x i32>* +; SSE-NEXT: [[WIDE_VEC:%.*]] = load <8 x i32>, <8 x i32>* [[TMP5]], align 4 +; SSE-NEXT: [[WIDE_VEC1:%.*]] = load <8 x i32>, <8 x i32>* [[TMP6]], align 4 +; SSE-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> +; SSE-NEXT: [[STRIDED_VEC2:%.*]] = shufflevector <8 x i32> [[WIDE_VEC1]], <8 x i32> poison, <4 x i32> +; SSE-NEXT: [[STRIDED_VEC3:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> +; SSE-NEXT: [[STRIDED_VEC4:%.*]] = shufflevector <8 x i32> [[WIDE_VEC1]], <8 x i32> poison, <4 x i32> +; SSE-NEXT: [[TMP7:%.*]] = add nsw <4 x i32> [[STRIDED_VEC3]], [[STRIDED_VEC]] +; SSE-NEXT: [[TMP8:%.*]] = add nsw <4 x i32> [[STRIDED_VEC4]], [[STRIDED_VEC2]] +; SSE-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDEX]] +; SSE-NEXT: [[TMP10:%.*]] = bitcast i32* [[TMP9]] to <4 x i32>* +; SSE-NEXT: store <4 x i32> [[TMP7]], <4 x i32>* [[TMP10]], align 4 +; SSE-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, i32* [[TMP9]], i64 4 +; SSE-NEXT: [[TMP12:%.*]] = bitcast i32* [[TMP11]] to <4 x i32>* +; SSE-NEXT: store <4 x i32> [[TMP8]], <4 x i32>* [[TMP12]], align 4 +; SSE-NEXT: [[INDEX_NEXT]] = add i64 [[INDEX]], 8 +; SSE-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1024 +; SSE-NEXT: br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]] +; SSE: middle.block: +; SSE-NEXT: br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]] +; SSE: scalar.ph: ; SSE-NEXT: br label [[FOR_BODY:%.*]] ; SSE: for.cond.cleanup: ; SSE-NEXT: ret void ; SSE: for.body: -; SSE-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ] -; SSE-NEXT: [[TMP0:%.*]] = shl nuw nsw i64 [[INDVARS_IV]], 1 -; SSE-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[TMP0]] -; SSE-NEXT: [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4 -; SSE-NEXT: [[TMP2:%.*]] = or i64 [[TMP0]], 1 -; SSE-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP2]] -; SSE-NEXT: [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX3]], align 4 -; SSE-NEXT: [[ADD4:%.*]] = add nsw i32 [[TMP3]], [[TMP1]] -; SSE-NEXT: [[ARRAYIDX6:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]] -; SSE-NEXT: store i32 [[ADD4]], i32* [[ARRAYIDX6]], align 4 -; SSE-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 -; SSE-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 1024 -; SSE-NEXT: br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]] +; SSE-NEXT: br i1 undef, label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], [[LOOP2:!llvm.loop !.*]] ; ; AVX-LABEL: @foo( ; AVX-NEXT: entry: @@ -35,15 +55,15 @@ ; AVX-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] ; AVX-NEXT: [[TMP0:%.*]] = shl nsw i64 [[INDEX]], 1 ; AVX-NEXT: [[TMP1:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[TMP0]] -; AVX-NEXT: [[TMP2:%.*]] = bitcast i32* [[TMP1]] to <8 x i32>* -; AVX-NEXT: [[WIDE_VEC:%.*]] = load <8 x i32>, <8 x i32>* [[TMP2]], align 4 -; AVX-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> -; AVX-NEXT: [[STRIDED_VEC1:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> -; AVX-NEXT: [[TMP3:%.*]] = add nsw <4 x i32> [[STRIDED_VEC1]], [[STRIDED_VEC]] +; AVX-NEXT: [[TMP2:%.*]] = bitcast i32* [[TMP1]] to <16 x i32>* +; AVX-NEXT: [[WIDE_VEC:%.*]] = load <16 x i32>, <16 x i32>* [[TMP2]], align 4 +; AVX-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <16 x i32> [[WIDE_VEC]], <16 x i32> poison, <8 x i32> +; AVX-NEXT: [[STRIDED_VEC1:%.*]] = shufflevector <16 x i32> [[WIDE_VEC]], <16 x i32> poison, <8 x i32> +; AVX-NEXT: [[TMP3:%.*]] = add nsw <8 x i32> [[STRIDED_VEC1]], [[STRIDED_VEC]] ; AVX-NEXT: [[TMP4:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDEX]] -; AVX-NEXT: [[TMP5:%.*]] = bitcast i32* [[TMP4]] to <4 x i32>* -; AVX-NEXT: store <4 x i32> [[TMP3]], <4 x i32>* [[TMP5]], align 4 -; AVX-NEXT: [[INDEX_NEXT]] = add i64 [[INDEX]], 4 +; AVX-NEXT: [[TMP5:%.*]] = bitcast i32* [[TMP4]] to <8 x i32>* +; AVX-NEXT: store <8 x i32> [[TMP3]], <8 x i32>* [[TMP5]], align 4 +; AVX-NEXT: [[INDEX_NEXT]] = add i64 [[INDEX]], 8 ; AVX-NEXT: [[TMP6:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1024 ; AVX-NEXT: br i1 [[TMP6]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]] ; AVX: middle.block: @@ -55,6 +75,88 @@ ; AVX: for.body: ; AVX-NEXT: br i1 undef, label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], [[LOOP2:!llvm.loop !.*]] ; +; HASWELL-LABEL: @foo( +; HASWELL-NEXT: entry: +; HASWELL-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] +; HASWELL: vector.ph: +; HASWELL-NEXT: br label [[VECTOR_BODY:%.*]] +; HASWELL: vector.body: +; HASWELL-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] +; HASWELL-NEXT: [[TMP0:%.*]] = shl nsw i64 [[INDEX]], 1 +; HASWELL-NEXT: [[TMP1:%.*]] = shl i64 [[INDEX]], 1 +; HASWELL-NEXT: [[TMP2:%.*]] = or i64 [[TMP1]], 8 +; HASWELL-NEXT: [[TMP3:%.*]] = shl i64 [[INDEX]], 1 +; HASWELL-NEXT: [[TMP4:%.*]] = or i64 [[TMP3]], 16 +; HASWELL-NEXT: [[TMP5:%.*]] = shl i64 [[INDEX]], 1 +; HASWELL-NEXT: [[TMP6:%.*]] = or i64 [[TMP5]], 24 +; HASWELL-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[TMP0]] +; HASWELL-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP2]] +; HASWELL-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP4]] +; HASWELL-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP6]] +; HASWELL-NEXT: [[TMP11:%.*]] = bitcast i32* [[TMP7]] to <8 x i32>* +; HASWELL-NEXT: [[TMP12:%.*]] = bitcast i32* [[TMP8]] to <8 x i32>* +; HASWELL-NEXT: [[TMP13:%.*]] = bitcast i32* [[TMP9]] to <8 x i32>* +; HASWELL-NEXT: [[TMP14:%.*]] = bitcast i32* [[TMP10]] to <8 x i32>* +; HASWELL-NEXT: [[WIDE_VEC:%.*]] = load <8 x i32>, <8 x i32>* [[TMP11]], align 4 +; HASWELL-NEXT: [[WIDE_VEC1:%.*]] = load <8 x i32>, <8 x i32>* [[TMP12]], align 4 +; HASWELL-NEXT: [[WIDE_VEC2:%.*]] = load <8 x i32>, <8 x i32>* [[TMP13]], align 4 +; HASWELL-NEXT: [[WIDE_VEC3:%.*]] = load <8 x i32>, <8 x i32>* [[TMP14]], align 4 +; HASWELL-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC4:%.*]] = shufflevector <8 x i32> [[WIDE_VEC1]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC5:%.*]] = shufflevector <8 x i32> [[WIDE_VEC2]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC6:%.*]] = shufflevector <8 x i32> [[WIDE_VEC3]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC7:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC8:%.*]] = shufflevector <8 x i32> [[WIDE_VEC1]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC9:%.*]] = shufflevector <8 x i32> [[WIDE_VEC2]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[STRIDED_VEC10:%.*]] = shufflevector <8 x i32> [[WIDE_VEC3]], <8 x i32> poison, <4 x i32> +; HASWELL-NEXT: [[TMP15:%.*]] = add nsw <4 x i32> [[STRIDED_VEC7]], [[STRIDED_VEC]] +; HASWELL-NEXT: [[TMP16:%.*]] = add nsw <4 x i32> [[STRIDED_VEC8]], [[STRIDED_VEC4]] +; HASWELL-NEXT: [[TMP17:%.*]] = add nsw <4 x i32> [[STRIDED_VEC9]], [[STRIDED_VEC5]] +; HASWELL-NEXT: [[TMP18:%.*]] = add nsw <4 x i32> [[STRIDED_VEC10]], [[STRIDED_VEC6]] +; HASWELL-NEXT: [[TMP19:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDEX]] +; HASWELL-NEXT: [[TMP20:%.*]] = bitcast i32* [[TMP19]] to <4 x i32>* +; HASWELL-NEXT: store <4 x i32> [[TMP15]], <4 x i32>* [[TMP20]], align 4 +; HASWELL-NEXT: [[TMP21:%.*]] = getelementptr inbounds i32, i32* [[TMP19]], i64 4 +; HASWELL-NEXT: [[TMP22:%.*]] = bitcast i32* [[TMP21]] to <4 x i32>* +; HASWELL-NEXT: store <4 x i32> [[TMP16]], <4 x i32>* [[TMP22]], align 4 +; HASWELL-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, i32* [[TMP19]], i64 8 +; HASWELL-NEXT: [[TMP24:%.*]] = bitcast i32* [[TMP23]] to <4 x i32>* +; HASWELL-NEXT: store <4 x i32> [[TMP17]], <4 x i32>* [[TMP24]], align 4 +; HASWELL-NEXT: [[TMP25:%.*]] = getelementptr inbounds i32, i32* [[TMP19]], i64 12 +; HASWELL-NEXT: [[TMP26:%.*]] = bitcast i32* [[TMP25]] to <4 x i32>* +; HASWELL-NEXT: store <4 x i32> [[TMP18]], <4 x i32>* [[TMP26]], align 4 +; HASWELL-NEXT: [[INDEX_NEXT]] = add i64 [[INDEX]], 16 +; HASWELL-NEXT: [[TMP27:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1024 +; HASWELL-NEXT: br i1 [[TMP27]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]] +; HASWELL: middle.block: +; HASWELL-NEXT: br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]] +; HASWELL: scalar.ph: +; HASWELL-NEXT: br label [[FOR_BODY:%.*]] +; HASWELL: for.cond.cleanup: +; HASWELL-NEXT: ret void +; HASWELL: for.body: +; HASWELL-NEXT: br i1 undef, label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], [[LOOP2:!llvm.loop !.*]] +; +; ATOM-LABEL: @foo( +; ATOM-NEXT: entry: +; ATOM-NEXT: br label [[FOR_BODY:%.*]] +; ATOM: for.cond.cleanup: +; ATOM-NEXT: ret void +; ATOM: for.body: +; ATOM-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ] +; ATOM-NEXT: [[TMP0:%.*]] = shl nuw nsw i64 [[INDVARS_IV]], 1 +; ATOM-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[TMP0]] +; ATOM-NEXT: [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX]], align 4 +; ATOM-NEXT: [[TMP2:%.*]] = or i64 [[TMP0]], 1 +; ATOM-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[TMP2]] +; ATOM-NEXT: [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX3]], align 4 +; ATOM-NEXT: [[ADD4:%.*]] = add nsw i32 [[TMP3]], [[TMP1]] +; ATOM-NEXT: [[ARRAYIDX6:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]] +; ATOM-NEXT: store i32 [[ADD4]], i32* [[ARRAYIDX6]], align 4 +; ATOM-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 +; ATOM-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 1024 +; ATOM-NEXT: br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]] +; entry: br label %for.body