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

[Jakub Jelinek <jakub at redhat dot com>]

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.

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.

	Jakub