General purpose intermediate representation of software for software development tools

• US 7,146,606 B2
• Filed: 07/22/2003
• Issued: 12/05/2006
• Est. Priority Date: 06/26/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Grover, Vinod K., Burger, Julian, Mitchell, Charles L., Tarditi, David Read Jr.
• Primary Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US10/625,892
• Publication Number:
  US 20040268331A1
• Time in Patent Office: 1,232 Days
• Field of Search: 717/141
• US Class Current: 717/141
• CPC Class Codes: N/A

Abstract

Various intermediate representation techniques for software development tool scenarios are described. An intermediate representation format can be used for both high level and low level representations. The intermediate representation can be built from various operands and instructions types. Various annotations can be added to the intermediate representation without modifying its format. For example, flow control and data control can be explicitly represented by threading a graph through the intermediate representation.

Claims

1. One or more computer-readable media having encoded thereon computer executable instructions for performing a method to generate an intermediate representation of software, the method comprising:

storing, in a data structure, a plurality of instruction nodes representing a plurality of instructions of the software;

wherein the instruction nodes are operable to represent the instructions in a machine-dependent manner and are further operable to represent the instructions in a machine-independent manner, using a single uniform format for both the instructions represented in the machine-dependant manner and the instructions represented in the machine-independent manner.

2. The computer-readable media of claim 1 wherein instructions are represented by the single uniform format for specifying at least the following for an instruction:

an operator;

any number of or no destination operands associated with the operator via the format; and

any number of or no source operands associated with the operator via the format.

3. The computer-readable media of claim 1 wherein instructions are represented by the single uniform format for specifying an instruction node, zero or more destination operand nodes, and zero or more source operand nodes.

4. The computer-readable media of claim 1 wherein the method further comprises:

storing, in the data structure, a plurality of operand nodes associated with the instruction nodes, wherein the operand nodes represent a plurality of operands of the instructions of the software.

5. The computer-readable media of claim 4 wherein at least one data flow graph is threaded through the operand nodes.

6. The computer-readable media of claim 5 wherein the data flow graph comprises an SSA representation.

7. The computer-readable media of claim 4 wherein the operand nodes are further operable to be annotated to explicitly indicate at least one data flow graph for the software.

8. The computer-readable media of claim 4 wherein the nodes of the data structure are further operable to store information explicitly indicating at least one data flow graph for the software without constructing a separate data structure therefor.

9. The computer-readable media of claim 4 wherein the nodes of the data structure are further operable to store information explicitly indicating at least one control flow graph for the software without constructing a separate data structure for the control flow graph.

10. The computer-readable media of claim 9 wherein the control graph for the software is indicated by associating at least one control flow operation to at least one target label via a control flow edge.

11. The computer-readable media of claim 9 wherein the control graph for the software is indicated by associating at least one exception causing instruction to at least one instance of exception handling code via a control flow edge.

12. The computer-readable media of claim 1 wherein the method further comprises:

storing, in the data structure, a representation of non-instruction data of the software stored as an instruction.

13. The computer-readable media of claim 12 wherein the method further comprises:

storing, in the data structure, a representation of instruction data of the software stored as a data instruction.

14. The computer-readable media of claim 1 wherein:

the data structure represents a lowered form of the software; and

at least one operand preserves type information specified in source code for the software.

15. The computer-readable media of claim 4 wherein:

at least one operand node is annotated with alias information.

16. One or more computer-readable media having encoded thereon computer executable instructions for performing a method comprising:

generating an intermediate representation of software derived from source code; and

generating annotations for a plurality of analyses of the software, wherein a single format accommodates the annotations, and wherein the single format is operable to represent instructions of the intermediate representation in a machine-dependent manner and a machine-independent manner.

17. The computer-readable media of claim 16 wherein the intermediate representation of the software comprises a graph threaded through nodes of the representation.

18. The computer-readable media of claim 17 wherein the graph comprises a control flow graph representing control flow for the software.

19. The computer-readable media of claim 17 wherein the graph comprises a data flow graph representing data flow for the software.

20. One or more computer-readable media having encoded thereon computer executable instructions for performing a method to generate an intermediate representation of software, the method comprising:

