include/swift/SIL/SILInstruction.h

//===--- SILInstruction.h - Instructions for SIL code -----------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file defines the high-level SILInstruction class used for SIL code.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_SIL_INSTRUCTION_H
#define SWIFT_SIL_INSTRUCTION_H

#include "swift/AST/AutoDiff.h"
#include "swift/AST/Builtins.h"
#include "swift/AST/Decl.h"
#include "swift/AST/GenericSignature.h"
#include "swift/AST/ProtocolConformanceRef.h"
#include "swift/AST/SubstitutionMap.h"
#include "swift/AST/TypeAlignments.h"
#include "swift/Basic/Compiler.h"
#include "swift/Basic/NullablePtr.h"
#include "swift/Basic/ProfileCounter.h"
#include "swift/Basic/Range.h"
#include "swift/SIL/Consumption.h"
#include "swift/SIL/SILAllocated.h"
#include "swift/SIL/SILArgumentArrayRef.h"
#include "swift/SIL/SILDeclRef.h"
#include "swift/SIL/SILFunctionConventions.h"
#include "swift/SIL/SILLocation.h"
#include "swift/SIL/SILSuccessor.h"
#include "swift/SIL/SILValue.h"
#include "swift/SIL/ValueUtils.h"
#include "swift/Strings.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/Support/TrailingObjects.h"
#include <array>

namespace swift {

class AllocationInst;
class DeclRefExpr;
class FloatLiteralExpr;
class FuncDecl;
class IntegerLiteralExpr;
class SingleValueInstruction;
class MultipleValueInstruction;
class MultipleValueInstructionResult;
class DestructureTupleInst;
class DestructureStructInst;
class NonValueInstruction;
class SILBasicBlock;
class SILBuilder;
class SILDebugLocation;
class SILDebugScope;
class SILDifferentiabilityWitness;
class SILFunction;
class SILGlobalVariable;
class SILInstructionResultArray;
class SILOpenedArchetypesState;
class SILType;
class SILArgument;
class SILPhiArgument;
class SILUndef;
class Stmt;
class StringLiteralExpr;
class ValueDecl;
class VarDecl;
class FunctionRefBaseInst;

template <typename ImplClass> class SILClonerWithScopes;

// An enum class for SILInstructions that enables exhaustive switches over
// instructions.
enum class SILInstructionKind : std::underlying_type<SILNodeKind>::type {
#define INST(ID, PARENT) \
  ID = unsigned(SILNodeKind::ID),
#define INST_RANGE(ID, FIRST, LAST) \
  First_##ID = unsigned(SILNodeKind::First_##ID), \
  Last_##ID = unsigned(SILNodeKind::Last_##ID),
#include "SILNodes.def"
};

/// Return a range which can be used to easily iterate over all
/// SILInstructionKinds.
inline IntRange<SILInstructionKind> allSILInstructionKinds() {
  return IntRange<SILInstructionKind>(
            SILInstructionKind(SILNodeKind::First_SILInstruction),
            SILInstructionKind(unsigned(SILNodeKind::Last_SILInstruction) + 1));
}

/// Map SILInstruction's mnemonic name to its SILInstructionKind.
SILInstructionKind getSILInstructionKind(StringRef InstName);

/// Map SILInstructionKind to a corresponding SILInstruction name.
StringRef getSILInstructionName(SILInstructionKind Kind);

/// A formal SIL reference to a list of values, suitable for use as the result
/// of a SILInstruction.
///
/// *NOTE* Most multiple value instructions will not have many results, so if we
/// want we can cache up to 3 bytes in the lower bits of the value.
///
/// *NOTE* Most of this defined out of line further down in the file to work
/// around forward declaration issues.
///
/// *NOTE* The reason why this does not store the size of the stored element is
/// that just from the number of elements we can infer the size of each element
/// due to the restricted problem space. Specificially:
///
/// 1. Size == 0 implies nothing is stored and thus element size is irrelevent.
/// 2. Size == 1 implies we either had a single value instruction or a multiple
/// value instruction, but no matter what instruction we had, we are going to
/// store the results at the same starting location so element size is
/// irrelevent.
/// 3. Size > 1 implies we must be storing multiple value instruction results
/// implying that the size of each stored element must be
/// sizeof(MultipleValueInstructionResult).
///
/// If we ever allow for subclasses of MultipleValueInstructionResult of
/// different sizes, we will need to store a stride into
/// SILInstructionResultArray. We always assume all results are the same
/// subclass of MultipleValueInstructionResult.
class SILInstructionResultArray {
  friend class MultipleValueInstruction;

  /// Byte pointer to our data. nullptr for empty arrays.
  const uint8_t *Pointer;

  /// The number of stored elements.
  unsigned Size;

public:
  SILInstructionResultArray() : Pointer(nullptr), Size(0) {}
  SILInstructionResultArray(const SingleValueInstruction *SVI);
  SILInstructionResultArray(ArrayRef<MultipleValueInstructionResult> results);

  template <class Result>
  SILInstructionResultArray(ArrayRef<Result> results);

  SILInstructionResultArray(const SILInstructionResultArray &Other) = default;
  SILInstructionResultArray &
  operator=(const SILInstructionResultArray &Other) = default;
  SILInstructionResultArray(SILInstructionResultArray &&Other) = default;
  SILInstructionResultArray &
  operator=(SILInstructionResultArray &&Other) = default;

  SILValue operator[](size_t Index) const;

  bool empty() const { return Size == 0; }

  size_t size() const { return Size; }

  class iterator;

  friend bool operator==(iterator, iterator);
  friend bool operator!=(iterator, iterator);

  iterator begin() const;
  iterator end() const;

  using reverse_iterator = std::reverse_iterator<iterator>;
  reverse_iterator rbegin() const;
  reverse_iterator rend() const;

  using range = iterator_range<iterator>;
  range getValues() const;
  using reverse_range = iterator_range<reverse_iterator>;
  reverse_range getReversedValues() const;

  using type_range = iterator_range<
    llvm::mapped_iterator<iterator, SILType(*)(SILValue), SILType>>;
  type_range getTypes() const;

  bool operator==(const SILInstructionResultArray &rhs);
  bool operator!=(const SILInstructionResultArray &other) {
    return !(*this == other);
  }

  /// Returns true if both this and \p rhs have the same result types.
  ///
  /// *NOTE* This does not imply that the actual return SILValues are the
  /// same. Just that the types are the same.
  bool hasSameTypes(const SILInstructionResultArray &rhs);

private:
  /// Return the first element of the array. Asserts if the array is empty.
  ///
  /// Please do not use this outside of this class. It is only meant to speedup
  /// MultipleValueInstruction::getIndexOfResult(SILValue).
  const ValueBase *front() const;

  /// Return the last element of the array. Asserts if the array is empty.
  ///
  /// Please do not use this outside of this class. It is only meant to speedup
  /// MultipleValueInstruction::getIndexOfResult(SILValue).
  const ValueBase *back() const;
};

class SILInstructionResultArray::iterator {
  /// Our "parent" array.
  ///
  /// This is actually a value type reference into a SILInstruction of some
  /// sort. So we can just have our own copy. This also allows us to not worry
  /// about our underlying array having too short of a lifetime.
  SILInstructionResultArray Parent;

  /// The index into the parent array.
  unsigned Index;

public:
  using difference_type = int;
  using value_type = SILValue;
  using pointer = void;
  using reference = SILValue;
  using iterator_category = std::bidirectional_iterator_tag;

  iterator() = default;
  iterator(const SILInstructionResultArray &Parent, unsigned Index = 0)
      : Parent(Parent), Index(Index) {}

  SILValue operator*() const { return Parent[Index]; }
  SILValue operator->() const { return operator*(); }

  iterator &operator++() {
    ++Index;
    return *this;
  }

  iterator operator++(int) {
    iterator copy = *this;
    ++Index;
    return copy;
  }

  iterator &operator--() {
    --Index;
    return *this;
  }

  iterator operator--(int) {
    iterator copy = *this;
    --Index;
    return copy;
  }

  friend bool operator==(iterator lhs, iterator rhs) {
    assert(lhs.Parent.Pointer == rhs.Parent.Pointer);
    return lhs.Index == rhs.Index;
  }

