On Tue, 2006-10-31 at 12:49 +1100, skaller wrote:
> On Mon, 2006-10-30 at 20:18 +1100, Jonathan Kelly wrote:
> > $ flx avl/array.flx
> > avl/array.cpp: In member function `flxusr::array::_poly_1972t_6882
> > flxusr::array::find::apply(const flxusr::array::_tt6885&)':
> > avl/array.cpp:2096: error: `ptf' undeclared (first use this function)
> > avl/array.cpp:2096: error: (Each undeclared identifier is reported only
> > once for each function it appears in.)
> >
> > plain text document attachment (array.flx)
>
> The bug is somewhere in flx_global.ipk or flx_mkclosure.ipk,
> which tracks whether the ptf (pointer to thread frame) has
> to be passed to the function. Avl::find passes it to one
> of its subroutines, but it isn't passed in to it.
This is not fixed but:
> However, looking at the generated C++ there is a much
> more serious problem: there are a lot of small subroutine
> which SHOULD have been inlined but weren't. That code
> is not only bloated, it's going to go as slow as a
> wet week.
I did fix this with a brute force hack. The code looks much
better now, should run 2x faster :)
Due to the extra inlining .. the other bug went was not
exhibited (yes, there is a bug there still).
So .. the problem was that the inliner was starting with
the roots (normally the top level init routine) and recursively
inlining into every function/procedure directly (prior to
inlining THAT function into the current one). Also every child
of a function is inlined into first, before the function is
inlined into.
This ordering is mainly to avoid inlining raw non-optimised
code into a function, then having to inline it in place ..
if there are several calls the process would be repeated.
The problem was some functions are not called directly:
they're called via closures. I tried to fix that by inlining
into the function of each closure seen .. but it didn't
seem to work. So I just added a pass that inlines into
EVERYTHING. Well, that chucked an exception in some cases,
not finding something (the inlining code removes unused
things as it goes .. again to reduce processing).
So .. I hacked it and just ignored those exceptions :)
////////////////////////////////////////////////////////////////////
It is possible this algorithm will lead to an infinite recursion.
Inlining recursive functions is tricky. Felix inlines recursive
calls to children, but not parents or siblings. This guarantees
that the process terminates.
It is also nasty: given two mutually recursive routines f and g,
often only f is called externally: in that case we should inline
g into f, eliminating it, and possibly finding a tail-rec self
call of f to results.
Felix doesn't do this. In a recursive descent inline operation
it is easy to inline into everything, stopping only when
you try to inline yourself into yourself.
The problem is that Felix doesn't just use recursive descent
down the call chain. After inlining is done on some section
of code it is rescanned for further inlining opportunities:
the rescanning IS recursive, but it is a different
recursion to the original inlining.
The PROBLEM is that when you inline a function, you have
to not only glue its code into the current function ..
you also have to glue all its children too .. variables
AND nested functions get 'reparented'. These new functions
have fresh names.. and it seems possible to go into an
infinite loop EVEN if one maintains a trail of functions
being inlined into .. because that doesn't include these
newly cloned functions.
////////////////////////////////////////////////////////////
There is an optimisation I name 'call lifting'. It works
like this:
call ( if c then f else g ) x ==>
if c then call f x else call g x
This is a distributive law of control flow. The original
form looks simpler .. but it has a serious problem:
the conditional expression has to return a closure,
either of f or of g, which is applied to f. Since we
don't know which one .. we can't inline it.
The second form only uses direct calls .. do they can
be inlined. Call lifting is vital to ensure code like:
match x with
| a => f
| _ => g
endmatch ();
is rewritten as
if x = a then f();
else g();
OK, so the problem is apply lifting isn't implemented:
thats the same distributive law again:
(if c then f else g) x ==>
if c then f x else g x
which eliminates closures in cases like:
fun p (x) = return
match x with
| a => f
| _ => g
endmatch
;
var x = (p y) z;
should make:
if y = a then x = f z;
else x = g z;
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
