Consider this high-level code sequence of three statements:

A = B + C;
B = A + C;
D = A €“ B;

Use the technique of copy propagation (see Figure A.20) to transform the code sequence to the point where no operand is a computed value. Note the instances in which the transformation has reduced the computational work of a statement and those cases where the work has increased. What does this suggest about the technical challenge faced in trying to satisfy the desire for optimizing compilers?

Figure A.20

Transcribed Image Text:

Percentage of the total number of optimizing transforms Optimization name Explanation At or near the source level; processor- independent High-level Procedure integration Replace procedure call by procedure body Within straight-line code N.M. Local Common subexpression elimination Replace two instances of the same computation by single copy 18% Constant propagation Replace all instances of a variable that is assigned a constant with the constant 22% Stack height reduction Rearrange expression tree to minimize resources needed for expression evaluation N.M. Across a branch Global Global common subexpression elimination Same as local, but this version crosses branches 13% Replace all instances of a variable A that has been assigned X (i.e., A = X) with X Copy propagation 11% Code motion Remove code from a loop that computes same value each iteration of the loop 16% Simplify/eliminate array addressing calculations within loops 2% Induction variable elimination Processor-dependent Depends on processor knowledge Many examples, such as replace multiply by a constant with adds and shifts Strength reduction N.M. Reorder instructions to improve pipeline performance N.M. Pipeline scheduling Branch offset optimization N.M. Choose the shortest branch displacement that reaches target