CbC/CbC_gcc: gcc/cfgcleanup.c comparison

comparison gcc/cfgcleanup.c @ 67:f6334be47118

update gcc from gcc-4.6-20100522 to gcc-4.6-20110318

author	nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Tue, 22 Mar 2011 17:18:12 +0900
parents	b7f97abdc517
children	04ced10e8804

comparison

equal deleted inserted replaced

-:65488c3d617d
+:f6334be47118
 #include "timevar.h"
 #include "output.h"
 #include "insn-config.h"
 #include "flags.h"
 #include "recog.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
 #include "cselib.h"
 #include "params.h"
 #include "tm_p.h"
 #include "target.h"
 #include "cfglayout.h"
 /* Set to true when we are running first pass of try_optimize_cfg loop.  */
 static bool first_pass;
 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg.  */
 static bool crossjumps_occured;
+/* Set to true if we couldn't run an optimization due to stale liveness
+information; we should run df_analyze to enable more opportunities.  */
+static bool block_was_dirty;
 static bool try_crossjump_to_edge (int, edge, edge);
 static bool try_crossjump_bb (int, basic_block);
 static bool outgoing_edges_match (int, basic_block, basic_block);
 static bool old_insns_match_p (int, rtx, rtx);
 {
 basic_block target, first;
 int counter, goto_locus;
 bool threaded = false;
 int nthreaded_edges = 0;
-bool may_thread = first_pass | df_get_bb_dirty (b);
+bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
 /* Skip complex edges because we don't know how to update them.
 	 Still handle fallthru edges, as we can succeed to forward fallthru
 	 edge to the same place as the branch edge of conditional branch
 while (counter < n_basic_blocks)
 	{
 	  basic_block new_target = NULL;
 	  bool new_target_threaded = false;
-	  may_thread |= df_get_bb_dirty (target);
+	  may_thread |= (target->flags & BB_MODIFIED) != 0;
 	  if (FORWARDER_BLOCK_P (target)
 	      && !(single_succ_edge (target)->flags & EDGE_CROSSING)
 	      && single_succ (target) != EXIT_BLOCK_PTR)
 	    {
 		counter = n_basic_blocks;
 	      else if (!optimize)
 		{
 		  /* When not optimizing, ensure that edges or forwarder
 		     blocks with different locus are not optimized out.  */
-		  int locus = single_succ_edge (target)->goto_locus;
+		  int new_locus = single_succ_edge (target)->goto_locus;
+		  int locus = goto_locus;
-		  if (locus && goto_locus && !locator_eq (locus, goto_locus))
-		    counter = n_basic_blocks;
+		  if (new_locus && locus && !locator_eq (new_locus, locus))
-		  else if (locus)
+		    new_target = NULL;
-		    goto_locus = locus;
+		  else
-		  if (INSN_P (BB_END (target)))
 		    {
-		      locus = INSN_LOCATOR (BB_END (target));
+		      rtx last;
-		      if (locus && goto_locus
+		      if (new_locus)
-			  && !locator_eq (locus, goto_locus))
+			locus = new_locus;
-			counter = n_basic_blocks;
-		      else if (locus)
+		      last = BB_END (target);
-			goto_locus = locus;
+		      if (DEBUG_INSN_P (last))
+			last = prev_nondebug_insn (last);
+		      new_locus = last && INSN_P (last)
+				  ? INSN_LOCATOR (last) : 0;
+		      if (new_locus && locus && !locator_eq (new_locus, locus))
+			new_target = NULL;
+		      else
+			{
+			  if (new_locus)
+			    locus = new_locus;
+			  goto_locus = locus;
+			}
 		    }
 		}
 	    }
 	  /* Allow to thread only over one edge at time to simplify updating
 else if (mode & CLEANUP_EXPENSIVE)
 {
 edge tmp_edge, b_fallthru_edge;
 bool c_has_outgoing_fallthru;
 bool b_has_incoming_fallthru;
-edge_iterator ei;
 /* Avoid overactive code motion, as the forwarder blocks should be
 	 eliminated by edge redirection instead.  One exception might have
 	 been if B is a forwarder block and C has no fallthru edge, but
 	 that should be cleaned up by bb-reorder instead.  */
 /* We must make sure to not munge nesting of lexical blocks,
 	 and loop notes.  This is done by squeezing out all the notes
 	 and leaving them there to lie.  Not ideal, but functional.  */
-FOR_EACH_EDGE (tmp_edge, ei, c->succs)
+tmp_edge = find_fallthru_edge (c->succs);
-	if (tmp_edge->flags & EDGE_FALLTHRU)
-	  break;
 c_has_outgoing_fallthru = (tmp_edge != NULL);
