* Makefile.in (cfg.o, cfganal.o, cfgloop.o, cfgbuild.o, cfgcleanup.o):

	New.
	* basic-block.h (flow_obstack, label_value_list,
	tail_recursion_label_list): Declare
	(tidy_fallthru_edges): Declare.
	(expunge_block, last_loop_beg_note): Delete.
	(can_fallthru, flow_nodes_print, flow_edge_list_print): Declare.
	* cfg.c: New file
	(basic_block_for_insn, label_value_list): Move from flow.c; make global.
	(n_basic_blocks, n_edges, basic_block_info, entry_exit_blocks,
	init_flow, clear_edges, can_delete_note_p, can_delete_label_p,
	flow_delete_insn, flow_delete_insn_chain, create_basic_block,
	expunge_block, flow_delete_block, compute_bb_for_insn,
	update_bb_for_insn, set_block_for_insn, set_block_for_new_insns,
	make_edge, remove_edge, redirect_edge_succ, redirect_edge_succ_nodup,
	redirect_edge_pred, split_block, marge_blocks_nomove, block_label,
	try_redirect_by_replacing_jump, last_loop_beg_note,
	redirect_edge_and_branch, redirect_edge_and_branch_force,
	tidy_fallthru_edge, tidy_fallthru_edges, back_edge_of_syntactic_loop_p,
	split_edge, insert_insn_on_edge, commit_one_edge_insertion,
	commit_edge_insertions, dump_flow_info, debug_flow_info,
	dump_edge_info, dump_bb, debug_bb, debug_bb_n, print_rtl_with_bb,
	verify_flow_info, purge_dead_edges, purge_all_dead_edges):
	Move here from flow.c
	* cfganal.c: New file.
	(forwarder_block_p, can_fallthru, mark_critical_edges,
	 mark_dfs_back_edges, need_fake_edge_p, flow_call_edges_add,
	 find_unreachable_blocks, create_edge_list, free_edge_list,
	 print_edge_list, verify_edge_list, find_edge_index, flow_nodes_print,
	 flow_edge_list_print, remove_fake_successors, remove_fake_edges,
	 add_noreturn_fake_exit_edges, connect_infinite_loops_to_exit,
	 flow_reverse_top_sort_order_compute, flow_depth_first_order_compute,
	 flow_dfs_compute_reverse_init, flow_dfs-compute_reverse_add_bb,
	 flow_dfs-compute_reverse_execute, flow_dfs_compute_reverse_finish);
	Move here from flow.c
	* cfgbuild.c: New file
	(count_basic_blocks, find_label_refs, make_label_edge, make_eh_edge,
	 make_edges, find_basic_blocks_1, find_basic_blocks,
	 find_sub_basic_blocks): Move here from flow.c
	* cfgcleanup.c: New file.
	(try_simplify_condjump, try_forward_edges, tail_recursion_label_p,
	 merge_blocks_move_predecessor_nojumps,
	 merge_blocks_move_successor_nojumps, merge_blocks,
	 flow_find_cross_jump, outgoing_edges_match, try_crossjump_to_edge,
	 try_crossjump_bb, try_optimize_cfg): Move here from flow.c
	(delete_unreachable_blocks, cleanup_cfg): Likewise; return true
	if succeeded.
	* cfgloop.c: New file
	(flow_loops_cfg_dump, flow_loop_nested_p, flow_loop_dump,
	 flow_loops_dump, flow_loops_free, flow_loop_entry_edges_find,
	 flow_loop_exit_edges_find, flow_loop_nodes_find,
	 flow_loop_pre_header_scan, flow_loop_pre_header_find,
	 flow_loop_tree_node_add, flow_loops_tree_build,
	 flow_loop_level_compute, flow_loops_level_compute, flow_loop_scan,
	 flow_loops_find, flow_loops_update, flow_loop_outside_edge_p):
	Move here from flow.c
	* flow.c: Remove everything moved elsewhere
	* output.h (cleanup_cfg): Return bool.

	* bb-reorder.c (reorder_block_def): Remove 'index'.
	(insert_intra_1): Add argument BB, set block for new note.
	(make_reorder_chain): Do not depdent on BB indexes.
	(make_reorder_chain_1): Do not use BB indexes.
	(label_for_bb): Likewise; set BB for new insn.
	(emit_jump_to_block_after): Likewise.
	(fixup_reoder_chain): Sanity check that all basic blocks
	are chained; verify newly created insn chain; remove
	undocnitional jump simplifying; Do not use BB indexes;
	properly initialize count and frequency information;
	dump reordered sequence.
	(insert_intra_bb_scope_notes): update call of insert_intra_1.
	(insert_inter_bb_scope_notes): Set block for new insn.
	(reorder_basic_blocks): Dump flow info before reoredering.


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

