Take 3: RFA: re-instate struct_equiv code

[Joern RENNECKE <joern dot rennecke at st dot com>]

Joern Rennecke wrote:

> Bernd Schmidt wrote:
>
> >  
> > I don't think "fancy" is the direction we should be going with this. 
> > I'd rather experiment with moving crossjumping out of the 
> > try_optimize_cfg loop, to a place where we know life information is 
> > up-to-date, and making sure we don't visit blocks more than once.
>
>
> As a said before, the cross-jumping can tolerate inaccurate life 
> information, as long it is not plain wrong.  I'll be working on a 
> patch update to do this.
I have attached the patch that I am currently testing.
2006-01-12  J"orn Rennecke <joern.rennecke@st.com>

	* cfgcleanup.c: Reinstate patches for PR 20070
	* struct-equiv.c (struct_equiv_regs_eq_p): New function.
	(struct_equiv_init): Only call update_life_info_in_dirty_blocks
	in order to initialize regsets if both blocks are dirty.
	Make do sanity check of registers bening equal for STRUCT_EQUIV_FINAL.
	Add new parameter check_regs_eq.  Changed all callers.
	* basic-block.h (struct_equiv_init): Update prototype.

	* basic-block.h (STRUCT_EQUIV_SUSPEND_UPDATE): Define.
	* struct-equiv.c (struct_equiv_regs_eq_p): Don't call
	update_life_info_in_dirty_blocks if STRUCT_EQUIV_SUSPEND_UPDATE
	is set in info->mode.
	(struct_equiv_init): Likewise.  Also, add sanity check of
	global_live_at_end in that case.
	* cfgcleanup.c (try_optimize_cfg): Don't create fake edges if
	we don't need them.
	Set STRUCT_EQUIV_SUSPEND_UPDATE in mode argument passed to
	try_crossjump_bb.
	(try_crossjump_to_edge): Set global_live_at_end of redirect_from
	from global_live_at_start of redirect_to.
	(outgoing_edges_match): Check number of edges before comparing
	patterns.

	* basic-block.h (maybe_killed_reg): Define.
	(struct control_flow_graph): Add new member x_maybe_killed_regs.
	(used_by_bb_end): Declare.
	* flow.c (allocate_bb_life_data): Allocate maybe_killed_regs.
	(used_by_bb_end): New function.
	* cfgrtl.c (try_redirect_by_replacing_jump): Update maybe_killed_regs.
	* cfgcleanup.c (try_optimize_cfg): For CLEANUP_POST_REGSTACK, add
	stack regs to maybe_killed_regs.
	* struct-equiv.c (struct_equiv_regs_eq_p): Use maybe_killed_regs
	to determine the difference of which registers to ignore.
	(struct_equiv_init): For STRUCT_EQUIV_SUSPEND_UPDATES, calculate
	common_live as intersection of global_live_at_end of both blocks.

Index: flow.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L flow.c	(revision 110439) -L flow.c	(working copy) .svn/text-base/flow.c.svn-base flow.c
--- flow.c	(revision 110439)
+++ flow.c	(working copy)
@@ -1563,6 +1563,7 @@ allocate_bb_life_data (void)
       bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
       bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
     }
+  maybe_killed_regs = ALLOC_REG_SET (&reg_obstack);
 
   regs_live_at_setjmp = ALLOC_REG_SET (&reg_obstack);
 }
@@ -2195,6 +2196,39 @@ propagate_block (basic_block bb, regset 
 
   return changed;
 }
+
+/* RESULT has to be an initialized regset.  If we have liveness information,
+   fill RESSULT in with the set of registers that are live before FIRST
+   (which must be inside BB), but not at the end of BB.  */
+regset
+used_by_bb_end (rtx first, basic_block bb, regset result)
+{
+  struct propagate_block_info *pbi;
+  rtx insn, prev;
+
+  if (!bb->il.rtl->global_live_at_end)
+    {
+      CLEAR_REG_SET (result);
+      return result;
+    }
+
+  COPY_REG_SET (result, bb->il.rtl->global_live_at_end);
+  pbi = init_propagate_block_info (bb, result, NULL, NULL, 0);
+
+  /* Scan the chain an insn at a time from end to beginning.  */
+
+  for (insn = BB_END (bb); ; insn = prev)
+    {
+      prev = propagate_one_insn (pbi, insn);
+
+      if (insn == first)
+	break;
+    }
+
+  free_propagate_block_info (pbi);
+  AND_COMPL_REG_SET (result, bb->il.rtl->global_live_at_end);
+  return result;
+}
 
 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
    (SET expressions whose destinations are registers dead after the insn).
Index: cfgcleanup.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgcleanup.c	(revision 110439) -L cfgcleanup.c	(working copy) .svn/text-base/cfgcleanup.c.svn-base cfgcleanup.c
--- cfgcleanup.c	(revision 110439)
+++ cfgcleanup.c	(working copy)
@@ -60,9 +60,7 @@ Software Foundation, 51 Franklin Street,
 static bool first_pass;
 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 int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
-static bool old_insns_match_p (int, rtx, rtx);
+static bool outgoing_edges_match (int *, struct equiv_info *);
 
 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
