Patent ID: 6948161

Claim:
A computer implemented method of determining, in a computer environment, an equivalence, if any, of two blocks of assignment statements in a computer program for use in compiler optimization of source code, program verification, and like computing tasks, said method comprising the steps of: (a) forming, for each block of assignment statements, a corresponding array, each array comprising a plurality of elements corresponding to respective ones of the statements and populating the elements with attributes of the statements including an expression at right-hand side of the statement; (b) processing, in each array, each assignment statement in turn, in an order from a last statement to a first statement, the processing comprising an inspection of each unprocessed assignment statement in turn, in the order from a last unprocessed assignment statement to a first unprocessed assignment statement, to determine if a variable appearing on lefthand side of the unprocessed assignment statement appears on righthand side of the assignment statement being processed; (c) during step (b), in each array, if the variable appearing on the left-hand side of the unprocessed assignment statement also appears on the right-hand side of the assignment statement being processed, replacing all occurrences of such variable on the right-hand side of the assignment statement being processed, non-recursively, by the right-hand side of the said unprocessed assignment statement; (d) forming, from each array, a corresponding new block of assignment statements comprising the statements processed according to steps (b) and (c) and not comprising any statements which, after processing, is either an identity (the left and right sides of the statement are identical) or whose lefthand side variable is not an output variable; (e) creating, from each new block of assignment statements, a corresponding new array, each array comprising a plurality of elements corresponding to respective ones of the statements and populating the elements with attributes of the statements including the expression at the righthand side of the statement; (f) sorting, in each new array, the array elements in alphabetical order using the output variable name as a key; (g) comparing the arrays to detect the equivalence of two blocks of assignment statements.