[Bug rtl-optimization/48702] New: optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[Bug rtl-optimization/48702] New: optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[mariah.lenox at gmail dot com]

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

           Summary: optimization regression with gcc-4.6 on
                    x86_64-unknown-linux-gnu
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: mariah.lenox@gmail.com


/* optimization regression with gcc-4.6.0 on x86_64-unknown-linux-gnu

% gcc-4.6.0 -O2 -o foo foo.c
% foo
% 1
%
% gcc-4.6.0 -O1 -o foo foo.c
% foo
% 4
%
% gcc-4.5.1 -O2 -o foo foo.c
% foo
% 4

% gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/local/gcc-4.6.0/x86_64-Linux-core2-fc/libexec/gcc/x86_64-unknown-linux-gnu/4.6.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /usr/local/gcc-4.6.0/src/gcc-4.6.0/configure
--enable-languages=c,c++,fortran --with-gnu-as
--with-gnu-as=/usr/local/binutils-2.21/x86_64-Linux-core2-fc-gcc-4.5.1-rh/bin/as
--with-gnu-ld
--with-ld=/usr/local/binutils-2.21/x86_64-Linux-core2-fc-gcc-4.5.1-rh/bin/ld
--with-gmp=/usr/local/mpir-2.3.0/x86_64-Linux-core2-fc-gcc-4.5.1-rh
--with-mpfr=/usr/local/mpfr-3.0.0/x86_64-Linux-core2-fc-mpir-2.3.0-gcc-4.5.1-rh
--with-mpc=/usr/local/mpc-0.9/x86_64-Linux-core2-fc-mpir-2.3.0-mpfr-3.0.0-gcc-4.5.1-rh
--prefix=/usr/local/gcc-4.6.0/x86_64-Linux-core2-fc
Thread model: posix
gcc version 4.6.0 (GCC) 
%

*/

#include  <stdio.h>

#define LEN 4  

void unpack(int  array[LEN])
{
int ii, val;

val = 1;
for (ii = 0; ii < LEN; ii++) {
  array[ii] = val % 2;
  val = val / 2;
}

return;
}

int  pack(int  array[LEN])
{
int ans, ii;

ans = 0;
for (ii = LEN-1; ii >= 0; ii--) {
  ans = 2 * ans + array[ii];
}

return ans;
}

int  foo()
{
int temp, ans;
int array[LEN];

unpack(array);
temp = array[0];
array[0] = array[2];
array[2] = temp;
ans = pack(array);
return ans;
}

int main(void)
{
int val;

val = foo();
printf("%d\n", val);

return 0; 
}

[Bug rtl-optimization/48702] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.04.20 14:28:27
      Known to work|                            |4.7.0
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-20 14:28:27 UTC ---
Confirmed.  Seems to work on trunk.

The following fails at -O1:

extern void abort (void);

#define LEN 4

static inline void unpack(int  array[LEN])
{
  int ii, val;
  val = 1;
  for (ii = 0; ii < LEN; ii++) {
      array[ii] = val % 2;
      val = val / 2;
  }
}

static inline int  pack(int  array[LEN])
{
  int ans, ii;
  ans = 0;
  for (ii = LEN-1; ii >= 0; ii--) {
      ans = 2 * ans + array[ii];
  }
  return ans;
}

int __attribute__((noinline))
foo()
{
  int temp, ans;
  int array[LEN];
  unpack(array);
  temp = array[0];
  array[0] = array[2];
  array[2] = temp;
  ans = pack(array);
  return ans;
}

int main(void)
{
  int val;
  val = foo();
  if (val != 4)
    abort ();
  return 0;
}

