assembly - 编译为汇编时最小化跳转量

Question

假设我们已经将一些程序编译为某种抽象中间语言:我们的程序是一系列操作和决定(分支)下一个要执行的操作(基本上是一棵树)。示例:

a();
if (bla) then c();
else b(); d();
e();

现在我们需要将此序列“打包”到我们的线性内存中，通过这样做，我们的代码必须分支(有条件或无条件)。例如，其中一种可能性:

      CALL A
      TEST bla
      BRANCH else
      CALL C
      JMP esc
else: CALL B
      CALL D
esc:  CALL E

当然，如何在线性存储器中排列这些 block 有多种可能性，并且它们的分支/跳转数量都不同。我们的目标是尽量减少它们。
问题:
a) 这个问题怎么称呼？它有一个通用的名称吗？ (是BDD构建的一个实例吗？)
b) 这个问题的复杂度是多少(找到一个 block 的排列使得跳转/分支的数量最小)？

Answer 1

你拥有的是一堆基本 block ，它们在每个基本 block 的末尾将控制权从一个 block 传递到另一个 block 。

您可以使用有向图轻松对此进行建模。节点是基本 block 。从一个节点到另一个节点的有向弧表示(wlog)从一个 block 到另一个 block 的条件分支(有时条件为“真”)。您应该将引发的异常视为分支，并将捕获处理程序视为 block 。

线性化一系列 block 本质上是选择一系列弧。这样的序列以不执行任何分支的 block 结束(例如，函数返回或应用程序退出)。

您想要做的是选择一组弧序列(想象一下您将这些弧着色为蓝色)，以使剩余的弧(将它们想象为红色)最少。

我不知道复杂性是多少，但由于可以说每个节点都有两个选择，因此看起来难度呈指数级增长。 (在最坏的情况下，您可以拥有一个完全连接的图。通常推理此类图的成本非常昂贵)。

我希望人们可以用一种贪婪的方案来实现这一点并获得相当好的结果:重复找到最长的弧序列，将其着色为蓝色。

最大顺序化可能不是您真正想要的。想象一下，我们根据分析数据、算法知识、异常罕见因此概率较低的假设，甚至程序员提供的提示，为每个弧赋予一个概率。现在你想要的是具有最大概率的长弧链；这样的路径在文献中被称为“踪迹”。这确保了代码中的热路径在内存中是连续的，从而最大化了指令缓存的值(value)。以这种方式定义的失序分支概率较低，例如冷路径。

您仍然有相同的复杂性选择。但贪婪方案可能效果更好:通过简单地从序列中已有的每个节点中选择最高概率的弧来形成序列。

通过对弧序列进行着色，可以轻松地以“正确”的顺序生成代码。

这个paper更正式地讨论使用跟踪的“代码放置”，特别是为了减少缓存未命中的成本。它讨论了一个贪婪的选择过程，它产生了相当好的结果，以及一个更复杂但相当昂贵的时间“本地搜索”方案，它产生了出色的结果。