SelectionDAG: Select min/max when both are used

[arsenm]

Summary

Allow two users of the condition if the other user
is also a min/max select. i.e.

%c = icmp slt i32 %x, %y
%min = select i1 %c, i32 %x, i32 %y
%max = select i1 %c, i32 %y, i32 %x

[jmolloy]

Hi,

Generally looks fine as-is, but I think the helper can be simplified a bit.

James

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2702

I think this can be written simpler. Is it important that we bail out for > 2 users? If we have > 2 users of an icmp that are both selects, surely one would have been CSEd before now?

So we could just do:

static bool hasOnlySelectUsers(Value *Cond) {
  return std::all_of(Cond->user_begin(), Cond->user_end(), [](Value *V) {
    return isa<SelectInst>(V);
  });
}

?

[junbuml]

test/CodeGen/AMDGPU/select-i1.ll

16

You need to add your check.

[arsenm]

test/CodeGen/AMDGPU/select-i1.ll

16

This won't actually be hit because min/max isn't legal for i1

[arsenm]

r269699

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitFCmp(const User &I) {
   // further optimization, but currently FMF is only applicable to binary nodes.
   if (TM.Options.NoNaNsFPMath)
     Condition = getFCmpCodeWithoutNaN(Condition);
   EVT DestVT = DAG.getTargetLoweringInfo().getValueType(DAG.getDataLayout(),
                                                         I.getType());
   setValue(&I, DAG.getSetCC(getCurSDLoc(), DestVT, Op1, Op2, Condition));
 }
 
