Bug 36149 - -O2 optimization generates wrong code
Summary: -O2 optimization generates wrong code
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 4.1.2
: P3 normal
Target Milestone: 4.2.4
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, wrong-code
Depends on:
Blocks:
 
Reported: 2008-05-06 07:14 UTC by Edin Hodzic
Modified: 2008-12-28 06:06 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.2.4 4.3.0
Known to fail: 4.0.4 4.1.3
Last reconfirmed: 2008-06-06 21:32:26


Attachments
A relatively simple self contained piece of code that reproduces the problem. (2.57 KB, application/x-compressed-tar)
2008-06-06 21:13 UTC, Edin Hodzic
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Edin Hodzic 2008-05-06 07:14:05 UTC
GCC version:
gcc (GCC) 4.1.2 20070925 (Red Hat 4.1.2-27)

It is really hard to reproduce and goes away even with minimal code changes.

Happens in a unit test. 

Host is x86_64: "model name      : Intel(R) Core(TM)2 CPU          6300  @ 1.86GHz" from /proc/cpuinfo.

The following snippets might be useful to someone perhaps:

C code:

    void pRemove(CLASS *d)
    {
      LC(d)->m_back->m_fwd = LC(d)->m_fwd;
      LC(d)->m_fwd->m_back = LC(d)->m_back;
    }

    void prepend(CLASS *a)
    {
        pRemove(a);
        LC(a)->m_fwd = head.m_fwd;
        head.m_fwd->m_back = LC(a);
        LC(a)->m_back = &head;
        head.m_fwd = LC(a);
    }

