LLVM từ góc độ cờ vây

Phát triển một trình biên dịch là một nhiệm vụ rất khó khăn. Nhưng may mắn thay, với sự phát triển của các dự án như LLVM, giải pháp cho vấn đề này đã được đơn giản hóa rất nhiều, điều này cho phép ngay cả một lập trình viên duy nhất cũng có thể tạo ra một ngôn ngữ mới có hiệu suất gần giống với C. Làm việc với LLVM rất phức tạp bởi thực tế là điều này hệ thống được thể hiện bằng một lượng lớn mã, được trang bị ít tài liệu. Để cố gắng khắc phục thiếu sót này, tác giả của tài liệu, bản dịch mà chúng tôi đang xuất bản ngày hôm nay, sẽ trình bày các ví dụ về mã được viết bằng Go và cho thấy cách chúng được dịch lần đầu sang Đi SSA, sau đó trong LLVM IR bằng trình biên dịch tinyGO. Mã Go SSA và LLVM IR đã được chỉnh sửa một chút để loại bỏ những thứ không liên quan đến các giải thích được đưa ra ở đây, nhằm làm cho các giải thích trở nên dễ hiểu hơn.

Ví dụ đầu tiên

Hàm đầu tiên tôi sẽ xem xét ở đây là một cơ chế đơn giản để cộng số:

func myAdd(a, b int) int{
    return a + b
}

Chức năng này rất đơn giản và có lẽ không gì có thể đơn giản hơn. Nó dịch sang mã Go SSA sau:

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

Với chế độ xem này, gợi ý về loại dữ liệu được đặt ở bên phải và có thể bị bỏ qua trong hầu hết các trường hợp.

Ví dụ nhỏ này đã cho phép bạn thấy được bản chất của một khía cạnh của SSA. Cụ thể, khi chuyển đổi mã thành dạng SSA, mỗi biểu thức được chia thành các phần cơ bản nhất mà nó được tạo thành. Trong trường hợp của chúng tôi, lệnh return a + btrên thực tế, đại diện cho hai thao tác: cộng hai số và trả về kết quả.

Ngoài ra, tại đây bạn có thể thấy các khối cơ bản của chương trình, trong mã này chỉ có một khối - khối đầu vào. Chúng ta sẽ nói nhiều hơn về các khối bên dưới.

Mã Go SSA dễ dàng chuyển đổi sang LLVM IR:

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

Điều bạn có thể nhận thấy là mặc dù các cấu trúc cú pháp khác nhau được sử dụng ở đây nhưng cấu trúc của hàm về cơ bản không thay đổi. Mã LLVM IR mạnh hơn mã Go SSA một chút, tương tự như C. Ở đây, trong phần khai báo hàm, đầu tiên có mô tả về kiểu dữ liệu mà nó trả về, kiểu đối số được chỉ định trước tên đối số. Ngoài ra, để đơn giản hóa việc phân tích cú pháp IR, tên của các thực thể toàn cục được đặt trước ký hiệu @và trước tên địa phương có ký hiệu % (một chức năng cũng được coi là một thực thể toàn cầu).

Một điều cần lưu ý về mã này là quyết định biểu diễn kiểu của Go int, có thể được biểu diễn dưới dạng giá trị 32 bit hoặc 64 bit, tùy thuộc vào trình biên dịch và mục tiêu biên dịch, được chấp nhận khi LLVM tạo mã IR. Đây là một trong nhiều lý do khiến mã LLVM IR không độc lập với nền tảng như nhiều người nghĩ. Mã như vậy, được tạo cho một nền tảng, không thể được lấy và biên dịch đơn giản cho nền tảng khác (trừ khi bạn phù hợp để giải quyết vấn đề này với sự cẩn thận).

Một điểm thú vị khác đáng chú ý là loại i64 không phải là số nguyên có dấu: nó trung tính về mặt biểu thị dấu của số. Tùy thuộc vào hướng dẫn, nó có thể biểu thị cả số có dấu và số không dấu. Trong trường hợp biểu diễn phép cộng, điều này không thành vấn đề, do đó không có sự khác biệt khi làm việc với số có dấu hoặc không dấu. Ở đây tôi muốn lưu ý rằng trong ngôn ngữ C, việc tràn một biến số nguyên có dấu dẫn đến hành vi không xác định, do đó giao diện Clang thêm cờ vào thao tác nsw (không có gói có chữ ký), thông báo cho LLVM biết rằng nó có thể cho rằng phần bổ sung đó không bao giờ tràn.

Điều này có thể quan trọng đối với một số tối ưu hóa. Ví dụ: cộng hai giá trị i16 trên nền tảng 32 bit (có thanh ghi 32 bit), sau đó, yêu cầu hoạt động mở rộng dấu hiệu để duy trì trong phạm vi i16. Vì điều này, việc thực hiện các phép toán số nguyên dựa trên kích thước thanh ghi máy thường hiệu quả hơn.

