[CS:APP] Chap3 Machine-Level Representation of Programs(2)
3.4 Accessing Information
- 레지스터 구성
- x86-64 CPU는 16개의 일반 목적 레지스터를 포함하며, 각각 64비트 값을 저장한다.
- 레지스터는 정수 데이터와 포인터를 저장하는 데 사용된다.
- 레지스터 이름은 %r로 시작한다.
- 초기 8086 아키텍처 : 8개의 16비트 레지스터(%ax ~ %bp)
- IA32 확장 : 32비트 레지스터(%eax ~ %ebp)
- x86-64 확장 : 기존 레지스터를 64비트로 확장(%rax ~ %rbp), 8개의 새로운 레지스터 추가(%r8 ~ %r15)
- 데이터 크기와 접근
- 레지스터는 바이트 크기(1, 2, 4, 8 바이트)에 따라 다른 데이터 크기로 작업할 수 있다.
- 각 데이터 크기에 따라 레지스터의 하위 비트에 접근한다.(1바이트 : 가장 하위 바이트 / 2바이트 : 가장 하위 2바이트 / 4바이트 : 가장 하위 4바이트 / 8바이트 : 전체 레지스터)
- 상위 비트 처리 규칙
- 1바이트, 2바이트 데이터를 생성하는 명령어는 상위 비트를 변경하지 않는다.
- 4바이트 데이터를 생성하는 명령어는 상위 4바이트를 0으로 설정한다.
- 레지스터
- %rsp(스택 포인터)
- 런타임 스택의 끝 위치를 나타낸다.
- 특정 명령어가 스택 포인터를 읽거나 수정한다.
- 나머지 15개 레지스터
- 더 유연하게 사용 가능하며, 임시 데이터, 함수 인자 전달, 함수 반환값, 로컬 변수 저장에 활용된다.(레지스터마다의 사용 목적이 존재하며, 사용 목적을 반영하여 이름을 지었다.)
- %rsp(스택 포인터)
- 프로그래밍 규약
- 표준 규칙이 레지스터 사용을 관리
- 스택 관리
- 함수 인자 전달
- 함수 반환값 처리
- 로컬 및 임시 데이터 저장
- section 3.7에서 자세히 다룰 예정
- 표준 규칙이 레지스터 사용을 관리
3.4.1 Operand Specifiers
- 피연산자와 명령어의 구성
- 대부분의 명령어는 연산을 수행하기 위한 소스 값(source values)과 결과를 저장할 목적지(destination)를 지정하는 하나 이상의 피연산자(operands)를 포함한다.
-
x86-64 아키텍쳐는 다양한 피연산자 형식을 지원하며, 소스 값은 상수(constants), 레지스터(Registers), 메모리(memory)에서 가져올 수 있다.
-
결과는 레지스터나 메모리에 저장할 수 있다.
- 피연산자의 3가지 유형
- Immediate(즉시 값)
- 상수 값을 나타낸다.
- ATT 형식 어셈블리 코드에서는 $ 기호로 시작하며, 뒤에 C 표기법을 사용한 정수가 온다.(ex. $0x1f, $577)
- 명령어마다 사용할 수 있는 즉시 값의 범위가 다르며, 어셈블러는 값에 가장 적합한 인코딩 방식을 자동으로 선택한다.
- Register(레지스터)
- 레지스터의 내용을 나타낸다.
- x86-64에는 16개의 레지스터가 있으며, 각 레지스터는 64, 32, 16, 8비트의 하위 부분을 갖는다.
- ex. R[ ra ]는 특정 레지스터 a의 값을 나타낸다.
- Memory reference(메모리 참조)
- 메모리 주소를 계산하여 접근한다.
- 메모리는 큰 바이트 배열로 간주되며, 특정 주소의 값을 참조한다.
- 표기법 : Mb[Addr]는 주소 Addr에서 시작하는 b바이트 값을 나타낸다.
- Immediate(즉시 값)
- 메모리 참조와 주소 계산(Effective Address)
- 메모리 참조는 여러가지 주소 지정 방식을 가질 수 있으며, 가장 일반적인 형식은 다음과 같다.
- Imm(rb, ri, s)
- Imm : 즉시 값(offset)
- rb : 기본 레지스터(base register)
- ri : 인덱스 레지스터(index register)
- s : 스케일 팩터(scale factor, 1,2,4,8 중 하나)
- Effective Address(유효 주소) 계산
- Effective Address = Imm + R[ rb ] + R[ ri ] x s
- 주로 배열과 구조체 요소를 참조할 때 사용한다.
//solution
0x100
0xAB
0x108 // 즉시 값($)
0xFF // %rax에 저장된 값을 메모리 주소로 해석, 메모리 위치 0x100에 위치한 값에 접근
0xAB // Address 0x100 + 4 = 0x104
0x11 // 9 + 0x100 + 0x3 = 0x10C 에 저장되어있는 값에 접근
0x13 // 260 > Hex : 0x104 ... 0x104 + 0x1 + 0x3 = 0x108
0xFF // 0xFC + 0x4 = 0xFF
0x11 //0x100 + 4*0x3 = 0x10C
3.4.2 Data Movement Instructions
데이터 이동 명령어는 데이터를 한 위치에서 다른 위치로 복사하는 데 사용되며, x86-64에서 가장 많이 사용되는 명령어 중 하나이다. 단순한 데이터 이동 명령어로 다양한 작업을 수행할 수 있으며, 명령어는 데이터 크기 (1,2,4,8 바이트)에 따라 movb, movw, movl, movq로 구분된다.
- 피연산자(Operand) 특징
- Source Operand : 소스 값은 즉시 값(immediate), 레지스터(register), 메모리(memory)에서 가져올 수 있다.
- Destination Operand : 목적지는 레지스터, 메모리 주소로 설정 가능하다.
- 제약 사항
- 두 피연산자가 모두 메모리 주소일 수 없다.
- 메모리 간 데이터를 복사하려면 중간에 레지스터를 사용해야한다.
- MOV 명령어의 특징
- 데이터 크기와 레지스터 크기 일치
- movb, movw, movl, movq의 데이터 크기와 레지스터 크기가 일치해야한다.
- 예외
- movl 명령어가 4바이트 값을 레지스터에 저장하면 상위 4바이트를 0으로 초기화
- x86-64 아키텍쳐에서 채택된 규칙이다.
- 즉시 값과 메모리 주소 사용
- movabsq 명령어는 64비트 즉시 값을 레지스터에 저장하는데 사용된다.(목적지는 무조건 레지스터)
- 데이터 크기와 레지스터 크기 일치
- 작은 소스 크기에서 큰 목적지로 데이터가 이동하는 경우
- MOVZ class
- zero-extension : 소스 크기보다 큰 목적지 크기를 0으로 채워 확장
- MOVS class
- Sign-extension : 소스 크기보다 큰 목적지 크기를 소스의 MSB로 채워 확장
- 지원 크기 : 1,2바이트 소스를 2,4바이트 목적지로 복사 가능
- MOVZ class
- 4바이트 -> 8바이트
- 4바이트 소스를 8바이트 목적지로 제로 확장하는 명령어는 존재하지 않는다.
- movl 명령어를 사용해 4바이트 값을 레지스터에 저장하면 상위 4바이트가 자동으로 0으로 설정됨을 이용하여 확장 가능
- cltq 명령어
- cltq (Convert Long to Quad)
- 소스 : %eax
- 목적지 : %rax
- 부호 확장을 수행하며, movslq %eax, %rax와 동일한 동작을 하지만 더 간결한 인코딩을 제공한다.
- cltq (Convert Long to Quad)
//solution
movb $0xF, (%ebx)
// %ebs를 주소 레지스터로 사용하면 안된다. 메모리 참조는 64비트 주소 레지스터를 사용해야한다.
movl %rax, (%rsp)
// %r..은 64비트 레지스터이다. movl은 32비트 데이터를 처리함으로 데이터크기와 레지스터 크기가 일치하지 않는다.
movw (%rax),4(%rsp)
// source, Destination 모두 메모리 참조를 할 수 없다.
movb %al,%sl
// 레지스터 sl은 존재하지 않는다.
movq %rax,$0x123
//immdiate value는 destination에 사용할 수 없다.
movl %eax,%rdx
// movld은 32비트 데이터 크기, rdx는 64비트 일치하지 않는다.
movb %si, 8(%rbp)
// 레지스터 %si는 16비트, movb는 8비트 데이터를 처리한다 (일치x)
3.4.3 Data Movement Example
- 프로시저의 시작
- 함수가 실행되면, 매개변수 xp와 y는 각각 레지스터 %rdi와 %rsi에 저장된다.
- 명령어 2 : x = *xp
- 메모리에서 x값을 읽어와 레지스터 %rax에 저장
- x = *xp를 어셈블리에서 직접 구현한 것
- 레지스터 %rax는 이후 반환 값으로 사용된다.
- 명령어 3 : *xp = y
- y값을 레지스터 %rdi가 지정하는 메모리 주소(xp)에 기록
- *xp = y 를 구현한 것
- C언어의 포인터는 단순히 메모리 주소일 뿐이다.
- 포인터 역참조(dereference)는 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 방식으로 수행된다.
- 로컬 변수는 메모리에 저장되지 않고 주로 레지스터에 저장된다.(레지스터 접근 속도가 메모리 접근보다 훨씬 빠르기 때문이다.)
//solution
void decode1(long *xp, long *yp, long *zp){
long x = *xp;
long y = *yp;
long z = *zp;
*yp = x;
*zp = y;
*xp = z;
}
3.4.4 Pushing and Popping Stack Data
- 스택 데이터 이동 연산
- push와 pop 명령어는 프로그램 스택에 데이터를 추가하거나 제거하는데 사용된다.
- 스택(stack)
- 데이터가 추가되거나 제거될 수 있는 자료구조
- LIFO(Last-In, First-Out) 규칙에 따라 작동
- 스택은 배열로 구현될 수 있으며, 배열의 한쪽 끝(스택의 “상단(top)”)에서만 데이터가 삽입/삭제된다.
- x86-64에서의 스택
- x86-64 아키텍쳐에서는 스택이 메모리의 특정 영역에 저장된다.
- 스택의 특징
- 아래 방향으로 확장
- 스택의 상단(top)요소가 가장 낮은 주소를 가진다.
- 관례적으로, 스택 그림은 상단을 아래쪽에 표시된다.
- 스택 포인터(%rsp)
- 스택 최상단 요소의 주소를 저장한다.
- 아래 방향으로 확장
- pushq 명령어
- 데이터를 스택에 push한다.
- pushq %rbp의 동작은 아래 두 명령어와 동일하다.
subq $8, %rsp # 스택 포인터 감소 movq %rbp, (%rsp) # %rbp 값을 스택에 저장- 동작 과정
- 스택 포인터(%rsp)를 8만큼 감소
- 새로운 스택 최상단 주소에 데이터를 기록
- 효율성
- 위 두 명령어는 총 8바이트가 필요하지만 pushq는 단일 명령어로 인코딩되며 1바이트만 필요하다.
- Figure 3.9 예시
- %rsp = 0x108, %rax = 0x123 일 대 pushq %rax 실행
- %rsp를 8 감소 -> 0x100
- 메모리 주소 0x100에 값 0x123 저장
- %rsp = 0x108, %rax = 0x123 일 대 pushq %rax 실행
- popq 명령어
- 데이터를 스택에 pop한다.
- popq %rax의 동작은 아래 두 명령어와 동일하다.
movq (%rsp), %rax # 스택에서 값을 읽어 %rax에 저장 addq $8, %rsp # 스택 포인터 증가- 동작 과정
- 스택 최상단 주소에서 값을 읽어 레지스터에 저장
- 스택 포인터(%rsp)를 8만큼 증가
- Figure 3.9 예시
- pushq 이후에 popq %rdx 실행:
- 메모리 주소 0x100에서 값 0x123을 읽어 %rdx에 저장
- %rsp를 8 증가 -> 0x108
- pushq 이후에 popq %rdx 실행:
- 스택 값 유지 : 값 0x123은 메모리 주소 0x104에 남아 있지만, 스택의 최상단은 항상 %rsp가 가리키는 주소로 간주된다.
- 스택의 메모리 접근
- 스택은 프로그램 코드 및 데이터와 같은 메모리 공간에 포함되어 있다.
- 스택의 임의 위치에 접근 가능하다.
- ex. movq 8(%rsp), %rdx 는 스택의 두 번째 64비트 값을 %rdxㄹ로 복사한다.
3.5 Arithmetic and Logical Operations
대부분의 연산은 명령어 클래스(instruction classes)로 표시되며, 피연산자의 크기에 따라 여러 변형(variants)를 가질 수 있다. (leaq 명령어는 크기 변형 없는 유일한 예외이다.)
연산은 다음 네 가지 그룹으로 나뉜다.
- Load Effective Address(유효 주소 로드)
- Unary(단항 연산)
- Binary(이항 연산)
- Shifts(비트 이동)
3.5.1 Load Effective Address
leaq 명령어는 사실상 movq 명령어의 변형이다. 이 명령어는 메모리에서 레지스터로 데이터를 읽는 형태를 가지고 있지만, 실제로는 메모리를 참조하지 않는다. 첫 번째 피연산자는 메모리 참조처럼 보이지만, 해당 명령어는 메모리를 읽는 대신 유효 주소(effective address)를 계산하여 이를 목적지(destination) 레지스터에 복사한다.
위 그림(Figure 3.10) leaq 연산을 보면, C 언어의 주소 연산자 &S를 사용하여 나타내는 것을 볼 수 있다. 이 명령어는 이후 메모리 참조를 위한 포인터를 생성하는 데 사용될 수 있으며, 일반적인 산술 연산을 간단히 표현하는 데도 사용된다.
예를 들어, 레지스터 %rdx에 값 x가 저장되어 있다고 가정하면,
leaq 7(%rdx, %rdx, 4), %rax
위 명령어는 레지스터 %rax에 5x + 7 값을 설정한다.
컴파일러는 종종 유효 주소 계산과 관련이 없는 상황에서도 leaq명령어를 기발한 방식으로 활용한다.
주의할 점은, 목적 피연산자(destination operand)는 반드시 레지스터여야 한다는 것이다.
leaq example Code
long scale(long x, long y, long z){
long t = x + 4 * y + 12 * z;
return t;
}
; x in %rdi, y in %rsi, z in %rdx
scale :
leaq (%rdi, %rsi, 4), %rax ; x + 4*y
leaq (%rdx, %rdx, 2), %rdx ; z + 2*z = 3*z
leaq (%rax, %rdx, 4), %rax ; (x+4*y) + 4*(3*z) = x+ 4*y + 12*z
ret
3.5.2 Unary and Binary Operations
Unary operations(단항 연산자)
- 단항 연산은 하나의 피연산자가 소스(source)와 대상(destination)을 겸한다. 이 피연산자는 레지스터나 메모리 위치가 될 수 있다. 예를 들어, 명령어 incq (%rsp)는 스택 맨 위에 있는 8바이트 요소를 증가시킨다.(C언어의 (++)연산)
Binary operations(이항 연산자)
-
이항 연산은 두 번째 피연산자가 소스와 대상을 겸한다. 이 명령어의 문법은 C언어에서 x-=y 꼴을 생각하면 된다. 그러나 여기서 주의할 점은 소스 피연산자가 먼저 나오고 대상 피연산자가 뒤에 나온다는 점이다. 예를 들어, 명령어 subq %rax, %rdx는 레지스터 %rdx에서 %rax 값을 뺸다.
- 첫 번째 피연산자는 즉시 값(immediate value), 레지스터, 메모리 위치가 올 수 있다.
- 두 번째 피연산자는 레지스터, 메모리 위치가 올 수 있다.
- mov 명령어와 마찬가지로 source와 destination 모두 메모리 위치일 수 없다.
- 두 번째 피연산자가 메모리 위치라면, 프로세서는 메모리 값을 읽어오고, 연산 수행 후 결과를 메모리에 쓰는 과정이 필요하다.
//solution
addq %rcx,(%rax) 0x100 0x100
subq %rdx,8(%rax) 0x108 0xA8
imulq $16,(%rax,%rdx,8) 0x118 0x110
incq 16(%rax) 0x110 0x14
decq %rcx %rcx 0x0
subq %rdx,%rax %rax 0xFD
3.5.3 Shift Operations
-
Shift 연산은 Shift 양(shift amount)이 먼저 지정되고, Shift할 값(value)이 두 번째로 지정된다.
-
shift 양은 즉시 값(immediate value) 또는 단일 바이트 레지스터 %cl로 지정할 수 있다.(오직 레지스터 %cl만 피연산자로 허용한다.)
- 이론적으로, 1바이트(8비트)의 shift 양을 사용하면 최대 28 - 1 = 255까지의 Shift 양을 인코딩할 수 있다. x86-64에서는 Shift 명령어가 w 비트 크기의 데이터 값에 작동될 때, **Shift 양을 레지스터 %cl의 하위 m비트에서 결정하며, 2m = w 이다.(상위 비트는 무시)
- 레지스터 %cl에 16진수 0xFF가 있으면
- salb 는 7비트 만큼 shift
- salw 는 15비트 만큼 shift
- sall 는 31비트 만큼 shift
- salq 는 63비트 만큼 shift
- 레지스터 %cl에 16진수 0xFF가 있으면
- 산술 시프트 연산과 논리 시프트 연산 모두 가능하다.
- 왼쪽 shift 명령어
- sal(Shift Arithmetic Left)
- shl(Shift Logical Left)
- 두 명령어는 동일한 동작을 수행하며, 오른쪽에서 0으로 채워넣는 방식이다.
- 오른쪽 shift 명령어
- sar(Shift Arithmetic right) : 부호 비트(sign bit)의 복사로 채워넣음
- shr(Shift Logical right) : 0으로 채워넣음
- 왼쪽 shift 명령어
- Shift 연산의 대상(destination) 피연산자는 레지스터 또는 메모리 위치가 될 수 있다.
3.5.4 Discussion
- 위 그림 3.11은 산술 연산을 수행하는 함수와 그 함수가 어셈블리 코드로 변환되는 예제를 보여준다.
- 함수의 매개 변수인 x,y,z는 각각 %rdi, %rsi, %rdx 레지스터에 초기 저장됨
- 어셈블리 명령어들은 C 소스 코드의 각 줄과 밀접하게 대응된다.
- 어셈블리 코드 설명
- 2번째 줄 : x^y 연산을 계산한다.(x와 y의 XOR 연산)
- 3,4번째 줄 : z*48 계산
- 이 연산은 leaq 명령어와 시프트 명령어를 조합하여 수행된다.
- 곱셈 대신, 48은 2의 배수이므로 쉬프트 연산으로 효율적으로 계산한다.
- 5번째 줄 : t1 & 0x0F0F0F0F 계산
- t1과 특정값의 비트 AND 연산을 수행한다.
- 6번째 줄 : 최종적으로 t4 = t3 - t2 연산을 수행한다.
- 이 연산의 결과는 레지스터 %rax에 저장된다.
- 함수의 반환 값은 %rax에 저장되므로, 이 값이 반환된다.
- 컴파일러의 최적화 동작
- 일반적으로, 컴파일러는 다음과 같은 방식으로 코드를 생성한다.
- 단일 레지스터를 여러 프로그램 값에 재사용한다.
- 예를 들어, %rax는 함수 내에서 여러 중간 값과 최종 반환 값을 저장하는 데 사용된다.
- 프로그램 값들을 레지스터 간에 이동(mov)하거나, 필요에 따라 재배치한다.
- 단일 레지스터를 여러 프로그램 값에 재사용한다.
- 레지스터의 사용을 최소화하고, 코드 실행 효율성을 높이기 위한 것
- 일반적으로, 컴파일러는 다음과 같은 방식으로 코드를 생성한다.
3.5.5 Special Arithmetic Operations
- 128비트 곱셈과 나눗셈 연산
- 128비트 곱셈 : x86-64는 64비트 정수 두 개의 곱셈 결과를 128비트로 처리하는 연산을 지원한다.
- 부호 없는 곱셈 : mulq
- 2의 보수 곱셈(부호 있는 곱셈) : imulq
- 결과는 레지스터 %rdx(상위 64비트)와 %rdx(하위 64비트)에 저장된다.
- 레지스터 조건
- %rax는 반드시 피연산자 중 하나를 포함해야 하며, 다른 피연산자는 명령어의 소스 피연산자로 제공된다.
- 128비트 곱셈 : x86-64는 64비트 정수 두 개의 곱셈 결과를 128비트로 처리하는 연산을 지원한다.
- 어셈블리 명령어의 동작
- imulq는 두 가지 형태로 사용된다.
- 2-operand 곱셈 : 두 64비트 값을 곱해 64비트 결과를 생성
- 1-operand 곱셈 : 64비트 값 두 개를 곱해 128비트 결과를 생성
typedef unsigned __int128 uint128_t; void store_uprod(uint128_t *dest, uint64_t x, uint64_t y) { *dest = x * (uint128_t) y; }movq %rsi, %rax ; x를 곱셈에 사용할 %rax로 이동 mulq %rdx ; y와 곱셈 movq %rax, (%rdi) ; 하위 64비트를 dest에 저장 movq %rdx, 8(%rdi) ; 상위 64비트를 dest+8에 저장 - imulq는 두 가지 형태로 사용된다.
- 128비트 나눗셈
- x86-64는 1-operand 나눗셈 명령어를 제공한다.
- 부호 있는 나눗셈 : idivq
- 부호 없는 나눗셈 : divq
- 피제수(dividend)는 128비트로, 상위 64비트는 %rdx에, 하위 64비트는 %rax에 저장된다.
- 결과
- 몫(quotient) : %rax
- 나머지(remainder) : %rdx
- x86-64는 1-operand 나눗셈 명령어를 제공한다.
- 64비트 피제수(dividend) 준비
- %rax에 64비트 피제수를 저장
- %rdx를 다음으로 설정 :
- 0으로 초기화(부호 없는 연산)
- %rax의 부호 비트(sign bit)로 확장(부호 있는 연산, cpto 명령어 사용)
- cpto : 부호 확장 명령어(피연산자는 없으며, %rax 부호 비트를 읽고, %rdx에 확장한다.)
void remdiv(long x, long y, long *qp, long *rp) { long q = x / y; long r = x % y; *qp = q; *rp = r; }movq %rdx, %r8 ; qp를 임시 레지스터 %r8로 복사 movq %rdi, %rax ; x를 %rax로 이동 cqto ; %rax를 확장하여 %rdx 설정 idivq %rsi ; y로 나눗셈 수행 movq %rax, (%r8) ; 몫을 qp에 저장 movq %rdx, (%rcx) ; 나머지를 rp에 저장 - 컴파일러 최적화
- 컴파일러는 제한된 레지스터를 효율적으로 사용하기 위해 단일 레지스터에 여러 값을 저장하고, 필요에 따라 값을 이동(mov 명령어 사용)한다.