[InstCombine] Allow splats with poison/undef in llvm::decomposeBitTestICmp

[jmciver]

Summary

This change is made to enable conversion of a masked icmp splat vector
containing poison/undef to an equality expression.

llvm::decomposeBitTestICmp Alive2 correctness examples using splat/masking vectors:

• SLT <
• SLE <=
• SGT >
• SGE >=
• ULT <u
• ULE <=u
• UGT >u
• UGE >=u

Tests have been verified using Alive2:

• icmp-logical.ll: @nomask_splat_and_B_allones
• icmp-logical.ll: @nomask_splat_and_B_mixed
• signed-truncation-check.ll: @positive_vec_undef0

[jmciver]

Update patch per changes to test label names in D143031

[jmciver]

Update per change to poison based splat vectors in D143031

[jmciver]

Rebase onto latest main.

[RKSimon]

please can you add alive2 links?

[jmciver]

I have added Alive2 links to the summary as per @RKSimon request.

[jmciver]

@RKSimon I added Alive2 examples exercising llvm::decomposeBitTestICmp using splat/mask vectors for all supported comparisons.

[RKSimon]

LGTM

[jmciver]

Thanks @RKSimon for reviewing! Can you please review the predecessor D143031?

[jmciver]

@RKSimon thanks for taking the time to review the patch!

I have recently requested repository access. In the interim can you please land this patch for me?

Name: John McIver
Email: [e-mail]

llvm/lib/Analysis/CmpInstAnalysis.cpp

 }
 
 bool llvm::decomposeBitTestICmp(Value *LHS, Value *RHS,
                                 CmpInst::Predicate &Pred,
                                 Value *&X, APInt &Mask, bool LookThruTrunc) {
   using namespace PatternMatch;
 
   const APInt *C;
-  if (!match(RHS, m_APInt(C)))
+  if (!match(RHS, m_APIntAllowUndef(C)))
     return false;
 
   switch (Pred) {
   default:
     return false;
   case ICmpInst::ICMP_SLT:
     // X < 0 is equivalent to (X & SignMask) != 0.
     if (!C->isZero())

llvm/test/Transforms/InstCombine/icmp-logical.ll

;
   %t2 = icmp ne i32 %t1, 0
   %t3 = icmp ne i32 %x, 2147483647
   %t4 = select i1 %t3, i1 true, i1 %t2
   ret i1 %t4
 }
 
 define <2 x i1> @nomask_splat_and_B_allones(<2 x i32> %A) {
 ; CHECK-LABEL: @nomask_splat_and_B_allones(
-; CHECK-NEXT:    [[TST1:%.*]] = icmp slt <2 x i32> [[A:%.*]], <i32 0, i32 poison>
-; CHECK-NEXT:    [[MASK2:%.*]] = and <2 x i32> [[A]], <i32 1879048192, i32 1879048192>
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq <2 x i32> [[MASK2]], <i32 1879048192, i32 1879048192>
-; CHECK-NEXT:    [[RES:%.*]] = and <2 x i1> [[TST1]], [[TST2]]
+; CHECK-NEXT:    [[RES:%.*]] = icmp ugt <2 x i32> [[A:%.*]], <i32 -268435457, i32 -268435457>
 ; CHECK-NEXT:    ret <2 x i1> [[RES]]
 ;
   %tst1 = icmp slt <2 x i32> %A, <i32 0, i32 poison>
   %mask2 = and <2 x i32> %A, <i32 1879048192, i32 1879048192>
   %tst2 = icmp eq <2 x i32> %mask2, <i32 1879048192, i32 1879048192>
   %res = and <2 x i1> %tst1, %tst2
   ret <2 x i1> %res
 }
 
 define <2 x i1> @nomask_splat_and_B_mixed(<2 x i32> %A) {
 ; CHECK-LABEL: @nomask_splat_and_B_mixed(
-; CHECK-NEXT:    [[TST1:%.*]] = icmp sgt <2 x i32> [[A:%.*]], <i32 -1, i32 poison>
-; CHECK-NEXT:    [[MASK2:%.*]] = and <2 x i32> [[A]], <i32 1879048192, i32 1879048192>
-; CHECK-NEXT:    [[TST2:%.*]] = icmp eq <2 x i32> [[MASK2]], <i32 1879048192, i32 1879048192>
-; CHECK-NEXT:    [[RES:%.*]] = and <2 x i1> [[TST1]], [[TST2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 -268435456, i32 -268435456>
+; CHECK-NEXT:    [[RES:%.*]] = icmp eq <2 x i32> [[TMP1]], <i32 1879048192, i32 1879048192>
 ; CHECK-NEXT:    ret <2 x i1> [[RES]]
 ;
   %tst1 = icmp sgt <2 x i32> %A, <i32 -1, i32 poison>
   %mask2 = and <2 x i32> %A, <i32 1879048192, i32 1879048192>
   %tst2 = icmp eq <2 x i32> %mask2, <i32 1879048192, i32 1879048192>
   %res = and <2 x i1> %tst1, %tst2
   ret <2 x i1> %res
 }

llvm/test/Transforms/InstCombine/signed-truncation-check.ll

;
   %t2 = add <2 x i32> %arg, <i32 128, i32 256>
   %t3 = icmp ult <2 x i32> %t2, <i32 256, i32 512>
   %t4 = and <2 x i1> %t1, %t3
   ret <2 x i1> %t4
 }
 
 define <3 x i1> @positive_vec_undef0(<3 x i32> %arg) {
 ; CHECK-LABEL: @positive_vec_undef0(
-; CHECK-NEXT:    [[T1:%.*]] = icmp sgt <3 x i32> [[ARG:%.*]], <i32 -1, i32 undef, i32 -1>
-; CHECK-NEXT:    [[T2:%.*]] = add <3 x i32> [[ARG]], <i32 128, i32 128, i32 128>
-; CHECK-NEXT:    [[T3:%.*]] = icmp ult <3 x i32> [[T2]], <i32 256, i32 256, i32 256>
-; CHECK-NEXT:    [[T4:%.*]] = and <3 x i1> [[T1]], [[T3]]
-; CHECK-NEXT:    ret <3 x i1> [[T4]]
+; CHECK-NEXT:    [[T4_SIMPLIFIED:%.*]] = icmp ult <3 x i32> [[ARG:%.*]], <i32 128, i32 128, i32 128>
+; CHECK-NEXT:    ret <3 x i1> [[T4_SIMPLIFIED]]
 ;
   %t1 = icmp sgt <3 x i32> %arg, <i32 -1, i32 undef, i32 -1>
   %t2 = add <3 x i32> %arg, <i32 128, i32 128, i32 128>
   %t3 = icmp ult <3 x i32> %t2, <i32 256, i32 256, i32 256>
   %t4 = and <3 x i1> %t1, %t3
   ret <3 x i1> %t4
 }