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);
 
+  /// Returns a bitmask with the non-local side effects and dependencies of
+  /// this primitive, as defined by [Effects].
+  int get effects => Effects.none;
+
   /// 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 effects = 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 774 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 effects => 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 effects => 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;
 
+  /// True if the field never changes value.
+  final bool isFinal;
+
   /// 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)
+  GetField(Primitive object, this.field, {this.isFinal: false})
       : 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 effects => isFinal ? 0 : Effects.dependsOnInstanceField;

[sra1, 2016/02/29 23:40:33]

isFinal ? Effects.none : Effects.dependsOnInstanceField

 }
 
 /// Get the length of a string or native list.
 class GetLength extends Primitive {
   final Reference<Primitive> object;
 
+  /// True if the length of the given object can never change.
+  bool isFinal;
+
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
-  GetLength(Primitive object) : this.object = new Reference<Primitive>(object);
+  GetLength(Primitive object, {this.isFinal: false})
+      : 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 effects => 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 effects => 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 effects => 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;
 
+  /// True if the field never changes value.
+  final bool isFinal;
+
   /// 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]);
+  GetStatic(this.element, {this.isFinal: false, 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);
+  GetStatic.witnessed(this.element, Primitive witness, {this.sourceInformation})
+      : witness = witness == null ? null : new Reference<Primitive>(witness),
+        isFinal = false;
 
   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 effects => 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 effects => 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;
 
-  GetLazyStatic(this.element, [this.sourceInformation]);
+  /// True if the field never changes value.
+  final bool isFinal;
+
+  GetLazyStatic(this.element, {this.isFinal: false, 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 effects => 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) {
+    effects = Effects.from(nativeBehavior.sideEffects);
+  }
 
   accept(Visitor visitor) => visitor.visitForeignCode(this);
 
   bool get hasValue => true;
 
   void setParentPointers() {
     _setParentsOnList(arguments, this);
   }
 
   bool isNullGuardOnNullFirstArgument() {
@@ skipping 980 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,
+        isFinal: node.isFinal,
+        sourceInformation: node.sourceInformation);
   }
 
   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),
+          sourceInformation: node.sourceInformation);
+    } else {
+      return new GetStatic(node.element,
+          isFinal: node.isFinal,
+          sourceInformation: 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 26 matching lines @@
   }
 
   Definition visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
     return new ApplyBuiltinMethod(node.method, getCopy(node.receiver),
         getList(node.arguments),
         node.sourceInformation,
         receiverIsNotNull: node.receiverIsNotNull);
   }
 
   Definition visitGetLength(GetLength node) {
-    return new GetLength(getCopy(node.object));
+    return new GetLength(getCopy(node.object), isFinal: node.isFinal);
   }
 
   Definition visitGetIndex(GetIndex node) {
     return new GetIndex(getCopy(node.object), getCopy(node.index));
   }
 
   Definition visitSetIndex(SetIndex node) {
     return new SetIndex(getCopy(node.object), getCopy(node.index),
         getCopy(node.value));
   }
 
   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 visitReceiverCheck(ReceiverCheck node) {
     return new ReceiverCheck(getCopy(node.value),
         node.selector,
         node.sourceInformation,
-        condition: node.condition == null ? null : getCopy(node.condition),
+        condition: getCopyOrNull(node.condition),
         useSelector: node.useSelector,
         isNullCheck: node.isNullCheck);
   }
 
   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());
   }
 }