GCC의 switch 문 컴파일 전략: 점프 테이블·비트셋·결정 트리

핵심 요약

• GCC는 switch 문을 세 가지 방식으로 변환한다: 점프 테이블, 비트셋 테스트, 비교 트리이며, 어느 전략을 쓸지는 사건의 밀도와 개수에 따라 결정된다.
• 점프 테이블은 사건이 조밀할 때(입력값 8개당 사건 레이블 1개 이상) 사용되며, 함수 포인터 배열처럼 동작하여 빠른 디스패치를 가능하게 한다.
• GCC는 연속된 사건들을 묶어서 처리하며, 점프 테이블 크기가 '비교 횟수 × 8'을다면 비용-효율적이라고 판단한다(크기 최적화 시에는 × 2).
• 비트셋 클러스터는 ASCII 값처럼 특정 범위의 사건을 비트마스크로 변환하는 기법으로, bt 명령어로 한 번에 여러 경우를 검사할 수 있다.
• 비트셋 생성은 동적 프로그래밍으로 필요한 비트셋의 최소 개수를 먼저 찾은 뒤, is_beneficial 휴리스틱으로 실제 유익성을 재검토하여 필터링한다.
• 점프 테이블 변환도 동적 프로그래밍을 쓰며, 점프 테이블의 오버헤드(간접 점프·경계 검사)를 고려해 최소 5개 사건 이상일 때만 생성하도록 제약한다.
• 점프 테이블과 비트셋으로 처리되지 않은 사건들은 이진 트리 구조의 비교 계단으로 변환되며, 프로파일 유도 최적화로 얻은 확률을 바탕으로 균형잡힌 트리를 구성한다.
• GCC의 pass_lower_switch 패스가 analyze_switch_statement 함수를 호출하여 사건을 simple_cluster로 변환한 뒤, bit_test_cluster와 jump table 변환을 시도하고 남은 것들을 결정 트리로 처리한다.
• 스피드 최적화(-O1/O2/O3/Ofast)와 크기 최적화(-Os)에서 사용하는 점프 테이블 크기 비율이 다르며, 이는 컴파일러가 최적화 목표에 맞춰 변환 전략을 선택함을 의미한다.