编译为程序集时最小化跳转的数量

假设我们已经编译了一些程序给了一些抽象的中间语言：我们的程序是执行下一个操作（基本上是一棵树）的一系列操作和决策（分支）。例如：编译为程序集时最小化跳转的数量

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

当然也有关于如何安排线性存储这些块的多种可能性，他们都在分行的量不同/跳跃。我们的目标是尽量减少它们。
问题：
a）如何调用这个问题？有一个通用名称吗？（这是BDD构建的一个实例吗？）
b）这种问题的复杂性是什么（寻找块的排列使得跳转/分支的数量最小）？

来源

2016-09-21 artemonster

你有什么是一堆基本块，在每个基本块的末尾将控制权从一个控制到另一个。

您可以使用有向图很容易地对此进行建模。节点是基本块。从一个节点到另一个节点的定向弧代表（wlog）从一个块到另一个块的条件分支（有时条件为“真”）。您应该考虑将异常提升为分支，并将处理程序视为块。

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

你想要做的是选择一组弧形序列（想象你将这些蓝色染色），使其余的弧线（想象成红色）最小。

我不知道复杂性是什么，但由于您可以在每个节点上有两个选择，它看起来像指数级的困难。（在最坏的情况下，你可以有一个完全连通的图表，通常对这样的图表进行推理非常昂贵）。

我期望一个人可以用贪婪的方案来实现它，并获得相当不错的结果：重复查找最长的弧序列，将其着色为蓝色。

最大顺序化可能不是你真正想要的。想象一下，基于概要分析数据，算法知识，假设异常很少出现，因此概率很低，甚至程序员提供了提示，我们将概率附加到每个弧上。现在你想要的是具有最大概率的长弧链。这种路径在文献中被称为“痕迹”。这确保代码中的热路径在内存中是连续的，从而最大化指令高速缓存的值。以这种方式定义的偏序分支是低概率的，例如冷路径。

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

由于弧序列有颜色，因此很容易以“正确”的顺序生成代码。

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

来源

2016-09-21 10:20:30

编译为程序集时最小化跳转的数量

回答

相关问题