Re: Compile-time improvement for if conversion.

[Yuri Rumyantsev <ysrumyan@gmail.com>]

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?

2016-10-10 15:00 GMT+03:00 Richard Biener <richard.guenther@gmail.com>:
> On Mon, Oct 10, 2016 at 1:42 PM, Yuri Rumyantsev <ysrumyan@gmail.com> 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 <richard.guenther@gmail.com>:
>>> On Wed, Oct 5, 2016 at 3:22 PM, Yuri Rumyantsev <ysrumyan@gmail.com> 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  <ysrumyan@gmail.com>
>>>>
>>>> * 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.