Tối ưu hóa mô hình chi phí của SLP Vectorizer trong LLVM

Mới đây, kỹ sư Kavin Gnanapandithan đã công bố một trường hợp nghiên cứu thú vị về việc giải quyết sự tụt giảm hiệu suất (performance regression) trong bộ biên dịch LLVM. Vấn đề này xảy ra trên kiến trúc RISC-V và liên quan trực tiếp đến SLP Vectorizer (Superword Level Parallelism Vectorizer) – một thành phần quan trọng chịu trách nhiệm tối ưu hóa mã bằng cách chuyển đổi các lệnh vô hướng (scalar instructions) thành lệnh vector.

Bài viết này sẽ đi sâu vào cách phân tích benchmark, xác định nguyên nhân gốc rễ và giải pháp điều chỉnh mô hình chi phí (cost model) để cải thiện hiệu năng.

Vấn đề: Hiệu suất tụt giảm nghiêm trọng

Quá trình bắt đầu khi Kavin nhận thấy một benchmark cụ thể trên máy chủ BPI-F3 (sử dụng RISC-V) có sự gia tăng đến 89% về thời gian thực thi. Cụ thể, số lượng lệnh phát ra (issued instructions) tăng khoảng 26%, và số chu kỳ (cycles) tăng tới 48%.

Chi tiết benchmark ban đầu cho thấy sự tăng

Để tìm hiểu nguyên nhân, Kavin so sánh mã hợp dịch (assembly) của bản build LLVM cũ và bản mới. Kết quả cho thấy bản build mới đang thực hiện một chuỗi các lệnh fsd (Float Store Double), lưu các giá trị dấu chấm động từ thanh ghi xuống stack. Sau đó, nó sử dụng lệnh vle64.v để tải các giá trị này từ bộ nhớ vào thanh ghi vector v16, và cuối cùng thực hiện lệnh vfredosum.vs (Vector Ordered Floating-point Sum Reduction).

Về lý thuyết, việc thay thế chuỗi các lệnh cộng vô hướng (fadd) bằng một lệnh giảm vector (vector reduction) sẽ nhanh hơn. Tuy nhiên, thực tế lại trái ngược. Chi phí để xây dựng vector ban đầu bằng cách lưu dữ liệu vào bộ nhớ rồi tải lại (spill và reload) đã vượt quá lợi ích thu được từ việc thực hiện phép tính bằng vector.

So sánh mã assembly giữa bản cũ và bản mới

Tìm kiếm nguyên nhân

Kavin đã sử dụng LLVM IR (Intermediate Representation) để xác định xem các thay đổi này bắt nguồn từ đâu. Kết quả chỉ rõ một chuỗi các lệnh insertelement đang được tạo ra để đóng gói (pack) các giá trị vô hướng vào một vector trước khi gọi hàm nội tại llvm.vector.reduce.fadd.

Bằng cách sử dụng git log và lọc các commit liên quan đến "reduction", tác giả đã tìm ra nguyên nhân là commit: [SLP] Support ordered fadd reduction via reduction intrinsics.

Commit này có mục đích cho phép SLP Vectorizer thay thế chuỗi vô hướng bằng intrinsic giảm vector nếu lợi ích về chi phí. Tuy nhiên, hàm tryToReduceOrdered chịu trách nhiệm kiểm tra tính khả thi về chi phí đã hoạt động sai.

Vấn đề cốt lõi nằm ở cấu trúc dữ liệu TreeEntry. Khi tính toán chi phí cho các nút, hàm getGatherNodeEffectiveScale thường dùng getScaleToLoopIterations để ước lượng. Tuy nhiên, với nút gốc của phép giảm (reduction root), thông tin về vòng lặp cha có thể bị thiếu hoặc không chính xác khi cây được xây dựng biệt lập, dẫn đến việc đánh giá chi phí xây dựng vector quá thấp.

Giải pháp: Điều chỉnh mô hình chi phí

Để khắc phục, Kavin đã đề xuất chỉnh sửa cách tính chi phí trong hàm getGatherNodeEffectiveScale và calculateTreeCostAndTrimNonProfitable.

Thay đổi chính là chuyển tham số Instruction *U vào hàm getGatherNodeEffectiveScale. Đối với nút gốc (TE.Idx == 0), tham số này sẽ là RdxRoot (nút gốc của phép giảm). Việc này giúp hàm tính toán chi phí có thể neo (anchor) vào ngữ cảnh vòng lặp chính xác hơn thông qua U, thay vì dựa vào thông tin cha bị thiếu trong cây biệt lập.

Đoạn mã vá (patch) chính bao gồm việc cập nhật chữ ký hàm và logic gọi hàm để truyền RdxRoot khi cần thiết:

// Truyền RdxRoot vào tính toán chi phí cho nút gather
Scale = IsGatherLike ? getGatherNodeEffectiveScale(TE, TE.Idx == 0 ? RdxRoot : nullptr)
                     : getScaleToLoopIterations(TE);

Nhờ đó, mô hình chi phí có thể tính toán chính xác chi phí thực sự của việc xây dựng vector thông qua các thao tác insertelement và tràn bộ nhớ (spill), từ đó chặn lại các tối ưu hóa không mang lại lợi ích.

Kết quả

Sau khi áp dụng bản vá, hiệu suất của benchmark đã được phục hồi. Hình ảnh dưới đây cho thấy số chu kỳ (cycles) đã quay lại mức gần như so với baseline ban đầu, dù số lượng lệnh vector có thể thay đổi đôi chút.

Hiệu suất sau khi áp dụng bản vá

Trường hợp này một lần nữa khẳng định tầm quan trọng của việc chính xác trong mô hình chi phí của các trình biên dịch hiện đại. Đôi khi, một tối ưu hóa lý thuyết có lợi (như dùng vector thay vì vô hướng) có thể trở thành gánh nặng nếu chi phí "vận chuyển" dữ liệu không được tính toán đầy đủ.