Loops in Assembly

Implementing loop constructs in assembly language: for, while, do-while, and nested loops.

Introduction

Loops are the workhorses of programming — they repeat operations thousands or millions of times. In high-level languages, you write for or while and the compiler handles the details. In assembly, YOU handle the details: initializing a counter, comparing it each iteration, branching back or forward, and managing the loop body. Understanding how loops work at the assembly level explains why some code runs fast and other code is slow — it all comes down to how many instructions execute per iteration and how branches interact with the pipeline.

Loop Anatomy in Assembly

Every loop in assembly has four components:

1. INITIALIZATION	Set up counter/pointer before the loop
2. BODY	The actual work of each iteration
3. UPDATE	Modify counter/pointer for next iteration
4. CONDITION + BRANCH	Test if loop should continue, branch back or exit

For Loop

High-level: for (int i = 0; i < 10; i++) { sum += i; }

Example

# MIPS implementation li $t0, 0 # 1. INIT: i = 0 li $t1, 10 # limit = 10 li $t2, 0 # sum = 0 for_loop: bge $t0, $t1, for_end # 4. CONDITION: if i >= 10, exit add $t2, $t2, $t0 # 2. BODY: sum += i addi $t0, $t0, 1 # 3. UPDATE: i++ j for_loop # branch back to top for_end: # $t2 = 0+1+2+...+9 = 45

Execution trace:

Example

Iteration $t0(i) $t2(sum) Branch taken? 0 0 0 No (continue) 1 1 1 No 2 2 3 No ... 9 9 45 No 10 10 - Yes (exit)

Total instructions per iteration: 4 (bge, add, addi, j) → very tight loop.

While Loop

High-level: while (n > 1) { if (n%2==0) n=n/2; else n=3*n+1; count++; }

(Collatz conjecture)

Example

li $t0, 27 # n = 27 (starting value) li $t1, 0 # count = 0 while_loop: ble $t0, 1, while_end # while (n > 1) andi $t2, $t0, 1 # Check if n is odd (LSB) bnez $t2, odd_case # if odd, go to odd case # Even: n = n / 2 srl $t0, $t0, 1 # Shift right = divide by 2 j count_step odd_case: # Odd: n = 3*n + 1 sll $t2, $t0, 1 # $t2 = n * 2 add $t0, $t2, $t0 # $t0 = n*2 + n = n*3 addi $t0, $t0, 1 # $t0 = 3n + 1 count_step: addi $t1, $t1, 1 # count++ j while_loop while_end: # $t1 = number of steps (111 for n=27)

Architecture insight: The srl (shift right logical) for division by 2 is ONE cycle. An actual div instruction would take 30+ cycles!

Do-While Loop

High-level: do { read input; } while (input != 0);

assembly example

    li   $t1, 0              # sum = 0

do_while:
    # BODY executes at least once
    li   $v0, 5              # Read integer
    syscall
    move $t0, $v0            # input in $t0
    
    add  $t1, $t1, $t0       # sum += input
    
    bnez $t0, do_while       # CONDITION: repeat if input != 0
    
    # When we get here, user entered 0
    move $a0, $t1
    li   $v0, 1
    syscall                  # Print sum

The key difference: condition is checked at the END, so the body always executes at least once.

Nested Loops

Multiplication table (5×5):

Example

.data tab: .asciiz "\t" newline: .asciiz "\n" .text .globl main main: li $t0, 1 # i = 1 (outer) outer_loop: bgt $t0, 5, done # if i > 5, exit li $t1, 1 # j = 1 (inner — reset each outer iteration!) inner_loop: bgt $t1, 5, next_row # if j > 5, go to next row mul $a0, $t0, $t1 # product = i * j li $v0, 1 syscall # Print product la $a0, tab li $v0, 4 syscall # Print tab addi $t1, $t1, 1 # j++ j inner_loop next_row: la $a0, newline li $v0, 4 syscall # Print newline addi $t0, $t0, 1 # i++ j outer_loop done: li $v0, 10 syscall

Loop Optimization Techniques

1. Loop Unrolling

Process multiple elements per iteration to reduce branch overhead:

