| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 import '../common/codegen.dart' show CodegenWorkItem; | 5 import '../common/codegen.dart' show CodegenWorkItem; |
| 6 import '../common/tasks.dart' show CompilerTask; | 6 import '../common/tasks.dart' show CompilerTask; |
| 7 import '../compiler.dart' show Compiler; | 7 import '../compiler.dart' show Compiler; |
| 8 import '../constants/constant_system.dart'; | 8 import '../constants/constant_system.dart'; |
| 9 import '../constants/values.dart'; | 9 import '../constants/values.dart'; |
| 10 import '../core_types.dart' show CoreClasses; | 10 import '../core_types.dart' show CoreClasses; |
| 11 import '../dart_types.dart'; | 11 import '../dart_types.dart'; |
| 12 import '../elements/elements.dart'; | 12 import '../elements/elements.dart'; |
| 13 import '../js/js.dart' as js; | 13 import '../js/js.dart' as js; |
| 14 import '../js_backend/backend_helpers.dart' show BackendHelpers; | 14 import '../js_backend/backend_helpers.dart' show BackendHelpers; |
| 15 import '../js_backend/js_backend.dart'; | 15 import '../js_backend/js_backend.dart'; |
| 16 import '../native/native.dart' as native; | 16 import '../native/native.dart' as native; |
| 17 import '../tree/dartstring.dart' as ast; | 17 import '../tree/dartstring.dart' as ast; |
| 18 import '../types/types.dart'; | 18 import '../types/types.dart'; |
| 19 import '../universe/selector.dart' show Selector; | 19 import '../universe/selector.dart' show Selector; |
| 20 import '../universe/side_effects.dart' show SideEffects; | 20 import '../universe/side_effects.dart' show SideEffects; |
| 21 import '../util/util.dart'; | 21 import '../util/util.dart'; |
| 22 import '../world.dart' show ClassWorld, World; | 22 import '../world.dart' show ClassWorld, World; |
| 23 import 'context.dart'; |
| 23 import 'interceptor_simplifier.dart'; | 24 import 'interceptor_simplifier.dart'; |
| 24 import 'nodes.dart'; | 25 import 'nodes.dart'; |
| 25 import 'types.dart'; | 26 import 'types.dart'; |
| 26 import 'types_propagation.dart'; | 27 import 'types_propagation.dart'; |
| 27 import 'value_range_analyzer.dart'; | 28 import 'value_range_analyzer.dart'; |
| 28 import 'value_set.dart'; | 29 import 'value_set.dart'; |
| 29 | 30 |
| 30 abstract class OptimizationPhase { | 31 abstract class OptimizationPhase { |
| 31 String get name; | 32 String get name; |
| 32 void visitGraph(HGraph graph); | 33 void visitGraph(HGraph graph); |
| 33 } | 34 } |
| 34 | 35 |
| 35 class SsaOptimizerTask extends CompilerTask { | 36 class SsaOptimizerTask extends CompilerTask { |
| 36 final JavaScriptBackend backend; | 37 final JavaScriptBackend backend; |
| 37 SsaOptimizerTask(JavaScriptBackend backend) | 38 SsaOptimizerTask(JavaScriptBackend backend) |
| 38 : this.backend = backend, | 39 : this.backend = backend, |
| 39 super(backend.compiler.measurer); | 40 super(backend.compiler.measurer); |
| 40 String get name => 'SSA optimizer'; | 41 String get name => 'SSA optimizer'; |
| 41 Compiler get compiler => backend.compiler; | 42 Compiler get compiler => backend.compiler; |
| 42 Map<HInstruction, Range> ranges = <HInstruction, Range>{}; | 43 Map<HInstruction, Range> ranges = <HInstruction, Range>{}; |
| 43 | 44 |
| 44 void optimize(CodegenWorkItem work, HGraph graph) { | 45 void optimize(HGraph graph, CodegenWorkItem work, |
| 46 SsaCompilationContext context) { |
| 45 void runPhase(OptimizationPhase phase) { | 47 void runPhase(OptimizationPhase phase) { |
| 46 measureSubtask(phase.name, () => phase.visitGraph(graph)); | 48 measureSubtask(phase.name, () => phase.visitGraph(graph)); |
| 47 compiler.tracer.traceGraph(phase.name, graph); | 49 compiler.tracer.traceGraph(phase.name, graph); |
| 48 assert(graph.isValid()); | 50 assert(graph.isValid()); |
| 49 } | 51 } |
| 50 | 52 |
| 51 ConstantSystem constantSystem = compiler.backend.constantSystem; | 53 ConstantSystem constantSystem = compiler.backend.constantSystem; |
| 52 JavaScriptItemCompilationContext context = work.compilationContext; | |
| 53 bool trustPrimitives = compiler.options.trustPrimitives; | 54 bool trustPrimitives = compiler.options.trustPrimitives; |
| 54 measure(() { | 55 measure(() { |
| 55 List<OptimizationPhase> phases = <OptimizationPhase>[ | 56 List<OptimizationPhase> phases = <OptimizationPhase>[ |
| 56 // Run trivial instruction simplification first to optimize | 57 // Run trivial instruction simplification first to optimize |
| 57 // some patterns useful for type conversion. | 58 // some patterns useful for type conversion. |
| 58 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 59 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 59 new SsaTypeConversionInserter(compiler), | 60 new SsaTypeConversionInserter(compiler), |
| 60 new SsaRedundantPhiEliminator(), | 61 new SsaRedundantPhiEliminator(), |
| 61 new SsaDeadPhiEliminator(), | 62 new SsaDeadPhiEliminator(), |
| 62 new SsaTypePropagator(compiler), | 63 new SsaTypePropagator(compiler), |
| 63 // After type propagation, more instructions can be | 64 // After type propagation, more instructions can be |
| 64 // simplified. | 65 // simplified. |
| 65 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 66 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 66 new SsaCheckInserter( | 67 new SsaCheckInserter( |
| 67 trustPrimitives, backend, work, context.boundsChecked), | 68 trustPrimitives, backend, context.boundsChecked), |
| 68 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 69 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 69 new SsaCheckInserter( | 70 new SsaCheckInserter( |
| 70 trustPrimitives, backend, work, context.boundsChecked), | 71 trustPrimitives, backend, context.boundsChecked), |
| 71 new SsaTypePropagator(compiler), | 72 new SsaTypePropagator(compiler), |
| 72 // Run a dead code eliminator before LICM because dead | 73 // Run a dead code eliminator before LICM because dead |
| 73 // interceptors are often in the way of LICM'able instructions. | 74 // interceptors are often in the way of LICM'able instructions. |
| 74 new SsaDeadCodeEliminator(compiler, this), | 75 new SsaDeadCodeEliminator(compiler, this), |
| 75 new SsaGlobalValueNumberer(compiler), | 76 new SsaGlobalValueNumberer(compiler), |
| 76 // After GVN, some instructions might need their type to be | 77 // After GVN, some instructions might need their type to be |
| 77 // updated because they now have different inputs. | 78 // updated because they now have different inputs. |
| 78 new SsaTypePropagator(compiler), | 79 new SsaTypePropagator(compiler), |
| 79 new SsaCodeMotion(), | 80 new SsaCodeMotion(), |
| 80 new SsaLoadElimination(compiler), | 81 new SsaLoadElimination(compiler), |
| 81 new SsaRedundantPhiEliminator(), | 82 new SsaRedundantPhiEliminator(), |
| 82 new SsaDeadPhiEliminator(), | 83 new SsaDeadPhiEliminator(), |
| 83 new SsaTypePropagator(compiler), | 84 new SsaTypePropagator(compiler), |
| 84 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), | 85 new SsaValueRangeAnalyzer(compiler, constantSystem, this), |
| 85 // Previous optimizations may have generated new | 86 // Previous optimizations may have generated new |
| 86 // opportunities for instruction simplification. | 87 // opportunities for instruction simplification. |
| 87 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 88 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 88 new SsaCheckInserter( | 89 new SsaCheckInserter( |
| 89 trustPrimitives, backend, work, context.boundsChecked), | 90 trustPrimitives, backend, context.boundsChecked), |
| 90 ]; | 91 ]; |
| 91 phases.forEach(runPhase); | 92 phases.forEach(runPhase); |
| 92 | 93 |
| 93 // Simplifying interceptors is not strictly just an optimization, it is | 94 // Simplifying interceptors is not strictly just an optimization, it is |
| 94 // required for implementation correctness because the code generator | 95 // required for implementation correctness because the code generator |
| 95 // assumes it is always performed. | 96 // assumes it is always performed. |
| 96 runPhase(new SsaSimplifyInterceptors(compiler, constantSystem, work)); | 97 runPhase(new SsaSimplifyInterceptors( |
| 98 compiler, constantSystem, work.element)); |
| 97 | 99 |
| 98 SsaDeadCodeEliminator dce = new SsaDeadCodeEliminator(compiler, this); | 100 SsaDeadCodeEliminator dce = new SsaDeadCodeEliminator(compiler, this); |
| 99 runPhase(dce); | 101 runPhase(dce); |
| 100 if (dce.eliminatedSideEffects) { | 102 if (dce.eliminatedSideEffects) { |
| 101 phases = <OptimizationPhase>[ | 103 phases = <OptimizationPhase>[ |
| 102 new SsaTypePropagator(compiler), | 104 new SsaTypePropagator(compiler), |
| 103 new SsaGlobalValueNumberer(compiler), | 105 new SsaGlobalValueNumberer(compiler), |
| 104 new SsaCodeMotion(), | 106 new SsaCodeMotion(), |
| 105 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), | 107 new SsaValueRangeAnalyzer(compiler, constantSystem, this), |
| 106 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 108 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 107 new SsaCheckInserter( | 109 new SsaCheckInserter( |
| 108 trustPrimitives, backend, work, context.boundsChecked), | 110 trustPrimitives, backend, context.boundsChecked), |
| 109 new SsaSimplifyInterceptors(compiler, constantSystem, work), | 111 new SsaSimplifyInterceptors(compiler, constantSystem, work.element), |
| 110 new SsaDeadCodeEliminator(compiler, this), | 112 new SsaDeadCodeEliminator(compiler, this), |
| 111 ]; | 113 ]; |
| 112 } else { | 114 } else { |
| 113 phases = <OptimizationPhase>[ | 115 phases = <OptimizationPhase>[ |
| 114 new SsaTypePropagator(compiler), | 116 new SsaTypePropagator(compiler), |
| 115 // Run the simplifier to remove unneeded type checks inserted by | 117 // Run the simplifier to remove unneeded type checks inserted by |
| 116 // type propagation. | 118 // type propagation. |
| 117 new SsaInstructionSimplifier(constantSystem, backend, this, work), | 119 new SsaInstructionSimplifier(constantSystem, backend, this, context), |
| 118 ]; | 120 ]; |
| 119 } | 121 } |
| 120 phases.forEach(runPhase); | 122 phases.forEach(runPhase); |
| 121 }); | 123 }); |
| 122 } | 124 } |
| 123 } | 125 } |
| 124 | 126 |
| 125 /// Returns `true` if [mask] represents only types that have a length that | 127 /// Returns `true` if [mask] represents only types that have a length that |
| 126 /// cannot change. The current implementation is conservative for the purpose | 128 /// cannot change. The current implementation is conservative for the purpose |
| 127 /// of identifying gvn-able lengths and mis-identifies some unions of fixed | 129 /// of identifying gvn-able lengths and mis-identifies some unions of fixed |
| (...skipping 21 matching lines...) Expand all Loading... |
| 149 */ | 151 */ |
| 150 class SsaInstructionSimplifier extends HBaseVisitor | 152 class SsaInstructionSimplifier extends HBaseVisitor |
| 151 implements OptimizationPhase { | 153 implements OptimizationPhase { |
| 152 // We don't produce constant-folded strings longer than this unless they have | 154 // We don't produce constant-folded strings longer than this unless they have |
| 153 // a single use. This protects against exponentially large constant folded | 155 // a single use. This protects against exponentially large constant folded |
| 154 // strings. | 156 // strings. |
| 155 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; | 157 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; |
| 156 | 158 |
| 157 final String name = "SsaInstructionSimplifier"; | 159 final String name = "SsaInstructionSimplifier"; |
| 158 final JavaScriptBackend backend; | 160 final JavaScriptBackend backend; |
| 159 final CodegenWorkItem work; | |
| 160 final ConstantSystem constantSystem; | 161 final ConstantSystem constantSystem; |
| 161 HGraph graph; | 162 HGraph graph; |
| 162 Compiler get compiler => backend.compiler; | 163 Compiler get compiler => backend.compiler; |
| 163 final SsaOptimizerTask optimizer; | 164 final SsaOptimizerTask optimizer; |
| 165 final SsaCompilationContext context; |
| 164 | 166 |
| 165 SsaInstructionSimplifier( | 167 SsaInstructionSimplifier( |
| 166 this.constantSystem, this.backend, this.optimizer, this.work); | 168 this.constantSystem, this.backend, this.optimizer, this.context); |
| 167 | 169 |
| 168 CoreClasses get coreClasses => compiler.coreClasses; | 170 CoreClasses get coreClasses => compiler.coreClasses; |
| 169 | 171 |
| 170 BackendHelpers get helpers => backend.helpers; | 172 BackendHelpers get helpers => backend.helpers; |
| 171 | 173 |
| 172 void visitGraph(HGraph visitee) { | 174 void visitGraph(HGraph visitee) { |
| 173 graph = visitee; | 175 graph = visitee; |
| 174 visitDominatorTree(visitee); | 176 visitDominatorTree(visitee); |
| 175 } | 177 } |
| 176 | 178 |
| (...skipping 651 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 828 VariableElement findConcreteFieldForDynamicAccess( | 830 VariableElement findConcreteFieldForDynamicAccess( |
| 829 HInstruction receiver, Selector selector) { | 831 HInstruction receiver, Selector selector) { |
| 830 TypeMask receiverType = receiver.instructionType; | 832 TypeMask receiverType = receiver.instructionType; |
| 831 return compiler.world.locateSingleField(selector, receiverType); | 833 return compiler.world.locateSingleField(selector, receiverType); |
| 832 } | 834 } |
| 833 | 835 |
| 834 HInstruction visitFieldGet(HFieldGet node) { | 836 HInstruction visitFieldGet(HFieldGet node) { |
| 835 if (node.isNullCheck) return node; | 837 if (node.isNullCheck) return node; |
| 836 var receiver = node.receiver; | 838 var receiver = node.receiver; |
| 837 if (node.element == helpers.jsIndexableLength) { | 839 if (node.element == helpers.jsIndexableLength) { |
| 838 JavaScriptItemCompilationContext context = work.compilationContext; | |
| 839 if (context.allocatedFixedLists.contains(receiver)) { | 840 if (context.allocatedFixedLists.contains(receiver)) { |
| 840 // TODO(ngeoffray): checking if the second input is an integer | 841 // TODO(ngeoffray): checking if the second input is an integer |
| 841 // should not be necessary but it currently makes it easier for | 842 // should not be necessary but it currently makes it easier for |
| 842 // other optimizations to reason about a fixed length constructor | 843 // other optimizations to reason about a fixed length constructor |
| 843 // that we know takes an int. | 844 // that we know takes an int. |
| 844 if (receiver.inputs[0].isInteger(compiler)) { | 845 if (receiver.inputs[0].isInteger(compiler)) { |
| 845 return receiver.inputs[0]; | 846 return receiver.inputs[0]; |
| 846 } | 847 } |
| 847 } else if (receiver.isConstantList() || receiver.isConstantString()) { | 848 } else if (receiver.isConstantList() || receiver.isConstantString()) { |
| 848 return graph.addConstantInt(receiver.constant.length, compiler); | 849 return graph.addConstantInt(receiver.constant.length, compiler); |
| (...skipping 345 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1194 // If there are type arguments, all type arguments are 'dynamic'. | 1195 // If there are type arguments, all type arguments are 'dynamic'. |
| 1195 (int i) => graph.addConstantNull(compiler)); | 1196 (int i) => graph.addConstantNull(compiler)); |
| 1196 } | 1197 } |
| 1197 | 1198 |
| 1198 return node; | 1199 return node; |
| 1199 } | 1200 } |
| 1200 } | 1201 } |
| 1201 | 1202 |
| 1202 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { | 1203 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { |
| 1203 final Set<HInstruction> boundsChecked; | 1204 final Set<HInstruction> boundsChecked; |
| 1204 final CodegenWorkItem work; | |
| 1205 final bool trustPrimitives; | 1205 final bool trustPrimitives; |
| 1206 final JavaScriptBackend backend; | 1206 final JavaScriptBackend backend; |
| 1207 final String name = "SsaCheckInserter"; | 1207 final String name = "SsaCheckInserter"; |
| 1208 HGraph graph; | 1208 HGraph graph; |
| 1209 | 1209 |
| 1210 SsaCheckInserter( | 1210 SsaCheckInserter( |
| 1211 this.trustPrimitives, this.backend, this.work, this.boundsChecked); | 1211 this.trustPrimitives, this.backend, this.boundsChecked); |
| 1212 | 1212 |
| 1213 BackendHelpers get helpers => backend.helpers; | 1213 BackendHelpers get helpers => backend.helpers; |
| 1214 | 1214 |
| 1215 void visitGraph(HGraph graph) { | 1215 void visitGraph(HGraph graph) { |
| 1216 this.graph = graph; | 1216 this.graph = graph; |
| 1217 | 1217 |
| 1218 // In --trust-primitives mode we don't add bounds checks. This is better | 1218 // In --trust-primitives mode we don't add bounds checks. This is better |
| 1219 // than trying to remove them later as the limit expression would become | 1219 // than trying to remove them later as the limit expression would become |
| 1220 // dead and require DCE. | 1220 // dead and require DCE. |
| 1221 if (trustPrimitives) return; | 1221 if (trustPrimitives) return; |
| (...skipping 1366 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2588 | 2588 |
| 2589 keyedValues.forEach((receiver, values) { | 2589 keyedValues.forEach((receiver, values) { |
| 2590 result.keyedValues[receiver] = | 2590 result.keyedValues[receiver] = |
| 2591 new Map<HInstruction, HInstruction>.from(values); | 2591 new Map<HInstruction, HInstruction>.from(values); |
| 2592 }); | 2592 }); |
| 2593 | 2593 |
| 2594 result.nonEscapingReceivers.addAll(nonEscapingReceivers); | 2594 result.nonEscapingReceivers.addAll(nonEscapingReceivers); |
| 2595 return result; | 2595 return result; |
| 2596 } | 2596 } |
| 2597 } | 2597 } |
| OLD | NEW |