<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 12/4/19 7:27 AM, Nikita Popov wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAF+90c-2ZUCz_w5sHry1G0gcLVpYL6aJB=zGnR6Tqo=s5C36QQ@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sun, Dec 1, 2019 at 11:52
PM Roman Lebedev <<a href="mailto:lebedev.ri@gmail.com"
moz-do-not-send="true">lebedev.ri@gmail.com</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Hello.<br>
<br>
This question has come up in <a
href="https://reviews.llvm.org/D70043" rel="noreferrer"
target="_blank" moz-do-not-send="true">https://reviews.llvm.org/D70043</a><br>
There, i'm teaching ConstantRange how no-wrap flags affect<br>
the range of `mul` instruction, with end goal of exploiting<br>
this in LVI/CVP.<br>
<br>
There are certain combinations of ranges and no-wrap flags<br>
that result in always-overflowing `mul`. For example,<br>
`mul nuw nsw i4 [2,0), [4,0)` always overflows:<br>
<a href="https://rise4fun.com/Alive/1aK" rel="noreferrer"
target="_blank" moz-do-not-send="true">https://rise4fun.com/Alive/1aK</a><br>
so for such ranges the ideal answer is `empty set`;<br>
although it wouldn't be incorrect to return a more
pessimistic<br>
range (e.g. full-set) that contains more than the ideal
result.<br>
<br>
The problem is, unlike the case of `add`, where intersection<br>
between plain `add` range and `saturating-[un?]signed-add`<br>
range already returns empty set in similar cases, here we
'need'<br>
to model it explicitly. (as it is seen in the patch, the
modelling<br>
is reasonably straight-forward)<br>
<br>
As it was pointed out in the review, currently, LVI does not<br>
make use of empty-sets, and maps them to `overdefined`:<br>
<a href="https://godbolt.org/z/N3KggA" rel="noreferrer"
target="_blank" moz-do-not-send="true">https://godbolt.org/z/N3KggA</a><br>
<br>
So the question is: considering the fact that LVI would not<br>
make use of such empty-set knowledge, does that mean we<br>
shouldn't bother doing that extra analysis in ConstantRange,<br>
thus avoiding the compile time cost of said modelling?<br>
<br>
Right now i'm thinking we *should* be doing it, because:<br>
* Wouldn't `overdefined` lattice result in LVI giving up<br>
on the users of said value, as opposed to keeping<br>
propagating "incorrect" range, and thus incurring maybe<br>
more compile time cost, than we would have spent<br>
proving that the result is empty-set?<br>
* Likely LVI will make use of the knowledge later on?<br>
* Are there other users of ConstantRange<br>
that may want this precision?<br>
<br>
Roman.<br>
</blockquote>
<div><br>
</div>
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.</div>
<div class="gmail_quote"><br>
</div>
<div class="gmail_quote">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.<br>
</div>
</div>
</blockquote>
<p>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. <br>
</p>
<p>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. </p>
<p>Slightly OT - Isn't the empty set result here useful for proving
overflow (and thus removing x.with.overflow calls)? <br>
</p>
<p>Philip<br>
</p>
</body>
</html>