[Perf] Simplify llvm::StringSwitch and improve incremental rebuild by 54%

[davezarzycki]

Summary

Simplify llvm::StringSwitch and improve incremental rebuild performance by 54% on dual Xeon 8168 machines.

[jordan_rose]

include/llvm/ADT/StringSwitch.h

49

This makes it impossible to return a move-only type by reference (although I suppose you can still do it by pointer).

73–75

Until StringRef gets a known-size constructor I don't think we should do this, even if it's not kicking in in most cases. It's also serving another purpose right now, which is to make sure the argument strings are compile-time constants. I can see that it would generate tons of duplicate code this way, though.

(StringRef has long been overdo for a constexpr known-size constructor anyway.)

[davezarzycki]

include/llvm/ADT/StringSwitch.h

49

Doug signed of on this in a separate and simpler review.

73–75

strlen() is effectively constexpr (I just verified this in a test file). Unless there is something nontrivial I'm missing about StringRef that would prevent strlen() from being compile away, there should be no difference in code output.

[davezarzycki]

include/llvm/ADT/StringSwitch.h

73–75

Oh, I also tried adding a known size constructor to StringRef and that blew up spectacularly. Too much code likes to create large fixed size char arrays, fill in the first few bytes, and then call StringRef(array) and trust that strlen() finds the NUL byte.

[craig.topper]

include/llvm/ADT/StringSwitch.h

73–75

There's a subclass of StringRef called StringLiteral that has a fixed size constructor. Can that be used here?

[davezarzycki]

include/llvm/ADT/StringSwitch.h

73–75

Neat-o. I spent hours yesterday trying to figure out if a mix of type traits and template magic could detect string literals inside of StringRef, but I didn't think of just subclassing StringRef and I forgot that __builtin_strlen() existed. That should work.

[jordan_rose]

include/llvm/ADT/StringSwitch.h

73–75

Oh, whoa, I didn't know that existed. Thanks, Craig! (Now to go use it in some places in Swift…)

[davezarzycki]

Switched to StringLiteral and verified that the performance gain still exists.

[davezarzycki]

Fixed Google unit test.

[davezarzycki]

I can separate out the macro system if people want it to have separate review.

[davezarzycki]

Sorry for the STRING_SWITCH proposal/noise. I was working on that in parallel with the templated version fixes. Now that I'm comparing the code gen of the two, I'm impressed with the optimizer generating essentially the STRING_SWITCH code gen. I'll keep the macro version in my back pocket in case I find a scenario where the optimizer fails to optimize the templated version code gen.

[jordan_rose]

include/llvm/ADT/StringRef.h

875

I don't think this should be marked a hack. Sometimes people want to make StringRefs containing nul bytes. It's reasonable that it's explicit now, though.

[davezarzycki]

Drop the 'HACK' comment from the diff.

[davezarzycki]

