| // 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. |
| |
| part of ssa; |
| |
| class SsaTypePropagator extends HGraphVisitor implements OptimizationPhase { |
| |
| final Map<int, HInstruction> workmap; |
| final List<int> worklist; |
| final Map<HInstruction, Function> pendingOptimizations; |
| final HTypeMap types; |
| |
| final Compiler compiler; |
| String get name => 'type propagator'; |
| |
| SsaTypePropagator(this.compiler, this.types) |
| : workmap = new Map<int, HInstruction>(), |
| worklist = new List<int>(), |
| pendingOptimizations = new Map<HInstruction, Function>(); |
| |
| HType computeType(HInstruction instruction) { |
| if (instruction.hasGuaranteedType()) return instruction.guaranteedType; |
| return instruction.computeTypeFromInputTypes(types, compiler); |
| } |
| |
| // Re-compute and update the type of the instruction. Returns |
| // whether or not the type was changed. |
| bool updateType(HInstruction instruction) { |
| // The [updateType] method is invoked when one of the inputs of |
| // the instruction changes its type. That gives us a new |
| // opportunity to consider this instruction for optimizations. |
| considerForArgumentTypeOptimization(instruction); |
| // Compute old and new types. |
| HType oldType = types[instruction]; |
| HType newType = computeType(instruction); |
| // We unconditionally replace the propagated type with the new type. The |
| // computeType must make sure that we eventually reach a stable state. |
| types[instruction] = newType; |
| return oldType != newType; |
| } |
| |
| void considerForArgumentTypeOptimization(HInstruction instruction) { |
| if (instruction is !HBinaryArithmetic) return; |
| // Update the pending optimizations map based on the potentially |
| // new types of the operands. If the operand types no longer allow |
| // us to optimize, we remove the pending optimization. |
| HBinaryArithmetic arithmetic = instruction; |
| HInstruction left = arithmetic.left; |
| HInstruction right = arithmetic.right; |
| if (left.isNumber(types) && !right.isNumber(types)) { |
| pendingOptimizations[instruction] = () { |
| // This callback function is invoked after we're done |
| // propagating types. The types shouldn't have changed. |
| assert(left.isNumber(types) && !right.isNumber(types)); |
| convertInput(instruction, right, HType.NUMBER); |
| }; |
| } else { |
| pendingOptimizations.remove(instruction); |
| } |
| } |
| |
| 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 "unitialized" and take this |
| // into account when doing the propagation inside the phis. Just |
| // setting the propagated type is however easier. |
| types[phi] = types[phi.inputs[0]]; |
| 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 addDependentInstructionsToWorkList(HInstruction instruction) { |
| for (int i = 0, length = instruction.usedBy.length; i < length; i++) { |
| // The non-speculative 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 addToWorkList(HInstruction instruction) { |
| final int id = instruction.id; |
| if (!workmap.containsKey(id)) { |
| worklist.add(id); |
| workmap[id] = instruction; |
| } |
| } |
| |
| void processPendingOptimizations() { |
| pendingOptimizations.forEach((instruction, action) => action()); |
| pendingOptimizations.clear(); |
| } |
| |
| void convertInput(HInstruction instruction, HInstruction input, HType type) { |
| HTypeConversion converted = |
| new HTypeConversion.argumentTypeCheck(type, input); |
| instruction.block.addBefore(instruction, converted); |
| Set<HInstruction> dominatedUsers = input.dominatedUsers(instruction); |
| for (HInstruction user in dominatedUsers) { |
| user.changeUse(input, converted); |
| addToWorkList(user); |
| } |
| } |
| } |
| |
| class SsaSpeculativeTypePropagator extends SsaTypePropagator { |
| final String name = 'speculative type propagator'; |
| SsaSpeculativeTypePropagator(Compiler compiler, HTypeMap types) |
| : super(compiler, types); |
| |
| void addDependentInstructionsToWorkList(HInstruction instruction) { |
| // The speculative type propagator propagates types forward and backward. |
| // Not only do we need to add the users of the [instruction] to the list. |
| // We also need to add the inputs fo the [instruction], since they might |
| // want to propagate the desired outgoing type. |
| for (int i = 0, length = instruction.usedBy.length; i < length; i++) { |
| addToWorkList(instruction.usedBy[i]); |
| } |
| for (int i = 0, length = instruction.inputs.length; i < length; i++) { |
| addToWorkList(instruction.inputs[i]); |
| } |
| } |
| |
| HType computeDesiredType(HInstruction instruction) { |
| HType desiredType = HType.UNKNOWN; |
| for (final user in instruction.usedBy) { |
| HType userType = |
| user.computeDesiredTypeForInput(instruction, types, compiler); |
| // Mainly due to the "if (true)" added by hackAroundPossiblyAbortingBody |
| // in builder.dart uninitialized variables will propagate a type of null |
| // which will result in a conflicting type when combined with a primitive |
| // type. Avoid this to improve generated code. |
| // TODO(sgjesse): Reconcider this when hackAroundPossiblyAbortingBody |
| // has been removed. |
| if (desiredType.isPrimitive() && userType == HType.NULL) continue; |
| desiredType = desiredType.intersection(userType, compiler); |
| // No need to continue if two users disagree on the type. |
| if (desiredType.isConflicting()) break; |
| } |
| return desiredType; |
| } |
| |
| HType computeType(HInstruction instruction) { |
| // Once we are in a conflicting state don't update the type anymore. |
| HType oldType = types[instruction]; |
| if (oldType.isConflicting()) return oldType; |
| |
| HType newType = super.computeType(instruction); |
| // [computeDesiredType] goes to all usedBys and lets them compute their |
| // desired type. By setting the [newType] here we give them more context to |
| // work with. |
| types[instruction] = newType; |
| HType desiredType = computeDesiredType(instruction); |
| // If the desired type is conflicting just return the computed type. |
| if (desiredType.isConflicting()) return newType; |
| // TODO(ngeoffray): Allow speculative optimizations on |
| // non-primitive types? |
| if (!desiredType.isPrimitive()) return newType; |
| return newType.intersection(desiredType, compiler); |
| } |
| |
| // Do not use speculative argument type optimization for now. |
| void considerForArgumentTypeOptimization(HInstruction instruction) { } |
| |
| } |