| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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 library dart2js.cps_ir.redundant_phi_elimination; | 5 library dart2js.cps_ir.redundant_phi_elimination; |
| 6 | 6 |
| 7 import 'cps_ir_nodes.dart'; | 7 import 'cps_ir_nodes.dart'; |
| 8 import 'optimizers.dart'; | 8 import 'optimizers.dart'; |
| 9 | 9 |
| 10 /// Eliminate redundant phis from the given [FunctionDefinition]. | 10 /// Eliminate redundant phis from the given [FunctionDefinition]. |
| (...skipping 29 matching lines...) Expand all Loading... |
| 40 | 40 |
| 41 /// Called for each continuation on the work set. Modifies the IR graph if | 41 /// Called for each continuation on the work set. Modifies the IR graph if |
| 42 /// [cont] is a candidate for redundant phi elimination. | 42 /// [cont] is a candidate for redundant phi elimination. |
| 43 void _processContinuation(Continuation cont) { | 43 void _processContinuation(Continuation cont) { |
| 44 // Generate the list of all cont invocations. If cont is used in any other | 44 // Generate the list of all cont invocations. If cont is used in any other |
| 45 // context (i.e. as a continuation of InvokeMethod), it is not possible to | 45 // context (i.e. as a continuation of InvokeMethod), it is not possible to |
| 46 // optimize. | 46 // optimize. |
| 47 List<InvokeContinuation> invokes = <InvokeContinuation>[]; | 47 List<InvokeContinuation> invokes = <InvokeContinuation>[]; |
| 48 for (Reference ref = cont.firstRef; ref != null; ref = ref.next) { | 48 for (Reference ref = cont.firstRef; ref != null; ref = ref.next) { |
| 49 Node parent = ref.parent; | 49 Node parent = ref.parent; |
| 50 if (parent is InvokeContinuation && ref == parent.continuation) { | 50 if (parent is InvokeContinuation && ref == parent.continuationRef) { |
| 51 invokes.add(parent); | 51 invokes.add(parent); |
| 52 } else { | 52 } else { |
| 53 return; // Can't optimize. | 53 return; // Can't optimize. |
| 54 } | 54 } |
| 55 } | 55 } |
| 56 | 56 |
| 57 if (invokes.isEmpty) { | 57 if (invokes.isEmpty) { |
| 58 return; // Continuation is never invoked, can't optimize. | 58 return; // Continuation is never invoked, can't optimize. |
| 59 } | 59 } |
| 60 | 60 |
| 61 /// Returns the unique definition of parameter i if it exists and null | 61 /// Returns the unique definition of parameter i if it exists and null |
| 62 /// otherwise. A definition is unique if it is the only value used to | 62 /// otherwise. A definition is unique if it is the only value used to |
| 63 /// invoke the continuation, excluding feedback. | 63 /// invoke the continuation, excluding feedback. |
| 64 Primitive uniqueDefinitionOf(int i) { | 64 Primitive uniqueDefinitionOf(int i) { |
| 65 Primitive value = null; | 65 Primitive value = null; |
| 66 for (InvokeContinuation invoke in invokes) { | 66 for (InvokeContinuation invoke in invokes) { |
| 67 Primitive def = invoke.arguments[i].definition.effectiveDefinition; | 67 Primitive def = invoke.argument(i).effectiveDefinition; |
| 68 | 68 |
| 69 if (cont.parameters[i] == def) { | 69 if (cont.parameters[i] == def) { |
| 70 // Invocation param == param in LetCont (i.e. a recursive call). | 70 // Invocation param == param in LetCont (i.e. a recursive call). |
| 71 continue; | 71 continue; |
| 72 } else if (value == null) { | 72 } else if (value == null) { |
| 73 value = def; // Set initial comparison value. | 73 value = def; // Set initial comparison value. |
| 74 } else if (value != def) { | 74 } else if (value != def) { |
| 75 return null; // Differing invocation arguments. | 75 return null; // Differing invocation arguments. |
| 76 } | 76 } |
| 77 } | 77 } |
| (...skipping 25 matching lines...) Expand all Loading... |
| 103 // to index `dst`. | 103 // to index `dst`. |
| 104 int dst = 0; | 104 int dst = 0; |
| 105 for (int src = 0; src < cont.parameters.length; src++) { | 105 for (int src = 0; src < cont.parameters.length; src++) { |
| 106 // Is the current phi redundant? | 106 // Is the current phi redundant? |
| 107 Primitive uniqueDefinition = uniqueDefinitionOf(src); | 107 Primitive uniqueDefinition = uniqueDefinitionOf(src); |
| 108 if (uniqueDefinition == null || !safeForHandlers(uniqueDefinition)) { | 108 if (uniqueDefinition == null || !safeForHandlers(uniqueDefinition)) { |
| 109 // Reorganize parameters and arguments in case of deletions. | 109 // Reorganize parameters and arguments in case of deletions. |
| 110 if (src != dst) { | 110 if (src != dst) { |
| 111 cont.parameters[dst] = cont.parameters[src]; | 111 cont.parameters[dst] = cont.parameters[src]; |
| 112 for (InvokeContinuation invoke in invokes) { | 112 for (InvokeContinuation invoke in invokes) { |
| 113 invoke.arguments[dst] = invoke.arguments[src]; | 113 invoke.argumentRefs[dst] = invoke.argumentRefs[src]; |
| 114 } | 114 } |
| 115 } | 115 } |
| 116 dst++; | 116 dst++; |
| 117 continue; | 117 continue; |
| 118 } | 118 } |
| 119 | 119 |
| 120 Primitive oldDefinition = cont.parameters[src]; | 120 Primitive oldDefinition = cont.parameters[src]; |
| 121 | 121 |
| 122 // Add continuations of about-to-be modified invokes to worklist since | 122 // Add continuations of about-to-be modified invokes to worklist since |
| 123 // we might introduce new optimization opportunities. | 123 // we might introduce new optimization opportunities. |
| 124 for (Reference ref = oldDefinition.firstRef; | 124 for (Reference ref = oldDefinition.firstRef; |
| 125 ref != null; | 125 ref != null; |
| 126 ref = ref.next) { | 126 ref = ref.next) { |
| 127 Node parent = ref.parent; | 127 Node parent = ref.parent; |
| 128 if (parent is InvokeContinuation) { | 128 if (parent is InvokeContinuation) { |
| 129 Continuation thatCont = parent.continuation.definition; | 129 Continuation thatCont = parent.continuation; |
| 130 if (thatCont != cont) { | 130 if (thatCont != cont) { |
| 131 workSet.add(thatCont); | 131 workSet.add(thatCont); |
| 132 } | 132 } |
| 133 } | 133 } |
| 134 } | 134 } |
| 135 | 135 |
| 136 // Replace individual parameters: | 136 // Replace individual parameters: |
| 137 // * In the continuation body, replace occurrence of param with value, | 137 // * In the continuation body, replace occurrence of param with value, |
| 138 // * and implicitly remove param from continuation signature and | 138 // * and implicitly remove param from continuation signature and |
| 139 // invocations by not incrementing `dst`. References of removed | 139 // invocations by not incrementing `dst`. References of removed |
| 140 // arguments are unlinked to keep definition usages up to date. | 140 // arguments are unlinked to keep definition usages up to date. |
| 141 oldDefinition.replaceUsesWith(uniqueDefinition); | 141 oldDefinition.replaceUsesWith(uniqueDefinition); |
| 142 for (InvokeContinuation invoke in invokes) { | 142 for (InvokeContinuation invoke in invokes) { |
| 143 invoke.arguments[src].unlink(); | 143 invoke.argumentRefs[src].unlink(); |
| 144 } | 144 } |
| 145 | 145 |
| 146 // Finally, if the substituted definition is not in scope of the affected | 146 // Finally, if the substituted definition is not in scope of the affected |
| 147 // continuation, move the continuation binding. This is safe to do since | 147 // continuation, move the continuation binding. This is safe to do since |
| 148 // the continuation is referenced only as the target in continuation | 148 // the continuation is referenced only as the target in continuation |
| 149 // invokes, and all such invokes must be within the scope of | 149 // invokes, and all such invokes must be within the scope of |
| 150 // [uniqueDefinition]. Note that this is linear in the depth of | 150 // [uniqueDefinition]. Note that this is linear in the depth of |
| 151 // the binding of [uniqueDefinition]. | 151 // the binding of [uniqueDefinition]. |
| 152 letCont = _makeUniqueBinding(cont); | 152 letCont = _makeUniqueBinding(cont); |
| 153 _moveIntoScopeOf(letCont, uniqueDefinition); | 153 _moveIntoScopeOf(letCont, uniqueDefinition); |
| 154 } | 154 } |
| 155 | 155 |
| 156 // Remove trailing items from parameter and argument lists. | 156 // Remove trailing items from parameter and argument lists. |
| 157 cont.parameters.length = dst; | 157 cont.parameters.length = dst; |
| 158 for (InvokeContinuation invoke in invokes) { | 158 for (InvokeContinuation invoke in invokes) { |
| 159 invoke.arguments.length = dst; | 159 invoke.argumentRefs.length = dst; |
| 160 } | 160 } |
| 161 } | 161 } |
| 162 | 162 |
| 163 void processLetCont(LetCont node) { | 163 void processLetCont(LetCont node) { |
| 164 node.continuations.forEach(workSet.add); | 164 node.continuations.forEach(workSet.add); |
| 165 } | 165 } |
| 166 } | 166 } |
| 167 | 167 |
| 168 /// Returns true, iff [letCont] is not scope of [definition]. | 168 /// Returns true, iff [letCont] is not scope of [definition]. |
| 169 /// Linear in the depth of definition within the IR graph. | 169 /// Linear in the depth of definition within the IR graph. |
| (...skipping 25 matching lines...) Expand all Loading... |
| 195 /// Returns the LetCont that now binds [continuation]. | 195 /// Returns the LetCont that now binds [continuation]. |
| 196 LetCont _makeUniqueBinding(Continuation continuation) { | 196 LetCont _makeUniqueBinding(Continuation continuation) { |
| 197 LetCont letCont = continuation.parent; | 197 LetCont letCont = continuation.parent; |
| 198 if (letCont.continuations.length == 1) return letCont; | 198 if (letCont.continuations.length == 1) return letCont; |
| 199 letCont.continuations.remove(continuation); | 199 letCont.continuations.remove(continuation); |
| 200 LetCont newBinding = new LetCont(continuation, null); | 200 LetCont newBinding = new LetCont(continuation, null); |
| 201 continuation.parent = newBinding; | 201 continuation.parent = newBinding; |
| 202 newBinding.insertBelow(letCont); | 202 newBinding.insertBelow(letCont); |
| 203 return newBinding; | 203 return newBinding; |
| 204 } | 204 } |
| OLD | NEW |