Điều gì xảy ra tiếp theo với mã IR này hiện không được chúng tôi đặc biệt quan tâm. Mã được tối ưu hóa (nhưng trong trường hợp ví dụ đơn giản như của chúng tôi, không có gì được tối ưu hóa) và sau đó được chuyển đổi thành mã máy.

Ví dụ thứ hai

Ví dụ tiếp theo chúng ta xem xét sẽ phức tạp hơn một chút. Cụ thể, chúng ta đang nói về một hàm tính tổng một lát số nguyên:

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

Mã này chuyển đổi thành mã Go SSA sau:

func sum(numbers []int) int:
entry:
    jump for.loop
for.loop:
    t0 = phi [entry: 0:int, for.body: t6] #n                       int
    t1 = phi [entry: 0:int, for.body: t7] #i                       int
    t2 = len(numbers)                                              int
    t3 = t1 < t2                                                  bool
    if t3 goto for.body else for.done
for.body:
    t4 = &numbers[t1]                                             *int
    t5 = *t4                                                       int
    t6 = t0 + t5                                                   int
    t7 = t1 + 1:int                                                int
    jump for.loop
for.done:
    return t0

Tại đây, bạn có thể thấy nhiều cấu trúc điển hình hơn để biểu diễn mã ở dạng SSA. Có lẽ tính năng rõ ràng nhất của mã này là không có lệnh điều khiển luồng có cấu trúc nào. Để kiểm soát luồng tính toán, chỉ có các bước nhảy có điều kiện và vô điều kiện, và nếu chúng ta coi lệnh này là lệnh để kiểm soát luồng, thì lệnh quay lại.

Trên thực tế, ở đây bạn có thể chú ý đến thực tế là chương trình không được chia thành các khối bằng dấu ngoặc nhọn (như trong họ ngôn ngữ C). Nó được chia theo nhãn, gợi nhớ đến các ngôn ngữ hợp ngữ và được trình bày dưới dạng các khối cơ bản. Trong SSA, các khối cơ bản được định nghĩa là các chuỗi mã liền kề bắt đầu bằng nhãn và kết thúc bằng các hướng dẫn hoàn thành khối cơ bản, chẳng hạn như − return и jump.

Một chi tiết thú vị khác của mã này được thể hiện bằng lệnh phi. Các hướng dẫn khá bất thường và có thể mất một thời gian để hiểu. nhớ lấy SSA là viết tắt của Bài tập đơn tĩnh. Đây là cách biểu diễn trung gian của mã được trình biên dịch sử dụng, trong đó mỗi biến chỉ được gán một giá trị một lần. Điều này rất tốt cho việc thể hiện các hàm đơn giản như hàm của chúng ta myAddđược hiển thị ở trên, nhưng không phù hợp với các hàm phức tạp hơn như hàm được thảo luận trong phần này sum. Đặc biệt, các biến thay đổi trong quá trình thực hiện vòng lặp i и n.

SSA bỏ qua hạn chế trong việc gán giá trị biến một lần bằng cách sử dụng cái gọi là lệnh phi (tên của nó được lấy từ bảng chữ cái Hy Lạp). Thực tế là để tạo ra biểu diễn mã SSA cho các ngôn ngữ như C, bạn phải sử dụng một số thủ thuật. Kết quả của việc gọi lệnh này là giá trị hiện tại của biến (i hoặc n) và danh sách các khối cơ bản được sử dụng làm tham số của nó. Ví dụ, hãy xem xét hướng dẫn này:

t0 = phi [entry: 0:int, for.body: t6] #n

Ý nghĩa của nó như sau: nếu khối cơ bản trước đó là một khối entry (đầu vào), sau đó t0 là một hằng số 0và nếu khối cơ bản trước đó là for.body, thì bạn cần lấy giá trị t6 từ khối này. Tất cả điều này có vẻ khá bí ẩn, nhưng cơ chế này là nguyên nhân khiến SSA hoạt động. Từ góc độ con người, tất cả điều này làm cho mã khó hiểu, nhưng thực tế là mỗi giá trị chỉ được gán một lần khiến cho nhiều lần tối ưu hóa trở nên dễ dàng hơn nhiều.

Lưu ý rằng nếu bạn viết trình biên dịch của riêng mình, bạn thường sẽ không phải đối mặt với loại nội dung này. Ngay cả Clang cũng không tạo ra tất cả các hướng dẫn này phi, nó sử dụng cơ chế alloca (nó giống như làm việc với các biến cục bộ thông thường). Sau đó, khi chạy thẻ tối ưu hóa LLVM có tên mem2reg, hướng dẫn alloca được chuyển đổi sang dạng SSA. Tuy nhiên, TinyGo nhận đầu vào từ Go SSA, thuận tiện là đã được chuyển đổi sang dạng SSA.

Một sự đổi mới khác của đoạn mã trung gian đang được xem xét là việc truy cập vào các phần tử lát cắt theo chỉ mục được biểu diễn dưới dạng một phép toán tính địa chỉ và một phép toán hủy tham chiếu con trỏ kết quả. Tại đây bạn có thể thấy việc bổ sung trực tiếp các hằng số vào mã IR (ví dụ - 1:int). Trong ví dụ với hàm myAdd cái này chưa được sử dụng Bây giờ chúng ta đã có những tính năng đó, hãy xem mã này sẽ trở thành gì khi được chuyển đổi sang dạng LLVM IR:

