Làm thế nào một trình biên dịch có thể áp dụng chức năng loại bỏ các hàm không tinh khiết?

Question

Thông thường, khi viết mã, tôi thấy mình sử dụng giá trị từ một hàm gọi cụ thể nhiều lần. Tôi nhận ra rằng một sự tối ưu hóa rõ ràng sẽ là nắm bắt các giá trị được sử dụng nhiều lần này trong các biến. này (pseudo code):

function add1(foo){ foo + 1; } 
... 
do_something(foo(1)); 
do_something_else(foo(1)); 

trở thành:

function add1(foo){ foo + 1; } 
... 
bar = foo(1); 
do_something(bar); 
do_something_else(bar); 

Tuy nhiên, làm điều này một cách rõ ràng làm cho mã dễ đọc hơn trong kinh nghiệm của tôi. Tôi cho rằng các trình biên dịch không thể thực hiện loại tối ưu hóa này nếu ngôn ngữ lựa chọn của chúng ta cho phép các hàm có tác dụng phụ.

Gần đây tôi đã xem xét điều này và nếu tôi hiểu chính xác, tối ưu hóa này là/có thể được thực hiện cho các ngôn ngữ trong đó chức năng phải thuần túy. Điều đó không làm tôi ngạc nhiên, nhưng được cho là điều này cũng có thể được thực hiện cho các chức năng không tinh khiết. Với một số tìm kiếm Google nhanh chóng tôi tìm thấy những đoạn: GCC 4.7 Fortran improvement

Khi thực hiện front-end-tối ưu hóa, tùy chọn -faggressive chức năng-loại trừ cho phép việc loại bỏ các hàm duplicate gọi ngay cả đối với các chức năng bất tịnh.

Compiler Optimization (Wikipedia)

Ví dụ, trong một số chức năng ngôn ngữ không được phép có tác dụng phụ. Do đó, nếu một chương trình thực hiện nhiều cuộc gọi đến cùng một hàm với cùng các đối số, trình biên dịch có thể ngay lập tức suy ra rằng kết quả của hàm chỉ cần được tính một lần. Trong các ngôn ngữ mà các chức năng được phép có các tác dụng phụ, một chiến lược khác là có thể. Trình tối ưu hóa có thể xác định chức năng nào không có tác dụng phụ và hạn chế tối ưu hóa như vậy đối với các chức năng miễn phí có hiệu lực phụ. Tối ưu hóa này chỉ có thể khi trình tối ưu hóa có quyền truy cập vào hàm được gọi.

Từ hiểu biết của tôi, điều này có nghĩa là trình tối ưu hóa có thể xác định khi nào hàm không hoặc không thuần túy và thực hiện tối ưu hóa này khi hàm. Tôi nói điều này bởi vì nếu một hàm luôn tạo ra cùng một đầu ra khi cho cùng một đầu vào, và là tác dụng phụ tự do, nó sẽ đáp ứng cả hai điều kiện được coi là thuần túy.

Hai đoạn trích này đưa ra hai câu hỏi cho tôi.

1. Trình biên dịch có thể thực hiện tối ưu hóa này một cách an toàn nếu một hàm không thuần túy? (như trong -faggressive-chức năng loại bỏ)
2. Làm thế nào một trình biên dịch có thể xác định xem một hàm là thuần khiết hay không? (Như trong chiến lược gợi ý trong bài viết Wikipedia)

và cuối cùng là:

• thể loại này của tối ưu hóa được áp dụng cho bất kỳ ngôn ngữ, hoặc chỉ khi điều kiện nhất định được đáp ứng?
• Tối ưu hóa này có đáng giá ngay cả đối với các chức năng cực kỳ đơn giản không?
• Chi phí lưu trữ và truy xuất giá trị từ ngăn xếp tăng lên bao nhiêu?

Tôi xin lỗi nếu đây là những câu hỏi ngu ngốc hoặc phi logic. Họ chỉ là một số điều tôi đã tò mò về thời gian gần đây. :)

Answer 1

Tuyên bố từ chối trách nhiệm: Tôi không phải là trình biên dịch/người tối ưu hóa, tôi chỉ có khuynh hướng nhìn vào mã được tạo và thích đọc về nội dung đó - vì vậy đó không phải là tính năng tự động. Một tìm kiếm nhanh không bật lên nhiều trong việc loại bỏ chức năng-tích cực, vì vậy nó có thể làm thêm một số phép thuật không được giải thích ở đây.

---

Một ưu có thể

• nỗ lực để nội tuyến cuộc gọi chức năng (với thế hệ mã thời gian liên kết, công trình này thậm chí trên các đơn vị biên soạn)
• thực hiện loại bỏ subexpression thông thường, và có thể là tác dụng phụ sắp xếp lại.

Sửa đổi ví dụ của bạn một chút, và thực hiện nó trong C++:

extern volatile int RW_A = 0; // see note below 

int foo(int a) { return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 
} 

Giải quyết tới (giả)

<register> = 4; 
RW_A = register; 
RW_A = register; 

(Lưu ý: đọc từ và viết cho một biến không ổn định là một "hiệu ứng phụ có thể quan sát", mà trình tối ưu hóa phải giữ nguyên theo thứ tự được đưa ra bởi mã.)

---

Sửa đổi ví dụ cho foo để có một tác dụng phụ:

extern volatile int RW_A = 0; 
extern volatile int RW_B = 0; 
int accu = 1; 

int foo(int a) { accu *= 2; return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 

    RW_B = accu; 
    return 0; 
} 

tạo giả sau đây:

registerA = accu; 
registerA += registerA; 
accu = registerA; 

registerA += registerA; 
registerC = 4; 
accu = registerA; 

RW_A = registerC; 
RW_A = registerC; 

RW_B = registerA; 

Chúng tôi nhận thấy rằng việc loại bỏ subexpression chung vẫn được thực hiện, và tách ra khỏi các tác dụng phụ. Nội tuyến và sắp xếp lại cho phép tách các tác dụng phụ khỏi phần "thuần túy".

Lưu ý rằng trình biên dịch đọc và háo hức viết lại thành accu, điều này không cần thiết. Tôi không chắc chắn về lý do ở đây.

---

Để kết luận:

Một trình biên dịch không cần phải kiểm tra độ tinh khiết. Nó có thể xác định các tác dụng phụ cần được bảo tồn, và sau đó chuyển đổi phần còn lại theo ý thích của nó.

tối ưu hóa như vậy là đáng giá, ngay cả đối với các chức năng tầm thường, bởi vì, trong số những người khác,

• tài nguyên CPU và bộ nhớ được chia sẻ, những gì bạn sử dụng bạn có thể lấy đi từ người khác
• Tuổi thọ pin
• Tối ưu hóa nhỏ có thể là cổng đến các cổng lớn hơn

Chi phí cho việc truy cập bộ nhớ ngăn xếp thường là ~ 1 chu kỳ, vì đầu ngăn xếp thường ở bộ nhớ cache Cấp 1 rồi.Lưu ý rằng thường nên in đậm: nó có thể "thậm chí tốt hơn", vì đọc/ghi có thể được tối ưu hóa đi, hoặc nó có thể tồi tệ hơn do áp lực tăng lên trên bộ đệm L1 xóa một số dữ liệu quan trọng khác trở lại L2.

Giới hạn ở đâu?

Về mặt lý thuyết, thời gian biên dịch. Trong thực tế, khả năng dự đoán và tính chính xác của trình tối ưu hóa là sự cân bằng bổ sung.

---

Tất cả các kiểm tra với VC2008, cài đặt tối ưu hóa mặc định cho bản dựng "Bản phát hành".