문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 프로그램 분석]] == 개요 == 큰 프로그램에 대해서 [[Anderson algorithm]]과 같은 경우에는 세제곱 복잡도로 인해서 성능이 매우 느려진다. Steensgaard 알고리즘은 정확도를 포기해서 거의 Linear-time에 프로그램 분석을 가능하도록 하는 알고리즘이다. 본 알고리즘은 Field-insensitive 알고리즘이며, 만약 [[Field sensitive]]하게 알고리즘을 만들면 이 알고리즘은 더이상 Linear-time에 분석할 수 없게 된다. linear time에 point to analysis를 하는 것이 가능하게 해야 하는데, 프로그램은 자연적으로 N개의 변수가 N개의 서로다른 변수를 가르킬 수 있음으로, N^2의 복잡도를 가진다. 과연 이문제를 어떻게 해결할 수 있을까? 이 해결책으로, Steensgaard algorithm은 q와 r에 대한 abstract location을 unification하는 방식으로 해결하였다. Inclusion방식의 엔더슨 알고리즘과는 다르게 Unification하기 때문에 거의 Linear하게 프로그램의 point to 분석을 할 수 있다. 예를 들어서 다음과 같은 프로그램이 있다고 해보자. P := &x r := &p q := y s := &q r := s 이 경우 Anerson방식은 r -> p -> x \> q -> y s / 와 같은 그래프를 그리지만, Steensgaard 알고리즘에서는, 현재 r이 p와 q를 동시에 가르킬 수 있기 때문에, p와 q를 Unification해서, r -> pq -> x s / \> y 와 같은 그래프를 그린다. 이 경우 pq가 x와 y를 또 동시에 가르키고 있기 떄문에, x와 y를 Unification해서 r -> pq -> xy s / 와 같은 최종적은 그래프가 그려진다. Precision은 사라졌지만, 최종적으로 Linear한 메모리 사용량과 Linear한 계산량을 가지게 된다. == 알고리즘 == 포인터는 다음 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가 가르키는 Location에 대한 Abstract location을 말한다. * address-of: <math>join(*A, B)</math> * copy: <math>join(*A, *B)</math> * assign: <math>join(**A, *B)</math> * dereference: <math>join(*A, **B)</math> == 복잡도 == 프로그램은 처음 부터 끝까지 한번 훝는 것으로 알고리즘이 구현되기 때문에, 우선 N의 복잡도가 더해진다. Find operation은 Union data find로 구현되는데, O(a(n))이라는 시간 복잡도를 가진다. 따라서 최종적으로 O(n * a(n))인데, 보통 Union data find-join알고리즘은 대다수의 경우 거의 상수의 값이 난온다. 따라서 거의 Linear time에 이 알고리즘을 돌릴 수 있다. == 같이 보기 == # [[Anderson algorithm]] # [[Field sensitive algorithm]] == 참고 == # https://web.eece.maine.edu/~vweaver/projects/steensgaard/ # http://www.cs.cmu.edu/~clegoues/courses/15-819O-16sp/notes/notes07-pointers.pdf Steensgaard's algorithm 문서로 돌아갑니다.