// 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.optimize;

import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
import static com.google.common.base.Predicates.alwaysTrue;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClassAndField;
import com.android.tools.r8.graph.DexClassAndMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.FieldResolutionResult.SuccessfulFieldResolutionResult;
import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
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.Assume;
import com.android.tools.r8.ir.code.Assume.DynamicTypeAssumption;
import com.android.tools.r8.ir.code.Assume.NonNullAssumption;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.BasicBlockIterator;
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.DominatorTree;
import com.android.tools.r8.ir.code.FieldInstruction;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.LazyDominatorTree;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.optimize.info.FieldOptimizationInfo;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfo;
import com.android.tools.r8.ir.optimize.membervaluepropagation.assume.AssumeInfoLookup;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.TriConsumer;
import com.android.tools.r8.utils.TriFunction;
import com.android.tools.r8.utils.TriPredicate;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
import it.unimi.dsi.fastutil.ints.IntListIterator;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.Predicate;

public class AssumeInserter {

  private final AppView<AppInfoWithLiveness> appView;

  public AssumeInserter(AppView<AppInfoWithLiveness> appView) {
    this.appView = appView;
  }

  public void insertAssumeInstructions(IRCode code, Timing timing) {
    insertAssumeInstructionsInBlocks(code, code.listIterator(), alwaysTrue(), timing);
  }

  public void insertAssumeInstructionsInBlocks(
      IRCode code,
      BasicBlockIterator blockIterator,
      Predicate<BasicBlock> blockTester,
      Timing timing) {
    timing.begin("Insert assume instructions");
    internalInsertAssumeInstructionsInBlocks(code, blockIterator, blockTester, timing);
    timing.end();
  }

  private void internalInsertAssumeInstructionsInBlocks(
      IRCode code,
      BasicBlockIterator blockIterator,
      Predicate<BasicBlock> blockTester,
      Timing timing) {
    timing.begin("Part 1: Compute assumed values");
    AssumedValues assumedValues = computeAssumedValues(code, blockIterator, blockTester);
    timing.end();
    if (assumedValues.isEmpty()) {
      return;
    }

    timing.begin("Part 2: Remove redundant assume instructions");
    removeRedundantAssumeInstructions(assumedValues);
    timing.end();

    timing.begin("Part 3: Compute dominated users");
    Map<Instruction, Map<Value, AssumedValueInfo>> redundantAssumedValues =
        computeDominanceForAssumedValues(code, assumedValues);
    timing.end();
    if (assumedValues.isEmpty()) {
      return;
    }

    timing.begin("Part 4: Remove redundant dominated assume instructions");
    removeRedundantDominatedAssumeInstructions(assumedValues, redundantAssumedValues);
    timing.end();
    if (assumedValues.isEmpty()) {
      return;
    }

    timing.begin("Part 5: Materialize assume instructions");
    materializeAssumeInstructions(code, assumedValues);
    timing.end();
  }

  private AssumedValues computeAssumedValues(
      IRCode code, BasicBlockIterator blockIterator, Predicate<BasicBlock> blockTester) {
    AssumedValues.Builder assumedValuesBuilder = new AssumedValues.Builder();
    while (blockIterator.hasNext()) {
      BasicBlock block = blockIterator.next();
      if (blockTester.test(block)) {
        computeAssumedValuesInBlock(code, blockIterator, block, assumedValuesBuilder);
      }
    }
    return assumedValuesBuilder.build();
  }

