swift-mirror/lib/SIL/IR/SILModule.cpp

//===--- SILModule.cpp - SILModule implementation -------------------------===//
//
// 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-module"

#include "swift/SIL/SILModule.h"
#include "Linker.h"
#include "swift/AST/ASTMangler.h"
#include "swift/AST/Decl.h"
#include "swift/AST/GenericEnvironment.h"
#include "swift/AST/ProtocolConformance.h"
#include "swift/Basic/Assertions.h"
#include "swift/ClangImporter/ClangModule.h"
#include "swift/SIL/FormalLinkage.h"
#include "swift/SIL/Notifications.h"
#include "swift/SIL/SILDebugScope.h"
#include "swift/SIL/SILDefaultOverrideTable.h"
#include "swift/SIL/SILMoveOnlyDeinit.h"
#include "swift/SIL/SILRemarkStreamer.h"
#include "swift/SIL/SILValue.h"
#include "swift/SIL/SILVisitor.h"
#include "swift/Serialization/SerializedSILLoader.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/YAMLTraits.h"
#include <functional>
using namespace swift;
using namespace Lowering;

STATISTIC(NumSlabsAllocated, "number of slabs allocated in SILModule");

class SILModule::SerializationCallback final
    : public DeserializationNotificationHandler {
  void didDeserialize(ModuleDecl *M, SILFunction *fn) override {
    updateLinkage(fn);
  }

  void didDeserialize(ModuleDecl *M, SILGlobalVariable *var) override {
    updateLinkage(var);

    if (!M->getASTContext().LangOpts.hasFeature(Feature::Embedded)) {
      // For globals we currently do not support available_externally.
      // In the interpreter it would result in two instances for a single
      // global: one in the imported module and one in the main module.
      //
      // We avoid that in Embedded Swift where we do actually link globals from
      // other modules into the client module.
      var->setDeclaration(true);
    }
  }

  void didDeserialize(ModuleDecl *M, SILVTable *vtable) override {
    // TODO: should vtables get linkage?
    //updateLinkage(vtable);
  }

  void didDeserialize(ModuleDecl *M, SILWitnessTable *wt) override {
    updateLinkage(wt);
  }

  template <class T> void updateLinkage(T *decl) {
    switch (decl->getLinkage()) {
    case SILLinkage::Public:
      decl->setLinkage(SILLinkage::PublicExternal);
      return;
    case SILLinkage::PublicNonABI:
      // PublicNonABI functions receive Shared linkage, so that
      // they have "link once" semantics when deserialized by multiple
      // translation units in the same Swift module.
      decl->setLinkage(SILLinkage::Shared);
      return;
    case SILLinkage::Package:
      decl->setLinkage(SILLinkage::PackageExternal);
      return;
    case SILLinkage::PackageNonABI: // Same as PublicNonABI
      decl->setLinkage(SILLinkage::Shared);
      return;
    case SILLinkage::Hidden:
      decl->setLinkage(SILLinkage::HiddenExternal);
      return;
    case SILLinkage::Private:
      llvm_unreachable("cannot make a private external symbol");
    case SILLinkage::PublicExternal:
    case SILLinkage::PackageExternal:
    case SILLinkage::HiddenExternal:
    case SILLinkage::Shared:
      return;
    }
  }

  StringRef getName() const override {
    return "SILModule::SerializationCallback";
  }
};

SILModule::SILModule(llvm::PointerUnion<FileUnit *, ModuleDecl *> context,
                     Lowering::TypeConverter &TC, const SILOptions &Options,
                     const IRGenOptions *irgenOptions)
    : Stage(SILStage::Raw), loweredAddresses(!Options.EnableSILOpaqueValues),
      indexTrieRoot(new IndexTrieNode()), Options(Options),
      irgenOptions(irgenOptions), serialized(false),
      regDeserializationNotificationHandlerForAllFuncOME(false),
      hasAccessMarkerHandler(false),
      prespecializedFunctionDeclsImported(false), SerializeSILAction(),
      Types(TC) {
  assert(!context.isNull());
  if (auto *file = context.dyn_cast<FileUnit *>()) {
    AssociatedDeclContext = file;
  } else {
    AssociatedDeclContext = cast<ModuleDecl *>(context);
  }
  TheSwiftModule = AssociatedDeclContext->getParentModule();

  // We always add the base SILModule serialization callback.
  std::unique_ptr<DeserializationNotificationHandler> callback(
      new SILModule::SerializationCallback());
  deserializationNotificationHandlers.add(std::move(callback));
}

SILModule::~SILModule() {
#ifndef NDEBUG
  NumSlabsAllocated += numAllocatedSlabs;
  assert(numAllocatedSlabs == freeSlabs.size() && "leaking slabs in SILModule");
#endif

  assert(!hasUnresolvedLocalArchetypeDefinitions());

  // Decrement ref count for each SILGlobalVariable with static initializers.
  for (SILGlobalVariable &v : silGlobals) {
    v.clear();
  }

  for (auto vt : vtables)
    vt->~SILVTable();

  for (auto deinit : moveOnlyDeinits)
    deinit->~SILMoveOnlyDeinit();

  // Drop everything functions in this module reference.
  //
  // This is necessary since the functions may reference each other.  We don't
  // need to worry about sil_witness_tables since witness tables reference each
  // other via protocol conformances and sil_vtables don't reference each other
  // at all.
  for (SILFunction &F : *this) {
    F.dropAllReferences();
    F.dropDynamicallyReplacedFunction();
    F.dropReferencedAdHocRequirementWitnessFunction();
    F.clearSpecializeAttrs();
  }

  for (SILFunction &F : *this) {
    F.eraseAllBlocks();
  }
  flushDeletedInsts();
}

