CSAPP 3.6.5 - 3.7

CSAPP

3.6.5 조건부 분기를 조건 제어로 구현하기

• C에서 조건부 수식과 문장을 기계어 코드로 번역하는 가장 일반적인 방법은 조건부 및 무조건 점프를 함께 사용하는 것이다.(일부 조건문은 제어의 이동보다 데이터 이동으로 구현 할 수 있다.)
• GOTO문을 사용하는 것은 코드를 해독하고 디버깅하기 어렵게 할 수 있기 때문에 일반적으로 나쁜 프로그래밍 스타일이다.

3.6.6 조건부 이동으로 조건부 분기 구현하기

• 조건부 동작을 구현하는 전형적인 방법은 조건이 만족되면 프로그램의 한 가지 실행경로를 따르고, 아닌 경우에는 다른 경로를 따라가도록 하는 제어의 조건부 전환을 통해 이루어진다. 이 방법은 간단하고 일반적이지만 최신 프로세서들에서는 매우 비효율적일 수 있다.
• 또 다른 전략은 데이터 조건부 전송을 이용하는 것이다. 조건부 동작의 산출물 모두를 계산하고 조건에 따라 하나만 선택하는 방식이다. 제한적인 경우에만 의미를 갖고 move인스트럭션으로 구현된다.
• 조건부 제어 이동기반 코드보다 조건부 데이터 이동 코드가 성능이 우수하다. 프로세서들은 각 인스트럭션을 일련의 단계로 처리하며, 이 단계들은 각각 요구된 동작의 작은 부분만을 실행하는 파이프 라인을 통해 높은 성능을 얻는다. 이 방법은 이전 인스트럭션의 산술 연산을 수행하는 동안에 다른 인스트럭션을 인출하는 것처럼 연속되는 인스트럭션들의 단계를 중첩시켜 고성능을 얻는다. 이를 위해서는 파이프라인을 실행할 인스트럭션들로 미리 채우기 위한 실행할 인스트럭션들의 순서를 훨씬 일찍 결정할 수 있어야한다. 프로세서가 조건부 점프를 만나게 되면 프로세서는 분기 조건에 대한 계산이 완료될 때 까지는어느쪽으로 분기할지 결정할 수 없다.
• 프로세서는 각 점프 인스트럭션이 실행될지 추측하기 위한 복잡한 분기 예측 회로를 채택하고 있다. 점프 하나를 잘못 예측하면, 미래의 인스트럭션을 위해 이미 실행한 작업 결과들을 상당 부분 버려야 하고, 정확한 위치에서 다시 인스트럭션들을 파이프라인에 채우는 작업을 수행해야 한다. 이러한 예측 오류는 약 15~30 클럭 사이클의 손실을 발생시켜 프로그램 성능에 상당한 감소를 야기한다.
• 분기 예측 오류 손실이 함수의 성능을 결정한다.
• x86-64 코드에서 쉽게 예측할 수 있는 경우 함수당 약 8클럭, 분기 패턴이 랜덤인 경우 17.50 클럭 사이클을 소모한다 분기 예측 오류 손실은 약 19클럭 사이클 정도이다.
• 이것은 함수의 실행시간이 분기 예측에 따라 8에서 27 사이클의 범위를 갖는다는것을 의미한다. 반면 조건부 이동 명령을 사용해 컴파일한 코드는 테스트 하는 데이터와 상관없이 약 8클럭 사이클을 필요로 한다. 이것은 프로세서가 파이프라인을 꽉 찬 상태로 유지하는 것을 더욱 쉽게 해준다.
• 조건부 이동 인스트럭션. 두개의 오퍼랜드를 갖는다 : 소스 레지스터 또는 메모리 위치, 목적지 레지스터
• set과 점프 인스트럭션처럼 이 인스트럭션들의 결과는 조건코드값에 따라 달라진다. 소스값은 메모리나 소스 레지스터로 부터 읽히지만, 목적지에는 명시된 조건이 만족될때만 복사된다.
• 소스와 목적지 값은 16,32 또는 64 비트 길이를 가진다. 단일 바이트 조건부 이동은 지원되지 않는다. 오퍼랜드의 길이가 명시적으로 인스트럭션의 이름에 인코딩되는 무조건형 인스트럭션들과는 달리, 어셈블러는 목적지 레지스터의 이름으로 부터 조건부 이동 인스트럭션의 오퍼랜드의 길이를 추정한다. 그래서 동일한 인스트럭션 이름이 모든 오퍼랜드 길이에 대해 사용 될 수있다.
• 조건부 점프와는 달리, 프로세서는 테스트 결과를 예측하지 않고서도 조건부 이동 인스트럭션을 실행할 수 있다. 프로세서는 간단히 소스값을 읽고(대개 메모리로부터) 조건 코드를 검사하고, 목적지 레지스터를 갱신하거나 그대로 유지한다.
• 조건부 이동move 에서는 계산 결과에 따라 선택되는 최정 값에 의해 모두 계산된다.
• 조건부 이동을 사용한다고 해서 언제나 코드 효율성을 개선할 수 있는 것은 아니다.
• 계산이 상당한 양의 계산을 요하는 경우 해당 조건이 만족되지 못한다면 이 노력은 낭비가 되고 만다. 컴파일러는 낭비되는 계산량과 분기 예측 오류에 의한 잠재적 성능 손실 사이의 상대적 성능을 고려해야한다. GCC 컴파일러는 add같은 간단한 경우만 move를 사용한다.
• 조건부 동작을 구현하기 위해서 조건부 제어의 전환외에 추가적으로 조건부 데이터 이동을 사용할 수 있다는 것을 알 수 있었다. 매우 제한적인 경우에만 사용 가능 하지만 이들은 상당히 보편적이고, 최신 프로세서들의 연산들과도 보다 더 잘 동작한다.

