I have confirmed there is a bug in the recursion detection algorithm.
Well actually not a bug so much as a design fault.
When I introduced the new instantiation algorithm, S_expr started
blowing up, in particular the str function. Here is the fixed version:
instance[T with Str[T]] Str[sexpr[T]] {
noinline fun str(x:sexpr[T])=>
match x with
| Leaf ?a => str a
| Tree ?b => Str[list[sexpr[T]]]::str b
;
}
Without the "noinline" adjective this code blows up. It's not hard to guess why:
str of sexpr calls str of list which calls str of sexpr. If these were direct
calls Felix
would detect the recursion and "noinline" the function automatically.
however the calls "go through" virtual function dispatches and the Tree case
above ends up calling itself, but only after instantiation does the call become
recursive. Felix doesn't detect this. This problem should only occur when
an instance of a virtual calls the virtual in such a way that the selected
instance
is itself, which makes the function recursive. But static analysis does not
label
it recursive because that's done *before* instantiation is attempted.
The Felix inliner instantiates virtuals every chance it gets, to promote
inlining, as early as possible, but doesn't "reanalyse" the function to see if
its recursive after doing so. That would be hard because the recursion
detection is more or less a global (all functions) operation. It could only
be done for a particular function is a "what calls what map" existed and
could be modified piecemeal. Felix does try to do this so it can eliminate
functions that are "inlined away", however it isn't fully general. It is almost
impossible to do this right since inlining modifies the call graph, and it
isn't done "all at once" for a function call: the changes occur at somewhat
indeterminate points in time, and the new information is needed *during*
the inlining process (not after it is complete).
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
