Loops

Do-while Loops

General Form

do {
    body-statement
} while (test-expr);          // repeat body while test-expr is non-zero

Notice: body-statement is executed at least once.

Example C code

fact_do(n) = n! = n * (n-1) * (n-2) * … * (1)

long fact_do(long n){
    long result = 1;
    do {
        result *= n;
        n = n - 1;
    } while (n > 1) ;
    return result;
}

Goto Form

loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;

C Code with goto and Conditional

long fact_do_goto(long n){
    long result = 1;
    loop:
    result *= n;
    n = n-1;
    if (n > 1)
        goto loop;
    return result;
}

Assembly Code

Note: n in %rdi

fact_do:
    movl    $1, %eax
.L2
    imulq  %rdi, %rax        // compute result *= n
    subq   $1, %rdi          // decrement n
    cmpq   $1, %rdi          // compare 1:n
    jg     .L2               // jump to repeat is n > 1 (like goto)
    rep;   ret

While-loops

General Form

while (test-expr){
    body-statement
}

Example C code

long fact_while(long n){
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n-1;
    }
    return result;
}

*** Jump to the Middle Form ***

    goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t)
        goto loop;

Assembly Code

Note: n in %rdi

fact_while:
    movl   $1,   %eax          // set result = 1
    jmp    .L5                 // jump to test
.L6:
    imulq  %rdi, %rax          // compute result *= n
    subq   $1,   %rdi          // decrement n
.L5:
    cmpq   $1,   %rdi          // compare 1:n
    jg     .L6
    rep;   ret

*** The Guarded-Do Form ***

    t = test-expr;
    if (!t)
        goto done;
loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;
done:

Assembly

Note: n in %rdi

fact_while:                        //return 1 or init result
    cmpq   $1,   %rdi
    jle    .L7
    movl   $1,   %eax              // set result = 1
.L6:
    imulq  %rdi, %rax              //result *= n
    subq   $1,   %rdi              // decrement n
    cmpq   $1,   %rdi              // compare 1:n
    jne    .L6
    rep;   ret
.L7
    movl   $1,   %eax              //result = 1
    ret

For-Loops

General Form

for(init-expr; test-expr; post-expr) {
    body-statement
}

Equivalent While-loop

init-expr;
while (test-expr) {
    body-statement
    update-expr;
}

Since there are two forms for while-loops, we have two ways to implement for-loops.

• Jump to the Middle Form
• Guarded Do Form.

Jump to the Middle Form

    init-expr;
    goto test;
loop:
    body-statement
    update-expression;
test:
    t = test-expr;
    if (t)
        goto loop;

Guarded Do Form

    init-expr;
    t = test-expr;
    if (!t)
        goto done;
loop:
    body-statement
    update-expr;
    if (t)
        goto loop;
done:

Example C Code

long fact_for(long n){
    long i;
    long result = 1;
    for (i = 2; i <= n; i++)
        result *= i;
    return result;
}

Assembly-code (Jump to the Middle)

Note: n in %rdi

fact_for:
    movl   $1,    %eax              // set result = 1
    movl   $2,    %edx              // Set i = 2;
    jmp    .L8
.L9
    imulq  %rdx,  %rax              // result *= i
    addq   $1,    %rdx              // increment i
.L8
    cmpq   %rdi,  %rdx              // compare n:i
    jle    .L9
    rep;   ret

© 2017 – 2018, Eric. All rights reserved.