Optimization of alternate loop exits

Claim 2

A digital computer for eliminating, under programmed control, alternate exit tests from a loop body, the programmed computer comprising: (a) transformation means for transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=, ≠, >, ≧, <, ≦); (b) comparison means for comparing the transformed alternate exit test to a list of elimination conditions; and (c) elimination means for eliminating the alternate exit test from the loop body if it matches one of the elimination conditions; whereby an optimized loop body is produced.

Claim 3

The programmed computer of claim 1 wherein the list of elimination conditions comprises: (a) where the operator is "=", α=0, and β-φ≠0; (b) where the operator is "=", α>0, and β-φ>0; (c) where the operator is "=", α<0, and β-φ<0; (d) where the operator is "=", |α|>1, and (φ-β) modα≠0; (e) where the operator is "≠", α=0, and β-φ=0; (f) where the operator is "<", α≧0, and β-φ≧0; (g) where the operator is "≦", α≧0, and β-φ>0; (h) where the operator is ">", α≦0, and β-φ≦0; and (i) where the operator is "≧", α≦0, and β-φ<0.

Claim 4

The programmed computer of claim 1 further comprising insertion means for inserting program code before the loop body for calculating the value of each loop invariant expression α, β or φ that is a variable expression.

Claim 5

A digital computer for removing, under programmed control, alternate exit tests from a loop body, the programmed computer comprising: (a) transformation means for transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparison means for comparing the transformed alternate exit test to a list of restriction conditions; and (c) calculation means for calculating a new loop exit iteration value i exit according to a list of exit expression rules if the transformed alternate exit test matches one of the restriction conditions; (d) removal means for removing the alternate exit test from the loop body if the transformed alternate exit test matches one of the restriction conditions; (e) comparison means for comparing the value of an existing loop exit upper bounds expression N to i exit if N is a constant expression; (f) modification means for modifying the value of N to be substantially equal to i exit minus two if N is a constant expression and the value of N is greater than i exit ; and (g) trailing segment insertion means for inserting a first trailing segment of program code after the loop body if N is a constant expression and the value of N is greater than i exit , whereby an optimized loop body is produced.

Claim 6

A digital computer for removing, under programmed control, alternate exit tests from a loop body, the programmed computer comprising: (a) transformation means for transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparison means for comparing the transformed alternate exit test to a list of restriction conditions; and (c) calculation means for calculating a new loop exit iteration value i exit according to a list of exit expression rules if the transformed alternate exit test matches one of the restriction conditions; (d) removal means for removing the alternate exit test from the loop body if the transformed alternate exit test matches one of the restriction conditions; (e) comparison means for comparing the value of an existing loop exit upper bounds expression N to i exit if N is a constant expression; (f) modification means for modifying the value of N to be substantially equal to i exit minus two if N is a constant expression and the value of N is greater than i exit ; and (g) trailing segment insertion means for inserting a first trailing segment of program code after the loop body if N is a constant expression and the value of N is greater than i exit , whereby an optimized loop body is produced.

Claim 7

The programmed computer of claim 4 wherein the list of restriction conditions comprises: (a) if operator is "=", α=0, and β-φ=0; (b) if operator is "=", α≠0, and (φ-β)modα=0; (c) if operator is "=", α=0, and β-φ≠0; (d) if operator is "=", α≠0, and (φ-β) modα≠0; (e) if operator is "≠" and β-φ≠0; (f) if operator is "≠", α≠0, and β-φ=0; (g) if operator is "≠", α=0, and β-φ=0; (h) if operator is "<" and β-φ<0; (i) if operator is "<" and α<0; (j) if operator is "<" and α≧0; (k) if operator is "≦" and β-φ≦0; (l) if operator is "≦" and α<0; (m) if operator is "≦" and α≧0; (n) if operator is ">" and β-φ>0; (o) if operator is ">" and α>0; (p) if operator is ">" and α≦0; (q) if operator is "≧" and β-φ≧0; (r) if operator is "≧" and α>0; and (s) if operator is "≧" and α≦0.

Claim 8

