cfg merge part 24 - real datastructure for dominance information.

Jan Hubicka jh@suse.cz
Thu Jun 20 06:37:00 GMT 2002


> On Thu, Jun 20, 2002 at 08:34:38AM +0200, Jan Hubicka wrote:
> > Would be the patch OK with the reference added? (I can do it after the
> > exams, but that will take another two or three hours)
> 
> With the reference added, the style issues addressed, 
> and function comments added.
I've done all of this.  THe comments for ET-trees are not very
descriptive, but I guess without reading the paper one should not modify
the structure anyway.

OK now?  Bootstrapping/regtesting in progress, but since I didn't
changed single line of code I guess it will pass.

Mon Jun 10 20:42:34 CEST 2002  Jan Hubicka  <jh@suse.cz>
			       Pavel Nejedly  <bim@atrey.karlin.mff.cuni.cz>

	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.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.903
diff -c -3 -p -r1.903 Makefile.in
*** Makefile.in	19 Jun 2002 19:00:09 -0000	1.903
--- Makefile.in	20 Jun 2002 12:37:17 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 736,742 ****
   sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o		   \
   stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
   tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
!  $(GGC) $(out_object_file) $(EXTRA_OBJS)
  
  BACKEND = main.o libbackend.a
  
--- 736,742 ----
   sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o		   \
   stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
   tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
!  et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
  
  BACKEND = main.o libbackend.a
  
*************** cfgcleanup.o : cfgcleanup.c $(CONFIG_H) 
*** 1543,1549 ****
  cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h
  dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
!    $(BASIC_BLOCK_H)
  combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
     insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
     $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h $(TM_P_H)
--- 1543,1550 ----
  cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h
  dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
!    $(BASIC_BLOCK_H) et-forest.h
! et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) et-forest.h
  combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
     insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
     $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h $(TM_P_H)
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.153
diff -c -3 -p -r1.153 basic-block.h
*** basic-block.h	10 Jun 2002 22:33:06 -0000	1.153
--- basic-block.h	20 Jun 2002 12:37:17 -0000
*************** extern void clear_edges			PARAMS ((void)
*** 350,355 ****
--- 350,359 ----
  extern void mark_critical_edges		PARAMS ((void));
  extern rtx first_insn_after_basic_block_note	PARAMS ((basic_block));
  
+ /* Dominator information for basic blocks.  */
+ 
+ typedef struct dominance_info *dominance_info;
+ 
  /* Structure to hold information for each natural loop.  */
  struct loop
  {
*************** struct loops
*** 498,504 ****
    struct cfg
    {
      /* The bitmap vector of dominators or NULL if not computed.  */
!     sbitmap *dom;
  
      /* The ordering of the basic blocks in a depth first search.  */
      int *dfs_order;
--- 502,508 ----
    struct cfg
    {
      /* The bitmap vector of dominators or NULL if not computed.  */
!     dominance_info dom;
  
      /* The ordering of the basic blocks in a depth first search.  */
      int *dfs_order;
*************** enum cdi_direction
*** 770,776 ****
    CDI_POST_DOMINATORS
  };
  
! extern void calculate_dominance_info	PARAMS ((int *, sbitmap *,
! 						 enum cdi_direction));
! 
  #endif /* GCC_BASIC_BLOCK_H */
--- 774,794 ----
    CDI_POST_DOMINATORS
  };
  
! extern dominance_info calculate_dominance_info	PARAMS ((enum cdi_direction));
! extern void free_dominance_info			PARAMS ((dominance_info));
! extern basic_block nearest_common_dominator	PARAMS ((dominance_info,
! 						 basic_block, basic_block));
! extern void set_immediate_dominator	PARAMS ((dominance_info,
! 						 basic_block, basic_block));
! extern basic_block get_immediate_dominator	PARAMS ((dominance_info,
! 						 basic_block));
! extern bool dominated_by_p	PARAMS ((dominance_info, basic_block, basic_block));
! extern int get_dominated_by PARAMS ((dominance_info, basic_block, basic_block **));
! extern void add_to_dominance_info PARAMS ((dominance_info, basic_block));
! extern void delete_from_dominance_info PARAMS ((dominance_info, basic_block));
! basic_block recount_dominator PARAMS ((dominance_info, basic_block));
! extern void redirect_immediate_dominators PARAMS ((dominance_info, basic_block,
! 						 basic_block));
! void iterate_fix_dominators PARAMS ((dominance_info, basic_block *, int));
! extern void verify_dominators PARAMS ((dominance_info));
  #endif /* GCC_BASIC_BLOCK_H */
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgloop.c,v
retrieving revision 1.14
diff -c -3 -p -r1.14 cfgloop.c
*** cfgloop.c	1 Jun 2002 09:24:41 -0000	1.14
--- cfgloop.c	20 Jun 2002 12:37:18 -0000
*************** static void flow_loop_exit_edges_find	PA
*** 36,42 ****
  static int flow_loop_nodes_find		PARAMS ((basic_block, struct loop *));
  static void flow_loop_pre_header_scan	PARAMS ((struct loop *));
  static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
! 						      const sbitmap *));
  static int flow_loop_level_compute	PARAMS ((struct loop *));
  static int flow_loops_level_compute	PARAMS ((struct loops *));
  static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
--- 36,42 ----
  static int flow_loop_nodes_find		PARAMS ((basic_block, struct loop *));
  static void flow_loop_pre_header_scan	PARAMS ((struct loop *));
  static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
! 						      dominance_info));
  static int flow_loop_level_compute	PARAMS ((struct loop *));
  static int flow_loops_level_compute	PARAMS ((struct loops *));
  static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
*************** flow_loops_free (loops)
*** 224,230 ****
        loops->parray = NULL;
  
        if (loops->cfg.dom)
! 	sbitmap_vector_free (loops->cfg.dom);
  
        if (loops->cfg.dfs_order)
  	free (loops->cfg.dfs_order);
--- 224,230 ----
        loops->parray = NULL;
  
        if (loops->cfg.dom)
! 	free_dominance_info (loops->cfg.dom);
  
        if (loops->cfg.dfs_order)
  	free (loops->cfg.dfs_order);
*************** flow_loop_pre_header_scan (loop)
*** 415,421 ****
  static basic_block
  flow_loop_pre_header_find (header, dom)
       basic_block header;
