적시 컴파일 추적

Tracing just-in-time compilation
프로그램 실행
일반적인 개념
코드의 종류
컴파일 전략
주목할 만한 런타임
주목할 만한 컴파일러 및 툴 체인

적시 컴파일 추적은 실행 시 프로그램 실행을 최적화하기 위해 가상 시스템에서 사용하는 기술입니다.이는 자주 실행되는 작업의 선형 시퀀스를 기록하고 이를 네이티브 머신 코드로 컴파일하여 실행함으로써 이루어집니다.이는 방식별로 작동하는 기존 JIT(Just-in-Time) 컴파일러와 반대됩니다.

개요

저스트 인 타임 컴파일은 런타임에 프로그램 일부를 기계어로 컴파일해 프로그램 실행 속도를 높이는 기술이다.다른 JIT 컴파일러를 분류하는 방법 중 하나는 컴파일 범위를 기준으로 분류하는 것입니다.메서드 기반의 JIT 컴파일러는 한 번에 하나의 메서드를 기계 코드로 변환하여 J를 추적합니다.IT부문은 자주 실행되는 루프를 컴파일 단위로 사용합니다.트레이스 JIT는 프로그램이 대부분의 시간을 프로그램의 일부 루프("핫 루프")에 소비하는 것을 전제로 하고 있습니다.또, 그 후의 루프 반복도, 같은 패스를 사용하는 경우가 많습니다.추적 JIT가 있는 가상 시스템은 대개 혼합 모드 실행 환경입니다. 즉, 추적 JIT 외에 인터프리터 또는 메서드 컴파일러가 있습니다.

기술적 세부사항

트레이스 JIT 컴파일러는 런타임에 다양한 단계를 거칩니다.우선 루프의 프로파일링 정보를 수집합니다.핫 루프가 식별되면 해당 루프의 실행된 모든 동작을 기록하는 특별한 트레이스 단계가 시작됩니다.이 조작 시퀀스를 트레이스라고 부릅니다.그런 다음 트레이스가 최적화되고 머신 코드(트레이스)로 컴파일됩니다.이 루프가 다시 실행되면 프로그램 상대편 대신 컴파일된 트레이스가 호출됩니다.

이러한 순서의 상세한 것에 대하여는, 이하를 참조해 주세요.

프로파일링 단계

프로파일링의 목적은 핫루프를 식별하는 것입니다.이것은 루프마다 반복 횟수를 카운트함으로써 이루어집니다.루프 카운트가 특정 문턱값을 초과하면 루프는 핫한 것으로 간주되어 트레이스 단계가 시작됩니다.

트레이스 단계

트레이스 단계에서는 루프의 실행은 정상적으로 진행되지만 실행된 모든 동작은 트레이스에 기록됩니다.기록된 조작은 통상 트레이스 트리에 저장됩니다.종종 Intermediate Representation(IR; 중간 표현)에 저장됩니다.트레이스는 함수 호출에 이어 이루어지며, 그 결과 함수 호출이 트레이스 안으로 삽입됩니다.루프가 끝에 도달하고 다시 선두로 점프할 때까지 트레이스는 계속됩니다.

트레이스는 루프의 구체적인 실행 경로를 따라 기록되기 때문에 나중에 해당 경로에서 해당 트레이스의 실행이 분산될 수 있습니다.이 문제가 발생할 수 있는 장소를 특정하기 위해 트레이스에 특수 가드 지침이 삽입됩니다.이러한 장소의 예로는 if 스테이트먼트가 있습니다.가드는 원래 상태가 여전히 사실인지 여부를 빠르게 확인하는 것입니다.가드에 장애가 발생하면 트레이스 실행이 중단됩니다.

트레이스는 실행 중에 실행되므로 트레이스에 런타임 정보(예: 유형 정보)를 포함할 수 있습니다.이 정보는 나중에 최적화 단계에서 코드 효율을 높이기 위해 사용할 수 있습니다.

최적화 및 코드 생성 단계

