[CSAPP] 3.6 Controls(제어문)

3.6 Controls(제어문)

C의 반복문 스위치문은 시험결과에 따라 일련의 연산이 실행되는 조건부 실행이 요구됨.

두개의 기본적인 방법을 제공

데이터 값을 시험해서 시험결과에 따라 데이터 흐름을 바꾼다.

데이터 값을 시험해서 결과에 따라 제어흐름을 바꾼다.

보통 C와 기계어코드의 인스트럭션은 모두 프로그램에 나타나는 순서대로 실행된다.

이때 기계어의 인스트럭션은 jump로 변경가능함.

3.6.1 Condition Codes(조건 코드)

CPU는 레지스터와 함께 구성되는데 이 레지스터는 조건부 분기를 수행하는데 쓰일 수 있음.

• CF : 캐리 플래그. 가장 최근에 수행한 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시. 비부호형 연산에서 오버플로우를 검출할 때 사용.
• ZF : 영 플래그. 가장 최근 연산의 결과가 0인 것을 표시.
• SF : 사인 플래그. 가장 최근의 연산이 음수를 생성한 것을 표시.
• OF : 오버플로우 플래그. 가장 최근의 연산이 양수/음수의 2의 보수 오버플로우를 발생시킨 것을 표시.

t = a + b를 수행하기 위해 ADD를 썼다고 가정하자. 조건코드는 다음 수식에 따라 설정된다.

CF (unsigned) t < (unsigned) a //Unsigned overflow
ZF (t == 0) //Zero
SF (t < 0) //Negative
OF (a < 0 == b < 0) && (t < 0 != a < 0) //Signed overflow

• leaq는 주소계산에 사용되므로 조건 코드를 변경하지 않는다. 이 leaq를 제외한 나머지 모든인스트럭션들은 조건 코드 값을 변경한다.
  • 논리연산에서는 CF, OF가 0으로 세팅
  • 쉬프트연산에서는 CF가 쉬프트되어 없어지는 마지막 비트로 설정. OF는 0

인스트럭션에 의해 조건 코드 값이 변경될 뿐만 아니라 다른 레지스터들은 변경시키지 않으면서 조건 코드만 변경해주는 인스트럭션 클래스.

CMP, TEST는 목적지 오퍼랜드를 변경하지 않으면서 조건 코드를 설정하는 점만 제외하고 각각 SUB, AND 인스트럭션과 같은 방식으로 작동한다.

3.6.2 Accessing the Condition Codes(조건 코드 사용하기)

조건 코드를 직접 읽는 것 외 조건 코드를 이용하는 세가지 방법

1. 조건 코드의 조합에 따라 0 or 1을 한 개의 바이트에 기록
2. 조건에 따라 프로그램의 다른 부분으로 이동
3. 조건에 따라 데이터 전송

조건 코드의 조합에 따라 0 또는 1을 한개의 바이트에 기록하기

💡 SET 인스트럭션

접미어를 이용해 오퍼랜드의 크기를 나타내는 것이 아니라, 조건 코드의 어떤 조합을 사용할 것인지를 나타낸다.

setl : set less (not set long word)

setb : set below (not set byte)

SET은 단일 바이트 레지스터중 한 개, 또는 단일 바이트 메모리 주소를 사용한다. 이때 32비트나 64비트 결과를 만들려면 다른 상위 비트들을 0으로 만들어줘야 한다.

		//int comp(data_t a, data_t b)
		//a in %rdi, b in %rsi
1   comp:
2   cmpq %rsi, %rdi Compare a:b
3   setl %al Set low-order byte of %eax to 0 or 1
4   movzbl %al, %eax Clear rest of %eax (and rest of %rax)
5   ret

위 코드는 long 타입 변수 a와 b사이 a<b를 계산하는 인스트럭션이다.

• cmpq 인스트럭션의 비교 순서에 유의할 것. 인자가 %rsi, %rdi 순서로 나열되어 있으나, 비교는 실제로 a와 b 사이에 하게 된다.
• movzbl 인스트럭션은 %raz의 상위 4바이트 모두 지우는 것을 기억하자.

일부 기존의 기계어에는 ‘유사어’라는 동일한 기능을 하지만 다른 이름을 가진 인스트럭션이 존재한다.

setg (더 큰 경우에 1을 저장) == setnle(작거나 같지 않으면 1을 저장)

