PyPy의 어셈블러 백엔드¶

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

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

트레이스(trace)는 SSA 형식의 명령어 시퀀스입니다. 대부분의 명령어는 하나 또는 몇 개의 CPU 수준 명령어에 대응합니다. label과 같은 메타 명령어와 디버깅 관련 요소도 몇 가지 있습니다. 모든 분기는 가드(guard)로 이루어지며, 가드(guard)는 조건이 참인지 확인하고 참이 아니면 트레이스를 벗어나는 명령어입니다. 실패하는 가드(guard)에는 나중에 “브리지(bridge)”라고 불리는 새로운 트레이스가 추가될 수 있습니다. 패치된 가드(guard)는 간접 참조나 레지스터 스필링 등이 전혀 없이 브리지로 곧장 향하는 Jcond 명령어가 됩니다.

트레이스는 return이나 jump to label로 끝납니다. 대상 레이블은 동일한 트레이스 내부에 있거나, 더 오래된 트레이스 내부에 있습니다. 역사적인 이유로, 브리지가 아닌 트레이스를 “루프”라고 부릅니다. 우리가 생성하는 머신 코드는 나무들의 숲으로 구성됩니다. 나무의 줄기는 “루프”이고, 가지는 모두 브리지입니다(줄기에서 갈라지거나 다른 가지에서 갈라집니다).

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

JIT 처리 과정에 대한 세부 사항:

프론트엔드와 최적화 패스
재작성 (단순화뿐 아니라 GC 관련 변환도 포함합니다)
어셈블러 생성

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

여기서는 자세히 다루지 않습니다. 이는 어떤 의미에서 “고수준”인 명령어 집합을 사용하여 루프와 브리지를 생성합니다: 여기에는 “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에서의 “카드 마킹”이 그렇습니다. (배열 안에 객체 포인터를 기록하면 나중에 “young” 참조를 찾기 위해 배열 전체를 훑어야 합니다. 그 대신, 128개 항목 범위마다 비트 하나를 뒤집습니다. 이는 흔히 쓰이는 GC 최적화 기법입니다.) GC 객체의 카드 비트를 설정하려면 일련의 어셈블러 명령어가 필요한데, 이는 대상 CPU에 지나치게 의존적이어서 여기서 명시적으로 표현할 수 없습니다(게다가 이 명령어에는 이 수준에서 표현하기 어려운 몇 가지 분기도 포함되어 있습니다).

어셈블리¶

정교한 코드 생성 기법이 아니라, 몇 가지 함정을 피하려 시도하는 탐욕적(greedy) 순방향 패스입니다.

명령어 처리¶

하나씩(정방향). 각 명령어는 레지스터 할당자(register allocator)에게 일부 인자가 (jitframe이 아니라) 레지스터에 있도록 보장할 것을 요청하고, 결과를 넣을 레지스터를 요청하며, 명령어 끝에서 해제될 추가 스크래치 레지스터를 요청합니다. 불리언(boolean) 변수에는 특별한 경우가 있습니다: 이들은 0/1 값으로 구체화(materialize)되는 대신 조건 코드 플래그에 저장됩니다. (다음 guard_false나 guard_true에서만 사용된 후 잊히는 일반적인 경우를 제외하면, 이들은 나중에 구체화됩니다.)
명령어 인자는 필요할 때 레지스터에 로드됩니다. 이는 백엔드를 작성하기 매우 쉽게 만들지만, 몇 가지 잘못된 결정으로 이어집니다.

선형 스캔 레지스터 할당¶

우리가 고려하는 것은 항상 선형 트레이스이지만, 레지스터 할당에는 고급 기법을 사용하지 않습니다: 백엔드가 어셈블러를 생성함에 따라 전방으로, 필요할 때마다 할당을 수행합니다. 어떤 값을 담을 레지스터를 요청하면, 나중에 그 값으로 무엇을 할지는 고려하지 않고 비어 있는 레지스터 중 아무거나 내줍니다. 모든 변수의 수명을 계산하지만, 이는 어떤 레지스터를 스필(spill)할지 선택할 때만 사용합니다(수명이 가장 긴 변수를 스필합니다).

