GCC가 switch를 저수준 코드로 변환하는 방법

GCC는 switch를 비트셋, 점프 테이블, 비교 트리로 변환하며, 하나의 switch 안에서도 구간별로 서로 다른 전략을 조합함 점프 테이블이 유리한지는 단순한 case 개수가 아니라 필요한 비교 횟수 대비 테이블 크기로 판단하며, 속도 최적화와 크기 최적화에 서로 다른 기준을 적용함 같은 코드로 분기하는 연속된 case는 범위 비교로 합쳐지고, 불연속 값도 범위와 분기 목적지 수가 조건을 충족하면 비트 테스트로 처리할 수 있음 비트셋과 점프 테이블 후보는 동적 계획법으로 묶은 뒤 이득 여부를 검사하며, 변환하지 못한 부분은 비교 기반 이진 결정 트리로 처리함 분기 확률은 결정 트리 구성에 반영되지만, 희소 값 예제에서 입력을 8로 나누어 단순화하는 변환까지 GCC가 찾아내지는 못함 예제로 보는 변환 전략 분석은 GCC에 초점을 맞추며, 별도 표시가 없는 예제는 -O3로 컴파일함 비트셋 변환을 제외한 최적화는 Clang에도 적용됨 인용한 GCC 코드는 간결하게 보이도록 일부 수정하고 일부 단언문을 제거한 형태임 이전 글에서 살펴본 비교 결정 트리 외에도 여러 switch 구현 방식이 있음 서로 다른 함수를 호출하는 case 0부터 case 4까지는 점프 테이블로 변환됨 입력 범위를 검사한 뒤 테이블에 저장된 주소로 간접 점프함 case 97부터 case 101까지처럼 상수만큼 이동한 값도 입력에서 97을 빼는 방식으로 같은 구조를 사용함 값이 희소해질수록 점프 테이블의 이점이 줄어들며, 실험에서는 case당 약 8개 엔트리 부근에서 전략이 달라짐 0, 7, 14, 21, 34는 빈 위치를 기본 분기로 채운 점프 테이블로 변환됨 0, 8, 16, 24, 40은 비교 트리로 변환됨 두 번째 예제에서 입력을 8로 나누어 단순화하는 변환은 GCC가 찾아내지 못함 일부 구간과 공통 분기 목적지 처리 밀집된 부분집합만 점프 테이블로 만드는 것도 가능함 case 1부터 case 5까지와 case 100이 함께 있으면, 1~5는 점프 테이블로 처리하고 100은 별도 비교 분기로 처리함 같은 함수를 호출하는 연속된 case 는 범위로 묶어 비교 횟수를 줄임 0~3, 21~24, 42~45, 63~66, 84~87의 다섯 구간이 각각 같은 함수를 호출하는 예제에는 총 20개의 case가 있음 점프 테이블은 88개 엔트리가 필요하지만, 각 구간은 비교 두 번으로 처리할 수 있어 비교 횟수는 총 10회임 88 < 20 × ...