!      const sbitmap *dom;
  {
    basic_block pre_header;
    edge e;
--- 415,421 ----
  static basic_block
  flow_loop_pre_header_find (header, dom)
       basic_block header;
!      dominance_info dom;
  {
    basic_block pre_header;
    edge e;
*************** flow_loop_pre_header_find (header, dom)
*** 428,434 ****
        basic_block node = e->src;
  
        if (node != ENTRY_BLOCK_PTR
! 	  && ! TEST_BIT (dom[node->index], header->index))
  	{
  	  if (pre_header == NULL)
  	    pre_header = node;
--- 428,434 ----
        basic_block node = e->src;
  
        if (node != ENTRY_BLOCK_PTR
! 	  && ! dominated_by_p (dom, node, header))
  	{
  	  if (pre_header == NULL)
  	    pre_header = node;
*************** make_forwarder_block (bb, redirect_latch
*** 645,657 ****
  static void
  canonicalize_loop_headers ()
  {
!   sbitmap *dom;
    basic_block header;
    edge e;
    
    /* Compute the dominators.  */
!   dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
!   calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
  
    alloc_aux_for_blocks (sizeof (int));
    alloc_aux_for_edges (sizeof (int));
--- 645,656 ----
  static void
  canonicalize_loop_headers ()
  {
!   dominance_info dom;
    basic_block header;
    edge e;
    
    /* Compute the dominators.  */
!   dom = calculate_dominance_info (CDI_DOMINATORS);
  
    alloc_aux_for_blocks (sizeof (int));
    alloc_aux_for_edges (sizeof (int));
*************** canonicalize_loop_headers ()
*** 670,676 ****
  	    have_abnormal_edge = 1;
  
  	  if (latch != ENTRY_BLOCK_PTR
! 	      && TEST_BIT (dom[latch->index], header->index))
  	    {
  	      num_latches++;
  	      LATCH_EDGE (e) = 1;
--- 669,675 ----
  	    have_abnormal_edge = 1;
  
  	  if (latch != ENTRY_BLOCK_PTR
! 	      && dominated_by_p (dom, latch, header))
  	    {
  	      num_latches++;
  	      LATCH_EDGE (e) = 1;
*************** canonicalize_loop_headers ()
*** 747,753 ****
  
    free_aux_for_blocks ();
    free_aux_for_edges ();
!   sbitmap_vector_free (dom);
  }
  
  /* Find all the natural loops in the function and save in LOOPS structure and
--- 746,752 ----
  
    free_aux_for_blocks ();
    free_aux_for_edges ();
!   free_dominance_info (dom);
  }
  
  /* Find all the natural loops in the function and save in LOOPS structure and
*************** flow_loops_find (loops, flags)
*** 765,774 ****
    int num_loops;
    edge e;
    sbitmap headers;
!   sbitmap *dom;
    int *dfs_order;
    int *rc_order;
!   basic_block header, bb;
  
    /* This function cannot be repeatedly called with different
       flags to build up the loop information.  The loop tree
--- 764,774 ----
    int num_loops;
    edge e;
    sbitmap headers;
!   dominance_info dom;
    int *dfs_order;
    int *rc_order;
!   basic_block header;
!   basic_block bb;
  
    /* This function cannot be repeatedly called with different
       flags to build up the loop information.  The loop tree
*************** flow_loops_find (loops, flags)
*** 790,797 ****
    canonicalize_loop_headers ();
  
    /* Compute the dominators.  */
!   loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
!   calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
  
    /* Count the number of loop headers.  This should be the
       same as the number of natural loops.  */
--- 790,796 ----
    canonicalize_loop_headers ();
  
    /* Compute the dominators.  */
!   dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS);
  
    /* Count the number of loop headers.  This should be the
       same as the number of natural loops.  */
*************** flow_loops_find (loops, flags)
*** 824,831 ****
  	     node (header) that dominates all the nodes in the
  	     loop.  It also has single back edge to the header
  	     from a latch node.  */
! 	  if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index],
! 						    header->index))
  	    {
  	      /* Shared headers should be eliminated by now.  */
  	      if (more_latches)
--- 823,829 ----
  	     node (header) that dominates all the nodes in the
  	     loop.  It also has single back edge to the header
  	     from a latch node.  */
! 	  if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
  	    {
  	      /* Shared headers should be eliminated by now.  */
  	      if (more_latches)
*************** flow_loops_find (loops, flags)
*** 899,905 ****
  	      basic_block latch = e->src;
  
  	      if (latch != ENTRY_BLOCK_PTR
! 		  && TEST_BIT (dom[latch->index], header->index))
  		{
  		  loop->latch = latch;
  		  break;
--- 897,903 ----
  	      basic_block latch = e->src;
  
  	      if (latch != ENTRY_BLOCK_PTR
! 		  && dominated_by_p (dom, latch, header))
  		{
  		  loop->latch = latch;
  		  break;
*************** flow_loops_find (loops, flags)
*** 925,931 ****
    else
      {
        loops->cfg.dom = NULL;
!       sbitmap_vector_free (dom);
      }
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
--- 923,929 ----
    else
      {
        loops->cfg.dom = NULL;
!       free_dominance_info (dom);
      }
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/dominance.c,v
retrieving revision 1.10
diff -c -3 -p -r1.10 dominance.c
*** dominance.c	27 May 2002 13:45:19 -0000	1.10
--- dominance.c	20 Jun 2002 12:37:18 -0000
***************
*** 38,44 ****
--- 38,56 ----
  #include "rtl.h"
  #include "hard-reg-set.h"
  #include "basic-block.h"
+ #include "error.h"
+ #include "et-forest.h"
  
+ struct dominance_info
+ {
+   et_forest_t forest;
+   varray_type varray;
+ };
+ 
+ #define BB_NODE(info, bb) \
+   ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
+ #define SET_BB_NODE(info, bb, node) \
+   (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
  
  /* We name our nodes with integers, beginning with 1.  Zero is reserved for
     'undefined' or 'end of list'.  The name of each node is given by the dfs
*************** static TBB eval				PARAMS ((struct dom_i
*** 113,120 ****
  static void link_roots			PARAMS ((struct dom_info *, TBB, TBB));
  static void calc_idoms			PARAMS ((struct dom_info *,
  						 enum cdi_direction));
! static void idoms_to_doms		PARAMS ((struct dom_info *,
! 						 sbitmap *));
  
  /* Helper macro for allocating and initializing an array,
     for aesthetic reasons.  */
--- 125,131 ----
  static void link_roots			PARAMS ((struct dom_info *, TBB, TBB));
  static void calc_idoms			PARAMS ((struct dom_info *,
  						 enum cdi_direction));
! void debug_dominance_info		PARAMS ((dominance_info));
  
  /* Helper macro for allocating and initializing an array,
     for aesthetic reasons.  */
*************** calc_idoms (di, reverse)
*** 531,580 ****
        di->dom[v] = di->dom[di->dom[v]];
  }
  
- /* Convert the information about immediate dominators (in DI) to sets of all
-    dominators (in DOMINATORS).  */
- 
- static void
- idoms_to_doms (di, dominators)
-      struct dom_info *di;
-      sbitmap *dominators;
- {
-   TBB i, e_index;
-   int bb, bb_idom;
-   sbitmap_vector_zero (dominators, last_basic_block);
-   /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
-      in the list of (post)-doms, so remember that in e_index.  */
-   e_index = di->dfs_order[last_basic_block];
- 
-   for (i = 1; i <= di->nodes; i++)
-     {
-       if (i == e_index)
- 	continue;
-       bb = di->dfs_to_bb[i]->index;
- 
-       if (di->dom[i] && (di->dom[i] != e_index))
- 	{
- 	  bb_idom = di->dfs_to_bb[di->dom[i]]->index;
- 	  sbitmap_copy (dominators[bb], dominators[bb_idom]);
- 	}
-       else
- 	{
- 	  /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
- 	     If it is a child of ENTRY_BLOCK that's OK, and it's only
- 	     dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
- 	     means, it is unreachable.  That case has been disallowed in the
- 	     building of the DFS tree, so we are save here.  For the reverse
- 	     flow graph it means, it has no children, so, to be compatible
- 	     with the old code, we set the post_dominators to all one.  */
- 	  if (!di->dom[i])
- 	    {
- 	      sbitmap_ones (dominators[bb]);
- 	    }
- 	}
-       SET_BIT (dominators[bb], bb);
-     }
- }
- 
  /* The main entry point into this module.  IDOM is an integer array with room
     for last_basic_block integers, DOMS is a preallocated sbitmap array having
     room for last_basic_block^2 bits, and POST is true if the caller wants to
--- 542,547 ----
*************** idoms_to_doms (di, dominators)
*** 587,623 ****
     Either IDOM or DOMS may be NULL (meaning the caller is not interested in
     immediate resp. all dominators).  */
  
! void
! calculate_dominance_info (idom, doms, reverse)
!      int *idom;
!      sbitmap *doms;
       enum cdi_direction reverse;
  {
    struct dom_info di;
  
-   if (!doms && !idom)
-     return;
    init_dom_info (&di);
    calc_dfs_tree (&di, reverse);
    calc_idoms (&di, reverse);
  
!   if (idom)
      {
!       basic_block b;
  
!       FOR_EACH_BB (b)
  	{
! 	  TBB d = di.dom[di.dfs_order[b->index]];
  
! 	  /* The old code didn't modify array elements of nodes having only
! 	     itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
! 	     (d==1).  */
! 	  if (d > 1)
! 	    idom[b->index] = di.dfs_to_bb[d]->index;
  	}
      }
!   if (doms)
!     idoms_to_doms (&di, doms);
  
!   free_dom_info (&di);
  }
--- 554,812 ----
     Either IDOM or DOMS may be NULL (meaning the caller is not interested in
     immediate resp. all dominators).  */
  
! dominance_info
! calculate_dominance_info (reverse)
       enum cdi_direction reverse;
  {
    struct dom_info di;
+   dominance_info info;
+   basic_block b;
+ 
+   /* allocate structure for dominance information.  */
+   info = xmalloc (sizeof (struct dominance_info));
+   info->forest = et_forest_create ();
+   VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
+ 
+   /* Add the two well-known basic blocks.  */
+   SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
+ 							  ENTRY_BLOCK_PTR));
+   SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
+ 							 EXIT_BLOCK_PTR));
+   FOR_EACH_BB (b)
+     SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
  
    init_dom_info (&di);
    calc_dfs_tree (&di, reverse);
    calc_idoms (&di, reverse);
  
! 
!   FOR_EACH_BB (b)
      {
!       TBB d = di.dom[di.dfs_order[b->index]];
! 
!       if (di.dfs_to_bb[d])
!         et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
!     }
! 
!   free_dom_info (&di);
!   return info;
! }
! 
! /* Free dominance information.  */
! void
! free_dominance_info (info)
!      dominance_info info;
! {
!   basic_block bb;
! 
!   /* Allow users to create new basic block without setting up the dominance
!      information for them.  */
!   FOR_EACH_BB (bb)
!     if (bb->index < (int)(info->varray->num_elements - 2)
! 	&& BB_NODE (info, bb))
!       delete_from_dominance_info (info, bb);
!   delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
!   delete_from_dominance_info (info, EXIT_BLOCK_PTR);
!   et_forest_delete (info->forest);
!   VARRAY_GROW (info->varray, 0);
!   free (info);
! }
! 
! /* Return the immediate dominator of basic block BB.  */
! basic_block
! get_immediate_dominator (dom, bb)
!      dominance_info dom;
!      basic_block bb;
! {
!   return et_forest_node_value (dom->forest,
! 			       et_forest_parent (dom->forest,
! 						 BB_NODE (dom, bb)));
! }
! 
! /* Set the immediate dominator of the block possibly removing
!    existing edge.  NULL can be used to remove any edge.  */
! inline void
! set_immediate_dominator (dom, bb, dominated_by)
!      dominance_info dom;
!      basic_block bb, dominated_by;
! {
!   void *aux_bb_node;
!   et_forest_node_t bb_node = BB_NODE (dom, bb);
! 
!   aux_bb_node = et_forest_parent (dom->forest, bb_node);
!   if (aux_bb_node)
!     et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
!   if (dominated_by != NULL)
!     {
!       if (bb == dominated_by)
! 	abort ();
!       if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
! 	abort ();
!     }
! }
! 
! /* Store all basic blocks dominated by BB into BBS and return their number.  */
! int
! get_dominated_by (dom, bb, bbs)
!      dominance_info dom;
!      basic_block bb;
!      basic_block **bbs;
! {
!   int n, i;
! 
!   *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
!   n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
!   for (i = 0; i < n; i++)
!    (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
!   return n;
! }
! 
! /* Redirect all edges pointing to BB to TO.  */
! void
! redirect_immediate_dominators (dom, bb, to)
!      dominance_info dom;
!      basic_block bb;
!      basic_block to;
! {
!   et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
!   et_forest_node_t node = BB_NODE (dom, bb);
!   et_forest_node_t node2 = BB_NODE (dom, to);
!   int n = et_forest_enumerate_sons (dom->forest, node, bbs);
!   int i;
! 
!   for (i = 0; i < n; i++)
!     {
!       et_forest_remove_edge (dom->forest, node, bbs[i]);
!       et_forest_add_edge (dom->forest, node2, bbs[i]);
!     }
!   free (bbs);
! }
! 
! /* Find first basic block in the tree dominating both BB1 and BB2.  */
! basic_block
! nearest_common_dominator (dom, bb1, bb2)
!      dominance_info dom;
!      basic_block bb1;
!      basic_block bb2;
! {
!   if (!bb1)
!     return bb2;
!   if (!bb2)
!     return bb1;
!   return et_forest_node_value (dom->forest,
! 			       et_forest_common_ancestor (dom->forest,
! 							  BB_NODE (dom, bb1),
! 							  BB_NODE (dom,
! 								   bb2)));
! }
! 
! /* Return TRUE in case BB1 is dominated by BB2.  */
! bool
! dominated_by_p (dom, bb1, bb2)
!      dominance_info dom;
!      basic_block bb1;
!      basic_block bb2;
! {
!   return nearest_common_dominator (dom, bb1, bb2) == bb2;
! }
! 
! /* Verify invariants of dominator structure.  */
! void
! verify_dominators (dom)
!      dominance_info dom;
! {
!   int err = 0;
!   basic_block bb;
! 
!   FOR_EACH_BB (bb)
!     {
!       basic_block dom_bb;
  
!       dom_bb = recount_dominator (dom, bb);
!       if (dom_bb != get_immediate_dominator (dom, bb))
  	{
! 	  error ("dominator of %d should be %d, not %d",
! 	   bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
! 	  err = 1;
! 	}
!     }
!   if (err)
!     abort ();
! }
! 
! /* Recount dominator of BB.  */
! basic_block
! recount_dominator (dom, bb)
!      dominance_info dom;
!      basic_block bb;
! {
!    basic_block dom_bb = NULL;
!    edge e;
! 
!    for (e = bb->pred; e; e = e->pred_next)
!      {
!        if (!dominated_by_p (dom, e->src, bb))
!          dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
!      }
  
!    return dom_bb;
! }
! 
! /* Iteratively recount dominators of BBS. The change is supposed to be local
!    and not to grow further.  */
! void
! iterate_fix_dominators (dom, bbs, n)
!      dominance_info dom;
!      basic_block *bbs;
!      int n;
! {
!   int i, changed = 1;
!   basic_block old_dom, new_dom;
! 
!   while (changed)
!     {
!       changed = 0;
!       for (i = 0; i < n; i++)
! 	{
! 	  old_dom = get_immediate_dominator (dom, bbs[i]);
! 	  new_dom = recount_dominator (dom, bbs[i]);
! 	  if (old_dom != new_dom)
! 	    {
! 	      changed = 1;
! 	      set_immediate_dominator (dom, bbs[i], new_dom);
! 	    }
  	}
      }
! }
  
! void
! add_to_dominance_info (dom, bb)
!      dominance_info dom;
!      basic_block bb;
! {
!   VARRAY_GROW (dom->varray, last_basic_block + 3);
! #ifdef ENABLE_CHECKING
!   if (BB_NODE (dom, bb))
!     abort ();
! #endif
!   SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
! }
! 
! void
! delete_from_dominance_info (dom, bb)
!      dominance_info dom;
!      basic_block bb;
! {
!   et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
!   SET_BB_NODE (dom, bb, NULL);
! }
! 
! void
! debug_dominance_info (dom)
!   dominance_info dom;
! {
!   basic_block bb, bb2;
!   FOR_EACH_BB (bb)
!     if ((bb2 = get_immediate_dominator (dom, bb)))
!       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
  }
Index: et-forest.c
===================================================================
RCS file: et-forest.c
diff -N et-forest.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- et-forest.c	20 Jun 2002 12:37:18 -0000
***************
*** 0 ****
--- 1,680 ----
+ /* ET-trees datastructure implementation.
+    Contributed by Pavel Nejedly
+    Copyright (C) 2002 Free Software Foundation, Inc.
+ 
+ This file is part of the libiberty library.
+ Libiberty is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+ 
+ Libiberty is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ Library General Public License for more details.
+ 
+ You should have received a copy of the GNU Library General Public
+ License along with libiberty; see the file COPYING.LIB.  If
+ not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.  
+ 
+   The ET-forest structure is described in:
+     D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
+     J.  G'omput. System Sci., 26(3):362 381, 1983.
+ */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "et-forest.h"
+ 
+ struct et_forest_occurrence;
+ typedef struct et_forest_occurrence* et_forest_occurrence_t;
+ 
+ /* The ET-forest type.  */
+ struct et_forest
+ {
+   /* Linked list of nodes is used to destroy the structure.  */
+   int nnodes;
+ };
+ 
+ /* Single occurrence of node in ET-forest.  
+    A single node may have multiple occurrences.
+  */
+ struct et_forest_occurrence
+ {
+   /* Parent in the splay-tree.  */
+   et_forest_occurrence_t parent;
+ 
+   /* Children in the splay-tree.  */
+   et_forest_occurrence_t left, right;
+ 
+   /* Counts of vertices in the two splay-subtrees.  */
+   int count_left, count_right;
+ 
+   /* Next occurrence of this node in the sequence.  */
+   et_forest_occurrence_t next;
+ 
+   /* The node, which this occurrence is of.  */
+   et_forest_node_t node;
+ };
+ 
+ 
+ /* ET-forest node.  */
+ struct et_forest_node
+ {
+   et_forest_t forest;
+   void *value;
+ 
+   /* First and last occurrence of this node in the sequence.  */
+   et_forest_occurrence_t first, last;
+ };
+ 
+ 
+ static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
+ static void remove_all_occurrences PARAMS ((et_forest_node_t));
+ static inline et_forest_occurrence_t find_leftmost_node 
+                                PARAMS ((et_forest_occurrence_t));
+ static inline et_forest_occurrence_t find_rightmost_node 
+                                PARAMS ((et_forest_occurrence_t));
+ static int calculate_value PARAMS ((et_forest_occurrence_t));
+ 
+ /* Return leftmost node present in the tree roted by OCC.  */
+ static inline et_forest_occurrence_t
+ find_leftmost_node (occ)
+      et_forest_occurrence_t occ;
+ {
+   while (occ->left)
+     occ = occ->left;
+ 
+   return occ;
+ }
+ 
+ /* Return rightmost node present in the tree roted by OCC.  */
+ static inline et_forest_occurrence_t
+ find_rightmost_node (occ)
+      et_forest_occurrence_t occ;
+ {
+   while (occ->right)
+     occ = occ->right;
+   return occ;
+ }
+ 
+ 
+ /* Operation splay for splay tree structure representing ocuurences.  */
+ static et_forest_occurrence_t
+ splay (node)
+      et_forest_occurrence_t node;
+ {
+   et_forest_occurrence_t parent;
+   et_forest_occurrence_t grandparent;
+ 
+   while (1)
+     {
+       parent = node->parent;
+ 
+       if (! parent)
+ 	return node;  /* node == root.  */
+ 
+       grandparent = parent->parent;
+ 
+       if (! grandparent)
+ 	break;
+ 
+       /* Now there are four possible combinations:  */
+ 
+       if (node == parent->left)
+ 	{
+ 	  if (parent == grandparent->left)
+ 	    {
+ 	      et_forest_occurrence_t node1, node2;
+ 	      int count1, count2;
+ 
+ 	      node1 = node->right;
+ 	      count1 = node->count_right;
+ 	      node2 = parent->right;
+ 	      count2 = parent->count_right;
+ 
+ 	      grandparent->left = node2;
+ 	      grandparent->count_left = count2;
+ 	      if (node2)
+ 		node2->parent = grandparent;
+ 	      parent->left = node1;
+ 	      parent->count_left = count1;
+ 	      if (node1)
+ 		node1->parent = parent;
+ 	      parent->right = grandparent;
+ 	      parent->count_right = count2 + grandparent->count_right + 1;
+ 	      node->right = parent;
+ 	      node->count_right = count1 + parent->count_right + 1;
+ 
+ 	      node->parent = grandparent->parent;
+ 	      parent->parent = node;
+ 	      grandparent->parent = parent;
+ 
+ 	      if (node->parent)
+ 		{
+ 		  if (node->parent->left == grandparent)
+ 		    node->parent->left = node;
+ 		  else
+ 		    node->parent->right = node;
+ 		}
+ 	    }
+ 	  else
+ 	    {
+ 	      /* parent == grandparent->right && node == parent->left*/
+ 	      et_forest_occurrence_t node1, node2;
+ 	      int count1, count2;
+ 
+ 	      node1 = node->left;
+ 	      count1 = node->count_left;
+ 	      node2 = node->right;
+ 	      count2 = node->count_right;
+ 
+ 	      grandparent->right = node1;
+ 	      grandparent->count_right = count1;
+ 	      if (node1)
+ 		node1->parent = grandparent;
+ 	      parent->left = node2;
+ 	      parent->count_left = count2;
+ 	      if (node2)
+ 		node2->parent = parent;
+ 	      node->left = grandparent;
+ 	      node->count_left = grandparent->count_left + count1 + 1;
+ 	      node->right = parent;
+ 	      node->count_right = parent->count_right + count2 + 1;
+ 
+ 	      node->parent = grandparent->parent;
+ 	      parent->parent = node;
+ 	      grandparent->parent = node;
+ 
+ 	      if (node->parent)
+ 		{
+ 		  if (node->parent->left == grandparent)
+ 		    node->parent->left = node;
+ 		  else
+ 		    node->parent->right = node;
+ 		}
+ 	    }
+ 	}
+       else
+ 	{
+ 	  /* node == parent->right.  */
+ 	  if (parent == grandparent->left)
+ 	    {
+ 	      et_forest_occurrence_t node1, node2;
+ 	      int count1, count2;
+ 
+ 	      node1 = node->left;
+ 	      count1 = node->count_left;
+ 	      node2 = node->right;
+ 	      count2 = node->count_right;
+ 
+ 	      parent->right = node1;
+ 	      parent->count_right = count1;
+ 	      if (node1)
+ 		node1->parent = parent;
+ 	      grandparent->left = node2;
+ 	      grandparent->count_left = count2;
+ 	      if (node2)
+ 		node2->parent = grandparent;
+ 	      node->left = parent;
+ 	      node->count_left = parent->count_left + count1 + 1;
+ 	      node->right = grandparent;
+ 	      node->count_right = grandparent->count_right + count2 + 1;
+ 
+ 	      node->parent = grandparent->parent;
+ 	      parent->parent = node;
+ 	      grandparent->parent = node;
+ 
+ 	      if (node->parent)
+ 		{
+ 		  if (node->parent->left == grandparent)
+ 		    node->parent->left = node;
+ 		  else
+ 		    node->parent->right = node;
+ 		}
+ 	    }
+ 	  else
+ 	    {
+ 	      /* parent == grandparent->right && node == parent->right*/
+ 	      et_forest_occurrence_t node1, node2;
+ 	      int count1, count2;
+ 
+ 	      node1 = node->left;
+ 	      count1 = node->count_left;
+ 	      node2 = parent->left;
+ 	      count2 = parent->count_left;
+ 
+ 	      grandparent->right = node2;
+ 	      grandparent->count_right = count2;
+ 	      if (node2)
+ 		node2->parent = grandparent;
+ 	      parent->right = node1;
+ 	      parent->count_right = count1;
+ 	      if (node1)
+ 		node1->parent = parent;
+ 	      parent->left = grandparent;
+ 	      parent->count_left = count2 + grandparent->count_left + 1;
+ 	      node->left = parent;
+ 	      node->count_left = count1 + parent->count_left + 1;
+ 
+ 	      node->parent = grandparent->parent;
+ 	      parent->parent = node;
+ 	      grandparent->parent = parent;
+ 
+ 	      if (node->parent)
+ 		{
+ 		  if (node->parent->left == grandparent)
+ 		    node->parent->left = node;
+ 		  else
+ 		    node->parent->right = node;
+ 		}
+ 	    }
+ 	}
+ 	  
+     }
+ 
+   /* parent == root.  */
+   /* There are two possible combinations:  */
+ 
+   if (node == parent->left)
+     {
+       et_forest_occurrence_t node1;
+       int count1;
+       
+       node1 = node->right;
+       count1 = node->count_right;
+ 
+       parent->left = node1;
+       parent->count_left = count1;
+       if (node1)
+ 	node1->parent = parent;
+       node->right = parent;
+       node->count_right = parent->count_right + 1 + count1;
+       node->parent = parent->parent;  /* the same as = 0;  */
+       parent->parent = node;
+ 
+       if (node->parent)
+ 	{
+ 	  if (node->parent->left == parent)
+ 	    node->parent->left = node;
+ 	  else
+ 	    node->parent->right = node;
+ 	}
+     } 
+   else 
+     {
+       /* node == parent->right.  */
+       et_forest_occurrence_t node1;
+       int count1;
+       
+       node1 = node->left;
+       count1 = node->count_left;
+ 
+       parent->right = node1;
+       parent->count_right = count1;
+       if (node1)
+ 	node1->parent = parent;
+       node->left = parent;
+       node->count_left = parent->count_left + 1 + count1;
+       node->parent = parent->parent;  /* the same as = 0;  */
+       parent->parent = node;
+ 
+       if (node->parent)
+ 	{
+ 	  if (node->parent->left == parent)
+ 	    node->parent->left = node;
+ 	  else
+ 	    node->parent->right = node;
+ 	}
+     }
+ 
+   return node;
+ }
+ 
+ /* Remove all occurences of the given node before destroying the node.  */
+ static void
+ remove_all_occurrences (forest_node)
+      et_forest_node_t forest_node;
+ {
+   et_forest_occurrence_t first = forest_node->first;
+   et_forest_occurrence_t last = forest_node->last;
+   et_forest_occurrence_t node;
+ 
+   splay (first);
+ 
+   if (first->left)
+     first->left->parent = 0;
+   if (first->right)
+     first->right->parent = 0;   
+ 
+   if (last != first)
+     {
+       splay (last);
+ 
+       if (last->left)
+ 	last->left->parent = 0;
+       if (last->right)
+ 	last->right->parent = 0;
+     }
+ 
+   if (last->right && first->left) /* actually, first->left would suffice.  */
+     {
+       /* Need to join them.  */
+       et_forest_occurrence_t prev_node, next_node;
+ 
+       prev_node = splay (find_rightmost_node (first->left));
+       next_node = splay (find_leftmost_node (last->right));
+       /* prev_node and next_node are consecutive occurencies
+ 	 of the same node.  */
+       if (prev_node->next != next_node)
+ 	abort ();
+ 
+       prev_node->right = next_node->right;
+       prev_node->count_right = next_node->count_right;
+       prev_node->next = next_node->next;
+       if (prev_node->right)
+ 	prev_node->right->parent = prev_node;
+ 
+       if (prev_node->node->last == next_node)
+ 	prev_node->node->last = prev_node;
+ 
+       free (next_node);
+     }
+ 
+   if (first != last)
+     {
+       node = first->next;
+ 
+       while (node != last)
+ 	{
+ 	  et_forest_occurrence_t next_node;
+ 
+ 	  splay (node);
+ 
+ 	  if (node->left)
+ 	    node->left->parent = 0;
+ 	  if (node->right)
+ 	    node->right->parent = 0;
+ 
+ 	  next_node = node->next;
+ 	  free (node);
+ 	  node = next_node;
+ 	}
+     }
+ 
+   free (first);
+   if (first != last)
+     free (last);
+ }
+ 
+ /* Calculate ET value of the given node.  */
+ static inline int
+ calculate_value (node)
+      et_forest_occurrence_t node;
+ {
+   int value = node->count_left;
+ 
+   while (node->parent)
+     {
+       if (node == node->parent->right)
+ 	value += node->parent->count_left + 1;
+ 
+       node = node->parent;
+     }
+ 
+   return value;
+ }
+ 
+ 
+ 
+ 
+ /* Create ET-forest structure.  */
+ et_forest_t
+ et_forest_create ()
+ {
+ 
+   et_forest_t forest = xmalloc (sizeof (struct et_forest));
+ 
+   forest->nnodes = 0;
+   return forest;
+ }
+ 
+ 
+ 
+ /* Deallocate the structure.  */
+ void 
+ et_forest_delete (forest)
+      et_forest_t forest;
+ {
+   if (forest->nnodes)
+     abort ();
+ 
+   free (forest);
+ }
+ 
+ /* Create new node with VALUE and return the edge.
+    Return NULL when memory allocation failed.  */
+ et_forest_node_t
+ et_forest_add_node (forest, value)
+      et_forest_t forest;
+      void *value;
+ {
+   /* Create node with one occurrence.  */
+   et_forest_node_t node;
+   et_forest_occurrence_t occ;
+ 
+   node = xmalloc (sizeof (struct et_forest_node));
+   occ = xmalloc (sizeof (struct et_forest_occurrence));
+ 
+   node->first = node->last = occ;
+   node->value = value;
+   forest->nnodes++;
+ 
+   occ->node = node;
+   occ->left = occ->right = occ->parent = 0;
+   occ->next = 0;
+   occ->count_left = occ->count_right = 0;
+   return node;
+ }
+ 
+ /* Add new edge to the tree, return 1 if succesfull.
+    0 indicates that creation of the edge will close the cycle in graph.  */
+ int
+ et_forest_add_edge (forest, parent_node, child_node)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t parent_node;
+      et_forest_node_t child_node;
+ {
+   et_forest_occurrence_t new_occ, parent_occ, child_occ;
+ 
+   if (! parent_node || ! child_node)
+     abort ();
+ 
+   parent_occ = parent_node->first;
+   child_occ = child_node->first;
+ 
+   splay (parent_occ);
+   splay (child_occ);
+ 
+   if (parent_occ->parent)
+     return 0; /* Both child and parent are in the same tree.  */
+ 
+   if (child_occ->left)
+     abort ();  /* child must be root of its containing tree.  */
+   
+   new_occ = xmalloc (sizeof (struct et_forest_occurrence));
+ 
+   new_occ->node = parent_node;
+   new_occ->left = child_occ;
+   new_occ->count_left = child_occ->count_right + 1; /* count_left is 0.  */
+   new_occ->right = parent_occ->right;
+   new_occ->count_right = parent_occ->count_right;
+   new_occ->parent = parent_occ;
+   new_occ->next = parent_occ->next;
+   child_occ->parent = new_occ;
+   parent_occ->right = new_occ;
+   parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
+   parent_occ->next = new_occ;
+   if (new_occ->right)
+     new_occ->right->parent = new_occ;
+ 
+   if (parent_node->last == parent_occ)
+     parent_node->last = new_occ;
+   return 1;
+ }
+ 
+ /* Remove NODE from the tree and all connected edges.  */
+ void
+ et_forest_remove_node (forest, node)
+      et_forest_t forest;
+      et_forest_node_t node;
+ {
+   remove_all_occurrences (node);
+   forest->nnodes--;
+ 
+   free (node);
+ }
+ 
+ /* Remove edge from the tree, return 1 if sucesfull,
+    0 indicates nonexisting edge.  */
+ int
+ et_forest_remove_edge (forest, parent_node, child_node)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t parent_node;
+      et_forest_node_t child_node;
+ {
+   et_forest_occurrence_t parent_pre_occ, parent_post_occ;
+ 
+   splay (child_node->first);
+ 
+   if (! child_node->first->left)
+     return 0;
+ 
+   parent_pre_occ = find_rightmost_node (child_node->first->left);
+   if (parent_pre_occ->node != parent_node)
+     abort ();
+ 
+   splay (parent_pre_occ);
+   parent_pre_occ->right->parent = 0;
+   
+   parent_post_occ = parent_pre_occ->next;
+   splay (parent_post_occ);
+ 
+   parent_post_occ->left->parent = 0;
+ 
+   parent_pre_occ->right = parent_post_occ->right;
+   parent_pre_occ->count_right = parent_post_occ->count_right;
+   if (parent_post_occ->right)
+     parent_post_occ->right->parent = parent_pre_occ;
+ 
+   parent_pre_occ->next = parent_post_occ->next;
+ 
+   if (parent_post_occ == parent_node->last)
+     parent_node->last = parent_pre_occ;
+ 
+   free (parent_post_occ);
+   return 1;
+ }
+ 
+ /* Return the parent of the NODE if any, NULL otherwise.  */
+ et_forest_node_t
+ et_forest_parent (forest, node)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t node;
+ {
+   splay (node->first);
+ 
+   if (node->first->left)
+     return find_rightmost_node (node->first->left)->node;
+   else
+     return 0;
+ }
+ 
+ 
+ /* Return nearest common ancestor of NODE1 and NODE2.
+    Return NULL of they are in different trees.  */
+ et_forest_node_t
+ et_forest_common_ancestor (forest, node1, node2)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t node1;
+      et_forest_node_t node2;
+ {
+   int value1, value2, max_value;
+   et_forest_node_t ancestor;
+ 
+   if (node1 == node2)
+     return node1;
+   
+   if (! node1 || ! node2)
+     abort ();
+ 
+   splay (node1->first);
+   splay (node2->first);
+ 
+   if (! node1->first->parent)  /* The two vertices are in different trees.  */
+     return 0;
+ 
+   value2 = calculate_value (node2->first);
+   value1 = calculate_value (node1->first);
+ 
+   if (value1 < value2)
+     {
+       ancestor = node1;
+       max_value = value2;
+     }
+   else
+     {
+       ancestor = node2;
+       max_value = value1;
+     }
+   
+   while (calculate_value (ancestor->last) < max_value)
+     {
+       /* Find parent node.  */
+       splay (ancestor->first);
+       ancestor = find_rightmost_node (ancestor->first->left) ->node;
+     }
+ 
+   return ancestor;
+ }
+ 
+ /* Return the value pointer of node set during it's creation.  */
+ void *
+ et_forest_node_value (forest, node)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t node;
+ {
+   /* Alloc threading NULL as a special node of the forest.  */
+   if (!node)
+     return NULL;
+   return node->value;
+ }
+ 
+ /* Find all sons of NODE and store them into ARRAY allocated by the caller.
+    Return number of nodes found.  */
+ int
+ et_forest_enumerate_sons (forest, node, array)
+      et_forest_t forest ATTRIBUTE_UNUSED;
+      et_forest_node_t node;
+      et_forest_node_t *array;
+ {
+   int n = 0;
+   et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
+ 
+   /* Parent is the rightmost node of the left successor.
+      Look for all occurences having no right succesor
+      and lookup the sons. */
+   while (occ != stop)
+     {
+       splay (occ);
+       if (occ->right)
+ 	{
+           occ1 = find_leftmost_node (occ->right);
+ 	  if (occ1->node->first == occ1)
+ 	    array[n++] = occ1->node;
+ 	}
+       occ = occ->next;
+     }
+   return n;
+ }
Index: et-forest.h
===================================================================
RCS file: et-forest.h
diff -N et-forest.h
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- et-forest.h	20 Jun 2002 12:37:18 -0000
***************
*** 0 ****
--- 1,83 ----
+ /* Et-forest data structure implementation.  
+    Copyright (C) 2002 Free Software Foundation, Inc.
+ 
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+ 
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU General Public License for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+ 
+ /* This package implements ET forest data structure. Each tree in 
+    the structure maintains a tree structure and offers logarithmic time
+    for tree operations (insertion and removal of nodes and edges) and
+    poly-logarithmic time for nearest common ancesto.
+  
+    ET tree strores its structue as a sequence of symbols obtained 
+    by dfs(root)
+ 
+    dfs (node) 
+    {
+      s = node;
+      for each child c of node do
+        s = concat (s, c, node);
+      return s;
+    }
+    
+    For example for tree
+  
+             1
+           / | \
+          2  3  4
+        / |
+       4  5
+  
+    the sequence is 1 2 4 2 5 3 1 3 1 4 1.
+  
+    The sequence is stored in a sligtly modified splay tree.
+    In order to support various types of node values, a hashtable
+    is used to convert node values to the internal representation.  */
+ 
+ #ifndef _ET_TREE_H
+ #define _ET_TREE_H
+ 
+ #include <ansidecl.h>
+ #include <stddef.h>
+ 
+ #ifdef __cplusplus
+ extern "C" {
+ #endif /* __cplusplus */
+ 
+ typedef struct et_forest *et_forest_t;
+ typedef struct et_forest_node *et_forest_node_t;
+ 
+ extern et_forest_t et_forest_create PARAMS ((void));
+ 
+ extern void et_forest_delete PARAMS ((et_forest_t));
+ 
+ extern et_forest_node_t et_forest_add_node PARAMS ((et_forest_t, void *));
+ extern int et_forest_add_edge PARAMS ((et_forest_t, et_forest_node_t, 
+ 					et_forest_node_t));
+ extern void et_forest_remove_node PARAMS ((et_forest_t, et_forest_node_t));
+ extern int et_forest_remove_edge PARAMS ((et_forest_t, et_forest_node_t,
+ 					   et_forest_node_t));
+ extern et_forest_node_t et_forest_parent PARAMS ((et_forest_t, et_forest_node_t));
+ extern et_forest_node_t et_forest_common_ancestor PARAMS ((et_forest_t,
+ 							  et_forest_node_t,
+ 							  et_forest_node_t));
+ extern void * et_forest_node_value PARAMS ((et_forest_t, et_forest_node_t));
+ extern int et_forest_enumerate_sons PARAMS ((et_forest_t, et_forest_node_t,
+ 					     et_forest_node_t *));
+ 
+ #ifdef __cplusplus
+ }
+ #endif /* __cplusplus */
+ 
+ #endif /* _ET_TREE_H */
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.205
diff -c -3 -p -r1.205 gcse.c
*** gcse.c	14 Jun 2002 16:25:35 -0000	1.205
--- gcse.c	20 Jun 2002 12:37:23 -0000
*************** static sbitmap *hoist_vbeout;
*** 5752,5758 ****
  static sbitmap *hoist_exprs;
  
  /* Dominator bitmaps.  */
! static sbitmap *dominators;
  
  /* ??? We could compute post dominators and run this algorithm in
     reverse to to perform tail merging, doing so would probably be
--- 5752,5758 ----
  static sbitmap *hoist_exprs;
  
  /* Dominator bitmaps.  */
! dominance_info dominators;
  
  /* ??? We could compute post dominators and run this algorithm in
     reverse to to perform tail merging, doing so would probably be
*************** alloc_code_hoist_mem (n_blocks, n_exprs)
*** 5775,5782 ****
    hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
    hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
    transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
- 
-   dominators = sbitmap_vector_alloc (n_blocks, n_blocks);
  }
  
  /* Free vars used for code hoisting analysis.  */
--- 5775,5780 ----
*************** free_code_hoist_mem ()
*** 5793,5799 ****
    sbitmap_vector_free (hoist_exprs);
    sbitmap_vector_free (transpout);
  
!   sbitmap_vector_free (dominators);
  }
  
  /* Compute the very busy expressions at entry/exit from each block.
--- 5791,5797 ----
    sbitmap_vector_free (hoist_exprs);
    sbitmap_vector_free (transpout);
  
!   free_dominance_info (dominators);
  }
  
  /* Compute the very busy expressions at entry/exit from each block.
*************** compute_code_hoist_data ()
*** 5842,5848 ****
    compute_local_properties (transp, comp, antloc, 0);
    compute_transpout ();
    compute_code_hoist_vbeinout ();
!   calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
    if (gcse_file)
      fprintf (gcse_file, "\n");
  }
--- 5840,5846 ----
    compute_local_properties (transp, comp, antloc, 0);
    compute_transpout ();
    compute_code_hoist_vbeinout ();
!   dominators = calculate_dominance_info (CDI_DOMINATORS);
    if (gcse_file)
      fprintf (gcse_file, "\n");
  }
*************** hoist_code ()
*** 5949,5955 ****
  		{
  		  /* Ignore self dominance.  */
  		  if (bb == dominated
! 		      || ! TEST_BIT (dominators[dominated->index], bb->index))
  		    continue;
  
  		  /* We've found a dominated block, now see if it computes
--- 5947,5953 ----
  		{
  		  /* Ignore self dominance.  */
  		  if (bb == dominated
! 		      || dominated_by_p (dominators, dominated, bb))
  		    continue;
  
  		  /* We've found a dominated block, now see if it computes
*************** hoist_code ()
*** 6006,6012 ****
  		{
  		  /* Ignore self dominance.  */
  		  if (bb == dominated
! 		      || ! TEST_BIT (dominators[dominated->index], bb->index))
  		    continue;
  
  		  /* We've found a dominated block, now see if it computes
--- 6004,6010 ----
  		{
  		  /* Ignore self dominance.  */
  		  if (bb == dominated
! 		      || ! dominated_by_p (dominators, dominated, bb))
  		    continue;
  
  		  /* We've found a dominated block, now see if it computes
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ifcvt.c,v
retrieving revision 1.95
diff -c -3 -p -r1.95 ifcvt.c
*** ifcvt.c	11 Jun 2002 12:21:45 -0000	1.95
--- ifcvt.c	20 Jun 2002 12:37:25 -0000
*************** static int num_removed_blocks;
*** 77,83 ****
  static bool life_data_ok;
  
  /* The post-dominator relation on the original block numbers.  */
! static sbitmap *post_dominators;
  
  /* Forward references.  */
  static int count_bb_insns		PARAMS ((basic_block));
--- 77,83 ----
  static bool life_data_ok;
  
  /* The post-dominator relation on the original block numbers.  */
! static dominance_info post_dominators;
  
  /* Forward references.  */
  static int count_bb_insns		PARAMS ((basic_block));
*************** merge_if_block (test_bb, then_bb, else_b
*** 1814,1819 ****
--- 1814,1821 ----
        if (combo_bb->global_live_at_end)
  	COPY_REG_SET (combo_bb->global_live_at_end,
  		      then_bb->global_live_at_end);
+       if (post_dominators)
+ 	delete_from_dominance_info (post_dominators, then_bb);
        merge_blocks_nomove (combo_bb, then_bb);
        num_removed_blocks++;
      }
*************** merge_if_block (test_bb, then_bb, else_b
*** 1823,1828 ****
--- 1825,1832 ----
       get their addresses taken.  */
    if (else_bb)
      {
+       if (post_dominators)
+ 	delete_from_dominance_info (post_dominators, else_bb);
        merge_blocks_nomove (combo_bb, else_bb);
        num_removed_blocks++;
      }
*************** merge_if_block (test_bb, then_bb, else_b
*** 1877,1882 ****
--- 1881,1888 ----
        if (combo_bb->global_live_at_end)
  	COPY_REG_SET (combo_bb->global_live_at_end,
  		      join_bb->global_live_at_end);
+       if (post_dominators)
+ 	delete_from_dominance_info (post_dominators, join_bb);
        merge_blocks_nomove (combo_bb, join_bb);
        num_removed_blocks++;
      }
*************** find_cond_trap (test_bb, then_edge, else
*** 2135,2140 ****
--- 2141,2148 ----
    remove_edge (trap_bb == then_bb ? then_edge : else_edge);
    if (trap_bb->pred == NULL)
      {
+       if (post_dominators)
+ 	delete_from_dominance_info (post_dominators, trap_bb);
        flow_delete_block (trap_bb);
        num_removed_blocks++;
      }
*************** find_if_case_1 (test_bb, then_edge, else
*** 2316,2321 ****
--- 2324,2331 ----
    
    new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
    then_bb_index = then_bb->index;
+   if (post_dominators)
+     delete_from_dominance_info (post_dominators, then_bb);
    flow_delete_block (then_bb);
    /* Make rest of code believe that the newly created block is the THEN_BB
       block we removed.  */
*************** find_if_case_2 (test_bb, then_edge, else
*** 2366,2373 ****
    if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
      ;
    else if (else_succ->dest->index < 0
! 	   || TEST_BIT (post_dominators[then_bb->index], 
! 			else_succ->dest->index))
      ;
    else
      return FALSE;
--- 2376,2383 ----
    if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
      ;
    else if (else_succ->dest->index < 0
! 	   || dominated_by_p (post_dominators, then_bb, 
! 			      else_succ->dest))
      ;
    else
      return FALSE;
*************** find_if_case_2 (test_bb, then_edge, else
*** 2393,2398 ****
--- 2403,2410 ----
  		    then_bb->global_live_at_start,
  		    else_bb->global_live_at_end, BITMAP_IOR);
    
+   if (post_dominators)
+     delete_from_dominance_info (post_dominators, else_bb);
    flow_delete_block (else_bb);
  
    num_removed_blocks++;
*************** if_convert (x_life_data_ok)
*** 2700,2707 ****
    post_dominators = NULL;
    if (HAVE_conditional_execution || life_data_ok)
      {
!       post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
!       calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
      }
    if (life_data_ok)
      clear_bb_flags ();
--- 2712,2718 ----
    post_dominators = NULL;
    if (HAVE_conditional_execution || life_data_ok)
      {
!       post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
      }
    if (life_data_ok)
      clear_bb_flags ();
*************** if_convert (x_life_data_ok)
*** 2712,2718 ****
        continue;
  
    if (post_dominators)
!     sbitmap_vector_free (post_dominators);
  
    if (rtl_dump_file)
      fflush (rtl_dump_file);
--- 2723,2729 ----
        continue;
  
    if (post_dominators)
!     free_dominance_info (post_dominators);
  
    if (rtl_dump_file)
      fflush (rtl_dump_file);
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.71
diff -c -3 -p -r1.71 predict.c
*** predict.c	1 Jun 2002 09:24:41 -0000	1.71
--- predict.c	20 Jun 2002 12:37:25 -0000
*************** Software Foundation, 59 Temple Place - S
*** 49,54 ****
--- 49,55 ----
  #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.  */
*************** static void estimate_loops_at_level	 PAR
*** 73,82 ****
  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 bool last_basic_block_p           PARAMS ((basic_block));
  static void compute_function_frequency	 PARAMS ((void));
  static void choose_function_section	 PARAMS ((void));
--- 74,85 ----
  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 *,
! 						  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));
*************** void
*** 408,421 ****
  estimate_probability (loops_info)
       struct loops *loops_info;
  {
!   sbitmap *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);
  
    /* Try to predict out blocks in a loop that are not part of a
       natural loop.  */
--- 411,423 ----
  estimate_probability (loops_info)
       struct loops *loops_info;
  {
!   dominance_info dominators, post_dominators;
    basic_block bb;
    int i;
  
!   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.  */
*************** estimate_probability (loops_info)
*** 495,502 ****
  	  /* 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))
  	    {
  	      rtx insn;
  
--- 497,504 ----
  	  /* 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
! 	      && dominated_by_p (dominators, e->dest, e->src)
! 	      && !dominated_by_p (post_dominators, e->src, e->dest))
  	    {
  	      rtx insn;
  
*************** estimate_probability (loops_info)
*** 613,621 ****
  	&& bb->succ->succ_next != NULL)
        combine_predictions_for_insn (bb->end, bb);
  
!   sbitmap_vector_free (post_dominators);
!   sbitmap_vector_free (dominators);
  
    estimate_bb_frequencies (loops_info);
  }
  
--- 615,624 ----
  	&& bb->succ->succ_next != NULL)
        combine_predictions_for_insn (bb->end, bb);
  
!   free_dominance_info (post_dominators);
!   free_dominance_info (dominators);
  
+   remove_fake_edges ();
    estimate_bb_frequencies (loops_info);
  }
  
*************** static void
*** 717,724 ****
  process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
       basic_block bb;
       int *heads;
!      int *dominators;
!      sbitmap *post_dominators;
       int pred;
       int flags;
  {
--- 720,727 ----
  process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
       basic_block bb;
       int *heads;
!      dominance_info dominators;
!      dominance_info post_dominators;
       int pred;
       int flags;
  {
*************** process_note_prediction (bb, heads, domi
*** 733,759 ****
        /* 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];
        int head;
  
!       while (heads[next_ai] < 0)
  	{
! 	  if (!TEST_BIT (post_dominators[next_ai], bb->index))
  	    break;
! 	  heads[next_ai] = ai;
  	  ai = next_ai;
! 	  next_ai = dominators[next_ai];
  	}
!       if (!TEST_BIT (post_dominators[next_ai], bb->index))
! 	head = next_ai;
        else
! 	head = heads[next_ai];
!       while (next_ai != bb->index)
  	{
  	  next_ai = ai;
! 	  ai = heads[ai];
! 	  heads[next_ai] = head;
  	}
      }
    y = heads[bb->index];
--- 736,765 ----
        /* 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).  */
!       basic_block ai = bb;
!       basic_block next_ai = get_immediate_dominator (dominators, bb);
        int head;
  
!       while (heads[next_ai->index] < 0)
  	{
! 	  if (!dominated_by_p (post_dominators, next_ai, bb))
  	    break;
! 	  heads[next_ai->index] = ai->index;
  	  ai = next_ai;
! 	  next_ai = get_immediate_dominator (dominators, next_ai);
  	}
!       if (!dominated_by_p (post_dominators, next_ai, bb))
! 	head = next_ai->index;
        else
! 	head = heads[next_ai->index];
!       while (next_ai != bb)
  	{
  	  next_ai = ai;
! 	  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];
*************** process_note_prediction (bb, heads, domi
*** 764,770 ****
      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))
        predict_edge_def (e, pred, taken);
  }
  
--- 770,776 ----
      return;
    for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
      if (e->dest->index >= 0
! 	&& dominated_by_p (post_dominators, e->dest, bb))
        predict_edge_def (e, pred, taken);
  }
  
*************** static void
*** 776,783 ****
  process_note_predictions (bb, heads, dominators, post_dominators)
       basic_block bb;
       int *heads;
!      int *dominators;
!      sbitmap *post_dominators;
  {
    rtx insn;
    edge e;
--- 782,789 ----
  process_note_predictions (bb, heads, dominators, post_dominators)
       basic_block bb;
       int *heads;
!      dominance_info dominators;
!      dominance_info post_dominators;
  {
    rtx insn;
    edge e;
*************** void
*** 838,855 ****
  note_prediction_to_br_prob ()
  {
    basic_block bb;
!   sbitmap *post_dominators;
!   int *dominators, *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);
  
    heads = xmalloc (sizeof (int) * last_basic_block);
    memset (heads, -1, sizeof (int) * last_basic_block);
--- 844,858 ----
  note_prediction_to_br_prob ()
  {
    basic_block bb;
!   dominance_info post_dominators, dominators;
!   int *heads;
  
    /* To enable handling of noreturn blocks.  */
    add_noreturn_fake_exit_edges ();
    connect_infinite_loops_to_exit ();
  
!   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);
*************** note_prediction_to_br_prob ()
*** 860,867 ****
    FOR_EACH_BB (bb)
      process_note_predictions (bb, heads, dominators, post_dominators);
  
!   sbitmap_vector_free (post_dominators);
!   free (dominators);
    free (heads);
  
    remove_fake_edges ();
--- 863,870 ----
    FOR_EACH_BB (bb)
      process_note_predictions (bb, heads, dominators, post_dominators);
  
!   free_dominance_info (post_dominators);
!   free_dominance_info (dominators);
    free (heads);
  
    remove_fake_edges ();
Index: sched-rgn.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/sched-rgn.c,v
retrieving revision 1.46
diff -c -3 -p -r1.46 sched-rgn.c
*** sched-rgn.c	14 Jun 2002 18:57:40 -0000	1.46
--- sched-rgn.c	20 Jun 2002 12:37:26 -0000
*************** static int *containing_rgn;
*** 153,159 ****
  
  void debug_regions PARAMS ((void));
  static void find_single_block_region PARAMS ((void));
! static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
  static int too_large PARAMS ((int, int *, int *));
  
  extern void debug_live PARAMS ((int, int));
--- 153,159 ----
  
  void debug_regions PARAMS ((void));
  static void find_single_block_region PARAMS ((void));
! static void find_rgns PARAMS ((struct edge_list *, dominance_info));
  static int too_large PARAMS ((int, int *, int *));
  
  extern void debug_live PARAMS ((int, int));
*************** too_large (block, num_bbs, num_insns)
*** 624,630 ****
  static void
  find_rgns (edge_list, dom)
       struct edge_list *edge_list;
!      sbitmap *dom;
  {
    int *max_hdr, *dfs_nr, *stack, *degree;
    char no_loops = 1;
--- 624,630 ----
  static void
  find_rgns (edge_list, dom)
       struct edge_list *edge_list;
!      dominance_info dom;
  {
    int *max_hdr, *dfs_nr, *stack, *degree;
    char no_loops = 1;
*************** find_rgns (edge_list, dom)
*** 837,843 ****
  		    {
  		      /* Now verify that the block is dominated by the loop
  			 header.  */
! 		      if (!TEST_BIT (dom[jbb->index], bb->index))
  			break;
  		    }
  		}
--- 837,843 ----
  		    {
  		      /* Now verify that the block is dominated by the loop
  			 header.  */
! 		      if (!dominated_by_p (dom, jbb, bb))
  			break;
  		    }
  		}
*************** init_regions ()
*** 2909,2919 ****
  	}
        else
  	{
! 	  sbitmap *dom;
  	  struct edge_list *edge_list;
  
- 	  dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
- 
  	  /* The scheduler runs after flow; therefore, we can't blindly call
  	     back into find_basic_blocks since doing so could invalidate the
  	     info in global_live_at_start.
--- 2909,2917 ----
  	}
        else
  	{
! 	  dominance_info dom;
  	  struct edge_list *edge_list;
  
  	  /* The scheduler runs after flow; therefore, we can't blindly call
  	     back into find_basic_blocks since doing so could invalidate the
  	     info in global_live_at_start.
*************** init_regions ()
*** 2928,2934 ****
  	  edge_list = create_edge_list ();
  
  	  /* Compute the dominators and post dominators.  */
! 	  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
  
  	  /* build_control_flow will return nonzero if it detects unreachable
  	     blocks or any other irregularity with the cfg which prevents
--- 2926,2932 ----
  	  edge_list = create_edge_list ();
  
  	  /* Compute the dominators and post dominators.  */
! 	  dom = calculate_dominance_info (CDI_DOMINATORS);
  
  	  /* build_control_flow will return nonzero if it detects unreachable
  	     blocks or any other irregularity with the cfg which prevents
*************** init_regions ()
*** 2946,2952 ****
  
  	  /* For now.  This will move as more and more of haifa is converted
  	     to using the cfg code in flow.c.  */
! 	  free (dom);
  	}
      }
  
--- 2944,2950 ----
  
  	  /* For now.  This will move as more and more of haifa is converted
  	     to using the cfg code in flow.c.  */
! 	  free_dominance_info (dom);
  	}
      }
  
Index: ssa-dce.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa-dce.c,v
retrieving revision 1.21
diff -c -3 -p -r1.21 ssa-dce.c
*** ssa-dce.c	12 Jun 2002 14:51:03 -0000	1.21
--- ssa-dce.c	20 Jun 2002 12:37:27 -0000
*************** static void set_control_dependent_block_
*** 98,110 ****
  static void control_dependent_block_to_edge_map_free
    PARAMS ((control_dependent_block_to_edge_map c));
  static void find_all_control_dependences
!   PARAMS ((struct edge_list *el, int *pdom,
  	   control_dependent_block_to_edge_map cdbte));
  static void find_control_dependence
!   PARAMS ((struct edge_list *el, int edge_index, int *pdom,
  	   control_dependent_block_to_edge_map cdbte));
  static basic_block find_pdom
!   PARAMS ((int *pdom, basic_block block));
  static int inherently_necessary_register_1
    PARAMS ((rtx *current_rtx, void *data));
  static int inherently_necessary_register
--- 98,110 ----
  static void control_dependent_block_to_edge_map_free
    PARAMS ((control_dependent_block_to_edge_map c));
  static void find_all_control_dependences
!   PARAMS ((struct edge_list *el, dominance_info pdom,
  	   control_dependent_block_to_edge_map cdbte));
  static void find_control_dependence
!   PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
  	   control_dependent_block_to_edge_map cdbte));
  static basic_block find_pdom
!   PARAMS ((dominance_info pdom, basic_block block));
  static int inherently_necessary_register_1
    PARAMS ((rtx *current_rtx, void *data));
  static int inherently_necessary_register
*************** control_dependent_block_to_edge_map_free
*** 218,224 ****
  static void
  find_all_control_dependences (el, pdom, cdbte)
     struct edge_list *el;
!    int *pdom;
     control_dependent_block_to_edge_map cdbte;
  {
    int i;
--- 218,224 ----
  static void
  find_all_control_dependences (el, pdom, cdbte)
     struct edge_list *el;
!    dominance_info pdom;
     control_dependent_block_to_edge_map cdbte;
  {
    int i;
*************** static void
*** 237,243 ****
  find_control_dependence (el, edge_index, pdom, cdbte)
     struct edge_list *el;
     int edge_index;
!    int *pdom;
     control_dependent_block_to_edge_map cdbte;
  {
    basic_block current_block;
--- 237,243 ----
  find_control_dependence (el, edge_index, pdom, cdbte)
     struct edge_list *el;
     int edge_index;
!    dominance_info pdom;
     control_dependent_block_to_edge_map cdbte;
  {
    basic_block current_block;
*************** find_control_dependence (el, edge_index,
*** 266,272 ****
  
  static basic_block
  find_pdom (pdom, block)
!      int *pdom;
       basic_block block;
  {
    if (!block)
--- 266,272 ----
  
  static basic_block
  find_pdom (pdom, block)
!      dominance_info pdom;
       basic_block block;
  {
    if (!block)
*************** find_pdom (pdom, block)
*** 276,285 ****
  
    if (block == ENTRY_BLOCK_PTR)
      return ENTRY_BLOCK_PTR->next_bb;
!   else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK)
      return EXIT_BLOCK_PTR;
    else
!     return BASIC_BLOCK (pdom[block->index]);
  }
  
  /* Determine if the given CURRENT_RTX uses a hard register not
--- 276,290 ----
  
    if (block == ENTRY_BLOCK_PTR)
      return ENTRY_BLOCK_PTR->next_bb;
!   else if (block == EXIT_BLOCK_PTR)
      return EXIT_BLOCK_PTR;
    else
!     {
!       basic_block bb = get_immediate_dominator (pdom, block);
!       if (!bb)
! 	return EXIT_BLOCK_PTR;
!       return bb;
!     }
  }
  
  /* Determine if the given CURRENT_RTX uses a hard register not
*************** delete_insn_bb (insn)
*** 488,494 ****
  void
  ssa_eliminate_dead_code ()
  {
-   int i;
    rtx insn;
    basic_block bb;
    /* Necessary instructions with operands to explore.  */
--- 493,498 ----
*************** ssa_eliminate_dead_code ()
*** 497,503 ****
       edge.  "cdbte" abbreviates control dependent block to edge.  */
    control_dependent_block_to_edge_map cdbte;
   /* Element I is the immediate postdominator of block I.  */
!   int *pdom;
    struct edge_list *el;
  
    /* Initialize the data structures.  */
--- 501,507 ----
       edge.  "cdbte" abbreviates control dependent block to edge.  */
    control_dependent_block_to_edge_map cdbte;
   /* Element I is the immediate postdominator of block I.  */
!   dominance_info pdom;
    struct edge_list *el;
  
    /* Initialize the data structures.  */
*************** ssa_eliminate_dead_code ()
*** 510,523 ****
    connect_infinite_loops_to_exit ();
  
    /* Compute control dependence.  */
!   pdom = (int *) xmalloc (last_basic_block * sizeof (int));
!   for (i = 0; i < last_basic_block; ++i)
!     pdom[i] = INVALID_BLOCK;
!   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
!   /* Assume there is a path from each node to the exit block.  */
!   for (i = 0; i < last_basic_block; ++i)
!     if (pdom[i] == INVALID_BLOCK)
!       pdom[i] = EXIT_BLOCK;
    el = create_edge_list ();
    find_all_control_dependences (el, pdom, cdbte);
  
--- 514,520 ----
    connect_infinite_loops_to_exit ();
  
    /* Compute control dependence.  */
!   pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
    el = create_edge_list ();
    find_all_control_dependences (el, pdom, cdbte);
  
Index: ssa.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa.c,v
retrieving revision 1.52
diff -c -3 -p -r1.52 ssa.c
*** ssa.c	11 Jun 2002 12:21:57 -0000	1.52
--- ssa.c	20 Jun 2002 12:37:28 -0000
*************** struct rename_context;
*** 165,171 ****
  static inline rtx * phi_alternative
    PARAMS ((rtx, int));
  static void compute_dominance_frontiers_1
!   PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
  static void find_evaluations_1
    PARAMS ((rtx dest, rtx set, void *data));
  static void find_evaluations
--- 165,171 ----
  static inline rtx * phi_alternative
    PARAMS ((rtx, int));
  static void compute_dominance_frontiers_1
!   PARAMS ((sbitmap *frontiers, dominance_info idom, int bb, sbitmap done));
  static void find_evaluations_1
    PARAMS ((rtx dest, rtx set, void *data));
  static void find_evaluations
*************** static void apply_delayed_renames
*** 183,191 ****
  static int rename_insn_1
    PARAMS ((rtx *ptr, void *data));
  static void rename_block
!   PARAMS ((int b, int *idom));
  static void rename_registers
!   PARAMS ((int nregs, int *idom));
  
  static inline int ephi_add_node
    PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
--- 183,191 ----
  static int rename_insn_1
    PARAMS ((rtx *ptr, void *data));
  static void rename_block
!   PARAMS ((int b, dominance_info dom));
  static void rename_registers
!   PARAMS ((int nregs, dominance_info idom));
  
  static inline int ephi_add_node
    PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
*************** find_evaluations (evals, nregs)
*** 516,522 ****
  static void
  compute_dominance_frontiers_1 (frontiers, idom, bb, done)
       sbitmap *frontiers;
!      int *idom;
       int bb;
       sbitmap done;
  {
--- 516,522 ----
  static void
  compute_dominance_frontiers_1 (frontiers, idom, bb, done)
       sbitmap *frontiers;
!      dominance_info idom;
       int bb;
       sbitmap done;
  {
*************** compute_dominance_frontiers_1 (frontiers
*** 531,537 ****
       dominator tree (blocks dominated by this one) are children in the
       CFG, so check all blocks.  */
    FOR_EACH_BB (c)
!     if (idom[c->index] == bb && ! TEST_BIT (done, c->index))
        compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
  
    /* Find blocks conforming to rule (1) above.  */
--- 531,538 ----
       dominator tree (blocks dominated by this one) are children in the
       CFG, so check all blocks.  */
    FOR_EACH_BB (c)
!     if (get_immediate_dominator (idom, c)->index == bb
! 	&& ! TEST_BIT (done, c->index))
        compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
  
    /* Find blocks conforming to rule (1) above.  */
*************** compute_dominance_frontiers_1 (frontiers
*** 539,556 ****
      {
        if (e->dest == EXIT_BLOCK_PTR)
  	continue;
!       if (idom[e->dest->index] != bb)
  	SET_BIT (frontiers[bb], e->dest->index);
      }
  
    /* Find blocks conforming to rule (2).  */
    FOR_EACH_BB (c)
!     if (idom[c->index] == bb)
        {
  	int x;
  	EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
  	  {
! 	    if (idom[x] != bb)
  	      SET_BIT (frontiers[bb], x);
  	  });
        }
--- 540,557 ----
      {
        if (e->dest == EXIT_BLOCK_PTR)
  	continue;
!       if (get_immediate_dominator (idom, e->dest)->index != bb)
  	SET_BIT (frontiers[bb], e->dest->index);
      }
  
    /* Find blocks conforming to rule (2).  */
    FOR_EACH_BB (c)
!     if (get_immediate_dominator (idom, c)->index == bb)
        {
  	int x;
  	EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
  	  {
! 	    if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
  	      SET_BIT (frontiers[bb], x);
  	  });
        }
*************** compute_dominance_frontiers_1 (frontiers
*** 559,565 ****
  void
  compute_dominance_frontiers (frontiers, idom)
       sbitmap *frontiers;
!      int *idom;
  {
    sbitmap done = sbitmap_alloc (last_basic_block);
    sbitmap_zero (done);
--- 560,566 ----
  void
  compute_dominance_frontiers (frontiers, idom)
       sbitmap *frontiers;
!      dominance_info idom;
  {
    sbitmap done = sbitmap_alloc (last_basic_block);
    sbitmap_zero (done);
*************** gen_sequence ()
*** 1001,1007 ****
  static void
  rename_block (bb, idom)
       int bb;
!      int *idom;
  {
    basic_block b = BASIC_BLOCK (bb);
    edge e;
--- 1002,1008 ----
  static void
  rename_block (bb, idom)
       int bb;
!      dominance_info idom;
  {
    basic_block b = BASIC_BLOCK (bb);
    edge e;
*************** rename_block (bb, idom)
*** 1111,1117 ****
       dominator order.  */
  
    FOR_EACH_BB (c)
!     if (idom[c->index] == bb)
        rename_block (c->index, idom);
  
    /* Step Four: Update the sets to refer to their new register,
--- 1112,1118 ----
       dominator order.  */
  
    FOR_EACH_BB (c)
!     if (get_immediate_dominator (idom, c)->index == bb)
        rename_block (c->index, idom);
  
    /* Step Four: Update the sets to refer to their new register,
*************** rename_block (bb, idom)
*** 1137,1143 ****
  static void
  rename_registers (nregs, idom)
       int nregs;
!      int *idom;
  {
    VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
    ssa_rename_from_initialize ();
--- 1138,1144 ----
  static void
  rename_registers (nregs, idom)
       int nregs;
!      dominance_info idom;
  {
    VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
    ssa_rename_from_initialize ();
*************** convert_to_ssa ()
*** 1168,1174 ****
    sbitmap *idfs;
  
    /* Element I is the immediate dominator of block I.  */
!   int *idom;
  
    int nregs;
  
--- 1169,1175 ----
    sbitmap *idfs;
  
    /* Element I is the immediate dominator of block I.  */
!   dominance_info idom;
  
    int nregs;
  
*************** convert_to_ssa ()
*** 1182,1196 ****
       dead code.  We'll let the SSA optimizers do that.  */
    life_analysis (get_insns (), NULL, 0);
  
!   idom = (int *) alloca (last_basic_block * sizeof (int));
!   memset ((void *) idom, -1, (size_t) last_basic_block * sizeof (int));
!   calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
  
    if (rtl_dump_file)
      {
        fputs (";; Immediate Dominators:\n", rtl_dump_file);
        FOR_EACH_BB (bb)
! 	fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index, idom[bb->index]);
        fflush (rtl_dump_file);
      }
  
--- 1183,1196 ----
       dead code.  We'll let the SSA optimizers do that.  */
    life_analysis (get_insns (), NULL, 0);
  
!   idom = calculate_dominance_info (CDI_DOMINATORS);
  
    if (rtl_dump_file)
      {
        fputs (";; Immediate Dominators:\n", rtl_dump_file);
        FOR_EACH_BB (bb)
! 	fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index,
! 		 get_immediate_dominator (idom, bb)->index);
        fflush (rtl_dump_file);
      }
  
*************** convert_to_ssa ()
*** 1241,1246 ****
--- 1241,1247 ----
    in_ssa_form = 1;
  
    reg_scan (get_insns (), max_reg_num (), 1);
+   free_dominance_info (idom);
  }
  
  /* REG is the representative temporary of its partition.  Add it to the
Index: ssa.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa.h,v
retrieving revision 1.7
diff -c -3 -p -r1.7 ssa.h
*** ssa.h	4 Jun 2002 07:07:56 -0000	1.7
--- ssa.h	20 Jun 2002 12:37:28 -0000
*************** typedef int (*successor_phi_fn)         
*** 27,33 ****
  extern int for_each_successor_phi       PARAMS ((basic_block bb,
  						 successor_phi_fn,
  						 void *));
! void compute_dominance_frontiers	PARAMS ((sbitmap *frontiers, int *idom));
  extern int remove_phi_alternative	PARAMS ((rtx, basic_block));
  
  
--- 27,34 ----
  extern int for_each_successor_phi       PARAMS ((basic_block bb,
  						 successor_phi_fn,
  						 void *));
! void compute_dominance_frontiers	PARAMS ((sbitmap *frontiers,
! 						 dominance_info idom));
  extern int remove_phi_alternative	PARAMS ((rtx, basic_block));
  
  



More information about the Gcc-patches mailing list