데이터 흐름 분석

데이터 흐름 분석은 컴퓨터 프로그램의 다양한 지점에서 계산될 수 있는 값 집합에 대한 정보를 수집하는 기술입니다.프로그램의 제어 흐름 그래프(CFG)는 변수에 할당된 특정 값이 전파될 수 있는 프로그램 부분을 결정하기 위해 사용됩니다.수집된 정보는 컴파일러가 프로그램을 최적화할 때 자주 사용됩니다.데이터 흐름 분석의 일반적인 예는 정의에 도달하는 것입니다.

프로그램의 데이터 흐름 분석을 실행하는 간단한 방법은 제어 흐름 그래프의 각 노드에 대해 데이터 흐름 방정식을 설정하고 시스템 전체가 안정될 때까지, 즉 고정점에 도달할 때까지 각 노드에서 입력으로부터의 출력을 반복 계산함으로써 그것들을 푸는 것이다.킬달의 방법이라고도 알려진 이 일반적인 접근법은 해군 대학원 ^[1]^[2]^[3]^[4]교수 시절 게리 킬달에 의해 개발되었다.

기본 원칙

데이터 흐름 분석은 프로그램에서 변수를 정의하고 사용하는 방법에 대한 정보를 수집하는 프로세스입니다.프로시저의 각 포인트에서 특정 정보를 취득하려고 합니다.일반적으로 기본 블록의 경계에서 이 정보를 얻으면 충분합니다. 기본 블록의 각 지점에서 정보를 쉽게 계산할 수 있기 때문입니다.순방향 흐름 분석에서 블록의 종료 상태는 블록의 진입 상태의 함수입니다.이 함수는 블록에 있는 문장의 효과의 구성입니다.블록의 입력 상태는 이전 블록의 종료 상태의 함수입니다.이를 통해 일련의 데이터 흐름 방정식이 생성됩니다.

각 블록 b:

\displaystyle out_{b}=trans_{b}(in_{b})

{displaystyle in_{b}=pred_{b}(out_{p})}

