Re: Back End Generators

>There are lots of very interesting CG techniques. One of my favorites
>is CG via _parsing_, which uses an inherently ambiguous grammar to
>recognize a parse tree, and then uses dynamic programming to pick the
>winning parses based on their execution-time costs. The code
>generation itself is via a standard Knuth attributed grammar. Very
>elegant.


johnmce@world.std.com (John McEnerney) writes:
>This was the Graham-Glanville algorithm; it was Glanville's PhD thesis.
>I seem to have lost the original paper. The idea was to use an LR parser
>to recognize substrings in a prefix representation of the IR tree, and
>associate code generation actions with the parse. There have been several
>follow-up papers on this. The only commercial compiler I have heard of
>that used this was an old Intel cross-compiler for x86 development.


Half right.


Graham & Glanville did the first (tree) parser for code generation.
They did not do dynamic programming for parse selection.
The LR parsing technology they used could not accommodate this.


The first tree pattern matching (really tree parsing) based code
generators that used dynamic programming were done by Aho, Ganapathi, &
Tjiang at Stanford/Bell Labs, by Henry & myself at Univ. of Washington,
and by Hatcher & Christopher at ??? (see bibliography below). Also, Chase
and Pelegri-Llopart were doing work in this area at about that time
(1985-1986).


There has been some more recent work by Henry & Fraser that appeared in
Software Practice & Experience, but I can't find the references for that.


The SunPro/SunSoft SPARCompilers 3.0 and 3.0.1 use a bottom-up tree
pattern matching code generator generator, though you'd be hard pressed to
notice it.




>My favorite was Davidson & Fraser's "Code Selection through Object Code
>Optimization". The idea was to generate simple instructions, then
>optimize them into more complex instructions/addressing modes by
>examining logically adjacent instructions and doing symbolic substitution
>on their algebraic definitions, looking for a new instruction whose
>algebraic definition has the combined effect. This approach is used in
>the gcc compiler; it generates incredibly good code for CISC machines
>like the 680x0.


These "peephole optimizer" code generators are the major "competitor" to
the tree pattern matching code generators. Each has its advantages and
disadvantages.


I believe that "lcc" by Fraser and Hanson (?) is based on this technology.


Later,
Peter.




Bibliography:
-------------
BTLMH == Bell Labs, Murray Hill, NJ
CCC == ACM Sigplan Symp. on Compiler Construction
UWCSD == Dept. of Computer Science, Univ. of Washington
POPL == ACM Symp. on Principles of Programming Languages
TOPLAS == ACM Trans. on Programming Languages and Systems


%A Alfred V. Aho
%A Mahadevan Ganapathi
%A Steven W. K. Tjiang
%T Code Generation Using Tree Matching and Dynamic Programming
%R Technical Report
%I BTLMH
%D JAN 1986
%K tree pattern matching


%A Steven W. K. Tjiang
%T Twig Reference Manual
%R Computing Science Technical Report No. 120
%I BTLMH
%D JAN 1986


%A Peter C. Damron
%T Code Generation and Top Down Tree Pattern Matching
%K masters thesis
%R M.S. Thesis, UWCSD
%D MAR 1986


%A Robert R. Henry
%A Peter C. Damron
%T Algorithms for Table-Driven Code Generators Using Tree-Pattern Matching
%R Technical Report 89-02-03
%I UWCSD
%C Seattle, WA
%D FEB 1989


%A Robert R. Henry
%A Peter C. Damron
%T Performance of Table-Driven Code Generators Using Tree-Pattern Matching
%R Technical Report 89-02-02
%I UWCSD
%C Seattle, WA
%D FEB 1989


%A Philip J. Hatcher
%A Thomas W. Christopher
%T High-Quality Code Generation Via Bottom-Up Tree Pattern Matching
%P 119-130
%J POPL13


%A Eduardo Pelegri-Llopart
%T Tree Transformations in Compiler Systems
%R PhD Dissertation
%I UCBCS
%D DEC 1987


%A Eduardo Pelegri-Llopart
%A Susan L. Graham
%T Optimal Code Generation for Expression Trees: An Application of BURS Theory
%J POPL88
%K 1988 popl popl15
%P 294-308


%T Automatic Generation of Peephole Optimizations
%A Jack W. Davidson
%A Christopher W. Fraser
%J CCC84
%P 111-116


%A Chris W. Fraser
%A Alan Wendt
%T Integrating Code Generation and Optimization
%P 242-248
%J CCC86


%J CCC88
%T Automatic Generation of Fast Optimizing Code Generators
%A Chris W. Fraser
%A Alan L. Wendt
%P 79-84


----------------------------
Peter C. Damron, (not speaking for) SunSoft, a Sun Microsystems, Inc. Business
Advanced Languages, UMTV 12-40, 2550 Garcia Ave. Mtn. View, CA 94043
pdamron@eng.sun.com
--

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