QBE 1.3: Bản cập nhật quan trọng nhất với hiệu suất vượt trội và hỗ trợ Windows ABI

QBE 1.3: Bản cập nhật quan trọng nhất với hiệu suất vượt trội và hỗ trợ Windows ABI

QBE 1.3 đã mất một khoảng thời gian để phát triển, nhưng đây được coi là bản phát hành quan trọng nhất kể từ phiên bản 1.0 với khoảng 7.000 dòng mã mới và 1.500 dòng mã bị loại bỏ. Ngoài việc sửa các lỗi thông thường, QBE giờ đây sở hữu thuật toán khớp IL (Intermediate Language) mới và nguyên bản, các tối ưu hóa mới từ Roland Paterson-Jones, sự hỗ trợ cho Windows ABI do Scott Graham thêm vào, và việc triển khai kế hoạch của Michael Forney giúp QBE tạo ra mã độc lập vị trí (như trong các đối tượng chia sẻ).

Tối ưu hóa hiệu suất và Benchmark Coremark

Thỉnh thoảng, "con ong QBE" lại chích một lập trình viên xuất sắc, và lần này nạn nhân là Roland! Chúng tôi đã đề xuất xem xét benchmark coremark để tạo ra một sân chơi cụ thể nhưng đơn giản để tối ưu hóa. Các phép đo ban đầu với qbe-1.2 cho thấy chúng tôi đang tụt hậu khá xa so với mục tiêu "70% hiệu suất của gcc -O2", chỉ đạt khoảng 40%.

Chúng tôi quyết định giải quyết vấn đề này cho bản phát hành 1.3. Việc kiểm tra dữ liệu profiling sớm cho thấy khoảng cách về hiệu suất chủ yếu nằm ở cách xử lý hai hàm: ee_isdigit và crcu8. Đáng chú ý là các hàm này không thực sự viết theo phong cách C chuẩn; ví dụ, ee_isdigit thường được nội tuyến (inline) văn bản, sử dụng && thay vì & và bỏ qua toán tử ternary thừa. Đối với CRC, cách triển khai tốt nhất là sử dụng bảng tính toán trước.

Mặc dù quan sát này hơi thất vọng vì nó không chỉ ra một nguồn chi phí tổng quát, nhưng chúng tôi đã triển khai nhiều tối ưu hóa (GVN/GCM, tối ưu hóa vòng lặp, loại bỏ if, đơn giản hóa CFG, ...) và áp dụng thử nghiệm trên cả coremark và các trường hợp sử dụng thực tế hơn như bộ kiểm tra Hare. Kết quả là chúng tôi hiện đạt hơn 63% hiệu suất của các trình biên dịch thương mại trên coremark gốc. Đặc biệt, chúng tôi loại bỏ việc nội tuyến khỏi bộ tối ưu hóa để hoãn giải quyết sự không tương thích của nó với mô hình biên dịch theo từng hàm kiểu luồng (streaming) của QBE. Nếu sửa đổi benchmark coremark để nội tuyến hàm ee_isdigit và sử dụng triển khai crcu8 không rẽ nhánh đơn giản hơn, QBE có thể đạt mục tiêu 70%. Các tối ưu hóa mới cũng mang lại lợi ích cho người dùng Hare: tôi đã đo được mức cải thiện 33% trên bộ kiểm tra Hare so với qbe-1.2 (1.7s so với 2.6s).

Thuật toán khớp IL mới và công cụ mgen

Kể từ những ngày đầu, QBE sử dụng thuật toán đánh số cây từ dưới lên (bottom-up tree-numbering) lấy cảm hứng từ trình biên dịch C Plan9 của Ken Thompson. Thuật toán này khá chung chung nhưng có những tinh tế trong việc xử lý khéo léo tính kết hợp và giao hoán của các toán tử số học. Mục tiêu lâu dài của tôi là triển khai giải pháp siêu lập trình (metaprogramming) cho vấn đề này, và QBE 1.3 đã hiện thực hóa điều đó.

Một công cụ OCaml mới gọi là mgen được sử dụng để biên dịch các mẫu IL kiểu lispy thành mã C chuẩn để khớp chúng. Công cụ mgen sẽ tìm kiếm các khối bình luận đặc biệt chứa các mẫu IL và chèn mã C khớp ngay bên dưới các khối đó. Mã C được tạo ra được thiết kế để trông giống hệt mã chuẩn trong qbe và hoạt động tương tự như logic viết tay trước phiên bản 1.3.

Chi tiết hơn, các DAG (đồ thị có hướng không chu trình) của lệnh được khớp bằng cách theo tiếp cận đánh số giống như trong trình biên dịch của Ken Thompson. Sau đó, mgen liên kết mỗi số với một bitset chỉ định mẫu người dùng cấp cao nhất nào được khớp bởi nút IL hiện tại (biến tạm); từ đó có thể chọn mẫu phù hợp nhất bằng logic viết tay. Các mẫu có thể bao gồm các biến có thể được thu thập bằng cách chạy một chương trình khớp. Các chương trình này cũng được mgen tạo ra trong một ngôn ngữ bytecode đơn giản mà hàm runmatch() có thể diễn giải.

Tôi mong muốn trong tương lai mgen sẽ được sử dụng để đơn giản hóa việc chọn lệnh (instruction selection) ở nhiều backend hơn và thậm chí nhận ra các mẫu IL như xoay bit (bit rotations) trong các lần chạy tối ưu hóa.

Hỗ trợ Windows ABI và Mã độc lập vị trí (PIC)

Đối với bản phát hành 1.3, QBE cũng "chích" phải Scott Graham. Scott đã hào phóng upstreaming (đóng góp ngược) bản triển khai Windows ABI của mình, ban đầu được tìm thấy trong một công việc phái sinh thú vị. Mã assembly được tạo bởi QBE vẫn giữ cú pháp AT&T và được biên dịch tốt nhất bởi bộ lắp ráp mingw, mặc dù tôi chưa tự thử nó trên Windows. Biên dịch cho Windows giờ đây đơn giản như việc truyền tham số -t amd64_win cho QBE.

Cuối cùng nhưng không kém phần quan trọng, QBE đã cải thiện hỗ trợ cho mã độc lập vị trí (position-independent code - PIC) và giờ đây có thể liên kết mượt mà với và thậm chí tạo ra các đối tượng chia sẻ (shared objects) trên hầu hết các mục tiêu. Rào cản chính cho đến nay là thiếu hỗ trợ cho quyền gián tiếp tiếp cận các biến toàn cục (ví dụ: bảng bù toàn cục trên ELF). Điều này giờ đây có thể ở cấp độ IL thông qua hỗ trợ của cờ "hằng số động" (dynamic constant) mới (DYNCONST trong đặc tả IL).

Ví dụ, để truy cập một biến dlvar từ một thư viện liên kết động, người ta sẽ sử dụng cờ này. Và, trong trường hợp bạn thắc mắc, chúng tôi dùng từ chập "hằng số động" để nói về các ký hiệu địa chỉ (hằng số trong quá trình thực thi) chỉ có thể biết tại thời gian chạy (động) vì chúng được cấp phát bởi thời gian chạy hoặc bộ liên kết động thay vì bởi giai đoạn liên kết thông thường của quá trình biên dịch.

Cảm ơn đã đọc đến đây và chúc các bạn lập trình vui vẻ!