basic-block.h (redirect_edge_and_branch_force, [...]): Declare.

	* basic-block.h (redirect_edge_and_branch_force,
	redirect_edge_and_branch, block_label, forwarder_block_p): Declare.
	* flow.c (redirect_edge_and_branch_force,
	redirect_edge_and_branch, block_label, forwarder_block_p): Make global.
	(redirect_edge_and_branch_force): Fix copying of lifeness information.
	(block_label): Handle EXIT_BLOCK_PTR by returning NULL.
	* ifcvt.c (dead_or_predictable): Take BB as an new destionation
	instead of label; update CFG after transformation.
	(find_if_case_1): Update call, use redirect_edge_and_branch_force
	for finishing the transformation; handle even case where ELSE
	does not follow THEN.
	(find_if_case_2): Update call of dead_or_predictable; simplify
	CFG update.

	* emit-rtl.c (split_branch_probability): New global variable.
	(try_split): Take care to set split_branch_probability and
	create REG_BR_PROB note for new jump insns.
	* md.texi (define_split): Document new feature.

	* i386.c (ix86_split_fp_branch): Redistribute branch probability notes.

From-SVN: r44249

8 files changed, 178 insertions, 87 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 29f9d56..9898084 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,26 @@
+Sun Jul 22 23:28:56 CEST 2001  Jan Hubicka  <jh@suse.cz>
+
+	* basic-block.h (redirect_edge_and_branch_force,
+	redirect_edge_and_branch, block_label, forwarder_block_p): Declare.
+	* flow.c (redirect_edge_and_branch_force,
+	redirect_edge_and_branch, block_label, forwarder_block_p): Make global.
+	(redirect_edge_and_branch_force): Fix copying of lifeness information.
+	(block_label): Handle EXIT_BLOCK_PTR by returning NULL.
+	* ifcvt.c (dead_or_predictable): Take BB as an new destionation
+	instead of label; update CFG after transformation.
+	(find_if_case_1): Update call, use redirect_edge_and_branch_force
+	for finishing the transformation; handle even case where ELSE
+	does not follow THEN.
+	(find_if_case_2): Update call of dead_or_predictable; simplify
+	CFG update.
+
+	* emit-rtl.c (split_branch_probability): New global variable.
+	(try_split): Take care to set split_branch_probability and
+	create REG_BR_PROB note for new jump insns.
+	* md.texi (define_split): Document new feature.
+
+	* i386.c (ix86_split_fp_branch): Redistribute branch probability notes.
+
 2001-07-22  Neil Booth  <neil@daikokuya.demon.co.uk>
 
 	* varasm.c: Don't inlcude dbxout.h, sdbout.h or xcoffout.h.
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 5b210fb..6a6039e 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -597,6 +597,11 @@ extern void debug_regset		PARAMS ((regset));
 extern void allocate_reg_life_data      PARAMS ((void));
 extern void allocate_bb_life_data	PARAMS ((void));
 extern void find_unreachable_blocks	PARAMS ((void));
