Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(619)

Unified Diff: pkg/compiler/lib/src/cps_ir/share_final_fields.dart

Issue 1415923012: Simple sharing and hoisting of final field loads (Closed) Base URL: https://github.com/dart-lang/sdk.git@master
Patch Set: Created 5 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « pkg/compiler/lib/src/cps_ir/optimizers.dart ('k') | pkg/compiler/lib/src/js_backend/codegen/task.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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];
+ }
+}
« no previous file with comments | « pkg/compiler/lib/src/cps_ir/optimizers.dart ('k') | pkg/compiler/lib/src/js_backend/codegen/task.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698