[DAGCombiner] Hoist add/sub binop w/ constant op only if it won't increase divergency node

[bcl5980]

This is a general solution for regression of D148463.

[bcl5980]

update test result.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

We also want to do this if x is divergent and y is uniform.

[foad]

llvm/test/CodeGen/AMDGPU/llvm.amdgcn.s.barrier.ll

57–59

Regression

78–80

Regression

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

If x is divergent and y is uniform, we can transform to
(x + C) - y --> x + (C - y)
y - (x + C) --> (y - C) - x
(x - C) -y --> x - (C + y) ;; this is speical case that AMDGPU doesnt' support op1 as sgpr, so this case we needn't optimize it. But this should be a TLI behaivor. Generally I think we still can't enable it.
(C - x) - y --> (C -y) -x

So I believe in DAGCombiner we only need to enable it when the divergency property is the same.

[bcl5980]

llvm/test/CodeGen/AMDGPU/llvm.amdgcn.s.barrier.ll

57–59

I think the scalar instruction + vop2 instruction should save power compare to v_xad_u32. Especially the xor value is -1.
But if you insist I can try to "fix" it.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

The rules we implement in DAGCombiner should make sense without having to understand exactly what any particular target can do.

The original rule here was "pull constants out of nested adds/subs".

The new rule is "pull constants out of nested adds/subs, unless that increases the number of divergent nodes in the dag".

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

Yeah, the rule is correct. But it means (N0->isDivergent() == N1->isDivergent()) not (N0->isDivergent() || !N1->isDivergent()) I think.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

These reassociations only increase the number of divergent nodes in one case: when x is uniform and y is divergent.

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

There are 3 operators, 1 operator is uniform, 1 is divergency, 1 is constant, we can always do (uniform op constant) op divergency.
So we haven't use any particular target information here. I still think N0->isDivergent() == N1->isDivergent() is better and cleaner.
But if you insist I can change to your way.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

If you use N0->isDivergent() == N1->isDivergent() then this target independent code will not transform: (divergent op constant) op uniform into (divergent op uniform) op constant
I think it *should* do that transform, because:

1. pulling constants out is generally useful (that is why this code exists in the first place)
2. it does not increase the number of divergent nodes - both before and after the transform, there are two divergent "op" nodes

Can you explain why it should *not* do the transform?

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

But if you insist I can change to your way.

I don't want to insist, I want to reach agreement :)

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

I think it’s unnecessary because that case should be transformed to:
‘(uniform op constant) op divergent’
Hoist constant can get potential benefits but uniform instruction can get real benefits.

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

I think it’s unnecessary because that case should be transformed to:
‘(uniform op constant) op divergent’

That sounds fine but it is implemented yet (in a target-independent way)? Or can you implement it in this patch or in a follow-up?

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3903–3904

Maybe I can move D148463 into target-independent way?
I think it's OK for me to use if (N0->isDivergent() || !N1->isDivergent()) in this patch and later we can do step by step if neceassary.
And another question is do I need to fix the "regression" for v_xad_u32 before this patch?

[arsenm]

llvm/test/CodeGen/AMDGPU/llvm.amdgcn.s.barrier.ll

77

This is the kind of regression I expect out of globalisel, I'm surprised the DAG regressed here

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSUB(SDNode *N) {
   //   sub y, (xor x, -1)
   // And if the target does not like this form then turn into:
   //   add (add x, y), 1
   if (TLI.preferIncOfAddToSubOfNot(VT) && N1.hasOneUse() && isBitwiseNot(N1)) {
     SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, N1.getOperand(0));
     return DAG.getNode(ISD::ADD, DL, VT, Add, DAG.getConstant(1, DL, VT));
   }
 
-  // Hoist one-use addition by non-opaque constant:
+  // Hoist one-use addition by non-opaque constant unless it increases the
+  // number of divergent nodes:
+  if (N0.hasOneUse() && (N0->isDivergent() || !N1->isDivergent())) {
     //   (x + C) - y  ->  (x - y) + C
-  if (N0.getOpcode() == ISD::ADD && N0.hasOneUse() &&
+    if (N0.getOpcode() == ISD::ADD &&
         isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
       SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), N1);
       return DAG.getNode(ISD::ADD, DL, VT, Sub, N0.getOperand(1));
     }
-  // y - (x + C)  ->  (y - x) - C
-  if (N1.getOpcode() == ISD::ADD && N1.hasOneUse() &&
-      isConstantOrConstantVector(N1.getOperand(1), /*NoOpaques=*/true)) {
-    SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, N1.getOperand(0));
-    return DAG.getNode(ISD::SUB, DL, VT, Sub, N1.getOperand(1));
-  }
     // (x - C) - y  ->  (x - y) - C
     // This is necessary because SUB(X,C) -> ADD(X,-C) doesn't work for vectors.
