Re: Graham-Glannville code generators

Ralph Boland <rpboland@gmail.com> writes:
>1) Is Graham-Glannville style code generation still in active use/
>development or is it passe?


It is passe. Tree-parsing instruction selection (iburg, burg, BEG,
etc.) is a superior technology for the same principle.


Basically, in Graham-Glanville instruction selection you represent the
intermediate representation tree as string in prefix form, and then
use an ambiguous grammar to parse it into patterns corresponding to
instructions. To get good instruction selection, you need a parser
generator tuned for the purpose and you need to arrange the order of
the rules in a special way (IIRC), which takes quite a bit of effort;
at least that's the impression I got from a paper on the topic
(unfortunately I don't remember anything else about the paper; maybe
it was published in Software - Practice and Experience in the early
90s).


In tree-parsing the tree is represented as a tree, you have explicit
costs, and a simple (bottom-up) dynamic programming algorithm can
select a set of instructions with minimal cost.


>Once my parser generator is complete I will start a project on
>generating code targeting virtual machines such as JVM and LLVM. So
>my second question is:
>
>2) Where does Graham-Glannville style code generation fit in when
>generating virtual machine code?


It would fit in the same place as for real machine code: If the VM has
instructions that correspond to several operations of the intermediate
representation, instruction selection should select them where
profitable.


IIRC the JVM has a few such instructions, but IIRC they are amenable
to simple greedy instruction selection methods.


LLVM is a compiler infrastructure that generates real-machine code. I
think that LLVM is also the name of the intermediate representation of
that compiler. I doubt that you need an instruction selection method
when generating that intermediate representation. Using it for
generating the real-machine is possible. AFAIK LLVM uses a greedy
(not necessarily optimal) top-down tree-parsing method for instruction
selection.


>2b) (O.k. so I can't count to 3.)
>Let's say I now want translate virtual machine code into real
>machine code. I assume that this is where Graham-Glannville would
>normally be used.


Yes.


>Is there anything about Graham-Glannville style code generation that
>is going to be different or of interest in this situation?


No.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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