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 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(x: Val.Predicate, y: Val.CallingConv);
62 return DenseMapInfo<
63 std::pair<const Record *, const Record *>>::getHashValue(PairVal: 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() + 1
119 << ";\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(data: 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 hashes
136static std::pair<int, int>
137computePerfectHashParameters(ArrayRef<uint64_t> Hashes) {
138 // Chosen based on experimentation with llvm/benchmarks/RuntimeLibcalls.cpp
139 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(A: 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(t&: Hashes, u&: 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(reason: "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(V: ImplName).second) {
210 MaxFuncNameSize = std::max(a: MaxFuncNameSize, b: ImplName.size());
211 TableValues[Index] = LibCallImpl.getEnumVal();
212 Hashes[Index++] = hash(Str: ImplName);
213 }
214 }
215
216 // Trim excess elements from non-unique entries.
217 Hashes.resize(new_size: SeenFuncNames.size());
218 TableValues.resize(new_size: 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 miss
231 // case on the set of symbols in a clang binary. Emit this as an inlinable
232 // precondition in the header.
233 //
234 // The empty check is also used to get sensible behavior on anonymous
235 // functions.
236 //
237 // TODO: It may make more sense to split the search by string size more. There
238 // 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 << MaxFuncNameSize
245 << ")\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(Keywords: 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 values
265 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 << ") * " << Collisions
274 << ";\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 names
295 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(Str: LibCallImpl.getLibcallFuncName());
304
305 Table.EmitStringTableDef(OS, Name: "RuntimeLibcallImplNameTable");
306 OS << R"(
307const uint16_t RTLIB::RuntimeLibcallsInfo::RuntimeLibcallNameOffsetTable[] = {
308)";
309
310 OS << formatv(Fmt: " {}, // {}\n", Vals: Table.GetStringOffset(Str: ""),
311 Vals: ""); // Unsupported entry
312 for (const RuntimeLibcallImpl &LibCallImpl :
313 Libcalls.getRuntimeLibcallImplDefList()) {
314 StringRef ImplName = LibCallImpl.getLibcallFuncName();
315 OS << formatv(Fmt: " {}, // {}\n", Vals: Table.GetStringOffset(Str: ImplName), Vals&: 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::Libcall
330 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, OffsetTable&: 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(ClassName: "SystemRuntimeLibrary");
359
360 for (const Record *R : AllLibs) {
361 OS << '\n';
362
363 AvailabilityPredicate TopLevelPredicate(R->getValueAsDef(FieldName: "TriplePred"));
364
365 OS << indent(2);
366 TopLevelPredicate.emitIf(OS);
367
368 if (const Record *DefaultCCClass =
369 R->getValueAsDef(FieldName: "DefaultLibcallCallingConv")) {
370 StringRef DefaultCC =
371 DefaultCCClass->getValueAsString(FieldName: "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(ClassName: "LibcallImpls", std::make_unique<LibcallPredicateExpander>(
387 args: Libcalls, args&: Func2Preds));
388
389 const SetTheory::RecVec *Elements =
390 Sets.expand(Set: R->getValueAsDef(FieldName: "MemberList"));
391
392 // Sort to get deterministic output
393 SetVector<PredicateWithCC> PredicateSorter;
394 PredicateSorter.insert(
395 X: 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 Numerator: Libcalls.getRuntimeLibcallImplDefList().size() + 1, Denominator: BitsPerStorageElt));
402
403 for (const Record *Elt : *Elements) {
404 const RuntimeLibcallImpl *LibCallImpl =
405 Libcalls.getRuntimeLibcallImpl(Def: Elt);
406 if (!LibCallImpl) {
407 PrintError(Rec: R, Msg: "entry for SystemLibrary is not a RuntimeLibcallImpl");
408 PrintNote(NoteLoc: Elt->getLoc(), Msg: "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(Val: LibCallImpl);
417 if (It == Func2Preds.end()) {
418 BitsetValues[BitsetIdx] |= BitmaskVal;
419 Pred2Funcs[PredicateWithCC()].LibcallImpls.push_back(x: 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(x: LibCallImpl);
432 Entry.CallingConv = It->second.second;
433 PredicateSorter.insert(X: 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 } else
447 OS << LS;
448 OS << format_hex(N: Bits, Width: 16);
449 }
450 OS << "\n });\n"
451 " AvailableLibcallImpls = SystemAvailableImpls;\n\n";
452
453 SmallVector<PredicateWithCC, 0> SortedPredicates =
454 PredicateSorter.takeVector();
455
456 llvm::sort(C&: SortedPredicates, Comp: [](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(Val: 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 the
482 // selection table.
483 //
484 // FIXME: We need to generate separate functions for
485 // 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 the
488 // entries from the default set may win over the replacements unless
489 // they are explicitly removed.
490 stable_sort(Range&: Funcs, C: [](const RuntimeLibcallImpl *A,
491 const RuntimeLibcallImpl *B) {
492 return A->getProvides()->getEnumVal() < B->getProvides()->getEnumVal();
493 });
494
495 auto UniqueI = llvm::unique(
496 R&: Funcs, P: [&](const RuntimeLibcallImpl *A, const RuntimeLibcallImpl *B) {
497 if (A->getProvides() == B->getProvides()) {
498 PrintWarning(WarningLoc: R->getLoc(),
499 Msg: 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(first: UniqueI, last: 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(FieldName: "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 relying
555 // 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(Desc: "Runtime LibCalls Source Fragment", OS, Record: 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