[InstCombine] don't automatically drop poison-generating flags in SimplifyVectorDemandedElts

[spatel]

Summary

I noticed this while reviewing the test diffs in D115460 (and so the diffs in that patch will be reduced if this one is applied first).

This is effectively a revert of 3436dc29239d ( https://reviews.llvm.org/rG3436dc29239d ) - since that commit, we've made several enhancements, so the reasoning there is no longer valid. Specifically, we added a poison value to IR, and we clarified the behavior of undef/poison elements in a shuffle mask:
https://llvm.org/docs/LangRef.html#shufflevector-instruction

Alive2 seems to agree that the propagation of flags in the test diffs shown here are valid:
https://alive2.llvm.org/ce/z/UuY-jr
https://alive2.llvm.org/ce/z/GXoMD9
https://alive2.llvm.org/ce/z/nVCyVH

[nikic]

It looks like the shufflevector poison change hasn't landed yet? D93818 / D103874

[reames]

I was thinking about this as well, but you have more history on the discussion than I do.

Let me briefly mention the case which I was unclear about. For most of the demanded lane stuff, leaving the flags is clearly fine as we make only undemanded lanes "more poison". However, is there an interaction with undef and demanded lanes? Do any callers assume that flags hold for any value of undef chosen? It seems like we might have a version of the undef commit problem. (i.e. where two different places assume different values for an undef, and the first doesn't commit that to IR.) Not sure, but I was uncomfortable when trying to think it through.

In a local patch, I'd tried preserving the existing drop flags functionality for undef lanes. That appeared to allow all the test changes, but I didn't post it because I wasn't clear if it was actually needed or not.

[spatel]

In D115526#3185635, @nikic wrote:

It looks like the shufflevector poison change hasn't landed yet? D93818 / D103874

Thanks for the reminder! ( cc @aqjune @hyeongyukim @regehr )

I'm not sure what effect those patches would have here, so maybe we can add test examples to confirm that this doesn't break anything?
All of the combinations of poison/undef that I tried in Alive2 with shuffles similar to the ones in the diffs here are shown as valid.

[nikic]

LGTM. After looking a bit closer, I do think this is safe and independent of the shufflevector patches referenced above. We already convert non-demanded elements to poison, so converting them to poison through nowrap flags should be just fine.

[spatel]

In D115526#3188491, @nikic wrote:

LGTM. After looking a bit closer, I do think this is safe and independent of the shufflevector patches referenced above. We already convert non-demanded elements to poison, so converting them to poison through nowrap flags should be just fine.

Thanks! That's probably better than any of my attempts to put the reasoning into words.

References to preliminary steps in the path to cleaning this up:
https://llvm.org/PR43958
D70246

Let's give this a try and see if the theory holds up...

[aqjune]

In D115526#3185703, @spatel wrote:

In D115526#3185635, @nikic wrote:

It looks like the shufflevector poison change hasn't landed yet? D93818 / D103874

Thanks for the reminder! ( cc @aqjune @hyeongyukim @regehr )

Hi, sorry for my late reply.
The patch is blocked at the moment because the mm*_undefined* intrinsics must be correctly lowered first. (see: https://reviews.llvm.org/D103874#3022980)
Simply fixing them to return a zero vector would be the simplest solution, but not sure whether it will have no performance regression, and no one (including me) has no time to explore...

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

Value *InstCombinerImpl::SimplifyDemandedVectorElts(Value *V,
 
   // TODO: We bail completely on integer div/rem and shifts because they have
   // UB/poison potential, but that should be refined.
   BinaryOperator *BO;
   if (match(I, m_BinOp(BO)) && !BO->isIntDivRem() && !BO->isShift()) {
     simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
     simplifyAndSetOp(I, 1, DemandedElts, UndefElts2);
 
-    // Any change to an instruction with potential poison must clear those flags
-    // because we can not guarantee those constraints now. Other analysis may
-    // determine that it is safe to re-apply the flags.
-    if (MadeChange)
-      BO->dropPoisonGeneratingFlags();
-
     // Output elements are undefined if both are undefined. Consider things
     // like undef & 0. The result is known zero, not undef.
     UndefElts &= UndefElts2;
   }
 
   // If we've proven all of the lanes undef, return an undef value.
   // TODO: Intersect w/demanded lanes
   if (UndefElts.isAllOnes())
     return UndefValue::get(I->getType());;
 
   return MadeChange ? I : nullptr;
 }

llvm/test/Transforms/InstCombine/X86/x86-muldq-inseltpoison.ll

 define <2 x i64> @test_demanded_elts_pmuludq_128(<4 x i32> %a0, <4 x i32> %a1) {
 ; CHECK-LABEL: @test_demanded_elts_pmuludq_128(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[A0:%.*]], <4 x i32> poison, <4 x i32> <i32 0, i32 0, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32> [[A1:%.*]], <4 x i32> poison, <4 x i32> <i32 1, i32 1, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast <4 x i32> [[TMP1]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast <4 x i32> [[TMP2]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i64> [[TMP3]], <i64 4294967295, i64 poison>
 ; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i64> [[TMP4]], <i64 4294967295, i64 poison>
-; CHECK-NEXT:    [[TMP7:%.*]] = mul <2 x i64> [[TMP5]], [[TMP6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = mul nuw <2 x i64> [[TMP5]], [[TMP6]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <2 x i64> [[TMP7]], <2 x i64> poison, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <2 x i64> [[TMP8]]
 ;
   %1 = shufflevector <4 x i32> %a0, <4 x i32> poison, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   %2 = shufflevector <4 x i32> %a1, <4 x i32> poison, <4 x i32> <i32 1, i32 1, i32 3, i32 3>
   %3 = call <2 x i64> @llvm.x86.sse2.pmulu.dq(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <2 x i64> %3, <2 x i64> poison, <2 x i32> zeroinitializer
   ret <2 x i64> %4

llvm/test/Transforms/InstCombine/X86/x86-muldq.ll

 define <2 x i64> @test_demanded_elts_pmuludq_128(<4 x i32> %a0, <4 x i32> %a1) {
 ; CHECK-LABEL: @test_demanded_elts_pmuludq_128(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[A0:%.*]], <4 x i32> undef, <4 x i32> <i32 0, i32 0, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32> [[A1:%.*]], <4 x i32> undef, <4 x i32> <i32 1, i32 1, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast <4 x i32> [[TMP1]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast <4 x i32> [[TMP2]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i64> [[TMP3]], <i64 4294967295, i64 poison>
 ; CHECK-NEXT:    [[TMP6:%.*]] = and <2 x i64> [[TMP4]], <i64 4294967295, i64 poison>
-; CHECK-NEXT:    [[TMP7:%.*]] = mul <2 x i64> [[TMP5]], [[TMP6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = mul nuw <2 x i64> [[TMP5]], [[TMP6]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <2 x i64> [[TMP7]], <2 x i64> undef, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <2 x i64> [[TMP8]]
 ;
   %1 = shufflevector <4 x i32> %a0, <4 x i32> undef, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   %2 = shufflevector <4 x i32> %a1, <4 x i32> undef, <4 x i32> <i32 1, i32 1, i32 3, i32 3>
   %3 = call <2 x i64> @llvm.x86.sse2.pmulu.dq(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <2 x i64> %3, <2 x i64> undef, <2 x i32> zeroinitializer
   ret <2 x i64> %4

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

 }
 
 ; Negative test: not all 'or' insts can be converted to 'add'.
 
 define <4 x i8> @or_add_not_enough_masking(<4 x i8> %v) {
 ; CHECK-LABEL: @or_add_not_enough_masking(
 ; CHECK-NEXT:    [[V0:%.*]] = lshr <4 x i8> [[V:%.*]], <i8 1, i8 1, i8 1, i8 1>
 ; CHECK-NEXT:    [[T1:%.*]] = or <4 x i8> [[V0]], <i8 poison, i8 poison, i8 -64, i8 -64>
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i8> [[V0]], <i8 1, i8 2, i8 poison, i8 poison>
+; CHECK-NEXT:    [[T2:%.*]] = add nuw nsw <4 x i8> [[V0]], <i8 1, i8 2, i8 poison, i8 poison>
 ; CHECK-NEXT:    [[T3:%.*]] = shufflevector <4 x i8> [[T2]], <4 x i8> [[T1]], <4 x i32> <i32 0, i32 1, i32 6, i32 7>
 ; CHECK-NEXT:    ret <4 x i8> [[T3]]
 ;
   %v0 = lshr <4 x i8> %v, <i8 1, i8 1, i8 1, i8 1>          ; clear not enough top bits
   %t1 = or <4 x i8> %v0, <i8 192, i8 192, i8 192, i8 192>   ; set some top bits
   %t2 = add nsw nuw <4 x i8> %v0, <i8 1, i8 2, i8 3, i8 4>  ; this can't be converted to 'or'
   %t3 = shufflevector <4 x i8> %t1, <4 x i8> %t2, <4 x i32> <i32 4, i32 5, i32 2, i32 3>
   ret <4 x i8> %t3

llvm/test/Transforms/InstCombine/shuffle_select.ll

 }
 
 ; Negative test: not all 'or' insts can be converted to 'add'.
 
 define <4 x i8> @or_add_not_enough_masking(<4 x i8> %v) {
 ; CHECK-LABEL: @or_add_not_enough_masking(
 ; CHECK-NEXT:    [[V0:%.*]] = lshr <4 x i8> [[V:%.*]], <i8 1, i8 1, i8 1, i8 1>
 ; CHECK-NEXT:    [[T1:%.*]] = or <4 x i8> [[V0]], <i8 poison, i8 poison, i8 -64, i8 -64>
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i8> [[V0]], <i8 1, i8 2, i8 poison, i8 poison>
+; CHECK-NEXT:    [[T2:%.*]] = add nuw nsw <4 x i8> [[V0]], <i8 1, i8 2, i8 poison, i8 poison>
 ; CHECK-NEXT:    [[T3:%.*]] = shufflevector <4 x i8> [[T2]], <4 x i8> [[T1]], <4 x i32> <i32 0, i32 1, i32 6, i32 7>
 ; CHECK-NEXT:    ret <4 x i8> [[T3]]
 ;
   %v0 = lshr <4 x i8> %v, <i8 1, i8 1, i8 1, i8 1>          ; clear not enough top bits
   %t1 = or <4 x i8> %v0, <i8 192, i8 192, i8 192, i8 192>   ; set some top bits
   %t2 = add nsw nuw <4 x i8> %v0, <i8 1, i8 2, i8 3, i8 4>  ; this can't be converted to 'or'
   %t3 = shufflevector <4 x i8> %t1, <4 x i8> %t2, <4 x i32> <i32 4, i32 5, i32 2, i32 3>
   ret <4 x i8> %t3

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

;
   %shuffle = shufflevector <4 x float> %out123, <4 x float> poison, <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
   ret <4 x float> %shuffle
 }
 
 ; Test undef replacement in constant vector elements with binops.
 
 define <3 x i8> @shuf_add(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_add(
-; CHECK-NEXT:    [[BO:%.*]] = add <3 x i8> [[X:%.*]], <i8 poison, i8 2, i8 3>
+; CHECK-NEXT:    [[BO:%.*]] = add nsw <3 x i8> [[X:%.*]], <i8 poison, i8 2, i8 3>
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> poison, <3 x i32> <i32 1, i32 undef, i32 2>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = add nsw <3 x i8> %x, <i8 1, i8 2, i8 3>
   %r = shufflevector <3 x i8> %bo, <3 x i8> poison, <3 x i32> <i32 1, i32 undef, i32 2>
   ret <3 x i8> %r
 }
 
 define <3 x i8> @shuf_sub(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_sub(
-; CHECK-NEXT:    [[BO:%.*]] = sub <3 x i8> <i8 1, i8 poison, i8 3>, [[X:%.*]]
+; CHECK-NEXT:    [[BO:%.*]] = sub nuw <3 x i8> <i8 1, i8 poison, i8 3>, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> poison, <3 x i32> <i32 0, i32 undef, i32 2>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = sub nuw <3 x i8> <i8 1, i8 2, i8 3>, %x
   %r = shufflevector <3 x i8> %bo, <3 x i8> poison, <3 x i32> <i32 0, i32 undef, i32 2>
   ret <3 x i8> %r
 }
 
 define <3 x i8> @shuf_mul(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_mul(
-; CHECK-NEXT:    [[BO:%.*]] = mul <3 x i8> [[X:%.*]], <i8 1, i8 poison, i8 3>
+; CHECK-NEXT:    [[BO:%.*]] = mul nsw <3 x i8> [[X:%.*]], <i8 1, i8 poison, i8 3>
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> poison, <3 x i32> <i32 0, i32 2, i32 0>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = mul nsw <3 x i8> %x, <i8 1, i8 2, i8 3>
   %r = shufflevector <3 x i8> %bo, <3 x i8> poison, <3 x i32> <i32 0, i32 2, i32 0>
   ret <3 x i8> %r
 }
 

llvm/test/Transforms/InstCombine/vec_demanded_elts.ll

;
   %shuffle = shufflevector <4 x float> %out123, <4 x float> undef, <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
   ret <4 x float> %shuffle
 }
 
 ; Test undef replacement in constant vector elements with binops.
 
 define <3 x i8> @shuf_add(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_add(
-; CHECK-NEXT:    [[BO:%.*]] = add <3 x i8> [[X:%.*]], <i8 poison, i8 2, i8 3>
+; CHECK-NEXT:    [[BO:%.*]] = add nsw <3 x i8> [[X:%.*]], <i8 poison, i8 2, i8 3>
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> undef, <3 x i32> <i32 1, i32 undef, i32 2>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = add nsw <3 x i8> %x, <i8 1, i8 2, i8 3>
   %r = shufflevector <3 x i8> %bo, <3 x i8> undef, <3 x i32> <i32 1, i32 undef, i32 2>
   ret <3 x i8> %r
 }
 
 define <3 x i8> @shuf_sub(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_sub(
-; CHECK-NEXT:    [[BO:%.*]] = sub <3 x i8> <i8 1, i8 poison, i8 3>, [[X:%.*]]
+; CHECK-NEXT:    [[BO:%.*]] = sub nuw <3 x i8> <i8 1, i8 poison, i8 3>, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> undef, <3 x i32> <i32 0, i32 undef, i32 2>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = sub nuw <3 x i8> <i8 1, i8 2, i8 3>, %x
   %r = shufflevector <3 x i8> %bo, <3 x i8> undef, <3 x i32> <i32 0, i32 undef, i32 2>
   ret <3 x i8> %r
 }
 
 define <3 x i8> @shuf_mul(<3 x i8> %x) {
 ; CHECK-LABEL: @shuf_mul(
-; CHECK-NEXT:    [[BO:%.*]] = mul <3 x i8> [[X:%.*]], <i8 1, i8 poison, i8 3>
+; CHECK-NEXT:    [[BO:%.*]] = mul nsw <3 x i8> [[X:%.*]], <i8 1, i8 poison, i8 3>
 ; CHECK-NEXT:    [[R:%.*]] = shufflevector <3 x i8> [[BO]], <3 x i8> undef, <3 x i32> <i32 0, i32 2, i32 0>
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %bo = mul nsw <3 x i8> %x, <i8 1, i8 2, i8 3>
   %r = shufflevector <3 x i8> %bo, <3 x i8> undef, <3 x i32> <i32 0, i32 2, i32 0>
   ret <3 x i8> %r
 }