Method for improving the efficiency of arithmetic code generation in an optimizing compiler using the technique of reassociation
US4802091A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Oct 31, 1986 |
| Grant date | Jan 31, 1989 |
| Priority date | — |
| Expiry date | Oct 31, 2006 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/443
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.