| // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| library dart2js.cps_ir.optimize_interceptors; |
| |
| import 'optimizers.dart'; |
| import 'cps_ir_nodes.dart'; |
| import 'loop_hierarchy.dart'; |
| import 'cps_fragment.dart'; |
| import '../constants/values.dart'; |
| import '../elements/elements.dart'; |
| import '../js_backend/backend_helpers.dart' show BackendHelpers; |
| import '../js_backend/js_backend.dart' show JavaScriptBackend; |
| import '../types/types.dart' show TypeMask; |
| import '../io/source_information.dart' show SourceInformation; |
| import '../world.dart'; |
| import 'type_mask_system.dart'; |
| |
| /// Replaces `getInterceptor` calls with interceptor constants when possible, |
| /// or with "almost constant" expressions like "x && CONST" when the input |
| /// is either null or has a known interceptor. |
| /// |
| /// Narrows the set of intercepted classes for interceptor calls. |
| /// |
| /// Replaces calls on interceptors with one-shot interceptors. |
| class OptimizeInterceptors extends TrampolineRecursiveVisitor implements Pass { |
| String get passName => 'Optimize interceptors'; |
| |
| final TypeMaskSystem typeSystem; |
| final JavaScriptBackend backend; |
| LoopHierarchy loopHierarchy; |
| Continuation currentLoopHeader; |
| |
| OptimizeInterceptors(this.backend, this.typeSystem); |
| |
| BackendHelpers get helpers => backend.helpers; |
| World get classWorld => backend.compiler.world; |
| |
| Map<Interceptor, Continuation> loopHeaderFor = <Interceptor, Continuation>{}; |
| |
| void rewrite(FunctionDefinition node) { |
| // TODO(asgerf): Computing the LoopHierarchy here may be overkill when all |
| // we want is to hoist constants out of loops. |
| loopHierarchy = new LoopHierarchy(node); |
| visit(node.body); |
| new ShareConstants().visit(node); |
| } |
| |
| @override |
| Expression traverseContinuation(Continuation cont) { |
| Continuation oldLoopHeader = currentLoopHeader; |
| currentLoopHeader = loopHierarchy.getLoopHeader(cont); |
| pushAction(() { |
| currentLoopHeader = oldLoopHeader; |
| }); |
| return cont.body; |
| } |
| |
| bool hasNoFalsyValues(ClassElement class_) { |
| return class_ != helpers.jsInterceptorClass && |
| class_ != helpers.jsNullClass && |
| class_ != helpers.jsBoolClass && |
| class_ != helpers.jsStringClass && |
| !class_.isSubclassOf(helpers.jsNumberClass); |
| } |
| |
| Continuation getCurrentOuterLoop({Continuation scope}) { |
| Continuation inner = null, outer = currentLoopHeader; |
| while (outer != scope) { |
| inner = outer; |
| outer = loopHierarchy.getEnclosingLoop(outer); |
| } |
| return inner; |
| } |
| |
| /// Binds the given constant in a primitive, in scope of the [useSite]. |
| /// |
| /// The constant will be hoisted out of loops, and shared with other requests |
| /// for the same constant as long as it is in scope. |
| Primitive makeConstantFor(ConstantValue constant, |
| {Expression useSite, |
| TypeMask type, |
| SourceInformation sourceInformation, |
| Entity hint}) { |
| Constant prim = |
| new Constant(constant, sourceInformation: sourceInformation); |
| prim.hint = hint; |
| prim.type = type; |
| LetPrim letPrim = new LetPrim(prim); |
| Continuation loop = getCurrentOuterLoop(); |
| if (loop != null) { |
| LetCont loopBinding = loop.parent; |
| letPrim.insertAbove(loopBinding); |
| } else { |
| letPrim.insertAbove(useSite); |
| } |
| return prim; |
| } |
| |
| void computeInterceptedClasses(Interceptor interceptor) { |
| Set<ClassElement> intercepted = interceptor.interceptedClasses; |
| intercepted.clear(); |
| for (Reference ref = interceptor.firstRef; ref != null; ref = ref.next) { |
| Node use = ref.parent; |
| if (use is InvokeMethod) { |
| TypeMask type = use.dartReceiver.type; |
| bool canOccurAsReceiver(ClassElement elem) { |
| return classWorld.isInstantiated(elem) && |
| !typeSystem.areDisjoint(type, |
| typeSystem.getInterceptorSubtypes(elem)); |
| } |
| Iterable<ClassElement> classes = |
| backend.getInterceptedClassesOn(use.selector.name); |
| intercepted.addAll(classes.where(canOccurAsReceiver)); |
| } else { |
| intercepted.clear(); |
| intercepted.add(backend.helpers.jsInterceptorClass); |
| break; |
| } |
| } |
| if (intercepted.contains(backend.helpers.jsInterceptorClass) || |
| intercepted.contains(backend.helpers.jsNullClass)) { |
| // If the null value is intercepted, update the type of the interceptor. |
| // The Tree IR uses this information to determine if the method lookup |
| // on an InvokeMethod might throw. |
| interceptor.type = interceptor.type.nonNullable(); |
| } |
| } |
| |
| /// True if [node] may return [JSNumber] instead of [JSInt] or [JSDouble]. |
| bool jsNumberClassSuffices(Interceptor node) { |
| // No methods on JSNumber call 'down' to methods on JSInt or JSDouble. If |
| // all uses of the interceptor are for methods is defined only on JSNumber |
| // then JSNumber will suffice in place of choosing between JSInt or |
| // JSDouble. |
| for (Reference ref = node.firstRef; ref != null; ref = ref.next) { |
| if (ref.parent is InvokeMethod) { |
| InvokeMethod invoke = ref.parent; |
| if (invoke.receiverRef != ref) return false; |
| var interceptedClasses = |
| backend.getInterceptedClassesOn(invoke.selector.name); |
| if (interceptedClasses.contains(helpers.jsDoubleClass)) return false; |
| if (interceptedClasses.contains(helpers.jsIntClass)) return false; |
| continue; |
| } |
| // Other uses need full distinction. |
| return false; |
| } |
| return true; |
| } |
| |
| /// True if [node] can intercept a `null` value and return the [JSNull] |
| /// interceptor. |
| bool canInterceptNull(Interceptor node) { |
| for (Reference ref = node.firstRef; ref != null; ref = ref.next) { |
| Node use = ref.parent; |
| if (use is InvokeMethod) { |
| if (selectorsOnNull.contains(use.selector) && |
| use.dartReceiver.type.isNullable) { |
| return true; |
| } |
| } else { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /// Returns the only interceptor class that may be returned by [node], or |
| /// `null` if no such class could be found. |
| ClassElement getSingleInterceptorClass(Interceptor node) { |
| // TODO(asgerf): This could be more precise if we used the use-site type, |
| // since the interceptor may have been hoisted out of a loop, where a less |
| // precise type is known. |
| Primitive input = node.input; |
| TypeMask type = input.type; |
| if (canInterceptNull(node)) return null; |
| type = type.nonNullable(); |
| if (typeSystem.isDefinitelyArray(type)) { |
| return backend.helpers.jsArrayClass; |
| } |
| if (typeSystem.isDefinitelyInt(type)) { |
| return backend.helpers.jsIntClass; |
| } |
| if (typeSystem.isDefinitelyNum(type) && jsNumberClassSuffices(node)) { |
| return backend.helpers.jsNumberClass; |
| } |
| ClassElement singleClass = type.singleClass(classWorld); |
| if (singleClass != null && |
| singleClass.isSubclassOf(backend.helpers.jsInterceptorClass)) { |
| return singleClass; |
| } |
| return null; |
| } |
| |
| /// Try to replace [interceptor] with a constant, and return `true` if |
| /// successful. |
| bool constifyInterceptor(Interceptor interceptor) { |
| LetPrim let = interceptor.parent; |
| Primitive input = interceptor.input; |
| ClassElement classElement = getSingleInterceptorClass(interceptor); |
| |
| if (classElement == null) return false; |
| ConstantValue constant = new InterceptorConstantValue(classElement.rawType); |
| |
| if (!input.type.isNullable) { |
| Primitive constantPrim = makeConstantFor(constant, |
| useSite: let, |
| type: interceptor.type, |
| sourceInformation: interceptor.sourceInformation); |
| constantPrim.useElementAsHint(interceptor.hint); |
| interceptor..replaceUsesWith(constantPrim)..destroy(); |
| let.remove(); |
| } else { |
| Primitive constantPrim = makeConstantFor(constant, |
| useSite: let, |
| type: interceptor.type.nonNullable(), |
| sourceInformation: interceptor.sourceInformation); |
| CpsFragment cps = new CpsFragment(interceptor.sourceInformation); |
| Parameter param = new Parameter(interceptor.hint); |
| param.type = interceptor.type; |
| Continuation cont = cps.letCont(<Parameter>[param]); |
| if (hasNoFalsyValues(classElement)) { |
| // If null is the only falsy value, compile as "x && CONST". |
| cps.ifFalsy(input).invokeContinuation(cont, [input]); |
| } else { |
| // If there are other falsy values compile as "x == null ? x : CONST". |
| Primitive condition = cps.applyBuiltin( |
| BuiltinOperator.LooseEq, |
| [input, cps.makeNull()]); |
| cps.ifTruthy(condition).invokeContinuation(cont, [input]); |
| } |
| cps.invokeContinuation(cont, [constantPrim]); |
| cps.context = cont; |
| cps.insertAbove(let); |
| interceptor..replaceUsesWith(param)..destroy(); |
| let.remove(); |
| } |
| return true; |
| } |
| |
| @override |
| Expression traverseLetPrim(LetPrim node) { |
| Expression next = node.body; |
| visit(node.primitive); |
| return next; |
| } |
| |
| @override |
| void visitInterceptor(Interceptor node) { |
| if (constifyInterceptor(node)) return; |
| computeInterceptedClasses(node); |
| if (node.hasExactlyOneUse) { |
| // Set the loop header on single-use interceptors so [visitInvokeMethod] |
| // can determine if it should become a one-shot interceptor. |
| loopHeaderFor[node] = currentLoopHeader; |
| } |
| } |
| |
| @override |
| void visitInvokeMethod(InvokeMethod node) { |
| if (node.callingConvention != CallingConvention.Intercepted) return; |
| Primitive interceptor = node.receiver; |
| if (interceptor is! Interceptor || |
| interceptor.hasMultipleUses || |
| loopHeaderFor[interceptor] != currentLoopHeader) { |
| return; |
| } |
| // TODO(asgerf): Consider heuristics for when to use one-shot interceptors. |
| // E.g. using only one-shot interceptors with a fast path. |
| node.callingConvention = CallingConvention.OneShotIntercepted; |
| node..receiverRef.unlink()..receiverRef = node.argumentRefs.removeAt(0); |
| } |
| |
| @override |
| void visitTypeTestViaFlag(TypeTestViaFlag node) { |
| Primitive interceptor = node.interceptor; |
| if (interceptor is! Interceptor || |
| interceptor.hasMultipleUses || |
| loopHeaderFor[interceptor] != currentLoopHeader || |
| !backend.mayGenerateInstanceofCheck(node.dartType)) { |
| return; |
| } |
| Interceptor inter = interceptor; |
| Primitive value = inter.input; |
| node.replaceWith(new TypeTest(value, node.dartType, [])..type = node.type); |
| } |
| } |
| |
| /// Shares interceptor constants when one is in scope of another. |
| /// |
| /// Interceptor optimization runs after GVN, hence this clean-up step is needed. |
| /// |
| /// TODO(asgerf): Handle in separate constant optimization pass? With some other |
| /// constant-related optimizations, like cloning small constants at use-site. |
| class ShareConstants extends TrampolineRecursiveVisitor { |
| Map<ConstantValue, Constant> sharedConstantFor = <ConstantValue, Constant>{}; |
| |
| Expression traverseLetPrim(LetPrim node) { |
| Expression next = node.body; |
| if (node.primitive is Constant && shouldShareConstant(node.primitive)) { |
| Constant prim = node.primitive; |
| Constant existing = sharedConstantFor[prim.value]; |
| if (existing != null) { |
| existing.useElementAsHint(prim.hint); |
| prim..replaceUsesWith(existing)..destroy(); |
| node.remove(); |
| return next; |
| } |
| sharedConstantFor[prim.value] = prim; |
| pushAction(() { |
| assert(sharedConstantFor[prim.value] == prim); |
| sharedConstantFor.remove(prim.value); |
| }); |
| } |
| return next; |
| } |
| |
| bool shouldShareConstant(Constant constant) { |
| return constant.value.isInterceptor; |
| } |
| } |