제 10 장  코드 생성

제 10 장  코드 생성 이 장에서는 앞에서 생성한 중간 코드를 중앙처리장치에서 실행할 수 있는 기계어 인스트럭션으로 생성하는 방법을 살펴본다.

10.1 코드 생성의 개요 컴파일러 설계는 보통 전처리 부분과 후처리 부분으로 나눈다. 전처리 부분은 어휘 분석과 구문 분석 단계 컴퓨터와 독립적으로 구현할 수 있는 부분 후처리 부분은 코드 생성이나 코드 최적화 컴퓨터 구조에 매우 종속적으로 구현되는 부분

코드 생성의 위치 그림 10.1 코드 생성의 위치

순차 컴퓨터의 인스트럭션 수식 a = b + c - d는 아래 같이 순서에 따라 차례로 실행하는 기계어 인스트럭션으로 변환한다.                  lod  r1  b                  add  r1  c                  sub  r1  d                  sto  r1  a

병렬 컴퓨터의 인스트럭션 어떤 벡터 병렬 컴퓨터가 1000개씩의 벡터 데이터를 저장한 배열 A ,B ,D ,E 를 동시에 계산하는 벡터 더하기 연산을 A = B + D - E 처럼 수행하면 아래 같은 벡터 인스트럭션으로 변환한다. VADD B D        VSUB B E        VSTO B  A

10.2 기계어 인스트럭션으로 변환 이 절에서는 프로그램의 실행에 변화를 주는 점프 같은 인스트럭션은 뒤에서 다루고, 먼저 중간 코드를 기계어 인스트럭션으로 변환하는 과정을 살펴본다.

10.2.1 직접 주소 지정 인스트럭션 인스트럭션은 해당 피연산자의 주소를 직접 지정한다. 산술 수식 a = b + c 를 중간 코드로 번역하면 아래와 같다.               add   b  c  t1                   store  t1  a 이 중간 코드에 대응하는 기계어 프로그램은 아래와 같이 각 인스트럭션이 b, c, a 의 해당 데이터 주소와 레지스터 번호를 직접 나타낸다.                  lod  r1  b                  add  r1  c                  sto  r1  t1                  lod  r1  t1                  sto  r1  a

 그림 10.2 C = B + A 에 대한 기계어 인스트럭션의 실행과정

그림 10.3 중간 코드 mov의 기계어 인스트럭션 구현

10.2.2 상대 주소 지정 인스트럭션 취급할 데이터 주소를 상대적으로 나타내는 인스트럭션이다. 이 때 주소를 상대적으로 나타내는 방법은 아래와 같다. 인덱스에 의한 주소 지정 간접 주소 지정 시작 레지스터에 의한 주소 지정

10.2.2.1 인덱스에 의한 주소 지정 피연산자 주소를 목적 기계의 인덱스 레지스터와 인덱스 레지스터에 저장된 값으로 계산한다. 예를 들어 아래 인스트럭션을 살펴보자.           lod    r2   8(r1) 그림 10.4 인덱스에 의한 주소 지정

10.2.2.2 간접 주소 지정 인스트럭션에서 계산하여 지정한 주소의 값을 최종 피연산자 주소로 한다. 예를 들어 아래 인스트럭션을 살펴보자.           lod   r2    *8(r1)  그림 10.5 간접 주소 지정

10.2.2.3 시작 레지스터에 의한 주소 지정 목적 기계의 시작 레지스터와 시작 주소의 값으로 계산한 변위가 주소이며 그 주소의 내용이 피연산자이다. 그림 10.6 시작 주소와 변위에 의한 피연산자 주소 계산

실습 10.1 어느 프로그래밍 언어의 조건 문장인 if (a > b) a = b + c 를 중간 코드로 번역하면 아래와 같다. 이 중간 코드를 기계어 인스트럭션으로 번역해 보자. comp a  b gt L1   /*  이 코드는 의미 분석의 실습에 있음  */       goto L2 L1:  add  b  c  a       goto L3 L2:  .... L3:  ....

