dart2js cps: Clone small constants to use site.

pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart

Index: pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
diff --git a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
index c36a394fa77728ca74c897c41f76bff613d5c370..1dda41d5cbdf7a6147843892bb9db0fd38a0dcb5 100644
--- a/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
+++ b/pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart
@@ -53,6 +53,7 @@ class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ {
       <cps_ir.Primitive, Variable>{};
   final Map<cps_ir.MutableVariable, Variable> mutable2variable =
       <cps_ir.MutableVariable, Variable>{};
+  final Set<cps_ir.Constant> inlinedConstants = new Set<cps_ir.Constant>();
 
   // Continuations with more than one use are replaced with Tree labels.  This
   // is the mapping from continuations to labels.
@@ -109,6 +110,9 @@ class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ {
   /// returned expression must be used in the tree.
   Expression getVariableUse(cps_ir.Reference<cps_ir.Primitive> reference) {
     cps_ir.Primitive prim = reference.definition.effectiveDefinition;
+    if (prim is cps_ir.Constant && inlinedConstants.contains(prim)) {
+      return new Constant(prim.value);
+    }
     if (thisParameter != null && prim == thisParameter) {
       return new This();
     }
@@ -279,6 +283,54 @@ class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ {
     return prim.accept(this);
   }
 
+  /************************ CONSTANT COPYING *****************************/
+
+  /// Estimate of the number of characters needed to emit a use of the given
+  /// constant.
+  int constantSize(PrimitiveConstantValue value) {
+    if (value is StringConstantValue) {
+      // Account for the quotes, but ignore the cost of escape sequences to
+      // avoid traversing the string.

[sra1, 2015/12/16 18:40:12]

Note. The size will depend on the output encoding too (utf8 does not need
escaping, giving e.g. 3 bytes, vs 6 bytes for ascii escaped \uXXXX)

[asgerf, 2015/12/17 15:51:52]

Updated the comment to reflect this.

+      return value.length + 2;
+    } else {
+      return '${value.primitiveValue}'.length;

[sra1, 2015/12/16 18:40:12]

We generate true and false as !0 and !1 in minified code.
We generate numbers in shorter forms too, e.g. 1230000 as 123e4 when minifying.

see js_backend/constant_emitter.dart

Given that we are about to clone the constant, does it make sense to generate
the JS for it now (for an exact measurement) and reuse the AST later?

[asgerf, 2015/12/17 15:51:52]

Bools -> done.

Added a TODO for the rest. We could interface with the emitter, but I think it's
overkill.

+    }
+  }
+
+  /// The number of uses [prim] has, or `-1` if it is used in a phi assignment
+  /// which is likely to be eliminated after liveness analysis.
+  int countNonPhiUses(cps_ir.Primitive prim) {
+    int count = 0;
+    for (cps_ir.Reference ref = prim.firstRef; ref != null; ref = ref.next) {
+      cps_ir.Node use = ref.parent;
+      if (use is cps_ir.InvokeContinuation) {
+        cps_ir.Continuation cont = use.continuation.definition;
+        int index = use.arguments.indexOf(ref);
+        if (cont.parameters[index].hint == prim.hint) {

[sra1, 2015/12/16 18:40:12]

Is this because they are both null or both something else?
I'm a bit nervous that a pass that tried to pick nice names might

[asgerf, 2015/12/17 15:51:52]

(this is also in response to the comment below)

The register allocation will only merge variables with the same hint. But it
turns out that phi assignments in general tend to be pretty bad so I changed
this to just look any kind of phi assignment.

After merging variables, we would need def-use analysis to propagate constants
to the right uses, so our last chance to do this is after register allocation,
but before variables have actually been merged.

At that point we know which phi assignments become identity assignments, and how
many variables there are going to be.  I tried this, but I wasn't able to make
it better than this, and trying to be very clever about it actually made it
worse.  There are cases where cloning forces an "else" to be generated or a
block to get its curly braces.  It seems better to just not mess with the phis
at all, even if it's not an identity assignment.

This is just not something can solve exactly.

+          return -1;
+        }
+      }
+      count++;
+    }
+    return count;
+  }
+
+  /// True if the given [constant] should be copied to every use site.
+  bool shouldCopyToUses(cps_ir.Constant constant) {
+    if (!constant.value.isPrimitive) return false;
+    if (constant.hasAtMostOneUse) return true;
+    int uses = countNonPhiUses(constant);
+    if (uses == -1) return false; // Copying might prevent elimination of a phi.
+    int size = constantSize(constant.value);
+    // Compare the expected code size output of copying vs sharing.
+    const int USE = 2; // Minified locals usually have length 2.

[sra1, 2015/12/16 18:40:12]

Only in 'large' functions.

Can we estimate the number of temps and use 1 if the function is 'small'?
(Or at least add a TODO to refine this).

We could use more single-byte names with a little analysis to see e.g. if 'C'
and 'J' are unused.

[asgerf, 2015/12/17 15:51:52]

Changed to 1.  I just wanted to use the common case and I somehow got the idea
that one-byte variable names were never generated.

+    const int ASSIGN = USE + 2; // Variable and '=' and ';'
+    const int BIAS = 2; // Artificial bias to slightly favor copying.
+    int costOfSharing = USE * uses + size + ASSIGN + BIAS;
+    int costOfCopying = size * uses;
+    return costOfCopying <= costOfSharing;
+  }
+
   /************************ INTERIOR EXPRESSIONS  ************************/
   //
   // Visit methods for interior expressions must return a function:
@@ -287,6 +339,10 @@ class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ {
   //
 
   NodeCallback visitLetPrim(cps_ir.LetPrim node) {
+    if (node.primitive is cps_ir.Constant && shouldCopyToUses(node.primitive)) {
+      inlinedConstants.add(node.primitive);
+      return (Statement next) => next;
+    }
     Variable variable = getVariable(node.primitive);
     var value = translatePrimitive(node.primitive);
     if (value is Expression) {