@@ -74,7 +72,6 @@ static bool mark_effect (rtx, bitmap);
 static void notice_new_block (basic_block);
 static void update_forwarder_flag (basic_block);
 static int mentions_nonequal_regs (rtx *, void *);
-static void merge_memattrs (rtx, rtx);
 
 /* Set flags for newly created block.  */
 
@@ -881,319 +878,6 @@ merge_blocks_move (edge e, basic_block b
   return NULL;
 }
 
-
-/* Removes the memory attributes of MEM expression
-   if they are not equal.  */
-
-void
-merge_memattrs (rtx x, rtx y)
-{
-  int i;
-  int j;
-  enum rtx_code code;
-  const char *fmt;
-
-  if (x == y)
-    return;
-  if (x == 0 || y == 0)
-    return;
-
-  code = GET_CODE (x);
-
-  if (code != GET_CODE (y))
-    return;
-
-  if (GET_MODE (x) != GET_MODE (y))
-    return;
-
-  if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
-    {
-      if (! MEM_ATTRS (x))
-	MEM_ATTRS (y) = 0;
-      else if (! MEM_ATTRS (y))
-	MEM_ATTRS (x) = 0;
-      else 
-	{
-	  rtx mem_size;
-
-	  if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
-	    {
-	      set_mem_alias_set (x, 0);
-	      set_mem_alias_set (y, 0);
-	    }
-	  
-	  if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
-	    {
-	      set_mem_expr (x, 0);
-	      set_mem_expr (y, 0);
-	      set_mem_offset (x, 0);
-	      set_mem_offset (y, 0);
-	    }
-	  else if (MEM_OFFSET (x) != MEM_OFFSET (y))
-	    {
-	      set_mem_offset (x, 0);
-	      set_mem_offset (y, 0);
-	    }
-	 
-	  if (!MEM_SIZE (x))
-	    mem_size = NULL_RTX;
-	  else if (!MEM_SIZE (y))
-	    mem_size = NULL_RTX;
-	  else
-	    mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
-				     INTVAL (MEM_SIZE (y))));
-	  set_mem_size (x, mem_size);
-	  set_mem_size (y, mem_size);
-
-	  set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
-	  set_mem_align (y, MEM_ALIGN (x));
-	}
-    }
-  
-  fmt = GET_RTX_FORMAT (code);
-  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
-    {
-      switch (fmt[i])
-	{
-	case 'E':
-	  /* Two vectors must have the same length.  */
-	  if (XVECLEN (x, i) != XVECLEN (y, i))
-	    return;
-
-	  for (j = 0; j < XVECLEN (x, i); j++)
-	    merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
-
-	  break;
-
-	case 'e':
-	  merge_memattrs (XEXP (x, i), XEXP (y, i));
-	}
-    }
-  return;
-}
-
-
-/* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
-
-static bool
-old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
-{
-  rtx p1, p2;
-
-  /* Verify that I1 and I2 are equivalent.  */
-  if (GET_CODE (i1) != GET_CODE (i2))
-    return false;
-
-  p1 = PATTERN (i1);
-  p2 = PATTERN (i2);
-
-  if (GET_CODE (p1) != GET_CODE (p2))
-    return false;
-
-  /* If this is a CALL_INSN, compare register usage information.
-     If we don't check this on stack register machines, the two
-     CALL_INSNs might be merged leaving reg-stack.c with mismatching
-     numbers of stack registers in the same basic block.
-     If we don't check this on machines with delay slots, a delay slot may
-     be filled that clobbers a parameter expected by the subroutine.
-
-     ??? We take the simple route for now and assume that if they're
-     equal, they were constructed identically.  */
-
-  if (CALL_P (i1)
-      && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
-		        CALL_INSN_FUNCTION_USAGE (i2))
-	  || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
-    return false;
-
-#ifdef STACK_REGS
-  /* If cross_jump_death_matters is not 0, the insn's mode
-     indicates whether or not the insn contains any stack-like
-     regs.  */
-
-  if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
-    {
-      /* If register stack conversion has already been done, then
-         death notes must also be compared before it is certain that
-         the two instruction streams match.  */
-
-      rtx note;
-      HARD_REG_SET i1_regset, i2_regset;
-
-      CLEAR_HARD_REG_SET (i1_regset);
-      CLEAR_HARD_REG_SET (i2_regset);
-
-      for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
-	if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
-	  SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
-
-      for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
-	if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
-	  SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
-
-      GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
-
-      return false;
-
-    done:
-      ;
-    }
-#endif
-
-  if (reload_completed
-      ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
-    return true;
-
-  /* Do not do EQUIV substitution after reload.  First, we're undoing the
-     work of reload_cse.  Second, we may be undoing the work of the post-
-     reload splitting pass.  */
-  /* ??? Possibly add a new phase switch variable that can be used by
-     targets to disallow the troublesome insns after splitting.  */
-  if (!reload_completed)
-    {
-      /* The following code helps take care of G++ cleanups.  */
-      rtx equiv1 = find_reg_equal_equiv_note (i1);
-      rtx equiv2 = find_reg_equal_equiv_note (i2);
-
-      if (equiv1 && equiv2
-	  /* If the equivalences are not to a constant, they may
-	     reference pseudos that no longer exist, so we can't
-	     use them.  */
-	  && (! reload_completed
-	      || (CONSTANT_P (XEXP (equiv1, 0))
-		  && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
-	{
-	  rtx s1 = single_set (i1);
-	  rtx s2 = single_set (i2);
-	  if (s1 != 0 && s2 != 0
-	      && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
-	    {
-	      validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
-	      validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
-	      if (! rtx_renumbered_equal_p (p1, p2))
-		cancel_changes (0);
-	      else if (apply_change_group ())
-		return true;
-	    }
-	}
-    }
-
-  return false;
-}
-
-/* Look through the insns at the end of BB1 and BB2 and find the longest
-   sequence that are equivalent.  Store the first insns for that sequence
-   in *F1 and *F2 and return the sequence length.
-
-   To simplify callers of this function, if the blocks match exactly,
-   store the head of the blocks in *F1 and *F2.  */
-
-static int
-flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
-		      basic_block bb2, rtx *f1, rtx *f2)
-{
-  rtx i1, i2, last1, last2, afterlast1, afterlast2;
-  int ninsns = 0;
-
-  /* Skip simple jumps at the end of the blocks.  Complex jumps still
-     need to be compared for equivalence, which we'll do below.  */
-
-  i1 = BB_END (bb1);
-  last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
-  if (onlyjump_p (i1)
-      || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
-    {
-      last1 = i1;
-      i1 = PREV_INSN (i1);
-    }
-
-  i2 = BB_END (bb2);
-  if (onlyjump_p (i2)
-      || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
-    {
-      last2 = i2;
-      /* Count everything except for unconditional jump as insn.  */
-      if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
-	ninsns++;
-      i2 = PREV_INSN (i2);
-    }
-
-  while (true)
-    {
-      /* Ignore notes.  */
-      while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
-	i1 = PREV_INSN (i1);
-
-      while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
-	i2 = PREV_INSN (i2);
-
-      if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
-	break;
-
-      if (!old_insns_match_p (mode, i1, i2))
-	break;
-
-      merge_memattrs (i1, i2);
-
-      /* Don't begin a cross-jump with a NOTE insn.  */
-      if (INSN_P (i1))
-	{
-	  /* If the merged insns have different REG_EQUAL notes, then
-	     remove them.  */
-	  rtx equiv1 = find_reg_equal_equiv_note (i1);
-	  rtx equiv2 = find_reg_equal_equiv_note (i2);
-
-	  if (equiv1 && !equiv2)
-	    remove_note (i1, equiv1);
-	  else if (!equiv1 && equiv2)
-	    remove_note (i2, equiv2);
-	  else if (equiv1 && equiv2
-		   && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
-	    {
-	      remove_note (i1, equiv1);
-	      remove_note (i2, equiv2);
-	    }
-
-	  afterlast1 = last1, afterlast2 = last2;
-	  last1 = i1, last2 = i2;
-	  ninsns++;
-	}
-
-      i1 = PREV_INSN (i1);
-      i2 = PREV_INSN (i2);
-    }
-
-#ifdef HAVE_cc0
-  /* Don't allow the insn after a compare to be shared by
-     cross-jumping unless the compare is also shared.  */
-  if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
-    last1 = afterlast1, last2 = afterlast2, ninsns--;
-#endif
-
-  /* Include preceding notes and labels in the cross-jump.  One,
-     this may bring us to the head of the blocks as requested above.
-     Two, it keeps line number notes as matched as may be.  */
-  if (ninsns)
-    {
-      while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
-	last1 = PREV_INSN (last1);
-
-      if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
-	last1 = PREV_INSN (last1);
-
-      while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
-	last2 = PREV_INSN (last2);
-
-      if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
-	last2 = PREV_INSN (last2);
-
-      *f1 = last1;
-      *f2 = last2;
-    }
-
-  return ninsns;
-}
-
 /* Return true iff the condbranches at the end of BB1 and BB2 match.  */
 bool
 condjump_equiv_p (struct equiv_info *info, bool call_init)
@@ -1252,8 +936,8 @@ condjump_equiv_p (struct equiv_info *inf
   if (code2 == UNKNOWN)
     return false;
 
-  if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
-    gcc_unreachable ();
+  if (call_init)
+    struct_equiv_init (STRUCT_EQUIV_START | info->mode, info, false);
   /* Make the sources of the pc sets unreadable so that when we call
      insns_match_p it won't process them.
      The death_notes_match_p from insns_match_p won't see the local registers
@@ -1322,15 +1006,20 @@ condjump_equiv_p (struct equiv_info *inf
   return match;
 }
 
-/* Return true iff outgoing edges of BB1 and BB2 match, together with
-   the branch instruction.  This means that if we commonize the control
-   flow before end of the basic block, the semantic remains unchanged.
+/* Return true iff outgoing edges of INFO->y_block and INFO->x_block match,
+   together with the branch instruction.  This means that if we commonize the
+   control flow before end of the basic block, the semantic remains unchanged.
+   If we need to compare jumps, we set STRUCT_EQUIV_MATCH_JUMPS in *MODE,
+   and pass *MODE to struct_equiv_init or assign it to INFO->mode, as
+   appropriate.
 
    We may assume that there exists one edge with a common destination.  */
 
 static bool
-outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
+outgoing_edges_match (int *mode, struct equiv_info *info)
 {
+  basic_block bb1 = info->y_block;
+  basic_block bb2 = info->x_block;
   int nehedges1 = 0, nehedges2 = 0;
   edge fallthru1 = 0, fallthru2 = 0;
   edge e1, e2;
@@ -1346,114 +1035,19 @@ outgoing_edges_match (int mode, basic_bl
 		& (EDGE_COMPLEX | EDGE_FAKE)) == 0
 	    && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
 
+  *mode |= STRUCT_EQUIV_MATCH_JUMPS;
   /* Match conditional jumps - this may get tricky when fallthru and branch
      edges are crossed.  */
   if (EDGE_COUNT (bb1->succs) == 2
       && any_condjump_p (BB_END (bb1))
       && onlyjump_p (BB_END (bb1)))
     {
-      edge b1, f1, b2, f2;
-      bool reverse, match;
-      rtx set1, set2, cond1, cond2;
-      enum rtx_code code1, code2;
-
       if (EDGE_COUNT (bb2->succs) != 2
 	  || !any_condjump_p (BB_END (bb2))
 	  || !onlyjump_p (BB_END (bb2)))
 	return false;
-
-      b1 = BRANCH_EDGE (bb1);
-      b2 = BRANCH_EDGE (bb2);
-      f1 = FALLTHRU_EDGE (bb1);
-      f2 = FALLTHRU_EDGE (bb2);
-
-      /* Get around possible forwarders on fallthru edges.  Other cases
-         should be optimized out already.  */
-      if (FORWARDER_BLOCK_P (f1->dest))
-	f1 = single_succ_edge (f1->dest);
-
-      if (FORWARDER_BLOCK_P (f2->dest))
-	f2 = single_succ_edge (f2->dest);
-
-      /* To simplify use of this function, return false if there are
-	 unneeded forwarder blocks.  These will get eliminated later
-	 during cleanup_cfg.  */
-      if (FORWARDER_BLOCK_P (f1->dest)
-	  || FORWARDER_BLOCK_P (f2->dest)
-	  || FORWARDER_BLOCK_P (b1->dest)
-	  || FORWARDER_BLOCK_P (b2->dest))
-	return false;
-
-      if (f1->dest == f2->dest && b1->dest == b2->dest)
-	reverse = false;
-      else if (f1->dest == b2->dest && b1->dest == f2->dest)
-	reverse = true;
-      else
-	return false;
-
-      set1 = pc_set (BB_END (bb1));
-      set2 = pc_set (BB_END (bb2));
-      if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
-	  != (XEXP (SET_SRC (set2), 1) == pc_rtx))
-	reverse = !reverse;
-
-      cond1 = XEXP (SET_SRC (set1), 0);
-      cond2 = XEXP (SET_SRC (set2), 0);
-      code1 = GET_CODE (cond1);
-      if (reverse)
-	code2 = reversed_comparison_code (cond2, BB_END (bb2));
-      else
-	code2 = GET_CODE (cond2);
-
-      if (code2 == UNKNOWN)
-	return false;
-
-      /* Verify codes and operands match.  */
-      match = ((code1 == code2
-		&& rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
-		&& rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
-	       || (code1 == swap_condition (code2)
-		   && rtx_renumbered_equal_p (XEXP (cond1, 1),
-					      XEXP (cond2, 0))
-		   && rtx_renumbered_equal_p (XEXP (cond1, 0),
-					      XEXP (cond2, 1))));
-
-      /* If we return true, we will join the blocks.  Which means that
-	 we will only have one branch prediction bit to work with.  Thus
-	 we require the existing branches to have probabilities that are
-	 roughly similar.  */
-      if (match
-	  && !optimize_size
-	  && maybe_hot_bb_p (bb1)
-	  && maybe_hot_bb_p (bb2))
-	{
-	  int prob2;
-
-	  if (b1->dest == b2->dest)
-	    prob2 = b2->probability;
-	  else
-	    /* Do not use f2 probability as f2 may be forwarded.  */
-	    prob2 = REG_BR_PROB_BASE - b2->probability;
-
-	  /* Fail if the difference in probabilities is greater than 50%.
-	     This rules out two well-predicted branches with opposite
-	     outcomes.  */
-	  if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
-	    {
-	      if (dump_file)
-		fprintf (dump_file,
-			 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
-			 bb1->index, bb2->index, b1->probability, prob2);
-
-	      return false;
-	    }
-	}
-
-      if (dump_file && match)
-	fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
-		 bb1->index, bb2->index);
-
-      return match;
+      info->mode = *mode;
+      return condjump_equiv_p (info, true);
     }
 
   /* Generic case - we are seeing a computed jump, table jump or trapping
@@ -1501,31 +1095,22 @@ outgoing_edges_match (int mode, basic_bl
 		      identical = false;
 		}
 
-	      if (identical)
+	      if (identical
+		  && struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true))
 		{
-		  replace_label_data rr;
 		  bool match;
 
-		  /* Temporarily replace references to LABEL1 with LABEL2
+		  /* Indicate that LABEL1 is to be replaced with LABEL2
 		     in BB1->END so that we could compare the instructions.  */
-		  rr.r1 = label1;
-		  rr.r2 = label2;
-		  rr.update_label_nuses = false;
-		  for_each_rtx (&BB_END (bb1), replace_label, &rr);
+		  info->y_label = label1;
+		  info->x_label = label2;
 
-		  match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
+		  match = insns_match_p (BB_END (bb1), BB_END (bb2), info);
 		  if (dump_file && match)
 		    fprintf (dump_file,
 			     "Tablejumps in bb %i and %i match.\n",
 			     bb1->index, bb2->index);
 
-		  /* Set the original label in BB1->END because when deleting
-		     a block whose end is a tablejump, the tablejump referenced
-		     from the instruction is deleted too.  */
-		  rr.r1 = label2;
-		  rr.r2 = label1;
-		  for_each_rtx (&BB_END (bb1), replace_label, &rr);
-
 		  return match;
 		}
 	    }
@@ -1533,16 +1118,20 @@ outgoing_edges_match (int mode, basic_bl
 	}
     }
 
+  /* Ensure that the edge counts do match.  */
+  if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
+    return false;
+
   /* First ensure that the instructions match.  There may be many outgoing
      edges so this test is generally cheaper.  */
-  if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
+  /* FIXME: the regset compare might be costly.  We should try to get a cheap
+     and reasonably effective test first.  */
+  if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true)
+      || !insns_match_p (BB_END (bb1), BB_END (bb2), info))
     return false;
 
-  /* Search the outgoing edges, ensure that the counts do match, find possible
-     fallthru and exception handling edges since these needs more
-     validation.  */
-  if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
-    return false;
+  /* Search the outgoing edges, find possible fallthru and exception
+     handling edges since these needs more validation.  */
 
   FOR_EACH_EDGE (e1, ei, bb1->succs)
     {
@@ -1633,22 +1222,21 @@ block_has_preserve_label (basic_block bb
 static bool
 try_crossjump_to_edge (int mode, edge e1, edge e2)
 {
-  int nmatch;
+  int nmatch, i;
   basic_block src1 = e1->src, src2 = e2->src;
   basic_block redirect_to, redirect_from, to_remove;
-  rtx newpos1, newpos2;
   edge s;
   edge_iterator ei;
-
-  newpos1 = newpos2 = NULL_RTX;
+  struct equiv_info info;
+  rtx x_active, y_active;
 
   /* If we have partitioned hot/cold basic blocks, it is a bad idea
-     to try this optimization. 
+     to try this optimization.
 
      Basic block partitioning may result in some jumps that appear to
-     be optimizable (or blocks that appear to be mergeable), but which really 
-     must be left untouched (they are required to make it safely across 
-     partition boundaries).  See the comments at the top of 
+     be optimizable (or blocks that appear to be mergeable), but which really
+     must be left untouched (they are required to make it safely across
+     partition boundaries).  See the comments at the top of
      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 
   if (flag_reorder_blocks_and_partition && no_new_pseudos)
@@ -1687,19 +1275,66 @@ try_crossjump_to_edge (int mode, edge e1
     return false;
 
   /* Look for the common insn sequence, part the first ...  */
-  if (!outgoing_edges_match (mode, src1, src2))
+  info.x_block = src2;
+  info.y_block = src1;
+  if (!outgoing_edges_match (&mode, &info))
     return false;
 
   /* ... and part the second.  */
-  nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
+  info.input_cost = optimize_size ? COSTS_N_INSNS (1) : -1;
+  nmatch = struct_equiv_block_eq (STRUCT_EQUIV_START | mode, &info);
 
   /* Don't proceed with the crossjump unless we found a sufficient number
      of matching instructions or the 'from' block was totally matched
      (such that its predecessors will hopefully be redirected and the
      block removed).  */
-  if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
-      && (newpos1 != BB_HEAD (src1)))
+  if (!nmatch)
+    return false;
+  if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+      && (info.cur.y_start != BB_HEAD (src1)))
     return false;
+  while (info.need_rerun)
+    {
+      nmatch = struct_equiv_block_eq (STRUCT_EQUIV_RERUN | mode, &info);
+      if (!nmatch)
+	return false;
+      if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+	   && (info.cur.y_start != BB_HEAD (src1)))
+	return false;
+    }
+  nmatch = struct_equiv_block_eq (STRUCT_EQUIV_FINAL | mode, &info);
+  if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+      && (info.cur.y_start != BB_HEAD (src1)))
+    return false;
+
+  /* Skip possible basic block header.  */
+  x_active = info.cur.x_start;
+  if (LABEL_P (x_active))
+    x_active = NEXT_INSN (x_active);
+  if (NOTE_P (x_active))
+    x_active = NEXT_INSN (x_active);
+
+  y_active = info.cur.y_start;
+  if (LABEL_P (y_active))
+    y_active = NEXT_INSN (y_active);
+  if (NOTE_P (y_active))
+    y_active = NEXT_INSN (y_active);
+
+  /* In order for this code to become active, either we have to be called
+     before reload, or struct_equiv_block_eq needs to add register scavenging
+     code to allocate input_reg after reload.  */
+  if (info.input_reg)
+    {
+      emit_insn_before (gen_move_insn (info.input_reg, info.x_input),
+			x_active);
+      emit_insn_before (gen_move_insn (info.input_reg, info.y_input),
+			y_active);
+    }
+
+  for (i = 0; i < info.cur.local_count; i++)
+    if (info.local_rvalue[i])
+      emit_insn_before (gen_move_insn (info.x_local[i], info.y_local[i]),
+			y_active);
 
   /* Avoid deleting preserve label when redirecting ABNORMAL edeges.  */
   if (block_has_preserve_label (e1->dest)
@@ -1740,30 +1375,34 @@ try_crossjump_to_edge (int mode, edge e1
   /* Avoid splitting if possible.  We must always split when SRC2 has
      EH predecessor edges, or we may end up with basic blocks with both
      normal and EH predecessor edges.  */
-  if (newpos2 == BB_HEAD (src2)
+  if (info.cur.x_start == BB_HEAD (src2)
       && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
     redirect_to = src2;
   else
     {
-      if (newpos2 == BB_HEAD (src2))
+      if (info.cur.x_start == BB_HEAD (src2))
 	{
 	  /* Skip possible basic block header.  */
-	  if (LABEL_P (newpos2))
-	    newpos2 = NEXT_INSN (newpos2);
-	  if (NOTE_P (newpos2))
-	    newpos2 = NEXT_INSN (newpos2);
+	  if (LABEL_P (info.cur.x_start))
+	    info.cur.x_start = NEXT_INSN (info.cur.x_start);
+	  if (NOTE_P (info.cur.x_start))
+	    info.cur.x_start = NEXT_INSN (info.cur.x_start);
 	}
 
       if (dump_file)
 	fprintf (dump_file, "Splitting bb %i before %i insns\n",
 		 src2->index, nmatch);
-      redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
+      redirect_to = split_block (src2, PREV_INSN (info.cur.x_start))->dest;
     }
 
   if (dump_file)
-    fprintf (dump_file,
-	     "Cross jumping from bb %i to bb %i; %i common insns\n",
-	     src1->index, src2->index, nmatch);
+    {
+      fprintf (dump_file, "Cross jumping from bb %i to bb %i; %i common insns",
+	       src1->index, src2->index, nmatch);
+      if (info.cur.local_count)
+	fprintf (dump_file, ", %i local registers", info.cur.local_count);
+       fprintf (dump_file, "\n");
+    }
 
   redirect_to->count += src1->count;
   redirect_to->frequency += src1->frequency;
@@ -1827,17 +1466,12 @@ try_crossjump_to_edge (int mode, edge e1
 
   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
 
-  /* Skip possible basic block header.  */
-  if (LABEL_P (newpos1))
-    newpos1 = NEXT_INSN (newpos1);
-
-  if (NOTE_P (newpos1))
-    newpos1 = NEXT_INSN (newpos1);
-
-  redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
+  redirect_from = split_block (src1, PREV_INSN (y_active))->src;
   to_remove = single_succ (redirect_from);
 
   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
+  COPY_REG_SET (redirect_from->il.rtl->global_live_at_end,
+		redirect_to->il.rtl->global_live_at_start);
   delete_basic_block (to_remove);
 
   update_forwarder_flag (redirect_from);
@@ -1994,9 +1628,30 @@ try_optimize_cfg (int mode)
   bool changed;
   int iterations = 0;
   basic_block bb, b, next;
+  bool can_modify_jumps = ! targetm.cannot_modify_jumps_p ();
+  bool do_crossjump = false;
 
-  if (mode & CLEANUP_CROSSJUMP)
-    add_noreturn_fake_exit_edges ();
+  if (can_modify_jumps && (mode & CLEANUP_CROSSJUMP))
+    {
+      do_crossjump = true;
+      add_noreturn_fake_exit_edges ();
+      /* N.B.: Life info updates malfunction in the presence of fake edges.
+	 If we want to do any updates while fake edges are present, we'll have
+	 to make sure to exclude them when recomputing global_live_at_end,
+	 or treat them like EH edges.  */
+#ifdef STACK_REGS
+      if (mode & CLEANUP_POST_REGSTACK)
+	{
+	  /* Live information about stack regs is completely unreliable.
+	     Including them in maybe_killed_regs will make
+	     struct_equiv_regs_eq_p ignore them.  */
+	  int i;
+
+	  for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
+	    SET_REGNO_REG_SET (maybe_killed_regs, i);
+	}
+#endif
+    }
 
   if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
     clear_bb_flags ();
@@ -2004,7 +1659,7 @@ try_optimize_cfg (int mode)
   FOR_EACH_BB (bb)
     update_forwarder_flag (bb);
 
-  if (! targetm.cannot_modify_jumps_p ())
+  if (can_modify_jumps)
     {
       first_pass = true;
       /* Attempt to merge blocks as made possible by edge removal.  If
@@ -2160,8 +1815,8 @@ try_optimize_cfg (int mode)
 		changed_here = true;
 
 	      /* Look for shared code between blocks.  */
-	      if ((mode & CLEANUP_CROSSJUMP)
-		  && try_crossjump_bb (mode, b))
+	      if (do_crossjump
+		  && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES, b))
 		changed_here = true;
 
 	      /* Don't get confused by the index shift caused by
@@ -2172,8 +1827,9 @@ try_optimize_cfg (int mode)
 		changed = true;
 	    }
 
-	  if ((mode & CLEANUP_CROSSJUMP)
-	      && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
+	  if (do_crossjump
+	      && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES,
+				   EXIT_BLOCK_PTR))
 	    changed = true;
 
 #ifdef ENABLE_CHECKING
@@ -2187,7 +1843,7 @@ try_optimize_cfg (int mode)
       while (changed);
     }
 
-  if (mode & CLEANUP_CROSSJUMP)
+  if (do_crossjump)
     remove_fake_exit_edges ();
 
   FOR_ALL_BB (b)
Index: basic-block.h
===================================================================
/usr/bin/diff -p -d -F^( -u -L basic-block.h	(revision 110439) -L basic-block.h	(working copy) .svn/text-base/basic-block.h.svn-base basic-block.h
--- basic-block.h	(revision 110439)
+++ basic-block.h	(working copy)
@@ -382,6 +382,10 @@ struct control_flow_graph GTY(())
      only used for the tree CFG.  */
   VEC(basic_block,gc) *x_label_to_block_map;
 
+  /* Registers that might have been killed since the last recomputation of
+     data flow info.  */
+  bitmap GTY ((skip (""))) x_maybe_killed_regs;
+
   enum profile_status {
     PROFILE_ABSENT,
     PROFILE_GUESSED,
@@ -410,6 +414,7 @@ struct control_flow_graph GTY(())
 #define last_basic_block	(cfun->cfg->x_last_basic_block)
 #define label_to_block_map	(cfun->cfg->x_label_to_block_map)
 #define profile_status		(cfun->cfg->x_profile_status)
+#define maybe_killed_regs	(cfun->cfg->x_maybe_killed_regs)
 
 #define BASIC_BLOCK(N)		(VEC_index (basic_block, basic_block_info, (N)))
 #define SET_BASIC_BLOCK(N,BB)	(VEC_replace (basic_block, basic_block_info, (N), (BB)))
@@ -852,11 +857,14 @@ enum update_life_extent
 					     to match only full blocks  */
 #define STRUCT_EQUIV_MATCH_JUMPS 8192	/* Also include the jumps at the end of the block in the comparison.  */
 
+#define STRUCT_EQUIV_SUSPEND_UPDATES 16384 /* Assume global_live_at_end is up-to-date even if the block isn't.  */
+
 extern void life_analysis (FILE *, int);
 extern int update_life_info (sbitmap, enum update_life_extent, int);
 extern int update_life_info_in_dirty_blocks (enum update_life_extent, int);
 extern int count_or_remove_death_notes (sbitmap, int);
 extern int propagate_block (basic_block, regset, regset, regset, int);
+extern regset used_by_bb_end (rtx, basic_block, regset);
 
 struct propagate_block_info;
 extern rtx propagate_one_insn (struct propagate_block_info *, rtx);
@@ -1169,7 +1177,7 @@ struct equiv_info
 
 extern bool insns_match_p (rtx, rtx, struct equiv_info *);
 extern int struct_equiv_block_eq (int, struct equiv_info *);
-extern bool struct_equiv_init (int, struct equiv_info *);
+extern bool struct_equiv_init (int, struct equiv_info *, bool);
 extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
 
 /* In cfgrtl.c */
Index: struct-equiv.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L struct-equiv.c	(revision 110439) -L struct-equiv.c	(working copy) .svn/text-base/struct-equiv.c.svn-base struct-equiv.c
--- struct-equiv.c	(revision 110439)
+++ struct-equiv.c	(working copy)
@@ -987,38 +987,49 @@ insns_match_p (rtx i1, rtx i2, struct eq
   return false;
 }
 
-/* Set up mode and register information in INFO.  Return true for success.  */
+static bool
+struct_equiv_regs_eq_p (struct equiv_info *info)
+{
+  regset_head diff;
+  bool equal;
+
+  if (!(info->mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+      && ((info->x_block->flags | info->y_block->flags) & BB_DIRTY))
+    update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+				      (PROP_DEATH_NOTES
+				       | ((info->mode & CLEANUP_POST_REGSTACK)
+					  ? PROP_POST_REGSTACK : 0)));
+  INIT_REG_SET (&diff);
+  bitmap_xor (&diff,
+	      info->x_block->il.rtl->global_live_at_end,
+	      info->y_block->il.rtl->global_live_at_end);
+  AND_COMPL_REG_SET (&diff, maybe_killed_regs);
+  equal = bitmap_empty_p (&diff);
+  CLEAR_REG_SET (&diff);
+  return equal;
+}
+
+/* Set up mode and register information in INFO.  Return true for success.
+   Nonzero CHECK_REGS_EQ indicates that we might be called with blocks that
+   have non-matching successor sets, and thus need to check their live_at_end
+   regsets for match in the first pass.  */
 bool
-struct_equiv_init (int mode, struct equiv_info *info)
+struct_equiv_init (int mode, struct equiv_info *info, bool check_regs_eq)
 {
-  if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
+  if (!(mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+      && ((info->x_block->flags & info->y_block->flags) & BB_DIRTY))
     update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
 				      (PROP_DEATH_NOTES
 				       | ((mode & CLEANUP_POST_REGSTACK)
 					  ? PROP_POST_REGSTACK : 0)));
-  if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
-			info->y_block->il.rtl->global_live_at_end))
+  info->mode = mode;
+  if (check_regs_eq && (mode & STRUCT_EQUIV_START))
     {
-#ifdef STACK_REGS
-      unsigned rn;
-
-      if (!(mode & CLEANUP_POST_REGSTACK))
-	return false;
-      /* After reg-stack.  Remove bogus live info about stack regs.  N.B.
-	 these regs are not necessarily all dead - we swap random bogosity
-	 against constant bogosity.  However, clearing these bits at
-	 least makes the regsets comparable.  */
-      for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
-	{
-	  CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
-	  CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
-	}
-      if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
-			    info->y_block->il.rtl->global_live_at_end))
-#endif
+      if (!struct_equiv_regs_eq_p (info))
 	return false;
     }
-  info->mode = mode;
+  else if (mode & (STRUCT_EQUIV_FINAL | STRUCT_EQUIV_SUSPEND_UPDATES))
+    gcc_assert (struct_equiv_regs_eq_p (info));
   if (mode & STRUCT_EQUIV_START)
     {
       info->x_input = info->y_input = info->input_reg = NULL_RTX;
@@ -1036,7 +1047,15 @@ struct_equiv_init (int mode, struct equi
   info->common_live = ALLOC_REG_SET (&reg_obstack);
   info->x_local_live = ALLOC_REG_SET (&reg_obstack);
   info->y_local_live = ALLOC_REG_SET (&reg_obstack);
-  COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
+  if (mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+    bitmap_and (info->common_live,
+		info->x_block->il.rtl->global_live_at_end,
+		info->y_block->il.rtl->global_live_at_end);
+  else
+    COPY_REG_SET (info->common_live,
+		  ((info->x_block->flags & BB_DIRTY
+		    ? info->y_block : info->x_block)
+		   ->il.rtl->global_live_at_end));
   struct_equiv_make_checkpoint (&info->best_match, info);
   return true;
 }
@@ -1100,8 +1119,7 @@ struct_equiv_block_eq (int mode, struct 
       x_stop = info->cur.x_start;
       y_stop = info->cur.y_start;
     }
-  if (!struct_equiv_init (mode, info))
-    gcc_unreachable ();
+  struct_equiv_init (mode, info, false);
 
   /* Skip simple jumps at the end of the blocks.  Complex jumps still
      need to be compared for equivalence, which we'll do below.  */
Index: cfgrtl.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgrtl.c	(revision 110439) -L cfgrtl.c	(working copy) .svn/text-base/cfgrtl.c.svn-base cfgrtl.c
--- cfgrtl.c	(revision 110439)
+++ cfgrtl.c	(working copy)
@@ -686,6 +686,7 @@ try_redirect_by_replacing_jump (edge e, 
   rtx insn = BB_END (src), kill_from;
   rtx set;
   int fallthru = 0;
+  regset_head used_2b_used;
 
   /* If we are partitioning hot/cold basic blocks, we don't want to
      mess up unconditional or indirect jumps that cross between hot
@@ -741,6 +742,8 @@ try_redirect_by_replacing_jump (edge e, 
 	{
 	  rtx insn = src->il.rtl->footer;
 
+	  INIT_REG_SET (&used_2b_used);
+	  used_by_bb_end (kill_from, src, &used_2b_used);
           delete_insn_chain (kill_from, BB_END (src));
 
 	  /* Remove barriers but keep jumptables.  */
@@ -761,7 +764,11 @@ try_redirect_by_replacing_jump (edge e, 
 	    }
 	}
       else
-        delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
+	{
+	  INIT_REG_SET (&used_2b_used);
+	  used_by_bb_end (kill_from, src, &used_2b_used);
+	  delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
+	}
     }
 
   /* If this already is simplejump, redirect it.  */
@@ -777,6 +784,7 @@ try_redirect_by_replacing_jump (edge e, 
 	  gcc_assert (target == EXIT_BLOCK_PTR);
 	  return NULL;
 	}
+      INIT_REG_SET (&used_2b_used);
     }
 
   /* Cannot do anything for target exit block.  */
@@ -789,6 +797,9 @@ try_redirect_by_replacing_jump (edge e, 
       rtx target_label = block_label (target);
       rtx barrier, label, table;
 
+      INIT_REG_SET (&used_2b_used);
+      used_by_bb_end (kill_from, src, &used_2b_used);
+
       emit_jump_insn_after_noloc (gen_jump (target_label), insn);
       JUMP_LABEL (BB_END (src)) = target_label;
       LABEL_NUSES (target_label)++;
@@ -834,6 +845,14 @@ try_redirect_by_replacing_jump (edge e, 
 	}
     }
 
+  /* Any registers that used to be used by the old jump are possibly dead now.
+     incremental life updates might leave the notion that they are live
+     lingering around, so we want to keep track of these registers so that
+     we know the live information for them might be overly conservative.  */
+  if (maybe_killed_regs)
+    IOR_REG_SET (maybe_killed_regs, &used_2b_used);
+  CLEAR_REG_SET (&used_2b_used);
+
   /* Keep only one edge out and set proper flags.  */
   if (!single_succ_p (src))
     remove_edge (e);