public string DevelopmentDiary(Knowledge knowledge) {
if (knowledge != null) {
return "level up"
} else {
return "level down"
}
}컴퓨터 과학
Bryant, R. E., & O’Hallaron, D. R. (2023). Computer systems: A programmer’s perspective (3rd ed.). Pearson.
3.2 프로그램의 인코딩
최적화 수준을 올리면 최종 프로그램은 더욱 빨리 동작하게 되지만 컴파일 시간이 증가하고 디버깅 도구를 실행하기가 어려워질 위험이 있다.
=> 컴파일러의 최적화를 의미한다. 컴파일러의 최적화는 소스 코드를 실행 성능이 더 좋고, CPU와 메모리같은 자원을 효율적으로 사용하는 기계어 코드로 변환하도록 하는 것이다.
높은 수준의 최적화를 적용하면 만들어진 코드가 너무 많이 변경된다.
3.2.1 기계 수준 코드
기계 수준 프로그래밍에서 중요한 부분
- 기계수준 프로그램의 형식과 동작은 *인스트럭션 집합구조(ISA)에 의해 정의된다. ISA는 프로세서의 상태, 인스트럭션의 형식, 프로세서 상태에 대한 각 인스트럭션들의 영향들을 정의한다.
- 프로세서의 상태: CPU(레지스터, 프로그램 카운터, *플래그)가 특정 시점에 가지고 있는 정보
- 인스트럭션의 형식: 명령어(연산코드, 피연산자)가 어떤 구조(비트, 역할)로 이루어져 있는지
- 프로세서 상태에 대한 각 인스트럭션들의 영향: 명령어로 프로세서 상태가 어떻게 변화하는지
* ISA - 프로세서와 소프트웨어간 인터페이스를 정의하는 추상적인 명세.
하드웨어와 소프트웨어가 상호작용하는 방식 규정 (프로세서와 소프트웨어 간의 약속, 동작의 기본 틀을 제공함.)
* 플래그
- ZF: 0으로 만듦
- SF: 음수인지 확인함.
- OF: 오버플로우 플래그-
ISA의 종류
-
RISC (Reduced) - 단순, 간단
=> 컴퓨터의 성능이 뛰어나지 않았을 때 주로 사용, 레지스터의 역할이 구체적이고 명확해서 값을 레지스터에게 전달하면 레지스터 값을 보고 CPU가 처리함. -
CISC (Complex) - 복잡한 명령어 구조 (ex. x86-64)
=> 세부적으로 처리할 수 있음. 최적화가 잘 되어 메모리 낭비가 없음. 역어셈블 시 디버깅 편함. 고급 언어와 호환성이 좋다. 명령어 속도가 느림.
-
2. 기계수준 프로그램이 사용하는 주소는 가상주소이며 메모리가 매우 큰 바이트 배열인 것처럼 보이게 하는 메모리 모델을 제공한다. (가상메모리)
- 레지스터의 종류
- 프로그램 카운터: 실행할 다음 인스트럭션의 메모리 주소를 가리킴
- 정수 레지스터 파일: 주소나 정수 데이터를 저장
- 조건코드 레지스터: 가장 최근에 실행한 산술 또는 논리 인스트럭션에 관한 상태 정보를 저장(if, while 문)
- 벡터 레지스터의 집합: 하나 이상의 정수나 부동소수점 값들을 각각 저장
- 스택 관련 레지스터: 2개 존재하며 시작점과 끝점의 주소를 가리킴
- 세그먼트 레지스터: 시작점과 끝점을 가리킴 (프로세스를 잘라서 세그먼트 단위를 나타냄)
운영체제는 가상주소를 실제 프로세서 메모리 상의 물리적 주소 값으로 번역해준다.
- 하나의 기계어 인스트럭션이 수행하는 기초적인 동작
- 레지스터들에 저장된 두 개의 수 더하기
- 메모리와 레지스터 간에 데이터 교환
- 새로운 인스트럭션 주소로 조건에 따라 분기
- 가상메모리
- 물리주소를 쓰지 않는다. (프로세스 간 주소 충돌 발생할 확률 증가)
- 가상화 및 논리주소를 활용한다.
- 페이지, 세그먼트 (물리 주소를 논리 주소로 변환)
- 페이지는 크기를 고정함. 전체 코드(프로그램)에서 사용할 코드(부분)을 잘라서 램으로 보낸 것이 프로세스임.
- 프로세스의 크기에 따라 단편화가 생기기도 함.
- 세그먼트
- 페이지 테이블 (논리 주소를 넣으면 물리 주소의 시작점이 나옴)
- 페이지 폴트
- 논리 주소를 따라갔더니 물리 주소에 해당하는 프로세스가 없음
- 운영체제가 페이지 테이블의 인덱스를 따라갔더니 해당하는 코드가 없음.
- 페이지 스케일링
3.2.2 예제
-
명령어: CPU가 실행할 작업을 지시하는 코드. 일반적으로 두 부분으로 구성됨.
- 연산 코드: 어떤 작업을 수행할지 정의함(ADD, SUB, LOAD)
- 오퍼랜드: 작업에 필요한 데이터나 데이터의 위치를 지정함. (ADD R1, R2에서 R1, R2는 오퍼랜드)
-
인스트럭션 인코딩
movl %eax, %ebx =(encoding)=> 89 C3인스트럭션 인코딩은 자주 사용되는 인스트럭션들과 오퍼랜드가 적은 것들이 짧은 길이를 갖도록 함.
인스트럭션의 형식은 바이트들을 기계어 인스트럭션으로 유일하게 디코딩할 수 있도록 설계함.
(ex. pushq %rbx 인스트럭션만이 바이트 값 53으로 시작될 수 있음)
CPU는 데이터를 캐시 라인 단위로 가져온다. 코드블록이 정렬되면 캐시라인에 딱 맞아떨어져 한 번의 접근으로 더 많은 데이터를 가져올 수 있다.
데이터 캐시에는 패딩을 추가해서 캐시 정렬을 하고
명령어 캐시에는 nop을 저장해서 캐시 정렬을 한다.
캐시는 주소를 16, 32, 64바이트 단위로 관리하는데 만약 정렬되지 않은 데이터가 두 주소에 걸쳐 있다면 두 번 접근할 필요가 생긴다.
- 정렬되지 않은 경우(데이터 캐시)
| 캐시 주소 | '0x10' | 0x11 | ... | 0x1D | 0x1E | 0x1F | '0x20' | 0x21 | ... |
|---|---|---|---|---|---|---|---|---|---|
| 데이터 | 불필요 | 불필요 | ... | 불필요 | 필요 | 필요 | 필요 | 필요 | ... |
- 정렬되지 않은 경우(명령어 캐시)
| 캐시 주소 | '0x10' | 0x11 | ... | 0x1D | 0x1E | 0x1F | '0x20' | 0x21 | ... |
|---|---|---|---|---|---|---|---|---|---|
| 명령어 | 불필요 | 불필요 | ... | MOV EAX, 1 | CALL func | ... | ... | ... | ... |
이 경우 0x20뿐만 아니라 0x1E, 0x1F를 탐색하기 위해 0x10에도 접근해야 함.
- 정렬된 경우(데이터 캐시)
| 캐시 주소 | '0x10' | 0x11 | ... | 0x1D | 0x1E | 0x1F | '0x20' | 0x21 | ... |
|---|---|---|---|---|---|---|---|---|---|
| 데이터 | 불필요 | 불필요 | ... | 패딩 | 패딩 | 패딩 | 필요 | 필요 | ... |
- 정렬된 경우(명령어 캐시)
| 캐시 주소 | '0x10' | 0x11 | ... | 0x1C | 0x1D | 0x1E | 0x1F | '0x20' | 0x21 | ... |
|---|---|---|---|---|---|---|---|---|---|---|
| 명령어 | 불필요 | 불필요 | ... | NOP | NOP | NOP | NOP | CALL func | ... | ... |
이 경우 0x1F에 해당하는 캐시라인 탐색할 필요없이 0x20에 접근하면 됨.
3.3 데이터 형식
인텔 프로세서는 근본적으로 16비트 구조를 사용했기 때문에 '워드'는 16비트 데이터 타입을 말할 때 사용한다.
3.4 정보 접근하기
64비트 연산은 레지스터 전체에, 32비트 연산은 덜 중요한 4바이트에, 16비트 연산은 가장 덜 중요한 2바이트에 접근한다.
ex)
| 63 | 62 | ... | 31 | ... | 15 | ... | 7 | ... | 0 |
|---|---|---|---|---|---|---|---|---|---|
| %rax | %rax | ... | %eax | ... | %ax | ... | %al | ... | %al |
64비트의 rax레지스터를 예로 들면, eax, ax, al등 작은 부분으로 나뉘고, 연산의 크기에 맞게 할당된다.
8바이트보다 작은 바이트를 생성하는 인스트럭션들이 레지스터에서 남는 바이트를 처리하는 방법
- 1 또는 2바이트를 생성하는 경우에는 나머지 바이트들은 변경 없이 그대로 유지함.
(데이터를 보존하거나 특정 상황에서 성능을 최적화하는데 유용하다.) - 4바이트 길이의 값을 생성하는 경우는 상위 4바이트를 0으로 설정함.
(데이터 일관성을 유지하고 이전 값이 남는 것을 방지한다.)
%rax: 함수 반환값 저장
%rdi, rds, rdx, rcx: 함수 인자(파라미터) 저장
%rsp: 스택(top)
%rbp: 베이스
3.4.1 오퍼랜드 식별자
오퍼랜드: 연산을 수행할 소스 값과 그 결과를 저장할 목적지의 위치를 명시함.
- immediate: 상수값을 말함.
- register: 각각 16개의 64비트, 32비트, 16비트, 8비트 레지스터들의 하위 일부분인 8, 4, 2, 1바이트 중 하나의 레지스터를 가리킴.
- 메모리 참조: 유효 주소(effective address)라고 부르는 계산된 주소에 의해 메모리 위치에 접근함.
** 유효주소: CPU가 메모리에서 데이터를 읽거나 사용하는 최종적인 메모리 주소
3.4.2 데이터 이동 인스트럭션
오퍼랜드
- 소스 오퍼랜드: 상수, 레지스터 저장 값, 메모리 저장 값을 표시함.
- 목적 오퍼랜드: 레지스터 또는 메모리 주소의 위치를 지정함.
메모리 주소 지정 방식
-
(movq $10 %rax)
즉시 주소 지정($10): 상수값은 바이트로 표현할 수 있음 -
(movq 0xFAFF0000 %rax)
직접 주소 지정(0xFAFF0000) -
간접 주소 지정
- mov %rax, %rbx
레지스터 직접 주소 지정(%rax, %rbx) - mov (%rax)
레지스터 간접 주소 지정(메인 메모리 주소) - offset(%bp), %rax
베이스 레지스터 간접 주소 지정 - 데이터의 크기를 저장할 때 - mov ARRAY(%rdx), %rax
인덱스 레지스터 간접 주소 지정 - 시작점을 인덱스 - (rax, rdx)
베이스 인덱스 레지스터 간접 주소 지정 rax주소에 rdx더한 만큼 넘어감
- mov %rax, %rbx
데이터 이동 인스트럭션
(두 개의 오퍼랜드가 메모리 위치에 올 수 없도록 제한함)
-하나의 메모리 위치에서 다른 위치로 어떤 값을 복사하기 위해서는 두 개의 인스트럭션이 필요함.
첫 번째 - 소스 값을 레지스터에 적재하는 인스트럭션
두 번째 - 이 레지스터의 값을 목적지에 쓰기 위한 인스트럭션
-
MOV 클래스: 소스 위치에서 데이터를 목적지 위치로 어떤 변환도 하지 않고 복사한다.
(소스 오퍼랜드(S) 다음에 목적 오퍼랜드(D)가 나옴, b, w, l, q에 유의)Instruction Effect Description MOV S, D D ← S Move movb Move byte movw Move word movl Move double word movq Move quad word movabsq I, R R ← I Move absolute quad word - 대부분의 경우 MOV 인스트럭션들은 특정 레지스터 바이트들이나 대상 오퍼랜드에 의해 지정된 메모리 위치만을 업데이트하지만 movl이 레지스터를 목적지로 갖는 경우, 레지스터의 상위 4바이트도 0으로 설정함.
- movq 인스트럭션은 32비트 2의 보수 숫자로 나타낼 수 있는 상수 소스 오퍼랜드들만을 가짐.
상수 소스 오퍼랜드: 명령어에 직접 포함된 값(즉시값, 리터럴값)
ex) movq $0x12345678, %rax 의 $0x12345678, CPU가 명령어를 처리할 때 즉시값을 포함하려면 해당값을 명령어 자체에 저장해야함. 따라서 CPU 설계상 최대 32비트까지 가능
- 대부분의 경우 MOV 인스트럭션들은 특정 레지스터 바이트들이나 대상 오퍼랜드에 의해 지정된 메모리 위치만을 업데이트하지만 movl이 레지스터를 목적지로 갖는 경우, 레지스터의 상위 4바이트도 0으로 설정함.
-
MOVZ 클래스: 목적지의 남은 바이트들을 모두 0으로 채워준다.
Instruction Effect Description MOVZ S, R R ← ZeroExtends Move with zero extension movzbw Move zero-extended byte to word movzbl Move zero-extended byte to double word movzwl Move zero-extended word to double word movzbq Move zero-extended byte to quad word movzwq Move zero-extended word to quad word ** double word to quad word: movl 인스트럭션을 이용해서 구현할 수 있음 (상위 4바이트를 0으로 채움)
-
MOVS 클래스: 소스 오퍼랜드의 가장 중요한 비트를 반복해서 복사하는 부호 확장으로 채운다.
Instruction Effect Description MOVZ S, R R ← ZeroExtends Move with sign extension movsbw Move sign-extended byte to word movsbl Move sign-extended byte to double word movswl Move sign-extended word to double word movsbq Move sign-extended byte to quad word movswq Move sign-extended word to quad word movslq Move sign-extended double word to quad word cltq %rax ← SignExtend(%eax) Sign-extend %eax to %rax
3.4.3 데이터 이동 예제
(a)C code
long exchange(long *xp, long y)
{
(x를 메모리에서 읽어서 레지스터 %rax에 저장함)
long x = *xp;
(y를 레지스터 %rdi에 저장된 테로 지정한 메모리 위치에 써줌)
*xp = y;
(%rax를 리턴함)
return x;
}(b) Assembly code
(프로시저 매개변수 xp와 y는 레지스터 %rdi와 %rsi에 저장됨)
exchange:
(x를 메모리에서 읽어서 레지스터 %rax에 저장함)
movq (%rdi) , %rax
(y를 레지스터 %rdi에 저장된 테로 지정한 메모리 위치에 써줌)
movq %rsi, (%rdi)
(%rax를 리턴함)
ret- C언어에서 포인터라고 부르는 것이 어셈블리어에서는 단순히 주소임
(포인터를 역참조하는 것은 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 과정으로 이루어짐) - x 같은 지역변수들은 메모리에 저장되기보다는 종종 레지스터에 저장됨
(레지스터의 접근은 메모리보다 속도가 훨씬 더 빠름)
3.4.4 스택 데이터의 저장과 추출 (push, pop)
프로그램 스택은 메모리의 특정 영역에 위치한다. 스택의 탑(top) 원소가 모득 스택 원소 중에서 가장 낮은 주소를 갖는 형태로, 스택은 아래 방향으로 성장한다.
-스택은 아래쪽으로 성장하고 힙은 위쪽으로 성장하며 둘 사이에는 빈 공간이 존재함.
따라서 특정 값을 스택에 추가시키기 위해서는 스택 탑의 주소를 감소시킨 뒤 데이터를 추가(push)하고 스택에서 데이터를 읽어내고(pop) 스택 탑의 주소를 증가시킨다. 스택의 주소만 증가시키기 때문에 데이터는 메모리 주소에 여전히 남아있다.
Initially
| register | Effect |
|---|---|
| %rax | 0x123 |
| %rdx | 0 |
| %rap | 0x108 |
| Stack |
|---|
| (1) - (bottom) |
| (2) |
| (3) |
| (4) |
| (5) |
| (6) - (0x108 (top)) |
pushq %rax (스택 포인터를 8 감소시켜 스택 탑을 갱신하고 새로운 데이터를 저장한다.)
| register | Effect |
|---|---|
| %rax | 0x123 |
| %rdx | 0 |
| %rap | 0x100 |
| Stack |
|---|
| (1) - (bottom) |
| (2) |
| (3) |
| (4) |
| (5) |
| (6) |
| 0x123 - (0x100 (top)) |
popq %rax (값 0x123을 메모리에서 읽어서 레지스터 %rdx에 기록함)
| register | Effect |
|---|---|
| %rax | 0x123 |
| %rdx | 0x123 |
| %rap | 0x108 |
| Stack |
|---|
| (1) - bottom |
| (2) |
| (3) |
| (4) |
| (5) |
| (6) - (0x108 (top)) |
| 0x123 |
3.5 산술연산과 논리연산
| Instruction | Effect | Description |
|---|---|---|
| 첫 번째 그룹 | ||
| leaq S, D | D ← &S | Load effective address |
| 두 번째 그룹 | ||
| INC D | D ← D + 1 | Increment |
| DEC D | D ← D - 1 | Decrement |
| NEG D | D ← -D | Negate |
| NOT D | D ← ~D | Complement |
| 세 번째 그룹 | ||
| ADD S, D | D ← D + S | Add |
| SUB S, D | D ← D - S | Subtract |
| IMUL S, D | D ← D * S | Multiply |
| XOR S, D | D ← D ^ S | Exclusive-or |
| OR S, D | D ← D | S | Or |
| AND S, D | D ← D & S | And |
| 네 번째 그룹 | ||
| SAL k, D | D ← D << k | Left shift |
| SHL k, D | D ← D << k | Left shift (same as SAL) |
| SAR k, D | D ← D >> Ak | Arithmetic right shift |
| SHR k, D | D ← D >> Lk | Logical right shift |
3.5.1 유효주소 적재
leaq: movq 인스트럭션의 변형으로 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않음. (유효주소를 목적지에 복사함)
leaq offset(base, inde, scale) = offset + base + index * scale
3.5.2 단항 및 이항 연산
두 번째 그룹에서의 연산은 하나의 오퍼랜드가 소스와 목적지로 동시에 사용되는 단항 연산임.
세 번째 그룹은 이항 연산으로 구성되며 두 번째 오퍼랜드는 소스이면서 목적지로 사용됨.
(두 번째 오퍼랜드가 메모리 위치이면 프로세서가 메모리에서 값을 읽고 연산을 하고 다시 결과를 메모리에 쓴다.)
3.5.3 쉬프트 연산
네 번째 그룹은 쉬프트 연산으로 쉬프트 하는 크기를 먼저 주고, 쉬프트할 값을 두 번째로 준다.
쉬프트할 값은 즉시 값이나 단일 바이트 레지스터 %cl로 명시할 수 있다.
w비트 길이의 데이터 값에 적용하는 쉬프트 연산은 레지스터 %cl의 하위 m비트로 쉬프트 양을 결정한다.
-
초기 상태
%cl = 0x23 (10진수로 35)Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0 0 0 1 0 0 0 1 1 -
하위 m비트 추출
데이터가 32비트이므로 m = log232 = 5
마스크 값 0x1F
계산: %cl & 0x1F
하위 m비트 값: 00011 (3) -
실제 쉬프트 횟수
쉬프트 횟수는 하위 m비트 값으로 제한됨. -
쉬프트 연산 결과
데이터:%rax = 0x12345678
| Bit 31 | Bit 30 | Bit 29 | Bit 28 | Bit 27 | Bit 26 | Bit 25 | Bit 24 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| Bit 23 | Bit 22 | Bit 21 | Bit 20 | Bit 19 | Bit 18 | Bit 17 | Bit 16 |
|---|
...
<물어보기>
3.5.4 토의
우측 쉬프트만이 부호형과 비부호형 데이터를 구분하는 인스트럭션을 요구한다.
어셈블리 코드들의 인스트럭션은 C소스코드의 줄번호와 밀접하게 대응된다.
3.5.5 특수 산술 연산
64비트 정수들 간 곱셈은 결과 값을 표시하기 위해 128비트를 필요로 함.
두 개의 단일 오퍼랜드인 경우 한 개의 인자는 %rax에 보관하고 다른 하나는 인스트럭션 소스 오퍼랜드로 주어짐. R:R을 하나의 오퍼랜드로 봄
결과 값에 저장할 때는 2개의 레지스터를 활용하며. %rdx에 상위 64비트, %rax에 하위 64비트를 저장함.
따라서 두 개의 movq 인스트럭션이 필요
| Instruction | Effect | Description |
|---|---|---|
| imulq S | R[%rdx]:R[%rax] ← S * R[%rax] | Signed full multiply |
| mulq S | R[%rdx]:R[%rax] ← S * R[%rax] | Unsigned full multiply |
| cqto | R[%rdx]:R[%rax] ← SignExtend(R[%rax]) | Convert to oct word |
| idivq S | R[%rdx] ← R[%rdx]:R[%rax] mod S; R[%rax] ← R[%rdx]:R[%rax] / S; | Signed divide |
| divq S | R[%rdx] ← R[%rdx]:R[%rax] mod S; R[%rax] ← R[%rdx]:R[%rax] / S; | Unsigned divide |
cqto: 부호가 있는 변수에서 활용
3.6 제어문
C와 기계어 코드의 인스트럭션들은 순차적으로 실행된다. 실행 순서는 Jump 인스트럭션으로 변경할 수 있으며, 결과에 따라 프로그램의 다른 일부분으로 제어를 넘겨준다.
3.6.1 조건 코드
CPU는 가장 최근 산술 또는 논리연산의 특성을 설명하는 단일 비트 조건 코드로 구성된 레지스터를 운영한다.
- CF(캐리 플래그): 가장 최근의 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시. 비부호형 연산에서 오버플로우를 검출할 때 사용
- ZF(영 플래그): 가장 최근 연산의 결과가 0인 것을 표시
- SF(부호 플래그): 가장 최근 연산이 음수를 생성한 것을 표시
- OF(오버플로우 플래그): 가장 최근 연산이 양수/음수의 2의 보수 오버플로우를 발생시킨 것을 표시
인스트럭션들에 의해 조건 코드 값이 변경될 뿐만 아니라 다른 레지스터들을 변경시키지 않으면서 조건 코드만 변경해주는 두 개의 인스트럭션 클래스
| Instruction | Based on | Description |
|---|---|---|
| CMP S1, S2 | S2 - S1 | Compare |
| cpmb | Compare byte | |
| cpmw | Compare word | |
| cpml | Compare double word | |
| cpmq | Compare quad word | |
| TEST S1, S2 | S2 & S1 | Test |
| testb | Test byte | |
| testw | Test word | |
| testl | Test double word | |
| testq | Test quad word |
CMP 인스트럭션: 두 오퍼랜드의 차에 따라 조건 코드를 설정함. 목적지를 갱신하지 않고 조건 코드를 설정한다는 점을 제외하면 SUB 인스트럭션과 똑같은 방법으로 동작함.
TEST 인스트럭션: 목적지 오퍼랜드를 변경하지 않으면서 조건 코드를 설정하는 점만 제외하면 AND 인스트럭션과 같은 방식으로 동작함.
3.6.2 조건 코드 사용하기
조건 코드를 직접 읽는 것 외의 조건 코드를 이용하는 보편적인 세 가지 방법
- 조건 코드의 조합에 따라 0 또는 1을 한 개의 바이트에 기록함.
- 조건에 따라 프로그램의 다른 부분으로 이동함.
- 조건에 따라 데이터를 전송함.
(1) SET 인스트럭션: 조건 코드의 조합에 따라 0 또는 1을 한 개의 바이트에 기록하는 인스트럭션
(!) set 인스트럭션의 접미어는 오퍼랜드의 크기가 아닌 어떤 조합을 사용할 것인지에 관해 나타낸다.
- 오버플로우가 발생하지 않은 경우
- t = a - b < 0일 때 SF비트가 1이면 a < b
- t = a - b > 0일 때 SF비트가 0이면 a > b
- 오버플로우가 발생한 경우
- a - b > 0 (음의 오버플로우) 일 때 a < b => OF = 1, SF = 0
- a - b < 0 (양의 오버플로우) 일 때 a > b => OF = 1, SF = 1
오버플로우와 부호비트의 XOR 값은 a < b 여부를 테스트할 수 있는 방법이 됨.
비부호형의 비교 - 캐리와 영 플래그의 조합을 사용한다.
3.6.3 점프 인스트럭션
일반적인 경우 인스트럭션들은 나열된 순서에 따라 순차적으로 실행됨.
점프 인스트럭션은 프로그램이 완전히 새로운 위치로 실행을 전환하도록 함.
목적 코드파일을 만들기 위해 어셈블러는 모든 레이블이 붙은 인스트럭션들의 주소를 결정하고 점프 인스트럭션의 일부분인 점프 목적지를 인코딩한다.
점프의 종류
- 직접 점프: 점프 목적지가 인스트럭션의 일부로 인코딩되는 경우. 점프 대상을 레이블로 프로그램 내에 작성한다. (ex. jmp *%rax)
- 간접 점프: 점프 대상을 레지스터나 메모리 위치로부터 읽어들여야 하는 경우. '*'와 메모리 오퍼랜드 중의 하나를 이용한 오퍼랜드 식별자를 합쳐서 작성한다. (ex. jmp *(%rax))
3.6.4 점프 인스트럭션 인코딩
점프를 인코딩하는 방법
- PC 상대적 방법: 대상 인스트럭션과 점프 인스트럭션 바로 다음에 오는 인스트럭션 주소와의 차이를 인코딩함. 이들 오프셋은 1, 2 또는 4바이트로 인코딩 될 수 있음. (점프 인스트럭션 자신의 주소가 아님)
- 절대 주소 제공: 대상을 직접 명시하기 위해 4바이트를 사용함.
3.6.6 조건부 이동으로 조건부 분기 구현하기
프로세서는 각 인스트럭션을 일련의 단계로 처리하며 각각 요구된 동작의 작은 부분만을 실행하는 파이프라인을 통해 높은 성능을 얻는다. 파이프라인을 실행할 인스트럭션들로 미리 채우기 위해 실행할 인스트럭션들의 순서를 훨씬 일찍 결정할 수 있어야 한다.
조건부 인스트럭션(cmove, cmovne, ...)이 다른 길이를 갖는 데이터에도 똑같이 작용할 수 있는 이유 - 목적지 레지스터의 이름으로부터 조건부 이동 인스트럭션의 오퍼랜드 길이를 추정함.
복잡한 분기예측 회로 채택
- 안정적으로 예측한다면 인스트럭션 파이프 라인은 인스트럭션들로 가득 채워진다.
- 점프 하나를 잘못 예측하면 이미 실행한 작업 결과들을 상당 부분 버려야하고 다시 인스트럭션들을 파이프라인에 채워야 한다.
분기 예측: 모든 인스트럭션을 파이프 라이닝
- 단순하게 올리고 예측함.
- 분기 예측을 하는 방법 이전 분기 결과를 참고함, 이전 분기가 실패했으면 올리지 않고 이전 분기가 성공했으면 올림.
- 연속으로 2번 성공했는지 실패했는지 봄. (상태 머신 참고)
조건부 동작을 구현하는 방법
1) 제어의 조건부 전환 (if - else)
- 프로그램의 한 가지 실행경로를 따르고 아닌 경우에는 다른 경로를 따라가도록 함.
- 프로그램의 실행 흐름을 변경함
- 특정 조건이 참일 때, 다른 코드로 점프하거나 분기함.
2) 조건부 데이터 이동 (test-expr ? then-expr : else-expr)
- 조건부 동작의 산출물 모두를 계산하고 조건에 따라 하나만 선택하는 방식
- 프로그램의 실행 흐름은 그대로 유지함.
- 특정 조건에 따라 데이터를 이동하거나 처리함.
- 계산이 간단할 경우 성능 향상에 도움됨.
(이 경우 데이터를 모두 할당하기 때문에 변수에 Null이 있을 경우 Null 역참조 에러가 발생할 수 있다.)
3.6.7 반복문
기계어는 여기에 대응되는 인스트럭션이 없다. 대신 조건부 테스트와 점프를 함께 사용해 반복문을 구현한다.
Do-While
최초로 실행되는 while문 이후 while문의 마지막에서 조건을 판단하여 loop로 goto한다.
While
test-expr를 먼저 계산해서 while문에 진입하기 전 종료될 수 있다.
For
for문은 while문과 유사하다. 따라서 while 루프를 사용하되 do while을 위한 두 개의 번역전략 중 하나를 따른다.
for (init-expr; test-expr; update-expr)
body-statement
init-expr;
while (test-expr) {
body-statement
update-expr;
}참고로 두 가지 번역 전략은 다음과 같다.
1.
init-expr;
goto test;
loop:
body-statement;
update-expr;
test:
t = test-expr;
if (t)
goto loop; init-expr;
if (!t)
goto done;
loop:
body-statement
update-expr;
t = test-expr;
if (t)
goto loop;
done:Switch
점프 테이블이라는 자료구조를 사용해서 효율적인 구현을 가능하게 한다.
점프 테이블: 원소 i가 switch문의 인덱스와 같을 때 프로그램이 실행해야 하는 동작을 구현하는 코드 블록의 주소가 되는 배열
GCC는 case 값의 밀집도와 case의 수를 고려해서 switch문의 번역 방법을 선택함.
여러 개의 case가 있고 값들이 작은 범위에 분포할 때 점프 테이블이 사용된다.
컴파일러는 case 옆의 숫자에 적절한 수를 빼서 0부터 시작하는 부호없는 정수 인덱스를 새로 생성한다.
ex)
switch (n) {
case 100:
~~
case 102:
~~
}컴파일러 수정
static void *jt[n] = {
&&loc_A, &&loc_def, &&loc_B, ...
}
unsigned long index = n - 100;
if (index > 6)
goto loc_def;
goto *ft[index];그렇다면 문자열은 어떻게 사용할까?
- 해시 함수 사용 - 문자열을 해시 함수로 처리하여 고유한 정수 값을 생성하고 이를 점프 테이블의 인덱스로 사용
- 검색 및 매핑 - 문자열을 사전에 저장하고 이를 기반으로 적절한 인덱스를 찾아 점프 테이블에 접근
- 문자열 비교 - 문자열을 직접 비교하여 특정 조건에 따라 점프테이블 항목 선택
3.7 프로시저
지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공한다.
프로시저에 대한 기계어수준 지원을 제공해야할 때 처리되어야 하는 특성
(프로시저 P에서 프로시저 Q를 호출하고 Q가 실행한 후에 다시 P로 리턴할 때)
- 제어권 전달: 프로그램 카운터는 진입할 때 Q에 대한 코드의 시작주소로 설정되고, 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 함.
- 데이터 전달: P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하며, Q는 다시 P로 하나의 값을 리턴할 수 있어야 함.
- 메모리 할당과 반납: Q는 시작할 때 지역변수들을 위한 공간을 할당할 수도 있고 리턴할 때 이 저장소를 반납할 수 있음.
3.7.1 런타임 스택
대부분의 언어에서는 프로시저 호출 동장방식을 스택 자료구조의 후입선출 메모리 관리 방식을 활용한다.
Q프로시저는 지역변수를 위한 공간, 다른 프로시저로의 호출을 설정하는 능력이 필요하며 리턴할 때는 할당받은 로컬 저장소를 반납한다.
스택 프레임: 프로시저가 레지스터들에 저장할 수 있는 개수 이상의 저장 공간을 필요로 할 때 할당하는 공간
현재 실행 중인 프로시저에 대한 프레임은 항상 스택의 맨 위에 위치함.
프로시저 P가 프로시저 Q를 호출할 때 리턴 주소를 스택에 푸시함.
리턴 주소는 P에 관계된 상태들을 저장하기 때문에 리턴 주소는 P의 스택 프레임에 속하는 것으로 간주함.
레지스터 값, 지연변수들을 위한 공간을 할당하며 자신이 호출하는 프로시저들을 위한 인자를 설정할 수 있다.
모든 지역변수들을 레지스터에 보관할 수 있고(지역변수가 6개이하) 이 함수가 다른 함수를 호출하지 않을 때, 스택 프레임을 요청하지 않는다. (leaf 프로시저)
3.7.2 제어의 이동
제어를 함수 P에서 Q로 전달하는 것은 단순하게 말하면 프로그램 카운터 PC를 Q를 위한 코드의 시작주소로 설정하는 것과 관련된다.
| Instruction | Description |
|---|---|
| call Label | Procedure call |
| call *Operand | Procedure call |
| ret | Return from call |
call Label: 프로시저 라벨을 호출해서 기록한다. (직접 호출)
call *Operand: 주소를 호출한다. (간접 호출)
//Beginning of function multstore
(400540) push %rbx => 원래 rbx에 있던 값 스택에 백업
(400541) mov %rdx, %rbx
...
//Return from function multstore
retq
...
//Call to multstore from main
(400563) callq 400540 <multstore> => 리턴 주소(400568) 스택에 저장
(400568) mov 0x8(%rsp), %rdx3.7.3 데이터 전송
프로시저 콜은 데이터를 인자로 전달하는 것과 관련되어 있으며, 프로시저에서 리턴하는 것도 어떤 값을 리턴하는 것과 관련되어 있을 수 있다.
프로시저로부터의 데이터 전달은 레지스터를 통해서 일어난다.
x86-64에서는 최대 여섯 개의 정수형 인자가 레지스터로 전달될 수 있다. 데이터 형의 길이에 따라 레지스터 이름을 이용해서 정해진 순서로 이용된다.만약 함수가 여섯 개 이상의 정수형 인자를 가지면 다른 인자들은 스택으로 전달된다.이 때 이 인자들을 위해 충분한 크기의 저장공간을 스택 프레임에 할당한다. (이 때 모든 데이터 길이는 8의 배수로 반올림된다.)
3.7.4 스택에서의 지역저장공간
때로는 지역 데이터가 메모리에 저장되어야 하는 경우가 있다.
- 지역 데이터 모두를 저장하기에는 레지스터의 수가 부족할 때
- 지역변수에 연산자 '&'가 사용되었으며, 이 변수의 주소를 생성해야 할 때
- 일부 지역변수들이 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근될 때
3.7.5 레지스터를 이용하는 지역저장소
프로그램 레지스터들은 모든 프로시저들이 공유하는 단일 자원의 역할을 한다.
하나의 프로시저가 다른 프로시저를 호출할 때, 피호출자는 호출자가 추후 사용할 일부 레지스터의 값을 덮어쓰지 않도록 한다. (호출된 프로시저는 이 값을 전혀 변경하지 않거나 원래의 값을 스택에 push 해두었다 추후 pop 하는 방식을 통해 보존한다.)
스택 포인터 %rsp를 제외한 다른 모든 레지스터들은 호출자-저장 레지스터로 구분되며 이는 함수에 의해 변경될 수 있다는 것을 의미한다.
3.7.6 재귀 프로시저
레지스터와 스택을 사용하는 것에 대해 설명한 내용을 통해 x86-64 프로시저들이 재귀적으로 호출하는 것에 대해 설명할 수 있다. 각 프로시저 콜은 스택 상에 자신만의 사적인 공간을 가지며, 다수의 별도 호출들의 지역변수들은 서로 간섭하지 않는다.
3.8 배열의 할당과 접근
최적화 컴파일러는 배열의 인덱스를 사용할 때 필요한 주소계산을 단순화하는 데 우수한 성능을 보임.
3.8.1 기본 원리
크기가 L인 자료형 T가 있다고 할 때, 시작하는 위치를 xA
T A[N]; 은 다음과 같은 의미를 지닌다.
- 이는 L * N 바이트의 연속적인 공간을 메모리에 할당한다.
- 새로운 식별자 A를 통해서 배열이 시작하는 위치의 포인터(xA)로 사용한다.
- 배열의 각 원소는 0에서 N-1사이의 정수형 인덱스를 사용해서 접근할 수 있다.
- 배열의 원소 i는 주소 xA + L * i에 저장된다.
E[i]를 계산하려고 할 때 다음과 같이 접근할 수 있다.
정수형 데이터 E의 주소는 %rdx에, i는 %rcx에 저장되어 있다. 아래 인스트럭션은 주소 계산 xE + 4i를 수행하고 메모리 위치를 읽어서 그 결과를 레지스터 %eax에 저장한다.
movl (%rdx, %rcx, 4) ,%eax
3.8.2 포인터 연산
p가 자료형 T의 데이터에 대한 포인터이고, p의 값을 xp라고 한다면 수식 p + i는 xp + L * i가 되며 여기서 L은 자료형 T의 크기이다.
어떤 객체를 나타내는 식 Expr에 대해 &Expr은 그 개게의 주소를 주는 포인터이다.
주소를 나타내는 식 AExpr에 대해 *AExpr은 그 주소에 위치한 값을 준다.
따라서 Expr과 *&Expr은 동일하다.
즉, A[i] = *(A + i)와 동일하다.
3.8.3 다중 배열
int A[5][3]은 다음과 같다.
typedef int row3_t[3];
row3_t A[5];
배열의 원소들은 행 우선 순소로 저장된다. 즉, A[0]으로 표시되는 모든 행 0의 원소들 다음에 행 1, A[1]의 원소가 따라오는 방식으로 저장된다.
T D[R][C];
&D[i][j] = xD + L(C * i + j)
3.8.4 고정크기의 배열
3.8.5 가변크기의 배열
3.9 이기종 자료구조
struct, class와 같은 것들이 이기종 자료구조 (다양한 자료형이 공존함)
알고리즘
다이나믹 프로그래밍(동적계획법)
복잡한 문제를 작은 여러 개의 작은 문제로 나누고 해결 결과를 다시 활용하여 복잡한 문제를 해결하는 방법
그리디 알고리즘
현재 상황에서 가장 좋은 것을 선택하는 알고리즘
