<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>And this is where things get complicated... <br>
</p>
My gut reaction is that inferring nonnull across function boundaries
is probably a good idea. Let me now figure out how to explain why.
:)<br>
<br>
Most of the optimizer is structured around single function
optimization. Within a single function, we typically don't cache
analysis results within the IR. Across function boundaries, we do
(e.g. readonly, readynone, etc...). Why the split? <br>
<br>
I *think* that at a high level, this comes down to a issue of
practicality. We don't have a good mechanism for accessing module
level analysis results within function transform passes. If we did,
maybe we'd have a different set of decisions here. Given we don't,
we've made the decision that function boundaries are a reasonable
place to summarize analysis results. <br>
<br>
p.s. I'll freely admit I'm out on a bit of a limb here philosophy
wise. If other folks have alternate views, I'd be very interested
in hearing them. <br>
<br>
Philip<br>
<br>
<div class="moz-cite-prefix">On 12/16/2016 12:03 PM, Sanjay Patel
wrote:<br>
</div>
<blockquote
cite="mid:CA+wODiu_sR87XEzL6tnxd34dbPE=H_5feY8xOch1f2UB1d739A@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>Based on the earlier comments in this thread and the
existence of a transform that adds 'nonnull' to callsite
params, I have proposed a patch to extend nonnull to a parent
function:<br>
<a moz-do-not-send="true"
href="https://reviews.llvm.org/D27855" target="_blank">https://reviews.llvm.org/<wbr>D27855</a><br>
</div>
...but given today's comments about inferring the analysis
rather than making it part of the IR, this might be the wrong
approach?<br>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Fri, Dec 16, 2016 at 12:49 PM,
Philip Reames via llvm-dev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><span class="">
<p><br>
</p>
<br>
<div class="m_-204715508414924075moz-cite-prefix">On
12/16/2016 11:37 AM, Michael Kuperstein wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Calling an instruction a "source" is
basically another way to say "we can't dataflow
through this".
<div><br>
<div>What I'm trying to say is that this is not
really a property of the instruction type.</div>
<div>I agree we should be adding annotations
sparingly - that is, we should not annotate
something we can infer. But that's a semantic
property, so I don't really see why that means
we should prohibit annotating certain
instructions on the syntactic level.</div>
</div>
</div>
</blockquote>
</span> I'm not opposed to this per se, but I see it as a
slippery slope argument. One of the foundational design
principles of LLVM is that analysis results are inferred
from the IR, not part of the IR. This decision is hugely
important for stability and extensibility of the
framework. If we ever got to the day where we were
putting !range on an add instruction as part of a
transform pass, that would clearly be several steps too
far.<span class=""><br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>Admittedly, the only example I have in mind
right now is the one under discussion above - if
we have:</div>
<div><br>
</div>
<div>%p = select i1 %a, i8* %x, i8 *y</div>
<div>call void foo(i8* nonnull %p)</div>
<div><br>
</div>
<div>Then after inlining foo, we lose the non-null
information for %p unless we annotate it - and we
can't propagate it through the select. The same
would happen for a phi, <br>
</div>
</div>
</blockquote>
</span> Are there cases where we loose information by
inlining this example? Yes. Are they common? I don't
know. In particular, if foo contains an unconditional
load from %p, we don't actually loose any information by
inlining. Similarly, we can frequently infer the non-null
fact from another source.<br>
<br>
Just to be clear, I want to spell out a distinction
between having metadata available for frontend annotation
and having the optimizer itself introduce metadata. The
former is a much easier request because it implies a much
smaller maintenance burden. If we screw something up
(compile time say), then only the frontend that cared
bears the cost. If we start having the optimizer itself
introduce metadata (or assumes, etc..), then the
justification has to sufficient for *all* frontends and
use cases. In practice, that's going to be a much higher
bar to clear.
<div>
<div class="h5"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra"><br>
<div class="gmail_quote">On Fri, Dec 16, 2016 at
11:25 AM, Philip Reames <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:listmail@philipreames.com"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:listmail@philipreames.com">listmail@philipreames.com</a></a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0 0 0 .8ex;border-left:1px
#ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<p>The general idea to date has been only
"sources" get annotations. If there's
something we fundamentally *can't*
analyze through, that's where we
annotate. We try not to use annotations
for places where we could have but
didn't. </p>
e.g. call metadata/attributes allow us to
model external calls, load metadata allow
us to model frontend knowledge of external
memory locations, etc..
<div>
<div class="m_-204715508414924075h5"><br>
<br>
<div
class="m_-204715508414924075m_2027015015759923768moz-cite-prefix">On
12/16/2016 11:03 AM, Michael
Kuperstein via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">By the way, I've been
wondering - why can we only attach
!nonnull and !range to loads (for
both) and call/invoke (for
!range)?
<div><br>
</div>
<div>I mean, those are all
instructions you can't do
dataflow through -
intraprocedurally, w/o memoryssa
- but why only these
instructions? Why not allow
annotating any pointer def with
!nonnull and any integer def
with !range?</div>
<div>Sure, that's redundant w.r.t
llvm.assume, but so are the
existing annotations.</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed,
Dec 14, 2016 at 11:20 PM, Hal
Finkel <span dir="ltr"><<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:hfinkel@anl.gov" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a></a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0 0 0
.8ex;border-left:1px #ccc
solid;padding-left:1ex">
<div>
<div
style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br>
<br>
<hr
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675zwchr">
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From:
</b>"Michael Kuperstein"
<<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:michael.kuperstein@gmail.com"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:michael.kuperstein@gmail.com">michael.kuperstein@gmail.com</a></a>><br>
<b>To: </b>"Hal Finkel"
<<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:hfinkel@anl.gov"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a></a>><br>
<b>Cc: </b>"Sanjay
Patel" <<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:spatel@rotateright.com"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:spatel@rotateright.com">spatel@rotateright.com</a></a>>,
"llvm-dev" <<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>>,
"Michael Kuperstein"
<<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:mkuper@google.com"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:mkuper@google.com">mkuper@google.com</a></a>><br>
<b>Sent: </b>Thursday,
December 15, 2016
1:13:07 AM<span><br>
<b>Subject: </b>Re:
[llvm-dev] analysis
based on nonnull
attribute<br>
<br>
</span><span>
<div dir="ltr">I think
what Sanjay is
getting at is that
it's not an integer,
it's still a pointer
- but it's not clear
where information
about non-nullness
of the pointer
should be propagated
to.
<div><br>
<div>In this
particular case,
since the def of
%x in the caller
is also an
argument, we
could propagate
it to the def
directly, e.g.</div>
<div><br>
</div>
<div><span
style="color:rgb(0,0,0);font-family:helvetica,arial,sans-serif;font-size:16px">define
i1 @foo(i32*
nonnull %x) {</span><br
style="color:rgb(0,0,0);font-family:helvetica,arial,sans-serif;font-size:16px">
<span
style="color:rgb(0,0,0);font-family:helvetica,arial,sans-serif;font-size:16px">
%y.i = load
i32, i32* %x
; inlined,
still known to
be nonnull</span><br>
</div>
<div><span
style="color:rgb(0,0,0);font-family:helvetica,arial,sans-serif;font-size:16px"><br>
</span></div>
And if the def of
%x was a load, we
could use
!nonnull. But I'm
not sure what we
can do in the
general case (say,
%x = select...).</div>
<div
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675DWT59679">The
best I can think
of is generating
an llvm.assume for
the condition.</div>
</div>
</span></blockquote>
True. In this case, the
preferred thing would be
to add the nonnull
attribute to the caller's
parameter. Adding
llvm.assume is indeed a
general solution.<span
class="m_-204715508414924075m_2027015015759923768HOEnZb"><font
color="#888888"><br>
<br>
-Hal</font></span>
<div>
<div
class="m_-204715508414924075m_2027015015759923768h5"><br>
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div dir="ltr">
<div><br>
</div>
<div>Michael</div>
<div
class="gmail_extra"><br>
<div
class="gmail_quote">On
14 December
2016 at 14:05,
Hal Finkel via
llvm-dev <span
dir="ltr"><<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:llvm-dev@lists.llvm.org" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>></span>
wrote:<br>
<blockquote
class="gmail_quote"
style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div>
<div
style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br>
<hr
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143zwchr">
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From:
</b>"Sanjay
Patel" <<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:spatel@rotateright.com" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:spatel@rotateright.com">spatel@rotateright.com</a></a>><br>
<b>To: </b>"Hal
Finkel" <<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:hfinkel@anl.gov" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a></a>><br>
<b>Cc: </b>"llvm-dev"
<<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>><br>
<b>Sent: </b>Wednesday,
December 14,
2016 4:03:40
PM<br>
<b>Subject: </b>Re:
[llvm-dev]
analysis based
on nonnull
attribute
<div>
<div
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051h5"><br>
<br>
<div dir="ltr"><br>
<div
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143DWT51043"
class="gmail_extra"><br>
<div
class="gmail_quote">On
Wed, Dec 14,
2016 at 2:51
PM, Hal Finkel
<span
dir="ltr"><<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:hfinkel@anl.gov" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a></a>></span>
wrote:<br>
<blockquote
class="gmail_quote"
style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div><br>
<div
style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br>
<hr
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-m_3630810500302298505zwchr">
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:helvetica,arial,sans-serif;font-size:12pt"><b>From:
</b>"Sanjay
Patel via
llvm-dev" <<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:llvm-dev@lists.llvm.org" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>><br>
<b>To: </b>"llvm-dev"
<<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-abbreviated"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a>><br>
<b>Sent: </b>Wednesday,
December 14,
2016 3:47:03
PM<br>
<b>Subject: </b>[llvm-dev]
analysis based
on nonnull
attribute<span
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-"><br>
<br>
<div
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-m_3630810500302298505DWT50626"
dir="ltr">Does
the nonnull
parameter
attribute give
us information
about
subsequent
uses of that
value outside
of the
function that
has the
attribute? <br>
</div>
</span></blockquote>
Yes. We're
guaranteeing
that we never
pass a null
value for the
argument, so
that
information
can be used to
optimize the
caller as
well.</div>
</div>
</blockquote>
<div><br>
</div>
<div>Thanks! I
don't know if
that will
actually solve
our
sub-optimal
output for
dyn_cast (!),
but it might
help...<br>
<a
moz-do-not-send="true"
class="m_-204715508414924075moz-txt-link-freetext"
href="https://llvm.org/bugs/show_"
target="_blank"><a class="moz-txt-link-freetext" href="https://llvm.org/bugs/show_">https://llvm.org/bugs/show_</a></a>bug<wbr>.cgi?id=28430<br>
</div>
<div><br>
</div>
<blockquote
class="gmail_quote"
style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div>
<div
style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><span
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-"><br>
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:helvetica,arial,sans-serif;font-size:12pt">
<div
id="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-m_3630810500302298505DWT50627"
dir="ltr"><br>
Example:<br>
<br>
define i1
@bar(i32*
nonnull %x) {
; %x must be
non-null in
this function<br>
%y = load
i32, i32* %x<br>
%z = icmp
ugt i32 %y, 23<br>
ret i1 %z<br>
}<br>
<br>
define i1
@foo(i32* %x)
{<br>
%d = call i1
@bar(i32* %x)<br>
%null_check
= icmp eq i32*
%x, null ;
check if null
after call
that
guarantees
non-null?<br>
br i1
%null_check,
label %t,
label %f<br>
t:<br>
ret i1 1<br>
f:<br>
ret i1 %d<br>
}<br>
<br>
$ opt
-inline
nonnull.ll -S<br>
...<br>
define i1
@foo(i32* %x)
{<br>
%y.i = load
i32, i32* %x
; inlined and
non-null
knowledge is
lost?<br>
</div>
</blockquote>
</span>It
should be
replaced by
!nonnull
metadata on
the load. We
might not be
doing that
today,
however.<span
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-HOEnZb"><font
color="#888888">
<div><span></span></div>
</font></span><br>
</div>
</div>
</blockquote>
<div><br>
We can't tag
this load with
!nonnull
though because
this isn't a
load of the
pointer?<br>
"The existence
of the <code
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-docutils
m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-literal"><span
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-pre">!nonnull</span></code>
metadata on
the
instruction
tells the
optimizer that
the value
loaded is
known to never
be null. This
is analogous
to the <code
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-docutils
m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-literal"><span
class="m_-204715508414924075m_2027015015759923768m_8813124120249439675m_-7730040808428572051m_-2858323345671407143gmail-pre">nonnull</span></code>
attribute on
parameters and
return values.
This metadata
can only be
applied to
loads of a
pointer type."
<br>
</div>
</div>
<br>
</div>
</div>
</div>
</div>
</blockquote>
True, but we
have range
metadata for
integers.<br>
<br>
-Hal<span><br>
<blockquote
style="border-left:2px
solid
rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div dir="ltr">
<div
class="gmail_extra"><br>
<br>
</div>
</div>
</blockquote>
<br>
<br>
<br>
-- <br>
<div><span></span>Hal
Finkel<br>
Lead, Compiler
Technology and
Programming
Languages<br>
Leadership
Computing
Facility<br>
Argonne
National
Laboratory<span></span><br>
</div>
</span></div>
</div>
<br>
______________________________<wbr>_________________<br>
LLVM
Developers
mailing list<br>
<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></a><br>
<a
moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer"
target="_blank"><a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/">http://lists.llvm.org/cgi-bin/</a><wbr>mailman/listinfo/llvm-dev</a><br>
<br>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
<br>
<br>
-- <br>
<div><span name="x"></span>Hal
Finkel<br>
Lead, Compiler
Technology and
Programming
Languages<br>
Leadership Computing
Facility<br>
Argonne National
Laboratory<span
name="x"></span><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset
class="m_-204715508414924075m_2027015015759923768mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a moz-do-not-send="true" class="m_-204715508414924075m_2027015015759923768moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true" class="m_-204715508414924075m_2027015015759923768moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</div></div></div>
</blockquote></div>
</div></div>
</blockquote>
</div></div></div>
______________________________<wbr>_________________
LLVM Developers mailing list
<a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a moz-do-not-send="true" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</blockquote></div>
</div>
</blockquote>
</body></html>