Anticipatory optimization with composite folding

• US 6,745,384 B1
• Filed: 09/21/2000
• Issued: 06/01/2004
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Biggerstaff, Ted J.
• Primary Examiner(s): DAS, CHAMELI
• Application Number:
  US09/667,958
• Time in Patent Office: 1,349 Days
• Field of Search: 717/110, 717/140, 717/139, 717/150, 717/154, 717/160, 717/146, 717/136, 717/137, 717/161, 717/151, 717/100, 717/155, 717/156, 717/157, 709/100, 712/203, 712/209, 712/212
• US Class Current: 717/156
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A method and system for anticipatory optimization of computer programs. The system generates code for a program that is specified using programming-language-defined computational constructs and user-defined, domain-specific computational constructs, the computational constructs including high-level operands that are domain-specific composites of low-level computational constructs. The system generates an abstract syntax tree (AST) representation of the program in a loop merging process. The AST has nodes representing the computational constructs of the program and abstract optimization tags for folding of the composites. A composite folding process is applied to the AST according to the optimization tags to generate optimized code for the program. The composite folding process includes identifying an optimization event, identifying each abstract optimization tag applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation, and attempting execution of each of the anticipated optimization transformations associated with the optimization event.

Claims

1. A method in a computer system for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the programming-language-defined computational constructs defining a data flow and including high-level operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, the method comprising:

identifying selected domain-specific composites within the programming-language-defined computational constructs; and

applying one or more abstract optimization tags to the programming-language-defined computational constructs in association with the selected domain-specific composites, the one or more abstract optimization tags identifying one or more anticipated optimization transformations for modifying the data flow in the translation from the high-level program to the low-level program.

2. The method of claim 1 in which the composites include separate components and modifying the data flow in the translation from the high-level program to the low-level program includes melding the separate components from different composites.

3. The method of claim 1 in which the composites include separate components and modifying the data flow in the translation from the high-level program to the low-level program includes reorganizing components from the composites.

4. The method of claim 1 in which the data flow defined by the high-level computational constructs includes a shared storage element and modifying the data flow in the translation from the high-level program to the low-level program includes elimination of the shared storage element.

5. The method of claim 1 in which the data flow defined by the high-level computational constructs includes plural loop structures and modifying the data flow in the translation from the high-level program to the low-level program includes identifying at least one of the loop structures as redundant and eliminating the redundant loop structure.

6. The method of claim 1 further comprising inlining the programming-language-defined computational constructs to form an inlined representation of the programming-language-defined computational constructs with the one or more abstract optimization tags to the programming-language-defined computational constructs in association with the selected domain-specific composites.

7. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a contract standard establishing selected data flow requirements between the low-level computational constructs.

8. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a contract standard establishing selected data reference requirements between the low-level computational constructs.

9. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a confinement property contract standard confining relationships between domain specific operator and operand definitions to predetermined, fixed relationships.

10. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a confined referential transparency property contract standard establishing that symbolic values that are equal in different expressions may be used interchangeably between those expressions.

11. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a common canonical quantification property contract standard establishing a common canonical form for quantified computations on shared data in a composite method and a domain specific operator.

12. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a problem specific notational extensions property contract standard establishing a notation in which operator implementations and composite methods can express relevant relationships among parameters, global variables, and local variables.

13. The method of claim 1 further comprising defining the domain-specific composites of low-level computational constructs in accordance with a single assignment property contract standard establishing that each assignment of a value to a shared variable shall be accomplished by a single assignment.

14. The method of claim 1 further comprising:

generating an abstract syntax tree (AST) representation of the programming-language-defined computational constructs, the AST having nodes representing the computational constructs of the program; and

applying the one or more abstract optimization tags to the programming-language-defined computational constructs includes applying the optimization tags to the AST.

15. The method of claim 1 in which the domain-specific composites are of the graphics imaging domain.

16. In a computer readable data storage medium having therein a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the programming-language-defined computational constructs including high-level operands that are composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, an optimization tag data structure, comprising:

an anticipated optimization transformation in the translation from the high-level program to the low-level program; and

a transformation condition identifying a condition for attempting the anticipated optimization in the translation from the high-level program to the low-level program.

17. The medium of claim 16 wherein the transformation condition relates to a localized condition in the high-level program.

