* loop-iv.c: New file.

	* Makefile.in (loop-iv.o): New.
	* basic_block.h (FOR_BB_INSNS, FOR_BB_INSNS_REVERSE): New macros.
	* cfgloop.c (fill_sons_in_loop, get_loop_body_in_dom_order,
	num_loop_branches): New functions.
	* cfgloop.h (get_loop_body_in_dom_order, num_loop_branches,
	iv_analysis_loop_init, iv_get_reaching_def, iv_analyse, get_iv_value,
	find_simple_exit, iv_number_of_iterations, iv_analysis_done,
	get_simple_loop_desc, free_simple_loop_desc): Declare.
	(simple_loop_desc): New inline function.
	(struct rtx_iv, struct niter_desc): New.
	* cfgloopmanip.c (loopify): Specify semantics more precisely.
	* expr.c (force_operand): Handle subregs of expressions created by
	loop unroller.
	* loop-init.c (loop_optimizer_init, loop_optimizer_finalize): Move
	parts of the initialization to toplev.c
	* loop-unroll.c (loop_exit_at_end_p): New.
	(unroll_and_peel_loops): Call iv_analysis_done.
	(decide_peel_once_rolling, decide_peel_completely,
	decide_unroll_stupid, decide_unroll_constant_iterations,
	decide_unroll_runtime_iterations, decide_peel_simple,
	peel_loop_simple, unroll_loop_stupid, unroll_loop_constant_iterations,
	unroll_loop_runtime_iterations): Use new simple loop analysis.
	* loop-unswitch.c (compare_and_jump_seq): New.
	(may_unswitch_on_p): Renamed to ...
	(may_unswitch_on): Use new iv analysis.
	(reversed_condition): Export.
	(unswitch_single_loop, unswitch_loop): Use new iv analysis.
	* predict.c (estimate_probability): Use new simple loop analysis.
	* rtl.h (get_mode_bounds, reversed_condition,compare_and_jump_seq,
	canon_condition, simplify_using_condition): Declare.
	* stor-layout.c (get_mode_bounds): New.
	* toplev.c (rest_of_handle_loop2): Some parts of
	initialization/finalization moved here from loop-init.c.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@77951 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 152 insertions, 78 deletions

diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c
index 40f0e830e4a..ebbabe82988 100644
--- a/gcc/loop-unswitch.c
+++ b/gcc/loop-unswitch.c
@@ -79,11 +79,63 @@ 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.  */
+      if (!cinsn)
+	abort ();
+      cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
+      if (GET_CODE (cond) != comp
+	  || !rtx_equal_p (op0, XEXP (cond, 0))
+	  || !rtx_equal_p (op1, XEXP (cond, 1)))
+	abort ();
+      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
+    {
+      if (cinsn)
+	abort ();
+
+      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 +163,82 @@ 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, insn, op[2];
+  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;
+    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;
+    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);
   if (!test)
-    return false;
+    return NULL_RTX;
+
+  for (i = 0; i < 2; i++)
+    {
+      op[i] = XEXP (test, i);
+
+      if (CONSTANT_P (op[i]))
+	continue;
+
+      insn = iv_get_reaching_def (at, op[i]);
+      if (!iv_analyse (insn, 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;
 
-  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;
+      *cinsn = BB_END (bb);
+      if (!rtx_equal_p (op[0], XEXP (test, 0))
+	  || !rtx_equal_p (op[1], XEXP (test, 1)))
+	return NULL_RTX;
 
-  return true;
+      return test;
+    }
+
+  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,13 +259,10 @@ 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, conds, rconds, acond, cinsn = NULL_RTX;
   int repeat;
   edge e;
 
@@ -237,8 +320,9 @@ unswitch_single_loop (struct loops *loops, struct loop *loop,
 
       /* 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 +331,26 @@ 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);
+      if (rcond)
+	rcond = canon_condition (rcond);
 
       /* Check whether the result can be predicted.  */
-      always_true = 0;
-      always_false = 0;
       for (acond = cond_checked; acond; acond = XEXP (acond, 1))
-	{
-	  if (rtx_equal_p (cond, XEXP (acond, 0)))
-	    {
-	      always_true = 1;
-	      break;
-	    }
-	  if (rtx_equal_p (rcond, XEXP (acond, 0)))
-	    {
-	      always_false = 1;
-	      break;
-	    }
-	}
+	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,21 +364,17 @@ 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");
 
   /* Unswitch the loop on this condition.  */
-  nloop = unswitch_loop (loops, loop, bb);
+  nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
   if (!nloop)
   abort ();
 
   /* 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)
@@ -316,17 +383,21 @@ unswitch_single_loop (struct loops *loops, struct loop *loop,
 
 /* 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;
+  edge entry, latch_edge, true_edge, false_edge, e;
   basic_block switch_bb, unswitch_on_alt, src;
   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))
@@ -343,12 +414,6 @@ unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on)
   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;
-
   entry = loop_preheader_edge (loop);
 
   /* Make a copy.  */
@@ -365,10 +430,24 @@ unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on)
 
   /* Record the block with condition we unswitch on.  */
   unswitch_on_alt = unswitch_on->rbi->copy;
+  true_edge = BRANCH_EDGE (unswitch_on_alt);
+  false_edge = FALLTHRU_EDGE (unswitch_on);
+  latch_edge = loop->latch->rbi->copy->succ;
+
+  /* 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;
@@ -381,19 +460,14 @@ unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on)
       switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
       switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
     }
-  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);
 
-  /* 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.  */