Search
Duplicate

컴퓨터 구조 및 설계/ 명령어: 컴퓨터 언어

서론

컴퓨터 하드웨어에게 일을 시키려면 하드웨어가 알아들을 수 있는 언어로 말을 해야 한다. 컴퓨터 언어에서 단어를 명령어(instruction)라 하고, 그 어휘를 명령어 집합(instruction set)이라고 한다.
기계어도 다양한 것처럼 보이지만 실제로는 모두 유사하기 때문에 서로 다른 언어라기보다는 같은 언어의 사투리 정도로 보는 것이 타당하다. 그러므로 일단 한 언어를 배우면 다른 언어들도 쉽게 익숙해질 수 있다.
사용할 명령어 집합은 MIPS에서 선택했다.
이 장에서 명령어 표현 방식을 배우는데, 표현 방식을 배우면 컴퓨터의 가장 큰 비밀인 내장 프로그램 개념(stored-program concept)을 이해할 수 있다.

하드웨어 연산

기본적으로 모든 컴퓨터는 산술 연산을 할 수 있어야 한다. 다음 MIPS 어셈블리 언어는 두 변수 b와 c를 더해서 그 합을 a에 넣으라고 컴퓨터에 지시한다.
add a, b, c
Plain Text
MIPS 산술 명령어는 반드시 한 종류의 연산만 지시하며 항상 변수 세 개를 갖는 형식을 엄격히 지킨다. 네 변수 b, c, d, e의 합을 a에 넣으려면 다음과 같이 한다.
네 변수의 합을 구하려면 명령어가 세 개 필요하다.
add a, b, c # The sum of b and c is placed in a add a, a, d # The sum of b, c, and d is now in a add a, a, e # The sum of b, c, d, and e is now in a
Plain Text
#의 오른쪽은 주석(comment)인데, 컴퓨터는 이것을 무시한다. 고급 프로그래밍 언어와 달리 한 줄에 명령어 하나만 쓸 수 있으며, 줄이 끝나면 주석도 끝난다는 점이 C와 다르다.
모든 명령어가 피연산자를 반드시 세 개씩 갖도록 제한하는 것은 하드웨어를 단순하게 하자는 원칙과 부합한다. 이런 관점에서 하드웨어 설계의 3대 원칙 중 첫 번째를 도출 할 수 있다.
설계 원칙 1: 간단하게 하기 위해서는 규칙적인 것이 좋다.

피연산자

상위 수준 언어 프로그램과 달리 산술 명령어의 피연산자에는 제약이 있다. 레지스터(register)라고 하는 하드웨어로 직접 구현된 특수 위치 몇 곳에 있는 것만을 사용할 수 있다.
레지스터는 하드웨어 설계의 기본 요소인 동시에 프로그래머에게도 보이는 부분이므로 컴퓨터를 구성하는 벽돌과 같다고 할 수 있다.
MIPS 구조에서 레지스터의 크기는 32비트이다. MIPS에서는 32비트가 한 덩어리로 처리되는 일이 매우 빈번하므로 이것을 워드(word)라고 부른다.
프로그래밍 언어에서 사용하는 변수와 하드웨어 레지스터의 큰 차이점 하나는 레지스터는 개수가 한정되어 있다는 점이다. 현대 컴퓨터에서는 MIPS에서처럼 보통 32개의 레지스터가 있다.
그러므로 기호 형태로 표현된 MIPS 언어를 단계적으로 구체화할 때 산술 명령어의 각 피연산자는 32개의 32비트 레지스터 중 하나이어야 한다는 제약이 추가된다.
레지스터 개수를 32개로 제한하는 이유는 하드웨어 기술의 바탕이 되는 세 가지 설계 원칙 중 두 번째 원칙에서 찾을 수 있다.
설계 원칙 2: 작은 것이 더 빠르다.
레지스터가 아주 많아지면 전기 신호가 더 멀리까지 전달되어야 하므로 클럭 사이클 시간이 길어진다.
물론 ‘작은 것이 더 빠르다’가 절대적인 것은 아니다. 예컨대 레지스터를 31개로 한다고 해서 32개보다 빨라지지는 않는다. 이 같은 사실은 컴퓨터 설계자로 하여금 이 문제를 진지하게 고려하도록 만든다.
컴퓨터 설계자는 더 많은 레지스터를 원하는 프로그램의 갈망과 클럭 사이클을 빠르게 하고 싶은 본인의 바람 사이에서 적절한 타협점을 찾아야 할 것이다.
레지스터를 32개 이상 사용하지 않는 또 다른 이유는 비트 수와 관련 있다. 이는 2.5절에서 살펴보겠다.
우리는 단순히 레지스터 번호 0부터 31까지 사용하여 명령어를 작성하지만 레지스터를 나타내기 위해 MIPS 관례는 달러 기호 뒤에 두 글자가 따라 나오는 이름을 사용한다.
2.8절에서 이유를 설명하겠지만 지금은 단순히 C나 Java의 변수에 해당하는 레지스터를 위해서는 $s0, $s1 등을 사용하고 프로그램을 MIPS 명령어로 컴파일 하기 위해 필요한 임시 레지스터를 위해서는 $t0, $t1 등을 사용하겠다.

메모리 피연산자

프로그래밍 언어에는 값 하나만 기억하는 단순 변수 외에도 배열(array)나 구조체(structure) 같은 복잡한 자료구조가 있다. 이러한 복잡한 자료구조 하나에는 레지스터 개수보다 훨씬 많은 데이터 원소가 있을 수 있다. 그렇다면 이런 큰 구조는 컴퓨터 내에서 어떻게 표현되고 사용되는가?
컴퓨터의 5대 구성 요소를 생각해 보자. 프로세서는 소량의 데이터만을 레지스터에 저장할 수 있지만, 컴퓨터 메모리는 수십억 개의 데이터를 저장할 수 있다. 그러므로 배열이나 구조체 같은 자료 구조는 메모리에 보관한다.
MIPS의 산술연산은 레지스터에서만 실행되므로 메모리와 레지스터 간에 데이터를 주고받는 명령어가 있어야 한다. 이런 명령어를 데이터 전송 명령어(data transfer instruction)라 한다.
메모리에 기억된 데이터 워드에 접근하려면 명령어가 메모리 주소(address)를 지정해야 한다. 메모리는 주소가 인덱스 역할을 하는 큰 1차원 배열이다. 주소는 0부터 시작한다.
예컨대 아래 그림 2.2에서 세 번째 데이터 원소의 주소는 2이고, Memory[2]의 값은 10이다.
메모리에서 레지스터로 데이터를 복사해 오는 데이터 전송 명령을 적재(load)라 한다.
적재 명령은 연산자 이름과 메모리에서 읽어 온 값을 저장할 레지스터, 메모리 접근에 사용할 상수와 레지스터로 구성된다. 메모리 주소는 명령어의 상수 부분과 두 번째 레지스터 값의 합으로 구해진다.
MIPS에서 이 명령어의 실제 이름은 lw(load word)이다.

예제) 메모리 피연산자를 사용하는 치환문의 번역

A는 100워드 배열이고, 변수 g, h는 레지스터 $s1, $s2에 할당되었다고 가정한다. 또 배열 A의 시작 주소(base address)가 $s3에 기억되어 있다고 할 때, 다음 C 문장을 컴파일 하라.
g = h + A[8];
Plain Text
이 치환문에 연산은 하나밖에 없지만 피연산자 중 하나가 메모리에 있으므로 먼저 A[8]을 레지스터로 옮긴 후 연산을 시작해야 한다. 이 배열 원소의 주소는 $s3에 있는 배열의 시작 주소에 인덱스 8을 더한 값이다. 이 데이터는 다음 명령어가 사용할 수 있도록 임시 레지스터에 넣어야 한다. 그림 2.2를 참고하면 첫 명령어는 다음과 같다.
lw  $t0, 8($s3)  # Temporary reg $t0 gets A[8]
Plain Text
(이 명령어 그대로는 약간의 문제가 있어 곧 수정될 것이지만 당장은 이대로 사용한다) 이제 필요한 값(즉 A[8])을 레지스터 $t0에 넣었으므로 덧셈을 수행할 수 있다. 다음 덧셈 명령어는 h($s2에 있음)를 A[8]($t0 값)에 더해서 g에 해당하는 레지스터($s1)에 넣는다.
add $s1, $s2, $t0  # g = h + A[8]
Plain Text
데이터 전송 명령어의 상수 부분(8)을 변위(offset)라 하고, 주소 계산을 위해 여기에 더해지는 레지스터($s3)을 베이스 레지스터(base register)라 한다.
변수를 레지스터와 연관 짓는 일뿐 아니라 배열이나 구조체 같은 자료구조를 메모리에 할당하는 것도 컴파일러의 임무이다. 그런 다음 컴파일러는 자료구조의 시작 주소를 데이터 전송 명령에 넣을 수가 있다.
프로그램에서 8비트로 구성된 바이트를 많이 사용하므로 대부분의 컴퓨터는 바이트 단위로 주소를 지정한다. 워드 주소는 워드를 구성하는 4바이트 주소 중 하나를 사용한다. 그러므로 연속된 워드의 주소는 4씩 차이난다.
아래 그림 2.3은 그림 2.2의 실제 MIPS 주소를 보여주는 것이다. 예컨대 세 번째 워드의 바이트 주소는 8이다.
MIPS에서 워드의 시작 주소는 항상 4의 배수여야 한다. 이러한 요구사항을 정렬 제약(alignment restriction)이라 하며, 많은 컴퓨터에서 이 방법을 사용한다. (정렬을 사용하면 데이터 전송이 빨라지는데, 그 이유는 4장에서 설명한다)
컴퓨터는 제일 왼쪽, 즉 최상위(big end) 바이트 주소를 워드 주소로 사용하는 것과 제일 오른쪽, 즉 최하위(little end) 바이트 주소를 워드 주소로 사용하는 것 두 종류로 나누어진다. MIPS는 최상위 주소를 사용하는 빅엔디안(big-endian) 계열에 속한다.
바이트 주소의 사용은 배열의 인덱스에도 영향을 미친다. 앞의 코드에서 바이트 주소를 제대로 구하려면 베이스 레지스터 $s3에 4×8 즉 32를 더해야 한다. 그래야 A[8/4]이 아닌 A[8]의 주소가 구해진다.
객체와 반대로 레지스터에서 메모리로 데이터를 보내는 명령을 저장(store)이라 한다. 저장 명령의 생김새는 적재와 같다. 즉 연산자 이름, 저장할 데이터를 갖고 있는 레지스터, 배열 원소 선택에 사용할 변위, 베이스 레지스터로 구성된다.
앞서와 마찬가지로 주소의 일부는 상수 형태로 명령어에 포함되어 있고 일부는 레지스터에 기억되어 있다.
MIPS에서 이 명령어의 실제 이름은 sw(store word)이다.
적재, 저장 명령어에서의 주소가 이진수이기 때문에 DRAM 메모리 주소가 십진수 단위가 아니라 이진수 단위로 표시됨을 알 수 있다. 즉 기가바이트(10910^{9}) 또는 테라바이트(101210^{12})가 아닌 게비바이트(2302^{30})또는 테비바이트(2402^{40})로 표시된다.

예제) 적재와 저장을 사용한 번역

변수 h가 레지스터 $s2에 할당되어 있으며 배열 A의 시작 주소는 $s3에 들어 있다고 가정하자. 다음 C 문장을 MIPS 어셈블리 프로그램으로 바꾸어라.
A[12] = h + A[8];
Plain Text
위 C 문장에 연산자는 하나지만 피연산자 두 개가 메모리에 있기 때문에 MIPS 명령어가 더 필요하다. 처음 두 명령어는 앞의 예와 같으나, 적재 명령어가 바이트 주소에 맞는 적절한 변위를 사용한 것과 add 명령어가 합을 $t0에 넣는 것이 다르다.
lw $t0, 32($s3)  # Temporary reg $t0 gets A[8] add $t0, $s2, $t0 # Temporary reg $t0 gets h + A[8]
Plain Text
마지막 명령어는 48(4 x 12)을 변위로, $s3을 베이스 레지스터로 사용하여 합을 A[12]에 저장한다.
sw  $t0, 48($s3)  # Stores h + A[8] back into A[12]
Plain Text
MIPS에서 메모리와 레지스터 사이에 워드를 복사하는 명령어들이 lw와 sw인데, 다른 컴퓨터에서는 데이터 전송을 위해 적재 명령어와 저장 명령어 외에 다른 명령어들을 함께 사용하기도 한다. Intel x86이 이러한 구조인데 2.15절에서 설명한다.
컴퓨터가 갖고 있는 레지스터보다 프로그램에서 사용하는 변수가 더 많은 경우가 자주 있다. 그러므로 컴파일러는 자주 사용되는 변수를 가능한 한 많이 레지스터에 넣고 나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣는다.
자주 사용하지 않는(또는 한참 후에 사용할) 변수를 메모리에 넣는 일을 레지스터 스필링(spilling)이라고 한다.
‘작을수록 빠르다’ 원칙에 의하면 레지스터가 더 작으므로 메모리는 레지스터 보다 속도가 느려야 한다. 이것은 사실이며 데이터가 레지스터에 있으면 더 빨리 접근할 수 있다.
레지스터에 저장된 데이터는 메모리 데이터보다 사용하기도 편리하다. MIPS의 산술연산 명령은 레지스터 두 개를 읽어서 연산한 다음 결과를 레지스터에 쓴다. 하지만 데이터 전송 명령은 피연산자 하나를 읽거나 쓰는 일만 할 뿐 데이터에 대한 연산은 하지 못한다.
레지스터는 메모리보다 접근시간이 짧고 처리량도 많으므로, 레지스터에 저장된 데이터를 사용하면 시간이 절약되고 사용하기도 간편하다. 그뿐만 아니라 레지스터 접근은 메모리 접근보다 에너지도 적게 든다. 그러므로 좋은 성능을 얻고 에너지를 절약하기 위해서는 컴파일러가 레지스터를 효율적으로 사용하여야 한다.

상수 또는 수치 피연산자

