Modern Compiler Implementation in ML – Having issues with the register allocator wanting to coalesce the frame pointer and various temporaries

huangapple go评论68阅读模式
英文:

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指令技巧,我认为这对这个问题也适用。

我按照书中的算法实现了代码。可能我犯了一个错误,但我不这么认为。这是我的代码:

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

非常感谢您的帮助。

英文:

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:

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

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.

huangapple
  • 本文由 发表于 2023年8月9日 11:04:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/76864314.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定