×

Method of, system for, and computer program product for providing global value numbering

  • US 6,202,203 B1
  • Filed: 12/06/1995
  • Issued: 03/13/2001
  • Est. Priority Date: 12/06/1995
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of performing value numbering for optimization of a computer program, said value numbering being performed by a value number processing which assigns value numbers, said method comprising the steps of:

  • determining a complete topological order of a plurality of basic blocks from a flow graph of the computer program;

    processing the plurality of basic blocks in the complete topological order, wherein the processing comprises assigning a value number to each expression in each of the plurality of basic blocks, 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 a definite value number to each value number corresponding to each expression of a first subset of the expressions;

    assigning a value of unknown to at least one value number corresponding to each expression of a second subset of the expressions, the assignment of the value of unknown indicating that although the at least one value number has been processed by the value number processing, the assignment of a definite known value number is to be postponed until later in the value number processing, 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 and assigning a value representing unassigned to each value number corresponding to each expression of a third subset of the expressions, said unassigned value indicating that the corresponding expression has not yet been processed by the value number processing and that neither a definite value nor an unknown value is yet assigned to the value number of the third subset by the value number processing.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×