This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Compile-time improvement for if conversion.
On Tue, Oct 11, 2016 at 3:23 PM, Yuri Rumyantsev <ysrumyan@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.guenther@gmail.com>:
>> On Mon, Oct 10, 2016 at 4:17 PM, Yuri Rumyantsev <ysrumyan@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.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.