News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

3AC vs Tree Rewritting

Started by cman, May 11, 2007, 07:43:20 PM

Previous topic - Next topic

cman

What are the benefits of using either of these intermediate code representations as far as code generation and optimization ( enhancement  :bg ) are concerned? Most of the compiler construction books I have seem to use the 3AC treatment of code generation. I know using a target program tree ( or tree rewritting as covered in pages 572-579 of the "Red Dragon Book" ) simplifies the task of instruction selection on machines with many addressing modes. Both treatments look interesting and I would like to work with the simplest and most efficient method to study complier code generation ( generation into assembly language in this case ). Thanks for any information! :U

tenkey

The primary use of three-address instructions is redundancy elimination, which is an optimization feature. It is also closer to machine language than a parse tree. For every "micro" operation, including those used in address calculations, you get an explicit statement of what values are used, and what value is generated. You can discover def-use dependencies that tell you which values are redundant, and also if they have not been properly initialized. The benefits are great, but it can be a bit of work because most languages don't have built-in functions for combining sets, or handling graph networks.

The parse tree is easier to understand. If you want to optimize, you don't need all the math used by the above method. However, it can become unmanageable if you try to optimize a lot of things, all at once.

Do you have any of Appel's compiler construction books? I believe they will be, if they haven't already become, the new standard for compiler textbooks.
A programming language is low level when its programs require attention to the irrelevant.
Alan Perlis, Epigram #8

cman

Thanks for the information tenkey! I'm thinking of using the syntax tree route as this method allows the collection and storage of more information from the original parse tree and definition table. Thomas Parsons book Introduction to Compiler Construction recommends this method for its ease of optimization ( but then covers the topic with 3AC !  :bg ). I think many optimizations could be feasible with this treatment ( I think data flow analysis being the most valuable ) and a syntax tree will offer the code generator much information for instruction selection ( the "shape" of the instruction , easier type coercion  , a general class of instruction needed ( floating point addtion , ect. )  , ect. ). I haven't got Appel's new book yet , but I will at some point ( I have many others now , and I'm currently reading other things as well compiler construction - electronic design and some physics things ). Thanks for your input! :bg