assembly example

# Original: 1 element per iteration (4 instructions overhead per element)
loop:
    lw   $t0, 0($t1)
    add  $t2, $t2, $t0
    addi $t1, $t1, 4
    addi $t3, $t3, -1
    bnez $t3, loop

# Unrolled: 4 elements per iteration (4 instructions overhead per 4 elements)
loop_unrolled:
    lw   $t0, 0($t1)
    lw   $t4, 4($t1)
    lw   $t5, 8($t1)
    lw   $t6, 12($t1)
    add  $t2, $t2, $t0
    add  $t2, $t2, $t4
    add  $t2, $t2, $t5
    add  $t2, $t2, $t6
    addi $t1, $t1, 16
    addi $t3, $t3, -4
    bnez $t3, loop_unrolled

Benefit: Branch overhead reduced from 25% to 7% of instructions.

2. Strength Reduction

Replace expensive operations with cheaper equivalents:

assembly example

# Expensive: multiply in each iteration
    mul  $t0, $t1, $t2       # Array offset = i × element_size (3-5 cycles)

# Cheap: incremental addition
    addi $t0, $t0, 4         # Just add element_size each time (1 cycle)

3. Loop Invariant Code Motion

Move calculations that do not change inside the loop to outside:

assembly example

# Bad: recalculates array base every iteration
loop:
    la   $t0, array          # REDUNDANT — same every iteration
    add  $t0, $t0, $t1
    lw   $t2, 0($t0)
    ...

# Good: calculate once before loop
    la   $t0, array          # Only once!
loop:
    add  $t3, $t0, $t1
    lw   $t2, 0($t3)
    ...

Performance Analysis

A loop with N iterations and B instructions per body:

Example

Total instructions = N × (B + overhead) Overhead per iteration = 1 compare + 1 branch + 1 update = 3 instructions For body of 5 instructions, N=1000: Total = 1000 × (5 + 3) = 8000 instructions Overhead fraction = 3/8 = 37.5% of all instructions are loop control!

This is why loop unrolling helps — it amortizes the 3-instruction overhead over more useful work.

Why Loops Matter for Architecture

Branch prediction: Loop back-branches are highly predictable (taken N-1 times, not-taken once). Predict-taken works well.
Cache behavior: Loops re-execute the same instructions — excellent temporal locality in I-cache.
Pipeline utilization: The backward branch at loop end is predicted correctly ~99% of the time in a counted loop.
Data prefetching: Sequential array access in loops has perfect spatial locality — hardware prefetchers love this pattern.

Key Takeaways

Every loop needs initialization, body, update, and conditional branch — the branch makes it a loop
For loops check the condition at the top (may execute zero times); do-while checks at bottom (always executes once)
Nested loops require resetting the inner counter on each outer iteration
Loop overhead (compare + branch + update) can be 25-50% of total instructions — unrolling reduces this
Loops are where programs spend most of their time — optimizing loop bodies has the highest performance impact
From the CPU perspective, a loop is just a backward branch that is almost always taken — branch predictors handle this efficiently

Introduction

Loop Anatomy in Assembly

Every loop in assembly has four components:

1. INITIALIZATION	Set up counter/pointer before the loop
2. BODY	The actual work of each iteration
3. UPDATE	Modify counter/pointer for next iteration
4. CONDITION + BRANCH	Test if loop should continue, branch back or exit

For Loop

High-level: for (int i = 0; i < 10; i++) { sum += i; }

Example

Execution trace:

Example

Iteration $t0(i) $t2(sum) Branch taken? 0 0 0 No (continue) 1 1 1 No 2 2 3 No ... 9 9 45 No 10 10 - Yes (exit)

Total instructions per iteration: 4 (bge, add, addi, j) → very tight loop.

While Loop

High-level: while (n > 1) { if (n%2==0) n=n/2; else n=3*n+1; count++; }

(Collatz conjecture)

Example

Architecture insight: The srl (shift right logical) for division by 2 is ONE cycle. An actual div instruction would take 30+ cycles!

Do-While Loop

High-level: do { read input; } while (input != 0);

