Arithmetic expression

antoine <the-gos@ifrance.com>
21 Apr 2002 19:38:20 -0400

          From comp.compilers

Related articles
Arithmetic expression the-gos@ifrance.com (antoine) (2002-04-21)
| List of all articles for this month |

From: antoine <the-gos@ifrance.com>
Newsgroups: comp.compilers
Date: 21 Apr 2002 19:38:20 -0400
Organization: None
Keywords: arithmetic, comment
Posted-Date: 21 Apr 2002 19:38:20 EDT

Hello all


I'm looking for any documentation (paper or electronic) that deals
with the following subject: the generation of code for evaluating
arithmetic expressions. In particular, I would like to understand how
to compute the minimum number of 'accumulators' necessary for the
evaluation of such expressions.
--
I t±ld yo±, "Never±touch ±he flop±y disk s±rface!"


[In the early 1970s, Sethi and Ullman did a pretty good heuristic that
runs down an expression tree and labelled each node with the number of
registers needed to compute that node. The value is usually 1 plus
the lesser value of the two subtrees, and the value of a leaf is one
or zero depending on whether the machine can do arithmetic operations
from memory. Then generate code by running over the tree again,
computing the "more expensive" subtree first at each point. That may
not be optimal, but I think it's pretty close. These days, I'm not
sure it's a meaningful question since compilers tend to take a much
higher level view of a program, using registers to cache common
subexpressions and frequently used operands as well as for expression
intermediate values. If you just want to generate simple-minded code
for an expression tree, flatten the tree into RPN and pretend your
register file is a stack. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.