Back to results
US 7,003,760 B1Granted
Method for enhancing pointer analyses
AssigneeMicrosoft Corporation
InventorManuvir Das
Life of this patent
Estimating the term…
Abstract
Methods are described that enhance pointer analysis for programs. Whereas previous methods are constrained by the extremes of an inverse relationship between time and information, the present methods selectively unify information so as to allow a desired level of analytical decision within a desired duration of analysis. One aspect of the present invention includes selectively retaining information at a first order of indirection based on variables in an assignment statement while unifying information at subsequent orders of indirection. The methods are used for pointer variables, but are equally useful to function definitions, function calls, function pointers, indirect function calls, and others. The methods may be used in client analysis tools such as code browsers and slicing tools.
Claims41
A computer-implemented method for enhancing pointer analysis, the method comprising:
- processing an assignment statement between two variables in a program, wherein processing the assignment statement includes forming a relationship between two locations that are related to the two variables, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement, wherein each location includes a label and a content;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying the content of the first one of the two locations with the content of the second one of the two locations.
2 more elements
A computer readable medium having instructions stored thereon for causing a computer to perform a method for enhancing pointer analysis, the method comprising:
- processing an assignment statement between two variables in a program, wherein processing an assignment statement includes forming a relationship between two locations that are related to the two variables, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement, wherein each location includes a label and a content;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying the content of the first one of the two locations with the content of the second one of the two locations.
2 more elements
A computer-implemented method of analyzing pointers in a program, the method comprising:
- forming a location for at least one variable in the program, wherein the location includes a label and a content;
- defining a relationship between two locations upon an assignment statement in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge associates a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer-implemented method of analyzing pointers in a program, the method comprising:
- forming at least one location for at least one variable in the program, wherein the at least one location includes a label and a content;
- forming a relationship between two locations upon an assignment statement of a first variable and a second variable in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement:
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer-implemented method of analyzing pointers in a program, the method comprising:
- forming a location for at least one variable in the program, wherein the location includes a label and a content;
- forming a relationship between two locations upon an assignment statement of a first variable and an address of a second variable in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer-implemented method of analyzing pointers in a program, the method comprising:
- forming a location for at least one variable in the program, wherein the location includes a label and a content;
- forming a relationship between two locations upon an assignment statement of a first variable and a dereference of a second variable in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer-implemented method of analyzing pointers in a program, the method comprising:
- forming a location for at least one variable in the program, wherein the location includes a label and a content;
- forming a relationship between two locations upon an assignment statement of a dereference of a first variable and a second variable in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer readable medium having instructions stored thereon for causing a computer to perform a method of analyzing pointers in a program, the method comprising:
- forming a location for at least one variable in the program, wherein the location includes a label and a content;
- defining a relationship between two locations upon an assignment statement in the program, wherein the two locations are selected to be one level of indirection away from a level associated with the assignment statement;
- defining a flow edge at the one level of indirection away from the level associated with the assignment statement;
- associating the flow edge with the first one of two locations and the second one of two locations, wherein the flow edge is configured to propagate a label of the first one of the two locations to a label of the second one of the two locations such that the label of the first one of the two locations is a subset of the second one of the two locations;
- and
- selectively unifying contents of the two locations.
3 more elements
A computer-implemented method for enhancing pointer analysis, the method comprising:
- processing a plurality of assignment statements between variables in a program to derive a plurality of sets of information, wherein the plurality of sets of information is distributed among a plurality of levels of indirection;
- establishing a plurality of flow relationships between locations that are related to the variables corresponding to each of the plurality of assignment statements, wherein each of the flow relationships is selected to be established one level of indirection away from each of the assignment statements, and wherein the flow relationship includes a flow edge defined at the one level of indirection away from the level associated with the assignment statements and configured to propagate a label such that the label of one of the plurality of sets of information is a subset of another of the plurality of sets of information;
- and
- selectively unifying at least one of the sets of information in at least one level of indirection as at to allow a desired level of analytical precision within a desired duration of pointer analysis.
1 more element
A computer system having a processor and memory for enhancing pointer analysis of a program, wherein the program includes at least one source file, the system comprising:
- a compiler to compile the at least one source file to produce an intermediate language;
- a builder receptive to the intermediate language to build a tree that represents the at least one source file;
- and
- an analyzer to analyze the tree to produce an object file, wherein the object file contains at least one relationship between two locations that are related to two variables in an assignment statement in the program, wherein the relationship includes a flow edge that defines that a set of symbols relating to one of the two variables is a subset of a set of symbols relating to the other of the two variables, wherein the relationship is selectively formed one level of indirection away from a level associated with the assignment statement between the set of symbols related to one of the two variables and the set of symbols relating to the other of the two variables;
- and wherein contents of the two locations are selectively unified.
2 more elements
Dependencies are inferred from the claim text.