3.6.7 반복문

• 기계어에는 반복문 인스트럭션이 없다 조건 부 테스트와 점프를 사용해 효과를 구현한다.
  • do while
  • while
  • for문

3.6.8 Switch문

• switch 문은 정수 인덱스 값에 따라 다중 분기 기능을 제공한다. 이것은 테스트 해야하는 경우의 수가 많은 경우 특히 유용하다.
• 점프 테이블이라는 자료구조를 사용해서 효율적으로 구현한다.
  • 점프테이블은 그 원소 i가 switch문의 인덱스가 i일 때 프로그램이 실행해야 하는 동작을 구현하는 코드 블록의 주소가 되는 배열을 말한다.
  • 이 코드는 점프 인스트럭션의 목적지를 찾아내기 위해 switch문의 인덱스를 사용하여 점프테이블을 배열처럼 참조한다.
  • 점프테이블을 사용하면 다 단계의 if-else 구문을 사용하는 것 보다 switch를 실행하는데 걸리는 시간이 case수에 관계 없는 점이 장점이다.

3.7 프로시저

• 프로시저 호출은 소프트웨어에서의 주요 추상화, 지정 된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공한다.
• 잘 설계 된 소프트웨어는 무슨 값이 계산되고, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는지에 대한 명쾌하고 간결한 인터페이스 정의를 제공하는 한편, 일부 동작의 구체적인 구현은 감춰주는 방식으로 프로시저를 추상화 매커니즘으로 이용한다. 프로시저는 서로 다른 프로그래밍 언어에서 여러가지 다른 모습-함수, 메소드, 서브루틴, 핸들러- 등으로 사용된다. 그러나 이 모두는 일반적은 특징들을 공유한다.
• 프로시저에 대한 기계어 수준 지원을 제공할 때 처리되어야 하는 여러 많은 특성
  • 제어권 전달 : 프로그램 카운터는 진입할 때 Q에 대한 코드의 시작주소로 설정되고 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정 되어야 한다.
  • 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하며 Q는 다시 P로 하나의 값을 리턴할 수 있어야한다.
  • 메모리 할당과 반납 : Q는 시작할 때 지역변수들을 위한 공간을 할당할 수도 있고, 리턴할 때 이 저장소를 반납할 수도 있다.

3.7.1 런타임 스택

• 대부분 언어에서 프로시저 호출 동작 방식의 주요 특징은 스택 자료 구조가 제공하는 후입선출 메모리 관리 방식을 활용할 수 있다는 점이다. 프로그램은 스택을 사용해서 프로시저들이 요구하는 저장장소를 관리할 수 있으며, 여기서 스택과 프로그램 레지스터들은 제어와 데이터를 전송하기 위해, 메모리를 할당하기 위해 필요한 정보를 저장한다.
• x86-64 프로시저가 레지스터들에 저장할 수 있는 개수 이상의 저장공간을 필요로 할때 공간을 스택에 할당한다. 이 영역은 프로시저의 스택프레임 이라고 부른다.
  • 현재 실행중인 프로시저에 대한 프레임은 항상 스택의 맨 위에 위치한다.
