Richard, Here is updated patch . I avoided creation of new entry/exit blocks but instead add check to border cases - do not consider also blocks which are out of region.
Any comments will be appreciated.
2016-10-11 16:48 GMT+03:00 Richard Biener <richard.guent...@gmail.com>:
> On Tue, Oct 11, 2016 at 3:23 PM, Yuri Rumyantsev <ysrum...@gmail.com> wrote:
>> Richard,
>>
>> 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.
>
> + FOR_EACH_VEC_ELT (region, i, bb)
> + {
> + bb->dom[dir_index] = et_new_tree (bb);
> + }
> + /* Check that region is SESE region. */
> + entry = region[0];
> + if ( EDGE_COUNT (entry->succs) > 1)
> + {
> + /* Create new entry block with the only successor. */
> + basic_block succ = NULL;
> + bool found = false;
> + FOR_EACH_EDGE (e, ei, entry->succs)
> + if (in_region (region, e->dest))
> + {
> + gcc_assert (!found);
>
> is that check equal to e->dest->dom[dir_index] != NULL? I think we
> shouldn't need the callback.
>
> + new_entry = create_empty_bb (entry);
> + unchecked_make_edge (new_entry, succ, 0);
>
> I still think this is somewhat gross and we should try to avoid it
> somehow - at least it's well-hidden now ;)
>
> + /* Put it to region as entry node. */
> + region[0] = new_entry;
>
> so region[0] is overwritten now?
>
> As far as I understand calc_dfs_tree it should be possible to compute
> the region on-the-fly
> from calling calc_dfs_tree_nonrec on the entry/exit (also maybe
> avoiding some of the still
> "large" complexity of zeroing arrays in the constructor).
>
> And if we use that DFS walk directly we should be able to avoid
> creating those fake entry/exit
> blocks by using entry/exit edges instead... (somehow).
>
> Richard.
>
>
>
>> Thanks.
>>
>> 2016-10-11 13:33 GMT+03:00 Richard Biener <richard.guent...@gmail.com>:
>>> On Mon, Oct 10, 2016 at 4:17 PM, Yuri Rumyantsev <ysrum...@gmail.com> 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 <richard.guent...@gmail.com>:
>>>>> On Mon, Oct 10, 2016 at 1:42 PM, Yuri Rumyantsev <ysrum...@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.guent...@gmail.com>:
>>>>>>> On Wed, Oct 5, 2016 at 3:22 PM, Yuri Rumyantsev <ysrum...@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 <ysrum...@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.
patch.3
Description: Binary data
