575 lines · cpp
1//===- RuntimeLibcallEmitter.cpp - Properties from RuntimeLibcalls.td -----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#define DEBUG_TYPE "runtime-libcall-emitter"10 11#include "RuntimeLibcalls.h"12 13#include "llvm/ADT/DenseSet.h"14#include "llvm/ADT/StringRef.h"15#include "llvm/Support/Debug.h"16#include "llvm/Support/Format.h"17#include "llvm/Support/FormatVariadic.h"18#include "llvm/Support/raw_ostream.h"19#include "llvm/Support/xxhash.h"20#include "llvm/TableGen/CodeGenHelpers.h"21#include "llvm/TableGen/Error.h"22#include "llvm/TableGen/Record.h"23#include "llvm/TableGen/SetTheory.h"24#include "llvm/TableGen/StringToOffsetTable.h"25#include "llvm/TableGen/TableGenBackend.h"26 27using namespace llvm;28 29namespace {30// Pair of a RuntimeLibcallPredicate and LibcallCallingConv to use as a map key.31struct PredicateWithCC {32 const Record *Predicate = nullptr;33 const Record *CallingConv = nullptr;34 35 PredicateWithCC() = default;36 PredicateWithCC(std::pair<const Record *, const Record *> P)37 : Predicate(P.first), CallingConv(P.second) {}38 39 PredicateWithCC(const Record *P, const Record *C)40 : Predicate(P), CallingConv(C) {}41};42 43inline bool operator==(PredicateWithCC LHS, PredicateWithCC RHS) {44 return LHS.Predicate == RHS.Predicate && LHS.CallingConv == RHS.CallingConv;45}46} // namespace47 48namespace llvm {49template <> struct DenseMapInfo<PredicateWithCC, void> {50 static inline PredicateWithCC getEmptyKey() {51 return DenseMapInfo<52 std::pair<const Record *, const Record *>>::getEmptyKey();53 }54 55 static inline PredicateWithCC getTombstoneKey() {56 return DenseMapInfo<57 std::pair<const Record *, const Record *>>::getTombstoneKey();58 }59 60 static unsigned getHashValue(const PredicateWithCC Val) {61 auto Pair = std::make_pair(Val.Predicate, Val.CallingConv);62 return DenseMapInfo<63 std::pair<const Record *, const Record *>>::getHashValue(Pair);64 }65 66 static bool isEqual(PredicateWithCC LHS, PredicateWithCC RHS) {67 return LHS == RHS;68 }69};70 71class RuntimeLibcallEmitter {72private:73 const RecordKeeper &Records;74 RuntimeLibcalls Libcalls;75 76 void emitGetRuntimeLibcallEnum(raw_ostream &OS) const;77 78 void emitNameMatchHashTable(raw_ostream &OS,79 StringToOffsetTable &OffsetTable) const;80 81 void emitGetInitRuntimeLibcallNames(raw_ostream &OS) const;82 83 void emitSystemRuntimeLibrarySetCalls(raw_ostream &OS) const;84 85public:86 RuntimeLibcallEmitter(const RecordKeeper &R) : Records(R), Libcalls(R) {}87 88 void run(raw_ostream &OS);89};90 91} // End anonymous namespace.92 93void RuntimeLibcallEmitter::emitGetRuntimeLibcallEnum(raw_ostream &OS) const {94 IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALL_ENUM");95 96 OS << "namespace llvm {\n"97 "namespace RTLIB {\n"98 "enum Libcall : unsigned short {\n";99 100 for (const RuntimeLibcall &LibCall : Libcalls.getRuntimeLibcallDefList()) {101 StringRef Name = LibCall.getName();102 OS << " " << Name << " = " << LibCall.getEnumVal() << ",\n";103 }104 105 OS << " UNKNOWN_LIBCALL = " << Libcalls.getRuntimeLibcallDefList().size()106 << "\n};\n\n"107 "enum LibcallImpl : unsigned short {\n"108 " Unsupported = 0,\n";109 110 for (const RuntimeLibcallImpl &LibCall :111 Libcalls.getRuntimeLibcallImplDefList()) {112 OS << " impl_" << LibCall.getName() << " = " << LibCall.getEnumVal()113 << ", // " << LibCall.getLibcallFuncName() << '\n';114 }115 116 OS << "};\n"117 << "constexpr size_t NumLibcallImpls = "118 << Libcalls.getRuntimeLibcallImplDefList().size() + 1119 << ";\n"120 "} // End namespace RTLIB\n"121 "} // End namespace llvm\n";122}123 124// StringMap uses xxh3_64bits, truncated to uint32_t.125static uint64_t hash(StringRef Str) {126 return static_cast<uint32_t>(xxh3_64bits(Str));127}128 129static void emitHashFunction(raw_ostream &OS) {130 OS << "static inline uint64_t hash(StringRef Str) {\n"131 " return static_cast<uint32_t>(xxh3_64bits(Str));\n"132 "}\n\n";133}134 135/// Return the table size, maximum number of collisions for the set of hashes136static std::pair<int, int>137computePerfectHashParameters(ArrayRef<uint64_t> Hashes) {138 // Chosen based on experimentation with llvm/benchmarks/RuntimeLibcalls.cpp139 const int SizeOverhead = 4;140 141 // Index derived from hash -> number of collisions.142 DenseMap<uint64_t, int> Table;143 144 unsigned NumHashes = Hashes.size();145 146 for (int MaxCollisions = 1;; ++MaxCollisions) {147 for (unsigned N = NextPowerOf2(NumHashes - 1); N < SizeOverhead * NumHashes;148 N <<= 1) {149 Table.clear();150 151 bool NeedResize = false;152 for (uint64_t H : Hashes) {153 uint64_t Idx = H % static_cast<uint64_t>(N);154 if (++Table[Idx] > MaxCollisions) {155 // Need to resize the final table if we increased the collision count.156 NeedResize = true;157 break;158 }159 }160 161 if (!NeedResize)162 return {N, MaxCollisions};163 }164 }165}166 167static std::vector<unsigned>168constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords,169 ArrayRef<uint64_t> Hashes,170 ArrayRef<unsigned> TableValues, int Size,171 int Collisions, StringToOffsetTable &OffsetTable) {172 std::vector<unsigned> Lookup(Size * Collisions);173 174 for (auto [HashValue, TableValue] : zip(Hashes, TableValues)) {175 uint64_t Idx = (HashValue % static_cast<uint64_t>(Size)) *176 static_cast<uint64_t>(Collisions);177 178 bool Found = false;179 for (int J = 0; J < Collisions; ++J) {180 unsigned &Entry = Lookup[Idx + J];181 if (Entry == 0) {182 Entry = TableValue;183 Found = true;184 break;185 }186 }187 188 if (!Found)189 reportFatalInternalError("failure to hash");190 }191 192 return Lookup;193}194 195/// Generate hash table based lookup by name.196void RuntimeLibcallEmitter::emitNameMatchHashTable(197 raw_ostream &OS, StringToOffsetTable &OffsetTable) const {198 ArrayRef<RuntimeLibcallImpl> RuntimeLibcallImplDefList =199 Libcalls.getRuntimeLibcallImplDefList();200 std::vector<uint64_t> Hashes(RuntimeLibcallImplDefList.size());201 std::vector<unsigned> TableValues(RuntimeLibcallImplDefList.size());202 DenseSet<StringRef> SeenFuncNames;203 204 size_t MaxFuncNameSize = 0;205 size_t Index = 0;206 207 for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {208 StringRef ImplName = LibCallImpl.getLibcallFuncName();209 if (SeenFuncNames.insert(ImplName).second) {210 MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size());211 TableValues[Index] = LibCallImpl.getEnumVal();212 Hashes[Index++] = hash(ImplName);213 }214 }215 216 // Trim excess elements from non-unique entries.217 Hashes.resize(SeenFuncNames.size());218 TableValues.resize(SeenFuncNames.size());219 220 LLVM_DEBUG({221 for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {222 StringRef ImplName = LibCallImpl.getLibcallFuncName();223 if (ImplName.size() == MaxFuncNameSize) {224 dbgs() << "Maximum runtime libcall name size: " << ImplName << '('225 << MaxFuncNameSize << ")\n";226 }227 }228 });229 230 // Early exiting on the symbol name provides a significant speedup in the miss231 // case on the set of symbols in a clang binary. Emit this as an inlinable232 // precondition in the header.233 //234 // The empty check is also used to get sensible behavior on anonymous235 // functions.236 //237 // TODO: It may make more sense to split the search by string size more. There238 // are a few outliers, most call names are small.239 {240 IfDefEmitter IfDef(OS, "GET_LOOKUP_LIBCALL_IMPL_NAME_BODY");241 242 OS << " size_t Size = Name.size();\n"243 " if (Size == 0 || Size > "244 << MaxFuncNameSize245 << ")\n"246 " return enum_seq(RTLIB::Unsupported, RTLIB::Unsupported);\n"247 " return lookupLibcallImplNameImpl(Name);\n";248 }249 250 auto [Size, Collisions] = computePerfectHashParameters(Hashes);251 std::vector<unsigned> Lookup =252 constructPerfectHashTable(RuntimeLibcallImplDefList, Hashes, TableValues,253 Size, Collisions, OffsetTable);254 255 LLVM_DEBUG(dbgs() << "Runtime libcall perfect hashing parameters: Size = "256 << Size << ", maximum collisions = " << Collisions << '\n');257 258 IfDefEmitter IfDef(OS, "DEFINE_GET_LOOKUP_LIBCALL_IMPL_NAME");259 emitHashFunction(OS);260 261 OS << "iota_range<RTLIB::LibcallImpl> RTLIB::RuntimeLibcallsInfo::"262 "lookupLibcallImplNameImpl(StringRef Name) {\n";263 264 // Emit RTLIB::LibcallImpl values265 OS << " static constexpr uint16_t HashTableNameToEnum[" << Lookup.size()266 << "] = {\n";267 268 for (unsigned TableVal : Lookup)269 OS << " " << TableVal << ",\n";270 271 OS << " };\n\n";272 273 OS << " unsigned Idx = (hash(Name) % " << Size << ") * " << Collisions274 << ";\n\n"275 " for (int I = 0; I != "276 << Collisions << R"(; ++I) {277 const uint16_t Entry = HashTableNameToEnum[Idx + I];278 const uint16_t StrOffset = RuntimeLibcallNameOffsetTable[Entry];279 const uint8_t StrSize = RuntimeLibcallNameSizeTable[Entry];280 StringRef Str(281 &RTLIB::RuntimeLibcallsInfo::RuntimeLibcallImplNameTableStorage[StrOffset],282 StrSize);283 if (Str == Name)284 return libcallImplNameHit(Entry, StrOffset);285 }286 287 return enum_seq(RTLIB::Unsupported, RTLIB::Unsupported);288}289)";290}291 292void RuntimeLibcallEmitter::emitGetInitRuntimeLibcallNames(293 raw_ostream &OS) const {294 // Emit the implementation names295 StringToOffsetTable Table(/*AppendZero=*/true,296 "RTLIB::RuntimeLibcallsInfo::");297 298 {299 IfDefEmitter IfDef(OS, "GET_INIT_RUNTIME_LIBCALL_NAMES");300 301 for (const RuntimeLibcallImpl &LibCallImpl :302 Libcalls.getRuntimeLibcallImplDefList())303 Table.GetOrAddStringOffset(LibCallImpl.getLibcallFuncName());304 305 Table.EmitStringTableDef(OS, "RuntimeLibcallImplNameTable");306 OS << R"(307const uint16_t RTLIB::RuntimeLibcallsInfo::RuntimeLibcallNameOffsetTable[] = {308)";309 310 OS << formatv(" {}, // {}\n", Table.GetStringOffset(""),311 ""); // Unsupported entry312 for (const RuntimeLibcallImpl &LibCallImpl :313 Libcalls.getRuntimeLibcallImplDefList()) {314 StringRef ImplName = LibCallImpl.getLibcallFuncName();315 OS << formatv(" {}, // {}\n", Table.GetStringOffset(ImplName), ImplName);316 }317 OS << "};\n";318 319 OS << R"(320const uint8_t RTLIB::RuntimeLibcallsInfo::RuntimeLibcallNameSizeTable[] = {321)";322 323 OS << " 0,\n";324 for (const RuntimeLibcallImpl &LibCallImpl :325 Libcalls.getRuntimeLibcallImplDefList())326 OS << " " << LibCallImpl.getLibcallFuncName().size() << ",\n";327 OS << "};\n\n";328 329 // Emit the reverse mapping from implementation libraries to RTLIB::Libcall330 OS << "const RTLIB::Libcall llvm::RTLIB::RuntimeLibcallsInfo::"331 "ImplToLibcall[RTLIB::NumLibcallImpls] = {\n"332 " RTLIB::UNKNOWN_LIBCALL, // RTLIB::Unsupported\n";333 334 for (const RuntimeLibcallImpl &LibCallImpl :335 Libcalls.getRuntimeLibcallImplDefList()) {336 const RuntimeLibcall *Provides = LibCallImpl.getProvides();337 OS << " ";338 Provides->emitEnumEntry(OS);339 OS << ", // ";340 LibCallImpl.emitEnumEntry(OS);341 OS << '\n';342 }343 344 OS << "};\n\n";345 }346 347 emitNameMatchHashTable(OS, Table);348}349 350void RuntimeLibcallEmitter::emitSystemRuntimeLibrarySetCalls(351 raw_ostream &OS) const {352 OS << "void llvm::RTLIB::RuntimeLibcallsInfo::setTargetRuntimeLibcallSets("353 "const llvm::Triple &TT, ExceptionHandling ExceptionModel, "354 "FloatABI::ABIType FloatABI, EABI EABIVersion, "355 "StringRef ABIName) {\n";356 357 ArrayRef<const Record *> AllLibs =358 Records.getAllDerivedDefinitions("SystemRuntimeLibrary");359 360 for (const Record *R : AllLibs) {361 OS << '\n';362 363 AvailabilityPredicate TopLevelPredicate(R->getValueAsDef("TriplePred"));364 365 OS << indent(2);366 TopLevelPredicate.emitIf(OS);367 368 if (const Record *DefaultCCClass =369 R->getValueAsDef("DefaultLibcallCallingConv")) {370 StringRef DefaultCC =371 DefaultCCClass->getValueAsString("CallingConv").trim();372 373 if (!DefaultCC.empty()) {374 OS << " const CallingConv::ID DefaultCC = " << DefaultCC << ";\n"375 << " for (CallingConv::ID &Entry : LibcallImplCallingConvs) {\n"376 " Entry = DefaultCC;\n"377 " }\n\n";378 }379 }380 381 SetTheory Sets;382 383 DenseMap<const RuntimeLibcallImpl *,384 std::pair<std::vector<const Record *>, const Record *>>385 Func2Preds;386 Sets.addExpander("LibcallImpls", std::make_unique<LibcallPredicateExpander>(387 Libcalls, Func2Preds));388 389 const SetTheory::RecVec *Elements =390 Sets.expand(R->getValueAsDef("MemberList"));391 392 // Sort to get deterministic output393 SetVector<PredicateWithCC> PredicateSorter;394 PredicateSorter.insert(395 PredicateWithCC()); // No predicate or CC override first.396 397 constexpr unsigned BitsPerStorageElt = 64;398 DenseMap<PredicateWithCC, LibcallsWithCC> Pred2Funcs;399 400 SmallVector<uint64_t, 32> BitsetValues(divideCeil(401 Libcalls.getRuntimeLibcallImplDefList().size() + 1, BitsPerStorageElt));402 403 for (const Record *Elt : *Elements) {404 const RuntimeLibcallImpl *LibCallImpl =405 Libcalls.getRuntimeLibcallImpl(Elt);406 if (!LibCallImpl) {407 PrintError(R, "entry for SystemLibrary is not a RuntimeLibcallImpl");408 PrintNote(Elt->getLoc(), "invalid entry `" + Elt->getName() + "`");409 continue;410 }411 412 size_t BitIdx = LibCallImpl->getEnumVal();413 uint64_t BitmaskVal = uint64_t(1) << (BitIdx % BitsPerStorageElt);414 size_t BitsetIdx = BitIdx / BitsPerStorageElt;415 416 auto It = Func2Preds.find(LibCallImpl);417 if (It == Func2Preds.end()) {418 BitsetValues[BitsetIdx] |= BitmaskVal;419 Pred2Funcs[PredicateWithCC()].LibcallImpls.push_back(LibCallImpl);420 continue;421 }422 423 for (const Record *Pred : It->second.first) {424 const Record *CC = It->second.second;425 AvailabilityPredicate SubsetPredicate(Pred);426 if (SubsetPredicate.isAlwaysAvailable())427 BitsetValues[BitsetIdx] |= BitmaskVal;428 429 PredicateWithCC Key(Pred, CC);430 auto &Entry = Pred2Funcs[Key];431 Entry.LibcallImpls.push_back(LibCallImpl);432 Entry.CallingConv = It->second.second;433 PredicateSorter.insert(Key);434 }435 }436 437 OS << " static constexpr LibcallImplBitset SystemAvailableImpls({\n"438 << indent(6);439 440 ListSeparator LS;441 unsigned EntryCount = 0;442 for (uint64_t Bits : BitsetValues) {443 if (EntryCount++ == 4) {444 EntryCount = 1;445 OS << ",\n" << indent(6);446 } else447 OS << LS;448 OS << format_hex(Bits, 16);449 }450 OS << "\n });\n"451 " AvailableLibcallImpls = SystemAvailableImpls;\n\n";452 453 SmallVector<PredicateWithCC, 0> SortedPredicates =454 PredicateSorter.takeVector();455 456 llvm::sort(SortedPredicates, [](PredicateWithCC A, PredicateWithCC B) {457 StringRef AName = A.Predicate ? A.Predicate->getName() : "";458 StringRef BName = B.Predicate ? B.Predicate->getName() : "";459 return AName < BName;460 });461 462 for (PredicateWithCC Entry : SortedPredicates) {463 AvailabilityPredicate SubsetPredicate(Entry.Predicate);464 unsigned IndentDepth = 2;465 466 auto It = Pred2Funcs.find(Entry);467 if (It == Pred2Funcs.end())468 continue;469 470 if (!SubsetPredicate.isAlwaysAvailable()) {471 IndentDepth = 4;472 473 OS << indent(IndentDepth);474 SubsetPredicate.emitIf(OS);475 }476 477 LibcallsWithCC &FuncsWithCC = It->second;478 479 std::vector<const RuntimeLibcallImpl *> &Funcs = FuncsWithCC.LibcallImpls;480 481 // Ensure we only emit a unique implementation per libcall in the482 // selection table.483 //484 // FIXME: We need to generate separate functions for485 // is-libcall-available and should-libcall-be-used to avoid this.486 //487 // This also makes it annoying to make use of the default set, since the488 // entries from the default set may win over the replacements unless489 // they are explicitly removed.490 stable_sort(Funcs, [](const RuntimeLibcallImpl *A,491 const RuntimeLibcallImpl *B) {492 return A->getProvides()->getEnumVal() < B->getProvides()->getEnumVal();493 });494 495 auto UniqueI = llvm::unique(496 Funcs, [&](const RuntimeLibcallImpl *A, const RuntimeLibcallImpl *B) {497 if (A->getProvides() == B->getProvides()) {498 PrintWarning(R->getLoc(),499 Twine("conflicting implementations for libcall " +500 A->getProvides()->getName() + ": " +501 A->getLibcallFuncName() + ", " +502 B->getLibcallFuncName()));503 return true;504 }505 506 return false;507 });508 509 Funcs.erase(UniqueI, Funcs.end());510 511 OS << indent(IndentDepth + 2)512 << "static const RTLIB::LibcallImpl LibraryCalls";513 SubsetPredicate.emitTableVariableNameSuffix(OS);514 if (FuncsWithCC.CallingConv)515 OS << '_' << FuncsWithCC.CallingConv->getName();516 517 OS << "[] = {\n";518 for (const RuntimeLibcallImpl *LibCallImpl : Funcs) {519 OS << indent(IndentDepth + 6);520 LibCallImpl->emitEnumEntry(OS);521 OS << ", // " << LibCallImpl->getLibcallFuncName() << '\n';522 }523 524 OS << indent(IndentDepth + 2) << "};\n\n"525 << indent(IndentDepth + 2)526 << "for (const RTLIB::LibcallImpl Impl : LibraryCalls";527 SubsetPredicate.emitTableVariableNameSuffix(OS);528 if (FuncsWithCC.CallingConv)529 OS << '_' << FuncsWithCC.CallingConv->getName();530 531 OS << ") {\n" << indent(IndentDepth + 4) << "setAvailable(Impl);\n";532 533 if (FuncsWithCC.CallingConv) {534 StringRef CCEnum =535 FuncsWithCC.CallingConv->getValueAsString("CallingConv");536 OS << indent(IndentDepth + 4) << "setLibcallImplCallingConv(Impl, "537 << CCEnum << ");\n";538 }539 540 OS << indent(IndentDepth + 2) << "}\n";541 OS << '\n';542 543 if (!SubsetPredicate.isAlwaysAvailable()) {544 OS << indent(IndentDepth);545 SubsetPredicate.emitEndIf(OS);546 OS << '\n';547 }548 }549 550 OS << indent(4) << "return;\n" << indent(2);551 TopLevelPredicate.emitEndIf(OS);552 }553 554 // FIXME: This should be a fatal error. A few contexts are improperly relying555 // on RuntimeLibcalls constructed with fully unknown triples.556 OS << " LLVM_DEBUG(dbgs() << \"no system runtime library applied to target "557 "\\'\" << TT.str() << \"\\'\\n\");\n"558 "}\n\n";559}560 561void RuntimeLibcallEmitter::run(raw_ostream &OS) {562 emitSourceFileHeader("Runtime LibCalls Source Fragment", OS, Records);563 emitGetRuntimeLibcallEnum(OS);564 565 emitGetInitRuntimeLibcallNames(OS);566 567 {568 IfDefEmitter IfDef(OS, "GET_RUNTIME_LIBCALLS_INFO");569 emitSystemRuntimeLibrarySetCalls(OS);570 }571}572 573static TableGen::Emitter::OptClass<RuntimeLibcallEmitter>574 X("gen-runtime-libcalls", "Generate RuntimeLibcalls");575