[OpenCL] Group builtin functions by prototype

[svenvh]

Summary

The file generated from the tablegen file, and containing the
function definitions can be re-organised to save some memory.
Functions having the same prototypes will point to a common
list of prototypes.
Functions having only one prototype will point to a prototype
definition of another function.

This depends on:
-1, splitting opencl-c.h file: https://reviews.llvm.org/D63256/new/
-2, Adding generic types: https://reviews.llvm.org/D63434
-3, Adding const, volatile and pointer types: https://reviews.llvm.org/D63442
-4, Adding image types: https://reviews.llvm.org/D63480
-5, Adding version handling: https://reviews.llvm.org/D63504

[Anastasia]

Functions having only one prototype will point to a prototype
definition of another function.

Do you mean functions having only one prototype will point to a prototype
definition of another function with the same prototype?

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

129

This optimization generally seems reasobale. Do you have any idea how it affects the build time to generate the Tablegen file and how much space do we actually save?

199

It is not clear whether signatures for functions that don't share the prototype with any others should still be in this table?

219

This data stricture is really difficult to understand, do you think you could split it into multiple type aliases?

489

I think you need to either simplify or document what (SignatureListMap.find(Candidate)->second.first)[Index].first expression returns.

513

where is this being deallocated?

526

same problem as before... expression is too complex!

535

The same here... where do we release the memory?

[svenvh]

• Improve variable names & comments.
• Fix memory leaks.
• Rebase on top of recent master, and move before https://reviews.llvm.org/D63555 as the generated code on master is growing in size; with this patch we save about 100kb in the binary.
• Restucture SignatureListMap to make it easier to understand.

[svenvh]

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

129

It doesn't affect build time in a noticable way. With this patch, clang-tblgen -gen-clang-opencl-builtins runs in less than half a second.

We save about 100kb now. The savings will increase when we add more OpenCL builtins to the .td file.

199

All signatures will go into this table. Some might be shared, some not.

219

Done.

489

Broken up (and readability benefits from the SignatureListMap restructuring too).

513

At lines 535 and 545 now.

526

Better now?

535

You were referring to a new expression here, which is now gone.

[Anastasia]

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

199

I am confused where does the saving come from. We are currently adding an extra data structure without removing any other. So do we then reduce number of entries in SignaturesList?

200

This sentence is a bit hard to understand. I am also still confused what BuiltinIndexListTy represents.

557

frame?

[svenvh]

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

199

When generating the tables, this patch will make EmitBuiltinTable iterate over the entries in SignatureListMap instead of FctOverloadMap. SignatureListMap essentially contains the same information as FctOverloadMap, but it results in fewer table entries as we group builtins with the same signatures together.

200

Would it help if it was rephrased as follows?

Map an ordered vector of signatures to their original TableGen Record instances, and to a list of function names that share these signatures.

557

"frame" here means an index into the BuiltinTable and the number of BuiltinTable entries, which together compose a list of signatures. This is the pair being returned by the StringMatcher when a name is successfully matched.

Frankly speaking the comment is a bit confusing, will rephrase as:
// A single signature list may be used by different builtins. Return the same <index, length> pair for each of those builtins.

[Anastasia]

LGTM! Feel free to change comments on the final commit! Thanks!

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

200

Yes, it is much more readable! Thank you!

557

Perfect! Thanks!

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/StringMatcher.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <set>
 
 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;
+};
+
 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
private:
   // 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 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.:
private:
   MapVector<const Record *, unsigned> TypeMap;
 
   // 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 the definitions of the same list
+  // of signatures, and to a list of function names that have this list of
+  // 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;
 };
 } // 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();
 
   GetOverloads();
+  GroupBySignature();
 
   // Emit tables.
   EmitTypeTable();
   EmitSignatureTable();
   EmitBuiltinTable();
 
   EmitStringMatcher();
 
void BuiltinNameEmitter::EmitSignatureTable() {
   }
   OS << "};\n\n";
 }
 
 void BuiltinNameEmitter::EmitBuiltinTable() {
   unsigned Index = 0;
 
   OS << "static const OpenCLBuiltinStruct BuiltinTable[] = {\n";
-  for (const auto &FOM : FctOverloadMap) {
+  for (const auto &SLM : SignatureListMap) {
 
-    OS << "  // " << (Index + 1) << ": " << FOM.first << "\n";
+    OS << "  // " << (Index + 1) << ": ";
+    for (const auto &Name : SLM.second.Names) {
+      OS << Name << ", ";
+    }
+    OS << "\n";
 
-    for (const auto &Overload : FOM.second) {
+    for (const auto &Overload : SLM.second.Signatures) {
       OS << "  { " << Overload.second << ", "
          << Overload.first->getValueAsListOfDefs("Signature").size() << ", "
          << (Overload.first->getValueAsBit("IsPure")) << ", "
          << (Overload.first->getValueAsBit("IsConst")) << ", "
          << (Overload.first->getValueAsBit("IsConv")) << ", "
          << Overload.first->getValueAsDef("MinVersion")->getValueAsInt("ID")
          << ", "
          << Overload.first->getValueAsDef("MaxVersion")->getValueAsInt("ID")
          << " },\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->getValueAsString("Extension") ==
+            Rec2->getValueAsString("Extension")) {
+      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.
+    std::sort(CurSignatureList->begin(), CurSignatureList->end());
+
+    // 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 (auto &i : FctOverloadMap) {
-    auto &Ov = i.second;
+
+  for (const auto &SLM : SignatureListMap) {
+    const auto &Ovl = SLM.second.Signatures;
+
+    // Function names with the same list of signatures have to reference the
+    // same frame in the BuiltinTable.
+    for (const auto &FctName : SLM.second.Names) {
       std::string RetStmt;
       raw_string_ostream SS(RetStmt);
-    SS << "return std::make_pair(" << CumulativeIndex << ", " << Ov.size()
+      SS << "return std::make_pair(" << CumulativeIndex << ", " << Ovl.size()
          << ");";
       SS.flush();
-    CumulativeIndex += Ov.size();
-
-    ValidBuiltins.push_back(StringMatcher::StringPair(i.first, RetStmt));
+      ValidBuiltins.push_back(StringMatcher::StringPair(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) {