// Copyright (c) 2019, 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.info;

import static com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query.DIRECTLY;
import static com.android.tools.r8.ir.code.DominatorTree.Assumption.MAY_HAVE_UNREACHABLE_BLOCKS;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexEncodedMethod.ClassInlinerEligibility;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.ResolutionResult;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
import com.android.tools.r8.ir.analysis.DeterminismAnalysis;
import com.android.tools.r8.ir.analysis.InitializedClassesOnNormalExitAnalysis;
import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis;
import com.android.tools.r8.ir.analysis.sideeffect.ClassInitializerSideEffectAnalysis.ClassInitializerSideEffect;
import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.ConstString;
import com.android.tools.r8.ir.code.DominatorTree;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.InstancePut;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InvokeDirect;
import com.android.tools.r8.ir.code.NewInstance;
import com.android.tools.r8.ir.code.Return;
import com.android.tools.r8.ir.code.StaticPut;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.optimize.DynamicTypeOptimization;
import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsageBuilder;
import com.android.tools.r8.ir.optimize.info.initializer.ClassInitializerInfo;
import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
import com.android.tools.r8.ir.optimize.info.initializer.NonTrivialInstanceInitializerInfo;
import com.android.tools.r8.kotlin.Kotlin;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Deque;
import java.util.List;
import java.util.Set;
import java.util.function.BiFunction;

public class MethodOptimizationInfoCollector {
  private final AppView<AppInfoWithLiveness> appView;
  private final InternalOptions options;
  private final DexItemFactory dexItemFactory;

  public MethodOptimizationInfoCollector(AppView<AppInfoWithLiveness> appView) {
    this.appView = appView;
    this.options = appView.options();
    this.dexItemFactory = appView.dexItemFactory();
  }

  public void collectMethodOptimizationInfo(
      DexEncodedMethod method,
      IRCode code,
      OptimizationFeedback feedback,
      DynamicTypeOptimization dynamicTypeOptimization) {
    identifyClassInlinerEligibility(method, code, feedback);
    identifyParameterUsages(method, code, feedback);
    identifyReturnsArgument(method, code, feedback);
    if (options.enableInlining) {
      identifyInvokeSemanticsForInlining(method, code, appView, feedback);
    }
    computeDynamicReturnType(dynamicTypeOptimization, feedback, method, code);
    computeInitializedClassesOnNormalExit(feedback, method, code);
    computeInitializerInfo(method, code, feedback);
    computeMayHaveSideEffects(feedback, method, code);
    computeReturnValueOnlyDependsOnArguments(feedback, method, code);
    computeNonNullParamOrThrow(feedback, method, code);
    computeNonNullParamOnNormalExits(feedback, code);
  }

  private void identifyClassInlinerEligibility(
      DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
    // Method eligibility is calculated in similar way for regular method
    // and for the constructor. To be eligible method should only be using its
    // receiver in the following ways:
    //
    //  (1) as a receiver of reads/writes of instance fields of the holder class,
    //  (2) as a return value,
    //  (3) as a receiver of a call to the superclass initializer. Note that we don't
    //      check what is passed to superclass initializer as arguments, only check
    //      that it is not the instance being initialized,
    //  (4) as argument to a monitor instruction.
    //
    // Note that (4) can safely be removed as the receiver is guaranteed not to escape when we class
    // inline it, and hence any monitor instructions are no-ops.
    boolean instanceInitializer = method.isInstanceInitializer();
    if (method.accessFlags.isNative()
        || (!method.isNonAbstractVirtualMethod() && !instanceInitializer)) {
      return;
    }

    feedback.setClassInlinerEligibility(method, null);  // To allow returns below.

    Value receiver = code.getThis();
    if (receiver.numberOfPhiUsers() > 0) {
      return;
    }

    DexClass clazz = appView.definitionFor(method.method.holder);
    if (clazz == null) {
      return;
    }

    boolean receiverUsedAsReturnValue = false;
    boolean seenSuperInitCall = false;
    for (Instruction insn : receiver.aliasedUsers()) {
      if (insn.isAssume()) {
        continue;
      }

      if (insn.isMonitor()) {
        continue;
      }

      if (insn.isReturn()) {
        receiverUsedAsReturnValue = true;
        continue;
      }

      if (insn.isInstanceGet() || insn.isInstancePut()) {
        if (insn.isInstancePut()) {
          InstancePut instancePutInstruction = insn.asInstancePut();
          // Only allow field writes to the receiver.
          if (instancePutInstruction.object().getAliasedValue() != receiver) {
            return;
          }
          // Do not allow the receiver to escape via a field write.
          if (instancePutInstruction.value().getAliasedValue() == receiver) {
            return;
          }
        }
        DexField field = insn.asFieldInstruction().getField();
        if (field.holder == clazz.type && clazz.lookupInstanceField(field) != null) {
          // Require only accessing instance fields of the *current* class.
          continue;
        }
        return;
      }

      // If this is an instance initializer allow one call to superclass instance initializer.
      if (insn.isInvokeDirect()) {
        InvokeDirect invokedDirect = insn.asInvokeDirect();
        DexMethod invokedMethod = invokedDirect.getInvokedMethod();
        if (dexItemFactory.isConstructor(invokedMethod)
            && invokedMethod.holder == clazz.superType
            && ListUtils.lastIndexMatching(
                invokedDirect.inValues(), v -> v.getAliasedValue() == receiver) == 0
            && !seenSuperInitCall
            && instanceInitializer) {
          seenSuperInitCall = true;
          continue;
        }
        // We don't support other direct calls yet.
        return;
      }

      // Other receiver usages make the method not eligible.
      return;
    }
    if (instanceInitializer && !seenSuperInitCall) {
      // Call to super constructor not found?
      return;
    }

    feedback.setClassInlinerEligibility(
        method, new ClassInlinerEligibility(receiverUsedAsReturnValue));
  }

