pkg/compiler/lib/src/ssa/types_propagation.dart

// 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 '../elements/types.dart';
import '../inferrer/abstract_value_domain.dart';
import '../inferrer/types.dart';
import '../options.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).isDefinitelyTrue &&
        right.isInteger(abstractValueDomain).isDefinitelyTrue) {
      return abstractValueDomain.intType;
    }
    if (left.isDouble(abstractValueDomain).isDefinitelyTrue) {
      return abstractValueDomain.doubleType;
    }
    return abstractValueDomain.numType;
  }

  AbstractValue checkPositiveInteger(HBinaryArithmetic instruction) {
    HInstruction left = instruction.left;
    HInstruction right = instruction.right;
    if (left.isPositiveInteger(abstractValueDomain).isDefinitelyTrue &&
        right.isPositiveInteger(abstractValueDomain).isDefinitelyTrue) {
      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).isDefinitelyTrue) {
      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).isDefinitelyTrue &&
          abstractValueDomain.isDoubleOrNull(checkedType).isDefinitelyFalse &&
          input.isIntegerOrNull(abstractValueDomain).isDefinitelyTrue) {
        instruction.checkedType = abstractValueDomain.intType;
      } else if (abstractValueDomain
              .isIntegerOrNull(checkedType)
              .isDefinitelyTrue &&
          input.isIntegerOrNull(abstractValueDomain).isPotentiallyFalse) {
        instruction.checkedType = abstractValueDomain.numType;
      }
    }

    AbstractValue outputType =
        abstractValueDomain.intersection(checkedType, inputType);
    if (abstractValueDomain.isEmpty(outputType).isDefinitelyTrue) {
      // 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).isDefinitelyTrue &&
          abstractValueDomain.isDoubleOrNull(checkedType).isDefinitelyTrue) {
        if (abstractValueDomain.isNull(inputType).isPotentiallyTrue &&
            abstractValueDomain.isNull(checkedType).isPotentiallyTrue) {
          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, DartType typeExpression) {
    Selector selector = (kind == HTypeConversion.RECEIVER_TYPE_CHECK)
        ? instruction.selector
        : null;
    HTypeConversion converted = new HTypeConversion(
        typeExpression, 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).isDefinitelyTrue) {
      // 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).isDefinitelyTrue;
    }
    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).isDefinitelyTrue) {
      return false;
    }
    if (receiver.isNumberOrNull(abstractValueDomain).isDefinitelyTrue) {
      convertInput(
          instruction,
          receiver,
          abstractValueDomain.excludeNull(receiver.instructionType),
          HTypeConversion.RECEIVER_TYPE_CHECK,
          commonElements.numType);
      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.
        DartType typeExpression;
        if (abstractValueDomain.isNumberOrNull(type).isDefinitelyTrue) {
          typeExpression = commonElements.numType;
        } else if (abstractValueDomain.isBooleanOrNull(type).isDefinitelyTrue) {
          typeExpression = commonElements.boolType;
        } else {
          return false;
        }
        if (!isCheckEnoughForNsmOrAe(receiver, type)) return false;
        instruction.element = target;
        convertInput(instruction, receiver, type,
            HTypeConversion.RECEIVER_TYPE_CHECK, typeExpression);
        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).isDefinitelyTrue) {
      if (right.isNumber(abstractValueDomain).isDefinitelyTrue) {
        return false;
      }
      AbstractValue type =
          right.isIntegerOrNull(abstractValueDomain).isDefinitelyTrue
              ? 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, commonElements.numType);
      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);
  }
}