| // Copyright (c) 2012, 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 '../elements/entities.dart'; |
| import '../options.dart'; |
| import '../types/abstract_value_domain.dart'; |
| import '../types/types.dart'; |
| import '../universe/selector.dart' show Selector; |
| import '../world.dart' show JClosedWorld; |
| import 'nodes.dart'; |
| import 'optimize.dart'; |
| |
| /// Type propagation and conditioning check insertion. |
| /// |
| /// 1. Type propagation (dataflow) to determine the types of all nodes. |
| /// |
| /// 2. HTypeKnown node insertion captures type strengthening. |
| /// |
| /// 3. Conditioning check insertion inserts receiver and argument checks on |
| /// calls where that call is expected to be replaced with an instruction with |
| /// a narrower domain. For example `{Null,int} + {int}` would insert an |
| /// receiver check to strengthen the types to `{int} + {int}` to allow the |
| /// call of `operator+` to be replaced with a HAdd instruction. |
| /// |
| /// Analysis and node insertion are done together, since insertion improves the |
| /// type propagation results. |
| // TODO(sra): The InvokeDynamicSpecializer should be consulted for better |
| // targeted conditioning checks. |
| class SsaTypePropagator extends HBaseVisitor implements OptimizationPhase { |
| final Map<int, HInstruction> workmap = new Map<int, HInstruction>(); |
| final List<int> worklist = new List<int>(); |
| final Map<HInstruction, Function> pendingOptimizations = |
| new Map<HInstruction, Function>(); |
| |
| final GlobalTypeInferenceResults results; |
| final CompilerOptions options; |
| final CommonElements commonElements; |
| final JClosedWorld closedWorld; |
| String get name => 'SsaTypePropagator'; |
| |
| SsaTypePropagator( |
| this.results, this.options, this.commonElements, this.closedWorld); |
| |
| AbstractValueDomain get abstractValueDomain => |
| closedWorld.abstractValueDomain; |
| |
| AbstractValue computeType(HInstruction instruction) { |
| return instruction.accept(this); |
| } |
| |
| // Re-compute and update the type of the instruction. Returns |
| // whether or not the type was changed. |
| bool updateType(HInstruction instruction) { |
| // Compute old and new types. |
| AbstractValue oldType = instruction.instructionType; |
| AbstractValue newType = computeType(instruction); |
| assert(newType != null); |
| // We unconditionally replace the propagated type with the new type. The |
| // computeType must make sure that we eventually reach a stable state. |
| instruction.instructionType = newType; |
| return oldType != newType; |
| } |
| |
| void visitGraph(HGraph graph) { |
| visitDominatorTree(graph); |
| processWorklist(); |
| } |
| |
| visitBasicBlock(HBasicBlock block) { |
| if (block.isLoopHeader()) { |
| block.forEachPhi((HPhi phi) { |
| // Set the initial type for the phi. We're not using the type |
| // the phi thinks it has because new optimizations may imply |
| // changing it. |
| // In theory we would need to mark |
| // the type of all other incoming edges as "uninitialized" and take this |
| // into account when doing the propagation inside the phis. Just |
| // setting the propagated type is however easier. |
| phi.instructionType = phi.inputs[0].instructionType; |
| addToWorkList(phi); |
| }); |
| } else { |
| block.forEachPhi((HPhi phi) { |
| if (updateType(phi)) { |
| addDependentInstructionsToWorkList(phi); |
| } |
| }); |
| } |
| |
| HInstruction instruction = block.first; |
| while (instruction != null) { |
| if (updateType(instruction)) { |
| addDependentInstructionsToWorkList(instruction); |
| } |
| instruction = instruction.next; |
| } |
| } |
| |
| void processWorklist() { |
| do { |
| while (!worklist.isEmpty) { |
| int id = worklist.removeLast(); |
| HInstruction instruction = workmap[id]; |
| assert(instruction != null); |
| workmap.remove(id); |
| if (updateType(instruction)) { |
| addDependentInstructionsToWorkList(instruction); |
| } |
| } |
| // While processing the optimizable arithmetic instructions, we |
| // may discover better type information for dominated users of |
| // replaced operands, so we may need to take another stab at |
| // emptying the worklist afterwards. |
| processPendingOptimizations(); |
| } while (!worklist.isEmpty); |
| } |
| |
| void addToWorkList(HInstruction instruction) { |
| final int id = instruction.id; |
| |
| if (!workmap.containsKey(id)) { |
| worklist.add(id); |
| workmap[id] = instruction; |
| } |
| } |
| |
| AbstractValue visitBinaryArithmetic(HBinaryArithmetic instruction) { |
| HInstruction left = instruction.left; |
| HInstruction right = instruction.right; |
| if (left.isInteger(abstractValueDomain) && |
| right.isInteger(abstractValueDomain)) { |
| return abstractValueDomain.intType; |
| } |
| if (left.isDouble(abstractValueDomain)) { |
| return abstractValueDomain.doubleType; |
| } |
| return abstractValueDomain.numType; |
| } |
| |
| AbstractValue checkPositiveInteger(HBinaryArithmetic instruction) { |
| HInstruction left = instruction.left; |
| HInstruction right = instruction.right; |
| if (left.isPositiveInteger(abstractValueDomain) && |
| right.isPositiveInteger(abstractValueDomain)) { |
| return abstractValueDomain.positiveIntType; |
| } |
| return visitBinaryArithmetic(instruction); |
| } |
| |
| AbstractValue visitMultiply(HMultiply instruction) { |
| return checkPositiveInteger(instruction); |
| } |
| |
| AbstractValue visitAdd(HAdd instruction) { |
| return checkPositiveInteger(instruction); |
| } |
| |
| AbstractValue visitDivide(HDivide instruction) { |
| // Always double, as initialized. |
| return instruction.instructionType; |
| } |
| |
| AbstractValue visitTruncatingDivide(HTruncatingDivide instruction) { |
| // Always as initialized. |
| return instruction.instructionType; |
| } |
| |
| AbstractValue visitRemainder(HRemainder instruction) { |
| // Always as initialized. |
| return instruction.instructionType; |
| } |
| |
| AbstractValue visitNegate(HNegate instruction) { |
| HInstruction operand = instruction.operand; |
| // We have integer subclasses that represent ranges, so widen any int |
| // subclass to full integer. |
| if (operand.isInteger(abstractValueDomain)) { |
| return abstractValueDomain.intType; |
| } |
| return instruction.operand.instructionType; |
| } |
| |
| AbstractValue visitAbs(HAbs instruction) { |
| // TODO(sra): Can narrow to non-negative type for integers. |
| return instruction.operand.instructionType; |
| } |
| |
| AbstractValue visitInstruction(HInstruction instruction) { |
| assert(instruction.instructionType != null); |
| return instruction.instructionType; |
| } |
| |
| AbstractValue visitPhi(HPhi phi) { |
| AbstractValue candidateType = abstractValueDomain.emptyType; |
| for (int i = 0, length = phi.inputs.length; i < length; i++) { |
| AbstractValue inputType = phi.inputs[i].instructionType; |
| candidateType = abstractValueDomain.union(candidateType, inputType); |
| } |
| return candidateType; |
| } |
| |
| AbstractValue visitTypeConversion(HTypeConversion instruction) { |
| HInstruction input = instruction.checkedInput; |
| AbstractValue inputType = input.instructionType; |
| AbstractValue checkedType = instruction.checkedType; |
| if (instruction.isArgumentTypeCheck || instruction.isReceiverTypeCheck) { |
| // We must make sure a type conversion for receiver or argument check |
| // does not try to do an int check, because an int check is not enough. |
| // We only do an int check if the input is integer or null. |
| if (abstractValueDomain.isNumberOrNull(checkedType) && |
| !abstractValueDomain.isDoubleOrNull(checkedType) && |
| input.isIntegerOrNull(abstractValueDomain)) { |
| instruction.checkedType = abstractValueDomain.intType; |
| } else if (abstractValueDomain.isIntegerOrNull(checkedType) && |
| !input.isIntegerOrNull(abstractValueDomain)) { |
| instruction.checkedType = abstractValueDomain.numType; |
| } |
| } |
| |
| AbstractValue outputType = |
| abstractValueDomain.intersection(checkedType, inputType); |
| if (abstractValueDomain.isEmpty(outputType)) { |
| // Intersection of double and integer conflicts (is empty), but JS numbers |
| // can be both int and double at the same time. For example, the input |
| // can be a literal double '8.0' that is marked as an integer (because 'is |
| // int' will return 'true'). What we really need to do is make the |
| // overlap between int and double values explicit in the TypeMask system. |
| if (abstractValueDomain.isIntegerOrNull(inputType) && |
| abstractValueDomain.isDoubleOrNull(checkedType)) { |
| if (abstractValueDomain.canBeNull(inputType) && |
| abstractValueDomain.canBeNull(checkedType)) { |
| outputType = |
| abstractValueDomain.includeNull(abstractValueDomain.doubleType); |
| } else { |
| outputType = abstractValueDomain.doubleType; |
| } |
| } |
| } |
| if (inputType != outputType) { |
| // Replace dominated uses of input with uses of this HTypeConversion so |
| // the uses benefit from the stronger type. |
| // |
| // The dependency on the checked value also improves the generated |
| // JavaScript. Many checks are compiled to a function call expression that |
| // returns the checked result, so the check can be generated as a |
| // subexpression rather than a separate statement. |
| // |
| // Do not replace local accesses, since the local must be a HLocalValue, |
| // not a HTypeConversion. |
| if (!(input is HParameterValue && input.usedAsVariable())) { |
| input.replaceAllUsersDominatedBy(instruction.next, instruction); |
| } |
| } |
| return outputType; |
| } |
| |
| AbstractValue visitTypeKnown(HTypeKnown instruction) { |
| HInstruction input = instruction.checkedInput; |
| AbstractValue inputType = input.instructionType; |
| AbstractValue outputType = |
| abstractValueDomain.intersection(instruction.knownType, inputType); |
| if (inputType != outputType) { |
| input.replaceAllUsersDominatedBy(instruction.next, instruction); |
| } |
| return outputType; |
| } |
| |
| void convertInput(HInvokeDynamic instruction, HInstruction input, |
| AbstractValue type, int kind) { |
| Selector selector = (kind == HTypeConversion.RECEIVER_TYPE_CHECK) |
| ? instruction.selector |
| : null; |
| HTypeConversion converted = new HTypeConversion( |
| null, kind, type, input, instruction.sourceInformation, |
| receiverTypeCheckSelector: selector); |
| instruction.block.addBefore(instruction, converted); |
| input.replaceAllUsersDominatedBy(instruction, converted); |
| } |
| |
| bool isCheckEnoughForNsmOrAe(HInstruction instruction, AbstractValue type) { |
| // In some cases, we want the receiver to be an integer, |
| // but that does not mean we will get a NoSuchMethodError |
| // if it's not: the receiver could be a double. |
| if (abstractValueDomain.isIntegerOrNull(type)) { |
| // If the instruction's type is integer or null, the codegen |
| // will emit a null check, which is enough to know if it will |
| // hit a noSuchMethod. |
| return instruction.isIntegerOrNull(abstractValueDomain); |
| } |
| return true; |
| } |
| |
| // Add a receiver type check when the call can only hit |
| // [noSuchMethod] if the receiver is not of a specific type. |
| // Return true if the receiver type check was added. |
| bool checkReceiver(HInvokeDynamic instruction) { |
| assert(instruction.isInterceptedCall); |
| HInstruction receiver = instruction.inputs[1]; |
| if (receiver.isNumber(abstractValueDomain)) return false; |
| if (receiver.isNumberOrNull(abstractValueDomain)) { |
| convertInput( |
| instruction, |
| receiver, |
| abstractValueDomain.excludeNull(receiver.instructionType), |
| HTypeConversion.RECEIVER_TYPE_CHECK); |
| return true; |
| } else if (instruction.element == null) { |
| if (closedWorld.includesClosureCall( |
| instruction.selector, instruction.mask)) { |
| return false; |
| } |
| Iterable<MemberEntity> targets = |
| closedWorld.locateMembers(instruction.selector, instruction.mask); |
| if (targets.length == 1) { |
| MemberEntity target = targets.first; |
| ClassEntity cls = target.enclosingClass; |
| AbstractValue type = abstractValueDomain.createNonNullSubclass(cls); |
| // We currently only optimize on some primitive types. |
| if (!abstractValueDomain.isNumberOrNull(type) && |
| !abstractValueDomain.isBooleanOrNull(type)) { |
| return false; |
| } |
| if (!isCheckEnoughForNsmOrAe(receiver, type)) return false; |
| instruction.element = target; |
| convertInput( |
| instruction, receiver, type, HTypeConversion.RECEIVER_TYPE_CHECK); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Add an argument type check if the argument is not of a type |
| // expected by the call. |
| // Return true if the argument type check was added. |
| bool checkArgument(HInvokeDynamic instruction) { |
| HInstruction left = instruction.inputs[1]; |
| HInstruction right = instruction.inputs[2]; |
| |
| Selector selector = instruction.selector; |
| if (selector.isOperator && left.isNumber(abstractValueDomain)) { |
| if (right.isNumber(abstractValueDomain)) return false; |
| AbstractValue type = right.isIntegerOrNull(abstractValueDomain) |
| ? abstractValueDomain.excludeNull(right.instructionType) |
| : abstractValueDomain.numType; |
| // TODO(ngeoffray): Some number operations don't have a builtin |
| // variant and will do the check in their method anyway. We |
| // still add a check because it allows to GVN these operations, |
| // but we should find a better way. |
| convertInput( |
| instruction, right, type, HTypeConversion.ARGUMENT_TYPE_CHECK); |
| return true; |
| } |
| return false; |
| } |
| |
| void processPendingOptimizations() { |
| pendingOptimizations.forEach((instruction, action) => action()); |
| pendingOptimizations.clear(); |
| } |
| |
| void addDependentInstructionsToWorkList(HInstruction instruction) { |
| for (int i = 0, length = instruction.usedBy.length; i < length; i++) { |
| // The type propagator only propagates types forward. We |
| // thus only need to add the users of the [instruction] to the list. |
| addToWorkList(instruction.usedBy[i]); |
| } |
| } |
| |
| void addAllUsersBut(HInvokeDynamic invoke, HInstruction instruction) { |
| instruction.usedBy.forEach((HInstruction user) { |
| if (user != invoke) addToWorkList(user); |
| }); |
| } |
| |
| AbstractValue visitInvokeDynamic(HInvokeDynamic instruction) { |
| if (instruction.isInterceptedCall) { |
| // We cannot do the following optimization now, because we have to wait |
| // for the type propagation to be stable. The receiver of [instruction] |
| // might move from number to dynamic. |
| void checkInputs() { |
| Selector selector = instruction.selector; |
| if (selector.isOperator && selector.name != '==') { |
| if (checkReceiver(instruction)) { |
| addAllUsersBut(instruction, instruction.inputs[1]); |
| } |
| if (!selector.isUnaryOperator && checkArgument(instruction)) { |
| addAllUsersBut(instruction, instruction.inputs[2]); |
| } |
| } else if (selector.isCall) { |
| if (selector.name == 'abs' && selector.argumentCount == 0) { |
| if (checkReceiver(instruction)) { |
| addAllUsersBut(instruction, instruction.inputs[1]); |
| } |
| } |
| } |
| } |
| |
| pendingOptimizations.putIfAbsent(instruction, () => checkInputs); |
| } |
| |
| HInstruction receiver = instruction.getDartReceiver(closedWorld); |
| AbstractValue receiverType = receiver.instructionType; |
| instruction.mask = receiverType; |
| |
| // Try to specialize the receiver after this call by inserting a refinement |
| // node (HTypeKnown). There are two potentially expensive tests - are there |
| // any uses of the receiver dominated by and following this call?, and what |
| // is the refined type? The first is expensive if the receiver has many |
| // uses, the second is expensive if many classes implement the selector. So |
| // we try to do the least expensive test first. |
| const int _MAX_QUICK_USERS = 50; |
| if (!instruction.selector.isClosureCall) { |
| AbstractValue newType; |
| AbstractValue computeNewType() { |
| newType = closedWorld.computeReceiverType( |
| instruction.selector, instruction.mask); |
| newType = abstractValueDomain.intersection(newType, receiverType); |
| return newType; |
| } |
| |
| var next = instruction.next; |
| if (next is HTypeKnown && next.checkedInput == receiver) { |
| // On a previous pass or iteration we already refined [receiver] by |
| // inserting a [HTypeKnown] instruction. That replaced several dominated |
| // uses with the refinement. We update the type of the [HTypeKnown] |
| // instruction because it may have been refined with a correct type at |
| // the time, but incorrect now. |
| if (next.instructionType != computeNewType()) { |
| next.knownType = next.instructionType = newType; |
| addDependentInstructionsToWorkList(next); |
| } |
| } else { |
| DominatedUses uses; |
| bool hasCandidates() { |
| uses = |
| DominatedUses.of(receiver, instruction, excludeDominator: true); |
| return uses.isNotEmpty; |
| } |
| |
| if ((receiver.usedBy.length <= _MAX_QUICK_USERS) |
| ? (hasCandidates() && computeNewType() != receiverType) |
| : (computeNewType() != receiverType && hasCandidates())) { |
| // Insert a refinement node after the call and update all users |
| // dominated by the call to use that node instead of [receiver]. |
| HTypeKnown converted = |
| new HTypeKnown.witnessed(newType, receiver, instruction); |
| instruction.block.addBefore(instruction.next, converted); |
| uses.replaceWith(converted); |
| addDependentInstructionsToWorkList(converted); |
| } |
| } |
| } |
| |
| return instruction.specializer |
| .computeTypeFromInputTypes(instruction, results, options, closedWorld); |
| } |
| } |