https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63155
--- Comment #29 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #28)
> Created attachment 44724 [details]
> patch for the SSA propagator issue
>
> Using an sbitmap helps. I am testing the attached.
Note there's
void
ssa_propagation_engine::process_ssa_edge_worklist (void)
{
/* Process the next entry from the worklist. */
unsigned stmt_uid = bitmap_first_set_bit (ssa_edge_worklist);
which will then be a O(n) operation. Likewise the bitmap_empty_p test
isn't efficient (can be avoided by re-using the above walk).
For this particular testcase we only
end up here 1494 times (compared to many more bitmap_set_bit operations).
Still this makes using a sbitmap not the best idea. A sparse-set fits a bit
better but we want to iterate over the set in UID order as well which
the sparse-set doesn't allow - it only does choose_one in O(1) which might
not be the optimal propagation order (but eventually this detail isn't
too important...?). Iff only our sparse bitmap implementation would
be O(log N) in bit finding...
Note all of the same issues in theory apply to the CFG BB worklist.
