13 files changed, 126 insertions, 133 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 95ce7d2696c..174b392e3dd 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,37 @@
+2002-05-28  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+
+	* basic-block.h (last_basic_block): Declare.
+	(expunge_block_nocompact): Declaration removed.
+	(compact_blocks): Declare.
+	* cfg.c (last_basic_block): New variable.
+	(expunge_block_nocompact): Removed.
+	(expunge_block): Do not compact basic blocks.
+	(compact_blocks): New.
+	* cfganal.c (flow_call_edges_add): Use the fact that bb indices no
+	longer change.
+	* cfgbuild.c (find_basic_blocks_1, find_basic_blocks): Set
+	last_basic_block.
+	* cfgcleanup.c (merge_blocks_move_predecessor_nojumps): Do not change
+	real positions of blocks.
+	(delete_unreachable_blocks): Simplified -- quadratic behavior now
+	cannot occur.
+	(cleanup_cfg): Compact blocks.
+	* cfgrtl.c (create_basic_block): Insert basic blocks to the end of
+	basic_block_info varray.
+	(flow_delete_block): Comment update.
+	(back_edge_of_syntactic_loop_p): Modify position check code.
+	(verify_flow_info): Update checking.
+	* flow.c (calculate_global_regs_live): Use FOR_EACH_BB.
+	* ifcvt.c (SET_ORIG_INDEX, ORIG_INDEX): Removed.
+	(find_if_case_1, find_if_case_2, if_convert): Use the fact that bb
+	indices no longer change.
+	* lcm.c (optimize_mode_switching): Replace n_basic_blocks with
+	last_basic_block.
+	* predict.c (estimate_bb_frequencies): Remove unneccessary code.
+	* profile.c (branch_prob): Compact blocks.
+	* sched-rgn.c (find_rgns): Replace n_basic_blocks with
+	last_basic_block.
+
 2002-05-28  Kazu Hirata  <kazu@cs.umass.edu>
 
 	* config/h8300/h8300.md (two anonymous patterns): New.
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 55981644d4e..a848e946e91 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -235,7 +235,7 @@ extern int n_basic_blocks;
 
 /* First free basic block number.  */
 
-#define last_basic_block n_basic_blocks
+extern int last_basic_block;
 
 /* Number of edges in the current function.  */
 
@@ -670,7 +670,7 @@ extern void allocate_bb_life_data	PARAMS ((void));
 extern void expunge_block		PARAMS ((basic_block));
 extern void link_block			PARAMS ((basic_block, basic_block));
 extern void unlink_block		PARAMS ((basic_block));
-extern void expunge_block_nocompact	PARAMS ((basic_block));
+extern void compact_blocks		PARAMS ((void));
 extern basic_block alloc_block		PARAMS ((void));
 extern void find_unreachable_blocks	PARAMS ((void));
 extern int delete_noop_moves		PARAMS ((rtx));
diff --git a/gcc/cfg.c b/gcc/cfg.c
index 948a3454611..313516b32fa 100644
--- a/gcc/cfg.c
+++ b/gcc/cfg.c
@@ -65,6 +65,10 @@ static char *flow_firstobj;
 
 int n_basic_blocks;
 
+/* First free basic block number.  */
+
+int last_basic_block;
+
 /* Number of edges in the current function.  */
 
 int n_edges;
@@ -243,14 +247,37 @@ unlink_block (b)
   b->prev_bb->next_bb = b->next_bb;
 }
 
+/* Sequentially order blocks and compact the arrays.  */
+void
+compact_blocks ()
+{
+  int i;
+  basic_block bb;
+ 
+  i = 0;
+  FOR_EACH_BB (bb)
+    {
+      BASIC_BLOCK (i) = bb;
+      bb->index = i;
+      i++;
+    }
+
+  if (i != n_basic_blocks)
+    abort ();
+
+  last_basic_block = n_basic_blocks;
+}
+
 
-/* Remove block B from the basic block array and compact behind it.  */
+/* Remove block B from the basic block array.  */
 
 void
