이스케이프 분석

컴파일러 최적화에서 이스케이프 분석(Escape analysis)은 포인터의 동적 범위를 결정하는 방법이다. 이 분석은 프로그램 내에서 포인터가 어디에 접근될 수 있는지를 파악한다. 이는 포인터 분석 및 형태 분석과 관련이 있다.

변수(또는 객체)가 서브루틴에 할당될 때, 변수에 대한 포인터는 다른 실행 스레드나 호출 서브루틴으로 이스케이프될 수 있다. 구현에서 꼬리 재귀 최적화(일반적으로 함수형 프로그래밍 언어에서 요구됨)를 사용하는 경우, 객체는 호출된 서브루틴으로 이스케이프하는 것으로 간주될 수도 있다. 언어가 1급 연속을 지원하는 경우(예: 스킴 및 Standard ML of New Jersey), 콜 스택의 일부도 이스케이프될 수 있다.

서브루틴이 객체를 할당하고 그 객체에 대한 포인터를 반환하는 경우, 해당 객체는 프로그램 내의 불특정한 위치에서 접근될 수 있다. 즉, 포인터가 "이스케이프"한 것이다. 포인터는 또한 전역 변수나 현재 프로시저를 벗어나는 다른 데이터 구조에 저장될 때도 이스케이프할 수 있다.

이스케이프 분석은 포인터가 저장될 수 있는 모든 위치와 포인터의 생명 주기가 현재 프로시저 및 스레드에만 제한되는지 여부를 판단한다.

최적화
컴파일러는 이스케이프 분석 결과를 기반으로 최적화를 수행할 수 있다.T. Kotzmann and H. Mössenböck, “Escape analysis in the context of dynamic compilation and deoptimization,” in Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, New York, NY, USA, 2005, pp. 111–120.

 힙 할당을 스택 할당으로 변환. 객체가 서브루틴에 할당되고 객체에 대한 포인터가 절대 이스케이프하지 않는다면, 그 객체는 힙 할당 대신 스택 할당의 후보가 될 수 있다. 가비지 컬렉션 언어에서는 이로 인해 컬렉터가 실행되어야 하는 빈도를 줄일 수 있다.
 동기화 생략. 객체가 단일 스레드에서만 접근 가능한 것으로 판명되면, 해당 객체에 대한 작업은 동기화 없이 수행될 수 있다.
 객체 분할 또는 스칼라 대체. 객체가 순차적인 메모리 구조로 존재할 필요가 없는 방식으로 접근되는 것으로 판명될 수 있다. 이는 객체의 일부(또는 전체)를 메모리 대신 CPU 레지스터에 저장할 수 있도록 한다.

실용적 고려 사항
객체 지향 프로그래밍 언어에서 동적 컴파일러는 이스케이프 분석을 수행하는 데 특히 적합하다. 전통적인 정적 컴파일에서는 메소드 오버라이딩으로 인해 이스케이프 분석이 불가능할 수 있다. 이는 호출된 모든 메소드가 포인터를 이스케이프시킬 수 있는 버전으로 오버라이드될 수 있기 때문이다. 동적 컴파일러는 오버로딩에 대한 가용한 정보를 사용하여 이스케이프 분석을 수행할 수 있으며, 관련 메소드가 동적 코드 로딩에 의해 오버라이드될 때 분석을 다시 수행할 수 있다.

자바 프로그래밍 언어의 인기로 인해 이스케이프 분석은 관심의 대상이 되었다. 자바의 힙 전용 객체 할당, 내장 스레딩, 썬 핫스팟 동적 컴파일러, 그리고 OpenJ9의 JIT 컴파일러 (JIT)의 조합은 이스케이프 분석 관련 최적화를 위한 후보 플랫폼을 제공한다 (자세한 내용은 자바의 이스케이프 분석 참조). 이스케이프 분석은 자바 표준 에디션 6에 구현되어 있다. 일부 JVM은 함수의 특정 경로에서 객체가 이스케이프하더라도 할당된 객체의 스칼라 대체를 가능하게 하는 부분 이스케이프 분석이라는 더 강력한 이스케이프 분석 변형을 지원한다.

예시 (자바)
class Main {
    public static void main(String[] args) {
        example();
    }
    public static void example() {
        Foo foo = new Foo(); //alloc
        Bar bar = new Bar(); //alloc
        bar.setFoo(foo);
    }
}

class Foo {}

class Bar {
    private Foo foo;
    public void setFoo(Foo foo) {
        this.foo = foo;
    }
}

이 예시에서는 두 개의 객체가 생성되고(alloc 주석), 그 중 하나가 다른 객체의 메소드에 인수로 제공된다. `setFoo()` 메소드는 받은 Foo 객체에 대한 참조를 저장한다. Bar 객체가 힙에 있었다면 Foo에 대한 참조는 이스케이프되었을 것이다. 그러나 이 경우 컴파일러는 이스케이프 분석을 통해 Bar 객체 자체가 `example()` 호출을 벗어나지 않는다는 것을 판단할 수 있다. 결과적으로 Foo에 대한 참조도 이스케이프할 수 없으며, 컴파일러는 두 객체를 안전하게 스택에 할당할 수 있다.

예시 (스킴)
다음 예시에서 벡터 p는 g로 이스케이프되지 않으므로 스택에 할당된 후 g를 호출하기 전에 스택에서 제거될 수 있다.
(define (f x)
   (let ((p (make-vector 10000)))
      (fill-vector-with-good-stuff p)
      (g (vector-ref p 7023))))

그러나 만약 다음과 같다면
(define (f x)
   (let ((p (make-vector 10000)))
      (fill-vector-with-good-stuff p)
      (g p)))
p는 힙에 할당되거나 (g가 f가 컴파일될 때 컴파일러에 알려져 있고 잘 작동한다면) g가 호출될 때 제자리에 유지될 수 있는 방식으로 스택에 할당되어야 한다.

연속을 사용하여 예외와 같은 제어 구조를 구현하는 경우, 이스케이프 분석은 이를 자주 감지하여 실제 연속을 할당하고 콜 스택을 복사하는 것을 피할 수 있다. 예를 들어, 다음에서
;;사용자가 입력한 스킴 객체를 읽습니다. 모든 객체가 숫자이면,
;;모든 객체가 순서대로 포함된 목록을 반환합니다. 사용자가 숫자가 아닌
;;객체를 입력하면 즉시 #f를 반환합니다.
(define (getnumlist)
  (call/cc (lambda (continuation)
    (define (get-numbers)
       (let ((next-object (read)))
          (cond
             ((eof-object? next-object) '())
             ((number? next-object) (cons next-object (get-numbers)))
             (else (continuation #f)))))
    (get-numbers))))
이스케이프 분석은 `call/cc`에 의해 캡처된 연속이 이스케이프하지 않으므로 연속 구조를 할당할 필요가 없으며, `continuation`을 호출하여 연속을 호출하는 것은 스택 풀기를 통해 구현될 수 있다고 판단할 것이다.

 같이 보기 
 별칭 분석
 포인터 분석
 형태 분석

 각주 

분류:정적 프로그램 분석