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 |