This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Fix Ada bootstrap with LTO


Hi,
this patch fixes the cddce ICE reproducing during Ada bootstrap. The problem is
forward_edge_to_pdom which does not know how to update PHIs. Due to presence
of abnormal edges there is not unique predecestor the code looks for.

I decided to simply remove the code and go for alternative solution. When CDDCE
removes a conditional, it knows that the condition does not decide about any
live statement.  We can just keep one of outgoing edges but we need to be sure
to not close empty loops in the regions consisting only of basic blocks containing
no live statements in them.

I simply calculate distance from next live BB by using inverted_post_order_compute
and chose the successors that is on the path to live code. This leaves all the
redirection up to the following cfgcleanup.

Bootstrapped/regtested ppc64-linux. Without Ada because it does not build currently
for unrelated reasons, but I did LTObootstrap far enough to be sure that we can
build gnat binary now.

Honza

	PR middle-end/65337
	* cfganal.c (inverted_post_order_compute): Add option to specify starting
	points other than EXIT_BLOCK.
	* cfganal.h (inverted_post_order_compute): Update prototype.
	(bb_postoder): New variable.
	(forward_edge_to_pdom): Remove.
	(remove_dead_stmt): Rewrite removal of dead control flow.
	(eliminate_unnecessary_stmts): Free bb_postorder.
Index: cfganal.c
===================================================================
--- cfganal.c	(revision 223892)
+++ 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;
@@ -794,6 +798,18 @@ 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))
+	  {
+            stack[sp++] = ei_start (bb->preds);
+            bitmap_set_bit (visited, bb->index);
+	  }
+      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 223892)
+++ cfganal.h	(working copy)
@@ -61,7 +61,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);
Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c	(revision 223892)
+++ tree-ssa-dce.c	(working copy)
@@ -147,6 +147,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.  */
@@ -1030,65 +1034,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.  */
@@ -1108,38 +1053,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;
@@ -1548,6 +1503,10 @@ eliminate_unnecessary_stmts (void)
       something_changed |= remove_dead_phis (bb);
     }
 
+  if (bb_postorder)
+    free (bb_postorder);
+  bb_postorder = NULL;
+
   return something_changed;
 }
 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]