1 files changed, 81 insertions, 71 deletions

diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 72d3902e7fc..3102132eb3e 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -165,7 +165,6 @@ typedef struct reorder_block_def
   rtx eff_end;
   scope scope;
   basic_block next;
-  int index;
   int visited;
 } *reorder_block_def;
 
@@ -187,7 +186,7 @@ static void relate_bbs_with_scopes	PARAMS ((scope));
 static scope make_new_scope		PARAMS ((int, rtx));
 static void build_scope_forest		PARAMS ((scope_forest_info *));
 static void remove_scope_notes		PARAMS ((void));
-static void insert_intra_1		PARAMS ((scope, rtx *));
+static void insert_intra_1		PARAMS ((scope, rtx *, basic_block));
 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
 static void rebuild_scope_notes		PARAMS ((scope_forest_info *));
@@ -323,6 +322,7 @@ make_reorder_chain ()
   basic_block last_block = NULL;
   basic_block prev = NULL;
   int nbb_m1 = n_basic_blocks - 1;
+  basic_block next;
 
   /* If we've not got epilogue in RTL, we must fallthru to the exit.
      Force the last block to be at the end.  */
@@ -339,7 +339,8 @@ make_reorder_chain ()
   do
     {
       int i;
-      basic_block next = NULL;
+
+      next = NULL;
 
       /* Find the next unplaced block.  */
       /* ??? Get rid of this loop, and track which blocks are not yet
@@ -348,27 +349,21 @@ make_reorder_chain ()
 	 remove from the list as we place.  The head of that list is
 	 what we're looking for here.  */
 
-      for (i = 0; i <= nbb_m1; ++i)
+      for (i = 0; i <= nbb_m1 && !next; ++i)
 	{
 	  basic_block bb = BASIC_BLOCK (i);
 	  if (! RBI (bb)->visited)
-	    {
-	      next = bb;
-	      break;
-	    }
+	    next = bb;
 	}
-      if (! next)
-	abort ();
-
-      prev = make_reorder_chain_1 (next, prev);
+      if (next)
+        prev = make_reorder_chain_1 (next, prev);
     }
-  while (RBI (prev)->index < nbb_m1);
+  while (next);
 
   /* Terminate the chain.  */
   if (! HAVE_epilogue)
     {
       RBI (prev)->next = last_block;
-      RBI (last_block)->index = RBI (prev)->index + 1;
       prev = last_block;
     }
   RBI (prev)->next = NULL;
@@ -397,19 +392,18 @@ make_reorder_chain_1 (bb, prev)
   /* Mark this block visited.  */
   if (prev)
     {
-      int new_index;
-
  restart:
       RBI (prev)->next = bb;
-      new_index = RBI (prev)->index + 1;
-      RBI (bb)->index = new_index;
 
       if (rtl_dump_file && prev->index + 1 != bb->index)
-	fprintf (rtl_dump_file, "Reordering block %d (%d) after %d (%d)\n",
-		 bb->index, RBI (bb)->index, prev->index, RBI (prev)->index);
+	fprintf (rtl_dump_file, "Reordering block %d after %d\n",
+		 bb->index, prev->index);
     }
   else
-    RBI (bb)->index = 0;
+    {
+      if (bb->index != 0)
+	abort ();
+    }
   RBI (bb)->visited = 1;
   prev = bb;
 
@@ -508,13 +502,15 @@ label_for_bb (bb)
   if (GET_CODE (label) != CODE_LABEL)
     {
       if (rtl_dump_file)
-	fprintf (rtl_dump_file, "Emitting label for block %d (%d)\n",
-		 bb->index, RBI (bb)->index);
+	fprintf (rtl_dump_file, "Emitting label for block %d\n",
+		 bb->index);
 
       label = emit_label_before (gen_label_rtx (), label);
       if (bb->head == RBI (bb)->eff_head)
 	RBI (bb)->eff_head = label;
       bb->head = label;
+      if (basic_block_for_insn)
+	set_block_for_insn (label, bb);
     }
 
   return label;
