맨위로가기

데이터 흐름 분석

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

데이터 흐름 분석은 프로그램의 제어 흐름 그래프를 기반으로 변수의 정의, 사용, 생존 여부 등을 분석하는 기법이다. 전이 함수와 결합 연산을 사용하여 기본 블록의 데이터 흐름 정보를 계산하고 반복적으로 갱신하여 해를 구한다. 정방향 분석과 역방향 분석으로 구분되며, 도달 정의 분석과 생존 변수 분석이 대표적이다. 흐름 민감도, 경로 민감도, 문맥 민감도를 고려하며, 반복 알고리즘과 작업 목록 알고리즘을 통해 데이터 흐름 방정식을 푼다. 주요 분석 유형으로는 도달 정의 분석, 생존 변수 분석, 상수 전파 등이 있다.

더 읽어볼만한 페이지

  • 데이터 흐름 분석 - 사용-정의 체인
    사용-정의 체인은 변수의 정의 지점과 사용 지점을 연결하여 데이터 흐름을 파악하고 코드 최적화, 오류 검출, 리팩토링 효율성을 향상시키는 개념이다.
  • 컴파일러 최적화 - 느긋한 계산법
    느긋한 계산법은 계산 결과가 필요할 때까지 계산을 늦추는 방식으로, 함수형 프로그래밍 언어에서 유용하게 사용되며 무한 데이터 구조를 다루거나 불필요한 계산을 피하는 데 효과적이다.
  • 컴파일러 최적화 - 인라인 확장
    인라인 확장은 컴파일러가 함수 호출 지점에 함수의 코드를 직접 넣어 실행 속도를 빠르게 하지만 코드 크기가 커지는 단점이 있어 자주 호출되는 작은 함수에 적합한 최적화 기법이다.
  • 프로그램 분석 - 정적 프로그램 분석
    정적 프로그램 분석은 소프트웨어 개발 시 코드를 실행 없이 분석하여 오류, 보안 취약점, 코딩 표준 위반 등을 탐지하는 기술로, 개발 비용 절감, 품질 향상, 시스템 신뢰성 확보에 기여하며 다양한 레벨로 분석 가능하다.
  • 프로그램 분석 - 기호 실행
    기호 실행은 프로그램의 모든 실행 경로를 탐색하여 버그를 찾는 기술로, 경로 폭발 문제와 기술적 한계에 직면하지만, 다양한 기법과 도구들을 통해 소프트웨어 보안 분야에서 활용된다.
데이터 흐름 분석

2. 기본 원리

데이터 흐름 분석은 프로그램의 제어 흐름 그래프를 기반으로 각 지점에서 변수가 어떻게 사용되는지에 대한 정보를 수집하는 과정이다. 일반적으로 기본 블록의 경계에서 정보를 얻는 것으로 충분한데, 이는 기본 블록 내에서 각 지점의 정보를 계산하기 쉽기 때문이다.

각 블록 b에 대해 다음과 같은 데이터 흐름 방정식을 정의할 수 있다.


  • out_b = trans_b (in_b)
  • in_b = join_{p \in pred_b}(out_p)


여기서,

  • trans_b 는 블록 b의 전이 함수로, 블록의 시작 상태 in_b에 적용되어 종료 상태 out_b를 만든다.
  • 결합 연산 join은 b의 선행 블록 p \in pred_b들의 종료 상태를 결합하여 b의 시작 상태를 만든다.


이 방정식들을 풀면 블록의 시작 및 종료 상태를 통해 프로그램의 속성을 파악할 수 있다. 각 문장의 전이 함수를 개별적으로 적용하면 기본 블록 내부 지점의 정보도 얻을 수 있다.

데이터 흐름 분석에는 고유한 전이 함수와 결합 연산이 필요하며, 역방향 분석이 필요한 경우도 있다. 역방향 분석은 전이 함수가 종료 상태에 적용되어 시작 상태를 만들고, 결합 연산이 후행 블록의 시작 상태에서 작동하여 종료 상태를 만든다는 점을 제외하면 정방향 분석과 동일하다.

진입점은 선행 블록이 없으므로 분석 시작 시 시작 상태가 잘 정의되어야 한다. 예를 들어, 알려진 값을 가진 지역 변수의 집합은 비어 있을 수 있다.

제어 흐름 그래프에 사이클(반복문)이 없다면, 위상 정렬을 통해 각 블록의 시작 상태를 쉽게 계산할 수 있다. 그러나 사이클이 있다면 더 복잡한 알고리즘이 필요하다.

