[Bug tree-optimization/26726] New: -fivopts producing out of bounds array refs

[Bug tree-optimization/26726] New: -fivopts producing out of bounds array refs

[mueller at gcc dot gnu dot org]

=== Cut ===
struct
QValueList
{
    QValueList()
    {
        sh = new int;
    }
   QValueList& operator+= ( QValueList&);
   int* sh;
};

void
queryIconsByContext()
{
    QValueList iconlist[8];
    QValueList iconlistResult;
    for (int i=0; i<8; i++)
            iconlistResult+=iconlist[i];

}
=== Cut ===

g++ -O2 
produces this SSA form after ivopts branch:

...
  ivtmp.38_37 = ivtmp.38_1 + 4B;
  if (ivtmp.38_37 != &iconlist[9]) goto <L10>; else goto <L2>;
...

taking address of the 10th iconlist element is out of bounds access.


-- 
           Summary: -fivopts producing out of bounds array refs
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mueller at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-03-17 11:39 -------
Reduced testcase:

struct QValueList {
    QValueList() { sh = new int; }
    void foo();
    int* sh;
};

void queryIconsByContext()
{
    QValueList iconlist[8];
    iconlist[7].foo();
}

ivopts generates

<bb 2>:
  ivtmp.35_3 = &iconlist[1];

  # ivtmp.35_12 = PHI <ivtmp.35_17(4), ivtmp.35_3(2)>;
<L0>:;
  D.2027_8 = operator new (4);
  D.2028_9 = (int *) D.2027_8;
  D.2072_4 = (int * *) &iconlist[0];
  D.2073_7 = (int * *) ivtmp.35_12;
  D.2074_21 = D.2072_4 + D.2073_7;
  D.2075_22 = -&iconlist;
  D.2076_23 = (int * *) D.2075_22;
  MEM[base: D.2074_21, index: D.2076_23, offset: -4B] = D.2028_9;
  ivtmp.35_17 = ivtmp.35_12 + 4B;
  if (ivtmp.35_17 != &iconlist[9]) goto <L5>; else goto <L2>;

<L5>:; 
  goto <bb 3> (<L0>);

both using -&iconlist (!?) as index and and -4 as offset for TMR looks weird
here.  Referencing &iconlist[9] is sort of wrong-code.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2006-03-17 11:39:44
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[mueller at gcc dot gnu dot org]

------- Comment #2 from mueller at gcc dot gnu dot org  2006-03-17 12:40 -------
one possible workaround would be to lower the ARRAY_REF's to indirect mem refs,
which I don't track


-- 

mueller at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.2.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2006-03-17 12:55 -------
For your warning patch another option is to simply only warn in either the
first or the second VRP pass, not in the third which is the only one run after
loop optimizations.  Also you could ignore ADDR_EXPR (ARRAY_REF (...)) as these
are
not reading/writing to the memory.  Instead for

 D.1234_2 = &a[i];
 *D.1234_2 = j;

warn at the point of the INDIRECT_REF and lookup the DEF for D.1234_2 to
check if it is defined as &ARRAY_REF (...)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-03-17 13:00 -------
Now I noticed IVOPTs generates a TMR with base == &iconlist[1] + ivtmp,
offset -&iconlist[0] and offset -4B (ivtmp being &iconlist[0] initially).
Which boils down to using simply *ivtmp instead of a TMR.  Funny.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2006-03-17 13:17 -------
Simpler testcase:

struct Foo {
  Foo() : s(1) {}
  int s;
};
void foo(Foo&);
void bar(void)
{
  Foo x[4];
  foo(x[0]);
}

<bb 0>:
  ivtmp.34 = &x[1];

<L0>:;
  D.1822 = (int *) &x[0];
  D.1825 = -&x;
  MEM[base: D.1822 + (int *) ivtmp.34, index: (int *) D.1825, offset: -4B] = 1;
  ivtmp.34 = ivtmp.34 + 4B;
  if (ivtmp.34 != &x[5]) goto <L0>; else goto <L2>;


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

