Loop allocation for optimizing compilers

• US 6,651,246 B1
• Filed: 05/18/2000
• Issued: 11/18/2003
• Est. Priority Date: 11/08/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Blainey, Robert James, Archambault, Roch Georges
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): STEELMAN, MARY J
• Application Number:
  US09/574,408
• Time in Patent Office: 1,279 Days
• Field of Search: 717/160, 717/149-151, 717/154-157, 717/159, 717/126
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Loop allocation for optimizing compilers includes the generation of a program dependence graph for a source code segment. Control dependence graph representations of the nested loops, from innermost to outermost, are generated and data dependence graph representations are generated for each level of nested loop as constrained by the control dependence graph. An interference graph is generated with the nodes of the data dependence graph. Weights are generated for the edges of the interference graph reflecting the affinity between statements represented by the nodes joined by the edges. Nodes in the interference graph are given weights reflecting resource usage by the statements associated with the nodes. The interference graph is partitioned using a profitability test based on the weights of edges and nodes and on a correctness test based on the reachability of nodes in the data dependence graph. Code is emitted based on the partitioned interference graph.

Claims

1. A computer program product for compilation of a source code segment, said computer program product comprising:

instruction means to generate a program dependence graph for the source code segment, the program dependence graph comprising a control dependence graph and a data dependence graph, each of the control dependence graph and the data dependence graph comprising nodes, each node in the data dependence graph being associated with one or more statements in the source code segment,

instruction means to generate an interference graph from the data dependence graph, comprising

instruction means for deriving nodes for the interference graph from the nodes in the data dependence graph, the nodes in the interference graph thereby each being associated with one or more statements in the source code segment,

instruction means for generating a node weight for each node in the interference graph, each node having a node weight reflecting the resources used by the one or more statements associated with the node,

instruction means for generating edges for the interference graph, each edge connecting a pair of nodes in the interference graph,

instruction means for generating an associated edge weight for each edge reflecting the desirability of maintaining the one or more statements associated with each node of the pair of nodes connected by the edge within the same loop,

instruction means for partitioning the interference graph into subgraphs based on the edge weights and the node weights of the interference graph, and

instruction means for emitting code conforming to the partitioned interference graph.

2. The computer program product of claim 1 in which the instruction means for partitioning the interference graph comprises instruction means for first conducting a profitability test to select a pair of nodes in the interference graph, instruction means for then conducting a correctness test on the selected pair, and instruction means for merging the selected pair of nodes into a coalesced node where the correctness test is satisfied for the selected pair.

3. The computer program product of claim 2 in which the instruction means for conducting a profitability test comprises instruction means for selecting the pair of nodes in the interference graph having the highest associated edge weight, the selected pair of nodes having a sum of node weights lower than a pre-defined resource limit for a target machine for the compiler.

4. The computer program product of claim 2 in which the instruction means for conducting a correctness test comprises instruction means for comparing the selected pair of nodes in the interference graph with nodes in the interference graph corresponding to nodes in the data dependence graph defined to be reachable by the data dependence graph from those nodes in the data dependence graph reachable from the nodes in the data dependence graph corresponding to the selected pair of nodes in the interference graph.

5. The computer program product of claim 4 in which the instruction means for comparing nodes comprises instruction means for defining a test set by generating a merged reachability set by taking the union of the nodes reachable from the selected pair of nodes, and removing the selected pair of nodes, and taking the union of the nodes reachable from the merged reachability set, and comparing the intersection of the test set with the union of the pair of selected nodes with the null set.

6. The computer program product of claim 5 in which each node in the interference graph has an associated reachability vector representing which nodes in the interference graph are reachable from the node and in which set operations to determine reachability of nodes are carried out using the reachability vectors.

7. The computer program product of claim 6 in which the instruction means for generating a program dependence graph comprises instruction means for generating the control dependence graph for a level of nested loops in the source code segment and for then generating corresponding nodes for the data dependence graph for the said level of nested loops, the corresponding nodes in the data dependence graph being defined by constraints determined from the control dependence graph.

8. The computer program product of claim 1 in which the instruction means for generating a program dependence graph comprises instruction means for ordering the generation of the program dependence graph from an innermost level of nested loops in the source code segment to an outermost level of nested loops in the source code segment.

