如何用JavaScript实现一门编程语言 - 编译器优化 #25

llwanghong · 2023-04-28T01:38:40Z

整篇译文的目录章节如下：

优化器（Optimizer）

作者原文提到的bug此译文中已修复，主要是指在解释器，CPS求值器及CPS编译器章节中：像 a() && b() 或者 a() || b() 的表达式两侧都会求值。这样处理是不对的，是否对 b() 求值依赖 a() 的求值结果。通过将 || 及 && 两个二元操作符的处理逻辑替换为 if 表达式来修复。

优化器

— 细节决定成败 —

优化CPS形式的代码是许多学术研究的主题。但即使不知道很多理论，我们仍然可以进行一些明显的改进。对于fib函数，相对于之前的版本大概会有3倍的提速：

fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2);
time( λ() println(fib(27)) );

像我们写的其它代码一样，优化器会递归遍历AST，依据一些规则，将表达式尽可能转换为更简单的形式。这种方法很有效直至到达了数学家们所谓的“不动点”：optimize(ast) == ast。也就是说，至此AST不能进一步简化了。为了实现这点，我们使用一个changes变量，优化开始前将其重置为0，每次AST简化的同时递增该变量。当changes保持为0，意味着优化完成。

示例

fib函数

下面你可以看到fib函数所经历的一系列简化。虽然我使用了JavaScript代码来展示说明，但请记住优化器接收的是一个AST返回的也是一个AST；make_js只在最后被调用一次。

优化器本身并没有特别被优化 — 每一轮可以做更多的事情，但我更倾向于一次只做一次修改，当changes > 0时返回未被修改的原表达式（后面我会给出详细原因）。

初始代码，to_cps返回的代码。

fib = function β_CC(β_K1, n) {
  GUARD(arguments, β_CC);
  (function β_CC(β_I2) {
    GUARD(arguments, β_CC);
    n < 2 ? β_I2(n) : fib(function β_CC(β_R4) {
      GUARD(arguments, β_CC);
      fib(function β_CC(β_R5) {
        GUARD(arguments, β_CC);
        β_I2(β_R4 + β_R5);
      }, n - 2);
    }, n - 1);
  })(function β_CC(β_R3) {
    GUARD(arguments, β_CC);
    β_K1(β_R3);
  });
};

展开IIFE。β_I2（if节点的continuation）成为了所在函数的一个变量。

