While looking into speeding up incremental SSA update for PR56113 (it's IDF compute slowness) I played with optimizing IDF compute itself. One obvious thing that speeds it up by 5% is to use quick_push in the innermost loop. When experimenting with using a sparseset for the worklist to avoid iterating multiple times I noticed its workers have embedded gcc_assert()s which prevents them from being inlined. Thus, fixed as well.
Bootstrap and regtest running on x86_64-unknown-linux-gnu. As for the IDF slowness - I suppose a different PHI insertion strategy that is not quadratic would be nice. Richard. 2013-01-30 Richard Biener <rguent...@suse.de> * sparseset.h (sparseset_bit_p): Use gcc_checking_assert. (sparseset_pop): Likewise. * cfganal.c (compute_idf): Likewise. Increase work-stack size to be able to use quick_push in the worker loop. Index: gcc/sparseset.h =================================================================== *** gcc/sparseset.h (revision 195574) --- gcc/sparseset.h (working copy) *************** sparseset_bit_p (sparseset s, SPARSESET_ *** 140,146 **** { SPARSESET_ELT_TYPE idx; ! gcc_assert (e < s->size); idx = s->sparse[e]; --- 140,146 ---- { SPARSESET_ELT_TYPE idx; ! gcc_checking_assert (e < s->size); idx = s->sparse[e]; *************** sparseset_pop (sparseset s) *** 174,180 **** { SPARSESET_ELT_TYPE mem = s->members; ! gcc_assert (mem != 0); s->members = mem - 1; return s->dense[mem]; --- 174,180 ---- { SPARSESET_ELT_TYPE mem = s->members; ! gcc_checking_assert (mem != 0); s->members = mem - 1; return s->dense[mem]; Index: gcc/cfganal.c =================================================================== *** gcc/cfganal.c (revision 195574) --- gcc/cfganal.c (working copy) *************** compute_idf (bitmap def_blocks, bitmap_h *** 1141,1147 **** vec<int> work_stack; bitmap phi_insertion_points; ! work_stack.create (n_basic_blocks); phi_insertion_points = BITMAP_ALLOC (NULL); /* Seed the work list with all the blocks in DEF_BLOCKS. We use --- 1141,1148 ---- vec<int> work_stack; bitmap phi_insertion_points; ! /* Each block can appear at most twice on the work-stack. */ ! work_stack.create (2 * n_basic_blocks); phi_insertion_points = BITMAP_ALLOC (NULL); /* Seed the work list with all the blocks in DEF_BLOCKS. We use *************** compute_idf (bitmap def_blocks, bitmap_h *** 1165,1179 **** form, the basic blocks where new and/or old names are defined may have disappeared by CFG cleanup calls. In this case, we may pull a non-existing block from the work stack. */ ! gcc_assert (bb_index < (unsigned) last_basic_block); EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, 0, i, bi) { ! /* Use a safe push because if there is a definition of VAR ! in every basic block, then WORK_STACK may eventually have ! more than N_BASIC_BLOCK entries. */ ! work_stack.safe_push (i); bitmap_set_bit (phi_insertion_points, i); } } --- 1166,1177 ---- form, the basic blocks where new and/or old names are defined may have disappeared by CFG cleanup calls. In this case, we may pull a non-existing block from the work stack. */ ! gcc_checking_assert (bb_index < (unsigned) last_basic_block); EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, 0, i, bi) { ! work_stack.quick_push (i); bitmap_set_bit (phi_insertion_points, i); } }