[Bug tree-optimization/98255] New: wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[Bug tree-optimization/98255] New: wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 98255
           Summary: wrong code at -Os and above with -fPIC on
                    x86_64-pc-linux-gnu
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

[510] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/11.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 11.0.0 20201212 (experimental) [master revision
ff2dfdef2f2:87144b47033:815eb852a2d293331eba2e241a986b8641d4da1f] (GCC) 
[511] % 
[511] % gcctk -Os small.c; ./a.out
[512] % 
[512] % gcctk -Os -fPIC small.c
[513] % ./a.out
Segmentation fault
[514] % 
[514] % cat small.c
struct a {
  volatile unsigned b;
  unsigned c;
};

int d, *e, h, k, l;
static struct a f;
long g;
static unsigned i = 4294967294;
volatile int j;

long m() {
  char n[4][4][3] = {{{9, 2, 8}, {9, 2, 8}, {9, 2, 8}, {9}}, {{8}}, {{8}},
{{2}}};
  while (d) {
    for (; f.c < 4; f.c++) {
      *e = 0;
      h = n[f.c + 4][0][d];
    }
    while (g)
      return n[0][3][i];
    while (1) {
      if (k) {
        j = 0;
        if (j)
          continue;
      }
      if (l)
        break;
    }
  }
  return 0;
}

int main() {
  m();
  return 0;
}

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |jamborm at gcc dot gnu.org
            Summary|wrong code at -Os and above |[10/11 Regression] wrong
                   |with -fPIC on               |code at -Os and above with
                   |x86_64-pc-linux-gnu         |-fPIC on
                   |                            |x86_64-pc-linux-gnu
   Last reconfirmed|                            |2020-12-12
   Target Milestone|---                         |10.3
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r10-917-g3b47da42de621c6c3bf7d2f9245df989aa7eb5a1

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P2

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Martin, can you please have a look?  Thanks.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jamborm at gcc dot gnu.org]

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

--- Comment #3 from Martin Jambor <jamborm at gcc dot gnu.org> ---
So SRA sees statements:
  n[0][2] = "\t\x02\b";
and later
  _11 = n[0][3][4294967294];

The latter loads a scalar sitting inside what the store above
initialized (according to get_ref_base_and_extent) and so SRA creates
a single char replacement for it which is initialized with:

n$0$3$4294967294_24 = "\t\x02\b"[4294967294];

the RHS being:

 <array_ref 0x7ffff76420a8
    type <integer_type 0x7ffff74e63f0 char sizes-gimplified public QI
        size <integer_cst 0x7ffff74cddc8 constant 8>
        unit-size <integer_cst 0x7ffff74cdde0 constant 1>
        align:8 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type
0x7ffff74e63f0 precision:8 min <integer_cst 0x7ffff74cde10 -128> max
<integer_cst 0x7ffff74cde40 127>
        pointer_to_this <pointer_type 0x7ffff74f1c78>>

    arg:0 <string_cst 0x7ffff76133d8
        type <array_type 0x7ffff7601498 type <integer_type 0x7ffff74e63f0 char>
            sizes-gimplified BLK
            size <integer_cst 0x7ffff74eb180 constant 24>
            unit-size <integer_cst 0x7ffff7613138 constant 3>
            align:8 warn_if_not_align:0 symtab:0 alias-set 0 canonical-type
0x7ffff7601498 domain <integer_type 0x7ffff76013f0>>
        constant "\011\002\010">
    arg:1 <integer_cst 0x7ffff76130a8 type <integer_type 0x7ffff74e6690
unsigned int> constant 4294967294>
    pr98255.c:20:21 start: pr98255.c:20:14 finish: pr98255.c:20:23>

At expansion time, that the 4294967294 index is not however
sign-expanded and so the program ends up loading from a bad memory
address.

Is "\t\x02\b"[4294967294] something the expander should sign-extend
or should SRA avoid re-using array_refs with indices which change when
sign-extended to a pointer width integer?

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The return n[0][3][-2U]; access is UB in the program, so if it would be
reached, it can do anything, but the important thing is that it is guarded with
while (g)
where g is always 0 during the exection of the program.
The sra bug is that it hoists the n[0][3][-2U] read from where it was in the IL
to the start of the function.  That is perhaps fine for memory reads that can't
trap (are within the bounds of the object), though even for those it might not
be beneficial from optimization POV (higher register pressure), but for memory
references for which tree_could_trap_p is true as in this case, they shouldn't
be hoisted in the IL before their guarding condition.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jamborm at gcc dot gnu.org]

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

--- Comment #5 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Right, the issue is that SRA depends on get_ref_base_and_extent to figure out
what is being accessed (and so whether it is safe) and that function believes
the load is safely from within the array.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
get_ref_base_and_extent is not the right API to check for the UBs caused by out
of bounds accesses, tree_could_trap_p is.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jamborm at gcc dot gnu.org]

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

--- Comment #7 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Even our constant folding thinks the unsigned expression wraps around.  If I
tell SRA to fold the expression if the base is a string_cst, the invalid
dereference is avoided.  My experiment was (I am not proposing this, but it
illustrates the point):

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index d177f1ba11c..d33c0ab63f7 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -99,6 +99,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dbgcnt.h"
 #include "builtins.h"
 #include "tree-sra.h"