define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
  br label %for.loop

for.loop:                                         ; preds = %for.body, %entry
  %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
  %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
  %2 = icmp slt i64 %1, %len
  br i1 %2, label %for.body, label %for.done

for.body:                                         ; preds = %for.loop
  %3 = getelementptr i64, i64* %ptr, i64 %1
  %4 = load i64, i64* %3
  %5 = add i64 %0, %4
  %6 = add i64 %1, 1
  br label %for.loop

for.done:                                         ; preds = %for.loop
  ret i64 %0
}

Ở đây, như trước đây, chúng ta có thể thấy cấu trúc tương tự, bao gồm các cấu trúc cú pháp khác. Ví dụ, trong các cuộc gọi phi giá trị và nhãn được hoán đổi. Tuy nhiên, có một điều ở đây đáng được đặc biệt chú ý.

Để bắt đầu, ở đây bạn có thể thấy một chữ ký hàm hoàn toàn khác. LLVM không hỗ trợ các lát cắt và do đó, để tối ưu hóa, trình biên dịch TinyGo tạo ra mã trung gian này sẽ chia mô tả cấu trúc dữ liệu này thành các phần. Nó có thể đại diện cho ba phần tử lát cắt (ptr, len и cap) dưới dạng cấu trúc (struct), nhưng việc biểu diễn chúng dưới dạng ba thực thể riêng biệt sẽ cho phép thực hiện một số tối ưu hóa. Các trình biên dịch khác có thể biểu diễn lát cắt theo những cách khác, tùy thuộc vào quy ước gọi các chức năng của nền tảng đích.

Một tính năng thú vị khác của mã này là việc sử dụng lệnh getelementptr (thường viết tắt là GEP).

Lệnh này hoạt động với các con trỏ và được sử dụng để lấy một con trỏ tới phần tử lát cắt. Ví dụ: hãy so sánh nó với đoạn mã sau được viết bằng C:

int* sliceptr(int *ptr, int index) {
    return &ptr[index];
}

Hoặc với những điều sau đây tương đương với điều này:

int* sliceptr(int *ptr, int index) {
    return ptr + index;
}

Điều quan trọng nhất ở đây là hướng dẫn getelementptr không thực hiện các hoạt động hội thảo. Nó chỉ tính toán một con trỏ mới dựa trên con trỏ hiện có. Nó có thể được coi là hướng dẫn mul и add ở cấp độ phần cứng. Bạn có thể đọc thêm về hướng dẫn GEP đây.

Một đặc điểm thú vị khác của mã trung gian này là việc sử dụng lệnh icmp. Đây là lệnh có mục đích chung được sử dụng để thực hiện so sánh số nguyên. Kết quả của lệnh này luôn là một giá trị thuộc loại i1 - giá trị logic. Trong trường hợp này, sự so sánh được thực hiện bằng từ khóa slt (có dấu nhỏ hơn), vì chúng ta đang so sánh hai số được biểu thị trước đó bằng loại int. Nếu chúng ta so sánh hai số nguyên không dấu thì chúng ta sẽ sử dụng icmpvà từ khóa được sử dụng trong so sánh sẽ là ult. Để so sánh các số dấu phẩy động, một lệnh khác được sử dụng, fcmp, hoạt động theo cách tương tự.

Kết quả

Tôi tin rằng trong tài liệu này tôi đã đề cập đến những tính năng quan trọng nhất của LLVM IR. Tất nhiên, có rất nhiều hơn nữa ở đây. Đặc biệt, biểu diễn trung gian của mã có thể chứa nhiều chú thích cho phép quá trình tối ưu hóa có tính đến một số tính năng nhất định của mã mà trình biên dịch đã biết mà không thể được biểu thị bằng IR. Ví dụ: đây là một lá cờ inbounds Hướng dẫn GEP hoặc cờ nsw и nuw, có thể được thêm vào hướng dẫn add. Từ khóa cũng vậy private, cho trình tối ưu hóa biết rằng hàm mà nó đánh dấu sẽ không được tham chiếu từ bên ngoài đơn vị biên dịch hiện tại. Điều này cho phép thực hiện nhiều tối ưu hóa liên thủ tục thú vị như loại bỏ các đối số không sử dụng.

Bạn có thể đọc thêm về LLVM trong tài liệu, mà bạn sẽ thường xuyên tham khảo khi phát triển trình biên dịch dựa trên LLVM của riêng mình. Đây khả năng lãnh đạo, xem xét việc phát triển trình biên dịch cho một ngôn ngữ rất đơn giản. Cả hai nguồn thông tin này sẽ hữu ích cho bạn khi tạo trình biên dịch của riêng mình.

Gởi bạn đọc! Bạn có đang sử dụng LLVM không?

Nguồn: www.habr.com