Re: [Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[Daniel Berlin]

On Fri, 2006-03-17 at 12:40 +0000, mueller at gcc dot gnu dot org wrote:
> 
> ------- Comment #2 from mueller at gcc dot gnu dot org  2006-03-17 12:40 -------
> one possible workaround would be to lower the ARRAY_REF's to indirect mem refs,
> which I don't track
> 
> 

Uh, no.
We are in fact, trying to do the exact opposite in the future (keep
things array ref as long as possible)

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[dberlin at dberlin dot org]

------- Comment #6 from dberlin at gcc dot gnu dot org  2006-03-17 13:31 -------
Subject: Re:  -fivopts producing out of bounds
        array refs

On Fri, 2006-03-17 at 12:40 +0000, mueller at gcc dot gnu dot org wrote:
> 
> ------- Comment #2 from mueller at gcc dot gnu dot org  2006-03-17 12:40 -------
> one possible workaround would be to lower the ARRAY_REF's to indirect mem refs,
> which I don't track
> 
> 

Uh, no.
We are in fact, trying to do the exact opposite in the future (keep
things array ref as long as possible)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2006-04-27 15:47 -------
One thing is, that find_interesting_uses_address () produces bases that look
like &(&a[0])->s.  I.e. they are not folded during IV base insertion via

      if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
          || zero_p (step))
        goto fail;

Also we don't see that *&a[0] is an ARRAY_REF in idx_find_step, which may cause
other problems.

Another problem is that we record both

(const Foo*)&a[0]

and

&a[0]

as biv's which confuses IVOPTs a lot.

Stripping useless type conversions during biv discovery and folding after the
substitution above fixes the two problems.  What remains is the use of an
out-of-bound array index and a (useless) offset:

<bb 2>:
  ivtmp.39_2 = &x[1];

  # ivtmp.39_4 = PHI <ivtmp.39_1(4), ivtmp.39_2(2)>;
<L0>:;
  D.2068_10 = (int *) ivtmp.39_4;
  MEM[base: D.2068_10, offset: -4B]{this->s} = 1;
  ivtmp.39_1 = ivtmp.39_4 + 4B;
  if (ivtmp.39_1 != &x[5]) goto <L5>; else goto <L2>;

here I do not see how IVOPTs decided that using &x[1] as base is better
than &x[0] (well, the cost for the former is 1 while for the latter is 2(!?)

I have a patch for the first two problems in testing.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2006-04-27 15:59 -------
The offset causes the assembler to be sub-optimal:

.LCFI2:
        leal    -12(%ebp), %eax
        leal    4(%ebp), %edx
        .p2align 4,,7
.L2:
        movl    $1, -4(%eax)
        addl    $4, %eax
        cmpl    %edx, %eax
        jne     .L2

and I can imagine on auto-decrement targets it would be even worse (though
I didn't check).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #9 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-27 16:02 -------
Subject: Re:  -fivopts producing out of bounds array refs

> One thing is, that find_interesting_uses_address () produces bases that look
> like &(&a[0])->s.  I.e. they are not folded during IV base insertion via
> 
>       if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
>           || zero_p (step))
>         goto fail;
> 
> Also we don't see that *&a[0] is an ARRAY_REF in idx_find_step, which may cause
> other problems.
> 
> Another problem is that we record both
> 
> (const Foo*)&a[0]
> 
> and
> 
> &a[0]
> 
> as biv's which confuses IVOPTs a lot.
> 
> Stripping useless type conversions during biv discovery and folding after the
> substitution above fixes the two problems.

I also have some patches for similar problems (in killloop-branch),
unfortunately
they mostly depend on http://gcc.gnu.org/ml/gcc-patches/2006-03/msg00345.html
that seems hopelessly stuck.

> What remains is the use of an
> out-of-bound array index and a (useless) offset:
> 
> <bb 2>:
>   ivtmp.39_2 = &x[1];
> 
>   # ivtmp.39_4 = PHI <ivtmp.39_1(4), ivtmp.39_2(2)>;
> <L0>:;
>   D.2068_10 = (int *) ivtmp.39_4;
>   MEM[base: D.2068_10, offset: -4B]{this->s} = 1;
>   ivtmp.39_1 = ivtmp.39_4 + 4B;
>   if (ivtmp.39_1 != &x[5]) goto <L5>; else goto <L2>;
> 
> here I do not see how IVOPTs decided that using &x[1] as base is better
> than &x[0] (well, the cost for the former is 1 while for the latter is 2(!?)

Welcome to the wonderful world of cost arithmetics :-) x86 backend
pretends that more complicated memory addressing modes are cheaper,
in order to persuade CSE to create them.  Thus, given several equally
costly ways how to express a memory reference, ivopts will choose the
most complicated one.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenther at suse dot de]

