Tối ưu hóa đệ quy đuôi (Tail Call Optimization) là gì?

Tóm tắt

Tối ưu hóa lời gọi đuôi (Tail Call Optimization – TCO) là kỹ thuật tối ưu trong trình biên dịch nhằm thực hiện lời gọi hàm ở vị trí đuôi mà không cần duy trì một khung ngăn xếp (Stack Frame) mới theo cơ chế gọi hàm thông thường. Khi áp dụng thành công, kỹ thuật này có thể hạn chế sự gia tăng bộ nhớ ngăn xếp, giảm chi phí gọi hàm và cho phép thực hiện những chuỗi lời gọi đuôi có độ sâu lớn.

Trong trường hợp hàm tự gọi lại chính nó, kỹ thuật này thường được gọi cụ thể là tối ưu hóa đệ quy đuôi (Tail Recursion Optimization) hoặc loại bỏ lời gọi đệ quy đuôi (Tail Recursion Elimination – TRE).

Bài viết trình bày nguyên lý của đệ quy đuôi, cơ chế hoạt động của ngăn xếp khi gọi hàm, phương pháp chuyển đổi đệ quy thành vòng lặp, những điều kiện cần thiết để tối ưu, ảnh hưởng của quy ước gọi hàm (Calling Convention) và giao diện nhị phân ứng dụng (Application Binary Interface – ABI). Đồng thời, bài viết đối chiếu cơ chế triển khai trong GCC và LLVM, phân tích mã máy trên các kiến trúc x86-64 và ARM64, cũng như những giới hạn của kỹ thuật này trong thực tế.

Từ khóa: tối ưu hóa lời gọi đuôi; đệ quy đuôi; trình biên dịch; khung ngăn xếp; loại bỏ đệ quy đuôi; LLVM; GCC; quy ước gọi hàm; mã máy.

---

1. Đệ quy và cơ chế gọi hàm

1.1. Đệ quy là gì?

Đệ quy $Recursion$ là kỹ thuật trong đó một hàm trực tiếp hoặc gián tiếp gọi lại chính nó để giải quyết một bài toán.

Một thuật toán đệ quy thường có hai thành phần:

1. Điều kiện dừng (Base Case): Xác định thời điểm thuật toán kết thúc việc gọi đệ quy.
2. Bước đệ quy (Recursive Case): Tiếp tục giải quyết bài toán thông qua một lời gọi hàm mới với dữ liệu đã được biến đổi.

Ví dụ, giai thừa của số nguyên không âm $n$ được định nghĩa:

Có thể biểu diễn bằng ngôn ngữ C:

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

Đây là một hàm đệ quy trực tiếp vì factorial gọi lại chính factorial.

Với n = 4, quá trình tính toán về mặt logic như sau:

factorial(4)
  4 * factorial(3)
        3 * factorial(2)
              2 * factorial(1)
                    1 * factorial(0)
                          1

Khi đến điều kiện dừng, các lời gọi lần lượt hoàn thành theo chiều ngược lại:

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Ví dụ này thể hiện đặc trưng của đệ quy thông thường: sau khi lời gọi đệ quy trả về, hàm gọi vẫn cần thực hiện thêm một phép toán.

1.2. Khung ngăn xếp (Stack Frame)

Khi một chương trình thực hiện lời gọi hàm, hệ thống thực thi thường cần duy trì thông tin phục vụ việc chuyển quyền điều khiển và quay trở lại hàm gọi.

Những thông tin này có thể bao gồm:

• Địa chỉ trả về (Return Address).
• Các biến cục bộ cần được lưu trong bộ nhớ.
• Giá trị thanh ghi cần bảo toàn.
• Tham số không được truyền hoàn toàn qua thanh ghi.
• Vùng nhớ tạm phục vụ tính toán.
• Dữ liệu phục vụ cơ chế gỡ lỗi hoặc xử lý ngoại lệ.

Tập hợp vùng nhớ và trạng thái phục vụ một lần thực thi hàm thường được gọi là khung ngăn xếp.

Cấu trúc cụ thể phụ thuộc vào kiến trúc CPU, quy ước gọi hàm, trình biên dịch và mức tối ưu.

Không phải mọi lời gọi hàm đều nhất thiết tạo ra một khung ngăn xếp riêng trong bộ nhớ. Tuy nhiên, nếu không được tối ưu, lời gọi đệ quy thường khiến nhiều trạng thái thực thi phải được duy trì đồng thời.

Ví dụ minh họa:

Ngăn xếp khi factorial(4) gọi xuống factorial(0)

