[DAG] SimplifyDemandedBits - if we're only demanding the signbits, a MIN/MAX node can be simplified to a OR or AND node

[RKSimon]

Summary

Extension to the signbit case, if the signbits extend down through all the demanded bits then SMIN/SMAX/UMIN/UMAX nodes can be simplified to a OR/AND/AND/OR.

Alive2: https://alive2.llvm.org/ce/z/mFVFAn (general case)

[goldstein.w.n]

Can you parameterize the proofs with C1 and C2 instead of just 3 and 1 to make them complete?

[goldstein.w.n]

Also I think this also works for umax / umin (although inverted): https://alive2.llvm.org/ce/z/UX_NYn
There is a fair bit of common codes between, maybe a this should also come with a helper like
simplifyMinMaxWithDemandedBits.

[RKSimon]

I'll update this to add umin/umax handling

[RKSimon]

Added UMIN/UMAX handling and merged all MIN/MAX cases to share code

SMIN/SMAX are still missing proper known bits handling in SimplifyDemandedBits - I'll address this separately with proper test coverage.

[RKSimon]

ping?

[goldstein.w.n]

Other than the few nits looks good.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

2185

Should compute Known for smin/smax? Imo also just fill in the TODO. Its not much code required.

2195

I guess already existed but Known computation should be after the condition folding has failed already.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

2185

Adding smin/smax knownbits handling adds a couple of unrelated changes - I'd prefer to handle that separately. If you prefer, I can refactor the existing min/max cases into this new layout first (with existing functionality) and then fix the missing knownbits handling first?

[goldstein.w.n]

LGTM

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

2185

No, fine to leave as todo I guess.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

case ISD::ROTR: {
     if (isPowerOf2_32(BitWidth)) {
       APInt DemandedAmtBits(Op1.getScalarValueSizeInBits(), BitWidth - 1);
       if (SimplifyDemandedBits(Op1, DemandedAmtBits, DemandedElts, Known2, TLO,
                                Depth + 1))
         return true;
     }
     break;
   }
-  case ISD::SMIN: {
-    SDValue Op0 = Op.getOperand(0);
-    SDValue Op1 = Op.getOperand(1);
-    // If we're only wanting the signbit, then we can simplify to OR node.
-    // TODO: Extend this based on ComputeNumSignBits.
-    if (DemandedBits.isSignMask())
-      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, VT, Op0, Op1));
-    break;
-  }
-  case ISD::SMAX: {
-    SDValue Op0 = Op.getOperand(0);
-    SDValue Op1 = Op.getOperand(1);
-    // If we're only wanting the signbit, then we can simplify to AND node.
-    // TODO: Extend this based on ComputeNumSignBits.
-    if (DemandedBits.isSignMask())
-      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0, Op1));
-    break;
-  }
-  case ISD::UMIN: {
+  case ISD::SMIN:
+  case ISD::SMAX:
+  case ISD::UMIN:
+  case ISD::UMAX: {
+    unsigned Opc = Op.getOpcode();
     SDValue Op0 = Op.getOperand(0);
     SDValue Op1 = Op.getOperand(1);
-    // If we're only wanting the msb, then we can simplify to AND node.
-    if (DemandedBits.isSignMask())
-      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0, Op1));
-    // Check if one arg is always less than (or equal) to the other arg.
+
+    // If we're only demanding signbits, then we can simplify to OR/AND node.
+    unsigned BitOp =
+        (Opc == ISD::SMIN || Opc == ISD::UMAX) ? ISD::OR : ISD::AND;
+    unsigned NumSignBits =
+        std::min(TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1),
+                 TLO.DAG.ComputeNumSignBits(Op1, DemandedElts, Depth + 1));
+    unsigned NumDemandedUpperBits = BitWidth - DemandedBits.countr_zero();
+    if (NumSignBits >= NumDemandedUpperBits)
+      return TLO.CombineTo(Op, TLO.DAG.getNode(BitOp, SDLoc(Op), VT, Op0, Op1));
+
+    // Check if one arg is always less/greater than (or equal) to the other arg.
     KnownBits Known0 = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth + 1);
     KnownBits Known1 = TLO.DAG.computeKnownBits(Op1, DemandedElts, Depth + 1);
