RPython 툴체인 ============== .. contents:: 이 문서는 RPython 프로그램(PyPy 자체와 같은)을 다양한 대상 플랫폼에 맞춰 분석하고 "컴파일"하기 위해 우리가 개발한 툴체인을 설명합니다. 이 문서는 크게 세 부분으로 구성되어 있습니다: 다소 단순화된 개요, 저희 툴체인의 주요 구성 요소 각각에 대한 간략한 소개, 그리고 각 구성 요소가 어떻게 맞물리는지를 더 포괄적으로 설명하는 절입니다. 이 문서를 처음 읽으신다면 `개요`_\ 가 가장 유용할 것이고, PyPy에 대한 기억을 되살리려는 것이라면 `어떻게 맞물려 동작하는가`_\ 절이 원하시는 내용일 것입니다. 개요 ---- 번역(translation) 툴체인의 역할은 RPython 프로그램을 다양한 대상 플랫폼 중 하나를 위한 효율적인 버전으로 번역하는 것이며, 이 플랫폼은 일반적으로 Python보다 훨씬 저수준입니다. 이 작업은 여러 단계로 나뉘며, 이 문서의 목적은 그 단계들을 소개하는 것입니다. 먼저 :ref:`RPython ` 프로그램을 C(기본이자 원래 대상)로 번역(translation)하는 과정을 설명합니다. .. _initialization-time: RPython 번역(translation) 도구 체인은 Python 소스 코드나 구문 트리를 전혀 보지 않으며, 대신 입력으로 주어진 함수 객체의 동작을 정의하는 *코드 객체*\ 에서 시작합니다. 이 코드 객체들은 :ref:`플로우 그래프 빌더`\ 가 `추상 해석`_\ 을 사용하여 처리한 결과, 제어 흐름 그래프(함수당 하나씩)로 만들어집니다: 이는 소스 프로그램의 또 다른 표현이지만, 타입 추론과 번역(translation) 기법을 적용하기에 적합하며, 대부분의 번역(translation) 단계가 다루는 근본적인 자료구조입니다. 번역(translation)을 다음 단계들로 구성된 것으로 생각하면 도움이 됩니다(아래 그림도 참고하십시오): 1. 전체 프로그램이 임포트되며, 이 시점에 임의의 실행 시점 초기화를 수행할 수 있습니다. 이 작업이 끝나면, 프로그램은 :doc:`RPython `\ 의 의미에서 "충분히 정적인" 형태로 메모리에 존재해야 합니다. 2. Annotator_\ 는 지정된 진입점에서 시작해 전역 분석을 수행하여, 각 변수가 실행 시점에 담을 수 있는 타입 및 기타 정보를 추론하며, 그 과정에서 마주치는 대로 :ref:`흐름 그래프를 구축합니다 `. 3. 제어 흐름 그래프의 연산을 저수준 연산으로 변환하기 위해, :ref:`RPython Typer ` (또는 RTyper)는 Annotator가 추론한 고수준 정보를 사용합니다. 4. RTyper 이후에는 적용할 수 있는 여러 선택적 `optimizations`_\ 이 있으며, 이는 결과 프로그램을 더 빠르게 만들기 위한 것입니다. 5. 다음 단계는 `preparing the graphs for source generation`_\ 이며, 이는 프로그램 내의 다양한 함수와 타입이 최종 소스에서 갖게 될 이름을 계산하고, 명시적인 예외 처리와 메모리 관리 연산을 삽입하는 변환을 적용하는 과정을 포함합니다. 6. `C 백엔드`_ (속칭 "GenC"라고 불림)은 다수의 C 소스 파일을 생성합니다(위에서 언급했듯이, 지금은 다른 백엔드들은 무시합니다). 7. 이 소스 파일들은 컴파일되어 실행 파일을 생성합니다. (다만 이 단계들은 이 설명에서 여러분이 생각하는 것만큼 뚜렷하게 구분되지는 않습니다). 번역(translation) 과정에는 이 단계들을 대화식으로 진행할 수 있게 해주는 :source:`rpython/bin/translatorshell.py`\ 라는 :ref:`대화형 인터페이스 `\ 가 있습니다. 다음 그림은 단순화된 개요를 보여줍니다(`PDF color version`_): .. image:: _static/translation-greyscale-small.png .. _PDF color version: _static/translation.pdf .. _abstract interpretation: http://en.wikipedia.org/wiki/Abstract_interpretation .. _flow-graphs: 흐름 그래프(Flow Graph) 구축 ---------------------------- 소개 ~~~~ 흐름 그래프 빌더(소스는 :source:`rpython/flowspace/`\ 에 있습니다)의 역할은 함수로부터 제어 흐름 그래프를 생성하는 것입니다. 이 그래프는 개별 연산들의 트레이스도 담고 있으므로, 실제로는 해당 함수에 대한 또 다른 표현 방식에 불과합니다. 기본 아이디어는 인터프리터에 함수가 주어졌을 때, 예를 들어:: def f(n): return 3*n+2 그것을 바이트코드로 컴파일한 다음 자신의 VM에서 실행합니다. 대신, 흐름 그래프 빌더는 바이트코드를 받아 필요한 스택 조작과 변수 처리를 수행하지만, Python 객체에 대해 실제로 수행되는 연산은 기본 블록(basic block)이라 불리는 구조에 기록하기만 하는 `abstract interpreter`_\ 를 포함합니다. 연산의 결과는 이후 연산에 나타날 수 있는 자리 표시자(placeholder) 값으로 표현됩니다. .. _abstract interpreter: http://en.wikipedia.org/wiki/Abstract_interpretation 예를 들어 위 함수의 인자로 플레이스홀더 ``v1``\ 이 주어지면, 바이트코드 인터프리터는 ``v2 = space.mul(space.wrap(3), v1)``\ 을 호출한 다음 ``v3 = space.add(v2, space.wrap(2))``\ 을 호출하고 ``v3``\ 를 결과로 반환합니다. 이러한 호출 중에 다음 블록이 기록됩니다.:: Block(v1): # input argument v2 = mul(Constant(3), v1) v3 = add(v2, Constant(2)) 추상 해석 ~~~~~~~~~ ``build_flow()``\ 는 바이트코드 인터프리터가 실행한 모든 연산을 기본 블록(basic block)으로 기록하는 방식으로 동작합니다. 기본 블록은 다음 두 경우 중 하나가 발생하면 종료됩니다: 바이트코드 인터프리터가 ``is_true()``\ 를 호출하는 경우, 또는 조인포인트(joinpoint)에 도달하는 경우입니다. * 다음 연산이 현재 블록에 막 기록되려는 시점에, 동일한 바이트코드 위치에 대한 연산을 이미 기록하고 있는 다른 블록이 존재하는 경우 조인포인트(joinpoint)가 발생합니다. 이는 바이트코드 인터프리터가 루프를 닫고 이미 살펴본 코드를 다시 해석하고 있음을 의미합니다. 이 상황에서는 바이트코드 인터프리터를 중단시키고, 현재 블록의 끝에서 이전 블록으로 되돌아가는 링크를 만들어 흐름 그래프(flow graph)에서도 루프를 닫습니다. (이는 연산이 막 기록되려는 시점에만 발생하며, 이를 통해 어느 정도의 상수 폴딩(constant-folding)이 가능해집니다.) * 바이트코드 인터프리터가 ``is_true()``\ 를 호출하면, 추상 인터프리터는 일반적으로 답이 True여야 할지 False여야 할지 알 수 없으므로, 조건부 점프를 배치하고 현재 기본 블록에 대해 두 개의 후속 블록을 생성합니다. 바이트코드 인터프리터를 속여서 ``is_true()``\ 가 처음에는 False를 반환한다고(그리고 이어지는 연산들이 첫 번째 후속 블록에 기록된다고) 생각하게 만들고, 이후에는 *같은* ``is_true()`` 호출이 True도 반환한다고(그리고 이번에는 이어지는 연산들이 다른 후속 블록으로 간다고) 생각하게 만드는 일종의 트릭이 사용됩니다. (이 절은 추후 보강될 예정입니다...) .. _flow-model: 흐름 모델(Flow Model) --------------------- 여기서는 ``build_flow()``\ 가 생성하는 데이터 구조에 대해 설명하며, 이는 번역(translation) 과정의 기본 데이터 구조입니다. 이 모든 타입은 :source:`rpython/flowspace/model.py`\ 에 정의되어 있습니다(다시 한번 강조하자면, 이는 PyPy 소스 베이스에서 상당히 중요한 모듈입니다). 함수의 흐름 그래프(flow graph)는 ``FunctionGraph`` 클래스로 표현됩니다. 이는 ``Link``\ 로 연결된 ``Block``\ 들의 컬렉션에 대한 참조를 포함합니다. ``Block``\ 은 ``SpaceOperation``\ 들의 목록을 포함합니다. 각 ``SpaceOperation``\ 은 ``opname``\ 과 ``args`` 목록, ``result``\ 를 가지며, 이는 ``Variable``\ 이거나 ``Constant``\ 입니다. 저희에게는 매우 유용한 PyGame 뷰어가 있는데, 이를 이용하면 번역(translation) 과정의 다양한 단계에서 그래프를 시각적으로 살펴볼 수 있습니다(문제가 발생하는 이유를 파악하는 데 매우 유용합니다). 이는 다음과 같은 모습입니다: .. image:: _static/bpnn_update.png 흐름 그래프(flow graph)의 구조에 대한 감을 잡으려면 몇 가지 예제에서 ``python bin/translatorshell.py``\ 를 사용해 보는 것을 권장합니다. 다음은 타입과 그 속성을 좀 더 자세히 설명합니다: ``FunctionGraph`` 하나의 그래프(하나의 함수에 대응)를 담는 컨테이너입니다. :startblock: the first block. It is where the control goes when the 함수가 호출됩니다. startblock의 입력 인자는 함수의 인자입니다. 함수가 ``*args`` 인자를 받는 경우, ``args`` 튜플이 startblock의 마지막 입력 인자로 주어집니다. :returnblock: the (unique) block that performs a function return. It is 비어 있으며, 실제로 어떤 ``return`` 연산도 포함하지 않습니다. 반환은 암묵적입니다. 반환된 값은 returnblock의 유일한 입력 변수입니다. :exceptblock: the (unique) block that raises an exception out of the 함수입니다. 두 입력 변수는 각각 예외 클래스와 예외 값입니다. (함수가 명시적으로 예외를 발생시키지 않으면, 다른 어떤 블록도 실제로 exceptblock에 연결되지 않습니다.) ``Block`` 기본 블록(basic block)은 연산 목록을 포함하며, 다른 기본 블록으로의 점프로 끝납니다. 블록이 실행되는 동안 "활성" 상태인 모든 값은 Variable에 저장됩니다. 각 기본 블록은 자신만의 고유한 Variable을 사용합니다. :inputargs: list of fresh, distinct Variables that represent all the 이전 블록들 중 어느 것에서든 이 블록으로 들어올 수 있는 값들입니다. :operations: list of SpaceOperations. :exitswitch: see below :exits: list of Links representing possible jumps from the end of this 기본 블록에서 다른 기본 블록의 시작 부분으로 각 Block\ 은 다음 방법 중 하나로 종료됩니다: * 무조건 점프: exitswitch\ 는 None이고, exits\ 는 단일 Link를 포함합니다. * 조건부 점프: exitswitch는 Block에 나타나는 Variables 중 하나이며, exits는 하나 이상의 Links(보통 2개)를 포함합니다. 각 Link의 exitcase는 구체적인 값을 제공합니다. 이는 "switch"에 해당하는 것으로, 제어 흐름은 exitcase가 exitswitch Variable의 런타임 값과 일치하는 Link를 따라갑니다. Variable이 어떤 exitcase와도 일치하지 않으면 런타임 오류입니다. * 예외 포착(exception catching): exitswitch는 ``Constant(last_exception)``\ 입니다. 첫 번째 Link는 exitcase가 None으로 설정되어 있으며, 예외가 발생하지 않는 경로를 나타냅니다. 다음 Link들은 exitcase가 Exception의 서브클래스로 설정되어 있으며, 기본 블록(basic block)의 *마지막* 연산이 일치하는 예외를 발생시킬 때 선택됩니다. (따라서 기본 블록은 비어 있으면 안 되며, 마지막 연산만 핸들러에 의해 보호됩니다.) * return 또는 except: returnblock과 exceptblock은 operations는 빈 튜플로, exitswitch는 None으로, exits는 비어 있게 설정되어 있습니다. ``링크`` 하나의 기본 블록에서 다른 기본 블록으로의 링크입니다. :prevblock: the Block that this Link is an exit of. :target: the target Block to which this Link points to. :args: a list of Variables and Constants, of the same size as the target Block의 inputargs이며, 다음 블록에 전달되는 모든 값을 제공합니다. (prevblock에서 사용된 각 Variable이 ``args`` 목록에 0번, 1번 또는 그 이상 나타날 수 있다는 점에 유의하십시오.) :exitcase: see above. :last_exception: None or a Variable; see below. :last_exc_value: None or a Variable; see below. ``args``\ 는 prevblock의 Variable을 사용하며, 이는 튜플 할당이나 함수 호출에서와 마찬가지로 위치에 따라 대상 블록의 ``inputargs``\ 와 매칭된다는 점에 유의하십시오. 링크가 예외를 포착하는 링크라면, ``last_exception``\ 과 ``last_exc_value``\ 는 링크에 진입할 때 생성되는 것으로 간주되는 두 개의 새로운 Variable로 설정됩니다. 실행 시점에는 각각 예외 클래스와 값을 담게 됩니다. 이 두 개의 새로운 변수는 같은 링크의 ``args`` 목록에서만 사용될 수 있으며, 다음 블록으로 전달됩니다(평소와 같이 실제로는 전혀 나타나지 않거나 ``args``\ 에 여러 번 나타날 수도 있습니다). ``SpaceOperation`` 기록된(또는 다른 방식으로 생성된) 기본 연산(basic operation)입니다. :opname: the name of the operation. ``build_flow()`` produces only operations ``rpython.flowspace.operation``\ 의 목록에서 가져오지만, 이후에는 이름을 임의로 변경할 수 있습니다. :args: list of arguments. Each one is a Constant or a Variable seen 이전에 기본 블록(basic block)에서 :result: a *new* Variable into which the result is to be stored. 연산은 보통 실행 시점에 암묵적으로 예외를 발생시킬 수 없다는 점에 유의하십시오. 예를 들어 코드 생성기는 리스트에 대한 ``getitem`` 연산이 안전하며 경계 검사 없이 수행될 수 있다고 가정할 수 있습니다. 이 규칙의 예외는 다음과 같습니다: (1) 연산이 블록의 마지막 연산이면서 ``exitswitch == Constant(last_exception)``\ 으로 끝나는 경우, 암묵적 예외를 확인하고 생성하여 적절히 처리해야 합니다; (2) ``simple_call``\ 이나 ``call_args``\ 에 따른 다른 함수 호출은 호출된 함수가 발생시킬 수 있는 예외를 항상 발생시킬 수 있으며, 이러한 예외는 위에서 설명한 대로 포착되지 않는 한 상위 호출자에게 전달되어야 합니다. ``Variable`` 런타임(run-time) 값을 위한 자리 표시자(placeholder)입니다. 여기에는 대부분 디버깅 관련 내용이 있습니다. :name: it is good style to use the Variable object itself instead of its 값을 참조하기 위한 ``name`` 속성, 비록 그 ``name``\ 이 고유함이 보장되기는 하지만 ``상수`` SpaceOperation의 인자로 사용되거나, 대상 Block에서 입력 Variable을 초기화하기 위해 Link를 통해 전달할 값으로 사용되는 상수 값입니다. :value: the concrete value represented by this Constant. :key: a hashable object representing the value. Constant는 간혹 변경 가능한(mutable) Python 객체를 저장할 수 있습니다. 이는 해당 객체의 정적이고 미리 초기화된, 읽기 전용 버전을 나타냅니다. 흐름 그래프(flow graph)는 이러한 Constant를 실제로 변경하려고 시도해서는 안 됩니다. .. _annotator: 어노테이션(Annotation) 패스 --------------------------- 아래에서는 제어 흐름 그래프에 어떻게 "주석을 달아(annotated)" 객체들의 타입을 알아낼 수 있는지 간략히 설명합니다. 이 주석 처리 과정(annotation pass)은 타입 추론의 한 형태입니다. 이는 Flow 객체 공간(object space)이 만든 제어 흐름 그래프에서 동작합니다. 어노테이션 과정에 대한 더 포괄적인 설명은 저희의 `EU report about translation`_\ 의 해당 절을 참조하십시오. 어노테이터(annotator)의 주요 목표는 흐름 그래프에 나타나는 각 변수를 "어노테이트"하는 것입니다. "어노테이션"은 함수당 하나씩 존재하는 모든 흐름 그래프에 대한 전체 프로그램 분석을 바탕으로, 이 변수가 실행 시점에 담을 수 있는 모든 가능한 Python 객체를 기술합니다. "annotation"은 ``SomeObject``\ 의 서브클래스의 인스턴스입니다. 각 서브클래스는 특정 객체 계열을 나타냅니다. 다음은 개요입니다 (``pypy/annotation/model/``\ 참조): * ``SomeObject``\ 는 기본 클래스입니다. ``SomeObject()``\ 의 인스턴스는 임의의 Python 객체를 나타내며, 이는 대개 입력 프로그램이 완전한 RPython이 아니었음을 의미합니다. * ``SomeInteger()``\ 는 임의의 정수를 나타냅니다. ``SomeInteger(nonneg=True)``\ 는 음이 아닌 정수(``>=0``)를 나타냅니다. * ``SomeString()``\ 은 임의의 문자열을 나타내고, ``SomeChar()``\ 는 길이가 1인 문자열을 나타냅니다. * ``SomeTuple([s1,s2,..,sn])``\ 는 길이가 ``n``\ 인 튜플을 나타냅니다. 이 튜플의 요소들은 각각 주어진 annotation 목록에 의해 제약됩니다. 예를 들어, ``SomeTuple([SomeInteger(), SomeString()])``\ 는 정수와 문자열이라는 두 항목을 가진 튜플을 나타냅니다. 어노테이션(annotation) 패스의 결과는 본질적으로 ``Variable``\ 들을 어노테이션에 매핑하는 큰 딕셔너리입니다. 모든 ``SomeXxx`` 인스턴스는 불변입니다. annotator가 Variable이 무엇을 담을 수 있는지에 대한 자신의 판단을 수정해야 할 경우, 기존 주석을 변경하는 것이 아니라 새로운 주석을 생성하여 그렇게 합니다. .. _EU report about translation: https://foss.heptapod.net/pypy/extradoc/-/tree/branch/extradoc/D05.1_Publish_on_translating_a_very-high-level_description.pdf 가변 값과 컨테이너 ~~~~~~~~~~~~~~~~~~ 가변(mutable) 객체는 어노테이션 과정에서 특별한 처리가 필요합니다. 포함된 값들의 어노테이션이 변경 연산(mutation operations)을 반영하기 위해 갱신되어야 할 수 있고, 그 결과 어노테이션 정보가 흐름 그래프(flow graph)의 관련 부분들에 다시 흘러 들어가야 하기 때문입니다. * ``SomeList``\ 는 동종(homogeneous) 타입의 리스트를 나타냅니다(즉, 리스트의 모든 원소는 단일한 공통 ``SomeXxx`` 어노테이션으로 표현됩니다). * ``SomeDict``\ 는 동종(homogeneous) 딕셔너리를 나타냅니다 (즉, 모든 키가 동일한 ``SomeXxx`` 애노테이션을 가지며, 모든 값도 마찬가지입니다). 사용자 정의 클래스와 인스턴스 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ``SomeInstance``\ 는 주어진 클래스 또는 그 서브클래스의 인스턴스를 나타냅니다. 애노테이터가 확인한 사용자 정의 클래스마다, 그 클래스의 인스턴스가 갖는 속성을 기술하는 ClassDef(``pypy.annotation.classdef``)를 유지합니다. 본질적으로 ClassDef는 모든 클래스 수준 및 인스턴스 수준 속성의 집합을 제공하며, 각각에 대해 대응하는 ``SomeXxx`` 애노테이션을 제공합니다. 인스턴스 수준 속성은 어노테이션(annotation)이 진행됨에 따라 점진적으로 발견됩니다. 다음과 같은 할당문은:: inst.attr = value 주어진 인스턴스의 ClassDef를 갱신하여, 주어진 속성이 존재하고 주어진 값만큼 일반적일 수 있음을 기록합니다. 각 속성에 대해, ClassDef는 해당 속성이 *읽히는* 모든 위치도 기록합니다. 이후 어느 시점에 해당 속성에 대한 어노테이션을 일반화하도록 강제하는 대입을 발견하면, 지금까지 해당 속성을 읽은 모든 위치가 무효로 표시되고 어노테이터는 그 지점부터 분석을 재시작합니다. 인스턴스 수준 속성과 클래스 수준 속성의 구분은 미미합니다; 클래스 수준 속성은 본질적으로 인스턴스 수준 속성의 초기값으로 간주됩니다. 메서드는 인스턴스의 초기값으로 간주될 때 인스턴스에 바인딩된다는 점(즉, ``self = SomeInstance(cls)``)을 제외하면 이런 점에서 특별하지 않습니다. 상속 규칙은 다음과 같습니다: 두 ``SomeInstance`` 어노테이션의 합집합은 가장 정밀한 공통 기반 클래스의 ``SomeInstance``\ 입니다. 부모 클래스의 ``SomeInstance``\ 를 통해 어떤 속성이 고려된다면(즉, 읽히거나 쓰인다면), 우리는 모든 서브클래스도 동일한 속성을 가지며 동일한 어노테이션이 그 모두에 적용된다고 가정합니다(따라서 부모 클래스의 메서드에 있는 ``return self.x`` 같은 코드는 부모 클래스와 그 모든 서브클래스가 속성 ``x``\ 를 가지도록 강제하며, 그 어노테이션은 모든 서브클래스가 ``x``\ 에 저장하고자 할 수도 있는 모든 값을 포함할 만큼 충분히 일반적입니다). 그러나 서로 다른 서브클래스들은 부모 클래스를 통해 일반적인 방식으로 사용되지 않는 경우, 서로 다르고 관련 없는 어노테이션을 가진 동일한 이름의 속성을 가질 수 있습니다. RPython 타이퍼(Typer) --------------------- 자세한 내용은 :doc:`rtyper`\ 를 참조하십시오. .. _optimizations: 백엔드 최적화 ------------- 백엔드 최적화의 목적은 컴파일된 프로그램을 더 빠르게 실행되도록 만드는 것입니다. 전통적인 컴파일러와는 매우 다른 PyPy 번역기(translator)의 많은 부분과 비교하면, 이들 중 대부분은 컴파일러의 작동 방식을 아는 사람들에게 상당히 익숙할 것입니다. 함수 인라이닝 ~~~~~~~~~~~~~ PyPy 인터프리터를 실행할 때 발생하는 많은 함수 호출의 오버헤드를 줄이기 위해, 함수 인라이닝(inlining)을 구현했습니다. 이는 흐름 그래프(flow graph)와 호출 지점(callsite)을 받아, 흐름 그래프의 사본을 호출하는 함수의 그래프에 삽입하고, 등장하는 변수의 이름을 적절히 바꾸는 최적화입니다. 원래 함수가 ``try: ... except: ...`` 가드(guard)로 둘러싸여 있는 경우 문제가 발생합니다. 이 경우 인라이닝이 항상 가능한 것은 아닙니다. 그러나 호출된 함수가 직접 예외를 발생시키지 않는 경우(하지만 더 깊이 호출되는 함수에서 예외가 발생할 가능성이 있는 경우)에는 인라이닝이 안전합니다. 추가로 어디에 인라인할지를 결정하는 휴리스틱도 구현했습니다. 이를 위해 모든 함수에 "크기"를 할당합니다. 이 크기는 해당 함수가 어딘가에 인라인될 경우 예상되는 코드 크기 증가량에 대략 대응해야 합니다. 이 추정치는 두 수의 합입니다. 하나는 모든 연산에 특정 가중치가 할당되는 것이며, 기본값은 가중치 1입니다. 일부 연산은 다른 연산보다 더 많은 비용이 드는 것으로 간주됩니다(예: 메모리 할당과 호출). 반면 다른 연산은 전혀 비용이 들지 않는 것으로 간주됩니다(캐스트 등). 크기 추정치는 우선 그래프에 나타나는 모든 연산의 가중치 합입니다. 이를 "정적 명령어 수"라고 부릅니다. 그래프 크기 추정치의 나머지 부분은 "중간 실행 비용"입니다. 이 역시 그래프의 모든 연산 가중치 합이지만, 이번에는 해당 연산이 얼마나 자주 실행되는지에 대한 추정치로 가중됩니다. 이 추정치를 얻기 위해 모든 분기에서 두 경로를 동일한 빈도로 택한다고 가정하되, 루프의 끝에 해당하는 분기는 예외로 하여 루프 끝으로 되돌아가는 점프가 더 가능성이 높은 것으로 간주합니다. 이로부터 연립 방정식이 도출되며, 이를 풀면 모든 연산에 대한 근사 가중치를 얻을 수 있습니다. 모든 함수에 대한 크기 추정이 결정된 후, 가장 작은 함수부터 시작하여 함수들이 호출 지점(callsite)으로 인라인됩니다. 함수가 다른 함수로 인라인될 때마다, 바깥쪽 함수의 크기가 다시 계산됩니다. 이 과정은 남은 함수들이 모두 미리 정해진 한계값보다 큰 크기를 가질 때까지 계속됩니다. Malloc 제거 ~~~~~~~~~~~ RPython은 가비지 컬렉션을 사용하는 언어이기 때문에 항상 힙 메모리 할당이 많이 발생하는데, 이는 좀 더 전통적인 명시적 메모리 관리 언어라면 아예 발생하지 않거나, 소멸 시점을 미리 알 수 있어 명시적으로 해제 가능한 객체를 만들어냈을 것입니다. 예를 들어 다음과 같은 형태의 루프는:: for i in range(n): ... 0부터 n - 1까지의 모든 숫자를 단순히 순회하는 것으로, Python에서는 다음과 동등합니다:: l = range(n) iterator = iter(l) try: while 1: i = iterator.next() ... except StopIteration: pass 이는 세 번의 메모리 할당이 실행된다는 것을 의미합니다: range 객체, range 객체의 반복자(iterator), 그리고 루프를 종료시키는 StopIteration 인스턴스입니다. 약간의 인라이닝 이후, 이 세 객체는 다른 함수의 인자로 전달되는 일도 전혀 없으며 전역적으로 도달 가능한 위치에 저장되지도 않습니다. 이러한 상황에서는 (어차피 함수가 반환된 후 소멸할 것이므로) 해당 객체를 제거하고 그것이 담고 있는 값들로 대체할 수 있습니다. 이러한 패턴(할당된 객체가 현재 함수를 벗어나지 않고 함수가 반환된 후 소멸하는 경우)은 특히 인라이닝이 일어난 후에 상당히 자주 발생합니다. 따라서 저희는 이 단순하지만 상당히 흔한 상황에서 객체를 "폭발(explode)"시켜 할당 한 번을 절약하는 최적화를 구현했습니다. 탈출 분석(Escape Analysis)과 스택 할당 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 메모리 할당 부담을 줄이는 또 다른 기법은 자신이 할당된 스택 프레임보다 오래 살아남지 않는다고 증명할 수 있는 객체에 대해 스택 할당을 사용하는 것입니다. 이는 실제로 속도 향상을 가져오지 않는 것으로 판명되어, 시간이 지나면서 다시 제거되었습니다. .. _preparing the graphs for source generation: 소스 생성을 위한 준비 --------------------- 다소 모호하게 이름 붙여졌을 수도 있는 이 단계는, 별도의 단계로 등장한 것 중 가장 최근의 것입니다. 이 단계의 역할은 소스 생성 이전에 최종 구현 결정을 내리는 것입니다 -- 실제로 소스 코드를 생성하는 것과 동시에 *어떤* 사고 작업이라도 수행하는 것은 결코 바람직하지 않다는 것이 경험상 밝혀졌습니다. C 백엔드의 경우, 이 단계는 세 가지 일을 수행합니다: - 명시적 예외 처리를 삽입합니다, - 명시적인 메모리 관리 연산을 삽입하며, - 최종 소스에서 함수와 타입이 갖게 될 이름을 결정합니다(객체와 이름 사이의 이러한 매핑은 때때로 "저수준 데이터베이스"라고 불립니다). 예외 처리를 명시적으로 만들기 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RPython 코드는 제약 없는 Python과 거의 같은 방식으로 예외를 자유롭게 사용할 수 있지만, 최종 결과물은 C 프로그램이며 C에는 예외라는 개념이 없습니다. 예외 변환기(exception transformer)는 CPython과 비슷한 방식으로 예외 처리를 구현합니다: 예외는 특수한 반환값으로 표시되며 현재 예외는 전역 자료구조에 저장됩니다. 어떤 의미에서 예외 변환기(exception transformer)의 입력은 예외가 포함된 :term:`lltypesystem`\ 을 기준으로 한 프로그램이고, 출력은 순수한 lltypesystem을 기준으로 한 프로그램입니다. 메모리 관리 세부 사항 ~~~~~~~~~~~~~~~~~~~~~ 예외를 특징으로 할 뿐만 아니라, RPython은 가비지 컬렉션되는 언어입니다. 다시 말하지만 C는 그렇지 않습니다. 이 모순을 해결하기 위해, 메모리 관리에 관한 결정이 내려져야 합니다. 유연성에 대한 PyPy의 접근 방식에 맞게, 이를 수행하는 방법을 자유롭게 변경할 수 있습니다. 오늘날 구현된 접근 방식은 세 가지입니다: - 참조 카운팅(사용 중단됨, 너무 느림) - `Boehm-Demers-Weiser conservative garbage collector`_\ 를 사용하여 - 저희의 커스텀 :doc:`RPython으로 구현된 정확한 GC ` 중 하나를 사용하여 .. _Boehm-Demers-Weiser conservative garbage collector: http://hboehm.info/gc/ 거의 모든 애플리케이션 수준의 Python 코드는 매우 빠른 속도로 객체를 할당합니다. 이는 메모리 관리 구현이 PyPy 인터프리터의 성능에 결정적이라는 것을 의미합니다. .. _genc: C 백엔드 -------- :source:`rpython/translator/c/` 이는 현재 유일한 코드 생성 백엔드입니다. 역사적 참고 사항 ---------------- 이 문서에서 보여주었듯이, 번역(translation) 단계는 처음에 예상했을 법한 것보다 더 많은 단계로 나뉘어 있습니다. 프로젝트가 시작될 당시 예상했던 것보다 확실히 더 많은 단계로 나뉘어 있습니다. GenC의 최초 버전은 고수준 흐름 그래프(flow graph)와 애노테이터(annotator)의 출력을 대상으로 동작했으며, RTyper라는 개념조차 아직 존재하지 않았습니다. 최근 들어서는, 소스 생성을 위해 그래프를 준비하는 것("데이터베이스화")과 실제로 소스를 생성하는 것을 별도로 고려하는 편이 낫다는 사실이 분명해졌습니다. 어떻게 맞물려 동작하는가 ------------------------ 지금까지 살펴본 바와 같이, PyPy의 번역(translation) 툴체인은 여러 개별 구성 요소로 이루어진 유연하면서도 복잡한 존재입니다. .. digraph:: translation graph [fontname = "Sans-Serif", size="6.00"] node [fontname = "Sans-Serif"] edge [fontname = "Sans-Serif"] subgraph legend { "입력 또는 출력" [shape=ellipse, style=filled] "변환 단계" [shape=box, style="rounded,filled"] // 수직으로 배치되도록 하기 위한 보이지 않는 엣지 "입력 또는 출력" -> "변환 단계" [style=invis] } "입력 프로그램" [shape=ellipse] "흐름 분석" [shape=box, style=rounded] "Annotator" [shape=box, style=rounded] "RTyper" [shape=box, style=rounded] "백엔드 최적화 (선택 사항)" [shape=box, style=rounded] "예외 변환기" [shape=box, style=rounded] "GC 변환기" [shape=box, style=rounded] "GenC" [shape=box, style=rounded] "ANSI C 코드" [shape=ellipse] "입력 프로그램" -> "흐름 분석" -> "애노테이터" -> "RTyper" -> "백엔드 최적화 (선택 사항)" -> "예외 변환기" -> "GC 변환기" "RTyper" -> "예외 변환기" [style=dotted] "GC 변환기" -> "GenC" -> "ANSI C 코드" // "GC 변환기" -> "GenLLVM" -> "LLVM IR" 아직 강조되지 않은 세부 사항 하나는 여러 구성 요소 간의 상호작용입니다. 어노테이터가 작업을 마친 후 RTyper가 그래프를 처리하고, 그다음 예외 처리가 명시적으로 이루어지는 식이라고 말하면 발표하기에는 그럴듯하지만, 완전한 사실은 아닙니다. 예를 들어 RTyper는 먼저 annotate되어야 하는 많은 :term:`저수준 헬퍼`\ 에 대한 호출을 삽입하며, GC 트랜스포머는 성능을 향상시키기 위해 자신의 작은 헬퍼 함수 일부에 인라이닝(`백엔드 최적화`_ 중 하나)을 사용할 수 있습니다. 다음 그림은 기본 번역(translation) 과정의 각 단계를 수행하는 데 관련된 구성 요소를 요약하려고 합니다: .. image:: _static/translation-detail-0.9.png :align: center 앞서 언급하지 않은 구성 요소로 "MixLevelAnnotator"가 있습니다. 이는 "늦은"(RTyping 이후) 번역(translation) 단계에서, (서로 상호 재귀적으로 참조할 수 있는) 함수들의 집합 각각을 호출할 수 있어야 한다고 선언하고 이들을 한꺼번에 annotate 및 rtype할 수 있도록 편리한 인터페이스를 제공합니다.