std::unique_ptr<SILModule> SILModule::createEmptyModule(
    llvm::PointerUnion<FileUnit *, ModuleDecl *> context,
    Lowering::TypeConverter &TC, const SILOptions &Options,
    const IRGenOptions *irgenOptions) {
  return std::unique_ptr<SILModule>(new SILModule(context, TC, Options,
                                                  irgenOptions));
}

ASTContext &SILModule::getASTContext() const {
  return TheSwiftModule->getASTContext();
}

void *SILModule::allocate(unsigned Size, unsigned Align) const {
  if (getASTContext().LangOpts.UseMalloc)
    return AlignedAlloc(Size, Align);

  return BPA.Allocate(Size, Align);
}

FixedSizeSlab *SILModule::allocSlab() {
  if (freeSlabs.empty()) {
    numAllocatedSlabs++;
    return new (*this) FixedSizeSlab();
  }

  FixedSizeSlab *slab = &*freeSlabs.rbegin();
  freeSlabs.remove(*slab);
  return slab;
}

void SILModule::freeSlab(FixedSizeSlab *slab) {
  freeSlabs.push_back(*slab);
  assert(slab->overflowGuard == FixedSizeSlab::magicNumber);
}

void SILModule::freeAllSlabs(SlabList &slabs) {
  freeSlabs.splice(freeSlabs.end(), slabs);
}

void *SILModule::allocateInst(unsigned Size, unsigned Align) const {
  return AlignedAlloc(Size, Align);
}

void SILModule::willDeleteInstruction(SILInstruction *I) {
  // Update RootLocalArchetypeDefs.
  I->forEachDefinedLocalEnvironment([&](GenericEnvironment *genericEnv,
                                        SILValue dependency) {
    LocalArchetypeKey key = {genericEnv, I->getFunction()};
    // In case `willDeleteInstruction` is called twice for the
    // same instruction, we need to check if the archetype is really
    // still in the map for this instruction.
    if (RootLocalArchetypeDefs.lookup(key) == dependency)
      RootLocalArchetypeDefs.erase(key);
  });
}

void SILModule::scheduleForDeletion(SILInstruction *I) {
  I->dropAllReferences();
  scheduledForDeletion.push_back(I);
}

void SILModule::flushDeletedInsts() {
  for (SILInstruction *instToDelete : scheduledForDeletion) {
    SILInstruction::destroy(instToDelete);
    AlignedFree(instToDelete);
  }
  scheduledForDeletion.clear();
}

SILWitnessTable *
SILModule::lookUpWitnessTable(const ProtocolConformance *C) {
  // First try to lookup a specialized witness table for that conformance.
  if (auto *wt = lookUpWitnessTable(C, /*isSpecialized=*/true)) {
    return wt;
  }
  return lookUpWitnessTable(C, /*isSpecialized=*/false);
}

SILWitnessTable *
SILModule::lookUpWitnessTable(const ProtocolConformance *C, bool isSpecialized) {
  assert(C && "null conformance passed to lookUpWitnessTable");

  if (isSpecialized) {
    // First try to lookup a specialized witness table for that conformance.
    auto foundSpec = specializedWitnessTableMap.find(C);
    if (foundSpec != specializedWitnessTableMap.end())
      return foundSpec->second;
  } else if (auto *rootConf = dyn_cast<RootProtocolConformance>(C)) {
    auto found = WitnessTableMap.find(rootConf);
    if (found != WitnessTableMap.end())
      return found->second;
  }
  return nullptr;
}

SILDefaultWitnessTable *
SILModule::lookUpDefaultWitnessTable(const ProtocolDecl *Protocol,
                                     bool deserializeLazily) {
  // Note: we only ever look up default witness tables in the translation unit
  // that is currently being compiled, since SILGen generates them when it
  // visits the protocol declaration, and IRGen emits them when emitting the
  // protocol descriptor metadata for the protocol.

  auto found = DefaultWitnessTableMap.find(Protocol);
  if (found == DefaultWitnessTableMap.end()) {
    if (deserializeLazily) {
      SILLinkage linkage =
        getSILLinkage(getDeclLinkage(Protocol), ForDefinition);
      SILDefaultWitnessTable *wtable =
        SILDefaultWitnessTable::create(*this, linkage, Protocol);
      wtable = getSILLoader()->lookupDefaultWitnessTable(wtable);
      if (wtable)
        DefaultWitnessTableMap[Protocol] = wtable;
      return wtable;
    }

    return nullptr;
  }

  return found->second;
}

SILDefaultWitnessTable *
SILModule::createDefaultWitnessTableDeclaration(const ProtocolDecl *Protocol,
                                                SILLinkage Linkage) {
  return SILDefaultWitnessTable::create(*this, Linkage, Protocol);
}

