text: //===--- Verifier.cpp - Verification of Swift SIL Code --------------------===//
  //
  // 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
  //
  //===----------------------------------------------------------------------===//
  
  #define DEBUG_TYPE "sil-verifier"
  #include "swift/AST/ASTContext.h"
  #include "swift/AST/AnyFunctionRef.h"
  #include "swift/AST/Decl.h"
  #include "swift/AST/ExistentialLayout.h"
  #include "swift/AST/GenericEnvironment.h"
  #include "swift/AST/Module.h"
  #include "swift/AST/ParameterList.h"
  #include "swift/AST/ProtocolConformance.h"
  #include "swift/AST/Types.h"
  #include "swift/Basic/Range.h"
  #include "swift/ClangImporter/ClangModule.h"
  #include "swift/SIL/ApplySite.h"
  #include "swift/SIL/BasicBlockUtils.h"
  #include "swift/SIL/DebugUtils.h"
  #include "swift/SIL/Dominance.h"
  #include "swift/SIL/DynamicCasts.h"
  #include "swift/SIL/MemAccessUtils.h"
  #include "swift/SIL/PostOrder.h"
  #include "swift/SIL/PrettyStackTrace.h"
  #include "swift/SIL/SILDebugScope.h"
  #include "swift/SIL/SILFunction.h"
  #include "swift/SIL/SILModule.h"
  #include "swift/SIL/SILOpenedArchetypesTracker.h"
  #include "swift/SIL/SILVTable.h"
  #include "swift/SIL/SILVTableVisitor.h"
  #include "swift/SIL/SILVisitor.h"
  #include "swift/SIL/TypeLowering.h"
  #include "llvm/ADT/DenseSet.h"
  #include "llvm/ADT/PostOrderIterator.h"
  #include "llvm/ADT/StringSet.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/Debug.h"
  using namespace swift;
  
  using Lowering::AbstractionPattern;
  
  // This flag is used only to check that sil-combine can properly
  // remove any code after unreachable, thus bringing SIL into
  // its canonical form which may get temporarily broken during
  // intermediate transformations.
  static llvm::cl::opt<bool> SkipUnreachableMustBeLastErrors(
                                "verify-skip-unreachable-must-be-last",
                                llvm::cl::init(false));
  
  // This flag controls the default behaviour when hitting a verification
  // failure (abort/exit).
  static llvm::cl::opt<bool> AbortOnFailure(
                                "verify-abort-on-failure",
                                llvm::cl::init(true));
  
  static llvm::cl::opt<bool> VerifyDIHoles(
                                "verify-di-holes",
                                llvm::cl::init(true));
  
  static llvm::cl::opt<bool> SkipConvertEscapeToNoescapeAttributes(
      "verify-skip-convert-escape-to-noescape-attributes", llvm::cl::init(false));
  
  // The verifier is basically all assertions, so don't compile it with NDEBUG to
  // prevent release builds from triggering spurious unused variable warnings.
  
  //===----------------------------------------------------------------------===//
  //                                SILVerifier
  //===----------------------------------------------------------------------===//
  
  /// Returns true if A is an opened existential type or is equal to an
  /// archetype from F's generic context.
  static bool isArchetypeValidInFunction(ArchetypeType *A, const SILFunction *F) {
    auto root = dyn_cast<PrimaryArchetypeType>(A->getRoot());
    if (!root)
      return true;
    if (isa<OpenedArchetypeType>(A->getRoot()))
      return true;
    if (isa<OpaqueTypeArchetypeType>(A->getRoot()))
      return true;
  
    // Ok, we have a primary archetype, make sure it is in the nested generic
    // environment of our caller.
    if (auto *genericEnv = F->getGenericEnvironment())
      if (root->getGenericEnvironment() == genericEnv)
        return true;
  
    return false;
  }
  
  namespace {
  
  /// Metaprogramming-friendly base class.
  template <class Impl>
  class SILVerifierBase : public SILInstructionVisitor<Impl> {
  public:
    // visitCLASS calls visitPARENT and checkCLASS.
    // checkCLASS does nothing by default.
  #define INST(CLASS, PARENT)                                     \
    void visit##CLASS(CLASS *I) {                                 \
      static_cast<Impl*>(this)->visit##PARENT(I);                 \
      static_cast<Impl*>(this)->check##CLASS(I);                  \
    }                                                             \
    void check##CLASS(CLASS *I) {}
  #include "swift/SIL/SILNodes.def"
  
    void visitSILInstruction(SILInstruction *I) {
      static_cast<Impl*>(this)->checkSILInstruction(I);
    }
    void checkSILInstruction(SILInstruction *I) {}
  };
  } // end anonymous namespace
  
  namespace {
  
  /// Verify invariants on a key path component.
  void verifyKeyPathComponent(SILModule &M,
                              ResilienceExpansion expansion,
                              llvm::function_ref<void(bool, StringRef)> require,
                              CanType &baseTy,
                              CanType leafTy,
                              const KeyPathPatternComponent &component,
                              ArrayRef<Operand> operands,
                              CanGenericSignature patternSig,
                              SubstitutionMap patternSubs,
                              bool forPropertyDescriptor,
                              bool hasIndices) {
    auto &C = M.getASTContext();
  
    auto opaque = AbstractionPattern::getOpaque();
    auto loweredBaseTy =
      M.Types.getLoweredType(opaque, baseTy, expansion);
    auto componentTy = component.getComponentType().subst(patternSubs)
      ->getCanonicalType();
    auto loweredComponentTy =
      M.Types.getLoweredType(opaque, componentTy, expansion);
  
    auto checkIndexEqualsAndHash = [&]{
      if (!component.getSubscriptIndices().empty()) {
        // Equals should be
        // <Sig...> @convention(thin) (RawPointer, RawPointer) -> Bool
        {
          auto equals = component.getSubscriptIndexEquals();
          require(equals, "key path pattern with indexes must have equals "
                          "operator");
          
          auto substEqualsType = equals->getLoweredFunctionType()
            ->substGenericArgs(M, patternSubs);
          
          require(substEqualsType->getParameters().size() == 2,
                  "must have two arguments");
          for (unsigned i = 0; i < 2; ++i) {
            auto param = substEqualsType->getParameters()[i];
            require(param.getConvention()
                      == ParameterConvention::Direct_Unowned,
                    "indices pointer should be trivial");
            require(param.getType()->getAnyNominal()
                      == C.getUnsafeRawPointerDecl(),
                    "indices pointer should be an UnsafeRawPointer");
          }
          
          require(substEqualsType->getResults().size() == 1,
                  "must have one result");
          
          require(substEqualsType->getResults()[0].getConvention()
                    == ResultConvention::Unowned,
                  "result should be unowned");
          require(substEqualsType->getResults()[0].getType()->getAnyNominal()
                    == C.getBoolDecl(),
                  "result should be Bool");
        }
        {
          // Hash should be
          // <Sig...> @convention(thin) (RawPointer) -> Int
          auto hash = component.getSubscriptIndexHash();
          require(hash, "key path pattern with indexes must have hash "
                        "operator");
          
          auto substHashType = hash->getLoweredFunctionType()
            ->substGenericArgs(M, patternSubs);
          
          require(substHashType->getParameters().size() == 1,
                  "must have two arguments");
          auto param = substHashType->getParameters()[0];
          require(param.getConvention()
                    == ParameterConvention::Direct_Unowned,
                  "indices pointer should be trivial");
          require(param.getType()->getAnyNominal()
                    == C.getUnsafeRawPointerDecl(),
                  "indices pointer should be an UnsafeRawPointer");
          
          require(substHashType->getResults().size() == 1,
                  "must have one result");
          
          require(substHashType->getResults()[0].getConvention()
                    == ResultConvention::Unowned,
                  "result should be unowned");
          require(substHashType->getResults()[0].getType()->getAnyNominal()
                    == C.getIntDecl(),
                  "result should be Int");
        }
      } else {
        require(!component.getSubscriptIndexEquals()
                && !component.getSubscriptIndexHash(),
                "component without indexes must not have equals/hash");
      }
    };
  
    switch (auto kind = component.getKind()) {
    case KeyPathPatternComponent::Kind::StoredProperty: {
      auto property = component.getStoredPropertyDecl();
      if (expansion == ResilienceExpansion::Minimal) {
        require(property->getEffectiveAccess() >= AccessLevel::Public,
                "Key path in serialized function cannot reference non-public "
                "property");
      }
  
      auto fieldTy = baseTy->getTypeOfMember(M.getSwiftModule(), property)
                           ->getReferenceStorageReferent()
                           ->getCanonicalType();
      require(fieldTy == componentTy,
              "property decl should be a member of the base with the same type "
              "as the component");
      require(property->hasStorage(), "property must be stored");
      require(!property->isResilient(M.getSwiftModule(), expansion),
              "cannot access storage of resilient property");
      auto propertyTy = loweredBaseTy.getFieldType(property, M);
      require(propertyTy.getObjectType()
                == loweredComponentTy.getObjectType(),
              "component type should match the maximal abstraction of the "
              "formal type");
      break;
    }
      
    case KeyPathPatternComponent::Kind::GettableProperty:
    case KeyPathPatternComponent::Kind::SettableProperty: {
      if (forPropertyDescriptor) {
        require(component.getSubscriptIndices().empty()
                && !component.getSubscriptIndexEquals()
                && !component.getSubscriptIndexHash(),
                "property descriptor should not have index information");
        
        require(component.getExternalDecl() == nullptr
                && component.getExternalSubstitutions().empty(),
                "property descriptor should not refer to another external decl");
      } else {
        require(hasIndices == !component.getSubscriptIndices().empty(),
                "component for subscript should have indices");
      }
      
      auto normalArgConvention = ParameterConvention::Indirect_In_Guaranteed;
    
      // Getter should be <Sig...> @convention(thin) (@in_guaranteed Base) -> @out Result
      {
        auto getter = component.getComputedPropertyGetter();
        if (expansion == ResilienceExpansion::Minimal) {
          require(getter->hasValidLinkageForFragileRef(),
                  "Key path in serialized function should not reference "
                  "less visible getters");
        }
  
        auto substGetterType = getter->getLoweredFunctionType()
          ->substGenericArgs(M, patternSubs);
        require(substGetterType->getRepresentation() ==
                  SILFunctionTypeRepresentation::Thin,
                "getter should be a thin function");
        
        require(substGetterType->getNumParameters() == 1 + hasIndices,
                "getter should have one parameter");
        auto baseParam = substGetterType->getParameters()[0];
        require(baseParam.getConvention() == normalArgConvention,
                "getter base parameter should have normal arg convention");
        require(baseParam.getType() == loweredBaseTy.getASTType(),
                "getter base parameter should match base of component");
        
        if (hasIndices) {
          auto indicesParam = substGetterType->getParameters()[1];
          require(indicesParam.getConvention()
                    == ParameterConvention::Direct_Unowned,
                  "indices pointer should be trivial");
          require(indicesParam.getType()->getAnyNominal()
                    == C.getUnsafeRawPointerDecl(),
                  "indices pointer should be an UnsafeRawPointer");
        }
  
        require(substGetterType->getNumResults() == 1,
                "getter should have one result");
        auto result = substGetterType->getResults()[0];
        require(result.getConvention() == ResultConvention::Indirect,
                "getter result should be @out");
        require(result.getType() == loweredComponentTy.getASTType(),
                "getter result should match the maximal abstraction of the "
                "formal component type");
      }
      
      if (kind == KeyPathPatternComponent::Kind::SettableProperty) {
        // Setter should be
        // <Sig...> @convention(thin) (@in_guaranteed Result, @in Base) -> ()
        
        auto setter = component.getComputedPropertySetter();
        if (expansion == ResilienceExpansion::Minimal) {
          require(setter->hasValidLinkageForFragileRef(),
                  "Key path in serialized function should not reference "
                  "less visible setters");
        }
  
        auto substSetterType = setter->getLoweredFunctionType()
          ->substGenericArgs(M, patternSubs);
        
        require(substSetterType->getRepresentation() ==
                  SILFunctionTypeRepresentation::Thin,
                "setter should be a thin function");
        
        require(substSetterType->getNumParameters() == 2 + hasIndices,
                "setter should have two parameters");
  
        auto newValueParam = substSetterType->getParameters()[0];
        // TODO: This should probably be unconditionally +1 when we
        // can represent that.
        require(newValueParam.getConvention() == normalArgConvention,
                "setter value parameter should havee normal arg convention");
  
        auto baseParam = substSetterType->getParameters()[1];
        require(baseParam.getConvention() == normalArgConvention
                || baseParam.getConvention() ==
                    ParameterConvention::Indirect_Inout,
                "setter base parameter should be normal arg convention "
                "or @inout");
        
        if (hasIndices) {
          auto indicesParam = substSetterType->getParameters()[2];
          require(indicesParam.getConvention()
                    == ParameterConvention::Direct_Unowned,
                  "indices pointer should be trivial");
          require(indicesParam.getType()->getAnyNominal()
                    == C.getUnsafeRawPointerDecl(),
                  "indices pointer should be an UnsafeRawPointer");
        }
  
        require(newValueParam.getType() ==
                  loweredComponentTy.getASTType(),
                "setter value should match the maximal abstraction of the "
                "formal component type");
        
        require(substSetterType->getNumResults() == 0,
                "setter should have no results");
      }
      
      if (!forPropertyDescriptor) {
        for (auto &index : component.getSubscriptIndices()) {
          auto opIndex = index.Operand;
          auto contextType =
            index.LoweredType.subst(M, patternSubs);
          require(contextType == operands[opIndex].get()->getType(),
                  "operand must match type required by pattern");
          SILType loweredType = index.LoweredType;
          require(loweredType.isLoweringOf(M, index.FormalType),
                  "pattern index formal type doesn't match lowered type");
        }
  
        checkIndexEqualsAndHash();
      }
      
      break;
    }
    case KeyPathPatternComponent::Kind::OptionalChain: {
      require(baseTy->getOptionalObjectType()->isEqual(componentTy),
              "chaining component should unwrap optional");
      require((bool)leafTy->getOptionalObjectType(),
              "key path with chaining component should have optional "
              "result");
      break;
    }
    case KeyPathPatternComponent::Kind::OptionalForce: {
      require(baseTy->getOptionalObjectType()->isEqual(componentTy),
              "forcing component should unwrap optional");
      break;
    }
    case KeyPathPatternComponent::Kind::OptionalWrap: {
      require(componentTy->getOptionalObjectType()->isEqual(baseTy),
              "wrapping component should wrap optional");
      break;
    }
    case KeyPathPatternComponent::Kind::TupleElement: {
      require(loweredBaseTy.is<TupleType>(),
              "invalid baseTy, should have been a TupleType");
        
      auto tupleTy = loweredBaseTy.castTo<TupleType>();
      auto eltIdx = component.getTupleIndex();
        
      require(eltIdx < tupleTy->getNumElements(),
              "invalid element index, greater than # of tuple elements");
  
      auto eltTy = tupleTy.getElementType(eltIdx)
        .getReferenceStorageReferent();
      
      require(eltTy == componentTy,
              "tuple element type should match the type of the component");
  
      break;
    }
    }
    
    baseTy = componentTy;
  }
  
  /// Check if according to the SIL language model this memory /must only/ be used
  /// immutably. Today this is only applied to in_guaranteed arguments and
  /// open_existential_addr. We should expand it as needed.
  struct ImmutableAddressUseVerifier {
    SmallVector<Operand *, 32> worklist;
  
    bool isConsumingOrMutatingArgumentConvention(SILArgumentConvention conv) {
      switch (conv) {
      case SILArgumentConvention::Indirect_In_Guaranteed:
        return false;
  
      case SILArgumentConvention::Indirect_InoutAliasable:
        // DISCUSSION: We do not consider inout_aliasable to be "truly mutating"
        // since today it is just used as a way to mark a captured argument and
        // not that something truly has mutating semantics. The reason why this
        // is safe is that the typechecker guarantees that if our value was
        // immutable, then the use in the closure must be immutable as well.
        //
        // TODO: Remove this in favor of using Inout and In_Guaranteed.
        return false;
  
      case SILArgumentConvention::Indirect_Out:
      case SILArgumentConvention::Indirect_In:
      case SILArgumentConvention::Indirect_In_Constant:
      case SILArgumentConvention::Indirect_Inout:
        return true;
  
      case SILArgumentConvention::Direct_Unowned:
      case SILArgumentConvention::Direct_Guaranteed:
      case SILArgumentConvention::Direct_Owned:
      case SILArgumentConvention::Direct_Deallocating:
        assert(conv.isIndirectConvention() && "Expect an indirect convention");
        return true; // return something "conservative".
      }
      llvm_unreachable("covered switch isn't covered?!");
    }
  
    bool isConsumingOrMutatingApplyUse(Operand *use) {
      ApplySite apply(use->getUser());
      assert(apply && "Not an apply instruction kind");
      auto conv = apply.getArgumentConvention(*use);
      return isConsumingOrMutatingArgumentConvention(conv);
    }
  
    bool isConsumingOrMutatingYieldUse(Operand *use) {
      // For now, just say that it is non-consuming for now.
      auto *yield = cast<YieldInst>(use->getUser());
      auto conv = yield->getArgumentConventionForOperand(*use);
      return isConsumingOrMutatingArgumentConvention(conv);
    }
  
    // A "copy_addr %src [take] to *" is consuming on "%src".
    // A "copy_addr * to * %dst" is mutating on "%dst".
    bool isConsumingOrMutatingCopyAddrUse(Operand *use) {
      auto *copyAddr = cast<CopyAddrInst>(use->getUser());
      if (copyAddr->getDest() == use->get())
        return true;
      if (copyAddr->getSrc() == use->get() && copyAddr->isTakeOfSrc() == IsTake)
        return true;
      return false;
    }
  
    bool isCastToNonConsuming(UncheckedAddrCastInst *i) {
      // Check if any of our uses are consuming. If none of them are consuming, we
      // are good to go.
      return llvm::none_of(i->getUses(), [&](Operand *use) -> bool {
        auto *inst = use->getUser();
        switch (inst->getKind()) {
        default:
          return false;
        case SILInstructionKind::ApplyInst:
        case SILInstructionKind::TryApplyInst:
        case SILInstructionKind::PartialApplyInst:
        case SILInstructionKind::BeginApplyInst:
          return isConsumingOrMutatingApplyUse(use);
        }
      });
    }
  
    bool isMutatingOrConsuming(SILValue address) {
      copy(address->getUses(), std::back_inserter(worklist));
      while (!worklist.empty()) {
        auto *use = worklist.pop_back_val();
        auto *inst = use->getUser();
  
        if (inst->isTypeDependentOperand(*use))
          continue;
  
        switch (inst->getKind()) {
        case SILInstructionKind::MarkDependenceInst:
        case SILInstructionKind::LoadBorrowInst:
        case SILInstructionKind::DebugValueAddrInst:
        case SILInstructionKind::ExistentialMetatypeInst:
        case SILInstructionKind::ValueMetatypeInst:
        case SILInstructionKind::FixLifetimeInst:
        case SILInstructionKind::KeyPathInst:
        case SILInstructionKind::SwitchEnumAddrInst:
          break;
        case SILInstructionKind::AddressToPointerInst:
          // We assume that the user is attempting to do something unsafe since we
          // are converting to a raw pointer. So just ignore this use.
          //
          // TODO: Can we do better?
          break;
        case SILInstructionKind::BranchInst:
        case SILInstructionKind::CondBranchInst:
          // We do not analyze through branches and cond_br instructions and just
          // assume correctness. This is so that we can avoid having to analyze
          // through phi loops and since we want to remove address phis (meaning
          // that this eventually would never be able to happen). Once that
          // changes happens, we should remove this code and just error below.
          break;
        case SILInstructionKind::ApplyInst:
        case SILInstructionKind::TryApplyInst:
        case SILInstructionKind::PartialApplyInst:
        case SILInstructionKind::BeginApplyInst:
          if (isConsumingOrMutatingApplyUse(use))
            return true;
          break;
        case SILInstructionKind::YieldInst:
          if (isConsumingOrMutatingYieldUse(use))
            return true;
          break;
        case SILInstructionKind::CopyAddrInst:
          if (isConsumingOrMutatingCopyAddrUse(use))
            return true;
          else
            break;
        case SILInstructionKind::DestroyAddrInst:
          return true;
        case SILInstructionKind::UncheckedAddrCastInst: {
          if (isCastToNonConsuming(cast<UncheckedAddrCastInst>(inst))) {
            break;
          }
          return true;
        }
        case SILInstructionKind::CheckedCastAddrBranchInst:
          switch (cast<CheckedCastAddrBranchInst>(inst)->getConsumptionKind()) {
          case CastConsumptionKind::BorrowAlways:
            llvm_unreachable("checked_cast_addr_br cannot have BorrowAlways");
          case CastConsumptionKind::CopyOnSuccess:
            break;
          case CastConsumptionKind::TakeAlways:
          case CastConsumptionKind::TakeOnSuccess:
            return true;
          }
          break;
        case SILInstructionKind::LoadInst:
          // A 'non-taking' value load is harmless.
          if (cast<LoadInst>(inst)->getOwnershipQualifier() ==
              LoadOwnershipQualifier::Take)
            return true;
          break;
  #define NEVER_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)             \
    case SILInstructionKind::Load##Name##Inst:                                   \
      if (cast<Load##Name##Inst>(inst)->isTake())                                \
        return true;                                                             \
      break;
  #include "swift/AST/ReferenceStorage.def"
        case SILInstructionKind::OpenExistentialAddrInst:
          // If we have a mutable use, return true. Otherwise fallthrough since we
          // want to look through immutable uses.
          if (cast<OpenExistentialAddrInst>(inst)->getAccessKind() !=
              OpenedExistentialAccess::Immutable)
            return true;
          LLVM_FALLTHROUGH;
        case SILInstructionKind::StructElementAddrInst:
        case SILInstructionKind::TupleElementAddrInst:
        case SILInstructionKind::IndexAddrInst:
        case SILInstructionKind::TailAddrInst:
        case SILInstructionKind::IndexRawPointerInst:
          // Add these to our worklist.
          for (auto result : inst->getResults()) {
            copy(result->getUses(), std::back_inserter(worklist));
          }
          break;
        default:
          llvm::errs() << "Unhandled, unexpected instruction: " << *inst;
          llvm_unreachable("invoking standard assertion failure");
          break;
        }
      }
      return false;
    }
  };
  
  /// The SIL verifier walks over a SIL function / basic block / instruction,
  /// checking and enforcing its invariants.
  class SILVerifier : public SILVerifierBase<SILVerifier> {
    ModuleDecl *M;
    const SILFunction &F;
    SILFunctionConventions fnConv;
    Lowering::TypeConverter &TC;
    SILOpenedArchetypesTracker OpenedArchetypes;
    SmallVector<StringRef, 16> DebugVars;
    const SILInstruction *CurInstruction = nullptr;
    const SILArgument *CurArgument = nullptr;
    std::unique_ptr<DominanceInfo> Dominance;
  
    // Used for dominance checking within a basic block.
    llvm::DenseMap<const SILInstruction *, unsigned> InstNumbers;
  
    DeadEndBlocks DEBlocks;
    bool SingleFunction = true;
  
    SILVerifier(const SILVerifier&) = delete;
    void operator=(const SILVerifier&) = delete;
  public:
    bool isSILOwnershipEnabled() const {
      return F.getModule().getOptions().VerifySILOwnership;
    }
  
    void _require(bool condition, const Twine &complaint,
                  const std::function<void()> &extraContext = nullptr) {
      if (condition) return;
  
      llvm::dbgs() << "SIL verification failed: " << complaint << "\n";
  
      if (extraContext) extraContext();
  
      if (CurInstruction) {
        llvm::dbgs() << "Verifying instruction:\n";
        CurInstruction->printInContext(llvm::dbgs());
      } else if (CurArgument) {
        llvm::dbgs() << "Verifying argument:\n";
        CurArgument->printInContext(llvm::dbgs());
      }
      llvm::dbgs() << "In function:\n";
      F.print(llvm::dbgs());
  
      // We abort by default because we want to always crash in
      // the debugger.
      if (AbortOnFailure)
        abort();
      else
        exit(1);
    }
  #define require(condition, complaint) \
    _require(bool(condition), complaint ": " #condition)
  
    template <class T> typename CanTypeWrapperTraits<T>::type
    _requireObjectType(SILType type, const Twine &valueDescription,
                       const char *typeName) {
      _require(type.isObject(), valueDescription + " must be an object");
      auto result = type.getAs<T>();
      _require(bool(result), valueDescription + " must have type " + typeName);
      return result;
    }
    template <class T> typename CanTypeWrapperTraits<T>::type
    _requireObjectType(SILValue value, const Twine &valueDescription,
                       const char *typeName) {
      return _requireObjectType<T>(value->getType(), valueDescription, typeName);
    }
  #define requireObjectType(type, value, valueDescription) \
    _requireObjectType<type>(value, valueDescription, #type)
  
    template <class T> typename CanTypeWrapperTraits<T>::type
    _requireAddressType(SILType type, const Twine &valueDescription,
                        const char *typeName) {
      _require(type.isAddress(), valueDescription + " must be an address");
      auto result = type.getAs<T>();
      _require(bool(result), valueDescription + " must have type " + typeName);
      return result;
    }
    template <class T> typename CanTypeWrapperTraits<T>::type
    _requireAddressType(SILValue value, const Twine &valueDescription,
                       const char *typeName) {
      return _requireAddressType<T>(value->getType(), valueDescription, typeName);
    }
  #define requireAddressType(type, value, valueDescription) \
    _requireAddressType<type>(value, valueDescription, #type)
  
    template <class T>
    typename CanTypeWrapperTraits<T>::type
    _forbidObjectType(SILType type, const Twine &valueDescription,
                      const char *typeName) {
      _require(type.isObject(), valueDescription + " must be an object");
      auto result = type.getAs<T>();
      _require(!bool(result),
               valueDescription + " must not have type " + typeName);
      return result;
    }
    template <class T>
    typename CanTypeWrapperTraits<T>::type
    _forbidObjectType(SILValue value, const Twine &valueDescription,
                      const char *typeName) {
      return _forbidObjectType<T>(value->getType(), valueDescription, typeName);
    }
  #define forbidObjectType(type, value, valueDescription)                        \
    _forbidObjectType<type>(value, valueDescription, #type)
  
    // Require that the operand is a non-optional, non-unowned reference-counted
    // type.
    void requireReferenceValue(SILValue value, const Twine &valueDescription) {
      require(value->getType().isObject(), valueDescription +" must be an object");
      require(value->getType().isReferenceCounted(F.getModule()),
              valueDescription + " must have reference semantics");
      forbidObjectType(UnownedStorageType, value, valueDescription);
    }
  
    // Require that the operand is a reference-counted type, or an Optional
    // thereof.
    void requireReferenceOrOptionalReferenceValue(SILValue value,
                                                  const Twine &valueDescription) {
      require(value->getType().isObject(), valueDescription +" must be an object");
      
      auto objectTy = value->getType().unwrapOptionalType();
      
      require(objectTy.isReferenceCounted(F.getModule()),
              valueDescription + " must have reference semantics");
    }
    
    // Require that the operand is a type that supports reference storage
    // modifiers.
    void requireReferenceStorageCapableValue(SILValue value,
                                             const Twine &valueDescription) {
      requireReferenceOrOptionalReferenceValue(value, valueDescription);
      require(!value->getType().is<SILFunctionType>(),
              valueDescription + " cannot apply to a function type");
    }
    
    /// Assert that two types are equal.
    void requireSameType(SILType type1, SILType type2, const Twine &complaint) {
      _require(type1 == type2, complaint, [&] {
        llvm::dbgs() << "  " << type1 << "\n  " << type2 << '\n';
      });
    }
    
    /// Require two function types to be ABI-compatible.
    void requireABICompatibleFunctionTypes(CanSILFunctionType type1,
                                           CanSILFunctionType type2,
                                           const Twine &what,
                                           SILFunction *inFunction = nullptr) {
      auto complain = [=](const char *msg) -> std::function<void()> {
        return [=]{
          llvm::dbgs() << "  " << msg << '\n'
                       << "  " << type1 << "\n  " << type2 << '\n';
        };
      };
      auto complainBy = [=](std::function<void()> msg) -> std::function<void()> {
        return [=]{
          msg();
          llvm::dbgs() << '\n';
          llvm::dbgs() << "  " << type1 << "\n  " << type2 << '\n';
        };
      };
  
      // If we didn't have a failure, return.
      auto Result = type1->isABICompatibleWith(type2, inFunction);
      if (Result.isCompatible())
        return;
  
      if (!Result.hasPayload()) {
        _require(false, what, complain(Result.getMessage().data()));
      } else {
        _require(false, what, complainBy([=] {
                   llvm::dbgs() << " " << Result.getMessage().data()
                                << ".\nParameter: " << Result.getPayload();
                 }));
      }
    }
  
    void requireSameFunctionComponents(CanSILFunctionType type1,
                                       CanSILFunctionType type2,
                                       const Twine &what) {
      require(type1->getNumResults() == type2->getNumResults(),
              "results of " + what + " do not match in count");
      for (auto i : indices(type1->getResults())) {
        require(type1->getResults()[i] == type2->getResults()[i],
                "result " + Twine(i) + " of " + what + " do not match");
      }
      require(type1->getParameters().size() ==
              type2->getParameters().size(),
              "inputs of " + what + " do not match in count");
      for (auto i : indices(type1->getParameters())) {
        require(type1->getParameters()[i] ==
                type2->getParameters()[i],
                "input " + Twine(i) + " of " + what + " do not match");
      }
    }
  
    static unsigned numInstsInFunction(const SILFunction &F) {
      unsigned numInsts = 0;
      for (auto &BB : F) {
        numInsts += std::distance(BB.begin(), BB.end());
      }
      return numInsts;
    }
  
    SILVerifier(const SILFunction &F, bool SingleFunction = true)
        : M(F.getModule().getSwiftModule()), F(F),
          fnConv(F.getLoweredFunctionType(), F.getModule()),
          TC(F.getModule().Types), OpenedArchetypes(&F), Dominance(nullptr),
          InstNumbers(numInstsInFunction(F)),
          DEBlocks(&F), SingleFunction(SingleFunction) {
      if (F.isExternalDeclaration())
        return;
        
      // Check to make sure that all blocks are well formed.  If not, the
      // SILVerifier object will explode trying to compute dominance info.
      unsigned InstIdx = 0;
      for (auto &BB : F) {
        require(!BB.empty(), "Basic blocks cannot be empty");
        require(isa<TermInst>(BB.back()),
                "Basic blocks must end with a terminator instruction");
        for (auto &I : BB)
          InstNumbers[&I] = InstIdx++;
      }
  
      Dominance.reset(new DominanceInfo(const_cast<SILFunction *>(&F)));
  
      auto *DebugScope = F.getDebugScope();
      require(DebugScope, "All SIL functions must have a debug scope");
      require(DebugScope->Parent.get<SILFunction *>() == &F,
              "Scope of SIL function points to different function");
    }
  
    // Checks dominance between two instructions.
    // This does not use DominanceInfo.properlyDominates, because for large basic
    // blocks it would result in quadratic behavior.
    bool properlyDominates(SILInstruction *a, SILInstruction *b) {
      auto aBlock = a->getParent(), bBlock = b->getParent();
  
      // If the blocks are different, it's as easy as whether A's block
      // dominates B's block.
      if (aBlock != bBlock)
        return Dominance->properlyDominates(aBlock, bBlock);
  
      return InstNumbers[a] < InstNumbers[b];
    }
  
    // FIXME: For sanity, address-type block args should be prohibited at all SIL
    // stages. However, the optimizer currently breaks the invariant in three
    // places:
    // 1. Normal Simplify CFG during conditional branch simplification
    //    (sneaky jump threading).
    // 2. Simplify CFG via Jump Threading.
    // 3. Loop Rotation.
    //
    //
    bool prohibitAddressBlockArgs() {
      // If this function was deserialized from canonical SIL, this invariant may
      // already have been violated regardless of this module's SIL stage or
      // exclusivity enforcement level. Presumably, access markers were already
      // removed prior to serialization.
      if (F.wasDeserializedCanonical())
        return false;
  
      SILModule &M = F.getModule();
      return M.getStage() == SILStage::Raw;
    }
  
    void visitSILPhiArgument(SILPhiArgument *arg) {
      // Verify that the `isPhiArgument` property is sound:
      // - Phi arguments come from branches.
      // - Non-phi arguments have a single predecessor.
      if (arg->isPhiArgument()) {
        for (SILBasicBlock *predBB : arg->getParent()->getPredecessorBlocks()) {
          auto *TI = predBB->getTerminator();
          // FIXME: when critical edges are removed, only allow BranchInst.
          require(isa <BranchInst>(TI) || isa<CondBranchInst>(TI),
                  "All phi argument inputs must be from branches.");
        }
      } else {
      }
      if (arg->isPhiArgument() && prohibitAddressBlockArgs()) {
        // As a property of well-formed SIL, we disallow address-type block
        // arguments. Supporting them would prevent reliably reasoning about the
        // underlying storage of memory access. This reasoning is important for
        // diagnosing violations of memory access rules and supporting future
        // optimizations such as bitfield packing. Address-type block arguments
        // also create unnecessary complexity for SIL optimization passes that
        // need to reason about memory aliasing.
        require(!arg->getType().isAddress(),
                "Block arguments cannot be addresses");
      }
    }
  
    void visitSILArgument(SILArgument *arg) {
      CurArgument = arg;
      checkLegalType(arg->getFunction(), arg, nullptr);
      checkValueBaseOwnership(arg);
      if (auto *phiArg = dyn_cast<SILPhiArgument>(arg)) {
        if (phiArg->isPhiArgument())
          visitSILPhiArgument(phiArg);
        else {
          // A non-phi BlockArgument must have a single predecessor unless it is
          // unreachable.
          require(arg->getParent()->pred_empty()
                      || arg->getParent()->getSinglePredecessorBlock(),
                  "Non-branch terminator must have a unique successor.");
        }
        return;
      }
  
      // If we are not in lowered SIL and have an in_guaranteed function argument,
      // verify that we do not mutate or consume it.
      auto *fArg = cast<SILFunctionArgument>(arg);
      if (fArg->getModule().getStage() == SILStage::Lowered ||
          !fArg->getType().isAddress() ||
          !fArg->hasConvention(SILArgumentConvention::Indirect_In_Guaranteed))
        return;
  
      require(!ImmutableAddressUseVerifier().isMutatingOrConsuming(fArg),
              "Found mutating or consuming use of an in_guaranteed parameter?!");
    }
  
    void visitSILInstruction(SILInstruction *I) {
      CurInstruction = I;
      OpenedArchetypes.registerOpenedArchetypes(I);
      checkSILInstruction(I);
  
      // Check the SILLLocation attached to the instruction.
      checkInstructionsSILLocation(I);
  
      // Check ownership.
      SILFunction *F = I->getFunction();
      assert(F && "Expected value base with parent function");
  
      for (auto result : I->getResults()) {
        checkLegalType(F, result, I);
        checkValueBaseOwnership(result);
      }
    }
  
    void checkValueBaseOwnership(ValueBase *V) {
      // If ownership is not enabled, bail.
      if (!isSILOwnershipEnabled())
        return;
  
      SILFunction *F = V->getFunction();
      assert(F && "Expected value base with parent function");
      // If we do not have qualified ownership, then do not verify value base
      // ownership.
      if (!F->hasOwnership())
        return;
      SILValue(V).verifyOwnership(&DEBlocks);
    }
  
    void checkSILInstruction(SILInstruction *I) {
      const SILBasicBlock *BB = I->getParent();
      require(BB, "Instruction with null parent");
  
      // Check that non-terminators look ok.
      if (!isa<TermInst>(I)) {
        require(!BB->empty(), "Can't be in a parent block if it is empty");
        if (!I->isStaticInitializerInst()) {
          require(&*BB->rbegin() != I,
                  "Non-terminators cannot be the last in a block");
        }
      } else {
        // Skip the check for UnreachableInst, if explicitly asked to do so.
        if (!isa<UnreachableInst>(I) || !SkipUnreachableMustBeLastErrors)
          require(&*BB->rbegin() == I,
                  "Terminator must be the last in block");
      }
  
      // Verify that all of our uses are in this function.
      for (auto result : I->getResults()) {
        for (Operand *use : result->getUses()) {
          auto user = use->getUser();
          require(user, "instruction user is null?");
          require(isa<SILInstruction>(user),
                  "instruction used by non-instruction");
          auto userI = cast<SILInstruction>(user);
          require(userI->getParent(),
                  "instruction used by unparented instruction");
          if (I->isStaticInitializerInst()) {
            require(userI->getParent() == BB,
                  "instruction used by instruction not in same static initializer");
          } else {
            require(userI->getFunction() == &F,
                    "instruction used by instruction in different function");
          }
  
          auto operands = userI->getAllOperands();
          require(operands.begin() <= use && use <= operands.end(),
                  "use doesn't actually belong to instruction it claims to");
        }
      }
  
      // Verify some basis structural stuff about an instruction's operands.
      for (auto &operand : I->getAllOperands()) {
        require(operand.get(), "instruction has null operand");
  
        if (auto *valueI = operand.get()->getDefiningInstruction()) {
          require(valueI->getParent(),
                  "instruction uses value of unparented instruction");
          if (I->isStaticInitializerInst()) {
            require(valueI->getParent() == BB,
                "instruction uses value which is not in same static initializer");
          } else {
            require(valueI->getFunction() == &F,
                    "instruction uses value of instruction from another function");
            require(properlyDominates(valueI, I),
                    "instruction isn't dominated by its operand");
          }
        }
        
        if (auto *valueBBA = dyn_cast<SILArgument>(operand.get())) {
          require(!I->isStaticInitializerInst(),
                  "static initializer inst cannot refer to SILArgument");
          require(valueBBA->getParent(),
                  "instruction uses value of unparented instruction");
          require(valueBBA->getFunction() == &F,
                  "bb argument value from another function");
          require(Dominance->dominates(valueBBA->getParent(), I->getParent()),
                  "instruction isn't dominated by its bb argument operand");
        }
  
        require(operand.getUser() == I,
                "instruction's operand's owner isn't the instruction");
        require(isInValueUses(&operand), "operand value isn't used by operand");
  
        if (I->isTypeDependentOperand(operand)) {
          require(isa<SILInstruction>(I),
                 "opened archetype operand should refer to a SILInstruction");
        }
  
        // Make sure that if operand is generic that its primary archetypes match
        // the function context.
        checkLegalType(I->getFunction(), operand.get(), I);
      }
  
      // TODO: There should be a use of an opened archetype inside the instruction for
      // each opened archetype operand of the instruction.
    }
  
    void checkInstructionsSILLocation(SILInstruction *I) {
      // Check the debug scope.
      auto *DS = I->getDebugScope();
      if (DS && !maybeScopeless(*I))
        require(DS, "instruction has a location, but no scope");
  
      require(!DS || DS->getParentFunction() == I->getFunction(),
              "debug scope of instruction belongs to a different function");
  
      // Check the location kind.
      SILLocation L = I->getLoc();
      SILLocation::LocationKind LocKind = L.getKind();
      SILInstructionKind InstKind = I->getKind();
  
      // Check that there is at most one debug variable defined
      // for each argument slot. This catches SIL transformations
      // that accidentally remove inline information (stored in the SILDebugScope)
      // from debug-variable-carrying instructions.
      if (!DS->InlinedCallSite) {
        Optional<SILDebugVariable> VarInfo;
        if (auto *DI = dyn_cast<AllocStackInst>(I))
          VarInfo = DI->getVarInfo();
        else if (auto *DI = dyn_cast<AllocBoxInst>(I))
          VarInfo = DI->getVarInfo();
        else if (auto *DI = dyn_cast<DebugValueInst>(I))
          VarInfo = DI->getVarInfo();
        else if (auto *DI = dyn_cast<DebugValueAddrInst>(I))
          VarInfo = DI->getVarInfo();
  
        if (VarInfo)
          if (unsigned ArgNo = VarInfo->ArgNo) {
            // It is a function argument.
            if (ArgNo < DebugVars.size() && !DebugVars[ArgNo].empty()) {
              require(
                  DebugVars[ArgNo] == VarInfo->Name,
                  "Scope contains conflicting debug variables for one function "
                  "argument");
            } else {
              // Reserve enough space.
              while (DebugVars.size() <= ArgNo) {
                DebugVars.push_back(StringRef());
              }
            }
            DebugVars[ArgNo] = VarInfo->Name;
        }
      }
  
      // Regular locations are allowed on all instructions.
      if (LocKind == SILLocation::RegularKind)
        return;
  
      if (LocKind == SILLocation::ReturnKind ||
          LocKind == SILLocation::ImplicitReturnKind)
        require(InstKind == SILInstructionKind::BranchInst ||
                InstKind == SILInstructionKind::ReturnInst ||
                InstKind == SILInstructionKind::UnreachableInst,
          "return locations are only allowed on branch and return instructions");
  
      if (LocKind == SILLocation::ArtificialUnreachableKind)
        require(InstKind == SILInstructionKind::UnreachableInst,
          "artificial locations are only allowed on Unreachable instructions");
    }
  
    /// Check that the types of this value producer are all legal in the function
    /// context in which it exists.
    void checkLegalType(SILFunction *F, ValueBase *value, SILInstruction *I) {
      SILType type = value->getType();
      if (type.is<SILTokenType>()) {
        require(isLegalSILTokenProducer(value),
                "SIL tokens can only be produced as the results of specific "
                "instructions");
        return;
      }
  
      checkLegalType(F, type, I);
    }
  
    static bool isLegalSILTokenProducer(SILValue value) {
      if (auto beginApply = dyn_cast<BeginApplyResult>(value))
        return beginApply->isTokenResult();
  
      // Add more token cases here as they arise.
  
      return false;
    }
  
    /// Check that the given type is a legal SIL value type.
    void checkLegalType(SILFunction *F, SILType type, SILInstruction *I) {
      checkLegalSILType(F, type.getASTType(), I);
    }
  
    /// Check that the given type is a legal SIL value type.
    void checkLegalSILType(SILFunction *F, CanType rvalueType, SILInstruction *I) {
      // These types should have been removed by lowering.
      require(!isa<LValueType>(rvalueType),
              "l-value types are not legal in SIL");
      require(!isa<AnyFunctionType>(rvalueType),
              "AST function types are not legal in SIL");
  
      // Tuples should have had their element lowered.
      if (auto tuple = dyn_cast<TupleType>(rvalueType)) {
        for (auto eltTy : tuple.getElementTypes()) {
          checkLegalSILType(F, eltTy, I);
        }
        return;
      }
  
      // Optionals should have had their objects lowered.
      if (auto objectType = rvalueType.getOptionalObjectType()) {
        return checkLegalSILType(F, objectType, I);
      }
  
      // Metatypes should have explicit representations.
      if (auto metatype = dyn_cast<AnyMetatypeType>(rvalueType)) {
        require(metatype->hasRepresentation(),
                "metatypes in SIL must have a representation");;
        // fallthrough for archetype check
      }
  
      rvalueType.visit([&](CanType t) {
        auto A = dyn_cast<ArchetypeType>(t);
        if (!A)
          return;
        require(isArchetypeValidInFunction(A, F),
                "Operand is of an ArchetypeType that does not exist in the "
                "Caller's generic param list.");
        if (auto OpenedA = getOpenedArchetypeOf(A)) {
          auto Def = OpenedArchetypes.getOpenedArchetypeDef(OpenedA);
          require (Def, "Opened archetype should be registered in SILFunction");
          require(I == nullptr || Def == I ||
                  properlyDominates(cast<SILInstruction>(Def), I),
                  "Use of an opened archetype should be dominated by a "
                  "definition of this opened archetype");
        }
      });
    }
  
    /// Check that this operand appears in the use-chain of the value it uses.
    static bool isInValueUses(const Operand *operand) {
      for (auto use : operand->get()->getUses())
        if (use == operand)
          return true;
      return false;
    }
  
    /// \return True if all of the users of the AllocStack instruction \p ASI are
    /// inside the same basic block.
    static bool isSingleBlockUsage(AllocStackInst *ASI, DominanceInfo *Dominance){
      SILBasicBlock *BB = ASI->getParent();
      for (auto UI = ASI->use_begin(), E = ASI->use_end(); UI != E; ++UI)
        if (UI->getUser()->getParent() != BB &&
            Dominance->isReachableFromEntry(UI->getUser()->getParent()))
          return false;
  
      return true;
    }
  
    void checkAllocStackInst(AllocStackInst *AI) {
      require(AI->getType().isAddress(),
              "result of alloc_stack must be an address type");
  
      verifyOpenedArchetype(AI, AI->getElementType().getASTType());
  
      // There used to be a check if all uses of ASI are inside the alloc-dealloc
      // range. But apparently it can be the case that ASI has uses after the
      // dealloc_stack. This can come up if the source contains a
      // withUnsafePointer where the pointer escapes.
      // It's illegal code but the compiler should not crash on it.
    }
  
    void checkAllocRefBase(AllocRefInstBase *ARI) {
      requireReferenceValue(ARI, "Result of alloc_ref");
      verifyOpenedArchetype(ARI, ARI->getType().getASTType());
      auto Types = ARI->getTailAllocatedTypes();
      auto Counts = ARI->getTailAllocatedCounts();
      unsigned NumTypes = Types.size();
      require(NumTypes == Counts.size(), "Mismatching types and counts");
      require(NumTypes == 0 || !ARI->isObjC(),
              "Can't tail allocate with ObjC class");
      for (unsigned Idx = 0; Idx < NumTypes; ++Idx) {
        verifyOpenedArchetype(ARI, Types[Idx].getASTType());
        require(Counts[Idx].get()->getType().is<BuiltinIntegerType>(),
                "count needs integer type");
      }
    }
  
    void checkAllocRefInst(AllocRefInst *AI) {
      require(AI->isObjC() || AI->getType().getClassOrBoundGenericClass(),
              "alloc_ref must allocate class");
      checkAllocRefBase(AI);
    }
  
    void checkAllocRefDynamicInst(AllocRefDynamicInst *ARDI) {
      SILValue Metadata = ARDI->getMetatypeOperand();
      require(Metadata->getType().is<AnyMetatypeType>(),
              "operand of alloc_ref_dynamic must be of metatype type");
      auto metaTy = Metadata->getType().castTo<AnyMetatypeType>();
      require(metaTy->hasRepresentation(),
              "operand of alloc_ref_dynamic must have a metatype representation");
      if (ARDI->isObjC()) {
        require(metaTy->getRepresentation() == MetatypeRepresentation::ObjC,
                "alloc_ref_dynamic @objc requires operand of ObjC metatype");
      } else {
        require(metaTy->getRepresentation() == MetatypeRepresentation::Thick,
                "alloc_ref_dynamic requires operand of thick metatype");
      }
      checkAllocRefBase(ARDI);
    }
  
    /// Check the substitutions passed to an apply or partial_apply.
    CanSILFunctionType checkApplySubstitutions(SubstitutionMap subs,
                                               SILType calleeTy) {
      auto fnTy = requireObjectType(SILFunctionType, calleeTy, "callee operand");
  
      // If there are substitutions, verify them and apply them to the callee.
      if (!subs.hasAnySubstitutableParams()) {
        require(!fnTy->isPolymorphic(),
                "callee of apply without substitutions must not be polymorphic");
        return fnTy;
      }
      require(fnTy->isPolymorphic(),
              "callee of apply with substitutions must be polymorphic");
  
      // Each archetype occurring in the substitutions list should belong to the
      // current function.
      for (auto replacementType : subs.getReplacementTypes()) {
        replacementType->getCanonicalType().visit([&](CanType t) {
          auto A = dyn_cast<ArchetypeType>(t);
          if (!A)
            return;
          require(isArchetypeValidInFunction(A, &F),
                  "Replacement type of a substitution contains an ArchetypeType "
                  "that does not exist in the Caller's generic param list.");
        });
      }
  
      // Apply the substitutions.
      return fnTy->substGenericArgs(F.getModule(), subs);
    }
  
    /// Check that for each opened archetype or dynamic self type in substitutions
    /// or the calle type, there is a type dependent operand.
    void checkApplyTypeDependentArguments(ApplySite AS) {
      SILInstruction *AI = AS.getInstruction();
  
      llvm::DenseSet<ArchetypeType *> FoundOpenedArchetypes;
      unsigned hasDynamicSelf = 0;
  
      // Function to collect opened archetypes in FoundOpenedArchetypes and set
      // hasDynamicSelf.
      auto HandleType = [&](CanType Ty) {
        if (Ty->isOpenedExistential()) {
          auto A = cast<ArchetypeType>(Ty);
          require(isArchetypeValidInFunction(A, AI->getFunction()),
                  "Archetype to be substituted must be valid in function.");
          // Collect all opened archetypes used in the substitutions list.
          FoundOpenedArchetypes.insert(A);
          // Also check that they are properly tracked inside the current
          // function.
          auto Def = OpenedArchetypes.getOpenedArchetypeDef(A);
          require(Def, "Opened archetype should be registered in SILFunction");
          require(Def == AI ||
                  properlyDominates(cast<SILInstruction>(Def), AI),
                  "Use of an opened archetype should be dominated by a "
                  "definition of this opened archetype");
        }
        if (Ty->hasDynamicSelfType()) {
          hasDynamicSelf = 1;
        }
      };
  
      // Search for opened archetypes and dynamic self.
      for (auto Replacement : AS.getSubstitutionMap().getReplacementTypes()) {
        Replacement->getCanonicalType().visit(HandleType);
      }
      AS.getSubstCalleeType().visit(HandleType);
  
      require(FoundOpenedArchetypes.size() + hasDynamicSelf ==
                  AI->getTypeDependentOperands().size(),
              "Number of opened archetypes and dynamic self in the substitutions "
              "list should match the number of type dependent operands");
  
      for (auto &Op : AI->getTypeDependentOperands()) {
        auto V = Op.get();
        if (isa<SILArgument>(V)) {
          require(hasDynamicSelf,
                  "dynamic self operand without dynamic self type");
          require(AI->getFunction()->hasSelfMetadataParam(),
                  "self metadata operand in function without self metadata param");
          require((ValueBase *)V == AI->getFunction()->getSelfMetadataArgument(),
                  "wrong self metadata operand");
        } else {
          require(isa<SingleValueInstruction>(V),
                  "opened archetype operand should refer to a SIL instruction");
          auto Archetype = getOpenedArchetypeOf(cast<SingleValueInstruction>(V));
          require(Archetype,
                  "opened archetype operand should define an opened archetype");
          require(FoundOpenedArchetypes.count(Archetype),
                  "opened archetype operand does not correspond to any opened "
                  "archetype from the substitutions list");
        }
      }
    }
  
    void checkFullApplySite(FullApplySite site) {
      checkApplyTypeDependentArguments(site);
  
      // Then make sure that we have a type that can be substituted for the
      // callee.
      auto substTy = checkApplySubstitutions(site.getSubstitutionMap(),
                                             site.getCallee()->getType());
      require(site.getOrigCalleeType()->getRepresentation() ==
              site.getSubstCalleeType()->getRepresentation(),
              "calling convention difference between types");
  
      require(!site.getSubstCalleeType()->isPolymorphic(),
              "substituted callee type should not be generic");
  
      requireSameType(SILType::getPrimitiveObjectType(substTy),
                      SILType::getPrimitiveObjectType(site.getSubstCalleeType()),
              "substituted callee type does not match substitutions");
  
      // Check that the arguments and result match.
      SILFunctionConventions substConv(substTy, F.getModule());
      //require(site.getArguments().size() == substTy->getNumSILArguments(),
      require(site.getNumArguments() == substConv.getNumSILArguments(),
              "apply doesn't have right number of arguments for function");
      for (size_t i = 0, size = site.getNumArguments(); i < size; ++i) {
        requireSameType(site.getArguments()[i]->getType(),
                        substConv.getSILArgumentType(i),
                        "operand of 'apply' doesn't match function input type");
      }
    }
  
    void checkApplyInst(ApplyInst *AI) {
      checkFullApplySite(AI);
  
      SILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());
      require(AI->getType() == calleeConv.getSILResultType(),
              "type of apply instruction doesn't match function result type");
      if (AI->isNonThrowing()) {
        require(calleeConv.funcTy->hasErrorResult(),
                "nothrow flag used for callee without error result");
      } else {
        require(!calleeConv.funcTy->hasErrorResult(),
                "apply instruction cannot call function with error result");
      }
  
      require(!calleeConv.funcTy->isCoroutine(),
              "cannot call coroutine with normal apply");
  
      // Check that if the apply is of a noreturn callee, make sure that an
      // unreachable is the next instruction.
      if (AI->getModule().getStage() == SILStage::Raw ||
          !AI->isCalleeNoReturn())
        return;
      require(isa<UnreachableInst>(std::next(SILBasicBlock::iterator(AI))),
              "No return apply without an unreachable as a next instruction.");
    }
  
    void checkTryApplyInst(TryApplyInst *AI) {
      checkFullApplySite(AI);
  
      SILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());
  
      require(!calleeConv.funcTy->isCoroutine(),
              "cannot call coroutine with normal apply");
  
      auto normalBB = AI->getNormalBB();
      require(normalBB->args_size() == 1,
              "normal destination of try_apply must take one argument");
      requireSameType((*normalBB->args_begin())->getType(),
                      calleeConv.getSILResultType(),
                      "normal destination of try_apply must take argument "
                      "of normal result type");
  
      auto errorBB = AI->getErrorBB();
      require(calleeConv.funcTy->hasErrorResult(),
              "try_apply must call function with error result");
      require(errorBB->args_size() == 1,
              "error destination of try_apply must take one argument");
      requireSameType((*errorBB->args_begin())->getType(),
                      calleeConv.getSILErrorType(),
                      "error destination of try_apply must take argument "
                      "of error result type");
    }
  
    void checkBeginApplyInst(BeginApplyInst *AI) {
      checkFullApplySite(AI);
  
      SILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());
      auto yieldResults = AI->getYieldedValues();
      auto yields = calleeConv.getYields();
      require(yields.size() == yieldResults.size(),
              "length mismatch in callee yields vs. begin_apply results");
      for (auto i : indices(yields)) {
        require(yieldResults[i]->getType() == calleeConv.getSILType(yields[i]),
                "callee yield type does not match begin_apply result type");
      }
  
      if (AI->isNonThrowing()) {
        require(calleeConv.funcTy->hasErrorResult(),
                "nothrow flag used for callee without error result");
      } else {
        require(!calleeConv.funcTy->hasErrorResult(),
                "begin_apply instruction cannot call function with error result");
      }
  
      require(calleeConv.funcTy->getCoroutineKind() == SILCoroutineKind::YieldOnce,
              "must call yield_once coroutine with begin_apply");
    }
  
    void checkAbortApplyInst(AbortApplyInst *AI) {
      require(isa<BeginApplyResult>(AI->getOperand()) &&
              cast<BeginApplyResult>(AI->getOperand())->isTokenResult(),
              "operand of abort_apply must be a begin_apply");
    }
  
    void checkEndApplyInst(EndApplyInst *AI) {
      require(isa<BeginApplyResult>(AI->getOperand()) &&
              cast<BeginApplyResult>(AI->getOperand())->isTokenResult(),
              "operand of end_apply must be a begin_apply");
    }
  
    void verifyLLVMIntrinsic(BuiltinInst *BI, llvm::Intrinsic::ID ID) {
      // Certain llvm intrinsic require constant values as their operands.
      // Consequently, these must not be phi nodes (aka. basic block arguments).
      switch (ID) {
      default:
        break;
      case llvm::Intrinsic::ctlz: // llvm.ctlz
      case llvm::Intrinsic::cttz: // llvm.cttz
        break;
      case llvm::Intrinsic::memcpy:
      case llvm::Intrinsic::memmove:
      case llvm::Intrinsic::memset:
        require(!isa<SILArgument>(BI->getArguments()[3]),
                "isvolatile argument of memory intrinsics must be an integer "
                "literal");
        break;
      case llvm::Intrinsic::lifetime_start:
      case llvm::Intrinsic::lifetime_end:
      case llvm::Intrinsic::invariant_start:
        require(!isa<SILArgument>(BI->getArguments()[0]),
                "size argument of memory use markers must be an integer literal");
        break;
      case llvm::Intrinsic::invariant_end:
        require(!isa<SILArgument>(BI->getArguments()[1]),
                "llvm.invariant.end parameter #2 must be an integer literal");
        break;
      }
    }
  
    void checkPartialApplyInst(PartialApplyInst *PAI) {
      auto resultInfo = requireObjectType(SILFunctionType, PAI,
                                          "result of partial_apply");
      verifySILFunctionType(resultInfo);
      require(resultInfo->getExtInfo().hasContext(),
              "result of closure cannot have a thin function type");
  
      checkApplyTypeDependentArguments(PAI);
  
      auto substTy = checkApplySubstitutions(PAI->getSubstitutionMap(),
                                          PAI->getCallee()->getType());
  
      require(!PAI->getSubstCalleeType()->isPolymorphic(),
              "substituted callee type should not be generic");
  
      requireSameType(SILType::getPrimitiveObjectType(substTy),
                      SILType::getPrimitiveObjectType(PAI->getSubstCalleeType()),
              "substituted callee type does not match substitutions");
  
      // The arguments must match the suffix of the original function's input
      // types.
      require(PAI->getArguments().size() +
                resultInfo->getParameters().size()
                == substTy->getParameters().size(),
              "result of partial_apply should take as many inputs as were not "
              "applied by the instruction");
  
      SILFunctionConventions substConv(substTy, F.getModule());
      unsigned appliedArgStartIdx =
          substConv.getNumSILArguments() - PAI->getNumArguments();
      for (unsigned i = 0, size = PAI->getArguments().size(); i < size; ++i) {
        require(PAI->getArguments()[i]->getType()
                    == substConv.getSILArgumentType(appliedArgStartIdx + i),
                "applied argument types do not match suffix of function type's "
                "inputs");
      }
  
      // The arguments to the result function type must match the prefix of the
      // original function's input types.
      for (unsigned i = 0, size = resultInfo->getParameters().size();
           i < size; ++i) {
        require(resultInfo->getParameters()[i] ==
                substTy->getParameters()[i],
                "inputs to result function type do not match unapplied inputs "
                "of original function");
      }
  
      require(resultInfo->getNumResults() == substTy->getNumResults(),
              "applied results do not agree in count with function type");
      for (unsigned i = 0, size = resultInfo->getNumResults(); i < size; ++i) {
        auto originalResult = resultInfo->getResults()[i];
        auto expectedResult = substTy->getResults()[i];
  
        // The "returns inner pointer" convention doesn't survive through a
        // partial application, since the thunk takes responsibility for
        // lifetime-extending 'self'.
        if (expectedResult.getConvention()
              == ResultConvention::UnownedInnerPointer) {
          expectedResult = SILResultInfo(expectedResult.getType(),
                                         ResultConvention::Unowned);
          require(originalResult == expectedResult,
                  "result type of result function type for partially applied "
                  "@unowned_inner_pointer function should have @unowned"
                  "convention");
  
        // The "autoreleased" convention doesn't survive through a
        // partial application, since the thunk takes responsibility for
        // retaining the return value.
        } else if (expectedResult.getConvention()
              == ResultConvention::Autoreleased) {
          expectedResult = SILResultInfo(expectedResult.getType(),
                                         ResultConvention::Owned);
          require(originalResult == expectedResult,
                  "result type of result function type for partially applied "
                  "@autoreleased function should have @owned convention");
  
        } else {
          require(originalResult == expectedResult,
                  "result type of result function type does not match original "
                  "function");
        }
      }
      
      // TODO: Impose additional constraints when partial_apply when the
      // -disable-sil-partial-apply flag is enabled. We want to reduce
      // partial_apply to being only a means of associating a closure invocation
      // function with its context.
      //
      // When we reach that point, we should be able to more deeply redesign
      // PartialApplyInst to simplify the representation to carry a single
      // argument.
      if (PAI->getModule().getOptions().DisableSILPartialApply) {
        // Should only be one context argument.
        require(PAI->getArguments().size() == 1,
                "partial_apply should have a single context argument");
        
        // Callee should already have the thin convention, and result should be
        // thick.
        require(resultInfo->getRepresentation() ==
                  SILFunctionTypeRepresentation::Thick,
                "partial_apply result should have thick convention");
        require(PAI->getCallee()->getType().castTo<SILFunctionType>()
                  ->getRepresentation() ==
                SILFunctionTypeRepresentation::Thin,
                "partial_apply callee should have thin convention");
        
        // TODO: Check that generic signature matches box's generic signature,
        // once we have boxes with generic signatures.
        require(!PAI->getCalleeFunction()->getGenericEnvironment(),
                "partial_apply context must capture generic environment for "
                "callee");
        
        // Result's callee convention should match context argument's convention.
        require(substTy->getParameters().back().getConvention()
                  == resultInfo->getCalleeConvention(),
                "partial_apply context argument must have the same convention "
                "as the resulting function's callee convention");
        
        auto isSwiftRefcounted = [](SILType t) -> bool {
          if (t.is<SILBoxType>())
            return true;
          if (t.getASTType() == t.getASTContext().TheNativeObjectType)
            return true;
          if (auto clas = t.getClassOrBoundGenericClass())
            // Must be a class defined in Swift.
            return clas->hasKnownSwiftImplementation();
          return false;
        };
        
        // The context argument must be a swift-refcounted box or class.
        require(isSwiftRefcounted(PAI->getArguments().front()->getType()),
                "partial_apply context argument must be swift-refcounted");
      }
    }
  
    void checkBuiltinInst(BuiltinInst *BI) {
      // Check for special constraints on llvm intrinsics.
      if (BI->getIntrinsicInfo().ID != llvm::Intrinsic::not_intrinsic)
        verifyLLVMIntrinsic(BI, BI->getIntrinsicInfo().ID);
    }
    
    void checkFunctionRefBaseInst(FunctionRefBaseInst *FRI) {
      auto fnType = requireObjectType(SILFunctionType, FRI,
                                      "result of function_ref");
      require(!fnType->getExtInfo().hasContext(),
              "function_ref should have a context-free function result");
  
      // Note: in SingleFunction mode, we relax some of these checks because
      // we may not have linked everything yet.
  
      SILFunction *RefF = FRI->getInitiallyReferencedFunction();
  
      if (isa<FunctionRefInst>(FRI))
        require(
            !RefF->isDynamicallyReplaceable(),
            "function_ref cannot reference a [dynamically_replaceable] function");
      else if (isa<PreviousDynamicFunctionRefInst>(FRI)) {
        require(!RefF->isDynamicallyReplaceable(),
                "previous_function_ref cannot reference a "
                "[dynamically_replaceable] function");
        require(RefF->getDynamicallyReplacedFunction(),
                "previous_function_ref must reference a "
                "[dynamic_replacement_for:...] function");
      } else if (isa<DynamicFunctionRefInst>(FRI))
        require(RefF->isDynamicallyReplaceable(),
                "dynamic_function_ref must reference a "
                "[dynamically_replaceable] function");
  
      // In canonical SIL, direct reference to a shared_external declaration
      // is an error; we should have deserialized a body. In raw SIL, we may
      // not have deserialized the body yet.
      if (F.getModule().getStage() >= SILStage::Canonical) {
        if (RefF->isExternalDeclaration()) {
          require(SingleFunction ||
                  !hasSharedVisibility(RefF->getLinkage()) ||
                  RefF->hasForeignBody(),
                  "external declarations of SILFunctions with shared visibility is "
                  "not allowed");
        }
      }
  
      // A direct reference to a non-public or shared but not fragile function
      // from a fragile function is an error.
      if (F.isSerialized()) {
        require((SingleFunction && RefF->isExternalDeclaration()) ||
                RefF->hasValidLinkageForFragileRef(),
                "function_ref inside fragile function cannot "
                "reference a private or hidden symbol");
      }
  
      verifySILFunctionType(fnType);
    }
  
    void checkFunctionRefInst(FunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
    }
  
    void checkDynamicFunctionRefInst(DynamicFunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
    }
  
    void checkPreviousDynamicFunctionRefInst(PreviousDynamicFunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
    }
  
    void checkAllocGlobalInst(AllocGlobalInst *AGI) {
      SILGlobalVariable *RefG = AGI->getReferencedGlobal();
      if (auto *VD = RefG->getDecl()) {
        require(!VD->isResilient(F.getModule().getSwiftModule(),
                                 F.getResilienceExpansion()),
                "cannot access storage of resilient global");
      }
      if (F.isSerialized()) {
        require(RefG->isSerialized()
                  || hasPublicVisibility(RefG->getLinkage()),
                "alloc_global inside fragile function cannot "
                "reference a private or hidden symbol");
      }
    }
  
    void checkGlobalAccessInst(GlobalAccessInst *GAI) {
      SILGlobalVariable *RefG = GAI->getReferencedGlobal();
      require(GAI->getType().getObjectType() == RefG->getLoweredType(),
              "global_addr/value must be the type of the variable it references");
      if (auto *VD = RefG->getDecl()) {
        require(!VD->isResilient(F.getModule().getSwiftModule(),
                                 F.getResilienceExpansion()),
                "cannot access storage of resilient global");
      }
      if (F.isSerialized()) {
        require(RefG->isSerialized()
                || hasPublicVisibility(RefG->getLinkage()),
                "global_addr/value inside fragile function cannot "
                "reference a private or hidden symbol");
      }
    }
  
    void checkGlobalAddrInst(GlobalAddrInst *GAI) {
      require(GAI->getType().isAddress(),
              "global_addr must have an address result type");
      require(!GAI->getReferencedGlobal()->isInitializedObject(),
              "global_addr cannot refer to a statically initialized object");
      checkGlobalAccessInst(GAI);
    }
  
    void checkGlobalValueInst(GlobalValueInst *GVI) {
      require(GVI->getType().isObject(),
              "global_value must have an address result type");
      checkGlobalAccessInst(GVI);
    }
  
    void checkObjectInst(ObjectInst *) {
      require(false, "object instruction is only allowed in a static initializer");
    }
  
    void checkIntegerLiteralInst(IntegerLiteralInst *ILI) {
      require(ILI->getType().is<AnyBuiltinIntegerType>(),
              "invalid integer literal type");
    }
  
    void checkLoadInst(LoadInst *LI) {
      require(LI->getType().isObject(), "Result of load must be an object");
      require(!fnConv.useLoweredAddresses()
                  || LI->getType().isLoadable(*LI->getFunction()),
              "Load must have a loadable type");
      require(LI->getOperand()->getType().isAddress(),
              "Load operand must be an address");
      require(LI->getOperand()->getType().getObjectType() == LI->getType(),
              "Load operand type and result type mismatch");
  
      // Ownership semantic checks.
      switch (LI->getOwnershipQualifier()) {
      case LoadOwnershipQualifier::Unqualified:
        // We should not see loads with unqualified ownership when SILOwnership is
        // enabled.
        require(!F.hasOwnership(),
                "Load with unqualified ownership in a qualified function");
        break;
      case LoadOwnershipQualifier::Copy:
      case LoadOwnershipQualifier::Take:
        require(F.hasOwnership(),
                "Load with qualified ownership in an unqualified function");
        // TODO: Could probably make this a bit stricter.
        require(!LI->getType().isTrivial(*LI->getFunction()),
                "load [copy] or load [take] can only be applied to non-trivial "
                "types");
        break;
      case LoadOwnershipQualifier::Trivial:
        require(F.hasOwnership(),
                "Load with qualified ownership in an unqualified function");
        require(LI->getType().isTrivial(*LI->getFunction()),
                "A load with trivial ownership must load a trivial type");
        break;
      }
    }
  
    void checkLoadBorrowInst(LoadBorrowInst *LBI) {
      require(
          F.hasOwnership(),
          "Inst with qualified ownership in a function that is not qualified");
      require(LBI->getType().isObject(), "Result of load must be an object");
      require(!fnConv.useLoweredAddresses()
              || LBI->getType().isLoadable(*LBI->getFunction()),
              "Load must have a loadable type");
      require(LBI->getOperand()->getType().isAddress(),
              "Load operand must be an address");
      require(LBI->getOperand()->getType().getObjectType() == LBI->getType(),
              "Load operand type and result type mismatch");
    }
  
    void checkEndBorrowInst(EndBorrowInst *EBI) {
      require(
          F.hasOwnership(),
          "Inst with qualified ownership in a function that is not qualified");
    }
  
    template <class AI>
    void checkAccessEnforcement(AI *AccessInst) {
      if (AccessInst->getModule().getStage() != SILStage::Raw) {
        require(AccessInst->getEnforcement() != SILAccessEnforcement::Unknown,
                "access must have known enforcement outside raw stage");
      }
    }
  
    void checkBeginAccessInst(BeginAccessInst *BAI) {
      requireSameType(BAI->getType(), BAI->getSource()->getType(),
                      "result must be same type as operand");
      require(BAI->getType().isAddress(),
              "begin_access operand must have address type");
  
      checkAccessEnforcement(BAI);
  
      switch (BAI->getAccessKind()) {
      case SILAccessKind::Init:
      case SILAccessKind::Deinit:
        require(BAI->getEnforcement() == SILAccessEnforcement::Static,
                "init/deinit accesses cannot use non-static enforcement");
        break;
  
      case SILAccessKind::Read:
      case SILAccessKind::Modify:
        break;
      }
  
      // Verify that all formal accesses patterns are recognized as part of a
      // whitelist. The presence of an unknown pattern means that analysis will
      // silently fail, and the compiler may be introducing undefined behavior
      // with no other way to detect it.
      //
      // For example, AccessEnforcementWMO runs very late in the
      // pipeline and assumes valid storage for all dynamic Read/Modify access. It
      // also requires that Unidentified access fit a whitelist on known
      // non-internal globals or class properties.
      //
      // First check that findAccessedStorage returns without asserting. For
      // Unsafe enforcement, that is sufficient. For any other enforcement
      // level also require that it returns a valid AccessedStorage object.
      // Unsafe enforcement is used for some unrecognizable access patterns,
      // like debugger variables. The compiler never cares about the source of
      // those accesses.
      AccessedStorage storage = findAccessedStorage(BAI->getSource());
      if (BAI->getEnforcement() != SILAccessEnforcement::Unsafe)
        require(storage, "Unknown formal access pattern");
    }
  
    void checkEndAccessInst(EndAccessInst *EAI) {
      auto BAI = dyn_cast<BeginAccessInst>(EAI->getOperand());
      require(BAI != nullptr,
              "operand of end_access must be a begin_access");
  
      if (EAI->isAborting()) {
        require(BAI->getAccessKind() == SILAccessKind::Init ||
                BAI->getAccessKind() == SILAccessKind::Deinit,
                "aborting access must apply to init or deinit");
      }
    }
  
    void checkBeginUnpairedAccessInst(BeginUnpairedAccessInst *BUAI) {
      require(BUAI->getEnforcement() != SILAccessEnforcement::Unknown,
              "unpaired access can never use unknown enforcement");
      require(BUAI->getSource()->getType().isAddress(),
              "address operand must have address type");
      requireAddressType(BuiltinUnsafeValueBufferType, BUAI->getBuffer(),
                         "scratch buffer operand");
  
      checkAccessEnforcement(BUAI);
  
      switch (BUAI->getAccessKind()) {
      case SILAccessKind::Init:
      case SILAccessKind::Deinit:
        require(BUAI->getEnforcement() == SILAccessEnforcement::Static,
                "init/deinit accesses cannot use non-static enforcement");
        break;
      case SILAccessKind::Read:
      case SILAccessKind::Modify:
        break;
      }
  
      // First check that findAccessedStorage never asserts.
      AccessedStorage storage = findAccessedStorage(BUAI->getSource());
      // Only allow Unsafe and Builtin access to have invalid storage.
      if (BUAI->getEnforcement() != SILAccessEnforcement::Unsafe
          && !BUAI->isFromBuiltin()) {
        require(storage, "Unknown formal access pattern");
      }
    }
  
    void checkEndUnpairedAccessInst(EndUnpairedAccessInst *I) {
      require(I->getEnforcement() != SILAccessEnforcement::Unknown,
              "unpaired access can never use unknown enforcement");
      requireAddressType(BuiltinUnsafeValueBufferType, I->getBuffer(),
                         "scratch buffer operand");
  
      checkAccessEnforcement(I);
    }
  
    void checkStoreInst(StoreInst *SI) {
      require(SI->getSrc()->getType().isObject(),
              "Can't store from an address source");
      require(!fnConv.useLoweredAddresses()
                  || SI->getSrc()->getType().isLoadable(*SI->getFunction()),
              "Can't store a non loadable type");
      require(SI->getDest()->getType().isAddress(),
              "Must store to an address dest");
      require(SI->getDest()->getType().getObjectType() == SI->getSrc()->getType(),
              "Store operand type and dest type mismatch");
  
      // Perform ownership checks.
      switch (SI->getOwnershipQualifier()) {
      case StoreOwnershipQualifier::Unqualified:
        // We should not see loads with unqualified ownership when SILOwnership is
        // enabled.
        require(!F.hasOwnership(),
                "Qualified store in function with unqualified ownership?!");
        break;
      case StoreOwnershipQualifier::Init:
      case StoreOwnershipQualifier::Assign:
        require(
            F.hasOwnership(),
            "Inst with qualified ownership in a function that is not qualified");
        // TODO: Could probably make this a bit stricter.
        require(!SI->getSrc()->getType().isTrivial(*SI->getFunction()),
                "store [init] or store [assign] can only be applied to "
                "non-trivial types");
        break;
      case StoreOwnershipQualifier::Trivial: {
        require(
            F.hasOwnership(),
            "Inst with qualified ownership in a function that is not qualified");
        SILValue Src = SI->getSrc();
        require(Src->getType().isTrivial(*SI->getFunction()) ||
                Src.getOwnershipKind() == ValueOwnershipKind::Any,
                "A store with trivial ownership must store a type with trivial "
                "ownership");
        break;
      }
      }
    }
  
    void checkAssignInst(AssignInst *AI) {
      SILValue Src = AI->getSrc(), Dest = AI->getDest();
      require(AI->getModule().getStage() == SILStage::Raw,
              "assign instruction can only exist in raw SIL");
      require(Src->getType().isObject(), "Can't assign from an address source");
      require(Dest->getType().isAddress(), "Must store to an address dest");
      require(Dest->getType().getObjectType() == Src->getType(),
              "Store operand type and dest type mismatch");
    }
  
    void checkAssignByWrapperInst(AssignByWrapperInst *AI) {
      SILValue Src = AI->getSrc(), Dest = AI->getDest();
      require(AI->getModule().getStage() == SILStage::Raw,
              "assign instruction can only exist in raw SIL");
      require(Dest->getType().isAddress(), "Must store to an address dest");
  
      SILValue initFn = AI->getInitializer();
      CanSILFunctionType initTy = initFn->getType().castTo<SILFunctionType>();
      SILFunctionConventions initConv(initTy, AI->getModule());
      unsigned firstArgIdx = initConv.getSILArgIndexOfFirstParam();
      require(initConv.getNumSILArguments() == firstArgIdx + 1,
              "init function has wrong number of arguments");
      require(Src->getType() == initConv.getSILArgumentType(firstArgIdx),
              "wrong argument type of init function");
      switch (initConv.getNumIndirectSILResults()) {
        case 0:
          require(initConv.getNumDirectSILResults() == 1,
                  "wrong number of init function results");
          require(Dest->getType().getObjectType() ==
                  initConv.getDirectSILResultTypes().front(),
                  "wrong init function result type");
          break;
        case 1:
          require(initConv.getNumDirectSILResults() == 0,
                  "wrong number of init function results");
          require(Dest->getType() == initConv.getIndirectSILResultTypes().front(),
                  "wrong indirect init function result type");
          break;
        default:
          require(false, "wrong number of indirect init function results");
      }
  
      SILValue setterFn = AI->getSetter();
      CanSILFunctionType setterTy = setterFn->getType().castTo<SILFunctionType>();
      SILFunctionConventions setterConv(setterTy, AI->getModule());
      require(setterConv.getNumIndirectSILResults() == 0,
              "set function has indirect results");
      require(setterConv.getNumSILArguments() == 1,
              "init function has wrong number of arguments");
      require(Src->getType() == setterConv.getSILArgumentType(0),
              "wrong argument type of init function");
    }
  
  #define NEVER_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
    void checkLoad##Name##Inst(Load##Name##Inst *LWI) { \
      require(LWI->getType().isObject(), "Result of load must be an object"); \
      auto isOptional = bool(LWI->getType().getOptionalObjectType()); \
      auto optionality = optionalityOf(ReferenceOwnership::Name); \
      if (optionality == ReferenceOwnershipOptionality::Required) \
        require(isOptional, "Optionality mismatch"); \
      if (optionality == ReferenceOwnershipOptionality::Disallowed) \
        require(!isOptional, "Optionality mismatch"); \
      auto PointerType = LWI->getOperand()->getType(); \
      auto PointerRVType = PointerType.getASTType(); \
      require(PointerType.isAddress() && \
              PointerRVType->is<Name##StorageType>(), \
              "load_" #name " operand must be a " #name " address"); \
      require(PointerRVType->getReferenceStorageReferent()->getCanonicalType() ==\
              LWI->getType().getASTType(), \
              "Load operand type and result type mismatch"); \
    } \
    void checkStore##Name##Inst(Store##Name##Inst *SWI) { \
      auto SrcTy = SWI->getSrc()->getType(); \
      require(SrcTy.isObject(), "Can't store from an address source"); \
      auto isOptional = bool(SrcTy.getOptionalObjectType()); \
      auto optionality = optionalityOf(ReferenceOwnership::Name); \
      if (optionality == ReferenceOwnershipOptionality::Required) \
        require(isOptional, "Optionality mismatch"); \
      if (optionality == ReferenceOwnershipOptionality::Disallowed) \
        require(!isOptional, "Optionality mismatch"); \
      auto PointerType = SWI->getDest()->getType(); \
      auto PointerRVType = PointerType.getASTType(); \
      require(PointerType.isAddress() && \
              PointerRVType->is<Name##StorageType>(), \
              "store_" #name " address operand must be a " #name " address"); \
      require(PointerRVType->getReferenceStorageReferent()->getCanonicalType() ==\
              SrcTy.getASTType(), \
              "Store operand type and dest type mismatch"); \
    }
  #define LOADABLE_REF_STORAGE_HELPER(Name, name) \
    void checkRefTo##Name##Inst(RefTo##Name##Inst *I) { \
      requireReferenceStorageCapableValue(I->getOperand(), \
                                          "Operand of ref_to_" #name); \
      auto operandType = I->getOperand()->getType().getASTType(); \
      auto resultType = requireObjectType(Name##StorageType, I, \
                                          "Result of ref_to_" #name); \
      require(resultType.getReferentType() == operandType, \
              "Result of ref_to_" #name " does not have the " \
              "operand's type as its referent type"); \
    } \
    void check##Name##ToRefInst(Name##ToRefInst *I) { \
      auto operandType = requireObjectType(Name##StorageType, \
                                           I->getOperand(), \
                                           "Operand of " #name "_to_ref"); \
      requireReferenceStorageCapableValue(I, "Result of " #name "_to_ref"); \
      auto resultType = I->getType().getASTType(); \
      require(operandType.getReferentType() == resultType, \
              "Operand of " #name "_to_ref does not have the " \
              "operand's type as its referent type"); \
    }
  #define ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, closure) \
    void checkStrongRetain##Name##Inst(StrongRetain##Name##Inst *RI) { \
      auto ty = requireObjectType(Name##StorageType, RI->getOperand(), \
                                  "Operand of strong_retain_" #name); \
      closure(); \
      (void)ty; \
      require(!F.hasOwnership(), "strong_retain_" #name " is only in " \
                                          "functions with unqualified " \
                                          "ownership"); \
    } \
    void check##Name##RetainInst(Name##RetainInst *RI) { \
      auto ty = requireObjectType(Name##StorageType, RI->getOperand(), \
                                  "Operand of " #name "_retain"); \
      closure(); \
      (void)ty; \
      require(!F.hasOwnership(), \
              #name "_retain is only in functions with unqualified ownership"); \
    } \
    void check##Name##ReleaseInst(Name##ReleaseInst *RI) { \
      auto ty = requireObjectType(Name##StorageType, RI->getOperand(), \
                                  "Operand of " #name "_release"); \
      closure(); \
      (void)ty; \
      require(!F.hasOwnership(), \
              #name "_release is only in functions with unqualified ownership"); \
    } \
    void checkCopy##Name##ValueInst(Copy##Name##ValueInst *I) { \
      auto ty = requireObjectType(Name##StorageType, I->getOperand(), \
                                  "Operand of " #name "_retain"); \
      closure(); \
      (void)ty; \
      /* *NOTE* We allow copy_##name##_value to be used throughout the entire */ \
      /* pipeline even though it is a higher level instruction. */ \
    }
  #define ALWAYS_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
    LOADABLE_REF_STORAGE_HELPER(Name, name) \
    ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, []{})
  #define SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
    LOADABLE_REF_STORAGE_HELPER(Name, name) \
    NEVER_LOADABLE_CHECKED_REF_STORAGE(Name, name, "...") \
    ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, [&]{ \
      require(ty->isLoadable(ResilienceExpansion::Maximal), \
              "'" #name "' type must be loadable"); \
    })
  #define UNCHECKED_REF_STORAGE(Name, name, ...) \
    LOADABLE_REF_STORAGE_HELPER(Name, name)
  #include "swift/AST/ReferenceStorage.def"
  #undef LOADABLE_REF_STORAGE_HELPER
  #undef ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER
  
    void checkMarkUninitializedInst(MarkUninitializedInst *MU) {
      SILValue Src = MU->getOperand();
      require(MU->getModule().getStage() == SILStage::Raw,
              "mark_uninitialized instruction can only exist in raw SIL");
      require(Src->getType().isAddress() ||
              Src->getType().getClassOrBoundGenericClass() ||
              Src->getType().getAs<SILBoxType>(),
              "mark_uninitialized must be an address, class, or box type");
      require(Src->getType() == MU->getType(),"operand and result type mismatch");
      // FIXME: When the work to force MUI to be on Allocations/SILArguments
      // complete, turn on this assertion.
      require(isa<AllocationInst>(Src)
              || isa<GlobalAddrInst>(Src)
              // TODO: Should we support SILUndef on mark_uninitialized? We
              // currently have a test that verifies this behavior, but it seems
              // like this would always be a bug due to the implications around
              // the code in DI. This just bakes in the current behavior.
              || isa<SILUndef>(Src)
              // We allow SILArguments to support the case of initializing
              // initializers. In such a case, the underlying case is allocated
              // outside by the allocating initializer and we pass in the to be
              // initialized value as a SILArgument.
              || isa<SILArgument>(Src)
              // FIXME: Once the MarkUninitializedFixup pass is eliminated,
              // mark_uninitialized should never be applied to a project_box. So
              // at that point, this should be eliminated.
              || isa<ProjectBoxInst>(Src)
              // FIXME: We only support pointer to address here to not break LLDB. It is
              // important that long term we get rid of this since this is a situation
              // where LLDB is breaking SILGen/DI invariants by not creating a new
              // independent stack location for the pointer to address.
              || isa<PointerToAddressInst>(Src),
              "Mark Uninitialized must be applied to a storage location");
    }
  
    void checkMarkFunctionEscapeInst(MarkFunctionEscapeInst *MFE) {
      require(MFE->getModule().getStage() == SILStage::Raw,
              "mark_function_escape instruction can only exist in raw SIL");
      for (auto Elt : MFE->getElements())
        require(Elt->getType().isAddress(), "MFE must refer to variable addrs");
    }
  
    void checkCopyAddrInst(CopyAddrInst *SI) {
      require(SI->getSrc()->getType().isAddress(),
              "Src value should be lvalue");
      require(SI->getDest()->getType().isAddress(),
              "Dest address should be lvalue");
      require(SI->getDest()->getType() == SI->getSrc()->getType(),
              "Store operand type and dest type mismatch");
      require(F.isTypeABIAccessible(SI->getDest()->getType()),
              "cannot directly copy type with inaccessible ABI");
    }
  
    void checkRetainValueInst(RetainValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!F.hasOwnership(),
              "retain_value is only in functions with unqualified ownership");
    }
  
    void checkRetainValueAddrInst(RetainValueAddrInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Source value should be an address value");
      require(!F.hasOwnership(),
              "retain_value is only in functions with unqualified ownership");
    }
  
    void checkCopyValueInst(CopyValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!I->getOperand()->getType().isTrivial(*I->getFunction()),
              "Source value should be non-trivial");
      require(!fnConv.useLoweredAddresses() || F.hasOwnership(),
              "copy_value is only valid in functions with qualified "
              "ownership");
    }
  
    void checkDestroyValueInst(DestroyValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!I->getOperand()->getType().isTrivial(*I->getFunction()),
              "Source value should be non-trivial");
      require(!fnConv.useLoweredAddresses() || F.hasOwnership(),
              "destroy_value is only valid in functions with qualified "
              "ownership");
    }
  
    void checkReleaseValueInst(ReleaseValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!F.hasOwnership(),
              "release_value is only in functions with unqualified ownership");
    }
  
    void checkReleaseValueAddrInst(ReleaseValueAddrInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Source value should be an address value");
      require(!F.hasOwnership(),
              "release_value is only in functions with unqualified ownership");
    }
  
    void checkAutoreleaseValueInst(AutoreleaseValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      // TODO: This instruction could in principle be generalized.
      require(I->getOperand()->getType().hasRetainablePointerRepresentation(),
              "Source value must be a reference type or optional thereof");
    }
    
    void checkSetDeallocatingInst(SetDeallocatingInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(I->getOperand()->getType().hasRetainablePointerRepresentation(),
              "Source value must be a reference type");
    }
    
    void checkCopyBlockInst(CopyBlockInst *I) {
      require(I->getOperand()->getType().isBlockPointerCompatible(),
              "operand of copy_block should be a block");
      require(I->getOperand()->getType() == I->getType(),
              "result of copy_block should be same type as operand");
    }
    void checkCopyBlockInst(CopyBlockWithoutEscapingInst *I) {
      require(I->getBlock()->getType().isBlockPointerCompatible(),
              "operand of copy_block should be a block");
      require(I->getBlock()->getType() == I->getType(),
              "result of copy_block should be same type as operand");
      auto FnTy = requireObjectType(SILFunctionType, I->getClosure(),
                                    "copy_block_without_escaping operand");
      require(!FnTy->isNoEscape(),
              "closure parameter must not be a @noescape closure");
    }
  
    void checkAllocValueBufferInst(AllocValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
      verifyOpenedArchetype(I, I->getValueType().getASTType());
    }
  
    void checkProjectValueBufferInst(ProjectValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
    }
  
    void checkProjectBoxInst(ProjectBoxInst *I) {
      require(I->getOperand()->getType().isObject(),
              "project_box operand should be a value");
      auto boxTy = I->getOperand()->getType().getAs<SILBoxType>();
      require(boxTy, "project_box operand should be a @box type");
      require(I->getType() == boxTy->getFieldType(F.getModule(),
                                                  I->getFieldIndex()),
              "project_box result should be address of boxed type");
  
      // If we have a mark_uninitialized as a user, the mark_uninitialized must be
      // our only user. This is a requirement that is asserted by allocbox to
      // stack. This check just embeds the requirement into the IR.
      require(I->hasOneUse() ||
              none_of(I->getUses(),
                      [](Operand *Op) -> bool {
                        return isa<MarkUninitializedInst>(Op->getUser());
                      }),
              "project_box with more than one user when a user is a "
              "mark_uninitialized");
    }
  
    void checkProjectExistentialBoxInst(ProjectExistentialBoxInst *PEBI) {
      SILType operandType = PEBI->getOperand()->getType();
      require(operandType.isObject(),
              "project_existential_box operand must not be address");
  
      require(operandType.canUseExistentialRepresentation(F.getModule(),
                                                ExistentialRepresentation::Boxed),
              "project_existential_box operand must be boxed existential");
  
      require(PEBI->getType().isAddress(),
              "project_existential_box result must be an address");
  
      if (auto *AEBI = dyn_cast<AllocExistentialBoxInst>(PEBI->getOperand())) {
        // The lowered type must be the properly-abstracted form of the AST type.
        SILType exType = AEBI->getExistentialType();
        auto archetype = OpenedArchetypeType::get(exType.getASTType());
  
        auto loweredTy = F.getLoweredType(Lowering::AbstractionPattern(archetype),
                                          AEBI->getFormalConcreteType())
                                            .getAddressType();
  
        requireSameType(loweredTy, PEBI->getType(),
                "project_existential_box result should be the lowered "
                "concrete type of its alloc_existential_box");
      }
    }
    
    void checkDeallocValueBufferInst(DeallocValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
    }
    
    void checkStructInst(StructInst *SI) {
      auto *structDecl = SI->getType().getStructOrBoundGenericStruct();
      require(structDecl, "StructInst must return a struct");
      require(!structDecl->hasUnreferenceableStorage(),
              "Cannot build a struct with unreferenceable storage from elements "
              "using StructInst");
      require(!structDecl->isResilient(F.getModule().getSwiftModule(),
                                       F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(SI->getType().isObject(),
              "StructInst must produce an object");
  
      SILType structTy = SI->getType();
      auto opi = SI->getElements().begin(), opEnd = SI->getElements().end();
      for (VarDecl *field : structDecl->getStoredProperties()) {
        require(opi != opEnd,
                "number of struct operands does not match number of stored "
                "member variables of struct");
  
        SILType loweredType = structTy.getFieldType(field, F.getModule());
        if (SI->getModule().getStage() != SILStage::Lowered) {
          require((*opi)->getType() == loweredType,
                  "struct operand type does not match field type");
        }
        ++opi;
      }
    }
  
    void checkEnumInst(EnumInst *UI) {
      EnumDecl *ud = UI->getType().getEnumOrBoundGenericEnum();
      require(ud, "EnumInst must return an enum");
      require(UI->getElement()->getParentEnum() == ud,
              "EnumInst case must be a case of the result enum type");
      require(UI->getType().isObject(),
              "EnumInst must produce an object");
      require(UI->hasOperand() == UI->getElement()->hasAssociatedValues(),
              "EnumInst must take an argument iff the element does");
  
      if (UI->getElement()->hasAssociatedValues()) {
        require(UI->getOperand()->getType().isObject(),
                "EnumInst operand must be an object");
        SILType caseTy = UI->getType().getEnumElementType(UI->getElement(),
                                                          F.getModule());
        if (UI->getModule().getStage() != SILStage::Lowered) {
          require(caseTy == UI->getOperand()->getType(),
                  "EnumInst operand type does not match type of case");
        }
      }
    }
  
    void checkInitEnumDataAddrInst(InitEnumDataAddrInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "InitEnumDataAddrInst must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "InitEnumDataAddrInst case must be a case of the enum operand type");
      require(UI->getElement()->hasAssociatedValues(),
              "InitEnumDataAddrInst case must have a data type");
      require(UI->getOperand()->getType().isAddress(),
              "InitEnumDataAddrInst must take an address operand");
      require(UI->getType().isAddress(),
              "InitEnumDataAddrInst must produce an address");
  
      SILType caseTy =
        UI->getOperand()->getType().getEnumElementType(UI->getElement(),
                                                      F.getModule());
  
      if (UI->getModule().getStage() != SILStage::Lowered) {
        requireSameType(
            caseTy, UI->getType(),
            "InitEnumDataAddrInst result does not match type of enum case");
      }
    }
  
    void checkUncheckedEnumDataInst(UncheckedEnumDataInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "UncheckedEnumData must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "UncheckedEnumData case must be a case of the enum operand type");
      require(UI->getElement()->getArgumentInterfaceType(),
              "UncheckedEnumData case must have a data type");
      require(UI->getOperand()->getType().isObject(),
              "UncheckedEnumData must take an address operand");
      require(UI->getType().isObject(),
              "UncheckedEnumData must produce an address");
  
      SILType caseTy =
        UI->getOperand()->getType().getEnumElementType(UI->getElement(),
                                                      F.getModule());
  
      if (UI->getModule().getStage() != SILStage::Lowered) {
        require(caseTy == UI->getType(),
                "UncheckedEnumData result does not match type of enum case");
      }
    }
  
    void checkUncheckedTakeEnumDataAddrInst(UncheckedTakeEnumDataAddrInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "UncheckedTakeEnumDataAddrInst must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "UncheckedTakeEnumDataAddrInst case must be a case of the enum operand type");
      require(UI->getElement()->getArgumentInterfaceType(),
              "UncheckedTakeEnumDataAddrInst case must have a data type");
      require(UI->getOperand()->getType().isAddress(),
              "UncheckedTakeEnumDataAddrInst must take an address operand");
      require(UI->getType().isAddress(),
              "UncheckedTakeEnumDataAddrInst must produce an address");
  
      SILType caseTy =
        UI->getOperand()->getType().getEnumElementType(UI->getElement(),
                                                      F.getModule());
  
      if (UI->getModule().getStage() != SILStage::Lowered) {
        require(caseTy == UI->getType(), "UncheckedTakeEnumDataAddrInst result "
                                         "does not match type of enum case");
      }
    }
  
    void checkInjectEnumAddrInst(InjectEnumAddrInst *IUAI) {
      require(IUAI->getOperand()->getType().is<EnumType>()
                || IUAI->getOperand()->getType().is<BoundGenericEnumType>(),
              "InjectEnumAddrInst must take an enum operand");
      require(IUAI->getElement()->getParentEnum()
                == IUAI->getOperand()->getType().getEnumOrBoundGenericEnum(),
              "InjectEnumAddrInst case must be a case of the enum operand type");
      require(IUAI->getOperand()->getType().isAddress(),
              "InjectEnumAddrInst must take an address operand");
    }
  
    void checkTupleInst(TupleInst *TI) {
      CanTupleType ResTy = requireObjectType(TupleType, TI, "Result of tuple");
  
      require(TI->getElements().size() == ResTy->getNumElements(),
              "Tuple field count mismatch!");
  
      if (TI->getModule().getStage() != SILStage::Lowered) {
        for (size_t i = 0, size = TI->getElements().size(); i < size; ++i) {
          require(TI->getElement(i)->getType().getASTType() ==
                      ResTy.getElementType(i),
                  "Tuple element arguments do not match tuple type!");
        }
      }
    }
  
    // Is a SIL type a potential lowering of a formal type?
    bool isLoweringOf(SILType loweredType, CanType formalType) {
      return loweredType.isLoweringOf(F.getModule(), formalType);
    }
    
    void checkMetatypeInst(MetatypeInst *MI) {
      require(MI->getType().is<MetatypeType>(),
              "metatype instruction must be of metatype type");
      auto MetaTy = MI->getType().castTo<MetatypeType>();
      require(MetaTy->hasRepresentation(),
              "metatype instruction must have a metatype representation");
      verifyOpenedArchetype(MI, MetaTy.getInstanceType());
    }
    void checkValueMetatypeInst(ValueMetatypeInst *MI) {
      require(MI->getType().is<MetatypeType>(),
              "value_metatype instruction must be of metatype type");
      require(MI->getType().castTo<MetatypeType>()->hasRepresentation(),
              "value_metatype instruction must have a metatype representation");
      auto formalInstanceTy
        = MI->getType().castTo<MetatypeType>().getInstanceType();
      require(isLoweringOf(MI->getOperand()->getType(), formalInstanceTy),
              "value_metatype result must be formal metatype of "
              "lowered operand type");
    }
    void checkExistentialMetatypeInst(ExistentialMetatypeInst *MI) {
      require(MI->getType().is<ExistentialMetatypeType>(),
              "existential_metatype instruction must be of metatype type");
      require(MI->getType().castTo<ExistentialMetatypeType>()->hasRepresentation(),
              "value_metatype instruction must have a metatype representation");
      require(MI->getOperand()->getType().isAnyExistentialType(),
              "existential_metatype operand must be of protocol type");
      auto formalInstanceTy
        = MI->getType().castTo<ExistentialMetatypeType>().getInstanceType();
      require(isLoweringOf(MI->getOperand()->getType(), formalInstanceTy),
              "existential_metatype result must be formal metatype of "
              "lowered operand type");
    }
  
    void checkStrongRetainInst(StrongRetainInst *RI) {
      requireReferenceValue(RI->getOperand(), "Operand of strong_retain");
      require(!F.hasOwnership(),
              "strong_retain is only in functions with unqualified ownership");
    }
    void checkStrongReleaseInst(StrongReleaseInst *RI) {
      requireReferenceValue(RI->getOperand(), "Operand of release");
      require(!F.hasOwnership(),
              "strong_release is only in functions with unqualified ownership");
    }
  
    void checkDeallocStackInst(DeallocStackInst *DI) {
      require(isa<SILUndef>(DI->getOperand()) ||
                  isa<AllocStackInst>(DI->getOperand()) ||
                  (isa<PartialApplyInst>(DI->getOperand()) &&
                   cast<PartialApplyInst>(DI->getOperand())->isOnStack()),
              "Operand of dealloc_stack must be an alloc_stack or partial_apply "
              "[stack]");
    }
    void checkDeallocRefInst(DeallocRefInst *DI) {
      require(DI->getOperand()->getType().isObject(),
              "Operand of dealloc_ref must be object");
      auto *cd = DI->getOperand()->getType().getClassOrBoundGenericClass();
      require(cd, "Operand of dealloc_ref must be of class type");
  
      if (!DI->canAllocOnStack()) {
        require(!cd->isResilient(F.getModule().getSwiftModule(),
                                F.getResilienceExpansion()),
                "cannot directly deallocate resilient class");
      }
    }
    void checkDeallocPartialRefInst(DeallocPartialRefInst *DPRI) {
      require(DPRI->getInstance()->getType().isObject(),
              "First operand of dealloc_partial_ref must be object");
      auto class1 = DPRI->getInstance()->getType().getClassOrBoundGenericClass();
      require(class1,
              "First operand of dealloc_partial_ref must be of class type");
      require(DPRI->getMetatype()->getType().is<MetatypeType>(),
              "Second operand of dealloc_partial_ref must be a metatype");
      auto class2 = DPRI->getMetatype()->getType().castTo<MetatypeType>()
          ->getInstanceType()->getClassOrBoundGenericClass();
      require(class2,
              "Second operand of dealloc_partial_ref must be a class metatype");
      require(class2->isSuperclassOf(class1),
              "First operand not superclass of second instance type");
    }
  
    void checkAllocBoxInst(AllocBoxInst *AI) {
      auto boxTy = AI->getType().getAs<SILBoxType>();
      require(boxTy, "alloc_box must have a @box type");
  
      require(AI->getType().isObject(),
              "result of alloc_box must be an object");
      for (unsigned field : indices(AI->getBoxType()->getLayout()->getFields())) {
        verifyOpenedArchetype(AI,
                     AI->getBoxType()->getFieldLoweredType(F.getModule(), field));
      }
  
      // An alloc_box with a mark_uninitialized user can not have any other users.
      require(none_of(AI->getUses(),
                      [](Operand *Op) -> bool {
                        return isa<MarkUninitializedInst>(Op->getUser());
                      }) ||
                  AI->hasOneUse(),
              "An alloc_box with a mark_uninitialized user can not have any "
              "other users.");
    }
  
    void checkDeallocBoxInst(DeallocBoxInst *DI) {
      auto boxTy = DI->getOperand()->getType().getAs<SILBoxType>();
      require(boxTy, "operand must be a @box type");
      require(DI->getOperand()->getType().isObject(),
              "operand must be an object");
    }
  
    void checkDestroyAddrInst(DestroyAddrInst *DI) {
      require(DI->getOperand()->getType().isAddress(),
              "Operand of destroy_addr must be address");
      require(F.isTypeABIAccessible(DI->getOperand()->getType()),
              "cannot directly destroy type with inaccessible ABI");
    }
  
    void checkBindMemoryInst(BindMemoryInst *BI) {
      require(BI->getBoundType(), "BI must have a bound type");
      require(BI->getBase()->getType().is<BuiltinRawPointerType>(),
              "bind_memory base be a RawPointer");
      require(BI->getIndex()->getType()
              == SILType::getBuiltinWordType(F.getASTContext()),
              "bind_memory index must be a Word");
    }
  
    void checkIndexAddrInst(IndexAddrInst *IAI) {
      require(IAI->getType().isAddress(), "index_addr must produce an address");
      require(IAI->getType() == IAI->getBase()->getType(),
              "index_addr must produce an address of the same type as its base");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "index_addr index must be of a builtin integer type");
    }
  
    void checkTailAddrInst(TailAddrInst *IAI) {
      require(IAI->getType().isAddress(), "tail_addr must produce an address");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "tail_addr index must be of a builtin integer type");
    }
  
    void checkIndexRawPointerInst(IndexRawPointerInst *IAI) {
      require(IAI->getType().is<BuiltinRawPointerType>(),
              "index_raw_pointer must produce a RawPointer");
      require(IAI->getBase()->getType().is<BuiltinRawPointerType>(),
              "index_raw_pointer base must be a RawPointer");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "index_raw_pointer index must be of a builtin integer type");
    }
  
    void checkTupleExtractInst(TupleExtractInst *EI) {
      CanTupleType operandTy = requireObjectType(TupleType, EI->getOperand(),
                                                 "Operand of tuple_extract");
      require(EI->getType().isObject(),
              "result of tuple_extract must be object");
  
      require(EI->getFieldNo() < operandTy->getNumElements(),
              "invalid field index for tuple_extract instruction");
      if (EI->getModule().getStage() != SILStage::Lowered) {
        require(EI->getType().getASTType() ==
                    operandTy.getElementType(EI->getFieldNo()),
                "type of tuple_extract does not match type of element");
      }
    }
  
    void checkStructExtractInst(StructExtractInst *EI) {
      SILType operandTy = EI->getOperand()->getType();
      require(operandTy.isObject(),
              "cannot struct_extract from address");
      require(EI->getType().isObject(),
              "result of struct_extract cannot be address");
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "must struct_extract from struct");
      require(!sd->isResilient(F.getModule().getSwiftModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot load computed property with struct_extract");
  
      require(EI->getField()->getDeclContext() == sd,
              "struct_extract field is not a member of the struct");
  
      if (EI->getModule().getStage() != SILStage::Lowered) {
        SILType loweredFieldTy =
            operandTy.getFieldType(EI->getField(), F.getModule());
        require(loweredFieldTy == EI->getType(),
                "result of struct_extract does not match type of field");
      }
    }
  
    void checkTupleElementAddrInst(TupleElementAddrInst *EI) {
      SILType operandTy = EI->getOperand()->getType();
      require(operandTy.isAddress(),
              "must derive element_addr from address");
      require(EI->getType().isAddress(),
              "result of tuple_element_addr must be address");
      require(operandTy.is<TupleType>(),
              "must derive tuple_element_addr from tuple");
  
      ArrayRef<TupleTypeElt> fields = operandTy.castTo<TupleType>()->getElements();
      require(EI->getFieldNo() < fields.size(),
              "invalid field index for element_addr instruction");
      if (EI->getModule().getStage() != SILStage::Lowered) {
        require(EI->getType().getASTType() ==
                    CanType(fields[EI->getFieldNo()].getType()),
                "type of tuple_element_addr does not match type of element");
      }
    }
  
    void checkStructElementAddrInst(StructElementAddrInst *EI) {
      SILType operandTy = EI->getOperand()->getType();
      require(operandTy.isAddress(),
              "must derive struct_element_addr from address");
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "struct_element_addr operand must be struct address");
      require(!sd->isResilient(F.getModule().getSwiftModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(EI->getType().isAddress(),
              "result of struct_element_addr must be address");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot get address of computed property with struct_element_addr");
  
      require(EI->getField()->getDeclContext() == sd,
              "struct_element_addr field is not a member of the struct");
  
      if (EI->getModule().getStage() != SILStage::Lowered) {
        SILType loweredFieldTy =
            operandTy.getFieldType(EI->getField(), F.getModule());
        require(loweredFieldTy == EI->getType(),
                "result of struct_element_addr does not match type of field");
      }
    }
  
    void checkRefElementAddrInst(RefElementAddrInst *EI) {
      requireReferenceValue(EI->getOperand(), "Operand of ref_element_addr");
      require(EI->getType().isAddress(),
              "result of ref_element_addr must be lvalue");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot get address of computed property with ref_element_addr");
      SILType operandTy = EI->getOperand()->getType();
      ClassDecl *cd = operandTy.getClassOrBoundGenericClass();
      require(cd, "ref_element_addr operand must be a class instance");
      require(!cd->isResilient(F.getModule().getSwiftModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient class");
  
      require(EI->getField()->getDeclContext() == cd,
              "ref_element_addr field must be a member of the class");
  
      if (EI->getModule().getStage() != SILStage::Lowered) {
        SILType loweredFieldTy =
            operandTy.getFieldType(EI->getField(), F.getModule());
        require(loweredFieldTy == EI->getType(),
                "result of ref_element_addr does not match type of field");
      }
      EI->getFieldNo();  // Make sure we can access the field without crashing.
    }
  
    void checkRefTailAddrInst(RefTailAddrInst *RTAI) {
      requireReferenceValue(RTAI->getOperand(), "Operand of ref_tail_addr");
      require(RTAI->getType().isAddress(),
              "result of ref_tail_addr must be lvalue");
      SILType operandTy = RTAI->getOperand()->getType();
      ClassDecl *cd = operandTy.getClassOrBoundGenericClass();
      require(cd, "ref_tail_addr operand must be a class instance");
      require(!cd->isResilient(F.getModule().getSwiftModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient class");
      require(cd, "ref_tail_addr operand must be a class instance");
    }
  
    void checkDestructureStructInst(DestructureStructInst *DSI) {
      SILType operandTy = DSI->getOperand()->getType();
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "must struct_extract from struct");
      require(!sd->isResilient(F.getModule().getSwiftModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
    }
  
    SILType getMethodSelfType(CanSILFunctionType ft) {
      return fnConv.getSILType(ft->getParameters().back());
    }
  
    void checkWitnessMethodInst(WitnessMethodInst *AMI) {
      auto methodType = requireObjectType(SILFunctionType, AMI,
                                          "result of witness_method");
  
      auto *protocol
        = dyn_cast<ProtocolDecl>(AMI->getMember().getDecl()->getDeclContext());
      require(protocol,
              "witness_method method must be a protocol method");
  
      require(methodType->getRepresentation()
                == F.getModule().Types.getProtocolWitnessRepresentation(protocol),
              "result of witness_method must have correct representation for protocol");
  
      require(methodType->isPolymorphic(),
              "result of witness_method must be polymorphic");
  
      auto genericSig = methodType->getGenericSignature();
  
      auto selfGenericParam = genericSig->getGenericParams()[0];
      require(selfGenericParam->getDepth() == 0
              && selfGenericParam->getIndex() == 0,
              "method should be polymorphic on Self parameter at depth 0 index 0");
      Optional<Requirement> selfRequirement;
      for (auto req : genericSig->getRequirements()) {
        if (req.getKind() != RequirementKind::SameType) {
          selfRequirement = req;
          break;
        }
      }
  
      require(selfRequirement &&
              selfRequirement->getKind() == RequirementKind::Conformance,
              "first non-same-typerequirement should be conformance requirement");
      auto conformsTo = genericSig->getConformsTo(selfGenericParam);
      require(std::find(conformsTo.begin(), conformsTo.end(), protocol)
                != conformsTo.end(),
              "requirement Self parameter must conform to called protocol");
  
      auto lookupType = AMI->getLookupType();
      if (getOpenedArchetypeOf(lookupType)) {
        require(AMI->getTypeDependentOperands().size() == 1,
                "Must have a type dependent operand for the opened archetype");
        verifyOpenedArchetype(AMI, lookupType);
      } else {
        require(AMI->getTypeDependentOperands().empty(),
                "Should not have an operand for the opened existential");
      }
      if (!isa<ArchetypeType>(lookupType)) {
        require(AMI->getConformance().isConcrete(),
                "concrete type lookup requires concrete conformance");
        auto conformance = AMI->getConformance().getConcrete();
        require(conformance->getType()->isEqual(AMI->getLookupType()),
                "concrete type lookup requires conformance that matches type");
      }
  
      require(AMI->getMember().requiresNewWitnessTableEntry(),
              "method does not have a witness table entry");
    }
  
    // Get the expected type of a dynamic method reference.
    SILType getDynamicMethodType(SILType selfType, SILDeclRef method) {
      auto &C = F.getASTContext();
  
      // The type of the dynamic method must match the usual type of the method,
      // but with the more opaque Self type.
      auto constantInfo = F.getModule().Types.getConstantInfo(method);
      auto methodTy = constantInfo.SILFnType;
  
      assert(!methodTy->isCoroutine());
  
      // Map interface types to archetypes.
      if (auto *env = F.getModule().Types.getConstantGenericEnvironment(method)) {
        auto subs = env->getForwardingSubstitutionMap();
        methodTy = methodTy->substGenericArgs(F.getModule(), subs);
      }
      assert(!methodTy->isPolymorphic());
  
      // Replace Self parameter with type of 'self' at the call site.
      auto params = methodTy->getParameters();
      SmallVector<SILParameterInfo, 4>
        dynParams(params.begin(), params.end() - 1);
      dynParams.push_back(SILParameterInfo(selfType.getASTType(),
                                           params.back().getConvention()));
  
      auto results = methodTy->getResults();
      SmallVector<SILResultInfo, 4> dynResults(results.begin(), results.end());    
  
      // If the method returns Self, substitute AnyObject for the result type.
      if (auto fnDecl = dyn_cast<FuncDecl>(method.getDecl())) {
        if (fnDecl->hasDynamicSelfResult()) {
          auto anyObjectTy = C.getAnyObjectType();
          for (auto &dynResult : dynResults) {
            auto newResultTy
              = dynResult.getType()->replaceCovariantResultType(anyObjectTy, 0);
            dynResult = SILResultInfo(newResultTy->getCanonicalType(),
                                      dynResult.getConvention());
          }
        }
      }
  
      auto fnTy = SILFunctionType::get(nullptr,
                                       methodTy->getExtInfo(),
                                       methodTy->getCoroutineKind(),
                                       methodTy->getCalleeConvention(),
                                       dynParams,
                                       methodTy->getYields(),
                                       dynResults,
                                       methodTy->getOptionalErrorResult(),
                                       F.getASTContext());
      return SILType::getPrimitiveObjectType(fnTy);
    }
  
    /// Visitor class that checks whether a given decl ref has an entry in the
    /// class's vtable.
    class VerifyClassMethodVisitor
        : public SILVTableVisitor<VerifyClassMethodVisitor>
    {
    public:
      SILDeclRef Method;
      bool Seen = false;
  
      VerifyClassMethodVisitor(SILDeclRef method)
        : Method(method.getOverriddenVTableEntry()) {
        auto *theClass = cast<ClassDecl>(Method.getDecl()->getDeclContext());
        addVTableEntries(theClass);
      }
  
      void addMethod(SILDeclRef method) {
        if (Seen)
          return;
        if (method == Method)
          Seen = true;
      }
  
      void addMethodOverride(SILDeclRef base, SILDeclRef derived) {}
  
      void addPlaceholder(MissingMemberDecl *) {}
    };
  
    void checkClassMethodInst(ClassMethodInst *CMI) {
      auto member = CMI->getMember();
      auto overrideTy = TC.getConstantOverrideType(member);
      if (CMI->getModule().getStage() != SILStage::Lowered) {
        requireSameType(
            CMI->getType(), SILType::getPrimitiveObjectType(overrideTy),
            "result type of class_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(SILFunctionType, CMI,
                                          "result of class_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      SILType operandType = CMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");
      
      require(!member.isForeign,
              "foreign method cannot be dispatched natively");
      require(!isa<ExtensionDecl>(member.getDecl()->getDeclContext()),
              "extension method cannot be dispatched natively");
      
      // The method ought to appear in the class vtable.
      require(VerifyClassMethodVisitor(member).Seen,
              "method does not appear in the class's vtable");
    }
  
    void checkSuperMethodInst(SuperMethodInst *CMI) {
      auto member = CMI->getMember();
      auto overrideTy = TC.getConstantOverrideType(member);
      if (CMI->getModule().getStage() != SILStage::Lowered) {
        requireSameType(
            CMI->getType(), SILType::getPrimitiveObjectType(overrideTy),
            "result type of super_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(SILFunctionType, CMI,
                                          "result of super_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      SILType operandType = CMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");
  
      require(!member.isForeign,
              "foreign method cannot be dispatched natively");
      require(!isa<ExtensionDecl>(member.getDecl()->getDeclContext()),
              "extension method cannot be dispatched natively");
  
      auto decl = CMI->getMember().getDecl();
      auto methodClass = decl->getDeclContext()->getDeclaredInterfaceType();
  
      require(methodClass->getClassOrBoundGenericClass(),
              "super_method must look up a class method");
  
      // The method ought to appear in the class vtable.
      require(VerifyClassMethodVisitor(member).Seen,
              "method does not appear in the class's vtable");    
    }
  
    void checkObjCMethodInst(ObjCMethodInst *OMI) {
      auto member = OMI->getMember();
      require(member.isForeign,
              "native method cannot be dispatched via objc");
  
      auto methodType = requireObjectType(SILFunctionType, OMI,
                                          "result of objc_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      require(methodType->getRepresentation()
              == SILFunctionTypeRepresentation::ObjCMethod,
              "wrong function type representation");
  
      auto operandType = OMI->getOperand()->getType();
      auto operandInstanceType = operandType.getASTType();
      if (auto metatypeType = dyn_cast<MetatypeType>(operandInstanceType))
        operandInstanceType = metatypeType.getInstanceType();
  
      if (operandInstanceType.getClassOrBoundGenericClass()) {
        auto overrideTy = TC.getConstantOverrideType(member);
        requireSameType(
            OMI->getType(), SILType::getPrimitiveObjectType(overrideTy),
            "result type of objc_method must match abstracted type of method");
      } else {
        require(isa<ArchetypeType>(operandInstanceType) ||
                operandInstanceType->isObjCExistentialType(),
                "operand type must be an archetype or self-conforming existential");
        verifyOpenedArchetype(OMI, OMI->getType().getASTType());
      }
  
      // TODO: We should enforce that ObjC methods are dispatched on ObjC
      // metatypes, but IRGen appears not to care right now.
  #if 0
      if (auto metaTy = operandType.getAs<AnyMetatypeType>()) {
        bool objcMetatype
          = metaTy->getRepresentation() == MetatypeRepresentation::ObjC;
        require(objcMetatype,
                "objc class methods must be invoked on objc metatypes");
      }
  #endif
    }
  
    void checkObjCSuperMethodInst(ObjCSuperMethodInst *OMI) {
      auto member = OMI->getMember();
      auto overrideTy = TC.getConstantOverrideType(member);
      if (OMI->getModule().getStage() != SILStage::Lowered) {
        requireSameType(
            OMI->getType(), SILType::getPrimitiveObjectType(overrideTy),
            "result type of super_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(SILFunctionType, OMI,
                                          "result of objc_super_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      SILType operandType = OMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");
  
      require(member.isForeign,
              "native method cannot be dispatched via objc");
  
      auto decl = member.getDecl();
      auto methodClass = decl->getDeclContext()->getDeclaredInterfaceType();
  
      require(methodClass->getClassOrBoundGenericClass(),
              "objc_super_method must look up a class method");
    }
  
    void checkOpenExistentialAddrInst(OpenExistentialAddrInst *OEI) {
      SILType operandType = OEI->getOperand()->getType();
      require(operandType.isAddress(),
              "open_existential_addr must be applied to address");
      require(operandType.canUseExistentialRepresentation(F.getModule(),
                                          ExistentialRepresentation::Opaque),
             "open_existential_addr must be applied to opaque existential");
  
      require(OEI->getType().isAddress(),
              "open_existential_addr result must be an address");
  
      auto archetype = getOpenedArchetypeOf(OEI->getType().getASTType());
      require(archetype,
          "open_existential_addr result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_addr should be registered in "
              "SILFunction");
  
      // Check all the uses. Consuming or mutating uses must have mutable access
      // to the opened value.
      auto allowedAccessKind = OEI->getAccessKind();
      if (allowedAccessKind == OpenedExistentialAccess::Mutable)
        return;
  
      require(allowedAccessKind == OpenedExistentialAccess::Mutable ||
                  !ImmutableAddressUseVerifier().isMutatingOrConsuming(OEI),
              "open_existential_addr uses that consumes or mutates but is not "
              "opened for mutation");
    }
  
    void checkOpenExistentialRefInst(OpenExistentialRefInst *OEI) {
      SILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_ref operand must not be address");
  
      require(operandType.canUseExistentialRepresentation(F.getModule(),
                                                ExistentialRepresentation::Class),
              "open_existential_ref operand must be class existential");
  
      CanType resultInstanceTy = OEI->getType().getASTType();
  
      require(OEI->getType().isObject(),
              "open_existential_ref result must be an address");
  
      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
          "open_existential_ref result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_ref should be registered in "
              "SILFunction");
    }
  
    void checkOpenExistentialBoxInst(OpenExistentialBoxInst *OEI) {
      SILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_box operand must not be address");
  
      require(operandType.canUseExistentialRepresentation(F.getModule(),
                                                ExistentialRepresentation::Boxed),
              "open_existential_box operand must be boxed existential");
  
      CanType resultInstanceTy = OEI->getType().getASTType();
  
      require(OEI->getType().isAddress(),
              "open_existential_box result must be an address");
  
      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
          "open_existential_box result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_box should be registered in "
              "SILFunction");
    }
  
    void checkOpenExistentialBoxValueInst(OpenExistentialBoxValueInst *OEI) {
      SILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_box operand must not be address");
  
      require(operandType.canUseExistentialRepresentation(F.getModule(),
                                                ExistentialRepresentation::Boxed),
              "open_existential_box operand must be boxed existential");
  
      CanType resultInstanceTy = OEI->getType().getASTType();
  
      require(!OEI->getType().isAddress(),
              "open_existential_box_value result must not be an address");
  
      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
          "open_existential_box_value result not an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_box_value should be "
              "registered in SILFunction");
    }
  
    void checkOpenExistentialMetatypeInst(OpenExistentialMetatypeInst *I) {
      SILType operandType = I->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_metatype operand must not be address");
      require(operandType.is<ExistentialMetatypeType>(),
              "open_existential_metatype operand must be existential metatype");
      require(operandType.castTo<ExistentialMetatypeType>()->hasRepresentation(),
              "open_existential_metatype operand must have a representation");
  
      SILType resultType = I->getType();
      require(resultType.isObject(),
              "open_existential_metatype result must not be address");
      require(resultType.is<MetatypeType>(),
              "open_existential_metatype result must be metatype");
      require(resultType.castTo<MetatypeType>()->hasRepresentation(),
              "open_existential_metatype result must have a representation");
      require(operandType.castTo<ExistentialMetatypeType>()->getRepresentation()
                == resultType.castTo<MetatypeType>()->getRepresentation(),
              "open_existential_metatype result must match representation of "
              "operand");
  
      CanType operandInstTy =
        operandType.castTo<ExistentialMetatypeType>().getInstanceType();
      CanType resultInstTy = 
        resultType.castTo<MetatypeType>().getInstanceType();
  
      while (auto operandMetatype =
               dyn_cast<ExistentialMetatypeType>(operandInstTy)) {
        require(isa<MetatypeType>(resultInstTy),
                "metatype depth mismatch in open_existential_metatype result");
        operandInstTy = operandMetatype.getInstanceType();
        resultInstTy = cast<MetatypeType>(resultInstTy).getInstanceType();
      }
  
      require(operandInstTy.isExistentialType(),
              "ill-formed existential metatype in open_existential_metatype "
              "operand");
      auto archetype = getOpenedArchetypeOf(resultInstTy);
      require(archetype, "open_existential_metatype result must be an opened "
                         "existential metatype");
      require(
          OpenedArchetypes.getOpenedArchetypeDef(archetype) == I,
          "Archetype opened by open_existential_metatype should be registered in "
          "SILFunction");
    }
  
    void checkOpenExistentialValueInst(OpenExistentialValueInst *OEI) {
      SILType operandType = OEI->getOperand()->getType();
      require(!operandType.isAddress(),
              "open_existential_value must not be applied to address");
      require(operandType.canUseExistentialRepresentation(
                  F.getModule(), ExistentialRepresentation::Opaque),
              "open_existential_value must be applied to opaque existential");
  
      require(!OEI->getType().isAddress(),
              "open_existential_value result must not be an address");
  
      auto archetype = getOpenedArchetypeOf(OEI->getType().getASTType());
      require(archetype, "open_existential_value result must be an opened "
                         "existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential should be registered in "
              "SILFunction");
    }
  
    void checkAllocExistentialBoxInst(AllocExistentialBoxInst *AEBI) {
      SILType exType = AEBI->getExistentialType();
      require(exType.isObject(),
              "alloc_existential_box #0 result should be a value");
      require(exType.canUseExistentialRepresentation(F.getModule(),
                                               ExistentialRepresentation::Boxed,
                                               AEBI->getFormalConcreteType()),
              "alloc_existential_box must be used with a boxed existential "
              "type");
      
      checkExistentialProtocolConformances(exType.getASTType(),
                                           AEBI->getFormalConcreteType(),
                                           AEBI->getConformances());
      verifyOpenedArchetype(AEBI, AEBI->getFormalConcreteType());
    }
  
    void checkInitExistentialAddrInst(InitExistentialAddrInst *AEI) {
      SILType exType = AEI->getOperand()->getType();
      require(exType.isAddress(),
              "init_existential_addr must be applied to an address");
      require(exType.canUseExistentialRepresentation(F.getModule(),
                                         ExistentialRepresentation::Opaque,
                                         AEI->getFormalConcreteType()),
              "init_existential_addr must be used with an opaque "
              "existential type");
      
      // The lowered type must be the properly-abstracted form of the AST type.
      auto archetype = OpenedArchetypeType::get(exType.getASTType());
      
      auto loweredTy = F.getLoweredType(Lowering::AbstractionPattern(archetype),
                                        AEI->getFormalConcreteType())
                        .getAddressType();
      
      requireSameType(loweredTy, AEI->getLoweredConcreteType(),
                      "init_existential_addr result type must be the lowered "
                      "concrete type at the right abstraction level");
  
      require(isLoweringOf(AEI->getLoweredConcreteType(),
                           AEI->getFormalConcreteType()),
              "init_existential_addr payload must be a lowering of the formal "
              "concrete type");
      
      checkExistentialProtocolConformances(exType.getASTType(),
                                           AEI->getFormalConcreteType(),
                                           AEI->getConformances());
      verifyOpenedArchetype(AEI, AEI->getFormalConcreteType());
    }
  
    void checkInitExistentialValueInst(InitExistentialValueInst *IEI) {
      SILType concreteType = IEI->getOperand()->getType();
      require(!concreteType.isAddress(),
              "init_existential_value must not be used on addresses");
      require(!IEI->getType().isAddress(),
              "init_existential_value result must not be an address");
      // The operand must be at the right abstraction level for the existential.
      SILType exType = IEI->getType();
      auto archetype = OpenedArchetypeType::get(exType.getASTType());
      auto loweredTy = F.getLoweredType(Lowering::AbstractionPattern(archetype),
                                        IEI->getFormalConcreteType());
      requireSameType(
          concreteType, loweredTy,
          "init_existential_value operand must be lowered to the right "
          "abstraction level for the existential");
  
      require(isLoweringOf(IEI->getOperand()->getType(),
                           IEI->getFormalConcreteType()),
              "init_existential_value operand must be a lowering of the formal "
              "concrete type");
  
      checkExistentialProtocolConformances(exType.getASTType(),
                                           IEI->getFormalConcreteType(),
                                           IEI->getConformances());
      verifyOpenedArchetype(IEI, IEI->getFormalConcreteType());
    }
  
    void checkInitExistentialRefInst(InitExistentialRefInst *IEI) {
      SILType concreteType = IEI->getOperand()->getType();
      require(concreteType.getASTType()->isBridgeableObjectType(),
              "init_existential_ref operand must be a class instance");
      require(IEI->getType().canUseExistentialRepresentation(F.getModule(),
                                       ExistentialRepresentation::Class,
                                       IEI->getFormalConcreteType()),
              "init_existential_ref must be used with a class existential type");
      require(IEI->getType().isObject(),
              "init_existential_ref result must not be an address");
      
      // The operand must be at the right abstraction level for the existential.
      SILType exType = IEI->getType();
      auto archetype = OpenedArchetypeType::get(exType.getASTType());
      auto loweredTy = F.getLoweredType(Lowering::AbstractionPattern(archetype),
                                        IEI->getFormalConcreteType());
      requireSameType(concreteType, loweredTy,
                      "init_existential_ref operand must be lowered to the right "
                      "abstraction level for the existential");
      
      require(isLoweringOf(IEI->getOperand()->getType(),
                           IEI->getFormalConcreteType()),
              "init_existential_ref operand must be a lowering of the formal "
              "concrete type");
      
      checkExistentialProtocolConformances(exType.getASTType(),
                                           IEI->getFormalConcreteType(),
                                           IEI->getConformances());
      verifyOpenedArchetype(IEI, IEI->getFormalConcreteType());
    }
  
    void checkDeinitExistentialAddrInst(DeinitExistentialAddrInst *DEI) {
      SILType exType = DEI->getOperand()->getType();
      require(exType.isAddress(),
              "deinit_existential_addr must be applied to an address");
      require(exType.canUseExistentialRepresentation(
                  F.getModule(), ExistentialRepresentation::Opaque),
              "deinit_existential_addr must be applied to an opaque existential");
    }
  
    void checkDeinitExistentialValueInst(DeinitExistentialValueInst *DEI) {
      SILType exType = DEI->getOperand()->getType();
      require(!exType.isAddress(),
              "deinit_existential_value must not be applied to an address");
      require(
          exType.canUseExistentialRepresentation(
              F.getModule(), ExistentialRepresentation::Opaque),
          "deinit_existential_value must be applied to an opaque existential");
    }
    
    void checkDeallocExistentialBoxInst(DeallocExistentialBoxInst *DEBI) {
      SILType exType = DEBI->getOperand()->getType();
      require(exType.isObject(),
              "dealloc_existential_box must be applied to a value");
      require(exType.canUseExistentialRepresentation(F.getModule(),
                                         ExistentialRepresentation::Boxed),
              "dealloc_existential_box must be applied to a boxed "
              "existential");
    }
  
    void checkInitExistentialMetatypeInst(InitExistentialMetatypeInst *I) {
      SILType operandType = I->getOperand()->getType();
      require(operandType.isObject(),
              "init_existential_metatype operand must not be an address");
      require(operandType.is<MetatypeType>(),
              "init_existential_metatype operand must be a metatype");
      require(operandType.castTo<MetatypeType>()->hasRepresentation(),
              "init_existential_metatype operand must have a representation");
  
      SILType resultType = I->getType();
      require(resultType.is<ExistentialMetatypeType>(),
              "init_existential_metatype result must be an existential metatype");
      auto MetaTy = resultType.castTo<ExistentialMetatypeType>();
      require(resultType.isObject(),
              "init_existential_metatype result must not be an address");
      require(MetaTy->hasRepresentation(),
              "init_existential_metatype result must have a representation");
      require(MetaTy->getRepresentation()
                == operandType.castTo<MetatypeType>()->getRepresentation(),
              "init_existential_metatype result must match representation of "
              "operand");
  
      auto resultInstanceType = resultType.getASTType();
      auto operandInstanceType = operandType.getASTType();
      while (isa<ExistentialMetatypeType>(resultInstanceType)) {
        resultInstanceType =
            cast<ExistentialMetatypeType>(resultInstanceType).getInstanceType();
        operandInstanceType =
            cast<MetatypeType>(operandInstanceType).getInstanceType();
      }
  
      checkExistentialProtocolConformances(resultInstanceType,
                                           operandInstanceType,
                                           I->getConformances());
      verifyOpenedArchetype(I, MetaTy.getInstanceType());
    }
  
    void checkExistentialProtocolConformances(CanType resultType,
                                              CanType concreteType,
                                  ArrayRef<ProtocolConformanceRef> conformances) {
      auto layout = resultType.getExistentialLayout();
      auto protocols = layout.getProtocols();
  
      require(conformances.size() == protocols.size(),
              "init_existential instruction must have the "
              "right number of conformances");
  
      if (layout.requiresClass()) {
        require(concreteType->mayHaveSuperclass() ||
                (concreteType.isExistentialType() &&
                 concreteType.getExistentialLayout().requiresClass()),
                "init_existential of class existential with non-class type");
      }
  
      if (auto superclass = layout.getSuperclass()) {
        require(superclass->isExactSuperclassOf(concreteType),
                "init_existential of subclass existential with wrong type");
      }
  
      for (auto i : indices(conformances)) {
        require(conformances[i].getRequirement() == protocols[i]->getDecl(),
                "init_existential instruction must have conformances in "
                "proper order");
      }
    }
  
    void verifyCheckedCast(bool isExact, SILType fromTy, SILType toTy,
                           bool isOpaque = false) {
      // Verify common invariants.
      require(fromTy.isObject() && toTy.isObject(),
              "value checked cast src and dest must be objects");
  
      auto fromCanTy = fromTy.getASTType();
      auto toCanTy = toTy.getASTType();
  
      require(isOpaque || canUseScalarCheckedCastInstructions(F.getModule(),
                                                              fromCanTy, toCanTy),
              "invalid value checked cast src or dest types");
  
      // Peel off metatypes. If two types are checked-cast-able, so are their
      // metatypes.
      unsigned MetatyLevel = 0;
      while (isa<AnyMetatypeType>(fromCanTy) && isa<AnyMetatypeType>(toCanTy)) {
        auto fromMetaty = cast<AnyMetatypeType>(fromCanTy);
        auto toMetaty = cast<AnyMetatypeType>(toCanTy);
        
        // Check representations only for the top-level metatypes as only
        // those are SIL-lowered.
        if (!MetatyLevel) {
          // The representations must match.
          require(fromMetaty->getRepresentation() == toMetaty->getRepresentation(),
                  "metatype checked cast cannot change metatype representation");
  
          // We can't handle the 'thin' case yet, but it shouldn't really even be
          // interesting.
          require(fromMetaty->getRepresentation() != MetatypeRepresentation::Thin,
                  "metatype checked cast cannot check thin metatypes");
        }
  
        fromCanTy = fromMetaty.getInstanceType();
        toCanTy = toMetaty.getInstanceType();
        MetatyLevel++;
      }
  
      if (isExact) {
        require(fromCanTy.getClassOrBoundGenericClass(),
                "downcast operand must be a class type");
        require(toCanTy.getClassOrBoundGenericClass(),
                "downcast must convert to a class type");
        require(fromCanTy->isBindableToSuperclassOf(toCanTy),
                "downcast must convert to a subclass");
      }
    }
  
    void checkUnconditionalCheckedCastInst(UnconditionalCheckedCastInst *CI) {
      verifyCheckedCast(/*exact*/ false,
                        CI->getOperand()->getType(),
                        CI->getType());
      verifyOpenedArchetype(CI, CI->getType().getASTType());
    }
  
    void checkUnconditionalCheckedCastValueInst(
        UnconditionalCheckedCastValueInst *CI) {
      verifyCheckedCast(/*exact*/ false, CI->getOperand()->getType(),
                        CI->getType(), true);
      verifyOpenedArchetype(CI, CI->getType().getASTType());
    }
  
    /// Verify if a given type is or contains an opened archetype or dynamic self.
    /// If this is the case, verify that the provided instruction has a type
    /// dependent operand for it.
    void verifyOpenedArchetype(SILInstruction *I, CanType Ty) {
      if (!Ty)
        return;
      // Check the type and all of its contained types.
      Ty.visit([&](CanType t) {
        SILValue Def;
        if (t->isOpenedExistential()) {
          auto archetypeTy = cast<ArchetypeType>(t);
          Def = OpenedArchetypes.getOpenedArchetypeDef(archetypeTy);
          require(Def, "Opened archetype should be registered in SILFunction");
        } else if (t->hasDynamicSelfType()) {
          require(I->getFunction()->hasSelfParam() ||
                  I->getFunction()->hasSelfMetadataParam(),
                "Function containing dynamic self type must have self parameter");
          if (I->getFunction()->hasSelfMetadataParam())
            Def = I->getFunction()->getArguments().back();
          else
            Def = I->getFunction()->getSelfArgument();
        } else {
          return;
        }
        for (auto &TypeDefOp : I->getTypeDependentOperands()) {
          if (TypeDefOp.get() == Def)
            return;
        }
        require(false, "Instruction should contain a type dependent operand for "
                       "every used open archetype or dynamic self");
      });
    }
  
    void checkCheckedCastBranchInst(CheckedCastBranchInst *CBI) {
      verifyCheckedCast(CBI->isExact(),
                        CBI->getOperand()->getType(),
                        CBI->getCastType());
      verifyOpenedArchetype(CBI, CBI->getCastType().getASTType());
  
      require(CBI->getSuccessBB()->args_size() == 1,
              "success dest of checked_cast_br must take one argument");
      require(CBI->getSuccessBB()->args_begin()[0]->getType() ==
                  CBI->getCastType(),
              "success dest block argument of checked_cast_br must match type of "
              "cast");
      require(!F.hasOwnership() || CBI->getFailureBB()->args_size() == 1,
              "failure dest of checked_cast_br must take one argument in "
              "ownership qualified sil");
      require(!F.hasOwnership() ||
                  CBI->getFailureBB()->args_begin()[0]->getType() ==
                      CBI->getOperand()->getType(),
              "failure dest block argument must match type of original type in "
              "ownership qualified sil");
      require(F.hasOwnership() || CBI->getFailureBB()->args_empty(),
              "Failure dest of checked_cast_br must not take any argument in "
              "non-ownership qualified sil");
    }
  
    void checkCheckedCastValueBranchInst(CheckedCastValueBranchInst *CBI) {
      verifyCheckedCast(false, CBI->getOperand()->getType(), CBI->getCastType(),
                        true);
      verifyOpenedArchetype(CBI, CBI->getCastType().getASTType());
  
      require(CBI->getSuccessBB()->args_size() == 1,
              "success dest of checked_cast_value_br must take one argument");
      require(CBI->getSuccessBB()->args_begin()[0]->getType() ==
                  CBI->getCastType(),
              "success dest block argument of checked_cast_value_br must match "
              "type of cast");
      require(F.hasOwnership() || CBI->getFailureBB()->args_empty(),
              "failure dest of checked_cast_value_br in unqualified ownership "
              "sil must take no arguments");
    }
  
    void checkCheckedCastAddrBranchInst(CheckedCastAddrBranchInst *CCABI) {
      require(CCABI->getSrc()->getType().isAddress(),
              "checked_cast_addr_br src must be an address");
      require(CCABI->getDest()->getType().isAddress(),
              "checked_cast_addr_br dest must be an address");
  
      require(
          CCABI->getSuccessBB()->args_size() == 0,
          "success dest block of checked_cast_addr_br must not take an argument");
      require(
          CCABI->getFailureBB()->args_size() == 0,
          "failure dest block of checked_cast_addr_br must not take an argument");
    }
  
    void checkThinToThickFunctionInst(ThinToThickFunctionInst *TTFI) {
      auto opFTy = requireObjectType(SILFunctionType, TTFI->getOperand(),
                                     "thin_to_thick_function operand");
      auto resFTy = requireObjectType(SILFunctionType, TTFI,
                                      "thin_to_thick_function result");
      require(opFTy->isPolymorphic() == resFTy->isPolymorphic(),
              "thin_to_thick_function operand and result type must differ only "
              " in thinness");
      requireSameFunctionComponents(opFTy, resFTy,
                                    "thin_to_thick_function operand and result");
  
      require(opFTy->getRepresentation() == SILFunctionType::Representation::Thin,
              "operand of thin_to_thick_function must be thin");
      require(resFTy->getRepresentation() == SILFunctionType::Representation::Thick,
              "result of thin_to_thick_function must be thick");
  
      auto adjustedOperandExtInfo =
          opFTy->getExtInfo()
              .withRepresentation(SILFunctionType::Representation::Thick)
              .withNoEscape(resFTy->isNoEscape());
      require(adjustedOperandExtInfo == resFTy->getExtInfo(),
              "operand and result of thin_to_think_function must agree in particulars");
    }
  
    void checkThickToObjCMetatypeInst(ThickToObjCMetatypeInst *TTOCI) {
      auto opTy = requireObjectType(AnyMetatypeType, TTOCI->getOperand(),
                                    "thick_to_objc_metatype operand");
      auto resTy = requireObjectType(AnyMetatypeType, TTOCI,
                                     "thick_to_objc_metatype result");
  
      require(TTOCI->getOperand()->getType().is<MetatypeType>() ==
              TTOCI->getType().is<MetatypeType>(),
              "thick_to_objc_metatype cannot change metatype kinds");
      require(opTy->getRepresentation() == MetatypeRepresentation::Thick,
              "operand of thick_to_objc_metatype must be thick");
      require(resTy->getRepresentation() == MetatypeRepresentation::ObjC,
              "operand of thick_to_objc_metatype must be ObjC");
  
      require(opTy->getInstanceType()->isEqual(resTy->getInstanceType()),
              "thick_to_objc_metatype instance types do not match");
    }
  
    void checkObjCToThickMetatypeInst(ObjCToThickMetatypeInst *OCTTI) {
      auto opTy = requireObjectType(AnyMetatypeType, OCTTI->getOperand(),
                                    "objc_to_thick_metatype operand");
      auto resTy = requireObjectType(AnyMetatypeType, OCTTI,
                                     "objc_to_thick_metatype result");
  
      require(OCTTI->getOperand()->getType().is<MetatypeType>() ==
              OCTTI->getType().is<MetatypeType>(),
              "objc_to_thick_metatype cannot change metatype kinds");
      require(opTy->getRepresentation() == MetatypeRepresentation::ObjC,
              "operand of objc_to_thick_metatype must be ObjC");
      require(resTy->getRepresentation() == MetatypeRepresentation::Thick,
              "operand of objc_to_thick_metatype must be thick");
  
      require(opTy->getInstanceType()->isEqual(resTy->getInstanceType()),
              "objc_to_thick_metatype instance types do not match");
    }
  
    void checkUpcastInst(UpcastInst *UI) {
      require(UI->getType() != UI->getOperand()->getType(),
              "can't upcast to same type");
      if (UI->getType().is<MetatypeType>()) {
        CanType instTy(UI->getType().castTo<MetatypeType>()->getInstanceType());
        require(UI->getOperand()->getType().is<MetatypeType>(),
                "upcast operand must be a class or class metatype instance");
        CanType opInstTy(UI->getOperand()->getType().castTo<MetatypeType>()
                           ->getInstanceType());
        auto instClass = instTy->getClassOrBoundGenericClass();
        require(instClass,
                "upcast must convert a class metatype to a class metatype");
        
        if (instClass->usesObjCGenericsModel()) {
          require(instClass->getDeclaredTypeInContext()
                    ->isBindableToSuperclassOf(opInstTy),
                  "upcast must cast to a superclass or an existential metatype");
        } else {
          require(instTy->isExactSuperclassOf(opInstTy),
                  "upcast must cast to a superclass or an existential metatype");
        }
        return;
      }
  
      require(UI->getType().getCategory() ==
              UI->getOperand()->getType().getCategory(),
              "Upcast can only upcast in between types of the same "
              "SILValueCategory. This prevents address types from being cast to "
              "object types or vis-a-versa");
  
      auto ToTy = UI->getType();
      auto FromTy = UI->getOperand()->getType();
  
      // Upcast from Optional<B> to Optional<A> is legal as long as B is a
      // subclass of A.
      if (ToTy.getASTType().getOptionalObjectType() &&
          FromTy.getASTType().getOptionalObjectType()) {
        ToTy = SILType::getPrimitiveObjectType(
            ToTy.getASTType().getOptionalObjectType());
        FromTy = SILType::getPrimitiveObjectType(
            FromTy.getASTType().getOptionalObjectType());
      }
  
      auto ToClass = ToTy.getClassOrBoundGenericClass();
      require(ToClass,
              "upcast must convert a class instance to a class type");
        if (ToClass->usesObjCGenericsModel()) {
          require(ToClass->getDeclaredTypeInContext()
                    ->isBindableToSuperclassOf(FromTy.getASTType()),
                  "upcast must cast to a superclass or an existential metatype");
        } else {
          require(ToTy.isExactSuperclassOf(FromTy),
                  "upcast must cast to a superclass or an existential metatype");
        }
    }
  
    void checkAddressToPointerInst(AddressToPointerInst *AI) {
      require(AI->getOperand()->getType().isAddress(),
              "address-to-pointer operand must be an address");
      require(AI->getType().getASTType()->isEqual(
                                AI->getType().getASTContext().TheRawPointerType),
              "address-to-pointer result type must be RawPointer");
    }
    
    void checkUncheckedRefCastInst(UncheckedRefCastInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getASTType());
      require(AI->getOperand()->getType().isObject(),
              "unchecked_ref_cast operand must be a value");
      require(AI->getType().isObject(),
              "unchecked_ref_cast result must be an object");
      require(SILType::canRefCast(AI->getOperand()->getType(), AI->getType(),
                                  AI->getModule()),
              "unchecked_ref_cast requires a heap object reference type");
    }
  
    void checkUncheckedRefCastAddrInst(UncheckedRefCastAddrInst *AI) {
      auto srcTy = AI->getSrc()->getType();
      auto destTy = AI->getDest()->getType();
      require(srcTy.isAddress(),
              "unchecked_ref_cast_addr operand must be an address");
      require(destTy.isAddress(),
              "unchecked_ref_cast_addr result must be an address");
      // The static src/dest types cannot be checked here even if they are
      // loadable. unchecked_ref_cast_addr may accept nonreference static types
      // (as a result of specialization). These cases will never be promoted to
      // value bitcast, thus will cause the subsequent runtime cast to fail.
    }
    
    void checkUncheckedAddrCastInst(UncheckedAddrCastInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getASTType());
  
      require(AI->getOperand()->getType().isAddress(),
              "unchecked_addr_cast operand must be an address");
      require(AI->getType().isAddress(),
              "unchecked_addr_cast result must be an address");
    }
    
    void checkUncheckedTrivialBitCastInst(UncheckedTrivialBitCastInst *BI) {
      verifyOpenedArchetype(BI, BI->getType().getASTType());
      require(BI->getOperand()->getType().isObject(),
              "unchecked_trivial_bit_cast must operate on a value");
      require(BI->getType().isObject(),
              "unchecked_trivial_bit_cast must produce a value");
      require(BI->getType().isTrivial(F),
              "unchecked_trivial_bit_cast must produce a value of trivial type");
    }
  
    void checkUncheckedBitwiseCastInst(UncheckedBitwiseCastInst *BI) {
      verifyOpenedArchetype(BI, BI->getType().getASTType());
      require(BI->getOperand()->getType().isObject(),
              "unchecked_bitwise_cast must operate on a value");
      require(BI->getType().isObject(),
              "unchecked_bitwise_cast must produce a value");
    }
  
    void checkRefToRawPointerInst(RefToRawPointerInst *AI) {
      require(AI->getOperand()->getType().isAnyClassReferenceType(),
              "ref-to-raw-pointer operand must be a class reference or"
              " NativeObject");
      require(AI->getType().getASTType()->isEqual(
                              AI->getType().getASTContext().TheRawPointerType),
              "ref-to-raw-pointer result must be RawPointer");
    }
  
    void checkRawPointerToRefInst(RawPointerToRefInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getASTType());
      require(AI->getType()
                .getASTType()->isBridgeableObjectType()
              || AI->getType().getASTType()->isEqual(
                               AI->getType().getASTContext().TheNativeObjectType),
          "raw-pointer-to-ref result must be a class reference or NativeObject");
      require(AI->getOperand()->getType().getASTType()->isEqual(
                              AI->getType().getASTContext().TheRawPointerType),
              "raw-pointer-to-ref operand must be NativeObject");
    }
    
    void checkRefToBridgeObjectInst(RefToBridgeObjectInst *RI) {
      require(RI->getConverted()->getType().isObject(),
              "ref_to_bridge_object must convert from a value");
      require(RI->getConverted()->getType().getASTType()
                ->isBridgeableObjectType(),
              "ref_to_bridge_object must convert from a heap object ref");
      require(RI->getBitsOperand()->getType()
                == SILType::getBuiltinWordType(F.getASTContext()),
              "ref_to_bridge_object must take a Builtin.Word bits operand");
      require(RI->getType() == SILType::getBridgeObjectType(F.getASTContext()),
              "ref_to_bridge_object must produce a BridgeObject");
    }
    
    void checkBridgeObjectToRefInst(BridgeObjectToRefInst *RI) {
      verifyOpenedArchetype(RI, RI->getType().getASTType());
      require(RI->getConverted()->getType()
                 == SILType::getBridgeObjectType(F.getASTContext()),
              "bridge_object_to_ref must take a BridgeObject");
      require(RI->getType().isObject(),
              "bridge_object_to_ref must produce a value");
      require(RI->getType().getASTType()->isBridgeableObjectType(),
              "bridge_object_to_ref must produce a heap object reference");
    }
    void checkBridgeObjectToWordInst(BridgeObjectToWordInst *RI) {
      require(RI->getConverted()->getType()
                 == SILType::getBridgeObjectType(F.getASTContext()),
              "bridge_object_to_word must take a BridgeObject");
      require(RI->getType().isObject(),
              "bridge_object_to_word must produce a value");
      require(RI->getType() == SILType::getBuiltinWordType(F.getASTContext()),
              "bridge_object_to_word must produce a Word");
    }
  
    void checkConvertFunctionInst(ConvertFunctionInst *ICI) {
      auto opTI = requireObjectType(SILFunctionType, ICI->getOperand(),
                                    "convert_function operand");
      auto resTI = requireObjectType(SILFunctionType, ICI,
                                     "convert_function result");
  
      // convert_function is required to be an ABI-compatible conversion.
      requireABICompatibleFunctionTypes(
          opTI, resTI, "convert_function cannot change function ABI",
          ICI->getFunction());
    }
  
    void checkConvertEscapeToNoEscapeInst(ConvertEscapeToNoEscapeInst *ICI) {
      auto opTI = requireObjectType(SILFunctionType, ICI->getOperand(),
                                    "convert_escape_to_noescape operand");
      auto resTI = ICI->getType().castTo<SILFunctionType>();
  
      // FIXME: Not yet, to be enabled when this is true.
      // require(resTI->isTrivial(F.getModule()),
      //         "convert_escape_to_noescape should produce a trivial result type");
  
      // convert_escape_to_noescape is required to be an ABI-compatible
      // conversion once escapability is the same on both sides.
      requireABICompatibleFunctionTypes(
          opTI, resTI->getWithExtInfo(resTI->getExtInfo().withNoEscape(false)),
          "convert_escape_to_noescape cannot change function ABI",
          ICI->getFunction());
  
      // After mandatory passes convert_escape_to_noescape should not have the
      // '[not_guaranteed]' or '[escaped]' attributes.
      if (!SkipConvertEscapeToNoescapeAttributes &&
          F.getModule().getStage() != SILStage::Raw) {
        require(ICI->isLifetimeGuaranteed(),
                "convert_escape_to_noescape [not_guaranteed] not "
                "allowed after mandatory passes");
      }
    }
  
    void checkThinFunctionToPointerInst(ThinFunctionToPointerInst *CI) {
      auto opTI = requireObjectType(SILFunctionType, CI->getOperand(),
                                    "thin_function_to_pointer operand");
      requireObjectType(BuiltinRawPointerType, CI,
                        "thin_function_to_pointer result");
  
      auto rep = opTI->getRepresentation();
      require(rep == SILFunctionTypeRepresentation::Thin ||
              rep == SILFunctionTypeRepresentation::Method ||
              rep == SILFunctionTypeRepresentation::WitnessMethod,
              "thin_function_to_pointer only works on thin, method or "
              "witness_method functions");
    }
  
    void checkPointerToThinFunctionInst(PointerToThinFunctionInst *CI) {
      auto resultTI = requireObjectType(SILFunctionType, CI,
                                        "pointer_to_thin_function result");
      requireObjectType(BuiltinRawPointerType, CI->getOperand(),
                        "pointer_to_thin_function operand");
  
      auto rep = resultTI->getRepresentation();
      require(rep == SILFunctionTypeRepresentation::Thin ||
              rep == SILFunctionTypeRepresentation::Method ||
              rep == SILFunctionTypeRepresentation::WitnessMethod,
              "pointer_to_thin_function only works on thin, method or "
              "witness_method functions");
    }
  
    void checkCondFailInst(CondFailInst *CFI) {
      require(CFI->getOperand()->getType()
                == SILType::getBuiltinIntegerType(1, F.getASTContext()),
              "cond_fail operand must be a Builtin.Int1");
    }
  
    void checkReturnInst(ReturnInst *RI) {
      LLVM_DEBUG(RI->print(llvm::dbgs()));
  
      SILType functionResultType =
          F.mapTypeIntoContext(fnConv.getSILResultType());
      SILType instResultType = RI->getOperand()->getType();
      LLVM_DEBUG(llvm::dbgs() << "function return type: ";
                 functionResultType.dump();
                 llvm::dbgs() << "return inst type: ";
                 instResultType.dump(););
      require(functionResultType == instResultType,
              "return value type does not match return type of function");
    }
  
    void checkThrowInst(ThrowInst *TI) {
      LLVM_DEBUG(TI->print(llvm::dbgs()));
  
      CanSILFunctionType fnType = F.getLoweredFunctionType();
      require(fnType->hasErrorResult(),
              "throw in function that doesn't have an error result");
  
      SILType functionResultType = F.mapTypeIntoContext(fnConv.getSILErrorType());
      SILType instResultType = TI->getOperand()->getType();
      LLVM_DEBUG(llvm::dbgs() << "function error result type: ";
                 functionResultType.dump();
                 llvm::dbgs() << "throw operand type: ";
                 instResultType.dump(););
      require(functionResultType == instResultType,
              "throw operand type does not match error result type of function");
    }
    
    void checkUnwindInst(UnwindInst *UI) {
      require(F.getLoweredFunctionType()->isCoroutine(),
              "unwind in non-coroutine function");
    }
  
    void checkYieldInst(YieldInst *YI) {
      CanSILFunctionType fnType = F.getLoweredFunctionType();
      require(fnType->isCoroutine(),
              "yield in non-coroutine function");
  
      auto yieldedValues = YI->getYieldedValues();
      auto yieldInfos = fnType->getYields();
      require(yieldedValues.size() == yieldInfos.size(),
              "wrong number of yielded values for function");
      for (auto i : indices(yieldedValues)) {
        SILType yieldType =
          F.mapTypeIntoContext(fnConv.getSILType(yieldInfos[i]));
        require(yieldedValues[i]->getType() == yieldType,
                "yielded value does not match yield type of coroutine");
      }
  
      // We require the resume and unwind destinations to be unique in order
      // to prevent either edge from becoming critical.
      require(YI->getResumeBB()->getSinglePredecessorBlock(),
              "resume dest of 'yield' must be uniquely used");
      require(YI->getUnwindBB()->getSinglePredecessorBlock(),
              "unwind dest of 'yield' must be uniquely used");
    }
  
    void checkSelectEnumCases(SelectEnumInstBase *I) {
      EnumDecl *eDecl = I->getEnumOperand()->getType().getEnumOrBoundGenericEnum();
      require(eDecl, "select_enum operand must be an enum");
  
      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      eDecl->getAllElements(unswitchedElts);
  
      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = I->getNumCases(); i < e; ++i) {
        EnumElementDecl *elt;
        SILValue result;
        std::tie(elt, result) = I->getCase(i);
  
        require(elt->getDeclContext() == eDecl,
                "select_enum dispatches on enum element that is not part of "
                "its type");
        require(unswitchedElts.count(elt),
                "select_enum dispatches on same enum element more than once");
        unswitchedElts.erase(elt);
  
        // The result value must match the type of the instruction.
        requireSameType(result->getType(), I->getType(),
                      "select_enum case operand must match type of instruction");
      }
  
      // If the select is non-exhaustive, we require a default.
      bool isExhaustive =
          eDecl->isEffectivelyExhaustive(F.getModule().getSwiftModule(),
                                         F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || I->hasDefault(),
              "nonexhaustive select_enum must have a default destination");
      if (I->hasDefault()) {
        requireSameType(I->getDefaultResult()->getType(),
                    I->getType(),
                    "select_enum default operand must match type of instruction");
      }
    }
  
    void checkSelectEnumInst(SelectEnumInst *SEI) {
      require(SEI->getEnumOperand()->getType().isObject(),
              "select_enum operand must be an object");
      
      checkSelectEnumCases(SEI);
    }
    void checkSelectEnumAddrInst(SelectEnumAddrInst *SEI) {
      require(SEI->getEnumOperand()->getType().isAddress(),
              "select_enum_addr operand must be an address");
      
      checkSelectEnumCases(SEI);
    }
  
    void checkSwitchValueInst(SwitchValueInst *SVI) {
      // TODO: Type should be either integer or function
      auto Ty = SVI->getOperand()->getType();
      require(Ty.is<BuiltinIntegerType>() || Ty.is<SILFunctionType>(),
              "switch_value operand should be either of an integer "
              "or function type");
  
      auto ult = [](const SILValue &a, const SILValue &b) { 
        return a == b || a < b; 
      };
  
      std::set<SILValue, decltype(ult)> cases(ult);
  
      for (unsigned i = 0, e = SVI->getNumCases(); i < e; ++i) {
        SILValue value;
        SILBasicBlock *dest;
        std::tie(value, dest) = SVI->getCase(i);
  
        require(value->getType() == Ty,
               "switch_value case value should have the same type as its operand");
  
        require(!cases.count(value),
                "multiple switch_value cases for same value");
        cases.insert(value);
  
        require(dest->args_empty(),
                "switch_value case destination cannot take arguments");
      }
  
      if (SVI->hasDefault())
        require(SVI->getDefaultBB()->args_empty(),
                "switch_value default destination cannot take arguments");
    }
  
    void checkSelectValueCases(SelectValueInst *I) {
      struct APIntCmp {
        bool operator()(const APInt &a, const APInt &b) const {
          return a.ult(b);
        };
      };
  
      llvm::SmallSet<APInt, 16, APIntCmp> seenCaseValues;
  
      // Verify the set of cases we dispatch on.
      for (unsigned i = 0, e = I->getNumCases(); i < e; ++i) {
        SILValue casevalue;
        SILValue result;
        std::tie(casevalue, result) = I->getCase(i);
        
        if (!isa<SILUndef>(casevalue)) {
          auto  *il = dyn_cast<IntegerLiteralInst>(casevalue);
          require(il,
                  "select_value case operands should refer to integer literals");
          APInt elt = il->getValue();
  
          require(!seenCaseValues.count(elt),
                  "select_value dispatches on same case value more than once");
  
          seenCaseValues.insert(elt);
        }
  
        requireSameType(I->getOperand()->getType(), casevalue->getType(),
                        "select_value case value must match type of operand");
  
        // The result value must match the type of the instruction.
        requireSameType(result->getType(), I->getType(),
                      "select_value case result must match type of instruction");
      }
  
      require(I->hasDefault(),
              "select_value should always have a default");
      requireSameType(I->getDefaultResult()->getType(),
                    I->getType(),
                    "select_value default operand must match type of instruction");
    }
  
    void checkSelectValueInst(SelectValueInst *SVI) {
      require(SVI->getOperand()->getType().isObject(),
              "select_value operand must be an object");
  
      checkSelectValueCases(SVI);
    }
  
    void checkSwitchEnumInst(SwitchEnumInst *SOI) {
      require(SOI->getOperand()->getType().isObject(),
              "switch_enum operand must be an object");
  
      SILType uTy = SOI->getOperand()->getType();
      EnumDecl *uDecl = uTy.getEnumOrBoundGenericEnum();
      require(uDecl, "switch_enum operand is not an enum");
  
      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      uDecl->getAllElements(unswitchedElts);
  
      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = SOI->getNumCases(); i < e; ++i) {
        EnumElementDecl *elt;
        SILBasicBlock *dest;
        std::tie(elt, dest) = SOI->getCase(i);
  
        require(elt->getDeclContext() == uDecl,
                "switch_enum dispatches on enum element that is not part of "
                "its type");
        require(unswitchedElts.count(elt),
                "switch_enum dispatches on same enum element more than once");
        unswitchedElts.erase(elt);
  
        // The destination BB can take the argument payload, if any, as a BB
        // arguments, or it can ignore it and take no arguments.
        if (elt->hasAssociatedValues()) {
          if (isSILOwnershipEnabled() && F.hasOwnership()) {
            require(dest->getArguments().size() == 1,
                    "switch_enum destination for case w/ args must take 1 "
                    "argument");
          } else {
            require(dest->getArguments().empty() ||
                        dest->getArguments().size() == 1,
                    "switch_enum destination for case w/ args must take 0 or 1 "
                    "arguments");
          }
  
          if (dest->getArguments().size() == 1) {
            SILType eltArgTy = uTy.getEnumElementType(elt, F.getModule());
            SILType bbArgTy = dest->getArguments()[0]->getType();
            if (F.getModule().getStage() != SILStage::Lowered) {
              // During the lowered stage, a function type might have different
              // signature
              require(eltArgTy == bbArgTy,
                      "switch_enum destination bbarg must match case arg type");
            }
            require(!dest->getArguments()[0]->getType().isAddress(),
                    "switch_enum destination bbarg type must not be an address");
          }
  
        } else {
          require(dest->getArguments().empty(),
                  "switch_enum destination for no-argument case must take no "
                  "arguments");
        }
      }
  
      // If the switch is non-exhaustive, we require a default.
      bool isExhaustive =
          uDecl->isEffectivelyExhaustive(F.getModule().getSwiftModule(),
                                         F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || SOI->hasDefault(),
              "nonexhaustive switch_enum must have a default destination");
      if (SOI->hasDefault()) {
        // When SIL ownership is enabled, we require all default branches to take
        // an @owned original version of the enum.
        //
        // When SIL ownership is disabled, we no longer support this.
        if (isSILOwnershipEnabled() && F.hasOwnership()) {
          require(SOI->getDefaultBB()->getNumArguments() == 1,
                  "Switch enum default block should have one argument");
          require(SOI->getDefaultBB()->getArgument(0)->getType() ==
                      SOI->getOperand()->getType(),
                  "Switch enum default block should have one argument that is "
                  "the same as the input type");
        } else if (!F.hasOwnership()) {
          require(SOI->getDefaultBB()->args_empty(),
                  "switch_enum default destination must take no arguments");
        }
      }
    }
  
    void checkSwitchEnumAddrInst(SwitchEnumAddrInst *SOI) {
      require(SOI->getOperand()->getType().isAddress(),
              "switch_enum_addr operand must be an address");
  
      SILType uTy = SOI->getOperand()->getType();
      EnumDecl *uDecl = uTy.getEnumOrBoundGenericEnum();
      require(uDecl, "switch_enum_addr operand must be an enum");
  
      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      uDecl->getAllElements(unswitchedElts);
  
      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = SOI->getNumCases(); i < e; ++i) {
        EnumElementDecl *elt;
        SILBasicBlock *dest;
        std::tie(elt, dest) = SOI->getCase(i);
  
        require(elt->getDeclContext() == uDecl,
                "switch_enum_addr dispatches on enum element that "
                "is not part of its type");
        require(unswitchedElts.count(elt),
                "switch_enum_addr dispatches on same enum element "
                "more than once");
        unswitchedElts.erase(elt);
  
        // The destination BB must not have BB arguments.
        require(dest->getArguments().empty(),
                "switch_enum_addr destination must take no BB args");
      }
  
      // If the switch is non-exhaustive, we require a default.
      bool isExhaustive =
          uDecl->isEffectivelyExhaustive(F.getModule().getSwiftModule(),
                                         F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || SOI->hasDefault(),
              "nonexhaustive switch_enum_addr must have a default destination");
  
      if (SOI->hasDefault())
        require(SOI->getDefaultBB()->args_empty(),
                "switch_enum_addr default destination must take "
                "no arguments");
    }
  
    bool verifyBranchArgs(SILValue branchArg, SILArgument *bbArg) {
      // NOTE: IRGen currently does not support the following method_inst
      // variants as branch arguments.
      // Once this is supported, the check can be removed.
      require(!(isa<MethodInst>(branchArg) &&
                cast<MethodInst>(branchArg)->getMember().isForeign),
          "branch argument cannot be a witness_method or an objc method_inst");
      require(!(branchArg->getType().is<SILFunctionType>() &&
                branchArg->getType()
                        .castTo<SILFunctionType>()
                        ->getExtInfo()
                        .getRepresentation() ==
                    SILFunctionTypeRepresentation::ObjCMethod),
              "branch argument cannot be a objective-c method");
      return branchArg->getType() == bbArg->getType();
    }
  
    void checkBranchInst(BranchInst *BI) {
      require(BI->getArgs().size() == BI->getDestBB()->args_size(),
              "branch has wrong number of arguments for dest bb");
      require(std::equal(BI->getArgs().begin(), BI->getArgs().end(),
                         BI->getDestBB()->args_begin(),
                         [&](SILValue branchArg, SILArgument *bbArg) {
                           return verifyBranchArgs(branchArg, bbArg);
                         }),
              "branch argument types do not match arguments for dest bb");
    }
  
    void checkCondBranchInst(CondBranchInst *CBI) {
      // It is important that cond_br keeps an i1 type. ARC Sequence Opts assumes
      // that cond_br does not use reference counted values or decrement reference
      // counted values under the assumption that the instruction that computes
      // the i1 is the use/decrement that ARC cares about and that after that
      // instruction is evaluated, the scalar i1 has a different identity and the
      // object can be deallocated.
      require(CBI->getCondition()->getType() ==
               SILType::getBuiltinIntegerType(1,
                                   CBI->getCondition()->getType().getASTContext()),
              "condition of conditional branch must have Int1 type");
  
      require(CBI->getTrueArgs().size() == CBI->getTrueBB()->args_size(),
              "true branch has wrong number of arguments for dest bb");
      require(CBI->getTrueBB() != CBI->getFalseBB(),
              "identical destinations");
      require(std::equal(CBI->getTrueArgs().begin(), CBI->getTrueArgs().end(),
                         CBI->getTrueBB()->args_begin(),
                         [&](SILValue branchArg, SILArgument *bbArg) {
                           return verifyBranchArgs(branchArg, bbArg);
                         }),
              "true branch argument types do not match arguments for dest bb");
  
      require(CBI->getFalseArgs().size() == CBI->getFalseBB()->args_size(),
              "false branch has wrong number of arguments for dest bb");
      require(std::equal(CBI->getFalseArgs().begin(), CBI->getFalseArgs().end(),
                         CBI->getFalseBB()->args_begin(),
                         [&](SILValue branchArg, SILArgument *bbArg) {
                           return verifyBranchArgs(branchArg, bbArg);
                         }),
              "false branch argument types do not match arguments for dest bb");
    }
  
    void checkDynamicMethodBranchInst(DynamicMethodBranchInst *DMBI) {
      SILType operandType = DMBI->getOperand()->getType();
  
      require(DMBI->getMember().getDecl()->isObjC(), "method must be @objc");
      if (!DMBI->getMember().getDecl()->isInstanceMember()) {
        require(operandType.is<MetatypeType>(),
                "operand must have metatype type");
        require(operandType.castTo<MetatypeType>()
                  ->getInstanceType()->mayHaveSuperclass(),
                "operand must have metatype of class or class-bound type");
      }
  
      // Check that the branch argument is of the expected dynamic method type.
      require(DMBI->getHasMethodBB()->args_size() == 1,
              "true bb for dynamic_method_br must take an argument");
  
      auto bbArgTy = DMBI->getHasMethodBB()->args_begin()[0]->getType();
      require(getDynamicMethodType(operandType, DMBI->getMember())
                .getASTType()
                ->isBindableTo(bbArgTy.getASTType()),
              "bb argument for dynamic_method_br must be of the method's type");
    }
  
    void checkProjectBlockStorageInst(ProjectBlockStorageInst *PBSI) {
      require(PBSI->getOperand()->getType().isAddress(),
              "operand must be an address");
      auto storageTy = PBSI->getOperand()->getType().getAs<SILBlockStorageType>();
      require(storageTy, "operand must be a @block_storage type");
      
      require(PBSI->getType().isAddress(),
              "result must be an address");
      auto captureTy = PBSI->getType().getASTType();
      require(storageTy->getCaptureType() == captureTy,
              "result must be the capture type of the @block_storage type");
    }
    
    void checkInitBlockStorageHeaderInst(InitBlockStorageHeaderInst *IBSHI) {
      auto storage = IBSHI->getBlockStorage();
      require(storage->getType().isAddress(),
              "block storage operand must be an address");
  
      auto storageTy = storage->getType().getAs<SILBlockStorageType>();
      require(storageTy, "block storage operand must be a @block_storage type");
  
      auto captureTy = storageTy->getCaptureType();
      if (auto capturedFnTy = captureTy->getAs<SILFunctionType>()) {
        if (capturedFnTy->isNoEscape()) {
          // If the capture is a noescape function then it must be possible to
          // locally determine the value stored to initialize the storage for the
          // capture. This is required to diagnose static exclusivity violations
          // when a noescape closure is converted to a noescape block that
          // is then passed to a function.
          auto *storageProjection =
             storage->getSingleUserOfType<ProjectBlockStorageInst>();
          require(storageProjection,
                  "block storage operand with noescape capture must have "
                  "projection from block");
  
          auto *storeInst = storageProjection->getSingleUserOfType<StoreInst>();
          require(storeInst,
                  "block storage operand with noescape capture must have "
                  "store to projection");
        }
      }
  
      require(IBSHI->getInvokeFunction()->getType().isObject(),
              "invoke function operand must be a value");
      auto invokeTy
        = IBSHI->getInvokeFunction()->getType().getAs<SILFunctionType>();
      require(invokeTy, "invoke function operand must be a function");
      require(invokeTy->getRepresentation()
                == SILFunctionType::Representation::CFunctionPointer,
              "invoke function operand must be a c function");
      require(invokeTy->getParameters().size() >= 1,
              "invoke function must take at least one parameter");
      require(!invokeTy->getGenericSignature() ||
              invokeTy->getExtInfo().isPseudogeneric(),
              "invoke function must not take reified generic parameters");
      
      invokeTy = checkApplySubstitutions(IBSHI->getSubstitutions(),
                                      SILType::getPrimitiveObjectType(invokeTy));
      
      auto storageParam = invokeTy->getParameters()[0];
      require(storageParam.getConvention() ==
              ParameterConvention::Indirect_InoutAliasable,
              "invoke function must take block storage as @inout_aliasable "
              "parameter");
      require(storageParam.getType() == storageTy,
              "invoke function must take block storage type as first parameter");
      
      require(IBSHI->getType().isObject(), "result must be a value");
      auto blockTy = IBSHI->getType().getAs<SILFunctionType>();
      require(blockTy, "result must be a function");
      require(blockTy->getRepresentation() == SILFunctionType::Representation::Block,
              "result must be a cdecl block function");
      require(blockTy->getResults() == invokeTy->getResults(),
              "result must have same results as invoke function");
  
      require(blockTy->getParameters().size() + 1
                == invokeTy->getParameters().size(),
            "result must match all parameters of invoke function but the first");
      auto blockParams = blockTy->getParameters();
      auto invokeBlockParams = invokeTy->getParameters().slice(1);
      for (unsigned i : indices(blockParams)) {
        require(blockParams[i] == invokeBlockParams[i],
            "result must match all parameters of invoke function but the first");
      }
    }
    
    void checkObjCProtocolInst(ObjCProtocolInst *OPI) {
      require(OPI->getProtocol()->isObjC(),
              "objc_protocol must be applied to an @objc protocol");
      auto classTy = OPI->getType();
      require(classTy.isObject(), "objc_protocol must produce a value");
      auto classDecl = classTy.getClassOrBoundGenericClass();
      require(classDecl, "objc_protocol must produce a class instance");
      require(classDecl->getName() == F.getASTContext().Id_Protocol,
              "objc_protocol must produce an instance of ObjectiveC.Protocol class");
      require(classDecl->getModuleContext()->getName() == F.getASTContext().Id_ObjectiveC,
              "objc_protocol must produce an instance of ObjectiveC.Protocol class");
    }
    
    void checkObjCMetatypeToObjectInst(ObjCMetatypeToObjectInst *OMOI) {
      require(OMOI->getOperand()->getType().isObject(),
              "objc_metatype_to_object must take a value");
      auto fromMetaTy = OMOI->getOperand()->getType().getAs<MetatypeType>();
      require(fromMetaTy, "objc_metatype_to_object must take an @objc metatype value");
      require(fromMetaTy->getRepresentation() == MetatypeRepresentation::ObjC,
              "objc_metatype_to_object must take an @objc metatype value");
      require(OMOI->getType().isObject(),
              "objc_metatype_to_object must produce a value");
      require(OMOI->getType().getASTType()->isAnyObject(),
              "objc_metatype_to_object must produce an AnyObject value");
    }
  
    void checkObjCExistentialMetatypeToObjectInst(
                                      ObjCExistentialMetatypeToObjectInst *OMOI) {
      require(OMOI->getOperand()->getType().isObject(),
              "objc_metatype_to_object must take a value");
      auto fromMetaTy = OMOI->getOperand()->getType()
        .getAs<ExistentialMetatypeType>();
      require(fromMetaTy, "objc_metatype_to_object must take an @objc existential metatype value");
      require(fromMetaTy->getRepresentation() == MetatypeRepresentation::ObjC,
              "objc_metatype_to_object must take an @objc existential metatype value");
      require(OMOI->getType().isObject(),
              "objc_metatype_to_object must produce a value");
      require(OMOI->getType().getASTType()->isAnyObject(),
              "objc_metatype_to_object must produce an AnyObject value");
    }
    
    void checkKeyPathInst(KeyPathInst *KPI) {
      auto kpTy = KPI->getType();
      
      require(kpTy.isObject(), "keypath result must be an object type");
      
      auto kpBGT = kpTy.getAs<BoundGenericType>();
      require(kpBGT, "keypath result must be a generic type");
      auto &C = F.getASTContext();
      require(kpBGT->getDecl() == C.getKeyPathDecl()
              || kpBGT->getDecl() == C.getWritableKeyPathDecl()
              || kpBGT->getDecl() == C.getReferenceWritableKeyPathDecl(),
              "keypath result must be a key path type");
      
      auto baseTy = CanType(kpBGT->getGenericArgs()[0]);
      auto pattern = KPI->getPattern();
      SubstitutionMap patternSubs = KPI->getSubstitutions();
      require(baseTy == pattern->getRootType().subst(patternSubs)->getCanonicalType(),
              "keypath root type should match root type of keypath pattern");
  
      auto leafTy = CanType(kpBGT->getGenericArgs()[1]);
      require(leafTy == pattern->getValueType().subst(patternSubs)->getCanonicalType(),
              "keypath value type should match value type of keypath pattern");
      
      {
        Lowering::GenericContextScope scope(F.getModule().Types,
                                            pattern->getGenericSignature());
        
        for (auto &component : pattern->getComponents()) {
          bool hasIndices;
          switch (component.getKind()) {
          case KeyPathPatternComponent::Kind::GettableProperty:
          case KeyPathPatternComponent::Kind::SettableProperty:
            hasIndices = !component.getSubscriptIndices().empty();
            break;
          
          case KeyPathPatternComponent::Kind::StoredProperty:
          case KeyPathPatternComponent::Kind::OptionalChain:
          case KeyPathPatternComponent::Kind::OptionalWrap:
          case KeyPathPatternComponent::Kind::OptionalForce:
          case KeyPathPatternComponent::Kind::TupleElement:
            hasIndices = false;
            break;
          }
        
          verifyKeyPathComponent(F.getModule(), F.getResilienceExpansion(),
            [&](bool reqt, StringRef message) { _require(reqt, message); },
            baseTy,
            leafTy,
            component,
            KPI->getAllOperands(),
            KPI->getPattern()->getGenericSignature(),
            KPI->getSubstitutions(),
            /*property descriptor*/false,
            hasIndices);
        }
      }
      require(CanType(baseTy) == CanType(leafTy),
              "final component should match leaf value type of key path type");
    }
  
    void checkIsEscapingClosureInst(IsEscapingClosureInst *IEC) {
      // The closure operand is allowed to be an optional closure.
      auto operandType = IEC->getOperand()->getType();
      if (operandType.getOptionalObjectType())
        operandType = operandType.getOptionalObjectType();
  
      auto fnType = operandType.getAs<SILFunctionType>();
      require(fnType && fnType->getExtInfo().hasContext() &&
                  !fnType->isNoEscape() &&
                  fnType->getExtInfo().getRepresentation() ==
                      SILFunctionTypeRepresentation::Thick,
              "is_escaping_closure must have a thick "
              "function operand");
      require(IEC->getVerificationType() == IsEscapingClosureInst::ObjCEscaping ||
                  IEC->getVerificationType() ==
                      IsEscapingClosureInst::WithoutActuallyEscaping,
              "unknown verfication type");
    }
  
    // This verifies that the entry block of a SIL function doesn't have
    // any predecessors and also verifies the entry point arguments.
    void verifyEntryBlock(SILBasicBlock *entry) {
      require(entry->pred_empty(), "entry block cannot have predecessors");
  
      LLVM_DEBUG(llvm::dbgs() << "Argument types for entry point BB:\n";
                 for (auto *arg
                      : make_range(entry->args_begin(), entry->args_end()))
                     arg->getType()
                         .dump();
                 llvm::dbgs() << "Input types for SIL function type ";
                 F.getLoweredFunctionType()->print(llvm::dbgs());
                 llvm::dbgs() << ":\n";
                 for (auto paramTy
                      : fnConv.getParameterSILTypes()) { paramTy.dump(); });
  
      require(entry->args_size() == (fnConv.getNumIndirectSILResults()
                                     + fnConv.getNumParameters()),
              "entry point has wrong number of arguments");
  
      bool matched = true;
      auto argI = entry->args_begin();
  
      auto check = [&](const char *what, SILType ty) {
        auto mappedTy = F.mapTypeIntoContext(ty);
        SILArgument *bbarg = *argI;
        ++argI;
        if (bbarg->getType() != mappedTy) {
          llvm::errs() << what << " type mismatch!\n";
          llvm::errs() << "  argument: "; bbarg->dump();
          llvm::errs() << "  expected: "; mappedTy.dump();
          matched = false;
        }
  
        // If we do not have qualified ownership, do not check ownership.
        if (!F.hasOwnership()) {
          return;
        }
  
        auto ownershipkind = ValueOwnershipKind(
            F, mappedTy, fnConv.getSILArgumentConvention(bbarg->getIndex()));
  
        if (bbarg->getOwnershipKind() != ownershipkind) {
          llvm::errs() << what << " ownership kind mismatch!\n";
          llvm::errs() << "  argument: " << bbarg->getOwnershipKind() << '\n';
          llvm::errs() << "  expected: " << ownershipkind << '\n';
          matched = false;
        }
      };
  
      for (auto result : fnConv.getIndirectSILResults()) {
        assert(fnConv.isSILIndirect(result));
        check("result", fnConv.getSILType(result));
      }
      for (auto param : F.getLoweredFunctionType()->getParameters()) {
        check("parameter", fnConv.getSILType(param));
      }
  
      require(matched, "entry point argument types do not match function type");
  
      // TBAA requirement for all address arguments.
      require(std::equal(entry->args_begin() + fnConv.getNumIndirectSILResults(),
                         entry->args_end(),
                         fnConv.funcTy->getParameters().begin(),
                         [&](SILArgument *bbarg, SILParameterInfo paramInfo) {
                           if (!bbarg->getType().isAddress())
                             return true;
                           switch (paramInfo.getConvention()) {
                           default:
                             return false;
                           case ParameterConvention::Indirect_In:
                           case ParameterConvention::Indirect_In_Constant:
                           case ParameterConvention::Indirect_Inout:
                           case ParameterConvention::Indirect_InoutAliasable:
                           case ParameterConvention::Indirect_In_Guaranteed:
                             return true;
                           }
                         }),
              "entry point address argument must have an indirect calling "
              "convention");
    }
  
    void verifyEpilogBlocks(SILFunction *F) {
      bool FoundReturnBlock = false;
      bool FoundThrowBlock = false;
      bool FoundUnwindBlock = false;
      for (auto &BB : *F) {
        if (isa<ReturnInst>(BB.getTerminator())) {
          require(!FoundReturnBlock,
                  "more than one return block in function");
          FoundReturnBlock = true;
        } else if (isa<ThrowInst>(BB.getTerminator())) {
          require(!FoundThrowBlock,
                  "more than one throw block in function");
          FoundThrowBlock = true;
        } else if (isa<UnwindInst>(BB.getTerminator())) {
          require(!FoundUnwindBlock,
                  "more than one unwind block in function");
          FoundUnwindBlock = true;
        } else {
          assert(!BB.getTerminator()->isFunctionExiting());
        }
      }
    }
  
    bool isUnreachableAlongAllPathsStartingAt(
        SILBasicBlock *StartBlock, SmallPtrSetImpl<SILBasicBlock *> &Visited) {
      if (isa<UnreachableInst>(StartBlock->getTerminator()))
        return true;
      else if (isa<ReturnInst>(StartBlock->getTerminator()))
        return false;
      else if (isa<ThrowInst>(StartBlock->getTerminator()))
        return false;
  
      // Recursively check all successors.
      for (auto *SuccBB : StartBlock->getSuccessorBlocks())
        if (!Visited.insert(SuccBB).second)
          if (!isUnreachableAlongAllPathsStartingAt(SuccBB, Visited))
            return false;
  
      return true;
    }
  
    void verifySILFunctionType(CanSILFunctionType FTy) {
      // Make sure that if FTy's calling convention implies that it must have a
      // self parameter.
      require(!FTy->hasSelfParam() || !FTy->getParameters().empty(),
              "Functions with a calling convention with self parameter must "
              "have at least one argument for self.");
    }
  
    struct VerifyFlowSensitiveRulesDetails {
      enum CFGState {
        /// No special rules are in play.
        Normal,
        /// We've followed the resume edge of a yield in a yield_once coroutine.
        YieldOnceResume,
        /// We've followed the unwind edge of a yield.
        YieldUnwind
      };
  
      struct BBState {
        std::vector<SingleValueInstruction*> Stack;
  
        /// Contents: BeginAccessInst*, BeginApplyInst*.
        std::set<SILInstruction*> ActiveOps;
  
        CFGState CFG = Normal;
      };
    };
  
    /// Verify the various control-flow-sensitive rules of SIL:
    ///
    /// - stack allocations and deallocations must obey a stack discipline
    /// - accesses must be uniquely ended
    /// - flow-sensitive states must be equivalent on all paths into a block
    void verifyFlowSensitiveRules(SILFunction *F) {
      // Do a traversal of the basic blocks.
      // Note that we intentionally don't verify these properties in blocks
      // that can't be reached from the entry block.
      llvm::DenseMap<SILBasicBlock*, VerifyFlowSensitiveRulesDetails::BBState> visitedBBs;
      SmallVector<SILBasicBlock*, 16> Worklist;
      visitedBBs.try_emplace(&*F->begin());
      Worklist.push_back(&*F->begin());
      while (!Worklist.empty()) {
        SILBasicBlock *BB = Worklist.pop_back_val();
        VerifyFlowSensitiveRulesDetails::BBState state = visitedBBs[BB];
        for (SILInstruction &i : *BB) {
          CurInstruction = &i;
  
          if (i.isAllocatingStack()) {
            state.Stack.push_back(cast<SingleValueInstruction>(&i));
  
          } else if (i.isDeallocatingStack()) {
            SILValue op = i.getOperand(0);
            require(!state.Stack.empty(),
                    "stack dealloc with empty stack");
            require(op == state.Stack.back(),
                    "stack dealloc does not match most recent stack alloc");
            state.Stack.pop_back();
  
          } else if (isa<BeginAccessInst>(i) || isa<BeginApplyInst>(i)) {
            bool notAlreadyPresent = state.ActiveOps.insert(&i).second;
            require(notAlreadyPresent,
                    "operation was not ended before re-beginning it");
  
          } else if (isa<EndAccessInst>(i) || isa<AbortApplyInst>(i) ||
                     isa<EndApplyInst>(i)) {
            if (auto beginOp = i.getOperand(0)->getDefiningInstruction()) {
              bool present = state.ActiveOps.erase(beginOp);
              require(present, "operation has already been ended");
            }
  
          } else if (auto term = dyn_cast<TermInst>(&i)) {
            if (term->isFunctionExiting()) {
              require(state.Stack.empty(),
                      "return with stack allocs that haven't been deallocated");
              require(state.ActiveOps.empty(),
                      "return with operations still active");
  
              if (isa<UnwindInst>(term)) {
                require(state.CFG == VerifyFlowSensitiveRulesDetails::YieldUnwind,
                        "encountered 'unwind' when not on unwind path");
              } else {
                require(state.CFG != VerifyFlowSensitiveRulesDetails::YieldUnwind,
                        "encountered 'return' or 'throw' when on unwind path");
                if (isa<ReturnInst>(term) &&
                    F->getLoweredFunctionType()->getCoroutineKind() ==
                      SILCoroutineKind::YieldOnce &&
                    F->getModule().getStage() != SILStage::Raw) {
                  require(state.CFG == VerifyFlowSensitiveRulesDetails::YieldOnceResume,
                          "encountered 'return' before yielding a value in "
                          "yield_once coroutine");
                }
              }
            }
  
            if (isa<YieldInst>(term)) {
              require(state.CFG != VerifyFlowSensitiveRulesDetails::YieldOnceResume,
                      "encountered multiple 'yield's along single path");
              require(state.CFG == VerifyFlowSensitiveRulesDetails::Normal,
                      "encountered 'yield' on abnormal CFG path");
            }
  
            auto successors = term->getSuccessors();
            for (auto i : indices(successors)) {
              SILBasicBlock *succBB = successors[i].getBB();
  
              // Optimistically try to set our current state as the state
              // of the successor.  We can use a move on the final successor;
              // note that if the insertion fails, the move won't actually
              // happen, which is important because we'll still need it
              // to compare against the already-recorded state for the block.
              auto insertResult =
                i + 1 == successors.size()
                  ? visitedBBs.try_emplace(succBB, std::move(state))
                  : visitedBBs.try_emplace(succBB, state);
  
              // If the insertion was successful, add the successor to the
              // worklist and continue.
              if (insertResult.second) {
                Worklist.push_back(succBB);
  
                // If we're following a 'yield', update the CFG state:
                if (isa<YieldInst>(term)) {
                  // Enforce that the unwind logic is segregated in all stages.
                  if (i == 1) {
                    insertResult.first->second.CFG = VerifyFlowSensitiveRulesDetails::YieldUnwind;
  
                  // We check the yield_once rule in the mandatory analyses,
                  // so we can't assert it yet in the raw stage.
                  } else if (F->getLoweredFunctionType()->getCoroutineKind()
                               == SILCoroutineKind::YieldOnce && 
                             F->getModule().getStage() != SILStage::Raw) {
                    insertResult.first->second.CFG = VerifyFlowSensitiveRulesDetails::YieldOnceResume;
                  }
                }
  
                continue;
              }
  
              // This rule is checked elsewhere, but we'd want to assert it
              // here anyway.
              require(!isa<YieldInst>(term),
                      "successor of 'yield' should not be encountered twice");
  
              // Check that the stack height is consistent coming from all entry
              // points into this BB. We only care about consistency if there is
              // a possible return from this function along the path starting at
              // this successor bb.  (FIXME: Why? Infinite loops should still
              // preserve consistency...)
              auto isUnreachable = [&] {
                SmallPtrSet<SILBasicBlock *, 16> visited;
                return isUnreachableAlongAllPathsStartingAt(succBB, visited);
              };
              
              const auto &foundState = insertResult.first->second;
              require(state.Stack == foundState.Stack || isUnreachable(),
                      "inconsistent stack heights entering basic block");
              require(state.ActiveOps == foundState.ActiveOps || isUnreachable(),
                      "inconsistent active-operations sets entering basic block");
              require(state.CFG == foundState.CFG,
                      "inconsistent coroutine states entering basic block");
            }
          }
        }
      }
    }
  
    void verifyBranches(const SILFunction *F) {
      // Verify that there is no non_condbr critical edge.
      auto isCriticalEdgePred = [](const TermInst *T, unsigned EdgeIdx) {
        assert(T->getSuccessors().size() > EdgeIdx && "Not enough successors");
  
        // A critical edge has more than one outgoing edges from the source
        // block.
        auto SrcSuccs = T->getSuccessors();
        if (SrcSuccs.size() <= 1)
          return false;
  
        // And its destination block has more than one predecessor.
        SILBasicBlock *DestBB = SrcSuccs[EdgeIdx];
        assert(!DestBB->pred_empty() && "There should be a predecessor");
        if (DestBB->getSinglePredecessorBlock())
          return false;
  
        return true;
      };
  
      for (auto &BB : *F) {
        const TermInst *TI = BB.getTerminator();
        CurInstruction = TI;
  
        // Check for non-cond_br critical edges.
        auto *CBI = dyn_cast<CondBranchInst>(TI);
        if (!CBI) {
          for (unsigned Idx = 0, e = BB.getSuccessors().size(); Idx != e; ++Idx) {
            require(!isCriticalEdgePred(TI, Idx),
                    "non cond_br critical edges not allowed");
          }
          continue;
        }
        // In ownership qualified SIL, ban critical edges from CondBranchInst that
        // have non-trivial arguments.
        //
        // FIXME: it would be far simpler to ban all critical edges in general.
        if (!F->hasOwnership())
          continue;
  
        if (isCriticalEdgePred(CBI, CondBranchInst::TrueIdx)) {
          require(
              llvm::all_of(CBI->getTrueArgs(),
                           [](SILValue V) -> bool {
                             return V.getOwnershipKind() ==
                                    ValueOwnershipKind::Any;
                           }),
              "cond_br with critical edges must not have a non-trivial value");
        }
        if (isCriticalEdgePred(CBI, CondBranchInst::FalseIdx)) {
          require(
              llvm::all_of(CBI->getFalseArgs(),
                           [](SILValue V) -> bool {
                             return V.getOwnershipKind() ==
                                    ValueOwnershipKind::Any;
                           }),
              "cond_br with critical edges must not have a non-trivial value");
        }
      }
    }
  
    void verifyOpenedArchetypes(SILFunction *F) {
      require(OpenedArchetypes.getFunction() == F,
             "Wrong SILFunction provided to verifyOpenedArchetypes");
      // Check that definitions of all opened archetypes from
      // OpenedArchetypesDefs are existing instructions
      // belonging to the function F.
      for (auto KV: OpenedArchetypes.getOpenedArchetypeDefs()) {
        require(getOpenedArchetypeOf(CanType(KV.first)),
                "Only opened archetypes should be registered in SILFunction");
        auto Def = cast<SILInstruction>(KV.second);
        require(Def->getFunction() == F, 
                "Definition of every registered opened archetype should be an"
                " existing instruction in a current SILFunction");
      }
    }
  
    /// This pass verifies that there are no hole in debug scopes at -Onone.
    void verifyDebugScopeHoles(SILBasicBlock *BB) {
      if (!VerifyDIHoles)
        return;
  
      // This check only makes sense at -Onone. Optimizations,
      // e.g. inlining, can move scopes around.
      llvm::DenseSet<const SILDebugScope *> AlreadySeenScopes;
      if (BB->getParent()->getEffectiveOptimizationMode() !=
          OptimizationMode::NoOptimization)
        return;
  
      // Exit early if this BB is empty.
      if (BB->empty())
        return;
  
      const SILDebugScope *LastSeenScope = nullptr;
      for (SILInstruction &SI : *BB) {
        if (SI.isMetaInstruction())
          continue;
        LastSeenScope = SI.getDebugScope();
        AlreadySeenScopes.insert(LastSeenScope);
        break;
      }
      for (SILInstruction &SI : *BB) {
        if (SI.isMetaInstruction())
          continue;
  
        // If we haven't seen this debug scope yet, update the
        // map and go on.
        auto *DS = SI.getDebugScope();
        assert(DS && "Each instruction should have a debug scope");
        if (!AlreadySeenScopes.count(DS)) {
          AlreadySeenScopes.insert(DS);
          LastSeenScope = DS;
          continue;
        }
  
        // Otherwise, we're allowed to re-enter a scope only if
        // the scope is an ancestor of the scope we're currently leaving.
        auto isAncestorScope = [](const SILDebugScope *Cur,
                                  const SILDebugScope *Previous) {
          const SILDebugScope *Tmp = Previous;
          assert(Tmp && "scope can't be null");
          while (Tmp) {
            PointerUnion<const SILDebugScope *, SILFunction *> Parent =
                Tmp->Parent;
            auto *ParentScope = Parent.dyn_cast<const SILDebugScope *>();
            if (!ParentScope)
              break;
            if (ParentScope == Cur)
              return true;
            Tmp = ParentScope;
          }
          return false;
        };
  
        if (isAncestorScope(DS, LastSeenScope)) {
          LastSeenScope = DS;
          continue;
        }
        if (DS != LastSeenScope) {
          LLVM_DEBUG(llvm::dbgs() << "Broken instruction!\n"; SI.dump());
          LLVM_DEBUG(llvm::dbgs() << "Please report a bug on bugs.swift.org\n");
          LLVM_DEBUG(llvm::dbgs() <<
            "Pass -Xllvm -verify-di-holes=false to disable the verification\n");
          require(
              DS == LastSeenScope,
              "Basic block contains a non-contiguous lexical scope at -Onone");
        }
      }
    }
  
    void visitSILBasicBlock(SILBasicBlock *BB) {
      // Make sure that each of the successors/predecessors of this basic block
      // have this basic block in its predecessor/successor list.
      for (const auto *SuccBB : BB->getSuccessorBlocks()) {
        require(SuccBB->isPredecessorBlock(BB),
                "Must be a predecessor of each successor.");
      }
  
      for (const SILBasicBlock *PredBB : BB->getPredecessorBlocks()) {
        require(PredBB->isSuccessorBlock(BB),
                "Must be a successor of each predecessor.");
      }
      
      SILInstructionVisitor::visitSILBasicBlock(BB);
      verifyDebugScopeHoles(BB);
    }
  
    void visitBasicBlockArguments(SILBasicBlock *BB) {
      CurInstruction = nullptr;
      for (auto argI = BB->args_begin(), argEnd = BB->args_end(); argI != argEnd;
           ++argI)
        visitSILArgument(*argI);
    }
  
    void visitSILBasicBlocks(SILFunction *F) {
      // Visit all basic blocks in the RPOT order.
      // This ensures that any open_existential instructions, which
      // open archetypes, are seen before the uses of these archetypes.
      llvm::ReversePostOrderTraversal<SILFunction *> RPOT(F);
      llvm::DenseSet<SILBasicBlock *> VisitedBBs;
      for (auto Iter = RPOT.begin(), E = RPOT.end(); Iter != E; ++Iter) {
        auto *BB = *Iter;
        VisitedBBs.insert(BB);
        visitSILBasicBlock(BB);
      }
  
      // Visit all basic blocks that were not visited during the RPOT traversal,
      // e.g. unreachable basic blocks.
      for (auto &BB : *F) {
        if (VisitedBBs.count(&BB))
          continue;
        visitSILBasicBlock(&BB);
      }
    }
  
    void visitSILFunction(SILFunction *F) {
      PrettyStackTraceSILFunction stackTrace("verifying", F);
  
      CanSILFunctionType FTy = F->getLoweredFunctionType();
      verifySILFunctionType(FTy);
  
      if (F->isExternalDeclaration()) {
        if (F->hasForeignBody())
          return;
  
        assert(F->isAvailableExternally() &&
               "external declaration of internal SILFunction not allowed");
        // If F is an external declaration, there is nothing further to do,
        // return.
        return;
      }
  
      assert(!F->hasForeignBody());
  
      // Make sure that our SILFunction only has context generic params if our
      // SILFunctionType is non-polymorphic.
      if (F->getGenericEnvironment()) {
        require(FTy->isPolymorphic(),
                "non-generic function definitions cannot have a "
                "generic environment");
      } else {
        require(!FTy->isPolymorphic(),
                "generic function definition must have a generic environment");
      }
  
      // Otherwise, verify the body of the function.
      verifyEntryBlock(&*F->getBlocks().begin());
      verifyEpilogBlocks(F);
      verifyFlowSensitiveRules(F);
      verifyBranches(F);
  
      visitSILBasicBlocks(F);
  
      // Verify archetypes after all basic blocks are visited,
      // because we build the map of archetypes as we visit the
      // instructions.
      verifyOpenedArchetypes(F);
    }
  
    void verify() {
      visitSILFunction(const_cast<SILFunction*>(&F));
    }
  };
  } // end anonymous namespace
  
  #undef require
  #undef requireObjectType
  
  //===----------------------------------------------------------------------===//
  //                     Out of Line Verifier Run Functions
  //===----------------------------------------------------------------------===//
  
  /// verify - Run the SIL verifier to make sure that the SILFunction follows
  /// invariants.
  void SILFunction::verify(bool SingleFunction) const {
  #ifdef NDEBUG
    if (!getModule().getOptions().VerifyAll)
      return;
  #endif
    // Please put all checks in visitSILFunction in SILVerifier, not here. This
    // ensures that the pretty stack trace in the verifier is included with the
    // back trace when the verifier crashes.
    SILVerifier(*this, SingleFunction).verify();
  }
  
  void SILFunction::verifyCriticalEdges() const {
  #ifdef NDEBUG
    if (!getModule().getOptions().VerifyAll)
      return;
  #endif
    SILVerifier(*this, /*SingleFunction=*/true).verifyBranches(this);
  }
  
  /// Verify that a property descriptor follows invariants.
  void SILProperty::verify(const SILModule &M) const {
  #ifdef NDEBUG
    if (!M.getOptions().VerifyAll)
      return;
  #endif
  
    auto *decl = getDecl();
    auto *dc = decl->getInnermostDeclContext();
    
    // TODO: base type for global/static descriptors
    auto sig = dc->getGenericSignatureOfContext();
    auto baseTy = dc->getInnermostTypeContext()->getSelfInterfaceType()
                    ->getCanonicalType(sig);
    auto leafTy = decl->getValueInterfaceType()->getCanonicalType(sig);
    SubstitutionMap subs;
    if (sig) {
      auto env = dc->getGenericEnvironmentOfContext();
      subs = env->getForwardingSubstitutionMap();
      baseTy = env->mapTypeIntoContext(baseTy)->getCanonicalType();
      leafTy = env->mapTypeIntoContext(leafTy)->getCanonicalType();
    }
    bool hasIndices = false;
    if (auto subscript = dyn_cast<SubscriptDecl>(decl)) {
      hasIndices = subscript->getIndices()->size() != 0;
    }
  
    auto canSig = sig ? sig->getCanonicalSignature() : nullptr;
    Lowering::GenericContextScope scope(M.Types, canSig);
  
    auto require = [&](bool reqt, StringRef message) {
        if (!reqt) {
          llvm::errs() << message << "\n";
          assert(false && "invoking standard assertion failure");
        }
      };
  
    if (auto &component = getComponent()) {
      verifyKeyPathComponent(const_cast<SILModule&>(M),
                             ResilienceExpansion::Maximal,
                             require,
                             baseTy,
                             leafTy,
                             *component,
                             {},
                             canSig,
                             subs,
                             /*property descriptor*/true,
                             hasIndices);
      // verifyKeyPathComponent updates baseTy to be the projected type of the
      // component, which should be the same as the type of the declared storage
      require(baseTy == leafTy,
              "component type of property descriptor should match type of storage");
    }
  }
  
  /// Verify that a vtable follows invariants.
  void SILVTable::verify(const SILModule &M) const {
  #ifdef NDEBUG
    if (!M.getOptions().VerifyAll)
      return;
  #endif
    for (auto &entry : getEntries()) {
      // All vtable entries must be decls in a class context.
      assert(entry.Method.hasDecl() && "vtable entry is not a decl");
      auto baseInfo = M.Types.getConstantInfo(entry.Method);
      ValueDecl *decl = entry.Method.getDecl();
  
      assert((!isa<AccessorDecl>(decl)
              || !cast<AccessorDecl>(decl)->isObservingAccessor())
             && "observing accessors shouldn't have vtable entries");
  
      // For ivar destroyers, the decl is the class itself.
      ClassDecl *theClass;
      if (entry.Method.kind == SILDeclRef::Kind::IVarDestroyer)
        theClass = dyn_cast<ClassDecl>(decl);
      else
        theClass = dyn_cast<ClassDecl>(decl->getDeclContext());
  
      assert(theClass && "vtable entry must refer to a class member");
  
      // The class context must be the vtable's class, or a superclass thereof.
      assert(theClass->isSuperclassOf(getClass()) &&
             "vtable entry must refer to a member of the vtable's class");
  
      // All function vtable entries must be at their natural uncurry level.
      assert(!entry.Method.isCurried && "vtable entry must not be curried");
  
      // Foreign entry points shouldn't appear in vtables.
      assert(!entry.Method.isForeign && "vtable entry must not be foreign");
      
      // The vtable entry must be ABI-compatible with the overridden vtable slot.
      SmallString<32> baseName;
      {
        llvm::raw_svector_ostream os(baseName);
        entry.Method.print(os);
      }
  
      if (M.getStage() != SILStage::Lowered) {
        SILVerifier(*entry.Implementation)
            .requireABICompatibleFunctionTypes(
                baseInfo.getSILType().castTo<SILFunctionType>(),
                entry.Implementation->getLoweredFunctionType(),
                "vtable entry for " + baseName + " must be ABI-compatible");
      }
    }
  }
  
  /// Verify that a witness table follows invariants.
  void SILWitnessTable::verify(const SILModule &M) const {
  #ifdef NDEBUG
    if (!M.getOptions().VerifyAll)
      return;
  #endif
    if (isDeclaration())
      assert(getEntries().empty() &&
             "A witness table declaration should not have any entries.");
  
    for (const Entry &E : getEntries())
      if (E.getKind() == SILWitnessTable::WitnessKind::Method) {
        SILFunction *F = E.getMethodWitness().Witness;
        if (F) {
          // If a SILWitnessTable is going to be serialized, it must only
          // reference public or serializable functions.
          if (isSerialized()) {
            assert(F->hasValidLinkageForFragileRef() &&
                   "Fragile witness tables should not reference "
                   "less visible functions.");
          }
  
          assert(F->getLoweredFunctionType()->getRepresentation() ==
                 SILFunctionTypeRepresentation::WitnessMethod &&
                 "Witnesses must have witness_method representation.");
        }
      }
  }
  
  /// Verify that a default witness table follows invariants.
  void SILDefaultWitnessTable::verify(const SILModule &M) const {
  #ifndef NDEBUG
    for (const Entry &E : getEntries()) {
      // FIXME: associated type witnesses.
      if (!E.isValid() || E.getKind() != SILWitnessTable::Method)
        continue;
  
      SILFunction *F = E.getMethodWitness().Witness;
  
  #if 0
      // FIXME: For now, all default witnesses are private.
      assert(F->hasValidLinkageForFragileRef() &&
             "Default witness tables should not reference "
             "less visible functions.");
  #endif
  
      assert(F->getLoweredFunctionType()->getRepresentation() ==
             SILFunctionTypeRepresentation::WitnessMethod &&
             "Default witnesses must have witness_method representation.");
    }
  #endif
  }
  
  /// Verify that a global variable follows invariants.
  void SILGlobalVariable::verify() const {
  #ifdef NDEBUG
    if (!getModule().getOptions().VerifyAll)
      return;
  #endif
    assert(getLoweredType().isObject()
           && "global variable cannot have address type");
  
    // Verify the static initializer.
    for (const SILInstruction &I : StaticInitializerBlock) {
      assert(isValidStaticInitializerInst(&I, getModule()) &&
             "illegal static initializer");
      auto init = cast<SingleValueInstruction>(&I);
      if (init == &StaticInitializerBlock.back()) {
        assert(init->use_empty() && "Init value must not have another use");
      } else {
        assert(!init->use_empty() && "dead instruction in static initializer");
        assert(!isa<ObjectInst>(init) &&
               "object instruction is only allowed for final initial value");
      }
      assert(I.getParent() == &StaticInitializerBlock);
    }
  }
  
  /// Verify the module.
  void SILModule::verify() const {
  #ifdef NDEBUG
    if (!getOptions().VerifyAll)
      return;
  #endif
    // Uniquing set to catch symbol name collisions.
    llvm::DenseSet<StringRef> symbolNames;
  
    // When merging partial modules, we only link functions from the current
    // module, without enabling "LinkAll" mode or running the SILLinker pass;
    // in this case, we need to relax some of the checks.
    bool SingleFunction = false;
    if (getOptions().MergePartialModules)
      SingleFunction = true;
  
    // Check all functions.
    for (const SILFunction &f : *this) {
      if (!symbolNames.insert(f.getName()).second) {
        llvm::errs() << "Symbol redefined: " << f.getName() << "!\n";
        assert(false && "triggering standard assertion failure routine");
      }
      f.verify(SingleFunction);
    }
  
    // Check all globals.
    for (const SILGlobalVariable &g : getSILGlobals()) {
      if (!symbolNames.insert(g.getName()).second) {
        llvm::errs() << "Symbol redefined: " << g.getName() << "!\n";
        assert(false && "triggering standard assertion failure routine");
      }
      g.verify();
    }
  
    // Check all vtables and the vtable cache.
    llvm::DenseSet<ClassDecl*> vtableClasses;
    unsigned EntriesSZ = 0;
    for (const SILVTable &vt : getVTables()) {
      if (!vtableClasses.insert(vt.getClass()).second) {
        llvm::errs() << "Vtable redefined: " << vt.getClass()->getName() << "!\n";
        assert(false && "triggering standard assertion failure routine");
      }
      vt.verify(*this);
      // Check if there is a cache entry for each vtable entry
      for (auto entry : vt.getEntries()) {
        if (VTableEntryCache.find({&vt, entry.Method}) == VTableEntryCache.end()) {
          llvm::errs() << "Vtable entry for function: "
                       << entry.Implementation->getName() << "not in cache!\n";
          assert(false && "triggering standard assertion failure routine");
        }
        EntriesSZ++;
      }
    }
    assert(EntriesSZ == VTableEntryCache.size() &&
           "Cache size is not equal to true number of VTable entries");
  
    // Check all witness tables.
    LLVM_DEBUG(llvm::dbgs() <<"*** Checking witness tables for duplicates ***\n");
    llvm::DenseSet<RootProtocolConformance*> wtableConformances;
    for (const SILWitnessTable &wt : getWitnessTables()) {
      LLVM_DEBUG(llvm::dbgs() << "Witness Table:\n"; wt.dump());
      auto conformance = wt.getConformance();
      if (!wtableConformances.insert(conformance).second) {
        llvm::errs() << "Witness table redefined: ";
        conformance->printName(llvm::errs());
        assert(false && "triggering standard assertion failure routine");
      }
      wt.verify(*this);
    }
  
    // Check all default witness tables.
    LLVM_DEBUG(llvm::dbgs() << "*** Checking default witness tables for "
               "duplicates ***\n");
    llvm::DenseSet<const ProtocolDecl *> defaultWitnessTables;
    for (const SILDefaultWitnessTable &wt : getDefaultWitnessTables()) {
      LLVM_DEBUG(llvm::dbgs() << "Default Witness Table:\n"; wt.dump());
      if (!defaultWitnessTables.insert(wt.getProtocol()).second) {
        llvm::errs() << "Default witness table redefined: ";
        wt.dump();
        assert(false && "triggering standard assertion failure routine");
      }
      wt.verify(*this);
    }
    
    // Check property descriptors.
    LLVM_DEBUG(llvm::dbgs() << "*** Checking property descriptors ***\n");
    for (auto &prop : getPropertyList()) {
      prop.verify(*this);
    }
  }
  
  /// Determine whether an instruction may not have a SILDebugScope.
  bool swift::maybeScopeless(SILInstruction &I) {
    if (I.getFunction()->isBare())
      return true;
    return !isa<DebugValueInst>(I) && !isa<DebugValueAddrInst>(I);
  }
  