Re: [PATCH 3/3] Loop flattening on loop-SSA.

[Sebastian Pop <sebpop at gmail dot com>]

Hi Richi,

Thanks for reviewing this.

On Fri, Nov 5, 2010 at 07:51, Richard Guenther <rguenther@suse.de> wrote:
> What extra testing apart from the 4 testcases did this new pass get?
> Do we pass bootstrap with it enabled? ?Did you check if we regress
> in SPEC 2k6 when it is enabled?

I tested loop flattening alone (before I reworked the if-conversion of
stores).  It passed bootstrap with it enabled and passed with no
run/compile errors the SPEC2k6.

> I think the pass misses a cost model and I'm still not sure when
> or if it will be profitable to do this at all (as said, no
> functional testcases). ?What's the immediate benefit for GCC 4.6?

I have not yet measured the perf gain/loss due to this pass on
SPEC2k6.  I will report the SPEC2k6 percentages with/without loop
flattening.

> The testcases seem to origin from ICEs found during development. ?There
> is a lack of functional tests, please consider coming up with some,
> eventually testing for enabled extra optimizations.

Ok.  I could add a matmult test with its runtime test, and grep in the
code generated by the loop flattening pass for only one loop.  I could
also add all the graphite/run-id-* testcases.

>> +/* In tree-if-conv.c */
>> +bool gate_tree_if_conversion (void);
>> +bool tree_if_conversion (struct loop *, tree *);
>> +
>
> Why'd you need to export the gate? ?I guess if-conversion should
> happen unconditionally for loops that are flattened as I see it is
> really part of the flattening transformation?

Right.  I will just call tree_if_conversion unconditionally at the end
of loop flattening.

>> +/* Keep the loop structure for LOOP and remove all the loop structures
>> + ? under LOOP. ?*/
>> +
>> +static void
>> +cancel_subloops (loop_p loop)
>> +{
>> + ?int i;
>> + ?loop_p li;
>> + ?VEC (loop_p, heap) *lv = VEC_alloc (loop_p, heap, 3);
>> +
>> + ?for (li = loop->inner; li; li = li->next)
>> + ? ?VEC_safe_push (loop_p, heap, lv, li);
>> +
>> + ?FOR_EACH_VEC_ELT (loop_p, lv, i, li)
>> + ? ?cancel_loop_tree (li);
>> +
>> + ?VEC_free (loop_p, heap, lv);
>> +}
>
> This function should be in cfgloop.c and implemented in simpler
> form, like
>
> void
> cancel_subloops (struct loop *loop)
> {
> ?while (loop->inner)
> ? ?cancel_loop_tree (loop->inner);
> }
>

Ok I will move this function to cfgloop.c.  However, if I don't think
we can simplify it further without extra storage: if I write the
simplified form like this:

void
cancel_subloops (struct loop *loop)
{
  loop_p x = loop->inner;

  while (x)
    {
      cancel_loop_tree (x);
      x = x->next;
    }
}

this won't work, as the loop x gets first canceled and then we try to
access x->next and this will produce a segfault.

>> + ? ? ?phi = create_phi_node (var, loop->latch);
>> + ? ? ?create_new_def_for (gimple_phi_result (phi), phi,
>> + ? ? ? ? ? ? ? ? ? ? ? gimple_phi_result_ptr (phi));
>
> Using create_new_def_for looks very suspicios. ?create_phi_node
> will already create a new SSA name for you for the result, so
> it doesn't make any sense to fiddle with the SSA updaters machinery, does
> it?
>

When I wrote this, I was following some other code in if-conversion.
I will remove this pattern from this file and from if-conversion.

>> +/* Flattens all the loops of the current function. ?*/
>> +
>> +static unsigned int
>> +tree_loop_flattening (void)
>> +{
>> + ?unsigned todo = 0;
>> + ?loop_p loop;
>> + ?loop_iterator li;
>> + ?tree scratch_pad = NULL_TREE;
>> +
>> + ?if (number_of_loops () <= 1)
>> + ? ?return 0;
>> +
>> + ?FOR_EACH_LOOP (li, loop, 0)
>> + ? ?todo |= flatten_loop (loop, &scratch_pad);
>
> So we might end up recursively flattening loops (or not, as this
> walk is in undefined order).

The order in which we flatten loops does not really matter.

> ?I'd say you want LI_ONLY_INNERMOST here,
> or do you really want to flatten all loop trees up to the number
> of basic blocks specified in the parm? ?I guess not.

For a given number of basic blocks per flat loop, any loop tree
traversal will end up with the same loop tree.  If we start walking
the loop tree from the innermost, we may end up flattening flat loops.

Sebastian