Page MenuHomePhabricator

[ConstantRange] Sign-flipping of signedness-invariant comparisons

Authored by lebedev.ri on Nov 6 2020, 3:06 AM.



For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.

This implements complete and precise model for all predicates, as confirmed by the brute-force tests.
(although i've conjured this some time ago, so unless i'm not seeing why the test is misleading)

In a follow-up, CVP will make use of this.

Not sure how to generalize ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate()

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 6 2020, 3:06 AM
lebedev.ri requested review of this revision.Nov 6 2020, 3:06 AM
lebedev.ri updated this revision to Diff 303403.Nov 6 2020, 4:41 AM

Ok, doesn't seem useful for SCEV.
Not sure if CVP-based fold is useful, so not really looking for review i guess.

lebedev.ri edited the summary of this revision. (Show Details)
lebedev.ri added reviewers: reames, mkazantsev, nikic.

As discussed/motivated by D111836, let's at least land the ConstantRange support.
I'd be fine landing this as-is, not sure if there is much to review here.

nikic added inline comments.Sat, Oct 30, 7:13 AM

As a drive-by note without having looked at the rest yet: I'd love to have this publicly available somewhere. Could be used in and I've wanted this on other occasions as well. Not sure where, maybe it could be a static method directly on ICmpInst?

lebedev.ri marked an inline comment as done.

Consolidated ICmpInst::compare().

nikic added inline comments.Sun, Oct 31, 1:42 AM

This implementation reads really confused to me. You should be able to reduce it to just:

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;

return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNegative());

I checked that this still passes your tests.


Use seq_inclusive() to avoid the back and forth casts?

lebedev.ri marked 2 inline comments as done.


nikic added inline comments.Sun, Oct 31, 11:03 AM

Personally I'd convert this to areInsensitiveToSignednessOfInvertedICmpPredicate(), in which case the implementation would be the direct conjugate of the above, i.e.

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;
return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNonNegative());

I believe the only difference would be in the treatment of ranges that have a single element intersection (in which case the right canonicalization is probably towards an equality comparison rather than a different sign).


Isn't it possible to drop the (ICmpInst::Predicate) casts if seq_inclusive is used?

lebedev.ri marked an inline comment as done.

Thank you for taking a look!
Improved areInsensitiveToSignednessOfICmpPredicate().


Hmm, tests suggest that said implementation is (also) precise.
I'm not seeing any obvious bugs in exhaustive test coverage,
so let's do that instead. Again, i don't really recall why this was
the way it it, perhaps i just got discouraged in non-applicability
of this in SCEV, and didn't get it fully cleaned up.


Hmm, indeed. I don't really recall why i ended up with that,
i was looking for a complex solution, so i didn't end up
converging on the simplest one.

Do not pass around srcpred in tests, NFC.

nikic accepted this revision.Sun, Oct 31, 12:35 PM

LGTM, thanks!


nit: "maybe inverted" now

Might be worth mentioning that BAD_ICMP_PREDICATE is returned on failure.


I find it slightly odd that the other two are static methods but this one is an instance method -- any particular reason for that choice?

This revision is now accepted and ready to land.Sun, Oct 31, 12:35 PM
lebedev.ri marked 2 inline comments as done.


lebedev.ri added inline comments.Sun, Oct 31, 12:50 PM

Nothing particular, but i think we are consistently inconsistent with this.
Let's go with static.

This revision was landed with ongoing or failed builds.Sun, Oct 31, 12:54 PM
This revision was automatically updated to reflect the committed changes.