[DAG] TargetLowering::expandABD - investigate alternative expansions

[RKSimon]

As mentioned here by @jayfoad #84431 (comment)

Incidentally Hacker's Delight has a section "Average of Two Integers" which has some neat tricks for implementing these operations without extending to N+1-bit integers.

These include alternative code for targets with poor MIN/MAX/SAT/CMPSEL instructions as well as simpler expansions depending upon the knownbits/numsignbits of the operands.

[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)

As mentioned here by @jayfoad https://github.com//pull/84431#issuecomment-1986043833

> Incidentally Hacker's Delight has a section "Average of Two Integers" which has some neat tricks for implementing these operations without extending to N+1-bit integers.

These include alternative code for targets with poor MIN/MAX/SAT/CMPSEL instructions as well as simpler expansions depending upon the knownbits/numsignbits of the operands.

[Sh0g0-1758]

Hey @RKSimon, I would like to work on this.

[changkhothuychung]

Hi I would like to work on this if this is available

[EugeneZelenko]

@changkhothuychung: Just create pull request and mention it on this page.

[Sh0g0-1758]

Does this issue aim to look at both the optimization of "Average of two integers" or only alternative code targets for absolute difference in the TargetLowering.cpp file? The description of the issue also seems a little open to me. Can you please refine it with fine-grained tasks?

In the original thread, a dev mentioned this :

Can I open a new discussion regarding a better implementation of AvgFloor and AvgCeil in TargetLowering::expandABD?

I don't see why we would want to implement AvgFloor in TargetLowering::expandABD.

If I am not wrong, the optimizations that were introduced in TargetLowering::expandAddSubSat need to be introduced in TargetLowering::expandABD.

[Sh0g0-1758]

During my findings, I found doz (difference or zero) to be a suitable alternative expansion. We can implement ABD(x,y) as :

doz(x,y) + doz(y,x)

Here is how it is defined :

And for the Average of two integers without using extra bits and ensuring no overflow, we can use :

(x&y)+((x^y)>>1)

[RKSimon]

Closing this as it references the wrong lowering code, is too broad and rather confusing - I'll create more useful smaller issues.

[Sh0g0-1758]

Right, that's what I thought, was scratching my head all morning :) Nevertheless, found some interesting resources on compiler optimization.