[llvm-dev] ConstantRange modelling precision?

[Philip Reames via llvm-dev]

On 12/1/19 2:52 PM, Roman Lebedev wrote:
> Hello.
>
> This question has come up in https://reviews.llvm.org/D70043
> There, i'm teaching ConstantRange how no-wrap flags affect
> the range of `mul` instruction, with end goal of exploiting
> this in LVI/CVP.
>
> There are certain combinations of ranges and no-wrap flags
> that result in always-overflowing `mul`. For example,
> `mul nuw nsw i4 [2,0), [4,0)` always overflows:
> https://rise4fun.com/Alive/1aK
> so for such ranges the ideal answer is `empty set`;
> although it wouldn't be incorrect to return a more pessimistic
> range (e.g. full-set) that contains more than the ideal result.
>
> The problem is, unlike the case of `add`, where intersection
> between plain `add` range and `saturating-[un?]signed-add`
> range already returns empty set in similar cases, here we 'need'
> to model it explicitly. (as it is seen in the patch, the modelling
> is reasonably straight-forward)
>
> As it was pointed out in the review, currently, LVI does not
> make use of empty-sets, and maps them to `overdefined`:
> https://godbolt.org/z/N3KggA
>
> So the question is: considering the fact that LVI would not
> make use of such empty-set knowledge, does that mean we
> shouldn't bother doing that extra analysis in ConstantRange,
> thus avoiding the compile time cost of said modelling?

I wouldn't support that conclusion.  I think it should always be fine 
for LVI to discard precision without making any statements about whether 
that precision is valuable in the underlying analysis.  For instance, 
are there any other transforms (say, instcombine) which can use the 
empty set information?

It would also seem reasonable to extend LVI with a notion of "empty set" 
- which on the surface seems to the same as poison. I'm not necessarily 
saying we need to, or am in a hurry to write the patches.  I'm just 
stating it would be reasonable.

One guess here is that it's the similarity to poison which causes us to 
be conservative in LVI.  Given how vague our poison/undef rules are, 
being aggressive here might expose miscompiles.  (Just a guess.)

>
> Right now i'm thinking we *should* be doing it, because:
> * Wouldn't `overdefined` lattice result in LVI giving up
>     on the users of said value, as opposed to keeping
>     propagating "incorrect" range, and thus incurring maybe
>     more compile time cost, than we would have spent
>     proving that the result is empty-set?
> * Likely LVI will make use of the knowledge later on?
> * Are there other users of ConstantRange
>    that may want this precision?
>
> Roman.