[DAG] Match some basic ISD::AVGFLOORU patterns

[RKSimon]

Pulled out of Hacker's Delight, both of these are valid patterns that can be folded to ISD::AVGFLOORU (assuming the target supports it):

define i4 @fixedwidth(i4 %a0, i4 %a1)  {
  %and = and i4 %a0, %a1
  %xor = xor i4 %a0, %a1
  %srl = lshr i4 %xor, 1
  %res = add i4 %and, %srl
  ret i4 %res
}

define i4 @zext_add_extract(i4 %a0, i4 %a1)  {
  %x0 = zext i4 %a0 to i5
  %x1 = zext i4 %a1 to i5
  %sum = add i5 %x0, %x1
  %srl = lshr i5 %sum, 1
  %res = trunc i5 %srl to i4
  ret i4 %res
}

These will need aarch64 vector tests as thats the only target that has legal ISD::AVGFLOORU instructions so far.

[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. In the comments of the issue, request for it to be assigned to you.
2. Fix the issue locally.
3. 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.
4. Create a Git commit.
5. Run git clang-format HEAD~1 to format your changes.
6. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation.

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)

Pulled out of Hacker's Delight, both of these are valid patterns that can be folded to ISD::AVGFLOORU (assuming the target supports it):

define i4 @fixedwidth(i4 %a0, i4 %a1) {
%and = and i4 %a0, %a1
%xor = xor i4 %a0, %a1
%srl = lshr i4 %xor, 1
%res = add i4 %and, %srl
ret i4 %res
}

define i4 @zext_add_extract(i4 %a0, i4 %a1) {
%x0 = zext i4 %a0 to i5
%x1 = zext i4 %a1 to i5
%sum = add i5 %x0, %x1
%srl = lshr i5 %sum, 1
%res = trunc i5 %srl to i4
ret i4 %res
}

These will need aarch64 vector tests as thats the only target that has legal ISD::AVGFLOORU instructions so far.

[Sh0g0-1758]

Hey there! I would like to work on this.

[RKSimon]

combineShiftToAVG already does this for some extraction patterns, its the fixedwidth variants that we're missing entirely.

[Sh0g0-1758]

Had a few doubts.

I think this pattern gives the AVGCEIL and not AVGFLOOR as implied by the issue.

define i4 @fixedwidth(i4 %a0, i4 %a1)  {
  %and = and i4 %a0, %a1
  %xor = xor i4 %a0, %a1
  %srl = lshr i4 %xor, 1
  %res = add i4 %and, %srl
  ret i4 %res
}

And this pattern is exactly how AVGFLOORU is implemented in SelectionDAG.cpp. I wonder why we still don't support detection of this pattern. Just needed a sanity check for this whether or not I should go ahead with its pattern matching in TargetLowering.cpp.

define i4 @zext_add_extract(i4 %a0, i4 %a1)  {
  %x0 = zext i4 %a0 to i5
  %x1 = zext i4 %a1 to i5
  %sum = add i5 %x0, %x1
  %srl = lshr i5 %sum, 1
  %res = trunc i5 %srl to i4
  ret i4 %res
}

[RKSimon]

Alive2: https://alive2.llvm.org/ce/z/6Ds_br

You'd be better off implementing the fixed width cases in DAGCombine - I think combineShiftToAVG being in TargetLowering was a special case for some reason?

[Sh0g0-1758]

I see. thanks for the alive2 link. The issue is clear to me now. I will add the logic in DAGCombine and raise a PR soon.