Method and system for selecting instrumentation points in a computer program
First Claim
1. In a computer system, a method for determining instrumentation points in a computer program comprising the steps of:
- a) creating a control flow graph for the computer program, the control flow graph including a plurality of nodes, each node connected to at least one other node by a directed edge;
b) selecting a node of the control flow graph as a starting point for a path;
c) beginning with the selected starting point node, following directed edges of the control flow graph in a directed manner to determine which nodes and edges are part of the path,d) after determining which nodes and edges are part of the path, repeating steps b) and c) until every node in the control flow graph is determined to be part of a path, whereby each node is part of only one path, ande) after every node in the control flow graph is determined to be part of a path, selecting as instrumentation points those edges in the control flow graph that are not determined to be part of one of the paths.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention provides a method in a computer system for selecting instrumentation points in a computer program. Instrumentation points are locations within the computer program at which instrumentation code is inserted. The method includes identifying code portions such as basic blocks in the computer program code, creating a control flow graph out of the code portions, generating a spanning tree for the control flow graph, and then selecting those edges of the control flow graph which are not a part of the spanning tree as instrumentation points. After instrumentation points are selected, instrumentation code may be added at those locations. When the computer program is executed, the added instrumentation code records execution information such as how many times an instrumentation point is accessed during execution of the computer program. Using the recorded execution information and direction specified in the control flow graph, execution information for the non-instrumented blocks may then be calculated.
154 Citations
9 Claims
-
1. In a computer system, a method for determining instrumentation points in a computer program comprising the steps of:
-
a) creating a control flow graph for the computer program, the control flow graph including a plurality of nodes, each node connected to at least one other node by a directed edge; b) selecting a node of the control flow graph as a starting point for a path; c) beginning with the selected starting point node, following directed edges of the control flow graph in a directed manner to determine which nodes and edges are part of the path, d) after determining which nodes and edges are part of the path, repeating steps b) and c) until every node in the control flow graph is determined to be part of a path, whereby each node is part of only one path, and e) after every node in the control flow graph is determined to be part of a path, selecting as instrumentation points those edges in the control flow graph that are not determined to be part of one of the paths.
-
-
2. In a computer system, a method for determining which edges in control flow graph should be instrumented to obtain execution counts for each node in the control flow graph, the control flow graph including a plurality of nodes, each node connected to at least one other node by a directed edge, the method comprising the steps of:
-
a) selecting a node in the control flow graph as a starting point for a thread of execution; b) beginning with the selected node, following the directed edges of the control flow graph in a directed manner to determine which nodes and edges are part of the thread of execution; c) after determining which nodes and edges are part of the thread of execution, repeating steps (a) and (b) until every node in the control flow graph is part of a thread of execution, whereby each node is part of only one thread of execution; and d) after all of the threads of execution in the control flow graph are identified, selecting those edges in the control flow graph that are not part of one of the determined threads of execution for instrumentation. - View Dependent Claims (3, 4)
-
-
5. A computer-readable storage device containing instructions for controlling a computer system to determine which edges in control flow graph should be instrumented to obtain execution counts for each node in the control flow graph, the control flow graph including a plurality of nodes, each node connected to at least one other node by a directed edge, by a method comprising the steps of:
-
a) selecting a node in the control flow graph as a starting point for a thread of execution; b) beginning with the selected node, following the directed edges of the control flow graph in a directed manner to determine which nodes and edges are part of the thread of execution; c) after determining which nodes and edges are part of the thread of execution, repeating steps (a) and (b) until every node in the control flow graph is part of a thread of execution, whereby each node is part of only one thread of execution; and d) after all of the threads of execution in the control flow graph are identified, selecting those edges in the control flow graph that are not part of one of the determined threads of execution for instrumentation. - View Dependent Claims (6, 7)
-
-
8. A method in a computer system for identifying instrumentation points for a computer program, the computer program represented by a control flow graph having nodes and edges, each node representing a basic block of the computer program, each edge representing flow control from one basic block to another basic block, the method comprising:
-
designating a root node of the control flow graph to be visited; and repeating the following until all nodes designated to be visited have already been visited, visiting a node designated to be visited that has not yet been visited; and repeat the following until the node currently being visited has already been visited, when an output edge from the currently visited node that does not point to a node that has already been visited, selecting that output edge; identifying the selected output edge as not to be instrumented; when a non-selected output edge points to a node that has not yet been visited, designating the node pointed to by the non-selected edge as to be visited; and visiting the node pointed to by the selected output edge wherein all edges other than those identified as not to be instrumented are instrumented. - View Dependent Claims (9)
-
Specification