Target code generation - (2)

 Code Generation 

 

연산 레지스터가 여러 개인 경우:

● 구문 트리를 만들 때 각 노드의 부분 트리를 계산하는 데 필요한 레지스터의 수 를 먼저 계산한 다음 표시.

      레지스터의 수를 label로 가진 구문 트리에서 목적 코드를 생성해낸다.

● 이 방법을 통해 STORE연산이 필요하지 않기 위한 레지스터의 수를 구할 수 있다.

● 레지스터의 수를 때때로 A. Ershov 수(Ershov number)라 부른다.

 

식 E를 계산하는 데 필요한 레지스터의 수를 CR(E)로 표시하면 [알고리즘]에 의해 구문 트리로부터

CE(E) 값을 구할 수 있다.

 

Label을 붙이는 순서는 터미널 노드에서 루트 노드로 진행하며, 필요한 레지스터의 수가 큰 쪽의 부분 트리부터

목적 코드로 변환해가면 된다.

 

[알고리즘] 레지스터 수(CR) 계산

● [입력] 구문 트리

● [출력] label을 가진 구문 트리

● [방법]

 

Example

산술식 A * (B + C) - D / E * (F + G)에 대해 레지스터 수를 label로 가진 구문 트리를 만들어보 자.

 

 

Example

다음 구문 트리에 대해 레지스터 수를 label로 가진 구문 트리를 만들어보자.

 

 

레지스터 수에 대한 label을 가진 구문 트리로부터 목적 코드를 생성하는 방법

[알고리즘] 여러 개의 연산 레지스터에 대한 label을 가진 구문 트리로부터 목적코드생성

● [입력] 여러 개의 연산 레지스터에 대한 label을 가진 구문 트리

● [출력] 목적 코드

● [방법]

주의할 점

- 자식의 label이 같지 않을 경우 : 두 자식의 base 를 동일하게 적용한다.

- 자식의 label이 같을 경우 : 오른쪽 트리를 base + 1, 왼쪽 트리를 base 으로 적용한다.

 

 

Example 다음 구문 트리에 [알고리즘 12-3]을 적용하여 목적 코드를 생성해보자. 

 

라벨 수가 3이므로 k = 3 으로 시작하는 것을 알 수 있다.

초기 base b 값은 1으로 시작한다. => b = 1, k = 3

 

1. 왼쪽 라벨값(3)이 오른쪽 라벨값(2) 보다 크므로 왼쪽 트리로 순회한다.

     b = 1(왼쪽 트리로 이동할 때 base 고정), k = 3(왼쪽 라벨 값) 

 

2. 왼쪽 라벨값(2)과 오른쪽 라벨값(2)이 동일하므로 오른쪽 트리로 순회한다.

     b = 2(오른쪽 트리로 이동할 때 base + 1), k = 2(오른쪽 라벨 값)

 

3. 왼쪽 라벨 값(1)과 오른쪽 라벨 값(1)이 동일하므로 오른쪽 트리로 순회한다.

     b = 3(오른쪽 트리로 이동할 때 base + 1), k = 1(오른쪽 라벨 값)

 

4. 알고리즘에 의하여 다음과 같이 명령어를 작성할 수 있다.

     LOAD R3, D     : 이때 base 값이 3이므로 R3에 D를 적재한다.

     LOAD R2, C     : 왼쪽 트리로 이동했으므로 base 값이 2이므로 R2에 C를 적재한다.

     SUBT R2, R3   : R2 - R3(C - D) 값을 R3 으로 설정한다.

 

5. 2번째 단계에서 오른쪽 트리를 전부 순회하였으므로 왼쪽 트리를 순회하도록 한다.

    이때 b = 1(부모 트리의 base가 1이므로 그대로), k = 2 이다.

 

6. 오른쪽 트리로 이동하면 b = 2, k = 1 이 되고 알고리즘에 의해 명령어를 작성할 수 있다.

    LOAD R2, B : 

    LOAD R1, A

    ADD R1, R2

 

7. 1번째 단계에서의 operation 에 대한 명령어를 작성한다.

    DIV R2, R3   : R3 에 (A + B) / (C - D) 에 대한 결과가 저장

 

8. 이제 초기 트리에서 오른쪽 트리로 이동하게 되므로 b = 1(자식 라벨이 동일했으므로), k = 2 가 된다.

     이동하고 알고리즘에 의해 명령어를 작성할 수 있다.

     LOAD R2, F

     LOAD R1, E

     MULT R1, R2

9. 마지막으로 트리 전체에 대한 operation 을 적용하면 끝이다.

    SUBT R2, R3

 

10. 모든 instruction 을 작성하면 다음과 같다.

     LOAD R3, D  

     LOAD R2, C     

     SUBT R2, R3  

     LOAD R2, B

     LOAD R1, A

     ADD R1, R2

     DIV R2, R3   

     LOAD R2, F

     LOAD R1, E

     MULT R1, R2

     SUBT R2, R3

