Background
A 3-way comparison between a and b returns 1 if a > b, 0 if a == b and -1 if
a < b. Such comparisons are used in C++ via operator<=> and in Rust via the
PartialOrd and Ord traits.
Currently, there is no canonical form for how such comparisons should be represented. There are a few typical classes of representations:
- Comparison-select sequences, such as
a == b ? 0 (a < b ? -1 : 1), which is whatoperator<=>currently generates. There are a lot of variations of this general pattern, using different predicates and different select orderings. - Comparison-select sequence with extension, such as
a < b ? -1 : sext(a > b). This is the canonical form of (1) for certain choices of predicates and select orderings. - Comparison-arithmetic sequences, such as
zext(a > b) + sext(a < b).
Which of these choices produces the best codegen depends on the target. For example, option 3 is ideal for riscv32, while for many other targets it’s some variant of option 2.
The patterns also behave differently and unreliably in the middle-end optimizer. There is generally no choice that will produce optimal optimization effects in all cases, you just get different subsets.
Especially important is that patterns like (a <=> b) <= 0 fold to a <= b etc very reliably. This is currently not the case (see e.g. folds for icmp-of-sum-of-extended-i1 aren't happening in more complex code · Issue #73417 · llvm/llvm-project · GitHub for one representative issue).
Proposal
I propose to introduce two intrinsics with the following signatures:
; Returns 1 if (%a ugt %b), -1 if (%a ult %b), 0 if (%a eq %b)
iN @llvm.ucmp.iN.iM(iM %a, iM %b)
; Returns 1 if (%a sgt %b), -1 if (%a slt %b), 0 if (%a eq %b)
iN @llvm.scmp.iN.iM(iM %a, iM %b)
These return the unsigned or signed three-way comparison result of two M-bit integers into an N-bit integer result. N must be greater or equal to 2, as the result is otherwise not representable. Vector overloads must have the same number of elements for both types.
These intrinsics would ensure that there is a canonical pattern for 3-way comparisons which transforms can recognize, and targets expand into their preferred form.
Alternatives
Don’t add intrinsics
An alternative to adding intrinsics is to instead to pick some canonical form and teach optimization passes and backends about it.
A key problem with doing this is that the patterns involved are complex and fragile. It is very simple for optimizations to transform it in a way that makes it no longer a recognizable three-way comparison.
For example, a representation that uses the slt and sgt predicates might have one of the predicates canonicalized into an unsigned variant, while the other is left alone. A representation that uses ult and eq might optimize the operands of the eq comparison while leaving the ult comparison alone.
Use only one type overload
The intrinsics as proposed specify the result type separately from the input type. An alternative would be to say that the input and result types are required to be the same.
A disadvantage of this would be that 3-way comparison of booleans can not be presented using the intrinsics.
Support other types
This is not so much an alternative as an extension. I believe that integer are the most important use-case, but three-way comparisons can in principle also be supported for other primitive types.
For pointers, the llvm.ucmp and llvm.scmp intrinsics could be supported as-is, simply by also allowing pointer types in place of iM.
For floating-point numbers, the existence of NaN makes the definition of a 3-way comparison ambiguous. We could define an intrisic that returns poison for NaN inputs, but I’m not sure whether this would actually be useful to anyone.
As such, I’m open to a pointer extension, but don’t think we should support floating-point types at this time.
Implementation
I haven’t done any implementation work on this. I’m considering to offer this as a GSoC project, as it seems like a good way to get familiar with a broad slice of LLVM.