Re: TWIG any info

ask@csa.iisc.ernet.in writes:
>wrt:
> TWIG code generator generator using tree pattern matching/rewriting.
>
> Can anybody give links to TWIG ? Where is it available
>source/binary form / at what terms/conditions for non-commercial use.
>-
>Abhay Kanhere
>[Twig is very old, before 1970 I think. -John]


Actually, TWIG was developed about 1985-1986. I was working on similar
technology in the UWCODEGEN system at University of Washington with Robert
Henry at the time. There was an early paper on the TWIG idea in POPL in
January 1986, I think. Here are a few references that I have.


%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, Bell Labs, Murray Hill, NJ
%D JAN 1986


%A Steven W. K. Tjiang
%T Twig Reference Manual
%R Computing Science Technical Report No. 120
%I BTLMH, Bell Labs, Murray Hill, NJ
%D JAN 1986


%T Code Generation Using Tree Matching and Dynamic Programming
%A Alfred V. Aho
%A Mahadevan Ganapathi
%A Steven W. K. Tjiang
%P 491-516
%J TOPLAS
%D OCT 1989
%V 11
%N 4


%A Peter C. Damron
%T Code Generation and Top Down Tree Pattern Matching
%R M.S. Thesis, UWCS, University of Washington, Dept. of Computer Science
%D MAR 1986


%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, University of Washington, Dept. of Computer Science
%C Seattle, WA
%D FEB 1989


Sorry, I don't have the code and don't know where it's located. Perhaps one
of the authors will respond.


If you are thinking of using TWIG or similar technology for code generation,
you should realize that the top-down tree pattern matching done by TWIG is
slower at pattern match time (compile-time), though faster at pattern
matcher generation time (build-time), than bottom-up pattern matchers, like
BEG, BURS, and IBURG.


Here are a few references to the bottom-up tree pattern matchers.


%A Christopher W. Fraser
%A Robert R. Henry
%T Hard-Coding Bottom-Up Code Generation Tables to Save Time and Space
%J SPE, Software - Practice and Experience
%V 21
%N 1
%D JAN 1991
%P 1-12


%T Optimal Code Generation for Expression Trees: An Application of BURS Theory
%A Eduardo Pelegri-Llopart
%A Susan L. Graham
%J POPL88, Principles of Programming Languages
%C San Diego, California
%D JAN 1988
%P 294-308


%T Simple and Efficient BURS Table Generation
%A Todd A. Proebsting
%P 331-340
%J SIGPLAN92, PLDI
%D JUL 1992
%V 27
%N 7




Hope this helps,
Peter.


----------------------------
Peter C. Damron, (not speaking for) SunSoft, a Sun Microsystems, Inc. Business
SPARCompilers, UMPK 16-303, 2550 Garcia Ave. Mtn. View, CA 94043
peter.damron@eng.sun.com
--

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