Granted Patent B1

US 7,886,272 · App. 11/477,020 · Granted Feb 8, 2011

Abstract

Claims (76)

1. A method for determining a series (S) of one or more code units within program code, comprising:

first determining, by a processor, a plurality of series of code units, wherein for each series of code units, if any one of the code units of the series is executed, then each code unit of the series is executed;

identifying, by the processor, at least one series (So) of the plurality of series of code units, wherein So includes an invocable program block, the invocable program block comprising a set of one or more invocable program elements, wherein the invocable program block has at least one statement that invokes at least one invocable program element, wherein the invocable program element includes one or more members of a group consisting of a function call, a method call, a program call, another invocable program element, and combinations thereof;

second determining, by the processor, a grouping of one or more code units for each of the invocable program elements in the set, wherein the grouping includes at least some of the code units for at least one execution path from a starting code unit for the respective invocable program element to an ending code unit for the respective invocable program element;

executing, by the processor, a relaxed priority estimation, wherein the relaxed priority estimation determines a priority value as a number of code lines that at least will be executed without determining which specific code line will be executed;

based on the relaxed priority estimation, third determining, by the processor, a value for at least one of: the invocable program block and each of the invocation program blocks in the set; and

determining, by the processor, the series S as one of the plurality of series, wherein S is related to the value.

2. The method of claim 1 , wherein the value of an invocable program element is related to a number of members in the corresponding grouping and wherein determining the series S as one of the plurality of series, wherein S is related to the value comprises:

obtaining a priority for each series of the plurality of series, wherein the priority for So is dependent upon the value for at least one member of the set; and wherein S is determined from the priorities.

3. The method of claim 1 , wherein the value for the invocable program element is related to a number of code units executed in a path through the invocable program element.

4. The method of claim 1 , wherein the grouping includes substantially all code units for at least one execution path from a starting code unit for the invocable program element to an ending code unit for the invocable program.

5. The method of claim 1 , wherein the value is dependent upon one or more additional invocable program elements invoked when the code units of the path are executed.

6. The method of claim 2 , wherein the plurality of series comprises a plurality of invocation blocks and wherein third determining a value for at least one of: the invocable program block and each of the invocation program blocks in the comprises the following set of steps performed for each of the invocation blocks and for each of the invocation program elements in the corresponding set:

determine an entry value for an entry code unit; and

add to the entry value a node value corresponding to a super block node identifying the entry code unit, wherein the priority is the sum of the entry and node values.

7. The method of claim 1 , wherein the value is derived from at least one of: (i) a number of lines of source code associated with a corresponding node in a super dominator graph, (ii) the number of object code statements associated with the identified node, and (iii) a number of basic data type fields whose value can change during execution of the code identified by the node.

8. The method of claim 1 , wherein second determining a grouping of one or more code units for each of the invocable program elements in the set comprises the substeps of:

obtaining a representation of a graph, wherein the graph corresponds to a flow graph for the program code, and each node of the graph corresponds to a series of code units of the program code, wherein at least some of the nodes correspond to at least one of an invocation program block and element, and wherein if any one of the code units of the series is executed, then each code unit of the series is executed; and

determining one or more acyclic executable paths through the graph from a predetermined starting node of the graph to a predetermined ending node of the graph; and wherein based on the relaxed priority estimation, third determining a value for eat one of: the invocable program block and each of the invocation program blocks in the set comprises the substeps:

determining, for each of at least some nodes of the graph, a corresponding value, wherein for each node having a corresponding value, the corresponding value is indicative of a number of code units executed when the corresponding series for the node is executed;

determining, for each of the acyclic executable paths, a corresponding path weight, wherein for each executable path (P) having a path weight (Wtp), the path weight Wtp is related to a combination of the values of the nodes of the executable path P; and

sorting the executable paths according to their corresponding path weights; and wherein determining the series S as one of the plurality of series, wherein S is related to the value comprises the substeps:

determining, for each node (N) of the graph, a corresponding priority using the path weight for each of the executable paths containing N; and

determining the series S of code units from the corresponding priorities of the nodes.

9. The method of claim 1 , wherein second determining a grouping of one or more code units for each of the invocable program elements in the set comprises the substeps:

identifying a path through the program code, the path corresponding to a plurality of sets of code units;

determining constraints in the sets of code units that, if satisfied, cause the path to be executed; and

solving the constraints for determining input data to the program code.

10. The method of claim 1 , further comprising:

determining constraints in the code units that, if satisfied, cause the program code to be executed;

determining, for at least one composite data type having an instantiation accessed by the constraints, a range of values for each of at least two non-composite data fields of the instantiation; and

solving the constraints for determining input data to the program code, wherein the range for at least one of the non-composite data fields is used for solving the constraints.

11. The method of claim 1 , further comprising:

compiling the program code into a corresponding second program code having a reduced number data operator types than is used in the original program code, and once compiled, the following steps are performed:

determining constraints in the code units of the second program code that, if satisfied, cause the program code to be executed; and

solving the constraints for determining input data to the program code.

