[llvm-dev] ConstantRange modelling precision?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] ConstantRange modelling precision?

Jimmy Zhongduo Lin via llvm-dev
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ConstantRange modelling precision?

Jimmy Zhongduo Lin 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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ConstantRange modelling precision?

Jimmy Zhongduo Lin via llvm-dev
On Tue, Dec 3, 2019 at 4:30 AM Philip Reames <[hidden email]> wrote:
>
>
> 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.
(Said patch is still eagerly awaiting review..)

> > 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.
That is my personal view, too.

> For instance,
> are there any other transforms (say, instcombine) which can use the
> empty set information?
Presently, only LVI uses `ConstantRange::overflowingBinaryOp()` interface,
and SCEV uses `ConstantRange::addWithNoWrap()` specifically.
So currently - no, nothing would immediately make use of that info.

> 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.

Roman
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ConstantRange modelling precision?

Jimmy Zhongduo Lin via llvm-dev
In reply to this post by Jimmy Zhongduo Lin via llvm-dev
On Sun, Dec 1, 2019 at 11:52 PM Roman Lebedev <[hidden email]> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] ConstantRange modelling precision?

Jimmy Zhongduo Lin via llvm-dev


On 12/4/19 7:27 AM, Nikita Popov wrote:
On Sun, Dec 1, 2019 at 11:52 PM Roman Lebedev <[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev