맛있는고슴도치

Computer System

79 min read

1. 정수 (Integers)

1.1. 디지털 시스템 (Digital Systems)

컴퓨터 시스템의 모든 정보는 비트(Bit) 의 연속으로 표현된다. 아날로그(Analog) 신호가 연속적인 값을 갖는 것과 달리, 디지털(Digital) 시스템은 이산적인 값, 즉 0과 1만을 사용하여 정보를 처리한다.

이렇듯 값의 종류에 무관하게 표현 방식이 이진법으로 동일하기에, 같은 비트 패턴이라도 어떤 맥락(Context) 에서 해석되는지에 따라 전혀 다른 정보가 될 수 있다.

부울 대수 (Boolean Algebra)

조지 불(George Boole)에 의해 개발된 논리 대수 체계로 , 현대 디지털 시스템의 수학적 기반을 이루며, 참(True)을 1, 거짓(False)을 0으로 표현한다. 이러한 시스템은 다음과 같은 기본 논리 연산들을 정의한다.

  • AND (&): 두 입력이 모두 1일 때만 결과가 1이 된다.
  • OR (∣): 두 입력 중 하나라도 1이면 결과가 1이 된다.
  • NOT (~): 입력을 반전시킨다. 따라서 1은 0으로, 0은 1로 바뀐다.
  • XOR (^): 두 입력이 서로 다를 때만 결과가 1이 된다.

또한, 이러한 연산들은 다음과 같이 비트 벡터의 각 비트에 대해 개별적으로 적용될 수 있다.

논리 게이트 (Logic Gates)

부울 대수의 연산들은 트랜지스터(Transistor) 라는 전자 스위치를 이용하여 물리적인 회로로 구현된다.

특히 NAND 게이트는 기능적으로 완전하여(functionally complete), NAND 게이트만으로도 AND, OR, NOT 등 다른 모든 논리 연산을 구현할 수 있다. 따라서 CMOS 기술을 통해 쉽게 구현할 수 있는 NAND 게이트는 디지털 시스템의 핵심적인 구성 요소가 된다.

이러한 게이트들을 조합하여 가산기(Adder) 와 같은 조합 논리 (Combinational Logic) 회로나, 플립플롭(Flip-flop) 과 같은 순차 논리 (Sequential Logic) 회로를 구성할 수 있다.

1.2. 정수 표현 (Representing Integers)

개의 비트를 사용하여 정수를 표현하는 방식은 크게 부호 없는 정수와 부호 있는 정수로 나뉜다.

1.2.1. 부호 없는 정수 (Unsigned Integers)

개의 비트를 통해 의 정수만을 표현하는 자료형이다.

개의 비트 벡터 가 주어졌을 때, 해당 정수 값은 다음과 같이 계산된다.

1.2.2. 부호 있는 정수 (Signed Integers)

unsigned integer와 달리, 음수, 0, 양수를 모두 표현하며, 대표적으로 다음 세 가지 방식이 존재한다.

부호와 크기 (Sign-Magnitude)

최상위 비트(Most Significant Bit, MSB) 를 부호 로 사용하고 나머지 비트로 크기를 표현한다. 사람에게 가장 직관적이지만, 표현가능한 범위 내에 0에 대한 표현이 두 개 존재하는 단점이 있다.

1의 보수 (Ones’ Complement)

양수는 부호 없는 정수와 동일하게 표현하고, 음수는 해당 양수의 모든 비트를 반전시켜 표현한다. 부호와 크기를 이용한 표현법과 비슷하게, 역시 0에 대한 표현이 중복으로 존재하며 현재는 거의 사용되지 않는다.

2의 보수 (Two’s Complement)

현대의 거의 모든 컴퓨터 시스템에서 사용하는 표준 방식이다.

비트로 표현 가능한 범위는 까지이며, 최상위 비트는 의 가중치를 가지는 부호 비트로 사용된다. 0에 대한 표현이 유일하고, 음수 쪽의 표현 범위가 하나 더 넓은 비대칭적인 특징을 가진다.

음수 는 의 모든 비트를 반전시킨 후 1을 더하여 간단히 구할 수 있다. 다르게 말하자면, 개의 비트를 통해 2의 보수법으로 표현되는 정수는 를 만족하게끔 정의된다.

1.2.3. 정수의 형 변환 (Integer Type Conversion)

정수는 이를 표현하는 비트 수에 따라 그 범위를 쉽게 확장(Extension) 또는 축소(Truncation) 할 수 있다.

확장 과정에서 신경써야할 것은 확장되는 공간을 채울 비트를 어떤 것으로 하느냐이다.

컴퓨터는 unsigned integer에 대해 확장할 때에는 남는 공간을 0으로 채우는 0 확장 (Zero Extension) 을 수행한다.

또한, 부호 있는 정수를 확장할 때에는 기존의 부호 비트(MSB)를 복사하여 채우는 부호 확장 (Sign Extension) 을 수행한다.

비트 수를 줄일 때는 상위 비트를 단순히 버린다.

1.3. C언어에서의 고려사항 (C Language Considerations)

C언어에서 정수형을 다룰 때, 특히 부호 있는(signed) 값과 부호 없는(unsigned) 값을 혼용할 경우 예상치 못한 결과가 발생할 수 있다.

명시적 형변환 (Explicit Casting)

C언어에서 부호 있는 값과 부호 없는 값이 하나의 표현식(expression) 에 함께 사용될 때, 프로그래머는 이 중 특정한 형식으로 표현된 값의 비트를 다른 형식으로 해석하게끔 강제할 수 있다.

unsigned char x = 129; //  x = 0b10000001 = 129
char ix = (char) x;    // ix = 0b10000001 = -127

이렇게 (char), (int) 등의 문법을 통해 다른 형식으로 형 변환을 수행하는 것을 명시적 형변환(Explicit Casting) 이라 한다.

암시적 형변환 (Implicit Casting)

C언어에서는 부호 있는 값과 부호 없는 값이 하나의 표현식(expression) 에 함께 사용될 경우, 프로그램러가 명시하지 않더라도, 부호 있는 값(signed)은 암시적으로 부호 없는 값(unsigned)으로 변환된 후 연산이 수행된다. 이러한 형변환을 암시적 형변환(Implicit Casting) 이라 한다.

이 규칙은 산술 연산 뿐만 아니라 비교 연산자(<, >, == 등)에도 동일하게 적용된다.

-1 < 0u

C언어에서 -1 < 0U 라는 비교문은 거짓(false)으로 평가된다.

이는 signed int인 -1이 unsigned int인 0u와 비교 연산되는 과정에서 암시적 형변환으로 unsigned로 변환되면서 매우 큰 양수(UMax)가 되어 0U보다 크다고 판단되기 때문이다.

프로그래머가 명시하지 않은 암시적 형변환은 다음과 같은 심각한 잠재적 위협을 가지고 있다.

반복문에서의 암시적 형변환 위험성 

int main() {
	unsigned i;
	for (i = 10; i >= 0; i--) 
		printf("%u\n", i);
}

위 코드에서 unsigned int i를 i >= 0 조건으로 반복문을 실행하면, i가 0이 된 후 1을 감소시키는 과정에서 오버플로우가 발생하여 가장 큰 부호 없는 정수(UMax)가 된다. 따라서 i는 항상 0 이상의 수로 유지되고 따라서 무한 루프에 빠지게 된다.

함수에서의 암시적 형변환 위험성 

#include ‹string.h>
 
int stronger (char *s, char *t) {
	return (strlen(s) - strlen(t)) > 0; 
}

위 코드에서 strlen 함수는 size_t라는 부호 없는 정수형을 반환한다. 따라서 strlen(s) - strlen(t) < 0과 같은 비교는 strlen(s)가 strlen(t)보다 작을 때 음수가 아닌 매우 큰 양수가 되어 의도와 다르게 동작할 수 있다.

배열 점근에서 암시적 형변환 위험성 