[Bug rtl-optimization/48702] [4.6 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
   Target Milestone|---                         |4.6.1
            Summary|optimization regression     |[4.6 Regression]
                   |with gcc-4.6 on             |optimization regression
                   |x86_64-unknown-linux-gnu    |with gcc-4.6 on
                   |                            |x86_64-unknown-linux-gnu

[Bug rtl-optimization/48702] [4.6 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-20 14:38:51 UTC ---
DSE2 kills the stores of the shuffle

temp = array[0];
array[0] = array[2];
array[2] = temp;

likely being confused about the loops use.  Mine.

[Bug rtl-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|4.7.0                       |
            Summary|[4.6 Regression]            |[4.6/4.7 Regression]
                   |optimization regression     |optimization regression
                   |with gcc-4.6 on             |with gcc-4.6 on
                   |x86_64-unknown-linux-gnu    |x86_64-unknown-linux-gnu
      Known to fail|                            |4.7.0

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-20 15:08:32 UTC ---
I have a patch that makes it fail on trunk as well.  IVOPTs generates

  for (p = &a; p != &a - 3; --p)
    *(p + 3) = ...

and alias analysis doesn't like this invalid pointer.

[Bug rtl-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-21 10:48:34 UTC ---
Created attachment 24066
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24066
patch

Patch I am testing.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-21 11:05:09 UTC ---
Before the patch:

        movq    %rsp, %rdx
        leaq    -16(%rsp), %rcx
        movl    $0, %eax
.L5:
        addl    %eax, %eax
        addl    12(%rdx), %eax
        subq    $4, %rdx
        cmpq    %rcx, %rdx
        jne     .L5

after the patch:

        movl    $0, %edx
        movl    $0, %eax
.L5:
        addl    %eax, %eax
        addl    12(%rsp,%rdx), %eax
        subq    $4, %rdx
        cmpq    $-16, %rdx
        jne     .L5

not 100% clear which to prefer.

Alternatively alias-analysis can be dumbed down, never exploiting knowledge
of a constant offset added to a pointer before dereferencing it
(thus, ignoring the constant offset operand in MEM_REFs and TARGET_MEM_REFs).
FYI, the disambiguation that triggers is

  /* If only one reference is based on a variable, they cannot alias if
     the pointer access is beyond the extent of the variable access.
     (the pointer base cannot validly point to an offset less than zero
     of the variable).
     They also cannot alias if the pointer may not point to the decl.  */
  if ((TREE_CODE (base1) != TARGET_MEM_REF
       || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
      && !ranges_overlap_p (MAX (0, offset1p), -1, offset2p, max_size2))
    return false;

thus, for "the pointer base cannod validly point to an offset less than
zero" say that this only holds for ptr + constant offset, not ptr in
isolation.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rakdver at gcc dot gnu.org]

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

--- Comment #6 from Zdenek Dvorak <rakdver at gcc dot gnu.org> 2011-04-21 11:49:36 UTC ---
I think we rely on the assumption that pointer arithmetics satisfies the
restrictions of C standard (i.e., that the pointer is within a single memory
object) on more places than just this one.  So, if the code produced by ivopts
is indeed

for (p = &a; p != &a - 3; --p)
  *(p + 3) = ...

this could potentially cause other problems other than with alias analysis.

But, I would expect the code from ivopts to be rather

for (p = &a; ...; p = (pointer) ((unsigned) p - 1)
  *((pointer) ((unsigned) p + 3)) = ...

Which should be a valid code.  Is that the case? If so, fixing alias analysis
would be the proper solution.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-21 12:32:04 UTC ---
IVOPTs generates

  ivtmp.25_24 = (long unsigned int) &array;
  array.26_26 = (long unsigned int) &array;
  D.2769_27 = array.26_26 + 0x0fffffffffffffff0;

<bb 3>:
  # ans_21 = PHI <ans_16(4), 0(2)>
  # ivtmp.25_20 = PHI <ivtmp.25_19(4), ivtmp.25_24(2)>
  D.2741_10 = ans_21 * 2;
  D.2767_25 = (void *) ivtmp.25_20;
  D.2737_15 = MEM[(int *)D.2767_25 + 12B];
  ans_16 = D.2741_10 + D.2737_15;
  ivtmp.25_19 = ivtmp.25_20 - 4;
  if (ivtmp.25_19 != D.2769_27)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

thus, the addition of the constant offset does not happen in a separate
unsigned long computation but is (of course) folded into the (TARGET_)MEM_REF.

What now exposes this kind of bugs is that we 1) prefer to generate MEM_REFs
instead of equivalent TARGET_MEM_REFs, 2) do not completely give up on
TARGET_MEM_REFs in alias analysis.

I am somewhat sympathetic to treating indirect (TARGET_)MEM_REFs as opaque,
only looking at the final pointer that is dereferenced, not at the
pieces of the address computation.  We'd retain the case where two
such derefrences differ only in a constant offset.

I don't think that any pass interprets the address computation that is
implicit in a memory refrence in any way at the moment.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-21 12:39:10 UTC ---
(In reply to comment #7)
> IVOPTs generates
> 
>   ivtmp.25_24 = (long unsigned int) &array;
>   array.26_26 = (long unsigned int) &array;
>   D.2769_27 = array.26_26 + 0x0fffffffffffffff0;
> 
> <bb 3>:
>   # ans_21 = PHI <ans_16(4), 0(2)>
>   # ivtmp.25_20 = PHI <ivtmp.25_19(4), ivtmp.25_24(2)>
>   D.2741_10 = ans_21 * 2;
>   D.2767_25 = (void *) ivtmp.25_20;

Actually D.2767_25 is already the problem as it can point before &array.

>   D.2737_15 = MEM[(int *)D.2767_25 + 12B];

Here we assume that the memory reference happens only to array[3] or beyond,
as D.2767_25 is assumed to at least point to &array[0] but never to &array[-1].

Other passes could derive similar info for D.2767_25 given that points-to
analysis computes it points somewhere into array.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rakdver at kam dot mff.cuni.cz]

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

--- Comment #9 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-04-21 12:56:20 UTC ---
>   ivtmp.25_24 = (long unsigned int) &array;
>   array.26_26 = (long unsigned int) &array;
>   D.2769_27 = array.26_26 + 0x0fffffffffffffff0;
> 
> <bb 3>:
>   # ans_21 = PHI <ans_16(4), 0(2)>
>   # ivtmp.25_20 = PHI <ivtmp.25_19(4), ivtmp.25_24(2)>
>   D.2741_10 = ans_21 * 2;
>   D.2767_25 = (void *) ivtmp.25_20;
>   D.2737_15 = MEM[(int *)D.2767_25 + 12B];
>   ans_16 = D.2741_10 + D.2737_15;
>   ivtmp.25_19 = ivtmp.25_20 - 4;
>   if (ivtmp.25_19 != D.2769_27)
>     goto <bb 4>;
>   else
>     goto <bb 5>;
> 
> <bb 4>:
>   goto <bb 3>;

So the computation of the induction variable is performed in (long unsigned
int),
which should be safe.

> I am somewhat sympathetic to treating indirect (TARGET_)MEM_REFs as opaque,
> only looking at the final pointer that is dereferenced, not at the
> pieces of the address computation.  We'd retain the case where two
> such derefrences differ only in a constant offset.
> 
> I don't think that any pass interprets the address computation that is
> implicit in a memory refrence in any way at the moment.

We definitely should decide on and document the precise semantics of
(TARGET_)MEM_REFs.
One possibility is to give no guarantees on the computations (i.e., treat them
as opaque);
this is easy for ivopts, but possibly removes some useful information (at least
for MEM_REFs,
I would not do that).  On the other hand, if we decide to enforce the
restrictions as for
the pointer arithmetics, we should also say e.g. in what way are the parts of
the address
computation in TARGET_MEM_REFs associated, as that may make a difference.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenther at suse dot de]

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

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> 2011-04-21 13:05:54 UTC ---
On Thu, 21 Apr 2011, rakdver at kam dot mff.cuni.cz wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48702
> 
> --- Comment #9 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-04-21 12:56:20 UTC ---
> >   ivtmp.25_24 = (long unsigned int) &array;
> >   array.26_26 = (long unsigned int) &array;
> >   D.2769_27 = array.26_26 + 0x0fffffffffffffff0;
> > 
> > <bb 3>:
> >   # ans_21 = PHI <ans_16(4), 0(2)>
> >   # ivtmp.25_20 = PHI <ivtmp.25_19(4), ivtmp.25_24(2)>
> >   D.2741_10 = ans_21 * 2;
> >   D.2767_25 = (void *) ivtmp.25_20;
> >   D.2737_15 = MEM[(int *)D.2767_25 + 12B];
> >   ans_16 = D.2741_10 + D.2737_15;
> >   ivtmp.25_19 = ivtmp.25_20 - 4;
> >   if (ivtmp.25_19 != D.2769_27)
> >     goto <bb 4>;
> >   else
> >     goto <bb 5>;
> > 
> > <bb 4>:
> >   goto <bb 3>;
> 
> So the computation of the induction variable is performed in (long unsigned
> int),
> which should be safe.
> 
> > I am somewhat sympathetic to treating indirect (TARGET_)MEM_REFs as opaque,
> > only looking at the final pointer that is dereferenced, not at the
> > pieces of the address computation.  We'd retain the case where two
> > such derefrences differ only in a constant offset.
> > 
> > I don't think that any pass interprets the address computation that is
> > implicit in a memory refrence in any way at the moment.
> 
> We definitely should decide on and document the precise semantics of
> (TARGET_)MEM_REFs.
> One possibility is to give no guarantees on the computations (i.e., treat them
> as opaque);
> this is easy for ivopts, but possibly removes some useful information (at least
> for MEM_REFs,
> I would not do that).  On the other hand, if we decide to enforce the
> restrictions as for
> the pointer arithmetics, we should also say e.g. in what way are the parts of
> the address
> computation in TARGET_MEM_REFs associated, as that may make a difference.

What we lose when we treat them as opaque is disambiguating the load of i
in

int i;
int foo (int *p) { i = 0; *(p + 4) = 1; return i; }

where *(p + 4) is MEM[p, 16] where we see that p + 16 != &i for any
valid (in the C sense) pointer p.

That would indeed be not so nice.

Richard.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rakdver at kam dot mff.cuni.cz]

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

--- Comment #11 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-04-21 13:34:29 UTC ---
> > > I am somewhat sympathetic to treating indirect (TARGET_)MEM_REFs as opaque,
> > > only looking at the final pointer that is dereferenced, not at the
> > > pieces of the address computation.  We'd retain the case where two
> > > such derefrences differ only in a constant offset.
> > > 
> > > I don't think that any pass interprets the address computation that is
> > > implicit in a memory refrence in any way at the moment.
> > 
> > We definitely should decide on and document the precise semantics of
> > (TARGET_)MEM_REFs.
> > One possibility is to give no guarantees on the computations (i.e., treat them
> > as opaque);
> > this is easy for ivopts, but possibly removes some useful information (at least
> > for MEM_REFs,
> > I would not do that).  On the other hand, if we decide to enforce the
> > restrictions as for
> > the pointer arithmetics, we should also say e.g. in what way are the parts of
> > the address
> > computation in TARGET_MEM_REFs associated, as that may make a difference.
> 
> What we lose when we treat them as opaque is disambiguating the load of i
> in
> 
> int i;
> int foo (int *p) { i = 0; *(p + 4) = 1; return i; }
> 
> where *(p + 4) is MEM[p, 16] where we see that p + 16 != &i for any
> valid (in the C sense) pointer p.
> 
> That would indeed be not so nice.

what about always interpreting the computations in the type of the base of
MEM_REF
(allowing non-pointers as the base)?  So both of the following forms would be
valid:

1)
int *p;

