Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-03-26
2001-09-04
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06286135
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to compiler optimization techniques, and more specifically to a compiler optimization algorithm that deals with aggressive strength reduction of integer machine instructions found in loops.
BACKGROUND OF THE INVENTION
Typically, compiler strength reduction algorithms focus on integer address computations within loops that can be expressed as a simple linear function of a loop induction variable.
Prior approaches to strength reduction have generally adopted one of the following techniques:
a. Simple bit-vector based data-flow analysis to identify induction variables and region constants within loops, followed by identification of simple inductive multiplications within loops and replacement of those multiplications with temporaries that are updated within loop bodies in parallel with updates to the induction variable. See, Aho, et al. “Induction Variables and Reduction in Strength”.
The drawbacks of this approach are that:
the bit-vector data-flow analysis precludes deep analysis of region constants used in strength reduction candidate expressions
profitability issues are not considered
reassociation opportunities are not exploited
machine-specific issues (specifically, predication and segmented address computations) are not considered.
b. Simple bit-vector based data-flow analysis to identify induction variables and region constants within loops, followed by symbolic analysis of strength reduction candidate address expressions within loops and replacement of those expressions with temporaries that are updated within loop bodies in parallel with updates to the induction variable. Vatsa Santhanam, HP Journal 1992, “Register Reassociation in PA-RISC Compilers”.
The drawbacks of this approach are that:
the bit-vector data-flow analysis precludes deep analysis of region constants used in strength reduction candidate expressions
profitability in terms of optimal placement of temporary updates is not considered
strength reduction and reassociation are not applied to expressions that do not compute an address value
machine-specific issues (specifically, predication and segmented address computations) are not considered.
c. SSA-based data-flow analysis to identify induction variables and region constants within loops, followed by symbolic analysis of strength reduction candidate address expressions within loops and replacement of those expressions with temporaries that are updated within loop bodies in parallel with updates to the induction variable. P. Markstein, et al., December 1992 “Strength Reduction chapter of an unpublished text book on program optimization”.
The drawbacks of this approach are that:
profitability in terms of optimal placement of temporary updates, net path-length reduction and register pressure are not considered
machine-specific issues (specifically, predication and segmented address computations) are not considered.
only computations that are involved in computing address values are strength reduced.
d. A PRE-based data-flow analysis of arbitrary control-flow structures to identify multiplications that can be reduced in strength by replacement with temporaries that are updated at optimal points in the flow-graph to preserve the multiplication result.
The drawbacks of this approach are that:
reassociation opportunities are not exploited
machine-specific issues (specifically, predication and segmented address computations) are not considered.
Often the strength reduction algorithm, and notably the reassociation transformation, is applied only to integer expressions that compute the address used by a memory access instruction. Moreover, strength reduction algorithms typically do not factor in the profitability of the code transformations in terms of register pressure impact and net path-length reduction within loop bodies.
An architecture that supports “Predication” is Ron Cytron, et al., entitled “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph”, poses some new challenges with regard to identifying and exploiting strength reduction opportunities within loop bodies. In particular, machine instructions that either update loop induction variables or are themselves candidates for strength reduction may be guarded by predicate registers. This poses a complication for strength reduction algorithms. In addition, on a 64-bit segmented architecture, the result of 32-bit address computations need to be converted into a 64-bit address value through an explicit conversion. Strength reduction of such address conversion operations can be quite important to achieve high performance within integer loops, but requires careful analysis to avoid compromising correctness—particularly in the presence of pointer values that may refer to different “segments”.
FIG. 1
illustrates at a very high level the strength reduction transformation. The strength reduction transformation is an algorithm that is typically implemented in an optimizing compiler that is focused on code that executes within loops. The basic idea behind the strength reduction algorithm is to look for expensive multiply operations within the loop involving a pair of terms, wherein one of which does not vary during the course of the loop's execution, and the other of which, happens to be a variable that progresses through a linear sequence of values as the loop iterates. The goal of strength reduction is to identify such multiplications and replace them by cheaper operations, namely additions. This will allow for the loop to execute faster on processors, because multiply operations are generally more expensive than addition operations.
FIG. 1A
depicts a code fragment of a high-level C source program
10
. There is a variable called g
11
of type “int”. It is an integer typed variable and is global in scope, in that it is declared outside the function main. Main
12
is a procedure function that is the routine where a program execution typically starts in a C program. Inside of this function main, there is a local variable i
13
declared to be an integer, and a loop
14
whose execution is controlled by the variable i, whereby i is assigned the value 0 by the for statement before entering the loop, and it is incremented by 1 each time through the loop, as indicated by the i++ expression at the end of that for statement. At the end of each iteration of the loop, i is checked to determine whether i is less than 10, as shown by the condition between the two semi-colons in the for statement. If that condition happens to be true, then execution of the loop is continued.
In other words, this for loop iterates ten times, where i assumes the value 0-9 in steps of 1, and when i reaches 10, then execution of the loop is terminated and the code that follows the for loop is executed. Now inside the for loop, there is an assignment to the global variable g of the expression 20*i+5
15
. Thus, on the first iteration when i is 0, g would get the value 5, and the next iteration
25
, and so forth. Therefore, there is an expensive multiply operation namely, 20*i; the 20 is a value that remains unchanged through the course of the loop's execution, and i is a variable that is incremented in steps of 1.
So there is strength reduction opportunity in this code fragment
10
, and
FIG. 1B
illustrates how the strength reduction transformation, that is the compiler algorithm that performs this transformation, would effectively optimize this program. Specifically, the for loop is strength reduced so that the multiply operation is transformed into a loop that involves only additions.
FIG. 1B
shows that the compiler effectively has created a new variable, a temporary variable called t
16
of type integer, and assigned it the value 5 outside of this loop. Thus, the temporary variable is initialized to 5, and the assignment to g that involved the multiplication of 20 with i and the addition of 5, has just been replaced with a simple assignment to g of t
17
. The compiler has also generated code to increment the tempora
Booker Kelvin
Hewlett--Packard Company
Powell Mark R.
LandOfFree
Cost-sensitive SSA-based strength reduction algorithm for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cost-sensitive SSA-based strength reduction algorithm for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cost-sensitive SSA-based strength reduction algorithm for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2466066