[Bug c++/102970] New: stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize

[Bug c++/102970] New: stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize

[dan at stahlke dot org]

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

            Bug ID: 102970
           Summary: stable_sort uninitialized value with -funroll-loops
                    -fno-tree-vectorize
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dan at stahlke dot org
  Target Milestone: ---

Created attachment 51682
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51682&action=edit
demonstration source code

The attached file, compiled with 11.2.0, using the command line in the comment,
causes std::stable_sort to access uninitialized memory.  In fact, it already
goes wrong by the time it passes the inputs to the first comparison operation. 
The problem goes away if the copy constructor of the box struct is defaulted
(see the "#if").

It only happens with "-funroll-loops -fno-tree-vectorize".

Here is a Godbolt: https://godbolt.org/z/6PsdPj6q3

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|stable_sort uninitialized   |[11/12 Regression]
                   |value with -funroll-loops   |stable_sort uninitialized
                   |-fno-tree-vectorize         |value with -funroll-loops
                   |                            |-fno-tree-vectorize
      Known to fail|                            |11.1.0, 11.2.0
           Keywords|                            |wrong-code
      Known to work|                            |10.3.0
          Component|c++                         |middle-end
   Target Milestone|---                         |11.3

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-10-27
     Ever confirmed|0                           |1
             Target|x86_64-linux-gnu            |x86_64-linux-gnu,
                   |                            |aarch64-linux-gnu
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is a self contained example which aborts if it is wrong.
#include <vector>
#include <algorithm>
#include <cassert>

struct box {
   box(int xmin, int xmax, int ymin, int ymax) noexcept
      : m_xmin(xmin),
        m_xmax(xmax),
        m_ymin(ymin),
        m_ymax(ymax) {
   }

   box(box const & o) noexcept
      : m_xmin(o.m_xmin),
        m_xmax(o.m_xmax),
        m_ymin(o.m_ymin),
        m_ymax(o.m_ymax) { }

   int m_xmin;
   int m_xmax;
   int m_ymin;
   int m_ymax;
};


int main() {
    std::vector<box> vRects{ // requires 18 elements
        { 900, 11, 22, 33 },
        { 901, 11, 22, 33 },
        { 902, 11, 22, 33 },
        { 903, 11, 22, 33 },
        { 704, 11, 22, 33 },
        { 705, 11, 22, 33 },
        { 706, 11, 22, 33 },
        { 707, 11, 22, 33 },
        { 808, 11, 22, 33 },
        { 809, 11, 22, 33 },
        { 810, 11, 22, 33 },
        { 811, 11, 22, 33 },
        { 812, 11, 22, 33 },
        { 813, 11, 22, 33 },
        { 814, 11, 22, 33 },
        { 815, 11, 22, 33 },
        { 816, 11, 22, 33 },
        { 817, 11, 22, 33 },
        { 818, 11, 22, 33 },
    };

    std::stable_sort(vRects.begin(), vRects.end(), [](auto const &r1, auto
const &r2) -> bool {
        if (r2.m_xmax==0||r2.m_ymin==0||r2.m_ymax==0){__builtin_abort();}
        return r1.m_xmin < r2.m_xmin;
    });
  return 0;
}

------- CUT -----
-O2 -funroll-loops -fno-tree-vectorize
Is enough (note the -fno-tree-vectorize is needed for the trunk as it is
enabled now at -O2).

Also this happens on aarch64-linux-gnu too.

Confirmed.

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The gimple level looks correct:
  <bb 4> [local count: 8209314308]:
  # __cur_2 = PHI <__cur_149(5), _141(3)>
  # __first_156 = PHI <__first_148(5), &D.24777(3)>
  # prephitmp_155 = PHI <pretmp_3(5), 900(3)>
  # prephitmp_153 = PHI <pretmp_142(5), 11(3)>
  # prephitmp_108 = PHI <pretmp_109(5), 22(3)>
  # prephitmp_105 = PHI <pretmp_106(5), 33(3)>
  MEM[(int *)__cur_2] = prephitmp_155;
  MEM[(int *)__cur_2 + 4B] = prephitmp_153;
  MEM[(int *)__cur_2 + 8B] = prephitmp_108;
  MEM[(int *)__cur_2 + 12B] = prephitmp_105;
  __first_148 = __first_156 + 16;
  __cur_149 = __cur_2 + 16;
  if (&MEM <const struct box[19]> [(void *)&D.24777 + 304B] != __first_148)
    goto <bb 5>; [89.00%]
  else
    goto <bb 6>; [11.00%]

  <bb 5> [local count: 7306289739]:
  pretmp_3 = MEM[(int *)__first_148];
  pretmp_142 = MEM[(int *)__first_148 + 4B];
  pretmp_109 = MEM[(int *)__first_148 + 8B];
  pretmp_106 = MEM[(int *)__first_148 + 12B];
  goto <bb 4>; [100.00%]

I suspect the rtl level unroller messes up the first iteration for the stores
in the above case.

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
            Summary|[11/12 Regression]          |[11/12 Regression]
                   |stable_sort uninitialized   |stable_sort uninitialized
                   |value with -funroll-loops   |value with -funroll-loops
                   |-fno-tree-vectorize         |-fno-tree-vectorize since
                   |                            |r11-2963-gd6a05b494b4b714e
           Keywords|needs-bisection             |

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r11-2963-gd6a05b494b4b714e.

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[rguenth at gcc dot gnu.org]

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

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
           Priority|P3                          |P2
             Status|NEW                         |ASSIGNED

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will investigate.

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
So it looks like while we copy the array to an allocated array successfully
the call

        movl    $10, %edx
        movq    %rbp, %rsi
        leaq    32(%rsp), %rdi
        movq    %r12, 8(%rsp)
        call   
