[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

94

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?

202

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

222

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

521

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

545

where is this being deallocated?

558

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

567

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

94

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.

202

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

222

Done.

521

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

545

At lines 535 and 545 now.

558

Better now?

567

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

[Anastasia]

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

201

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

202

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?

584

frame?

[svenvh]

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

201

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.

202

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.

584

"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

201

Yes, it is much more readable! Thank you!

584

Perfect! Thanks!

clang/utils/TableGen/ClangOpenCLBuiltinEmitter.cpp

private:
   // Emit the enum or struct used in the file generated
   // Populate the TypeExtensionList and FctExtensionList at the same time.
   void EmitDeclarations();
 
   // Parse the Records generated by TableGen to populate the SignaturesList,
   // FctOverloadMap and TypeMap.
   void GetOverloads();
 
+  // Helper function for BuiltinNameEmitter::GroupFctBySignature.
+  // When comparing two lists of signatures, checks OpenCL versions and
+  // function extension are equal for each signature.
+  // \param Candidate (in) The entry in the SignatureListMap to check
+  //
+  // \param SignatureList (in) The list of signatures of the considered function.
+  //
+  // \returns true if the two lists of signatures are identic
+  bool CheckSignature(SmallVector<unsigned, 11>* Candidate,
+        std::vector<std::pair<const Record *, unsigned>> &SignatureList);
+
+  // Some builtin functions have the same list of signatures. For instance, the
+  // "sin" and "cos" functions. To save space in the BuiltinTable, the
+  // "isOpenCLBuiltin" function will have the same output for these two
+  // function name.
+  // This function groups functions with the same list of signatures by
+  // populating the SignatureListMap.
+  void GroupFctBySignature();
+
   // Emit the FctExtensionTable and the TypeExtensionTable.
   // FctExtensionTable maps enums OpenCLFctExtensionID to their extension.
   // TypeExtensionTable maps OpenCLTypeID enums (not being generic types) to
   // their extension.
   // GenTypeExtensionTable maps OpenCLTypeID enums (generic type indexes) to
   // their extension.
   void EmitExtensionTable();
 
private:
   // int func(float, int)
   // The "int" type being at the index 12 in the TypeTable.
   void EmitSignatureTable();
 
   // Emit the BuiltinTable table. This table contains all the overloads of
   // each function.
   // E.g.:
   // // acos
-  //   { 2, 0, "", 100 },
-  // This means that the signature of this acos overload has 1 argument (+1 for
-  // the return type), stored at index 0 in the OpenCLSignature table.
+  //   { 1, 0, "", 100 },
+  // This means that the signature of acos, defined in OpenCL version 1.0 and
+  // not belonging to any extension, has a signature with 0 argument (only one
+  // return type), and is stored at index 0 in the SignatureTable.
   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.
private:
   // Generic types are not part of this list.
   // E.g.: <Type<name="half", TypeExtension="cl_khr_fp16">,
   //       <VectorType<name="double", TypeExtension="cl_khr_fp64">,
   //       ...>
   std::vector<const Record *> TypeExtensionList;
 
   // Same as TypeExtensionList, but for generic types only.
   std::vector<const Record *> GenTypeExtensionList;
+
+  // 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.
+  // E.g.:
+  // If the "cos" and "sin" functions had only three signatures. These
+  // signatures being at the 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 signature:
+  // SignatureListMap(<I1, I2, I3>) =
+  //     <<<Signature1, I1>,
+  //       <Signature2, I2>,
+  //       <Signature3, I3>>,
+  //       <"cos", "sin">>
+  // The function "tan", having the same signatures, would be inserted at the
+  // same entry (<I1, I2, I3>).
+  MapVector<SmallVector<unsigned, 11>*,
+            std::pair<std::vector<std::pair<const Record *, unsigned>>,
+                      std::vector<StringRef>*>> SignatureListMap;
 };
 } // namespace
 
 void BuiltinNameEmitter::Emit() {
   emitSourceFileHeader("OpenCL Builtin handling", OS);
 
   OS << "#include \"llvm/ADT/StringRef.h\"\n";
   OS << "using namespace clang;\n\n";
 
   // Emit the enum and struct
   EmitDeclarations();
 
   // Parse the Records to populate the internal lists
   GetOverloads();
+  GroupFctBySignature();
 
   // Emit data strucures
   EmitExtensionTable();
   EmitTypeTable();
   EmitSignatureTable();
   EmitBuiltinTable();
 
   // Emit functions
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 << " " << FOM.first << "\n";
+    OS << "// " << Index << " ";
+    for (const auto &Name : *(SLM.second.second)) {
+      OS << Name << ", ";
+    }
+    OS << "\n";
 
-    for (const auto &Overload : FOM.second) {
+    for (const auto &Overload : SLM.second.first) {
       OS << "  { "
          << Overload.second << ", "
          << Overload.first->getValueAsListOfDefs("Signature").size() << ", "
          << "OCLE_" << Overload.first->getValueAsDef("Extension")->getValueAsString("ID") << ", "
          << Overload.first->getValueAsDef("MinVersion")->getValueAsInt("Name") << ", "
          << Overload.first->getValueAsDef("MaxVersion")->getValueAsInt("Name")
          << " },\n";
          Index++;
     }
   }
   OS << "};\n\n";
 }
 
 
