.. _trace_optimizer:

트레이스 최적화기
=================

사용자 프로그램의 트레이스는 기계어로 직접 번역되지 않습니다. 옵티마이저 모듈은 연산을 트레이스에서 제거할 수 있게 하거나 시간이나 공간이 덜 필요한 연산으로 변환하는, 의미를 보존하는 여러 가지 변환을 구현합니다.

옵티마이저는 `rpython/jit/metainterp/optimizeopt/`\ 에 있습니다. 이 모듈을 이해하려고 할 때, 이 페이지가 도움이 될 수 있습니다.

몇몇 최적화를 더 자세히 설명하기 전에, 트레이스가 어떤 모습인지 이해하는 것이 필수적입니다. 최적화기(optimizer)는 테스트 스위트와 함께 제공됩니다. 여기에는 많은 트레이스 예제가 포함되어 있으며, (`rpython/jit/metainterp/optimizeopt/test/*.py`\ 에서) 한번 살펴보실 만합니다. 허용된 연산은 `rpython/jit/metainterp/resoperation.py`\ 에서 찾을 수 있습니다. 다음은 트레이스의 예시입니다::

    [p0,i0,i1]
    label(p0, i0, i1)
    i2 = getarrayitem_raw(p0, i0, descr=<Array Signed>)
    i3 = int_add(i1,i2)
    i4 = int_add(i0,1)
    i5 = int_le(i4, 100) # lower-or-equal
    guard_true(i5)
    jump(p0, i4, i3)

처음에는 읽기가 어색할 수 있지만, 트레이스를 구성한 파이썬 코드와 비교하기 시작하면 이해가 됩니다::

    from array import array
    a = array('i', range(101))
    sum = 0; i = 0
    while i <= 100: # can be seen as label
        sum += a[i]
        i += 1
        # jumps back to the while header

물론 ``[0..100]``\ 의 합을 계산하는 더 나은 방법들도 있지만, 이 예제는 ``sum(range(101))``\ 보다 트레이스가 어떻게 구성되는지에 대해 더 나은 직관을 제공합니다. 트레이스 구문은 테스트 스위트에서 사용되는 것과 동일하다는 점에 유의하십시오. 또한 :doc:`PYPYLOG <../logging>`\ 가 런타임에 출력하는 트레이스와도 매우 유사합니다. 첫 번째 줄은 입력 변수들을 제공하고, 두 번째 줄은 ``label`` 연산이며, 마지막 줄은 역방향 ``jump`` 연산입니다.

앞서 언급한 이 지침들은 특별합니다:

* 입력(input)은 트레이스에 진입하는 입력 매개변수의 유형과 이름을 정의합니다.
* ``label``\ 은 ``jump``\ 가 대상으로 삼을 수 있는 명령입니다. 레이블 명령어에는 레이블을 고유하게 식별하는 ``JitCellToken``\ 이 연관되어 있습니다. 모든 점프는 레이블의 대상 토큰을 가집니다.

토큰은 명령어의 이른바 `descriptor`\ 에 저장됩니다. 테스트에서도 마찬가지로 하지 않기 때문에 명시적으로 작성되지 않습니다. 하지만 테스트 스위트는 각 트레이스마다 더미 토큰을 생성하여 ``label``\ 과 ``jump``\ 에 descriptor로 추가합니다. 물론 옵티마이저도 런타임에 동일한 작업을 수행하지만, 실제 값을 사용합니다. 샘플 트레이스는 ``getarrayitem_raw``\ 에 descriptor를 포함합니다. 여기서 이는 배열의 타입을 나타냅니다. 이는 부호 있는 정수 배열입니다.

상위 수준 개요
--------------

JIT 백엔드가 트레이스를 머신 코드로 변환하기 전에, 먼저 그 트레이스를 더 빠르게 실행되는 동등한 트레이스로 변환하려고 시도합니다. `rpython/jit/metainterp/optimizeopt/__init__.py`\ 의 `optimize_trace` 메서드가 주된 진입점입니다.

최적화는 순서대로 하나씩 적용되며, 기본 순서는 다음과 같습니다::

    intbounds:rewrite:virtualize:string:earlyforce:pure:heap:unroll

콜론으로 구분된 각 이름에는 `Optimization` 클래스를 상속하는 클래스가 연결되어 있습니다. `Optimizer` 클래스 자체도 `Optimization` 클래스를 상속하며, 최적화를 위한 제어 로직을 구현합니다. 대부분의 최적화는 단 한 번의 정방향 패스만 필요로 합니다. 트레이스는 `propagate_forward` 메서드를 사용하여 각 최적화로 '전파(propagate)'됩니다. 명령어 단위로, 첫 번째 최적화에서 마지막 최적화까지 흘러갑니다. 다음 옵티마이저로 전달되는 모든 연산에 대해 `emit_operation` 메서드가 호출됩니다.

intbounds 최적화(주로 정수 연산 최적화와 관련된 것)는 대체로 :doc:`규칙 기반 패턴 매칭 DSL <ruleopt>`\ 로 구현되어 있습니다.

자주 마주치는 패턴
------------------

잠재적인 최적화 대상을 찾으려면 명령어 유형을 알아야 합니다. 간단한 해결책은 연산 번호(= 유형)를 사용해 분기하는 것입니다.::

    for op in operations:
        if op.getopnum() == rop.INT_ADD:
            # handle this instruction
            pass
        elif op.getopnum() == rop.INT_FLOOR_DIV:
            pass
        # and many more

