问强迫RIP-相对地址？

EN

这似乎与你在评论中的讨论有关

C实际上是图灵完整的吗？ on cs.SE (在您发布这篇文章之前，我碰巧看到了它)。

请注意，PC相对寻址并不能帮助您实现无界存储。所需的数据大小可以大于代码大小，因此PC相对寻址的偏移部分需要无界大小。(它通常只能用于静态存储。)

我以为您建议的指针是相对于它们自己的地址(而不是代码)的指针，对于x86-64这样的传统ISA，它仍然需要无界寄存器宽度，所以您最好使用随机存取机抽象计算模型。x86-64需要寄存器中的全部绝对地址，或者至少有2部分与绝对地址相加。([base + idx*scale]，标度为2位左移位)。add rdi, [rdi]向指针添加了一个指向偏移量(如C ptr += *ptr)，但仍然需要结果才能适应寄存器。

如果您的意思是停止编译器对静态数据使用绝对内存寻址，那么是的，这很容易，可以使用gcc -fPIE或-fPIC。

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

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

在手工编写的asm中，你当然可以做任何你想做的事情，但是限制自己重写rel32位移会使它(严格地？)没有香草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; };。然后遍历该树，并按排序顺序输出行。

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

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

对于UTM的每一步使用有限的C实现并不能给出一个完整的图灵化C实现，它给你一个图灵机一个类似磁带的非随机访问，当你的问题大小超过了你在一个“状态”或“内存库”内所能做的，或者你称之为什么。