* bb-reorder.c (copy_bb, duplicate_computed_gotos): Add argument

	to duplicate_block.
	* cfghooks.c (duplicate_block): Added position where to place
	new block as argument.
	* cfghooks.h (duplicate_block): Declaration changed.
	* cfglayout.c (copy_bbs): Add argument after.  Pass it to
	duplicate_block.
	* cfglayout.h (copy_bbs): Declaration changed.
	* cfgloop.h (loop_version): Declaration changed.
	* cfgloopmanip.c (duplicate_loop_to_header_edge): Pass
	position to copy_bbs.
	(loop_version): Pass position to duplicate_loop_to_header_edge.
	Add place_after argument and position new blocks according to
	it.
	* modulo-sched.c (sms_schedule): Pass place_after argument
	to loop_version.
	* tracer.c (tail_duplicate): Pass argument to duplicate_block.
	* tree-cfg.c (split_edge_bb_loc): New function.
	(tree_split_edge, tree_duplicate_sese_region): Use split_edge_bb_loc
	to determine position of new blocks.
	* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Pass argument
	to loop_version.
	* tree-ssa-threadupdate.c (create_block_for_threading): Pass
	argument to duplicate_block.
	* tree-vectorizer.c (slpeel_tree_duplicate_loop_to_edge_cfg):
	Pass position to copy_bbs.


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

14 files changed, 122 insertions, 44 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3307aa91a8a..533b33d13cd 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,34 @@
 2005-08-24  Zdenek Dvorak  <dvorakz@suse.cz>
 
+	* bb-reorder.c (copy_bb, duplicate_computed_gotos): Add argument
+	to duplicate_block.
+	* cfghooks.c (duplicate_block): Added position where to place
+	new block as argument.
+	* cfghooks.h (duplicate_block): Declaration changed.
+	* cfglayout.c (copy_bbs): Add argument after.  Pass it to
+	duplicate_block.
+	* cfglayout.h (copy_bbs): Declaration changed.
+	* cfgloop.h (loop_version): Declaration changed.
+	* cfgloopmanip.c (duplicate_loop_to_header_edge): Pass
+	position to copy_bbs.
+	(loop_version): Pass position to duplicate_loop_to_header_edge.
+	Add place_after argument and position new blocks according to
+	it.
+	* modulo-sched.c (sms_schedule): Pass place_after argument
+	to loop_version.
+	* tracer.c (tail_duplicate): Pass argument to duplicate_block.
+	* tree-cfg.c (split_edge_bb_loc): New function.
+	(tree_split_edge, tree_duplicate_sese_region): Use split_edge_bb_loc
+	to determine position of new blocks.
+	* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Pass argument
+	to loop_version.
+	* tree-ssa-threadupdate.c (create_block_for_threading): Pass
+	argument to duplicate_block.
+	* tree-vectorizer.c (slpeel_tree_duplicate_loop_to_edge_cfg):
+	Pass position to copy_bbs.
+
+2005-08-24  Zdenek Dvorak  <dvorakz@suse.cz>
+
 	* fold-const.c (ptr_difference_const): Use
 	cst_and_fits_in_hwi instead of host_integerp.
 
diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 2dca3e373e8..c5de2352fa2 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -758,7 +758,7 @@ copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
 {
   basic_block new_bb;
 
-  new_bb = duplicate_block (old_bb, e);
+  new_bb = duplicate_block (old_bb, e, bb);
   BB_COPY_PARTITION (new_bb, old_bb);
 
   gcc_assert (e->dest == new_bb);
@@ -2072,7 +2072,7 @@ duplicate_computed_gotos (void)
       if (!bitmap_bit_p (candidates, single_succ (bb)->index))
 	continue;
 
-      new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb));
+      new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
       new_bb->aux = bb->aux;
       bb->aux = new_bb;
       new_bb->il.rtl->visited = 1;
diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
index bc296d43e0b..138bc4ab2ae 100644
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -691,10 +691,11 @@ can_duplicate_block_p (basic_block bb)
 }
 
 /* Duplicates basic block BB and redirects edge E to it.  Returns the
-   new basic block.  */
+   new basic block.  The new basic block is placed after the basic block
+   AFTER.  */
 
 basic_block
