[Support] Use find() for faster StringRef::count.

[ishitatsuyuki]

Summary

While profiling InclusionRewriter, it was found that counting lines was
so slow that it took up 20% of the processing time. Surely, calling
memcmp() of size 1 on every substring in the window isn't a good idea.

Use StringRef::find() instead; in the case of N=1 it will forward to
memcmp which is much more optimal. For 2<=N<256 it will run the same
memcmp loop as we have now, which is still suboptimal but at least does
not regress anything.

[ishitatsuyuki]

A note that the N=2 search code is mostly mirrored from glibc; I believe it's short enough to not cause copyright issues but please let me know if I should be more defensive here.

https://codebrowser.dev/glibc/glibc/string/memmem.c.html#70

[nikic]

Please split this into two patches, one for count(), and one for find().

[ishitatsuyuki]

Split revision; this becomes the first revision (StringRef::count).

[ishitatsuyuki]

The split is done; the second revision is D133660.

[nikic]

LGTM

[ishitatsuyuki]

Looks like this still hasn't been committed. Can anyone help me commit this (as I don't have commiter rights)?

[nikic]

llvm/lib/Support/StringRef.cpp

386

The !N condition needs to be retained, otherwise we will go into an infinite loop for an empty Str. I believe this causes the ADTTest timeout.

(Returning 0 for an empty string isn't really right, this should return Length + 1, but this is orthogonal to your change.)

[ishitatsuyuki]

Restore check for zero N

[ishitatsuyuki]

llvm/lib/Support/StringRef.cpp

386

Looks like there's a test with hardcoded expect result of 0. Should I change the test too or retain the old behavior?

[nikic]

llvm/lib/Support/StringRef.cpp

386

I'd suggest keeping the old behavior in this patch (maybe with a TODO) to keep it NFC. We should fix this separately.

[ishitatsuyuki]

Restore behavior when Str == "" and add TODO

[nikic]

LGTM

llvm/lib/Support/StringRef.cpp

 //===----------------------------------------------------------------------===//
 // Helpful Algorithms
 //===----------------------------------------------------------------------===//
 
 /// count - Return the number of non-overlapped occurrences of \arg Str in
 /// the string.
 size_t StringRef::count(StringRef Str) const {
   size_t Count = 0;
+  size_t Pos = 0;
   size_t N = Str.size();
-  if (!N || N > Length)
+  // TODO: For an empty `Str` we return 0 for legacy reasons. Consider changing
+  //       this to `Length + 1` which is more in-line with the function
+  //       description.
+  if (!N)
     return 0;
-  for (size_t i = 0, e = Length - N + 1; i < e;) {
-    if (substr(i, N).equals(Str)) {
-      ++Count;
-      i += N;
-    }
-    else
-      ++i;
+  while ((Pos = find(Str, Pos)) != npos) {
+    Pos += N;
   }
   return Count;
 }
 
 static unsigned GetAutoSenseRadix(StringRef &Str) {
   if (Str.empty())
     return 10;