  friend bool operator!=(iterator lhs, iterator rhs) { return !(lhs == rhs); }
};

inline SILInstructionResultArray::iterator
SILInstructionResultArray::begin() const {
  return iterator(*this, 0);
}

inline SILInstructionResultArray::iterator
SILInstructionResultArray::end() const {
  return iterator(*this, size());
}

inline SILInstructionResultArray::reverse_iterator
SILInstructionResultArray::rbegin() const {
  return llvm::make_reverse_iterator(end());
}

inline SILInstructionResultArray::reverse_iterator
SILInstructionResultArray::rend() const {
  return llvm::make_reverse_iterator(begin());
}

inline SILInstructionResultArray::range
SILInstructionResultArray::getValues() const {
  return {begin(), end()};
}

inline SILInstructionResultArray::reverse_range
SILInstructionResultArray::getReversedValues() const {
  return {rbegin(), rend()};
}

/// This is the root class for all instructions that can be used as the
/// contents of a Swift SILBasicBlock.
///
/// Most instructions are defined in terms of two basic kinds of
/// structure: a list of operand values upon which the instruction depends
/// and a list of result values upon which other instructions can depend.
///
/// The operands can be divided into two sets:
///   - the formal operands of the instruction, which reflect its
///     direct value dependencies, and
///   - the type-dependent operands, which reflect dependencies that are
///     not captured by the formal operands; currently, these dependencies
///     only arise due to certain instructions (e.g. open_existential_addr)
///     that bind new archetypes in the local context.
class SILInstruction
    : public SILNode, public llvm::ilist_node<SILInstruction> {
  friend llvm::ilist_traits<SILInstruction>;
  friend llvm::ilist_traits<SILBasicBlock>;
  friend SILBasicBlock;

  /// A backreference to the containing basic block.  This is maintained by
  /// ilist_traits<SILInstruction>.
  SILBasicBlock *ParentBB;

  /// This instruction's containing lexical scope and source location
  /// used for debug info and diagnostics.
  SILDebugLocation Location;

  SILInstruction() = delete;
  void operator=(const SILInstruction &) = delete;
  void operator delete(void *Ptr, size_t) = delete;

  /// Check any special state of instructions that are not represented in the
  /// instructions operands/type.
  bool hasIdenticalState(const SILInstruction *RHS) const;

  /// Update this instruction's SILDebugScope. This function should
  /// never be called directly. Use SILBuilder, SILBuilderWithScope or
  /// SILClonerWithScope instead.
  void setDebugScope(const SILDebugScope *DS);

  /// Total number of created and deleted SILInstructions.
  /// It is used only for collecting the compiler statistics.
  static int NumCreatedInstructions;
  static int NumDeletedInstructions;

  // Helper functions used by the ArrayRefViews below.
  static SILValue projectValueBaseAsSILValue(const ValueBase &value) {
    return &value;
  }
  static SILType projectValueBaseType(const ValueBase &value) {
    return value.getType();
  }

  /// An internal method which retrieves the result values of the
  /// instruction as an array of ValueBase objects.
  SILInstructionResultArray getResultsImpl() const;

protected:
  SILInstruction(SILInstructionKind kind, SILDebugLocation DebugLoc)
      : SILNode(SILNodeKind(kind), SILNodeStorageLocation::Instruction,
                IsRepresentative::Yes),
        ParentBB(nullptr), Location(DebugLoc) {
    NumCreatedInstructions++;
  }

  ~SILInstruction() {
    NumDeletedInstructions++;
  }

public:
  /// Instructions should be allocated using a dedicated instruction allocation
  /// function from the ContextTy.
  template <typename ContextTy>
  void *operator new(size_t Bytes, const ContextTy &C,
                     size_t Alignment = alignof(ValueBase)) {
    return C.allocateInst(Bytes, Alignment);
  }

  enum class MemoryBehavior {
    None,
    /// The instruction may read memory.
    MayRead,
    /// The instruction may write to memory.
    /// This includes destroying or taking from memory (e.g. destroy_addr,
    /// copy_addr [take], load [take]).
    /// Although, physically, destroying or taking does not modify the memory,
    /// it is important to model it is a write. Optimizations must not assume
    /// that the value stored in memory is still available for loading after
    /// the memory is destroyed or taken.
    MayWrite,
    /// The instruction may read or write memory.
    MayReadWrite,
    /// The instruction may have side effects not captured
    ///        solely by its users. Specifically, it can return,
    ///        release memory, or store. Note, alloc is not considered
    ///        to have side effects because its result/users represent
    ///        its effect.
    MayHaveSideEffects,
  };

  /// Enumeration representing whether the execution of an instruction can
  /// result in memory being released.
  enum class ReleasingBehavior {
    DoesNotRelease,
    MayRelease,
  };

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  SILInstructionKind getKind() const {
    return SILInstructionKind(SILNode::getKind());
  }

  const SILBasicBlock *getParent() const { return ParentBB; }
  SILBasicBlock *getParent() { return ParentBB; }

  SILFunction *getFunction();
  const SILFunction *getFunction() const;

  /// Is this instruction part of a static initializer of a SILGlobalVariable?
  bool isStaticInitializerInst() const { return getFunction() == nullptr; }

  SILModule &getModule() const;

  /// This instruction's source location (AST node).
  SILLocation getLoc() const;
  const SILDebugScope *getDebugScope() const;
  SILDebugLocation getDebugLocation() const { return Location; }

  /// Sets the debug location.
  /// Note: Usually it should not be needed to use this function as the location
  /// is already set in when creating an instruction.
  void setDebugLocation(SILDebugLocation Loc) { Location = Loc; }

  /// This method unlinks 'self' from the containing basic block and deletes it.
  void eraseFromParent();

  /// Unlink this instruction from its current basic block and insert the
  /// instruction such that it is the first instruction of \p Block.
  void moveFront(SILBasicBlock *Block);

  /// Unlink this instruction from its current basic block and insert it into
  /// the basic block that Later lives in, right before Later.
  void moveBefore(SILInstruction *Later);

  /// Unlink this instruction from its current basic block and insert it into
  /// the basic block that Earlier lives in, right after Earlier.
  void moveAfter(SILInstruction *Earlier);

  /// Drops all uses that belong to this instruction.
  void dropAllReferences();

  /// Replace all uses of all results of this instruction with undef.
  void replaceAllUsesOfAllResultsWithUndef();

  /// Replace all uses of all results of this instruction
  /// with the parwise-corresponding results of the given instruction.
  void replaceAllUsesPairwiseWith(SILInstruction *other);

  /// Replace all uses of all results of this instruction with the
  /// parwise-corresponding results of the passed in array.
  void
  replaceAllUsesPairwiseWith(const llvm::SmallVectorImpl<SILValue> &NewValues);

  /// Are there uses of any of the results of this instruction?
  bool hasUsesOfAnyResult() const {
    for (auto result : getResults()) {
      if (!result->use_empty())
        return true;
    }
    return false;
  }

  /// Return the array of operands for this instruction.
  ArrayRef<Operand> getAllOperands() const;

  /// Return the array of type dependent operands for this instruction.
  ///
  /// Type dependent operands are hidden operands, i.e. not part of the SIL
  /// syntax (although they are printed as "type-defs" in comments).
  /// Their purpose is to establish a def-use relationship between
  ///   -) an instruction/argument which defines a type, e.g. open_existential
  /// and
  ///   -) this instruction, which uses the type, but doesn't use the defining
  ///      instruction as value-operand, e.g. a type in the substitution list.
  ///
  /// Currently there are two kinds of type dependent operands:
  ///
  /// 1. for opened archetypes:
  ///     %o = open_existential_addr %0 : $*P to $*@opened("UUID") P
  ///     %w = witness_method $@opened("UUID") P, ... // type-defs: %o
  ///
  /// 2. for the dynamic self argument:
  ///     sil @foo : $@convention(method) (@thick X.Type) {
  ///     bb0(%0 : $@thick X.Type):
  ///       %a = apply %f<@dynamic_self X>() ... // type-defs: %0
  ///
  /// The type dependent operands are just there to let optimizations know that
  /// there is a dependency between the instruction/argument which defines the
  /// type and the instruction which uses the type.
  ArrayRef<Operand> getTypeDependentOperands() const;

  /// Return the array of mutable operands for this instruction.
  MutableArrayRef<Operand> getAllOperands();

  /// Return the array of mutable type dependent operands for this instruction.
  MutableArrayRef<Operand> getTypeDependentOperands();

  unsigned getNumOperands() const { return getAllOperands().size(); }

  unsigned getNumTypeDependentOperands() const {
    return getTypeDependentOperands().size();
  }

  bool isTypeDependentOperand(unsigned i) const {
    return i >= getNumOperands() - getNumTypeDependentOperands();
  }

  bool isTypeDependentOperand(const Operand &Op) const {
    assert(Op.getUser() == this &&
           "Operand does not belong to a SILInstruction");
    return isTypeDependentOperand(Op.getOperandNumber());
  }
      
  /// Returns true if evaluation of this instruction may cause suspension of an
  /// async task.
  bool maySuspend() const;

private:
  /// Predicate used to filter OperandValueRange.
  struct OperandToValue;
  /// Predicate used to filter TransformedOperandValueRange.
  struct OperandToTransformedValue;

public:
  using OperandValueRange =
      OptionalTransformRange<ArrayRef<Operand>, OperandToValue>;
  using TransformedOperandValueRange =
      OptionalTransformRange<ArrayRef<Operand>, OperandToTransformedValue>;

  OperandValueRange
  getOperandValues(bool skipTypeDependentOperands = false) const;
  TransformedOperandValueRange
  getOperandValues(std::function<SILValue(SILValue)> transformFn,
                   bool skipTypeDependentOperands) const;

  SILValue getOperand(unsigned Num) const {
    return getAllOperands()[Num].get();
  }
  void setOperand(unsigned Num, SILValue V) { getAllOperands()[Num].set(V); }
  void swapOperands(unsigned Num1, unsigned Num2) {
    getAllOperands()[Num1].swap(getAllOperands()[Num2]);
  }

private:
  /// Predicate used to filter OperandTypeRange.
  struct OperandToType;

public:
  using OperandTypeRange =
      OptionalTransformRange<ArrayRef<Operand>, OperandToType>;
  // NOTE: We always skip type dependent operands.
  OperandTypeRange getOperandTypes() const;

  /// Return the list of results produced by this instruction.
  bool hasResults() const { return !getResults().empty(); }
  SILInstructionResultArray getResults() const { return getResultsImpl(); }
  unsigned getNumResults() const { return getResults().size(); }

  SILValue getResult(unsigned index) const { return getResults()[index]; }

  /// Return the types of the results produced by this instruction.
  SILInstructionResultArray::type_range getResultTypes() const {
    return getResultsImpl().getTypes();
  }

  MemoryBehavior getMemoryBehavior() const;
  ReleasingBehavior getReleasingBehavior() const;

  /// Returns true if the instruction may release any object.
  bool mayRelease() const;

  /// Returns true if the instruction may release or may read the reference
  /// count of any object.
  bool mayReleaseOrReadRefCount() const;

  /// Can this instruction abort the program in some manner?
  bool mayTrap() const;

  /// Returns true if the given instruction is completely identical to RHS.
  bool isIdenticalTo(const SILInstruction *RHS) const {
    return isIdenticalTo(RHS,
                         [](const SILValue &Op1, const SILValue &Op2) -> bool {
                           return Op1 == Op2; });
  }
  
  /// Returns true if the given instruction is completely identical to RHS,
  /// using \p opEqual to compare operands.
  ///
  template <typename OpCmp>
  bool isIdenticalTo(const SILInstruction *RHS, OpCmp &&opEqual) const {
    // Quick check if both instructions have the same kind, number of operands,
    // and types. This should filter out most cases.
    if (getKind() != RHS->getKind() ||
        getNumOperands() != RHS->getNumOperands()) {
      return false;
    }

    if (!getResults().hasSameTypes(RHS->getResults()))
      return false;

    // Check operands.
    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
      if (!opEqual(getOperand(i), RHS->getOperand(i)))
        return false;

    // Check any special state of instructions that are not represented in the
    // instructions operands/type.
    return hasIdenticalState(RHS);
  }

  /// Returns true if the instruction may have side effects.
  ///
  /// Instructions that store into memory or change retain counts as well as
  /// calls and deallocation instructions are considered to have side effects
  /// that are not visible by merely examining their uses.
  bool mayHaveSideEffects() const;

  /// Returns true if the instruction may write to memory.
  bool mayWriteToMemory() const {
    MemoryBehavior B = getMemoryBehavior();
    return B == MemoryBehavior::MayWrite ||
      B == MemoryBehavior::MayReadWrite ||
      B == MemoryBehavior::MayHaveSideEffects;
  }

  /// Returns true if the instruction may read from memory.
  bool mayReadFromMemory() const {
    MemoryBehavior B = getMemoryBehavior();
    return B == MemoryBehavior::MayRead ||
      B == MemoryBehavior::MayReadWrite ||
      B == MemoryBehavior::MayHaveSideEffects;
  }

  /// Returns true if the instruction may read from or write to memory.
  bool mayReadOrWriteMemory() const {
    return getMemoryBehavior() != MemoryBehavior::None;
  }

  /// Return true if the instruction is "pure" in the sense that it may execute
  /// multiple times without affecting behavior. This implies that it can be
  /// trivially cloned at multiple use sites without preserving path
  /// equivalence.
  bool isPure() const {
    return !mayReadOrWriteMemory() && !mayTrap() && !isa<AllocationInst>(this)
           && !isa<TermInst>(this);
  }

  /// Returns true if the result of this instruction is a pointer to stack
  /// allocated memory. In this case there must be an adjacent deallocating
  /// instruction.
  bool isAllocatingStack() const;

  /// Returns true if this is the deallocation of a stack allocating instruction.
  /// The first operand must be the allocating instruction.
  bool isDeallocatingStack() const;

  /// Create a new copy of this instruction, which retains all of the operands
  /// and other information of this one.  If an insertion point is specified,
  /// then the new instruction is inserted before the specified point, otherwise
  /// the new instruction is returned without a parent.
  SILInstruction *clone(SILInstruction *InsertPt = nullptr);

  /// Invoke an Instruction's destructor. This dispatches to the appropriate
  /// leaf class destructor for the type of the instruction. This does not
  /// deallocate the instruction.
  static void destroy(SILInstruction *I);

  /// Returns true if the instruction can be duplicated without any special
  /// additional handling. It is important to know this information when
  /// you perform such optimizations like e.g. jump-threading.
  bool isTriviallyDuplicatable() const;

  /// Returns true if the instruction is only relevant for debug
  /// informations and has no other impact on program semantics.
  bool isDebugInstruction() const {
    return getKind() == SILInstructionKind::DebugValueInst ||
           getKind() == SILInstructionKind::DebugValueAddrInst;
  }

  /// Returns true if the instruction is a meta instruction which is
  /// relevant for debug information and does not get lowered to a real
  /// instruction.
  bool isMetaInstruction() const;

  /// Verify that all operands of this instruction have compatible ownership
  /// with this instruction.
  void verifyOperandOwnership() const;

  /// Get the number of created SILInstructions.
  static int getNumCreatedInstructions() {
    return NumCreatedInstructions;
  }

  /// Get the number of deleted SILInstructions.
  static int getNumDeletedInstructions() {
    return NumDeletedInstructions;
  }

  /// Pretty-print the value.
  void dump() const;
  void print(raw_ostream &OS) const;

  /// Pretty-print the value in context, preceded by its operands (if the
  /// value represents the result of an instruction) and followed by its
  /// users.
  void dumpInContext() const;
  void printInContext(raw_ostream &OS) const;

  static bool classof(const SILNode *N) {
    return N->getKind() >= SILNodeKind::First_SILInstruction &&
           N->getKind() <= SILNodeKind::Last_SILInstruction;
  }
  static bool classof(const SILInstruction *I) { return true; }

  /// This is supportable but usually suggests a logic mistake.
  static bool classof(const ValueBase *) = delete;
};

struct SILInstruction::OperandToValue {
  const SILInstruction &i;
  bool skipTypeDependentOps;

  OperandToValue(const SILInstruction &i, bool skipTypeDependentOps)
      : i(i), skipTypeDependentOps(skipTypeDependentOps) {}

  Optional<SILValue> operator()(const Operand &use) const {
    if (skipTypeDependentOps && i.isTypeDependentOperand(use))
      return None;
    return use.get();
  }
};

struct SILInstruction::OperandToTransformedValue {
  const SILInstruction &i;
  std::function<SILValue(SILValue)> transformFn;
  bool skipTypeDependentOps;

  OperandToTransformedValue(const SILInstruction &i,
                            std::function<SILValue(SILValue)> transformFn,
                            bool skipTypeDependentOps)
      : i(i), transformFn(transformFn),
        skipTypeDependentOps(skipTypeDependentOps) {}

  Optional<SILValue> operator()(const Operand &use) const {
    if (skipTypeDependentOps && i.isTypeDependentOperand(use))
      return None;
    return transformFn(use.get());
  }
};

inline auto
SILInstruction::getOperandValues(bool skipTypeDependentOperands) const
    -> OperandValueRange {
  return OperandValueRange(getAllOperands(),
                           OperandToValue(*this, skipTypeDependentOperands));
}

inline auto
SILInstruction::getOperandValues(std::function<SILValue(SILValue)> transformFn,
                                 bool skipTypeDependentOperands) const
    -> TransformedOperandValueRange {
  return TransformedOperandValueRange(
      getAllOperands(),
      OperandToTransformedValue(*this, transformFn, skipTypeDependentOperands));
}

struct SILInstruction::OperandToType {
  const SILInstruction &i;

