System, method, and computer program product for partial redundancy elimination based on static single assignment form during compilation
US6026241A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 13, 1997 |
| Grant date | Feb 15, 2000 |
| Priority date | — |
| Expiry date | Jun 13, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/443
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting .PHI. functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the .PHI. functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each .PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each .PHI. function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflectin…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.