Mon Jun 10 20:42:34 CEST 2002 Jan Hubicka <jh@suse.cz>

	* basic-block.h: Do not include et-forest.h
	(dominance_info): Declare as struct dominance-info.
	* cfglayout.c (cleanup_unconditional_jumps): Remove the edge before
	deleting block.
	* dominance.c (struct dominance_info): Define.
	(BB_NODE, SET_BB_NODE): New macros.
	(bb_hash_func, bb_eq_func): Kill.
	(calculate_dominace_info, free_dominacne_info, set_immediate_dominator,
	nearest_common_dominator, dominated_by_p, recount_dominator,
	add_to_dominance_info, delete_from_dominance_info): update for new
	representation.
	(get_dominated_by, redirect_immediate_dominators): Rewrite using
	enumerate_sons.
	* ifcvt.c (process_double_test_block, merge_if_block, find_cond_trap,
	find_if_case_1, find_if_case_2): Remove killed blocks from dominance
	structure.

	* et-forest.h: Update copyright; revamp all function to operate on
	nodes
	(et_forest_value): Kill.
	(et_forest_enumerate_sons, et_forest_node_value): New.
	* et-forest.c: Update copyright.
	* et-forest.h: Update copyright; revamp all function to operate on
	nodes
	(et_forest_value): Kill.
	(et_forest_enumerate_sons, et_forest_node_value): New.

	Thu Jun  6 22:43:43 CEST 2002  Jan Hubicka  <jh@suse.cz>

	* basic-block.h: Inlude et-forest.h
	(basic_block_def): Kill dominator.
	(dominance_info): New type.
	(loops): Use dominace_info.
	(dominace handling functions): Take dominace_info as argument
	instead of bitmaps.
	(create_preheader): Likewise.
	* cfg.c (entry_exit_blocks): Kill dominator.
	(dump_flow_info): Do not dump dominators.
	* cfglayout.c (cleanup_unconditonal_jumps): Delete deleted block from
	dominators.
	* cfgloop.c (flow_pre_header_find): Use dominacne_info.
	(flow_loops_pre_header_scan, make_forwarder_block,
	canonicale_loop_headers, flow_loops_find): Likewise.
	* dominance.c: Include error.h
	(idoms_to_doms): Kill.
	(bb_hash_func, bb_eq_func): New static functions.
	(debug_dominace_info): New global function.
	(calculate_dominance_info): Use new et forest structure.
	(free_dominace_info, get_immediate_dominator, set_immediate_dominator,
	get_dominated_by, redirect_immediate_dominators,
	nearest_common_dominator, dominated_by_p, verify_dominators,
	recount_dominator, iterate_fix_dominators, add_to_dominace_info,
	delete_from_dominance_info): New global functions.
	* gcse.c (domnators): CHange to dominance_info.
	(alloc_hoist_mem): Do not alloc dominators
	(free_code_hoist_mem): Use free_dominance_info.
	(compute_code_hoist_data): Use dominance_info.
	(hoist_code): Likewise.
	* ifcvt.c (post_dominators): Likewise.
	(find_if_case_2, if_convert): Likewise.
	* predict.c (process_note_predictions, process_note_prediction,
	estimate-probability): Likewise.
	* sched-rgn.c (find_rgns, init_regions): Likewise.
	* ssa-dce.c (find_all_control_dependences, fint_control_depemndence,
	find_pdom, delete_insn_bb, ssa_eliminate_dead_code): Likewise.
	* ssa.c (compute_dominance_frontiers_1, rename_block, rename_registers,
	find_evaluations, convert_to_ssa): Likewise.
	* ssa.h (compute_dominance_frontiers): Likewise.

	Thu Jun  6 22:57:34 CEST 2002  Pavel Nejedly <bim@atrey.karlin.mff.cuni.cz>

	* Makefile.in (et-forest.c): Add.
	* et-forest.c: New file.
	* at-forest.h: New file.


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

1 files changed, 42 insertions, 39 deletions

diff --git a/gcc/predict.c b/gcc/predict.c
index c00c86409f3..71950ee6766 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -49,6 +49,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "real.h"
 #include "params.h"
 #include "target.h"
+#include "loop.h"
 
 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
                    REAL_BB_FREQ_MAX.  */
@@ -73,10 +74,12 @@ static void estimate_loops_at_level	 PARAMS ((struct loop *loop));
 static void propagate_freq		 PARAMS ((struct loop *));
 static void estimate_bb_frequencies	 PARAMS ((struct loops *));
 static void counts_to_freqs		 PARAMS ((void));
-static void process_note_predictions	 PARAMS ((basic_block, int *, int *,
-						  sbitmap *));
-static void process_note_prediction	 PARAMS ((basic_block, int *, int *,
-						  sbitmap *, int, int));
+static void process_note_predictions	 PARAMS ((basic_block, int *,
+						  dominance_info,
+						  dominance_info));
+static void process_note_prediction	 PARAMS ((basic_block, int *, 
+						  dominance_info,
+						  dominance_info, int, int));
 static bool last_basic_block_p           PARAMS ((basic_block));
 static void compute_function_frequency	 PARAMS ((void));
 static void choose_function_section	 PARAMS ((void));