프로그램의 연산에서 상수를 사용하는 경우는 많이 있다. 배열의 다음 원소를 가리키도록 인덱스를 증가시키는 경우가 한 예가 될 것이다. SPEC CPU2006 벤치마크를 실행해 보면 MIPS 산술 명령의 절반 이상이 상수를 피연산자로 사용함을 알 수 있다.
이제까지 배운 명령어만으로 상수를 사용하려면 메모리에서 상수를 읽어와야 한다. (상수는 프로그램이 적재될 때 메모리에 넣어진다) 예컨대 레지스터 $s3에 상수 4를 더하는 코드는 아래와 같다.
lw  $t0, AddrConstant4($s1)  # $t0 = constant 4 add $s3, $s3, $t0 # $s3 = $s3 + $t0 ($t0 == 4)
Plain Text
여기서 $s1 + AddrConstatnt4는 상수 4가 저장되어 있는 메모리 주소라고 가정한다. 적재 명령어를 사용하지 않는 방법은 피연산자 중 하나가 상수인 산술연산 명령어를 제공하는 것이다.
이 상수를 수치(immediate) 피연산자라고 한다. 수치 피연산자를 갖는 덧셈 명령어는 addi인데 레지스터 $s3에 4를 더하려면 다음과 같이 쓰면 된다.
addi  $s3, $s3, 4  # $s3 = $s3 + 4
Plain Text
상수 피연산자는 자주 사용되므로 상수 필드를 갖는 산술 명령어를 사용하면 매번 메모리에서 상수를 가져오는 것보다 연산이 훨씬 빨라지고 에너지를 덜 소모하게 된다.
상수 0은 또 다른 역할을 하는데 유용한 여러 변형을 제공함으로써 단순한 명령어 집합을 가능케 한다. 예컨대 복사(move) 연산은 피연산자 중 하나가 0인 add 명령어이다.
따라서 MIPS에서는 레지스터 $zero를 값 0으로 묶어 두도록 회로가 구현되어 있다. (독자가 예상하듯이 레지스터 0이다)
쓰이는 빈도가 높으면 상수를 명령어에 포함 시키도록 하는 것이 ‘자주 생기는 일을 빠르게 하라’는 좋은 아이디어의 또 다른 예가 된다.

부호있는 수와 부호없는 수

모든 정보는 이진 자리 수(binary digit), 즉 비트(bit)로 구성되므로 비트가 계산의 기본 단위가 된다.
워드 내의 각 비트에 오른쪽에서 왼쪽으로 0, 1, 2, 3… 과 같은 번호를 붙인다. 아래 그림은 MIPS 워드 내의 비트에 번호를 붙이는 방식과 이진수 1011 의 표현을 보여주고 있다.
워드는 수평으로 뿐만 아니라 수직으로 그릴 수 있기 때문에 가장 오른쪽 혹은 가장 왼쪽 비트라고 말하면 애매할 수 있다. 대신 LSB(least significant bit)라는 용어를 써서 가장 오른쪽의 비트 0을 나타내고 MSB(most significant bit)라는 용어를 써서 가장 왼쪽의 비트 31을 나타내기도 한다.
MIPS 워드의 길이는 32비트이므로 2322^{32}가지의 서로 다른 32비트 패턴을 표현할 수 있다. 이 조합이 0부터 2321(4,294,967,295)2^{32} - 1(4,294,967,295) 까지의 숫자를 표시하게 하는 것은 자연스러운 일이다.
32비트 이진수는 비트 값과 2의 멱수를 곱한 값으로 표현할 수 있다. 여기서 xix_{i}xxii번째 비트를 의미한다)
(x31×231)+(x30×230)+(x29×229)+...+(x1×21)+(x0×20)(x_{31} \times 2^{31}) + (x_{30} \times 2^{30}) + (x_{29} \times 2^{29}) + ... + (x_{1} \times 2^{1}) + (x_{0} \times 2^{0})
여러 이유로 이러한 양수를 부호없는 수라 한다.
이진 비트 패턴은 단순히 수의 표기방법일 뿐이라는 것을 명심하라.
이러한 이진 비트 패턴을 더하고 빼고 곱하고 나누는 하드웨어를 설계할 수 있다. 만약 이러한 연산 결과가 하드웨어에 구현된 오른쪽 비트들만으로는 표현일 불가능하면, 오버플로(overflow)가 발생했다고 말한다.
컴퓨터 프로그램은 양수와 음수를 모두 계산한다. 따라서 양수와 음수를 구별하는 표현방법이 필요하다. 가장 확실한 방법은 별도의 부호를 덧붙이는 것인데, 부호는 한 비트면 표현할 수 있다. 이 방법의 이름은 부호와 크기(sign and magnitude) 표현법이다.
그러나 부호와 크기 표현법에는 몇 가지 단점이 있다.
첫째로 어디에 부호 비트를 붙여야 하는지가 명확하지 않다. 오른쪽에? 왼쪽에? 초기 컴퓨터들은 두 가지를 다 시도해 보았다.
둘째로 부호와 크기 표현법의 덧셈기는 부호를 결정하기 위해 한 단계가 더 필요하다. 왜냐하면 최종 부호가 무엇이 될지 미리 알 수 없기 때문이다.
마지막으로 부호 비트가 따로 붙기 때문에 양의 0과 음의 0을 갖는다는 점이다. 이것이 부주의한 프로그래머에게는 문제를 야기할 수 있다.
이런 단점 때문에 부호와 크기 표현법은 곧 쓰지 않게 되었다.
더 좋은 대안을 찾는 가운데, 작은 수에서 큰 수를 뺄 때 부호없는 수의 경우에 결과가 어떻게 될까라는 의문이 대두되었다. 그 답은 0들로 시작되는 수에서 빌림을 수행하게 되어 그 결과는 1들로 시작하는 수가 된다는 것이다.
확실한 대안이 없는 상황에서 최종 결론은 하드웨어를 간략하게 하는 표현방식을 택하는 것이었다. 그 결과 0들이 앞에 나오면 양수이고 1들이 앞에 나오면 음수가 되었다.
부호있는 이진수를 표현하는 이러한 방식은 2의 보수(two’s complement) 표현법이라고 불린다.
전체의 절반인 양수 0부터 2,147,483,647(2311)2,147,483,647(2^{31} - 1) 까지는 앞서와 같은 표현법을 사용한다.
그 다음 비트 패턴(1000…000)은 가장 큰 음수 2,147,483,647(231)-2,147,483,647(-2^{31})을 나타내고, 계속 작은 음수가 이어져서 2,147,483,647-2,147,483,647부터 1-1까지 감소한다.
2의 보수에는 대응되는 양수가 없는 음수 -2,147,483,648이 존재한다. 이러한 불균형이 부주의한 프로그래머에게는 역시 골칫거리지만, 기존의 부호와 크기 표현법은 프로그래머와 하드웨어 설계자 모두에게 문제였었다. 결과적으로 모든 컴퓨터는 부호 있는 수를 2의 보수로 표현하고 있다.
2의 보수 표현에서 모든 음수는 MSB가 1이라는 장점이 있다. 따라서 하드웨어가 양수인지 음수인지 알아보려면 MSB만 검사하면 된다(0은 양수로 취급). 그러므로 MSB를 부호 비트(sign bit)라고 부른다.
부호 비트의 역할을 이해하면 비트 값에 2의 멱수를 곱한 값으로 32비트의 양수와 음수를 모두 표현할수 있다.
(x31×231)+(x30×230)+(x29×229)+...+(x1×21)+(x0×20)(x_{31} \times -2^{31}) + (x_{30} \times 2^{30}) + (x_{29} \times 2^{29}) + ... + (x_{1} \times 2^{1}) + (x_{0} \times 2^{0})
부호 비트에는 231-2^{31}을 곱하고 나머지 비트들은 각각의 위치에 해당하는 양의 기수를 곱한다.
부호 없는 수의 연산 결과가 오버플로를 발생시킬 수 있는 것처럼 2의 보수 연산에서도 오버플로가 발생한다. 무한히 많은 비트 수로 표현한다면 왼쪽에 무수히 나타날 비트와 실제 이진 비트 패턴의 제일 왼쪽 비트가 서로 다를 때(즉 부호 비트가 틀렸을 때) 오버플로가 발생한 것이다.
결과가 음수인데 MSB가 0이되거나 양수인데 1이 되는 경우이다.
부호 있는 수와 부호 없는 수는 산술연산 뿐만 아니라 적재 명령어와도 상관이 있다. 부호있는 적재의 경우 레지스터의 남는 곳을 채우기 위해 부호를 반복하여 복사–부호 확장(sign extension)이라고 불림– 하게 된다.
이것의 목적은 레지스터 내부에 정확한 값을 적재하기 위함이다. 부호없는 적재의 경우에는 단순히 데이터의 왼쪽을 0으로 채운다.
32비트 레지스터에 32비트 워드를 적재할 경우에는 논의할 여지가 있다. 부호있는 적재와 부호없는 적재는 동일하다.
MIPS는 바이트 적재를 위해 두 개의 명령어를 제공한다. lb(load byte) 명령어는 바이트를 부호 있는 수로 간주하고 남은 23비트를 부호확장하여 채운다. 반면 lbu(load byte unsigned) 명령어는 부호 없는 정수를 다룬다.
C 프로그램은 바이트를 부호 있는 정수로 다루기보다는 대부분의 경우에 문자를 표시하기 위해 사용하므로 lbu 명령어는 실제적으로 바이트 적재를 위해서만 사용된다.
앞서 논의한 숫자와 달리, 메모리 번지는 자연스럽게 0에서 시작해서 가장 큰 주소까지 이어진다. 음수 주소는 의미가 없다.
따라서 프로그램이 양수도 될 수 있고 음수도 될 수 있는 수를 다루려고 할 때도 있고, 양수 값만 갖는 수를 다루고자 할 때도 있다.
어떤 프로그래밍 언어에는 이러한 구별이 잘 반영되어 있다. 예컨대 C언어에서는 전자를 정수(integer)라고 부르며 후자를 부호없는 정수(unsigned integer)라고 부른다.
2의 보수 연산에서 사용할 수 있는 두 가지 빠른 계산법을 알아보자.
첫 번째는 2의 보수 이진수를 역부호화하는 빠른 방법이다. 모든 0을 1로 1은 0으로 바꾸고 거기에 1을 더한다. 이 방식은 원래 수와 모든 비트를 역전시킨 수의 합은 -1이라는데 기초하고 있다.
두 번째 빠른 계산법은 n비트로 표현된 이진수를 n비트보다 큰 수로 바꾸는 방법이다.
예컨대 load, store, branch, add 그리고 set on less then 명령어의 수치 필드에는 2의 보수 16비트 이진수가 들어가므로, 32,768(215)-32,768(-2^{15})에서 32,767(2151)32,767(2^{15}-1) 까지 값을 표현할 수 있다.
이 값을 32비트 레지스터와 더하려면 컴퓨터는 16비트 수를 같은 값의 32비트 수로 변환하여야 한다. 빠른 방법은 16비트 이진수의 최상위 비트(부호 비트)를 취해서 비어 있는 왼쪽 부분에 채우고, 원래의 16비트 값은 32비트 수의 오른쪽 부분에 그대로 복사하는 것이다.
이러한 방법을 보통 부호확장(sign extension)이라고 부른다. 2의 보수법으로 표현된 양수가 실제로는 왼쪽에 끝없이 많은 0을 가지고 있고, 음수는 끝없이 많은 1을 가지고 있기 때문이 이 방식이 가능한 것이다. 수를 나타내는 이진 비트 패턴은 하드웨어 폭에 맞추기 위해 왼쪽의 비트를 숨기고 있는데, 부호확장은 단순히 이들 중 약간만을 복원하는 것이라고 생각할 수 있다.

명령어의 컴퓨터 내부 표현

명령어도 컴퓨터 내부에서는 높고 낮은 전기 신호의 연속으로 저장되므로 숫자로 표현할 수 있다. 실제로 명령어의 각 부분을 숫자로 볼 수 있으며, 이 숫자들을 나란히 늘어놓으면 명령어가 된다.
레지스터가 명령어에서 참조가 되기 때문에 레지스터 이름을 숫자로 매핑하는 규칙이 있어야 하는데 MIPS에서는 레지스터 $s0에서 $s7까지는 레지스터 번호 16에서 23번까지로, $t0부터 $t7까지는 번호 8에서 15번까지 매핑한다.
(예제 생략)
위 예제에서 보인 레이아웃을 명령어 형식(instruction format)이라고 한다. MIPS 명령어의 길이는 데이터 워드와 마찬가지로 32비트이다.
‘간단하게 하기 위해서는 규칙적인 것이 좋다’라는 설계 원칙에 따라 모든 MIPS 명령어는 예외 없이 32비트이다.
어셈블리 언어와 구별하기 위해 명령어를 숫자로 표현한 것을 기계어(machine language)라고 하고, 이런 명령어들의 시퀀스를 기계 코드(machine code)라 한다.
당분간 긴 이진수를 읽고 쓰는 지루한 작업이 불가피할 것으로 보인다. 하지만 쉽게 이진수로 바꿀 수 있는 다른 진법 체계를 사용해서 이 문제를 해결할 수 있다.
거의 모든 컴퓨터의 데이터 길이는 4의 배수이므로 16진수(hexadecimal)가 많이 사용된다.
기수 16은 2의 멱승이므로 이진수 4비트를 16진수 숫자 하나로 쉽게 바꿀 수 있다. 16진수를 이진수로 바꾸는 것도 마찬가지다.
아래 그림 2.4는 16진수와 이진수 간의 변환을 보여준다.

MIPS 명령어의 필드