총 11개의 instruction 이 만들어진다.

 

 

이와 같이 라벨을 가진 구문 트리에서 가장 큰 라벨은 3이므로 연산 레지스터가 3개 이상 있는 컴퓨터에 대해서는

한 번도 STORE를 실행하지 않는 목적 코드를 생성 할 수 있다.

 

목적 코드를 생성하려고 하는데 label의 최대값이 컴퓨터가 가지고 있는 연산 레지 스터의 최대 개수보다 많으면

어떻게 할까? STORE 문을 사용해야 한다.

 

 

Register Allocation and Assignment 

 

코드 생성에서 가장 중요한 핵심은 어떤 값을 어떤 레지스터에 저장할지 결정하는 것

● 레지스터는 메모리 계층에서 가장 빠른 장치이지만, 모든 값을 저장할 수 있는 충분한 레지스터를 갖기는 힘들기

     때문에 레지스터에 저장되지 않은 값을 메모리에 저장할 필요가 있다.

● 프로그램의 각 위치에서 어떤 값을 레지스터에 저장할 것인지, 즉 레지스터 할당(register allocation) 그리고

      각 값을 어떤 레지스터에 저장할 것인지, 즉 레지스터 배정(register assignment)에 대해 다양한 기법을 살펴 본다.

 

레지스터 할당기(register allocator):

● 입력: 컴파일된 코드 (스캔, 파싱, 의미분석, 최적화, 타겟코드변환)

● 컴파일된 코드를 받아서 타겟 기계의 레지스터에 맞춤

● 로드와 저장 연산의 비용을 최소화

 

레지스터 할당기(register allocator) 의 목표는

● 목적 기계에 의해 제공되는 레지스터를 효율적으로 사용하는 것으로

● 레지스터 할당과 레지스터 배정 두 가지 문제를 동시에 해결한다.

 

할당기는 어떤 값이 안전하게 레지스터에 저장될 수 있는지 결정해야 한다.

그리고 과연 레지스터에 저장하는 것이 유용한지도 판단해야 한다.

좋은 성능을 얻기 위해 할당기는 가능한 한 많은 메모리 기반 값을 레지스터에 할당해야 한다.

 

Local Register Allocation and Assignment

 

지역 레지스터 할당과 배정

● 대부분의 컴퓨터는 일반 목적 레지스터와 부동 소수점 레지스터를 가지고 있다.

      ○ 일반 목적 레지스터는 정수 값과 메모리 주소를 저장하는 데 사용되고,

      ○ 부동 소수점 레지스터는 실수 값을 저장하는 데 사용된다.

● 하나의 기본 블록 안에서 레지스터 할당하는 방법을 지역 레지스터 할당이라 한다.

 

지역 레지스터 할당에서 발생할 수 있는 문제를 생각해보자.

● 가정: 기본 블록에서 시작해서 끝나는 프로그램. 이전 실행되는 기본 블록으로부터 어떠한 값도 전달받지 않으며,

     이후에 실행되는 기본 블록을 위해 어떠한 값도 남겨두지 않는다. 목적 기계는 k개의 일반 목적 레지스터만 제공한다.

● 하향식(top-down) 방법은 해당 기본 블록의 한 값에 대한 참조의 개수를 세고, 이 빈도수를 사용하여 어떤값 을

     레지스터를 통해 유지할지 결정하는 것이다. 이처럼 참조 빈도수에 의존하기 때문에 하향식 방법이라고 한다.

● 상향식(bottom-up) 방법은 해당 블록 전체를 각 연산별로 확인하면서 register spill이 필요한지 여부를 결정

      ○ register spill: 어떤 계산을 할 때 레지스터가 필요한데 이미 가능한 모든 레지스터가 사용되고 있을 때,

           레지스터를 확보하기 위해 사 용되고 있는 레지스터 중에서 하나를 선택하여 그 내용을 메모리 위치에 저장

      ○ 이는 많은 저차원(low-level) 정보를 사용하기 때문에 상향식 방법이라고 하는 것

 

Top-down Local Allocator

● 가장 많이 사용되는 값이 레지스터를 사용해야 한다는 기본 원칙을 토대로 동작

● 지역 할당기는 해당 블록에서 가상 레지스터가 발생 하는 횟수를 세고 이 빈도수를 사용하여 가상 레지스터 를 실제 레지스터에 할당한다.

● 이 방식의 가장 큰 단점은 전체 기본 블록에 대해 하나의 실제 레지스터를 하나의 가상 레지스터를 위해 사용 한다는 데 있다. 따라서 하나의 값이 해당 기본 블록의 앞부분에서 자주 사용되고 뒷부분에서 사용되지 않더 라도 블록 전체에서 해당 값을 위해 하나의 실질적인 레지스터가 사용되기 때문에 해당 블록의 뒷부분에서 실제 레지스터가 더 이상 사용되지 않는다는 문제 발생

 