  OperandToType(const SILInstruction &i) : i(i) {}

  Optional<SILType> operator()(const Operand &use) const {
    if (i.isTypeDependentOperand(use))
      return None;
    return use.get()->getType();
  }
};

inline auto SILInstruction::getOperandTypes() const -> OperandTypeRange {
  return OperandTypeRange(getAllOperands(), OperandToType(*this));
}

inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                     const SILInstruction &I) {
  I.print(OS);
  return OS;
}

/// Returns the combined behavior of \p B1 and \p B2.
inline SILInstruction::MemoryBehavior
combineMemoryBehavior(SILInstruction::MemoryBehavior B1,
                  SILInstruction::MemoryBehavior B2) {
  // Basically the combined behavior is the maximum of both operands.
  auto Result = std::max(B1, B2);

  // With one exception: MayRead, MayWrite -> MayReadWrite.
  if (Result == SILInstruction::MemoryBehavior::MayWrite &&
        (B1 == SILInstruction::MemoryBehavior::MayRead ||
         B2 == SILInstruction::MemoryBehavior::MayRead))
    return SILInstruction::MemoryBehavior::MayReadWrite;
  return Result;
}

/// Pretty-print the MemoryBehavior.
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              SILInstruction::MemoryBehavior B);
/// Pretty-print the ReleasingBehavior.
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              SILInstruction::ReleasingBehavior B);

/// An instruction which always produces a single value.
///
/// Because this instruction is both a SILInstruction and a ValueBase,
/// both of which inherit from SILNode, it introduces the need for
/// some care when working with SILNodes.  See the comment on SILNode.
class SingleValueInstruction : public SILInstruction, public ValueBase {
  static bool isSingleValueInstKind(SILNodeKind kind) {
    return kind >= SILNodeKind::First_SingleValueInstruction &&
           kind <= SILNodeKind::Last_SingleValueInstruction;
  }

  friend class SILInstruction;
  SILInstructionResultArray getResultsImpl() const {
    return SILInstructionResultArray(this);
  }
public:
  SingleValueInstruction(SILInstructionKind kind, SILDebugLocation loc,
                         SILType type)
      : SILInstruction(kind, loc),
        ValueBase(ValueKind(kind), type, IsRepresentative::No) {}

  using SILInstruction::operator new;
  using SILInstruction::dumpInContext;
  using SILInstruction::print;
  using SILInstruction::printInContext;

  // Redeclare because lldb currently doesn't know about using-declarations
  void dump() const;
  SILFunction *getFunction() { return SILInstruction::getFunction(); }
  const SILFunction *getFunction() const {
    return SILInstruction::getFunction();
  }
  SILModule &getModule() const { return SILInstruction::getModule(); }
  SILInstructionKind getKind() const { return SILInstruction::getKind(); }

  void operator delete(void *Ptr, size_t) = delete;

  ValueKind getValueKind() const {
    return ValueBase::getKind();
  }

  SingleValueInstruction *clone(SILInstruction *insertPt = nullptr) {
    return cast<SingleValueInstruction>(SILInstruction::clone(insertPt));
  }

  /// Override this to reflect the more efficient access pattern.
  SILInstructionResultArray getResults() const { return getResultsImpl(); }

  static bool classof(const SILNode *node) {
    return isSingleValueInstKind(node->getKind());
  }
};

// Resolve ambiguities.
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                     const SingleValueInstruction &I) {
  I.print(OS);
  return OS;
}

inline SingleValueInstruction *SILNode::castToSingleValueInstruction() {
  assert(isa<SingleValueInstruction>(this));

  // We do reference static_casts to convince the host compiler to do
  // null-unchecked conversions.

  // If we're in the value slot, cast through ValueBase.
  if (getStorageLoc() == SILNodeStorageLocation::Value) {
    return &static_cast<SingleValueInstruction&>(
                                         static_cast<ValueBase&>(*this));

  // Otherwise, cast through SILInstruction.
  } else {
    return &static_cast<SingleValueInstruction&>(
                                         static_cast<SILInstruction&>(*this));
  }
}

#define DEFINE_ABSTRACT_SINGLE_VALUE_INST_BOILERPLATE(ID)                      \
  static bool classof(const SILNode *node) {                                   \
    return node->getKind() >= SILNodeKind::First_##ID &&                       \
           node->getKind() <= SILNodeKind::Last_##ID;                          \
  }                                                                            \
  static bool classof(const SingleValueInstruction *inst) {                    \
    return inst->getKind() >= SILInstructionKind::First_##ID &&                \
           inst->getKind() <= SILInstructionKind::Last_##ID;                   \
  }

/// Abstract base class used for isa checks on instructions to determine if they
/// forward ownership and to verify that the set of ownership instructions and
/// the ownership utilities stay in sync via assertions.
///
/// NOTE: We assume that the constructor for the instruction subclass that
/// initializes the kind field on our object is run before our constructor runs.
class OwnershipForwardingInst {
  ValueOwnershipKind ownershipKind;

protected:
  OwnershipForwardingInst(SILInstructionKind kind,
                          ValueOwnershipKind ownershipKind)
      : ownershipKind(ownershipKind) {
    assert(classof(kind) && "Invalid subclass?!");
  }

public:
  ValueOwnershipKind getOwnershipKind() const { return ownershipKind; }

  void setOwnershipKind(ValueOwnershipKind newKind) { ownershipKind = newKind; }

  static bool classof(const SILNode *node) {
    if (auto *i = dyn_cast<SILInstruction>(node))
      return classof(i);
    return false;
  }

  // Defined inline below due to forward declaration issues.
  static bool classof(const SILInstruction *inst);

  /// Define inline below due to forward declaration issues.
  static bool classof(SILInstructionKind kind);
};

/// A single value inst that forwards a static ownership from one (or all) of
/// its operands.
///
/// The ownership kind is set on construction and afterwards must be changed
/// explicitly using setOwnershipKind().
class FirstArgOwnershipForwardingSingleValueInst
    : public SingleValueInstruction,
      public OwnershipForwardingInst {
protected:
  FirstArgOwnershipForwardingSingleValueInst(SILInstructionKind kind,
                                             SILDebugLocation debugLoc,
                                             SILType ty,
                                             ValueOwnershipKind ownershipKind)
      : SingleValueInstruction(kind, debugLoc, ty),
        OwnershipForwardingInst(kind, ownershipKind) {
    assert(classof(kind) && "classof missing new subclass?!");
  }

public:
  static bool classof(const SILNode *node) {
    if (auto *i = dyn_cast<SILInstruction>(node))
      return classof(i);
    return false;
  }

  static bool classof(SILInstructionKind kind);

  static bool classof(const SILInstruction *inst) {
    return classof(inst->getKind());
  }
};

/// An ownership forwarding single value that has a preferred operand of owned
/// but if its inputs are all none can have OwnershipKind::None as a result. We
/// assume that we always forward from operand 0.
class OwnedFirstArgForwardingSingleValueInst
    : public FirstArgOwnershipForwardingSingleValueInst {
protected:
  OwnedFirstArgForwardingSingleValueInst(SILInstructionKind kind,
                                         SILDebugLocation debugLoc, SILType ty,
                                         ValueOwnershipKind resultOwnershipKind)
      : FirstArgOwnershipForwardingSingleValueInst(kind, debugLoc, ty,
                                                   resultOwnershipKind) {
    assert(resultOwnershipKind.isCompatibleWith(OwnershipKind::Owned));
    assert(classof(kind) && "classof missing new subclass?!");
  }

public:
  ValueOwnershipKind getPreferredOwnership() const {
    return OwnershipKind::Owned;
  }

  static bool classof(const SILNode *node) {
    if (auto *i = dyn_cast<SILInstruction>(node))
      return classof(i);
    return false;
  }

  static bool classof(SILInstructionKind kind) {
    switch (kind) {
    case SILInstructionKind::MarkUninitializedInst:
      return true;
    default:
      return false;
    }
  }

  static bool classof(const SILInstruction *inst) {
    return classof(inst->getKind());
  }
};

/// An instruction that forwards guaranteed or none ownership. Assumed to always
/// forward from Operand(0) -> Result(0).
class GuaranteedFirstArgForwardingSingleValueInst
    : public FirstArgOwnershipForwardingSingleValueInst {
protected:
  GuaranteedFirstArgForwardingSingleValueInst(
      SILInstructionKind kind, SILDebugLocation debugLoc, SILType ty,
      ValueOwnershipKind resultOwnershipKind)
      : FirstArgOwnershipForwardingSingleValueInst(kind, debugLoc, ty,
                                                   resultOwnershipKind) {
    assert(resultOwnershipKind.isCompatibleWith(OwnershipKind::Guaranteed));
    assert(classof(kind) && "classof missing new subclass?!");
  }

public:
  ValueOwnershipKind getPreferredOwnership() const {
    return OwnershipKind::Guaranteed;
  }

  static bool classof(const SILNode *node) {
    if (auto *i = dyn_cast<SILInstruction>(node))
      return classof(i);
    return false;
  }

  static bool classof(SILInstructionKind kind) {
    switch (kind) {
    case SILInstructionKind::TupleExtractInst:
    case SILInstructionKind::StructExtractInst:
    case SILInstructionKind::DifferentiableFunctionExtractInst:
    case SILInstructionKind::LinearFunctionExtractInst:
    case SILInstructionKind::OpenExistentialValueInst:
    case SILInstructionKind::OpenExistentialBoxValueInst:
      return true;
    default:
      return false;
    }
  }

  static bool classof(const SILInstruction *inst) {
    return classof(inst->getKind());
  }
};

inline bool
FirstArgOwnershipForwardingSingleValueInst::classof(SILInstructionKind kind) {
  if (OwnedFirstArgForwardingSingleValueInst::classof(kind))
    return true;
  if (GuaranteedFirstArgForwardingSingleValueInst::classof(kind))
    return true;

  switch (kind) {
  case SILInstructionKind::ObjectInst:
  case SILInstructionKind::EnumInst:
  case SILInstructionKind::UncheckedEnumDataInst:
  case SILInstructionKind::SelectValueInst:
  case SILInstructionKind::OpenExistentialRefInst:
  case SILInstructionKind::InitExistentialRefInst:
  case SILInstructionKind::MarkDependenceInst:
    return true;
  default:
    return false;
  }
}

class AllArgOwnershipForwardingSingleValueInst
    : public SingleValueInstruction,
      public OwnershipForwardingInst {
protected:
  AllArgOwnershipForwardingSingleValueInst(SILInstructionKind kind,
                                           SILDebugLocation debugLoc,
                                           SILType ty,
                                           ValueOwnershipKind ownershipKind)
      : SingleValueInstruction(kind, debugLoc, ty),
        OwnershipForwardingInst(kind, ownershipKind) {
    assert(classof(kind) && "classof missing new subclass?!");
  }

public:
  static bool classof(const SILNode *node) {
    if (auto *i = dyn_cast<SILInstruction>(node))
      return classof(i);
    return false;
  }

  static bool classof(SILInstructionKind kind) {
    switch (kind) {
    case SILInstructionKind::StructInst:
    case SILInstructionKind::TupleInst:
    case SILInstructionKind::LinearFunctionInst:
    case SILInstructionKind::DifferentiableFunctionInst:
      return true;
    default:
      return false;
    }
  }

  static bool classof(const SILInstruction *inst) {
    return classof(inst->getKind());
  }
};

/// A value base result of a multiple value instruction.
///
/// *NOTE* We want this to be a pure abstract class that does not add /any/ size
/// to subclasses.
class MultipleValueInstructionResult : public ValueBase {
public:
  /// Create a new multiple value instruction result.
  ///
  /// \arg subclassDeltaOffset This is the delta offset in our parent object's
  /// layout in between the end of the MultipleValueInstruction object and the
  /// end of the specific subclass object.
  ///
  /// *NOTE* subclassDeltaOffset must be use only 5 bits. This gives us to
  /// support subclasses up to 32 bytes in size. We can scavange up to 6 more
  /// bits from ValueBase if this is not large enough.
  MultipleValueInstructionResult(ValueKind valueKind, unsigned index,
                                 SILType type,
                                 ValueOwnershipKind ownershipKind);

  /// Return the parent instruction of this result.
  MultipleValueInstruction *getParent();

  const MultipleValueInstruction *getParent() const {
    return const_cast<MultipleValueInstructionResult *>(this)->getParent();
  }

  unsigned getIndex() const {
    return Bits.MultipleValueInstructionResult.Index;
  }

  /// Get the ownership kind assigned to this result by its parent.
  ///
  /// This is stored in the bottom 3 bits of ValueBase's subclass data.
  ValueOwnershipKind getOwnershipKind() const;

