[시스템 프로그래밍] 어셈블리어[3] - 반복문

 

 

 

🧐 반복문

기계어에는 반복문에 대응되는 인스트럭션이 없습니다.

그 대신 조건부 테스트와, 점프 인스트럭션을 함께 사용하여 반복문을 표현합니다.

 

GCC 와 다른 컴파일러들은 반복문을 두 개의 기본 루프 패턴에 기초하여 코드를 생성합니다.

가장 간단한 do-while부터 시작하여 보다 복잡한 구현 방법을 살펴보며 두 가지 패턴을 다루도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 do - while

do-while 문장의 일반적인 형태는 아래와 같습니다.

do {
        body-statement
} while ( test-expr );

반복문은 body-statement 를 반복적으로 실행하고, test-expr 을 계산하여 그 결과가 0이 아니라면 반복합니다.

 

 

body-statement 는 적어도 한 번 실행된다는 것에 주목하며,

해당 반복문을 조건문 + goto문으로 바꿔보도록 하겠습니다.

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

 

 

 

 

실제 예시를 살펴보면 다음과 같습니다

long pcount_do(unsigned long x) {

    long result = 0;
    
    do {
        result += x & 0x1;
        
        x >>= 1;  
    } while (x);
    
    return result;
}

 

 

 

이를 goto 형태로 바꾸면 아래와 같습니다.

long pcount_goto(unsigned long x) {

    long result = 0;
    
  loop:
    result += x & 0x1;
    
    x >>= 1;
    
    if (x) goto loop;
    
    return result;
}

 

 

 

이를 어셈블리어로 번역하면 다음과 같습니다.

pcount_goto:
    
    movl $0, %eax  # result = 0
    
.L2:
    movq %rdi, $rdx # rdx = rdi(x)
    
    andl $1, %edx  # t = x & 0x1;
    addq %edx, %eax # result += t(x & 0x1); 
    shrq $1, %rdi # x >>= 1 (unsigned라 논리 쉬프트)
    jne .L2 # x 가 0이 아니면 L2로 이동
    rep; ret

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 while

while 문장의 일반적인 형태는 아래와 같습니다.

while ( test-expr )
      body-statement

 

while문은 test-expr 을 먼저 계산하여 body-statement 를 실행하기 전에 종료될 수 있다는 점에서 do-while문과 다릅니다.

 

while문을 기계어 코드로 번역하는 방법에는 여러 가지 방법이 있으며,

이 가운데 두 개의 방법이 GCC가 생성하는 코드에서 이용됩니다.

 

두 방법 모두 do-while 루프와 구조가 동일하고, 초기 테스트의 구현방법에서만 다릅니다.

 

 

 

 

 

 

⭐️ 중간으로 점프 (Jump to Middle)

기존 while문의 형태

while ( test-expr )
      body-statement

 

 

첫번째 방법은 중간으로 점프 입니다.

goto test;   # 바로 test로 이동합니다.

loop:
    body-statement

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

done:     

위와 같이 loop의 중간으로 이동하여 검사부터 진행합니다.

 

 

 

 

 

예시는 다음과 같습니다.

long pcount_while(unsigned long x) {

    long result = 0;
    
    while(x) {
        result += x & 0x1;   
        x >>= 1;  
    }
    
    return result;
}

 

 

 

이를 중간으로 점프를 사용하여 번역하면 다음과 같습니다.

long pcount_while(unsigned long x) {

    long result = 0;
    
    goto test;
    
 loop: 
    result += x & 0x1;
    
    x >>= 1;  

 test:
    if (x) goto loop;
    
    return result;
}

 

 

 

 

 

 

 

 

 

 

⭐️ 조건형 - do

조건형-do 라고 부르는 두 번째 번역방법은

먼저 코드를 조건부 분기를 이용해서 초기 테스트가 실패하는 경우에 루프를 건너뛰도록 하여

do-whille 루프로 번역합니다.

 

GCC의 경우 -O1 옵션을 사용하여 컴파일하는 경우 해당 전략을 따릅니다.

 

이 방법은 일반적인 while문의 형태를 do-while 루프로 번역할 때, 다음의 템플릿으로 표시될 수 있습니다.

 