┌─────────────────────────┐
│ factorial(0)            │
├─────────────────────────┤
│ factorial(1)            │
├─────────────────────────┤
│ factorial(2)            │
├─────────────────────────┤
│ factorial(3)            │
├─────────────────────────┤
│ factorial(4)            │
├─────────────────────────┤
│ Hàm gọi factorial(4)    │
└─────────────────────────┘

Đây là sơ đồ logic, không phải cách bố trí byte thực tế của một ABI cụ thể.

Khi độ sâu đệ quy tăng, số lượng trạng thái cần duy trì cũng có thể tăng theo.

Nếu mỗi lần gọi cần một lượng bộ nhớ ngăn xếp nhất định, tổng mức sử dụng có thể xấp xỉ:

Trong đó:

• $S(n)$: tổng dung lượng ngăn xếp liên quan đến chuỗi lời gọi.
• $S_0$: dung lượng ban đầu.
• $n$: số lần gọi đệ quy đang hoạt động.
• $F$: dung lượng trung bình cần duy trì cho mỗi lần gọi.

Đây là mô hình đơn giản hóa, phù hợp với trường hợp các khung có kích thước gần như cố định và chưa được tối ưu.

2. Đệ quy đuôi là gì?

2.1. Khái niệm vị trí đuôi

Vị trí đuôi (Tail Position) là vị trí trong quá trình đánh giá biểu thức mà kết quả của biểu thức đó được sử dụng trực tiếp làm kết quả của hàm hiện tại, không còn phép tính tiếp theo phải thực hiện sau khi biểu thức kết thúc.

Một lời gọi hàm ở vị trí đuôi được gọi là lời gọi đuôi (Tail Call).

Ví dụ:

int f(int x) {
    return gx;
}

Ở đây, lời gọi g$x$ nằm tại vị trí đuôi vì kết quả của g được trả về trực tiếp.

Ngược lại:

int f(int x) {
    return gx + 1;
}

Lời gọi g$x$ không nằm tại vị trí đuôi vì sau khi g trả về, hàm f vẫn phải thực hiện phép cộng với 1.

Điểm quyết định không phải là lời gọi hàm có xuất hiện ở dòng cuối hay không, mà là còn công việc nào phải thực hiện sau khi lời gọi kết thúc hay không.

2.2. Đệ quy đuôi

Đệ quy đuôi (Tail Recursion) là trường hợp một hàm tự gọi lại chính nó và lời gọi đó nằm tại vị trí đuôi.

Có thể viết lại hàm tính giai thừa bằng cách sử dụng biến tích lũy $Accumulator$:

unsigned long long factorial_acc(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return factorial_acc(n - 1, acc * n);
}

unsigned long long factorial(unsigned int n) {
    return factorial_acc(n, 1);
}

Khi gọi factorial(4), các trạng thái logic thay đổi như sau:

Tại mỗi bước, kết quả trung gian đã được tích lũy trong tham số acc.

Không cần giữ lại phép nhân để thực hiện sau khi lời gọi đệ quy trả về.

Lời gọi:

return factorial_acc(n - 1, acc * n);

nằm tại vị trí đuôi.

Vì vậy, hàm có cấu trúc phù hợp với tối ưu hóa đệ quy đuôi.

Ví dụ trên dùng số nguyên không dấu 64 bit theo cách biểu diễn thông thường của unsigned long long; kết quả chỉ còn chính xác trong phạm vi kiểu dữ liệu. Với hệ thống mà kiểu này có 64 bit, 20! còn biểu diễn được, còn 21! vượt phạm vi.

2.3. Đệ quy đuôi và lời gọi đuôi không đồng nhất

Lời gọi đuôi không bắt buộc phải là lời gọi đệ quy.

Ví dụ:

int process(int x) {
    return calculatex;
}

process gọi calculate ở vị trí đuôi, nhưng đây không phải đệ quy.

Trong khi đó:

int countdown(int n) {
    if n==0 {
        return 0;
    }

    return countdown(n - 1);
}

là đệ quy đuôi.

Do đó, cần sử dụng thuật ngữ chính xác:

3. Tối ưu hóa lời gọi đuôi là gì?

3.1. Nguyên lý

Tối ưu hóa lời gọi đuôi là kỹ thuật cho phép trình biên dịch thực hiện một lời gọi hàm ở vị trí đuôi mà không cần tiếp tục giữ trạng thái của hàm gọi như trong một chuỗi lời gọi thông thường.