  private void computeAssumedValuesInBlock(
      IRCode code,
      BasicBlockIterator blockIterator,
      BasicBlock block,
      AssumedValues.Builder assumedValuesBuilder) {
    // Add non-null after
    // 1) instructions that implicitly indicate receiver/array is not null.
    // 2) invocations that are guaranteed to return a non-null value.
    // 3) parameters that are not null after the invocation.
    // 4) field-get instructions that are guaranteed to read a non-null value.
    InstructionListIterator instructionIterator = block.listIterator(code);
    while (instructionIterator.hasNext()) {
      Instruction current = instructionIterator.next();
      boolean needsAssumeInstruction = false;

      // Case (1), instructions that implicitly indicate receiver/array is not null.
      if (current.throwsOnNullInput()) {
        Value inValue = current.getNonNullInput();
        if (assumedValuesBuilder.isMaybeNull(inValue)
            && isNullableReferenceTypeWithOtherNonDebugUsers(inValue, current)) {
          assumedValuesBuilder.addNonNullValueWithUnknownDominance(current, inValue);
          needsAssumeInstruction = true;
        }
      }

      if (current.isInvokeMethod()) {
        // Case (2) and (3).
        needsAssumeInstruction |=
            computeAssumedValuesForInvokeMethod(
                code, current.asInvokeMethod(), assumedValuesBuilder);
      } else if (current.isFieldGet()) {
        // Case (4), field-get instructions that are guaranteed to read a non-null value.
        needsAssumeInstruction |=
            computeAssumedValuesForFieldGet(current.asFieldInstruction(), assumedValuesBuilder);
      }

      // If we need to insert an assume instruction into a block with catch handlers, we split the
      // block such that the IR is ready for the insertion of the assume instruction.
      //
      // This splitting could in principle be deferred until we materialize the assume instructions,
      // but then we would need to rewind the basic block iterator to the beginning, and scan over
      // the instructions another time, splitting the blocks as needed.
      if (block.hasCatchHandlers()) {
        if (needsAssumeInstruction) {
          BasicBlock insertionBlock = instructionIterator.split(code, blockIterator);
          assert !instructionIterator.hasNext();
          assert instructionIterator.peekPrevious().isGoto();
          assert blockIterator.peekPrevious() == insertionBlock;
          computeAssumedValuesInBlock(code, blockIterator, insertionBlock, assumedValuesBuilder);
          return;
        }
        if (current.instructionTypeCanThrow()) {
          break;
        }
      }
    }

    If ifInstruction = block.exit().asIf();
    if (ifInstruction != null && ifInstruction.isNonTrivialNullTest()) {
      Value lhs = ifInstruction.lhs();
      if (assumedValuesBuilder.isMaybeNull(lhs)
          && isNullableReferenceTypeWithOtherNonDebugUsers(lhs, ifInstruction)
          && ifInstruction.targetFromNonNullObject().getPredecessors().size() == 1) {
        assumedValuesBuilder.addNonNullValueWithUnknownDominance(ifInstruction, lhs);
      }
    }
  }

  private boolean computeAssumedValuesForInvokeMethod(
      IRCode code, InvokeMethod invoke, AssumedValues.Builder assumedValuesBuilder) {
    if (!invoke.hasOutValue() && invoke.getInvokedMethod().proto.parameters.isEmpty()) {
      return false;
    }

    DexMethod invokedMethod = invoke.getInvokedMethod();
    if (invokedMethod.holder.isArrayType()
        && invokedMethod.match(appView.dexItemFactory().objectMembers.clone)) {
      return computeAssumedValuesFromArrayClone(invoke, assumedValuesBuilder);
    }

    return computeAssumedValuesFromSingleTarget(code, invoke, assumedValuesBuilder);
  }

  private boolean computeAssumedValuesFromArrayClone(
      InvokeMethod invoke, AssumedValues.Builder assumedValuesBuilder) {
    Value outValue = invoke.outValue();
    if (outValue == null || !outValue.hasNonDebugUsers()) {
      return false;
    }

    TypeElement dynamicUpperBoundType =
        TypeElement.fromDexType(invoke.getInvokedMethod().holder, definitelyNotNull(), appView);
    assumedValuesBuilder.addAssumedValueKnownToDominateAllUsers(
        invoke, outValue, dynamicUpperBoundType, null);
    return true;
  }

  private boolean computeAssumedValuesFromSingleTarget(
      IRCode code, InvokeMethod invoke, AssumedValues.Builder assumedValuesBuilder) {
    SingleResolutionResult resolutionResult =
        appView
            .appInfo()
            .unsafeResolveMethodDueToDexFormat(invoke.getInvokedMethod())
            .asSingleResolution();
    if (resolutionResult == null) {
      return false;
    }

    DexClassAndMethod singleTarget = invoke.lookupSingleTarget(appView, code.context());
    if (invoke.hasUsedOutValue() && invoke.getOutType().isReferenceType()) {
      AssumeInfo assumeInfo =
          AssumeInfoLookup.lookupAssumeInfo(appView, resolutionResult, singleTarget);
      if (assumeInfo != null
          && assumeInfo.hasReturnInfo()
          && assumeInfo.getReturnInfo().isNonNull()) {
        assumedValuesBuilder.addNonNullValueKnownToDominateAllUsers(invoke, invoke.outValue());
      }
    }

    if (singleTarget == null) {
      return false;
    }

    boolean needsAssumeInstruction = false;
    MethodOptimizationInfo optimizationInfo = singleTarget.getDefinition().getOptimizationInfo();

    // Case (2), invocations that are guaranteed to return a non-null value.
    if (invoke.hasUsedOutValue()) {
      needsAssumeInstruction =
          computeAssumedValuesForOutValue(
              invoke,
              optimizationInfo.getDynamicUpperBoundTypeOrElse(invoke.getOutType()),
              optimizationInfo.getDynamicLowerBoundType(),
              assumedValuesBuilder);
    }

    // Case (3), parameters that are not null after the invocation.
    BitSet nonNullParamOnNormalExits = optimizationInfo.getNonNullParamOnNormalExits();
    if (nonNullParamOnNormalExits != null) {
      int start = invoke.isInvokeMethodWithReceiver() ? 1 : 0;
      for (int i = start; i < invoke.arguments().size(); i++) {
        if (nonNullParamOnNormalExits.get(i)) {
          Value argument = invoke.getArgument(i);
          if (assumedValuesBuilder.isMaybeNull(argument)
              && isNullableReferenceTypeWithOtherNonDebugUsers(argument, invoke)) {
            assumedValuesBuilder.addNonNullValueWithUnknownDominance(invoke, argument);
            needsAssumeInstruction = true;
          }
        }
      }
    }
    return needsAssumeInstruction;
  }

