Compiler Optimizations: Choosing the Correct Loop-Transformation Answer
When a compiler “merges two loops into a single loop,” the standard optimization is Loop Fusion. In contrast, Loop Unrolling and Strength Reduction change the loop body/operations but do not merge multiple loops into one. Loop Concatenation typically concatenates execution rather than fusing iteration spaces into one loop.
Correct option: (iv) Loop Fusion.
Loop Fusion (compiler optimization) - conceptual overview
Key ideas behind Loop Fusion
Loop Fusion works when two loops iterate over the same bounds/iteration space and the combined loop is legal (dependencies allow it). The compiler produces one loop whose body performs the operations from both original loops in the right order.
Common rationale:
- Fewer loop overheads (one loop control instead of two).
- Better locality (data may remain in caches/regs longer).
- Reduced memory traffic in some cases because intermediate results may not need to be written/read between loops.
How compilers apply loop transformations (typical flow)
Analyze dependence
1Check if reordering/combining loops preserves program semantics."
Apply legal transformation
2Use Loop Fusion when iteration spaces match and dependencies permit."
Optimize code generation
3Emit optimized loop structure for performance."
Effect of each option on “merging two loops into one”
Which transformations directly produce a single loop from two separate loops?
How to answer the multiple-choice question (elimination method)
- 1Step 1
The question asks for a transformation that turns two loops into one loop.
- 2Step 2
Remove transformations like Loop Unrolling and Strength Reduction because they don’t merge separate loops.
- 3Step 3
The only option that directly combines two loops over the same iteration space into a single loop is Loop Fusion.
- 4Step 4
Therefore, select option (iv) Loop Fusion.
Pro Tip
In exam questions, “two loops → one loop” is a strong hint for Loop Fusion (not unrolling or strength reduction).
Common confusion
“Concatenation” is sometimes mistaken for “fusion,” but fusion typically interleaves computations per iteration to form one loop over the shared iteration space.
Quick FAQs (to secure the concept)
Loop Fusion vs other loop transformations
Knowledge Check
By which of the following, bodies of two loops merges to form a single loop?