assembly example

    li   $t1, 0              # sum = 0

do_while:
    # BODY executes at least once
    li   $v0, 5              # Read integer
    syscall
    move $t0, $v0            # input in $t0
    
    add  $t1, $t1, $t0       # sum += input
    
    bnez $t0, do_while       # CONDITION: repeat if input != 0
    
    # When we get here, user entered 0
    move $a0, $t1
    li   $v0, 1
    syscall                  # Print sum

The key difference: condition is checked at the END, so the body always executes at least once.

Nested Loops

Multiplication table (5×5):

Example

Loop Optimization Techniques

1. Loop Unrolling

Process multiple elements per iteration to reduce branch overhead:

assembly example

# Original: 1 element per iteration (4 instructions overhead per element)
loop:
    lw   $t0, 0($t1)
    add  $t2, $t2, $t0
    addi $t1, $t1, 4
    addi $t3, $t3, -1
    bnez $t3, loop

# Unrolled: 4 elements per iteration (4 instructions overhead per 4 elements)
loop_unrolled:
    lw   $t0, 0($t1)
    lw   $t4, 4($t1)
    lw   $t5, 8($t1)
    lw   $t6, 12($t1)
    add  $t2, $t2, $t0
    add  $t2, $t2, $t4
    add  $t2, $t2, $t5
    add  $t2, $t2, $t6
    addi $t1, $t1, 16
    addi $t3, $t3, -4
    bnez $t3, loop_unrolled

Benefit: Branch overhead reduced from 25% to 7% of instructions.

2. Strength Reduction

Replace expensive operations with cheaper equivalents:

assembly example

# Expensive: multiply in each iteration
    mul  $t0, $t1, $t2       # Array offset = i × element_size (3-5 cycles)

# Cheap: incremental addition
    addi $t0, $t0, 4         # Just add element_size each time (1 cycle)

3. Loop Invariant Code Motion

Move calculations that do not change inside the loop to outside:

assembly example

# Bad: recalculates array base every iteration
loop:
    la   $t0, array          # REDUNDANT — same every iteration
    add  $t0, $t0, $t1
    lw   $t2, 0($t0)
    ...

# Good: calculate once before loop
    la   $t0, array          # Only once!
loop:
    add  $t3, $t0, $t1
    lw   $t2, 0($t3)
    ...

Performance Analysis

A loop with N iterations and B instructions per body:

Example

This is why loop unrolling helps — it amortizes the 3-instruction overhead over more useful work.

Why Loops Matter for Architecture

Branch prediction: Loop back-branches are highly predictable (taken N-1 times, not-taken once). Predict-taken works well.
Cache behavior: Loops re-execute the same instructions — excellent temporal locality in I-cache.
Pipeline utilization: The backward branch at loop end is predicted correctly ~99% of the time in a counted loop.
Data prefetching: Sequential array access in loops has perfect spatial locality — hardware prefetchers love this pattern.

Key Takeaways

Every loop needs initialization, body, update, and conditional branch — the branch makes it a loop
For loops check the condition at the top (may execute zero times); do-while checks at bottom (always executes once)
Nested loops require resetting the inner counter on each outer iteration
Loop overhead (compare + branch + update) can be 25-50% of total instructions — unrolling reduces this
Loops are where programs spend most of their time — optimizing loop bodies has the highest performance impact
From the CPU perspective, a loop is just a backward branch that is almost always taken — branch predictors handle this efficiently

Loops in Assembly

Introduction

Loop Anatomy in Assembly

For Loop

While Loop

Do-While Loop

Nested Loops

Loop Optimization Techniques

1. Loop Unrolling

2. Strength Reduction

3. Loop Invariant Code Motion

Performance Analysis

Why Loops Matter for Architecture

Key Takeaways

Continue learning this concept

Loops in Assembly

Introduction

Loop Anatomy in Assembly

For Loop

While Loop

Do-While Loop

Nested Loops

Loop Optimization Techniques

1. Loop Unrolling

2. Strength Reduction

3. Loop Invariant Code Motion

Performance Analysis

Why Loops Matter for Architecture

Key Takeaways

Continue learning this concept