[llvm][StringExtras] Use a lookup table for `hexDigitValue`

[rriddle]

Summary

This method is at the core of the conversion from hex to binary, and using a lookup table great improves the compile time of hex conversions.

Context: In MLIR we use hex strings to represent very large constants in the textual format of the IR. These changes lead to a large decrease in compile time when parsing these constants (>1 second -> 350 miliseconds).

Depends On D90265

[dblaikie]

If you like you could try rephrasing this as a programmatic initialization rather than writing it all out manually, might make it easier to read/look more like the original code (except applied as a loop over the range/table) and hopefully can be phrased in such a way that the compiler boils it down to the same values anyway.

llvm/include/llvm/ADT/StringExtras.h

70

const?

[dexonsmith]

LGTM, thanks for splitting this out.

llvm/include/llvm/ADT/StringExtras.h

72

I wonder if this would feel more ordered / be easier to read if each line of -1U was a (possibly incomplete) group of 8.

• 0-47 would have 6 groups of 8;
• 58-64 would have a group of 7;
• 71-96 would have a group of 1, three groups of 8, and a group of 1;
• 103-255 would have a group of 1, and 19 groups of 8.

I chose 8 because 16 will be too long for 80-column.

If you try it out and it looks worse, then what you have now is probably best.

[dexonsmith]

In D90320#2359587, @dblaikie wrote:

If you like you could try rephrasing this as a programmatic initialization rather than writing it all out manually, might make it easier to read/look more like the original code (except applied as a loop over the range/table) and hopefully can be phrased in such a way that the compiler boils it down to the same values anyway.

Hmmm, yeah, that's better than my idea.

[rriddle]

Reformat LUT.

[rriddle]

Rebase

[rriddle]

In D90320#2359587, @dblaikie wrote:

If you like you could try rephrasing this as a programmatic initialization rather than writing it all out manually, might make it easier to read/look more like the original code (except applied as a loop over the range/table) and hopefully can be phrased in such a way that the compiler boils it down to the same values anyway.

Thanks for the suggestion! That would definitely be much nicer. I tried about 4-5 different ways of doing the initialization and I could only get clang to generate a proper LUT in C++17(using constexpr lambda initialization with std::array), not C++14. I couldn't get GCC to do the right thing in either C++14 or C++17. Do you have any suggestions on how to do the initialization?

[rriddle]

Simplify LUT

[rriddle]

In D90320#2359805, @rriddle wrote:

In D90320#2359587, @dblaikie wrote:

If you like you could try rephrasing this as a programmatic initialization rather than writing it all out manually, might make it easier to read/look more like the original code (except applied as a loop over the range/table) and hopefully can be phrased in such a way that the compiler boils it down to the same values anyway.

Thanks for the suggestion! That would definitely be much nicer. I tried about 4-5 different ways of doing the initialization and I could only get clang to generate a proper LUT in C++17(using constexpr lambda initialization with std::array), not C++14. I couldn't get GCC to do the right thing in either C++14 or C++17. Do you have any suggestions on how to do the initialization?

NVM, found something that works.

[dblaikie]

Nice!

I guess in C++20 we could change this to something like:

constexpr std::array<int, 3> a = [] {
    std::array<int, 3> r;
    int i = 0;
    for (auto &v : r) {
        v = ++i;
    }
    return r;
}();

But based on godbolt testing at least, std::array's ctor isn't constexpr until 20. Oh well.

llvm/include/llvm/ADT/StringExtras.h

inline ArrayRef<uint8_t> arrayRefFromStringRef(StringRef Input) {
   return {Input.bytes_begin(), Input.bytes_end()};
 }
 
 /// Interpret the given character \p C as a hexadecimal digit and return its
 /// value.
 ///
 /// If \p C is not a valid hex digit, -1U is returned.
 inline unsigned hexDigitValue(char C) {
-  if (C >= '0' && C <= '9') return C-'0';
-  if (C >= 'a' && C <= 'f') return C-'a'+10U;
-  if (C >= 'A' && C <= 'F') return C-'A'+10U;
-  return -1U;
+  struct HexTable {
+    unsigned LUT[255] = {};
+    constexpr HexTable() {
+      // Default initialize everything to invalid.
+      for (int i = 0; i < 255; ++i)
+        LUT[i] = -1U;
+      // Initialize `0`-`9`.
+      for (int i = 0; i < 10; ++i)
+        LUT['0' + i] = i;
+      // Initialize `A`-`F` and `a`-`f`.
+      for (int i = 0; i < 6; ++i)
+        LUT['A' + i] = LUT['a' + i] = 10 + i;
+    }
+  };
+  constexpr HexTable Table;
+  return Table.LUT[static_cast<unsigned char>(C)];
 }
 
 /// Checks if character \p C is one of the 10 decimal digits.
 inline bool isDigit(char C) { return C >= '0' && C <= '9'; }
 
 /// Checks if character \p C is a hexadecimal numeric character.
 inline bool isHexDigit(char C) { return hexDigitValue(C) != -1U; }