[Instcombine] Canonicalize all <=> patterns to (a>b)-(a<b)

[bcl5980]

Summary

Even though this canonicalization increases one instruction, it helps to generate better backend code.
And in D143373 we have a combination on the pattern add (zext, sext). So canonicalize all select patterns to add(zext, sext).

Alive2 proof:
https://alive2.llvm.org/ce/z/RB6EEe
https://alive2.llvm.org/ce/z/EFZTwV
https://alive2.llvm.org/ce/z/ooqz8R

Fix: https://github.com/llvm/llvm-project/issues/60012

[nikic]

I think it's long overdue to canonicalize three-way comparisons in some way. Looking at asm for different backends, it does look like this representation is pretty much universally better than the select form. I'm less sure whether this is ideal for middle-end optimization.

Something I'm wondering is whether it might make sense to recognize this as a first-class pattern and actually introduce an iN @llvm.compare.iN.iM(iM %a, iM %b) intrinsic for this purpose.

[nikic]

Was this abandoned because it breaks some of the existing optimizations? For the record, this is how the compare-3way.ll test diff looks like: https://gist.github.com/nikic/056516a0d621f9ca69059d05eef7e7b2

[bcl5980]

In D145772#4192188, @nikic wrote:

Was this abandoned because it breaks some of the existing optimizations? For the record, this is how the compare-3way.ll test diff looks like: https://gist.github.com/nikic/056516a0d621f9ca69059d05eef7e7b2

Yeah, I haven't found a quick way to fix the test failures. So, I abandon it for now. Need more time to detect the canonicalized form in matchThreeWayIntCompare.

[bcl5980]

In D145772#4184090, @nikic wrote:

I think it's long overdue to canonicalize three-way comparisons in some way. Looking at asm for different backends, it does look like this representation is pretty much universally better than the select form. I'm less sure whether this is ideal for middle-end optimization.

Something I'm wondering is whether it might make sense to recognize this as a first-class pattern and actually introduce an iN @llvm.compare.iN.iM(iM %a, iM %b) intrinsic for this purpose.

I try to involve new intrinsic @llvm.compare.iN.iM and try to canonicalize the select form and extend form to the intrinsic on my local branch. It looks I get some regressions after that. Then I realize we may need more work if we canonicalize to intrinsic.
Similar to this patch, it will break all optimizations in current code. And I am not sure how to write cost model for the intrinsic. If we expand the intrinsic in SDAG, we can't detect any information cross basic block to optimize the code but I think a lot of times the 3-way comparison result will be invovled in a branch condition.

All I say here should be solvable. But I think it may need some patches to make it works. @nikic, How do you think about this ? Continue based on current patch or involve a new intrinsic like llvm.compare ?