https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113910
--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> --- Note after the proper fix we still have (gdb) p pointer_equiv_class_table->m_searches $17 = 180497 (gdb) p pointer_equiv_class_table->m_collisions $18 = 4101085 (gdb) p pointer_equiv_class_table->m_n_elements $22 = 143701 (gdb) p pointer_equiv_class_table->m_size $23 = 262139 "perfecting" the hash helps (mixing each individual bit number) but then all the time is spent hashing ;) Samples: 177K of event 'cycles:u', Event count (approx.): 232966151280 Overhead Samples Command Shared Object Symbol 35.77% 65423 cc1plus cc1plus [.] bitmap_hash 9.64% 16589 cc1plus cc1plus [.] bitmap_set_bit I think the data structure used is simply far from optimal. Mixing each bitmap word has higher collision rates than the XOR (dropping the XOR of the first bit number). Mixing in ptr->indx as well gives OK collision rates but still 12.78% 16684 cc1plus cc1plus [.] bitmap_set_bit 12.56% 19318 cc1plus cc1plus [.] bitmap_hash XOR for the words ontop of mixing of ptr->indx gets little worse but still reasonable rates with 14.03% 16837 cc1plus cc1plus [.] bitmap_set_bit 6.33% 7694 cc1plus cc1plus [.] insert_updated_phi_node 4.74% 7500 cc1plus cc1plus [.] bitmap_hash
