//===- RuntimeLibcallEmitter.cpp - Properties from RuntimeLibcalls.td -----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "runtime-libcall-emitter"

#include "RuntimeLibcalls.h"

#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/xxhash.h"
#include "llvm/TableGen/CodeGenHelpers.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/SetTheory.h"
#include "llvm/TableGen/StringToOffsetTable.h"
#include "llvm/TableGen/TableGenBackend.h"

using namespace llvm;

namespace {
// Pair of a RuntimeLibcallAvailability and LibcallCallingConv to use as a map
// key.
struct PredicateWithCC {
  const Record *Availability = nullptr;
  const Record *CallingConv = nullptr;

  PredicateWithCC() = default;
  PredicateWithCC(std::pair<const Record *, const Record *> P)
      : Availability(P.first), CallingConv(P.second) {}

  PredicateWithCC(const Record *P, const Record *C)
      : Availability(P), CallingConv(C) {}
};

inline bool operator==(PredicateWithCC LHS, PredicateWithCC RHS) {
  return LHS.Availability == RHS.Availability &&
         LHS.CallingConv == RHS.CallingConv;
}
} // namespace

namespace {
/// A floating-point libcall family parsed from a RuntimeLibcallFamily record.
struct FPLibcallFamily {
  StringRef Base;
  std::vector<StringRef> Intrinsics;
  std::vector<StringRef> VectorSuffixes;

  explicit FPLibcallFamily(const Record *R)
      : Base(R->getValueAsString("LibcallBase")),
        Intrinsics(R->getValueAsListOfStrings("Intrinsics")),
        VectorSuffixes(R->getValueAsListOfStrings("VectorSuffixes")) {}
};
} // namespace

namespace llvm {
template <> struct DenseMapInfo<PredicateWithCC, void> {
  static unsigned getHashValue(const PredicateWithCC Val) {
    auto Pair = std::make_pair(Val.Availability, Val.CallingConv);
    return DenseMapInfo<
        std::pair<const Record *, const Record *>>::getHashValue(Pair);
  }

  static bool isEqual(PredicateWithCC LHS, PredicateWithCC RHS) {
    return LHS == RHS;
  }
};

class RuntimeLibcallEmitter {
private:
  const RecordKeeper &Records;
  RuntimeLibcalls Libcalls;

  void emitGetRuntimeLibcallEnum(raw_ostream &OS) const;

  void emitNameMatchHashTable(raw_ostream &OS,
                              StringToOffsetTable &OffsetTable) const;

  void emitGetInitRuntimeLibcallNames(raw_ostream &OS) const;

  // Emit the sorted per-predicate `setAvailable` tables/loops. The
  // always-available bucket emits at \p BaseIndent; each predicated bucket is
  // wrapped in `if (pred)`. All calls are emitted in member context (no
  // receiver prefix).
  void
  emitPredicateGroups(raw_ostream &OS, const Record *R,
                      DenseMap<PredicateWithCC, LibcallsWithCC> &Pred2Funcs,
                      SetVector<PredicateWithCC> &PredicateSorter,
                      unsigned BaseIndent) const;

  // A LibraryRef opt-out: the impls a consumer drops from a shared library,
  // plus the consumer's triple predicate.
  struct LibraryExclusion {
    const Record *TriplePred;
    std::vector<const RuntimeLibcallImpl *> Impls;
  };

  // A single LibcallLibrary variant, expanded into its per-predicate impl
  // groups. Unconditional impls are tracked separately for cross-variant
  // deduplication. A variant is Deferred when it re-adds an impl its own
  // consumer excludes; deferred variants are emitted after the LibraryRef
  // exclusions so the re-add wins over the opt-out.
  struct ExpandedLibrary {
    const Record *Lib;
    DenseMap<PredicateWithCC, LibcallsWithCC> Pred2Funcs;
    SetVector<PredicateWithCC> PredicateSorter;
    SetVector<const RuntimeLibcallImpl *> Unconditional;
    bool Deferred = false;
  };

  // Emit one variant's guarded `setAvailable` block into the enclosing
  // `setAvailableLibFuncs_<name>` function.
  void emitLibraryVariant(raw_ostream &OS, ExpandedLibrary &EL) const;

  // Emit a `setAvailableLibFuncs_<name>` member function for all LibcallLibrary
  // defs sharing \p Name, each gated by its own availability predicate. \p
  // Exclusions are emitted as guarded setUnavailable calls at the end.
  void emitLibraryFunction(raw_ostream &OS, StringRef Name,
                           ArrayRef<const Record *> Libs,
                           ArrayRef<LibraryExclusion> Exclusions) const;

  // Group all LibcallLibrary defs by their shared LibraryName, preserving
  // definition order. Both the member-declaration fragment and the definitions
  // iterate this to stay in lockstep.
  MapVector<StringRef, std::vector<const Record *>>
  collectLibrariesByName() const;

  void emitRuntimeLibcallsInfoMemberDecls(raw_ostream &OS) const;

  void emitSystemRuntimeLibrarySetCalls(raw_ostream &OS) const;

  DenseSet<StringRef> collectLibcallNames() const;

  void checkFPLibcallFamilies(ArrayRef<FPLibcallFamily> Families,
                              const DenseSet<StringRef> &LibcallNames) const;

  void emitFPLibcallSelectorDecls(raw_ostream &OS,
                                  ArrayRef<FPLibcallFamily> Families) const;

  void emitFPLibcallSelectors(raw_ostream &OS,
                              ArrayRef<FPLibcallFamily> Families,
                              const DenseSet<StringRef> &LibcallNames) const;

  void
  emitGetLibcallForIntrinsic(raw_ostream &OS,
                             ArrayRef<FPLibcallFamily> Families,
                             const DenseSet<StringRef> &LibcallNames) const;

public:
  RuntimeLibcallEmitter(const RecordKeeper &R) : Records(R), Libcalls(R) {}

