Re: [tree-ssa] Cleanup and enhance dominator infrastructure

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > In message <F36A4AB3-2C4C-11D8-8CD9-000A95DA505C@dberlin.org>, Daniel Berlin wr
> > ites:
> >  >> oops.  Exactly the kind of problems I have expected when I have seen 
> >  >> you
> >  >> have created another interface to the dominator information.  IMHO it
> >  >> would be better to just keep the original one from the dominance.c (I
> >  >> know there are performance problems, but these are easy to fix).
> >  >>
> >  >
> >  >Please fix them then.
> >  >It would let me remove about 100-200 lines of tree-ssa-pre.c.
> > And do so without introducing compile-time regressions.
> > 
> > We've known for a while that the design of the dominator tree had its
> > share of problems.  Time to fix it.
> > 
> >  >
> >  >If you want to see a performance problem, changed fast_a_dominates_b to 
> >  >just use dominated_by_p, and compile 20001226-1.c, or any other large 
> >  >testcase.
> > Also include generate-3.4.ii from Gerald's testcase.
> 
> here is the patch.

as pointed out by Daniel, there is a mistake in the part of the patch in
tree-ssa-pre.c (I did not notice that the arguments of
fast_a_dominates_b are reversed wrto dominated_by_p).  The correct chunk
of the patch with this problem fixed is here; the patch still passes
regtesting (it did before as well, since we have no testcases for PRE in
the testsuite :-( ) and improves the compilation times as described in the
previous mail.

Zdenek

Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-pre.c,v
retrieving revision 1.1.4.115
diff -c -3 -p -r1.1.4.115 tree-ssa-pre.c
*** tree-ssa-pre.c	8 Dec 2003 12:58:22 -0000	1.1.4.115
--- tree-ssa-pre.c	14 Dec 2003 17:49:11 -0000
*************** static bool split_critical_edges (void);
*** 245,262 ****
  static void collect_expressions (basic_block, varray_type *);
  static int build_dfn_array (basic_block, int);
  static int eref_compare (const void *, const void *);
- static inline bool fast_a_dominates_b (basic_block, basic_block);
- static void build_dfs_id_array_1 (basic_block, int *);
- static void build_dfs_id_array (void);
  
  
  /* Bitmap of E-PHI predecessor operands have already been created. 
     We only create one phi-pred per block.  */
  static bitmap created_phi_preds;
  
- /* PRE dominance info.  */
- static dominance_info pre_idom;
- 
  /* PRE dominance frontiers.  */
  static bitmap *pre_dfs;
  
--- 245,256 ----
*************** ephi_at_block (basic_block bb)
*** 870,912 ****
      return NULL_TREE;
  }
  
