0

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

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

4

1 回答 1

5

这似乎与您在评论中的讨论有关
C 实际上是图灵完备的吗？在 cs.SE 上（在您发布此内容之前，我最近碰巧看到了）。

请注意，PC 相对寻址不能帮助您实现无限存储。所需的数据大小可以是比代码大小更大的无限量，因此 PC 相对寻址的偏移部分需要具有无限大小。（而且它通常只用于静态存储。）

我以为您建议使用相对于它们自己的地址（而不是代码）的指针，对于像 x86-64 这样的传统 ISA，这仍然需要无限制的寄存器宽度，因此您不妨只使用随机存取机抽象计算模型. x86-64 需要寄存器中的整个绝对地址，或至少 2 个部分总和为绝对地址。（[base + idx*scale]其中 scale 是 2 位左移）。 add rdi, [rdi]将指向的偏移量添加到指针（如 C ptr += *ptr），但仍需要将结果放入寄存器中。

如果您的意思是阻止编译器对静态数据使用绝对内存寻址，那么是的，这很容易，使用gcc -fPIEor -fPIC.

但是，如果您的意思是仅 [rip + rel32]使用寻址，从不使用或通用替代[reg]的任何子集，那么不，当然不适用于现实世界的编译器。 RIP 相对寻址只能访问静态存储，因此限制自己将意味着没有堆栈空间和指针。 x86-64 唯一的 RIP 相对寻址模式是rel32 是嵌入在机器代码中的常量，而不是寄存器值。[base + idx*scale + disp0/8/32][RIP + rel32][rip + rel32]

（也许您可以使用自修改代码来修改rel32RIP+rel32 寻址模式，但没有主流编译器会这样做。仅使用一个函数机器的一个副本来管理堆栈空间的重入性并不明显您正在修改的代码，但也许将正确的数据保留在堆栈空间中可以让您恢复调用者的 rel32 偏移量）。

在手写 asm 中，你当然可以做任何你想做的事情，但是限制自己重写 rel32 位移使它（严格来说？）不如 vanilla x86-64 强大，而不是图灵完备。

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

无限图灵完备 C：

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

图灵完备的 C 实现可以malloc无限次地循环调用，例如读取输入fgets行并在每行到达时使用标准递归方法将每行添加到二叉树中。使用基于 C 指针的标准节点布局：
struct node { struct node *left, *right; const char *str; };. 然后稍后遍历该树并按排序顺序输出行。

要使树工作，任何现有节点都需要能够指向新分配的 note。据我所知，相对于部分的寻址并没有让您更接近这一点。这个二叉树示例可能是无界 C 的一个很好的试金石，涉及指向其他对象的指针，其排列取决于输入。

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

对 UTM 的每个步骤使用有限的 C 实现并不能为您提供整体图灵完备的C 实现，当您的问题大小超出您可以在其中执行的范围时，它会为您提供具有类似磁带的非随机访问的图灵机“状态”或“记忆库”或任何你称之为的东西。

于 2020-08-26T01:10:48.777 回答