强制 RIP 相对寻址?

Forcing RIP-relative addressing?

有没有办法强制编译器或汇编器只生成 RIP 相对寻址代码?

我正在尝试找到一种方法来提供从传统编程模型到图灵完备抽象计算模型的映射。

这似乎与你在
评论中的讨论有关 Is C actually Turing-complete? 在 cs.SE 上(在你发布之前我最近碰巧看到了)。

请注意,PC-relative 寻址并不能帮助您实现无限存储。所需的数据大小可以是大于代码大小的无限量,因此 PC-relative 寻址的偏移量部分需要是无限大小。 (而且它通常只能用于静态存储。)

我以为你是在建议使用相对于它们自己的地址(而不是代码)的指针,对于像 x86-64 这样的传统 ISA,这仍然需要无限的寄存器宽度,所以你也可以使用 Random Access Machine 计算的抽象模型。 x86-64 需要寄存器中的整个绝对地址,或者至少 2 个部分总和为绝对地址。 ([base + idx*scale] 其中 scale 是 2 位左移)。 add rdi, [rdi] 向指针添加 pointed-to 偏移量(如 C ptr += *ptr),但仍需要将结果放入寄存器。


如果你的意思是阻止编译器对静态数据使用绝对内存寻址,那么是的,这很简单,使用 gcc -fPIE-fPIC

但是,如果您的意思是仅使用 [rip + rel32] 寻址,则永远不要 [reg] 或通用 [base + idx*scale + disp0/8/32] 替代 [=18 的任何子集=],那么不,当然不适用于 real-world 编译器。 RIP-relative 寻址只能访问静态存储,因此将自己局限于此将意味着没有堆栈 space 和指针。 x86-64 仅 RIP-relative 寻址模式是 [rip + rel32],其中 rel32 是嵌入机器代码中的常量,而不是寄存器值。

(也许你可以使用self-modifying代码来修改RIP+rel32寻址模式的rel32,但没有主流编译器会这样做。你如何管理re-entrancy for stack space 只有一个你正在修改的函数的机器代码副本,但也许在堆栈 space 中保留正确的数据会让你恢复调用者的 rel32 偏移量)。

在 hand-written asm 中,你当然可以做任何你想做的事,但限制自己重写 rel32 位移使得它(严格来说?)不如 vanilla x86-64 强大,而不是更图灵完备。


如果您正在寻找像 [PC + other_register] 这样的寻址模式,我认为 32 位 ARM 有。它具有索引寻址,程序计数器可作为 16 个 general-purpose 寄存器之一访问(与 AArch64 不同)。这样你就可以对静态数组进行 PC-relative 索引。同样,这并不是说这有任何明显的帮助。对于固定 PC 上的任何给定指令来寻址无限数量的内存位置中的任何一个,“其他寄存器”必须具有无限宽度。


无界Turing-complete C:

我相信这是不可能的,除非你放宽语言以消除每个类型(包括指针)都有一些提前决定的固定宽度的事实,而不是基于你要处理的输入的大小。

A Turing-complete C 实现可以在循环中调用 malloc 无限次,例如使用 fgets 读取输入行并在每一行到达具有标准递归方法的二叉树。使用基于 C 指针的标准节点布局:
struct node { struct node *left, *right; const char *str; };。然后遍历那棵树并按排序顺序输出行。

要使树正常工作,任何现有节点都需要能够指向 newly-allocated 注释。 Section-relative 据我所知,寻址并不能使您更接近于此。这个 binary-tree 示例可能是无界 C 的一个很好的试金石,涉及到根据输入进行排列的其他对象的指针。


您在评论中描述的似乎是在 x86 asm 中编写 UTM 状态机的本地部分,每个状态都有自己的 2GiB 内存 space 并且能够向前或向后跳到下一个状态.没有明确的方法来获得真正的随机访问或真正的指针,只能在一种状态的代码中。

对 UTM 的每个步骤使用有限的 C 实现不会给你一个整体 Turing-complete C 实现,它给你一个图灵机 tape-like non-random-access 当你的问题规模超过了你在一个“状态”或“记忆库”或任何你称之为的情况下可以做的事情时。