This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] cfg.c: Speed up make_edge and cached_make_edge.


Hi,

Attached is a patch to speed up make_edge and cached_make_edge.

Having come up with no good alternative to the edge cache, I went for
microoptimization.

cached_make_edge has a lot of "if" statements, especially in its tree
dump.  For example, consider:

  if (use_edge_cache)
    SET_BIT (edge_cache[src->index], dst->index);

If we are given an edge cache and don't find a requested edge in the
cache, we know we have to set a bit in the bitmap and create the edge.
Just do so right after the bit test like so:

  if (! TEST_BIT (edge_cache[src->index], dst->index))
    {
      SET_BIT (edge_cache[src->index], dst->index);
      return unchecked_make_edge (src, dst, flags);
    }

This gives rise to some CSE opportunities between TEST_BIT and
SET_BIT.  Also, we end with a tail call.  Nice.

make_edge does not have to rely on cached_make_edge.  Instead, I made
cached_make_edge fall back to make_edge when edge cache isn't
available.

Here is a timing in seconds for five runs of ./cc1 -quiet -O2 -o
/dev/null.  The improvements are small but measurable.

             original patched   diff%
c-common.i     18.105  18.092 -0.071%
combine.i      16.579  16.552 -0.162%
fold-const.i   37.484  37.372 -0.298%
reload1.i      13.103  13.100 -0.022%
reload.i       12.019  11.996 -0.191%

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-02-22  Kazu Hirata  <kazu@cs.umass.edu>

	* cfg.c (cached_make_edge): Call make_edge if edge cache is
	not available.  Use tail calls wherever possible.
	(make_edge): Call unchecked_make_edge to create an edge.

Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.81
diff -u -d -p -r1.81 cfg.c
*** cfg.c	15 Jan 2005 16:06:14 -0000	1.81
--- cfg.c	21 Feb 2005 02:18:49 -0000
***************
*** 273,315 ****
  edge
  cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
  {
!   int use_edge_cache;
!   edge e;
! 
!   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
!      many edges to them, or we didn't allocate memory for it.  */
!   use_edge_cache = (edge_cache
! 		    && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
  
!   /* Make sure we don't add duplicate edges.  */
!   switch (use_edge_cache)
      {
!     default:
!       /* Quick test for non-existence of the edge.  */
!       if (! TEST_BIT (edge_cache[src->index], dst->index))
! 	break;
! 
!       /* The edge exists; early exit if no work to do.  */
!       if (flags == 0)
! 	return NULL;
! 
!       /* Fall through.  */
!     case 0:
!       e = find_edge (src, dst);
!       if (e)
! 	{
! 	  e->flags |= flags;
! 	  return NULL;
! 	}
!       break;
      }
  
!   e = unchecked_make_edge (src, dst, flags);
! 
!   if (use_edge_cache)
!     SET_BIT (edge_cache[src->index], dst->index);
  
!   return e;
  }
  
  /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
--- 273,301 ----
  edge
  cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
  {
!   if (edge_cache == NULL
!       || src == ENTRY_BLOCK_PTR
!       || dst == EXIT_BLOCK_PTR)
!     return make_edge (src, dst, flags);
  
!   /* Does the requested edge already exist?  */
!   if (! TEST_BIT (edge_cache[src->index], dst->index))
      {
!       /* The edge does not exist.  Create one and update the
! 	 cache.  */
!       SET_BIT (edge_cache[src->index], dst->index);
!       return unchecked_make_edge (src, dst, flags);
      }
  
!   /* At this point, we know that the requested edge exists.  Adjust
!      flags if necessary.  */
!   if (flags)
!     {
!       edge e = find_edge (src, dst);
!       e->flags |= flags;
!     }
  
!   return NULL;
  }
  
  /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
***************
*** 318,324 ****
  edge
  make_edge (basic_block src, basic_block dest, int flags)
  {
!   return cached_make_edge (NULL, src, dest, flags);
  }
  
  /* Create an edge connecting SRC to DEST and set probability by knowing
--- 304,319 ----
  edge
  make_edge (basic_block src, basic_block dest, int flags)
  {
!   edge e = find_edge (src, dest);
! 
!   /* Make sure we don't add duplicate edges.  */
!   if (e)
!     {
!       e->flags |= flags;
!       return NULL;
!     }
! 
!   return unchecked_make_edge (src, dest, flags);
  }
  
  /* Create an edge connecting SRC to DEST and set probability by knowing


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]