+bool BuiltinNameEmitter::CheckSignature(
+      SmallVector<unsigned, 11>* Candidate,
+      std::vector<std::pair<const Record *, unsigned>> &SignatureList) {
+  // The two lists have the same list of signatures, but there are other
+  // fields to check
+  const Record *Rec, *Rec2;
+  for (unsigned Index = 0; Index < Candidate->size(); Index++) {
+    Rec   = SignatureList[Index].first;
+    Rec2  = (SignatureListMap.find(Candidate)->second.first)[Index].first;
+    if (Rec->getValueAsDef("MinVersion")->getValueAsInt("Name") ==
+        Rec2->getValueAsDef("MinVersion")->getValueAsInt("Name") &&
+        Rec->getValueAsDef("MaxVersion")->getValueAsInt("Name") ==
+        Rec2->getValueAsDef("MaxVersion")->getValueAsInt("Name") &&
+        Rec->getValueAsDef("Extension")->getValueAsString("ID") ==
+        Rec2->getValueAsDef("Extension")->getValueAsString("ID")) {
+        return true;
+    }
+  }
+  return false;
+}
+
+
+void BuiltinNameEmitter::GroupFctBySignature() {
+  // Available lists of signatures
+  std::vector<SmallVector<unsigned, 11>*> SignatureListPool;
+  bool FoundSimilar = false;
+
+  for (auto &Fct : FctOverloadMap) {
+    FoundSimilar = false;
+
+    // Gather all the signatures for the current function
+    SmallVector<unsigned, 11> *CurSignatureList =
+        new SmallVector<unsigned, 11>();
+    for (const auto &Signature : Fct.second) {
+      CurSignatureList->push_back(Signature.second);
+    }
+    // Order the list to facilitate the future comparisons
+    std::sort(CurSignatureList->begin(), CurSignatureList->end());
+
+    // Check if another function has the same list of signatures
+    // If yes, we just need to add the name of the function
+    for (auto *Candidate : SignatureListPool) {
+      if (Candidate->size() == CurSignatureList->size()) {
+        if (*Candidate == *CurSignatureList) {
+          if (CheckSignature(Candidate, Fct.second)) {
+            SignatureListMap.find(Candidate)->second.second->push_back(Fct.first);
+            FoundSimilar = true;
+          }
+        }
+      }
+    }
+
+    // else, add a new entry
+    if (!FoundSimilar) {
+      std::vector<StringRef> *NewStringList = new std::vector<StringRef>();
+      NewStringList->push_back(Fct.first);
+      SignatureListMap[CurSignatureList] =
+          std::make_pair(Fct.second, NewStringList);
+      SignatureListPool.push_back(CurSignatureList);
+    }
+  }
+}
+
+
 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.first;
+
+    // Function names with the same list of signatures have the reference the
+    // same frame in the BuiltinTable.
+    for (const auto &FctName : *(SLM.second.second)) {
       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"(
 
 // Return 0 if name is not a recognized OpenCL builtin, or an index
 // into a table of declarations if it is an OpenCL builtin.
 std::pair<unsigned, unsigned> isOpenCLBuiltin(llvm::StringRef name) {
 
 )";