This is the mail archive of the
mailing list for the GCC project.
RE: Proposal for another approach for Loop transformation with conditional in Loops.
- From: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- To: Aditya K <hiraditya at msn dot com>, Jeff Law <law at redhat dot com>, Richard Biener <richard dot guenther at gmail dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Cc: 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: Sun, 15 Mar 2015 06:26:30 +0000
- Subject: RE: Proposal for another approach for Loop transformation with conditional in Loops.
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=pass (sender IP is 22.214.171.124) smtp dot mailfrom=ajit dot kumar dot agarwal at xilinx dot com; gmail.com; dkim=none (message not signed) header.d=none;
- References: <BN1BFFO11OLC00152B62B175CC7F96E1424AE050 at BN1BFFO11OLC001 dot protection dot gbl> <BLU179-W599EE58593138D23A6CF7BB6050 at phx dot gbl>
From: Aditya K [mailto:firstname.lastname@example.org]
Sent: Sunday, March 15, 2015 11:37 AM
To: Ajit Kumar Agarwal; Jeff Law; Richard Biener; email@example.com
Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: RE: Proposal for another approach for Loop transformation with conditional in Loops.
> From: firstname.lastname@example.org
> To: email@example.com; firstname.lastname@example.org; email@example.com
> CC: firstname.lastname@example.org; email@example.com; firstname.lastname@example.org;
> Subject: Proposal for another approach for Loop transformation with conditional in Loops.
> Date: Sun, 15 Mar 2015 04:40:54 +0000
> 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.
> For ( x1= lb1; x1<= ub1; x1++)
> For(xn= lbn; xn <= ubn; xn++)
> V = cond_expr;
> If ( V)
> Code_FOR _THEN;
> /* Loop for cond_expr == true */
> For( x1 = ................................) For(xn =
> ............................) CODE_FOR_THEN; End End
> /* Loop for cond_expr == false */
> For ( x1 = ......................)
> For( xn = .......................)
> /* Loop for cond_expr == unknown *//
> For ( x1 = ...........................) For( xn =
> V = cond_expr;
> If( v)
> Fig ( b).
> Thoughts Please ?
> Thanks & Regards
>>How different this is from the loop-unswitch pass already in gcc (tree-ssa-loop-unswitch.c)?
Aditya: The loop unswitching moves the loop inside the IF-THEN and IF-ELSE with different versions of the Loop. The iteration space
remains same for the Loop unswitching. In the proposal given above the iteration spaces with different version of the Loop will be different
based on the cond_expr for the iteration space is true or false. Based on partitioned iteration space the transformed loops are generated
with different iterations space for the transformed loops based on the condition is true or false.
Another difference in the Loop unswitching the conditional expression for IF-THEN-ELSE is present with the loop unswitching, whereas
In the above optimizations the conditional expressions is removed for the cond_expr condition true or false. The different versions of the
Loop with different iteration spaces execute either the statements for then-block or statement for the ELSE block. For unknown cases for
The iterations spaces the Loops will be with different iterations space. This results in much more optimized code without having the
Conditional hot branches inside the loops and the performance bottleneck with respect to branch mispredictions with respect to
conditional branches Inside the loops will be removed or reduced to negligible amount.
As you mentioned it should be for the Hot Loops.
Thanks & Regards