//===--- RCIdentityAnalysis.cpp -------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SIL/SILInstruction.h"
#include "llvm/Support/CommandLine.h"

using namespace swift;

//===----------------------------------------------------------------------===//
//                                  Utility
//===----------------------------------------------------------------------===//

/// Returns true if V is an enum without a payload.
///
/// We perform this computation by checking if V is an enum instruction without
/// an argument. I am using a helper here in case I find more cases where I need
/// to expand it.
static bool isNoPayloadEnum(SILValue V) {
  auto *EI = dyn_cast<EnumInst>(V);
  if (!EI)
    return false;

  return !EI->hasOperand();
}

/// RC identity is more than a guarantee that references refer to the same
/// object. It also means that reference counting operations on those references
/// have the same semantics. If the types on either side of a cast do not have
/// equivalent reference counting semantics, then the source and destination
/// values are not RC identical. For example, unchecked_addr_cast does not
/// necessarily preserve RC identity because it may cast from a
/// reference-counted type to a non-reference counted type, or from a larger to
/// a smaller struct with fewer references.
static bool isRCIdentityPreservingCast(ValueKind Kind) {
  switch (Kind) {
  case ValueKind::UpcastInst:
  case ValueKind::UncheckedRefCastInst:
  case ValueKind::UnconditionalCheckedCastInst:
  case ValueKind::InitExistentialRefInst:
  case ValueKind::OpenExistentialRefInst:
  case ValueKind::RefToBridgeObjectInst:
  case ValueKind::BridgeObjectToRefInst:
  case ValueKind::ConvertFunctionInst:
    return true;
  default:
    return false;
  }
}

//===----------------------------------------------------------------------===//
//                    RC Identity Root Instruction Casting
//===----------------------------------------------------------------------===//

static SILValue stripRCIdentityPreservingInsts(SILValue V) {
  // First strip off RC identity preserving casts.
  if (isRCIdentityPreservingCast(V->getKind()))
    return cast<SingleValueInstruction>(V)->getOperand(0);

  // Then if we have a struct_extract that is extracting a non-trivial member
  // from a struct with no other non-trivial members, a ref count operation on
  // the struct is equivalent to a ref count operation on the extracted
  // member. Strip off the extract.
  if (auto *SEI = dyn_cast<StructExtractInst>(V))
    if (SEI->isFieldOnlyNonTrivialField())
      return SEI->getOperand();

  // If we have a struct instruction with only one non-trivial stored field, the
  // only reference count that can be modified is the non-trivial field. Return
  // the non-trivial field.
  if (auto *SI = dyn_cast<StructInst>(V))
    if (SILValue NewValue = SI->getUniqueNonTrivialFieldValue())
      return NewValue;

  // If we have an unchecked_enum_data, strip off the unchecked_enum_data.
  if (auto *UEDI = dyn_cast<UncheckedEnumDataInst>(V))
    return UEDI->getOperand();

  // If we have an enum instruction with a payload, strip off the enum to
  // expose the enum's payload.
  if (auto *EI = dyn_cast<EnumInst>(V))
    if (EI->hasOperand())
      return EI->getOperand();

  // If we have a tuple_extract that is extracting the only non trivial member
  // of a tuple, a retain_value on the tuple is equivalent to a retain_value on
  // the extracted value.
  if (auto *TEI = dyn_cast<TupleExtractInst>(V))
    if (TEI->isEltOnlyNonTrivialElt())
      return TEI->getOperand();

  // If we are forming a tuple and the tuple only has one element with reference
  // semantics, a retain_value on the tuple is equivalent to a retain value on
  // the tuple operand.
  if (auto *TI = dyn_cast<TupleInst>(V))
    if (SILValue NewValue = TI->getUniqueNonTrivialElt())
      return NewValue;

  // Any SILArgument with a single predecessor from a "phi" perspective is
  // dead. In such a case, the SILArgument must be rc-identical.
  //
  // This is the easy case. The difficult case is when you have an argument with
  // /multiple/ predecessors.
  //
  // We do not need to insert this SILArgument into the visited SILArgument set
  // since we will only visit it twice if we go around a back edge due to a
  // different SILArgument that is actually being used for its phi node like
  // purposes.
  if (auto *A = dyn_cast<SILPHIArgument>(V))
    if (SILValue Result = A->getSingleIncomingValue())
      return Result;

  return SILValue();
}

