问为什么分支位移的“启动小”算法不是最优的？

EN

这里有一个证据表明，在没有哈罗德在评论中提到的异常跳跃的情况下，“开始小”算法是最优的：

首先，让我们确定“从小开始”总是产生一个可行的解决方案--也就是说，一个不包含任何太长的跳跃的短编码的解决方案。这个算法实质上相当于反复问“它可行吗？”如果不是的话，延长一些跳转编码，所以如果它终止了，那么它产生的解决方案就必须是可行的。由于每次迭代都会延长一些跳转，而且跳转也不会超过一次，因此该算法在最多nJumps迭代后必须最终终止，因此解决方案必须是可行的。

现在假设相反，该算法可以产生一个次优解X，设Y是一些最优解。我们可以将解决方案表示为被延长的跳转指令的子集。我们知道X \Y >= 1 --也就是说，X中至少有1条指令延长，而不是在Y中--因为否则X将是Y的一个子集，而且由于Y在假设下是最优的，并且X是已知可行的，因此X= Y，这意味着X本身就是一个最优解，这将与我们关于X的最初假设相矛盾。

从X\ Y中的指令中，选择I作为"start small“算法首先加长的指令，并让Z是Y(和X的子集)的子集，该子集由算法在此之前已经加长的所有指令组成。由于“开始小”算法决定延长I的编码，所以在那个时间点(即，在延长Z中的所有指令之后)，我的跳跃位移太大，不能进行短编码。(请注意，虽然Z中的一些加长可能将我的跳跃位移推过临界点，但这绝不是必要的--也许我的位移从一开始就超过了阈值。)我们所能知道的，也就是我们需要知道的是，当Z被处理完时，我的跳跃位移已经超过了阈值。)但是现在回顾一下最优解Y，并注意到Y中的其他任何一个加长--即Y\Z --都不能降低我的跳跃位移，所以，既然我的位移超过了阈值，但是它的编码没有被Y延长，甚至是不可行的！不可行的解不可能是最优解，因此Y中这样一个非加长指令i的存在将与Y是最优的假设相矛盾--这意味着没有这样的我可以存在。

对于没有填充听起来合理的简化情况，J_random_hacker的论点从小开始是最佳的。但是，在优化大小函数之外，它并不是很有用。Real does 具有指令，而执行E 212E 113使E 214有所不同。

这里是一个最简单的例子，我可以构造一个案例，在这种情况下，Start Small没有给出最佳结果(用NASM和YASM测试)。jz near .target0 使用强制长编码，提前移动 another_function: 32字节，并减少 func**.**中的填充。

func:
.target0:               ; anywhere nearby
    jz  .target0        ; (B0)  short encoding is easily possible
.target1:
   times 10 vpermilps xmm14, xmm15, [rdi+12345]
        ; A long B0 doesn't push this past a 32B boundary, so short or long B0 doesn't matter
ALIGN 32
.loop:
   times 12 xor r15d,r15d
    jz  .target1         ; (B1)  short encoding only possible if B0 is long
   times 18 xor r15d,r15d
    ret   ; A long B1 does push this just past a 32B boundary.

ALIGN 32
another_function:
    xor  eax,eax
    ret

• 如果B0短，那么B1必须很长时间才能到达target1。
• 如果B0是长的，它会使target1更接近B1，允许短编码到达。

因此，最多只能有一个B0和B1可以有一个短编码，但是重要的是哪个是短。一个短的B0意味着增加3个字节的对齐填充，而不节省代码大小.允许短B0的长B1确实节省了总代码大小。在我的示例中，我演示了最简单的方法:在B1之后将代码的末尾推过下一个对齐的边界。它还可能影响其他分支，例如，需要对分支进行长时间编码到.loop。

• 理想: B0 long，B1 short。
• 开始-小结果: B0短，B1长.(他们最初的第一关状态。)Start-Small不尝试延长B0和缩短B1以查看它是否减少了总体填充，或者只是执行了填充(理想情况下按trip计数加权)。 在.loop之前有一个4字节的NOP，在another_func之前有31个字节的NOP，所以它从0x400160开始，而不是我们使用jz near .target0获得的0x400140，这导致了对B1的简短编码。

注意到，B0本身的长编码是而不是，实现B1短编码的唯一方法。在.target1之前，对任何指令进行长时间的编码也可以做到这一点。(例如，4B位移或立即移动，而不是1B。或不必要的或重复的前缀。)

不幸的是，我所知道的没有一个汇编程序支持这种填充方式；只支持nop。What methods can be used to efficiently extend instruction length on modern x86?

通常，在循环开始时甚至不会跳过长NOP，因此更多的填充可能会降低性能(如果需要多个NOPs，或者代码运行在Atom或Silvermont这样的CPU上，由于没有为Silvermont进行调优而使用的前缀非常少)。

注意，编译器输出很少有函数之间的跳转(通常只是为了尾部调用优化)。x86没有call的短编码。手工编写的asm可以做它想做的任何事情，但是意大利面代码是(希望？)在大范围内还是不常见的。

我认为，对于大多数asm源文件，很可能会将BDO问题分解成多个独立的子问题，通常每个函数都是一个独立的问题。这意味着即使是非多项式复杂度的算法也是可行的。

一些帮助解决问题的快捷方式会有所帮助:例如，检测何时确实需要长编码，即使所有中间的分支都使用短编码。这将允许打破子问题之间的依赖关系，当连接它们的唯一东西是两个遥远的函数之间的尾部调用。

我不知道从哪里开始做一个算法来找到一个全局最优解。如果我们愿意考虑扩展其他指令来移动分支目标，搜索空间是相当大的。然而，我认为我们只需要考虑交叉排列的分支-填充。

可能出现的情况如下：

• 在向后分支的分支目标之前填充
• 前向分支的分支指令之前填充

如果我们将一些关于微体系结构优化的知识嵌入到汇编程序中，做好这方面的工作可能会更容易一些:例如，总是尝试让分支目标在16Binsn提取块开始时开始，但在最后绝对不是正确的。Intel uop缓存线只能从一个32B块中缓存uop，因此32B边界对于uop缓存非常重要。L1 I$行大小为64B，页面大小为4 4kiB。(但是汇编程序不知道哪个代码是热的，哪个是冷的。有两个页的热代码跨度可能比稍微大一点的代码大小更糟糕。)

对于英特尔和AMD来说，在指令解码组开始时拥有多个uop指令也比在其他任何地方拥有多uop指令要好得多。(对于具有uop高速缓存的Intel CPU则不是这样)。找出CPU大部分时间都要通过代码的路径，以及指令解码边界将在哪里，这可能远远超出了汇编程序所能管理的范围。