Patent ID: 6035124
Filing Date: 2000-03-07
Classification: G06F

Abstract:
A method of performing redundancy optimization of a computer program, said method comprising the steps of:determining a complete topological order of a plurality of basic blocks comprising expressions from a flow graph of the computer program; andprocessing the plurality of basic blocks in the topological order, wherein the processing comprises:assigning a value number to each expression of a first subset of the expressions, wherein the value number is a symbolic execution of a basic block of the computer program, in which each variable entering the basic block is given a distinct symbolic value comprising the value number;assigning a value of unknown to at least one value number corresponding to each expression of a second subset of the expressions, the second subset comprising .phi.-functions having an operand whose value number is assigned a value of unknown, and op-codes having an operand whose value number is assigned a value of unknown; andassigning a value number list to each expression of a third subset of the expressions, wherein the value number list comprises an ordered list of value numbers assigned to the expression, and wherein the value number list does not contain a value number assigned a value of unknown.