Chapter 6 : Machine-Level Programming 2 (Control)

Processor State (x86-64)

실행 중인 프로그램에 대한 정보는 크게 4개로 분리할 수 있습니다.

1. Temporary data(임시 데이터)

%rax, %rbx 등 범용 레지스터에 저장되있습니다.

2. Location of runtime stack (런타임 스택의 포인터 저장)

%rsp 레지스터

3. Location of current code control point (다음 실행할 명령어의 메모리주소를 저장함으로써 현재의 제어위치)

%rip 레지스터 (PC 레지스터)

4. Status of recent tests (조건 분기/이동 에 사용되는 상태값을 저장)

condition code(컨디션 코드) (CF, ZF, SF, OF) 레지스터

Condition Codes : Implicit Setting(암묵적 방법)

x86-64의 condition code 레지스터는 총 4개입니다.

CF(Carry Flag) : 부호 없는 값의 Carry Out발생 여부를 나타냅니다. (unsigned)

ZF(Zero Flag) : 값이 0인지를 나타냅니다.

SF(Sign Flag) : 부호 있는 값의 부호를 나타냅니다. (signed)

OF(Overflow Flag) : 부호 있는 값의 오버플로우 발생 여부를 나타냅니다. (signed)

 

값에 대한 특정 연산을 수행하는 계산 명령어가 실행되고 나면, 그 결과값에 의해 condition code 레지스터들의

값이 자동으로 setting됩니다. 

ex) addq A, B를 실행하여 A + B를 실행합니다.

CF : 덧셈시 MSB로 부터 Carry Out이 발생하면 setting 됩니다.

ZF : A + B = 0이면 setting 됩니다.

SF : A + B의 MSB가 1이면 setting됩니다.

OF : (A>0 && B>0 && A+B<0) 또는 (A<0 && B<0 && A+B >= 0)이면 setting 됩니다.

 

CF는 unsigned의 덧셈시에 오버플로우를 감지하는 수단이되고 OF는 signed의 덧셈시에 오버플로우를 감지하는

수단이 됩니다.

 

Condition Codes : Explicit Setting  명시적 방법 (Compare)

condition code 레지스터들의 값을 직접 조작하기 위한 명령어들도 존재합니다. 

Compare 명령어는 두 값의 대소 비교 결과값에 따라 condition code 레지스터들의 값을 setting합니다.

ex) cmpq B, A은 A - B의 결과에 따라 condition code 레지스터들의 값을 setting합니다.

CF : 뺄셈 시 MSB로의 Borrow가 발생한 경우 setting됩니다. (unsigned)

ZF : A - B = 0 이면 setting 됩니다.

SF : A - B의 MSB가 1이면 setting됩니다. (signed)

OF : (A>0 && B<0 && A-B<0) 또는 (A<0 && B>0 && A-B > 0) 이면 setting됩니다. (signed)

 

Condition Codes : Explicit Setting  명시적 방법 (Test)

두 값의 AND연산 결과값에 따라 condition code 레지스터들의 값을 setting하는 Test 명령어 입니다.

ex) testq B, A는 A & B의 결과에 따라 condition code 레지스터들의 값을 setting 됩니다.

ZF : A & B = 0 이면 setting 됩니다.

SF : A & B의 MSB가 1이면 setting됩니다.

 

Reading Condition Codes

SetX 명령어는 현재 condition code 레지스터들의 값이 어떠하냐에 따라서 달리 동작하는 명령어 입니다.

현재 condition code 레지스터들의 값에 따라 목적지에 해당하는 레지스터 하위 1 byte값을 

0 또는 1로 setting됩니다. (나머지 7 byte는 건드리지 않습니다)

나머지 7 byte의 경우는 movzbl 명령어를 통해 0으로 채워줍니다. 

명령어가 l로 끝나면 32 bit 명령어는 자동으로 상위 32 bit를 0으로 채웁니다.

w로 끝나면 16 bit 명령어

b로 끝나면 8 bit 명령어

movzbl A, B => A를 Zero Extenstion 한 결과를 B에 넣습니다. (32 bit)

mobsbl A, B => A를 Sign Extention한 결과를 B에 넣습니다. (32 bit)

ex)

cmpq 연산을 통해 4개의 condition code의 값은 0 또는 1로 setting됩니다. 

x가 y보다 크면 %al 은 1또는 0이 됩니다. 

cmpq와 setq는 동시에 진행되어야 하므로 중간에 새로운 코드라인이 추가 될 수 없습니다. 

movzbl은 %rax에 %al을 대입합니다. %rax는 8byte이고 %al은 1byte입니다. 

연산 후 남는 7byte는 movzbl을 통해 0으로 채울 수 있습니다.

Conditional Branch (조건 분기)

x86-64에서는 분기(branch)를 위한 명령어로 jX 명령어를 제공합니다. 

여기에는 무조건 분기와 조건 분기가 모두 포함되있습니다. 

조건 분기의 경우 condition code 레지스터들의 값에 따라서 분기 여부를 결정하게 됩니다.

shell에다가 gcc -Og -S -fno-if-conversion control.c를 치면

if와 else문의 분기점에 jump명령어가 있어야하기 때문에 jle 명령어가 나왔습니다.

전체 어셈블러어를 보면 

먼저 cmpq명령어로 x와 y를 비교합ㄴ디ㅏ.

그 다음 jle 명령어로 x와 y가 less or equal인지 확인한 후 true이면 아래의 subq 명령어로 가고

false이면 L2로 jump하여 subq 명령어를 실행합니다.

 

C 언어의 goto문을 이용하면 어셈블리어로 번역되는 유사한 형태로 바꿀 수 있습니다. 

ex)

Conditional Move (조건 이동)