-duplicate_block (basic_block bb, edge e)
+duplicate_block (basic_block bb, edge e, basic_block after)
 {
   edge s, n;
   basic_block new_bb;
@@ -713,6 +714,8 @@ duplicate_block (basic_block bb, edge e)
 #endif
 
   new_bb = cfg_hooks->duplicate_block (bb);
+  if (after)
+    move_block_after (new_bb, after);
 
   new_bb->loop_depth = bb->loop_depth;
   new_bb->flags = bb->flags;
diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h
index 5c3e610ea2c..8d5222a5f13 100644
--- a/gcc/cfghooks.h
+++ b/gcc/cfghooks.h
@@ -157,7 +157,7 @@ extern void tidy_fallthru_edges (void);
 extern void predict_edge (edge e, enum br_predictor predictor, int probability);
 extern bool predicted_by_p (basic_block bb, enum br_predictor predictor);
 extern bool can_duplicate_block_p (basic_block);
-extern basic_block duplicate_block (basic_block, edge);
+extern basic_block duplicate_block (basic_block, edge, basic_block);
 extern bool block_ends_with_call_p (basic_block bb);
 extern bool block_ends_with_condjump_p (basic_block bb);
 extern int flow_call_edges_add (sbitmap);
diff --git a/gcc/cfglayout.c b/gcc/cfglayout.c
index c63c6f7a4cf..9cc2f8fa709 100644
--- a/gcc/cfglayout.c
+++ b/gcc/cfglayout.c
@@ -1243,12 +1243,15 @@ end:
    is copied, we do not set the new blocks as header or latch.
 
    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
-   also in the same order.  */
+   also in the same order.
+   
+   Newly created basic blocks are put after the basic block AFTER in the
+   instruction stream, and the order of the blocks in BBS array is preserved.  */
 
 void
 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
 	  edge *edges, unsigned num_edges, edge *new_edges,
-	  struct loop *base)
+	  struct loop *base, basic_block after)
 {
   unsigned i, j;
   basic_block bb, new_bb, dom_bb;
@@ -1259,7 +1262,8 @@ copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
     {
       /* Duplicate.  */
       bb = bbs[i];
-      new_bb = new_bbs[i] = duplicate_block (bb, NULL);
+      new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
+      after = new_bb;
       bb->flags |= BB_DUPLICATED;
       /* Add to loop.  */
       add_bb_to_loop (new_bb, bb->loop_father->copy);
diff --git a/gcc/cfglayout.h b/gcc/cfglayout.h
index ed41aa3c2a3..52bd4e9ee14 100644
--- a/gcc/cfglayout.h
+++ b/gcc/cfglayout.h
@@ -31,7 +31,8 @@ extern void insn_locators_initialize (void);
 extern void reemit_insn_block_notes (void);
 extern bool can_copy_bbs_p (basic_block *, unsigned);
 extern void copy_bbs (basic_block *, unsigned, basic_block *,
-		      edge *, unsigned, edge *, struct loop *);
+		      edge *, unsigned, edge *, struct loop *,
+		      basic_block);
 extern rtx duplicate_insn_chain (rtx, rtx);
 
 #endif /* GCC_CFGLAYOUT_H */
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index cc3992e6a4b..b237631433d 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -309,7 +309,7 @@ extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
 extern struct loop *loopify (struct loops *, edge, edge,
 			     basic_block, edge, edge, bool);
 struct loop * loop_version (struct loops *, struct loop *, void *,
-			    basic_block *);			     
+			    basic_block *, bool);
 extern bool remove_path (struct loops *, edge);
 extern edge split_loop_bb (basic_block, void *);
 
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 02c3add4717..806daa789f7 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -860,6 +860,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
   int p, freq_in, freq_le, freq_out_orig;
   int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
   int add_irreducible_flag;
+  basic_block place_after;
 
   gcc_assert (e->dest == loop->header);
   gcc_assert (ndupl > 0);
@@ -871,7 +872,10 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
       gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
     }
 
-  bbs = get_loop_body (loop);
+  n = loop->num_nodes;
+  bbs = get_loop_body_in_dom_order (loop);
+  gcc_assert (bbs[0] == loop->header);
+  gcc_assert (bbs[n  - 1] == loop->latch);
 
   /* Check whether duplication is possible.  */
   if (!can_copy_bbs_p (bbs, loop->num_nodes))
@@ -975,8 +979,6 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
 
   loop->copy = target;
 