  private void identifyParameterUsages(
      DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
    List<ParameterUsage> usages = new ArrayList<>();
    List<Value> values = code.collectArguments();
    for (int i = 0; i < values.size(); i++) {
      Value value = values.get(i);
      if (value.numberOfPhiUsers() > 0) {
        continue;
      }
      ParameterUsage usage = collectParameterUsages(i, value);
      if (usage != null) {
        usages.add(usage);
      }
    }
    feedback.setParameterUsages(
        method,
        usages.isEmpty()
            ? DefaultMethodOptimizationInfo.UNKNOWN_PARAMETER_USAGE_INFO
            : new ParameterUsagesInfo(usages));
  }

  private ParameterUsage collectParameterUsages(int i, Value value) {
    ParameterUsageBuilder builder = new ParameterUsageBuilder(value, i);
    for (Instruction user : value.aliasedUsers()) {
      if (!builder.note(user)) {
        return null;
      }
    }
    return builder.build();
  }

  private void identifyReturnsArgument(
      DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
    List<BasicBlock> normalExits = code.computeNormalExitBlocks();
    if (normalExits.isEmpty()) {
      feedback.methodNeverReturnsNormally(method);
      return;
    }
    Return firstExit = normalExits.get(0).exit().asReturn();
    if (firstExit.isReturnVoid()) {
      return;
    }
    Value returnValue = firstExit.returnValue();
    boolean isNeverNull = returnValue.getTypeLattice().isReference() && returnValue.isNeverNull();
    for (int i = 1; i < normalExits.size(); i++) {
      Return exit = normalExits.get(i).exit().asReturn();
      Value value = exit.returnValue();
      if (value != returnValue) {
        returnValue = null;
      }
      isNeverNull &= value.getTypeLattice().isReference() && value.isNeverNull();
    }
    if (returnValue != null) {
      Value aliasedValue = returnValue.getAliasedValue();
      if (aliasedValue.isArgument()) {
        // Find the argument number.
        int index = aliasedValue.computeArgumentPosition(code);
        assert index >= 0;
        feedback.methodReturnsArgument(method, index);
      }
      if (aliasedValue.isConstant()) {
        if (aliasedValue.definition.isConstNumber()) {
          long value = aliasedValue.definition.asConstNumber().getRawValue();
          feedback.methodReturnsConstantNumber(method, appView, value);
        } else if (aliasedValue.definition.isConstString()) {
          ConstString constStringInstruction = aliasedValue.definition.asConstString();
          if (!constStringInstruction.instructionInstanceCanThrow()) {
            feedback.methodReturnsConstantString(
                method, appView, constStringInstruction.getValue());
          }
        }
      }
    }
    if (isNeverNull) {
      feedback.methodNeverReturnsNull(method);
    }
  }

