[컴파일러 이론] 10. Dataflow Analysis

컴파일러의 frontend에서는

사람이 작성한 source code를 lexical, systax, semantic ayalys

 

is를 통해 문법적으로 문제없는 코드라는 것을 보장했고,

AST를 만들었다.

front end와 back end를 연결하는 과정으로 이전글에서 봤던 code generation 과정이 있다.

여기서 AST를 IR로 바꿔서 back end로 넘긴다.

이번 글에서부턴 back end의 동작을 알아보자.

이 back end에서는 최적화를 하는데 프로그램의 자원 효율성을 높이는 것이다.

이 자원의 기준은 사람/프로그램 마다 다르다.

어떤 프로그램은 공간을 많이 쓰더라도 시간을 줄이는게 효율성을 높이는 것일 수도 있고 그 반대일 수도 있다.

그러나 어떤 방식으로 최적화를 하던지 프로그램의 결과는 바뀌면 안된다.

---

Basic Block (BB)

컴파일러의 back end부분을 설명할 때 계속 사용할 BB라는 중요한 개념이 있다.

이는 jump와 label이 포함되지 않은 최대로 연속해서 실행되는 명령어의 집합을 의미한다.

따라서 하나의 BB는 시작에서 끝까지 분기나 다른 코드에서 들어오는 부분이 없다.

 

---

Control Flow Graph(CFG)

CFG는 front end의 context free grammar와 약자는 같지만 아예 다른 것이다.

이 CFG는 control flow graph로 노드가 BB인 directed 그래프이다.

각 노드(BB)사이 화살표의 의미는 이전 BB의 마지막 명령어에서 화살표가 가리키는 BB의 첫번째 명령어로 가는 실행흐름이 있다는 것을 의미한다.

위에서 얘기한 BB와 CFG를 한번에 살펴볼 수 있는 예시를 보자.

색칠된 그룹이 각각 BB이다.

---

Optimization

optimization scope

최적화를 할 때 최적화 범위를 크게 3가지로 나눌 수 있다.

1. BB블럭 안에서만 최적화(local optimization)

2. CFG 안에서의 최적화(Global optimization)

3. 전체 범위에서 최적화(inter-procedural optimization)

---

optimization types

최적화의 종류는 크게 두 가지가 있다.

1. dataflow optimization

2. control flow optimization

우리는 이 두가지 각각을 앞으로 이어질 글들에서 자세히 알아볼 것이다.

 

---

Dataflow optimization

dataflow라는 것은 코드가 데이터를 다루는 것에 대한 것이다.

반복되는 계산을 삭제하거나, 계산을 단순화해서 최적화를 할 수 있다.

 

 

---

Dataflow optimization - Local optimization

1. algebraic simplification

아래처럼 무의미한 코드는 삭제가능하다.

x = x + 0

x = x * 1

 

또 아래처럼 코드 단순화도 가능하다.

y = y ** 2 → y = y * y

x = x * 8 → x = x << 3

x = x * 15 → t = x << 4 ; x = t - x

컴퓨터에서는 거듭제곱 보다는 그냥 곱하기가, 곱하기 보다는 비트쉬프트 연산이 더 효율적이기 때문이다.

 

2. constant folding

실행 중이 아닌 컴파일하는 동안 몇몇 식을 계산하는 것이다.

x = 2 +2 같은 코드는 바로 x = 4라고 바꿀 수 있다.

또 if 2<0 같은 것은 바로 false임을 알기 때문에 실행중에 판단하지 않고 컴파일 타임에 바로 판단 가능하다.

 

★하지만 이 constant folding은 컴파일러를 실행한 cpu와 실제 실행할 cpu가 다를 때는 위험할 수 있다.

일부 소수 연산의 정밀도 차이 때문에 두 cpu에서 다른 결과가 나올 수 있기 때문이다.

 

3. unreachable code

도달할 수 없는 BB를 삭제하는 것이다.

 

4. Dead code Elimination

아래 그림처럼 대입을 하고나면 a의 값은 더이상 사용되지 않으므로 이 가운데 줄은 삭제가 가능하다.

이 과정은 copy propagation이라고도 불린다.

하나의 최적화가 적용되면 다른 최적화가 적용되게끔 되는 상황이 자주 나오기 때문에 복합적으로 방식들을 적용해봐야한다.

 