트레이스는 1개의 실행 경로만을 나타내기 때문에 최적화가 용이합니다.즉, 제어 플로우가 존재하지 않기 때문에 처리가 필요하지 않습니다.일반적인 최적화에는 상수-하위 표현 제거, 데드 코드 제거, 레지스터 할당, 불변 코드 모션, 상수 폴딩 및 이스케이프 [1]분석이 포함됩니다.

최적화 후 트레이스는 기계코드로 변환됩니다.최적화와 마찬가지로, 이는 트레이스의 선형 특성으로 인해 쉽습니다.

실행

트레이스를 머신 코드로 컴파일 한 후 루프의 후속 반복으로 실행할 수 있습니다.트레이스 실행은 가드가 실패할 때까지 계속됩니다.

역사

JITs의 개념은 1960년대까지 거슬러 올라가지만, JIT를 추적하면IT의 사용 빈도는 최근에서야 높아졌습니다.J를 추적하는 오늘날의 아이디어와 유사한 아이디어의 첫 번째 언급IT는 [2]1970년에 있었다.컴파일된 코드는 단순히 해석 중에 수행된 작업을 저장함으로써 런타임에 해석자로부터 파생될 수 있다는 것이 관찰되었다.

트레이스의 첫 번째 구현은 Dynamo로, "프로세서에서 실행될 때 네이티브 명령 스트림의 성능을 투명하게 개선할 수 있는 소프트웨어 동적 최적화 시스템"[3]입니다.이를 위해 "핫" 명령 시퀀스가 발견될 때까지 네이티브 명령 스트림이 해석됩니다.이 시퀀스에서는 최적화된 버전이 생성, 캐시 및 실행됩니다.

Dynamo는 나중에 DynamoRIO로 연장되었다.Dynamo RIO에 기반을 둔 한 프로젝트는 추적과 부분 평가를 결합한 통역기 구축 프레임워크였다.이는 "언어 구현에서 인터프리터 오버헤드를 동적으로 제거하기 위해"[4] 사용되었습니다.

2006년 Hotpath VM, 최초의 트레이스 J고급[citation needed] 언어용 IT 컴파일러가 [5]개발되었습니다.이 VM은 자주 실행되는 바이트 코드 명령을 동적으로 식별할 수 있었습니다. 바이트 코드 명령은 추적된 후 SSA(Static Single Assignment) 구성을 사용하여 기계 코드로 컴파일됩니다.Hotpath VM의 동기는 리소스가 제한된 모바일 디바이스에 효율적인 JVM을 제공하기 위해서였습니다.

트레이스 J의 다른 예IT는 Mozilla의 Firefox용 JavaScript 구현(2009)[6] 중 하나인 TraceMonkey입니다.TraceMonkey는 실행 시 자주 실행되는 루프 트레이스를 동적 언어 JavaScript로 컴파일하고 생성된 코드를 각 경로에서 발생하는 실제 동적 유형에 맞게 특수화합니다.

트레이스 J를 이용한 다른 프로젝트IT는 PyPy입니다.PyPy 번역 툴체인으로 작성된 언어 구현에 JIT를 추적하여 해당 인터프리터를 사용하여 실행되는 프로그램의 성능을 향상시킬 수 있습니다.이는 [7]인터프리터에 의해 실행되는 프로그램이 아니라 인터프리터 자체를 추적함으로써 가능합니다.

트레이스 J또, Microsoft는, 공통의 중간 언어(CIL)에 관한 SPR프로젝트에서도 IT를 검토했습니다.SPER는 CIL의 범용 트레이서이며 JavaScript [8]구현을 통한 트레이스에도 사용할 수 있습니다.

트레이스 예시

다음 Python 프로그램이 연속된 정수의 제곱합이 100000을 초과할 때까지 계산한다고 가정합니다.

방어하다 광장(x):     돌아가다 x * x  i = 0 y = 0 하는 동안에 진실의:     y += 광장(i)     한다면 y > 100000:         브레이크.     i = i + 1

