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