Ahn9807: /* 개요 */

2023-11-10T05:13:13Z

개요

← 이전 판		2023년 11월 10일 (금) 05:13 판
24번째 줄:		24번째 줄:
	r -> pq -> xy		r -> pq -> xy
	s /		s /
	와 같은 ~~최종적은~~ 그래프가 그려진다. Precision은 사라졌지만, ~~최종적으로~~ Linear한 메모리 사용량과 Linear한 계산량을 가지게 된다.		최종적으로 위와 같은 그래프가 그려진다. Precision은 사라졌지만, 결과적으로 Linear한 메모리 사용량과 Linear한 계산량을 가지게 된다.

	== 알고리즘 ==		== 알고리즘 ==

Ahn9807: /* 같이 보기 */

2023-11-10T04:38:23Z

같이 보기

← 이전 판		2023년 11월 10일 (금) 04:38 판
44번째 줄:		44번째 줄:
	== 같이 보기 ==		== 같이 보기 ==
	# [[Anderson algorithm]]		# [[Anderson algorithm]]
	# [[Field sensitive]]		# [[Field sensitive algorithm]]

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

Ahn9807: 새 문서: 분류: 프로그램 분석 == 개요 == 큰 프로그램에 대해서 Anderson algorithm과 같은 경우에는 세제곱 복잡도로 인해서 성능이 매우 느려진다. Steensgaard 알고리즘은 정확도를 포기해서 거의 Linear-time에 프로그램 분석을 가능하도록 하는 알고리즘이다. 본 알고리즘은 Field-insensitive 알고리즘이며, 만약 Field sensitive하게 알고리즘을 만들면 이 알고리즘은 더이상 Linear-t...

2023-11-10T04:38:00Z

새 문서: 분류: 프로그램 분석 == 개요 == 큰 프로그램에 대해서 Anderson algorithm과 같은 경우에는 세제곱 복잡도로 인해서 성능이 매우 느려진다. Steensgaard 알고리즘은 정확도를 포기해서 거의 Linear-time에 프로그램 분석을 가능하도록 하는 알고리즘이다. 본 알고리즘은 Field-insensitive 알고리즘이며, 만약 Field sensitive하게 알고리즘을 만들면 이 알고리즘은 더이상 Linear-t...

새 문서

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

== 개요 ==
큰 프로그램에 대해서 [[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]]

== 참고 ==
# 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 - 편집 역사

Ahn9807: /* 개요 */

Ahn9807: /* 같이 보기 */