-  if (N0.getOpcode() == ISD::SUB && N0.hasOneUse() &&
+    if (N0.getOpcode() == ISD::SUB &&
         isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
       SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), N1);
       return DAG.getNode(ISD::SUB, DL, VT, Sub, N0.getOperand(1));
     }
     // (C - x) - y  ->  C - (x + y)
-  if (N0.getOpcode() == ISD::SUB && N0.hasOneUse() &&
+    if (N0.getOpcode() == ISD::SUB &&
         isConstantOrConstantVector(N0.getOperand(0), /*NoOpaques=*/true)) {
       SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(1), N1);
       return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), Add);
     }
+  }
+
+  // y - (x + C)  ->  (y - x) - C
+  if (N1.getOpcode() == ISD::ADD && N1.hasOneUse() &&
+      isConstantOrConstantVector(N1.getOperand(1), /*NoOpaques=*/true) &&
+      (N1->isDivergent() || !N0->isDivergent())) {
+    SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, N1.getOperand(0));
+    return DAG.getNode(ISD::SUB, DL, VT, Sub, N1.getOperand(1));
+  }
 
   // If the target's bool is represented as 0/-1, prefer to make this 'add 0/-1'
   // rather than 'sub 0/1' (the sext should get folded).
   // sub X, (zext i1 Y) --> add X, (sext i1 Y)
   if (N1.getOpcode() == ISD::ZERO_EXTEND &&
       N1.getOperand(0).getScalarValueSizeInBits() == 1 &&
       TLI.getBooleanContents(VT) ==
           TargetLowering::ZeroOrNegativeOneBooleanContent) {
     SDValue SExt = DAG.getNode(ISD::SIGN_EXTEND, DL, VT, N1.getOperand(0));

llvm/test/CodeGen/AMDGPU/llvm.amdgcn.s.barrier.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck --check-prefix=VARIANT0 %s
 ; RUN: llc -march=amdgcn -mattr=+auto-waitcnt-before-barrier -verify-machineinstrs < %s | FileCheck --check-prefix=VARIANT1 %s
 ; RUN: llc -march=amdgcn -mcpu=gfx900 -verify-machineinstrs < %s | FileCheck --check-prefix=VARIANT2 %s
 ; RUN: llc -march=amdgcn -mcpu=gfx900 -mattr=+auto-waitcnt-before-barrier -verify-machineinstrs < %s | FileCheck --check-prefix=VARIANT3 %s
 
 define amdgpu_kernel void @test_barrier(ptr addrspace(1) %out, i32 %size) #0 {
 ; VARIANT0-LABEL: test_barrier:
 ; VARIANT0:       ; %bb.0: ; %entry
 ; VARIANT0-NEXT:    s_load_dwordx2 s[4:5], s[0:1], 0x9
 ; VARIANT0-NEXT:    s_load_dword s0, s[0:1], 0xb
 ; VARIANT0-NEXT:    s_mov_b32 s7, 0xf000
 ; VARIANT0-NEXT:    s_mov_b32 s6, 0
 ; VARIANT0-NEXT:    v_lshlrev_b32_e32 v1, 2, v0
 ; VARIANT0-NEXT:    v_mov_b32_e32 v2, 0
-; VARIANT0-NEXT:    v_not_b32_e32 v3, v0
 ; VARIANT0-NEXT:    s_waitcnt lgkmcnt(0)
 ; VARIANT0-NEXT:    buffer_store_dword v0, v[1:2], s[4:7], 0 addr64
 ; VARIANT0-NEXT:    s_waitcnt vmcnt(0) expcnt(0)
 ; VARIANT0-NEXT:    s_barrier
-; VARIANT0-NEXT:    v_add_i32_e32 v3, vcc, s0, v3
+; VARIANT0-NEXT:    s_add_i32 s0, s0, -1
+; VARIANT0-NEXT:    v_sub_i32_e32 v3, vcc, s0, v0
 ; VARIANT0-NEXT:    v_ashrrev_i32_e32 v4, 31, v3
 ; VARIANT0-NEXT:    v_lshl_b64 v[3:4], v[3:4], 2
 ; VARIANT0-NEXT:    buffer_load_dword v0, v[3:4], s[4:7], 0 addr64
 ; VARIANT0-NEXT:    s_waitcnt vmcnt(0)
 ; VARIANT0-NEXT:    buffer_store_dword v0, v[1:2], s[4:7], 0 addr64
 ; VARIANT0-NEXT:    s_endpgm
 ;
 ; VARIANT1-LABEL: test_barrier:
 ; VARIANT1:       ; %bb.0: ; %entry
 ; VARIANT1-NEXT:    s_load_dwordx2 s[4:5], s[0:1], 0x9
 ; VARIANT1-NEXT:    s_load_dword s0, s[0:1], 0xb
 ; VARIANT1-NEXT:    s_mov_b32 s7, 0xf000
 ; VARIANT1-NEXT:    s_mov_b32 s6, 0
 ; VARIANT1-NEXT:    v_lshlrev_b32_e32 v1, 2, v0
 ; VARIANT1-NEXT:    v_mov_b32_e32 v2, 0
-; VARIANT1-NEXT:    v_not_b32_e32 v3, v0
 ; VARIANT1-NEXT:    s_waitcnt lgkmcnt(0)
 ; VARIANT1-NEXT:    buffer_store_dword v0, v[1:2], s[4:7], 0 addr64
 ; VARIANT1-NEXT:    s_barrier
-; VARIANT1-NEXT:    v_add_i32_e32 v3, vcc, s0, v3
+; VARIANT1-NEXT:    s_add_i32 s0, s0, -1
+; VARIANT1-NEXT:    v_sub_i32_e32 v3, vcc, s0, v0
 ; VARIANT1-NEXT:    v_ashrrev_i32_e32 v4, 31, v3
 ; VARIANT1-NEXT:    v_lshl_b64 v[3:4], v[3:4], 2
 ; VARIANT1-NEXT:    s_waitcnt expcnt(0)
 ; VARIANT1-NEXT:    buffer_load_dword v0, v[3:4], s[4:7], 0 addr64
 ; VARIANT1-NEXT:    s_waitcnt vmcnt(0)
 ; VARIANT1-NEXT:    buffer_store_dword v0, v[1:2], s[4:7], 0 addr64
 ; VARIANT1-NEXT:    s_endpgm
 ;
 ; VARIANT2-LABEL: test_barrier:
 ; VARIANT2:       ; %bb.0: ; %entry
 ; VARIANT2-NEXT:    s_load_dwordx2 s[2:3], s[0:1], 0x24
 ; VARIANT2-NEXT:    s_load_dword s4, s[0:1], 0x2c
 ; VARIANT2-NEXT:    v_lshlrev_b32_e32 v2, 2, v0
 ; VARIANT2-NEXT:    s_waitcnt lgkmcnt(0)
 ; VARIANT2-NEXT:    global_store_dword v2, v0, s[2:3]
-; VARIANT2-NEXT:    v_xad_u32 v0, v0, -1, s4
+; VARIANT2-NEXT:    s_add_i32 s4, s4, -1
+; VARIANT2-NEXT:    v_sub_u32_e32 v0, s4, v0
 ; VARIANT2-NEXT:    v_ashrrev_i32_e32 v1, 31, v0
 ; VARIANT2-NEXT:    v_lshlrev_b64 v[0:1], 2, v[0:1]
 ; VARIANT2-NEXT:    v_mov_b32_e32 v3, s3
 ; VARIANT2-NEXT:    v_add_co_u32_e32 v0, vcc, s2, v0
 ; VARIANT2-NEXT:    v_addc_co_u32_e32 v1, vcc, v3, v1, vcc
 ; VARIANT2-NEXT:    s_waitcnt vmcnt(0)
 ; VARIANT2-NEXT:    s_barrier
 ; VARIANT2-NEXT:    global_load_dword v0, v[0:1], off
 ; VARIANT2-NEXT:    s_waitcnt vmcnt(0)
 ; VARIANT2-NEXT:    global_store_dword v2, v0, s[2:3]
 ; VARIANT2-NEXT:    s_endpgm
 ;
 ; VARIANT3-LABEL: test_barrier:
 ; VARIANT3:       ; %bb.0: ; %entry
 ; VARIANT3-NEXT:    s_load_dwordx2 s[2:3], s[0:1], 0x24
 ; VARIANT3-NEXT:    s_load_dword s4, s[0:1], 0x2c
 ; VARIANT3-NEXT:    v_lshlrev_b32_e32 v2, 2, v0
 ; VARIANT3-NEXT:    s_waitcnt lgkmcnt(0)
 ; VARIANT3-NEXT:    global_store_dword v2, v0, s[2:3]
-; VARIANT3-NEXT:    v_xad_u32 v0, v0, -1, s4
+; VARIANT3-NEXT:    s_add_i32 s4, s4, -1
+; VARIANT3-NEXT:    v_sub_u32_e32 v0, s4, v0
 ; VARIANT3-NEXT:    v_ashrrev_i32_e32 v1, 31, v0
 ; VARIANT3-NEXT:    v_lshlrev_b64 v[0:1], 2, v[0:1]
 ; VARIANT3-NEXT:    v_mov_b32_e32 v3, s3
 ; VARIANT3-NEXT:    v_add_co_u32_e32 v0, vcc, s2, v0
 ; VARIANT3-NEXT:    v_addc_co_u32_e32 v1, vcc, v3, v1, vcc
 ; VARIANT3-NEXT:    s_barrier
 ; VARIANT3-NEXT:    global_load_dword v0, v[0:1], off
 ; VARIANT3-NEXT:    s_waitcnt vmcnt(0)
 ; VARIANT3-NEXT:    global_store_dword v2, v0, s[2:3]