|optimizing an asm-like language firstname.lastname@example.org (Remo D.) (2008-01-29)|
|Re: optimizing an asm-like language cfc@shell01.TheWorld.com (Chris F Clark) (2008-01-30)|
|Re: optimizing an asm-like language email@example.com (Remo D.) (2008-02-03)|
|Re: optimizing an asm-like language firstname.lastname@example.org (Walter Banks) (2008-02-04)|
|From:||"Remo D." <email@example.com>|
|Date:||Sun, 03 Feb 2008 09:26:49 +0100|
|Posted-Date:||04 Feb 2008 13:05:47 EST|
Chris F Clark ha scritto:
> "Remo D." <firstname.lastname@example.org> 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.
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.
>> I've defined an assembly-like language to use as intermediate
>> code. [...]
> 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.
>> The second question is: are there any optimization techniques I should
>> absolutely know for optimizing asm-like code?
> Well, you do want to be able to normal minimization like you would do with a
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
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
Let's get back to coding ...
Code for '[a-z]?n'
1 S1: GET
2 CMP 'n'
3 JGT L3
4 JEQ S4
5 CMP 'a'
7 JMP S2
8 L3: CMP 'z'
10 JMP S2
11 S4: MTC 1
13 CMP 'n'
15 S3: MTC 1
17 S2: GET
18 CMP 'n'
20 JMP S3
Return to the
Search the comp.compilers archives again.