| 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.optimize_interceptors; | |
| 6 | |
| 7 import '../constants/values.dart'; | |
| 8 import '../elements/elements.dart'; | |
| 9 import '../io/source_information.dart' show SourceInformation; | |
| 10 import '../js_backend/backend_helpers.dart' show BackendHelpers; | |
| 11 import '../js_backend/js_backend.dart' show JavaScriptBackend; | |
| 12 import '../types/types.dart' show TypeMask; | |
| 13 import '../world.dart'; | |
| 14 import 'cps_fragment.dart'; | |
| 15 import 'cps_ir_nodes.dart'; | |
| 16 import 'loop_hierarchy.dart'; | |
| 17 import 'optimizers.dart'; | |
| 18 import 'type_mask_system.dart'; | |
| 19 | |
| 20 /// Replaces `getInterceptor` calls with interceptor constants when possible, | |
| 21 /// or with "almost constant" expressions like "x && CONST" when the input | |
| 22 /// is either null or has a known interceptor. | |
| 23 /// | |
| 24 /// Narrows the set of intercepted classes for interceptor calls. | |
| 25 /// | |
| 26 /// Replaces calls on interceptors with one-shot interceptors. | |
| 27 class OptimizeInterceptors extends TrampolineRecursiveVisitor implements Pass { | |
| 28 String get passName => 'Optimize interceptors'; | |
| 29 | |
| 30 final TypeMaskSystem typeSystem; | |
| 31 final JavaScriptBackend backend; | |
| 32 LoopHierarchy loopHierarchy; | |
| 33 Continuation currentLoopHeader; | |
| 34 | |
| 35 OptimizeInterceptors(this.backend, this.typeSystem); | |
| 36 | |
| 37 BackendHelpers get helpers => backend.helpers; | |
| 38 World get classWorld => backend.compiler.world; | |
| 39 | |
| 40 Map<Interceptor, Continuation> loopHeaderFor = <Interceptor, Continuation>{}; | |
| 41 | |
| 42 void rewrite(FunctionDefinition node) { | |
| 43 // TODO(asgerf): Computing the LoopHierarchy here may be overkill when all | |
| 44 // we want is to hoist constants out of loops. | |
| 45 loopHierarchy = new LoopHierarchy(node); | |
| 46 visit(node.body); | |
| 47 new ShareConstants().visit(node); | |
| 48 } | |
| 49 | |
| 50 @override | |
| 51 Expression traverseContinuation(Continuation cont) { | |
| 52 Continuation oldLoopHeader = currentLoopHeader; | |
| 53 currentLoopHeader = loopHierarchy.getLoopHeader(cont); | |
| 54 pushAction(() { | |
| 55 currentLoopHeader = oldLoopHeader; | |
| 56 }); | |
| 57 return cont.body; | |
| 58 } | |
| 59 | |
| 60 bool hasNoFalsyValues(ClassElement class_) { | |
| 61 return class_ != helpers.jsInterceptorClass && | |
| 62 class_ != helpers.jsNullClass && | |
| 63 class_ != helpers.jsBoolClass && | |
| 64 class_ != helpers.jsStringClass && | |
| 65 !class_.isSubclassOf(helpers.jsNumberClass); | |
| 66 } | |
| 67 | |
| 68 Continuation getCurrentOuterLoop({Continuation scope}) { | |
| 69 Continuation inner = null, outer = currentLoopHeader; | |
| 70 while (outer != scope) { | |
| 71 inner = outer; | |
| 72 outer = loopHierarchy.getEnclosingLoop(outer); | |
| 73 } | |
| 74 return inner; | |
| 75 } | |
| 76 | |
| 77 /// Binds the given constant in a primitive, in scope of the [useSite]. | |
| 78 /// | |
| 79 /// The constant will be hoisted out of loops, and shared with other requests | |
| 80 /// for the same constant as long as it is in scope. | |
| 81 Primitive makeConstantFor(ConstantValue constant, | |
| 82 {Expression useSite, | |
| 83 TypeMask type, | |
| 84 SourceInformation sourceInformation, | |
| 85 Entity hint}) { | |
| 86 Constant prim = | |
| 87 new Constant(constant, sourceInformation: sourceInformation); | |
| 88 prim.hint = hint; | |
| 89 prim.type = type; | |
| 90 LetPrim letPrim = new LetPrim(prim); | |
| 91 Continuation loop = getCurrentOuterLoop(); | |
| 92 if (loop != null) { | |
| 93 LetCont loopBinding = loop.parent; | |
| 94 letPrim.insertAbove(loopBinding); | |
| 95 } else { | |
| 96 letPrim.insertAbove(useSite); | |
| 97 } | |
| 98 return prim; | |
| 99 } | |
| 100 | |
| 101 void computeInterceptedClasses(Interceptor interceptor) { | |
| 102 Set<ClassElement> intercepted = interceptor.interceptedClasses; | |
| 103 intercepted.clear(); | |
| 104 for (Reference ref = interceptor.firstRef; ref != null; ref = ref.next) { | |
| 105 Node use = ref.parent; | |
| 106 if (use is InvokeMethod) { | |
| 107 TypeMask type = use.receiver.type; | |
| 108 bool canOccurAsReceiver(ClassElement elem) { | |
| 109 return classWorld.isInstantiated(elem) && | |
| 110 !typeSystem.areDisjoint( | |
| 111 type, typeSystem.getInterceptorSubtypes(elem)); | |
| 112 } | |
| 113 | |
| 114 Iterable<ClassElement> classes = | |
| 115 backend.getInterceptedClassesOn(use.selector.name); | |
| 116 intercepted.addAll(classes.where(canOccurAsReceiver)); | |
| 117 } else { | |
| 118 intercepted.clear(); | |
| 119 intercepted.add(backend.helpers.jsInterceptorClass); | |
| 120 break; | |
| 121 } | |
| 122 } | |
| 123 if (intercepted.contains(backend.helpers.jsInterceptorClass) || | |
| 124 intercepted.contains(backend.helpers.jsNullClass)) { | |
| 125 // If the null value is intercepted, update the type of the interceptor. | |
| 126 // The Tree IR uses this information to determine if the method lookup | |
| 127 // on an InvokeMethod might throw. | |
| 128 interceptor.type = interceptor.type.nonNullable(); | |
| 129 } | |
| 130 } | |
| 131 | |
| 132 /// True if [node] may return [JSNumber] instead of [JSInt] or [JSDouble]. | |
| 133 bool jsNumberClassSuffices(Interceptor node) { | |
| 134 // No methods on JSNumber call 'down' to methods on JSInt or JSDouble. If | |
| 135 // all uses of the interceptor are for methods is defined only on JSNumber | |
| 136 // then JSNumber will suffice in place of choosing between JSInt or | |
| 137 // JSDouble. | |
| 138 for (Reference ref = node.firstRef; ref != null; ref = ref.next) { | |
| 139 if (ref.parent is InvokeMethod) { | |
| 140 InvokeMethod invoke = ref.parent; | |
| 141 if (invoke.interceptorRef != ref) return false; | |
| 142 var interceptedClasses = | |
| 143 backend.getInterceptedClassesOn(invoke.selector.name); | |
| 144 if (interceptedClasses.contains(helpers.jsDoubleClass)) return false; | |
| 145 if (interceptedClasses.contains(helpers.jsIntClass)) return false; | |
| 146 continue; | |
| 147 } | |
| 148 // Other uses need full distinction. | |
| 149 return false; | |
| 150 } | |
| 151 return true; | |
| 152 } | |
| 153 | |
| 154 /// True if [node] can intercept a `null` value and return the [JSNull] | |
| 155 /// interceptor. | |
| 156 bool canInterceptNull(Interceptor node) { | |
| 157 for (Reference ref = node.firstRef; ref != null; ref = ref.next) { | |
| 158 Node use = ref.parent; | |
| 159 if (use is InvokeMethod) { | |
| 160 if (selectorsOnNull.contains(use.selector) && | |
| 161 use.receiver.type.isNullable) { | |
| 162 return true; | |
| 163 } | |
| 164 } else { | |
| 165 return true; | |
| 166 } | |
| 167 } | |
| 168 return false; | |
| 169 } | |
| 170 | |
| 171 /// Returns the only interceptor class that may be returned by [node], or | |
| 172 /// `null` if no such class could be found. | |
| 173 ClassElement getSingleInterceptorClass(Interceptor node) { | |
| 174 // TODO(asgerf): This could be more precise if we used the use-site type, | |
| 175 // since the interceptor may have been hoisted out of a loop, where a less | |
| 176 // precise type is known. | |
| 177 Primitive input = node.input; | |
| 178 TypeMask type = input.type; | |
| 179 if (canInterceptNull(node)) return null; | |
| 180 type = type.nonNullable(); | |
| 181 if (typeSystem.isDefinitelyArray(type)) { | |
| 182 return backend.helpers.jsArrayClass; | |
| 183 } | |
| 184 if (typeSystem.isDefinitelyInt(type)) { | |
| 185 return backend.helpers.jsIntClass; | |
| 186 } | |
| 187 if (typeSystem.isDefinitelyNum(type) && jsNumberClassSuffices(node)) { | |
| 188 return backend.helpers.jsNumberClass; | |
| 189 } | |
| 190 ClassElement singleClass = type.singleClass(classWorld); | |
| 191 if (singleClass != null && | |
| 192 singleClass.isSubclassOf(backend.helpers.jsInterceptorClass)) { | |
| 193 return singleClass; | |
| 194 } | |
| 195 return null; | |
| 196 } | |
| 197 | |
| 198 /// Try to replace [interceptor] with a constant, and return `true` if | |
| 199 /// successful. | |
| 200 bool constifyInterceptor(Interceptor interceptor) { | |
| 201 LetPrim let = interceptor.parent; | |
| 202 Primitive input = interceptor.input; | |
| 203 ClassElement classElement = getSingleInterceptorClass(interceptor); | |
| 204 | |
| 205 if (classElement == null) return false; | |
| 206 ConstantValue constant = new InterceptorConstantValue(classElement.rawType); | |
| 207 | |
| 208 if (!input.type.isNullable) { | |
| 209 Primitive constantPrim = makeConstantFor(constant, | |
| 210 useSite: let, | |
| 211 type: interceptor.type, | |
| 212 sourceInformation: interceptor.sourceInformation); | |
| 213 constantPrim.useElementAsHint(interceptor.hint); | |
| 214 interceptor | |
| 215 ..replaceUsesWith(constantPrim) | |
| 216 ..destroy(); | |
| 217 let.remove(); | |
| 218 } else { | |
| 219 Primitive constantPrim = makeConstantFor(constant, | |
| 220 useSite: let, | |
| 221 type: interceptor.type.nonNullable(), | |
| 222 sourceInformation: interceptor.sourceInformation); | |
| 223 CpsFragment cps = new CpsFragment(interceptor.sourceInformation); | |
| 224 Parameter param = new Parameter(interceptor.hint); | |
| 225 param.type = interceptor.type; | |
| 226 Continuation cont = cps.letCont(<Parameter>[param]); | |
| 227 if (hasNoFalsyValues(classElement)) { | |
| 228 // If null is the only falsy value, compile as "x && CONST". | |
| 229 cps.ifFalsy(input).invokeContinuation(cont, [input]); | |
| 230 } else { | |
| 231 // If there are other falsy values compile as "x == null ? x : CONST". | |
| 232 Primitive condition = | |
| 233 cps.applyBuiltin(BuiltinOperator.LooseEq, [input, cps.makeNull()]); | |
| 234 cps.ifTruthy(condition).invokeContinuation(cont, [input]); | |
| 235 } | |
| 236 cps.invokeContinuation(cont, [constantPrim]); | |
| 237 cps.context = cont; | |
| 238 cps.insertAbove(let); | |
| 239 interceptor | |
| 240 ..replaceUsesWith(param) | |
| 241 ..destroy(); | |
| 242 let.remove(); | |
| 243 } | |
| 244 return true; | |
| 245 } | |
| 246 | |
| 247 @override | |
| 248 Expression traverseLetPrim(LetPrim node) { | |
| 249 Expression next = node.body; | |
| 250 visit(node.primitive); | |
| 251 return next; | |
| 252 } | |
| 253 | |
| 254 @override | |
| 255 void visitInterceptor(Interceptor node) { | |
| 256 if (constifyInterceptor(node)) return; | |
| 257 computeInterceptedClasses(node); | |
| 258 if (node.hasExactlyOneUse) { | |
| 259 // Set the loop header on single-use interceptors so [visitInvokeMethod] | |
| 260 // can determine if it should become a one-shot interceptor. | |
| 261 loopHeaderFor[node] = currentLoopHeader; | |
| 262 } | |
| 263 } | |
| 264 | |
| 265 @override | |
| 266 void visitInvokeMethod(InvokeMethod node) { | |
| 267 if (node.callingConvention != CallingConvention.Intercepted) return; | |
| 268 Primitive interceptor = node.interceptor; | |
| 269 if (interceptor is! Interceptor || | |
| 270 interceptor.hasMultipleUses || | |
| 271 loopHeaderFor[interceptor] != currentLoopHeader) { | |
| 272 return; | |
| 273 } | |
| 274 // TODO(asgerf): Consider heuristics for when to use one-shot interceptors. | |
| 275 // E.g. using only one-shot interceptors with a fast path. | |
| 276 node.makeOneShotIntercepted(); | |
| 277 } | |
| 278 | |
| 279 @override | |
| 280 void visitTypeTestViaFlag(TypeTestViaFlag node) { | |
| 281 Primitive interceptor = node.interceptor; | |
| 282 if (interceptor is! Interceptor || | |
| 283 interceptor.hasMultipleUses || | |
| 284 loopHeaderFor[interceptor] != currentLoopHeader || | |
| 285 !backend.mayGenerateInstanceofCheck(node.dartType)) { | |
| 286 return; | |
| 287 } | |
| 288 Interceptor inter = interceptor; | |
| 289 Primitive value = inter.input; | |
| 290 node.replaceWith(new TypeTest(value, node.dartType, [])..type = node.type); | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 /// Shares interceptor constants when one is in scope of another. | |
| 295 /// | |
| 296 /// Interceptor optimization runs after GVN, hence this clean-up step is needed. | |
| 297 /// | |
| 298 /// TODO(asgerf): Handle in separate constant optimization pass? With some other | |
| 299 /// constant-related optimizations, like cloning small constants at use-site. | |
| 300 class ShareConstants extends TrampolineRecursiveVisitor { | |
| 301 Map<ConstantValue, Constant> sharedConstantFor = <ConstantValue, Constant>{}; | |
| 302 | |
| 303 Expression traverseLetPrim(LetPrim node) { | |
| 304 Expression next = node.body; | |
| 305 if (node.primitive is Constant && shouldShareConstant(node.primitive)) { | |
| 306 Constant prim = node.primitive; | |
| 307 Constant existing = sharedConstantFor[prim.value]; | |
| 308 if (existing != null) { | |
| 309 existing.useElementAsHint(prim.hint); | |
| 310 prim | |
| 311 ..replaceUsesWith(existing) | |
| 312 ..destroy(); | |
| 313 node.remove(); | |
| 314 return next; | |
| 315 } | |
| 316 sharedConstantFor[prim.value] = prim; | |
| 317 pushAction(() { | |
| 318 assert(sharedConstantFor[prim.value] == prim); | |
| 319 sharedConstantFor.remove(prim.value); | |
| 320 }); | |
| 321 } | |
| 322 return next; | |
| 323 } | |
| 324 | |
| 325 bool shouldShareConstant(Constant constant) { | |
| 326 return constant.value.isInterceptor; | |
| 327 } | |
| 328 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