Bottom-up Local Allocator: top-down 방식의 문제점들을 해결하기 위한 방식

● 각 연산이 실행될 때 발생하는 레지스터 할당에 집중하는 방법. 사용되고 있지 않은 모든 레지스터를 사용하 여 시작된다.

● 각 연산이 실행되기 전에 피연산자가 반드시 레지스터에 저장되어 있어야 한다는 가정에서 시작한다. 연산의 결과를 위해서도 하나의 레지스터를 할당해야 한다. 해당 블록 내에서 연산을 반복적으로 분석하면서 할당에 필요한 결정을 수행한다.

● Operation:

   ○ 먼저 실제 레지스터가 사용되지 않는다고 간주하고 실제 레지스터를 free list에 추가한다.

   ○ 첫 번째 몇몇 연산 동안 free list로부터 실제 레지스터를 반환하여 사용한다.

   ○ 할당기가 다른 레지스터를 필요로 하고 free list가 비어 있음을 발견하면 한 레지스터의 값을 메모리로 옮긴다.

   ○ 이 때 메모리에 옮기는 값은 할당기가 다음에 사용하는 값 중에서 가장 나중에 사용할 값이다.

   ○ 하나의 값을 고르도록 하는 데 드는 비용이 모든 레지스터에 대해 동일하다면 가장 긴 시간 동안 사용되는

         레지스터를 선택한다.

   ○ 몇몇 측면에서 이는 register spill의 비용으로 얻는 이득을 최대화한다.

 

 

Global Register Allocation and Assignment

 

Global Register Allocation:

● 각 내부 루프에서 가장 활발하게 사용되는 값을 저장하기 위해 레지스터의 고정된 개수를 배정 하는 것이다.

     할당되지 않은 레지스터는 기본 블록에서 지역 적인 값을 저장하는 데 사용된다.

● 레지스터에의 저장과 상응하는 로드 명령어들이 실행되면서도 값을 유지하기 위해서, 빈번하 게 사용되는 변수를

     레지스터에 배정하고, 배정된 레지스터들이 여러 블록에 걸쳐서(전역적) 계속 이 값을 유지하도록 해야 한다.

● 내부 루프의 경우 프로그램 실행 시간의 대부분을 소비하므로 루프의 처음부터 끝까지 빈번하 게 사용되는 값을

     고정된 레지스터에 놓고 계속 사용

 

흐름 그래프의 루프 구조를 알고 있다면 기본 블록에서 계산된 값 가운데 어떤 값이 그 블록 외부에 서도 사용되는지 알 수 있음. 기본 블록에서 계산된 값 가운데 어떤 값이 그 블록 외부에서도 사용되 는지를 계산하는 데는 DAG를 이용할 수 있다.

 

Graph Coloring

 

Recap:

● register spill은 어떤 계산을 할 때 레지스터가 필요한데 이미 가능한 모든 레지스터가 사용되고 있을 때,

      레지스터를 확보하기 위해 사용되고 있는 레지스터 중에서 하나를 선택하여 그 내용을 메모리 위치에 저장하는

      것을 의미

 

Graph coloring은 간편하고 체계적으로 register spill을 수행

● Graph coloring에는 2-패스가 사용된다.

● 첫 번째 패스에서는 제한된 레지스터를 가지고 목적 기계 명령어를 선택한다. 효율성을 위해 중간 코드에서 사용된 이름은 레지스터 이름이 되고, 3-주소 명령어는 기계어 명령어로 바뀐다.

● 두 번째 패스는 기호 레지스터(symbolic register)에 실제 레지스터를 배정하고 register spill의 비용을 최소화 하는 방법을 찾는 것이다.

    ○ 각 프로시저마다 레지스터 간섭 그래프(register-interference graph)를 구성한다. 

    ○ 노드는 기호 레지스터이다. 한 노드가 다른 노드가 정의되는 지점에서 살아 있으면 이 두 노드를 edge로 연결한다.

 

배정 가능한 레지스터의 개수를 k라고 할 때, k-coloring 알고리즘을 이용하여 레지스터-간섭 그래프를 색칠할 수 있 다. 인접한 2개의 노드가 동일한 색을 가지지 않는 방식으로 각 노드가 한 색을 배정받았다면 그 그래프는 coloring 되었다고 (colored) 한다. 여기서 각각의 색은 레지스터를 나타낸다.

 

주어진 그래프가 k-coloring 가능한지를 결정하는 문제

● NP-완전이지만, 경험적인 기법을 이용하여 Graph coloring을 빠르게 할 수 있음

● 인접 노드와 다른 색을 배정

● Edge 수가 많은 노드부터 색을 배정

 

Example) 다음 그래프에 대해 Graph coloring을 해보자.