Partial redundancy elimination - AbsoluteAstronomy.com

In compiler theory, partial redundancy elimination (PRE) is a compiler optimization

Compiler optimization

Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...

that eliminates expressions

Expression (programming)

An expression in a programming language is a combination of explicit values, constants, variables, operators, and functions that are interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then produces another value...

that are redundant on some but not necessarily all paths through a program. PRE is a form of common subexpression elimination

Common subexpression elimination

In computer science, common subexpression elimination is a compiler optimization that searches for instances of identical expressions , and analyses whether it is worthwhile replacing them with a single variable holding the computed value.- Example :In the following code: a = b * c + g; d = b * c...

.

An expression is called partially redundant if the value

Value (computer science)

In computer science, a value is an expression which cannot be evaluated any further . The members of a type are the values of that type. For example, the expression "1 + 2" is not a value as it can be reduced to the expression "3"...

computed by the expression is already available on some but not all paths through a program to that expression. An expression is fully redundant if the value computed by the expression is available on all paths through the program to that expression. PRE can eliminate partially redundant expressions by inserting the partially redundant expression on the paths that do not already compute it, thereby making the partially redundant expression fully redundant.

For instance, in the following code:

if (some_condition) {
// some code
y = x + 4;
}
else {
// other code
}
z = x + 4;

the expression x+4 assigned to z is partially redundant because it is computed twice if some_condition is true. PRE would perform code motion on the expression to yield the following optimized code:

if (some_condition) {
// some code
t = x + 4;
y = t;
}
else {
// other code
t = x + 4;
}
z = t;

An interesting property of PRE is that it performs (a form of) common subexpression elimination

Common subexpression elimination

and loop-invariant code motion

Loop-invariant code motion

In computer programming, loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program...

at the same time. In addition, PRE can be extended to eliminate injured partial redundancies, thereby effectively performing strength reduction

Strength reduction

Strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array...

. This makes PRE one of the most important optimizations in optimizing compilers. Traditionally, PRE is applied to lexically equivalent expressions, but recently formulations of PRE based on static single assignment form

Static single assignment form

In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...

have been published that apply the PRE algorithm to values instead of expressions, unifying PRE and global value numbering

Global value numbering

Global value numbering is a compiler optimization based on the SSA intermediate representation. It sometimes helps eliminate redundant code that common subexpression elimination does not. At the same time, however, CSE may eliminate code that GVN does not, so both are often found in modern...

Further reading