On Wed, 2008-03-12 at 14:14 -0400, Swaroop Sridhar wrote:
> 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, your statement [2] is wrong. Counter-example:
(define (g)
(let ((local : (mutable int32) 1)
(letrec ((closure
((lambda (lref:(by-ref (mutable 'a)))
(lambda (x)
(set! lref (+ lref 1))
(+ lref x))) local)))
(pair (closure 1) (closure 1)))))
If your theory were correct, the result should be (2, 2). But it is
clear here that the outer lambda has closed over "local" by means of
application, and the correct answer must be (2, 3).
Note, however, that this capture can only occur through application, and
that it is always legal (in principle) to inline that application and
substitute the actual argument for the formal parameter. That would have
the effect of erasing the BY-REF parameter, at which point this devolves
to a capture of X. X is heapified and we are done.
That is: all we need to do here is propagate the "needs to be heapified"
marker from the formal parameter to the actual parameter.
[Note: Swaroop's example below reveals why this argument is wrong.]
I concede that this is fairly icky, but it is not conceptually
difficult.
> 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) )
This example is different, and it illustrates the real problem. The
problem here is that we cannot syntactically see the application of F,
and in consequence we cannot propagate heapification. We could heapify
conservatively wherever an argument is passed at top level to a by-ref
formal parameter, but doing that would entirely defeat the point of
adding BY-REF to the language.
So I think this brings us back to two possible rules:
SIMPLE: No captured formal parameter of BY-REF type is permitted to
escape.
REFINED: A BY-REF parameter can be captured and allowed to escape
exactly if the compiler can statically determine that the
aliased actual parameter can be heapified.
For now, I think it is best to go with the simpler rule. The refined
rule can be handled by an escape analysis pass that re-writes those
cases of BY-REF into simple REF. Since that is a backwards-compatible
relaxation of language constraints, it can be done later. Better still,
adding it later will not impact the later pass that checks the simple
rule.
> 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).
Yes.
shap
_______________________________________________
bitc-dev mailing list
bitc-dev@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
