트레이스 옵티마이저

사용자 프로그램의 트레이스는 기계어 코드로 바로 변환되지 않습니다. 옵티마이저 모듈은 의미론을 보존하는 여러 가지 변환을 구현합니다. 이 변환들은 연산을 트레이스에서 제거하거나, 시간이나 공간을 덜 차지하는 연산으로 바꿉니다.

옵티마이저는 rpython/jit/metainterp/optimizeopt/에 있습니다. 이 모듈을 이해하려고 할 때 이 페이지로 시작하면 도움이 될 것입니다.

몇 가지 최적화를 더 자세히 설명하기 전에, 먼저 트레이스가 어떤 모습인지 이해해야 합니다. 옵티마이저에는 테스트 스위트가 함께 제공됩니다. 테스트 스위트에는 트레이스 예제가 많이 들어 있으므로 한번 살펴보시기 바랍니다(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)

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

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에 디스크립터로 추가합니다. 물론 옵티마이저도 런타임에 같은 작업을 수행하지만, 실제 값을 사용합니다. 예제 트레이스에는 getarrayitem_raw에 디스크립터가 포함되어 있습니다. 여기서 디스크립터는 배열의 타입을 나타냅니다. 이 배열은 부호 있는 정수 배열입니다.

상위 수준 개요

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

최적화는 정해진 순서에 따라 하나씩 차례로 적용되며, 기본 순서는 다음과 같습니다:

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

콜론으로 구분된 각 이름에는 Optimization 클래스를 상속하는 클래스가 하나씩 연결되어 있습니다. Optimizer 클래스 자체도 Optimization 클래스를 상속하며, 최적화를 위한 제어 로직을 구현합니다. 대부분의 최적화는 단 한 번의 순방향 패스만 필요로 합니다. 트레이스는 propagate_forward 메서드를 통해 각 최적화로 ‘전파’됩니다. 트레이스는 명령어 단위로 첫 번째 최적화에서 마지막 최적화까지 흘러갑니다. 다음 옵티마이저로 전달되는 모든 연산에 대해 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

인자까지 매칭하기 시작하면 상황은 더 나빠집니다(첫 번째 인자가 상수이고 두 번째 인자가 변수입니까, 아니면 그 반대입니까?). 이러한 코드 비대화를 해결하는 패턴은 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’라고 하며, 흔히 강도 감소(strength reduction)라고도 합니다. 간단한 예로, 정수에 2를 곱하는 것은 비트를 왼쪽으로 한 번 시프트하는 것과 같습니다(예: x * 2 == x << 1). 이 최적화에서는 강도 감소뿐만 아니라 불리언 단순화나 산술 단순화도 수행합니다. 다른 예로는 x & 0 == 0, x - 0 == x 등이 있습니다.

이러한 연산을 만날 때마다(예: y = x & 0) 연산을 내보내지 않습니다. 대신 변수 y를 0과 같게 만듭니다(= make_constant_int(op, 0)). 트레이스에 나오는 변수는 rpython/jit/metainterp/history.py에 있는 클래스의 인스턴스입니다. 어떤 값을 다른 값과 같게 만들면, 그 값의 박스가 다른 값을 가리키게 됩니다.

순수 최적화

기본 옵티마이저에 함께 엮여 있는 ‘pure’ 최적화입니다. 이 최적화는 순수한 의미론을 갖는 것으로 알려진 연산, 결과, 인자를 저장합니다.

여기서 “순수(pure)”는 jit.elidable 데코레이터와 같은 의미입니다. 즉 “관찰 가능한” 부수 효과가 없고 참조 투명하다는 뜻입니다(프로그램의 의미론을 바꾸지 않고 연산을 그 결과로 대체할 수 있습니다). resoperation.py에서 ALWAYS_PURE로 표시된 연산은 NOSIDEEFFECT 연산의 부분집합입니다. new, new array, getfield_(raw/gc) 같은 연산은 NOSIDEEFFECT로 표시되어 있지만 ALWAYS_PURE로는 표시되어 있지 않습니다.

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

언롤 최적화

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

이 최적화는 순방향 패스를 한 번만 수행하는 전통적인 방식에 속하지 않습니다. 간단히 말해, 이 최적화는 트레이스를 한 번 언롤(unroll)하고, (벗겨낸(peeled) 트레이스의 jump와 label에 매개변수를 삽입하여) 두 트레이스를 연결한 뒤, 그 정보를 활용하여 할당을 제거하고, 상수를 전파하며, 현재 ‘optimizeopt’ 모듈에 있는 그 밖의 모든 최적화를 수행합니다.

이것은 모든 최적화 앞에 추가되므로 옵티마이저(Optimizer) 클래스를 확장하며, 진행하기 전에 루프를 한 번 펼칩니다.

벡터화

이 문서에서 다루지 않는 내용

  • 가드(guard)에 대한 설명이 없습니다
  • 몇 가지 최적화는 설명되어 있지 않습니다