  private boolean computeAssumedValuesForFieldGet(
      FieldInstruction fieldGet, AssumedValues.Builder assumedValuesBuilder) {
    if (fieldGet.hasUnusedOutValue()) {
      return false;
    }

    SuccessfulFieldResolutionResult resolutionResult =
        appView.appInfo().resolveField(fieldGet.getField()).asSuccessfulResolution();
    if (resolutionResult == null) {
      return false;
    }

    DexClassAndField field = resolutionResult.getResolutionPair();

    if (field.getType().isReferenceType()) {
      AssumeInfo assumeInfo = AssumeInfoLookup.lookupAssumeInfo(appView, field);
      if (assumeInfo != null
          && assumeInfo.hasReturnInfo()
          && assumeInfo.getReturnInfo().isNonNull()) {
        assumedValuesBuilder.addNonNullValueKnownToDominateAllUsers(fieldGet, fieldGet.outValue());
      }
    }

    FieldOptimizationInfo optimizationInfo = field.getDefinition().getOptimizationInfo();
    return computeAssumedValuesForOutValue(
        fieldGet,
        optimizationInfo.getDynamicUpperBoundTypeOrElse(fieldGet.getOutType()),
        optimizationInfo.getDynamicLowerBoundType(),
        assumedValuesBuilder);
  }

  private boolean computeAssumedValuesForOutValue(
      Instruction instruction,
      TypeElement dynamicUpperBoundType,
      ClassTypeElement dynamicLowerBoundType,
      AssumedValues.Builder assumedValuesBuilder) {
    Value outValue = instruction.outValue();

    // Do not insert dynamic type information if it does not refine the static type.
    boolean isRedundant =
        !dynamicUpperBoundType.strictlyLessThan(outValue.getType(), appView)
            && dynamicLowerBoundType == null;
    if (isRedundant) {
      return false;
    }

    // Do not insert dynamic type information if the dynamic type only refines the nullability.
    if (dynamicUpperBoundType.equalUpToNullability(outValue.getType())
        && dynamicLowerBoundType == null) {
      assert dynamicUpperBoundType.isDefinitelyNotNull();
      assumedValuesBuilder.addNonNullValueKnownToDominateAllUsers(instruction, outValue);
    } else {
      assumedValuesBuilder.addAssumedValueKnownToDominateAllUsers(
          instruction, outValue, dynamicUpperBoundType, dynamicLowerBoundType);
    }
    return true;
  }

  private void removeRedundantAssumeInstructions(AssumedValues assumedValues) {
    assumedValues.removeIf(
        (instruction, assumedValue, assumedValueInfo) -> {
          // Assumed values with dynamic type information are never redundant.
          if (assumedValueInfo.hasDynamicTypeInfo()) {
            return false;
          }

          assert assumedValueInfo.isNonNull();

          // Otherwise, it is redundant if it is defined by another instruction that guarantees its
          // non-nullness.
          if (assumedValue.isPhi()) {
            return false;
          }

          Instruction definition = assumedValue.definition;
          if (definition == instruction) {
            return false;
          }

          AssumedValueInfo otherAssumedValueInfo =
              assumedValues.getAssumedValueInfo(definition, assumedValue);
          if (otherAssumedValueInfo == null) {
            return false;
          }

          if (!otherAssumedValueInfo.isNonNull()) {
            // This is not redundant, but we can strenghten it with the dynamic type information
            // from the other assume instruction.
            assumedValueInfo.setDynamicTypeAssumption(
                otherAssumedValueInfo.getDynamicTypeAssumption());
            return false;
          }

          return true;
        });
  }

