This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Proposal for another approach for Loop transformation with conditional in Loops.


On March 17, 2015 3:37:25 PM GMT+01:00, Jeff Law <law@redhat.com> wrote:
>On 03/16/2015 09:45 PM, Ajit Kumar Agarwal wrote:
>>
>>
>> -----Original Message-----
>> From: Jeff Law [mailto:law@redhat.com]
>> Sent: Monday, March 16, 2015 11:45 PM
>> To: Ajit Kumar Agarwal; Richard Biener; gcc@gcc.gnu.org
>> Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju
>Mekala
>> Subject: Re: Proposal for another approach for Loop transformation
>with conditional in Loops.
>>
>> On 03/14/15 22:40, Ajit Kumar Agarwal wrote:
>>> Hello All:
>>>
>>> I am proposing the new approach to Loop transformation as given
>below
>>> in the example For the loops with conditional expression inside the
>>> Loops. The Loop body should be reducible control flow graph. The
>>> iteration space is partitioned into different spaces for which
>either
>>> the cond_expr is true or cond_expr  is false. The evaluation of
>>> cond_expr for the partitioned iteration spaces can be determined
>statically. For the partitioned iterations and based on the analysis of
>cond_expr on the partitioned iterations spaces the Loops in fig (a)
>will be transformed to Loops in fig (b).
>>>
>>> for the iteration spaces of the conditional inside the loop is live
>in
>>> at the entry of the cond_expr and Live out the Control flow graph is
>>> topological ordered with the basic blocks for the conditional CFG
>and the partitioned iteration spaces can be formed for which the spaces
>can be true for conditional expr and false and unknown.
>>>
>>> Based on the above info and analysis the Loop of Fig (a) will be
>transformed to Loop Fig (b).
>>>
>>> This is much more optimized code as compared to the performance. The
>>> cases will be triggered for SPEC Benchmarks. Loops is partitioned to
>>> different version with different iteration spaces. Optimized in the
>presence Of the transformed generation of the loops without
>conditional.
>> I fail to see how this is dramatically different than unswitching.  
>You
>> pull the condition out (it has to be loop invariant), then have two
>instances of the loop, one for the THEN, the other for the ELSE.  You
>obviously select one or the other based on the condition of V.
>>
>>>> Specific examples might be helpful in understanding how you see
>this as different than unswitching.
>>
>> For ( I = 1; I < 5; i++)
>>    For ( j =1; j<=5;j++)
>>      If ( I >3 && j >3)
>>       A[i][j] = a[i+1][j-1];
>>      Else
>>         A{i][j] = 0;
>>     End
>> End
>>
>> Fig (1)
>>
>> For ( I = 1; I <= 3;i++)
>>    For(j= 4; j <= 5; j++)
>>      A[i][j] = 0;
>>
>> For( I = 4; I <= 5; i++)
>>    For(j = 4; j <=5;j++)
>>       A[i][j]= a[i+1][j-1];
>>
>> For( (I = 1; I <=5 ;i++)
>>    For(j = 1; j <= 3;j++)
>>      A[i][j] = 0;
>>
>> Fig(2) Transformed code for Fig(1).
>>
>> Fig(1) is the original code and Fig(2) is the transformed code for
>fig(1).
>Ah, I see, you're changing the loop iteration space.   Not sure how I 
>missed that the first time around.
>
>How often does this happen in practice?  Are there specific routines in
>
>SPEC that would benefit from this kind of transformation?

It's usually an enablement transform for other transforms. In the case of hmmer  it would enable vectorization. But if it is basically peeling it can also enable fusion for example.

Richard.

>jeff



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]