Using any ILP optimization, double the performance of the following loop, or explain why it is not possible. The machine can only do one branch per cycle, but has infinite resources otherwise.
r1 = ... ; r1 is head pointer to a linked list r3 = 0
LOOP:
r2 = M[r1 + 8]
r3 = r3 + r2 r1 = M[r1]
branch r1 != 0, LOOP
... = r3 ; r3 is used when loop complete

Question

Quizplus · Accepted Answer

The Answer is By performing the following code reordering we can avoid a 1-cycle stall due to a dependence between the first and second instructions of the loop:
r1 = ... ; r1 is head pointer to a linked list r3 = 0
LOOP:
r3 = r3 + r2 r2 = M[r1 + 8] r1 = M[r1]
branch r1 != 0, LOOP
... = r3 ; r3 is used when loop complete

Using Any ILP Optimization, Double the Performance of the Following