Re: Is it just me or...

jaycole@bgn.mindspring.com (Jay Cole) writes:


[deletions]


      2) Am I one of the few people in the compiler world that prefers to
      generate and optimize code from a tree-type structure rather than
      tuples? I find optimization and manipulation much easier in the tree
      format. I just have a difficult time generating real good code from
      the tuple format. Is there a good book on tuple based code
      generation?


If you're one of the few, so am I.


The "optimising" compiler that I co-wrote in a previous existance
compiled RTL/2 code -- to be exact, the intermediate codes generated
by the then-Standard RTL/2 front end -- into assembly code for the
SMR-mu, a 24-bit home-grown machine made, if I remember correctly, by
a subsidary of Phillips.


We reconstructed a "parse" tree from the intermediate code (that was
fun; the reconstruction relied on certain undocumented features of
that code, specifically the way branch labels [integers] were
allocated. Looking back, I'm impressed that it was as reliable as it
was. Then the tree was well-shaken, doing things like constant
evaluation (which the front end didn't do) and some simplifications;
then a couple of walks looked for "interesting" information about the
tree nodes, eg whether sub-nodes did indexing.


(That was because the machine had two base registers and one index
register, so when a subscript expression was being evaluated it was
useful to know if either operand itself required the index register).


The annotated tree then got flattened by another tree-walk, which
tracked register used (easy enough, given the base/indexing registers
mentioned and the single accumulator) and generated generic assembly
code; the genericity was removed by the final pass, which took
instructions like "ADD [INT] X" and generated the appropriate flavour
of assembler instruction.


We found that trees made a very convenient structure; a single node
can represent arbitrary amounts of data in a natural way. I was very
influenced by Bornat's "understanding and writing compilers", but I'd
also read (and still own!) "the design of an optimising compiler".


We [the developers and the client] were very satisfied with the
results. The compiler was later ported to compile for the SMR-mu's
successor, and the architecture later generalised to work with
multi-general-register machines such as the 68K and the Vax (where the
compiler exposed a Vax microcode bug!).


So, yes, trees. Good stuff. I could ramble on for ages about that
project, probably the most fun one I've ever worked on, but in
deference to our moderators limited editing time and our readers
patience, I'll stop here.
--


Regards,
Kers.
[The main advantage I see in quads is that it makes code motion easier, but
I've been pretty happy with trees, too. -John]
--

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