Browse Prior Art Database

Expression Evaluation With Minimum Average Storage Demand

IP.com Disclosure Number: IPCOM000073899D
Original Publication Date: 1971-Feb-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 2 page(s) / 38K

Publishing Venue

IBM

Related People

Chroust, G: AUTHOR

Abstract

A binary program tree, representing the expression to be evaluated, is scanned, commencing at the root. If at some node an operation is encountered which has more than one branch, a branch is chosen which has not been previously scanned and whose execution takes longer than any other unscanned branch. Scanning continues until an operation is reached, whose operands are either temporarily stored or are variables. For this operation a code is generated. The name of the temporary storage, into which the result of the operation is to be transferred at object time, replaces the operation. Scanning continues with the next higher node in the tree.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 68% of the total text.

Page 1 of 2

Expression Evaluation With Minimum Average Storage Demand

A binary program tree, representing the expression to be evaluated, is scanned, commencing at the root. If at some node an operation is encountered which has more than one branch, a branch is chosen which has not been previously scanned and whose execution takes longer than any other unscanned branch. Scanning continues until an operation is reached, whose operands are either temporarily stored or are variables. For this operation a code is generated. The name of the temporary storage, into which the result of the operation is to be transferred at object time, replaces the operation. Scanning continues with the next higher node in the tree.

The above algorithm takes into account that the values of the operands initially evaluated have to await in temporary storage evaluation of the other operands, so that this storage is occupied during evaluation of the latter operands. Operands whose evaluation takes longer are preferred during object code generation. This results in the time for which the temporary storage is required fur the result previously evaluated being reduced. The algorithm is used in a compiler to generate an object code which requires, on an average, a minimum number of storage locations or registers for the intermediate results at object time. Example: a + b - (c + d) + e * f * g.

The structure of the above expression is shown in the left view. Assuming that multiplication takes ten times lon...