-    Known = KnownBits::umin(Known0, Known1);
+    switch (Opc) {
+    case ISD::SMIN:
+      // TODO: Add KnownBits::sle/slt handling.
+      break;
+    case ISD::SMAX:
+      // TODO: Add KnownBits::sge/sgt handling.
+      break;
+    case ISD::UMIN:
       if (std::optional<bool> IsULE = KnownBits::ule(Known0, Known1))
         return TLO.CombineTo(Op, *IsULE ? Op0 : Op1);
       if (std::optional<bool> IsULT = KnownBits::ult(Known0, Known1))
         return TLO.CombineTo(Op, *IsULT ? Op0 : Op1);
+      Known = KnownBits::umin(Known0, Known1);
       break;
-  }
-  case ISD::UMAX: {
-    SDValue Op0 = Op.getOperand(0);
-    SDValue Op1 = Op.getOperand(1);
-    // If we're only wanting the msb, then we can simplify to OR node.
-    if (DemandedBits.isSignMask())
-      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, VT, Op0, Op1));
-    // Check if one arg is always greater than (or equal) to the other arg.
-    KnownBits Known0 = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth + 1);
-    KnownBits Known1 = TLO.DAG.computeKnownBits(Op1, DemandedElts, Depth + 1);
-    Known = KnownBits::umax(Known0, Known1);
+    case ISD::UMAX:
       if (std::optional<bool> IsUGE = KnownBits::uge(Known0, Known1))
         return TLO.CombineTo(Op, *IsUGE ? Op0 : Op1);
       if (std::optional<bool> IsUGT = KnownBits::ugt(Known0, Known1))
         return TLO.CombineTo(Op, *IsUGT ? Op0 : Op1);
+      Known = KnownBits::umax(Known0, Known1);
+      break;
+    }
     break;
   }
   case ISD::BITREVERSE: {
     SDValue Src = Op.getOperand(0);
     APInt DemandedSrcBits = DemandedBits.reverseBits();
     if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedElts, Known2, TLO,
                              Depth + 1))
       return true;

llvm/test/CodeGen/X86/known-signbits-vector.ll

; X64-AVX2-NEXT:    retq
   %5 = shufflevector <4 x i64> %4, <4 x i64> undef, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   %6 = sitofp <4 x i64> %5 to <4 x float>
   ret <4 x float> %6
 }
 
 define <4 x i32> @signbits_mask_ashr_smax(<4 x i32> %a0, <4 x i32> %a1) {
 ; X86-LABEL: signbits_mask_ashr_smax:
 ; X86:       # %bb.0:
-; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X86-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X86-NEXT:    vpmaxsd %xmm1, %xmm0, %xmm0
+; X86-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; X86-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X86-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}, %xmm0, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-AVX1-LABEL: signbits_mask_ashr_smax:
 ; X64-AVX1:       # %bb.0:
-; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X64-AVX1-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X64-AVX1-NEXT:    vpmaxsd %xmm1, %xmm0, %xmm0
+; X64-AVX1-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX1-NEXT:    retq
 ;
 ; X64-AVX2-LABEL: signbits_mask_ashr_smax:
 ; X64-AVX2:       # %bb.0:
