Trình Biên Dịch

Thiết kế trình biên dịch: Tạo mã

Posted on by ComdyVN

Thiết kế trình biên dịch: Tạo mã

Ở hướng dẫn trước, bạn đã tìm hiểu vì sao cần phải tạo mã trung gian? Cách tạo mã trung gian trong thiết kế trình biên dịch. Nếu bỏ lỡ thì bạn có thể xem ở đây:

Thiết kế trình biên dịch: Tạo mã trung gian
Trong hướng dẫn này, bạn sẽ tìm hiểu vì sao cần phải tạo mã trung gian? Cách tạo mã trung gian trong thiết kế trình biên dịch.
Trung NguyenComdy

Trong hướng dẫn này bạn sẽ tìm hiểu cách tạo mã của trình biên dịch.

Tạo mã (code generation) có thể được coi là giai đoạn cuối cùng của quá trình biên dịch. Thông qua quá trình tạo mã, quá trình tối ưu hóa có thể được áp dụng trên mã, nhưng đó có thể được coi là một phần của giai đoạn tạo mã.

Mã do trình biên dịch tạo ra là mã đối tượng của một số ngôn ngữ lập trình cấp thấp hơn, ví dụ, hợp ngữ.

Chúng tôi đã thấy rằng mã nguồn được viết bằng ngôn ngữ cấp cao hơn được chuyển đổi thành ngôn ngữ cấp thấp hơn tạo ra mã đối tượng cấp thấp hơn, mã này phải có các thuộc tính tối thiểu sau:

  • Nó phải mang ý nghĩa chính xác của mã gốc (mã cấp cao).
  • Nó phải hiệu quả về mặt sử dụng CPU và quản lý bộ nhớ.

Bây giờ chúng ta sẽ xem cách mã trung gian được chuyển đổi thành mã đối tượng đích (mã hợp ngữ, trong trường hợp này).

Đồ thị Acyclic có hướng

Directed Acyclic Graph (DAG) là một công cụ mô tả cấu trúc của các khối cơ bản, giúp xem luồng giá trị chảy giữa các khối cơ bản và cũng cung cấp tối ưu hóa. DAG cung cấp sự chuyển đổi dễ dàng trên các khối cơ bản. DAG có thể được hiểu ở đây:

  • Các nút lá đại diện cho định danh, tên hoặc hằng số.
  • Các nút bên trong đại diện cho các toán tử.
  • Các nút bên trong cũng đại diện cho kết quả của các biểu thức hoặc định danh / tên nơi các giá trị sẽ được lưu trữ hoặc gán.

Ví dụ:

t0 = a + b
t1 = t0 + c
d = t0 + t1
Đồ thị Acyclic có hướng
[t0 = a + b]
Đồ thị Acyclic có hướng
[t1 = t0 + c]
Đồ thị Acyclic có hướng
[d = t0 + t1]

Tối ưu hóa Peephole

Kỹ thuật tối ưu hóa này hoạt động cục bộ trên mã nguồn để biến nó thành mã tối ưu hóa. Theo cục bộ, chúng tôi muốn nói đến một phần nhỏ của khối mã đang xử lý.

Các phương pháp này có thể được áp dụng trên các mã trung gian cũng như trên các mã đích. Một loạt các câu lệnh được phân tích và được kiểm tra để đảm bảo khả năng tối ưu hóa sau đây:

Loại bỏ lệnh dư thừa

Ở cấp độ mã nguồn, người dùng có thể thực hiện những điều sau:

int add_ten(int x)
{
    int y, z;
    y = 10;
    z = x + y;
    return z;
}

// or
int add_ten(int x)
{
    int y;
    y = 10;
    y = x + y;
    return y;
}

// or
int add_ten(int x)
{
    int y = 10;
    return x + y;
}

// or
int add_ten(int x)
{
    return x + 10;
}

Ở cấp độ biên dịch, trình biên dịch tìm kiếm các hướng dẫn dư thừa trong tự nhiên. Việc tải và lưu trữ nhiều hướng dẫn có thể mang cùng một ý nghĩa ngay cả khi một số trong số chúng bị loại bỏ. Ví dụ:

MOV x, R0
MOV R0, R1

Chúng ta có thể xóa lệnh đầu tiên và viết lại câu dưới dạng:

MOV x, R1

Mã không thể truy cập

Mã không thể truy cập là một phần của mã chương trình không bao giờ được truy cập do cấu trúc lập trình. Các lập trình viên có thể đã vô tình viết một đoạn mã không bao giờ có thể tiếp cận được.