표시하기 쉽게 MIPS 명령어의 각 필드에는 다음과 같은 이름이 붙어 있다.
각 이름의 의미는 다음과 같다.
op: 명령어가 실행할 연산의 종류로서 연산자(opcode)라고 부른다.
rs: 첫 번째 근원지(source) 피연산자 레지스터
rt: 두 번째 근원지 피연산자 레지스터
rd: 목적지(destination) 레지스터. 연산 결과가 기억된다.
shamt: 자리이동(shift)량 (2.6절에서 설명한다)
funct: 기능(function). op 필드에서 연산의 종류를 표시하고 funct 필드에서는 그중의 한 연산을 구체적으로 지정한다. 기능 코드(function code)라고 부르기도 한다.
이것보다 필드 길이가 더 길어야 하는 경우에는 문제가 생길 수 있다.
예컨대 lw 명령어는 레지스터 필드 두 개와 상수 필드 하나가 필요하다. 만일 위의 5비트 필드 중 하나를 주소로 쓴다면 25=322^{5} = 32 보다 작은 값만을 사용할 수 있다.
이 필드는 큰 배열이나 자료구조에서 한 원소를 선택하는데 사용된다. 따라서 32보다 큰 값이 필요한 경우가 많으므로 5비트 필드로는 부족하다.
이런 문제 때문에 모든 명령어의 길이를 같게하고 싶은 생각과 명령어 형식을 한 가지로 통일하고 싶은 생각 사이에서 충돌이 생긴다. 여기서 마지막 하드웨어 설계 원칙이 도출된다.
설계 원칙 3: 좋은 설계에는 적당한 절충이 필요하다.
MIPS 설계자들이 택한 절충안은 모든 명령어의 길이를 같게 하되, 명령어 종류에 따라 형식은 다르게 하는 것이었다.
예컨대 위의 명령어 형식은 R 타입 또는 R형식(여기서 R은 Register를 뜻한다)이라 하는데, 이것만으로는 불충분하기 때문에 I 타입 또는 I 형식(여기서 I는 immediate)라는 두 번째 명령어 형식을 만들었다.
I 타입은 수치 연산과 데이터 전송 명령어에서 사용되며 그 모양은 다음과 같다.
16비트 주소를 사용하므로 lw 명령은 베이스 레지스터 rs에 저장된 주소를 기준으로 ±215=±32,768\pm 2^{15} = \pm 32,768 바이트(±213=±8192\pm 2^{13} = \pm 8192)를 지정할 수 있다.
마찬가지로 addi에서 사용할 수 있는 상수는 ±215\pm 2^{15}보다 더 클 수 없다. 이 명령어 형식에서는 레지스터를 32개 이상 사용하기 어렵다. 그렇게 되면 rs와 rt 필드가 더 커져서 한 워드에 모든 정보를 담을 수 없게 된다.
2.3절의 적재 명령을 보자.
lw  $t0, 32($s3)  # Temporary reg $t0 gets A[8]
Plain Text
여기서 rs 필드에는 19($s3의 번호), rt 필드에는 8($t0), 주소 필드에는 32가 들어간다. 이 명령어에서는 rt 필드의 의미가 바뀌어 적재 결과가 들어갈 목적지 레지스터 번호를 표시하는 것으로 바뀌었다.
명령어 형식이 여러 가지가 되면 하드웨어가 복잡해지지만 모든 형식을 유사하게 함으로써 복잡도를 낮출 수 있었다.
예컨대 R타입과 I타입의 처음 세 필드는 이름과 크기가 같고, I 타입의 네 번째 필드 길이는 R 타입의 나머지 세 필드 길이를 더한 것과 같게 하였다.
명령어 형식을 어떻게 구분하는지 궁금해하는 사람이 많을 텐데, 첫 번째 필드의 값을 보면 형식을 알 수 있다.
형식별로 op 필드가 가질 수 있는 값들이 다르므로, 하드웨어는 op 필드를 보고 명령어의 오른쪽 절반을 필드 세 개로 볼 것인지(R 타입), 필드 하나로 볼 것인지(I 타입) 결정한다.
그림 2.5는 이제까지 설명한 MIPS 명령어의 각 필드 내용을 보여준다.
모든 명령어의 길이를 같게 하려는 욕망과 더 많은 레지스터를 가지려는 욕망이 충돌을 일으킨다. 레지스터 개수를 늘리게 되면 명령어 형식에서 각각의 레지스터 필드는 적어도 1비트가 더 필요하게 된다.
이 같은 제한조건과 ‘작은 것이 더 빠르다’라고 하는 설계 원칙 때문에 오늘날 대부분의 명령어 집합은 16개 또는 32개의 범용 레지스터를 갖고 있다.
그림 2.6에서 이절에서 설명한 MIPS 어셈블리 언어를 요약하였다. 서로 관련이 있는 명령어의 이진수 표현을 유사하게 하면 하드웨어 설계가 간단해짐을 4장에서 보게될 것이다. 이것은 MIPS 구조가 갖는 규칙성의 또 다른 예이다.
오늘날 컴퓨터는 두 가지 중요한 원리에 바탕을 두고 있다.
1.
명령어는 숫자로 표현된다.
2.
프로그램은 메모리에 기억되어 있어서 숫자처럼 읽고 쓸 수 있다.
이것이 내장 프로그램의 개념이다. 이 개념을 발명한 덕택에 컴퓨터가 눈부시게 발전할 수 있었다. 그림 2.7은 내장 프로그램의 장점을 보여준다.
메모리에는 편집기가 편집 중인 소스 코드, 컴파일된 기계어 프로그램, 실행 프로그램이 사용하는 텍스트 데이터, 심지어는 기계어를 생성하는 컴파일러까지도 기억될 수 있다.
명령어를 숫자처럼 취급하게 된 결과, 프로그램이 이진수 파일 형태로 판매되게 되었다. 이것이 상업적으로는 만약 기존 명령어 집합과 호환성이 있다면 다른 컴퓨터의 소프트웨어를 물려받을 수 있다는 의미를 갖는다. 이러한 ‘이진 호환성(binary compatibility)’ 문제 때문에 상업적으로 살아남는 명령어 집합 구조는 극히 소수로 집약된다.

논리연산 명령어

초기 컴퓨터는 워드 전체에 대한 처리에만 관심을 가졌지만, 워드 내 일부 비트들에 대한 연산, 심지어는 개개 비트에 대한 연산도 필요하다는 것이 곧 명백해졌다. 워드 내에 8비트로 저장된 문자를 검사하는 작업이 이러한 연산의 한 예이다.
뒤를 이어 비트들을 워드로 묶는(packing) 작업과 워드를 비트 단위로 나누는 (unpacking) 작업을 간단하게 하는 명령어들이 프로그래밍 언어와 명령어 집합에 추가되었다. 이러한 명령어들을 논리연산 명령어라 부른다.
그림 2.8은 C, Java와 MIPS의 논리 연산을 보여준다.
(shift, and, or, not 연산 예 생략)

판단을 위한 명령어

컴퓨터가 단순한 계산기와 다른 점은 판단 기능이 있다는 것이다. 입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있다. 프로그래밍 언어에서는 보통 if 문장으로 (때에 따라서는 go to문과 레이블을 함께 써서) 판단 기능을 표현한다.
처음 볼 명령어는
beg register1, register2, L1
Plain Text
인데 register1과 register2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다. beq는 branch if equal을 의미한다.
또 다른 예는
bne register1, register2, L1
으로서, register1과 register2의 값이 같지 않으면 L1으로 가라는 뜻이다. bne는 branch if not equal을 의미한다. beq와 bne 두 명령어를 조건부 분기(conditional branch)라 부른다.

예제) If-then-else를 조건부 분기로 번역

다음 코드에서 f, g, h, i, j는 변수이고, 각각은 레지스터 $s0부터 $s4까지에 해당한다. 아래의 C 언어 if 문장을 컴파일한 코드는 무엇인가?
if (i == j) f = g + h; else f = g - h;
Plain Text
아래 그림 2.9는 MIPS 코드가 해야 할 일을 보여주는 순서도이다. 첫 번째 부분은 같은지 비교하는 것이므로 beq로 번역하면 될 것처럼 보인다. 그러나 실제로는 조건을 반대로 검사해서 then 부분을 건너뛰게 하는 것이 더 효율적이므로 bne를 사용하자. (레이블 Else는 나중에 정의한다)
bne $s3, $s4, Else # go to Else if i ≠ j
Plain Text
다음 치환문은 연산 하나를 실행하는 것이므로 피연산자가 모두 레지스터에 있다는 명령어 하나로 번역된다.
add $s0, $s1, $s2  # f = g + h (skipped if i ≠ j)
Plain Text
이 명령을 실행한 후에는 if 문장의 끝 부분으로 가야 한다. 이것은 무조건 분기(unconditional branch)라는 새로운 종류의 분기 명령으로 해결한다. 이 명령어는 프로세서에게 항상 분기하라고 말한다. MIPS에서는 이 같은 명령어에 jump라는 이름을 붙이고 간략하게 j로 사용한다. (레이블 Exit는 나중에 정의한다)
j Exit  # go to exit
Plain Text
else 부분의 치환문도 역시 명령어 하나로 번역된다. 단 이 명령어에는 Else 라는 레이블을 붙여야 한다. 그리고 이 명령어 뒤에는 if-then-else 문장의 끝을 표시하는 Exit란 레이블을 둔다.
Else:sub $s0, $s1, $s2  # f = g - h (skipped if i = j) Exit:
Plain Text
어셈블러가 컴파일러나 어셈블리 언어 프로그래머가 지겨운 분기 주소 계산을 하지 않도록 해준다는 것을 기억하라. 이는 마치 적재와 저장 명령어를 위해 데이터 주소를 계산해 주는 것과 똑같다. (2.11절 참조)
컴파일러가 소스 프로그램에는 없는 분기 명령이나 레이블을 만들어 내는 경우가 많이 있다. 필요한 레이블과 분기 명령을 일일이 표시하지 않아도 되는 것이 상위 수준 프로그래밍 언어의 장점 중 하나이며, 상위 수준 언어를 사용하면 코딩이 더 빨라지는 이유이기도 하다.

순환문

판단 기능은 둘 중의 하나를 선택하는 데도 (if 문장 사용) 중요하지만 계산의 반복에도(순환문 사용) 중요하다. 두 경우 모두 같은 어셈블리 명령어가 사용된다.

예제) while 순환문의 번역

다음과 같은 전형적인 C 순환문이 있다.
while (save[i] == k) i += 1;
Plain Text
i와 k가 레지스터 $s3과 $s5에 할당되었고 배열 save의 시작 주소가 $s6에 저장되어 있다고 할 때 위 C 문장에 해당하는 MIPS 어셈블리 코드를 보여라
첫 번째로 할 일은 save[i]를 임시 레지스터로 가져오는 것이다. save[i]를 임시 레지스터에 적재하려면 먼저 그 주소를 구해야 한다. 바이트 주소 문제 때문에 인덱스 i에 4를 곱해서 save의 시작 주소에 더해야 주소가 만들어진다. 2비트씩 좌측 자리로 이동을 하면 4를 곱한 것과 같으므로 (2.6절 참조) s11 연산을 사용할 수 있다. 순환의 끝에서 처음 명령어로 되돌아갈 수 있도록 Loop라는 레이블을 추가한다.
Loop: s11  $t1, $s3, 2  # Temp reg $t1 = i * 4
Plain Text
save[i]의 주소를 계산하기 위해 $t1 값에다 $s6에 있는 save의 베이스 주소 값을 더할 필요가 있다.
add $t1, $t1, $s6  # $t1 = address of save[i]
Plain Text
이제 이 주소를 이용해서 save[i]를 임시 레지스터에 넣을 수 있다.
lw $t0, 0($t1)  # Temp reg $t0 = save[i]
Plain Text
다음은 반복 검사를 수행해서 save[i] ≠ k이면 순환에서 빠져나가는 부분이다.
bne $t0, $s5, Exit  # go to Exit if save[i] ≠ k
Plain Text
다음은 i에 1을 더하는 명령어이다.
addi $s3, $s3, 1  # i = i + 1
Plain Text
순환문의 끝에서는 맨 앞의 while 조건 검사로 되돌아가야 한다. 그리고 이 명령의 다음에 Exit 레이블을 두면 번역이 끝난다.
j Loop  # go to loop Exit:
Plain Text
이렇게 분기 명령어로 끝나는 명령어 시퀀스는 컴파일러에게 특히 중요한 의미가 있기 때문에 기본 블록(basic block)이라는 별칭이 붙어 있다.
기본 블록이란 분기 명령을 포함하지 않으면(맨 끝에는 있을 수 있다) 분기 목적지나 분기 레이블도 없는(맨 앞에 있는 것은 허용된다) 시퀀스이다.
컴파일의 초기 단계 작업 중 하나는 프로그램을 기본 블록으로 나누는 일이다.
같은지 다른지 비교하는 것이 아마도 가장 흔한 검사이겠지만, 경우에 따라서는 두 변수 간의 대소 비교가 필요할 때도 있다.
예컨대 for 순환문에서 인덱스 변수값이 0보다 작은지 검사할 때가 있다. MIPS에서는 두 개의 근원지 레지스터의 값을 비교한 후 목적지 레지스터 값을 설정하는 명령어가 있다.
즉 첫 번째 근원지 레지스터 값이 두 번째 근원지 레지스터의 값보다 작으면 목적지 레지스터 값을 1로 아니면 0으로 하는 명령어로 이런 일을 처리한다.
이 명령어를 slt(set on less than)라 한다.
slt $t0, $s3, $s4  # $t0 = 1 if $s3 < $s4
Plain Text
는 레지스터 $s3의 값이 레지스터 $s4의 값보다 작으면 레지스터 $t0를 1로 아니면 0으로 하라는 명령이다.
상수 피연산자는 비교에서도 많이 이용된다. 따라서 상수 피연산자를 갖는 slt 명령어가 필요하다. 레지스터 $s2가 상수 10보다 작은지 검사하려면 다음과 같이 쓰면 된다.
slti $t0, $s2, 10  # $t0 = 1 if $s2 < 10
Plain Text
MIPS 컴파일러는 slt, slti, beq, bne와 레지스터 $zero에 있는 상수 0을 이용해서 모든 비교 조건(같다, 다르다, 작다, 작거나 크다, 크다, 크거나 같다)을 만들 수 있다. (레지스터 $zero는 0번 레지스터를 가리킨다)
하드웨어는 간단해야 좋다는 von Neumann의 경고를 준수하여 MIPS 구조에서는 구현하기에 너무 복잡한 blt(branch on less than) 명령어를 제외시켰다.
이 명령을 구현하면 클럭 속도가 느려지거나 이 명령 실행에 별도의 클럭 사이클이 더 필요하게 된다. 그러므로 빠른 명령어 두 개를 사용하는 것이 더 유리하다.
비교 명령은 부호 있는 수와 부호 없는 수 사이의 이분법도 다루어야 한다. 어떤 때는 MSB가 1인 수가 음수를 나타내며, 이때는 당연히 MSB가 0인 어떤 양수보다도 작다. 하지만 부호없는 정수의 경우에는 MSB가 1인 수가 MSB가 0인 어떤 수보다도 더 크다.
MIPS는 이 두가지 경우를 처리할 수 있도록 set on less than의 두 가지 유형을 제공하고 있는데 slt(set on less than)와 slti(set on less than immediate)는 부호 있는 정수에, sltu(set on less than unsigned)와 sltiu(set on less than immediate unsigned)는 부호없는 정수에 사용한다.
(예제 생략)
부호 있는 정수를 부호없는 정수처럼 다루면 0 ≤ x < y 검사 비용을 낮출 수 있는데, 이 검사는 인덱스가 배열의 함계를 벗어났는지 확인하는 검사에 딱 맞는다.
핵심은 2의 보수로 표현된 음수가 부호없는 정수에서의 큰 수처럼 보인다는 것이다.
즉 2의 보수 표현에서는 MSB가 부호 비트이지만 부호 없는 정수에서는 큰 값을 의미한다. 따라서 부호없는 비교 x < y를 하면 x가 y보다 작은지뿐만 아니라 x가 음수인지도 검사할 수 있다.
(예제 생략)

Case/Switch 문장