이는 이전 최적화 패스와 잘 통합되어 있기 때문에 어느 정도 효과가 있습니다. 루프는 더 강력한 최적화를 가능하게 하기 위해 최적화 패스에 의해 한 번 언롤링되는데, 최적화 패스 자체가 가장 큰 이득을 보는 지점이지만 어셈블리 패스에서도 여기서 이점을 얻습니다. 그 이점은 다음과 같습니다:

첫 번째 필링(peeling)은 첫 사용 시 레지스터 바인딩을 초기화합니다.
이는 트레이스 루프의 이미 할당된 레지스터로 이어집니다.
브리지(bridge)를 벗어날 때 할당된 레지스터도 마찬가지입니다.

[ABI에 맞춰 레지스터를 더 잘 할당해 보십시오 (현재 상태에서는 이득이 적거나 없습니다)]

더 복잡한 매핑¶

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

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

GC 포인터¶

대부분의 CALL 명령어 주위에서는 GC 포인터가 어디에 있는지(레지스터와 스택 프레임)에 대한 설명을 기록해야 합니다. 이는 CALL이 가비지 컬렉션을 호출하는 경우에 대비해 필요합니다. GC 포인터는 이동할 수 있습니다. 레지스터와 스택 프레임에 있는 포인터는 GC에 의해 갱신됩니다. 그것이 바로 명시적인 내부 포인터를 두지 않는 이유입니다.

GC 포인터는 트레이스에서 상수로 나타날 수 있습니다. 저희는 이를 상수 테이블과 MOV REG, (%RIP+offset)을 사용하는 방식으로 바쁘게 변경하는 중입니다. 테이블의 “상수”는 객체가 이동하면 실제로는 GC가 갱신합니다.

벡터화¶

트레이스 루프에 SIMD 명령어를 사용하기 위해 개발된 최적화입니다. 주된 아이디어는 이를 micro numpy의 최적화로 사용하는 것이었습니다. 이미 최적화된 트레이스에 대해 여러 패스를 가지고 있습니다.

간단히 설명하면, 펼쳐진(unrolled) 트레이스 루프에 대한 의존성을 구성하여 병렬로 실행될 수 있는 연산의 쌍/묶음을 수집한 다음 최종적으로 연산을 스케줄링합니다.

이것이 코드베이스에 추가한 것은 다음과 같습니다:

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

할 수 있는 일:

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

저희는 하지 않습니다¶

트레이스 트리를 재최적화하기 위해 트레이싱 데이터를 유지합니다. (트레이스가 컴파일되면 최소한의 데이터만 유지됩니다.) 이는 다음 결과가 나타나는 한 가지 이유입니다(프론트엔드에도 다른 이유들이 있습니다): 두 개의 공통 경로를 가진 작은 루프를 JIT 컴파일하면 결국 하나의 “루프”와 하나의 브리지(bridge)로 어셈블되며, 브리지를 따르는 경로가 약간 덜 효율적입니다. 이는 특히 이 브리지가 두 가지 제약 조건과 함께 어셈블되기 때문입니다: 입력 레지스터는 (가드(guard)로부터) 고정되고, 출력 레지스터는 (점프 대상으로부터) 고정됩니다. 보통 이 두 고정 레지스터 집합은 서로 다르므로 복사 작업이 필요합니다.
저희는 트레이스(trace) 끝을 연결하지 않습니다: 오직 트리(tree)만 조립합니다.
우리는 재정렬을 전혀 수행하지 않습니다(트레이스 명령어 재정렬도, 개별 어셈블리 명령어 재정렬도 하지 않습니다)
저희는 백엔드에서만 의미가 있고 상위 레벨에서는 쉽게 표현할 수 없는 명령어 간 최적화는 전혀 수행하지 않습니다. 그런 예는 분명 많이 있을 텐데, 예를 들어 여러 명령어에 걸쳐 살아남을 큰 상수를 레지스터에 적재하는 것, 주소 계산과 같은 특정 명령어의 일부를 루프 밖으로 옮기는 것 등이 있습니다.
제가 생각할 수 있는 다른 최적화 기회로는 함수 프롤로그/에필로그를 살펴보는 것과, 브리지(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는 인터프리터 상태의 선택적 오프라인 재구성을 위해 모든 지역 변수를 노출해야 합니다.