컴파일러 설계-코드 생성

코드 생성은 컴파일의 마지막 단계로 간주 할 수 있습니다. 포스트 코드 생성을 통해 최적화 프로세스를 코드에 적용 할 수 있지만 이는 코드 생성 단계 자체의 일부로 볼 수 있습니다. 컴파일러에서 생성 된 코드는 어셈블리 언어와 같은 일부 하위 수준 프로그래밍 언어의 개체 코드입니다. 상위 수준 언어로 작성된 소스 코드가 하위 수준 언어로 변환되어 하위 수준의 개체 코드가 생성되는 것을 확인했습니다.이 코드는 다음과 같은 최소 속성을 가져야합니다.

소스 코드의 정확한 의미를 전달해야합니다.
CPU 사용 및 메모리 관리 측면에서 효율적이어야합니다.

이제 중간 코드가 대상 개체 코드 (이 경우 어셈블리 코드)로 어떻게 변환되는지 살펴 보겠습니다.

방향성 비순환 그래프

DAG (Directed Acyclic Graph)는 기본 블록의 구조를 묘사하고 기본 블록 사이에 흐르는 값의 흐름을 확인하는 데 도움이되며 최적화도 제공하는 도구입니다. DAG는 기본 블록에 대한 쉬운 변환을 제공합니다. DAG는 여기에서 이해할 수 있습니다.

리프 노드는 식별자, 이름 또는 상수를 나타냅니다.
내부 노드는 연산자를 나타냅니다.
내부 노드는 또한 표현식의 결과 또는 값이 저장되거나 할당되는 식별자 / 이름을 나타냅니다.

Example:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t ₀ = a + b]	[t ₁ = t ₀ + c]	[d = t ₀ + t ₁ ]

구멍 최적화

이 최적화 기술은 소스 코드에서 로컬로 작동하여 최적화 된 코드로 변환합니다. 로컬이란 코드 블록의 작은 부분을 의미합니다. 이러한 방법은 중간 코드와 대상 코드에 적용 할 수 있습니다. 여러 명령문이 분석되고 다음과 같은 가능한 최적화가 있는지 확인합니다.

중복 명령 제거

소스 코드 수준에서 사용자는 다음을 수행 할 수 있습니다.

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

컴파일 수준에서 컴파일러는 본질적으로 중복 된 명령어를 검색합니다. 명령어의 여러로드 및 저장은 일부가 제거 되더라도 동일한 의미를 가질 수 있습니다. 예를 들면 :

MOV x, R0
MOV R0, R1

첫 번째 명령어를 삭제하고 문장을 다음과 같이 다시 작성할 수 있습니다.

MOV x, R1

연결할 수없는 코드

연결할 수없는 코드는 프로그래밍 구조로 인해 액세스 할 수없는 프로그램 코드의 일부입니다. 프로그래머는 도달 할 수없는 코드를 실수로 작성했을 수 있습니다.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

이 코드 세그먼트에서 printf 프로그램 컨트롤이 실행되기 전에 다시 반환되므로 문이 실행되지 않습니다. printf 제거 할 수 있습니다.

제어 최적화의 흐름

프로그램 컨트롤이 중요한 작업을 수행하지 않고 앞뒤로 점프하는 코드의 경우가 있습니다. 이러한 점프는 제거 할 수 있습니다. 다음 코드 덩어리를 고려하십시오.

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

이 코드에서 L1 레이블은 컨트롤을 L2로 전달할 때 제거 할 수 있습니다. 따라서 L1으로 점프 한 다음 L2로 점프하는 대신 아래에 표시된 것처럼 컨트롤이 L2에 직접 도달 할 수 있습니다.

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

대수 표현 단순화

대수적 표현을 간단하게 만들 수있는 경우가 있습니다. 예를 들어, 표현식a = a + 0 대체 가능 a 그 자체와 표현 a = a + 1은 단순히 INC a로 대체 될 수 있습니다.

강도 감소

더 많은 시간과 공간을 소비하는 작업이 있습니다. 그들의 '강도'는 시간과 공간을 덜 소비하지만 동일한 결과를 생성하는 다른 작업으로 대체하여 줄일 수 있습니다.

예를 들면 x * 2 대체 가능 x << 1, 하나의 왼쪽 교대 만 포함됩니다. a * a와 a ² 의 출력 은 동일하지만 a ² 를 구현하는 것이 훨씬 더 효율적입니다.

기계 지침에 액세스

대상 컴퓨터는 특정 작업을 훨씬 효율적으로 수행 할 수있는 더 정교한 명령을 배포 할 수 있습니다. 대상 코드가 이러한 명령을 직접 수용 할 수 있다면 코드의 품질이 향상 될뿐만 아니라보다 효율적인 결과를 얻을 수 있습니다.

코드 생성기

코드 생성기는 대상 머신의 런타임 환경과 해당 명령어 세트를 이해하고 있어야합니다. 코드 생성기는 코드를 생성하기 위해 다음 사항을 고려해야합니다.