------- Comment #10 from rguenther at suse dot de  2006-04-27 16:09 -------
Subject: Re:  -fivopts producing out of bounds
 array refs

On Thu, 27 Apr 2006, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:

> > Stripping useless type conversions during biv discovery and folding after the
> > substitution above fixes the two problems.
> 
> I also have some patches for similar problems (in killloop-branch),
> unfortunately
> they mostly depend on http://gcc.gnu.org/ml/gcc-patches/2006-03/msg00345.html
> that seems hopelessly stuck.

I thought there was consensus and approval on the generic parts.  Maybe
it's time to ping these again, as they were clearly submitted before 
stage3.

> > What remains is the use of an
> > out-of-bound array index and a (useless) offset:
> > 
> > <bb 2>:
> >   ivtmp.39_2 = &x[1];
> > 
> >   # ivtmp.39_4 = PHI <ivtmp.39_1(4), ivtmp.39_2(2)>;
> > <L0>:;
> >   D.2068_10 = (int *) ivtmp.39_4;
> >   MEM[base: D.2068_10, offset: -4B]{this->s} = 1;
> >   ivtmp.39_1 = ivtmp.39_4 + 4B;
> >   if (ivtmp.39_1 != &x[5]) goto <L5>; else goto <L2>;
> > 
> > here I do not see how IVOPTs decided that using &x[1] as base is better
> > than &x[0] (well, the cost for the former is 1 while for the latter is 2(!?)
> 
> Welcome to the wonderful world of cost arithmetics :-) x86 backend
> pretends that more complicated memory addressing modes are cheaper,
> in order to persuade CSE to create them.  Thus, given several equally
> costly ways how to express a memory reference, ivopts will choose the
> most complicated one.

*sigh* :/

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[patchapp at dberlin dot org]

------- Comment #11 from patchapp at dberlin dot org  2006-04-28 14:35 -------
Subject: Bug number PR26726

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-04/msg01095.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug tree-optimization/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2006-05-01 15:07 -------
Subject: Bug 26726

Author: rguenth
Date: Mon May  1 15:07:25 2006
New Revision: 113414

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113414
Log:
2006-05-01  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/26726
        * tree-ssa-loop-ivopts.c (idx_find_step): Mark source of the
        problem ...
        (find_interesting_uses_address): ... we work around here
        by folding INDIRECT_REFs in the substituted base.

        * g++.dg/tree-ssa/ivopts-1.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/tree-ssa/ivopts-1.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2006-05-01 15:09 -------
This is now a target specific problem, on i?86 and x86_64 we are left with an
offset of -4B and so referencing &a[5] in the exit condition.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |target
 GCC target triplet|                            |i?86-*-* x86_64-*-*


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[uros at kss-loka dot si]

