On 11/05/2014, at 12:36 AM, Shayne Fletcher wrote:
> Happy days.
>
> Target was Debian 3.2.54-2 x86_64 GNU/Linux using g++ (Debian 4.7.2-5) 4.7.2.
>
For my next project I propose to speed up the flxg compiler.
The first step is to rewrite the monomorphisation routine
and run it first, before inlining.
At present, Felix inlines, then monomorphises, then inlines again.
Felix uses a seriously slow hack to garbage collect symbols.
Fixing that will be the next step.
Monomorphisation means instantiating polymorphic entities
replacing the type variables with concrete types. In C++ this
is called specialisation.
In principle the idea is to start with some monomorphic roots
(roots are C functions so have to be monomorphic). Then we
trace all polymorphic entities used recursively keeping a record
to prevent an infinite loop, replacing calls to polymorphic functions
with calls to monomorpised versions. In C++ terms a call like:
vector<int>,size()
would be replaced by
vector_int.size()
References to variables and types have to be specialised too,
the exception is C bindings, since the specialisation is done
by the back end using textual substitution into C code strings.
There is a trick here: calls to virtual functions (in type classes)
have to be traced through to the actual instances by this
process. C++ is the same, where a specialisation is given by
the programmer instead of being generated.
At the end of the monomorphisation all type class stuff can
be removed.
Inlining now only needs to be done once, and the need to continually
attempt type class instantiation whilst doing it can be removed.
The cloning function can also be simplified since functions only
need to be specialised on arguments now, not type arguments.
The symbol garbage collector works by calculating which symbols
are used, starting from the roots. However there's a problem.
given:
{
var a;
var b = a;
var c = b;
var d = c;
};
then variable d is NOT considered used. However its initialised uses c,
and its initialiser uses b, and its initialiser uses a. The symbol d is deleted
and its initialiser is deleted too. Now we run the whole symbol collection
again. Now c is deleted. Then again. Now b is deleted. Then again.
Now a is deleted. Now again. Nothing is deleted, so we can stop.
It takes SIX passes to deletes 5 statements, and those passes analyse
the WHOLE program.
What's worse, because usage is so hard to calculate, the inliner does this
collection about SIX times when processing to keep the symbol set
minimised. This is essential to the algorithm when cloning children.
If I don't do this, the algorithm goes viral: inlining doesn't just reduce
the number of functions, in fact it doesn't reduce them at all. It increases
the number of functions so without pruning useless ones it can get
into an infinite expansion.
The multiple passes to delete unused symbols can be reduces to a single
pass by generating a proper dependency graph instead of just counting
the uses, and then doing a normal copy-collection pass.
All of this should speed up compilation of larger Felix programs a bit.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
