utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

//===- ClangOpenCLBuiltinEmitter.cpp - Generate Clang OpenCL Builtin handling
//
//                     The LLVM Compiler Infrastructure
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// These backends consume the definitions of OpenCL builtin functions in
// clang/lib/Sema/OpenCLBuiltins.td and produce builtin handling code for
// inclusion in SemaLookup.cpp, or a test file that calls all declared builtins.
//
//===----------------------------------------------------------------------===//

#include "TableGenBackends.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/StringMatcher.h"
#include "llvm/TableGen/TableGenBackend.h"

using namespace llvm;

namespace {

// A list of signatures that are shared by one or more builtin functions.
struct BuiltinTableEntries {
  SmallVector<StringRef, 4> Names;
  std::vector<std::pair<const Record *, unsigned>> Signatures;
};

// This tablegen backend emits code for checking whether a function is an
// OpenCL builtin function. If so, all overloads of this function are
// added to the LookupResult. The generated include file is used by
// SemaLookup.cpp
//
// For a successful lookup of e.g. the "cos" builtin, isOpenCLBuiltin("cos")
// returns a pair <Index, Len>.
// BuiltinTable[Index] to BuiltinTable[Index + Len] contains the pairs
// <SigIndex, SigLen> of the overloads of "cos".
// SignatureTable[SigIndex] to SignatureTable[SigIndex + SigLen] contains
// one of the signatures of "cos". The SignatureTable entry can be
// referenced by other functions, e.g. "sin", to exploit the fact that
// many OpenCL builtins share the same signature.
//
// The file generated by this TableGen emitter contains the following:
//
//  * Structs and enums to represent types and function signatures.
//
//  * const char *FunctionExtensionTable[]
//    List of space-separated OpenCL extensions.  A builtin references an
//    entry in this table when the builtin requires a particular (set of)
//    extension(s) to be enabled.
//
//  * OpenCLTypeStruct TypeTable[]
//    Type information for return types and arguments.
//
//  * unsigned SignatureTable[]
//    A list of types representing function signatures.  Each entry is an index
//    into the above TypeTable.  Multiple entries following each other form a
//    signature, where the first entry is the return type and subsequent
//    entries are the argument types.
//
//  * OpenCLBuiltinStruct BuiltinTable[]
//    Each entry represents one overload of an OpenCL builtin function and
//    consists of an index into the SignatureTable and the number of arguments.
//
//  * std::pair<unsigned, unsigned> isOpenCLBuiltin(llvm::StringRef Name)
//    Find out whether a string matches an existing OpenCL builtin function
//    name and return an index into BuiltinTable and the number of overloads.
//
//  * void OCL2Qual(Sema&, OpenCLTypeStruct, std::vector<QualType>&)
//    Convert an OpenCLTypeStruct type to a list of QualType instances.
//    One OpenCLTypeStruct can represent multiple types, primarily when using
//    GenTypes.
//
class BuiltinNameEmitter {
public:
  BuiltinNameEmitter(RecordKeeper &Records, raw_ostream &OS)
      : Records(Records), OS(OS) {}

  // Entrypoint to generate the functions and structures for checking
  // whether a function is an OpenCL builtin function.
  void Emit();

private:
  // A list of indices into the builtin function table.
  using BuiltinIndexListTy = SmallVector<unsigned, 11>;

  // Contains OpenCL builtin functions and related information, stored as
  // Record instances. They are coming from the associated TableGen file.
  RecordKeeper &Records;

  // The output file.
  raw_ostream &OS;

  // Helper function for BuiltinNameEmitter::EmitDeclarations.  Generate enum
  // definitions in the Output string parameter, and save their Record instances
  // in the List parameter.
  // \param Types (in) List containing the Types to extract.
  // \param TypesSeen (inout) List containing the Types already extracted.
  // \param Output (out) String containing the enums to emit in the output file.
  // \param List (out) List containing the extracted Types, except the Types in
  //        TypesSeen.
  void ExtractEnumTypes(std::vector<Record *> &Types,
                        StringMap<bool> &TypesSeen, std::string &Output,
                        std::vector<const Record *> &List);

  // Emit the enum or struct used in the generated file.
  // Populate the TypeList at the same time.
  void EmitDeclarations();

  // Parse the Records generated by TableGen to populate the SignaturesList,
  // FctOverloadMap and TypeMap.
  void GetOverloads();

  // Compare two lists of signatures and check that e.g. the OpenCL version,
  // function attributes, and extension are equal for each signature.
  // \param Candidate (in) Entry in the SignatureListMap to check.
  // \param SignatureList (in) List of signatures of the considered function.
  // \returns true if the two lists of signatures are identical.
  bool CanReuseSignature(
      BuiltinIndexListTy *Candidate,
      std::vector<std::pair<const Record *, unsigned>> &SignatureList);

  // Group functions with the same list of signatures by populating the
  // SignatureListMap.
  // Some builtin functions have the same list of signatures, for example the
  // "sin" and "cos" functions. To save space in the BuiltinTable, the
  // "isOpenCLBuiltin" function will have the same output for these two
  // function names.
  void GroupBySignature();

  // Emit the FunctionExtensionTable that lists all function extensions.
  void EmitExtensionTable();

  // Emit the TypeTable containing all types used by OpenCL builtins.
  void EmitTypeTable();

  // Emit the SignatureTable. This table contains all the possible signatures.
  // A signature is stored as a list of indexes of the TypeTable.
  // The first index references the return type (mandatory), and the followings
  // reference its arguments.
  // E.g.:
  // 15, 2, 15 can represent a function with the signature:
  // int func(float, int)
  // The "int" type being at the index 15 in the TypeTable.
  void EmitSignatureTable();

  // Emit the BuiltinTable table. This table contains all the overloads of
  // each function, and is a struct OpenCLBuiltinDecl.
  // E.g.:
  // // 891 convert_float2_rtn
  //   { 58, 2, 3, 100, 0 },
  // This means that the signature of this convert_float2_rtn overload has
  // 1 argument (+1 for the return type), stored at index 58 in
  // the SignatureTable.  This prototype requires extension "3" in the
  // FunctionExtensionTable.  The last two values represent the minimum (1.0)
  // and maximum (0, meaning no max version) OpenCL version in which this
  // overload is supported.
  void EmitBuiltinTable();