대부분의 프로그래밍 언어는 특정 변수의 값에 따라 여러 가지 중 하나를 선택하는 case나 switch 문장을 갖고 있다. switch를 구현하는 가장 간단한 방법은 계속적인 조건 검사를 통해 switch를 if-then-else의 연속으로 바꾸는 것이다.
그러나 여러 코드의 시작 주소를 표로 만들면 더 효율적으로 구현할 수 있다. 이때 프로그램은 점프 주소 테이블(jump address table) 또는 점프 테이블(jump table)의 인덱스만 계산해서 해당 루틴으로 점프할 수 있다.
점프 테이블은 프로그램상의 레이블에 해당하는 주소를 저장하고 있는 배열이다. 프로그램은 점프 테이블의 적당한 주소를 레지스터에 적재한 후 레지스터의 주소를 사용하여 점프한다.
MIPS에는 이런 상황을 다루기 위해 jr(jump register)이라고 하는 명령어를 갖고 있는데 이 명령어는 레지스터에 명시된 주소로 무조건 점프한다.
C나 Java 같은 프로그래밍 언어에는 많은 판단문과 순환문이 있지만, 그 명령어 집합 계층에서 이것을 구현하는 기반은 조건부 분기이다.

하드웨어의 프로시저 지원

프로시저(procedure)나 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중의 하나이다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있게 해준다.
인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다.
Java에서 프로시저에 해당하는 것을 2.13절에서 설명하겠지만, Java도 C가 필요로 하는 모든 것을 필요로 한다.
프로시저는 소프트웨어에서 추상화를 구현하는 방법이다.
프로시저는 스파이에 비유할 수 있다. 스파이는 비밀 계획을 지니고 출발해서 필요한 자원을 획득하여 임무를 완수하고, 흔적을 없앤 후 원하는 결과를 가지고 출발 장소로 되돌아 온다.
지정된 임무를 수행하는 것 외에 다른 것은 아무것도 건드리지 말아야 한다.
또 스파이는 알 필요가 있는 일만 알기 때문에 자기의 상관에 대해서는 어떠한 가정도 할 수 없다.
마찬가지로 프로그램이 프로시저를 실행할 때도 다음과 같이 여섯 단계를 거친다.
프로시저가 접근할 수 있는 곳에 인수를 넣는다.
프로시저로 제어를 넘긴다.
프로시저가 필요로 하는 메모리 자원을 획득한다.
필요한 작업을 수행한다.
호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다.
프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.
앞서 언급한 바와 같이 레지스터는 데이터를 저장하는 가장 빠른 장소이므로 가능한 많이 사용하는 것이 바람직하다. 그러므로 MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라 레지스터 32개를 할당한다.
$a0-$a3: 전달할 인수를 가지고 있는 인수 레지스터 4개
$v0-$v1: 반환되는 값을 갖게 되는 값 레지스터 2개
$ra: 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개
MIPS 어셈블리 언어는 레지스터를 할당할 뿐 아니라 프로시저를 위한 명령어도 제공한다. 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령으로 jal 명령어(jump-and-link instruction)라 부른다.
jal ProcedureAddress
Plain Text
이름에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다.
레지스터 $ra(레지스터 31)에 기억되는 이 링크를 복귀 주소(return address)라고 부른다. 한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요하다.
이러한 것을 지원하기 위하여 MIPS는 case 문 구현에 사용했던 jr(jump register) 명령을 이용한다. 이 명령은 레지스터에 저장된 주소로 무조건 점프하라는 뜻이다.
jr $ra
Plain Text
위 명령어는 레지스터 $ra에 저장되어 있는 주소로 점프라하는 뜻이다. 이것이 바로 우리가 원하는 것이다. 호출 프로그램(caller)은 $a0-$a3에 전달할 인수 값을 넣은 후 jal X 명령을 이용해서 프로시저 X[피호출 프로그램(callee)이라 부른다]로 점프한다.
피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0-$v1에 넣은 후 jr $ra 명령을 실행하여 복귀한다.
내장 프로그램 개념은 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 필요로 한다. 이 레지스터의 이름은 명령어 주소 레지스터(instruction address register)라고 하는 것이 타당하겠지만, 역사적인 이유로 보통 프로그램 카운터(program counter)라고 부른다.
MIPS에서는 약어를 사용하여 PC라고 부른다.
jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC+4를 레지스터 $ra에 저장한다.

더 많은 레지스터의 사용

컴파일러가 프로시저를 번역하는데 인수 레지스터 4개, 결과 값 레지스터 2개만으로는 부족한 경우를 생각해 보자. 프로시저 호출이 다른 부분에 영향을 미쳐서는 안 되므로, 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야 한다.
이 상황은 2.3절의 마지막 ‘하드웨어/소프트웨어 인터페이스’에서 설명한 레지스터 스필링이 필요한 경우의 한 예가 된다.
레지스터 스필링에 이상적인 자료구조는 스택(stack)이다. 스택은 나중에 들어간 것이 먼저 나오는 큐이다.
스택에는 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요하다.
이 스택 포인터(stack pointer)는 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될 때마다 한 워드씩 조정된다.
MIPS 소프트웨어는 스택 포인터를 위해 레지스터 29를 할당해 놓고 있는데 이름은 당연히 $sp이다.
스택에 데이터를 넣는 작업을 푸시(push), 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.
역사적 선례에 따라 스택은 높은 주소에서 낮은 주소 쪽으로 성장한다. 그러므로 스택에 푸시를 할 때는 스택 포인터 값을 감소시켜야 하고, 스택에서 팝을 할 때는 스택 포인터 값을 증가시켜야 한다.

예제) 다른 프로시저를 호출하지 않는 C 프로시저의 컴파일

2.2 절의 두 번째 예제를 C 프로시저로 바꾸면 다음과 같다.
int leaf_example(int g, int h, int i, int j) { int f; f = (g + h) - (i + j); return f; }
Plain Text
위 프로그램을 번역한 MIPS 어셈블리 코드를 보여라
인수 g, h, i, j는 인수 레지스터 $a0, $a1, $a2, $a3에 해당하고 f는 $s0에 해당한다. 컴파일된 프로그램은 다음과 같은 프로시저 레이블로부터 시작된다.
leaf_example:
Plain Text
다음 단계는 프로시저가 사용할 레지스터 값을 저장하는 것이다. 프로시저 본문의 C 치환문은 2.3절 예제와 같으므로 임시 레지스터 두 개를 사용한다. 따라서 저장해야 할 레지스터는 $s0, $t0, $t1 세 개이다. 스택에 세 워드를 저장할 자리를 만든 후 값을 저장한다.
addi $sp, $sp, -12  $ adjuststack to make room for 3 items sw $t1, 8($sp) # save register $t1 for use afterwards sw $t0, 4($sp) # save register $t0 for use afterwards sw $s0, 0($sp) # save register $s0 for use afterwards
Plain Text
그림 2.10은 프로시저 호출 전후와 프로시저 실행 중의 스택 상태를 보여준다. 프로시저 본문은 2.3절 예제에서와 같이 명령어 세 개로 표현된다.
add $t0, $a0, $a1  # register $t0 contains g + h add $t1, $a2, $a3 # register $t1 contains i + j sub $s0, $t0, $t1 # f = $t0 - $t1. which is (g + h) - (i + j)
Plain Text
계산 결과 f를 보내주기 위해 f를 결과 값 레지스터에 복사한다.
add $v0, $s0, $zero  # returns f ($v0 = $s0 + 0)
Plain Text
호출 프로그램으로 되돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구한다.
lw $s0, 0($sp)  # restore register $s0 for caller lw $t0, 4($sp)  # restore register $t0 for caller lw $t1, 8($sp)  # restore register $t1 for caller addi $sp, #sp, 12  # adjust stack to delete 3 items
Plain Text
이 프로시저는 복귀 주소를 사용하는 jr 명령으로 끝난다.
jr $ra  # jump back to calling routine
Plain Text
위의 예제에서 임시 레지스터를 사용했는데, 임시 레지스터 값도 저장했다가 원상 복구해야 한다고 가정하였다. 그러나 사용하지도 않는 레지스터 값을 쓸데 없이 저장했다 복구하는 일이 생길 수 있다. 특히 임시 레지스터에 대해 이런 일이 발생할 가능성이 크다. 이를 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈다.
$t0-$t9: 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터
$s0-$s7: 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 변수 레지스터 8개(피호출 프로그램이 이 레지스터를 사용하면 원래 값을 저장했다가 원상 복구한다)
이런 간단한 관례를 정함으로써 레지스터 스필링을 많이 줄일 수 있다. 위 예에서 $t0와 $t1 값이 호출 전후에 같은 값을 유지할 필요가 없기 때문에 저장 명령 두 개와 적재 명령 두 개를 없앨 수 있다.
그러나 $s0는 피호출 프로그램 입장에서는 호출 프로그램이 이 값을 필요로 할 것이라고 가정하기 때문에 저장했다가 원상 복구해야 한다.

중첩된 프로시저

다른 프로시저를 호출하지 않는 프로시저를 말단(leaf) 프로시저라 한다. 말단 프로시저만 있다면 일이 쉽겠지만 실제로는 그렇지 못하다. 스파이가 다른 스파이를 고용해서 일의 일부를 맡기고, 그 스파이는 또 다른 스파이를 고용할 수도 있는 것이다.
프로시저도 다른 프로시저를 호출할 수 있다. 심지어는 자기 자신을 호출하는 재귀(recursive) 프로시저도 있다. 프로시저에서 레지스터를 사용할 때 조심해야 하는 것처럼 말단 프로시저가 아닌 프로시저를 호출할 때는 더욱 조심해야 한다.
예컨대 주 프로그램이 인수값 3을 가지고 프로시저 A를 호출했다고 가정하자.
이때 레지스터 $a0에 3을 넣고 jal A 명령을 실행할 것이다. 프로시저 A가 다시 인수 7(이것도 역시 $a0에 들어간다)을 가지고 jal B를 통해 프로시저 B를 호출했다고 하자.
아직 A가 다 끝난 것이 아니기 때문에 레지스터 $a0 사용에서 충돌이 발생한다. 마찬가지로 레지스터 $ra에 지금은 B의 복귀주소가 있으므로 $ra의 복귀 주소에 대해서도 충돌이 생긴다. 이러한 문제를 예방하기 위한 조치를 취하지 않는다면 충돌로 인해 프로시저 A가 호출 프로그램으로 돌아가지 못하게 된다.
한 가지 방법은 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다. 호출 프로그램은 인수 레지스터($a0-$a3)와 임시 레지스터($t0-$t9) 중 프로시저 호출 후에도 계속 사용해야 하는 것은 모두 스택에 넣는다.
피호출 프로그램은 복귀 주소 레지스터 $ra와 저장 레지스터($s0-$s7) 중에서 피호출 프로그램이 사용하는 레지스터 모두 저장한다. 스택 포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다.
복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상복구하고 이에 맞추어 스택 포인터를 다시 조정한다.

예제) 재귀 프로시저의 컴파일

n 계승을 계산하는 다음 재귀 프로시저에 해당하는 MIPS 어셈블리 코드를 보여라
int fact(int n) { if (n < 1) return (1); else return (n * fact(n-1)); }
Plain Text
인수 n은 인수 레지스터 $a0에 해당한다. 번역된 프로그램은 프로시저 레이블로 시작하며, 뒤이어 복귀 주소와 $a0를 스택에 저장하는 명령어가 나온다.
fact: addi $sp, $sp, -8 # adjust stack for 2 items sw $ra, 4($sp) # save the return address sw $a0, 0($sp) # save the argument n
Plain Text
fact가 처음 호출되었을 때 sw는 fact를 호출한 프로그램의 주소를 저장한다. 다음은 n이 1보다 작은지 검사해서 n ≥ 1이면 L1으로 가게 하는 명령어들이다.
slti $t0, $a0, 1  # test for n < 1 beq $t0, $zero, L1 # if n >= 1, go to L1
Plain Text
n이 1보다 작으면 1을 결과 레지스터에 넣는다. 이때 0에다 1을 더해서 $v0에 넣는다. 복귀하기 전에 스택에 저장된 값 두 개를 버리고 복귀 주소로 점프한다.
addi $v0, $zero, 1  # return 1 addi $sp, $sp, 8 # pop 2 items off stack jr $ra # return to caller
Plain Text
스택에서 값 두 개를 꺼내서 $a0와 $ra에 넣을 수도 있으나, n이 1보다 작을 때 $a0와 $ra는 변하지 않으므로 그럴 필요가 없다. n이 1보다 작지 않으면, 인수 n을 감소시키고 이 감소된 값으로 다시 fact를 호출한다.
L1: addi $a0, $a0, -1  # n >= 1: argument gets (n-1) jal fact # call fact with (n-1)
Plain Text
다음은 호출한 프로그램으로 되돌아가는 부분이다. 먼저 스택 포인터를 사용해서 이전의 복귀 주소와 인수 값을 복구한다.
lw $a0, 0($sp)  # return from jal: restore argument n lw $ra, 4($sp) # restore the return address addi $sp, $sp, 8 # adjust stack pointer to pop 2 items
Plain Text
다음으로 인수 $a0와 결과 값 레지스터의 현재 값을 곱해서 $v0에 넣는다. 곱셈 명령어는 3장에서 소개되지만 우선 설명없이 사용하기로 하자.
mul $v0, $a0, $v0  # return n * fact(n-1)
Plain Text
마지막으로 복귀 주소를 이용해 되돌아간다.
jr $ra  # return to the caller
Plain Text
C 변수는 기억장치의 한 장소에 해당한다. 여기에 기억된 내용을 어떻게 해석하는가는 데이터형(type)과 저장유형(storage class)에 따라 달라진다. 예컨대 정수형, 문자형 등이 있다.
C에는 자동(automatic)과 정적(static) 두 가지 저장 유형이 있다.
자동 변수는 프로시저 내에서만 정의되는 것으로 프로시저가 종료되면 없어진다.
정적 변수는 프로시저로 들어간 후나 프로시저에서 빠져나온 후에도 계속 존재한다.
모든 프로시저 외부에서 선언된 C 변수는 정적 변수로 간주되며, static이라는 키워드를 사용해서 선언된 변수도 마찬가지다. 그 외는 모두 자동 변수이다.
정적 변수에 대한 접근을 단순화하기 위해 MIPS는 전역 포인터(global pointer, $gp)라 불리는 레지스터를 예약해 놓고 있다.
아래 그림 2.11은 프로시저 호출 전후의 값 보존 관계를 보여준다. 여러 가지 방버븡로 스택을 보존하여 호출 프로그램이 스택에 저장한 값과 같은 값을 꺼낼 수 있게 보장하고 있음에 주목하라.
피호출 프로그램이 $sp보다 위쪽에는 값을 쓰지 못하게 함으로써 $sp 윗부분의 스택을 원상태로 유지한다.
$sp 자체는 뺀 값 만큼을 피호출 프로그램이 도로 더해서 원래 값을 유지하고, 다른 레지스터는 (만일 프로시저 내에서 사용되면) 스택에 저장했다가 다시 꺼내서 원래 값을 유지하게 한다.