  void run(raw_ostream &OS);
};

} // End anonymous namespace.

void RuntimeLibcallEmitter::emitGetRuntimeLibcallEnum(raw_ostream &OS) const {
  IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALL_ENUM");

  OS << "namespace llvm {\n"
        "namespace RTLIB {\n"
        "enum Libcall : unsigned short {\n";

  for (const RuntimeLibcall &LibCall : Libcalls.getRuntimeLibcallDefList()) {
    StringRef Name = LibCall.getName();
    OS << "  " << Name << " = " << LibCall.getEnumVal() << ",\n";
  }

  OS << "  UNKNOWN_LIBCALL = " << Libcalls.getRuntimeLibcallDefList().size()
     << "\n};\n\n"
        "enum LibcallImpl : unsigned short {\n"
        "  Unsupported = 0,\n";

  for (const RuntimeLibcallImpl &LibCall :
       Libcalls.getRuntimeLibcallImplDefList()) {
    OS << "  impl_" << LibCall.getName() << " = " << LibCall.getEnumVal()
       << ", // " << LibCall.getLibcallFuncName() << '\n';
  }

  OS << "};\n"
     << "constexpr size_t NumLibcallImpls = "
     << Libcalls.getRuntimeLibcallImplDefList().size() + 1
     << ";\n"
        "} // End namespace RTLIB\n"
        "} // End namespace llvm\n";
}

// StringMap uses xxh3_64bits, truncated to uint32_t.
static uint64_t hash(StringRef Str) {
  return static_cast<uint32_t>(xxh3_64bits(Str));
}

static void emitHashFunction(raw_ostream &OS) {
  OS << "static inline uint64_t hash(StringRef Str) {\n"
        "  return static_cast<uint32_t>(xxh3_64bits(Str));\n"
        "}\n\n";
}

/// Return the table size, maximum number of collisions for the set of hashes
static std::pair<int, int>
computePerfectHashParameters(ArrayRef<uint64_t> Hashes) {
  // Chosen based on experimentation with llvm/benchmarks/RuntimeLibcalls.cpp
  const int SizeOverhead = 4;

  // Index derived from hash -> number of collisions.
  DenseMap<uint64_t, int> Table;

  unsigned NumHashes = Hashes.size();

  for (int MaxCollisions = 1;; ++MaxCollisions) {
    for (unsigned N = NextPowerOf2(NumHashes - 1); N < SizeOverhead * NumHashes;
         N <<= 1) {
      Table.clear();

      bool NeedResize = false;
      for (uint64_t H : Hashes) {
        uint64_t Idx = H % static_cast<uint64_t>(N);
        if (++Table[Idx] > MaxCollisions) {
          // Need to resize the final table if we increased the collision count.
          NeedResize = true;
          break;
        }
      }

      if (!NeedResize)
        return {N, MaxCollisions};
    }
  }
}

static std::vector<unsigned>
constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords,
                          ArrayRef<uint64_t> Hashes,
                          ArrayRef<unsigned> TableValues, int Size,
                          int Collisions, StringToOffsetTable &OffsetTable) {
  std::vector<unsigned> Lookup(Size * Collisions);

  for (auto [HashValue, TableValue] : zip(Hashes, TableValues)) {
    uint64_t Idx = (HashValue % static_cast<uint64_t>(Size)) *
                   static_cast<uint64_t>(Collisions);

    bool Found = false;
    for (int J = 0; J < Collisions; ++J) {
      unsigned &Entry = Lookup[Idx + J];
      if (Entry == 0) {
        Entry = TableValue;
        Found = true;
        break;
      }
    }

    if (!Found)
      reportFatalInternalError("failure to hash");
  }

  return Lookup;
}

