From 00e4f7b3c15437df90cf06dabb096fd0576e1814 Mon Sep 17 00:00:00 2001 From: "Alex Lam S.L" Date: Fri, 16 Jun 2017 19:19:54 +0800 Subject: [PATCH] in-place `tigten_body()` (#2111) By reducing copies of `AST_Node` arrays, we should be able to reduce: - memory pressure - potential bugs caused by multiple references in AST - duplicated executions of `OPT()` --- lib/compress.js | 317 +++++++++++++++++++++++------------------------- 1 file changed, 153 insertions(+), 164 deletions(-) diff --git a/lib/compress.js b/lib/compress.js index a4552e85..3bf54da0 100644 --- a/lib/compress.js +++ b/lib/compress.js @@ -668,26 +668,24 @@ merge(Compressor.prototype, { var CHANGED, max_iter = 10; do { CHANGED = false; - statements = eliminate_spurious_blocks(statements); + eliminate_spurious_blocks(statements); if (compressor.option("dead_code")) { - statements = eliminate_dead_code(statements, compressor); + eliminate_dead_code(statements, compressor); } if (compressor.option("if_return")) { - statements = handle_if_return(statements, compressor); + handle_if_return(statements, compressor); } if (compressor.sequences_limit > 0) { - statements = sequencesize(statements, compressor); + sequencesize(statements, compressor); } if (compressor.option("join_vars")) { - statements = join_consecutive_vars(statements, compressor); + join_consecutive_vars(statements, compressor); } if (compressor.option("collapse_vars")) { - statements = collapse(statements, compressor); + collapse(statements, compressor); } } while (CHANGED && max_iter-- > 0); - return statements; - // Search from right to left for assignment-like expressions: // - `var a = x;` // - `a = x;` @@ -789,7 +787,6 @@ merge(Compressor.prototype, { if (replaced && !remove_candidate(candidate)) statements.splice(stat_index, 1); } } - return statements; function extract_candidates(expr) { if (expr instanceof AST_Assign && !expr.left.has_side_effects(compressor) @@ -891,59 +888,60 @@ merge(Compressor.prototype, { function eliminate_spurious_blocks(statements) { var seen_dirs = []; - return statements.reduce(function(a, stat){ + for (var i = 0; i < statements.length;) { + var stat = statements[i]; if (stat instanceof AST_BlockStatement) { CHANGED = true; - a.push.apply(a, eliminate_spurious_blocks(stat.body)); + eliminate_spurious_blocks(stat.body); + [].splice.apply(statements, [i, 1].concat(stat.body)); + i += stat.body.length; } else if (stat instanceof AST_EmptyStatement) { CHANGED = true; + statements.splice(i, 1); } else if (stat instanceof AST_Directive) { if (seen_dirs.indexOf(stat.value) < 0) { - a.push(stat); + i++; seen_dirs.push(stat.value); } else { CHANGED = true; + statements.splice(i, 1); } - } else { - a.push(stat); - } - return a; - }, []); - }; + } else i++; + } + } function handle_if_return(statements, compressor) { var self = compressor.self(); var multiple_if_returns = has_multiple_if_returns(statements); var in_lambda = self instanceof AST_Lambda; - var ret = []; // Optimized statements, build from tail to front - loop: for (var i = statements.length; --i >= 0;) { + for (var i = statements.length; --i >= 0;) { var stat = statements[i]; - switch (true) { - case (in_lambda && stat instanceof AST_Return && !stat.value && ret.length == 0): + var next = statements[i + 1]; + + if (in_lambda && stat instanceof AST_Return && !stat.value && !next) { CHANGED = true; - // note, ret.length is probably always zero - // because we drop unreachable code before this - // step. nevertheless, it's good to check. - continue loop; - case stat instanceof AST_If: + statements.length--; + continue; + } + + if (stat instanceof AST_If) { var ab = aborts(stat.body); if (can_merge_flow(ab)) { if (ab.label) { remove(ab.label.thedef.references, ab); } CHANGED = true; - var funs = extract_functions_from_statement_array(ret); - var body = as_statement_array_with_return(stat.body, ab); stat = stat.clone(); stat.condition = stat.condition.negate(compressor); + var body = as_statement_array_with_return(stat.body, ab); stat.body = make_node(AST_BlockStatement, stat, { - body: as_statement_array(stat.alternative).concat(ret) + body: as_statement_array(stat.alternative).concat(extract_functions()) }); stat.alternative = make_node(AST_BlockStatement, stat, { body: body }); - ret = [ stat.transform(compressor) ].concat(funs); - continue loop; + statements[i] = stat.transform(compressor); + continue; } var ab = aborts(stat.alternative); @@ -952,81 +950,71 @@ merge(Compressor.prototype, { remove(ab.label.thedef.references, ab); } CHANGED = true; - var funs = extract_functions_from_statement_array(ret); stat = stat.clone(); stat.body = make_node(AST_BlockStatement, stat.body, { - body: as_statement_array(stat.body).concat(ret) + body: as_statement_array(stat.body).concat(extract_functions()) }); var body = as_statement_array_with_return(stat.alternative, ab); stat.alternative = make_node(AST_BlockStatement, stat.alternative, { body: body }); - ret = [ stat.transform(compressor) ].concat(funs); - continue loop; + statements[i] = stat.transform(compressor); + continue; } + } - if (stat.body instanceof AST_Return) { - var value = stat.body.value; - //--- - // pretty silly case, but: - // if (foo()) return; return; ==> foo(); return; - if ((in_lambda && ret.length == 0 || ret[0] instanceof AST_Return && !ret[0].value) - && !value && !stat.alternative) { - CHANGED = true; - var cond = make_node(AST_SimpleStatement, stat.condition, { - body: stat.condition - }); - ret.unshift(cond); - continue loop; - } - //--- - // if (foo()) return x; return y; ==> return foo() ? x : y; - if (ret[0] instanceof AST_Return && value && ret[0].value && !stat.alternative) { - CHANGED = true; - stat = stat.clone(); - stat.alternative = ret[0]; - ret[0] = stat.transform(compressor); - continue loop; - } - //--- - // if (foo()) return x; [ return ; ] ==> return foo() ? x : undefined; - if (multiple_if_returns && (ret.length == 0 || ret[0] instanceof AST_Return) - && value && !stat.alternative && in_lambda) { - CHANGED = true; - stat = stat.clone(); - stat.alternative = ret[0] || make_node(AST_Return, stat, { - value: null - }); - ret[0] = stat.transform(compressor); - continue loop; - } - //--- - // if (a) return b; if (c) return d; e; ==> return a ? b : c ? d : void e; - // - // if sequences is not enabled, this can lead to an endless loop (issue #866). - // however, with sequences on this helps producing slightly better output for - // the example code. - if (compressor.option("sequences") - && i > 0 && statements[i - 1] instanceof AST_If && statements[i - 1].body instanceof AST_Return - && ret.length == 1 && in_lambda && ret[0] instanceof AST_SimpleStatement - && !stat.alternative) { - CHANGED = true; - ret.push(make_node(AST_Return, ret[0], { - value: null - }).transform(compressor)); - ret.unshift(stat); - continue loop; - } + if (stat instanceof AST_If && stat.body instanceof AST_Return) { + var value = stat.body.value; + //--- + // pretty silly case, but: + // if (foo()) return; return; ==> foo(); return; + if (!value && !stat.alternative + && (in_lambda && !next || next instanceof AST_Return && !next.value)) { + CHANGED = true; + statements[i] = make_node(AST_SimpleStatement, stat.condition, { + body: stat.condition + }); + continue; + } + //--- + // if (foo()) return x; return y; ==> return foo() ? x : y; + if (value && !stat.alternative && next instanceof AST_Return && next.value) { + CHANGED = true; + stat = stat.clone(); + stat.alternative = next; + statements.splice(i, 2, stat.transform(compressor)); + continue; + } + //--- + // if (foo()) return x; [ return ; ] ==> return foo() ? x : undefined; + if (multiple_if_returns && in_lambda && value && !stat.alternative + && (!next || next instanceof AST_Return)) { + CHANGED = true; + stat = stat.clone(); + stat.alternative = next || make_node(AST_Return, stat, { + value: null + }); + statements.splice(i, next ? 2 : 1, stat.transform(compressor)); + continue; + } + //--- + // if (a) return b; if (c) return d; e; ==> return a ? b : c ? d : void e; + // + // if sequences is not enabled, this can lead to an endless loop (issue #866). + // however, with sequences on this helps producing slightly better output for + // the example code. + var prev = statements[i - 1]; + if (compressor.option("sequences") && in_lambda && !stat.alternative + && prev instanceof AST_If && prev.body instanceof AST_Return + && i + 2 == statements.length && next instanceof AST_SimpleStatement) { + CHANGED = true; + statements.push(make_node(AST_Return, next, { + value: null + }).transform(compressor)); + continue; } - - ret.unshift(stat); - break; - default: - ret.unshift(stat); - break; } } - return ret; function has_multiple_if_returns(statements) { var n = 0; @@ -1051,6 +1039,18 @@ merge(Compressor.prototype, { || ab instanceof AST_Break && lct instanceof AST_BlockStatement && self === lct; } + function extract_functions() { + var tail = statements.slice(i + 1); + statements.length = i + 1; + return tail.filter(function(stat) { + if (stat instanceof AST_Defun) { + statements.push(stat); + return false; + } + return true; + }); + } + function as_statement_array_with_return(node, ab) { var body = as_statement_array(node).slice(0, -1); if (ab.value) { @@ -1060,49 +1060,52 @@ merge(Compressor.prototype, { } return body; } - }; + } function eliminate_dead_code(statements, compressor) { - var has_quit = false; - var orig = statements.length; + var has_quit; var self = compressor.self(); - statements = statements.reduce(function(a, stat){ - if (has_quit) { - extract_declarations_from_unreachable_code(compressor, stat, a); - } else { - if (stat instanceof AST_LoopControl) { - var lct = compressor.loopcontrol_target(stat); - if ((stat instanceof AST_Break - && !(lct instanceof AST_IterationStatement) - && loop_body(lct) === self) || (stat instanceof AST_Continue - && loop_body(lct) === self)) { - if (stat.label) { - remove(stat.label.thedef.references, stat); - } - } else { - a.push(stat); + for (var i = 0, n = 0, len = statements.length; i < len; i++) { + var stat = statements[i]; + if (stat instanceof AST_LoopControl) { + var lct = compressor.loopcontrol_target(stat); + if (stat instanceof AST_Break + && !(lct instanceof AST_IterationStatement) + && loop_body(lct) === self + || stat instanceof AST_Continue + && loop_body(lct) === self) { + if (stat.label) { + remove(stat.label.thedef.references, stat); } } else { - a.push(stat); + statements[n++] = stat; } - if (aborts(stat)) has_quit = true; + } else { + statements[n++] = stat; } - return a; - }, []); - CHANGED = statements.length != orig; - return statements; - }; + if (aborts(stat)) { + has_quit = statements.slice(i + 1); + break; + } + } + statements.length = n; + CHANGED = n != len; + if (has_quit) has_quit.forEach(function(stat) { + extract_declarations_from_unreachable_code(compressor, stat, statements); + }); + } function sequencesize(statements, compressor) { - if (statements.length < 2) return statements; - var seq = [], ret = []; + if (statements.length < 2) return; + var seq = [], n = 0; function push_seq() { if (!seq.length) return; var body = make_sequence(seq[0], seq); - ret.push(make_node(AST_SimpleStatement, body, { body: body })); + statements[n++] = make_node(AST_SimpleStatement, body, { body: body }); seq = []; - }; - statements.forEach(function(stat){ + } + for (var i = 0, len = statements.length; i < len; i++) { + var stat = statements[i]; if (stat instanceof AST_SimpleStatement) { if (seq.length >= compressor.sequences_limit) push_seq(); var body = stat.body; @@ -1110,18 +1113,18 @@ merge(Compressor.prototype, { if (body) merge_sequence(seq, body); } else { push_seq(); - ret.push(stat); + statements[n++] = stat; } - }); + } push_seq(); - ret = sequencesize_2(ret, compressor); - CHANGED = ret.length != statements.length; - return ret; - }; + statements.length = n; + sequencesize_2(statements, compressor); + CHANGED = statements.length != len; + } function sequencesize_2(statements, compressor) { function cons_seq(right) { - ret.pop(); + n--; var left = prev.body; if (!(left instanceof AST_Sequence)) { left = make_node(AST_Sequence, left, { @@ -1131,8 +1134,9 @@ merge(Compressor.prototype, { merge_sequence(left.expressions, right); return left.transform(compressor); }; - var ret = [], prev = null; - statements.forEach(function(stat){ + var n = 0, prev; + for (var i = 0, len = statements.length; i < len; i++) { + var stat = statements[i]; if (prev) { if (stat instanceof AST_For) { try { @@ -1145,7 +1149,7 @@ merge(Compressor.prototype, { } else if (!stat.init) { stat.init = prev.body.drop_side_effect_free(compressor); - ret.pop(); + n--; } } catch(ex) { if (ex !== cons_seq) throw ex; @@ -1167,15 +1171,16 @@ merge(Compressor.prototype, { stat.expression = cons_seq(stat.expression); } } - ret.push(stat); + statements[n++] = stat; prev = stat instanceof AST_SimpleStatement ? stat : null; - }); - return ret; - }; + } + statements.length = n; + } function join_consecutive_vars(statements, compressor) { - var prev = null; - return statements.reduce(function(a, stat){ + for (var i = 0, j = -1, len = statements.length; i < len; i++) { + var stat = statements[i]; + var prev = statements[j]; if (stat instanceof AST_Definitions && prev && prev.TYPE == stat.TYPE) { prev.definitions = prev.definitions.concat(stat.definitions); CHANGED = true; @@ -1184,35 +1189,19 @@ merge(Compressor.prototype, { && prev instanceof AST_Var && (!stat.init || stat.init.TYPE == prev.TYPE)) { CHANGED = true; - a.pop(); if (stat.init) { stat.init.definitions = prev.definitions.concat(stat.init.definitions); } else { stat.init = prev; } - a.push(stat); - prev = stat; + statements[j] = stat; } else { - prev = stat; - a.push(stat); + statements[++j] = stat; } - return a; - }, []); - }; - - }; - - function extract_functions_from_statement_array(statements) { - var funs = []; - for (var i = statements.length - 1; i >= 0; --i) { - var stat = statements[i]; - if (stat instanceof AST_Defun) { - statements.splice(i, 1); - funs.unshift(stat); } - } - return funs; + statements.length = j + 1; + }; } function extract_declarations_from_unreachable_code(compressor, stat, target) { @@ -1989,12 +1978,12 @@ merge(Compressor.prototype, { }); OPT(AST_Block, function(self, compressor){ - self.body = tighten_body(self.body, compressor); + tighten_body(self.body, compressor); return self; }); OPT(AST_BlockStatement, function(self, compressor){ - self.body = tighten_body(self.body, compressor); + tighten_body(self.body, compressor); switch (self.body.length) { case 1: return self.body[0]; case 0: return make_node(AST_EmptyStatement, self); @@ -2901,7 +2890,7 @@ merge(Compressor.prototype, { }); OPT(AST_Try, function(self, compressor){ - self.body = tighten_body(self.body, compressor); + tighten_body(self.body, compressor); if (self.bcatch && self.bfinally && all(self.bfinally.body, is_empty)) self.bfinally = null; if (all(self.body, is_empty)) { var body = []; -- 2.34.1