Re: optimizing an asm-like language

Chris F Clark ha scritto:
> "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.


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

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