Patchwork Fix RTL fwprop compile-time for PR56113

On Wed, Jan 30, 2013 at 12:01 AM, Steven Bosscher wrote:
> To prevent that mistake in the future, I've add an assert in dominance.c.

Hmm, that worked with my release-checking compiler of course, but
fails in at least tree-ssa-dom.c (same as for fwprop.c,
loop_optimizer_init destroys fast queries) and tree-ssa-loop-im.c (not
sure yet why).

NB, the fwprop.c change is independent and should go in. The domwalk.c
thing is something to maybe postpone to gcc 4.9.

Testing this patch now:

On Wed, 30 Jan 2013, Steven Bosscher wrote:

> On Wed, Jan 30, 2013 at 12:01 AM, Steven Bosscher wrote:
> > To prevent that mistake in the future, I've add an assert in dominance.c.
> 
> Hmm, that worked with my release-checking compiler of course, but
> fails in at least tree-ssa-dom.c (same as for fwprop.c,
> loop_optimizer_init destroys fast queries) and tree-ssa-loop-im.c (not
> sure yet why).
> 
> NB, the fwprop.c change is independent and should go in. The domwalk.c
> thing is something to maybe postpone to gcc 4.9.

The fwprop.c change is ok - fwprop.c doesn't seem to care about
identified latches or preheaders.

Now, I wonder what part of loop_optimizer_init wrecks dominance
info - I _suppose_ it's disambiguate_loops_with_multiple_latches (),
but that only ends up calling make_forwarder_block which looks like
it has code to fix dominators via iterate_fix_dominators ().

Hmm, it seems to be

make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
                      void (*new_bb_cbk) (basic_block))
{
...
  fallthru = split_block_after_labels (bb);

that sets DOM_NO_FAST_QUERY via add_to_dominance_info () via
create_basic_block.  Then split_block () does

482       if (dom_info_available_p (CDI_DOMINATORS))
483         {
484           redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
485           set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
486         }

but that doesn't set dominance info to DOM_OK again.  The
iterate_fix_dominators doesn't do that either.

IMHO at least split_block () should be able to preserve fast queries?

Thanks,
Richard.

> Testing this patch now:
> 
> Index: domwalk.c
> ===================================================================
> --- domwalk.c   (revision 195559)
> +++ domwalk.c   (working copy)
> @@ -147,8 +147,17 @@ walk_dominator_tree (struct dom_walk_dat
>    bitmap_clear (visited);
>    bitmap_set_bit (visited, ENTRY_BLOCK_PTR->index);
> 
> +  /* Make sure dominance information is available, and compute fast queries
> +     if necessary.  */
> +  gcc_assert (dom_info_state (walk_data->dom_direction) >= DOM_NO_FAST_QUERY);
> +  calculate_dominance_info (walk_data->dom_direction);
> +
>    while (true)
>      {
> +      /* Thou shall not modify the dominator tree while walking it
> +         (nor present it without fast queries available).  */
> +      gcc_assert (dom_info_state (walk_data->dom_direction) == DOM_OK);
> +
>        /* Don't worry about unreachable blocks.  */
>        if (EDGE_COUNT (bb->preds) > 0
>           || bb == ENTRY_BLOCK_PTR
> 
>

Hi,

On Wed, 30 Jan 2013, Richard Biener wrote:

> 483         {
> 484           redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
> 485           set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
> 486         }
> 
> but that doesn't set dominance info to DOM_OK again.  The
> iterate_fix_dominators doesn't do that either.
> 
> IMHO at least split_block () should be able to preserve fast queries?

I don't see how.  Fast queries rely on DFS in and out numbers of the 
dominance tree being correct.  If you insert a node in a tree the 
DFS numbers of all nodes after it need to change, i.e. updating fast 
queries for a single-block change is O(n_basic_blocks).


Ciao,
Michael.