This is the mail archive of the
mailing list for the GCC project.
Re: More of a Loop distribution.
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- Cc: Jeff Law <law at redhat dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>, Vinod Kathail <vinodk at xilinx dot com>, Shail Aditya Gupta <shailadi at xilinx dot com>, Vidhumouli Hunsigida <vidhum at xilinx dot com>, Nagaraju Mekala <nmekala at xilinx dot com>
- Date: Fri, 14 Aug 2015 09:23:57 +0200
- Subject: Re: More of a Loop distribution.
- Authentication-results: sourceware.org; auth=none
- References: <37378DC5BCD0EE48BA4B082E0B55DFAA42959F07 at XAP-PVEXMBX02 dot xlnx dot xilinx dot com> <CAFiYyc3o7zKrbu4UVsmqoh5Lw+uBfaASA_vP8YaqzQm8sT_5Rg at mail dot gmail dot com> <37378DC5BCD0EE48BA4B082E0B55DFAA4295A47A at XAP-PVEXMBX02 dot xlnx dot xilinx dot com> <8D796B7F-FC86-45CE-8DF7-A4278E01554A at gmail dot com> <37378DC5BCD0EE48BA4B082E0B55DFAA4295A4F1 at XAP-PVEXMBX02 dot xlnx dot xilinx dot com>
On Fri, Aug 14, 2015 at 8:13 AM, Ajit Kumar Agarwal
> -----Original Message-----
> From: Richard Biener [mailto:email@example.com]
> Sent: Friday, August 14, 2015 11:30 AM
> To: Ajit Kumar Agarwal
> Cc: Jeff Law; firstname.lastname@example.org; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
> Subject: RE: More of a Loop distribution.
> On August 14, 2015 4:59:07 AM GMT+02:00, Ajit Kumar Agarwal <email@example.com> wrote:
>>From: Richard Biener [mailto:firstname.lastname@example.org]
>>Sent: Thursday, August 13, 2015 3:23 PM
>>To: Ajit Kumar Agarwal
>>Cc: Jeff Law; email@example.com; Vinod Kathail; Shail Aditya Gupta;
>>Vidhumouli Hunsigida; Nagaraju Mekala
>>Subject: Re: More of a Loop distribution.
>>On Thu, Aug 13, 2015 at 9:37 AM, Ajit Kumar Agarwal
>>> Loop distribution considers DDG to decide on distributing the Loops.
>>> The Loops with control statements like IF-THEN-ELSE can also be
>>> Distributed. Instead of Data Dependency Graph, the Control Dependence
>>Graph should be considered in order to distribute the loops In presence
>>of control Statements.
>>> Also the presence of multiple exits in the Loop can also be
>>considered for Loop distribution transformation.
>>> Thus the above transformation helps in the Libquantum benchmarks for
>>> There are following articles that looks interesting to me.
>>> "Loop Distribution in presence of arbitrarily control flow Ken
>>> "Loop Distribution in presence of Multiple Exits Bor-Ming Hsieh
>>> I don't think the loop distribution in presence of control flow is
>>implemented in GCC/LLVM.
>>> I think it is feasible to consider the above for the implementation
>>>>It's true that loop distribution does not try to distribute based on
>>any control structure heuristics but it only considers data locality.
>>It does however already >>compute the control dependence graph (and
>>uses it to add control edges to the DDG to properly add data dependence
>>edges to uses of control statements >>necessary in partitions).
>>>>So it should be a matter of specifying the proper set of starting
>>statements it tries separating.
>>>>Not sure which kind of distribution you are after, can you give an
>>I would like to have a distribution of the loop having control flow.
>>For (I = 2 ; I < N; i++)
>> If (condition)
>> S1: A[i] = ...
>> S2: D[i] = A[i-1]...
>>The above loop can be distributed with two loops having one loop with
>>S1 inside IF and another loop with S2 with the IF.
>>The two scenario can be true.
>>1. The condition inside IF have a check on A[i] and is dependent on S1.
>>In this case the distribution is difficult. And the above article From
>>Ken Kennedy et.al does store the partial results of comparison in an
>>temporary array and that array is compared inside the IF Condition.
>>This makes the loop distributed. This is what I was looking for which I
>>found in the above article.
>>2. The condition inside the IF in the above loop is not dependent on
>>the S1 and S2 , and this case the loop can be distributed.
>>In the above two scenario the GCC can't distribute the loop, as the
>>control dependency graph ( control structure ) is not used.
>>>The above loop can be distributed by gcc just fine.
> Existing loop distribution implementation in GCC distributes the above loop in both the above scenario's?
GCC cannot do the trick of computing the condition into a temporary
array. What it does
(and may then reject for dependence reasons) is to have the original
condition (including an
eventual reference to A[i]) in both partitions containing S1 and S2.
So if the exact thing
for (i = 0; i < N; i++)
A[i] = ...;
D[i] = A[i-1] ...;
then I see no dependence that makes distributing into
for (i = 0; i < N; i++)
D[i] = A[i-1] ...;
for (i =0; i < N; i++)
A[i] = ...;
invalid. But as the testcase isn't complete or compilable I can't
what GCC does here. I would think loop distributions cost metric would reject
this distribution because A is accessed in both loops, but as said, only real
code examples will show.
All I wanted to say is the underlying support is there in loop
distribution - where
current loop distribution is lacking is a) determining the desired partitioning
(by determining the stmts to distribute) and b) the cost model that fuses back
partitions that are related.
Oh, and of course CSE comes in the way of both cost modeling and actual
dependences. Loop distribution doesn't understand to reload an expression
from memory if it sees
tem = B[i] + C[i];
A[i] = tem; (1)
D[i] = tem; (2)
then the partitions containing (1) and (2) will both have the tem =
B[i] + C[i] compute
inside them - there isn't any code trying to replace that with A[i] or
D[i] in either
partition. I think that's the most important thing to improve with
GCCs loop distribution
pass (as it will also fix some of the cost modelling issues).
> Thanks & Regards
>>The above loop distribution makes the loop vectorizable which otherwise
>>not possible due to presence of multiple statements inside the IF and
>>Also may not be IF-converted due to presence of multiple statements. If
>>we distribute the loop for the above two scenarios the individual loops
>>in the distributed loop can be vectorized which is otherwise not
>>Thanks & Regards
>>> Thanks & Regards