bfin.c: Include "cfglayout.h".

	* config/bfin/bfin.c: Include "cfglayout.h".
	(MAX_LSETUP_DISTANCE): New macro.
	(struct loop_info): New members incoming, incoming_src and
	incoming_dest.  Delete member predecessor.
	(length_for_loop): New function.
	(bfin_optimize_loop): Handle more different loop structures.
	(bfin_discover_loop): Rework detection of predecessor blocks by
	examining incoming edges.
	(bfin_discover_loops, bfin_free_loops): New functions, broken out of
	bfin_reorg_loops.
	(bfin_reorder_loops): New function.
	(bfin_reorg_loops): Use these three new functions.

From-SVN: r122372

2 files changed, 340 insertions, 86 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2de3d70..51c99a6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -2,6 +2,19 @@
 
 	* config/bfin/bfin.md (doloop_end): FAIL if counter reg isn't SImode.
 
+	* config/bfin/bfin.c: Include "cfglayout.h".
+	(MAX_LSETUP_DISTANCE): New macro.
+	(struct loop_info): New members incoming, incoming_src and
+	incoming_dest.  Delete member predecessor.
+	(length_for_loop): New function.
+	(bfin_optimize_loop): Handle more different loop structures.
+	(bfin_discover_loop): Rework detection of predecessor blocks by
+	examining incoming edges.
+	(bfin_discover_loops, bfin_free_loops): New functions, broken out of
+	bfin_reorg_loops.
+	(bfin_reorder_loops): New function.
+	(bfin_reorg_loops): Use these three new functions.
+
 2007-02-27  Andreas Schwab  <schwab@suse.de>
 
 	* Makefile.in (TEXI_GCCINSTALL_FILES): Add gcc-common.texi.
diff --git a/gcc/config/bfin/bfin.c b/gcc/config/bfin/bfin.c
index e71305a..12212b2 100644
--- a/gcc/config/bfin/bfin.c
+++ b/gcc/config/bfin/bfin.c
@@ -52,6 +52,7 @@
 #include "tm-preds.h"
 #include "gt-bfin.h"
 #include "basic-block.h"
+#include "cfglayout.h"
 #include "timevar.h"
 
 /* A C structure for machine-specific, per-function data.
@@ -3025,6 +3026,9 @@ bfin_hardware_loop (void)
 /* Maximum size of a loop.  */
 #define MAX_LOOP_LENGTH 2042
 
+/* Maximum distance of the LSETUP instruction from the loop start.  */
+#define MAX_LSETUP_DISTANCE 30
+
 /* We need to keep a vector of loops */
 typedef struct loop_info *loop_info;
 DEF_VEC_P (loop_info);
@@ -3037,9 +3041,16 @@ struct loop_info GTY (())
   /* loop number, for dumps */
   int loop_no;
 
-  /* Predecessor block of the loop.   This is the one that falls into
-     the loop and contains the initialization instruction.  */
-  basic_block predecessor;
+  /* All edges that jump into and out of the loop.  */
+  VEC(edge,gc) *incoming;
+
+  /* We can handle two cases: all incoming edges have the same destination
+     block, or all incoming edges have the same source block.  These two
+     members are set to the common source or destination we found, or NULL
+     if different blocks were found.  If both are NULL the loop can't be
+     optimized.  */
+  basic_block incoming_src;
+  basic_block incoming_dest;
 
   /* First block in the loop.  This is the one branched to by the loop_end
      insn.  */
@@ -3175,6 +3186,31 @@ bfin_scan_loop (loop_info loop, rtx reg, rtx loop_end)
   return false;
 }
 
+/* Estimate the length of INSN conservatively.  */
+
+static int
+length_for_loop (rtx insn)
+{
+  int length = 0;
+  if (JUMP_P (insn) && any_condjump_p (insn) && !optimize_size)
+    {
+      if (TARGET_CSYNC_ANOMALY)
+	length = 8;
+      else if (TARGET_SPECLD_ANOMALY)
+	length = 6;
+    }
+  else if (LABEL_P (insn))
+    {
+      if (TARGET_CSYNC_ANOMALY)
+	length = 4;
+    }
+
+  if (INSN_P (insn))
+    length += get_attr_length (insn);
+
+  return length;
+}
+
 /* Optimize LOOP.  */
 
 static void
