[DAG] Fold trunc(abdu(x,y)) and trunc(abds(x,y)) if they have sufficient leading zero/sign bits

[RKSimon]

https://zig.godbolt.org/z/f3ac4Moxr

SelectionDAG has 12 nodes:
  t0: ch,glue = EntryToken
          t2: v4i16,ch = CopyFromReg t0, Register:v4i16 %0
        t5: v4i32 = zero_extend t2
          t4: v4i16,ch = CopyFromReg t0, Register:v4i16 %1
        t6: v4i32 = zero_extend t4
      t13: v4i32 = abdu t5, t6
    t9: v4i16 = truncate t13
  t11: ch,glue = CopyToReg t0, Register:v4i16 $d0, t9
  t12: ch = AArch64ISD::RET_GLUE t11, Register:v4i16 $d0, t11:1

If a ABD node has sufficient leading zero/sign bits then it should still work in a truncated type - it doesn't have to be from a zext/sext node specifically so computeKnownBits/ComputeNumSignBits should probably be used.

• Create alive2 links to prove when abd patterns can be safely truncated
• Add test coverage (using aarch64 intrinsics is probably easiest as that will always start from ISD::ABDU/S nodes)
• Add suitable folds in DAGCombiner::visitTRUNCATE - including legality checks

[RKSimon]

CC @woruyu - not sure if this is of interest?

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor is working on this issue. If someone is assigned to the issue or claimed to be working on it, ping the person. After one week without a response, the assignee may be changed.
2. Leave a comment indicating that you are working on the issue, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

https://zig.godbolt.org/z/f3ac4Moxr

SelectionDAG has 12 nodes:
  t0: ch,glue = EntryToken
          t2: v4i16,ch = CopyFromReg t0, Register:v4i16 %0
        t5: v4i32 = zero_extend t2
          t4: v4i16,ch = CopyFromReg t0, Register:v4i16 %1
        t6: v4i32 = zero_extend t4
      t13: v4i32 = abdu t5, t6
    t9: v4i16 = truncate t13
  t11: ch,glue = CopyToReg t0, Register:v4i16 $d0, t9
  t12: ch = AArch64ISD::RET_GLUE t11, Register:v4i16 $d0, t11:1

If a ABD node has sufficient leading zero/sign bits then it should still work in a truncated type - it doesn't have to be from a zext/sext_extend node specifically so computeKnownBits/ComputeNumSignBits should probably be used.

• Create alive2 links to prove when abd patterns can be safely truncated
• Add test coverage (using aarch64 intrinsics is probably easiest as that will always start from ISD::ABDU/S nodes)
• Add suitable folds in DAGCombiner::visitTRUNCATE - including legality checks

[toprakmurat]

Hi! I'd like to work on this issue. Can you assign it to me?

[RKSimon]

alive2 abdu pattern: https://alive2.llvm.org/ce/z/d59BCq

define i4 @src_abdu(i16 %a0, i16 %a1) {
#0:
  %lz0 = ctlz i16 %a0, 0
  %lz1 = ctlz i16 %a1, 0
  %zz0 = icmp uge i16 %lz0, 12
  %zz1 = icmp uge i16 %lz1, 12
  assume i1 %zz0
  assume i1 %zz1
  %max = umax i16 %a0, %a1
  %min = umin i16 %a0, %a1
  %diff = sub i16 %max, %min
  %res = trunc i16 %diff to i4
  ret i4 %res
}
=>
define i4 @tgt_abdu(i16 %a0, i16 %a1) {
#0:
  %x0 = trunc i16 %a0 to i4
  %x1 = trunc i16 %a1 to i4
  %max = umax i4 %x0, %x1
  %min = umin i4 %x0, %x1
  %diff = sub i4 %max, %min
  ret i4 %diff
}
Transformation seems to be correct!

[RKSimon]

alive2 abds pattern

define i4 @src_abds(i16 %a0, i16 %a1) {
  ; representable as i4
  %t0 = trunc i16 %a0 to i4
  %t1 = trunc i16 %a1 to i4
  %x0 = sext i4 %t0 to i16
  %x1 = sext i4 %t1 to i16
  %eq0 = icmp eq i16 %x0, %a0
  %eq1 = icmp eq i16 %x1, %a1
  call void @llvm.assume(i1 %eq0)
  call void @llvm.assume(i1 %eq1)

  %max = call i16 @llvm.smax.i16(i16 %a0, i16 %a1)
  %min = call i16 @llvm.smin.i16(i16 %a0, i16 %a1)
  %diff = sub i16 %max, %min
  %res = trunc i16 %diff to i4
  ret i4 %res
}

define i4 @tgt_abds(i16 %a0, i16 %a1) {
  %x0 = trunc i16 %a0 to i4
  %x1 = trunc i16 %a1 to i4
  %max = call i4 @llvm.smax.i4(i4 %x0, i4 %x1)
  %min = call i4 @llvm.smin.i4(i4 %x0, i4 %x1)
  %diff = sub i4 %max, %min
  ret i4 %diff
}