라이브 변수 분석

컴파일러에서 라이브 변수 분석(또는 단순히 라이브 분석)은 프로그램의 각 포인트에서 라이브 변수를 계산하는 전형적인 데이터 흐름 분석입니다.변수는 미래에 필요할 수 있는 값을 보유하고 있는 경우, 또는 다음 번에 변수를 쓰기 전에 해당 값을 읽을 수 있는 경우, 어느 시점에서 활성 상태입니다.

예

다음 프로그램을 고려하십시오.

b = 3 c = 5 a = f(b * c)

행 2와 행 3 사이의 활성 변수 집합은 {}입니다.b,c}은(는) 둘 다 3행의 곱셈에 사용되기 때문입니다.그러나 1행 뒤의 활성 변수 집합은 {}에 불과합니다.b변수 이후 },c는 나중에 2행으로 갱신됩니다.변수 값a이 코드에서는 사용되지 않습니다.

에의 할당에 주의해 주세요.a로서 제거될지도 모른다a나중에 사용되지 않지만 3행 모두를 삭제할 수 있는 충분한 정보가 없습니다.f부작용이 있을 수 있다(부작용)b * c아마도).

데이터 흐름 방정식의 표현

라이브스 분석은 "백워드 메이" 분석입니다.분석은 역순으로 수행되며 데이터 흐름 합류 연산자는 집합 결합입니다.즉, 특정 개수의 논리 분기가 있는 함수에 라이브스 분석을 적용할 경우, 분석은 처음부터 수행되며(따라서 "후진"), 함수 내에서 전진하는 분기가 잠재적으로 다음과 같은 경우(따라서 "후진") 변수는 라이브로 간주됩니다.may")에는 변수의 현재 값이 필요합니다.이는 앞으로 나아가는 모든 브랜치에 대해 이 조건을 적용하는 "백워드 필수" 분석과는 대조적입니다.

라이브 변수 분석에서 특정 기본 블록 및 출구 블록 f에 사용되는 데이터 흐름 방정식은 다음과 같습니다.

$]{$$$$EN}}$ [$s$ : 할당 전 에서 사용되는 변수 세트.

$]{$$$ILL$}}$ [$s$ : 에서 값이 할당되어 있는 변수 세트(많은^{[clarification needed]} 책에서 KILL은 사용하기 전에 s에서 값이 할당되어 있는 변수 세트로도 정의되지만 데이터 흐름 방정식의 솔루션은 변경되지 않습니다).

$디스플레이 스타일{displaystyle\mbox\}라이브}_{in}[s]=mbox{G}EN}}[s]\cup({\mbox{})라이브}_{out}[s]-{\mbox{K}ILL}}(s)}},$

$디스플레이 스타일{displaystyle\mbox\}라이브}_{out}[최종]=({emptyset}})$

$디스플레이 스타일{displaystyle\mbox\}라이브}}_{out}[s]=\bigcup_{p\in succ[s]}{\mbox{라이브}_{in}[p]}$

${\displaystyle\mbox{G}EN}} [d:y\left 화살표 f(x_{1},\cdots,x_{n})]=\{x_{1}...x_{n}\}$

${\displaystyle\mbox{K}ILL}} [d:y\left 화살표 f(x_{1},\cdots,x_{n}]=\{y\}}$

블록의 in-state는 블록의 시작 부분에서 활성 상태인 변수 집합입니다.out-state는 out-state의 끝에 존재하는 변수 집합입니다.out-state는 블록의 후계자 in-state의 결합입니다.스테이트먼트의 전송 함수는 데드(dead)로 기입된 변수를 라이브(live)로 함으로써 적용됩니다.

두 번째 예

// 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가 삽입되고 프로세스가 계속됩니다.진행 상황은 아래 표에 요약되어 있습니다.

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

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

레퍼런스

Aho, Alfred; Lam, Monica; Sethi, Ravi; Ullman, Jeffrey (2007). Compilers: Principles, Techniques, and Tools (2 ed.). p. 608.