Intermediate language representation and modification

• US 8,875,111 B2
• Filed: 04/23/2009
• Issued: 10/28/2014
• Est. Priority Date: 04/23/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dubinsky, Leon, Lyon-Smith, John
• Primary Examiner(s): Mitchell, Jason
• Assistant Examiner(s): APONTE, FRANCISCO JAVIER
• Application Number:
  US12/428,489
• Publication Number:
  US 20100275188A1
• Time in Patent Office: 2,014 Days
• Field of Search: 717101-178, 703/6, 703/22, 715771-772, 718/102, 711/147, 716/103, 702/108, 702/125
• US Class Current: 717/144
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

A system and method for facilitating analysis and modification of a computer program. A directed graph is generated from an intermediate language representation of a computer program function, with a node representing each instruction. Meta-edges or meta-nodes are inserted into the directed graph to facilitate location of instruction nodes. One type of meta-edge is a back edge that identifies branch instruction nodes. Some meta-nodes may identify instructions of a specific type. Some meta-nodes may identify exception blocks and corresponding handlers. Analysis of a program function may include insertion of new instructions prior to execution of the function.

Claims

1. A computer-implemented method for modifying execution of a computer program function having a plurality of instructions, comprising:

a) in response to detecting an invocation of the computer program function, generating a directed graph representing the computer program function, the directed graph including a plurality of instruction nodes, each instruction node representing a corresponding instruction of the plurality of instructions;

b) inserting, into the directed graph, one or more meta-nodes, the one or more meta-nodes including a first edge to an instruction node of the directed graph corresponding to an instruction of an exception block and a second edge to an instruction node of the directed graph corresponding to a handler associated with the exception block; and

c) employing the one or more meta-nodes to perform at least one of adding or removing at least one other instruction node to the directed graph; and

d) translating the directed graph to an intermediate language representation of the computer program function.

2. The method of claim 1, further comprising translating the intermediate language representation of the computer program function into a native code representation of the computer program function.

3. The method of claim 2, further comprising translating the intermediate language representation to a native code representation and executing the native code representation.

4. The method of claim 1, further comprising:

a) inserting, into the directed graph, one or more back edges that point from an instruction node representing a target of a branch instruction to an instruction node representing the branch instruction;

b) manipulating the directed graph by employing the one or more back edges to perform at least one of adding or removing at least one additional instruction node to the directed graph.

5. A computer-implemented method for modifying execution of a computer program function having a plurality of instructions, comprising:

a) in response to detecting an invocation of the computer program function, generating a directed graph representing the computer program function, the directed graph including a plurality of instruction nodes, each instruction node representing a corresponding instruction of the plurality of instructions;

b) inserting, into the directed graph, a type meta-node corresponding to a type of instruction, the type meta-node pointing to a plurality of associated instruction nodes of the directed graph, each associated instruction node representing a corresponding instruction of the type corresponding to the type meta-node;

c) employing the type meta-node to perform at least one of adding or removing at least one other instruction node to the directed graph; and

d) translating the directed graph to an intermediate language representation of the computer program function;

wherein the type corresponding to the type meta-node is at least one of a branch instruction, an exception block beginning, an exception block ending, an exception handler beginning, or an object allocation instruction.

6. The method of claim 5, further comprising scanning an intermediate language representation of the computer program function in one pass, and generating the directed graph, inserting the one or more back edges, and inserting the one or more meta-nodes during the scan of the intermediate language.

7. The method of claim 5, wherein the type of instruction is a branch instruction or a function invocation instruction, and the at least one other instruction node represents at least one instruction for determining a flow of the computer program during a subsequent execution.

8. The method of claim 5, translating the directed graph to the intermediate language representation comprising employing the type meta-node to insert an offset of a first instruction into a second instruction that references the first instruction.

9. A hardware computer-readable storage device comprising computer program instructions for enabling execution of a computer program function having a plurality of instructions including at least one branch instruction and at least one exception handler, the program instructions executable by a processor to perform actions including:

a) in response to detecting an invocation of the computer program function, generating a data structure representing the computer program function, the data structure including at least one directed graph, each of the plurality of instructions represented by a corresponding instruction node of the at least one directed graph;

b) inserting, into the at least one directed graph, a back edge corresponding to each target of each branch instruction, the back edge indicating an instruction node representing the branch instruction corresponding to the target;

c) employing the back edge to insert at least one instruction node into the at least one directed graph;

d) inserting, into the at least one directed graph, at least one instruction type meta-node, each instruction type meta-node having one or more edges to a corresponding one or more instruction nodes of the at least one directed graph, the one or more instruction nodes representative of a type of instruction corresponding to the instruction type meta-node;

e) employing the one or more edges of the at least one instruction type meta-node to insert at least one other instruction node into the at least one directed graph; and

f) translating the data structure to an intermediate language representation of the computer program function.

10. The hardware computer-readable device of claim 9, the actions further including:

a) generating an exception block meta-node including an exception block edge that points to a node of an exception block and an exception handler edge that points to a node of an exception handler; and

b) employing the exception block meta-node to insert an instruction node into the directed graph.

11. The hardware computer-readable storage device of claim 9, the at least one other instruction node representing at least one instruction for performing an analysis of the program function, the analysis including at least one of fault injection or memory analysis.

12. The hardware computer-readable storage device of claim 9, the actions further including translating the intermediate language representation to a native code representation of the computer program function and enabling execution of the computer program function.

13. The hardware computer-readable storage device of claim 9, the action further including generating the at least one directed graph, inserting the back edge, and inserting the instruction type meta-node by performing a single scan of a representation of the computer program function.

14. A computer-based system for translating and executing a computer program, comprising:

a) a run-time manager that in response to an invocation of a computer program function, generating a directed graph representing the computer program function, the directed graph including at least one instruction type meta-node pointing to at least one node representing an instruction of a designated type and further including an exception meta-node with a first edge to an exception block and a second edge to an exception handler corresponding to the exception block;

b) an application that modifies the directed graph to insert one or more nodes representative of one or more program instructions for performing analysis of the computer program function; and

c) a code generator that translates the directed graph to an executable representation of the computer program function; and

d) a hardware processor that executes an executable representation of the computer program function;

wherein the runtime manager manages execution of the executable representation of the computer program function.

15. The system of claim 14, wherein the run-time manager generates the directed graph and inserts an instruction node that is a target of each of two other instruction nodes by performing a single scan of an intermediate language representation of the computer program function.

16. The system of claim 14, the exception meta-node having a third edge to an end of the exception handler.

17. The system of claim 14, the directed graph further including at least one back edge pointing from a target instruction node to a corresponding instruction node representing a branch instruction directed to the target instruction node.

18. The system of claim 14, the directed graph further including at least two back edges, each back edge pointing from a first target instruction node to a corresponding instruction node representing a branch instruction, the application including program instructions to perform actions including inserting a second target instruction node prior to the first target instruction node, employing the at least two back edges to modify the instruction nodes representing the branch instructions to point to the second target instruction node.

19. The system of claim 14, the directed graph further including an allocation meta-node pointing to one or more object allocation instruction nodes.