DAG combine "and|or (select c, -1, 0), x" -> "select c, x, 0|-1"

[rampitec]

Summary

Allowed folding for "and/or" binops with non-constant operand if
arguments of select are 0/-1 values.

Normally this code with "and" opcode does not get to a DAG combiner
and simplified yet in the InstCombine. However AMDGPU produces it
during lowering and InstCombine has no chance to optimize it out.

In turn the same pattern with "or" opcode can reach DAG.

[rampitec]

Rebased.

[rampitec]

Updated x86 test after rebase.

[rampitec]

Rebased.

[rampitec]

Updated test.

[rampitec]

Rebased to master.

[rampitec]

All prerequisites are submitted, this change is ready now.

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1904–1905

This deserves an example in the comment since it doesn't match the formula below here.

Something like:
and (select Cond, 0, -1), X --> select Cond, 0, X
or X, (select Cond, -1, 0) --> select Cond, -1, X

1908–1911

This should handle vector types. Currently, it will crash:

define <4 x i32> @select_or1_vec(i32 %x, <4 x i32> %y) {
  %c = icmp slt i32 %x, 11
  %s = select i1 %c, <4 x i32> zeroinitializer, <4 x i32><i32 -1, i32 -1, i32 -1, i32 -1>
  %a = or <4 x i32> %y, %s
  ret <4 x i32> %a
}

test/CodeGen/X86/dagcombine-select.ll

12

We need some tests where the select's true value is the -1.

[rampitec]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1908–1911

Thank you!

[rampitec]

Addressed review comments.

[spatel]

LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (!isConstantOrConstantVector(CT, true) &&
     return SDValue();
 
   SDValue CF = Sel.getOperand(2);
   if (!isConstantOrConstantVector(CF, true) &&
       !isConstantFPBuildVectorOrConstantFP(CF))
     return SDValue();
 
   // Bail out if any constants are opaque because we can't constant fold those.
+  // The exception is "and" and "or" with either 0 or -1 in which case we can
+  // propagate non constant operands into select.
+  bool CanFoldNonConst = false;
+  if (BinOpcode == ISD::AND || BinOpcode == ISD::OR) {
+    ConstantSDNode *CTN = cast<ConstantSDNode>(CT);
+    ConstantSDNode *CFN = cast<ConstantSDNode>(CF);
+    CanFoldNonConst = (CTN->isNullValue() || CTN->isAllOnesValue()) &&
+                      (CFN->isNullValue() || CFN->isAllOnesValue());
+  }
+
   SDValue CBO = BO->getOperand(SelOpNo ^ 1);
-  if (!isConstantOrConstantVector(CBO, true) &&
+  if (!CanFoldNonConst &&
+      !isConstantOrConstantVector(CBO, true) &&
       !isConstantFPBuildVectorOrConstantFP(CBO))
     return SDValue();
 
   EVT VT = Sel.getValueType();
 
   // In case of shift value and shift amount may have different VT. For instance
   // on x86 shift amount is i8 regardles of LHS type. Bail out if we have
   // swapped operands and value types do not match. NB: x86 is fine if operands
   // are not swapped with shift amount VT being not bigger than shifted value.
   // TODO: that is possible to check for a shift operation, correct VTs and
   // still perform optimization on x86 if needed.
   if (SelOpNo && VT != CBO.getValueType())
     return SDValue();
 
   // We have a select-of-constants followed by a binary operator with a
   // constant. Eliminate the binop by pulling the constant math into the select.
   // Example: add (select Cond, CT, CF), CBO --> select Cond, CT + CBO, CF + CBO
   SDLoc DL(Sel);
   SDValue NewCT = SelOpNo ? DAG.getNode(BinOpcode, DL, VT, CBO, CT)
                           : DAG.getNode(BinOpcode, DL, VT, CT, CBO);
-  if (!NewCT.isUndef() &&
+  if (!CanFoldNonConst && !NewCT.isUndef() &&
       !isConstantOrConstantVector(NewCT, true) &&
       !isConstantFPBuildVectorOrConstantFP(NewCT))
     return SDValue();
 
   SDValue NewCF = SelOpNo ? DAG.getNode(BinOpcode, DL, VT, CBO, CF)
                           : DAG.getNode(BinOpcode, DL, VT, CF, CBO);
-  if (!NewCF.isUndef() &&
+  if (!CanFoldNonConst && !NewCF.isUndef() &&
       !isConstantOrConstantVector(NewCF, true) &&
       !isConstantFPBuildVectorOrConstantFP(NewCF))
     return SDValue();
 
   return DAG.getSelect(DL, VT, Sel.getOperand(0), NewCT, NewCF);
 }
 
 SDValue DAGCombiner::visitADD(SDNode *N) {

test/CodeGen/AMDGPU/dagcombine-select.ll

 ; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -enable-var-scope -check-prefix=GCN %s
 
+; GCN-LABEL: {{^}}select_and1:
+; GCN:     v_cndmask_b32_e32 [[SEL:v[0-9]+]], 0, v{{[0-9]+}},
+; GCN-NOT: v_and_b32
+; GCN:     store_dword [[SEL]],
+define amdgpu_kernel void @select_and1(i32 addrspace(1)* %p, i32 %x, i32 %y) {
+  %c = icmp slt i32 %x, 11
+  %s = select i1 %c, i32 0, i32 -1
+  %a = and i32 %y, %s
+  store i32 %a, i32 addrspace(1)* %p, align 4
+  ret void
+}
+
+; GCN-LABEL: {{^}}select_and2:
+; GCN:     v_cndmask_b32_e32 [[SEL:v[0-9]+]], 0, v{{[0-9]+}},
+; GCN-NOT: v_and_b32
+; GCN:     store_dword [[SEL]],
+define amdgpu_kernel void @select_and2(i32 addrspace(1)* %p, i32 %x, i32 %y) {
+  %c = icmp slt i32 %x, 11
+  %s = select i1 %c, i32 0, i32 -1
+  %a = and i32 %s, %y
+  store i32 %a, i32 addrspace(1)* %p, align 4
+  ret void
+}
+
+; GCN-LABEL: {{^}}select_or1:
+; GCN:     v_cndmask_b32_e32 [[SEL:v[0-9]+]], -1, v{{[0-9]+}},
+; GCN-NOT: v_or_b32
+; GCN:     store_dword [[SEL]],
+define amdgpu_kernel void @select_or1(i32 addrspace(1)* %p, i32 %x, i32 %y) {
+  %c = icmp slt i32 %x, 11
+  %s = select i1 %c, i32 0, i32 -1
+  %a = or i32 %y, %s
+  store i32 %a, i32 addrspace(1)* %p, align 4
+  ret void
+}
+
+; GCN-LABEL: {{^}}select_or2:
+; GCN:     v_cndmask_b32_e32 [[SEL:v[0-9]+]], -1, v{{[0-9]+}},
+; GCN-NOT: v_or_b32
+; GCN:     store_dword [[SEL]],
+define amdgpu_kernel void @select_or2(i32 addrspace(1)* %p, i32 %x, i32 %y) {
+  %c = icmp slt i32 %x, 11
+  %s = select i1 %c, i32 0, i32 -1
+  %a = or i32 %s, %y
+  store i32 %a, i32 addrspace(1)* %p, align 4
+  ret void
+}
+
 ; GCN-LABEL: {{^}}sel_constants_sub_constant_sel_constants:
 ; v_cndmask_b32_e64 v{{[0-9]+}}, 2, 9,
 define amdgpu_kernel void @sel_constants_sub_constant_sel_constants(i32 addrspace(1)* %p, i1 %cond) {
   %sel = select i1 %cond, i32 -4, i32 3
   %bo = sub i32 5, %sel
   store i32 %bo, i32 addrspace(1)* %p, align 4
   ret void
 }

test/CodeGen/AMDGPU/udivrem.ll

 ; EG-DAG: SUB_INT
 ; EG-DAG: CNDE_INT
 ; EG-DAG: CNDE_INT
 
 ; SI: v_rcp_iflag_f32_e32 [[RCP:v[0-9]+]]
 ; SI-DAG: v_mul_hi_u32 [[RCP_HI:v[0-9]+]], [[RCP]]
 ; SI-DAG: v_mul_lo_i32 [[RCP_LO:v[0-9]+]], [[RCP]]
 ; SI-DAG: v_sub_{{[iu]}}32_e32 [[NEG_RCP_LO:v[0-9]+]], vcc, 0, [[RCP_LO]]
-; SI: v_cndmask_b32_e64
-; SI: v_mul_hi_u32 [[E:v[0-9]+]], {{v[0-9]+}}, [[RCP]]
+; SI: v_cmp_eq_u32_e64 [[CC1:s\[[0-9:]+\]]], 0, [[RCP_HI]]
+; SI: v_cndmask_b32_e64 [[CND1:v[0-9]+]], [[RCP_LO]], [[NEG_RCP_LO]], [[CC1]]
+; SI: v_mul_hi_u32 [[E:v[0-9]+]], [[CND1]], [[RCP]]
 ; SI-DAG: v_add_{{[iu]}}32_e32 [[RCP_A_E:v[0-9]+]], vcc, [[E]], [[RCP]]
 ; SI-DAG: v_subrev_{{[iu]}}32_e32 [[RCP_S_E:v[0-9]+]], vcc, [[E]], [[RCP]]
-; SI: v_cndmask_b32_e64
-; SI: v_mul_hi_u32 [[Quotient:v[0-9]+]]
-; SI: v_mul_lo_i32 [[Num_S_Remainder:v[0-9]+]]
+; SI: v_cndmask_b32_e64 [[CND2:v[0-9]+]], [[RCP_S_E]], [[RCP_A_E]], [[CC1]]
+; SI: v_mul_hi_u32 [[Quotient:v[0-9]+]], [[CND2]],
+; SI: v_mul_lo_i32 [[Num_S_Remainder:v[0-9]+]], [[CND2]]
 ; SI-DAG: v_add_{{[iu]}}32_e32 [[Quotient_A_One:v[0-9]+]], vcc, 1, [[Quotient]]
 ; SI-DAG: v_sub_{{[iu]}}32_e32 [[Remainder:v[0-9]+]], vcc, {{[vs][0-9]+}}, [[Num_S_Remainder]]
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_subrev_{{[iu]}}32_e32 [[Quotient_S_One:v[0-9]+]],
 ; SI-DAG: v_subrev_{{[iu]}}32_e32 [[Remainder_S_Den:v[0-9]+]],
-; SI: v_and_b32_e32 [[Tmp1:v[0-9]+]]
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32 [[Remainder_A_Den:v[0-9]+]],
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
+; SI-NOT: v_and_b32
 ; SI: s_endpgm
 define amdgpu_kernel void @test_udivrem(i32 addrspace(1)* %out0, i32 addrspace(1)* %out1, i32 %x, i32 %y) {
   %result0 = udiv i32 %x, %y
   store i32 %result0, i32 addrspace(1)* %out0
   %result1 = urem i32 %x, %y
   store i32 %result1, i32 addrspace(1)* %out1
   ret void
 }

 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_and_b32_e32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_rcp_iflag_f32_e32
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_sub_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_and_b32_e32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
+; SI-NOT: v_and_b32
 ; SI: s_endpgm
 define amdgpu_kernel void @test_udivrem_v2(<2 x i32> addrspace(1)* %out, <2 x i32> %x, <2 x i32> %y) {
   %result0 = udiv <2 x i32> %x, %y
   store <2 x i32> %result0, <2 x i32> addrspace(1)* %out
   %result1 = urem <2 x i32> %x, %y
   store <2 x i32> %result1, <2 x i32> addrspace(1)* %out
   ret void
 }

 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_and_b32_e32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_rcp_iflag_f32_e32
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_sub_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_and_b32_e32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_rcp_iflag_f32_e32
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_sub_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_cndmask_b32_e64
-; SI-DAG: v_and_b32_e32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_rcp_iflag_f32_e32
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_mul_lo_i32
 ; SI-DAG: v_sub_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
 ; SI-DAG: v_mul_hi_u32
 ; SI-DAG: v_add_{{[iu]}}32_e32
 ; SI-DAG: v_subrev_{{[iu]}}32_e32
 ; SI-DAG: v_cndmask_b32_e64
+; SI-NOT: v_and_b32
 ; SI: s_endpgm
 define amdgpu_kernel void @test_udivrem_v4(<4 x i32> addrspace(1)* %out, <4 x i32> %x, <4 x i32> %y) {
   %result0 = udiv <4 x i32> %x, %y
   store <4 x i32> %result0, <4 x i32> addrspace(1)* %out
   %result1 = urem <4 x i32> %x, %y
   store <4 x i32> %result1, <4 x i32> addrspace(1)* %out
   ret void
 }

test/CodeGen/X86/dagcombine-select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=x86_64-unknown-unknown -verify-machineinstrs < %s | FileCheck -enable-var-scope %s
 
 define i32 @select_and1(i32 %x, i32 %y) {
 ; CHECK-LABEL: select_and1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $11, %edi
-; CHECK-NEXT:    setl %al
-; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    andl %esi, %eax
+; CHECK-NEXT:    cmovgel %esi, %eax
 ; CHECK-NEXT:    retq
   %c = icmp slt i32 %x, 11
   %s = select i1 %c, i32 0, i32 -1
   %a = and i32 %y, %s
   ret i32 %a
 }
 
 define i32 @select_and2(i32 %x, i32 %y) {
 ; CHECK-LABEL: select_and2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $11, %edi
-; CHECK-NEXT:    setl %al
-; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    andl %esi, %eax
+; CHECK-NEXT:    cmovgel %esi, %eax
 ; CHECK-NEXT:    retq
   %c = icmp slt i32 %x, 11
   %s = select i1 %c, i32 0, i32 -1
   %a = and i32 %s, %y
   ret i32 %a
 }
 
 define i32 @select_or1(i32 %x, i32 %y) {
 ; CHECK-LABEL: select_or1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $11, %edi
-; CHECK-NEXT:    setl %al
-; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    movl $-1, %eax
+; CHECK-NEXT:    cmovll %esi, %eax
 ; CHECK-NEXT:    retq
   %c = icmp slt i32 %x, 11
   %s = select i1 %c, i32 0, i32 -1
   %a = or i32 %y, %s
   ret i32 %a
 }
 
 define i32 @select_or2(i32 %x, i32 %y) {
 ; CHECK-LABEL: select_or2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $11, %edi
-; CHECK-NEXT:    setl %al
-; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    movl $-1, %eax
+; CHECK-NEXT:    cmovll %esi, %eax
 ; CHECK-NEXT:    retq
   %c = icmp slt i32 %x, 11
   %s = select i1 %c, i32 0, i32 -1
   %a = or i32 %s, %y
   ret i32 %a
 }
 
 define i32 @sel_constants_sub_constant_sel_constants(i1 %cond) {