<commit_before>//===------- COWArrayOpt.cpp - Optimize Copy-On-Write Array Checks --------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "cowarray-opts"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILCloner.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SILOptimizer/Analysis/ArraySemantic.h"
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
#include "swift/SILOptimizer/Analysis/ColdBlockInfo.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SILOptimizer/Analysis/LoopAnalysis.h"
#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/CFG.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/Utils/SILSSAUpdater.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
using namespace swift;

#ifndef NDEBUG
llvm::cl::opt<std::string>
COWViewCFGFunction("view-cfg-before-cow-for", llvm::cl::init(""),
                   llvm::cl::desc("Only print out the sil for this function"));
#endif

/// \return a sequence of integers representing the access path of this element
/// within a Struct/Ref/Tuple.
///
/// Do not form a path with an IndexAddrInst because we have no way to
/// distinguish between indexing and subelement access. The same index could
/// either refer to the next element (indexed) or a subelement.
static SILValue getAccessPath(SILValue V, SmallVectorImpl<unsigned>& Path) {
  V = V.stripCasts();
  ProjectionIndex PI(V.getDef());
  if (!PI.isValid() || V->getKind() == ValueKind::IndexAddrInst)
    return V;

  SILValue UnderlyingObject = getAccessPath(PI.Aggregate, Path);
  Path.push_back(PI.Index);
  return UnderlyingObject;
}

namespace {
/// Collect all uses of a struct given an aggregate value that contains the
/// struct and access path describing the projection of the aggregate
/// that accesses the struct.
///
/// AggregateAddressUsers records uses of the aggregate value's address. These
/// may indirectly access the struct's elements.
///
/// Projections over the aggregate that do not access the struct are ignored.
///
/// StructLoads records loads of the struct value.
/// StructAddressUsers records other uses of the struct address.
/// StructValueUsers records direct uses of the loaded struct.
///
/// Projections of the struct over its elements are all similarly recorded in
/// ElementAddressUsers, ElementLoads, and ElementValueUsers.
///
/// bb0(%arg : $*S)
/// apply %f(%arg)           // <--- Aggregate Address User
/// %struct_addr = struct_element_addr %arg : $*S, #S.element
/// apply %g(%struct_addr)   // <--- Struct Address User
/// %val = load %struct_addr // <--- Struct Load
/// apply %h(%val)           // <--- Struct Value User
/// %elt_addr = struct_element_addr %struct_addr : $*A, #A.element
/// apply %i(%elt_addr)      // <--- Element Address User
/// %elt = load %elt_addr    // <--- Element Load
/// apply %j(%elt)           // <--- Element Value User
class StructUseCollector {
public:
  typedef SmallPtrSet<Operand*, 16> VisitedSet;
  typedef SmallVector<SILInstruction*, 16> UserList;

  /// Record the users of a value or an element within that value along with the
  /// operand that directly uses the value. Multiple levels of struct_extract
  /// may exist between the operand and the user instruction.
  typedef SmallVector<std::pair<SILInstruction*, Operand*>, 16> UserOperList;

  UserList AggregateAddressUsers;
  UserList StructAddressUsers;
  UserList StructLoads;
  UserList StructValueUsers;
  UserOperList ElementAddressUsers;
  UserOperList ElementLoads;
  UserOperList ElementValueUsers;
  VisitedSet Visited;

  /// Collect all uses of the value at the given address.
  void collectUses(ValueBase *V, ArrayRef<unsigned> AccessPath) {
    // Save our old indent and increment.
    // Collect all users of the address and loads.
    collectAddressUses(V, AccessPath, nullptr);

    // Collect all uses of the Struct value.
    for (auto *DefInst : StructLoads) {
      for (auto *DefUI : DefInst->getUses()) {
        if (!Visited.insert(&*DefUI).second) {
          continue;
        }

        StructValueUsers.push_back(DefUI->getUser());
      }
    }

    // Collect all users of element values.
    for (auto &Pair : ElementLoads) {
      for (auto *DefUI : Pair.first->getUses()) {
        if (!Visited.insert(&*DefUI).second) {
          continue;
        }

        ElementValueUsers.push_back(
            std::make_pair(DefUI->getUser(), Pair.second));
      }
    }
  }

protected:

  static bool definesSingleObjectType(ValueBase *V) {
    if (auto *Arg = dyn_cast<SILArgument>(V))
      return Arg->getType().isObject();
    if (auto *Inst = dyn_cast<SILInstruction>(V))
      return Inst->getNumTypes() == 1 && Inst->getType(0).isObject();
    return false;
  }

  /// If AccessPathSuffix is non-empty, then the value is the address of an
  /// aggregate containing the Struct. If AccessPathSuffix is empty and
  /// StructVal is invalid, then the value is the address of the Struct. If
  /// StructVal is valid, the value is the address of an element within the
  /// Struct.
  void collectAddressUses(ValueBase *V, ArrayRef<unsigned> AccessPathSuffix,
                          Operand *StructVal) {
    for (auto *UI : V->getUses()) {
      // Keep the operand, not the instruction in the visited set. The same
      // instruction may theoretically have different types of uses.
      if (!Visited.insert(&*UI).second) {
        continue;
      }

      SILInstruction *UseInst = UI->getUser();
      if (StructVal) {
        // Found a use of an element.
        assert(AccessPathSuffix.empty() && "should have accessed struct");
        if (auto *LoadI = dyn_cast<LoadInst>(UseInst)) {
          ElementLoads.push_back(std::make_pair(LoadI, StructVal));
          continue;
        }

        if (isa<StructElementAddrInst>(UseInst)) {
          collectAddressUses(UseInst, AccessPathSuffix, StructVal);
          continue;
        }

        ElementAddressUsers.push_back(std::make_pair(UseInst,StructVal));
        continue;
      }

      if (AccessPathSuffix.empty()) {
        // Found a use of the struct at the given access path.
        if (auto *LoadI = dyn_cast<LoadInst>(UseInst)) {
          StructLoads.push_back(LoadI);
          continue;
        }

        if (isa<StructElementAddrInst>(UseInst)) {
          collectAddressUses(UseInst, AccessPathSuffix, &*UI);
          continue;
        }

        // Value users - this happens if we start with a value object in V.
        if (definesSingleObjectType(V)) {
          StructValueUsers.push_back(UseInst);
          continue;
        }

        StructAddressUsers.push_back(UseInst);
        continue;
      }

      ProjectionIndex PI(UseInst);
      // Do not form a path from an IndexAddrInst without otherwise
      // distinguishing it from subelement addressing.
      if (!PI.isValid() || V->getKind() == ValueKind::IndexAddrInst) {
        // Found a use of an aggregate containing the given element.
        AggregateAddressUsers.push_back(UseInst);
        continue;
      }

      if (PI.Index != AccessPathSuffix[0]) {
        // Ignore uses of disjoint elements.
        continue;
      }

      // An alloc_stack returns its address as the second value.
      assert((PI.Aggregate == V || PI.Aggregate == SILValue(V, 1)) &&
             "Expected unary element addr inst.");

      // Recursively check for users after stripping this component from the
      // access path.
      collectAddressUses(UseInst, AccessPathSuffix.slice(1), nullptr);
    }
  }
};
} // namespace

// Do the two values \p A and \p B reference the same 'array' after potentially
// looking through a load. To identify a common array address this functions
// strips struct projections until it hits \p ArrayAddress.
bool areArraysEqual(RCIdentityFunctionInfo *RCIA, SILValue A, SILValue B,
                    SILValue ArrayAddress) {
  A = RCIA->getRCIdentityRoot(A);
  B = RCIA->getRCIdentityRoot(B);
  if (A == B)
    return true;
  // We have stripped off struct_extracts. Remove the load to look at the
  // address we are loading from.
  if (auto *ALoad = dyn_cast<LoadInst>(A))
    A = ALoad->getOperand();
  if (auto *BLoad = dyn_cast<LoadInst>(B))
    B = BLoad->getOperand();
  // Strip off struct_extract_refs until we hit array address.
  if (ArrayAddress) {
    StructElementAddrInst *SEAI = nullptr;
    while (A != ArrayAddress && (SEAI = dyn_cast<StructElementAddrInst>(A)))
      A = SEAI->getOperand();
    while (B != ArrayAddress && (SEAI = dyn_cast<StructElementAddrInst>(B)))
      B = SEAI->getOperand();
  }
  return A == B;
}

/// \return true if the given instruction releases the given value.
static bool isRelease(SILInstruction *Inst, SILValue RetainedValue,
                      SILValue ArrayAddress, RCIdentityFunctionInfo *RCIA,
                      SmallPtrSetImpl<Operand *> &MatchedReleases) {

  // Before we can match a release with a retain we need to check that we have
  // not already matched the release with a retain we processed earlier.
  // We don't want to match the release with both retains in the example below.
  //
  //   retain %a  <--|
  //   retain %a     | Match.   <-| Dont't match.
  //   release %a <--|          <-|
  //
  if (auto *R = dyn_cast<ReleaseValueInst>(Inst))
    if (!MatchedReleases.count(&R->getOperandRef()))
      if (areArraysEqual(RCIA, Inst->getOperand(0), RetainedValue,
                         ArrayAddress)) {
        DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
        MatchedReleases.insert(&R->getOperandRef());
        return true;
      }

  if (auto *R = dyn_cast<StrongReleaseInst>(Inst))
    if (!MatchedReleases.count(&R->getOperandRef()))
      if (areArraysEqual(RCIA, Inst->getOperand(0), RetainedValue,
                         ArrayAddress)) {
        DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
        MatchedReleases.insert(&R->getOperandRef());
        return true;
      }

  if (auto *AI = dyn_cast<ApplyInst>(Inst)) {
    if (auto *F = AI->getCalleeFunction()) {
      auto Params = F->getLoweredFunctionType()->getParameters();
      auto Args = AI->getArguments();
      for (unsigned ArgIdx = 0, ArgEnd = Params.size(); ArgIdx != ArgEnd;
           ++ArgIdx) {
        if (MatchedReleases.count(&AI->getArgumentRef(ArgIdx)))
          continue;
        if (!areArraysEqual(RCIA, Args[ArgIdx], RetainedValue, ArrayAddress))
          continue;
        ParameterConvention P = Params[ArgIdx].getConvention();
        if (P == ParameterConvention::Direct_Owned) {
          DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
          MatchedReleases.insert(&AI->getArgumentRef(ArgIdx));
          return true;
        }
      }
    }
  }
  DEBUG(llvm::dbgs() << "      not a matching release " << *Inst);
  return false;
}

