Anderson algorithm - 편집 역사

2023년 11월 10일 (금) 04:12에 Ahn9807님의 편집

2023-11-10T04:12:03Z

← 이전 판		2023년 11월 10일 (금) 04:12 판
11번째 줄:		11번째 줄:
	* dereference: A = *B		* dereference: A = *B

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

2023년 11월 10일 (금) 04:09에 Ahn9807님의 편집

2023-11-10T04:09:17Z

← 이전 판		2023년 11월 10일 (금) 04:09 판
11번째 줄:		11번째 줄:
	* dereference: A = *B		* dereference: A = *B

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

Ahn9807: Ahn9807님이 Anderson Algorithm 문서를 넘겨주기를 만들지 않고 Anderson algorithm 문서로 이동했습니다

2023-11-10T03:30:20Z

Ahn9807님이 Anderson Algorithm 문서를 넘겨주기를 만들지 않고 Anderson algorithm 문서로 이동했습니다

← 이전 판	2023년 11월 10일 (금) 03:30 판
(차이 없음)

2023년 11월 10일 (금) 03:30에 Ahn9807님의 편집

2023-11-10T03:30:00Z

← 이전 판		2023년 11월 10일 (금) 03:30 판
22번째 줄:		22번째 줄:
	* assign: var1 = {var1, <math>l_b</math>}, var2 = {var2, <math>l_b</math>}, .., var_x is #x element of A.		* 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		* 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즉 최종적으로 NN의 크기를 먹는다. 만약 변수 하나를 Dereference하게 된다면, 상태를 업데이트 하기 위해서 NN개의 변수 집합에 대한 dereference operation이 필요하다. 따라서 최종적으로 NNN의 최대 계산 복잡도를 가진다.

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

Ahn9807: 새 문서: 분류: 프로그램 분석 == 개요 == 앤덜슨 알고리즘은 프로그램 분석에서 기본이 되는 2가지 알고리즘 중에 하나로, 제일 정확하지만, 제일 오래걸리는 특징을 가진다. Context-insensitive 알고리즘 이며, Flow-insensitive분석 방법이다. == 알고리즘 == 포인터는 다음 4가지의 상태에서 연산된다. * address of: A = &B or (A = malloc(size), A = new ...) * copy: A = B * assign: A = B dere...

2023-11-09T09:46:25Z

새 문서: 분류: 프로그램 분석 == 개요 == 앤덜슨 알고리즘은 프로그램 분석에서 기본이 되는 2가지 알고리즘 중에 하나로, 제일 정확하지만, 제일 오래걸리는 특징을 가진다. Context-insensitive 알고리즘 이며, Flow-insensitive분석 방법이다. == 알고리즘 == 포인터는 다음 4가지의 상태에서 연산된다. * address of: A = &B or (A = malloc(size), A = new ...) * copy: A = B * assign: *A = B * dere...

새 문서

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

== 개요 ==
앤덜슨 알고리즘은 [[프로그램 분석]]에서 기본이 되는 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