  // Emit a StringMatcher function to check whether a function name is an
  // OpenCL builtin function name.
  void EmitStringMatcher();

  // Emit a function returning the clang QualType instance associated with
  // the TableGen Record Type.
  void EmitQualTypeFinder();

  // Contains a list of the available signatures, without the name of the
  // function. Each pair consists of a signature and a cumulative index.
  // E.g.:  <<float, float>, 0>,
  //        <<float, int, int, 2>>,
  //        <<float>, 5>,
  //        ...
  //        <<double, double>, 35>.
  std::vector<std::pair<std::vector<Record *>, unsigned>> SignaturesList;

  // Map the name of a builtin function to its prototypes (instances of the
  // TableGen "Builtin" class).
  // Each prototype is registered as a pair of:
  //   <pointer to the "Builtin" instance,
  //    cumulative index of the associated signature in the SignaturesList>
  // E.g.:  The function cos: (float cos(float), double cos(double), ...)
  //        <"cos", <<ptrToPrototype0, 5>,
  //                 <ptrToPrototype1, 35>,
  //                 <ptrToPrototype2, 79>>
  // ptrToPrototype1 has the following signature: <double, double>
  MapVector<StringRef, std::vector<std::pair<const Record *, unsigned>>>
      FctOverloadMap;

  // Contains the map of OpenCL types to their index in the TypeTable.
  MapVector<const Record *, unsigned> TypeMap;

  // List of OpenCL function extensions mapping extension strings to
  // an index into the FunctionExtensionTable.
  StringMap<unsigned> FunctionExtensionIndex;

  // List of OpenCL type names in the same order as in enum OpenCLTypeID.
  // This list does not contain generic types.
  std::vector<const Record *> TypeList;

  // Same as TypeList, but for generic types only.
  std::vector<const Record *> GenTypeList;

  // Map an ordered vector of signatures to their original Record instances,
  // and to a list of function names that share these signatures.
  //
  // For example, suppose the "cos" and "sin" functions have only three
  // signatures, and these signatures are at index Ix in the SignatureTable:
  //          cos         |         sin         |  Signature    | Index
  //  float   cos(float)  | float   sin(float)  |  Signature1   | I1
  //  double  cos(double) | double  sin(double) |  Signature2   | I2
  //  half    cos(half)   | half    sin(half)   |  Signature3   | I3
  //
  // Then we will create a mapping of the vector of signatures:
  // SignatureListMap[<I1, I2, I3>] = <
  //                  <"cos", "sin">,
  //                  <Signature1, Signature2, Signature3>>
  // The function "tan", having the same signatures, would be mapped to the
  // same entry (<I1, I2, I3>).
  MapVector<BuiltinIndexListTy *, BuiltinTableEntries> SignatureListMap;
};

/// Base class for emitting a file (e.g. header or test) from OpenCLBuiltins.td
class OpenCLBuiltinFileEmitterBase {
public:
  OpenCLBuiltinFileEmitterBase(RecordKeeper &Records, raw_ostream &OS)
      : Records(Records), OS(OS) {}
  virtual ~OpenCLBuiltinFileEmitterBase() = default;

  // Entrypoint to generate the functions for testing all OpenCL builtin
  // functions.
  virtual void emit() = 0;

protected:
  struct TypeFlags {
    TypeFlags() : IsConst(false), IsVolatile(false), IsPointer(false) {}
    bool IsConst : 1;
    bool IsVolatile : 1;
    bool IsPointer : 1;
    StringRef AddrSpace;
  };

  // Return a string representation of the given type, such that it can be
  // used as a type in OpenCL C code.
  std::string getTypeString(const Record *Type, TypeFlags Flags,
                            int VectorSize) const;

  // Return the type(s) and vector size(s) for the given type.  For
  // non-GenericTypes, the resulting vectors will contain 1 element.  For
  // GenericTypes, the resulting vectors typically contain multiple elements.
  void getTypeLists(Record *Type, TypeFlags &Flags,
                    std::vector<Record *> &TypeList,
                    std::vector<int64_t> &VectorList) const;

  // Expand the TableGen Records representing a builtin function signature into
  // one or more function signatures.  Return them as a vector of a vector of
  // strings, with each string containing an OpenCL C type and optional
  // qualifiers.
  //
  // The Records may contain GenericTypes, which expand into multiple
  // signatures.  Repeated occurrences of GenericType in a signature expand to
  // the same types.  For example [char, FGenType, FGenType] expands to:
  //   [char, float, float]
  //   [char, float2, float2]
  //   [char, float3, float3]
  //   ...
  void
  expandTypesInSignature(const std::vector<Record *> &Signature,
                         SmallVectorImpl<SmallVector<std::string, 2>> &Types);

  // Emit extension enabling pragmas.
  void emitExtensionSetup();

  // Emit an #if guard for a Builtin's extension.  Return the corresponding
  // closing #endif, or an empty string if no extension #if guard was emitted.
  std::string emitExtensionGuard(const Record *Builtin);

  // Emit an #if guard for a Builtin's language version.  Return the
  // corresponding closing #endif, or an empty string if no version #if guard
  // was emitted.
  std::string emitVersionGuard(const Record *Builtin);

  // Emit an #if guard for all type extensions required for the given type
  // strings.  Return the corresponding closing #endif, or an empty string
  // if no extension #if guard was emitted.
  StringRef
  emitTypeExtensionGuards(const SmallVectorImpl<std::string> &Signature);

  // Map type strings to type extensions (e.g. "half2" -> "cl_khr_fp16").
  StringMap<StringRef> TypeExtMap;

  // Contains OpenCL builtin functions and related information, stored as
  // Record instances. They are coming from the associated TableGen file.
  RecordKeeper &Records;

  // The output file.
  raw_ostream &OS;
};

// OpenCL builtin test generator.  This class processes the same TableGen input
// as BuiltinNameEmitter, but generates a .cl file that contains a call to each
// builtin function described in the .td input.
class OpenCLBuiltinTestEmitter : public OpenCLBuiltinFileEmitterBase {
public:
  OpenCLBuiltinTestEmitter(RecordKeeper &Records, raw_ostream &OS)
      : OpenCLBuiltinFileEmitterBase(Records, OS) {}