  private Map<Instruction, Map<Value, AssumedValueInfo>> computeDominanceForAssumedValues(
      IRCode code, AssumedValues assumedValues) {
    Map<Instruction, Map<Value, AssumedValueInfo>> redundantAssumedValues = new IdentityHashMap<>();
    LazyDominatorTree lazyDominatorTree = new LazyDominatorTree(code);
    Map<BasicBlock, Set<BasicBlock>> dominatedBlocksCache = new IdentityHashMap<>();
    assumedValues.computeDominance(
        (instruction, assumedValue, assumedValueInfo) -> {
          Map<Value, AssumedValueInfo> alreadyAssumedValues =
              redundantAssumedValues.get(instruction);
          if (alreadyAssumedValues != null) {
            AssumedValueInfo alreadyAssumedValueInfo = alreadyAssumedValues.get(assumedValue);
            if (alreadyAssumedValueInfo != null) {
              if (assumedValueInfo.isSubsumedBy(alreadyAssumedValueInfo)) {
                // Returning redundant() will cause the entry (instruction, assumedValue) to be
                // removed.
                return AssumedDominance.redundant();
              }

              // This assume value is dominated by the other assume value, so strengthen this one.
              assumedValueInfo.strengthenWith(alreadyAssumedValueInfo);
            }
          }

          // If this value is the out-value of some instruction it is known to dominate all users.
          if (assumedValue == instruction.outValue()) {
            return AssumedDominance.everything();
          }

          // If we learn that this value is known to be non-null in the same block as it is defined,
          // and it is not used between its definition and the instruction that performs the null
          // check, then the non-null-value is known to dominate all other users than the null check
          // itself.
          BasicBlock block = instruction.getBlock();
          if (assumedValue.getBlock() == block
              && block.exit().isGoto()
              && !instruction.getBlock().hasCatchHandlers()) {
            InstructionIterator iterator = instruction.getBlock().iterator();
            if (!assumedValue.isPhi()) {
              iterator.nextUntil(x -> x != assumedValue.definition);
              iterator.previous();
            }
            boolean isUsedBeforeInstruction = false;
            while (iterator.hasNext()) {
              Instruction current = iterator.next();
              if (current == instruction) {
                break;
              }
              if (current.inValues().contains(assumedValue)
                  || current.getDebugValues().contains(assumedValue)) {
                isUsedBeforeInstruction = true;
                break;
              }
            }
            if (!isUsedBeforeInstruction) {
              return AssumedDominance.everythingElse();
            }
          }

          // Otherwise, we need a dominator tree to determine which users are dominated.
          BasicBlock insertionBlock = getInsertionBlock(instruction);

          assert assumedValue.hasPhiUsers()
              || assumedValue.uniqueUsers().stream().anyMatch(user -> user != instruction)
              || assumedValue.isArgument();

          // Find all users of the original value that are dominated by either the current block
          // or the new split-off block. Since NPE can be explicitly caught, nullness should be
          // propagated through dominance.
          DominatorTree dominatorTree = lazyDominatorTree.get();
          Set<BasicBlock> dominatedBlocks =
              dominatedBlocksCache.computeIfAbsent(
                  insertionBlock, x -> dominatorTree.dominatedBlocks(x, Sets.newIdentityHashSet()));

          AssumedDominance.Builder dominance = AssumedDominance.builder(assumedValue);
          for (Instruction user : assumedValue.uniqueUsers()) {
            if (user != instruction && dominatedBlocks.contains(user.getBlock())) {
              if (user.getBlock() == insertionBlock && insertionBlock == block) {
                Instruction first = block.iterator().nextUntil(x -> x == instruction || x == user);
                assert first != null;
                if (first == user) {
                  continue;
                }
              }
              dominance.addDominatedUser(user);

              // Record that there is no need to insert an assume instruction for the non-null-value
              // after the given user in case the user is also a null check for the non-null-value.
              redundantAssumedValues
                  .computeIfAbsent(user, ignore -> new IdentityHashMap<>())
                  .put(assumedValue, assumedValueInfo);
            }
          }
          for (Phi user : assumedValue.uniquePhiUsers()) {
            IntList dominatedPredecessorIndices =
                findDominatedPredecessorIndexesInPhi(user, assumedValue, dominatedBlocks);
            if (!dominatedPredecessorIndices.isEmpty()) {
              dominance.addDominatedPhiUser(user, dominatedPredecessorIndices);
            }
          }
          return dominance.build();
        });
    return redundantAssumedValues;
  }

  private void removeRedundantDominatedAssumeInstructions(
      AssumedValues assumedValues,
      Map<Instruction, Map<Value, AssumedValueInfo>> redundantAssumedValues) {
    assumedValues.removeAll(redundantAssumedValues);
  }

