On Sun, 2007-03-11 at 17:36 +1100, skaller wrote:
> Almost done now ..
The infinite cloning problem is back somehow: reminder
of what happens:
fun B { fun C { call B } call C }
fun A { call B }
Here, B,C are mutually recursive. Felix only inlines
a recursive call if the callee is a child of the caller,
if the child calls the parent directly this should lead
to a recursive self-call: inlining C into B leaves:
fun B { call B }
But this is not what actually happens. When we inline B
into A we first get:
fun A { fun C' {call B} call C' }
and inlining the call to C' we get
fun A { call B }
which is right back where we started. The problem is that
C' is a clone of C, reparent to belong to A. It calls B,
which is not its parent .. A is its parent. So the call
can be inlined and we get an infinite loop.
When the call to B is a tail call, I think this
is handled: B is optimised to
fun B { call B }
first, and if that's a tail call replaced by a goto. That
happens before B is inlined into A. A realistic example:
fun B { fun C { c1; call B; c2; } b1; call C; b2; }
will result in
fun B { b1; c1; call B; c2; b2; }
So now, when A inlined B, it still doesn't work:
fun A { b1; c1; call B; c2; b2; }
and it repeats. Now this case is actually blocked from an
infinite recursion because it results in a self-call,
but if the recursion is via a sibling this will not
happen YET. Instead, Felix doesn't inline yet, because
recursive calls to a sibling aren't inlined.
The problem is back at the original example now,
where we have failed for some reason to reduce to a self-call,
then the cloning process leaves the recursive call pointing
at the original uncloned target B, and the recursion manifiests
by infinite unfolding: yet none of the unfolding calls are
recursive because when inlining the recursion is unfolded.
Just to be clear: when you inline a function, you are
'reparenting' its code and children (variables and nested
functions) to the caller. Reparenting specialises the
children both over type variables and value arguments,
and the reparented function generally refers to reparented
variables.
The exceptions are: calls to a common ancestor or ancestors
children, for example library functions -- this always includes
all globals. IN particular note B above is a global, so the
interior call to it within C is NOT remapped -- it actually
CANNOT be remapped because it would have to call C' parent
which is A, clearly the wrong thing. EXCEPT if it is a tail
call in which case it can call B' by jumping to the start
of the B' code inlined into A.
I have no serious idea how to stop this clone spawning fest
at the moment .. if anyone can suggest an algorithm
it would be interesting.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
