https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102943
--- Comment #14 from rguenther at suse dot de <rguenther at suse dot de> --- On Wed, 3 Nov 2021, amacleod at redhat dot com wrote: > 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. In other places we use one level indirection when we want to visit in a particular CFG order. We have a mapping bb-index to CFG-order and a back-mapping CFG-order to bb-index, then the bitmap is set up to contain CFG-order[bb_index] and the bitmap_first_set_bit result is indirected via bb_index[CFG-order]. That gives the desired ordering of the bitmap based worklist at the expense of two int->int maps.
