src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java

// Copyright (c) 2018, the R8 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.
package com.android.tools.r8.ir.conversion;

import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.analysis.type.ArrayTypeElement;
import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.ArrayPut;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.ImpreciseMemberTypeInstruction;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.MemberType;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueTypeConstraint;
import com.android.tools.r8.position.MethodPosition;
import com.android.tools.r8.utils.StringDiagnostic;
import com.google.common.collect.ImmutableSet;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;

/**
 * Type constraint resolver that ensures that all SSA values have a "precise" type, ie, every value
 * must be an element of exactly one of: object, int, float, long or double.
 *
 * <p>The resolution is a union-find over the SSA values, linking any type with an imprecise type to
 * a parent value that has either the same imprecise type or a precise one. SSA values are linked if
 * there type is constrained to be the same. This happens in two places:
 *
 * <ul>
 *   <li>For phis, the out value and all operand values must have the same type.
 *   <li>For if-{eq,ne} instructions, the input values must have the same type.
 *   <li>For array-{get,put} instructions, the array value must have member type compatible with the
 *       type of output/input value.
 * </ul>
 *
 * <p>All other constraints on types have been computed during IR construction where every call to
 * readRegister(ValueTypeConstraint) will constrain the type of the SSA value that the read resolves
 * to.
 */
public class TypeConstraintResolver {

  private final AppView<?> appView;
  private final IRBuilder builder;
  private final Map<Value, Value> unificationParents = new HashMap<>();

  public TypeConstraintResolver(AppView<?> appView, IRBuilder builder) {
    this.appView = appView;
    this.builder = builder;
  }

  public static ValueTypeConstraint constraintForType(TypeElement type) {
    // During constraint resolution the type bottom denotes references of not-yet-computed types.
    return type.isBottom() ? ValueTypeConstraint.OBJECT : ValueTypeConstraint.fromTypeLattice(type);
  }

  public static TypeElement typeForConstraint(ValueTypeConstraint constraint) {
    switch (constraint) {
      case INT_OR_FLOAT_OR_OBJECT:
        return TypeElement.getTop();
      case OBJECT:
        // If the constraint is object the concrete lattice type will need to be computed.
        // We mark the object type as bottom for now, with the implication that it is of type
        // reference but that it should not contribute to the computation of its join
        // (in potentially self-referencing phis).
        return TypeElement.getBottom();
      case INT:
        return TypeElement.getInt();
      case FLOAT:
        return TypeElement.getFloat();
      case INT_OR_FLOAT:
        return TypeElement.getSingle();
      case LONG:
        return TypeElement.getLong();
      case DOUBLE:
        return TypeElement.getDouble();
      case LONG_OR_DOUBLE:
        return TypeElement.getWide();
      default:
        throw new Unreachable("Unexpected constraint type: " + constraint);
    }
  }

  public void resolve(List<ImpreciseMemberTypeInstruction> impreciseInstructions, IRCode code) {
    // Round one will resolve at least all object vs single types.
    List<Value> remainingImpreciseValues = resolveRoundOne(code);
    // Round two will resolve any remaining single and wide types. These can depend on the types
    // of array instructions, thus we need to complete the type fixed point prior to resolving.
    new TypeAnalysis(appView, true).widening(code);
    // Round two resolves any remaining imprecision and finally selects a final precise type for
    // any unconstrained imprecise type.
    resolveRoundTwo(code, impreciseInstructions, remainingImpreciseValues);
  }

  private List<Value> resolveRoundOne(IRCode code) {
    List<Value> impreciseValues = new ArrayList<>();
    for (BasicBlock block : code.blocks) {
      for (Phi phi : block.getPhis()) {
        if (!phi.getType().isPreciseType()) {
          impreciseValues.add(phi);
        }
        for (Value value : phi.getOperands()) {
          merge(phi, value);
        }
      }
      for (Instruction instruction : block.getInstructions()) {
        if (instruction.outValue() != null && !instruction.outValue().getType().isPreciseType()) {
          impreciseValues.add(instruction.outValue());
        }

        if (instruction.isIf() && instruction.inValues().size() == 2) {
          If ifInstruction = instruction.asIf();
          assert !ifInstruction.isZeroTest();
          If.Type type = ifInstruction.getType();
          if (type == If.Type.EQ || type == If.Type.NE) {
            merge(ifInstruction.inValues().get(0), ifInstruction.inValues().get(1));
          }
        }
      }
    }
    return constrainValues(false, impreciseValues);
  }