+extern basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block));
+extern bool redirect_edge_and_branch	PARAMS ((edge, basic_block));
+extern rtx block_label			PARAMS ((basic_block));
+extern bool forwarder_block_p		PARAMS ((basic_block));
+
 
 /* This function is always defined so it can be called from the
    debugger, and it is declared extern so we don't get warnings about
diff --git a/gcc/config/i386/i386.c b/gcc/config/i386/i386.c
index 948fde2..821daa6 100644
--- a/gcc/config/i386/i386.c
+++ b/gcc/config/i386/i386.c
@@ -6267,6 +6267,8 @@ ix86_split_fp_branch (code, op1, op2, target1, target2, tmp)
   rtx second, bypass;
   rtx label = NULL_RTX;
   rtx condition;
+  int bypass_probability = -1, second_probability = -1, probability = -1;
+  rtx i;
 
   if (target2 != pc_rtx)
     {
@@ -6278,35 +6280,59 @@ ix86_split_fp_branch (code, op1, op2, target1, target2, tmp)
 
   condition = ix86_expand_fp_compare (code, op1, op2,
 				      tmp, &second, &bypass);
+
+  if (split_branch_probability >= 0)
+    {
+      /* Distribute the probabilities across the jumps.
+	 Assume the BYPASS and SECOND to be always test
+	 for UNORDERED.  */
+      probability = split_branch_probability;
+
+      /* Value of 1 is low enought to make no need for probability
+	 to be updated.  Later we may run some experiments and see
+	 if unordered values are more frequent in practice.  */
+      if (bypass)
+	bypass_probability = 1;
+      if (second)
+	second_probability = 1;
+    }
   if (bypass != NULL_RTX)
     {
       label = gen_label_rtx ();
-      emit_jump_insn (gen_rtx_SET
+      i = emit_jump_insn (gen_rtx_SET
+			  (VOIDmode, pc_rtx,
+			   gen_rtx_IF_THEN_ELSE (VOIDmode,
+						 bypass,
+						 gen_rtx_LABEL_REF (VOIDmode,
+								    label),
+						 pc_rtx)));
+      if (bypass_probability >= 0)
+	REG_NOTES (i)
+	  = gen_rtx_EXPR_LIST (REG_BR_PROB,
+			       GEN_INT (bypass_probability),
+			       REG_NOTES (i));
+    }
+  i = emit_jump_insn (gen_rtx_SET
 		      (VOIDmode, pc_rtx,
 		       gen_rtx_IF_THEN_ELSE (VOIDmode,
-					     bypass,
-					     gen_rtx_LABEL_REF (VOIDmode,
-								label),
-					     pc_rtx)));
-    }
-  /* AMD Athlon and probably other CPUs too have fast bypass path between the
-     comparison and first branch.  The second branch takes longer to execute
-     so place first branch the worse predicable one if possible.  */
-  if (second != NULL_RTX
-      && (GET_CODE (second) == UNORDERED || GET_CODE (second) == ORDERED))
-    {
-      rtx tmp = condition;
-      condition = second;
-      second = tmp;
-    }
-  emit_jump_insn (gen_rtx_SET
-		  (VOIDmode, pc_rtx,
-		   gen_rtx_IF_THEN_ELSE (VOIDmode,
-					 condition, target1, target2)));
+					     condition, target1, target2)));
+  if (probability >= 0)
+    REG_NOTES (i)
+      = gen_rtx_EXPR_LIST (REG_BR_PROB,
+			   GEN_INT (probability),
+			   REG_NOTES (i));
   if (second != NULL_RTX)
-    emit_jump_insn (gen_rtx_SET
-		    (VOIDmode, pc_rtx,
-		     gen_rtx_IF_THEN_ELSE (VOIDmode, second, target1, target2)));
+    {
+      i = emit_jump_insn (gen_rtx_SET
+			  (VOIDmode, pc_rtx,
+			   gen_rtx_IF_THEN_ELSE (VOIDmode, second, target1,
+						 target2)));
+      if (second_probability >= 0)
+	REG_NOTES (i)
+	  = gen_rtx_EXPR_LIST (REG_BR_PROB,
+			       GEN_INT (second_probability),
+			       REG_NOTES (i));
+    }
   if (label != NULL_RTX)
     emit_label (label);
 }
diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi
index 98752a6..0a79f34 100644
--- a/gcc/doc/md.texi
+++ b/gcc/doc/md.texi
@@ -3805,6 +3805,22 @@ insns that don't.  Instead, write two separate @code{define_split}
 definitions, one for the insns that are valid and one for the insns that
 are not valid.
 
+The splitter is allowed to split jump instructions into sequence of
+jumps or create new jumps in while splitting non-jump instructions.  As
+the central flowgraph and branch prediction information needs to be updated,
+several restriction apply. 
+
+Splitting of jump instruction into sequence that over by another jump
+instruction is always valid, as compiler expect identical behaviour of new
+jump.  When new sequence contains multiple jump instructions or new labels,
+more assistance is needed.  Splitter is required to create only unconditional
+jumps, or simple conditional jump instructions.  Additionally it must attach a
+@code{REG_BR_PROB} note to each conditional jump. An global variable
+@code{split_branch_probability} hold the probability of original branch in case
+it was an simple conditional jump, @minus{}1 otherwise.  To simplify
+recomputing of edge frequencies, new sequence is required to have only
+forward jumps to the newly created labels.
+
 For the common case where the pattern of a define_split exactly matches the
 pattern of a define_insn, use @code{define_insn_and_split}.  It looks like
 this:
