Method and apparatus for profile-based code placement using a minimum cut set of the control flow graph
US5978588A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Jun 30, 1997 |
| Grant date | Nov 2, 1999 |
| Priority date | — |
| Expiry date | Jun 30, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/445
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus placing blocks of object code by a compiler. The code placement is done optimally, using a "cut set technique" that uses the "max-flow/min-cut" principle. A preferred embodiment of the present invention divides a source program into blocks and generates a control flow graph (cfg) and a data flow graph (dfg) for the blocks. The compiler then identifies the strongly connected components (sccs) of the dfg and recursively breaks down the cycles in each scc to yield a plurality of directed acyclic graphs (dfg-dag's). The compiler then finds the "minimum cut set" in the cfg corresponding to each dfg-dag and moves the code into blocks in accordance with the minimum cut sets. Lastly, the compiler generates object code for the blocks.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.