Re: [PATCH]: Cache immediate dominators

[Mike Stump <mrs at apple dot com>]

On Thursday, August 15, 2002, at 01:46 PM, Daniel Berlin wrote:

> In compiling expr.c on the tree-ssa-branch, get_dominated_by is called 
> 258
> million times.
I was composing a message to complain about that function just the 
other day.  Didn't finish it...  well, here is most of it...

I was wondering something else, and that was, could the call:

/* 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;
}

be recoded to use a new et primitive that could run faster, and decide 
wether it was == or != bb2 more quickly than
the general case of finding the nearest common dominator?  If so, is 
that a better change that a simple cache (which will consume memory)?  
Or, would it just complement the cache?  Anyway, just wanted to say, 
thanks for looking at this.

background gcov style info (a 60,000 bb function):

----- toplev.c
                      /* Discover and record the loop depth at the head 
of each basic
                         block.  The loop infrastructure does the real 
job for us.  */
           1          flow_loops_find (&loops, LOOP_TREE);

----- dominance.c
                /* 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;
       60002    {
       60002      return nearest_common_dominator (dom, bb1, bb2) == 
bb2;
                }
----- dominance.c
                /* 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;
       60002    {
       60002      if (!bb1)
      ######        return bb2;
       60002      if (!bb2)
      ######        return bb1;
       60002      return et_forest_node_value (dom->forest,
                                               
et_forest_common_ancestor (dom->forest,
       60002                                                            
  BB_NODE (dom, bb1),
                                                                        
  BB_NODE (dom,
       60002                                                            
           bb2)));
                }
----- et-forest.c
                /* 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;
       60002    {
       60002      int value1, value2, max_value;
       60002      et_forest_node_t ancestor;

[ ... ]
       60002      value2 = calculate_value (node2->first);
       60002      value1 = calculate_value (node1->first);
[ ... ]
       80001      while (calculate_value (ancestor->last) < max_value)
----- et-forest.c
                /* Calculate ET value of the given node.  */
                static inline int
                calculate_value (node)
                     et_forest_occurrence_t node;
      200005    {
      200005      int value = node->count_left;

  1000830892      while (node->parent)
                    {
  1000630887          if (node == node->parent->right)
  1000590882            value += node->parent->count_left + 1;

  1000630887          node = node->parent;
                    }

      200005      return value;
                }