------- Comment #14 from uros at kss-loka dot si  2006-05-13 08:46 -------
(In reply to comment #13)
> This is now a target specific problem, on i?86 and x86_64 we are left with an
> offset of -4B and so referencing &a[5] in the exit condition.
> 
This is PR target/24669.


-- 

uros at kss-loka dot si changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |24669


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[pinskia at gcc dot gnu dot org]

------- Comment #15 from pinskia at gcc dot gnu dot org  2007-06-04 05:36 -------
One should note that:
/* { dg-final { scan-tree-dump-not "offset: -4B" "ivopts" { xfail i?86-*-*
x86_64-*-* } } } */

Will not match any more since switching over offset to sizetype.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[ubizjak at gmail dot com]

------- Comment #16 from ubizjak at gmail dot com  2007-10-26 10:06 -------
(In reply to comment #14)

> > This is now a target specific problem, on i?86 and x86_64 we are left with an
> > offset of -4B and so referencing &a[5] in the exit condition.
> > 
> This is PR target/24669.

Hm, the testcase in PR 24669 was fixed by adjusting x86 costs, but we still
generate offset of -4 bytes here. There are also some relevant comments in PR
27707 (dupe?).

This issue with -4 offset is annoying because code size of offsetted load insn
is huge:

   f:   c7 40 fc 01 00 00 00    movl   $0x1,-0x4(%eax)

BTW: The issue in Comment #15 is now fixed in the testsuite.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |27707
              nThis|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[bonzini at gnu dot org]

------- Comment #17 from bonzini at gnu dot org  2007-10-29 10:05 -------
> This issue with -4 offset is annoying because code size of offsetted load insn
> is huge:
>
>    f:   c7 40 fc 01 00 00 00    movl   $0x1,-0x4(%eax)

-0x4(%eax) is 2 bytes more than (%eax), where IIRC it would be "a3 01 00 00
00", and only one byte more than any other non-offsetted load insn.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[ubizjak at gmail dot com]

------- Comment #18 from ubizjak at gmail dot com  2007-10-29 13:22 -------
Perhaps this analysis will help someone...:

We start with following loop:

void bar() ()
{
  unsigned int ivtmp.19;
  int pretmp.14;
  struct Foo * pretmp.13;
  struct Foo x[4];
  int D.1669;
  struct Foo * D.1668;

<bb 2>:

<bb 3>:
  # ivtmp.19_2 = PHI <ivtmp.19_1(4), 4(2)>
  # D.1669_34 = PHI <D.1669_7(4), 3(2)>
  # D.1668_33 = PHI <D.1668_6(4), &x[0](2)>
  D.1668_33->s = 1;
  D.1668_6 = D.1668_33 + 4;
  D.1669_7 = D.1669_34 + -1;
  ivtmp.19_1 = ivtmp.19_2 - 1;
  if (ivtmp.19_1 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

...

General ivs in BB are found in tree-ssa-loop-ivopts.c via find_givs_in_bb().

find_givs_in_stmt() is entered with "D.1668_6 = D.1668_33 + 4". For this stmt,
find_givs_in_stmt_scev() returns iv.base = &x[1] and iv.step = 4.

Digging a bit further, find_givs_in_stmt_scev() calls simple_iv() in
tree-scalar-evolution.c() to determine iv base and step. simple_iv() is called
with op = "D.1668_33 + 4" and this op is furhter passed to
analyze_scalar_evolution_in_loop(). This function returns "{&x[1], +, 4}_1".

analyze_scalar_evolution_in_loop() calls analyze_scalar_evolution() with
"D.1668_33 + 4". This expression is further passed to
analyze_scalar_evolution_1(). As the expression is not SSA_NAME, it is passed
to interpret_rhs_modify_stmt() as POINTER_PLUS_EXPR.

interpret_rhs_modify_stmt() decomposes expression into "{&x[0], +, 4}_1" and
"4". These two are summed in chrec_fold_plus() in tree-chrec.c to the final
"{&x[1], +, 4}_1" expression.

This results in:

  struct FooD.1649 xD.1666[4];
  intD.2 D.1669;
  struct FooD.1649 * D.1668;

  ivtmp.24D.1709_11 = (unsigned intD.6) &xD.1666[1];


  # BLOCK 3 freq:8000
  ...
  MEM[index: ivtmp.24D.1709_9, offset: 0x0fffffffc]{D.1668->sD.1653} = 1;
  ivtmp.24D.1709_10 = ivtmp.24D.1709_9 + 4;
  ...

and on i686:

        leal    -12(%ebp), %eax
        leal    4(%ebp), %edx
.L2:
        movl    $1, -4(%eax)
        addl    $4, %eax
        cmpl    %edx, %eax
        jne     .L2
        ...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[ubizjak at gmail dot com]

------- Comment #19 from ubizjak at gmail dot com  2008-01-27 17:52 -------
The problem in comment #13 is fixed for 4.3.0 by the fix for PR 34771.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |34771
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726

[Bug target/26726] -fivopts producing out of bounds array refs

[ubizjak at gmail dot com]

------- Comment #20 from ubizjak at gmail dot com  2008-01-27 17:53 -------
(In reply to comment #19)
> The problem in comment #13 is fixed for 4.3.0 by the fix for PR 34771.

Oops, PR 34711.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|34771                       |34711


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726