@@ -540,8 +536,8 @@ emit_jump_to_block_after (bb, after)
 	set_block_for_new_insns (jump, bb);
 
       if (rtl_dump_file)
-	fprintf (rtl_dump_file, "Emitting jump to block %d (%d)\n",
-		 bb->index, RBI (bb)->index);
+	fprintf (rtl_dump_file, "Emitting jump to block %d\n",
+		 bb->index);
     }
   else
     {
@@ -549,6 +545,8 @@ emit_jump_to_block_after (bb, after)
       if (! HAVE_return)
 	abort ();
       jump = emit_jump_insn_after (gen_return (), after);
+      if (basic_block_for_insn)
+	set_block_for_new_insns (jump, bb);
 
       if (rtl_dump_file)
 	fprintf (rtl_dump_file, "Emitting return\n");
@@ -567,12 +565,16 @@ static void
 fixup_reorder_chain ()
 {
   basic_block bb, last_bb;
+  int index;
+  rtx insn;
+  int old_n_basic_blocks = n_basic_blocks;
 
   /* First do the bulk reordering -- rechain the blocks without regard to
      the needed changes to jumps and labels.  */
 
   last_bb = BASIC_BLOCK (0);
   bb = RBI (last_bb)->next;
+  index = 1;
   while (bb)
     {
       rtx last_e = RBI (last_bb)->eff_end;
@@ -583,19 +585,24 @@ fixup_reorder_chain ()
 
       last_bb = bb;
       bb = RBI (bb)->next;
+      index++;
     }
 
-  {
-    rtx insn = RBI (last_bb)->eff_end;
+  if (index != n_basic_blocks)
+    abort ();
 
-    NEXT_INSN (insn) = function_tail_eff_head;
-    if (function_tail_eff_head)
-      PREV_INSN (function_tail_eff_head) = insn;
+  insn = RBI (last_bb)->eff_end;
 
-    while (NEXT_INSN (insn))
-      insn = NEXT_INSN (insn);
-    set_last_insn (insn);
-  }
+  NEXT_INSN (insn) = function_tail_eff_head;
+  if (function_tail_eff_head)
+    PREV_INSN (function_tail_eff_head) = insn;
+
+  while (NEXT_INSN (insn))
+    insn = NEXT_INSN (insn);
+  set_last_insn (insn);
+#ifdef ENABLE_CHECKING
+  verify_insn_chain ();
+#endif
 
   /* Now add jumps and labels as needed to match the blocks new
      outgoing edges.  */
@@ -621,27 +628,11 @@ fixup_reorder_chain ()
       bb_end_insn = bb->end;
       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 	{
-	  if (any_uncondjump_p (bb_end_insn))
-	    {
-	      /* If the destination is still not next, nothing to do.  */
-	      if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index)
-		continue;
-
-	      /* Otherwise, we can remove the jump and cleanup the edge.  */
-	      tidy_fallthru_edge (e_taken, bb, e_taken->dest);
-	      RBI (bb)->eff_end = skip_insns_after_block (bb);
-	      RBI (e_taken->dest)->eff_head = NEXT_INSN (RBI (bb)->eff_end);
-
-	      if (rtl_dump_file)
-		fprintf (rtl_dump_file, "Removing jump in block %d (%d)\n",
-			 bb->index, RBI (bb)->index);
-	      continue;
-	    }
-	  else if (any_condjump_p (bb_end_insn))
+	  if (any_condjump_p (bb_end_insn))
 	    {
 	      /* If the old fallthru is still next, nothing to do.  */
-	      if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index
-	          || (RBI (bb)->index == n_basic_blocks - 1
+	      if (RBI (bb)->next == e_fall->dest
+	          || (!RBI (bb)->next
 		      && e_fall->dest == EXIT_BLOCK_PTR))
 		continue;
 
@@ -649,7 +640,7 @@ fixup_reorder_chain ()
 		 such as happens at the very end of a function, then we'll
 		 need to add a new unconditional jump.  Choose the taken
 		 edge based on known or assumed probability.  */
-	      if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index)
+	      if (RBI (bb)->next != e_taken->dest)
 		{
 		  rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 		  if (note
@@ -684,7 +675,7 @@ fixup_reorder_chain ()
 #ifdef CASE_DROPS_THROUGH
 	      /* Except for VAX.  Since we didn't have predication for the
 		 tablejump, the fallthru block should not have moved.  */
-	      if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index)
+	      if (RBI (bb)->next == e_fall->dest)
 		continue;
 	      bb_end_insn = skip_insns_after_block (bb);
 #else
@@ -701,9 +692,7 @@ fixup_reorder_chain ()
 	    continue;
 
 	  /* If the fallthru block is still next, nothing to do.  */
-	  if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index
-	      || (RBI (bb)->index == n_basic_blocks - 1
-		  && e_fall->dest == EXIT_BLOCK_PTR))
+	  if (RBI (bb)->next == e_fall->dest)
 	    continue;
 
 	  /* We need a new jump insn.  If the block has only one outgoing
@@ -730,12 +719,12 @@ fixup_reorder_chain ()
       create_basic_block (n_basic_blocks - 1, jump_insn, jump_insn, NULL);
 
       nb = BASIC_BLOCK (n_basic_blocks - 1);
-      nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
-      nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
       nb->local_set = 0;
       nb->count = e_fall->count;
       nb->frequency = EDGE_FREQUENCY (e_fall);
 
+      nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+      nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
       COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start);
       COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start);
 
@@ -743,7 +732,6 @@ fixup_reorder_chain ()
       RBI (nb)->eff_head = nb->head;
       RBI (nb)->eff_end = barrier_insn;
       RBI (nb)->scope = RBI (bb)->scope;
-      RBI (nb)->index = RBI (bb)->index + 1;
       RBI (nb)->visited = 1;
       RBI (nb)->next = RBI (bb)->next;
       RBI (bb)->next = nb;
@@ -756,17 +744,26 @@ fixup_reorder_chain ()
 
       /* Don't process this new block.  */
       bb = nb;
-
-      /* Fix subsequent reorder block indices to reflect new block.  */
-      while ((nb = RBI (nb)->next) != NULL)
-	RBI (nb)->index += 1;
     }
 
   /* Put basic_block_info in the new order.  */
-  for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
+  bb = BASIC_BLOCK (0);
+  index = 0;
+
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "Reordered sequence:\n");
+  while (bb)
     {
-      bb->index = RBI (bb)->index;
-      BASIC_BLOCK (bb->index) = bb;
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
+		 bb->index >= old_n_basic_blocks ? "compensation " : "",
+		 bb->index,
+	   	 bb->frequency);
+      bb->index = index;
+      BASIC_BLOCK (index) = bb;
+
+      bb = RBI (bb)->next;
+      index++;
     }
 }
 
