| 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 part of ssa; | 5 part of ssa; |
| 6 | 6 |
| 7 abstract class OptimizationPhase { | 7 abstract class OptimizationPhase { |
| 8 String get name; | 8 String get name; |
| 9 void visitGraph(HGraph graph); | 9 void visitGraph(HGraph graph); |
| 10 } | 10 } |
| (...skipping 20 matching lines...) Expand all Loading... |
| 31 } | 31 } |
| 32 | 32 |
| 33 void optimize(CodegenWorkItem work, HGraph graph) { | 33 void optimize(CodegenWorkItem work, HGraph graph) { |
| 34 ConstantSystem constantSystem = compiler.backend.constantSystem; | 34 ConstantSystem constantSystem = compiler.backend.constantSystem; |
| 35 JavaScriptItemCompilationContext context = work.compilationContext; | 35 JavaScriptItemCompilationContext context = work.compilationContext; |
| 36 measure(() { | 36 measure(() { |
| 37 SsaDeadCodeEliminator dce; | 37 SsaDeadCodeEliminator dce; |
| 38 List<OptimizationPhase> phases = <OptimizationPhase>[ | 38 List<OptimizationPhase> phases = <OptimizationPhase>[ |
| 39 // Run trivial instruction simplification first to optimize | 39 // Run trivial instruction simplification first to optimize |
| 40 // some patterns useful for type conversion. | 40 // some patterns useful for type conversion. |
| 41 new SsaInstructionSimplifier(constantSystem, backend, work), | 41 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
| 42 new SsaTypeConversionInserter(compiler), | 42 new SsaTypeConversionInserter(compiler), |
| 43 new SsaRedundantPhiEliminator(), | 43 new SsaRedundantPhiEliminator(), |
| 44 new SsaDeadPhiEliminator(), | 44 new SsaDeadPhiEliminator(), |
| 45 new SsaTypePropagator(compiler), | 45 new SsaTypePropagator(compiler), |
| 46 // After type propagation, more instructions can be | 46 // After type propagation, more instructions can be |
| 47 // simplified. | 47 // simplified. |
| 48 new SsaInstructionSimplifier(constantSystem, backend, work), | 48 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
| 49 new SsaCheckInserter(backend, work, context.boundsChecked), | 49 new SsaCheckInserter(backend, work, context.boundsChecked), |
| 50 new SsaInstructionSimplifier(constantSystem, backend, work), | 50 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
| 51 new SsaCheckInserter(backend, work, context.boundsChecked), | 51 new SsaCheckInserter(backend, work, context.boundsChecked), |
| 52 new SsaTypePropagator(compiler), | 52 new SsaTypePropagator(compiler), |
| 53 // Run a dead code eliminator before LICM because dead | 53 // Run a dead code eliminator before LICM because dead |
| 54 // interceptors are often in the way of LICM'able instructions. | 54 // interceptors are often in the way of LICM'able instructions. |
| 55 new SsaDeadCodeEliminator(compiler), | 55 new SsaDeadCodeEliminator(compiler, this), |
| 56 new SsaGlobalValueNumberer(compiler), | 56 new SsaGlobalValueNumberer(compiler), |
| 57 // After GVN, some instructions might need their type to be | 57 // After GVN, some instructions might need their type to be |
| 58 // updated because they now have different inputs. | 58 // updated because they now have different inputs. |
| 59 new SsaTypePropagator(compiler), | 59 new SsaTypePropagator(compiler), |
| 60 new SsaCodeMotion(), | 60 new SsaCodeMotion(), |
| 61 new SsaLoadElimination(compiler), | 61 new SsaLoadElimination(compiler), |
| 62 new SsaDeadPhiEliminator(), | 62 new SsaDeadPhiEliminator(), |
| 63 new SsaTypePropagator(compiler), | 63 new SsaTypePropagator(compiler), |
| 64 new SsaValueRangeAnalyzer(compiler, constantSystem, work), | 64 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), |
| 65 // Previous optimizations may have generated new | 65 // Previous optimizations may have generated new |
| 66 // opportunities for instruction simplification. | 66 // opportunities for instruction simplification. |
| 67 new SsaInstructionSimplifier(constantSystem, backend, work), | 67 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
| 68 new SsaCheckInserter(backend, work, context.boundsChecked), | 68 new SsaCheckInserter(backend, work, context.boundsChecked), |
| 69 new SsaSimplifyInterceptors(compiler, constantSystem, work), | 69 new SsaSimplifyInterceptors(compiler, constantSystem, work), |
| 70 dce = new SsaDeadCodeEliminator(compiler), | 70 dce = new SsaDeadCodeEliminator(compiler, this), |
| 71 new SsaTypePropagator(compiler)]; | 71 new SsaTypePropagator(compiler)]; |
| 72 runPhases(graph, phases); | 72 runPhases(graph, phases); |
| 73 if (dce.eliminatedSideEffects) { | 73 if (dce.eliminatedSideEffects) { |
| 74 phases = <OptimizationPhase>[ | 74 phases = <OptimizationPhase>[ |
| 75 new SsaGlobalValueNumberer(compiler), | 75 new SsaGlobalValueNumberer(compiler), |
| 76 new SsaCodeMotion(), | 76 new SsaCodeMotion(), |
| 77 new SsaValueRangeAnalyzer(compiler, constantSystem, work), | 77 new SsaValueRangeAnalyzer(compiler, constantSystem, this, work), |
| 78 new SsaInstructionSimplifier(constantSystem, backend, work), | 78 new SsaInstructionSimplifier(constantSystem, backend, this, work), |
| 79 new SsaCheckInserter(backend, work, context.boundsChecked), | 79 new SsaCheckInserter(backend, work, context.boundsChecked), |
| 80 new SsaSimplifyInterceptors(compiler, constantSystem, work), | 80 new SsaSimplifyInterceptors(compiler, constantSystem, work), |
| 81 new SsaDeadCodeEliminator(compiler)]; | 81 new SsaDeadCodeEliminator(compiler, this)]; |
| 82 } else { | 82 } else { |
| 83 phases = <OptimizationPhase>[ | 83 phases = <OptimizationPhase>[ |
| 84 // Run the simplifier to remove unneeded type checks inserted | 84 // Run the simplifier to remove unneeded type checks inserted |
| 85 // by type propagation. | 85 // by type propagation. |
| 86 new SsaInstructionSimplifier(constantSystem, backend, work)]; | 86 new SsaInstructionSimplifier(constantSystem, backend, this, work)]; |
| 87 } | 87 } |
| 88 runPhases(graph, phases); | 88 runPhases(graph, phases); |
| 89 }); | 89 }); |
| 90 } | 90 } |
| 91 } | 91 } |
| 92 | 92 |
| 93 bool isFixedLength(mask, Compiler compiler) { | 93 bool isFixedLength(mask, Compiler compiler) { |
| 94 ClassWorld classWorld = compiler.world; | 94 ClassWorld classWorld = compiler.world; |
| 95 JavaScriptBackend backend = compiler.backend; | 95 JavaScriptBackend backend = compiler.backend; |
| 96 if (mask.isContainer && mask.length != null) { | 96 if (mask.isContainer && mask.length != null) { |
| (...skipping 18 matching lines...) Expand all Loading... |
| 115 // a single use. This protects against exponentially large constant folded | 115 // a single use. This protects against exponentially large constant folded |
| 116 // strings. | 116 // strings. |
| 117 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; | 117 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; |
| 118 | 118 |
| 119 final String name = "SsaInstructionSimplifier"; | 119 final String name = "SsaInstructionSimplifier"; |
| 120 final JavaScriptBackend backend; | 120 final JavaScriptBackend backend; |
| 121 final CodegenWorkItem work; | 121 final CodegenWorkItem work; |
| 122 final ConstantSystem constantSystem; | 122 final ConstantSystem constantSystem; |
| 123 HGraph graph; | 123 HGraph graph; |
| 124 Compiler get compiler => backend.compiler; | 124 Compiler get compiler => backend.compiler; |
| 125 final SsaOptimizerTask optimizer; |
| 125 | 126 |
| 126 SsaInstructionSimplifier(this.constantSystem, this.backend, this.work); | 127 SsaInstructionSimplifier(this.constantSystem, |
| 128 this.backend, |
| 129 this.optimizer, |
| 130 this.work); |
| 127 | 131 |
| 128 void visitGraph(HGraph visitee) { | 132 void visitGraph(HGraph visitee) { |
| 129 graph = visitee; | 133 graph = visitee; |
| 130 visitDominatorTree(visitee); | 134 visitDominatorTree(visitee); |
| 131 } | 135 } |
| 132 | 136 |
| 133 visitBasicBlock(HBasicBlock block) { | 137 visitBasicBlock(HBasicBlock block) { |
| 134 HInstruction instruction = block.first; | 138 HInstruction instruction = block.first; |
| 135 while (instruction != null) { | 139 while (instruction != null) { |
| 136 HInstruction next = instruction.next; | 140 HInstruction next = instruction.next; |
| (...skipping 819 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 956 if (boundsChecked.contains(node)) return; | 960 if (boundsChecked.contains(node)) return; |
| 957 insertBoundsCheck( | 961 insertBoundsCheck( |
| 958 node, node.receiver, graph.addConstantInt(0, backend.compiler)); | 962 node, node.receiver, graph.addConstantInt(0, backend.compiler)); |
| 959 } | 963 } |
| 960 } | 964 } |
| 961 | 965 |
| 962 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { | 966 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { |
| 963 final String name = "SsaDeadCodeEliminator"; | 967 final String name = "SsaDeadCodeEliminator"; |
| 964 | 968 |
| 965 final Compiler compiler; | 969 final Compiler compiler; |
| 970 final SsaOptimizerTask optimizer; |
| 966 SsaLiveBlockAnalyzer analyzer; | 971 SsaLiveBlockAnalyzer analyzer; |
| 967 bool eliminatedSideEffects = false; | 972 bool eliminatedSideEffects = false; |
| 968 SsaDeadCodeEliminator(this.compiler); | 973 SsaDeadCodeEliminator(this.compiler, this.optimizer); |
| 969 | 974 |
| 970 HInstruction zapInstructionCache; | 975 HInstruction zapInstructionCache; |
| 971 HInstruction get zapInstruction { | 976 HInstruction get zapInstruction { |
| 972 if (zapInstructionCache == null) { | 977 if (zapInstructionCache == null) { |
| 973 // A constant with no type does not pollute types at phi nodes. | 978 // A constant with no type does not pollute types at phi nodes. |
| 974 ConstantValue constant = | 979 ConstantValue constant = |
| 975 new DummyConstantValue(const TypeMask.nonNullEmpty()); | 980 new DummyConstantValue(const TypeMask.nonNullEmpty()); |
| 976 zapInstructionCache = analyzer.graph.addConstant(constant, compiler); | 981 zapInstructionCache = analyzer.graph.addConstant(constant, compiler); |
| 977 } | 982 } |
| 978 return zapInstructionCache; | 983 return zapInstructionCache; |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1011 && instruction.onlyThrowsNSM() | 1016 && instruction.onlyThrowsNSM() |
| 1012 && hasFollowingThrowingNSM(instruction)) { | 1017 && hasFollowingThrowingNSM(instruction)) { |
| 1013 return true; | 1018 return true; |
| 1014 } | 1019 } |
| 1015 return !instruction.canThrow() | 1020 return !instruction.canThrow() |
| 1016 && instruction is !HParameterValue | 1021 && instruction is !HParameterValue |
| 1017 && instruction is !HLocalSet; | 1022 && instruction is !HLocalSet; |
| 1018 } | 1023 } |
| 1019 | 1024 |
| 1020 void visitGraph(HGraph graph) { | 1025 void visitGraph(HGraph graph) { |
| 1021 analyzer = new SsaLiveBlockAnalyzer(graph, compiler); | 1026 analyzer = new SsaLiveBlockAnalyzer(graph, compiler, optimizer); |
| 1022 analyzer.analyze(); | 1027 analyzer.analyze(); |
| 1023 visitPostDominatorTree(graph); | 1028 visitPostDominatorTree(graph); |
| 1024 cleanPhis(graph); | 1029 cleanPhis(graph); |
| 1025 } | 1030 } |
| 1026 | 1031 |
| 1027 void visitBasicBlock(HBasicBlock block) { | 1032 void visitBasicBlock(HBasicBlock block) { |
| 1028 bool isDeadBlock = analyzer.isDeadBlock(block); | 1033 bool isDeadBlock = analyzer.isDeadBlock(block); |
| 1029 block.isLive = !isDeadBlock; | 1034 block.isLive = !isDeadBlock; |
| 1030 // Start from the last non-control flow instruction in the block. | 1035 // Start from the last non-control flow instruction in the block. |
| 1031 HInstruction instruction = block.last.previous; | 1036 HInstruction instruction = block.last.previous; |
| (...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1095 if (input == inputs[i]) { | 1100 if (input == inputs[i]) { |
| 1096 user.inputs[i] = zapInstruction; | 1101 user.inputs[i] = zapInstruction; |
| 1097 zapInstruction.usedBy.add(user); | 1102 zapInstruction.usedBy.add(user); |
| 1098 } | 1103 } |
| 1099 } | 1104 } |
| 1100 } | 1105 } |
| 1101 } | 1106 } |
| 1102 | 1107 |
| 1103 class SsaLiveBlockAnalyzer extends HBaseVisitor { | 1108 class SsaLiveBlockAnalyzer extends HBaseVisitor { |
| 1104 final HGraph graph; | 1109 final HGraph graph; |
| 1105 final Compiler compiler; | |
| 1106 final Set<HBasicBlock> live = new Set<HBasicBlock>(); | 1110 final Set<HBasicBlock> live = new Set<HBasicBlock>(); |
| 1107 final List<HBasicBlock> worklist = <HBasicBlock>[]; | 1111 final List<HBasicBlock> worklist = <HBasicBlock>[]; |
| 1112 final SsaOptimizerTask optimizer; |
| 1113 final Compiler compiler; |
| 1108 | 1114 |
| 1109 SsaLiveBlockAnalyzer(this.graph, this.compiler); | 1115 SsaLiveBlockAnalyzer(this.graph, this.compiler, this.optimizer); |
| 1110 | 1116 |
| 1111 JavaScriptBackend get backend => compiler.backend; | 1117 Map<HInstruction, Range> get ranges => optimizer.ranges; |
| 1112 Map<HInstruction, Range> get ranges => backend.optimizer.ranges; | |
| 1113 | 1118 |
| 1114 bool isDeadBlock(HBasicBlock block) => !live.contains(block); | 1119 bool isDeadBlock(HBasicBlock block) => !live.contains(block); |
| 1115 | 1120 |
| 1116 void analyze() { | 1121 void analyze() { |
| 1117 markBlockLive(graph.entry); | 1122 markBlockLive(graph.entry); |
| 1118 while (!worklist.isEmpty) { | 1123 while (!worklist.isEmpty) { |
| 1119 HBasicBlock live = worklist.removeLast(); | 1124 HBasicBlock live = worklist.removeLast(); |
| 1120 live.last.accept(this); | 1125 live.last.accept(this); |
| 1121 } | 1126 } |
| 1122 } | 1127 } |
| (...skipping 1019 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2142 | 2147 |
| 2143 keyedValues.forEach((receiver, values) { | 2148 keyedValues.forEach((receiver, values) { |
| 2144 result.keyedValues[receiver] = | 2149 result.keyedValues[receiver] = |
| 2145 new Map<HInstruction, HInstruction>.from(values); | 2150 new Map<HInstruction, HInstruction>.from(values); |
| 2146 }); | 2151 }); |
| 2147 | 2152 |
| 2148 result.nonEscapingReceivers.addAll(nonEscapingReceivers); | 2153 result.nonEscapingReceivers.addAll(nonEscapingReceivers); |
| 2149 return result; | 2154 return result; |
| 2150 } | 2155 } |
| 2151 } | 2156 } |
| OLD | NEW |