On Thu, 31 Jan 2002, Andrew C. Greenberg wrote:
On Thursday, January 31, 2002, at 02:19 AM, Scott A Crosby wrote:
How, exactly, can I safely and in straightforward manner optimize this for any Class, when the definitions of foo1 and foo2 may well depend upon definitions in subclasses, which in turn may change? Moreover, since these kinds of expressions can be horribly complex, I would HATE if the debugger lost contexts when showing me the problem.
Actually, its not all that bad to implement. Tail recursion can be done by replacing your own context with a new one..
IE:
foo blah blah ^self bar: 12
--
What happens is when foo sees the `^bar: 12' at the end, it replaces its method context with the one for `^bar: 12'. (or, equivalently, it pops its stack frame. and pushes the new one for ^bar.)
How, exactly, do you intend to do this, with optimization, without massively rewriting the compiler? Assuming bar is inherited, we can't
One bytecode. call it a #tailSend:. Basically, it sets up the methodcontext, then 'moves' it down to replace the current methodcontext. As such, it doesn't care about the function being invoked, just the invoker.
optimize this code without recompiling foo everytime we change a bar, whether in this class or a superclass.
You don't need to change the function you're invoking. the function #bar: that gets invoked doesn't need to change and can be written as normal.
IE:
Let slook at the stack, normally, it'd go:
PARENT >> foo PARENT >> foo >> bar PARENT >> foo >> bar >> (stuff in Bar) ..... PARENT >> foo >> bar >> (stuff in Bar) PARENT >> foo >> bar PARENT >> foo PARENT
Here, we make the tailcall of bar instead:
PARENT >> foo PARENT >> bar PARENT >> bar >> (stuff in Bar) .... PARENT >> bar >> (stuff in Bar) PARENT >> bar PARENT >> bar PARENT
Which we do by replacing foo's methodcontext *completely* with bar's methodcontext, thus, for all intents and purposes, bar will think that its been invoked by PARENT, and return its result there.
This change only requires a new bytecode that replaces: send: returnTop
with a single one called tailSend:
which does the above optimization.
foo ^self bar: self. -- 9 <70> self 10 <70> self 11 <E0> send: bar: 12 <7C> returnTop
In *either* case, the code for #bar: remains completely unchanged. What changes is the last two bytecodes in #foo. Since I don't care about #bar when doing this, it doesn't matter if its inherited or where it came from. It can be a primitive, inherited, or even changed.
BTW, assume we have something like:
foo: n ^ self bar: 2*n bar: n ^ self baz: n+1 baz: n ^ n
Then, using tailcall, the stack looks like:
PARENT PARENT>>foo PARENT>>foo>>* PARENT>>foo PARENT>>bar PARENT>>bar>>+ PARENT>>bar PARENT>>baz PARENT
--
All in all, it should be an easy optimization. The only complexity there might be would depend on exactly how it builds methodcontexts... I don't know; I'm not planning on learning that till I see the new BC VM.
Scott
squeak-dev@lists.squeakfoundation.org