[AArch64][GlobalISel] HADD operations and combines

[davemgreen]

SDAG, via these nodes can pattern-recognise and optimise hadd and rhadd nodes. We should add the same operations for global isel.

  /// AVGFLOORS/AVGFLOORU - Averaging add - Add two integers using an integer of
  /// type i[N+1], halving the result by shifting it one bit right.
  /// shr(add(ext(X), ext(Y)), 1)
  AVGFLOORS,
  AVGFLOORU,
  /// AVGCEILS/AVGCEILU - Rounding averaging add - Add two integers using an
  /// integer of type i[N+2], add 1 and halve the result by shifting it one bit
  /// right. shr(add(ext(X), ext(Y), 1), 1)
  AVGCEILS,
  AVGCEILU,

There are tests in, for example, llvm/test/CodeGen/AArch64/hadd-combine.ll.
https://godbolt.org/z/xGs95MGz5

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: David Green (davemgreen)

SDAG, via these nodes can pattern-recognise and optimise hadd and rhadd nodes. We should add the same operations for global isel. ``` /// AVGFLOORS/AVGFLOORU - Averaging add - Add two integers using an integer of /// type i[N+1], halving the result by shifting it one bit right. /// shr(add(ext(X), ext(Y)), 1) AVGFLOORS, AVGFLOORU, /// AVGCEILS/AVGCEILU - Rounding averaging add - Add two integers using an /// integer of type i[N+2], add 1 and halve the result by shifting it one bit /// right. shr(add(ext(X), ext(Y), 1), 1) AVGCEILS, AVGCEILU, ```

There are tests in, for example, llvm/test/CodeGen/AArch64/hadd-combine.ll.
https://godbolt.org/z/xGs95MGz5

[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 has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, 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: David Green (davemgreen)

SDAG, via these nodes can pattern-recognise and optimise hadd and rhadd nodes. We should add the same operations for global isel. ``` /// AVGFLOORS/AVGFLOORU - Averaging add - Add two integers using an integer of /// type i[N+1], halving the result by shifting it one bit right. /// shr(add(ext(X), ext(Y)), 1) AVGFLOORS, AVGFLOORU, /// AVGCEILS/AVGCEILU - Rounding averaging add - Add two integers using an /// integer of type i[N+2], add 1 and halve the result by shifting it one bit /// right. shr(add(ext(X), ext(Y), 1), 1) AVGCEILS, AVGCEILU, ```

There are tests in, for example, llvm/test/CodeGen/AArch64/hadd-combine.ll.
https://godbolt.org/z/xGs95MGz5

[davemgreen]

I've added good first issue to this ticket, not because it is a small task but that it should be an interesting case that is relatively well understood that someone can attempt.

[Atafid]

I would like to try working on this if possible ! :)

[aemerson]

I would like to try working on this if possible ! :)

Thanks, I've assigned this to you. If you change your mind just un-assign and let us know on this thread.

[davemgreen]

Sounds good. There is a similar ticket in #118085 for abd, which added these patches to get things going:

• [GlobalISel] Add G_ABDS and G_ABDU instructions #118122
• [GlobalISel] Combine into abd[su] and legalize abd[su] #118865

I imagine something similar will be needed here (the first patch doesn't do much on it's own, they could be combined if that is helpful). There are more nodes for this ticket, but getting the non-rounding version (AVGFLOOR) going would be a good first step.

The basic pattern in SDAG is in https://github.com/llvm/llvm-project/blame/8713914d76cb9d6b54278dd75fecb68bb93f6ea5/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp#L986. That is faily complex due to requiring demanded bits. The more basic pattern is avgfloor(A, B) from trunc(shr(add(ext(A), ext(B)), 1)) and avgceil(A, B) from trunc(shr(add(ext(A), ext(B), 1), 1)). Note that we cannot convert just shr(add(A,B),1) without nsw/nuw on the add, but with them can convert as in DAGCombiner::foldShiftToAvg. There is another transform in DAGCombiner::foldAddToAvg for (A & B) + ((A ^ B) >> 1) to avgfloor(A, B).

[Atafid]

Thanks for the help ! I am currently working on it, and finished a few days ago the combine rules for avgfloors/avgfloorsu. I still have to do the legalization/lowering part for AArch64 (because I didn't find any built-in instruction, is there one ?). Unfortunately, I will not be able to work on it this week-end but I hope the first part (avgfloors/avgfloorsu) will be done next week ! :)