---

Dataflow optimization - Global Optimization

BB는 보통 명령어 4~8개 정도로 작게 구성되어있다.

따라서 그 이상의 범위에서 최적화는 필수적이다.

 

1. Constant Propagation

아래 양쪽의 CFG에서 가장 마지막의 x를 상수로 바꾸려면 모든 경로에서 x값이 바뀌지 않아야 한다.

바뀌지 않았다면 왼쪽 그래프 같은 경우 A를 6으로 바로 바꿀 수 있다.

오른쪽 그래프는 어떤 경로를 타느냐에 따라 A가 바뀌므로 상수로 바꿀 수 없다.

 

global optimization의 특징이 있다.

어떤 값이 변하는지 등을 모든 분기, 모든 함수 같은 경우에서 파악하려면 너무 비용이 비싸기 때문에

컴파일러는 대신 보수적(conservative)으로 행동한다.

이 값이 고정인지 불확실하면 그냥 치환을 안하는 식이다.

따라서 dataflow analysis라는 것이 필요하다.

---

Dataflow Analysis

컴파일러가 이 변수가 어디에서 정의되어, 이 명령어까지 도달 가능할지, 중간에 값이 바뀔 가능성은 없는지 등을 분석한다.

이 분석에는 두 가지 종류가 있다.

1. Global analysis : BB의 경계 단위에서 해당 블록에 들어갈 때, 나올 때 상태를 계산한다.

2. Local analysis : BB내부에서 명령어 하나하나 단위로 명령어 실행 전, 후 상태에 대해 계산한다.

---

Dataflow analysis 예시 - reaching definition

reaching definition은 local, global 분석이 복합적으로 필요한 dataflow analysis의 예시이다.

어떤 변수가 정의되고(x=3) 나중에 다른 값으로 다시 정의되면 (x=5)이 시점부터는 이전 정의는 쓸모가 없어진다.

따라서 어떤 정의의 도달가능한 범위는 재정의가 일어나기 전까지이다.

 

아래 예시를 보면 끝 부분에 도달할 수 있는 정의들이 무엇인지 물어보고 있다.

 

 

---

local analysis 부분

명령어 단위에서 명령어의 영향에 대해 먼저 살펴보자.

위에서 애기한 것처럼, 새 정의는 이전 정의를 kill한다.

 

global analysis 부분

BB의 범위에서 이 개별 명령어들의 영향을 더해 처리한다.

IN[BB], OUT[BB], GEN[BB], KILL[BB]

어떤 BB의 시작부분까지 살아있는 definition이 무엇인지, 

이 BB가 끝나고도 살아있는 definition이 무엇인지 표현하기 위해 IN[BB], OUT[BB]이라는 집합을 만들었다.

 

또 해당 BB안에서 새롭게 만들어진 definition들을 모은 집합인 GEN[BB]와,

프로그램 전체에 있던 명령어들 중 BB안의 명령어에 의해 죽은 definition들을 모은 집합인 KILL[BB] 라는 집합도 생각하자.

 

그렇다면 어떤 b라는 이름의 BB에 대해,

OUT[b] = GEN[b] U (IN[b] - KILL[b]) 가 된다.

즉 BB에 들어간 definition들 중 KILL된 애들은 빼고 새로 GEN된 애들은 추가하는 것이다.

이런 계산식을 transfer function이라고 한다.

 

여러 BB에서 하나의 BB로 화살표가 있을 때는 각 OUT을 합집합하면 그 다음 BB의 IN이 된다.

 

종합적인 예시이다.

 

먼저 오른쪽 위의 표를 만든다.

BB1을 예시로 들면, GEN은 당연히 1,2번 정의를 가지는 것을 알 수 있는데,

KILL에 왜 3,4,6이 있는지 이해가 얼핏 가지않을 수도 있다.

왜냐하면 BB1은 시작하자마자 바로 만나는 블럭이라 죽일 수 있는 정의가 없기 때문이다.

 

하지만 loop가 있는 CFG도 있기 때문에 이런 경우를 위해 흐름에 상관없이,

1번정의가 a를 정의하는 것이라면 다른 a에 대한 정의는 모두 죽이는 것이다.

 