컴파일러와 역어셈블러는 어떤 이름을 쓸지 랜덤으로 정한다.

sete : 같으면 1로 설정

만일 a = b라면 t = 0일 것이고, 영 플래그는 동일함을 나타낸다.

setl : 값이 작으면 1로 설정

오버플로우가 발생하지 않을 경우 $t=a- _w^tb < 0$일 때 SF 비트가 1로 세팅되고, 반대의 경우 0으로 세팅되어 각각의 경우를 알 수 있다.

반면 오버플로우가 발생하면, $t=a- _w^tb \ge 0$일때 SF 비트가 1으로 세팅되고, $t=a- _w^tb < 0$일때 0으로 세팅되며, a=b일 때는 오버플로우가 발생하지 않는다.

그래서 0F가 1로 세팅되면 만일 SF가 0일 때 a<b 관계를 알 수 있다. 즉, 오버플로우와 부호비트의 XOR 값은 a<b의 관계여부를 테스트할 수 있는 방법이 된다. 다른 부호형 비교시험은 SF^0F와 ZF의 조합으로 만들 수 있다

3.6.3 Jump Instructions(JUMP 인스트럭션)

일반적인 실행의 경우 인스트럭션은 나열된 순서에 따라 순차적으로 실행된다. 반면 점프 인스트럭션은 프로그램이 완전히 새로운 위치로 실행하도록 한다. 일반적으로 점프의 목적지는 label로 표시한다.

	movq $0,%rax                Set %rax to 0
	jmp .L1                     Goto .L1
	movq (%rax),%rdx            Null pointer dereference (skipped)
.L1:
	popq %rdx                   Jump target

인스트럭션 jmp .L1은 프로그램이 movq를 건너뛰고 popq로 실행을 시작하게 된다. 목적 코드파일을 만들기 위해서 어셈블러는 모든 레이블이 붙은 인스트럭션의 일부분인 점프 목적지(목적지 인스트럭션의 주소)를 인코딩한다.

jmp : 무조건적인 점프. 점프 목적지가 인스트럭션의 일부로 인코딩되면 직접 점프, 점프 대상을 레지스터나 메모리 위치로부터 읽는 경우 간접 점프를 쓴다.

직접 점프는 .L1와 같이 점프 대상을 레이블로 프로그램 내에 작성하는 방식. 간접 점프는 ‘*’와 메모리 오퍼랜드 중 하나를 이용한 오퍼랜드 식별자를 합쳐서 작성한다.

다음 인스트럭션은 레지스터의 값을 정프 목적지로 사용한다.

jmp *%rax

다음 인스트럭션은 %rax에 저장된 값을 읽기 주소로 사용하여 메모리에서 점프 목적지를 읽어들인다.

jmp *(%rax)

표에 남은 다른 점프 인스트럭션은 조건부 점프에 해당함. 조건 코드의 조합에 의해 점프를 실행한다. 조건부 점프는 직접 점프만 가능하다.

3.6.4 Jump Instruction Encoding(점프 인스트럭션 인코딩)

점프를 인코딩하는 방법에는 여러가지가 있으나, 가장 일반적인 방법은 PC 상대적 방법일 것이다.

대상 인스트럭션과 점프 인스트럭션 바로 다음에 오는 인스트럭션 주소와의 차이를 인코딩 (오프셋은 1,2,4바이트)

또 다른 방법으로는 절대 주소를 제공하는 방법. 대상을 직접 명시하기 위해 4바이트를 사용한다.

	movq %rdi, %rax
	jmp .L2
.L3:
	sarq %rax
.L2:
	testq %rax, %rax
	jg .L3
	rep; ret

L2로의 jmp 인스트럭션은 더 높은 주소로 전진 이동하는 반면, L3로의 jg는 낮은 위치로 되돌아가는 점프를 실행한다. 어셈블러가 생성한 오브젝트 파일의 역어셈블 버젼은 다음과 같다.

0: 48 89 f8                         mov %rdi,%rax
3: eb 03                            jmp 8 <loop+0x8>
5: 48 d1 f8                         sar %rax
8: 48 85 c0                         test %rax,%rax
b: 7f f8                            jg 5 <loop+0x5>
d: f3 c3                            repz retq

