Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-02-08
2003-05-27
Ingberg, Todd (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S151000
Reexamination Certificate
active
06571387
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer program (i.e., software) compilers and more particularly to optimizers in computer program compilers that perform sign-extension and zero-extension operation optimization.
2. Related Art
The Static Single Assignment Form (SSA) is a popular program representation in optimizing compilers, because it provides accurate use-definition (use-def) relationships among the program variables in a concise form. SSA is described in detail in R Cytron et al.,
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
, ACM Trans. on Programming Languages and Systems, 13(4):451-490, October 1991 (hereinafter “Cytron et al.”), which is incorporated herein by reference in its entirety.
The SSA form can be briefly described as a form where each definition of a variable is given a unique version, and different versions of the same variable can be regarded as different program variables. Each use of a variable version can only refer to a single reaching definition. When several definitions of a variable, a
1
, a
2
, . . . , a
m
, reach a common node (called a merging node) in the control flow graph of the program, a &phgr; function assignment statement, a
n
=&phgr;(a
1
, a
2
, . . . , a
m
), is inserted to merge the variables into the definition of a new variable version a
n
. Thus, the semantics of single reaching definitions are maintained.
Many efficient global optimization algorithms have been developed based on SSA. These optimizations, based on SSA, all share the common characteristic that they do not require traditional iterative data flow analysis in their solutions. They all take advantage of the sparse representation of SSA. In a sparse form, information associated with an object is represented only at places where it changes, or when the object actually occurs in the program. Because it does not replicate information over the entire program, a sparse representation conserves memory space. Thus, information can be propagated through the sparse representation in a smaller number of steps, speeding up most algorithms.
Among the optimizations based on SSA are dead code elimination, dead store elimination, constant propagation, value numbering, induction variable analysis, live range computation, and global code motion. Minimization of sign-extension and zero-extension operations, however, has not been addressed.
Modern programming languages like C and FORTRAN support integer data of various sizes and signage (i.e., either signed or unsigned). For example, using the C programming Language, one can declare an integer variable to be:
unsigned int i;
such that the variable i can hold values from 0 to 65,535 (assuming a machine where integers are 2 bytes (i.e., 16 bits)). One can also declare, however, an integer variable to be:
signed int i;
such that the variable i can hold values from −32,768 to 32,767 (also assuming a machine where integers are 2 bytes). Though the common sizes are 8 bits, 16 bits, 32 bits and 64 bits, any other size is possible. But the instruction architecture of a computer's central processor may not provide integer operations (e.g., +, −, *, /, and %) at each different bit size.
To represent negative numbers in binary within a computer, the “two's complement” representation is common to those skilled in the relevant art(s). In two's complement representation, each bit of the negative number being represented is first inverted (i.e., zeros are replaced with ones, and ones replaced with zeros). Then, a one (000 . . . 001 in binary) is added to avoid there being two representations for zero. For example, TABLE 1 shows the two's complement binary representation for the range of numbers from −3 to +3.
TABLE 1
Example of Two's Complement Representations
000 ... 00011 = +3
000 ... 00010 = +2
000 ... 00001 = +1
000 ... 00000 = 0
111 ... 11111 = −1
111 ... 11110 = −2
111 ... 11101 = −3
From TABLE 1 it can be seen that positive two's complement integers have the same binary representation as unsigned numbers.
Under the two's complement representation for integers, if integer operations are provided only for integer data of size n, it is possible to support signed integer types smaller than size n by providing the sign-extension operation, and to support unsigned integer types smaller than size n by providing the zero-extension operation. The sign-extension instruction specifies a bit position from which to sign-extend. For example, “SIGN_EXT
12
” specifies that the sign bit is at bit position eleven, and all bits at position twelve and higher are to be set to the value of bit eleven. The zero-extension instruction specifies a bit position from which to zero-extend. For example, “ZERO_EXT
8
” specifies that all bits at bit position eight and higher are to be set to zero.
As an example, suppose a program specifies a 12-bit addition operation on two signed integers that are each 12 bits in size. Further, suppose the underlying machine provides only registers that are 32 bits in size, and provides only the 32-bit addition operation. Before the 32-bit operation, the two 12-bit operands reside in two 32-bit registers, with their upper bits (i.e. those from bit 12 onwards) appropriately sign-extended. After the 32-bit addition, the result may be larger than what can be represented in 12 bits. Thus, it is necessary to execute a “SIGN_EXT
12
” operation so as to truncate the result back into a signed 12-bit integer, in order to preserve the semantics of 12-bit addition (as opposed to 32-bit addition).
The “ZERO_EXT n” command is the same as the “SIGN_EXT n”, but is more specific. It refers to extending with zeros only, which usually means a positive number. The 12 or 8 used in the examples above simply refers to the number of digits from right to left (least significant to most significant) that is counted before reaching the sign (positive or negative) bit. The least significant bit is referred to as bit zero.
The sign-extension and zero-extension operations provide the effect of truncation during arithmetic operations. This allows arithmetic operations to achieve correct results at smaller integer (i.e., bit) sizes despite the fact that these integer values reside in registers that are larger. Sign-extensions and zero-extensions also appear when user application programs contain type casts or truncation operations.
Typically, however, a processor may provide only 64-bit operations, although 32-bit is the most common integer size used. Thus, 32-bit integer code will perform sub-optimally. Therefore, what is needed is a method and computer program product, within an optimizing compiler, for the global minimization of sign-extension and zero-extension operations in generated code during compilation.
SUMMARY OF THE INVENTION
The present invention is directed to a method and computer program product for the global minimization of sign-extension and zero-extension operations in generated code during compilation.
The method and computer program of the present invention involve accessing a static single assignment (SSA) representation of a computer program and performing a bitwise liveness analysis of the SSA representation of the computer program in order to identify all sign-extension and zero-extension operations that affect only the dead bits. Then, a deletion of all sign-extension and zero-extension operations within the computer program which have been identified as useless is performed which allows an optimizing compiler to produce more efficient executable program code from the SSA representation.
An advantage of the present invention is that 64-bit compilers can improve the SPECint benchmarks compiled for the Intel IA64 architecture by reducing the number of sign-extension and zero-extension operations in the global and intra-procedural scope, thus, speeding up the execution of the compiled program.
Chow Frederick
Lo Raymond
Ingberg Todd
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
Wood William H.
LandOfFree
Method and computer program product for global minimization... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and computer program product for global minimization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for global minimization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3036070