有没有可能在大会上不使用“jump”和“goto”来做决定？

Question

在这个问题中，一些答案表明，不使用“if”语句就可以做出决策，但我怀疑这是可能的，因为“if”不是生成跳转指令的唯一语句。

给定一种固定的编译语言（在示例C中），生成的程序集是否可以在不使用跳转和转到指令的情况下执行某种决策？

请给出一个简单的if/else语句的替代示例，在肯定回答的情况下，该语句不使用此类说明。

Answer 1

假设您指的是x86，

1. 条件移动（cmov）如前所述

所有这些都允许在寄存器中获得决策结果（cmp*），在寄存器中可以通过移位和结果进行进一步操作。

这主要用于创建没有分支的函数返回值，或用于流处理的特定形式（例如，基于SSE2的图像二值化）。它实际上不是分支的通用替代品。

Answer 2

有关编写无分支代码（cmov/其他谓词执行、cmp/setcc、将标志复制到GP寄存器等）的简单“正常”方法列表，请参阅@Marco van de Voort的答案。这形成了一个构建块，用于制作无分支版本的东西，而使用分支可以做得更好。

当你说“做决定”时，听起来你真的在问这样一台机器是否可以完全编程。

计算机科学中计算理论的一部分是计算不同的计算模型有多强大。这并不是一个模型有多有效，而是它能计算出什么。我怀疑，没有条件分支指令的寄存器机器在性能上不等同于图灵机，即通用计算机。（即使您允许非间接无条件分支）。

更新：x86的mov指令是图灵完备的，即使没有自修改代码，只需使用正常的索引寻址模式。您还需要围绕加载和存储序列进行循环。待办事项：重写此答案中因该原因而无效的部分。这增加了没有自修改代码的无条件分支的价值（例如，让IP在真实模式下环绕，或在没有jmp的情况下执行此操作的其他奇怪技巧，见下文）。

我认为只有图灵机才是在x86的寄存器和内存中模拟另一台机器，因此，与x86的IP分支不同，通用寄存器中的值的行为类似于正在分支的程序计数器。（或正在遍历磁带的图灵机）

您可以创建非常精简的体系结构，这些体系结构仍然是通用计算机，但我从目前为止看到的情况来看，任何类似于注册机的计算模型（如x86、ARM等）都需要某种版本的条件分支才能成为通用计算机。

另请参阅这个问题：解决计算机程序问题的最小指令集，特别是维基百科的“单指令集计算机”文章中的位操作机部分；它最不象一个条件分支，但仍然做同样的工作。

我对计算理论知之甚少，无法对无条件分支（在x86或ARM等注册机上）可以计算的内容给出准确的界限或形式化描述，但我可以说：

我可以说，给定足够的指令空间，您可以对数组进行排序，但可能只有在为该数组长度生成正确的指令序列时。使用cmov等无分支技术，您可以基于比较有条件地交换两个内存位置。一个好的算法选择是排序网络。

您可以完全展开任何已知长度的循环，也可以通过展开所需的最大迭代次数来处理可变长度的循环。当循环计数器超过数组末尾时，可以使用无分支技术从虚拟地址加载/存储。（例如，使用cmov将指针设置为指向一个小的静态数组，该数组只存在用于存储垃圾，而不影响其他任何内容。您的代码将始终执行相同的固定数量的存储，但使用不同的输入，这些存储中的不同存储可以进入垃圾场。）ARM谓词执行任何指令意味着您可以在不需要静态转储的情况下执行条件存储。

完全展开合并排序应该可以很好地工作，因为对于给定的数组大小，它总是执行相同的工作量。另一方面，快速排序将非常不方便，因为工作量随数据和分区的选择而变化。此外，它有一个O（n^2）最坏的情况，所以您至少需要那么多代码。

由于您必须完全展开任何要运行的内容，这意味着您需要知道它将运行多长时间。这意味着您无法实现完整的图灵机，因为并非所有图灵机都会停止。（更不用说，不可能存在一个决定任何给定图灵机是否停止的算法）。

自我修改代码可能会提高这方面的效率，但如果仍然不允许重写自己的机器代码以包含分支指令，我认为这不会提高计算能力。（我们必须排除SMC生成任何类型的分支，而不仅仅是条件分支指令，因为我们可以有条件地生成无条件分支指令。）

我认为固定循环中的SMC可能比循环中的非自修改代码更强大，即使SMC不允许生成跳转指令。有关无分支指令循环的一些疯狂想法，请参见下文（例如计时器中断和IP环绕）。

仅使用无条件跳转（无条件跳转），可以创建循环来处理与无跳转相同问题的任意大小版本。但是你的程序不能终止。如果有某种“终止程序”指令，将其放入循环将使其成为非循环。