-  n = loop->num_nodes;
-
   first_active = xmalloc (n * sizeof (basic_block));
   if (is_latch)
     {
@@ -995,13 +997,16 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
   spec_edges[SE_ORIG] = orig;
   spec_edges[SE_LATCH] = latch_edge;
 
+  place_after = e->src;
   for (j = 0; j < ndupl; j++)
     {
       /* Copy loops.  */
       copy_loops_to (loops, orig_loops, n_orig_loops, target);
 
       /* Copy bbs.  */
-      copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
+      copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
+		place_after);
+      place_after = new_spec_edges[SE_LATCH]->src;
 
       if (flags & DLTHE_RECORD_COPY_NUMBER)
 	for (i = 0; i < n; i++)
@@ -1039,7 +1044,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
 	  redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
 					  loop->header);
 	  set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
-	  latch = loop->latch = new_bbs[1];
+	  latch = loop->latch = new_bbs[n - 1];
 	  e = latch_edge = new_spec_edges[SE_LATCH];
 	}
       else
@@ -1060,7 +1065,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
       if (!first_active_latch)
 	{
 	  memcpy (first_active, new_bbs, n * sizeof (basic_block));
-	  first_active_latch = new_bbs[1];
+	  first_active_latch = new_bbs[n - 1];
 	}
 
       /* Set counts and frequencies.  */
