RE: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation

[Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com>]

Hello Jeff:

Did you get a chance to look at the below response. Please let me know your opinion on the below.

Thanks & Regards
Ajit

-----Original Message-----
From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-owner@gcc.gnu.org] On Behalf Of Ajit Kumar Agarwal
Sent: Saturday, September 12, 2015 4:09 PM
To: Jeff Law; Richard Biener
Cc: GCC Patches; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: RE: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation



-----Original Message-----
From: Jeff Law [mailto:law@redhat.com]
Sent: Thursday, September 10, 2015 3:10 AM
To: Ajit Kumar Agarwal; Richard Biener
Cc: GCC Patches; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Re: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation

On 08/26/2015 11:29 PM, Ajit Kumar Agarwal wrote:
>
> Thanks. The following testcase testsuite/gcc.dg/tree-ssa/ifc-5.c
>
> void dct_unquantize_h263_inter_c (short *block, int n, int qscale, int
> nCoeffs) { int i, level, qmul, qadd;
>
> qadd = (qscale - 1) | 1; qmul = qscale << 1;
>
> for (i = 0; i <= nCoeffs; i++) { level = block[i]; if (level < 0) 
> level = level * qmul - qadd; else level = level * qmul + qadd; 
> block[i] = level; } }
>
> The above Loop is a candidate of path splitting as the IF block merges 
> at the latch of the Loop and the path splitting duplicates The latch 
> of the loop which is the statement block[i] = level into the 
> predecessors THEN and ELSE block.
>
> Due to above path splitting,  the IF conversion is disabled and the 
> above IF-THEN-ELSE is not IF-converted and the test case fails.
>>So I think the question then becomes which of the two styles generally results in better code?  The path-split version or the older if-converted version.

>>If the latter, then this may suggest that we've got the path splitting code at the wrong stage in the optimizer pipeline or that we need better heuristics for >>when to avoid applying path splitting.

The code generated by the Path Splitting is useful when it exposes the DCE, PRE,CCP candidates. Whereas the IF-conversion is useful When the if-conversion exposes the vectorization candidates. If the  if-conversion doesn't exposes the vectorization and the path splitting doesn't Exposes the DCE, PRE redundancy candidates, it's hard to predict. If the if-conversion does not exposes the vectorization and in the similar case Path splitting exposes the DCE , PRE  and CCP redundancy candidates then path splitting is useful. Also the path splitting increases the granularity of the THEN and ELSE path makes better register allocation and code scheduling.

The suggestion for keeping the path splitting later in the pipeline after the if-conversion and the vectorization is useful as it doesn't break the Existing Deja GNU tests. Also useful to keep the path splitting later in the pipeline after the if-conversion and vectorization is that path splitting Can always duplicate the merge node into its predecessor after the if-conversion and vectorization pass, if the if-conversion and vectorization Is not applicable to the Loops. But this suppresses the CCP, PRE candidates which are earlier in the optimization pipeline.


>
> There were following review comments from the above patch.
>
> +/* This function performs the feasibility tests for path splitting
>> +   to perform. Return false if the feasibility for path splitting
>> +   is not done and returns true if the feasibility for path
>> splitting +   is done. Following feasibility tests are performed.
>> + +   1. Return false if the join block has rhs casting for assign
>> +      gimple statements.
>
> Comments from Jeff:
>
>>> These seem totally arbitrary.  What's the reason behind each of 
>>> these restrictions?  None should be a correctness requirement 
>>> AFAICT.
>
> In the above patch I have made a check given in point 1. in the loop 
> latch and the Path splitting is disabled and the IF-conversion happens 
> and the test case passes.
>>That sounds more like a work-around/hack.  There's nothing inherent with a type conversion that should disable path splitting.

I have sent the patch with this change and I will remove the above check from the patch.

>>What happens if we delay path splitting to a point after if-conversion is complete?

This is better suggestion as explained above, but gains achieved through path splitting by keeping earlier in the pipeline before if-conversion , tree-vectorization, tree-vrp is suppressed if the following optimization after path splitting is not applicable for the above loops.

I have made the above changes and the existing set up doesn't break but the gains achieved in the benchmarks like rgbcmy_lite(EEMBC) Benchmarks is suppressed. The path splitting for the above EEMBC benchmarks give gains of 9% and for such loops if-conversion and Vectorization is not applicable  exposing gain with path splitting optimizations.

>>Alternately, could if-conversion export a routine which indicates if a particular sub-graph is likely to be if-convertable?  The path splitting pass could then use >>that routine to help determine if the path ought to be split or if it should instead rely on if-conversion.

Exporting the above routine from IF-conversion is not useful as the heuristics used in IF-conversion populates the Data Dependence through Scalar evolution which is trigger much later in the optimization pipeline. Populating such info in the earlier stage of the optimizations will not work as the Data Dependence through scalar evolution is trigger much later in the optimization  pipeline. Structure of basic block hierarchy required for if-conversion Looks similar to path splitting and exporting such function disables the path splitting for the cases where if-conversion is not applicable as there Are more data dependency check that distinguishes the if-conversion and path splitting.

Considering all the above, Keeping path splitting after if-conversion and vectorization looks better suggestion though this suppresses gains achieved Given above because of having path splitting after  tree-vrp, PRE, CCP. There is a dce path after the tree-vrp, if-conversion and tree-vectorize So the path splitting exposing DCE will not be affected.

Please suggest.

Thanks & Regards
Ajit

Jeff