Bug 22591 - [4.0 regression] wrong alias information causes an incorrect redundant load elimination
Summary: [4.0 regression] wrong alias information causes an incorrect redundant load e...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.1
: P2 critical
Target Milestone: 4.0.2
Assignee: Diego Novillo
URL:
Keywords: alias, wrong-code
: 22513 (view as bug list)
Depends on:
Blocks: 22513 23086
  Show dependency treegraph
 
Reported: 2005-07-21 15:56 UTC by Simon Finn
Modified: 2005-07-27 15:04 UTC (History)
9 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-07-26 14:26:55


Attachments
Standalone testcase (6.3 kB) (1.47 KB, text/plain)
2005-07-23 03:11 UTC, Volker Reichelt
Details
Small testcase (~50 lines, 750 bytes) (378 bytes, text/plain)
2005-07-24 15:34 UTC, Volker Reichelt
Details
C testcase (361 bytes, text/plain)
2005-07-24 17:51 UTC, Volker Reichelt
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Simon Finn 2005-07-21 15:56:51 UTC
Save the following as foo.C, then

g++ foo.C -o foo

Running foo blows the assertion.

g++ -v produces:

Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../gcc-4.0.1/configure
Thread model: posix
gcc version 4.0.1

Uncommenting the print statements shows that my_list.begin()
has not been updated by the call to my_list.erase(), even
though the first (only) element of this list has just been deleted.


//----------------------------------------------------------------------------

#include <list>
#include <iostream>
#include <cassert>

using namespace std;

