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

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

Hi,

Attached is a revised version of my patch to speed up FOR_EACH_EDGE.

I addressed Jeff's comments.

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

Kazu Hirata

2005-03-03  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	2 Mar 2005 19:55:55 -0000
*************** struct edge_list
*** 552,557 ****
--- 552,561 ----
  typedef struct {
    unsigned index;
    VEC(edge) **container;
+ 
+   /* This field is initialized when the iterator is created and not
+      updated after that.  */
+   unsigned length;
  } edge_iterator;
  
  static inline VEC(edge) *
*************** ei_start_1 (VEC(edge) **ev)
*** 572,577 ****
--- 576,582 ----
  
    i.index = 0;
    i.container = ev;
+   i.length = EDGE_COUNT (*i.container);
  
    return i;
  }
*************** ei_safe_edge (edge_iterator i)
*** 636,644 ****
    return !ei_end_p (i) ? ei_edge (i) : NULL;
  }
  
  /* 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
     elements will be missed.  Instead, use a for-loop like that shown
     in the following pseudo-code:
     
--- 641,668 ----
    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 added or removed during the traversal, otherwise
     elements will be missed.  Instead, use a for-loop like that shown
     in the following pseudo-code:
     
*************** 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);
--- 675,683 ----
       }
  */
  
! #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);