Compiling for multiple virtual machines targeting different processor architectures

• US 6,738,967 B1
• Filed: 03/14/2000
• Issued: 05/18/2004
• Est. Priority Date: 03/14/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Radigan, James J.
• Primary Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/524,440
• Time in Patent Office: 1,526 Days
• Field of Search: 717/103, 717/106, 717/118, 717/101, 717/132, 717/137, 717/139, 717/140, 717/145, 717/148, 717/151, 717/157, 717/159, 717/162
• US Class Current: 717/146
• CPC Class Codes: G06F 8/47 Retargetable compilers

Abstract

A developer'"'"'s system compiles a source-language program by parsing it into an intermediate language (IL) program that is independent of the architecture or resources of any particular processor. This system generates a set of machine independent annotations that record attributes and structure of the IL program such as variable definitions and uses. The annotations are in the form of a unique graph structure. Further annotations are used to associate the machine specific optimization information with each of many different microprocessors. The IL program and all the annotations are distributed to multiple user systems having mutually different virtual machines that translate the IL program into object language for their respective different processors. Optimizers in the virtual machines select graph edges based on the machine specific annotations to generate an optimized object program. The translators are table-driven. Entities in the IL program are keyed to entries in a replaceable table in each virtual machine.

Claims

1. A method of compiling a source program prepared in a source language for multiple different processors, the method comprising:

converting the textual source program into an intermediate program comprised of generic abstraction machine instructions that are independent of any particular processor architecture; and

generating and embedding a compact processor-independent graph structure in an extended static single assignment (SSA) form, comprising a plurality of machine independent annotations in the intermediate program and alias information identifying potential optimizations for use by an optimizing translator at a target processor.

2. The method of claim 1 wherein the machine independent annotations comprises use-definition edges of a graph.

3. The method of claim 2 and further comprising tracing possible execution paths between endpoints of an edge to ensure values are not affected.

4. The method of claim 1 wherein the use-definition edges employed herein follow at least one of operators, functions, pointers, or any arbitrarily complex expression.

5. A medium containing computer-readable instructions and data for causing a computer to perform the method of claim 1.

6. The method of claim 1 and further comprising generating machine dependent annotations identifying selected machine independent annotations for use with selected machines.

7. The method of claim 6 and further comprising distributing the intermediate program and the annotations to a plurality of user computer systems.

8. The method of claim 7 where distributing the intermediate program and the annotations comprises packaging them together prior to distribution.

9. The method of claim 8 where the intermediate program and the annotations are distributed via a physical package transferred to users as a single unit.

10. The method of claim 8 where the intermediate program and the annotations are distributed together over a network.

11. The method of claim 1 wherein the machine independent annotations hold locations of definitions and of uses for the program entities.

12. The method of claim 11 where optimizing comprises improving use of the resources of each target processor.

13. The method of claim 12 where optimizing includes improving use of architected registers.

14. The method of claim 11 where optimizing includes unrolling loops.

15. The method of claim 11 where optimizing includes enhancing exploitation of instruction level parallelism.

16. The method of claim 11 where optimizing includes strength reduction, linear test replacement, and induction variable substitution.

17. The method of claim 1 where the annotations include information relating to the definitions and uses of entities of the intermediate program.

18. The method of claim 1, wherein the graph structure in extended SSA form captures all alias relationships in the source program.

19. The method of claim 1, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

20. A method of compiling a source program prepared in a source language for multiple different processors, the method comprising:

identifying potential optimizations in the program which are machine independent; and

generating and embedding a compact processor-independent graph structure in an extended static single assignment (SSA) form, comprising a plurality of graph based annotations and alias information identifying the potential optimizations into the program for use by an optimizing translator at one of multiple different target processors.

21. The method of claim 20 where the optimizations are selected from a group consisting of improving use of architected register, unrolling loops, and exploiting instruction level parallelism.

22. The method of claim 20, wherein the graph structure in extended SSA form captures all alias relationships in the source program.

23. The method of claim 20, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

24. A medium having computer executable instructions stored thereon for causing a computer to perform a method of compiling a source program prepared in a source language for multiple different processors, the method comprising:

identifying potential optimizations in the program which are machine independent; and

