개요

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

같이 보기

  1. Anderson algorithm
  2. Field sensitive algorithm

참고

  1. https://web.eece.maine.edu/~vweaver/projects/steensgaard/
  2. http://www.cs.cmu.edu/~clegoues/courses/15-819O-16sp/notes/notes07-pointers.pdf