21 Apr 2002 19:38:20 -0400

Related articles |
---|

Arithmetic expression the-gos@ifrance.com (antoine) (2002-04-21) |

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.