Re: [PATCH][RFC] Fix PR63155 (some more)

[Richard Biener <rguenther at suse dot de>]

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.