//===----------------------------------------------------------------------===//
//                  RC Identity Dominance Argument Analysis
//===----------------------------------------------------------------------===//

/// Returns true if FirstIV is a SILArgument or SILInstruction in a BB that
/// dominates the BB of A.
static bool dominatesArgument(DominanceInfo *DI, SILArgument *A,
                              SILValue FirstIV) {
  SILBasicBlock *OtherBB = FirstIV->getParentBlock();
  if (!OtherBB || OtherBB == A->getParent())
    return false;
  return DI->dominates(OtherBB, A->getParent());
}

/// V is the incoming value for the SILArgument A on at least one path.  Find a
/// value that is trivially RC-identical to V and dominates the argument's
/// block. If such a value exists, it is a candidate for RC-identity with the
/// argument itself--the caller must verify this after evaluating all paths.
SILValue RCIdentityFunctionInfo::stripOneRCIdentityIncomingValue(SILArgument *A,
                                                             SILValue V) {
  // Strip off any non-argument instructions from IV. We know that this will
  // always result in RCIdentical values without additional analysis.
  while (SILValue NewIV = stripRCIdentityPreservingInsts(V))
    V = NewIV;

  // Then make sure that this incoming value is from a BB which is different
  // from our BB and dominates our BB. Otherwise, return SILValue() to bail.
  DominanceInfo *DI = DA->get(A->getFunction());
  if (!dominatesArgument(DI, A, V))
    return SILValue();

  // In the future attempt to recursively strip here. We are being more
  // conservative than most likely necessary.
  return V;
}

/// Returns true if we proved that RCIdentity has a non-payloaded enum case,
/// false if RCIdentity has a payloaded enum case, and None if we failed to find
/// anything.
static llvm::Optional<bool> proveNonPayloadedEnumCase(SILBasicBlock *BB,
                                                      SILValue RCIdentity) {
  // Then see if BB has one predecessor... if it does not, return None so we
  // keep searching up the domtree.
  SILBasicBlock *SinglePred = BB->getSinglePredecessorBlock();
  if (!SinglePred)
    return None;

  // Check if SinglePred has a switch_enum terminator switching on
  // RCIdentity... If it does not, return None so we keep searching up the
  // domtree.
  auto *SEI = dyn_cast<SwitchEnumInst>(SinglePred->getTerminator());
  if (!SEI || SEI->getOperand() != RCIdentity)
    return None;

  // Then return true if along the edge from the SEI to BB, RCIdentity has a
  // non-payloaded enum value.
  NullablePtr<EnumElementDecl> Decl = SEI->getUniqueCaseForDestination(BB);
  if (Decl.isNull())
    return None;
  return !Decl.get()->hasAssociatedValues();
}

