CS:APP Ch03. Machine-Level Representation of Programs - 2

3.4 Accessing Information

x86-64 중앙처리장치(CPU)는 64-비트 값을 저장하는 16개의 범용(general-purpose) 레지스터를 포함한다.

이 레지스터들은 정수 데이터와 포인터를 저장한다.

 

레지스터들의 이름은 %r로 시작하고 뒤에는 다른 이름들을 가지고 있다.

명령어는 16개 레지스터의 낮은 정렬에 있는 바이트에 저장되어 있는 다른 사이즈의 데이터에 대해 연산한다.

바이트 수준 연산은 최하위 비트에 접근한다. (16-비트 연산은 최하위 2바이트, 32비트는 4비트, 64-비트는 모든 레지스터에 접근한다.)

 

다른 레지스터들은 프로그램에서 다른 역할을 제공한다.

가장 유일한 것은 스택 포인터(stack pointer)로 %rsp이며, 런타임 스택에서 마지막 위치를 가리키는 데 사용된다.

어떤 명령어는 이 레지스터를 읽거나 쓸 때가 있다. 다른 15개의 레지스터들은 그들의 사용에서 유연함을 가진다.

 

표준 프로그래밍 기준은 어떻게 레지스터가 스택을 관리하는 지, 함수 매개변수를 어떻게 넘기는 지, 함수로부터 값을 반환하는지, 지역과 임시 데이터를 저장하는 지에 대해 결정한다.

 

3.4.1 Operand Specifiers

대부분의 명령어는 하나 이상의 피연산자를 가진다.

피연산자는 연산을 수행하는 데 사용되는 값과 결과를 위치시키려는 목적지에 사용되는 소스 값을 명세한다.

피연산자 형식

x86-64는 많은 피연산자 형태를 제공한다. 소스 값은 상수나 레지스터나 메모리로부터 읽어들인 형태로 주어진다.

결과 값은 레지스터와 메모리에 저장된다.

각기 다른 피연산자들은 세 가지 유형으로 나뉜다.

 

첫 번째는 immediate 이며 상수 값에 사용된다.

두 번째는 register로 레지스터의 내용을 표현한다. R[r]

세 번째는 메모리 위치에 접근하는 memory 레퍼런스로 효과적인 주소로 불린다.

메모리를 하나의 큰 바이트 배열로 보기 때문에 Mb[Addr] 형태를 사용하며 Addr로 시작한 메모리에 저장된 b-바이트 값을 표현한다.

 

가장 일반적인 형태는 Imm(rb, ri, s)이다.

Imm은 Immediate 오프셋이며, 기준 레지스터 rb, 인덱스 레지스터 ri, 스케일 값 s(1, 2, 4, 8)이다.

기준 레지스터와 인덱스 레지스터는 64-비트 레지스터여야 한다.

효과적인 주소는 Imm + R[rb] + R[ri] * s 로 계산된다.

 

3.4.2 Data Movement Instructions

가장 무거운 명령어는 데이터를 다른 위치로 복사하는 것이다.

피연산자의 일반성은 간단한 데이터 이동 명령어가 가능한 범위를 표현하게 해준다.

 

많은 다른 명령어들을 클래스 형태로 되어 있는 명령어들은 다른 피연산자 사이즈에서 다른 연산을 수행하는 명령어 클래스(instructions classes)로 그룹화한다.

간단한 데이터 이동 명령어

위의 표는 MOV 클래스인 데이터 이동 명령어에 대한표이다.

어떠한 변형없이 데이터를 소스 위치에서 목적지 위치로 복사하는 명령어들이다.

 

소스 피연산자는 직접적이고, 메모리나 레지스터에 저장되어 있는 값을 지정한다.

목적지 피연산자는 메모리나 레지스터 주소를 지정한다.

 

값을 한 위치에서 다른 위치로 복사하는 것은 두 가지 명령어를 요구한다.

하나는 소스 값을 레지스터에 로드(load)하는 것

두 번째는 목적지에 레지스터 값을 쓰는(write) 것

 

MOV 명령어는 레지스터 바이트나 메모리 위치만을 갱신한다.

movl이 레지스터를 목적지로 가지고 있을 때, 레지스터의 가장 높은 바이트를 0으로 바꾸는 것만이 예외이다.

 

movq 명령어는 32-비트 2의 보수 수를 표현할 수 있는 immediate 소스 피연산자만을 가질 수 있다.

이 값은 부호를 확장하여 목적지에 대한 64-비트 값을 생성한다.

movabsq 명령어는 임의적인 64-비트 immediate 값을 가질 수 있다.

 

MOVZ, MOVS

 

3.4.3 Data Movement Example -- 다시

C 언어 예시

어셈블리 코드 예시

3.4.4 Pushing and Popping Stack Data

두 가지의 데이터 이동 연산은 프로그램 스택에서 데이터를 푸시(push)하고 팝(pop)한다.

스택은 프로시저 콜을 다룰 때의 필수적인 역할을 한다.

