GCC 4.2.0 release.

1 files changed, 204 insertions, 126 deletions

diff --git a/contrib/gcc/loop-unswitch.c b/contrib/gcc/loop-unswitch.c
index 4cfaa2f..c76f481 100644
--- a/contrib/gcc/loop-unswitch.c
+++ b/contrib/gcc/loop-unswitch.c
@@ -1,5 +1,5 @@
 /* Loop unswitching for GNU compiler.
-   Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -15,8 +15,8 @@ for more details.
 
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING.  If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.  */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
 
 #include "config.h"
 #include "system.h"
@@ -24,6 +24,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "tm.h"
 #include "rtl.h"
 #include "hard-reg-set.h"
+#include "obstack.h"
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "cfglayout.h"
@@ -79,11 +80,60 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
   with handling this case.  */
 
 static struct loop *unswitch_loop (struct loops *, struct loop *,
-				   basic_block);
+				   basic_block, rtx, rtx);
 static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
-static bool may_unswitch_on_p (basic_block, struct loop *,
-			       basic_block *);
-static rtx reversed_condition (rtx);
+static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
+
+/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
+   true, with probability PROB.  If CINSN is not NULL, it is the insn to copy
+   in order to create a jump.  */
+
+rtx
+compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
+		      rtx cinsn)
+{
+  rtx seq, jump, cond;
+  enum machine_mode mode;
+
+  mode = GET_MODE (op0);
+  if (mode == VOIDmode)
+    mode = GET_MODE (op1);
+
+  start_sequence ();
+  if (GET_MODE_CLASS (mode) == MODE_CC)
+    {
+      /* A hack -- there seems to be no easy generic way how to make a
+	 conditional jump from a ccmode comparison.  */
+      gcc_assert (cinsn);
+      cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
+      gcc_assert (GET_CODE (cond) == comp);
+      gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
+      gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
+      emit_jump_insn (copy_insn (PATTERN (cinsn)));
+      jump = get_last_insn ();
+      JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
+      LABEL_NUSES (JUMP_LABEL (jump))++;
+      redirect_jump (jump, label, 0);
+    }
+  else
+    {
+      gcc_assert (!cinsn);
+
+      op0 = force_operand (op0, NULL_RTX);
+      op1 = force_operand (op1, NULL_RTX);
+      do_compare_rtx_and_jump (op0, op1, comp, 0,
+			       mode, NULL_RTX, NULL_RTX, label);
+      jump = get_last_insn ();
+      JUMP_LABEL (jump) = label;
+      LABEL_NUSES (label)++;
+    }
+  REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
+					REG_NOTES (jump));
+  seq = get_insns ();
+  end_sequence ();
+
+  return seq;
+}
 
 /* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
 void
@@ -111,48 +161,87 @@ unswitch_loops (struct loops *loops)
       verify_loop_structure (loops);
 #endif
     }
+
+  iv_analysis_done ();
 }
 
 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
-   basic blocks (for what it means see comments below).  List of basic blocks
-   inside LOOP is provided in BODY to save time.  */
-static bool
-may_unswitch_on_p (basic_block bb, struct loop *loop, basic_block *body)
+   basic blocks (for what it means see comments below).  In case condition
+   compares loop invariant cc mode register, return the jump in CINSN.  */
+
+static rtx
+may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
 {
-  rtx test;
+  rtx test, at, op[2], stest;
+  struct rtx_iv iv;
   unsigned i;
+  enum machine_mode mode;
 
   /* BB must end in a simple conditional jump.  */
-  if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
-    return false;
+  if (EDGE_COUNT (bb->succs) != 2)
+    return NULL_RTX;
   if (!any_condjump_p (BB_END (bb)))
-    return false;
+    return NULL_RTX;
 
   /* With branches inside loop.  */
-  if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
-      || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
-    return false;
+  if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
+      || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
+    return NULL_RTX;
 
   /* It must be executed just once each iteration (because otherwise we
      are unable to update dominator/irreducible loop information correctly).  */
   if (!just_once_each_iteration_p (loop, bb))
-    return false;
+    return NULL_RTX;
 
-  /* Condition must be invariant.  We use just a stupid test of invariantness
-     of the condition: all used regs must not be modified inside loop body.  */
-  test = get_condition (BB_END (bb), NULL, true);
+  /* Condition must be invariant.  */
+  test = get_condition (BB_END (bb), &at, true, false);
   if (!test)
-    return false;
+    return NULL_RTX;
+
+  for (i = 0; i < 2; i++)
+    {
+      op[i] = XEXP (test, i);
+
+      if (CONSTANT_P (op[i]))
+	continue;
+
+      if (!iv_analyze (at, op[i], &iv))
+	return NULL_RTX;
+      if (iv.step != const0_rtx
+	  || iv.first_special)
+	return NULL_RTX;
+
+      op[i] = get_iv_value (&iv, const0_rtx);
+    }
+
+  mode = GET_MODE (op[0]);
+  if (mode == VOIDmode)
+    mode = GET_MODE (op[1]);
+  if (GET_MODE_CLASS (mode) == MODE_CC)
+    {
+      if (at != BB_END (bb))
+	return NULL_RTX;
+
+      if (!rtx_equal_p (op[0], XEXP (test, 0))
+	  || !rtx_equal_p (op[1], XEXP (test, 1)))
+	return NULL_RTX;
+
+      *cinsn = BB_END (bb);
+      return test;
+    }
 
-  for (i = 0; i < loop->num_nodes; i++)
-    if (modified_between_p (test, BB_HEAD (body[i]), NEXT_INSN (BB_END (body[i]))))
-      return false;
+  stest = simplify_gen_relational (GET_CODE (test), SImode,
+				   mode, op[0], op[1]);
+  if (stest == const0_rtx
+      || stest == const_true_rtx)
+    return stest;
 
-  return true;
+  return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
+					  op[0], op[1]));
 }
 
 /* Reverses CONDition; returns NULL if we cannot.  */