fib = function β_CC(β_K1, n) {
  var β_I2;
  GUARD(arguments, β_CC);
  β_I2 = function β_CC(β_R3) {
    GUARD(arguments, β_CC);
    β_K1(β_R3);
  }, n < 2 ? β_I2(n) : fib(function β_CC(β_R4) {
    GUARD(arguments, β_CC);
    fib(function β_CC(β_R5) {
      GUARD(arguments, β_CC);
      β_I2(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

“尾部调用优化”。这里并没有真正进行TCO，但最终结果是一样的。可以发现β_I2实际上等同于β_K1，所以将不需要的函数闭包删除。

fib = function β_CC(β_K1, n) {
  var β_I2;
  GUARD(arguments, β_CC);
  β_I2 = β_K1, n < 2 ? β_I2(n) : fib(function β_CC(β_R4) {
    GUARD(arguments, β_CC);
    fib(function β_CC(β_R5) {
      GUARD(arguments, β_CC);
      β_I2(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

变量消除。既然β_I2与β_K1相同，β_I2出现的地方都可以用β_K1来替换，赋值语句就可以删除了。

fib = function β_CC(β_K1, n) {
  var β_I2;
  GUARD(arguments, β_CC);
  β_K1, n < 2 ? β_K1(n) : fib(function β_CC(β_R4) {
    GUARD(arguments, β_CC);
    fib(function β_CC(β_R5) {
      GUARD(arguments, β_CC);
      β_K1(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

删除无用代码。既然β_I2不再需要，var语句也可以删除。同样一个无意义的β_K1也可以删除。

fib = function β_CC(β_K1, n) {
  GUARD(arguments, β_CC);
  n < 2 ? β_K1(n) : fib(function β_CC(β_R4) {
    GUARD(arguments, β_CC);
    fib(function β_CC(β_R5) {
      GUARD(arguments, β_CC);
      β_K1(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

丢掉一些GUARD调用。当一个函数立即调用另外一个函数，就有机会来让下一个函数再重置堆栈，考虑到我们目前堆栈嵌套限制相当小（200次调用），所以可以承受住少数函数不保护堆栈。

[**XXX: 需要更多的测试来确保这是合理的；速度增益是很显著的。**同时我们也丧失了无限的递归能力，尽管正确的尾递归函数仍可以运行。]

fib = function β_CC(β_K1, n) {
  GUARD(arguments, β_CC);
  n < 2 ? β_K1(n) : fib(function(β_R4) {
    fib(function(β_R5) {
      β_K1(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

没有更多的转换。到达了不动点，至此停止。

fib = function β_CC(β_K1, n) {
  GUARD(arguments, β_CC);
  n < 2 ? β_K1(n) : fib(function(β_R4) {
    fib(function(β_R5) {
      β_K1(β_R4 + β_R5);
    }, n - 2);
  }, n - 1);
};

let节点

下面示例中我将不会展示全部中间步骤，只展示初始和最终形式。

输入代码：

(λ(){
  let (a = 2, b = 5) {
    print(a + b);
  };
})();

转换：

输入代码：

(λ(){
  let (a = 2) {
    let (a = 3) {
      print(a);
    };
    print(a);
  };
})();

转换：

实现概览

如前所述，优化器将接收AST并逐步简化节点，直到没有更多可能的简化为止。不像我们之前写的其它AST遍历器，这个优化器是具有“破坏性”的 — 可能会修改输入的源AST，而不是创建一个新的。关键的简化动作如下：

丢掉无用的闭包：λ(x){ y(x) } → y。
尽可能丢掉没有被使用的变量。
在所在函数内部展开IIFE。
计算常量表达式：a = 2 + 3 * 4 → a = 14。
同样，如果if节点的条件是常量，将if替换为恰当的分支。
丢掉prog节点中没有副作用的表达式。
只要有可能使用unguarded: true标识lambda节点。

一些优化可能是“级联”的 — 例如，将一个变量替换为另一个，则被替换的变量就可能可以丢掉。因此完成任意的改动后进行反复处理优化很重要。

make_scope

因为与环境耦合在一起（有时引入变量，有时又要删除它们），我们需要一个精确的方式来确定变量之间的联系。就像“变量x都被什么引用”？为了实现这个能力，我写了一个帮助函数make_scope。它会遍历AST，恰当地创建Environment实例，并对一些节点进行如下标识：

"lambda" — 既然它们会创建新环境，每个lambda节点将获得一个env属性指向其环境。同样每个lambda节点会获得一个locs属性 — 当前函数所有“局部”变量的名字数组（最终代码中使用var定义）。
"var" — 变量节点将获得一个env属性指向定义该变量的环境，以及一个def属性指向一个definition对象。

环境会为每个变量存储一个definition对象，并且为了方便，每个var节点的def属性将指向该definition对象。该对象包含了下面的信息：

{
  refs: [/* array of "var" nodes pointing to this definition */],
  assigned: integer, // how many times is this var assigned to?
  cont: true or false, // is this a continuation argument?
}

这个信息使得优化器可以进行想做的优化。例如，如果一个变量被赋值和被引用的次数相同，意味着没有任何地方在使用该变量的值（因为每次赋值都算一次引用）— 所以可以将它丢掉。或者，当需要将变量X替换为变量Y时，我们可以遍历X的refs并将每个引用节点的名字修改为Y。

我们给lambda节点增加的locs属性将用来存储展开IIFE过程中得到的变量。如果locs已存在，则make_scope会保留它（并会谨慎地在环境中定义得到的变量），否则将其初始化为空数组。JS代码生成器（js_lambda中）将为那些变量名字（如果存在的话）引入一个var语句（所以js_lambda也需要修改）。

我第一次尝试的时侯是在开始的时侯调用一次make_scope，然后让优化器维护每个简化中所有env和def等其它属性，优势是在一轮优化中就可以做多个简化。但这个代码太复杂，最终放弃了。当前代码会在每轮优化之前调用make_scope，然后优化器在每次简化后不会做其它操作（这是必要的，这样我们就不会操作过时的作用域信息）。

optimize函数

如之前所说，优化器每轮优化开展之前将先调用make_scope，并如此反复直到没有更多可能的优化。最终，在返回优化过的表达式之前，会将顶层作用域保存到env属性中。下面是入口函数：

function optimize(exp) {
    do {
        var changes = 0;
        var defun = exp;
        make_scope(exp);
        exp = opt(exp);
    } while (changes);
    return exp;

    function opt(exp) {
        if (changes) return exp;
        switch (exp.type) {
          case "num"    :
          case "str"    :
          case "bool"   :
          case "var"    : return exp;
          case "binary" : return opt_binary (exp);
          case "assign" : return opt_assign (exp);
          case "if"     : return opt_if     (exp);
          case "prog"   : return opt_prog   (exp);
          case "call"   : return opt_call   (exp);
          case "lambda" : return opt_lambda (exp);
        }
        throw new Error("I don't know how to optimize " + JSON.stringify(exp));
    }

    ... // the opt_* functions here
}

我们不需要关心let节点，因为CPS转换器中已将它们脱糖展开为IIFE了。

那些“容易”的节点（常量和变量）直接按原样返回。

每个opt_*函数将对当前表达式的成员递归调用opt函数。

opt_binary将优化二元表达式：会对left和right节点分别调用opt，然后校验它们是否是常量 — 如果是，则对表达式求值并替换结果。
opt_assign同样将同时优化left和right节点。然后校验潜在的可进行的优化。
opt_if将依次优化cond，then以及else节点。当condition可以确定时（一个常量表达式）则会相应地返回then或else。
opt_prog会重复一些CPS转换器中已经做过的工作，比如丢掉没有副作用的表达式；这里仍旧有用是因为优化是相互级联的（即使to_cps返回了紧凑的代码，这里仍旧可能经过一些优化最终得到了没有副作用的表达式）。
opt_call优化函数调用。如果我们调用的是一个匿名lambda函数（IIFE），将会跳转至opt_iife（查看代码）函数，它会将函数参数和函数体在当前程序展开。这可能是我们做的最巧妙（且最有效）的优化工作了。
opt_lambda将优化仅会以相同参数调用另一个函数的一类函数。如果事实并非如此，它会将未使用变量从locs中丢掉，然后进一步优化函数体。

实现代码

我不打算详细介绍所有函数实现。点击下面的显示代码来查看完整的代码（默认隐藏了起来，不希望滚动条把你吓跑）。

显示代码

function optimize(exp) {
    var changes, defun;
    do {
        changes = 0;
        make_scope(exp);
        exp = opt(exp);
    } while (changes);
    make_scope(exp);
    return exp;

    function opt(exp) {
        if (changes) return exp;
        switch (exp.type) {
          case "num"    :
          case "str"    :
          case "bool"   :
          case "var"    : return exp;
          case "binary" : return opt_binary (exp);
          case "assign" : return opt_assign (exp);
          case "if"     : return opt_if     (exp);
          case "prog"   : return opt_prog   (exp);
          case "call"   : return opt_call   (exp);
          case "lambda" : return opt_lambda (exp);
        }
        throw new Error("I don't know how to optimize " + JSON.stringify(exp));
    }

    function changed() {
        ++changes;
    }

    function is_constant(exp) {
        return exp.type == "num"
            || exp.type == "str"
            || exp.type == "bool";
    }

    function num(exp) {
        if (exp.type != "num")
            throw new Error("Not a number: " + JSON.stringify(exp));
        return exp.value;
    }

    function div(exp) {
        if (num(exp) == 0)
            throw new Error("Division by zero: " + JSON.stringify(exp));
        return exp.value;
    }

    function opt_binary(exp) {
        exp.left = opt(exp.left);
        exp.right = opt(exp.right);
        if (is_constant(exp.left) && is_constant(exp.right)) {
            switch (exp.operator) {
              case "+":
                changed();
                return {
                    type: "num",
                    value: num(exp.left) + num(exp.right)
                };

              case "-":
                changed();
                return {
                    type: "num",
                    value: num(exp.left) - num(exp.right)
                };

              case "*":
                changed();
                return {
                    type: "num",
                    value: num(exp.left) * num(exp.right)
                };

              case "/":
                changed();
                return {
                    type: "num",
                    value: num(exp.left) / div(exp.right)
                };

              case "%":
                changed();
                return {
                    type: "num",
                    value: num(exp.dleft) % div(exp.right)
                };

              case "<":
                changed();
                return {
                    type: "bool",
                    value: num(exp.left) < num(exp.right)
                };

              case ">":
                changed();
                return {
                    type: "bool",
                    value: num(exp.left) > num(exp.right)
                };

              case "<=":
                changed();
                return {
                    type: "bool",
                    value: num(exp.left) <= num(exp.right)
                };

              case ">=":
                changed();
                return {
                    type: "bool",
                    value: num(exp.left) >= num(exp.right)
                };

              case "==":
                changed();
                if (exp.left.type != exp.right.type)
                    return FALSE;
                return {
                    type: "bool",
                    value: exp.left.value === exp.right.value
                };

              case "!=":
                changed();
                if (exp.left.type != exp.right.type)
                    return TRUE;
                return {
                    type: "bool",
                    value: exp.left.value !== exp.right.value
                };

              case "||":
                changed();
                if (exp.left.value !== false)
                    return exp.left;
                return exp.right;

              case "&&":
                changed();
                if (exp.left.value !== false)
                    return exp.right;
                return FALSE;
            }
        }
        return exp;
    }

    function opt_assign(exp) {
        if (exp.left.type == "var") {
            if (exp.right.type == "var" && exp.right.def.cont) {
                // the var on the right never changes.  we can safely
                // replace references to exp.left with references to
                // exp.right, saving one var and the assignment.
                changed();
                exp.left.def.refs.forEach(function(node){
                    node.value = exp.right.value;
                });
                return opt(exp.right); // could be needed for the result.
            }
            if (exp.left.def.refs.length == exp.left.def.assigned && exp.left.env.parent) {
                // if assigned as many times as referenced and not a
                // global, it means the var is never used, drop the
                // assignment but keep the right side for possible
                // side effects.
                changed();
                return opt(exp.right);
            }
        }
        exp.left = opt(exp.left);
        exp.right = opt(exp.right);
        return exp;
    }

    function opt_if(exp) {
        exp.cond = opt(exp.cond);
        exp.then = opt(exp.then);
        exp.else = opt(exp.else || FALSE);
        if (is_constant(exp.cond)) {
            changed();
            if (exp.cond.value !== false)
                return exp.then;
            return exp.else;
        }
        return exp;
    }

    function opt_prog(exp) {
        if (exp.prog.length == 0) {
            changed();
            return FALSE;
        }
        if (exp.prog.length == 1) {
            changed();
            return opt(exp.prog[0]);
        }
        if (!has_side_effects(exp.prog[0])) {
            changed();
            return opt({
                type : "prog",
                prog : exp.prog.slice(1)
            });
        }
        if (exp.prog.length == 2) return {
            type: "prog",
            prog: exp.prog.map(opt)
        };
        // normalize
        return opt({
            type: "prog",
            prog: [
                exp.prog[0],
                { type: "prog", prog: exp.prog.slice(1) }
            ]
        });
    }

    function opt_call(exp) {
        // IIFE-s will be optimized away by defining variables in the
        // containing function.  However, we don't unwrap into the
        // global scope (that's why checking for env.parent.parent).
        var func = exp.func;
        if (func.type == "lambda" && !func.name) {
            if (func.env.parent.parent)
                return opt_iife(exp);
            // however, if in global scope we can safely unguard it.
            func.unguarded = true;
        }
        return {
            type : "call",
            func : opt(func),
            args : exp.args.map(opt)
        };
    }

    function opt_lambda(f) {
        // λ(x...) y(x...)  ==>  y
        TCO: if (f.body.type == "call" &&
                 f.body.func.type == "var" &&
                 f.body.func.def.assigned == 0 &&
                 f.body.func.env.parent &&
                 f.vars.indexOf(f.body.func.value) < 0 &&
                 f.vars.length == f.body.args.length) {
            for (var i = 0; i < f.vars.length; ++i) {
                var x = f.body.args[i];
                if (x.type != "var" || x.value != f.vars[i])
                    break TCO;
            }
            changed();
            return opt(f.body.func);
        }
        f.locs = f.locs.filter(function(name){
            var def = f.env.get(name);
            return def.refs.length > 0;
        });
        var save = defun;
        defun = f;
        f.body = opt(f.body);
        if (f.body.type == "call")
            f.unguarded = true;
        defun = save;
        return f;
    }

    // (λ(foo, bar){...body...})(fooval, barval)
    //    ==>
    // foo = fooval, bar = barval, ...body...
    function opt_iife(exp) {
        changed();
        var func = exp.func;
        var argvalues = exp.args.map(opt);
        var body = opt(func.body);
        function rename(name) {
            var sym = name in defun.env.vars ? gensym(name + "$") : name;
            defun.locs.push(sym);
            defun.env.def(sym, true);
            func.env.get(name).refs.forEach(function(ref){
                ref.value = sym;
            });
            return sym;
        }
        var prog = func.vars.map(function(name, i){
            return {
                type     : "assign",
                operator : "=",
                left     : { type: "var", value: rename(name) },
                right    : argvalues[i] || FALSE
            };
        });
        func.locs.forEach(rename);
        prog.push(body);
        return opt({
            type: "prog",
            prog: prog
        });
    }
}

function make_scope(exp) {
    var global = new Environment();
    exp.env = global;
    (function scope(exp, env) {
        switch (exp.type) {
          case "num":
          case "str":
          case "bool":
            break;

          case "var":
            var s = env.lookup(exp.value);
            if (!s) {
                exp.env = global;
                global.def(exp.value, { refs: [], assigned: 0 });
            } else {
                exp.env = s;
            }
            var def = exp.env.get(exp.value);
            def.refs.push(exp);
            exp.def = def;
            break;

          case "assign":
            scope(exp.left, env);
            scope(exp.right, env);
            if (exp.left.type == "var")
                exp.left.def.assigned++;
            break;

          case "binary":
            scope(exp.left, env);
            scope(exp.right, env);
            break;

          case "if":
            scope(exp.cond, env);
            scope(exp.then, env);
            if (exp.else)
                scope(exp.else, env);
            break;

          case "prog":
            exp.prog.forEach(function(exp){
                scope(exp, env);
            });
            break;

          case "call":
            scope(exp.func, env);
            exp.args.forEach(function(exp){
                scope(exp, env);
            });
            break;

          case "lambda":
            exp.env = env = env.extend();
            if (exp.name)
                env.def(exp.name, { refs: [], func: true, assigned: 0 });
            exp.vars.forEach(function(name, i){
                env.def(name, { refs: [], farg: true, assigned: 0, cont: i == 0 });
            });
            if (!exp.locs) exp.locs = [];
            exp.locs.forEach(function(name){
                env.def(name, { refs: [], floc: true, assigned: 0 });
            });
            scope(exp.body, env);
            break;

          default:
            throw new Error("Can't handle node " + JSON.stringify(exp));
        }
    })(exp, global);
    return exp.env;
}

var FALSE = { type: "bool", value: false };
var TRUE = { type: "bool", value: true };

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

如何用JavaScript实现一门编程语言 - 编译器优化 #25

如何用JavaScript实现一门编程语言 - 编译器优化 #25

llwanghong commented Apr 28, 2023 •

edited

如何用JavaScript实现一门编程语言 - 编译器优化 #25

如何用JavaScript实现一门编程语言 - 编译器优化 #25

Comments

llwanghong commented Apr 28, 2023 • edited

优化器（Optimizer）

优化器

示例

fib函数

let节点

实现概览

make_scope

optimize函数

实现代码

llwanghong commented Apr 28, 2023 •

edited