  private void computeInitializerInfo(
      DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
    assert !appView.appInfo().isPinned(method.method);

    if (!method.isInitializer()) {
      return;
    }

    if (method.accessFlags.isNative()) {
      return;
    }

    if (appView.appInfo().mayHaveSideEffects.containsKey(method.method)) {
      return;
    }

    DexClass clazz = appView.appInfo().definitionFor(method.method.holder);
    if (clazz == null) {
      assert false;
      return;
    }

    feedback.setInitializerInfo(
        method,
        method.isInstanceInitializer()
            ? computeInstanceInitializerInfo(code, clazz)
            : computeClassInitializerInfo(code, clazz));
  }

  // This method defines trivial class initializer as follows:
  //
  // ** The initializer may only instantiate an instance of the same class,
  //    initialize it with a call to a trivial constructor *without* arguments,
  //    and assign this instance to a static final field of the same class.
  //
  private ClassInitializerInfo computeClassInitializerInfo(IRCode code, DexClass clazz) {
    Value createdSingletonInstance = null;
    DexField singletonField = null;
    for (Instruction insn : code.instructions()) {
      if (insn.isConstNumber()) {
        continue;
      }

      if (insn.isConstString()) {
        if (insn.instructionInstanceCanThrow()) {
          return null;
        }
        continue;
      }

      if (insn.isReturn()) {
        continue;
      }

      if (insn.isAssume()) {
        continue;
      }

      if (insn.isNewInstance()) {
        NewInstance newInstance = insn.asNewInstance();
        if (createdSingletonInstance != null
            || newInstance.clazz != clazz.type
            || insn.outValue() == null) {
          return null;
        }
        createdSingletonInstance = insn.outValue();
        continue;
      }

      if (insn.isInvokeDirect()) {
        InvokeDirect invokedDirect = insn.asInvokeDirect();
        if (createdSingletonInstance == null
            || invokedDirect.getReceiver() != createdSingletonInstance) {
          return null;
        }
        DexEncodedMethod callTarget = clazz.lookupDirectMethod(invokedDirect.getInvokedMethod());
        if (callTarget == null
            || !callTarget.isInstanceInitializer()
            || !callTarget.method.proto.parameters.isEmpty()
            || callTarget.getOptimizationInfo().getInstanceInitializerInfo().isDefaultInfo()) {
          return null;
        }
        continue;
      }

      if (insn.isStaticPut()) {
        StaticPut staticPut = insn.asStaticPut();
        if (singletonField != null
            || createdSingletonInstance == null
            || staticPut.value() != createdSingletonInstance) {
          return null;
        }
        DexEncodedField field = clazz.lookupStaticField(staticPut.getField());
        if (field == null
            || !field.accessFlags.isStatic()
            || !field.accessFlags.isFinal()) {
          return null;
        }
        singletonField = field.field;
        continue;
      }

      // Other instructions make the class initializer not eligible.
      return null;
    }
    return singletonField == null ? null : new ClassInitializerInfo(singletonField);
  }

  // This method defines trivial instance initializer as follows:
  //
  // ** The holder class must not define a finalize method.
  //
  // ** The initializer may call the initializer of the base class, which
  //    itself must be trivial.
  //
  // ** java.lang.Object.<init>() is considered trivial.
  //
  // ** all arguments passed to a super-class initializer must be non-throwing
  //    constants or arguments.
  //
  // ** Assigns arguments or non-throwing constants to fields of this class.
  //
  // (Note that this initializer does not have to have zero arguments.)
  private InstanceInitializerInfo computeInstanceInitializerInfo(IRCode code, DexClass clazz) {
    if (clazz.definesFinalizer(options.itemFactory)) {
      // Defining a finalize method can observe the side-effect of Object.<init> GC registration.
      return null;
    }
    Value receiver = code.getThis();
    for (Instruction insn : code.instructions()) {
      if (insn.isReturn()) {
        continue;
      }

      if (insn.isAssume()) {
        continue;
      }

      if (insn.isArgument()) {
        continue;
      }

      if (insn.isConstInstruction()) {
        if (insn.instructionInstanceCanThrow()) {
          return null;
        } else {
          continue;
        }
      }

      if (insn.isInvokeDirect()) {
        InvokeDirect invokedDirect = insn.asInvokeDirect();
        DexMethod invokedMethod = invokedDirect.getInvokedMethod();
        if (!dexItemFactory.isConstructor(invokedMethod)) {
          return null;
        }
        if (invokedMethod.holder != clazz.superType) {
          return null;
        }
        // java.lang.Enum.<init>() and java.lang.Object.<init>() are considered trivial.
        if (invokedMethod == dexItemFactory.enumMethods.constructor
            || invokedMethod == dexItemFactory.objectMethods.constructor) {
          continue;
        }
        DexEncodedMethod callTarget = appView.definitionFor(invokedMethod);
        if (callTarget == null
            || callTarget.getOptimizationInfo().getInstanceInitializerInfo().isDefaultInfo()
            || invokedDirect.getReceiver() != receiver) {
          return null;
        }
        for (Value value : invokedDirect.inValues()) {
          if (value != receiver && !(value.isConstant() || value.isArgument())) {
            return null;
          }
        }
        continue;
      }

      if (insn.isInstancePut()) {
        InstancePut instancePut = insn.asInstancePut();
        DexEncodedField field = clazz.lookupInstanceField(instancePut.getField());
        if (field == null
            || instancePut.object() != receiver
            || (instancePut.value() != receiver && !instancePut.value().isArgument())) {
          return null;
        }
        continue;
      }

      if (insn.isGoto()) {
        // Trivial goto to the next block.
        if (insn.asGoto().isTrivialGotoToTheNextBlock(code)) {
          continue;
        }
        return null;
      }

      // Other instructions make the instance initializer not eligible.
      return null;
    }
    return NonTrivialInstanceInitializerInfo.INSTANCE;
  }