  /// Set the ownership kind assigned to this result.
  ///
  /// This is stored in SILNode in the subclass data.
  void setOwnershipKind(ValueOwnershipKind Kind);

  static bool classof(const SILInstruction *) = delete;
  static bool classof(const SILUndef *) = delete;
  static bool classof(const SILArgument *) = delete;
  static bool classof(const MultipleValueInstructionResult *) { return true; }
  static bool classof(const SILNode *node) {
    // This is an abstract class without anything implementing it right now, so
    // just return false. This will be fixed in a subsequent commit.
    SILNodeKind kind = node->getKind();
    return kind >= SILNodeKind::First_MultipleValueInstructionResult &&
           kind <= SILNodeKind::Last_MultipleValueInstructionResult;
  }

protected:
  /// Set the index of this result.
  void setIndex(unsigned NewIndex);
};

template <class Result>
SILInstructionResultArray::SILInstructionResultArray(ArrayRef<Result> results)
  : SILInstructionResultArray(
        ArrayRef<MultipleValueInstructionResult>(results.data(),
                                                 results.size())) {
  static_assert(sizeof(Result) == sizeof(MultipleValueInstructionResult),
                "MultipleValueInstructionResult subclass has wrong size");
}

/// An instruction that may produce an arbitrary number of values.
class MultipleValueInstruction : public SILInstruction {
  friend class SILInstruction;
  friend class SILInstructionResultArray;

protected:
  MultipleValueInstruction(SILInstructionKind kind, SILDebugLocation loc)
      : SILInstruction(kind, loc) {}

public:
  void operator delete(void *Ptr, size_t) = delete;

  MultipleValueInstruction *clone(SILInstruction *insertPt = nullptr) {
    return cast<MultipleValueInstruction>(SILInstruction::clone(insertPt));
  }

  SILValue getResult(unsigned Index) const { return getResults()[Index]; }

  /// Return the index of \p Target if it is a result in the given
  /// MultipleValueInstructionResult. Otherwise, returns None.
  Optional<unsigned> getIndexOfResult(SILValue Target) const;

  unsigned getNumResults() const { return getResults().size(); }

  static bool classof(const SILNode *node) {
    SILNodeKind kind = node->getKind();
    return kind >= SILNodeKind::First_MultipleValueInstruction &&
           kind <= SILNodeKind::Last_MultipleValueInstruction;
  }
};

template <typename...> class InitialTrailingObjects;
template <typename...> class FinalTrailingObjects;

/// A utility mixin class that must be used by /all/ subclasses of
/// MultipleValueInstruction to store their results.
///
/// The exact ordering of trailing types matters quite a lot because
/// it's vital that the fields used by preceding numTrailingObjects
/// implementations be initialized before this base class is (and
/// conversely that this base class be initialized before any of the
/// succeeding numTrailingObjects implementations are called).
template <typename Derived, typename DerivedResult,
          typename Init = InitialTrailingObjects<>,
          typename Final = FinalTrailingObjects<>>
class MultipleValueInstructionTrailingObjects;

template <typename Derived, typename DerivedResult,
          typename... InitialOtherTrailingTypes,
          typename... FinalOtherTrailingTypes>
class MultipleValueInstructionTrailingObjects<Derived, DerivedResult,
                      InitialTrailingObjects<InitialOtherTrailingTypes...>,
                      FinalTrailingObjects<FinalOtherTrailingTypes...>>
    : protected llvm::TrailingObjects<Derived,
                                      InitialOtherTrailingTypes...,
                                      MultipleValueInstruction *,
                                      DerivedResult,
                                      FinalOtherTrailingTypes...> {
  static_assert(std::is_final<DerivedResult>(),
                "Expected DerivedResult to be final");
  static_assert(
      std::is_base_of<MultipleValueInstructionResult, DerivedResult>::value,
      "Expected DerivedResult to be a subclass of "
      "MultipleValueInstructionResult");
  static_assert(sizeof(MultipleValueInstructionResult) == sizeof(DerivedResult),
                "Expected DerivedResult to be the same size as a "
                "MultipleValueInstructionResult");

protected:
  using TrailingObjects =
      llvm::TrailingObjects<Derived,
                            InitialOtherTrailingTypes...,
                            MultipleValueInstruction *, DerivedResult,
                            FinalOtherTrailingTypes...>;
  friend TrailingObjects;

  using TrailingObjects::totalSizeToAlloc;
  using TrailingObjects::getTrailingObjects;

  unsigned NumResults;

  size_t numTrailingObjects(typename TrailingObjects::template OverloadToken<
                            MultipleValueInstruction *>) const {
    return 1;
  }

  size_t numTrailingObjects(
      typename TrailingObjects::template OverloadToken<DerivedResult>) const {
    return NumResults;
  }

  template <typename... Args>
  MultipleValueInstructionTrailingObjects(
      Derived *Parent, ArrayRef<SILType> Types,
      ArrayRef<ValueOwnershipKind> OwnershipKinds, Args &&... OtherArgs)
      : NumResults(Types.size()) {

    // If we do not have any results, then we do not need to initialize even the
    // parent pointer since we do not have any results that will attempt to get
    // our parent pointer.
    if (!NumResults)
      return;

    auto **ParentPtr = this->TrailingObjects::template
        getTrailingObjects<MultipleValueInstruction *>();
    *ParentPtr = static_cast<MultipleValueInstruction *>(Parent);

    auto *DataPtr = this->TrailingObjects::template
        getTrailingObjects<DerivedResult>();
    for (unsigned i : range(NumResults)) {
      ::new (&DataPtr[i]) DerivedResult(i, Types[i], OwnershipKinds[i],
                                        std::forward<Args>(OtherArgs)...);
      assert(DataPtr[i].getParent() == Parent &&
             "Failed to setup parent reference correctly?!");
    }
  }

  // Destruct the Derived Results.
  ~MultipleValueInstructionTrailingObjects() {
    if (!NumResults)
      return;
    auto *DataPtr = this->TrailingObjects::template
        getTrailingObjects<DerivedResult>();
    // We call the DerivedResult destructors to ensure that:
    //
    // 1. If our derived results have any stored data that need to be cleaned
    // up, we clean them up. *NOTE* Today, no results have this property.
    // 2. In ~ValueBase, we validate via an assert that a ValueBase no longer
    // has any uses when it is being destroyed. Rather than re-implement that in
    // result, we get that for free.
    for (unsigned i : range(NumResults))
      DataPtr[i].~DerivedResult();
  }

public:
  ArrayRef<DerivedResult> getAllResultsBuffer() const {
    auto *ptr = this->TrailingObjects::template
        getTrailingObjects<DerivedResult>();
    return { ptr, NumResults };
  }

  MutableArrayRef<DerivedResult> getAllResultsBuffer() {
    auto *ptr = this->TrailingObjects::template
        getTrailingObjects<DerivedResult>();
    return { ptr, NumResults };
  }

  SILInstructionResultArray getAllResults() const {
    // Our results start at element 1 since we stash the pointer to our parent
    // MultipleValueInstruction in the 0 elt slot. This allows all
    // MultipleValueInstructionResult to find their parent
    // MultipleValueInstruction by using pointer arithmetic.
    return SILInstructionResultArray(getAllResultsBuffer());
  };
};

/// A subclass of SILInstruction which does not produce any values.
class NonValueInstruction : public SILInstruction {
public:
  NonValueInstruction(SILInstructionKind kind, SILDebugLocation loc)
    : SILInstruction(kind, loc) {}

  /// Doesn't produce any results.
  SILType getType() const = delete;
  SILInstructionResultArray getResults() const = delete;

  static bool classof(const ValueBase *value) = delete;
  static bool classof(const SILNode *N) {
    return N->getKind() >= SILNodeKind::First_NonValueInstruction &&
           N->getKind() <= SILNodeKind::Last_NonValueInstruction;
  }
  static bool classof(const NonValueInstruction *) { return true; }
};
#define DEFINE_ABSTRACT_NON_VALUE_INST_BOILERPLATE(ID)          \
  static bool classof(const ValueBase *value) = delete;         \
  static bool classof(const SILNode *node) {                    \
    return node->getKind() >= SILNodeKind::First_##ID &&        \
           node->getKind() <= SILNodeKind::Last_##ID;           \
  }

/// A helper class for defining some basic boilerplate.
template <SILInstructionKind Kind, typename InstBase,
          bool IsSingleResult =
              std::is_base_of<SingleValueInstruction, InstBase>::value>
class InstructionBase;

template <SILInstructionKind Kind, typename InstBase>
class InstructionBase<Kind, InstBase, /*HasResult*/ true> : public InstBase {
protected:
  template <typename... As>
  InstructionBase(As &&... args) : InstBase(Kind, std::forward<As>(args)...) {}

public:
  /// Override to statically return the kind.
  static constexpr SILInstructionKind getKind() {
    return Kind;
  }

  static bool classof(const SILNode *node) {
    return node->getKind() == SILNodeKind(Kind);
  }
  static bool classof(const SingleValueInstruction *I) { // resolve ambiguities
    return I->getKind() == Kind;
  }
};

template <SILInstructionKind Kind, typename InstBase>
class InstructionBase<Kind, InstBase, /*HasResult*/ false> : public InstBase {
protected:
  template <typename... As>
  InstructionBase(As &&... args) : InstBase(Kind, std::forward<As>(args)...) {}

public:
  static constexpr SILInstructionKind getKind() {
    return Kind;
  }

  /// Can never dynamically succeed.
  static bool classof(const ValueBase *value) = delete;

  static bool classof(const SILNode *node) {
    return node->getKind() == SILNodeKind(Kind);
  }
};

/// A template base class for instructions that take a single SILValue operand.
template<SILInstructionKind Kind, typename Base>
class UnaryInstructionBase : public InstructionBase<Kind, Base> {
  // Space for 1 operand.
  FixedOperandList<1> Operands;

public:
  template <typename... A>
  UnaryInstructionBase(SILDebugLocation loc, SILValue op, A &&... args)
      : InstructionBase<Kind, Base>(loc, std::forward<A>(args)...),
        Operands(this, op) {}

  SILValue getOperand() const { return Operands[0].get(); }
  void setOperand(SILValue V) { Operands[0].set(V); }

  Operand &getOperandRef() { return Operands[0]; }

  ArrayRef<Operand> getAllOperands() const { return Operands.asArray(); }
  MutableArrayRef<Operand> getAllOperands() { return Operands.asArray(); }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return {};
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return {};
  }
};

/// A template base class for instructions that a variable number of SILValue
/// operands, and has zero or one value results. The operands are tail allocated
/// after the instruction. Further trailing data can be allocated as well if
/// OtherTrailingTypes are provided.
template<SILInstructionKind Kind,
         typename Derived,
         typename Base,
         typename... OtherTrailingTypes>
class InstructionBaseWithTrailingOperands
    : public InstructionBase<Kind, Base>,
      protected llvm::TrailingObjects<Derived, Operand, OtherTrailingTypes...> {

protected:
  friend llvm::TrailingObjects<Derived, Operand, OtherTrailingTypes...>;

  using TrailingObjects =
      llvm::TrailingObjects<Derived, Operand, OtherTrailingTypes...>;

  using TrailingObjects::totalSizeToAlloc;

public:
  template <typename... Args>
  InstructionBaseWithTrailingOperands(ArrayRef<SILValue> Operands,
                                      Args &&...args)
        : InstructionBase<Kind, Base>(std::forward<Args>(args)...) {
    SILInstruction::Bits.IBWTO.NumOperands = Operands.size();
    TrailingOperandsList::InitOperandsList(getAllOperands().begin(), this,
                                           Operands);
  }

  template <typename... Args>
  InstructionBaseWithTrailingOperands(SILValue Operand0,
                                      ArrayRef<SILValue> Operands,
                                      Args &&...args)
        : InstructionBase<Kind, Base>(std::forward<Args>(args)...) {
    SILInstruction::Bits.IBWTO.NumOperands = Operands.size() + 1;
    TrailingOperandsList::InitOperandsList(getAllOperands().begin(), this,
                                           Operand0, Operands);
  }

  template <typename... Args>
  InstructionBaseWithTrailingOperands(SILValue Operand0,
                                      SILValue Operand1,
                                      ArrayRef<SILValue> Operands,
                                      Args &&...args)
        : InstructionBase<Kind, Base>(std::forward<Args>(args)...) {
    SILInstruction::Bits.IBWTO.NumOperands = Operands.size() + 2;
    TrailingOperandsList::InitOperandsList(getAllOperands().begin(), this,
                                           Operand0, Operand1, Operands);
  }

  // Destruct tail allocated objects.
  ~InstructionBaseWithTrailingOperands() {
    Operand *Operands = TrailingObjects::template getTrailingObjects<Operand>();
    auto end = SILInstruction::Bits.IBWTO.NumOperands;
    for (unsigned i = 0; i < end; ++i) {
      Operands[i].~Operand();
    }
  }

  size_t numTrailingObjects(typename TrailingObjects::template
                            OverloadToken<Operand>) const {
    return SILInstruction::Bits.IBWTO.NumOperands;
  }

  ArrayRef<Operand> getAllOperands() const {
    return {TrailingObjects::template getTrailingObjects<Operand>(),
            SILInstruction::Bits.IBWTO.NumOperands};
  }

  MutableArrayRef<Operand> getAllOperands() {
    return {TrailingObjects::template getTrailingObjects<Operand>(),
            SILInstruction::Bits.IBWTO.NumOperands};
  }
};