bool RCIdentityFunctionInfo::
findDominatingNonPayloadedEdge(SILBasicBlock *IncomingEdgeBB,
                               SILValue RCIdentity) {
  // First grab the NonPayloadedEnumBB and RCIdentityBB. If we cannot find
  // either of them, return false.
  SILBasicBlock *RCIdentityBB = RCIdentity->getParentBlock();
  if (!RCIdentityBB)
    return false;

  // Make sure that the incoming edge bb is not the RCIdentityBB. We are not
  // trying to handle this case here, so simplify by just bailing if we detect
  // it.
  //
  // I think the only way this can happen is if we have a switch_enum of some
  // sort with multiple incoming values going into the destination BB. We are
  // not interested in handling that case anyways.
  //
  // FIXME: If we ever split all critical edges, this should be relooked at.
  if (IncomingEdgeBB == RCIdentityBB)
    return false;

  // Now we know that RCIdentityBB and IncomingEdgeBB are different. Prove that
  // RCIdentityBB dominates IncomingEdgeBB.
  SILFunction *F = RCIdentityBB->getParent();

  // First make sure that IncomingEdgeBB dominates NonPayloadedEnumBB. If not,
  // return false.
  DominanceInfo *DI = DA->get(F);
  if (!DI->dominates(RCIdentityBB, IncomingEdgeBB))
    return false;

  // Now walk up the dominator tree from IncomingEdgeBB to RCIdentityBB and see
  // if we can find a use of RCIdentity that dominates IncomingEdgeBB and
  // enables us to know that RCIdentity must be a no-payload enum along
  // IncomingEdge. We don't care if the case or enum of RCIdentity match the
  // case or enum along RCIdentityBB since a pairing of retain, release of two
  // non-payloaded enums can always be eliminated (since we can always eliminate
  // ref count operations on non-payloaded enums).

  // RCIdentityBB must have a valid dominator tree node.
  auto *EndDomNode = DI->getNode(RCIdentityBB);
  if (!EndDomNode)
    return false;

  for (auto *Node = DI->getNode(IncomingEdgeBB); Node; Node = Node->getIDom()) {
    // Search for uses of RCIdentity in Node->getBlock() that will enable us to
    // know that it has a non-payloaded enum case.
    SILBasicBlock *DominatingBB = Node->getBlock();
    llvm::Optional<bool> Result =
        proveNonPayloadedEnumCase(DominatingBB, RCIdentity);

    // If we found either a signal of a payloaded or a non-payloaded enum,
    // return that value.
    if (Result.hasValue())
      return Result.getValue();

    // If we didn't reach RCIdentityBB, keep processing up the DomTree.
    if (DominatingBB != RCIdentityBB)
      continue;

    // Otherwise, we failed to find any interesting information, return false.
    return false;
  }

  return false;
}

static SILValue allIncomingValuesEqual(
    llvm::SmallVectorImpl<std::pair<SILBasicBlock *,
                                    SILValue >> &IncomingValues) {
  SILValue First = stripRCIdentityPreservingInsts(IncomingValues[0].second);
  if (std::all_of(std::next(IncomingValues.begin()), IncomingValues.end(),
                     [&First](std::pair<SILBasicBlock *, SILValue> P) -> bool {
                       return stripRCIdentityPreservingInsts(P.second) == First;
                     }))
    return First;
  return SILValue();
}