Thí dụ:

void add_ten(int x)
{
    return x + 10;
    printf(“value of x is %d”, x);
}

Trong đoạn mã này, câu lệnh printf sẽ không bao giờ được thực thi vì điều khiển chương trình quay trở lại trước khi nó có thể thực thi, do đó printf có thể bị loại bỏ.

Tối ưu hóa luồng điều khiển

Có những trường hợp trong mã mà điều khiển chương trình nhảy qua lại mà không thực hiện bất kỳ tác vụ quan trọng nào. Các bước nhảy này có thể được loại bỏ. Hãy xem xét đoạn mã sau:

#...		
MOV R1, R2
GOTO L1
#...
L1 :   GOTO L2
L2 :   INC R1

Trong mã này, nhãn L1 có thể được loại bỏ khi nó chuyển điều khiển đến L2. Vì vậy, thay vì nhảy đến L1 và sau đó đến L2, điều khiển có thể trực tiếp đến L2, như hình dưới đây:

#...		
MOV R1, R2
GOTO L2
#...
L2 :   INC R1

Đơn giản hóa biểu thức đại số

Có những trường hợp mà các biểu thức đại số có thể trở nên đơn giản. Ví dụ, khái niệm a = a + 0 có thể được thay thế bằng a và biểu thức a = a + 1 chỉ có thể được thay thế bằng INC a.

Giảm chi phí

Có những thao tác tiêu tốn nhiều thời gian và không gian hơn. ‘Chi phí’ của chúng có thể được giảm bớt bằng cách thay thế chúng bằng các hoạt động khác tiêu tốn ít thời gian và không gian hơn, nhưng cho kết quả tương tự.

Ví dụ: x * 2 có thể được thay thế bằng x << 1 , chỉ liên quan đến một lần dịch sang trái. Mặc dù đầu ra của a * a và a2 là như nhau, nhưng a2 sẽ hiệu quả hơn nhiều để triển khai.

Truy cập chỉ dẫn máy

Máy mục tiêu có thể triển khai các lệnh phức tạp hơn, có thể có khả năng thực hiện các hoạt động cụ thể một cách hiệu quả hơn nhiều.

Nếu mã đích có thể đáp ứng các chỉ dẫn đó một cách trực tiếp, điều đó sẽ không chỉ cải thiện chất lượng của mã mà còn mang lại kết quả hiệu quả hơn.

Trình tạo mã (code generator)

Một trình tạo mã được mong đợi có sự hiểu biết về môi trường thời gian chạy của máy mục tiêu và tập lệnh của nó. Trình tạo mã nên xem xét những điều sau để tạo mã:

  • Ngôn ngữ đích: Trình tạo mã phải nhận thức được bản chất của ngôn ngữ đích mà mã sẽ được chuyển đổi. Ngôn ngữ đó có thể tạo điều kiện cho một số hướng dẫn dành riêng cho máy để giúp trình biên dịch tạo mã theo cách thuận tiện hơn. Máy đích có thể có kiến ​​trúc bộ xử lý CISC hoặc RISC.
  • Loại IR: Biểu diễn trung gian có nhiều dạng khác nhau. Nó có thể nằm trong cấu trúc Cây cú pháp trừu tượng (AST), Ký pháp nghịch đảo Ba Lan hoặc Mã ba địa chỉ.
  • Lựa chọn lệnh: Trình tạo mã lấy Biểu diễn trung gian làm đầu vào và chuyển đổi (ánh xạ) nó thành tập lệnh của máy đích. Một biểu diễn có thể có nhiều cách (hướng dẫn) để chuyển đổi nó, vì vậy trách nhiệm của người tạo mã là chọn các hướng dẫn thích hợp một cách khôn ngoan.
  • Cấp phát thanh ghi: Một chương trình có một số giá trị được duy trì trong quá trình thực hiện. Kiến trúc của máy đích có thể không cho phép lưu giữ tất cả các giá trị trong bộ nhớ hoặc thanh ghi CPU. Trình tạo mã quyết định những giá trị nào cần giữ trong thanh ghi. Ngoài ra, nó quyết định các thanh ghi được sử dụng để giữ các giá trị này.
  • Thứ tự các lệnh: Cuối cùng, bộ tạo mã quyết định thứ tự mà lệnh sẽ được thực hiện. Nó tạo lịch trình cho các hướng dẫn để thực hiện chúng.

Trình mô tả (Descriptor)

