Turning off unrolling to certain loops

Turning off unrolling to certain loops

[Jean Christophe Beyler]

Dear all,

I was wondering if it was possible to turn off the unrolling to
certain loops. Basically, I'd like the compiler not to consider
certain loops for unrolling but fail to see how exactly I can achieve
that.

I've traced the unrolling code to multiple places in the code (I'm
working with the 4.3.2 version) and, for the moment, I'm trying to
figure out if I can add something in the loop such as a note that I
can later find in the FOR_EACH_LOOP loops in order to turn the
unrolling for that particular loop off.

Have you got any ideas of what I could use like "note" or even a
better idea all together?

Thanks,
Jc

Re: Turning off unrolling to certain loops

[Zdenek Dvorak]

Hi,

> I was wondering if it was possible to turn off the unrolling to
> certain loops. Basically, I'd like the compiler not to consider
> certain loops for unrolling but fail to see how exactly I can achieve
> that.
> 
> I've traced the unrolling code to multiple places in the code (I'm
> working with the 4.3.2 version) and, for the moment, I'm trying to
> figure out if I can add something in the loop such as a note that I
> can later find in the FOR_EACH_LOOP loops in order to turn the
> unrolling for that particular loop off.
> 
> Have you got any ideas of what I could use like "note" or even a
> better idea all together?

the normal way of doing this is using a #pragma.  For instance,
icc implements #pragma nounroll for this purpose.  I have some prototype
implementation for gcc, I can send it to you if you were interested in
finishing it,

Zdenek

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

Yes, I'd be happy to look into how you did it or where you were up to.

I don't know what I'll be able to do but it might lead me in the right
direction and allow me to finish what you started.

Thanks,
Jc

On Tue, Oct 6, 2009 at 2:53 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> I was wondering if it was possible to turn off the unrolling to
>> certain loops. Basically, I'd like the compiler not to consider
>> certain loops for unrolling but fail to see how exactly I can achieve
>> that.
>>
>> I've traced the unrolling code to multiple places in the code (I'm
>> working with the 4.3.2 version) and, for the moment, I'm trying to
>> figure out if I can add something in the loop such as a note that I
>> can later find in the FOR_EACH_LOOP loops in order to turn the
>> unrolling for that particular loop off.
>>
>> Have you got any ideas of what I could use like "note" or even a
>> better idea all together?
>
> the normal way of doing this is using a #pragma.  For instance,
> icc implements #pragma nounroll for this purpose.  I have some prototype
> implementation for gcc, I can send it to you if you were interested in
> finishing it,
>
> Zdenek
>

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

Dear all,

I've been working on a loop unrolling scheme and I have a few questions:

1) Is there an interest in having a loop unrolling scheme for GCC? I'm
working on the 4.3.2 version but can port it afterwards to the 4.5
version or any version you think is appropriate.

2) I was using a simple example:

#pragma unroll 2
        for (i=0;i<6;i++)
        {
            printf ("Hello world\n");
        }

If I do this, instead of transforming the code into :
        for (i=0;i<3;i++)
        {
            printf ("Hello world\n");
            printf ("Hello world\n");
        }

as we could expect, it is transformed into:
        for (i=0;i<2;i++)
        {
            printf ("Hello world\n");
            printf ("Hello world\n");
        }
        for (i=0;i<2;i++)
        {
            printf ("Hello world\n");
        }


(I am using 4.3.2 currently)

I am using the tree_unroll_loop function to perform the unrolling and
it seems to always want to keep that epilogue. Is there a reason for
this? Or is this a bug of some sorts?

It seems that because the unrolling function wants always have this epilogue.

I've moved forwards (debugging wise) on this also but will wait to
know a bit of your input. I'll be looking at how to remove this
epilogue when it is not needed.

Thanks in advance,
Jc

Re: Turning off unrolling to certain loops

[Zdenek Dvorak]

Hi,

> 2) I was using a simple example:
> 
> #pragma unroll 2
>         for (i=0;i<6;i++)
>         {
>             printf ("Hello world\n");
>         }
> 
> If I do this, instead of transforming the code into :
>         for (i=0;i<3;i++)
>         {
>             printf ("Hello world\n");
>             printf ("Hello world\n");
>         }
> 
> as we could expect, it is transformed into:
>         for (i=0;i<2;i++)
>         {
>             printf ("Hello world\n");
>             printf ("Hello world\n");
>         }
>         for (i=0;i<2;i++)
>         {
>             printf ("Hello world\n");
>         }
> 
> 
> (I am using 4.3.2 currently)
> 
> I am using the tree_unroll_loop function to perform the unrolling and
> it seems to always want to keep that epilogue. Is there a reason for
> this? Or is this a bug of some sorts?

such an epilogue is needed when the # of iterations is not known in the
compile time; it should be fairly easy to modify the unrolling not to
emit it when it is not necessary,

Zdenek

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

Hi,

> such an epilogue is needed when the # of iterations is not known in the
> compile time; it should be fairly easy to modify the unrolling not to
> emit it when it is not necessary,

Agreed, that is why I was surprised to see this in my simple example.
It seems to me that the whole unrolling process has been made to, on
purpose, have this epilogue in place.

In the case where the unrolling would be perfect (ie. there would be
no epilogue), the calculation of the max bound of the unrolled version
is always done to have this epilogue (if you have 4 iterations and ask
to unroll twice, it will actually change the max bound to 3,
therefore, having one iteration of the unrolled version and 2
iterations of the original...). I am currently looking at the code of
tree_transform_and_unroll_loop to figure out how to change this and
not have an epilogue in my cases.

