Trình biên dịch tối ưu hóa chức năng giai thừa này như thế nào?

Question

Vì vậy, tôi đã có một cái nhìn tại một số ma thuật đó là O3 trong GCC (thực sự tôi đang biên dịch bằng cách sử dụng Clang nhưng nó giống với GCC và tôi đoán một phần lớn của trình tối ưu hóa đã được kéo từ GCC đến Clang).

xem xét chương trình C này:

int foo(int n) { 
    if (n == 0) return 1; 
    return n * foo(n-1); 
} 

int main() { 
    return foo(10); 
} 

Điều đầu tiên tôi đã khá WOW-ed tại (mà cũng là WOW-ed ở trong câu hỏi này - https://stackoverflow.com/a/414774/1068248) là cách int foo(int) (một chức năng thừa cơ bản) biên dịch vào một vòng lặp chặt chẽ. Đây là hội đồng ARM cho nó:

.globl _foo 
    .align 2 
    .code 16 
    .thumb_func _foo 
_foo: 
    mov r1, r0 
    movs r0, #1 
    cbz r1, LBB0_2 
LBB0_1: 
    muls r0, r1, r0 
    subs r1, #1 
    bne LBB0_1 
LBB0_2: 
    bx lr 

Blimey tôi nghĩ. Điều đó khá thú vị! Vòng lặp hoàn toàn chặt chẽ để làm giai thừa. WOW. Nó không phải là một tối ưu hóa cuộc gọi đuôi kể từ khi, tốt, nó không phải là một cuộc gọi đuôi. Nhưng nó dường như đã thực hiện một tối ưu hóa tương tự.

Bây giờ nhìn vào main:

.globl _main 
    .align 2 
    .code 16 
    .thumb_func _main 
_main: 
    movw r0, #24320 
    movt r0, #55 
    bx lr 

Đó chỉ thổi tâm trí của tôi phải trung thực. Nó hoàn toàn bỏ qua foo và trả lại 3628800 là 10!.

Điều này làm cho tôi thực sự nhận ra cách trình biên dịch của bạn thường có thể thực hiện công việc tốt hơn nhiều so với việc tối ưu hóa mã của bạn. Nhưng nó đặt ra câu hỏi, làm thế nào để nó quản lý để làm một công việc tốt như vậy? Vì vậy, bất kỳ ai cũng có thể giải thích (có thể bằng cách liên kết với mã có liên quan) cách tối ưu hóa sau hoạt động:

1. Tối ưu hóa ban đầu là một vòng lặp chặt chẽ.

2. Tối ưu hóa nơi main chỉ cần gửi và trả lại kết quả trực tiếp thay vì thực sự thực hiện foo.

Một hiệu ứng phụ thú vị khác của câu hỏi này sẽ cho thấy một số tối ưu thú vị hơn mà GCC/Clang có thể thực hiện.

Answer 1

Nếu bạn biên dịch với gcc -O3 -fdump-tree-all, bạn có thể thấy rằng lần kết xuất đầu tiên trong đó đệ quy đã được chuyển thành vòng lặp là foo.c.035t.tailr1. Điều này có nghĩa là cùng một tối ưu hóa xử lý các cuộc gọi đuôi khác cũng xử lý trường hợp này hơi mở rộng. Việc đệ quy dưới dạng n * foo(...) hoặc n + foo(...) không khó để xử lý thủ công (xem bên dưới) và vì có thể mô tả chính xác cách thức, trình biên dịch có thể thực hiện tối ưu hóa tự động đó.

Tối ưu hóa main đơn giản hơn nhiều: nội tuyến có thể biến thành 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1 và nếu tất cả toán hạng của phép nhân là hằng số, thì phép nhân có thể được thực hiện tại thời gian biên dịch.

Cập nhật: Dưới đây là cách bạn có thể xóa thủ công đệ trình từ foo, có thể được thực hiện tự động. Tôi không nói đây là phương pháp được sử dụng bởi GCC, nhưng đó là một khả năng thực tế.

Đầu tiên, hãy tạo hàm trợ giúp.Nó hoạt động chính xác như foo(n), ngoại trừ kết quả của nó được nhân với một tham số bổ sung f.

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f * 1; 
    return f * n * foo(n-1); 
} 

Sau đó, lần lượt các cuộc gọi đệ quy của foo vào cuộc gọi đệ quy của foo_helper, và dựa vào các thông số yếu tố để thoát khỏi các nhân.

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f; 
    return foo_helper(n-1, f * n); 
} 

Rẽ này vào một vòng lặp:

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

Cuối cùng, inline foo_helper:

int foo(int n) 
{ 
    int f = 1; 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

(Đương nhiên, đây không phải là cách hợp lý nhất để tự viết hàm.)