/// Generate hash table based lookup by name.
void RuntimeLibcallEmitter::emitNameMatchHashTable(
    raw_ostream &OS, StringToOffsetTable &OffsetTable) const {
  ArrayRef<RuntimeLibcallImpl> RuntimeLibcallImplDefList =
      Libcalls.getRuntimeLibcallImplDefList();
  std::vector<uint64_t> Hashes(RuntimeLibcallImplDefList.size());
  std::vector<unsigned> TableValues(RuntimeLibcallImplDefList.size());
  DenseSet<StringRef> SeenFuncNames;

  size_t MaxFuncNameSize = 0;
  size_t Index = 0;

  for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {
    StringRef ImplName = LibCallImpl.getLibcallFuncName();
    if (SeenFuncNames.insert(ImplName).second) {
      MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size());
      TableValues[Index] = LibCallImpl.getEnumVal();
      Hashes[Index++] = hash(ImplName);
    }
  }

  // Trim excess elements from non-unique entries.
  Hashes.resize(SeenFuncNames.size());
  TableValues.resize(SeenFuncNames.size());

  LLVM_DEBUG({
    for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {
      StringRef ImplName = LibCallImpl.getLibcallFuncName();
      if (ImplName.size() == MaxFuncNameSize) {
        dbgs() << "Maximum runtime libcall name size: " << ImplName << '('
               << MaxFuncNameSize << ")\n";
      }
    }
  });

  // Early exiting on the symbol name provides a significant speedup in the miss
  // case on the set of symbols in a clang binary. Emit this as an inlinable
  // precondition in the header.
  //
  // The empty check is also used to get sensible behavior on anonymous
  // functions.
  //
  // TODO: It may make more sense to split the search by string size more. There
  // are a few outliers, most call names are small.
  {
    IfDefEmitter IfDef(OS, "GET_LOOKUP_LIBCALL_IMPL_NAME_BODY");

    OS << "  size_t Size = Name.size();\n"
          "  if (Size == 0 || Size > "
       << MaxFuncNameSize
       << ")\n"
          "    return enum_seq(RTLIB::Unsupported, RTLIB::Unsupported);\n"
          " return lookupLibcallImplNameImpl(Name);\n";
  }

  auto [Size, Collisions] = computePerfectHashParameters(Hashes);
  std::vector<unsigned> Lookup =
      constructPerfectHashTable(RuntimeLibcallImplDefList, Hashes, TableValues,
                                Size, Collisions, OffsetTable);

  LLVM_DEBUG(dbgs() << "Runtime libcall perfect hashing parameters: Size = "
                    << Size << ", maximum collisions = " << Collisions << '\n');

  IfDefEmitter IfDef(OS, "DEFINE_GET_LOOKUP_LIBCALL_IMPL_NAME");
  emitHashFunction(OS);

  OS << "iota_range<RTLIB::LibcallImpl> RTLIB::RuntimeLibcallsInfo::"
        "lookupLibcallImplNameImpl(StringRef Name) {\n";

  // Emit RTLIB::LibcallImpl values
  OS << "  static constexpr uint16_t HashTableNameToEnum[" << Lookup.size()
     << "] = {\n";

  for (unsigned TableVal : Lookup)
    OS << "    " << TableVal << ",\n";

  OS << "  };\n\n";

  OS << "  unsigned Idx = (hash(Name) % " << Size << ") * " << Collisions
     << ";\n\n"
        "  for (int I = 0; I != "
     << Collisions << R"(; ++I) {
    const uint16_t Entry = HashTableNameToEnum[Idx + I];
    const uint16_t StrOffset = RuntimeLibcallNameOffsetTable[Entry];
    const uint8_t StrSize = RuntimeLibcallNameSizeTable[Entry];
    StringRef Str(
      &RTLIB::RuntimeLibcallsInfo::RuntimeLibcallImplNameTableStorage[StrOffset],
      StrSize);
    if (Str == Name)
      return libcallImplNameHit(Entry, StrOffset);
  }

  return enum_seq(RTLIB::Unsupported, RTLIB::Unsupported);
}
)";
}

void RuntimeLibcallEmitter::emitGetInitRuntimeLibcallNames(
    raw_ostream &OS) const {
  // Emit the implementation names
  StringToOffsetTable Table(/*AppendZero=*/true,
                            "RTLIB::RuntimeLibcallsInfo::");

  {
    IfDefEmitter IfDef(OS, "GET_INIT_RUNTIME_LIBCALL_NAMES");

    for (const RuntimeLibcallImpl &LibCallImpl :
         Libcalls.getRuntimeLibcallImplDefList())
      Table.GetOrAddStringOffset(LibCallImpl.getLibcallFuncName());

    Table.EmitStringTableDef(OS, "RuntimeLibcallImplNameTable");
    OS << R"(
const uint16_t RTLIB::RuntimeLibcallsInfo::RuntimeLibcallNameOffsetTable[] = {
)";

    OS << formatv("  {}, // {}\n", Table.GetStringOffset(""),
                  ""); // Unsupported entry
    for (const RuntimeLibcallImpl &LibCallImpl :
         Libcalls.getRuntimeLibcallImplDefList()) {
      StringRef ImplName = LibCallImpl.getLibcallFuncName();
      OS << formatv("  {}, // {}\n", Table.GetStringOffset(ImplName), ImplName);
    }
    OS << "};\n";

    OS << R"(
const uint8_t RTLIB::RuntimeLibcallsInfo::RuntimeLibcallNameSizeTable[] = {
)";

    OS << "  0,\n";
    for (const RuntimeLibcallImpl &LibCallImpl :
         Libcalls.getRuntimeLibcallImplDefList())
      OS << "  " << LibCallImpl.getLibcallFuncName().size() << ",\n";
    OS << "};\n\n";

    // Emit the reverse mapping from implementation libraries to RTLIB::Libcall
    OS << "const RTLIB::Libcall llvm::RTLIB::RuntimeLibcallsInfo::"
          "ImplToLibcall[RTLIB::NumLibcallImpls] = {\n"
          "  RTLIB::UNKNOWN_LIBCALL, // RTLIB::Unsupported\n";

    for (const RuntimeLibcallImpl &LibCallImpl :
         Libcalls.getRuntimeLibcallImplDefList()) {
      const RuntimeLibcall *Provides = LibCallImpl.getProvides();
      OS << "  ";
      Provides->emitEnumEntry(OS);
      OS << ", // ";
      LibCallImpl.emitEnumEntry(OS);
      OS << '\n';
    }

    OS << "};\n\n";
  }

  emitNameMatchHashTable(OS, Table);
}

