编译为汇编时最小化跳转次数

Question

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

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

现在我们需要 "pack" 这个序列到我们的线性内存，这样做，我们的代码必须分支（有条件的和无条件的）。例如，其中一种可能性：

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

如何在线性内存中排列这些块当然有多种可能性，而且它们的数量都不同branches/jumps。我们的目标是尽量减少它们。
问题：
a) 这个问题怎么称呼？它有一个通用名称吗？（是BDD构造的实例吗？）
b) 这个问题的复杂度是多少（找到一个块的排列使得 jumps/branches 的数量最少）？

Answer 1

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

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

线性化一系列块本质上是选择一系列弧线。这样的序列以没有分支的块结束（例如，函数 return 或应用程序退出）。

您要做的是选择一组弧序列（假设您将这些涂成蓝色），使剩余的弧（假设这些涂成红色）最少。

我不知道复杂性是什么，但由于可以说您在每个节点都有两个选择，所以它似乎呈指数级增长。（在最坏的情况下，你可以有一个完全连接的图。通常对这样的图进行推理是非常昂贵的）。

我希望可以用一个贪婪的方案来实现它并得到很好的结果：重复找到最长的弧序列，将其涂成蓝色。

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

您仍然有同样复杂的选择。但是贪婪方案可能会更好：通过简单地从序列中已经存在的每个节点中选择最高概率的弧来形成序列。

有了彩色的圆弧序列，就很容易按"right"顺序生成代码。

此 paper 更正式地讨论了 "code placement" 使用跟踪，特别是为了减少缓存未命中的成本。它讨论了一个贪婪的选择过程，它产生了很好的结果，以及一个更复杂但相当昂贵的时间明智的 "local search" 方案产生了很好的结果。

编译为汇编时最小化跳转次数

Minimize amount of jumps when compiling to assembly

compiler-construction

assembly

compilation