diff --git a/gcc/emit-rtl.c b/gcc/emit-rtl.c
index 58e264f..5c021772 100644
--- a/gcc/emit-rtl.c
+++ b/gcc/emit-rtl.c
@@ -185,6 +185,10 @@ static int const_int_htab_eq            PARAMS ((const void *,
 static int rtx_htab_mark_1              PARAMS ((void **, void *));
 static void rtx_htab_mark               PARAMS ((void *));
 
+/* Probability of the conditional branch currently proceeded by try_split.
+   Set to -1 otherwise.  */
+int split_branch_probability = -1;
+
 
 /* Returns a hash code for X (which is a really a CONST_INT).  */
 
@@ -2486,9 +2490,19 @@ try_split (pat, trial, last)
 {
   rtx before = PREV_INSN (trial);
   rtx after = NEXT_INSN (trial);
-  rtx seq = split_insns (pat, trial);
   int has_barrier = 0;
   rtx tem;
+  rtx note, seq;
+  int probability;
+
+  if (any_condjump_p (trial)
+      && (note = find_reg_note (trial, REG_BR_PROB, 0)))
+    split_branch_probability = INTVAL (XEXP (note, 0));
+  probability = split_branch_probability;
+
+  seq = split_insns (pat, trial);
+
+  split_branch_probability = -1;
 
   /* If we are splitting a JUMP_INSN, it might be followed by a BARRIER.
      We may need to handle this specially.  */
@@ -2505,7 +2519,7 @@ try_split (pat, trial, last)
 	 it, in turn, will be split (SFmode on the 29k is an example).  */
       if (GET_CODE (seq) == SEQUENCE)
 	{
-	  int i;
+	  int i, njumps = 0;
 	  rtx eh_note;
 
 	  /* Avoid infinite loop if any insn of the result matches
@@ -2518,9 +2532,27 @@ try_split (pat, trial, last)
 	  /* Mark labels.  */
 	  for (i = XVECLEN (seq, 0) - 1; i >= 0; i--)
 	    if (GET_CODE (XVECEXP (seq, 0, i)) == JUMP_INSN)
-	      mark_jump_label (PATTERN (XVECEXP (seq, 0, i)),
-			       XVECEXP (seq, 0, i), 0);
-
+	      {
+		rtx insn = XVECEXP (seq, 0, i);
+		mark_jump_label (PATTERN (insn),
+				 XVECEXP (seq, 0, i), 0);
+		njumps++;
+		if (probability != -1
+		    && any_condjump_p (insn)
+		    && !find_reg_note (insn, REG_BR_PROB, 0))
+		  {
+		    /* We can preserve the REG_BR_PROB notes only if exactly
+		       one jump is created, otherwise the machinde description
+		       is responsible for this step using
+		       split_branch_probability variable.  */
+		    if (njumps != 1)
+		      abort ();
+		    REG_NOTES (insn)
+		      = gen_rtx_EXPR_LIST (REG_BR_PROB,
+					   GEN_INT (probability),
+					   REG_NOTES (insn));
+		  }
+	      }
 	  /* If we are splitting a CALL_INSN, look for the CALL_INSN
 	     in SEQ and copy our CALL_INSN_FUNCTION_USAGE to it.  */
 	  if (GET_CODE (trial) == CALL_INSN)
@@ -2577,8 +2609,8 @@ try_split (pat, trial, last)
       /* Return either the first or the last insn, depending on which was
 	 requested.  */
       return last
-		? (after ? prev_active_insn (after) : last_insn)
-		: next_active_insn (before);
+		? (after ? PREV_INSN (after) : last_insn)
+		: NEXT_INSN (before);
     }
 
   return trial;
diff --git a/gcc/flow.c b/gcc/flow.c
index fb054e4..a6a63e5 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -393,7 +393,6 @@ static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
 static int merge_blocks			PARAMS ((edge,basic_block,basic_block,
 						 int));
 static bool try_optimize_cfg		PARAMS ((int));
-static bool forwarder_block_p		PARAMS ((basic_block));
 static bool can_fallthru		PARAMS ((basic_block, basic_block));
 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
 static bool try_simplify_condjump	PARAMS ((basic_block));
@@ -485,9 +484,6 @@ static void flow_loops_tree_build	PARAMS ((struct loops *));
 static int flow_loop_level_compute	PARAMS ((struct loop *, int));
 static int flow_loops_level_compute	PARAMS ((struct loops *));
 static void find_sub_basic_blocks	PARAMS ((basic_block));
-static bool redirect_edge_and_branch 	PARAMS ((edge, basic_block));
-static basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block));
-static rtx block_label			PARAMS ((basic_block));
 
 /* Find basic blocks of the current function.
    F is the first insn of the function and NREGS the number of register
@@ -1598,10 +1594,12 @@ split_block (bb, insn)
 }
 
 /* Return label in the head of basic block.  Create one if it doesn't exist.  */
-static rtx
+rtx
 block_label (block)
      basic_block block;
 {
+  if (block == EXIT_BLOCK_PTR)
+    return NULL_RTX;
   if (GET_CODE (block->head) != CODE_LABEL)
     block->head = emit_label_before (gen_label_rtx (), block->head);
   return block->head;
@@ -1609,7 +1607,7 @@ block_label (block)
 
 /* Return true if the block has no effect and only forwards control flow to
    its single destination.  */
-static bool
+bool
 forwarder_block_p (bb)
      basic_block bb;
 {
@@ -1759,7 +1757,7 @@ try_redirect_by_replacing_jump (e, target)
    Return true if transformation suceeded.  We still return flase in case
    E already destinated TARGET and we didn't managed to simplify instruction
    stream.  */
-static bool
+bool
 redirect_edge_and_branch (e, target)
      edge e;
      basic_block target;
@@ -1867,7 +1865,7 @@ redirect_edge_and_branch (e, target)
 /* Redirect edge even at the expense of creating new jump insn or
    basic block.  Return new basic block if created, NULL otherwise.
    Abort if converison is impossible.  */
-static basic_block
+basic_block
 redirect_edge_and_branch_force (e, target)
      edge e;
      basic_block target;
@@ -1937,7 +1935,7 @@ redirect_edge_and_branch_force (e, target)
       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
       COPY_REG_SET (new_bb->global_live_at_start,
-		    e->dest->global_live_at_start);
+		    target->global_live_at_start);
       COPY_REG_SET (new_bb->global_live_at_end, new_bb->global_live_at_start);
     }
 
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index bdb44c4..08ec087 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -106,7 +106,7 @@ static int find_if_case_2		PARAMS ((basic_block, edge, edge));
 static int find_cond_trap		PARAMS ((basic_block, edge, edge));
 static int find_memory			PARAMS ((rtx *, void *));
 static int dead_or_predicable		PARAMS ((basic_block, basic_block,
-						 basic_block, rtx, int));
+						 basic_block, basic_block, int));
 static void noce_emit_move_insn		PARAMS ((rtx, rtx));
 
 /* Abuse the basic_block AUX field to store the original block index,
@@ -2183,9 +2183,8 @@ find_if_case_1 (test_bb, then_edge, else_edge)
       edge then_edge, else_edge;
 {
   basic_block then_bb = then_edge->dest;
-  basic_block else_bb = else_edge->dest;
+  basic_block else_bb = else_edge->dest, new_bb;
   edge then_succ = then_bb->succ;
-  rtx new_lab;
 
   /* THEN has one successor.  */
   if (!then_succ || then_succ->succ_next != NULL)
