[Icfp04-discuss] Ant optimizers?

[Ganesh Sittampalam]

On Thu, 10 Jun 2004, Jack Diederich wrote:

> Oops, I just checked dunkosmiloolump-1.ant and it reduces by zero,
> so at least one team wrote an ant optimizer (either post optimizer
> or built into their generator).

It was one of the phases before actually numbering the states; we did
pretty much what you described with collapsing identical statements and
then iterating. (Someone pointed out to me afterwards that it's actually
just DFA minimisation and rather more efficient algorithms exist to do
that, but this was simple and it worked fine for us).

We also detected and removed dead code (as a natural consequence of the
generator), but warned about it as it normally indicated a mistake. We
collapsed identical branches except for Sense Here Foe n n which was used
when we needed to waste time for some reason, and carried out some
peephole optimisations - in pseudocode, if (Sense Here Marker n) goto x
else Mark n ; goto x can be translated to Mark n ; goto x. Of course you
then rerun the common state eliminator in case any new optimisation
opportunities, appeared, and vice versa.

I even wrote a control flow analysis that eliminated unnecessary Sense and
Mark instructions by analysing the known marking state on any program
path; but I never got it fully debugged.

In the end none of it mattered; none of our ants were ever close to 10000
states pre-optimisation. But the extra headroom it provided possibly meant
we were more willing to try stuff.

Cheers,

Ganesh