  private void identifyInvokeSemanticsForInlining(
      DexEncodedMethod method, IRCode code, AppView<?> appView, OptimizationFeedback feedback) {
    if (method.isStatic()) {
      // Identifies if the method preserves class initialization after inlining.
      feedback.markTriggerClassInitBeforeAnySideEffect(
          method, triggersClassInitializationBeforeSideEffect(method.method.holder, code, appView));
    } else {
      // Identifies if the method preserves null check of the receiver after inlining.
      final Value receiver = code.getThis();
      feedback.markCheckNullReceiverBeforeAnySideEffect(
          method, receiver.isUsed() && checksNullBeforeSideEffect(code, receiver, appView));
    }
  }

  /**
   * Returns true if the given code unconditionally triggers class initialization before any other
   * side effecting instruction.
   *
   * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
   */
  private static boolean triggersClassInitializationBeforeSideEffect(
      DexType clazz, IRCode code, AppView<?> appView) {
    return alwaysTriggerExpectedEffectBeforeAnythingElse(
        code,
        (instruction, it) -> {
          DexType context = code.method.method.holder;
          if (instruction.definitelyTriggersClassInitialization(
              clazz, context, appView, DIRECTLY, AnalysisAssumption.INSTRUCTION_DOES_NOT_THROW)) {
            // In order to preserve class initialization semantic, the exception must not be caught
            // by any handler. Therefore, we must ignore this instruction if it is covered by a
            // catch handler.
            // Note: this is a conservative approach where we consider that any catch handler could
            // catch the exception, even if it cannot catch an ExceptionInInitializerError.
            if (!instruction.getBlock().hasCatchHandlers()) {
              // We found an instruction that preserves initialization of the class.
              return InstructionEffect.DESIRED_EFFECT;
            }
          } else if (instruction.instructionMayHaveSideEffects(appView, clazz)) {
            // We found a side effect before class initialization.
            return InstructionEffect.OTHER_EFFECT;
          }
          return InstructionEffect.NO_EFFECT;
        });
  }

