[bitc-dev] Capture problem with by-ref

Swaroop Sridhar swaroop at cs.jhu.edu
Wed Mar 12 14:14:54 EDT 2008


Jonathan S. Shapiro wrote:
> On Wed, 2008-03-12 at 12:00 +0000, Sam Mason wrote:
>> On Tue, Mar 11, 2008 at 05:54:01PM -0400, Swaroop Sridhar wrote:
>>> The by-ref operator is a limited form of the address (&) operator. There
>>> is actually no problem as long as the reference does not escape its
>>> definition. 
>> Then I'm confused, I thought that was the point of shap's original
>> email---the fact that by-refs can escape.
> 
> Swaroop later corrected me, though now that I think about it again I am
> not convinced that he had it right.
> 
> Ignoring BY-REF, any stack-allocated closed-over variable is forced into
> the heap so that the stack frame is not aliased by the closure. This is
> done automatically by the compiler. Swaroop and I sometimes refer to
> this process as "heapification".

My understanding was that a by-ref argument must never introduce
heapification. In the original mail proposing by-ref (then called
stack-ref), you had stated a rule that by-ref arguments cannot escape at
all, including through the process of being captured by a closure:
http://www.coyotos.org/pipermail/bitc-dev/2007-June/000915.html


> If a by-reference parameter could be treated in all respects as an
> argument passing optimization, then it would follow that the by-ref
> parameter should be heapified in exactly the same way. When Swaroop
> argued yesterday that the [internal] make-closure operation copies its
> parameters, I think this is what he was saying. Note that this would
> eliminate the dangling reference into the stack frame that is created by
> using a BY-REF parameter.

This is actually not precise wrt what I said yesterday.  I said (or at
least meant to say) that a capture of a by-ref formal variable (x) by an
inner lambda (L) is safe only if:

(1) L does not escape,   or
(2) The body of L does not use x as an lvalue that is a target of an
     assignment.

If (1) holds, we don't have a problem since nothing escapes. However,
this requires that we perform a closure escape analysis.

If (2) holds, we only need a copy of the by-ref argument in the closure.
That is, the closure contains a de-referenced shallowly immutable
version of the by-reference argument.

> Unfortunately -- and this is the part I did not consider yesterday -- a
> BY-REF parameter CANNOT be treated in all respects as an argument
> passing optimization. In particular, a parameter of type
> 
>   (BY-REF (MUTABLE T))

True. This interpretation is possible only if (1) or (2) above hold.

> creates an alias whose presence is observable. Consider:
> 
>   (defun (f x : (mutable int32))
>     (defun (g xref: (by-ref (mutable (int32))))
>       (pair xref (begin (set! x (+ x 1)) xref)))
>     (g x))

In this case, there is no problem because condition (1) is satisfied.
The inner lambda g does not escape its scope.

If my understanding is correct, the same issue can be captured by the
following simpler example (right?). The fact that xref is an alias to x
does not matter in this case since the application of g is immediate.

(define (f x:(by-ref (mutable int32)))
    ((lambda (y) (set! x x)) #t) )

The type of the inner function is bool -> ()
The type of f is (byref (mutable int32)) -> ()

In this case, no heapification is required. The closure of the inner
lambda will contain a _stack_ pointer to x. It is still safe because the
closure does not escape beyond its caller.

However, we currently do not perform closure escape analysis, and
therefore, this example will fail to compile.

Similarly, if we wrote:
(define (f x:(by-ref (mutable int32)))
    (lambda (y) x))

it is okay because this expression satisfies (2) even though the inner
lambda escapes. Here too, no heapification is required. The closure for
the inner lambda will contain the value denoted by x's dereference.

> But the following variation is NOT okay:
> 
>   (defun (f x : (mutable int32))
>     (defun (g xref: (by-ref (mutable (int32))))
>       (pair xref (begin (set! x (+ x 1)) xref)))
>     g)
> Swaroop: can you explain again what currently happens in my second
> example? 

This case is an error because it does not satisfy any of (1) or (2).
I think that the fact that x is being set within a closure that is 
escaping is sufficient to cause a problem. (Or, is the xref alias
illustrating some other problem that I am missing?).

That is, this case should be equivalent to writing

(define (f x:(by-ref (mutable int32)))
    (lambda (y) (set! x x)))

This case currently fails to compile. It fails because of a type error.
MAKE-CLOSURE constructs a dereferenced immutable version x in the
closure environment, and the assignment (set! x x) fails to type check.
I can fix it with a better diagnostic in the closure construction pass,
by explicitly detecting it.

> I suspect that this example is actually okay, because the inner
> capture of x forces it to be heapified, and once it is heapified the
> subsequent alias created by xfef is okay.

Actually, what we need to heapify here is not x but the value whose
reference was actually passed as x. That is, we will be converting
by-refs to ordinary refs that can escape. However, this might not be
possible in all cases because we can pass members of unboxed
data-structures by-reference.

My understanding is that by-ref is really intended to mean an in-place
&-like reference. Even in places where heapification can be done, the
programmer will have no control over stack representation (as you
previously mentioned).


> Hmm. I *think* I may see what is going on here and why it is okay
> generally, but I would appreciate a clear explanation from Swaroop. Here
> is my theory:
> 
> 1. If the BY-REF emerges as a *parameter* of an escaping closure, it is
> still a parameter and no harm has been done.

Does this case refer to escape of a lambda with a by-ref argument?
For example, like:

(define (f)
    (lambda (x:(by-ref 'a)) x))

This case is definitely not a problem.

> 2. All of the problem cases arise when an inner procedure having a
> by-ref parameter is applied in such a way that the by-ref parameter
> aliases a stack-allocated variable. All such cases are syntactically
> observable, and it is possible to back-propagate the capture of the
> by-ref formal parameter onto the actual parameter.

Unfortunately, I did not fully understand this case. I don't know if
these conditions are still relevant under my new constraints for by-ref
escape. By back-propagate, do you mean back-propagation of
heapification?

> Actually, there is another tricky bit that I bet Swaroop may not have
> noticed yet.
> 
> *Because* a by-ref parameter can only escape by copy, there is an
> ill-advised but legal one-way copy compatibility:
> 
> 	(by-ref T) <- (mutable T)   ; where T is immutable
> 
> This is "safe" because (1) the resulting by-ref is strictly less mutable
> than the original parameter, and (2) it can only escape by copy, and
> 
>     T ~= (mutable T)    ; is copy compatible.
> 
> In spite of this, I do NOT think that we should allow this unification.
> In BitC, an immutable type is supposed to be immutable through any
> alias, and the compiler is entitled to assume such.  If we allow this
> unification, then in the following procedure:
> 
>   (defun (f x : (mutable int32))
>     (defun (g xref: (by-ref (mutable (int32))))
>       (pair xref (begin (set! x (+ x 1)) xref)))
>     (g x))
> 
> the compiler cannot assume that the value of xref is unchanged between
> the first and second use occurrences, because the relaxed unification
> has violated the deep immutability constraint.
> 
> For this reason, we should NOT allow this unification.
> 
> In other words, I am arguing that preservation of deep immutability is a
> safety property of the language.

I completely agree with the typing issue. We agreed that (by-ref t)
should only be compatible with t to preserve the per-location notion of
immutability.

Swaroop.



More information about the bitc-dev mailing list