@@ -3187,7 +3223,7 @@ bfin_optimize_loop (loop_info loop)
   rtx reg_lc0, reg_lc1, reg_lt0, reg_lt1, reg_lb0, reg_lb1;
   rtx iter_reg;
   rtx lc_reg, lt_reg, lb_reg;
-  rtx seq;
+  rtx seq, seq_end;
   int length;
   unsigned ix;
   int inner_depth = 0;
@@ -3239,6 +3275,32 @@ bfin_optimize_loop (loop_info loop)
       goto bad_loop;
     }
 
+  if (loop->incoming_src)
+    {
+      /* Make sure the predecessor is before the loop start label, as required by
+	 the LSETUP instruction.  */
+      length = 0;
+      for (insn = BB_END (loop->incoming_src);
+	   insn && insn != loop->start_label;
+	   insn = NEXT_INSN (insn))
+	length += length_for_loop (insn);
+      
+      if (!insn)
+	{
+	  if (dump_file)
+	    fprintf (dump_file, ";; loop %d lsetup not before loop_start\n",
+		     loop->loop_no);
+	  goto bad_loop;
+	}
+
+      if (length > MAX_LSETUP_DISTANCE)
+	{
+	  if (dump_file)
+	    fprintf (dump_file, ";; loop %d lsetup too far away\n", loop->loop_no);
+	  goto bad_loop;
+	}
+    }
+
   /* Check if start_label appears before loop_end and calculate the
      offset between them.  We calculate the length of instructions
      conservatively.  */
@@ -3246,23 +3308,7 @@ bfin_optimize_loop (loop_info loop)
   for (insn = loop->start_label;
        insn && insn != loop->loop_end;
        insn = NEXT_INSN (insn))
-    {
-      if (JUMP_P (insn) && any_condjump_p (insn) && !optimize_size)
-	{
-	  if (TARGET_CSYNC_ANOMALY)
-	    length += 8;
-	  else if (TARGET_SPECLD_ANOMALY)
-	    length += 6;
-	}
-      else if (LABEL_P (insn))
-	{
-	  if (TARGET_CSYNC_ANOMALY)
-	    length += 4;
-	}
-
-      if (INSN_P (insn))
-	length += get_attr_length (insn);
-    }
+    length += length_for_loop (insn);
 
   if (!insn)
     {
@@ -3472,21 +3518,64 @@ bfin_optimize_loop (loop_info loop)
 
   if (loop->init != NULL_RTX)
     emit_insn (loop->init);
-  emit_insn(loop->loop_init);
-  emit_label (loop->start_label);
+  seq_end = emit_insn (loop->loop_init);
 
   seq = get_insns ();
   end_sequence ();
 
-  emit_insn_after (seq, BB_END (loop->predecessor));
-  delete_insn (loop->loop_end);
+  if (loop->incoming_src)
+    {
+      rtx prev = BB_END (loop->incoming_src);
+      if (VEC_length (edge, loop->incoming) > 1
+	  || !(VEC_last (edge, loop->incoming)->flags & EDGE_FALLTHRU))
+	{
+	  gcc_assert (JUMP_P (prev));
+	  prev = PREV_INSN (prev);
+	}
+      emit_insn_after (seq, prev);
+    }
+  else
+    {
+      basic_block new_bb;
+      edge e;
+      edge_iterator ei;
+      
+      if (loop->head != loop->incoming_dest)
+	{
+	  FOR_EACH_EDGE (e, ei, loop->head->preds)
+	    {
+	      if (e->flags & EDGE_FALLTHRU)
+		{
+		  rtx newjump = gen_jump (loop->start_label);
+		  emit_insn_before (newjump, BB_HEAD (loop->head));
+		  new_bb = create_basic_block (newjump, newjump, loop->head->prev_bb);
+		  gcc_assert (new_bb = loop->head->prev_bb);
+		  break;
+		}
+	    }
+	}
+
+      emit_insn_before (seq, BB_HEAD (loop->head));
+      seq = emit_label_before (gen_label_rtx (), seq);
 
+      new_bb = create_basic_block (seq, seq_end, loop->head->prev_bb);
+      FOR_EACH_EDGE (e, ei, loop->incoming)
+	{
+	  if (!(e->flags & EDGE_FALLTHRU)
+	      || e->dest != loop->head)
+	    redirect_edge_and_branch_force (e, new_bb);
+	  else
+	    redirect_edge_succ (e, new_bb);
+	}
+    }
+  
+  delete_insn (loop->loop_end);
   /* Insert the loop end label before the last instruction of the loop.  */
   emit_label_before (loop->end_label, loop->last_insn);
 
   return;
 
-bad_loop:
+ bad_loop:
 
   if (dump_file)
     fprintf (dump_file, ";; loop %d is bad\n", loop->loop_no);
@@ -3531,7 +3620,6 @@ bfin_discover_loop (loop_info loop, basic_block tail_bb, rtx tail_insn)
   loop->tail = tail_bb;
   loop->head = BRANCH_EDGE (tail_bb)->dest;
   loop->successor = FALLTHRU_EDGE (tail_bb)->dest;
-  loop->predecessor = NULL;
   loop->loop_end = tail_insn;
   loop->last_insn = NULL_RTX;
   loop->iter_reg = SET_DEST (XVECEXP (PATTERN (tail_insn), 0, 1));
@@ -3540,7 +3628,7 @@ bfin_discover_loop (loop_info loop, basic_block tail_bb, rtx tail_insn)
   loop->clobber_loop0 = loop->clobber_loop1 = 0;
   loop->outer = NULL;
   loop->loops = NULL;
-
+  loop->incoming = VEC_alloc (edge, gc, 2);
   loop->init = loop->loop_init = NULL_RTX;
   loop->start_label = XEXP (XEXP (SET_SRC (XVECEXP (PATTERN (tail_insn), 0, 0)), 1), 0);
   loop->end_label = NULL_RTX;
@@ -3594,69 +3682,113 @@ bfin_discover_loop (loop_info loop, basic_block tail_bb, rtx tail_insn)
 	}
     }
 
