개요
큰 프로그램에 대해서 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에 이 알고리즘을 돌릴 수 있다.