[m-dev.] Summer Student Report

[Samrith UONG]

Hi everyone,

I'm one of the summer students this year and Ralph (my supervisor) has
asked me to write a progress report.  My project can be roughly
divided into three parts, described below:

1) Last year we performed a lot of benchmarking on the compiler, with
different optimisation settings and different grades.  There were a
number of interesting results from this, such as finding out that not
only is -O6 a lot slower than -O5 (at least for the compiler), but
also that any one of the options that it sets results in a decrease in
performance.

2) I am also working on a top-down inlining algorithm for Mercury,
which may replace the current bottom-up inliner if the new inliner can
outperform the current one.

The algorithm to be implemented was originally written for a Scheme
compiler.   After a while we realised that most of the inlining
algorithm was already implemented in the compiler (in simplify.m and
inlining.m), except for the code which keeps track of the effort
expended and the size of the current program (which is used to make
decisions on whether to continue inlining).

The most difficult part of this was in understanding the existing code
for the compiler, especially how the HLDS is structured.  After
spending some time last year working this out, I plan to complete the
implementation of this part of the project after the genetic algorithm
code is implemented (see below).  This is to allow the GA to run on
leopard while I am working on the inliner.

Implementing this will require modifying the existing inliner so that
it goes top-down instead of bottom up.  The code already constructs a
call graph for the program to be compiled.  All that needs to be done
is to go through the graph in reverse and modify the inlining_in_*
predicates to do their work in reverse.

An "effort counter" and "size counter" will be implemented inside the
existing "inline_info" data structure.  This data structure is
threaded through the inlining algorithm.  The appropriate checks will
need to be added to the inlining_in_* predicates to decide whether or
not to continue inlining.

Recursive predicates will eventually exhaust the effort counter,
however, we can improve this by avoiding inlining a procedure more
than once.  This can easily be done by keeping track of the procedures
that have been inlined in a stack.  After this has been implemented,
the algorithm might be modified to more closely follow the original
algorithm.

3) Finding sets of optimisation flags to pass to mmc that will work
well on most programs is the other part of the project.  It would also
be good to find out why these combinations of flags work better than
others.  These sets of optimisations will be used by the -O flag in
the future.

Although the original project description mentioned using a local
search algorithm, it was decided that a genetic algorithm would be
used instead.  The code for this has mostly been written, except for
some of the genetic operators and the code to compile the benchmark
programs in parallel.

The genetic operators don't present too much of a problem, and should
be implemented fairly quickly.

However building in parallel may mean that the compile time results
cannot be used (as other people may be using the computer).  One way
around this is to ignore (or decrease the weighting of) compile times,
and rely more on executable sizes and run times.  I've written the
program so that it can be started without the parallel building code,
and then later restarted once that has been implemented.

There was also a problem with one of the data structures I was using
earlier, which meant that the shell script I was planning to use to
run the benchmarking tests had to be thrown away.  This will be
rewritten shortly.

The current code for the Mercury program is attached.  Some dummy
inputs are also attached.  It reads in two files containing the
optimisation flags and benchmark results, and produces a new
generation of optimisation flags.  At the moment some of the
predicates (that evolve the genotype to the next state) are just
placeholders, so the breeding process just creates an identical copy
of the parent.

Sam.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: evolve.m
Type: text/x-objcsrc
Size: 11118 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/developers/attachments/20060110/f6adc3d9/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: genotypes
Type: application/octet-stream
Size: 1857 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/developers/attachments/20060110/f6adc3d9/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: phenotypes
Type: application/octet-stream
Size: 4 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/developers/attachments/20060110/f6adc3d9/attachment-0001.obj>