[flang] Add constant time mapping from enumeration to string in ENUM_CLASS macro

[Renaud-K]

Summary

The utility function EnumIndexToString that is used to extract a substring from the enumeration list at a position given by the integral value of the enumeration is linear time.
This change adds an NAME_struct structure that holds an array used for constant time mapping of enumerations to strings and a one time utility function BuildIndexToString use to built it.

[klausler]

If EnumToString() is a bottleneck for you, you should look into changing its result type to a string reference rather than a string copy first. That extra overhead may be dominating your performance, not a O(n) algorithm.

Second, memoizing that function would best be done once in the function, not once at each call site. What you have here will build a distinct look-up table for every c++ source file that uses a particular ENUM_CLASS.

If ENUM_CLASS is used in the Fortran runtime support library, please don't use C++ library code like regex to implement the memoization. We don't want compiled Fortran applications to have a needless dependency on any C++ runtime library.

[Renaud-K]

This pattern is based on the Meyers singleton. There is only one instance of the lookup table.
It was not possible in the past to return a reference to string since the string was computed on the fly. It did not seem to bother anyone so I did not change that.
Though this would be possible now. I gave it a quick try and I am only getting a few compilation errors. So, I can look into these and add to these changes.
I could also use good ol' strtok if regex is going to be a problem.

[Renaud-K]

1. Returning a reference to string since string are now held permanently in memory
2. Adding #include<array>
3. No changes in idioms.cpp because it turns out that it is not used by the runtime and could never have been since it returned strings by value

[Renaud-K]

Applying clang-format

[Renaud-K]

Peter has resigned from the review. He says, all his concerns have been addressed but he would like someone else to approve the change.

To re-iterate on the concerns:

1. The table is unique, initialized once on the first call and shared among all translation unit. It is a C++ guaranty for local static variables. It is also the basis for the Meyers singleton.
2. idioms.cpp already has dependencies with the C++ runtime, so we leave it as a non-runtime file
3. We can now return references to string. We debated that we could even return const char * however all functions taking an ENUM_CLASS string expect a const std::string &. So they would all have to change otherwise an implicit temporary is created for the conversion from const char * to const std::string & which would defeat the purpose.
4. The use of const char * would mostly help in making the table more compact though thanks to the short string optimization (SSO) and array<string> is essentially an array<char[32]> for strings less than 16 characters. I did not find enumerations greater than 15 characters so none of strings will be relying on dynamic allocations. Therefore the table is already fairly compact with all strings contained within it as opposed to pointing to some heap allocated storage.

Let me know if would like to see this optimized even further.

[jeanPerier]

Is this really implementing Meyer's singleton ? I am not very familiar with Meyer's singleton, but from what I understood I thought its thread safety lied in the fact the singleton initialization was in the ctor of a static variable with block scope, and that C++11 guarantees that this ctor will be called only once and that no other thread may access it before the end of initialization. But here, it looks like the initialization is done in a manual lazy init fashion in EnumToString, and I do not get how this is thread safe.

An alternative would be to make this data structure constexpr static data. This would looks safer and more optimal to me, but this may as well be over-engineering, may have drawbacks I do not foresee, and I think you would have to use const char* or std::string_view as a return since std::string ctor will only be constexpr in C++20.

The thread safety part is in my opinion critical if EnumToString is ever used in some MLIR pass that may be multithreaded. Otherwise, I do not have a strong opinion on the matter. Lowering does not heavily rely on ENUM_CLASS, so I do not have a strong opinion on the impact. But I would be ready to approve this change (provided thread safety is indeed guaranteed) if you think this is an improvement.

[Renaud-K]

No, it is not Meyers singleton. It uses the same C++ guarantee that is the basis for the Meyers singleton.
It is is not thread safe. I only intended for the table to be unique. If we need thread safety then maybe a constexpr table is best.

[Renaud-K]

Moving the table initialization into a Meyers singleton.

[jeanPerier]

Thanks for addressing my concerns.

flang/include/flang/Common/enum-set.h

template <typename FUNC> void IterateOverMembers(const FUNC &f) const {
     EnumSet copy{*this};
     while (auto least{copy.LeastElement()}) {
       f(*least);
       copy.erase(*least);
     }
   }
 
   template <typename STREAM>
