dart2js cps: Refactor and optimize string concatenations.

pkg/compiler/lib/src/cps_ir/type_propagation.dart

Index: pkg/compiler/lib/src/cps_ir/type_propagation.dart
diff --git a/pkg/compiler/lib/src/cps_ir/type_propagation.dart b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
index 7ae47a5c134e79a5ad369d2a07259bf3dd9c03d7..c4f557c6953335465dca51320101f809776d0cee 100644
--- a/pkg/compiler/lib/src/cps_ir/type_propagation.dart
+++ b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
@@ -5,12 +5,11 @@
 import 'optimizers.dart' show Pass, ParentVisitor;
 
 import '../constants/constant_system.dart';
-import '../constants/expressions.dart';
 import '../resolution/operators.dart';
 import '../constants/values.dart';
 import '../dart_types.dart' as types;
 import '../dart2jslib.dart' as dart2js;
-import '../tree/tree.dart' show LiteralDartString;
+import '../tree/tree.dart' show DartString, ConsDartString, LiteralDartString;
 import 'cps_ir_nodes.dart';
 import '../types/types.dart' show TypeMask, TypesTask;
 import '../types/constants.dart' show computeTypeMask;
@@ -457,9 +456,7 @@ class TransformingVisitor extends RecursiveVisitor {
 
   /// Make a constant primitive for [constant] and set its entry in [values].
   Constant makeConstantPrimitive(ConstantValue constant) {
-    ConstantExpression constExp =
-        const ConstantExpressionCreator().convert(constant);
-    Constant primitive = new Constant(constExp, constant);
+    Constant primitive = new Constant(constant);
     values[primitive] = new AbstractValue.constantValue(constant,
         typeSystem.getTypeOf(constant));
     return primitive;
@@ -628,6 +625,11 @@ class TransformingVisitor extends RecursiveVisitor {
             return replaceWithBinary(operator, leftArg, rightArg);
           }
         }
+        else if (lattice.isDefinitelyString(left, allowNull: false) &&
+                 lattice.isDefinitelyString(right, allowNull: false)) {
+          return replaceWithBinary(BuiltinOperator.StringConcat,
+                                   leftArg, rightArg);
+        }
       }
     }
     // We should only get here if the node was not specialized.
@@ -645,12 +647,6 @@ class TransformingVisitor extends RecursiveVisitor {
     super.visitInvokeMethod(node);
   }
 