  private void resolveRoundTwo(
      IRCode code,
      List<ImpreciseMemberTypeInstruction> impreciseInstructions,
      List<Value> remainingImpreciseValues) {
    if (impreciseInstructions != null) {
      for (ImpreciseMemberTypeInstruction impreciseInstruction : impreciseInstructions) {
        impreciseInstruction.constrainType(this);
      }
    }
    ArrayList<Value> stillImprecise = constrainValues(true, remainingImpreciseValues);
    if (!stillImprecise.isEmpty()) {
      throw appView
          .options()
          .reporter
          .fatalError(
              new StringDiagnostic(
                  "Cannot determine precise type for value: "
                      + stillImprecise.get(0)
                      + ", its imprecise type is: "
                      + stillImprecise.get(0).getType(),
                  code.origin,
                  new MethodPosition(code.method.method)));
    }
  }

  private ArrayList<Value> constrainValues(boolean finished, List<Value> impreciseValues) {
    ArrayList<Value> stillImprecise = new ArrayList<>(impreciseValues.size());
    for (Value value : impreciseValues) {
      builder.constrainType(value, getCanonicalTypeConstraint(value, finished));
      if (!value.getType().isPreciseType()) {
        stillImprecise.add(value);
      }
    }
    return stillImprecise;
  }

  public void constrainArrayMemberType(
      MemberType type, Value value, Value array, Consumer<MemberType> setter) {
    assert !type.isPrecise();
    Value canonical = canonical(value);
    ValueTypeConstraint constraint;
    if (array.getType().isArrayType()) {
      // If the array type is known it uniquely defines the actual member type.
      ArrayTypeElement arrayType = array.getType().asArrayType();
      constraint = ValueTypeConstraint.fromTypeLattice(arrayType.getMemberTypeAsValueType());
    } else {
      // If not, e.g., the array input is null, the canonical value determines the final type.
      constraint = getCanonicalTypeConstraint(canonical, true);
    }
    // Constrain the canonical value by the final and precise type constraint and set the member.
    // A refinement of the value type will then be propagated in constrainValues of "round two".
    builder.constrainType(canonical, constraint);
    setter.accept(MemberType.constrainedType(type, constraint));
  }

  private void merge(Value value1, Value value2) {
    link(canonical(value1), canonical(value2));
  }

  private ValueTypeConstraint getCanonicalTypeConstraint(Value value, boolean finished) {
    ValueTypeConstraint type = constraintForType(canonical(value).getType());
    switch (type) {
      case INT_OR_FLOAT_OR_OBJECT:
        // There is never a second round for resolving object vs single.
        assert !finished;
        return ValueTypeConstraint.INT_OR_FLOAT;
      case INT_OR_FLOAT:
        assert !finished || verifyNoConstrainedUses(value);
        return finished ? ValueTypeConstraint.INT : type;
      case LONG_OR_DOUBLE:
        assert !finished || verifyNoConstrainedUses(value);
        return finished ? ValueTypeConstraint.LONG : type;
      default:
        return type;
    }
  }

  private static boolean verifyNoConstrainedUses(Value value) {
    return verifyNoConstrainedUses(value, ImmutableSet.of());
  }

  private static boolean verifyNoConstrainedUses(Value value, Set<Value> assumeNoConstrainedUses) {
    for (Instruction user : value.uniqueUsers()) {
      if (user.isIf()) {
        If ifInstruction = user.asIf();
        if (ifInstruction.isZeroTest()) {
          continue;
        }
        Value other = ifInstruction.inValues().get(1 - ifInstruction.inValues().indexOf(value));
        if (assumeNoConstrainedUses.contains(other)) {
          continue;
        }
        assert verifyNoConstrainedUses(
            other,
            ImmutableSet.<Value>builder().addAll(assumeNoConstrainedUses).add(value).build());
      } else if (user.isArrayPut()) {
        ArrayPut put = user.asArrayPut();
        assert value == put.value();
        assert !put.getMemberType().isPrecise();
        assert put.array().getType().isDefinitelyNull();
      } else {
        assert false;
      }
    }
    return true;
  }

  // Link two values as having the same type.
  private void link(Value canonical1, Value canonical2) {
    if (canonical1 == canonical2) {
      return;
    }
    TypeElement type1 = canonical1.getType();
    TypeElement type2 = canonical2.getType();
    if (type1.isPreciseType() && type2.isPreciseType()) {
      if (type1 != type2 && constraintForType(type1) != constraintForType(type2)) {
        throw new CompilationError(
            "Cannot unify types for values "
                + canonical1
                + ":"
                + type1
                + " and "
                + canonical2
                + ":"
                + type2);
      }
      return;
    }
    if (type1.isPreciseType()) {
      unificationParents.put(canonical2, canonical1);
    } else {
      unificationParents.put(canonical1, canonical2);
    }
  }

  // Find root with path-compression.
  private Value canonical(Value value) {
    Value parent = value;
    while (parent != null) {
      Value grandparent = unificationParents.get(parent);
      if (grandparent != null) {
        unificationParents.put(value, grandparent);
      }
      value = parent;
      parent = grandparent;
    }
    return value;
  }
}