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: [RFC] Design and Implementation for Path Splitting for Loop with Conditional IF-THEN-ELSE



-----Original Message-----
From: Jeff Law [mailto:law@redhat.com] 
Sent: Friday, July 10, 2015 4:04 AM
To: Ajit Kumar Agarwal; Richard Biener; gcc@gcc.gnu.org
Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Re: [RFC] Design and Implementation for Path Splitting for Loop with Conditional IF-THEN-ELSE

On 06/02/2015 10:43 PM, Ajit Kumar Agarwal wrote:
>
>
> -----Original Message-----
> From: Jeff Law [mailto:law@redhat.com]
> Sent: Tuesday, June 02, 2015 9:19 PM
> To: Ajit Kumar Agarwal; Richard Biener; gcc@gcc.gnu.org
> Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju 
> Mekala
> Subject: Re: [RFC] Design and Implementation for Path Splitting for 
> Loop with Conditional IF-THEN-ELSE
>
> On 06/02/2015 12:35 AM, Ajit Kumar Agarwal wrote:
>>>> I don't offhand know if any of the benchmarks you cite above are 
>>>> free-enough to derive a testcase from.  But one trick many of us 
>>>> use is to instrument the >>pass and compile some known free 
>>>> software (often gcc
>>>> itself) to find triggering code and use that to generate tests for the new transformation.
>>
>> I will add tests in the suite. I could see many existing tests in the suite also get triggered with this optimization.
>>> Thanks.  For cases in the existing testsuite where you need to change the expected output, it's useful to note why the expected output was changed.  >>Sometimes a test is compromised by a new optimization, sometimes the expected output is changed and is papering over a problem, etc so it's something >>we look at reasonably closely.
>
> Thanks. I will modify accordingly.
>
>>
>>>
>>> diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c index 9faa339..559ca96
>>> 100644
>>> --- a/gcc/cfghooks.c
>>> +++ b/gcc/cfghooks.c
>>> @@ -581,7 +581,7 @@ delete_basic_block (basic_block bb)
>>>
>>>           /* If we remove the header or the latch of a loop, mark the loop for
>>>     	 removal.  */
>>> -      if (loop->latch == bb
>>> +      if (loop && loop->latch == bb
>>>     	  || loop->header == bb)
>>>     	mark_loop_for_removal (loop);
>>>> So what caused you to add this additional test?  In general loop 
>>>> structures are supposed to always be available.  The change here 
>>>> implies that the loop structures were gone at some point.  That 
>>>> seems at first glance a mistake.
>>
>> I was using the gimple_duplicate_bb which will not add the duplicate 
>> basic block inside the current_loops. That's why the above Condition 
>> is required. I am using duplicate_block instead of gimple_duplicate_bb. With this change the above check with loop Is not required as it adds the duplicate basic block inside the loops.
>>> OK.  Good to hear it's not required anymore.
>
>
>>
>>>
>>> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index aed5254..b25e409
>>> 100644
>>> --- a/gcc/tree-cfg.c
>>> +++ b/gcc/tree-cfg.c
>>> @@ -1838,6 +1838,64 @@ replace_uses_by (tree name, tree val)
>>>         }
>>>     }
>>>
>>> +void
>>> +gimple_threaded_merge_blocks (basic_block a, basic_block b)
>> If we keep this function it will need a block comment.
>>
>>>> I say "if" for a couple reasons.  First we already have support 
>>>> routines that know how to merge blocks.  If you really need to 
>>>> merge blocks you should try to use them.
>>
>>>> Second, I'm not sure that you really need to worry about block 
>>>> merging in this pass.  Just create the duplicates, wire them into 
>>>> the CFG and let the existing block merging support handle this problem.
>>
>> The above routine is not merging but duplicates the join nodes into 
>> its predecessors. If I change the name of the above Function to the gimple_threaded_duplicating_join_node it should be fine.
>>> But you don't need to duplicate into the predecessors.  If you create the duplicates and wire them into the CFG properly the existing code in cfgcleanup >>should take care of this for you.
>
> Certainly I will do it.
>>
>>> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c 
>>> index 4303a18..2c7d36d 100644
>>> --- a/gcc/tree-ssa-threadedge.c
>>> +++ b/gcc/tree-ssa-threadedge.c
>>> @@ -1359,6 +1359,322 @@ thread_through_normal_block (edge e,
>>>       return 0;
>>>     }
>>>
>>> +static void
>>> +replace_threaded_uses (basic_block a,basic_block b)
>>>> If you keep this function, then it'll need a function comment.
>>
>>>> It looks like this is just doing const/copy propagation.  I think a 
>>>> better structure is to implement your optimization as a distinct 
>>>> pass, then rely on existing passes such as update_ssa, DOM, CCP to 
>>>> handle updating the SSA graph and propagation opportunities exposed 
>>>> by your transformation.
>>
>>
>>>> Similarly for the other replace_ functions.
>>
>> I think these replace_ functions are required as existing Dom, CCP 
>> and propagation opportunities doesn't transform these Propagation given below.
>>
>> <bb 29>:
>> xk_124 = MIN_EXPR <xy_123, xc_121>;
>> xc_126 = xc_121 - xk_6;
>> xm_127 = xm_122 - xk_6;
>> xy_128 = xy_123 - xk_6;
>> *EritePtr_14 = xc_126;
>> MEM[(Byte *)EritePtr_14 + 1B] = xm_127; MEM[(Byte *)EritePtr_14 + 2B] 
>> = xy_128;
>> EritePtr_135 = &MEM[(void *)EritePtr_14 + 4B]; MEM[(Byte 
>> *)EritePtr_14 + 3B] = xk_6;
>> i_137 = i_4 + 1;
>> goto <bb 31>;
>>
>> <bb 30>:
>> xk_125 = MIN_EXPR <xy_123, xm_122>;
>> xc_165 = xc_121 - xk_6;
>> xm_166 = xm_122 - xk_6;
>> xy_167 = xy_123 - xk_6;
>> *EritePtr_14 = xc_126;
>> MEM[(Byte *)EritePtr_14 + 1B] = xm_127; MEM[(Byte *)EritePtr_14 + 2B] 
>> = xy_128;
>> EritePtr_171 = &MEM[(void *)EritePtr_14 + 4B]; MEM[(Byte 
>> *)EritePtr_14 + 3B] = xk_6;
>> i_173 = i_4 + 1;
>>
>> <bb 29> and <bb 30 > are the predecessors of the join node. After the 
>> duplication of join node and the duplicating the Join node into the predecessors < bb 29> and <bb 30>, the above is the gimple representations.
>> }
>>
>> But the < bb 30 > should be the following after the transformation.
>>
>> <bb 30>:
>> xk_125 = MIN_EXPR <xy_123, xm_122>;
>> xc_165 = xc_121 - xk_125;
>> xm_166 = xm_122 - xk_125;
>> xy_167 = xy_123 - xk_125;
>> *EritePtr_14 = xc_165;
>> MEM[(Byte *)EritePtr_14 + 1B] = xm_166; MEM[(Byte *)EritePtr_14 + 2B] 
>> = xy_167;
>> EritePtr_171 = &MEM[(void *)EritePtr_14 + 4B]; MEM[(Byte 
>> *)EritePtr_14 + 3B] = xk_125;
>> i_173 = i_4 + 1;
>>
>> The phi-only cprop will  replace the x_6 with xk_125 but the other 
>> replacements like xk_126, xk_127, xk_128 with Xk_165, xk_166, xk_167 
>> will not be done by the existing routine like phi-only-cprop as this not only copy propagation because the duplicate block defines New results but the copy is still old with the join node.
>>
>> The replace function does the above transformation and I think it is required.
>>> Can you send me the testcase this came from so that I can compile 
>>> and examine the dumps myself and possibly poke at things with the debugger?
>    >>I don't have enough context to know what's missing.
>
>>> If indeed there's a form of propagation missing, we should enhance 
>>> the propagation routines to handle the missing cases rather than 
>>> write new ones inside a pass.
>
> Please find the testcase given below.
>>Thanks.  But I don't offhand see how that testcase matches up with the code you provided.  If I use your patch from May on x86_64 compiling with -O2, I >>have something like 9 basic blocks where your gimple hunks above show ~30.

