[patch] basic-block.h: Speed up FOR_EACH_EDGE.

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

Attached is a patch to speed up FOR_EACH_EDGE.

Ideally, FOR_EACH_EDGE should be optimized to something like this:

  unsigned int length = EDGE_COUNT (blah);
  edge e;
  for (i = 0; i < length; i++)
    {
      e = EDGE_I (blah, i);

      /* Do something with e.  */
    }
  e = NULL;

However, the reality even after tree optimizations is more like this:

  edge e;
  for (i = 0; 1; i++)
    {
      unsigned int length = EDGE_COUNT (blah);
      if (i == length)
	break;

      e = EDGE_I (blah, i);
      if (e == NULL)
	break;

      /* Do something with e.  */
    }
  e = NULL;

It turns out that we have two unnecessary "if" statements in this
"for" loop.  The obvious one is "if (e == NULL)", which is unnecessary
because every edge in the vector is supposed to be nonnull.  The other
one is hidden in EDGE_COUNT because VEC_length is written like so:

  return vec_ ? vec_->num : 0;

The patch essentially removes the two "if" statements mentioned above.
In order to cram a construct like

  for (i = 0; i < length; i++)
    {
      e = EDGE_I (blah, i);

      /* Do something eith e. */
    }
  e = NULL;

into a single "for" loop, I created a helper function called ei_cond.

Here is a timing in seconds for five runs of ./cc1 -quiet -O2
-fomit-frame-pointer -o /dev/null.

               original patched   diff%
c-common.i       13.695  13.664 -0.226%
combine.i        16.484  16.451 -0.200%
fold-const.i     16.945  16.905 -0.236%
reload1.i        11.780  11.752 -0.237%
reload.i         11.638  11.617 -0.180%
insn-attrtab.i  199.636 199.298 -0.169%

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

Kazu Hirata

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

	* basic-block.h (edge_iterator): Add new field length.
	(ei_start_1): Initialize length.
	(ei_cond): New.
	(FOR_EACH_EDGE): Call ei_cond instead of ei_safe_edge.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.238
diff -c -d -p -r1.238 basic-block.h
*** basic-block.h	15 Feb 2005 07:18:22 -0000	1.238
--- basic-block.h	28 Feb 2005 04:35:23 -0000
*************** struct edge_list
*** 552,557 ****
--- 552,558 ----
  typedef struct {
    unsigned index;
    VEC(edge) **container;
+   unsigned length;
  } edge_iterator;
  
  static inline VEC(edge) *
*************** ei_start_1 (VEC(edge) **ev)
*** 572,577 ****
--- 573,579 ----
  
    i.index = 0;
    i.container = ev;
+   i.length = EDGE_COUNT (*i.container);
  
    return i;
  }
*************** ei_safe_edge (edge_iterator i)
*** 636,641 ****
--- 638,662 ----
    return !ei_end_p (i) ? ei_edge (i) : NULL;
  }
  
+ /* Return 1 if we should continue to iterate.  Return 0 otherwise.
+    *Edge P is set to the next edge if we are to continue to iterate
+    and 0 otherwise.  */
+ 
+ static inline int
+ ei_cond (edge_iterator ei, edge *p)
+ {
+   if (ei.index < ei.length)
+     {
+       *p = ei_edge (ei);
+       return 1;
+     }
+   else
+     {
+       *p = NULL;
+       return 0;
+     }
+ }
+ 
  /* This macro serves as a convenient way to iterate each edge in a
     vector of predecessor or successor edges.  It must not be used when
     an element might be removed during the traversal, otherwise
*************** ei_safe_edge (edge_iterator i)
*** 651,659 ****
       }
  */
  
! #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
!   for ((EDGE) = NULL, (ITER) = ei_start ((EDGE_VEC)); \
!        ((EDGE) = ei_safe_edge ((ITER))); \
         ei_next (&(ITER)))
  
  struct edge_list * create_edge_list (void);
--- 672,680 ----
       }
  */
  
! #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC)	\
!   for ((ITER) = ei_start ((EDGE_VEC));		\
!        ei_cond ((ITER), &(EDGE));		\
         ei_next (&(ITER)))
  
  struct edge_list * create_edge_list (void);