+  /* Find the predecessor, and make sure nothing else jumps into this loop.  */
   if (!loop->bad)
     {
-      /* Make sure we only have one entry point.  */
-      if (EDGE_COUNT (loop->head->preds) == 2)
+      int pass, retry;
+      for (dwork = 0; VEC_iterate (basic_block, loop->blocks, dwork, bb); dwork++)
 	{
-	  loop->predecessor = EDGE_PRED (loop->head, 0)->src;
-	  if (loop->predecessor == loop->tail)
-	    /* We wanted the other predecessor.  */
-	    loop->predecessor = EDGE_PRED (loop->head, 1)->src;
-
-	  /* We can only place a loop insn on a fall through edge of a
-	     single exit block.  */
-	  if (EDGE_COUNT (loop->predecessor->succs) != 1
-	      || !(EDGE_SUCC (loop->predecessor, 0)->flags & EDGE_FALLTHRU)
-	      /* If loop->predecessor is in loop, loop->head is not really
-		 the head of the loop.  */
-	      || bfin_bb_in_loop (loop, loop->predecessor))
-	    loop->predecessor = NULL;
+	  edge e;
+	  edge_iterator ei;
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    {
+	      basic_block pred = e->src;
+
+	      if (!bfin_bb_in_loop (loop, pred))
+		{
+		  if (dump_file)
+		    fprintf (dump_file, ";; Loop %d: incoming edge %d -> %d\n",
+			     loop->loop_no, pred->index,
+			     e->dest->index);
+		  VEC_safe_push (edge, gc, loop->incoming, e);
+		}
+	    }
 	}
 
-      if (loop->predecessor == NULL)
+      for (pass = 0, retry = 1; retry && pass < 2; pass++)
 	{
-	  if (dump_file)
-	    fprintf (dump_file, ";; loop has bad predecessor\n");
-	  loop->bad = 1;
+	  edge e;
+	  edge_iterator ei;
+	  bool first = true;
+	  retry = 0;
+
+	  FOR_EACH_EDGE (e, ei, loop->incoming)
+	    {
+	      if (first)
+		{
+		  loop->incoming_src = e->src;
+		  loop->incoming_dest = e->dest;
+		  first = false;
+		}
+	      else
+		{
+		  if (e->dest != loop->incoming_dest)
+		    loop->incoming_dest = NULL;
+		  if (e->src != loop->incoming_src)
+		    loop->incoming_src = NULL;
+		}
+	      if (loop->incoming_src == NULL && loop->incoming_dest == NULL)
+		{
+		  if (pass == 0)
+		    {
+		      if (dump_file)
+			fprintf (dump_file,
+				 ";; retrying loop %d with forwarder blocks\n",
+				 loop->loop_no);
+		      retry = 1;
+		      break;
+		    }
+		  loop->bad = 1;
+		  if (dump_file)
+		    fprintf (dump_file,
+			     ";; can't find suitable entry for loop %d\n",
+			     loop->loop_no);
+		  goto out;
+		}
+	    }
+	  if (retry)
+	    {
+	      retry = 0;
+	      FOR_EACH_EDGE (e, ei, loop->incoming)
+		{
+		  if (forwarder_block_p (e->src))
+		    {
+		      edge e2;
+		      edge_iterator ei2;
+
+		      if (dump_file)
+			fprintf (dump_file,
+				 ";; Adding forwarder block %d to loop %d and retrying\n",
+				 e->src->index, loop->loop_no);
+		      VEC_safe_push (basic_block, heap, loop->blocks, e->src);
+		      bitmap_set_bit (loop->block_bitmap, e->src->index);
+		      FOR_EACH_EDGE (e2, ei2, e->src->preds)
+			VEC_safe_push (edge, gc, loop->incoming, e2);
+		      VEC_unordered_remove (edge, loop->incoming, ei.index);
+		      retry = 1;
+		      break;
+		    }
+		}
+	    }
 	}
     }
 
