Compilers - optimizing an asm-like language

Author

optimizing an asm-like language

Remo D.

2008-01-30, 4:58 am

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

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.

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

To give you an example, the code at the bottom of this post is
generated for the expression "[a-z]?n". The meaning of the
instructions should be clear enough, except, maybe, for Rxx
(conditionl returns; RNE = Return if Not Equal, RLT = Return if Less
Then, etc) and "MTC x" (MaTCh expression, signals that the expression
x has been matched).

The things I've thought so far are:
- rearrange basic blocks to eliminate absolute jumps (e.g. the block
labeled S2, lines 24-27, could be moved to line 14 removing the "JMP S2")
- eliminate dead code (line 15, line 21 and line 28 for example)
- eliminate useless JMP (like the "JMP S3" at line 20)
Should I look for other optimizations?

Any comment will be very welcome.

Remo.D

1 S1: GET
2 L2: CMP 'n'
3 JGT L3
4 JEQ S4
5 L1: CMP 'a'
6 RLT
7 CMP 'm'
8 RGT
9 JMP S2
10 L3: CMP 'o'
11 RLT
12 CMP 'z'
13 RGT
14 JMP S2
15 RET
16 S4: GET
17 MTC 1
18 L4: CMP 'n'
19 RNE
20 JMP S3
21 RET
22 S3: MTC 1
23 RET
24 S2: GET
25 L5: CMP 'n'
26 RNE
27 JMP S3
28 RET

Chris F Clark

2008-02-01, 7:45 pm

"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)
------------------------------------------------------------------------------

Remo D.

2008-02-04, 7:51 pm

Chris F Clark ha scritto:
> "Remo D." <rdentato@news.tin.it> writes:
>
>
> I read this. Although the work is still unpolished and sketchy, it
> looks very promising.

Thanks Chris. There are corrections I have to make to the way tags
displacements are propagated to lambda transitions but the basic ideas
have not been changed.

Since English is not my first language, it takes a lot of time to me
to write a long document and, in the end, I'm never sure I managed to
make myself clear. I'll revise it, anyway.

> You machine looks like a single accumulator machine model.

Yes, only one character at time is considered so no operations other
than reading into the accumulator and comparing with a constant are
needed. Actualy there are other registers in the model but their
usage is straightforward. I'll have the instruction register (IR), a
register for the current position in the input stream (PR), a flags
register (FR) for the comparison results and a "tag register" (TR)
that will be used to implement all the tags machinery.

Conceptually TR will be the pointer to an array where the tags values
will be stored. The only operation needed is writing a constant into one
of the array cells.

> Well, you do want to be able to normal minimization like you would do with a
> DFA.

Yes but I still have to figure out how to modify a DFA minimization
algorithm to make it work with tagged FA. Probably it's just a matter
of re-defining the state equivalence relationship, I'll work on that
as soon as I'll be sure there's no fundamental flaw in my current
approach.

So far I've optimized the code removing dead code, useless jump and
useless comparisons. I still have to move basic blocks around to
eliminate some JMP.

At the bottom of the message there's the code generated for '[a-z]?n'
(the same example I gave in my previous message). As you anticipated
it's not much shorter but it avoids a pair of comparisons, so I guess it
has been worthwile to optimize it.

I'm now converting the ASM code to C so I can create and execute a
comprehensive test suite and get confidence on the correctness of my
approach.

Let's get back to coding ...

Remo.D.

--

Code for '[a-z]?n'

1 S1: GET
2 CMP 'n'
3 JGT L3
4 JEQ S4
5 CMP 'a'
6 RLT
7 JMP S2
8 L3: CMP 'z'
9 RGT
10 JMP S2
11 S4: MTC 1
12 GET
13 CMP 'n'
14 RNE
15 S3: MTC 1
16 RET
17 S2: GET
18 CMP 'n'
19 RNE
20 JMP S3

Walter Banks

2008-02-06, 10:17 pm

"Remo D." wrote:

> I'm now converting the ASM code to C so I can create and execute a
> comprehensive test suite and get confidence on the correctness of my
> approach.
>
> Let's get back to coding ...
>
> Remo.D.
>
> --
>
> Code for '[a-z]?n'
>
> 1 S1: GET
> 2 CMP 'n'
> 3 JGT L3
> 4 JEQ S4
> 5 CMP 'a'
> 6 RLT
> 7 JMP S2
> 8 L3: CMP 'z'
> 9 RGT
> 10 JMP S2
> 11 S4: MTC 1
> 12 GET
> 13 CMP 'n'
> 14 RNE
> 15 S3: MTC 1
> 16 RET
> 17 S2: GET
> 18 CMP 'n'
> 19 RNE
> 20 JMP S3

You might want to check common sub expression lines 13/14 and 18/19.
From experience C as an intermediate code does work quite well.

Walter Banks

Sponsored Links