Data Flow Analysis - 2 (Available Expression)

3. Available Expression Problem

지난 정의에 따르면 이 문제는 다음과 같다.

• The available expressions problem

• 위치 $P$에서 어떤 expression이 항상 사용 가능한가 (always)?

즉, 이 말은 다음과 같다.

y = a + b; // Exp 1

// point P

Exp 1에서 a+b라는 expression을 사용하였다. 우리는 Exp 1부터 Point P까지 a값과 b값이 변하지 않았기 때문에 expression a+b를 그대로 사용할 수 있다. 우리는 a+b를 available expression이라 지칭한다.

y = a + b; // Exp 1

if( a > 0 )

{

  a = 3;

}

// point P

하지만 위 예제에서 Exp 1에 사용된 a+b는 point P에서 사용할 수 없다. 그 이유는 if문에서 a값이 수정되었을 수 있기 때문이다. 다시 말하면, Exp 1에 사용된 a+b expression은 point P에서 available 하지 않다.

이러한 관찰에서 a+b가 사용되었다면 우리는 available expression이 generated 되었다 말하고, a 또는 b 변수가 바뀌어 a+b expression 값 자체가 바뀌었다면 우리는 기존 available expression이 killed되었다고 말한다. 이를 수식으로 표현하면 다음과 같다.

Expression이 a+b가 BB 블럭 내에서 생성되었다면 $$Gen(BB) = \{a+b\}$$

Expression a+b가 BB블럭 내에서 없어졌다면 $$Killed(BB)=\{a+b\}$$

Expression이 $Gen$된 시점과 $Killed$된 시점은 다음과 같다.

y = a + b;

// a + b expression이 generated 되었다.

if( a > 0 )

{

  a = 3;

  // a + b expression이 killed 되었다.

}

// point P

이를 control flow graph를 통해 보면 다음과 같다.

위 graph를 보면 BB1와 BB2가 BB3에서 만난다(meet). 만난다는 의미를 위해 우리는 meet operator($\wedge$)를 도입하겠다. 만약, BB1 마지막 포인트의 available expression을 $V_{out(BB1)}$이라 하고 BB2 마지막 포인트의 available expression을 $V_{out(BB2)}$라 하고, BB3 진입 포인트의 availble expression을 $V_{out(BB3)}$이라 하면 수식 표현은 다음과 같다.

$$V_{in(BB3)} = V_{out(BB1)} \wedge V_{out(BB2)}$$

이 표현은 말 그대로 $V_{out(BB1)}$과 $V_{out(BB2)}$가 $\wedge$(만났다)라는 것이다. 이 때, 각 $V$에 대하여 available expression 집합은 다음과 같다.

$$ V_{out(BB1)} = \{a + b\} $$

$$ V_{out(BB2)} = \{\} $$

위 분석을 토대로

Q) 만약 이 두개의 집합이 $\wedge$(만났을) 때, $V_{in(BB3)}$에서 always(항상) availble expression은 무엇인가?

A) "available expression은 없다."

라고 available expression problem을 풀 수 있다. 그 이유는 a+b는 BB2에서 killed되었기 때문이다. 이는 $\wedge$가 $\cap$ 역할을 한다고 유추해낼 수 있다. 즉,

$$\wedge = \cap$$

다시 말하면,

$$V_{in(BB3)} = V_{out(BB1)} \wedge V_{out(BB2)} = V_{out(BB1)} \cap V_{out(BB2)}$$

이다. 그리고 $V_{out(BB3)}$은 다음과 같이 계산한다.

$$V_{out(BB3)} = Gen(BB3) \cup (V_{in(BB3)} - Killed(BB3))...[1]$$

이제까지 우리는 expression의 generation과 kill, 그리고 meet($\wedge$)를 알아보았다. 이제 좀 더 복잡한 예제에 적용해보려 한다.

위 그림에서 표현된 expression을 기호로 매핑해보았다.

Expression	Notation
u+3	$e_1$
v-4	$e_2$
w*2	$e_3$
x-1	$e_4$
y+1	$e_5$

그리고 간단한 B1 block부터 살펴보자. B1 block은 expression을 $\{e_1, e_2, e_3\}$를 generated하고 있다. 그리고 x와 y variable 값을 변경하므로 $\{e_4, e_5\}$를 killed하고 있다. 즉,

$$gen(B1) = \{e_1, e_2, e_3\}$$

$$kill(B1) = \{e_4, e_5\}$$

이다. 이를 각 블럭에 대해 정리하면

Blocks	Generated	Killed
B1	$\{e_1, e_2, e_3\}$	$\{e_4, e_5\}$
B2	$\emptyset$	$\{e_4, e_5\}$
B3	$\{e_5\}$	$\emptyset$
B4	$\emptyset$	$\{e_4\}$
B5	$\emptyset$	$\emptyset$

이다.

또한 available expression은 rule out(부분제거) 방식으로 이루어진다. 이 말은 임의의 expression이 basicblock을 통과했을 때, killed 되지 않은 expression은 그대로 통과한다는 뜻이다. 예를들면 다음과 같은 block이 있다.