+#include "gimple-fold.h"


 /* Enumeration of all aggregate reductions we can do.  */
@@ -1696,6 +1697,14 @@ build_ref_for_model (location_t loc, tree base,
HOST_WIDE_INT offset,
   else
     { 
       tree res;
+      if (TREE_CODE (base) == STRING_CST)
+       {
+         res = build_ref_for_offset (loc, base, offset, model->reverse,
+                                     model->type, gsi, insert_after);
+         res = fold_const_aggregate_ref (res);
+         return res;
+       }
+      
       if (model->grp_same_access_path
          && !TREE_THIS_VOLATILE (base)
          && (TYPE_ADDR_SPACE (TREE_TYPE (base))

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
503                     poly_offset_int woffset
504                       = wi::sext (wi::to_poly_offset (index)
505                                   - wi::to_poly_offset (low_bound),
506                                   TYPE_PRECISION (TREE_TYPE (index)));
in get_ref_base_and_extent indeed looks incorrect to me, for precisions smaller
than precision of pointer (or is that sizetype) I think we need to sign or zero
extend based on whether index has signed or unsigned type.
For arrays with zero low_bound I think what get_inner_reference does is right,
in particular:
            offset = size_binop (PLUS_EXPR, offset,
                                 size_binop (MULT_EXPR,
                                             fold_convert (sizetype, index),
                                             unit_size));
For non-zero low_bound, it does:
            if (! integer_zerop (low_bound))
              index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
                                   index, low_bound);
before that and I'm surprised that it assumes index and low_bound will be
compatible types.  But perhaps they are in the languages that do support
non-zero low bounds.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #8)
> 503			poly_offset_int woffset
> 504			  = wi::sext (wi::to_poly_offset (index)
> 505				      - wi::to_poly_offset (low_bound),
> 506				      TYPE_PRECISION (TREE_TYPE (index)));
> in get_ref_base_and_extent indeed looks incorrect to me, for precisions
> smaller than precision of pointer (or is that sizetype) I think we need to
> sign or zero extend based on whether index has signed or unsigned type.
> For arrays with zero low_bound I think what get_inner_reference does is
> right, in particular:
>             offset = size_binop (PLUS_EXPR, offset,
>                                  size_binop (MULT_EXPR,
>                                              fold_convert (sizetype, index),
>                                              unit_size));
> For non-zero low_bound, it does:
>             if (! integer_zerop (low_bound))
>               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
>                                    index, low_bound);
> before that and I'm surprised that it assumes index and low_bound will be
> compatible types.  But perhaps they are in the languages that do support
> non-zero low bounds.

Note all the above "mess" is due to FEs behaving oddly, notably different
from just interpreting the index as-is (appropriately sign or zero-extending
it to sizetype for the sizetype offset compute).  The odd sign-extension
is from gb48e22b2bd02

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jamborm at gcc dot gnu.org]

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

--- Comment #10 from Martin Jambor <jamborm at gcc dot gnu.org> ---
OK, adding an additional check whether tree_could_trap_p is of course easy. 
I'll wait a little while if the discussion about get_ref_base_and_extent
perhaps leads to a different solution but if not, I will prepare a patch.

Also, please disregard my comment #7, even though it shows that SRA can do
better by folding away the reference (and that works), it only shows that
fold_const_aggregate_ref can deal with simple MEM_REFs with sane offsets, not
arrays into strings with negative index.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #9)
> (In reply to Jakub Jelinek from comment #8)
> > 503			poly_offset_int woffset
> > 504			  = wi::sext (wi::to_poly_offset (index)
> > 505				      - wi::to_poly_offset (low_bound),
> > 506				      TYPE_PRECISION (TREE_TYPE (index)));
> > in get_ref_base_and_extent indeed looks incorrect to me, for precisions
> > smaller than precision of pointer (or is that sizetype) I think we need to
> > sign or zero extend based on whether index has signed or unsigned type.
> > For arrays with zero low_bound I think what get_inner_reference does is
> > right, in particular:
> >             offset = size_binop (PLUS_EXPR, offset,
> >                                  size_binop (MULT_EXPR,
> >                                              fold_convert (sizetype, index),
> >                                              unit_size));
> > For non-zero low_bound, it does:
> >             if (! integer_zerop (low_bound))
> >               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
> >                                    index, low_bound);
> > before that and I'm surprised that it assumes index and low_bound will be
> > compatible types.  But perhaps they are in the languages that do support
> > non-zero low bounds.
> 
> Note all the above "mess" is due to FEs behaving oddly, notably different
> from just interpreting the index as-is (appropriately sign or zero-extending
> it to sizetype for the sizetype offset compute).  The odd sign-extension
> is from gb48e22b2bd02

Possibly wi::sext(..., TYPE_PRECISION (sizetype)) is what we want.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Yeah, exactly that change I had in mind too.
The question is what it will mean to Ada.
In any case, from the get_inner_reference code I assume that either low_bound
is zero and then index can have any type which is then cast to sizetype before
using further, or low_bound is variable or non-zero constant and in that case
the FE needs to ensure the indexes have type compatible with the type of the
low bound.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 50021
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50021&action=edit
gcc11-pr98255.patch

The full patch would be I think this.  Am going to bootstrap/regtest it just to
see what it breaks or fixes.

[Bug tree-optimization/98255] [10/11 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:e287a2a11d7958e5d9f7c6172e59cc83495e393a

commit r11-6852-ge287a2a11d7958e5d9f7c6172e59cc83495e393a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Fri Jan 22 11:42:03 2021 +0100

    on ARRAY_REFs sign-extend offsets only from sizetype's precision [PR98255]

    As discussed in the PR, the problem here is that the routines changed in
    this patch sign extend the difference of index and low_bound from the
    precision of the index, so e.g. when index is unsigned int and contains
    value -2U, we treat it as index -2 rather than 0x00000000fffffffeU on
64-bit
    arches.
    On the other hand, get_inner_reference which is used during expansion,
does:
                if (! integer_zerop (low_bound))
                  index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
                                       index, low_bound);

                offset = size_binop (PLUS_EXPR, offset,
                                     size_binop (MULT_EXPR,
                                                 fold_convert (sizetype,
index),
                                                 unit_size));
    which effectively requires that either low_bound is constant 0 and then
    index in ARRAY_REFs can be arbitrary type which is then sign or zero
    extended to sizetype, or low_bound is something else and then index and
    low_bound must have compatible types and it is still converted afterwards
to
    sizetype and from there then a few lines later:
    expr.c-  if (poly_int_tree_p (offset))
    expr.c-    {
    expr.c:      poly_offset_int tem = wi::sext (wi::to_poly_offset (offset),
    expr.c-                               TYPE_PRECISION (sizetype));
    The following patch makes those routines match what get_inner_reference is
    doing.

    2021-01-22  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98255
            * tree-dfa.c (get_ref_base_and_extent): For ARRAY_REFs, sign
            extend index - low_bound from sizetype's precision rather than
index
            precision.
            (get_addr_base_and_unit_offset_1): Likewise.
            * tree-ssa-sccvn.c (ao_ref_init_from_vn_reference): Likewise.
            * gimple-fold.c (fold_const_aggregate_ref_1): Likewise.

            * gcc.dg/pr98255.c: New test.

[Bug tree-optimization/98255] [10 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[10/11 Regression] wrong    |[10 Regression] wrong code
                   |code at -Os and above with  |at -Os and above with -fPIC
                   |-fPIC on                    |on x86_64-pc-linux-gnu
                   |x86_64-pc-linux-gnu         |

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk.  Not sure what to do in 10.3.

[Bug tree-optimization/98255] [10 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #15)
> Fixed on the trunk.  Not sure what to do in 10.3.

Same, if there's no fallout.

[Bug tree-optimization/98255] [10 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:8e28ebfa5a359942752ca9f5e774cadd1878005a

commit r10-9316-g8e28ebfa5a359942752ca9f5e774cadd1878005a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Fri Jan 22 11:42:03 2021 +0100

    on ARRAY_REFs sign-extend offsets only from sizetype's precision [PR98255]

    As discussed in the PR, the problem here is that the routines changed in
    this patch sign extend the difference of index and low_bound from the
    precision of the index, so e.g. when index is unsigned int and contains
    value -2U, we treat it as index -2 rather than 0x00000000fffffffeU on
64-bit
    arches.
    On the other hand, get_inner_reference which is used during expansion,
does:
                if (! integer_zerop (low_bound))
                  index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
                                       index, low_bound);

                offset = size_binop (PLUS_EXPR, offset,
                                     size_binop (MULT_EXPR,
                                                 fold_convert (sizetype,
index),
                                                 unit_size));
    which effectively requires that either low_bound is constant 0 and then
    index in ARRAY_REFs can be arbitrary type which is then sign or zero
    extended to sizetype, or low_bound is something else and then index and
    low_bound must have compatible types and it is still converted afterwards
to
    sizetype and from there then a few lines later:
    expr.c-  if (poly_int_tree_p (offset))
    expr.c-    {
    expr.c:      poly_offset_int tem = wi::sext (wi::to_poly_offset (offset),
    expr.c-                               TYPE_PRECISION (sizetype));
    The following patch makes those routines match what get_inner_reference is
    doing.

    2021-01-22  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/98255
            * tree-dfa.c (get_ref_base_and_extent): For ARRAY_REFs, sign
            extend index - low_bound from sizetype's precision rather than
index
            precision.
            (get_addr_base_and_unit_offset_1): Likewise.
            * tree-ssa-sccvn.c (ao_ref_init_from_vn_reference): Likewise.
            * gimple-fold.c (fold_const_aggregate_ref_1): Likewise.

            * gcc.dg/pr98255.c: New test.

[Bug tree-optimization/98255] [10 Regression] wrong code at -Os and above with -fPIC on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
         Resolution|---                         |FIXED

--- Comment #18 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 10.3+ too.