[InstCombine] remove useless insertelement

[Chenbing.Zheng]

Summary

Remove insertelement, if we don't use the inserted element.
extractelement (bitcast (insertelement (Vec, b)), a) -> extractelement (bitcast (Vec), a)

[RKSimon]

Shouldn't this be in InstCombinerImpl::SimplifyDemandedVectorElts ?

[Chenbing.Zheng]

In D128890#3621675, @RKSimon wrote:

Shouldn't this be in InstCombinerImpl::SimplifyDemandedVectorElts ?

'SimplifyDemandedVectorElts' cannot support scalable vector type now, and it seems to be no need to break this setting.

[RKSimon]

In which case, we need a FIXME comment explaining that this should be removed once scale vectors are supported

[Chenbing.Zheng]

In D128890#3624484, @RKSimon wrote:

In which case, we need a FIXME comment explaining that this should be removed once scale vectors are supported

In D78895, @huihuiz add this limit for SimplifyDemandedVectorElts. Maybe SimplifyDemandedVectorElts will no longer support scale vectors.

[RKSimon]

In D128890#3627776, @Chenbing.Zheng wrote:

In D128890#3624484, @RKSimon wrote:

In which case, we need a FIXME comment explaining that this should be removed once scale vectors are supported

In D78895, @huihuiz add this limit for SimplifyDemandedVectorElts. Maybe SimplifyDemandedVectorElts will no longer support scale vectors.

More likely its untested / has edge cases and they haven't the bandwidth to address it yet. @dmgreen is currently dealing with a similar limit that was added in DAG (D128918)

Adding code to foldBitcastExtElt to get around this limitation must be seen as a temporary measure only.

[Chenbing.Zheng]

add fixme comment

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

250

Are there tests for multiuse?

llvm/test/Transforms/InstCombine/vscale_extractelement-inseltpoison.ll

47–48

technically its not a wrong insert - 'useless' might be a better term!

llvm/test/Transforms/InstCombine/vscale_extractelement.ll

43–44

technically its not a wrong insert - 'useless' might be a better term!

[Chenbing.Zheng]

complete tests

[RKSimon]

LGTM - but please add back the FIXME that you're lost in the rebase

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

248

Add back the FIXME

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