  // Entrypoint to generate the functions for testing all OpenCL builtin
  // functions.
  void emit() override;
};

} // namespace

void BuiltinNameEmitter::Emit() {
  emitSourceFileHeader("OpenCL Builtin handling", OS);

  OS << "#include \"llvm/ADT/StringRef.h\"\n";
  OS << "using namespace clang;\n\n";

  // Emit enums and structs.
  EmitDeclarations();

  // Parse the Records to populate the internal lists.
  GetOverloads();
  GroupBySignature();

  // Emit tables.
  EmitExtensionTable();
  EmitTypeTable();
  EmitSignatureTable();
  EmitBuiltinTable();

  // Emit functions.
  EmitStringMatcher();
  EmitQualTypeFinder();
}

void BuiltinNameEmitter::ExtractEnumTypes(std::vector<Record *> &Types,
                                          StringMap<bool> &TypesSeen,
                                          std::string &Output,
                                          std::vector<const Record *> &List) {
  raw_string_ostream SS(Output);

  for (const auto *T : Types) {
    if (TypesSeen.find(T->getValueAsString("Name")) == TypesSeen.end()) {
      SS << "  OCLT_" + T->getValueAsString("Name") << ",\n";
      // Save the type names in the same order as their enum value. Note that
      // the Record can be a VectorType or something else, only the name is
      // important.
      List.push_back(T);
      TypesSeen.insert(std::make_pair(T->getValueAsString("Name"), true));
    }
  }
  SS.flush();
}

void BuiltinNameEmitter::EmitDeclarations() {
  // Enum of scalar type names (float, int, ...) and generic type sets.
  OS << "enum OpenCLTypeID {\n";

  StringMap<bool> TypesSeen;
  std::string GenTypeEnums;
  std::string TypeEnums;

  // Extract generic types and non-generic types separately, to keep
  // gentypes at the end of the enum which simplifies the special handling
  // for gentypes in SemaLookup.
  std::vector<Record *> GenTypes =
      Records.getAllDerivedDefinitions("GenericType");
  ExtractEnumTypes(GenTypes, TypesSeen, GenTypeEnums, GenTypeList);

  std::vector<Record *> Types = Records.getAllDerivedDefinitions("Type");
  ExtractEnumTypes(Types, TypesSeen, TypeEnums, TypeList);

  OS << TypeEnums;
  OS << GenTypeEnums;
  OS << "};\n";

  // Structure definitions.
  OS << R"(
// Image access qualifier.
enum OpenCLAccessQual : unsigned char {
  OCLAQ_None,
  OCLAQ_ReadOnly,
  OCLAQ_WriteOnly,
  OCLAQ_ReadWrite
};

// Represents a return type or argument type.
struct OpenCLTypeStruct {
  // A type (e.g. float, int, ...).
  const OpenCLTypeID ID;
  // Vector size (if applicable; 0 for scalars and generic types).
  const unsigned VectorWidth;
  // 0 if the type is not a pointer.
  const bool IsPointer : 1;
  // 0 if the type is not const.
  const bool IsConst : 1;
  // 0 if the type is not volatile.
  const bool IsVolatile : 1;
  // Access qualifier.
  const OpenCLAccessQual AccessQualifier;
  // Address space of the pointer (if applicable).
  const LangAS AS;
};

// One overload of an OpenCL builtin function.
struct OpenCLBuiltinStruct {
  // Index of the signature in the OpenCLTypeStruct table.
  const unsigned SigTableIndex;
  // Entries between index SigTableIndex and (SigTableIndex + NumTypes - 1) in
  // the SignatureTable represent the complete signature.  The first type at
  // index SigTableIndex is the return type.
  const unsigned NumTypes;
  // Function attribute __attribute__((pure))
  const bool IsPure : 1;
  // Function attribute __attribute__((const))
  const bool IsConst : 1;
  // Function attribute __attribute__((convergent))
  const bool IsConv : 1;
  // OpenCL extension(s) required for this overload.
  const unsigned short Extension;
  // OpenCL versions in which this overload is available.
  const unsigned short Versions;
};

)";
}

// Verify that the combination of GenTypes in a signature is supported.
// To simplify the logic for creating overloads in SemaLookup, only allow
// a signature to contain different GenTypes if these GenTypes represent
// the same number of actual scalar or vector types.
//
// Exit with a fatal error if an unsupported construct is encountered.
static void VerifySignature(const std::vector<Record *> &Signature,
                            const Record *BuiltinRec) {
  unsigned GenTypeVecSizes = 1;
  unsigned GenTypeTypes = 1;

  for (const auto *T : Signature) {
    // Check all GenericType arguments in this signature.
    if (T->isSubClassOf("GenericType")) {
      // Check number of vector sizes.
      unsigned NVecSizes =
          T->getValueAsDef("VectorList")->getValueAsListOfInts("List").size();
      if (NVecSizes != GenTypeVecSizes && NVecSizes != 1) {
        if (GenTypeVecSizes > 1) {
          // We already saw a gentype with a different number of vector sizes.
          PrintFatalError(BuiltinRec->getLoc(),
              "number of vector sizes should be equal or 1 for all gentypes "
              "in a declaration");
        }
        GenTypeVecSizes = NVecSizes;
      }

      // Check number of data types.
      unsigned NTypes =
          T->getValueAsDef("TypeList")->getValueAsListOfDefs("List").size();
      if (NTypes != GenTypeTypes && NTypes != 1) {
        if (GenTypeTypes > 1) {
          // We already saw a gentype with a different number of types.
          PrintFatalError(BuiltinRec->getLoc(),
              "number of types should be equal or 1 for all gentypes "
              "in a declaration");
        }
        GenTypeTypes = NTypes;
      }
    }
  }
}

