英文:
Modern Compiler Implementation in ML - Having issues with the register allocator wanting to coalesce the frame pointer and various temporaries
问题
我无法完全理解为什么寄存器分配器认为帧指针是一个适合节点合并的候选对象 - 它应该会干扰到每个其他临时变量,因此涉及帧指针的任何移动都应受到限制。例如,这是从 merge.tig
中的 isdigit
函数生成的汇编代码(包括合并的移动指令):
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]
当然,你可以硬编码以确保不会考虑与帧指针相关的任何移动指令进行合并,但这并不是一个优雅的解决方案。如何使寄存器分配器意识到在这种情况下合并是不安全的呢?通常情况下,它不会尝试使用帧指针,因为我使用了书中教授的“sink instruction” 技巧,我认为这也适用于这种情况。
我按照书中的确切算法实施了代码。可能我犯了错误,但我认为不是这样。以下是代码链接:
非常感谢你提前的帮助。
英文:
I can't quite figure out why the register allocator considers the frame pointer a good candidate for node coalescing - it should interfere with every other temporary and therefore any move involving the frame pointer should be constrained. For example, here is the generated assembly for the function isdigit
from merge.tig
(including the coalesced moves):
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
Specifically, this part:
L8:
mov r13, 1
mov rbp, rbp
add rbp, 16
mov r10, qword [rbp]
This is going to mess up the stack when the leave
instruction is executed. Without coalescing, it looks something like this:
L8:
mov r13, 1
mov r10, rbp
add r10, 16
mov r10, qword [r10]
Of course, you could hardcode it so that no move instructions related to the frame pointer are ever considered for coalescing but that's an inelegant solution. How can I make the register allocator realize that it's not safe to coalesce in this case? Normally, it does not attempt to use the frame pointer since I use the sink instruction trick taught in the book, which I assumed would work for this too.
I implemented the algorithm exactly as written in the book. It's possible I made a mistake but I don't think so. Here is the code:
Thanks very much in advance.
答案1
得分: 0
我发现了问题,这只是一个愚蠢的错误。我不小心使用了一个有向图而不是无向图作为干扰图,所以来自Ocamlgraph库的mem_edge
函数没有报告正确的干扰。
英文:
I've discovered the problem, it was just a silly mistake. Have accidentally been using a directed graph for the interference graph rather than an undirected one, so the mem_edge
function from the Ocamlgraph library wasn't reporting correct interferences.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论