[PATCH][RFC] Teach more transformations in ifcvt.c how to update the CFG

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

Hi,

This is an "upgrade" of yesterday's patch.  This time I've updated all
functions not related to conditional execution to update the CFG instead
if relying on merge_if_block.

There is one additional change, namely that I need simple jumps at the
end of the THEN and ELSE blocks.  I think if-conversion would currently
produce wrong code if the jumps would not be simple: merge_if_block is
not looking at jumps with side-effects at all, and merge_blocks just
removes the jump.  So this shouldn't have any negative effects for the
pass at all, it just tightens the checks a bit.

This was bootstrapped and tested on {ia64,x86_64}-unknown-linux-gnu.
I don't ask for approval yet because I want to look into the generated
code a bit first.  I'm not expecting any changes, but I want to be sure
that this doesn't cause us to miss optimization opportunities.
I'll probably submit the final patch next week-end.  Comments on the
patch are welcome in the mean time!

When this patch goes in, we should be able to run the compiler in
cfglayout mode from pass_initial_value_sets up to pass_combine.  I am
not sure yet whether combine could work in cfglayout mode too, but I
doubt it will without changes.  That'll be next on my list.

Thanks for looking at the patch and for any suggested improvements!

Gr.
Steven

	* ifcvt.c (struct noce_if_info): Add comments to the fields.
	(noce_process_if_block): Do not use merge_if_blocks.  Update
	the CFG here.
	(cond_move_process_if_block): Likewise.
	(find_cond_trap): Likewise.
	(check_cond_move_block): Require simple jump insns at the end
	of the basic block.

Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 120546)
+++ ifcvt.c	(working copy)
@@ -596,11 +596,35 @@ cond_exec_process_if_block (ce_if_block_
 
 struct noce_if_info
 {
+  /* A basic block that ends in a simple conditional jump.  */
   basic_block test_bb;
+
+  /* The jump that ends TEST_BB.  */
+  rtx jump;
+ 
+  /* The jump condition.  */
+  rtx cond;
+
+  /* New insns should be inserted before this one.  */
+  rtx cond_earliest;
+
+  /* Insns in the THEN and ELSE block.  There is always just this
+     one insns in those blocks.  The insns are single_set insns.
+     If there was no ELSE block, INSN_B is the last insn before
+     COND_EARLIEST, or NULL_RTX.  In the former case, the insn
+     operands are still valid, as if INSN_B was moved down below
+     the jump.  */
   rtx insn_a, insn_b;
-  rtx x, a, b;
-  rtx jump, cond, cond_earliest;
-  /* True if "b" was originally evaluated unconditionally.  */
+
+  /* The SET_SRC of INSN_A and INSN_B.  */
+  rtx a, b;
+
+  /* The SET_DEST of INSN_A.  */
+  rtx x;
+
+  /* True if "b" was originally evaluated unconditionally.
+     ??? This is the same as saying there is no ELSE block.  In this
+	 case, INSN_B must be taken from TEST_BB.  Eliminate this field!  */
   bool b_unconditional;
 };
 
@@ -2173,6 +2200,7 @@ noce_process_if_block (struct ce_if_bloc
   basic_block test_bb = ce_info->test_bb;	/* test block */
   basic_block then_bb = ce_info->then_bb;	/* THEN */
   basic_block else_bb = ce_info->else_bb;	/* ELSE or NULL */
+  basic_block join_bb;
   struct noce_if_info if_info;
   rtx insn_a, insn_b;
   rtx set_a, set_b;
@@ -2364,39 +2392,47 @@ noce_process_if_block (struct ce_if_bloc
   return FALSE;
 
  success:
-  /* The original sets may now be killed.  */
-  delete_insn (insn_a);
-
-  /* Several special cases here: First, we may have reused insn_b above,
-     in which case insn_b is now NULL.  Second, we want to delete insn_b
-     if it came from the ELSE block, because follows the now correct
-     write that appears in the TEST block.  However, if we got insn_b from
-     the TEST block, it may in fact be loading data needed for the comparison.
-     We'll let life_analysis remove the insn if it's really dead.  */
-  if (insn_b && else_bb)
-    delete_insn (insn_b);
-
-  /* The new insns will have been inserted immediately before the jump.  We
-     should be able to remove the jump with impunity, but the condition itself
-     may have been modified by gcse to be shared across basic blocks.  */
-  delete_insn (jump);
 
   /* If we used a temporary, fix it up now.  */
   if (orig_x != x)
     {
+      rtx seq;
+
       start_sequence ();
       noce_emit_move_insn (orig_x, x);
-      insn_b = get_insns ();
+      seq = get_insns ();
       set_used_flags (orig_x);
-      unshare_all_rtl_in_chain (insn_b);
+      unshare_all_rtl_in_chain (seq);
       end_sequence ();
 
-      emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a));
+      emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a));
     }
 
