Program Optimization Technique
Original Publication Date: 1969-Nov-01
Included in the Prior Art Database: 2005-Mar-05
Carpenter, PF: AUTHOR [+1]
In unoptimized programs, certain expressions are evaluated repeatedly where there is no logical necessity to do so. For example: ... 104 1 = 2 = * N 105 A = A+1 106 IF A <20 GO TO 104.
Program Optimization Technique
In unoptimized programs, certain expressions are evaluated repeatedly where there is no logical necessity to do so. For example: ...
104 1 = 2 = * N
105 A = A+1
106 IF A <20 GO TO 104.
In this portion of the program, statement 104 becomes redundant after its first execution in the loop. This type of situation is normally handled by the programmer or language compiler by moving the statement outside of the loop. The general case of this form of optimization has to satisfy the logical constraints of prior definition and later use of variables across programs with a complex branching topology.
This technique has the effect of such optimization without requiring physical
rearrangement of the program. Each instruction in a program has an associated
flag. Before commencing program execution the flag on each instruction is set to
1. The first instruction in the program is selected for execution and then the following steps are taken repeatedly. For step 1, the instruction is executed and its flag is reset. If the operand whose value is changed by the instruction is also used as a source of data for the instruction, the flag is reset to 1. If the operand whose value is changed by the instruction is not otherwise referenced by the instruction, the flag is reset to 0. In step 2, the operand whose value is changed by the instruction is compared with all operands of all other instructions in the program. Any instructions found to refer to the changed operand have their flags reset to 1. For step 3, the next instruction in the program sequence whose flag is currently set to 1 is selected for execution.
As an example, the following program loop can be taken:
1 A = B x C
2 C = D x E
3 F = X x Y
4 G = M x N
5 E = R - C
6 IF E = 7 GO TO 8
7 GO TO 1.
Examination of these expressions shows that X, Y, and M and N, F and G, only occur once. Therefore, expressions 3 and 4 need be calculated only on the first pass.
Initially, all expressions are flagged with a 1. When step 1 is executed, its flag is changed to 0. Step 2 is then executed, and its flag is changed to 0, its operators are compared with those of the other expressions. Since C is changed and this operator also occurs in expressions 1 and 5, the flag for expression 1 is reset to 1 and the flag for expression 5 is set to 1. Steps 3 and 4 are then executed and their flags are set to 0. The comparing
operation is performed after each of these steps, but as the operators occurring in them do not appear elsewhere, no other flags are changed. After step 5 is executed, its flag is set to 0 and its corresponding comparing operation sets the flag of expression 2 to 1.
When, after steps 6 and 7, the program returns to step 1, this step is executed and its flag is changed to 0. After the execution of step 2, its flag is set to 0 and the flags of steps 1 and 5 are set to 1. Steps 3 and 4 have their flags set to 0. Consequently, these steps are not executed duri...