스택은 값이 추가되거나 삭제하는 자료 구조(Data Structure)지만 "후입선출(Last-In, First-Out)" 원칙을 지킨다.

 

스택은 배열로 구현될 수 있는 데, 배열의 끝에서만 데이터를 삽입/삭제 할 수 있다. 이를 스택의 top이라 한다.

x86-64에서, 프로그램 스택은 메모리의 지역을 저장한다.

스택 연산의 과정

pushq 명령어는 데이터를 스택에 push하고, 반면에 popq 명령어는 pop한다.

 

스택이 프로그램 코드와 프로그램 데이터의 형태로 같은 메모리에 포함되어 있기 때문에,

프로그램은 표준 메모리 어드레싱 방법을 사용한 스택과 함께 임의적인 위치에 접근할 수 있다.

 

3.5 Arithmetic and Logical Operations

x86-64 산술과 논리 연산들은 명령어 클래스 형태로 제공된다.

ADD는 네 가지 명령어를 포함하고 있다: addb, addw, addl, addq

연산은 네 가지 그룹으로 나눌 수 있다: 효과적인 주소 로드, 단항(unary), 이항, 이진(Binary), 시프트

정수 산술 연산

 

이진 연산자는 두 개의 피연산자가 있고, 단일체는 하나의 피연산자를 가지고 있다.

 

3.5.1 Load Effective Address

load effective address 명령어인 leaq는 movq의 변형이다. 메모리부터 레지스터까지를 읽는 명령어이다.

leaq 명령어는 간단한 산술을 수행하기 위해 주로 사용되지만, 메모리 전체를 레퍼런스 하지 않는다.

이 명령어는 마지막 메모리 레퍼런스에 대한 포인터를 생성하는 데 사용된다.

 

leaq C언어 예시

위 프로그램 어셈블리어 예시

위 어셈블리어를 보면 함수의 산술 연산으 세 개의 leaq 명령어를 볼 수 있다.

leaq (%rdi, %rsi, 4), %rax -> x + 4 * y

leaq (%rdi, %rsi, 2), %rcx -> z + 2 * z = 3z

leaq (%rax, %rcx, 4), %rax -> (x + 4 * y) + 4 * (3z) = x + 4 * y + 12 * z

 

덧셈과 제한적인 곱셈을 수행하는 leaq 명령어의 능력은 유용하다.

 

3.5.2 Unary and Binary Operations

두 번째 연산은 단항 연산으로 하나의 피연산자로 소스와 목적지에 대해 동시에 제공한다.

이 피연산자는 레지스터와 메모리 위치가 될 수 있다. ++, --

 

두 번째 피연산자가 소스와 목적지 동시로 사용되는 이항 연산이다.

x -= y 와 같은 대입 연산자

 

3.5.3 Shift Operations

 

시프트 값이 먼저 주어지고, 시프트할 값이 두 번째로 주어지는 시프트 연산이다.

산술과 논리 오른쪽 시프트 연산이 가능하다.

 

왼쪽 시프트 연산에는 두 가지 이름이 있다. SAL = SHL

오른쪽 시프트 연산에서 SAR은 산술적, SHR은 논리적 시프트 연산이다.

 

3.5.4 Discussion

대부분의 명령어는 부호가 없거나 2의 보수 산술에 사용된다.

 

arith.c 예시

arith 어셈블리 (교재랑 다름)

x 는 레지스터 %esi, y는 %edi, z는 %rdx에 저장된다.

 

3.5.5 Special Arithmetic Operations -- 다시

두 개의 부호가 있거나 없는 64-비트 정수를 곱하면 128-비트가 필요한 결과를 얻는다.

 

특별한 산술 연산

3.6 Control

여태까지 우리는 직선적인(straight-line) 코드만을 고려하였다.

조건문, 반복문(loop), switch문과 같은 구조는 조건적 실행을 필요로 한다.

 

기계 코드는 조건적 행동을 구현하기 위한 기본적인 저수준 메커니즘을 제공한다:

데이터 값을 검증하고 검증의 결과에 의존하는 제어 흐름이나 데이터 흐름를 변경한다.

 

데이터 의존 제어 흐름은 조건적 행동을 구현하는 데 더 일반적이고 흔한 접근이다.

C와 기계 코드이 명령어는 순차적으로 실행된다.

기계 코드 명령어 집합의 실행 순서는 제어권이 프로그램의 다른 부분으로 이동하는 jump 명령어로 바뀔 수 있다.

 

3.6.1 Condition Code

CPU는 가장 최근의 산술적이거나 논리적인 연산을 설명하는 단일 비트 조건 코드 레지스터를 유지한다.

이러한 레지스터들은 조건적인 분기(branch)들을 수행하기 위해 검증받는다.

 

다음과 같은 조건 코드들은 유용하다:

CF : Carry Flag

ZF : Zero Flag

SF : Sign Flag

OF : Overflow Flag

 

예를 들어, C 명령어인 t = a + b를 수행하기 위해 ADD 함수를 사용한다. 그럴 때의 조건 코드는 다음과 같다.