-static rtx
+rtx
 reversed_condition (rtx cond)
 {
   enum rtx_code reversed;
@@ -173,72 +262,71 @@ static void
 unswitch_single_loop (struct loops *loops, struct loop *loop,
 		      rtx cond_checked, int num)
 {
-  basic_block *bbs, bb;
+  basic_block *bbs;
   struct loop *nloop;
   unsigned i;
-  int true_first;
-  rtx cond, rcond, conds, rconds, acond, split_before;
-  int always_true;
-  int always_false;
+  rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
   int repeat;
   edge e;
 
   /* Do not unswitch too much.  */
   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching anymore, hit max level\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
       return;
     }
 
   /* Only unswitch innermost loops.  */
   if (loop->inner)
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
       return;
     }
 
   /* We must be able to duplicate loop body.  */
   if (!can_duplicate_loop_p (loop))
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching, can't duplicate loop\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
       return;
     }
 
   /* The loop should not be too large, to limit code growth.  */
   if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching, loop too big\n");
       return;
     }
 
   /* Do not unswitch in cold areas.  */
   if (!maybe_hot_bb_p (loop->header))
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching, not hot area\n");
       return;
     }
 
   /* Nor if the loop usually does not roll.  */
   if (expected_loop_iterations (loop) < 1)
     {
-      if (rtl_dump_file)
-	fprintf (rtl_dump_file, ";; Not unswitching, loop iterations < 1\n");
+      if (dump_file)
+	fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
       return;
     }
 
   do
     {
       repeat = 0;
+      cinsn = NULL_RTX;
 
       /* Find a bb to unswitch on.  */
       bbs = get_loop_body (loop);
+      iv_analysis_loop_init (loop);
       for (i = 0; i < loop->num_nodes; i++)
-	if (may_unswitch_on_p (bbs[i], loop, bbs))
+	if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
 	  break;
 
       if (i == loop->num_nodes)
@@ -247,39 +335,30 @@ unswitch_single_loop (struct loops *loops, struct loop *loop,
 	  return;
 	}
 
-      if (!(cond = get_condition (BB_END (bbs[i]), &split_before, true)))
-	abort ();
-      rcond = reversed_condition (cond);
-
-      /* Check whether the result can be predicted.  */
-      always_true = 0;
-      always_false = 0;
-      for (acond = cond_checked; acond; acond = XEXP (acond, 1))
+      if (cond != const0_rtx
+	  && cond != const_true_rtx)
 	{
-	  if (rtx_equal_p (cond, XEXP (acond, 0)))
-	    {
-	      always_true = 1;
-	      break;
-	    }
-	  if (rtx_equal_p (rcond, XEXP (acond, 0)))
-	    {
-	      always_false = 1;
-	      break;
-	    }
+	  rcond = reversed_condition (cond);
+	  if (rcond)
+	    rcond = canon_condition (rcond);
+
+	  /* Check whether the result can be predicted.  */
+	  for (acond = cond_checked; acond; acond = XEXP (acond, 1))
+	    simplify_using_condition (XEXP (acond, 0), &cond, NULL);
 	}
 
-      if (always_true)
+      if (cond == const_true_rtx)
 	{
 	  /* Remove false path.  */
-	  for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
+	  e = FALLTHRU_EDGE (bbs[i]);
 	  remove_path (loops, e);
 	  free (bbs);
 	  repeat = 1;
 	}
-      else if (always_false)
+      else if (cond == const0_rtx)
 	{
 	  /* Remove true path.  */
-	  for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
+	  e = BRANCH_EDGE (bbs[i]);
 	  remove_path (loops, e);
 	  free (bbs);
 	  repeat = 1;
@@ -293,108 +372,107 @@ unswitch_single_loop (struct loops *loops, struct loop *loop,
   else
     rconds = cond_checked;
 
-  /* Separate condition in a single basic block.  */
-  bb = split_loop_bb (bbs[i], PREV_INSN (split_before))->dest;
-  free (bbs);
-  true_first = !(bb->succ->flags & EDGE_FALLTHRU);
-  if (rtl_dump_file)
-    fprintf (rtl_dump_file, ";; Unswitching loop\n");
+  if (dump_file)
+    fprintf (dump_file, ";; Unswitching loop\n");
 
   /* Unswitch the loop on this condition.  */
-  nloop = unswitch_loop (loops, loop, bb);
-  if (!nloop)
-  abort ();
+  nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
+  gcc_assert (nloop);
 
   /* Invoke itself on modified loops.  */
-  unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1);
-  unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1);
+  unswitch_single_loop (loops, nloop, rconds, num + 1);
+  unswitch_single_loop (loops, loop, conds, num + 1);
 
   free_EXPR_LIST_node (conds);
   if (rcond)
     free_EXPR_LIST_node (rconds);
+
+  free (bbs);
 }
 
 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
    unswitching of innermost loops.  UNSWITCH_ON must be executed in every
