데이터 흐름 분석
데이터 흐름 분석(Data-flow analysis)은 컴퓨터 프로그램에서 다양한 지점에서 계산된 가능한 값들의 집합에 대한 정보를 모으는 기법이다. 프로그램의 제어 흐름 그래프(CFG)는 프로그램의 이러한 값들에서 변수에 저장되기 위해서는 어떤 값이 전파돼야 하는지를 결정하는데 사용된다. 모아진 정보는 종종 컴파일러가 프로그램을 최적화할 때 사용된다. 데이터 흐름 분석의 고전적인 예로 도달 정의(reaching definition)가 있다.
프로그램의 데이터 흐름 분석을 수행하는 간단한 방법은 제어 흐름 그래프의 각 노드에 데이터 흐름 방정식을 세우고 전체 시스템이 안정될 때 까지 각 노드의 입력에서 결과물을 반복적으로 계산하여 푸는 것이다. 이 일반적인 접근법은 개리 킬달에 의해 개발되었다.
이것은 프로그램에서 변수들이 사용되고 정의되는 방식에 관한 정보를 모으는 과정이다. 데이터 흐름 분석은 과정의 각 포인트에서 특정한 정보를 얻으려고 시도한다. 보통, 기본 블록의 경계에서 이 정보를 얻는것은 충분하다. 기본 블록에서 포인트의 정보를 계산하는 것은 쉽기 때문이다. 정방향 흐름 분석에서, 블록의 종료 상태는 블록의 전체 상태 함수이다. 이 함수는 블록에서 선언의 효과들의 구성 요소이다. 블록의 엔트리 상태는 이것의 전임자의 종료 상태 함수이다. 이것은 데이터 흐름 방정식을 만들어낸다.
각 블록 b에서:
여기서, formula_3 은 블록 b의 전달 함수이다. 이것은 엔트리 상태 formula_4에 적용되며, 종료 상태 formula_5을 만들어낸다. 결합 연산 formula_6은 b의 엔트리 상태를 만들어내면서, b의 전임자 formula_7 의 종료 상태를 결합한다.
이 방정식의 집합을 풀고난 후에, 블록의 엔트리 그리고/또는 종료 상태는 블록 경계에서 프로그램의 속성을 끌어내기 위해 사용된다. 각 선언의 전달 함수는 각각 기본 블록 내에서 한 지점의 정보를 얻기위해 적용될 수 있다.
데이터 흐름 분석의 각 특정한 타입은 자신만의 특정한 전달 함수와 결합 연산을 갖는다. 어떤 데이터 흐름 프로그램은 역방향 흐름 분석을 필요로 한다. 이것은 전달 함수가 엔트리 상태를 산출하면서 종료 상태에 적용되며, 결합 연산이 종료 상태를 산출하기 위해 계승자의 엔트리 상태에 적용된다는 사실을 제외하고는 같은 계획을 따른다.
엔트리 포인트는 (정방향 흐름에서) 중요한 역할을 수행한다. 이것은 전임자가 없기 때문에 엔트리 상태가 분석의 시작점에 잘 정의되어 있다. 예를 들면, 알려진 값이 들어있는 지역 변수들의 집합은 비어있다. 만약 제어 흐름 그래프가 사이클을 갖는다면, 방정식을 푸는 것은 간단하다. 제어 흐름 그래프는 위상적으로 정렬될 수 있다. 이 정렬 순서로 실행되면서, 엔트리 상태는 각 블록의 시작에서 계산될 수 있다. 블록의 모든 전임자들이 이미 진행되어서, 그들의 종료 상태가 사용 가능하기 때문이다. 만약 제어 흐름 그래프가 사이클을 포함하지 않는다면, 더 발전된 알고리즘이 필요하다.
데이터 흐름 방정식을 푸는 가장 흔한 방법은 반복 알고리즘을 사용하는 것이다. 이것은 각 블록의 내부 상태의 근사치로 시작한다. 외부 상태는 내부 상태의 전달 함수를 적용함으로써 계산된다. 이것들에서, 내부 상태는 결합 연산을 적용함으로써 갱신된다. 다음 두 단계들은 고정점(fixpoint)이라고 불리는 곳에 도달할 때까지 반복된다. 내부 상태(그리고 결과인 외부 상태)에서 상황은 바뀌지 않는다.
데이터 흐름 방정식을 푸는 기본 알고리즘은 라운드-로빈 반복 알고리즘이다.
사용되기 위해서는, 반복적인 접근은 실제로 고정점에 도달해야 한다. 이것은 상태의 가치유형(value domain)과 전달 함수 그리고 결합 연산의 조합에 대한 통제를 부과함으로써 보장될 수 있다.
가치유형은 유한한 높이를 가진 (finite height) 부분 순서여야 한다. (즉, 유한한 오름 체인 formula_8 < formula_9 < ...이 없다.) 전달 함수와 결합 연산의 조합은 부분 순서에 대하여 단조함수여야 한다. 단조성은 유한 높이가 무기한으로 커질 수 없다는 것을 보장하면서, 각 반복 시에 값이 같은 상태로 유지되거나 더 커질 것이라는 것을 보장한다. 그래서 우리는 궁극적으로 모든 x에 대해서 고정점인 T(x) = x라는 상황에 도달하게 된다.
전임자의 외부 상태가 바뀌지 않는다면 블록의 내부 상태가 바뀌지 않을 것이라는 것을 알림으로써 알고리즘을 개선시키는 것은 쉬운 일이다. 그러므로 우리는 work list를 도입한다. 이것은 아직 처리될 필요가 있는 블록들의 목록이다. 블록의 외부 상태가 바뀔 때마다 블록은 목록에서 제거된다. 이것의 외부 상태는 계산된다. 만약 외부 상태가 바뀌면, 블록의 계승자가 work list에 추가된다. 효율성을 위하여, 블록은 한 번 이상 work list에 있으면 안된다.
알고리즘은 work list에서 블록을 생성하는 정보를 넣음으로써 시작된다. 이것은 work list가 비면 종료된다.
데이터 흐름 방정식을 반복적으로 푸는 것의 효율성은 지역 노드가 방문되는 순서에 영향을 받았다. 게다가, 이것은 데이터 흐름 방정식이 정방향 데이터 흐름 분석에 사용되는지 역방향 데이터 흐름 분석에 사용되는지에 의존한다. 직관적으로, 정방향 흐름 문제에서, 이것은 블록의 전임자들이 블록 이전에 진행되었다면 더 빠르며, 이후 반복은 최신 정보를 사용한다. 루프가 없는 경우, 각 블록을 단 한번만 진행하면서 정확한 외부 상태들이 계산되는 방식으로 블록을 정렬하는 것은 가능하다.
아래는, 데이터 흐름 방정식을 푸는 몇 가지 반복 순서이다. (CFG의 반복 순서에 관련된 것은 트리의 트리 순회이다.).
내부 상태들의 초기 값은 정확한 결과를 얻기 위해 중요하다. 만약 결과들이 컴파일러 최적화에 사용된다면, 이것들은 보수적인 정보를 제공해야 한다. 즉, 정보를 적용할 때 프로그램은 의미를 바꿔서는 안된다. 고정점 알고리즘의 반복은 최대값 요소의 방향에서 값을 갖는다.
아래는 데이터 흐름 분석으로 계산된는 컴퓨터 프로그램들의 속성들의 예시들이다. 데이터 흐름 분석으로 계산되는 속성들은 일반적으로 실제 속성들의 근사치라는 것을 기억하자. 이것은 데이터 흐름 분석이 프로그램의 전확한 제어 흐름 시뮬레이션 없이 CFG의 구문론적 구조에서 동작하기 때문이다. 그러나 실생활에 유용하기 위해서, 데이터 흐름 분석 알고리즘은 일반적으로 실제 프로그램 속성들의 근사치를 계산하도록 설계되었다.
도달 정의 분석은 각 프로그램 포인트에서 잠재적으로 이 프로그램의 포인트에 닿을 수 있는 정의들의 집합을 계산한다.
라이브 변수 분석은 각 프로그램 지점에서 다음 쓰기 갱신 전에, 잠재적으로 추후에 읽어지는 변수를 계산한다. 결과는 일반적으로 불필요한 코드 제거에서 값이 나중에 사용되지 않는 변수로 정해진 선언을 제거하기 위해 사용된다.
블록의 외부 상태는 블록의 끝에 살아 있는 변수들의 집합이다. 이것의 내부 상태는 시작 시에 살아 있는 변수들의 집합이다. 외부 상태는 블록 계승자의 내부 상태의 연합이다. 선언의 전달 함수는 dead 변수들을 만들면서 적용된다. 그리고 살아있는 것을 읽는 변수들을 만든다.
초기 코드:
역방향 코드:
c가 써졌기 때문에, b3의 내부 상태는 단지 b와 d를 포함한다. b1의 외부 상태는 b2와 b3의 내부 상태들의 연합이다. c가 선언 직후에 살아있지 않기 때문에 b2에서 c의 정의는 제거될 수 있다.
데이터 흐름 방정식을 푸는 것은 모든 내부 상태와 외부 상태를 빈 집합으로 초기화하면서 시작된다. work list는 work list에서 종료 지점(b3)을 삽입함으로써 초기화된다. 이것의 계산된 내부 상태는 이전의 것과 다르며, 전임자 b1과 b2는 삽입되고, 진행은 계속된다. 과정은 아래의 테이블로 요약된다.
b1이 b1을 두 번 진행하게 강요된 b2 이전에 리스트에 들어간다는 것을 기억하자. (b1은 b2의 전임자로써 다시 들어간다.) b1 이전에 b2를 삽입하는 것은 이전 완료에서 허락된다.
빈 집합으로 초기화하는 것은 낙관적인 초기화이다. 모든 값들은 죽은 상태로 시작된다. 외부 상태들은 비록 내부 상태들보다 적다 하더라도 다음으로의 반복을 꺼린다는 것을 기억하자. 내부 상태가 빈 집합으로 시작되기 때문에, 추후의 반복에서만 커질 수 있다.
데이터 흐름 분석은 본질적으로 흐름에 민감하다. 그리고 비록 경로에 민감한 분석을 산출하는 데이터 흐름 방정식을 정의할 수도 있지만 일반적으로 경로에 민감하지 않다.