XOR과 같은 논리적인 연산에서, carry와 overflow flag는 0이 된다.

시프트 연산에서, carry flag는 나가 떨어진 마지막 비트로 되고, overflow flag는 0이 된다.

 

다른 레지스터로 변경하지 않고 조건 코드를 설정하는 두 가지 명령어 클래스가 있다:

비교와 테스트 명령어

CMP 명령어는 두 가지 피연산자의 차이에 따라 조건 코드를 설정한다.

SUB 명령어와 같은 방식으로 작동하지만, 그들의 목적지를 업데이트하지 않고 조건 코드를 설정하는 것은 다르다.

 

TEST 명령어는 AND 명령어와 같은 방식으로 작동하지만, 그들의 목적지를 변경하지 않고 조건 코드를 설정하는 것은 다르다.

 

3.6.2 Accessing the Condition Codes

조건 코드를 직접적으로 읽는 거 보다, 조건 코드를 사용하는 데 세 가지 흔한 방법이 있다.

1. 조건 코드의 어떤 조합에 의존하여 단일 바이트를 0또는 1로 설정한다.

2. 다른 프로그램으로 조건적으로 jump할 수 있다.

3. 데이터를 조건적으로 전송할 수 있다.

 

SET 명령어는 하위 단일 바이트 레지스터 요소나 단일 바이트 목적지 위치를 가지고 있다.

SET 명령어

각 명령어들은 조건 코드의 조합을 기반으로 단일 바이트를 0 또는 1로 지정한다.

어떤 명령어는 "synonyms"를 가지고 있으며, 이는 같은 기계 명령어의 대안 이름이다.

 

3.6.3 Jump Instructions

jump 명령어는 프로그램에 완전히 새로운 위치로 바꾸어 실행한다.

jump 목적지는 label(라벨)로 어셈블리 코드 내를 가리킨다.

 

jump .L1 명령어는 밑에 movq 명령어를 skip하고popq 명령어로 재개한다.

오브젝트-코드 파일을 생성하여, 어셈블러는 모든 라벨된(labeled) 명령어의 주소를 결정하고

jump 타겟을 jump 명령어의 한 부분으로 인코딩한다.

 

jmp *%rax는 레지스터 내의 값인 %rax를 jump 타겟으로 사용하고,

jmp *(%rax)는 메모리로부터 jump 타겟을 읽는다.

 

3.6.4 Jump Instruction Encodings

어떻게 jump 명령어의 타겟이 인코딩되는지를 이해하는 것은 링킹(linking)에서 중요한 부분이다.

jump 타겟은 상징적 라벨을 사용해서 작성된다.

 

어셈블러와 링커는 jump 타겟의 적절한 인코딩을 생성한다.

많은 인코딩이 있지만, 가장 흔하게 사용하는 것은 PC relative이다.

타겟 명령어의 주소와 jump을 따라가는 명령어의 주소 간의 차이를 인코딩한다.

 

두 번째 인코딩 방법은 "절대적인" 주소를 주는 것으로 타겟을 바로 구체화하기 위해4 바이트를 사용한다.

 

PC-relative 어드레싱을 수행할 때 Program Counter의 값은 jump 자체가 아닌 jump을 따르는 명령어의 주소이다.

링킹 이후에 프로그램에서 명령어는 다른 주소로 재배치 받지만 jump 타겟은 바뀌지 않는다.

 

3.6.5 Implementing Conditional Branches with Conditional Control

C에서 조건문과 명령어를 기계 코드로 번역하는 가장 일반적인 방법은 조건적인 jump와 무조건적인 jump의 조합을 사용하는 것이다.

 

goto 명령어를 사용하는 것은 안 좋은 프로그래밍 스타일이다. 코드를 매우 읽고 디버깅하기 까다롭기 때문이다.

 

3.6.6 Implementing Conditional Branches with Conditional Move -- 다시

조건 연산을 구현하기 위한 가장 관습적인 방법은 제어의 조건적 전송을 통한 구현이다.

이 방법은 매우 단순하고 일반적이지만, 모던 프로세서에서는 비효율적이다.

 

대안적인 전략은 데이터의 조건적 전송을 통해 구현하는 것이다.

이 접근은 조건 연산의 결과와 조건에 속하는 것을 하나 선택하여 계산한다.

이 전략은 매우 제한적인 경우지만, 간단한 조건적 이동 명령어에 의해 구현된다.

 

조건적 데이터 전송에 따른 코드가 조건적 제어 전송보다 성능이 좋은 지 이해하려면, 모던 프로세서 연산을 이해해야 한다.

프로세서는 파이프라이닝(pipelining)을 통해 높은 성능을 얻는다.

 

3.6.7 Loops

C는 do-while, while, for문과 같은 다양한 반복문을 제공한다.

기계 코드에는 대응하는 명령어가 없지만, test와 jump의 조합으로 반복문을 구현한다.

 

Do-While Loops

While Loops

For Loops

 

3.6.8 Switch Statements