-   iteration, i.e. it must dominate LOOP latch, and should only contain code
-   for the condition we unswitch on.  Returns NULL if impossible, new
-   loop otherwise.  */
+   iteration, i.e. it must dominate LOOP latch.  COND is the condition
+   determining which loop is entered.  Returns NULL if impossible, new loop
+   otherwise.  The new loop is entered if COND is true.  If CINSN is not
+   NULL, it is the insn in that COND is compared.  */
+
 static struct loop *
-unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on)
+unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
+	       rtx cond, rtx cinsn)
 {
-  edge entry, latch_edge;
-  basic_block switch_bb, unswitch_on_alt, src;
+  edge entry, latch_edge, true_edge, false_edge, e;
+  basic_block switch_bb, unswitch_on_alt;
   struct loop *nloop;
   sbitmap zero_bitmap;
-  int irred_flag;
+  int irred_flag, prob;
+  rtx seq;
 
   /* Some sanity checking.  */
-  if (!flow_bb_inside_loop_p (loop, unswitch_on))
-    abort ();
-  if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
-      unswitch_on->succ->succ_next->succ_next)
-    abort ();
-  if (!just_once_each_iteration_p (loop, unswitch_on))
-    abort ();
-  if (loop->inner)
-    abort ();
-  if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest))
-    abort ();
-  if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest))
-    abort ();
-
-  /* Will we be able to perform redirection?  */
-  if (!any_condjump_p (BB_END (unswitch_on)))
-    return NULL;
-  if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
-    return NULL;
+  gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
+  gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
+  gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
+  gcc_assert (!loop->inner);
+  gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
+  gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
 
   entry = loop_preheader_edge (loop);
 
   /* Make a copy.  */
-  src = entry->src;
   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
   zero_bitmap = sbitmap_alloc (2);
   sbitmap_zero (zero_bitmap);
   if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
 	zero_bitmap, NULL, NULL, NULL, 0))
-    return NULL;
-  free (zero_bitmap);
+    {
+      sbitmap_free (zero_bitmap);
+      return NULL;
+    }
+  sbitmap_free (zero_bitmap);
   entry->flags |= irred_flag;
 
   /* Record the block with condition we unswitch on.  */
-  unswitch_on_alt = unswitch_on->rbi->copy;
+  unswitch_on_alt = get_bb_copy (unswitch_on);
+  true_edge = BRANCH_EDGE (unswitch_on_alt);
+  false_edge = FALLTHRU_EDGE (unswitch_on);
+  latch_edge = single_succ_edge (get_bb_copy (loop->latch));
+
+  /* Create a block with the condition.  */
+  prob = true_edge->probability;
+  switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+  seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
+			      block_label (true_edge->dest),
+			      prob, cinsn);
+  emit_insn_after (seq, BB_END (switch_bb));
+  e = make_edge (switch_bb, true_edge->dest, 0);
+  e->probability = prob;
+  e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
+  e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
+  e->probability = false_edge->probability;
+  e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
 
-  /* Make a copy of the block containing the condition; we will use
-     it as switch to decide which loop we want to use.  */
-  switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
   if (irred_flag)
     {
       switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
-      switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
-      switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP;
+      EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
+      EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
     }
   else
     {
       switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
-      switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
-      switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+      EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+      EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
     }
-  add_to_dominance_info (CDI_DOMINATORS, switch_bb);
-  unswitch_on->rbi->copy = unswitch_on_alt;
 
   /* Loopify from the copy of LOOP body, constructing the new loop.  */
-  for (latch_edge = loop->latch->rbi->copy->succ;
-       latch_edge->dest != loop->header;
-       latch_edge = latch_edge->succ_next);
   nloop = loopify (loops, latch_edge,
-		   loop->header->rbi->copy->pred, switch_bb);
+		   single_pred_edge (get_bb_copy (loop->header)), switch_bb,
+		   BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true);
 
-  /* Remove branches that are now unreachable in new loops.  We rely on the
-     fact that cfg_layout_duplicate_bb reverses list of edges.  */
-  remove_path (loops, unswitch_on->succ);
-  remove_path (loops, unswitch_on_alt->succ);
+  /* Remove branches that are now unreachable in new loops.  */
+  remove_path (loops, true_edge);
+  remove_path (loops, false_edge);
 
   /* One of created loops do not have to be subloop of the outer loop now,
      so fix its placement in loop data structure.  */