segfaults with -O2 -flto, doesn't with -O2.
Created attachment 18355 [details] testcase somewhat reduced testcase. Manual love and analyzing necessary.
Confirmed.
The testcase was reduced to an invalid one.
I'm reducing again, from a single-file testcase.
FYI, this testcase also fails on alpha: FAIL: ext/pb_ds/regression/hash_data_map_rand.cc execution test (I was not able to debug it properly, will wait for your reduced testcase...)
Created attachment 18426 [details] single-file testcase It reduced to nonsense again. *sigh* Attaching the single-file input for reference.
Weird. A trigger for the failure with -flto is the removal of a dead store in container_rand_regression_test<Cntnr>::assignment_operator(). We remove tmp.D.3238.D.3239.D.3240.D.3090.D.3046.D.3014._vptr.hash_load_check_resize_trigger = &_ZTVN10__gnu_pbds6detail15gp_ht_map_data_INS_4test10basic_typeES3_NS2_4hashESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0ENS2_27direct_mod_range_hashing_t_IS9_EENS2_21quadratic_probe_fn_t_IS3_S9_EENS_27hash_standard_resize_policyINS2_25hash_prime_size_policy_t_ENS2_33hash_load_check_resize_trigger_t_IS9_Lm1ELm8ELm1ELm2ELb1EEELb1EmEEEE[2]; at the beginning of BB 21. If you retain that store then this will be the only assembly code difference and the segfault disappears. Reduced flags: -O2 -fno-tree-pre -fno-ivopts -fno-tree-loop-optimize -fno-dse -fno-gcse -fno-tree-sink -fno-tree-dominator-opts -fno-tree-vrp -fno-tree-fre either specifying -fno-strict-aliasing or -fno-tree-dse also fixes the segfault. The funny thing is that trunk (or the branch w/o -flto) also removes that store. I'll attach a slightly reduced testcase momentarily (it just reduces the amount of instantiations, not the amount of source). The testcase is rather awkward in that it relies on randomness to perform the operations.
Created attachment 18437 [details] testcase, simplified
In fact the code generated by the C++ frontend (or the library) looks bogus. other.1157_15 = (const struct hash_eq_fn *) D.107435_2; this.1158_16 = (struct hash_eq_fn *) D.107436_4; other.1161_17 = (struct equal_to *) other.1157_15; this.1162_18 = (struct equal_to *) this.1158_16; __tmp = *this.1162_18; *this.1162_18 = *other.1161_17; *other.1161_17 = __tmp; this swaps the first byte(!) of the struct which contains the vtable pointer. In fact gp_hash_table::swap(gp_hash_table&) seems to cause this. Forcing to not inline that function fixes the issue as well. (so the dead store really is not dead - but only because of that bogus swap). Thus, things like void _M_swap(_Hash_code_base& __x) { std::swap(_M_extract, __x._M_extract); std::swap(_M_eq, __x._M_eq); std::swap(_M_h1, __x._M_h1); std::swap(_M_h2, __x._M_h2); } protected: _ExtractKey _M_extract; _Equal _M_eq; _H1 _M_h1; _H2 _M_h2; }; seem to corrupt the vtable pointer as the empty function classes are tail-packed into that field. OTOH std::swap should do nothing for empty classes, but instead it does ;; Function void std::swap(_Tp&, _Tp&) [with _Tp = std::equal_to<__gnu_pbds::test::basic_type>] (null) ;; enabled by -tree-original { struct equal_to __tmp; struct equal_to __tmp; <<cleanup_point <<< Unknown tree: expr_stmt (void) (__tmp = TARGET_EXPR <D.100064, *(const struct equal_to &) (const struct equal_to *) __a>) >>> >>; <<cleanup_point <<< Unknown tree: expr_stmt (void) (*(struct equal_to *) __a = *(const struct equal_to &) (const struct equal_to *) __b) >>> >>; <<cleanup_point <<< Unknown tree: expr_stmt (void) (*(struct equal_to *) __b = *(const struct equal_to &) (const struct equal_to *) &__tmp) >>> >>; } bah. Paolo, who is at fault here? The library or the frontend? The issue must be latent on trunk.
Richard, I have no idea, at the moment. Frankly however, I know, or at least strongly suspect basing on past and still open issues, that pb_ds cannot be fully trusted, isn't really maintained as it should and unfortunately the original author isn't available anymore. Sorry, but I don't think I'm going to spend much time on this issue or anything having to do with this ext/ code, for that matter. I'm CC-ing Benjamin - for sure he knows the code much better than me - just for his information.
Thanks paolo. It is btw _ZN10__gnu_pbds13gp_hash_tableINS_4test10basic_typeES2_NS1_4hashESt8equal_toIS2_ENS1_27direct_mod_range_hashing_t_IN9__gnu_cxx15throw_allocatorIS2_EEEENS1_21quadratic_probe_fn_t_IS2_S9_EENS_27hash_standard_resize_policyINS1_25hash_prime_size_policy_t_ENS1_33hash_load_check_resize_trigger_t_IS9_Lm1ELm8ELm1ELm2ELb1EEELb1EmEELb0ES9_E4swapERSI_ that has this issue. That is, basic_hash_table<...>::swap which eventually ends up - somewhere (it's a maze in that libstdc++!)
Instantiating _ZN10__gnu_pbds13gp_hash_tableINS_4test10basic_typeES2_NS1_4hashESt8equal_toIS2_ENS1_27direct_mod_range_hashing_t_IN9__gnu_cxx15throw_allocatorIS2_EEEENS1_21quadratic_probe_fn_t_IS2_S9_EENS_27hash_standard_resize_policyINS1_25hash_prime_size_policy_t_ENS1_33hash_load_check_resize_trigger_t_IS9_Lj1ELj8ELj1ELj2ELb1EEELb1EjEELb0ES9_EaSERKSI_ tmpD.97537.D.92388.D.92047.D.91561.D.91103.D.89988.D.89882._vptr.hash_load_check_resize_triggerD.89847 other.1162D.116069_22 = (struct equal_toD.83779 *) &tmpD.97537.D.92388.D.92047.D.91561; *this.1163D.116068_23 = *other.1162D.116069_22; Dissecting the types of tmpD.97537.D.92388.D.92047.D.91561.D.91103.D.89988.D.89882._vptr.hash_load_check_resize_triggerD.89847: <record_type 0xb55beaf0 gp_hash_table fields <field_decl 0xb52cef60 D.92388 type <record_type 0xb525f540 basic_hash_table offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> <record_type 0xb525f540 basic_hash_table fields <field_decl 0xb52cede0 D.92047 type <record_type 0xb5266c40 container_base> offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> <record_type 0xb5266c40 container_base fields <field_decl 0xb52cec60 D.91561 type <record_type 0xb527a000 gp_ht_map_data_ offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> <record_type 0xb527a000 gp_ht_map_data_ fields <field_decl 0xb52ce6c0 D.91103 type <record_type 0xb5555e00 hash_standard_resize_policy offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> record_type 0xb5555e00 hash_standard_resize_policy fields <field_decl 0xb528b360 D.89988 type <record_type 0xb567ebd0 hash_load_check_resize_trigger_t_ offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> <record_type 0xb567ebd0 hash_load_check_resize_trigger_t_ fields <field_decl 0xb528b180 D.89882 type <record_type 0xb527f2a0 hash_load_check_resize_trigger offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> <record_type 0xb527f2a0 hash_load_check_resize_trigger fields <field_decl 0xb526ad20 _vptr.hash_load_check_resize_trigger type <pointer_type 0xb7d80e00 type <pointer_type 0xb7d80cb0 __vtbl_ptr_type> offset <integer_cst 0xb7c9a310 0> bit offset <integer_cst 0xb7c9a7e0 0> Shows that other.1162D.116069_22 = (struct equal_toD.83779 *) &tmpD.97537.D.92388.D.92047.D.91561; takes the address of gp_ht_map_data_. There is no equal_to typed field in this struct. So the question boils down to who is responsible for the std::swap of this "field" and how do we end up with this code. It seems to be _ZN10__gnu_pbds6detail15gp_ht_map_data_INS_4test10basic_typeES3_NS2_4hashESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0ENS2_27direct_mod_range_hashing_t_IS9_EENS2_21quadratic_probe_fn_t_IS3_S9_EENS_27hash_standard_resize_policyINS2_25hash_prime_size_policy_t_ENS2_33hash_load_check_resize_trigger_t_IS9_Lj1ELj8ELj1ELj2ELb1EEELb1EjEEE4swapERSJ_ calling other.1158D.107162 = (const struct hash_eq_fnD.89704 *) otherD.90715; this.1159D.107163 = (struct hash_eq_fnD.89704 *) thisD.90714; _ZN10__gnu_pbds6detail10hash_eq_fnINS_4test10basic_typeESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0EE4swapERKS9_D.89731 (this.1159D.107163, other.1158D.107162); ;; Function swap (_ZN10__gnu_pbds6detail10hash_eq_fnINS_4test10basic_typeESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0EE4swapERKS9_) swap (struct hash_eq_fnD.89704 * const thisD.89732, const struct hash_eq_fnD.89704 & otherD.89733) { struct equal_toD.83779 * this.1163D.107177; struct equal_toD.83779 * other.1162D.107176; <bb 2>: other.1162D.107176 = (struct equal_toD.83779 *) otherD.89733; this.1163D.107177 = (struct equal_toD.83779 *) thisD.89732; _ZSt4swapISt8equal_toIN10__gnu_pbds4test10basic_typeEEEvRT_S6_D.99289 (this.1163D.107177, other.1162D.107176); return; } ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp: PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); std::swap(m_num_e, other.m_num_e); std::swap(m_num_used_e, other.m_num_used_e); std::swap(m_entries, other.m_entries); ranged_probe_fn_base::swap(other); hash_eq_fn_base::swap(other); resize_base::swap(other); _GLIBCXX_DEBUG_ONLY(debug_base::swap(other)); _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); } where hash_eq_fn_base::swap(other); is the culprit. ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp: PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: swap(const PB_DS_CLASS_C_DEC& other) { std::swap((Eq_Fn& )(*this), (Eq_Fn& )other); } WTF?
This pattern happens more often in pb_ds. If I replace the casts by static_cast<>s and const_cast<>s the problem persists though. I do not see that the frontend produces a FIELD_DECL for the Eq_Fn base of hash_eq_fn (nor a field for hash_eq_fn base of gp_ht_map_data_). Thus the static_cast fails to do the proper pointer adjustment to a padding field (but stays pointing to the vtable pointer). Obviously hash_eq_fn and Eq_Fn as they are empty classes end up in tail-padding somewhere. Let's get some C++ folks in here.
It seems that on trunk the swap other.1157_15 = (const struct hash_eq_fn *) D.107435_2; this.1158_16 = (struct hash_eq_fn *) D.107436_4; other.1161_17 = (struct equal_to *) other.1157_15; this.1162_18 = (struct equal_to *) this.1158_16; __tmp = *this.1162_18; *this.1162_18 = *other.1161_17; *other.1161_17 = __tmp; is optimized away - likely by some langhooks.expr_size magic. It feels like some Deja-vu, but why is the frontend emitting these assignments at all? Didn't we think of killing them during gimplification at least? Either way we need to address this, also for merging fld (see cp_expr_size).
Index: cp/cp-gimplify.c =================================================================== --- cp/cp-gimplify.c (revision 151156) +++ cp/cp-gimplify.c (working copy) @@ -853,6 +853,15 @@ cp_genericize_r (tree *stmt_p, int *walk *walk_subtrees = 0; } + else if (TREE_CODE (stmt) == MODIFY_EXPR + && (integer_zerop (cp_expr_size (TREE_OPERAND (stmt, 0))) + || integer_zerop (cp_expr_size (TREE_OPERAND (stmt, 1))))) + { + *stmt_p = build2 (COMPOUND_EXPR, TREE_TYPE (stmt), + TREE_OPERAND (stmt, 0), + TREE_OPERAND (stmt, 1)); + } + pointer_set_insert (p_set, *stmt_p); return NULL; fixes the testcase on the lto branch. I'm going to test this patch on trunk. Jason - might there be any reason this is not correct?
Subject: Re: FAIL: ext/pb_ds/regression/hash_data_map_rand.cc On 08/28/2009 06:59 AM, rguenth at gcc dot gnu dot org wrote: > Jason - might there be any reason this is not correct? Looks fine to me.
Subject: Bug 41058 Author: rguenth Date: Fri Aug 28 19:36:05 2009 New Revision: 151176 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=151176 Log: 2009-08-28 Richard Guenther <rguenther@suse.de> PR lto/41058 * cp-gimplify.c (cp_genericize_r): Do not leak zero-sized stores into the generic IL. Modified: trunk/gcc/cp/ChangeLog trunk/gcc/cp/cp-gimplify.c
Fixed. (bah, it didn't fix all the others ...)
Sigh, the patch doesn't fix alpha failure :(
Subject: Re: FAIL: ext/pb_ds/regression/hash_data_map_rand.cc On Sat, 29 Aug 2009, ubizjak at gmail dot com wrote: > ------- Comment #19 from ubizjak at gmail dot com 2009-08-29 19:52 ------- > Sigh, the patch doesn't fix alpha failure :( It also doensn't fix reliably the failure on i?86. Is your alpha failure on lto branch or on trunk? Richard.
(In reply to comment #20) > > Sigh, the patch doesn't fix alpha failure :( > > It also doensn't fix reliably the failure on i?86. Is your alpha > failure on lto branch or on trunk? It is on the trunk. However, I have started debugging this, and the problem is that the pointer to LSDA structure gets corrupted and test aborts when parsing LSDA header with parse_lsda_header. The actual abort is triggered in read_encoded_value_with_base. Exception data points to _ZN10__gnu_pbds6detail15gp_ht_map_data_INS_4test10basic_typeES3_NS2_4hashESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0ENS2_27direct_mod_range_hashing_t_IS9_EENS2_21quadratic_probe_fn_t_IS3_S9_EENS_27hash_standard_resize_policyINS2_25hash_prime_size_policy_t_ENS2_33hash_load_check_resize_trigger_t_IS9_Lm1ELm8ELm1ELm2ELb1EEELb1EmEEEC2ERKSJ_ aka: __gnu_pbds::detail::gp_ht_map_data_<__gnu_pbds::test::basic_type, __gnu_pbds::test::basic_type, __gnu_pbds::test::hash, std::equal_to<__gnu_pbds::test::basic_type>, __gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type>, false, __gnu_pbds::test::direct_mod_range_hashing_t_<__gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type> >, __gnu_pbds::test::quadratic_probe_fn_t_<__gnu_pbds::test::basic_type, __gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type> >, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::test::hash_prime_size_policy_t_, __gnu_pbds::test::hash_load_check_resize_trigger_t_<__gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type>, 1ul, 8ul, 1ul, 2ul, true>, true, unsigned long> >::gp_ht_map_data_(__gnu_pbds::detail::gp_ht_map_data_<__gnu_pbds::test::basic_type, __gnu_pbds::test::basic_type, __gnu_pbds::test::hash, std::equal_to<__gnu_pbds::test::basic_type>, __gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type>, false, __gnu_pbds::test::direct_mod_range_hashing_t_<__gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type> >, __gnu_pbds::test::quadratic_probe_fn_t_<__gnu_pbds::test::basic_type, __gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type> >, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::test::hash_prime_size_policy_t_, __gnu_pbds::test::hash_load_check_resize_trigger_t_<__gnu_cxx::throw_allocator<__gnu_pbds::test::basic_type>, 1ul, 8ul, 1ul, 2ul, true>, true, unsigned long> > const&) Defined in: file /home/uros/gcc-build/alphaev68-unknown-linux-gnu/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp, line 144. (2 locations) Return address points just after the call to: 12000f9e8: d3 da 5f d3 bsr ra,120006538 <_ZN9__gnu_cxx16probability_base19throw_conditionallyEv+0x8> > 12000f9ec: 00 00 fe 2f unop 12000f9f0: 00 00 fe 2f unop This is hard to debug, since this is conditional exception, and the condition that triggers this exception depends on a random value. I have checked that it is not LSDA data that gets corrupted, but the pointer to LSDA data: failed: 0x1201bb405 objdump --section=.gcc_except_table -s hash_data_map_rand.test 1201bb3f4 ff9b2d01 23a80148 c40400f0 0208b404 ..-.#..H........ >1201bb404 01880308 e00301d8 0304c404 009c0414 ................ 1201bb414 e80400e0 04040000 01000000 00000000 ................ 1201bb424 ff9b2101 17ac0208 d80401d8 0308fc03 ..!............. 1201bb434 05940404 a80400d0 04380000 7f000000 .........8...... 1201bb444 7f7d0000 00000000 ff9b4901 41d4015c .}........I.A..\ correct: 0x1201bb3f4 1201bb3e4 00ffff01 08240848 005c0400 00000000 .....$.H.\...... >1201bb3f4 ff9b2d01 23a80148 c40400f0 0208b404 ..-.#..H........ 1201bb404 01880308 e00301d8 0304c404 009c0414 ................ 1201bb414 e80400e0 04040000 01000000 00000000 ................ 1201bb424 ff9b2101 17ac0208 d80401d8 0308fc03 ..!............. 1201bb434 05940404 a80400d0 04380000 7f000000 .........8...... So, the pointer to LSDA is off by 0x11.
Digging deeper, it smells like a linker error, at least on alpha (please note that I used -static for final linking to ease debugging a bit): FDE that corresponds to _ZN10__gnu_pbds6detail15gp_ht_map_data_INS_4test10basic_typeES3_NS2_4hashESt8equal_toIS3_EN9__gnu_cxx15throw_allocatorIS3_EELb0ENS2_27direct_mod_range_hashing_t_IS9_EENS2_21quadratic_probe_fn_t_IS3_S9_EENS_27hash_standard_resize_policyINS2_25hash_prime_size_policy_t_ENS2_33hash_load_check_resize_trigger_t_IS9_Lm1ELm8ELm1ELm2ELb1EEELb1EmEEEC2ERKSJ_ is defined as: $LSFDE1017: .4byte $LEFDE1017-$LASFDE1017 $LASFDE1017: .4byte $LASFDE1017-$Lframe1 .4byte $LFB5855-. .4byte $LFE5855-$LFB5855 .uleb128 0x4 >> .4byte $LLSDA5855-. .byte 0x4 .4byte $LCFI1142-$LFB5855 .byte 0xe .uleb128 0x40 .byte 0x4 and corresponding LSDA: $LLSDA5855: .byte 0xff .byte 0x9b .uleb128 $LLSDATT5855-$LLSDATTD5855 $LLSDATTD5855: .byte 0x1 .uleb128 $LLSDACSE5855-$LLSDACSB5855 $LLSDACSB5855: .uleb128 $LEHB373-$LFB5855 .uleb128 $LEHE373-$LEHB373 .uleb128 $L2169-$LFB5855 .uleb128 0x0 Now, liker links LSDA into FDE as: (gdb) x/32cx fde 0x12019e770: 0x34 0x00 0x00 0x00 0xf4 0x1a 0x00 0x00 0x12019e778: 0xc8 0x11 0xe7 0xff 0x88 0x02 0x00 0x00 0x12019e780: 0x04 0x84 0xcc 0x01 0x00 0x50 0x0e 0x40 0x12019e788: 0x58 0x8e 0x02 0x8b 0x05 0x89 0x07 0x58 So, linker puts 0x0001cc84 at PC 0x12019e781. Adding both together (as marked by ">>" above), we get 0x1201bb405. This value is wrong, LSDA is located at 0x1201bb3f4 (see comment #21). So, linker is perhaps creating address, relative to start of FDE instead of current address.
Perhaps Jakub can help from here...
If you think it is a linker bug, try to see if the LSDA pointer in readelf -wf dump is correct when you link with --traditional-format. And, file a binutils bugreport and attach everything needed to reproduce it there. I don't have access to alpha, so would need something reproduceable with cross-binutils.
(In reply to comment #24) > If you think it is a linker bug, try to see if the LSDA pointer in readelf -wf > dump is correct when you link with --traditional-format. And, file a binutils No, with --traditional-format, it fails the same way. In this case, LSDA is parsed from __gcc_personality_v0 and without --traditional-format, LSDA is parsed from uw_frame_state_for. The target is always 0x11 off.
Created attachment 18456 [details] alpha dump This is the dump. Please look for $LSFDE285: $LSFDE285: .4byte $LEFDE285-$LASFDE285 $LASFDE285: .4byte $LASFDE285-$Lframe1 .4byte $LFB5858-. .4byte $LFE5858-$LFB5858 .uleb128 0x4 >>> .4byte $LLSDA5858-. .byte 0x4 .4byte $LCFI1142-$LFB5858 .byte 0xe The line that will fail to link to correct LSDA is marked with >>>.
(In reply to comment #26) > The line that will fail to link to correct LSDA is marked with >>>. This issue is reported in binutils bugzilla as Bug 10579 [1]. [1] http://sourceware.org/bugzilla/show_bug.cgi?id=10579
This may be related to PR 37144.
(In reply to comment #28) > This may be related to PR 37144. No, it was assembler bug with 2.19.1 in my case.
Even if the bug is fixed, I think it would be nice to have it properly categorization: I can see only a C++ front-end patch in the trail, thus I'm changing the category to C++. If I'm wrong, please improve it...
Let's reopen it as LTO specific. The test still fails on i?86 with the original multi-file testcase and -flto. There are also other similar pb_ds fails.