Optimal code generation for expression trees: an application BURS theory
Eduardo Pelegri-Llopart, S. L. Graham · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1988
A Rewrite System is a collection of rewrite rules of the form α β where α and β 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 all those sequences writing T into G.
Cited by 105 works. doi:10.1145/73560.73586 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Personal communication
- Yacc : Yet Another Compiler Compiler
- Reduced instruction set computers
- Code Generation for Expressions with Common Subexpressions
- Code generation using tree matching and dynamic programming
- A new method for compiler code generation
- tree automata: an informal survey
- An improvement to bottom-up tree pattern matching
- High-quality code generation via bottom-up tree pattern matching