[Support] Optimize (.*) regex matches

[nikic]

Summary

If capturing groups are used, the regex matcher handles something like (.*)suffix by first doing a maximal match of .*, trying to match suffix afterward, and then reducing the maximal stop position one by one until this finally succeeds. This makes the match quadratic in the length of the line (with large constant factors).

This is particularly problematic because regexes of this form are ubiquitous in FileCheck (something like [[VAR:%.*]] = ... falls in this category), making FileCheck executions much slower than they have any right to be.

This implements a very crude optimization that checks if suffix starts with a fixed character, and steps back to the last occurrence of that character, instead of stepping back by one character at the time. This drops FileCheck time on clang/test/CodeGen/RISCV/rvv-intrinsics/vloxseg_mask.c from 7.3 seconds to 2.7 seconds.

An obvious further improvement would be to check more than one character (once again, this is particularly relevant for FileCheck, because the next character is usually a space, which happens to have many occurrences).

This should help with https://github.com/llvm/llvm-project/issues/54821.

[nikic]

I don't think this code has any maintainers, as it is originally taken from OpenBSD, so choice of reviewers is somewhat arbitrary...

[tstellar]

Is there some reason we can't use the c++11 regex library for this?

[nikic]

In D123776#3452587, @tstellar wrote:

Is there some reason we can't use the c++11 regex library for this?

std::regex implementations are known to perform very badly for ABI compatibility reasons -- but it's possible that they're still better than this one, so I guess it would be worth trying at least.

[junaire]

In D123776#3452587, @tstellar wrote:

Is there some reason we can't use the c++11 regex library for this?

I heard about some rumors that std::regex is really bad, both slow to build and run, is it true? Can we use some well-maintained 3rd party library like CTRE or re2?

[xbolva00]

Yeah, std::regex is very poor.. anything is better than std::regex nowdays.

Can we use some well-maintained 3rd party library like CTRE or re2?

I am not sure about CTRE as there is mainly a one sole developer so.. risks are higher.

re2, pcre or hyperscan sound good.

[xbolva00]

In D123776#3452653, @nikic wrote:

In D123776#3452587, @tstellar wrote:

Is there some reason we can't use the c++11 regex library for this?

std::regex implementations are known to perform very badly for ABI compatibility reasons -- but it's possible that they're still better than this one, so I guess it would be worth trying at least.

Is it worth to spend time to port this matching code to std::regex when you could use much better libs?

[aeubanks]

this looks fine and is better than the status quo so let's land this first then consider alternatives

[nikic]

Landed as https://github.com/llvm/llvm-project/commit/653de14f17215c540a7dc058acb3c29a28ef0f1c, forgot to add differential revision tag.

I also gave std::regex a try, with the following patch: https://gist.github.com/nikic/9608b350a821740402115790fd2a906f This actually had good performance on clang/test/CodeGen/RISCV/rvv-intrinsics/vloxseg_mask.c -- but the multiline support that is needed by FileCheck is apparently only part of C++17 (if compilers implement it at all?) so this doesn't work for our purpose. I tried emulating it, but that would require support for lookbehind assertions, which is also missing.

llvm/lib/Support/regengine.inc

 #define slow  sslow
 #define dissect sdissect
 #define backref sbackref
 #define step  sstep
 #define print sprint
 #define at  sat
 #define match smat
 #define nope  snope
+#define step_back sstep_back
 #endif
 #ifdef LNAMES
 #define matcher lmatcher
 #define fast  lfast
 #define slow  lslow
 #define dissect ldissect
 #define backref lbackref
 #define step  lstep
 #define print lprint
 #define at  lat
 #define match lmat
 #define nope  lnope
+#define step_back lstep_back
 #endif
 
 /* another structure passed up and down to avoid zillions of parameters */
 struct match {
   struct re_guts *g;
   int eflags;
   llvm_regmatch_t *pmatch;  /* [nsub+1] (0 element unused) */
   const char *offp;   /* offsets work from here */
#endif
   if (m->pmatch != NULL)
     free((char *)m->pmatch);
   if (m->lastpos != NULL)
     free((char *)m->lastpos);
   STATETEARDOWN(m);
   return(0);
 }
 
+/* Step back from "stop" to a position where the strip startst..stopst might
+ * match. This can always conservatively return "stop - 1", but may return an
+ * earlier position if matches at later positions are impossible. */
+static const char *
+step_back(struct re_guts *g, const char *start, const char *stop, sopno startst,
+          sopno stopst)
+{
+  /* Always step back at least one character. */
+  assert(stop > start);
+  const char *res = stop - 1;
+
+  /* Check whether the strip startst..stropst starts with a fixed character,
+   * ignoring any closing parentheses. If not, return a conservative result. */
+  for (;;) {
+    if (startst >= stopst)
+      return res;
+    if (OP(g->strip[startst]) != ORPAREN)
+      break;
+    startst++;
+  }
+  if (OP(g->strip[startst]) != OCHAR)
+    return res;
+
+  /* Find the character that starts the following match. */
+  char ch = OPND(g->strip[startst]);
+  for (; res != start; --res) {
+    if (*res == ch)
+      break;
+  }
+  return res;
+}
+
 /*
  - dissect - figure out what matched what, no back references
  */
 static const char *     /* == stop (success) always */
 dissect(struct match *m, const char *start, const char *stop, sopno startst,
         sopno stopst)
 {
   int i;
case OQUEST_:
         /* how long could this one be? */
         rest = slow(m, sp, stp, ss, es);
         assert(rest != NULL); /* it did match */
         /* could the rest match the rest? */
         tail = slow(m, rest, stop, es, stopst);
         if (tail == stop)
           break;    /* yes! */
         /* no -- try a shorter match for this one */
-        stp = rest - 1;
+        stp = step_back(m->g, sp, rest, es, stopst);
         assert(stp >= sp); /* it did work */
       }
       ssub = ss + 1;
       esub = es - 1;
       /* did innards match? */
       if (slow(m, sp, rest, ssub, esub) != NULL) {
         const char *dp = dissect(m, sp, rest, ssub, esub);
         (void)dp; /* avoid warning if assertions off */
         assert(dp == rest);
       } else    /* no */
         assert(sp == rest);
       sp = rest;
       break;
     case OPLUS_:
       stp = stop;
       for (;;) {
         /* how long could this one be? */
         rest = slow(m, sp, stp, ss, es);
         assert(rest != NULL); /* it did match */
         /* could the rest match the rest? */
         tail = slow(m, rest, stop, es, stopst);
         if (tail == stop)
           break;    /* yes! */
         /* no -- try a shorter match for this one */
-        stp = rest - 1;
+        stp = step_back(m->g, sp, rest, es, stopst);
         assert(stp >= sp); /* it did work */
       }
       ssub = ss + 1;
       esub = es - 1;
       ssp = sp;
       oldssp = ssp;
       for (;;) {  /* find last match of innards */
         sep = slow(m, ssp, rest, ssub, esub);

 #undef  slow
 #undef  dissect
 #undef  backref
 #undef  step
 #undef  print
 #undef  at
 #undef  match
 #undef  nope
+#undef  step_back