[Icfp04-discuss] Ant optimizers?

[Kevin S. Millikin]

On Thursday, June 10, 2004 11:57 AM, Jack Diederich 
[SMTP:jack at performancedrivers.com] wrote:
> Did anyone write a state optimizer?  I didn't, but I just banged
> one out (50 lines of python, I'm sure someone could write a one-liner
> in perl).  If two lines are the same, anyone that goes to one could
> go to the other instead.

Yes, we wrote an optimizer, but we did not submit it.

In addition to the optimization you describe (combining identical states), 
we coalesced useless jumps.  Our compiler inserted "jumps" in the compiled 
ant, of the form:

Sense Here X X Rock   ; where X = X, though the first state is irrelevant

We could have used "Flip X Y Y" as well.  Control flow to a useless jump 
was replaced with flow to the jump target X (except for the case where the 
useless jump was state X itself, which would have been an unsound 
translation if there were any other jumps to X).

Finally, we traversed the reachable states starting with the start state, 
and removed unreachable states.  After no more states could be removed, we 
compressed the ant to eliminate empty instructions.

----
Kevin S. Millikin           Architecture Technology Corporation
Research Scientist          Specialists in Computer Architecture
(952)829-5864 x162          http://www.atcorp.com