@@ -2199,8 +2198,8 @@ find_if_case_1 (test_bb, then_edge, else_edge)
   if (then_bb->pred->pred_next != NULL)
     return FALSE;
 
-  /* ELSE follows THEN.  (??? could be moved)  */
-  if (else_bb->index != then_bb->index + 1)
+  /* THEN must do something.  */
+  if (forwarder_block_p (then_bb))
     return FALSE;
 
   num_possible_if_blocks++;
@@ -2213,18 +2212,9 @@ find_if_case_1 (test_bb, then_edge, else_edge)
   if (count_bb_insns (then_bb) > BRANCH_COST)
     return FALSE;
 
-  /* Find the label for THEN's destination.  */
-  if (then_succ->dest == EXIT_BLOCK_PTR)
-    new_lab = NULL_RTX;
-  else
-    {
-      new_lab = JUMP_LABEL (then_bb->end);
-      if (! new_lab)
-	abort ();
-    }
-
   /* Registers set are dead, or are predicable.  */
-  if (! dead_or_predicable (test_bb, then_bb, else_bb, new_lab, 1))
+  if (! dead_or_predicable (test_bb, then_bb, else_bb, 
+			    then_bb->succ->dest, 1))
     return FALSE;
 
   /* Conversion went ok, including moving the insns and fixing up the
@@ -2235,9 +2225,17 @@ find_if_case_1 (test_bb, then_edge, else_edge)
 		    else_bb->global_live_at_start,
 		    then_bb->global_live_at_end, BITMAP_IOR);
   
-  make_edge (NULL, test_bb, then_succ->dest, 0);
+  new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
+  /* Make rest of code believe that the newly created block is the THEN_BB
+     block we are going to remove.  */
+  if (new_bb)
+    {
+      new_bb->aux = then_bb->aux;
+      SET_UPDATE_LIFE (then_bb);
+    }
   flow_delete_block (then_bb);