Instruction *InstCombinerImpl::foldBitcastExtElt(ExtractElementInst &Ext) {
 
   assert(NumSrcElts.isScalable() == NumElts.isScalable() &&
          "Src and Dst must be the same sort of vector type");
 
   // If the source elements are wider than the destination, try to shift and
   // truncate a subset of scalar bits of an insert op.
   if (NumSrcElts.getKnownMinValue() < NumElts.getKnownMinValue()) {
     Value *Scalar;
+    Value *Vec;
     uint64_t InsIndexC;
-    if (!match(X, m_InsertElt(m_Value(), m_Value(Scalar),
+    if (!match(X, m_InsertElt(m_Value(Vec), m_Value(Scalar),
                               m_ConstantInt(InsIndexC))))
       return nullptr;
 
     // The extract must be from the subset of vector elements that we inserted
     // into. Example: if we inserted element 1 of a <2 x i64> and we are
     // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
     // of elements 4-7 of the bitcasted vector.
     unsigned NarrowingRatio =
         NumElts.getKnownMinValue() / NumSrcElts.getKnownMinValue();
-    if (ExtIndexC / NarrowingRatio != InsIndexC)
+
+    if (ExtIndexC / NarrowingRatio != InsIndexC) {
+      // Remove insertelement, if we don't use the inserted element.
+      // extractelement (bitcast (insertelement (Vec, b)), a) ->
+      // extractelement (bitcast (Vec), a)
+      if (X->hasOneUse() && Ext.getVectorOperand()->hasOneUse()) {
+        Value *NewBC = Builder.CreateBitCast(Vec, Ext.getVectorOperandType());
+        return ExtractElementInst::Create(NewBC, Ext.getIndexOperand());
+      }
       return nullptr;
+    }
 
     // We are extracting part of the original scalar. How that scalar is
     // inserted into the vector depends on the endian-ness. Example:
     //              Vector Byte Elt Index:    0  1  2  3  4  5  6  7
     //                                       +--+--+--+--+--+--+--+--+
     // inselt <2 x i32> V, <i32> S, 1:       |V0|V1|V2|V3|S0|S1|S2|S3|
     // extelt <4 x i16> V', 3:               |                 |S2|S3|
     //                                       +--+--+--+--+--+--+--+--+

llvm/test/Transforms/InstCombine/vscale_extractelement-inseltpoison.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
+
+declare void @use_vscale_2_i32(<vscale x 2 x i32>)
+declare void @use_vscale_8_i8(<vscale x 8 x i8>)
+
 define i32 @extractelement_in_range(<vscale x 4 x i32> %a) {
 ; CHECK-LABEL: @extractelement_in_range(
 ; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 4 x i32> [[A:%.*]], i64 1
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %r = extractelement <vscale x 4 x i32> %a, i64 1
   ret i32 %r
 }

 ; CHECK-NEXT:    [[R:%.*]] = trunc i32 [[X:%.*]] to i8
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1
   %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
   %r = extractelement <vscale x 8 x i8> %vec_cast, i32 4
   ret i8 %r
 }
 
-; TODO: Instcombine could remove the insert.
-define i8 @extractelement_bitcast_wrong_insert(<vscale x 2 x i32> %a, i32 %x) {
-; CHECK-LABEL: @extractelement_bitcast_wrong_insert(
+define i8 @extractelement_bitcast_useless_insert(<vscale x 2 x i32> %a, i32 %x) {
+; CHECK-LABEL: @extractelement_bitcast_useless_insert(
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <vscale x 2 x i32> [[A:%.*]] to <vscale x 8 x i8>
+; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 8 x i8> [[TMP1]], i64 2
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1
+  %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
+  %r = extractelement <vscale x 8 x i8> %vec_cast, i32 2
+  ret i8 %r
+}
+
+; extra use tests
+
+define i8 @extractelement_bitcast_insert_extra_use_insert(<vscale x 2 x i32> %a, i32 %x) {
+; CHECK-LABEL: @extractelement_bitcast_insert_extra_use_insert(
 ; CHECK-NEXT:    [[VEC:%.*]] = insertelement <vscale x 2 x i32> [[A:%.*]], i32 [[X:%.*]], i64 1
+; CHECK-NEXT:    call void @use_vscale_2_i32(<vscale x 2 x i32> [[VEC]])
 ; CHECK-NEXT:    [[VEC_CAST:%.*]] = bitcast <vscale x 2 x i32> [[VEC]] to <vscale x 8 x i8>
 ; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 8 x i8> [[VEC_CAST]], i64 2
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
-  %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1 ; <- This insert could be removed.
+  %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1
+  call void @use_vscale_2_i32(<vscale x 2 x i32> %vec)
+  %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
+  %r = extractelement <vscale x 8 x i8> %vec_cast, i32 2
+  ret i8 %r
+}
+
+define i8 @extractelement_bitcast_insert_extra_use_bitcast(<vscale x 2 x i32> %a, i32 %x) {
+; CHECK-LABEL: @extractelement_bitcast_insert_extra_use_bitcast(
+; CHECK-NEXT:    [[VEC:%.*]] = insertelement <vscale x 2 x i32> [[A:%.*]], i32 [[X:%.*]], i64 1
+; CHECK-NEXT:    [[VEC_CAST:%.*]] = bitcast <vscale x 2 x i32> [[VEC]] to <vscale x 8 x i8>
+; CHECK-NEXT:    call void @use_vscale_8_i8(<vscale x 8 x i8> [[VEC_CAST]])
+; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 8 x i8> [[VEC_CAST]], i64 2
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1
   %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
+  call void @use_vscale_8_i8(<vscale x 8 x i8> %vec_cast)
   %r = extractelement <vscale x 8 x i8> %vec_cast, i32 2
   ret i8 %r
 }
 
 define i32 @extractelement_shuffle_maybe_out_of_range(i32 %v) {
 ; CHECK-LABEL: @extractelement_shuffle_maybe_out_of_range(
 ; CHECK-NEXT:    [[IN:%.*]] = insertelement <vscale x 4 x i32> poison, i32 [[V:%.*]], i64 0
 ; CHECK-NEXT:    [[SPLAT:%.*]] = shufflevector <vscale x 4 x i32> [[IN]], <vscale x 4 x i32> poison, <vscale x 4 x i32> zeroinitializer

llvm/test/Transforms/InstCombine/vscale_extractelement.ll

 ; CHECK-NEXT:    [[R:%.*]] = trunc i32 [[X:%.*]] to i8
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1
   %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
   %r = extractelement <vscale x 8 x i8> %vec_cast, i32 4
   ret i8 %r
 }
 
-; TODO: Instcombine could remove the insert.
-define i8 @extractelement_bitcast_wrong_insert(<vscale x 2 x i32> %a, i32 %x) {
-; CHECK-LABEL: @extractelement_bitcast_wrong_insert(
-; CHECK-NEXT:    [[VEC:%.*]] = insertelement <vscale x 2 x i32> [[A:%.*]], i32 [[X:%.*]], i64 1
-; CHECK-NEXT:    [[VEC_CAST:%.*]] = bitcast <vscale x 2 x i32> [[VEC]] to <vscale x 8 x i8>
-; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 8 x i8> [[VEC_CAST]], i64 2
+define i8 @extractelement_bitcast_useless_insert(<vscale x 2 x i32> %a, i32 %x) {
+; CHECK-LABEL: @extractelement_bitcast_useless_insert(
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <vscale x 2 x i32> [[A:%.*]] to <vscale x 8 x i8>
+; CHECK-NEXT:    [[R:%.*]] = extractelement <vscale x 8 x i8> [[TMP1]], i64 2
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %vec = insertelement <vscale x 2 x i32> %a, i32 %x, i32 1 ; <- This insert could be removed.
   %vec_cast = bitcast <vscale x 2 x i32> %vec to <vscale x 8 x i8>
   %r = extractelement <vscale x 8 x i8> %vec_cast, i32 2
   ret i8 %r
 }