void RuntimeLibcallEmitter::emitPredicateGroups(
    raw_ostream &OS, const Record *R,
    DenseMap<PredicateWithCC, LibcallsWithCC> &Pred2Funcs,
    SetVector<PredicateWithCC> &PredicateSorter, unsigned BaseIndent) const {
  SmallVector<PredicateWithCC, 0> SortedPredicates =
      PredicateSorter.takeVector();

  llvm::sort(SortedPredicates, [](PredicateWithCC A, PredicateWithCC B) {
    StringRef AName = A.Availability ? A.Availability->getName() : "";
    StringRef BName = B.Availability ? B.Availability->getName() : "";
    if (AName != BName)
      return AName < BName;
    // Break name ties on the calling convention for a deterministic order.
    StringRef ACC = A.CallingConv ? A.CallingConv->getName() : "";
    StringRef BCC = B.CallingConv ? B.CallingConv->getName() : "";
    return ACC < BCC;
  });

  for (PredicateWithCC Entry : SortedPredicates) {
    AvailabilityPredicate SubsetPredicate(Entry.Availability);
    unsigned IndentDepth = BaseIndent;

    auto It = Pred2Funcs.find(Entry);
    if (It == Pred2Funcs.end())
      continue;

    // Shared-core deduplication can empty a bucket.
    if (It->second.LibcallImpls.empty())
      continue;

    if (!SubsetPredicate.isAlwaysAvailable()) {
      IndentDepth = BaseIndent + 2;

      OS << indent(IndentDepth);
      SubsetPredicate.emitIf(OS);
    }

    LibcallsWithCC &FuncsWithCC = It->second;

    std::vector<const RuntimeLibcallImpl *> &Funcs = FuncsWithCC.LibcallImpls;

    // Records which impls are available, not which is selected, so a libcall
    // may have more than one. Order is irrelevant (each entry is a setAvailable
    // call); sort by the provided libcall, breaking ties on the impl enum for a
    // deterministic total order.
    llvm::sort(Funcs, [](const RuntimeLibcallImpl *A,
                         const RuntimeLibcallImpl *B) {
      return std::make_pair(A->getProvides()->getEnumVal(), A->getEnumVal()) <
             std::make_pair(B->getProvides()->getEnumVal(), B->getEnumVal());
    });

    OS << indent(IndentDepth + 2)
       << "static const RTLIB::LibcallImpl LibraryCalls";
    SubsetPredicate.emitTableVariableNameSuffix(OS);
    if (FuncsWithCC.CallingConv)
      OS << '_' << FuncsWithCC.CallingConv->getName();

    OS << "[] = {\n";
    for (const RuntimeLibcallImpl *LibCallImpl : Funcs) {
      OS << indent(IndentDepth + 6);
      LibCallImpl->emitEnumEntry(OS);
      OS << ", // " << LibCallImpl->getLibcallFuncName() << '\n';
    }

    OS << indent(IndentDepth + 2) << "};\n\n"
       << indent(IndentDepth + 2)
       << "for (const RTLIB::LibcallImpl Impl : LibraryCalls";
    SubsetPredicate.emitTableVariableNameSuffix(OS);
    if (FuncsWithCC.CallingConv)
      OS << '_' << FuncsWithCC.CallingConv->getName();

    OS << ") {\n" << indent(IndentDepth + 4) << "setAvailable(Impl);\n";

    if (FuncsWithCC.CallingConv) {
      StringRef CCEnum =
          FuncsWithCC.CallingConv->getValueAsString("CallingConv");
      OS << indent(IndentDepth + 4) << "setLibcallImplCallingConv(Impl, "
         << CCEnum << ");\n";
    }

    OS << indent(IndentDepth + 2) << "}\n";
    OS << '\n';

    if (!SubsetPredicate.isAlwaysAvailable()) {
      OS << indent(IndentDepth);
      SubsetPredicate.emitEndIf(OS);
      OS << '\n';
    }
  }
}

// Emit the linker name \p Name as a C++ identifier suffix, replacing characters
// invalid in an identifier (e.g. the '-' in "compiler-rt") with '_'.
static void emitLibFuncSuffix(raw_ostream &OS, StringRef Name) {
  for (char C : Name)
    OS << (isAlnum(C) || C == '_' ? C : '_');
}

void RuntimeLibcallEmitter::emitLibraryVariant(raw_ostream &OS,
                                               ExpandedLibrary &EL) const {
  AvailabilityPredicate LibPred(EL.Lib->getValueAsDef("Pred"));

  if (!LibPred.isAlwaysAvailable()) {
    OS << indent(2);
    LibPred.emitIf(OS);
  } else {
    // Own block scope so per-variant `LibraryCalls` tables do not collide.
    OS << indent(2) << "{\n";
  }

  emitPredicateGroups(OS, EL.Lib, EL.Pred2Funcs, EL.PredicateSorter,
                      /*BaseIndent=*/2);

  if (!LibPred.isAlwaysAvailable()) {
    OS << indent(2);
    LibPred.emitEndIf(OS);
  } else {
    OS << indent(2) << "}\n";
  }
}