인자를 매칭하기 시작하면 상황은 더 나빠집니다(첫 번째 인자가 상수이고 두 번째가 변수인지, 아니면 그 반대인지?). 이러한 코드 비대화(code bloat)에 대처하는 패턴은 `make_dispatcher_method`\ 를 사용하여 별도의 메서드로 옮기는 것입니다. 이는 메서드를 명령어 유형과 연결합니다.::

    class OptX(Optimization):
        def prefix_INT_ADD(self, op):
            pass # emit, transform, ...

    dispatch_opt = make_dispatcher_method(OptX, 'prefix_',
                                          default=OptX.emit_operation)
    OptX.propagate_forward = dispatch_opt

    optX = OptX()
    for op in operations:
        optX.propagate_forward(op)

``propagate_forward``\ 는 해당 명령어 타입을 처리할 수 있는 메서드를 검색합니다. 예를 들어 `INT_ADD`\ 는 `prefix_INT_ADD`\ 를 호출합니다. 해당 명령어에 대한 함수가 없으면 기본 구현(이 예제에서는 ``emit_operation``)으로 전달됩니다.

재작성(Rewrite) 최적화
----------------------

두 번째 최적화는 'rewrite'라고 불리며, 흔히 강도 감소(strength reduction)라고도 알려져 있습니다. 간단한 예로 정수에 2를 곱하는 것은 비트를 한 번 왼쪽으로 시프트하는 것과 동일합니다(예: ``x * 2 == x << 1``). 이 최적화에서는 강도 감소뿐만 아니라 불리언(boolean) 또는 산술 단순화도 수행됩니다. 다른 예로는 ``x & 0 == 0``, ``x - 0 == x`` 등이 있습니다.

이러한 연산이 발견될 때마다(예: ``y = x & 0``), 어떤 연산도 방출되지 않습니다. 대신 변수 y는 0과 같아집니다(= ``make_constant_int(op, 0)``). 트레이스에서 발견되는 변수들은 `rpython/jit/metainterp/history.py`\ 에서 찾을 수 있는 클래스의 인스턴스입니다. 어떤 값이 다른 값과 같아지면, 그 box는 다른 값을 가리키도록 만들어집니다.


순수 최적화
-----------

기본 최적화기에 엮여 있는 '순수' 최적화입니다. 순수 의미를 갖는 것으로 알려진 연산, 결과, 인자를 저장합니다.

여기서 "순수"(pure)는 ``jit.elidable`` 데코레이터와 동일한 의미로, "관찰 가능한"(observable) 부작용이 없고 참조 투명(referentially transparent)함을 뜻합니다(해당 연산은 프로그램 의미론을 변경하지 않고 그 결과값으로 대체될 수 있습니다). `resoperation.py`\ 에서 ALWAYS_PURE로 표시된 연산들은 NOSIDEEFFECT 연산의 부분집합입니다. new, new array, getfield_(raw/gc) 같은 연산들은 NOSIDEEFFECT로 표시되어 있지만 ALWAYS_PURE로는 표시되어 있지 않습니다.

순수 연산은 두 가지 방식으로 최적화됩니다. 인자가 상수이면 해당 연산은 제거되고 결과는 상수로 바뀝니다. 그렇지 않은 경우에도 메모이제이션 기법을 사용할 수 있습니다. 이후에 같은 인자에 대해 같은 연산을 다시 만나면, 결과를 다시 계산할 필요 없이 이전 연산의 결과를 그대로 재사용하면 됩니다.

언롤 최적화(Unroll optimization)
--------------------------------

자세한 설명은 `Loop-Aware Optimizations in PyPy's Tracing JIT`__ 문서에서 찾을 수 있습니다.

.. __: http://www2.maths.lth.se/matematiklth/vision/publdb/reports/pdf/ardo-bolz-etal-dls-12.pdf

이 최적화는 단일 순방향 패스만 수행하는 전통적인 방식에 속하지 않습니다. 요약하면, 이 최적화는 트레이스를 한 번 언롤(unroll)하고, (벗겨진(peeled) 트레이스의 점프(jump)와 레이블(label)에 매개변수를 삽입하여) 두 트레이스를 연결하며, 정보를 활용해 할당(allocation)을 정리하고 상수를 전파하며, 현재 'optimizeopt' 모듈에 있는 다른 모든 최적화를 수행합니다.

이는 모든 최적화 앞에 붙기 때문에 Optimizer 클래스를 확장하며, 진행하기 전에 루프를 한 번 언롤(unroll)합니다.

벡터화(Vectorization)
---------------------

- :doc:`벡터화(Vectorization) <vectorization>`

이 문서에서 빠진 내용
---------------------

* 가드(guard)는 설명되지 않습니다
* 몇 가지 최적화 기법은 설명되어 있지 않습니다


추가 참고 자료
--------------

* `Allocation Removal by Partial Evaluation in a Tracing JIT`__
* `PyPy의 트레이싱 JIT에서의 루프 인지 최적화`__

.. __: http://www.stups.uni-duesseldorf.de/mediawiki/images/b/b0/Pub-BoCuFiLePeRi2011.pdf
.. __: http://www2.maths.lth.se/matematiklth/vision/publdb/reports/pdf/ardo-bolz-etal-dls-12.pdf