X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedmris.c;h=7de3bcc9b7c6d0347525d3b313fa74947461fa06;hb=fe36a9963a604d99e4a1d10302944a4b3892a897;hp=54463c0378846bc48972708b9defe9b17a45d994;hpb=863d31d7a5c8210432fef88b30fc3e8353131538;p=libfirm diff --git a/ir/be/beschedmris.c b/ir/be/beschedmris.c index 54463c037..7de3bcc9b 100644 --- a/ir/be/beschedmris.c +++ b/ir/be/beschedmris.c @@ -1,14 +1,35 @@ +/* + * 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 @@ -24,18 +45,17 @@ #include "irgwalk.h" #include "irtools.h" #include "irbitset.h" - +#include "irnodeset.h" #include "height.h" -#include "benode_t.h" -#include "besched_t.h" +#include "benode.h" +#include "besched.h" #include "beschedmris.h" -#include "benodesets.h" +#include "beirg.h" struct _mris_env_t { - phase_t ph; + ir_phase ph; heights_t *heights; - const arch_env_t *aenv; ir_graph *irg; ir_node *bl; int visited; @@ -57,62 +77,15 @@ typedef struct _mris_irn_t { #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 void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data) +static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn, void *data) { 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); - - if(get_irn_visited(irn) >= visited) { - DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height)); - return mi->height; - } - - else { - const ir_edge_t *edge; - - set_irn_visited(irn, visited); - mi->height = 0; - - foreach_out_edge(irn, edge) { - ir_node *dep = get_edge_src_irn(edge); - - if(!is_Block(dep) && get_nodes_block(dep) == env->bl) { - int dep_height = compute_height(env, dep, visited); - mi->height = MAX(mi->height, dep_height); - } - } - - mi->height++; - DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height)); - } - - return mi->height; -} - -static void compute_heights(mris_env_t *env) -{ - const ir_edge_t *edge; - unsigned long visited; - - visited = get_irg_visited(env->irg) + 1; - set_irg_visited(env->irg, visited); - - foreach_out_edge(env->bl, edge) { - ir_node *dep = get_edge_src_irn(edge); - if(to_appear(env, dep)) - compute_height(env, dep, visited); - } -} -#endif - #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, bitset_t *visited) @@ -185,99 +158,40 @@ 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) { - - set_irn_visited(irn, visited); - - if(irn == tgt) - *found = 1; - else { - int i, n; - - for(i = 0, n = get_irn_arity(irn); i < n; ++i) { - ir_node *op = get_irn_n(irn, i); - if(!*found) - reaches_walker(env, op, tgt, found, visited); - } - } - } -} - -static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt) -{ - int found = 0; - unsigned long visited = get_irg_visited(env->irg) + 1; - - set_irg_visited(env->irg, visited); - reaches_walker(env, src, tgt, &found, visited); - return found; -} -#endif - -static INLINE ir_node *skip_Projs(ir_node *irn) +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; - - for(i = 0; in[i]; ++i) { - if(get_irn_mode(in[i]) == mode_T) { - const ir_edge_t *edge; - ir_node *proj = NULL; - ir_node *first = NULL; - - foreach_out_edge(in[i], edge) { - ir_node *desc = get_edge_src_irn(edge); - - first = first ? first : desc; - if(get_irn_mode(desc) == mode_M) { - proj = desc; - break; - } - } - - proj = proj ? proj : first; - assert(proj); - in[i] = proj; - } - } -} -#endif - static void lineage_formation(mris_env_t *env) { DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg); - nodeset *nodes = new_nodeset(128); + 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); } - 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 *start; + 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; 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)) { + foreach_ir_nodeset(&nodes, irn, iter) { unsigned height = get_irn_height(env->heights, irn); if(height > curr_height) { highest_node = irn; @@ -296,7 +210,7 @@ static void lineage_formation(mris_env_t *env) 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. @@ -353,7 +267,7 @@ static void lineage_formation(mris_env_t *env) start_mi->lineage_end = lowest_desc; lowest_mi->lineage_start = start; - nodeset_remove(nodes, lowest_desc); + ir_nodeset_remove(&nodes, lowest_desc); } /* else we cannot extend this lineage, so break. */ @@ -372,6 +286,8 @@ static void lineage_formation(mris_env_t *env) if(recompute_height) 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) @@ -486,18 +402,18 @@ void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) { mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg) { - mris_env_t *env = xmalloc(sizeof(env[0])); + mris_env_t *env = XMALLOC(mris_env_t); + ir_graph *irg = be_get_birg_irg(birg); - phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init); - 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->irg = irg; env->visited = 0; - env->heights = heights_new(birg->irg); + 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;