因此，您最终可能得到的是一个程序，它最终对一个数组进行了排序（或者无论它的工作是什么），并且可能它通过在某个地方存储“true”来表明这一事实，并在不影响数据的情况下保持循环（使用无分支条件代码）。您可以将其视为具有“传输触发”的退出函数，因此它可以有条件地使用。

更多的方法来模拟无条件跳转，这样你就可以创建一个循环，我认为增加了自我修改代码的力量。（即使你从使用这种力量有条件地分支副歌）。

函数调用指令很容易被滥用来实现纯跳转，因此我们显然希望排除它们。

在x86上，您可以使用call跳转到仅弹出堆栈返回地址而不是永远返回的代码。（因此您可以实现循环）。要使用x86的间接call指令构建条件分支，您可以使用无分支技术（如cmov）将调用后的指令或不同的目标获取到寄存器中，然后运行call rax。或者更简单地说，将eax设置为0或1（例如从setcc），您可以运行call[target_tablerax*8]在分支的两个目标之间进行选择。

类似地，ret很容易被滥用为间接跳转：推送地址，然后运行ret。（现实生活中不要这样做：CPU针对正确的调用/ret嵌套进行了优化，它们不匹配会导致返回地址预测器堆栈错误预测未来的ret。）

中断导致CPU跳转到中断处理程序。软件中断（如x86的int 0x80指令，或ARMsvc/swi）同步跳转到中断处理程序，因此它们实际上只是一个函数全部（以及模式切换到内核模式）。

这意味着int是我们需要排除的另一条跳转指令。但我们也可以使用计时器中断来循环。中断处理程序是循环的顶部。执行您想要的任何工作量，然后重新启用中断。之后执行NOPs；下一个计时器中断最终将触发。或者在为中断提供服务时启用中断的机器上：将循环体的工作量限制在计时器中断之间始终可以容纳的工作量，即使在最坏的缓存行为下也是如此。

软件生成中断的另一种方法是运行非法指令。通过有条件地生成非法指令，自修改代码可以有条件地分支到非法指令中断处理程序。或通过有条件地除以0，有条件地分支到除法错误处理程序。由于可以设置该中断处理程序的地址（例如，通过在x86上存储到中断向量/描述符表中），因此可以使用存储和除以0有条件地分支到任意地址。（不过，您的所有分支目标都需要做任何必要的事情来重新启用可触发的中断）。

让程序计数器绕过去：在平面内存冯·诺依曼体系结构的机器上，这需要自修改代码来跟踪程序状态，因为没有不作为代码执行的内存。

在分段x86（例如16位实模式）中，IP将从0xFFFF环绕到0x0000。因此，循环是整个代码段，在其他段中有单独的数据存储。您只能使用远jmp或远调用（或中断/中断返回）修改CS，因此您不能像pop CS那样跳转（因为与其他pop段寄存器指令不同，pop CS不存在）。

有趣的事实：代码段末尾的最后一条指令不必以0xFFFF结尾。e、 g.多字节指令可以从0xFFFF开始，到0x04结束。如果从不同的起点解码，可以编写以不同方式执行的x86机器代码，但这在这里并不有用。（这对你的能力造成了巨大的限制）。

ARM使程序计数器可以作为普通的通用寄存器访问，因此您可以使用sub r15、#1024或其他东西进行控制流，技术上不使用分支或任何类型的调用（bl）或返回指令。不过，您仍然在直接修改程序计数器，因此它实际上只是一条分支指令。（pc是r15的另一个名称）。

Answer 3

ARM架构有一个有趣的条件执行特性。在完全ARM模式下运行，几乎每条指令都可以附加一个条件。这些与Branch指令上使用的条件相同。诸如add r0， r0，#15之类的指令将始终执行，但诸如addeq r0， r0，#15之类的指令仅在设置了零标志时才会执行。使用分支的等效项是：

    beq afteradd       ; skip add if equal
    add r0, r0, #15    ; add 15 to R0
afteradd:

在使用Thumb-2的内核上运行时，条件执行会受到更多限制，但仍然可以使用IT指令。此指令将在不使用分支的情况下创建“if-then”构造。IT构造实际上是ARM统一汇编语言的一部分，无论您是为ARM还是Thumb-2编写，都应该使用它。这是上面条件添加的UAL版本。

it eq                 ; if equal
addeq r0, r0, #15     ; then add 15 to r0

IT构造可以包含多条指令。使用指令中的一系列T和E指令，可以添加更多条件指令。在下面的示例中，如果设置了零标志，我们将向R0加15，否则我们将从R0减去15。从字面上看，ITE的意思是“如果不是”。以下第一条指令的条件应与您的ITE条件相匹配，然后第二条指令将变为“else”，并且应具有与ITE条件相反的条件。

ite eq                ; if equal
addeq r0, r0, #15     ; then add 15 to r0
subne r0, r0, #15     ; else subtract 15 from r0

我想这种方法确实使用if，这可能与你的要求背道而驰。但在执行方面，这实现了if，而不使用跳转。