GCC는 switch문을 비트 검사·점프 테이블·비교 트리로 조합합니다

본문

GCC는 switch문을 점프 테이블, 비트 검사, 비교 트리 가운데 하나로만 처리하지 않습니다. 2024년 1월 14일 공개된 분석 글은 GCC가 case 값의 범위와 밀도, 각 case가 이어지는 실행 경로를 살펴 여러 방식을 한 switch문 안에서도 조합한다고 설명합니다. 예를 들어 1부터 5까지는 점프 테이블로 처리하고 멀리 떨어진 100은 별도 분기로 남길 수 있습니다.

점프 테이블은 입력값을 인덱스로 삼아 분기 대상을 찾습니다. 값이 드물게 흩어져 있으면 실제 case가 없는 칸도 테이블에 생깁니다. GCC는 연속된 case 범위를 먼저 묶어 필요한 비교 횟수를 계산한 뒤 테이블 후보를 검토합니다. 글이 살펴본 휴리스틱에서는 속도 최적화 시 테이블 항목 수와 비교 횟수의 비율 기준으로 8을, 크기 최적화(-Os) 시 2를 사용합니다. 글은 이 기준 외에도 작은 테이블을 걸러내는 최소 크기 조건이 있으며, 현대 x64와 Arm64에서는 그 기본값이 5라고 설명합니다.

GCC는 점프 테이블을 검토하기 전에 case들을 비트 검사로 묶을 수 있는지도 살펴봅니다. 비트 검사는 정수의 각 비트를 case 값에 대응시켜 해당 값인지 판별합니다. 글에서 분석한 구현은 case 값의 전체 범위가 레지스터 폭보다 작고, 서로 다른 실행 경로가 세 개 이내인 경우를 후보로 삼습니다. 한 실행 경로로 이어지는 case가 충분하면 비트 검사로 바꾸며, 나머지 case는 점프 테이블 후보로 넘깁니다.

변환되지 않은 case는 비교 트리로 처리합니다. GCC는 분기 확률 정보가 있으면 그 정보를 트리 구성에 반영합니다. 글의 예제는 -O3를 사용했지만 GCC 버전과 세부 타깃 설정은 밝히지 않았으므로, 8과 2 같은 수치는 해당 글이 분석한 조건의 휴리스틱으로 읽어야 합니다.

자료: Xoranth / 정리·해설: Trawling

참고 자료

• gcc/gcc/tree-switch-conversion.cc at master · gcc-mirror/gcc · GitHub — https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-switch-conversion.cc