  private void materializeAssumeInstructions(IRCode code, AssumedValues assumedValues) {
    Set<Value> affectedValues = Sets.newIdentityHashSet();
    Map<BasicBlock, Map<Instruction, List<Instruction>>> pendingInsertions =
        new IdentityHashMap<>();

    // We materialize the assume instructions in two steps. First, we materialize all the assume
    // instructions that do not dominate everything. These assume instructions can refine previous
    // assume instructions, so we materialize those first as they are "stronger".
    //
    // Example:
    //   1. Object value = getNullableValueWithDynamicType();
    //   2. Object nullableValueWithDynamicType = assume(value, ...)
    //   3. checkNotNull(value);
    //   4. Object nonNullValueWithDynamicType = assume(value, ...)
    //   5. return value;
    //
    // In this example, we first materialize the assume instruction in line 4, and replace the
    // dominated use of `value` in line 5 by the new assumed value `nonNullValueWithDynamicType`.
    // Afterwards, we materialize the assume instruction in line 2, and replace all remaining users
    // of `value` by `nullableValueWithDynamicType`.
    //
    // Result:
    //   1. Object value = getNullableValueWithDynamicType();
    //   2. Object nullableValueWithDynamicType = assume(value, ...)
    //   3. checkNotNull(nullableValueWithDynamicType);
    //   4. Object nonNullValueWithDynamicType = assume(value, ...)
    //   5. return nonNullValueWithDynamicType;
    materializeSelectedAssumeInstructions(
        code,
        assumedValues,
        affectedValues,
        pendingInsertions,
        assumedValueInfo -> !assumedValueInfo.dominance.isEverything());
    materializeSelectedAssumeInstructions(
        code,
        assumedValues,
        affectedValues,
        pendingInsertions,
        assumedValueInfo -> assumedValueInfo.dominance.isEverything());
    pendingInsertions.forEach(
        (block, pendingInsertionsPerInstruction) -> {
          InstructionListIterator instructionIterator = block.listIterator(code);
          while (instructionIterator.hasNext() && !pendingInsertionsPerInstruction.isEmpty()) {
            Instruction instruction = instructionIterator.next();
            List<Instruction> pendingAssumeInstructions =
                pendingInsertionsPerInstruction.remove(instruction);
            if (pendingAssumeInstructions != null) {
              pendingAssumeInstructions.forEach(instructionIterator::add);
            }
          }
        });
    if (!affectedValues.isEmpty()) {
      new TypeAnalysis(appView).narrowing(affectedValues);
    }
  }

  private void materializeSelectedAssumeInstructions(
      IRCode code,
      AssumedValues assumedValues,
      Set<Value> affectedValues,
      Map<BasicBlock, Map<Instruction, List<Instruction>>> pendingInsertions,
      Predicate<AssumedValueInfo> predicate) {
    assumedValues.removeIf(
        (instruction, assumedValue, assumedValueInfo) -> {
          if (!predicate.test(assumedValueInfo)) {
            return false;
          }

          BasicBlock block = instruction.getBlock();
          BasicBlock insertionBlock = getInsertionBlock(instruction);

          AssumedDominance dominance = assumedValueInfo.getDominance();
          Value newValue =
              assumedValueInfo.isNull()
                  ? code.createValue(TypeElement.getNull())
                  : code.createValue(
                      assumedValueInfo.isNonNull()
                          ? assumedValue.getType().asReferenceType().asMeetWithNotNull()
                          : assumedValue.getType(),
                      assumedValue.getLocalInfo());
          if (dominance.isEverything()) {
            assumedValue.replaceUsers(newValue);
          } else if (dominance.isEverythingElse()) {
            assumedValue.replaceSelectiveInstructionUsers(newValue, user -> user != instruction);
            assumedValue.replacePhiUsers(newValue);
          } else if (dominance.isSomething()) {
            SomethingAssumedDominance somethingDominance = dominance.asSomething();
            somethingDominance
                .getDominatedPhiUsers()
                .forEach(
                    (user, indices) -> {
                      IntListIterator iterator = indices.iterator();
                      while (iterator.hasNext()) {
                        Value operand = user.getOperand(iterator.nextInt());
                        if (operand != assumedValue) {
                          assert operand.isDefinedByInstructionSatisfying(Instruction::isAssume);
                          iterator.remove();
                        }
                      }
                    });
            assumedValue.replaceSelectiveUsers(
                newValue,
                somethingDominance.getDominatedUsers(),
                somethingDominance.getDominatedPhiUsers());
          }
          affectedValues.addAll(newValue.affectedValues());

          Instruction assumeInstruction;
          if (assumedValueInfo.isNull()) {
            assumeInstruction = new ConstNumber(newValue, 0);
          } else {
            assumeInstruction =
                new Assume(
                    assumedValueInfo.dynamicTypeAssumption,
                    assumedValueInfo.nonNullAssumption,
                    newValue,
                    assumedValue,
                    instruction,
                    appView);
          }
          assumeInstruction.setPosition(instruction.getPosition());
          if (insertionBlock != block) {
            insertionBlock.listIterator(code).add(assumeInstruction);
          } else {
            pendingInsertions
                .computeIfAbsent(block, ignore -> new IdentityHashMap<>())
                .computeIfAbsent(instruction, ignore -> new ArrayList<>())
                .add(assumeInstruction);
          }
          return true;
        });
  }

  private BasicBlock getInsertionBlock(Instruction instruction) {
    if (instruction.isIf()) {
      return instruction.asIf().targetFromNonNullObject();
    }
    BasicBlock block = instruction.getBlock();
    if (block.hasCatchHandlers()) {
      return block.exit().asGoto().getTarget();
    }
    return block;
  }