-FOR_EACH_EDGE (tmp_edge, ei, b->preds)
+tmp_edge = find_fallthru_edge (b->preds);
-	if (tmp_edge->flags & EDGE_FALLTHRU)
-	  break;
 b_has_incoming_fallthru = (tmp_edge != NULL);
 b_fallthru_edge = tmp_edge;
 next = b->prev_bb;
 if (next == c)
 	next = next->prev_bb;
 i2 = BB_HEAD (bb2);
 last1 = beforelast1 = last2 = beforelast2 = NULL_RTX;
 while (true)
 {
+/* Ignore notes, except NOTE_INSN_EPILOGUE_BEG.  */
-/* Ignore notes.  */
 while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
-	i1 = NEXT_INSN (i1);
+	{
+	  if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
+	    break;
+	  i1 = NEXT_INSN (i1);
+	}
 while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
-	i2 = NEXT_INSN (i2);
+	{
+	  if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
+	    break;
+	  i2 = NEXT_INSN (i2);
+	}
+if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
+	  || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
+	break;
 if (NOTE_P (i1) || NOTE_P (i2)
 	  || JUMP_P (i1) || JUMP_P (i2))
 	break;
 {
 edge e, e2, fallthru;
 bool changed;
 unsigned max, ix, ix2;
 basic_block ev, ev2;
-edge_iterator ei;
 /* Nothing to do if there is not at least two incoming edges.  */
 if (EDGE_COUNT (bb->preds) < 2)
 return false;
 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
 if (EDGE_COUNT (bb->preds) > max)
 return false;
-FOR_EACH_EDGE (e, ei, bb->preds)
+fallthru = find_fallthru_edge (bb->preds);
-{
-if (e->flags & EDGE_FALLTHRU)
-	{
-	  fallthru = e;
-	  break;
-	}
-}
 changed = false;
 for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
 {
 e = EDGE_PRED (ev, ix);
 	  if (e == fallthru)
 	    continue;
 	  /* If nothing changed since the last attempt, there is nothing
 	     we can do.  */
 	  if (!first_pass
-	      && (!(df_get_bb_dirty (e->src))
+	      && !((e->src->flags & BB_MODIFIED)
-		  && !(df_get_bb_dirty (fallthru->src))))
+		   || (fallthru->src->flags & BB_MODIFIED)))
 	    continue;
 	  if (try_crossjump_to_edge (mode, e, fallthru))
 	    {
 	      changed = true;
 	    continue;
 	  /* If nothing changed since the last attempt, there is nothing
 	     we can do.  */
 	  if (!first_pass
-	      && (!(df_get_bb_dirty (e->src))
+	      && !((e->src->flags & BB_MODIFIED)
-		  && !(df_get_bb_dirty (e2->src))))
+		   || (e2->src->flags & BB_MODIFIED)))
 	    continue;
 	  if (try_crossjump_to_edge (mode, e, e2))
 	    {
 	      changed = true;
 crossjumps_occured = true;
 return changed;
 }
+/* Search the successors of BB for common insn sequences.  When found,
+share code between them by moving it across the basic block
+boundary.  Return true if any changes made.  */
+static bool
+try_head_merge_bb (basic_block bb)
+{
+basic_block final_dest_bb = NULL;
+int max_match = INT_MAX;
+edge e0;
+rtx *headptr, *currptr, *nextptr;
+bool changed, moveall;
+unsigned ix;
+rtx e0_last_head, cond, move_before;
+unsigned nedges = EDGE_COUNT (bb->succs);
+rtx jump = BB_END (bb);
+regset live, live_union;
+/* Nothing to do if there is not at least two outgoing edges.  */
+if (nedges < 2)
+return false;
+/* Don't crossjump if this block ends in a computed jump,
+unless we are optimizing for size.  */
+if (optimize_bb_for_size_p (bb)
+&& bb != EXIT_BLOCK_PTR
+&& computed_jump_p (BB_END (bb)))
+return false;
+cond = get_condition (jump, &move_before, true, false);
+if (cond == NULL_RTX)
+move_before = jump;
+for (ix = 0; ix < nedges; ix++)
+if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR)
+return false;
+for (ix = 0; ix < nedges; ix++)
+{
+edge e = EDGE_SUCC (bb, ix);
+basic_block other_bb = e->dest;
+if (df_get_bb_dirty (other_bb))
+	{
+	  block_was_dirty = true;
+	  return false;
+	}
+if (e->flags & EDGE_ABNORMAL)
+	return false;
+/* Normally, all destination blocks must only be reachable from this
+	 block, i.e. they must have one incoming edge.
+	 There is one special case we can handle, that of multiple consecutive
+	 jumps where the first jumps to one of the targets of the second jump.
+	 This happens frequently in switch statements for default labels.
+	 The structure is as follows:
+	 FINAL_DEST_BB
+	 ....
+	 if (cond) jump A;
+	 fall through
+	 BB
+	 jump with targets A, B, C, D...
+	 A
+	 has two incoming edges, from FINAL_DEST_BB and BB
+	 In this case, we can try to move the insns through BB and into
+	 FINAL_DEST_BB.  */
+if (EDGE_COUNT (other_bb->preds) != 1)
+	{
+	  edge incoming_edge, incoming_bb_other_edge;
+	  edge_iterator ei;
+	  if (final_dest_bb != NULL
+	      || EDGE_COUNT (other_bb->preds) != 2)
+	    return false;
+	  /* We must be able to move the insns across the whole block.  */
+	  move_before = BB_HEAD (bb);
+	  while (!NONDEBUG_INSN_P (move_before))
+	    move_before = NEXT_INSN (move_before);
+	  if (EDGE_COUNT (bb->preds) != 1)
+	    return false;
+	  incoming_edge = EDGE_PRED (bb, 0);
+	  final_dest_bb = incoming_edge->src;
+	  if (EDGE_COUNT (final_dest_bb->succs) != 2)
+	    return false;
+	  FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
+	    if (incoming_bb_other_edge != incoming_edge)
+	      break;
+	  if (incoming_bb_other_edge->dest != other_bb)
+	    return false;
+	}
+}
+e0 = EDGE_SUCC (bb, 0);
+e0_last_head = NULL_RTX;
+changed = false;
+for (ix = 1; ix < nedges; ix++)
+{
+edge e = EDGE_SUCC (bb, ix);
+rtx e0_last, e_last;
+int nmatch;
+nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
+						 &e0_last, &e_last, 0);
+if (nmatch == 0)
+	return false;
+if (nmatch < max_match)
+	{
+	  max_match = nmatch;
+	  e0_last_head = e0_last;
+	}
+}
+/* If we matched an entire block, we probably have to avoid moving the
+last insn.  */
+if (max_match > 0
+&& e0_last_head == BB_END (e0->dest)
+&& (find_reg_note (e0_last_head, REG_EH_REGION, 0)
+	  || control_flow_insn_p (e0_last_head)))
+{
+max_match--;
+if (max_match == 0)
+	return false;
+do
+	e0_last_head = prev_real_insn (e0_last_head);
+while (DEBUG_INSN_P (e0_last_head));
+}
+if (max_match == 0)
+return false;
+/* We must find a union of the live registers at each of the end points.  */
+live = BITMAP_ALLOC (NULL);
+live_union = BITMAP_ALLOC (NULL);
+currptr = XNEWVEC (rtx, nedges);
+headptr = XNEWVEC (rtx, nedges);
+nextptr = XNEWVEC (rtx, nedges);
+for (ix = 0; ix < nedges; ix++)
+{
+int j;
+basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
+rtx head = BB_HEAD (merge_bb);
+while (!NONDEBUG_INSN_P (head))
+	head = NEXT_INSN (head);
+headptr[ix] = head;
+currptr[ix] = head;
+/* Compute the end point and live information  */
+for (j = 1; j < max_match; j++)
+	do
+	  head = NEXT_INSN (head);
+	while (!NONDEBUG_INSN_P (head));
+simulate_backwards_to_point (merge_bb, live, head);
+IOR_REG_SET (live_union, live);
+}
+/* If we're moving across two blocks, verify the validity of the
+first move, then adjust the target and let the loop below deal
+with the final move.  */
+if (final_dest_bb != NULL)
+{
+rtx move_upto;
+moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
+				       jump, e0->dest, live_union,
+				       NULL, &move_upto);
+if (!moveall)
+	{
+	  if (move_upto == NULL_RTX)
+	    goto out;
+	  while (e0_last_head != move_upto)
+	    {
+	      df_simulate_one_insn_backwards (e0->dest, e0_last_head,
+					      live_union);
+	      e0_last_head = PREV_INSN (e0_last_head);
+	    }
+	}
+if (e0_last_head == NULL_RTX)
+	goto out;
+jump = BB_END (final_dest_bb);
+cond = get_condition (jump, &move_before, true, false);
+if (cond == NULL_RTX)
+	move_before = jump;
+}
+do
+{
+rtx move_upto;
+moveall = can_move_insns_across (currptr[0], e0_last_head,
+				       move_before, jump, e0->dest, live_union,
+				       NULL, &move_upto);
+if (!moveall && move_upto == NULL_RTX)
+	{
+	  if (jump == move_before)
+	    break;
+	  /* Try again, using a different insertion point.  */
+	  move_before = jump;
+#ifdef HAVE_cc0
+	  /* Don't try moving before a cc0 user, as that may invalidate
+	     the cc0.  */
+	  if (reg_mentioned_p (cc0_rtx, jump))
+	    break;
+#endif
+	  continue;
+	}
+if (final_dest_bb && !moveall)
+	/* We haven't checked whether a partial move would be OK for the first
+	   move, so we have to fail this case.  */
+	break;
+changed = true;
+for (;;)
+	{
+	  if (currptr[0] == move_upto)
+	    break;
+	  for (ix = 0; ix < nedges; ix++)
+	    {
+	      rtx curr = currptr[ix];
+	      do
+		curr = NEXT_INSN (curr);
+	      while (!NONDEBUG_INSN_P (curr));
+	      currptr[ix] = curr;
+	    }
+	}
+/* If we can't currently move all of the identical insns, remember
+	 each insn after the range that we'll merge.  */
+if (!moveall)
+	for (ix = 0; ix < nedges; ix++)
+	  {
+	    rtx curr = currptr[ix];
+	    do
+	      curr = NEXT_INSN (curr);
+	    while (!NONDEBUG_INSN_P (curr));
+	    nextptr[ix] = curr;
+	  }
+reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
+df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
+if (final_dest_bb != NULL)
+	df_set_bb_dirty (final_dest_bb);
+df_set_bb_dirty (bb);
+for (ix = 1; ix < nedges; ix++)
+	{
+	  df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
+	  delete_insn_chain (headptr[ix], currptr[ix], false);
+	}
+if (!moveall)
+	{
+	  if (jump == move_before)
+	    break;
+	  /* For the unmerged insns, try a different insertion point.  */
+	  move_before = jump;
+#ifdef HAVE_cc0
+	  /* Don't try moving before a cc0 user, as that may invalidate
+	     the cc0.  */
+	  if (reg_mentioned_p (cc0_rtx, jump))
+	    break;
+#endif
+	  for (ix = 0; ix < nedges; ix++)
+	    currptr[ix] = headptr[ix] = nextptr[ix];
+	}
+}
+while (!moveall);
+out:
+free (currptr);
+free (headptr);
+free (nextptr);
+crossjumps_occured |= changed;
+return changed;
+}
 /* Return true if BB contains just bb note, or bb note followed
 by only DEBUG_INSNs.  */
 static bool
 trivially_empty_bb_p (basic_block bb)
 /* Attempt to merge blocks as made possible by edge removal.  If
 	 a block has only one successor, and the successor has only
 	 one predecessor, they may be combined.  */
 do
 	{
+	  block_was_dirty = false;
 	  changed = false;
 	  iterations++;
 	  if (dump_file)
 	    fprintf (dump_file,
 			      if ((e->flags & EDGE_FALLTHRU))
 				emit_barrier_after (BB_END (e->src));
 			}
 		    }
 		  delete_basic_block (b);
