X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbessaconstr.c;h=d88c5f1db90bf4b81ad5ff1dd123c853dd415c5c;hb=2a018b8111bd0596816c1d00c38a0024857753f7;hp=45a7c10d993b5c6d17a2c5d1e8cec26827cdfd8d;hpb=06442ea1375d71a91fc5fd0e499cdf4bc9ce6475;p=libfirm diff --git a/ir/be/bessaconstr.c b/ir/be/bessaconstr.c index 45a7c10d9..d88c5f1db 100644 --- a/ir/be/bessaconstr.c +++ b/ir/be/bessaconstr.c @@ -20,7 +20,8 @@ /** * @file * @brief SSA construction for a set of nodes - * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig + * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig, + * Sebastian Buchwald * @date 04.05.2005 * @version $Id$ * @@ -29,7 +30,7 @@ * 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. Then + * and its 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 do the same search for all @@ -46,42 +47,150 @@ * 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" #include "pdeq.h" #include "array.h" #include "irdom.h" +#include "irnodeset.h" #include "ircons.h" #include "iredges_t.h" +#include "irphase_t.h" DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) +static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, + ir_node *block); + +struct constr_info { + bool is_definition; + bool is_use; + bool already_processed; + union { + /* Since we only consider scheduled nodes, + * this points to the real definition (e.g. a Proj). */ + ir_node *definition; + + /* Last definition of a block. */ + ir_node *last_definition; + }; +}; + +typedef struct constr_info constr_info; + +/** + * @return Whether the block contains a definition. + */ +static inline bool has_definition(be_ssa_construction_env_t *env, ir_node *block) +{ + (void)env; + + return irn_visited(block); +} + +/** + * @return Whether the block contains a use. + */ +static inline bool has_use(be_ssa_construction_env_t *env, ir_node *block) +{ + constr_info *info = phase_get_or_set_irn_data(env->phase, block); + + return info->is_use; +} + +/** + * @return Whether the node is a definition. + */ +static inline bool is_definition(be_ssa_construction_env_t *env, ir_node *node) +{ + constr_info *info = phase_get_irn_data(env->phase, node); + + return info && info->is_definition; +} + +/** + * @return Whether the node is a use. + */ +static inline bool is_use(const be_ssa_construction_env_t *env, ir_node *node) +{ + constr_info *info = phase_get_irn_data(env->phase, node); + + return info && info->is_use; +} + +/** + * Introduces a definition at the corresponding block. + */ +static void introduce_definition(be_ssa_construction_env_t *env, ir_node *def) +{ + ir_node *block = get_nodes_block(def); + ir_phase *phase = env->phase; + constr_info *def_info = phase_get_or_set_irn_data(phase, def); + ir_node *skip = skip_Proj(def); + constr_info *skip_info = phase_get_or_set_irn_data(phase, skip); + constr_info *block_info = phase_get_or_set_irn_data(phase, block); + + DBG((dbg, LEVEL_2, "\tintroducing definition %+F in %+F\n", def, block)); + + def_info->is_definition = true; + + skip_info->is_definition = true; + skip_info->definition = def; + + // Set the last definition if we only introduce one definition for the block + if (has_definition(env, block)) { + assert(!block_info->already_processed); + block_info->last_definition = NULL; + } + else { + mark_irn_visited(block); + block_info->last_definition = def; + } +} + +static void introduce_use(be_ssa_construction_env_t *env, ir_node *use) +{ + ir_node *block = get_nodes_block(use); + ir_phase *phase = env->phase; + constr_info *info = phase_get_or_set_irn_data(phase, use); + constr_info *block_info = phase_get_or_set_irn_data(phase, block); + + DBG((dbg, LEVEL_2, "\tintroducing use %+F in %+F\n", use, block)); + + info->is_use = true; + block_info->is_use = true; + + waitq_put(env->worklist, use); +} + /** * 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 (!waitq_empty(env->worklist)) { int i; - ir_node *block = waitq_get(env->worklist); + ir_node *block = (ir_node*)waitq_get(env->worklist); ir_node **domfront = be_get_dominance_frontier(env->domfronts, block); int domfront_len = ARR_LEN(domfront); @@ -105,149 +214,213 @@ 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 *create_phi(be_ssa_construction_env_t *env, ir_node *block, - ir_node *link_with) +/** + * Inserts a new phi at the given block. + * + * The constructed phi has only Dummy operands, + * but can be used as definition for other nodes. + * + * @see fix_phi_arguments + */ +static ir_node *insert_dummy_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_graph *irg = get_Block_irg(block); + ir_node **ins = ALLOCAN(ir_node*, n_preds); + ir_node *dummy; + ir_node *phi; + + DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block)); assert(n_preds > 1); - for(i = 0; i < n_preds; ++i) { - ins[i] = new_r_Unknown(irg, env->mode); + dummy = new_r_Dummy(irg, env->mode); + for (i = 0; i < n_preds; ++i) { + ins[i] = dummy; } - phi = new_r_Phi(irg, block, n_preds, ins, env->mode); - if(env->new_phis != NULL) { + phi = be_new_Phi(block, n_preds, ins, env->mode, env->phi_cls); + sched_add_after(block, phi); + if (env->new_phis != NULL) { ARR_APP1(ir_node*, env->new_phis, phi); } - if(env->mode != mode_M) { - sched_add_after(block, phi); - } - DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block)); - set_irn_link(link_with, phi); - mark_irn_visited(block); + introduce_definition(env, phi); - for(i = 0; i < n_preds; ++i) { - ir_node *pred_block = get_Block_cfgpred_block(block, i); - ir_node *pred_def = search_def_end_of_block(env, pred_block); - - set_irn_n(phi, i, pred_def); - } + waitq_put(env->worklist, phi); return phi; } -static -ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block) +/** + * @return Last definition of the immediate dominator. + */ +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); + DBG((dbg, LEVEL_3, "\t...continue at idom %+F\n", dom)); 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) +/** + * Fixes all operands of a use. + * + * If an operand of the use is a (original) definition, + * it will be replaced by the given definition. + */ +static void set_operands(be_ssa_construction_env_t *env, ir_node *use, ir_node *def) { - if(irn_visited(block)) { - assert(get_irn_link(block) != NULL); - return get_irn_link(block); - } else if(Block_block_visited(block)) { - return create_phi(env, block, block); - } else { - ir_node *def = get_def_at_idom(env, block); - mark_irn_visited(block); - set_irn_link(block, def); - return def; + constr_info *info = phase_get_irn_data(env->phase, use); + int arity = get_irn_arity(use); + int i; + + for (i = 0; i < arity; ++i) { + ir_node *op = get_irn_n(use, i); + + if (is_definition(env, op)) { + DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", use, i, def)); + set_irn_n(use, i, def); + } } + + info->already_processed = true; } -static -ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at) +/** + * Fixes all uses of the given block. + */ +static void process_block(be_ssa_construction_env_t *env, ir_node *block) { - ir_node *block = get_nodes_block(at); - ir_node *node; - ir_node *def; + ir_node *node; + ir_node *def = NULL; + constr_info *block_info = phase_get_or_set_irn_data(env->phase, block); + + assert(has_definition(env, block)); + assert(!block_info->already_processed && "Block already processed"); + + DBG((dbg, LEVEL_3, "\tprocessing block %+F\n", block)); + + sched_foreach(block, node) { + if (is_use(env, node) && !is_Phi(node)) { + DBG((dbg, LEVEL_3, "\t...found use %+F\n", node)); + + if (def == NULL) { + /* Create a phi if the block is in the dominance frontier. */ + if (Block_block_visited(block)) { + def = insert_dummy_phi(env, block); + } + else { + def = get_def_at_idom(env, block); + } + } - DBG((dbg, LEVEL_3, "\t...searching def at %+F\n", at)); + set_operands(env, node, def); + } - /* no defs in the current block we can do the normal searching */ - if(!irn_visited(block) && !Block_block_visited(block)) { - DBG((dbg, LEVEL_3, "\t...continue at idom\n")); - return get_def_at_idom(env, block); + if (is_definition(env, node)) { + constr_info *info = phase_get_irn_data(env->phase, node); + def = info->definition; + DBG((dbg, LEVEL_3, "\t...found definition %+F\n", def)); + } } - /* there are defs in the current block, walk the linked list to find - the one immediately dominating us - */ - node = block; - def = get_irn_link(node); - while(def != NULL) { - if(!value_dominates(at, def)) { - DBG((dbg, LEVEL_3, "\t...found dominating def %+F\n", def)); - return def; + block_info->already_processed = true; + block_info->last_definition = def; +} + +/** + * @return Last definition of the given block. + */ +static ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, + ir_node *block) +{ + constr_info *block_info = phase_get_or_set_irn_data(env->phase, block); + ir_node *last_definition = block_info->last_definition; + + if (last_definition != NULL) + return last_definition; + + if (has_definition(env, block)) { + if (has_use(env, block)) { + if (!block_info->already_processed) { + process_block(env, block); + } } + else { + ir_node *def = NULL; + + /* Search the last definition of the block. */ + sched_foreach_reverse(block, def) { + if (is_definition(env, def)) { + constr_info *info = phase_get_irn_data(env->phase, def); + def = info->definition; + DBG((dbg, LEVEL_3, "\t...found definition %+F\n", def)); + + break; + } + } - node = def; - def = get_irn_link(node); - } + assert(def && "No definition found"); - /* block in dominance frontier? create a phi then */ - if(Block_block_visited(block)) { - DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block)); - assert(!is_Phi(node)); - return create_phi(env, block, node); - } + block_info->last_definition = def; + } + + return block_info->last_definition; + } else if (Block_block_visited(block)) { + ir_node *phi = insert_dummy_phi(env, block); - DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n")); - return get_def_at_idom(env, block); + block_info->last_definition = phi; + + return phi; + } else { + ir_node *def = get_def_at_idom(env, block); + + block_info->last_definition = def; + + return def; + } } /** - * 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. + * Fixes all operands of the given use. */ -static -void introduce_def_at_block(ir_node *block, ir_node *def) +static void search_def_at_block(be_ssa_construction_env_t *env, ir_node *use) { - if(irn_visited(block)) { - ir_node *node = block; - ir_node *current_def; - - while(1) { - current_def = get_irn_link(node); - if(current_def == def) { - /* already in block */ - return; - } - if(current_def == NULL) - break; - if(value_dominates(current_def, def)) - break; - node = current_def; - } + ir_node *block = get_nodes_block(use); + constr_info *block_info = phase_get_or_set_irn_data(env->phase, block); + + if (block_info->already_processed) + return; - set_irn_link(node, def); - set_irn_link(def, current_def); + if (has_definition(env, block)) { + process_block(env, block); + } else if (Block_block_visited(block)) { + ir_node *phi = insert_dummy_phi(env, block); + + set_operands(env, use, phi); } else { - set_irn_link(block, def); - set_irn_link(def, NULL); - mark_irn_visited(block); + ir_node *def = get_def_at_idom(env, block); + + set_operands(env, use, def); } } -void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) +static void *init_constr_info(ir_phase *phase, const ir_node *node) +{ + constr_info *info = phase_alloc(phase, sizeof(constr_info)); + (void)node; + + info->is_definition = false; + info->is_use = false; + info->already_processed = false; + info->definition = NULL; + + return info; +} + +void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg) { - ir_graph *irg = be_get_birg_irg(birg); ir_node *sb = get_irg_start_block(irg); int n_blocks = get_Block_dom_max_subtree_pre_num(sb); @@ -258,16 +431,16 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) stat_ev_dbl("bessaconstr_n_blocks", n_blocks); memset(env, 0, sizeof(env[0])); - be_assure_dom_front(birg); + be_assure_dom_front(irg); env->irg = irg; - env->domfronts = be_get_birg_dom_front(birg); + env->domfronts = be_get_irg_dom_front(irg); env->new_phis = NEW_ARR_F(ir_node*, 0); env->worklist = new_waitq(); + env->phase = new_phase(irg, init_constr_info); - set_using_irn_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 */ @@ -280,12 +453,12 @@ void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg) void be_ssa_construction_destroy(be_ssa_construction_env_t *env) { stat_ev_int("bessaconstr_phis", ARR_LEN(env->new_phis)); + phase_free(env->phase); del_waitq(env->worklist); DEL_ARR_F(env->new_phis); - clear_using_irn_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"); @@ -298,18 +471,19 @@ 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); + if (env->mode == NULL) { + env->mode = get_irn_mode(copy); + env->phi_cls = arch_get_irn_reg_class_out(copy); } else { assert(env->mode == get_irn_mode(copy)); } block = get_nodes_block(copy); - if(!irn_visited(block)) { + if (!has_definition(env, block)) { waitq_put(env->worklist, block); } - introduce_def_at_block(block, copy); + introduce_definition(env, copy); } void be_ssa_construction_add_copies(be_ssa_construction_env_t *env, @@ -319,19 +493,20 @@ 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]); + if (env->mode == NULL) { + 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]; + for (i = 0; i < copies_len; ++i) { + ir_node *copy = copies[i]; ir_node *block = get_nodes_block(copy); assert(env->mode == get_irn_mode(copy)); - if(!irn_visited(block)) { + if (!has_definition(env, block)) { waitq_put(env->worklist, block); } - introduce_def_at_block(block, copy); + introduce_definition(env, copy); } } @@ -346,57 +521,95 @@ ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env) return env->new_phis; } +/** + * Fixes all arguments of a newly constructed phi. + * + * @see insert_dummy_phi + */ +static void fix_phi_arguments(be_ssa_construction_env_t *env, ir_node *phi) +{ + constr_info *info = phase_get_irn_data(env->phase, phi); + ir_node *block = get_nodes_block(phi); + int i; + int n_preds = get_Block_n_cfgpreds(block); + + DBG((dbg, LEVEL_3, "\tfixing phi arguments %+F\n", phi)); + + for (i = 0; i < n_preds; ++i) { + ir_node *op = get_irn_n(phi, i); + + if (is_definition(env, op) || is_Dummy(op)) { + ir_node *pred_block = get_Block_cfgpred_block(block, i); + ir_node *pred_def = search_def_end_of_block(env, pred_block); + + DBG((dbg, LEVEL_1, "\t...%+F(%d) -> %+F\n", phi, i, pred_def)); + set_irn_n(phi, i, pred_def); + } + } + + info->already_processed = true; +} + 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); + be_timer_push(T_SSA_CONSTR); - if(!env->iterated_domfront_calculated) { + if (!env->iterated_domfront_calculated) { mark_iterated_dominance_frontiers(env); env->iterated_domfront_calculated = 1; } + DBG((dbg, LEVEL_1, "\tfixing users array\n")); + + assert(waitq_empty(env->worklist)); + stat_ev_tim_push(); - for(i = 0; i < nodes_len; ++i) { + + for (i = 0; i < nodes_len; ++i) { + const ir_edge_t *edge, *next; ir_node *value = nodes[i]; + DBG((dbg, LEVEL_3, "\tfixing users of %+F\n", value)); + introduce_definition(env, value); - /* - * 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; + ir_node *use = get_edge_src_irn(edge); - if(env->ignore_uses != NULL && - ir_nodeset_contains(env->ignore_uses, use)) + 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 *predblock = get_Block_cfgpred_block(block, pos); - at = sched_last(predblock); - } + introduce_use(env, use); + } + } - def = search_def(env, at); + assert(!waitq_empty(env->worklist)); - if(def == NULL) { - panic("no definition found for %+F at position %d\n", use, pos); - } + while (!waitq_empty(env->worklist)) { + ir_node *use = (ir_node *)waitq_get(env->worklist); + constr_info *info = phase_get_irn_data(env->phase, use); + + if (info->already_processed) + continue; - DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def)); - set_irn_n(use, pos, def); - stat_ev_cnt_inc(uses); + if (is_Phi(use)) { + fix_phi_arguments(env, use); } + else { + DBG((dbg, LEVEL_3, "\tsearching def for %+F at %+F\n", use, get_nodes_block(use))); + search_def_at_block(env, use); + } + + stat_ev_cnt_inc(uses); } - BE_TIMER_POP(t_ssa_constr); + + be_timer_pop(T_SSA_CONSTR); stat_ev_tim_pop("bessaconstr_fix_time"); stat_ev_cnt_done(uses, "bessaconstr_uses"); @@ -413,20 +626,19 @@ void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env, { int i, n; - BE_TIMER_PUSH(t_ssa_constr); + be_timer_push(T_SSA_CONSTR); n = ARR_LEN(env->new_phis); - for(i = 0; i < n; ++i) { + for (i = 0; i < n; ++i) { ir_node *phi = env->new_phis[i]; be_liveness_introduce(lv, phi); } - BE_TIMER_POP(t_ssa_constr); + be_timer_pop(T_SSA_CONSTR); } +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr) void be_init_ssaconstr(void) { FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr"); } - -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);