namespace {

/// Optimize Copy-On-Write array checks based on high-level semantics.
///
/// Performs an analysis on all Array users to ensure they do not interfere
/// with make_mutable hoisting. Ultimately, the only thing that can interfere
/// with make_mutable is a retain of the array. To ensure no retains occur
/// within the loop, it is necessary to check that the array does not escape on
/// any path reaching the loop, and that it is not directly retained within the
/// loop itself.
///
/// In some cases, a retain does exist within the loop, but is balanced by a
/// release or call to @owned. The analysis must determine whether any array
/// mutation can occur between the retain and release. To accomplish this it
/// relies on knowledge of all array operations within the loop. If the array
/// escapes in some way that cannot be tracked, the analysis must fail.
///
/// TODO: Handle this pattern:
///   retain(array)
///   call(array)
///   release(array)
/// Whenever the call is readonly, has balanced retain/release for the array,
/// and does not capture the array. Under these conditions, the call can neither
/// mutate the array nor save an alias for later mutation.
///
/// TODO: Completely eliminate make_mutable calls if all operations that the
/// guard are already guarded by either "init" or "mutate_unknown".
class COWArrayOpt {
  typedef StructUseCollector::UserList UserList;
  typedef StructUseCollector::UserOperList UserOperList;

  RCIdentityFunctionInfo *RCIA;
  SILFunction *Function;
  SILLoop *Loop;
  SILBasicBlock *Preheader;
  DominanceInfo *DomTree;
  bool HasChanged = false;

  // Keep track of cold blocks.
  ColdBlockInfo ColdBlocks;

  // Cache of the analysis whether a loop is safe wrt. make_unique hoisting by
  // looking at the operations (no uniquely identified objects).
  std::pair<bool, bool> CachedSafeLoop;

  // Set of all blocks that may reach the loop, not including loop blocks.
  llvm::SmallPtrSet<SILBasicBlock*,32> ReachingBlocks;

  // Map an array to a hoisted make_mutable call for the current loop. An array
  // is only mapped to a call once the analysis has determined that no
  // make_mutable calls are required within the loop body for that array.
  llvm::SmallDenseMap<SILValue, ApplyInst*> ArrayMakeMutableMap;

  // \brief Transient per-Array user set.
  //
  // Track all known array users with the exception of struct_extract users
  // (checkSafeArrayElementUse prohibits struct_extract users from mutating the
  // array). During analysis of retains/releases within the loop body, the
  // users in this set are assumed to cover all possible mutating operations on
  // the array. If the array escaped through an unknown use, the analysis must
  // abort earlier.
  SmallPtrSet<SILInstruction*, 8> ArrayUserSet;

  // When matching retains to releases we must not match the same release twice.
  //
  // For example we could have:
  //   retain %a // id %1
  //   retain %a // id %2
  //   release %a // id %3
  // When we match %1 with %3, we can't match %3 again when we look for a
  // matching release for %2.
  // The set refers to operands instead of instructions because an apply could
  // have several operands with release semantics.
  SmallPtrSet<Operand*, 8> MatchedReleases;

  // The address of the array passed to the current make_mutable we are
  // analysing.
  SILValue CurrentArrayAddr;
public:
  COWArrayOpt(RCIdentityFunctionInfo *RCIA, SILLoop *L,
              DominanceAnalysis *DA)
      : RCIA(RCIA), Function(L->getHeader()->getParent()), Loop(L),
        Preheader(L->getLoopPreheader()), DomTree(DA->get(Function)),
        ColdBlocks(DA), CachedSafeLoop(false, false) {}

  bool run();

protected:
  bool checkUniqueArrayContainer(SILValue ArrayContainer);
  SmallPtrSetImpl<SILBasicBlock*> &getReachingBlocks();
  bool isRetainReleasedBeforeMutate(SILInstruction *RetainInst,
                                    bool IsUniquelyIdentifiedArray = true);
  bool checkSafeArrayAddressUses(UserList &AddressUsers);
  bool checkSafeArrayValueUses(UserList &ArrayValueUsers);
  bool checkSafeArrayElementUse(SILInstruction *UseInst, SILValue ArrayVal);
  bool checkSafeElementValueUses(UserOperList &ElementValueUsers);
  bool hoistMakeMutable(ArraySemanticsCall MakeMutable);
  void hoistMakeMutableAndSelfProjection(ArraySemanticsCall MakeMutable,
                                         bool HoistProjection);
  bool hasLoopOnlyDestructorSafeArrayOperations();
  bool isArrayValueReleasedBeforeMutate(
      SILValue V, llvm::SmallSet<SILInstruction *, 16> &Releases);
  bool hoistInLoopWithOnlyNonArrayValueMutatingOperations();
};
} // namespace

/// \return true of the given container is known to be a unique copy of the
/// array with no aliases. Cases we check:
///
/// (1) An @inout argument.
///
/// (2) A local variable, which may be copied from a by-val argument,
/// initialized directly, or copied from a function return value. We don't
/// need to check how it is initialized here, because that will show up as a
/// store to the local's address. checkSafeArrayAddressUses will check that the
/// store is a simple initialization outside the loop.
bool COWArrayOpt::checkUniqueArrayContainer(SILValue ArrayContainer) {
  if (SILArgument *Arg = dyn_cast<SILArgument>(ArrayContainer)) {
    // Check that the argument is passed as an inout type. This means there are
    // no aliases accessible within this function scope.
    auto Params = Function->getLoweredFunctionType()->getParameters();
    ArrayRef<SILArgument*> FunctionArgs = Function->begin()->getBBArgs();
    for (unsigned ArgIdx = 0, ArgEnd = Params.size();
         ArgIdx != ArgEnd; ++ArgIdx) {
      if (FunctionArgs[ArgIdx] != Arg)
        continue;

      if (!Params[ArgIdx].isIndirectInOut()) {
        DEBUG(llvm::dbgs() << "    Skipping Array: Not an inout argument!\n");
        return false;
      }
    }
    return true;
  }
  else if (isa<AllocStackInst>(ArrayContainer))
    return true;

  DEBUG(llvm::dbgs()
        << "    Skipping Array: Not an argument or local variable!\n");
  return false;
}

/// Lazilly compute blocks that may reach the loop.
SmallPtrSetImpl<SILBasicBlock*> &COWArrayOpt::getReachingBlocks() {
  if (ReachingBlocks.empty()) {
    SmallVector<SILBasicBlock*, 8> Worklist;
    ReachingBlocks.insert(Preheader);
    Worklist.push_back(Preheader);
    while (!Worklist.empty()) {
      SILBasicBlock *BB = Worklist.pop_back_val();
      for (auto PI = BB->pred_begin(), PE = BB->pred_end(); PI != PE; ++PI) {
        if (ReachingBlocks.insert(*PI).second)
          Worklist.push_back(*PI);
      }
    }
  }
  return ReachingBlocks;
}


// \return true if the instruction is a call to a non-mutating array semantic
// function.
static bool isNonMutatingArraySemanticCall(SILInstruction *Inst) {
  ArraySemanticsCall Call(Inst);
  if (!Call)
    return false;

  switch (Call.getKind()) {
  case ArrayCallKind::kNone:
  case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
  case ArrayCallKind::kCheckSubscript:
  case ArrayCallKind::kCheckIndex:
  case ArrayCallKind::kGetCount:
  case ArrayCallKind::kGetCapacity:
  case ArrayCallKind::kGetElement:
  case ArrayCallKind::kGetArrayOwner:
  case ArrayCallKind::kGetElementAddress:
    return true;
  case ArrayCallKind::kMakeMutable:
  case ArrayCallKind::kMutateUnknown:
  case ArrayCallKind::kArrayInit:
  case ArrayCallKind::kArrayUninitialized:
    return false;
  }
}

/// \return true if the given retain instruction is followed by a release on the
/// same object prior to any potential mutating operation.
bool COWArrayOpt::isRetainReleasedBeforeMutate(SILInstruction *RetainInst,
                                               bool IsUniquelyIdentifiedArray) {
  // If a retain is found outside the loop ignore it. Otherwise, it must
  // have a matching @owned call.
  if (!Loop->contains(RetainInst))
    return true;

  DEBUG(llvm::dbgs() << "     Looking at retain " << *RetainInst);

  // Walk forward looking for a release of ArrayLoad or element of
  // ArrayUserSet. Note that ArrayUserSet does not included uses of elements
  // within the Array. Consequently, checkSafeArrayElementUse must prove that
  // no uses of the Array value, or projections of it can lead to mutation
  // (element uses may only be retained/released).
  for (auto II = std::next(SILBasicBlock::iterator(RetainInst)),
         IE = RetainInst->getParent()->end(); II != IE; ++II) {
    if (isRelease(&*II, RetainInst->getOperand(0), CurrentArrayAddr, RCIA,
                  MatchedReleases))
      return true;

    if (isa<RetainValueInst>(II) || isa<StrongRetainInst>(II))
      continue;

    // A side effect free instruction cannot mutate the array.
    if (!II->mayHaveSideEffects())
      continue;

    // Non mutating array calls are safe.
    if (isNonMutatingArraySemanticCall(&*II))
      continue;

    if (IsUniquelyIdentifiedArray) {
      // It is okay for an identified loop to have releases in between a retain
      // and a release. We can end up here if we have two retains in a row and
      // then a release. The second retain cannot be matched with the release
      // but must be matched by a follow up instruction.
      //   retain %ptr
      //   retain %ptr
      //   release %ptr
      //   array_operation(..., @owned %ptr)
      //
      // This is not the case for an potentially aliased array because a release
      // can cause a destructor to run. The destructor in turn can cause
      // arbitrary side effects.
      if (isa<ReleaseValueInst>(II) || isa<StrongReleaseInst>(II))
        continue;

      if (ArrayUserSet.count(&*II)) // May be an array mutation.
        break;
    } else {
      // Not safe.
      break;
    }
  }
  DEBUG(llvm::dbgs() << "    Skipping Array: retained in loop!\n    "
        << *RetainInst);
  return false;
}

/// \return true if all given users of an array address are safe to hoist
/// make_mutable across.
///
/// General calls are unsafe because they may copy the array struct which in
/// turn bumps the reference count of the array storage.
///
/// The same logic currently applies to both uses of the array struct itself and
/// uses of an aggregate containing the array.
///
/// This does not apply to addresses of elements within the array. e.g. it is
/// not safe to store to an element in the array because we may be storing an
/// alias to the array storage.
bool COWArrayOpt::checkSafeArrayAddressUses(UserList &AddressUsers) {

  for (auto *UseInst : AddressUsers) {

    if (isDebugInst(UseInst))
      continue;

    if (auto *AI = dyn_cast<ApplyInst>(UseInst)) {
      if (ArraySemanticsCall(AI))
        continue;

      // Check of this escape can reach the current loop.
      if (!Loop->contains(UseInst->getParent()) &&
          !getReachingBlocks().count(UseInst->getParent())) {
        continue;
      }

      DEBUG(llvm::dbgs() << "    Skipping Array: may escape through call!\n    "
            << *UseInst);
      return false;
    }

    if (auto *StInst = dyn_cast<StoreInst>(UseInst)) {
      // Allow a local array to be initialized outside the loop via a by-value
      // argument or return value. The array value may be returned by its
      // initializer or some other factory function.
      if (Loop->contains(StInst->getParent())) {
        DEBUG(llvm::dbgs() << "    Skipping Array: store inside loop!\n    "
              << *StInst);
        return false;
      }

      SILValue InitArray = StInst->getSrc();
      if (isa<SILArgument>(InitArray) || isa<ApplyInst>(InitArray))
        continue;

      DEBUG(llvm::dbgs() << "    Skipping Array: may escape through store!\n"
                         << "    " << *UseInst);
      return false;
    }

    if (isa<DeallocStackInst>(UseInst)) {
      // Handle destruction of a local array.
      continue;
    }

    if (isa<MarkDependenceInst>(UseInst)) {
      continue;
    }

    DEBUG(llvm::dbgs() << "    Skipping Array: unknown Array use!\n    "
          << *UseInst);
    // Found an unsafe or unknown user. The Array may escape here.
    return false;
  }
  return true;
}