새 데이터를 위한 스택 공간의 할당

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는데도 스택이 사용되기 때문에 문제가 복잡해진다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부른다. 그림 2.12는 프로시저 호출 전, 중, 후의 스택 상태를 보여준다.
MIPS 소프트웨어 중에는 프레임 포인터(frame pointer, $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있다.
이런 이유로 프로시저가 더 이해하기 어려워지는데, 프레임 포인터를 사용하면 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하므로 지역 변수 참조가 간단해진다. 별도의 프레임 포인터 사용 여부와 상관없이 액티베이션 레코드는 항상 스택에 존재함에 유의하라.
이제까지는 프로시저 내에서 $sp가 변하지 않게 했기 땜누에 $fp를 사용하지 않아도 되었다. 예컨대 앞의 예제는 프로시저에 들어갈 떄와 나올 때만 스택을 변화시킨다.

새 데이터를 위한 힙 공간의 할당

C 프로그래머는 프로시저에만 국한되는 자동 변수 외에도 정적 변수와 동적 자료구조를 위한 메모리 공간이 필요하다. 아래 그림 2.13은 MIPS의 메모리 할당 방식이다.
스택은 최상위 주소에서부터 시작해서 아래쪽으로 자란다. 최하위 주소 부분은 사용이 유보되어 있고, 그 다음은 MIPS 기계어 코드가 들어가는 부분이다. 이 부분은 전통적으로 텍스트 세그먼트(text segment)라 부른다.
코드 위쪽에는 정적 데이터 세그먼트(static data segment)라는 부분이 있는데, 상수와 기타 정적 변수들이 여기에 들어간다. 배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다.
그러나 링크드 리스트(linked list) 같은 자료구조는 늘어났다 줄어들었다 한다. 이러한 자료구조를 위한 세그먼트를 전통적으로 힙(heap)이라 불러왔다. 이것이 메모리의 그 다음 부분에 들어간다. 스택과 힙이 서로 마주보면서 자라도록 할당하기 떄문에 메모리를 효율적으로 사용한다.
C는 함수를 사용해서 힙의 공간을 할당받기도 하고 사용하지 않는 공간은 되돌려주기도 한다.
malloc()은 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과 값으로 보내준다. free()는 포인터가 가리키는 힙 공간을 반납한다.
C에서는 메모리 할당을 프로그램이 통제하는데, 이 부분이 흔하고도 까다로운 여러 버그의 근원이다. 사용이 끝난 공간을 반납하는 것을 잊어버리면 ‘메모리 누출(memory leak)’이 발생하여 결국은 메모리 부족으로 운영체제가 붕괴될 수 있다.
반면 공간을 너무 일찍 반납하면 프로그램 의도와 상관 없는 엉뚱한 것을 가리키는 ‘매달린 포인터(dangling pointer)’가 발생한다.
Java에서는 이러한 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션(garbage collection)을 사용한다.
그림 2.14는 MIPS 어셈블리 언어의 레지스터 사용 관계를 보여준다. 이 같은 관례는 ‘자주 생기는 일을 빠르게 하라’는 원칙의 또 다른 예가 된다.
대부분의 프로시저에서는 최대 4개 인자, 복귀 값을 위한 2개의 레지스터, 8개의 보존 레지스터 및 10개의 임시 레지스터를 가지고 메모리에 굳이 갈 필요가 없다.

MIPS의 32비트 수치를 위한 주소지정 및 복잡한 주소지정 방식

32비트 수치 피연산자

프로그램에서 사용하는 상수는 대체로 크기가 작다. 그러므로 대부분 작은 16비트 필드면 충분하지만 때에 따라서는 더 큰 상수가 필요한 경우도 있다. 이럴 때를 위해 MIPS는 레지스터의 상위 16비트에 상수를 넣는 lui(load upper immediate) 명령어를 제공한다. 하위 16비트는 그 다음에 나오는 다른 명령으로 채울 수 있다.
아래 그림 2.15는 lui의 동작을 보여준다.

예제) 32비트 상수의 로딩

레지스터 $s0에 다음 32비트 상수를 채우는 MIPS 어셈블리 코드를 작성하라
0000 0000 0011 1101 0000 1001 0000 0000
Plain Text
먼저 lui를 이용해서 상위 16비트를 채운다. 상위 16비트의 값은 십진수로 61이다.
lui $s0, 61  # 61 decimal = 0000 0000 0011 1101 binary
Plain Text
이 명령을 실행한 후 레지스터 $s0의 값은 다음과 같다.
0000 0000 0011 1101 0000 0000 0000 0000
Plain Text
다음은 하위 16비트를 더하면 된다. 하위 16비트의 값은 십진수로 2304이다.
ori $s0, $s0, 2304  # 2304 decimal = 0000 1001 0000 0000
Plain Text
원하는 대로 레지스터 $s0에는 다음 값이 들어간다.
0000 0000 0011 1101 0000 1001 0000 0000
Plain Text
컴파일러나 어셈블러는 큰 숫자를 직접 다룰 수 없기 때문에 몇 조각으로 나눈 후 레지스터에서 재조립해야 한다. 수치 명령어의 상수는 물론 load나 store의 메모리 주소도 상수 필드의 크기의 제약이 문제가 된다.
MIPS 소프트웨어처럼 이 문제를 어셈블러가 해결하도록 하려면 큰 값을 만드는데 사용할 임시 레지스터를 제공해야 한다.
이 어셈블러를 위해 예약된 레지스터 $at가 이런 용도로 사용된다.
그러므로 MIPS 기계어의 기호 표현은 하드웨어에 의해 제한되기 보다는 어셈블러를 만든 사람이 어떤 것을 포함시키기로 했느냐에 달려 있다.
본서는 컴퓨터 구조를 설명하기 위해 하드웨어를 더 따르되, 하드웨어에는 없지만 어셈블러가 제공하는 확장된 언어를 사용할 때는 별도로 표시하고 쓰기로 한다.

분기와 점프 명령에서의 주소지정

MIPS에서 가장 간단한 주소지정 방식은 점프 명령에서 사용하는 것이다. 점프 명령은 6비트의 op 코드와 26비트의 주소 필드로 구성되는 J 타입 명령어 형식을 사용한다. 그러므로
j 10000  # go to location 10000
Plain Text
을 어셈블하면 다음과 같아진다. (사실은 좀 더 복잡하지만 자세한 것은 곧 다시 설명한다.)
조건부 분기 명령에는 분기 주소 외에 두 개의 피연산자가 더 있다. 그러므로
bne $s0, $s1, Exit  # go to Exit if $s0 ≠ $s1
Plain Text
은 다음과 같이 어셈블되어 분기 주소로 16비트만 쓸 수 있다.
만일 프로그램에서 사용하는 모든 주소가 이 16비트 필드에 들어가야 한다면 어떤 프로그램도 2162^{16} 보다 더 커질 수는 없다. 그러나 이것은 현실적으로 너무 작은 크기이다.
이 문제를 해결할 수 있는 대안은 어떤 레지스터를 지정해서 그 값을 분기 주소와 더하도록 하는 것이다. 이렇게 했을 때 분기 주소는 다음과 같이 구해진다.
PC = 레지스터 + 분기 주소
이 방식은 프로그램 크기가 2322^{32}까지 커지는 것을 허용하면서 조건부 분기도 지원함으로써 분기 주소의 크기 제한을 극복한다. 그러면 이제 남은 문제는 어떤 레지스터를 사용하느냐 하는 것이다.
조건부 분기가 어떻게 사용되는지를 살펴보면 이 문제의 답을 구할 수 있다. 조건부 분기는 주로 순환문이나 if 문에서 사용되므로 가까이 있는 명령어로 분기하는 경향이 있다.
예컨대 SPEC 벤치마크에서 사용된 조건부 분기의 절반가량이 16개 명령어 이상 떨어지지 않은 위치로 분기한다.
PC(program counter)는 현 명령어의 주소를 가지고 있으므로 분기 주소를 더할 레지스터로 PC를 선택하면 현 위치에서 ±215\pm 2^{15} 워드 이내 떨어진 곳은 어디든지 분기할 수 있다.
거의 모든 순환문과 if 문의 분기 범위가 2162^{16}워드 이내이므로 PC는 이상적인 선택이다.
이런 분기 주소지정 방식을 PC 상대 주소지점(PC-relative addressing) 방식이라 한다.
4장에서 설명하겠지만 하드웨어 입장에서는 PC를 일찍 증가시켜 다음 명령을 가리키게 하는 것이 편리하다. 그러므로 실제 MIPS 주소는 현재 명령어 주소(PC)를 기준으로 하는 것이 아니라 다음 명령어 주소(PC+4)를 기준으로 하게 된다.
이것은 ‘자주 생기는 일을 빠르게’라는 원칙의 또 다른 예인데 이 경우에는 가까운 명령어들을 가리키게 되는 것이다.
최근의 모든 컴퓨터가 다 그렇듯이 MIPS도 모든 조건부 분기 명령에 PC 상대 주소를 사용한다. 조건부 분기의 목적지는 대체로 가까운 곳에 있기 때문이다.
반면에 프로시저들은 가까이 붙어 있어야 할 이유가 없으므로 jal 명령은 다른 주소지정 방식을 사용한다. MIPS 구조에서 j 명령어나 jal 명령어가 긴 주소를 사용할 수 있도록 J 타입 형식을 사용한다.
MIPS 명령어의 길이는 항상 4바이트이므로 MIPS의 PC 상대 주소지정 방식에서는 분기할 거리를 바이트 수가 아니라 워드 수로 나타내면 더 먼 거리까지 분기할 수 있다. 바이트 주소 대신 워드 주소를 사용함으로써 분기 거리를 4배로 늘릴 수 있는 것이다.
마찬가지로 점프 명령어의 26비트 필드도 워드 주소이다. 바이트 주소로는 28비트에 해당한다.
(예제 생략)
거의 모든 조건부 분기의 목적지는 가까운 곳이지만, 가끔은 16비트로 나타낼 수 없는 먼 곳으로 분기하는 경우도 있다. 이런 경우 어셈블러는 큰 주소나 상수를 처리할 때와 같은 방법으로 해결한다.
분기 목적지로 가는 무조건 점프를 삽입한 후, 분기로건을 반대로 만들어서 이 점프를 건너뛸 것인지 말 것인지를 결정하게 한다.

예제) 아주 먼 거리로의 분기

레지스터 $s0가 레지스터 $s1과 같으면 분기하는 코드
beq $s0, $s1, L1
Plain Text
를 L1이 아주 멀어도 분기가 가능하도록 바꾸되 명령어 두 개를 사용하라.
다음과 같이 바꿀 수 있다.
bne $s0, $s1, L2 j L1 L2:
Plain Text

MIPS 주소지정 방식 요약

여러 형태의 주소 표현을 일반적으로 주소지정 방식(addressing mode)이라 한다. 그림 2.16에서 보면 각각의 주소지정 방식에서 피연산자가 어떻게 식별되는지 알 수 있다. MIPS에서 사용되는 주소지정 방식은 다음과 같다.
1.
수치(immediate) 주소지정: 피연산자는 명령어 내에 있는 상수이다.
2.
레지스터 주소지정: 피연산자는 레지스터이다.
3.
베이스(base) 또는 변위(displacement) 주소지정: 메모리 내용이 피연산자이다. 메모리 주소는 레지스터와 명령어 내의 상수를 더해서 구한다.
4.
PC 상대 주소지정: PC 값과 명령어 내 상수의 합을 더해서 주소를 구한다.
5.
의사직접(pseudodirect) 주소지정: 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구한다.
MIPS 구조는 32비트 주소를 사용한다고 설명하기는 했지만, 거의 모든 마이크로프로세서(MIPS를 포함해서)가 64비트로 주소를 확장할 수 있다.
이것은 더 큰 프로그램을 필요로 하는 소프트웨어 쪽의 요구에 따른 것이다. 이러한 명령어 집합의 확장은 소프트웨어가 차세대 구조와 상향 호환성을 유지하면서 컴퓨터 구조를 확대할 수 있게 해준다.

기계어의 해독

때로는 역공학을 통해 기계어로부터 원래의 어셈블리 언어를 추출하는 작업을 해야 할 때가 있다. 그런 예 중 하나가 ‘코어 덤프(core dump)’를 읽을 때이다. 이를 위하여 MIPS 기계어 필드의 값을 그림 2.17에 정리하였다. 이 표는 어셈블리 언어와 기계어를 손으로 변환할 때 유용하다.

병렬성과 명령어: 동기화

