오늘은 제어문


    1. 조건 코드

    CF: Carry flag. 가장 최근 연산에서 가장 중요한 비트의 올림 발생 표시.

    ZF: Zero flag. 가장 최근 연산의 결과가 0인 것을 표시.

    SF: Sign flag. 가장 최근 연산이 음수인 것을 표시.

    OF: Overflow flag. 가장 최근 연산에서 양수/음수 2의 보수 오버플로 발생 표시.


    이 조건 코드 4개가 많이 유용하다고.

    만약 C코드 t = a + b를 수행하기 위해 add 인스트럭션을 사용했을 때 위 네가지 조건 코드는 아래의 C 수식에 따라 결정된다.

    CF = (unsigned)t < (unsigned)a

    ZF = (t == 0)

    SF = (t < 0)

    OF = (a < 0 == b < 0) && (t < 0 != a < 0)


    어제 글에서 수식 계산에 잘 써먹었던 leaq 인스트럭션은 주소 계산에 사용하기 위한 것으로, 조건 코드를 변경하지 않는다.

    그밖에 소개했던 산술연산에 쓰이는 다른 인스트럭션은 조건 코드 값을 변경한다.

    xor 같은 논리연산은 CF와 OF를 0으로 설정한다.

    쉬프트 연산은 CF가 마지막으로 쉬프트되는 비트로 설정되며 OF는 0으로 설정된다.

    INC와 DEC는 OF와 ZF를 설정하지만, CF에는 영향을 주지 않는다.



    2. CMP, TEST 인스트럭션

    다른 레지스터는 변경시키지 않고 조건 코드만 변경시키는 인스트럭션 클래스가 있다.

    Instruction

    Based on

    Description

    CMP    S1, S2

    S2 - S1

    Compare

     cmpb

    Compare byte

     cmpw

    Compare word

     cmpl

    Compare double word

     cmpq

    Compare quad word

    TEST    S1, S2

    S1 & S2

    Test

     testb

    Test byte

     testw

    Test word

     testl

    Test double word

     testq

    Test quad

    CMP는 레지스터에 영향을 주지 않는단 차이를 제외하면 SUB 인스트럭션과 동일하다.

    같은 관점에서 TEST도 AND 인스트럭션과 동일하다.



    3. SET, JMP, CMOV 인스트럭션

    조건 코드를 이용하는 보편적인 세 가지 방법이 있다.


    (1) 조건에 따라 0 또는 1을 한 개의 바이트에 기록하기

    SET 인스트럭션을 이용한다.

    Instruction

    Synonym

    Effect

    Set condition

    sete    D

    setz

    D <- ZF

    Equal / zero

    setne    D

    setnz

    D <- ~ZF

    Not equal / not zero

    sets    D

    D <- SF

    Negative

    setns    D

    D <- ~SF

    Nonnegative

    setg    D

    setnle

    D <- ~(SF^OF) & ~ZF

    Greater (signed >)

    setge    D

    setnl

    D <- ~(SF^OF)

    Greater or equal (signed >=)

    setl    D

    setnge

    D <- SF^OF

    Less (signed <)

    setle    D

    setng

    D <- (SF^OF) | ZF

    Less or equal (signed <=)

    seta    D

    setnbe

    D <- ~CF & ~ZF

    Above (unsigned >)

    setae    D

    setnb

    D <- ~CF

    Above or equal (unsigned >=)

    setb    D

    setnae

    D <- CF

    Below (unsigned <)

    setbe    D

    setna

    D <- CF | ZF

    Below or equal (unsigned <=)

    여기서 l과 b는 각각 less와 below를 뜻한다. long word나 byte로 헷갈리지 말자.


    C코드로 사용 예를 보자.

    long cmp(long a, long b) {
        return a < b;
    }

    gcc -Og -S cmp.c로 컴파일.

    comp:
    .LFB0:
        .cfi_startproc
        cmpq    %rsi, %rdi    ; Compare a:b
        setl    %al           ; Set low-order byte to %eax to 0 or 1
        movzbl  %al, %eax     $ Clear rest of %eax (and rest of %rax)
        ret
        .cfi_endproc


    (2) 조건에 따라 프로그램의 다른 부분으로 이동하기

    JMP 인스트럭션을 사용하여 조건에 따라(필요하다면 조건 없이) 프로그램의 다른 부분으로 이동할 수 있다.

    Instruction

    Synonym

    Jump condition

    Description

    jmp    Label

    ZF

    Direct jump

    jmp    *Operand

    ZF

    Equal / zero

    je    Label

    jz

    ZF

    Equal / zero

    jne    Label

    jnz

    ~ZF

    Not equal / not zero

    js    Label

    SF

    Negative

    jns    Label

    ~SF

    Nonnegative

    jg    Label

    jnle

    ~(SF ^ OF) & ~ZF

    Greater (signed >)

    jge    Label

    jnl

    ~(SF ^ OF)

    Greater or equal (signed >=)

    jl    Label

    jnge

    SF ^ OF

    Less (signed <)

    jle    Label

    jng

    (SF ^ OF) | ZF

    Less or equal (signed <=)

    ja    Label

    jnbe

    ~CF & ~ZF

    Above (unsigned >)

    jae    Label

    jnb

    ~CF

    Above or equal (unsigned >=)

    jb    Label

    jnae

    CF

    Below (unsigned <)

    jbe    Label

    jna

    CF | ZF

    Below or equal (unsigned <=)

    조건부 JMP 인스트럭션은 Direct jump만 가능하다.


    C 코드로 if-else문을 작성해서 좀 더 자세히 살펴본다. 아래는 absdiff_se.c 내용이다.

    long lt_cnt = 0;
    long ge_cnt = 0;
    
    long absdiff_se(long x, long y) {
        long result;
        if (x < y) {
            lt_cnt++;
            result = y - x;
        }
        else {
            ge_cnt++;
            result = x - y;
        }
        return result;
    }

    gcc -Og -S absdiff_se.c의 결과로 나온 absdiff_se.s의 내용은 아래와 같다.

    absdiff_se:
    .LFB0:
        .cfi_startproc
        cmpq    %rsi, %rdi
        jl      .L4
        addq    $1, ge_cnt(%rip)    ; ge_cnt++
        movq    %rdi, %rax
        subq    %rsi, %rax          ; result = x - y
        ret                         ; Return
    .L4:
        addq    $1, lt_cnt(%rip)    ; le_cnt++
        movq    %rsi, %rax
        subq    %rdi, %rax          ; result = y - x
        ret                         ; Return
        .cfi_endproc

    gcc -c absdiff_se.s(또는 gcc -Og -c absdiff_se.c)의 결과로 나온 absdiff_se.o의 역어셈블 내용은 아래와 같다.

    0000000000000000 <absdiff_se>:
       0:   48 39 f7                cmp    %rsi,%rdi
       3:   7c 0f                   jl     14 <absdiff_se+0x14>
       5:   48 83 05 00 00 00 00    addq   $0x1,0x0(%rip)        ; d <absdiff_se+0xd>
       c:   01 
       d:   48 89 f8                mov    %rdi,%rax
      10:   48 29 f0                sub    %rsi,%rax
      13:   c3                      retq   
      14:   48 83 05 00 00 00 00    addq   $0x1,0x0(%rip)        ; 1c <absdiff_se+0x1c>
      1b:   01 
      1c:   48 89 f0                mov    %rsi,%rax
      1f:   48 29 f8                sub    %rdi,%rax
      22:   c3                      retq

    여기서 jl 인스트럭션의 인코딩에 주목해보자.

    7c는 jl 인스트럭션로 보인다. 그럼 jl 인스트럭션의 오퍼랜드로 온 0x0f는 어떻게 0x14로 유도된 것일까?


    JMP 인스트럭션을 인코딩하는 방법은 2가지가 있다. 첫번째가 PC relative 방법이고, 두번째가 절대 주소 방법이다. PC는 프로그램 카운터(Program Counter)를 뜻한다. 아마... rip 레지스터가 pc겠지...

    PC relative을 수행할 때, 관습상 PC의 값은 JMP 인스트럭션 자신의 주소가 아닌 그 다음 인스트럭션의 주소가 된다.


    다시 위 인코딩을 보면 jl 인스트럭션의 다음 인스트럭션, addq의 주소인 0x5에 상대주소 0xf가 더해져 0x14로 점프하게 됨을 알 수 있다.


    추가로 여기서 C의 if-else문의 제어흐름을 알아볼 수 있다.

    if (test-expr)
        then-statement
    else
        else-statement

    위와 같은 형태에 대한 어셈블리 구현은 아래와 같은 C 문법의 제어흐름을 가진다.

        t = test-expr;
        if (!t)
            goto false;
        then-statement
        goto done;
    false:
        else-statement
    done:


    (3) 조건에 따라 데이터를 전송하기

    조건에 따라 특정 실행경로를 따르는 방법은 간단하다. 그런데 최신 프로세서 입장에서 이는 매우 비효율적인 방법일 수 있다.


    나중에 다룰 내용인데, 프로세서는 고성능을 위해 파이프라인에 연속되는 인스트럭션을 중첩시킨다. 이를 위해서는 실행할 인스트럭션의 순서를 알 필요가 있고, 조건부 점프와 같은 분기가 이 과정을 힘들게 만든다.

    프로세서는 분기예측 회로를 통해 분기를 예측한다. 만약 이 예측이 잘못되면 그 때까지 작업한 결과를 버려야 한다. 그리고 제대로 된 분기에 맞춰 인스트럭션을 파이프라인에 다시 채워넣어야 한다. 결과적으로 약 15~30 클럭 사이클의 손실을 발생시켜 프로그램 성능에 상당한 감소를 야기한다.


    그래서 조건부 동작의 결과를 모두 계산하고 조건에 따라 하나만 선택하는 방법이 존재한다.

    CMOV(조건부 mov) 인스트럭션에 대해 알아보자.

    Instruction

    Synonym

    Move condition

    Description

    cmove    S, R

    cmovz

    ZF

    Equal / zero

    cmovne    S, R

    cmovnz

    ~ZF

    Not equal / not zero

    cmovs    S, R

    SF

    Negative

    cmovns    S, R

    ~SF

    Nonnegative

    cmovg    S, R

    cmovnle

    ~(SF ^ OF) & ~ZF

    Greater (signed >)

    cmovge    S, R

    cmovnl

    ~(SF ^ OF)

    Greater or equal (signed >=)

    cmovl    S, R

    cmovnge

    SF ^ OF

    Less (signed <)

    cmovle    S, R

    cmovng

    (SF ^ OF) | ZF

    Less or equal (signed <=)

    cmova    S, R

    cmovnbe

    ~CF & ~ZF

    Above (unsigned >)

    cmovae    S, R

    cmovnb

    ~CF

    Above or equal (unsigned >=)

    cmovb    S, R

    cmovnae

    CF

    Below (unsigned <)

    cmovbe    S, R

    cmovna

    CF | ZF

    Below or equal (unsigned <=)

    이 인스트럭션들은 조건을 만족하면 값 S를 목적지 R에 복사한다.


    어떻게 사용되는지 알기 위해 책에 있는 absdiff 코드를 두개의 최적화 옵션으로 컴파일했다.

    long absdiff(long x, long y) {
        long result;
        if (x < y)
            result = y - x;
        else
            result = x - y;
        return result;
    }


    Og 옵션으로 컴파일했을 때. cmpq %rsi, %rdi의 결과에 따라서 분기가 나뉜다.

    absdiff:
    .LFB0:
        .cfi_startproc
        cmpq    %rsi, %rdi
        jl      .L4
        movq    %rdi, %rax
        subq    %rsi, %rax
        ret
    .L4:
        movq    %rsi, %rax
        subq    %rdi, %rax
        ret
        .cfi_endproc


    O1 옵션으로 컴파일했을 때. 분기에 따른 계산을 모두 마쳐놓고 조건에 따라서 값을 복사하고 있다.

    absdiff:
    .LFB0:
        .cfi_startproc
        movq    %rsi, %rdx
        subq    %rdi, %rdx    ; %rdx = y - x
        movq    %rdi, %rax
        subq    %rsi, %rax    ; %rax = x - y
        cmpq    %rsi, %rdi    ; Compare x:y
        cmovl   %rdx, %rax    ; if (x < y) %rax = %rdx
        ret
        .cfi_endproc

    책은 위 어셈블리 코드의 동작을 모사한 C 코드로 아래를 제시한다.

    long cmovdiff(long x, long y) {
        long rval = y - x;
        long eval = x - y;
        long ntest = x >= y;
        /* Line below requires single instruction: */
        if (ntest) rval = eval;
        return rval;
    }


    두 개의 어셈블리 코드는 성능이 얼마나 차이날까? 손실값을 계산해보자.

    예측오류 확률을 , 예측 오류 없이 코드를 실행한 시간을 , 예측오류 손실을 라고 하자.

    p에 대한 함수, 평균 코드실행 시간은 다음과 같다.


    일 때의 와 평균시간 이 주어졌을 때, 를 결정하고자 한다.

    수식에 대입하면,


    책에 의하면 분기가 나뉘는 위 어셈블리 코드에서 분기 패턴이 쉽게 예측되는 경우에는 8클럭을, 분기 패턴이 랜덤인 경우에는 약 17.50클럭을 소모한다.

    분기 예측오류 손실 는 다음과 같다.

    분기 예측오류 손실이 약 19클럭 사이클임을 유추했다. 이 함수 호출에 대해서 분기가 잘못 예측되면 27클럭을 소모할 수 있단 이야기다.


    그 반면에 CMOV 인스트럭션을 사용한 위 어셈블리 코드에서는 테스트에 사용되는 데이터와 상관없이 약 8클럭을 소모한다고 한다.

    생각보다 차이가 큰 걸 알 수 있다.


    마지막으로 정리하면,

    v = test-expr ? then-expr : else-expr;

    위 수식에 대한 조건부 제어 전송을 이용한 컴파일은 다음의 형태를 가진다.

        if (!test-expr)
            goto false;
        v = then-expr;
        goto done;
    false:
        v = else-expr;
    done:

    위 수식에 대해 조건부 이동을 이용한 컴파일은 다음의 형태를 가진다.

    v  = then-expr;
    ve = else-expr;
    t  = test-expr;
    if (!t) v = ve;



    4. 반복문

    C에서 제공하는 반복문은 3가지가 있다. do-while, while, 그리고 for.


    (1) Do-While 반복문

    일반적인 do-while문의 형태는 다음과 같다.

    do
        body-statement
    while (test)-expr;

    위 코드에 대한 일반적인 제어흐름은 다음과 같다.

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

    예시는 안쓴다.


    (2) While 반복문

    일반적인 while문의 형태는 다음과 같다.

    while (test-expr)
        body-statement

    위 코드에 대한 일반적인 제어흐름은 다음과 같다.

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

    조건형 do-while문이라고 부르는 형태도 있다. 보통 상위수준의 최적화로 컴파일할 때 이런 방식을 따른다.

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



    (3) For 반복문

    for문의 형태는 다음과 같다.

    for (init-expr; test-expr; update-expr)
        body-statement

    C 표준에는 한 가지 예외를 제외하고 위 for문이 아래 while문과 동일한 동작을 한다고 기록돼있다.

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

    body-statement에 continue가 삽입되면 위와 같은 형태로는 for문을 표현할 수 없다.

    아마 continue가 적절하게 goto문으로 번역돼야하지 않을까...



    5. switch문

    switch문은 점프 테이블이라는 자료구조를 사용해서 효율적으로 구현될 수 있다.

    void switch_eg(long x, long n, long *dest) {
        long val = x;
    
        switch (n) {
    
        case 100:
            val *= 13;
            break;
    
        case 102:
            val += 10;
            /* Fall through */
    
        case 103:
            val += 11;
            break;
    
        case 104:
        case 106:
            val *= val;
            break;
    
        default:
            val = 0;
        }
        *dest = val;
    }

    명령줄 옵션 -Og -S를 줘서 gcc를 실행한 결과이다.

    switch_eg:
    .LFB0:
        .cfi_startproc
        subq    $100, %rsi             ; Compute index = n - 100
        cmpq    $6, %rsi               ; Compare index:6
        ja      .L8                    ; if (index > 6) goto default
        leaq    .L4(%rip), %rcx        ; %rcx = &jump_table[0]
        movslq  (%rcx,%rsi,4), %rax    ; %rax = jump_table[%rsi]
        addq    %rcx, %rax             ; %rax += %rcx
        jmp     *%rax
        .section    .rodata
        .align 4
        .align 4
    .L4:
        .long   .L3-.L4    ; case 100:
        .long   .L8-.L4    ; default:
        .long   .L5-.L4    ; case 102:
        .long   .L6-.L4    ; case 103:
        .long   .L7-.L4    ; case 104: case 106:
        .long   .L8-.L4    ; default:
        .long   .L7-.L4    ; case 104: case 106:
        .text
    .L3:                           ; case 100:
        leaq    (%rdi,%rdi,2), %rax
        leaq    (%rdi,%rax,4), %rdi    ; val *= 13
        jmp     .L2                    ; Goto done
    .L5:                           ; case 102:
        addq    $10, %rdi              ; val += 10
    .L6:                           ; case 103:
        addq    $11, %rdi              ; val += 11
    .L2:                           ; Done:
        movq    %rdi, (%rdx)           ; *dest = val
        ret                            ; Return
    .L7:                           ; case 104: case 106:
        imulq   %rdi, %rdi             ; val *= val
        jmp     .L2                    ; Goto done
    .L8:                           ; default:
        movl    $0, %edi               ; val = 0
        jmp     .L2                    ; Goto done
        .cfi_endproc

    .L4가 점프 테이블이다.


    책을 보니 점프테이블은 rodata 영역에 저장된다는데...

    궁금해서 실행파일을 빌드하고 찾아봤다.

    00000000000006c0 <switch_eg>:
     6c0:   48 83 ee 64             sub    $0x64,%rsi
     6c4:   48 83 fe 06             cmp    $0x6,%rsi
     6c8:   77 2c                   ja     6f6 <switch_eg+0x36>
     6ca:   48 8d 0d 03 01 00 00    lea    0x103(%rip),%rcx        ; 7d4 <_IO_stdin_used+0x4>
     6d1:   48 63 04 b1             movslq (%rcx,%rsi,4),%rax
     6d5:   48 01 c8                add    %rcx,%rax
     6d8:   ff e0                   jmpq   *%rax
     6da:   48 8d 04 7f             lea    (%rdi,%rdi,2),%rax
     6de:   48 8d 3c 87             lea    (%rdi,%rax,4),%rdi
     6e2:   eb 08                   jmp    6ec <switch_eg+0x2c>
     6e4:   48 83 c7 0a             add    $0xa,%rdi
     6e8:   48 83 c7 0b             add    $0xb,%rdi
     6ec:   48 89 3a                mov    %rdi,(%rdx)
     6ef:   c3                      retq   
     6f0:   48 0f af ff             imul   %rdi,%rdi
     6f4:   eb f6                   jmp    6ec <switch_eg+0x2c>
     6f6:   bf 00 00 00 00          mov    $0x0,%edi
     6fb:   eb ef                   jmp    6ec <switch_eg+0x2c>

    점프테이블이 0x7d4 영역에 있댄다. 아마 여기가 rodata 영역인가 보다.


    objdump -sj .rodata switch_eg

    위 명령어를 쳐서 rodata 영역을 봤다.

    0x7d4에 7개의 4바이트 정수 테이블이 있는 걸 확인할 수 있었다.

    책 예제를 보면 이 함수테이블에 주소를 직접 적어놓아서 한번에 점프하던데 언제부터 이렇게 바뀌었는진 궁금하다.



    6. 마무리

    내일 3장을 끝낼 수 있을 것 같다ㅎㅎ



    출처:

    'Computer Systems A Programmer's Perspective (3rd Edition)'



    Posted by 코요

티스토리 툴바