Re: [patch] PR middle-end/39326 - limit LIM

[Steven Bosscher <stevenb.gcc@gmail.com>]

On Mon, Mar 11, 2013 at 10:52 AM, Richard Biener wrote:
> Given
>
> +   well.  Return true if all is well, false if something happened
> +   that is fatal to the rest of the LIM pass.  */
>
> -static void
> +static bool
>  gather_mem_refs_stmt (struct loop *loop, gimple stmt)
>
> and
>
>    FOR_EACH_BB (bb)
>      {
> ...
> +      for (bsi = gsi_start_bb (bb);
> +          !gsi_end_p (bsi) && all_ok;
> +          gsi_next (&bsi))
> +       all_ok = gather_mem_refs_stmt (loop, gsi_stmt (bsi));
> +
> +      if (! all_ok)
> +        bitmap_set_bit (loops_with_too_many_memrefs, loop->num);
> +    }
> +
> +  /* Propagate the information about loops with too many memory
> +     references up the loop hierarchy.  */
> +  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
> +    {
> +      struct loop *outer = loop_outer (loop);
> +      if (outer == current_loops->tree_root
> +         || ! bitmap_bit_p (loops_with_too_many_memrefs, loop->num))
> +       continue;
> +      bitmap_set_bit (loops_with_too_many_memrefs, outer->num);
>      }
>
> I don't see how this propagation works correctly as you start to mark
> BBs as not-ok starting from a "random" basic-block in the loop tree.

Not at all. The function looks like this:

static void
gather_mem_refs_in_loops (bitmap loops_with_too_many_memrefs)
{
  FOR_EACH_BB (bb)
    {
       for each gimple statement
         all_ok = gather_mem_refs_stmt (loop, gsi_stmt (bsi));
    if (! all_ok)
        bitmap_set_bit (loops_with_too_many_memrefs, loop->num);
    }

  /* Propagate the information about loops with too many memory
     references up the loop hierarchy.  */
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
    {
      struct loop *outer = loop_outer (loop);
      if (outer == current_loops->tree_root
          || ! bitmap_bit_p (loops_with_too_many_memrefs, loop->num))
        continue;
      bitmap_set_bit (loops_with_too_many_memrefs, outer->num);
    }

  /* Propagate the information about accessed memory references up
     the loop hierarchy.  */
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
    /* Propagate stuff */
}

So all basic blocks are visited first.
Note it is also like this without my patch.


> You of course also end up disqualifying very small loops completely
> if they happen to be analyzed after a very big one you disqualify.
> Of course that's partly because memory_accesses contains all
> memory accesses in the function - so I think rather than limiting
> on length of memory_accesses you want to limit on the length of
> memory_accesses.refs_in_loop (well, on memory_accesses.all_refs_in_loop).

Right, I guess the limit should be per-loop, and it's "global" now.


> And you want the initial walk over all BBs to instead walk on BBs
> FOR_EACH_LOOP and LI_FROM_INNERMOST (you can then do the
> propagation to fill all_refs_in_loop there, too).

That is already what happens.


> At this point this should be stage1 material, eventually backported for 4.8.1.

Obviously.

> And yes, aside from the above the rest of the patch looks good to me
> (move loops_with_too_many_memrefs into the memory_accesses struct?)

That's a good idea.

I'll come back with an updated patch for trunk GCC 4.9.

Ciao!
Steven