dart2js cps: Global value numbering and loop-invariant code motion.

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

-// Copyright (c) 2015, 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.cps_ir.share_final_fields;
-
-import 'optimizers.dart';
-import 'cps_ir_nodes.dart';
-import 'loop_hierarchy.dart';
-import '../elements/elements.dart';
-import '../js_backend/js_backend.dart' show JavaScriptBackend;
-import '../types/types.dart' show TypeMask;
-
-/// Removes redundant GetField operations.
-///
-/// The pass performs these optimizations for field loads:
-/// - share GetFields of final fields when one is in scope of the other.
-/// - pull GetField operations of final fields out of loops when safe (object is
-///   not null).
-///
-/// This pass only optimizes final fields and should be replaced with a full
-/// load elimination pass.
-class ShareFinalFields extends TrampolineRecursiveVisitor implements Pass {
-  String get passName => 'Share final fields';
-
-  /// The innermost loop containing a given primitive.
-  final Map<Primitive, Continuation> loopHeaderFor =
-      <Primitive, Continuation>{};
-
-  // field -> receiver -> GetField
-  Map<FieldElement, Map<Primitive, Primitive>> fieldValues =
-      <FieldElement, Map<Primitive, Primitive>>{};
-
-  /// Interceptors that have been hoisted out of a given loop.
-  final Map<Continuation, List<GetField>> loopHoistedGetters =
-      <Continuation, List<GetField>>{};
-
-  JavaScriptBackend backend;
-  LoopHierarchy loopHierarchy;
-  Continuation currentLoopHeader;
-
-  ShareFinalFields(this.backend);
-
-  void rewrite(FunctionDefinition node) {
-    loopHierarchy = new LoopHierarchy(node);
-    visit(node.body);
-  }
-
-  @override
-  Expression traverseContinuation(Continuation cont) {
-    Continuation oldLoopHeader = currentLoopHeader;
-    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
-    for (Parameter parameter in cont.parameters) {
-      loopHeaderFor[parameter] = currentLoopHeader;
-    }
-    if (cont.isRecursive) {
-      pushAction(() {
-        // After the loop body has been processed, all values hoisted to this
-        // loop fall out of scope and should be removed from the environment.
-        List<GetField> hoisted = loopHoistedGetters[cont];
-        if (hoisted != null) {
-          for (GetField primitive in hoisted) {
-            Primitive refinedReceiver = primitive.object.definition;
-            Primitive receiver = refinedReceiver.effectiveDefinition;
-            var map = fieldValues[primitive.field];
-            assert(map[receiver] == primitive);
-            map.remove(receiver);
-          }
-        }
-      });
-    }
-    pushAction(() {
-      currentLoopHeader = oldLoopHeader;
-    });
-    return cont.body;
-  }
-
-  Continuation getCurrentOuterLoop({Continuation scope}) {
-    Continuation inner = null, outer = currentLoopHeader;
-    while (outer != scope) {
-      inner = outer;
-      outer = loopHierarchy.getEnclosingLoop(outer);
-    }
-    return inner;
-  }
-
-  @override
-  Expression traverseLetPrim(LetPrim node) {
-    loopHeaderFor[node.primitive] = currentLoopHeader;
-    Expression next = node.body;
-    if (node.primitive is! GetField) {
-      return next;
-    }
-    GetField primitive = node.primitive;
-    FieldElement field = primitive.field;
-
-    if (!shouldShareField(field)) {
-      return next;
-    }
-
-    Primitive refinedReceiver = primitive.object.definition;
-    Primitive receiver = refinedReceiver.effectiveDefinition;
-
-    // Try to reuse an existing load for the same input.
-    var map = fieldValues.putIfAbsent(field, () => <Primitive,Primitive>{});
-    Primitive existing = map[receiver];
-    if (existing != null) {
-      primitive..replaceUsesWith(existing)..destroy();
-      node.remove();
-      return next;
-    }
-
-    map[receiver] = primitive;
-
-    if (primitive.objectIsNotNull) {
-      // Determine how far the GetField can be lifted. The outermost loop that
-      // contains the input binding should also contain the load.
-      // Don't move above a refinement guard since that might be unsafe.
-
-      // TODO(sra): We can move above a refinement guard provided the input is
-      // still in scope and safe (non-null). We will have to replace
-      // primitive.object with the most constrained refinement still in scope.
-      Continuation referencedLoop =
-          lowestCommonAncestor(loopHeaderFor[refinedReceiver],
-                               currentLoopHeader);
-      if (referencedLoop != currentLoopHeader) {
-        Continuation hoistTarget = getCurrentOuterLoop(scope: referencedLoop);
-        LetCont loopBinding = hoistTarget.parent;
-        node.remove();
-        node.insertAbove(loopBinding);
-        // Remove the hoisted operations from the environment after processing
-        // the loop.
-        loopHoistedGetters
-            .putIfAbsent(hoistTarget, () => <GetField>[])
-            .add(primitive);
-        return next;
-      }
-    }
-
-    pushAction(() {
-        var map = fieldValues[field];
-        assert(map[receiver] == primitive);
-        map.remove(receiver);
-      });
-    return next;
-  }
-
-  bool shouldShareField(FieldElement field) {
-    // TODO(24781): This query is incorrect for fields assigned only via
-    //
-    //     super.field = ...
-    //
-    // return backend.compiler.world.fieldNeverChanges(field);
-
-    // Native fields are getters with side effects (e.g. layout).
-    if (backend.isNative(field)) return false;
-    return field.isFinal || field.isConst;
-  }
-
-  /// Returns the the innermost loop that effectively encloses both
-  /// c1 and c2 (or `null` if there is no such loop).
-  Continuation lowestCommonAncestor(Continuation c1, Continuation c2) {
-    int d1 = getDepth(c1), d2 = getDepth(c2);
-    while (c1 != c2) {
-      if (d1 <= d2) {
-        c2 = loopHierarchy.getEnclosingLoop(c2);
-        d2 = getDepth(c2);
-      } else {
-        c1 = loopHierarchy.getEnclosingLoop(c1);
-        d1 = getDepth(c1);
-      }
-    }
-    return c1;
-  }
-
-  int getDepth(Continuation loop) {
-    if (loop == null) return -1;
-    return loopHierarchy.loopDepth[loop];
-  }
-}