표가 완성되었다면 초기값 "IN[BB1] = {}와 모든 OUTPUT은 공집합"만 주고 위에서 본 OUT[b] = GEN[b] U (IN[b] - KILL[b]) 집합연산에 따라 계산만 하면 된다.

 

loop가 있는 경우는 이 집합 연산을 여러번해 결과가 바뀌지 않을 때까지 하면된다.

---

Dataflow analysis 예시 - liveness analysis

또 다른 예시를 살펴보자.

아래 그림에서 x = 3은 더이상 사용되지 않아서 없애도 되는 코드가 되었다.

즉 x는 죽은 변수이다.

 

미래에 사용이 되는지를 알아야하는데 reaching definition처럼 앞에서부터 분석하는 것은 어려울 것이다.

따라서 liveness분석에서는 CFG를 역으로 거슬러 올라가며 분석한다.

 

아래 예시에서 y = x처럼 x가 사용되기 때문에 이 전까지 x는 live하다고 볼 수 있다.

x가 정의되는 순간부터 사용되는 순간까지 살아있다고 생각하기 때문에 x가 정의되기 전에는 죽어있다고 생각을 한다.

 

---

reeaching definition에서 IN[BB], OUT[BB], GEN[BB], KILL[BB]를 사용했듯이 여기서도 집합 계산을 한다.

IN, OUT은 BB전후로 살아있는 변수들의 집합이다.

USE[BB]는  BB에서 사용되는 변수들의 집합이다.

DEF[BB]는 BB에서 정의된 변수들의 집합이다.

 

transfer function은 아래와 같다.

IN[b] = USE[b] U (OUT[b] - DEF[b]) 

역순으로 올라가며 계산하므로 결과가 OUT이 아닌 IN이다.

 

만약 예를 들어 하나의 BB에서 3개의 BB가 나오는 구조가 있다면 3개의 BB의 IN중 하나라도 live하다면 부모 BB의 OUT에서도 live하다고 판단한다.

 

이번에도 예시를 보자.

이전처럼 테이블을 만들고 집합연산에 따라 연산하면 된다.

loop가 있으므로 계속 계산해서 변화가 없을 때까지 하면 된다.

 

---

Constant Propagation

앞에서 잠깐 언급했던 constant propagation은 특정 지점에서 변수를 상수로 바꿀 수 있는지 결정하는 것이다.

 

이를 위해 세 가지 타입이 필요하다.

각 타입의 기호와 의미는 아래와 같다.

T : 모르는 타입

c : 상수

⊥ : 상수가 아님

이 그림에서 몇가지 설명을 하면,

처음 x는 T타입으로 어떤 타입인지 몰랐지만 x = 3 정의가 실행되면 x는 상수(3)을 타입으로 가진다.

가장 마지막 BB에서 어떤 경로를 탔는지에 따라 x = 4, x = 3 중에 하나가 되는데 이는 어떤값이 될지 모르기 때문에 ⊥타입이 된다.

 

여기서도 역시 transfer function을 위해 IN/OUT[b][x], SET[b]라는 표현이 필요하다.

IN/OUT[b][x] : BB에 들어가기전, 나온 후의 변수 x값을 위미힌다.

SET[b] : BB안에서 새롭게 생성된 정의들의 집합

 

constant propagation에 대한 transfer function은 좀 복잡하다.

 

1. 먼저 OUT[b] = IN[b]로 설정해준 후

2. SET[b]안의 모든 정의 각각에 대해: (예를 들어  x = a + b + c)

 2-1) 우변에서 하나라도 ⊥라면 : OUT[b][x] = ⊥

 2-2) 우변에서 하나라도 T라면 : OUT[b][x] = T

 2-3) 나머지 경우(우변 모두 상수) : OUT[b][x] = 계산된 상수 값 (a+b+c)

 

여러 BB에서 하나의 BB로 화살표가 가는 상황에서는 

어떤 변수에 대한 각 BB의 OUT을 조합해야한다.

모든 BB에서 x = 3이라는 값이 있다면 당연히 마지막 BB에서도 x=3이다.

하지만 몇개의 BB에서는 x=3인데, 또 몇개에서는 x=4라는 정보가 내려오면, x = ⊥가 된다.

만약 최종 BB로 오는 값 중 T타입이 있다면 무시한다.

즉, x=3,x=3,x=T가 하나의 BB로 들어오면 x=3이 된다.

 

아래는 예시이다.