• 프로시저P가 프로시저Q를 호출할 때 리턴주소 return address를 스택에 푸시해서 Q가 리턴할 때 P에서 프로그램이 실행을 재시작 해야하는 위치를 가리킨다. 리턴 주소가 P에 관계된 상태를 저장하기 때문에 리턴 주소는 P에 스택 프레임에 속하는 것으로 간주한다. Q에 대한 코드는 현재 스택 경계를 확장해서 자신의 스택프레임을 위한 공간을 할당한다. 이 공간 내에서 레지스터 값들을 저장하고, 지역변수들을 위한 공간을 할당하며, 자신이 호출하는 프로시저들을 위한 인자들을 설정할 수 있다. 대부분의 프로시저의 스택프레임들은 프로시저가 시작될 때 할당되는 고정 크기를 갖는다 그러나 일부 프로시저는 가변 크기 프레임을 필요로 한다.
• 시간과 공간 효율성을 위해 x86-64 프로시저는 요청받은 스택프레임의 부분만을 할당한다. 사실 많은 함수들은 심지어 스택 프레임을 요청하지도 않는다. 이런 경우는 모든 지역변수들을 레지스터에 보관할 수 있고, 이 함수가 다른 함수 하나를 하나도 호출하지 않을 때 발생한다.

3.7.2 제어의 이동

• 제어를 함수 P에서 함수 Q로 전달하는 것은 단순히 프로그램 카운터 PC를 Q를 위한 코드의 시작주소로 설정하는 것과 관련된다.
• x86-64에서 call인스트럭션 Q로 프로시저 Q를 호출해서 기록한다. call인스트럭션은 호출된 프로시저가 시작하는 인스트럭션 주소를 목적지로 갖는다. 점프와 유사하게 명령은 직접 혹은 간접 형태를 갖는다 어셈블리 코드에서의 직접 호출의 목적지는 레이블로 주어지는 반면, 간접호출의 목적지는 ‘*’ 와 그 뒤에 따라오는 식별자에 의해 주어진다.
  • 프로그램 카운터 %rip
• 리턴 주소를 스택에 푸시하는 방법을 사용해서 함수가 나중에 프로그램의 적절한 위치로 리턴 가능하게 된다는 것을 알 수 있다.

3.7.3 데이터 전송

• 프로시저로 부터의 데이터 전달은 레지스터를 통해 일어난다.
• x86-64에서는 최대 여섯개의 정수형(정수와 포인터) 인자가 레지스터로 전달될 수 있다. 이 레지스터들은 전달되는 데이터 형의 길이에 따라 레지스터 이름을 이용해서 정해진 순서로 이용된다.
• 인자들은 인자 리스트에서 각자의 순서에 따라 이들 레지스터에 할당된다.
• 함수가 여섯개 이상의 정수형 인자를 가질 때, 다른 인자들은 스택으로 전달된다.
• 매개변수들은 스택으로 전달할 때, 모든 데이터 길이는 8의 배수로 반올림 된다.
• 인자들이 배치되면, 프로그램은 프로시저로 제어를 전달하기 위해 call인스트럭션을 실행할 수 있다. 프로시저는 레지스터와 스택을 통해 자신의 인자들에 접근할 수 있다. 프로시저가 6개가 넘는 인자를 호출하려면 자신의 스택프레임에 argument build area 라고 이름 붙인 영역으로 이들을 위한 공간을 할당할 수 있다.

3.7.4 스택에서의 지역 저장 공간

• 지역데이터가 메모리에 저장 되어야 하는 경우
  • 지역데이터 모두를 저장하기에는 레지스터수가 부족하다.
  • 지역 변수에 연산자 ‘&’가 사용되었으며, 이 변수의 주소를 생성할 수 있어야 한다.
  • 일부 지역 변수들이 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근 되어야 하는 경우

3.7.5 레지스터를 이용하는 지역저장소

• 프로그램 레지스터들은 모든 프로시저들이 공유하는 단일 자원의 역할을 한다.
• 레지스터 %rbx, %rbp, %r12-%r15는 피호출자 - 저장 레지스터로 구분한다.
• 프로시저P가 프로시저 Q를 호출할 때, Q는 Q가 P로 리턴될 때 Q가 호출되었을 때의 값들과 동일하도록 보장할 수 있게 이 레지스터들의 값을 보존해야한다. 프로시저 Q는 이 값을 전혀 변경하지 않거나 원래의 값을 스택에 푸시해두고 이 값을 변경하며, 리턴하기 전에 스택에서 이전 값을 POP 해오는 방식으로 레지스터를 보존한다.
• 안전하게 값을 저장할 수 있으며 이 값이 위험 없이 레지스터에서 사용할 수 있다. 스택포인터 %rsp 를 제외한 다른 모든 레지스터들은 호출자 저장 레지스터로 구분된다. 이것은 이들이 함수에 의해 변경될 수 있다는 것을 의미한다.

3.7.6 재귀 프로시저

• 함수를 재귀적으로 호출 하는것도 다른 함수의 호출과 마찬가지로 진행된다.
• 스택 기법을 사용해서 함수의 각 호출시 상태정보(리턴 위치의 저장된 값, 피호출자-저장 레지스터를 위한 자신만의 저장공간을 제공한다.) 필요한 경우 지역변수를 위한 저장 공간도 제공할 수 있다.