System and method for control logic code reordering based on stochastic execution time information
View Patent ↗A method, computer program product, and data processing system for performing automated optimization of a control processing flow containing Boolean conditional expressions is disclosed. Each conditional expression is profiled using a representative set of test vectors to determine the probabilities of individual conditions and combinations of conditions in the expression. Next, the expression is restructured or reordered, including selective computation of subexpressions, based on the probability information, so as to maximize the probability of a short-circuit termination of evaluation of the expression and/or to minimize the statistical execution time of the expression. This process is performed for all Boolean conditional expressions related to the control processing flow.
1. A computer-executed method comprising:
profiling execution of a control processing flow to obtain empirical information regarding a plurality of Boolean conditions associated with execution of the control processing flow; and
transforming Boolean condition evaluation code within the control processing flow to obtain improved code, the transforming comprising rearranging an order in which the plurality of Boolean conditions are tested, wherein the improved code is improved with respect to a performance heuristic that is estimated using the empirical information.
2. The method of claim 1 , wherein the empirical information comprises probabilities of the Boolean conditions being true or false during execution of the control processing flow.
3. The method of claim 1 , wherein the heuristic estimates statistical execution time, wherein the statistical execution time is derived from average execution time or from variance of execution time.
4. The method of claim 1 , wherein the Boolean condition evaluation code evaluates a conjunctive Boolean expression.
5. The method of claim 1 , wherein the Boolean condition evaluation code evaluates a disjunctive Boolean expression.
6. The method of claim 1 , wherein the Boolean condition evaluation code is transformed such that an estimated likelihood of short circuit Boolean evaluation in the improved code is greater than an estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code, and wherein the estimated likelihood of short circuit Boolean evaluation in the improved code that the estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code are estimated from the empirical information.
7. A computer program product stored in a tangible computer-readable medium, comprising functional descriptive material that, when executed by a computer, directs the computer to perform actions that include:
obtaining empirical information regarding a plurality of Boolean conditions associated with execution of a control processing flow; and
transforming Boolean condition evaluation code within the control processing flow to obtain improved code, the transforming comprising rearranging an order in which the plurality of Boolean conditions are tested, wherein the improved code is improved with respect to a performance heuristic that is estimated using the empirical information.
8. The computer program product of claim 7 , wherein the empirical information comprises probabilities of the Boolean conditions being true or false during execution of the control processing flow.
9. The computer program product of claim 7 , wherein the empirical information is obtained by profiling execution of the control processing flow.
10. The computer program product of claim 7 , wherein the empirical information is obtained from storage.
11. The computer program product of claim 7 , wherein the heuristic estimates statistical execution time, wherein the statistical execution time is derived from average execution time or from variance of execution time.
12. The computer program product of claim 7 , wherein the Boolean condition evaluation code evaluates a conjunctive Boolean expression.
13. The computer program product of claim 7 , wherein the Boolean condition evaluation code evaluates a disjunctive Boolean expression.
14. The computer program product of claim 7 , wherein the Boolean condition evaluation code is transformed such that an estimated likelihood of short circuit Boolean evaluation in the improved code is greater than an estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code, and wherein the estimated likelihood of short circuit Boolean evaluation in the improved code that the estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code are estimated from the empirical information.
15. A data processing system comprising:
at least one processor;
at least one storage system associated with the at least one processor;
a set of instructions in the at least one storage system, wherein the set of instructions is executed by the at least one processor to perform actions that include:
obtaining empirical information regarding a plurality of Boolean conditions associated with execution of a control processing flow; and
transforming Boolean condition evaluation code within the control processing flow to obtain improved code, the transforming comprising rearranging an order in which the plurality of Boolean conditions are tested, wherein the improved code is improved with respect to a performance heuristic that is estimated using the empirical information.
16. The data processing system of claim 15 , wherein the heuristic estimates statistical execution time, wherein the statistical execution time is derived from average execution time or from variance of execution time.
17. The data processing system of claim 15 , wherein the Boolean condition evaluation code is transformed such that an estimated likelihood of short circuit Boolean evaluation in the improved code is greater than an estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code, and wherein the estimated likelihood of short circuit Boolean evaluation in the improved code that the estimated likelihood of short circuit Boolean evaluation in the Boolean condition evaluation code are estimated from the empirical information.