# US 8,543,974 B2 · Plan-based program slicing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,974 B2 - Document ID: US8543974B2 - Status: Granted - Kind: B2 - Application number: 12/550,406 - Filed: 2009-08-31 - Published: 2011-03-03 - Granted: 2013-09-24 - Earliest claimed: 2009-08-31 - Assignees: International Business Machines Corporation - Applicants: Aharon Abadi; Jonathan Bnayahu; Ran Ettinger; Yishai Feldman - Inventors: Aharon Abadi; Jonathan Bnayahu; Ran Ettinger; Yishai Feldman - Web page: https://patentgrep.com/patent/US8543974B2 ## CPC - G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)} - G06F 8/75: Structural analysis for program understanding - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for generating a slice from a plan-based representation of a program is provided. The method comprises constructing a plan representation of a program, wherein the plan representation comprises a plurality of nodes, edges, and ports; and receiving one or more slicing criteria from a user. The slicing criteria comprise one or more variable occurrences or statements from the program, according to which a slice is generated from the plan representation. ## Claims ### Claim 1 A method of generating a slice from a plan-based representation of a program, the method comprising: constructing, using one or more processors, a first plan representation of a program, wherein the first plan representation comprises a plurality of nodes, edges, and ports, wherein a node represents at least one of an operation associated with data input/output (I/O) in the program, a test specification associated with a branch in control flow of the program, or a join specification associated with a point in the program where control and data flow are joined, wherein a port represents at least one of a data port or a control port, wherein a data edge connects a data port on a first node to a data port on a second node, and wherein a control edge connects a control port on a third node to a control port on a fourth node, such that an edge defines control or data flow among the nodes; receiving one or more slicing criteria from a user, wherein the slicing criteria comprise one or more variable occurrences or statements from the program; associating each variable occurrence in the set of slicing criteria to a corresponding data edge in the first plan representation; associating each statement in the set of slicing criteria to a corresponding node or edge in the first plan representation; adding input or source ports associated with the set of slicing criteria to a second plan representation; iteratively adding input control or data ports to the second plan representation according to control or data dependence, respectively, of ports in the second plan representation; adding one or more ports, nodes, or edges to the second plan representation to complete control or data flows in the second plan representation; adding a minimal set of join specifications to the second plan representation to prevent fan-in of control; adding a minimal set of test specifications to the second plan representation to prevent fan-in of control; and coverting the second plan representation to source code of the program; and generating a slice from the plan representation according to the slicing criteria. ### Claim 2 (depends on 1) The method of claim 1, wherein the plan representation is constructed from a CFG (control flow graph). ### Claim 3 (depends on 1) The method of claim 1, wherein the slice is generated by traversing the plan representation backward or forward from the slicing criteria. ### Claim 4 (depends on 1) The method of claim 1, wherein the program is a structured program. ### Claim 5 (depends on 1) The method of claim 1, wherein the program is an unstructured program ### Claim 6 (depends on 1) The method of claim 1, wherein a statement in the program is mapped to one or more components of the plan representation of the program, such that one or more components are mapped to the statement, in order to translate a generated slice back to source code for the program. ### Claim 7 A system of generating a slice from a plan-based representation of a program, the system comprising: one or more processors coupled to one or more memory units; a logic unit for constructing, using one or more processors, a plan representation of a program, wherein the plan representation comprisesa plurality of nodes, edges, and ports, wherein a node represents at least one of an operation associated with data input/output (I/O) in the program, a test specification associated with a branch in control flow of the program, or a join specification associated with a point in the program where control and data flow are joined, wherein a port represents at least one of a data port or a control port, wherein a data edge connects a data port on a first node to a data port on a second node, and wherein a control edge connects a control port on a third node to a control port on a fourth node, such that an edge defines control; or data flow among the nodes; a logic unit for receiving one or more slicing criteria from a user, wherein the slicing criteria comprise one or more variable occurrences or statements from the program; a logic unit for associating each variable occurrence in the set of slicing criteria to a corresponding data edge in the first plan representation; a logic for associating each statement in the set of slicing criteria to a corresponding node or edge in the first plan representation; a logic unit for adding input or source ports associated with the set of slicing criteria to a second plan representation; a logic unit for iteratively adding input control or data ports to the second plan representation according to control or data dependence, respectively, of ports in the second plan representation; a logic unit for adding one or more ports, nodes, or edges to the second plan representation to complete control or data flows in the second plan representation; a logic unit for adding a minimal set of join specifications to the second plan representation to prevent fan-in control; a logic unit for adding a minimal set of test specifications to the second plan representation to prevent fan-in of control; and a logic unit for converting the second plan representation to source code of the program; and a logic unit for generating a slice from the plan representation according to the slicing criteria. ### Claim 8 (depends on 7) The system of claim 7, further comprising associating each variable occurrence in the slicing criteria to a corresponding data edge in the first plan representation. ### Claim 9 (depends on 7) The system of claim 7, further comprising associating each statement in the slicing criteria to a corresponding node or edge in the first plan representation. ### Claim 10 (depends on 7) The system of claim 7, wherein the adding is performed by traversing the first plan representation backward or forward from the slicing criteria. ### Claim 11 (depends on 7) The system of claim 7, wherein the adding comprises including input or source ports associated with the slicing criteria to the second plan representation. ### Claim 12 (depends on 7) The system of claim 7, wherein the adding comprises iteratively including input control or data ports in the second plan representation according to control or data dependence, respectively, of ports in the second plan representation. ### Claim 13 (depends on 7) The claim 7, wherein the adding comprises including ports, nodes, or edges in the second plan representation to complete control or data flows in the second plan representation. ### Claim 14 (depends on 7) The system of claim 7, wherein the adding comprises including a minimal set of join specifications in the second plan representation to prevent fan-in of control. ### Claim 15 (depends on 7) The system of claim 7, wherein the adding comprises including a minimal set of test specifications in the second plan representation to prevent fan-out of control. ### Claim 16 (depends on 7) The system of claim 7, wherein the program is structured. ### Claim 17 (depends on 7) The system of claim 7, wherein the program is unstructured. ### Claim 18 (depends on 17) The system of claim 17, wherein a join specification associated with a test specification is included in the second plan representation, and wherein the test specification is included in the second plan representation, in response to determining: there is a control path from a first output control port of the test specification to a maximal join block of the join specification that carries a data value; and there is a control path from a second output control port of the test specification that carries a different data value or no data value. ### Claim 19 (depends on 7) The system of claim 7, wherein a statement in the program is mapped to one or more components of the plan representation of the program, such that one or more components are mapped to the statement, in order to translate a generated slice back to the source code for the program. ### Claim 20 A computer program product comprising logic code stored in a non-transitory storage medium, wherein execution of the logic code on a computer causes the computer to: construct a first plan representation of a program, wherein the first plan representation comprises a plurality of nodes, edges, and ports, wherein a node represents at least one of an operation associated with data input/output (I/O) in the program, a test specification associated with a branch in control flow of the program, or a join specification associated with a point in the program where control and data flow are joined, wherein a port represents at least one of a data port or a control port, wherein a data edge connects a data port on a first node to a data port on a second node, and wherein a control edge connects a control port on a third node to a control port on a fourth node, such that an edge defines control or data flow among the nodes; associate each variable occurrence in a set of slicing criteria to a corresponding data edge in the first plan representation; associate each statement in the set of slicing criteria to a corresponding node or edge in the first plan representation; add input or source ports associated with the set of slicing criteria to a second plan representation; iteratively add input control or data ports to the second plan according to control or data dependence, respectively, of ports in the second plan representation; add one or more ports, nodes, or edges to the second plan representation to complete control or data flows in the second plan representation; add a minimal set of join specifications to the second plan to prevent fan-in of control; add a minimal set of test specifications to the second plan to prevent fan-in of control; convert the second plan representation to source code of the program; generate a slice from the plan representation according to the slicing criteria.