| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase { | 5 class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase { |
| 6 | 6 |
| 7 final Map<int, HInstruction> workmap; | 7 final Map<int, HInstruction> workmap; |
| 8 final List<int> worklist; | 8 final List<int> worklist; |
| 9 final Compiler compiler; | 9 final Compiler compiler; |
| 10 String get name() => 'type propagator'; | 10 String get name() => 'type propagator'; |
| 11 | 11 |
| 12 SsaTypePropagator(Compiler this.compiler) | 12 SsaTypePropagator(Compiler this.compiler) |
| 13 : workmap = new Map<int, HInstruction>(), | 13 : workmap = new Map<int, HInstruction>(), |
| 14 worklist = new List<int>(); | 14 worklist = new List<int>(); |
| 15 | 15 |
| 16 | 16 |
| 17 HType computeType(HInstruction instruction) { | 17 HType computeType(HInstruction instruction) { |
| 18 return instruction.computeTypeFromInputTypes(); | 18 return instruction.computeTypeFromInputTypes(); |
| 19 } | 19 } |
| 20 | 20 |
| 21 // Re-compute and update the type of the instruction. Returns | 21 // Re-compute and update the type of the instruction. Returns |
| 22 // whether or not the type was changed. | 22 // whether or not the type was changed. |
| 23 bool updateType(HInstruction instruction) { | 23 bool updateType(HInstruction instruction) { |
| 24 if (instruction.propagatedType.isConflicting()) return false; | |
| 25 | |
| 26 HType oldType = instruction.propagatedType; | 24 HType oldType = instruction.propagatedType; |
| 27 HType newType = instruction.hasGuaranteedType() | 25 HType newType = instruction.hasGuaranteedType() |
| 28 ? instruction.guaranteedType | 26 ? instruction.guaranteedType |
| 29 : computeType(instruction); | 27 : computeType(instruction); |
| 30 instruction.propagatedType = oldType.combine(newType); | 28 // We unconditionally replace the propagated type with the new type. The |
| 31 return oldType !== instruction.propagatedType; | 29 // computeType must make sure that we eventually reach a stable state. |
| 30 instruction.propagatedType = newType; |
| 31 return oldType !== newType; |
| 32 } | 32 } |
| 33 | 33 |
| 34 void visitGraph(HGraph graph) { | 34 void visitGraph(HGraph graph) { |
| 35 visitDominatorTree(graph); | 35 visitDominatorTree(graph); |
| 36 processWorklist(); | 36 processWorklist(); |
| 37 } | 37 } |
| 38 | 38 |
| 39 visitBasicBlock(HBasicBlock block) { | 39 visitBasicBlock(HBasicBlock block) { |
| 40 if (block.isLoopHeader()) { | 40 if (block.isLoopHeader()) { |
| 41 block.forEachPhi((HPhi phi) { | 41 block.forEachPhi((HPhi phi) { |
| (...skipping 29 matching lines...) Expand all Loading... |
| 71 addDependentInstructionsToWorkList(instruction); | 71 addDependentInstructionsToWorkList(instruction); |
| 72 } | 72 } |
| 73 } | 73 } |
| 74 } | 74 } |
| 75 | 75 |
| 76 void addDependentInstructionsToWorkList(HInstruction instruction) { | 76 void addDependentInstructionsToWorkList(HInstruction instruction) { |
| 77 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { | 77 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { |
| 78 // The non-speculative type propagator only propagates types forward. We | 78 // The non-speculative type propagator only propagates types forward. We |
| 79 // thus only need to add the users of the [instruction] to the list. | 79 // thus only need to add the users of the [instruction] to the list. |
| 80 addToWorkList(instruction.usedBy[i]); | 80 addToWorkList(instruction.usedBy[i]); |
| 81 } | 81 } |
| 82 } | 82 } |
| 83 | 83 |
| 84 void addToWorkList(HInstruction instruction) { | 84 void addToWorkList(HInstruction instruction) { |
| 85 final int id = instruction.id; | 85 final int id = instruction.id; |
| 86 if (!workmap.containsKey(id)) { | 86 if (!workmap.containsKey(id)) { |
| 87 worklist.add(id); | 87 worklist.add(id); |
| 88 workmap[id] = instruction; | 88 workmap[id] = instruction; |
| 89 } | 89 } |
| 90 } | 90 } |
| 91 } | 91 } |
| 92 | 92 |
| 93 class SsaSpeculativeTypePropagator extends SsaTypePropagator { | 93 class SsaSpeculativeTypePropagator extends SsaTypePropagator { |
| 94 final String name = 'speculative type propagator'; | 94 final String name = 'speculative type propagator'; |
| 95 SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler); | 95 SsaSpeculativeTypePropagator(Compiler compiler) : super(compiler); |
| 96 | 96 |
| 97 void addDependentInstructionsToWorkList(HInstruction instruction) { | 97 void addDependentInstructionsToWorkList(HInstruction instruction) { |
| 98 // The speculative type propagator propagates types forward and backward. | 98 // The speculative type propagator propagates types forward and backward. |
| 99 // Not only do we need to add the users of the [instruction] to the list. | 99 // Not only do we need to add the users of the [instruction] to the list. |
| 100 // We also need to add the inputs fo the [instruction], since they might | 100 // We also need to add the inputs fo the [instruction], since they might |
| 101 // want to propagate the desired outgoing type. | 101 // want to propagate the desired outgoing type. |
| 102 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { | 102 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { |
| 103 addToWorkList(instruction.usedBy[i]); | 103 addToWorkList(instruction.usedBy[i]); |
| 104 } | 104 } |
| 105 for (int i = 0, length = instruction.inputs.length; i < length; i++) { | 105 for (int i = 0, length = instruction.inputs.length; i < length; i++) { |
| 106 addToWorkList(instruction.inputs[i]); | 106 addToWorkList(instruction.inputs[i]); |
| 107 } | 107 } |
| 108 } | 108 } |
| 109 | 109 |
| 110 HType computeDesiredType(HInstruction instruction) { | 110 HType computeDesiredType(HInstruction instruction) { |
| 111 HType desiredType = HType.UNKNOWN; | 111 HType desiredType = HType.UNKNOWN; |
| 112 for (final user in instruction.usedBy) { | 112 for (final user in instruction.usedBy) { |
| 113 desiredType = | 113 desiredType = |
| 114 desiredType.combine(user.computeDesiredTypeForInput(instruction)); | 114 desiredType.combine(user.computeDesiredTypeForInput(instruction)); |
| 115 // No need to continue if two users disagree on the type. | 115 // No need to continue if two users disagree on the type. |
| 116 if (desiredType.isConflicting()) break; | 116 if (desiredType.isConflicting()) break; |
| 117 } | 117 } |
| 118 return desiredType; | 118 return desiredType; |
| 119 } | 119 } |
| 120 | 120 |
| 121 HType computeType(HInstruction instruction) { | 121 HType computeType(HInstruction instruction) { |
| 122 // Once we are in a conflicting state don't update the type anymore. |
| 123 HType oldType = instruction.propagatedType; |
| 124 if (oldType.isConflicting()) return oldType; |
| 125 |
| 122 HType newType = super.computeType(instruction); | 126 HType newType = super.computeType(instruction); |
| 123 // [computeDesiredType] goes to all usedBys and lets them compute their | 127 // [computeDesiredType] goes to all usedBys and lets them compute their |
| 124 // desired type. By setting the [newType] here we give them more context to | 128 // desired type. By setting the [newType] here we give them more context to |
| 125 // work with. | 129 // work with. |
| 126 instruction.propagatedType = newType; | 130 instruction.propagatedType = newType; |
| 127 HType desiredType = computeDesiredType(instruction); | 131 HType desiredType = computeDesiredType(instruction); |
| 128 // If the desired type is conflicting just return the computed type. | 132 // If the desired type is conflicting just return the computed type. |
| 129 if (desiredType.isConflicting()) return newType; | 133 if (desiredType.isConflicting()) return newType; |
| 130 return newType.combine(desiredType); | 134 return newType.combine(desiredType); |
| 131 } | 135 } |
| 132 } | 136 } |
| OLD | NEW |