[PATCH]: Cache immediate dominators

[Daniel Berlin <dberlin at dberlin dot org>]

In compiling expr.c on the tree-ssa-branch, get_dominated_by is called 258 
million times. This in terms leads to 258 million calls to splay and 
another helper routine, which take up 30 seconds.

This is, of course, unnecessary, unless the idom info has changed since 
the last time it was calculated.

This patch caches it, invalidating the idom cache for bb's when the idoms 
change.

It doesn't bother to cache the idom info for bb -1 or -2, since anything 
making absurd numbers of calls to determine domination of the entry or 
exit blocks is braindead anyway.

With this patch, the compilation time of expr.c for a profiled gcc at -O2 
goes from ~300 to 134 seconds (The 30 seconds i quoted above is what gprof 
claims).
splay and the other routine drop off the profile completely.

The only complete invalidation occurs when we call redirect_immediate_dominators.

--Dan

Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.10.2.1
diff -c -3 -p -w -B -b -r1.10.2.1 dominance.c
*** dominance.c	24 Jun 2002 21:37:55 -0000	1.10.2.1
--- dominance.c	15 Aug 2002 18:15:34 -0000
*************** struct dominance_info
*** 45,50 ****
--- 45,51 ----
  {
    et_forest_t forest;
    varray_type varray;
+   basic_block *idom;
  };
  
  #define BB_NODE(info, bb) \
*************** calculate_dominance_info (reverse)
*** 565,570 ****
--- 566,573 ----
    /* allocate structure for dominance information.  */
    info = xmalloc (sizeof (struct dominance_info));
    info->forest = et_forest_create ();
+   info->idom = xcalloc (last_basic_block, sizeof (basic_block));
+ 
    VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
  
    /* Add the two well-known basic blocks.  */
*************** free_dominance_info (info)
*** 609,614 ****
--- 612,618 ----
    delete_from_dominance_info (info, EXIT_BLOCK_PTR);
    et_forest_delete (info->forest);
    VARRAY_GROW (info->varray, 0);
+   free (info->idom);
    free (info);
  }
  
*************** get_immediate_dominator (dom, bb)
*** 618,626 ****
       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
--- 622,637 ----
       dominance_info dom;
       basic_block bb;
  {
!   basic_block answer;
!   if (bb->index >= 0 && dom->idom[bb->index] != NULL)
!     return dom->idom[bb->index];
!   answer =  et_forest_node_value (dom->forest,
  				  et_forest_parent (dom->forest,
  						    BB_NODE (dom, bb)));
+   if (bb->index >= 0)
+     dom->idom[bb->index] = answer;
+   return answer;
+ 
  }
  
  /* Set the immediate dominator of the block possibly removing
*************** set_immediate_dominator (dom, bb, domina
*** 643,648 ****
--- 654,661 ----
        if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
  	abort ();
      }
+   if (bb->index >= 0)
+     dom->idom[bb->index] = dominated_by;
  }
  
  /* Store all basic blocks dominated by BB into BBS and return their number.  */
*************** redirect_immediate_dominators (dom, bb, 
*** 674,679 ****
--- 687,693 ----
    int n = et_forest_enumerate_sons (dom->forest, node, bbs);
    int i;
    
+   memset (dom->idom, 0, last_basic_block * sizeof (basic_block));
    for (i = 0; i < n; i++)
      {
        et_forest_remove_edge (dom->forest, node, bbs[i]);
*************** add_to_dominance_info (dom, bb)
*** 785,795 ****
--- 799,812 ----
       basic_block bb;
  {
    VARRAY_GROW (dom->varray, last_basic_block + 3);
+   dom->idom = xrealloc (dom->idom, last_basic_block * sizeof (basic_block));
  #ifdef ENABLE_CHECKING
    if (BB_NODE (dom, bb))
      abort ();
  #endif
    SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
+   if (bb->index >= 0)
+     dom->idom[bb->index] = NULL;
  }
  
  void
*************** delete_from_dominance_info (dom, bb)
*** 798,803 ****
--- 815,822 ----
       basic_block bb;
  {
    et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
+   if (bb->index >= 0)
+     dom->idom[bb->index]  = NULL;
    SET_BB_NODE (dom, bb, NULL);
  }