This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][RFC] Fix PR63155 (some more)
- From: Richard Biener <rguenther at suse dot de>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Wed, 19 Sep 2018 16:04:54 +0200 (CEST)
- Subject: Re: [PATCH][RFC] Fix PR63155 (some more)
- References: <alpine.LSU.2.20.1809191455250.16707@zhemvz.fhfr.qr> <20180919132745.GD8250@tucnak>
On Wed, 19 Sep 2018, Jakub Jelinek wrote:
> On Wed, Sep 19, 2018 at 03:06:30PM +0200, Richard Biener wrote:
> >
> > The second testcase in the above PR runs into our O(N) bitmap element
> > search limitation and spends 8s (60%) of the compile-time in the SSA propagator
> > engine (when optimizing). The patch improves that to 0.9s (15%). For the
> > first testcase it isn't that bad but still the patch improves CCP from 36% to
> > 14%.
> >
> > The "solution" is to use sbitmap instead of a bitmap to avoid
> > the linearity when doing add_ssa_edge. We pay for that (but not
> > actually with the testcases) with a linear-time bitmap_first_set_bit
> > in process_ssa_edge_worklist. I do not (yet...) have a testcase
>
> Perhaps you could remember the first set bit number in an integral variable
> next to the bitmap. On bitmap_set_bit this would be just a comparison +
> conditional update, in simulate_stmt it would be again conditional on
> clearing the first set bit and in that case it could start from that bit
> onwards rather than from the beginning (EXECUTE_IF_SET_IN_BITMAP), similarly
> in process_ssa_edge_worklist (non-conditional in that case, we are always
> clearing the first bit). Or instead of tracking exact first bit track
> it lazily, i.e. just remember the smallest bitnum we've set and in
> process_ssa_edge_worklist don't use bitmap_first_set_bit, but walk from
> that minimum using EXECUTE_IF_SET_IN_BITMAP and update the minimum to
> whatever we've found.
I thought about that but as you say it's easily invalidated and we can
only optimize the searching start point. So it felt somewhat like
a hack ;)
I can still do that if you think that otherwise using an sbitmap
is fine (I'm not 100% convinced about that yet).
> Similarly, empty_p can be done linearly by keeping on the side the count of
> set bits and updating it on set_bit when previously not set, as well on
> clear_bit.
I elided empty_p by re-using the fact that bitmap_first_set_bit
already has to do the walk (and may fail). Of course using a
on-the-side count might be more optimal (I was wondering why
sbitmap itself didn't have that).
I wonder if reviving Stevens [patch][RFC] bitmaps as lists *or* trees
makes more sense so we can turn this kind of random-access bitmaps
to tree view.
Richard.