[Bug tree-optimization/105216] New: [12 regression] 8% regression for m-queens compared to gcc11 O2

[Bug tree-optimization/105216] New: [12 regression] 8% regression for m-queens compared to gcc11 O2

[crazylht at gmail dot com]

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

            Bug ID: 105216
           Summary: [12 regression] 8% regression for m-queens compared to
                    gcc11 O2
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: crazylht at gmail dot com
  Target Milestone: ---

Created attachment 52778
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52778&action=edit
g++ -O2 main.c;./a.out

Regression happens in pass_pre

      while (posib != UINT_FAST32_MAX) {
        // The standard trick for getting the rightmost bit in the mask
        uint_fast32_t bit = ~posib & (posib + 1);
        posib ^= bit; // Eliminate the tried possibility.
        uint_fast32_t new_diagl = (bit << 1) | diagl_shifted;
        uint_fast32_t new_diagr = (bit >> 1) | diagr_shifted;
        bit |= cols[d];
        uint_fast32_t new_posib = (bit | new_diagl | new_diagr);

        if (new_posib != UINT_FAST32_MAX) {
            uint_fast32_t lookahead1 = (bit | (new_diagl << (LOOKAHEAD - 2)) |
(new_diagr >> (LOOKAHEAD - 2)));
            uint_fast32_t lookahead2 = (bit | (new_diagl << (LOOKAHEAD - 1)) |
(new_diagr >> (LOOKAHEAD - 1)));
            uint_fast32_t allowed2 = l_rest > (int8_t)0;

            if(allowed2 && ((lookahead2 == UINT_FAST32_MAX) || (lookahead1 ==
UINT_FAST32_MAX))) {
                continue;
            }


          if(l_rest == (STORE_LEVEL + 1)) {
            start_level4[level4_cnt][0] = bit;   // cols
            start_level4[level4_cnt][1] = new_diagl; // diagl
            start_level4[level4_cnt][2] = new_diagr; // diagr
            level4_cnt++;
            continue;
          }

          l_rest--;

          // The next two lines save stack depth + backtrack operations
          // when we passed the last possibility in a row.
          // Go lower in the stack, avoid branching by writing above the
current
          // position
          posibs[d] = posib;
          d += posib != UINT_FAST32_MAX; // avoid branching with this trick
          posib = new_posib;


          // make values current
          cols[d] = bit;
          diagl[d] = new_diagl;
          diagr[d] = new_diagr;
          rest[d] = l_rest;
          diagl_shifted = new_diagl << 1;
          diagr_shifted = new_diagr >> 1;
        }
      }
      d--;
      posib = posibs[d]; // backtrack ...
    }

For bit |= cols[d]; cols[d] is loop invariant if loop latch from *continue*,
GCC11 catches it, GCC12 not.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Does -fno-tree-vectorizer help? There is definitely another big recording the
fact pre had to turn something off while vectorization is turned on.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Target Milestone|---                         |12.0
   Last reconfirmed|                            |2022-04-11
           Keywords|                            |missed-optimization,
                   |                            |needs-bisection
             Target|                            |x86_64-*-*
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I suppose it's good again with -fno-tree-vectorize?  With vectorization enabled
we tame down PRE to avoid creating loop carried dependences the vectorizer
cannot handle.  For the "important" opportunities we try to recover after
vectorization with predictive commoning.

Hmm, confirmed with -fno-tree-vectorize even.

Possibly caused by r12-7389-ge25dce50133405

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2

[crazylht at gmail dot com]

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

--- Comment #3 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Andrew Pinski from comment #1)
> Does -fno-tree-vectorizer help? There is definitely another big recording
> the fact pre had to turn something off while vectorization is turned on.

No, not related to O2 vectorizer.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> I suppose it's good again with -fno-tree-vectorize?  With vectorization
> enabled we tame down PRE to avoid creating loop carried dependences the
> vectorizer cannot handle.  For the "important" opportunities we try to
> recover after vectorization with predictive commoning.
> 
> Hmm, confirmed with -fno-tree-vectorize even.
> 
> Possibly caused by r12-7389-ge25dce50133405

Nope, reverting that doesn't fix it.

Note it seems the GCC 11 branch head also regressed compared to
r11-8866-g056e324ce46a79 but not as much as trunk.  Note I can reproduce
~2% regression from that 11 branch rev on the branch and ~4% towards trunk
so it's also a bit noisy.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
My bisect shows it's caused by
r12-3876-g4a960d548b7d7d942f316c5295f6d849b74214f5

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #6 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Hongtao.liu from comment #5)
> My bisect shows it's caused by
> r12-3876-g4a960d548b7d7d942f316c5295f6d849b74214f5

pre dump before vs after

