| // 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.bounds_checker; |
| |
| import 'cps_ir_nodes.dart'; |
| import 'optimizers.dart' show Pass; |
| import 'octagon.dart'; |
| import '../constants/values.dart'; |
| import 'cps_fragment.dart'; |
| import 'type_mask_system.dart'; |
| import '../types/types.dart'; |
| import '../world.dart'; |
| import '../elements/elements.dart'; |
| import 'loop_effects.dart'; |
| |
| /// Eliminates bounds checks when they can be proven safe. |
| /// |
| /// In general, this pass will try to eliminate any branch with arithmetic |
| /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc. |
| /// |
| /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon |
| /// analyzers, we do not use a closed matrix representation, but just maintain |
| /// a bucket of constraints. Constraints can therefore be added and removed |
| /// on-the-fly without significant overhead. |
| /// |
| /// We never copy the constraint system. While traversing the IR, the |
| /// constraint system is mutated to take into account the knowledge that is |
| /// valid for the current location. Constraints are added when entering a |
| /// branch, for instance, and removed again after the branch has been processed. |
| /// |
| /// Loops are analyzed in two passes. The first pass establishes monotonicity |
| /// of loop variables, which the second pass uses to compute upper/lower bounds. |
| /// |
| /// The two-pass scheme is suboptimal compared to a least fixed-point |
| /// computation, but does not require repeated iteration. Repeated iteration |
| /// would be expensive, since we cannot perform a sparse analysis with our |
| /// mutable octagon representation. |
| class BoundsChecker extends TrampolineRecursiveVisitor implements Pass { |
| String get passName => 'Bounds checker'; |
| |
| static const int MAX_UINT32 = (1 << 32) - 1; |
| |
| /// All integers of this magnitude or less are representable as JS numbers. |
| static const int MAX_SAFE_INT = (1 << 53) - 1; |
| |
| /// Marker to indicate that a continuation should get a unique effect number. |
| static const int NEW_EFFECT = -1; |
| |
| final TypeMaskSystem types; |
| final World world; |
| |
| /// Fields for the constraint system and its variables. |
| final Octagon octagon = new Octagon(); |
| final Map<Primitive, SignedVariable> valueOf = {}; |
| final Map<Primitive, Map<int, SignedVariable>> lengthOf = {}; |
| |
| /// Fields for the two-pass handling of loops. |
| final Map<Parameter, Monotonicity> monotonicity = <Parameter, Monotonicity>{}; |
| bool isStrongLoopPass; |
| bool foundLoop = false; |
| |
| /// Fields for tracking side effects. |
| /// |
| /// The IR is divided into regions wherein the lengths of indexable objects |
| /// are known not to change. Regions are identified by their "effect number". |
| LoopSideEffects loopEffects; |
| final Map<Continuation, int> effectNumberAt = <Continuation, int>{}; |
| int currentEffectNumber = 0; |
| int effectNumberCounter = 0; |
| |
| BoundsChecker(this.types, this.world); |
| |
| void rewrite(FunctionDefinition node) { |
| loopEffects = new LoopSideEffects(node, world); |
| isStrongLoopPass = false; |
| visit(node); |
| if (foundLoop) { |
| isStrongLoopPass = true; |
| effectNumberAt.clear(); |
| visit(node); |
| } |
| } |
| |
| // ------------- VARIABLES ----------------- |
| |
| int makeNewEffect() => ++effectNumberCounter; |
| |
| bool isInt(Primitive prim) { |
| return types.isDefinitelyInt(prim.type); |
| } |
| |
| bool isUInt32(Primitive prim) { |
| return types.isDefinitelyUint32(prim.type); |
| } |
| |
| bool isNonNegativeInt(Primitive prim) { |
| return types.isDefinitelyNonNegativeInt(prim.type); |
| } |
| |
| /// Get a constraint variable representing the numeric value of [number]. |
| SignedVariable getValue(Primitive number) { |
| number = number.effectiveDefinition; |
| int min, max; |
| if (isUInt32(number)) { |
| min = 0; |
| max = MAX_UINT32; |
| } else if (isNonNegativeInt(number)) { |
| min = 0; |
| } |
| return valueOf.putIfAbsent(number, () => octagon.makeVariable(min, max)); |
| } |
| |
| /// Get a constraint variable representing the length of [indexableObject] at |
| /// program locations with the given [effectNumber]. |
| SignedVariable getLength(Primitive indexableObject, int effectNumber) { |
| indexableObject = indexableObject.effectiveDefinition; |
| TypeMask type = indexableObject.type.nonNullable(); |
| if (types.isDefinitelyFixedLengthIndexable(type)) { |
| // Always use the same effect number if the length is immutable. |
| effectNumber = 0; |
| } |
| return lengthOf |
| .putIfAbsent(indexableObject, () => <int, SignedVariable>{}) |
| .putIfAbsent(effectNumber, () { |
| int length = types.getContainerLength(type); |
| if (length != null) { |
| return octagon.makeVariable(length, length); |
| } else { |
| return octagon.makeVariable(0, MAX_UINT32); |
| } |
| }); |
| } |
| |
| // ------------- CONSTRAINT HELPERS ----------------- |
| |
| /// Puts the given constraint "in scope" by adding it to the octagon, and |
| /// pushing a stack action that will remove it again. |
| void applyConstraint(SignedVariable v1, SignedVariable v2, int k) { |
| Constraint constraint = new Constraint(v1, v2, k); |
| octagon.pushConstraint(constraint); |
| pushAction(() => octagon.popConstraint(constraint)); |
| } |
| |
| /// Return true if we can prove that `v1 + v2 <= k`. |
| bool testConstraint(SignedVariable v1, SignedVariable v2, int k) { |
| // Add the negated constraint and check for solvability. |
| // !(v1 + v2 <= k) <==> -v1 - v2 <= -k-1 |
| Constraint constraint = new Constraint(v1.negated, v2.negated, -k - 1); |
| octagon.pushConstraint(constraint); |
| bool answer = octagon.isUnsolvable; |
| octagon.popConstraint(constraint); |
| return answer; |
| } |
| |
| void makeLessThanOrEqual(SignedVariable v1, SignedVariable v2) { |
| // v1 <= v2 <==> v1 - v2 <= 0 |
| applyConstraint(v1, v2.negated, 0); |
| } |
| |
| void makeLessThan(SignedVariable v1, SignedVariable v2) { |
| // v1 < v2 <==> v1 - v2 <= -1 |
| applyConstraint(v1, v2.negated, -1); |
| } |
| |
| void makeGreaterThanOrEqual(SignedVariable v1, SignedVariable v2) { |
| // v1 >= v2 <==> v2 - v1 <= 0 |
| applyConstraint(v2, v1.negated, 0); |
| } |
| |
| void makeGreaterThan(SignedVariable v1, SignedVariable v2) { |
| // v1 > v2 <==> v2 - v1 <= -1 |
| applyConstraint(v2, v1.negated, -1); |
| } |
| |
| void makeLessThanOrEqualToConstant(SignedVariable v1, int k) { |
| // v1 + v1 <= 2k |
| applyConstraint(v1, v1, 2 * k); |
| } |
| |
| void makeGreaterThanOrEqualToConstant(SignedVariable v1, int k) { |
| // -v1 - v1 <= -2k |
| applyConstraint(v1.negated, v1.negated, -2 * k); |
| } |
| |
| void makeConstant(SignedVariable v1, int k) { |
| // We model this using the constraints: |
| // v1 + v1 <= 2k |
| // -v1 - v1 <= -2k |
| applyConstraint(v1, v1, 2 * k); |
| applyConstraint(v1.negated, v1.negated, -2 * k); |
| } |
| |
| /// Make `v1 = v2 + k`. |
| void makeExactSum(SignedVariable v1, SignedVariable v2, int k) { |
| applyConstraint(v1, v2.negated, k); |
| applyConstraint(v1.negated, v2, -k); |
| } |
| |
| /// Make `v1 = v2 [+] k` where [+] represents floating-point addition. |
| void makeFloatingPointSum(SignedVariable v1, SignedVariable v2, int k) { |
| if (isDefinitelyLessThanOrEqualToConstant(v2, MAX_SAFE_INT - k) && |
| isDefinitelyGreaterThanOrEqualToConstant(v2, -MAX_SAFE_INT + k)) { |
| // The result is known to be in the 53-bit range, so no rounding occurs. |
| makeExactSum(v1, v2, k); |
| } else { |
| // A rounding error may occur, so the result may not be exactly v2 + k. |
| // We can still add monotonicity constraints: |
| // adding a positive number cannot return a lesser number |
| // adding a negative number cannot return a greater number |
| if (k >= 0) { |
| // v1 >= v2 <==> v2 - v1 <= 0 <==> -v1 + v2 <= 0 |
| applyConstraint(v1.negated, v2, 0); |
| } else { |
| // v1 <= v2 <==> v1 - v2 <= 0 |
| applyConstraint(v1, v2.negated, 0); |
| } |
| } |
| } |
| |
| void makeEqual(SignedVariable v1, SignedVariable v2) { |
| // We model this using the constraints: |
| // v1 <= v2 <==> v1 - v2 <= 0 |
| // v1 >= v2 <==> v2 - v1 <= 0 |
| applyConstraint(v1, v2.negated, 0); |
| applyConstraint(v2, v1.negated, 0); |
| } |
| |
| void makeNotEqual(SignedVariable v1, SignedVariable v2) { |
| // The octagon cannot represent non-equality, but we can sharpen a weak |
| // inequality to a sharp one. If v1 and v2 are already known to be equal, |
| // this will create a contradiction and eliminate a dead branch. |
| // This is necessary for eliminating concurrent modification checks. |
| if (isDefinitelyLessThanOrEqualTo(v1, v2)) { |
| makeLessThan(v1, v2); |
| } else if (isDefinitelyGreaterThanOrEqualTo(v1, v2)) { |
| makeGreaterThan(v1, v2); |
| } |
| } |
| |
| /// Return true if we can prove that `v1 <= v2`. |
| bool isDefinitelyLessThanOrEqualTo(SignedVariable v1, SignedVariable v2) { |
| return testConstraint(v1, v2.negated, 0); |
| } |
| |
| /// Return true if we can prove that `v1 < v2`. |
| bool isDefinitelyLessThan(SignedVariable v1, SignedVariable v2) { |
| return testConstraint(v1, v2.negated, -1); |
| } |
| |
| /// Return true if we can prove that `v1 >= v2`. |
| bool isDefinitelyGreaterThanOrEqualTo(SignedVariable v1, SignedVariable v2) { |
| return testConstraint(v2, v1.negated, 0); |
| } |
| |
| bool isDefinitelyLessThanOrEqualToConstant(SignedVariable v1, int value) { |
| // v1 <= value <==> v1 + v1 <= 2 * value |
| return testConstraint(v1, v1, 2 * value); |
| } |
| |
| bool isDefinitelyGreaterThanOrEqualToConstant(SignedVariable v1, int value) { |
| // v1 >= value <==> -v1 - v1 <= -2 * value |
| return testConstraint(v1.negated, v1.negated, -2 * value); |
| } |
| |
| // ------------- TAIL EXPRESSIONS ----------------- |
| |
| @override |
| void visitBranch(Branch node) { |
| Primitive condition = node.condition.definition; |
| Continuation trueCont = node.trueContinuation.definition; |
| Continuation falseCont = node.falseContinuation.definition; |
| effectNumberAt[trueCont] = currentEffectNumber; |
| effectNumberAt[falseCont] = currentEffectNumber; |
| pushAction(() { |
| // If the branching condition is known statically, either or both of the |
| // branch continuations will be replaced by Unreachable. Clean up the |
| // branch afterwards. |
| if (trueCont.body is Unreachable && falseCont.body is Unreachable) { |
| destroyAndReplace(node, new Unreachable()); |
| } else if (trueCont.body is Unreachable) { |
| destroyAndReplace( |
| node, new InvokeContinuation(falseCont, <Parameter>[])); |
| } else if (falseCont.body is Unreachable) { |
| destroyAndReplace( |
| node, new InvokeContinuation(trueCont, <Parameter>[])); |
| } |
| }); |
| void pushTrue(makeConstraint()) { |
| pushAction(() { |
| makeConstraint(); |
| push(trueCont); |
| }); |
| } |
| void pushFalse(makeConstraint()) { |
| pushAction(() { |
| makeConstraint(); |
| push(falseCont); |
| }); |
| } |
| if (condition is ApplyBuiltinOperator && |
| condition.arguments.length == 2 && |
| isInt(condition.arguments[0].definition) && |
| isInt(condition.arguments[1].definition)) { |
| SignedVariable v1 = getValue(condition.arguments[0].definition); |
| SignedVariable v2 = getValue(condition.arguments[1].definition); |
| switch (condition.operator) { |
| case BuiltinOperator.NumLe: |
| pushTrue(() => makeLessThanOrEqual(v1, v2)); |
| pushFalse(() => makeGreaterThan(v1, v2)); |
| return; |
| case BuiltinOperator.NumLt: |
| pushTrue(() => makeLessThan(v1, v2)); |
| pushFalse(() => makeGreaterThanOrEqual(v1, v2)); |
| return; |
| case BuiltinOperator.NumGe: |
| pushTrue(() => makeGreaterThanOrEqual(v1, v2)); |
| pushFalse(() => makeLessThan(v1, v2)); |
| return; |
| case BuiltinOperator.NumGt: |
| pushTrue(() => makeGreaterThan(v1, v2)); |
| pushFalse(() => makeLessThanOrEqual(v1, v2)); |
| return; |
| case BuiltinOperator.StrictEq: |
| pushTrue(() => makeEqual(v1, v2)); |
| pushFalse(() => makeNotEqual(v1, v2)); |
| return; |
| case BuiltinOperator.StrictNeq: |
| pushTrue(() => makeNotEqual(v1, v2)); |
| pushFalse(() => makeEqual(v1, v2)); |
| return; |
| default: |
| } |
| } |
| |
| push(trueCont); |
| push(falseCont); |
| } |
| |
| @override |
| void visitConstant(Constant node) { |
| // TODO(asgerf): It might be faster to inline the constant in the |
| // constraints that reference it. |
| if (node.value.isInt) { |
| IntConstantValue constant = node.value; |
| makeConstant(getValue(node), constant.primitiveValue); |
| } |
| } |
| |
| @override |
| void visitApplyBuiltinOperator(ApplyBuiltinOperator node) { |
| if (!isInt(node)) return; |
| if (node.arguments.length == 1) { |
| applyUnaryOperator(node); |
| } else if (node.arguments.length == 2) { |
| applyBinaryOperator(node); |
| } |
| } |
| |
| void applyBinaryOperator(ApplyBuiltinOperator node) { |
| Primitive left = node.arguments[0].definition; |
| Primitive right = node.arguments[1].definition; |
| if (!isInt(left) || !isInt(right)) { |
| return; |
| } |
| SignedVariable leftVar = getValue(left); |
| SignedVariable rightVar = getValue(right); |
| SignedVariable result = getValue(node); |
| switch (node.operator) { |
| case BuiltinOperator.NumAdd: |
| int leftConst = getIntConstant(left); |
| if (leftConst != null) { |
| makeFloatingPointSum(result, rightVar, leftConst); |
| } |
| int rightConst = getIntConstant(right); |
| if (rightConst != null) { |
| makeFloatingPointSum(result, leftVar, rightConst); |
| } |
| // Attempt to compute the sign of the result. |
| // TODO(asgerf): Compute upper/lower bounds instead of using 0. |
| if (testConstraint(leftVar, rightVar, 0)) { |
| makeLessThanOrEqualToConstant(result, 0); |
| } |
| if (testConstraint(leftVar.negated, rightVar.negated, 0)) { |
| makeGreaterThanOrEqualToConstant(result, 0); |
| } |
| // Classical octagon-based analyzers would compute upper and lower |
| // bounds for the two operands and add constraints for the result based |
| // on those. For performance reasons we only compute the sign |
| // TODO(asgerf): It seems expensive, but we should evaluate it. |
| break; |
| |
| case BuiltinOperator.NumSubtract: |
| int leftConst = getIntConstant(left); |
| if (leftConst != null) { |
| // result = leftConst - right = (-right) + leftConst |
| makeFloatingPointSum(result, rightVar.negated, leftConst); |
| } |
| int rightConst = getIntConstant(right); |
| if (rightConst != null) { |
| // result = left - rightConst = left + (-rightConst) |
| makeFloatingPointSum(result, leftVar, -rightConst); |
| } |
| // Attempt to compute the sign of the result. |
| if (isDefinitelyGreaterThanOrEqualTo(leftVar, rightVar)) { |
| makeGreaterThanOrEqualToConstant(result, 0); |
| } |
| if (isDefinitelyLessThanOrEqualTo(leftVar, rightVar)) { |
| makeLessThanOrEqualToConstant(result, 0); |
| } |
| break; |
| |
| case BuiltinOperator.NumTruncatingDivideToSigned32: |
| if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) { |
| // If we divide by a positive number, the result is closer to zero. |
| // If we divide by a negative number, the result is negative, and |
| // thus less than the original (non-negative) number. |
| // TODO(asgerf): The divisor is currently always positive, because |
| // type propagation checks that, but we could do better. |
| makeLessThanOrEqual(result, leftVar); |
| } |
| break; |
| |
| case BuiltinOperator.NumShr: |
| if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) { |
| makeLessThanOrEqual(result, leftVar); |
| } |
| int shiftAmount = getIntConstant(right); |
| if (shiftAmount != null) { |
| // TODO(asgerf): Compute upper bound on [leftVar] and use that |
| // instead of MAX_UINT32. |
| makeLessThanOrEqualToConstant(result, MAX_UINT32 >> shiftAmount); |
| } |
| break; |
| |
| case BuiltinOperator.NumRemainder: |
| // TODO(asgerf): This check overlaps with checks performed in a type |
| // propagation transformation, and we can do it more precisely here. |
| // Should we do the rewrite here? |
| if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) && |
| isDefinitelyGreaterThanOrEqualToConstant(rightVar, 1)) { |
| makeLessThanOrEqual(result, leftVar); |
| makeLessThan(result, rightVar); |
| } |
| break; |
| |
| case BuiltinOperator.NumAnd: |
| // We use the faster UInt32 check instead of constraint based checks |
| // here, because the common case is that one operand is a constant. |
| if (isUInt32(left)) { |
| makeLessThanOrEqual(result, leftVar); |
| } |
| if (isUInt32(right)) { |
| makeLessThanOrEqual(result, rightVar); |
| } |
| break; |
| |
| default: |
| } |
| } |
| |
| void applyUnaryOperator(ApplyBuiltinOperator node) { |
| Primitive argument = node.arguments[0].definition; |
| if (!isInt(argument)) return; |
| if (node.operator == BuiltinOperator.NumNegate) { |
| valueOf[node] = getValue(argument).negated; |
| } |
| } |
| |
| int getIntConstant(Primitive prim) { |
| if (prim is Constant && prim.value.isInt) { |
| IntConstantValue constant = prim.value; |
| return constant.primitiveValue; |
| } |
| return null; |
| } |
| |
| @override |
| void visitRefinement(Refinement node) { |
| // In general we should get the container length of the refined type and |
| // add a constraint if we know the length after the refinement. |
| // However, our current type system removes container information when a |
| // type becomes part of a union, so this cannot happen. |
| } |
| |
| @override |
| void visitGetLength(GetLength node) { |
| valueOf[node] = getLength(node.object.definition, currentEffectNumber); |
| } |
| |
| @override |
| void visitBoundsCheck(BoundsCheck node) { |
| if (node.checks == BoundsCheck.NONE) return; |
| assert(node.index != null); // Because there is at least one check. |
| Primitive object = node.object.definition; |
| SignedVariable length = node.length == null |
| ? null |
| : getValue(node.length.definition); |
| SignedVariable index = getValue(node.index.definition); |
| if (node.hasUpperBoundCheck) { |
| if (isDefinitelyLessThan(index, length)) { |
| node.checks &= ~BoundsCheck.UPPER_BOUND; |
| } else { |
| makeLessThan(index, length); |
| } |
| } |
| if (node.hasLowerBoundCheck) { |
| if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) { |
| node.checks &= ~BoundsCheck.LOWER_BOUND; |
| } else { |
| makeGreaterThanOrEqualToConstant(index, 0); |
| } |
| } |
| if (node.hasEmptinessCheck) { |
| if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) { |
| node.checks &= ~BoundsCheck.EMPTINESS; |
| } else { |
| makeGreaterThanOrEqualToConstant(length, 1); |
| } |
| } |
| if (!node.lengthUsedInCheck && node.length != null) { |
| node..length.unlink()..length = null; |
| } |
| if (node.checks == BoundsCheck.NONE) { |
| // We can't remove the bounds check node because it may still be used to |
| // restrict code motion. But the index is no longer needed. |
| node..index.unlink()..index = null; |
| } |
| } |
| |
| void analyzeLoopEntry(InvokeContinuation node) { |
| foundLoop = true; |
| Continuation cont = node.continuation.definition; |
| if (isStrongLoopPass) { |
| for (int i = 0; i < node.arguments.length; ++i) { |
| Parameter param = cont.parameters[i]; |
| if (!isInt(param)) continue; |
| Primitive initialValue = node.arguments[i].definition; |
| SignedVariable initialVariable = getValue(initialValue); |
| Monotonicity mono = monotonicity[param]; |
| if (mono == null) { |
| // Value never changes. This is extremely uncommon. |
| param.replaceUsesWith(initialValue); |
| } else if (mono == Monotonicity.Increasing) { |
| makeGreaterThanOrEqual(getValue(param), initialVariable); |
| } else if (mono == Monotonicity.Decreasing) { |
| makeLessThanOrEqual(getValue(param), initialVariable); |
| } |
| } |
| } |
| if (loopEffects.loopChangesLength(cont)) { |
| currentEffectNumber = effectNumberAt[cont] = makeNewEffect(); |
| } |
| push(cont); |
| } |
| |
| void analyzeLoopContinue(InvokeContinuation node) { |
| Continuation cont = node.continuation.definition; |
| |
| // During the strong loop phase, there is no need to compute monotonicity, |
| // and we already put bounds on the loop variables when we went into the |
| // loop. |
| if (isStrongLoopPass) return; |
| |
| // For each loop parameter, try to prove that the new value is definitely |
| // less/greater than its old value. When we fail to prove this, update the |
| // monotonicity flag accordingly. |
| for (int i = 0; i < node.arguments.length; ++i) { |
| Parameter param = cont.parameters[i]; |
| if (!isInt(param)) continue; |
| SignedVariable arg = getValue(node.arguments[i].definition); |
| SignedVariable paramVar = getValue(param); |
| if (!isDefinitelyLessThanOrEqualTo(arg, paramVar)) { |
| // We couldn't prove that the value does not increase, so assume |
| // henceforth that it might be increasing. |
| markMonotonicity(cont.parameters[i], Monotonicity.Increasing); |
| } |
| if (!isDefinitelyGreaterThanOrEqualTo(arg, paramVar)) { |
| // We couldn't prove that the value does not decrease, so assume |
| // henceforth that it might be decreasing. |
| markMonotonicity(cont.parameters[i], Monotonicity.Decreasing); |
| } |
| } |
| } |
| |
| void markMonotonicity(Parameter param, Monotonicity mono) { |
| Monotonicity current = monotonicity[param]; |
| if (current == null) { |
| monotonicity[param] = mono; |
| } else if (current != mono) { |
| monotonicity[param] = Monotonicity.NotMonotone; |
| } |
| } |
| |
| @override |
| void visitInvokeContinuation(InvokeContinuation node) { |
| Continuation cont = node.continuation.definition; |
| if (node.isRecursive) { |
| analyzeLoopContinue(node); |
| } else if (cont.isRecursive) { |
| analyzeLoopEntry(node); |
| } else { |
| int effect = effectNumberAt[cont]; |
| if (effect == null) { |
| effectNumberAt[cont] = currentEffectNumber; |
| } else if (effect != currentEffectNumber && effect != NEW_EFFECT) { |
| effectNumberAt[cont] = NEW_EFFECT; |
| } |
| // TODO(asgerf): Compute join for parameters to increase precision? |
| } |
| } |
| |
| // ---------------- PRIMITIVES -------------------- |
| |
| @override |
| void visitInvokeMethod(InvokeMethod node) { |
| // TODO(asgerf): What we really need is a "changes length" side effect flag. |
| if (world |
| .getSideEffectsOfSelector(node.selector, node.mask) |
| .changesIndex()) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| } |
| |
| @override |
| void visitInvokeStatic(InvokeStatic node) { |
| if (world.getSideEffectsOfElement(node.target).changesIndex()) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| } |
| |
| @override |
| void visitInvokeMethodDirectly(InvokeMethodDirectly node) { |
| FunctionElement target = node.target; |
| if (target is ConstructorBodyElement) { |
| ConstructorBodyElement body = target; |
| target = body.constructor; |
| } |
| if (world.getSideEffectsOfElement(target).changesIndex()) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| } |
| |
| @override |
| void visitInvokeConstructor(InvokeConstructor node) { |
| if (world.getSideEffectsOfElement(node.target).changesIndex()) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| } |
| |
| @override |
| void visitTypeCast(TypeCast node) { |
| } |
| |
| @override |
| void visitGetLazyStatic(GetLazyStatic node) { |
| // TODO(asgerf): How do we get the side effects of a lazy field initializer? |
| currentEffectNumber = makeNewEffect(); |
| } |
| |
| @override |
| void visitForeignCode(ForeignCode node) { |
| if (node.nativeBehavior.sideEffects.changesIndex()) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| } |
| |
| @override |
| void visitAwait(Await node) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| |
| @override |
| void visitYield(Yield node) { |
| currentEffectNumber = makeNewEffect(); |
| } |
| |
| @override |
| void visitApplyBuiltinMethod(ApplyBuiltinMethod node) { |
| Primitive receiver = node.receiver.definition; |
| int effectBefore = currentEffectNumber; |
| currentEffectNumber = makeNewEffect(); |
| int effectAfter = currentEffectNumber; |
| SignedVariable lengthBefore = getLength(receiver, effectBefore); |
| SignedVariable lengthAfter = getLength(receiver, effectAfter); |
| switch (node.method) { |
| case BuiltinMethod.Push: |
| // after = before + count |
| int count = node.arguments.length; |
| makeExactSum(lengthAfter, lengthBefore, count); |
| break; |
| |
| case BuiltinMethod.Pop: |
| // after = before - 1 |
| makeExactSum(lengthAfter, lengthBefore, -1); |
| break; |
| } |
| } |
| |
| @override |
| void visitLiteralList(LiteralList node) { |
| makeConstant(getLength(node, currentEffectNumber), node.values.length); |
| } |
| |
| // ---------------- INTERIOR EXPRESSIONS -------------------- |
| |
| @override |
| Expression traverseContinuation(Continuation cont) { |
| if (octagon.isUnsolvable) { |
| destroyAndReplace(cont.body, new Unreachable()); |
| } else { |
| int effect = effectNumberAt[cont]; |
| if (effect != null) { |
| currentEffectNumber = effect == NEW_EFFECT ? makeNewEffect() : effect; |
| } |
| } |
| return cont.body; |
| } |
| |
| @override |
| Expression traverseLetCont(LetCont node) { |
| // Join continuations should be pushed at declaration-site, so all their |
| // call sites are seen before they are analyzed. |
| // Other continuations are pushed at the use site. |
| for (Continuation cont in node.continuations) { |
| if (cont.hasAtLeastOneUse && |
| !cont.isRecursive && |
| cont.firstRef.parent is InvokeContinuation) { |
| push(cont); |
| } |
| } |
| return node.body; |
| } |
| } |
| |
| /// Lattice representing the known (weak) monotonicity of a loop variable. |
| /// |
| /// The lattice bottom is represented by `null` and represents the case where |
| /// the loop variable never changes value during the loop. |
| enum Monotonicity { NotMonotone, Increasing, Decreasing, } |
