PyPy의 어셈블러 백엔드¶

2016년 PyPy JIT의 어셈블러 백엔드 구성에 관한 초안 노트¶

입력: “트레이스(trace)”라고 부르는 선형 명령어 시퀀스입니다.

트레이스는 SSA 형식의 명령어 시퀀스입니다. 대부분의 명령어는 CPU 수준 명령어 하나 또는 몇 개에 대응합니다. label과 디버깅용 명령어 같은 몇 가지 메타 명령어도 있습니다. 모든 분기는 가드(guard)로 이루어집니다. 가드(guard)는 조건이 참인지 검사하고 참이 아니면 트레이스를 빠져나가는 명령어입니다. 실패하는 가드(guard)에는 나중에 “브리지(bridge)”라고 부르는 새 트레이스를 덧붙일 수 있습니다. 패치된 가드(guard)는 브리지로 곧장 이동하는 Jcond 명령어가 되며, 간접 참조나 레지스터 스필링 같은 것이 전혀 없습니다.

트레이스는 return이나 jump to label로 끝납니다. 대상 레이블은 같은 트레이스 안에 있거나, 그보다 오래된 트레이스 안에 있습니다. 역사적인 이유로, 브리지가 아닌 트레이스를 “루프”라고 부릅니다. 우리가 생성하는 기계어 코드는 여러 트리로 이루어진 숲 형태로 구성됩니다. 트리의 줄기는 “루프”이고, 브랜치는 모두 브리지입니다(줄기나 다른 브랜치에서 갈라져 나온 것입니다).

jump to label로 끝나는 모든 트렁크나 브랜치 역시 다른 트리의 레이블을 대상으로 삼을 수 있습니다.
루프나 브랜치를 어셈블하는 전체 과정은 기본적으로 단일 스레드로 이루어지므로, 그 부분에서는 동기화 문제가 없습니다(이전에 생성된 명령어를 패치하는 경우도 포함합니다).
생성된 어셈블러 코드는 %rbp에 “프레임”을 두고 있습니다. 이 프레임은 사실 스택에 전혀 있지 않으며, (“jitframe”이라고 부르는) GC 객체입니다. 스필링(spilling)된 값은 그곳에 저장됩니다.
가드(guard)는 생성된 아주 작은 코드 조각으로 향하는 Jcond입니다. 이 코드는 기본적으로 스택에 상수 몇 개를 푸시한 다음 범용 가드(guard) 복구 코드로 점프합니다. 그 코드는 레지스터를 jitframe에 저장한 다음 생성된 함수 전체를 빠져나옵니다. 생성된 함수의 호출자는 함수가 어떻게 종료되었는지 확인합니다. 가드(guard)에 걸려 종료되었다면 호출자가 “블랙홀 인터프리터”를 호출할 책임을 집니다. 블랙홀 인터프리터는 실패한 가드(guard)에서 복구하고 프레임 실행을 마무리하는 프런트엔드 부분입니다(경우에 따라 생성된 어셈블러로 다시 점프하는 것도 포함합니다).

JIT 컴파일 과정에 대한 세부 사항은 다음과 같습니다:

프런트엔드와 최적화 패스
재작성 (가비지 컬렉션 관련 변환과 단순화 포함)
어셈블러 생성

프런트엔드와 최적화 패스¶

여기서는 자세히 다루지 않습니다. 이 단계는 어떤 의미에서 “고수준”인 명령어 집합을 사용하여 루프와 브리지를 생성합니다. 이 명령어 집합에는 “new”/”new_array” 같은 명령어와, 구조체나 배열의 정확한 필드에 값을 저장하는 동작을 기술하는 “setfield”/”setarrayitem”/”setinteriorfield” 같은 명령어가 포함됩니다. 예를 들어, “setfield” 동작에는 암묵적으로 GC 쓰기 배리어(write barrier)가 필요할 수 있습니다. 이것이 다음 단계로 보내는 고수준 트레이스입니다.

재작성¶

대부분 CPU에 독립적이지만 완전히 그렇지는 않은 단계로, 일부 명령어를 로어링합니다. 예를 들어 “new”의 여러 변형은 “malloc”과 몇 개의 “gc_store”로 로어링됩니다. 즉, GC의 포인터를 증가시킨 다음 새로 할당된 구조체의 몇몇 필드를 명시적으로 설정합니다. “setfield”는 필요한 경우 “cond_gc_wb_call”(쓰기 배리어에 대한 조건부 호출)로 대체되고, 그 뒤에 “gc_store”가 이어집니다.

“gc_store” 명령어는 MOV 어셈블러 명령어 하나로 인코딩할 수 있지만, MOV만큼 유연하지는 않습니다. 주소는 항상 “어떤 GC 포인터 + 오프셋” 형태로 지정됩니다. GC 객체에는 내부 포인터(interior pointer)라는 개념이 없습니다.

또 다른 명령어인 “gc_store_indexed”는 추가 피연산자를 제공하며, 이 피연산자는 [rax+8*rcx+24]와 같은 형태를 사용하여 단일 MOV 명령어로 매핑될 수 있습니다.

