Questions: Array Subscript Optimization

Question 1

A compiler applies strength reduction to the loop `for (i=0; i<n; i++) a[i] = 0;`. Which transformation best describes what happens to the address calculation `base + i * element_size`?

• A. The multiplication is replaced by a left shift, because element_size is always a power of two
• B. A pointer `p` is initialized to `base` before the loop and incremented by `element_size` each iteration, replacing the multiply-add with a single add
• C. The loop is unrolled so the multiplication only executes every other iteration
• D. The subscript is cached and reused, so the multiplication executes once regardless of loop length

Answer: (B)

Strength reduction for a derived induction variable replaces the per-iteration `multiply + add` with a single `add`. A pointer is initialized to `base` before the loop and advanced by `element_size` on each iteration — producing the same address sequence with no multiplication. Option A (shift) is a narrower optimization that only works for power-of-two element sizes and is a separate transformation. Option D describes constant folding, not strength reduction for a loop-varying expression.

Question 2

A student claims that array subscript optimization changes which memory locations are accessed in order to improve performance. Is this correct?

• A. Yes — the optimizer reorders memory accesses to improve cache behavior
• B. Yes — the optimizer skips redundant accesses identified by data dependence analysis
• C. No — strength reduction produces the same address sequence using cheaper arithmetic operations
• D. No — the optimizer replaces array accesses with register variables, eliminating memory access entirely

Answer: (C)

Strength reduction is purely an arithmetic optimization: it computes the same addresses using additions instead of multiplications. The memory access pattern — which locations are touched, in what order — is unchanged. This is confirmed by data dependence analysis, which verifies that the new pointer-based access visits the same locations in the same order, preserving all dependencies. Option A (cache reordering) describes loop interchange or tiling, which are separate transformations.

Question 3

Strength reduction can be applied to `a[b[i]]` when `b[i]` is known to be monotonically increasing.

• T. True
• F. False

Answer: False

Strength reduction requires a *linear* function of the loop induction variable: the address must advance by a constant stride each iteration. `a[b[i]]` uses indirect indexing — the subscript depends on the contents of `b`, which are generally not known at compile time and not necessarily a constant stride. Strength reduction does not apply here, even if `b[i]` happens to be monotone at runtime.

Question 4

In a doubly-nested loop accessing `a[i][j]`, strength reduction can eliminate both the outer and inner multiplications by maintaining a separate pointer for each loop level.

• T. True
• F. False

Answer: True

For `a[i][j]`, the unoptimized address involves `base + i * row_size + j * element_size` — two multiplications. The outer multiplication (involving `i`) can be reduced by a row pointer updated in the outer loop; the inner multiplication (involving `j`) can be reduced by a column pointer updated in the inner loop. Both are linear functions of their respective loop variables, so both qualify for strength reduction independently. This compounds the savings in nested-loop linear algebra code.

Question 5

Why is array subscript optimization especially important for dense linear algebra code rather than for code with irregular access patterns?

Model answer: Dense linear algebra (matrix multiply, convolution, stencils) has inner loops that execute millions of times with regular, strided array access. Each iteration has a constant address stride, so the subscript forms a derived induction variable — exactly the pattern that makes strength reduction applicable and impactful. Irregular access patterns (e.g., sparse matrices, hash tables) involve non-linear or data-dependent subscripts where no constant stride exists, so strength reduction cannot apply.

The optimization's benefit scales with loop trip count: replacing a multiply with an add saves a small constant per iteration, but in a loop running 10⁸ times that constant dominates total execution time. Dense linear algebra is the prototypical case because it combines high trip counts with perfectly regular stride patterns. Irregular patterns break the linear induction variable assumption, so the compiler cannot safely substitute an increment for the general address calculation.