<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
<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">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">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">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"><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">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">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">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">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">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">https://github.com/rust-lang/rust/issues/54462</a>
and <a href="https://github.com/rust-lang/rust/issues/54878">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">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">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">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">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>
</body>
</html>