12. A non-transitory computer readable medium, stored on a tangible medium, comprising processor executable instructions to perform the steps of claim 1 .

13. A system that determines a series (S) of one or more code units within program code, comprising:

a processor operable to execute;

a priority estimation component operable to:

determine a plurality of series of code units, wherein for each series of code units, if any one of the code units of the series is executed, then each code unit of the series is executed;

identify at least one series (So) of the plurality of series, wherein So includes an invocable program block, the invocable program block comprising a set of at least one invocable program elements;

determine a grouping of one or more code units for each of the invocable program elements in the set, wherein the grouping includes at least some of the code units for at least one execution path from a starting code unit for the respective invocable program element to an ending code unit for the respective invocable program element, wherein the invocable program element proceeds from a predetermined entry code unit to at least one predetermined exit code unit, and wherein the invocable program element is at least one of a group consisting of a software package, a collection of one or more of class hierarchies, class methods, functions, subprograms, macros, other executable structures that are invoked, and combinations thereof;

executing a relaxed priority estimation, wherein the relaxed priority estimation determines a priority value as a number of code lines that at least will be executed without determining which specific code line will be executed;

based on the relaxed priority estimation, determine a value for at least one of: the invocable program block and the at least one invocation program elements; and

determine the series S as one of the plurality of series, wherein S is related to the value.

14. The system of claim 13 , wherein the value of an invocable program element is related to a number of members in the corresponding grouping and wherein the priority estimation component obtains a priority for each series of the plurality of series, wherein the priority for So is dependent upon the value for at least one member of the set and wherein S is determined from the priorities.

15. The system of claim 13 , wherein the value for the invocable program element is related to a number of code units executed in a path through the invocable program element.

16. The system of claim 13 , wherein the grouping includes substantially all code units for at least one execution path from a starting code unit for the invocable program element to an ending code unit for the invocable program.

17. The system of claim 13 , wherein the value is dependent upon one or more additional invocable program elements invoked when the code units of the path are executed.

18. The system of claim 14 , wherein the plurality of series comprises a plurality of invocation blocks and wherein determine a value for at least one of: the invocable program block and the at least one invocation program elements comprises the following set of sub-operations performed for each of the invocation blocks and for each of the invocation program elements in the corresponding set:

determine an entry value for an entry code unit; and

add to the entry value a node value corresponding to a super block node identifying the entry code unit, wherein the priority is the sum of the entry and node values.

19. The system of claim 13 , wherein the value is derived from at least one of:

(i) a number of lines of source code associated with a corresponding node in a super dominator graph, (ii) the number of object code statements associated with the identified node, and (iii) a number of basic data type fields whose value can change during execution of the code identified by the node.

20. The system of claim 13 , wherein determine a grouping of one or more code units for each of the invocable program elements in the set comprises the sub-operations of:

obtaining a representation of a graph, wherein the graph corresponds to a flow graph for the program code, and each node of the graph corresponds to a series of code units of the program code, wherein at least some of the nodes correspond to at least one of an invocation program block and element, and wherein if any one of the code units of the series is executed, then each code unit of the series is executed; and

determining one or more acyclic executable paths through the graph from a predetermined starting node of the graph to a predetermined ending node of the graph; and wherein based on the relaxed priority estimation, third determining a value for eat one of: the invocable program block and each of the invocation program blocks in the set comprises the substeps:

determining, for each of at least some nodes of the graph, a corresponding value, wherein for each node having a corresponding value, the corresponding value is indicative of a number of code units executed when the corresponding series for the node is executed;

determining, for each of the acyclic executable paths, a corresponding path weight, wherein for each executable path (P) having a path weight (Wtp), the path weight Wtp is related to a combination of the values of the nodes of the executable path P; and

sorting the executable paths according to their corresponding path weights; and wherein determining the series S as one of the plurality of series, wherein S is related to the value comprises the substeps:

determining, for each node (N) of the graph, a corresponding priority using the path weight for each of the executable paths containing N; and

determining the series S of code units from the corresponding priorities of the nodes.

21. The system of claim 13 , further comprising:

a constraint analysis subsystem operable to:

identify a path through the program code, the path comprising a number of sets of code units;

determine constraints in the sets of code units that, if satisfied, cause the path to be executed; and

solve the constraints for determining input data to the program code.

22. The system of claim 13 , further comprising:

a constraint analysis subsystem operable to:

determine constraints in the code units that, if satisfied, cause the program code to be executed;

determine, for at least one composite data type having an instantiation accessed by the constraints, a range of values for each of at least two non-composite data fields of the instantiation; and

solve the constraints for determining input data to the program code, wherein the range for at least one of the non-composite data fields is used for solving the constraints.

23. The system of claim 13 , further comprising: a code translator operable to translate the program code into a corresponding second program code having a reduced number data operator types than is used in the original program code, and a constraint analysis subsystem operable, once the program code is translated, to:

determine constraints in the code units of the second program code that, if satisfied, cause the program code to be executed; and

solve the constraints for determining input data to the program code.

Assignments (15)