Bài 6: Điều khiển luồng: Vòng lặp trong C và Assembly

1. Tổng quan về vòng lặp ở mức máy

Trong C, có ba dạng vòng lặp: do-while, while, và for. Tuy nhiên, ở mức mã máy (machine code), không có instruction nào hỗ trợ trực tiếp cho vòng lặp. Thay vào đó, trình biên dịch chuyển đổi tất cả các dạng vòng lặp thành tổ hợp các phép kiểm tra điều kiện (test) và nhảy có điều kiện (conditional jump).

Quy trình chuyển đổi tổng quát: for / while → do-while → goto + conditional jump → mã máy

2. Vòng lặp Do-While

2.1 Cấu trúc tổng quát

// C Code
do {
    Body
} while (Test);

Tương đương với dạng goto:

loop:
    Body
    if (Test) goto loop;

2.2 Ví dụ: Đếm số bit 1 (popcount)

// C Code
int pcount_do(unsigned int x) {
    int result = 0;
    do {
        result += x & 0x1;   // lấy bit thấp nhất
        x >>= 1;              // dịch phải 1 bit
    } while (x);
    return result;
}

Chuyển sang dạng goto:

int pcount_goto(unsigned int x) {
    int result = 0;
loop:
    result += x & 0x1;
    x >>= 1;
    if (x) goto loop;
    return result;
}

Assembly tương ứng (%edx = x, %ecx = result):

    movl  $0, %ecx      ; result = 0
.L2:                    ; loop:
    movl  %edx, %eax
    andl  $1, %eax      ; t = x & 1
    addl  %eax, %ecx    ; result += t
    shrl  %edx          ; x >>= 1
    jne   .L2           ; if (x != 0) goto loop

3. Vòng lặp While

3.1 Khác biệt với Do-While

Đặc điểmdo-whilewhile
Kiểm tra điều kiệnSau BodyTrước Body
Số lần thực hiện tối thiểu10

3.2 Dạng 1: “Nhảy vào giữa” (Jump-to-middle) — dùng với -Og

// While version
while (Test)
    Body

Chuyển sang goto:

    goto test;        // nhảy thẳng đến kiểm tra điều kiện
loop:
    Body
test:
    if (Test) goto loop;
done:

Ví dụ popcount:

int pcount_goto_jtm(unsigned int x) {
    int result = 0;
    goto test;          // bắt đầu tại test
loop:
    result += x & 0x1;
    x >>= 1;
test:
    if (x) goto loop;
    return result;
}

3.3 Dạng 2: Chuyển sang Do-While — dùng với -O1

// Dạng Do-While tương đương
if (!Test) goto done;    // kiểm tra trước, nếu sai thì bỏ qua
loop:
    Body
    if (Test) goto loop;
done:

Ví dụ popcount:

int pcount_goto_dw(unsigned int x) {
    int result = 0;
    if (!x) goto done;    // thoát ngay nếu x = 0
loop:
    result += x & 0x1;
    x >>= 1;
    if (x) goto loop;
done:
    return result;
}

4. Vòng lặp For

4.1 Cấu trúc tổng quát

for (Init; Test; Update)
    Body

Tương đương hoàn toàn với while:

Init;
while (Test) {
    Body
    Update;
}

4.2 Ví dụ: popcount dùng for

#define WSIZE 8*sizeof(int)   // = 32

int pcount_for(unsigned int x) {
    size_t i;
    int result = 0;
    for (i = 0; i < WSIZE; i++) {
        unsigned bit = (x >> i) & 0x1;
        result += bit;
    }
    return result;
}

Chuyển sang while:

int pcount_for_while(unsigned int x) {
    size_t i;
    int result = 0;
    i = 0;
    while (i < WSIZE) {
        unsigned bit = (x >> i) & 0x1;
        result += bit;
        i++;
    }
    return result;
}

Chuyển tiếp sang do-while (goto version):

int pcount_for_goto_dw(unsigned int x) {
    size_t i;
    int result = 0;
    i = 0;
    if (!(i < WSIZE)) goto done;   // Init xong, kiểm tra Test
loop:
    {
        unsigned bit = (x >> i) & 0x1;
        result += bit;
    }
    i++;                           // Update
    if (i < WSIZE) goto loop;      // Test
done:
    return result;
}
flowchart TD A[Init: i = 0] --> B{Test: i < WSIZE?} B -- No --> E[done: return result] B -- Yes --> C["Body: bit = (x >> i) & 1\nresult += bit"] C --> D["Update: i++"] D --> B

5. Ví dụ chuyển C → Assembly

5.1 Vòng lặp for với bước nhảy 2

int func1(int a) {
    int sum = 0;
    for (int i = 0; i < a; i += 2)
        sum += (a - i);
    return sum;
}

Assembly (dạng jump-to-middle):

; a ở 8(%ebp)
    movl  $0, -4(%ebp)      ; sum = 0
    movl  $0, -8(%ebp)      ; i = 0
    jmp   .test             ; nhảy đến kiểm tra điều kiện trước

.Loop:
    movl  8(%ebp), %eax     ; eax = a
    subl  -8(%ebp), %eax    ; eax = a - i
    addl  %eax, -4(%ebp)    ; sum += (a - i)
    addl  $2, -8(%ebp)      ; i += 2

.test:
    movl  8(%ebp), %eax     ; eax = a
    cmpl  -8(%ebp), %eax    ; so sánh a với i
    jg    .Loop             ; if (a > i) goto Loop
; return sum

6. Ví dụ đọc Assembly → C

6.1 Ví dụ 1

; x at 8(%ebp)
    movl  $0, -4(%ebp)      ; count = 0