void SILModule::deleteWitnessTable(SILWitnessTable *Wt) {
  auto Conf = Wt->getConformance();
  assert(lookUpWitnessTable(Conf) == Wt);
  getSILLoader()->invalidateWitnessTable(Wt);
  specializedWitnessTableMap.erase(Conf);
  if (auto *rootConf = dyn_cast<RootProtocolConformance>(Conf))
    WitnessTableMap.erase(rootConf);
  witnessTables.erase(Wt);
}

SILDefaultOverrideTable *SILModule::createDefaultOverrideTableDefinition(
    const ClassDecl *decl, SILLinkage linkage,
    ArrayRef<SILDefaultOverrideTable::Entry> entries) {
  return SILDefaultOverrideTable::define(*this, linkage, decl, entries);
}

SILDefaultOverrideTable *
SILModule::lookUpDefaultOverrideTable(const ClassDecl *decl,
                                      bool deserializeLazily) {
  // Note: we only ever look up default override tables in the translation unit
  // that is currently being compiled, since SILGen generates them when it
  // visits the class declaration, and IRGen emits them when emitting the
  // class descriptor metadata for the class.

  auto found = DefaultOverrideTableMap.find(decl);
  if (found == DefaultOverrideTableMap.end()) {
    if (deserializeLazily) {
      SILLinkage linkage = getSILLinkage(getDeclLinkage(decl), ForDefinition);
      SILDefaultOverrideTable *otable =
          SILDefaultOverrideTable::declare(*this, linkage, decl);
      otable = getSILLoader()->lookupDefaultOverrideTable(otable);
      if (otable)
        DefaultOverrideTableMap[decl] = otable;
      return otable;
    }

    return nullptr;
  }

  return found->second;
}

const IntrinsicInfo &SILModule::getIntrinsicInfo(Identifier ID) {
  unsigned OldSize = IntrinsicIDCache.size();
  IntrinsicInfo &Info = IntrinsicIDCache[ID];

  // If the element was is in the cache, return it.
  if (OldSize == IntrinsicIDCache.size())
    return Info;

  // Otherwise, lookup the ID and Type and store them in the map.
  StringRef NameRef = getBuiltinBaseName(getASTContext(), ID.str(), Info.Types);
  Info.ID = getLLVMIntrinsicID(NameRef);

  return Info;
}

const BuiltinInfo &SILModule::getBuiltinInfo(Identifier ID) {
  unsigned OldSize = BuiltinIDCache.size();
  BuiltinInfo &Info = BuiltinIDCache[ID];

  // If the element was is in the cache, return it.
  if (OldSize == BuiltinIDCache.size())
    return Info;

  // Otherwise, lookup the ID and Type and store them in the map.
  // Find the matching ID.
  StringRef OperationName =
    getBuiltinBaseName(getASTContext(), ID.str(), Info.Types);

  // Several operation names have suffixes and don't match the name from
  // Builtins.def, so handle those first.
  if (OperationName.starts_with("fence_"))
    Info.ID = BuiltinValueKind::Fence;
  else if (OperationName.starts_with("ifdef_"))
    Info.ID = BuiltinValueKind::Ifdef;
  else if (OperationName.starts_with("cmpxchg_"))
    Info.ID = BuiltinValueKind::CmpXChg;
  else if (OperationName.starts_with("atomicrmw_"))
    Info.ID = BuiltinValueKind::AtomicRMW;
  else if (OperationName.starts_with("atomicload_"))
    Info.ID = BuiltinValueKind::AtomicLoad;
  else if (OperationName.starts_with("atomicstore_"))
    Info.ID = BuiltinValueKind::AtomicStore;
  else if (OperationName.starts_with("allocWithTailElems_"))
    Info.ID = BuiltinValueKind::AllocWithTailElems;
  else if (OperationName.starts_with("applyDerivative_"))
    Info.ID = BuiltinValueKind::ApplyDerivative;
  else if (OperationName.starts_with("applyTranspose_"))
    Info.ID = BuiltinValueKind::ApplyTranspose;
  else
    Info.ID = llvm::StringSwitch<BuiltinValueKind>(OperationName)
#define BUILTIN(id, name, attrs) .Case(name, BuiltinValueKind::id)
#include "swift/AST/Builtins.def"
      .Default(BuiltinValueKind::None);

  return Info;
}

SILFunction *SILModule::lookUpFunction(SILDeclRef fnRef) {
  auto name = fnRef.mangle();
  return lookUpFunction(name);
}

bool SILModule::loadFunction(SILFunction *F, LinkingMode LinkMode) {
  SILFunction *NewF =
    getSILLoader()->lookupSILFunction(F, /*onlyUpdateLinkage*/ false);
  if (!NewF)
    return false;

  linkFunction(NewF, LinkMode);

  assert(F == NewF);
  return true;
}

SILFunction *SILModule::loadFunction(StringRef name, LinkingMode LinkMode,
                                     std::optional<SILLinkage> linkage) {
  SILFunction *func = lookUpFunction(name);
  if (!func)
    func = getSILLoader()->lookupSILFunction(name, linkage);
  if (!func)
    return nullptr;

  linkFunction(func, LinkMode);
  return func;
}

void SILModule::updateFunctionLinkage(SILFunction *F) {
  getSILLoader()->lookupSILFunction(F, /*onlyUpdateLinkage*/ true);
}