I think this final diff addresses all concerns, including some amount of move-only type compatibility (it compiles, but I'm not sure the experience is pleasurable).

Jordan -- Chris recently gave me commit-after-approval access. Might you please approve this? Thanks!

[jordan_rose]

Go for it!

[davezarzycki]

LLVM: r326109
clang: r326110

include/llvm/ADT/StringRef.h

namespace llvm {
   /// A wrapper around a string literal that serves as a proxy for constructing
   /// global tables of StringRefs with the length computed at compile time.
   /// In order to avoid the invocation of a global constructor, StringLiteral
   /// should *only* be used in a constexpr context, as such:
   ///
   /// constexpr StringLiteral S("test");
   ///
   class StringLiteral : public StringRef {
+  private:
+    constexpr StringLiteral(const char *Str, size_t N) : StringRef(Str, N) {
+    }
+
   public:
     template <size_t N>
     constexpr StringLiteral(const char (&Str)[N])
 #if defined(__clang__) && __has_attribute(enable_if)
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wgcc-compat"
         __attribute((enable_if(__builtin_strlen(Str) == N - 1,
                                "invalid string literal")))
 #pragma clang diagnostic pop
 #endif
         : StringRef(Str, N - 1) {
     }
+
+    // Explicit construction for strings like "foo\0bar".
+    template <size_t N>
+    static constexpr StringLiteral withInnerNUL(const char (&Str)[N]) {
+      return StringLiteral(Str, N - 1);
+    }
   };
 
   /// @name StringRef Comparison Operators
   /// @{
 
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   inline bool operator==(StringRef LHS, StringRef RHS) {
     return LHS.equals(RHS);

include/llvm/ADT/StringSwitch.h

 ///   .Case("blue", Blue)
 ///   .Case("indigo", Indigo)
 ///   .Cases("violet", "purple", Violet)
 ///   .Default(UnknownColor);
 /// \endcode
 template<typename T, typename R = T>
 class StringSwitch {
   /// \brief The string we are matching.
-  StringRef Str;
+  const StringRef Str;
 
   /// \brief The pointer to the result of this switch statement, once known,
   /// null before that.
-  const T *Result;
+  Optional<T> Result;
 
 public:
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   explicit StringSwitch(StringRef S)
-  : Str(S), Result(nullptr) { }
+  : Str(S), Result() { }
 
   // StringSwitch is not copyable.
   StringSwitch(const StringSwitch &) = delete;
   void operator=(const StringSwitch &) = delete;
 
   StringSwitch(StringSwitch &&other) {
     *this = std::move(other);
   }
   StringSwitch &operator=(StringSwitch &&other) {
-    Str = other.Str;
-    Result = other.Result;
+    Str = std::move(other.Str);
+    Result = std::move(other.Result);
     return *this;
   }
 
   ~StringSwitch() = default;
 
   // Case-sensitive case matchers
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& Case(const char (&S)[N], const T& Value) {
-    assert(N);
-    if (!Result && N-1 == Str.size() &&
-        (N == 1 || std::memcmp(S, Str.data(), N-1) == 0)) {
-      Result = &Value;
+  StringSwitch &Case(StringLiteral S, T Value) {
+    if (!Result && Str == S) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& EndsWith(const char (&S)[N], const T &Value) {
-    assert(N);
-    if (!Result && Str.size() >= N-1 &&
-        (N == 1 || std::memcmp(S, Str.data() + Str.size() + 1 - N, N-1) == 0)) {
-      Result = &Value;
+  StringSwitch& EndsWith(StringLiteral S, T Value) {
+    if (!Result && Str.endswith(S)) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& StartsWith(const char (&S)[N], const T &Value) {
-    assert(N);
-    if (!Result && Str.size() >= N-1 &&
-        (N == 1 || std::memcmp(S, Str.data(), N-1) == 0)) {
-      Result = &Value;
+  StringSwitch& StartsWith(StringLiteral S, T Value) {
+    if (!Result && Str.startswith(S)) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N0, unsigned N1>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, T Value) {
     return Case(S0, Value).Case(S1, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2, unsigned N3>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7, unsigned N8>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const char (&S8)[N8], const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, StringLiteral S8,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, S8, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7, unsigned N8, unsigned N9>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const char (&S8)[N8], const char (&S9)[N9],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, StringLiteral S8,
+                      StringLiteral S9, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, S8, S9, Value);
   }
 
   // Case-insensitive case matchers.
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &CaseLower(const char (&S)[N],
-                                                       const T &Value) {
-    if (!Result && Str.equals_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CaseLower(StringLiteral S, T Value) {
+    if (!Result && Str.equals_lower(S))
+      Result = std::move(Value);
 
     return *this;
   }
 
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &EndsWithLower(const char (&S)[N],
-                                                           const T &Value) {
-    if (!Result && Str.endswith_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &EndsWithLower(StringLiteral S, T Value) {
+    if (!Result && Str.endswith_lower(S))
+      Result = Value;
 
     return *this;
   }
 
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &StartsWithLower(const char (&S)[N],
-                                                             const T &Value) {
-    if (!Result && Str.startswith_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &StartsWithLower(StringLiteral S, T Value) {
+    if (!Result && Str.startswith_lower(S))
+      Result = std::move(Value);
 
     return *this;
   }
-  template <unsigned N0, unsigned N1>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const T &Value) {
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, T Value) {
     return CaseLower(S0, Value).CaseLower(S1, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const char (&S3)[N3], const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           StringLiteral S3, T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, S3, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const char (&S3)[N3], const char (&S4)[N4], const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           StringLiteral S3, StringLiteral S4, T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, S3, S4, Value);
   }
 
+  LLVM_NODISCARD
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  R Default(const T &Value) const {
+  R Default(T Value) {
     if (Result)
-      return *Result;
+      return std::move(*Result);
     return Value;
   }
 
+  LLVM_NODISCARD
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  operator R() const {
+  operator R() {
     assert(Result && "Fell off the end of a string-switch");
-    return *Result;
+    return std::move(*Result);
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGSWITCH_H

unittests/ADT/StringSwitchTest.cpp

TEST(StringSwitchTest, EndsWithLower) {
   EXPECT_EQ(Suffix::Unknown, Translate("optimizer"));
 }
 
 TEST(StringSwitchTest, Cases) {
   enum class OSType { Windows, Linux, Unknown };
 
   auto Translate = [](StringRef S) {
     return llvm::StringSwitch<OSType>(S)
-        .Cases("wind\0ws", "win32", "winnt", OSType::Windows)
+        .Cases(StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt",
+               OSType::Windows)
         .Cases("linux", "unix", "*nix", "posix", OSType::Linux)
         .Default(OSType::Unknown);
   };
 
   EXPECT_EQ(OSType::Windows, Translate(llvm::StringRef("wind\0ws", 7)));
   EXPECT_EQ(OSType::Windows, Translate("win32"));
   EXPECT_EQ(OSType::Windows, Translate("winnt"));
 
TEST(StringSwitchTest, Cases) {
   EXPECT_EQ(OSType::Unknown, Translate(""));
 }
 
 TEST(StringSwitchTest, CasesLower) {
   enum class OSType { Windows, Linux, Unknown };
 
   auto Translate = [](StringRef S) {
     return llvm::StringSwitch<OSType>(S)
-        .CasesLower("wind\0ws", "win32", "winnt", OSType::Windows)
+        .CasesLower(StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt",
+                    OSType::Windows)
         .CasesLower("linux", "unix", "*nix", "posix", OSType::Linux)
         .Default(OSType::Unknown);
   };
 
   EXPECT_EQ(OSType::Windows, Translate(llvm::StringRef("WIND\0WS", 7)));
   EXPECT_EQ(OSType::Windows, Translate("WIN32"));
   EXPECT_EQ(OSType::Windows, Translate("WINNT"));