9. The computer program product of claim 8 in which the instruction means for generating a program dependence graph comprises instruction means for determining pi blocks in the segment of source code and in which pi blocks are maintained in the generation of the program dependence graph from an inner level of nested loops to a parent level of nested loops in the source code segment.

10. The computer program product of claim 9 in which the instruction means for emitting code comprises means for generating optimized object code by optimizing for parallelism and for data locality.

11. The computer program product of claim 1 in which the means for emitting code comprises instruction means for generating optimized object code including one or more techniques selected from the set of techniques comprising scalar expansion, usage of temporary storage, array contraction, and strip mining.

12. A loop allocation optimizing compiler comprising, means for generating a program dependence graph for a source code segment, the program dependence graph comprising a control dependence graph and a data dependence graph, each of the control dependence graph and the data dependence graph comprising nodes, each node in the data dependence graph being associated with one or more statements in the source code segment, means for generating an interference graph from the data dependence graph, comprising means for deriving nodes for the interference graph from the nodes in the data dependence graph, the nodes in the interference graph thereby each being associated with one or more statements in the source code segment, means for generating a node weight for each node in the interference graph, each node having a node weight reflecting the resources used by the one or more statements associated with the node, means for generating edges for the interference graph, each edge connecting a pair of nodes in the interference graph, means for generating an associated edge weight for each edge reflecting the desirability of maintaining the one or more statements associated with each node of the pair of nodes connected by the edge within the same loop, means for partitioning the interference graph into subgraphs based on the edge weights and the node weights of the interference graph, comprising means for first conducting a profitability test to select a pair of nodes in the interference graph, means for then conducting a correctness test on the selected pair, and means for merging the selected pair of nodes into a coalesced node where the correctness test is satisfied for the selected pair, and means for emitting code conforming to the partitioned interference graph.

13. The compiler of claim 12 in which the means for conducting a profitability test comprises means for selecting the pair of nodes in the interference graph having the highest associated edge weight, the selected pair of nodes having a sum of node weights lower than a pre-defined resource limit for a target machine for the compiler.

14. The compiler of claim 12 in which the means for conducting a correctness test comprises means for comparing the selected pair of nodes in the interference graph with nodes in the interference graph corresponding to nodes in the data dependence graph defined to be reachable by the data dependence graph from those nodes in the data dependence graph reachable from the nodes in the data dependence graph corresponding to the selected pair of nodes in the interference graph.

15. The compiler of claim 12 in which the means for generating a program dependence graph comprises means for ordering the generation of the program dependence graph from an innermost level of nested loops in the source code segment to an outermost level of nested loops in the source code segment.

16. The compiler system of claim 15 in which the means for generating a program dependence graph comprises means for generating the control dependence graph for a level of nested loops in the source code segment and for then generating corresponding nodes for the data dependence graph for the said level of nested loops, the corresponding nodes in the data dependence graph being defined by constraints determined from the control dependence graph.

17. A method for compiling a source code segment, the method comprising the following steps:

generating a program dependence graph for the source code segment, the program dependence graph comprising a control dependence graph and a data dependence graph, each of the control dependence graph and the data dependence graph comprising nodes, each node in the data dependence graph being associated with one or more statements in the source code segment, causing a computer to generate an interference graph from the data dependence graph, by deriving nodes for the interference graph from the nodes in the data dependence graph, the nodes in the interference graph thereby each being associated with one or more statements in the source code segment and generating a node weight for each node in the interference graph, each node having a node weight reflecting the resources used by the one or more statements associated with the node, generating edges for the interference graph, each edge connecting a pair of nodes in the interference graph, generating an associated edge weight for each edge reflecting the desirability of maintaining the one or more statements associated with each node of the pair of nodes connected by the edge within the same loop, partitioning the interference graph into subgraphs based on the edge weights and the node weights of the interference graph, and emitting code conforming to the partitioned interference graph.

18. The method of claim 17 in which the step of partitioning the interference graph comprises the steps of conducting a profitability test to select a pair of nodes in the interference graph, conducting a correctness test on the selected pair, merging the selected pair of nodes into a coalesced node where the correctness test is satisfied for the selected pair.

19. The method of claim 18 in which the step of conducting the profitability test comprises selecting the pair of nodes in the interference graph having the highest associated edge weight, the selected pair of nodes having a sum of node weights lower than a pre-defined resource limit for a target machine for the compiler.

