Cách GCC xử lý câu lệnh switch: Bảng nhảy, bitset và cây so sánh

Câu lệnh switch tưởng chừng đơn giản nhưng thực chất lại phức tạp hơn nhiều so với vẻ ngoài của nó. Bài viết này đi sâu vào cách trình biên dịch GCC quyết định "hạ cấp" (lowering) câu lệnh switch thành mã máy, với nhiều chiến lược khác nhau tùy thuộc vào hình dạng dữ liệu đầu vào.

Từ bảng nhảy đến cây so sánh

Khởi đầu với một ví dụ đơn giản: một hàm nhận hai số nguyên x và val, tùy theo giá trị x mà gọi hàm tương ứng (f0, f1...) với tham số val.

Nếu tự tay viết, lập trình viên sẽ dùng mảng con trỏ hàm với đầu vào làm chỉ số. GCC cũng đồng tình với cách tiếp cận này và biến câu lệnh switch thành một bảng nhảy (jump table). Thậm chí trình biên dịch còn nhận ra khi các giá trị bị lệch bởi một hằng số và tự động bù trừ.

Tuy nhiên, trực giác mách bảo rằng các giá trị càng thưa thớt thì bảng nhảy càng kém hiệu quả. Qua thử nghiệm, có thể thấy GCC đặt ngưỡng khoảng 8 mục bảng nhảy cho mỗi nhãn case. Nghĩa là nếu bảng nhảy có kích thước nhỏ hơn 8 lần số nhãn case, việc chuyển đổi được coi là có lợi.

Khi có một giá trị "ngoại lai", GCC vẫn nhận diện được các tập con case dày đặc: nó phát sinh một nhánh rẽ cho case 100, nhưng vẫn dùng bảng nhảy cho các case từ 1 đến 5.

Khi nhiều nhãn case gọi cùng một hàm

Điều thú vị xuất hiện khi nhiều nhãn case cùng gọi chung một hàm. Giả sử có 20 nhãn case với giá trị từ 0 đến 87 — về lý thuyết, bảng nhảy chỉ cần 88 mục, nhỏ hơn nhiều so với 20 × 8. Vậy mà GCC lại chọn một chuỗi phép so sánh.

Lý do: GCC đếm số phép so sánh chứ không phải số nhãn case. Khi các case liên tiếp nhau, chúng có thể được xử lý chỉ với hai phép so sánh thay vì bốn. Tổng cộng chỉ còn 10 phép so sánh, và 10 × 8 < 88, nên bảng nhảy không còn sinh lợi.

Chiến lược bitset và lệnh bt

Có những trường hợp GCC sinh ra mã máy trông rất lạ: không có lệnh cmp, cũng không có bảng nhảy, mà chỉ một hằng số bí ẩn như 2753205. Manh mối nằm ở lệnh bt (bit test) của Intel, dùng để kiểm tra một bit trong chuỗi bit.

Nếu chuyển 2753205 sang hệ nhị phân, ta sẽ thấy đó chính là một bitset, trong đó các bit được bật tương ứng với giá trị ASCII của các nhãn case (sau khi trừ đi 48). Đây là một kỹ thuật tối ưu rất tinh tế, biến chuỗi so sánh thành một phép kiểm tra bit duy nhất.

Bên trong mã nguồn GCC

Trình biên dịch dùng pass tên là pass_lower_switch, gọi đến hàm analyze_switch_statement. Các bước chính gồm:

• Tập hợp cluster: mỗi nhãn case được ghi lại thành một simple_cluster chứa khoảng giá trị, cạnh đầu ra và xác suất được chọn (từ tối ưu hóa dẫn hướng hồ sơ — profile-guided optimization).
• Tìm bitset tối ưu: dùng quy hoạch động để tìm số lượng bitset ít nhất biểu diễn được toàn bộ các case.
• Chuyển đổi bảng nhảy: cũng dùng quy hoạch động, tìm cách nhóm các cluster liên tiếp thành bảng nhảy sao cho có lợi nhất.
• Dựng cây so sánh: phần còn lại được chuyển thành cây nhị phân so sánh, có tính đến xác suất của từng cluster để chia đôi danh sách sao cho hai nửa có xác suất bằng nhau.

Các heuristic quan trọng

GCC sử dụng tỷ lệ giữa số mục bảng nhảy và số phép so sánh làm thước đo:

• Khi tối ưu cho tốc độ (-O1, -O2, -O3, -Ofast), tỷ lệ là 8.
• Khi tối ưu cho kích thước (-Os), tỷ lệ là 2.

Ngoài ra, do bảng nhảy có chi phí phụ trợ (nhảy gián tiếp và kiểm tra biên), GCC yêu cầu một số lượng nhãn case tối thiểu — trên các kiến trúc x64 và Arm64 hiện đại, ngưỡng này mặc định là 5.

Khi so sánh hai phương án phân tách, GCC ưu tiên phương án tạo ra ít bảng nhảy hơn; nếu hòa, nó chọn phương án xử lý được nhiều nhãn case hơn.

Ý nghĩa với lập trình viên

Với những ai quan tâm đến hiệu năng mã nguồn C/C++, hiểu được các chiến lược này giúp viết switch hiệu quả hơn: sắp xếp các case liên tiếp khi có thể, tránh các giá trị quá thưa thớt nếu không cần thiết, và cân nhắc dùng __builtin_expect_with_probability để hướng dẫn trình biên dịch khi biết trước phân bố xác suất của dữ liệu đầu vào.

Tóm lại, GCC áp dụng ba chiến lược hạ cấp chính: bitset cluster, bảng nhảy và cây so sánh nhị phân — trong đó bitset và bảng nhảy là các lá của cây quyết định. Đây là minh chứng cho thấy công việc của trình biên dịch tinh vi hơn nhiều so với những gì lập trình viên thường hình dung.