/// A template base class for instructions that take a single regular SILValue
/// operand, a set of type dependent operands and has no result
/// or a single value result. The operands are tail allocated after the
/// instruction. Further trailing data can be allocated as well if
/// TRAILING_TYPES are provided.
template<SILInstructionKind Kind,
         typename Derived,
         typename Base,
         typename... OtherTrailingTypes>
class UnaryInstructionWithTypeDependentOperandsBase
    : public InstructionBaseWithTrailingOperands<Kind, Derived, Base,
                                                 OtherTrailingTypes...> {
protected:
  friend InstructionBaseWithTrailingOperands<Kind, Derived, Operand,
                                             OtherTrailingTypes...>;

  using TrailingObjects =
      InstructionBaseWithTrailingOperands<Kind, Derived, Operand,
                                          OtherTrailingTypes...>;

public:
  template <typename... Args>
  UnaryInstructionWithTypeDependentOperandsBase(SILDebugLocation debugLoc,
                                       SILValue operand,
                                       ArrayRef<SILValue> typeDependentOperands,
                                       Args &&...args)
      : InstructionBaseWithTrailingOperands<Kind, Derived, Base,
                                            OtherTrailingTypes...>(
                                              operand, typeDependentOperands,
                                              debugLoc,
                                              std::forward<Args>(args)...) {}

  unsigned getNumTypeDependentOperands() const {
    return this->getAllOperands().size() - 1;
  }

  SILValue getOperand() const {
    return this->getAllOperands()[0].get();
  }
  void setOperand(SILValue V) {
    this->getAllOperands()[0].set(V);
  }

  Operand &getOperandRef() {
    return this->getAllOperands()[0];
  }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return this->getAllOperands().slice(1);
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return this->getAllOperands().slice(1);
  }
};

/// Holds common debug information about local variables and function
/// arguments that are needed by DebugValueInst, DebugValueAddrInst,
/// AllocStackInst, and AllocBoxInst.
struct SILDebugVariable {
  StringRef Name;
  unsigned ArgNo : 16;
  unsigned Constant : 1;

  SILDebugVariable() : ArgNo(0), Constant(false) {}
  SILDebugVariable(bool Constant, uint16_t ArgNo)
      : ArgNo(ArgNo), Constant(Constant) {}
  SILDebugVariable(StringRef Name, bool Constant, unsigned ArgNo)
      : Name(Name), ArgNo(ArgNo), Constant(Constant) {}
  bool operator==(const SILDebugVariable &V) {
    return ArgNo == V.ArgNo && Constant == V.Constant && Name == V.Name;
  }
};

/// A DebugVariable where storage for the strings has been
/// tail-allocated following the parent SILInstruction.
class TailAllocatedDebugVariable {
  using int_type = uint32_t;
  union {
    int_type RawValue;
    struct {
      /// Whether this is a debug variable at all.
      int_type HasValue : 1;
      /// True if this is a let-binding.
      int_type Constant : 1;
      /// When this is nonzero there is a tail-allocated string storing
      /// variable name present. This typically only happens for
      /// instructions that were created from parsing SIL assembler.
      int_type NameLength : 14;
      /// The source function argument position from left to right
      /// starting with 1 or 0 if this is a local variable.
      int_type ArgNo : 16;
    } Data;
  } Bits;
public:
  TailAllocatedDebugVariable(Optional<SILDebugVariable>, char *buf);
  TailAllocatedDebugVariable(int_type RawValue) { Bits.RawValue = RawValue; }
  int_type getRawValue() const { return Bits.RawValue; }

  unsigned getArgNo() const { return Bits.Data.ArgNo; }
  void setArgNo(unsigned N) { Bits.Data.ArgNo = N; }
  /// Returns the name of the source variable, if it is stored in the
  /// instruction.
  StringRef getName(const char *buf) const;
  bool isLet() const { return Bits.Data.Constant; }

  Optional<SILDebugVariable> get(VarDecl *VD, const char *buf) const {
    if (!Bits.Data.HasValue)
      return None;
    if (VD)
      return SILDebugVariable(VD->getName().empty() ? "" : VD->getName().str(),
                              VD->isLet(), getArgNo());
    else
      return SILDebugVariable(getName(buf), isLet(), getArgNo());
  }
};
static_assert(sizeof(TailAllocatedDebugVariable) == 4,
              "SILNode inline bitfield needs updating");

//===----------------------------------------------------------------------===//
// Allocation Instructions
//===----------------------------------------------------------------------===//

/// Abstract base class for allocation instructions, like alloc_stack, alloc_box
/// and alloc_ref, etc.
class AllocationInst : public SingleValueInstruction {
protected:
  AllocationInst(SILInstructionKind Kind, SILDebugLocation DebugLoc, SILType Ty)
      : SingleValueInstruction(Kind, DebugLoc, Ty) {}

public:
  DEFINE_ABSTRACT_SINGLE_VALUE_INST_BOILERPLATE(AllocationInst)

  /// Return the underlying variable declaration associated with this
  /// allocation, or null if this allocation inst is associated with a temporary
  /// allocation.
  VarDecl *getDecl() const;
};

class DeallocStackInst;

/// AllocStackInst - This represents the allocation of an unboxed (i.e., no
/// reference count) stack memory.  The memory is provided uninitialized.
class AllocStackInst final
    : public InstructionBase<SILInstructionKind::AllocStackInst,
                             AllocationInst>,
      private llvm::TrailingObjects<AllocStackInst, Operand, char> {
  friend TrailingObjects;
  friend SILBuilder;

  bool dynamicLifetime = false;

  AllocStackInst(SILDebugLocation Loc, SILType elementType,
                 ArrayRef<SILValue> TypeDependentOperands,
                 SILFunction &F,
                 Optional<SILDebugVariable> Var, bool hasDynamicLifetime);

  static AllocStackInst *create(SILDebugLocation Loc, SILType elementType,
                                SILFunction &F,
                                SILOpenedArchetypesState &OpenedArchetypes,
                                Optional<SILDebugVariable> Var,
                                bool hasDynamicLifetime);

  size_t numTrailingObjects(OverloadToken<Operand>) const {
    return SILInstruction::Bits.AllocStackInst.NumOperands;
  }

public:
  ~AllocStackInst() {
    Operand *Operands = getTrailingObjects<Operand>();
    size_t end = SILInstruction::Bits.AllocStackInst.NumOperands;
    for (unsigned i = 0; i < end; ++i) {
      Operands[i].~Operand();
    }
  }

  /// Set to true that this alloc_stack contains a value whose lifetime can not
  /// be ascertained from uses.
  ///
  /// As an example if an alloc_stack is known to be only conditionally
  /// initialized.
  void setDynamicLifetime() { dynamicLifetime = true; }

  /// Returns true if the alloc_stack's initialization can not be ascertained
  /// from uses directly (so should be treated conservatively).
  ///
  /// An example of an alloc_stack with dynamic lifetime is an alloc_stack that
  /// is conditionally initialized.
  bool hasDynamicLifetime() const { return dynamicLifetime; }

  /// Return the debug variable information attached to this instruction.
  Optional<SILDebugVariable> getVarInfo() const {
    auto RawValue = SILInstruction::Bits.AllocStackInst.VarInfo;
    auto VI = TailAllocatedDebugVariable(RawValue);
    return VI.get(getDecl(), getTrailingObjects<char>());
  };
  void setArgNo(unsigned N) {
    auto RawValue = SILInstruction::Bits.AllocStackInst.VarInfo;
    auto VI = TailAllocatedDebugVariable(RawValue);
    VI.setArgNo(N);
    SILInstruction::Bits.AllocStackInst.VarInfo = VI.getRawValue();
  }

  /// getElementType - Get the type of the allocated memory (as opposed to the
  /// type of the instruction itself, which will be an address type).
  SILType getElementType() const {
    return getType().getObjectType();
  }

  ArrayRef<Operand> getAllOperands() const {
    return { getTrailingObjects<Operand>(),
             static_cast<size_t>(SILInstruction::Bits.AllocStackInst.NumOperands) };
  }

  MutableArrayRef<Operand> getAllOperands() {
    return { getTrailingObjects<Operand>(),
             static_cast<size_t>(SILInstruction::Bits.AllocStackInst.NumOperands) };
  }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands();
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands();
  }

  /// Return a single dealloc_stack user or null.
  DeallocStackInst *getSingleDeallocStack() const;
};

/// The base class for AllocRefInst and AllocRefDynamicInst.
///
/// The first NumTailTypes operands are counts for the tail allocated
/// elements, the remaining operands are opened archetype operands.
class AllocRefInstBase : public AllocationInst {
protected:

  AllocRefInstBase(SILInstructionKind Kind,
                   SILDebugLocation DebugLoc,
                   SILType ObjectType,
                   bool objc, bool canBeOnStack,
                   ArrayRef<SILType> ElementTypes);

  SILType *getTypeStorage();
  const SILType *getTypeStorage() const {
    return const_cast<AllocRefInstBase*>(this)->getTypeStorage();
  }

  unsigned getNumTailTypes() const {
    return SILInstruction::Bits.AllocRefInstBase.NumTailTypes;
  }

public:
  bool canAllocOnStack() const {
    return SILInstruction::Bits.AllocRefInstBase.OnStack;
  }

  void setStackAllocatable(bool OnStack = true) {
    SILInstruction::Bits.AllocRefInstBase.OnStack = OnStack;
  }

  ArrayRef<SILType> getTailAllocatedTypes() const {
    return {getTypeStorage(), getNumTailTypes()};
  }

  MutableArrayRef<SILType> getTailAllocatedTypes() {
    return {getTypeStorage(), getNumTailTypes()};
  }
  
  ArrayRef<Operand> getTailAllocatedCounts() const {
    return getAllOperands().slice(0, getNumTailTypes());
  }

  MutableArrayRef<Operand> getTailAllocatedCounts() {
    return getAllOperands().slice(0, getNumTailTypes());
  }

  ArrayRef<Operand> getAllOperands() const;
  MutableArrayRef<Operand> getAllOperands();
  
  /// Whether to use Objective-C's allocation mechanism (+allocWithZone:).
  bool isObjC() const {
    return SILInstruction::Bits.AllocRefInstBase.ObjC;
  }
};

/// AllocRefInst - This represents the primitive allocation of an instance
/// of a reference type. Aside from the reference count, the instance is
/// returned uninitialized.
/// Optionally, the allocated instance contains space for one or more tail-
/// allocated arrays.
class AllocRefInst final
    : public InstructionBaseWithTrailingOperands<
                                               SILInstructionKind::AllocRefInst,
                                               AllocRefInst,
                                               AllocRefInstBase, SILType> {
  friend AllocRefInstBase;
  friend SILBuilder;

  AllocRefInst(SILDebugLocation DebugLoc, SILFunction &F,
               SILType ObjectType,
               bool objc, bool canBeOnStack,
               ArrayRef<SILType> ElementTypes,
               ArrayRef<SILValue> AllOperands)
      : InstructionBaseWithTrailingOperands(AllOperands, DebugLoc, ObjectType,
                        objc, canBeOnStack, ElementTypes) {
    assert(AllOperands.size() >= ElementTypes.size());
    std::uninitialized_copy(ElementTypes.begin(), ElementTypes.end(),
                            getTrailingObjects<SILType>());
  }

  static AllocRefInst *create(SILDebugLocation DebugLoc, SILFunction &F,
                              SILType ObjectType,
                              bool objc, bool canBeOnStack,
                              ArrayRef<SILType> ElementTypes,
                              ArrayRef<SILValue> ElementCountOperands,
                              SILOpenedArchetypesState &OpenedArchetypes);

public:
  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands().slice(getNumTailTypes());
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands().slice(getNumTailTypes());
  }
};