2. 1. 정방향 분석과 역방향 분석

데이터 흐름 분석은 프로그램의 시작 지점부터 끝 지점까지, 또는 그 반대 방향으로 데이터의 흐름을 추적하여 변수가 어떻게 사용되는지에 대한 정보를 수집하는 기법이다.
정방향 분석(Forward Analysis)프로그램의 시작 지점부터 끝 지점 방향으로 데이터 흐름을 분석한다. 각 블록의 시작 상태는 선행 블록들의 종료 상태에 의해 결정되며, 블록 내의 각 구문은 종료 상태를 갱신한다.

  • 도달 정의 분석(Reaching Definitions Analysis): 각 프로그램 지점에서 해당 지점에 도달할 수 있는 변수의 정의(값 할당)를 추적한다. 예를 들어, 특정 변수가 어떤 행에서 값을 할당받았는지를 파악하여, 해당 변수가 사용되는 지점에서 어떤 값을 가질 수 있는지 예측하는 데 사용된다.

역방향 분석(Backward Analysis)프로그램의 끝 지점부터 시작 지점 방향으로 데이터 흐름을 분석한다. 각 블록의 종료 상태는 후행 블록들의 시작 상태에 의해 결정되며, 블록 내의 각 구문은 시작 상태를 갱신한다.

  • 생존 변수 분석(Live Variable Analysis): 각 프로그램 지점에서 이후에 사용될 가능성이 있는 변수(생존 변수)를 추적한다. 이를 통해 사용되지 않는 변수에 대한 불필요한 연산을 제거하는 데드 코드 제거 최적화에 활용할 수 있다.[1]


```text

if b == 4 then

a = 5;

else

a = 3;

endif

if a < 4 then

...

```

위 코드에서 변수 `a`의 7행에 대한 도달 정의는 2행의 `a = 5` 할당과 4행의 `a = 3` 할당의 집합이다.[1]

생존 변수 분석은 각 프로그램 지점에 대해 다음에 다시 쓰이기 전에 잠재적으로 읽힐 수 있는 변수를 계산한다. 결과는 일반적으로 값이 나중에 사용되지 않는 변수에 할당하는 문을 제거하기 위해 데드 코드 제거에 사용된다.[1]

2. 2. 흐름 민감도, 경로 민감도, 문맥 민감도


  • '''흐름 민감(Flow-Sensitive) 분석''': 프로그램 문장의 순서를 고려한다. 예를 들어, 흐름에 민감하지 않은 포인터 분석은 "변수 x와 y가 같은 위치를 가리킬 수 있다"라고 판단하지만, 흐름 민감 분석은 "20번째 문장 이후 변수 x와 y가 같은 위치를 가리킬 수 있다"라고 판단할 수 있다.[1]

  • '''경로 민감(Path-Sensitive) 분석''': 조건 분기문의 조건에 따라 다른 분석 결과를 생성한다. 예를 들어, 분기 조건이 `x > 0` 이라면, 분기가 없을 때는 `x <= 0` 이라고 가정하고, 분기가 있을 때는 `x > 0` 이라고 가정한다.[1]

  • '''문맥 민감(Context-Sensitive) 분석''': 함수 호출 시 호출 위치의 문맥을 고려하여 분석한다. 문맥 정보를 사용하면 원래 호출 위치로 돌아갈 수 있지만, 문맥 정보가 없으면 분석 정보가 가능한 모든 호출 위치로 전파되어 정확성이 떨어질 수 있다.[1]

3. 반복 알고리즘

데이터 흐름 방정식을 푸는 가장 일반적인 방법은 반복 알고리즘을 사용하는 것이다. 이 방법은 각 블록의 입구 상태(In-State)와 출구 상태(Out-State)를 초기화하고, 전이 함수와 결합 연산을 반복적으로 적용하여 값이 변하지 않는 고정점(Fixed Point)에 도달할 때까지 계산한다.[1]

데이터 흐름 방정식의 고정점은 아래의 "라운드 로빈 반복 알고리즘"을 사용하여 계산할 수 있다.