-  /* Merge the blocks!  */
-  merge_if_block (ce_info);
+  /* The original THEN and ELSE blocks may now be removed.  The test block
+     must now jump to the join block.  If the test block and the join block
+     can be merged, do so.  */
 
+  join_bb = single_succ (then_bb);
+  if (else_bb)
+    {
+      delete_basic_block (else_bb);
+      num_true_changes++;
+    }
+  else
+    remove_edge (find_edge (test_bb, join_bb));
+
+  remove_edge (find_edge (then_bb, join_bb));
+  redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
+  delete_basic_block (then_bb);
+  num_true_changes++;
+  
+  if (can_merge_blocks_p (test_bb, join_bb))
+    {
+      merge_blocks (test_bb, join_bb);
+      num_true_changes++;
+    }
+
+  num_updated_if_blocks++;
   return TRUE;
 }
 
@@ -2463,6 +2499,12 @@ check_cond_move_block (basic_block bb, r
 	return FALSE;
     }
 
+  /* We can only handle simple jumps at the end of the basic block.
+     It is almost impossible to update the CFG otherwise.  */
+  insn = BB_END (bb);
+  if (JUMP_P (insn) && ! onlyjump_p (insn))
+    return FALSE;
+  
   return TRUE;
 }
 
@@ -2537,10 +2579,12 @@ cond_move_convert_if_block (struct noce_
 static int
 cond_move_process_if_block (struct ce_if_block *ce_info)
 {
+  basic_block test_bb = ce_info->test_bb;
   basic_block then_bb = ce_info->then_bb;
   basic_block else_bb = ce_info->else_bb;
+  basic_block join_bb;
   struct noce_if_info if_info;
-  rtx jump, cond, insn, seq, loc_insn;
+  rtx jump, cond, seq, loc_insn;
   int max_reg, size, c, i;
   rtx *then_vals;
   rtx *else_vals;
@@ -2624,21 +2668,30 @@ cond_move_process_if_block (struct ce_if
     }
   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
 
-  FOR_BB_INSNS (then_bb, insn)
-    if (INSN_P (insn) && !JUMP_P (insn))
-      delete_insn (insn);
+  join_bb = single_succ (then_bb);
   if (else_bb)
     {
-      FOR_BB_INSNS (else_bb, insn)
-	if (INSN_P (insn) && !JUMP_P (insn))
-	  delete_insn (insn);
+      delete_basic_block (else_bb);
+      num_true_changes++;
     }
-  delete_insn (jump);
+  else
+    remove_edge (find_edge (test_bb, join_bb));
 
-  merge_if_block (ce_info);
+  remove_edge (find_edge (then_bb, join_bb));
+  redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
+  delete_basic_block (then_bb);
+  num_true_changes++;
+  
+  if (can_merge_blocks_p (test_bb, join_bb))
+    {
+      merge_blocks (test_bb, join_bb);
+      num_true_changes++;
+    }
 
+  num_updated_if_blocks++;
   return TRUE;
 }
+
 
 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
    straight line code.  Return true if successful.  */
@@ -3201,29 +3254,20 @@ find_cond_trap (basic_block test_bb, edg
   if (seq == NULL)
     return FALSE;
 
-  num_true_changes++;
-
   /* Emit the new insns before cond_earliest.  */
   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
 
   /* Delete the trap block if possible.  */
   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
   if (EDGE_COUNT (trap_bb->preds) == 0)
-    delete_basic_block (trap_bb);
-
-  /* If the non-trap block and the test are now adjacent, merge them.
-     Otherwise we must insert a direct branch.  */
-  if (test_bb->next_bb == other_bb)
     {
-      struct ce_if_block new_ce_info;
-      delete_insn (jump);
-      memset (&new_ce_info, '\0', sizeof (new_ce_info));
-      new_ce_info.test_bb = test_bb;
-      new_ce_info.then_bb = NULL;
-      new_ce_info.else_bb = NULL;
-      new_ce_info.join_bb = other_bb;
-      merge_if_block (&new_ce_info);
+      delete_basic_block (trap_bb);
+      num_true_changes++;
     }
+
+  /* Wire together the blocks again.  */
+  if (current_ir_type () == IR_RTL_CFGLAYOUT)
+    single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
   else
     {
       rtx lab, newjump;
@@ -3233,10 +3277,16 @@ find_cond_trap (basic_block test_bb, edg
       LABEL_NUSES (lab) += 1;
       JUMP_LABEL (newjump) = lab;
       emit_barrier_after (newjump);
+    }
+  delete_insn (jump);
 
-      delete_insn (jump);
+  if (can_merge_blocks_p (test_bb, other_bb))
+    {
+      merge_blocks (test_bb, other_bb);
+      num_true_changes++;
     }
 
+  num_updated_if_blocks++;
   return TRUE;
 }