Super nested block method to minimize coverage testing overhead
A method for determining the number and location of instrumentation probes to be inserted into a program is disclosed. The method advantageously inserts the minimum number of probes that are required to obtain execution coverage for every node in the program's control-flow graph. In addition, the method requires only one bit to store each probe and does not require the assignment of weights to arcs or nodes of the control-flow graph. In the illustrative embodiment, the nodes of a control-flow graph are partitioned into non-empty sets, where each non-empty set corresponds to a super nested block of the program.
1. A method comprising:
while a control-flow graph for a program is generated via a processor:
determining a subset of nodes of the control-flow graph by solving a minimum-cut maximum-flow problem;
partitioning the control-flow graph into subgraphs that correspond to child nodes of the subset of nodes; and
determining a respective partition of each of the subgraphs;
partitioning the program into a plurality of blocks of code based on the respective partition, wherein:
(1) for any two consecutive lines of code within any block belonging to the plurality of blocks, when a first line of the two consecutive lines executes at a first time, the second line of the two consecutive lines executes at a second time later than the first time; and
(2) the any block is not a basic block and
inserting, via the processor, a probe into each of the plurality of blocks of code.
2. The method of claim 1 , wherein inserting the probe is performed while the control-flow graph is generated.
3. The method of claim 1 , wherein determining the respective partition is performed recursively.
4. The method of claim 1 , wherein the control-flow graph is unweighted.
5. The method of claim 1 , further comprising:
while the control-flow graph is generated, marking a node of the control-flow graph with a first type of mark and another node of the control-flow graph with a second type of mark, wherein inserting the probe is based on one of the first type of mark and the second type of mark.
6. A system comprising:
a processor; and
a computer-readable storage memory device storing instructions which, when executed by the processor, cause the processor to perform operations comprising:
while a control-flow graph for a program is generated:
determining a subset of nodes of the control-flow graph by solving a minimum-cut maximum-flow problem;
partitioning the control-flow graph into subgraphs that correspond to child nodes of the subset of nodes; and
determining a respective partition of each of the subgraphs;
partitioning the program into a plurality of blocks of code based on the respective partition, wherein:
(1) for any two consecutive lines of code within any block belonging to the plurality of blocks, when a first line of the two consecutive lines executes at a first time, the second line of the two consecutive lines executes at a second time later than the first time; and
(2) the any block is not a basic block; and
inserting a probe into each of the plurality of blocks of code.
7. The system of claim 6 , wherein inserting the probe is performed while the control-flow graph is generated.
8. The system of claim 6 , wherein determining the respective partition is performed recursively.
9. The system of claim 6 , wherein the control-flow graph is unweighted.
10. The system of claim 6 , wherein the computer-readable storage memory device stores additional instructions which, when executed by the processor, cause the processor to perform the operations further comprising:
while the control-flow graph is generated, marking a node of the control-flow graph with a first type of mark and another node of the control-flow graph with a second type of mark, wherein inserting the probe is based on one of the first type of mark and the second type of mark.
11. A computer-readable storage memory device storing instructions which, when executed by a processor, cause the processor to perform operations comprising:
while a control-flow graph for a program is generated:
determining a subset of nodes of the control-flow graph by solving a minimum-cut maximum-flow problem;
partitioning the control-flow graph into subgraphs that correspond to child nodes of the subset of nodes; and
determining a respective partition of each of the subgraphs;
partitioning the program into a plurality of blocks of code based on the respective partition, wherein:
(1) for any two consecutive lines of code within any block belonging to the plurality of blocks, when a first line of the two consecutive lines executes at a first time, the second line of the two consecutive lines executes at a second time later than the first time; and
(2) the any block is not a basic block; and
inserting a probe into each of the plurality of blocks of code.
12. The computer-readable storage memory device of claim 11 , wherein inserting the probe is performed while the control-flow graph is generated.
13. The computer-readable storage memory device of claim 11 , wherein determining the respective partition is performed recursively.
14. The computer-readable storage memory device of claim 11 , wherein the control-flow graph is unweighted.
15. The computer-readable storage memory device of claim 11 , storing additional instructions which, when executed by the processor, cause the processor to perform the operations further comprising:
while the control-flow graph is generated, marking a node of the control-flow graph with a first type of mark and another node of the control-flow graph with a second type of mark, wherein inserting the probe is based on one of the first type of mark and the second type of mark.