-expunge_block_nocompact (b)
+expunge_block (b)
      basic_block b;
 {
   unlink_block (b);
+  BASIC_BLOCK (b->index) = NULL;
+  n_basic_blocks--;
 
   /* Invalidate data to make bughunting easier.  */
   memset (b, 0, sizeof *b);
@@ -258,25 +285,6 @@ expunge_block_nocompact (b)
   b->succ = (edge) first_deleted_block;
   first_deleted_block = (basic_block) b;
 }
-
-void
-expunge_block (b)
-     basic_block b;
-{
-  int i, n = n_basic_blocks;
-
-  for (i = b->index; i + 1 < n; ++i)
-    {
-      basic_block x = BASIC_BLOCK (i + 1);
-      BASIC_BLOCK (i) = x;
-      x->index = i;
-    }
-
-  n_basic_blocks--;
-  basic_block_info->num_elements--;
-
-  expunge_block_nocompact (b);
-}
 
 /* Create an edge connecting SRC and DST with FLAGS optionally using
    edge cache CACHE.  Return the new edge, NULL if already exist.  */
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index 15031f621c5..5f69d1ab2d4 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -258,29 +258,16 @@ flow_call_edges_add (blocks)
 {
   int i;
   int blocks_split = 0;
-  int bb_num = 0;
-  basic_block *bbs, bb;
+  int last_bb = last_basic_block;
   bool check_last_block = false;
 
-  /* Map bb indices into basic block pointers since split_block
-     will renumber the basic blocks.  */
-
-  bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
+  if (n_basic_blocks == 0)
+    return 0;
 
   if (! blocks)
-    {
-      FOR_EACH_BB (bb)
-	bbs[bb_num++] = bb;
-
-      check_last_block = true;
-    }
+    check_last_block = true;
   else
-    EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
-			       {
-				 bbs[bb_num++] = BASIC_BLOCK (i);
-				 if (i == n_basic_blocks - 1)
-				   check_last_block = true;
-			       });
+    check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
 
   /* In the last basic block, before epilogue generation, there will be
      a fallthru edge to EXIT.  Special care is required if the last insn
@@ -321,12 +308,18 @@ flow_call_edges_add (blocks)
      calls since there is no way that we can determine if they will
      return or not...  */
 
-  for (i = 0; i < bb_num; i++)
+  for (i = 0; i < last_bb; i++)
     {
-      basic_block bb = bbs[i];
+      basic_block bb = BASIC_BLOCK (i);
       rtx insn;
       rtx prev_insn;
 
+      if (!bb)
+	continue;
+
+      if (blocks && !TEST_BIT (blocks, i))
+	continue;
+
       for (insn = bb->end; ; insn = prev_insn)
 	{
 	  prev_insn = PREV_INSN (insn);
@@ -374,7 +367,6 @@ flow_call_edges_add (blocks)
   if (blocks_split)
     verify_flow_info ();
 
-  free (bbs);
   return blocks_split;
 }
 
@@ -927,7 +919,7 @@ flow_preorder_transversal_compute (pot_order)
       for (e = bb->succ; e; e = e->succ_next)
 	max_successors++;
 
-      dfst[i].node
+      dfst[bb->index].node
 	= (max_successors
 	   ? (struct dfst_node **) xcalloc (max_successors,
 					    sizeof (struct dfst_node *))
diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c
index 3a86e1ca8f3..bdf175d53af 100644
--- a/gcc/cfgbuild.c
+++ b/gcc/cfgbuild.c
@@ -471,7 +471,6 @@ find_basic_blocks_1 (f)
      rtx f;
 {
   rtx insn, next;
-  int i = 0;
   rtx bb_note = NULL_RTX;
   rtx lvl = NULL_RTX;
   rtx trll = NULL_RTX;
@@ -494,7 +493,7 @@ find_basic_blocks_1 (f)
       if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
 	  && head)
 	{
-	  prev = create_basic_block_structure (i++, head, end, bb_note, prev);
+	  prev = create_basic_block_structure (last_basic_block++, head, end, bb_note, prev);
 	  head = end = NULL_RTX;
 	  bb_note = NULL_RTX;
 	}
@@ -508,7 +507,7 @@ find_basic_blocks_1 (f)
 
       if (head && control_flow_insn_p (insn))
 	{
-	  prev = create_basic_block_structure (i++, head, end, bb_note, prev);
+	  prev = create_basic_block_structure (last_basic_block++, head, end, bb_note, prev);
 	  head = end = NULL_RTX;
 	  bb_note = NULL_RTX;
 	}
@@ -590,11 +589,11 @@ find_basic_blocks_1 (f)
     }
 
   if (head != NULL_RTX)
-    create_basic_block_structure (i++, head, end, bb_note, prev);
+    create_basic_block_structure (last_basic_block++, head, end, bb_note, prev);
   else if (bb_note)
     delete_insn (bb_note);
 
-  if (i != n_basic_blocks)
+  if (last_basic_block != n_basic_blocks)
     abort ();
 
   label_value_list = lvl;
@@ -635,6 +634,7 @@ find_basic_blocks (f, nregs, file)
     }
 
   n_basic_blocks = count_basic_blocks (f);
