Thiết kế trình biên dịch - Tối ưu hóa mã

Tối ưu hóa là một kỹ thuật chuyển đổi chương trình, cố gắng cải thiện mã bằng cách làm cho nó tiêu thụ ít tài nguyên hơn (tức là CPU, Bộ nhớ) và cung cấp tốc độ cao.

Trong tối ưu hóa, các cấu trúc lập trình chung cấp cao được thay thế bằng các mã lập trình cấp thấp rất hiệu quả. Quá trình tối ưu hóa mã phải tuân theo ba quy tắc được đưa ra dưới đây:

Mã đầu ra, theo bất kỳ cách nào, không được thay đổi ý nghĩa của chương trình.
Việc tối ưu hóa sẽ làm tăng tốc độ của chương trình và nếu có thể, chương trình sẽ yêu cầu ít tài nguyên hơn.
Bản thân việc tối ưu hóa phải nhanh chóng và không được làm chậm trễ quá trình biên dịch tổng thể.

Các nỗ lực cho một mã được tối ưu hóa có thể được thực hiện ở nhiều cấp độ khác nhau của quá trình biên dịch.

Khi bắt đầu, người dùng có thể thay đổi / sắp xếp lại mã hoặc sử dụng các thuật toán tốt hơn để viết mã.
Sau khi tạo mã trung gian, trình biên dịch có thể sửa đổi mã trung gian bằng cách tính toán địa chỉ và cải thiện các vòng lặp.
Trong khi tạo mã máy đích, trình biên dịch có thể sử dụng phân cấp bộ nhớ và thanh ghi CPU.

Tối ưu hóa có thể được phân loại rộng rãi thành hai loại: độc lập với máy và phụ thuộc vào máy.

Tối ưu hóa độc lập với máy

Trong tối ưu hóa này, trình biên dịch lấy mã trung gian và biến đổi một phần của mã không liên quan đến bất kỳ thanh ghi CPU và / hoặc vị trí bộ nhớ tuyệt đối nào. Ví dụ:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Mã này liên quan đến việc gán lặp lại mục định danh, nếu chúng ta đặt theo cách này:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

không chỉ lưu các chu kỳ CPU mà có thể được sử dụng trên bất kỳ bộ xử lý nào.

Tối ưu hóa phụ thuộc vào máy móc

Tối ưu hóa phụ thuộc vào máy được thực hiện sau khi mã đích đã được tạo và khi mã được chuyển đổi theo kiến trúc máy đích. Nó liên quan đến các thanh ghi CPU và có thể có tham chiếu bộ nhớ tuyệt đối hơn là tham chiếu tương đối. Các trình tối ưu hóa phụ thuộc vào máy móc nỗ lực để tận dụng tối đa hệ thống phân cấp bộ nhớ.

Khối cơ bản

Mã nguồn thường có một số lệnh, các lệnh này luôn được thực thi theo trình tự và được coi là các khối cơ bản của mã. Các khối cơ bản này không có bất kỳ câu lệnh nhảy nào trong số chúng, tức là khi lệnh đầu tiên được thực hiện, tất cả các lệnh trong cùng một khối cơ bản sẽ được thực hiện theo trình tự xuất hiện của chúng mà không làm mất quyền kiểm soát luồng của chương trình.

Một chương trình có thể có nhiều cấu trúc khác nhau dưới dạng các khối cơ bản, như IF-THEN-ELSE, câu lệnh điều kiện SWITCH-CASE và các vòng lặp như DO-WHILE, FOR và REPEAT-UNTIL, v.v.

Nhận dạng khối cơ bản

Chúng tôi có thể sử dụng thuật toán sau để tìm các khối cơ bản trong một chương trình:

Câu lệnh tiêu đề tìm kiếm của tất cả các khối cơ bản từ nơi bắt đầu khối cơ bản:
- Câu lệnh đầu tiên của một chương trình.
- Các câu lệnh là đích của bất kỳ nhánh nào (có điều kiện / không điều kiện).
- Các câu lệnh theo sau bất kỳ câu lệnh nhánh nào.
Các câu lệnh tiêu đề và các câu lệnh theo sau chúng tạo thành một khối cơ bản.
Một khối cơ bản không bao gồm bất kỳ câu lệnh tiêu đề nào của bất kỳ khối cơ bản nào khác.

Khối cơ bản là những khái niệm quan trọng theo cả quan điểm tạo mã và tối ưu hóa.

