[Bug tree-optimization/96979] [8/9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96979

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Reduced testcase:

using u64 = unsigned long long;

constexpr inline u64
foo (const char *str) noexcept
{
  u64 value = 0xcbf29ce484222325ULL;
  for (u64 i = 0; str[i]; i++)
    value = (value ^ u64(str[i])) * 0x100000001b3ULL;
  return value;
}

struct V
{
  enum W
  {
#define A(n) n,
#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) A(n##5) A(n##6) A(n##7)
A(n##8) A(n##9)
#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) B(n##5) B(n##6) B(n##7)
B(n##8) B(n##9)
#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) C(n##5) C(n##6) C(n##7)
C(n##8) C(n##9)
#define E D(foo1) D(foo2) D(foo3)
    E
    last
  };

  constexpr static W
  bar (const u64 h) noexcept
  {
    switch (h)
      {
#undef A
#define F(n) #n
#define A(n) case foo (F(n)): return n;
        E
      }
    return last;
  }
};

int
baz (const char *s)
{
  const u64 h = foo (s);
  return V::bar (h);
}

jump_table_cluster::find_jump_tables is indeed quadratic in the number of case
label clusters (3000 on the above testcase):
  for (unsigned i = 1; i <= l; i++)
    {
      /* Set minimal # of clusters with i-th item to infinite.  */
      min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));

      for (unsigned j = 0; j < i; j++)
        {
          unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
          if (i - j < case_values_threshold ())
            s += i - j;

          /* Prefer clusters with smaller number of numbers covered.  */
          if ((min[j].m_count + 1 < min[i].m_count
               || (min[j].m_count + 1 == min[i].m_count
                   && s < min[i].m_non_jt_cases))
              && can_be_handled (clusters, j, i - 1))
            min[i] = min_cluster_item (min[j].m_count + 1, j, s);
        }

      gcc_checking_assert (min[i].m_count != INT_MAX);
    }