From aff5bee35fb36897dd5414a52c11c14d2f858822 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Sun, 8 Sep 2019 19:03:01 +0000 Subject: [PATCH] [InstCombine] fold extract+insert into identity shuffle This is similar to the existing fold for splats added with: rL365379 If we can adjust the shuffle mask to include another element in an identity mask (if it changes vector length, that's an extract/insert subvector operation in the backend), then that can eliminate extractelement/insertelement pairs in IR. All targets are expected to lower shuffles with identity masks efficiently. llvm-svn: 371340 --- .../InstCombine/InstCombineVectorOps.cpp | 52 ++++++++++++++++++++++ .../InstCombine/insert-extract-shuffle.ll | 17 +++---- 2 files changed, 61 insertions(+), 8 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp b/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp index dc9abdd..b07aae4 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp @@ -766,6 +766,55 @@ static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) { return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask); } +/// Try to fold an extract+insert element into an existing identity shuffle by +/// changing the shuffle's mask to include the index of this insert element. +static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) { + // Check if the vector operand of this insert is an identity shuffle. + auto *Shuf = dyn_cast(InsElt.getOperand(0)); + if (!Shuf || !isa(Shuf->getOperand(1)) || + !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding())) + return nullptr; + + // Check for a constant insertion index. + uint64_t IdxC; + if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC))) + return nullptr; + + // Check if this insert's scalar op is extracted from the identity shuffle's + // input vector. + Value *Scalar = InsElt.getOperand(1); + Value *X = Shuf->getOperand(0); + if (!match(Scalar, m_ExtractElement(m_Specific(X), m_SpecificInt(IdxC)))) + return nullptr; + + // Replace the shuffle mask element at the index of this extract+insert with + // that same index value. + // For example: + // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask' + unsigned NumMaskElts = Shuf->getType()->getVectorNumElements(); + SmallVector NewMaskVec(NumMaskElts); + Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext()); + Constant *NewMaskEltC = ConstantInt::get(I32Ty, IdxC); + Constant *OldMask = Shuf->getMask(); + for (unsigned i = 0; i != NumMaskElts; ++i) { + if (i != IdxC) { + // All mask elements besides the inserted element remain the same. + NewMaskVec[i] = OldMask->getAggregateElement(i); + } else if (OldMask->getAggregateElement(i) == NewMaskEltC) { + // If the mask element was already set, there's nothing to do + // (demanded elements analysis may unset it later). + return nullptr; + } else { + assert(isa(OldMask->getAggregateElement(i)) && + "Unexpected shuffle mask element for identity shuffle"); + NewMaskVec[i] = NewMaskEltC; + } + } + + Constant *NewMask = ConstantVector::get(NewMaskVec); + return new ShuffleVectorInst(X, Shuf->getOperand(1), NewMask); +} + /// If we have an insertelement instruction feeding into another insertelement /// and the 2nd is inserting a constant into the vector, canonicalize that /// constant insertion before the insertion of a variable: @@ -987,6 +1036,9 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { if (Instruction *Splat = foldInsEltIntoSplat(IE)) return Splat; + if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(IE)) + return IdentityShuf; + return nullptr; } diff --git a/llvm/test/Transforms/InstCombine/insert-extract-shuffle.ll b/llvm/test/Transforms/InstCombine/insert-extract-shuffle.ll index f6a837f..1eb1248 100644 --- a/llvm/test/Transforms/InstCombine/insert-extract-shuffle.ll +++ b/llvm/test/Transforms/InstCombine/insert-extract-shuffle.ll @@ -575,9 +575,7 @@ define <4 x float> @insert_in_nonsplat2(float %x, <4 x float> %y) { define <4 x i8> @shuf_identity_padding(<2 x i8> %x, i8 %y) { ; CHECK-LABEL: @shuf_identity_padding( -; CHECK-NEXT: [[V0:%.*]] = shufflevector <2 x i8> [[X:%.*]], <2 x i8> undef, <4 x i32> -; CHECK-NEXT: [[X1:%.*]] = extractelement <2 x i8> [[X]], i32 1 -; CHECK-NEXT: [[V1:%.*]] = insertelement <4 x i8> [[V0]], i8 [[X1]], i32 1 +; CHECK-NEXT: [[V1:%.*]] = shufflevector <2 x i8> [[X:%.*]], <2 x i8> undef, <4 x i32> ; CHECK-NEXT: [[V2:%.*]] = insertelement <4 x i8> [[V1]], i8 [[Y:%.*]], i32 2 ; CHECK-NEXT: ret <4 x i8> [[V2]] ; @@ -590,9 +588,7 @@ define <4 x i8> @shuf_identity_padding(<2 x i8> %x, i8 %y) { define <3 x i8> @shuf_identity_extract(<4 x i8> %x, i8 %y) { ; CHECK-LABEL: @shuf_identity_extract( -; CHECK-NEXT: [[V0:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> undef, <3 x i32> -; CHECK-NEXT: [[X1:%.*]] = extractelement <4 x i8> [[X]], i32 1 -; CHECK-NEXT: [[V1:%.*]] = insertelement <3 x i8> [[V0]], i8 [[X1]], i32 1 +; CHECK-NEXT: [[V1:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> undef, <3 x i32> ; CHECK-NEXT: [[V2:%.*]] = insertelement <3 x i8> [[V1]], i8 [[Y:%.*]], i32 2 ; CHECK-NEXT: ret <3 x i8> [[V2]] ; @@ -607,8 +603,7 @@ define <4 x float> @shuf_identity_extract_extra_use(<6 x float> %x, float %y) { ; CHECK-LABEL: @shuf_identity_extract_extra_use( ; CHECK-NEXT: [[V0:%.*]] = shufflevector <6 x float> [[X:%.*]], <6 x float> undef, <4 x i32> ; CHECK-NEXT: call void @use(<4 x float> [[V0]]) -; CHECK-NEXT: [[X1:%.*]] = extractelement <6 x float> [[X]], i32 2 -; CHECK-NEXT: [[V1:%.*]] = insertelement <4 x float> [[V0]], float [[X1]], i32 2 +; CHECK-NEXT: [[V1:%.*]] = shufflevector <6 x float> [[X]], <6 x float> undef, <4 x i32> ; CHECK-NEXT: [[V2:%.*]] = insertelement <4 x float> [[V1]], float [[Y:%.*]], i32 1 ; CHECK-NEXT: ret <4 x float> [[V2]] ; @@ -620,6 +615,8 @@ define <4 x float> @shuf_identity_extract_extra_use(<6 x float> %x, float %y) { ret <4 x float> %v2 } +; Negative test - can't map variable index to shuffle mask. + define <4 x i8> @shuf_identity_padding_variable_index(<2 x i8> %x, i8 %y, i32 %index) { ; CHECK-LABEL: @shuf_identity_padding_variable_index( ; CHECK-NEXT: [[V0:%.*]] = shufflevector <2 x i8> [[X:%.*]], <2 x i8> undef, <4 x i32> @@ -635,6 +632,8 @@ define <4 x i8> @shuf_identity_padding_variable_index(<2 x i8> %x, i8 %y, i32 %i ret <4 x i8> %v2 } +; Negative test - don't create arbitrary shuffle masks. + define <4 x i8> @shuf_identity_padding_wrong_source_vec(<2 x i8> %x, i8 %y, <2 x i8> %other) { ; CHECK-LABEL: @shuf_identity_padding_wrong_source_vec( ; CHECK-NEXT: [[V0:%.*]] = shufflevector <2 x i8> [[X:%.*]], <2 x i8> undef, <4 x i32> @@ -650,6 +649,8 @@ define <4 x i8> @shuf_identity_padding_wrong_source_vec(<2 x i8> %x, i8 %y, <2 x ret <4 x i8> %v2 } +; Negative test - don't create arbitrary shuffle masks. + define <4 x i8> @shuf_identity_padding_wrong_index(<2 x i8> %x, i8 %y) { ; CHECK-LABEL: @shuf_identity_padding_wrong_index( ; CHECK-NEXT: [[V0:%.*]] = shufflevector <2 x i8> [[X:%.*]], <2 x i8> undef, <4 x i32> -- 2.7.4