- static int *dfs_id;
- static int *dfs_id_last;
- 
- /* Depth first ID calculation.
-    In order to not have to deal with the et-forest, which can be slow,
-    we calculate two arrays that can quickly tell us whether one block
-    dominates another.  One array tracks the dfs_id of each block.
-    The other array tracks the last dfs_id of the dominator children of
-    the block.  */
- 
- static void
- build_dfs_id_array_1 (basic_block bb, int *id)
- {
-   int i;
-   if (bb->index >= 0)
-     dfs_id[bb->index] = *id;
-   
-   ++(*id);
-   if (dom_children (bb))
-     EXECUTE_IF_SET_IN_BITMAP(dom_children (bb), 0, i,
-     {
-       build_dfs_id_array_1 (BASIC_BLOCK (i), id);
-     });
-   if (bb->index >= 0)
-     dfs_id_last[bb->index] = *id - 1;
-   
- }
- static void
- build_dfs_id_array (void)
- {
-   int id = 0;
-   dfs_id = xcalloc (last_basic_block + 1, sizeof (int));
-   dfs_id_last = xcalloc (last_basic_block + 1, sizeof (int));
-   build_dfs_id_array_1 (ENTRY_BLOCK_PTR, &id);
- }
- 
- 			       
  static int *dfn;
  
  /* Build a depth first numbering array to be used in sorting in
--- 864,869 ----
*************** static int *dfn;
*** 915,928 ****
  static int
  build_dfn_array (basic_block bb, int num)
  {
!   int i;
    if (bb->index >= 0)
      dfn[bb->index] = num;
!   if (dom_children (bb))
!     EXECUTE_IF_SET_IN_BITMAP (dom_children (bb), 0, i,
!     {
!       num = build_dfn_array (BASIC_BLOCK (i), ++num);
!     });
    return num;
  }
  
--- 872,886 ----
  static int
  build_dfn_array (basic_block bb, int num)
  {
!   basic_block son;
! 
    if (bb->index >= 0)
      dfn[bb->index] = num;
! 
!   for (son = first_dom_son (CDI_DOMINATORS, bb);
!        son;
!        son = next_dom_son (CDI_DOMINATORS, son))
!     num = build_dfn_array (son, ++num);
    return num;
  }
  
*************** eref_compare (const void *elem1, const v
*** 967,973 ****
      {
        if (dfn[bb1->index] == dfn[bb2->index])
  	{
! 	  if (dominated_by_p (pre_idom, bb1, bb2))
  	    return 1;
  	  else
  	    return -1;
--- 925,931 ----
      {
        if (dfn[bb1->index] == dfn[bb2->index])
  	{
! 	  if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
  	    return 1;
  	  else
  	    return -1;
*************** bool load_modified_phi_result (basic_blo
*** 1406,1412 ****
    basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (cr));
    if (defbb != bb)
      {
!       if (fast_a_dominates_b (defbb, bb))
  	return false;
      }
    else
--- 1364,1373 ----
    basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (cr));
    if (defbb != bb)
      {
!       if (!defbb)
! 	return true;
! 
!       if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
  	return false;
      }
    else
*************** process_delayed_rename (struct expr_info
*** 1556,1574 ****
      }
  }
  
- /* Return whether BB A dominates BB B without using the slow
-    et-forest all the time.  */
- 
- static inline bool 
- fast_a_dominates_b (basic_block bb1, basic_block bb2)
- {
-   if (!bb1 || !bb2 || bb1->index < 0 || bb2->index < 0)
-     return dominated_by_p (pre_idom, bb1, bb2);
-   
-   return (dfs_id[bb2->index] >= dfs_id[bb1->index])
-     && (dfs_id[bb2->index] <= dfs_id_last[bb1->index]);
- }
- 
  /* Renaming is done like Open64 does it.  Basically as the paper says, 
     except that we try to use earlier defined occurrences if they are
     available in order to keep the number of saves down.  */
--- 1517,1522 ----
*************** rename_1 (struct expr_info *ei)
*** 1590,1597 ****
        occur = VARRAY_TREE (ei->euses_dt_order, i);
        
        while (VARRAY_ACTIVE_SIZE (stack) > 0	     
! 	     && !fast_a_dominates_b (bb_for_stmt (VARRAY_TOP_TREE (stack)),
! 				     bb_for_stmt (occur)))
  	
  	VARRAY_POP (stack);
        if (VARRAY_TOP_TREE (stack) == NULL || VARRAY_ACTIVE_SIZE (stack) == 0)
--- 1538,1546 ----
        occur = VARRAY_TREE (ei->euses_dt_order, i);
        
        while (VARRAY_ACTIVE_SIZE (stack) > 0	     
! 	     && !dominated_by_p (CDI_DOMINATORS,
! 			     	 bb_for_stmt (occur),
! 				 bb_for_stmt (VARRAY_TOP_TREE (stack))))
  	
  	VARRAY_POP (stack);
        if (VARRAY_TOP_TREE (stack) == NULL || VARRAY_ACTIVE_SIZE (stack) == 0)
*************** reaching_def (tree var, tree currstmt, b
*** 1986,1992 ****
      }
    if (curruse != NULL_TREE)
      return curruse;
!   dom = get_immediate_dominator (pre_idom, bb);
    if (bb == ENTRY_BLOCK_PTR)
      {
        htab_t temp;
--- 1935,1941 ----
      }
    if (curruse != NULL_TREE)
      return curruse;
