[Compiler] Liveness analysis w. CFG

Forward liveness analysis.

1. 위의 식을 기억하고 넘어감.

2. in[n] 먼저 하고 out[n] 진행

 

 

---

이런 명령어를 가진 그래프가 있다고 하자.

 

3. 초기 상태는 다음과 같다.

 

4. 공식에 넣기 위해 use, def 를 구한다.

use 는 명령어에서 보통 사용되는 변수 집합이라고 생각하면 되고

def 는 정의되는(값이 변하는) 변수라고 생각하면 된다.

 

5. 갱신

in[n] 먼저 구하는데, in[n] 은 use[n] U (out[n] - def[n]) 이다.

이후 out[n] 을 구하는데, out[n] 은 successor의 in 을 가져온다.

 

1st

명령어 1번 : in, out이 모두 공집합 상태이고, def 를 빼도 아무것도 남지 않는다.

in[1] = {}

out[1] =  in[2] = {}

이렇게 명령어 하나 지날 때 마다 업데이트 되는 개념임.

 

명령어 2번 

in[2] = {a} U ({} - {b}) = {a}

out[2] = in[3] = {}

 

명령어 3번 

in[3] = {bc} U ({} - {c}) = {bc}        -> {} - {c} = {}

out[3] = in[4] = {}

 

명령어 4번 

in[4] = {b} U ({} - {a}) = {b}

out[4] = in[5] = {}

 

명령어 5번 

in[5] = {a} U ({} - {}) = {a}

out[5] = in[2] U in[6] = {a} U {} = {a}

여기는 분기가 나뉘어 있어서, 현재까지 들어온 값에서 처리함.

1번 사이클에서 명렁어 2번에 의해 in[2] 가 이미 최신화되었기 때문에 그 값을 사용한다는 의미

 

명령어 6번

in[6] = {c} U ({} - {}) = {c}

out[6] = {}, 연결 X

 

1번 사이클을 지난 후 값 (inst# in/out)

inst1 : {} / {}

inst2 : {a} / {}

inst3 : {bc} / {}

inst4 : {b} / {}

inst5 : {a} / {a}

inst6 : {c} / {}

표의 1번째 사이클과 같은 것을 확인 가능함.

이것을 더 이상 최신화 되지 않을 때 까지 수행 (previous sets == current sets)

 

 

 

 

 

---

Backward liveness analysis.

 

1. 마찬가지로 위의 식을 기억하고 넘어감.

2. out[n] 을 먼저 계산하고 in[n] 을 계산한다.

 

---

이런 명령어를 가진 그래프가 있다고 하자. (Forward 와 동일)

 

3. 초기 상태는 다음과 같다. (Forward 와 동일)

 

4. 공식에 넣기 위해 use, def 를 구한다. (Forward 와 동일)

 

---

5. 1차 갱신

successor 를 파악해야 하므로 가장 끝 노드에서부터 처리를 시작한다.(backward 는 6번부터 1번으로 감)

out - in - out - in - ... 순서로 처리를 한다.

 

 

6. 2차 갱신

 

값이 변할 때 까지 업데이트

 

8. 최종 결과