dart2js cps: Clone small constants to use site.

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

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library tree_ir_builder;
 
 import '../common.dart';
 import '../constants/values.dart';
 import '../cps_ir/cps_ir_nodes.dart' as cps_ir;
 import '../elements/elements.dart';
@@ skipping 35 matching lines @@
  * particular, intermediate values and blocks used for local control flow are
  * still all named.
  */
 class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ {
   final InternalErrorFunction internalError;
 
   final Map<cps_ir.Primitive, Variable> primitive2variable =
       <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.
   final Map<cps_ir.Continuation, Label> labels = <cps_ir.Continuation, Label>{};
 
   ExecutableElement currentElement;
   /// The 'this' Parameter for currentElement or the enclosing method.
   cps_ir.Parameter thisParameter;
   cps_ir.Continuation returnContinuation;
 
@@ skipping 36 matching lines @@
     return primitive2variable.putIfAbsent(primitive,
         () => new Variable(currentElement, primitive.hint));
   }
 
   /// Obtains a reference to the tree Variable corresponding to the IR primitive
   /// referred to by [reference].
   /// This increments the reference count for the given variable, so the
   /// 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();
     }
     return new VariableUse(getVariable(prim));
   }
 
   Expression getVariableUseOrNull(
         cps_ir.Reference<cps_ir.Primitive> reference) {
     return reference == null ? null : getVariableUse(reference);
   }
@@ skipping 150 matching lines @@
     return result;
   }
 
   /// Translates a CPS primitive to a tree expression.
   ///
   /// This simply calls the visit method for the primitive.
   translatePrimitive(cps_ir.Primitive prim) {
     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:
   //
   //    (Statement next) => <result statement>
   //
 
   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) {
       if (node.primitive.hasAtLeastOneUse) {
         return (Statement next) => Assign.makeStatement(variable, value, next);
       } else {
         return (Statement next) => new ExpressionStatement(value, next);
       }
     } else {
       assert(value is NodeCallback);
@@ skipping 399 matching lines @@
     internalError(CURRENT_ELEMENT_SPANNABLE, 'Unexpected IR node: $node');
   }
 
   visitFunctionDefinition(cps_ir.FunctionDefinition node) {
     unexpectedNode(node);
   }
   visitParameter(cps_ir.Parameter node) => unexpectedNode(node);
   visitContinuation(cps_ir.Continuation node) => unexpectedNode(node);
   visitMutableVariable(cps_ir.MutableVariable node) => unexpectedNode(node);
 }