-  STREAM &Dump(STREAM &o, std::string EnumToString(enumerationType)) const {
+  STREAM &Dump(
+      STREAM &o, const std::string &EnumToString(enumerationType)) const {
     char sep{'{'};
     IterateOverMembers([&](auto e) {
       o << sep << EnumToString(e);
       sep = ',';
     });
     return o << (sep == '{' ? "{}" : "}");
   }
 

flang/include/flang/Common/idioms.h

 #if __cplusplus < 201703L
 #error this is a C++17 program
 #endif
 #if !__clang__ && defined __GNUC__ && __GNUC__ < 7
 #error g++ >= 7.2 is required
 #endif
 
 #include "visit.h"
+#include <array>
 #include <functional>
 #include <list>
 #include <memory>
 #include <optional>
 #include <string>
 #include <tuple>
 #include <type_traits>
 #include <variant>
template <typename A> constexpr bool trait_value() { \
         return U::value; \
       } else { \
         return false; \
       } \
     } \
   } \
   template <typename A> constexpr bool T{class_trait_ns_##T::trait_value<A>()};
 
-// Define enum class NAME with the given enumerators, a static
-// function EnumToString() that maps enumerators to std::string,
-// and a constant NAME_enumSize that captures the number of items
-// in the enum class.
+// Define enum class NAME with the given enumerators,
+// - a static function EnumToString() that maps enumerators to std::string,
+// - a constant NAME_enumSize that captures the number of items in the enum,
+// - a struct NAME_struct that implements a Meyers singleton to hold the mapping
+// from index to names
 
-std::string EnumIndexToString(int index, const char *names);
+void BuildIndexToString(
+    const char *commaSeparated, std::string enumNames[], int enumSize);
 
 template <typename A> struct ListItemCount {
   constexpr ListItemCount(std::initializer_list<A> list) : value{list.size()} {}
   const std::size_t value;
 };
 
 #define ENUM_CLASS(NAME, ...) \
   enum class NAME { __VA_ARGS__ }; \
   [[maybe_unused]] static constexpr std::size_t NAME##_enumSize{[] { \
     enum { __VA_ARGS__ }; \
     return Fortran::common::ListItemCount{__VA_ARGS__}.value; \
   }()}; \
-  [[maybe_unused]] static inline std::string EnumToString(NAME e) { \
-    return Fortran::common::EnumIndexToString( \
-        static_cast<int>(e), #__VA_ARGS__); \
+  struct NAME##_struct { \
+    NAME##_struct(const NAME##_struct &) = delete; \
+    NAME##_struct &operator=(const NAME##_struct &) = delete; \
+    static NAME##_struct &instance() { \
+      static NAME##_struct s; \
+      return s; \
+    } \
+    std::array<std::string, NAME##_enumSize> _enumNames; \
+\
+  private: \
+    NAME##_struct() { \
+      Fortran::common::BuildIndexToString( \
+          #__VA_ARGS__, _enumNames.data(), NAME##_enumSize); \
+    } \
+    ~NAME##_struct() {} \
+  }; \
+  [[maybe_unused]] static inline const std::string &EnumToString(NAME e) { \
+    return NAME##_struct::instance()._enumNames[static_cast<int>(e)]; \
   }
 
 // Check that a pointer is non-null and dereference it
 #define DEREF(p) Fortran::common::Deref(p, __FILE__, __LINE__)
 
 template <typename T> constexpr T &Deref(T *p, const char *file, int line) {
   if (!p) {
     Fortran::common::die("nullptr dereference at %s(%d)", file, line);

flang/lib/Common/idioms.cpp

 //===-- lib/Common/idioms.cpp ---------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "flang/Common/idioms.h"
 #include <cstdarg>
 #include <cstdio>
 #include <cstdlib>
+#include <regex>
 
 namespace Fortran::common {
 
 [[noreturn]] void die(const char *msg, ...) {
   va_list ap;
   va_start(ap, msg);
   std::fputs("\nfatal internal error: ", stderr);
   std::vfprintf(stderr, msg, ap);
   va_end(ap);
   fputc('\n', stderr);
   std::abort();
 }
 
-// Convert the int index of an enumerator to a string.
-// enumNames is a list of the names, separated by commas with optional spaces.
-// This is intended for use from the expansion of ENUM_CLASS.
-std::string EnumIndexToString(int index, const char *enumNames) {
-  const char *p{enumNames};
-  for (; index > 0; --index, ++p) {
-    for (; *p && *p != ','; ++p) {
-    }
-  }
-  for (; *p == ' '; ++p) {
-  }
-  CHECK(*p != '\0');
-  const char *q = p;
-  for (; *q && *q != ' ' && *q != ','; ++q) {
+// Converts the comma separated list of enumerators into tokens which are then
+// stored into the provided array of strings. This is intended for use from the
+// expansion of ENUM_CLASS.
+void BuildIndexToString(
+    const char *commaSeparated, std::string enumNames[], int enumSize) {
+  std::string input(commaSeparated);
+  std::regex reg("\\s*,\\s*");
+
+  std::sregex_token_iterator iter(input.begin(), input.end(), reg, -1);
+  std::sregex_token_iterator end;
+  int index = 0;
+  while (iter != end) {
+    enumNames[index] = *iter;
+    iter++;
+    index++;
   }
-  return std::string(p, q - p);
+  CHECK(index == enumSize);
 }
 } // namespace Fortran::common