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

3.7 Procedures

프로시저는 소프트웨어에서 중요한 추상화이다.

프로시저는 인수와 반환 값의 지정된 집합을 가진 기능들을 구현한 코드를 패키징하는 방법을 제공한다.

 

잘 설계된 소프트웨어는 프로시저를 추상화 메카니즘으로 사용하며, 상세한 구현은 숨기며 어떤 값이 계산되고 프로시저가

프로그램 상태에 어떤 영향 있는 지에 대한 명확한 정의는 제공한다.

프로시저는 프로그래밍 언어에서 많은 모습으로 보여진다. - 함수, 메소드, 서브루틴, 핸들러 등

 

프로시저에 대한 기계 수준을 제공할 때 많은 속성들이 있다

프로시저 P가 프로시저 Q를 호출하고, Q가 실행되고 P로 다시 반환된다.

 

- Passing Control : PC는 Q의 코드의 시작 주소로 설정되고 Q를 호출한 후에 P의 명령어로 설정한다.

- Passing Data : P는 하나 이상의 파라미터를 Q에게 제공하고, Q는 P에게 값을 다시 반환한다.

- Allocating and deallocating memory : Q는 지역 변수에 대한 공간을 할당할 필요가 있다.

 

x86-64은 특별한 명령어와 레지스터와 프로그램 메모리와 같은 기계 자원을 어떻게 사용하는 지에 대한 관습을 포함한 프로시저 구현체이다.

 

3.7.1 The Run-time Stack

C와 다른 언어의 프로시저 콜 메카니즘의 중요한 특징은 스택 자료 구조에 의해 제공된 LIFO 메모리 관리 원칙을 사용하는 것이다.

P가 Q를 호출하고, Q가 실행하고 있는 동안 P는 정지 상태이다.

Q가 실행되고 있을 때, 지역 변수에 대한 새로운 공간을 할당과 다른 프로시저에 대한 호출을 설정할 필요가 있다.

 

Q가 반환되면, 할당한 로컬 저장소는 해제한다.

프로그램은 스택을 사용한 프로시저에 의해 요구된 저장소를 관리한다.

P가 Q를 호출하면, 제어와 데이터 정보는 스택의 마지막에 추가된다. P가 반환되면 그 정보는 할당이 해제가 된다.

일반적인 스택 프레임 구조

위 그림은 런타임 스택의 전체적인 구조를 보여준다.

최근의 실행된 프로시저는 항상 스택의 top에 위치한다.

 

공간과 시간 효율성 관점에서, x86-64 프로시저들은 스택 프레임의 한 부분에만 할당된다.

 

3.7.2 Control Transfer

함수 P에서 Q로 제어 전송을 하는 것은 PC에 Q 코드에 대한 시작 주소로 설정하면 된다.

나중에 Q가 반환할 시간이 오면, 프로세서는 P의 실행을 다시 재개해야 하는 위치를 기록해야 한다.

이 정보는 Q를 호출하는 명령어와 함께 프로시저 Q를 부르면서 x86-64 기계에 저장된다.

 

이 명령어는 스택에 주소 A를 푸시하고, PC를 Q의 시작 주소로 설정한다.

푸시된 주소는 반환 주소로 부르며 call 명령어로 명령어의 주소로써 계산된다.

 

call 명령어는 호출된 프로시저가 시작할 때 명령어의 주소를 가리키는 타겟을 가지고 있다.

직접 호출은 라벨이 주어지는 반면에 간접 호출은 *로 주어진다.

 

C의 표준 호출/반환 메카니즘은 스택에 의해 제공되는 LIFO 메모리 관리 원칙이다.

 

3.7.3 Data Transfer

호출된 프로시저에 제어를 넘겨주고 프로시저가 반환되면, 프로시저 호출은 인수 데이터를 넘기고, 프로시저로부터 반환되는 것은

값을 반환하는 것을 포함한다.

x86-64에서, 대부분의 데이터들은 레지스터를 통해 이루어진다.

 

x86-64에서 6개의 인수가 레지스터를 통해 전달된다.

레지스터들은 전달된 데이터 타입의 크기에 맞는 레지스터를 위해 사용된 이름과 함께 구체적인 순서로 사용된다.

 

함수가 6개보다 많은 인수를 가지고 있으면, 다른 인수는 스택에 전달된다.

인수가 8개인 proc 함수

어셈블리 코드 (교재와 다름)

6번째 인수까지는 레지스터에 저장되지만 마지막 두 개는 스택으로 전달된다.

 

3.7.4 Local Storage on the Stack

로컬 데이터는 메모리에 저장되어야 한다.

 

- 로컬 데이터를 가지고 있기에 충분한 레지스터가 없다.

- 주소 연산자 &는 지역 변수에 적용되어서 주소를 생성할 수 있어야 한다.

- 어떤 지역 변수는 배열이나 구조체이므로 배열이나 구조체 레퍼런스로 접근되어야만 한다.

 

일반적으로 프로시저는 스택 포인터를 감소시키면서 스택 프레임에 공간을 할당한다.

 

3.7.5 Local Storage in Registers

프로그램 레지스터 집합은 모든 프로시저에 의해 공유되는 하나의 자원처럼 행동한다.

하나의 프로시저가 주어진 시간에만 활동적이지만, 하나의 프로시저가 다른 프로시저를 호출할 때, 피호출자는 호출자가 나중에 사용할

레지스터 값을 중복해서 쓰면 안되게 해야한다.

 

레지스터 %rbx, %rbp와 %r12 - %r15는 피호출자-저장 레지스터로 분류된다.

스택 포인터인 %rsp를 제외하고는 호출자-저장 레지스터로 분류된다.

 

3.7.6 Recursive Procedures

