비트 출처 분석으로 긴 비트 연산열을 줄인다

비트 출처 분석은 각 비트가 어떤 입력 비트에서 왔는지 추적해, 여러 연산을 거친 뒤에도 같은 값이나 단순한 시프트로 되돌릴 수 있는지 찾아낸다. PyPy의 기존 비트 상수 분석이 파악하지 못하는 비트 이동 관계를 이용해, 개별 연산 조합마다 규칙을 만들지 않고도 최적화하는 방법이다.

예를 들어 x에서 하위 4비트를 마스킹한 값과, x를 60비트 왼쪽으로 옮겼다가 논리적으로 오른쪽으로 60비트 옮긴 값을 비교하면 두 값은 같다. 비트 출처 분석은 각 비트의 출처를 기록해 이 관계를 찾아내고, 마지막 AND 연산을 이미 계산된 값으로 대체한다. 기존 Knownbits 장난감 추상 도메인은 각 비트가 0인지 1인지, 또는 알 수 없는지만 기록하지만, 새 방식은 서로 다른 변수의 비트가 같은 원본 비트인지도 추적한다.

이 분석은 64비트 값의 비트를 상수 0·1 또는 원본 비트에 연결해 표현한다. 상수 시프트는 비트 위치를 옮기고, 가변 시프트는 결과를 알 수 없는 값으로 취급한다. AND·OR·XOR와 비트 반전도 비트 단위로 처리한다. 분석 결과가 상수면 상수로 바꾸고, 앞서 계산한 값과 같으면 재사용하며, 특정 출처의 단순 시프트로 표현할 수 있으면 그 연산으로 대체한다. 이 방식은 국소 피프홀 재작성 규칙을 조합별로 계속 추가하는 대신, 비트의 출처 정보로 긴 연산열을 다룬다.

실험 결과와 적용 범위

글에 소개된 실험은 최적화를 PyPy JIT에 직접 넣지 않고, RPython JIT 로그를 읽어 처리하는 외부 패스로 수행했다. 비교 대상은 PyPy 번역기와 Sail 기반 RISC-V 시뮬레이터인 Pydrofoil이며, 두 작업의 정수 연산만 남긴 추적을 기준으로 삼았다. 프로토타입에는 산술 오른쪽 시프트와 부호 확장 등도 추가됐고, 원본 입력뿐 아니라 앞서 계산한 값의 시프트도 추출할 수 있었다. 모든 경로에 최적화 뒤 죽은 코드 제거를 적용했다.

Pydrofoil에서는 RPython 최적화 뒤에도 비트 출처 분석이 연산을 더 줄였지만, 이 효과가 전체 JIT 최적화 과정에서도 이어지는지는 추가 조사가 필요하다고 글은 설명한다. PyPy 작업에서는 RPython 정수 최적화를 먼저 적용한 뒤 비트 출처 분석으로 줄어든 연산이 없었다. 따라서 이 수치는 제한된 실험의 결과이며, 실제 JIT 전체 과정에서의 이점을 입증한 것은 아니다.

글은 이 방식의 의의가 기존 최적화를 이겼다는 데 있기보다, 적은 수의 전달 함수로 다양한 비트 연산 재작성을 찾아낸다는 데 있다고 정리한다. 예시에는 두 번의 바이트 순서 뒤집기와, 비트 반전·시프트 조합을 단순 시프트로 줄이는 경우가 포함된다. 전체 코드는 gist에서 볼 수 있다.