Re: optimizing an asm-like language

"Remo D." <rdentato@news.tin.it> writes:


> Hi there. I'm adding the capability to generate code to my regular
> expression based tool (http://yrx.googlecode.com).


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


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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