main()
{
	list<int> my_list;
	my_list.push_front(1);

	list<int> my_other_list;
	my_other_list.push_front(2);

//cerr << "Lists built \n";
//cerr << "my_list.end() = " << ((void *) (&*my_list.end())) << "\n";
//cerr << "my_list.begin() = " << ((void *) (&*my_list.begin())) << "\n";
//cerr << "my_other_list.end() = " << ((void *) (&*my_other_list.end())) << "\n";
//cerr << "my_other_list.begin() = " << ((void *) (&*my_other_list.begin())) <<
"\n";

	swap(my_list,my_other_list);

//cerr << "After swap \n";
//cerr << "my_list.end() = " << ((void *) (&*my_list.end())) << "\n";
//cerr << "my_list.begin() = " << ((void *) (&*my_list.begin())) << "\n";
//cerr << "my_other_list.end() = " << ((void *) (&*my_other_list.end())) << "\n";
//cerr << "my_other_list.begin() = " << ((void *) (&*my_other_list.begin())) <<
"\n";

	list<int>::iterator it = my_list.begin();
	while (it != my_list.end())
	{
//cerr << "erasing: " << ((void *)(&*it)) << "\n";
		it = my_list.erase(it);
//cerr << "my_list.end() = " << ((void *) (&*my_list.end())) << "\n";
//cerr << "my_list.begin() = " << ((void *) (&*my_list.begin())) << "\n";
	}

//cerr << "At end \n";
//cerr << "my_list.end() = " << ((void *) (&*my_list.end())) << "\n";
//cerr << "my_list.begin() = " << ((void *) (&*my_list.begin())) << "\n";
//cerr << "my_other_list.end() = " << ((void *) (&*my_other_list.end())) << "\n";
//cerr << "my_other_list.begin() = " << ((void *) (&*my_other_list.begin())) <<
"\n";

	assert(my_list.begin() == my_list.end());
}
Comment 1 Paolo Carlini 2005-07-21 16:12:55 UTC
Looks like a miscompilation: mainline is ok and old (~1 month) mainline is not;
no changes in 4_0-branch to std::list and std::swap. Related to c++/22513??
Comment 2 Giovanni Bajo 2005-07-21 16:59:50 UTC
It would greatly help to identify the patch that broke either this PR or PR 
22513. One possible offender is the new alias stuff by Diego/Daniel.
Comment 3 Andrew Pinski 2005-07-21 17:03:32 UTC
(In reply to comment #2)
> It would greatly help to identify the patch that broke either this PR or PR 
> 22513. One possible offender is the new alias stuff by Diego/Daniel.

Also Paolo said it works on the mainline so I really doube it was broken by those patches.
Comment 4 Andrew Pinski 2005-07-21 17:54:23 UTC
I wonder if this is not really a bug in libstdc++.  with -fmudflap:
*******
mudflap violation 1 (check/write): time=1121968411.144393 ptr=0xbffa2030 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE5beginEv+0x83) [0x804b145]
Nearby object 1: checked region begins 16B before and ends 13B before
mudflap object 0x9ce43b8: name=`t1.cc:10240 (std::list<int, std::allocator<int> >::push_front) 
<unnamed variable>'
bounds=[0xbffa2040,0xbffa2043] size=4 area=stack check=0r/0w liveness=0
alloc time=1121968411.144386 pc=0x22604d
Nearby object 2: checked region begins 7B before and ends 4B before
mudflap dead object 0x9ce4350: name=`t1.cc:9992 (std::_List_base<int, std::allocator<int> >::
_List_base) <unnamed variable>'
bounds=[0xbffa2037,0xbffa2037] size=1 area=stack check=0r/0w liveness=0
alloc time=1121968411.144362 pc=0x22604d
dealloc time=1121968411.144370 pc=0x225ba6
number of nearby objects: 2
*******
mudflap violation 2 (check/write): time=1121968411.146855 ptr=0xbffa2030 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE5beginEv+0x83) [0x804b145]
Nearby object 1: checked region begins 16B before and ends 13B before
mudflap object 0x9d2cca8: name=`t1.cc:10240 (std::list<int, std::allocator<int> >::push_front) 
<unnamed variable>'
bounds=[0xbffa2040,0xbffa2043] size=4 area=stack check=0r/0w liveness=0
alloc time=1121968411.146849 pc=0x22604d
Nearby object 2: checked region begins 7B before and ends 4B before
mudflap dead object 0x9d2cc58: name=`t1.cc:9992 (std::_List_base<int, std::allocator<int> >::
_List_base) <unnamed variable>'
bounds=[0xbffa2037,0xbffa2037] size=1 area=stack check=0r/0w liveness=0
alloc time=1121968411.146839 pc=0x22604d
dealloc time=1121968411.146845 pc=0x225ba6
number of nearby objects: 2
*******
mudflap violation 3 (check/write): time=1121968411.147476 ptr=0xbffa2090 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE5beginEv+0x83) [0x804b145]
Nearby object 1: checked region begins 4B before and ends 1B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
bounds=[0xbffa2094,0xbffa2097] size=4 area=stack check=0r/0w liveness=0
alloc time=1121968411.144342 pc=0x22604d
Nearby object 2: checked region begins 77B after and ends 80B after
mudflap dead object 0x9d2cca8: name=`t1.cc:10240 (std::list<int, std::allocator<int> >::push_front) 
<unnamed variable>'
bounds=[0xbffa2040,0xbffa2043] size=4 area=stack check=0r/0w liveness=0
alloc time=1121968411.146849 pc=0x22604d
dealloc time=1121968411.147468 pc=0x225ba6
number of nearby objects: 2
*******
mudflap violation 4 (check/write): time=1121968411.148044 ptr=0xbffa2088 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE3endEv+0x19) [0x804b0b7]
Nearby object 1: checked region begins 12B before and ends 9B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
Nearby object 2: checked region begins 16B before and ends 13B before
mudflap object 0x9ce4220: name=`t1.cc:29322 (main) std::list<int, std::allocator<int> > 
my_other_list'
bounds=[0xbffa2098,0xbffa209f] size=8 area=stack check=0r/1w liveness=1
alloc time=1121968411.144338 pc=0x22604d
Nearby object 3: checked region begins 69B after and ends 72B after
mudflap dead object 0x9d2cca8: name=`t1.cc:10240 (std::list<int, std::allocator<int> >::push_front) 
<unnamed variable>'
number of nearby objects: 3
*******
mudflap violation 5 (check/write): time=1121968411.148637 ptr=0xbffa208c size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE5eraseESt14_List_iteratorIiE+0xd3) [0x804c737]
Nearby object 1: checked region begins 8B before and ends 5B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
Nearby object 2: checked region begins 12B before and ends 9B before
mudflap object 0x9ce4220: name=`t1.cc:29322 (main) std::list<int, std::allocator<int> > 
my_other_list'
Nearby object 3: checked region begins 20B before and ends 17B before
mudflap object 0x9ce41b8: name=`t1.cc:29319 (main) std::list<int, std::allocator<int> > my_list'
bounds=[0xbffa20a0,0xbffa20a7] size=8 area=stack check=0r/1w liveness=1
alloc time=1121968411.144334 pc=0x22604d
Nearby object 4: checked region begins 73B after and ends 76B after
mudflap dead object 0x9d2cca8: name=`t1.cc:10240 (std::list<int, std::allocator<int> >::push_front) 
<unnamed variable>'
number of nearby objects: 4
*******
mudflap violation 6 (check/write): time=1121968411.149349 ptr=0xbffa2088 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE3endEv+0x19) [0x804b0b7]
Nearby object 1: checked region begins 12B before and ends 9B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
Nearby object 2: checked region begins 16B before and ends 13B before
mudflap object 0x9ce4220: name=`t1.cc:29322 (main) std::list<int, std::allocator<int> > 
my_other_list'
Nearby object 3: checked region begins 45B after and ends 48B after
mudflap dead object 0x9d2cd48: name=`t1.cc:10520 (std::list<int, std::allocator<int> >::erase) std::
_List_iterator<int> __position'
bounds=[0xbffa2058,0xbffa205b] size=4 area=stack check=0r/0w liveness=0
alloc time=1121968411.148627 pc=0x22604d
dealloc time=1121968411.149343 pc=0x225ba6
number of nearby objects: 3
*******
mudflap violation 7 (check/write): time=1121968411.149980 ptr=0xbffa2084 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE3endEv+0x19) [0x804b0b7]
Nearby object 1: checked region begins 16B before and ends 13B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
Nearby object 2: checked region begins 20B before and ends 17B before
mudflap object 0x9ce4220: name=`t1.cc:29322 (main) std::list<int, std::allocator<int> > 
my_other_list'
Nearby object 3: checked region begins 41B after and ends 44B after
mudflap dead object 0x9d2cd48: name=`t1.cc:10520 (std::list<int, std::allocator<int> >::erase) std::
_List_iterator<int> __position'
number of nearby objects: 3
*******
mudflap violation 8 (check/write): time=1121968411.150537 ptr=0xbffa2080 size=4
pc=0x226d6d location=`t1.cc:9808 (std::_List_iterator<int>::_List_iterator)'
      /home/peshtigo/pinskia/linux/lib/libmudflap.so.0(__mf_check+0x3d) [0x226d6d]
      ./a.out(_ZNSt14_List_iteratorIiEC1EPSt15_List_node_base+0x6f) [0x804b093]
      ./a.out(_ZNSt4listIiSaIiEE5beginEv+0x83) [0x804b145]
Nearby object 1: checked region begins 20B before and ends 17B before
mudflap object 0x9ce4288: name=`t1.cc:29341 (main) std::_List_iterator<int> it'
Nearby object 2: checked region begins 37B after and ends 40B after
mudflap dead object 0x9d2cd48: name=`t1.cc:10520 (std::list<int, std::allocator<int> >::erase) std::
_List_iterator<int> __position'
number of nearby objects: 2
Comment 5 Janis Johnson 2005-07-21 17:59:16 UTC
The test case passes for me on powerpc-linux with GCC 3.4.x and fails with
everything later.  Is the mudflap output enough to track down the problem,
or would the results of a regression hunt still help?
Comment 6 Paolo Carlini 2005-07-21 23:34:23 UTC
> The test case passes for me on powerpc-linux with GCC 3.4.x and fails with
> everything later.

Mainline doesn't fail for me on x86-linux, but I have it configured with a
different allocator (new).

                     Is the mudflap output enough to track down the problem,
> or would the results of a regression hunt still help?

I'm trying to debug a little further, a regression hunt would definitely help!
Comment 7 Paolo Carlini 2005-07-22 01:24:09 UTC
For the moment, I give up: in my opinion, a miscompilation is still the most
likely possibility. Meaningless behaviors are taking place: for instance, the
testcase passes if I exchange the arguments of swap to (my_other_list, my_list)
and of course the implementation is symmetric and nobody changed it for eons.

A last comment about mudflap. Right now, I'm not really able to make sense out of 
some of its outputs: even a single push_back() to a single list leads to errors?!?

Really, it would be great if Janis could hunt for the regression.
Comment 8 Paolo Carlini 2005-07-22 08:23:51 UTC
_List_node_base::swap is part of list.cc, in the built .so/.a library: If I
change the build, lowering the optimization level (tried CXXFLAGS="-O0 -g")
the problem disappear (on x86-linux). Wrong-code.
Comment 9 Paolo Carlini 2005-07-22 10:46:02 UTC
By the way, I confirm that cannot reproduce with current mainline, neither on
x86-linux nor x86_64-linux (default build options). I'm unsure whether we should
mark it as 'target' and 4.1 Regression too...
Comment 10 Paolo Carlini 2005-07-22 12:44:05 UTC
Mainline is fine on ia64-linux too.
Comment 11 Janis Johnson 2005-07-22 15:57:16 UTC
I'm doing a regression hunt, but keep making stupid mistakes in the setup so
it's taking much longer than it should.
Comment 12 Volker Reichelt 2005-07-22 16:40:09 UTC
Just another data point:

I just compiled the testcase (without including iostream) with -O3 -c
using 4.0 branch.
If I link this with libstdc++ from the 4.0 the assertion is triggered.
If I link this with libstdc++ from the 3.4 branch or mainline,
the assert is not triggered.
The same happens, if I use -O0 instead of -O3.

nm of the object file yields:

         U _Unwind_Resume
         U _ZNSt15_List_node_base4hookEPS_
         U _ZNSt15_List_node_base4swapERS_S0_
         U _ZNSt15_List_node_base6unhookEv
00000000 d _ZZ4mainE19__PRETTY_FUNCTION__
         U _ZdlPv
         U _Znwj
         U __assert_fail
         U __gxx_personality_v0
00000000 T main

So a miscompilation of _List_node_base::swap (or ::hook or ::unhook)
in libstdc++ seems to be very likely.
Comment 13 Janis Johnson 2005-07-22 22:11:21 UTC
My regression hunt identified the following patch from dnovillo:

  http://gcc.gnu.org/ml/gcc-cvs/2004-09/msg00671.html
Comment 14 Paolo Carlini 2005-07-22 22:23:49 UTC
Thanks a lot, Janis!
Comment 15 Paolo Carlini 2005-07-22 22:30:08 UTC
Maybe it's appropriate adding Diego in CC...
Comment 16 Volker Reichelt 2005-07-23 00:57:44 UTC
With an older mainline from 20050623 I also see the crash.
Comment 17 Volker Reichelt 2005-07-23 03:11:56 UTC
Created attachment 9335 [details]
Standalone testcase (6.3 kB)
Comment 18 Volker Reichelt 2005-07-23 03:15:14 UTC
I just added a standalone testcase which only uses "new" from libstdc++
(and __gxx_personality_v0).

It reports FAIL with -O2 and -Os on the 4.0 branch, but works with
-O0, -O1 and -O3 or a different compiler (even 2.95.3 works).
Comment 19 Volker Reichelt 2005-07-24 15:34:00 UTC
Created attachment 9345 [details]
Small testcase (~50 lines, 750 bytes)
Comment 20 Andrew Pinski 2005-07-24 16:04:43 UTC
This is a strict aliasing bug.
Comment 21 Andrew Pinski 2005-07-24 16:15:12 UTC
Hmm, this test does not fail on ppc-darwin but does on i686-pc-linux-gnu.

I think this is a RTL problem as the tree dumps for both i686 and ppc are the same at -O2.

Then again this might be a bug in the C++ front-end still.
Comment 22 Andrew Pinski 2005-07-24 16:25:25 UTC
Actually I take that back.
the tree dumps are different.
Hmm, maybe we are miscompiling more than just the testcase.
Comment 23 Andrew Pinski 2005-07-24 16:33:21 UTC
(In reply to comment #22)
> Hmm, maybe we are miscompiling more than just the testcase.
Nope.  Compiling for x86_64 from ppc-darwin, we get the same failure here.
Comment 24 Volker Reichelt 2005-07-24 17:51:42 UTC
Created attachment 9351 [details]
C testcase

It's not a bug in the C++ frontend.
I get the same failure with this C testcase.
Comment 25 Volker Reichelt 2005-07-24 22:29:11 UTC
Just another data point: The problem disappeared on mainline with
Dan's patch
http://gcc.gnu.org/ml/gcc-cvs/2005-06/msg01108.html
Comment 26 Andrew Pinski 2005-07-24 22:32:35 UTC
(In reply to comment #25)
> Just another data point: The problem disappeared on mainline with
> Dan's patch

Not according to my testing, it still fails on the mainline as of today.
Comment 27 Volker Reichelt 2005-07-25 00:15:21 UTC
> Not according to my testing, it still fails on the mainline as of today.

Indeed, I have to add -march=pentium4 to trigger the bug, though.
Comment 28 Steven Bosscher 2005-07-26 10:39:21 UTC
I can reproduce this with the C test case from comment #24 on x86_64-linux 
with -march=nocona.  With -march=k8 that test case does _not_ abort. 
 
Comment 29 Steven Bosscher 2005-07-26 10:43:23 UTC
Well I'll be damned! 
$ ./xgcc -B. t.c -O2 -march=nocona 
$ ./a.out 
Aborted 
$ ./xgcc -B. t.c -O2 -march=nocona -da -fdump-tree-all 
$ ./a.out 
$ 
 
$ ./xgcc -B. t.c -O2 -march=nocona -S -da 
$ mv t.s t.s.with_dumps 
$ ./xgcc -B. t.c -O2 -march=nocona -S 
$ diff -u t.s t.s.with_dumps 
--- t.s 2005-07-26 12:42:14.447531418 +0200 
+++ t.s.with_dumps      2005-07-26 12:42:03.501170603 +0200 
@@ -26,19 +26,20 @@ 
        .type   ListSwap, @function 
 ListSwap: 
 .LFB4: 
-       movq    (%rdi), %rcx 
-       testq   %rcx, %rcx 
+       cmpq    $0, (%rdi) 
        je      .L8 
+       movq    (%rdi), %rdx 
        movq    (%rsi), %rax 
        movq    %rax, (%rdi) 
-       movq    %rcx, (%rsi) 
+       movq    %rdx, (%rsi) 
        movq    8(%rdi), %rdx 
        movq    8(%rsi), %rax 
        movq    %rax, 8(%rdi) 
        movq    %rdx, 8(%rsi) 
+       movq    (%rdi), %rdx 
        movq    8(%rdi), %rax 
        movq    %rdi, (%rax) 
-       movq    %rdi, 8(%rcx) 
+       movq    %rdi, 8(%rdx) 
        movq    (%rsi), %rdx 
        movq    8(%rsi), %rax 
        movq    %rsi, (%rax) 
 
wtf?! 
Comment 30 Steven Bosscher 2005-07-26 11:18:39 UTC
My version of t.c: 
=========================================== 
void abort (); 
 
typedef struct _Node 
{ 
  struct _Node *next, *prev; 
} Node; 
 
void __attribute__ ((noinline)) append (Node * q, Node * p) 
{ 
  p->next = q; 
  p->prev = q; 
  q->next = p; 
  q->prev = p; 
} 
 
inline void 
swap (Node ** a, Node ** b) 
{ 
  Node *tmp = *a; 
  *a = *b; 
  *b = tmp; 
} 
 
/* Miscompilation seems to happen here. If one removes the if condition 
   (which should be true) the program works fine.  */ 
void 
ListSwap (Node * x, Node * y) 
{ 
  Node *tmp; 
  if (x->next) 
    { 
      swap (&x->next, &y->next); 
      swap (&x->prev, &y->prev); 
      x->next->prev = x->prev->next = x; 
      y->next->prev = y->prev->next = y; 
    } 
} 
 
int 
main () 
{ 
  Node A, A1, B, B1; 
 
  append (&A, &A1); 
  append (&B, &B1); 
 
  ListSwap (&A, &B); 
 
  if (&A != A.next->prev) 
    abort (); 
} 
=========================================== 
 
compiled with: 
$ ./xgcc -B. t.c -O2 -m32 -march=pentium4 -da -fdump-tree-vars 
 
gives me this for ListSwap: 
=========================================== 
ListSwap (x, y) 
{ 
  struct Node * * a; 
  struct Node * * b; 
  struct Node * tmp; 
  struct Node * * a; 
  struct Node * * b; 
  struct Node * tmp; 
  struct _Node * D.1621; 
  struct _Node * D.1614; 
 
<bb 0>: 
  D.1614 = x->next; 
  if (D.1614 != 0B) goto <L0>; else goto <L1>; 
 
<L0>:; 
  a = &x->next; 
  b = &y->next; 
  tmp = *a; 
  *a = *b; 
  *b = tmp; 
  a = &x->prev; 
  b = &y->prev; 
  tmp = *a; 
  *a = *b; 
  *b = tmp; 
  x->prev->next = x; 
  D.1614->prev = x; 
  D.1621 = y->next; 
  y->prev->next = y; 
  D.1621->prev = y; 
 
<L1>:; 
  return; 
 
} 
=========================================== 
 
Look at D.1614.  It is loaded befoe the conditional, and later there is 
a store to D.1614->prev.  But isn't x->next already something else by 
then?  After all, x->next and y->next are swapped.  I checked with Serge 
Belyshev and he agrees this looks fishy: 
/QUOTE/ 
>   a = &x->next; 
>   b = &y->next; 
... 
>   *a = *b; 
 
this changes x->next 
 
>   D.1614->prev = x; 
 
but this still uses old value of x->next 
/QUOTE/ 
 
Comment 31 Steven Bosscher 2005-07-26 11:43:39 UTC
Smaller test case: 
 
====================================================== 
void abort (); 
 
typedef struct _Node 
{ 
  struct _Node *next, *prev; 
} Node; 
 
inline void 
swap (Node ** a, Node ** b) 
{ 
  Node *tmp = *a; 
  *a = *b; 
  *b = tmp; 
} 
 
/* Miscompilation seems to happen here. If one removes the if condition 
   (which should be true) the program works fine.  */ 
void 
ListSwap (Node * x, Node * y) 
{ 
  Node *tmp; 
  if (x->next) 
    { 
      swap (&x->next, &y->next); 
      x->next->prev = x->prev->next = x; 
    } 
} 
====================================================== 
 
 
Gives this .vars dump: 
 
====================================================== 
ListSwap (x, y) 
{ 
  struct Node * * a; 
  struct Node * * b; 
  struct Node * tmp; 
  struct _Node * D.1610; 
 
<bb 0>: 
  D.1610 = x->next; 
  if (D.1610 != 0B) goto <L0>; else goto <L1>; 
 
<L0>:; 
  a = &x->next; 
  b = &y->next; 
  tmp = *a; 
  *a = *b; 
  *b = tmp; 
  x->prev->next = x; 
  D.1610->prev = x; 
 
<L1>:; 
  return; 
 
} 
====================================================== 
 
In the .t22.ccp dump the function still looks OK: 
  D.1610_10 = x_1->next; 
  D.1613_11 = x_1->prev; 
  D.1613_11->next = x_1; 
  D.1614_12 = D.1613_11->next; 
  D.1610_10->prev = D.1614_12; 
 
Then .t23.fre causes the problem because the wrong alias info is wrong: 
  D.1610_10 = D.1610_2; 
  D.1613_11 = x_1->prev; 
  D.1613_11->next = x_1; 
  D.1614_12 = D.1613_11->next; 
  D.1610_10->prev = D.1614_12; 
 
Note btw how FRE does not replace "D.1614_12" with x_1, which is a missed 
optimization. 
 
The alias info is already wrong when it is computed, so at least it is not 
some kind of weird updating problem: 
 
ListSwap (xD.1605, yD.1606) 
{ 
  struct NodeD.1598 * * aD.1660; 
  struct NodeD.1598 * * bD.1661; 
  struct NodeD.1598 * tmpD.1662; 
  struct NodeD.1598 * D.1663; 
  struct NodeD.1598 * tmpD.1609; 
  struct _Node * D.1614; 
  struct _Node * D.1613; 
  struct _Node * * D.1612; 
  struct _Node * * D.1611; 
  struct _Node * D.1610; 
 
  # BLOCK 0 
  # PRED: ENTRY (fallthru) 
  #   VUSE <TMT.31D.1669_13>; 
  D.1610_2 = xD.1605_1->nextD.1596; 
  if (D.1610_2 != 0B) goto <L0>; else goto <L1>; 
  # SUCC: 1 (true) 2 (false) 
 
  # BLOCK 1 
  # PRED: 0 (true) 
<L0>:; 
  D.1611_4 = &yD.1606_3->nextD.1596; 
  D.1612_5 = &xD.1605_1->nextD.1596; 
  aD.1660_6 = (struct NodeD.1598 * *) D.1612_5; 
  bD.1661_7 = (struct NodeD.1598 * *) D.1611_4; 
  #   VUSE <TMT.32D.1670_14>; 
  tmpD.1662_8 = *aD.1660_6; 
  #   VUSE <TMT.32D.1670_14>; 
  D.1663_9 = *bD.1661_7; 
  #   TMT.32D.1670_15 = V_MAY_DEF <TMT.32D.1670_14>; 
  *aD.1660_6 = D.1663_9; 
  #   TMT.32D.1670_16 = V_MAY_DEF <TMT.32D.1670_15>; 
  *bD.1661_7 = tmpD.1662_8; 
  #   VUSE <TMT.31D.1669_13>; 
  D.1610_10 = xD.1605_1->nextD.1596; 
  #   VUSE <TMT.31D.1669_13>; 
  D.1613_11 = xD.1605_1->prevD.1597; 
  #   TMT.31D.1669_17 = V_MAY_DEF <TMT.31D.1669_13>; 
  D.1613_11->nextD.1596 = xD.1605_1; 
  #   VUSE <TMT.31D.1669_17>; 
  D.1614_12 = D.1613_11->nextD.1596; 
  #   TMT.31D.1669_18 = V_MAY_DEF <TMT.31D.1669_17>; 
  D.1610_10->prevD.1597 = D.1614_12; 
  # SUCC: 2 (fallthru) 
 
  # BLOCK 2 
  # PRED: 0 (false) 1 (fallthru) 
<L1>:; 
  return; 
  # SUCC: EXIT 
 
} 
 
Notice that the stores to *a and *b are not killing TMT.31D.1669_13.  That 
is wrong. 
 
 
 
Comment 32 Richard Biener 2005-07-26 13:10:55 UTC
I have (with whatever load of patches applied...)

;; Function ListSwap (ListSwap)

ListSwap (x, y)
{
  struct Node * tmp;
  struct _Node * D.1292;

<bb 0>:
  tmp = x->next;
  if (tmp != 0B) goto <L0>; else goto <L1>;

<L0>:;
  x->next = y->next;
  y->next = tmp;
  D.1292 = x->next;
  x->prev->next = x;
  D.1292->prev = x;

<L1>:;
  return;

}
Comment 33 Paolo Carlini 2005-07-26 13:17:03 UTC
Yes, but why P1 -> P2?!?
Comment 34 Diego Novillo 2005-07-26 14:46:59 UTC
(In reply to comment #31)
> Smaller test case: 
>  
This works for me.  The original test case does abort, though.
Comment 35 Diego Novillo 2005-07-26 16:19:30 UTC
Testing patch.  The shortcut we were taking in may_alias_p is invalid even with
strict aliasing.

--- tree-ssa-alias.c    25 Jul 2005 12:04:50 -0000      2.107
+++ tree-ssa-alias.c    26 Jul 2005 16:16:34 -0000
@@ -1511,23 +1511,6 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem

   alias_stats.tbaa_queries++;

-  /* If VAR is a pointer with the same alias set as PTR, then dereferencing
-     PTR can't possibly affect VAR.  Note, that we are specifically testing
-     for PTR's alias set here, not its pointed-to type.  We also can't
-     do this check with relaxed aliasing enabled.  */
-  if (POINTER_TYPE_P (TREE_TYPE (var))
-      && var_alias_set != 0
-      && mem_alias_set != 0)
-    {
-      HOST_WIDE_INT ptr_alias_set = get_alias_set (ptr);
-      if (ptr_alias_set == var_alias_set)
-       {
-         alias_stats.alias_noalias++;
-         alias_stats.tbaa_resolved++;
-         return false;
-       }
-    }
-
   /* If the alias sets don't conflict then MEM cannot alias VAR.  */
   if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
     {
Comment 36 CVS Commits 2005-07-26 19:54:00 UTC
Subject: Bug 22591

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dnovillo@gcc.gnu.org	2005-07-26 19:53:54

Modified files:
	gcc            : ChangeLog tree-ssa-alias.c 
	gcc/testsuite  : ChangeLog 
	gcc/testsuite/gcc.dg/tree-ssa: 20030807-7.c 
Added files:
	gcc/testsuite/gcc.dg/tree-ssa: pr22591.c 

Log message:
	PR 22591
	* tree-ssa-alias.c (may_alias_p): Remove shortcut that tests
	whether a pointer of type T * may point to objects of type T *.
	
	testsuite/ChangeLog
	
	PR 22591
	* gcc.dg/tree-ssa/pr22591.c: New test.
	* gcc.dg/tree-ssa/20030807-7.c: XFAIL everywhere.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9554&r2=2.9555
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&r1=2.107&r2=2.108
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5824&r2=1.5825
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr22591.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c.diff?cvsroot=gcc&r1=1.4&r2=1.5

Comment 37 Diego Novillo 2005-07-26 20:04:15 UTC
Fixed.  http://gcc.gnu.org/ml/gcc-patches/2005-07/msg01749.html
Comment 38 Andrew Pinski 2005-07-26 20:06:45 UTC
Subject: Re:  [4.0/4.1 Regression] wrong alias information causes an incorrect redundant load elimination

> 
> 
> ------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-07-26 20:04 -------
> 
> Fixed.  http://gcc.gnu.org/ml/gcc-patches/2005-07/msg01749.html

On the 4.0 branch too?

-- Pinski
Comment 39 Steven Bosscher 2005-07-26 20:43:48 UTC
This is not yet fixed.  The 4.0 branch has the same problem. 
 
Comment 40 Steven Bosscher 2005-07-26 20:44:33 UTC
4.0 only now. 
Comment 41 CVS Commits 2005-07-26 20:54:40 UTC
Subject: Bug 22591

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	dnovillo@gcc.gnu.org	2005-07-26 20:54:31

Modified files:
	gcc            : ChangeLog tree-ssa-alias.c 
	gcc/testsuite  : ChangeLog 
	gcc/testsuite/gcc.dg/tree-ssa: 20030807-7.c 
Added files:
	gcc/testsuite/gcc.dg/tree-ssa: pr22591.c 

Log message:
	PR 22591
	* tree-ssa-alias.c (may_alias_p): Remove shortcut that tests
	whether a pointer of type T * may point to objects of type T *.
	
	testsuite/ChangeLog
	
	PR 22591
	* gcc.dg/tree-ssa/pr22591.c: New test.
	* gcc.dg/tree-ssa/20030807-7.c: XFAIL everywhere.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.332&r2=2.7592.2.333
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.71.2.1&r2=2.71.2.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.5084.2.301&r2=1.5084.2.302
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr22591.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=NONE&r2=1.1.2.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.3&r2=1.3.36.1

Comment 42 Diego Novillo 2005-07-26 20:56:09 UTC
(In reply to comment #39)
> This is not yet fixed.  The 4.0 branch has the same problem. 
>  
You are not very patient, are you?
Comment 43 Steven Bosscher 2005-07-26 22:00:49 UTC
You just closed the bug before it was fixed everywhere.  I don't understand 
your grim comment. 
 
Comment 44 Diego Novillo 2005-07-26 22:24:37 UTC
Subject: Re:  [4.0 regression] wrong alias information causes an incorrect redundant load elimination

On Tue, Jul 26, 2005 at 10:00:51PM -0000, steven at gcc dot gnu dot org wrote:

> You just closed the bug before it was fixed everywhere.  I don't understand 
> your grim comment. 
>  
Tried to be sarcastic but forgot the smiley.  Sorry.
Comment 45 Jonathan Wakely 2005-07-27 13:24:54 UTC
*** Bug 22513 has been marked as a duplicate of this bug. ***
Comment 46 Simon Finn 2005-07-27 15:04:00 UTC
Thanks everyone. I'm really impressed by the effectiveness of the collaborative
debugging process.
Comment 47 CVS Commits 2005-08-03 18:25:37 UTC
Subject: Bug 22591

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	apple-local-200502-branch
Changes by:	mrs@gcc.gnu.org	2005-08-03 18:25:16

Modified files:
	gcc            : tree-ssa-alias.c ChangeLog 

Log message:
	PR 22591
	* tree-ssa-alias.c (may_alias_p): Remove shortcut that tests
	whether a pointer of type T * may point to objects of type T *.
	Radar 4203511

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.68.4.1&r2=2.68.4.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.7489.2.17&r2=2.7489.2.18