void RuntimeLibcallEmitter::emitLibraryFunction(
    raw_ostream &OS, StringRef Name, ArrayRef<const Record *> Libs,
    ArrayRef<LibraryExclusion> Exclusions) const {
  OS << "void llvm::RTLIB::RuntimeLibcallsInfo::setAvailableLibFuncs_";
  emitLibFuncSuffix(OS, Name);
  OS << "(const llvm::Triple &TT, "
        "ExceptionHandling ExceptionModel, FloatABI::ABIType FloatABI, "
        "StringRef ABIName, "
        "LongDoubleFormat LongDoubleFormat) {\n";

  SmallVector<ExpandedLibrary, 2> Expanded;
  for (const Record *Lib : Libs) {
    ExpandedLibrary EL;
    EL.Lib = Lib;

    // Expand this library's members with a library-local Func2Preds.
    SetTheory Sets;
    DenseMap<const RuntimeLibcallImpl *,
             std::pair<std::vector<const Record *>, const Record *>>
        Func2Preds;
    Sets.addExpander("LibcallImpls", std::make_unique<LibcallPredicateExpander>(
                                         Libcalls, Func2Preds));

    SetTheory::RecSet Elements;
    Sets.evaluate(Lib->getValueInit("Impls"), Elements, Lib->getLoc());

    EL.PredicateSorter.insert(
        PredicateWithCC()); // No predicate or CC override first.

    for (const Record *Elt : Elements) {
      const RuntimeLibcallImpl *LibCallImpl =
          Libcalls.getRuntimeLibcallImpl(Elt);
      if (!LibCallImpl) {
        PrintError(Lib, "entry for LibcallLibrary is not a RuntimeLibcallImpl");
        PrintNote(Elt->getLoc(), "invalid entry `" + Elt->getName() + "`");
        continue;
      }

      auto It = Func2Preds.find(LibCallImpl);
      if (It == Func2Preds.end()) {
        EL.Pred2Funcs[PredicateWithCC()].LibcallImpls.push_back(LibCallImpl);
        EL.Unconditional.insert(LibCallImpl);
        continue;
      }

      for (const Record *Pred : It->second.first) {
        const Record *CC = It->second.second;
        PredicateWithCC Key(Pred, CC);
        auto &Entry = EL.Pred2Funcs[Key];
        Entry.LibcallImpls.push_back(LibCallImpl);
        Entry.CallingConv = CC;
        EL.PredicateSorter.insert(Key);
      }
    }

    Expanded.push_back(std::move(EL));
  }

  // Impls unconditional in every variant are emitted once and stripped from
  // each variant, so the shared core is not repeated.
  SetVector<const RuntimeLibcallImpl *> SharedCore;
  if (Expanded.size() > 1) {
    for (const RuntimeLibcallImpl *Impl : Expanded.front().Unconditional) {
      if (all_of(drop_begin(Expanded), [&](const ExpandedLibrary &EL) {
            return EL.Unconditional.contains(Impl);
          }))
        SharedCore.insert(Impl);
    }
  }

  if (!SharedCore.empty()) {
    // Emit the shared core once, then strip it from every variant.
    DenseMap<PredicateWithCC, LibcallsWithCC> CorePred2Funcs;
    SetVector<PredicateWithCC> CoreSorter;
    CoreSorter.insert(PredicateWithCC());
    for (const RuntimeLibcallImpl *Impl : SharedCore)
      CorePred2Funcs[PredicateWithCC()].LibcallImpls.push_back(Impl);
    emitPredicateGroups(OS, Libs.front(), CorePred2Funcs, CoreSorter,
                        /*BaseIndent=*/0);

    for (ExpandedLibrary &EL : Expanded) {
      auto &Funcs = EL.Pred2Funcs[PredicateWithCC()].LibcallImpls;
      llvm::erase_if(Funcs, [&](const RuntimeLibcallImpl *Impl) {
        return SharedCore.contains(Impl);
      });
    }
  }

  // Mark a variant deferred when it re-adds an impl its own consumer excludes
  // (same triple, via LibraryRef). Such a variant must be emitted after the
  // exclusion so the re-add wins while the exclusion still suppresses every
  // other variant's contribution.
  for (ExpandedLibrary &EL : Expanded) {
    const Record *ELPred = EL.Lib->getValueAsDef("Pred");
    SetVector<const RuntimeLibcallImpl *> Impls;
    for (const auto &[Key, Funcs] : EL.Pred2Funcs)
      Impls.insert(Funcs.LibcallImpls.begin(), Funcs.LibcallImpls.end());

    for (const LibraryExclusion &Excl : Exclusions) {
      if (Excl.TriplePred != ELPred)
        continue;
      if (any_of(Excl.Impls, [&](const RuntimeLibcallImpl *Impl) {
            return Impls.contains(Impl);
          })) {
        EL.Deferred = true;
        break;
      }
    }
  }

  // Emit each non-deferred variant under its own Pred.
  for (ExpandedLibrary &EL : Expanded) {
    if (!EL.Deferred)
      emitLibraryVariant(OS, EL);
  }

  // Emit each consumer's LibraryRef opt-outs.
  for (const LibraryExclusion &Excl : Exclusions) {
    OS << '\n' << indent(2);
    AvailabilityPredicate ExcludePred(Excl.TriplePred);
    ExcludePred.emitIf(OS);
    for (const RuntimeLibcallImpl *Impl : Excl.Impls) {
      OS << indent(4) << "setUnavailable(";
      Impl->emitEnumEntry(OS);
      OS << "); // " << Impl->getLibcallFuncName() << '\n';
    }

    OS << indent(2);
    ExcludePred.emitEndIf(OS);
  }

  // Deferred variants: emitted after exclusions so a target's own re-adds
  // override its own LibraryRef opt-outs (the exclusion still applied above
  // to every other variant's contributions).
  for (ExpandedLibrary &EL : Expanded) {
    if (EL.Deferred)
      emitLibraryVariant(OS, EL);
  }

  OS << "}\n\n";
}

MapVector<StringRef, std::vector<const Record *>>
RuntimeLibcallEmitter::collectLibrariesByName() const {
  MapVector<StringRef, std::vector<const Record *>> LibsByName;
  for (const Record *Lib : Records.getAllDerivedDefinitions("LibcallLibrary"))
    LibsByName[Lib->getValueAsString("LibraryName")].push_back(Lib);
  return LibsByName;
}

void RuntimeLibcallEmitter::emitRuntimeLibcallsInfoMemberDecls(
    raw_ostream &OS) const {
  IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALLS_INFO_MEMBER_DECLS");
  for (const auto &[Name, Libs] : collectLibrariesByName()) {
    OS << "void setAvailableLibFuncs_";
    emitLibFuncSuffix(OS, Name);
    OS << "(const llvm::Triple &TT, ExceptionHandling ExceptionModel, "
          "FloatABI::ABIType FloatABI, StringRef ABIName, "
          "LongDoubleFormat LongDoubleFormat);\n";
  }
}

