Patch to handle perfect loop unrolling in tree_transform_and_unroll_loop

[Bingfeng Mei]

Hello,
This patch is to handle perfect loop unrolling as
discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.

I merged the original code into tree_transform_and_unroll_loop,
and added some code to get probability/frequency right.

This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
A tree-level unrolling pass will just call this modified function.
I will submit a separate patch if needed.

2009-10-28  Bingfeng Mei <bmei@...>

        * tree_transform_and_unroll_loop (tree_transform_and_unroll_loop):
        To handle perfect loop unrolling. (perfect_loop_unrolling_p): New function
        to check whether a loop can perfect unrolling.

Cheers,
Bingfeng Mei

[Jean Christophe Beyler]

I am only looking at your patch so I haven't tried your code, so it is
very possible some of these comments are simply stupid:

- I wonder the usefulness of :
+  if(perfect_unrolling)
+    {
+      new_exit = exit;
+      rest = exit->dest;
+      new_est_niter = est_niter / factor;
+    }

as far as I can tell, rest is only used in the non perfect case

- Not important at all:
+      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
doesn't follow the normal indentation for the '('

- More to the point, I did something similar except I added a test to
see if the factor requested by the user was above the limit of
n_iters. If so, I say that the unrolling is perfect and issue a
warning.

Do you want me to look a bit more?
Jc

On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei <bmei@...> wrote:

> Hello,
> This patch is to handle perfect loop unrolling as
> discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
>
> I merged the original code into tree_transform_and_unroll_loop,
> and added some code to get probability/frequency right.
>
> This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
> A tree-level unrolling pass will just call this modified function.
> I will submit a separate patch if needed.
>
> 2009-10-28  Bingfeng Mei <bmei@...>
>
>        * tree_transform_and_unroll_loop (tree_transform_and_unroll_loop):
>        To handle perfect loop unrolling. (perfect_loop_unrolling_p): New function
>        to check whether a loop can perfect unrolling.
>
> Cheers,
> Bingfeng Mei
>
>

[Bingfeng Mei]

 

> -----Original Message-----
> From: fearyourself@... [mailto:fearyourself@...]
> On Behalf Of Jean Christophe Beyler
> Sent: 28 October 2009 15:24
> To: Bingfeng Mei
> Cc: gcc-patches@...; Zdenek Dvorak
> Subject: Re: Patch to handle perfect loop unrolling in
> tree_transform_and_unroll_loop
>
> I am only looking at your patch so I haven't tried your code, so it is
> very possible some of these comments are simply stupid:
>
> - I wonder the usefulness of :
> +  if(perfect_unrolling)
> +    {
> +      new_exit = exit;
> +      rest = exit->dest;
> +      new_est_niter = est_niter / factor;
> +    }

You are right. These lines are leftover of previous atttempt to merge code.
Removed now in new patch.

>
> as far as I can tell, rest is only used in the non perfect case
>
> - Not important at all:
> +      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
> doesn't follow the normal indentation for the '('
>

Also found others and fixed.

> - More to the point, I did something similar except I added a test to
> see if the factor requested by the user was above the limit of
> n_iters. If so, I say that the unrolling is perfect and issue a
> warning.

Can the check be done in unrolling pass?
Does your test case only work with an extra unrolling pass? Or can be
tested with this patch only? Currently, tree_transform_and_unroll_loop
seems to be called by prefetch pass only.

>
> Do you want me to look a bit more?
> Jc
>
> On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei
> <bmei@...> wrote:
> > Hello,
> > This patch is to handle perfect loop unrolling as
> > discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
> >
> > I merged the original code into tree_transform_and_unroll_loop,
> > and added some code to get probability/frequency right.
> >
> > This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
> > A tree-level unrolling pass will just call this modified function.
> > I will submit a separate patch if needed.
> >
> > 2009-10-28  Bingfeng Mei <bmei@...>
> >
> >        * tree_transform_and_unroll_loop
> (tree_transform_and_unroll_loop):
> >        To handle perfect loop unrolling.
> (perfect_loop_unrolling_p): New function
> >        to check whether a loop can perfect unrolling.
> >
> > Cheers,
> > Bingfeng Mei
> >
> >
>
>

[Bingfeng Mei]

BTW: the following lines in original tree_transform_and_unroll_loop (I didn't change) are
problematic. Some complex loops won't meet requirements of single_pred(loop->latch) (e.g., 20060905-1.c)
should this function is called to unroll them.
 
      exit_bb = single_pred (loop->latch);
      new_exit = find_edge (exit_bb, rest);
      new_exit->count = loop_preheader_edge (loop)->count;
      new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1);

      rest->count += new_exit->count;
      rest->frequency += EDGE_FREQUENCY (new_exit);

      new_nonexit = single_pred_edge (loop->latch);
      prob = new_nonexit->probability;
      new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
      new_nonexit->count = exit_bb->count - new_exit->count;

> -----Original Message-----
> From: fearyourself@... [mailto:fearyourself@...]
> On Behalf Of Jean Christophe Beyler
> Sent: 28 October 2009 15:24
> To: Bingfeng Mei
> Cc: gcc-patches@...; Zdenek Dvorak
> Subject: Re: Patch to handle perfect loop unrolling in
> tree_transform_and_unroll_loop
>
> I am only looking at your patch so I haven't tried your code, so it is
> very possible some of these comments are simply stupid:
>
> - I wonder the usefulness of :
> +  if(perfect_unrolling)
> +    {
> +      new_exit = exit;
> +      rest = exit->dest;
> +      new_est_niter = est_niter / factor;
> +    }
>
> as far as I can tell, rest is only used in the non perfect case
>
> - Not important at all:
> +      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
> doesn't follow the normal indentation for the '('
>
> - More to the point, I did something similar except I added a test to
> see if the factor requested by the user was above the limit of
> n_iters. If so, I say that the unrolling is perfect and issue a
> warning.
>
> Do you want me to look a bit more?
> Jc
>
> On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei
> <bmei@...> wrote:
> > Hello,
> > This patch is to handle perfect loop unrolling as
> > discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
> >
> > I merged the original code into tree_transform_and_unroll_loop,
> > and added some code to get probability/frequency right.
> >
> > This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
> > A tree-level unrolling pass will just call this modified function.
> > I will submit a separate patch if needed.
> >
> > 2009-10-28  Bingfeng Mei <bmei@...>
> >
> >        * tree_transform_and_unroll_loop
> (tree_transform_and_unroll_loop):
> >        To handle perfect loop unrolling.
> (perfect_loop_unrolling_p): New function
> >        to check whether a loop can perfect unrolling.
> >
> > Cheers,
> > Bingfeng Mei
> >
> >
>
>

[Jean Christophe Beyler]

> You are right. These lines are leftover of previous atttempt to merge code.
> Removed now in new patch.

Actually (again just looking at your patch code, have not tested), but now:

- Since you removed that code, new_exit does not get set at the
perfect_unrolling case. The call to tree_duplicate_loop_to_header_edge
now has new_exit passed as NULL instead of being set to either exit or
single_dom_exit like you did before.

>> - More to the point, I did something similar except I added a test to
>> see if the factor requested by the user was above the limit of
>> n_iters. If so, I say that the unrolling is perfect and issue a
>> warning.
>
> Can the check be done in unrolling pass?
> Does your test case only work with an extra unrolling pass? Or can be
> tested with this patch only? Currently, tree_transform_and_unroll_loop
> seems to be called by prefetch pass only.
>

You've got a point, I was thinking of my code where the user can
request an unrolling of a higher degree

#pragma unroll 100
for (i=0; i<20; i++)
{
...
}

Your patch won't unroll it at all.

However, in the case where this patch is only to fix the current code,
I don't think the unrolling passes would ever ask to unroll more than
the known iterations, so this is not a problem.

> BTW: the following lines in original tree_transform_and_unroll_loop (I didn't change) are problematic. Some complex loops won't
> meet requirements of single_pred(loop->latch) (e.g., 20060905-1.c) should this function is called to unroll them.

I don't understand this. Can you explain a bit more ?

I looked at this, my modified version 4.3.2 does not have any issues
with this test. Without my pragma, it does not try to unroll, with it,
it does not fail.

Jc

[Bingfeng Mei]

Oops! The previous revised patch failed. I should really run tests on
every seemingly minor change :-).

 +  if(perfect_unrolling)
 +    {
 +      new_exit = exit;       <-- the later gimple_duplicate_loop_to_header_edge uses new_exit
 +      new_est_niter = est_niter / factor; <-- just to be consistent with non-perfect loop case and remove need to initialize this var.
 +    }

Cheers,
Bingfeng

> -----Original Message-----
> From: fearyourself@... [mailto:fearyourself@...]
> On Behalf Of Jean Christophe Beyler
> Sent: 28 October 2009 15:24
> To: Bingfeng Mei
> Cc: gcc-patches@...; Zdenek Dvorak
> Subject: Re: Patch to handle perfect loop unrolling in
> tree_transform_and_unroll_loop
>
> I am only looking at your patch so I haven't tried your code, so it is
> very possible some of these comments are simply stupid:
>
> - I wonder the usefulness of :
> +  if(perfect_unrolling)
> +    {
> +      new_exit = exit;
> +      rest = exit->dest;
> +      new_est_niter = est_niter / factor;
> +    }
>
> as far as I can tell, rest is only used in the non perfect case
>
> - Not important at all:
> +      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
> doesn't follow the normal indentation for the '('
>
> - More to the point, I did something similar except I added a test to
> see if the factor requested by the user was above the limit of
> n_iters. If so, I say that the unrolling is perfect and issue a
> warning.
>
> Do you want me to look a bit more?
> Jc
>
> On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei
> <bmei@...> wrote:
> > Hello,
> > This patch is to handle perfect loop unrolling as
> > discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
> >
> > I merged the original code into tree_transform_and_unroll_loop,
> > and added some code to get probability/frequency right.
> >
> > This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
> > A tree-level unrolling pass will just call this modified function.
> > I will submit a separate patch if needed.
> >
> > 2009-10-28  Bingfeng Mei <bmei@...>
> >
> >        * tree_transform_and_unroll_loop
> (tree_transform_and_unroll_loop):
> >        To handle perfect loop unrolling.
> (perfect_loop_unrolling_p): New function
> >        to check whether a loop can perfect unrolling.
> >
> > Cheers,
> > Bingfeng Mei
> >
> >
>
>

[Jean Christophe Beyler]

I don't see any problems with what you have done. It's what I've done
in mine as well except for the probability code. I would have
factorized more the code to really keep the common code unique.

I've updated your patch but have not tested it, it should be fine but
will give you an idea what I mean.

I also wonder about that assert, in what case could there not be 2 successors ?

Jc

On Wed, Oct 28, 2009 at 1:43 PM, Bingfeng Mei <bmei@...> wrote:

> Oops! The previous revised patch failed. I should really run tests on
> every seemingly minor change :-).
>
>  +  if(perfect_unrolling)
>  +    {
>  +      new_exit = exit;       <-- the later gimple_duplicate_loop_to_header_edge uses new_exit
>  +      new_est_niter = est_niter / factor; <-- just to be consistent with non-perfect loop case and remove need to initialize this var.
>  +    }
>
> Cheers,
> Bingfeng
>
>> -----Original Message-----
>> From: fearyourself@... [mailto:fearyourself@...]
>> On Behalf Of Jean Christophe Beyler
>> Sent: 28 October 2009 15:24
>> To: Bingfeng Mei
>> Cc: gcc-patches@...; Zdenek Dvorak
>> Subject: Re: Patch to handle perfect loop unrolling in
>> tree_transform_and_unroll_loop
>>
>> I am only looking at your patch so I haven't tried your code, so it is
>> very possible some of these comments are simply stupid:
>>
>> - I wonder the usefulness of :
>> +  if(perfect_unrolling)
>> +    {
>> +      new_exit = exit;
>> +      rest = exit->dest;
>> +      new_est_niter = est_niter / factor;
>> +    }
>>
>> as far as I can tell, rest is only used in the non perfect case
>>
>> - Not important at all:
>> +      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
>> doesn't follow the normal indentation for the '('
>>
>> - More to the point, I did something similar except I added a test to
>> see if the factor requested by the user was above the limit of
>> n_iters. If so, I say that the unrolling is perfect and issue a
>> warning.
>>
>> Do you want me to look a bit more?
>> Jc
>>
>> On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei
>> <bmei@...> wrote:
>> > Hello,
>> > This patch is to handle perfect loop unrolling as
>> > discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
>> >
>> > I merged the original code into tree_transform_and_unroll_loop,
>> > and added some code to get probability/frequency right.
>> >
>> > This is related to http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
>> > A tree-level unrolling pass will just call this modified function.
>> > I will submit a separate patch if needed.
>> >
>> > 2009-10-28  Bingfeng Mei <bmei@...>
>> >
>> >        * tree_transform_and_unroll_loop
>> (tree_transform_and_unroll_loop):
>> >        To handle perfect loop unrolling.
>> (perfect_loop_unrolling_p): New function
>> >        to check whether a loop can perfect unrolling.
>> >
>> > Cheers,
>> > Bingfeng Mei
>> >
>> >
>>
>>

[Bingfeng Mei]

 

> I also wonder about that assert, in what case could there not
> be 2 successors ?

Just try to be safe. I don't know whether a bb can has more than
2 successors in general. If the spec of tree says otherwise, this
line is redundant indeed.

> > BTW: the following lines in original
> tree_transform_and_unroll_loop (I didn't change) are
> problematic. Some complex loops won't
> > meet requirements of single_pred(loop->latch) (e.g.,
> 20060905-1.c) should this function is called to unroll them.
>
> I don't understand this. Can you explain a bit more ?
>
> I looked at this, my modified version 4.3.2 does not have any issues
> with this test. Without my pragma, it does not try to unroll, with it,
> it does not fail.

When my unrolling pass calles this function, I experienced the assertion
of single_pred for 20060905-1.c and others. That's why I can't share
the original code of obtaining new_exit and exit_bb.  I suspected problem
may show up for non-perfect loop though I cannot produce the error for now.

Still haven't heard from others who can approve the patch. I am wondering
whether Zdenek miss the mail :-).

Bingfeng

>
> Jc
>
> On Wed, Oct 28, 2009 at 1:43 PM, Bingfeng Mei
> <bmei@...> wrote:
> > Oops! The previous revised patch failed. I should really
> run tests on
> > every seemingly minor change :-).
> >
> >  +  if(perfect_unrolling)
> >  +    {
> >  +      new_exit = exit;       <-- the later
> gimple_duplicate_loop_to_header_edge uses new_exit
> >  +      new_est_niter = est_niter / factor; <-- just to be
> consistent with non-perfect loop case and remove need to
> initialize this var.
> >  +    }
> >
> > Cheers,
> > Bingfeng
> >
> >> -----Original Message-----
> >> From: fearyourself@... [mailto:fearyourself@...]
> >> On Behalf Of Jean Christophe Beyler
> >> Sent: 28 October 2009 15:24
> >> To: Bingfeng Mei
> >> Cc: gcc-patches@...; Zdenek Dvorak
> >> Subject: Re: Patch to handle perfect loop unrolling in
> >> tree_transform_and_unroll_loop
> >>
> >> I am only looking at your patch so I haven't tried your
> code, so it is
> >> very possible some of these comments are simply stupid:
> >>
> >> - I wonder the usefulness of :
> >> +  if(perfect_unrolling)
> >> +    {
> >> +      new_exit = exit;
> >> +      rest = exit->dest;
> >> +      new_est_niter = est_niter / factor;
> >> +    }
> >>
> >> as far as I can tell, rest is only used in the non perfect case
> >>
> >> - Not important at all:
> >> +      gcc_assert(EDGE_COUNT(exit_bb->succs) == 2);
> >> doesn't follow the normal indentation for the '('
> >>
> >> - More to the point, I did something similar except I
> added a test to
> >> see if the factor requested by the user was above the limit of
> >> n_iters. If so, I say that the unrolling is perfect and issue a
> >> warning.
> >>
> >> Do you want me to look a bit more?
> >> Jc
> >>
> >> On Wed, Oct 28, 2009 at 10:43 AM, Bingfeng Mei
> >> <bmei@...> wrote:
> >> > Hello,
> >> > This patch is to handle perfect loop unrolling as
> >> > discussed in http://gcc.gnu.org/ml/gcc/2009-10/msg00333.html.
> >> >
> >> > I merged the original code into tree_transform_and_unroll_loop,
> >> > and added some code to get probability/frequency right.
> >> >
> >> > This is related to
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712
> >> > A tree-level unrolling pass will just call this modified
> function.
> >> > I will submit a separate patch if needed.
> >> >
> >> > 2009-10-28  Bingfeng Mei <bmei@...>
> >> >
> >> >        * tree_transform_and_unroll_loop
> >> (tree_transform_and_unroll_loop):
> >> >        To handle perfect loop unrolling.
> >> (perfect_loop_unrolling_p): New function
> >> >        to check whether a loop can perfect unrolling.
> >> >
> >> > Cheers,
> >> > Bingfeng Mei
> >> >
> >> >
> >>
> >>
>

[Zdenek Dvorak-2]

Hi,

> +/* Check whether the number of iterations can be divided by unrolling
> +   factor to perform perfect unrolling */

the arguments of the function should be documented.

> +static bool
> +perfect_loop_unrolling_p(struct loop *loop, int factor, unsigned *num_iters)

Space is missing before (

> +{
> +   tree niters = number_of_exit_cond_executions(loop);

You should use the number of iterations information provided to tree_transform_and_unroll_loop
via struct tree_niter_desc *desc argument.

> +   if(niters != NULL_TREE

ditto (and everywhere else in the patch, I stop pointing this out here).

> +     && niters!= chrec_dont_know
> +     && TREE_CODE(niters) == INTEGER_CST)

host_integerp

> +     {
> +       *num_iters = tree_low_cst(niters, 1);

type of num_iters should be unsigned HOST_WIDE_INT.
I don't think it is a good idea to return number of iterations this way, as this
looks rather unrelated to the purpose of this function.

> +  bool perfect_unrolling = perfect_loop_unrolling_p(loop, factor, &est_niter);
>  
> -  est_niter = expected_loop_iterations (loop);

It seems more natural to use est_niter = expected_loop_iterations (which may differ from the value
in desc->niter in case that the loop has several exits).

> +  if (perfect_unrolling)
> +    {
> +      new_exit = single_dom_exit (loop);

This will fail if the loop has more than one exit.  Also, I somewhat miss the point of dealing with
updating of frequencies and probabilities separately in the case of perfect unrolling (the code
for the general case should work, possibly with minor tweaks).

Zdenek

[Bingfeng Mei]

Zdenek,
Thanks for comments.

> This will fail if the loop has more than one exit.  Also, I
> somewhat miss the point of dealing with
> updating of frequencies and probabilities separately in the
> case of perfect unrolling (the code
> for the general case should work, possibly with minor tweaks).
Initially, I tried to use the original code. But it doesn't seem
to produce correct frequency/probability for me. Additionally,
it causes ICE for some complex loops (e.g. 20060905-1.c).

      exit_bb = single_pred (loop->latch);
      new_exit = find_edge (exit_bb, rest);

The latch may have more than one predecessors. I couldn't use
above statements to find exit_bb/exit edge.

tree_transform_and_unroll_loop/tree_unroll_loop are used only
after determinate_unroll_factor, which checks whether
the loop has single exit through can_unroll_loop_p.

Cheers,
Bingfeng

> -----Original Message-----
> From: Zdenek Dvorak [mailto:rakdver@...]
> Sent: 06 November 2009 11:08
> To: Bingfeng Mei
> Cc: Jean Christophe Beyler; gcc-patches@...
> Subject: Re: [Revised Patch] to handle perfect loop unrolling
> in tree_transform_and_unroll_loop
>
> Hi,
>
> > +/* Check whether the number of iterations can be divided
> by unrolling
> > +   factor to perform perfect unrolling */
>
> the arguments of the function should be documented.
>
> > +static bool
> > +perfect_loop_unrolling_p(struct loop *loop, int factor,
> unsigned *num_iters)
>
> Space is missing before (
>
> > +{
> > +   tree niters = number_of_exit_cond_executions(loop);
>
> You should use the number of iterations information provided
> to tree_transform_and_unroll_loop
> via struct tree_niter_desc *desc argument.
>
> > +   if(niters != NULL_TREE
>
> ditto (and everywhere else in the patch, I stop pointing this
> out here).
>
> > +     && niters!= chrec_dont_know
> > +     && TREE_CODE(niters) == INTEGER_CST)
>
> host_integerp
>
> > +     {
> > +       *num_iters = tree_low_cst(niters, 1);
>
> type of num_iters should be unsigned HOST_WIDE_INT.
> I don't think it is a good idea to return number of
> iterations this way, as this
> looks rather unrelated to the purpose of this function.
>
> > +  bool perfect_unrolling = perfect_loop_unrolling_p(loop,
> factor, &est_niter);
> >  
> > -  est_niter = expected_loop_iterations (loop);
>
> It seems more natural to use est_niter =
> expected_loop_iterations (which may differ from the value
> in desc->niter in case that the loop has several exits).
>
> > +  if (perfect_unrolling)
> > +    {
> > +      new_exit = single_dom_exit (loop);
>
> This will fail if the loop has more than one exit.  Also, I
> somewhat miss the point of dealing with
> updating of frequencies and probabilities separately in the
> case of perfect unrolling (the code
> for the general case should work, possibly with minor tweaks).
>
> Zdenek
>
>

[Zdenek Dvorak-2]

Hi,

> > This will fail if the loop has more than one exit.  Also, I
> > somewhat miss the point of dealing with
> > updating of frequencies and probabilities separately in the
> > case of perfect unrolling (the code
> > for the general case should work, possibly with minor tweaks).
> Initially, I tried to use the original code. But it doesn't seem
> to produce correct frequency/probability for me. Additionally,
> it causes ICE for some complex loops (e.g. 20060905-1.c).
>
>       exit_bb = single_pred (loop->latch);
>       new_exit = find_edge (exit_bb, rest);
>
> The latch may have more than one predecessors. I couldn't use
> above statements to find exit_bb/exit edge.

original code moves the exit to the end of the loop (this somewhat improves
efficiency, since it avoids having an extra jump instruction for the loop
back-edge), thus ensuring that latch is empty and has only one predecessor.
Your patch skips this part of the code.  An easy way how to handle this would
be to only consider the loop perfect if it already satisfies this condition,
i.e., the latch block is empty and exit->src is its only predecessor
(this should be the common case, anyway).

> tree_transform_and_unroll_loop/tree_unroll_loop are used only
> after determinate_unroll_factor, which checks whether
> the loop has single exit through can_unroll_loop_p.

You should not rely on that -- this is something someone might reasonably want
to change (I think there is no principial reason for requiring single exit in
can_unroll_loop_p).  Also, exit of the loop is provided as a parameter to the
function, so getting this information from other sources is inconsistent.

Zdenek