다른 몇몇 복잡한 명령어는 백엔드로 그대로 전달되며, 백엔드가 이를 처리해야 합니다. 예를 들어 GC의 “카드 마킹(card marking)”이 그렇습니다. (배열 안에 객체 포인터를 쓰면 나중에 “젊은(young)” 참조를 찾기 위해 배열 전체를 순회해야 합니다. 그렇게 하는 대신, 128개 항목 범위마다 비트 하나를 뒤집습니다. 이것은 흔히 쓰이는 GC 최적화입니다.) GC 객체의 카드 비트를 설정하려면 일련의 어셈블러 명령어가 필요한데, 이 명령어들은 대상 CPU에 너무 크게 의존하므로 여기서 명시적으로 표현할 수 없습니다(게다가 그 안에는 브랜치가 몇 개 있는데, 이는 이 수준에서 표현하기 어렵습니다).

어셈블리¶

화려한 코드 생성 기법은 쓰지 않지만, 몇 가지 함정을 피하려고 하는 탐욕적(greedy) 순방향 패스를 사용합니다

명령어 처리¶

명령어를 하나씩 정방향으로 처리합니다. 각 명령어는 레지스터 할당기(register allocator)에 일부 인자가 (jitframe이 아닌) 레지스터에 있도록 보장해 달라고 요청하고, 결과를 넣을 레지스터를 요청하며, 명령어가 끝날 때 해제될 추가 스크래치 레지스터를 요청합니다. 불리언 변수는 특별하게 처리합니다. 불리언 변수는 0/1 값으로 구체화(materialize)되는 대신 조건 코드 플래그에 저장됩니다. (불리언 변수는 나중에 구체화되지만, 바로 다음의 guard_false 또는 guard_true에서만 사용되고 그 뒤로는 버려지는 흔한 경우는 예외입니다.)
명령어 인자는 필요할 때 레지스터에 로드됩니다. 이 방식 덕분에 백엔드를 작성하기는 꽤 쉽지만, 몇 가지 좋지 않은 결정으로 이어집니다.

선형 스캔 레지스터 할당¶

우리가 다루는 것은 항상 선형 트레이스이지만, 레지스터 할당에 고급 기법을 사용하지는 않습니다. 백엔드가 어셈블러 코드를 생성하는 동안 앞에서부터 차례로, 필요할 때마다 할당합니다. 백엔드가 어떤 값을 넣을 레지스터를 요청하면, 그 레지스터가 이후에 어떻게 쓰일지는 고려하지 않고 비어 있는 레지스터를 아무것이나 내줍니다. 모든 변수의 수명을 계산하기는 하지만, 이 정보는 어떤 레지스터를 스필(spill)할지 고를 때만 사용합니다(수명이 가장 긴 변수를 스필합니다).

이 방식은 앞선 최적화 패스와 잘 통합되어 있기 때문에 어느 정도 효과가 있습니다. 더 강력한 최적화를 할 수 있도록 최적화 패스에서 루프를 한 번 펼칩니다(unroll). 이로써 가장 큰 이점을 얻는 곳은 최적화 패스 자체이지만, 여기 어셈블리 패스에서도 이점이 있습니다. 그 이점은 다음과 같습니다.

첫 번째 필링(peeling)은 처음 사용될 때 레지스터 바인딩을 초기화합니다.
이렇게 하면 트레이스 루프에서 이미 할당된 레지스터를 사용하게 됩니다.
브리지(bridge)를 빠져나갈 때 할당된 레지스터도 마찬가지입니다.

[ABI에 맞게 레지스터를 더 잘 할당하도록 시도합니다 (현재 상태에서는 이점이 미미하거나 없습니다)]

더 복잡한 매핑¶

일부 명령어는 더 복잡한 코드를 생성합니다. 이러한 명령어는 다음 중 하나 또는 둘 모두에 해당합니다:

“cond_gc_wb_call”(쓰기 배리어용), “call_assembler”(호출 뒤에 몇 가지 검사가 이어지는 명령어)처럼 일부 지역 제어 흐름을 생성하는 복잡한 명령어입니다.
쓰기 배리어(write barrier)의 슬로우 패스나 할당의 슬로우 패스처럼 커스텀 어셈블러 헬퍼를 호출하는 명령어입니다. 이러한 슬로우 패스도 보통 함께 생성되므로 일반적인 호출 규약(calling convention)에 얽매이지 않습니다.

GC 포인터¶

대부분의 CALL 명령어 주변에서는 GC 포인터가 어디에 있는지(레지스터와 스택 프레임)에 대한 설명을 기록해야 합니다. 이는 CALL이 가비지 컬렉션을 일으키는 경우에 대비하기 위해 필요합니다. GC 포인터는 이동할 수 있으며, 레지스터와 스택 프레임에 있는 포인터는 GC가 갱신합니다. 이것이 명시적인 내부 포인터(interior pointer)를 두지 않는 이유 중 하나입니다.