태스크가 서로 독립적일 때에는 병렬처리가 쉽지만 그래도 서로 협력해야 할 때가 많다. 협력은 보통 다른 태스크들이 읽어야 하는 새로운 값을 어떤 태스크들이 쓰는 것을 의미한다.
다른 태스크들이 안전하게 읽을 수 있게 하려고 태스크가 언제까지 쓰기를 마쳐야 하는지를 알려면 태스트들이 동기화되어야 한다.
이들이 동기화되지 않으면 데이터 경쟁관계(data race)의 위험이 있다. 이벤트가 일어나는 순서에 따라 프로그램의 결과가 달라질 수 있는 상황을 데이터 경쟁관계라 한다.
컴퓨팅에 있어서도 동기화 메커니즘은 일반적으로는 사용자 수준 소프트웨어 루틴에서 제공되는데 이 소프트웨어 루틴들은 하드웨어가 제공하는 동기화 명령을 사용하고 있다.
이 절에서는 lock과 unlock 동기화 연산의 구현에 집중하려 한다. ock과 unlock을 그대로 이용하여 단 하나의 프로세서만이 작업할 수 있는 영역을 생성할 수 있으며 –상호배제(mutual exclusion)라 불림– 더 복잡한 동기화 메커니즘을 구현하는데도 사용할 수 있다.
멀티프로세서에서 동기화를 구현하기 위해서는 메모리 주소에서 읽고 수정하는 것을 원자적(atomically)으로 처리할 능력을 가진 하드웨어 프리미티브가 있어야 한다.
즉 메모리에서 읽고 쓰는 중간에 아무것도 끼어들 수 없어야 한다. 그러한 능력이 없으면 기본 동기화 프리미티브 구현 비용이 너무 비쌀 것이며 그 비용은 프로세서 수가 증가함에 따라 더욱 증가할 것이다.
기본 하드웨어 프리미티브를 대신하는 많은 방법이 있는데, 모두가 메모리 주소에서 읽고 수정하는 것을 원자적으로 처리하는 방법을 제공하고 있으며 읽고 쓰는 것이 원자적으로 처리되었는지 알려 주는 방법도 함께 가지고 있다.
일반적으로 설계자는 기본 하드웨어 프리미티브를 사용자가 쓸 것이라고는 생각하지 않는다. 시스템 프로그래머가 동기화 라이브러리를 구축하는데 사용할 것이라고 생각한다. 이 과정은 상당히 복잡하고 까다로운 경우가 많다.
먼저 하드웨어 프리미티브 하나를 살펴보고 이것이 기본 동기화 프리미티브 구축에 어떻게 사용되는지 알아보자. 동기화 연산 구축을 위한 전형적인 연산은 원자적 교화(atomic exchange 또는 atomic swap)인데, 이 연산은 레지스터의 값을 메모리 값과 교환하는 것이다. MIPS는 이런 명령어 SWP을 가지고 있다.
이것을 기본 동기화 프리미티브 구축에 어떻게 사용하는지 보기 위해 간단한 lock을 만들어보자.
이 lock은 0이면 사용 가능하고 1이면 사용할 수 없을 표시한다고 가정한다. 프로세서는 레지스터에 있는 값 1과 메모리에 있는 lock을 맞바꿈으로써 lock을 1로 만들고자 할 것이다.
만약 다른 프로세서가 이미 접근을 주장하였다면 교환 명령어가 가져온 값은 1일 것이며 그렇지 않은 경우에는 0일 것이다. 후자의 경우에는 그 값이 1로 바뀌어서 다른 프로세서에 있는 경쟁관계의 교환 명령이 0을 읽어가지 못하게 한다.
예컨대 동시에 교환 하려고 하는 두 프로세서를 생각해 보자. 이 경쟁은 금방 끝나게 되는데 한 프로세서만이 교환을 먼저 수행해서 0을 가져올 것이다. 두 번째 프로세서는 1을 읽어 올 것이다.
동기화를 구현하기 위해 교환 프리미티브를 사용할 떄의 핵심은 연산이 원자적이라는 것이다. 즉 교환은 나뉠 수 없는(indivisible) 것이라서 두 개의 동시 교환은 하드웨어에 의해 순서가 결정된다.
두 프로세서가 이런 방법으로 동기화 변수를 설정하여 두 프로세서 모두 그들이 변수를 설정했다고 생각하는 경우는 나올 수 없다.
단일 원자적 메모리 연산을 구현하려면 프로세서 설계 시 몇 가지 문제를 극복해야 하는데 이 연산은 메모리 읽기와 쓰기를 인터럽트가 불가능한 단일 명령어에서 처리해야 하기 때문이다.
또 다른 방법은 한 쌍의 명령어를 갖도록 하는데 두 번째 명령어는 한 쌍의 명령어가 마치 원자적인 것처럼 실행되었는지를 나타내는 값을 반환하여야 한다.
어느 프로세서에서도 실행되는 모든 연산들이 이 한 쌍의 명령어 전이나 후에 실행되는 것처럼 보인다면 이 한 쌍의 명령어는 실질적으로는 원자적이라 말할 수 있다.
따라서 이 명령어 쌍이 실제적으로 원자적이라면 다른 어느 프로세서도 명령어 쌍 사이에서 값을 바꿀 수는 없다.
MIPS에는 이러한 명령어 쌍으로 load linked라 불리는 특수 적재 명령어와 store conditional이라 불리는 특수 저장 명령어가 있다.
이 명령어 쌍은 순차적으로 사용되는데 만약 load linked 명렁어에 의해 명시된 메모리 주소의 내용이 같은 주소에 대한 store conditional 명령어가 실행되기 전에 바뀐다면 store conditional 명령은 실패하게 된다.
store conditional 명령어는 레지스터 값을 메모리에 저장하고 동시에 그 레지스터 값을 1로 바꾸게 되면 송공이고 만약 실패한다면 레지스터 값은 0이 된다.
load linked 명령어는 초깃값을 반환하고 store conditional은 성공할 때만 1을 반환하기 때문에 다음 명령어 시퀀스는 $s1의 내용이 가리키는 메모리 주소에 대해 원자적 교환을 구현하게 된다.
again: addi $t0, $zero, 1  # copy locked value ll $t1, 0($s1) # load linked sc $t0, 0($s1) # store conditional beq $t0, $zero, again # branch if store fails add $s4, $zero, %t1 # put load value in $s4
Plain Text
ll 명령어와 sc 명령어 사이에 프로세스가 끼어들거나 메모리 값을 수정하는 경우에는 sc는 $t0에 0을 반환하기 때문에 코드 시퀀스가 다시 실행하게 된다. 결국 이 시퀀스 끝에는 $s4의 내용과 $s1에 의해 명시된 주소의 메모리 사이에 원자적으로 교환이 이루어진다.

프로그램 번역과 실행

이 절에서는 디스크 파일에 저장되어 있는 C 프로그램을 컴퓨터가 실행할 수 있는 프로그램으로 변환하기 위한 네 단계를 설명한다. 그림 2.19는 이러한 번역 단계를 계층적으로 보여준다.
어떤 시스템은 번역 시간을 줄이기 위해 이 중 몇 단계를 하나로 합치기도 하지만, 논리적으로는 이 네 단계를 거쳐야 한다.

컴파일러

컴파일러는 C 프로그램을 어셈블리 언어 프로그램으로 바꾼다. 어셈블리 언어 프로그램은 컴퓨터가 이해할 수 있는 심벌 형태이다.
상위 수준 언어 프로그램은 어셈블리 언어보다 문장 수가 훨씬 적으므로 프로그래머의 생산성이 높아진다.
1975년 당시에는 메모리가 부족하고 컴파일러가 비효율적이었기 때문에 운영체제와 어셈블러는 어셈블리 언어(assembly language)로 작성하였다.
그러나 오늘날에는 DRAM 칩의 용량이 수백만 배나 커져서 프로그램 크기 문제도 완화되었고, 최적화 컴파일러가 어셈블리 프로그램 전문가에게 필적하거나 오히려 더 우수한(특히 큰 프로그램에 대해서) 어셈블리 언어 프로그램을 생성하고 있다.

어셈블러

어셈블리 언어는 상위 수준 소프트웨어와의 인터페이스이므로 원래는 없는 명령어를 어셈블러가 독자적으로 제공할 수도 있다. 이 명령어들은 하드웨어로 구현이 되어 있지 않더라도, 어셈블러가 알아서 처리하여 번역과 프로그래밍을 간편하게 해준다. 이런 명령어들을 의사명령어(pseudoinstruction)라 한다.
MIPS 하드웨어는 레지스터 $zero의 값이 항상 0이 되도록 한다. 즉 $zero를 사용하면 그 값은 항상 0이며 $zero의 값은 바꿀 수 없다.
그러므로 $zero는 한 레지스터의 내용을 다른 레지스터로 복사하는 move 명령어를 구현하는데 사용할 수 있다. MIPS 하드웨어에는 move 명령어가 없지만 MIPS 어셈블러는 이 명령을 받아들인다.
move $t0, $t1  # register $t0 gets register $t1
Plain Text
어셈블러는 이 명령어를 다음 명령어 해당하는 기계어로 바꾼다.
add $t0, $zero, $t1  # register $t0 gets 0 + register $t1
Plain Text
MIPS 어셈블러는 blt(branch on less than) 명령어를 slt와 bne 두 개의 명령어로 바꾼다.
이 외에도 bgt, bge, ble 명령어가 이렇게 처리된다. 먼 거리로 분기하는 명령어는 분기와 점프 명령어로 바꾸기도 한다.
명령어의 수치 필드 크기는 16비트로 제한되어 있지만 MIPS 어셈블러는 레지스터에 32비트 상수를 넣는 일도 해 줄 수 있다.
결과적으로 의사명령어는 실제의 하드웨어 구현보다 훨씬 더 풍부한 어셈블리 언어 명령어 집합을 제공한다. 이에 대한 대가는 레지스터 하나($at)를 어셈블러 전용으로 유보해 두어야 한다는 것뿐이다.
어셈블리 프로그램을 작성할 때 의사명령어를 적절히 사용하면 일이 쉬워진다.
그러나 MIPS 구조를 제대로 이해하고 주어진 성능을 최대한 활용하기 위해서는 그림 2.1과 2.19에 보인 실제 MIPS 명령어를 공부하는 것이 바람직하다.
어셈블러는 여러 진수의 숫자를 받아들인다. 이진수와 십진수 뿐만 아니라 이진수보다 간결하면서 이진수로 쉽게 바꿀 수 있는 그 외의 진수도 사용할 수 있다. MIPS 어셈블러는 16진수를 사용한다.
이런 기능이 편리하기는 하지만 어셈블러의 주된 임무는 어셈블리 프로그램을 기계어로 번역하는 것이다.
어셈블러는 어셈블리 언어 프로그램을 목적 파일(object file)로 바꾼다. 목적 파일에는 기계어 명령어, 데이터, 명령어를 메모리에 적절히 배치하기 위한 각종 정보들이 혼합되어 있다.
어셈블리 언어 프로그램을 구성하는 각 명령어를 이진수로 바꾸기 위해서는 레이블에 해당하는 주소를 모두 알아야 한다.
어셈블러는 분기나 데이터 전송 명령에서 사용된 모든 레이블을 심벌 테이블(symbol table)에 저장한다. 이 테이블은 심벌과 그 주소를 저장한다.
UNIX 시스템의 목적 파일은 보통 다음과 같은 여섯 부분으로 구성된다.
목적 파일 헤더: 목적 파일을 구성하는 각 부분의 크기와 위치를 서술한다.
텍스트 세그먼트: 기계어 코드가 들어 있다.
정적 데이터 세그먼트: 프로그램 수명 동안 할당되는 데이터가 들어 있다(UNIX 프로그램 실행이 끝날 때까지 계속 할당되는 정적 데이터와 프로그램의 요구에 따라 커졌다 작아졌다 하는 동적 데이터 두 가지를 프로그램이 사용할 수 있게 한다. 그림 2.13 참조)
재배치(relocation) 정보: 프로그래밍 메모리에 적재될 때 절대 주소에 의존하는 명령어와 데이터 워드를 표시한다.
심벌 테이블: 외부 참조 같이 아직 정의되지 않고 남아 있는 레이블들을 저장한다.
디버깅 정보: 각 모듈이 어떻게 번역되었는지에 대한 간단한 설명이 들어 있다. 디버거는 이 정보를 이용해서 기계어와 C 소스 파일을 연관 짓고 자료구조를 판독한다.

링커

이제까지 설명한 대로라면 어떤 프로시저를 한 줄이라도 고치면 전체 프로그램을 다시 컴파일하고 어셈블해야 한다. 이렇게 처음부터 다시 한다면 컴퓨터의 자원이 심각하게 낭비된다.
특히 표준 라이브러리 루틴의 경우는 이런 낭비가 심한데, 그것은 전혀 바뀌지 않는 루틴들을 매번 컴파일하고 어셈블해야 하기 때문이다.
이것을 피하는 방법은 각 프로시저를 따로따로 컴파일, 어셈블 하는 것이다. 어떤 프로시저가 바뀌면 바뀐 프로시저만 다시 번역하면 된다. 이렇게 하려면 링크 에디터(link editor) 또는 링커(linker)라고 부르는 시스템 프로그램이 추가로 필요하다.
이 프로그램은 따로 따로 어셈블된 기계어 프로그램을 하나로 연결해 주는 일을 한다.
링커의 동작은 세 단계로 이루어진다.
1.
코드와 데이터 모듈을 메모리에 심벌 형태로 올려 놓는다.
2.
데이터와 명령어 레이블의 주소를 결정한다.
3.
외부 및 내부 참조를 해결한다.
링커는 각 목적 모듈의 재배치 정보와 심벌 테이블을 이용해서 미정 레이블의 주소를 결정한다. 분기 명령어, 점프 명령어, 데이터 주소 등에 나타나는 구주소를 신주소로 바꾸는 일을 하므로 에디터와 유사한 점이 있다.
이런 이유로 이 프로그램을 링크 에디터라고 부르며, 줄여서 링커라 한다. 프로그램 전체를 다시 컴파일하고 어셈블 하는 대신 링커를 써서 번역된 모듈을 연결하면 시간이 절약된다.
링커가 외부 참조를 모두 해결하고 나면 각 모듈의 메모리 주소를 결정한다. 그림 2.13은 MIPS의 프로그램과 데이터 메모리의 할당 관례를 보여준다.
각 파일을 독립적으로 어셈블하기 때문에 어셈블러는 어떤 모듈의 명령어와 데이터가 다른 모듈과 비교해서 어떤 위치에 있게 될는지 알 수 없다.
링커가 모듈을 메모리에 적재할 때 절대 참조 –레지스터에 더해지는 것이 아닌 실제 메모리 주소– 는 모두 실제 위치에 해당하는 값으로 재설정되어야 한다.
링커는 컴퓨터에서 실행될 수 있는 실행 파일(executable file)을 생성한다. 이 팡리은 대개 목적 파일과 같은 형식을 갖는데, 다만 미해결된 참조는 없다.
라이브러리 루틴같이 일부만 링크된 파일이 있을 수도 있다. 이런 파일은 아직도 미해결 주소를 갖고 있으므로 목적 파일에 속한다.

로더

운영체제는 디스크에 있는 실행 파일을 메모리에 넣고 이를 시작시킨다. UNIX 시스템에서 로더(loader)는 이 일을 다음 순서로 진행한다.
1.
실행 파일 헤더를 읽어서 텍스트와 데이터 세그먼트의 크기를 알아낸다.
2.
텍스트와 데이터가 들어갈 만한 주소 공간을 확보한다.
3.
실행 파일의 명령어와 데이터를 메모리에 복사한다.
4.
주 프로그램에 전달해야 할 인수가 있으면 이를 스택에 복사한다.
5.
레지스터를 초기화하고 스택 포인터는 사용 가능한 첫 주소를 가리키게 한다.
6.
기동 루틴(start-up routine)으로 점프한다. 이 기동 루틴에서는 인수를 인수 레지스터에 넣고 프로그램의 주 루틴을 호출한다. 주 프로그램에서 기동 루틴으로 복귀하면 exit 시스템 호출을 사용하여 프로그램을 종료시킨다.

동적 링크 라이브러리

