introduce `merge_vars` (#4100)

3 files changed, 415 insertions, 5 deletions

diff --git a/lib/compress.js b/lib/compress.js
index f34673d6..c39c0da6 100644
--- a/lib/compress.js
+++ b/lib/compress.js
@@ -73,6 +73,7 @@ function Compressor(options, false_by_default) {
         keep_fnames     : false,
         keep_infinity   : false,
         loops           : !false_by_default,
+        merge_vars      : !false_by_default,
         negate_iife     : !false_by_default,
         objects         : !false_by_default,
         passes          : 1,
@@ -225,7 +226,8 @@ merge(Compressor.prototype, {
         // output and performance.
         descend(node, this);
         var opt = node.optimize(this);
-        if (is_scope && opt === node) {
+        if (is_scope && opt === node && !this.has_directive("use asm") && !opt.pinned()) {
+            opt.merge_variables(this);
             opt.drop_unused(this);
             descend(opt, this);
         }
@@ -4305,11 +4307,185 @@ merge(Compressor.prototype, {
         return self;
     });
 
+    AST_Scope.DEFMETHOD("merge_variables", function(compressor) {
+        if (!compressor.option("merge_vars")) return;
+        var self = this, segment = self;
+        var first = [], last = [], index = 0;
+        var references = Object.create(null);
+        var prev = Object.create(null);
+        var tw = new TreeWalker(function(node, descend) {
+            if (node instanceof AST_Assign) {
+                var sym = node.left;
+                if (!(sym instanceof AST_SymbolRef)) return;
+                node.right.walk(tw);
+                mark(sym, node.operator == "=");
+                return true;
+            }
+            if (node instanceof AST_Binary) {
+                if (!lazy_op[node.operator]) return;
+                node.left.walk(tw);
+                var save = segment;
+                segment = node;
+                node.right.walk(tw);
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_Conditional) {
+                node.condition.walk(tw);
+                var save = segment;
+                segment = node;
+                node.consequent.walk(tw);
+                node.alternative.walk(tw);
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_For) {
+                if (node.init) node.init.walk(tw);
+                var save = segment;
+                segment = node;
+                if (node.condition) node.condition.walk(tw);
+                node.body.walk(tw);
+                if (node.step) node.step.walk(tw);
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_ForIn) {
+                node.object.walk(tw);
+                var save = segment;
+                segment = node;
+                node.init.walk(tw);
+                node.body.walk(tw);
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_If) {
+                node.condition.walk(tw);
+                var save = segment;
+                segment = node;
+                node.body.walk(tw);
+                if (node.alternative) node.alternative.walk(tw);
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_IterationStatement) {
+                var save = segment;
+                segment = node;
+                descend();
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_Scope) {
+                if (node instanceof AST_Lambda) {
+                    references[node.variables.get("arguments").id] = false;
+                    if (node.name) references[node.name.definition().id] = false;
+                }
+                var save = segment;
+                segment = node;
+                descend();
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_Switch) {
+                node.expression.walk(tw);
+                var save = segment;
+                segment = node;
+                node.body.forEach(function(branch) {
+                    branch.walk(tw);
+                });
+                segment = save;
+                return true;
+            }
+            if (node instanceof AST_SymbolFunarg) {
+                mark(node, true);
+                return true;
+            }
+            if (node instanceof AST_SymbolRef) {
+                mark(node);
+                return true;
+            }
+            if (node instanceof AST_Unary) {
+                if (!unary_arithmetic[node.operator]) return;
+                var sym = node.expression;
+                if (!(sym instanceof AST_SymbolRef)) return;
+                mark(sym);
+                return true;
+            }
+            if (node instanceof AST_VarDef) {
+                if (!node.value) return true;
+                node.value.walk(tw);
+                mark(node.name, true);
+                return true;
+            }
+        });
+        self.walk(tw);
+        var merged = Object.create(null);
+        while (first.length && last.length) {
+            var head = first.pop();
+            var def = head.definition;
+            if (!(def.id in prev)) continue;
+            if (!references[def.id]) continue;
+            while (def.id in merged) def = merged[def.id];
+            do {
+                var tail = last.pop();
+                if (!tail) continue;
+                if (tail.index > head.index) continue;
+                if (!references[tail.definition.id]) continue;
+                var orig = [], refs = [];
+                references[tail.definition.id].forEach(function(sym) {
+                    push(sym);
+                    sym.thedef = def;
+                    sym.name = def.name;
+                });
+                references[def.id].forEach(push);
+                def.orig = orig;
+                def.refs = refs;
+                def.eliminated = def.replaced = 0;
+                def.fixed = tail.definition.fixed && def.fixed;
+                merged[tail.definition.id] = def;
+                break;
+            } while (last.length);
+        }
+
+        function read(def) {
+            prev[def.id] = last.length;
+            last.push({
+                index: index++,
+                definition: def,
+            });
+        }
+
+        function mark(sym, write_only) {
+            var def = sym.definition();
+            if (segment !== self) references[def.id] = false;
+            if (def.id in references) {
+                if (!references[def.id]) return;
+                references[def.id].push(sym);
+                if (def.id in prev) last[prev[def.id]] = null;
+                read(def);
+            } else if (compressor.exposed(def) || self.variables.get(def.name) !== def) {
+                references[def.id] = false;
+            } else {
+                references[def.id] = [ sym ];
+                if (!write_only) return read(def);
+                first.push({
+                    index: index++,
+                    definition: def,
+                });
+            }
+        }
+
+        function push(sym) {
+            if (sym instanceof AST_SymbolRef) {
+                refs.push(sym);
+            } else {
+                orig.push(sym);
+            }
+        }
+    });
+
     AST_Scope.DEFMETHOD("drop_unused", function(compressor) {
         if (!compressor.option("unused")) return;
-        if (compressor.has_directive("use asm")) return;
         var self = this;
-        if (self.pinned()) return;
         var drop_funcs = !(self instanceof AST_Toplevel) || compressor.toplevel.funcs;
         var drop_vars = !(self instanceof AST_Toplevel) || compressor.toplevel.vars;
         var assign_as_unused = /keep_assign/.test(compressor.option("unused")) ? return_false : function(node, props) {
@@ -6451,7 +6627,7 @@ merge(Compressor.prototype, {
             if (self.args.length == 0) return make_node(AST_Function, self, {
                 argnames: [],
                 body: []
-            });
+            }).init_scope_vars(exp.scope);
             if (all(self.args, function(x) {
                 return x instanceof AST_String;
             })) {
@@ -8739,7 +8915,7 @@ merge(Compressor.prototype, {
                 self.expression = make_node(AST_Function, self.expression, {
                     argnames: [],
                     body: []
-                });
+                }).init_scope_vars(exp.scope);
                 break;
               case "Number":
                 self.expression = make_node(AST_Number, self.expression, {
diff --git a/lib/scope.js b/lib/scope.js
index 5d990c06..ec69eb1b 100644
--- a/lib/scope.js
+++ b/lib/scope.js
@@ -279,6 +279,7 @@ AST_Lambda.DEFMETHOD("init_scope_vars", function(parent_scope) {
         start: this.start,
         end: this.end,
     }));
+    return this;
 });
 
 AST_Symbol.DEFMETHOD("mark_enclosed", function(options) {
diff --git a/test/compress/merge_vars.js b/test/compress/merge_vars.js
new file mode 100644
index 00000000..8ef186cf
--- /dev/null
+++ b/test/compress/merge_vars.js
@@ -0,0 +1,233 @@
+merge: {
+    options = {
+        merge_vars: true,
+        toplevel: false,
+    }
+    input: {
+        var a = "foo";
+        console.log(a);
+        function f(b) {
+            var c;
+            console.log(b);
+            c = "bar";
+            console.log(c);
+        }
+        f("baz");
+        var d = "moo";
+        console.log(d);
+    }
+    expect: {
+        var a = "foo";
+        console.log(a);
+        function f(c) {
+            var c;
+            console.log(c);
+            c = "bar";
+            console.log(c);
+        }
+        f("baz");
+        var d = "moo";
+        console.log(d);
+    }
+    expect_stdout: [
+        "foo",
+        "baz",
+        "bar",
+        "moo",
+    ]
+}
+
+merge_toplevel: {
+    options = {
+        merge_vars: true,
+        toplevel: true,
+    }
+    input: {
+        var a = "foo";
+        console.log(a);
+        function f(b) {
+            var c;
+            console.log(b);
+            c = "bar";
+            console.log(c);
+        }
+        f("baz");
+        var d = "moo";
+        console.log(d);
+    }
+    expect: {
+        var d = "foo";
+        console.log(d);
+        function f(c) {
+            var c;
+            console.log(c);
+            c = "bar";
+            console.log(c);
+        }
+        f("baz");
+        var d = "moo";
+        console.log(d);
+    }
+    expect_stdout: [
+        "foo",
+        "baz",
+        "bar",
+        "moo",
+    ]
+}
+
+init_scope_vars: {
+    options = {
+        merge_vars: true,
+        unsafe_proto: true,
+    }
+    input: {
+        Function.prototype.call();
+    }
+    expect: {
+        (function() {}).call();
+    }
+    expect_stdout: true
+}
+
+binary_branch: {
+    options = {
+        merge_vars: true,
+    }
+    input: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            a && (c = b);
+            return c || "PASS";
+        }());
+    }
+    expect: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            a && (c = b);
+            return c || "PASS";
+        }());
+    }
+    expect_stdout: "PASS"
+}
+
+conditional_branch: {
+    options = {
+        merge_vars: true,
+    }
+    input: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            a ? (c = b) : void 0;
+            return c || "PASS";
+        }());
+    }
+    expect: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            a ? (c = b) : void 0;
+            return c || "PASS";
+        }());
+    }
+    expect_stdout: "PASS"
+}
+
+if_branch: {
+    options = {
+        merge_vars: true,
+    }
+    input: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            if (a) c = b;
+            return c || "PASS";
+        }());
+    }
+    expect: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            if (a) c = b;
+            return c || "PASS";
+        }());
+    }
+    expect_stdout: "PASS"
+}
+
+switch_branch: {
+    options = {
+        merge_vars: true,
+    }
+    input: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            switch (a) {
+              case 1:
+                c = b;
+                break;
+            }
+            return c || "PASS";
+        }());
+    }
+    expect: {
+        console.log(function(a) {
+            var b = "FAIL", c;
+            switch (a) {
+              case 1:
+                c = b;
+                break;
+            }
+            return c || "PASS";
+        }());
+    }
+    expect_stdout: "PASS"
+}
+
+read_before_assign_1: {
+    options = {
+        inline: true,
+        merge_vars: true,
+        sequences: true,
+        toplevel: true,
+    }
+    input: {
+        var c = 0;
+        c = 0;
+        (function() {
+            var a = console.log(++a);
+            a;
+        })();
+        c;
+    }
+    expect: {
+        var c = 0;
+        var a;
+        c = 0,
+        a = console.log(++a);
+    }
+    expect_stdout: "NaN"
+}
+
+read_before_assign_2: {
+    options = {
+        dead_code: true,
+        loops: true,
+        merge_vars: true,
+    }
+    input: {
+        console.log(function(a, a) {
+            while (b)
+                return "FAIL";
+            var b = 1;
+            return "PASS";
+        }(0, []));
+    }
+    expect: {
+        console.log(function(a, a) {
+            if (b)
+                return "FAIL";
+            var b = 1;
+            return "PASS";
+        }(0, []));
+    }
+    expect_stdout: "PASS"
+}