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

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ng, John Shek-Luen
• Primary Examiner(s): Banankhah, Majid
• Assistant Examiner(s): LAO, SUE X
• Application Number:
  US08/568,075
• Time in Patent Office: 1,924 Days
• Field of Search: 395/709, 395/708, 717/9, 717/8
• US Class Current: 717/151
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A fast and efficient way of performing global value numbering beyond basic blocks and extended basic blocks on a complete topological ordering of basic blocks in a program. Global value numbering makes use of an unknown value number and iterative processing of a worklist containing expressions assigned an unknown value number. A hash table is used to reduce storage and processing time.

Claims

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.

2. The method of claim 1 wherein the processing step further comprises the steps of:

placing each of the second subset on a worklist;

removing from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

repeating the processing for the second subset until the worklist is empty.

3. The method of claim 2:

wherein the assigning for the second subset further comprises the step of;

assigning a value of unknown to a value number corresponding to a definition of an operand of an expression if a value number is not assigned to the definition, assigning a value of unknown to a value number corresponding to a result of the expression if the value number corresponding to any operand of the expression is assigned a value of unknown, and if any value number corresponding to any operand of a φ

-function is assigned a value of unknown, then assigning a value of unknown to the value number corresponding to the φ

-function.

4. The method of claim 3 further comprising the steps of:

for each operand of each expression;

if the operand does not have a definition, assigning the operand a new unique value number and propagating this new unique value number to other uses of this operand, and

if the operand has a definition, but a value number is not assigned to the definition, then assigning a value of unknown to a value number corresponding to the definition;

for each result of each expression;

if value numbers assigned to each operand of the expression are a same value number, then assigning the same value number to the result of the expression, else if the value number of any operand of the expression is assigned a value of unknown, then assigning a value of unknown to a value number corresponding to the result of the expression,

else assigning a new unique value number to the result of the expression; and

for each φ

-function;

if all value numbers of all operands of a φ

-function are equal, then assigning a value number of the φ

-function to the equal value numbers,

if all value numbers of all operands of a φ

-function are not equal, then assigning a new unique value number to the value number of the φ

-function, and

if any value number of any operand of a φ

-function is assigned a value of unknown, then assigning a value of unknown to a value number corresponding to the φ

-function.

5. A computer system for performing value numbering for optimization of a computer program, said value numbering being performed by a value number processing which assigns value numbers said computer system comprising:

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

means for 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;

means for assigning a value of a definite value number to each value number corresponding to each expression of a first subset of the expressions;

means for 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

means for 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.

6. The computer system of claim 5 wherein the processing means further comprises:

means for placing each of the second subset on a worklist;

means for removing from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

means for repeating the processing for the second subset until the worklist is empty.

7. The computer system of claim 6:

wherein the assigning means for the second subset further comprises;

means for assigning a value of unknown to a value number corresponding to a definition of an operand of an expression if a value number is not assigned to the definition, means for assigning a value of unknown to a value number corresponding to a result of the expression if the value number corresponding to any operand of the expression is assigned a value of unknown, and means for assigning a value of unknown to the value number corresponding to the φ

-function if any value number corresponding to any operand of a φ

-function is assigned a value of unknown.

8. The computer system of claim 7 further comprising:

for each operand of each expression;

means for assigning the operand a new unique value number if the operand does not have a definition, and for propagating this new unique value number to other uses of this operand, and means for assigning a value of unknown to a value number corresponding to the definition if the operand has a definition, but a value number is not assigned to the definition;

for each result of each expression;

means for assigning the same value number to the result of the expression if value numbers assigned to each operand of the expression are a same value number, else assigning a value of unknown to a value number corresponding to the result of the expression if a value number of any operand of the expression is assigned a value of unknown,

else assigning a new unique value number to the result of the expression; and

for each φ

-function;

means for assigning a value number of the φ

-function to an equal value number if all value numbers of all operands of a φ

-function are equal,

means for assigning a new unique value number to the value number of the φ

-function if all value numbers of all operands of the φ

-function are not equal, and

means for assigning a value of unknown to a value number corresponding to the value number of the φ

-function if any value number of any operand of the φ

-function is assigned a value of unknown.

9. An article of manufacture for use in a computer system performing value numbering for optimization of a computer program, said value numbering being performed by a value number processing which assigns value numbers, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to:

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

process 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;

assign a value of a definite value number to each value number corresponding to each expression of a first subset of the expressions;

assign 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

assign 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.

10. The article of manufacture of claim 9 wherein the processing may further cause the computer system to:

place each of the second subset on a worklist;

remove from the worklist an expression of the second subset if the expression does not have at least one corresponding value number assigned a value of unknown after assigning a value number to the expression of the second subset; and

repeat the processing for the second subset until the worklist is empty.

11. The article of manufacture of claim 10:

wherein the assigning for the second subset may further cause the computer system to;

assigning a value of unknown to a value number corresponding to a definition of an operand of an expression if a value number is not assigned to the definition, assigning a value of unknown to a value number corresponding to a result of the expression if the value number corresponding to any operand of the expression is assigned a value of unknown, and if any value number corresponding to any operand of a φ

-function is assigned a value of unknown, then assigning a value of unknown to the value number corresponding to the φ

-function.

12. The article of manufacture of claim 11 wherein the processing may further cause the computer system to:

for each operand of each expression;

if the operand does not have a definition, assign the operand a new unique value number and propagate this new unique value number to other uses of this operand, and

if the operand has a definition, but a value number is not assigned to the definition, then assign a value of unknown to a value number corresponding to the definition;

for each result of each expression;

if value numbers assigned to each operand of the expression are a same value number, then assign the same value number to the result of the expression,

else if the value number of any operand of the expression is assigned a value of unknown, then assign a value of unknown to a value number corresponding to the result of the expression,

else assign a new unique value number to the result of the expression; and

for each φ

-function;

if all value numbers of all operands of a φ

-function are equal, then assign a value number of the φ

-function to the equal value numbers,

if all value numbers of all operands of a φ

-function are not equal, then assign a new unique value number to the value number of the φ

-function, and

if any value number of any operand of a φ

-function is assigned a value of unknown, then assign a value of unknown to a value number corresponding to the φ

-function.