Khi hàm gọi không còn công việc nào phải thực hiện sau lời gọi đuôi, trong những điều kiện thích hợp, trình biên dịch có thể kết thúc hoặc tái sử dụng trạng thái thực thi hiện tại trước khi chuyển quyền điều khiển sang hàm được gọi.

Ví dụ:

int f(int x) {
    return gx;
}

Trong cách thực hiện thông thường, có thể hình dung:

f gọi g
g thực hiện
g trả về f
f trả về hàm trước đó

Sau khi áp dụng tối ưu hóa lời gọi đuôi, quá trình có thể được tổ chức thành:

f chuẩn bị tham số cho g
f kết thúc hoặc giải phóng trạng thái không còn cần thiết
chuyển trực tiếp sang g
g trả về hàm đã gọi f

Như vậy, lời gọi g không nhất thiết cần một tầng ngăn xếp mới nằm phía trên khung thực thi còn hoạt động của f.

3.2. So sánh mức sử dụng ngăn xếp

Không tối ưu:

┌───────────────────┐
│ factorial_acc(0)  │
├───────────────────┤
│ factorial_acc(1)  │
├───────────────────┤
│ factorial_acc(2)  │
├───────────────────┤
│ factorial_acc(3)  │
├───────────────────┤
│ factorial_acc(4)  │
└───────────────────┘

Sau khi loại bỏ đệ quy đuôi:

┌──────────────────────────┐
│ Một trạng thái thực thi  │
│ factorial_acc            │
│                          │
│ n và acc được cập nhật   │
│ qua các vòng lặp         │
└──────────────────────────┘

Đối với kiểu tối ưu chuyển đệ quy thành vòng lặp và không sử dụng bộ nhớ phụ tăng theo độ sâu, dung lượng ngăn xếp của quá trình lặp có thể duy trì gần như không đổi.

Đây là lợi ích quan trọng nhất của kỹ thuật này.

3.3. Độ phức tạp bộ nhớ

Đối với hàm đệ quy có độ sâu tỷ lệ với $n$:

• Nếu mỗi lần gọi phải duy trì một khung riêng, mức sử dụng ngăn xếp thường là $O(n)$.
• Nếu đệ quy đuôi được loại bỏ thành vòng lặp với trạng thái có kích thước cố định, mức sử dụng ngăn xếp có thể là $O(1)$.

Tuy nhiên, $O(1)$ chỉ mô tả bộ nhớ ngăn xếp phục vụ cơ chế lặp trong những giả thiết nêu trên, không có nghĩa tổng bộ nhớ của mọi thuật toán đệ quy đuôi đều là hằng số.

Dữ liệu được cấp phát trên heap, cấu trúc tích lũy hoặc các đối tượng trung gian vẫn có thể sử dụng bộ nhớ tăng theo kích thước đầu vào.

4. Cơ chế loại bỏ đệ quy đuôi

4.1. Chuyển lời gọi đệ quy thành vòng lặp

Một trong những cách triển khai phổ biến của TRE là biến lời gọi tự đệ quy thành bước nhảy trở lại đầu hàm hoặc một khối lặp tương đương.

Xét hàm:

unsigned int sum_tail(
    unsigned int n,
    unsigned int acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

Về mặt logic, có thể chuyển đổi thành:

unsigned int sum_loop(
    unsigned int n,
    unsigned int acc
) {
    while n!=0 {
        acc += n;
        n -= 1;
    }

    return acc;
}

Trong phiên bản thứ hai, không còn lời gọi tự đệ quy.

Các giá trị trạng thái được cập nhật trực tiếp trong vòng lặp.

Bằng cách này, trình biên dịch không cần tạo thêm một trạng thái gọi hàm cho mỗi lần lặp.

4.2. Quá trình biến đổi ở mức biểu diễn trung gian

Trong trình biên dịch, mã nguồn thường được chuyển thành biểu diễn trung gian (Intermediate Representation – IR) trước khi sinh mã máy.

Hàm đệ quy đuôi có thể được biểu diễn bằng một khối chứa lời gọi tự đệ quy, sau đó là lệnh trả về.

Quá trình tối ưu có thể thay lời gọi bằng việc cập nhật trạng thái và chuyển quyền điều khiển về khối đầu hàm.

Tài liệu LLVM mô tả phép tối ưu tailcallelim như sau:

This file transforms calls of the current function (self recursion) followed by a return instruction with a branch to the entry of the function, creating a loop.

(Dịch nghĩa: Phép biến đổi này thay những lời gọi tự đệ quy của hàm hiện tại, theo sau bởi lệnh trả về, bằng bước nhảy đến điểm bắt đầu của hàm, qua đó tạo thành một vòng lặp.)

Nguồn: LLVM, LLVM's Analysis and Transform Passes, mục tailcallelim.^[1]

Ngoài trường hợp cơ bản, LLVM còn mô tả các khả năng như xử lý một số lệnh đơn giản nằm giữa lời gọi và lệnh trả về, hoặc sử dụng biến tích lũy trong những trường hợp phép toán cho phép chuyển đổi hợp lệ.

Điều đó cho thấy tối ưu hóa đệ quy đuôi không nhất thiết chỉ là việc thay trực tiếp một lệnh gọi hàm bằng một lệnh nhảy.

4.3. Ảnh hưởng đến mã máy x86-64

Trên kiến trúc x86-64, các lệnh thường gặp trong cơ chế gọi hàm bao gồm:

• call: Gọi hàm, đồng thời lưu thông tin địa chỉ trả về theo cơ chế của kiến trúc.
• ret: Trả quyền điều khiển về địa chỉ trả về.
• jmp: Chuyển quyền điều khiển trực tiếp đến một địa chỉ khác.

Xét đoạn mã minh họa:

extern int calculate(int x);

int process(int x) {
    return calculatex;
}

Trong trường hợp phù hợp về ABI và các điều kiện tối ưu khác, trình biên dịch có thể sinh mã tương tự:

process:
    jmp calculate

Thay vì:

process:
    call calculate
    ret

Sơ đồ này minh họa sự khác nhau về luồng điều khiển, không phải kết quả biên dịch được bảo đảm cho mọi trình biên dịch và mọi nền tảng.

Trong cách thực hiện dùng jmp, hàm calculate có thể trả kết quả trực tiếp về nơi đã gọi process, với điều kiện trạng thái máy đã được chuẩn bị phù hợp.

Trên thực tế, trình biên dịch có thể cần giải phóng vùng nhớ ngăn xếp, khôi phục thanh ghi hoặc sắp xếp lại tham số trước khi thực hiện bước nhảy.

4.4. Ảnh hưởng đến mã máy ARM64

Trên kiến trúc AArch64, những lệnh thường gặp gồm:

Thông thường, thanh ghi X30 được sử dụng làm thanh ghi liên kết (Link Register).

Với một lời gọi đuôi hợp lệ, trình biên dịch có thể thực hiện bước nhảy thay cho cơ chế gọi hàm thông thường.

Ví dụ mã máy minh họa:

process:
    b calculate

Thay cho dạng:

process:
    bl calculate
    ret

Trong trường hợp sử dụng B, trình biên dịch phải bảo đảm địa chỉ trả về ban đầu vẫn còn hợp lệ, đồng thời tuân thủ quy ước gọi hàm của nền tảng.

Cơ chế này có thể giúp tránh phát sinh thêm một tầng gọi hàm không cần thiết.

5. Điều kiện để áp dụng tối ưu hóa lời gọi đuôi

5.1. Lời gọi phải thực sự ở vị trí đuôi

Điều kiện đầu tiên là hàm gọi không còn công việc phải thực hiện sau khi lời gọi kết thúc.

Ví dụ có thể tối ưu:

int f(int x) {
    return gx;
}

Ví dụ không phải lời gọi đuôi:

int f(int x) {
    return gx * 2;
}

Trong ví dụ thứ hai, f vẫn phải thực hiện phép nhân.

Tuy nhiên, trình biên dịch có thể thực hiện những phép biến đổi khác để loại bỏ đệ quy trong một số trường hợp. Vì vậy, việc lời gọi ban đầu không nằm tại vị trí đuôi không đồng nghĩa với việc không tồn tại bất kỳ phương án tối ưu nào.

5.2. Phải tuân thủ quy ước gọi hàm

Quy ước gọi hàm (Calling Convention) xác định cách truyền tham số, trả kết quả và bảo toàn trạng thái máy khi chuyển quyền điều khiển giữa các hàm.

Các yêu cầu thường liên quan đến:

• Thanh ghi được dùng để truyền tham số.
• Thanh ghi phải được hàm gọi hoặc hàm được gọi bảo toàn.
• Cách truyền giá trị trả về.
• Vị trí của tham số truyền qua ngăn xếp.
• Yêu cầu căn chỉnh ngăn xếp.
• Cách xử lý đối số biến thiên.
• Cấu trúc dữ liệu trả về có kích thước lớn.

Một lời gọi có thể ở vị trí đuôi về mặt ngữ nghĩa, nhưng việc thực hiện nó dưới dạng bước nhảy trực tiếp vẫn có thể không hợp lệ nếu những yêu cầu ABI chưa được đáp ứng.

5.3. Vòng đời của biến cục bộ

Trong một số trường hợp, hàm được gọi có thể tiếp tục truy cập dữ liệu thuộc khung ngăn xếp của hàm gọi.

Ví dụ:

extern int use_pointer(const int *p);

int fvoid {
    int value = 10;
    return use_pointer(&value);
}

Ở đây, use_pointer nhận địa chỉ của biến cục bộ value.

Việc giải phóng khung ngăn xếp của f trước khi use_pointer kết thúc có thể khiến con trỏ không còn trỏ đến vùng nhớ hợp lệ.

Do đó, trình biên dịch không thể tùy tiện áp dụng phép biến đổi hủy khung gọi hiện tại nếu điều đó làm thay đổi vòng đời dữ liệu.

Đây là một ví dụ về giới hạn an toàn của tối ưu hóa lời gọi đuôi.

5.4. Trạng thái dọn dẹp và xử lý ngoại lệ

Một số ngôn ngữ và môi trường thực thi yêu cầu thực hiện công việc bổ sung khi thoát khỏi hàm.

Ví dụ:

• Chạy hàm hủy đối tượng.
• Giải phóng tài nguyên theo phạm vi.
• Thực hiện khối finally.
• Cập nhật trạng thái xử lý ngoại lệ.
• Thực hiện các thao tác bảo vệ ngăn xếp.

Nếu những thao tác này phải xảy ra sau khi lời gọi hàm kết thúc, lời gọi có thể không còn đủ điều kiện thực hiện như một tail call trực tiếp.

Một trình biên dịch có thể xử lý bằng các phép biến đổi khác khi hợp lệ, nhưng tính đúng đắn ngữ nghĩa luôn phải được duy trì.

5.5. Giới hạn của nền tảng

Ngay cả khi mã nguồn có cấu trúc phù hợp, việc tối ưu vẫn có thể phụ thuộc vào:

• Kiến trúc CPU.
• ABI của hệ điều hành.
• Backend sinh mã.
• Mức tối ưu.
• Quy ước gọi hàm.
• Kiểu dữ liệu trả về.
• Các thuộc tính đặc biệt của hàm.

Vì vậy, không thể khẳng định rằng mọi hàm đệ quy đuôi đều tự động được chuyển thành vòng lặp trong mọi trình biên dịch.

6. Tối ưu hóa đệ quy đuôi trong GCC và LLVM

6.1. GCC

GCC cung cấp tùy chọn:

-foptimize-sibling-calls

Tài liệu GCC mô tả:

Optimize sibling and tail recursive calls.

(Dịch nghĩa: Tối ưu hóa các lời gọi hàm ngang cấp và những lời gọi đệ quy đuôi.)

Theo tài liệu GCC 14.3, tùy chọn này được bật tại các mức tối ưu -O2, -O3 và -Os.^[2]

Ví dụ:

gcc -O2 -S example.c -o example.s

Lệnh trên yêu cầu GCC sinh mã hợp ngữ để có thể kiểm tra kết quả tối ưu.

Việc bật tùy chọn không bảo đảm mọi lời gọi đuôi đều được tối ưu thành công. Quyết định cuối cùng còn phụ thuộc vào điều kiện hợp lệ của từng lời gọi và khả năng của backend.

6.2. LLVM

LLVM hỗ trợ nhiều cơ chế liên quan đến lời gọi đuôi.

Trong LLVM IR, lời gọi có thể mang những dấu hiệu như:

Ví dụ minh họa LLVM IR:

define i32 @f(i32 %x) {
entry:
  %result = tail call i32 @g(i32 %x)
  ret i32 %result
}

declare i32 @gi32

Dấu hiệu tail không phải sự bảo đảm tuyệt đối rằng mã máy cuối cùng sẽ thực hiện lời gọi theo dạng tối ưu.

Đối với musttail, LLVM đặt ra những điều kiện nghiêm ngặt hơn về vị trí lời gọi, kiểu hàm, quy ước gọi hàm và các thuộc tính ảnh hưởng ABI.

Tài liệu ngôn ngữ LLVM quy định rằng musttail phải được tối ưu phù hợp để bảo đảm tính đúng đắn của chương trình; đặc biệt, chuỗi đệ quy thông qua các lời gọi musttail hợp lệ không được gây tăng trưởng ngăn xếp không giới hạn chỉ vì những lời gọi đó.^[3]

6.3. Đệ quy đuôi được bảo đảm và đệ quy đuôi có thể tối ưu

Cần xác định sự khác nhau giữa ba trường hợp:

Trường hợp thứ nhất: Mã nguồn có cấu trúc đệ quy đuôi, nhưng ngôn ngữ không yêu cầu trình biên dịch tối ưu.

Trường hợp thứ hai: Trình biên dịch nhận diện lời gọi đuôi và tối ưu khi điều kiện cho phép.

Trường hợp thứ ba: Ngôn ngữ hoặc cơ chế IR đặt ra yêu cầu bảo đảm lời gọi đuôi, trong phạm vi các điều kiện được quy định.

Điều này đặc biệt quan trọng đối với những chương trình sử dụng đệ quy sâu như một cơ chế điều khiển chính.

6.4. Ngôn ngữ Scheme và đệ quy đuôi đúng nghĩa

Scheme là một ví dụ quan trọng vì đặc tả ngôn ngữ có yêu cầu rõ ràng về đệ quy đuôi đúng nghĩa (Proper Tail Recursion).

Báo cáo R5RS nêu:

Implementations of Scheme are required to be properly tail-recursive.

(Dịch nghĩa: Các bản triển khai của ngôn ngữ Scheme bắt buộc phải hỗ trợ đệ quy đuôi đúng nghĩa.)

Nguồn: Revised⁵ Report on the Algorithmic Language Scheme, mục 3.5.^[4]

Trong Scheme, hỗ trợ đệ quy đuôi không chỉ là một lựa chọn cải thiện hiệu năng, mà là một phần trong yêu cầu về hành vi của bản triển khai.

Đặc tả yêu cầu hỗ trợ số lượng không bị giới hạn trước của các lời gọi đuôi đang hoạt động, trong ý nghĩa kỹ thuật được định nghĩa bởi ngôn ngữ.

Điều đó không có nghĩa chương trình có bộ nhớ vô hạn, mà là chuỗi lời gọi đuôi không được buộc phải tiêu thụ thêm không gian chỉ để duy trì những tầng tiếp diễn không cần thiết.

7. Tác động đến hiệu năng và bộ nhớ

7.1. Bộ nhớ ngăn xếp

Tác động nổi bật nhất của tối ưu hóa lời gọi đuôi là hạn chế sự gia tăng bộ nhớ ngăn xếp.

Khi chuyển một chuỗi tự đệ quy đuôi thành vòng lặp, chương trình có thể tránh việc duy trì nhiều khung gọi hàm đồng thời.

Đây là lợi ích quan trọng đối với:

• Thuật toán xử lý chuỗi có độ dài lớn.
• Bộ thông dịch và máy ảo.
• Các thuật toán duyệt cấu trúc dữ liệu.
• Những ngôn ngữ lập trình hàm.
• Các hệ thống sử dụng hàm như đơn vị điều khiển thay cho vòng lặp.

7.2. Chi phí gọi hàm

Khi loại bỏ được lời gọi hàm thông thường, trình biên dịch có thể giảm một phần chi phí liên quan đến:

• Lưu và khôi phục địa chỉ trả về.
• Thiết lập hoặc tháo dỡ khung ngăn xếp.
• Bảo toàn một số thanh ghi.
• Chuyển quyền điều khiển qua nhiều tầng gọi.

Tuy nhiên, mức cải thiện thực tế phụ thuộc vào kiến trúc CPU, mã máy được sinh và đặc điểm chương trình.

Không phải mọi lời gọi đuôi được tối ưu đều nhanh hơn đáng kể so với lời gọi thông thường.

7.3. Độ phức tạp thời gian

Đối với ví dụ tính giai thừa, việc chuyển từ đệ quy thông thường sang đệ quy đuôi không làm thay đổi số phép nhân cần thực hiện.

Độ phức tạp thời gian vẫn là:

Nếu được chuyển thành vòng lặp, độ phức tạp bộ nhớ ngăn xếp có thể giảm từ $O(n)$ xuống $O(1)$, trong điều kiện mỗi bước chỉ duy trì một lượng trạng thái cố định.

Như vậy, tối ưu hóa lời gọi đuôi chủ yếu cải thiện cơ chế thực thi và mức sử dụng tài nguyên, chứ không nhất thiết thay đổi độ phức tạp thời gian của thuật toán.

8. Những giới hạn và vấn đề cần lưu ý

8.1. Không phải mọi đệ quy đều là đệ quy đuôi

Ví dụ:

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

Lời gọi đệ quy không nằm tại vị trí đuôi vì vẫn còn phép nhân sau khi nhận kết quả.

Một trình biên dịch có thể nhận diện và biến đổi một số dạng đệ quy như thế này, nhưng không thể xem đó là thuộc tính mặc định của mọi trình biên dịch.

8.2. Đệ quy đuôi không đồng nghĩa với không bao giờ tràn ngăn xếp

Nếu một bản triển khai không thực hiện tối ưu hóa, một hàm đệ quy đuôi vẫn có thể tạo ra chuỗi lời gọi làm tăng mức sử dụng ngăn xếp.

Ngoài ra, chương trình còn có thể sử dụng ngăn xếp cho những hoạt động khác.

Vì vậy, cần xem xét cả hình thức mã nguồn lẫn bảo đảm của trình biên dịch và môi trường thực thi.

8.3. Tối ưu hóa có thể làm thay đổi cách quan sát khi gỡ lỗi

Khi lời gọi hàm được thay bằng bước nhảy hoặc vòng lặp, chuỗi lời gọi quan sát được trong trình gỡ lỗi có thể khác với cấu trúc hàm ban đầu.

Một số khung gọi có thể không xuất hiện như khi biên dịch ở chế độ không tối ưu.

Điều này có thể ảnh hưởng đến:

• Việc quan sát ngăn xếp lời gọi (Call Stack).
• Theo dõi thứ tự thực hiện hàm.
• Phân tích thông tin khung gọi.
• Đọc kết quả lấy mẫu hiệu năng.

Các trình biên dịch và công cụ gỡ lỗi có thể sử dụng thông tin bổ sung để hỗ trợ việc quan sát mã đã tối ưu, nhưng không phải lúc nào cũng tái hiện được đầy đủ chuỗi lời gọi theo mã nguồn.

8.4. Tối ưu hóa lời gọi đuôi không thay thế mọi hình thức tối ưu khác

Các kỹ thuật như nội tuyến hàm $Inlining$, lan truyền hằng số (Constant Propagation), loại bỏ mã chết (Dead Code Elimination) và tối ưu vòng lặp vẫn có thể tác động đến cùng một đoạn chương trình.

Một hàm đệ quy có thể được biến đổi bởi nhiều phép tối ưu kết hợp.

Do đó, khi phân tích mã máy, không nên mặc nhiên gán mọi trường hợp không còn lời gọi đệ quy cho một phép tối ưu duy nhất.

9. Kiểm chứng tối ưu hóa trong thực tế

9.1. Chương trình thử nghiệm

Có thể sử dụng đoạn mã sau:

__attribute__((noinline))
unsigned long long sum_tail(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

int mainvoid {
    return sum_tail(10, 0) != 55;
}

Thuộc tính noinline trong GCC hoặc Clang được dùng để hạn chế việc hàm bị nội tuyến, giúp quan sát riêng mã của hàm rõ hơn.

Tuy nhiên, thuộc tính này không cấm các tối ưu hóa khác, bao gồm việc loại bỏ đệ quy đuôi.

9.2. Biên dịch bằng GCC

gcc -O0 -S test.c -o test_O0.s
gcc -O2 -S test.c -o test_O2.s

Sau đó, so sánh mã hợp ngữ của hàm sum_tail.

Ở mức tối ưu thấp, mã thường giữ lại lời gọi tự đệ quy.

Ở mức tối ưu cao, trình biên dịch có thể chuyển hàm thành vòng lặp và không còn lời gọi tự đệ quy.

Kết quả cụ thể phụ thuộc vào phiên bản GCC, kiến trúc đích và các tùy chọn biên dịch.

9.3. Biên dịch bằng Clang

clang -O0 -S test.c -o test_O0.s
clang -O2 -S test.c -o test_O2.s

Có thể kiểm tra biểu diễn LLVM IR:

clang -O2 -S -emit-llvm test.c -o test.ll

Khi đọc kết quả, cần tìm những dấu hiệu như:

• Khối lặp thay thế lời gọi đệ quy.
• Lời gọi đuôi được đánh dấu trong IR.
• Lệnh nhảy thay cho chuỗi gọi và trả về trong mã máy.
• Sự thay đổi trong việc thiết lập khung ngăn xếp.

Đây là các dấu hiệu cần phân tích cùng nhau, thay vì chỉ dựa vào sự xuất hiện của một lệnh cụ thể.

10. Kết luận

Tối ưu hóa lời gọi đuôi là một kỹ thuật quan trọng trong thiết kế và triển khai trình biên dịch.

Kỹ thuật này khai thác đặc điểm của những lời gọi hàm không còn công việc phải thực hiện sau khi kết thúc, từ đó cho phép loại bỏ việc duy trì những trạng thái gọi hàm không cần thiết.

Trong trường hợp đệ quy đuôi, trình biên dịch có thể chuyển lời gọi tự đệ quy thành vòng lặp, giúp giảm mức sử dụng bộ nhớ ngăn xếp và tránh sự gia tăng số lượng khung gọi theo độ sâu đệ quy.

Tuy nhiên, khả năng tối ưu phụ thuộc vào nhiều điều kiện, bao gồm cấu trúc chương trình, vòng đời dữ liệu, quy ước gọi hàm, ABI và khả năng của backend sinh mã.

Sự khác nhau giữa lời gọi đuôi, đệ quy đuôi, tối ưu hóa lời gọi đuôi và loại bỏ đệ quy đuôi là cơ sở cần thiết để hiểu đúng cơ chế này.

Đối với nghiên cứu trình biên dịch, kỹ thuật tối ưu hóa lời gọi đuôi cũng là ví dụ tiêu biểu cho mối quan hệ giữa ngữ nghĩa ngôn ngữ lập trình, biểu diễn trung gian, phân tích luồng điều khiển và quá trình sinh mã máy.

---

Phụ lục A. Thuật ngữ kỹ thuật

Phụ lục B. Tài liệu tham khảo và nghiên cứu mở rộng

B.1. Đặc tả và tài liệu trình biên dịch

[1] LLVM Project, LLVM's Analysis and Transform Passes.

Mục tailcallelim giải thích phép biến đổi lời gọi tự đệ quy thành vòng lặp và một số mở rộng của thuật toán.

https://llvm.org/docs/Passes.html

[2] GNU Compiler Collection, Optimize Options.

Tài liệu về tùy chọn -foptimize-sibling-calls, mức tối ưu và những phép tối ưu liên quan.

https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html

[3] LLVM Project, LLVM Language Reference Manual.

Đặc tả ngôn ngữ LLVM IR, bao gồm dấu hiệu tail, musttail, notail, các quy ước gọi hàm và điều kiện tối ưu lời gọi đuôi.

https://llvm.org/docs/LangRef.html

[4] Clang Project, Attribute Reference.

Tài liệu về thuộc tính musttail, những điều kiện áp dụng và bảo đảm của trình biên dịch.

https://clang.llvm.org/docs/AttributeReference.html

B.2. Ngôn ngữ lập trình và ngữ nghĩa lời gọi đuôi

[5] Richard Kelsey, William Clinger và Jonathan Rees (biên tập), Revised⁵ Report on the Algorithmic Language Scheme, 1998.

Mục 3.5, Proper Tail Recursion, trình bày yêu cầu chính thức về đệ quy đuôi đúng nghĩa trong Scheme.

https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html

[6] Guy L. Steele Jr. và Gerald Jay Sussman, Lambda: The Ultimate Imperative, MIT Artificial Intelligence Laboratory, AI Memo 353, 1976.

Một công trình quan trọng trong lịch sử nghiên cứu ngôn ngữ Scheme, cơ chế tiếp diễn và các phương pháp thực thi lời gọi hàm.

B.3. Đặc tả kiến trúc và quy ước gọi hàm

[7] Arm Limited, Procedure Call Standard for the Arm 64-bit Architecture $AAPCS64$.

Đặc tả quy ước gọi hàm trên AArch64, bao gồm sử dụng thanh ghi, truyền tham số và tổ chức trạng thái khi gọi hàm.

https://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst

[8] System V Application Binary Interface, AMD64 Architecture Processor Supplement.

Đặc tả ABI dành cho x86-64 theo môi trường System V, bao gồm quy ước gọi hàm, thanh ghi và bố trí ngăn xếp.

https://gitlab.com/x86-psABIs/x86-64-ABI

[9] Intel, Intel 64 and IA-32 Architectures Software Developer's Manuals.

Tài liệu chính thức về tập lệnh x86, bao gồm CALL, RET và JMP.

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

B.4. Các chủ đề nghiên cứu tiếp theo

• Khung ngăn xếp (Stack Frame): Cấu trúc và vòng đời.
• Tràn ngăn xếp (Stack Overflow): Nguyên nhân và cơ chế.
• Giao diện nhị phân ứng dụng $ABI$: Các quy ước gọi hàm.
• Biểu diễn trung gian $IR$: Phân tích và tối ưu luồng điều khiển.
• Bộ liên kết $Linker$: Vai trò trong quá trình biên dịch và thực thi chương trình.

---

Chú thích