MapList::add():
            // ...
            m_list.remove(removed);
            if (fTop) {
                  m_list.prepend(item);
            } else {
            // ...


Disassembly w/ comments:

 8053c7f:       80 7d 8f 00             cmpb   $0x0,0xffffff8f(%ebp)        ###
if (fTop)
 8053c83:       89 02                   mov    %eax,(%edx)
 8053c85:       8b 07                   mov    (%edi),%eax
 8053c87:       89 3f                   mov    %edi,(%edi)
 8053c89:       89 50 04                mov    %edx,0x4(%eax)
 8053c8c:       89 7f 04                mov    %edi,0x4(%edi)

The above few lines perform the remove(removed) call and the if test out of
order, which is OK. After that, variables look like this:
14: item.m_back = (Vapi::DoubleLink *) 0x81d4400
13: item.m_fwd = (Vapi::DoubleLink *) 0x81d4400
12: item = (DownloadQueue::DQ_Item *) 0x81d4400
11: this->m_list.head.m_back = (Vapi::DoubleLink *) 0xffc26b3c
10: this->m_list.head.m_fwd = (Vapi::DoubleLink *) 0xffc26b3c
9: &this->m_list.head = (Vapi::DoubleLink *) 0xffc26b3c
8: removed.m_back = (Vapi::DoubleLink *) 0x81d43b0
7: removed.m_fwd = (Vapi::DoubleLink *) 0x81d43b0
6: removed = (DownloadQueue::DQ_Item *) 0x81d43b0

The m_list.head is empty, item is on no list, and removed is on no list.

Then the code for prepend(item) is supposed to execute:

 8053c8f:       0f 84 bf 01 00 00       je     8053e54
<DownloadQueue::DQ_MapList::add(DownloadQueue::DQ_Item*, bool)+0x354>
 8053c95:       8b 55 0c                mov    0xc(%ebp),%edx               ###
edx = item
 8053c98:       8b 42 04                mov    0x4(%edx),%eax               ###
eax = item->m_back (in pRemove)
 8053c9b:       89 d3                   mov    %edx,%ebx                    ###
ebx = item
 8053c9d:       8b 12                   mov    (%edx),%edx                  ###
edx = item->m_fwd
 8053c9f:       89 10                   mov    %edx,(%eax)                  ###
item->m_back->m_fwd = edx (item->m_fwd)
 8053ca1:       8b 13                   mov    (%ebx),%edx                  ###
edx = item->m_fwd
 8053ca3:       89 0b                   mov    %ecx,(%ebx)                  ###
item->m_fwd = %ecx (removed?!)
 8053ca5:       89 42 04                mov    %eax,0x4(%edx)               ###
item->m_fwd->m_back = item->m_back
 8053ca8:       8b 45 9c                mov    0xffffff9c(%ebp),%eax        ###
eax = head
 8053cab:       8b 55 98                mov    0xffffff98(%ebp),%edx        ###
??
 8053cae:       89 59 04                mov    %ebx,0x4(%ecx)               ###
removed->m_back = item (?!)
 8053cb1:       89 43 04                mov    %eax,0x4(%ebx)               ###
item->m_back = head
 8053cb4:       89 5a 04                mov    %ebx,0x4(%edx)               ###
?? head->m_back = item
 8053cb7:       8b 5f 20                mov    0x20(%edi),%ebx

But that doesn't look all that great. The compiler somehow tries to interleave
the pRemove and the rest of prepend, but the result is pretty bad:

14: item.m_back = (Vapi::DoubleLink *) 0xffc26b3c
13: item.m_fwd = (Vapi::DoubleLink *) 0x81d43b0
12: item = (DownloadQueue::DQ_Item *) 0x81d4400
11: this->m_list.head.m_back = (Vapi::DoubleLink *) 0xffc26b3c
10: this->m_list.head.m_fwd = (Vapi::DoubleLink *) 0x81d4400
9: &this->m_list.head = (Vapi::DoubleLink *) 0xffc26b3c
8: removed.m_back = (Vapi::DoubleLink *) 0x81d4400
7: removed.m_fwd = (Vapi::DoubleLink *) 0x81d43b0
6: removed = (DownloadQueue::DQ_Item *) 0x81d43b0

Item and removed point to each other, with one of their pointers, m_list.head
points to item but not with both pointers, item points to head with one of its
pointers...

May not be able to provide full source that reproduces the problem (couldn't generate a short piece of code that reproduces the problem.) But, could perhaps provide additional info.
Comment 1 Edin Hodzic 2008-05-06 07:19:02 UTC
The same code works fine with -O1 and -O3.
Comment 2 Andrew Pinski 2008-05-06 08:23:16 UTC
How is LC defined?
Comment 3 Edin Hodzic 2008-05-06 14:18:59 UTC
    template<class Y> static LINK* LC(Y* X) {
        return static_cast<LINK*>(X);
    }
    template<class Y> static const LINK* LCC(Y* X) {
        return static_cast<const LINK*>(X);
    }
Comment 4 Andrew Pinski 2008-05-06 15:23:13 UTC
This looks like you are violating C/C++ aliasing rules from that definition.
Comment 5 Edin Hodzic 2008-05-06 15:42:56 UTC
Are we missing a const, or would you care to give a bit more specific comment?

I see that:

    template<class Y> static const LINK* LCC(Y* X) {
        return static_cast<const LINK*>(X);
    }

could be missing a const in the declaration of Y* X, should probably be const Y* X. Is that what you're referring to?

Comment 6 Andrew Pinski 2008-05-06 15:45:26 UTC
As I mentioned it looks like you are violating aliasing rules.  Basically you are accessing one type as another.  But without a full testcase I cann't be sure.  Also Does -O2 -fno-strict-aliasing work?
Comment 7 Edin Hodzic 2008-05-06 16:54:20 UTC
-O2 -fno-strict-aliasing does work.

I think the LC and LLC functions always cast from a derived class to a base class. That shouldn't cause aliasing problems, but I need to learn more about that.

Thanks.
Comment 8 Wolfgang Bangerth 2008-05-07 04:17:42 UTC
The point is: without the complete source code nothing definitive can
be said whether it's the compiler's or the programmer's fault. Your chances
that someone will take the time to try to understand what's going on
increase exponentially if you manage to produce a small testcase, whereas
they are pretty low if all you can show is several thousand lines of code.

W.
Comment 9 Edin Hodzic 2008-05-07 06:15:12 UTC
Understood. Just haven't been able to reproduce on a small piece of code :-(

It seems GNU C++ compiler doesn't give strict-aliasing warnings.
Comment 10 Richard Biener 2008-05-07 19:29:52 UTC
Note that gcc 4.1 is known to have some wrong-code bugs regarding aliasing.
Comment 11 Edin Hodzic 2008-06-06 21:13:09 UTC
Created attachment 15727 [details]
A relatively simple self contained piece of code that reproduces the problem.

Please see the comments in the Makefile for info on how to reproduce the problem.
Comment 12 Richard Biener 2008-06-06 21:32:26 UTC
Looks more like one of the known alias related miscompilations of the 4.1
branch.
Comment 13 Andrew Pinski 2008-12-28 06:06:16 UTC
Since 4.1.x is closed, closing as fixed for 4.2.x.