generating and embedding a plurality of graph based annotations identifying the potential optimizations into the program for use by an optimizing translator at one of multiple different target processors.

25. A method of compiling a program for one of multiple different processors, comprising:

receiving a program written in an intermediate language;

receiving a compact graph structure in an extended static single assignment (SSA) form, comprising a set of machine independent and machine dependent annotations and alias information identifying optimizations for the program;

generating an object code program from the intermediate language program based on the graph structure in the extended SSA form comprising the set of annotations; and

optimizing the object code program for the one processor of multiple different target processors.

26. A medium containing computer-readable instructions and data for carrying out the method of claim 25.

27. The method of claim 25 where the intermediate program and the set of annotations are received as a single package.

28. The method of claim 27 where the intermediate program and the annotations are received at the same time over a network.

29. The method of claim 25 wherein the machine dependent annotations includes information relating the definitions and uses of entities in the intermediate program with respect to the architecture of one of the multiple different processors.

30. The method of claim 25 where the intermediate language program is a parse tree having a plurality of nodes specifying entities derived from a source program.

31. The method of claim 30 where optimizing the object code program comprises assigning resources of the particular processor to the program entities in response to the selected annotations.

32. The method of claim 25, wherein the graph structure in extended SSA form captures all alias relationships in the program.

33. The method of claim 25, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

34. A system for compiling a source program written in a high-level source language, comprising:

a compiler that translates the source program to an intermediate program in an intermediate language substantially independent of the structure of any particular processor and generates a compact graph structure in an extended static single assignment (SSA) form to annotate the intermediate program with processor independent information and processor dependent information and alias information; and

a plurality of virtual machines for translating the intermediate program into an object program in a low-level object language, the object program being optimized for one of a plurality of different processors in response to the processor-dependent information in a selected one of the annotations.

35. The system of claim 34 further including a plurality of user computer systems having processors of different architectures respectively associated with the translating virtual machines.

36. The system of claim 34 where the low-level object programs are directly executable on their respective processors.

37. The system of claim 34, wherein the graph structure in extended SSA form captures all alias relationships in the source program.

38. The system of claim 34, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

39. A system for compiling a program written in a high-level source language, comprising:

a compiler having;

a translator that translates the source program to an intermediate program in an intermediate language and generates a compact graph structure in an extended static single assignment (SSA) form having annotations and alias information representing potential code optimizations that are independent of the resources of any particular processor, and

a generator that produces a set of machine dependent annotations containing information concerning the use of the potential code optimizations with respect to the resources of architecturally different processors.

40. The system of claim 39 where the annotations hold locations of definitions and of uses for the program entities.

41. The system of claim 39 where the intermediate program is a parse tree having a plurality of nodes.

42. The system of claim 39, wherein the graph structure in extended SSA form captures all alias relationships in the program.

43. The system of claim 39, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

44. A system for executing a program, comprising:

an intermediate program in a tokenized language containing;

a set of annotations containing optimization information related to the intermediate program, a portion of which is independent, and portion of which is dependent upon the resources of one of a plurality of different processors; and

a translator that translates the intermediate program into an object program in a low-level object language executable on one particular processor as a function of the annotations such that the executable is optimized for that particular processor.

45. The system of claim 44 and further comprising storage for holding the intermediate program and the annotations.

46. The system of claim 44 where the annotations contains information concerning locations of definitions and uses of entities within the intermediate program.

47. The system of claim 46 where the translator comprises an optimizer that assigns the entities to specific resources of the one particular processor in accordance with the processor dependent annotations.

48. The system of claim 44 where the translator is driven by a function table.

49. The system of claim 48 where the function table contains a plurality of entries each specifying the name and the definition of a function executed by the optimizer.

50. The system of claim 48, wherein the processor dependent annotations point to entries in the function table.

51. The system of claim 44, wherein the graph structure in extended SSA form captures all alias relationships in the program.

52. The system of claim 44, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

53. A medium containing computer-readable instructions and data for carrying out a method of compiling a program for multiple different processors, the method comprising:

receiving the program in source code;

parsing the source code into a program in an intermediate language that includes optimization information which identifies definitions and uses of entities, and is neutral as to the resources of any of the multiple processors; and