레지스터와 스택을 사용하는 규칙에는 x86-64 프로시저가 재귀적으로 호출하는 것을 허용한다.

각 프로시저는 스택에 자기 만의공간을 가지고 있고, 다양하게 호출의 지역 변수가 다른 것을 방해하지 않는다.

 

프로시저가 호출되고 반환하기 전에 할당 해제 할 때, 스택 규칙은 할당한 로컬 저장소를 위해 적절한 정책을 제공한다.

재귀적으로 함수를 호출하는 것은 다른 함수 호출과 같다.

할당과 할당 해제의 스택 규칙은 함수의 호출 반환 순서를 매치시킨다.

 

3.8 Array Allocation and Access

C에서 배열은 스칼라 데이터를 큰 데이터 타입으로 결합하는 것을 의미한다.

C는 배열의 간단한 구현체를 사용하여, 기계 코드로 번역하는 것은 꽤 직선적이다.

C의 특별한 특징 중 하나는 배열의 요소에 포인터를 생성할 수 있고, 이 포인터로 산술을 수행할 수 있다.

 

컴파일러를 최적화하는 것은 배열 인덱싱에 의해 사용된 주소 계산 단순화에 좋다.

 

3.8.1 Basic Principles

T A[n] -> T는 데이터 타입, 상수 N을 사용하여 다음과 같이 배열 선언

시작 위치는 xA로 표기한다.

 

L은 데이터 타입 T의 사이즈일 때, 메모리에 L * N 바이트의 인접한 지역의 할당

식별자 A는 배열의 시작에 대한 포인터로 사용된다.

 

배열 요소 i는 주소 xA + L * i에 저장된다.

int 타입의 E 배열이 있고, E[i] 값을 알고 싶다.

E는 레지스터 %rdx에 저장되어 있고, i는 레지스터 %rcx에 저장되어 있다.

명령어는 xE + 4i 주소 계산을 실시하고, 메모리 위치를 읽어 결과를 %eax로 복사한다.  movl (%rdx, %rcx, 4), %eax

 

3.8.2 Pointer Arithmetic

C는 포인터에 대한 산술을 허용해준다.

만약 p가 데이터 타입 T에 대한 포인터이면, p의 값은 xp이고 p + i 은 xp + L * i 값을 가진다.

 

단항 연산자 &와 *는 포인터의 생성과 디퍼런스를 허용해준다.

&Expr은 오브젝트의 주소를 주는 포인터이다.

*AExpr은 해당 주소의 값을 준다. Expr == *&Expr, A[i] == *(A + i)

 

3.8.3 Nested Arrays

배열할당과 참조의 기본적인 원칙은 우리가 배열을 만들 때 유지한다.

 

 

3.8.4 Fixed-size Arrays

C 컴파일러는 고정된 사이즈의 다차원 배열에 대한 코드 연산에 많은 최적화를 만들 수 있다.

 

원래 C 코드

최적화된 C 코드

최적화된 C 코드(아래 사진)는 많은 똑똑한 최적화를 포함하고 있다.

인덱스 j를 없애고 모든 배열 참조를 포인터 디퍼런스로 바꿨다.

 

3.8.5 Variable-size Arrays

C는 컴파일 시간에 결정되는 사이즈를 가진 다차원 배열을 지원하였다.

가변 배열을 필요로 하는 프로그래머는 malloc 이나 calloc과 같은 함수를 사용하여 이러한 배열에 대한 저장소를 할당해야 한다.

그리고 다차원 배열의 매핑을 1차원으로 인코딩해야 한다.

 

3.9 Heterogeneous Data Structures

C언어는 다른 타입들을 조합하여 데이터 타입을 만드는 데 두 가지 메카니즘을 제공한다.

구조체(structures)는 struct라는 키워드를 사용하여 선언, 다수의 오브젝트를 단일체로 결합

유니온(union)은 union이라는 키워드를 사용하여 선언, 오브젝트 다양한 데이터 타입을 사용하여 참조되게 해준다

 

3.9.1 Structures

C struct 선언은 다른 타입의 오브젝트들을 하나의 단일 오브젝트로 그룹화하는 데이터 타입을 만든다.

컴파일러는 각 필드의 바이트 오프셋을 가리키는 각 구조체 타입에 대한 정보를 유지한다.

이는 메모리 참조 명령어에서의 이동인 오프셋을 사용하여 구조체 요소에 대한 참조를 생성한다.

struct rec {
    int i;
    int j;
    int a[2];
    int *p;
};

위 구조체는 4개의 필드를 포함하고 있다: 2개의 int 형을 가진 4바이트 값, int 형을 가진 두 개의 요소를 가진 배열, 8바이트 정수 포인터

총 24바이트를 가지고 있다.

구조체의 필드에 접근하려면, 컴파일러는 구조체의 주소에 적절한 오프셋을 더한 코드를 생성한다.

 

3.9.2 Unions

Union은 C의 타입 시스템을 우회하는 방법을 제공하며, 단일 오브젝트를 다수의 타입에 따라 참조되게 해준다.

다른 필드가 다른 메모리 블록을 참조하는 대신, 그들은 다 같은 블록을 참조한다.

 

Union은 다양한 컨텍스트에서 유용하다. 하지만, Union은 C 타입 시스템에서 제공되는 안정성을 우회하기 때문에 Union은 버그를 만들 수 있다.

 

3.9.3 Data Alignment -- 다시

많은 컴퓨터 시스템이 원시적인 데이터 타입에 대한 주소에 제한을 건다.

이러한 정렬 제한(alignment restriction)은 프로세서와 메모리 시스템 간의 인터페이스를 형성하는 하드웨어 설계를 단순화한다.

 

예를 들어, 프로세서가 8로 곱해지는 주소와 함께 메모리로부터 8바이트를 불러온다고 생각해보자.