【汇编】Tail Call Elimination

概述：Tail Call Elimination（尾调用消除）是一种编译优化技术，旨在减少因函数调用而产生的栈空间使用，特别是在递归调用或尾调用频繁的场景中。

参考文章：

• CodeMachine - Article - X64 Deep Dive

1. Tail Call Elimination

尾调用是指一个函数在其返回语句中调用另一个函数，且该调用是该函数的最后一条指令。尾调用消除（TCO）则是一种编译器优化技术，它能够在不增加调用栈深度的情况下，将尾调用转化为一种类似于跳转（goto）的操作，从而避免在调用栈上创建新的栈帧。

X64编译器可以通过将函数的最后一次调用替换为跳转到被调用方来优化该调用。这避免了为被调用方设置堆栈帧的开销。调用方和被调用方共享相同的堆栈帧，被调用方直接返回给调用方的调用方。当调用方和被调用方具有相同的参数时，这尤其有益，因为如果相关参数已经在所需的寄存器中，并且这些寄存器没有更改，则不必重新加载它们。

图 1 显示了在调用 Function4时 Function1中的尾部调用消除。Function1跳转到 Function4，当 Function4完成执行时，它直接返回到 Function1的调用方。

调用过程大致如下所示：

2. 原理

简单说就是减少创建堆栈的过程

在传统的函数调用中，每当一个函数被调用时，都会在调用栈上创建一个新的栈帧来保存函数的局部变量、参数以及返回地址等信息。而在尾调用的情况下，由于被调用的函数是调用函数的最后一条指令，且调用函数在被调用函数返回后没有其他操作需要执行，因此理论上可以不需要保存调用函数的栈帧信息。

编译器在检测到尾调用时，会优化这个调用过程，使其不再在调用栈上创建新的栈帧，而是直接复用当前栈帧，将参数和返回地址等信息更新为被调用函数所需的信息，并跳转到被调用函数的执行入口。这样，当被调用函数返回时，就可以直接返回到调用函数的调用者处，而不需要再经过调用函数的栈帧。

3. 说明

这里以快速排序为例

参考文章：Tail Call Elimination - GeeksforGeeks

常规的写法如下所示，通过递归调用最终达到对整个数据排序的目的。

/* Tail recursive function for QuickSort 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 
		/* pi is partitioning index, arr[p] is now 
		at right place */
		int pi = partition(arr, low, high); 

		// Separately sort elements before 
		// partition and after partition 
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
}

这里就可以考虑使用 Tail Call Elimination 来进行替换优化

/* QuickSort after tail call elimination 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
start: 
	if (low < high) 
	{ 
		/* pi is partitioning index, arr[p] is now 
		at right place */
		int pi = partition(arr, low, high); 

		// Separately sort elements before 
		// partition and after partition 
		quickSort(arr, low, pi - 1); 

		// Update parameters of recursive call 
		// and replace recursive call with goto 
		low = pi+1; 
		high = high; 
		goto start; 
	} 
} 
// See below link for complete running code 
// https://ide.geeksforgeeks.org/dbq4yl 

这么做的目的是为了让编译器可以识别到尾调用消除。添加 start 标签，并且在尾部添加 goto 即可。

4. 尾部调用消除的堆栈管理

递归使用堆栈来跟踪函数调用。每次函数调用时，一个新的帧被推送到包含本地变量和调用数据的堆栈上。假设一个堆栈帧需要 O (1) ，即常量内存空间，那么对于 N 个递归调用内存需要 O (N)。

尾调用消除降低了从 O (N)到 O (1)的递归的空间复杂度。当函数调用被消除时，不会创建新的堆栈帧，函数将在常量内存空间中执行。

函数可以在常量内存空间中执行，因为在尾递归函数中，在调用语句之后没有语句，所以不需要保留父函数的状态和框架。子函数被调用并立即完成，它不必将控制返回给父函数。

由于不会对返回的值执行任何计算，也不会留下任何语句供执行，因此可以根据当前函数调用的要求修改当前框架。因此，不需要保留以前函数调用的堆栈帧，函数在常量内存空间中执行。这使得尾部递归更快，内存友好。