-#ifdef ENABLE_CHECKING
-  /* Make sure nothing jumps into this loop.  This shouldn't happen as we
-     wouldn't have generated the counted loop patterns in such a case.
-     However, this test must be done after the test above to detect loops
-     with invalid headers.  */
-  if (!loop->bad)
-    for (dwork = 0; VEC_iterate (basic_block, loop->blocks, dwork, bb); dwork++)
-      {
-	edge e;
-	edge_iterator ei;
-	if (bb == loop->head)
-	  continue;
-	FOR_EACH_EDGE (e, ei, bb->preds)
-	  {
-	    basic_block pred = EDGE_PRED (bb, ei.index)->src;
-	    if (!bfin_bb_in_loop (loop, pred))
-	      abort ();
-	  }
-      }
-#endif
+ out:
   VEC_free (basic_block, heap, works);
 }
 
-static void
-bfin_reorg_loops (FILE *dump_file)
+/* Analyze the structure of the loops in the current function.  Use STACK
+   for bitmap allocations.  Returns all the valid candidates for hardware
+   loops found in this function.  */
+static loop_info
+bfin_discover_loops (bitmap_obstack *stack, FILE *dump_file)
 {
-  bitmap_obstack stack;
-  bitmap tmp_bitmap;
-  basic_block bb;
   loop_info loops = NULL;
   loop_info loop;
+  basic_block bb;
+  bitmap tmp_bitmap;
   int nloops = 0;
 
-  bitmap_obstack_initialize (&stack);
-
   /* Find all the possible loop tails.  This means searching for every
      loop_end instruction.  For each one found, create a loop_info
      structure and add the head block to the work list. */
@@ -3678,7 +3810,7 @@ bfin_reorg_loops (FILE *dump_file)
 	  loops = loop;
 	  loop->loop_no = nloops++;
 	  loop->blocks = VEC_alloc (basic_block, heap, 20);
-	  loop->block_bitmap = BITMAP_ALLOC (&stack);
+	  loop->block_bitmap = BITMAP_ALLOC (stack);
 	  bb->aux = loop;
 
 	  if (dump_file)
@@ -3692,7 +3824,7 @@ bfin_reorg_loops (FILE *dump_file)
 	}
     }
 
-  tmp_bitmap = BITMAP_ALLOC (&stack);
+  tmp_bitmap = BITMAP_ALLOC (stack);
   /* Compute loop nestings.  */
   for (loop = loops; loop; loop = loop->next)
     {
@@ -3720,12 +3852,130 @@ bfin_reorg_loops (FILE *dump_file)
 	    }
 	  else
 	    {
+	      if (dump_file)
+		fprintf (dump_file,
+			 ";; can't find suitable nesting for loops %d and %d\n",
+			 loop->loop_no, other->loop_no);
 	      loop->bad = other->bad = 1;
 	    }
 	}
     }
   BITMAP_FREE (tmp_bitmap);
 