  private IntList findDominatedPredecessorIndexesInPhi(
      Phi user, Value assumedValue, Set<BasicBlock> dominatedBlocks) {
    assert user.getOperands().contains(assumedValue);
    List<Value> operands = user.getOperands();
    List<BasicBlock> predecessors = user.getBlock().getPredecessors();
    assert operands.size() == predecessors.size();

    IntList predecessorIndexes = new IntArrayList();
    int index = 0;
    Iterator<Value> operandIterator = operands.iterator();
    Iterator<BasicBlock> predecessorIterator = predecessors.iterator();
    while (operandIterator.hasNext() && predecessorIterator.hasNext()) {
      Value operand = operandIterator.next();
      BasicBlock predecessor = predecessorIterator.next();
      // When this phi is chosen to be known-to-be-non-null value,
      // check if the corresponding predecessor is dominated by the block where non-null is added.
      if (operand == assumedValue && dominatedBlocks.contains(predecessor)) {
        predecessorIndexes.add(index);
      }

      index++;
    }
    return predecessorIndexes;
  }

  private static boolean isNullableReferenceType(Value value) {
    TypeElement type = value.getType();
    return type.isReferenceType() && type.asReferenceType().isNullable();
  }

  private static boolean isNullableReferenceTypeWithOtherNonDebugUsers(
      Value value, Instruction ignore) {
    if (isNullableReferenceType(value)) {
      if (value.hasPhiUsers()) {
        return true;
      }
      for (Instruction user : value.uniqueUsers()) {
        if (user != ignore) {
          return true;
        }
      }
    }
    return false;
  }

  static class AssumedValueInfo {

    AssumedDominance dominance;
    DynamicTypeAssumption dynamicTypeAssumption;
    NonNullAssumption nonNullAssumption;

    AssumedValueInfo(AssumedDominance dominance) {
      this.dominance = dominance;
    }

    AssumedDominance getDominance() {
      return dominance;
    }

    void setDominance(AssumedDominance dominance) {
      this.dominance = dominance;
    }

    boolean hasDynamicTypeInfo() {
      return dynamicTypeAssumption != null;
    }

    DynamicTypeAssumption getDynamicTypeAssumption() {
      return dynamicTypeAssumption;
    }

    void setDynamicTypeAssumption(DynamicTypeAssumption dynamicTypeAssumption) {
      this.dynamicTypeAssumption = dynamicTypeAssumption;
    }

    void setDynamicTypeAssumption(
        TypeElement dynamicUpperBoundType, ClassTypeElement dynamicLowerBoundType) {
      dynamicTypeAssumption =
          new DynamicTypeAssumption(dynamicUpperBoundType, dynamicLowerBoundType);
      if (dynamicUpperBoundType.isDefinitelyNotNull()) {
        setNotNull();
      }
      if (dynamicLowerBoundType != null && dynamicLowerBoundType.isDefinitelyNotNull()) {
        setNotNull();
      }
    }

    boolean isNull() {
      return dynamicTypeAssumption != null
          && dynamicTypeAssumption.getDynamicUpperBoundType().isDefinitelyNull();
    }

    boolean isNonNull() {
      return nonNullAssumption != null;
    }

    void setNotNull() {
      nonNullAssumption = NonNullAssumption.get();
    }

    boolean isSubsumedBy(AssumedValueInfo other) {
      return !hasDynamicTypeInfo() && other.isNonNull();
    }

    void strengthenWith(AssumedValueInfo info) {
      if (info.isNonNull()) {
        setNotNull();
      }
      if (!hasDynamicTypeInfo() && info.hasDynamicTypeInfo()) {
        setDynamicTypeAssumption(info.getDynamicTypeAssumption());
      }
    }
  }

  static class AssumedValues {

    /**
     * A mapping from each instruction to the (in and out) values that are guaranteed to be non-null
     * by the instruction. Each non-null value is subsequently mapped to the set of users that it
     * dominates.
     */
    Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues;

    public AssumedValues(Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues) {
      this.assumedValues = assumedValues;
    }

    public static Builder builder() {
      return new Builder();
    }

    void computeDominance(
        TriFunction<Instruction, Value, AssumedValueInfo, AssumedDominance> function) {
      Iterator<Entry<Instruction, Map<Value, AssumedValueInfo>>> outerIterator =
          assumedValues.entrySet().iterator();
      while (outerIterator.hasNext()) {
        Entry<Instruction, Map<Value, AssumedValueInfo>> outerEntry = outerIterator.next();
        Instruction instruction = outerEntry.getKey();
        Map<Value, AssumedValueInfo> dominancePerValue = outerEntry.getValue();
        Iterator<Entry<Value, AssumedValueInfo>> innerIterator =
            dominancePerValue.entrySet().iterator();
        while (innerIterator.hasNext()) {
          Entry<Value, AssumedValueInfo> innerEntry = innerIterator.next();
          Value assumedValue = innerEntry.getKey();
          AssumedValueInfo assumedValueInfo = innerEntry.getValue();
          AssumedDominance dominance = assumedValueInfo.dominance;
          if (dominance.isEverything()) {
            assert assumedValue.isDefinedByInstructionSatisfying(
                definition -> definition.outValue() == assumedValue);
            continue;
          }
          assert dominance.isUnknown();
          dominance = function.apply(instruction, assumedValue, assumedValueInfo);
          if ((dominance.isNothing() && !assumedValue.isArgument()) || dominance.isUnknown()) {
            innerIterator.remove();
          } else {
            assumedValueInfo.setDominance(dominance);
          }
        }
        if (dominancePerValue.isEmpty()) {
          outerIterator.remove();
        }
      }
    }