Thanks. The gimple above with ~30 is with respect to the application compiled with the changes. The testcase I have sent is the
Subset of the application with lesser basic blocks. Sorry for the inconvenience caused.

>>I've having to read between the lines a lot here, but I think the missing propagations are really an artifact of not calling the SSA updater and instead doing a >>by-hand update inside replace_threaded_uses_block.

>>When you duplicate blocks, you duplicate side effects.  ie, you will have one SSA_NAME that is set multiple times.  Thankfully the block duplication code >>does the bookkeeping necessary so that if you tell the pass manager that you need an incremental ssa update, the right things will "just happen".

Yes I agree.

>>So again, I like what you're trying to do, but I think that implementing SSA updates, const/copy propagation, block merging, etc within your code is the wrong >>thing to do.

>>Instead make your code an independent pass -- which would include duplicating blocks and wiring up the new edges in the CFG and possibly deleting some >>edges in the CFG. Make sure the new pass returns TODO_cleanup_cfg and TODO_update_ssa which should handle the block merging and an incremental >>update of the SSA graph.

Thanks. In the updated patch I have sent a week back,  have made the path splitting as an independent pass and made the changes as given
above.

>>I believe you'll want a phi-only cprop pass run after your path splitting which will take care of the const/copy propagation exposed by path splitting.

In the updated patch, I have placed the path splitting optimization pass  well before the cprop.
 
>>I'll try to look at the updated patch shortly.

Thanks! I am looking forward to it.

Thanks & Regards
Ajit
Jeff



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