/// Returns true if this instruction is a safe array use if all of its users are
/// also safe array users.
static bool isTransitiveSafeUser(SILInstruction *I) {
  switch (I->getKind()) {
  case ValueKind::StructExtractInst:
  case ValueKind::TupleExtractInst:
  case ValueKind::UncheckedEnumDataInst:
  case ValueKind::StructInst:
  case ValueKind::TupleInst:
  case ValueKind::EnumInst:
  case ValueKind::UncheckedRefCastInst:
  case ValueKind::UncheckedBitwiseCastInst:
    assert(I->getNumTypes() == 1 && "We assume these are unary");
    return true;
  default:
    return false;
  }
}

/// Check that the use of an Array value, the value of an aggregate containing
/// an array, or the value of an element within the array, is safe w.r.t
/// make_mutable hoisting. Retains are safe as long as they are not inside the
/// Loop.
bool COWArrayOpt::checkSafeArrayValueUses(UserList &ArrayValueUsers) {
  for (auto *UseInst : ArrayValueUsers) {
    if (auto *AI = dyn_cast<ApplyInst>(UseInst)) {
      if (ArraySemanticsCall(AI))
        continue;

      // Found an unsafe or unknown user. The Array may escape here.
      DEBUG(llvm::dbgs() << "    Skipping Array: unsafe call!\n    "
            << *UseInst);
      return false;
    }

    /// Is this a unary transitive safe user instruction. This means that the
    /// instruction is safe only if all of its users are safe. Check this
    /// recursively.
    if (isTransitiveSafeUser(UseInst)) {
      if (std::all_of(UseInst->use_begin(), UseInst->use_end(),
                      [this](Operand *Op) -> bool {
                        return checkSafeArrayElementUse(Op->getUser(),
                                                        Op->get());
                      }))
        continue;
      return false;
    }

    if (isa<RetainValueInst>(UseInst)) {
      if (isRetainReleasedBeforeMutate(UseInst))
        continue;
      // Found an unsafe or unknown user. The Array may escape here.
      DEBUG(llvm::dbgs() << "    Skipping Array: found unmatched retain value!\n"
                         << "    " << *UseInst);
      return false;
    }

    if (isa<ReleaseValueInst>(UseInst)) {
      // Releases are always safe. This case handles the release of an array
      // buffer that is loaded from a local array struct.
      continue;
    }

    if (isa<MarkDependenceInst>(UseInst))
      continue;

    if (isDebugInst(UseInst))
      continue;
    
    // Found an unsafe or unknown user. The Array may escape here.
    DEBUG(llvm::dbgs() << "    Skipping Array: unsafe Array value use!\n    "
          << *UseInst);
    return false;
  }
  return true;
}

/// Given an array value, recursively check that uses of elements within the
/// array are safe.
///
/// Consider any potentially mutating operation unsafe. Mutation would not
/// prevent make_mutable hoisting, but it would interfere with
/// isRetainReleasedBeforeMutate. Since struct_extract users are not visited by
/// StructUseCollector, they are never added to ArrayUserSet. Thus we check here
/// that no mutating struct_extract users exist.
///
/// After the lower aggregates pass, SIL contains chains of struct_extract and
/// retain_value instructions. e.g.
///   %a = load %0 : $*Array<Int>
///   %b = struct_extract %a : $Array<Int>, #Array._buffer
///   %s = struct_extract %b : $_ArrayBuffer<Int>, #_ArrayBuffer.storage
///  retain_value %s : $Optional<Builtin.NativeObject>
///
///  SILCombine typically simplifies this by bypassing the
///  struct_extract. However, for completeness this analysis has the ability to
///  follow struct_extract users.
///
/// Since this does not recurse through multi-operand instructions, no visited
/// set is necessary.
bool COWArrayOpt::checkSafeArrayElementUse(SILInstruction *UseInst,
                                           SILValue ArrayVal) {
  if ((isa<RetainValueInst>(UseInst) || isa<StrongRetainInst>(UseInst)) &&
      isRetainReleasedBeforeMutate(UseInst))
    return true;

  if (isa<ReleaseValueInst>(UseInst) || isa<StrongReleaseInst>(UseInst))
    // Releases are always safe. This case handles the release of an array
    // buffer that is loaded from a local array struct.
    return true;

  // Look for a safe mark_dependence instruction use.
  //
  // This use looks something like:
  //
  //   %57 = load %56 : $*Builtin.BridgeObject from Array<Int>
  //   %58 = unchecked_ref_cast %57 : $Builtin.BridgeObject to
  //   $_ContiguousArray
  //   %59 = unchecked_ref_cast %58 : $_ContiguousArrayStorageBase to
  //   $Builtin.NativeObject
  //   %60 = struct_extract %53 : $UnsafeMutablePointer<Int>,
  //   #UnsafeMutablePointer
  //   %61 = pointer_to_address %60 : $Builtin.RawPointer to $*Int
  //   %62 = mark_dependence %61 : $*Int on %59 : $Builtin.NativeObject
  //
  // The struct_extract, unchecked_ref_cast is handled below in the
  // "Transitive SafeArrayElementUse" code.
  if (isa<MarkDependenceInst>(UseInst))
    return true;

  if (isDebugInst(UseInst))
    return true;
  
  // If this is an instruction which is a safe array element use if and only if
  // all of its users are safe array element uses, recursively check its uses
  // and return false if any of them are not transitive escape array element
  // uses.
  if (isTransitiveSafeUser(UseInst)) {
    return std::all_of(UseInst->use_begin(), UseInst->use_end(),
                       [this, &ArrayVal](Operand *UI) -> bool {
                         return checkSafeArrayElementUse(UI->getUser(),
                                                         ArrayVal);
                       });
  }

  // Found an unsafe or unknown user. The Array may escape here.
  DEBUG(llvm::dbgs() << "    Skipping Array: unknown Element use!\n"
        << *UseInst);
  return false;
}

/// Check that the use of an Array element is safe w.r.t. make_mutable hoisting.
///
/// This logic should be similar to checkSafeArrayElementUse
bool COWArrayOpt::checkSafeElementValueUses(UserOperList &ElementValueUsers) {
  for (auto &Pair : ElementValueUsers) {
    SILInstruction *UseInst = Pair.first;
    Operand *ArrayValOper = Pair.second;
    if (!checkSafeArrayElementUse(UseInst, ArrayValOper->get()))
      return false;
  }
  return true;
}
static bool isArrayEltStore(StoreInst *SI) {
  SILValue Dest = SI->getDest().stripAddressProjections();
  if (auto *MD = dyn_cast<MarkDependenceInst>(Dest))
    Dest = MD->getOperand(0);

  if (auto *PtrToAddr =
          dyn_cast<PointerToAddressInst>(Dest.stripAddressProjections()))
    if (auto *SEI = dyn_cast<StructExtractInst>(PtrToAddr->getOperand())) {
      ArraySemanticsCall Call(SEI->getOperand().getDef());
      if (Call && Call.getKind() == ArrayCallKind::kGetElementAddress)
        return true;
    }
  return false;
}

/// Check whether the array semantic operation could change an array value to
/// not be uniquely referenced.
///
/// Array.append for example can capture another array value.
static bool mayChangeArrayValueToNonUniqueState(ArraySemanticsCall &Call) {
  switch (Call.getKind()) {
  case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
  case ArrayCallKind::kCheckSubscript:
  case ArrayCallKind::kCheckIndex:
  case ArrayCallKind::kGetCount:
  case ArrayCallKind::kGetCapacity:
  case ArrayCallKind::kGetElement:
  case ArrayCallKind::kGetArrayOwner:
  case ArrayCallKind::kGetElementAddress:
  case ArrayCallKind::kMakeMutable:
    return false;

  case ArrayCallKind::kNone:
  case ArrayCallKind::kMutateUnknown:
  case ArrayCallKind::kArrayInit:
  case ArrayCallKind::kArrayUninitialized:
    return true;
  }
}

/// Check that the array value stored in \p ArrayStruct is released by \Inst.
bool isReleaseOfArrayValueAt(AllocStackInst *ArrayStruct, SILInstruction *Inst,
                             RCIdentityFunctionInfo *RCIA) {
  auto *SRI = dyn_cast<StrongReleaseInst>(Inst);
  if (!SRI)
   return false;
  auto Root = RCIA->getRCIdentityRoot(SRI->getOperand());
  auto *ArrayLoad = dyn_cast<LoadInst>(Root);
  if (!ArrayLoad)
    return false;

  if (ArrayLoad->getOperand().getDef() == ArrayStruct)
    return true;

  return false;
}

/// Check that the array value is released before a mutating operation happens.
bool COWArrayOpt::isArrayValueReleasedBeforeMutate(
    SILValue V, llvm::SmallSet<SILInstruction *, 16> &Releases) {
  auto *ASI = dyn_cast<AllocStackInst>(V.getDef());
  if (!ASI)
    return false;

  for (auto II = std::next(SILBasicBlock::iterator(ASI)),
            IE = ASI->getParent()->end();
       II != IE; ++II) {
    auto *Inst = &*II;
    // Ignore matched releases.
    if (auto SRI = dyn_cast<StrongReleaseInst>(Inst))
      if (MatchedReleases.count(&SRI->getOperandRef()))
        continue;
    if (auto RVI = dyn_cast<ReleaseValueInst>(Inst))
      if (MatchedReleases.count(&RVI->getOperandRef()))
        continue;

    if (isReleaseOfArrayValueAt(ASI, &*II, RCIA)) {
      Releases.erase(&*II);
      return true;
    }

    if (isa<RetainValueInst>(II) || isa<StrongRetainInst>(II))
      continue;

    // A side effect free instruction cannot mutate the array.
    if (!II->mayHaveSideEffects())
      continue;

    // Non mutating array calls are safe.
    if (isNonMutatingArraySemanticCall(&*II))
      continue;

    return false;
  }
  return true;
}