Trình tạo mã phải theo dõi cả thanh ghi (tính khả dụng) và địa chỉ (vị trí của các giá trị) trong khi tạo mã. Đối với cả hai, hai trình mô tả sau được sử dụng:

  • Trình mô tả thanh ghi: Trình mô tả thanh ghi được sử dụng để thông báo cho trình tạo mã về tính khả dụng của các thanh ghi. Trình mô tả thanh ghi theo dõi các giá trị được lưu trữ trong mỗi thanh ghi. Bất cứ khi nào một thanh ghi mới được yêu cầu trong quá trình tạo mã, trình mô tả này sẽ được tham khảo để biết tính khả dụng của thanh ghi.
  • Trình mô tả địa chỉ: Giá trị của các tên (mã định danh) được sử dụng trong chương trình có thể được lưu trữ tại các vị trí khác nhau trong khi thực thi. Trình mô tả địa chỉ được sử dụng để theo dõi các vị trí bộ nhớ nơi các giá trị của mã định danh được lưu trữ. Các vị trí này có thể bao gồm thanh ghi CPU, heap, ngăn xếp, bộ nhớ hoặc kết hợp các vị trí được đề cập.

Trình tạo mã giữ cho cả hai trình mô tả được cập nhật trong thời gian thực. Đối với câu lệnh tải, LD R1, x, trình tạo mã:

  • Cập nhật Trình mô tả thanh ghi R1 có giá trị là x và
  • Cập nhật Trình mô tả địa chỉ (x) để hiển thị rằng một phiên bản của x nằm trong R1.

Tạo mã (code generation)

Các khối cơ bản bao gồm một chuỗi các lệnh ba địa chỉ. Trình tạo mã lấy chuỗi các lệnh này làm đầu vào.

Lưu ý: Nếu giá trị của tên được tìm thấy ở nhiều nơi (thanh ghi, bộ đệm hoặc bộ nhớ), giá trị của thanh ghi sẽ được ưu tiên hơn bộ nhớ đệm và bộ nhớ chính. Tương tự như vậy, giá trị của bộ nhớ đệm sẽ được ưu tiên hơn bộ nhớ chính. Bộ nhớ chính hầu như không được ưu tiên.

getReg: Trình tạo mã sử dụng hàm getReg để xác định trạng thái của các thanh ghi có sẵn và vị trí của các giá trị tên. getReg hoạt động như sau:

  • Nếu biến Y đã có trong thanh ghi R, nó sẽ sử dụng thanh ghi đó.
  • Nếu không, nếu một số thanh ghi R có sẵn, nó sẽ sử dụng thanh ghi đó.
  • Ngoài ra, nếu cả hai tùy chọn trên đều không thể thực hiện được, nó sẽ chọn một thanh ghi yêu cầu số lần tải và lưu trữ tối thiểu.

Đối với lệnh x = y OP z, trình tạo mã có thể thực hiện các hành động sau. Giả sử rằng L là vị trí (tốt nhất là thanh ghi) nơi lưu đầu ra của y OP z:

  • Gọi hàm getReg, để quyết định vị trí của L.

Xác định vị trí hiện tại (thanh ghi hoặc bộ nhớ) của y bằng cách tham khảo Trình mô tả địa chỉ của y . Nếu y hiện không có trong thanh ghi L , thì tạo lệnh sau để sao chép giá trị của y vào L :

MOV y', L

trong đó y ‘ đại diện cho giá trị được sao chép của y.

Xác định vị trí hiện tại của z bằng cách sử dụng cùng một phương pháp được sử dụng trong bước 2 cho y và tạo ra lệnh sau:

OP z', L

trong đó z ‘ đại diện cho giá trị được sao chép của z .

  • Bây giờ L chứa giá trị của y OP z, giá trị này được gán cho x. Vì vậy, nếu L là một thanh ghi, hãy cập nhật trình mô tả của nó để chỉ ra rằng nó chứa giá trị của x. Cập nhật mô tả của x để cho biết rằng nó được bảo quản ở vị trí L .
  • Nếu y và z không còn sử dụng nữa, chúng có thể được trả lại cho hệ thống.

Các cấu trúc mã khác như vòng lặp và câu lệnh điều kiện được chuyển đổi thành ngôn ngữ hợp ngữ theo hợp ngữ chung.

Trong hướng dẫn tiếp theo, bạn sẽ tìm hiểu chi tiết các phương pháp để tối ưu mã trong thiết kế trình biên dịch.

Thiết kế trình biên dịch: Tối ưu hóa mã
Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết các phương pháp để tối ưu mã trong thiết kế trình biên dịch.
Trung NguyenComdy

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *