From c84df20a77cee7031432836dc18d7cf0f7c6bc23 Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Thu, 13 Jan 2005 12:20:41 +0000 Subject: [PATCH] Added dom tree traversal [r4889] --- ir/ana/irdom.c | 124 ++++++++++++++++++++++++++++++++++++++++++++--- ir/ana/irdom.h | 75 ++++++++++++++++++++++++++-- ir/ana/irdom_t.h | 14 ++++-- 3 files changed, 201 insertions(+), 12 deletions(-) diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c index 867c52de7..0ed62d86b 100644 --- a/ir/ana/irdom.c +++ b/ir/ana/irdom.c @@ -27,25 +27,43 @@ #include "irnode_t.h" #include "ircons_t.h" +#define get_dom_info(bl) (&(bl)->attr.block.dom) + + /*--------------------------------------------------------------------*/ /** Accessing the dominator data structures **/ /*--------------------------------------------------------------------*/ -ir_node *get_Block_idom(ir_node *bl) { - assert(get_irn_op(bl) == op_Block); +ir_node *get_Block_idom(const ir_node *bl) { + assert(is_Block(bl)); if (get_Block_dom_depth(bl) == -1) { /* This block is not reachable from Start */ return new_Bad(); } - return bl->attr.block.dom.idom; + return get_dom_info(bl)->idom; } void set_Block_idom(ir_node *bl, ir_node *n) { + dom_info *bli = get_dom_info(bl); + assert(get_irn_op(bl) == op_Block); - bl->attr.block.dom.idom = n; + + /* Set the immediate dominator of bl to n */ + bli->idom = n; + + /* + * If we don't set the root of the dominator tree + * Append bl to the dominates queue of n. + */ + if(n != NULL) { + dom_info *ni = get_dom_info(n); + + bli->next = ni->first; + ni->first = bl; + } } -int get_Block_pre_num(ir_node *bl) { +int get_Block_pre_num(const ir_node *bl) { assert(get_irn_op(bl) == op_Block); return bl->attr.block.dom.pre_num; } @@ -55,7 +73,7 @@ void set_Block_pre_num(ir_node *bl, int num) { bl->attr.block.dom.pre_num = num; } -int get_Block_dom_depth(ir_node *bl) { +int get_Block_dom_depth(const ir_node *bl) { assert(get_irn_op(bl) == op_Block); return bl->attr.block.dom.dom_depth; } @@ -65,7 +83,94 @@ void set_Block_dom_depth(ir_node *bl, int depth) { bl->attr.block.dom.dom_depth = depth; } +unsigned get_Block_dom_tree_pre_num(const ir_node *bl) +{ + assert(is_Block(bl)); + return get_dom_info(bl)->tree_pre_num; +} + +unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl) +{ + assert(is_Block(bl)); + return get_dom_info(bl)->max_subtree_pre_num; +} + +int block_dominates(const ir_node *a, const ir_node *b) +{ + const dom_info *ai, *bi; + + assert(is_Block(a) && is_Block(b)); + ai = get_dom_info(a); + bi = get_dom_info(b); + return bi->tree_pre_num - ai->tree_pre_num + <= ai->max_subtree_pre_num - ai->tree_pre_num; +} + +ir_node *get_Block_dominated_first(const ir_node *bl) +{ + assert(is_Block(bl)); + return get_dom_info(bl)->first; +} + +ir_node *get_Block_dominated_next(const ir_node *bl) +{ + assert(is_Block(bl)); + return get_dom_info(bl)->next; +} + +void dom_tree_walk(ir_node *n, irg_walk_func *pre, + irg_walk_func *post, void *env) +{ + ir_node *p; + + assert(get_irn_irg(n)->dom_state == dom_consistent + && "The dominators of the irg must be consistent"); + + for(p = get_dom_info(p)->first; p; p = get_dom_info(p)->next) { + if(pre) + pre(p, env); + + dom_tree_walk(p, pre, post, env); + + if(post) + post(p, env); + } +} + +void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, + irg_walk_func *post, void *env) +{ + /* The root of the dominator tree should be the start node. */ + ir_node *root = get_irg_start_block(irg); + + assert(irg->dom_state == dom_consistent + && "The dominators of the irg must be consistent"); + assert(root && "The start block of the graph is NULL?"); + assert(get_dom_info(root)->idom == NULL + && "The start node in the graph must be the root of the dominator tree"); + dom_tree_walk(root, pre, post, env); +} + +static void assign_tree_pre_order(ir_node *bl, void *data) +{ + unsigned *num = data; + dom_info *bi = get_dom_info(bl); + bi->tree_pre_num = (*num)++; +} +static void assign_tree_pre_order_max(ir_node *bl, void *data) +{ + dom_info *bi = get_dom_info(bl); + ir_node *p; + unsigned max = 0; + + for(p = bi->first; p; p = get_dom_info(p)->next) { + unsigned max_p = get_dom_info(p)->max_subtree_pre_num; + max = max > max_p ? max : max_p; + } + + bi->max_subtree_pre_num = max; +} /*--------------------------------------------------------------------*/ /* Building and Removing the dominator datastructure */ @@ -259,6 +364,13 @@ void compute_doms(ir_graph *irg) { /* clean up */ /* free(tdi_list); @@@ does not work !!?? */ current_ir_graph = rem; + + /* Do a walk over the tree and assign the tree pre orders. */ + { + unsigned tree_pre_order = 0; + dom_tree_walk_irg(irg, assign_tree_pre_order, + assign_tree_pre_order_max, &tree_pre_order); + } } void free_dom_and_peace(ir_graph *irg) { diff --git a/ir/ana/irdom.h b/ir/ana/irdom.h index 12af2371b..fadfe7502 100644 --- a/ir/ana/irdom.h +++ b/ir/ana/irdom.h @@ -30,6 +30,7 @@ # define _IRDOM_H_ # include "irgraph.h" +# include "irgwalk.h" # include "irnode.h" @@ -40,15 +41,83 @@ * * If the block is not reachable from Start, returns a Bad node. */ -ir_node *get_Block_idom(ir_node *bl); +ir_node *get_Block_idom(const ir_node *bl); void set_Block_idom(ir_node *bl, ir_node *n); -int get_Block_dom_depth(ir_node *bl); +int get_Block_dom_depth(const ir_node *bl); void set_Block_dom_depth(ir_node *bl, int depth); -int get_Block_pre_num(ir_node *bl); +int get_Block_pre_num(const ir_node *bl); void set_Block_pre_num(ir_node *bl, int num); +/** + * Get the pre-order number of a block resulting from a dfs walk + * over the dominator tree. + * @param bl The block. + * @return The pre-order number. + */ +unsigned get_Block_dom_tree_pre_num(const ir_node *bl); + +/** + * Get the largest pre-order number found in the subtree of the + * dominator tree rooted at a given block. + * @param bl The block. + * @return The largest pre-order number of block's dominator subtree. + */ +unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl); + +/** + * Get the first node in the list of nodes dominated by a given block. + * + * Each node keeps a list of nodes which it immediately dominates. The + * nodes are queued using the @c next pointer in the @c dom_info struct. + * Each node keeps a head of this list using the pointer @c first in the + * same structure. + * + * @param bl The block for which to get the first node dominated by @c bl. + * @return The first node dominated by @p bl. + */ +ir_node *get_Block_dominated_first(const ir_node *bl); + +/** + * Get the next node in a list of nodes which are dominated by some + * other node. + * @see get_Block_dominated_first(). + * @param dom The previous node. + * @return The next node in this list or NULL if it was the last. + */ +ir_node *get_Block_dominated_next(const ir_node *dom); + +/** + * Check, if a block dominates another block. + * @param a The first block. + * @param b The second block. + * @return 1, if @p a dominates @p b, else 0. + */ +int block_dominates(const ir_node *a, const ir_node *b); + +/** + * Visit all nodes in the dominator subtree of a given node. + * Call a pre-visitor before descending to the children and call a + * post-visitor after returning from them. + * @param n The node to start walking from. + * @param pre The pre-visitor callback. + * @param post The post-visitor callback. + * @param env Some custom data passed to the visitors. + */ +void dom_tree_walk(ir_node *n, irg_walk_func *pre, + irg_walk_func *post, void *env); + + +/** + * Walk over the dominator tree of an irg starting at the root. + * @param irg The graph. + * @param pre A pre-visitor to call. + * @param post A post-visitor to call. + * @param env Some private data to give to the visitors. + */ +void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, + irg_walk_func *post, void *env); /* ------------ Building and Removing the dominator datasturcture ----------- */ diff --git a/ir/ana/irdom_t.h b/ir/ana/irdom_t.h index 5a5857c6e..e5441fb85 100644 --- a/ir/ana/irdom_t.h +++ b/ir/ana/irdom_t.h @@ -28,9 +28,17 @@ /** For dominator information */ typedef struct dom_info { - struct ir_node *idom; /**< immediate CFG dominator */ - int pre_num; /**< pre-order graph-walk number */ - int dom_depth; /**< depth in dominator-tree */ + struct ir_node *idom; /**< immediate CFG dominator */ + struct ir_node *next; /**< The next node in the dominated + list of @c idom. */ + struct ir_node *first; /**< The first node in the list of nodes + this nodes dominates immediately. */ + int tree_pre_num; /**< The pre-order number from a dfs walk + over the dominator tree. */ + int max_subtree_pre_num; /**< The largest tree pre num found in the + dominator subtree of this node. */ + int pre_num; /**< pre-order graph-walk number */ + int dom_depth; /**< depth in dominator-tree */ } dom_info; #endif /* _IRDOM_T_H_ */ -- 2.20.1