[Bug tree-optimization/102814] New: [12 regression] quadratique/exponential time complexity for max-jump-thread-duplication-stmts

["dimhen at gmail dot com" <gcc-bugzilla@gcc.gnu.org>]

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

            Bug ID: 102814
           Summary: [12 regression] quadratique/exponential time
                    complexity for max-jump-thread-duplication-stmts
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dimhen at gmail dot com
  Target Milestone: ---

r12-4256 FAST
r12-4444 SLOW

g++ -fpreprocessed -std=c++98 -O2 --param max-jump-thread-duplication-stmts=NNN
-c x.ii

     r12-4256 r12-4444
180    0.5s     0.21s
181    0.8s     > 100s
190    1.0s     52s

cat x.ii # cvise'd from proprietary codebase
struct a {
  a operator+(int);
};
void *operator new(unsigned long, void *c) { return c; }
struct d {
  void h(int *j) { new (j) int(); }
};
struct k {
  struct {
    int e;
    int f;
  } g;
};
struct n : k {
  a m_fn2();
  a o();
  int m_fn4();
  int operator[](int);
  int ae;
  void s() {
    if (g.e != g.f) {
      d l;
      int *b;
      l.h(b);
    }
    a m = o();
    t(m, ae);
  }
  template <typename af> void u(a, af, af);
  void t(a, unsigned char);
};
int ah;
struct v {
  n w();
};
void x() {
  v p;
  n ak = p.w(), al, rapdu;
  int q(ak.m_fn4());
  int r;
  for (int i = 0; q; i++) {
    if (i == q - 1) {
      al.s();
      r = ak.m_fn4();
    }
    al.s();
    al.s();
    al.s();
    al.s();
    a am, an = ak.m_fn2(), ao = an + 1, ap = ak.m_fn2(), aq = ap + ah,
          ar = aq + r;
    al.u(am, ao, ar);
    if (i == q - 1)
      al.s();
    i &&rapdu[1];
  }
}

g++ -v
Using built-in specs.
COLLECT_GCC=/home/dimhen/arch-gcc/gcc_current/bin/g++
COLLECT_LTO_WRAPPER=/home/dimhen/arch-gcc/gcc_current/libexec/gcc/x86_64-pc-linux-gnu/12.0.0/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
Target: x86_64-pc-linux-gnu
Configured with: /home/dimhen/src/gcc_current/configure
--prefix=/home/dimhen/arch-gcc/gcc_current
--enable-checking=yes,df,fold,rtl,extra --enable-languages=c,c++,lto
--disable-multilib --enable-shared --enable-threads=posix --enable-__cxa_atexit
--enable-gnu-unique-object --enable-linker-build-id
--with-linker-hash-style=gnu --enable-plugin --enable-initfini-array --with-isl
--enable-offload-targets=nvptx-none --without-cuda-driver
--enable-gnu-indirect-function --enable-cet --with-tune=native
--enable-libstdcxx-debug
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.0 20211015 (experimental) [master r12-4444-ga01704fc45a] (GCC)