이 절의 첫 부분에서 프로그램 실행 전에 라이브러리를 링크하는 전통적 방법을 설명했다. 이 정적 접근 방법은 라이브러리 루틴을 호출하는 가장 빠른 방법이지만, 몇 가지 단점이 있다.
라이브러리 루틴이 실행 코드의 일부가 된다. 버그가 제거되었거나 새로운 하드웨어 장치를 지원하는 신판 라이브러리가 나오더라도 정적으로 링크된 프로그램은 옛날 라이브러리를 사용해야 한다.
실행 파일에서 호출되는 라이브러리 루틴들은 이 호출의 실행 여부와 상관없이 전부 적재해야 한다. 따라서 프로그램에 비해 라이브러리가 클 수 있다. 예컨대 표준 C 라이브러리는 2.5MB이다.
이러한 단점 때문에 동적 링크 라이브러리(DLL: dynamically linked library)가 등장하였다.
이 방식에서는 프로그램 실행 전에는 라이브러리가 링크되지도 않고 적재되지도 않는다. 대신 프로그램과 라이브러리 루틴은 전역적 프로시저의 위치와 이름에 대한 정보를 추가로 가지고 있다.
초기의 DLL에서는 로더가 동적 링커를 실행시켰다. 동적 링커는 파일에 저장된 추가 정보를 이용해서 적절한 라이브러리를 찾고 모든 외부 참조를 갱신한다.
이 초기 DLL의 단점은 호출될 가능성이 있는 모든 라이브러리 루틴을 링크시킨다는 것이다. 호출되는 것만 링크 시킨다면 더 좋을 것이다.
이런 관점에서 지연(lazy) 프로시저 링키지형의 DLL이 개발되었다. 여기서는 모든 루틴을 실제로 호출된 후에 링크 시킨다.
다른 많은 기술 혁신처럼 여기에도 트릭이 존재하는데 이것은 일련의 간접접근(indirection) 기법을 사용한다. 그림 2.20에 이 기술을 표시하였다.
이 과정은 프로그램 끝에 있는 더미 루틴(dummy routine)들을 호출하는 전역 루틴에서부터 시작된다. 전역 루틴 하나당 더미 엔트리 하나씩인데, 이 더미 엔트리들은 간접 점프를 가지고 있다.
라이브러리 루틴을 처음 호출할 때는 프로그램이 더미 엔트리를 호출하고 간접 점프를 따라간다. 더미 엔트리는 원한느 라이브러리 루틴을 표시하기 위해 레지스터에 숫자를 넣고 동적 링커/로더로 점프하는 코드를 가리킨다.
링커/로더는 원하는 루틴을 찾아서 재사상하고, 이 루틴을 가리키도록 간접 점프 위치에 있는 주소를 바꾼다. 그러고 나서는 그 주소로 점프한다. 이 루틴이 끝나면 원래 호출한 위치로 돌아온다.
그러므로 다시 라이브러리 루틴을 호출하면 추가로 돌아다는 일 없이 해당 루틴으로 간접 점프한다.
요약하면 DLL은 동적 링킹에 필요한 정보를 위한 추가 공간을 필요로 하지만 전체 라이브러리를 복사하거나 링크할 필요는 없다.
어떤 루틴을 처음 호출할 때는 오버헤드가 매우 크지만, 그 다음부터는 간접 점프 하나만 하면 된다.
라이브러리에서 되돌아올 때는 추가 오버헤드가 없음에 주목하라. Microsoft Windows는 동적 링크 라이브러리에 크게 의존하고 있으며, 오늘날 UNIX 시스템에서 프로그램을 실행할 때도 디폴트이다.

종합: C 정렬 프로그램

(생략)

고급자료: C 컴파일하기

(생략)

실례: ARMv7(32비트) 명령어

ARM은 임베디드 디바이스로는 가장 인기 있는 명령어 집합이다. 처음에는 Acorn RISC Machine을 의미했는데 후에 Advanced RISC Machine으로 바뀌었다.
ARM은 MIPS와 같은 해에 나왔으며 비슷한 철학을 따르고 있다. 그림 2.27은 두 프로세서 사이의 유사성에 대해 보여준다.
가장 근본적으로 다른 점은 MIPS가 더 많은 레지스터를 갖고 있으며 ARM이 더 많은 주소지정 방식을 갖고 있다는 것이다.
그림 2.28은 MIPS와 ARM이 산술-논리 명령어와 데이터 이동 명령어에 대해서는 비슷한 명령어 집합을 갖고 있음을 보여준다.

주소지정 방식

그림 2.29는 ARM이 지원하는 데이터 주소지정 모드를 보여주고 있다.
MIPS와는 달리 ARM은 0을 갖는 레지스터를 갖고 있지 않다.
MIPS는 단지 세 개의 단순한 데이터 주소지정 방식을 갖고 있는데 반해(그림 2.16) ARM은 9개의 주소지정 방식을 갖고 있으며 이 중에는 상당히 복잡한 계산을 하는 방식도 포함되어 있다.
예컨대 ARM은 레지스터를 원하는 만큼 자리이동한 후 다른 레지스터 값을 더하여 주소를 만든 다음 원하는 레지스터를 이 주소로 대체하는 주소 지정 방식을 갖고 있다.

비교 후 조건부 분기

조건부 분기 여부를 판단하기 이ㅜ해 MIPS에서는 레지스터 값을 사용한다. 반면 ARM에서는 프로그램 상태 워드에 저장되는 네 개의 전통적인 조건 코드 비트를 사용하는데 이들은 negative, zero, carry, overflow이다.
이 조건 비트들은 어느 산술 또는 논리 연산 명령 시 설정될 수 있는데 초기 구조와는 달리 이 설정은 각각의 명령어에서 선택사항이다. 즉 명령어 실행 시 해당 조건 비트들을 설정할 수도 하지 않을 수도 있다.
이러한 선택사항을 명시적으로 표시해야 하는 것은 파이프라인 구현에서 몇 가지 문제점을 갖게 된다. ARM은 모든 가능한 관계식(부호 없는 관계, 부호 있는 관계)을 결정하기 위해 조건부 분기를 사용하여 조건 코드들을 테스트한다.
CMP는 한 연산자에서 다른 피연산자를 뺸 후 그 차이에 따라 조건 코드를 설정한다.
CMN(compare negative)은 한 피연산자에다 다른 피연산자를 더하여 그 결과로서 조건 코드를 설정한다.
TST는 두 피연산자에 논리적 AND 연산을 수행하여 overflow를 제외한 모든 조건 코드를 설정하게 되며 반면에 TEQ는 두 피연ㅅ나자에 exclusive OR 연산을 하여 overflow를 제외한 나머지 조건 코드를 설정하게 된다.
ARM의 특이한 점 중 하나는 모든 명령어가 조건 코드에 따라 수행할지 말지를 결정하는 선택사항을 갖고 있다는 점이다.
모든 명령어의 첫 4비트 필드가 조건 코드에 따라서 nop(no operation) 명령어로 작동할지 아니면 실제 명령어로 작동할지 결정하게 된다.
따라서 조건부 분기 명령어는 정확히는 무조건 분기 명령어의 실행 여부를 조건 코드에 따라 결정하는 것으로 생각할 수 있다. 조건부 실행은 분기 명령어가 항상 같은 명령어로 점프하게 되는 것을 피할 수 있게 해준다.
이러한 방법은 명령어 하나를 단순히 조건에 따라 실행할 때 필요한 코드 길이와 시간을 짧게 해준다.
그림 2.30은 ARM과 MIPS의 명령어 형식을 보여주는데 근본적인 차이점은 모든 명령어가 4비트 조건부 실행 필드를 갖고 있으며 레지스터 필드가 짧다는 것이다. 이는 ARM의 레지스터 개수가 반밖에 되지 않기 때문이다.

ARM의 고유 특징

그림 2.31은 MIPS에서는 발견되지 않는 몇 가지 산술-논리 연산 명령어를 보여준다.
ARM에는 0값을 갖는 전용 레지스터가 없기 때문에 MIPS가 $zero를 가지고 할 수 있는 여러 가지 연산을 수행할 수 있는 독립된 opcode를 가지고 있다. ARM은 다중워드 산술 연산도 지원한다.
ARM의 12비트 수치 필드는 특이한 설명이 필요하다. 이 필드의 하위 8비트를 앞에 0을 붙여 32비트 수로 만든 다음 앞의 4비트 값에다 2를 곱한 값에 해당되는 비트만큼 오른쪽으로 회전한다.
이 방법의 장점은 2의 멱승을 32비트 워드로 표현할 수 있다는 것이다.
그러나 이러한 방법이 단순한 12비트 필드보다 더 많은 수치를 가질 수 있는지는 좀 더 연구해 봐야 한다.
피연산자 자리이동이 수치에만 국한되는 것은 아니다. 모든 산술 및 논리 연산에서의 두 번째 레지스터는 연산이 취해지기 전에 자리이동을 할 것인지 말 것인지에 대한 선택사항을 갖고 있다. 자리이동 선택사항은 shift left logical, shift right logical, shift right arithmetic, rotate right이다.
ARM에는 레지스터 그룹을 위한 명령어도 존재하는데 이들 명령어는 block loads 및 block stores라 불린다.
명령어에 있는 16비트 마스크를 사용하여 16개 레지스터 중 어느 레지스터도 하나의 명령어 사이클에 로드되거나 메모리에 저장될 수 있다.
이러한 명령어들은 프로시저에 진입하거나 프로시저에서 빠져나갈 때 레지스터들을 저장하거나 복원할 수 있다.
이러한 명령어들은 블록 메모리 복사를 위해 사용될 수 있는데 오늘날 블록 복사는 이러한 명령어가 가장 중요하게 사용되는 경우이다.

실례: x86 명령어

ARM이나 MIPS보다 강력한 연산을 제공하는 명령어 집합도 있다. 그 목적은 프로그램이 실행하는 명령어의 개수를 줄이자는 것이다.
그러나 이것은 간결성을 희생한 대가로 얻어지는 것이므로, 명령어 처리 시간이 길어져서 프로그램 실행에 걸리는 시간은 오히려 늘어날 위험이 있다.
이렇게 느려지는 이유는 클럭 사이클 시간이 길어지거나 필요한 클럭 사이클 개수가 더 많아지기 때문이다.
복잡한 명령어를 지향하는 것은 이러한 위험성을 내포하고 있다.

Intel x86의 진화

ARM과 MIPS는 1985년에 한 작은 연구팀이 만든 것이다. 이 프로세서의 각 부분은 서로 잘 조화를 이루고 있으며 전체 구조도 아주 간결하다. 그러나 x96은 경우가 다르다. x86은 여러 독립적인 그룹이 35년 이상 꾸준히 발전시켜 온 결과이다.
Intel은 마치 짐가방에 옷을 더 집어 넣듯이 원래의 명령어 집합에 새로운 기능을 꾸겨 넣었다.
x86 발달 과정에 있었던 중요한 사건을 정리하면 다음과 같다.
(생략)
이 변천 과정은 호환성이라는 ‘황금수갑’이 끼치는 해악을 잘 보여주고 있다. x86에게는 기존의 확고한 소프트웨어 기반이 오히려 족쇄가 되어 혁신적인 구조 개혁을 감행할 수가 없었다.

x86 레지스터와 데이터 주소지정 방식

80386 레지스터(그림 2.32)를 보면 명령어 집합의 발달 과정을 알 수 있다.
80386은 모든 16비트 레지스터(세그먼트 레지스터 제외)를 32비트로 확장하고 레지스터 이름 앞에 E를 붙였다.
이 레지스터들을 범용 레지스터(GPR: generl-purpose register)라 한다. 80386에는 GPR이 8개 밖에 없지만, MIPS는 이보다 네 배나 더 많고 ARM은 두 배가 많다.
그림 2.33에서 산술, 논리, 데이터 전송 명령은 피연산자를 두 개씩 갖는 것을 알 수 있다. ARM 및 MIPS와 비교하면 중요한 차이점이 두 가지 있다.
ARMv7과 MIPS의 산술 및 논리 명령은 근원지와 목적지 레지스터를 독립적으로 지정할 수 있지만 x86에서 피연산자 하나는 근원지이면서 동시에 목적지가 된다. 레지스터 개수도 충분하지 못한데다 두 근원지 레지스터 중 하나는 값이 변해야 하므로 매우 불편하다.
두 번째 차이점은 피연산자 중 하나가 메모리에 있을 수 있다는 것이다. MIPS나 ARMv7과는 달리 거의 모든 명령어가 메모리 피연산자를 사용할 수 있다.
메모리 피연산자는 모든 주소지정 방식을 사용할 수 있지만, 특정 주소지정 방식에서 사용할 수 있는 레지스터에는 제한이 있다. 그림 2.34는 x86의 주소지정 방식과 각 주소지정 방식에서 사용할 수 없는 레지스터를 보여준다. 아울러 MIPS 명령어를 사용하여 어떻게 같은 효과를 얻는지 설명하고 있다.

x86의 정수 연산

8086은 8비트(바이트)와 16비트(워드) 데이터형을 지원하며, 80386은 여기에 32비트 주소와 3비트 데이터(더블 워드)를 추가하였다. (AMD64에서는 64비트 주소와 64비트 데이터(쿼드워드)를 추가했지만 이 절에서는 80386에 국한해서 설명한다) 이 데이터형 구분은 메모리에 접근할 때 뿐만 아니라 레지스터 연산을 할 때도 적용된다.
거의 모든 연산이 두 데이터 모두 8비트인 경우와 하나의 데이터가 8비트보다 더 긴 경우 모두를 지원한다. 긴 데이터의 크기는 주소지정 방식에 따라 16비트와 32비트 중 하나로 정해진다.
세 가지 크기의 데이터를 모두 다루어야 하는 프로그램도 있기 때문에 80386 설계자들은 코드 길이를 많이 늘리지 않으면서 데이터 크기를 간편하게 지정할 수 있는 방법을 고안하였다.
대부분의 프로그램이 16비트나 32비트 데이터 중 한 가지를 주로 사용하는 경향이 있다는데 착안하여 디폴트 데이터 크기를 선언하는 방법을 사용하였다. 디폴트 데이터 크기는 코드 세그먼트 레지스터의 비트 하나를 이용하여 설정된다.
디폴트 데이터 크기는 코드 세그먼트 레지스터의 비트 하나를 이용하여 설정된다. 디폴트 크기가 아닌 데이터를 사용할 떄는 명령어에 8비트짜리 접두사를 붙여 다른 크기의 데이터를 사용한다는 것을 알린다.
이러한 접두사 사용법은 8086에서 차용한 것으로, 8086은 몇 가지 접두사를 써서 명령어 동작에 변형을 가할 수 있게 되어 있다.
원래의 세 가지 접두사는 (1) 디폴트가 아닌 다른 세그먼트 레지스터의 사용, (2) 동기화 지원을 위한 버스 잠금, (3) ECX 레지스터가 0이 될 때까지 명령어의 반복 실행 등을 지시하는 것이다.
이 중 마지막 것은 바이트 복사 명령어에 붙여서 가변 개수의 바이트 데이터를 복사하는데 사용하기 위한 것이다.
80386은 이 세가지에 디폴트 크기가 아닌 주소를 사용하기 위한 접두사 하나를 추가하였다.
x86의 정수 명령은 크게 네 종류로 나눌 수 있다.
move, push, pop을 포함하는 데이터 전송 명령
검사와 정수 및 십진수 연산을 포함하는 산술 및 논리 명령
조건부 분기, 무조건 점프, call, return 등을 포함하는 제어 흐름 명령
문자열 이동 및 문자열 비교 등을 포함하는 문자열 명령
산술 및 논리 명령의 목적지가 레지스터, 메모리 어느 쪽도 가능하다는 점을 제외하면 처음 두 종류는 특별한 것이 없다. 그림 2.35에 전형적인 x86 명령어와 그 기능을 보였다.
x86의 조건부 분기는 ARMv7처럼 조건 코드(또는 플래그)에 의해 결정된다. 조건 코드는 연산 결과에 따라 자동적으로 값이 결정되는데, 가장 많이 쓰이는 것은 연산 결과가 0인지 아닌지 비교한느 것이다.
분기 명령어는 조건 코드를 검사한다. ARM이나 MIPS와 달리 80386 명령어는 길이가 일정하지 않으므로 PC 상대 주소지정 방식에서 워드 주소를 사용하지 못하고 바이트 주소를 사용해야 한다.
문자열 명령어는 8080에서부터 있었는데 많이 사용되지는 않았다. 그 이유는 소프트웨어 루틴으로 처리하는 것보다 오히려 더 느린 경우가 많았기 때문이다.
그림 2.36에 x86의 정수 명령어를 일부 보였다. 그중 많은 명령어가 바이트와 워드 데이터 양쪽을 다 지원한다.

