The point
Two loop optimizations you will not implement, worked by hand so you can discuss them accurately — and one you already have without noticing.
Do this
- Unroll by hand. Take
and write both the normal lowering and a fully unrolled version. Count instructions in each listing, and count how many execute in each.for (i = 0; i < 4; i = i + 1) { s = s + a[i]; } - Partial unrolling. Unroll by two instead. What must be true of the trip count for this to be correct, and what extra code is needed when it is not?
- When does unrolling lose? Change the loop to 10,000 iterations and reason about it. Name two costs, at least one of which is not code size.
- Loop-invariant code motion. In
while (i <= n - 1) { ... }, which computation is invariant? Move it. What would the compiler have to prove before it could do this automatically? - Strength reduction. Rewrite the indexed loop to keep a running address and add 4 each iteration instead of multiplying. Count the instructions saved per iteration.
- Find the one you already have. Locate the existing strength reduction in the code generator, and say why the compiler can always apply that one safely.
On step 3
Code size, and instruction-cache pressure. A loop body that fitted in cache may not after unrolling, and a cache miss costs far more than the compare-and-branch you removed. This is why unrolling decisions in production compilers are driven by measured heuristics rather than by a rule — and why Dragon §9.1 is careful to say that loop optimizations are where the gains are usually found.
Deliverable
Both unrolled listings with instruction counts; your answers on partial unrolling and on the two costs; the hoisted invariant with the condition the compiler would have to prove; the strength-reduced loop; and the location of the existing one. Feeds Lab Question 21.