generating a separate set of annotations relating the definitions and uses of entities in the intermediate program, each of the annotations relating the entities of the intermediate-language program to the specific resources of any targeted hardware architecture of multiple different target architectures.

54. A medium containing computer-readable instructions and data for carrying out a method of compiling a program for one of multiple different processors, the method comprising:

receiving a program in an intermediate language;

receiving a set of annotations relating the definitions and uses of entities in the intermediate program that is neutral as to the resources of any of the multiple processors;

selecting one of the annotations corresponding to the one processor; and

translating the intermediate-language program into an object-language executable program in an optimized form on the one processor of multiple different target processors based upon the selected annotation.

55. A computer-readable medium containing computer-readable representations of:

an intermediate program containing optimization information that is substantially independent of the resources of any of a set of specific processors; and

a set of annotations for the intermediate program, each annotation comprising information concerning the structure of the intermediate program with respect to the resources of one of the specific processors of multiple different target processors for executing the program.

56. A computer program stored on a medium, the program comprising:

computer program instructions for execution on a computer processor; and

a data structure comprising;

processor independent computer program annotations that identify potential optimizations for the computer program instructions; and

processor dependent annotations that identify processor independent optimizations for selected processors of multiple different target processors.

57. The computer program of claim 56 wherein the processor independent annotations are embedded into the computer program instructions as edges of a graph.

58. The computer program of claim 57 wherein the edges of the graph are identified by a unique identifier.

59. The computer program of claim 58 wherein the processor dependent annotations identify relevant edges for each processor by use of the unique identifier of each edge.

60. A method of compiling a source program prepared in a source language for multiple different processors, the method comprising:

converting the textual source program into an intermediate program comprised of generic abstraction machine instructions that are independent of any particular processor architecture; and

generating and embedding a compact processor-independent graph structure in an extended static single assignment (SSA) form, comprising a plurality of machine independent annotations in the intermediate program and alias information identifying potential optimizations and constraints for use by an optimizing translator at one of multiple different target processors.

61. The method of claim 60 wherein the optimizations are selected from the group 5 consisting of global redundancy elimination, loop optimization and scheduling machine instructions to exploit parallelism.

62. The method of claim 60 wherein the constraints are selected from the group consisting of output constraints and anti dependency constraints.

63. The method of claim 60 and further comprising generating machine dependent annotations to identify optimizations and constraints that apply to specific machines.

64. A computer readable medium having instructions stored thereon to cause a computer to implement the method of claim 60.

65. The method of claim 60, wherein the graph structure in extended SSA form captures all alias relationships in the source program.

66. The method of claim 60, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

67. A system having computer-readable instructions for causing a computer to compile a source program prepared in a source language for multiple different processors, the system comprising:

means for converting the textual source program into an intermediate program comprised of generic abstraction machine instructions that are independent of any particular processor architecture; and

means for generating and embedding a compact processor-independent graph structure in an extended static single assignment (SSA) form, comprising a plurality of machine independent annotations in the intermediate program and alias information identifying potential optimizations and constraints for use by an optimizing translator at multiple different target processors.

68. The system of claim 67, wherein the graph structure in extended SSA form captures all alias relationships in the source program.

69. The system of claim 67, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.

70. A computer-readable medium containing computer-readable representations of:

an intermediate program containing optimization and constraint information that is substantially independent of the resources of any of a set of specific processors; and

a set of annotations for the intermediate program, each annotation comprising information concerning the structure of the intermediate program with respect to the resources of one of the specific processors for executing the program.

71. The method of claim 70 wherein the optimization is selected from the group consisting of global redundancy elimination, loop optimization and scheduling machine instructions to exploit parallelism, and wherein the constraint is selected from the group consisting of output constraints and anti dependency constraints.

72. A computer program stored on a medium, the program comprising:

computer program instructions for execution on a computer processor; and

a data structure comprising a compact graph structure in an extended static single assignment (SSA) form, comprising;

alias information;

processor independent computer program annotations that identify potential optimizations and constraints for the computer program instructions; and

processor dependent annotations that identify processor independent optimizations for selected processors.

73. The computer program of claim 72, wherein the graph structure in extended SSA form captures all alias relationships in the program.

74. The computer program of claim 72, wherein the graph structure in extended SSA form encodes a plurality of types of edges for all alias relationships.