[RFC] Signedness-independent icmps

[nikic]

Motivation

When comparing two values that are known to have the same sign, signed and unsigned predicates return the same result, e.g. ult is the same as slt.

In such cases, we attempt to canonicalize the icmp to use the unsigned predicate. However, this can cause major optimization regressions in some cases: If there are multiple comparisons involving related values, and only some of them can be converted from signed to unsigned, then later optimizations may have a hard time reasoning about how these comparisons relate to each other, as they now have different signedness.

In InstCombine, we currently suppress the signed → unsigned conversion in some cases where it is likely other analyses will not be able to re-derive relevant facts. Of course, this is sub-optimal as the heuristic may fail in both directions.

Proposal

I propose to add a new icmp instruction flag samesign. If both operands of the icmp do not have the same sign, then the result is a poison value. (The name is very much up for bikeshedding, I’m really not a fan of samesign!)

As such, icmp samesign ult i8 %x, %y is equivalent to icmp samesign slt i8 %x, %y, with the former variant considered canonical.

Alternatives

Use nneg instead

A minor variant on this proposal would be to support the nneg flag on icmp instead.

This is weaker than samesign, because it does not support two negative values, but has the advantage that the nneg flag is already used by other instructions. The “both non-negative” case is a lot more common than the “both negative” case, so this probably captures most of the value of the proposal.

Introduce signedness-independent predicates instead

An alternative solution would be to introduce four new signedness-independent predicates instead: lt, le, gt and ge. These predicates indicate that the comparison can be performed in either signedness. If the signs of the values differ (or equivalently, if the results of the unsigned and signed predicates differ), the result is a poison value.

To minimize impact on code which doesn’t care, ICmpInst::getPredicate() would implicitly normalize lt to ult and so on, while a separate method would provide the raw predicate.

The advantage I see in this approach is that we can easily pass the signedness-independent predicates around in various analysis tooling. For example we can pass it to isImpliedCond() and the implementation can then decide itself as what kind of predicate it wants to treat it. Especially for APIs that deal with multiple predicates at the same time, I expect this to be a lot cleaner than passing around an extra flag.

The downside is that this is outside our usual model of poison generating flags, and will require special casing in various places, like “if-defined” instruction comparisons and flag intersection.

While this is the variant I originally wanted to propose, I think that ultimately we can get the best of both worlds by using a normal poison-generating flag in IR, but change the type returned by ICmpInst::getPredicate() to be a struct that also carries the “same sign” information. That should allow clean handling in analysis code, while using well-established concepts in IR.

[nhaehnle]

This makes sense to me.

One minor observation, which is really only about the textual IR representation: Having the shortest form of the instruction be icmp lt and have a rather unusual meaning to it (same sign, poison otherwise) feels surprising and a bit unfriendly to beginners. As a general rule, I’d say more unusual / complex instructions forms should be explicit and longer in the textual IR.

Therefore, I like the idea of explicitly writing something like icmp samesign lt (or icmp samesign ult) instead. You seem to be leaning in that direction anyway, and the CmpInst representation could theoretically make a slightly different choice (though it’s best for the textual and Value representations to match; you could argue that samesign lt is the spelling of a new predicate, but anyway, I could go either way on that).

[kparzysz]

Would it make sense to introduce a builtin for the sign of a value, and use it in an assume builtin? e.g. llvm.assume(llvm.sign(a) == llvm.sign(b)).

This would then apply to a range of instructions, not just the compares. Would this help with the analyses you mention in the motivation?

[nikic]

No, assumes don’t work for this purpose for a couple of reasons:

• Most facts are only known “up to poison”, in which case we can not emit assumes, which convert poison into immediate UB.
• Introducing assumes can degrade optimization quality and compile-time. It’s not viable to mass-introduce assumes for facts of unclear value.
• Taking information from assumes is somewhere in the middle of the “analysis sophistication scale”. It’s not as bad as using information from dominating conditions, but this is exactly the kind of context-sensitive information that less-sophisticated analysis code has a hard time recovering, and even more-sophisticated analysis code does not want to spend compile-time on.

For this purpose, it’s important to have the information directly on the icmp, so that no sophisticated/expensive context-sensitive analysis is necessary.

[tschuett]

@nikic

samesign

I like the samesign. It is the same concept as nneg. It allows us to safely undo transformations on a case by case basis.

[preames]

@tschuett

I like the samesign. It is the same concept as nneg. It allows us to safely undo transformations on a case by case basis.

I agree. As you mention, not a huge fan of the name, but don’t have anything better to suggest unfortunately.

One possible thought, should we add both nneg and samesign? nneg gives an additional value restriction (in that w know the inputs must be non negative.) I haven’t given it a lot of thought, but it seems like there must be cases where that is useful? If we wanted that as our end result, it would maybe also encourage an implementation plan which starts with ‘nneg’ first (since we have precedent for that), and that adds ‘samesign’ as a second step?

[nhaehnle]

These kinds of bits tend to be a bit of a scarce resource (in terms of available space in the Instruction class representation), so I’d rather not have both unless we already know that both are actually useful.

[nikic]

I don’t think multiple flags are really a problem from a storage perspective, because icmp currently doesn’t use any of the 7 available bits of SubclassOptionalData.

I do agree though that we probably don’t want to have both flags. Flags aren’t free in terms of maintenance effort, mainly because we have to always consider which flags to preserve when doing transforms.

[tschuett]

As I said above, samesign allows us to safely undo transformations. Adding nneg to icmp would be for optimizations.

I will also have to do some work with the new flags.

[Mohamed]

I will work on this.

[nikic]

For the record, there’s a PR to implement the samesign flag here: [IR] Add `samesign` flag to icmp instruction by elhewaty · Pull Request #111419 · llvm/llvm-project · GitHub