> Just curious, a few questions :
> - How long was your program?
> - How did you do the parsing? with happy?
> parser combinators? ...
> - Which compiler did you use ? (Okay, i think i know ... :-))
> - Other information you want to share with us ...
> (eg. - which optimization algoritm did you use?
> - how much coffee did you consume? :-))
1200 lines of Haskell.
The parser was a Happy parser.
We used GHC.
Below is our README, written in haste in the closing 10 mins.
One thing I didn't mention in it is that we use the exception-handling
extensions to arrange that if an optimisation pass hit a pattern-matching
error (usually a fatal error in Haskell), we catch it and simply throw
away that optimisation pass, and move on to the next one. So if all
give errors, our compiler degenerates to 'cat'. A fault-tolerant compiler.
Simon
The major passes of the optimiser are:
* convert (simple) IF to CASE
* simplify:
- merge identical branches of if/case
- eliminate if/case with only one remaining branch
- take account of information about variables gleaned
from enclosing cases to
o prune case branches
o make conditions go to True or False
- simplify boolean conditions arising from the above
- eliminate ifs with simple true/false conditions
* reorder: the program is basically a decision tree.
This pass tries to change the order in which variables are
examined in order to produce a smaller tree.
* merge: for each case, try to merge branches that are "fairly
similar". The differences are patched up by adding
cases at the patch points. This is a big win for busker
* Repeat simplify, reorder, merge
* Back end: the main task is to conver cases to a good representation, by:
- splitting into somewhat dense blocks
- using conditionals where that improves matters
o a case with a single value to match
o a case with a single sparse range turns into
an if with ORs
The driver program also includes a *simlulator* which checks that
the output of each pass is not obviously broken. If it is, the
driver throws away the output of the pass, and carries on. This
seems like a good way to avoid getting disqualified because of stupid bugs.
The driver also checks for timeout and abandons later passes if it
runs out of time.