20. The method of claim 18 in which conducting a correctness test comprises the steps of comparing the selected pair of nodes in the interference graph with nodes in the interference graph corresponding to nodes in the data dependence graph defined to be reachable by the data dependence graph from those nodes in the data dependence graph reachable from the nodes in the data dependence graph corresponding to the selected pair of nodes in the interference graph.

21. The method of claim 20 in which the step of comparing nodes comprises the steps of defining a test set by generating a merged reachability set by taking the union of the nodes reachable from the selected pair of nodes, and removing the selected pair of nodes, and taking the union of the nodes reachable from the merged reachability set, and comparing the intersection of the test set with the union of the pair of selected nodes with the null set.

22. The method of claim 17 in which the step of generating a program dependence graph comprises the steps of generating the program dependence graph from an innermost level of nested loops in the source code segment to an outermost level of nested loops in the source code segment.

23. The method of claim 22 in which the step of generating a program dependence graph comprises the steps of generating the control dependence graph for a level of nested loops in the source code segment and then generating corresponding nodes for the data dependence graph for the said level of nested loops, the corresponding nodes in the data dependence graph being defined by constraints determined from the control dependence graph.

24. The method of claim 23 in which the step of generating a program dependence graph comprises the steps of determining pi blocks in the segment of source code and maintaining pi blocks in the generation of the program dependence graph from an inner level of nested loops to a parent level of nested loops in the source code segment.

25. The method of claim 17 in which the step of emitting code comprises the steps of generating optimized object code by applying one or more techniques selected from the set of techniques comprising scalar expansion, usage of temporary storage, array contraction, and strip mining.

26. The method of claim 17 in which the step of emitting code comprises the steps of generating optimized object code by optimizing for parallelism and for data locality.

27. A computer program product tangibly embodying a program of instructions executable by a computer to perform the method steps of claim 17.

28. A system for compilation of a source code segment, comprising:

means to generate a program dependence graph for the source code segment, the program dependence graph comprising a control dependence graph and a data dependence graph, each of the control dependence graph and the data dependence graph comprising nodes, each node in the data dependence graph being associated with one or more statements in the source code segment, means to generate an interference graph from the data dependence graph, comprising means for deriving nodes for the interference graph from the nodes in the data dependence graph, the nodes in the interference graph thereby each being associated with one or more statements in the source code segment, means for generating a node weight for each node in the interference graph, each node having a node weight reflecting the resources used by the one or more statements associated with the node, means for generating edges for the interference graph, each edge connecting a pair of nodes in the interference graph, means for generating an associated edge weight for each edge reflecting the desirability of maintaining the one or more statements associated with each node of the pair of nodes connected by the edge within the same loop means for partitioning the interference graph into subgraphs based on the edge weights and the node weights of the interference graph, and means for emitting code conforming to the partitioned interference graph.

29. The system of claim 28 in which the means for partitioning the interference graph comprises means for first conducting a profitability test to select a pair of nodes in the interference graph, means for then conducting a correctness test on the selected pair, and means for merging the selected pair of nodes into a coalesced node where the correctness test is satisfied for the selected pair.

30. The system of claim 29 in which the means for conducting a profitability test comprises means for selecting the pair of nodes in the interference graph having the highest associated edge weight, the selected pair of nodes having a sum of node weights lower than a pre-defined resource limit for a target machine for the compiler.

31. The system of claim 29 in which the means for conducting a correctness test comprises means for comparing the selected pair of nodes in the interference graph with nodes in the interference graph corresponding to nodes in the data dependence graph defined to be reachable by the data dependence graph from those nodes in the data dependence graph reachable from the nodes in the data dependence graph corresponding to the selected pair of nodes in the interference graph.

32. The system of claim 31 in which the means for comparing nodes comprises means for defining a test set by generating a merged reachability set by taking the union of the nodes reachable from the selected pair of nodes, and removing the selected pair of nodes, and taking the union of the nodes reachable from the merge reachability set, and comparing the intersection of the test set with the union of the pair of selected nodes with the null set.

33. The system of claim 32 in which each node in the interference graph has an associated reachability vector representing which set nodes in the interference graph are reachable from the node and in which set operations to determine reachability of nodes are carried out using the reachability vetors.