bool SILModule::linkFunction(SILFunction *F, SILModule::LinkingMode Mode) {
  return SILLinkerVisitor(*this, Mode).processFunction(F);
}

bool SILModule::linkWitnessTable(ProtocolConformance *PC, SILModule::LinkingMode Mode) {
  return SILLinkerVisitor(*this, Mode).processConformance(ProtocolConformanceRef(PC));
}

bool SILModule::hasFunction(StringRef Name) {
  if (lookUpFunction(Name))
    return true;
  return getSILLoader()->hasSILFunction(Name);
}

void SILModule::invalidateSILLoaderCaches() {
  getSILLoader()->invalidateAllCaches();
}

SILFunction *SILModule::removeFromZombieList(StringRef Name) {
  if (auto *Zombie = ZombieFunctionTable.lookup(Name)) {
    assert(Zombie->snapshotID == 0 && "zombie cannot be a snapthot function");
    ZombieFunctionTable.erase(Name);
    zombieFunctions.remove(Zombie);

    // The owner of the function's Name is the ZombieFunctionTable key, which is
    // freed by erase().
    // Make sure nobody accesses the name string after it is freed.
    Zombie->setName(StringRef());
    return Zombie;
  }
  return nullptr;
}

/// Erase a function from the module.
void SILModule::eraseFunction(SILFunction *F) {
  assert(!F->isZombie() && "zombie function is in list of alive functions");
  assert(F->snapshotID == 0 && "cannot erase a snapshot function");

  llvm::StringMapEntry<SILFunction*> *entry =
      &*ZombieFunctionTable.insert(std::make_pair(F->getName(), nullptr)).first;
  assert(!entry->getValue() && "Zombie function already exists");
  StringRef zombieName = entry->getKey();

  // The owner of the function's Name is the FunctionTable key. As we remove
  // the function from the table we need to use the allocated name string from
  // the ZombieFunctionTable.
  FunctionTable.erase(F->getName());
  F->setName(zombieName);

  // Remove from the asmname table.
  if (!F->asmName().empty()) {
    auto known = FunctionByAsmNameTable.find(F->asmName());
    if (known != FunctionByAsmNameTable.end() && known->second == F)
      FunctionByAsmNameTable.erase(known);
  }

  // The function is dead, but we need it later (at IRGen) for debug info
  // or vtable stub generation. So we move it into the zombie list.
  getFunctionList().remove(F);
  zombieFunctions.push_back(F);
  entry->setValue(F);
  F->setZombie();

  // This opens dead-function-removal opportunities for called functions.
  // (References are not needed anymore.)
  F->clear();
  F->dropDynamicallyReplacedFunction();
  F->dropReferencedAdHocRequirementWitnessFunction();
  // Drop references for any _specialize(target:) functions.
  F->clearSpecializeAttrs();
}

void SILModule::invalidateFunctionInSILCache(SILFunction *F) {
  getSILLoader()->invalidateFunction(F);
}

/// Erase a global SIL variable from the module.
void SILModule::eraseGlobalVariable(SILGlobalVariable *gv) {
  getSILLoader()->invalidateGlobalVariable(gv);
  GlobalVariableMap.erase(gv->getName());

  if (gv->asmName().empty()) {
    auto known = GlobalVariableByAsmNameMap.find(gv->asmName());
    if (known != GlobalVariableByAsmNameMap.end() && known->second == gv)
      GlobalVariableByAsmNameMap.erase(known);
  }

  getSILGlobalList().erase(gv);
}

void SILModule::eraseDifferentiabilityWitness(SILDifferentiabilityWitness *dw) {
  getSILLoader()->invalidateDifferentiabilityWitness(dw);

  Mangle::ASTMangler mangler(getASTContext());
  auto originalFunction = dw->getOriginalFunction()->getName();
  auto mangledKey = mangler.mangleSILDifferentiabilityWitness(
    originalFunction, dw->getKind(), dw->getConfig());
  DifferentiabilityWitnessMap.erase(mangledKey);
  llvm::erase(DifferentiabilityWitnessesByFunction[originalFunction], dw);

  getDifferentiabilityWitnessList().erase(dw);
}

void SILModule::eraseAllDifferentiabilityWitnesses(SILFunction *f) {
  Mangle::ASTMangler mangler(getASTContext());

  for (auto *dw : DifferentiabilityWitnessesByFunction.at(f->getName())) {
    getSILLoader()->invalidateDifferentiabilityWitness(dw);
    auto mangledKey = mangler.mangleSILDifferentiabilityWitness(
      f->getName(), dw->getKind(), dw->getConfig());
    DifferentiabilityWitnessMap.erase(mangledKey);
    getDifferentiabilityWitnessList().erase(dw);
  }

  DifferentiabilityWitnessesByFunction.erase(f->getName());
}

