text: //===--- InstOptUtils.cpp - SILOptimizer instruction utilities ------------===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2019 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/Utils/InstOptUtils.h"
  #include "swift/AST/GenericSignature.h"
  #include "swift/AST/SemanticAttrs.h"
  #include "swift/AST/SubstitutionMap.h"
  #include "swift/Basic/SmallPtrSetVector.h"
  #include "swift/SIL/ApplySite.h"
  #include "swift/SIL/BasicBlockUtils.h"
  #include "swift/SIL/DebugUtils.h"
  #include "swift/SIL/DynamicCasts.h"
  #include "swift/SIL/InstructionUtils.h"
  #include "swift/SIL/SILArgument.h"
  #include "swift/SIL/SILBuilder.h"
  #include "swift/SIL/SILDebugInfoExpression.h"
  #include "swift/SIL/SILModule.h"
  #include "swift/SIL/SILUndef.h"
  #include "swift/SIL/TypeLowering.h"
  #include "swift/SILOptimizer/Analysis/ARCAnalysis.h"
  #include "swift/SILOptimizer/Analysis/Analysis.h"
  #include "swift/SILOptimizer/Analysis/ArraySemantic.h"
  #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
  #include "swift/SILOptimizer/Utils/CFGOptUtils.h"
  #include "swift/SILOptimizer/Utils/ConstExpr.h"
  #include "swift/SILOptimizer/Utils/DebugOptUtils.h"
  #include "swift/SILOptimizer/Utils/ValueLifetime.h"
  #include "llvm/ADT/Optional.h"
  #include "llvm/ADT/SmallPtrSet.h"
  #include "llvm/ADT/StringSwitch.h"
  #include "llvm/IR/Intrinsics.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/Compiler.h"
  #include <deque>
  
  using namespace swift;
  
  static llvm::cl::opt<bool> EnableExpandAll("enable-expand-all",
                                             llvm::cl::init(false));
  
  static llvm::cl::opt<bool> KeepWillThrowCall(
      "keep-will-throw-call", llvm::cl::init(false),
      llvm::cl::desc(
        "Keep calls to swift_willThrow, even if the throw is optimized away"));
  
  Optional<SILBasicBlock::iterator> swift::getInsertAfterPoint(SILValue val) {
    if (auto *inst = val->getDefiningInstruction()) {
      return std::next(inst->getIterator());
    }
    if (isa<SILArgument>(val)) {
      return cast<SILArgument>(val)->getParentBlock()->begin();
    }
    return None;
  }
  
  /// Creates an increment on \p Ptr before insertion point \p InsertPt that
  /// creates a strong_retain if \p Ptr has reference semantics itself or a
  /// retain_value if \p Ptr is a non-trivial value without reference-semantics.
  NullablePtr<SILInstruction>
  swift::createIncrementBefore(SILValue ptr, SILInstruction *insertPt) {
    // Set up the builder we use to insert at our insertion point.
    SILBuilder builder(insertPt);
    auto loc = RegularLocation::getAutoGeneratedLocation();
  
    // If we have a trivial type, just bail, there is no work to do.
    if (ptr->getType().isTrivial(builder.getFunction()))
      return nullptr;
  
    // If Ptr is refcounted itself, create the strong_retain and
    // return.
    if (ptr->getType().isReferenceCounted(builder.getModule())) {
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)            \
      if (ptr->getType().is<Name##StorageType>())                                \
        return builder.create##Name##Retain(loc, ptr,                            \
                                            builder.getDefaultAtomicity());
  #include "swift/AST/ReferenceStorage.def"
  
      return builder.createStrongRetain(loc, ptr,
                                        builder.getDefaultAtomicity());
    }
  
    // Otherwise, create the retain_value.
    return builder.createRetainValue(loc, ptr, builder.getDefaultAtomicity());
  }
  
  /// Creates a decrement on \p ptr before insertion point \p InsertPt that
  /// creates a strong_release if \p ptr has reference semantics itself or
  /// a release_value if \p ptr is a non-trivial value without
  /// reference-semantics.
  NullablePtr<SILInstruction>
  swift::createDecrementBefore(SILValue ptr, SILInstruction *insertPt) {
    // Setup the builder we will use to insert at our insertion point.
    SILBuilder builder(insertPt);
    auto loc = RegularLocation::getAutoGeneratedLocation();
  
    if (ptr->getType().isTrivial(builder.getFunction()))
      return nullptr;
  
    // If ptr has reference semantics itself, create a strong_release.
    if (ptr->getType().isReferenceCounted(builder.getModule())) {
  #define ALWAYS_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)            \
      if (ptr->getType().is<Name##StorageType>())                                \
        return builder.create##Name##Release(loc, ptr,                           \
                                            builder.getDefaultAtomicity());
  #include "swift/AST/ReferenceStorage.def"
  
      return builder.createStrongRelease(loc, ptr,
                                         builder.getDefaultAtomicity());
    }
  
    // Otherwise create a release value.
    return builder.createReleaseValue(loc, ptr, builder.getDefaultAtomicity());
  }
  
  static bool isOSSAEndScopeWithNoneOperand(SILInstruction *i) {
    if (!isa<EndBorrowInst>(i) && !isa<DestroyValueInst>(i))
      return false;
    return i->getOperand(0).getOwnershipKind() == OwnershipKind::None;
  }
  
  /// Perform a fast local check to see if the instruction is dead.
  ///
  /// This routine only examines the state of the instruction at hand.
  bool swift::isInstructionTriviallyDead(SILInstruction *inst) {
    // At Onone, consider all uses, including the debug_info.
    // This way, debug_info is preserved at Onone.
    if (inst->hasUsesOfAnyResult()
        && inst->getFunction()->getEffectiveOptimizationMode()
               <= OptimizationMode::NoOptimization)
      return false;
  
    if (!onlyHaveDebugUsesOfAllResults(inst) || isa<TermInst>(inst))
      return false;
  
    if (auto *bi = dyn_cast<BuiltinInst>(inst)) {
      // Although the onFastPath builtin has no side-effects we don't want to
      // remove it.
      if (bi->getBuiltinInfo().ID == BuiltinValueKind::OnFastPath)
        return false;
      return !bi->mayHaveSideEffects();
    }
  
    // condfail instructions that obviously can't fail are dead.
    if (auto *cfi = dyn_cast<CondFailInst>(inst))
      if (auto *ili = dyn_cast<IntegerLiteralInst>(cfi->getOperand()))
        if (!ili->getValue())
          return true;
  
    // mark_uninitialized is never dead.
    if (isa<MarkUninitializedInst>(inst))
      return false;
  
    if (isa<DebugValueInst>(inst))
      return false;
  
    // These invalidate enums so "write" memory, but that is not an essential
    // operation so we can remove these if they are trivially dead.
    if (isa<UncheckedTakeEnumDataAddrInst>(inst))
      return true;
  
    // An ossa end scope instruction is trivially dead if its operand has
    // OwnershipKind::None. This can occur after CFG simplification in the
    // presence of non-payloaded or trivial payload cases of non-trivial enums.
    //
    // Examples of ossa end_scope instructions: end_borrow, destroy_value.
    if (inst->getFunction()->hasOwnership() &&
        isOSSAEndScopeWithNoneOperand(inst))
      return true;
  
    if (!inst->mayHaveSideEffects())
      return true;
  
    return false;
  }
  
  /// Return true if this is a release instruction and the released value
  /// is a part of a guaranteed parameter.
  bool swift::isIntermediateRelease(SILInstruction *inst,
                                    EpilogueARCFunctionInfo *eafi) {
    // Check whether this is a release instruction.
    if (!isa<StrongReleaseInst>(inst) && !isa<ReleaseValueInst>(inst))
      return false;
  
    // OK. we have a release instruction.
    // Check whether this is a release on part of a guaranteed function argument.
    SILValue Op = stripValueProjections(inst->getOperand(0));
    auto *arg = dyn_cast<SILFunctionArgument>(Op);
    if (!arg)
      return false;
  
    // This is a release on a guaranteed parameter. Its not the final release.
    if (arg->hasConvention(SILArgumentConvention::Direct_Guaranteed))
      return true;
  
    // This is a release on an owned parameter and its not the epilogue release.
    // Its not the final release.
    auto rel = eafi->computeEpilogueARCInstructions(
        EpilogueARCContext::EpilogueARCKind::Release, arg);
    if (rel.size() && !rel.count(inst))
      return true;
  
    // Failed to prove anything.
    return false;
  }
  
  bool swift::hasOnlyEndOfScopeOrEndOfLifetimeUses(SILInstruction *inst) {
    for (SILValue result : inst->getResults()) {
      for (Operand *use : result->getUses()) {
        SILInstruction *user = use->getUser();
        bool isDebugUser = user->isDebugInstruction();
        if (!isa<DestroyValueInst>(user) && !isa<EndLifetimeInst>(user) &&
            !isEndOfScopeMarker(user) && !isDebugUser)
          return false;
        // Include debug uses only in Onone mode.
        if (isDebugUser && inst->getFunction()->getEffectiveOptimizationMode() <=
                               OptimizationMode::NoOptimization)
          if (auto DbgVarInst = DebugVarCarryingInst(user)) {
            auto VarInfo = DbgVarInst.getVarInfo();
            if (VarInfo && !VarInfo->Implicit)
              return false;
          }
      }
    }
    return true;
  }
  
  unsigned swift::getNumInOutArguments(FullApplySite applySite) {
    assert(applySite);
    auto substConv = applySite.getSubstCalleeConv();
    unsigned numIndirectResults = substConv.getNumIndirectSILResults();
    unsigned numInOutArguments = 0;
    for (unsigned argIndex = 0; argIndex < applySite.getNumArguments();
         argIndex++) {
      // Skip indirect results.
      if (argIndex < numIndirectResults) {
        continue;
      }
      auto paramNumber = argIndex - numIndirectResults;
      auto ParamConvention =
          substConv.getParameters()[paramNumber].getConvention();
      switch (ParamConvention) {
      case ParameterConvention::Indirect_Inout:
      case ParameterConvention::Indirect_InoutAliasable: {
        ++numInOutArguments;
        break;
      default:
        break;
      }
      }
    }
    return numInOutArguments;
  }
  
  /// Return true iff the \p applySite calls a constant-evaluable function and
  /// it is non-generic and read/destroy only, which means that the call can do
  /// only the following and nothing else:
  ///   (1) The call may read any memory location.
  ///   (2) The call may destroy owned parameters i.e., consume them.
  ///   (3) The call may write into memory locations newly created by the call.
  ///   (4) The call may use assertions, which traps at runtime on failure.
  ///   (5) The call may return a non-generic value.
  /// Essentially, these are calls whose "effect" is visible only in their return
  /// value or through the parameters that are destroyed. The return value
  /// is also guaranteed to have value semantics as it is non-generic and
  /// reference semantics is not constant evaluable.
  static bool isNonGenericReadOnlyConstantEvaluableCall(FullApplySite applySite) {
    assert(applySite);
    SILFunction *callee = applySite.getCalleeFunction();
    if (!callee || !isConstantEvaluable(callee)) {
      return false;
    }
    return !applySite.hasSubstitutions() && !getNumInOutArguments(applySite) &&
           !applySite.getNumIndirectSILResults();
  }
  
  /// A scope-affecting instruction is an instruction which may end the scope of
  /// its operand or may produce scoped results that require cleaning up. E.g.
  /// begin_borrow, begin_access, copy_value, a call that produces a owned value
  /// are scoped instructions. The scope of the results of the first two
  /// instructions end with an end_borrow/acess instruction, while those of the
  /// latter two end with a consuming operation like destroy_value instruction.
  /// These instruction may also end the scope of its operand e.g. a call could
  /// consume owned arguments thereby ending its scope. Dead-code eliminating a
  /// scope-affecting instruction requires fixing the lifetime of the non-trivial
  /// operands of the instruction and requires cleaning up the end-of-scope uses
  /// of non-trivial results.
  ///
  /// \param inst instruction that checked for liveness.
  ///
  /// TODO: Handle partial_apply [stack] which has a dealloc_stack user.
  static bool isScopeAffectingInstructionDead(SILInstruction *inst,
                                              bool fixLifetime) {
    SILFunction *fun = inst->getFunction();
    assert(fun && "Instruction has no function.");
    // Only support ownership SIL for scoped instructions.
    if (!fun->hasOwnership()) {
      return false;
    }
    // If the instruction has any use other than end of scope use or destroy_value
    // use, bail out.
    if (!hasOnlyEndOfScopeOrEndOfLifetimeUses(inst)) {
      return false;
    }
    // If inst is a copy or beginning of scope, inst is dead, since we know that
    // it is used only in a destroy_value or end-of-scope instruction.
    if (getSingleValueCopyOrCast(inst))
      return true;
  
    switch (inst->getKind()) {
    case SILInstructionKind::LoadBorrowInst: {
      // A load_borrow only used in an end_borrow is dead.
      return true;
    }
    case SILInstructionKind::LoadInst: {
      LoadOwnershipQualifier loadOwnershipQual =
          cast<LoadInst>(inst)->getOwnershipQualifier();
      // If the load creates a copy, it is dead, since we know that if at all it
      // is used, it is only in a destroy_value instruction.
      return (loadOwnershipQual == LoadOwnershipQualifier::Copy ||
              loadOwnershipQual == LoadOwnershipQualifier::Trivial);
      // TODO: we can handle load [take] but we would have to know that the
      // operand has been consumed. Note that OperandOwnershipKind map does not
      // say this for load.
    }
    case SILInstructionKind::PartialApplyInst: {
      bool onlyTrivialArgs = true;
      for (auto &arg : cast<PartialApplyInst>(inst)->getArgumentOperands()) {
        auto argTy = arg.get()->getType();
        // Non-stack partial apply captures that are passed by address are always
        // captured at +1 by the closure contrext, regardless of the calling
        // convention.
        //
        // TODO: When on-stack partial applies are also handled, then their +0
        // address arguments can be ignored.
        //
        // FIXME: Even with fixLifetimes enabled, InstructionDeleter does not know
        // how to cleanup arguments captured by address. This should be as simple
        // as inserting a destroy_addr. But the analagous code in
        // tryDeleteDeadClosure() and keepArgsOfPartialApplyAlive() mysteriously
        // creates new alloc_stack's and invalidates stack nesting. So we
        // conservatively bail-out until we understand why that hack exists.
        if (argTy.isAddress())
          return false;
  
        onlyTrivialArgs &= argTy.isTrivial(*fun);
      }
      // Partial applies that are only used in destroys cannot have any effect on
      // the program state, provided the values they capture are explicitly
      // destroyed, which only happens when fixLifetime is true.
      return onlyTrivialArgs || fixLifetime;
    }
    case SILInstructionKind::StructInst:
    case SILInstructionKind::EnumInst:
    case SILInstructionKind::TupleInst:
    case SILInstructionKind::ConvertFunctionInst:
    case SILInstructionKind::DestructureStructInst:
    case SILInstructionKind::DestructureTupleInst: {
      // All these ownership forwarding instructions that are only used in
      // destroys are dead provided the values they consume are destroyed
      // explicitly.
      return true;
    }
    case SILInstructionKind::ApplyInst: {
      // The following property holds for constant-evaluable functions that do
      // not take arguments of generic type:
      // 1. they do not create objects having deinitializers with global
      // side effects, as they can only create objects consisting of trivial
      // values, (non-generic) arrays and strings.
      // 2. they do not use global variables or call arbitrary functions with
      // side effects.
      // The above two properties imply that a value returned by a constant
      // evaluable function does not have a deinitializer with global side
      // effects. Therefore, the deinitializer can be sinked.
      //
      // A generic, read-only constant evaluable call only reads and/or
      // destroys its (non-generic) parameters. It therefore cannot have any
      // side effects (note that parameters being non-generic have value
      // semantics). Therefore, the constant evaluable call can be removed
      // provided the parameter lifetimes are handled correctly, which is taken
      // care of by the function: \c deleteInstruction.
      FullApplySite applySite(cast<ApplyInst>(inst));
      return isNonGenericReadOnlyConstantEvaluableCall(applySite);
    }
    default: {
      return false;
    }
    }
  }
  
  static bool hasOnlyIncidentalUses(SILInstruction *inst,
                                    bool disallowDebugUses = false) {
    for (SILValue result : inst->getResults()) {
      for (Operand *use : result->getUses()) {
        SILInstruction *user = use->getUser();
        if (!isIncidentalUse(user))
          return false;
        if (disallowDebugUses && user->isDebugInstruction())
          return false;
      }
    }
    return true;
  }
  
  bool InstructionDeleter::trackIfDead(SILInstruction *inst) {
    bool fixLifetime = inst->getFunction()->hasOwnership();
    if (isInstructionTriviallyDead(inst)
        || isScopeAffectingInstructionDead(inst, fixLifetime)) {
      assert(!isIncidentalUse(inst) && !isa<DestroyValueInst>(inst) &&
             "Incidental uses cannot be removed in isolation. "
             "They would be removed iff the operand is dead");
      getCallbacks().notifyWillBeDeleted(inst);
      deadInstructions.insert(inst);
      return true;
    }
    return false;
  }
  
  void InstructionDeleter::forceTrackAsDead(SILInstruction *inst) {
    bool disallowDebugUses = inst->getFunction()->getEffectiveOptimizationMode()
                             <= OptimizationMode::NoOptimization;
    assert(hasOnlyIncidentalUses(inst, disallowDebugUses));
    getCallbacks().notifyWillBeDeleted(inst);
    deadInstructions.insert(inst);
  }
  
  /// Force-delete \p inst and all its uses.
  ///
  /// \p fixLifetimes causes new destroys to be inserted after dropping
  /// operands.
  ///
  /// \p forceDeleteUsers allows deleting an instruction with non-incidental,
  /// non-destoy uses, such as a store.
  ///
  /// Does not call callbacks.notifyWillBeDeleted for \p inst. But does
  /// for any other instructions that become dead as a result.
  ///
  /// Carefully orchestrated steps for deleting an instruction with its uses:
  ///
  /// Recursively gather the instruction's uses into the toDeleteInsts set and
  /// dropping the operand for each use traversed.
  ///
  /// For the remaining operands, insert destroys for consuming operands and track
  /// newly dead operand definitions.
  ///
  /// Finally, erase the instruction.
  void InstructionDeleter::deleteWithUses(SILInstruction *inst, bool fixLifetimes,
                                          bool forceDeleteUsers) {
    // Cannot fix operand lifetimes in non-ownership SIL.
    assert(!fixLifetimes || inst->getFunction()->hasOwnership());
  
    // Recursively visit all uses while growing toDeleteInsts in def-use order and
    // dropping dead operands.
    SmallVector<SILInstruction *, 4> toDeleteInsts;
  
    toDeleteInsts.push_back(inst);
    swift::salvageDebugInfo(inst);
    for (unsigned idx = 0; idx < toDeleteInsts.size(); ++idx) {
      for (SILValue result : toDeleteInsts[idx]->getResults()) {
        // Temporary use vector to avoid iterator invalidation.
        auto uses = llvm::to_vector<4>(result->getUses());
        for (Operand *use : uses) {
          SILInstruction *user = use->getUser();
          assert(forceDeleteUsers || isIncidentalUse(user) ||
                 isa<DestroyValueInst>(user));
          assert(!isa<BranchInst>(user) && "can't delete phis");
  
          toDeleteInsts.push_back(user);
          swift::salvageDebugInfo(user);
          use->drop();
        }
      }
    }
    // Process the remaining operands. Insert destroys for consuming
    // operands. Track newly dead operand values.
    for (auto *inst : toDeleteInsts) {
      for (Operand &operand : inst->getAllOperands()) {
        SILValue operandValue = operand.get();
        // Check for dead operands, which are dropped above.
        if (!operandValue)
          continue;
  
        if (fixLifetimes && operand.isConsuming()) {
          SILBuilderWithScope builder(inst);
          auto *dvi = builder.createDestroyValue(inst->getLoc(), operandValue);
          getCallbacks().createdNewInst(dvi);
        }
        auto *operDef = operandValue->getDefiningInstruction();
        operand.drop();
        if (operDef) {
          trackIfDead(operDef);
        }
      }
      inst->dropNonOperandReferences();
      deadInstructions.remove(inst);
      getCallbacks().deleteInst(inst, false /*notify when deleting*/);
    }
  }
  
  void InstructionDeleter::cleanupDeadInstructions() {
    while (!deadInstructions.empty()) {
      SmallVector<SILInstruction *, 8> currentDeadInsts(deadInstructions.begin(),
                                                        deadInstructions.end());
      // Though deadInstructions is cleared here, calls to deleteInstruction may
      // append to deadInstructions. So we need to iterate until this it is empty.
      deadInstructions.clear();
      for (SILInstruction *deadInst : currentDeadInsts) {
        // deadInst will not have been deleted in the previous iterations,
        // because, by definition, deleteInstruction will only delete an earlier
        // instruction and its incidental/destroy uses. The former cannot be
        // deadInst as deadInstructions is a set vector, and the latter cannot be
        // in deadInstructions as they are incidental uses which are never added
        // to deadInstructions.
        deleteWithUses(deadInst,
                       /*fixLifetimes*/ deadInst->getFunction()->hasOwnership());
      }
    }
  }
  
  bool InstructionDeleter::deleteIfDead(SILInstruction *inst) {
    bool fixLifetime = inst->getFunction()->hasOwnership();
    if (isInstructionTriviallyDead(inst)
        || isScopeAffectingInstructionDead(inst, fixLifetime)) {
      getCallbacks().notifyWillBeDeleted(inst);
      deleteWithUses(inst, fixLifetime);
      return true;
    }
    return false;
  }
  
  void InstructionDeleter::forceDeleteAndFixLifetimes(SILInstruction *inst) {
    SILFunction *fun = inst->getFunction();
    assert(fun->hasOwnership());
    bool disallowDebugUses =
        fun->getEffectiveOptimizationMode() <= OptimizationMode::NoOptimization;
    assert(hasOnlyIncidentalUses(inst, disallowDebugUses));
    deleteWithUses(inst, /*fixLifetimes*/ true);
  }
  
  void InstructionDeleter::forceDelete(SILInstruction *inst) {
    bool disallowDebugUses =
        inst->getFunction()->getEffectiveOptimizationMode() <=
        OptimizationMode::NoOptimization;
    assert(hasOnlyIncidentalUses(inst, disallowDebugUses));
    deleteWithUses(inst, /*fixLifetimes*/ false);
  }
  
  void InstructionDeleter::recursivelyDeleteUsersIfDead(SILInstruction *inst) {
    SmallVector<SILInstruction *, 8> users;
    for (SILValue result : inst->getResults())
      for (Operand *use : result->getUses())
        users.push_back(use->getUser());
  
    for (SILInstruction *user : users)
      recursivelyDeleteUsersIfDead(user);
    deleteIfDead(inst);
  }
  
  void InstructionDeleter::recursivelyForceDeleteUsersAndFixLifetimes(
      SILInstruction *inst) {
    for (SILValue result : inst->getResults()) {
      while (!result->use_empty()) {
        SILInstruction *user = result->use_begin()->getUser();
        recursivelyForceDeleteUsersAndFixLifetimes(user);
      }
    }
    if (isIncidentalUse(inst) || isa<DestroyValueInst>(inst)) {
      forceDelete(inst);
      return;
      }
    forceDeleteAndFixLifetimes(inst);
  }
  
  void swift::eliminateDeadInstruction(SILInstruction *inst,
                                       InstModCallbacks callbacks) {
    InstructionDeleter deleter(callbacks);
    deleter.trackIfDead(inst);
    deleter.cleanupDeadInstructions();
  }
  
  void swift::recursivelyDeleteTriviallyDeadInstructions(
      ArrayRef<SILInstruction *> ia, bool force, InstModCallbacks callbacks) {
    // Delete these instruction and others that become dead after it's deleted.
    llvm::SmallPtrSet<SILInstruction *, 8> deadInsts;
    for (auto *inst : ia) {
      // If the instruction is not dead and force is false, do nothing.
      if (force || isInstructionTriviallyDead(inst))
        deadInsts.insert(inst);
    }
    llvm::SmallPtrSet<SILInstruction *, 8> nextInsts;
    while (!deadInsts.empty()) {
      for (auto inst : deadInsts) {
        // Call the callback before we mutate the to be deleted instruction in any
        // way.
        callbacks.notifyWillBeDeleted(inst);
  
        // Check if any of the operands will become dead as well.
        MutableArrayRef<Operand> operands = inst->getAllOperands();
        for (Operand &operand : operands) {
          SILValue operandVal = operand.get();
          if (!operandVal)
            continue;
  
          // Remove the reference from the instruction being deleted to this
          // operand.
          operand.drop();
  
          // If the operand is an instruction that is only used by the instruction
          // being deleted, delete it.
          if (auto *operandValInst = operandVal->getDefiningInstruction())
            if (!deadInsts.count(operandValInst) &&
                isInstructionTriviallyDead(operandValInst))
              nextInsts.insert(operandValInst);
        }
  
        // If we have a function ref inst, we need to especially drop its function
        // argument so that it gets a proper ref decrement.
        if (auto *fri = dyn_cast<FunctionRefBaseInst>(inst))
          fri->dropReferencedFunction();
      }
  
      for (auto inst : deadInsts) {
        // This will remove this instruction and all its uses.
        eraseFromParentWithDebugInsts(inst, callbacks);
      }
  
      nextInsts.swap(deadInsts);
      nextInsts.clear();
    }
  }
  
  /// If the given instruction is dead, delete it along with its dead
  /// operands.
  ///
  /// \param inst The instruction to be deleted.
  /// \param force If force is set, don't check if the top level instruction is
  ///        considered dead - delete it regardless.
  void swift::recursivelyDeleteTriviallyDeadInstructions(
      SILInstruction *inst, bool force, InstModCallbacks callbacks) {
    ArrayRef<SILInstruction *> ai = ArrayRef<SILInstruction *>(inst);
    recursivelyDeleteTriviallyDeadInstructions(ai, force, callbacks);
  }
  
  void swift::collectUsesOfValue(SILValue v,
                                 llvm::SmallPtrSetImpl<SILInstruction *> &insts) {
    for (auto ui = v->use_begin(), E = v->use_end(); ui != E; ++ui) {
      auto *user = ui->getUser();
      // Instruction has been processed.
      if (!insts.insert(user).second)
        continue;
  
      // Collect the users of this instruction.
      for (auto result : user->getResults())
        collectUsesOfValue(result, insts);
    }
  }
  
  void swift::eraseUsesOfValue(SILValue v) {
    llvm::SmallPtrSet<SILInstruction *, 4> insts;
    // Collect the uses.
    collectUsesOfValue(v, insts);
    // Erase the uses, we can have instructions that become dead because
    // of the removal of these instructions, leave to DCE to cleanup.
    // Its not safe to do recursively delete here as some of the SILInstruction
    // maybe tracked by this set.
    for (auto inst : insts) {
      inst->replaceAllUsesOfAllResultsWithUndef();
      inst->eraseFromParent();
    }
  }
  
  SILValue swift::
  getConcreteValueOfExistentialBox(AllocExistentialBoxInst *existentialBox,
                                    SILInstruction *ignoreUser) {
    StoreInst *singleStore = nullptr;
    SmallPtrSetVector<Operand *, 32> worklist;
    for (auto *use : getNonDebugUses(existentialBox)) {
      worklist.insert(use);
    }
  
    while (!worklist.empty()) {
      auto *use = worklist.pop_back_val();
      SILInstruction *user = use->getUser();
      switch (user->getKind()) {
      case SILInstructionKind::StrongRetainInst:
      case SILInstructionKind::StrongReleaseInst:
      case SILInstructionKind::DestroyValueInst:
      case SILInstructionKind::EndBorrowInst:
        break;
      case SILInstructionKind::CopyValueInst:
      case SILInstructionKind::BeginBorrowInst:
        // Look through copy_value, begin_borrow
        for (SILValue result : user->getResults())
          for (auto *transitiveUse : result->getUses())
            worklist.insert(transitiveUse);
        break;
      case SILInstructionKind::ProjectExistentialBoxInst: {
        auto *projectedAddr = cast<ProjectExistentialBoxInst>(user);
        for (Operand *addrUse : getNonDebugUses(projectedAddr)) {
          if (auto *store = dyn_cast<StoreInst>(addrUse->getUser())) {
            assert(store->getSrc() != projectedAddr && "cannot store an address");
            // Bail if there are multiple stores.
            if (singleStore)
              return SILValue();
            singleStore = store;
            continue;
          }
          // If there are other users to the box value address then bail out.
          return SILValue();
        }
        break;
      }
      case SILInstructionKind::BuiltinInst: {
        auto *builtin = cast<BuiltinInst>(user);
        if (KeepWillThrowCall ||
            builtin->getBuiltinInfo().ID != BuiltinValueKind::WillThrow) {
          return SILValue();
        }
        break;
      }
      default:
        if (user != ignoreUser)
          return SILValue();
        break;
      }
    }
    if (!singleStore)
      return SILValue();
    return singleStore->getSrc();
  }
  
  SILValue swift::
  getConcreteValueOfExistentialBoxAddr(SILValue addr, SILInstruction *ignoreUser) {
    auto *stackLoc = dyn_cast<AllocStackInst>(addr);
    if (!stackLoc)
      return SILValue();
  
    StoreInst *singleStackStore = nullptr;
    for (Operand *stackUse : stackLoc->getUses()) {
      SILInstruction *stackUser = stackUse->getUser();
      switch (stackUser->getKind()) {
      case SILInstructionKind::DestroyAddrInst: {
        // Make sure the destroy_addr is the instruction before one of our
        // dealloc_stack insts and is directly on the stack location.
        auto next = std::next(stackUser->getIterator());
        if (auto *dsi = dyn_cast<DeallocStackInst>(next))
          if (dsi->getOperand() != stackLoc)
            return SILValue();
        break;
      }
      case SILInstructionKind::DeallocStackInst:
      case SILInstructionKind::LoadInst:
        break;
      case SILInstructionKind::DebugValueInst:
        if (!DebugValueInst::hasAddrVal(stackUser)) {
          if (stackUser != ignoreUser)
            return SILValue();
        }
        break;
      case SILInstructionKind::StoreInst: {
        auto *store = cast<StoreInst>(stackUser);
        assert(store->getSrc() != stackLoc && "cannot store an address");
        // Bail if there are multiple stores.
        if (singleStackStore)
          return SILValue();
        singleStackStore = store;
        break;
      }
      default:
        if (stackUser != ignoreUser)
          return SILValue();
        break;
      }
    }
    if (!singleStackStore)
      return SILValue();
  
    // Look through copy value insts.
    SILValue val = singleStackStore->getSrc();
    while (auto *cvi = dyn_cast<CopyValueInst>(val))
      val = cvi->getOperand();
    auto *box = dyn_cast<AllocExistentialBoxInst>(val);
    if (!box)
      return SILValue();
  
    return getConcreteValueOfExistentialBox(box, singleStackStore);
  }
  
  bool swift::mayBindDynamicSelf(SILFunction *F) {
    if (!F->hasDynamicSelfMetadata())
      return false;
  
    SILValue mdArg = F->getDynamicSelfMetadata();
  
    for (Operand *mdUse : mdArg->getUses()) {
      SILInstruction *mdUser = mdUse->getUser();
      for (Operand &typeDepOp : mdUser->getTypeDependentOperands()) {
        if (typeDepOp.get() == mdArg)
          return true;
      }
    }
    return false;
  }
  
  static SILValue skipAddrProjections(SILValue v) {
    for (;;) {
      switch (v->getKind()) {
      case ValueKind::IndexAddrInst:
      case ValueKind::IndexRawPointerInst:
      case ValueKind::StructElementAddrInst:
      case ValueKind::TupleElementAddrInst:
        v = cast<SingleValueInstruction>(v)->getOperand(0);
        break;
      default:
        return v;
      }
    }
    llvm_unreachable("there is no escape from an infinite loop");
  }
  
  /// Check whether the \p addr is an address of a tail-allocated array element.
  bool swift::isAddressOfArrayElement(SILValue addr) {
    addr = stripAddressProjections(addr);
    if (auto *md = dyn_cast<MarkDependenceInst>(addr))
      addr = stripAddressProjections(md->getValue());
  
    // High-level SIL: check for an get_element_address array semantics call.
    if (auto *ptrToAddr = dyn_cast<PointerToAddressInst>(addr))
      if (auto *sei = dyn_cast<StructExtractInst>(ptrToAddr->getOperand())) {
        ArraySemanticsCall call(sei->getOperand());
        if (call && call.getKind() == ArrayCallKind::kGetElementAddress)
          return true;
      }
  
    // Check for an tail-address (of an array buffer object).
    if (isa<RefTailAddrInst>(skipAddrProjections(addr)))
      return true;
  
    return false;
  }
  
  /// Find a new position for an ApplyInst's FuncRef so that it dominates its
  /// use. Not that FunctionRefInsts may be shared by multiple ApplyInsts.
  void swift::placeFuncRef(ApplyInst *ai, DominanceInfo *domInfo) {
    FunctionRefInst *funcRef = cast<FunctionRefInst>(ai->getCallee());
    SILBasicBlock *domBB = domInfo->findNearestCommonDominator(
        ai->getParent(), funcRef->getParent());
    if (domBB == ai->getParent() && domBB != funcRef->getParent())
      // Prefer to place the FuncRef immediately before the call. Since we're
      // moving FuncRef up, this must be the only call to it in the block.
      funcRef->moveBefore(ai);
    else
      // Otherwise, conservatively stick it at the beginning of the block.
      funcRef->moveBefore(&*domBB->begin());
  }
  
  /// Add an argument, \p val, to the branch-edge that is pointing into
  /// block \p Dest. Return a new instruction and do not erase the old
  /// instruction.
  TermInst *swift::addArgumentsToBranch(ArrayRef<SILValue> vals,
                                        SILBasicBlock *dest, TermInst *branch) {
    SILBuilderWithScope builder(branch);
  
    if (auto *cbi = dyn_cast<CondBranchInst>(branch)) {
      SmallVector<SILValue, 8> trueArgs;
      SmallVector<SILValue, 8> falseArgs;
  
      for (auto arg : cbi->getTrueArgs())
        trueArgs.push_back(arg);
  
      for (auto arg : cbi->getFalseArgs())
        falseArgs.push_back(arg);
  
      if (dest == cbi->getTrueBB()) {
        for (auto val : vals)
          trueArgs.push_back(val);
        assert(trueArgs.size() == dest->getNumArguments());
      } else {
        for (auto val : vals)
          falseArgs.push_back(val);
        assert(falseArgs.size() == dest->getNumArguments());
      }
  
      return builder.createCondBranch(
          cbi->getLoc(), cbi->getCondition(), cbi->getTrueBB(), trueArgs,
          cbi->getFalseBB(), falseArgs, cbi->getTrueBBCount(),
          cbi->getFalseBBCount());
    }
  
    if (auto *bi = dyn_cast<BranchInst>(branch)) {
      SmallVector<SILValue, 8> args;
  
      for (auto arg : bi->getArgs())
        args.push_back(arg);
  
      for (auto val : vals)
        args.push_back(val);
      assert(args.size() == dest->getNumArguments());
      return builder.createBranch(bi->getLoc(), bi->getDestBB(), args);
    }
  
    llvm_unreachable("unsupported terminator");
  }
  
  SILLinkage swift::getSpecializedLinkage(SILFunction *f, SILLinkage linkage) {
    if (hasPrivateVisibility(linkage) && !f->isSerialized()) {
      // Specializations of private symbols should remain so, unless
      // they were serialized, which can only happen when specializing
      // definitions from a standard library built with -sil-serialize-all.
      return SILLinkage::Private;
    }
  
    return SILLinkage::Shared;
  }
  
  /// Cast a value into the expected, ABI compatible type if necessary.
  /// This may happen e.g. when:
  /// - a type of the return value is a subclass of the expected return type.
  /// - actual return type and expected return type differ in optionality.
  /// - both types are tuple-types and some of the elements need to be casted.
  /// Return the cast value and true if a CFG modification was required
  /// NOTE: We intentionally combine the checking of the cast's handling
  /// possibility and the transformation performing the cast in the same function,
  /// to avoid any divergence between the check and the implementation in the
  /// future.
  ///
  /// \p usePoints are required when \p value has guaranteed ownership. It must be
  /// the last users of the returned, casted value. A usePoint cannot be a
  /// BranchInst (a phi is never the last guaranteed user). \p builder's current
  /// insertion point must dominate all \p usePoints. \p usePoints must
  /// collectively post-dominate \p builder's current insertion point.
  ///
  /// NOTE: The implementation of this function is very closely related to the
  /// rules checked by SILVerifier::requireABICompatibleFunctionTypes. It must
  /// handle all cases recognized by SILFunctionType::isABICompatibleWith (see
  /// areABICompatibleParamsOrReturns()).
  std::pair<SILValue, bool /* changedCFG */>
  swift::castValueToABICompatibleType(SILBuilder *builder, SILLocation loc,
                                      SILValue value, SILType srcTy,
                                      SILType destTy,
                                      ArrayRef<SILInstruction *> usePoints) {
    assert(value.getOwnershipKind() != OwnershipKind::Guaranteed
           || !usePoints.empty() && "guaranteed value must have use points");
  
    // No cast is required if types are the same.
    if (srcTy == destTy)
      return {value, false};
  
    if (srcTy.isAddress() && destTy.isAddress()) {
      // Cast between two addresses and that's it.
      return {builder->createUncheckedAddrCast(loc, value, destTy), false};
    }
  
    // If both types are classes and dest is the superclass of src,
    // simply perform an upcast.
    if (destTy.isExactSuperclassOf(srcTy)) {
      return {builder->createUpcast(loc, value, destTy), false};
    }
  
    if (srcTy.isHeapObjectReferenceType() && destTy.isHeapObjectReferenceType()) {
      return {builder->createUncheckedRefCast(loc, value, destTy), false};
    }
  
    if (auto mt1 = srcTy.getAs<AnyMetatypeType>()) {
      if (auto mt2 = destTy.getAs<AnyMetatypeType>()) {
        if (mt1->getRepresentation() == mt2->getRepresentation()) {
          // If builder.Type needs to be casted to A.Type and
          // A is a superclass of builder, then it can be done by means
          // of a simple upcast.
          if (mt2.getInstanceType()->isExactSuperclassOf(mt1.getInstanceType())) {
            return {builder->createUpcast(loc, value, destTy), false};
          }
  
          // Cast between two metatypes and that's it.
          return {builder->createUncheckedReinterpretCast(loc, value, destTy),
                  false};
        }
      }
    }
  
    // Check if src and dest types are optional.
    auto optionalSrcTy = srcTy.getOptionalObjectType();
    auto optionalDestTy = destTy.getOptionalObjectType();
  
    // Both types are optional.
    if (optionalDestTy && optionalSrcTy) {
      // If both wrapped types are classes and dest is the superclass of src,
      // simply perform an upcast.
      if (optionalDestTy.isExactSuperclassOf(optionalSrcTy)) {
        // Insert upcast.
        return {builder->createUpcast(loc, value, destTy), false};
      }
  
      // Unwrap the original optional value.
      auto *someDecl = builder->getASTContext().getOptionalSomeDecl();
      auto *curBB = builder->getInsertionPoint()->getParent();
      auto *contBB = curBB->split(builder->getInsertionPoint());
      auto *someBB = builder->getFunction().createBasicBlockAfter(curBB);
      auto *noneBB = builder->getFunction().createBasicBlockAfter(someBB);
  
      auto *phi = contBB->createPhiArgument(destTy, value.getOwnershipKind());
      if (phi->getOwnershipKind() == OwnershipKind::Guaranteed) {
        auto createEndBorrow = [&](SILBasicBlock::iterator insertPt) {
          builder->setInsertionPoint(insertPt);
          builder->createEndBorrow(loc, phi);
        };
        for (SILInstruction *user : usePoints) {
          if (isa<TermInst>(user)) {
            assert(!isa<BranchInst>(user) && "no branch as guaranteed use point");
            for (auto *succBB : user->getParent()->getSuccessorBlocks()) {
              createEndBorrow(succBB->begin());
            }
            continue;
          }
          createEndBorrow(std::next(user->getIterator()));
        }
      }
  
      SmallVector<std::pair<EnumElementDecl *, SILBasicBlock *>, 1> caseBBs;
      caseBBs.push_back(std::make_pair(someDecl, someBB));
      builder->setInsertionPoint(curBB);
      auto *switchEnum = builder->createSwitchEnum(loc, value, noneBB, caseBBs);
      // In OSSA switch_enum destinations have terminator results.
      //
      // TODO: This should be in a switchEnum utility.
      SILValue unwrappedValue;
      if (builder->hasOwnership()) {
        unwrappedValue = switchEnum->createOptionalSomeResult();
        builder->setInsertionPoint(someBB);
      } else {
        builder->setInsertionPoint(someBB);
        unwrappedValue = builder->createUncheckedEnumData(loc, value, someDecl);
      }
      // Cast the unwrapped value.
      SILValue castedUnwrappedValue;
      std::tie(castedUnwrappedValue, std::ignore) = castValueToABICompatibleType(
        builder, loc, unwrappedValue, optionalSrcTy, optionalDestTy, usePoints);
      // Wrap into optional. An owned value is forwarded through the cast and into
      // the Optional. A borrowed value will have a nested borrow for the
      // rewrapped Optional.
      SILValue someValue =
          builder->createOptionalSome(loc, castedUnwrappedValue, destTy);
      if (phi->getOwnershipKind() == OwnershipKind::Guaranteed) {
         someValue = builder->createBeginBorrow(loc, someValue);
      }
      builder->createBranch(loc, contBB, {someValue});
  
      // Handle the None case.
      builder->setInsertionPoint(noneBB);
      SILValue noneValue = builder->createOptionalNone(loc, destTy);
      if (phi->getOwnershipKind() == OwnershipKind::Guaranteed) {
         noneValue = builder->createBeginBorrow(loc, noneValue);
      }
      builder->createBranch(loc, contBB, {noneValue});
      builder->setInsertionPoint(contBB->begin());
  
      return {phi, true};
    }
  
    // Src is not optional, but dest is optional.
    if (!optionalSrcTy && optionalDestTy) {
      auto optionalSrcCanTy =
          OptionalType::get(srcTy.getASTType())->getCanonicalType();
      auto loweredOptionalSrcType =
          SILType::getPrimitiveObjectType(optionalSrcCanTy);
  
      // Wrap the source value into an optional first.
      SILValue wrappedValue =
          builder->createOptionalSome(loc, value, loweredOptionalSrcType);
      // Cast the wrapped value.
      return castValueToABICompatibleType(builder, loc, wrappedValue,
                                          wrappedValue->getType(), destTy,
                                          usePoints);
    }
  
    // Handle tuple types.
    // Extract elements, cast each of them, create a new tuple.
    if (auto srcTupleTy = srcTy.getAs<TupleType>()) {
      SmallVector<SILValue, 8> expectedTuple;
      bool changedCFG = false;
      auto castElement = [&](unsigned idx, SILValue element) {
        // Cast the value if necessary.
        bool neededCFGChange;
        std::tie(element, neededCFGChange) = castValueToABICompatibleType(
            builder, loc, element, srcTy.getTupleElementType(idx),
            destTy.getTupleElementType(idx), usePoints);
        changedCFG |= neededCFGChange;
        expectedTuple.push_back(element);
      };
      builder->emitDestructureValueOperation(loc, value, castElement);
      return {builder->createTuple(loc, destTy, expectedTuple), changedCFG};
    }
  
    // Function types are interchangeable if they're also ABI-compatible.
    if (srcTy.is<SILFunctionType>()) {
      if (destTy.is<SILFunctionType>()) {
        assert(srcTy.getAs<SILFunctionType>()->isNoEscape()
                   == destTy.getAs<SILFunctionType>()->isNoEscape()
               || srcTy.getAs<SILFunctionType>()->getRepresentation()
                          != SILFunctionType::Representation::Thick
                      && "Swift thick functions that differ in escapeness are "
                         "not ABI "
                         "compatible");
        // Insert convert_function.
        return {builder->createConvertFunction(loc, value, destTy,
                                               /*WithoutActuallyEscaping=*/false),
                false};
      }
    }
  
    llvm::errs() << "Source type: " << srcTy << "\n";
    llvm::errs() << "Destination type: " << destTy << "\n";
    llvm_unreachable("Unknown combination of types for casting");
  }
  
  ProjectBoxInst *swift::getOrCreateProjectBox(AllocBoxInst *abi,
                                               unsigned index) {
    SILBasicBlock::iterator iter(abi);
    ++iter;
    assert(iter != abi->getParent()->end()
           && "alloc_box cannot be the last instruction of a block");
    SILInstruction *nextInst = &*iter;
    if (auto *pbi = dyn_cast<ProjectBoxInst>(nextInst)) {
      if (pbi->getOperand() == abi && pbi->getFieldIndex() == index)
        return pbi;
    }
  
    SILBuilder builder(nextInst);
    return builder.createProjectBox(abi->getLoc(), abi, index);
  }
  
  // Peek through trivial Enum initialization, typically for pointless
  // Optionals.
  //
  // Given an UncheckedTakeEnumDataAddrInst, check that there are no
  // other uses of the Enum value and return the address used to initialized the
  // enum's payload:
  //
  //   %stack_adr = alloc_stack
  //   %data_adr  = init_enum_data_addr %stk_adr
  //   %enum_adr  = inject_enum_addr %stack_adr
  //   %copy_src  = unchecked_take_enum_data_addr %enum_adr
  //   dealloc_stack %stack_adr
  //   (No other uses of %stack_adr.)
  InitEnumDataAddrInst *
  swift::findInitAddressForTrivialEnum(UncheckedTakeEnumDataAddrInst *utedai) {
    auto *asi = dyn_cast<AllocStackInst>(utedai->getOperand());
    if (!asi)
      return nullptr;
  
    SILInstruction *singleUser = nullptr;
    for (auto use : asi->getUses()) {
      auto *user = use->getUser();
      if (user == utedai)
        continue;
  
      // As long as there's only one UncheckedTakeEnumDataAddrInst and one
      // InitEnumDataAddrInst, we don't care how many InjectEnumAddr and
      // DeallocStack users there are.
      if (isa<InjectEnumAddrInst>(user) || isa<DeallocStackInst>(user))
        continue;
  
      if (singleUser)
        return nullptr;
  
      singleUser = user;
    }
    if (!singleUser)
      return nullptr;
  
    // Assume, without checking, that the returned InitEnumDataAddr dominates the
    // given UncheckedTakeEnumDataAddrInst, because that's how SIL is defined. I
    // don't know where this is actually verified.
    return dyn_cast<InitEnumDataAddrInst>(singleUser);
  }
  
  //===----------------------------------------------------------------------===//
  //                              Closure Deletion
  //===----------------------------------------------------------------------===//
  
  /// NOTE: Instructions with transitive ownership kind are assumed to not keep
  /// the underlying value alive as well. This is meant for instructions only
  /// with non-transitive users.
  static bool useDoesNotKeepValueAlive(const SILInstruction *inst) {
    switch (inst->getKind()) {
    case SILInstructionKind::StrongRetainInst:
    case SILInstructionKind::StrongReleaseInst:
    case SILInstructionKind::DestroyValueInst:
    case SILInstructionKind::RetainValueInst:
    case SILInstructionKind::ReleaseValueInst:
    case SILInstructionKind::DebugValueInst:
    case SILInstructionKind::EndBorrowInst:
      return true;
    default:
      return false;
    }
  }
  
  static bool useHasTransitiveOwnership(const SILInstruction *inst) {
    // convert_escape_to_noescape is used to convert to a @noescape function type.
    // It does not change ownership of the function value.
    if (isa<ConvertEscapeToNoEscapeInst>(inst))
      return true;
  
    // Look through copy_value, begin_borrow. They are inert for our purposes, but
    // we need to look through it.
    return isa<CopyValueInst>(inst) || isa<BeginBorrowInst>(inst);
  }
  
  static bool shouldDestroyPartialApplyCapturedArg(SILValue arg,
                                                   SILParameterInfo paramInfo,
                                                   const SILFunction &F) {
    // If we have a non-trivial type and the argument is passed in @inout, we do
    // not need to destroy it here. This is something that is implicit in the
    // partial_apply design that will be revisited when partial_apply is
    // redesigned.
    if (paramInfo.isIndirectMutating())
      return false;
  
    // If we have a trivial type, we do not need to put in any extra releases.
    if (arg->getType().isTrivial(F))
      return false;
  
    // We handle all other cases.
    return true;
  }
  
  void swift::emitDestroyOperation(SILBuilder &builder, SILLocation loc,
                                   SILValue operand, InstModCallbacks callbacks) {
    // If we have an address, we insert a destroy_addr and return. Any live range
    // issues must have been dealt with by our caller.
    if (operand->getType().isAddress()) {
      // Then emit the destroy_addr for this operand. This function does not
      // delete any instructions
      SILInstruction *newInst = builder.emitDestroyAddrAndFold(loc, operand);
      if (newInst != nullptr)
        callbacks.createdNewInst(newInst);
      return;
    }
  
    // Otherwise, we have an object. We emit the most optimized form of release
    // possible for that value.
  
    // If we have qualified ownership, we should just emit a destroy value.
    if (builder.getFunction().hasOwnership()) {
      callbacks.createdNewInst(builder.createDestroyValue(loc, operand));
      return;
    }
  
    if (operand->getType().hasReferenceSemantics()) {
      auto u = builder.emitStrongRelease(loc, operand);
      if (u.isNull())
        return;
  
      if (auto *SRI = u.dyn_cast<StrongRetainInst *>()) {
        callbacks.deleteInst(SRI);
        return;
      }
  
      callbacks.createdNewInst(u.get<StrongReleaseInst *>());
      return;
    }
  
    auto u = builder.emitReleaseValue(loc, operand);
    if (u.isNull())
      return;
  
    if (auto *rvi = u.dyn_cast<RetainValueInst *>()) {
      callbacks.deleteInst(rvi);
      return;
    }
  
    callbacks.createdNewInst(u.get<ReleaseValueInst *>());
  }
  
  // *HEY YOU, YES YOU, PLEASE READ*. Even though a textual partial apply is
  // printed with the convention of the closed over function upon it, all
  // non-inout arguments to a partial_apply are passed at +1. This includes
  // arguments that will eventually be passed as guaranteed or in_guaranteed to
  // the closed over function. This is because the partial apply is building up a
  // boxed aggregate to send off to the closed over function. Of course when you
  // call the function, the proper conventions will be used.
  void swift::releasePartialApplyCapturedArg(SILBuilder &builder, SILLocation loc,
                                             SILValue arg,
                                             SILParameterInfo paramInfo,
                                             InstModCallbacks callbacks) {
    if (!shouldDestroyPartialApplyCapturedArg(arg, paramInfo,
                                              builder.getFunction()))
      return;
  
    emitDestroyOperation(builder, loc, arg, callbacks);
  }
  
  void swift::deallocPartialApplyCapturedArg(SILBuilder &builder, SILLocation loc,
                                             SILValue arg,
                                             SILParameterInfo paramInfo) {
    if (!paramInfo.isIndirectInGuaranteed())
      return;
  
    builder.createDeallocStack(loc, arg);
  }
  
  static bool
  deadMarkDependenceUser(SILInstruction *inst,
                         SmallVectorImpl<SILInstruction *> &deleteInsts) {
    if (!isa<MarkDependenceInst>(inst))
      return false;
    deleteInsts.push_back(inst);
    for (auto *use : cast<SingleValueInstruction>(inst)->getUses()) {
      if (!deadMarkDependenceUser(use->getUser(), deleteInsts))
        return false;
    }
    return true;
  }
  
  void swift::getConsumedPartialApplyArgs(PartialApplyInst *pai,
                                          SmallVectorImpl<Operand *> &argOperands,
                                          bool includeTrivialAddrArgs) {
    ApplySite applySite(pai);
    SILFunctionConventions calleeConv = applySite.getSubstCalleeConv();
    unsigned firstCalleeArgIdx = applySite.getCalleeArgIndexOfFirstAppliedArg();
    auto argList = pai->getArgumentOperands();
    SILFunction *F = pai->getFunction();
  
    for (unsigned i : indices(argList)) {
      auto argConv = calleeConv.getSILArgumentConvention(firstCalleeArgIdx + i);
      if (argConv.isInoutConvention())
        continue;
  
      Operand &argOp = argList[i];
      SILType ty = argOp.get()->getType();
      if (!ty.isTrivial(*F) || (includeTrivialAddrArgs && ty.isAddress()))
        argOperands.push_back(&argOp);
    }
  }
  
  bool swift::collectDestroys(SingleValueInstruction *inst,
                              SmallVectorImpl<SILInstruction *> &destroys) {
    bool isDead = true;
    for (Operand *use : inst->getUses()) {
      SILInstruction *user = use->getUser();
      if (useHasTransitiveOwnership(user)) {
        if (!collectDestroys(cast<SingleValueInstruction>(user), destroys))
          isDead = false;
        destroys.push_back(user);
      } else if (useDoesNotKeepValueAlive(user)) {
        destroys.push_back(user);
      } else {
        isDead = false;
      }
    }
    return isDead;
  }
  
  /// Move the original arguments of the partial_apply into newly created
  /// temporaries to extend the lifetime of the arguments until the partial_apply
  /// is finally destroyed.
  ///
  /// TODO: figure out why this is needed at all. Probably because of some
  ///       weirdness of the old retain/release ARC model. Most likely this will
  ///       not be needed anymore with OSSA.
  static bool keepArgsOfPartialApplyAlive(PartialApplyInst *pai,
                                          ArrayRef<SILInstruction *> paiUsers,
                                          SILBuilderContext &builderCtxt,
                                          InstModCallbacks callbacks) {
    SmallVector<Operand *, 8> argsToHandle;
    getConsumedPartialApplyArgs(pai, argsToHandle,
                                /*includeTrivialAddrArgs*/ false);
    if (argsToHandle.empty())
      return true;
  
    // Compute the set of endpoints, which will be used to insert destroys of
    // temporaries. This may fail if the frontier is located on a critical edge
    // which we may not split.
    ValueLifetimeAnalysis vla(pai, paiUsers);
  
    ValueLifetimeAnalysis::Frontier partialApplyFrontier;
    if (!vla.computeFrontier(partialApplyFrontier,
                             ValueLifetimeAnalysis::DontModifyCFG)) {
      return false;
    }
  
    for (Operand *argOp : argsToHandle) {
      SILValue arg = argOp->get();
  
      SILValue tmp = arg;
      if (arg->getType().isAddress()) {
        // Move the value to a stack-allocated temporary.
        SILBuilderWithScope builder(pai, builderCtxt);
        tmp = builder.createAllocStack(pai->getLoc(), arg->getType());
        builder.createCopyAddr(pai->getLoc(), arg, tmp, IsTake_t::IsTake,
                               IsInitialization_t::IsInitialization);
      }
  
      // Delay the destroy of the value (either as SSA value or in the stack-
      // allocated temporary) at the end of the partial_apply's lifetime.
      endLifetimeAtFrontier(tmp, partialApplyFrontier, builderCtxt, callbacks);
    }
    return true;
  }
  
  bool swift::tryDeleteDeadClosure(SingleValueInstruction *closure,
                                   InstModCallbacks callbacks,
                                   bool needKeepArgsAlive) {
    auto *pa = dyn_cast<PartialApplyInst>(closure);
  
    // We currently only handle locally identified values that do not escape. We
    // also assume that the partial apply does not capture any addresses.
    if (!pa && !isa<ThinToThickFunctionInst>(closure))
      return false;
  
    // A stack allocated partial apply does not have any release users. Delete it
    // if the only users are the dealloc_stack and mark_dependence instructions.
    if (pa && pa->isOnStack()) {
      SmallVector<SILInstruction *, 8> deleteInsts;
      for (auto *use : pa->getUses()) {
        if (isa<DeallocStackInst>(use->getUser())
            || isa<DebugValueInst>(use->getUser()))
          deleteInsts.push_back(use->getUser());
        else if (!deadMarkDependenceUser(use->getUser(), deleteInsts))
          return false;
      }
      for (auto *inst : reverse(deleteInsts))
        callbacks.deleteInst(inst);
      callbacks.deleteInst(pa);
  
      // Note: the lifetime of the captured arguments is managed outside of the
      // trivial closure value i.e: there will already be releases for the
      // captured arguments. Releasing captured arguments is not necessary.
      return true;
    }
  
    // Collect all destroys of the closure (transitively including destorys of
    // copies) and check if those are the only uses of the closure.
    SmallVector<SILInstruction *, 16> closureDestroys;
    if (!collectDestroys(closure, closureDestroys))
      return false;
  
    // If we have a partial_apply, release each captured argument at each one of
    // the final release locations of the partial apply.
    if (auto *pai = dyn_cast<PartialApplyInst>(closure)) {
      assert(!pa->isOnStack() &&
             "partial_apply [stack] should have been handled before");
      SILBuilderContext builderCtxt(pai->getModule());
      if (needKeepArgsAlive) {
        if (!keepArgsOfPartialApplyAlive(pai, closureDestroys, builderCtxt,
                                         callbacks))
          return false;
      } else {
        // A preceeding partial_apply -> apply conversion (done in
        // tryOptimizeApplyOfPartialApply) already ensured that the arguments are
        // kept alive until the end of the partial_apply's lifetime.
        SmallVector<Operand *, 8> argsToHandle;
        getConsumedPartialApplyArgs(pai, argsToHandle,
                                    /*includeTrivialAddrArgs*/ false);
  
        // We can just destroy the arguments at the point of the partial_apply
        // (remember: partial_apply consumes all arguments).
        for (Operand *argOp : argsToHandle) {
          SILValue arg = argOp->get();
          SILBuilderWithScope builder(pai, builderCtxt);
          emitDestroyOperation(builder, pai->getLoc(), arg, callbacks);
        }
      }
    }
  
    // Delete all copy and destroy instructions in order so that leaf uses are
    // deleted first.
    for (SILInstruction *user : closureDestroys) {
      assert(
          (useDoesNotKeepValueAlive(user) || useHasTransitiveOwnership(user)) &&
          "We expect only ARC operations without "
          "results or a cast from escape to noescape without users");
      callbacks.deleteInst(user);
    }
  
    callbacks.deleteInst(closure);
    return true;
  }
  
  bool swift::simplifyUsers(SingleValueInstruction *inst) {
    bool changed = false;
    InstModCallbacks callbacks;
  
    for (auto ui = inst->use_begin(), ue = inst->use_end(); ui != ue;) {
      SILInstruction *user = ui->getUser();
      ++ui;
  
      auto svi = dyn_cast<SingleValueInstruction>(user);
      if (!svi)
        continue;
  
      callbacks.resetHadCallbackInvocation();
      simplifyAndReplaceAllSimplifiedUsesAndErase(svi, callbacks);
      changed |= callbacks.hadCallbackInvocation();
    }
  
    return changed;
  }
  
  /// True if a type can be expanded without a significant increase to code size.
  bool swift::shouldExpand(SILModule &module, SILType ty) {
    // FIXME: Expansion
    auto expansion = TypeExpansionContext::minimal();
  
    if (module.Types.getTypeLowering(ty, expansion).isAddressOnly()) {
      return false;
    }
    if (EnableExpandAll) {
      return true;
    }
  
    unsigned numFields = module.Types.countNumberOfFields(ty, expansion);
    return (numFields <= 6);
  }
  
  /// Some support functions for the global-opt and let-properties-opts
  
  // Encapsulate the state used for recursive analysis of a static
  // initializer. Discover all the instruction in a use-def graph and return them
  // in topological order.
  //
  // TODO: We should have a DFS utility for this sort of thing so it isn't
  // recursive.
  class StaticInitializerAnalysis {
    SmallVectorImpl<SILInstruction *> &postOrderInstructions;
    llvm::SmallDenseSet<SILValue, 8> visited;
    int recursionLevel = 0;
  
  public:
    StaticInitializerAnalysis(
        SmallVectorImpl<SILInstruction *> &postOrderInstructions)
        : postOrderInstructions(postOrderInstructions) {}
  
    // Perform a recursive DFS on on the use-def graph rooted at `V`. Insert
    // values in the `visited` set in preorder. Insert values in
    // `postOrderInstructions` in postorder so that the instructions are
    // topologically def-use ordered (in execution order).
    bool analyze(SILValue rootValue) {
      return recursivelyAnalyzeOperand(rootValue);
    }
  
  protected:
    bool recursivelyAnalyzeOperand(SILValue v) {
      if (!visited.insert(v).second)
        return true;
  
      if (++recursionLevel > 50)
        return false;
  
      // TODO: For multi-result instructions, we could simply insert all result
      // values in the visited set here.
      auto *inst = dyn_cast<SingleValueInstruction>(v);
      if (!inst)
        return false;
  
      if (!recursivelyAnalyzeInstruction(inst))
        return false;
  
      postOrderInstructions.push_back(inst);
      --recursionLevel;
      return true;
    }
  
    bool recursivelyAnalyzeInstruction(SILInstruction *inst) {
      if (auto *si = dyn_cast<StructInst>(inst)) {
        // If it is not a struct which is a simple type, bail.
        if (!si->getType().isTrivial(*si->getFunction()))
          return false;
  
        return llvm::all_of(si->getAllOperands(), [&](Operand &operand) -> bool {
          return recursivelyAnalyzeOperand(operand.get());
        });
      }
      if (auto *ti = dyn_cast<TupleInst>(inst)) {
        // If it is not a tuple which is a simple type, bail.
        if (!ti->getType().isTrivial(*ti->getFunction()))
          return false;
  
        return llvm::all_of(ti->getAllOperands(), [&](Operand &operand) -> bool {
          return recursivelyAnalyzeOperand(operand.get());
        });
      }
      if (auto *bi = dyn_cast<BuiltinInst>(inst)) {
        switch (bi->getBuiltinInfo().ID) {
        case BuiltinValueKind::FPTrunc:
          if (auto *li = dyn_cast<LiteralInst>(bi->getArguments()[0])) {
            return recursivelyAnalyzeOperand(li);
          }
          return false;
        default:
          return false;
        }
      }
      return isa<IntegerLiteralInst>(inst) || isa<FloatLiteralInst>(inst)
             || isa<StringLiteralInst>(inst);
    }
  };
  
  /// Check if the value of v is computed by means of a simple initialization.
  /// Populate `forwardInstructions` with references to all the instructions
  /// that participate in the use-def graph required to compute `V`. The
  /// instructions will be in def-use topological order.
  bool swift::analyzeStaticInitializer(
      SILValue v, SmallVectorImpl<SILInstruction *> &forwardInstructions) {
    return StaticInitializerAnalysis(forwardInstructions).analyze(v);
  }
  
  /// FIXME: This must be kept in sync with replaceLoadSequence()
  /// below. What a horrible design.
  bool swift::canReplaceLoadSequence(SILInstruction *inst) {
    if (auto *cai = dyn_cast<CopyAddrInst>(inst))
      return true;
  
    if (auto *li = dyn_cast<LoadInst>(inst))
      return true;
  
    if (auto *seai = dyn_cast<StructElementAddrInst>(inst)) {
      for (auto seaiUse : seai->getUses()) {
        if (!canReplaceLoadSequence(seaiUse->getUser()))
          return false;
      }
      return true;
    }
  
    if (auto *teai = dyn_cast<TupleElementAddrInst>(inst)) {
      for (auto teaiUse : teai->getUses()) {
        if (!canReplaceLoadSequence(teaiUse->getUser()))
          return false;
      }
      return true;
    }
  
    if (auto *ba = dyn_cast<BeginAccessInst>(inst)) {
      for (auto use : ba->getUses()) {
        if (!canReplaceLoadSequence(use->getUser()))
          return false;
      }
      return true;
    }
  
    // Incidental uses of an address are meaningless with regard to the loaded
    // value.
    if (isIncidentalUse(inst) || isa<BeginUnpairedAccessInst>(inst))
      return true;
  
    return false;
  }
  
  /// Replace load sequence which may contain
  /// a chain of struct_element_addr followed by a load.
  /// The sequence is traversed inside out, i.e.
  /// starting with the innermost struct_element_addr
  /// Move into utils.
  ///
  /// FIXME: this utility does not make sense as an API. How can the caller
  /// guarantee that the only uses of `I` are struct_element_addr and
  /// tuple_element_addr?
  void swift::replaceLoadSequence(SILInstruction *inst, SILValue value) {
    if (auto *cai = dyn_cast<CopyAddrInst>(inst)) {
      SILBuilder builder(cai);
      builder.createStore(cai->getLoc(), value, cai->getDest(),
                          StoreOwnershipQualifier::Unqualified);
      return;
    }
  
    if (auto *li = dyn_cast<LoadInst>(inst)) {
      li->replaceAllUsesWith(value);
      return;
    }
  
    if (auto *seai = dyn_cast<StructElementAddrInst>(inst)) {
      SILBuilder builder(seai);
      auto *sei =
          builder.createStructExtract(seai->getLoc(), value, seai->getField());
      for (auto seaiUse : seai->getUses()) {
        replaceLoadSequence(seaiUse->getUser(), sei);
      }
      return;
    }
  
    if (auto *teai = dyn_cast<TupleElementAddrInst>(inst)) {
      SILBuilder builder(teai);
      auto *tei =
          builder.createTupleExtract(teai->getLoc(), value, teai->getFieldIndex());
      for (auto teaiUse : teai->getUses()) {
        replaceLoadSequence(teaiUse->getUser(), tei);
      }
      return;
    }
  
    if (auto *ba = dyn_cast<BeginAccessInst>(inst)) {
      for (auto use : ba->getUses()) {
        replaceLoadSequence(use->getUser(), value);
      }
      return;
    }
  
    // Incidental uses of an addres are meaningless with regard to the loaded
    // value.
    if (isIncidentalUse(inst) || isa<BeginUnpairedAccessInst>(inst))
      return;
  
    llvm_unreachable("Unknown instruction sequence for reading from a global");
  }
  
  /// Are the callees that could be called through Decl statically
  /// knowable based on the Decl and the compilation mode?
  bool swift::calleesAreStaticallyKnowable(SILModule &module, SILDeclRef decl) {
    if (decl.isForeign)
      return false;
    return calleesAreStaticallyKnowable(module, decl.getDecl());
  }
  
  /// Are the callees that could be called through Decl statically
  /// knowable based on the Decl and the compilation mode?
  bool swift::calleesAreStaticallyKnowable(SILModule &module, ValueDecl *vd) {
    assert(isa<AbstractFunctionDecl>(vd) || isa<EnumElementDecl>(vd));
  
    // Only handle members defined within the SILModule's associated context.
    if (!cast<DeclContext>(vd)->isChildContextOf(module.getAssociatedContext()))
      return false;
  
    if (vd->isDynamic()) {
      return false;
    }
  
    if (!vd->hasAccess())
      return false;
  
    // Only consider 'private' members, unless we are in whole-module compilation.
    switch (vd->getEffectiveAccess()) {
    case AccessLevel::Open:
      return false;
    case AccessLevel::Public:
      if (isa<ConstructorDecl>(vd)) {
        // Constructors are special: a derived class in another module can
        // "override" a constructor if its class is "open", although the
        // constructor itself is not open.
        auto *nd = vd->getDeclContext()->getSelfNominalTypeDecl();
        if (nd->getEffectiveAccess() == AccessLevel::Open)
          return false;
      }
      LLVM_FALLTHROUGH;
    case AccessLevel::Internal:
      return module.isWholeModule();
    case AccessLevel::FilePrivate:
    case AccessLevel::Private:
      return true;
    }
  
    llvm_unreachable("Unhandled access level in switch.");
  }
  
  Optional<FindLocalApplySitesResult>
  swift::findLocalApplySites(FunctionRefBaseInst *fri) {
    SmallVector<Operand *, 32> worklist(fri->use_begin(), fri->use_end());
  
    Optional<FindLocalApplySitesResult> f;
    f.emplace();
  
    // Optimistically state that we have no escapes before our def-use dataflow.
    f->escapes = false;
  
    while (!worklist.empty()) {
      auto *op = worklist.pop_back_val();
      auto *user = op->getUser();
  
      // If we have a full apply site as our user.
      if (auto apply = FullApplySite::isa(user)) {
        if (apply.getCallee() == op->get()) {
          f->fullApplySites.push_back(apply);
          continue;
        }
      }
  
      // If we have a partial apply as a user, start tracking it, but also look at
      // its users.
      if (auto *pai = dyn_cast<PartialApplyInst>(user)) {
        if (pai->getCallee() == op->get()) {
          // Track the partial apply that we saw so we can potentially eliminate
          // dead closure arguments.
          f->partialApplySites.push_back(pai);
          // Look to see if we can find a full application of this partial apply
          // as well.
          llvm::copy(pai->getUses(), std::back_inserter(worklist));
          continue;
        }
      }
  
      // Otherwise, see if we have any function casts to look through...
      switch (user->getKind()) {
      case SILInstructionKind::ThinToThickFunctionInst:
      case SILInstructionKind::ConvertFunctionInst:
      case SILInstructionKind::ConvertEscapeToNoEscapeInst:
        llvm::copy(cast<SingleValueInstruction>(user)->getUses(),
                   std::back_inserter(worklist));
        continue;
  
      // A partial_apply [stack] marks its captured arguments with
      // mark_dependence.
      case SILInstructionKind::MarkDependenceInst:
        llvm::copy(cast<SingleValueInstruction>(user)->getUses(),
                   std::back_inserter(worklist));
        continue;
  
      // Look through any reference count instructions since these are not
      // escapes:
      case SILInstructionKind::CopyValueInst:
        llvm::copy(cast<CopyValueInst>(user)->getUses(),
                   std::back_inserter(worklist));
        continue;
      case SILInstructionKind::StrongRetainInst:
      case SILInstructionKind::StrongReleaseInst:
      case SILInstructionKind::RetainValueInst:
      case SILInstructionKind::ReleaseValueInst:
      case SILInstructionKind::DestroyValueInst:
      // A partial_apply [stack] is deallocated with a dealloc_stack.
      case SILInstructionKind::DeallocStackInst:
        continue;
      default:
        break;
      }
  
      // But everything else is considered an escape.
      f->escapes = true;
    }
  
    // If we did escape and didn't find any apply sites, then we have no
    // information for our users that is interesting.
    if (f->escapes && f->partialApplySites.empty() && f->fullApplySites.empty())
      return None;
    return f;
  }
  
  /// Insert destroys of captured arguments of partial_apply [stack].
  void swift::insertDestroyOfCapturedArguments(
      PartialApplyInst *pai, SILBuilder &builder,
      llvm::function_ref<bool(SILValue)> shouldInsertDestroy) {
    assert(pai->isOnStack());
  
    ApplySite site(pai);
    SILFunctionConventions calleeConv(site.getSubstCalleeType(),
                                      pai->getModule());
    auto loc = RegularLocation::getAutoGeneratedLocation();
    for (auto &arg : pai->getArgumentOperands()) {
      if (!shouldInsertDestroy(arg.get()))
        continue;
      unsigned calleeArgumentIndex = site.getCalleeArgIndex(arg);
      assert(calleeArgumentIndex >= calleeConv.getSILArgIndexOfFirstParam());
      auto paramInfo = calleeConv.getParamInfoForSILArg(calleeArgumentIndex);
      releasePartialApplyCapturedArg(builder, loc, arg.get(), paramInfo);
    }
  }
  
  void swift::insertDeallocOfCapturedArguments(
      PartialApplyInst *pai, SILBuilder &builder) {
    assert(pai->isOnStack());
  
    ApplySite site(pai);
    SILFunctionConventions calleeConv(site.getSubstCalleeType(),
                                      pai->getModule());
    auto loc = RegularLocation::getAutoGeneratedLocation();
    for (auto &arg : pai->getArgumentOperands()) {
      unsigned calleeArgumentIndex = site.getCalleeArgIndex(arg);
      assert(calleeArgumentIndex >= calleeConv.getSILArgIndexOfFirstParam());
      auto paramInfo = calleeConv.getParamInfoForSILArg(calleeArgumentIndex);
      deallocPartialApplyCapturedArg(builder, loc, arg.get(), paramInfo);
    }
  }
  
  AbstractFunctionDecl *swift::getBaseMethod(AbstractFunctionDecl *FD) {
    while (FD->getOverriddenDecl()) {
      FD = FD->getOverriddenDecl();
    }
    return FD;
  }
  
  FullApplySite
  swift::cloneFullApplySiteReplacingCallee(FullApplySite applySite,
                                           SILValue newCallee,
                                           SILBuilderContext &builderCtx) {
    SmallVector<SILValue, 16> arguments;
    llvm::copy(applySite.getArguments(), std::back_inserter(arguments));
  
    SILBuilderWithScope builder(applySite.getInstruction(), builderCtx);
  
    switch (applySite.getKind()) {
    case FullApplySiteKind::TryApplyInst: {
      auto *tai = cast<TryApplyInst>(applySite.getInstruction());
      return builder.createTryApply(tai->getLoc(), newCallee,
                                    tai->getSubstitutionMap(), arguments,
                                    tai->getNormalBB(), tai->getErrorBB(),
                                    tai->getApplyOptions());
    }
    case FullApplySiteKind::ApplyInst: {
      auto *ai = cast<ApplyInst>(applySite);
      auto fTy = newCallee->getType().getAs<SILFunctionType>();
  
      auto options = ai->getApplyOptions();
      // The optimizer can generate a thin_to_thick_function from a throwing thin
      // to a non-throwing thick function (in case it can prove that the function
      // is not throwing).
      // Therefore we have to check if the new callee (= the argument of the
      // thin_to_thick_function) is a throwing function and set the not-throwing
      // flag in this case.
      if (fTy->hasErrorResult())
        options |= ApplyFlags::DoesNotThrow;
      return builder.createApply(applySite.getLoc(), newCallee,
                                 applySite.getSubstitutionMap(), arguments,
                                 options);
    }
    case FullApplySiteKind::BeginApplyInst: {
      llvm_unreachable("begin_apply support not implemented?!");
    }
    }
    llvm_unreachable("Unhandled case?!");
  }
  
  SILBasicBlock::iterator
  swift::replaceAllUsesAndErase(SingleValueInstruction *svi, SILValue newValue,
                                InstModCallbacks &callbacks) {
    assert(svi != newValue && "Cannot RAUW a value with itself");
    SILBasicBlock::iterator nextii = std::next(svi->getIterator());
  
    // Only SingleValueInstructions are currently simplified.
    while (!svi->use_empty()) {
      Operand *use = *svi->use_begin();
      SILInstruction *user = use->getUser();
      // Erase the end of scope marker.
      if (isEndOfScopeMarker(user)) {
        if (&*nextii == user)
          ++nextii;
        callbacks.deleteInst(user);
        continue;
      }
      callbacks.setUseValue(use, newValue);
    }
  
    callbacks.deleteInst(svi);
  
    return nextii;
  }
  
  /// Given that we are going to replace use's underlying value, if the use is a
  /// lifetime ending use, insert an end scope scope use for the underlying value
  /// before we RAUW.
  static void cleanupUseOldValueBeforeRAUW(Operand *use, SILBuilder &builder,
                                           SILLocation loc,
                                           InstModCallbacks &callbacks) {
    if (!use->isLifetimeEnding()) {
      return;
    }
  
    switch (use->get().getOwnershipKind()) {
    case OwnershipKind::Any:
      llvm_unreachable("Invalid ownership for value");
    case OwnershipKind::Owned: {
      auto *dvi = builder.createDestroyValue(loc, use->get());
      callbacks.createdNewInst(dvi);
      return;
    }
    case OwnershipKind::Guaranteed: {
      // Should only happen once we model destructures as true reborrows.
      auto *ebi = builder.createEndBorrow(loc, use->get());
      callbacks.createdNewInst(ebi);
      return;
    }
    case OwnershipKind::None:
      return;
    case OwnershipKind::Unowned:
      llvm_unreachable("Unowned object can never be consumed?!");
    }
    llvm_unreachable("Covered switch isn't covered");
  }
  
  SILBasicBlock::iterator swift::replaceSingleUse(Operand *use, SILValue newValue,
                                                  InstModCallbacks &callbacks) {
    auto oldValue = use->get();
    assert(oldValue != newValue && "Cannot RAUW a value with itself");
  
    auto *user = use->getUser();
    auto nextII = std::next(user->getIterator());
  
    // If we have an end of scope marker, just return next. We are done.
    if (isEndOfScopeMarker(user)) {
      return nextII;
    }
  
    // Otherwise, first insert clean up our use's value if we need to and then set
    // use to have a new value.
    SILBuilderWithScope builder(user);
    cleanupUseOldValueBeforeRAUW(use, builder, user->getLoc(), callbacks);
    callbacks.setUseValue(use, newValue);
  
    return nextII;
  }
  
  SILValue swift::makeCopiedValueAvailable(SILValue value, SILBasicBlock *inBlock) {
    if (!value->getFunction()->hasOwnership())
      return value;
  
    if (value.getOwnershipKind() == OwnershipKind::None)
      return value;
  
    auto insertPt = getInsertAfterPoint(value).getValue();
    SILBuilderWithScope builder(insertPt);
    auto *copy = builder.createCopyValue(
        RegularLocation::getAutoGeneratedLocation(), value);
  
    return makeValueAvailable(copy, inBlock);
  }
  
  SILValue swift::makeValueAvailable(SILValue value, SILBasicBlock *inBlock) {
    if (!value->getFunction()->hasOwnership())
      return value;
  
    if (value.getOwnershipKind() == OwnershipKind::None)
      return value;
  
    assert(value.getOwnershipKind() == OwnershipKind::Owned);
  
    SmallVector<SILBasicBlock *, 4> userBBs;
    for (auto use : value->getUses()) {
      userBBs.push_back(use->getParentBlock());
    }
    userBBs.push_back(inBlock);
  
    // Use \p jointPostDomComputer to:
    // 1. Create a control equivalent copy at \p inBlock if needed
    // 2. Insert destroy_value at leaking blocks
    SILValue controlEqCopy;
    findJointPostDominatingSet(
        value->getParentBlock(), userBBs,
        [&](SILBasicBlock *loopBlock) {
          assert(loopBlock == inBlock);
          auto front = loopBlock->begin();
          SILBuilderWithScope newBuilder(front);
          controlEqCopy = newBuilder.createCopyValue(
              RegularLocation::getAutoGeneratedLocation(), value);
        },
        [&](SILBasicBlock *postDomBlock) {
          // Insert a destroy_value in the leaking block
          auto front = postDomBlock->begin();
          SILBuilderWithScope newBuilder(front);
          newBuilder.createDestroyValue(
              RegularLocation::getAutoGeneratedLocation(), value);
        });
  
    return controlEqCopy ? controlEqCopy : value;
  }
  
  bool swift::tryEliminateOnlyOwnershipUsedForwardingInst(
      SingleValueInstruction *forwardingInst, InstModCallbacks &callbacks) {
    if (!OwnershipForwardingMixin::isa(forwardingInst) ||
        isa<AllArgOwnershipForwardingSingleValueInst>(forwardingInst))
      return false;
  
    SmallVector<Operand *, 32> worklist(getNonDebugUses(forwardingInst));
    while (!worklist.empty()) {
      auto *use = worklist.pop_back_val();
      auto *user = use->getUser();
  
      if (isa<EndBorrowInst>(user) || isa<DestroyValueInst>(user) ||
          isa<RefCountingInst>(user))
        continue;
  
      if (isa<CopyValueInst>(user) || isa<BeginBorrowInst>(user)) {
        for (auto result : user->getResults())
          for (auto *resultUse : getNonDebugUses(result))
            worklist.push_back(resultUse);
        continue;
      }
  
      return false;
    }
  
    // Now that we know we can perform our transform, set all uses of
    // forwardingInst to be used of its operand and then delete \p forwardingInst.
    auto newValue = forwardingInst->getOperand(0);
    while (!forwardingInst->use_empty()) {
      auto *use = *(forwardingInst->use_begin());
      use->set(newValue);
    }
  
    callbacks.deleteInst(forwardingInst);
    return true;
  }
  
  // The consuming use blocks are assumed either not to inside a loop relative to
  // \p value or they must have their own copies.
  void swift::endLifetimeAtLeakingBlocks(SILValue value,
                                         ArrayRef<SILBasicBlock *> uses) {
    if (!value->getFunction()->hasOwnership())
      return;
  
    if (value.getOwnershipKind() != OwnershipKind::Owned)
      return;
  
    findJointPostDominatingSet(
        value->getParentBlock(), uses, [&](SILBasicBlock *loopBlock) {},
        [&](SILBasicBlock *postDomBlock) {
          // Insert a destroy_value in the leaking block
          auto front = postDomBlock->begin();
          SILBuilderWithScope newBuilder(front);
          newBuilder.createDestroyValue(
              RegularLocation::getAutoGeneratedLocation(), value);
        });
  }
  
  void swift::salvageDebugInfo(SILInstruction *I) {
    if (!I)
      return;
  
    if (auto *SI = dyn_cast<StoreInst>(I)) {
      if (SILValue DestVal = SI->getDest())
        // TODO: Generalize this into "get the attached debug info
        // on `DestVal`".
        if (auto *ASI = dyn_cast_or_null<AllocStackInst>(
                DestVal.getDefiningInstruction())) {
          if (auto VarInfo = ASI->getVarInfo())
            SILBuilder(SI, ASI->getDebugScope())
                .createDebugValue(SI->getLoc(), SI->getSrc(), *VarInfo);
        }
    }
  
    // If a `struct` SIL instruction is "unwrapped" and removed,
    // for instance, in favor of using its enclosed value directly,
    // we need to make sure any of its related `debug_value` instruction
    // is preserved.
    if (auto *STI = dyn_cast<StructInst>(I)) {
      auto STVal = STI->getResult(0);
      llvm::ArrayRef<VarDecl *> FieldDecls =
        STI->getStructDecl()->getStoredProperties();
      for (Operand *U : getDebugUses(STVal)) {
        auto *DbgInst = cast<DebugValueInst>(U->getUser());
        auto VarInfo = DbgInst->getVarInfo();
        if (!VarInfo)
          continue;
        if (VarInfo->DIExpr.hasFragment())
          // Since we can't merge two different op_fragment
          // now, we're simply bailing out if there is an
          // existing op_fragment in DIExpresison.
          // TODO: Try to merge two op_fragment expressions here.
          continue;
        for (VarDecl *FD : FieldDecls) {
          SILDebugVariable NewVarInfo = *VarInfo;
          auto FieldVal = STI->getFieldValue(FD);
          // Build the corresponding fragment DIExpression
          auto FragDIExpr = SILDebugInfoExpression::createFragment(FD);
          NewVarInfo.DIExpr.append(FragDIExpr);
  
          if (!NewVarInfo.Type)
            NewVarInfo.Type = STI->getType();
  
          // Create a new debug_value
          SILBuilder(DbgInst, DbgInst->getDebugScope())
            .createDebugValue(DbgInst->getLoc(), FieldVal, NewVarInfo);
        }
      }
    }
  
    if (auto *IA = dyn_cast<IndexAddrInst>(I)) {
      if (IA->getBase() && IA->getIndex())
        // Only handle cases where offset is constant.
        if (const auto *LiteralInst =
              dyn_cast<IntegerLiteralInst>(IA->getIndex())) {
          SILValue Base = IA->getBase();
          SILValue ResultAddr = IA->getResult(0);
          APInt OffsetVal = LiteralInst->getValue();
          const SILDIExprElement ExprElements[3] = {
            SILDIExprElement::createOperator(OffsetVal.isNegative() ?
              SILDIExprOperator::ConstSInt : SILDIExprOperator::ConstUInt),
            SILDIExprElement::createConstInt(OffsetVal.getLimitedValue()),
            SILDIExprElement::createOperator(SILDIExprOperator::Plus)
          };
          for (Operand *U : getDebugUses(ResultAddr)) {
            auto *DbgInst = cast<DebugValueInst>(U->getUser());
            auto VarInfo = DbgInst->getVarInfo();
            if (!VarInfo)
              continue;
            VarInfo->DIExpr.prependElements(ExprElements);
            // Create a new debug_value
            SILBuilder(DbgInst, DbgInst->getDebugScope())
              .createDebugValue(DbgInst->getLoc(), Base, *VarInfo);
          }
        }
    }
  }
  