18. The medium of claim 16 wherein the transformation condition relates to a cross-operator condition in the high-level program.

19. The medium of claim 16 wherein the transformation condition relates to a condition indicating finalization of the optimization of the high-level program.

20. The medium of claim 16 wherein the optimization transformation effects a folding of composites within the programming-language-defined computational constructs.

21. The medium of claim 16 wherein the optimization transformation includes merging conditions within different composites within the programming-language-defined computational constructs.

22. The medium of claim 16 wherein composites of the programming-language-defined computational constructs include computational conditions and the optimization transformation includes merging computational conditions within different composites of the programming-language-defined computational constructs.

23. The medium of claim 16 wherein composites of the programming-language-defined computational constructs include computational loops with conditions therein and the optimization transformation includes promoting the conditions above the computational loops.

24. The medium of claim 16 wherein a composite of the programming-language-defined computational constructs includes an undefined term and the optimization transformation includes removing the undefined term.

25. The medium of claim 16 wherein a composite of the programming-language-defined computational constructs includes a user-definable small number of terms and the optimization transformation includes unfolding the computational construct.

26. The medium of claim 16 wherein the transformation condition relates to a scheduled event in optimization of the program.

27. The medium of claim 16 wherein the transformation condition relates to an unscheduled event in optimization of the program.

28. The medium of claim 16 wherein the transformation condition is parameterized to define an ordering preference for the optimization transformations.

29. The medium of claim 16 wherein the optimization transformation relates to a computer processing format.

30. The medium of claim 29 wherein the optimization transformation relates to a sequential computer processing format.

31. The medium of claim 29 wherein the optimization transformation relates to a vector computer processing format.

32. In a computer readable data storage medium software instructions for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the programming-language-defined computational constructs defining a data flow and including high-level operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, comprising:

software instructions for applying one or more abstract optimization tags to the programming-language-defined computational constructs in association with the selected domain-specific composites, the one or more abstract optimization tags identifying one or more anticipated optimization transformations for modifying the data flow in the translation from the high-level program to the low-level program.

33. The medium of claim 32 in which each of the one or more abstract optimization tags includes a transformation condition identifying a condition for attempting the anticipated optimization in the translation from the high-level program to the low-level program.

34. The medium of claim 33 wherein at least one transformation condition relates to a localized condition in the high-level program.

35. The medium of claim 33 wherein at least one transformation condition relates to a cross-operator condition in the high-level program.

36. The medium of claim 33 wherein at least one transformation condition relates to a condition indicating finalization of the optimization of the high-level program.

37. The medium of claim 33 wherein the transformation condition relates to a scheduled event in optimization of the program.

38. The medium of claim 33 wherein the transformation condition relates to an unscheduled event in optimization of the program.

39. The medium of claim 33 wherein the transformation condition is parameterized to define an ordering preference for the optimization transformations.

40. The medium of claim 32 wherein the optimization transformation effects a folding of composites within the programming-language-defined computational constructs.

41. The medium of claim 32 wherein the optimization transformation relates to a sequential computer processing format.

42. The medium of claim 32 wherein the optimization transformation relates to a vector computer processing format.

43. A method for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the programming-language-defined computational constructs including high-level operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, comprising:

identifying an optimization event;

identifying each abstract optimization tag applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation; and

attempting execution of each of the anticipated optimization transformations associated with the optimization event.

44. The method of claim 43 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which the anticipated optimization transformations are attempted in the sequential order of the optimization tags.

45. The method of claim 43 in which the optimization event is a scheduled event that occurs upon a scheduled basis.

46. The method of claim 43 in which the optimization event is an unscheduled event that does not occur upon a scheduled basis.

47. The method of claim 46 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which the anticipated optimization transformations associated with unscheduled events are attempted in the sequential order of the optimization tags.

48. The method of claim 43 in which the transformation condition includes a logical combination of plural conditions.

49. A method in a computer system for generating code for a program, the program being specified using programming-language-defined computational constructs and user-defined, domain-specific computational constructs, the computational constructs including high-level operands that are domain-specific composites of low-level computational constructs, the method comprising:

generating in a loop merging process an abstract syntax tree (AST) representation of the program, the AST having nodes representing the computational constructs of the program and abstract optimization tags for folding of the composites; and

