X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedmris.c;h=8ac256e1fc97ecaed4b4e7f50acc38cc43930f4c;hb=8d07d17eb2ade0b6b4aef0ebd68d6af3cc368b06;hp=32cfc149ea71504c129b857b21be925d0aacea63;hpb=1990c0a38e4c19212e7e306a0902c65809f28228;p=libfirm diff --git a/ir/be/beschedmris.c b/ir/be/beschedmris.c index 32cfc149e..8ac256e1f 100644 --- a/ir/be/beschedmris.c +++ b/ir/be/beschedmris.c @@ -1,11 +1,37 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** + * @file + * @brief Implements a list scheduler for the MRIS algorithm. + * @author Sebastian Hack + * @date 04.04.2006 + * @version $Id$ + * * Implements a list scheduler for the MRIS algorithm in: * Govindarajan, Yang, Amaral, Zhang, Gao * Minimum Register Instruction Sequencing to Reduce Register Spills * in out-of-order issue superscalar architectures - * @author Sebastian Hack - * @date 04.04.2006 */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif #include @@ -16,27 +42,32 @@ #include "irnode_t.h" #include "iredges_t.h" #include "ircons_t.h" +#include "irphase_t.h" +#include "irdump_t.h" #include "irgwalk.h" #include "irtools.h" +#include "irbitset.h" +#include "height.h" #include "benode_t.h" #include "besched_t.h" #include "beschedmris.h" +#include "beirg.h" struct _mris_env_t { - firm_dbg_module_t *dbg; + ir_phase ph; + heights_t *heights; const arch_env_t *aenv; ir_graph *irg; ir_node *bl; - nodeset *inserted; int visited; struct list_head lineage_head; struct obstack obst; + DEBUG_ONLY(firm_dbg_module_t *dbg;) }; typedef struct _mris_irn_t { int visited; - int height; ir_node *lineage_start; ir_node *lineage_next; ir_node *lineage_end; @@ -45,23 +76,19 @@ typedef struct _mris_irn_t { #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl) -#define get_irn_height(env, irn) (get_mris_irn(env, irn)->height) +#define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn)) #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list) -static mris_irn_t *get_mris_irn(mris_env_t *env, ir_node *irn) +static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn, void *data) { - mris_irn_t *mi = get_irn_link(irn); - - if(!mi) { - mi = obstack_alloc(&env->obst, sizeof(mi[0])); - memset(mi, 0, sizeof(mi[0])); - set_irn_link(irn, mi); - INIT_LIST_HEAD(&mi->lineage_list); - } - + mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0])); + (void) irn; + memset(mi, 0, sizeof(mi[0])); + INIT_LIST_HEAD(&mi->lineage_list); return mi; } +#if 0 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited) { mris_irn_t *mi = get_mris_irn(env, irn); @@ -107,33 +134,42 @@ static void compute_heights(mris_env_t *env) compute_height(env, dep, visited); } } +#endif -#define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep)) +#define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep)) -static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited) +static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited) { const ir_edge_t *edge; - assert(get_irn_mode(irn) != mode_T); + // assert(get_irn_mode(irn) != mode_T); foreach_out_edge(irn, edge) { ir_node *desc = get_edge_src_irn(edge); - if(valid_node(env, desc) && get_irn_visited(desc) < visited) { + if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) { + obstack_ptr_grow(&env->obst, desc); + bitset_add_irn(visited, desc); + } + } + + foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) { + ir_node *desc = get_edge_src_irn(edge); + if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) { obstack_ptr_grow(&env->obst, desc); - set_irn_visited(desc, visited); + bitset_add_irn(visited, desc); } } } static ir_node **all_descendants(mris_env_t *env, ir_node *irn) { - unsigned long visited; - const ir_edge_t *edge; + bitset_t *visited = bitset_irg_malloc(env->irg); - visited = get_irg_visited(env->irg) + 1; - set_irg_visited(env->irg, visited); + grow_all_descendands(env, irn, visited); +#if 0 if(get_irn_mode(irn) == mode_T) { + const ir_edge_t *edge; foreach_out_edge(irn, edge) { ir_node *desc = get_edge_src_irn(edge); assert(is_Proj(desc) && get_irn_mode(desc) != mode_T); @@ -143,21 +179,22 @@ static ir_node **all_descendants(mris_env_t *env, ir_node *irn) else grow_all_descendands(env, irn, visited); - +#endif + bitset_free(visited); obstack_ptr_grow(&env->obst, NULL); return obstack_finish(&env->obst); } static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in) { - int lowest_index = 0; - int lowest_height = INT_MAX; + int lowest_index = 0; + unsigned lowest_height = INT_MAX; int i; for(i = 0; in[i]; ++i) { - mris_irn_t *mi = get_mris_irn(env, in[i]); - if(mi->height < lowest_height) { - lowest_height = mi->height; + unsigned height = get_irn_height(env->heights, in[i]); + if(height < lowest_height) { + lowest_height = height; lowest_index = i; } } @@ -171,6 +208,7 @@ static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in) return in[0]; } +#if 0 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited) { if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) { @@ -200,12 +238,14 @@ static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt) reaches_walker(env, src, tgt, &found, visited); return found; } +#endif static INLINE ir_node *skip_Projs(ir_node *irn) { return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn; } +#if 0 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in) { int i; @@ -232,51 +272,56 @@ static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in) } } } +#endif static void lineage_formation(mris_env_t *env) { - firm_dbg_module_t *dbg = env->dbg; - nodeset *nodes = new_nodeset(128); + DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg); + ir_nodeset_t nodes; + const ir_edge_t *edge; - const ir_edge_t *edge; + ir_nodeset_init(&nodes); foreach_out_edge(env->bl, edge) { ir_node *irn = get_edge_src_irn(edge); if(to_appear(env, irn)) - nodeset_insert(nodes, irn); + ir_nodeset_insert(&nodes, irn); } - compute_heights(env); - - while(nodeset_count(nodes) > 0) { + while(ir_nodeset_size(&nodes) > 0) { mris_irn_t *mi; - ir_node *irn; - ir_node *highest_node = NULL; - ir_node *lowest_desc = NULL; + ir_node *irn; + ir_node *highest_node = NULL; + ir_node *lowest_desc = NULL; + ir_node *start; + mris_irn_t *start_mi; + ir_nodeset_iterator_t iter; ir_node **in; int recompute_height = 0; - int curr_height = 0; + unsigned curr_height = 0; /* search the highest node which is not yet in a lineage. */ - for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) { - mris_irn_t *inf = get_mris_irn(env, irn); - if(inf->height > curr_height) { + foreach_ir_nodeset(&nodes, irn, iter) { + unsigned height = get_irn_height(env->heights, irn); + if(height > curr_height) { highest_node = irn; - curr_height = inf->height; + curr_height = height; } } assert(highest_node); - DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env, highest_node))); + DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node))); + + start = highest_node; + mi = start_mi = get_mris_irn(env, highest_node); /* start a lineage beginning with highest_node. */ - mi = get_mris_irn(env, highest_node); mi->lineage_start = highest_node; mi->lineage_next = NULL; mi->lineage_end = NULL; list_add(&mi->lineage_list, &env->lineage_head); - nodeset_remove(nodes, highest_node); + ir_nodeset_remove(&nodes, highest_node); /* put all descendants in an array. @@ -290,53 +335,50 @@ static void lineage_formation(mris_env_t *env) while(lowest_desc) { mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc); mris_irn_t *highest_mi = get_mris_irn(env, highest_node); - mris_irn_t *start_mi = get_mris_irn(env, highest_mi->lineage_start); int highest_is_tuple = get_irn_mode(highest_node) == mode_T; int n_desc; - DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, mi->height)); + DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc))); /* count the number of all descendants which are not the lowest descendant */ - for(n_desc = 0; in[n_desc + 1]; ++n_desc); + for(n_desc = 0; in[n_desc]; ++n_desc); /* we insert a CopyKeep node to express the artificial dependencies from the lowest descendant to all other descendants. */ if(n_desc > 1 && !be_is_Keep(lowest_desc)) { - const arch_register_class_t *cls; - ir_node *copy_keep, *op; + ir_node *op; int i, n; - for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) { + for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) { ir_node *cmp; - op = get_irn_n(lowest_desc, i); + op = get_irn_in_or_dep(lowest_desc, i); cmp = highest_is_tuple ? skip_Projs(op) : op; - if(cmp == highest_node) + // if(cmp == highest_node) + if(op == highest_node) break; } assert(i < n && "could not find operand"); - cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0)); - replace_tuple_by_repr_proj(env, &in[1]); - copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op)); - set_irn_n(lowest_desc, i, copy_keep); - nodeset_insert(env->inserted, copy_keep); + //replace_tuple_by_repr_proj(env, &in[1]); + if(!is_Proj(lowest_desc)) + add_irn_dep(lowest_desc, in[1]); } obstack_free(&env->obst, in); - /* mark the current lowest node as the last one in the lineage. */ - highest_mi->lineage_next = lowest_desc; - start_mi->lineage_end = lowest_desc; - /* if the current lowest node is not yet in a lineage, add it to the current one. */ if(!lowest_mi->lineage_start) { - lowest_mi->lineage_start = highest_mi->lineage_start; - nodeset_remove(nodes, lowest_desc); + /* mark the current lowest node as the last one in the lineage. */ + highest_mi->lineage_next = lowest_desc; + start_mi->lineage_end = lowest_desc; + + lowest_mi->lineage_start = start; + ir_nodeset_remove(&nodes, lowest_desc); } /* else we cannot extend this lineage, so break. */ @@ -353,15 +395,16 @@ static void lineage_formation(mris_env_t *env) /* recompute the heights if desired. */ if(recompute_height) - compute_heights(env); + heights_recompute(env->heights); } + + ir_nodeset_destroy(&nodes); } static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v) { mris_irn_t *mi; - mris_irn_t *copy_mi; - ir_node *irn, *last, *copy; + ir_node *irn, *last; ir_node *u_end = u->lineage_end; ir_node *v_start = v->lineage_start; ir_node *start = skip_Projs(v_start); @@ -372,7 +415,7 @@ static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v) /* set lineage end of nodes in u to end of v. */ irn = last = u->lineage_start; mi = get_mris_irn(env, irn); - while(irn != u_end) { + while(irn && irn != u_end) { mi = get_mris_irn(env, irn); mi->lineage_end = v->lineage_end; last = irn; @@ -380,43 +423,33 @@ static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v) } /* insert a CopyKeep to make lineage v dependent on u. */ - { - const arch_register_class_t *cls; - ir_node *op = NULL; - - if(get_irn_arity(start) == 0) - return 0; - - op = get_irn_n(start, 0); + if(get_irn_ins_or_deps(start) == 0) + return 0; - cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0)); - if(get_irn_mode(last) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(last, edge) { - last = get_edge_src_irn(edge); - break; - } + if(get_irn_mode(last) == mode_T) { + const ir_edge_t *edge; + foreach_out_edge(last, edge) { + last = get_edge_src_irn(edge); + break; } - copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op)); - set_irn_n(start, 0, copy); - copy_mi = get_mris_irn(env, copy); - nodeset_insert(env->inserted, copy); } /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */ - mi->lineage_next = copy; - copy_mi->lineage_start = u->lineage_start; - copy_mi->lineage_end = v->lineage_end; - copy_mi->lineage_next = v_start; + mi->lineage_next = v_start; + + /* add a dependency from the first node in v's lineage to the last in u's */ + add_irn_dep(u_end, v_start); /* set lineage start of nodes in v to start of u. */ irn = v->lineage_start; - while(irn != v->lineage_end) { + while(irn && irn != v->lineage_end) { mris_irn_t *mi = get_mris_irn(env, irn); mi->lineage_start = u->lineage_start; irn = mi->lineage_next; } + heights_recompute(env->heights); + mi = get_mris_irn(env, v_start); list_del(&mi->lineage_list); @@ -425,23 +458,27 @@ static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v) static void fuse_lineages(mris_env_t *env) { - int fused = 1; mris_irn_t *u, *v, *tmp1, *tmp2; again: foreach_lineage(env, u, tmp1) { foreach_lineage(env, v, tmp2) { - if(u == v) - continue; - - if(!reaches(env, u->lineage_start, v->lineage_end) && reaches(env, v->lineage_start, u->lineage_end)) { - if(fuse_two_lineages(env, u, v)) - goto again; + if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end + && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) { + int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end); + int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end); + + if(uv && !vu) { + if(fuse_two_lineages(env, u, v)) + goto again; + } } } } } +static mris_env_t *dump_env = NULL; + static void block_walker(ir_node *bl, void *data) { mris_env_t *env = data; @@ -450,47 +487,53 @@ static void block_walker(ir_node *bl, void *data) fuse_lineages(env); } +static int mris_edge_hook(FILE *F, ir_node *irn) +{ + mris_irn_t *mi = get_mris_irn(dump_env, irn); + + if(mi->lineage_next) { + fprintf(F, "edge:{sourcename:\""); + PRINT_NODEID(mi->lineage_next); + fprintf(F, "\" targetname:\""); + PRINT_NODEID(irn); + fprintf(F, "\" color:lilac}\n"); + } + return 1; +} + +void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) { + DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook(); + + dump_consts_local(0); + set_dump_node_edge_hook(mris_edge_hook); + dump_env = env; + dump_ir_block_graph(env->irg, suffix); + set_dump_node_edge_hook(old); +} mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg) { mris_env_t *env = xmalloc(sizeof(env[0])); + ir_graph *irg = be_get_birg_irg(birg); - env->aenv = birg->main_env->arch_env; - env->irg = birg->irg; + phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL); + env->aenv = be_get_birg_arch_env(birg); + env->irg = irg; env->visited = 0; - env->inserted = new_nodeset(128); + env->heights = heights_new(irg); INIT_LIST_HEAD(&env->lineage_head); FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris"); obstack_init(&env->obst); - irg_walk_graph(env->irg, firm_clear_link, NULL, NULL); - irg_block_walk_graph(birg->irg, block_walker, NULL, env); + irg_walk_graph(irg, firm_clear_link, NULL, NULL); + irg_block_walk_graph(irg, block_walker, NULL, env); obstack_free(&env->obst, NULL); + // dump_ir_block_graph_mris(env, "-mris"); return env; } -static void cleanup_inserted(mris_env_t *env) -{ - ir_node *irn; - - foreach_nodeset(env->inserted, irn) { - int i, n; - ir_node *tgt; - - assert(be_is_CopyKeep(irn)); - tgt = get_irn_n(irn, be_pos_CopyKeep_op); - - /* reroute the edges, remove from schedule and make it invisible. */ - edges_reroute(irn, tgt, env->irg); - if (sched_is_scheduled(irn)) - sched_remove(irn); - for(i = -1, n = get_irn_arity(irn); i < n; ++i) - set_irn_n(irn, i, new_r_Bad(env->irg)); - } -} - void be_sched_mris_free(mris_env_t *env) { - cleanup_inserted(env); - del_nodeset(env->inserted); + phase_free(&env->ph); + heights_free(env->heights); free(env); }