https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102943
--- Comment #13 from Andrew Macleod <amacleod at redhat dot com> --- > > > > This is a large CFG, so a linear search of a BB, is bound to be slow. > > Indeed, vec should never have gotten ::contains () ... I'd have > used a regular bitmap, not sbitmap, because we do > > bb = m_update_list.pop (); > > and bitmap_first_set_bit is O(n) for an sbitmap bit O(1) for a bitmap. > If we replaced the current vector with just the bitmap implementation, then this would be the ideal way to do it. However, the propagation engine is suppose to call add_to_update in a (mostly) breadth-first way so that changes being pushed minimize turmoil. As I look closer, I see that this code doesn't really end up doing that properly now anyway. I'll do some experiments and either fix the current code to do breadth right, or just switch to the bitmap solution you suggest which will then be quasi-random. And you are right.. that contains should never have gotten in there, let alone been used by me. :-) Must have been in a hurry that day.
