| // Copyright (c) 2013, 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. | |
| import '../common_elements.dart' show CommonElements; | |
| import '../constants/values.dart'; | |
| import '../elements/entities.dart'; | |
| import '../js_backend/interceptor_data.dart'; | |
| import '../types/abstract_value_domain.dart'; | |
| import '../universe/selector.dart' show Selector; | |
| import '../world.dart' show JClosedWorld; | |
| import 'nodes.dart'; | |
| import 'optimize.dart'; | |
| /** | |
| * This phase simplifies interceptors in multiple ways: | |
| * | |
| * 1) If the interceptor is for an object whose type is known, it | |
| * tries to use a constant interceptor instead. | |
| * | |
| * 2) Interceptors are specialized based on the selector it is used with. | |
| * | |
| * 3) If we know the object is not intercepted, we just use the object | |
| * instead. | |
| * | |
| * 4) Single use interceptors at dynamic invoke sites are replaced with 'one | |
| * shot interceptors' which are synthesized static helper functions that fetch | |
| * the interceptor and then call the method. This saves code size and makes the | |
| * receiver of an intercepted call a candidate for being generated at use site. | |
| * | |
| * 5) Some HIs operations on an interceptor are replaced with a HIs version that | |
| * uses 'instanceof' rather than testing a type flag. | |
| * | |
| */ | |
| class SsaSimplifyInterceptors extends HBaseVisitor | |
| implements OptimizationPhase { | |
| final String name = "SsaSimplifyInterceptors"; | |
| final JClosedWorld _closedWorld; | |
| final ClassEntity _enclosingClass; | |
| HGraph _graph; | |
| SsaSimplifyInterceptors(this._closedWorld, this._enclosingClass); | |
| CommonElements get _commonElements => _closedWorld.commonElements; | |
| InterceptorData get _interceptorData => _closedWorld.interceptorData; | |
| AbstractValueDomain get _abstractValueDomain => | |
| _closedWorld.abstractValueDomain; | |
| void visitGraph(HGraph graph) { | |
| this._graph = graph; | |
| visitDominatorTree(graph); | |
| } | |
| void visitBasicBlock(HBasicBlock node) { | |
| currentBlock = node; | |
| HInstruction instruction = node.first; | |
| while (instruction != null) { | |
| bool shouldRemove = instruction.accept(this); | |
| HInstruction next = instruction.next; | |
| if (shouldRemove) { | |
| instruction.block.remove(instruction); | |
| } | |
| instruction = next; | |
| } | |
| } | |
| bool visitInstruction(HInstruction instruction) => false; | |
| bool visitInvoke(HInvoke invoke) { | |
| if (!invoke.isInterceptedCall) return false; | |
| dynamic interceptor = invoke.inputs[0]; | |
| if (interceptor is! HInterceptor) return false; | |
| // TODO(sra): Move this per-call code to visitInterceptor. | |
| // | |
| // The interceptor is visited first, so we get here only when the | |
| // interceptor was not rewritten to a single shared replacement. I'm not | |
| // sure we should substitute a constant interceptor on a per-call basis if | |
| // the interceptor is already available in a local variable, but it is | |
| // possible that all uses can be rewritten to use different constants. | |
| HInstruction constant = tryComputeConstantInterceptor( | |
| invoke.inputs[1], interceptor.interceptedClasses); | |
| if (constant != null) { | |
| invoke.changeUse(interceptor, constant); | |
| } | |
| return false; | |
| } | |
| bool canUseSelfForInterceptor(HInstruction receiver, | |
| {Set<ClassEntity> interceptedClasses}) { | |
| if (receiver.canBePrimitive(_abstractValueDomain)) { | |
| // Primitives always need interceptors. | |
| return false; | |
| } | |
| if (receiver.canBeNull(_abstractValueDomain)) { | |
| if (interceptedClasses == null || | |
| interceptedClasses.contains(_commonElements.jsNullClass)) { | |
| // Need the JSNull interceptor. | |
| return false; | |
| } | |
| } | |
| // All intercepted classes extend `Interceptor`, so if the receiver can't be | |
| // a class extending `Interceptor` then it can be called directly. | |
| return !_abstractValueDomain.canBeInterceptor(receiver.instructionType); | |
| } | |
| HInstruction tryComputeConstantInterceptor( | |
| HInstruction input, Set<ClassEntity> interceptedClasses) { | |
| ClassEntity constantInterceptor = tryComputeConstantInterceptorFromType( | |
| input.instructionType, interceptedClasses); | |
| if (constantInterceptor == null) return null; | |
| // If we just happen to be in an instance method of the constant | |
| // interceptor, `this` is a shorter alias. | |
| if (constantInterceptor == _enclosingClass && | |
| _graph.thisInstruction != null) { | |
| return _graph.thisInstruction; | |
| } | |
| ConstantValue constant = new InterceptorConstantValue(constantInterceptor); | |
| return _graph.addConstant(constant, _closedWorld); | |
| } | |
| ClassEntity tryComputeConstantInterceptorFromType( | |
| AbstractValue type, Set<ClassEntity> interceptedClasses) { | |
| if (_abstractValueDomain.canBeNull(type)) { | |
| if (_abstractValueDomain.isNull(type)) { | |
| return _commonElements.jsNullClass; | |
| } | |
| } else if (_abstractValueDomain.isIntegerOrNull(type)) { | |
| return _commonElements.jsIntClass; | |
| } else if (_abstractValueDomain.isDoubleOrNull(type)) { | |
| return _commonElements.jsDoubleClass; | |
| } else if (_abstractValueDomain.isBooleanOrNull(type)) { | |
| return _commonElements.jsBoolClass; | |
| } else if (_abstractValueDomain.isStringOrNull(type)) { | |
| return _commonElements.jsStringClass; | |
| } else if (_abstractValueDomain.isArray(type)) { | |
| return _commonElements.jsArrayClass; | |
| } else if (_abstractValueDomain.isNumberOrNull(type) && | |
| !interceptedClasses.contains(_commonElements.jsIntClass) && | |
| !interceptedClasses.contains(_commonElements.jsDoubleClass)) { | |
| // If the method being intercepted is not defined in [int] or [double] we | |
| // can safely use the number interceptor. This is because none of the | |
| // [int] or [double] methods are called from a method defined on [num]. | |
| return _commonElements.jsNumberClass; | |
| } else { | |
| // Try to find constant interceptor for a native class. If the receiver | |
| // is constrained to a leaf native class, we can use the class's | |
| // interceptor directly. | |
| // TODO(sra): Key DOM classes like Node, Element and Event are not leaf | |
| // classes. When the receiver type is not a leaf class, we might still be | |
| // able to use the receiver class as a constant interceptor. It is | |
| // usually the case that methods defined on a non-leaf class don't test | |
| // for a subclass or call methods defined on a subclass. Provided the | |
| // code is completely insensitive to the specific instance subclasses, we | |
| // can use the non-leaf class directly. | |
| ClassEntity element = _abstractValueDomain.getExactClass(type); | |
| if (element != null && _closedWorld.nativeData.isNativeClass(element)) { | |
| return element; | |
| } | |
| } | |
| return null; | |
| } | |
| HInstruction findDominator(Iterable<HInstruction> instructions) { | |
| HInstruction result; | |
| L1: | |
| for (HInstruction candidate in instructions) { | |
| for (HInstruction current in instructions) { | |
| if (current != candidate && !candidate.dominates(current)) continue L1; | |
| } | |
| result = candidate; | |
| break; | |
| } | |
| return result; | |
| } | |
| static int useCount(HInstruction user, HInstruction used) => | |
| user.inputs.where((input) => input == used).length; | |
| bool visitInterceptor(HInterceptor node) { | |
| if (node.receiver.nonCheck() == _graph.explicitReceiverParameter) { | |
| // If `explicitReceiverParameter` is set it means the current method is an | |
| // interceptor method, and `this` is the interceptor. The caller just did | |
| // `getInterceptor(foo).currentMethod(foo)` to enter the current method. | |
| node.block.rewrite(node, _graph.thisInstruction); | |
| return true; | |
| } | |
| rewriteSelfInterceptorUses(node); | |
| if (node.usedBy.isEmpty) return true; | |
| // Specialize the interceptor with set of classes it intercepts, considering | |
| // all uses. (The specialized interceptor has a shorter dispatch chain). | |
| // This operation applies only where the interceptor is used to dispatch a | |
| // method. Other uses, e.g. as an ordinary argument or a HIs check use the | |
| // most general interceptor. | |
| // | |
| // TODO(sra): Take into account the receiver type at each call. e.g: | |
| // | |
| // (a) => a.length + a.hashCode | |
| // | |
| // Currently we use the most general interceptor since all intercepted types | |
| // implement `hashCode`. But in this example, `a.hashCode` is only reached | |
| // if `a.length` succeeds, which is indicated by the hashCode receiver being | |
| // a HTypeKnown instruction. | |
| Set<ClassEntity> interceptedClasses; | |
| HInstruction dominator = findDominator(node.usedBy); | |
| // If there is a call that dominates all other uses, we can use just the | |
| // selector of that instruction. | |
| if (dominator is HInvokeDynamic && | |
| dominator.isCallOnInterceptor(_closedWorld) && | |
| node == dominator.receiver && | |
| useCount(dominator, node) == 1) { | |
| interceptedClasses = _interceptorData.getInterceptedClassesOn( | |
| dominator.selector.name, _closedWorld); | |
| // If we found that we need number, we must still go through all | |
| // uses to check if they require int, or double. | |
| if (interceptedClasses.contains(_commonElements.jsNumberClass) && | |
| !(interceptedClasses.contains(_commonElements.jsDoubleClass) || | |
| interceptedClasses.contains(_commonElements.jsIntClass))) { | |
| Set<ClassEntity> required; | |
| for (HInstruction user in node.usedBy) { | |
| if (user is! HInvoke) continue; | |
| Set<ClassEntity> intercepted = _interceptorData | |
| .getInterceptedClassesOn(user.selector.name, _closedWorld); | |
| if (intercepted.contains(_commonElements.jsIntClass)) { | |
| // TODO(johnniwinther): Use type argument when all uses of | |
| // intercepted classes expect entities instead of elements. | |
| required ??= new Set<ClassEntity>(); | |
| required.add(_commonElements.jsIntClass); | |
| } | |
| if (intercepted.contains(_commonElements.jsDoubleClass)) { | |
| // TODO(johnniwinther): Use type argument when all uses of | |
| // intercepted classes expect entities instead of elements. | |
| required ??= new Set<ClassEntity>(); | |
| required.add(_commonElements.jsDoubleClass); | |
| } | |
| } | |
| // Don't modify the result of | |
| // [_interceptorData.getInterceptedClassesOn]. | |
| if (required != null) { | |
| interceptedClasses = interceptedClasses.union(required); | |
| } | |
| } | |
| } else { | |
| // TODO(johnniwinther): Use type argument when all uses of intercepted | |
| // classes expect entities instead of elements. | |
| interceptedClasses = new Set<ClassEntity>(); | |
| for (HInstruction user in node.usedBy) { | |
| if (user is HInvokeDynamic && | |
| user.isCallOnInterceptor(_closedWorld) && | |
| node == user.receiver && | |
| useCount(user, node) == 1) { | |
| interceptedClasses.addAll(_interceptorData.getInterceptedClassesOn( | |
| user.selector.name, _closedWorld)); | |
| } else if (user is HInvokeSuper && | |
| user.isCallOnInterceptor(_closedWorld) && | |
| node == user.receiver && | |
| useCount(user, node) == 1) { | |
| interceptedClasses.addAll(_interceptorData.getInterceptedClassesOn( | |
| user.selector.name, _closedWorld)); | |
| } else { | |
| // Use a most general interceptor for other instructions, example, | |
| // is-checks and escaping interceptors. | |
| interceptedClasses.addAll(_interceptorData.interceptedClasses); | |
| break; | |
| } | |
| } | |
| } | |
| node.interceptedClasses = interceptedClasses; | |
| HInstruction receiver = node.receiver; | |
| // Try computing a constant interceptor. | |
| HInstruction constantInterceptor = | |
| tryComputeConstantInterceptor(receiver, interceptedClasses); | |
| if (constantInterceptor != null) { | |
| node.block.rewrite(node, constantInterceptor); | |
| return false; | |
| } | |
| // If it is a conditional constant interceptor and was not strengthened to a | |
| // constant interceptor then there is nothing more we can do. | |
| if (node.isConditionalConstantInterceptor) return false; | |
| // Do we have an 'almost constant' interceptor? The receiver could be | |
| // `null` but not any other JavaScript falsy value, `null` values cause | |
| // `NoSuchMethodError`s, and if the receiver was not null we would have a | |
| // constant interceptor `C`. Then we can use `(receiver && C)` for the | |
| // interceptor. | |
| if (receiver.canBeNull(_abstractValueDomain)) { | |
| if (!interceptedClasses.contains(_commonElements.jsNullClass)) { | |
| // Can use `(receiver && C)` only if receiver is either null or truthy. | |
| if (!(receiver.canBePrimitiveNumber(_abstractValueDomain) || | |
| receiver.canBePrimitiveBoolean(_abstractValueDomain) || | |
| receiver.canBePrimitiveString(_abstractValueDomain))) { | |
| ClassEntity interceptorClass = tryComputeConstantInterceptorFromType( | |
| _abstractValueDomain.excludeNull(receiver.instructionType), | |
| interceptedClasses); | |
| if (interceptorClass != null) { | |
| HInstruction constantInstruction = _graph.addConstant( | |
| new InterceptorConstantValue(interceptorClass), _closedWorld); | |
| node.conditionalConstantInterceptor = constantInstruction; | |
| constantInstruction.usedBy.add(node); | |
| return false; | |
| } | |
| } | |
| } | |
| } | |
| // Try creating a one-shot interceptor or optimized is-check | |
| if (node.usedBy.length != 1) return false; | |
| HInstruction user = node.usedBy.single; | |
| // If the interceptor [node] was loop hoisted, we keep the interceptor. | |
| if (!user.hasSameLoopHeaderAs(node)) return false; | |
| bool replaceUserWith(HInstruction replacement) { | |
| HBasicBlock block = user.block; | |
| block.addAfter(user, replacement); | |
| block.rewrite(user, replacement); | |
| block.remove(user); | |
| return false; | |
| } | |
| if (user is HIs) { | |
| // See if we can rewrite the is-check to use 'instanceof', i.e. rewrite | |
| // "getInterceptor(x).$isT" to "x instanceof T". | |
| if (node == user.interceptor) { | |
| if (_interceptorData.mayGenerateInstanceofCheck( | |
| user.typeExpression, _closedWorld)) { | |
| HInstruction instanceofCheck = new HIs.instanceOf(user.typeExpression, | |
| user.expression, user.instructionType, user.sourceInformation); | |
| instanceofCheck.sourceElement = user.sourceElement; | |
| return replaceUserWith(instanceofCheck); | |
| } | |
| } | |
| } else if (user is HInvokeDynamic) { | |
| if (node == user.inputs[0]) { | |
| // Replace the user with a [HOneShotInterceptor]. | |
| HConstant nullConstant = _graph.addConstantNull(_closedWorld); | |
| List<HInstruction> inputs = new List<HInstruction>.from(user.inputs); | |
| inputs[0] = nullConstant; | |
| HOneShotInterceptor oneShotInterceptor = new HOneShotInterceptor( | |
| _abstractValueDomain, | |
| user.selector, | |
| user.mask, | |
| inputs, | |
| user.instructionType, | |
| user.typeArguments, | |
| interceptedClasses); | |
| oneShotInterceptor.sourceInformation = user.sourceInformation; | |
| oneShotInterceptor.sourceElement = user.sourceElement; | |
| return replaceUserWith(oneShotInterceptor); | |
| } | |
| } | |
| return false; | |
| } | |
| void rewriteSelfInterceptorUses(HInterceptor node) { | |
| HInstruction receiver = node.receiver; | |
| // At instructions that use the interceptor and its receiver, the receiver | |
| // might be refined at the use site. | |
| // dynamic x = ... | |
| // if (x is Mumble) { | |
| // print(x.length); // Self-interceptor here. | |
| // } else { | |
| // print(x.length); // | |
| // } | |
| finishInvoke(HInvoke invoke, Selector selector) { | |
| HInstruction callReceiver = invoke.getDartReceiver(_closedWorld); | |
| if (receiver.nonCheck() == callReceiver.nonCheck()) { | |
| Set<ClassEntity> interceptedClasses = _interceptorData | |
| .getInterceptedClassesOn(selector.name, _closedWorld); | |
| if (canUseSelfForInterceptor(callReceiver, | |
| interceptedClasses: interceptedClasses)) { | |
| invoke.changeUse(node, callReceiver); | |
| } | |
| } | |
| } | |
| for (HInstruction user in node.usedBy.toList()) { | |
| if (user is HIs) { | |
| if (user.interceptor == node) { | |
| HInstruction expression = user.expression; | |
| if (canUseSelfForInterceptor(expression)) { | |
| user.changeUse(node, expression); | |
| } | |
| } | |
| } else if (user is HInvokeDynamic) { | |
| if (user.isCallOnInterceptor(_closedWorld) && | |
| node == user.inputs[0] && | |
| useCount(user, node) == 1) { | |
| finishInvoke(user, user.selector); | |
| } | |
| } else if (user is HInvokeSuper) { | |
| if (user.isCallOnInterceptor(_closedWorld) && | |
| node == user.inputs[0] && | |
| useCount(user, node) == 1) { | |
| finishInvoke(user, user.selector); | |
| } | |
| } else { | |
| // TODO(sra): Are there other paired uses of the receiver and | |
| // interceptor where we can make use of a strengthened receiver? | |
| } | |
| } | |
| } | |
| bool visitOneShotInterceptor(HOneShotInterceptor node) { | |
| // 'Undo' the one-shot transformation if the receiver has a constant | |
| // interceptor. | |
| HInstruction constant = | |
| tryComputeConstantInterceptor(node.inputs[1], node.interceptedClasses); | |
| if (constant == null) return false; | |
| Selector selector = node.selector; | |
| AbstractValue mask = node.mask; | |
| HInstruction instruction; | |
| if (selector.isGetter) { | |
| instruction = new HInvokeDynamicGetter( | |
| selector, | |
| mask, | |
| node.element, | |
| <HInstruction>[constant, node.inputs[1]], | |
| true, | |
| node.instructionType, | |
| node.sourceInformation); | |
| } else if (selector.isSetter) { | |
| instruction = new HInvokeDynamicSetter( | |
| selector, | |
| mask, | |
| node.element, | |
| <HInstruction>[constant, node.inputs[1], node.inputs[2]], | |
| true, | |
| node.instructionType, | |
| node.sourceInformation); | |
| } else { | |
| List<HInstruction> inputs = new List<HInstruction>.from(node.inputs); | |
| inputs[0] = constant; | |
| instruction = new HInvokeDynamicMethod(selector, mask, inputs, | |
| node.instructionType, node.typeArguments, node.sourceInformation, | |
| isIntercepted: true); | |
| } | |
| HBasicBlock block = node.block; | |
| block.addAfter(node, instruction); | |
| block.rewrite(node, instruction); | |
| return true; | |
| } | |
| } |