[llvm-dev] ConstantRange modelling precision?
Philip Reames via llvm-dev
llvm-dev at lists.llvm.org
Wed Dec 4 09:23:01 PST 2019
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:
> 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:
> 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`:
> 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?
> 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)?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev