Re: Turning off unrolling to certain loops

[Jean Christophe Beyler <jean.christophe.beyler@gmail.com>]

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
>> >> >
>> >>
>> >>
>> >
>>
>>
>