void BuiltinNameEmitter::GetOverloads() {
  // Populate the TypeMap.
  std::vector<Record *> Types = Records.getAllDerivedDefinitions("Type");
  unsigned I = 0;
  for (const auto &T : Types) {
    TypeMap.insert(std::make_pair(T, I++));
  }

  // Populate the SignaturesList and the FctOverloadMap.
  unsigned CumulativeSignIndex = 0;
  std::vector<Record *> Builtins = Records.getAllDerivedDefinitions("Builtin");
  for (const auto *B : Builtins) {
    StringRef BName = B->getValueAsString("Name");
    if (FctOverloadMap.find(BName) == FctOverloadMap.end()) {
      FctOverloadMap.insert(std::make_pair(
          BName, std::vector<std::pair<const Record *, unsigned>>{}));
    }

    auto Signature = B->getValueAsListOfDefs("Signature");
    // Reuse signatures to avoid unnecessary duplicates.
    auto it =
        llvm::find_if(SignaturesList,
                      [&](const std::pair<std::vector<Record *>, unsigned> &a) {
                        return a.first == Signature;
                      });
    unsigned SignIndex;
    if (it == SignaturesList.end()) {
      VerifySignature(Signature, B);
      SignaturesList.push_back(std::make_pair(Signature, CumulativeSignIndex));
      SignIndex = CumulativeSignIndex;
      CumulativeSignIndex += Signature.size();
    } else {
      SignIndex = it->second;
    }
    FctOverloadMap[BName].push_back(std::make_pair(B, SignIndex));
  }
}

void BuiltinNameEmitter::EmitExtensionTable() {
  OS << "static const char *FunctionExtensionTable[] = {\n";
  unsigned Index = 0;
  std::vector<Record *> FuncExtensions =
      Records.getAllDerivedDefinitions("FunctionExtension");

  for (const auto &FE : FuncExtensions) {
    // Emit OpenCL extension table entry.
    OS << "  // " << Index << ": " << FE->getName() << "\n"
       << "  \"" << FE->getValueAsString("ExtName") << "\",\n";

    // Record index of this extension.
    FunctionExtensionIndex[FE->getName()] = Index++;
  }
  OS << "};\n\n";
}

void BuiltinNameEmitter::EmitTypeTable() {
  OS << "static const OpenCLTypeStruct TypeTable[] = {\n";
  for (const auto &T : TypeMap) {
    const char *AccessQual =
        StringSwitch<const char *>(T.first->getValueAsString("AccessQualifier"))
            .Case("RO", "OCLAQ_ReadOnly")
            .Case("WO", "OCLAQ_WriteOnly")
            .Case("RW", "OCLAQ_ReadWrite")
            .Default("OCLAQ_None");

    OS << "  // " << T.second << "\n"
       << "  {OCLT_" << T.first->getValueAsString("Name") << ", "
       << T.first->getValueAsInt("VecWidth") << ", "
       << T.first->getValueAsBit("IsPointer") << ", "
       << T.first->getValueAsBit("IsConst") << ", "
       << T.first->getValueAsBit("IsVolatile") << ", "
       << AccessQual << ", "
       << T.first->getValueAsString("AddrSpace") << "},\n";
  }
  OS << "};\n\n";
}

void BuiltinNameEmitter::EmitSignatureTable() {
  // Store a type (e.g. int, float, int2, ...). The type is stored as an index
  // of a struct OpenCLType table. Multiple entries following each other form a
  // signature.
  OS << "static const unsigned short SignatureTable[] = {\n";
  for (const auto &P : SignaturesList) {
    OS << "  // " << P.second << "\n  ";
    for (const Record *R : P.first) {
      unsigned Entry = TypeMap.find(R)->second;
      if (Entry > USHRT_MAX) {
        // Report an error when seeing an entry that is too large for the
        // current index type (unsigned short).  When hitting this, the type
        // of SignatureTable will need to be changed.
        PrintFatalError("Entry in SignatureTable exceeds limit.");
      }
      OS << Entry << ", ";
    }
    OS << "\n";
  }
  OS << "};\n\n";
}

// Encode a range MinVersion..MaxVersion into a single bit mask that can be
// checked against LangOpts using isOpenCLVersionContainedInMask().
// This must be kept in sync with OpenCLVersionID in OpenCLOptions.h.
// (Including OpenCLOptions.h here would be a layering violation.)
static unsigned short EncodeVersions(unsigned int MinVersion,
                                     unsigned int MaxVersion) {
  unsigned short Encoded = 0;

  // A maximum version of 0 means available in all later versions.
  if (MaxVersion == 0) {
    MaxVersion = UINT_MAX;
  }

  unsigned VersionIDs[] = {100, 110, 120, 200, 300};
  for (unsigned I = 0; I < std::size(VersionIDs); I++) {
    if (VersionIDs[I] >= MinVersion && VersionIDs[I] < MaxVersion) {
      Encoded |= 1 << I;
    }
  }

  return Encoded;
}

void BuiltinNameEmitter::EmitBuiltinTable() {
  unsigned Index = 0;

  OS << "static const OpenCLBuiltinStruct BuiltinTable[] = {\n";
  for (const auto &SLM : SignatureListMap) {

    OS << "  // " << (Index + 1) << ": ";
    for (const auto &Name : SLM.second.Names) {
      OS << Name << ", ";
    }
    OS << "\n";

    for (const auto &Overload : SLM.second.Signatures) {
      StringRef ExtName = Overload.first->getValueAsDef("Extension")->getName();
      unsigned int MinVersion =
          Overload.first->getValueAsDef("MinVersion")->getValueAsInt("ID");
      unsigned int MaxVersion =
          Overload.first->getValueAsDef("MaxVersion")->getValueAsInt("ID");

      OS << "  { " << Overload.second << ", "
         << Overload.first->getValueAsListOfDefs("Signature").size() << ", "
         << (Overload.first->getValueAsBit("IsPure")) << ", "
         << (Overload.first->getValueAsBit("IsConst")) << ", "
         << (Overload.first->getValueAsBit("IsConv")) << ", "
         << FunctionExtensionIndex[ExtName] << ", "
         << EncodeVersions(MinVersion, MaxVersion) << " },\n";
      Index++;
    }
  }
  OS << "};\n\n";
}