The programmed computer of claim 4 wherein the list of exit expression rules comprises: (a) if operator is "=", α=0, and β-φ=0, then i exit =1; (b) if operator is "=", α≠0, and (φ-β)modα=0, then i exit =(φ-β)/α+1; (c) if operator is "=", α=0, and β-φ≠0, them i exit =∞; (d) if operator is "=", α≠0, and (φ-β) modα≠0, then i exit =∞; (e) if operator is "≠" and β-φ≠0, then i exit =1; (f) if operator is "≠", α≠0, and β-φ=0, then i exit =2; (g) if operator is "≠", α=0, and β-φ=0, then i exit =∞; (h) if operator is "<" and β-φ<0, then i exit =1; (i) if operator is "<" and α<0, then i exit =(φ-β)/α+2; (j) if operator is "<" and α≧0, then i exit =∞; (k) if operator is "≦" and β-φ≦0, then i exit =1; (l) if operator is "≦" and α<0, then i exit =(φ-β-1)/α+2; (m) if operator is "≦" and α≧0, then i exit =∞; (n) if operator is ">" and β-φ>0, then i exit =1; (o) if operator is ">" and α>0, then i exit =(φ-β)/α+2; (p) if operator is ">" and α≦0, then i exit =∞; (q) if operator is "≧" and β-φ≧0, then i exit =1; (r) if operator is "≧" and α>0, then i exit =(φ-β+1)/α+2; and (s) if operator is "≧" and α≦0, then i exit =∞.

Claim 9

The programmed computer of claim 4 further comprising invariant expression evaluation insertion means for inserting before the loop body program code for calculating the value of each loop invariant expression α, β or φ that is a variable expression.

Claim 10

The programmed computer of claim 4 further comprising modification means for modifying the value the existing loop exit upper bounds expression N to be equal to the minimum value of either i exit minus two or the value of N if N is a variable expression.

Claim 11

The programmed computer of claim 4 wherein the trailing segment of program code comprises a final partial loop iteration calculation and error handling program code.

Claim 12

The programmed computer of claim 4 wherein the trailing segment insertion means comprises means for inserting a second trailing segment of program code after the loop body if N is a variable expression.

Claim 13

The programmed computer of claim 10 wherein the second trailing segment of program code comprises a test, a final partial loop iteration calculation, and error handling program code.

Claim 14

An optimization method to be carried out within a digital computer under programmed control for eliminating alternate exit tests from a loop body, the method comprising the steps of: (a) transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparing the transformed alternate exit test to a list of elimination conditions; and (c) eliminating the alternate exit test from the loop body if the transformed alternate exit test matches one of the elimination conditions, whereby an optimized loop body is produced.

Claim 15

An optimization method to be carried out within a digital computer under programmed control for eliminating alternate exit tests from a loop body, the method comprising the steps of: (a) transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparing the transformed alternate exit test to a list of elimination conditions; and (c) eliminating the alternate exit test from the loop body if the transformed alternate exit test matches one of the elimination conditions, whereby an optimized loop body is produced.

Claim 16

The optimization method of claim 12 wherein the list of elimination conditions comprises: (a) where the operator is "=", α=0, and β-φ≠0; (b) where the operator is "=", α>0, and β-φ>0; (c) where the operator is "=", α<0, and β-φ<0; (d) where the operator is "=", |α|>1, and (φ-β)modα≠0; (e) where the operator is "≠", α=0, and β-φ=0; (f) where the operator is "<", α≧0, and β=φ≧0; (g) where the operator is "≦", α≧0, and β-φ≧0; (h) where the operator is ">", α≦0, and β-φ≦0; and (i) where the operator is "≧", α≦0, and β-φ<0.

Claim 17

The optimization method of claim 12 wherein the method further comprises inserting before the loop body program code for calculating the value of each loop invariant expression α, β or φ that is a variable expression.

Claim 18

An optimization method to be carried out within a digital computer under programmed control for removing alternate exit tests from a loop body, the method comprising the steps of: (a) transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparing the transformed alternate exit test to a list of restriction conditions; (c) calculating a new loop exit iteration value i exit according to a list of exit expression rules if the transformed alternate exit test matches one of the restriction conditions; (d) removing the alternate exit test from the loop body if the transformed alternate exit test matches one of the restriction conditions; (e) comparing the value of an existing loop exit upper bounds expression N to the new loop exit iteration value i exit ; (f) modifying the value of N to be substantially equal to i exit minus two if N is a constant expression and the value of N is greater than i exit ; and (g) inserting a trailing segment of program code after the loop body if N is a constant expression and the value of N is greater than i exit , whereby an optimized loop body is produced.

