到底如何为编译器构建“基本块”（以JavaScript为例）？

Question

我正在开发一个编译器项目，想知道控制流图（CFG ）的“基本块”的含义和实现。他们说基本块是用于没有任何分支的线性步骤序列。但首先，有几个问题：

1. 如果存在嵌套分支怎么办？它是如何工作的？
2. 条件分支语句内部的逻辑怎么样，是前一个块的一部分还是当前块（或第三个块）的一部分？

例如，假设我有这个：

let a = 10;
let b = 0;
if ((foo() && bar()) || baz()) {
  b = 20;
  if (hello > world) {
    b *= 3
  }
} else {
  b = 2 * a;
}
let c = a * b
log(a);

这里，什么是“基本块”？

const blocks = [
  {
    inputs: [],
    statements: [
      'let a = 10',
      'let b = 0',
    ],
    outputs: ['a', 'b']
  },
  {
    // ...?
  }
]

我不是问如何准确地实现数据流分析器，只是粗略地说在这样的示例中块应该是什么？一些伪代码会有所帮助。条件表达式(foo() && bar()) || baz()甚至隐藏了一些分支逻辑。在我的代码中，我做了这样的事情：

if
  or
    and
      test foo
      test bar
    baz

甚至：

andResult = 
  and
    test foo
    test bar
orResult = baz | andResult
if orResult, ...

这表明它本身就是计算的步骤。该语句应该if放在哪里，它是否开始下一个块？基本上想知道它们通常应该如何构建。然后考虑嵌套条件分支。

Answer 1

如果您要根据标签和 goto（无条件形式：goto L和条件形式：）重写程序，基本块实际上是您将获得的代码段if (t0) then goto L else L'。

必须注意正确降低条件结构，以保留随之而来的短路语义。

此转换是构造控制流图之前的常见中间步骤。所谓的“领导者”算法（您识别第一个语句和跳转目标，将它们指定为领导者，然后通过从一个领导者到下一个领导者的指令来构造块）在“编译器：原理，技术”中描述和工具”。

那么，让我们看看你的例子：

let a = 10;
let b = 0;
if ((foo() && bar()) || baz()) {
  b = 20;
  if (hello > world) {
    b *= 3
  }
} else {
  b = 2 * a;
}
let c = a * b
log(a);

编译器首先希望将其规范化为如下所示的内容（请注意必须保留短路语义）：

L0:
  a = 100;
  b = 0;
  t0 = foo();
  if (t0 != 0) goto L1; else goto L2;
L1:
  t1 = bar();
  if (t1 != 0) goto L3; else goto L2;
L2:
  t2 = baz();
  if (t2 != 0) goto L3; else goto L4;
L3:
  b = 20;
  if (hello > world) goto L5; else goto L6;
L5:
  b = b * 3;
L6:
  goto L7;
L4:
  b = a * 2;
L7:
  c = a * b;
  log (a);
  return

从这里，我们可以应用前面提到的“前导”算法来识别基本块的前导指令。然后，我们可以将代码分割成块（从一个领导者到下一个领导者），然后找出控制流程；确保识别“fallthrough”边缘（当块的最后一条指令落在没有显式分支的领导者上时）。

最后，我们留下类似的东西：

您可以看到 是L6一个无条件跳转到 的块L7，这是归一化/线性化算法产生的产物。删除此类多余的块称为“跳转线程”，稍后完成。

如果您希望使用现有的编译器，在其 IR 之一中公开此控制流转换，您可以使用该标志调用 GCC -fdump-tree-all，然后查看扩展名为.gimple.