bool BuiltinNameEmitter::CanReuseSignature(
    BuiltinIndexListTy *Candidate,
    std::vector<std::pair<const Record *, unsigned>> &SignatureList) {
  assert(Candidate->size() == SignatureList.size() &&
         "signature lists should have the same size");

  auto &CandidateSigs =
      SignatureListMap.find(Candidate)->second.Signatures;
  for (unsigned Index = 0; Index < Candidate->size(); Index++) {
    const Record *Rec = SignatureList[Index].first;
    const Record *Rec2 = CandidateSigs[Index].first;
    if (Rec->getValueAsBit("IsPure") == Rec2->getValueAsBit("IsPure") &&
        Rec->getValueAsBit("IsConst") == Rec2->getValueAsBit("IsConst") &&
        Rec->getValueAsBit("IsConv") == Rec2->getValueAsBit("IsConv") &&
        Rec->getValueAsDef("MinVersion")->getValueAsInt("ID") ==
            Rec2->getValueAsDef("MinVersion")->getValueAsInt("ID") &&
        Rec->getValueAsDef("MaxVersion")->getValueAsInt("ID") ==
            Rec2->getValueAsDef("MaxVersion")->getValueAsInt("ID") &&
        Rec->getValueAsDef("Extension")->getName() ==
            Rec2->getValueAsDef("Extension")->getName()) {
      return true;
    }
  }
  return false;
}

void BuiltinNameEmitter::GroupBySignature() {
  // List of signatures known to be emitted.
  std::vector<BuiltinIndexListTy *> KnownSignatures;

  for (auto &Fct : FctOverloadMap) {
    bool FoundReusableSig = false;

    // Gather all signatures for the current function.
    auto *CurSignatureList = new BuiltinIndexListTy();
    for (const auto &Signature : Fct.second) {
      CurSignatureList->push_back(Signature.second);
    }
    // Sort the list to facilitate future comparisons.
    llvm::sort(*CurSignatureList);

    // Check if we have already seen another function with the same list of
    // signatures.  If so, just add the name of the function.
    for (auto *Candidate : KnownSignatures) {
      if (Candidate->size() == CurSignatureList->size() &&
          *Candidate == *CurSignatureList) {
        if (CanReuseSignature(Candidate, Fct.second)) {
          SignatureListMap.find(Candidate)->second.Names.push_back(Fct.first);
          FoundReusableSig = true;
        }
      }
    }

    if (FoundReusableSig) {
      delete CurSignatureList;
    } else {
      // Add a new entry.
      SignatureListMap[CurSignatureList] = {
          SmallVector<StringRef, 4>(1, Fct.first), Fct.second};
      KnownSignatures.push_back(CurSignatureList);
    }
  }

  for (auto *I : KnownSignatures) {
    delete I;
  }
}

void BuiltinNameEmitter::EmitStringMatcher() {
  std::vector<StringMatcher::StringPair> ValidBuiltins;
  unsigned CumulativeIndex = 1;

  for (const auto &SLM : SignatureListMap) {
    const auto &Ovl = SLM.second.Signatures;

    // A single signature list may be used by different builtins.  Return the
    // same <index, length> pair for each of those builtins.
    for (const auto &FctName : SLM.second.Names) {
      std::string RetStmt;
      raw_string_ostream SS(RetStmt);
      SS << "return std::make_pair(" << CumulativeIndex << ", " << Ovl.size()
         << ");";
      SS.flush();
      ValidBuiltins.push_back(
          StringMatcher::StringPair(std::string(FctName), RetStmt));
    }
    CumulativeIndex += Ovl.size();
  }

  OS << R"(
// Find out whether a string matches an existing OpenCL builtin function name.
// Returns: A pair <0, 0> if no name matches.
//          A pair <Index, Len> indexing the BuiltinTable if the name is
//          matching an OpenCL builtin function.
static std::pair<unsigned, unsigned> isOpenCLBuiltin(llvm::StringRef Name) {

)";

  StringMatcher("Name", ValidBuiltins, OS).Emit(0, true);

  OS << "  return std::make_pair(0, 0);\n";
  OS << "} // isOpenCLBuiltin\n";
}

// Emit an if-statement with an isMacroDefined call for each extension in
// the space-separated list of extensions.
static void EmitMacroChecks(raw_ostream &OS, StringRef Extensions) {
  SmallVector<StringRef, 2> ExtVec;
  Extensions.split(ExtVec, " ");
  OS << "      if (";
  for (StringRef Ext : ExtVec) {
    if (Ext != ExtVec.front())
      OS << " && ";
    OS << "S.getPreprocessor().isMacroDefined(\"" << Ext << "\")";
  }
  OS << ") {\n  ";
}

