탈출 분석

Escape analysis

컴파일러 최적화에서 탈출 분석은 포인터의 동적 범위(프로그램에서 포인터에 액세스할 수 있는 위치)를 결정하는 방법이다. 그것은 포인터 분석과 형상 분석과 관련이 있다.

변수(또는 개체)가 서브루틴에 할당될 때, 변수에 대한 포인터가 실행의 다른 스레드로 빠져나가거나 서브루틴을 호출할 수 있다. 구현이 테일 콜 최적화를 사용하는 경우(일반적으로 기능 언어에 필요), 객체는 호출된 서브루틴으로 빠져나가는 것으로 보일 수 있다. 한 언어가 (뉴저지 주의 Scheme 및 Standard ML과 마찬가지로) 1급 연속성을 지원하는 경우, 통화 스택의 일부도 빠져나갈 수 있다.

서브루틴이 객체를 할당하고 포인터를 반환하는 경우, 프로그램의 미정 위치에서 객체에 접근할 수 있으며, 포인터가 "탈출"된 경우. 포인터도 전역 변수나 현재 절차를 벗어나는 다른 데이터 구조에 저장되어 있는 경우 탈출할 수 있다.

탈출 분석은 포인터를 저장할 수 있는 모든 장소와 포인터의 수명을 현재 절차 및/또는 스레드로만 제한할 수 있는지 여부를 결정한다.

최적화

컴파일러는 탈출 분석 결과를 최적화의 기준으로 사용할 수 있다.[1]

  • 힙 할당을 스택 할당으로 변환하는 중.[2] 객체가 서브루틴에 할당되고 객체에 대한 포인터가 절대 이탈하지 않는 경우, 객체는 힙 할당 대신 스택 할당 후보일 수 있다. 가비지 수집 언어에서 이것은 수집가가 실행해야 하는 빈도를 줄일 수 있다.
  • 동기화 엘리비전. 하나의 스레드에서만 객체에 액세스할 수 있는 것으로 확인되면 동기화 없이 객체에 대한 작업을 수행할 수 있다.
  • 객체를 분해하거나 스칼라 교체.[3] 개체가 순차 메모리 구조로 존재할 필요가 없는 방법으로 접근되는 것을 발견할 수 있다. 이렇게 하면 개체의 일부(또는 모든)가 메모리가 아닌 CPU 레지스터에 저장될 수 있다.

현실적 고려

객체 지향 프로그래밍 언어에서 동적 컴파일러는 특히 탈출 분석을 수행할 수 있는 좋은 후보들이다. 기존의 정적 컴파일에서 메서드 오버라이드는 포인터에서 탈출할 수 있는 버전에 의해 호출된 메서드가 오버라이드될 수 있기 때문에 탈출 분석을 불가능하게 만들 수 있다. 동적 컴파일러는 과부하와 관련된 정보를 이용하여 탈출 분석을 수행할 수 있으며, 동적 코드 로딩에 의해 관련 방법이 오버라이드되면 분석을 다시 수행할 수 있다.[1]

자바 프로그래밍 언어의 인기는 탈출 분석을 관심의 대상으로 만들었다. Java의 힙 전용 객체 할당, 내장 스레딩, Sun HotSpot 동적 컴파일러, OpenJ9의 JIT(Just-in-Time Compiler)의 조합은 탈출 분석 관련 최적화를 위한 후보 플랫폼을 만든다(Java의 탈출 분석 참조). 탈출 분석은 Java Standard Edition 6에서 구현된다. 일부 JVM은 할당된 객체의 스칼라 교체가 함수의 일부 경로에서 이탈하더라도 가능하게 하는 부분탈출 분석이라는 보다 강력한 탈출 분석을 지원한다.[4]

예제(Java)