데이터 흐름 방정식의 반복 계산 효율은 노드 그룹을 방문하는 순서에 영향을 받는다. 위의 라운드 로빈 반복 알고리즘에서는 노드를 계산하는 순서(번호)가 영향을 미친다. 또한, 제어 흐름 그래프에 대해 데이터 흐름 방정식이 전방 분석되는지 후방 분석되는지도 영향을 미친다.


  • 무작위 순서 (random order): 순서를 신경 쓰지 않고 데이터 흐름 방정식을 풀어 나간다. 성능은 다른 것에 비해 낮다.
  • 트리 구조의 후행 순서 (postorder): 후방 데이터 흐름 문제에서 일반적인 반복 순서이다. 자식 노드를 모두 방문한 후 부모 노드를 방문하는 순서에 해당한다.
  • 역후행 순서 (reverse postorder): 전방 데이터 흐름 문제에서 일반적인 반복 순서이다. 후행 순서의 거의 반대 움직임이지만, 선행 순서 (preorder) 와는 다르다.

3. 1. 라운드 로빈 반복 알고리즘

데이터 흐름 방정식을 푸는 가장 기본적인 알고리즘은 '''라운드 로빈 반복 알고리즘'''이다.[1] 이 알고리즘은 다음 의사 코드로 표현할 수 있다.

```

for i ← 1 to N

노드 i를 초기화

while (집합이 아직 변화하고 있다)

for i ← 1 to N

노드 i에서의 집합을 재계산

```

라운드 로빈 반복 알고리즘은 각 블록의 들어오는(in) 상태를 근사치로 설정하고,[1] 나가는(out) 상태는 들어오는 상태에 전이 함수를 적용하여 계산한다.[1] 이후 들어오는 상태는 상한(join) 연산을 통해 갱신하며,[1] 이 과정을 들어오는 상태와 나가는 상태가 변하지 않는 고정점(fixpoint)에 도달할 때까지 반복한다.[1]

3. 2. 작업 목록(Worklist) 알고리즘

데이터 흐름 방정식을 푸는 기본 알고리즘은 라운드 로빈 반복 알고리즘이지만, 이를 개선한 것이 작업 목록(Worklist) 알고리즘이다.[1]

작업 목록 알고리즘은 아직 처리해야 할 블록들의 목록인 '''작업 목록'''을 활용한다. 블록의 나가는 상태(out-state)가 변경될 때마다, 해당 블록의 후행 노드(successor)들을 작업 목록에 추가한다. 각 반복에서 작업 목록에 있는 블록을 제거하고, 해당 블록의 나가는 상태를 계산한다. 나가는 상태가 변경되면, 그 블록의 후행 노드들을 다시 작업 목록에 추가한다. 이때, 효율성을 위해 한 블록은 작업 목록에 한 번만 존재하도록 한다.[1]

알고리즘은 초기화 과정에서 작업 목록에 블록을 추가하는 것으로 시작하며, 작업 목록이 비면 종료된다. 이 알고리즘은 변경된 블록만 처리하므로 불필요한 계산을 줄일 수 있다.[1]

4. 주요 데이터 흐름 분석 유형

데이터 흐름 분석의 주요 유형은 다음과 같다.


  • 도달 정의: 프로그램의 각 지점에 도달할 수 있는 정의(변수에 값을 할당하는 문장)의 집합을 계산한다. 이는 전파 상수 등에 활용된다.[1]
  • 생존 변수 분석: 각 지점에서 나중에 사용될 가능성이 있는 변수를 파악한다. 이는 데드 코드 제거에 사용된다.[1]
  • 가용 표현식 분석: 도달 정의 및 전파 상수 분석과 관련이 있다.
  • 상수 전파: 도달 정의와 전파 상수를 포함하는 개념이다.

4. 1. 도달 정의 분석 (Reaching Definitions Analysis)

도달 정의 분석은 프로그램의 각 지점에 대해, 거기에 도달할 가능성이 있는 정의의 집합을 계산한다.[1]

예시:

1: if b==4 then
2: a = 5;
3: else
4: a = 3;
5: endif
6:
7: if a < 4 then
8: ...



변수 "a"의 7행에서의 도달 정의는, 행 번호 집합 {2, 4}이다. 즉, 2행과 4행에서 정의된 `a`가 7행에 도달할 수 있다. 이는 전파 상수 등에 활용된다.[1]

4. 2. 생존 변수 분석 (Live Variable Analysis)

생존 변수 분석은 각 프로그램 지점에서 다음에 쓰이기 전에 잠재적으로 읽힐 가능성이 있는 변수를 계산한다. 이 결과는 데드 코드 제거에 사용되어, 나중에 사용되지 않는 변수에 값을 할당하는 코드를 제거하는 데 활용된다.[1]

블록의 들어오는 상태(in-state)는 블록 시작 시점에 살아있는 변수들의 집합이다. 나가는 상태(out-state)는 블록 끝에서 살아있는 변수들의 집합이며, 블록의 후속 블록들의 들어오는 상태(in-state)들의 합집합으로 계산된다. 구문의 전이 함수는 죽은 변수들을 만들면서 적용되고, 살아있는 변수들을 읽는 변수들을 만든다.[1]