/// AllocRefDynamicInst - This represents the primitive allocation of
/// an instance of a reference type whose runtime type is provided by
/// the given metatype value. Aside from the reference count, the
/// instance is returned uninitialized.
/// Optionally, the allocated instance contains space for one or more tail-
/// allocated arrays.
class AllocRefDynamicInst final
    : public InstructionBaseWithTrailingOperands<
                                        SILInstructionKind::AllocRefDynamicInst,
                                        AllocRefDynamicInst,
                                        AllocRefInstBase, SILType> {
  friend AllocRefInstBase;
  friend SILBuilder;

  AllocRefDynamicInst(SILDebugLocation DebugLoc,
                      SILType ty,
                      bool objc,
                      ArrayRef<SILType> ElementTypes,
                      ArrayRef<SILValue> AllOperands)
      : InstructionBaseWithTrailingOperands(AllOperands, DebugLoc, ty, objc,
                                            false, ElementTypes) {
    assert(AllOperands.size() >= ElementTypes.size() + 1);
    std::uninitialized_copy(ElementTypes.begin(), ElementTypes.end(),
                            getTrailingObjects<SILType>());
  }

  static AllocRefDynamicInst *
  create(SILDebugLocation DebugLoc, SILFunction &F,
         SILValue metatypeOperand, SILType ty, bool objc,
         ArrayRef<SILType> ElementTypes,
         ArrayRef<SILValue> ElementCountOperands,
         SILOpenedArchetypesState &OpenedArchetypes);

public:
  SILValue getMetatypeOperand() const {
    return getAllOperands()[getNumTailTypes()].get();
  }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands().slice(getNumTailTypes() + 1);
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands().slice(getNumTailTypes() + 1);
  }
};

/// AllocValueBufferInst - Allocate memory in a value buffer.
class AllocValueBufferInst final
    : public UnaryInstructionWithTypeDependentOperandsBase<
                                  SILInstructionKind::AllocValueBufferInst,
                                  AllocValueBufferInst,
                                  AllocationInst> {
  friend SILBuilder;

  AllocValueBufferInst(SILDebugLocation DebugLoc, SILType valueType,
                       SILValue operand,
                       ArrayRef<SILValue> TypeDependentOperands);

  static AllocValueBufferInst *
  create(SILDebugLocation DebugLoc, SILType valueType, SILValue operand,
         SILFunction &F, SILOpenedArchetypesState &OpenedArchetypes);

public:
  SILType getValueType() const { return getType().getObjectType(); }
};

/// This represents the allocation of a heap box for a Swift value of some type.
/// The instruction returns two values.  The first return value is the object
/// pointer with Builtin.NativeObject type.  The second return value
/// is an address pointing to the contained element. The contained
/// element is uninitialized.
class AllocBoxInst final
    : public InstructionBaseWithTrailingOperands<
                                           SILInstructionKind::AllocBoxInst,
                                           AllocBoxInst, AllocationInst, char> {
  friend SILBuilder;

  TailAllocatedDebugVariable VarInfo;

  bool dynamicLifetime = false;

  AllocBoxInst(SILDebugLocation DebugLoc, CanSILBoxType BoxType,
               ArrayRef<SILValue> TypeDependentOperands, SILFunction &F,
               Optional<SILDebugVariable> Var, bool hasDynamicLifetime);

  static AllocBoxInst *create(SILDebugLocation Loc, CanSILBoxType boxType,
                              SILFunction &F,
                              SILOpenedArchetypesState &OpenedArchetypes,
                              Optional<SILDebugVariable> Var,
                              bool hasDynamicLifetime);

public:
  CanSILBoxType getBoxType() const {
    return getType().castTo<SILBoxType>();
  }

  void setDynamicLifetime() { dynamicLifetime = true; }
  bool hasDynamicLifetime() const { return dynamicLifetime; }

  // Return the type of the memory stored in the alloc_box.
  SILType getAddressType() const;

  /// Return the debug variable information attached to this instruction.
  Optional<SILDebugVariable> getVarInfo() const {
    return VarInfo.get(getDecl(), getTrailingObjects<char>());
  };

  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands();
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands();
  }
};

/// This represents the allocation of a heap box for an existential container.
/// The instruction returns two values.  The first return value is the owner
/// pointer, which has the existential type.  The second return value
/// is an address pointing to the contained element. The contained
/// value is uninitialized.
class AllocExistentialBoxInst final
    : public InstructionBaseWithTrailingOperands<
                                   SILInstructionKind::AllocExistentialBoxInst,
                                   AllocExistentialBoxInst, AllocationInst> {
  friend SILBuilder;
  CanType ConcreteType;
  ArrayRef<ProtocolConformanceRef> Conformances;

  AllocExistentialBoxInst(SILDebugLocation DebugLoc, SILType ExistentialType,
                          CanType ConcreteType,
                          ArrayRef<ProtocolConformanceRef> Conformances,
                          ArrayRef<SILValue> TypeDependentOperands,
                          SILFunction *Parent)
    : InstructionBaseWithTrailingOperands(TypeDependentOperands, DebugLoc,
                                          ExistentialType.getObjectType()),
      ConcreteType(ConcreteType), Conformances(Conformances) {}

  static AllocExistentialBoxInst *
  create(SILDebugLocation DebugLoc, SILType ExistentialType,
         CanType ConcreteType, ArrayRef<ProtocolConformanceRef> Conformances,
         SILFunction *Parent, SILOpenedArchetypesState &OpenedArchetypes);

public:
  CanType getFormalConcreteType() const { return ConcreteType; }

  SILType getExistentialType() const { return getType(); }

  ArrayRef<ProtocolConformanceRef> getConformances() const {
    return Conformances;
  }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands();
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands();
  }
};

/// GenericSpecializationInformation - provides information about a generic
/// specialization. This meta-information is created for each generic
/// specialization, which allows for tracking of dependencies between
/// specialized generic functions and can be used to detect specialization loops
/// during generic specialization.
class GenericSpecializationInformation {
  /// The caller function that triggered this specialization.
  SILFunction *Caller;
  /// The original function that was specialized.
  SILFunction *Parent;
  /// Substitutions used to produce this specialization.
  SubstitutionMap Subs;

  GenericSpecializationInformation(SILFunction *Caller, SILFunction *Parent,
                                   SubstitutionMap Subs);

public:
  static const GenericSpecializationInformation *create(SILFunction *Caller,
                                                        SILFunction *Parent,
                                                        SubstitutionMap Subs);
  static const GenericSpecializationInformation *create(SILInstruction *Inst,
                                                        SILBuilder &B);
  const SILFunction *getCaller() const { return Caller; }
  const SILFunction *getParent() const { return Parent; }
  SubstitutionMap getSubstitutions() const { return Subs; }
};

class PartialApplyInst;

// There's no good reason for the OverloadToken type to be internal
// or protected, and it makes it very difficult to write our CRTP classes
// if it is, so pull it out.  TODO: just fix LLVM.
struct TerribleOverloadTokenHack :
    llvm::trailing_objects_internal::TrailingObjectsBase {
  template <class T>
  using Hack = OverloadToken<T>;
};
template <class T>
using OverloadToken = TerribleOverloadTokenHack::Hack<T>;

/// ApplyInstBase - An abstract class for different kinds of function
/// application.
template <class Impl, class Base,
          bool IsFullApply = !std::is_same<Impl, PartialApplyInst>::value>
class ApplyInstBase;

// The partial specialization for non-full applies.  Note that the
// partial specialization for full applies inherits from this.
template <class Impl, class Base>
class ApplyInstBase<Impl, Base, false> : public Base {
  enum { Callee, NumStaticOperands };

  /// The type of the callee with our substitutions applied.
  SILType SubstCalleeType;

  /// Information about specialization and inlining of this apply.
  /// This is only != nullptr if the apply was inlined. And in this case it
  /// points to the specialization info of the inlined function.
  const GenericSpecializationInformation *SpecializationInfo;

  /// Used for apply_inst instructions: true if the called function has an
  /// error result but is not actually throwing.
  unsigned NonThrowing: 1;

  /// The number of call arguments as required by the callee.
  unsigned NumCallArguments : 31;

  /// The total number of type-dependent operands.
  unsigned NumTypeDependentOperands;

  /// The substitutions being applied to the callee.
  SubstitutionMap Substitutions;

  Impl &asImpl() { return static_cast<Impl &>(*this); }
  const Impl &asImpl() const { return static_cast<const Impl &>(*this); }

protected:
  template <class... As>
  ApplyInstBase(SILInstructionKind kind, SILDebugLocation DebugLoc, SILValue callee,
                SILType substCalleeType, SubstitutionMap subs,
                ArrayRef<SILValue> args,
                ArrayRef<SILValue> typeDependentOperands,
                const GenericSpecializationInformation *specializationInfo,
                As... baseArgs)
      : Base(kind, DebugLoc, baseArgs...), SubstCalleeType(substCalleeType),
        SpecializationInfo(specializationInfo),
        NonThrowing(false), NumCallArguments(args.size()),
        NumTypeDependentOperands(typeDependentOperands.size()),
        Substitutions(subs) {

    // Initialize the operands.
    auto allOperands = getAllOperands();
    new (&allOperands[Callee]) Operand(this, callee);
    for (size_t i : indices(args)) {
      new (&allOperands[NumStaticOperands + i]) Operand(this, args[i]);
    }
    for (size_t i : indices(typeDependentOperands)) {
      new (&allOperands[NumStaticOperands + args.size() + i])
        Operand(this, typeDependentOperands[i]);
    }
  }

  ~ApplyInstBase() {
    for (auto &operand : getAllOperands())
      operand.~Operand();
  }

  template <class, class...>
  friend class llvm::TrailingObjects;

  unsigned numTrailingObjects(OverloadToken<Operand>) const {
    return getNumAllOperands();
  }

  static size_t getNumAllOperands(ArrayRef<SILValue> args,
                                  ArrayRef<SILValue> typeDependentOperands) {
    return NumStaticOperands + args.size() + typeDependentOperands.size();
  }

  void setNonThrowing(bool isNonThrowing) { NonThrowing = isNonThrowing; }
  
  bool isNonThrowingApply() const { return NonThrowing; }
  
public:
  /// The operand number of the first argument.
  static unsigned getArgumentOperandNumber() { return NumStaticOperands; }

  Operand *getCalleeOperand() { return &getAllOperands()[Callee]; }
  const Operand *getCalleeOperand() const { return &getAllOperands()[Callee]; }
  SILValue getCallee() const { return getCalleeOperand()->get(); }

  /// Gets the origin of the callee by looking through function type conversions
  /// until we find a function_ref, partial_apply, or unrecognized value.
  ///
  /// This is defined out of line to work around incomplete definition
  /// issues. It is at the bottom of the file.
  SILValue getCalleeOrigin() const;

  /// Gets the referenced function by looking through partial apply,
  /// convert_function, and thin to thick function until we find a function_ref.
  ///
  /// This is defined out of line to work around incomplete definition
  /// issues. It is at the bottom of the file.
  SILFunction *getCalleeFunction() const;

  bool isCalleeDynamicallyReplaceable() const;

  /// Gets the referenced function if the callee is a function_ref instruction.
  /// Returns null if the callee is dynamic or a (prev_)dynamic_function_ref
  /// instruction.
  SILFunction *getReferencedFunctionOrNull() const {
    if (auto *FRI = dyn_cast<FunctionRefBaseInst>(getCallee()))
      return FRI->getReferencedFunctionOrNull();
    return nullptr;
  }

  /// Return the referenced function if the callee is a function_ref like
  /// instruction.
  ///
  /// WARNING: This not necessarily the function that will be called at runtime.
  /// If the callee is a (prev_)dynamic_function_ref the actual function called
  /// might be different because it could be dynamically replaced at runtime.
  ///
  /// If the client of this API wants to look at the content of the returned SIL
  /// function it should call getReferencedFunctionOrNull() instead.
  SILFunction *getInitiallyReferencedFunction() const {
    if (auto *FRI = dyn_cast<FunctionRefBaseInst>(getCallee()))
      return FRI->getInitiallyReferencedFunction();
    return nullptr;
  }

  /// Get the type of the callee without the applied substitutions.
  CanSILFunctionType getOrigCalleeType() const {
    return getCallee()->getType().template castTo<SILFunctionType>();
  }
  SILFunctionConventions getOrigCalleeConv() const {
    return SILFunctionConventions(getOrigCalleeType(), this->getModule());
  }

  /// Get the type of the callee with the applied substitutions.
  CanSILFunctionType getSubstCalleeType() const {
    return SubstCalleeType.castTo<SILFunctionType>();
  }
  SILType getSubstCalleeSILType() const {
    return SubstCalleeType;
  }
  
  void setSubstCalleeType(CanSILFunctionType t) {
    SubstCalleeType = SILType::getPrimitiveObjectType(t);
  }
  
  SILFunctionConventions getSubstCalleeConv() const {
    return SILFunctionConventions(getSubstCalleeType(), this->getModule());
  }

  bool isCalleeNoReturn() const {
    return getSubstCalleeSILType().isNoReturnFunction(
        this->getModule(), TypeExpansionContext(*this->getFunction()));
  }

  bool isCalleeThin() const {
    auto Rep = getSubstCalleeType()->getRepresentation();
    return Rep == FunctionType::Representation::Thin;
  }