10.3 점프 주소 지정 중간 코드에서 기계어 인스트럭션을 생성하면서 코드 생성기는 프로그램 카운터를 관리한다. 아래 중간 코드 아직 목적지 주소를 알 수 없기 때문에 레이블 L1로 가는 점프 인스트럭션을 완전하게 생성할 수 없다.              중간 코드                 주소          인스트럭션           add  a  b   t1              1000           lod   r1, a                                       1004           add   r1, b                                        1008           sto  r1, t1           goto  L1                    1012           cmp  0,0,0                                        1016           jmp   ?             ....    L1:  add  c   d  t2              1128           lod   r1, a

10.3.1 단일 단계 그림 10.7 단일 단계에 의한 점프할 주소 계산과 점프 인스트럭션 생성

그림 10.7의 중간코드 goto L1에서 레이블 L1을 아직 알 수 없기 때문에 jmp의 위치인 1016 번지가 준비 테이블에 들어간다. 그러면 (b)와 같은 인스트럭션을 생성한다.

10.3.2 다단계 그림 10.8 다단계 방법을 사용하는 점프 인스트럭션 생성

실습 10.2 아래는 고급 언어의 while 문 중간 코드이다. while (k <= x) {                  x = x + 2;                  k= i * 3;                }      L1: comp  k  x ,  le, L2         goto  L3      L2: add  x  2  x          mul  k  3 k          goto L1                 L3:

(1) 각 인스트럭션이 4바이트를 차지한다고 가정하고 단일 단계 방법으로 중간 코드를 기계어 인스트럭션으로 변환하시오 (1) 각 인스트럭션이 4바이트를 차지한다고 가정하고 단일 단계 방법으로 중간 코드를 기계어 인스트럭션으로 변환하시오. 이 때 준비 테이블과 레이블 테이블의 내용을 보이시오. (2) 다단계 방법으로 기계어 인스트럭션으로 번역하시오.

실습 10.3 아래 고급 언어 문장의 중간 코드를 생성하고 기계어 인스트럭션으로 번역하시오.         if (k <= x)              if (k == 10)                {                 x = x + 2;                 k= i * 3;                }                else k= i / 2;

실습 10.4 아래 고급 언어 문장의 중간 코드를 생성하고 기계어 인스트럭션으로 번역하시오.         for (k = a; k <= b + c; k++)                     b = b / 2;

10.4 레지스터 할당 레지스터 할당이란 코드 생성 과정에서 프로그램의 변수나 수행하고자 하는 일을 할당하는 과정이다. 아래와 같은 프로그램의 일부를 레지스터 한 개를 사용할 때와 두 개를 사용할 때의 전체 인스트럭션의 길이를 비교하여 보자. 여기에서 레지스터 수와 할당 기법에 따라 인스트럭션의 수에 많은 영향을 준다는 것을 알 수 있다.          A = B * ( C + D )          B = A - ( C + D )

레지스터를 한 개 사용한 경우의 인스트럭션 lod r1, C add r1, D sto r1, t1 lod r1, B            mul  r1, t1            sto  r1, A            lod  r1, C            sto  r1, t2            lod  r1, A            sub  r1, t2            sto  r1, B

레지스터를 두 개 사용한 경우의 인스트럭션 lod r1, C add r1, D lod r2, B mul r2, r1            sto  r2, A            sub  r2, r1            sto  r2, B

레지스터를 한 개 사용하는 경우는 열두 개의 인스트럭션이 생성되고 피연산자를 사용하기 위해 메모리를 열두 번 참조한다. 그러나 레지스터를 두개 사용하면 인스트럭션은 일곱 개이지만 메모리는 다섯 번만 참조한다. 위에서는 (C + D)가 공통 부분수식이므로 두 번째 문장의 (C + D)를 계산하는 인스트럭션을 또 생성하고 반복 실행하는 것은 수행 시간 낭비이다.

제 10 장 끝