기존 while문의 형태

while ( test-expr )
      body-statement

 

 

 

이를 조건형 - do 를 사용하여 번역하면 다음과 같습니다.

t = test-expr;

if (!t) goto done;

do {
    body-statement
    } while( test-expr );

done:

 

 

 

이는 다시 goto 코드로 다음과 같이 번역됩니다.

t = test-expr;

if (!t) goto done;

loop:
    body-statement
    t =  test-expr;

    if (t) goto loop;

done:

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 For 루프

for 반복문의 일반적인 유형은 다음과 같습니다.

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

 

 

C언어 표준에서는 위 반복문이 while 반복문을 사용하는 다음의 코드와 동일한 동작을 한다고 기록되어 있습니다.

(continue 사용하는 경우 제외)

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

 

프로그램은 먼저 초기화 수식인 init-expr을 계산합니다

테스트 조건인 test-expr을 계산하는 곳에서 루프에 들어가고,

테스트가 실패하면 루프를 빠져나오며,

성공했다면 반복문 body-statement를 실행하며, update-expr을 계산합니다

 

 

for루프에 대해 생성되는 코드는 위에서 살펴본 while -> do-while 의 방법에 따라 do-while로 번역됩니다.

 

 

 

 

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

 

(조건형 - do 사용)

init-expr;
t = test-expr;

if (!t) goto done;

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

done:

 

 

 

 

 

 

헷갈리실 것 같아 한번에 모아서 확인해보도록 하겠습니다.

⭐️ do - while

do {
        body-statement
} while ( test-expr );

 

조건문 + goto 로 번역

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

 

 

 

 

⭐️ while

while ( test-expr )
     body-statement

 

중간으로 점프

goto test;   # 바로 test로 이동합니다.

loop:
    body-statement

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

done:     

 

조건형 - do

t = test-expr;

if (!t) goto done;

do {
    body-statement
    } while( test-expr );

done:

 

 

⭐️ for

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

 

while로 번역

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

 

조건형 - do

init-expr;
t = test-expr;

if (!t) goto done;

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

done:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Switch

Switch문은 정수 인덱스 값에 따라 다중분기 기능을 제공합니다.

 

이것은 테스트해야 하는 경우의 수가 많은 경우에 특히 유용합니다.

 

Switch문을 사용하면 점프 테이블(Jump table)이라는 자료구조를 사용하여 효율적으로 조건에 따른 분기 기능을 제공합니다.

 

점프 테이블은 해당 테이블의 원소 i가, Switch문의 대상이 i일 때 프로그램이 실행해야 하는 동작을 구현하는 코드 블록의 주소가 되는 배열을 말합니다.

 

해당 코드는 점프 인스트럭션의 목적지를 찾아내기 위해서 switch문의 인덱스를 사용하여 점프 테이블을 배열처럼 참조합니다.

 

점프 테이블을 사용하면 switch문을 실행하는 데 걸리는 시간이 언제나 $O(1)의 시간$을 보장합니다.

이는 다단계의 if-else문을 사용하는 것보다 훨씬 효율적입니다.

 

