Re: optimizing an asm-like language

Chris F Clark <>
Wed, 30 Jan 2008 14:15:26 -0500

          From comp.compilers

Related articles
optimizing an asm-like language (Remo D.) (2008-01-29)
Re: optimizing an asm-like language (Chris F Clark) (2008-01-30)
Re: optimizing an asm-like language (Remo D.) (2008-02-03)
Re: optimizing an asm-like language (Walter Banks) (2008-02-04)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Wed, 30 Jan 2008 14:15:26 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 08-01-079
Keywords: optimize
Posted-Date: 01 Feb 2008 20:42:10 EST

"Remo D." <> writes:

> Hi there. I'm adding the capability to generate code to my regular
> expression based tool (

I read this. Although the work is still unpolished and sketchy, it
looks very promising.

> I've defined an assembly-like language to use as intermediate
> code. The plan is to optimize this asm-like code and then convert it
> in C (or possibly other languages).
> The main reason to go through this intermediate language is to apply
> optimization only once rather that having to devise optimization in
> each target language.
> The other reason is to be able to write a function to directly execute
> this asm-like program.
> The first question I have is: Should I use a different approach? I
> briefly thought of interpreting the DFA but it didn't seem a good idea
> to me. Also, I can foresee an issue on converting the ASM language to
> another language that doesn't have goto's.

Your ASM approach is a fundamentally good one. In fact, the
traditional DFA (or NFA) approach is also just an assembly language
approach--just a more abstract one. We used our own hand-designed
assembly language in Yacc++ to very good effect. You machine looks
like a single accumulator machine model. That is potentially a good
choice, since it is fairly simple and straight-forward and regular
expressions do not need more (not even a stack).

> The second question is: are there any optimization techniques I should
> absolutely know for optimizing asm-like code?

Probably, but I can't recommend many off-the-top-of-my-head. Well,
you do want to be able to normal minimization like you would do with a
DFA. Tail merging is a good technique to know. You probably want to
have some "default state" processing techniques. Also worth knowing are
state compression techniques. From, the text I elided, it sounds like
you are already considering merging blocks and jump-to-jump type
optimizations, which are good.

However, all-in-all, there probably won't be that much effect from
optimizing your assembly language, aside from eliminating a few jumps
and merging some flow paths to make the code smaller. The basic
nature of an FA is pretty close to optimal in itself, because you only
have the single element you are looking at (the accumulator/read head)
and there are no variables or expressions to apply traditional
optimizations to.

Hope this helps,

Chris Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.