@@ -408,14 +411,13 @@ void
 estimate_probability (loops_info)
      struct loops *loops_info;
 {
-  sbitmap *dominators, *post_dominators;
+  dominance_info dominators, post_dominators;
   basic_block bb;
   int i;
 
-  dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
-  calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
+  connect_infinite_loops_to_exit ();
+  dominators = calculate_dominance_info (CDI_DOMINATORS);
+  post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
 
   /* Try to predict out blocks in a loop that are not part of a
      natural loop.  */
@@ -495,8 +497,8 @@ estimate_probability (loops_info)
 	  /* Look for block we are guarding (ie we dominate it,
 	     but it doesn't postdominate us).  */
 	  if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
-	      && TEST_BIT (dominators[e->dest->index], e->src->index)
-	      && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
+	      && dominated_by_p (dominators, e->dest, e->src)
+	      && !dominated_by_p (post_dominators, e->src, e->dest))
 	    {
 	      rtx insn;
 
@@ -613,9 +615,10 @@ estimate_probability (loops_info)
 	&& bb->succ->succ_next != NULL)
       combine_predictions_for_insn (bb->end, bb);
 
-  sbitmap_vector_free (post_dominators);
-  sbitmap_vector_free (dominators);
+  free_dominance_info (post_dominators);
+  free_dominance_info (dominators);
 
+  remove_fake_edges ();
   estimate_bb_frequencies (loops_info);
 }
 
@@ -717,8 +720,8 @@ static void
 process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
      basic_block bb;
      int *heads;
-     int *dominators;
-     sbitmap *post_dominators;
+     dominance_info dominators;
+     dominance_info post_dominators;
      int pred;
      int flags;
 {
@@ -733,27 +736,30 @@ process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
       /* This is first time we need this field in heads array; so
          find first dominator that we do not post-dominate (we are
          using already known members of heads array).  */
-      int ai = bb->index;
-      int next_ai = dominators[bb->index];
+      basic_block ai = bb;
+      basic_block next_ai = get_immediate_dominator (dominators, bb);
       int head;
 
-      while (heads[next_ai] < 0)
+      while (heads[next_ai->index] < 0)
 	{
-	  if (!TEST_BIT (post_dominators[next_ai], bb->index))
+	  if (!dominated_by_p (post_dominators, next_ai, bb))
 	    break;
-	  heads[next_ai] = ai;
+	  heads[next_ai->index] = ai->index;
 	  ai = next_ai;
-	  next_ai = dominators[next_ai];
+	  next_ai = get_immediate_dominator (dominators, next_ai);
 	}
-      if (!TEST_BIT (post_dominators[next_ai], bb->index))
-	head = next_ai;
+      if (!dominated_by_p (post_dominators, next_ai, bb))
+	head = next_ai->index;
       else
-	head = heads[next_ai];
-      while (next_ai != bb->index)
+	head = heads[next_ai->index];
+      while (next_ai != bb)
 	{
 	  next_ai = ai;
-	  ai = heads[ai];
-	  heads[next_ai] = head;
+	  if (heads[ai->index] == ENTRY_BLOCK)
+	    ai = ENTRY_BLOCK_PTR;
+	  else
+	    ai = BASIC_BLOCK (heads[ai->index]);
+	  heads[next_ai->index] = head;
 	}
     }
   y = heads[bb->index];
@@ -764,7 +770,7 @@ process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
     return;
   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
     if (e->dest->index >= 0
-	&& TEST_BIT (post_dominators[e->dest->index], bb->index))
+	&& dominated_by_p (post_dominators, e->dest, bb))
       predict_edge_def (e, pred, taken);
 }
 
@@ -776,8 +782,8 @@ static void
 process_note_predictions (bb, heads, dominators, post_dominators)
      basic_block bb;
      int *heads;
-     int *dominators;
-     sbitmap *post_dominators;
+     dominance_info dominators;
+     dominance_info post_dominators;
 {
   rtx insn;
   edge e;
@@ -838,18 +844,15 @@ void
 note_prediction_to_br_prob ()
 {
   basic_block bb;
-  sbitmap *post_dominators;
-  int *dominators, *heads;
+  dominance_info post_dominators, dominators;
+  int *heads;
 
   /* To enable handling of noreturn blocks.  */
   add_noreturn_fake_exit_edges ();
   connect_infinite_loops_to_exit ();
 
-  dominators = xmalloc (sizeof (int) * last_basic_block);
-  memset (dominators, -1, sizeof (int) * last_basic_block);
-  post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-  calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
-  calculate_dominance_info (dominators, NULL, CDI_DOMINATORS);
+  post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
+  dominators = calculate_dominance_info (CDI_DOMINATORS);
 
   heads = xmalloc (sizeof (int) * last_basic_block);
   memset (heads, -1, sizeof (int) * last_basic_block);
@@ -860,8 +863,8 @@ note_prediction_to_br_prob ()
   FOR_EACH_BB (bb)
     process_note_predictions (bb, heads, dominators, post_dominators);
 
-  sbitmap_vector_free (post_dominators);
-  free (dominators);
+  free_dominance_info (post_dominators);
+  free_dominance_info (dominators);
   free (heads);
 
   remove_fake_edges ();