void BuiltinNameEmitter::EmitQualTypeFinder() {
  OS << R"(

static QualType getOpenCLEnumType(Sema &S, llvm::StringRef Name);
static QualType getOpenCLTypedefType(Sema &S, llvm::StringRef Name);

// Convert an OpenCLTypeStruct type to a list of QualTypes.
// Generic types represent multiple types and vector sizes, thus a vector
// is returned. The conversion is done in two steps:
// Step 1: A switch statement fills a vector with scalar base types for the
//         Cartesian product of (vector sizes) x (types) for generic types,
//         or a single scalar type for non generic types.
// Step 2: Qualifiers and other type properties such as vector size are
//         applied.
static void OCL2Qual(Sema &S, const OpenCLTypeStruct &Ty,
                     llvm::SmallVectorImpl<QualType> &QT) {
  ASTContext &Context = S.Context;
  // Number of scalar types in the GenType.
  unsigned GenTypeNumTypes;
  // Pointer to the list of vector sizes for the GenType.
  llvm::ArrayRef<unsigned> GenVectorSizes;
)";

  // Generate list of vector sizes for each generic type.
  for (const auto *VectList : Records.getAllDerivedDefinitions("IntList")) {
    OS << "  constexpr unsigned List"
       << VectList->getValueAsString("Name") << "[] = {";
    for (const auto V : VectList->getValueAsListOfInts("List")) {
      OS << V << ", ";
    }
    OS << "};\n";
  }

  // Step 1.
  // Start of switch statement over all types.
  OS << "\n  switch (Ty.ID) {\n";

  // Switch cases for image types (Image2d, Image3d, ...)
  std::vector<Record *> ImageTypes =
      Records.getAllDerivedDefinitions("ImageType");

  // Map an image type name to its 3 access-qualified types (RO, WO, RW).
  StringMap<SmallVector<Record *, 3>> ImageTypesMap;
  for (auto *IT : ImageTypes) {
    auto Entry = ImageTypesMap.find(IT->getValueAsString("Name"));
    if (Entry == ImageTypesMap.end()) {
      SmallVector<Record *, 3> ImageList;
      ImageList.push_back(IT);
      ImageTypesMap.insert(
          std::make_pair(IT->getValueAsString("Name"), ImageList));
    } else {
      Entry->second.push_back(IT);
    }
  }

  // Emit the cases for the image types.  For an image type name, there are 3
  // corresponding QualTypes ("RO", "WO", "RW").  The "AccessQualifier" field
  // tells which one is needed.  Emit a switch statement that puts the
  // corresponding QualType into "QT".
  for (const auto &ITE : ImageTypesMap) {
    OS << "    case OCLT_" << ITE.getKey() << ":\n"
       << "      switch (Ty.AccessQualifier) {\n"
       << "        case OCLAQ_None:\n"
       << "          llvm_unreachable(\"Image without access qualifier\");\n";
    for (const auto &Image : ITE.getValue()) {
      StringRef Exts =
          Image->getValueAsDef("Extension")->getValueAsString("ExtName");
      OS << StringSwitch<const char *>(
                Image->getValueAsString("AccessQualifier"))
                .Case("RO", "        case OCLAQ_ReadOnly:\n")
                .Case("WO", "        case OCLAQ_WriteOnly:\n")
                .Case("RW", "        case OCLAQ_ReadWrite:\n");
      if (!Exts.empty()) {
        OS << "    ";
        EmitMacroChecks(OS, Exts);
      }
      OS << "          QT.push_back("
         << Image->getValueAsDef("QTExpr")->getValueAsString("TypeExpr")
         << ");\n";
      if (!Exts.empty()) {
        OS << "          }\n";
      }
      OS << "          break;\n";
    }
    OS << "      }\n"
       << "      break;\n";
  }

  // Switch cases for generic types.
  for (const auto *GenType : Records.getAllDerivedDefinitions("GenericType")) {
    OS << "    case OCLT_" << GenType->getValueAsString("Name") << ": {\n";

    // Build the Cartesian product of (vector sizes) x (types).  Only insert
    // the plain scalar types for now; other type information such as vector
    // size and type qualifiers will be added after the switch statement.
    std::vector<Record *> BaseTypes =
        GenType->getValueAsDef("TypeList")->getValueAsListOfDefs("List");

    // Collect all QualTypes for a single vector size into TypeList.
    OS << "      SmallVector<QualType, " << BaseTypes.size() << "> TypeList;\n";
    for (const auto *T : BaseTypes) {
      StringRef Exts =
          T->getValueAsDef("Extension")->getValueAsString("ExtName");
      if (!Exts.empty()) {
        EmitMacroChecks(OS, Exts);
      }
      OS << "      TypeList.push_back("
         << T->getValueAsDef("QTExpr")->getValueAsString("TypeExpr") << ");\n";
      if (!Exts.empty()) {
        OS << "      }\n";
      }
    }
    OS << "      GenTypeNumTypes = TypeList.size();\n";

    // Duplicate the TypeList for every vector size.
    std::vector<int64_t> VectorList =
        GenType->getValueAsDef("VectorList")->getValueAsListOfInts("List");
    OS << "      QT.reserve(" << VectorList.size() * BaseTypes.size() << ");\n"
       << "      for (unsigned I = 0; I < " << VectorList.size() << "; I++) {\n"
       << "        QT.append(TypeList);\n"
       << "      }\n";

    // GenVectorSizes is the list of vector sizes for this GenType.
    OS << "      GenVectorSizes = List"
       << GenType->getValueAsDef("VectorList")->getValueAsString("Name")
       << ";\n"
       << "      break;\n"
       << "    }\n";
  }

  // Switch cases for non generic, non image types (int, int4, float, ...).
  // Only insert the plain scalar type; vector information and type qualifiers
  // are added in step 2.
  std::vector<Record *> Types = Records.getAllDerivedDefinitions("Type");
  StringMap<bool> TypesSeen;

  for (const auto *T : Types) {
    // Check this is not an image type
    if (ImageTypesMap.find(T->getValueAsString("Name")) != ImageTypesMap.end())
      continue;
    // Check we have not seen this Type
    if (TypesSeen.find(T->getValueAsString("Name")) != TypesSeen.end())
      continue;
    TypesSeen.insert(std::make_pair(T->getValueAsString("Name"), true));

    // Check the Type does not have an "abstract" QualType
    auto QT = T->getValueAsDef("QTExpr");
    if (QT->getValueAsBit("IsAbstract") == 1)
      continue;
    // Emit the cases for non generic, non image types.
    OS << "    case OCLT_" << T->getValueAsString("Name") << ":\n";

    StringRef Exts = T->getValueAsDef("Extension")->getValueAsString("ExtName");
    // If this type depends on an extension, ensure the extension macros are
    // defined.
    if (!Exts.empty()) {
      EmitMacroChecks(OS, Exts);
    }
    OS << "      QT.push_back(" << QT->getValueAsString("TypeExpr") << ");\n";
    if (!Exts.empty()) {
      OS << "      }\n";
    }
    OS << "      break;\n";
  }

  // End of switch statement.
  OS << "  } // end of switch (Ty.ID)\n\n";

  // Step 2.
  // Add ExtVector types if this was a generic type, as the switch statement
  // above only populated the list with scalar types.  This completes the
  // construction of the Cartesian product of (vector sizes) x (types).
  OS << "  // Construct the different vector types for each generic type.\n";
  OS << "  if (Ty.ID >= " << TypeList.size() << ") {";
  OS << R"(
    for (unsigned I = 0; I < QT.size(); I++) {
      // For scalars, size is 1.
      if (GenVectorSizes[I / GenTypeNumTypes] != 1) {
        QT[I] = Context.getExtVectorType(QT[I],
                          GenVectorSizes[I / GenTypeNumTypes]);
      }
    }
  }
)";

  // Assign the right attributes to the types (e.g. vector size).
  OS << R"(
  // Set vector size for non-generic vector types.
  if (Ty.VectorWidth > 1) {
    for (unsigned Index = 0; Index < QT.size(); Index++) {
      QT[Index] = Context.getExtVectorType(QT[Index], Ty.VectorWidth);
    }
  }

  if (Ty.IsVolatile != 0) {
    for (unsigned Index = 0; Index < QT.size(); Index++) {
      QT[Index] = Context.getVolatileType(QT[Index]);
    }
  }

  if (Ty.IsConst != 0) {
    for (unsigned Index = 0; Index < QT.size(); Index++) {
      QT[Index] = Context.getConstType(QT[Index]);
    }
  }

  // Transform the type to a pointer as the last step, if necessary.
  // Builtin functions only have pointers on [const|volatile], no
  // [const|volatile] pointers, so this is ok to do it as a last step.
  if (Ty.IsPointer != 0) {
    for (unsigned Index = 0; Index < QT.size(); Index++) {
      QT[Index] = Context.getAddrSpaceQualType(QT[Index], Ty.AS);
      QT[Index] = Context.getPointerType(QT[Index]);
    }
  }
)";

  // End of the "OCL2Qual" function.
  OS << "\n} // OCL2Qual\n";
}