applying a composite finding process to the AST according to the optimizations tags to generate optimized code for the program.

50. The method of claim 49 wherein the composite folding process includes:

identifying an optimization event;

identifying each abstract optimization tag, applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation; and

attempting execution of each of the anticipated optimization transformations associated with the optimization event.

51. The method of claim 49 wherein the computer system uses multiple phases and each user-defined, domain-specific transform has an associated phase during which it can transform the AST.

52. The method of claim 49 in which the optimization event is a scheduled event that occurs, upon a scheduled basis.

53. The method of claim 49 in which the optimization event is an unscheduled event that does not occur upon a scheduled basis.

54. A method for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the high-level computational constructs including high-level operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, comprising:

identifying an optimization event;

identifying each abstract optimization tag applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation, the abstract optimization tags being arranged in the programming-language-defined computational constructs in a sequential order; and

attempting execution of each of the anticipated optimization transformations associated with the optimization event, at least a pair of the anticipated optimization transformations being attempted in an indicated sequential order different from the sequential order of the optimization tags.

55. The method of claim 54 in which the optimization event is a scheduled event that occurs upon a scheduled basis.

56. The method of claim 54 in which the optimization event is an unscheduled event that does not occur upon a scheduled basis.

57. The method of claim 56 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which the anticipated optimization transformations associated with unscheduled events are attempted in the sequential order of the optimization tags.

58. The method of claim 57 in which an attempt of the anticipated optimization transformation associated with the unscheduled event interrupts the attempt of the anticipated optimization transformation associated with the scheduled event.

59. The method of claim 54 in which the transformation condition includes a logical combination of plural conditions.

60. The method of claim 54 in which at least one of the optimization tags is generated automatically in response to the optimization transformation in another of the optimization tags.

61. A method for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the high-level computational constructs including high-level, operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, comprising:

identifying an optimization event including an unscheduled event that does not occur upon a scheduled basis;

identifying each abstract optimization tag applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation, the abstract optimization tags being arranged in the programming-language-defined computational constructs in a sequential order; and

attempting execution of each of the anticipated optimization transformations associated with the optimization event, the anticipated optimization transformations associated with unscheduled events being attempted in the sequential order of the optimization tags and an attempt of the anticipated optimization transformation associated with the unscheduled event interrupting the attempt of the anticipated optimization transformation associated with the scheduled event.

62. The method of claim 61 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which at least a pair of the anticipated optimization transformations are attempted in an indicated sequential order different from the sequential order of the optimization tags.

63. The method of claim 61 in which the transformation condition includes a logical combination of plural conditions.

64. The method of claim 61 in which at least one of the optimization tags is generated automatically in response to the optimization transformation in another of the optimization tags.

65. A method for generating code for a high-level program that is specified using programming-language-defined computational constructs and that is to be translated into a low-level computer program using low-level computational constructs, the high-level computational constructs including high-level operands that are domain-specific composites of low-level computational constructs and including high-level operators for indicating operations on the high-level operands, comprising:

identifying an optimization event;

identifying each abstract optimization tag applied to the programming-language-defined computational constructs and having a transformation condition identifying the optimization event as a condition for attempting an anticipated optimization in the translation, at least one of the optimization tags being generated automatically in response to the optimization transformation in another of the optimization tags; and

attempting execution of each of the anticipated optimization transformations associated with the optimization event.

66. The method of claim 65 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which the anticipated optimization transformations are attempted in the sequential order of the optimization tags.

67. The method of claim 65 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which at least a pair of the anticipated optimization transformations are attempted in an indicated sequential order different from the sequential order of the optimization tags.

68. The method of claim 65 in which the optimization event is a scheduled event that occurs upon a scheduled basis.

69. The method of claim 65 in which the optimization event is an unscheduled event that does not occur upon a scheduled basis.

70. The method of claim 69 in which the abstract optimization tags are arranged in the programming-language-defined computational constructs in a sequential order and in which the anticipated optimization transformations associated with unscheduled events are attempted in the sequential order of the optimization tags.

71. The method of claim 70 in which an attempt of the anticipated optimization transformation associated with the unscheduled event interrupts the attempt of the anticipated optimization transformation associated with the scheduled event.

72. The method of claim 65 in which the transformation condition includes a logical combination of plural conditions.