Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system
US5761514A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 31, 1995 |
| Grant date | Jun 2, 1998 |
| Priority date | — |
| Expiry date | Aug 31, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/441
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for truncating runaway lifetimes of program variables calculates liveness for each variable based on upwardly exposed uses. Reaching definitions are then calculated for at least the program variables that have runaway lifetimes. The liveness information is compared to the reaching definition information to determine whether a variable that is live upon entry to a basic block has a definition that reaches the end of each predecessor block, or has a use within the basic block. If the reaching definition for a variable reaches the beginning of the block and if there is a predecessor block for which there is no reaching definition, the variable has a runaway lifetime. The variable also has a runaway lifetime if there is a use of the variable in a block without a reaching definition for the variable at the beginning of the block. The runaway lifetime is truncated by inserting an instruction such as a pseudo-definition of the variable into the instruction stream at an appropriate place. Once runaway lifetimes are truncated using this method, subsequent stages of the compiler may calculate liveness by performing a single dataflow analysis which calculates lifetimes …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.