!   dom = get_immediate_dominator (CDI_DOMINATORS, bb);
    if (bb == ENTRY_BLOCK_PTR)
      {
        htab_t temp;
*************** finalize_1 (struct expr_info *ei)
*** 2094,2100 ****
        else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
  	{
  	  if (avdefs[nx] == NULL
! 	      || !dominated_by_p (pre_idom, bb_for_stmt (x), 
  				  bb_for_stmt (avdefs[nx])))
  	    {
  	      EREF_RELOAD (x) = false;
--- 2043,2049 ----
        else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
  	{
  	  if (avdefs[nx] == NULL
! 	      || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x), 
  				  bb_for_stmt (avdefs[nx])))
  	    {
  	      EREF_RELOAD (x) = false;
*************** static void 
*** 3101,3108 ****
  collect_expressions (basic_block block, varray_type *bexprsp)
  {
    size_t k;
-   int i;
    block_stmt_iterator j;
  
    varray_type bexprs = *bexprsp;
    
--- 3050,3057 ----
  collect_expressions (basic_block block, varray_type *bexprsp)
  {
    size_t k;
    block_stmt_iterator j;
+   basic_block son;
  
    varray_type bexprs = *bexprsp;
    
*************** collect_expressions (basic_block block, 
*** 3190,3201 ****
        process_left_occs_and_kills (bexprs, orig_expr);
      }
    *bexprsp = bexprs;
!   if (dom_children (block))
!     EXECUTE_IF_SET_IN_BITMAP (dom_children (block), 0, i,
!     {
!       collect_expressions (BASIC_BLOCK (i), bexprsp);
!     });
!   
  }
  
  /* Main entry point to the SSA-PRE pass.
--- 3139,3149 ----
        process_left_occs_and_kills (bexprs, orig_expr);
      }
    *bexprsp = bexprs;
! 
!   for (son = first_dom_son (CDI_DOMINATORS, block);
!        son;
!        son = next_dom_son (CDI_DOMINATORS, son))
!     collect_expressions (son, bexprsp);
  }
  
  /* Main entry point to the SSA-PRE pass.
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3228,3240 ****
                sizeof (struct ephi_use_entry), 30);
    VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
    VARRAY_TREE_INIT (added_phis, 1, "Added phis");
    /* Compute immediate dominators.  */
!   pre_idom = calculate_dominance_info (CDI_DOMINATORS);
  
    /* DCE screws the dom_children up, without bothering to fix it. So fix it. */
    currbbs = n_basic_blocks;
-   build_dominator_tree (pre_idom);
-   build_dfs_id_array ();
    dfn = xcalloc (last_basic_block + 1, sizeof (int));
    build_dfn_array (ENTRY_BLOCK_PTR, 0);
  
--- 3176,3187 ----
                sizeof (struct ephi_use_entry), 30);
    VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
    VARRAY_TREE_INIT (added_phis, 1, "Added phis");
+ 
    /* Compute immediate dominators.  */
!   calculate_dominance_info (CDI_DOMINATORS);
  
    /* DCE screws the dom_children up, without bothering to fix it. So fix it. */
    currbbs = n_basic_blocks;
    dfn = xcalloc (last_basic_block + 1, sizeof (int));
    build_dfn_array (ENTRY_BLOCK_PTR, 0);
  
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3245,3251 ****
    pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
    for (i = 0; i < currbbs; i++)
       pre_dfs[i] = BITMAP_XMALLOC ();
!   compute_dominance_frontiers (pre_dfs, pre_idom);
  
    created_phi_preds = BITMAP_XMALLOC ();
    
--- 3192,3198 ----
    pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
    for (i = 0; i < currbbs; i++)
       pre_dfs[i] = BITMAP_XMALLOC ();
!   compute_dominance_frontiers (pre_dfs);
  
    created_phi_preds = BITMAP_XMALLOC ();
    
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3289,3295 ****
    free_alloc_pool (euse_node_pool);
    free_alloc_pool (eref_node_pool);
    VARRAY_CLEAR (bexprs);
-   free_dominance_info (pre_idom);
    for (i = 0; i < currbbs; i++)
      BITMAP_XFREE (pre_dfs[i]);
    free (pre_dfs);
--- 3236,3241 ----
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3303,3310 ****
    if (bitmap_first_set_bit (vars_to_rename) != -1)
      rewrite_into_ssa (fndecl, vars_to_rename, TDI_pre);
    BITMAP_XFREE (vars_to_rename);
-   free (dfs_id);
-   free (dfs_id_last);
    free (dfn);
    timevar_pop (TV_TREE_PRE);
  }
--- 3249,3254 ----