GC 포인터는 트레이스에 상수로 나타날 수 있습니다. 저희는 이를 상수 테이블과 MOV REG, (%RIP+offset)을 사용하도록 바꾸는 작업을 한창 진행하고 있습니다. 테이블에 있는 “상수”는 객체가 이동하면 실제로는 GC가 갱신합니다.

벡터화¶

트레이스 루프에 SIMD 명령어를 사용하기 위해 개발된 최적화입니다. 원래는 micro numpy의 최적화로 사용하려는 것이 주된 목적이었습니다. 이 최적화는 이미 최적화된 트레이스에 대해 여러 패스를 수행합니다.

간단히 설명하자면, 이 알고리즘은 펼쳐진(unrolled) 트레이스 루프의 의존성을 빌드하고, 병렬로 실행될 수 있는 연산의 쌍/묶음을 모은 다음, 마지막으로 연산을 스케줄링합니다.

코드베이스에 추가된 내용은 다음과 같습니다:

의존성을 구성할 수 있습니다
의존성 완화를 위한 가드(guard)의 코드 이동
트레이스를 재정렬하는 스케줄러
배열 경계 검사 제거(특히 언롤링된 트레이스의 경우)

할 수 있는 일:

벡터 루프 변환(요소별 연산)
누적(reduce([…],operator,0)). Operation이 결합 법칙과 교환 법칙을 만족해야 합니다
“벡터 백엔드”로서의 SSE 4.1

저희는 하지 않습니다¶

트레이스 트리를 재최적화할 수 있도록 트레이싱 데이터를 계속 보관하십시오. (현재는 트레이스가 컴파일되고 나면 최소한의 데이터만 보관됩니다.) 이것은 다음과 같은 결과가 나오는 이유 중 하나입니다(프런트엔드에도 다른 이유들이 있습니다). 자주 실행되는 경로가 두 개인 작은 루프를 JIT 컴파일하면 결국 “루프” 하나와 브리지 하나가 어셈블되며, 브리지를 따라가는 경로는 효율이 약간 떨어집니다. 이는 특히 이 브리지가 두 가지 제약 조건 아래에서 어셈블되기 때문입니다. 입력 레지스터는 (가드(guard)에 의해) 고정되어 있고, 출력 레지스터는 (점프 대상에 의해) 고정되어 있습니다. 보통 이 두 고정 레지스터 집합은 서로 다르므로 값을 이리저리 복사해야 합니다.
저희는 트레이스 꼬리(trace tail)를 이어 붙이지 않습니다. 오직 트리만 조립합니다.
저희는 어떠한 재배치도 하지 않습니다(트레이스 명령어도, 개별 어셈블러 명령어도 재배치하지 않습니다)
저희는 백엔드에서만 의미가 있고 더 높은 수준에서는 쉽게 표현할 수 없는 명령어 간 최적화를 전혀 수행하지 않습니다. 그런 예는 분명 무수히 많겠지만, 예를 들어 여러 명령어에 걸쳐 유지될 레지스터에 큰 상수를 적재하는 것, 주소 계산 같은 어떤 명령어의 일부를 루프 밖으로 옮기는 것 등등이 있습니다.
그 밖에 제가 생각할 수 있는 최적화 기회로는 함수 프롤로그/에필로그를 살펴보는 것과, 브리지(bridge) 시작 부분의 오버헤드(작지만 0은 아닌)를 살펴보는 것이 있습니다. 또한 가드(guard)가 구현된 방식이 타당한지도 확인해 보십시오. 또한 우리는 거의 분기하지 않는 Jcond 명령어가 잔뜩 들어간 꽤 긴 어셈블러 명령어 시퀀스를 생성하는데, 여기에 최적화 기회가 있겠습니까? (이것이 뭔가 달라지게 하는지는 모르겠지만, 이들은 모두 앞쪽으로 분기합니다.) 이론적으로는 이 중 일부를 세그폴트(segfault) 시그널 핸들러로 대체할 수도 있습니다(예: guard_nonnull_class).

GCC 또는 LLVM 백엔드입니까?¶

적어도 비교를 위해서라도 GCC나 LLVM을 사용해 코드를 생성하는 JIT 백엔드가 있으면 좋겠습니다(소요 시간과는 관계없이). 그러나 가드(guard)를 C 언어나 LLVM IR에 적절하게 대응시키기는 어렵습니다. 문제는 다음과 같습니다. (1) 가드(guard)가 많으므로, 아직 살아 있는 모든 지역 변수를 전부 저장하는 작업을 각각 수행하는 경로가 여러 개 생기는 것은 피하고 싶습니다. (2) 가드(guard)로부터 브리지가 컴파일될 때 그 가드(guard)를 패치하기 어렵습니다. (3) CALL 같은 명령어는 GC 포인터인 지역 변수를 노출해야 하며, CALL_MAY_FORCE는 필요할 때 인터프리터 상태를 오프라인에서 재구성할 수 있도록 모든 지역 변수를 노출해야 합니다.