@@ -1142,9 +1139,10 @@ remove_scope_notes ()
 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
 
 static void
-insert_intra_1 (s, ip)
+insert_intra_1 (s, ip, bb)
      scope s;
      rtx *ip;
+     basic_block bb;
 {
   scope p;
 
@@ -1152,15 +1150,19 @@ insert_intra_1 (s, ip)
     {  
       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
+      if (basic_block_for_insn)
+	set_block_for_insn (*ip, bb);
     } 
 
   for (p = s->inner; p; p = p->next)
-    insert_intra_1 (p, ip);
+    insert_intra_1 (p, ip, bb);
 
   if (NOTE_BLOCK (s->note_beg))
     {  
       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
+      if (basic_block_for_insn)
+	set_block_for_insn (*ip, bb);
     }
 }
 
@@ -1186,7 +1188,7 @@ insert_intra_bb_scope_notes (bb)
   for (p = s->inner; p; p = p->next)
     {
       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
-	insert_intra_1 (p, &ip);
+	insert_intra_1 (p, &ip, bb);
     }
 }
 
@@ -1254,6 +1256,8 @@ insert_inter_bb_scope_notes (bb1, bb2)
 	    {  
 	      ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
 	      NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
+	      if (basic_block_for_insn)
+		set_block_for_insn (ip, bb1);
 	    }
 	  s = s->outer;
 	}
@@ -1270,6 +1274,8 @@ insert_inter_bb_scope_notes (bb1, bb2)
 	    {  
 	      ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
 	      NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
+	      if (basic_block_for_insn)
+		set_block_for_insn (ip, bb2);
 	    }
 	  s = s->outer;
 	}
@@ -1414,6 +1420,10 @@ reorder_basic_blocks ()
 
   record_effective_endpoints ();
   make_reorder_chain ();
+
+  if (rtl_dump_file)
+    dump_flow_info (rtl_dump_file);
+
   fixup_reorder_chain ();
 
 #ifdef ENABLE_CHECKING