+// Check if the condition of the select has one use or two users that are both
+// selects with the same condition.
+bool hasMinMaxUses(const SelectInst &SI) {
+  const Value *C = SI.getCondition();
+
+  Value::const_user_iterator I = C->user_begin();
+  assert(I != C->user_end());
+
+  // One user.
+  const User *User0 = *I++;
+  if (I == C->user_end())
+    return true;
+
+  // > 2 users
+  const User *User1 = *I++;
+  if (I != C->user_end())
+    return false;
+
+  // Has a second user that is also a select.
+  const User *Other = User0 == &SI ? User1 : User0;
+  return isa<SelectInst>(Other);
+}
+
 void SelectionDAGBuilder::visitSelect(const User &I) {
   SmallVector<EVT, 4> ValueVTs;
   ComputeValueVTs(DAG.getTargetLoweringInfo(), DAG.getDataLayout(), I.getType(),
                   ValueVTs);
   unsigned NumValues = ValueVTs.size();
   if (NumValues == 0) return;
 
   SmallVector<SDValue, 4> Values(NumValues);
if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {
 
     if (Opc != ISD::DELETED_NODE &&
         (TLI.isOperationLegalOrCustom(Opc, VT) ||
          (UseScalarMinMax &&
           TLI.isOperationLegalOrCustom(Opc, VT.getScalarType()))) &&
         // If the underlying comparison instruction is used by any other
         // instruction, the consumed instructions won't be destroyed, so it is
         // not profitable to convert to a min/max.
-        cast<SelectInst>(&I)->getCondition()->hasOneUse()) {
+        hasMinMaxUses(cast<SelectInst>(I))) {
       OpCode = Opc;
       LHSVal = getValue(LHS);
       RHSVal = getValue(RHS);
       BaseOps = {};
     }
   }
 
   for (unsigned i = 0; i != NumValues; ++i) {

test/CodeGen/AMDGPU/select-i1.ll

-; RUN: llc -march=amdgcn -mcpu=SI -verify-machineinstrs < %s | FileCheck -check-prefix=SI -check-prefix=FUNC %s
+; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=SI -check-prefix=FUNC %s
 ; RUN: llc -march=amdgcn -mcpu=tonga -verify-machineinstrs < %s | FileCheck -check-prefix=SI -check-prefix=FUNC %s
 
 ; FIXME: This should go in existing select.ll test, except the current testcase there is broken on SI
 
 ; FUNC-LABEL: {{^}}select_i1:
 ; SI: v_cndmask_b32
 ; SI-NOT: v_cndmask_b32
 define void @select_i1(i1 addrspace(1)* %out, i32 %cond, i1 %a, i1 %b) nounwind {
   %cmp = icmp ugt i32 %cond, 5
   %sel = select i1 %cmp, i1 %a, i1 %b
   store i1 %sel, i1 addrspace(1)* %out, align 4
   ret void
 }
 
+; FUNC-LABEL: {{^}}s_minmax_i1:
+define void @s_minmax_i1(i1 addrspace(1)* %out, i1 %cond, i1 %a, i1 %b) nounwind {
+  %cmp = icmp slt i1 %cond, false
+  %sel = select i1 %cmp, i1 %a, i1 %b
+  store i1 %sel, i1 addrspace(1)* %out, align 4
+  ret void
+}

test/CodeGen/AMDGPU/sminmax.ll

define void @v_abs_v4i32(<4 x i32> addrspace(1)* %out, <4 x i32> addrspace(1)* %src) nounwind {
   %val = load <4 x i32>, <4 x i32> addrspace(1)* %src, align 4
   %neg = sub <4 x i32> %z3, %val
   %cond = icmp sgt <4 x i32> %val, %neg
   %res = select <4 x i1> %cond, <4 x i32> %val, <4 x i32> %neg
   %res2 = add <4 x i32> %res, %t3
   store <4 x i32> %res2, <4 x i32> addrspace(1)* %out, align 4
   ret void
 }
+
+; FUNC-LABEL: {{^}}s_min_max_i32:
+; GCN: s_load_dword [[VAL0:s[0-9]+]]
+; GCN: s_load_dword [[VAL1:s[0-9]+]]
+
+; GCN-DAG: s_min_i32 s{{[0-9]+}}, [[VAL0]], [[VAL1]]
+; GCN-DAG: s_max_i32 s{{[0-9]+}}, [[VAL0]], [[VAL1]]
+define void @s_min_max_i32(i32 addrspace(1)* %out0, i32 addrspace(1)* %out1, i32 %val0, i32 %val1) nounwind {
+  %cond0 = icmp sgt i32 %val0, %val1
+  %sel0 = select i1 %cond0, i32 %val0, i32 %val1
+  %sel1 = select i1 %cond0, i32 %val1, i32 %val0
+
+  store volatile i32 %sel0, i32 addrspace(1)* %out0, align 4
+  store volatile i32 %sel1, i32 addrspace(1)* %out1, align 4
+  ret void
+}
+
+; FUNC-LABEL: {{^}}v_min_max_i32:
+; GCN: buffer_load_dword [[VAL0:v[0-9]+]]
+; GCN: buffer_load_dword [[VAL1:v[0-9]+]]
+
+; GCN-DAG: v_min_i32_e32 v{{[0-9]+}}, [[VAL1]], [[VAL0]]
+; GCN-DAG: v_max_i32_e32 v{{[0-9]+}}, [[VAL1]], [[VAL0]]
+define void @v_min_max_i32(i32 addrspace(1)* %out0, i32 addrspace(1)* %out1, i32 addrspace(1)* %ptr0, i32 addrspace(1)* %ptr1) nounwind {
+  %val0 = load volatile i32, i32 addrspace(1)* %ptr0
+  %val1 = load volatile i32, i32 addrspace(1)* %ptr1
+
+  %cond0 = icmp sgt i32 %val0, %val1
+  %sel0 = select i1 %cond0, i32 %val0, i32 %val1
+  %sel1 = select i1 %cond0, i32 %val1, i32 %val0
+
+  store volatile i32 %sel0, i32 addrspace(1)* %out0, align 4
+  store volatile i32 %sel1, i32 addrspace(1)* %out1, align 4
+  ret void
+}
+
+; FUNC-LABEL: {{^}}s_min_max_v4i32:
+; GCN-DAG: s_min_i32
+; GCN-DAG: s_min_i32
+; GCN-DAG: s_min_i32
+; GCN-DAG: s_min_i32
+; GCN-DAG: s_max_i32
+; GCN-DAG: s_max_i32
+; GCN-DAG: s_max_i32
+; GCN-DAG: s_max_i32
+define void @s_min_max_v4i32(<4 x i32> addrspace(1)* %out0, <4 x i32> addrspace(1)* %out1, <4 x i32> %val0, <4 x i32> %val1) nounwind {
+  %cond0 = icmp sgt <4 x i32> %val0, %val1
+  %sel0 = select <4 x i1> %cond0, <4 x i32> %val0, <4 x i32> %val1
+  %sel1 = select <4 x i1> %cond0, <4 x i32> %val1, <4 x i32> %val0
+
+  store volatile <4 x i32> %sel0, <4 x i32> addrspace(1)* %out0, align 4
+  store volatile <4 x i32> %sel1, <4 x i32> addrspace(1)* %out1, align 4
+  ret void
+}
+
+; FUNC-LABEL: {{^}}v_min_max_i32_user:
+; GCN: v_cmp_gt_i32_e32
+; GCN-DAG: v_cndmask_b32_e32
+; GCN-DAG: v_cndmask_b32_e32
+; GCN-DAG: v_cndmask_b32_e64 v{{[0-9]+}}, 0, 1, vcc
+define void @v_min_max_i32_user(i32 addrspace(1)* %out0, i32 addrspace(1)* %out1, i32 addrspace(1)* %ptr0, i32 addrspace(1)* %ptr1) nounwind {
+  %val0 = load volatile i32, i32 addrspace(1)* %ptr0
+  %val1 = load volatile i32, i32 addrspace(1)* %ptr1
+
+  %cond0 = icmp sgt i32 %val0, %val1
+  %sel0 = select i1 %cond0, i32 %val0, i32 %val1
+  %sel1 = select i1 %cond0, i32 %val1, i32 %val0
+
+  store volatile i32 %sel0, i32 addrspace(1)* %out0, align 4
+  store volatile i32 %sel1, i32 addrspace(1)* %out1, align 4
+  store volatile i1 %cond0, i1 addrspace(1)* undef
+  ret void
+}