Method and apparatus for conflict-based block reordering

• US 5,933,644 A
• Filed: 06/18/1997
• Issued: 08/03/1999
• Est. Priority Date: 06/18/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wallace, David R.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/878,436
• Time in Patent Office: 776 Days
• Field of Search: 395/709, 395/704, 395/183.14, 395/582, 395/584, 395/580-583, 395/588, 395/380-381, 395/390, 395/392
• US Class Current: 717/156
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method and apparatus for ordering blocks of code by a compiler. The compiler generates a conflict graph in accordance with the blocks of a computer program being compiled. Once the conflict graph is generated, a preferred embodiment of the present invention finds maximum weight independent set (MWS) of nodes in the conflict graph. By definition, the nodes in the MWS have no flow control conflicts between them. The compiler then generates an object program having blocks ordered in accordance with the maximum weight independent set.

Claims

1. A method of ordering the blocks of a computer program for efficient execution, the method comprising the steps, performed by a data processing system, of:

dividing the computer program into a plurality of blocks;

generating a control flow graph representing a flow of control between the plurality of blocks;

generating a conflict graph in accordance with the control flow graph, where the edges of the conflict graph indicate which paths in the flow of control have conflicts;

determining a maximum weight independent set of the conflict graph; and

ordering the blocks of the computer program in accordance with the determined maximum weight independent set.

2. The method of claim 1, wherein the step of generating the control flow graph includes the step of generating a weight for each edge of the control flow graph, representing a frequency with which the path corresponding to the edge is entered in the control flow.

3. The method of claim 1, wherein the step of generating the conflict graph includes the step of generating a conflict graph where each node in the conflict graph corresponds to an edge in the control flow graph.

4. The method of claim 1, wherein the step of ordering the blocks is performed in accordance with the maximum weight independent set and the control flow graph.

5. The method of claim 1, wherein the step of determining the maximum weight independent set of the conflict graph includes the step of generating a configuration subgraph for each node in the conflict graph.

6. The method of claim 5, wherein the step of determining the maximum weight independent set of the conflict graph further includes the step of determining a best weight so far for the subgraphs.

7. A method of ordering the blocks of a computer program for efficient execution, the method comprising the steps, performed by a data processing system, of:

dividing the computer program into a plurality of blocks;

generating a control flow graph representing a flow of control between the plurality of blocks;

generating a conflict graph in accordance with the control flow graph, where the edges of the conflict graph indicate which paths in the flow of control have conflicts;

determining a maximum weight independent set of the conflict graph, the determining step including the steps of;

turning an initial node in the conflict graph ON and placing it on a queue in a memory,

removing a next node, v, from the queue,

when the direction of a next node on the queue is ON, and when any neighbor nodes of v are selected and ON, turning the neighbor nodes OFF and placing the neighbor nodes on the queue,

when the direction of a next node on the queue is OFF, and when any neighbor nodes of v are OFF, turning the neighbor nodes ON and placing the neighbor nodes on the queue, and

keeping the highest weight set thus far as the new maximum weight independent set; and

ordering the blocks of the computer program in accordance with the determined maximum weight independent set.

8. The method of claim 7, wherein the step performed when the direction of the next node on the queue is ON, further includes a lookahead test, so that the neighbor nodes are only placed on the queue if they pass the lookahead test.

9. An apparatus that orders the blocks of a computer program for efficient execution, the apparatus comprising:

a portion configured to divide the computer program into a plurality of blocks;

a portion configured to generate a control flow graph representing a flow of control between the plurality of blocks;

a portion configured to generate a conflict graph in accordance with the control flow graph, where the edges of the conflict graph indicate which paths in the flow of control have conflicts;

a portion configured to determine a maximum weight independent set of the conflict graph; and

a portion configured to order the blocks of the computer program in accordance with the determined maximum weight independent set.

10. The apparatus of claim 9, wherein the portion configured to generate the control flow graph includes a portion configured to generate a weight for each edge of the control flow graph, representing a frequency that the path corresponding to the edge is entered in the control flow.

11. The apparatus of claim 9, wherein the portion configured to generate the conflict graph includes a portion configured to generate a conflict graph where each node in the conflict graph corresponds to an edge in the control flow graph.

12. The apparatus of claim 9 wherein the portion configured to order the blocks is coupled to the portion configured to generate a conflict graph and the portion configured to determine a maximum weight independent set, and operates in accordance with the maximum weight independent set and the control flow graph.

13. The apparatus of claim 9, wherein the portion configured to determine the maximum weight independent set of the conflict graph includes a portion configured to generate a configuration subgraph for each node in the conflict graph.

14. The apparatus of claim 13, wherein the portion configured to determine the maximum weight independent set of the conflict graph further includes a portion configured to determine a best weight so far for the subgraphs.

15. A computer program product, including:

a computer usable medium having computer readable code embodied therein for causing ordering of the blocks of a computer program for efficient execution, the computer program product comprising;

computer readable program code devices configured to cause a computer to effect dividing the computer program into a plurality of blocks;

computer readable program code devices configured to cause a computer to effect generating a control flow graph representing the flow of control between the plurality of blocks;

computer readable program code devices configured to cause a computer to effect generating a conflict graph in accordance with the control flow graph, where the edges of the conflict graph indicate which paths in the flow of control have conflicts;

computer readable program code devices configured to cause a computer to effect determining a maximum weight independent set of the conflict graph; and

computer readable program code devices configured to cause a computer to effect ordering the blocks of the computer program in accordance with the determined maximum weight independent set.