+  return loops;
+}
+
+/* Free up the loop structures in LOOPS.  */
+static void
+free_loops (loop_info loops)
+{
+  while (loops)
+    {
+      loop_info loop = loops;
+      loops = loop->next;
+      VEC_free (loop_info, heap, loop->loops);
+      VEC_free (basic_block, heap, loop->blocks);
+      BITMAP_FREE (loop->block_bitmap);
+      XDELETE (loop);
+    }
+}
+
+#define BB_AUX_INDEX(BB) ((unsigned)(BB)->aux)
+
+/* The taken-branch edge from the loop end can actually go forward.  Since the
+   Blackfin's LSETUP instruction requires that the loop end be after the loop
+   start, try to reorder a loop's basic blocks when we find such a case.  */
+static void
+bfin_reorder_loops (loop_info loops, FILE *dump_file)
+{
+  basic_block bb;
+  loop_info loop;
+
+  FOR_EACH_BB (bb)
+    bb->aux = NULL;
+  cfg_layout_initialize (CLEANUP_UPDATE_LIFE);
+
+  for (loop = loops; loop; loop = loop->next)
+    {
+      unsigned index;
+      basic_block bb;
+      edge e;
+      edge_iterator ei;
+
+      if (loop->bad)
+	continue;
+
+      /* Recreate an index for basic blocks that represents their order.  */
+      for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+	   bb != EXIT_BLOCK_PTR;
+	   bb = bb->next_bb, index++)
+	bb->aux = (PTR) index;
+
+      if (BB_AUX_INDEX (loop->head) < BB_AUX_INDEX (loop->tail))
+	continue;
+
+      FOR_EACH_EDGE (e, ei, loop->head->succs)
+	{
+	  if (bitmap_bit_p (loop->block_bitmap, e->dest->index)
+	      && BB_AUX_INDEX (e->dest) < BB_AUX_INDEX (loop->tail))
+	    {
+	      basic_block start_bb = e->dest;
+	      basic_block start_prev_bb = start_bb->prev_bb;
+
+	      if (dump_file)
+		fprintf (dump_file, ";; Moving block %d before block %d\n",
+			 loop->head->index, start_bb->index);
+	      loop->head->prev_bb->next_bb = loop->head->next_bb;
+	      loop->head->next_bb->prev_bb = loop->head->prev_bb;
+
+	      loop->head->prev_bb = start_prev_bb;
+	      loop->head->next_bb = start_bb;
+	      start_prev_bb->next_bb = start_bb->prev_bb = loop->head;
+	      break;
+	    }
+	}
+      loops = loops->next;
+    }
+  
+  FOR_EACH_BB (bb)
+    {
+      if (bb->next_bb != EXIT_BLOCK_PTR)
+	bb->aux = bb->next_bb;
+      else
+	bb->aux = NULL;
+    }
+  cfg_layout_finalize ();
+}
+
+/* Run from machine_dependent_reorg, this pass looks for doloop_end insns
+   and tries to rewrite the RTL of these loops so that proper Blackfin
+   hardware loops are generated.  */
+
+static void
+bfin_reorg_loops (FILE *dump_file)
+{
+  loop_info loops = NULL;
+  loop_info loop;
+  basic_block bb;
+  bitmap_obstack stack;
+
+  bitmap_obstack_initialize (&stack);
+
+  if (dump_file)
+    fprintf (dump_file, ";; Find loops, first pass\n\n");
+
+  loops = bfin_discover_loops (&stack, dump_file);
+
+  if (dump_file)
+    bfin_dump_loops (loops);
+
+  bfin_reorder_loops (loops, dump_file);
+  free_loops (loops);
+
+  if (dump_file)
+    fprintf (dump_file, ";; Find loops, second pass\n\n");
+
+  loops = bfin_discover_loops (&stack, dump_file);
   if (dump_file)
     {
       fprintf (dump_file, ";; All loops found:\n\n");
@@ -3742,16 +3992,7 @@ bfin_reorg_loops (FILE *dump_file)
       bfin_dump_loops (loops);
     }
 
-  /* Free up the loop structures */
-  while (loops)
-    {
-      loop = loops;
-      loops = loop->next;
-      VEC_free (loop_info, heap, loop->loops);
-      VEC_free (basic_block, heap, loop->blocks);
-      BITMAP_FREE (loop->block_bitmap);
-      XDELETE (loop);
-    }
+  free_loops (loops);
 
   if (dump_file)
     print_rtl (dump_file, get_insns ());