Scalable propagation-based methods for call graph construction
AssigneeInternational Business Machines Corporation
InventorsFrank Tip, Jens Palsberg
Life of this patent
Estimating the term…
Abstract
A program storage device, readably by a machine, tangibly embodying instructions to perform method steps for constructing a call graph whereby for each method M, a set of types SM of objects that may occur in method M is determined for each field F, a set of types SF of objects is determined that may be stored in field F, the method comprising: determining the allocation sites inside the body of method M; determining the set of directly called methods M′ inside the body of method M; and determining the set of virtually called methods M″ inside the body of method M.
Claims18
A program storage device, readable by a machine, tangibly embodying programming instructions to perform method steps for constructing a set of types occurring within a method, the programming instructions comprising:
- selecting a program P for constructing a call graph representation thereof;
- wherein the program P contains zero or more fields FF and at least two methods MM;
- wherein each method M1 in MM has a single body B;
- constructing for each method M in MM, a set of types SM of objects which occur therein;
- constructing for each field F in FF, a set of types SF of objects stored therein;
- identifying one or more allocation sites inside the body B of each of method M;
- determining a set of methods M′ that are directly called within the body B of each method M and propagating types from the set of types SM′ to the set of types SM and from of the set of types SM to the set of types SM′;
- determining a set of methods M″ that are virtually called within the body B of each method M and propagating types from the set of types SM″ to the set of types SM and from the set of types SM to the set of types SM″;
- determining a set of fields F that are
- read in the body B of each method M, and propagating types from the set of types SF to the set of types SM;
- and
- written in the body B of each method M, and propagating types from the set of types SM to the set of types SF.
A computer program product for constructing a set of types occurring within a method, the computer program product comprising:
- a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
- selecting a program P for constructing a call graph representation thereof;
- wherein the program P contains zero or more fields FF and at least two methods MM;
- wherein each method M1 in MM has a single body B;
- wherein for each method M2 in MM, the call graph representation includes a corresponding node;
- wherein the call graph representation includes zero or more edges corresponding to connections between two or more of nodes;
- constructing for each method M in MM, a set of types SM of objects which occur therein;
- constructing for each field F in FF, a set of types SF of objects stored therein;
- identifying one or more allocation sites inside the body B of each of method M;
- determining a set of methods M′ that are directly called within the body B of each method M and propagating types from the set of types SM′ to the set of types SM and from of the set of types SM to the set of types SM′;
- determining a set of methods M″ that are virtually called within the body B of each method M and propagating types from the set of types SM″ to the set of types SM and from of the set of types SM to the set of types SM″;
- determining a set of fields F that are
- read in the body B of each method M, and propagating types from the set of types SF to the set of types SM;
- and
- written in the body B of each method M, and propagating types from the set of types SM to the set of types SF.
A method for constructing a set of types occurring within a method, the method comprising:
- selecting a program P for constructing a call graph representation thereof;
- wherein the program P contains zero or more fields FF and at least two methods MM;
- wherein each method M1 in MM has a single body B;
- constructing for each method M in MM, a set of types SM of objects which occur therein;
- constructing for each field F in FF, a set of types SF of objects stored therein;
- identifying one or more allocation sites inside the body B of each of method M;
- determining a set of methods M′ that are directly called within the body B of each method M and propagating types from a set of types SM′ to the set of types SM and from of the set of types SM to the set of types SM′;
- determining a set of methods M″ that are virtually called within the body B of each method M and propagating types from a set of types SM″ to the set of types SM and from of the set of types SM to the set of types SM″;
- determining a set of fields F that are
- read in the body B of each method M, and propagating types from the set of types SF to the set of types SM;
- and
- written in the body B of each method M, and propagating types from the set of types SM to the set of types SF.
Dependencies are inferred from the claim text.