X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelive.c;h=ce7d6b8bd70b2bf336bbf99f1d10c3247a95c17c;hb=7438ae082c9ec7658ccd006b40aa62084aedca2d;hp=bf9626610fb669bdfda27435f2e4d0e9cf2186f7;hpb=25d9bce9e2724624a9ebda1407ca92e69429e724;p=libfirm diff --git a/ir/be/belive.c b/ir/be/belive.c index bf9626610..ce7d6b8bd 100644 --- a/ir/be/belive.c +++ b/ir/be/belive.c @@ -8,43 +8,38 @@ #endif #include "impl.h" -#include "irouts.h" +#include "iredges_t.h" #include "irgwalk.h" #include "irprintf_t.h" #include "beutil.h" #include "belive_t.h" -#define DEFAULT_LIVE_SET_SIZE 8 - FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *) FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *) FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *) /** The offset of the liveness information in a firm node. */ -size_t live_irn_data_offset = 0; +size_t live_irg_data_offset = 0; void be_liveness_init(void) { - live_irn_data_offset = register_additional_node_data(sizeof(live_info_t)); + live_irg_data_offset = register_additional_graph_data(sizeof(irn_live_t)); } static INLINE void mark_live_in(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->in, irn); + _get_or_set_live(block, irn, live_state_in); } static INLINE void mark_live_out(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->out, irn); + _get_or_set_live(block, irn, live_state_out | live_state_end); } static INLINE void mark_live_end(ir_node *block, const ir_node *irn) { - block_live_info_t *info = get_block_live_info(block); - pset_insert_ptr(info->end, irn); + _get_or_set_live(block, irn, live_state_end); } /** @@ -58,30 +53,30 @@ static INLINE void mark_live_end(ir_node *block, const ir_node *irn) * of the block. */ static void live_end_at_block(ir_node *def, ir_node *block, - pset *visited, int is_true_out) + pset *visited, int is_true_out) { - mark_live_end(block, def); - if(is_true_out) - mark_live_out(block, def); + mark_live_end(block, def); + if(is_true_out) + mark_live_out(block, def); - if(!pset_find_ptr(visited, block)) { + if(!pset_find_ptr(visited, block)) { - pset_insert_ptr(visited, block); + pset_insert_ptr(visited, block); - /* - * If this block is not the definition block, we have to go up - * further. - */ - if(get_nodes_block(def) != block) { - int i, n; + /* + * If this block is not the definition block, we have to go up + * further. + */ + if(get_nodes_block(def) != block) { + int i, n; - mark_live_in(block, def); + mark_live_in(block, def); - for(i = 0, n = get_irn_arity(block); i < n; ++i) - live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1); - } + for(i = 0, n = get_irn_arity(block); i < n; ++i) + live_end_at_block(def, get_Block_cfgpred_block(block, i), visited, 1); + } - } + } } /** @@ -93,98 +88,181 @@ static void live_end_at_block(ir_node *def, ir_node *block, */ static void liveness_for_node(ir_node *irn, void *env) { - int i, n; - ir_node *def_block; - pset *visited; - - /* Don't compute liveness information for non-data nodes. */ - if(!is_data_node(irn)) - return; - - visited = pset_new_ptr(512); - def_block = get_nodes_block(irn); - - /* Go over all uses of the value */ - for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { - ir_node *use = get_irn_out(irn, i); - ir_node *use_block; - - /* - * If the usage is no data node, skip this use, since it does not - * affect the liveness of the node. - */ - if(!is_data_node(use)) - continue; - - /* Get the block where the usage is in. */ - use_block = get_nodes_block(use); - - /* - * If the use is a phi function, determine the corresponding block - * through which the value reaches the phi function and mark the - * value as live out of that block. - */ - if(is_Phi(use)) { - int i, n; - - /* Mark the node as a phi operand, since a use by a phi was found. */ - get_node_live_info(irn)->is_phi_op = 1; - - for(i = 0, n = get_irn_arity(use); i < n; ++i) { - if(get_irn_n(use, i) == irn) { - ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); - live_end_at_block(irn, pred_block, visited, 0); - } - } - } + const ir_edge_t *edge; + ir_node *def_block; + pset *visited; + + /* Don't compute liveness information for non-data nodes. */ + if(!is_data_node(irn)) + return; + + visited = pset_new_ptr(512); + def_block = get_nodes_block(irn); + + /* Go over all uses of the value */ + foreach_out_edge(irn, edge) { + ir_node *use = edge->src; + ir_node *use_block; + + /* + * If the usage is no data node, skip this use, since it does not + * affect the liveness of the node. + */ + if(!is_data_node(use)) + continue; + + /* Get the block where the usage is in. */ + use_block = get_nodes_block(use); + + /* + * If the use is a phi function, determine the corresponding block + * through which the value reaches the phi function and mark the + * value as live out of that block. + */ + if(is_Phi(use)) { + ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos); + live_end_at_block(irn, pred_block, visited, 0); + } + + /* + * Else, the value is live in at this block. Mark it and call live + * out on the predecessors. + */ + else if(def_block != use_block) { + int i, n; + + mark_live_in(use_block, irn); + + for(i = 0, n = get_irn_arity(use_block); i < n; ++i) { + ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); + live_end_at_block(irn, pred_block, visited, 1); + } + } + } + + del_pset(visited); +} + +static int cmp_irn_live(const void *a, const void *b, size_t size) +{ + const irn_live_t *p = a; + const irn_live_t *q = b; - /* - * Else, the value is live in at this block. Mark it and call live - * out on the predecessors. - */ - else if(def_block != use_block) { - int i, n; + return !(p->block == q->block && p->irn == q->irn); +} - mark_live_in(use_block, irn); +static int (*old_dump_block_func)(ir_node *self, FILE *F, dump_reason_t reason) = NULL; - for(i = 0, n = get_irn_arity(use_block); i < n; ++i) { - ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); - live_end_at_block(irn, pred_block, visited, 1); +static int dump_block_func(ir_node *self, FILE *F, dump_reason_t reason) +{ + switch(reason) { + case dump_node_opcode_txt: + fprintf(F, get_irn_opname(self)); + break; + case dump_node_mode_txt: + fprintf(F, get_irn_modename(self)); + break; + case dump_node_nodeattr_txt: + break; + case dump_node_info_txt: + if(!get_irg_live_info(get_irn_irg(self))->live) + return 0; + + fprintf(F, "liveness information:\n"); + { + irn_live_t *li; + live_foreach(self, li) { + ir_fprintf(F, "%+F", li->irn); + if(live_is_in(li)) + fprintf(F, " in"); + if(live_is_end(li)) + fprintf(F, " end"); + if(live_is_out(li)) + fprintf(F, " out"); + + fprintf(F, "\n"); } } } - del_pset(visited); + return 0; +} + +void be_liveness(ir_graph *irg) +{ + irg_live_info_t *live_info = get_irg_live_info(irg); + if(live_info->live) + del_set(live_info->live); + + live_info->live = new_set(cmp_irn_live, 8192); + irg_walk_graph(irg, liveness_for_node, NULL, NULL); + + old_dump_block_func = op_Block->ops.dump_node; + op_Block->ops.dump_node = dump_block_func; } -static void create_sets(ir_node *block, void *env) +static void dump_liveness_walker(ir_node *bl, void *data) { - block_live_info_t *info = get_block_live_info(block); - info->in = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); - info->out = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); - info->end = pset_new_ptr(DEFAULT_LIVE_SET_SIZE); + FILE *f = data; + const irn_live_t *li; + char buf[64]; + + ir_fprintf(f, "%+F\n", bl); + live_foreach(bl, li) { + strcpy(buf, ""); + + if(live_is_in(li)) + strcat(buf, "in "); + + if(live_is_end(li)) + strcat(buf, "end "); + + if(live_is_out(li)) + strcat(buf, "out "); + + ir_fprintf(f, "\t%+20F %s\n", li->irn, buf); + } } +void be_liveness_dump(ir_graph *irg, FILE *f) +{ + irg_block_walk_graph(irg, dump_liveness_walker, NULL, f); +} -static void liveness_dump(ir_node *block, void *env) +void be_liveness_dumpto(ir_graph *irg, const char *cls_name) { - FILE *f = env; - block_live_info_t *info = get_block_live_info(block); - - assert(is_Block(block) && "Need a block here"); - ir_fprintf(f, "liveness at block %n\n", block); - ir_fprintf(f, "\tlive in: %*n\n", pset_iterator, info->in); - ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out); - ir_fprintf(f, "\tlive end: %*n\n", pset_iterator, info->end); + FILE *f; + char buf[128]; + ir_snprintf(buf, sizeof(buf), "%F_%s-live.txt", irg, cls_name); + if((f = fopen(buf, "wt")) != NULL) { + be_liveness_dump(irg, f); + fclose(f); + } } -void be_liveness_dump(FILE *f, ir_graph *irg) +static void dom_check(ir_node *irn, void *data) { - irg_block_walk_graph(irg, liveness_dump, NULL, f); + if(!is_Block(irn) && irn != get_irg_end(get_irn_irg(irn))) { + int i, n; + ir_node *bl = get_nodes_block(irn); + + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + ir_node *def_bl = get_nodes_block(op); + ir_node *use_bl = bl; + + if(is_Phi(irn)) + use_bl = get_Block_cfgpred_block(bl, i); + + if(!block_dominates(def_bl, use_bl)) { + ir_fprintf(stderr, "%+F in %+F must dominate %+F for user %+F\n", op, def_bl, use_bl, irn); + assert(0); + } + } + } } -void be_liveness(ir_graph *irg) +void be_check_dominance(ir_graph *irg) { - irg_block_walk_graph(irg, create_sets, NULL, NULL); - irg_walk_graph(irg, liveness_for_node, NULL, NULL); + irg_walk_graph(irg, dom_check, NULL, NULL); }