Code Generation for Expressions with Common Subexpressions
Alfred V. Aho, S. C. Johnson, Jeffrey David Ullman · Journal of the ACM · 1977
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.
Cited by 167 works. doi:10.1145/321992.322001 Open-access PDF
Authors
References
- A study of replacement algorithms for a virtual-storage computer
- Index Register Allocation
- The Generation of Optimal Code for Arithmetic Expressions
- Optimal Code Generation for Expression Trees
- Complete Register Allocation Problems
- Optimal code generation for expression trees
- Code Generation for a One-Register Machine
- Register allocation via usage counts
- Generation of optimal code for expressions via factorization
- The Generation of Optimal Code for Stack Machines