_ZNSt17_Temporary_bufferIN9__gnu_cxx17__normal_iteratorIP3boxSt6vectorIS2_SaIS2_EEEES2_EC1ES7_l

clobbers part of the vRects data on the stack.  (it is at 32(%rsp))

This is the function that is appearantly miscomplied I think.  We have there

  <bb 9> [local count: 3804909251]:
  # PT = { D.54048 } (escaped, escaped heap)
  # __cur_76 = PHI <__cur_43(11), __cur_36(8)>
  # prephitmp_81 = PHI <pretmp_80(11), _32(8)>
  # prephitmp_83 = PHI <pretmp_82(11), _33(8)>
  # prephitmp_31 = PHI <pretmp_78(11), _34(8)>
  # prephitmp_28 = PHI <pretmp_45(11), _35(8)>
  [t.C:14:9] MEM[(int *)__cur_76 clique 4 base 1] = prephitmp_81;
  [t.C:15:9] MEM[(int *)__cur_76 + 4B clique 4 base 1] = prephitmp_83;
  [t.C:16:9] MEM[(int *)__cur_76 + 8B clique 4 base 1] = prephitmp_31;
  [t.C:17:9] MEM[(int *)__cur_76 + 12B clique 4 base 1] = prephitmp_28;
 
[/home/rguenther/install/gcc-11/usr/local/include/c++/11.2.1/bits/stl_tempbuf.h:212:8]
# PT = { D.54048 } (escaped, escaped heap)
  __cur_43 = __cur_76 + 16;
 
[/home/rguenther/install/gcc-11/usr/local/include/c++/11.2.1/bits/stl_tempbuf.h:212:20]
if (_3 != __cur_43)
    goto <bb 11>; [89.00%]
  else
    goto <bb 10>; [11.00%]

  <bb 10> [local count: 418540015]:
  # RANGE ~[18446744073709551600, 18446744073709551600]
  _37 = 18446744073709551600 - _56;
  _41 = _37 + _42;
 
[/home/rguenther/install/gcc-11/usr/local/include/c++/11.2.1/bits/stl_tempbuf.h:212:8]
# PT = { D.54048 } (escaped, escaped heap)
  __prev_27 = _26 + _41;
  goto <bb 12>; [100.00%]

  <bb 11> [local count: 3386369236]:
  [t.C:14:18] pretmp_80 = MEM[(int *)__cur_43 + -16B clique 4 base 0];
  [t.C:15:18] pretmp_82 = MEM[(int *)__cur_43 + -12B clique 4 base 0];
  [t.C:16:18] pretmp_78 = MEM[(int *)__cur_43 + -8B clique 4 base 0];
  [t.C:17:18] pretmp_45 = MEM[(int *)__cur_43 + -4B clique 4 base 0];
  goto <bb 9>; [100.00%]

note how PRE manages to "leak" the clique from one iteration to the previous
by translating the references across the backedge but the references
do actually conflict.

So we get to changes that are invalid done by sched2.  Both disabling
sched2 and PRE avoids this situation.

-fdbg-cnt=treepre_insert:10-10 is enough to trigger it (on the 11 branch).

[Bug middle-end/102970] [11/12 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 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:1967fd8f2197f2b0334ab0fbc26abc3d9efe56c9

commit r12-4865-g1967fd8f2197f2b0334ab0fbc26abc3d9efe56c9
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Nov 3 13:26:48 2021 +0100

    tree-optimization/102970 - remap cliques when translating over backedges

    The following makes sure to remap (or rather drop for simplicity)
    dependence info encoded in MR_DEPENDENCE_CLIQUE when PRE PHI translation
    translates a reference over a backedge since that ends up interleaving
    two different loop iterations which boils down to two different
    inline copies.

    2021-11-03  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/102970
            * tree-ssa-pre.c (phi_translate_1): Drop clique and base
            when translating a MEM_REF over a backedge.

            * g++.dg/opt/pr102970.C: New testcase.

[Bug middle-end/102970] [11 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12 Regression]          |[11 Regression] stable_sort
                   |stable_sort uninitialized   |uninitialized value with
                   |value with -funroll-loops   |-funroll-loops
                   |-fno-tree-vectorize since   |-fno-tree-vectorize since
                   |r11-2963-gd6a05b494b4b714e  |r11-2963-gd6a05b494b4b714e
      Known to work|                            |12.0

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug middle-end/102970] [11 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:2936f551adec1d8f8c731d013e1b0d9d3f1e824a

commit r11-9258-g2936f551adec1d8f8c731d013e1b0d9d3f1e824a
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Nov 3 13:26:48 2021 +0100

    tree-optimization/102970 - remap cliques when translating over backedges

    The following makes sure to remap (or rather drop for simplicity)
    dependence info encoded in MR_DEPENDENCE_CLIQUE when PRE PHI translation
    translates a reference over a backedge since that ends up interleaving
    two different loop iterations which boils down to two different
    inline copies.

    2021-11-03  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/102970
            * tree-ssa-pre.c (phi_translate_1): Drop clique and base
            when translating a MEM_REF over a backedge.

            * g++.dg/opt/pr102970.C: New testcase.

    (cherry picked from commit 1967fd8f2197f2b0334ab0fbc26abc3d9efe56c9)

[Bug middle-end/102970] [11 Regression] stable_sort uninitialized value with -funroll-loops -fno-tree-vectorize since r11-2963-gd6a05b494b4b714e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
      Known to work|                            |11.2.1
             Status|ASSIGNED                    |RESOLVED

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