libc/benchmarks/automemcpy/lib/CodeGen.cpp

   1 //===-- C++ code generation from NamedFunctionDescriptors -----------------===//
   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 // This code is responsible for generating the "Implementation.cpp" file.
   9 // The file is composed like this:
  10 //
  11 // 1. Includes
  12 // 2. Using statements to help readability.
  13 // 3. Source code for all the mem function implementations.
  14 // 4. The function to retrieve all the function descriptors with their name.
  15 //      llvm::ArrayRef<NamedFunctionDescriptor> getFunctionDescriptors();
  16 // 5. The functions for the benchmarking infrastructure:
  17 //      llvm::ArrayRef<MemcpyConfiguration> getMemcpyConfigurations();
  18 //      llvm::ArrayRef<MemcmpOrBcmpConfiguration> getMemcmpConfigurations();
  19 //      llvm::ArrayRef<MemcmpOrBcmpConfiguration> getBcmpConfigurations();
  20 //      llvm::ArrayRef<MemsetConfiguration> getMemsetConfigurations();
  21 //      llvm::ArrayRef<BzeroConfiguration> getBzeroConfigurations();
  22 //
  23 //
  24 // Sections 3, 4 and 5 are handled by the following namespaces:
  25 // - codegen::functions
  26 // - codegen::descriptors
  27 // - codegen::configurations
  28 //
  29 // The programming style is functionnal. In each of these namespace, the
  30 // original `NamedFunctionDescriptor` object is turned into a different type. We
  31 // make use of overloaded stream operators to format the resulting type into
  32 // either a function, a descriptor or a configuration. The entry point of each
  33 // namespace is the Serialize function.
  34 //
  35 // Note the code here is better understood by starting from the `Serialize`
  36 // function at the end of the file.
  37
  38 #include "automemcpy/CodeGen.h"
  39 #include <cassert>
  40 #include <llvm/ADT/STLExtras.h>
  41 #include <llvm/ADT/StringSet.h>
  42 #include <llvm/Support/FormatVariadic.h>
  43 #include <llvm/Support/raw_ostream.h>
  44 #include <optional>
  45 #include <set>
  46
  47 namespace llvm {
  48 namespace automemcpy {
  49 namespace codegen {
  50
  51 // The indentation string.
  52 static constexpr StringRef kIndent = "  ";
  53
  54 // The codegen namespace handles the serialization of a NamedFunctionDescriptor
  55 // into source code for the function, the descriptor and the configuration.
  56
  57 namespace functions {
  58
  59 // This namespace turns a NamedFunctionDescriptor into an actual implementation.
  60 // -----------------------------------------------------------------------------
  61 // e.g.
  62 // static void memcpy_0xB20D4702493C397E(char *__restrict dst,
  63 //                                       const char *__restrict src,
  64 //                                       size_t size) {
  65 //   using namespace __llvm_libc::x86;
  66 //   if(size == 0) return;
  67 //   if(size == 1) return copy<_1>(dst, src);
  68 //   if(size < 4) return copy<HeadTail<_2>>(dst, src, size);
  69 //   if(size < 8) return copy<HeadTail<_4>>(dst, src, size);
  70 //   if(size < 16) return copy<HeadTail<_8>>(dst, src, size);
  71 //   if(size < 32) return copy<HeadTail<_16>>(dst, src, size);
  72 //   return copy<Accelerator>(dst, src, size);
  73 // }
  74
  75 // The `Serialize` method turns a `NamedFunctionDescriptor` into a
  76 // `FunctionImplementation` which holds all the information needed to produce
  77 // the C++ source code.
  78
  79 // An Element with its size (e.g. `_16` in the example above).
  80 struct ElementType {
  81   size_t Size;
  82 };
  83 // The case `if(size == 0)` is encoded as a the Zero type.
  84 struct Zero {
  85   StringRef DefaultReturnValue;
  86 };
  87 // An individual size `if(size == X)` is encoded as an Individual type.
  88 struct Individual {
  89   size_t IfEq;
  90   ElementType Element;
  91 };
  92 // An overlap strategy is encoded as an Overlap type.
  93 struct Overlap {
  94   size_t IfLt;
  95   ElementType Element;
  96 };
  97 // A loop strategy is encoded as a Loop type.
  98 struct Loop {
  99   size_t IfLt;
 100   ElementType Element;
 101 };
 102 // An aligned loop strategy is encoded as an AlignedLoop type.
 103 struct AlignedLoop {
 104   size_t IfLt;
 105   ElementType Element;
 106   ElementType Alignment;
 107   StringRef AlignTo;
 108 };
 109 // The accelerator strategy.
 110 struct Accelerator {
 111   size_t IfLt;
 112 };
 113 // The Context stores data about the function type.
 114 struct Context {
 115   StringRef FunctionReturnType; // e.g. void* or int
 116   StringRef FunctionArgs;
 117   StringRef ElementOp; // copy, three_way_compare, splat_set, ...
 118   StringRef FixedSizeArgs;
 119   StringRef RuntimeSizeArgs;
 120   StringRef DefaultReturnValue;
 121 };
 122 // A detailed representation of the function implementation mapped from the
 123 // NamedFunctionDescriptor.
 124 struct FunctionImplementation {
 125   Context Ctx;
 126   StringRef Name;
 127   std::vector<Individual> Individuals;
 128   std::vector<Overlap> Overlaps;
 129   std::optional<Loop> Loop;
 130   std::optional<AlignedLoop> AlignedLoop;
 131   std::optional<Accelerator> Accelerator;
 132   ElementTypeClass ElementClass;
 133 };
 134
 135 // Returns the Context for each FunctionType.
 136 static Context getCtx(FunctionType FT) {
 137   switch (FT) {
 138   case FunctionType::MEMCPY:
 139     return {"void",
 140             "(char *__restrict dst, const char *__restrict src, size_t size)",
 141             "copy",
 142             "(dst, src)",
 143             "(dst, src, size)",
 144             ""};
 145   case FunctionType::MEMCMP:
 146     return {"int",
 147             "(const char * lhs, const char * rhs, size_t size)",
 148             "three_way_compare",
 149             "(lhs, rhs)",
 150             "(lhs, rhs, size)",
 151             "0"};
 152   case FunctionType::MEMSET:
 153     return {"void",
 154             "(char * dst, int value, size_t size)",
 155             "splat_set",
 156             "(dst, value)",
 157             "(dst, value, size)",
 158             ""};
 159   case FunctionType::BZERO:
 160     return {"void",           "(char * dst, size_t size)",
 161             "splat_set",      "(dst, 0)",
 162             "(dst, 0, size)", ""};
 163   default:
 164     report_fatal_error("Not yet implemented");
 165   }
 166 }
 167
 168 static StringRef getAligntoString(const AlignArg &AlignTo) {
 169   switch (AlignTo) {
 170   case AlignArg::_1:
 171     return "Arg::P1";
 172   case AlignArg::_2:
 173     return "Arg::P2";
 174   case AlignArg::ARRAY_SIZE:
 175     report_fatal_error("logic error");
 176   }
 177 }
 178
 179 static raw_ostream &operator<<(raw_ostream &Stream, const ElementType &E) {
 180   return Stream << '_' << E.Size;
 181 }
 182 static raw_ostream &operator<<(raw_ostream &Stream, const Individual &O) {
 183   return Stream << O.Element;
 184 }
 185 static raw_ostream &operator<<(raw_ostream &Stream, const Overlap &O) {
 186   return Stream << "HeadTail<" << O.Element << '>';
 187 }
 188 static raw_ostream &operator<<(raw_ostream &Stream, const Loop &O) {
 189   return Stream << "Loop<" << O.Element << '>';
 190 }
 191 static raw_ostream &operator<<(raw_ostream &Stream, const AlignedLoop &O) {
 192   return Stream << "Align<" << O.Alignment << ',' << O.AlignTo << ">::Then<"
 193                 << Loop{O.IfLt, O.Element} << ">";
 194 }
 195 static raw_ostream &operator<<(raw_ostream &Stream, const Accelerator &O) {
 196   return Stream << "Accelerator";
 197 }
 198
 199 template <typename T> struct IfEq {
 200   StringRef Op;
 201   StringRef Args;
 202   const T &Element;
 203 };
 204
 205 template <typename T> struct IfLt {
 206   StringRef Op;
 207   StringRef Args;
 208   const T &Element;
 209 };
 210
 211 static raw_ostream &operator<<(raw_ostream &Stream, const Zero &O) {
 212   Stream << kIndent << "if(size == 0) return";
 213   if (!O.DefaultReturnValue.empty())
 214     Stream << ' ' << O.DefaultReturnValue;
 215   return Stream << ";\n";
 216 }
 217
 218 template <typename T>
 219 static raw_ostream &operator<<(raw_ostream &Stream, const IfEq<T> &O) {
 220   return Stream << kIndent << "if(size == " << O.Element.IfEq << ") return "
 221                 << O.Op << '<' << O.Element << '>' << O.Args << ";\n";
 222 }
 223
 224 template <typename T>
 225 static raw_ostream &operator<<(raw_ostream &Stream, const IfLt<T> &O) {
 226   Stream << kIndent;
 227   if (O.Element.IfLt != kMaxSize)
 228     Stream << "if(size < " << O.Element.IfLt << ") ";
 229   return Stream << "return " << O.Op << '<' << O.Element << '>' << O.Args
 230                 << ";\n";
 231 }
 232
 233 static raw_ostream &operator<<(raw_ostream &Stream,
 234                                const ElementTypeClass &Class) {
 235   switch (Class) {
 236   case ElementTypeClass::SCALAR:
 237     return Stream << "scalar";
 238   case ElementTypeClass::BUILTIN:
 239     return Stream << "builtin";
 240   case ElementTypeClass::NATIVE:
 241     // FIXME: the framework should provide a `native` namespace that redirect to
 242     // x86, arm or other architectures.
 243     return Stream << "x86";
 244   }
 245 }
 246
 247 static raw_ostream &operator<<(raw_ostream &Stream,
 248                                const FunctionImplementation &FI) {
 249   const auto &Ctx = FI.Ctx;
 250   Stream << "static " << Ctx.FunctionReturnType << ' ' << FI.Name
 251          << Ctx.FunctionArgs << " {\n";
 252   Stream << kIndent << "using namespace __llvm_libc::" << FI.ElementClass
 253          << ";\n";
 254   for (const auto &I : FI.Individuals)
 255     if (I.Element.Size == 0)
 256       Stream << Zero{Ctx.DefaultReturnValue};
 257     else
 258       Stream << IfEq<Individual>{Ctx.ElementOp, Ctx.FixedSizeArgs, I};
 259   for (const auto &O : FI.Overlaps)
 260     Stream << IfLt<Overlap>{Ctx.ElementOp, Ctx.RuntimeSizeArgs, O};
 261   if (const auto &C = FI.Loop)
 262     Stream << IfLt<Loop>{Ctx.ElementOp, Ctx.RuntimeSizeArgs, *C};
 263   if (const auto &C = FI.AlignedLoop)
 264     Stream << IfLt<AlignedLoop>{Ctx.ElementOp, Ctx.RuntimeSizeArgs, *C};
 265   if (const auto &C = FI.Accelerator)
 266     Stream << IfLt<Accelerator>{Ctx.ElementOp, Ctx.RuntimeSizeArgs, *C};
 267   return Stream << "}\n";
 268 }
 269
 270 // Turns a `NamedFunctionDescriptor` into a `FunctionImplementation` unfolding
 271 // the contiguous and overlap region into several statements. The zero case is
 272 // also mapped to its own type.
 273 static FunctionImplementation
 274 getImplementation(const NamedFunctionDescriptor &NamedFD) {
 275   const FunctionDescriptor &FD = NamedFD.Desc;
 276   FunctionImplementation Impl;
 277   Impl.Ctx = getCtx(FD.Type);
 278   Impl.Name = NamedFD.Name;
 279   Impl.ElementClass = FD.ElementClass;
 280   if (auto C = FD.Contiguous)
 281     for (size_t I = C->Span.Begin; I < C->Span.End; ++I)
 282       Impl.Individuals.push_back(Individual{I, ElementType{I}});
 283   if (auto C = FD.Overlap)
 284     for (size_t I = C->Span.Begin; I < C->Span.End; I *= 2)
 285       Impl.Overlaps.push_back(Overlap{2 * I, ElementType{I}});
 286   if (const auto &L = FD.Loop)
 287     Impl.Loop = Loop{L->Span.End, ElementType{L->BlockSize}};
 288   if (const auto &AL = FD.AlignedLoop)
 289     Impl.AlignedLoop =
 290         AlignedLoop{AL->Loop.Span.End, ElementType{AL->Loop.BlockSize},
 291                     ElementType{AL->Alignment}, getAligntoString(AL->AlignTo)};
 292   if (const auto &A = FD.Accelerator)
 293     Impl.Accelerator = Accelerator{A->Span.End};
 294   return Impl;
 295 }
 296
 297 static void Serialize(raw_ostream &Stream,
 298                       ArrayRef<NamedFunctionDescriptor> Descriptors) {
 299
 300   for (const auto &FD : Descriptors)
 301     Stream << getImplementation(FD);
 302 }
 303
 304 } // namespace functions
 305
 306 namespace descriptors {
 307
 308 // This namespace generates the getFunctionDescriptors function:
 309 // -------------------------------------------------------------
 310 // e.g.
 311 // ArrayRef<NamedFunctionDescriptor> getFunctionDescriptors() {
 312 //   static constexpr NamedFunctionDescriptor kDescriptors[] = {
 313 //     {"memcpy_0xE00E29EE73994E2B",{FunctionType::MEMCPY,std::nullopt,std::nullopt,std::nullopt,std::nullopt,Accelerator{{0,kMaxSize}},ElementTypeClass::NATIVE}},
 314 //     {"memcpy_0x8661D80472487AB5",{FunctionType::MEMCPY,Contiguous{{0,1}},std::nullopt,std::nullopt,std::nullopt,Accelerator{{1,kMaxSize}},ElementTypeClass::NATIVE}},
 315 //     ...
 316 //   };
 317 //   return ArrayRef(kDescriptors);
 318 // }
 319
 320 static raw_ostream &operator<<(raw_ostream &Stream, const SizeSpan &SS) {
 321   Stream << "{" << SS.Begin << ',';
 322   if (SS.End == kMaxSize)
 323     Stream << "kMaxSize";
 324   else
 325     Stream << SS.End;
 326   return Stream << '}';
 327 }
 328 static raw_ostream &operator<<(raw_ostream &Stream, const Contiguous &O) {
 329   return Stream << "Contiguous{" << O.Span << '}';
 330 }
 331 static raw_ostream &operator<<(raw_ostream &Stream, const Overlap &O) {
 332   return Stream << "Overlap{" << O.Span << '}';
 333 }
 334 static raw_ostream &operator<<(raw_ostream &Stream, const Loop &O) {
 335   return Stream << "Loop{" << O.Span << ',' << O.BlockSize << '}';
 336 }
 337 static raw_ostream &operator<<(raw_ostream &Stream, const AlignArg &O) {
 338   switch (O) {
 339   case AlignArg::_1:
 340     return Stream << "AlignArg::_1";
 341   case AlignArg::_2:
 342     return Stream << "AlignArg::_2";
 343   case AlignArg::ARRAY_SIZE:
 344     report_fatal_error("logic error");
 345   }
 346 }
 347 static raw_ostream &operator<<(raw_ostream &Stream, const AlignedLoop &O) {
 348   return Stream << "AlignedLoop{" << O.Loop << ',' << O.Alignment << ','
 349                 << O.AlignTo << '}';
 350 }
 351 static raw_ostream &operator<<(raw_ostream &Stream, const Accelerator &O) {
 352   return Stream << "Accelerator{" << O.Span << '}';
 353 }
 354 static raw_ostream &operator<<(raw_ostream &Stream, const ElementTypeClass &O) {
 355   switch (O) {
 356   case ElementTypeClass::SCALAR:
 357     return Stream << "ElementTypeClass::SCALAR";
 358   case ElementTypeClass::BUILTIN:
 359     return Stream << "ElementTypeClass::BUILTIN";
 360   case ElementTypeClass::NATIVE:
 361     return Stream << "ElementTypeClass::NATIVE";
 362   }
 363 }
 364 static raw_ostream &operator<<(raw_ostream &Stream, const FunctionType &T) {
 365   switch (T) {
 366   case FunctionType::MEMCPY:
 367     return Stream << "FunctionType::MEMCPY";
 368   case FunctionType::MEMCMP:
 369     return Stream << "FunctionType::MEMCMP";
 370   case FunctionType::BCMP:
 371     return Stream << "FunctionType::BCMP";
 372   case FunctionType::MEMSET:
 373     return Stream << "FunctionType::MEMSET";
 374   case FunctionType::BZERO:
 375     return Stream << "FunctionType::BZERO";
 376   }
 377 }
 378 template <typename T>
 379 static raw_ostream &operator<<(raw_ostream &Stream,
 380                                const std::optional<T> &MaybeT) {
 381   if (MaybeT)
 382     return Stream << *MaybeT;
 383   return Stream << "std::nullopt";
 384 }
 385 static raw_ostream &operator<<(raw_ostream &Stream,
 386                                const FunctionDescriptor &FD) {
 387   return Stream << '{' << FD.Type << ',' << FD.Contiguous << ',' << FD.Overlap
 388                 << ',' << FD.Loop << ',' << FD.AlignedLoop << ','
 389                 << FD.Accelerator << ',' << FD.ElementClass << '}';
 390 }
 391 static raw_ostream &operator<<(raw_ostream &Stream,
 392                                const NamedFunctionDescriptor &NFD) {
 393   return Stream << '{' << '"' << NFD.Name << '"' << ',' << NFD.Desc << '}';
 394 }
 395 template <typename T>
 396 static raw_ostream &operator<<(raw_ostream &Stream,
 397                                const std::vector<T> &VectorT) {
 398   Stream << '{';
 399   bool First = true;
 400   for (const auto &Obj : VectorT) {
 401     if (!First)
 402       Stream << ',';
 403     Stream << Obj;
 404     First = false;
 405   }
 406   return Stream << '}';
 407 }
 408
 409 static void Serialize(raw_ostream &Stream,
 410                       ArrayRef<NamedFunctionDescriptor> Descriptors) {
 411   Stream << R"(ArrayRef<NamedFunctionDescriptor> getFunctionDescriptors() {
 412   static constexpr NamedFunctionDescriptor kDescriptors[] = {
 413 )";
 414   for (size_t I = 0, E = Descriptors.size(); I < E; ++I) {
 415     Stream << kIndent << kIndent << Descriptors[I] << ",\n";
 416   }
 417   Stream << R"(  };
 418   return ArrayRef(kDescriptors);
 419 }
 420 )";
 421 }
 422
 423 } // namespace descriptors
 424
 425 namespace configurations {
 426
 427 // This namespace generates the getXXXConfigurations functions:
 428 // ------------------------------------------------------------
 429 // e.g.
 430 // llvm::ArrayRef<MemcpyConfiguration> getMemcpyConfigurations() {
 431 //   using namespace __llvm_libc;
 432 //   static constexpr MemcpyConfiguration kConfigurations[] = {
 433 //     {Wrap<memcpy_0xE00E29EE73994E2B>, "memcpy_0xE00E29EE73994E2B"},
 434 //     {Wrap<memcpy_0x8661D80472487AB5>, "memcpy_0x8661D80472487AB5"},
 435 //     ...
 436 //   };
 437 //   return llvm::ArrayRef(kConfigurations);
 438 // }
 439
 440 // The `Wrap` template function is provided in the `Main` function below.
 441 // It is used to adapt the gnerated code to the prototype of the C function.
 442 // For instance, the generated code for a `memcpy` takes `char*` pointers and
 443 // returns nothing but the original C `memcpy` function take and returns `void*`
 444 // pointers.
 445
 446 struct FunctionName {
 447   FunctionType ForType;
 448 };
 449
 450 struct ReturnType {
 451   FunctionType ForType;
 452 };
 453
 454 struct Configuration {
 455   FunctionName Name;
 456   ReturnType Type;
 457   std::vector<const NamedFunctionDescriptor *> Descriptors;
 458 };
 459
 460 static raw_ostream &operator<<(raw_ostream &Stream, const FunctionName &FN) {
 461   switch (FN.ForType) {
 462   case FunctionType::MEMCPY:
 463     return Stream << "getMemcpyConfigurations";
 464   case FunctionType::MEMCMP:
 465     return Stream << "getMemcmpConfigurations";
 466   case FunctionType::BCMP:
 467     return Stream << "getBcmpConfigurations";
 468   case FunctionType::MEMSET:
 469     return Stream << "getMemsetConfigurations";
 470   case FunctionType::BZERO:
 471     return Stream << "getBzeroConfigurations";
 472   }
 473 }
 474
 475 static raw_ostream &operator<<(raw_ostream &Stream, const ReturnType &RT) {
 476   switch (RT.ForType) {
 477   case FunctionType::MEMCPY:
 478     return Stream << "MemcpyConfiguration";
 479   case FunctionType::MEMCMP:
 480   case FunctionType::BCMP:
 481     return Stream << "MemcmpOrBcmpConfiguration";
 482   case FunctionType::MEMSET:
 483     return Stream << "MemsetConfiguration";
 484   case FunctionType::BZERO:
 485     return Stream << "BzeroConfiguration";
 486   }
 487 }
 488
 489 static raw_ostream &operator<<(raw_ostream &Stream,
 490                                const NamedFunctionDescriptor *FD) {
 491   return Stream << formatv("{Wrap<{0}>, \"{0}\"}", FD->Name);
 492 }
 493
 494 static raw_ostream &
 495 operator<<(raw_ostream &Stream,
 496            const std::vector<const NamedFunctionDescriptor *> &Descriptors) {
 497   for (size_t I = 0, E = Descriptors.size(); I < E; ++I)
 498     Stream << kIndent << kIndent << Descriptors[I] << ",\n";
 499   return Stream;
 500 }
 501
 502 static raw_ostream &operator<<(raw_ostream &Stream, const Configuration &C) {
 503   Stream << "llvm::ArrayRef<" << C.Type << "> " << C.Name << "() {\n";
 504   if (C.Descriptors.empty())
 505     Stream << kIndent << "return {};\n";
 506   else {
 507     Stream << kIndent << "using namespace __llvm_libc;\n";
 508     Stream << kIndent << "static constexpr " << C.Type
 509            << " kConfigurations[] = {\n";
 510     Stream << C.Descriptors;
 511     Stream << kIndent << "};\n";
 512     Stream << kIndent << "return llvm::ArrayRef(kConfigurations);\n";
 513   }
 514   Stream << "}\n";
 515   return Stream;
 516 }
 517
 518 static void Serialize(raw_ostream &Stream, FunctionType FT,
 519                       ArrayRef<NamedFunctionDescriptor> Descriptors) {
 520   Configuration Conf;
 521   Conf.Name = {FT};
 522   Conf.Type = {FT};
 523   for (const auto &FD : Descriptors)
 524     if (FD.Desc.Type == FT)
 525       Conf.Descriptors.push_back(&FD);
 526   Stream << Conf;
 527 }
 528
 529 } // namespace configurations
 530 static void Serialize(raw_ostream &Stream,
 531                       ArrayRef<NamedFunctionDescriptor> Descriptors) {
 532   Stream << "// This file is auto-generated by libc/benchmarks/automemcpy.\n";
 533   Stream << "// Functions : " << Descriptors.size() << "\n";
 534   Stream << "\n";
 535   Stream << "#include \"LibcFunctionPrototypes.h\"\n";
 536   Stream << "#include \"automemcpy/FunctionDescriptor.h\"\n";
 537   Stream << "#include \"src/string/memory_utils/elements.h\"\n";
 538   Stream << "\n";
 539   Stream << "using llvm::libc_benchmarks::BzeroConfiguration;\n";
 540   Stream << "using llvm::libc_benchmarks::MemcmpOrBcmpConfiguration;\n";
 541   Stream << "using llvm::libc_benchmarks::MemcpyConfiguration;\n";
 542   Stream << "using llvm::libc_benchmarks::MemmoveConfiguration;\n";
 543   Stream << "using llvm::libc_benchmarks::MemsetConfiguration;\n";
 544   Stream << "\n";
 545   Stream << "namespace __llvm_libc {\n";
 546   Stream << "\n";
 547   codegen::functions::Serialize(Stream, Descriptors);
 548   Stream << "\n";
 549   Stream << "} // namespace __llvm_libc\n";
 550   Stream << "\n";
 551   Stream << "namespace llvm {\n";
 552   Stream << "namespace automemcpy {\n";
 553   Stream << "\n";
 554   codegen::descriptors::Serialize(Stream, Descriptors);
 555   Stream << "\n";
 556   Stream << "} // namespace automemcpy\n";
 557   Stream << "} // namespace llvm\n";
 558   Stream << "\n";
 559   Stream << R"(
 560 using MemcpyStub = void (*)(char *__restrict, const char *__restrict, size_t);
 561 template <MemcpyStub Foo>
 562 void *Wrap(void *__restrict dst, const void *__restrict src, size_t size) {
 563   Foo(reinterpret_cast<char *__restrict>(dst),
 564       reinterpret_cast<const char *__restrict>(src), size);
 565   return dst;
 566 }
 567 )";
 568   codegen::configurations::Serialize(Stream, FunctionType::MEMCPY, Descriptors);
 569   Stream << R"(
 570 using MemcmpStub = int (*)(const char *, const char *, size_t);
 571 template <MemcmpStub Foo>
 572 int Wrap(const void *lhs, const void *rhs, size_t size) {
 573   return Foo(reinterpret_cast<const char *>(lhs),
 574              reinterpret_cast<const char *>(rhs), size);
 575 }
 576 )";
 577   codegen::configurations::Serialize(Stream, FunctionType::MEMCMP, Descriptors);
 578   codegen::configurations::Serialize(Stream, FunctionType::BCMP, Descriptors);
 579   Stream << R"(
 580 using MemsetStub = void (*)(char *, int, size_t);
 581 template <MemsetStub Foo> void *Wrap(void *dst, int value, size_t size) {
 582   Foo(reinterpret_cast<char *>(dst), value, size);
 583   return dst;
 584 }
 585 )";
 586   codegen::configurations::Serialize(Stream, FunctionType::MEMSET, Descriptors);
 587   Stream << R"(
 588 using BzeroStub = void (*)(char *, size_t);
 589 template <BzeroStub Foo> void Wrap(void *dst, size_t size) {
 590   Foo(reinterpret_cast<char *>(dst), size);
 591 }
 592 )";
 593   codegen::configurations::Serialize(Stream, FunctionType::BZERO, Descriptors);
 594   Stream << R"(
 595 llvm::ArrayRef<MemmoveConfiguration> getMemmoveConfigurations() {
 596   return {};
 597 }
 598 )";
 599   Stream << "// Functions : " << Descriptors.size() << "\n";
 600 }
 601
 602 } // namespace codegen
 603
 604 // Stores `VolatileStr` into a cache and returns a StringRef of the cached
 605 // version.
 606 StringRef getInternalizedString(std::string VolatileStr) {
 607   static llvm::StringSet StringCache;
 608   return StringCache.insert(std::move(VolatileStr)).first->getKey();
 609 }
 610
 611 static StringRef getString(FunctionType FT) {
 612   switch (FT) {
 613   case FunctionType::MEMCPY:
 614     return "memcpy";
 615   case FunctionType::MEMCMP:
 616     return "memcmp";
 617   case FunctionType::BCMP:
 618     return "bcmp";
 619   case FunctionType::MEMSET:
 620     return "memset";
 621   case FunctionType::BZERO:
 622     return "bzero";
 623   }
 624 }
 625
 626 void Serialize(raw_ostream &Stream, ArrayRef<FunctionDescriptor> Descriptors) {
 627   std::vector<NamedFunctionDescriptor> FunctionDescriptors;
 628   FunctionDescriptors.reserve(Descriptors.size());
 629   for (auto &FD : Descriptors) {
 630     FunctionDescriptors.emplace_back();
 631     FunctionDescriptors.back().Name = getInternalizedString(
 632         formatv("{0}_{1:X16}", getString(FD.Type), FD.id()));
 633     FunctionDescriptors.back().Desc = std::move(FD);
 634   }
 635   // Sort functions so they are easier to spot in the generated C++ file.
 636   std::sort(FunctionDescriptors.begin(), FunctionDescriptors.end(),
 637             [](const NamedFunctionDescriptor &A,
 638                const NamedFunctionDescriptor &B) { return A.Desc < B.Desc; });
 639   codegen::Serialize(Stream, FunctionDescriptors);
 640 }
 641
 642 } // namespace automemcpy
 643 } // namespace llvm