초기 코드는 다음과 같다:

```

b1: a = 3;

b = 5;

d = 4;

x = 100;

if a > b then

b2: c = a + b;

d = 2;

b3: endif

c = 4;

return b * d + c;

```

이를 역방향으로 분석하면 다음과 같다:

```

// in: {}

b1: a = 3;

b = 5;

d = 4;

x = 100; //x는 나중에 사용되지 않으므로 out 집합 {a,b,d}에 포함되지 않음

if a > b then

// out: {a,b,d} //b1의 모든 후속자(b2: {a,b}, b3:{b,d})의 in-state 합집합

// in: {a,b}

b2: c = a + b;

d = 2;

// out: {b,d}

// in: {b,d}

b3: endif

c = 4;

return b * d + c;

// out:{}

```

b3의 들어오는 상태는 b와 d만을 포함하는데, 이는 c가 쓰여졌기 때문이다. b1의 나가는 상태는 b2와 b3의 들어오는 상태의 합집합이다. b2에서 c의 정의는 c가 구문 직후에 살아있지 않기 때문에 제거될 수 있다.[1]

데이터 흐름 방정식을 풀기 위해, 모든 들어오는 상태와 나가는 상태를 빈 집합으로 초기화한다. 작업 목록은 종료 지점(b3)을 삽입하여 초기화한다. 계산된 들어오는 상태가 이전과 다르므로, 선행 노드들인 b1과 b2가 삽입되고, 이 과정이 계속된다. 이 과정은 아래 표와 같이 요약된다.[1]

과정나가는 상태이전의 들어오는 상태새로운 들어오는 상태작업 목록
b3{}{}{b,d}(b1,b2)
b1{b,d}{}{}(b2)
b2{b,d}{}{a,b}(b1)
b1{a,b,d}{}{}()



b1은 b2 이전에 리스트에 들어가서 b1을 두 번 처리하게 되었다 (b1은 b2의 선행 노드로서 다시 들어간다). b1 이전에 b2를 삽입하면 더 빨리 완료할 수 있었다.[1]

빈 집합으로 초기화하는 것은 낙관적인 초기화이다. 즉, 모든 값들은 죽은 상태로 시작한다. 나가는 상태는 들어오는 상태보다 작을 수 있지만, 다음 반복을 꺼린다. 들어오는 상태가 빈 집합으로 시작되므로, 이후 반복에서만 커질 수 있다.[1]

4. 3. 가용 표현식 분석 (Available Expression Analysis)

도달 정의 및 전파 상수 분석과 관련이 있다.

4. 4. 상수 전파 (Constant Propagation)

상수 전파는 도달 정의와 전파 상수를 포함하는 개념이다.

5. 더 읽어보기


  • Cooper, Keith D.; Torczon, Linda. ''Engineering a Compiler''|쿠퍼, 키스 D.; 토존, 린다. ''컴파일러 공학''영어. Morgan Kaufmann. 2005.
  • Muchnick, Steven S. ''Advanced Compiler Design and Implementation''|무크닉, 스티븐 S. ''고급 컴파일러 설계 및 구현''영어. Morgan Kaufmann. 1997.
  • Hecht, Matthew S. ''Flow Analysis of Computer Programs''|헤흐트, 매튜 S. ''컴퓨터 프로그램의 흐름 분석''영어. Elsevier North-Holland Inc. 1977.
  • Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri. ''Data Flow Analysis: Theory and Practice''|케드커, 우다이 P.; 산얄, 아미타브; 카르카레, 바게시리. ''데이터 흐름 분석: 이론과 실제''영어. CRC Press (Taylor and Francis Group). 2009.
  • Flemming Nielson, Hanne Riis Nielson, Chris Hankin. ''Principles of Program Analysis''|플레밍 닐슨, 하네 리스 닐슨, 크리스 핸킨. ''프로그램 분석의 원리''영어. Springer. 2005.

참조

[1] 웹사이트 Static Single Assignment (with relevant examples) https://www.geeksfor[...] 2023-08-16
[2] 논문 A Unified Approach to Global Program Optimization http://portal.acm.or[...] 2006-11-20
[3] 저널 A Unified Approach to Global Program Optimization http://portal.acm.or[...] 2006-11-20
[4] 웹인용 Iterative data-flow analysis, revisited http://citeseerx.ist[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com