dart2js cps: Refactor tracking of side effects.

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

 // Copyright (c) 2013, 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 dart2js.ir_nodes;
 
 import 'dart:collection';
 import 'cps_fragment.dart' show CpsFragment;
 import 'cps_ir_nodes_sexpr.dart';
 import '../constants/values.dart' as values;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
 import '../io/source_information.dart' show SourceInformation;
 import '../types/types.dart' show TypeMask;
 import '../universe/selector.dart' show Selector;
+import '../universe/side_effects.dart';
 
 import 'builtin_operator.dart';
 export 'builtin_operator.dart';
 
+import 'effects.dart';
+
 // These imports are only used for the JavaScript specific nodes.  If we want to
 // support more than one native backend, we should probably create better
 // abstractions for native code and its type and effect system.
 import '../js/js.dart' as js show Template, isNullGuardOnFirstArgument;
 import '../native/native.dart' as native show NativeBehavior;
 
 abstract class Node {
   /// A pointer to the parent node. Is null until set by optimization passes.
   Node parent;
 
@@ skipping 206 matching lines @@
 
 /// A named value.
 ///
 /// The identity of the [Primitive] object is the name of the value.
 /// The subclass describes how to compute the value.
 ///
 /// All primitives except [Parameter] must be bound by a [LetPrim].
 abstract class Primitive extends Variable<Primitive> {
   Primitive() : super(null);
 
+  int get effectFlags => Effects.none;

[Siggi Cherem (dart-lang), 2016/02/17 20:53:23]

+ dartdoc

Also, low-priority but, what do you think about simply calling this `effects`?

[asgerf, 2016/02/29 12:48:17]

Done.

+
   /// True if this primitive has a value that can be used by other expressions.
   bool get hasValue;
 
   /// True if the primitive can be removed, assuming it has no uses
   /// (this getter does not check if there are any uses).
   ///
   /// False must be returned for primitives that may throw, diverge, or have
   /// observable side-effects.
   bool get isSafeForElimination;
 
@@ skipping 83 matching lines @@
     replaceUsesWith(newPrimitive);
     destroy();
     LetPrim let = parent;
     fragment.insertBelow(let);
     let.remove();
   }
 }
 
 /// A primitive that is generally not safe for elimination, but may be marked
 /// as safe by type propagation
-//
-// TODO(asgerf): Store the flag in a bitmask in [Primitive] and get rid of this
-//               class.
 abstract class UnsafePrimitive extends Primitive {
+  int effectFlags = Effects.all;
   bool isSafeForElimination = false;
   bool isSafeForReordering = false;
 }
 
 /// Operands to invocations and primitives are always variables.  They point to
 /// their definition and are doubly-linked into a list of occurrences.
 class Reference<T extends Definition<T>> {
   T definition;
   Reference<T> previous;
   Reference<T> next;
@@ skipping 714 matching lines @@
   accept(Visitor visitor) => visitor.visitApplyBuiltinMethod(this);
 
   bool get hasValue => true;
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
 
   void setParentPointers() {
     receiver.parent = this;
     _setParentsOnList(arguments, this);
   }
+
+  int get effectFlags => getEffectsOfBuiltinMethod(method);
 }
 
 /// Throw a value.
 ///
 /// Throw is an expression, i.e., it always occurs in tail position with
 /// respect to a body or expression.
 class Throw extends TailExpression {
   Reference<Primitive> value;
 
   Throw(Primitive value) : value = new Reference<Primitive>(value);
@@ skipping 175 matching lines @@
   accept(Visitor visitor) => visitor.visitSetField(this);
 
   bool get hasValue => false;
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
 
   void setParentPointers() {
     object.parent = this;
     value.parent = this;
   }
+
+  int get effectFlags => Effects.changesInstanceField;
 }
 
 /// Directly reads from a field on a given object.
 ///
 /// The [object] must either be `null` or an object that has [field].
 class GetField extends Primitive {
   final Reference<Primitive> object;
   FieldElement field;
+  bool isFinal = false;

[Siggi Cherem (dart-lang), 2016/02/17 20:53:23]

+dartdoc

[asgerf, 2016/02/29 12:48:17]

Done.

 
   /// True if the object is known not to be null.
   // TODO(asgerf): This is a placeholder until we agree on how to track
   //               side effects.
   bool objectIsNotNull = false;
 
   GetField(Primitive object, this.field)
       : this.object = new Reference<Primitive>(object);
 
   accept(Visitor visitor) => visitor.visitGetField(this);
 
   bool get hasValue => true;
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   toString() => 'GetField($field)';
 
   void setParentPointers() {
     object.parent = this;
   }
+
+  int get effectFlags => isFinal ? 0 : Effects.dependsOnInstanceField;
 }
 
 /// Get the length of a string or native list.
 class GetLength extends Primitive {
   final Reference<Primitive> object;
+  bool isFinal = false;
 
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
   GetLength(Primitive object) : this.object = new Reference<Primitive>(object);
 
   bool get hasValue => true;
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetLength(this);
 
   void setParentPointers() {
     object.parent = this;
   }
+
+  int get effectFlags => isFinal ? 0 : Effects.dependsOnIndexableLength;
 }
 
 /// Read an entry from an indexable object.
 ///
 /// [object] must be null or an indexable object, and [index] must be
 /// an integer where `0 <= index < object.length`.
 class GetIndex extends Primitive {
   final Reference<Primitive> object;
   final Reference<Primitive> index;
 
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
   GetIndex(Primitive object, Primitive index)
       : this.object = new Reference<Primitive>(object),
         this.index = new Reference<Primitive>(index);
 
   bool get hasValue => true;
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetIndex(this);
 
   void setParentPointers() {
     object.parent = this;
     index.parent = this;
   }
+
+  int get effectFlags => Effects.dependsOnIndexableContent;
 }
 
 /// Set an entry on a native list.
 ///
