X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firdom.c;h=2726b484b9a4f17e1387add93080d8a90aad9906;hb=6b1241844320899c9c3f175a81a274fcbdd5be27;hp=1ba5b9d75cd6002d2e333d90b11a9c89bc6eb20a;hpb=81d4cf5aeab4d0c0bc2a5e7c461d58ee7a7522d6;p=libfirm diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c index 1ba5b9d75..2726b484b 100644 --- a/ir/ana/irdom.c +++ b/ir/ana/irdom.c @@ -24,20 +24,16 @@ * @date 2.2002 * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif -#ifdef HAVE_STRING_H #include -#endif #include "irouts.h" #include "xmalloc.h" #include "irgwalk.h" #include "irdom_t.h" -#include "irgraph_t.h" /* To access state field. */ +#include "irgraph_t.h" #include "irnode_t.h" #include "ircons_t.h" #include "array_t.h" @@ -51,7 +47,8 @@ /** Accessing the dominator and post dominator data structures **/ /*--------------------------------------------------------------------*/ -ir_node *get_Block_idom(const ir_node *bl) { +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 */ @@ -60,7 +57,8 @@ ir_node *get_Block_idom(const ir_node *bl) { return get_dom_info(bl)->idom; } -void set_Block_idom(ir_node *bl, ir_node *n) { +void set_Block_idom(ir_node *bl, ir_node *n) +{ ir_dom_info *bli = get_dom_info(bl); assert(is_Block(bl)); @@ -72,7 +70,7 @@ void set_Block_idom(ir_node *bl, ir_node *n) { * If we don't set the root of the dominator tree * Append bl to the dominates queue of n. */ - if(n != NULL) { + if (n != NULL) { ir_dom_info *ni = get_dom_info(n); bli->next = ni->first; @@ -80,7 +78,8 @@ void set_Block_idom(ir_node *bl, ir_node *n) { } } -ir_node *get_Block_ipostdom(const ir_node *bl) { +ir_node *get_Block_ipostdom(const ir_node *bl) +{ assert(is_Block(bl)); if (get_Block_postdom_depth(bl) == -1) { /* This block is not reachable from Start */ @@ -89,7 +88,8 @@ ir_node *get_Block_ipostdom(const ir_node *bl) { return get_pdom_info(bl)->idom; } -void set_Block_ipostdom(ir_node *bl, ir_node *n) { +void set_Block_ipostdom(ir_node *bl, ir_node *n) +{ ir_dom_info *bli = get_pdom_info(bl); assert(is_Block(bl)); @@ -101,7 +101,7 @@ void set_Block_ipostdom(ir_node *bl, ir_node *n) { * If we don't set the root of the post dominator tree * Append bl to the post dominates queue of n. */ - if(n != NULL) { + if (n != NULL) { ir_dom_info *ni = get_pdom_info(n); bli->next = ni->first; @@ -109,69 +109,82 @@ void set_Block_ipostdom(ir_node *bl, ir_node *n) { } } -int get_Block_dom_pre_num(const ir_node *bl) { +int get_Block_dom_pre_num(const ir_node *bl) +{ assert(is_Block(bl)); return get_dom_info(bl)->pre_num; } -void set_Block_dom_pre_num(ir_node *bl, int num) { +void set_Block_dom_pre_num(ir_node *bl, int num) +{ assert(is_Block(bl)); get_dom_info(bl)->pre_num = num; } -int get_Block_dom_depth(const ir_node *bl) { +int get_Block_dom_depth(const ir_node *bl) +{ assert(is_Block(bl)); return get_dom_info(bl)->dom_depth; } -void set_Block_dom_depth(ir_node *bl, int depth) { +void set_Block_dom_depth(ir_node *bl, int depth) +{ assert(is_Block(bl)); get_dom_info(bl)->dom_depth = depth; } -int get_Block_postdom_pre_num(const ir_node *bl) { +int get_Block_postdom_pre_num(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->pre_num; } -void set_Block_postdom_pre_num(ir_node *bl, int num) { +void set_Block_postdom_pre_num(ir_node *bl, int num) +{ assert(is_Block(bl)); get_pdom_info(bl)->pre_num = num; } -int get_Block_postdom_depth(const ir_node *bl) { +int get_Block_postdom_depth(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->dom_depth; } -void set_Block_postdom_depth(ir_node *bl, int depth) { +void set_Block_postdom_depth(ir_node *bl, int depth) +{ assert(is_Block(bl)); get_pdom_info(bl)->dom_depth = depth; } -unsigned get_Block_dom_tree_pre_num(const ir_node *bl) { +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) { +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; } -unsigned get_Block_pdom_tree_pre_num(const ir_node *bl) { +unsigned get_Block_pdom_tree_pre_num(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->tree_pre_num; } -unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl) { +unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->max_subtree_pre_num; } /* Check, if a block dominates another block. */ -int block_dominates(const ir_node *a, const ir_node *b) { +int block_dominates(const ir_node *a, const ir_node *b) +{ const ir_dom_info *ai, *bi; if (is_Block(a) && is_Block(b)) { @@ -185,12 +198,14 @@ int block_dominates(const ir_node *a, const ir_node *b) { } /* Check, if a block strictly dominates another block. */ -int block_strictly_dominates(const ir_node *a, const ir_node *b) { +int block_strictly_dominates(const ir_node *a, const ir_node *b) +{ return (a != b) && block_dominates(a, b); } /* Returns the smallest common dominator block of two nodes. */ -ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b) { +ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b) +{ ir_node *bl_a = is_Block(a) ? a : get_nodes_block(a); ir_node *bl_b = is_Block(b) ? b : get_nodes_block(b); ir_node *dom_bl = NULL; @@ -217,7 +232,8 @@ ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b) { } /* Returns the smallest common dominator block of all users of a node. */ -ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi) { +ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi) +{ int n, j, i = 0, success; ir_node **user_blocks, *dom_bl; const ir_edge_t *edge; @@ -274,20 +290,23 @@ ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi) { /* Get the first node in the list of nodes dominated by a given block. */ -ir_node *get_Block_dominated_first(const ir_node *bl) { +ir_node *get_Block_dominated_first(const ir_node *bl) +{ assert(is_Block(bl)); return get_dom_info(bl)->first; } /* Get the next node in a list of nodes which are dominated by some * other node. */ -ir_node *get_Block_dominated_next(const ir_node *bl) { +ir_node *get_Block_dominated_next(const ir_node *bl) +{ assert(is_Block(bl)); return get_dom_info(bl)->next; } /* Check, if a block post dominates another block. */ -int block_postdominates(const ir_node *a, const ir_node *b) { +int block_postdominates(const ir_node *a, const ir_node *b) +{ const ir_dom_info *ai, *bi; if (is_Block(a) && is_Block(b)) { @@ -301,20 +320,23 @@ int block_postdominates(const ir_node *a, const ir_node *b) { } /* Check, if a block strictly dominates another block. */ -int block_strictly_postdominates(const ir_node *a, const ir_node *b) { +int block_strictly_postdominates(const ir_node *a, const ir_node *b) +{ return (a != b) && block_postdominates(a, b); } /* Get the first node in the list of nodes post dominated by a given block. */ -ir_node *get_Block_postdominated_first(const ir_node *bl) { +ir_node *get_Block_postdominated_first(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->first; } /* Get the next node in a list of nodes which are post dominated by some * other node. */ -ir_node *get_Block_postdominated_next(const ir_node *bl) { +ir_node *get_Block_postdominated_next(const ir_node *bl) +{ assert(is_Block(bl)); return get_pdom_info(bl)->next; } @@ -325,14 +347,14 @@ void dom_tree_walk(ir_node *bl, irg_walk_func *pre, { ir_node *p; - if(pre) + if (pre) pre(bl, env); dominates_for_each(bl, p) { dom_tree_walk(p, pre, post, env); } - if(post) + if (post) post(bl, env); } @@ -342,14 +364,14 @@ void postdom_tree_walk(ir_node *bl, irg_walk_func *pre, { ir_node *p; - if(pre) + if (pre) pre(bl, env); postdominates_for_each(bl, p) { postdom_tree_walk(p, pre, post, env); } - if(post) + if (post) post(bl, env); } @@ -360,7 +382,7 @@ void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre, /* The root of the dominator tree should be the Start block. */ ir_node *root = get_irg_start_block(irg); - assert(irg->dom_state == dom_consistent + 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 @@ -400,7 +422,7 @@ static void assign_tree_dom_pre_order_max(ir_node *bl, void *data) unsigned children = 0; (void) data; - for(p = bi->first; p; p = get_dom_info(p)->next) { + 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; children++; @@ -426,7 +448,7 @@ static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data) unsigned children = 0; (void) data; - for(p = bi->first; p; p = get_pdom_info(p)->next) { + for (p = bi->first; p; p = get_pdom_info(p)->next) { unsigned max_p = get_pdom_info(p)->max_subtree_pre_num; max = max > max_p ? max : max_p; children++; @@ -443,7 +465,8 @@ static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data) /** * count the number of blocks and clears the post dominance info */ -static void count_and_init_blocks_pdom(ir_node *bl, void *env) { +static void count_and_init_blocks_pdom(ir_node *bl, void *env) +{ int *n_blocks = (int *) env; (*n_blocks) ++; @@ -483,7 +506,8 @@ typedef struct { * Start block misses control dead blocks. */ static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent, - tmp_dom_info *tdi_list, int *used, int n_blocks) { + tmp_dom_info *tdi_list, int *used, int n_blocks) +{ tmp_dom_info *tdi; int i; @@ -507,7 +531,11 @@ static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent, /* Iterate */ for (i = get_Block_n_cfg_outs_ka(bl) - 1; i >= 0; --i) { ir_node *pred = get_Block_cfg_out_ka(bl, i); - assert(is_Block(pred)); + /* can happen for half-optimized dead code (I've seen this in student + projects */ + if (!is_Block(pred)) + continue; + init_tmp_dom_info(pred, tdi, tdi_list, used, n_blocks); } } @@ -517,7 +545,8 @@ static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent, * End block misses blocks in endless loops. */ static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent, - tmp_dom_info *tdi_list, int* used, int n_blocks) { + tmp_dom_info *tdi_list, int* used, int n_blocks) +{ tmp_dom_info *tdi; int i; @@ -564,7 +593,8 @@ static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent, } } -static void dom_compress(tmp_dom_info *v) { +static void dom_compress(tmp_dom_info *v) +{ assert (v->ancestor); if (v->ancestor->ancestor) { dom_compress (v->ancestor); @@ -579,21 +609,24 @@ static void dom_compress(tmp_dom_info *v) { * if V is a root, return v, else return the vertex u, not being the * root, with minimum u->semi on the path from v to its root. */ -INLINE static tmp_dom_info *dom_eval(tmp_dom_info *v) { +inline static tmp_dom_info *dom_eval(tmp_dom_info *v) +{ if (!v->ancestor) return v; dom_compress (v); return v->label; } /** make V W's ancestor */ -INLINE static void dom_link(tmp_dom_info *v, tmp_dom_info *w) { +inline static void dom_link(tmp_dom_info *v, tmp_dom_info *w) +{ w->ancestor = v; } /** * Walker: count the number of blocks and clears the dominance info */ -static void count_and_init_blocks_dom(ir_node *bl, void *env) { +static void count_and_init_blocks_dom(ir_node *bl, void *env) +{ int *n_blocks = (int *) env; (*n_blocks) ++; @@ -614,7 +647,8 @@ static void count_and_init_blocks_dom(ir_node *bl, void *env) { * @param irg the graph * @param pre a walker function that will be called for every block in the graph */ -static int init_construction(ir_graph *irg, irg_walk_func *pre) { +static int init_construction(ir_graph *irg, irg_walk_func *pre) +{ ir_graph *rem = current_ir_graph; ir_node *end; int arity; @@ -636,18 +670,19 @@ static int init_construction(ir_graph *irg, irg_walk_func *pre) { for (i = j = 0; i < arity; i++) { ir_node *pred = get_End_keepalive(end, i); - if (is_Block(pred)) { - if (Block_block_visited(pred)) + if (!is_Block(pred)) { + pred = get_nodes_block(pred); + if (!is_Block(pred)) { + /* a node which has a bad block input: kill it */ continue; - - /* we found an endless loop */ - dec_irg_block_visited(irg); - irg_block_walk(pred, pre, NULL, &n_blocks); + } } + dec_irg_block_visited(irg); + irg_block_walk(pred, pre, NULL, &n_blocks); in[j++] = pred; } if (j != arity) { - /* we kill some Block keep-alives */ + /* we kill some keep-alives */ set_End_keepalives(end, j, in); set_irg_outs_inconsistent(irg); } @@ -661,7 +696,8 @@ static int init_construction(ir_graph *irg, irg_walk_func *pre) { /* Computes the dominator trees. Sets a flag in irg to "dom_consistent". If the control flow of the graph is changed this flag must be set to "dom_inconsistent". */ -void compute_doms(ir_graph *irg) { +void compute_doms(ir_graph *irg) +{ ir_graph *rem = current_ir_graph; int n_blocks, used, i, j; tmp_dom_info *tdi_list; /* Ein Golf? */ @@ -676,7 +712,7 @@ void compute_doms(ir_graph *irg) { n_blocks = init_construction(irg, count_and_init_blocks_dom); /* Memory for temporary information. */ - tdi_list = xcalloc(n_blocks, sizeof(tdi_list[0])); + tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks); /* We need the out data structure. */ assure_irg_outs(irg); @@ -783,12 +819,14 @@ void compute_doms(ir_graph *irg) { current_ir_graph = rem; } -void assure_doms(ir_graph *irg) { +void assure_doms(ir_graph *irg) +{ if (get_irg_dom_state(irg) != dom_consistent) compute_doms(irg); } -void free_dom(ir_graph *irg) { +void free_dom(ir_graph *irg) +{ /* Update graph state */ assert(get_irg_phase_state(irg) != phase_building); irg->dom_state = dom_none; @@ -800,7 +838,8 @@ void free_dom(ir_graph *irg) { /* Computes the post dominator trees. Sets a flag in irg to "dom_consistent". If the control flow of the graph is changed this flag must be set to "dom_inconsistent". */ -void compute_postdoms(ir_graph *irg) { +void compute_postdoms(ir_graph *irg) +{ ir_graph *rem = current_ir_graph; int n_blocks, used, i, j; tmp_dom_info *tdi_list; @@ -815,7 +854,7 @@ void compute_postdoms(ir_graph *irg) { n_blocks = init_construction(irg, count_and_init_blocks_pdom); /* Memory for temporary information. */ - tdi_list = xcalloc(n_blocks, sizeof(tdi_list[0])); + tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks); /* We need the out data structure. */ assure_irg_outs(irg); @@ -894,12 +933,14 @@ void compute_postdoms(ir_graph *irg) { current_ir_graph = rem; } -void assure_postdoms(ir_graph *irg) { +void assure_postdoms(ir_graph *irg) +{ if (get_irg_postdom_state(irg) != dom_consistent) compute_postdoms(irg); } -void free_postdom(ir_graph *irg) { +void free_postdom(ir_graph *irg) +{ /* Update graph state */ assert(get_irg_phase_state(irg) != phase_building); irg->pdom_state = dom_none;