-    goto <bb 21>; [11.00%]
-
-  <bb 12> [local count: 105119324]:
-  pretmp_379 = cols[d_243]; ---- miss optimization here.
-
-  <bb 13> [local count: 955630226]:
-  # level4_cnt_250 = PHI <level4_cnt_236(20), level4_cnt_242(12)>
-  # d_252 = PHI <d_98(20), d_243(12)>
-  # posib_254 = PHI <posib_102(20), posib_244(12)>
-  # diagl_shifted_255 = PHI <diagl_shifted_103(20), diagl_shifted_184(12)>
-  # diagr_shifted_256 = PHI <diagr_shifted_104(20), diagr_shifted_185(12)>
-  # l_rest_257 = PHI <l_rest_115(20), prephitmp_366(12)>
-  # prephitmp_380 = PHI <prephitmp_378(20), pretmp_379(12)>
+    goto <bb 19>; [11.00%]
+
+  <bb 12> [local count: 955630226]:
+  # level4_cnt_250 = PHI <level4_cnt_205(18), level4_cnt_242(11)>
+  # d_252 = PHI <d_47(18), d_243(11)>
+  # posib_254 = PHI <posib_27(18), posib_244(11)>
+  # diagl_shifted_255 = PHI <diagl_shifted_25(18), diagl_shifted_184(11)>
+  # diagr_shifted_256 = PHI <diagr_shifted_24(18), diagr_shifted_185(11)>
+  # l_rest_257 = PHI <l_rest_13(18), prephitmp_313(11)>
   _30 = ~posib_254;
   _31 = posib_254 + 1;
   bit_189 = _30 & _31;
@@ -1030,15 +1037,16 @@ uint64_t nqueens (uint_fast8_t n)
   new_diagl_191 = _32 | diagl_shifted_255;
   _33 = bit_189 >> 1;
   new_diagr_192 = _33 | diagr_shifted_256;
-  bit_193 = bit_189 | prephitmp_380;
+  _34 = cols[d_252];
+  bit_193 = _34 | bit_189;

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 11 Apr 2022, crazylht at gmail dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105216
> 
> --- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
> My bisect shows it's caused by
> r12-3876-g4a960d548b7d7d942f316c5295f6d849b74214f5

So it's a missed jump threading - care to investigate which?

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #8 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to rguenther@suse.de from comment #7)
> On Mon, 11 Apr 2022, crazylht at gmail dot com wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105216
> > 
> > --- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
> > My bisect shows it's caused by
> > r12-3876-g4a960d548b7d7d942f316c5295f6d849b74214f5
> 
> So it's a missed jump threading - care to investigate which?

The commit is about jump threading, but the regression is present without
-fopenmp， so there's no jump threading?
Somehow it affects PRE.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #9 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Hongtao.liu from comment #8)
> (In reply to rguenther@suse.de from comment #7)
> > On Mon, 11 Apr 2022, crazylht at gmail dot com wrote:
> > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105216
> > > 
> > > --- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
> > > My bisect shows it's caused by
> > > r12-3876-g4a960d548b7d7d942f316c5295f6d849b74214f5
> > 
> > So it's a missed jump threading - care to investigate which?
> 
> The commit is about jump threading, but the regression is present without
> -fopenmp， so there's no jump threading?
> Somehow it affects PRE.
Please ignore this comment, obviously i had poor understanding of jump
threading.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #10 from Hongtao.liu <crazylht at gmail dot com> ---
Probably related to below 3 cancelled jump thread which affects pre.

2076Threading through latch before loop opts would create non-empty latch:
2077  Cancelling jump thread: (15, 16) incoming edge;  (16, 43) normal;

3742Path crosses loops:
3743  Cancelling jump thread: (36, 3) incoming edge;  (3, 37) normal (37, 4)
nocopy;

4755Threading through latch before loop opts would create non-empty latch:
4756  Cancelling jump thread: (26, 28) incoming edge;  (28, 40) normal;

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX.

[crazylht at gmail dot com]

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

--- Comment #11 from Hongtao.liu <crazylht at gmail dot com> ---
There's post_loop pass_thread_jumps, add a copy of pass_pre doesn't help.

[Bug tree-optimization/105216] [12 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
                 CC|                            |marxin at gcc dot gnu.org
            Summary|[12 regression] 8%          |[12 regression] 8%
                   |regression for m-queens     |regression for m-queens
                   |compared to gcc11 O2 on     |compared to gcc11 O2 on
                   |CLX.                        |CLX. since
                   |                            |r12-3876-g4a960d548b7d7d94

--- Comment #12 from Martin Liška <marxin at gcc dot gnu.org> ---
Yes, I can confirm r12-3876-g4a960d548b7d7d94 regresses from 0m2.603s to
0m2.904s.

[Bug tree-optimization/105216] [12/13 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |12.2

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 12.1 is being released, retargeting bugs to GCC 12.2.

[Bug tree-optimization/105216] [12/13 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/105216] [12/13 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[pinskia at gcc dot gnu.org]

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

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Might be interesting to test it again to see if it has been fixed on the trunk.

[Bug tree-optimization/105216] [12/13 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[crazylht at gmail dot com]

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

--- Comment #16 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Andrew Pinski from comment #15)
> Might be interesting to test it again to see if it has been fixed on the
> trunk.

The regression is still there.

gcc version 13.0.0 20230102 (experimental) (GCC)

[Bug tree-optimization/105216] [12/13/14 regression] 8% regression for m-queens compared to gcc11 O2 on CLX. since r12-3876-g4a960d548b7d7d94

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.3                        |12.4

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 12.3 is being released, retargeting bugs to GCC 12.4.