  /// Returns true if the callee function is annotated with
  /// @_semantics("programtermination_point")
  bool isCalleeKnownProgramTerminationPoint() const {
    auto calleeFn = getCalleeFunction();
    if (!calleeFn) return false;
    return calleeFn->hasSemanticsAttr(SEMANTICS_PROGRAMTERMINATION_POINT);
  }

  /// True if this application has generic substitutions.
  bool hasSubstitutions() const {
    return Substitutions.hasAnySubstitutableParams();
  }

  /// The substitutions used to bind the generic arguments of this function.
  SubstitutionMap getSubstitutionMap() const { return Substitutions; }

  /// Return the total number of operands of this instruction.
  unsigned getNumAllOperands() const {
    return NumStaticOperands + NumCallArguments + NumTypeDependentOperands;
  }

  /// Return all the operands of this instruction, which are (in order):
  ///   - the callee
  ///   - the formal arguments
  ///   - the type-dependency arguments
  MutableArrayRef<Operand> getAllOperands() {
    return { asImpl().template getTrailingObjects<Operand>(),
             getNumAllOperands() };
  }

  ArrayRef<Operand> getAllOperands() const {
    return { asImpl().template getTrailingObjects<Operand>(),
             getNumAllOperands() };
  }

  /// Check whether the given operand index is a call-argument index
  /// and, if so, return that index.
  Optional<unsigned> getArgumentIndexForOperandIndex(unsigned index) {
    assert(index < getNumAllOperands());
    if (index < NumStaticOperands) return None;
    index -= NumStaticOperands;
    if (index >= NumCallArguments) return None;
    return index;
  }

  /// The arguments passed to this instruction.
  MutableArrayRef<Operand> getArgumentOperands() {
    return getAllOperands().slice(NumStaticOperands, NumCallArguments);
  }

  ArrayRef<Operand> getArgumentOperands() const {
    return getAllOperands().slice(NumStaticOperands, NumCallArguments);
  }

  /// The arguments passed to this instruction.
  OperandValueArrayRef getArguments() const {
    return OperandValueArrayRef(getArgumentOperands());
  }

  /// Returns the number of arguments being passed by this apply.
  /// If this is a partial_apply, it can be less than the number of
  /// parameters.
  unsigned getNumArguments() const { return NumCallArguments; }

  Operand &getArgumentRef(unsigned i) {
    return getArgumentOperands()[i];
  }

  /// Return the ith argument passed to this instruction.
  SILValue getArgument(unsigned i) const { return getArguments()[i]; }

  /// Set the ith argument of this instruction.
  void setArgument(unsigned i, SILValue V) {
    return getArgumentOperands()[i].set(V);
  }

  ArrayRef<Operand> getTypeDependentOperands() const {
    return getAllOperands().slice(NumStaticOperands + NumCallArguments);
  }

  MutableArrayRef<Operand> getTypeDependentOperands() {
    return getAllOperands().slice(NumStaticOperands + NumCallArguments);
  }

  const GenericSpecializationInformation *getSpecializationInfo() const {
    return SpecializationInfo;
  }
};

/// Given the callee operand of an apply or try_apply instruction,
/// does it have the given semantics?
bool doesApplyCalleeHaveSemantics(SILValue callee, StringRef semantics);

/// Predicate used to filter InoutArgumentRange.
struct OperandToInoutArgument {
  ArrayRef<SILParameterInfo> paramInfos;
  OperandValueArrayRef arguments;
  OperandToInoutArgument(ArrayRef<SILParameterInfo> paramInfos,
                         OperandValueArrayRef arguments)
      : paramInfos(paramInfos), arguments(arguments) {
    assert(paramInfos.size() == arguments.size());
  }
  Optional<SILValue> operator()(size_t i) const {
    if (paramInfos[i].isIndirectMutating())
      return arguments[i];
    return None;
  }
};

using InoutArgumentRange =
    OptionalTransformRange<IntRange<size_t>, OperandToInoutArgument>;

/// The partial specialization of ApplyInstBase for full applications.
/// Adds some methods relating to 'self' and to result types that don't
/// make sense for partial applications.
template <class Impl, class Base>
class ApplyInstBase<Impl, Base, true>
  : public ApplyInstBase<Impl, Base, false> {
  using super = ApplyInstBase<Impl, Base, false>;
protected:
  template <class... As>
  ApplyInstBase(As &&...args)
    : ApplyInstBase<Impl, Base, false>(std::forward<As>(args)...) {}

private:
  const Impl &asImpl() const { return static_cast<const Impl &>(*this); }

public:
  using super::getCallee;
  using super::getSubstCalleeType;
  using super::getSubstCalleeConv;
  using super::hasSubstitutions;
  using super::getNumArguments;
  using super::getArgument;
  using super::getArguments;
  using super::getArgumentOperands;

  /// The collection of following routines wrap the representation difference in
  /// between the self substitution being first, but the self parameter of a
  /// function being last.
  ///
  /// The hope is that this will prevent any future bugs from coming up related
  /// to this.
  ///
  /// Self is always the last parameter, but self substitutions are always
  /// first. The reason to add this method is to wrap that dichotomy to reduce
  /// errors.
  ///
  /// FIXME: Could this be standardized? It has and will lead to bugs. IMHO.
  SILValue getSelfArgument() const {
    assert(hasSelfArgument() && "Must have a self argument");
    assert(getNumArguments() && "Should only be called when Callee has "
           "arguments.");
    return getArgument(getNumArguments()-1);
  }

  Operand &getSelfArgumentOperand() {
    assert(hasSelfArgument() && "Must have a self argument");
    assert(getNumArguments() && "Should only be called when Callee has "
           "arguments.");
    return getArgumentOperands()[getNumArguments()-1];
  }

  void setSelfArgument(SILValue V) {
    assert(hasSelfArgument() && "Must have a self argument");
    assert(getNumArguments() && "Should only be called when Callee has "
                                      "arguments.");
    getArgumentOperands()[getNumArguments() - 1].set(V);
  }

  OperandValueArrayRef getArgumentsWithoutSelf() const {
    assert(hasSelfArgument() && "Must have a self argument");
    assert(getNumArguments() && "Should only be called when Callee has "
           "at least a self parameter.");
    ArrayRef<Operand> ops = this->getArgumentOperands();
    ArrayRef<Operand> opsWithoutSelf = ArrayRef<Operand>(&ops[0],
                                                         ops.size()-1);
    return OperandValueArrayRef(opsWithoutSelf);
  }

  Optional<SILResultInfo> getSingleResult() const {
    auto SubstCallee = getSubstCalleeType();
    if (SubstCallee->getNumAllResults() != 1)
      return None;
    return SubstCallee->getSingleResult();
  }

  bool hasIndirectResults() const {
    return getSubstCalleeConv().hasIndirectSILResults();
  }
  unsigned getNumIndirectResults() const {
    return getSubstCalleeConv().getNumIndirectSILResults();
  }

  bool hasSelfArgument() const {
    return getSubstCalleeType()->hasSelfParam();
  }

  bool hasGuaranteedSelfArgument() const {
    auto C = getSubstCalleeType()->getSelfParameter().getConvention();
    return C == ParameterConvention::Direct_Guaranteed;
  }

  OperandValueArrayRef getIndirectSILResults() const {
    return getArguments().slice(0, getNumIndirectResults());
  }

  OperandValueArrayRef getArgumentsWithoutIndirectResults() const {
    return getArguments().slice(getNumIndirectResults());
  }

  /// Returns all `@inout` and `@inout_aliasable` arguments passed to the
  /// instruction.
  InoutArgumentRange getInoutArguments() const {
    auto &impl = asImpl();
    return InoutArgumentRange(
        indices(getArgumentsWithoutIndirectResults()),
        OperandToInoutArgument(impl.getSubstCalleeConv().getParameters(),
                               impl.getArgumentsWithoutIndirectResults()));
  }

  bool hasSemantics(StringRef semanticsString) const {
    return doesApplyCalleeHaveSemantics(getCallee(), semanticsString);
  }
};

/// ApplyInst - Represents the full application of a function value.
class ApplyInst final
    : public InstructionBase<SILInstructionKind::ApplyInst,
                             ApplyInstBase<ApplyInst, SingleValueInstruction>>,
      public llvm::TrailingObjects<ApplyInst, Operand> {
  friend SILBuilder;

  ApplyInst(SILDebugLocation DebugLoc, SILValue Callee,
            SILType SubstCalleeType, SILType ReturnType,
            SubstitutionMap Substitutions,
            ArrayRef<SILValue> Args,
            ArrayRef<SILValue> TypeDependentOperands,
            bool isNonThrowing,
            const GenericSpecializationInformation *SpecializationInfo);

  static ApplyInst *
  create(SILDebugLocation DebugLoc, SILValue Callee,
         SubstitutionMap Substitutions, ArrayRef<SILValue> Args,
         bool isNonThrowing, Optional<SILModuleConventions> ModuleConventions,
         SILFunction &F, SILOpenedArchetypesState &OpenedArchetypes,
         const GenericSpecializationInformation *SpecializationInfo);

public:
  /// Returns true if the called function has an error result but is not actually
  /// throwing an error.
  bool isNonThrowing() const {
    return isNonThrowingApply();
  }
};

/// PartialApplyInst - Represents the creation of a closure object by partial
/// application of a function value.
class PartialApplyInst final
    : public InstructionBase<SILInstructionKind::PartialApplyInst,
                             ApplyInstBase<PartialApplyInst,
                                           SingleValueInstruction>>,
      public llvm::TrailingObjects<PartialApplyInst, Operand> {
  friend SILBuilder;

public:
  enum OnStackKind {
    NotOnStack, OnStack
  };

private:
  PartialApplyInst(SILDebugLocation DebugLoc, SILValue Callee,
                   SILType SubstCalleeType,
                   SubstitutionMap Substitutions,
                   ArrayRef<SILValue> Args,
                   ArrayRef<SILValue> TypeDependentOperands,
                   SILType ClosureType,
                   const GenericSpecializationInformation *SpecializationInfo);

  static PartialApplyInst *
  create(SILDebugLocation DebugLoc, SILValue Callee, ArrayRef<SILValue> Args,
         SubstitutionMap Substitutions, ParameterConvention CalleeConvention,
         SILFunction &F, SILOpenedArchetypesState &OpenedArchetypes,
         const GenericSpecializationInformation *SpecializationInfo,
         OnStackKind onStack);

public:
  /// Return the result function type of this partial apply.
  CanSILFunctionType getFunctionType() const {
    return getType().castTo<SILFunctionType>();
  }
  bool hasCalleeGuaranteedContext() const {
    return getType().castTo<SILFunctionType>()->isCalleeGuaranteed();
  }

  OnStackKind isOnStack() const {
    return getFunctionType()->isNoEscape() ? OnStack : NotOnStack;
  }
};

class BeginApplyInst;
class BeginApplyResult final : public MultipleValueInstructionResult {
public:
  BeginApplyResult(unsigned index, SILType type,
                   ValueOwnershipKind ownershipKind)
      : MultipleValueInstructionResult(ValueKind::BeginApplyResult,
                                       index, type, ownershipKind) {}

  BeginApplyInst *getParent(); // inline below
  const BeginApplyInst *getParent() const {
    return const_cast<BeginApplyResult *>(this)->getParent();
  }

  /// Is this result the token result of the begin_apply, which abstracts
  /// over the implicit coroutine state?
  bool isTokenResult() const; // inline below

  static bool classof(const SILNode *N) {
    return N->getKind() == SILNodeKind::BeginApplyResult;
  }
};

class EndApplyInst;
class AbortApplyInst;