-  void visitConcatenateStrings(ConcatenateStrings node) {
-    Continuation cont = node.continuation.definition;
-    if (constifyExpression(node, cont)) return;
-    super.visitConcatenateStrings(node);
-  }
-
   void visitTypeCast(TypeCast node) {
     Continuation cont = node.continuation.definition;
 
@@ -678,6 +674,24 @@ class TransformingVisitor extends RecursiveVisitor {
     super.visitTypeCast(node);
   }
 
+  void visitInvokeStatic(InvokeStatic node) {
+    Continuation cont = node.continuation.definition;
+    Primitive arg(int n) => node.arguments[n].definition;

[karlklose, 2015/06/19 08:33:45]

Could you inline the two helpers?

[asgerf, 2015/06/19 11:04:34]

We're going to need them anyway.

Why I am doing this:
If pattern matching on the IR turns out to be hopelessly verbose and infeasible,
we would want to know about it ASAP. Implementing one case as if there is only
ever going to be one case will not reveal any such problems, so I am writing it
in a way that I feel would support having more cases added easily.

It also means it IS actually going to easier to add new cases.

I've added a TODO to clarify that we don't have a single-case switch just for
the heck of it.

+    AbstractValue argType(int n) => getValue(arg(n));
+    if (node.target.library.isInternalLibrary) {

[karlklose, 2015/06/19 08:33:45]

Change to one conditional?
  if (node.target.library.isInternalLibrary &&
      node.target.name == InternalMethod.Stringify) {
    ...
  }

[asgerf, 2015/06/19 11:04:34]

See previous reply.

+      switch(node.target.name) {
+        case InternalMethod.Stringify:
+          if (lattice.isDefinitelyString(argType(0))) {
+            InvokeContinuation invoke =
+                new InvokeContinuation(cont, <Primitive>[arg(0)]);

[Kevin Millikin (Google), 2015/06/19 11:36:13]

I wonder if we can come up with a convenient and safe abstraction to take
ownership of references when replacing subterms.

Here we unbox the Reference, allocate a list, map over it to create a new
Reference, add it to the definition's use list, and remove the old reference.

Instead I wish we had: change the reference's parent pointer to point to the
replacement subterm.

[asgerf, 2015/06/19 12:00:52]

Yeah I don't like it either. I tried adding constructors that take references
directly, but it was neither convenient or safe.

+            replaceSubtree(node, invoke);
+            visitInvokeContinuation(invoke);
+          }
+          break;
+      }
+    }
+  }
+
   AbstractValue getValue(Primitive primitive) {
     AbstractValue value = values[primitive];
     return value == null ? new AbstractValue.nothing() : value;
@@ -696,6 +710,63 @@ class TransformingVisitor extends RecursiveVisitor {
     }
   }
 
+  void insertLetPrim(Expression node, Primitive prim) {
+    InteriorNode parent = node.parent;
+    LetPrim let = new LetPrim(prim);
+    parent.body = let;
+    let.body = node;
+    node.parent = let;
+    let.parent = parent;
+  }
+
+  void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
+    switch (node.operator) {
+      case BuiltinOperator.StringConcat:

[karlklose, 2015/06/19 08:33:45]

Use if instead?

[asgerf, 2015/06/19 11:04:34]

Same as previous reply.

+        // Concatenate consecutive constants.
+        bool argumentsWereRemoved = false;
+        int i = 0;
+        while (i < node.arguments.length - 1) {
+          int startOfSequence = i;
+          AbstractValue firstValue = getValue(node.arguments[i++].definition);
+          if (!firstValue.isConstant) continue;
+          AbstractValue secondValue = getValue(node.arguments[i++].definition);
+          if (!secondValue.isConstant) continue;
+
+          DartString getString(AbstractValue value) {

[karlklose, 2015/06/19 08:33:45]

Consider moving this helper to the top of the method.

I would also get rid of the cast (it must also be checked in production mode)
and add a checked mode check instead.

Perhaps like the following:
  DartString getString(AbstractValue value) {
    StringConstantValue constant = value.constant;
    return constant.primitiveValue;
  }

[asgerf, 2015/06/19 11:04:34]

Done.

+            return (value.constant as StringConstantValue).primitiveValue;
+          }
+          DartString string =
+              new ConsDartString(getString(firstValue), getString(secondValue));
+
+          // We found a sequence of at least two constants.
+          // Look for the end of the sequence.
+          while (i < node.arguments.length) {
+            AbstractValue value = getValue(node.arguments[i].definition);
+            if (!value.isConstant) break;
+            string = new ConsDartString(string, getString(value));
+            ++i;
+          }
+          Constant prim =
+              makeConstantPrimitive(new StringConstantValue(string));
+          insertLetPrim(node.parent, prim);
+          for (int k = startOfSequence; k < i; ++k) {
+            node.arguments[k].unlink();
+            node.arguments[k] = null; // Remove the argument after the loop.
+          }
+          node.arguments[startOfSequence] = new Reference<Primitive>(prim);
+          argumentsWereRemoved = true;
+        }
+        if (argumentsWereRemoved) {
+          node.arguments.removeWhere((ref) => ref == null);
+        }
+        // TODO(asgerf): Rebalance nested StringConcats that arise from
+        //               rewriting the + operator to StringConcat.
+        break;
+
+      default:
+    }
+  }
+
   Primitive visitTypeTest(TypeTest node) {
     Primitive prim = node.value.definition;
     AbstractValue value = getValue(prim);
@@ -732,6 +803,10 @@ class TransformingVisitor extends RecursiveVisitor {
     } else {
       Primitive newPrim = visit(node.primitive);
       if (newPrim != null) {
+        if (!values.containsKey(newPrim)) {
+          // If the type was not set, default to the same type as before.
+          values[newPrim] = values[node.primitive];
+        }
         newPrim.substituteFor(node.primitive);
         RemovalVisitor.remove(node.primitive);
         node.primitive = newPrim;
@@ -904,10 +979,22 @@ class TypePropagationVisitor implements Visitor {
 
     assert(cont.parameters.length == 1);
     Parameter returnValue = cont.parameters[0];
-    Entity target = node.target;
-    TypeMask returnType = target is FieldElement
-        ? typeSystem.dynamicType
-        : typeSystem.getReturnType(node.target);
+
+    if (node.target.library.isInternalLibrary) {
+      switch (node.target.name) {

[karlklose, 2015/06/19 08:33:45]

Use if?

[asgerf, 2015/06/19 11:04:34]

See previous reply.

+        case InternalMethod.Stringify:
+          AbstractValue argValue = getValue(node.arguments[0].definition);
+          if (argValue.isNothing) return; // And come back later.
+          if (lattice.isDefinitelyString(argValue)) {
+            setValue(returnValue, argValue);
+          } else {
+            setValue(returnValue, nonConstant(typeSystem.stringType));
+          }
+          return;
+      }
+    }
+
+    TypeMask returnType = typeSystem.getReturnType(node.target);
     setValue(returnValue, nonConstant(returnType));
   }
 
@@ -981,8 +1068,34 @@ class TypePropagationVisitor implements Visitor {
   }
 
   void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
-    // Not actually reachable yet.
-    // TODO(asgerf): Implement type propagation for builtin operators.
+    // Note that most built-in operators do not exist before the transformation
+    // pass after this analysis has finished.
+    switch (node.operator) {
+      case BuiltinOperator.StringConcat:

[karlklose, 2015/06/19 08:33:45]

Use if?

[asgerf, 2015/06/19 11:04:34]

Same.

+        DartString stringValue = const LiteralDartString('');
+        for (Reference<Primitive> arg in node.arguments) {
+          AbstractValue value = getValue(arg.definition);
+          if (value.isNothing) {
+            return; // And come back later
+          } else if (value.isConstant &&
+                     value.constant.isString &&
+                     stringValue != null) {
+            StringConstantValue constant = value.constant;
+            stringValue =
+                new ConsDartString(stringValue, constant.primitiveValue);
+          } else {
+            stringValue = null;
+            break;
+          }
+        }
+        if (stringValue == null) {
+          setValue(node, nonConstant(typeSystem.stringType));
+        } else {
+          setValue(node, constantValue(new StringConstantValue(stringValue)));
+        }
+        break;
+      default:
+    }
     setValue(node, nonConstant());
   }
 
@@ -1005,50 +1118,6 @@ class TypePropagationVisitor implements Visitor {
     setValue(returnValue, nonConstant(typeSystem.getReturnType(node.target)));
   }
 
-  void visitConcatenateStrings(ConcatenateStrings node) {
-    Continuation cont = node.continuation.definition;
-    setReachable(cont);
-
-    /// Sets the value of the target continuation parameter, and possibly
-    /// try to replace the whole invocation with a constant.
-    void setResult(AbstractValue updateValue, {bool canReplace: false}) {
-      Parameter returnValue = cont.parameters[0];
-      setValue(returnValue, updateValue);
-      if (canReplace && updateValue.isConstant) {
-        replacements[node] = updateValue.constant;
-      } else {
-        // A previous iteration might have tried to replace this.
-        replacements.remove(node);
-      }
-    }
-
-    // TODO(jgruber): Currently we only optimize if all arguments are string
-    // constants, but we could also handle cases such as "foo${42}".
-    bool allStringConstants = node.arguments.every((Reference ref) {
-      if (!(ref.definition is Constant)) {
-        return false;
-      }
-      Constant constant = ref.definition;
-      return constant != null && constant.value.isString;
-    });
-
-    TypeMask type = typeSystem.stringType;
-    assert(cont.parameters.length == 1);
-    if (allStringConstants) {
-      // All constant, we can concatenate ourselves.
-      Iterable<String> allStrings = node.arguments.map((Reference ref) {
-        Constant constant = ref.definition;
-        StringConstantValue stringConstant = constant.value;
-        return stringConstant.primitiveValue.slowToString();
-      });
-      LiteralDartString dartString = new LiteralDartString(allStrings.join());
-      ConstantValue constant = new StringConstantValue(dartString);
-      setResult(constantValue(constant, type), canReplace: true);
-    } else {
-      setResult(nonConstant(type));
-    }
-  }
-
   void visitThrow(Throw node) {
   }
 
@@ -1367,76 +1436,7 @@ class AbstractValue {
   }
 }
 
-class ConstantExpressionCreator
-    implements ConstantValueVisitor<ConstantExpression, dynamic> {
-
-  const ConstantExpressionCreator();
-
-  ConstantExpression convert(ConstantValue value) => value.accept(this, null);
-
-  @override
-  ConstantExpression visitBool(BoolConstantValue constant, _) {
-    return new BoolConstantExpression(constant.primitiveValue);
-  }
-
-  @override
-  ConstantExpression visitConstructed(ConstructedConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitConstructed");
-  }
-
-  @override
-  ConstantExpression visitDeferred(DeferredConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitDeferred");
-  }
-
-  @override
-  ConstantExpression visitDouble(DoubleConstantValue constant, arg) {
-    return new DoubleConstantExpression(constant.primitiveValue);
-  }
-
-  @override
-  ConstantExpression visitSynthetic(SyntheticConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitSynthetic");
-  }
-
-  @override
-  ConstantExpression visitFunction(FunctionConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitFunction");
-  }
-
-  @override
-  ConstantExpression visitInt(IntConstantValue constant, arg) {
-    return new IntConstantExpression(constant.primitiveValue);
-  }
-
-  @override
-  ConstantExpression visitInterceptor(InterceptorConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitInterceptor");
-  }
-
-  @override
-  ConstantExpression visitList(ListConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitList");
-  }
-
-  @override
-  ConstantExpression visitMap(MapConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitMap");
-  }
-
-  @override
-  ConstantExpression visitNull(NullConstantValue constant, arg) {
-    return new NullConstantExpression();
-  }
-
-  @override
-  ConstantExpression visitString(StringConstantValue constant, arg) {
-    return new StringConstantExpression(
-        constant.primitiveValue.slowToString());
-  }
-
-  @override
-  ConstantExpression visitType(TypeConstantValue constant, arg) {
-    throw new UnsupportedError("ConstantExpressionCreator.visitType");
-  }
-}
+/// Enum-like class with the names of internal methods we care about.
+abstract class InternalMethod {
+  static const String Stringify = 'S';

[karlklose, 2015/06/19 08:33:45]

Make this a predicate to test on the element instead.  Maybe there is already a
field on the compiler that holds the element.

[asgerf, 2015/06/19 11:04:34]

Are you proposing this?

isStringify(FunctionElement e) => e.library.isInternalLibrary && e.name == 'S'

I don't get it. Why would a predicate be better than a constant?

Or this?

isStringify(FunctionElement e, JavaScriptBackend backend) {
    return backend.getStringInterpolationHelper() == e;
}

That would look up the name 'S' in the library's environment to see if we get
out the element we are already holding. Instead of just looking at the library
and name of that element.

I would prefer not to introduce computational redundancy in the name of some
encapsulation principle that IMO has utterly failed to work in this compiler.

+}