Target language: 코드 생성기는 코드를 변환 할 대상 언어의 특성을 알고 있어야합니다. 이 언어는 컴파일러가보다 편리한 방법으로 코드를 생성하는 데 도움이되는 일부 기계 별 명령어를 용이하게 할 수 있습니다. 대상 머신은 CISC 또는 RISC 프로세서 아키텍처를 가질 수 있습니다.
IR Type: 중급 표현에는 다양한 형태가 있습니다. AST (Abstract Syntax Tree) 구조, Reverse Polish Notation 또는 3- 주소 코드 일 수 있습니다.
Selection of instruction: 코드 생성기는 Intermediate Representation을 입력으로 받아 대상 머신의 명령어 세트로 변환 (매핑)합니다. 하나의 표현에는 여러 가지 방법 (명령)이있을 수 있으므로 적절한 명령을 현명하게 선택하는 것은 코드 생성기의 책임이됩니다.
Register allocation: 프로그램에는 실행 중에 유지해야 할 여러 값이 있습니다. 대상 머신의 아키텍처는 모든 값이 CPU 메모리 또는 레지스터에 유지되는 것을 허용하지 않을 수 있습니다. 코드 생성기는 레지스터에 유지할 값을 결정합니다. 또한 이러한 값을 유지하는 데 사용할 레지스터를 결정합니다.
Ordering of instructions: 마지막으로 코드 생성기는 명령이 실행될 순서를 결정합니다. 명령을 실행하기위한 일정을 만듭니다.

설명자

코드 생성기는 코드를 생성하는 동안 레지스터 (가용성을 위해)와 주소 (값 위치)를 모두 추적해야합니다. 둘 다에 대해 다음 두 설명이 사용됩니다.

Register descriptor: 레지스터 설명자는 레지스터의 가용성에 대해 코드 생성기에 알리는 데 사용됩니다. 레지스터 설명자는 각 레지스터에 저장된 값을 추적합니다. 코드 생성 중에 새 레지스터가 필요할 때마다 레지스터 가용성을 위해이 설명자를 참조합니다.
Address descriptor: 프로그램에서 사용되는 이름 (식별자)의 값은 실행 중에 다른 위치에 저장 될 수 있습니다. 주소 설명자는 식별자 값이 저장되는 메모리 위치를 추적하는 데 사용됩니다. 이러한 위치에는 CPU 레지스터, 힙, 스택, 메모리 또는 언급 된 위치의 조합이 포함될 수 있습니다.

코드 생성기는 두 설명자를 실시간으로 업데이트합니다. load 문, LD R1, x, 코드 생성기의 경우 :

값이 x 인 레지스터 설명자 R1을 업데이트하고
주소 설명자 (x)를 업데이트하여 x의 한 인스턴스가 R1에 있음을 표시합니다.

코드 생성

기본 블록은 일련의 3 개 주소 명령으로 구성됩니다. 코드 생성기는 이러한 명령 시퀀스를 입력으로 사용합니다.

Note: 이름의 값이 여러 위치 (레지스터, 캐시 또는 메모리)에서 발견되면 레지스터의 값이 캐시 및 메인 메모리보다 우선합니다. 마찬가지로 캐시의 값이 주 메모리보다 선호됩니다. 메인 메모리는 거의 선호하지 않습니다.

getReg: 코드 생성기는 getReg 함수를 사용하여 사용 가능한 레지스터의 상태와 이름 값의 위치를 결정합니다. getReg 는 다음과 같이 작동합니다.

변수 Y가 이미 레지스터 R에 있으면 해당 레지스터를 사용합니다.
그렇지 않으면 레지스터 R을 사용할 수 있으면 해당 레지스터를 사용합니다.
그렇지 않으면 위의 두 옵션을 모두 사용할 수없는 경우 최소한의로드 및 저장 명령이 필요한 레지스터를 선택합니다.

명령어 x = y OP z의 경우 코드 생성기는 다음 작업을 수행 할 수 있습니다. L이 y OP z의 출력이 저장 될 위치 (가급적 레지스터)라고 가정 해 보겠습니다.

getReg 함수를 호출하여 L의 위치를 결정합니다.
현재 위치 (레지스터 또는 메모리) 확인 y 주소 설명자에게 문의하여 y. 만약y 현재 등록되지 않음 L, 다음 명령을 생성하여 값을 복사하십시오. y ...에 L:

MOV y ', L

어디 y’ 복사 된 값을 나타냅니다. y.
현재 위치 결정 z 2 단계에서 사용한 것과 동일한 방법을 사용하여 y 다음 명령을 생성하십시오.

OP z ', L

어디 z’ 복사 된 값을 나타냅니다. z.
이제 L은 y OP z의 값을 포함합니다. x. 따라서 L이 레지스터 인 경우 설명자를 업데이트하여 값이 포함되어 있음을 나타내십시오.x. 설명자 업데이트x 위치에 저장되었음을 나타 내기 위해 L.
y와 z가 더 이상 사용되지 않으면 시스템에 다시 제공 할 수 있습니다.

루프 및 조건문과 같은 다른 코드 구조는 일반적인 어셈블리 방식으로 어셈블리 언어로 변환됩니다.