  /**
   * Returns true if the given code unconditionally triggers an expected effect before anything
   * else, false otherwise.
   *
   * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
   */
  private static boolean alwaysTriggerExpectedEffectBeforeAnythingElse(
      IRCode code, BiFunction<Instruction, InstructionIterator, InstructionEffect> function) {
    final int color = code.reserveMarkingColor();
    try {
      ArrayDeque<BasicBlock> worklist = new ArrayDeque<>();
      final BasicBlock entry = code.entryBlock();
      worklist.add(entry);
      entry.mark(color);

      while (!worklist.isEmpty()) {
        BasicBlock currentBlock = worklist.poll();
        assert currentBlock.isMarked(color);

        InstructionEffect result = InstructionEffect.NO_EFFECT;
        InstructionIterator it = currentBlock.iterator();
        while (result == InstructionEffect.NO_EFFECT && it.hasNext()) {
          result = function.apply(it.next(), it);
        }
        if (result == InstructionEffect.OTHER_EFFECT) {
          // We found an instruction that is causing an unexpected side effect.
          return false;
        } else if (result == InstructionEffect.DESIRED_EFFECT) {
          // The current path is causing the expected effect. No need to go deeper in this path,
          // go to the next block in the work list.
          continue;
        } else if (result == InstructionEffect.CONDITIONAL_EFFECT) {
          assert !currentBlock.getNormalSuccessors().isEmpty();
          Instruction lastInstruction = currentBlock.getInstructions().getLast();
          assert lastInstruction.isIf();
          // The current path is checking if the value of interest is null. Go deeper into the path
          // that corresponds to the null value.
          BasicBlock targetIfReceiverIsNull = lastInstruction.asIf().targetFromCondition(0);
          if (!targetIfReceiverIsNull.isMarked(color)) {
            worklist.add(targetIfReceiverIsNull);
            targetIfReceiverIsNull.mark(color);
          }
        } else {
          assert result == InstructionEffect.NO_EFFECT;
          // The block did not cause any particular effect.
          if (currentBlock.getNormalSuccessors().isEmpty()) {
            // This is the end of the current non-exceptional path and we did not find any expected
            // effect. It means there is at least one path where the expected effect does not
            // happen.
            Instruction lastInstruction = currentBlock.getInstructions().getLast();
            assert lastInstruction.isReturn() || lastInstruction.isThrow();
            return false;
          } else {
            // Look into successors
            for (BasicBlock successor : currentBlock.getSuccessors()) {
              if (!successor.isMarked(color)) {
                worklist.add(successor);
                successor.mark(color);
              }
            }
          }
        }
      }
      // If we reach this point, we checked that the expected effect happens in every possible path.
      return true;
    } finally {
      code.returnMarkingColor(color);
    }
  }

  /**
   * Returns true if the given code unconditionally throws if value is null before any other side
   * effect instruction.
   *
   * <p>Note: we do not track phis so we may return false negative. This is a conservative approach.
   */
  private static boolean checksNullBeforeSideEffect(IRCode code, Value value, AppView<?> appView) {
    return alwaysTriggerExpectedEffectBeforeAnythingElse(
        code,
        (instr, it) -> {
          BasicBlock currentBlock = instr.getBlock();
          // If the code explicitly checks the nullability of the value, we should visit the next
          // block that corresponds to the null value where NPE semantic could be preserved.
          if (!currentBlock.hasCatchHandlers() && isNullCheck(instr, value)) {
            return InstructionEffect.CONDITIONAL_EFFECT;
          }
          if (isKotlinNullCheck(instr, value, appView)) {
            DexMethod invokedMethod = instr.asInvokeStatic().getInvokedMethod();
            // Kotlin specific way of throwing NPE: throwParameterIsNullException.
            // Similarly, combined with the above CONDITIONAL_EFFECT, the code checks on NPE on
            // the value.
            if (invokedMethod.name
                == appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException.name) {
              // We found a NPE (or similar exception) throwing code.
              // Combined with the above CONDITIONAL_EFFECT, the code checks NPE on the value.
              for (BasicBlock predecessor : currentBlock.getPredecessors()) {
                if (isNullCheck(predecessor.exit(), value)) {
                  return InstructionEffect.DESIRED_EFFECT;
                }
              }
              // Hitting here means that this call might be used for other parameters. If we don't
              // bail out, it will be regarded as side effects for the current value.
              return InstructionEffect.NO_EFFECT;
            } else {
              // Kotlin specific way of checking parameter nullness: checkParameterIsNotNull.
              assert invokedMethod.name
                  == appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull.name;
              return InstructionEffect.DESIRED_EFFECT;
            }
          }
          if (isInstantiationOfNullPointerException(instr, it, appView.dexItemFactory())) {
            it.next(); // Skip call to NullPointerException.<init>.
            return InstructionEffect.NO_EFFECT;
          } else if (instr.throwsNpeIfValueIsNull(value, appView.dexItemFactory())) {
            // In order to preserve NPE semantic, the exception must not be caught by any handler.
            // Therefore, we must ignore this instruction if it is covered by a catch handler.
            // Note: this is a conservative approach where we consider that any catch handler could
            // catch the exception, even if it cannot catch a NullPointerException.
            if (!currentBlock.hasCatchHandlers()) {
              // We found a NPE check on the value.
              return InstructionEffect.DESIRED_EFFECT;
            }
          } else if (instr.instructionMayHaveSideEffects(appView, code.method.method.holder)) {
            // If the current instruction is const-string, this could load the parameter name.
            // Just make sure it is indeed not throwing.
            if (instr.isConstString() && !instr.instructionInstanceCanThrow()) {
              return InstructionEffect.NO_EFFECT;
            }
            // We found a side effect before a NPE check.
            return InstructionEffect.OTHER_EFFECT;
          }
          return InstructionEffect.NO_EFFECT;
        });
  }