storing, in a data structure, a plurality of instruction nodes representing a plurality of instructions of the software, wherein at least one of the instruction nodes represents a control flow instruction and at least one of the instruction nodes represents an opcode, and wherein the plurality of instruction nodes are operable to represent the plurality of instructions in a machine-dependent manner and are further operable to represent the plurality of instructions in a machine-independent manner using a single uniform format for both the plurality of instructions represented in the machine-dependent manner and the plurality of instructions represented in the machine-independent manner;

for at least one of the instruction nodes, storing, in the data structure, one or more source operand nodes and one or more destination operand nodes, wherein at least one of the operand nodes represents a memory location and at least one of the operand nodes represents a label;

storing, in the data structure, one or more links explicitly representing control flow for the software, wherein the control flow includes exception handling control flow;

storing, in the data structure, one or more links explicitly representing data flow for the software;

storing, in the data structure, information associated with at least one operand node indicating alias information for a variable associated with the operand node; and

storing, in the data structure, at least one data instruction node of a same format as the instruction nodes but storing non-instruction data for the software.

21. The computer-readable media of claim 20 wherein the data structure is operable to represent the software in a machine-dependent and a machine-independent manner without changing format.

22. A system for software development, the system comprising:

means for representing software; and

means for analyzing the means for representing to analyze the software represented thereby;

wherein the means for representing is of a single format operable to represent the software in a machine-independent and a machine-dependent manner.

23. A method of processing a data structure storing an intermediate representation of software for a compiler, wherein the intermediate representation is of a single format, the method comprising:

conducting an analysis of the data structure; and

based on the analysis, taking an action without changing the single format;

wherein the single format is operable to represent the software in a machine-dependent and a machine-independent manner.

24. The method of claim 23 wherein the action comprises:

annotating the intermediate representation with data.

25. The method of claim 23 wherein the annotating is done in situ.

26. The method of claim 23 wherein the action comprises:

generating information about the software.

27. The method of claim 26 further comprising:

producing code for the software by traversing the data structure and generating object code for instructions therein.

28. On one or more computer readable media, a software product generated using the method of claim 26.

29. A method of processing a data structure encoded on one or more computer-readable media, wherein the data structure comprises a plurality of nodes, the method comprising:

starting at one of the nodes within the data structure; and

traversing to another of the nodes within the data structure;

wherein;

the data structure stores an intermediate representation of software using a single uniform format to represent both a machine-dependent and a machine-independent form of the software;

the data structure comprises a plurality of nodes representing instructions of the software; and

at least one node representing an instruction is associated with one or more source operands and one or more destination operands.

30. The method of claim 29 wherein the data structure is operable to represent operand types specified in source code in a low level representation of the software.

31. The method of claim 29 wherein the data structure is operable to explicitly represent control flow for the software.

32. The method of claim 31 wherein the control flow comprises exception handling, whereby the data structure is operable to explicitly represent control flow for exception handling of the software.

33. The method of claim 29 wherein the data structure is operable to explicitly represent data flow far the software.

34. The method of claim 29 wherein the data structure is operable to explicitly represent alias information for operands.

35. The method of claim 29 wherein the data structure comprises an association between a use of a variable and a definition of the variable.

36. The method of claim 29 further comprising:

based on analysis of the data structure, annotating the data structure with additional information.

37. The method of claim 36 wherein the annotating comprises associating an operand of one instruction with an operand of another instruction.

38. The method of claim 36 wherein the annotating comprises associating an instruction with another instruction.

39. The method of claim 29 further comprising:

based on analysis of the data structure, adding an instruction to the data structure.

40. The method of claim 29 further comprising:

based on analysis of the data structure, removing an instruction from the data structure.

41. The method of claim 29 further comprising:

based on analysis of the data structure, changing an instruction in the data structure.

42. On one or more computer-readable media, a software product generated using the method of claim 29.

43. A method of representing software, the method comprising:

representing each instruction and data element in a single format operable to represent each instruction and data element of the software in a machine-independent and a machine-dependent manner; and

representing each instruction as a data flow operation effected by execution of the instruction.

44. The method of claim 43 wherein representing each instruction as a data flow operation comprises explicitly representing side effects for the instruction.

45. A software development environment comprising:

one or more software development tools encoded on one or more computer-readable media;

wherein the software development tools are operable to generate or analyze an intermediate representation of software of a single format operable to represent software in a machine-independent and a machine-dependent manner.