Computer Architecture

Qn: 6

Consider the high level code sequence of three statements.

A= B+C

B=A+C

D=A-B

Use the technique of copy propagation (See Fig 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?

Sol:

A=B+C A=B+C the operands are given not computed by the code. So copy propagation will not transform this statement.

B=A+C here A is a computed value, so transform the code by substituting A=B+C

B= (B+C)+C Here no operand is computed

D=A-B both operands are computed so substitute for both

D=(B+C)-(B+C+C)

D=-C This is given not computed operand

Hence the reduced code with no computed operand is

A=B+C

B=B+C+C

D=-C

Copy propogation has increased the work in statement 2 from one addition to two additions. It has changed the work in statement 3 from substraction to negation. This requires reduced work over the addition.

Technicial Challenges in Optimizing compilers:

—The machine architectures differ so much that an optimization that is effective on one architecture may not be effective on a different architecture.

Transformations that are performed have to be safe and reliable.

—Produce correct results

• Correct results occur when dependences are satisfied

Qn#7: Consider the following fragment of C Code:

For (i=0; i<=100; I++)

{A[i]=B[i]+C;}

Assume that A and B are arrays of 64 bit integers and C and I are 64 bit integers. Assume that all data values and their addresses are kept in memory (at addresses 1000, 3000, 5000 and 7000 for A,B, and I respectively) except when they are operated on. Assume that values in registers are lost between iterations of the loop.

a. Write the code for MIPS. How many instructions are required dynamically?...