Hai nghiên cứu về tối ưu hóa trình biên dịch

Trường hợp 2: Chuyển đổi độ bền

Kịch bản

Hầu hết các định dạng nhị phân, cho dù để lưu trữ, IPC hay kết nối mạng, đều chỉ định một thứ tự byte cụ thể cho trường số; ví dụ: các tệp cơ sở dữ liệu SQLite sử dụng các trường big endian, trong khi Protobuf i32 và Các trường i64 có dạng endian nhỏ. Cách thông thường để viết giải mã bất khả tri về độ bền của máy chủ chức năng là nối rõ ràng các byte đầu vào riêng lẻ. Đối với các giá trị 32-bit trông giống như thế nào đó như (giả sử int 32-bit nên chúng ta không cần ép kiểu):

uint32_t load_le32(const uint8_t* dữ liệu)
{
    trả về dữ liệu [0] | (dữ liệu[1] << 8) | (dữ liệu[2] << 16) | (dữ liệu[3] << 24 );

uint32_t load_be32(const uint8_t* dữ liệu)
{
    trả về dữ liệu[3] | (dữ liệu[2] << 8) | ( dữ liệu[1] << 16) | (dữ liệu[0] << 24);

Trên x86, hỗ trợ các tải không được phân bổ từ bộ nhớ, điều này tạo ra Tập hợp tối ưu ở -O1 và ở trên:

load_le32 (chưa ký char const*):
        mov eax, dword ptr [rdi]
        ret
load_be32(chưa ký char const*):
        di chuyển  eax, dword ptr [rdi]
        bswap eax
        ret

Một số nhà phát triển mắc chứng DRY mãn tính và phải đối mặt với viễn cảnh phải viết những thứ này các hàm và các hàm tương đương 64-bit của chúng lần thứ mười một hoặc có thể hoạt động với các kích thước nguyên ngoài 4 và 8 byte, thay vào đó, bạn nên viết một phiên bản chung duy nhất:

static uint64_t tải(const uint8_t* dữ liệu , size_t sz, bool be)
{
    uint64_t val = 0;
    for (size_t i = 0; i < sz; ++i)
         val |= static_cast<uint64_t>(dữ liệu[be ? sz - i - 1 : i]) << (8 * i);
    trả về giá trị ;

uint32_t load_le32(const uint8_t* dữ liệu) { return tải(dữ liệu, 4, false); 
uint32_t load_be32(const uint8_t * dữ liệu) { return tải(dữ liệu, 4, true); 
uint64_t load_le64(const uint8_t* dữ liệu) { return tải(dữ liệu , 8, false); 
uint64_t load_be64(const uint8_t* dữ liệu) { return tải(dữ liệu, 8, true); 

Khi đó, người đánh giá mã có thể lo lắng một cách hợp lý về việc liệu có bất kỳ sự hồi quy hiệu suất nào không so với các chức năng truyền thống hơn. Hãy xem điều gì xảy ra khi chúng tôi biên dịch:

load_le32(unsigned char const*):
        mov eax, dword ptr [rdi]
        ret
load_be32(chưa ký char const*):
        mov eax, dword ptr [rdi]
        bswap eax
        ret
load_le64(chưa ký char const*):
        mov rax , qword ptr [rdi]
        ret
load_be64(chưa ký char const*):
        mov rax, qword ptr [rdi]
        bswap rax ret

Có vẻ như nhà phát triển lười biếng (hoặc có lẽ có tầm nhìn xa) của chúng tôi đã rõ ràng—ít nhất là nếu họ không làm vậy cần sử dụng gcc, ít nhất là ở phiên bản 15.2, không thể tối ưu hóa mã này. Hãy kiểm tra tiến trình của quy trình tối ưu hóa một lần nữa để hiểu rõ hơn về cách trình biên dịch thực hiện điều này tắt.

Lựa chọn hướng dẫn

Dựa trên những gì chúng ta đã thấy ở nửa đầu của bài đăng, có thể hơi ngạc nhiên khi tìm hiểu kỹ Trình xem đường dẫn Opt đáng tin cậy của chúng tôi rằng phải mất tất cả cho đến khi Giai đoạn lựa chọn lệnh (còn được gọi là ISel) cho các tải liên tiếp được xếp thành tải đơn 32 hoặc 64 bit. Chúng ta sẽ xem trong phần tiếp theo cách chúng ta có thể kích hoạt tính năng đơn giản hóa sớm hơn trong một số trường hợp, nhưng chúng ta hãy dành chút thời gian để hiểu ISel là gì và nó thực hiện thao tác gấp như thế nào.

Lựa chọn lệnh là giai đoạn đầu tiên của back-end trình biên dịch, chạy sau tất cả các lệnh chung. tối ưu hóa đã vượt qua (trong LLVM, sự khác biệt này cũng được phản ánh trong sự tách biệt giữa opt và các tệp nhị phân llc). Mục đích của nó là chuyển đổi LLVM IR do trình tối ưu hóa tạo ra thành Máy IR (MIR), một cách thể hiện cụ thể theo mục tiêu của luồng lệnh phù hợp với các lượt truyền xuống chẳng hạn như lập kế hoạch hoặc phân bổ đăng ký. Hầu hết các mục tiêu LLVM, bao gồm x86, đều sử dụng SelectionDAG làm khung lựa chọn hướng dẫn của họ. Chúng tôi sẽ không đi sâu vào SelectionDAG tại đây⁹; vì mục đích của chúng tôi, chỉ cần biết rằng nó bao gồm trình tối ưu hóa lỗ nhìn trộm của riêng nó được gọi là DAGCombiner, tương tự như InstCombine, có thể nắm bắt các cơ hội đơn giản hóa do tạo mã hoặc cụ thể cho mục tiêu đó.

Giống như InstCombiner truy cập từng lệnh trong một khối cơ bản, DAGCombiner truy cập từng nút trong khối DAG được xây dựng từ những hướng dẫn tương tự. Nó ở đây, trong số rất nhiều phép biến đổi được thực hiện bởi hoặc khách truy cập, chúng tôi tìm thấy MatchLoadCombine() phương pháp:

/// Khớp một mẫu trong đó giá trị vô hướng loại rộng được tải bởi nhiều loại hẹp
 /// tải và kết hợp bằng ca và ors. Gấp nó thành một tải hoặc một tải
/// và BSWAP nếu mục tiêu hỗ trợ nó.

Tất nhiên, đây là mẫu chính xác mà chúng ta thấy trong LLVM IR ở đầu vào SelectionDAG, sau load() được nội tuyến, các đối số không đổi được truyền đi và các vòng lặp được giải phóng hoàn toàn. Cái gì Tuy nhiên, điều thú vị về phương pháp này là nó không thực hiện khớp mẫu đơn giản như chúng ta đã làm. thấy trước đây trong InstCombine, nhưng thay vào đó theo dõi nguồn gốc của từng byte ở đầu ra của Lệnh hoặc đệ quy thông qua DAG (sử dụng tínhByteProvider() chức năng), không chỉ từ tải mà còn thông qua các hoạt động theo bit, hoán đổi byte và phần mở rộng 0/dấu. Cái này làm cho nó đủ mạnh để xử lý các biểu thức như:

static uint64_t load_alt(const uint8_t* dữ liệu, size_t sz, bool được)
{
    uint64_t val = 0; for (size_t i = 0; i < sz; ++i)
        val = (val << 8) | dữ liệu[là ? i : sz - i - 1];
    trả về giá trị;

Tuy nhiên, trong trường hợp này, chúng tôi nhận thấy chỉ có các chức năng 32-bit mới được tối ưu hóa hoàn toàn. Mặc dù chúng ta có cùng số lượng lệnh LLVM IR như trước đây, nhưng phiên bản mới yêu cầu đệ quy sâu hơn vào DAG để khám phá nguồn byte được tải sớm nhất (vì chúng tôi thực hiện hai thao tác trên biến đầu ra trong mỗi lần lặp, thay vì một), nhấn giới hạn được mã hóa cứng của mười cấp độ đệ quy. Đây là một ví dụ điển hình về cách có một bản đồ tư duy quá trình xử lý nội bộ của trình biên dịch, cũng như việc bám sát các mẫu phổ biến hơn, có thể giúp chúng ta tránh những trường hợp bệnh lý như vậy.¹⁰

Trợ giúp trình biên dịch

Một số nhà phát triển C++ dày dạn kinh nghiệm có thể phản đối ví dụ này theo bản năng. Rốt cuộc, nếu chúng ta chỉ have a few possible argument values known at compile-time, why wouldn’t we just template our thay vì dựa vào trình biên dịch để truyền các hằng số?

mẫu <size_t sz, bool be>
static uint64_t tải(const  uint8_t* dữ liệu)
{
    uint64_t val = 0;
    for (size_t i = 0; i < sz; ++i)
        val |= static_cast <uint64_t>(dữ liệu[be ? sz - i - 1 : i]) << (8 * i);
    trả về giá trị;

uint32_t  Load_le32(const uint8_t* dữ liệu) { return tải<4, false>(dữ liệu); 
uint32_t load_be32(const uint8_t* dữ liệu ) { trở lại tải<4, true>(dữ liệu); 
uint64_t load_le64(const uint8_t* dữ liệu) { return tải<8, false>(dữ liệu); 
uint64_t load_be64(const uint8_t* dữ liệu) { return tải<8, true>(dữ liệu); 

đầu ra không thay đổi, nhưng lần này IR cho các hàm little-endian được tối ưu hóa thành một lần tải duy nhất rất lâu trước khi chúng ta đạt được lệnh giai đoạn lựa chọn, trong một đường chuyền được gọi là AggressiveInstCombine . Giống như InstCombine, thẻ này thực hiện nhiều cách tối ưu hóa lỗ nhìn trộm khác nhau nhưng nó tập trung vào những thứ đó có xu hướng ít cần thiết hơn hoặc mất nhiều thời gian hơn để chạy, đó là lý do tại sao nó chỉ chạy một lần ở -O2 (và hoàn toàn không có ở -O1). Một trong những tối ưu hóa này được thực hiện trong foldConsecutiveLoads() chức năng, khớp với các mẫu có dạng “bitwise-hoặc (tùy chọn) dịch trái, mở rộng bằng 0, các lần tải liên tiếp”, chẳng hạn như những lần chúng tôi tìm thấy trong các hàm của mình.

Vì nó dựa vào việc khớp mẫu đơn giản nên AggressiveInstCombine không mạnh bằng DAGCombiner; đặc biệt, nó không thể tối ưu hóa màn hình gấp được sử dụng trong load_alt() ở trên ngay cả đối với 32 bit. Nó cũng có không ảnh hưởng đến tải trọng lớn của chúng tôi bởi vì, với tư cách là bước tối ưu hóa cấp trung (không giống như DAGCombiner, là một phần của back-end của trình biên dịch), nó cố gắng tạo ra IR độc lập với mục tiêu nhiều nhất có thể. có thể. Việc gấp tải lượng endian lớn lên mục tiêu endian nhỏ và ngược lại sẽ yêu cầu thêm nội tại trao đổi byte dành riêng cho mục tiêu sẽ làm phức tạp việc phân tích và tối ưu hóa tiếp theo vượt qua.

clang++ -S -emit-llvm -O2 -o- endianness.cpp \
    | opt -S -passes='aggressive-instcombine' - \
    | llc --x86-asm-syntax=intel

uint32_t load_le32(const uint8_t* dữ liệu) { return tải (dữ liệu, 4, false); 
uint32_t load_add_le32(const uint8_t* dữ liệu)
{
    trở lại load_le32(dữ liệu) + dữ liệu[0 ;

load_add_le32(chưa ký char const*):
        movzx ecx, byte ptr  [rdi]
        movzx edx, word ptr [rdi + 1]
        shl edx, 8
        movzx eax, byte ptr [rdi + 3 
        shl eax, 24
        hoặc eax, edx
        hoặc eax, ecx
        thêm eax, ecx
        ret

uint32_t load_add_le32(const uint8_t* dữ liệu)
{
    return tải<4, false>(dữ liệu) + dữ liệu[0 ;