SILVTable *SILModule::lookUpVTable(const ClassDecl *C,
                                   bool deserializeLazily) {
  if (!C)
    return nullptr;

  // First try to look up R from the lookup table.
  auto R = VTableMap.find(C);
  if (R != VTableMap.end())
    return R->second;

  if (!deserializeLazily)
    return nullptr;

  // If that fails, try to deserialize it. If that fails, return nullptr.
  SILVTable *Vtbl = getSILLoader()->lookupVTable(C);
  if (!Vtbl)
    return nullptr;

  if (C->walkSuperclasses([&](ClassDecl *S) {
    auto R = VTableMap.find(S);
    if (R != VTableMap.end())
      return TypeWalker::Action::Continue;
    SILVTable *Vtbl = getSILLoader()->lookupVTable(S);
    if (!Vtbl) {
      return TypeWalker::Action::Stop;
    }
    VTableMap[S] = Vtbl;
    return TypeWalker::Action::Continue;
  })) {
    return nullptr;
  }

  // If we succeeded, map C -> VTbl in the table and return VTbl.
  VTableMap[C] = Vtbl;
  return Vtbl;
}

SILMoveOnlyDeinit *SILModule::lookUpMoveOnlyDeinit(const NominalTypeDecl *C,
                                                   bool deserializeLazily) {
  if (!C)
    return nullptr;

  // First try to look up R from the lookup table.
  auto iter = MoveOnlyDeinitMap.find(C);
  if (iter != MoveOnlyDeinitMap.end())
    return iter->second;

  if (!deserializeLazily)
    return nullptr;

  // If that fails, try to deserialize it. If that fails, return nullptr.
  auto *tbl = getSILLoader()->lookupMoveOnlyDeinit(C);
  if (!tbl)
    return nullptr;

  // If we succeeded, map C -> VTbl in the table and return VTbl.
  MoveOnlyDeinitMap[C] = tbl;
  return tbl;
}

SILVTable *SILModule::lookUpSpecializedVTable(SILType classTy) {
  // First try to look up R from the lookup table.
  auto R = SpecializedVTableMap.find(classTy);
  if (R != SpecializedVTableMap.end())
    return R->second;

  return nullptr;
}

SerializedSILLoader *SILModule::getSILLoader() {
  // If the SILLoader is null, create it.
  if (!SILLoader)
    SILLoader = SerializedSILLoader::create(
        getASTContext(), this, &deserializationNotificationHandlers);
  // Return the SerializedSILLoader.
  return SILLoader.get();
}

/// Given a conformance \p C and a protocol requirement \p Requirement,
/// search the witness table for the conformance and return the witness thunk
/// for the requirement.
std::pair<SILFunction *, SILWitnessTable *>
SILModule::lookUpFunctionInWitnessTable(ProtocolConformanceRef C,
                                        SILDeclRef Requirement,
                                        bool lookupInSpecializedWitnessTable,
                                        SILModule::LinkingMode linkingMode) {
  if (!C.isConcrete())
    return {nullptr, nullptr};

  if (getStage() != SILStage::Lowered) {
    SILLinkerVisitor linker(*this, linkingMode);
    linker.processConformance(C);
  }
  ProtocolConformance *conf = C.getConcrete();
  SILWitnessTable *wt = nullptr;

  if (lookupInSpecializedWitnessTable) {
    wt = lookUpWitnessTable(conf);
    if (!wt) {
      if (auto *inheritedC = dyn_cast<InheritedProtocolConformance>(conf)) {
        conf = inheritedC->getInheritedConformance();
        wt = lookUpWitnessTable(conf);
      }
      if (!wt && !isa<SpecializedProtocolConformance>(conf)) {
        conf = conf->getRootConformance();
        wt = lookUpWitnessTable(conf);
      }
    }
  } else {
    wt = lookUpWitnessTable(conf->getRootConformance());
  }

  if (!wt) {
    LLVM_DEBUG(llvm::dbgs() << "        Failed speculative lookup of "
               "witness for: ";
               C.dump(llvm::dbgs()); Requirement.dump());
    return {nullptr, nullptr};
  }

  // Okay, we found the correct witness table. Now look for the method.
  for (auto &Entry : wt->getEntries()) {
    // Look at method entries only.
    if (Entry.getKind() != SILWitnessTable::WitnessKind::Method)
      continue;

    SILWitnessTable::MethodWitness MethodEntry = Entry.getMethodWitness();
    // Check if this is the member we were looking for.
    if (MethodEntry.Requirement != Requirement)
      continue;

    return {MethodEntry.Witness, wt};
  }

  return {nullptr, nullptr};
}

/// Given a protocol \p Protocol and a requirement \p Requirement,
/// search the protocol's default witness table and return the default
/// witness thunk for the requirement.
std::pair<SILFunction *, SILDefaultWitnessTable *>
SILModule::lookUpFunctionInDefaultWitnessTable(const ProtocolDecl *Protocol,
                                               SILDeclRef Requirement,
                                               bool deserializeLazily) {
  // Look up the default witness table associated with our protocol from the
  // SILModule.
  auto Ret = lookUpDefaultWitnessTable(Protocol, deserializeLazily);

  // If no default witness table was found, bail.
  //
  // FIXME: Could be an assert if we fix non-single-frontend mode to link
  // together serialized SIL emitted by each translation unit.
  if (!Ret) {
    LLVM_DEBUG(llvm::dbgs() << "        Failed speculative lookup of default "
               "witness for " << Protocol->getName() << " ";
               Requirement.dump());
    return std::make_pair(nullptr, nullptr);
  }

  // Okay, we found the correct default witness table. Now look for the method.
  for (auto &Entry : Ret->getEntries()) {
    // Ignore dummy entries emitted for non-method requirements, as well as
    // requirements without default implementations.
    if (!Entry.isValid() || Entry.getKind() != SILWitnessTable::Method)
      continue;

    // Check if this is the member we were looking for.
    if (Entry.getMethodWitness().Requirement != Requirement)
      continue;

    return std::make_pair(Entry.getMethodWitness().Witness, Ret);
  }

  // This requirement doesn't have a default implementation.
  return std::make_pair(nullptr, nullptr);
}