    AssumedValueInfo getAssumedValueInfo(Instruction instruction, Value assumedValue) {
      Map<Value, AssumedValueInfo> dominancePerValue = assumedValues.get(instruction);
      return dominancePerValue != null ? dominancePerValue.get(assumedValue) : null;
    }

    boolean isEmpty() {
      return assumedValues.isEmpty();
    }

    void forEach(TriConsumer<Instruction, Value, AssumedValueInfo> consumer) {
      assumedValues.forEach(
          (instruction, dominancePerValue) ->
              dominancePerValue.forEach(
                  (assumedValue, assumedValueInfo) ->
                      consumer.accept(instruction, assumedValue, assumedValueInfo)));
    }

    void removeAll(Map<Instruction, Map<Value, AssumedValueInfo>> keys) {
      keys.forEach(
          (instruction, redundantAssumedValues) -> {
            Map<Value, AssumedValueInfo> dominancePerValue = assumedValues.get(instruction);
            if (dominancePerValue != null) {
              redundantAssumedValues.keySet().forEach(dominancePerValue::remove);
              if (dominancePerValue.isEmpty()) {
                assumedValues.remove(instruction);
              }
            }
          });
    }

    void removeIf(TriPredicate<Instruction, Value, AssumedValueInfo> predicate) {
      Iterator<Entry<Instruction, Map<Value, AssumedValueInfo>>> outerIterator =
          assumedValues.entrySet().iterator();
      while (outerIterator.hasNext()) {
        Entry<Instruction, Map<Value, AssumedValueInfo>> outerEntry = outerIterator.next();
        Instruction instruction = outerEntry.getKey();
        Map<Value, AssumedValueInfo> dominancePerValue = outerEntry.getValue();
        Iterator<Entry<Value, AssumedValueInfo>> innerIterator =
            dominancePerValue.entrySet().iterator();
        while (innerIterator.hasNext()) {
          Entry<Value, AssumedValueInfo> innerEntry = innerIterator.next();
          Value assumedValue = innerEntry.getKey();
          AssumedValueInfo assumedValueInfo = innerEntry.getValue();
          if (predicate.test(instruction, assumedValue, assumedValueInfo)) {
            innerIterator.remove();
          }
        }
        if (dominancePerValue.isEmpty()) {
          outerIterator.remove();
        }
      }
    }

    static class Builder {

      private final Map<Instruction, Map<Value, AssumedValueInfo>> assumedValues =
          new LinkedHashMap<>();

      // Used to avoid unnecessary block splitting during phase 1.
      private final Set<Value> nonNullValuesKnownToDominateAllUsers = Sets.newIdentityHashSet();

      private void updateAssumedValueInfo(
          Instruction instruction,
          Value assumedValue,
          AssumedDominance dominance,
          Consumer<AssumedValueInfo> consumer) {
        AssumedValueInfo assumedValueInfo =
            assumedValues
                .computeIfAbsent(instruction, ignore -> new LinkedHashMap<>())
                .computeIfAbsent(assumedValue, ignore -> new AssumedValueInfo(dominance));
        consumer.accept(assumedValueInfo);
        if (dominance.isEverything() && assumedValueInfo.isNonNull()) {
          nonNullValuesKnownToDominateAllUsers.add(assumedValue);
        }
      }

      void addAssumedValueKnownToDominateAllUsers(
          Instruction instruction,
          Value assumedValue,
          TypeElement dynamicUpperBoundType,
          ClassTypeElement dynamicLowerBoundType) {
        updateAssumedValueInfo(
            instruction,
            assumedValue,
            AssumedDominance.everything(),
            assumedValueInfo ->
                assumedValueInfo.setDynamicTypeAssumption(
                    dynamicUpperBoundType, dynamicLowerBoundType));
      }

      void addNonNullValueKnownToDominateAllUsers(Instruction instruction, Value nonNullValue) {
        updateAssumedValueInfo(
            instruction, nonNullValue, AssumedDominance.everything(), AssumedValueInfo::setNotNull);
      }

      void addNonNullValueWithUnknownDominance(Instruction instruction, Value nonNullValue) {
        updateAssumedValueInfo(
            instruction, nonNullValue, AssumedDominance.unknown(), AssumedValueInfo::setNotNull);
      }