int sum_array (int all, unsigned len) {
	int i; 
	int result = 0;
	for (i = 0; i ‹= len - 1; i++) 
		result += a[il;
	return result;
}

위 코드처럼 배열의 길이를 unsigned len으로 받을 경우 i <= len - 1과 같은 반복 조건에서 len이 0이면, len - 1은 언더플로우로 인해 매우 큰 양수가 되어 메모리의 잘못된 영역에 접근하는 심각한 오류를 초래할 수 있습니다.

이외에도 암시적 형변환으로 인해 예상치 못한 동작이나 미묘한 버그가 발생할 수 있어 주의를 기울여야 한다.

2. 정수 연산 (Integer Operations)

2.1. 비트 및 논리 연산 (Bit-Level & Logical Operations)

C언어는 정수형 데이터 타입을 비트 벡터(Bit Vector)로 간주하여 직접 조작할 수 있는 다양한 연산자를 제공한다.

비트 연산 (Bit-Level Operations): & (AND), | (OR), ~ (NOT), ^ (XOR)

Bitwise Operation이라고도 하며, 두 정수 인자(비트 벡터)의 각 비트에 대해 개별적으로 연산을 적용한다.

또한, 비트 벡터를 집합(Set)으로 간주하여 교집합(&), 합집합(|), 여집합(~), 대칭차(^) 등을 효율적으로 계산할 수도 있다.

논리 연산 (Logical Operations): && (AND), || (OR), ! (NOT)

표현식의 결과에 대해 0은 ‘거짓(False)‘으로, 0이 아닌 모든 값은 ‘참(True)‘으로 간주하여, 논리 연산을 수행하며, 논리 연산의 결과는 항상 0 (거짓) 또는 1 (참) 이다.

  • 단축 평가 (Early Termination)
    • && 연산에서 첫 번째 인자가 거짓이거나, || 연산에서 첫 번째 인자가 참이면 두 번째 인자는 평가하지 않고 즉시 결과를 반환한다.
    • 이는 if (p && *p) 와 같은 구문에서 널 포인터 역참조 (Null Pointer Dereference) 를 방지하는 데 유용하게 사용된다.

시프트 연산 (Shift Operations)

w5-

  • 왼쪽 시프트 (Left Shift): x << y
    • 길이 의 비트 벡터 를 왼쪽으로 만큼 이동시킨다. 왼쪽으로 밀려나 의 표현범위 밖으로 벗어난 비트들은 버려지고, 오른쪽의 빈 공간은 0으로 채워진다.
    • 이진법에서 정수 를 왼쪽으로 비트 시프트하는 것은 곧 를 계산하는 것과 같다.
  • 오른쪽 시프트 (Right Shift): x >> y

    • 길이 의 비트 벡터 를 왼쪽으로 만큼 이동시킨다. 오른쪽으로 밀려나 인덱스 0번 이하로 벗어난 비트들은 버려진다. 이때 왼쪽에 채워지는 비트는 두가지 시프트 종류에 따라 달라진다.

    • 논리 시프트 (Logical Shift)

      • 부호 없는(unsigned) 정수에 사용되며, 왼쪽의 빈 공간을 항상 0으로 채운다. ㅌ >> y는 와 동일한 결과를 낸다.

    • 산술 시프트 (Arithmetic Shift)

      • 부호 있는(signed) 정수에 사용되며, 왼쪽의 빈 공간을 최상위 비트(부호 비트)인 MSB로 복사하여 채운다.
      • 이는 2의 보수 표현에서 음수의 부호를 유지할 수 있게 한다.

    • 이진법에서 정수 를 오른쪽으로 비트 시프트하는 것은 곧 를 계산하는 것과 같다

2.2. 정수 덧셈 (Integer Addition)

비트 정수 덧셈의 실제 합(true sum) 은 최대 개의 비트가 필요할 수 있다. 하지만 컴퓨터는 비트만을 결과로 저장하므로 자칫 결과 정수의 MSB 파트가 잘려나가는 오버플로우 (Overflow) 가 발생할 수 있다.

부호 없는 덧셈 (Unsigned Addition)

비트 정수 두개의 실제 합이 보다 크거나 같으면, 올림(carry) 비트를 무시하고 결과가 를 기준으로 순환(wrap around)한다. 이는 마치 모듈러(modular) 연산과 같다.

부호 있는 덧셈 (Signed Addition)

2의 보수 덧셈에서 오버플로우는 항상 결과의 부호가 예상과 다를 때 발생한다. 즉 다음의 두 경우와 오버플로우는 동치이다.

  • 양의 오버플로우: 두 양수를 더했을 때 음수가 나오는 경우
  • 음의 오버플로우: 두 음수를 더했을 때 양수가 나오는 경우

따라서 오버플로우 검사에서도 두 수의 범위나 결과의 범위를 따로 계산하지 않고, 단순히 피연산자와 연산 결과의 부호만을 비교하여 판단할 수 있다.

또한, 하드웨어 수준에서는 부호 있는 덧셈과 부호 없는 덧셈의 하위 w비트 계산 결과가 동일한 특성을 가진다.

2.3. 정수 곱셈 (Integer Multiplication)

두 비트 정수의 실제 곱(true product) 은 최대 개의 비트가 필요할 수 있다.

C언어에서는 이 중 하위 비트만을 결과로 저장한다.

  • 부호 없는 곱셈
    • UMult(u, v) = (u * v) mod 2^w 와 같이 모듈러 연산으로 구현된다.
  • 부호 있는 곱셈
    • 부호 없는 곱셈과 마찬가지로 하위 w비트만을 취하며, 이 비트들은 부호 없는 곱셈의 결과와 동일하다.

2의 거듭제곱 곱셈

컴퓨터에서 는 u << k와 같이 왼쪽 시프트 연산으로 최적화될 수 있다.

대부분의 CPU는 곱셈 연산보다 시프트와 덧셈 연산이 더 빠르기 때문에 컴파일러는 상수에 의한 곱셈을 시프트와 덧셈/뺄셈의 조합으로 변환한다.

2.4. 2의 거듭제곱 나눗셈 (Integer Division)

정수 나눗셈, 특히 2의 거듭제곱으로 나누는 연산은 오른쪽 시프트로 최적화될 수 있다.

  • 부호 없는 나눗셈
    • 는 논리 오른쪽 시프트인 u >> k를 통해 효율적으로 계산할 수 있으며, 이는 (내림)와 같다. (반올림 비트가 전부 잘려나간다)
  • 부호 있는 나눗셈
    • C언어는 나눗셈 결과를 0을 향해 버림(round toward zero) 하도록 정의한다.
      • 양수의 경우, 산술 오른쪽 시프트 x >> k는 와 같으므로 올바른 결과를 생성한다.
      • 음수의 경우, 산술 시프트는 기본적으로 음의 무한대를 향해 버림(round down) 하기 때문에 0을 향해 버리려는 C언어의 요구사항과 다르다! 예를 들어, -7/4는 산술 시프트 시 -2가 되지만, C에서는 -1이 되어야 하는 문제가 생긴다.

편향(Biasing)

2의 거듭제곱 나눗셈에 대한 산술 오른쪽 시프트는 항상 음의 무한대로 버리기 때문에 데이터 전체에 편향을 만들 수 있다.

따라서 이 문제를 해결하기 위해, 음수 x를 k비트 시프트하기 전에 편향 값 을 더해주는 기법을 사용하며 이를 편향(Biasing) 이라 한다. 이 편향은 버림으로 인해 손실될 값을 보상하여 0을 향한 버림이 올바르게 수행되도록 한다.

3. 부동소수점 (Floating Points)

3.1. 소수 표현 (Representing Fractions)

컴퓨터에서 유한한 비트를 사용하여 소수를 표현하는 데에는 몇 가지 접근 방식이 존재한다.

고정소수점 (Fixed-Point)

정수의 특정 비트들을 소수 부분을 나타내는 데 할당하는 방식이다.

예를 들어, 32비트 정수에서 1비트는 부호, 17비트는 정수부, 14비트는 소수부로 사용하는 ‘17.14’ 표현 방식이 있다.

이 방식은 단순히 표현 뿐 아니라 뿐만 아니라 덧셈, 곱셈 등의 연산에서 쓰이는 정수 연산 장치를 그대로 활용할 수 있어 간단하고 빠르다. 그럼에도 표현할 수 있는 수의 범위가 제한적이라는 명백한 단점이 있다.

부동소수점 (Floating Point)

부동소수점은 실수를 형태로 표현하는 방식이다. 여기서 는 부호(Sign), 은 가수(Mantissa 또는 Significand), 는 지수(Exponent)를 의미한다.

이 방식은 지수를 사용하여 소수점의 위치를 움직이므로 ‘떠다닌다(floating)‘는 의미를 가지며, 매우 큰 수부터 매우 작은 수까지 넓은 범위의 수를 표현할 수 있다.

또한 32비트 FP, 64비트 FP, TF 자료형 등에 대해 가수부분과 지수부분의 비율과 크기를 다르게 함으로써 다양한 범위의 수에 대해 유동적으로 표현할 수 있다. 여기에 더해 산술 연산을 위한 하드웨어 지원이 표준화되어 수치 계산의 신속성, 일관성과 신뢰성을 보장한다.

다른 특징으로는 수 자체의 크기(절댓값)에 따라 자료형이 보장하는 정밀도가 달라진다. 이는 큰 소수에 대해, 수 자체의 크기에 대한 상대적인 오차의 비율 한계는 유지되지만 절대적인 오차 자체는 커질 수 있음을 의미한다.

3.2. IEEE 754 표준 (IEEE 754 Standard)

1985년에 제정된 IEEE 754는 부동소수점 연산에 대한 국제 표준이다. 9이전까지 존재했던 다양한 부동소수점 형식을 통일하고, 반올림, 오버플로우, 언더플로우 등에 대한 명확한 규칙을 제공하여 수치 계산의 신뢰성과 이식성을 높였다.

부동소수점은 다음과 같은 세 부분으로 구성된다.

  1. 부호 (Sign): 1비트, 양수(0) 또는 음수(1)를 나타낸다.
  2. 지수 (Exponent): 비트, 지수 값 를 인코딩한다.
  3. 가수 (Mantissa/Fraction): 비트, 유효 숫자인 을 인코딩한다.

주요 정밀도는 다음과 같다.

  • 단정밀도 (Single Precision, float): 32비트 (부호 1, 지수 8, 가수 23)
  • 배정밀도 (Double Precision, double): 64비트 (부호 1, 지수 11, 가수 52)

3.3. 값의 종류 (Types of Values)

IEEE 754 표준은 지수 필드의 값에 따라 수를 여러 종류로 나누어 표현하며, 이를 통해 일반적으로 표현할 수 없는 특수한 값들을 지원한다.

정규화된 값 (Normalized Values)

지수 필드 가 모두 0이거나 모두 1이 아닌 경우의 값으로 다음의 계산 규칙에 따라 수를 표현한다.

  • 지수 는 exp 필드의 값에서 편향(Bias) 값을 빼서 계산한다. (). 단정밀도(float)의 편향은 127, 배정밀도(double)는 1023이다.

  • 가수 은 항상 ‘1.‘로 시작한다고 가정하고 소수 부분만 저장하여 추가적인 정밀도를 얻는다. 이를 암시적 선행 1(implied leading 1)이라 한다. 따라서 가수 은 형태로 계산되며, 여기서 는 가수 필드에 저장된 비트들이 나타내는 소수 값이다.

비정규화된 값 (Denormalized Values)

지수 필드 가 모두 0인 경우의 값으로 다음의 계산 규칙에 따라 수를 표현한다.

  • 지수 으로 고정한다.
  • 가수 은 암시적 선행 1 없이 형태로 계산한다.

왜 굳이 Normalized와 구별되는 계산 규칙을 세웠을까?

만약 float 자료형에서, Denormalized의 계산 규칙 없이 Normalized의 경우처럼 지수 로 계산해보자. 또한, 0을 표현하기 위해 부호 비트(MSB)를 제외한 모든 비트가 0일 때를 0으로 정의하자.

이 규칙 아래에서, 부호를 신경쓰지 않는다고 할 때 표현 가능한 0이 아닌 절댓값이 가장 작은 수는 이다. 이보다 0에 더욱 가까운 작은 수들을 표현하고 싶어도, 더이상 표현하지 못하고 0으로 보내버릴 수밖에 없으며, 이는 0 주변에 표현할 수 없는 ‘간격’이 생겨 정밀도 손실이 발생시킨다.

여기서 Denormalized 규칙을 적용하면, 표현 가능한 0이 아닌 절댓값이 가장 작은 수는 로 0에 더 가까운 수를 표현할 수 있게 된다.

이처럼 0으로 갑자기 값이 떨어지는 언더플로우(underflow) 대신 점진적인 언더플로우(gradual underflow) 를 구현할 수 있게 된다.

특별한 값 (Special Values)

지수 필드 가 모두 1인 경우의 값으로 다음의 규칙에 따라 수를 표현한다.

  • 가수 필드 이 모두 0이면 무한대() 를 나타낸다.
    • 이는 단정밀도 혹은 배정밀도의 최대 표현 범위를 넘어가 오버플로우가 발생한 연산 혹은, 0으로 나누는 연산(예: 1.0 / 0.0) 등의 결과로 사용된다.
  • 가수 필드가 0이 아니면 NaN(Not-a-Number) 을 나타내며, 실수에서 정의되지 않는 연산( 등) 혹은, 수의 개념으로 나타낼 수 없는 결과( 등)의 결과로 사용된다.

3.4. 반올림 및 연산 (Rounding & Operations)

Floating Point 자료형은 부동 소수점 형식으로 표현할 수 없는 값에 대해 가장 가까운 표현 가능한 값으로 만들려 하고, 이를 위한 반올림과 연산에 대한 규칙이 정의된다.

반올림 (Rounding)

부동소수점 형식으로 표현할 수 없는 값은 가장 가까운 표현 가능한 값으로 만들어야 한다. IEEE 754는 네 가지 반올림 모드를 정의하며, 기본 모드는 짝수로 반올림 (Round-to-even) 하는 것이다.

이 방식은 정확히 중간에 있는 값을 올림하거나 내림할 때 마지막 비트가 짝수가 되도록 만들어, 특정 방향으로 치우치는 통계적 편향을 피한다. (만약 0.5를 항상 1로 반올림한다면, 극단적으로 모든 표본값이 0.5인 데이터에 대해서는 +0.5의 편항이 생길 수 있다.)

덧셈 및 곱셈

  • 덧셈
    • 두 수의 지수를 맞추기 위해 소수점을 정렬하고(가수를 시프트), 가수를 더한 후 결과를 다시 정규화하고 반올림한다.
  • 곱셈
    • 부호는 XOR 연산으로, 지수는 덧셈으로, 가수는 곱셈으로 계산한 후, 결과를 정규화하고 반올림한다.

3.5. 부동소수점의 한계

부동소수점 연산은 실제 실수의 연산과 다르며, 교환 법칙은 성립하지만 결합 법칙이나 분배 법칙은 성립하지 않을 수 있다.

예를 들어, (3.14 + 1e20) - 1e20은 3.14 + (1e20 - 1e20)와 다른 결과를 낳을 수 있는데, 이는 매우 큰 수와 작은 수를 함께 연산할 때 정밀도 손실(rounding error) 이 발생하기 때문이다.

이러한 특성은 컴파일러 최적화나 수치 해석 프로그래밍을 복잡하게 만드는 요인이 되며, 이를 보정하기 위해 나오는 수/과학적 수치해석 라이브러리들은 정밀도 손실을 최소화하기 위한 특별한 알고리즘을 구현한다.

4. 바이트 순서 (Byte Ordering)

4.1. 메모리 모델과 워드 크기 (Memory Model & Word Size)

w

프로그래머의 관점에서 메모리는 개념적으로 매우 큰 바이트(byte)의 배열로 볼 수 있다. 각 컴퓨터는 데이터를 처리하는 기본 단위인 “워드 크기(word size)” 를 가지며, 이는 정수형 데이터와 주소(포인터)의 기본 크기가 된다.

과거에는 대부분 32비트(4바이트) 워드를 사용했지만, 이는 주소 공간을 4GB로 제한하여 메모리 집약적인 애플리케이션에 한계가 있었다. 현재는 64비트(8바이트) 워드 크기를 사용하는 추세이며, 이는 이론적으로 18EB (엑사바이트)에 달하는 거대한 주소 공간을 가능하게 한다.

32비트 시스템 주소공간 크기 계산

대부분의 컴퓨터에서 주소는 바이트 단위로 처리된다. 따라서 32bit로 표현할 수 있는 숫자 에 각 바이트마다 숫자를 부여하였을 때 총 크기의 메모리를 가리킬 수 있게 된다.

데이터는 워드 크기의 배수 또는 약수 형태의 다양한 크기로 저장될 수 있으며, 항상 바이트 단위로 정렬된다. (즉, 이론적으로 하나의 비트만 필요한 bool 자료형의 경우에도 1바이트를 차지하게 된다.)

w

4.2. 바이트 순서 (Byte Ordering)

여러 바이트로 구성된 데이터(e.g. 4바이트 int)를 메모리에 저장할 때, 바이트를 배열하는 방식에 대한 두 가지 규약이 존재한다. 이를 엔디언(Endianness) 이라 한다.

  • 빅 엔디언 (Big Endian)
    • 가장 중요한 바이트 (Most Significant Byte, MSB), 즉 사람이 숫자를 읽고 쓰는 순서대로 가장 큰 단위의 바이트를 낮은 메모리 주소에 저장하는 방식이다.
    • 대표적으로 Sun SPARC, PowerPC Mac, 그리고 인터넷 프로토콜(네트워크 바이트 순서)에서 이 방식을 사용한다.
  • 리틀 엔디언 (Little Endian)
    • 가장 덜 중요한 바이트 (Least Significant Byte, LSB), 즉 가장 작은 단위의 바이트를 낮은 메모리 주소에 저장하는 방식이다.
    • 현대의 많은 CPU (Intel x86 계열 CPU와 ARM 프로세서(Android, iOS) 등)에서 이 방식을 사용한다.

빅 엔디언과 리틀 엔디언으로 4바이트 정수 0x0A0B0C0D를 주소 a에 저장하면 다음과 같다.

       [Big]  [Little]
a     : 0A   :   0D
a + 1 : 0B   :   0C
a + 2 : 0C   :   0B
a + 3 : 0D   :   0A
 
------------------------------------
 
   [Big] XX 0A 0B 0C 0D XX XX XX ...
[Little] XX 0D 0C 0B 0A XX XX XX ...

위 비교에서 언뜻 보면 빅 엔디언이 우리가 보기에도 자연스럽고 메모리에 접근해 값을 읽는 과정에서도 자연스러워 보인다.

하지만, 대부분의 CPU 연산은 주로 LSB 영역에서 이루어진다. 이때, 빅 엔디언으로 메모리 주소를 다루고 있다면, 특정 값의 LSB 파트를 읽기 위해서는 메모리 주소에 오프셋을 더하는 추가적인 계산이 필요하다. 반면 리틀 엔디언은 LSB가 낮은 주소에 위치하므로, CPU가 LSB에 직접 접근하여 연산을 수행하기에 더 효율적이다.

이처럼 리틀 엔디언이 연산의 입장에서 더 효율적인 구조를 가능하게 하므로 현대의 CPU에서 많이 사용하고, 반면 빅 엔디언은 연산보다는 데이터를 읽고 전송하고 쓰는 과정에서 더 자연스럽고 직관적이기에 네트워크 통신 등에 사용한다.

따라서 로우레벨에서 네트워크 프로그래밍이나 다른 시스템과 파일 공유를 하는 경우, 프로그래머는 항상 데이터의 바이트 순서를 인지하고 적절히 변환해주는 과정을 고려해야 한다.

char[]에서의 Byte Ordering

간혹 char[]와 같은 배열에서 Byte Ordering을 신경쓰는 경우가 있는데,

  1. char은 그 크기가 1Byte로 Byte간 순서 지정에 영향을 받지 않는다.
  2. 배열 인덱싱에서 배열은 그 타입에 관계없이, 그 자체로 메모리 주소의 연속적인 나열이다. 배열의 요소에 인덱스로 접근할 때에는 각 요소의 주소가 항상 순차적으로 증가하며, 따라서 배열 자체의 순서는 엔디언과 무관하다.

5. 프로그램의 기계 수준 표현 (Machine-level Representation of Programs)

5.1. ISA (Instruction Set Architecture)

컴퓨터 프로그램은 본질적으로 데이터(재료)와 명령어(조리법)의 집합으로 볼 수 있다. 컴퓨터 시스템에서 중앙 처리 장치(CPU)는 메모리로부터 명령어와 데이터를 가져와 처리하는 역할을 수행한다.

w

ISA (Instruction Set Architecture) 는 소프트웨어와 하드웨어 사이의 인터페이스를 정의하는 규약이다. 이는 프로그래머(컴파일러, 운영체제 포함)가 기계의 동작을 이해하기 위해 알아야 할 모든 것을 포함하며, 실제 하드웨어 구현의 복잡한 세부 사항은 추상화한다. ISA는 다음과 같은 요소들을 정의한다.

  • 명령어 집합 (Instruction set): CPU가 실행할 수 있는 모든 명령어의 목록
  • 프로세서 레지스터 (Processor registers): CPU 내에 위치한 매우 빠른 저장 공간
  • 프로그램 카운터 (Program Counter, PC): 다음에 실행할 명령어의 메모리 주소
  • 데이터 타입 및 표현: 기계가 다룰 수 있는 데이터의 종류와 형식
  • 메모리 주소 지정 방식 (Memory addressing modes): 메모리 내의 데이터에 접근하는 방법

소프트웨어와 하드웨어 사이의 인터페이스라는 말이 추상적으로 들릴 수 있다. 이를 좀 더 구체적으로 설명하자면, ISA는 하드웨어가 이해할 수 있는 언어이자 소프트웨어가 하드웨어에게 명령을 내리는 방법이라고 할 수 있다.

서로 다른 CPU는 서로 다른 ISA를 가지며, 이는 곧 서로 다른 기계어, 즉 언어를 사용함을 말한다. C언어에서 출력을 위해서는 printf를, 파이썬에서는 print, 자바스크립트에서는 console.log를 쓰고, 그마저도 각각의 사용 방법과 내부 동작 방식이 다 다른 것과 비슷한 것이다.

이처럼 같은 동작 (e.g. 메모리 접근, 덧셈 연산 등)을 위해서도 CPU마다 다른 기계어 명령어를 사용하여야 하며, 이를 표준화하여 잘 정리한 것이 바로 ISA이다.

5.2. x86-64 아키텍처 (x86-64 Architecture)

Intel의 x86 아키텍처는 1978년 16비트 프로세서인 8086에서 시작하여 점진적으로 발전해왔다. 이 아키텍처는 하위 호환성을 유지하며 새로운 기능을 계속 추가해왔고, 현재 데스크톱, 노트북, 서버 시장을 지배하고 있다.

x86은 축소 명령어 집합 컴퓨터(Reduced Instruction Set Computer, RISC) 가 아닌 복잡 명령어 집합 컴퓨터(Complex Instruction Set Computer, CISC) 로, 다양하고 복잡한 형식의 많은 명령어를 가지고 있다.

초기 32비트 IA32 아키텍처에서 64비트로의 전환 과정에서, AMD는 x86-64라는 혁신적인 64비트 확장 아키텍처를 개발했다. 이에 대응하여 Intel도 거의 동일한 기술인 EM64T(현재 Intel 64)를 발표하며 현재의 64비트 표준이 정립되었다.

5.3. 컴파일과 어셈블리 (Compilation and Assembly)

C언어로 작성된 소스 코드가 실행 가능한 프로그램이 되기까지는 다음과 같은 과정을 거친다.

  1. 컴파일러 (Compiler): C 소스 코드(.c)를 어셈블리 코드(.s)로 번역한다. 어셈블리 코드는 기계어에 대한 텍스트 표현이다.
  2. 어셈블러 (Assembler): 어셈블리 코드(.s)를 기계어인 목적 코드(.o)로 변환한다. 이 파일은 명령어의 바이너리 인코딩을 포함하지만, 아직 완전한 실행 파일은 아니다.
  3. 링커 (Linker): 여러 목적 코드 파일들을 하나로 합치고, printf와 같은 라이브러리 함수들의 코드를 연결하여 최종 실행 파일(p)을 생성한다.

기계어(Machine Code) 는 프로세서가 직접 실행하는 바이트 수준의 프로그램이며, 어셈블리어(Assembly Code) 는 이를 사람이 읽을 수 있는 텍스트 형태로 표현한 것이다.

또한, objdump나 gdb와 같은 디버깅 도구를 사용하면, 기계어를 어셈블리어로 변환하는 디스어셈블(disassemble) 과정을 수행할 수 있다.

5.4. 어셈블리 코드의 특징 (Assembly Code Characteristics)

어셈블리 수준에서는 1, 2, 4, 8바이트 크기의 정수형 데이터와 4, 8, 10바이트 크기의 부동소수점 데이터만 존재한다. 배열이나 구조체와 같은 복합 데이터 타입은 단지 메모리 상에 연속적으로 할당된 바이트 덩어리로 취급된다.

또한, 어셈블리 명령어는 크게 세 종류로 나뉜다.

  • 레지스터나 메모리 데이터에 대한 산술/논리 연산 수행.
  • 메모리와 레지스터 간의 데이터 전송 (Load, Store).
  • 프로그램의 실행 흐름을 제어하는 제어 전송 (분기, 점프, 프로시저 호출).

어셈블리는 주로 AT&T 문법(GNU 기본값)과 Intel 문법 두 가지가 사용되며, 피연산자의 순서나 상수, 주소 지정 방식 표기에 차이가 있다.

6. 어셈블리 I: 기본 연산 (Assembly I: Basic Operations)

다음은 x86-64 기반 어셈블리 언어의 기본 연산(비트 이동, 주소 계산, 산술/논리 연산 등) 을 다룬 정리이다. 이 단계는 고수준 언어(C, C++ 등)에서 작성한 코드가 실제 기계에서 어떻게 동작하는지 이해하는 핵심이다.

6.1. 기본 실행 환경 (Basic Execution Environment)

CPU는 연산을 수행하기 위해 내부에 레지스터(Register) 라는 매우 빠른 저장 공간을 가지고 있다. x86-64 아키텍처에서 주로 사용되는 일반 목적 레지스터는 다음과 같다.

64비트32비트16비트하위 8비트용도
%rax%eax%ax%al / %ah누산기 (Accumulator)
%rbx%ebx%bx%bl / %bh베이스 레지스터 (Base)
%rcx%ecx%cx%cl / %ch카운터 (Counter )
%rdx%edx%dx%dl / %dh데이터 (Data)
%rsi%esi%si%sil소스 인덱스 (Source Index)
%rdi%edi%di%dil목적지 인덱스 (Destination Index)
%rbp%ebp%bp%bpl베이스 포인터 (Base Pointer)
%rsp%esp%sp%spl스택 포인터 (Stack Pointer)

추가로 %r8 ~ %r15 레지스터까지 총 16개의 64비트 일반 목적 레지스터를 사용할 수 있다.
또한 부동소수점 연산용 레지스터(XMM, YMM, ZMM)와 FPU/MMX 레지스터도 존재한다.

6.2. 데이터 이동 (Moving Data)

어셈블리에서 가장 기본적인 명령어는 데이터를 이동시키는 것이다.

6.2.1. mov 명령어

  • 형식
    • mov<T> Src, Dest
      • (<T> = q(8B)|l(4B)|w(2B)|b(1B))
  • 피연산자(Operand) - 즉값 (Immediate): $0x400, $-533와 같이 상수를 직접 사용 - 레지스터 (Register): %rax, %rbx와 같은 16개 일반 목적 레지스터 중 하나 - 메모리 (Memory): ($0x80), (%rax)와 같이 메모리 주소를 지정하여 접근

메모리 → 메모리 전송은 단일 mov 명령으로 불가능하다. 반드시 레지스터를 거쳐야 한다.

movq $0x4, %rax      # 즉값 → 레지스터
movl $-147, (%eax)   # 즉값 → 메모리
movl %eax, %edx      # 레지스터 → 레지스터
movq %rax, (%rdx)    # 레지스터 → 메모리
movq (%rax), %rdx    # 메모리 → 레지스터

6.2.2. 주소 지정 방식 (Addressing Modes)

C에서의 포인터 연산은 어셈블리에서 다음과 같은 주소 지정 방식으로 구현된다.

형식의미예시
(R)Mem[Reg[R]] – 단순 참조movq (%rcx), %rax
D(R)Mem[Reg[R] + D] – 변위movq 8(%rbp), %rdx
D(Rb, Ri, S)Mem[Reg[Rb] + S*Reg[Ri] + D] – 일반화movq 0x8(%rdx, %rcx, 4), %rax

이는 배열, 구조체 멤버 등에 접근할 때 자주 쓰인다.

스왑 예제 (Swap Example) 

void swap(long *xp, long *yp) {
   long t0 = *xp;
   long t1 = *yp;
   *xp = t1;
   *yp = t0;
}

컴파일된 어셈블리:

swap:
	movq   (%rdi), %rax   # t0 = *xp
    movq   (%rsi), %rdx   # t1 = *yp
    movq   %rdx, (%rdi)   # *xp = t1
    movq   %rax, (%rsi)   # *yp = t0
    ret

여기서 %rdi와 %rsi는 함수 인자로 전달된 포인터이며, %rax와 %rdx는 임시 변수(t0, t1)를 저장하는 레지스터로 사용된다.

6.3. 데이터 확장 (Data Extension)

0 확장 (Zero Extension)

작은 크기의 데이터를 더 큰 크기로 옮길 때 상위 비트를 0으로 채운다.

참고로, x86-64 아키텍쳐에서 32비트 movl 명령어는 기본적으로 대상 레지스터의 상위 32비트를 0으로 채우도록 설계되어 있기 때문에 movzlq는 존재하지 않는다.

movb $0x9, %al       # 하위 8비트에 0x09 저장
movzbq %al, %rbx     # 상위 비트 0으로 채우며 확장

부호 확장 (Sign Extension)

부호 있는 값을 확장할 때는 MSB를 복사하여 채운다.

cltq는 암묵적으로 피연산자가 %eax, %rax로 고정된 특수 명령어이다.

6.4. 산술 및 논리 연산 (Arithmetic & Logical Operations)

  • 이항 연산 (Two-Operand)
    • 사칙 연산
      • add<T> S D :
      • sub<T> S D :
      • mul<T> S D : (unsigned)
      • imul<T> S D : (signed)
    • 시프트 연산
      • sal<T> S D : (=shl<T>)
      • sar<T> S D : (산술 오른쪽 시프트)
      • shr<T> S D : (논리 오른쪽 시프트)
    • 논리 연산
      • and<T> S D :
      • or<T> S D :
      • xor<T> S D :
  • 단항 연산 (One-Operand)
    • inc<T> : D = D + 1
    • dec<T> : D = D - 1
    • neg<T> : D = -D
    • not<T> : `D = ~D

6.5. 주소 계산 명령어 (LEA)

lea<T>는 메모리에 접근하지 않고 주소 계산만 수행하는 명령어이다. 전용 연산 파이프라인을 통과하기 때문에 일반적인 imul, add보다도 빠르며, 이 때문에 단순 포인터 연산뿐만 아니라 곱셈을 포함한 산술 계산에도 활용된다.

leaq (%rdi, %rdi, 2), %rax   # %rax = x + 2*x = 3x
salq $2, %rax                # %rax = 12x

6.6. 특수 산술 연산 (Special Arithmetic Operations)

64비트 × 64비트 곱셈 결과는 128비트가 필요하다. 이를 위해 다음 명령어를 사용하며, 피연산자는 %rax로 고정된다.

명령어설명
imulq S%rdx:%rax ← S × %rax (부호 있는 곱셈)
mulq S%rdx:%rax ← S × %rax (부호 없는 곱셈)
cqto%rdx:%rax ← SignExtend(%rax)
idivq S%rax = %rdx:%rax / S
%rdx = %rdx:%rax mod S (부호 있는 나눗셈)
divq S(부호 없는 나눗셈)

6.7. CISC 아키텍처 특성

x86-64는 CISC(Complex Instruction Set Computer) 구조로, 다음 특징을 가진다.

  • 명령어는 즉값, 레지스터, 메모리 참조를 모두 지원
  • 산술 연산에서도 피연산자로 메모리 사용 가능
  • 복잡한 주소 계산 가능: Rb + S*Ri + D
  • 명령어 길이가 가변적 (1~15바이트)

7. 어셈블리 II: 제어 흐름 (Assembly II: Control Flow)

이제 우리는 C언어의 제어 구조(Control Structure) — 조건문, 반복문, switch문 — 가 실제 기계 수준에서 분기(Branch), 점프(Jump), 조건 코드(Condition Codes) 등을 통해 어떻게 구현되는지 살펴본다. 이는 고급 언어와 하드웨어 간의 동작 원리를 연결하는 핵심이다.

7.1. 프로세서 상태 (Processor State)

x86-64 프로세서는 명령어 실행과 흐름 제어를 위해 다음과 같은 주요 상태 정보를 가진다

  • 일반 목적 레지스터 (General-purpose registers)
    임시 데이터 저장용 (%rax, %rbx, … %r15)
  • 스택 포인터 (%rsp) – 현재 스택의 꼭대기
  • 베이스 포인터 (%rbp) – 현재 스택 프레임의 기준
  • 명령어 포인터 (%rip) – 다음 실행할 명령어의 주소
  • 상태 플래그 레지스터 (%rflags) – 연산 결과의 조건 코드 저장

7.1.1. 명령어 포인터 (Instruction Pointer, RIP)

%rip 레지스터는 다음 실행할 명령어의 주소를 저장하는 레지스터로, 코드의 순차 실행시에 한 명령어에서 다음 명령어로 자동 증가한다.

컴퓨터는 이 %rip 레지스터의 값을 참고하여 다음으로 실행될 명령어 위치를 알아내는데, 이를 이용하면 jmp, jcc, call, ret 등 %rip의 값을 직접 수정하는 명령어를 통해 다음 실행 코드를 지정하여 분기 또는 함수 호출을 구현할 수 있다.

이러한 레지스터%rip는 소프트웨어가 임의로 직접 접근할 수 없으며, 정해진 제어 전송 명령어나 예외/인터럽트를 통해서만 변경된다.

7.1.2. 조건 플래그 (Condition Flags) – RFLAGS 레지스터

RFLAGS는 주로 직전 산술/논리 연산 결과에 대한 상태 정보를 저장하는 레지스터로 다음과 같이 구성된다.

플래그의미
CF (Carry Flag)부호 없는 연산에서 캐리 또는 차용 발생 여부
PF (Parity Flag)결과의 LSB 바이트에서 1의 개수가 짝수인지 여부
AF (Adjust Flag)BCD 연산에서 3번째 비트에서 캐리/차용 발생 여부
ZF (Zero Flag)결과가 0인지 여부
SF (Sign Flag)결과의 부호 (MSB)
OF (Overflow Flag)부호 있는 연산에서 오버플로우 여부
DF (Direction Flag)문자열 명령에서 증감 방향

주로 위 표에서 굵게 표시된 플래그가 중요하게 사용되며, 조건부 점프 및 설정 명령어에서 기준으로써 사용된다.

7.1.3. 조건 코드 설정 (Condition Codes)

암묵적 설정 (Implicit Setting)

addq, subq 등 산술 연산 시 자동으로 RFLAG가 설정되는 것을 암묵적 설정 (Implicit Setting) 이라 한다.

  • CF: 부호 없는 오버플로우 감지
  • ZF: 결과가 0인지
  • SF: 결과가 음수인지
  • OF: 부호 있는 오버플로우 감지 ()

단, leaq, incq, decq는 조건 코드를 변경하지 않는다.

명시적 설정 (Explicit Setting)

아래의 특정한 명령어들은 결과를 저장하지 않고 연산을 수행하며, 조건 플래그를 명시적으로 설정 (Explicit Setting) 할 때 사용한다.

  • cmp<T> S R – 비교 명령어
    • 두 피연산자의 차이()를 계산하여 조건 플래그를 설정한다.
      • ZF:
      • SF:
      • CF: 캐리 발생 (부호 없는 비교용)
      • OF: 부호 있는 오버플로우 발생 여부
  • test<T> S R – 비트 마스크 검사
    • 두 피연산자의 비트 AND()를 계산하여 조건 플래그를 설정한다.
      • ZF: ()
      • SF: ()
      • CF, OF: 0으로 클리어

7.1.4. 조건 코드 판독 (Reading Condition Codes)

setX 명령어는 조건 코드(RFLAG)에 따라 8비트 레지스터를 0 또는 1로 설정한다. 이때 피연산자는 8비트 레지스터(이다.

명령어조건의미
sete ZF같다
setne ~ZF다르다
sets SF음수
setns ~SF음수가 아님
setg ~(SF ^ OF) & ~ZF(>) (signed)
setge ~(SF ^ OF)() (signed)
setl (SF ^ OF)(<) (signed)
setle `(SF ^ OF)ZF`
seta ~CF & ~ZF(>) (unsigned)
setae ~CF(\geq) (unsigned)
setb CF(<) (unsigned)
setbe `CFZF`

7.1.5. 조건 분기 (Conditional Branch)

jX 명령어는 조건 코드(RFLAG)에 따라 분기한다.

명령어조건의미
jmp무조건무조건 점프
jeZF같을 때
jne~ZF다를 때
jg~(SF ^ OF) & ~ZF(>) (signed)
jge~(SF ^ OF)(\geq) (signed)
jl(SF ^ OF)(<) (signed)
jle`(SF ^ OF)ZF`
ja~CF & ~ZF(>) (unsigned)
jbCF(<) (unsigned)

조건부 분기를 이용한 max 구현

또한 이와 비슷한 것으로 조건부 이동(cmovX) 이 있다.

cmpq %rsi, %rdi
movq %rsi, %rax
cmovge %rdi, %rax
ret

cmov는 if (Test) Dest <- Src와 같은 형태로 동작한다. 즉, 특정 조건(Test)이 참(true)일 때만 Src의 값을 Dest로 옮긴다. 이러한 명령어들은 setX 명령어와 유사하게 조건 코드(RFLAGS)를 기반으로 작동하지만, 레지스터에 0 또는 1을 쓰는 대신 데이터 자체를 이동시킨다는 점에서 차이가 있다.

예를 들어, cmovge %rdi, %rax 명령어는 (SF ^ OF) 조건이 거짓일 때(즉, “greater or equal” 조건이 참일 때) %rdi의 값을 %rax로 이동시킨다.

조건부 이동을 이용한 max 구현

왜 조건부 이동을 쓰나요?

기존의 jX와 같은 조건부 분기(Conditional Branch) 명령어는 파이프라인(pipeline) 을 통해 명령어 흐름에 큰 혼란을 줄 수 있다. 프로세서는 다음 실행될 명령어를 미리 예측하여 파이프라인을 채우는데, 분기 예측이 틀리면 파이프라인에 있던 명령어를 모두 버리고 다시 채워야 하므로 성능 저하가 발생했다.

이와 달리, 조건부 이동은 조건이 충족되지 않더라도 해당 명령어를 실행하되, 실제 데이터 이동만 발생하지 않을 뿐 제어 흐름을 다른 곳으로 전환하지 않는다.

조건부 이동은 만능인가요?

위의 내용을 보면 조건부 분기보다는 조건부 이동이 항상 좋아보일 수 있지만, 결코 그렇지 않다.

조건부 분기는 먼저 조건문을 검사하고, 그 결과에 따라 연산 흐름 자체를 바꾼다. 하지만, 조건부 이동은 각 조건문에 따라 가능한 연산 흐름을 미리 다 따라가며 그 결과를 저장해 놓고, 가장 마지막에 조건문을 검사하여 결과 값을 대체하는 방식이다. 이로써 다음의 문제를 발생시킬 수 있다.

1. 고비용 연산 (Expensive Computations)

각 조건 분기 내의 연산 흐름이 매우 고비용 연산인 경우에도 필요 없는 분기에서의 결과마저 연산하므로, 단순히 분기예측에 실패한 경우보다도 더 자원을 낭비할 수 있다.

2. 위험한 연산 (Risky Computations)

조건부 이동에서 각 분기 흐름을 모두 미리 계산하는 것은 때때로 조건문을 통해 만든 안전 가드를 통과할 위험이 있다. 예를 들어, 조건문이 널 포인터 역참조를 막는 역할(val = p ? *p : 0;)로 사용할 때 조건부 이동을 사용해버리면, 오히려 널 포인터 역참조 연산을 미리 수행하는 과정에서 예외를 발생시킬 수 있다.

3. 부작용이 있는 연산 (Computations with Side Effects)

각 분기 흐름을 미리 연산하는 과정에서, 자칫 예상하지 못한 사이드 이펙트를 발생시킬 수 있다. 예를 들어 val = (x >= 0) ? x *= 7 : x += 3; 와 같은 코드에서 조건이 참이더라도, x += 3 연산이 실행되어 x의 값이 의도치 않게 변경될 수 있다.

따라서, 이러한 경우에 대해 고려하며 조건부 분기와 조건부 이동 중 적절한 방식을 취해야 한다.

7.2. 반복문 (Loops)

c언어에서의 반복문은 대부분 while, 혹은 for 로 작성되며, 또한 현대에 와서 그렇게 작성하는 것이 권장된다. 그렇지만, 결국 분기는 jump로 결정되는 것이기에 어셈블리어에서의 표현은 goto를 이용해 표현된다.

7.2.1. While 루프

while 루프는 다음과 같은 goto 버전으로 재작성될 수 있다.

First Goto Version

  • C 언어의 while 루프가 “조건을 먼저 확인하고, 참일 경우 본문을 실행”하는 방식을 가장 직관적으로 번역한다.
  • 루프의 각 반복(iteration)은 항상 loop: 레이블에서 시작하여 조건을 검사한 후에 본문을 실행할지 결정한다.
  • 루프 조건이 처음부터 거짓일 경우, goto done;에 의해 본문은 한 번도 실행되지 않는다.

Second Goto Version

Second Goto Version은 GCC와 같은 컴파일러가 실제로 while 루프를 어셈블리로 변환할 때 자주 사용하는 최적화된 전략 중 하나이다.

  • 초기 조건 검사(if (!(x > 1)) goto done;):
    • while 루프가 처음부터 조건을 만족하지 않아 본문이 한 번도 실행되지 않아야 하는 경우를 처리한다.
  • do-while 유사한 내부 루프:
    • loop: 레이블부터 if (x > 1) goto loop;까지의 블록은 do-while 루프처럼 본문을 먼저 실행하고 그 다음에 조건을 검사한다. 이는 while 루프의 첫 번째 반복이 끝난 후부터 다음 반복으로 넘어갈 때의 동작을 효율적으로 표현한다.

이러한 방식은 조건 검사 위치를 분리하여, 루프 내의 분기 명령어를 줄이거나 파이프라인 효율성을 높이는 데 유리할 수 있다.

결국 loop 내부의 분기는 한번으로 동일한 것 아닌가요?

First/Second goto version을 비교하였을 때, 효율적임이 잘 보이지 않을 수 있다. 두 버전 모두에서 조건문 검사는 1회 이루어지며, 루프 한번을 돌기 위한 점프 또한 동일하게 1회 이루어지는 것처럼 보이기 때문이다.

  • First Version
    1. 조건검사(!(x > 1))이 실패함
    2. 무조건 goto loop가 실행됨
  • Second Version
    1. 조건검사 (x > 1)이 성공함
    2. 무조건 goto loop가 실행됨

그러나 이를 어셈블리어 수준에서 생각하면 달라진다. 조건부 분기 jX는 조건검사와 동시에 일어날 수 있었다. 즉, j명령어 자체에 조건검사가 포함된다는 것이다. 따라서 어셈블리어 수준에서는 다음과 같이 실행된다.

  • First Version
    1. 조건검사 (!(x > 1))이 실패함
    2. 무조건 j가 실행됨
  • Second Version
    1. 조건검사 (x > 1)이 성공하면 jg가 실행됨

이 경우 Second Version에서 실행 코드가 줄어들어 더 효율적임을 알 수 있다.

위에서 본 것처럼, C 코드를 어셈블리로 변환하는 방식은 한 가지만 있는 것이 아니라 여러 가지 최적화 전략이 존재한다. 이는 동일한 고수준 코드가 컴파일러의 구현 방식이나 최적화 수준에 따라 다른 형태의 어셈블리 또는 goto 기반 코드로 변환될 수 있음을 알려주며, 이프로그램의 성능 분석이나 디버깅 시에 중요한 고려 사항이 된다.

7.2.2. For 루프

for 루프는 사실상 while 루프의 문법적 설탕으로, while문으로 변경된 후 이전의 흐름을 따라가며 변환할 수 있다.

7.3. Switch 문과 점프 테이블 (Switch & Jump Tables)

7.3.1. 점프 테이블 구조

스위치(Switch) 문은 프로그래밍에서 여러 가능한 경우(case) 중 하나를 선택하여 실행하는 제어 구조로, if-else if-else 문과 유사하지만, 주로 단일 변수의 값에 따라 분기가 결정될 때 사용된다. while문과 마찬가지로, 어셈블리 수준에서는 이 스위치 문을 구현하는 여러 가지 방법이 있다.

w

연속적인 조건문 (Series of conditionals)

가장 기본적인 구현 방식으로, 스위치 문의 각 case를 일련의 if-else if 문으로 변환한다.

  • 장점: 처리해야 할 case의 수가 적을 때 구현이 간단하고 효율적이다.
  • 단점: case의 수가 많아지면, 각 조건을 순차적으로 검사해야 하므로 실행 속도가 느려진다. (최악의 경우 선형 시간 복잡도)

점프 테이블 (Jump Table)

각 case에 해당하는 코드 블록의 시작 주소를 배열 형태로 저장한 테이블(점프 테이블)을 사용한다. 스위치 변수의 값을 이 테이블의 인덱스로 사용하여 해당 코드 블록의 주소를 찾고, 그 주소로 간접 점프(indirect jump) 를 수행하여 분기한다.

  • 장점: 조건문을 사용하는 대신 한 번의 테이블 조회와 점프만으로 분기가 이루어지므로 매우 효율적이다. case의 수가 많아져도 성능 저하가 거의 없다. (상수 시간 복잡도)
  • 조건: 스위치 변수가 점프 테이블의 인덱스가 되므로, case 레이블이 0, 1, 2와 같이 작고 연속적인 정수 상수 범위일 때 가장 효과적이다. 그렇지 않은 경우 테이블의 크기가 비효율적으로 커지거나, 테이블을 직접 사용할 수 없어 다른 방법을 고려해야 한다.

  • 간접 점프 (jmp *.L4(,%rdi,8))
    • 이 명령어는 x의 값에 따라 점프 테이블(Jump Table)에서 해당 case의 주소를 찾아 그곳으로 실행 흐름을 옮긴다.
    • *: 간접 참조를 나타내며, 지정된 주소에 저장된 값을 최종 목적지 주소로 사용하라는 의미이다.
    • .L4(,%rdi,8): 이는 x86-64 아키텍처의 인덱싱된 메모리 주소 지정 방식이다.
      • .L4: 점프 테이블의 시작 주소(base address)
      • ,%rdi,8: (Base, Index, Scale) 형식에서 Index는 %rdi (즉, x의 값), Scale은 8, x 값을 8과 곱한 후 .L4 주소에 더하여 실제 점프할 주소를 계산

결과적으로 이 주소는 JTab[x]와 동일하게 작동하여, x에 해당하는 case의 코드 블록 주소를 찾아내고, 그곳으로 분기한다.

  • 점프 테이블 (.L4) 구조
    • .section .rodata: .L4 테이블이 읽기 전용 데이터 섹션에 정의되어 있음을 의미한다.
    • .align 8: 데이터가 8바이트 경계에 정렬되어 있음을 의미한다.
      • .quad .L3 # x = 1: x가 1일 때 점프할 주소로 .L3 ( case 1의 코드 블록)을 지정한다.
      • .quad .L7 # x = 5: x가 5일 때 점프할 주소로 .L7 ( case 5의 코드 블록)을 지정한다.
      • .quad .L7 # x = 6: x가 6일 때 점프할 주소로 .L7 ( case 6의 코드 블록)을 지정한다. case 5와 case 6이 동일한 코드 블록(.L7)을 공유하는 것을 볼 수 있다. (즉, fall through 또는 다중 레이블).

이렇듯, 점프테이블 변환에서 컴파일러는 switch 문을 x 값에 따른 점프 테이블을 사용하여 효율적인 간접 점프 코드로 변환합니다.

이진 탐색 트리 (Binary search tree)

case 레이블이 드문드문 떨어져 있거나(sparse cases), case의 값이 매우 큰 정수일 때 사용될 수 있는 방법으로, 스위치 변수의 값을 이진 탐색 트리 구조로 비교하여 해당 case를 찾는다.

  • 장점: case의 수가 많아도 효율적인 로그 시간 복잡도 성능을 가진다.
  • 단점: 점프 테이블보다는 오버헤드가 더 크다.

이러한 구현 방법들 중, 컴파일러가 스위치 문의 특성(case 값의 분포, 개수 등)을 분석하여 가장 효율적인 방식을 선택한다.

8. 어셈블리 III: 프로시저 (Procedures)

프로시저(함수) 호출은 제어 전달, 데이터 전달, 메모리 관리의 세 측면으로 구성된다.

즉, (1) 호출 지점에서 피호출자 시작 지점으로 제어를 넘기고, 종료 시 호출 지점의 다음 명령으로 복귀하며, (2) 인자를 전달하고 반환값을 되돌리며, (3) 실행 동안 필요한 임시 저장공간을 할당/해제한다. 이 모든 것은 기계어 수준의 명령들로 구현된다.

8.1. 스택 (Stack)

스택(Stack) 은 후입선출(LIFO) 규율을 따르는 메모리 영역으로, x86-64에서 (%rsp) 가 스택의 맨 위(top) 주소를 가리킨다. 스택은 낮은 주소 방향으로 성장하는데, 이는 프로시저 호출/복귀의 자연스러운 구조(마지막에 호출된 함수가 먼저 복귀)에 잘 부합한다.

8.1.1. push/pop

  • push<T> Src
  • popq<T> Dest

위 동작을 통해 호출 시 보존해야 할 값(예: 반환 주소, 보존 레지스터 등)을 스택에 적재/회수한다.

8.1.2. 제어 전달 (Control Transfer): call / ret

함수의 호출 (call)과 함수의 반환 (ret) 도 스택을 통해 이루어진다.

함수의 호출 (call label)

  • Procedure Call(call label): 반환 주소(현재 %rip)를 스택에 push한 뒤, label로 무조건 점프한다.
  • Procedure Return(ret): 스택의 맨 위(현재 %rsp)에 저장된 반환 주소를 pop하여 그 위치로 점프한다.

이 두 명령으로 호출 ↔ 복귀의 제어 흐름이 완성된다.

8.2. 데이터 전달 (Passing Data)

8.2.1. 레지스터 인자 (Register Arguments)

앞의 6개 정수/포인터 인자는 다음 순서의 레지스터를 사용한다(암기 구절: Diane’s silk dress costs $89):

  1. %rdi
  2. %rsi
  3. %rdx
  4. %rcx
  5. %r8
  6. %r9

반환값(return value) 은 (%rax)로 전달한다.

8.2.2. 스택 인자 (Stack Arguments)

7번째 이후의 인자는 오른쪽에서 왼쪽 순서로 스택에 push하여 전달한다. 필요할 때만 스택 공간을 실제로 할당한다(argument build 구역).

8.3. 스택 프레임 (Stack Frame)

스택 프레임(Stack Frame) 은 단일 프로시저 인스턴스가 실행되는 동안 필요한 상태를 담는다:

  • 반환 정보: 반환 주소 등

  • 인자(넘치는 부분)

  • 지역 변수 (&) 임시 공간

  • 보존해야 할 레지스터 저장본(saved registers)

  • (선택) 프레임 포인터 (%rbp)

일반적으로 진입 시(set-up) 필요 공간을 할당하고, 종료 시(finish) 해제한다. (%rsp)는 항상 프레임의 위쪽(top)을, (%rbp)는 선택적으로 현재 프레임의 기준을 가리킨다. 재귀/중첩 호출이 일어날수록 프레임이 층층이 쌓였다가 복귀하면서 차례로 제거된다.

8.4. 레지스터 보존 규약 (Register-Saving Conventions)

함수 호출 간 임시값 보존을 위해 호출자 보존(caller-saved) / 피호출자 보존(callee-saved) 규약을 구분한다.

  • 호출자 보존 (caller-saved): (%rax), (%rdi), (%rsi), (%rdx), (%rcx), (%r8), (%r9), (%r10), (%r11)
    → 호출자가 호출 전 스택에 저장해 두었다가, 호출 후 복원해야 한다. (호출 도중 변경될 수 있음)

  • 피호출자 보존 (callee-saved): (%rbx), (%r12), (%r13), (%r14), (%r15), (%rbp)
    → 피호출자가 사용 전 저장(push), 복귀 전 복원(pop) 해야 한다. (호출 전후 동일 보장)

  • (%rsp)는 특수: 프로시저 종료 시 진입 시점 값으로 복구되어야 한다.

주의 (Register Saving Problem)
호출자 함수가 (%rdx)에 중요한 값을 가지고 있는 동안 피호출자가 (%rdx)를 덮어쓰면, 복귀 후 호출자의 계산이 깨진다. 이때 (%rdx)는 caller-saved 이므로 호출자가 미리 스택에 저장해 두어야 한다.

8.5. 예제 1 — swap

void swap (long *xp, long *yp) {
    long t = *xp;
    *xp = *yp;
    *yp = t;
}

어셈블리는 두 포인터 인자 (%rdi = xp), (%rsi = yp)로부터 값을 읽어 레지스터 (%rax, %rdx)에 저장하고, 교차로 다시 쓴 뒤 ret으로 복귀한다. 이 단순 예제는 메모리 ↔ 레지스터 이동과 call/ret의 최소 단위를 잘 보여준다.

8.6. 예제 2 — 재귀 팩토리얼 (rfact)

long rfact(long x) {
    if (x <= 1) return 1;
    long rval = rfact(x-1);
    return rval * x;
}

어셈블리 핵심 흐름:

  1. ((x \le 1)) 검사 (\rightarrow) 기저 사례면 (1) 반환

  2. 그렇지 않으면 (%rbx)에 현재 (x)를 보존(push … %rbx)

  3. ((x-1))로 재귀 호출(call)

  4. 복귀 후 (%rbx)의 (x)와 (%rax)의 결과를 곱셈

  5. 종료 경로에서 (%rbx) 복원(pop … %rbx) (\rightarrow) ret
    여기서 (%rbx)는 callee-saved 이므로 보존/복원이 필수다. 슬라이드에는 (x=3)인 경우의 스택/레지스터 변화를 단계별로 시각화하여, 재귀 호출 중 각 호출 인스턴스가 독립된 스택 프레임을 가지며, 반환 주소/지역 상태가 안전하게 격리되는 과정을 보여준다.

8.7. 스택 기반 언어와 프레임 동작

C/C++/Java 등 재귀를 지원하는 언어는 코드가 재진입 가능(reentrant) 해야 하며, 각 호출 인스턴스의 상태(인자, 지역 변수, 반환 주소)가 프레임 단위로 스택에 저장된다. 호출자는 피호출자보다 먼저 복귀하지 않으며, 이로써 LIFO 규율이 자연스럽게 유지된다. 상호 재귀 또한 동일한 원리로 처리된다.

8.8. 요약 및 점검표

  • 제어 전달: call로 반환 주소 push (\rightarrow) 점프, ret로 pop (\rightarrow) 복귀.

  • 데이터 전달: 인자 1–6은 (%rdi, %rsi, %rdx, %rcx, %r8, %r9) / 반환값은 (%rax). 초과 인자는 스택.

  • 스택 프레임: 반환 정보, 인자(잉여), 지역/임시, 보존 레지스터, (선택) (%rbp).

  • 보존 규약: caller-saved((%rax, %rdi, …, %r11))는 호출자가, callee-saved((%rbx, %r12–%r15, %rbp))는 피호출자가 각각 저장/복원. (%rsp)는 종료 시 원위치.

  • 재귀: 별도 장치 없이도 프레임 분리로 안전히 동작.

이 모든 메커니즘은 프로시저 호출/복귀의 정확성과 상호 간섭 방지를 보장한다.

8.8.1. 부연 설명: 호출 규약(Calling Convention) 과 최적화 관점

  • 호출 규약은 어떤 레지스터에 무엇을 담아 전달/반환할지, 누가 어떤 레지스터를 보존할지, 스택의 어떤 구역에 무엇을 둘지를 표준화한다. 동일 규약을 따르는 컴파일러/라이브러리는 서로의 코드를 안전하게 호출할 수 있다. (플랫폼/ABI에 따라 상세는 달라질 수 있으나, 본 정리는 x86-64/Linux 강의 슬라이드 기준이다.)

  • 최적화 컴파일러는 지역 변수를 레지스터에 보관하여 스택 접근을 줄이고, 필요할 때만 스택 프레임을 잡는다(leaf function 등). 다만 보존 규약은 항상 지켜야 하므로, callee-saved 사용 시 진입/복귀 경로에 push/pop이 꼭 들어간다.

다음 장에서는 이 호출/프레임 체계를 전제로, 프로시저 간 데이터 전달의 다양한 패턴, 배열/구조체 인자 전달의 주소 계산, 가변 인자, 라이브러리 호출과 링커 관점 등을 확장해 살펴보면 전체 실행 모델이 더욱 명확해진다.

그래프 뷰