트레이스 최적화기

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

옵티마이저는 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))보다 트레이스가 어떻게 구성되는지에 대해 더 나은 직관을 제공합니다. 트레이스 구문은 테스트 스위트에서 사용되는 것과 동일하다는 점에 유의하십시오. 또한 PYPYLOG가 런타임에 출력하는 트레이스와도 매우 유사합니다. 첫 번째 줄은 입력 변수들을 제공하고, 두 번째 줄은 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 최적화(주로 정수 연산 최적화와 관련된 것)는 대체로 규칙 기반 패턴 매칭 DSL로 구현되어 있습니다.

자주 마주치는 패턴

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

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 문서에서 찾을 수 있습니다.

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

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

벡터화(Vectorization)

이 문서에서 빠진 내용

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