.L1:
    addl  $2, 8(%ebp)       ; x += 2
    incl  -4(%ebp)          ; count++
    cmpl  $9, 8(%ebp)       ; so sánh 9 với x
    jle   .L1               ; if (x <= 9) goto L1
    movl  -4(%ebp), %eax    ; return count

Phân tích:

  • Không có jmp trước .L1 → dạng do-while (body thực hiện trước)
  • Điều kiện duy trì: x <= 9
  • Body: x += 2; count++
int count = 0;
do {
    x += 2;
    count++;
} while (x <= 9);

6.2 Ví dụ 2

    movl  $0, -8(%ebp)      ; count = 0
    movl  $0, -4(%ebp)      ; i = 0
.L2:
    cmpl  $19, -4(%ebp)     ; so sánh 19 với i
    jg    .L3               ; if (i > 19) thoát
    movl  -4(%ebp), %eax
    addl  %eax, -8(%ebp)    ; count += i
    incl  -4(%ebp)          ; i++
    jmp   .L2               ; luôn nhảy về L2
.L3:

Phân tích:

  • Có kiểm tra điều kiện trước body → dạng while
  • Điều kiện dừng: i > 19 → điều kiện duy trì: i <= 19, tức i < 20
int count = 0;
for (int i = 0; i < 20; i++)
    count += i;
// hoặc tương đương:
int i = 0, count = 0;
while (i < 20) {
    count += i;
    i++;
}

6.3 Ví dụ 3

    movl  $0, -8(%ebp)      ; count = 0
    movl  $0, -4(%ebp)      ; i = 0
.L1:
    cmpl  $25, -4(%ebp)
    jge   .L3               ; if (i >= 25) thoát
    movl  -4(%ebp), %eax    ; eax = i
    cmpl  -8(%ebp), %eax    ; so sánh i với count
    jg    .L2               ; if (i > count) bỏ qua addl
    addl  %eax, -8(%ebp)    ; count += i
.L2:
    subl  %eax, -8(%ebp)    ; count -= i  (luôn thực hiện)
    incl  -4(%ebp)          ; i++
    jmp   .L1
.L3:
int i = 0, count = 0;
while (i < 25) {
    if (i <= count)
        count += i;
    count -= i;
    i++;
}

6.4 Ví dụ 4 — Mảng ký tự

; &a[0] at 8(%ebp), len at 12(%ebp)
    movl  $0, -8(%ebp)      ; result = 0
    movl  $0, -4(%ebp)      ; i = 0
    jmp   .L2
.L3:
    movl  -4(%ebp), %edx    ; edx = i
    movl  8(%ebp), %eax     ; eax = &a[0]
    addl  %edx, %eax        ; eax = &a[0] + i = &a[i]
    mov   (%eax), %al       ; al = a[i]  (1 byte, char)
    subl  $48, %eax         ; eax = a[i] - 48  (chuyển '0'-'9' → 0-9)
    addl  %eax, -8(%ebp)    ; result += a[i] - 48
    addl  $1, -4(%ebp)      ; i++
.L2:
    movl  -4(%ebp), %eax
    cmpl  12(%ebp), %eax    ; so sánh i với len
    jl    .L3               ; if (i < len) goto L3
    movl  -8(%ebp), %eax    ; return result
int result = 0;
for (int i = 0; i < len; i++)
    result += a[i] - 48;

7. Câu hỏi trắc nghiệm (Ví dụ 5)

Đề bài: Cho đoạn assembly sau, chọn đoạn C tương ứng:

; a at 8(%ebp), b at 12(%ebp), i at -4(%ebp), sum at -8(%ebp)
.L3:
    movl  8(%ebp), %eax     ; eax = a
    addl  12(%ebp), %eax    ; eax = a + b
    addl  %eax, -8(%ebp)    ; sum += (a + b)
    addl  $2, -4(%ebp)      ; i += 2
    cmpl  $10, -4(%ebp)     ; so sánh 10 với i
    jl    .L3               ; if (i < 10) goto L3

Các lựa chọn:

  • A. do { a += b; sum += a; i += 2; } while (i < 10);
  • B. do { sum += a + b; i += 2; } while (i <= 10);
  • C. A và B đúng
  • D. A và B sai

8. Extra: Các kỹ thuật nâng cao liên quan

8.1 Instruction SetX — Gán giá trị dựa trên điều kiện

Thay vì dùng jump để rẽ nhánh, có thể dùng setX để gán 0 hoặc 1 vào một byte dựa trên condition codes:

InstructionĐiều kiệnÝ nghĩa
seteZFEqual / Zero
setne~ZFNot Equal
setg~(SF^OF)&~ZFGreater (signed)
setge~(SF^OF)Greater or Equal (signed)
setlSF^OFLess (signed)
setle(SF^OF)|ZFLess or Equal (signed)
seta~CF&~ZFAbove (unsigned)
setbCFBelow (unsigned)

Ví dụ:

int gt(long x, long y) {
    return x > y;
}
    cmpq  %rsi, %rdi    ; so sánh x và y
    setg  %al           ; al = 1 nếu x > y, else 0
    movzbl %al, %eax    ; zero-extend al → eax (xóa 3 byte cao)
    ret

8.2 Conditional Move — Tránh phân nhánh

cmovX thực hiện move nếu điều kiện thỏa, giúp tránh pipeline stall do branch prediction.

long absdiff(long x, long y) {
    return (x > y) ? (x - y) : (y - x);
}
    movq  %rdi, %rax    ; result = x
    subq  %rsi, %rax    ; result = x - y
    movq  %rsi, %rdx
    subq  %rdi, %rdx    ; eval = y - x
    cmpq  %rsi, %rdi    ; so sánh x và y
    cmovle %rdx, %rax   ; nếu x <= y thì result = eval
    ret