std::string OpenCLBuiltinFileEmitterBase::getTypeString(const Record *Type,
                                                        TypeFlags Flags,
                                                        int VectorSize) const {
  std::string S;
  if (Type->getValueAsBit("IsConst") || Flags.IsConst) {
    S += "const ";
  }
  if (Type->getValueAsBit("IsVolatile") || Flags.IsVolatile) {
    S += "volatile ";
  }

  auto PrintAddrSpace = [&S](StringRef AddrSpace) {
    S += StringSwitch<const char *>(AddrSpace)
             .Case("clang::LangAS::opencl_private", "__private")
             .Case("clang::LangAS::opencl_global", "__global")
             .Case("clang::LangAS::opencl_constant", "__constant")
             .Case("clang::LangAS::opencl_local", "__local")
             .Case("clang::LangAS::opencl_generic", "__generic")
             .Default("__private");
    S += " ";
  };
  if (Flags.IsPointer) {
    PrintAddrSpace(Flags.AddrSpace);
  } else if (Type->getValueAsBit("IsPointer")) {
    PrintAddrSpace(Type->getValueAsString("AddrSpace"));
  }

  StringRef Acc = Type->getValueAsString("AccessQualifier");
  if (Acc != "") {
    S += StringSwitch<const char *>(Acc)
             .Case("RO", "__read_only ")
             .Case("WO", "__write_only ")
             .Case("RW", "__read_write ");
  }

  S += Type->getValueAsString("Name").str();
  if (VectorSize > 1) {
    S += std::to_string(VectorSize);
  }

  if (Type->getValueAsBit("IsPointer") || Flags.IsPointer) {
    S += " *";
  }

  return S;
}

void OpenCLBuiltinFileEmitterBase::getTypeLists(
    Record *Type, TypeFlags &Flags, std::vector<Record *> &TypeList,
    std::vector<int64_t> &VectorList) const {
  bool isGenType = Type->isSubClassOf("GenericType");
  if (isGenType) {
    TypeList = Type->getValueAsDef("TypeList")->getValueAsListOfDefs("List");
    VectorList =
        Type->getValueAsDef("VectorList")->getValueAsListOfInts("List");
    return;
  }

  if (Type->isSubClassOf("PointerType") || Type->isSubClassOf("ConstType") ||
      Type->isSubClassOf("VolatileType")) {
    StringRef SubTypeName = Type->getValueAsString("Name");
    Record *PossibleGenType = Records.getDef(SubTypeName);
    if (PossibleGenType && PossibleGenType->isSubClassOf("GenericType")) {
      // When PointerType, ConstType, or VolatileType is applied to a
      // GenericType, the flags need to be taken from the subtype, not from the
      // GenericType.
      Flags.IsPointer = Type->getValueAsBit("IsPointer");
      Flags.IsConst = Type->getValueAsBit("IsConst");
      Flags.IsVolatile = Type->getValueAsBit("IsVolatile");
      Flags.AddrSpace = Type->getValueAsString("AddrSpace");
      getTypeLists(PossibleGenType, Flags, TypeList, VectorList);
      return;
    }
  }

  // Not a GenericType, so just insert the single type.
  TypeList.push_back(Type);
  VectorList.push_back(Type->getValueAsInt("VecWidth"));
}

void OpenCLBuiltinFileEmitterBase::expandTypesInSignature(
    const std::vector<Record *> &Signature,
    SmallVectorImpl<SmallVector<std::string, 2>> &Types) {
  // Find out if there are any GenTypes in this signature, and if so, calculate
  // into how many signatures they will expand.
  unsigned NumSignatures = 1;
  SmallVector<SmallVector<std::string, 4>, 4> ExpandedGenTypes;
  for (const auto &Arg : Signature) {
    SmallVector<std::string, 4> ExpandedArg;
    std::vector<Record *> TypeList;
    std::vector<int64_t> VectorList;
    TypeFlags Flags;

    getTypeLists(Arg, Flags, TypeList, VectorList);

    // Insert the Cartesian product of the types and vector sizes.
    for (const auto &Vector : VectorList) {
      for (const auto &Type : TypeList) {
        std::string FullType = getTypeString(Type, Flags, Vector);
        ExpandedArg.push_back(FullType);

        // If the type requires an extension, add a TypeExtMap entry mapping
        // the full type name to the extension.
        StringRef Ext =
            Type->getValueAsDef("Extension")->getValueAsString("ExtName");
        if (!Ext.empty() && TypeExtMap.find(FullType) == TypeExtMap.end()) {
          TypeExtMap.insert({FullType, Ext});
        }
      }
    }
    NumSignatures = std::max<unsigned>(NumSignatures, ExpandedArg.size());
    ExpandedGenTypes.push_back(ExpandedArg);
  }

  // Now the total number of signatures is known.  Populate the return list with
  // all signatures.
  for (unsigned I = 0; I < NumSignatures; I++) {
    SmallVector<std::string, 2> Args;

    // Process a single signature.
    for (unsigned ArgNum = 0; ArgNum < Signature.size(); ArgNum++) {
      // For differently-sized GenTypes in a parameter list, the smaller
      // GenTypes just repeat, so index modulo the number of expanded types.
      size_t TypeIndex = I % ExpandedGenTypes[ArgNum].size();
      Args.push_back(ExpandedGenTypes[ArgNum][TypeIndex]);
    }
    Types.push_back(Args);
  }
}