-; X64-AVX2-NEXT:    vmovdqa {{.*#+}} xmm2 = [25,26,27,0]
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm0, %xmm0
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm1, %xmm1
-; X64-AVX2-NEXT:    vpmaxsd %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpand %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpbroadcastd %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX2-NEXT:    retq
   %1 = ashr <4 x i32> %a0, <i32 25, i32 26, i32 27, i32 0>
   %2 = ashr <4 x i32> %a1, <i32 25, i32 26, i32 27, i32 0>
   %3 = call <4 x i32> @llvm.smax.v4i32(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <4 x i32> %3, <4 x i32> undef, <4 x i32> zeroinitializer
   %5 = ashr <4 x i32> %4, <i32 1, i32 2, i32 3, i32 4>
   %6 = and <4 x i32> %5, <i32 -32768, i32 -65536, i32 -32768, i32 -65536>
   ret <4 x i32> %6
 }
 declare <4 x i32> @llvm.smax.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 
 define <4 x i32> @signbits_mask_ashr_smin(<4 x i32> %a0, <4 x i32> %a1) {
 ; X86-LABEL: signbits_mask_ashr_smin:
 ; X86:       # %bb.0:
-; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X86-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X86-NEXT:    vpminsd %xmm1, %xmm0, %xmm0
+; X86-NEXT:    vpor %xmm1, %xmm0, %xmm0
 ; X86-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X86-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}, %xmm0, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-AVX1-LABEL: signbits_mask_ashr_smin:
 ; X64-AVX1:       # %bb.0:
-; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X64-AVX1-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X64-AVX1-NEXT:    vpminsd %xmm1, %xmm0, %xmm0
+; X64-AVX1-NEXT:    vpor %xmm1, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX1-NEXT:    retq
 ;
 ; X64-AVX2-LABEL: signbits_mask_ashr_smin:
 ; X64-AVX2:       # %bb.0:
-; X64-AVX2-NEXT:    vmovdqa {{.*#+}} xmm2 = [25,26,27,0]
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm0, %xmm0
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm1, %xmm1
-; X64-AVX2-NEXT:    vpminsd %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpor %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpbroadcastd %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX2-NEXT:    retq
   %1 = ashr <4 x i32> %a0, <i32 25, i32 26, i32 27, i32 0>
   %2 = ashr <4 x i32> %a1, <i32 25, i32 26, i32 27, i32 0>
   %3 = call <4 x i32> @llvm.smin.v4i32(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <4 x i32> %3, <4 x i32> undef, <4 x i32> zeroinitializer
   %5 = ashr <4 x i32> %4, <i32 1, i32 2, i32 3, i32 4>
   %6 = and <4 x i32> %5, <i32 -32768, i32 -65536, i32 -32768, i32 -65536>
   ret <4 x i32> %6
 }
 declare <4 x i32> @llvm.smin.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 
 define <4 x i32> @signbits_mask_ashr_umax(<4 x i32> %a0, <4 x i32> %a1) {
 ; X86-LABEL: signbits_mask_ashr_umax:
 ; X86:       # %bb.0:
-; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X86-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X86-NEXT:    vpmaxud %xmm1, %xmm0, %xmm0
+; X86-NEXT:    vpor %xmm1, %xmm0, %xmm0
 ; X86-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X86-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}, %xmm0, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-AVX1-LABEL: signbits_mask_ashr_umax:
 ; X64-AVX1:       # %bb.0:
-; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X64-AVX1-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X64-AVX1-NEXT:    vpmaxud %xmm1, %xmm0, %xmm0
+; X64-AVX1-NEXT:    vpor %xmm1, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX1-NEXT:    retq
 ;
 ; X64-AVX2-LABEL: signbits_mask_ashr_umax:
 ; X64-AVX2:       # %bb.0:
-; X64-AVX2-NEXT:    vmovdqa {{.*#+}} xmm2 = [25,26,27,0]
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm0, %xmm0
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm1, %xmm1
-; X64-AVX2-NEXT:    vpmaxud %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpor %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpbroadcastd %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX2-NEXT:    retq
   %1 = ashr <4 x i32> %a0, <i32 25, i32 26, i32 27, i32 0>
   %2 = ashr <4 x i32> %a1, <i32 25, i32 26, i32 27, i32 0>
   %3 = call <4 x i32> @llvm.umax.v4i32(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <4 x i32> %3, <4 x i32> undef, <4 x i32> zeroinitializer
   %5 = ashr <4 x i32> %4, <i32 1, i32 2, i32 3, i32 4>
   %6 = and <4 x i32> %5, <i32 -32768, i32 -65536, i32 -32768, i32 -65536>
   ret <4 x i32> %6
 }
 declare <4 x i32> @llvm.umax.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 
 define <4 x i32> @signbits_mask_ashr_umin(<4 x i32> %a0, <4 x i32> %a1) {
 ; X86-LABEL: signbits_mask_ashr_umin:
 ; X86:       # %bb.0:
-; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X86-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X86-NEXT:    vpminud %xmm1, %xmm0, %xmm0
+; X86-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; X86-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X86-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X86-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}, %xmm0, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-AVX1-LABEL: signbits_mask_ashr_umin:
 ; X64-AVX1:       # %bb.0:
-; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
-; X64-AVX1-NEXT:    vpsrad $25, %xmm1, %xmm1
-; X64-AVX1-NEXT:    vpminud %xmm1, %xmm0, %xmm0
+; X64-AVX1-NEXT:    vpand %xmm1, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[0,0,0,0]
+; X64-AVX1-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX1-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX1-NEXT:    retq
 ;
 ; X64-AVX2-LABEL: signbits_mask_ashr_umin:
 ; X64-AVX2:       # %bb.0:
-; X64-AVX2-NEXT:    vmovdqa {{.*#+}} xmm2 = [25,26,27,0]
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm0, %xmm0
-; X64-AVX2-NEXT:    vpsravd %xmm2, %xmm1, %xmm1
-; X64-AVX2-NEXT:    vpminud %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpand %xmm1, %xmm0, %xmm0
+; X64-AVX2-NEXT:    vpsrad $25, %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpbroadcastd %xmm0, %xmm0
 ; X64-AVX2-NEXT:    vpand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0, %xmm0
 ; X64-AVX2-NEXT:    retq
   %1 = ashr <4 x i32> %a0, <i32 25, i32 26, i32 27, i32 0>
   %2 = ashr <4 x i32> %a1, <i32 25, i32 26, i32 27, i32 0>
   %3 = call <4 x i32> @llvm.umin.v4i32(<4 x i32> %1, <4 x i32> %2)
   %4 = shufflevector <4 x i32> %3, <4 x i32> undef, <4 x i32> zeroinitializer
   %5 = ashr <4 x i32> %4, <i32 1, i32 2, i32 3, i32 4>