Optimal Code Generation for Expression Trees: An Application of BURS (bottom-Up Rewrite Systems) Theory
Abstract
A Rewrite System is a collection of rewrite rules of the form alpha approaches limit of beta where alpha and beta are tree patterns. A rewrite system can be extended by associating a cost with each rewrite rule, and by defining the cost of a rewrite sequence as the sum of the costs of all the rewrite rules in the sequence. The REACHABILITY problem for a rewrite system R is, given an input tree T and a fixed goal tree G, to determine if there exists a rewrite sequence in R, rewriting T into G and, if so, to obtain one such sequence. The C-REACHABILITY problem is similar except that the obtained sequence must have minimal cost among wall those sequences rewriting T into G. This paper introduces a class of rewrite systems called Bottom-Up Rewrite Systems (BURS), and a tabledriven algorithm to solve REACHABILITY for members of the class. This algorithm is then modified to solve C-REACHABILITY for members of the class. This algorithm is then modified to solve C-REACHABILITY and specialized for a subclass of BURS so that all cost manipulation is encoded into the tables and is not performed explicitly at solving time. The subclass extends the simple machine architectures for code generation, by allowing additional types of rewrite rules such as commutativity transformations. A table-driven code generator based on solving C-REACHABILITY has been implemented and tested with several machine descriptions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1988
- Accession Number
- ADA197292
Entities
People
- Eduardo Pelegri-llopart
- Susan L. Graham
Organizations
- University of California, Berkeley