Compile-time improvement for if conversion.

Yuri Rumyantsev
Tue Oct 11 13:23:00 GMT 2016


I implemented this by passing callback function in_region which
returns true if block belongs to region.
I am testing it now

I attach modified patch for your quick review.


2016-10-11 13:33 GMT+03:00 Richard Biener <>:
> On Mon, Oct 10, 2016 at 4:17 PM, Yuri Rumyantsev <> wrote:
>> Richard,
>> If "fake" exit or entry block is created in dominance how we can
>> determine what is its the only  predecessor or successor without using
>> a notion of loop?
> The caller passes in an entry and exit edge instead of a block or loop.
> Richard.
>> 2016-10-10 15:00 GMT+03:00 Richard Biener <>:
>>> On Mon, Oct 10, 2016 at 1:42 PM, Yuri Rumyantsev <> wrote:
>>>> Thanks Richard for your comments.
>>>> I'd like to answer on your last comment regarding use split_edge()
>>>> instead of creating fake post-header. I started with this splitting
>>>> but it requires to fix-up closed ssa form by creating additional phi
>>>> nodes, so I decided to use only cfg change without updating ssa form.
>>>> Other changes look reasonable and will fix them.
>>> Ah.  In this case can you investigate what it takes to make the entry/exit
>>> edges rather than BBs?  That is, introduce those "fakes" only internally
>>> in dominance.c?
>>>> 2016-10-10 12:52 GMT+03:00 Richard Biener <>:
>>>>> On Wed, Oct 5, 2016 at 3:22 PM, Yuri Rumyantsev <> wrote:
>>>>>> Hi All,
>>>>>> Here is implementation of Richard proposal:
>>>>>> < For general infrastructure it would be nice to expose a (post-)dominator
>>>>>> < compute for MESE (post-dominators) / SEME (dominators) regions.  I believe
>>>>>> < what makes if-conversion expensive is the post-dom compute which happens
>>>>>> < for each loop for the whole function.  It shouldn't be very difficult
>>>>>> < to write this,
>>>>>> < sharing as much as possible code with the current DOM code might need
>>>>>> < quite some refactoring though.
>>>>>> I implemented this proposal by adding calculation of dominance info
>>>>>> for SESE regions and incorporate this change to if conversion pass.
>>>>>> SESE region is built by adding loop pre-header and possibly fake
>>>>>> post-header blocks to loop body. Fake post-header is deleted after
>>>>>> predication completion.
>>>>>> Bootstrapping and regression testing did not show any new failures.
>>>>>> Is it OK for trunk?
>>>>> It's mostly reasonable but I have a few comments.  First, re-using
>>>>> bb->dom[] for the dominator info is somewhat fragile but indeed
>>>>> a requirement to make the patch reasonably small.  Please,
>>>>> in calculate_dominance_info_for_region, make sure that
>>>>> !dom_info_available_p (dir).
>>>>> You pass loop * everywhere but require ->aux to be set up as
>>>>> an array of BBs forming the region with special BBs at array ends.
>>>>> Please instead pass in a vec<basic_block> which avoids using ->aux
>>>>> and also allows other non-loop-based SESE regions to be used
>>>>> (I couldn't spot anything that relies on this being a loop).
>>>>> Adding a convenience wrapper for loop  * would be of course nice,
>>>>> to cover the special pre/post-header code in tree-if-conv.c.
>>>>> In theory a SESE region is fully specified by its entry end exit _edge_,
>>>>> so you might want to see if it's possible to use such a pair of edges
>>>>> to guard the dfs/idom walks to avoid the need to create fake blocks.
>>>>> Btw, instead of using create_empty_bb, unchecked_make_edge, etc.
>>>>> please use split_edge() of the entry/exit edges.
>>>>> Richard.
>>>>>> ChangeLog:
>>>>>> 2016-10-05  Yuri Rumyantsev  <>
>>>>>> * dominance.c : Include cfgloop.h for loop recognition.
>>>>>> (dom_info): Add new functions and add boolean argument to recognize
>>>>>> computation for loop region.
>>>>>> (dom_info::dom_info): New function.
>>>>>> (dom_info::calc_dfs_tree): Add boolean argument IN_REGION to not
>>>>>> handle unvisited blocks.
>>>>>> (dom_info::calc_idoms): Likewise.
>>>>>> (compute_dom_fast_query_in_region): New function.
>>>>>> (calculate_dominance_info): Invoke calc_dfs_tree and calc_idoms with
>>>>>> false argument.
>>>>>> (calculate_dominance_info_for_region): New function.
>>>>>> (free_dominance_info_for_region): Likewise.
>>>>>> (verify_dominators): Invoke calc_dfs_tree and calc_idoms with false
>>>>>> argument.
>>>>>> * dominance.h: Add prototype for introduced functions
>>>>>> calculate_dominance_info_for_region and
>>>>>> free_dominance_info_for_region.
>>>>>> tree-if-conv.c: Add to local variables ifc_sese_bbs & fake_postheader.
>>>>>> (build_sese_region): New function.
>>>>>> (if_convertible_loop_p_1): Invoke local version of post-dominators
>>>>>> calculation, free it after basic block predication and delete created
>>>>>> fake post-header block if any.
>>>>>> (tree_if_conversion): Delete call of free_dominance_info for
>>>>>> post-dominators, free ifc_sese_bbs which represents SESE region.
>>>>>> (pass_if_conversion::execute): Delete detection of infinite loops
>>>>>> and fake edges to exit block since post-dominator calculation is
>>>>>> performed per if-converted loop only.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.2
Type: application/octet-stream
Size: 14622 bytes
Desc: not available
URL: <>

More information about the Gcc-patches mailing list