Index: pkg/compiler/lib/src/cps_ir/share_final_fields.dart |
diff --git a/pkg/compiler/lib/src/cps_ir/share_final_fields.dart b/pkg/compiler/lib/src/cps_ir/share_final_fields.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..efcc413f29dc18f135d6c8fc6d693092232410f9 |
--- /dev/null |
+++ b/pkg/compiler/lib/src/cps_ir/share_final_fields.dart |
@@ -0,0 +1,173 @@ |
+// 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) { |
+ existing.substituteFor(primitive); |
+ primitive.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) { |
+ return backend.compiler.world.fieldNeverChanges(field); |
+ } |
+ |
+ /// 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]; |
+ } |
+} |