Tyl*_*den 3 algorithm optimization assembly encoding
[底部加粗的问题]
当汇编程序生成二进制编码时,它需要决定是使每个分支变长还是短,如果可能的话,短路更好.汇编程序的这一部分称为分支位移优化(BDO)算法.一种典型的方法是汇编程序使所有分支编码变短(如果它们小于某个阈值),然后迭代地增加任何分支跳转到未到达的long.当然,这可以导致其他分支转换为跳远.因此,汇编程序必须不断通过跳转列表,直到不再需要升迁.这种二次时间方法对我来说似乎是一种最优算法,但据推测BDO是NP完全的,这种方法实际上并不是最优的.
兰德尔海德提供了一个反例:
.386
.model flat, syscall
00000000 .code
00000000 _HLAMain proc
00000000 E9 00000016 jmpLbl: jmp [near ptr] target
00000005 = 00000005 jmpSize = $-jmpLbl
00000005 00000016 [ byte 32 - jmpSize*2
dup
(0)
00
]
0000001B target:
0000001B _HLAMain endp
end
通过在括号"[near ptr]"中添加部分并强制进行5字节编码,二进制实际上最终会变短,因为分配的数组比跳跃大小的两倍小.因此,通过使跳转编码更短,最终代码实际上更长.
这对我来说似乎是一个非常病态的情况,并不是真正相关的,因为分支编码仍然较小,它只是对程序的非分支部分的这种奇怪的副作用,导致二进制变大.由于分支编码本身仍然较小,我并不认为这是"开始小"算法的有效反例.
我可以将start-small算法视为最佳BDO算法,还是存在一个实际情况,即它不能为所有分支提供最小的编码大小？
j_random_hacker 的论点是 Start Small 对于没有填充的简化情况来说是最佳的，这听起来很合理。但是，在优化大小的函数之外，它并不是很有用。 真正的 asm确实有ALIGN指令，而且确实有所作为。
这是我可以构建的最简单的例子，其中 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 必须很长才能达到目标 1。
如果 B0 很长，它会将 target1 推得更靠近 B1，从而允许到达短编码。
所以 B0 和 B1 中最多有一个可以有短编码，但哪个是 short 很重要。短 B0 意味着多 3 个字节的对齐填充，不节省代码大小。长 B0 允许短 B1确实节省了总代码大小。在我的示例中，我已经说明了可能发生的最简单的方法：将 B1 之后的代码末尾推送到下一个对齐的边界。它也可能影响其他分支，例如需要对分支进行长编码.loop。
Start-Small 结果：B0 短，B1 长。（它们的初始第一遍状态。）Start-Small 不会尝试延长 B0 和缩短 B1 以查看它是否减少了总填充，或者只是执行的填充（理想情况下由行程计数加权）。
之前的 4 字节 NOP.loop和之前的31 字节 NOP another_func，因此它从 开始0x400160而不是0x400140我们从使用jz near .target0中获得的 ，这导致 B1 的编码很短。
请注意， B0 本身的长编码并不是实现 B1 短编码的唯一方法。对之前的任何指令进行比必要更长的编码.target1也可以解决问题。（例如 4B 位移或立即数，而不是 1B。或不必要或重复的前缀。）
不幸的是，我所知道的没有一个汇编程序支持这种填充方式；仅与nop. 可以使用哪些方法有效地扩展现代 x86 上的指令长度？
通常，NOP在循环开始时甚至没有跳过 long- ，因此更多的填充可能会降低性能（如果需要多个 NOP，或者代码在像 Atom 或 Silvermont 这样的 CPU 上运行真的很慢）有很多前缀，因为汇编器没有针对 Silvermont 进行调整而得到使用）。
请注意，编译器输出很少在函数之间跳转（通常仅用于尾调用优化）。x86 没有短编码call。手写 asm 可以为所欲为，但意大利面条式代码（希望如此？）在大规模上仍然不常见。
我认为对于大多数 asm 源文件，BDO 问题很可能可以分解为多个独立的子问题，通常每个函数都是一个单独的问题。这意味着即使是非多项式复杂度算法也可能是可行的。
一些有助于解决问题的捷径会有所帮助：例如，检测何时肯定需要长编码，即使所有中间分支都使用短编码。当唯一连接它们的是两个远程函数之间的尾调用时，这将允许打破子问题之间的依赖关系。
我不确定从哪里开始真正开始制定算法来找到全局最优解。如果我们愿意考虑扩展其他指令来移动分支目标，搜索空间是相当巨大的。但是，我认为我们只需要考虑交叉对齐填充的分支。
可能的情况是：
如果我们将微架构优化的一些知识嵌入到汇编器中，那么做好这方面的工作可能会更容易：例如，始终尝试让分支目标开始于 16B insn 获取块的开始附近，而绝对不是在最后。Intel uop 缓存线只能缓存一个 32B 块内的 uop，因此 32B 边界对于 uop 缓存很重要。L1 I$ 行大小为 64B，页面大小为 4kiB。（不过，汇编器不会知道哪些代码是热的，哪些是冷的。热代码跨越两页可能比代码大小稍大的更糟糕。）
对于 Intel 和 AMD 而言，在指令解码组的开头使用多 uop 指令也比在其他任何地方使用它要好得多。（对于带有 uop 缓存的 Intel CPU 而言，情况更糟）。弄清楚 CPU 大部分时间将通过哪条路径执行代码，以及指令解码边界在哪里，可能远远超出了汇编程序的管理能力。
这里有一个证据表明,在评论中没有harold提到的异常跳跃时,"start small"算法是最佳的:
首先,让我们确定"从小开始"总是产生一个可行的解决方案 - 也就是说,一个不包含太长跳跃的短编码的解决方案.该算法基本上等于反复询问"它是否可行？"的问题.如果没有,则加长一些跳转编码,如果它终止则清楚,那么它产生的解决方案必须是可行的.由于每次迭代都会延长一些跳跃,并且跳转不会超过一次,因此该算法最终必须在最多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中 - - 能够减少i的跳跃位移,因此,由于我的位移高于阈值但是其编码没有被Y延长,Y甚至不可行!不可行的解决方案不是最优的,因此在Y中存在这样的非延长指令i将与Y是最优的假设相矛盾 - 意味着不存在这样的i.