참고 - (https://stackoverflow.com/questions/2158759/case-vs-if-else-if-which-is-more-efficient)

 

 

 

 

 

⭐️ 예시 코드

void switch_eg(long x, long n, long *dest) {

    long val = x;
    
    switch (x) {
        
    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;
}

 

 

 

 

이는 확장형 C에서 다음과 같이 번역됩니다.

void switch_eg_impl(long x, long n, long *dest) {

    /* Table of code pointers */
    static void *jt[7] = { // Jump table
        &&loc_A, &&loc_def, &&loc_B,
        &&loc_C, &&loc_D, &&loc_def,
        &&loc_D // D가 중복 정의 (104와 106이 동일 분기 주소로 엮기이 때문이다)
    };
    
    unsigned long index = n - 100; // unsigned int로 해준 이유는 `빠른 경계 검사`를 위해서입니다.
    long val;


    // index를 비부호형으로 하였기에 0 < index <= 6 의 범위를 가지는지를 조건문 한번으로 확인 
    if (index > 6) 
        goto loc_def; // default로 이동
        
        
    /* Multiway branch */
    goto *jt[index]; // Jump Table을 사용하여 O(1) 시간에 분기 주소로 이동
    
    
    
    
    
    /* 분기 주소들 */
    
    loc_A: /* Case 100: */
        val = x * 13;
        goto done;
        
    loc_B: /* Case 102: */
        val = x + 10;
        goto done;
        
    loc_C: /* Case 103: */
        val = x + 11;
        goto done;

    loc_D: /* Case 104, 106: */
        val = x * x;
        goto done;
        
    loc_def: /* default: */
        val = 0;

    done:
        *dest = val;
}

 

원본 코드는 case 값으로 100, 102~104, 106을 가지지만, Switch문의 변수인 n은 임의의 정수가 될 수 있습니다.

 

컴파일러는 먼저 n에서 100을 빼서 범위를 0에서 6사이로 만들어서 C 버전 코드에서 index라고 하는 새로운 프로그램 변수를 생성하였습니다.

 

2의 보수로 표현된 음수를 비부호형 표시로 대응시키면 큰 양수 값이 된다는 사실을 이용하여 index를 비부호형 값으로 취급해서 분기 가능성을 단순화시켰습니다.

 

따라서 index 값이 0~6 범위를 벗어나는지에 대한 판단을, 6보다 큰지에 대해 판단하는 방식으로 수행한 것입니다.

관련한 내용은 해당 글 의 `빠른 경계 검사 방법`을 확인해주세용 :)

 

 

 

 

 

 

레지스터는 다음과 같이 할당됩니다.

%rdi - x

%rsi - n

%rdx - dest

switch_eg:

    subq $100, %rsi              # n = n - 100
    
    cmpq $6, %rsi                # n과 6 비교
    
    ja .L8                       # 만약 n이 6보다 큰 경우 L8 (log_def로 이동)
    
    jmp *.L4(, %rsi, 8)          # 간접 점프 사용 (n * 8 + L4)로 이동
    
 .L3:                            # loc_A - Case 100
    leaq (%rdi, %rdi, 2), %rax   # result = x + 2x 
    leaq (%rdi, %rax, 4), %rdi   # x = 4 * result  + x ( == 13x)
    jmp .L2                      # goto done
    
 .L5:                            # loc_B - Case 102
     addq $10, %rdi              # x = x + 10
     
 .L6:                            # loc_C - Case 103
     addq $11, %rdi              # val = x + 11
     
 .L7:                            # loc_D - Case 104, 106
     imulq %rdi, %rdi            # val = x * x
     jmp .L2                     # goto done
     
 .L8:                            # loc_def - default
     movl $0, %edi               # val = 0
     
 .L2:                            # done
    movq %rdi, (%rdx)            # *dest = val 
    ret
    
    
    .setcion     .rodata
    .align 8                     # Align address to multiple of 8

 .L4:   # Jump Table
     .quad .L3                   # Case 100 : loc_A
     .quad .L8                   # Case 101 : loc_def
     .quad .L5                   # Case 102 : loc_B
     .quad .L6                   # Case 103 : loc_C
     .quad .L7                   # Case 104 : loc_D
     .quad .L8                   # Case 105 : loc_def
     .quad .L7                   # Case 106 : loc_D

 

 

 

 

 

 

 

 

 

 

⭐️ 점프 테이블 구조

 

 

 

 

 

아래와 같은 점프 테이블을 예시로 살펴보겠습니다.

점프 테이블의 각 타겟은 주소이므로 타겟별로 8바이트의 공간이 필요합니다.

또한 점프 테이블의 시작주소는 .L4 입니다.

 

 

점프하기 위해서는 직접점프 혹은 간접점프를 사용하실 수 있습니다.

직접점프 : jmp .L8

점프 대상은 레이블이며, .L8 로 표시됩니다.

간접점프 : jmp *.L4(, %rdi, 8)

점프 테이블의 시작 : .L4
주소이므로 8의 배수로 증가해야 합니다.
점프 타겟은 유효주소 .L4 + x * 8 로부터 얻어집니다. ( $0 \leq x leq 6$ 에 대해서만 성립합니다. )