MEM[p + 16]
which is equivalent to *(p POINTER_PLUS 16)

2)
int *p;
unsigned v = (unsigned) p;

MEM[v + 16]
equivalent to *(int *) (v + 16)

The form 1) would be default, and contains the information needed by alias
analysis.
The form 2) would only be generated by optimizations that are unable to decide
whether
  the pointer arithmetics form is valid (ivopts), and would be treated as
opaque by
  alias analysis.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #12 from davidxl <xinliangli at gmail dot com> 2011-04-21 16:22:03 UTC ---
(In reply to comment #3)
> I have a patch that makes it fail on trunk as well.  IVOPTs generates
> 
>   for (p = &a; p != &a - 3; --p)
>     *(p + 3) = ...
> 
> and alias analysis doesn't like this invalid pointer.


I wonder why ivopt does not select the iv candidate whose base is &a+3.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-12 10:52:54 UTC ---
(In reply to comment #12)
> (In reply to comment #3)
> > I have a patch that makes it fail on trunk as well.  IVOPTs generates
> > 
> >   for (p = &a; p != &a - 3; --p)
> >     *(p + 3) = ...
> > 
> > and alias analysis doesn't like this invalid pointer.
> 
> 
> I wonder why ivopt does not select the iv candidate whose base is &a+3.

I think that one is not in the list of initial candidates.

I think for that sake we would want to add stripped &base + object size (+ 1?)
(if we know it) as IV candidate iff iv->step is negative, iff iv->step is
positive continue to add &base.

I don't like the alias oracle fixups too much, but I guess we have to
benchmark both alternatives.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #14 from davidxl <xinliangli at gmail dot com> 2011-05-17 17:17:11 UTC ---
(In reply to comment #13)
> (In reply to comment #12)
> > (In reply to comment #3)
> > > I have a patch that makes it fail on trunk as well.  IVOPTs generates
> > > 
> > >   for (p = &a; p != &a - 3; --p)
> > >     *(p + 3) = ...
> > > 
> > > and alias analysis doesn't like this invalid pointer.
> > 
> > 
> > I wonder why ivopt does not select the iv candidate whose base is &a+3.
> 
> I think that one is not in the list of initial candidates.
> 
> I think for that sake we would want to add stripped &base + object size (+ 1?)
> (if we know it) as IV candidate iff iv->step is negative, iff iv->step is
> positive continue to add &base.
> 
> I don't like the alias oracle fixups too much, but I guess we have to
> benchmark both alternatives.

The candidate is actually there:

candidate 8
  var_before ivtmp.13
  var_after ivtmp.13
  incremented before exit test
  type long unsigned int
  base (long unsigned int) &MEM[(int *)&array][3]{lb: 0 sz: 4}
  step 0x0fffffffffffffffc
  base object (void *) &array

The following patch fixes the problem. Is it ok?

David


--- tree-ssa-loop-ivopts.c      (revision 173278)
+++ tree-ssa-loop-ivopts.c      (working copy)
@@ -3968,7 +3968,7 @@ get_computation_cost_at (struct ivopts_d
                          int *inv_expr_id)
 {
   tree ubase = use->iv->base, ustep = use->iv->step;
-  tree cbase, cstep;
+  tree cbase, cstep, cbase_strip;
   tree utype = TREE_TYPE (ubase), ctype;
   unsigned HOST_WIDE_INT cstepi, offset = 0;
   HOST_WIDE_INT ratio, aratio;
@@ -4026,6 +4026,13 @@ get_computation_cost_at (struct ivopts_d
   if (!constant_multiple_of (ustep, cstep, &rat))
     return infinite_cost;

+  cbase_strip = STRIP_NOPS (cbase);
+  /* Avoid confusing aliaser.  */
+  if (TREE_CODE (cbase_strip) == ADDR_EXPR
+      && TREE_CODE (TREE_OPERAND (cbase_strip, 0)) == VAR_DECL
+      && (HOST_WIDE_INT) cstepi < 0)
+    return infinite_cost;
+
   if (double_int_fits_in_shwi_p (rat))
     ratio = double_int_to_shwi (rat);
   else

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rakdver at kam dot mff.cuni.cz]

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

--- Comment #15 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-05-17 19:26:18 UTC ---
Hi,

> The following patch fixes the problem. Is it ok?

as a heuristic, this probably makes sense.  Still, it does
not fix the problem, just masks it and makes it harder to reproduce,

Zdenek

> David
> 
> 
> --- tree-ssa-loop-ivopts.c      (revision 173278)
> +++ tree-ssa-loop-ivopts.c      (working copy)
> @@ -3968,7 +3968,7 @@ get_computation_cost_at (struct ivopts_d
>                           int *inv_expr_id)
>  {
>    tree ubase = use->iv->base, ustep = use->iv->step;
> -  tree cbase, cstep;
> +  tree cbase, cstep, cbase_strip;
>    tree utype = TREE_TYPE (ubase), ctype;
>    unsigned HOST_WIDE_INT cstepi, offset = 0;
>    HOST_WIDE_INT ratio, aratio;
> @@ -4026,6 +4026,13 @@ get_computation_cost_at (struct ivopts_d
>    if (!constant_multiple_of (ustep, cstep, &rat))
>      return infinite_cost;
> 
> +  cbase_strip = STRIP_NOPS (cbase);
> +  /* Avoid confusing aliaser.  */
> +  if (TREE_CODE (cbase_strip) == ADDR_EXPR
> +      && TREE_CODE (TREE_OPERAND (cbase_strip, 0)) == VAR_DECL
> +      && (HOST_WIDE_INT) cstepi < 0)
> +    return infinite_cost;
> +
>    if (double_int_fits_in_shwi_p (rat))
>      ratio = double_int_to_shwi (rat);
>    else
> 
> -- 
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #16 from davidxl <xinliangli at gmail dot com> 2011-05-17 19:57:01 UTC ---
This is not really heuristic -- it prevents compiler from generating code in
ivopt that violates the aliasing assumption. 

David

(In reply to comment #15)
> Hi,
> 
> > The following patch fixes the problem. Is it ok?
> 
> as a heuristic, this probably makes sense.  Still, it does
> not fix the problem, just masks it and makes it harder to reproduce,
> 
> Zdenek
> 
> > David
> > 
> > 
> > --- tree-ssa-loop-ivopts.c      (revision 173278)
> > +++ tree-ssa-loop-ivopts.c      (working copy)
> > @@ -3968,7 +3968,7 @@ get_computation_cost_at (struct ivopts_d
> >                           int *inv_expr_id)
> >  {
> >    tree ubase = use->iv->base, ustep = use->iv->step;
> > -  tree cbase, cstep;
> > +  tree cbase, cstep, cbase_strip;
> >    tree utype = TREE_TYPE (ubase), ctype;
> >    unsigned HOST_WIDE_INT cstepi, offset = 0;
> >    HOST_WIDE_INT ratio, aratio;
> > @@ -4026,6 +4026,13 @@ get_computation_cost_at (struct ivopts_d
> >    if (!constant_multiple_of (ustep, cstep, &rat))
> >      return infinite_cost;
> > 
> > +  cbase_strip = STRIP_NOPS (cbase);
> > +  /* Avoid confusing aliaser.  */
> > +  if (TREE_CODE (cbase_strip) == ADDR_EXPR
> > +      && TREE_CODE (TREE_OPERAND (cbase_strip, 0)) == VAR_DECL
> > +      && (HOST_WIDE_INT) cstepi < 0)
> > +    return infinite_cost;
> > +
> >    if (double_int_fits_in_shwi_p (rat))
> >      ratio = double_int_to_shwi (rat);
> >    else
> > 
> > -- 
> > Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> > ------- You are receiving this mail because: -------
> > You are on the CC list for the bug.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rakdver at kam dot mff.cuni.cz]

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

--- Comment #17 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-05-17 20:18:39 UTC ---
> This is not really heuristic -- it prevents compiler from generating code in
> ivopt that violates the aliasing assumption. 

no, it does not.  For example, you only consider the case whent the base of the
memory
reference is addr_expr, and when the step is negative.  However, ivopts may
generate
"pointers" outside of the memory objects in other cases as well; and if those
get used in
mem_refs (where the computations are currently interpreted according to the
pointer
arithmetics rules, for the purpose of alias analysis), this leads to
misscompilations.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #18 from davidxl <xinliangli at gmail dot com> 2011-05-17 20:40:41 UTC ---
(In reply to comment #17)
> > This is not really heuristic -- it prevents compiler from generating code in
> > ivopt that violates the aliasing assumption. 
> 
> no, it does not. 

Does, but may not fully do.

> For example, you only consider the case whent the base of the
> memory
> reference is addr_expr, and when the step is negative.  However, ivopts may
> generate
> "pointers" outside of the memory objects in other cases as well;


Those would be bugs too -- do you have such examples? 

David

> and if those
> get used in
> mem_refs (where the computations are currently interpreted according to the
> pointer
> arithmetics rules, for the purpose of alias analysis), this leads to
> misscompilations.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenther at suse dot de]

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

--- Comment #19 from rguenther at suse dot de <rguenther at suse dot de> 2011-05-18 08:47:31 UTC ---
On Tue, 17 May 2011, rakdver at kam dot mff.cuni.cz wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48702
> 
> --- Comment #15 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-05-17 19:26:18 UTC ---
> Hi,
> 
> > The following patch fixes the problem. Is it ok?
> 
> as a heuristic, this probably makes sense.  Still, it does
> not fix the problem, just masks it and makes it harder to reproduce,

Looks similar to my original workaround, no?

We can actually use something like the aliasing non-pointer base
Zdenek mentioned upthread.  TARGET_MEM_REF has two index operands
(where usually TMR_INDEX2 is NULL of TMR_BASE is non-constant).
So we could build a TARGET_MEM_REF based off TMR_BASE 0B and
move the non-pointer base to TMR_INDEX2.  The oracle then should
not be able to disambiguate anything (and also no points-to
info would be available, which probably doesn't make this the
very very best idea either).

Richard.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #20 from davidxl <xinliangli at gmail dot com> 2011-05-18 15:51:06 UTC ---
(In reply to comment #19)
> On Tue, 17 May 2011, rakdver at kam dot mff.cuni.cz wrote:
> 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48702
> > 
> > --- Comment #15 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-05-17 19:26:18 UTC ---
> > Hi,
> > 
> > > The following patch fixes the problem. Is it ok?
> > 
> > as a heuristic, this probably makes sense.  Still, it does
> > not fix the problem, just masks it and makes it harder to reproduce,
> 
> Looks similar to my original workaround, no?
> 
> We can actually use something like the aliasing non-pointer base
> Zdenek mentioned upthread.  TARGET_MEM_REF has two index operands
> (where usually TMR_INDEX2 is NULL of TMR_BASE is non-constant).
> So we could build a TARGET_MEM_REF based off TMR_BASE 0B and
> move the non-pointer base to TMR_INDEX2.  The oracle then should
> not be able to disambiguate anything (and also no points-to
> info would be available, which probably doesn't make this the
> very very best idea either).
> 
> Richard.

This is at the cost of making aliasing info conservative which should at least
be modeled in the cost. Given that the alternative iv candidate exist (which
does not require such treatment), discarding the troublesome candidate seems
reasonable to me.

David

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[xinliangli at gmail dot com]

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

--- Comment #21 from davidxl <xinliangli at gmail dot com> 2011-05-19 05:02:29 UTC ---
Before a better fix is found, is the proposed patch ok? If yes, I will do more
testing and submit to gcc-patches@

David


(In reply to comment #19)
> On Tue, 17 May 2011, rakdver at kam dot mff.cuni.cz wrote:
> 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48702
> > 
> > --- Comment #15 from rakdver at kam dot mff.cuni.cz <rakdver at kam dot mff.cuni.cz> 2011-05-17 19:26:18 UTC ---
> > Hi,
> > 
> > > The following patch fixes the problem. Is it ok?
> > 
> > as a heuristic, this probably makes sense.  Still, it does
> > not fix the problem, just masks it and makes it harder to reproduce,
> 
> Looks similar to my original workaround, no?
> 
> We can actually use something like the aliasing non-pointer base
> Zdenek mentioned upthread.  TARGET_MEM_REF has two index operands
> (where usually TMR_INDEX2 is NULL of TMR_BASE is non-constant).
> So we could build a TARGET_MEM_REF based off TMR_BASE 0B and
> move the non-pointer base to TMR_INDEX2.  The oracle then should
> not be able to disambiguate anything (and also no points-to
> info would be available, which probably doesn't make this the
> very very best idea either).
> 
> Richard.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #22 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-25 10:19:12 UTC ---
Created attachment 24354
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24354
alternative patch for 4.6

This is another patch - it avoids creating MEM_REFs for base addresses that
we do not know whether they are always in bounds of the object it points to.
Instead we force the use of TARGET_MEM_REFs there and dumb down the alias
oracle to not assume that base address is within bounds.

Sounds like the most reasonable solution for 4.6 to me.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|49144                       |
                 CC|                            |doko at ubuntu dot com

--- Comment #23 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-25 10:33:24 UTC ---
*** Bug 49144 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #24 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-25 13:58:20 UTC ---
(In reply to comment #22)
> Created attachment 24354 [details]
> alternative patch for 4.6
> 
> This is another patch - it avoids creating MEM_REFs for base addresses that
> we do not know whether they are always in bounds of the object it points to.
> Instead we force the use of TARGET_MEM_REFs there and dumb down the alias
> oracle to not assume that base address is within bounds.
> 
> Sounds like the most reasonable solution for 4.6 to me.

Requires staging on trunk, there are multiple small fixes that need backporting
and one last cleanup (and fix) that I had pending needs to be finished first.

But I'll continue in this direction.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #25 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-26 10:01:33 UTC ---
I have benchmarked SPEC2k6 on the 4.6 branch with the patch (and required
backports) with -O3 -ffast-math -funroll-loops, Base is unpatched, Peak
is patched.  Average of three runs on a Intel(R) Core(TM) i7 CPU X 980 @
3.33GHz, the noise in the tests is +-1s.  So from a performance point
the patch doesn't seem to have problems.

                                  Estimated                       Estimated
                Base     Base       Base        Peak     Peak       Peak
Benchmarks      Ref.   Run Time     Ratio       Ref.   Run Time     Ratio
-------------- ------  ---------  ---------    ------  ---------  ---------
400.perlbench    9770        334       29.2 *    9770        337       29.0 *  
401.bzip2        9650        467       20.7 *    9650        459       21.0 *  
403.gcc          8050        289       27.9 *    8050        289       27.8 *  
429.mcf          9120        302       30.2 *    9120        304       30.0 *  
445.gobmk       10490        413       25.4 *   10490        413       25.4 *  
456.hmmer        9330        375       24.9 *    9330        374       24.9 *  
458.sjeng       12100        446       27.1 *   12100        446       27.1 *  
462.libquantum  20720        332       62.4 *   20720        332       62.4 *  
464.h264ref     22130        540       41.0 *   22130        540       41.0 *  
471.omnetpp      6250        300       20.9 *    6250        305       20.5 *  
473.astar        7020        373       18.8 *    7020        373       18.8 *  
483.xalancbmk    6900        225       30.7 *    6900        226       30.5 *  
 Est. SPECint_base2006                 28.3
 Est. SPECint2006                                                      28.3

                                  Estimated                       Estimated
                Base     Base       Base        Peak     Peak       Peak
Benchmarks      Ref.   Run Time     Ratio       Ref.   Run Time     Ratio
-------------- ------  ---------  ---------    ------  ---------  ---------
410.bwaves      13590        347       39.2 *   13590        347       39.2 *  
416.gamess      19580        740       26.5 *   19580        738       26.5 *  
433.milc         9180        382       24.0 *    9180        381       24.1 *  
434.zeusmp       9100        336       27.1 *    9100        336       27.1 *  
435.gromacs      7140        318       22.4 *    7140        318       22.4 *  
436.cactusADM   11950        422       28.3 *   11950        426       28.1 *  
437.leslie3d     9400        316       29.8 *    9400        315       29.9 *  
444.namd         8020        397       20.2 *    8020        398       20.2 *  
447.dealII      11440        315       36.3 *   11440        314       36.5 *  
450.soplex       8340        220       37.9 *    8340        220       37.9 *  
453.povray       5320        186       28.6 *    5320        187       28.4 *  
454.calculix     8250        365       22.6 *    8250        365       22.6 *  
459.GemsFDTD    10610        344       30.9 *   10610        340       31.2 *  
465.tonto        9840        380       25.9 *    9840        378       26.0 *  
470.lbm         13740        254       54.0 *   13740        255       53.9 *  
481.wrf         11170        351       31.8 *   11170        352       31.8 *  
482.sphinx3     19490        483       40.4 *   19490        485       40.2 *  
 Est. SPECfp_base2006                  30.0
 Est. SPECfp2006                                                       30.0

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #24354|0                           |1
        is obsolete|                            |

--- Comment #26 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-26 11:05:18 UTC ---
Created attachment 24362
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24362
alternative patch for 4.6, with backports

That's what I have successfully bootstrapped and tested and SPEC tested.

[Bug tree-optimization/48702] [4.6/4.7 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #27 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-26 13:01:50 UTC ---
Author: rguenth
Date: Thu May 26 13:01:48 2011
New Revision: 174282

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

    PR tree-optimization/48702
    * tree-ssa-address.c (create_mem_ref_raw): Create MEM_REFs
    only when we know the base address is within bounds.
    * tree-ssa-alias.c (indirect_ref_may_alias_decl_p): Do not
    assume the base address of TARGET_MEM_REFs is in bounds.

    * gcc.dg/torture/pr48702.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr48702.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-address.c
    trunk/gcc/tree-ssa-alias.c

[Bug tree-optimization/48702] [4.6 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.7.0
            Summary|[4.6/4.7 Regression]        |[4.6 Regression]
                   |optimization regression     |optimization regression
                   |with gcc-4.6 on             |with gcc-4.6 on
                   |x86_64-unknown-linux-gnu    |x86_64-unknown-linux-gnu
      Known to fail|4.7.0                       |

--- Comment #28 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-26 13:03:46 UTC ---
Fixed on trunk sofar.

[Bug tree-optimization/48702] [4.6 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #29 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-06 10:13:27 UTC ---
Author: rguenth
Date: Mon Jun  6 10:13:23 2011
New Revision: 174688

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174688
Log:
2011-06-06  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/48702
    * tree-ssa-address.c (create_mem_ref_raw): Create MEM_REFs
    only when we know the base address is within bounds.
    * tree-ssa-alias.c (indirect_ref_may_alias_decl_p): Do not
    assume the base address of TARGET_MEM_REFs is in bounds.
    (indirect_refs_may_alias_p): Fix TARGET_MEM_REF without index tests.

    * gcc.dg/torture/pr48702.c: New testcase.

    Backport from mainline
    2011-05-31  Jakub Jelinek  <jakub@redhat.com>

    PR rtl-optimization/49235
    * tree-ssa-address.c (gen_addr_rtx): Ignore base if it is const0_rtx.
    (create_mem_ref_raw): Create MEM_REF even if base is INTEGER_CST.

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

Added:
    branches/gcc-4_6-branch/gcc/testsuite/gcc.dg/pr49235.c
    branches/gcc-4_6-branch/gcc/testsuite/gcc.dg/torture/pr48702.c
Modified:
    branches/gcc-4_6-branch/gcc/ChangeLog
    branches/gcc-4_6-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_6-branch/gcc/tree-ssa-address.c
    branches/gcc-4_6-branch/gcc/tree-ssa-alias.c

[Bug tree-optimization/48702] [4.6 Regression] optimization regression with gcc-4.6 on x86_64-unknown-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #30 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-06 10:18:30 UTC ---
Fixed.