Retargeting optimized code by matching tree patterns in directed acyclic graphs

• US 6,292,938 B1
• Filed: 12/02/1998
• Issued: 09/18/2001
• Est. Priority Date: 12/02/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Serrano, Mauricio Jose, Sarkar, Vivek, Simons, Barbara Bluestein
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/204,210
• Time in Patent Office: 1,021 Days
• Field of Search: 717/6, 717/7, 717/5
• US Class Current: 717/138
• CPC Class Codes: G06F 8/47 Retargetable compilers

Abstract

An optimizing, compiler that performs retargetable object code generation for a specific processor by matching tree patterns in directed acyclic graphs derived from the source code.

Claims

1. A method of programming a first processor, comprising the steps of:

(a) receiving a series of programming language statements comprising source code into a memory of a second processor;

(b) translating the source code into object code in the memory of the second processor, wherein the translating step comprises the steps of;

(1) generating an intermediate language from the source code in the memory of the second processor, wherein the intermediate language is comprised of one or more directed acyclic graphs (DAGs);

(2) partitioning the DAGs into one or more trees in the memory of the second processor; and

(3) generating the object code in the memory of the second processor, including retargeting the object code to the first processor by matching patterns in the trees of the DAGs.

2. The method of claim 1 above, further comprising the step of identifying legality constraints for the partitioning step.

3. The method of claim 1 above, wherein the DAGs are optimized basic block DAGs.

4. The method of claim 1 above, wherein the partitioning step further comprises the step of partitioning the DAGs into trees that contain only true dependence edges and in which each node has at most one true dependence out-edge.

5. The method of claim 1 above, wherein the tree is a fan-in tree.

6. The method of claim 5 above, wherein the generating step further comprises the step of decomposing the fan-in tree into one or more patterns, which are represented as a second-level partition of each fan-in tree into subtrees.

7. The method of claim 1 above, wherein the partitioning step comprises the step of finding a minimum cost legal two-level partition of the DAG into subtrees.

8. The method of claim 1 above, further comprising the step of selectively performing duplication of the intermediate language to further improve the quality of the generated object code.

9. The method of claim 1 above, further comprising the step of optimizing the intermediate language.

10. The method of claim 1 above, wherein the optimized intermediate code is processor-independent.

11. The method of claim 1 above, further comprising the step of generating one or more pattern matching tables for use by the generating step from a grammar for the first processor.

12. The method of claim 1 above, wherein the first processor is of a different type from the second processor.

13. The method of claim 1 above, wherein the first processor is of a same type as the second processor.

14. An apparatus for programming a first processor, comprising:

(a) a second processor having a memory;

(b) means, performed by the second processor, for receiving a series of programming language statements comprising source code into the memory;

(c) means, performed by the second processor, for translating the source code into object code in the memory of the second processor, wherein the means for translating comprises;

(1) means for generating an intermediate language from the source code in the memory of the second processor, wherein the intermediate language is comprised of one or more directed acyclic graphs (DAGs);

(2) means for partitioning the DAGs into one or more trees in the memory of the second processor; and

(3) means for generating the object code in the memory of the second processor, including retargeting the object code to the first processor by matching patterns in the trees of the DAGs.

15. The apparatus of claim 14 above, further comprising means for identifying legality constraints for the means for partitioning.

16. The apparatus of claim 14 above, wherein the DAGs are optimized basic block DAGs.

17. The apparatus of claim 14 above, wherein the means for partitioning further comprises means for partitioning the DAGs into trees that contain only true dependence edges and in which each node has at most one true dependence out-edge.

18. The apparatus of claim 14 above, wherein the tree is a fan-in tree.

19. The apparatus of claim 14 above, wherein the means for generating further comprises means for decomposing the fan-in tree into one or more patterns, which are represented as a second-level partition of each fan-in tree into subtrees.

20. The apparatus of claim 14 above, wherein the means for partitioning comprises means for finding a minimum cost legal two-level partition of the DAG into subtrees.

21. The apparatus of claim 14 above, further comprising means for selectively performing duplication of the intermediate language to further improve the quality of the generated object code.

22. The apparatus of claim 14 above, further comprising means for optimizing the intermediate language.

23. The apparatus of claim 14 above, wherein the optimized intermediate code is processor-independent.

24. The apparatus of claim 14 above, further comprising means for generating one or more pattern matching tables for use by the means for generating from a grammar for the first processor.

25. The apparatus of claim 14 above, wherein the first processor is of a different type from the second processor.

26. The apparatus of claim 14 above, wherein the first processor is of a same type as the second processor.

27. An article of manufacture embodying logic for programing a first processor, the logic comprising the steps of:

(a) receiving a series of programming language statements comprising source code into a memory of a second processor;

(b) translating the source code into object code in the memory of the second processor, wherein the translating step comprises the steps of;

(1) generating an intermediate language from the source code in the memory of the second processor, wherein the intermediate language is comprised of one or more directed acyclic graphs (DAGs);

(2) partitioning the DAGs into one or more trees in the memory of the second processor; and

(3) generating the object code in the memory of the second processor, including retargeting the object code to the first processor by matching patterns in the trees of the DAGs.

28. The method of claim 27 above, further comprising the step of identifying legality constraints for the partitioning step.

29. The method of claim 27 above, wherein the DAGs are optimized basic block DAGs.

30. The method of claim 27 above, wherein the partitioning step further comprises the step of partitioning the DAGs into trees that contain only true dependence edges and in which each node has at most one true dependence out-edge.

31. The method of claim 27 above, wherein the tree is a fan-in tree.

32. The method of claim 31 above, wherein the generating step further comprises the step of decomposing the fan-in tree into one or more patterns, which are represented as a second-level partition of each fan-in tree into subtrees.

33. The method of claim 27 above, wherein the partitioning step comprises the step of finding a minimum cost legal two-level partition of the DAG;

into subtrees.

34. The method of claim 27 above, further comprising the step of selectively performing duplication of the intermediate language to further improve the quality of the generated object code.

35. The method of claim 27 above, further comprising the step of optimizing the intermediate language.

36. The method of claim 27 above, wherein the optimized intermediate code is processor-independent.

37. The method of claim 27 above, further comprising the step of generating one or more pattern matching tables for use by the generating step from a grammar for the first processor.

38. The method of claim 27 above, wherein the first processor is of a different type from the second processor.

39. The method of claim 27 above, wherein the first processor is of a same type as the second processor.