Re: Best Ref-counting algorithms?

On Sun, 2 Aug 2009 07:54:06 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>On Jul 30, 6:28 am, George Neuner <gneun...@comcast.net> wrote:
>> On Mon, 27 Jul 2009 11:18:56 -0700 (PDT), Christoffer Lernv
>> <le...@dragonascendant.com> wrote:
>>> In the case of an OO language with dynamic dispatch, then if I'm not
>>> mistaken it's not really possible to tell what happens to any of the
>>> arguments of a method invocation (including the object itself) at
>>> compile time.
>>
>>> It's only post-fact (when returning from the current scope) one is in
>>> a position to determine is the object will outlive the current scope
>>> or not.
>>
>> Even though the control path is not determined until run time, it is
>> still statically specified (even in Lisp where you can add/subtract
>> methods at run time). Although you don't know which control path will
>> be taken, you still know that (depending on what the language allows)
>> only actual OO objects, local structures or pointers to them can
>> possibly escape. The analysis considers the set of potential escapees
>> passed to the static method call. The actual types involved don't
>> matter, the analysis is only concerned with names.
>
>If I borrow an example from some Objective-C sample code:


      snip long example


>Can we say anything at all about the non-primitives here?


No.




>We create the objects NSString path and NSData rtfData, but both of
>those are argment for methods that has implementations that are
>determined at runtime, which means we cannot determine if the extent
>of these objects need to outlive the current scope.
>
>In fact, I cannot think of any non-trivial object usage where we can
>assert that escape is impossible, since even
>
>SomeObject *someObject = [[SomeObject alloc] init];
>
>could possibly already cause "someObject" to be registered to an
>object outside the scope of the current function.
>
>That's why I meant that there is an issue with dynamic dispatch.


It is not a problem of dynamic dispatch so much as a problem with the
implementation in Objective C. Dynamic dispatch takes 3 main forms:
messaging, class virtual functions and non-class generic functions.


Objective C objects have one entry point, a compiler generated
variadic (vararg) function which compares the message name string to a
list of recognized values and dispatches to the appropriate method.
Each method function then parses any additional arguments it needs
from the vararg list. Because of this structure there is no way to
tell which method is being called as it depends on the contents of the
character string. Even knowing which object/class is being referenced
does not help much. Smalltalk suffered from a similar defect although
its dispatch mechanism worked a bit differently.


With virtual functions (Java, C++, etc.) or with generic functions
(Lisp, etc.), the compiler can statically narrow the set of
possibilities based on the arguments and may be able to narrow the set
to only one function.




In languages like C each function is a disjoint scope - there is no
static scope chain because nested functions are not permitted. But it
is still not the case that every pointer used as a function argument
escapes the function's scope.


When you have no static scope chain, you have to follow the dynamic
scope chain by value propagation and call chain analysis ... ie. you
have to follow the values as they are passed from function to
function. If you can reach the leaves of the call tree without the
pointer escaping, then, by transitivity, it doesn't escape the
originating function's scope. Use of function pointers, of course,
screws with this analysis.


This can be done under separate compilation. For example, a function
can be analyzed statically to see which values are generated, which
are killed, which are passed to another function and which are stored
into a non-local data structure (gen-kill is normally done anyway and
the others can be added easily). The compiler can store such
inputs/outputs meta-information about the function and use it later
without needing access to the function's code.


Of course, none of this helps if you don't have the source or the
meta-information - such as with a canned library. However, in that
case, call chain analysis will fail to reach the leaves of the call
tree and so will have to assume the value(s) in question escape(s).




The point is that most languages are amenable to some kind of escape
analysis. Just because the language has dynamic dispatch is not a
reason to ignore it a priori.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.