+  last_basic_block = 0;
   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 
diff --git a/gcc/cfgcleanup.c b/gcc/cfgcleanup.c
index a2ff17d6981..2e6e02daba7 100644
--- a/gcc/cfgcleanup.c
+++ b/gcc/cfgcleanup.c
@@ -688,7 +688,6 @@ merge_blocks_move_predecessor_nojumps (a, b)
      basic_block a, b;
 {
   rtx barrier;
-  int index;
 
   barrier = next_nonnote_insn (a->end);
   if (GET_CODE (barrier) != BARRIER)
@@ -714,14 +713,7 @@ merge_blocks_move_predecessor_nojumps (a, b)
     fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
 	     a->index, b->index);
 
-  /* Swap the records for the two blocks around.  Although we are deleting B,
-     A is now where B was and we want to compact the BB array from where
-     A used to be.  */
-  BASIC_BLOCK (a->index) = b;
-  BASIC_BLOCK (b->index) = a;
-  index = a->index;
-  a->index = b->index;
-  b->index = index;
+  /* Swap the records for the two blocks around.  */
 
   unlink_block (a);
   link_block (a, b->prev_bb);
@@ -1755,13 +1747,10 @@ delete_unreachable_blocks ()
 {
   bool changed = false;
   basic_block b, next_bb;
-  int j = 0;
 
   find_unreachable_blocks ();
 
-  /* Delete all unreachable basic blocks.  Do compaction concurrently,
-     as otherwise we can wind up with O(N^2) behaviour here when we
-     have oodles of dead code.  */
+  /* Delete all unreachable basic blocks.  */
 
   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
     {
@@ -1769,18 +1758,10 @@ delete_unreachable_blocks ()
 
       if (!(b->flags & BB_REACHABLE))
 	{
-	  flow_delete_block_noexpunge (b);
-	  expunge_block_nocompact (b);
+	  flow_delete_block (b);
 	  changed = true;
 	}
-      else
-	{
-	  BASIC_BLOCK (j) = b;
-	  b->index = j++;
-	}
     }
-  n_basic_blocks = j;
-  basic_block_info->num_elements = j;
 
   if (changed)
     tidy_fallthru_edges ();
@@ -1806,6 +1787,9 @@ cleanup_cfg (mode)
 	  && !reload_completed)
 	delete_trivially_dead_insns (get_insns(), max_reg_num ());
     }