/// BeginApplyInst - Represents the beginning of the full application of
/// a yield_once coroutine (up until the coroutine yields a value back).
class BeginApplyInst final
    : public InstructionBase<SILInstructionKind::BeginApplyInst,
                             ApplyInstBase<BeginApplyInst,
                                           MultipleValueInstruction>>,
      public MultipleValueInstructionTrailingObjects<
          BeginApplyInst, BeginApplyResult,
          // These must be earlier trailing objects because their
          // count fields are initialized by an earlier base class.
          InitialTrailingObjects<Operand>> {
  friend SILBuilder;

  template <class, class...>
  friend class llvm::TrailingObjects;
  using InstructionBase::numTrailingObjects;
  using MultipleValueInstructionTrailingObjects::numTrailingObjects;

  friend class ApplyInstBase<BeginApplyInst, MultipleValueInstruction, false>;
  using MultipleValueInstructionTrailingObjects::getTrailingObjects;

  BeginApplyInst(SILDebugLocation debugLoc, SILValue callee,
                 SILType substCalleeType,
                 ArrayRef<SILType> allResultTypes,
                 ArrayRef<ValueOwnershipKind> allResultOwnerships,
                 SubstitutionMap substitutions,
                 ArrayRef<SILValue> args,
                 ArrayRef<SILValue> typeDependentOperands,
                 bool isNonThrowing,
                 const GenericSpecializationInformation *specializationInfo);

  static BeginApplyInst *
  create(SILDebugLocation debugLoc, SILValue Callee,
         SubstitutionMap substitutions, ArrayRef<SILValue> args,
         bool isNonThrowing, Optional<SILModuleConventions> moduleConventions,
         SILFunction &F, SILOpenedArchetypesState &openedArchetypes,
         const GenericSpecializationInformation *specializationInfo);

public:
  using MultipleValueInstructionTrailingObjects::totalSizeToAlloc;

  SILValue getTokenResult() const {
    return &getAllResultsBuffer().back();
  }

  SILInstructionResultArray getYieldedValues() const {
    return getAllResultsBuffer().drop_back();
  }

  /// Returns true if the called coroutine has an error result but is not
  /// actually throwing an error.
  bool isNonThrowing() const {
    return isNonThrowingApply();
  }

  void getCoroutineEndPoints(
      SmallVectorImpl<EndApplyInst *> &endApplyInsts,
      SmallVectorImpl<AbortApplyInst *> &abortApplyInsts) const;

  void getCoroutineEndPoints(SmallVectorImpl<Operand *> &endApplyInsts,
                             SmallVectorImpl<Operand *> &abortApplyInsts) const;
};

inline BeginApplyInst *BeginApplyResult::getParent() {
  auto *Parent = MultipleValueInstructionResult::getParent();
  return cast<BeginApplyInst>(Parent);
}
inline bool BeginApplyResult::isTokenResult() const {
  return getIndex() == getParent()->getNumResults() - 1;
}

/// AbortApplyInst - Unwind the full application of a yield_once coroutine.
class AbortApplyInst
    : public UnaryInstructionBase<SILInstructionKind::AbortApplyInst,
                                  NonValueInstruction> {
  friend SILBuilder;

  AbortApplyInst(SILDebugLocation debugLoc, SILValue beginApplyToken)
      : UnaryInstructionBase(debugLoc, beginApplyToken) {
    assert(isa<BeginApplyResult>(beginApplyToken) &&
           cast<BeginApplyResult>(beginApplyToken)->isTokenResult());
  }

public:
  BeginApplyInst *getBeginApply() const {
    return cast<BeginApplyResult>(getOperand())->getParent();
  }
};

/// EndApplyInst - Resume the full application of a yield_once coroutine
/// normally.
class EndApplyInst
    : public UnaryInstructionBase<SILInstructionKind::EndApplyInst,
                                  NonValueInstruction> {
  friend SILBuilder;

  EndApplyInst(SILDebugLocation debugLoc, SILValue beginApplyToken)
      : UnaryInstructionBase(debugLoc, beginApplyToken) {
    assert(isa<BeginApplyResult>(beginApplyToken) &&
           cast<BeginApplyResult>(beginApplyToken)->isTokenResult());
  }

public:
  BeginApplyInst *getBeginApply() const {
    return cast<BeginApplyResult>(getOperand())->getParent();
  }
};

//===----------------------------------------------------------------------===//
// Literal instructions.
//===----------------------------------------------------------------------===//

/// Abstract base class for literal instructions.
class LiteralInst : public SingleValueInstruction {
protected:
  LiteralInst(SILInstructionKind Kind, SILDebugLocation DebugLoc, SILType Ty)
      : SingleValueInstruction(Kind, DebugLoc, Ty) {}

public:

  DEFINE_ABSTRACT_SINGLE_VALUE_INST_BOILERPLATE(LiteralInst)
};

class FunctionRefBaseInst : public LiteralInst {
  SILFunction *f;

protected:
  FunctionRefBaseInst(SILInstructionKind Kind, SILDebugLocation DebugLoc,
                      SILFunction *F, TypeExpansionContext context);

public:
  ~FunctionRefBaseInst();

  /// Return the referenced function if this is a function_ref instruction and
  /// therefore a client can rely on the dynamically called function being equal
  /// to the returned value and null otherwise.
  SILFunction *getReferencedFunctionOrNull() const {
    auto kind = getKind();
    if (kind == SILInstructionKind::FunctionRefInst)
      return f;
    assert(kind == SILInstructionKind::DynamicFunctionRefInst ||
           kind == SILInstructionKind::PreviousDynamicFunctionRefInst);
    return nullptr;
  }

  /// Return the initially referenced function.
  ///
  /// WARNING: This not necessarily the function that will be called at runtime.
  /// If the callee is a (prev_)dynamic_function_ref the actual function called
  /// might be different because it could be dynamically replaced at runtime.
  ///
  /// If the client of this API wants to look at the content of the returned SIL
  /// function it should call getReferencedFunctionOrNull() instead.
  SILFunction *getInitiallyReferencedFunction() const { return f; }

  void dropReferencedFunction();

  CanSILFunctionType getFunctionType() const {
    return getType().castTo<SILFunctionType>();
  }
  SILFunctionConventions getConventions() const {
    return SILFunctionConventions(getFunctionType(), getModule());
  }

  ArrayRef<Operand> getAllOperands() const { return {}; }
  MutableArrayRef<Operand> getAllOperands() { return {}; }

  static bool classof(const SILNode *node) {
    return (node->getKind() == SILNodeKind::FunctionRefInst ||
        node->getKind() == SILNodeKind::DynamicFunctionRefInst ||
        node->getKind() == SILNodeKind::PreviousDynamicFunctionRefInst);
  }
  static bool classof(const SingleValueInstruction *node) {
    return (node->getKind() == SILInstructionKind::FunctionRefInst ||
        node->getKind() == SILInstructionKind::DynamicFunctionRefInst ||
        node->getKind() == SILInstructionKind::PreviousDynamicFunctionRefInst);
  }
};

/// FunctionRefInst - Represents a reference to a SIL function.
class FunctionRefInst : public FunctionRefBaseInst {
  friend SILBuilder;

  /// Construct a FunctionRefInst.
  ///
  /// \param DebugLoc  The location of the reference.
  /// \param F         The function being referenced.
  /// \param context   The type expansion context of the function reference.
  FunctionRefInst(SILDebugLocation DebugLoc, SILFunction *F,
                  TypeExpansionContext context);

public:
  static bool classof(const SILNode *node) {
    return node->getKind() == SILNodeKind::FunctionRefInst;
  }
  static bool classof(const SingleValueInstruction *node) {
    return node->getKind() == SILInstructionKind::FunctionRefInst;
  }
};

class DynamicFunctionRefInst : public FunctionRefBaseInst {
  friend SILBuilder;

  /// Construct a DynamicFunctionRefInst.
  ///
  /// \param DebugLoc  The location of the reference.
  /// \param F         The function being referenced.
  /// \param context   The type expansion context of the function reference.
  DynamicFunctionRefInst(SILDebugLocation DebugLoc, SILFunction *F,
                         TypeExpansionContext context);

public:
  static bool classof(const SILNode *node) {
    return node->getKind() == SILNodeKind::DynamicFunctionRefInst;
  }
  static bool classof(const SingleValueInstruction *node) {
    return node->getKind() == SILInstructionKind::DynamicFunctionRefInst;
  }
};

class PreviousDynamicFunctionRefInst : public FunctionRefBaseInst {
  friend SILBuilder;

  /// Construct a PreviousDynamicFunctionRefInst.
  ///
  /// \param DebugLoc  The location of the reference.
  /// \param F         The function being referenced.
  /// \param context   The type expansion context of the function reference.
  PreviousDynamicFunctionRefInst(SILDebugLocation DebugLoc, SILFunction *F,
                                 TypeExpansionContext context);

public:
  static bool classof(const SILNode *node) {
    return node->getKind() == SILNodeKind::PreviousDynamicFunctionRefInst;
  }
  static bool classof(const SingleValueInstruction *node) {
    return node->getKind() ==
           SILInstructionKind::PreviousDynamicFunctionRefInst;
  }
};

/// Component of a KeyPathInst.
class KeyPathPatternComponent {
public:
  /// Computed property components require an identifier so they can be stably
  /// identified at runtime. This has to correspond to the ABI of the property--
  /// whether a reabstracted stored property, a property dispatched through a
  /// vtable or witness table, or a computed property.
  class ComputedPropertyId {
    friend KeyPathPatternComponent;
  public:
    enum KindType {
      Property, Function, DeclRef,
    };
  private:
  
    union ValueType {
      AbstractStorageDecl *Property;
      SILFunction *Function;
      SILDeclRef DeclRef;
      
      ValueType() : Property(nullptr) {}
      ValueType(AbstractStorageDecl *p) : Property(p) {}
      ValueType(SILFunction *f) : Function(f) {}
      ValueType(SILDeclRef d) : DeclRef(d) {}
    } Value;
  
    KindType Kind;
    
    explicit ComputedPropertyId(ValueType Value, KindType Kind)
      : Value(Value), Kind(Kind)
    {}
    
  public:
    ComputedPropertyId() : Value(), Kind(Property) {}
  
    /*implicit*/ ComputedPropertyId(VarDecl *property)
      : Value{property}, Kind{Property}
    {
    }
    
    /*implicit*/ ComputedPropertyId(SILFunction *function)
      : Value{function}, Kind{Function}
    {}
    
    /*implicit*/ ComputedPropertyId(SILDeclRef declRef)
      : Value{declRef}, Kind{DeclRef}
    {}
    
    KindType getKind() const { return Kind; }
    
    VarDecl *getProperty() const {
      assert(getKind() == Property);
      return cast<VarDecl>(Value.Property);
    }
    
    SILFunction *getFunction() const {
      assert(getKind() == Function);
      return Value.Function;
    }
    
    SILDeclRef getDeclRef() const {
      assert(getKind() == DeclRef);
      return Value.DeclRef;
    }
  };
  
  enum class Kind: unsigned {
    StoredProperty,
    GettableProperty,
    SettableProperty,
    TupleElement,
    OptionalChain,
    OptionalForce,
    OptionalWrap,
  };
  
  // Description of a captured index value and its Hashable conformance for a
  // subscript keypath.
  struct Index {
    unsigned Operand;
    CanType FormalType;
    SILType LoweredType;
    ProtocolConformanceRef Hashable;
  };
  
private:
  enum PackedKind: unsigned {
    PackedStored,
    PackedComputed,
    Unpacked,
  };
  
  static const unsigned KindPackingBits = 2;
  
  static unsigned getPackedKind(Kind k) {
    switch (k) {
    case Kind::StoredProperty:
    case Kind::TupleElement:
      return PackedStored;
    case Kind::GettableProperty:
    case Kind::SettableProperty:
      return PackedComputed;
    case Kind::OptionalChain:
    case Kind::OptionalForce:
    case Kind::OptionalWrap:
      return Unpacked;
    }
  }
  
  // Value is the VarDecl* for StoredProperty, the SILFunction* of the
  // Getter for computed properties, or the Kind for other kinds
  llvm::PointerIntPair<void *, KindPackingBits, unsigned> ValueAndKind;
  llvm::PointerIntPair<SILFunction *, 2,
                       ComputedPropertyId::KindType> SetterAndIdKind;

  // If this component refers to a tuple element then TupleIndex is the
  // 1-based index of the element in the tuple, in order to allow the
  // discrimination of the TupleElement Kind from the StoredProperty Kind
  union {
    unsigned TupleIndex = 0;
    ComputedPropertyId::ValueType IdValue;
  };

  ArrayRef<Index> Indices;
  struct {
    SILFunction *Equal;
    SILFunction *Hash;
  } IndexEquality;
  CanType ComponentType;
  AbstractStorageDecl *ExternalStorage;
  SubstitutionMap ExternalSubstitutions;

  /// Constructor for stored components
  KeyPathPatternComponent(VarDecl *storedProp,
                          CanType ComponentType)
    : ValueAndKind(storedProp, PackedStored),
      ComponentType(ComponentType) {}

  /// Constructor for computed components
  KeyPathPatternComponent(ComputedPropertyId id,
                          SILFunction *getter,
                          SILFunction *setter,
                          ArrayRef<Index> indices,
                          SILFunction *indicesEqual,
                          SILFunction *indicesHash,
                          AbstractStorageDecl *externalStorage,
                          SubstitutionMap externalSubstitutions,
                          CanType ComponentType)
    : ValueAndKind(getter, PackedComputed),
      SetterAndIdKind{setter, id.Kind},
      IdValue{id.Value},
      Indices(indices),
      IndexEquality{indicesEqual, indicesHash},
      ComponentType(ComponentType),
      ExternalStorage(externalStorage),
      ExternalSubstitutions(externalSubstitutions)
  {
  }
  
  /// Constructor for optional components.
  KeyPathPatternComponent(Kind kind, CanType componentType)
    : ValueAndKind((void*)((uintptr_t)kind << KindPackingBits), Unpacked),
      ComponentType(componentType) {
    assert((unsigned)kind >