[PATCH] Speed up IDF compute a tiny bit

[Richard Biener]

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);
        }
      }