static SILInstruction *getInstBefore(SILInstruction *I) {
  auto It = SILBasicBlock::reverse_iterator(I->getIterator());
  if (I->getParent()->rend() == It)
    return nullptr;
  return &*It;
}

static SILInstruction *getInstAfter(SILInstruction *I) {
  auto It = SILBasicBlock::iterator(I);
  It = std::next(It);
  if (I->getParent()->end() == It)
    return nullptr;
  return &*It;
}

/// Strips and stores the struct_extract projections leading to the array
/// storage reference.
static SILValue
stripValueProjections(SILValue V,
                      SmallVectorImpl<SILInstruction *> &ValuePrjs) {
  while (V->getKind() == ValueKind::StructExtractInst) {
    ValuePrjs.push_back(cast<SILInstruction>(V.getDef()));
    V = cast<SILInstruction>(V.getDef())->getOperand(0);
  }
  return V;
}

/// Finds the preceding check_subscript, make_mutable call or returns nil.
///
/// If we found a make_mutable call this means that check_subscript was removed
/// by the array bounds check elimination pass.
static SILInstruction *
findPreceedingCheckSubscriptOrMakeMutable(ApplyInst *GetElementAddr) {
  for (auto ReverseIt =
           SILBasicBlock::reverse_iterator(GetElementAddr->getIterator()),
            End = GetElementAddr->getParent()->rend();
       ReverseIt != End; ++ReverseIt) {
    auto Apply = dyn_cast<ApplyInst>(&*ReverseIt);
    if (!Apply)
      continue;
    ArraySemanticsCall CheckSubscript(Apply);
    if (!CheckSubscript ||
        (CheckSubscript.getKind() != ArrayCallKind::kCheckSubscript &&
         CheckSubscript.getKind() != ArrayCallKind::kMakeMutable))
      return nullptr;
    return CheckSubscript;
  }
  return nullptr;
}

/// Matches the self parameter arguments, verifies that \p Self is called and
/// stores the instructions in \p DepInsts in order.
static bool
matchSelfParameterSetup(ApplyInst *Call, LoadInst *Self,
                        SmallVectorImpl<SILInstruction *> &DepInsts) {
  auto *RetainArray = dyn_cast_or_null<StrongRetainInst>(getInstBefore(Call));
  if (!RetainArray)
    return false;
  auto *ReleaseArray = dyn_cast_or_null<StrongReleaseInst>(getInstAfter(Call));
  if (!ReleaseArray)
    return false;
  if (ReleaseArray->getOperand() != RetainArray->getOperand())
    return false;

  DepInsts.push_back(ReleaseArray);
  DepInsts.push_back(Call);
  DepInsts.push_back(RetainArray);

  auto ArrayLoad = stripValueProjections(RetainArray->getOperand(), DepInsts);
  if (ArrayLoad != Self)
    return false;

  DepInsts.push_back(Self);
  return true;
}

/// Match a hoistable make_mutable call.
///
/// Precondition: The client must make sure that it is valid to actually hoist
/// the call. It must make sure that no write and no increment to the array
/// reference has happened such that hoisting is not valid.
///
/// This helper only checks that the operands computing the array reference
/// are also hoistable.
struct HoistableMakeMutable {
  SILLoop *Loop;
  bool IsHoistable;
  ApplyInst *MakeMutable;
  SmallVector<SILInstruction *, 24> DepInsts;

  HoistableMakeMutable(ArraySemanticsCall M, SILLoop *L) {
    IsHoistable = false;
    Loop = L;
    MakeMutable = M;

    // The function_ref needs to be invariant.
    if (Loop->contains(MakeMutable->getCallee()->getParentBB()))
      return;

    // The array reference is invariant.
    if (!L->contains(M.getSelf()->getParentBB())) {
      IsHoistable = true;
      return;
    }

    // Check whether we can hoist the dependent instructions resulting in the
    // array reference.
    if (canHoistDependentInstructions(M))
      IsHoistable = true;
  }

  /// Is this a hoistable make_mutable call.
  bool isHoistable() {
    return IsHoistable;
  }

  /// Hoist this make_mutable call and depend instructions to the preheader.
  void hoist() {
    auto *Term = Loop->getLoopPreheader()->getTerminator();
    for (auto *It : swift::reversed(DepInsts))
      It->moveBefore(Term);
    MakeMutable->moveBefore(Term);
  }

private:

  /// Check whether we can hoist the dependent instructions resulting in the
  /// array reference passed to the make_mutable call.
  /// We pattern match the first dimension's array access here.
  bool canHoistDependentInstructions(ArraySemanticsCall &M) {
    // Match get_element_addr call.
    // %124 = load %3
    // %125 = struct_extract %124
    // %126 = struct_extract %125
    // %127 = struct_extract %126
    // strong_retain %127
    // %129 = apply %70(%30, %124)
    // strong_release %127
    //
    // %131 = load %73
    // %132 = unchecked_ref_cast %131
    // %133 = enum $Optional<NativeObject>, #Optional.Some!enumelt.1, %132
    // %134 = struct_extract %129
    // %135 = pointer_to_address %134 to $*Array<Int>
    // %136 = mark_dependence %135 on %133

    auto *MarkDependence = dyn_cast<MarkDependenceInst>(M.getSelf());
    if (!MarkDependence)
      return false;
    DepInsts.push_back(MarkDependence);

    auto *PtrToAddrArrayAddr =
        dyn_cast<PointerToAddressInst>(MarkDependence->getValue());
    if (!PtrToAddrArrayAddr)
      return false;
    DepInsts.push_back(PtrToAddrArrayAddr);

    auto *StructExtractArrayAddr =
        dyn_cast<StructExtractInst>(PtrToAddrArrayAddr->getOperand());
    if (!StructExtractArrayAddr)
      return false;
    DepInsts.push_back(StructExtractArrayAddr);

    // Check the base the array element address is dependent on.
    auto *EnumArrayAddr = dyn_cast<EnumInst>(MarkDependence->getBase());
    if (!EnumArrayAddr)
      return false;
    DepInsts.push_back(EnumArrayAddr);
    auto *UncheckedRefCast =
        dyn_cast<UncheckedRefCastInst>(EnumArrayAddr->getOperand());
    if (!UncheckedRefCast)
      return false;
    DepInsts.push_back(UncheckedRefCast);
    auto *BaseLoad = dyn_cast<LoadInst>(UncheckedRefCast->getOperand());
    if (!BaseLoad ||  Loop->contains(BaseLoad->getOperand()->getParentBB()))
      return false;
    DepInsts.push_back(BaseLoad);

    // Check the get_element_addr call.
    ArraySemanticsCall GetElementAddrCall(
        StructExtractArrayAddr->getOperand().getDef());
    if (!GetElementAddrCall ||
        GetElementAddrCall.getKind() != ArrayCallKind::kGetElementAddress)
      return false;
    if (Loop->contains(
            ((ApplyInst *)GetElementAddrCall)->getCallee()->getParentBB()))
      return false;
    if (Loop->contains(GetElementAddrCall.getIndex()->getParentBB()))
      return false;

    auto *GetElementAddrArrayLoad =
        dyn_cast<LoadInst>(GetElementAddrCall.getSelf());
    if (!GetElementAddrArrayLoad ||
        Loop->contains(GetElementAddrArrayLoad->getOperand()->getParentBB()))
      return false;

    // Check the retain/release around the get_element_addr call.
    if (!matchSelfParameterSetup(GetElementAddrCall, GetElementAddrArrayLoad,
                                 DepInsts))
      return false;

    // Check check_subscript.
    // %116 = load %3
    // %118 = struct_extract %116
    // %119 = struct_extract %118
    // %120 = struct_extract %119
    // strong_retain %120
    // %122 = apply %23(%30, %69, %116)
    // strong_release %120
    //
    // Find the check_subscript call.
    auto *Check = findPreceedingCheckSubscriptOrMakeMutable(GetElementAddrCall);
    if (!Check)
      return false;

    ArraySemanticsCall CheckSubscript(Check);
    // The check_subscript call was removed.
    if (CheckSubscript.getKind() == ArrayCallKind::kMakeMutable)
      return true;

    if (Loop->contains(CheckSubscript.getIndex()->getParentBB()) ||
        Loop->contains(CheckSubscript.getArrayPropertyIsNativeTypeChecked()
                           ->getParentBB()))
      return false;

    auto *CheckSubscriptArrayLoad =
        dyn_cast<LoadInst>(CheckSubscript.getSelf());
    if (!CheckSubscript ||
        Loop->contains(CheckSubscriptArrayLoad->getOperand()->getParentBB()))
      return false;
  if (Loop->contains(
            ((ApplyInst *)CheckSubscript)->getCallee()->getParentBB()))
      return false;

    // The array must match get_element_addr's array.
    if (CheckSubscriptArrayLoad->getOperand() !=
        GetElementAddrArrayLoad->getOperand())
      return false;

    // Check the retain/release around the check_subscript call.
    if (!matchSelfParameterSetup(CheckSubscript, CheckSubscriptArrayLoad,
                                 DepInsts))
      return false;

    return true;
  }
};

