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