void RuntimeLibcallEmitter::emitSystemRuntimeLibrarySetCalls(
    raw_ostream &OS) const {
  ArrayRef<const Record *> AllLibs =
      Records.getAllDerivedDefinitions("SystemRuntimeLibrary");

  // Collect each shared library's LibraryRef opt-outs, keyed by library name,
  // so its library function can emit them.
  MapVector<StringRef, std::vector<LibraryExclusion>> ExclusionsByLibName;
  for (const Record *R : AllLibs) {
    const DagInit *MemberDag =
        R->getValueAsDef("MemberList")->getValueAsDag("MemberList");
    for (const Init *Arg : MemberDag->getArgs()) {
      const auto *DI = dyn_cast<DefInit>(Arg);
      if (!DI || !DI->getDef()->isSubClassOf("LibraryRef"))
        continue;
      const Record *Def = DI->getDef();
      LibraryExclusion Excl{R->getValueAsDef("TriplePred"), {}};
      for (const Record *ExcludeRec : Def->getValueAsListOfDefs("Exclude")) {
        if (const RuntimeLibcallImpl *Impl =
                Libcalls.getRuntimeLibcallImpl(ExcludeRec))
          Excl.Impls.push_back(Impl);
      }

      if (!Excl.Impls.empty()) {
        StringRef LibName =
            Def->getValueAsDef("Library")->getValueAsString("LibraryName");
        ExclusionsByLibName[LibName].push_back(std::move(Excl));
      }
    }
  }

  for (const auto &[Name, Libs] : collectLibrariesByName())
    emitLibraryFunction(OS, Name, Libs, ExclusionsByLibName.lookup(Name));

  OS << "void llvm::RTLIB::RuntimeLibcallsInfo::setTargetRuntimeLibcallSets("
        "const llvm::Triple &TT, ExceptionHandling ExceptionModel, "
        "FloatABI::ABIType FloatABI, "
        "StringRef ABIName, LongDoubleFormat LongDoubleFormat) {\n";

  for (const Record *R : AllLibs) {
    OS << '\n';

    AvailabilityPredicate TopLevelPredicate(R->getValueAsDef("TriplePred"));

    OS << indent(2);
    TopLevelPredicate.emitIf(OS);

    if (const Record *DefaultCCClass =
            R->getValueAsDef("DefaultLibcallCallingConv")) {
      StringRef DefaultCC =
          DefaultCCClass->getValueAsString("CallingConv").trim();

      if (!DefaultCC.empty()) {
        OS << "    const CallingConv::ID DefaultCC = " << DefaultCC << ";\n"
           << "    for (CallingConv::ID &Entry : LibcallImplCallingConvs) {\n"
              "      Entry = DefaultCC;\n"
              "    }\n\n";
      }
    }

    // Split the top-level member list into named LibcallLibrary references
    // (dispatched to their own setAvailableLibFuncs_<name> under an
    // isLibraryAvailable guard) and the remaining bare impl / LibcallImpls
    // members. A LibraryRef also records impls to drop.
    struct DispatchLib {
      StringRef Name;
      std::vector<const RuntimeLibcallImpl *> Exclude;
    };
    const DagInit *MemberDag =
        R->getValueAsDef("MemberList")->getValueAsDag("MemberList");
    SmallVector<DispatchLib, 4> DispatchLibs;
    SmallVector<const Init *, 16> InlineArgs;
    SmallVector<const StringInit *, 16> InlineArgNames;
    for (auto [Arg, ArgName] :
         zip_equal(MemberDag->getArgs(), MemberDag->getArgNames())) {
      if (const auto *DI = dyn_cast<DefInit>(Arg)) {
        const Record *Def = DI->getDef();
        if (Def->isSubClassOf("LibcallLibrary")) {
          DispatchLibs.push_back({Def->getValueAsString("LibraryName"), {}});
          continue;
        }

        if (Def->isSubClassOf("LibraryRef")) {
          const Record *Lib = Def->getValueAsDef("Library");
          DispatchLib DL{Lib->getValueAsString("LibraryName"), {}};
          for (const Record *ExcludeRec :
               Def->getValueAsListOfDefs("Exclude")) {
            if (const RuntimeLibcallImpl *Impl =
                    Libcalls.getRuntimeLibcallImpl(ExcludeRec))
              DL.Exclude.push_back(Impl);
          }

          DispatchLibs.push_back(std::move(DL));
          continue;
        }
      }
      InlineArgs.push_back(Arg);
      InlineArgNames.push_back(ArgName);
    }

    const DagInit *InlineDag =
        DagInit::get(MemberDag->getOperator(), InlineArgs, InlineArgNames);

    SetTheory Sets;

    DenseMap<const RuntimeLibcallImpl *,
             std::pair<std::vector<const Record *>, const Record *>>
        Func2Preds;
    Sets.addExpander("LibcallImpls", std::make_unique<LibcallPredicateExpander>(
                                         Libcalls, Func2Preds));

    SetTheory::RecSet ElementsSet;
    Sets.evaluate(InlineDag, ElementsSet, R->getLoc());
    const SetTheory::RecSet *Elements = &ElementsSet;

    // Sort to get deterministic output
    SetVector<PredicateWithCC> PredicateSorter;
    PredicateSorter.insert(
        PredicateWithCC()); // No predicate or CC override first.

    constexpr unsigned BitsPerStorageElt = 64;
    DenseMap<PredicateWithCC, LibcallsWithCC> Pred2Funcs;

    SmallVector<uint64_t, 32> BitsetValues(divideCeil(
        Libcalls.getRuntimeLibcallImplDefList().size() + 1, BitsPerStorageElt));

    for (const Record *Elt : *Elements) {
      const RuntimeLibcallImpl *LibCallImpl =
          Libcalls.getRuntimeLibcallImpl(Elt);
      if (!LibCallImpl) {
        PrintError(R, "entry for SystemLibrary is not a RuntimeLibcallImpl");
        PrintNote(Elt->getLoc(), "invalid entry `" + Elt->getName() + "`");
        continue;
      }

      size_t BitIdx = LibCallImpl->getEnumVal();
      uint64_t BitmaskVal = uint64_t(1) << (BitIdx % BitsPerStorageElt);
      size_t BitsetIdx = BitIdx / BitsPerStorageElt;

      auto It = Func2Preds.find(LibCallImpl);
      if (It == Func2Preds.end()) {
        BitsetValues[BitsetIdx] |= BitmaskVal;
        Pred2Funcs[PredicateWithCC()].LibcallImpls.push_back(LibCallImpl);
        continue;
      }

      for (const Record *Pred : It->second.first) {
        const Record *CC = It->second.second;
        AvailabilityPredicate SubsetPredicate(Pred);
        if (SubsetPredicate.isAlwaysAvailable())
          BitsetValues[BitsetIdx] |= BitmaskVal;

        PredicateWithCC Key(Pred, CC);
        auto &Entry = Pred2Funcs[Key];
        Entry.LibcallImpls.push_back(LibCallImpl);
        Entry.CallingConv = It->second.second;
        PredicateSorter.insert(Key);
      }
    }

    OS << "    static constexpr LibcallImplBitset SystemAvailableImpls({\n"
       << indent(6);

    ListSeparator LS;
    unsigned EntryCount = 0;
    for (uint64_t Bits : BitsetValues) {
      if (EntryCount++ == 4) {
        EntryCount = 1;
        OS << ",\n" << indent(6);
      } else
        OS << LS;
      OS << format_hex(Bits, 16);
    }
    OS << "\n    });\n"
          "    AvailableLibcallImpls = SystemAvailableImpls;\n\n";

    // Dispatch to each named library's setup function. This must come after the
    // SystemAvailableImpls assignment above (which overwrites the bitset); the
    // library functions union their members in on top via setAvailable.
    for (const DispatchLib &DL : DispatchLibs) {
      OS << indent(4) << "if (isLibraryAvailable(\"" << DL.Name << "\"))\n"
         << indent(6) << "setAvailableLibFuncs_";
      emitLibFuncSuffix(OS, DL.Name);
      OS << "(TT, ExceptionModel, FloatABI, ABIName, LongDoubleFormat);\n";
    }
    if (!DispatchLibs.empty())
      OS << '\n';

    emitPredicateGroups(OS, R, Pred2Funcs, PredicateSorter, /*BaseIndent=*/2);

    OS << indent(4) << "return;\n" << indent(2);
    TopLevelPredicate.emitEndIf(OS);
  }

  // FIXME: This should be a fatal error. A few contexts are improperly relying
  // on RuntimeLibcalls constructed with fully unknown triples.
  OS << "  LLVM_DEBUG(dbgs() << \"no system runtime library applied to target "
        "\\'\" << TT.str() << \"\\'\\n\");\n"
        "}\n\n";
}

