[Icfp04-discuss] Ant optimizers?

[Carlos Scheidegger]

While I did not use DDCG (am reading about it right now :) I did
implement and submit an optimizer with dead-code eliminator and a jump
chaser. The jump chaser typically created lots of dead code, which are
then pruned away. In some cases, I got some 60% improvement in final
state size (it was an extreme example, but goes to show that the
optimizer really helped). I didn't think of coalescing identical
instructions, but I will implement it right after I add state to my
language, as that is bound to generate lots of it.

The optimizer is arguably quite ugly (and certainly very inefficient),
as it uses a O(n^3) algorithm where quite likely a O(n log n) would
suffice. But it was coded in 15 minutes, so I'm proud of it :)

-carlos

On Thu, 10 Jun 2004 13:31:09 -0500, Kevin S. Millikin
<kmillikin at atcorp.com> wrote:
> 
> 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
> 
> _______________________________________________
> Icfp04-discuss mailing list
> Icfp04-discuss at lists.seas.upenn.edu
> http://lists.seas.upenn.edu/mailman/listinfo/icfp04-discuss
>