x86의 명령어 인코딩

80386은 여러 가지 명령어 형식을 사용하여 명령어를 아주 복잡하게 인코딩하고 있다. 80386의 명령어 길이는 1바이트(피연산자가 없는 명령어)부터 15바이트까지 매우 다양하다.
그림 2.35의 명령어 중 몇 개를 골라 그 명령어 형식을 그림 2.37에 보였다.
opcode 바이트에는 피연산자의 크기가 8비트인지 32비트인지를 표시하는 비트가 포함되어 있는 것이 보통이다.
어떤 명령어에서는 주소지정 방식과 레지스터 필드가 opcode에 포함된다. ‘레지스터=레지스터 op 상수’ 형태의 명령어는 대개가 다 그렇다.
다른 명령어들은 ‘mod, reg, r/m’ 이라는 추가 opcode 바이트(postbyte)를 사용한다. 여기에는 주소지정 방식에 관한 정보가 들어 있다. postbyte는 메모리에 접근한느 명령어에서 많이 사용된다.
베이스+스케일링된 인덱스 주소지정 방식은 ‘sc, index, base’라는 두 번째 postbyte를 사용한다.
그림 2.38은 16비트와 32비트 주소지정 방식에서 두 postbyte 주소지정자의 인코딩을 보여준다. 어떤 레지스터와 어떤 주소지정 방식을 사용할 수 있는지를 완전히 이해하려면 모든 주소지정 방식의 인코딩 방법을 알아야 하며, 경우에 따라서는 명령어의 인코딩 방법까지 알아야 한다.

x86 결론

Intel의 경쟁자 중에는 Motorola 68000과 같이 더 우아한 구조를 갖고 있는 회사들이 있었다. 그러나 Intel은 이들보다 2년 먼저 8086을 발표하였고, 그 덕에 IBM PC의 CPU로 선택되는 행운을 맞았다.
Intel 기술자들은 x86이 ARMv7이나 MIPS 같은 컴퓨터보다 만들기 어렵다는 것을 인정하지만 훨씬 큰 시장을 확보하고 있으므로 PC 시대에는 이러한 복잡성을 극복하기 위한 투자가 가능하다. x86은 스타일의 약점을 양으로 보상하고 있다.
다행스컵게도 가장 많이 쓰이는 x86 구성 요소들은 생각만큼 구현하기 어렵지 않았다. 1987년 이래 빠른 속도로 정수 프로그램의 성능을 개선해 오고 있는 것이 그 증거이다.
좋은 성능을 얻기 위해서는 컴파일러의 역할도 중요한데, 컴파일러는 속도가 느린 부분의 사용을 가능한 피해야 한다.
그러나 포스트 PC 시대에 수많은 구조 전문가와 제조 전문가가 있음에도 불구하고 x86은 개인 모바일 장치에서는 그리 경쟁력을 보여주지 못하고 있다.

실례: ARMv8(64비트) 명령어

명령어 집합에서의 잠재적 문제점들 중에서 거의 극복이 불가능한 문제는 메모리 주소가 너무 작은 것이다. x86은 32비트 주소로 확장되고 나중에 64비트 주소로 확장되었지만, 같은 처지에 있던 많은 프로세서들이 이를 따라 하지 못했다.
예컨대 16비트 주소를 갖는 MoStek 6502는 Apple II에 장착되었었다. 이 프로세서는 상업용으로 최초로 성공한 개인용 컴퓨터에 장착된 유리한 출발에도 불구하고 주소 비트가 작아서 역사의 휴지통으로 사라졌다.
ARM 설계자들은 이 32비트 주소 컴퓨터에 대해 언급되는 것을 볼 수 있었고, 2007년도에 64비트 주소 버전의 설계를 시작해서 마침내 2013년도에 세상에 내놓게 되었다.
기본적으로 x86에서 했던 것처럼 모든 레지스터 크기를 64비트로 늘리는 단순한 변화가 아니라 완전히 뜯어고친 프로세서였다.
좋은 소식이 MIPS에 대해 알고 있다면 64비트 버전인 ARMv8은 매우 쉽게 이해할 수 있다는 사실이다.
MIPS와 비교했을 떄 첫쨰로 ARM은 v7의 이상한 특징 모두를 싹 없앴다.
v7에서 거의 모든 명령어에 있던 조건부 실행 필드가 없어졌다.
수치 필드는 단순히 12비트 상수이다.(v7에서는 수치를 생성하는 기능에 대한 입력으로 주어졌었다)
다중 적재 명령어(load multiple instruction)와 다중 저장 명령어(store multiple instruction)은 없어졌다.
PC는 더는 일반 레지스터 중 하나가 아니다. 예전에는 일반 레지스터 중 하나였기 때문에 PC에 쓰기를 행하여 예기치 못한 분기가 일어나곤 했었다.
두 번째로는 MIPS에서 유용하게 생각되었지만 ARM에 없던 특징들이 추가되었다.
v8은 32개의 범용 레지스터를 갖고 있다. MIPS처럼 항상 0을 갖는 레지스터가 있다. 그러나 적재 명령어와 저장 명령어에서 이 레지스터는 스택 포인터를 가리킨다는게 다른 점이다.
ARM v8에서는 주소지정 방식이 모든 워든 크기에 대해 동작한다. ARM v7에서는 그렇지 못했다.
ARM v7에 없던 나눗셈 명령어가 추가되었다.
MIPS에서의 같을 시 분기와 다를 시 분기 명령어와 같은 명령어가 추가되었다.
ARM v8 명령어 집합의 철학이 ARM v7보다 MIPS에 훨씬 가깝기 때문에 ARM v7과 ARM v8 사이의 유사성은 이름 뿐이라는게 우리의 결론이다.

오류 및 함정

오류: 강력한 명령어를 사용하면 성능이 좋아진다.
Intel x86 명령어가 강력한 이유 중 하나는 명령어 실행 방식을 변경하는 접두사를 가지고 있기 때문이다. 그중 한 접두사는 카운터 값이 0이 될 때까지 명령어를 반복 실행시킬 수 있는 것이다.
메모리 내의 데이터 블록을 복사할 때 32비트 move 명령에 이 반복 접두사를 붙이면 편리하다.
접두사를 사용하지 않고 표준 명령어만 사용해서 데이터를 레지스터에 적재했다가 다시 메모리에 저장하는 방식을 사용할 수도 있다.
공평한 비교를 위해 순환문 오버헤드가 없도록 순환문으로 만들지 말고 명령어를 반복적으로 늘어놓는 방법을 쓰면 접두사를 쓴 것보다 1.5배 빠르다.
x86의 정수 레지스터 대신 이보다 더 큰 부동소수점 레지스터를 사용하면 복잡한 move 명령어보다 두 배 빨라진다.
오류: 최고 성능을 얻기 위해 어셈블리 언어로 프로그램 작성하기
과거에는 컴파일러가 출력하는 코드의 성능이 좋지 않았으나 컴파일러 기술이 발달하면서 컴파일한 코드와 손으로 작성한 코드 간의 차이가 급격히 줄어들고 있다.
실제로 어셈블리 프로그래머가 오늘날의 컴파일러와 경쟁하려면 4장과 5장에서 설명하는 프로세서 파이프라이닝과 메모리 계층의 개념을 완전히 이해하고 있어야 한다.
설사 손으로 작성해서 더 빠른 코드를 만들었다 하더라도 어셈블리 프로그램은 코딩과 디버깅에 더 많은 시간이 걸리고, 이식성이 없으며, 유지보수가 어렵다는 문제가 있다. 소프트웨어 공학에서 공인된 몇 안되는 공리 중 하나가 프로그램의 줄 수가 많을수록 코딩에 더 오랜 시간이 걸린다는 것이다.
어셈블리 언어 대신 상위 수준 언어를 사용하면 장래 새 기종이 개발되더라도 새 컴파일러에 맞게 수정하여 사용할 수 있을 뿐만 아니라 유지보수도 쉽고 여러 종류의 컴퓨터에서 사용할 수도 있다.
오류: 상업용 프로그램의 이진 호환성이 중요하다는 것은 성공적인 명령어 집합은 변하지 않는다는 것을 의미한다.
후방(backwards) 이진 호환성은 신성불가침이지만, 그림 2.39를 보면 x86 구조가 매우 극적으로 성장해 왔음을 알 수 있다. 지난 35년 동안 평균적으로 한 달에 하나 이상의 명령어가 추가된 셈이다.
함정: 바이트 주소를 사용하는 컴퓨터에서 인접 워드 간의 주소 차이가 1이 아니라는 사실을 잊는 것
많은 어셈블리 프로그래머들이 주소를 하나 증가시키면 다음 워드를 찾을 수 있다고 생각했다가 이로 인해 생긴 오류로 심한 고생을 겪었다. 유비무환임을 명심하라.
함정: 자동 변수가 정의된 프로시저 외부에서 자동 변수에 대한 포인터를 사용하는 것
포인터를 사용할 때 저지르기 쉬운 실수는 프로시저의 결과를 전달할 때 프로시저 내에서 지역 변수로 선언된 배열을 가리키는 포인터를 포함시키는 것이다.
그림 2.12의 스택 동작에 따르면 지역 배열이 저장된 메모리 영역은 프로시저가 종료되자마자 다른 용도로 재사용된다. 따라서 이미 없어진 자동 변수에 대한 포인터를 사용하면 예기치 못한 일이 발생할 수 있다.

결론

내장 프로그램 컴퓨터의 두 가지 기본 원리는 숫자와 같은 형태의 명령어를 사용한다는 것과 변경 가능한 메모리에 프로그램을 저장한다는 것이다.
이 두 가지 원리 때문에 컴퓨터 하나로 과학자는 과학자대로, 금융가는 금융가대로, 소설가는 소설가대로 자기가 필요한 일을 처리할 수 있는 것이다.
명령어 집합의 선택은 프로그램 실행에 필요한 명령어 개수와 명령어 한 개의 실행에 필요한 클럭 사이클 수, 그리고 클럭 속도 간의 미묘한 균형을 요하는 문제이다.
명령어 집합 설계자가 이런 미묘한 결정을 내릴 때 지침이 될 수 있는 설계 원칙이 세 가지 있다.
간단하게 하기 위해서는 규칙적인 것이 좋다.
MIPS 명령어 집합의 특성 중 많은 부분이 규칙성을 염두에 두고 결정된 것이다. 예컨대 모든 명령어의 길이를 똑같게 한 것, 산술 명령어는 항상 레지스터 피연산자 세 개를 갖도록 한 것, 어떤 명령어 형식에서나 레지스터 필드의 위치가 일정하게 만든 것 등이다.
작은 것이 더 빠르다.
MIPS의 레지스터 개수를 32개로 제한한 이유는 속도를 빠르게 하기 위해서다.
좋은 설계에는 적당한 절충이 필요하다.
MIPS는 명령어 내의 주소나 상수부는 클수록 좋으며 모든 명령어의 길이는 같은 것이 좋다는 두 요구사항을 적당히 절출하여 수용하고 있다.
자주 생기는 일을 빠르게라는 굉장한 생각이 명령어 집합 뿐만 아니라 컴퓨터 구조에도 적용된 것으 ㄹ볼 수 있다.
MIPS에서 자주 발생하는 일을 빠르게 한 예로는 조건부 분기에 PC 상대 주소를 사용한 것과 큰 상수 피연산자르 ㄹ위해 수치 주소지정 방식을 도입한 것 등을 들 수 있다.
이 기계어 수준 위에는 어셈블리 언어가 있다. 어셈블러는 이것을 기계가 이해할 수 있는 이진수로 번역하고, 때로는 하드웨어에 없는 명령을 추가하여 명령어 집합을 확장하기도 한다.
예컨대 너무 큰 상수나 주소는 적당한 크기로 나누어 처리하며, 자주 쓰이는 명령어 시퀀스에 별도의 이름을 붙여 의사 명령어를 만들기도 한다.
이제까지 우리가 살펴본 MIPS의 명령어를 그림 2.40에 열거했다. 상위 수준에서 구체적인 것들을 감추는 것은 추상화의 또 다른 예가 된다.
MIPS의 각 명령어 종류는 다음과 같이 상위 수준 언어의 구조나 문장과 연관 지을 수 있다.
산술 명령어는 치환문에 나타나는 연산에 해당한다.
데이터 전송 명령어는 배열이나 구조체 같은 자료구조를 다룰 때 자주 쓰인다.
조건부 분기는 if 문과 순환문에서 사용된다.
무조건 점프는 프로시저 호출과 복귀 및 case/switch 문에서 사용된다.
명령어들의 사용 빈도는 서로 다르다. 몇몇 명령어는 아주 자주 사용된다.
SPEC CPU2006에서 각 종류가 얼마나 자주 쓰이는지를 그림 2.41에 보였다. 이러한 명령어 사용 빈도의 차이는 데이터패스, 제어, 파이프라인의 설계와 밀접합 연관이 있다.