Jc

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

Ok, I've actually gone a different route. Instead of waiting for the
middle end to perform this, I've directly modified the parser stage to
unroll the loop directly there.

Basically, I take the parser of the for and modify how it adds the
various statements. Telling it to, instead of doing in the
c_finish_loop :

  if (body)
    add_stmt (body);
  if (clab)
    add_stmt (build1 (LABEL_EXPR, void_type_node, clab));
  if (incr)
    add_stmt (incr);
...

I tell it to add multiple copies of body and incr and the at the end
add in the loop the rest of it. I've also added support to remove
further unrolling to these modified loops and will be handling the
"No-unroll" pragma. I then let the rest of the optimization passes,
fuse the incrementations together if possible,  etc.

The initial results are quite good and seem to work and produce good code.

Currently, there are two possibilities :

- If the loop is not in the form we want, for example:

for (;i<n;)
{
    ...
}

Do we still unroll even though we have to trust the user that the
number of unrolling will not break the semantics ?

To handle this, I am adding warnings that will appear if the loop is
anything but :

for (i=C1; i < C2; i ++)
{
...
}

Later on, once this is thoroughly tested, I will allow :

for (i=C1; fct (i, C2); i = fct2 (i))


where fct is any comparison function with only i and C2,
         fct2 is a incrementation/decrementation calculation using i.


Any comments ? Concerns ? Questions ?
Thanks in advance,
Jc

On Thu, Oct 8, 2009 at 12:22 PM, Jean Christophe Beyler
<jean.christophe.beyler@gmail.com> wrote:
> Hi,
>
>> such an epilogue is needed when the # of iterations is not known in the
>> compile time; it should be fairly easy to modify the unrolling not to
>> emit it when it is not necessary,
>
> Agreed, that is why I was surprised to see this in my simple example.
> It seems to me that the whole unrolling process has been made to, on
> purpose, have this epilogue in place.
>
> In the case where the unrolling would be perfect (ie. there would be
> no epilogue), the calculation of the max bound of the unrolled version
> is always done to have this epilogue (if you have 4 iterations and ask
> to unroll twice, it will actually change the max bound to 3,
> therefore, having one iteration of the unrolled version and 2
> iterations of the original...). I am currently looking at the code of
> tree_transform_and_unroll_loop to figure out how to change this and
> not have an epilogue in my cases.
>
> Jc
>

Re: Turning off unrolling to certain loops

[Zdenek Dvorak]

Hi,

> Ok, I've actually gone a different route. Instead of waiting for the
> middle end to perform this, I've directly modified the parser stage to
> unroll the loop directly there.

I think this is a very bad idea.  First of all, getting the information
needed to decide at this stage whether unrolling is possible at all
is difficult; for instance, what happens for a loop of form

for (...)
  {
    something;
    label:
    something else;
  }

...

goto label;

?

Are you sure that you handle correctly loops with several exits from the
loop body, loops whose control variables may overflow, exception
handling, ...?  And if so, what is the benefit of having the code to
deal with all these complexities twice in the compiler?

Furthermore, unrolling the loops this early may increase compile time
with little or no gain in code quality.

Zdenek

RE: Turning off unrolling to certain loops

[Bingfeng Mei]

Hello,
I faced a similar issue a while ago. I filed a bug report 
(http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end, 
I implemented a simple tree-level unrolling pass in our port
which uses all the existing infrastructure. It works quite well for 
our purpose, but I hesitated to submit the patch because it contains
our not-very-elegannt #prgama unroll implementation. 

The following two functions do the unrolling. I insert the pass 
just after the loop_prefetch pass (4.4)

Cheers,
Bingfeng Mei


/* Perfect unrolling of a loop */
static void tree_unroll_perfect_loop (struct loop *loop, unsigned factor,
		  edge exit)
{
  sbitmap wont_exit;
  edge e;
  bool ok;
  unsigned i;
  VEC (edge, heap) *to_remove = NULL;
  
  /* Unroll the loop and remove the exits in all iterations except for the
     last one.  */
  wont_exit = sbitmap_alloc (factor);
  sbitmap_ones (wont_exit);
  RESET_BIT (wont_exit, factor - 1);

  ok = gimple_duplicate_loop_to_header_edge
	  (loop, loop_latch_edge (loop), factor - 1,
	   wont_exit, exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ);
  free (wont_exit);
  gcc_assert (ok);

  for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
    {
      ok = remove_path (e);
      gcc_assert (ok);
    }
  VEC_free (edge, heap, to_remove);
  update_ssa (TODO_update_ssa);
  
#ifdef ENABLE_CHECKING
  verify_flow_info ();
  verify_dominators (CDI_DOMINATORS);
  verify_loop_structure ();
  verify_loop_closed_ssa ();
#endif
}


                  
/* Go through all the loops: 
     1. Determine unrolling factor
     2. Unroll loops in different conditions
        -- perfect loop: no extra copy of original loop
        -- other loops: the original version of loops to execute the remaining iterations
*/        
static unsigned int rest_of_tree_unroll (void)
{
  loop_iterator li;
  struct loop *loop;
  unsigned ninsns, unroll_factor;
  HOST_WIDE_INT est_niter;
  struct tree_niter_desc desc;
  bool unrolled = false;

  initialize_original_copy_tables ();
  
  /* Scan the loops, inner ones first.  */
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
  {
     
     est_niter = estimated_loop_iterations_int (loop, false);
     ninsns = tree_num_loop_insns (loop, &eni_size_weights);
     unroll_factor = determine_unroll_factor (loop, ninsns, &desc, est_niter);
     if (unroll_factor != 1)
     {
       tree niters = number_of_exit_cond_executions(loop);
       
       bool perfect_unrolling = false;
       if(niters != NULL_TREE && niters!= chrec_dont_know && TREE_CODE(niters) == INTEGER_CST){
         int num_iters = tree_low_cst(niters, 1);
         if((num_iters % unroll_factor) == 0)
           perfect_unrolling = true;
       }
       
       /* If no. of iterations can be divided by unrolling factor, we have perfect unrolling */
       if(perfect_unrolling){
         tree_unroll_perfect_loop(loop, unroll_factor, single_dom_exit(loop));
       }
       else{
         tree_unroll_loop (loop, unroll_factor, single_dom_exit (loop), &desc);
       }  
       unrolled = true;
     }
  }  
  
  free_original_copy_tables ();
  
  /* Need to rebuild call graph due if new function calls are created due to
    loop unrolling 
    FIXME: rebuild cgraph will lose some information like reason of not inlining*/
  if(unrolled)  
    rebuild_cgraph_edges();
  /*debug_cgraph();*/
  
  return 0;
}

> -----Original Message-----
> From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org] On 
> Behalf Of Jean Christophe Beyler
> Sent: 14 October 2009 19:29
> To: Zdenek Dvorak
> Cc: gcc@gcc.gnu.org
> Subject: Re: Turning off unrolling to certain loops
> 
> Ok, I've actually gone a different route. Instead of waiting for the
> middle end to perform this, I've directly modified the parser stage to
> unroll the loop directly there.
> 
> Basically, I take the parser of the for and modify how it adds the
> various statements. Telling it to, instead of doing in the
> c_finish_loop :
> 
>   if (body)
>     add_stmt (body);
>   if (clab)
>     add_stmt (build1 (LABEL_EXPR, void_type_node, clab));
>   if (incr)
>     add_stmt (incr);
> ...
> 
> I tell it to add multiple copies of body and incr and the at the end
> add in the loop the rest of it. I've also added support to remove
> further unrolling to these modified loops and will be handling the
> "No-unroll" pragma. I then let the rest of the optimization passes,
> fuse the incrementations together if possible,  etc.
> 
> The initial results are quite good and seem to work and 
> produce good code.
> 
> Currently, there are two possibilities :
> 
> - If the loop is not in the form we want, for example:
> 
> for (;i<n;)
> {
>     ...
> }
> 
> Do we still unroll even though we have to trust the user that the
> number of unrolling will not break the semantics ?
> 
> To handle this, I am adding warnings that will appear if the loop is
> anything but :
> 
> for (i=C1; i < C2; i ++)
> {
> ...
> }
> 
> Later on, once this is thoroughly tested, I will allow :
> 
> for (i=C1; fct (i, C2); i = fct2 (i))
> 
> 
> where fct is any comparison function with only i and C2,
>          fct2 is a incrementation/decrementation calculation using i.
> 
> 
> Any comments ? Concerns ? Questions ?
> Thanks in advance,
> Jc
> 
> On Thu, Oct 8, 2009 at 12:22 PM, Jean Christophe Beyler
> <jean.christophe.beyler@gmail.com> wrote:
> > Hi,
> >
> >> such an epilogue is needed when the # of iterations is not 
> known in the
> >> compile time; it should be fairly easy to modify the 
> unrolling not to
> >> emit it when it is not necessary,
> >
> > Agreed, that is why I was surprised to see this in my 
> simple example.
> > It seems to me that the whole unrolling process has been made to, on
> > purpose, have this epilogue in place.
> >
> > In the case where the unrolling would be perfect (ie. there would be
> > no epilogue), the calculation of the max bound of the 
> unrolled version
> > is always done to have this epilogue (if you have 4 
> iterations and ask
> > to unroll twice, it will actually change the max bound to 3,
> > therefore, having one iteration of the unrolled version and 2
> > iterations of the original...). I am currently looking at 
> the code of
> > tree_transform_and_unroll_loop to figure out how to change this and
> > not have an epilogue in my cases.
> >
> > Jc
> >
> 
> 

Re: Turning off unrolling to certain loops

[Zdenek Dvorak]

Hi,

> I faced a similar issue a while ago. I filed a bug report 
> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end, 
> I implemented a simple tree-level unrolling pass in our port
> which uses all the existing infrastructure. It works quite well for 
> our purpose, but I hesitated to submit the patch because it contains
> our not-very-elegannt #prgama unroll implementation. 

could you please do so anyway?  Even if there are some issues with the
#prgama unroll implementation, it could serve as a basis of a usable
patch.

