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

[Jeffrey A Law <law at redhat dot com>]

On Tue, 2005-03-01 at 21:03 -0500, Kazu Hirata wrote:
> 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.
If I read this patch correctly, FOR_EACH_EDGE will not work correctly
anymore if edges are added within the FOR_EACH_EDGE body.  Right?

We should probably explicitly document that FOR_EACH_EDGE can not
be used if edges are going to be created within the body.

And more generally, the "length" field is not kept accurate.    It's
really only valid from the time the iterator is created until the point
when edges are added/removed from the edge vector.  That needs to be
documented as well.

Another possibility would be to not store the length in the vector, but
instead into a local variable.  That would certainly help avoid the
potential of getting the length field out of sync with the actual
length of the vector.

Thoughts?
Jeff