계급 메인 {     공중의 정태의 공허하게 하다 본래의(끈[] 아그) {         예시();     }     공중의 정태의 공허하게 하다 예시() {         푸 foo = 새로운 푸(); //message         바 술집을 내다 = 새로운 바(); //message         술집을 내다.setFoo(foo);     } }  계급 푸 {}  계급 바 {     사유의 푸 foo;     공중의 공허하게 하다 setFoo(푸 foo) {         이.foo = foo;     } }

이 예에서는 두 개의 객체가 생성되고(할당으로 구성), 그 중 하나가 다른 객체의 방법에 대한 인수로 주어진다. 방법 setFoo() 수신된 Foo 객체에 대한 참조를 저장한다. 만약 Bar 객체가 힙 위에 있다면 Foo에 대한 참조는 빠져나갈 것이다. 그러나 이 경우 컴파일러는 탈출 분석을 통해 Bar 객체 자체가 의 호출에서 벗어나지 않는다고 판단할 수 있다. example()그것은 Foo에 대한 언급도 피할 수 없다는 것을 의미한다. 그래서 컴파일러는 스택에 있는 두 개의 물체를 안전하게 할당할 수 있다.

예제(구성표)

다음 예에서 벡터 p는 g로 빠져나가지 않기 때문에 스택에 할당한 다음 g를 호출하기 전에 스택에서 제거할 수 있다. 

(정의를 내리다 (f x)    (하게 하다 ((p (가공의 10000)))       (배부르게 먹는 p)       (g (벡터-레프 p 7023))))

하지만, 만약 우리가 

(정의를 내리다 (f x)    (하게 하다 ((p (가공의 10000)))       (배부르게 먹는 p)       (g p)))

그런 다음 p를 힙에 할당해야 하거나 또는 (f를 컴파일할 때 컴파일러에 g가 알려져 있고 잘 동작하는 경우) g를 호출할 때 제자리에 유지할 수 있는 방식으로 스택에 할당해야 한다.

예외와 같은 제어 구조를 구현하기 위해 연속성을 사용하는 경우, 탈출 분석은 실제로 연속성을 할당하고 통화 스택을 그 구조로 복사할 필요가 없도록 하기 위해 종종 이것을 감지할 수 있다. 예를 들면, 

;;사용자가 입력한 스키마 객체를 읽으십시오. 모두 숫자라면 ;;모두 순서대로 수록된 목록을 작성한다. 사용자가 다음 항목을 입력한 경우 ;;숫자가 아니므로 즉시 #f를 반환한다. (정의를 내리다 (번호표를 얻다)   (전화를 걸다/전화를 걸다 (람다 (계속)     (정의를 내리다 (얻어먹다)        (하게 하다 ((다음 목적의 (읽다)))           (묵상하다              ((eof-object?  다음 목적의) '())              ((번호? 다음 목적의) (단점 다음 목적의 (얻어먹다)))              (다른 (계속 #f)))))     (얻어먹다))))

탈출 분석은 통화/cc에 의해 포착된 연속성이 빠져나가지 않기 때문에 연속 구조를 할당할 필요가 없으며, 연속성을 호출하여 연속성을 호출하는 것은 스택을 풀어서 실행될 수 있다.

참고 항목

참조

  1. ^ a b T. Kotzmann과 H. Mössenböck, "동적 컴파일 및 최적화의 맥락에서 탈출 분석" 뉴욕, 뉴욕, 미국, 2005, 페이지 111–120 가상 실행 환경에 관한 제1차 ACM/USENIX 국제 회의의 진행.
  2. ^ Blanchet, Bruno (November 2003). "Escape Analysis for JavaTM: Theory and Practice". ACM Transactions on Programming Languages and Systems. 25 (6): 713–775. doi:10.1145/945885.945886. ISSN 0164-0925.
  3. ^ Kotzmann, Thomas; Mössenböck, Hanspeter (March 2007). Run-Time Support for Optimizations Based on Escape Analysis. International Symposium on Code Generation and Optimization (CGO'07). pp. 49–60. CiteSeerX 10.1.1.394.5944. doi:10.1109/CGO.2007.34. ISBN 978-0-7695-2764-2.
  4. ^ Stadler, Lukas; Würthinger, Thomas; Mössenböck, Hanspeter (2014). "Partial Escape Analysis and Scalar Replacement for Java". Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization - CGO '14. pp. 165–174. doi:10.1145/2581122.2544157. ISBN 9781450326704.