Claim 19

An optimization method to be carried out within a digital computer under programmed control for removing alternate exit tests from a loop body, the method comprising the steps of: (a) transforming an alternate exit test into a transformed alternate exit test of the form αi+βcondφ, where α, β and φ are loop invariant expressions, i is the innermost loop index variable, and cond is one of the relational operators (=,≠,>,≧,<,≦); (b) comparing the transformed alternate exit test to a list of restriction conditions; (c) calculating a new loop exit iteration value i exit according to a list of exit expression rules if the transformed alternate exit test matches one of the restriction conditions; (d) removing the alternate exit test from the loop body if the transformed alternate exit test matches one of the restriction conditions; (e) comparing the value of an existing loop exit upper bounds expression N to the new loop exit iteration value i exit ; (f) modifying the value of N to be substantially equal to i exit minus two if N is a constant expression and the value of N is greater than i exit ; and (g) inserting a trailing segment of program code after the loop body if N is a constant expression and the value of N is greater than i exit , whereby an optimized loop body is produced.

Claim 20

The optimization method of claim 15 wherein the list of restriction conditions comprises: (a) if operator is "=", α=0, and β-φ=0; (b) if operator is "=", α≠0, and (φ-β)modα=0; (c) if operator is "=", α=0, and β-φ≠0; (d) if operator is "=", α≠0, and (φ-β) modα≠0; (e) if operator is "≠" and β=φ≠0; (f) if operator is "≠", α≠0, and β-φ=0; (g) if operator is "≠", α=0, and β-φ=0; (h) if operator is "<" and β-φ<0; (i) if operator is "<" and α<0; (j) if operator is "<" and α≧0; (k) if operator is "≦" and β-φ≦0; (l) if operator is "≦" and α<0; (m) if operator is "≦" and α≧0; (n) if operator is ">" and β-φ>0; (o) if operator is ">" and α>0; (p) if operator is ">" and α≦0; (q) if operator is "≧" and β-φ≧0; (r) if operator is "≧" and α>0; and (s) if operator is "≧" and α≦0.

Claim 21

The optimization method of claim 15 wherein the list of exit expression rules comprises: (a) if operator is "=", α=0, and β-φ=0, then i exit =1; (b) if operator is "=", α≠0, and (φ-β)modα=0, then i exit =(φ-β)/α+1; (c) if operator is "=", α=0, and β-φ≠0, them i exit =∞; (d) if operator is "=", α≠0, and (φ-β) modα≠0, then i exit =∞; (e) if operator is "≠" and β-φ≠0, then i exit =1; (f) if operator is "≠", α≠0, and β-φ=0, then i exit =2; (g) if operator is "≠", α=0, and β-φ=0, then i exit =∞; (h) if operator is "<" and β-φ<0, then i exit =1; (i) if operator is "<" and α<0, then i exit =(φ-β)/α+2; (j) if operator is "<" and α≧0, then i exit =∞; (k) if operator is "≦" and β-φ≦0, then i exit =1; (l) if operator is "≦" and α<0, then i exit =(φ-β-1)/α+2; (m) if operator is "≦" and α≧0, then i exit =∞; (n) if operator is ">" and β-φ>0, then i exit =1; (o) if operator is ">" and α>0, then i exit =(φ-β)/α+2; (p) if operator is ">" and α≦0, then i exit =∞; (q) if operator is "≧" and β-φ≧0, then i exit =1; (r) if operator is "≧" and α>0, then i exit =(φ-β+1)/α+2; and (s) if operator is "≧" and α≦0, then i exit =∞.

Claim 22

The optimization method of claim 15 wherein the method further comprises inserting before the loop body program code for calculating the value of each loop invariant expression α, β or φ that is a variable expression.

Claim 23

The optimization method of claim 18 wherein, if N is a variable expression, the method further comprises the step of modifying the value of the existing loop exit upper bounds expression N to be equal to the minimum value of either i exit minus two or the value of N.

Claim 24

The optimization method of claim 19 wherein the step of modifying comprises inserting a trailing segment of program code after the loop body.

Claim 25

The optimization method of claim 20 wherein the trailing segment of program code comprises a test, a final partial loop iteration calculation, and error handling program code.