Anderson algorithm 문서 원본 보기

[[분류: 프로그램 분석]]

== 개요 ==
앤덜슨 알고리즘은 [[프로그램 분석]]에서 기본이 되는 2가지 알고리즘 중에 하나로, 제일 정확하지만, 제일 오래걸리는 특징을 가진다. [[Context-insensitive]] 알고리즘 이며, [[Flow-insensitive]]분석 방법이다.

== 알고리즘 ==
포인터는 다음 4가지의 상태에서 연산된다.
* address of: A = &B or (A = malloc(size), A = new ...)
* copy: A = B
* assign: *A = B
* dereference: A = *B

각각의 상태는 다음과 같은 집합에 의해서 표현될 수 있다. 이때 A, B는 변수 A, B가 가르키는 주소들에 대한 집합이며, <math>l_x</math>는 X라는 변수의 위치 (즉 포인터)를 나타낸다. * 오퍼레이션은 집합 기호에서는 원래 없는 기호인데, 여기서는 *A가 가르키는 모든 변수들을 말한다.
* address-of: <math>l_b \in A</math>
* copy: <math>A \supseteq B</math>
* assign: <math> *A \supseteq B</math>
* dereference: <math> A \supseteq *B</math>

결과적으로 다음과 같이 나타난다.
* address of : A = {A, <math>l_b</math>}
* copy: A = {A, B}
* assign: var1 = {var1, <math>l_b</math>}, var2 = {var2, <math>l_b</math>}, .., var_x is #x element of A.
* dereference: A = {A, var1, var2, ...}, var_x is #x element of B

결국, 각 set A, B는 내부적으로 변수 집합을 가지게 되고, 각 변수 집합은 A라는 포인터 변수가 가르키는 오브젝트의 집합이 된다.

== 복잡도 ==
N개의 변수가 프로그램에 있다고 해보자. 이경우 각 변수 집합은 최대 N개의 다른 변수집합을 가르킬 수 있음으로, 최종 메모리의 사용량은 최대 O(<math>n^2</math>)이 된다.

dereference상황에서, 변수 <math>X\in N</math>는 dereference operation을 위해서 최대 O(<math>n^2</math>)의 operation을 각각의 원소에 대해서 수행해야 한다. 따라서 최종적으로는 O(<math>n^2</math>)의 계산 복잡도를 가진다.

쉽게 요약하자면, 엔더슨 알고리즘은 각 변수의 대입을 집합을 통해서 추적한다. 모든 변수가 서로 다른 모든 변수를 참고할 가능성이 있는 경우가 최대한의 복잡도의 상황이며, 이경우 각 집합은 N즉 최종적으로 N*N의 크기를 먹는다. 만약 변수 하나를 Dereference하게 된다면, 상태를 업데이트 하기 위해서 N*N개의 변수 집합에 대한 dereference operation이 필요하다. 따라서 최종적으로 N*N*N의 최대 계산 복잡도를 가진다.

== 같이 보기 ==
# [[Steensgaard's algorithm]] 
# [[Field sensitive algorithm]]
# [[Context sensitive algorithm]]