contrib/gcc/dominance.c

24    to dominate another block X, when all paths from the entry node of the CFG
52    'undefined' or 'end of list'.  The name of each node is given by the dfs
67   /* The parent of a node in the DFS tree.  */
69   /* For a node x key[x] is roughly the node nearest to the root from which
70      exists a way to x only over nodes behind x.  Such a node is also called
73   /* The value in path_min[x] is the node y on the path from x to the root of
76   /* bucket[x] points to the first node of the set of nodes having x as key.  */
78   /* And next_bucket[x] points to the next node.  */
86   /* set_chain[x] is the next node on the path from x to the representant
96      number of that node in DFS order counted from 1.  This is an index
99   /* If x is the DFS-index of a node which corresponds with a basic block,
198    node.  After this is done all nodes reachable from BB were visited, have
251 	      /* If the next node BN is either already visited or a border
253 	         with the next edge out of the current node.  */
297          child node was completely considered by DFS.  Here is the
379    in and path_min[V] is the node with the smallest key[] value on the path
399    changed since the last call).  Returns the node with the smallest key[]
471    On return the immediate dominator to node V is in di->dom[V].  */
508       /* Search all direct predecessors for the smallest node with a path
509          to them.  That way we have the smallest node with also a path to
569 assign_dfs_numbers (struct et_node *node, int *num)
573   node->dfs_num_in = (*num)++;
575   if (node->son)
577       assign_dfs_numbers (node->son, num);
578       for (son = node->son->right; son != node->son; son = son->right)
582   node->dfs_num_out = (*num)++;
677   struct et_node *node = bb->dom[dir];
681   if (!node->father)
684   return node->father->data;
693   struct et_node *node = bb->dom[dir];
697   if (node->father)
699       if (node->father->data == dominated_by)
701       et_split (node);
705     et_set_father (node, dominated_by->dom[dir]);
717   struct et_node *node = bb->dom[dir], *son = node->son, *ason;
825     1. The number for when we visit a node on the way down the tree
826     2. The number for when we visit a node on the way back up the tree
829     nodes in the subtree of the dominator tree rooted at that node
836     1. Node A is above Node B (and thus, Node A dominates node B)
850    2. Node A is below node B (and thus, node B dominates node A)
885    A_Dominates_B (node A, node B)
891    A_Dominated_by_B (node A, node B)