Re: Reconstructing the Types of Stack-Machine Codes

  Oukseh Lee <cookcu@ruby.kaist.ac.kr> writes:
> Whoever knows about TYPE ANALYSIS of STACK-MACHINE CODES?


The JavaVM people have to do this to check the validity of the class
file, and also to do better register allocation (the JavaVM has a
unified stack, but most architectures have separate integer and FP
register sets).


There is also work on statically type-checking Forth (by Jaanus Pöial,
Peter Knaggs and Bill Stoddart), but it is inspired by MLs type
inference and may be overkill for your purpose. You can find these
papers in the Forth bibliography:
http://liinwww.ira.uka.de/bibliography/Compiler/forth.html


> An example to explain why type information help us to generate more
> efficient target code:
>
> For example, for input code (a),
> assuming possible control-flow is A->C and B->C,
>
> A: push 1 A: rsp <- rsp+1 A: r1 <- 1
> push 2 M[rsp] <- 1 r2 <- 2
> jump B rsp <- rsp+1 jump B
> B: push 3 M[rsp] <- 2 B: r1 <- 3
> push 4 jump B r2 <- 4
> C: add B: rsp <- rsp+1 C: ... <- r1+r2
> M[rsp] <- 3
> rsp <- rsp+1
> M[rsp] <- 4
> C: ... <- M[rsp]+M[rsp-1]
> rsp <- rsp -2
>
> *rsp: register for stack *r1,r2: integer registers
> pointer
>
> (a) input (b) stack-emulation (c) efficient
> target code target code
>
> If we know the top of stack before C is two integer, instead of
> stack-emulation target code such as (b), we can generate more
> efficient target code such as (c).


Seems that you only need to know the stack depth statically, not the
types. There is a lot of work on this. You will probably find several
papers discussing this in the JavaVM JIT compiler literature. Among
my own work the most relevant is probably


@InProceedings{ertl&maierhofer95,
    author = {M. Anton Ertl and Martin Maierhofer},
    title = {Translating Forth to Efficient C},
    crossref = {euroforth95},
    url = {http://www.complang.tuwien.ac.at/papers/ertl&maierhofer95.ps.gz},
    abstract = {An automatic translator can translate Forth into C
                                    code which the current generation of optimizing C
                                    compilers compiles to efficient machine code. I.e.,
                                    the resulting code keeps stack items in registers
                                    and rarely updates the stack pointer. This paper
                                    presents a simple translation method that produces
                                    efficient C code, describes an implementation of the
                                    method and presents results achieved with this
                                    implementation: The translated code is 4.5--7.5
                                    times faster than Gforth (the fastest measured
                                    interpretive system), 1.3--3 times faster than
                                    BigForth 386 (a native code compiler), and smaller
                                    than Gforth's threaded code.}
}


@Proceedings{euroforth95,
    title = "EuroForth~'95 Conference Proceedings",
    booktitle = "EuroForth~'95 Conference Proceedings",
    year = "1995",
    key = "EuroForth '95",
    address = "Schloss Dagstuhl, Germany",
}


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

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