Data Flow Analysis - 1 (Intro)

Data Flow Analysis 정리

1. Data Flow Analysis

코드 분석에는 두가지로 나누어진다.

• Control flow analysis
  • 제어 흐름을 분석한다.
• Data flow analysis
  • 데이터의 흐름을 분석한다.

컴파일러 최적화를 위해서는 control flow와 data flow 분석을 완료하고, 이 분석된 자료를 토대로 optimization을 진행한다. 이 중 data flow analysis를 보기 위해 다음과 같은 예를 가져왔다.

y = a + b;
z = a + b;

위 코드를 보면 불필요하게 a+b를 여러번 계산하고 있다. 이를 알아내는것이 data flow analysis이다. 그리고 불필요한 계산을 없애는 것을 compiler optimization이라 한다. Compiler optimization 이후에는

t = a + b;
y = t;
z = t;

로 최적화 하여 a+b의 계산 횟수를 줄인다. 위처럼 CFA(Control Flow Analysis) 또는 DFA(Data Flow Analysis)로 분석한 자료는 optimization의 단초가 된다.

2. Data Flow Analysis Problems

우리는 코드를 작성할 때, 코드 한 줄을 statement라 부른다. Statement는 다음과 같이 이루어져 있다.

x = a + b;
y = 3;
z = &x; // z is pointer variable

이때 각 분석 요소를 설명하면

Definition

Varaible에 저장된 정의. 위 예에서는 x는 a + b로 정의되어 있다.

Expression

a + b로 연산의 표현

Variable

x 변수 (값이 아닌 변수)

Constant

3 상수

Aliase

x와 z는 같은 메모리 위치를 가리키므로 서로 aliase라 한다.

Range

변수 x가 가질 수 있는 값의 범위 (위 예제는 constant)

그리고 위 요소와 관련된 문제는 다음과 같이 있다.

• The available expressions problem
  • 위치 $P$에서 어떤 expression이 항상 사용 가능한가 (always)?
• The reaching definitions problem
  • 위치 $P$에서 어떤 definition이 도달할 수 있는가 (possible)?
• The live variables problem
  • 위치 $P$에서 어떤 variable이 지속적으로 사용되고 있는가 (possible)?
• The constant propagation problem
  • 위치 $P$에서 각 variable들이 어떤 constant를 항상 갖고 있는가 (always)?
• The aliasing problem
  • 위치 $P$에서 어떤 variable들이 서로 aliase¹될 수 있는가 (possible)?
• The symbolic range problem
  • 위치 $P$에서 variable이 가질 수 있는 값의 범위는 어떻게 되는가 (always)?

이 때, 괄호에 있는 always와 possible이 중요한데, 이는 "컴파일러 최적화는 코드의 correctness를 위반하면 안된다."라는 원칙에 근거한다. 즉, 코드 최적화 후 동작이 이상해지면 안된다는 의미이다. Compiler optimization에 사용할 근거 자료들은 어떠한 경우에도 correct해야 한다. 즉, always(항상) 같은 결과를 유지해야 한다는 것이다. Always 에 대한 답을 구하기 위해서는 다음과 같은 방법이 있다.

• Always: 집합 자체를 답으로 구한다.
• Never: Possible $P$ 집합을 구한 뒤, 전체 집합 $U$에서 $P$를 뺀다($U-P$).

항상 always 집합을 구할 수는 없다(힘들다). 우리는 대우법(antithesis)를 사용하는것과 마찬가지로 possible 집합을 구한 뒤, 전체집합에서 뺌으로써, always 집합을 구할 수 있다.

---

1. 서로 다른 두 변수가 같은 메모리를 참조하고 있을 때, aliase라 한다. ↩