Re: [patch] PR54146 - rewrite rewrite_into_loop_closed_ssa

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Thu, Aug 16, 2012 at 2:56 PM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Wed, 15 Aug 2012, Steven Bosscher wrote:
>
> Please convince me that this :
>
> +/* Return the outermost superloop LOOP of USE_LOOP that is a superloop of
> +   both DEF_LOOP and USE_LOOP.  */
> +static inline struct loop *
> +find_sibling_superloop (struct loop *use_loop, struct loop *def_loop)
> +{
> +  unsigned ud = loop_depth (use_loop);
> +  unsigned dd = loop_depth (def_loop);
> +  gcc_assert (ud > 0 && dd > 0);
> +  if (ud > dd)
> +    use_loop = superloop_at_depth (use_loop, dd);
> +  if (ud < dd)
> +    def_loop = superloop_at_depth (def_loop, ud);
> +  while (loop_outer (use_loop) != loop_outer (def_loop))
> +    {
> +      use_loop = loop_outer (use_loop);
> +      def_loop = loop_outer (def_loop);
> +      gcc_assert (use_loop && def_loop);
> +    }
> +  return use_loop;
>
> doesn't have the usual problem of advancing two iterators at the same time
> and expecting they'll eventually meet (which they generally don't have
> to).

I'd think the code is clear enough, if you look at how the function is
used. But I'll talk you through it because you ask so kindly.

1. Note the context of where the function is called:

      if (! flow_loop_nested_p (use_loop, def_loop))
        use_bb = find_sibling_superloop (use_loop, def_loop)->header;

so find_sibling_superloop is only called iff def_loop is not nested in use loop.


2. In find_sibling_superloop the first step is to align the loop depth:

> +  unsigned ud = loop_depth (use_loop);
> +  unsigned dd = loop_depth (def_loop);
> +  gcc_assert (ud > 0 && dd > 0);
> +  if (ud > dd)
> +    use_loop = superloop_at_depth (use_loop, dd);
> +  if (ud < dd)
> +    def_loop = superloop_at_depth (def_loop, ud);

So if USE_LOOP is at a deeper nesting level than DEF_LOOP, we find its
outer loop at the depth of DEF_LOOP and vice versa.


3. Now that USE_LOOP and DEF_LOOP are at the same nesting depth, we iterate:

> +  while (loop_outer (use_loop) != loop_outer (def_loop))
> +    {
> +      use_loop = loop_outer (use_loop);
> +      def_loop = loop_outer (def_loop);
> +      gcc_assert (use_loop && def_loop);
> +    }

This must meet at some point, because the outermost "loop" of all
loops is current_loops->tree_root at depth 0, and we count down from
the same loop depth.

Kind regards,
Steven