L2로의 점프 명령은 0x8로 계산되었고, jg 명령에서는 0x5로 계산된 것을 나타낸다. 하지만 인스트럭션의 바이트 인코딩의 경우에는 첫 번째 점프 인스트럭션 목적지가 0x03으로 인코딩 된 것을 알 수 있고, 다음 주소인 0x05에 더하면 4번 줄의 인스트럭션 주소인 0x8을 얻을 수 있다.

마찬가지로 두 번째 점프 인스트럭션의 목적지는 0xf8 로 단일 바이트 2의 보수 표시로 인코딩 된다. 6번 줄 인스트럭션 주소인 0xd에 더하면 0x5가 됨을 알 수 있다.

PC 상대 주소 지정을 수행할 때 프로그램의 카운터 값은 점프 인스트럭션 자신의 주소가 아닌 점프 다음 지점의 인스트럭션 주소가 된다. PC 상대 방식으로 점프 목적지를 인코딩하면, 인스트럭션들이 간결하게 인코딩 될 수 있고, 목적 코드는 수정 없이 메모리 상의 다른 위치로 이동 될 수 있다.

3.6.5 Implementing Conditional Branches with Conditional Control(조건부 분기를 조건제어로 구현하기)

조건부 수식과 문장을 기계어 코드로 번역하는 가장 일반적인 방법은 조건부와 점프를 같이 쓰는 것이다.

long lt_cnt = 0;
long ge_cnt = 0;
long absdiff_se(long x, long y)
{
	long result;
	if (x < y) {
		lt_cnt++;
		result = y - x;
	}
	else {
		ge_cnt++;
		result = x - y;
	}
	return result;
}

long gotodiff_se(long x, long y)
{
		long result;
		if (x >= y)
				goto x_ge_y;
		lt_cnt++;
		result = y - x;
		return result;
		x_ge_y:
		ge_cnt++;
		result = x - y;
		return result;
}

				long absdiff_se(long x, long y)
				x in %rdi, y in %rsi
absdiff_se:
	cmpq %rsi, %rdi                      Compare x:y
	jge .L2                              If >= goto x_ge_y
	addq $1, lt_cnt(%rip)                lt_cnt++
	movq %rsi, %rax
	subq %rdi, %rax                      result=y-x
	ret                                  Return
.L2:                                   x_ge_y:
	addq $1, ge_cnt(%rip)                ge_cnt++
	movq %rdi, %rax
	subq %rsi, %rax                      result=x-y
	ret                                  Return

위 코드는 두 수의 차이를 절대값으로 계산하는 함수이다.

GCC는 3번째 코드와 같이 어셈블리 코드를 만들어 낸다. 이 머신코드를 C 코드로 다시 해석한 것을 두번째 C 코드로 나타낸다. 어셈블리의 jump에 해당하는 부분을 goto문을 통해 표현하였다.

goto코드에서 5번줄의 goto x_ge_y는 9번줄의 레이블로 점프를 발생시킨다.(x≥y일때 발생하므로) 계속하여 함수의 else 부분으로 표시된 계산을 완료하고 리턴한다. 만약 x<y일 경우 if의 단계를 실행하고 리턴한다.

C에서 if-else의 일반적인 형태는 다음과 같은 유형이다.

if (test-expr)
		then-statement
else
		else-statement

여기서 test-expr는 정수 수식으로 계산 결과가 0이거나, 0이 아닌 값을 갖는다. 두개의 분기문에서 단 한개만이 실행된다.

이러한 문장 형태에 대해 어셈블리는 C 문법을 사용해 제어흐름을 나타내며 다음과 같은 형식을 갖는다.

		t = test-expr;
		if (!t)
				goto false;
		then-statement
		goto done;
false:
		else-statement
done:

컴파일러는 else와 then에 대해 별도의 코드 블럭을 생성한다.

3.6.6 Implementing Conditional Branches with Conditional Moves(조건부 이동으로 조건부 분기 구현하기)

조건이 만족되면 프로그램의 한 가지 실행경로를 따르고, 아닌 경우에는 다른 경로를 따라가도록 하는 제어의 조건부 전환을 통해 이루어짐. 간단하고 일반적이나, 최신 프로세서에서는 비효율적일 수 있음.

또 다른 전략은 데이터의 조건부 전송을 이용하는 것.

조건부 동작의 산출물 모두를 게산하고 조건에 따라 하나만 선택.

제한적인 경우에 의미를 가지나, 최신 프로세서의 성능특성과 잘 일치하는 간단한 조건부 이동 인스트럭션으로 구현가능함.