void OpenCLBuiltinFileEmitterBase::emitExtensionSetup() {
  OS << R"(
#pragma OPENCL EXTENSION cl_khr_fp16 : enable
#pragma OPENCL EXTENSION cl_khr_fp64 : enable
#pragma OPENCL EXTENSION cl_khr_int64_base_atomics : enable
#pragma OPENCL EXTENSION cl_khr_int64_extended_atomics : enable
#pragma OPENCL EXTENSION cl_khr_gl_msaa_sharing : enable
#pragma OPENCL EXTENSION cl_khr_mipmap_image_writes : enable
#pragma OPENCL EXTENSION cl_khr_3d_image_writes : enable

)";
}

std::string
OpenCLBuiltinFileEmitterBase::emitExtensionGuard(const Record *Builtin) {
  StringRef Extensions =
      Builtin->getValueAsDef("Extension")->getValueAsString("ExtName");
  if (Extensions.empty())
    return "";

  OS << "#if";

  SmallVector<StringRef, 2> ExtVec;
  Extensions.split(ExtVec, " ");
  bool isFirst = true;
  for (StringRef Ext : ExtVec) {
    if (!isFirst) {
      OS << " &&";
    }
    OS << " defined(" << Ext << ")";
    isFirst = false;
  }
  OS << "\n";

  return "#endif // Extension\n";
}

std::string
OpenCLBuiltinFileEmitterBase::emitVersionGuard(const Record *Builtin) {
  std::string OptionalEndif;
  auto PrintOpenCLVersion = [this](int Version) {
    OS << "CL_VERSION_" << (Version / 100) << "_" << ((Version % 100) / 10);
  };
  int MinVersion = Builtin->getValueAsDef("MinVersion")->getValueAsInt("ID");
  if (MinVersion != 100) {
    // OpenCL 1.0 is the default minimum version.
    OS << "#if __OPENCL_C_VERSION__ >= ";
    PrintOpenCLVersion(MinVersion);
    OS << "\n";
    OptionalEndif = "#endif // MinVersion\n" + OptionalEndif;
  }
  int MaxVersion = Builtin->getValueAsDef("MaxVersion")->getValueAsInt("ID");
  if (MaxVersion) {
    OS << "#if __OPENCL_C_VERSION__ < ";
    PrintOpenCLVersion(MaxVersion);
    OS << "\n";
    OptionalEndif = "#endif // MaxVersion\n" + OptionalEndif;
  }
  return OptionalEndif;
}

StringRef OpenCLBuiltinFileEmitterBase::emitTypeExtensionGuards(
    const SmallVectorImpl<std::string> &Signature) {
  SmallSet<StringRef, 2> ExtSet;

  // Iterate over all types to gather the set of required TypeExtensions.
  for (const auto &Ty : Signature) {
    StringRef TypeExt = TypeExtMap.lookup(Ty);
    if (!TypeExt.empty()) {
      // The TypeExtensions are space-separated in the .td file.
      SmallVector<StringRef, 2> ExtVec;
      TypeExt.split(ExtVec, " ");
      for (const auto Ext : ExtVec) {
        ExtSet.insert(Ext);
      }
    }
  }

  // Emit the #if only when at least one extension is required.
  if (ExtSet.empty())
    return "";

  OS << "#if ";
  bool isFirst = true;
  for (const auto Ext : ExtSet) {
    if (!isFirst)
      OS << " && ";
    OS << "defined(" << Ext << ")";
    isFirst = false;
  }
  OS << "\n";
  return "#endif // TypeExtension\n";
}

void OpenCLBuiltinTestEmitter::emit() {
  emitSourceFileHeader("OpenCL Builtin exhaustive testing", OS);

  emitExtensionSetup();

  // Ensure each test has a unique name by numbering them.
  unsigned TestID = 0;

  // Iterate over all builtins.
  std::vector<Record *> Builtins = Records.getAllDerivedDefinitions("Builtin");
  for (const auto *B : Builtins) {
    StringRef Name = B->getValueAsString("Name");

    SmallVector<SmallVector<std::string, 2>, 4> FTypes;
    expandTypesInSignature(B->getValueAsListOfDefs("Signature"), FTypes);

    OS << "// Test " << Name << "\n";

    std::string OptionalExtensionEndif = emitExtensionGuard(B);
    std::string OptionalVersionEndif = emitVersionGuard(B);

    for (const auto &Signature : FTypes) {
      StringRef OptionalTypeExtEndif = emitTypeExtensionGuards(Signature);

      // Emit function declaration.
      OS << Signature[0] << " test" << TestID++ << "_" << Name << "(";
      if (Signature.size() > 1) {
        for (unsigned I = 1; I < Signature.size(); I++) {
          if (I != 1)
            OS << ", ";
          OS << Signature[I] << " arg" << I;
        }
      }
      OS << ") {\n";

      // Emit function body.
      OS << "  ";
      if (Signature[0] != "void") {
        OS << "return ";
      }
      OS << Name << "(";
      for (unsigned I = 1; I < Signature.size(); I++) {
        if (I != 1)
          OS << ", ";
        OS << "arg" << I;
      }
      OS << ");\n";

      // End of function body.
      OS << "}\n";
      OS << OptionalTypeExtEndif;
    }

    OS << OptionalVersionEndif;
    OS << OptionalExtensionEndif;
  }
}

void clang::EmitClangOpenCLBuiltins(RecordKeeper &Records, raw_ostream &OS) {
  BuiltinNameEmitter NameChecker(Records, OS);
  NameChecker.Emit();
}

void clang::EmitClangOpenCLBuiltinTests(RecordKeeper &Records,
                                        raw_ostream &OS) {
  OpenCLBuiltinTestEmitter TestFileGenerator(Records, OS);
  TestFileGenerator.emit();
}