-/// [object] must be null or a native list, and [index] must be an integer.
+/// [object] must be null or a native list, and [index] must be an integer
+/// within the bounds of the indexable object.
+///
+/// [SetIndex] may not be used to alter the length of a JS array.
 ///
 /// The primitive itself has no value and may not be referenced.
 class SetIndex extends Primitive {
   final Reference<Primitive> object;
   final Reference<Primitive> index;
   final Reference<Primitive> value;
 
   SetIndex(Primitive object, Primitive index, Primitive value)
       : this.object = new Reference<Primitive>(object),
         this.index = new Reference<Primitive>(index),
         this.value = new Reference<Primitive>(value);
 
   bool get hasValue => false;
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitSetIndex(this);
 
   void setParentPointers() {
     object.parent = this;
     index.parent = this;
     value.parent = this;
   }
+
+  int get effectFlags => Effects.changesIndexableContent;
 }
 
 /// Reads the value of a static field or tears off a static method.
 ///
 /// If [GetStatic] is used to load a lazily initialized static field, it must
 /// have been initialized beforehand, and a [witness] must be set to restrict
 /// code motion.
 class GetStatic extends Primitive {
   /// Can be [FieldElement] or [FunctionElement].
   final Element element;
   final SourceInformation sourceInformation;
+  bool isFinal = false;
 
   /// If reading a lazily initialized field, [witness] must refer to a node
   /// that initializes the field or always occurs after the field initializer.
   ///
   /// The value of the witness is not used.
   Reference<Primitive> witness;
 
   GetStatic(this.element, [this.sourceInformation]);
 
   /// Read a lazily initialized static field that is known to have been
   /// initialized by [witness] or earlier.
   GetStatic.witnessed(this.element, Primitive witness, [this.sourceInformation])
       : witness = witness == null ? null : new Reference<Primitive>(witness);
 
   accept(Visitor visitor) => visitor.visitGetStatic(this);
 
   bool get hasValue => true;
   bool get isSafeForElimination => true;
-  bool get isSafeForReordering {
-    return element is FunctionElement || element.isFinal;
-  }
+  bool get isSafeForReordering => isFinal;
 
   void setParentPointers() {
     if (witness != null) {
       witness.parent = this;
     }
   }
+
+  int get effectFlags => isFinal ? 0 : Effects.dependsOnStaticField;
 }
 
 /// Sets the value of a static field.
 class SetStatic extends Primitive {
   final FieldElement element;
   final Reference<Primitive> value;
   final SourceInformation sourceInformation;
 
   SetStatic(this.element, Primitive value, [this.sourceInformation])
       : this.value = new Reference<Primitive>(value);
 
   accept(Visitor visitor) => visitor.visitSetStatic(this);
 
   bool get hasValue => false;
   bool get isSafeForElimination => false;
   bool get isSafeForReordering => false;
 
   void setParentPointers() {
     value.parent = this;
   }
+
+  int get effectFlags => Effects.changesStaticField;
 }
 
 /// Reads the value of a lazily initialized static field.
 ///
 /// If the field has not yet been initialized, its initializer is evaluated
 /// and assigned to the field.
 class GetLazyStatic extends UnsafePrimitive {
   final FieldElement element;
   final SourceInformation sourceInformation;
+  bool isFinal = false;
 
   GetLazyStatic(this.element, [this.sourceInformation]);
 
   accept(Visitor visitor) => visitor.visitGetLazyStatic(this);
 
   bool get hasValue => true;
 
   void setParentPointers() {}
+
+  // TODO(asgerf): Track side effects of lazy field initializers.
+  int get effectFlags => Effects.all;
 }
 
 /// Creates an object for holding boxed variables captured by a closure.
 class CreateBox extends Primitive {
   accept(Visitor visitor) => visitor.visitCreateBox(this);
 
   bool get hasValue => true;
   bool get isSafeForElimination => true;
   bool get isSafeForReordering => true;
 
@@ skipping 99 matching lines @@
 
 class ForeignCode extends UnsafePrimitive {
   final js.Template codeTemplate;
   final TypeMask storedType;
   final List<Reference<Primitive>> arguments;
   final native.NativeBehavior nativeBehavior;
   final FunctionElement dependency;
 
   ForeignCode(this.codeTemplate, this.storedType, List<Primitive> arguments,
       this.nativeBehavior, {this.dependency})
-      : this.arguments = _referenceList(arguments);
+      : this.arguments = _referenceList(arguments) {
+    effectFlags = Effects.from(nativeBehavior.sideEffects);
+  }
 
   accept(Visitor visitor) => visitor.visitForeignCode(this);
 
   bool get hasValue => true;
 
   void setParentPointers() {
     _setParentsOnList(arguments, this);
   }
 
   bool isNullGuardOnNullFirstArgument() {
@@ skipping 968 matching lines @@
       Variable originalVariable = original;
       copy.type = originalVariable.type;
       copy.hint = originalVariable.hint;
     }
     return _copies[original] = copy;
   }
 
   /// Get the copy of a [Reference]'s definition from the map.
   Definition getCopy(Reference reference) => _copies[reference.definition];
 
+  /// Get the copy of a [Reference]'s definition from the map.
+  Definition getCopyOrNull(Reference reference) => reference == null
+      ? null
+      : getCopy(reference);
+
   /// Map a list of [Reference]s to the list of their definition's copies.
   List<Definition> getList(List<Reference> list) => list.map(getCopy).toList();
 
   /// Copy a non-[Continuation] [Definition].
   Definition copy(Definition node) {
     assert (node is! Continuation);
     return putCopy(node, visit(node));
   }
 
   Definition visit(Node node) => node.accept(this);
@@ skipping 49 matching lines @@
   Definition visitSetStatic(SetStatic node) {
     return new SetStatic(node.element, getCopy(node.value),
         node.sourceInformation);
   }
 
   Definition visitSetField(SetField node) {
     return new SetField(getCopy(node.object), node.field, getCopy(node.value));
   }
 
   Definition visitGetLazyStatic(GetLazyStatic node) {
-    return new GetLazyStatic(node.element, node.sourceInformation);
+    return new GetLazyStatic(node.element, node.sourceInformation)
+        ..isFinal = node.isFinal;
   }
 
   Definition visitAwait(Await node) {
     return new Await(getCopy(node.input));
   }
 
   Definition visitYield(Yield node) {
     return new Yield(getCopy(node.input), node.hasStar);
   }
 
@@ skipping 12 matching lines @@
 
   Definition visitParameter(Parameter node) {
     return new Parameter(node.hint);
   }
 
   Definition visitMutableVariable(MutableVariable node) {
     return new MutableVariable(node.hint);
   }
 
   Definition visitGetStatic(GetStatic node) {
-    return new GetStatic(node.element, node.sourceInformation);
+    if (node.witness != null) {
+      return new GetStatic.witnessed(node.element,
+          getCopy(node.witness),
+          node.sourceInformation);
+    } else {
+      return new GetStatic(node.element, node.sourceInformation);
+    }
   }
 
   Definition visitInterceptor(Interceptor node) {
     return new Interceptor(getCopy(node.input), node.sourceInformation)
         ..interceptedClasses.addAll(node.interceptedClasses);
   }
 
   Definition visitCreateInstance(CreateInstance node) {
     return new CreateInstance(
         node.classElement,
         getList(node.arguments),
         node.typeInformation == null ? null : getCopy(node.typeInformation),
         node.sourceInformation);
   }
 
   Definition visitGetField(GetField node) {
-    return new GetField(getCopy(node.object), node.field);
+    return new GetField(getCopy(node.object), node.field)
+        ..isFinal = node.isFinal;
   }
 
   Definition visitCreateBox(CreateBox node) {
     return new CreateBox();
   }
 
   Definition visitReifyRuntimeType(ReifyRuntimeType node) {
     return new ReifyRuntimeType(getCopy(node.value), node.sourceInformation);
   }
 
@@ skipping 48 matching lines @@
   Definition visitRefinement(Refinement node) {
     return new Refinement(getCopy(node.value), node.refineType);
   }
 
   Definition visitBoundsCheck(BoundsCheck node) {
     if (node.hasNoChecks) {
       return new BoundsCheck.noCheck(getCopy(node.object),
           node.sourceInformation);
     } else {
       return new BoundsCheck(getCopy(node.object), getCopy(node.index),
-          node.length == null ? null : getCopy(node.length),
+          getCopyOrNull(node.length),
           node.checks,
           node.sourceInformation);
     }
   }
 
   Definition visitNullCheck(NullCheck node) {
     return new NullCheck(getCopy(node.value), node.sourceInformation,
-        condition: node.condition == null ? null : getCopy(node.condition),
+        condition: getCopyOrNull(node.condition),
         selector: node.selector,
         useSelector: node.useSelector);
   }
 
   Definition visitForeignCode(ForeignCode node) {
     return new ForeignCode(node.codeTemplate, node.storedType,
         getList(node.arguments),
         node.nativeBehavior,
         dependency: node.dependency);
   }
@@ skipping 132 matching lines @@
     plug(new Branch.loose(_definitions.getCopy(node.condition),
         _copies[node.trueContinuation.definition],
         _copies[node.falseContinuation.definition])
       ..isStrictCheck = node.isStrictCheck);
   }
 
   visitUnreachable(Unreachable node) {
     plug(new Unreachable());
   }
 }