여기서 $trans_{b}$ a $trans_{b}$ $trans_{b}$ b { $display$ style $trans$ _ { $b$ }는 $trans_b$ $블록$ b { $display style$ b $b$ }의 전송 함수입니다.이 기능은 엔트리 $in_{b}$ $in_{b}$ b({ $displaystyle in_{b$ 에서 동작하며 종료 $out_{b}$ 는 $out_{b}$ $out_{b}$ b({ $display out_{b$ 입니다. $join$ $조작$ $\displaystyle$ join은 b $join$ $displaystyle$ 의 $p\in pred_{b}$ p $p\in pred_{b}$ p $p\in pred_{b}$ $p\in pred_{b}$ \ $display style$ p\ $in pred$ _ { $b}$ 의 $p \in pred_b$ 종료 상태를 조합하여 b $\displaystyle$ 엔트리 상태를 생성합니다.

이 방정식 세트를 푼 후 블록 경계에서 프로그램의 특성을 도출하기 위해 블록의 엔트리 및/또는 출구 상태를 사용할 수 있다.각 문장의 전송 기능을 별도로 적용하여 기본 블록 내부의 한 지점에서 정보를 얻을 수 있습니다.

데이터 흐름 분석의 각 유형에는 고유한 전송 함수와 결합 연산이 있습니다.일부 데이터 흐름 문제에서는 역류 분석이 필요합니다.이는 전송 함수가 엔트리 스테이트를 생성하는 종료 스테이트에 적용되고 가입 조작이 후계자의 엔트리 스테이트에 작용하여 종료 스테이트를 생성하는 것을 제외하고 동일한 플랜에 따릅니다.

진입점(전진 흐름)은 중요한 역할을 합니다. 즉, 선행 항목이 없기 때문에 분석 시작 시 진입 상태가 잘 정의됩니다.예를 들어, 값이 알려진 로컬 변수 집합이 비어 있습니다.제어 흐름 그래프에 사이클이 포함되지 않은 경우(순서에 명시적 또는 암묵적 루프가 없는 경우) 방정식을 푸는 것은 간단합니다.제어 흐름 그래프는 토폴로지적으로 정렬할 수 있습니다.이러한 순서로 실행되면 각 블록의 시작 부분에서 엔트리 상태를 계산할 수 있습니다.이는 해당 블록의 모든 선행 블록이 이미 처리되었기 때문입니다.따라서 해당 블록의 종료 상태를 사용할 수 있기 때문입니다.제어 흐름 그래프에 사이클이 포함되어 있는 경우 보다 고도의 알고리즘이 필요합니다.

반복 알고리즘

데이터 흐름 방정식을 푸는 가장 일반적인 방법은 반복 알고리즘을 사용하는 것입니다.각 블록의 상태 근사치부터 시작합니다.그런 다음 in-state에 전송 함수를 적용하여 out-state가 계산됩니다.이들로부터, 가입 조작을 적용하면, in-state가 갱신됩니다.후자의 두 단계는 소위 고정점에 도달할 때까지 반복됩니다. 즉, 상태 내(및 결과적으로 상태 외)가 변경되지 않는 상황입니다.

데이터 흐름 방정식을 풀기 위한 기본 알고리즘은 라운드 로빈 반복 알고리즘입니다.

i ← 1 ~ N의 경우

노드 i 초기화

(세트는 아직 변경 중)

i ← 1 ~ N의 경우

노드 i에서 세트 다시 계산

컨버전스

반복적인 접근방식은 실제로 고정점에 도달해야 사용할 수 있습니다.이는 상태의 값 도메인, 전송 함수 및 결합 연산의 조합에 제약을 가함으로써 보증할 수 있습니다.

값 도메인은 높이가 유한한 부분 순서여야 합니다(즉, 무한 상승 $x_{1}$ x $(\$ }) $x_{1}$ < $x_{2}$ $(\$ }} $x_{2}$ <...).전송 함수와 결합 연산의 조합은 이 부분 순서와 관련하여 단조로워야 합니다.단조로움으로 인해 각 반복에서 값이 같거나 커지지만 유한 높이는 무한히 커질 수 없습니다.따라서 우리는 궁극적으로 고정점인 모든 x에 대해 T(x) = x인 상황에 도달할 것이다.

검사 목록 접근법

블록의 상태가 이전 버전의 아웃 상태가 변경되지 않으면 블록의 인 상태가 변경되지 않는다는 것을 알게 되면 위의 알고리즘을 개선할 수 있습니다.따라서 아직 처리해야 할 블록 목록인 작업 목록을 소개합니다.블록의 아웃 상태가 변경될 때마다 후속 블록이 작업 목록에 추가됩니다.각 반복에서 블록은 검사 목록에서 제거됩니다.아웃스테이트가 계산됩니다.out-state가 변경되면 블록의 후계자가 작업 목록에 추가됩니다.효율성을 위해 블록은 작업 목록에 두 번 이상 포함되지 않아야 합니다.

알고리즘은 정보 생성 블록을 작업 목록에 넣는 것으로 시작됩니다.검사 목록이 비어 있으면 종료됩니다.

주문

데이터 흐름 방정식을 반복적으로 푸는 효율은 로컬 노드가 ^[5]방문하는 순서에 따라 영향을 받습니다.또한 CFG를 통한 데이터 흐름 분석에 데이터 흐름 방정식이 사용되는지 또는 역방향 데이터 흐름 분석에 사용되는지에 따라 달라집니다.직관적으로, 순방향 흐름 문제에서, 블록의 모든 이전이 블록 자체보다 먼저 처리되는 것이 가장 빠를 것입니다. 그 이후 반복은 최신 정보를 사용합니다.루프가 없는 경우 각 블록을 한 번만 처리함으로써 올바른 아웃 상태가 계산되도록 블록을 정렬할 수 있습니다.

다음에서는 데이터 흐름 방정식을 풀기 위한 몇 가지 반복 순서가 논의된다(CFG의 반복 순서와 관련된 개념은 트리의 트리 트래버설).

랜덤 순서 - 이 반복 순서는 데이터 흐름 방정식이 순방향 데이터 흐름 문제를 해결하는지 또는 역방향 데이터 흐름 문제를 해결하는지 인식하지 않습니다.따라서 특수한 반복 순서에 비해 성능이 상대적으로 떨어집니다.
포스트오더: 이것은 역방향 데이터 흐름 문제에 대한 일반적인 반복 순서입니다.포스트오더 반복에서는 모든 후속 노드를 방문한 후에 노드가 방문됩니다.일반적으로 사후 순서 반복은 깊이 우선 전략으로 구현됩니다.
역순서 - 전송 데이터 흐름 문제에 대한 일반적인 반복 순서입니다.역순서 반복에서는 백엣지에 의해 후속 노드에 도달한 경우를 제외하고 후속 노드가 방문되기 전에 노드가 방문됩니다.(역순서는 예약순서와 동일하지 않습니다).

초기화

정확하고 정확한 결과를 얻으려면 in-state의 초기값이 중요합니다.결과가 컴파일러 최적화에 사용되는 경우 보수적인 정보를 제공해야 합니다.즉, 정보를 적용할 때 프로그램은 의미론을 변경하지 않아야 합니다.고정점 알고리즘의 반복은 최대 요소의 방향으로 값을 가져옵니다.따라서 최대 요소로 모든 블록을 초기화하는 것은 유용하지 않습니다.최소 1개의 블록이 최대값보다 작은 상태에서 시작됩니다.자세한 내용은 데이터 흐름 문제에 따라 달라집니다.최소 요소가 완전히 보수적인 정보를 나타내는 경우 데이터 흐름 반복 중에도 결과를 안전하게 사용할 수 있습니다.가장 정확한 정보를 나타내는 경우 결과를 적용하기 전에 수정점에 도달해야 합니다.

예

다음은 데이터 흐름 분석을 통해 계산 가능한 컴퓨터 프로그램의 특성 예입니다.데이터 흐름 분석에 의해 계산된 속성은 일반적으로 실제 속성의 근사치입니다.이는 프로그램의 정확한 제어 흐름을 시뮬레이션하지 않고 CFG의 구문 구조에 대해 데이터 흐름 분석이 실행되기 때문입니다.그러나 실제로 여전히 유용하기 위해 데이터 흐름 분석 알고리즘은 일반적으로 실제 프로그램 속성의 각각 상위 하위 근사치를 계산하도록 설계되어 있습니다.

전진 분석

도달 정의 분석은 각 프로그램 포인트에 대해 잠재적으로 이 프로그램 포인트에 도달할 수 있는 정의 세트를 계산합니다.

b == 4이면a = 5;또 다른a = 3;엔디프  a가 4 미만일 경우...

변수의 도달 정의a7행은 할당 세트입니다.a = 52행에서a = 34번 줄에.

역분석

실시간 변수 분석은 각 프로그램 지점에 대해 다음 쓰기 업데이트 전에 잠재적으로 읽을 수 있는 변수를 계산합니다.결과는 일반적으로 데드 코드 제거에서 나중에 사용되지 않는 값을 가진 변수에 할당되는 문을 제거하기 위해 사용됩니다.

블록의 in-state는 블록 시작 시 활성 상태인 변수 세트입니다.전송 함수가 적용되어 실제 포함된 값이 계산되기 전에 처음에는 블록에 활성(포함)된 모든 변수가 포함됩니다.스테이트먼트의 전송 함수는 이 블록 내에 기술되어 있는 변수를 삭제함으로써 적용됩니다(실시간 변수 집합에서 해당 변수를 삭제합니다.블록의 Out-state는 블록의 끝에 존재하는 변수 집합으로, 블록의 후계자 in-state의 합계에 의해 계산됩니다.

초기 코드:

b1: a = 3; b = 5; d = 4; x = 100; a > b이면 b2: c = a + b; d = 2; b3: endif c = 4; 반환 b * d + c;

역방향 분석:

// in: {} b1: a = 3; b = 5; d = 4; x = 100; //x가 나중에 사용되지 않으므로 a > b이면 출력 집합 {a,b,d}에 포함되지 않습니다. // b1 => b2: {a,b} 및 b3: {b}의 모든 후계자 결합이(in) {a,b}에 있습니다.////d}에 있습니다.{}

b3의 in-state에는 c가 기입되어 있기 때문에 b와 d만 포함됩니다.b1의 Out 상태는 in-state b2와 b3의 결합입니다.b2의 c 정의는 삭제할 수 있습니다.이는 c가 스테이트먼트 직후에는 활성화되지 않기 때문입니다.

데이터 흐름 방정식을 해결하려면 모든 인스테이트 및 아웃스테이트를 빈 세트로 초기화해야 합니다.작업 목록은 작업 목록에 종료 지점(b3)을 삽입하여 초기화됩니다(역방향 흐름의 경우 일반).계산된 in-state가 이전 것과 다르기 때문에 이전 b1과 b2가 삽입되고 프로세스가 계속됩니다.진행 상황은 아래 표에 요약되어 있습니다.

처리.	아웃스테이트	낡은 주의	새로운 주의	작업 목록
b3	{}	{}	{b,d}	(b1, b2)
b1	{b,d}	{}	{}	(b2)
b2	{b,d}	{}	{a,b}	(b1)
b1	{a,b,d}	{}	{}	()

b1은 b2보다 먼저 리스트에 입력되어 b1을 2회 강제 처리(b1은 b2의 이전 버전으로서 재입력)한 것에 주의해 주세요.b1보다 먼저 b2를 삽입하면 더 빨리 완료될 수 있습니다.

빈 집합을 사용하여 초기화하는 것은 낙관적인 초기화입니다. 모든 변수는 비활성 상태로 시작됩니다.out-state는 in-state보다 작을 수 있지만 out-state는 어떤 반복에서 다른 반복으로 축소할 수 없습니다.이것은 첫 번째 반복 후에 아웃스테이트는 인스테이트의 변경에 의해서만 변경된다는 사실에서 알 수 있습니다.in-state는 빈 세트로 시작되므로 추가 반복에서만 확장할 수 있습니다.

기타 접근법

2002년에 Markus Mohnen은 프로그램의 추상적 해석에 의존하여 프로그램 카운터 세트를 유지하는 대신 데이터 흐름 ^[6]그래프의 명시적인 구성을 필요로 하지 않는 새로운 데이터 흐름 분석 방법을 설명했습니다.각 조건부 브랜치에서는 두 타깃이 작업 세트에 추가됩니다.세트에 추가됩니다.각 경로는 가능한 한 많은 명령(프로그램이 종료될 때까지 또는 변경 없이 루프될 때까지)을 수행한 후 세트에서 제거되고 다음 프로그램 카운터가 검색됩니다.

제어 흐름 분석과 데이터 흐름 분석의 조합은 시스템의 기능(예: 특징, 요건 또는 사용 사례)^[7]을 구현하는 응집력 있는 소스 코드 영역을 식별하는 데 유용하고 상호 보완적인 것으로 나타났습니다.

특수한 종류의 문제

데이터 흐름 문제에는 효율적이고 일반적인 해결 방법이 있는 다양한 특수 클래스가 있습니다.

비트 벡터 문제

위의 예는 데이터 흐름 값이 도달 정의 세트(프로그램의 정의 위치에 비트 사용) 또는 활성 변수 세트인 문제입니다.이러한 세트는 비트 벡터로 효율적으로 나타낼 수 있습니다.각 비트는 특정 요소의 세트멤버십을 나타냅니다.이 표현을 사용하면 결합 및 전송 함수를 비트 논리 연산으로 구현할 수 있습니다.조인 연산은 일반적으로 유니언 또는 교차로이며 비트 논리 또는 논리 및 논리 및 로지에 의해 구현됩니다.각 블록의 전송 함수는 이른바 gen 및 kill 세트로 분해할 수 있습니다.

예를 들어 라이브 변수 분석에서는 결합 연산은 union입니다.kill set은 블록에 기록되는 변수 집합이며 gen set은 먼저 기록되지 않고 읽히는 변수 집합입니다.데이터 흐름 방정식은

\displaystyle out_{b}=\bigcup_{s\in succ_{b}in_{s}

{displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}

논리 연산에서는 다음과 같이 읽힙니다.

out(b) = succ(b) out(b) = out(b) 또는 in(s) = (kill(b)이 아닌 out(b) 또는 gen(b)에 대해 0

비트 벡터로 나타낼 수 있는 데이터 흐름 값 세트가 있는 데이터 흐름 문제는 비트 벡터 문제, gen-kill 문제 또는 로컬에서 분리할 수 있는 ^[8]문제로 불립니다.이러한 문제에는 일반적인 다항식 시간 ^[9]솔루션이 있습니다.

위의 정의에 도달하는 문제 및 라이브 변수 문제와 더불어 비트벡터 문제의 ^[9]예로서 다음 문제가 있습니다.

IFDS 문제

절차 간, 유한, 분포, 부분 집합 문제 또는 IFDS 문제는 일반적인 다항식 시간 솔루션의 ^[8]^[10]또 다른 종류의 문제입니다.이러한 문제에 대한 해결책은 상황에 따라 달라지는 데이터 흐름 분석을 제공합니다.

자주 사용되는 프로그래밍 언어에 대한 IFDS 기반 데이터 흐름 분석의 구현이 몇 가지 있습니다. 예를 들어 Java 분석을^[11] 위한 Sult 및 WALA^[12] 프레임워크입니다.

모든 비트벡터의 문제도 IFDS의 문제이지만 비트벡터의 문제가 아닌 중요한 IFDS 문제가 몇 가지 있습니다.실제 변수나 초기화되지 않은 변수 등이 있습니다.

감도

데이터 흐름 분석은 본질적으로 흐름에 민감합니다.데이터 흐름 분석은 일반적으로 경로에 민감하지 않지만 경로에 민감한 분석을 생성하는 데이터 흐름 방정식을 정의할 수 있습니다.

흐름에 민감한 분석에서는 프로그램 내 문장의 순서를 고려합니다.예를 들어, 흐름 감응형 포인터 에일리어스 분석에서는 "변수 x와 y가 같은 위치를 참조할 수 있다"고 판별할 수 있으며, 흐름 감응형 분석에서는 "문 20 이후 변수 x와 y가 같은 위치를 참조할 수 있다"고 판별할 수 있습니다.
경로 민감 분석은 조건부 분기 명령에 따라 술어에 의존하는 다른 분석 정보를 계산한다.예를 들어 브랜치에 조건이 포함되어 있는 경우x>0그 후 폴스루 경로에서 분석은 다음과 같이 가정합니다.x<=0그리고 나뭇가지 목표물에서는 정말로x>0쥔다.
컨텍스트 의존 분석은 함수 호출의 타깃을 분석할 때 호출 컨텍스트를 고려하는 프로시저 간 분석입니다.특히 컨텍스트 정보를 사용하면 원래 콜사이트로 돌아갈 수 있지만, 이 정보가 없으면 분석 정보가 모든 가능한 콜사이트로 전파되어 정밀도가 저하될 가능성이 있습니다.