X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbessaconstr.c;h=bf5ae96dd38038d0f97fb8546e749dae052d349a;hb=5124cba7e9aa4ef891804bb6124812c1eafd7705;hp=f23872000d3ace4f62276861cc319d009d40eff6;hpb=cc9e943991e0457b30236478427a44f91ed0084e;p=libfirm diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c index f23872000..bf5ae96dd 100644 --- a/ir/be/bessaconstr.c +++ b/ir/be/bessaconstr.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -29,11 +29,11 @@ * to their closest copy while introducing phis as necessary. * * Algorithm: Mark all blocks in the iterated dominance frontiers of the value - * and it's copies. Link the copies ordered by dominance to the blocks. The - * we search for each use all all definitions in the current block, if none is + * and it's copies. Link the copies ordered by dominance to the blocks. Then + * we search for each use all definitions in the current block, if none is * found, then we search one in the immediate dominator. If we are in a block - * of the dominance frontier, create a phi and search do the same search for - * the phi arguments. + * of the dominance frontier, create a phi and do the same search for all + * phi arguments. * * A copy in this context means, that you want to introduce several new * abstract values (in Firm: nodes) for which you know, that they @@ -46,15 +46,17 @@ * This function reroutes all uses of the original value to the copies in the * corresponding dominance subtrees and creates Phi functions where necessary. */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif + +/* statev in this file is extensive, so only enable if needed */ +#define DISABLE_STATEV #include "bessaconstr.h" #include "bemodule.h" #include "besched_t.h" #include "beintlive_t.h" #include "beirg_t.h" +#include "be_t.h" #include "debug.h" #include "error.h" @@ -73,29 +75,34 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) * frontier to the block itself. */ static -void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts, - waitq *worklist) +void mark_iterated_dominance_frontiers(const be_ssa_construction_env_t *env) { + stat_ev_cnt_decl(blocks); DBG((dbg, LEVEL_3, "Dominance Frontier:")); - while(!pdeq_empty(worklist)) { + stat_ev_tim_push(); + while (!waitq_empty(env->worklist)) { int i; - ir_node *block = waitq_get(worklist); - ir_node **domfront = be_get_dominance_frontier(domfronts, block); + ir_node *block = waitq_get(env->worklist); + ir_node **domfront = be_get_dominance_frontier(env->domfronts, block); int domfront_len = ARR_LEN(domfront); for (i = 0; i < domfront_len; ++i) { ir_node *y = domfront[i]; - if(Block_block_visited(y)) + if (Block_block_visited(y)) continue; - if(!irn_visited(y)) { + if (!irn_visited(y)) { set_irn_link(y, NULL); - waitq_put(worklist, y); + waitq_put(env->worklist, y); } + DBG((dbg, LEVEL_3, " %+F", y)); mark_Block_block_visited(y); + stat_ev_cnt_inc(blocks); } } + stat_ev_tim_pop("bessaconstr_idf_time"); + stat_ev_cnt_done(blocks, "bessaconstr_idf_blocks"); DBG((dbg, LEVEL_3, "\n")); } @@ -109,8 +116,8 @@ ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block, { int i, n_preds = get_Block_n_cfgpreds(block); ir_graph *irg = get_irn_irg(block); - ir_node *phi; - ir_node **ins = alloca(n_preds * sizeof(ins[0])); + ir_node **ins = ALLOCAN(ir_node*, n_preds); + ir_node *phi; assert(n_preds > 1); @@ -160,7 +167,6 @@ ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block) ir_node *def = get_def_at_idom(env, block); mark_irn_visited(block); set_irn_link(block, def); - return def; } } @@ -202,7 +208,6 @@ ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) return create_phi(env, block, node); } - DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n")); return get_def_at_idom(env, block); } @@ -215,7 +220,7 @@ ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) static void introduce_def_at_block(ir_node *block, ir_node *def) { - if(irn_visited(block)) { + if (irn_visited_else_mark(block)) { ir_node *node = block; ir_node *current_def; @@ -237,15 +242,22 @@ void introduce_def_at_block(ir_node *block, ir_node *def) } else { set_irn_link(block, def); set_irn_link(def, NULL); - mark_irn_visited(block); } } void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) { ir_graph *irg = be_get_birg_irg(birg); - memset(env, 0, sizeof(env[0])); + ir_node *sb = get_irg_start_block(irg); + int n_blocks = get_Block_dom_max_subtree_pre_num(sb); + + stat_ev_ctx_push_fobj("bessaconstr", irg); + stat_ev_tim_push(); + + (void) n_blocks; + stat_ev_dbl("bessaconstr_n_blocks", n_blocks); + memset(env, 0, sizeof(env[0])); be_assure_dom_front(birg); env->irg = irg; @@ -253,26 +265,28 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) env->new_phis = NEW_ARR_F(ir_node*, 0); env->worklist = new_waitq(); - set_using_visited(irg); - set_using_block_visited(irg); - set_using_irn_link(irg); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED + | IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK); /* we use the visited flag to indicate blocks in the dominance frontier * and blocks that already have the relevant value at the end calculated */ inc_irg_visited(irg); /* We use the block visited flag to indicate blocks in the dominance - * froniter of some values (and this potentially needing phis) */ + * frontier of some values (and this potentially needing phis) */ inc_irg_block_visited(irg); } void be_ssa_construction_destroy(be_ssa_construction_env_t *env) { + stat_ev_int("bessaconstr_phis", ARR_LEN(env->new_phis)); del_waitq(env->worklist); DEL_ARR_F(env->new_phis); - clear_using_visited(env->irg); - clear_using_block_visited(env->irg); - clear_using_irn_link(env->irg); + ir_free_resources(env->irg, IR_RESOURCE_IRN_VISITED + | IR_RESOURCE_BLOCK_VISITED | IR_RESOURCE_IRN_LINK); + + stat_ev_tim_pop("bessaconstr_total_time"); + stat_ev_ctx_pop("bessaconstr"); } void be_ssa_construction_add_copy(be_ssa_construction_env_t *env, @@ -330,67 +344,82 @@ ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env) return env->new_phis; } -void be_ssa_construction_fix_users(be_ssa_construction_env_t *env, - ir_node *value) +void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, + ir_node **nodes, size_t nodes_len) { const ir_edge_t *edge, *next; + size_t i; + stat_ev_cnt_decl(uses); + + BE_TIMER_PUSH(t_ssa_constr); if(!env->iterated_domfront_calculated) { - mark_iterated_dominance_frontiers(env->domfronts, env->worklist); + mark_iterated_dominance_frontiers(env); env->iterated_domfront_calculated = 1; } - /* - * Search the valid def for each use and set it. - */ - foreach_out_edge_safe(value, edge, next) { - ir_node *use = get_edge_src_irn(edge); - ir_node *at = use; - int pos = get_edge_src_pos(edge); - ir_node *def; - - if(env->ignore_uses != NULL && - ir_nodeset_contains(env->ignore_uses, use)) - continue; - - if(is_Phi(use)) { - ir_node *block = get_nodes_block(use); - ir_node *predblock = get_Block_cfgpred_block(block, pos); - at = sched_last(predblock); - } + stat_ev_tim_push(); + for(i = 0; i < nodes_len; ++i) { + ir_node *value = nodes[i]; + + /* + * Search the valid def for each use and set it. + */ + foreach_out_edge_safe(value, edge, next) { + ir_node *use = get_edge_src_irn(edge); + ir_node *at = use; + int pos = get_edge_src_pos(edge); + ir_node *def; + + if(env->ignore_uses != NULL && + ir_nodeset_contains(env->ignore_uses, use)) + continue; + if(is_Anchor(use)) + continue; - def = search_def(env, at); + if(is_Phi(use)) { + ir_node *block = get_nodes_block(use); + ir_node *predblock = get_Block_cfgpred_block(block, pos); + at = sched_last(predblock); + } - if(def == NULL) { - panic("no definition found for %+F at position %d\n", use, pos); - } + def = search_def(env, at); - DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def)); - set_irn_n(use, pos, def); + if(def == NULL) { + panic("no definition found for %+F at position %d", use, pos); + } + + DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def)); + set_irn_n(use, pos, def); + stat_ev_cnt_inc(uses); + } } + BE_TIMER_POP(t_ssa_constr); + + stat_ev_tim_pop("bessaconstr_fix_time"); + stat_ev_cnt_done(uses, "bessaconstr_uses"); } -void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, - ir_node **nodes, size_t nodes_len) +void be_ssa_construction_fix_users(be_ssa_construction_env_t *env, ir_node *value) { - size_t i; - - for(i = 0; i < nodes_len; ++i) { - ir_node *node = nodes[i]; - be_ssa_construction_fix_users(env, node); - } + be_ssa_construction_fix_users_array(env, &value, 1); } + void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env, be_lv_t *lv) { int i, n; + BE_TIMER_PUSH(t_ssa_constr); + n = ARR_LEN(env->new_phis); for(i = 0; i < n; ++i) { ir_node *phi = env->new_phis[i]; be_liveness_introduce(lv, phi); } + + BE_TIMER_POP(t_ssa_constr); } void be_init_ssaconstr(void)