long absdiff(long x, long y)
{
		long result;
		if (x < y)
				result = y - x;
		else
				result = x - y;
		return result;
}

long cmovdiff(long x, long y)
{
		long rval = y-x;
		long eval = x-y;
		long ntest = x >= y;
		/* Line below requires
		single instruction: */
		if (ntest) rval = eval;
		return rval;
}

long absdiff(long x, long y)
x in %rdi, y in %rsi
absdiff:
movq %rsi, %rax
subq %rdi, %rax                   rval = y-x
movq %rdi, %rdx
subq %rsi, %rdx                   eval = x-y
cmpq %rsi, %rdi                   Compare x:y
cmovge %rdx, %rax                 If >=, rval = eval
ret                               Return tval

위 코드는 조건부 이동을 사용해서 컴파일 되는 예제 코드이다.

x와 y의 차이의 절대 값을 계산하는 코드인데, 함수에 의해 리턴 되는 값만을 계산하는 특성이 있다.

어셈블리와 이를 모방한 C코드를 살펴보면, y-x와 x-y의 값을 모두 rval,eval에 각각 저장하는 것을 알 수 있다. 그 후, x와 y의 크기를 비교한 후, eval이나 rval을 상대값으로 복사한 후 함수를 마친다.

조건부 제어 이동 기반코드보다 조건부 데이터 이동 코드가 성능이 우수한 이유를 이해하기 위해서는 최신 프로세서들이 어떻게 동작하는지 이해할 필요가 있다.

프로세서는 각 인스트럭션을 일련의 단계로 처리하며, 이 단계들은 각각 요구된 동작의 작은 부분만을 실행하는 파이프라인을 통해 높은 성능을 얻는다.

이 방식은 이전 인스트럭션의 산술연산을 수행하는 동안 다른 인스트럭션을 인출하는 것 처럼 연속되는 인스트럭션의 단계를 중첩시키는 효과를 얻는다.

파이프라인에서는 실행할 인스트럭션을 미리 알고 실행순서를 결정할 필요가 있다.

프로세서가 조건부 점프(branch)를 만나면, 프로세서는 분기 조건에 대한 계산이 완료될 때까지는 어느쪽으로 분기될지 결정이 불가능하다.

이를 안정적으로 예측이 가능하다면 인스트럭션 파이프라인은 인스트럭션으로 가득 채워질 수 있다.

반면 예측이 실패하면, 해당 작업을 버리고 정확한 위치에 인스트럭션을 채우는 작업을 수행해야하므로, 프로그램의 성능에 상당한 감소를 야기할 수 있다.

반면 조건부 이동명령을 사용하면, 테스트데이터와 관계없이 짧은 클럭 사이클만을 요구하므로 파이프라인을 꽉 찬 상태로 유지하는 것을 쉽게 만들어준다.

위 도표는 조건부 이동 move 인스트럭션을 보여준다. 일반적으로 두개의 오퍼랜드를 갖는데, 소스 레지스터 또는 메모리 S와 목적지 레지스터 R.

소스값은 메모리나 소스 레지스터로부터 읽히나, 목적지에는 명시된 조건이 만족될 때에만 복사된다.

각 값은 16,32,64비트의 길이를 가진다.

무조건형 인스트럭션과는 달리, 어셈블러는 목적지 레지스터의 이름으로부터 조건부 이동 인스트럭션의 오퍼랜드 길이를 추측한다. 그러므로 모든 오퍼랜드 길이에 대해 동일한 인스트럭션으로 대응이 가능함.

v = test-expr ? then-expr : else-expr;

이 수식을 조건부 제어 전송을 이용해 컴파일하는 표준방식은 다음과 같다.

		if(!test-expr)
				goto false;
		v = then-expr;
		goto done;
false:
		v = else-expr;
done:

이 코드는 then-expr와 else-expr을 계산하는 두 개의 코드를 포함한다. 그리고 조건부와 무조건 부 점프의 조합을 사용해 오직 하나의 코드만이 계산되도록 한다.

조건부 이동에서는 다음과 같이 설명 가능할 것이다.

v = then-expr;
ve = else-expr;
t = test-expr;
if(!t) v = ve;

이 코드의 마지막 문장은 조건부 move로 구현된다. ve는 t가 만족 되지 않는 경우에만 v로 복사 된다.

