V8优化编译器中的关键思想Sea of Nodes介绍
编译器是每个软件工程师每天都要用到的东西。令人惊讶的是，即使是那些自认为远离代码编写的人，每天也会大量使用编译器。这是因为大多数网络依赖于客户端代码的执行，而许多客户端程序都是以源代码的形式传递给浏览器的。
这里有一件重要的事情：虽然源代码（通常）是人类可读的，但对于笔记本电脑/计算机/手机/......的 CPU 来说，它看起来完全是垃圾。另一方面，计算机可以读取的机器代码（几乎总是）不是人类可读的。对此，我们应该采取一些措施，而翻译过程就是解决这一问题的方法。
简单的编译器只进行一次翻译：从源代码到机器代码。但实际上，大多数编译器至少要进行两次翻译：从源代码到抽象语法树（AST），再从 AST 到机器代码。在这种情况下，AST 就像一个中间表示（IR），顾名思义，AST 只是相同源代码的另一种形式。这些中间表示法串联在一起，本质上就是抽象层。
层数没有限制。每一层都会使源程序更接近机器代码的样子。
优化层次（Optimization layers）
不过，并非所有层都只用于翻译。许多编译器还试图优化人工编写的代码。(这通常是为了在代码优雅和代码性能之间取得平衡）。
以下面的JavaScript代码为例子。
for (var i = 0, acc = 0; i < arr.length; i++)
acc += arr[i];如果编译器将其直接从 AST 翻译成机器代码，它可能类似于（非常抽象且脱离实际的指令集）：
acc = 0;
i = 0;
loop {
// Load `.length` field of arr
tmp = loadArrayLength(arr);
if (i >= tmp)
break;
// Check that `i` is between 0 and `arr.length`
// (NOTE: This is necessary for fast loads and
// stores).
checkIndex(arr, i);
// Load value
acc += load(arr, i);
// Increment index
i += 1;
}这一点可能并不明显，但这段代码远非最佳。数组长度在循环内部并没有真正发生变化，范围检查根本没有必要。理想的情况应该是这样的：
acc = 0;
i = 0;
len = loadArrayLength(arr);
loop {
if (i >= tmp)
break;
acc += load(arr, i);
i += 1;
}让我们试着想象一下如何做到这一点。
假设我们手头有一个 AST，并试图直接从中生成机器代码：
(注：由 esprima 生成）
{ type: 'ForStatement',
//
// This is `var i = 0;`
//
init:
{ type: 'VariableDeclaration',
declarations:
[ { type: 'VariableDeclarator',
id: { type: 'Identifier', name: 'i' },
init: { type: 'Literal', value: 0, raw: '0' } },
{ type: 'VariableDeclarator',
id: { type: 'Identifier', name: 'acc' },
init: { type: 'Literal', value: 0, raw: '0' } }],
kind: 'var' },
//
// `i < arr.length`
//
test:
{ type: 'BinaryExpression',
operator: '<',
left: { type: 'Identifier', name: 'i' },
right:
{ type: 'MemberExpression',
computed: false,
object: { type: 'Identifier', name: 'arr' },
property: { type: 'Identifier', name: 'length' } } },
//
// `i++`
//
update:
{ type: 'UpdateExpression',
operator: '++',
argument: { type: 'Identifier', name: 'i' },
prefix: false },
//
// `arr[i] += 1;`
//
body:
{ type: 'ExpressionStatement',
expression:
{ type: 'AssignmentExpression',
operator: '+=',
left: { type: 'Identifier', name: 'acc' },
right:
{ type: 'MemberExpression',
computed: true,
object: { type: 'Identifier', name: 'arr' },
property: { type: 'Identifier', name: 'i' } } } }这种 JSON 也可以可视化：
这是一棵树，因此很自然地从树顶向树底遍历，在访问 AST 节点时生成机器代码。这种方法的问题在于变量信息非常稀少，而且分散在不同的树节点中。
同样，为了安全地将长度查找移出循环，我们需要知道数组长度在循环迭代之间不会发生变化。人类只需查看源代码就能轻松做到这一点，但编译器需要做大量工作，才能自信地直接从 AST 中提取这些事实。
与许多其他编译器问题一样，解决这个问题的方法通常是将数据提升到一个更合适的抽象层，即中间表示。在这种特殊情况下，中间表示法被称为数据流图（DFG）。与其讨论语法实体（如 for 循环、表达式......），我们不如讨论数据本身（读取、变量值），以及数据如何在程序中发生变化。
数据流图
在我们的示例中，我们感兴趣的数据是变量 arr 的值。我们希望能够轻松地观察对它的所有使用，以验证是否存在越界访问或任何会修改数组长度的其他变化。
这是通过在不同数据值之间引入 "def-use"（定义和用途）关系来实现的。具体来说，这意味着该值已被声明过一次（节点），并在某处被用于创建新值（每次使用的边）。显然，将不同的值连接在一起会形成这样一个数据流图：
请注意这个巨大图表中的红色阵列框。从该方框流出的实心箭头代表了该值的使用情况。通过遍历这些边，编译器可以推导出数组值的使用位置：
- loadArrayLength
- checkIndex
- load
如果数组节点的值是以破坏性方式访问的（如存储、长度大小），那么这种图的构造方式就是明确地 "克隆 "数组节点。每当我们看到数组节点并观察其使用情况时，我们总能确定它的值不会改变。
这听起来很复杂，但要实现图形的这一属性却很容易。图形应遵循单一静态赋值（SSA）规则。简而言之，要将任何程序转换为 SSA，编译器需要重命名所有赋值和变量的后续使用，以确保每个变量只被赋值一次。
例如，在SSA之前：
var a = 1;
console.log(a);
a = 2;
console.log(a);在SSA之后：
var a0 = 1;
console.log(a0);
var a1 = 2;
console.log(a1);这样，我们就可以确定，当我们谈论 a0 时，我们实际上是在谈论对它的一次赋值。这与人们在函数式语言中的做法非常接近！
由于 loadArrayLength 没有控制依赖关系（即没有虚线；我们稍后将讨论虚线），编译器可能会得出结论：这个节点可以自由移动到任何它想去的地方，并且可以放在循环之外。通过进一步查看图，我们可以发现 ssa:phi 节点的值始终介于 0 和 arr.length 之间，因此可以完全删除 checkIndex。
很漂亮，不是吗？
控制流图
我们只是通过某种形式的数据流分析，从程序中提取信息。这样，我们就能对如何优化程序做出安全的假设。
这种数据流表示法在许多其他情况下也非常有用。唯一的问题是，将我们的代码转换成这种图，我们就在表示链（从源代码到机器代码）上倒退了一步。这种中间表示法甚至不如 AST 更适合生成机器代码。
原因在于，机器只是一个顺序排列的指令列表，CPU 一个接一个地执行这些指令。我们的结果图似乎并没有表达这一点。事实上，它根本没有强制排序。
通常，解决这个问题的方法是将图节点分组为块。这种表示法被称为控制流图（CFG）。举例说明
b0 {
i0 = literal 0
i1 = literal 0
i3 = array
i4 = jump ^b0
}
b0 -> b1
b1 {
i5 = ssa:phi ^b1 i0, i12
i6 = ssa:phi ^i5, i1, i14
i7 = loadArrayLength i3
i8 = cmp "<", i6, i7
i9 = if ^i6, i8
}
b1 -> b2, b3
b2 {
i10 = checkIndex ^b2, i3, i6
i11 = load ^i10, i3, i6
i12 = add i5, i11
i13 = literal 1
i14 = add i6, i13
i15 = jump ^b2
}
b2 -> b1
b3 {
i16 = exit ^b3
}它被称为图不是没有道理的。例如，bXX 块代表节点，bXX -> bYY 箭头代表边。让我们把它形象化：
如你所见，b0 块中有循环前的代码，b1 块中有循环头，b2 块中有循环测试，b3 块中有循环主体，b4 块中有退出节点。
从这种形式转换为机器码非常简单。我们只需将 iXX 标识符替换为 CPU 寄存器名称（从某种意义上说，CPU 寄存器有点像变量，CPU 的寄存器数量有限，因此我们需要注意不要用完寄存器），然后逐行生成每条指令的机器代码。
总而言之，CFG 具有数据流关系和排序。这使我们可以利用它进行数据流分析和机器代码生成。不过，如果试图通过操作数据块及其包含的内容来优化 CFG，很快就会变得复杂且容易出错。
相反，Clifford Click 和 Keith D. Cooper 提议使用一种称为sea-of-nodes的方法，这正是本博文的主题！
Sea-of-Nodes
还记得我们用虚线绘制的花哨的数据流图吗？这些虚线实际上是使该图成为sea of nodes图的原因。
我们选择将控制依赖关系声明为图形中的虚线边，而不是将节点按块分组和排序。如果我们将该图移除所有非虚线边，并稍加分组，我们将得到:
只要稍加想象并对节点重新排序，我们就能看到这个图与我们刚才看到的简化 CFG 图是一样的：
让我们再来看看sea of nodes表示法：
该图与 CFG 的显著区别在于，除了具有控制依赖关系的节点（换句话说，参与控制流的节点）外，其他节点没有排序。
这种表示法是一种非常强大的查看代码的方法。它具有一般数据流图的所有洞察力，并且可以轻松更改，而无需不断删除/替换块中的节点。
Reductions
说到修改，让我们来讨论一下修改图的方法。sea of nodes图通常是通过图形缩减（Reduction）来修改的。我们只需将图中的所有节点排成队列。对队列中的每个节点调用我们的缩减函数(reduction function)。该函数触及（更改、替换）的所有内容都会排队返回，并在稍后传递给该函数。如果有很多缩减，可以将它们堆叠在一起，然后在队列中的每个节点上调用所有缩减函数；或者，如果这些缩减函数依赖于彼此的最终状态，也可以一个接一个地调用。这种方法非常有效！
下面是一些javascript编写的sea-of-nodes实验工具：
- json-pipeline - the builder and stdlib of the graph. Provides methods to create nodes, add inputs to them, change their control dependencies, and export/import the graph to/from the printable data!
- json-pipeline-reducer - the reductions engine. Just create a reducer instance, feed it several reduction functions, and execute the reducer on the existing json-pipeline graph.
- json-pipeline-scheduler - library for putting back unordered graph in a limited amount of blocks connected to each other by control edges (dashed lines).
这些工具结合在一起，可以解决许多可以用数据流方程表述的问题。
缩减示例，它将优化我们的初始 JS 代码：
for (var i = 0, acc = 0; i < arr.length; i++)
acc += arr[i];TL;DR
这段代码比较长，如果你想跳过它，下面是我们要做的说明：
- 计算各种节点的整数范围：literal、add、phi
- 计算应用于分支主体的限值
- 应用范围和限制信息（i 始终是受 arr.length 限制的非负数）得出结论，长度检查没有必要，可以删除
- json-pipeline-scheduler 会自动将 arr.length 移出循环。这是因为它会做全局代码移动（Global Code Motion）调度块中的节点。
// Just for viewing graphviz output
var fs = require('fs');
var Pipeline = require('json-pipeline');
var Reducer = require('json-pipeline-reducer');
var Scheduler = require('json-pipeline-scheduler');
//
// Create empty graph with CFG convenience
// methods.
//
var p = Pipeline.create('cfg');
//
// Parse the printable data and generate
// the graph.
//
p.parse(`pipeline {
b0 {
i0 = literal 0
i1 = literal 0
i3 = array
i4 = jump ^b0
}
b0 -> b1
b1 {
i5 = ssa:phi ^b1 i0, i12
i6 = ssa:phi ^i5, i1, i14
i7 = loadArrayLength i3
i8 = cmp "<", i6, i7
i9 = if ^i6, i8
}
b1 -> b2, b3
b2 {
i10 = checkIndex ^b2, i3, i6
i11 = load ^i10, i3, i6
i12 = add i5, i11
i13 = literal 1
i14 = add i6, i13
i15 = jump ^b2
}
b2 -> b1
b3 {
i16 = exit ^b3
}
}`, { cfg: true }, 'printable');
if (process.env.DEBUG)
fs.writeFileSync('before.gv', p.render('graphviz'));
//
// Just a helper to run reductions
//
function reduce(graph, reduction) {
var reducer = new Reducer();
reducer.addReduction(reduction);
reducer.reduce(graph);
}
//
// Create reduction
//
var ranges = new Map();
function getRange(node) {
if (ranges.has(node))
return ranges.get(node);
var range = { from: -Infinity, to: +Infinity, type: 'any' };
ranges.set(node, range);
return range;
}
function updateRange(node, reducer, from, to) {
var range = getRange(node);
// Lowest type, can't get upwards
if (range.type === 'none')
return;
if (range.from === from && range.to === to && range.type === 'int')
return;
range.from = from;
range.to = to;
range.type = 'int';
reducer.change(node);
}
function updateType(node, reducer, type) {
var range = getRange(node);
if (range.type === type)
return;
range.type = type;
reducer.change(node);
}
//
// Set type of literal
//
function reduceLiteral(node, reducer) {
var value = node.literals[0];
updateRange(node, reducer, value, value);
}
function reduceBinary(node, left, right, reducer) {
if (left.type === 'none' || right.type === 'none') {
updateType(node, reducer, 'none');
return false;
}
if (left.type === 'int' || right.type === 'int')
updateType(node, reducer, 'int');
if (left.type !== 'int' || right.type !== 'int')
return false;
return true;
}
//
// Just join the ranges of inputs
//
function reducePhi(node, reducer) {
var left = getRange(node.inputs[0]);
var right = getRange(node.inputs[1]);
if (!reduceBinary(node, left, right, reducer))
return;
if (node.inputs[1].opcode !== 'add' || left.from !== left.to)
return;
var from = Math.min(left.from, right.from);
var to = Math.max(left.to, right.to);
updateRange(node, reducer, from, to);
}
//
// Detect: phi = phi + <positive number>, where initial phi is number,
// report proper range.
//
function reduceAdd(node, reducer) {
var left = getRange(node.inputs[0]);
var right = getRange(node.inputs[1]);
if (!reduceBinary(node, left, right, reducer))
return;
var phi = node.inputs[0];
if (phi.opcode !== 'ssa:phi' || right.from !== right.to)
return;
var number = right.from;
if (number <= 0 || phi.inputs[1] !== node)
return;
var initial = getRange(phi.inputs[0]);
if (initial.type !== 'int')
return;
updateRange(node, reducer, initial.from, +Infinity);
}
var limits = new Map();
function getLimit(node) {
if (limits.has(node))
return limits.get(node);
var map = new Map();
limits.set(node, map);
return map;
}
function updateLimit(holder, node, reducer, type, value) {
var map = getLimit(holder);
if (!map.has(node))
map.set(node, { type: 'any', value: null });
var limit = map.get(node);
if (limit.type === type && limit.value === value)
return;
limit.type = type;
limit.value = value;
reducer.change(holder);
}
function mergeLimit(node, reducer, other) {
var map = getLimit(node);
var otherMap = getLimit(other);
otherMap.forEach(function(limit, key) {
updateLimit(node, key, reducer, limit.type, limit.value);
});
}
//
// Propagate limit from: X < Y to `if`'s true branch
//
function reduceIf(node, reducer) {
var test = node.inputs[0];
if (test.opcode !== 'cmp' || test.literals[0] !== '<')
return;
var left = test.inputs[0];
var right = test.inputs[1];
updateLimit(node.controlUses[0], left, reducer, '<', right);
updateLimit(node.controlUses[2], left, reducer, '>=', right);
}
//
// Determine ranges and limits of
// the values.
//
var rangeAndLimit = new Reducer.Reduction({
reduce: function(node, reducer) {
if (node.opcode === 'literal')
reduceLiteral(node, reducer);
else if (node.opcode === 'ssa:phi')
reducePhi(node, reducer);
else if (node.opcode === 'add')
reduceAdd(node, reducer);
else if (node.opcode === 'if')
reduceIf(node, reducer);
}
});
reduce(p, rangeAndLimit);
//
// Now that we have ranges and limits,
// time to remove the useless array
// length checks.
//
function reduceCheckIndex(node, reducer) {
// Walk up the control chain
var region = node.control[0];
while (region.opcode !== 'region' && region.opcode !== 'start')
region = region.control[0];
var array = node.inputs[0];
var index = node.inputs[1];
var limit = getLimit(region).get(index);
if (!limit)
return;
var range = getRange(index);
// Negative array index is not valid
if (range.from < 0)
return;
// Index should be limited by array length
if (limit.type !== '<' ||
limit.value.opcode !== 'loadArrayLength' ||
limit.value.inputs[0] !== array) {
return;
}
// Check is safe to remove!
reducer.remove(node);
}
var eliminateChecks = new Reducer.Reduction({
reduce: function(node, reducer) {
if (node.opcode === 'checkIndex')
reduceCheckIndex(node, reducer);
}
});
reduce(p, eliminateChecks);
//
// Run scheduler to put everything
// back to the CFG
//
var out = Scheduler.create(p).run();
out.reindex();
if (process.env.DEBUG)
fs.writeFileSync('after.gv', out.render('graphviz'));
console.log(out.render({ cfg: true }, 'printable'));本文系外文翻译，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文系外文翻译，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