SILFunction *
SILModule::
lookUpFunctionInVTable(ClassDecl *Class, SILDeclRef Member) {
  // Try to lookup a VTable for Class from the module...
  auto *Vtbl = lookUpVTable(Class);

  // Bail, if the lookup of VTable fails.
  if (!Vtbl) {
    return nullptr;
  }

  // Ok, we have a VTable. Try to lookup the SILFunction implementation from
  // the VTable.
  if (auto E = Vtbl->getEntry(*this, Member))
    return E->getImplementation();

  return nullptr;
}

SILFunction *
SILModule::lookUpMoveOnlyDeinitFunction(const NominalTypeDecl *nomDecl) {
  assert(!nomDecl->canBeCopyable());

  auto *tbl = lookUpMoveOnlyDeinit(nomDecl);

  // Bail, if the lookup of VTable fails.
  if (!tbl) {
    return nullptr;
  }

  return tbl->getImplementation();
}

SILDifferentiabilityWitness *
SILModule::lookUpDifferentiabilityWitness(StringRef name) {
  auto it = DifferentiabilityWitnessMap.find(name);
  if (it != DifferentiabilityWitnessMap.end())
    return it->second;
  return nullptr;
}

SILDifferentiabilityWitness *
SILModule::lookUpDifferentiabilityWitness(SILDifferentiabilityWitnessKey key) {
  Mangle::ASTMangler mangler(getASTContext());
  return lookUpDifferentiabilityWitness(
      mangler.mangleSILDifferentiabilityWitness(
          key.originalFunctionName, key.kind, key.config));
}

/// Look up the differentiability witness corresponding to the given indices.
llvm::ArrayRef<SILDifferentiabilityWitness *>
SILModule::lookUpDifferentiabilityWitnessesForFunction(StringRef name) {
  return DifferentiabilityWitnessesByFunction[name];
}

bool SILModule::loadDifferentiabilityWitness(SILDifferentiabilityWitness *dw) {
  auto *newDW = getSILLoader()->lookupDifferentiabilityWitness(dw->getKey());
  if (!newDW)
    return false;
  assert(dw == newDW);
  return true;
}

void SILModule::registerDeserializationNotificationHandler(
    std::unique_ptr<DeserializationNotificationHandler> &&handler) {
  deserializationNotificationHandlers.add(std::move(handler));
}

SILValue SILModule::getLocalGenericEnvironmentDef(GenericEnvironment *genericEnv,
                                                  SILFunction *inFunction) {
  SILValue &def = RootLocalArchetypeDefs[{genericEnv, inFunction}];
  if (!def) {
    numUnresolvedLocalArchetypes++;
    def = ::new PlaceholderValue(inFunction,
                                 SILType::getPrimitiveAddressType(
                                    inFunction->getASTContext().TheEmptyTupleType));
  }

  return def;
}

SILValue SILModule::getRootLocalArchetypeDef(CanLocalArchetypeType archetype,
                                             SILFunction *inFunction) {
  return getLocalGenericEnvironmentDef(archetype->getGenericEnvironment(),
                                       inFunction);
}

void SILModule::reclaimUnresolvedLocalArchetypeDefinitions() {
  llvm::DenseMap<LocalArchetypeKey, SILValue> newLocalArchetypeDefs;

  for (auto pair : RootLocalArchetypeDefs) {
    if (auto *placeholder = dyn_cast<PlaceholderValue>(pair.second)) {
      // If a placeholder has no uses, the instruction that introduced it
      // was deleted before the local archetype was resolved. Reclaim the
      // placeholder so that we don't complain.
      if (placeholder->use_empty()) {
        assert(numUnresolvedLocalArchetypes > 0);
        --numUnresolvedLocalArchetypes;
        ::delete placeholder;
        continue;
      }
    }

    newLocalArchetypeDefs.insert(pair);
  }

  std::swap(newLocalArchetypeDefs, RootLocalArchetypeDefs);
}

bool SILModule::hasUnresolvedLocalArchetypeDefinitions() {
  return numUnresolvedLocalArchetypes != 0;
}

/// Get a unique index for a struct or class field in layout order.
unsigned SILModule::getFieldIndex(NominalTypeDecl *decl, VarDecl *field) {

  auto iter = fieldIndices.find({decl, field});
  if (iter != fieldIndices.end())
    return iter->second;

  unsigned index = 0;
  if (auto *classDecl = dyn_cast<ClassDecl>(decl)) {
    for (auto *superDecl = classDecl->getSuperclassDecl(); superDecl != nullptr;
         superDecl = superDecl->getSuperclassDecl()) {
      if (!superDecl->isResilient(getSwiftModule(),
                                  ResilienceExpansion::Maximal)) {
        index += superDecl->getStoredProperties().size();
      }
    }
  }
  for (VarDecl *property : decl->getStoredProperties()) {
    if (field == property) {
      fieldIndices[{decl, field}] = index;
      return index;
    }
    ++index;
  }
  llvm_unreachable("The field decl for a struct_extract, struct_element_addr, "
                   "or ref_element_addr must be an accessible stored "
                   "property of the operand type");
}