a = 3;

위 블럭에 x+y expression이 input으로써 통과한다고 해도 x+y는 그대로 available expression이다. 만일 a에 dependency를 가지지 않는 $\{e_1, e_2, e_3\}$ expression들을 통과시킨다고 해도 $\{e_1, e_2, e_3\}$는 그대로 available expression들이다.

이 때문에 위 블럭들은 다음과 같이 초기화 된다.

Blocks	Expression input	Expression output
B1	$\emptyset$	$\{e_1, e_2, e_3\}$
B2	$\{e_1, e_2, e_3, e_4, e_5\}$	$\{e_1, e_2, e_3\}$
B3	$\{e_1, e_2, e_3, e_4, e_5\}$	$\{e_1, e_2, e_3, e_4, e_5\}$
B4	$\{e_1, e_2, e_3, e_4, e_5\}$	$\{e_1, e_2, e_3, e_5\}$
B5	$\{e_1, e_2, e_3, e_4, e_5\}$	$\{e_1, e_2, e_3, e_4, e_5\}$

위를 보면 expression input은 B1을 제외한 모든 블럭에서 전체집합$\{e_1, e_2, e_3, e_4, e_5\}$이 들어갔다. 이는 가능한 모든 expression이 들어간 상황을 가정하고 각 블럭에서 available expression들이 killed 된 상황을 보여주고 있다. 단 B1은 input expression이 $\emptyset$인데 이는 entry point이고 초기 상태에서는 어떠한 expression도 input이 될 수 없음을 의미한다. 이러한 상황을 initial state라 부른다.

이후 DFS order인 B1, B2, B3, B5, B4로 각 블럭마다 available expression input과 output을 계산하게 된다.

1. B1은 input이 $\emptyset$이고, output은 $\{e_1, e_2, e_3\}$이다.
2. B2의 input은 $output(B1) \wedge output(B5)$이고 이는 $\{e_1, e_2, e_3\}$이다. 이후 전에 언급된 [1] 공식에 따라 $output(B2)$은 $Gen(B2) \cup (input(B2) - Killed(B2))$로 계산되어 $\{e_1, e_2, e_3\}$이다.
3. B3의 input은 $output(B2)$을 직접 받으므로 $\{e_1, e_2, e_3\}$¹이고, [1] 공식에 따라 $output(B3)$은 $\{e_1, e_2, e_3, e_5\}$이다.
4. B5의 input은 $output(B3)$ \wedge output(B4)$이고 이는 ${e1, e2, e3, e5}$이다. [1] 공식에 따라 $output(B5)$은 ${e1, e2, e_3}$이다.
5. B4의 input은 $output(B2)$을 직접 받으므로 $\{e_1, e_2, e_3\}$이고, [1] 공식에 따라 $output(B4)$은 $\{e_1, e_2, e_3\}$이다.

B1부터 B5까지 계산된 후, 첫번째 iteration의 결과는 다음과 같다.

Blocks	Expression input	Expression output
B1	$\emptyset$	$\{e_1, e_2, e_3\}$
B2	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3\}$
B3	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3, e_5\}$
B4	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3\}$
B5	$\{e_1, e_2, e_3, e_5\}$	$\{e_1, e_2, e_3, e_5\}$

이 때, 위 그래프를 자세히 보면 natural loop가 존재하는데, 이를 해석하는 방법은 다음과 같다.

위 그림을 보면 $B_x$의 output available expressions들은 $B_y$의 input available expressions이 된다. 이는 $B_x$로 들어가 $B_x$의 input available expressions가 된다. 이를 충분한 횟수 이상 반복하면 각 block의 available epxressions이 변하지 않고 수렴하게 된다. 이를 converge라고 하는데 이는 뒤의 unified DFA framework에서 더 자세히 다룬다. 중요한건

Available expression에 대해 loop를 반복하다보면 available expression이 converge된다.

그러므로 B1부터 B5를 쭉 두번째 iteration 한다. 결과는 다음과 같다.

Blocks	Expression input	Expression output
B1	$\emptyset$	$\{e_1, e_2, e_3\}$
B2	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3\}$
B3	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3, e_5\}$
B4	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3\}$
B5	$\{e_1, e_2, e_3\}$	$\{e_1, e_2, e_3\}$

이후 세번째, 네번째를 해도 이 expression input과 output은 변하지 않는다. 즉, 결과가 converge되었다. 이 결과에 대해 해석을 하면 다음과 같다.

"B5의 input available expression은 $\{e_1, e_2, e_3\}$밖에 없으며, 이에 대한 output available expression은 $\{e_1, e_2, e_3\}$이다."

그리고 만약 B1의 output point부터 끝까지 $\{e_1, e_2, e_3\}$은 공통된(common) expression이 된다. 즉, 위에서 보았던 중복된 expression을 지울 여지가 생긴 것이다.

다음은 reaching definition을 정리하겠다.

위 내용은 개인적인 공부를 정리한것이라 틀릴 수 있습니다. 검토가 필수적입니다.

---

1 최근에 계산된 output expressions을 써야 한다.↩