METHOD FOR IMPROVING THE EFFICIENCY OF ARITHMETIC CODE GENERATION IN AN OPTIMIZING COMPILER USING THE TECHNIQUE OF REASSOCIATION

A procedure for use in an optimizing compiler termed "reassociation" determines the preferred order of combining terms in a sum so as to produce loop invariant subcomputations, or to promote common subexpressions among several essential computations, by applying the associative law of addition. To achieve this, the requisite optimization of an object program or program segment, the following discrete steps must be performed after the strongly connected regions, USE and DEF chains have all been identified: PA1 1. Find the region constants and induction variables; PA1 2. Identify all of the essential computations; PA1 3. Write every essential computation as a sum of products; PA1 4. Exploit the use and DEF functions to substitute the definition of each operand R in an essential computation, if there is a unique computation of R in the strongly connected region and the defining operation is +, -, .times., or copy; PA1 5. Fix displacements; PA1 6. Determine how to compute each essential computation and rewrite code to use this preferred method of computation; PA1 7. Insert code to update the new induction variables; PA1 8. Perform linear test replacement.