이 프로그램의 트레이스는 다음과 같습니다.

 루프 스타트(i1, y1)  i2 = int_mul(i1, i1)  # x*x  y2 = int_add(y1, i2)  # y += i*i  b1 = int_gt(y2, 100000)  guard_false(b1)  i3 = int_add(i1, 1)  # i = i+1  뛰어내리다(i3, y2)

함수가 호출하는 방법을 확인합니다.square트레이스에 삽입되어 if 스테이트먼트가 어떻게 변환되는지guard_false.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Bolz, Carl Friedrich; Cuni, Antonio; FijaBkowski, Maciej; Leuschel, Michael; Pedroni, Samuele; Rigo, Armin (January 2011). "Allocation Removal by Partial Evaluation in a Tracing JIT" (PDF). Proceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation. PEPM '11. pp. 43–52. doi:10.1145/1929501.1929508. S2CID 15871223. Retrieved 2020-12-13.
  2. ^ Mitchell, James G. (June 29, 1970). The Design and Construction of Flexible and Efficient Interactive Programming Systems (PhD). Carnegie Mellon University. ISBN 978-0-8240-4414-5. LCCN 79050563. OCLC 633313022. S2CID 36249021. Docket AAI7104538. Retrieved 2020-12-13.
  3. ^ Bala, Vasanth; Duesterwald, Evelyn; Banerjia, Sanjeev (May 2000). "Dynamo: A Transparent Dynamic Optimization System" (PDF). Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation. PLDI '00. pp. 1–12. doi:10.1145/349299.349303. ISBN 978-1-58113-199-4. S2CID 53223267. Retrieved 2020-12-13.
  4. ^ Sullivan, Gregory T.; Bruening, Derek L.; Baron, Iris; Garnett, Timothy; Amarasinghe, Saman (June 2003). "Dynamic Native Optimization of Interpreters" (PDF). Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators. IVME '03. pp. 50–57. CiteSeerX 10.1.1.14.9819. doi:10.1145/858570.858576. ISBN 978-1-58113-655-5. S2CID 509405. Retrieved 2020-12-13.
  5. ^ Gal, Andreas; Probst, Christian W.; Franz, Michael (June 2006). "HotpathVM: An Effective JIT Compiler for Resource-constrained Devices" (PDF). Proceedings of the 2nd international conference on Virtual execution environments. VEE '06. pp. 144–153. doi:10.1145/1134760.1134780. ISBN 978-1-59593-332-4. S2CID 17846788. QID 56580114. Retrieved 2020-12-13.
  6. ^ Gal, Andreas; Orendorff, Jason; Ruderman, Jesse; Smith, Edwin W.; Reitmaier, Rick; Bebenita, Michael; Chang, Mason; Franz, Michael; Eich, Brendan; Shaver, Mike; Anderson, David; Mandelin, David; Haghighat, Mohammad R.; Kaplan, Blake; Hoare, Graydon; Zbarsky, Boris (June 2009). "Trace-based Just-in-Time Type Specialization for Dynamic Languages" (PDF). Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '09. pp. 465–478. doi:10.1145/1542476.1542528. ISBN 978-1-60558-392-1. S2CID 207172806. Retrieved 2020-12-13.
  7. ^ Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (July 2009). "Tracing the Meta-Level: PyPy's Tracing JIT Compiler" (PDF). Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems. ICOOOLPS '09. pp. 18–25. doi:10.1145/1565824.1565827. ISBN 978-1-60558-541-3. S2CID 7478596. Retrieved 2020-12-13.
  8. ^ Bebenita, Michael; Brandner, Florian; Fahndrich, Manuel; Logozzo, Francesco; Schulte, Wolfram; Tillmann, Nikolai; Venter, Herman (October 2010). "SPUR: A Trace-Based JIT Compiler for CIL" (PDF). Proceedings of the ACM international conference on Object oriented programming systems languages and applications. OOPSLA '10. pp. 708–725. doi:10.1145/1869459.1869517. ISBN 978-1-4503-0203-6. S2CID 3395746. Retrieved 2020-12-13.

외부 링크