Các khối cơ bản đóng một vai trò quan trọng trong việc xác định các biến, chúng đang được sử dụng nhiều lần trong một khối cơ bản duy nhất. Nếu bất kỳ biến nào đang được sử dụng nhiều hơn một lần, bộ nhớ thanh ghi được cấp cho biến đó không cần được làm trống trừ khi khối kết thúc thực thi.

Đồ thị luồng điều khiển

Các khối cơ bản trong một chương trình có thể được biểu diễn bằng đồ thị luồng điều khiển. Biểu đồ luồng điều khiển mô tả cách điều khiển chương trình đang được chuyển giữa các khối. Nó là một công cụ hữu ích giúp tối ưu hóa bằng cách giúp định vị bất kỳ vòng lặp không mong muốn nào trong chương trình.

Tối ưu hóa vòng lặp

Hầu hết các chương trình chạy như một vòng lặp trong hệ thống. Nó trở nên cần thiết để tối ưu hóa các vòng lặp để tiết kiệm chu kỳ CPU và bộ nhớ. Các vòng lặp có thể được tối ưu hóa bằng các kỹ thuật sau:

Invariant code: Một đoạn mã nằm trong vòng lặp và tính giá trị giống nhau tại mỗi lần lặp được gọi là mã bất biến của vòng lặp. Mã này có thể được di chuyển ra khỏi vòng lặp bằng cách lưu nó để được tính toán chỉ một lần, thay vì mỗi lần lặp lại.
Induction analysis : Một biến được gọi là biến cảm ứng nếu giá trị của nó bị thay đổi trong vòng lặp bởi một giá trị bất biến của vòng lặp.
Strength reduction: Có những biểu thức tiêu tốn nhiều chu kỳ, thời gian và bộ nhớ CPU hơn. Các biểu thức này nên được thay thế bằng các biểu thức rẻ hơn mà không ảnh hưởng đến kết quả đầu ra của biểu thức. Ví dụ, phép nhân (x * 2) tốn kém về chu kỳ CPU hơn (x << 1) và cho kết quả tương tự.

Loại bỏ mã chết

Mã chết là một hoặc nhiều câu lệnh mã, đó là:

Không bao giờ được thực thi hoặc không thể truy cập,
Hoặc nếu được thực thi, đầu ra của chúng sẽ không bao giờ được sử dụng.

Do đó, mã chết không đóng vai trò gì trong bất kỳ hoạt động chương trình nào và do đó nó có thể đơn giản bị loại bỏ.

Mã chết một phần

Có một số câu lệnh mã mà các giá trị được tính toán chỉ được sử dụng trong một số trường hợp nhất định, tức là, đôi khi các giá trị được sử dụng và đôi khi chúng không. Những mã như vậy được gọi là mã chết một phần.

Biểu đồ luồng điều khiển ở trên mô tả một đoạn chương trình trong đó biến 'a' được sử dụng để gán đầu ra của biểu thức 'x * y'. Giả sử rằng giá trị được gán cho 'a' không bao giờ được sử dụng trong vòng lặp. Ngay sau khi điều khiển rời khỏi vòng lặp, 'a' được gán giá trị của biến 'z', sẽ được sử dụng sau này trong chương trình. Chúng tôi kết luận ở đây rằng mã gán của 'a' không bao giờ được sử dụng ở bất cứ đâu, do đó nó đủ điều kiện để loại bỏ.

Tương tự như vậy, hình trên mô tả rằng câu lệnh điều kiện luôn sai, ngụ ý rằng mã, được viết trong trường hợp đúng, sẽ không bao giờ được thực thi, do đó nó có thể bị xóa.

Dự phòng một phần

Các biểu thức dư thừa được tính toán nhiều lần trong một đường dẫn song song mà không có bất kỳ sự thay đổi nào trong toán hạng. Trong khi các biểu thức dư thừa một phần được tính toán nhiều lần trong một đường dẫn mà không có bất kỳ thay đổi nào về toán hạng. Ví dụ,

[biểu thức thừa]	[biểu thức dư thừa một phần]

Mã bất biến vòng lặp là một phần dư thừa và có thể được loại bỏ bằng cách sử dụng kỹ thuật chuyển động mã.

Một ví dụ khác về mã dự phòng một phần có thể là:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Chúng tôi giả định rằng các giá trị của toán hạng (y và z) không bị thay đổi từ việc gán biến a biến c. Ở đây, nếu câu lệnh điều kiện là đúng, thì y OP z được tính hai lần, nếu không thì một lần. Chuyển động mã có thể được sử dụng để loại bỏ sự dư thừa này, như hình dưới đây:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Ở đây, cho dù điều kiện là đúng hay sai; y OP z chỉ nên được tính một lần.