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

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.utils.BooleanLatticeElement;
import com.android.tools.r8.utils.OptionalBool;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;

/**
 * This analysis determines whether a method returns the receiver. The analysis is specific to the
 * class inliner, and the result is therefore not sound in general.
 *
 * <p>The analysis makes the following assumptions.
 *
 * <ul>
 *   <li>None of the given method's arguments is an alias of the receiver (except for the receiver
 *       itself).
 *   <li>The receiver is not stored in the heap. Thus, it is guaranteed that (i) all field-get
 *       instructions do not return an alias of the receiver, and (ii) invoke instructions can only
 *       return an alias of the receiver if the receiver is given as an argument.
 * </ul>
 */
public class ClassInlinerReceiverAnalysis {

  private final AppView<?> appView;
  private final DexEncodedMethod method;
  private final IRCode code;
  private final Value receiver;

  private final Map<Value, OptionalBool> isReceiverAliasCache = new IdentityHashMap<>();

  public ClassInlinerReceiverAnalysis(AppView<?> appView, DexEncodedMethod method, IRCode code) {
    this.appView = appView;
    this.method = method;
    this.code = code;
    this.receiver = code.getThis();
    assert !receiver.hasAliasedValue();
    assert receiver.getTypeLattice().isClassType();
  }

  public OptionalBool computeReturnsReceiver() {
    if (method.method.proto.returnType.isVoidType()) {
      return OptionalBool.FALSE;
    }

    List<BasicBlock> normalExitBlocks = code.computeNormalExitBlocks();
    if (normalExitBlocks.isEmpty()) {
      return OptionalBool.FALSE;
    }

    BooleanLatticeElement result = OptionalBool.BOTTOM;
    for (BasicBlock block : normalExitBlocks) {
      Value returnValue = block.exit().asReturn().returnValue();
      result = result.join(getOrComputeIsReceiverAlias(returnValue));

      // Stop as soon as we reach unknown.
      if (result.isUnknown()) {
        return OptionalBool.UNKNOWN;
      }
    }
    assert !result.isBottom();
    return result.asOptionalBool();
  }

  private OptionalBool getOrComputeIsReceiverAlias(Value value) {
    Value root = value.getAliasedValue();
    return isReceiverAliasCache.computeIfAbsent(root, this::computeIsReceiverAlias);
  }

  private OptionalBool computeIsReceiverAlias(Value value) {
    assert !value.hasAliasedValue();

    if (value == receiver) {
      // Guaranteed to return the receiver.
      return OptionalBool.TRUE;
    }

    ClassTypeLatticeElement valueType = value.getTypeLattice().asClassTypeLatticeElement();
    if (valueType == null) {
      return OptionalBool.FALSE;
    }

    ClassTypeLatticeElement receiverType = receiver.getTypeLattice().asClassTypeLatticeElement();
    if (!valueType.isRelatedTo(receiverType, appView)) {
      // Guaranteed not to return the receiver.
      return OptionalBool.FALSE;
    }

    if (value.isPhi()) {
      // Not sure what is returned.
      return OptionalBool.UNKNOWN;
    }

    Instruction definition = value.definition;
    if (definition.isArrayGet() || definition.isFieldGet()) {
      // Guaranteed not to return the receiver, since the class inliner does not allow the
      // receiver to flow into any arrays or fields.
      return OptionalBool.FALSE;
    }

    if (definition.isConstInstruction() || definition.isCreatingInstanceOrArray()) {
      // Guaranteed not to return the receiver.
      return OptionalBool.FALSE;
    }

    if (definition.isInvokeMethod()) {
      // Since the class inliner does not allow the receiver to flow into the heap, the only way for
      // the invoked method to return the receiver is if one of the given arguments is an alias of
      // the receiver.
      InvokeMethod invoke = definition.asInvokeMethod();
      for (Value argument : invoke.arguments()) {
        if (getOrComputeIsReceiverAlias(argument).isPossiblyTrue()) {
          return OptionalBool.UNKNOWN;
        }
      }

      return OptionalBool.FALSE;
    }

    // Not sure what is returned.
    return OptionalBool.UNKNOWN;
  }
}