Code Generation for Expressions with Common Subexpressions
- 1 January 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 24 (1) , 146-160
- https://doi.org/10.1145/321992.322001
Abstract
This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.Keywords
This publication has 9 references indexed in Scilit:
- Optimal Code Generation for Expression TreesJournal of the ACM, 1976
- Code Generation for a One-Register MachineJournal of the ACM, 1976
- The Generation of Optimal Code for Stack MachinesJournal of the ACM, 1975
- Register allocation via usage countsCommunications of the ACM, 1974
- The Generation of Optimal Code for Arithmetic ExpressionsJournal of the ACM, 1970
- Optimal code for serial and parallel computationCommunications of the ACM, 1969
- Generation of optimal code for expressions via factorizationCommunications of the ACM, 1969
- Index Register AllocationJournal of the ACM, 1966
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966