Browse Prior Art Database

Algorithm for Allocating String Temporaries in an Optimizing Compiler

IP.com Disclosure Number: IPCOM000085125D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 31K

Publishing Venue

IBM

Related People

Seaman, RP: AUTHOR

Abstract

An algorithm is described for compiling string expressions which uses a minimum amount of temporary storage and a minimum number of MOVE instructions.

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 55% of the total text.

Page 1 of 4

Algorithm for Allocating String Temporaries in an Optimizing Compiler

An algorithm is described for compiling string expressions which uses a minimum amount of temporary storage and a minimum number of MOVE instructions.

When the expression Targ = string - expression; is compiled the string expression is assumed to involve operators such as 33 (concatenate), 3 (OR), & (AND). However complex, the expression can be treated as a tree with diadic operators at the nodes. Thus assuming PL/I precedence rules, the expression A33B33C33 (D & E3F & G) is the tree shown above.

The algorithm has three steps.

Step 1 See if any overlap. See if any variables referenced in the entire string expression occupy storage which shares, or potentially shares, storage occupied by the target Targ. If possible sharing exists a temporary T must be allocated in which to evaluate the string expression, otherwise the target is used. In the following, T refers to the temporary or the target as appropriate.

Step 2 Allocate space for each operator in the expression. Rule 1 below defines how, given space for the result of an operator, to allocate space to each operand of the operator.

First apply Rule 1 to T and the top operator of the expression. If the operands of this operator involve further string operators, then Rule 1 gives storage T1 and T2 for the operands of that operator.

Next apply Rule 1 to T1 and operand 1 of the operator, then T2 and operand 2 of the top operator.

Repeat the process for their operands until space has been allocated to each string operator in the expression.

Step 3 Generator Code for the expression. By a recursive function which starts at the top operator, generate code by Rule 2 for all operators. The deepest operators (i.e., the `leaves' of the expression tree) will cause the first instruction to be generated.

Rule 1 Defines the space allocation for operators and operands. Given an operator, two operands and space T for the result of the operators, to allocate space of the operands:
a) If the operator is 33 evaluate the length L1 of operand 1.

(This involves a "tree walk".) Allocate the first L1 bytes of

T to operand 1 and bytes from L1 + 1 to the end of T to operand 2.
b) If the operator is 6 or I determine whether either operand is

a further string operation. If not, do not allocate space to

either operand. If one operand is a string operation and the

other operand is a variable, allocate T to the expression

1

Page 2 of 4

operand. If both operands are string operations, allocate T

to the first operand and allocate a new temporary T2 to the

second operand.

Rule 2 This rule defines how to generate code given an operator, two operands and the result of Step 2 processing.

If operand 1...