[Bug tree-optimization/126538] New: Compile time hog with gimple-range-phi and bitint

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

            Bug ID: 126538
           Summary: Compile time hog with gimple-range-phi and bitint
           Product: gcc
           Version: 17.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ktkachov at gcc dot gnu.org
  Target Milestone: ---

/* Entry point: phi_group::calculate_using_modifier,
gcc/gimple-range-phi.cc:167
        num_iter = TYPE_PRECISION (m_vr.type ()) + 1;

   This is NOT a wrong-code case: the range that comes out is correct.  It is a
   compile-time explosion.  The iteration budget is the precision of the group
   type, and each iteration folds the modifier over an int_range_max of that
   same precision, so the cost is cubic in the precision.  _BitInt allows
   65535 bits, and this ten-line function then needs about 41000 iterations of
   a 65535-bit multiply.

     gcc -O2 -c phigrp-02-bitint-iteration-hog.c        167 s
     gcc -O1 -c ...                                       0.02 s   (no ranger
vrp)
     gcc -O2 -fno-tree-vrp -c ...                         0.8 s
     x = x + 3 instead of x * 3, -O2                      0.44 s   (PLUS skips
                                                           the iteration)

   Scaling of the -O2 time with the precision, one function per file:
     512 0.02  1024 0.04  2048 0.08  4096 0.18  8192 0.63
     16384 3.5  32768 22.8  65535 167.

   Dump evidence, at precision 16384 so the dump is quick:
     PHI ANALYZER : New PHI GROUP < x_1 > : range : [irange] T [1, 1][3, +INF]
       Modifier : x_8 = x_1 * 3;
       Initial range was [irange] T [1, 1]  */

typedef _BitInt(65535) T;

__attribute__((noipa)) T
f (int n)
{
  T x = 1;
  for (int i = 0; i < n; i++)
    x = x * 3;
  return x;
}

int
main (void)
{
  return (int) f (2) - 9;
}