-  tidy_fallthru_edge (else_edge, test_bb, else_bb);
+  /* We've possibly created jump to next insn, cleanup_cfg will solve that
+     later.  */
 
   num_removed_blocks++;
   num_updated_if_blocks++;
@@ -2255,7 +2253,7 @@ find_if_case_2 (test_bb, then_edge, else_edge)
   basic_block then_bb = then_edge->dest;
   basic_block else_bb = else_edge->dest;
   edge else_succ = else_bb->succ;
-  rtx new_lab, note;
+  rtx note;
 
   /* ELSE has one successor.  */
   if (!else_succ || else_succ->succ_next != NULL)
@@ -2294,27 +2292,8 @@ find_if_case_2 (test_bb, then_edge, else_edge)
   if (count_bb_insns (then_bb) > BRANCH_COST)
     return FALSE;
 
-  /* Find the label for ELSE's destination.  */
-  if (else_succ->dest == EXIT_BLOCK_PTR)
-    new_lab = NULL_RTX;
-  else
-    {
-      if (else_succ->flags & EDGE_FALLTHRU)
-	{
-	  new_lab = else_succ->dest->head;
-	  if (GET_CODE (new_lab) != CODE_LABEL)
-	    abort ();
-	}
-      else
-	{
-	  new_lab = JUMP_LABEL (else_bb->end);
-	  if (! new_lab)
-	    abort ();
-	}
-    }
-
   /* Registers set are dead, or are predicable.  */
-  if (! dead_or_predicable (test_bb, else_bb, then_bb, new_lab, 0))
+  if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
     return FALSE;
 
   /* Conversion went ok, including moving the insns and fixing up the
@@ -2325,8 +2304,6 @@ find_if_case_2 (test_bb, then_edge, else_edge)
 		    then_bb->global_live_at_start,
 		    else_bb->global_live_at_end, BITMAP_IOR);
   
-  remove_edge (else_edge);
-  make_edge (NULL, test_bb, else_succ->dest, 0);
   flow_delete_block (else_bb);
 
   num_removed_blocks++;
@@ -2360,10 +2337,10 @@ find_memory (px, data)
 static int
 dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
      basic_block test_bb, merge_bb, other_bb;
-     rtx new_dest;
+     basic_block new_dest;
      int reversep;
 {
-  rtx head, end, jump, earliest, old_dest;
+  rtx head, end, jump, earliest, old_dest, new_label;
 
   jump = test_bb->end;
 
@@ -2548,9 +2525,10 @@ dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
      change group management.  */
 
   old_dest = JUMP_LABEL (jump);
+  new_label = block_label (new_dest);
   if (reversep
-      ? ! invert_jump_1 (jump, new_dest)
-      : ! redirect_jump_1 (jump, new_dest))
+      ? ! invert_jump_1 (jump, new_label)
+      : ! redirect_jump_1 (jump, new_label))
     goto cancel;
 
   if (! apply_change_group ())
@@ -2558,13 +2536,25 @@ dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
 
   if (old_dest)
     LABEL_NUSES (old_dest) -= 1;
-  if (new_dest)
-    LABEL_NUSES (new_dest) += 1;
-  JUMP_LABEL (jump) = new_dest;
+  if (new_label)
+    LABEL_NUSES (new_label) += 1;
+  JUMP_LABEL (jump) = new_label;
 
   if (reversep)
     invert_br_probabilities (jump);
 
+  redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
+  if (reversep)
+    {
+      gcov_type count, probability;
+      count = BRANCH_EDGE (test_bb)->count;
+      BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
+      FALLTHRU_EDGE (test_bb)->count = count;
+      probability = BRANCH_EDGE (test_bb)->probability;
+      BRANCH_EDGE (test_bb)->probability = FALLTHRU_EDGE (test_bb)->probability;
+      FALLTHRU_EDGE (test_bb)->probability = probability;
+    }
+
   /* Move the insns out of MERGE_BB to before the branch.  */
   if (head != NULL)
     {
diff --git a/gcc/rtl.h b/gcc/rtl.h
index 8c8a2db..e9227b1 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -1301,6 +1301,7 @@ extern rtx *find_constant_term_loc	PARAMS ((rtx *));
 
 /* In emit-rtl.c  */
 extern rtx try_split			PARAMS ((rtx, rtx, int));
+extern int split_branch_probability;
 
 /* In unknown file  */
 extern rtx split_insns			PARAMS ((rtx, rtx));