/// Prove that there are not array value mutating or capturing operations in the
/// loop and hoist make_mutable.
bool COWArrayOpt::hoistInLoopWithOnlyNonArrayValueMutatingOperations() {
  // Only handle innermost loops.
  assert(Loop->getSubLoops().empty() && "Only works in innermost loops");

  DEBUG(llvm::dbgs() << "    Checking whether loop only has only non array "
                        "value mutating operations ...\n");

  // There is no current array addr value.
  CurrentArrayAddr = SILValue();

  // We need to cleanup the MatchedRelease on return.
  auto ReturnWithCleanup = [&] (bool LoopHasSafeOperations) {
    MatchedReleases.clear();
    return LoopHasSafeOperations;
  };

  llvm::SmallSet<SILValue, 16> ArrayValues;
  llvm::SmallSetVector<SILValue, 16> CreatedNonTrivialValues;
  llvm::SmallSet<SILInstruction *, 16> Releases;
  llvm::SmallVector<ArraySemanticsCall, 8> MakeMutableCalls;


  /// Make sure that no writes to an array value happens in the loop and that
  /// no array values are retained without beeing released before hitting a
  /// make_unique:
  ///
  /// * array semantic functions that don't change the uniqueness state to
  ///   non-unique are safe.
  /// * retains must be matched by a release before hitting a mutating operation
  /// * stores must not store an array value (only trivial stores are safe).
  ///
  auto &Module = Function->getModule();
  for (auto *BB : Loop->getBlocks()) {
    for (auto &InstIt : *BB) {
      auto *Inst = &InstIt;<commit_msg>Fix typo: beeing → being<commit_after>//===------- COWArrayOpt.cpp - Optimize Copy-On-Write Array Checks --------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "cowarray-opts"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILCloner.h"
#include "swift/SIL/SILBuilder.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SILOptimizer/Analysis/ArraySemantic.h"
#include "swift/SILOptimizer/Analysis/AliasAnalysis.h"
#include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
#include "swift/SILOptimizer/Analysis/ColdBlockInfo.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SILOptimizer/Analysis/LoopAnalysis.h"
#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/CFG.h"
#include "swift/SILOptimizer/Utils/Local.h"
#include "swift/SILOptimizer/Utils/SILSSAUpdater.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
using namespace swift;

#ifndef NDEBUG
llvm::cl::opt<std::string>
COWViewCFGFunction("view-cfg-before-cow-for", llvm::cl::init(""),
                   llvm::cl::desc("Only print out the sil for this function"));
#endif

/// \return a sequence of integers representing the access path of this element
/// within a Struct/Ref/Tuple.
///
/// Do not form a path with an IndexAddrInst because we have no way to
/// distinguish between indexing and subelement access. The same index could
/// either refer to the next element (indexed) or a subelement.
static SILValue getAccessPath(SILValue V, SmallVectorImpl<unsigned>& Path) {
  V = V.stripCasts();
  ProjectionIndex PI(V.getDef());
  if (!PI.isValid() || V->getKind() == ValueKind::IndexAddrInst)
    return V;

  SILValue UnderlyingObject = getAccessPath(PI.Aggregate, Path);
  Path.push_back(PI.Index);
  return UnderlyingObject;
}

namespace {
/// Collect all uses of a struct given an aggregate value that contains the
/// struct and access path describing the projection of the aggregate
/// that accesses the struct.
///
/// AggregateAddressUsers records uses of the aggregate value's address. These
/// may indirectly access the struct's elements.
///
/// Projections over the aggregate that do not access the struct are ignored.
///
/// StructLoads records loads of the struct value.
/// StructAddressUsers records other uses of the struct address.
/// StructValueUsers records direct uses of the loaded struct.
///
/// Projections of the struct over its elements are all similarly recorded in
/// ElementAddressUsers, ElementLoads, and ElementValueUsers.
///
/// bb0(%arg : $*S)
/// apply %f(%arg)           // <--- Aggregate Address User
/// %struct_addr = struct_element_addr %arg : $*S, #S.element
/// apply %g(%struct_addr)   // <--- Struct Address User
/// %val = load %struct_addr // <--- Struct Load
/// apply %h(%val)           // <--- Struct Value User
/// %elt_addr = struct_element_addr %struct_addr : $*A, #A.element
/// apply %i(%elt_addr)      // <--- Element Address User
/// %elt = load %elt_addr    // <--- Element Load
/// apply %j(%elt)           // <--- Element Value User
class StructUseCollector {
public:
  typedef SmallPtrSet<Operand*, 16> VisitedSet;
  typedef SmallVector<SILInstruction*, 16> UserList;

  /// Record the users of a value or an element within that value along with the
  /// operand that directly uses the value. Multiple levels of struct_extract
  /// may exist between the operand and the user instruction.
  typedef SmallVector<std::pair<SILInstruction*, Operand*>, 16> UserOperList;

  UserList AggregateAddressUsers;
  UserList StructAddressUsers;
  UserList StructLoads;
  UserList StructValueUsers;
  UserOperList ElementAddressUsers;
  UserOperList ElementLoads;
  UserOperList ElementValueUsers;
  VisitedSet Visited;

  /// Collect all uses of the value at the given address.
  void collectUses(ValueBase *V, ArrayRef<unsigned> AccessPath) {
    // Save our old indent and increment.
    // Collect all users of the address and loads.
    collectAddressUses(V, AccessPath, nullptr);

    // Collect all uses of the Struct value.
    for (auto *DefInst : StructLoads) {
      for (auto *DefUI : DefInst->getUses()) {
        if (!Visited.insert(&*DefUI).second) {
          continue;
        }

        StructValueUsers.push_back(DefUI->getUser());
      }
    }

    // Collect all users of element values.
    for (auto &Pair : ElementLoads) {
      for (auto *DefUI : Pair.first->getUses()) {
        if (!Visited.insert(&*DefUI).second) {
          continue;
        }

        ElementValueUsers.push_back(
            std::make_pair(DefUI->getUser(), Pair.second));
      }
    }
  }

protected:

  static bool definesSingleObjectType(ValueBase *V) {
    if (auto *Arg = dyn_cast<SILArgument>(V))
      return Arg->getType().isObject();
    if (auto *Inst = dyn_cast<SILInstruction>(V))
      return Inst->getNumTypes() == 1 && Inst->getType(0).isObject();
    return false;
  }

  /// If AccessPathSuffix is non-empty, then the value is the address of an
  /// aggregate containing the Struct. If AccessPathSuffix is empty and
  /// StructVal is invalid, then the value is the address of the Struct. If
  /// StructVal is valid, the value is the address of an element within the
  /// Struct.
  void collectAddressUses(ValueBase *V, ArrayRef<unsigned> AccessPathSuffix,
                          Operand *StructVal) {
    for (auto *UI : V->getUses()) {
      // Keep the operand, not the instruction in the visited set. The same
      // instruction may theoretically have different types of uses.
      if (!Visited.insert(&*UI).second) {
        continue;
      }

      SILInstruction *UseInst = UI->getUser();
      if (StructVal) {
        // Found a use of an element.
        assert(AccessPathSuffix.empty() && "should have accessed struct");
        if (auto *LoadI = dyn_cast<LoadInst>(UseInst)) {
          ElementLoads.push_back(std::make_pair(LoadI, StructVal));
          continue;
        }

        if (isa<StructElementAddrInst>(UseInst)) {
          collectAddressUses(UseInst, AccessPathSuffix, StructVal);
          continue;
        }

        ElementAddressUsers.push_back(std::make_pair(UseInst,StructVal));
        continue;
      }

      if (AccessPathSuffix.empty()) {
        // Found a use of the struct at the given access path.
        if (auto *LoadI = dyn_cast<LoadInst>(UseInst)) {
          StructLoads.push_back(LoadI);
          continue;
        }

        if (isa<StructElementAddrInst>(UseInst)) {
          collectAddressUses(UseInst, AccessPathSuffix, &*UI);
          continue;
        }

        // Value users - this happens if we start with a value object in V.
        if (definesSingleObjectType(V)) {
          StructValueUsers.push_back(UseInst);
          continue;
        }

        StructAddressUsers.push_back(UseInst);
        continue;
      }

      ProjectionIndex PI(UseInst);
      // Do not form a path from an IndexAddrInst without otherwise
      // distinguishing it from subelement addressing.
      if (!PI.isValid() || V->getKind() == ValueKind::IndexAddrInst) {
        // Found a use of an aggregate containing the given element.
        AggregateAddressUsers.push_back(UseInst);
        continue;
      }

      if (PI.Index != AccessPathSuffix[0]) {
        // Ignore uses of disjoint elements.
        continue;
      }

      // An alloc_stack returns its address as the second value.
      assert((PI.Aggregate == V || PI.Aggregate == SILValue(V, 1)) &&
             "Expected unary element addr inst.");

      // Recursively check for users after stripping this component from the
      // access path.
      collectAddressUses(UseInst, AccessPathSuffix.slice(1), nullptr);
    }
  }
};
} // namespace

// Do the two values \p A and \p B reference the same 'array' after potentially
// looking through a load. To identify a common array address this functions
// strips struct projections until it hits \p ArrayAddress.
bool areArraysEqual(RCIdentityFunctionInfo *RCIA, SILValue A, SILValue B,
                    SILValue ArrayAddress) {
  A = RCIA->getRCIdentityRoot(A);
  B = RCIA->getRCIdentityRoot(B);
  if (A == B)
    return true;
  // We have stripped off struct_extracts. Remove the load to look at the
  // address we are loading from.
  if (auto *ALoad = dyn_cast<LoadInst>(A))
    A = ALoad->getOperand();
  if (auto *BLoad = dyn_cast<LoadInst>(B))
    B = BLoad->getOperand();
  // Strip off struct_extract_refs until we hit array address.
  if (ArrayAddress) {
    StructElementAddrInst *SEAI = nullptr;
    while (A != ArrayAddress && (SEAI = dyn_cast<StructElementAddrInst>(A)))
      A = SEAI->getOperand();
    while (B != ArrayAddress && (SEAI = dyn_cast<StructElementAddrInst>(B)))
      B = SEAI->getOperand();
  }
  return A == B;
}

/// \return true if the given instruction releases the given value.
static bool isRelease(SILInstruction *Inst, SILValue RetainedValue,
                      SILValue ArrayAddress, RCIdentityFunctionInfo *RCIA,
                      SmallPtrSetImpl<Operand *> &MatchedReleases) {

  // Before we can match a release with a retain we need to check that we have
  // not already matched the release with a retain we processed earlier.
  // We don't want to match the release with both retains in the example below.
  //
  //   retain %a  <--|
  //   retain %a     | Match.   <-| Dont't match.
  //   release %a <--|          <-|
  //
  if (auto *R = dyn_cast<ReleaseValueInst>(Inst))
    if (!MatchedReleases.count(&R->getOperandRef()))
      if (areArraysEqual(RCIA, Inst->getOperand(0), RetainedValue,
                         ArrayAddress)) {
        DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
        MatchedReleases.insert(&R->getOperandRef());
        return true;
      }

  if (auto *R = dyn_cast<StrongReleaseInst>(Inst))
    if (!MatchedReleases.count(&R->getOperandRef()))
      if (areArraysEqual(RCIA, Inst->getOperand(0), RetainedValue,
                         ArrayAddress)) {
        DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
        MatchedReleases.insert(&R->getOperandRef());
        return true;
      }

  if (auto *AI = dyn_cast<ApplyInst>(Inst)) {
    if (auto *F = AI->getCalleeFunction()) {
      auto Params = F->getLoweredFunctionType()->getParameters();
      auto Args = AI->getArguments();
      for (unsigned ArgIdx = 0, ArgEnd = Params.size(); ArgIdx != ArgEnd;
           ++ArgIdx) {
        if (MatchedReleases.count(&AI->getArgumentRef(ArgIdx)))
          continue;
        if (!areArraysEqual(RCIA, Args[ArgIdx], RetainedValue, ArrayAddress))
          continue;
        ParameterConvention P = Params[ArgIdx].getConvention();
        if (P == ParameterConvention::Direct_Owned) {
          DEBUG(llvm::dbgs() << "     matching with release " << *Inst);
          MatchedReleases.insert(&AI->getArgumentRef(ArgIdx));
          return true;
        }
      }
    }
  }
  DEBUG(llvm::dbgs() << "      not a matching release " << *Inst);
  return false;
}

namespace {

/// Optimize Copy-On-Write array checks based on high-level semantics.
///
/// Performs an analysis on all Array users to ensure they do not interfere
/// with make_mutable hoisting. Ultimately, the only thing that can interfere
/// with make_mutable is a retain of the array. To ensure no retains occur
/// within the loop, it is necessary to check that the array does not escape on
/// any path reaching the loop, and that it is not directly retained within the
/// loop itself.
///
/// In some cases, a retain does exist within the loop, but is balanced by a
/// release or call to @owned. The analysis must determine whether any array
/// mutation can occur between the retain and release. To accomplish this it
/// relies on knowledge of all array operations within the loop. If the array
/// escapes in some way that cannot be tracked, the analysis must fail.
///
/// TODO: Handle this pattern:
///   retain(array)
///   call(array)
///   release(array)
/// Whenever the call is readonly, has balanced retain/release for the array,
/// and does not capture the array. Under these conditions, the call can neither
/// mutate the array nor save an alias for later mutation.
///
/// TODO: Completely eliminate make_mutable calls if all operations that the
/// guard are already guarded by either "init" or "mutate_unknown".
class COWArrayOpt {
  typedef StructUseCollector::UserList UserList;
  typedef StructUseCollector::UserOperList UserOperList;

  RCIdentityFunctionInfo *RCIA;
  SILFunction *Function;
  SILLoop *Loop;
  SILBasicBlock *Preheader;
  DominanceInfo *DomTree;
  bool HasChanged = false;

  // Keep track of cold blocks.
  ColdBlockInfo ColdBlocks;

  // Cache of the analysis whether a loop is safe wrt. make_unique hoisting by
  // looking at the operations (no uniquely identified objects).
  std::pair<bool, bool> CachedSafeLoop;

  // Set of all blocks that may reach the loop, not including loop blocks.
  llvm::SmallPtrSet<SILBasicBlock*,32> ReachingBlocks;

  // Map an array to a hoisted make_mutable call for the current loop. An array
  // is only mapped to a call once the analysis has determined that no
  // make_mutable calls are required within the loop body for that array.
  llvm::SmallDenseMap<SILValue, ApplyInst*> ArrayMakeMutableMap;

  // \brief Transient per-Array user set.
  //
  // Track all known array users with the exception of struct_extract users
  // (checkSafeArrayElementUse prohibits struct_extract users from mutating the
  // array). During analysis of retains/releases within the loop body, the
  // users in this set are assumed to cover all possible mutating operations on
  // the array. If the array escaped through an unknown use, the analysis must
  // abort earlier.
  SmallPtrSet<SILInstruction*, 8> ArrayUserSet;

  // When matching retains to releases we must not match the same release twice.
  //
  // For example we could have:
  //   retain %a // id %1
  //   retain %a // id %2
  //   release %a // id %3
  // When we match %1 with %3, we can't match %3 again when we look for a
  // matching release for %2.
  // The set refers to operands instead of instructions because an apply could
  // have several operands with release semantics.
  SmallPtrSet<Operand*, 8> MatchedReleases;

  // The address of the array passed to the current make_mutable we are
  // analysing.
  SILValue CurrentArrayAddr;
public:
  COWArrayOpt(RCIdentityFunctionInfo *RCIA, SILLoop *L,
              DominanceAnalysis *DA)
      : RCIA(RCIA), Function(L->getHeader()->getParent()), Loop(L),
        Preheader(L->getLoopPreheader()), DomTree(DA->get(Function)),
        ColdBlocks(DA), CachedSafeLoop(false, false) {}

  bool run();

protected:
  bool checkUniqueArrayContainer(SILValue ArrayContainer);
  SmallPtrSetImpl<SILBasicBlock*> &getReachingBlocks();
  bool isRetainReleasedBeforeMutate(SILInstruction *RetainInst,
                                    bool IsUniquelyIdentifiedArray = true);
  bool checkSafeArrayAddressUses(UserList &AddressUsers);
  bool checkSafeArrayValueUses(UserList &ArrayValueUsers);
  bool checkSafeArrayElementUse(SILInstruction *UseInst, SILValue ArrayVal);
  bool checkSafeElementValueUses(UserOperList &ElementValueUsers);
  bool hoistMakeMutable(ArraySemanticsCall MakeMutable);
  void hoistMakeMutableAndSelfProjection(ArraySemanticsCall MakeMutable,
                                         bool HoistProjection);
  bool hasLoopOnlyDestructorSafeArrayOperations();
  bool isArrayValueReleasedBeforeMutate(
      SILValue V, llvm::SmallSet<SILInstruction *, 16> &Releases);
  bool hoistInLoopWithOnlyNonArrayValueMutatingOperations();
};
} // namespace

/// \return true of the given container is known to be a unique copy of the
/// array with no aliases. Cases we check:
///
/// (1) An @inout argument.
///
/// (2) A local variable, which may be copied from a by-val argument,
/// initialized directly, or copied from a function return value. We don't
/// need to check how it is initialized here, because that will show up as a
/// store to the local's address. checkSafeArrayAddressUses will check that the
/// store is a simple initialization outside the loop.
bool COWArrayOpt::checkUniqueArrayContainer(SILValue ArrayContainer) {
  if (SILArgument *Arg = dyn_cast<SILArgument>(ArrayContainer)) {
    // Check that the argument is passed as an inout type. This means there are
    // no aliases accessible within this function scope.
    auto Params = Function->getLoweredFunctionType()->getParameters();
    ArrayRef<SILArgument*> FunctionArgs = Function->begin()->getBBArgs();
    for (unsigned ArgIdx = 0, ArgEnd = Params.size();
         ArgIdx != ArgEnd; ++ArgIdx) {
      if (FunctionArgs[ArgIdx] != Arg)
        continue;

      if (!Params[ArgIdx].isIndirectInOut()) {
        DEBUG(llvm::dbgs() << "    Skipping Array: Not an inout argument!\n");
        return false;
      }
    }
    return true;
  }
  else if (isa<AllocStackInst>(ArrayContainer))
    return true;

  DEBUG(llvm::dbgs()
        << "    Skipping Array: Not an argument or local variable!\n");
  return false;
}

/// Lazilly compute blocks that may reach the loop.
SmallPtrSetImpl<SILBasicBlock*> &COWArrayOpt::getReachingBlocks() {
  if (ReachingBlocks.empty()) {
    SmallVector<SILBasicBlock*, 8> Worklist;
    ReachingBlocks.insert(Preheader);
    Worklist.push_back(Preheader);
    while (!Worklist.empty()) {
      SILBasicBlock *BB = Worklist.pop_back_val();
      for (auto PI = BB->pred_begin(), PE = BB->pred_end(); PI != PE; ++PI) {
        if (ReachingBlocks.insert(*PI).second)
          Worklist.push_back(*PI);
      }
    }
  }
  return ReachingBlocks;
}


// \return true if the instruction is a call to a non-mutating array semantic
// function.
static bool isNonMutatingArraySemanticCall(SILInstruction *Inst) {
  ArraySemanticsCall Call(Inst);
  if (!Call)
    return false;

  switch (Call.getKind()) {
  case ArrayCallKind::kNone:
  case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
  case ArrayCallKind::kCheckSubscript:
  case ArrayCallKind::kCheckIndex:
  case ArrayCallKind::kGetCount:
  case ArrayCallKind::kGetCapacity:
  case ArrayCallKind::kGetElement:
  case ArrayCallKind::kGetArrayOwner:
  case ArrayCallKind::kGetElementAddress:
    return true;
  case ArrayCallKind::kMakeMutable:
  case ArrayCallKind::kMutateUnknown:
  case ArrayCallKind::kArrayInit:
  case ArrayCallKind::kArrayUninitialized:
    return false;
  }
}

/// \return true if the given retain instruction is followed by a release on the
/// same object prior to any potential mutating operation.
bool COWArrayOpt::isRetainReleasedBeforeMutate(SILInstruction *RetainInst,
                                               bool IsUniquelyIdentifiedArray) {
  // If a retain is found outside the loop ignore it. Otherwise, it must
  // have a matching @owned call.
  if (!Loop->contains(RetainInst))
    return true;

  DEBUG(llvm::dbgs() << "     Looking at retain " << *RetainInst);

  // Walk forward looking for a release of ArrayLoad or element of
  // ArrayUserSet. Note that ArrayUserSet does not included uses of elements
  // within the Array. Consequently, checkSafeArrayElementUse must prove that
  // no uses of the Array value, or projections of it can lead to mutation
  // (element uses may only be retained/released).
  for (auto II = std::next(SILBasicBlock::iterator(RetainInst)),
         IE = RetainInst->getParent()->end(); II != IE; ++II) {
    if (isRelease(&*II, RetainInst->getOperand(0), CurrentArrayAddr, RCIA,
                  MatchedReleases))
      return true;

    if (isa<RetainValueInst>(II) || isa<StrongRetainInst>(II))
      continue;

    // A side effect free instruction cannot mutate the array.
    if (!II->mayHaveSideEffects())
      continue;

    // Non mutating array calls are safe.
    if (isNonMutatingArraySemanticCall(&*II))
      continue;

    if (IsUniquelyIdentifiedArray) {
      // It is okay for an identified loop to have releases in between a retain
      // and a release. We can end up here if we have two retains in a row and
      // then a release. The second retain cannot be matched with the release
      // but must be matched by a follow up instruction.
      //   retain %ptr
      //   retain %ptr
      //   release %ptr
      //   array_operation(..., @owned %ptr)
      //
      // This is not the case for an potentially aliased array because a release
      // can cause a destructor to run. The destructor in turn can cause
      // arbitrary side effects.
      if (isa<ReleaseValueInst>(II) || isa<StrongReleaseInst>(II))
        continue;

      if (ArrayUserSet.count(&*II)) // May be an array mutation.
        break;
    } else {
      // Not safe.
      break;
    }
  }
  DEBUG(llvm::dbgs() << "    Skipping Array: retained in loop!\n    "
        << *RetainInst);
  return false;
}

/// \return true if all given users of an array address are safe to hoist
/// make_mutable across.
///
/// General calls are unsafe because they may copy the array struct which in
/// turn bumps the reference count of the array storage.
///
/// The same logic currently applies to both uses of the array struct itself and
/// uses of an aggregate containing the array.
///
/// This does not apply to addresses of elements within the array. e.g. it is
/// not safe to store to an element in the array because we may be storing an
/// alias to the array storage.
bool COWArrayOpt::checkSafeArrayAddressUses(UserList &AddressUsers) {

  for (auto *UseInst : AddressUsers) {

    if (isDebugInst(UseInst))
      continue;

    if (auto *AI = dyn_cast<ApplyInst>(UseInst)) {
      if (ArraySemanticsCall(AI))
        continue;

      // Check of this escape can reach the current loop.
      if (!Loop->contains(UseInst->getParent()) &&
          !getReachingBlocks().count(UseInst->getParent())) {
        continue;
      }

      DEBUG(llvm::dbgs() << "    Skipping Array: may escape through call!\n    "
            << *UseInst);
      return false;
    }

    if (auto *StInst = dyn_cast<StoreInst>(UseInst)) {
      // Allow a local array to be initialized outside the loop via a by-value
      // argument or return value. The array value may be returned by its
      // initializer or some other factory function.
      if (Loop->contains(StInst->getParent())) {
        DEBUG(llvm::dbgs() << "    Skipping Array: store inside loop!\n    "
              << *StInst);
        return false;
      }

      SILValue InitArray = StInst->getSrc();
      if (isa<SILArgument>(InitArray) || isa<ApplyInst>(InitArray))
        continue;

      DEBUG(llvm::dbgs() << "    Skipping Array: may escape through store!\n"
                         << "    " << *UseInst);
      return false;
    }

    if (isa<DeallocStackInst>(UseInst)) {
      // Handle destruction of a local array.
      continue;
    }

    if (isa<MarkDependenceInst>(UseInst)) {
      continue;
    }

    DEBUG(llvm::dbgs() << "    Skipping Array: unknown Array use!\n    "
          << *UseInst);
    // Found an unsafe or unknown user. The Array may escape here.
    return false;
  }
  return true;
}

/// Returns true if this instruction is a safe array use if all of its users are
/// also safe array users.
static bool isTransitiveSafeUser(SILInstruction *I) {
  switch (I->getKind()) {
  case ValueKind::StructExtractInst:
  case ValueKind::TupleExtractInst:
  case ValueKind::UncheckedEnumDataInst:
  case ValueKind::StructInst:
  case ValueKind::TupleInst:
  case ValueKind::EnumInst:
  case ValueKind::UncheckedRefCastInst:
  case ValueKind::UncheckedBitwiseCastInst:
    assert(I->getNumTypes() == 1 && "We assume these are unary");
    return true;
  default:
    return false;
  }
}

/// Check that the use of an Array value, the value of an aggregate containing
/// an array, or the value of an element within the array, is safe w.r.t
/// make_mutable hoisting. Retains are safe as long as they are not inside the
/// Loop.
bool COWArrayOpt::checkSafeArrayValueUses(UserList &ArrayValueUsers) {
  for (auto *UseInst : ArrayValueUsers) {
    if (auto *AI = dyn_cast<ApplyInst>(UseInst)) {
      if (ArraySemanticsCall(AI))
        continue;

      // Found an unsafe or unknown user. The Array may escape here.
      DEBUG(llvm::dbgs() << "    Skipping Array: unsafe call!\n    "
            << *UseInst);
      return false;
    }

    /// Is this a unary transitive safe user instruction. This means that the
    /// instruction is safe only if all of its users are safe. Check this
    /// recursively.
    if (isTransitiveSafeUser(UseInst)) {
      if (std::all_of(UseInst->use_begin(), UseInst->use_end(),
                      [this](Operand *Op) -> bool {
                        return checkSafeArrayElementUse(Op->getUser(),
                                                        Op->get());
                      }))
        continue;
      return false;
    }

    if (isa<RetainValueInst>(UseInst)) {
      if (isRetainReleasedBeforeMutate(UseInst))
        continue;
      // Found an unsafe or unknown user. The Array may escape here.
      DEBUG(llvm::dbgs() << "    Skipping Array: found unmatched retain value!\n"
                         << "    " << *UseInst);
      return false;
    }

    if (isa<ReleaseValueInst>(UseInst)) {
      // Releases are always safe. This case handles the release of an array
      // buffer that is loaded from a local array struct.
      continue;
    }

    if (isa<MarkDependenceInst>(UseInst))
      continue;

    if (isDebugInst(UseInst))
      continue;
    
    // Found an unsafe or unknown user. The Array may escape here.
    DEBUG(llvm::dbgs() << "    Skipping Array: unsafe Array value use!\n    "
          << *UseInst);
    return false;
  }
  return true;
}

/// Given an array value, recursively check that uses of elements within the
/// array are safe.
///
/// Consider any potentially mutating operation unsafe. Mutation would not
/// prevent make_mutable hoisting, but it would interfere with
/// isRetainReleasedBeforeMutate. Since struct_extract users are not visited by
/// StructUseCollector, they are never added to ArrayUserSet. Thus we check here
/// that no mutating struct_extract users exist.
///
/// After the lower aggregates pass, SIL contains chains of struct_extract and
/// retain_value instructions. e.g.
///   %a = load %0 : $*Array<Int>
///   %b = struct_extract %a : $Array<Int>, #Array._buffer
///   %s = struct_extract %b : $_ArrayBuffer<Int>, #_ArrayBuffer.storage
///  retain_value %s : $Optional<Builtin.NativeObject>
///
///  SILCombine typically simplifies this by bypassing the
///  struct_extract. However, for completeness this analysis has the ability to
///  follow struct_extract users.
///
/// Since this does not recurse through multi-operand instructions, no visited
/// set is necessary.
bool COWArrayOpt::checkSafeArrayElementUse(SILInstruction *UseInst,
                                           SILValue ArrayVal) {
  if ((isa<RetainValueInst>(UseInst) || isa<StrongRetainInst>(UseInst)) &&
      isRetainReleasedBeforeMutate(UseInst))
    return true;

  if (isa<ReleaseValueInst>(UseInst) || isa<StrongReleaseInst>(UseInst))
    // Releases are always safe. This case handles the release of an array
    // buffer that is loaded from a local array struct.
    return true;

  // Look for a safe mark_dependence instruction use.
  //
  // This use looks something like:
  //
  //   %57 = load %56 : $*Builtin.BridgeObject from Array<Int>
  //   %58 = unchecked_ref_cast %57 : $Builtin.BridgeObject to
  //   $_ContiguousArray
  //   %59 = unchecked_ref_cast %58 : $_ContiguousArrayStorageBase to
  //   $Builtin.NativeObject
  //   %60 = struct_extract %53 : $UnsafeMutablePointer<Int>,
  //   #UnsafeMutablePointer
  //   %61 = pointer_to_address %60 : $Builtin.RawPointer to $*Int
  //   %62 = mark_dependence %61 : $*Int on %59 : $Builtin.NativeObject
  //
  // The struct_extract, unchecked_ref_cast is handled below in the
  // "Transitive SafeArrayElementUse" code.
  if (isa<MarkDependenceInst>(UseInst))
    return true;

  if (isDebugInst(UseInst))
    return true;
  
  // If this is an instruction which is a safe array element use if and only if
  // all of its users are safe array element uses, recursively check its uses
  // and return false if any of them are not transitive escape array element
  // uses.
  if (isTransitiveSafeUser(UseInst)) {
    return std::all_of(UseInst->use_begin(), UseInst->use_end(),
                       [this, &ArrayVal](Operand *UI) -> bool {
                         return checkSafeArrayElementUse(UI->getUser(),
                                                         ArrayVal);
                       });
  }

  // Found an unsafe or unknown user. The Array may escape here.
  DEBUG(llvm::dbgs() << "    Skipping Array: unknown Element use!\n"
        << *UseInst);
  return false;
}

/// Check that the use of an Array element is safe w.r.t. make_mutable hoisting.
///
/// This logic should be similar to checkSafeArrayElementUse
bool COWArrayOpt::checkSafeElementValueUses(UserOperList &ElementValueUsers) {
  for (auto &Pair : ElementValueUsers) {
    SILInstruction *UseInst = Pair.first;
    Operand *ArrayValOper = Pair.second;
    if (!checkSafeArrayElementUse(UseInst, ArrayValOper->get()))
      return false;
  }
  return true;
}
static bool isArrayEltStore(StoreInst *SI) {
  SILValue Dest = SI->getDest().stripAddressProjections();
  if (auto *MD = dyn_cast<MarkDependenceInst>(Dest))
    Dest = MD->getOperand(0);

  if (auto *PtrToAddr =
          dyn_cast<PointerToAddressInst>(Dest.stripAddressProjections()))
    if (auto *SEI = dyn_cast<StructExtractInst>(PtrToAddr->getOperand())) {
      ArraySemanticsCall Call(SEI->getOperand().getDef());
      if (Call && Call.getKind() == ArrayCallKind::kGetElementAddress)
        return true;
    }
  return false;
}

/// Check whether the array semantic operation could change an array value to
/// not be uniquely referenced.
///
/// Array.append for example can capture another array value.
static bool mayChangeArrayValueToNonUniqueState(ArraySemanticsCall &Call) {
  switch (Call.getKind()) {
  case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
  case ArrayCallKind::kCheckSubscript:
  case ArrayCallKind::kCheckIndex:
  case ArrayCallKind::kGetCount:
  case ArrayCallKind::kGetCapacity:
  case ArrayCallKind::kGetElement:
  case ArrayCallKind::kGetArrayOwner:
  case ArrayCallKind::kGetElementAddress:
  case ArrayCallKind::kMakeMutable:
    return false;

  case ArrayCallKind::kNone:
  case ArrayCallKind::kMutateUnknown:
  case ArrayCallKind::kArrayInit:
  case ArrayCallKind::kArrayUninitialized:
    return true;
  }
}

/// Check that the array value stored in \p ArrayStruct is released by \Inst.
bool isReleaseOfArrayValueAt(AllocStackInst *ArrayStruct, SILInstruction *Inst,
                             RCIdentityFunctionInfo *RCIA) {
  auto *SRI = dyn_cast<StrongReleaseInst>(Inst);
  if (!SRI)
   return false;
  auto Root = RCIA->getRCIdentityRoot(SRI->getOperand());
  auto *ArrayLoad = dyn_cast<LoadInst>(Root);
  if (!ArrayLoad)
    return false;

  if (ArrayLoad->getOperand().getDef() == ArrayStruct)
    return true;

  return false;
}

/// Check that the array value is released before a mutating operation happens.
bool COWArrayOpt::isArrayValueReleasedBeforeMutate(
    SILValue V, llvm::SmallSet<SILInstruction *, 16> &Releases) {
  auto *ASI = dyn_cast<AllocStackInst>(V.getDef());
  if (!ASI)
    return false;

  for (auto II = std::next(SILBasicBlock::iterator(ASI)),
            IE = ASI->getParent()->end();
       II != IE; ++II) {
    auto *Inst = &*II;
    // Ignore matched releases.
    if (auto SRI = dyn_cast<StrongReleaseInst>(Inst))
      if (MatchedReleases.count(&SRI->getOperandRef()))
        continue;
    if (auto RVI = dyn_cast<ReleaseValueInst>(Inst))
      if (MatchedReleases.count(&RVI->getOperandRef()))
        continue;

    if (isReleaseOfArrayValueAt(ASI, &*II, RCIA)) {
      Releases.erase(&*II);
      return true;
    }

    if (isa<RetainValueInst>(II) || isa<StrongRetainInst>(II))
      continue;

    // A side effect free instruction cannot mutate the array.
    if (!II->mayHaveSideEffects())
      continue;

    // Non mutating array calls are safe.
    if (isNonMutatingArraySemanticCall(&*II))
      continue;

    return false;
  }
  return true;
}

static SILInstruction *getInstBefore(SILInstruction *I) {
  auto It = SILBasicBlock::reverse_iterator(I->getIterator());
  if (I->getParent()->rend() == It)
    return nullptr;
  return &*It;
}

static SILInstruction *getInstAfter(SILInstruction *I) {
  auto It = SILBasicBlock::iterator(I);
  It = std::next(It);
  if (I->getParent()->end() == It)
    return nullptr;
  return &*It;
}

/// Strips and stores the struct_extract projections leading to the array
/// storage reference.
static SILValue
stripValueProjections(SILValue V,
                      SmallVectorImpl<SILInstruction *> &ValuePrjs) {
  while (V->getKind() == ValueKind::StructExtractInst) {
    ValuePrjs.push_back(cast<SILInstruction>(V.getDef()));
    V = cast<SILInstruction>(V.getDef())->getOperand(0);
  }
  return V;
}

/// Finds the preceding check_subscript, make_mutable call or returns nil.
///
/// If we found a make_mutable call this means that check_subscript was removed
/// by the array bounds check elimination pass.
static SILInstruction *
findPreceedingCheckSubscriptOrMakeMutable(ApplyInst *GetElementAddr) {
  for (auto ReverseIt =
           SILBasicBlock::reverse_iterator(GetElementAddr->getIterator()),
            End = GetElementAddr->getParent()->rend();
       ReverseIt != End; ++ReverseIt) {
    auto Apply = dyn_cast<ApplyInst>(&*ReverseIt);
    if (!Apply)
      continue;
    ArraySemanticsCall CheckSubscript(Apply);
    if (!CheckSubscript ||
        (CheckSubscript.getKind() != ArrayCallKind::kCheckSubscript &&
         CheckSubscript.getKind() != ArrayCallKind::kMakeMutable))
      return nullptr;
    return CheckSubscript;
  }
  return nullptr;
}

/// Matches the self parameter arguments, verifies that \p Self is called and
/// stores the instructions in \p DepInsts in order.
static bool
matchSelfParameterSetup(ApplyInst *Call, LoadInst *Self,
                        SmallVectorImpl<SILInstruction *> &DepInsts) {
  auto *RetainArray = dyn_cast_or_null<StrongRetainInst>(getInstBefore(Call));
  if (!RetainArray)
    return false;
  auto *ReleaseArray = dyn_cast_or_null<StrongReleaseInst>(getInstAfter(Call));
  if (!ReleaseArray)
    return false;
  if (ReleaseArray->getOperand() != RetainArray->getOperand())
    return false;

  DepInsts.push_back(ReleaseArray);
  DepInsts.push_back(Call);
  DepInsts.push_back(RetainArray);

  auto ArrayLoad = stripValueProjections(RetainArray->getOperand(), DepInsts);
  if (ArrayLoad != Self)
    return false;

  DepInsts.push_back(Self);
  return true;
}

/// Match a hoistable make_mutable call.
///
/// Precondition: The client must make sure that it is valid to actually hoist
/// the call. It must make sure that no write and no increment to the array
/// reference has happened such that hoisting is not valid.
///
/// This helper only checks that the operands computing the array reference
/// are also hoistable.
struct HoistableMakeMutable {
  SILLoop *Loop;
  bool IsHoistable;
  ApplyInst *MakeMutable;
  SmallVector<SILInstruction *, 24> DepInsts;

  HoistableMakeMutable(ArraySemanticsCall M, SILLoop *L) {
    IsHoistable = false;
    Loop = L;
    MakeMutable = M;

    // The function_ref needs to be invariant.
    if (Loop->contains(MakeMutable->getCallee()->getParentBB()))
      return;

    // The array reference is invariant.
    if (!L->contains(M.getSelf()->getParentBB())) {
      IsHoistable = true;
      return;
    }

    // Check whether we can hoist the dependent instructions resulting in the
    // array reference.
    if (canHoistDependentInstructions(M))
      IsHoistable = true;
  }

  /// Is this a hoistable make_mutable call.
  bool isHoistable() {
    return IsHoistable;
  }

  /// Hoist this make_mutable call and depend instructions to the preheader.
  void hoist() {
    auto *Term = Loop->getLoopPreheader()->getTerminator();
    for (auto *It : swift::reversed(DepInsts))
      It->moveBefore(Term);
    MakeMutable->moveBefore(Term);
  }

private:

  /// Check whether we can hoist the dependent instructions resulting in the
  /// array reference passed to the make_mutable call.
  /// We pattern match the first dimension's array access here.
  bool canHoistDependentInstructions(ArraySemanticsCall &M) {
    // Match get_element_addr call.
    // %124 = load %3
    // %125 = struct_extract %124
    // %126 = struct_extract %125
    // %127 = struct_extract %126
    // strong_retain %127
    // %129 = apply %70(%30, %124)
    // strong_release %127
    //
    // %131 = load %73
    // %132 = unchecked_ref_cast %131
    // %133 = enum $Optional<NativeObject>, #Optional.Some!enumelt.1, %132
    // %134 = struct_extract %129
    // %135 = pointer_to_address %134 to $*Array<Int>
    // %136 = mark_dependence %135 on %133

    auto *MarkDependence = dyn_cast<MarkDependenceInst>(M.getSelf());
    if (!MarkDependence)
      return false;
    DepInsts.push_back(MarkDependence);

    auto *PtrToAddrArrayAddr =
        dyn_cast<PointerToAddressInst>(MarkDependence->getValue());
    if (!PtrToAddrArrayAddr)
      return false;
    DepInsts.push_back(PtrToAddrArrayAddr);

    auto *StructExtractArrayAddr =
        dyn_cast<StructExtractInst>(PtrToAddrArrayAddr->getOperand());
    if (!StructExtractArrayAddr)
      return false;
    DepInsts.push_back(StructExtractArrayAddr);

    // Check the base the array element address is dependent on.
    auto *EnumArrayAddr = dyn_cast<EnumInst>(MarkDependence->getBase());
    if (!EnumArrayAddr)
      return false;
    DepInsts.push_back(EnumArrayAddr);
    auto *UncheckedRefCast =
        dyn_cast<UncheckedRefCastInst>(EnumArrayAddr->getOperand());
    if (!UncheckedRefCast)
      return false;
    DepInsts.push_back(UncheckedRefCast);
    auto *BaseLoad = dyn_cast<LoadInst>(UncheckedRefCast->getOperand());
    if (!BaseLoad ||  Loop->contains(BaseLoad->getOperand()->getParentBB()))
      return false;
    DepInsts.push_back(BaseLoad);

    // Check the get_element_addr call.
    ArraySemanticsCall GetElementAddrCall(
        StructExtractArrayAddr->getOperand().getDef());
    if (!GetElementAddrCall ||
        GetElementAddrCall.getKind() != ArrayCallKind::kGetElementAddress)
      return false;
    if (Loop->contains(
            ((ApplyInst *)GetElementAddrCall)->getCallee()->getParentBB()))
      return false;
    if (Loop->contains(GetElementAddrCall.getIndex()->getParentBB()))
      return false;

    auto *GetElementAddrArrayLoad =
        dyn_cast<LoadInst>(GetElementAddrCall.getSelf());
    if (!GetElementAddrArrayLoad ||
        Loop->contains(GetElementAddrArrayLoad->getOperand()->getParentBB()))
      return false;

    // Check the retain/release around the get_element_addr call.
    if (!matchSelfParameterSetup(GetElementAddrCall, GetElementAddrArrayLoad,
                                 DepInsts))
      return false;

    // Check check_subscript.
    // %116 = load %3
    // %118 = struct_extract %116
    // %119 = struct_extract %118
    // %120 = struct_extract %119
    // strong_retain %120
    // %122 = apply %23(%30, %69, %116)
    // strong_release %120
    //
    // Find the check_subscript call.
    auto *Check = findPreceedingCheckSubscriptOrMakeMutable(GetElementAddrCall);
    if (!Check)
      return false;

    ArraySemanticsCall CheckSubscript(Check);
    // The check_subscript call was removed.
    if (CheckSubscript.getKind() == ArrayCallKind::kMakeMutable)
      return true;

    if (Loop->contains(CheckSubscript.getIndex()->getParentBB()) ||
        Loop->contains(CheckSubscript.getArrayPropertyIsNativeTypeChecked()
                           ->getParentBB()))
      return false;

    auto *CheckSubscriptArrayLoad =
        dyn_cast<LoadInst>(CheckSubscript.getSelf());
    if (!CheckSubscript ||
        Loop->contains(CheckSubscriptArrayLoad->getOperand()->getParentBB()))
      return false;
  if (Loop->contains(
            ((ApplyInst *)CheckSubscript)->getCallee()->getParentBB()))
      return false;

    // The array must match get_element_addr's array.
    if (CheckSubscriptArrayLoad->getOperand() !=
        GetElementAddrArrayLoad->getOperand())
      return false;

    // Check the retain/release around the check_subscript call.
    if (!matchSelfParameterSetup(CheckSubscript, CheckSubscriptArrayLoad,
                                 DepInsts))
      return false;

    return true;
  }
};

/// Prove that there are not array value mutating or capturing operations in the
/// loop and hoist make_mutable.
bool COWArrayOpt::hoistInLoopWithOnlyNonArrayValueMutatingOperations() {
  // Only handle innermost loops.
  assert(Loop->getSubLoops().empty() && "Only works in innermost loops");

  DEBUG(llvm::dbgs() << "    Checking whether loop only has only non array "
                        "value mutating operations ...\n");

  // There is no current array addr value.
  CurrentArrayAddr = SILValue();

  // We need to cleanup the MatchedRelease on return.
  auto ReturnWithCleanup = [&] (bool LoopHasSafeOperations) {
    MatchedReleases.clear();
    return LoopHasSafeOperations;
  };

  llvm::SmallSet<SILValue, 16> ArrayValues;
  llvm::SmallSetVector<SILValue, 16> CreatedNonTrivialValues;
  llvm::SmallSet<SILInstruction *, 16> Releases;
  llvm::SmallVector<ArraySemanticsCall, 8> MakeMutableCalls;


  /// Make sure that no writes to an array value happens in the loop and that
  /// no array values are retained without being released before hitting a
  /// make_unique:
  ///
  /// * array semantic functions that don't change the uniqueness state to
  ///   non-unique are safe.
  /// * retains must be matched by a release before hitting a mutating operation
  /// * stores must not store an array value (only trivial stores are safe).
  ///
  auto &Module = Function->getModule();
  for (auto *BB : Loop->getBlocks()) {
    for (auto &InstIt : *BB) {
      auto *Inst = &InstIt;
{'fraction_non_alphanumeric': 0.11233603125872174, 'fraction_numerical': 0.004674853474741837, 'mean_word_length': 3.0404548230982473, 'pattern_counts': {'":': 0, '<': 341, '<?xml version=': 0, '>': 443, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5993094', 'n_tokens_mistral': 25333, 'n_tokens_neox': 24773, 'n_words': 7673}