  /**
   * An enum used to classify instructions according to a particular effect that they produce.
   *
   * The "effect" of an instruction can be seen as a program state change (or semantic change) at
   * runtime execution. For example, an instruction could cause the initialization of a class,
   * change the value of a field, ... while other instructions do not.
   *
   * This classification also depends on the type of analysis that is using it. For instance, an
   * analysis can look for instructions that cause class initialization while another look for
   * instructions that check nullness of a particular object.
   *
   * On the other hand, some instructions may provide a non desired effect which is a signal for
   * the analysis to stop.
   */
  private enum InstructionEffect {
    DESIRED_EFFECT,
    CONDITIONAL_EFFECT,
    OTHER_EFFECT,
    NO_EFFECT
  }

  // Note that this method may have false positives, since the application could in principle
  // declare a method called checkParameterIsNotNull(parameter, message) or
  // throwParameterIsNullException(parameterName) in a package that starts with "kotlin".
  private static boolean isKotlinNullCheck(Instruction instr, Value value, AppView<?> appView) {
    if (!instr.isInvokeStatic()) {
      return false;
    }
    // We need to strip the holder, since Kotlin adds different versions of null-check machinery,
    // e.g., kotlin.collections.ArraysKt___ArraysKt... or kotlin.jvm.internal.ArrayIteratorKt...
    MethodSignatureEquivalence wrapper = MethodSignatureEquivalence.get();
    Wrapper<DexMethod> checkParameterIsNotNull =
        wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.checkParameterIsNotNull);
    Wrapper<DexMethod> throwParamIsNullException =
        wrapper.wrap(appView.dexItemFactory().kotlin.intrinsics.throwParameterIsNullException);
    DexMethod invokedMethod =
        appView.graphLense().getOriginalMethodSignature(instr.asInvokeStatic().getInvokedMethod());
    Wrapper<DexMethod> methodWrap = wrapper.wrap(invokedMethod);
    if (methodWrap.equals(throwParamIsNullException)
        || (methodWrap.equals(checkParameterIsNotNull) && instr.inValues().get(0).equals(value))) {
      if (invokedMethod.holder.getPackageDescriptor().startsWith(Kotlin.NAME)) {
        return true;
      }
    }
    return false;
  }

  private static boolean isNullCheck(Instruction instr, Value value) {
    return instr.isIf() && instr.asIf().isZeroTest()
        && instr.inValues().get(0).equals(value)
        && (instr.asIf().getType() == If.Type.EQ || instr.asIf().getType() == If.Type.NE);
  }

  /**
   * Returns true if the given instruction is {@code v <- new-instance NullPointerException}, and
   * the next instruction is {@code invoke-direct v, NullPointerException.<init>()}.
   */
  private static boolean isInstantiationOfNullPointerException(
      Instruction instruction, InstructionIterator it, DexItemFactory dexItemFactory) {
    if (!instruction.isNewInstance()
        || instruction.asNewInstance().clazz != dexItemFactory.npeType) {
      return false;
    }
    Instruction next = it.peekNext();
    if (next == null
        || !next.isInvokeDirect()
        || next.asInvokeDirect().getInvokedMethod() != dexItemFactory.npeMethods.init) {
      return false;
    }
    return true;
  }

  private void computeDynamicReturnType(
      DynamicTypeOptimization dynamicTypeOptimization,
      OptimizationFeedback feedback,
      DexEncodedMethod method,
      IRCode code) {
    if (dynamicTypeOptimization != null) {
      DexType staticReturnTypeRaw = method.method.proto.returnType;
      if (!staticReturnTypeRaw.isReferenceType()) {
        return;
      }
      TypeLatticeElement dynamicReturnType =
          dynamicTypeOptimization.computeDynamicReturnType(method, code);
      if (dynamicReturnType != null) {
        TypeLatticeElement staticReturnType =
            TypeLatticeElement.fromDexType(staticReturnTypeRaw, Nullability.maybeNull(), appView);
        // If the dynamic return type is not more precise than the static return type there is no
        // need to record it.
        if (dynamicReturnType.strictlyLessThan(staticReturnType, appView)) {
          feedback.methodReturnsObjectWithUpperBoundType(method, appView, dynamicReturnType);
        }
      }
      ClassTypeLatticeElement exactReturnType =
          dynamicTypeOptimization.computeDynamicLowerBoundType(method, code);
      if (exactReturnType != null) {
        feedback.methodReturnsObjectWithLowerBoundType(method, exactReturnType);
      }
    }
  }

  private void computeInitializedClassesOnNormalExit(
      OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
    if (options.enableInitializedClassesAnalysis && appView.appInfo().hasLiveness()) {
      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
      Set<DexType> initializedClasses =
          InitializedClassesOnNormalExitAnalysis.computeInitializedClassesOnNormalExit(
              appViewWithLiveness, code);
      if (initializedClasses != null && !initializedClasses.isEmpty()) {
        feedback.methodInitializesClassesOnNormalExit(method, initializedClasses);
      }
    }
  }

  private void computeMayHaveSideEffects(
      OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
    // If the method is native, we don't know what could happen.
    assert !method.accessFlags.isNative();
    if (!options.enableSideEffectAnalysis) {
      return;
    }
    if (appView.appInfo().withLiveness().mayHaveSideEffects.containsKey(method.method)) {
      return;
    }
    DexType context = method.method.holder;
    if (method.isClassInitializer()) {
      // For class initializers, we also wish to compute if the class initializer has observable
      // side effects.
      ClassInitializerSideEffect classInitializerSideEffect =
          ClassInitializerSideEffectAnalysis.classInitializerCanBePostponed(appView, code);
      if (classInitializerSideEffect.isNone()) {
        feedback.methodMayNotHaveSideEffects(method);
        feedback.classInitializerMayBePostponed(method);
      } else if (classInitializerSideEffect.canBePostponed()) {
        feedback.classInitializerMayBePostponed(method);
      }
      return;
    }
    boolean mayHaveSideEffects;
    if (method.accessFlags.isSynchronized()) {
      // If the method is synchronized then it acquires a lock.
      mayHaveSideEffects = true;
    } else if (method.isInstanceInitializer() && hasNonTrivialFinalizeMethod(context)) {
      // If a class T overrides java.lang.Object.finalize(), then treat the constructor as having
      // side effects. This ensures that we won't remove instructions on the form `new-instance
      // {v0}, T`.
      mayHaveSideEffects = true;
    } else {
      // Otherwise, check if there is an instruction that has side effects.
      mayHaveSideEffects =
          Streams.stream(code.instructions())
              .anyMatch(instruction -> instruction.instructionMayHaveSideEffects(appView, context));
    }
    if (!mayHaveSideEffects) {
      feedback.methodMayNotHaveSideEffects(method);
    }
  }

  // Returns true if `method` is an initializer and the enclosing class overrides the method
  // `void java.lang.Object.finalize()`.
  private boolean hasNonTrivialFinalizeMethod(DexType type) {
    DexClass clazz = appView.definitionFor(type);
    if (clazz != null) {
      if (clazz.isProgramClass() && !clazz.isInterface()) {
        DexItemFactory dexItemFactory = appView.dexItemFactory();
        ResolutionResult resolutionResult =
            appView
                .appInfo()
                .resolveMethodOnClass(clazz, appView.dexItemFactory().objectMethods.finalize);
        for (DexEncodedMethod target : resolutionResult.asListOfTargets()) {
          if (target.method != dexItemFactory.enumMethods.finalize
              && target.method != dexItemFactory.objectMethods.finalize) {
            return true;
          }
        }
        return false;
      } else {
        // Conservatively report that the library class could implement finalize().
        return true;
      }
    }
    return false;
  }

  private void computeReturnValueOnlyDependsOnArguments(
      OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
    if (!options.enableDeterminismAnalysis) {
      return;
    }
    boolean returnValueOnlyDependsOnArguments =
        DeterminismAnalysis.returnValueOnlyDependsOnArguments(appView.withLiveness(), code);
    if (returnValueOnlyDependsOnArguments) {
      feedback.methodReturnValueOnlyDependsOnArguments(method);
    }
  }

  // Track usage of parameters and compute their nullability and possibility of NPE.
  private void computeNonNullParamOrThrow(
      OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
    if (method.getOptimizationInfo().getNonNullParamOrThrow() != null) {
      return;
    }
    List<Value> arguments = code.collectArguments();
    BitSet paramsCheckedForNull = new BitSet();
    for (int index = 0; index < arguments.size(); index++) {
      Value argument = arguments.get(index);
      // This handles cases where the parameter is checked via Kotlin Intrinsics:
      //
      //   kotlin.jvm.internal.Intrinsics.checkParameterIsNotNull(param, message)
      //
      // or its inlined version:
      //
      //   if (param != null) return;
      //   invoke-static throwParameterIsNullException(msg)
      //
      // or some other variants, e.g., throw null or NPE after the direct null check.
      if (argument.isUsed() && checksNullBeforeSideEffect(code, argument, appView)) {
        paramsCheckedForNull.set(index);
      }
    }
    if (paramsCheckedForNull.length() > 0) {
      feedback.setNonNullParamOrThrow(method, paramsCheckedForNull);
    }
  }

  private void computeNonNullParamOnNormalExits(OptimizationFeedback feedback, IRCode code) {
    Set<BasicBlock> normalExits = Sets.newIdentityHashSet();
    normalExits.addAll(code.computeNormalExitBlocks());
    DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
    List<Value> arguments = code.collectArguments();
    BitSet facts = new BitSet();
    Set<BasicBlock> nullCheckedBlocks = Sets.newIdentityHashSet();
    for (int index = 0; index < arguments.size(); index++) {
      Value argument = arguments.get(index);
      // Consider reference-type parameter only.
      if (!argument.getTypeLattice().isReference()) {
        continue;
      }
      // The receiver is always non-null on normal exits.
      if (argument.isThis()) {
        facts.set(index);
        continue;
      }
      // Collect basic blocks that check nullability of the parameter.
      nullCheckedBlocks.clear();
      for (Instruction user : argument.uniqueUsers()) {
        if (user.isAssumeNonNull()) {
          nullCheckedBlocks.add(user.asAssumeNonNull().getBlock());
        }
        if (user.isIf()
            && user.asIf().isZeroTest()
            && (user.asIf().getType() == If.Type.EQ || user.asIf().getType() == If.Type.NE)) {
          nullCheckedBlocks.add(user.asIf().targetFromNonNullObject());
        }
      }
      if (!nullCheckedBlocks.isEmpty()) {
        boolean allExitsCovered = true;
        for (BasicBlock normalExit : normalExits) {
          if (!isNormalExitDominated(normalExit, code, dominatorTree, nullCheckedBlocks)) {
            allExitsCovered = false;
            break;
          }
        }
        if (allExitsCovered) {
          facts.set(index);
        }
      }
    }
    if (facts.length() > 0) {
      feedback.setNonNullParamOnNormalExits(code.method, facts);
    }
  }

  private boolean isNormalExitDominated(
      BasicBlock normalExit,
      IRCode code,
      DominatorTree dominatorTree,
      Set<BasicBlock> nullCheckedBlocks) {
    // Each normal exit should be...
    for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
      // A) ...directly dominated by any null-checked block.
      if (dominatorTree.dominatedBy(normalExit, nullCheckedBlock)) {
        return true;
      }
    }
    // B) ...or indirectly dominated by null-checked blocks.
    // Although the normal exit is not dominated by any of null-checked blocks (because of other
    // paths to the exit), it could be still the case that all possible paths to that exit should
    // pass some of null-checked blocks.
    Set<BasicBlock> visited = Sets.newIdentityHashSet();
    // Initial fan-out of predecessors.
    Deque<BasicBlock> uncoveredPaths = new ArrayDeque<>(normalExit.getPredecessors());
    while (!uncoveredPaths.isEmpty()) {
      BasicBlock uncoveredPath = uncoveredPaths.poll();
      // Stop traversing upwards if we hit the entry block: if the entry block has an non-null,
      // this case should be handled already by A) because the entry block surely dominates all
      // normal exits.
      if (uncoveredPath == code.entryBlock()) {
        return false;
      }
      // Make sure we're not visiting the same block over and over again.
      if (!visited.add(uncoveredPath)) {
        // But, if that block is the last one in the queue, the normal exit is not fully covered.
        if (uncoveredPaths.isEmpty()) {
          return false;
        } else {
          continue;
        }
      }
      boolean pathCovered = false;
      for (BasicBlock nullCheckedBlock : nullCheckedBlocks) {
        if (dominatorTree.dominatedBy(uncoveredPath, nullCheckedBlock)) {
          pathCovered = true;
          break;
        }
      }
      if (!pathCovered) {
        // Fan out predecessors one more level.
        // Note that remaining, unmatched null-checked blocks should cover newly added paths.
        uncoveredPaths.addAll(uncoveredPath.getPredecessors());
      }
    }
    // Reaching here means that every path to the given normal exit is covered by the set of
    // null-checked blocks.
    assert uncoveredPaths.isEmpty();
    return true;
  }
}