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