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_.
Created attachment 32979 [details] source file
The issue exists in trunk and as early as 4.7 (that i have tested).
I will have a look. Confirmed with 4.9 at least.
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.
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