ML 中的现代编译器实现 - 想要合并帧指针和各种临时变量的寄存器分配器存在问题

Question

我不太明白为什么寄存器分配器认为帧指针是节点合并的良好候选者 - 它应该干扰所有其他临时对象，因此涉及帧指针的任何移动都应该受到限制。例如，以下是从

isdigit

生成的函数

merge.tig

的程序集（包括合并的移动）：

L2_isdigit:
push rbp
mov rbp, rsp
push rbx
push r12
push r13
mov r10, rdi
L69:
mov r10, rbp
add r10, 16
mov r10, qword [r10]
mov r10, qword [r10+16]
add r10, -8
mov r10, qword [r10]
mov rdi, r10
call ord
mov r10, rax
mov r10, r10
mov r12, r10
mov r10, L4
mov rdi, r10
call ord
mov r10, rax
mov r10, r10
cmp r12, r10
jge L8
L9:
mov r10, 0
L10:
mov rax, r10
jmp L68
L8:
mov r13, 1
mov rbp, rbp
add rbp, 16
mov r10, qword [rbp]
mov r10, qword [r10+16]
add r10, -8
mov r10, qword [r10]
mov rdi, r10
call ord
mov r10, rax
mov r10, r10
mov r12, r10
mov r10, L5
mov rdi, r10
call ord
mov r10, rax
mov r10, r10
cmp r12, r10
jle L6
L7:
mov r13, 0
L6:
mov r10, r13
jmp L10
L68:
pop r13
pop r12
pop rbx
leave
ret 8

具体来说，这部分：

L8:
mov r13, 1
mov rbp, rbp
add rbp, 16
mov r10, qword [rbp]

执行

leave

指令时，这会弄乱堆栈。如果没有合并，它看起来像这样：

L8:
mov r13, 1
mov r10, rbp
add r10, 16
mov r10, qword [r10]

当然，您可以对其进行硬编码，以便不考虑与帧指针相关的移动指令进行合并，但这是一个不优雅的解决方案。我怎样才能让寄存器分配器意识到在这种情况下合并是不安全的？通常，它不会尝试使用帧指针，因为我使用了书中教授的接收器指令技巧，我认为这也适用于此。

我完全按照书上写的实现了算法。我可能犯了一个错误，但我不这么认为。这是代码：

https://github.com/BridgeTheMasterBuilder/tiger/blob/6fbadef26a58a605b2e25dbfaeda9f80dc5f59f1/lib/backend/color.ml#L73

提前非常感谢。

Answer 1

我发现了问题，这只是一个愚蠢的错误。不小心使用了有向图作为干扰图，而不是无向图，因此 Ocamlgraph 库中的

mem_edge

函数没有报告正确的干扰。