/// Return the underlying SILValue after stripping off SILArguments that cannot
/// affect RC identity.
///
/// This code is meant to enable RCIdentity to be ascertained in the following
/// cases:
///
/// 1. Where we have an unneeded phi node (i.e. all incoming values are the same
/// argument). This helps to avoid phase ordering issues (simplify-cfg *should*
/// catch this).
///
/// 2. Cases where we break apart an enum and then reform it from its individual
/// cases. The main problem here is when the non-payloaded cases are created
/// with new enum instructions (which happens when casting sometimes):
///
///   bb9:
///     ...
///     switch_enum %0 : $Optional<T>, #Optional.none: bb10,
///                                    #Optional.some: bb11
///
///   bb10:
///     %1 = enum $Optional<U>, #Optional.none
///     br bb12(%1 : $Optional<U>)
///
///   bb11:
///     %2 = some_cast_to_u %0 : ...
///     %3 = enum $Optional<U>, #Optional.some, %2 : $U
///     br bb12(%3 : $Optional<U>)
///
///   bb12(%4 : $Optional<U>):
///     ...
///
/// In this case, we want to be able to infer that %0 and %4 have the same ref
/// count identity. The key thing we have to be careful of is that %0 must have
/// the same enum case as %1 along the edge from bb10 to bb12. Otherwise, we can
/// potentially mismatch
SILValue RCIdentityFunctionInfo::stripRCIdentityPreservingArgs(SILValue V,
                                                      unsigned RecursionDepth) {
  auto *A = dyn_cast<SILPHIArgument>(V);
  if (!A) {
    return SILValue();
  }

  // If we already visited this BB, don't reprocess it since we have a cycle.
  if (!VisitedArgs.insert(A).second) {
    return SILValue();
  }

  // Ok, this is the first time that we have visited this BB. Get the
  // SILArgument's incoming values. If we don't have an incoming value for each
  // one of our predecessors, just return SILValue().
  llvm::SmallVector<std::pair<SILBasicBlock *, SILValue>, 8> IncomingValues;
  if (!A->getIncomingValues(IncomingValues) || IncomingValues.empty()) {
    return SILValue();
  }

  unsigned IVListSize = IncomingValues.size();

  assert(IVListSize != 1 && "Should have been handled in "
         "stripRCIdentityPreservingInsts");

  // Ok, we have multiple predecessors. See if all of them are the same
  // value. If so, just return that value.
  //
  // This returns a SILValue to save a little bit of compile time since we
  // already compute that value here.
  if (SILValue V = allIncomingValuesEqual(IncomingValues))
    return V;

  // Ok, we have multiple predecessors. First find the first non-payloaded enum.
  llvm::SmallVector<SILBasicBlock *, 8> NoPayloadEnumBBs;
  unsigned i = 0;
  for (; i < IVListSize && isNoPayloadEnum(IncomingValues[i].second); ++i) {
    NoPayloadEnumBBs.push_back(IncomingValues[i].first);
  }

  // If we did not find any non-payloaded enum, there is no RC associated with
  // this Phi node. Just return SILValue().
  if (i == IVListSize)
    return SILValue();

  SILValue FirstIV =
      stripOneRCIdentityIncomingValue(A, IncomingValues[i].second);
  if (!FirstIV)
    return SILValue();

  while (i < IVListSize) {
    SILBasicBlock *IVBB;
    SILValue IV;
    std::tie(IVBB, IV) = IncomingValues[i++];

    // If IV is a no payload enum, we don't care about it. Skip it.
    if (isNoPayloadEnum(IV)) {
      NoPayloadEnumBBs.push_back(IVBB);
      continue;
    }

    // Try to strip off the RCIdentityPreservingArg for IV. If it matches
    // FirstIV, we may be able to succeed here.
    if (FirstIV == stripOneRCIdentityIncomingValue(A, IV))
      continue;

    // Otherwise, just return SILValue().
    return SILValue();
  }

  // We now know that all incoming values, other than NoPayloadEnums, are
  // FirstIV after trivially stripping RCIdentical instructions. If we have no
  // NoPayloadEnums, then we know that this Arg's RCIdentity must be FirstIV.
  if (NoPayloadEnumBBs.empty())
    return FirstIV;

  // At this point, we know that we have *some* NoPayloadEnums. If FirstIV is
  // not an enum, then we must bail. We do not try to analyze this case.
  if (!FirstIV->getType().getEnumOrBoundGenericEnum())
    return SILValue();

  // Now we know that FirstIV is an enum and that all payloaded enum cases after
  // just stripping off instructions are FirstIV. Now we need to make sure that
  // each non-payloaded enum value is safe to ignore.
  //
  // Let IVE be the edge for the non-payloaded enum. It is only safe to perform
  // this operation when there exists a dominating edge E' of IVE for which
  // FirstIV also takes on a non-payloaded enum value.
  if (std::any_of(NoPayloadEnumBBs.begin(), NoPayloadEnumBBs.end(),
                  [&](SILBasicBlock *BB) -> bool {
                    return !findDominatingNonPayloadedEdge(BB, FirstIV);
                  }))
    return SILValue();

  // Ok all our values match! Return FirstIV.
  return FirstIV;
}

llvm::cl::opt<bool> StripOffArgs(
    "enable-rc-identity-arg-strip", llvm::cl::init(true),
    llvm::cl::desc("Should RC identity try to strip off arguments"));

//===----------------------------------------------------------------------===//
//                   Top Level RC Identity Root Entrypoints
//===----------------------------------------------------------------------===//

SILValue RCIdentityFunctionInfo::stripRCIdentityPreservingOps(SILValue V,
                                                      unsigned RecursionDepth) {
  while (true) {
    // First strip off any RC identity preserving instructions. This is cheap.
    if (SILValue NewV = stripRCIdentityPreservingInsts(V)) {
      V = NewV;
      continue;
    }

    if (!StripOffArgs)
      break;

    // Once we have done all of the easy work, try to see if we can strip off
    // any RCIdentityPreserving args. This is potentially expensive since we
    // need to perform additional stripping on the argument provided to this
    // argument from each predecessor BB. There is a counter in
    // getRCIdentityRootInner that ensures we don't do too many.
    SILValue NewV = stripRCIdentityPreservingArgs(V, RecursionDepth);
    if (!NewV)
      break;

    V = NewV;
  }

  return V;
}