@@ -1426,21 +1431,26 @@ lv_adjust_loop_entry_edge (basic_block first_head,
 
 /* Main entry point for Loop Versioning transformation.
    
-This transformation given a condition and a loop, creates
--if (condition) { loop_copy1 } else { loop_copy2 },
-where loop_copy1 is the loop transformed in one way, and loop_copy2
-is the loop transformed in another way (or unchanged). 'condition'
-may be a run time test for things that were not resolved by static
-analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
+   This transformation given a condition and a loop, creates
+   -if (condition) { loop_copy1 } else { loop_copy2 },
+   where loop_copy1 is the loop transformed in one way, and loop_copy2
+   is the loop transformed in another way (or unchanged). 'condition'
+   may be a run time test for things that were not resolved by static
+   analysis (overlapping ranges (anti-aliasing), alignment, etc.).
+
+   If PLACE_AFTER is true, we place the new loop after LOOP in the
+   instruction stream, otherwise it is placed before LOOP.  */
 
 struct loop *
 loop_version (struct loops *loops, struct loop * loop, 
-	      void *cond_expr, basic_block *condition_bb)
+	      void *cond_expr, basic_block *condition_bb,
+	      bool place_after)
 {
   basic_block first_head, second_head;
   edge entry, latch_edge, exit, true_edge, false_edge;
   int irred_flag;
   struct loop *nloop;
+  basic_block cond_bb;
 
   /* CHECKME: Loop versioning does not handle nested loop at this point.  */
   if (loop->inner)
@@ -1464,9 +1474,12 @@ loop_version (struct loops *loops, struct loop * loop,
   second_head = entry->dest;
 
   /* Split loop entry edge and insert new block with cond expr.  */
-  *condition_bb =  lv_adjust_loop_entry_edge (first_head, second_head,
-					      entry, cond_expr);
-  if (!*condition_bb)
+  cond_bb =  lv_adjust_loop_entry_edge (first_head, second_head,
+					entry, cond_expr);
+  if (condition_bb)
+    *condition_bb = cond_bb;
+
+  if (!cond_bb)
     {
       entry->flags |= irred_flag;
       return NULL;
@@ -1474,11 +1487,11 @@ loop_version (struct loops *loops, struct loop * loop,
 
   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
   
-  extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+  extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
   nloop = loopify (loops,
 		   latch_edge,
 		   single_pred_edge (get_bb_copy (loop->header)),
-		   *condition_bb, true_edge, false_edge,
+		   cond_bb, true_edge, false_edge,
 		   false /* Do not redirect all edges.  */);
 
   exit = loop->single_exit;
@@ -1489,15 +1502,30 @@ loop_version (struct loops *loops, struct loop * loop,
   lv_flush_pending_stmts (latch_edge);
 
   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */ 
-  extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+  extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
   lv_flush_pending_stmts (false_edge);
   /* Adjust irreducible flag.  */
   if (irred_flag)
     {
-      (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+      cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
-      single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP;
+      single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
+    }
+
+  if (place_after)
+    {
+      basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
+      unsigned i;
+
+      after = loop->latch;
+
+      for (i = 0; i < nloop->num_nodes; i++)
+	{
+	  move_block_after (bbs[i], after);
+	  after = bbs[i];
+	}
+      free (bbs);
     }
 
   /* At this point condition_bb is loop predheader with two successors, 
diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c
index 69a9d33664f..ed06fc46620 100644
--- a/gcc/modulo-sched.c
+++ b/gcc/modulo-sched.c
@@ -1261,7 +1261,8 @@ sms_schedule (FILE *dump_file)
 		  rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
 						 GEN_INT(stage_count));
 
-		  nloop = loop_version (loops, loop, comp_rtx, &condition_bb);
+		  nloop = loop_version (loops, loop, comp_rtx, &condition_bb,
+					true);
 		}
 
 	      /* Set new iteration count of loop kernel.  */
diff --git a/gcc/tracer.c b/gcc/tracer.c
index a92dcbc35dd..27f06c57d89 100644
--- a/gcc/tracer.c
+++ b/gcc/tracer.c
@@ -281,7 +281,7 @@ tail_duplicate (void)
 	      e = find_edge (bb, bb2);
 
 	      nduplicated += counts [bb2->index];
-	      bb2 = duplicate_block (bb2, e);
+	      bb2 = duplicate_block (bb2, e, bb);
 
 	      /* Reconsider the original copy of block we've duplicated.
 	         Removing the most common predecessor may make it to be
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index ad399fbce64..7a0bf1b9102 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -3037,6 +3037,22 @@ reinstall_phi_args (edge new_edge, edge old_edge)
   PENDING_STMT (old_edge) = NULL;
 }
 
+/* Returns the basic block after that the new basic block created
+   by splitting edge EDGE_IN should be placed.  Tries to keep the new block
+   near its "logical" location.  This is of most help to humans looking
+   at debugging dumps.  */
+
+static basic_block
+split_edge_bb_loc (edge edge_in)
+{
+  basic_block dest = edge_in->dest;
+
+  if (dest->prev_bb && find_edge (dest->prev_bb, dest))
+    return edge_in->src;
+  else
+    return dest->prev_bb;
+}
+
 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
    Abort on abnormal edges.  */
 
@@ -3052,13 +3068,7 @@ tree_split_edge (edge edge_in)
   src = edge_in->src;
   dest = edge_in->dest;
 
-  /* Place the new block in the block list.  Try to keep the new block
-     near its "logical" location.  This is of most help to humans looking
-     at debugging dumps.  */
-  if (dest->prev_bb && find_edge (dest->prev_bb, dest))
-    after_bb = edge_in->src;
-  else
-    after_bb = dest->prev_bb;
+  after_bb = split_edge_bb_loc (edge_in);
 
   new_bb = create_empty_bb (after_bb);
   new_bb->frequency = EDGE_FREQUENCY (edge_in);
@@ -4346,7 +4356,8 @@ tree_duplicate_sese_region (edge entry, edge exit,
 	entry_freq = total_freq;
     }
 
-  copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
+  copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
+	    split_edge_bb_loc (entry));
   if (total_count)
     {
       scale_bbs_frequencies_gcov_type (region, n_region,
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index 17362694db9..d0625c52ec9 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -282,5 +282,5 @@ tree_unswitch_loop (struct loops *loops, struct loop *loop,
   gcc_assert (loop->inner == NULL);
 
   return loop_version (loops, loop, unshare_expr (cond), 
-		       &condition_bb);
+		       &condition_bb, false);
 }
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index ab748ad7798..1b7733b0c9b 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -199,7 +199,7 @@ create_block_for_threading (basic_block bb, struct redirection_data *rd)
 {
   /* We can use the generic block duplication code and simply remove
      the stuff we do not need.  */
-  rd->dup_block = duplicate_block (bb, NULL);
+  rd->dup_block = duplicate_block (bb, NULL, NULL);
 
   /* Zero out the profile, since the block is unreachable for now.  */
   rd->dup_block->frequency = 0;
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 1cce052d276..84ed5a90c3b 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -862,7 +862,8 @@ slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
   new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
 
   copy_bbs (bbs, loop->num_nodes, new_bbs,
-	    &loop->single_exit, 1, &new_loop->single_exit, NULL);
+	    &loop->single_exit, 1, &new_loop->single_exit, NULL,
+	    e->src);
 
   /* Duplicating phi args at exit bbs as coming 
      also from exit of duplicated loop.  */