+
+  compact_blocks ();
+
   while (try_optimize_cfg (mode))
     {
       delete_unreachable_blocks (), changed = true;
diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index 79f7c0a403a..4509fa49de7 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -336,22 +336,12 @@ create_basic_block (head, end, after)
      basic_block after;
 {
   basic_block bb;
-  int i;
-  int index = after->index + 1;
+  int index = last_basic_block++;
 
-  /* Place the new block just after the block being split.  */
-  VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+  /* Place the new block just after the end.  */
+  VARRAY_GROW (basic_block_info, last_basic_block);
 
-  /* Some parts of the compiler expect blocks to be number in
-     sequential order so insert the new block immediately after the
-     block being split..  */
-  for (i = n_basic_blocks - 1; i > index; --i)
-    {
-      basic_block tmp = BASIC_BLOCK (i - 1);
-
-      BASIC_BLOCK (i) = tmp;
-      tmp->index = i;
-    }
+  n_basic_blocks++;
 
   bb = create_basic_block_structure (index, head, end, NULL, after);
   bb->aux = NULL;
@@ -435,7 +425,7 @@ flow_delete_block (b)
 {
   int deleted_handler = flow_delete_block_noexpunge (b);
 
-  /* Remove the basic block from the array, and compact behind it.  */
+  /* Remove the basic block from the array.  */
   expunge_block (b);
 
   return deleted_handler;
@@ -1210,12 +1200,19 @@ back_edge_of_syntactic_loop_p (bb1, bb2)
 {
   rtx insn;
   int count = 0;
+  basic_block bb;
 
-  if (bb1->index > bb2->index)
-    return false;
-  else if (bb1->index == bb2->index)
+  if (bb1 == bb2)
     return true;
 
+  /* ??? Could we guarantee that bb indices are monotone, so that we could
+     just compare them?  */
+  for (bb = bb1; bb && bb != bb2; bb = bb->next_bb)
+    continue;
+
+  if (!bb)
+    return false;
+
   for (insn = bb1->end; insn != bb2->head && count >= 0;
        insn = NEXT_INSN (insn))
     if (GET_CODE (insn) == NOTE)
@@ -1708,7 +1705,7 @@ verify_flow_info ()
   basic_block *bb_info, *last_visited;
   size_t *edge_checksum;
   rtx x;
-  int i, num_bb_notes, err = 0;
+  int num_bb_notes, err = 0;
   basic_block bb, last_bb_seen;
 
   bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
@@ -1734,21 +1731,6 @@ verify_flow_info ()
 	  err = 1;
 	}
 
-      /* For now, also check that we didn't change the order.  */
-      if (bb != EXIT_BLOCK_PTR && bb->index != last_bb_seen->index + 1)
-	{
-	  error ("Wrong order of blocks %d and %d",
-		 last_bb_seen->index, bb->index);
-	  err = 1;
-	}
-
-      if (bb == EXIT_BLOCK_PTR && last_bb_seen->index != n_basic_blocks - 1)
-	{
-	  error ("Only %d of %d blocks in chain",
-		 last_bb_seen->index + 1, n_basic_blocks);
-	  err = 1;
-	}
-
       last_bb_seen = bb;
     }
 
@@ -2065,10 +2047,10 @@ verify_flow_info ()
       edge_checksum[e->dest->index + 2] -= (size_t) e;
   }
 
-  for (i = -2; i < n_basic_blocks; ++i)
-    if (edge_checksum[i + 2])
+  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+    if (edge_checksum[bb->index + 2])
       {
-	error ("basic block %i edge lists are corrupted", i);
+	error ("basic block %i edge lists are corrupted", bb->index);
 	err = 1;
       }
 
@@ -2079,7 +2061,7 @@ verify_flow_info ()
     {
       if (NOTE_INSN_BASIC_BLOCK_P (x))
 	{
-	  basic_block bb = NOTE_BASIC_BLOCK (x);
+	  bb = NOTE_BASIC_BLOCK (x);
 
 	  num_bb_notes++;
 	  if (bb != last_bb_seen->next_bb)
diff --git a/gcc/flow.c b/gcc/flow.c
index a4dbe1ef14c..17a2662d154 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -1108,9 +1108,8 @@ calculate_global_regs_live (blocks_in, blocks_out, flags)
     }
   else
     {
-      for (i = 0; i < n_basic_blocks; ++i)
+      FOR_EACH_BB (bb)
 	{
-	  basic_block bb = BASIC_BLOCK (i);
 	  *--qhead = bb;
 	  bb->aux = bb;
 	}
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index b444f3b24d3..4ed1494416e 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -111,14 +111,6 @@ static int dead_or_predicable		PARAMS ((basic_block, basic_block,
 						 basic_block, basic_block, int));
 static void noce_emit_move_insn		PARAMS ((rtx, rtx));
 
-/* Abuse the basic_block AUX field to store the original block index,
-   as well as a flag indicating that the block should be rescaned for
-   life analysis.  */
-
-#define SET_ORIG_INDEX(BB,I)	((BB)->aux = (void *)((size_t)(I)))
-#define ORIG_INDEX(BB)		((size_t)(BB)->aux)
-
-
 /* Count the number of non-jump active insns in BB.  */
 
 static int
@@ -2279,6 +2271,7 @@ find_if_case_1 (test_bb, then_edge, else_edge)
   basic_block then_bb = then_edge->dest;
   basic_block else_bb = else_edge->dest, new_bb;
   edge then_succ = then_bb->succ;
+  int then_bb_index;
 
   /* THEN has one successor.  */
   if (!then_succ || then_succ->succ_next != NULL)
@@ -2319,11 +2312,15 @@ find_if_case_1 (test_bb, then_edge, else_edge)
 		    then_bb->global_live_at_end, BITMAP_IOR);
   
   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
+  then_bb_index = then_bb->index;
+  flow_delete_block (then_bb);
   /* Make rest of code believe that the newly created block is the THEN_BB
-     block we are going to remove.  */
+     block we removed.  */
   if (new_bb)
-    new_bb->aux = then_bb->aux;
-  flow_delete_block (then_bb);
+    {
+      new_bb->index = then_bb_index;
+      BASIC_BLOCK (then_bb_index) = new_bb;
+    }
   /* We've possibly created jump to next insn, cleanup_cfg will solve that
      later.  */
 
@@ -2366,8 +2363,8 @@ find_if_case_2 (test_bb, then_edge, else_edge)
   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
     ;
   else if (else_succ->dest->index < 0
-	   || TEST_BIT (post_dominators[ORIG_INDEX (then_bb)], 
-			ORIG_INDEX (else_succ->dest)))
+	   || TEST_BIT (post_dominators[then_bb->index], 
+			else_succ->dest->index))
     ;
   else
     return FALSE;
@@ -2706,10 +2703,6 @@ if_convert (x_life_data_ok)
   if (life_data_ok)
     clear_bb_flags ();
 
-  /* Record initial block numbers.  */
-  FOR_EACH_BB (bb)
-    SET_ORIG_INDEX (bb, bb->index);
-
   /* Go through each of the basic blocks looking for things to convert.  */
   FOR_EACH_BB (bb)
     while (find_if_header (bb))
diff --git a/gcc/lcm.c b/gcc/lcm.c
index ff0af92f0fa..2630cf317dc 100644
--- a/gcc/lcm.c
+++ b/gcc/lcm.c
@@ -1290,7 +1290,7 @@ optimize_mode_switching (file)
 
 #ifdef NORMAL_MODE
   /* Restore the special status of EXIT_BLOCK.  */
-  n_basic_blocks--;
+  last_basic_block--;
   VARRAY_POP (basic_block_info);
   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
 #endif
diff --git a/gcc/predict.c b/gcc/predict.c
index 34045c4d7be..a5131d4a475 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -1206,8 +1206,6 @@ estimate_bb_frequencies (loops)
       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 	BLOCK_INFO (bb)->tovisit = 1;
 
-      BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
-      BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
       propagate_freq (ENTRY_BLOCK_PTR);
 
       memcpy (&freq_max, &real_zero, sizeof (real_zero));
diff --git a/gcc/profile.c b/gcc/profile.c
index dcc75c0d5f8..8f7d5ef97a6 100644
--- a/gcc/profile.c
+++ b/gcc/profile.c
@@ -831,6 +831,9 @@ branch_prob ()
   num_edges = NUM_EDGES (el);
   alloc_aux_for_edges (sizeof (struct edge_info));
 
+  /* The basic blocks are expected to be numbered sequentially.  */
+  compact_blocks ();
+
   ignored_edges = 0;
   for (i = 0 ; i < num_edges ; i++)
     {
diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c
index dc9c3041c84..e2ea6b76117 100644
--- a/gcc/sched-rgn.c
+++ b/gcc/sched-rgn.c
@@ -680,7 +680,7 @@ find_rgns (edge_list, dom)
   in_stack = sbitmap_alloc (last_basic_block);
   sbitmap_zero (in_stack);
 
-  for (i = 0; i < n_basic_blocks; i++)
+  for (i = 0; i < last_basic_block; i++)
     max_hdr[i] = -1;
 
   /* DFS traversal to find inner loops in the cfg.  */