| // 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. |
| |
| // @dart = 2.10 |
| |
| import '../elements/entities.dart'; |
| import '../inferrer/abstract_value_domain.dart'; |
| import '../js_backend/field_analysis.dart' show JFieldAnalysis; |
| import '../world.dart' show JClosedWorld; |
| import 'logging.dart'; |
| import 'nodes.dart'; |
| import 'optimize.dart' show OptimizationPhase; |
| |
| /// Optimization phase that tries to eliminate late field checks and memory |
| /// loads. |
| class SsaLateFieldOptimizer extends HBaseVisitor implements OptimizationPhase { |
| @override |
| final String name = "SsaLateFieldOptimizer"; |
| |
| final JClosedWorld _closedWorld; |
| final OptimizationTestLog /*?*/ _log; |
| |
| final AbstractValueDomain _abstractValueDomain; |
| final JFieldAnalysis _fieldAnalysis; |
| |
| SsaLateFieldOptimizer(this._closedWorld, this._log) |
| : _abstractValueDomain = _closedWorld.abstractValueDomain, |
| _fieldAnalysis = _closedWorld.fieldAnalysis; |
| |
| @override |
| void visitGraph(HGraph graph) { |
| _log?.instructionHistogram('$name.pre', graph, _summarizeInstruction); |
| |
| visitDominatorTree(graph); |
| |
| _log?.instructionHistogram('$name.post', graph, _summarizeInstruction); |
| } |
| |
| static String /*?*/ _summarizeInstruction(HInstruction node) { |
| if (node is HLateCheck) return '${node.runtimeType}'; |
| if (node is HFieldGet) return '${node.runtimeType}'; |
| return null; |
| } |
| |
| @override |
| bool validPostcondition(HGraph graph) => true; |
| |
| @override |
| void visitBasicBlock(HBasicBlock block) { |
| HInstruction instruction = block.first; |
| while (instruction != null) { |
| HInstruction next = instruction.next; |
| instruction.accept(this); |
| instruction = next; |
| } |
| } |
| |
| @override |
| void visitLateReadCheck(HLateReadCheck node) { |
| // The getter for a `late` instance field has a check on the backing field |
| // to ensure that the sentinel value has been overwritten by an initializing |
| // assignment. When the getter is inlined, there is a sequence of loads, |
| // each with a check. `h(g(a.f), g(a.f))` looks like the following, where |
| // `#f` is the backing field for late field `f`. |
| // |
| // t1 = HFieldGet(a, #f) {T,sentinel} |
| // t2 = HLateReadCheck(t1) {T} |
| // t9 = g(t2) |
| // t11 = HFieldGet(a, #f) {T,sentinel} |
| // t12 = HLateReadCheck(t11) {T} |
| // t19 = g(t12) |
| // t99 = h(t9, t19) |
| // |
| // The field starts initialized with a sentinel value. HLateReadCheck will |
| // throw if the value is a sentinel. The backing field is never assigned a |
| // sentinel, so subsequent read checks will always succeed and can be |
| // removed. |
| // |
| // ## `late` fields |
| // |
| // The removal is effected by marking the subsequent loaded values with a |
| // strengthened type that excludes the sentinel, using HTypeKnown. This |
| // makes the sentinel check redundant so it can be removed when it is |
| // visited later in the pass. |
| // |
| // To prevent _uses_ of the loaded values from being moved to before the |
| // check, HTypeKnown is witnessed by (has a dependency on) the original |
| // check. We know the value is not a sentinel only _after_ the check. |
| // (Optimizations preserve the order of loads and stores. It is fine for the |
| // second load to move before the first check provided doing so does not |
| // change the value seen by the second load.) |
| // |
| // After inserting the HTypeKnown.witnessed instruction after each |
| // subsequent load we have: |
| // |
| // t1 = HFieldGet(a, #f) {T,sentinel} |
| // t2 = HLateReadCheck(t1) {T} |
| // t9 = g(t2) |
| // t11 = HFieldGet(a, #f) {T,sentinel} |
| // t12 = HTypeKnown(t11, t2) {T} |
| // t13 = HLateReadCheck(t12) {T} |
| // t19 = g(t13) |
| // t99 = h(t9, t19) |
| // |
| // The subsequent checks are now redundant, and are visited after the |
| // initial check, so they are cleaned up when visited. |
| // |
| // t1 = HFieldGet(a, #f) {T,sentinel} |
| // t2 = HLateReadCheck(t1) {T} |
| // t9 = g(t2) |
| // t11 = HFieldGet(a, #f) {T,sentinel} |
| // t12 = HTypeKnown(t11, t2) {T} |
| // t19 = g(t12) |
| // t99 = h(t9, t19) |
| // |
| // ## `late final` fields |
| // |
| // `late final` fields change value only once from sentinel to final value. |
| // If the read-check passes, the value is the final value, so the subsequent |
| // reads can be replaced by the checked value: |
| // |
| // t1 = HFieldGet(a, #f) {T,sentinel} |
| // t2 = HLateReadCheck(t1) {T} |
| // t9 = g(t2) |
| // t12 = HLateReadCheck(t2) {T} |
| // t19 = g(t12) |
| // t99 = h(t9, t19) |
| // |
| // This leads to back-to-back HLateReadCheck instructions, the second of |
| // which is redundant and is removed: |
| // |
| // t1 = HFieldGet(a, #f) {T,sentinel} |
| // t2 = HLateReadCheck(t1) {T} |
| // t9 = g(t2) |
| // t19 = g(t2) |
| // t99 = h(t9, t19) |
| |
| HInstruction input = node.checkedInput; |
| |
| // Cleanup. Remove redundant checks. |
| if (input is HLateReadCheck || node.isRedundant(_closedWorld)) { |
| node.block.rewrite(node, input); |
| node.block.remove(node); |
| return; |
| } |
| |
| if (input is HFieldGet) { |
| HInstruction receiver = input.receiver; |
| FieldEntity field = input.element; |
| |
| final uses = DominatedUses.of(receiver, node); |
| |
| List<HFieldGet> loads = []; |
| for (HInstruction use in uses.instructions) { |
| if (use is HFieldGet && use.element == field) { |
| loads.add(use); |
| } |
| } |
| |
| if (loads.isEmpty) return; |
| |
| if (_fieldAnalysis.getFieldData(field).isAssignedOnce) { |
| // `late final` backing fields are assigned at most once, so loads can |
| // be replaced with the dominating checked load value. |
| for (final load in loads) { |
| load.block.rewrite(load, node); |
| load.block.remove(load); |
| } |
| } else { |
| for (final load in loads) { |
| final known = HTypeKnown.witnessed(node.instructionType, load, node) |
| ..sourceInformation = node.sourceInformation; |
| load.block.rewrite(load, known); |
| load.block.addAfter(load, known); |
| } |
| } |
| } |
| } |
| |
| @override |
| void visitFieldSet(HFieldSet node) { |
| FieldEntity field = node.element; |
| final fieldData = _fieldAnalysis.getFieldData(field); |
| if (!fieldData.isLateBackingField) return; |
| |
| // [node] is a store to the backing field for a late instance field. The |
| // stored value cannot be the sentinel value, so future loads of the field |
| // will never be the sentinel value and do not need to be checked. |
| final uses = DominatedUses.of(node.receiver, node, excludeDominator: true); |
| |
| List<HFieldGet> loads = []; |
| for (HInstruction use in uses.instructions) { |
| if (use is HFieldGet && use.element == field) { |
| loads.add(use); |
| } |
| } |
| |
| if (loads.isEmpty) return; |
| |
| if (fieldData.isAssignedOnce) { |
| // [field] is a `late final` field so the stored value is the value of |
| // every subsequent load. Replace loads with the stored value. |
| for (final load in loads) { |
| load.block.rewrite(load, node.value); |
| load.block.remove(load); |
| } |
| } else { |
| // The subsequent loaded value cannot be the sentinel value. Refine the |
| // type of the load which will allow any check on the load to be removed. |
| // There is no need for HTypeKnown.witnessed since it would be an invalid |
| // transformation to move the read before the write. |
| for (final load in loads) { |
| load.instructionType = |
| _abstractValueDomain.excludeLateSentinel(load.instructionType); |
| } |
| } |
| } |
| } |