[llvm-dev] ConstantRange modelling precision?

[Nikita Popov via llvm-dev]

On Sun, Dec 1, 2019 at 11:52 PM Roman Lebedev <lebedev.ri at gmail.com> 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?
>
> 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.
>

To be clear: My objection here is less about computing information that we
don't presently need, and more about being precise about one very
particular thing, while much more common cases remain imprecise. The entire
"xxx with nowrap" code only produces precise ranges if the input ranges are
non-wrapping as well, because producing precise ranges for wrapping cases
is significantly more complicated and not very common in practice.

It does not make sense to me to pick out the case of an empty result set as
something that we always want to compute precisely, while still only
computing an approximation for the more common and more useful cases where
the result is non-empty. If we just happen to get this property for free
(as is the case with existing methods), that's fine. But going out of the
way to establish this even if it requires significantly more complicated
and/or slower code doesn't seem reasonable.

Nikita
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20191204/6913609d/attachment.html>