<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>The consensus in the responses to my previous email was that we
should go ahead and redefine dereferenceable to mean
dereferenceable at the point-in-time the instruction executes
(i.e. my option 2 below). I finally got the patch which does this
posted for review. Interested readers should see
<a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D110745">https://reviews.llvm.org/D110745</a>.</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 7/12/21 9:04 AM, Philip Reames
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:2252cb4f-4acd-8006-1164-ad277992f21f@philipreames.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<p>At this point, I find myself needing to declare that the
proposal below is a failure, and ask the community what next
steps we'd prefer.</p>
<p>This effort stumbled into the fact that we don't seem to have
any actual agreement on what the semantics of various attributes
are. In particular, the semantics of nofree don't appear to be
in a usable state, and my attempts at driving consensus have
failed. I am not willing to continue investing effort in that
direction. <br>
</p>
<p>Given that, I see three options, and need input from the
community as to which we should chose.</p>
<p>Option 1 - Back out the couple of changes which have landed,
update LangRef to be explicit about the scoped
dereferenceability we had historically, and consider this effort
a failure. <br>
</p>
<p>Option 2 - Change the semantic of the attributes to the point
in time semantic *without* attempting any further inference of
the scoped semantics. At the current moment, the Java use case
is covered (via the GC rule), no one seems to care about the
lost optimization power for C/C++, and I am unclear on the
practical impact (if any) on rust. <br>
</p>
<p>Option 3 - Introduce a new 'nofreeobj' attribute whose
semantics would be specifically that an object is not freed in
the dynamic scope of the function through any mechanism
(including concurrency). This attribute would be basically
uninferrable, and would exist only to support language
guarantees being encoded by frontends. <br>
</p>
<p>My recommendation would be for option 2, than 3, than 1. It's
worth noting that we could also chose option 2, then implement
option 3 lazily if anyone reports a practical performance
regression. <br>
</p>
<p>Philip</p>
<div class="moz-cite-prefix">On 3/17/21 2:22 PM, Philip Reames via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:2cdbc4a6-a31c-4323-cab8-38eab9e49766@philipreames.com">
<meta http-equiv="content-type" content="text/html;
charset=UTF-8">
<p>TLDR: We should change the existing dereferenceability
related attributes to imply point in time facts only, and
re-infer stronger global dereferenceability facts where
needed.</p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id1"
moz-do-not-send="true">Meta</a></h2>
<p>If you prefer to read proposals in a browser, you can read
this email <a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst"
moz-do-not-send="true">here</a>.</p>
<p>This proposal greatly benefited from multiple rounds of
feedback from Johannes, Artur, and Nick. All remaining
mistakes are my own.</p>
<p>Johannes deserves a lot of credit for driving previous
iterations on this design. In particular, I want to note that
we've basically returned to something Johannes first proposed
several years ago, before we had specified the nofree
attribute family.</p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id2"
moz-do-not-send="true">The Basic Problem</a></h2>
<p>We have a long standing semantic problem with the way we
define dereferenceability facts which makes it difficult to
express C++ references, or more generally, dereferenceability
on objects which may be freed at some point in the program.
The current structure does lend itself well to memory which
can't be freed. As discussed in detail a bit later, we want to
seamlessly support both use cases.</p>
<p>The basic statement of the problem is that a piece of memory
marked with deref(N) is assumed to remain dereferenceable
indefinitely. For an object which can be freed, marking it as
deref can enable unsound transformations in cases like the
following:</p>
<pre>o = deref(N) alloc();
if (c) free(o)
while(true) {
if (c) break;
// With the current semantics, we will hoist o.f above the loop
v = o.f;
}
</pre>
<p>Despite this, Clang does emit the existing dereferenceable
attribute in some problematic cases. We have observed
miscompiles as a result, and optimizer has an assortment of
hacks to try not to be too aggressive and miscompile too
widely.<a id="user-content-havent-we-already-solved-this"
class="anchor" aria-hidden="true"
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#havent-we-already-solved-this"
moz-do-not-send="true"><svg class="octicon octicon-link"
viewBox="0 0 16 16" width="16" height="16"
aria-hidden="true"></svg></a></p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id3"
moz-do-not-send="true">Haven't we already solved this?</a></h2>
<p>This has been discussed relatively extensively in the past,
included an accepted review (<a
href="https://reviews.llvm.org/D61652" rel="nofollow"
moz-do-not-send="true">https://reviews.llvm.org/D61652</a>)
which proposed splitting the dereferenceable attribute into
two to adress this. However, this change never landed and
recent findings reveal that we both need a broader solution,
and have an interesting oppurtunity to take advantage of other
recent work.</p>
<p>The need for a broader solution comes from the observation
that deref(N) is not the only attribute with this problem.
deref_or_null(N) is a fairly obvious case we'd known about
with the previous proposal, but it was recently realized that
other allocation related facts have this problem as well. We
now have specific examples with allocsize(N,M) - and the baked
in variants in MemoryBuiltins - and suspect there are other
attributes, either current or future, with the same challenge.</p>
<p>The opportunity comes from the addition of "nofree"
attribute. Up until recently, we really didn't have a good
notion of "free"ing an allocation in the abstract machine
model. We used to comingle this with our notion of capture.
(i.e. We'd assume that functions which could free must also
capture.) With the explicit notion of "nofree", we have an
approach available to us we didn't before.</p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id4"
moz-do-not-send="true">The Proposal Itself</a></h2>
<p>The basic idea is that we're going to redefine the currently
globally scoped attributes (deref, deref_or_null, and
allocsize) such that they imply a point in time fact only and
then combine that with nofree to recover the previous global
semantics.</p>
<p>More specifically:</p>
<ul>
<li>A deref attribute on a function parameter will imply that
the memory is dereferenceable for a specified number of
bytes at the instant the function call occurs.</li>
<li>A deref attribute on a function return will imply that the
memory is dereferenceable at the moment of return.</li>
</ul>
<p>We will then use the point in time fact combined with other
information to drive inference of the global facts. While in
principle we may loose optimization potential, we believe this
is sufficient to infer the global facts in all practical cases
we care about.</p>
<p>Sample inference cases:</p>
<ul>
<li>A deref(N) argument to a function with the nofree and
nosync function attribute is known to be globally
dereferenceable within the scope of the function call. We
need the nosync to ensure that no other thread is freeing
the memory on behalf of the callee in a coordinated manner.</li>
<li>An argument with the attributes deref(N), noalias, and
nofree is known to be globally dereferenceable within the
scope of the function call. This relies on the fact that
free is modeled as writing to the memory freed, and thus
noalias ensures there is no other argument which can be
freed. (See discussion below.)</li>
<li>A memory allocation in a function with a garbage collector
which guarantees collection occurs only at explicit
safepoints and uses the gc.statepoint infrastructure, is
known to be globally dereferenceable if there are no calls
to gc.statepoint anywhere in the module. This effectively
refines the abstract machine model used for garbage
collection before lowering by RS4GC to disallow explicit
deallocation (for collectors which opt in).</li>
</ul>
<p>The items above are described in terms of deref(N) for ease
of description. The other attributes are handle analogously.</p>
<p><strong>Explanation</strong></p>
<p>The "deref(N), noalias, + nofree" argument case requires a
bit of explanation as it involves a bunch of subtleties.</p>
<p>First, the current wording of nofree argument attribute
implies that the callee can not arrange for another thread to
free the object on it's behalf. This is different than the
specification of the nofree function attribute. There is no
"nosync" equivalent for function attributes.</p>
<p>Second, the noalias argument attribute is subtle. There's a
couple of sub-cases worth discussing:</p>
<ul>
<li>If the noalias argument is written to (reminder: free is
modeled as a write), then it must be the only copy of the
pointer passed to the function and there can be no copies
passed through memory used in the scope of function.</li>
<li>If the noalias argument is only read from, then there may
be other copies of the pointer. However, all of those copies
must also be read only. If the object was freed through one
of those other copies, then we must have at least one
writeable copy and having the noalias on the read copy was
undefined behavior to begin with.</li>
</ul>
<p>Essentially, what we're doing with noalias is using it to
promote a fact about the pointer to a fact about the object
being pointed to. Code structure wise, we should probably
write it exactly that way.</p>
<p><strong>Result</strong></p>
<p>It's important to acknowledge that with this change, we will
lose the ability to specify global dereferenceability of
arguments and return values in the general case. We believe
the current proposal allows us to recover that fact for all
interesting cases, but if we've missed an important use case
we may need to iterate a bit.</p>
<p>We've discussed a few alternatives (below) which could be
revisited if it turns out we are missing an important use
case.</p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id5"
moz-do-not-send="true">Use Cases</a></h2>
<p><strong>C++ References</strong> -- A C++ reference implies
that the value pointed to is dereferenceable at point of
declaration, and that the reference itself is non-null. Of
particular note, an object pointed to through a reference can
be freed without introducing UB.</p>
<div class="highlight highlight-source-c++">
<pre><span class="pl-k">class</span> <span class="pl-en">A</span> { <span class="pl-k">int</span> f; };
<span class="pl-k">void</span> <span class="pl-en">ugly_delete</span>(A &a) { <span class="pl-k">delete</span> &a; }
<span class="pl-en">ugly_delete</span>(*<span class="pl-k">new</span> A());
<span class="pl-k">void</span> <span class="pl-en">ugly_delete2</span>(A &a, A *a2) {
<span class="pl-k">if</span> (unknown)
<span class="pl-c"><span class="pl-c">//</span> a.f can be *proven* deref here as it's deref on entry,</span>
<span class="pl-c"><span class="pl-c">//</span> and no free on path from entry to here.</span>
x = a.<span class="pl-smi">f</span>;
<span class="pl-k">delete</span> a2;
}
<span class="pl-k">auto</span> *a = <span class="pl-k">new</span> A();
<span class="pl-en">ugly_delete2</span>(*a, a);
A &<span class="pl-en">foo</span>() {...}
A &a = foo();
<span class="pl-k">if</span> (unknown)
<span class="pl-k">delete</span> b;
<span class="pl-c"><span class="pl-c">//</span> If a and b point to the same object, a.f may not be deref here</span>
<span class="pl-k">if</span> (unknown2)
a.f;</pre>
</div>
<p><strong>Garbage Collected Objects (Java)</strong> -- LLVM
supports two models of GCed objects, the abstract machine and
the physical machine model. The later is essentially the same
as that for c++ as deallocation points (at safepoints) are
explicit. The former has objects conceptually live forever
(i.e. reclaimation is handled outside the model).</p>
<div class="highlight highlight-source-java">
<pre><span class="pl-k">class</span> <span class="pl-en">A</span> { <span class="pl-k">int</span> f; }
<span class="pl-k">void</span> foo(<span class="pl-smi">A</span> a) {
<span class="pl-c1">...</span>
<span class="pl-c"><span class="pl-c">//</span> a.f is trivially deref anywhere in foo</span>
x <span class="pl-k">=</span> a<span class="pl-k">.</span>f;
}
<span class="pl-smi">A</span> a <span class="pl-k">=</span> <span class="pl-k">new</span> <span class="pl-smi">A</span>();
<span class="pl-c1">...</span>
<span class="pl-c"><span class="pl-c">//</span> a.f is trivially deref following it's definition</span>
x <span class="pl-k">=</span> a<span class="pl-k">.</span>f;
<span class="pl-smi">A</span> foo();
a <span class="pl-k">=</span> foo();
<span class="pl-c1">...</span>
<span class="pl-c"><span class="pl-c">//</span> a.f is (still) trivially deref</span>
x <span class="pl-k">=</span> a<span class="pl-k">.</span>f;</pre>
</div>
<p><strong>Rust Borrows</strong> -- A rust reference argument
(e.g. "borrow") points to an object whose lifetime is
guaranteed to be longer than the reference's defining scope.
As such, the object is dereferenceable through the scope of
the function. Today, rustc does emit a dereferenceable
attribute using the current globally dereferenceable semantic.</p>
<div class="highlight highlight-source-rust">
<pre><span class="pl-k">pub</span> <span class="pl-k">fn</span> <span class="pl-en">square</span>(num: <span class="pl-k">&</span><span class="pl-k">i32</span>) -> <span class="pl-k">i32</span> {
num <span class="pl-k">*</span> num
}
<span class="pl-en">square</span>(<span class="pl-k">&</span><span class="pl-c1">5</span>);
<span class="pl-c">// a could be noalias, but isn't today</span>
<span class="pl-k">pub</span> <span class="pl-k">fn</span> <span class="pl-en">bar</span>(a: <span class="pl-k">&</span><span class="pl-k">mut</span> <span class="pl-k">i32</span>, b: <span class="pl-k">&</span><span class="pl-k">i32</span>) {
<span class="pl-k">*</span>a <span class="pl-k">=</span> a <span class="pl-k">*</span> b
}
<span class="pl-en">bar</span>(<span class="pl-k">&</span><span class="pl-k">mut</span> <span class="pl-c1">5</span>, <span class="pl-k">&</span><span class="pl-c1">2</span>);
<span class="pl-c">// At first appearance, rust does not allow returning references. So return</span>
<span class="pl-c">// attributes are not relevant. This seems like a major language hole, so this</span>
<span class="pl-c">// should probably be checked with a language expert.</span></pre>
</div>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id6"
moz-do-not-send="true">Migration</a></h2>
<p>Existing bytecode will be upgraded to the weaker non-global
semantics. This provides forward compatibility, but does lose
optimization potential for previously compiled bytecode.</p>
<p>C++ and GC'd language frontends don't change.</p>
<p>Rustc should emit noalias where possible. In particular, 'a'
in the case 'bar' above is currently not marked noalias and
results in lost optimization potential as a result of this
change. According to the rustc code, this is legal, but
currently blocked on a noalias related miscompile. See <a
href="https://github.com/rust-lang/rust/issues/54462"
moz-do-not-send="true">https://github.com/rust-lang/rust/issues/54462</a>
and <a href="https://github.com/rust-lang/rust/issues/54878"
moz-do-not-send="true">https://github.com/rust-lang/rust/issues/54878</a>
for further details. (My current belief is that all llvm side
blockers have been resolved.)</p>
<p>Frontends which want the global semantics should emit
noalias, nofree, and nosync where appropriate. If this is not
enough to recover optimizations in common cases, please
explain why not. It's possible we've failed to account for
something.</p>
<h2><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id7"
moz-do-not-send="true">Alternative Designs</a></h2>
<p>All of the alternate designs listed focus on recovering the
full global deref semantics. Our hope is that any common case
we've missed can be resolved with additional inference rules
instead.</p>
<h3><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id8"
moz-do-not-send="true">Extend nofree to object semantics</a></h3>
<p>The nofree argument attribute current describes whether an
object can freed through some particular copy of the pointer.
We could strength the semantics to imply that the object is
not freed through any copy of the pointer in the specified
scope.</p>
<p>Doing so greatly weakens our ability to infer the nofree
property. The current nofree property when combined with
capture tracking in the caller is enough to prove interest
deref facts over calls. We don't want to loose the ability to
infer that since it enables interesting transforms (such as
code reordering over calls).</p>
<h3><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id9"
moz-do-not-send="true">Add a separate nofreeobj attribute</a></h3>
<p>Rather than change nofree, we could add a parallel attribute
with the stronger object property. This - combined with
deref(N) as a point in time fact - would be enough to recover
the current globally deferenceable semantics.</p>
<p>The downside of this alternative is a) possible overkill, and
b) the "ugly" factor of having two similar but not quite
identical attributes.</p>
<h3><a
href="https://github.com/preames/public-notes/blob/master/deref+nofree.rst#id10"
moz-do-not-send="true">Add an orthogonal attribute to
promote pointer facts to object ones</a></h3>
<p>To address the weakness of the former alternative, we could
specify an attribute which strengthens arbitrary pointer facts
to object facts. Examples of current pointer facts are
attributes such as readonly, and writeonly.</p>
<p>This has not been well explored; there's a huge possible
design space here.</p>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" moz-do-not-send="true">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</blockquote>
</body>
</html>