-		  if (!(mode & CLEANUP_CFGLAYOUT))
+		  changed = true;
-		    changed = true;
 		  /* Avoid trying to remove ENTRY_BLOCK_PTR.  */
 		  b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
 		  continue;
 		}
 		  changed = true;
 		  b = c;
 		  continue;
 		}
+	      /* Merge B with its single successor, if any.  */
 	      if (single_succ_p (b)
 		  && (s = single_succ_edge (b))
 		  && !(s->flags & EDGE_COMPLEX)
 		  && (c = s->dest) != EXIT_BLOCK_PTR
 		  && single_pred_p (c)
 	      /* Look for shared code between blocks.  */
 	      if ((mode & CLEANUP_CROSSJUMP)
 		  && try_crossjump_bb (mode, b))
 		changed_here = true;
+	      if ((mode & CLEANUP_CROSSJUMP)
+		  /* This can lengthen register lifetimes.  Do it only after
+		     reload.  */
+		  && reload_completed
+		  && try_head_merge_bb (b))
+		changed_here = true;
 	      /* Don't get confused by the index shift caused by
 		 deleting blocks.  */
 	      if (!changed_here)
 		b = b->next_bb;
 	      else
 	    }
 	  if ((mode & CLEANUP_CROSSJUMP)
 	      && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
 	    changed = true;
+	  if (block_was_dirty)
+	    {
+	      /* This should only be set by head-merging.  */
+	      gcc_assert (mode & CLEANUP_CROSSJUMP);
+	      df_analyze ();
+	    }
 #ifdef ENABLE_CHECKING
 	  if (changed)
 	    verify_flow_info ();
 #endif
 	     code, so delete_trivially_dead_insns or even doing nothing at all
 	     is good enough.  */
 	  if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
 	      && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
 	    break;
-	  else if ((mode & CLEANUP_CROSSJUMP)
+	  if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occured)
-		   && crossjumps_occured)
 	    run_fast_dce ();
 	}
 else
 	break;
 }

Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfgcleanup.c @ 67:f6334be47118