SILValue RCIdentityFunctionInfo::getRCIdentityRootInner(SILValue V,
                                                    unsigned RecursionDepth) {
  // Only allow this method to be recursed on for a limited number of times to
  // make sure we don't explode compile time.
  if (RecursionDepth >= MaxRecursionDepth)
    return SILValue();

  SILValue NewValue = stripRCIdentityPreservingOps(V, RecursionDepth);
  if (!NewValue)
    return SILValue();

  // We can get back V if our analysis completely fails. There is no point in
  // storing this value into the cache so just return it.
  if (NewValue == V)
    return V;

  return NewValue;
}

SILValue RCIdentityFunctionInfo::getRCIdentityRoot(SILValue V) {
  // Do we have it in the RCCache ?
  auto Iter = RCCache.find(V);
  if (Iter != RCCache.end())
    return Iter->second;

  SILValue Root = getRCIdentityRootInner(V, 0);
  VisitedArgs.clear();

  // If we fail to find a root, return V.
  if (!Root)
    return V;

  // Make sure the cache does not grow too big.
  if (RCCache.size() > MaxRCIdentityCacheSize)
    RCCache.clear();

  // Return and cache it.
  return RCCache[V] = Root;
}

//===----------------------------------------------------------------------===//
//                              RCUser Analysis
//===----------------------------------------------------------------------===//

/// Is this a user that represents an escape of user from ARC control. This
/// means that from an RC use perspective, the object can be ignored since it is
/// up to the frontend to communicate via fix_lifetime and mark_dependence these
/// dependencies.
static bool isNonOverlappingTrivialAccess(SILValue value) {
  if (auto *TEI = dyn_cast<TupleExtractInst>(value)) {
    // If the tuple we are extracting from only has one non trivial element and
    // we are not extracting from that element, this is an ARC escape.
    return TEI->isTrivialEltOfOneRCIDTuple();
  }

  if (auto *SEI = dyn_cast<StructExtractInst>(value)) {
    // If the struct we are extracting from only has one non trivial element and
    // we are not extracting from that element, this is an ARC escape.
    return SEI->isTrivialFieldOfOneRCIDStruct();
  }

  return false;
}

/// Return all recursive users of V, looking through users which propagate
/// RCIdentity. *NOTE* This ignores obvious ARC escapes where the a potential
/// user of the RC is not managed by ARC.
///
/// We only use the instruction analysis here.
void RCIdentityFunctionInfo::getRCUsers(
    SILValue InputValue, llvm::SmallVectorImpl<SILInstruction *> &Users) {
  // Add V to the worklist.
  llvm::SmallVector<SILValue, 8> Worklist;
  Worklist.push_back(InputValue);

  // A set used to ensure we only visit users once.
  llvm::SmallPtrSet<SILInstruction *, 8> VisitedInsts;

  // Then until we finish the worklist...
  while (!Worklist.empty()) {
    // Pop off the top value.
    SILValue V = Worklist.pop_back_val();

    // For each user of V...
    for (auto *Op : V->getUses()) {
      SILInstruction *User = Op->getUser();

      // If we have already visited this user, continue.
      if (!VisitedInsts.insert(User).second)
        continue;

      for (auto value : User->getResults()) {
        // Otherwise attempt to strip off one layer of RC identical instructions
        // from User.
        SILValue StrippedRCID = stripRCIdentityPreservingInsts(value);

        // If StrippedRCID is not V, then we know that User's result is
        // conservatively not RCIdentical to V.
        if (StrippedRCID != V) {
          // If the user is extracting a trivial field of an aggregate structure
          // that does not overlap with the ref counted part of the aggregate, we
          // can ignore it.
          if (isNonOverlappingTrivialAccess(value))
            continue;

          // Otherwise, it is an RC user that our user wants.
          Users.push_back(User);
          continue;
        }

        // Otherwise, add the result to our list to continue searching.
        Worklist.push_back(value);
      }
    }
  }
}

//===----------------------------------------------------------------------===//
//                              Main Entry Point
//===----------------------------------------------------------------------===//

void RCIdentityAnalysis::initialize(SILPassManager *PM) {
  DA = PM->getAnalysis<DominanceAnalysis>();
}

SILAnalysis *swift::createRCIdentityAnalysis(SILModule *M) {
  return new RCIdentityAnalysis(M);
}