X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbessaconstr.c;h=9b60c37cbae18ce810a72a384f4253fafd2d1982;hb=64723d1bd8ace74ca5f0018db8655f2a1f443532;hp=ebe4f7fc6287f8070e2ca5af3d3619c5f966210d;hpb=0c2e168b002336b6273decb11d5e632594a5c13c;p=libfirm diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c index ebe4f7fc6..9b60c37cb 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,18 @@ * 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 "besched.h" #include "beintlive_t.h" -#include "beirg_t.h" +#include "beirg.h" +#include "be_t.h" +#include "benode.h" #include "debug.h" #include "error.h" @@ -67,23 +70,18 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -static INLINE int is_inside(unsigned what, unsigned low, unsigned hi) -{ - return what - low < hi; -} - /** * Calculates the iterated dominance frontier of a set of blocks. Marks the * blocks as visited. Sets the link fields of the blocks in the dominance * frontier to the block itself. */ -static -void mark_iterated_dominance_frontiers(const be_ssa_construction_env_t *env) +static void mark_iterated_dominance_frontiers( + const be_ssa_construction_env_t *env) { stat_ev_cnt_decl(blocks); DBG((dbg, LEVEL_3, "Dominance Frontier:")); stat_ev_tim_push(); - while (!pdeq_empty(env->worklist)) { + while (!waitq_empty(env->worklist)) { int i; ir_node *block = waitq_get(env->worklist); ir_node **domfront = be_get_dominance_frontier(env->domfronts, block); @@ -94,16 +92,6 @@ void mark_iterated_dominance_frontiers(const be_ssa_construction_env_t *env) if (Block_block_visited(y)) continue; - /* - * It makes no sense to add phi-functions to blocks - * that are not dominated by any definition; - * all uses are dominated, hence the paths reaching the uses - * have to stay in the dominance subtrees of the given definitions. - */ - - if (!is_inside(get_Block_dom_tree_pre_num(y), env->min_dom, env->max_dom)) - continue; - if (!irn_visited(y)) { set_irn_link(y, NULL); waitq_put(env->worklist, y); @@ -119,25 +107,23 @@ void mark_iterated_dominance_frontiers(const be_ssa_construction_env_t *env) DBG((dbg, LEVEL_3, "\n")); } -static -ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, - ir_node *block); +static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, + ir_node *block); -static -ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block, - ir_node *link_with) +static ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block, + ir_node *link_with) { 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_graph *irg = get_Block_irg(block); + ir_node **ins = ALLOCAN(ir_node*, n_preds); + ir_node *phi; assert(n_preds > 1); for(i = 0; i < n_preds; ++i) { ins[i] = new_r_Unknown(irg, env->mode); } - phi = new_r_Phi(irg, block, n_preds, ins, env->mode); + phi = be_new_Phi(block, n_preds, ins, env->mode, env->phi_cls); if(env->new_phis != NULL) { ARR_APP1(ir_node*, env->new_phis, phi); } @@ -160,16 +146,15 @@ ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block, return phi; } -static -ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block) +static ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block) { ir_node *dom = get_Block_idom(block); assert(dom != NULL); return search_def_end_of_block(env, dom); } -static -ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block) +static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, + ir_node *block) { if(irn_visited(block)) { assert(get_irn_link(block) != NULL); @@ -184,8 +169,7 @@ ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block) } } -static -ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) +static ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) { ir_node *block = get_nodes_block(at); ir_node *node; @@ -225,25 +209,14 @@ ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) return get_def_at_idom(env, block); } -static -void update_domzone(be_ssa_construction_env_t *env, const ir_node *bl) -{ - int start = get_Block_dom_tree_pre_num(bl); - int end = get_Block_dom_max_subtree_pre_num(bl) + 1; - - env->min_dom = MIN(env->min_dom, start); - env->max_dom = MAX(env->max_dom, end); -} - /** * Adds a definition into the link field of the block. The definitions are * sorted by dominance. A non-visited block means no definition has been * inserted yet. */ -static -void introduce_def_at_block(ir_node *block, ir_node *def) +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; @@ -265,7 +238,6 @@ 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); } } @@ -288,12 +260,9 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) env->domfronts = be_get_birg_dom_front(birg); env->new_phis = NEW_ARR_F(ir_node*, 0); env->worklist = new_waitq(); - env->min_dom = INT_MAX; - env->max_dom = 0; - 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 */ @@ -309,9 +278,8 @@ void be_ssa_construction_destroy(be_ssa_construction_env_t *env) 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"); @@ -325,7 +293,8 @@ void be_ssa_construction_add_copy(be_ssa_construction_env_t *env, assert(env->iterated_domfront_calculated == 0); if(env->mode == NULL) { - env->mode = get_irn_mode(copy); + env->mode = get_irn_mode(copy); + env->phi_cls = arch_get_irn_reg_class_out(copy); } else { assert(env->mode == get_irn_mode(copy)); } @@ -336,7 +305,6 @@ void be_ssa_construction_add_copy(be_ssa_construction_env_t *env, waitq_put(env->worklist, block); } introduce_def_at_block(block, copy); - update_domzone(env, block); } void be_ssa_construction_add_copies(be_ssa_construction_env_t *env, @@ -347,11 +315,12 @@ void be_ssa_construction_add_copies(be_ssa_construction_env_t *env, assert(env->iterated_domfront_calculated == 0); if(env->mode == NULL) { - env->mode = get_irn_mode(copies[0]); + env->mode = get_irn_mode(copies[0]); + env->phi_cls = arch_get_irn_reg_class_out(copies[0]); } for(i = 0; i < copies_len; ++i) { - ir_node *copy = copies[i]; + ir_node *copy = copies[i]; ir_node *block = get_nodes_block(copy); assert(env->mode == get_irn_mode(copy)); @@ -359,7 +328,6 @@ void be_ssa_construction_add_copies(be_ssa_construction_env_t *env, waitq_put(env->worklist, block); } introduce_def_at_block(block, copy); - update_domzone(env, block); } } @@ -377,16 +345,17 @@ ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env) void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, ir_node **nodes, size_t nodes_len) { - stat_ev_cnt_decl(uses); 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); env->iterated_domfront_calculated = 1; } - stat_ev_int("bessaconstr_domzone", env->max_dom - env->min_dom); stat_ev_tim_push(); for(i = 0; i < nodes_len; ++i) { ir_node *value = nodes[i]; @@ -403,11 +372,11 @@ void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, if(env->ignore_uses != NULL && ir_nodeset_contains(env->ignore_uses, use)) continue; - if(is_Anchor(use)) + if(is_Anchor(use) || is_End(use)) continue; if(is_Phi(use)) { - ir_node *block = get_nodes_block(use); + ir_node *block = get_nodes_block(use); ir_node *predblock = get_Block_cfgpred_block(block, pos); at = sched_last(predblock); } @@ -415,7 +384,7 @@ void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, def = search_def(env, at); if(def == NULL) { - panic("no definition found for %+F at position %d\n", use, pos); + panic("no definition found for %+F at position %d", use, pos); } DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def)); @@ -423,6 +392,8 @@ void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env, 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"); } @@ -438,11 +409,15 @@ void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env, { 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)