[Bug tree-optimization/98213] New: [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[Bug tree-optimization/98213] New: [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[marxin at gcc dot gnu.org]

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

            Bug ID: 98213
           Summary: [11 Regression] Never ending compilation at -O3 since
                    r11-161-g283cb9ea6293e813
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: rguenth at gcc dot gnu.org
  Target Milestone: ---

Since the revision, the following code does not terminate. The test-case was
given by yarpgen:

$ cat func.cpp
long var_23;
int var_24, test_var_8;
extern bool arr_20[][13];
char arr_21_0_0_0_0_0;
#include <algorithm>
int *test_arr_0;
void test(unsigned long long var_1) {
  int arr_16;
  for (int i_0 = 0;;)
    for (int i_5; i_5;) {
      for (int i_6 = 0; i_6 < 19; i_6 += 4)
        for (long i_7(test_var_8); i_7; i_7 += 2) {
          arr_20[0][i_7] = arr_21_0_0_0_0_0 = 0;
          var_23 = test_arr_0[0];
        }
      var_24 = std::max((unsigned long long)arr_16,
                        std::min((unsigned long long)5, var_1));
    }
}

$ timeout 10 g++ -O3 func.cpp -c
$ echo $?
124

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |10.2.0
     Ever confirmed|0                           |1
   Target Milestone|---                         |11.0
      Known to fail|                            |11.0
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-12-09

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Can you reduce to w/o <algorithm>?

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[marxin at gcc dot gnu.org]

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

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Sure:

long var_23, min___a;
int var_24, test_var_8, test_arr_16;
extern bool arr_20[][13];
char arr_21_0_0_0_0_0;
const unsigned long long &min(unsigned long long &__b) {
  if (__b)
    return __b;
  return min___a;
}
const unsigned long long &max(const unsigned long long &__a,
                              const unsigned long long &__b) {
  if (__b)
    return __b;
  return __a;
}
int *test_arr_0;
unsigned long long test_var_1;
void test() {
  for (;;) {
    for (int i_6 = 0; i_6 < 19; i_6 += 4)
      for (long i_7(test_var_8); i_7; i_7 += 2) {
        arr_20[0][i_7] = arr_21_0_0_0_0_0 = 0;
        var_23 = test_arr_0[0];
      }
    const unsigned long long &__trans_tmp_1 = min(test_var_1);
    var_24 = max(test_arr_16, __trans_tmp_1);
  }
}

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so it's "merely" taking a long time (exponential) walking all paths through
the CFG.  Meh.

I have a patch fixing this case but will have to think about some more.

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:84d08255f9f2f7137caf648fcc9dc36101bc893c

commit r11-5886-g84d08255f9f2f7137caf648fcc9dc36101bc893c
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Dec 9 15:48:36 2020 +0100

    tree-optimization/98213 - cache PHI walking result in SM

    This avoids exponential work when walking PHIs in loop store motion.
    Fails are quickly propagated and thus need no caching.

    2020-12-09  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/98213
            * tree-ssa-loop-im.c (sm_seq_valid_bb): Cache successfully
            processed PHIs.
            (hoist_memory_references): Adjust.

            * g++.dg/pr98213.C: New testcase.

[Bug tree-optimization/98213] [11 Regression] Never ending compilation at -O3 since r11-161-g283cb9ea6293e813

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.