assembly - x86-64 奇怪地将堆栈用于局部变量
问题描述
我正在学习 x86-64,并且正在使用一些我最了解的编译器生成的汇编代码。它是一个递归阶乘程序,它调用自身直到达到一个基数,其中 1 被放置在 rax 中,而 rax 又与每个先前递减的计数值相乘。我理解变量访问上下文中的对齐,其中访问未对齐的数据需要大量成本,我认为对齐的文本段大致相同。
在程序中,有两个标记点让我感到困惑,第一个在rdi寄存器的递减中使用三个堆栈分配的局部变量空间之一,该寄存器保存用户提供的数字来计算阶乘。为什么不直接使用 rax 替换:
mov qword [rbp + - 16]
和
mov rdi, rax?.
第二个是在执行每个阶乘乘法时使用其他两个堆栈局部变量,然后执行看似冗余的操作,其中乘法的结果从 rax 移入局部变量,然后在函数返回之前返回 rax .
mov qword [rbp + -24], rax
mov rax, rdi
imul rax, qword [rbp + -24]
mov qword [rbp + -8], rax
mov rax, qword [rbp + -8]
使用任何未触及的通用寄存器并省略这些堆栈局部变量,这些计算不会快得多,还是这些操作是 16 字节对齐的一部分?
rec:
push rbp
mov rbp, rsp
sub rsp, 24
push rbx
push r12
push r13
push r14
push r15
.sec0:
mov qword [rbp + -8], 1
test rdi, rdi
je .sec1
.sec2:
mov rax, rdi
sub rax, 1
mov qword [rbp + -16], rax ;; point 1.0
push rcx
push rdx
push rsi
push rdi
push r8
push r9
push r10
push r11
mov rdi, qword [rbp + -16] ;; point 1.1
call rec
pop r11
pop r10
pop r9
pop r8
pop rdi
pop rsi
pop rdx
pop rcx
mov qword [rbp + -24], rax ;; point 2.0
mov rax, rdi
imul rax, qword [rbp + -24] ;; point 2.1
mov qword [rbp + -8], rax ;; point 2.2
mov rax, qword [rbp + -8] ;; point 2.3
pop r15
pop r14
pop r13
pop r12
pop rbx
leave
ret
.sec1:
mov rax, qword [rbp + -8]
pop r15
pop r14
pop r13
pop r12
pop rbx
leave
ret
解决方案
你没有说这个例子是从什么代码生成的,或者在什么编译器上生成的,但它必须非常粗糙,甚至可能是来自本科编译器类的一些玩具编译器。你是对的,这是非常次优的。即使是gcc
我测试过的最旧版本,在所有优化关闭的情况下,也不会产生那么糟糕的代码。让我们看看当我们用几个不同的编译器编译时我们得到了什么。比较的一个好方法是在godbolt。
我测试了以下代码:
unsigned long long factorial(const unsigned long long n)
{
return (n <= 1) ? 1
: n*(factorial(n-1));
}
该factorial()
函数是您描述的简单的单行递归实现。我还写factorial_tail()
了一个带有累加器的尾递归版本,以使某些编译器更容易注意到该函数是尾递归模关联运算,因此可以自动转换为紧密循环。
但是,现代编译器通常对此非常聪明。
除了-fomit-frame-pointer
(抑制保存和恢复堆栈帧)之外没有其他优化,这就是 gcc 8.2 所做的:
factorial:
sub rsp, 24
mov QWORD PTR [rsp+8], rdi
cmp QWORD PTR [rsp+8], 1
jbe .L2
mov rax, QWORD PTR [rsp+8]
sub rax, 1
mov rdi, rax
call factorial
imul rax, QWORD PTR [rsp+8]
jmp .L4
.L2:
mov eax, 1
.L4:
add rsp, 24
ret
您仍然可以看到该函数将中间结果保存在堆栈中,紧邻 8 字节返回地址的上方,并在堆栈中进行了一些不必要的复制。这样做的目的是,在调试时,临时值存在于离散的内存位置,并且可以被观察、检查和修改。
你会问,“使用任何未触及的通用寄存器并省略这些堆栈局部变量 [...],这些计算不会快得多吗?” 好想法!确实会!您不能只将阶乘的每个因子保存在不同的寄存器中,因为可能有数十亿。但是您可以自动重构代码,直到您只需要恒定的暂存空间。
在生产代码中,您将打开优化。出于学习目的,针对空间优化的代码比针对速度完全优化的代码更容易理解,后者通常更长更复杂。有了gcc -std=c11 -g -Os -mavx
,我们得到了这个:
factorial:
mov eax, 1
.L3:
cmp rdi, 1
jbe .L1
imul rax, rdi
dec rdi
jmp .L3
.L1:
ret
GCC 足够聪明地计算出,因为乘法是关联的并且有一个恒等式, (4 × (3 × (2 × 1))) = 1 × 4 × 3 × 2 × 1。因此,它可以保持运行总和产品从左到右(4,然后 12,然后 24)并call
完全消除。该代码只是一个紧密循环,几乎与for
用高级语言编写循环所得到的相同。
如果您使用 优化时间而不是空间-O3
,GCC 将尝试对循环进行矢量化,具体取决于您是否给它一个标志,例如-mavx
. 其他关于最大优化的编译器展开循环但不使用向量指令。
Clang 7.0.0 使用相同的标志生成更长的一条指令的稍快代码,因为它知道足以检查是否在结束时终止循环,而不是跳回然后在开始时检查。我更喜欢这个代码而不是 GCC 的。
factorial: # @factorial
mov eax, 1
cmp rdi, 2
jb .LBB0_2
.LBB0_1: # =>This Inner Loop Header: Depth=1
imul rax, rdi
dec rdi
cmp rdi, 1
ja .LBB0_1
.LBB0_2:
ret
MSVC 19.0 无法确定将该转换应用于该代码,并且仍然使用 生成递归代码call
,但我们可以通过重构和添加显式累加器参数来给出提示:
unsigned long long factorial_tail(const unsigned long long n,
const unsigned long long p)
/* The n parameter is the current value counted down, and the p parameter
* is the accumulating product. Call this function with an initial value
* of p = 1.
*/
{
return (n <= 1) ? p
: factorial_tail( n-1, n*p );
}
这个版本是明确的尾递归的,每个现代编译器都知道尾调用消除。这编译/Ox /arch:avx
为:
factorial_tail PROC
mov rax, rdx
cmp rcx, 1
jbe SHORT $LN4@factorial_
mov rdx, rcx
imul rdx, rax
dec rcx
jmp factorial_tail
$LN4@factorial_:
ret 0
您在不同的代码清单中观察到,“这似乎是一个冗余操作,其中乘法的结果从 rax 移动到局部变量,然后在函数返回之前返回到 rax。” 事实上,在循环的每次迭代中都是如此。它没有意识到,已经将正在运行的产品放到rax
,它可以而且应该把它放在那里。
英特尔的编译器 19.0.1 也无法判断它可以转换factorial()
为循环,但可以使用factorial_tail()
. 使用-std=c11 -g -avT -Os
,这会产生比 MSVC 更好的代码,并且与 clang 非常相似:
factorial_tail:
cmp rdi, 1 #14.16
jbe ..B2.5 # Prob 12% #14.16
..B2.3: # Preds ..B2.1 ..B2.3
imul rsi, rdi #15.44
dec rdi #15.39
cmp rdi, 1 #14.16
ja ..B2.3 # Prob 88% #14.16
..B2.5: # Preds ..B2.3 ..B2.1
mov rax, rsi #14.16
ret
它意识到它应该避免在循环的迭代之间将值从一个寄存器复制到另一个寄存器。相反,它选择将其保留在其初始位置rsi
(第二个函数参数)并将返回值移动到rax
最后一次。
推荐阅读
- ruby-on-rails - Ruby Gem 项目——雷神生成器导致只读文件系统错误
- javascript - 如何返回“onclick”属性?
- c++ - 取消引用 nullptr 类对象
- macos - Clion 找不到使用自制软件安装的库
- sql-server-2012 - 获取“两天前”日期sql server
- c++ - OpenCV C++ 在 Macbook M1 芯片中给出架构 arm64 错误
- jenkins - 如何在groovy中的数组中获取正确的正则表达式
- html - Puppeteer 屏幕未正确垂直居中 flexbox 项目
- api - 比较 JMETER 断言中的 ISO 时间
- typescript - TypeScript - 描述一个可变长度的数组,但至少有一个特定的强制条目