unsigned SILModule::getCaseIndex(EnumElementDecl *enumElement) {
  auto iter = enumCaseIndices.find(enumElement);
  if (iter != enumCaseIndices.end())
    return iter->second;

  unsigned idx = 0;
  for (EnumElementDecl *e : enumElement->getParentEnum()->getAllElements()) {
    if (e == enumElement) {
      enumCaseIndices[enumElement] = idx;
      return idx;
    }
    ++idx;
  }
  ASSERT(false && "enum element not found in enum decl, broken AST?");
  return 0;
}

void SILModule::notifyAddedInstruction(SILInstruction *inst) {
  inst->forEachDefinedLocalEnvironment([&](GenericEnvironment *genericEnv,
                                           SILValue dependency) {
    SILValue &val = RootLocalArchetypeDefs[{genericEnv, inst->getFunction()}];
    if (val) {
      if (!isa<PlaceholderValue>(val)) {
        ABORT([&](auto &out) {
          // Print a useful error message (and not just abort with an assert).
          out << "re-definition of local environment in function "
              << inst->getFunction()->getName() << ":\n";
          inst->print(out);
          out << "previously defined in function "
              << val->getFunction()->getName() << ":\n";
          val->print(out);
        });
      }
      // The local environment was unresolved so far. Replace the placeholder
      // by inst.
      auto *placeholder = cast<PlaceholderValue>(val);
      placeholder->replaceAllUsesWith(dependency);
      ::delete placeholder;

      assert(numUnresolvedLocalArchetypes > 0);
      numUnresolvedLocalArchetypes--;
    }
    val = dependency;
  });
}

void SILModule::notifyMovedInstruction(SILInstruction *inst,
                                       SILFunction *fromFunction) {
  for (auto &op : inst->getAllOperands()) {
    if (auto *undef = dyn_cast<SILUndef>(op.get())) {
      op.set(SILUndef::get(inst->getFunction(), undef->getType()));
    }
  }

  inst->forEachDefinedLocalEnvironment([&](GenericEnvironment *genericEnv,
                                           SILValue dependency) {
    LocalArchetypeKey key = {genericEnv, fromFunction};
    assert(RootLocalArchetypeDefs.lookup(key) == dependency &&
           "archetype def was not registered");
    RootLocalArchetypeDefs.erase(key);
    RootLocalArchetypeDefs[{genericEnv, inst->getFunction()}] = dependency;
  });
}

// TODO: We should have an "isNoReturn" bit on Swift's BuiltinInfo, but for
// now, let's recognize noreturn intrinsics and builtins specially here.
bool SILModule::isNoReturnBuiltinOrIntrinsic(Identifier Name) {
  const auto &IntrinsicInfo = getIntrinsicInfo(Name);
  if (IntrinsicInfo.ID != llvm::Intrinsic::not_intrinsic) {
    return IntrinsicInfo.getOrCreateFnAttributes(getASTContext())
        .hasAttribute(llvm::Attribute::NoReturn);
  }
  const auto &BuiltinInfo = getBuiltinInfo(Name);
  switch (BuiltinInfo.ID) {
  default:
    return false;
  case BuiltinValueKind::Unreachable:
  case BuiltinValueKind::CondUnreachable:
  case BuiltinValueKind::UnexpectedError:
  case BuiltinValueKind::ErrorInMain:
    return true;
  }
}

bool SILModule::
shouldSerializeEntitiesAssociatedWithDeclContext(const DeclContext *DC) const {
  // Serialize entities associated with this module's associated context.
  if (DC->isChildContextOf(getAssociatedContext())) {
    return true;
  }
  
  // Serialize entities associated with clang modules, since other entities
  // may depend on them, and someone who deserializes those entities may not
  // have their own copy.
  if (isa<ClangModuleUnit>(DC->getModuleScopeContext())) {
    return true;
  }
  
  return false;
}

/// Returns true if it is the optimized OnoneSupport module.
bool SILModule::isOptimizedOnoneSupportModule() const {
  return getOptions().shouldOptimize() &&
         getSwiftModule()->isOnoneSupportModule();
}

void SILModule::setSerializeSILAction(SILModule::ActionCallback Action) {
  assert(!SerializeSILAction && "Serialization action can be set only once");
  SerializeSILAction = Action;
}

SILModule::ActionCallback SILModule::getSerializeSILAction() const {
  return SerializeSILAction;
}

void SILModule::serialize() {
  assert(SerializeSILAction && "Serialization action should be set");
  assert(!isSerialized() && "The module was serialized already");
  SerializeSILAction();
  setSerialized();
}

void SILModule::installSILRemarkStreamer() {
  assert(!silRemarkStreamer && "SIL Remark Streamer is already installed!");
  silRemarkStreamer = SILRemarkStreamer::create(*this);
}

