编译到汇编时最大限度地减少跳转量

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

关于如何在线性存储器中布置这些块当然有多种可能性,并且它们在分支/跳跃量方面都不同.我们的目标是尽量减少它们.
问题:
a)如何调用此问题？它有一般的名称吗？(它是BDD构造的一个实例吗？)
b)这种问题的复杂性是什么(找到一个块的排列,使得跳跃/分支的数量最小)？

Answer 1

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

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

线性化一系列块实际上是选择一系列弧.这样的序列以不具有分支的块结束(例如,功能返回或应用程序退出).

你想要做的是选择一组弧序列(想象你将这些蓝色着色),使剩余的弧(想象这些为红色)是最小的.

我不知道复杂性是什么,但是因为你可以说每个节点有两个选择,所以它似乎是指数级的难度.(在最坏的情况下,你可以有一个完全连接的图.通常推理这些图是非常昂贵的).

我希望人们可以用贪婪的方案实现这个并获得相当好的结果:重复找到最长的弧序列,将其颜色变为蓝色.

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

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

弧色序列着色后,很容易以"正确"的顺序生成代码.

该论文论述了"代码布局"使用痕迹更正式,尤其是减少高速缓存未命中的成本.它讨论了一个贪婪的选择过程,它产生了非常好的结果,以及一个更复杂但相当昂贵的时间"本地搜索"方案,可以产生出色的结果.