모든 조건부 수식이 조건부 이동으로 컴파일 되는 것은 아니나, 중요한 점은 테스트 결과에 상관없이 then-expr과 else-expr 모두가 실행된다는 점이다. 만일 어느 한 곳에라도 에러가 발생한다면, 유효하지 않은 동작이 발생한다.

또한, 조건부 이동을 사용하는 것이 언제나 코드 효율성을 개선하는 것은 아니다. expr의 계산이 상당한 양의 계산을 요구하고, 조건에 만족 되지 못하게 되면 이러한 계산이 낭비된다. 컴파일러는 낭비되는 계산량과 예측 오류 사이의 손실을 잘 따져야 한다.

3.6.7 Loops(반복문)

Do while

do
		body-statement
		while (test-expr);

body-statement를 반복적으로 실행하고, test-expr를 계산해 결과가 0이 아니면 반복수행을 계속한다.

조건문과 goto문으로 바꾸면 다음과 같다.

loop:
		body-statement
		t = test-expr;
		if (t)
				goto loop;

매 실행마다 프로그램은 본체의 문장과 테스트 수식을 반복해서 계산한다.

어셈블리 코드를 역 엔지니어링하기 위해서는 프로그램 값을 위해 어떤 레지스터가 이용되었는지 결정해야 한다.

while

while (test-expr);
		body-statement

while문은 test-expr을 먼저 계산해서 body-statement를 실행하기 전에 종료될 수 있다는 점에서 do-while과 다르다. while을 기계어로 번역하는 방법에는 여러가지 방법이 있으며, 이 가운데 GCC에서는 두개의 방법이 이용된다.

	goto test;
loop:
	body-statement
test:
	t = test-expr;
	if (t)
		goto loop;

첫번째 방법은 루프의 맨 마지막에서 테스트로 무조건 점프를 수행하기 위한 테스트를 진행하는 방법이다.

일례로 factorial함수의 경우 0! = 1을 정확히 계산한다.

t = test-expr;
if (!t)
		goto done;
do
		body-statement
		while (test-expr);
done:

두번째 방법은 조건형-do이다. 코드를 초기 테스트가 실패하는 경우 루프를 건너뛰도록 조건부 분기를 이용해 do-while로 번역하는 방법이다. 이를 goto로 변환하면 다음과 같다.

t = test-expr;
if (!t)
		goto done;
loop:
		body-statement
		t = test-expr;
		if (t)
				goto loop;
done:

두 방법을 이용해 컴파일러는 테스트 조건이 항상 만족되는지 결정하는 타입의 초기 테스트를 최적화 할 수 있다.(??)

For 루프문

for 반복문의 일반적인 유형은 다음과 같다.

for (init-expr; test-expr; update-expr)
		body-statement

C언어 표준에는 for문이 다음과 같은 코드와 동일한 동작을 한다고 적혀있다.

init-expr;
while (test-expr) {
		body-statement
		update-expr;
}

for 루프에 대해 생성된 코드는 최적화 수준에 따라 while루프와 같은 방식으로 2개의 번역 전략중 하나를 따른다.

		init-expr;
		goto test;
loop:
		body-statement
		update-expr;
test:
		t = test-expr;
		if (t)
				goto loop;

중간으로 점프 전략은 goto 코드를 생성하는 반면,

		init-expr;
		t = test-expr;
		if (!t)
				goto done;
loop:
		body-statement
		update-expr;
		t = test-expr;
		if (t)
				goto loop;
done:

조건형 do는 다음의 코드를 생성한다.

3.6.8 Switch Statement

정수 인덱스 값에 따라 다중분기 기능을 제공하는 조건문이다. 테스트의 경우의 수가 많을 때 유용하다.

case레이블이 연속적인 범위에 분포하지 않고, 다중 레이블이 있는 case가 있으며, case가 다른 case 내부에 들어가 있는 경우를 확인할 수 있다.

원본 코드는 case값으로 100,102~104, 106을 가지나, 스위치문의 변수는 임의의 정수가 될 수 있다.

먼저 n에서 100을 빼 범위를 0~6 사이로 제한해, index라는 변수를 생성한다.

unsigned타입으로 대응시켜 분기 가능성을 단순화 시켰다. 이를 이용해 index값이 0~6의 범위를 벗어나는지 시험하기 위해 6보다 큰지 시험하는 방식으로 수행하였다. (0보다 작으면 오버플로우 발생)

switch문에서 핵심은 점프 테이블을 통해 코드의 위치로 접근하는 것.