별칭 분석

별칭 분석(alias analysis)은 컴파일러 이론에서 저장 위치가 두 가지 이상의 방식으로 접근될 수 있는지 확인하는 데 사용되는 기술이다. 두 포인터가 동일한 위치를 가리키는 경우 별칭 처리된다고 말한다.

별칭 분석 기술은 일반적으로 흐름 민감도와 문맥 민감도에 따라 분류된다. 이는 may-alias 또는 must-alias 정보를 결정할 수 있다. 별칭 분석이라는 용어는 특정 사례인 포인터 분석과 종종 상호 교환적으로 사용된다.

별칭 분석기는 프로그램 내 별칭 처리를 이해하는 데 유용한 정보를 만들고 계산하는 것을 목표로 한다.

개요
일반적으로 별칭 분석은 별개의 메모리 참조가 메모리의 동일한 영역을 가리키는지 여부를 결정한다. 이를 통해 컴파일러는 프로그램의 어떤 변수가 특정 문장에 의해 영향을 받을지 결정할 수 있다. 예를 들어, 구조체 멤버에 접근하는 다음 코드 섹션을 고려해 보자:

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

여기에는 세 가지 가능한 별칭 사례가 있다:
 변수 p와 q는 별칭 처리될 수 없다 (즉, 결코 동일한 메모리 위치를 가리키지 않는다).
 변수 p와 q는 반드시 별칭 처리되어야 한다 (즉, 항상 동일한 메모리 위치를 가리킨다).
 컴파일 시점에 p와 q가 별칭 처리되는지 여부를 확실하게 결정할 수 없다.

만약 p와 q가 별칭 처리될 수 없다면, i = p.foo + 3;는 i = 4로 변경될 수 있다. 만약 p와 q가 반드시 별칭 처리되어야 한다면, i = p.foo + 3;는 i = 5로 변경될 수 있는데, 왜냐하면 p.foo + 3 = q.foo + 3이기 때문이다. 두 경우 모두, 별칭 지식으로부터 최적화를 수행할 수 있다 (다른 스레드가 동일한 위치를 업데이트하여 현재 스레드와 인터리빙될 수 없거나, 언어 메모리 모델이 명시적인 동기화 구성이 없는 경우 현재 스레드에게 즉시 보이지 않도록 해당 업데이트를 허용한다고 가정한다). 반면에, p와 q가 별칭 처리되는지 여부가 알려지지 않으면, 어떤 최적화도 수행할 수 없으며 결과를 얻기 위해 전체 코드가 실행되어야 한다. 두 메모리 참조는 별칭 처리가 알려지지 않은 경우 may-alias 관계를 갖는다고 말한다.

별칭 분석 수행

별칭 분석에서 우리는 프로그램의 메모리를 별칭 클래스로 나눈다. 별칭 클래스는 서로 별칭 처리될 수 없는 위치들의 분리된 집합이다. 여기서는 여기서 수행되는 최적화가 프로그램의 저수준 중간 표현에서 발생한다고 가정한다. 즉, 프로그램이 이진 연산, 점프, 레지스터 간 이동, 레지스터에서 메모리로 이동, 메모리에서 레지스터로 이동, 분기, 함수 호출/반환으로 컴파일되었다는 의미이다.

타입 기반 별칭 분석
컴파일되는 언어가 타입 안전하고, 컴파일러의 타입 검사기가 정확하며, 언어가 지역 변수를 참조하는 포인터를 생성하는 기능이 부족하다면 (예: ML, 하스켈, 또는 자바), 유용한 최적화를 수행할 수 있다. 두 메모리 위치가 다른 별칭 클래스에 있어야 한다고 아는 많은 경우가 있다:

 서로 다른 타입의 두 변수는 동일한 별칭 클래스에 있을 수 없다. 이는 강타입, 메모리 참조가 없는 (즉, 메모리 위치에 대한 참조를 직접 변경할 수 없는) 언어의 속성상 서로 다른 타입의 두 변수가 동시에 동일한 메모리 위치를 공유할 수 없기 때문이다.
 현재 스택 프레임에 로컬로 할당된 메모리는 이전 스택 프레임의 어떤 할당과도 동일한 별칭 클래스에 있을 수 없다. 이는 새로운 메모리 할당이 다른 모든 메모리 할당과 분리되어야 하기 때문이다.
 각 레코드 타입의 각 레코드 필드는 일반적으로 자체 별칭 클래스를 갖는다. 이는 타이핑 규율이 일반적으로 동일한 타입의 레코드만 별칭 처리되도록 허용하기 때문이다. 특정 타입의 모든 레코드가 메모리에 동일한 형식으로 저장되므로, 필드는 자체적으로만 별칭 처리될 수 있다.
 마찬가지로, 주어진 타입의 각 배열은 자체 별칭 클래스를 갖는다.

코드에 대한 별칭 분석을 수행할 때, 메모리에 대한 모든 로드 및 스토어는 해당 클래스로 레이블이 지정되어야 한다. 그러면  별칭 클래스를 갖는 메모리 위치 와 가 주어졌을 때, 이면 는 와 may-alias 관계를 가지며, 이면 메모리 위치는 별칭 처리되지 않는다는 유용한 속성을 갖게 된다.

흐름 기반 별칭 분석
흐름 기반 분석은 참조 또는 타입 캐스팅이 있는 언어의 프로그램에 적용될 수 있다. 흐름 기반 분석은 타입 기반 분석을 대신하거나 보완하는 데 사용될 수 있다. 흐름 기반 분석에서 새로운 별칭 클래스는 각 메모리 할당에 대해, 그리고 주소가 사용된 모든 전역 및 지역 변수에 대해 생성된다. 참조는 시간이 지남에 따라 하나 이상의 값을 가리킬 수 있으므로 하나 이상의 별칭 클래스에 속할 수 있다. 이는 각 메모리 위치가 단일 별칭 클래스 대신 별칭 클래스 집합을 갖는다는 것을 의미한다.

 같이 보기 

 이스케이프 분석
 포인터 분석
 형태 분석

 각주 



 외부 링크 
 별칭 분석의 분류 및 적용 - 이 분야에 대한 소개를 담은 석사 논문.

분류:정적 프로그램 분석