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