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.
