Re: Fix tree-ssa-dce Ada LTO bootstrap ice

[Richard Biener <richard dot guenther at gmail dot com>]

On Sun, Nov 22, 2015 at 7:49 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> this patch fixes tree-ssa-dce ICE seen during Ada bootstrap.  It is updated
> version of https://gcc.gnu.org/ml/gcc-patches/2015-05/msg02876.html for
> current mainline
>
> Bootstrapped/regtested x86_64-linux, OK?

Ok.

Thanks,
Richard.

>         PR middle-end/65337
>         * tree-ssa-dce.c (bb_postorder): New static var.
>         (forward_edge_to_pdom): Remove.
>         (remove_dead_stmt): Instead of redirecting edges only keep an edge
>         on a path to nearest live BB.
>         (eliminate_unnecessary_stmts): Free bb_postorder.
>         * cfganal.c (dfs_find_deadend): Add START_POINTES.
>         * cfganal.h (inverted_post_order_compute): Update prototype.
> Index: tree-ssa-dce.c
> ===================================================================
> --- tree-ssa-dce.c      (revision 230718)
> +++ tree-ssa-dce.c      (working copy)
> @@ -112,6 +112,9 @@ static sbitmap visited_control_parents;
>     to be recomputed.  */
>  static bool cfg_altered;
>
> +/* When non-NULL holds map from basic block index into the postorder.  */
> +static int *bb_postorder;
> +
>
>  /* If STMT is not already marked necessary, mark it, and add it to the
>     worklist if ADD_TO_WORKLIST is true.  */
> @@ -997,65 +1000,6 @@ remove_dead_phis (basic_block bb)
>    return something_changed;
>  }
>
> -/* Forward edge E to respective POST_DOM_BB and update PHIs.  */
> -
> -static edge
> -forward_edge_to_pdom (edge e, basic_block post_dom_bb)
> -{
> -  gphi_iterator gsi;
> -  edge e2 = NULL;
> -  edge_iterator ei;
> -
> -  if (dump_file && (dump_flags & TDF_DETAILS))
> -    fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
> -            e->dest->index, post_dom_bb->index);
> -
> -  e2 = redirect_edge_and_branch (e, post_dom_bb);
> -  cfg_altered = true;
> -
> -  /* If edge was already around, no updating is necessary.  */
> -  if (e2 != e)
> -    return e2;
> -
> -  if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
> -    {
> -      /* We are sure that for every live PHI we are seeing control dependent BB.
> -         This means that we can pick any edge to duplicate PHI args from.  */
> -      FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
> -       if (e2 != e)
> -         break;
> -      for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
> -       {
> -         gphi *phi = gsi.phi ();
> -         tree op;
> -         source_location locus;
> -
> -         /* PHIs for virtuals have no control dependency relation on them.
> -            We are lost here and must force renaming of the symbol.  */
> -         if (virtual_operand_p (gimple_phi_result (phi)))
> -           {
> -             mark_virtual_phi_result_for_renaming (phi);
> -             remove_phi_node (&gsi, true);
> -             continue;
> -           }
> -
> -         /* Dead PHI do not imply control dependency.  */
> -          if (!gimple_plf (phi, STMT_NECESSARY))
> -           {
> -             gsi_next (&gsi);
> -             continue;
> -           }
> -
> -         op = gimple_phi_arg_def (phi, e2->dest_idx);
> -         locus = gimple_phi_arg_location (phi, e2->dest_idx);
> -         add_phi_arg (phi, op, e, locus);
> -         /* The resulting PHI if not dead can only be degenerate.  */
> -         gcc_assert (degenerate_phi_p (phi));
> -         gsi_next (&gsi);
> -       }
> -    }
> -  return e;
> -}
>
>  /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
>     containing I so that we don't have to look it up.  */
> @@ -1075,38 +1019,48 @@ remove_dead_stmt (gimple_stmt_iterator *
>    stats.removed++;
>
>    /* If we have determined that a conditional branch statement contributes
> -     nothing to the program, then we not only remove it, but we also change
> -     the flow graph so that the current block will simply fall-thru to its
> -     immediate post-dominator.  The blocks we are circumventing will be
> -     removed by cleanup_tree_cfg if this change in the flow graph makes them
> -     unreachable.  */
> +     nothing to the program, then we not only remove it, but we need to update
> +     the CFG.  We can chose any of edges out of BB as long as we are sure to not
> +     close infinite loops.  This is done by always choosing the edge closer to
> +     exit in inverted_post_order_compute order.  */
>    if (is_ctrl_stmt (stmt))
>      {
> -      basic_block post_dom_bb;
> -      edge e, e2;
>        edge_iterator ei;
> +      edge e = NULL, e2;
>
> -      post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
> -
> -      e = find_edge (bb, post_dom_bb);
> -
> -      /* If edge is already there, try to use it.  This avoids need to update
> -         PHI nodes.  Also watch for cases where post dominator does not exists
> -        or is exit block.  These can happen for infinite loops as we create
> -        fake edges in the dominator tree.  */
> -      if (e)
> -        ;
> -      else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
> -       e = EDGE_SUCC (bb, 0);
> -      else
> -        e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
> +      /* See if there is only one non-abnormal edge.  */
> +      if (single_succ_p (bb))
> +        e = single_succ_edge (bb);
> +      /* Otherwise chose one that is closer to bb with live statement in it.
> +         To be able to chose one, we compute inverted post order starting from
> +        all BBs with live statements.  */
> +      if (!e)
> +       {
> +         if (!bb_postorder)
> +           {
> +             int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
> +             int postorder_num
> +                = inverted_post_order_compute (postorder, &bb_contains_live_stmts);
> +             bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
> +             for (int i = 0; i < postorder_num; ++i)
> +                bb_postorder[postorder[i]] = i;
> +             free (postorder);
> +           }
> +          FOR_EACH_EDGE (e2, ei, bb->succs)
> +           if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
> +               || bb_postorder [e->dest->index] < bb_postorder [e2->dest->index])
> +             e = e2;
> +       }
>        gcc_assert (e);
>        e->probability = REG_BR_PROB_BASE;
>        e->count = bb->count;
>
>        /* The edge is no longer associated with a conditional, so it does
> -        not have TRUE/FALSE flags.  */
> -      e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
> +        not have TRUE/FALSE flags.
> +        We are also safe to drop EH/ABNORMAL flags and turn them into
> +        normal control flow, because we know that all the destinations (including
> +        those odd edges) are equivalent for program execution.  */
> +      e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL);
>
>        /* The lone outgoing edge from BB will be a fallthru edge.  */
>        e->flags |= EDGE_FALLTHRU;
> @@ -1516,6 +1470,10 @@ eliminate_unnecessary_stmts (void)
>        something_changed |= remove_dead_phis (bb);
>      }
>
> +  if (bb_postorder)
> +    free (bb_postorder);
> +  bb_postorder = NULL;
> +
>    return something_changed;
>  }
>
> Index: cfganal.c
> ===================================================================
> --- cfganal.c   (revision 230718)
> +++ cfganal.c   (working copy)
> @@ -759,6 +759,9 @@ dfs_find_deadend (basic_block bb)
>     (from successors to predecessors).
>     This ordering can be used for forward dataflow problems among others.
>
> +   Optionally if START_POINTS is specified, start from exit block and all
> +   basic blocks in START_POINTS.  This is used by CD-DCE.
> +
>     This function assumes that all blocks in the CFG are reachable
>     from the ENTRY (but not necessarily from EXIT).
>
> @@ -776,7 +779,8 @@ dfs_find_deadend (basic_block bb)
>     and do another inverted traversal from that block.  */
>
>  int
> -inverted_post_order_compute (int *post_order)
> +inverted_post_order_compute (int *post_order,
> +                            sbitmap *start_points)
>  {
>    basic_block bb;
>    edge_iterator *stack;
> @@ -797,6 +801,22 @@ inverted_post_order_compute (int *post_o
>    /* None of the nodes in the CFG have been visited yet.  */
>    bitmap_clear (visited);
>
> +  if (start_points)
> +    {
> +      FOR_ALL_BB_FN (bb, cfun)
> +        if (bitmap_bit_p (*start_points, bb->index)
> +           && EDGE_COUNT (bb->preds) > 0)
> +         {
> +            stack[sp++] = ei_start (bb->preds);
> +            bitmap_set_bit (visited, bb->index);
> +         }
> +      if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
> +       {
> +          stack[sp++] = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
> +          bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
> +       }
> +    }
> +  else
>    /* Put all blocks that have no successor into the initial work list.  */
>    FOR_ALL_BB_FN (bb, cfun)
>      if (EDGE_COUNT (bb->succs) == 0)
> Index: cfganal.h
> ===================================================================
> --- cfganal.h   (revision 230718)
> +++ cfganal.h   (working copy)
> @@ -62,7 +62,7 @@ extern void add_noreturn_fake_exit_edges
>  extern void connect_infinite_loops_to_exit (void);
>  extern int post_order_compute (int *, bool, bool);
>  extern basic_block dfs_find_deadend (basic_block);
> -extern int inverted_post_order_compute (int *);
> +extern int inverted_post_order_compute (int *, sbitmap *start_points = 0);
>  extern int pre_and_rev_post_order_compute_fn (struct function *,
>                                               int *, int *, bool);
>  extern int pre_and_rev_post_order_compute (int *, int *, bool);