[Bug tree-optimization/102943] [12 Regression] Jump threader compile-time hog with 521.wrf_r
rguenther at suse dot de
gcc-bugzilla@gcc.gnu.org
Wed Nov 3 14:42:12 GMT 2021
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.
More information about the Gcc-bugs
mailing list