void SILModule::promoteLinkages() {
  for (auto &Fn : functions) {
    // Ignore functions with shared linkage
    if (Fn.getLinkage() == SILLinkage::Shared)
      continue;

    if (Fn.isDefinition())
      Fn.setLinkage(SILLinkage::Public);
    else
      Fn.setLinkage(SILLinkage::PublicExternal);
  }

  for (auto &Global : silGlobals) {
    // Ignore globals with shared linkage
    if (Global.getLinkage() == SILLinkage::Shared)
      continue;

    if (Global.isDefinition())
      Global.setLinkage(SILLinkage::Public);
    else
      Global.setLinkage(SILLinkage::PublicExternal);
  }

  // TODO: Promote linkage of other SIL entities
}

bool SILModule::isStdlibModule() const {
  return TheSwiftModule->isStdlibModule();
}
void SILModule::performOnceForPrespecializedImportedExtensions(
    llvm::function_ref<void(AbstractFunctionDecl *)> action) {
  if (prespecializedFunctionDeclsImported)
    return;

  // No prespecitalizations in embedded Swift
  if (getASTContext().LangOpts.hasFeature(Feature::Embedded))
    return;

  SmallVector<ModuleDecl *, 8> importedModules;
  // Add the Swift module.
  if (!isStdlibModule()) {
    auto *SwiftStdlib = getASTContext().getStdlibModule();
    if (SwiftStdlib)
      importedModules.push_back(SwiftStdlib);
  }

  // Add explicitly imported modules.
  SmallVector<Decl *, 32> topLevelDecls;
  getSwiftModule()->getTopLevelDecls(topLevelDecls);
  for (const Decl *D : topLevelDecls) {
    if (auto importDecl = dyn_cast<ImportDecl>(D)) {
      if (!importDecl->getModule() ||
          importDecl->getModule()->isNonSwiftModule())
        continue;
      importedModules.push_back(importDecl->getModule());
    }
  }

  for (auto *module : importedModules) {
    SmallVector<Decl *, 16> prespecializations;
    module->getExportedPrespecializations(prespecializations);
    for (auto *p : prespecializations) {
      if (auto *vd = dyn_cast<AbstractFunctionDecl>(p)) {
        action(vd);
      }
    }
  }
  prespecializedFunctionDeclsImported = true;
}

void SILModule::moveBefore(SILModule::iterator moveAfter, SILFunction *fn) {
  assert(&fn->getModule() == this);
  assert(&moveAfter->getModule() == this);
  assert(moveAfter != end() &&
         "We assume that moveAfter must not be end since nothing is after end");

  getFunctionList().remove(fn->getIterator());
  getFunctionList().insert(moveAfter, fn);
}

void SILModule::moveAfter(SILModule::iterator moveAfter, SILFunction *fn) {
  assert(&fn->getModule() == this);
  assert(&moveAfter->getModule() == this);
  assert(moveAfter != end() &&
         "We assume that moveAfter must not be end since nothing is after end");

  getFunctionList().remove(fn->getIterator());
  getFunctionList().insertAfter(moveAfter, fn);
}

SILProperty *
SILProperty::create(SILModule &M, unsigned Serialized, AbstractStorageDecl *Decl,
                    std::optional<KeyPathPatternComponent> Component) {
  auto prop = new (M) SILProperty(Serialized, Decl, Component);
  M.properties.push_back(prop);
  return prop;
}

// Definition from SILLinkage.h.
SILLinkage swift::getDeclSILLinkage(const ValueDecl *decl) {
  AccessLevel access = decl->getEffectiveAccess();
  SILLinkage linkage;
  switch (access) {
  case AccessLevel::Private:
  case AccessLevel::FilePrivate:
    linkage = SILLinkage::Private;
    break;
  case AccessLevel::Internal:
    linkage = SILLinkage::Hidden;
    break;
  case AccessLevel::Package:
    linkage = SILLinkage::Package;
    break;
  case AccessLevel::Public:
  case AccessLevel::Open:
    linkage = SILLinkage::Public;
    break;
  }
  return linkage;
}

void swift::simple_display(llvm::raw_ostream &out, const SILModule *M) {
  if (!M) {
    out << "(null)";
    return;
  }
  out << "SIL for ";
  simple_display(out, M->getSwiftModule());
}

SourceLoc swift::extractNearestSourceLoc(const SILModule *M) {
  if (!M)
    return SourceLoc();
  return extractNearestSourceLoc(M->getSwiftModule());
}

bool Lowering::usesObjCAllocator(ClassDecl *theClass) {
  // If the root class was implemented in Objective-C, use Objective-C's
  // allocation methods because they may have been overridden.
  return theClass->getObjectModel() == ReferenceCounting::ObjC;
}

bool Lowering::needsIsolatingDestructor(DestructorDecl *dd) {
  auto ai = swift::getActorIsolation(dd);
  if (!ai.isActorIsolated()) {
    return false;
  }
  DestructorDecl *firstIsolated = dd;
  while (true) {
    DestructorDecl *next = firstIsolated->getSuperDeinit();
    if (!next)
      break;
    auto ai = swift::getActorIsolation(next);
    if (!ai.isActorIsolated())
      break;
    firstIsolated = next;
  }

  // If isolation was introduced in ObjC code, then we assume that ObjC code
  // also overrides retain/release to make sure that dealloc is called on the
  // correct executor in the first place.
  return firstIsolated->getClangNode().isNull();
}