condition code 레지스터들의 값이 특정 조건을 만족할 때만 값을 이동시키는 cmovX 명령어가 존재합니다.

CPU의 명령어 실행 구현 방식 중 하나이 파이프라인 방식은 분기가 많으면 많을 수록 성능이 저하됩니다.

반면에 조건 이동은 분기를 실제로 수행하지 않기 때문에 성능저하를 일으키지 않습니다. 

ex) C언어의 삼항 연산자는 다음과 같은 형태로 번역될 수 있습니다.

빨간색 부분이 cmovX 명령어 역할을 합니다.

 

EX) 실제 C언어의 조건문이 cmovX 명령어로 번역

if 일 때와 else일때 실행할 코드들을 우선적으로 다 처리한후 cmpq 명령어로 x, y값을 비교하는것입니다.

cmpq 명령어를 기점으로 윗부분은 x-y, y-x를 실행합니다. 

따라서 현재 %rax = x-y, %rdx = y-x입니다.

cmpq를 포함해 밑의 부분에서는 x와 y를 비교하고, cmovle 명령어를 이용해 x <= y라면 %rax에 %rdx를 대입하여

return하고, x > y라면 별다른 연산 없이 %rax를 return합니다.

 

Bad Cases for Conditional Move

조건 이동에도 bad case가 존재합니다.

1) Expensive Computations (비용 높은 계산)

거의 모든 조건식에 해당합니다. 분기(branch)를 사용하면 여러 조건 중 일부만 계산할 수 있지만 

이동(move)를 사용하면 일단 모든 조건식에 해당하는 식을 처리하고 그 중 필요한 것만을 return하기 때문입니다.

 

2) Risky Computations (위험한 계산)

p라는 값이 만약 올바른 메모리 주소가 아니라면 *p를 계산하는 순간 에러가 발생하게 됩니다. 

 

3) Computation with side effects (계산 할때 부작용이 발생하는 경우)

move는 if와 else 모두 계산하므로

x*=7을 저장한 레지스터에 x+=3의 결과를 업데이트 하는 문제가 생길 수 있습니다. 

만에 하나 컴파일러가 올바른 판단을 해서 각각의 식의 결과를 다른 레지스터에 저장하면 문제가 없을 수 있습니다.

그러나 이러한 경우 함수가 전역변수를 업데이트 하는 경우에 또다른 문제가 생길 수 있습니다.

 

Do-While 문

do whild 문은 조건 분기를 이용하여 다음과 같은 형태로 번역됩니다.

ex) pcount는 x의 2진수가 1을 몇개 갖는지 세는 함수입니다.

C code

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

 

While 문

while문은 조건 분기를 이용하여 번역할 수 있는 방법이 2가지 있습니다. 

1) Jump-to-middle (조건 Test 부분으로 바로 jump하는 방식)

ex)

 

2) Do-While conversion (do while 문 형태로 고친뒤 이를 다시 번역하는 것입니다.)

ex)

 

for 문

for문은 Do-While 방식으로 번역되는 while문 처럼 번역이 됩니다. 

이때 for문의 경우에는 첫 번째 조건 Test가 불필요하다고 판단되는 경우 삭제될 수 있습니다.

이는 컴파일러의 자체적인 판단에 의한 최적화의 결과입니다.

ex)

 

Switch 문

왼쪽은 일반적인 C언어의 switch문입니다. switch문은 jump table이라는 것을 이용하여 구현됩니다. 

Jump Table은 switch문의 각 case에 해당하는 code block의 시작 주소들을 저장하는 table입니다.

x86-64에서 메모리 주소는 64 bit로 표현되므로 Jump Table의 각 칸은 8 byte입니다. 

먼저 x의 값에 따라 실행해야 하는 code block의 시작 주소를 Jump Table에서 찾고, 그곳으로 jump하여

올바른 code block을 실행하게 되는것입니다.

 

Jump Table은 프로그램 코드와는 다른 메모리 영역에 load됩니다. 구체적으로는 .rodata라는 메모리 영역에

저장되는데, 이곳에는 리터럴 상수나 Jump Table과 같은 읽기 전용(read only)데이터가 저장됩니다.

 

x의 값이 6보다 크면 default case에 해당하는 code block(시작주소:.L8)

으로 jump 합니다.

default case가 아니라면 jump table을 참조하여 실행해야 하는 block의

시작 주소를 찾고, 그곳으로 jump합니다. 

이렇게 jump할 주소를 메모리에서 먼저 찾은 다음 그곳으로 

jump하는 방식을 간접 점프(Indirect Jump)라고 합니다.

반면에 "jmp .L8"과 같이 점프할 주소를 명시적으로 적는 방식을

직접 점프(Direct Jump)하고 합니다. 

 

 

%rdi(=x의 값)에 8을 곱하는 이유는 Jump Table의 각 층이 8byte이기 때문입니다. 

여기서 w가 초기화 되지않는 이유는 컴파일러가 자체적으로 판단하여 최적화를 한 결과입니다.

이는 컴파일러가 자체적으로 판단하여 최적화를 한 결과로, 뒤에서 이해가 됩니다. 

%rdx(=z의 값)을 %rcx에 저장하는 이유도 뒤에서 이해가 됩니다.

각 case가 Jump Table에 어떻게 반영되어 있는지 mapping정보입니다. 

 

각 case에 해당하는 code block의 번역 결과를 살펴볼것입니다. 

x = 1인 경우

 

x = 2 또는 x = 3

case 2에 해당하는 code block에는 break가 없기 때문에 아래로 내려갑니다.

여기서 cqto, idivq라는 생소한 명령어를 볼 수 있습니다.

 

x = 5 또는 x = 6 또는 default