Method and system for probe optimization while instrumenting a program

• US 20050229165A1
• Filed: 04/07/2004
• Published: 10/13/2005
• Est. Priority Date: 04/07/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schertz, Stephen Craig, Ma, Kenneth Kai-Baun
• Granted Patent: US 7,590,521 B2
• Time in Patent Office: Days
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3676 for coverage analysis

Abstract

A method and system is provided for instrumenting a program by optimizing probe insertion. The number of probe insertions into instrumented code is reduced by providing optimal probe insertion points. The control flow of the code is analyzed along with the arc and block relationships to build a post-dominator tree. An optimization map is generated from the post-dominator tree that provides the optimal probe insertion points. Once the probes are inserted and data is collected by running the binary representing the code and probes, the data may be overlaid onto the optimization map and arc and block relationships to provide code coverage data.

Claims

1. A computer-implemented method for instrumenting a program, comprising:

examining a post-dominator tree associated with a function of a program;

determining a probe insertion into the program according to the post-dominator tree; and

inserting the probe into the program.

2. The computer-implemented method of claim 1, further comprising generating the post-dominator tree from a control flow graph associated with the program.

3. The computer-implemented method of claim 2, further comprising building an arc to block map from the control flow graph, such that when data is received from the probe, the data is overlaid on the arc to block map to discover arc and block coverage data for the program.

4. The computer-implemented method of claim 1, further comprising building an optimization map according to the post-dominator tree, wherein the optimization map includes an entry corresponding to the probe.

5. The computer-implemented method of claim 4, further comprising examining the program for a back edge and adding an entry to the optimization map that corresponds to the back edge, such that a second probe insertion is made that corresponds to the location of the back edge in the program.

6. The computer-implemented method of claim 4, further comprising examining the program for a call and adding an entry to the optimization map that corresponds to the call, such that a second probe insertion is made that corresponds to the location of the call in the program.

7. The computer-implemented method of claim 4, further comprising examining the program for an external entry point and adding an entry to the optimization map that corresponds to the external entry point, such that a second probe insertion is made that corresponds to the location of the external entry point in the program.

8. The computer-implemented method of claim 4, further comprising overlaying data received from the probe onto the optimization map to determine an arc relationship for the probe, wherein the arc relationship provides code coverage data for the program.

9. The computer-implemented method of claim 1, wherein the probe corresponds to a leaf node that is present within the post-dominator tree.

10. A computer-readable medium that includes computer-executable instructions for instrumenting a program, comprising:

examining a post-dominator tree associated with a function of a program;

building an optimization map that corresponds to the post-dominator tree, wherein the optimization map includes entries corresponding to leaf nodes within the post-dominator tree; and

inserting probes into the program corresponding to each entry of the optimization map.

11. The computer-readable medium of claim 10, further comprising generating the post-dominator tree from a control flow graph associated with the program.

12. The computer-readable medium of claim 11, further comprising building an arc to block map from the control flow graph, such that when data is received from the probes, the data is overlaid on the arc to block map to discover arc and block coverage data for the program.

13. The computer-readable medium of claim 10, further comprising examining the program for back edges and adding entries to the optimization map that correspond to the back edges, such that some of the probes inserted into the program are inserted corresponding to the locations of the back edges in the program.

14. The computer-readable medium of claim 10, further comprising examining the program for calls and adding entries to the optimization map that correspond to the calls, such that some of the probes inserted into the program are inserted corresponding to the locations of the calls in the program.

15. The computer-readable medium of claim 10, further comprising examining the program for external entry points and adding entries to the optimization map that correspond to the external entry points, such that some of the probes inserted into the program are inserted corresponding to the locations of the external entry points in the program.

16. The computer-readable medium of claim 10, further comprising overlaying data received from the probes onto the optimization map to determine arc relationships for the probes, wherein the arc relationships provide code coverage data for the program.

17. A system for instrumenting a program, comprising:

a computing device that includes an application that is configured to;

calculate a control flow graph corresponding to the program;

build a post-dominator tree that corresponds to the control flow graph;

build an optimization map that corresponds to the post-dominator tree, wherein the optimization map includes entries corresponding to leaf nodes within the post-dominator tree;

insert probes into the program corresponding to each entry of the optimization map; and

overlay data received from the probes after execution of the program onto the optimization map to provide code coverage data for the program.

18. The system of claim 17, wherein the application is further configured to examine the program for back edges and adding entries to the optimization map that correspond to the back edges, such that some of the probes inserted into the program are inserted corresponding to the locations of the back edges in the program.

19. The system of claim 17, wherein the application is further configured to examine the program for calls and adding entries to the optimization map that correspond to the calls, such that some of the probes inserted into the program are inserted corresponding to the locations of the calls in the program.

20. The system of claim 17, wherein the application is further configured to examine the program for external entry points and adding entries to the optimization map that correspond to the external entry points, such that some of the probes inserted into the program are inserted corresponding to the locations of the external entry points in the program.

21. The system of claim 17, wherein the application is further configured to build an arc map and a block map that each correspond to the control flow graph, such that the arc map and block map cross-reference the arc and block relationships for the control flow graph.

22. The system of claim 21, wherein the application is further configured to overlay the data overlaid onto optimization map onto the arc map and block map to refine the code coverage data for the program.

23. The system of claim 21, wherein the probes are included into the post-dominator tree such that duplication of probe mapping to arcs and blocks of code is prevented.