[Bug middle-end/61571] New: bad aliasing --> wrong FRE

[Bug middle-end/61571] New: bad aliasing --> wrong FRE

[xinliangli at gmail dot com]

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

            Bug ID: 61571
           Summary: bad aliasing --> wrong FRE
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: xinliangli at gmail dot com

Compile the attached source with -m32 -std=c++11 -O2 on x86, the program will
crash. It runs fine with -m32 -std=c++11 -O2 -fno-tree-pre -fno-tree-fre.

(same failure is also observed on arm target).

The bad FRE happens in list<int>::merge function. list<int>::splice needs to be
inlined to trigger the bad CSE.

The problematic CSE is this one:

list<int>::merge (...)
 {

     if (this != &__c)
    {
        iterator __f1 = begin();   
        iterator __e1 = end();
        iterator __f2 = __c.begin(); // this one
        ...
        while (...)
        {
        }

       // inline instance of splice:


    if (!__c.empty())
    {
        __node_pointer __f = __c.__end_.__next_;   // and this one
        __node_pointer __l = __c.__end_.__prev_;
        base::__unlink_nodes(__f, __l);
        __link_nodes(__p.__ptr_, __f, __l);
        base::__sz() += __c.__sz();
        __c.__sz() = 0;
    }

Note begin() method accesses __c.__end_.__next_.

[Bug middle-end/61571] bad aliasing --> wrong FRE

[xinliangli at gmail dot com]

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

--- Comment #1 from davidxl <xinliangli at gmail dot com> ---
Created attachment 32979
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=32979&action=edit
source file

[Bug middle-end/61571] bad aliasing --> wrong FRE

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-06-23
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.  Confirmed with 4.9 at least.

[Bug middle-end/61571] bad aliasing --> wrong FRE

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |INVALID

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm.

  <bb 3>:
  # VUSE <.MEM_9(D)>
  # PT = nonlocal escaped
  _64 = MEM[(struct __list_imp *)this_7(D)].__end_.__next_;
  # PT = nonlocal escaped
  __f1$__ptr__60 = _64;
  # PT = nonlocal
  _10 = &MEM[(struct __list_imp *)this_7(D)].__end_;
  # PT = nonlocal
  __e1$__ptr__59 = _10;
  # VUSE <.MEM_9(D)>
  # PT = nonlocal escaped
  _11 = MEM[(struct __list_imp *)__c_8(D)].__end_.__next_;
...

  <bb 12>:
  # __ds_1 = PHI <1(9), __ds_35(11)>
  # .MEM_4 = PHI <.MEM_5(9), .MEM_4(11)>
...

  <bb 16>:
  # PT = nonlocal
  _95 = &MEM[(struct __libcpp_compressed_pair_imp *)this_7(D) + 8B].__first_;
  # PT = nonlocal
  _130 = _95;
  # PT = nonlocal
  _37 = _130;
  # VUSE <.MEM_4>
  _38 = MEM[(size_type &)this_7(D) + 8];
...
  # .MEM_132 = VDEF <.MEM_45>
  _97->D.24075.__next_ = _98;
  # VUSE <.MEM_132>
  # PT = nonlocal escaped null
  _99 = __l_48->D.24075.__next_;
  # .MEM_133 = VDEF <.MEM_132>
  _99->D.24075.__prev_ = _97;
  # PT = nonlocal escaped null
  __x_135 = __f1$__ptr__63;
  # PT = nonlocal escaped null
  __x$__ptr__50 = __x_135;
  goto <bb 19>;



  <bb 20>:
...
  # .MEM_137 = VDEF <.MEM_133>
  _51->D.24075.__next_ = __f_46;
  # .MEM_138 = VDEF <.MEM_137>
  __f_46->D.24075.__prev_ = _51;
  # .MEM_139 = VDEF <.MEM_138>
  _52->D.24075.__prev_ = __l_48;
  # .MEM_140 = VDEF <.MEM_139>
  __l_48->D.24075.__next_ = _52;
  # PT = nonlocal escaped null
  __f1$__ptr__58 = __m2_49;
  goto <bb 22>;


  <bb 22>:
  # .MEM_5 = PHI <.MEM_9(D)(3), .MEM_140(20), .MEM_5(21)>
...

  <bb 27>:
  # VUSE <.MEM_5>
  # PT = nonlocal escaped
  __f_120 = __c_8(D)->D.23569.__end_.__next_;
  # VUSE <.MEM_5>
  # PT = nonlocal escaped
  __l_121 = __c_8(D)->D.23569.__end_.__prev_;

and fixed with -fno-strict-aliasing.  I've repeatedly seen up/down-casting
issues in container implementations.

We have for example a store via

__l_48->D.24075.__next_

when looking for __c_8(D)->D.23569.__end_.__next_

And we hit

  /* Do type-based disambiguation.  */
  if (base1_alias_set != base2_alias_set
      && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
    return false;

as one access is done via struct list and one is done via struct __list_node.
struct list has a __list_node_base<value_type, __void_pointer> __end_
member and you are accessing that via a __list_node type which is derived
from that.  That's clearly invalid.

That is, stuff like

       return iterator(static_cast<__node_pointer>(
                     
pointer_traits<__node_base_pointer>::pointer_to(__end_)));

breaks TBAA rules.

[Bug middle-end/61571] bad aliasing --> wrong FRE

[xinliangli at gmail dot com]

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

--- Comment #5 from davidxl <xinliangli at gmail dot com> ---
Thanks for the analysis.  I agree it is invalid to use -fstrict-aliasing for
the code. 

The implementation tries to save some space in __list_impl class by making the
sentinel marker __end_ to be just __list_node_base, but it is linked with other
__list_node type objects.

David