Computer implemented program specialization
AssigneeWisconsin Alumni Research Foundation
InventorsMohannad Alhanahnah, Vaibhav Rastogi, Somesh Jha, Thomas Reps
Life of this patent
Estimating the term…
Abstract
A computerized technique for program simplification and specialization combines a partial interpretation of the program based on a subset of program functions to obtain variable states with concrete values at a program “neck.” These concrete values are then propagated as part of an optimization transformation that simplifies the program based on these constant values, for example, by eliminating branches that are never taken based on the constant values.
Claims18
An apparatus for producing compact program versions comprising:
- at least one computer processor;
- and
- a memory coupled to the at least one processor holding a stored program executable by the at least one computer processor to:
- (a) receive a program implementing multiple functions and a separate pre-determined identification of a desired subset of functions less than the set of the multiple functions;
- (b) identify a neck of the program dividing configuration instructions from main logic instructions;
- (c) partially interpret the program to the neck to establish concrete values of selected variables at the neck, the selected variables selected according to the pre-determined identification of a desired subset of functions;
- (d) propagate the established concrete values through the main logic instructions;
- and
- (e) simplify the program by removing instructions of the main logic instructions that will never execute to implement the desired subset of functions based on the propagated concrete values.
An apparatus for producing compact program versions comprising:
- at least one computer processor;
- and
- a memory coupled to the at least one processor holding a stored program executable by the at least one computer processor to:
- (a) receive a program implementing multiple functions and a description of a desired subset of functions less than the set of the multiple functions;
- (b) identify a neck of the program dividing configuration instructions from main logic instructions;
- (c) partially interpret the program to the neck to establish concrete values of variables at the neck;
- (d) propagate the concrete values through the main logic instructions;
- and
- (e) simplify the program by removing instructions of the main logic instructions that will never execute based on the propagated concrete values,
- wherein the neck is identified as a portion of the received program:
- (i) that will execute once and only once for any combination of functions of the subset;
- and
- (ii) is an articulation point in a control flow graph of the program that dominates all subsequent instructions;
- and
- wherein the neck further is identified as a portion of the program:
- (iii) that is a closest instruction to a beginning of the program for instructions that satisfy (i) and (ii) and minimizes a number of instructions in the simplified program.
A method for producing compact program versions using an electronic computer comprising using the electronic computer to:
- (a) receive a program implementing multiple functions and a description of a desired subset of functions less than the set of the multiple functions;
- (b) identify a neck of the program dividing configuration instructions from main logic instructions;
- (c) partially interpret the program to the neck to establish concrete values of variables at the neck;
- (d) propagate the concrete values through the main logic instructions;
- and
- (e) simplify the program by removing instructions of the main logic instructions that will never execute based on the propagated concrete values;
- wherein the neck is identified as a portion of the program:
- (i) that will execute once and only once for any combination of functions of the subset;
- and (ii) is an articulation point in a control flow graph of the program that dominates all subsequent instructions;
- and
- wherein the neck further is identified as a portion of the program that:
- (iii) is a closest instruction to the beginning of the program for instructions that satisfy (i) and (ii) and minimizes a number of instructions in the simplified program.
Dependencies are inferred from the claim text.