OLD | NEW |
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, 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.share_interceptors; | 5 library dart2js.cps_ir.share_interceptors; |
6 | 6 |
7 import 'optimizers.dart'; | 7 import 'optimizers.dart'; |
8 import 'cps_ir_nodes.dart'; | 8 import 'cps_ir_nodes.dart'; |
9 import 'loop_hierarchy.dart'; | 9 import 'loop_hierarchy.dart'; |
| 10 import 'cps_fragment.dart'; |
10 import '../constants/values.dart'; | 11 import '../constants/values.dart'; |
| 12 import '../elements/elements.dart'; |
| 13 import '../js_backend/js_backend.dart' show JavaScriptBackend; |
| 14 import '../types/types.dart' show TypeMask; |
| 15 import '../io/source_information.dart' show SourceInformation; |
11 | 16 |
12 /// Removes redundant `getInterceptor` calls. | 17 /// Removes redundant `getInterceptor` calls. |
13 /// | 18 /// |
14 /// The pass performs three optimizations for interceptors: | 19 /// The pass performs three optimizations for interceptors: |
15 ///- pull interceptors out of loops | 20 ///- pull interceptors out of loops |
16 ///- replace interceptors with constants | 21 ///- replace interceptors with constants |
17 ///- share interceptors when one is in scope of the other | 22 ///- share interceptors when one is in scope of the other |
18 class ShareInterceptors extends TrampolineRecursiveVisitor implements Pass { | 23 class ShareInterceptors extends TrampolineRecursiveVisitor implements Pass { |
19 String get passName => 'Share interceptors'; | 24 String get passName => 'Share interceptors'; |
20 | 25 |
21 /// The innermost loop containing a given primitive. | 26 /// The innermost loop containing a given primitive. |
22 final Map<Primitive, Continuation> loopHeaderFor = | 27 final Map<Primitive, Continuation> loopHeaderFor = |
23 <Primitive, Continuation>{}; | 28 <Primitive, Continuation>{}; |
24 | 29 |
25 /// An interceptor currently in scope for a given primitive. | 30 /// An interceptor currently in scope for a given primitive. |
26 final Map<Primitive, Primitive> interceptorFor = | 31 final Map<Primitive, Interceptor> interceptorFor = <Primitive, Interceptor>{}; |
27 <Primitive, Primitive>{}; | |
28 | 32 |
29 /// A primitive currently in scope holding a given interceptor constant. | 33 /// Interceptors that have been hoisted out of a given loop. |
30 final Map<ConstantValue, Primitive> sharedConstantFor = | 34 final Map<Continuation, List<Interceptor>> loopHoistedInterceptors = |
31 <ConstantValue, Primitive>{}; | 35 <Continuation, List<Interceptor>>{}; |
32 | 36 |
33 /// Interceptors to be hoisted out of the given loop. | 37 JavaScriptBackend backend; |
34 final Map<Continuation, List<Primitive>> loopHoistedInterceptors = | |
35 <Continuation, List<Primitive>>{}; | |
36 | |
37 LoopHierarchy loopHierarchy; | 38 LoopHierarchy loopHierarchy; |
38 Continuation currentLoopHeader; | 39 Continuation currentLoopHeader; |
39 | 40 |
| 41 ShareInterceptors(this.backend); |
| 42 |
40 void rewrite(FunctionDefinition node) { | 43 void rewrite(FunctionDefinition node) { |
41 loopHierarchy = new LoopHierarchy(node); | 44 loopHierarchy = new LoopHierarchy(node); |
42 visit(node.body); | 45 visit(node.body); |
| 46 new ShareConstants().visit(node); |
43 } | 47 } |
44 | 48 |
45 @override | 49 @override |
46 Expression traverseContinuation(Continuation cont) { | 50 Expression traverseContinuation(Continuation cont) { |
47 Continuation oldLoopHeader = currentLoopHeader; | 51 Continuation oldLoopHeader = currentLoopHeader; |
48 pushAction(() { | |
49 currentLoopHeader = oldLoopHeader; | |
50 }); | |
51 currentLoopHeader = loopHierarchy.getLoopHeader(cont); | 52 currentLoopHeader = loopHierarchy.getLoopHeader(cont); |
52 for (Parameter param in cont.parameters) { | 53 for (Parameter param in cont.parameters) { |
53 loopHeaderFor[param] = currentLoopHeader; | 54 loopHeaderFor[param] = currentLoopHeader; |
54 } | 55 } |
55 if (cont.isRecursive) { | 56 if (cont.isRecursive) { |
56 pushAction(() { | 57 pushAction(() { |
57 // After the loop body has been processed, all interceptors hoisted | 58 // After the loop body has been processed, all interceptors hoisted |
58 // to this loop fall out of scope and should be removed from the | 59 // to this loop fall out of scope and should be removed from the |
59 // environment. | 60 // environment. |
60 List<Primitive> hoisted = loopHoistedInterceptors[cont]; | 61 List<Interceptor> hoisted = loopHoistedInterceptors[cont]; |
61 if (hoisted != null) { | 62 if (hoisted != null) { |
62 for (Primitive interceptor in hoisted) { | 63 for (Interceptor interceptor in hoisted) { |
63 if (interceptor is Interceptor) { | 64 Primitive input = interceptor.input.definition; |
64 Primitive input = interceptor.input.definition; | 65 assert(interceptorFor[input] == interceptor); |
65 assert(interceptorFor[input] == interceptor); | 66 interceptorFor.remove(input); |
66 interceptorFor.remove(input); | 67 constifyInterceptor(interceptor); |
67 } else if (interceptor is Constant) { | |
68 assert(sharedConstantFor[interceptor.value] == interceptor); | |
69 sharedConstantFor.remove(interceptor.value); | |
70 } else { | |
71 throw "Unexpected interceptor: $interceptor"; | |
72 } | |
73 } | 68 } |
74 } | 69 } |
75 }); | 70 }); |
76 } | 71 } |
| 72 pushAction(() { |
| 73 currentLoopHeader = oldLoopHeader; |
| 74 }); |
77 return cont.body; | 75 return cont.body; |
78 } | 76 } |
79 | 77 |
| 78 /// If only one method table can be returned by the given interceptor, |
| 79 /// returns a constant for that method table. |
| 80 InterceptorConstantValue getInterceptorConstant(Interceptor node) { |
| 81 if (node.interceptedClasses.length == 1 && |
| 82 node.isInterceptedClassAlwaysExact) { |
| 83 ClassElement interceptorClass = node.interceptedClasses.single; |
| 84 return new InterceptorConstantValue(interceptorClass.rawType); |
| 85 } |
| 86 return null; |
| 87 } |
| 88 |
| 89 bool hasNoFalsyValues(ClassElement class_) { |
| 90 return class_ != backend.jsInterceptorClass && |
| 91 class_ != backend.jsNullClass && |
| 92 class_ != backend.jsBoolClass && |
| 93 class_ != backend.jsStringClass && |
| 94 !class_.isSubclassOf(backend.jsNumberClass); |
| 95 } |
| 96 |
| 97 Continuation getCurrentOuterLoop({Continuation scope}) { |
| 98 Continuation inner = null, outer = currentLoopHeader; |
| 99 while (outer != scope) { |
| 100 inner = outer; |
| 101 outer = loopHierarchy.getEnclosingLoop(outer); |
| 102 } |
| 103 return inner; |
| 104 } |
| 105 |
| 106 /// Binds the given constant in a primitive, in scope of the [useSite]. |
| 107 /// |
| 108 /// The constant will be hoisted out of loops, and shared with other requests |
| 109 /// for the same constant as long as it is in scope. |
| 110 Primitive makeConstantFor(ConstantValue constant, |
| 111 {Expression useSite, |
| 112 TypeMask type, |
| 113 SourceInformation sourceInformation, |
| 114 Entity hint}) { |
| 115 Constant prim = |
| 116 new Constant(constant, sourceInformation: sourceInformation); |
| 117 prim.hint = hint; |
| 118 prim.type = type; |
| 119 LetPrim letPrim = new LetPrim(prim); |
| 120 Continuation loop = getCurrentOuterLoop(); |
| 121 if (loop != null) { |
| 122 LetCont loopBinding = loop.parent; |
| 123 letPrim.insertAbove(loopBinding); |
| 124 } else { |
| 125 letPrim.insertAbove(useSite); |
| 126 } |
| 127 return prim; |
| 128 } |
| 129 |
| 130 void constifyInterceptor(Interceptor interceptor) { |
| 131 LetPrim let = interceptor.parent; |
| 132 InterceptorConstantValue constant = getInterceptorConstant(interceptor); |
| 133 |
| 134 if (constant == null) return; |
| 135 |
| 136 if (interceptor.isAlwaysIntercepted) { |
| 137 Primitive constantPrim = makeConstantFor(constant, |
| 138 useSite: let, |
| 139 type: interceptor.type, |
| 140 sourceInformation: interceptor.sourceInformation); |
| 141 constantPrim.useElementAsHint(interceptor.hint); |
| 142 constantPrim.substituteFor(interceptor); |
| 143 interceptor.destroy(); |
| 144 let.remove(); |
| 145 } else if (interceptor.isAlwaysNullOrIntercepted) { |
| 146 Primitive input = interceptor.input.definition; |
| 147 Primitive constantPrim = makeConstantFor(constant, |
| 148 useSite: let, |
| 149 type: interceptor.type.nonNullable(), |
| 150 sourceInformation: interceptor.sourceInformation); |
| 151 CpsFragment cps = new CpsFragment(interceptor.sourceInformation); |
| 152 Parameter param = new Parameter(interceptor.hint); |
| 153 Continuation cont = cps.letCont(<Parameter>[param]); |
| 154 if (interceptor.interceptedClasses.every(hasNoFalsyValues)) { |
| 155 // If null is the only falsy value, compile as "x && CONST". |
| 156 cps.ifFalsy(input).invokeContinuation(cont, [input]); |
| 157 } else { |
| 158 // If there are other falsy values compile as "x == null ? x : CONST". |
| 159 Primitive condition = cps.applyBuiltin( |
| 160 BuiltinOperator.LooseEq, |
| 161 [input, cps.makeNull()]); |
| 162 cps.ifTruthy(condition).invokeContinuation(cont, [input]); |
| 163 } |
| 164 cps.invokeContinuation(cont, [constantPrim]); |
| 165 cps.context = cont; |
| 166 cps.insertAbove(let); |
| 167 param.substituteFor(interceptor); |
| 168 interceptor.destroy(); |
| 169 let.remove(); |
| 170 } |
| 171 } |
| 172 |
80 @override | 173 @override |
81 Expression traverseLetPrim(LetPrim node) { | 174 Expression traverseLetPrim(LetPrim node) { |
82 loopHeaderFor[node.primitive] = currentLoopHeader; | 175 loopHeaderFor[node.primitive] = currentLoopHeader; |
83 Expression next = node.body; | 176 Expression next = node.body; |
84 if (node.primitive is! Interceptor) { | 177 if (node.primitive is! Interceptor) { |
85 return next; | 178 return next; |
86 } | 179 } |
87 Interceptor interceptor = node.primitive; | 180 Interceptor interceptor = node.primitive; |
88 Primitive input = interceptor.input.definition; | 181 Primitive input = interceptor.input.definition; |
89 | 182 |
90 // Try to reuse an existing interceptor for the same input. | 183 // Try to reuse an existing interceptor for the same input. |
91 Primitive existing = interceptorFor[input]; | 184 Interceptor existing = interceptorFor[input]; |
92 if (existing != null) { | 185 if (existing != null) { |
93 if (existing is Interceptor) { | 186 existing.interceptedClasses.addAll(interceptor.interceptedClasses); |
94 existing.interceptedClasses.addAll(interceptor.interceptedClasses); | 187 existing.flags |= interceptor.flags; |
95 } | |
96 existing.substituteFor(interceptor); | 188 existing.substituteFor(interceptor); |
97 interceptor.destroy(); | 189 interceptor.destroy(); |
98 node.remove(); | 190 node.remove(); |
99 return next; | 191 return next; |
100 } | 192 } |
101 | 193 |
102 // There is no interceptor obtained from this particular input, but | 194 // Put this interceptor in the environment. |
103 // there might one obtained from another input that is known to | 195 interceptorFor[input] = interceptor; |
104 // have the same result, so try to reuse that. | |
105 InterceptorConstantValue constant = interceptor.constantValue; | |
106 if (constant != null) { | |
107 existing = sharedConstantFor[constant]; | |
108 if (existing != null) { | |
109 existing.substituteFor(interceptor); | |
110 interceptor.destroy(); | |
111 node.remove(); | |
112 return next; | |
113 } | |
114 | 196 |
115 // The interceptor could not be shared. Replace it with a constant. | 197 // Determine how far the interceptor can be lifted. The outermost loop |
116 Constant constantPrim = new Constant(constant); | 198 // that contains the input binding should also contain the interceptor |
117 node.primitive = constantPrim; | 199 // binding. |
118 constantPrim.parent = node; | 200 Continuation referencedLoop = |
119 constantPrim.hint = interceptor.hint; | 201 lowestCommonAncestor(loopHeaderFor[input], currentLoopHeader); |
120 constantPrim.type = interceptor.type; | 202 if (referencedLoop != currentLoopHeader) { |
121 constantPrim.substituteFor(interceptor); | 203 Continuation hoistTarget = getCurrentOuterLoop(scope: referencedLoop); |
122 interceptor.destroy(); | 204 LetCont loopBinding = hoistTarget.parent; |
123 sharedConstantFor[constant] = constantPrim; | 205 node.remove(); |
| 206 node.insertAbove(loopBinding); |
| 207 // Remove the interceptor from the environment after processing the loop. |
| 208 loopHoistedInterceptors |
| 209 .putIfAbsent(hoistTarget, () => <Interceptor>[]) |
| 210 .add(interceptor); |
124 } else { | 211 } else { |
125 interceptorFor[input] = interceptor; | 212 // Remove the interceptor from the environment when it falls out of scope. |
| 213 pushAction(() { |
| 214 assert(interceptorFor[input] == interceptor); |
| 215 interceptorFor.remove(input); |
| 216 |
| 217 // Now that the final set of intercepted classes has been seen, try to |
| 218 // replace it with a constant. |
| 219 constifyInterceptor(interceptor); |
| 220 }); |
126 } | 221 } |
127 | 222 |
128 // Determine the outermost loop where the input to the interceptor call | |
129 // is available. Constant interceptors take no input and can thus be | |
130 // hoisted all way to the top-level. | |
131 Continuation referencedLoop = constant != null | |
132 ? null | |
133 : lowestCommonAncestor(loopHeaderFor[input], currentLoopHeader); | |
134 if (referencedLoop != currentLoopHeader) { | |
135 // [referencedLoop] contains the binding for [input], so we cannot hoist | |
136 // the interceptor outside that loop. Find the loop nested one level | |
137 // inside referencedLoop, and hoist the interceptor just outside that one. | |
138 Continuation loop = currentLoopHeader; | |
139 Continuation enclosing = loopHierarchy.getEnclosingLoop(loop); | |
140 while (enclosing != referencedLoop) { | |
141 assert(loop != null); | |
142 loop = enclosing; | |
143 enclosing = loopHierarchy.getEnclosingLoop(loop); | |
144 } | |
145 assert(loop != null); | |
146 | |
147 // Move the LetPrim above the loop binding. | |
148 LetCont loopBinding = loop.parent; | |
149 node.remove(); | |
150 node.insertAbove(loopBinding); | |
151 | |
152 // A different loop now contains the interceptor. | |
153 loopHeaderFor[node.primitive] = enclosing; | |
154 | |
155 // Register the interceptor as hoisted to that loop, so it will be | |
156 // removed from the environment when it falls out of scope. | |
157 loopHoistedInterceptors | |
158 .putIfAbsent(loop, () => <Primitive>[]) | |
159 .add(node.primitive); | |
160 } else if (constant != null) { | |
161 // The LetPrim was not hoisted. Remove the bound interceptor from the | |
162 // environment when leaving the LetPrim body. | |
163 pushAction(() { | |
164 assert(sharedConstantFor[constant] == node.primitive); | |
165 sharedConstantFor.remove(constant); | |
166 }); | |
167 } else { | |
168 pushAction(() { | |
169 assert(interceptorFor[input] == node.primitive); | |
170 interceptorFor.remove(input); | |
171 }); | |
172 } | |
173 return next; | 223 return next; |
174 } | 224 } |
175 | 225 |
176 /// Returns the the innermost loop that effectively encloses both | 226 /// Returns the the innermost loop that effectively encloses both |
177 /// c1 and c2 (or `null` if there is no such loop). | 227 /// c1 and c2 (or `null` if there is no such loop). |
178 Continuation lowestCommonAncestor(Continuation c1, Continuation c2) { | 228 Continuation lowestCommonAncestor(Continuation c1, Continuation c2) { |
179 int d1 = getDepth(c1), d2 = getDepth(c2); | 229 int d1 = getDepth(c1), d2 = getDepth(c2); |
180 while (c1 != c2) { | 230 while (c1 != c2) { |
181 if (d1 <= d2) { | 231 if (d1 <= d2) { |
182 c2 = loopHierarchy.getEnclosingLoop(c2); | 232 c2 = loopHierarchy.getEnclosingLoop(c2); |
183 d2 = getDepth(c2); | 233 d2 = getDepth(c2); |
184 } else { | 234 } else { |
185 c1 = loopHierarchy.getEnclosingLoop(c1); | 235 c1 = loopHierarchy.getEnclosingLoop(c1); |
186 d1 = getDepth(c1); | 236 d1 = getDepth(c1); |
187 } | 237 } |
188 } | 238 } |
189 return c1; | 239 return c1; |
190 } | 240 } |
191 | 241 |
192 int getDepth(Continuation loop) { | 242 int getDepth(Continuation loop) { |
193 if (loop == null) return -1; | 243 if (loop == null) return -1; |
194 return loopHierarchy.loopDepth[loop]; | 244 return loopHierarchy.loopDepth[loop]; |
195 } | 245 } |
196 } | 246 } |
| 247 |
| 248 class ShareConstants extends TrampolineRecursiveVisitor { |
| 249 Map<ConstantValue, Constant> sharedConstantFor = <ConstantValue, Constant>{}; |
| 250 |
| 251 Expression traverseLetPrim(LetPrim node) { |
| 252 Expression next = node.body; |
| 253 if (node.primitive is Constant && shouldShareConstant(node.primitive)) { |
| 254 Constant prim = node.primitive; |
| 255 Constant existing = sharedConstantFor[prim.value]; |
| 256 if (existing != null) { |
| 257 existing.substituteFor(prim); |
| 258 existing.useElementAsHint(prim.hint); |
| 259 prim.destroy(); |
| 260 node.remove(); |
| 261 return next; |
| 262 } |
| 263 sharedConstantFor[prim.value] = prim; |
| 264 pushAction(() { |
| 265 assert(sharedConstantFor[prim.value] == prim); |
| 266 sharedConstantFor.remove(prim.value); |
| 267 }); |
| 268 } |
| 269 return next; |
| 270 } |
| 271 |
| 272 bool shouldShareConstant(Constant constant) { |
| 273 return constant.value.isInterceptor; |
| 274 } |
| 275 } |
OLD | NEW |