[llvm-dev] ConstantRange modelling precision?

[Philip Reames via llvm-dev]

On 12/4/19 7:27 AM, Nikita Popov wrote:
> On Sun, Dec 1, 2019 at 11:52 PM Roman Lebedev <lebedev.ri at gmail.com 
> <mailto: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.

I haven't looked at the patch, but to me this whole question comes down 
to whether the code in ConstantRange is "significantly more complicated 
and/or slower".  Complexity always needs justified.

I would not use the fact we miss other common cases as a reason to 
reject a cornercase though.  We'll never be in full agreement on what's 
common - my workloads don't look like yours.  As such, that's a very 
slippery slope towards paralysis.

Slightly OT - Isn't the empty set result here useful for proving 
overflow (and thus removing x.with.overflow calls)?

Philip

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