// Scalar FP type suffixes in the argument order of RTLIB::getFPLibCall, paired
// with the llvm::Type predicate used by the IR-level mapping.
static constexpr std::pair<StringRef, StringRef> ScalarFPSuffixes[] = {
    {"F32", "isFloatTy()"},         {"F64", "isDoubleTy()"},
    {"F80", "isX86_FP80Ty()"},      {"F128", "isFP128Ty()"},
    {"PPCF128", "isPPC_FP128Ty()"},
};

static std::vector<FPLibcallFamily>
collectFPLibcallFamilies(const RecordKeeper &Records) {
  std::vector<FPLibcallFamily> Families;
  for (const Record *R :
       Records.getAllDerivedDefinitions("RuntimeLibcallFamily"))
    Families.emplace_back(R);
  llvm::sort(Families, [](const FPLibcallFamily &A, const FPLibcallFamily &B) {
    return A.Base < B.Base;
  });
  return Families;
}

DenseSet<StringRef> RuntimeLibcallEmitter::collectLibcallNames() const {
  DenseSet<StringRef> LibcallNames;
  for (const RuntimeLibcall &LC : Libcalls.getRuntimeLibcallDefList())
    LibcallNames.insert(LC.getName());
  return LibcallNames;
}

void RuntimeLibcallEmitter::checkFPLibcallFamilies(
    ArrayRef<FPLibcallFamily> Families,
    const DenseSet<StringRef> &LibcallNames) const {
  std::vector<std::pair<StringRef, StringRef>> IntrinsicToBase;
  for (const FPLibcallFamily &Family : Families)
    for (StringRef Intrinsic : Family.Intrinsics)
      IntrinsicToBase.emplace_back(Intrinsic, Family.Base);
  llvm::sort(IntrinsicToBase);

  for (size_t I = 1, E = IntrinsicToBase.size(); I < E; ++I) {
    if (IntrinsicToBase[I].first == IntrinsicToBase[I - 1].first)
      PrintFatalError(
          "intrinsic '" + IntrinsicToBase[I].first +
          "' is mapped by multiple RuntimeLibcallFamily records ('" +
          IntrinsicToBase[I - 1].second + "' and '" +
          IntrinsicToBase[I].second + "')");
  }

  for (const FPLibcallFamily &Family : Families) {
    bool AnyScalarLibcall = any_of(
        ScalarFPSuffixes, [&](const std::pair<StringRef, StringRef> &Entry) {
          return LibcallNames.contains((Family.Base + "_" + Entry.first).str());
        });
    if (!AnyScalarLibcall)
      PrintFatalError("no runtime libcall found for base name '" + Family.Base +
                      "'");
  }
}

/// Generate the declarations for the RTLIB::get<base>(EVT) selectors.
void RuntimeLibcallEmitter::emitFPLibcallSelectorDecls(
    raw_ostream &OS, ArrayRef<FPLibcallFamily> Families) const {
  IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALL_FP_SELECTOR_DECLS");
  for (const FPLibcallFamily &Family : Families)
    OS << "LLVM_ABI Libcall get" << Family.Base << "(EVT VT);\n";
}