> /* Perfect unrolling of a loop */
> static void tree_unroll_perfect_loop (struct loop *loop, unsigned factor,
> 		  edge exit)
> {
> ...
> }
> 
> 
>                   
> /* Go through all the loops: 
>      1. Determine unrolling factor
>      2. Unroll loops in different conditions
>         -- perfect loop: no extra copy of original loop
>         -- other loops: the original version of loops to execute the remaining iterations
> */        
> static unsigned int rest_of_tree_unroll (void)
> {
...
>        tree niters = number_of_exit_cond_executions(loop);
>        
>        bool perfect_unrolling = false;
>        if(niters != NULL_TREE && niters!= chrec_dont_know && TREE_CODE(niters) == INTEGER_CST){
>          int num_iters = tree_low_cst(niters, 1);
>          if((num_iters % unroll_factor) == 0)
>            perfect_unrolling = true;
>        }
>        
>        /* If no. of iterations can be divided by unrolling factor, we have perfect unrolling */
>        if(perfect_unrolling){
>          tree_unroll_perfect_loop(loop, unroll_factor, single_dom_exit(loop));
>        }
>        else{
>          tree_unroll_loop (loop, unroll_factor, single_dom_exit (loop), &desc);
>        }

It would be better to move this test to tree_unroll_loop, and not
duplicate its code in tree_unroll_perfect_loop.

Zdenek

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

You are entirely correct, I hadn't thought that through enough.

So I backtracked and have just merged what Bingfeng Mei has done with
your code and have now a corrected version of the loop unrolling.

What I did was directly modified tree_unroll_loop to handle the case
of a perfect unroll or not internally and then used something similar
to what you had done around that. I added what I think is needed to
stop unrolling of those loops in later passes.

I'll be starting my tests but I can port it to 4.5 if you are
interested to see what I did.
Jc

On Thu, Oct 15, 2009 at 6:00 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> I faced a similar issue a while ago. I filed a bug report
>> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end,
>> I implemented a simple tree-level unrolling pass in our port
>> which uses all the existing infrastructure. It works quite well for
>> our purpose, but I hesitated to submit the patch because it contains
>> our not-very-elegannt #prgama unroll implementation.
>
> could you please do so anyway?  Even if there are some issues with the
> #prgama unroll implementation, it could serve as a basis of a usable
> patch.
>
>> /* Perfect unrolling of a loop */
>> static void tree_unroll_perfect_loop (struct loop *loop, unsigned factor,
>>                 edge exit)
>> {
>> ...
>> }
>>
>>
>>
>> /* Go through all the loops:
>>      1. Determine unrolling factor
>>      2. Unroll loops in different conditions
>>         -- perfect loop: no extra copy of original loop
>>         -- other loops: the original version of loops to execute the remaining iterations
>> */
>> static unsigned int rest_of_tree_unroll (void)
>> {
> ...
>>        tree niters = number_of_exit_cond_executions(loop);
>>
>>        bool perfect_unrolling = false;
>>        if(niters != NULL_TREE && niters!= chrec_dont_know && TREE_CODE(niters) == INTEGER_CST){
>>          int num_iters = tree_low_cst(niters, 1);
>>          if((num_iters % unroll_factor) == 0)
>>            perfect_unrolling = true;
>>        }
>>
>>        /* If no. of iterations can be divided by unrolling factor, we have perfect unrolling */
>>        if(perfect_unrolling){
>>          tree_unroll_perfect_loop(loop, unroll_factor, single_dom_exit(loop));
>>        }
>>        else{
>>          tree_unroll_loop (loop, unroll_factor, single_dom_exit (loop), &desc);
>>        }
>
> It would be better to move this test to tree_unroll_loop, and not
> duplicate its code in tree_unroll_perfect_loop.
>
> Zdenek
>

RE: Turning off unrolling to certain loops

[Bingfeng Mei]

Jc,
How did you implement #pragma unroll?  I checked other compilers. The
pragma should govern the next immediate loop. It took me a while to 
find a not-so-elegant way to do that. I also implemented #pragma ivdep.
These information are supposed to be passed through both tree and RTL
levels and suvive all GCC optimization. I still have problem in handling
combination of unroll and ivdep.

Bingfeng

> -----Original Message-----
> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com] 
> On Behalf Of Jean Christophe Beyler
> Sent: 15 October 2009 16:34
> To: Zdenek Dvorak
> Cc: Bingfeng Mei; gcc@gcc.gnu.org
> Subject: Re: Turning off unrolling to certain loops
> 
> You are entirely correct, I hadn't thought that through enough.
> 
> So I backtracked and have just merged what Bingfeng Mei has done with
> your code and have now a corrected version of the loop unrolling.
> 
> What I did was directly modified tree_unroll_loop to handle the case
> of a perfect unroll or not internally and then used something similar
> to what you had done around that. I added what I think is needed to
> stop unrolling of those loops in later passes.
> 
> I'll be starting my tests but I can port it to 4.5 if you are
> interested to see what I did.
> Jc
> 
> On Thu, Oct 15, 2009 at 6:00 AM, Zdenek Dvorak 
> <rakdver@kam.mff.cuni.cz> wrote:
> > Hi,
> >
> >> I faced a similar issue a while ago. I filed a bug report
> >> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end,
> >> I implemented a simple tree-level unrolling pass in our port
> >> which uses all the existing infrastructure. It works quite well for
> >> our purpose, but I hesitated to submit the patch because 
> it contains
> >> our not-very-elegannt #prgama unroll implementation.
> >
> > could you please do so anyway?  Even if there are some 
> issues with the
> > #prgama unroll implementation, it could serve as a basis of a usable
> > patch.
> >
> >> /* Perfect unrolling of a loop */
> >> static void tree_unroll_perfect_loop (struct loop *loop, 
> unsigned factor,
> >>                 edge exit)
> >> {
> >> ...
> >> }
> >>
> >>
> >>
> >> /* Go through all the loops:
> >>      1. Determine unrolling factor
> >>      2. Unroll loops in different conditions
> >>         -- perfect loop: no extra copy of original loop
> >>         -- other loops: the original version of loops to 
> execute the remaining iterations
> >> */
> >> static unsigned int rest_of_tree_unroll (void)
> >> {
> > ...
> >>        tree niters = number_of_exit_cond_executions(loop);
> >>
> >>        bool perfect_unrolling = false;
> >>        if(niters != NULL_TREE && niters!= chrec_dont_know 
> && TREE_CODE(niters) == INTEGER_CST){
> >>          int num_iters = tree_low_cst(niters, 1);
> >>          if((num_iters % unroll_factor) == 0)
> >>            perfect_unrolling = true;
> >>        }
> >>
> >>        /* If no. of iterations can be divided by unrolling 
> factor, we have perfect unrolling */
> >>        if(perfect_unrolling){
> >>          tree_unroll_perfect_loop(loop, unroll_factor, 
> single_dom_exit(loop));
> >>        }
> >>        else{
> >>          tree_unroll_loop (loop, unroll_factor, 
> single_dom_exit (loop), &desc);
> >>        }
> >
> > It would be better to move this test to tree_unroll_loop, and not
> > duplicate its code in tree_unroll_perfect_loop.
> >
> > Zdenek
> >
> 
> 

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

I implemented it like this:

- I modified c_parser_for_statement to include a pragma tree node in
the loop with the unrolling request as an argument

- Then during my pass to handle unrolling, I parse the loop to find the pragma.
         - I retrieve the unrolling factor and use a merge of Zdenek's
code and yours to perform either a perfect unrolling or  and register
it in the loop structure

          - During the following passes that handle loop unrolling, I
look at that variable in the loop structure to see if yes or no, we
should allow the normal execution of the unrolling

          - During the expand, I transform the pragma into a note that
will allow me to remove any unrolling at that point.

That is what I did and it seems to work quite well.

Of course, I have a few things I am currently considering:
    - Is there really a position that is better for the pragma node in
the tree representation ?
    - Can other passes actually move that node out of a given loop
before I register it in the loop ?
    - Should I, instead of keeping that node through the tree
optimizations, actually remove it and later on add it just before
expansion ?
    - Can an RTL pass remove notes or move them out of a loop ?
    - Can the tree node or note change whether or not an optimization
takes place?
    - It is important to note that after the registration, the pragma
node or note are actually just there to say "don't do anything",
therefore, the number of nodes or notes in the loop is not important
as long as they are not moved out.

Those are my current concerns :-), I can give more information if requested,
Jc

PS: What exactly was your solution to this issue?


On Thu, Oct 15, 2009 at 12:11 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
> Jc,
> How did you implement #pragma unroll?  I checked other compilers. The
> pragma should govern the next immediate loop. It took me a while to
> find a not-so-elegant way to do that. I also implemented #pragma ivdep.
> These information are supposed to be passed through both tree and RTL
> levels and suvive all GCC optimization. I still have problem in handling
> combination of unroll and ivdep.
>
> Bingfeng
>
>> -----Original Message-----
>> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com]
>> On Behalf Of Jean Christophe Beyler
>> Sent: 15 October 2009 16:34
>> To: Zdenek Dvorak
>> Cc: Bingfeng Mei; gcc@gcc.gnu.org
>> Subject: Re: Turning off unrolling to certain loops
>>
>> You are entirely correct, I hadn't thought that through enough.
>>
>> So I backtracked and have just merged what Bingfeng Mei has done with
>> your code and have now a corrected version of the loop unrolling.
>>
>> What I did was directly modified tree_unroll_loop to handle the case
>> of a perfect unroll or not internally and then used something similar
>> to what you had done around that. I added what I think is needed to
>> stop unrolling of those loops in later passes.
>>
>> I'll be starting my tests but I can port it to 4.5 if you are
>> interested to see what I did.
>> Jc
>>
>> On Thu, Oct 15, 2009 at 6:00 AM, Zdenek Dvorak
>> <rakdver@kam.mff.cuni.cz> wrote:
>> > Hi,
>> >
>> >> I faced a similar issue a while ago. I filed a bug report
>> >> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end,
>> >> I implemented a simple tree-level unrolling pass in our port
>> >> which uses all the existing infrastructure. It works quite well for
>> >> our purpose, but I hesitated to submit the patch because
>> it contains
>> >> our not-very-elegannt #prgama unroll implementation.
>> >
>> > could you please do so anyway?  Even if there are some
>> issues with the
>> > #prgama unroll implementation, it could serve as a basis of a usable
>> > patch.
>> >
>> >> /* Perfect unrolling of a loop */
>> >> static void tree_unroll_perfect_loop (struct loop *loop,
>> unsigned factor,
>> >>                 edge exit)
>> >> {
>> >> ...
>> >> }
>> >>
>> >>
>> >>
>> >> /* Go through all the loops:
>> >>      1. Determine unrolling factor
>> >>      2. Unroll loops in different conditions
>> >>         -- perfect loop: no extra copy of original loop
>> >>         -- other loops: the original version of loops to
>> execute the remaining iterations
>> >> */
>> >> static unsigned int rest_of_tree_unroll (void)
>> >> {
>> > ...
>> >>        tree niters = number_of_exit_cond_executions(loop);
>> >>
>> >>        bool perfect_unrolling = false;
>> >>        if(niters != NULL_TREE && niters!= chrec_dont_know
>> && TREE_CODE(niters) == INTEGER_CST){
>> >>          int num_iters = tree_low_cst(niters, 1);
>> >>          if((num_iters % unroll_factor) == 0)
>> >>            perfect_unrolling = true;
>> >>        }
>> >>
>> >>        /* If no. of iterations can be divided by unrolling
>> factor, we have perfect unrolling */
>> >>        if(perfect_unrolling){
>> >>          tree_unroll_perfect_loop(loop, unroll_factor,
>> single_dom_exit(loop));
>> >>        }
>> >>        else{
>> >>          tree_unroll_loop (loop, unroll_factor,
>> single_dom_exit (loop), &desc);
>> >>        }
>> >
>> > It would be better to move this test to tree_unroll_loop, and not
>> > duplicate its code in tree_unroll_perfect_loop.
>> >
>> > Zdenek
>> >
>>
>>
>

RE: Turning off unrolling to certain loops

[Bingfeng Mei]

The basic idea is the same as what is described in this thread.
 http://gcc.gnu.org/ml/gcc/2008-05/msg00436.html
But I made many changes on Alex's method. 

Pragmas are encoded into names of the helper functions because
they are not optimized out by tree-level optimizer. These
pseudo functions are either be consumed by target-builtins.c
if it is only used at tree-level (unroll) or be replaced in
target-builtins.c with special rtl NOTE(ivdep). 

To ensure the right scope of these loop pragmas, I also modified
c_parser_for_statement, c_parser_while_statemennt, etc, to check
loop level. I define that these pragmas only control the next 
innnermost loop. Once the right scope of the pragma is determined,
I actually generate two helper functions for each pragma. The second 
is to close the scope of the pragma.

When the pragma is used, I just search backward for preceding 
helper function (tree-level) or special note (rtl-level)


Bingfeng

> -----Original Message-----
> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com] 
> On Behalf Of Jean Christophe Beyler
> Sent: 15 October 2009 17:27
> To: Bingfeng Mei
> Cc: Zdenek Dvorak; gcc@gcc.gnu.org
> Subject: Re: Turning off unrolling to certain loops
> 
> I implemented it like this:
> 
> - I modified c_parser_for_statement to include a pragma tree node in
> the loop with the unrolling request as an argument
> 
> - Then during my pass to handle unrolling, I parse the loop 
> to find the pragma.
>          - I retrieve the unrolling factor and use a merge of Zdenek's
> code and yours to perform either a perfect unrolling or  and register
> it in the loop structure
> 
>           - During the following passes that handle loop unrolling, I
> look at that variable in the loop structure to see if yes or no, we
> should allow the normal execution of the unrolling
> 
>           - During the expand, I transform the pragma into a note that
> will allow me to remove any unrolling at that point.
> 
> That is what I did and it seems to work quite well.
> 
> Of course, I have a few things I am currently considering:
>     - Is there really a position that is better for the pragma node in
> the tree representation ?
>     - Can other passes actually move that node out of a given loop
> before I register it in the loop ?
>     - Should I, instead of keeping that node through the tree
> optimizations, actually remove it and later on add it just before
> expansion ?
>     - Can an RTL pass remove notes or move them out of a loop ?
>     - Can the tree node or note change whether or not an optimization
> takes place?
>     - It is important to note that after the registration, the pragma
> node or note are actually just there to say "don't do anything",
> therefore, the number of nodes or notes in the loop is not important
> as long as they are not moved out.
> 
> Those are my current concerns :-), I can give more 
> information if requested,
> Jc
> 
> PS: What exactly was your solution to this issue?
> 
> 
> On Thu, Oct 15, 2009 at 12:11 PM, Bingfeng Mei 
> <bmei@broadcom.com> wrote:
> > Jc,
> > How did you implement #pragma unroll?  I checked other 
> compilers. The
> > pragma should govern the next immediate loop. It took me a while to
> > find a not-so-elegant way to do that. I also implemented 
> #pragma ivdep.
> > These information are supposed to be passed through both 
> tree and RTL
> > levels and suvive all GCC optimization. I still have 
> problem in handling
> > combination of unroll and ivdep.
> >
> > Bingfeng
> >
> >> -----Original Message-----
> >> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com]
> >> On Behalf Of Jean Christophe Beyler
> >> Sent: 15 October 2009 16:34
> >> To: Zdenek Dvorak
> >> Cc: Bingfeng Mei; gcc@gcc.gnu.org
> >> Subject: Re: Turning off unrolling to certain loops
> >>
> >> You are entirely correct, I hadn't thought that through enough.
> >>
> >> So I backtracked and have just merged what Bingfeng Mei 
> has done with
> >> your code and have now a corrected version of the loop unrolling.
> >>
> >> What I did was directly modified tree_unroll_loop to 
> handle the case
> >> of a perfect unroll or not internally and then used 
> something similar
> >> to what you had done around that. I added what I think is needed to
> >> stop unrolling of those loops in later passes.
> >>
> >> I'll be starting my tests but I can port it to 4.5 if you are
> >> interested to see what I did.
> >> Jc
> >>
> >> On Thu, Oct 15, 2009 at 6:00 AM, Zdenek Dvorak
> >> <rakdver@kam.mff.cuni.cz> wrote:
> >> > Hi,
> >> >
> >> >> I faced a similar issue a while ago. I filed a bug report
> >> >> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end,
> >> >> I implemented a simple tree-level unrolling pass in our port
> >> >> which uses all the existing infrastructure. It works 
> quite well for
> >> >> our purpose, but I hesitated to submit the patch because
> >> it contains
> >> >> our not-very-elegannt #prgama unroll implementation.
> >> >
> >> > could you please do so anyway?  Even if there are some
> >> issues with the
> >> > #prgama unroll implementation, it could serve as a basis 
> of a usable
> >> > patch.
> >> >
> >> >> /* Perfect unrolling of a loop */
> >> >> static void tree_unroll_perfect_loop (struct loop *loop,
> >> unsigned factor,
> >> >>                 edge exit)
> >> >> {
> >> >> ...
> >> >> }
> >> >>
> >> >>
> >> >>
> >> >> /* Go through all the loops:
> >> >>      1. Determine unrolling factor
> >> >>      2. Unroll loops in different conditions
> >> >>         -- perfect loop: no extra copy of original loop
> >> >>         -- other loops: the original version of loops to
> >> execute the remaining iterations
> >> >> */
> >> >> static unsigned int rest_of_tree_unroll (void)
> >> >> {
> >> > ...
> >> >>        tree niters = number_of_exit_cond_executions(loop);
> >> >>
> >> >>        bool perfect_unrolling = false;
> >> >>        if(niters != NULL_TREE && niters!= chrec_dont_know
> >> && TREE_CODE(niters) == INTEGER_CST){
> >> >>          int num_iters = tree_low_cst(niters, 1);
> >> >>          if((num_iters % unroll_factor) == 0)
> >> >>            perfect_unrolling = true;
> >> >>        }
> >> >>
> >> >>        /* If no. of iterations can be divided by unrolling
> >> factor, we have perfect unrolling */
> >> >>        if(perfect_unrolling){
> >> >>          tree_unroll_perfect_loop(loop, unroll_factor,
> >> single_dom_exit(loop));
> >> >>        }
> >> >>        else{
> >> >>          tree_unroll_loop (loop, unroll_factor,
> >> single_dom_exit (loop), &desc);
> >> >>        }
> >> >
> >> > It would be better to move this test to tree_unroll_loop, and not
> >> > duplicate its code in tree_unroll_perfect_loop.
> >> >
> >> > Zdenek
> >> >
> >>
> >>
> >
> 
> 

Re: Turning off unrolling to certain loops

[Jean Christophe Beyler]

Wow, it seems more complicated then me.

I think I will modify my approach to :

- Add a node PRAGMA in the tree level when parsing the loop

- As soon as the loop structures are in place, find the pragma, update
the loop structure, remove the node

- Before the loop structure is lost due to the transformation to RTL,
create a note in the loop

- As soon as the loop structures are valid again in RTL, find the
notes and update the loop structures again, remove the notes


For the moment, though I don't remove the nodes like I just said, I
see no problems with this solutions, I've tried on multiple examples,
single loops or nested loops, and it seems to be working fine.

I will continue the testing, at worse, I'll change the notes to an
RTL, my question is, how do you force it to not be taken out of the
loop and how do you ensure it does not affect later pass optimizations
? I suppose you can remove them once you register their presence.

Jc

On Fri, Oct 16, 2009 at 5:09 AM, Bingfeng Mei <bmei@broadcom.com> wrote:
> The basic idea is the same as what is described in this thread.
>  http://gcc.gnu.org/ml/gcc/2008-05/msg00436.html
> But I made many changes on Alex's method.
>
> Pragmas are encoded into names of the helper functions because
> they are not optimized out by tree-level optimizer. These
> pseudo functions are either be consumed by target-builtins.c
> if it is only used at tree-level (unroll) or be replaced in
> target-builtins.c with special rtl NOTE(ivdep).
>
> To ensure the right scope of these loop pragmas, I also modified
> c_parser_for_statement, c_parser_while_statemennt, etc, to check
> loop level. I define that these pragmas only control the next
> innnermost loop. Once the right scope of the pragma is determined,
> I actually generate two helper functions for each pragma. The second
> is to close the scope of the pragma.
>
> When the pragma is used, I just search backward for preceding
> helper function (tree-level) or special note (rtl-level)
>
>
> Bingfeng
>
>> -----Original Message-----
>> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com]
>> On Behalf Of Jean Christophe Beyler
>> Sent: 15 October 2009 17:27
>> To: Bingfeng Mei
>> Cc: Zdenek Dvorak; gcc@gcc.gnu.org
>> Subject: Re: Turning off unrolling to certain loops
>>
>> I implemented it like this:
>>
>> - I modified c_parser_for_statement to include a pragma tree node in
>> the loop with the unrolling request as an argument
>>
>> - Then during my pass to handle unrolling, I parse the loop
>> to find the pragma.
>>          - I retrieve the unrolling factor and use a merge of Zdenek's
>> code and yours to perform either a perfect unrolling or  and register
>> it in the loop structure
>>
>>           - During the following passes that handle loop unrolling, I
>> look at that variable in the loop structure to see if yes or no, we
>> should allow the normal execution of the unrolling
>>
>>           - During the expand, I transform the pragma into a note that
>> will allow me to remove any unrolling at that point.
>>
>> That is what I did and it seems to work quite well.
>>
>> Of course, I have a few things I am currently considering:
>>     - Is there really a position that is better for the pragma node in
>> the tree representation ?
>>     - Can other passes actually move that node out of a given loop
>> before I register it in the loop ?
>>     - Should I, instead of keeping that node through the tree
>> optimizations, actually remove it and later on add it just before
>> expansion ?
>>     - Can an RTL pass remove notes or move them out of a loop ?
>>     - Can the tree node or note change whether or not an optimization
>> takes place?
>>     - It is important to note that after the registration, the pragma
>> node or note are actually just there to say "don't do anything",
>> therefore, the number of nodes or notes in the loop is not important
>> as long as they are not moved out.
>>
>> Those are my current concerns :-), I can give more
>> information if requested,
>> Jc
>>
>> PS: What exactly was your solution to this issue?
>>
>>
>> On Thu, Oct 15, 2009 at 12:11 PM, Bingfeng Mei
>> <bmei@broadcom.com> wrote:
>> > Jc,
>> > How did you implement #pragma unroll?  I checked other
>> compilers. The
>> > pragma should govern the next immediate loop. It took me a while to
>> > find a not-so-elegant way to do that. I also implemented
>> #pragma ivdep.
>> > These information are supposed to be passed through both
>> tree and RTL
>> > levels and suvive all GCC optimization. I still have
>> problem in handling
>> > combination of unroll and ivdep.
>> >
>> > Bingfeng
>> >
>> >> -----Original Message-----
>> >> From: fearyourself@gmail.com [mailto:fearyourself@gmail.com]
>> >> On Behalf Of Jean Christophe Beyler
>> >> Sent: 15 October 2009 16:34
>> >> To: Zdenek Dvorak
>> >> Cc: Bingfeng Mei; gcc@gcc.gnu.org
>> >> Subject: Re: Turning off unrolling to certain loops
>> >>
>> >> You are entirely correct, I hadn't thought that through enough.
>> >>
>> >> So I backtracked and have just merged what Bingfeng Mei
>> has done with
>> >> your code and have now a corrected version of the loop unrolling.
>> >>
>> >> What I did was directly modified tree_unroll_loop to
>> handle the case
>> >> of a perfect unroll or not internally and then used
>> something similar
>> >> to what you had done around that. I added what I think is needed to
>> >> stop unrolling of those loops in later passes.
>> >>
>> >> I'll be starting my tests but I can port it to 4.5 if you are
>> >> interested to see what I did.
>> >> Jc
>> >>
>> >> On Thu, Oct 15, 2009 at 6:00 AM, Zdenek Dvorak
>> >> <rakdver@kam.mff.cuni.cz> wrote:
>> >> > Hi,
>> >> >
>> >> >> I faced a similar issue a while ago. I filed a bug report
>> >> >> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36712) In the end,
>> >> >> I implemented a simple tree-level unrolling pass in our port
>> >> >> which uses all the existing infrastructure. It works
>> quite well for
>> >> >> our purpose, but I hesitated to submit the patch because
>> >> it contains
>> >> >> our not-very-elegannt #prgama unroll implementation.
>> >> >
>> >> > could you please do so anyway?  Even if there are some
>> >> issues with the
>> >> > #prgama unroll implementation, it could serve as a basis
>> of a usable
>> >> > patch.
>> >> >
>> >> >> /* Perfect unrolling of a loop */
>> >> >> static void tree_unroll_perfect_loop (struct loop *loop,
>> >> unsigned factor,
>> >> >>                 edge exit)
>> >> >> {
>> >> >> ...
>> >> >> }
>> >> >>
>> >> >>
>> >> >>
>> >> >> /* Go through all the loops:
>> >> >>      1. Determine unrolling factor
>> >> >>      2. Unroll loops in different conditions
>> >> >>         -- perfect loop: no extra copy of original loop
>> >> >>         -- other loops: the original version of loops to
>> >> execute the remaining iterations
>> >> >> */
>> >> >> static unsigned int rest_of_tree_unroll (void)
>> >> >> {
>> >> > ...
>> >> >>        tree niters = number_of_exit_cond_executions(loop);
>> >> >>
>> >> >>        bool perfect_unrolling = false;
>> >> >>        if(niters != NULL_TREE && niters!= chrec_dont_know
>> >> && TREE_CODE(niters) == INTEGER_CST){
>> >> >>          int num_iters = tree_low_cst(niters, 1);
>> >> >>          if((num_iters % unroll_factor) == 0)
>> >> >>            perfect_unrolling = true;
>> >> >>        }
>> >> >>
>> >> >>        /* If no. of iterations can be divided by unrolling
>> >> factor, we have perfect unrolling */
>> >> >>        if(perfect_unrolling){
>> >> >>          tree_unroll_perfect_loop(loop, unroll_factor,
>> >> single_dom_exit(loop));
>> >> >>        }
>> >> >>        else{
>> >> >>          tree_unroll_loop (loop, unroll_factor,
>> >> single_dom_exit (loop), &desc);
>> >> >>        }
>> >> >
>> >> > It would be better to move this test to tree_unroll_loop, and not
>> >> > duplicate its code in tree_unroll_perfect_loop.
>> >> >
>> >> > Zdenek
>> >> >
>> >>
>> >>
>> >
>>
>>
>