      public boolean isMaybeNull(Value value) {
        return !nonNullValuesKnownToDominateAllUsers.contains(value);
      }

      public AssumedValues build() {
        return new AssumedValues(assumedValues);
      }
    }
  }

  abstract static class AssumedDominance {

    boolean isEverything() {
      return false;
    }

    boolean isEverythingElse() {
      return false;
    }

    boolean isNothing() {
      return false;
    }

    boolean isSomething() {
      return false;
    }

    SomethingAssumedDominance asSomething() {
      return null;
    }

    boolean isUnknown() {
      return false;
    }

    public static Builder builder(Value assumedValue) {
      return new Builder(assumedValue);
    }

    public static EverythingAssumedDominance everything() {
      return EverythingAssumedDominance.getInstance();
    }

    public static EverythingElseAssumedDominance everythingElse() {
      return EverythingElseAssumedDominance.getInstance();
    }

    public static NothingAssumedDominance nothing() {
      return NothingAssumedDominance.getInstance();
    }

    public static UnknownAssumedDominance redundant() {
      return unknown();
    }

    public static SomethingAssumedDominance something(
        Set<Instruction> dominatedUsers, Map<Phi, IntList> dominatedPhiUsers) {
      return new SomethingAssumedDominance(dominatedUsers, dominatedPhiUsers);
    }

    public static UnknownAssumedDominance unknown() {
      return UnknownAssumedDominance.getInstance();
    }

    static class Builder {

      private final Value assumedValue;

      private final Set<Instruction> dominatedUsers = Sets.newIdentityHashSet();
      private final Map<Phi, IntList> dominatedPhiUsers = new IdentityHashMap<>();

      private Builder(Value assumedValue) {
        this.assumedValue = assumedValue;
      }

      void addDominatedUser(Instruction user) {
        assert assumedValue.uniqueUsers().contains(user);
        assert !dominatedUsers.contains(user);
        dominatedUsers.add(user);
      }

      void addDominatedPhiUser(Phi user, IntList dominatedPredecessorIndices) {
        assert assumedValue.uniquePhiUsers().contains(user);
        assert !dominatedPhiUsers.containsKey(user);
        dominatedPhiUsers.put(user, dominatedPredecessorIndices);
      }

      AssumedDominance build() {
        if (dominatedUsers.isEmpty() && dominatedPhiUsers.isEmpty()) {
          return nothing();
        }
        assert dominatedUsers.size() < assumedValue.uniqueUsers().size()
            || dominatedPhiUsers.size() < assumedValue.uniquePhiUsers().size();
        return something(dominatedUsers, dominatedPhiUsers);
      }
    }
  }

  static class EverythingAssumedDominance extends AssumedDominance {

    private static final EverythingAssumedDominance INSTANCE = new EverythingAssumedDominance();

    private EverythingAssumedDominance() {}

    public static EverythingAssumedDominance getInstance() {
      return INSTANCE;
    }

    @Override
    boolean isEverything() {
      return true;
    }
  }

  static class EverythingElseAssumedDominance extends AssumedDominance {

    private static final EverythingElseAssumedDominance INSTANCE =
        new EverythingElseAssumedDominance();

    private EverythingElseAssumedDominance() {}

    public static EverythingElseAssumedDominance getInstance() {
      return INSTANCE;
    }

    @Override
    boolean isEverythingElse() {
      return true;
    }
  }

  static class NothingAssumedDominance extends AssumedDominance {

    private static final NothingAssumedDominance INSTANCE = new NothingAssumedDominance();

    private NothingAssumedDominance() {}

    public static NothingAssumedDominance getInstance() {
      return INSTANCE;
    }

    @Override
    boolean isNothing() {
      return true;
    }
  }

  static class SomethingAssumedDominance extends AssumedDominance {

    private final Set<Instruction> dominatedUsers;
    private final Map<Phi, IntList> dominatedPhiUsers;

    SomethingAssumedDominance(
        Set<Instruction> dominatedUsers, Map<Phi, IntList> dominatedPhiUsers) {
      this.dominatedUsers = dominatedUsers;
      this.dominatedPhiUsers = dominatedPhiUsers;
    }

    public Set<Instruction> getDominatedUsers() {
      return dominatedUsers;
    }

    public Map<Phi, IntList> getDominatedPhiUsers() {
      return dominatedPhiUsers;
    }

    @Override
    boolean isSomething() {
      return true;
    }

    @Override
    SomethingAssumedDominance asSomething() {
      return this;
    }
  }

  static class UnknownAssumedDominance extends AssumedDominance {

    private static final UnknownAssumedDominance INSTANCE = new UnknownAssumedDominance();

    private UnknownAssumedDominance() {}

    public static UnknownAssumedDominance getInstance() {
      return INSTANCE;
    }

    @Override
    boolean isUnknown() {
      return true;
    }
  }
}