Portal de Periódicos da CAPES

Code Generation for Expressions with Common Subexpressions

1977; Association for Computing Machinery; Volume: 24; Issue: 1 Linguagem: Inglês

10.1145/321992.322001

1557-735X

Alfred V. Aho, S. C. Johnson, Jeffrey D. Ullman,

semigroups and automata theory

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.