/// Generate the backend RTLIB::get<base>(EVT) selectors from the floating-point
/// libcall families.
void RuntimeLibcallEmitter::emitFPLibcallSelectors(
    raw_ostream &OS, ArrayRef<FPLibcallFamily> Families,
    const DenseSet<StringRef> &LibcallNames) const {
  IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALL_FP_SELECTORS");

  // Only emit a libcall enumerator if it actually exists in the declared set.
  auto scalarEnum = [&](StringRef Base, StringRef Suffix) -> std::string {
    if (LibcallNames.contains((Base + "_" + Suffix).str()))
      return ("RTLIB::" + Base + "_" + Suffix).str();
    return "RTLIB::UNKNOWN_LIBCALL";
  };

  for (const FPLibcallFamily &Family : Families) {
    StringRef Base = Family.Base;
    OS << "RTLIB::Libcall llvm::RTLIB::get" << Base << "(EVT VT) {\n";

    if (!Family.VectorSuffixes.empty()) {
      OS << "  if (VT.isVector()) {\n"
            "    if (!VT.isSimple())\n"
            "      return RTLIB::UNKNOWN_LIBCALL;\n"
            "    switch (VT.getSimpleVT().SimpleTy) {\n";
      for (StringRef Suffix : Family.VectorSuffixes) {
        OS << "    case MVT::" << Suffix.lower()
           << ":\n      return RTLIB::" << Base << "_" << Suffix << ";\n";
      }
      OS << "    default:\n"
            "      return RTLIB::UNKNOWN_LIBCALL;\n"
            "    }\n"
            "  }\n";
    }

    OS << "  return getFPLibCall(VT";
    for (auto [Suffix, Pred] : ScalarFPSuffixes)
      OS << ", " << scalarEnum(Base, Suffix);
    OS << ");\n}\n\n";
  }
}

/// Emit the mapping from floating-point math intrinsics to the runtime libcall
/// they may lower to, keyed by intrinsic ID and floating-point type. This is
/// the IR-level counterpart to the backend's RTLIB::getXXX(EVT) selectors.
void RuntimeLibcallEmitter::emitGetLibcallForIntrinsic(
    raw_ostream &OS, ArrayRef<FPLibcallFamily> Families,
    const DenseSet<StringRef> &LibcallNames) const {
  IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALL_INTRINSIC_TO_LIBCALL");

  std::vector<std::pair<StringRef, StringRef>> IntrinsicToBase;
  for (const FPLibcallFamily &Family : Families)
    for (StringRef Intrinsic : Family.Intrinsics)
      IntrinsicToBase.emplace_back(Intrinsic, Family.Base);
  llvm::sort(IntrinsicToBase);

  MapVector<StringRef, SmallVector<StringRef, 2>> BaseToIntrinsics;
  for (auto [Intrinsic, Base] : IntrinsicToBase)
    BaseToIntrinsics[Base].push_back(Intrinsic);

  OS << "RTLIB::Libcall "
        "llvm::RTLIB::RuntimeLibcallsInfo::getLibcallForIntrinsic("
        "Intrinsic::ID ID, FunctionType *FTy) {\n"
        "  Type *Ty = FTy->getReturnType();\n"
        "  if (!Ty->isFloatingPointTy()) {\n"
        "    for (Type *ParamTy : FTy->params()) {\n"
        "      if (ParamTy->isFloatingPointTy()) {\n"
        "        Ty = ParamTy;\n"
        "        break;\n"
        "      }\n"
        "    }\n"
        "  }\n"
        "  if (!Ty->isFloatingPointTy())\n"
        "    return RTLIB::UNKNOWN_LIBCALL;\n"
        "  switch (ID) {\n";

  for (const auto &[Base, Intrinsics] : BaseToIntrinsics) {
    SmallVector<std::pair<StringRef, StringRef>, 5> Arms;
    for (auto [Suffix, Pred] : ScalarFPSuffixes)
      if (LibcallNames.contains((Base + "_" + Suffix).str()))
        Arms.emplace_back(Suffix, Pred);

    for (StringRef Intrinsic : Intrinsics)
      OS << "  case Intrinsic::" << Intrinsic << ":\n";
    for (auto [Suffix, Pred] : Arms)
      OS << "    if (Ty->" << Pred << ")\n      return RTLIB::" << Base << "_"
         << Suffix << ";\n";
    OS << "    return RTLIB::UNKNOWN_LIBCALL;\n";
  }

  OS << "  default:\n"
        "    return RTLIB::UNKNOWN_LIBCALL;\n"
        "  }\n"
        "}\n";
}

void RuntimeLibcallEmitter::run(raw_ostream &OS) {
  emitSourceFileHeader("Runtime LibCalls Source Fragment", OS, Records);
  emitGetRuntimeLibcallEnum(OS);

  emitGetInitRuntimeLibcallNames(OS);

  emitRuntimeLibcallsInfoMemberDecls(OS);

  {
    IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALLS_INFO");
    emitSystemRuntimeLibrarySetCalls(OS);
  }

  std::vector<FPLibcallFamily> FPFamilies = collectFPLibcallFamilies(Records);
  DenseSet<StringRef> LibcallNames = collectLibcallNames();
  checkFPLibcallFamilies(FPFamilies, LibcallNames);
  emitFPLibcallSelectorDecls(OS, FPFamilies);
  emitFPLibcallSelectors(OS, FPFamilies, LibcallNames);
  emitGetLibcallForIntrinsic(OS, FPFamilies, LibcallNames);
}

static TableGen::Emitter::OptClass<RuntimeLibcallEmitter>
    X("gen-runtime-libcalls", "Generate RuntimeLibcalls");