Region based optimizations using data dependence graphs
US6654952B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 3, 2000 |
| Grant date | Nov 25, 2003 |
| Priority date | — |
| Expiry date | Feb 3, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/433
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Region based optimization may be accomplished by creating dependence graphs for each block and then incrementally computing a single dependence graph for the region. First dependence DAGs are created for each block in the region. This includes defining incoming and outgoing dangling edges for each block. Each dependence DAG is then linked as a control flow graph. Examining of each incoming dangling edge within each block of the region then takes place, with the process traversing each path along the control flow graph in reverse, attempting to match each incoming dangling edge with a corresponding incoming or outgoing dangling edge, stopping only if an outgoing match is found, the same block is examined twice, or the top of the region is found. A similar process takes place for each outgoing dangling edge, traversing each path along the control flow path forward, attempting to match each outgoing dangling edge with a corresponding incoming dangling edge, stopping only if a match is found, the same block is examined twice, or the bottom of the region is found. The region may then be reduced to a single block with incoming dangling edges being any unmatched incoming dangling edges at…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.