+/*
+ * 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"
#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 {
- phase_t ph;
+ 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;
#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, const 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;
}
#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);
else
grow_all_descendands(env, irn, visited);
-
+#endif
+ bitset_free(visited);
obstack_ptr_grow(&env->obst, NULL);
return obstack_finish(&env->obst);
}
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;
}
}
}
+#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);
}
- 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;
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;
assert(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.
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, 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. */
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)
{
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);
}
/* 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;
static void fuse_lineages(mris_env_t *env)
{
- int fused = 1;
mris_irn_t *u, *v, *tmp1, *tmp2;
again:
}
}
+static mris_env_t *dump_env = NULL;
+
static void block_walker(ir_node *bl, void *data)
{
mris_env_t *env = 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);
- 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->aenv = be_get_birg_arch_env(birg);
+ env->irg = irg;
env->visited = 0;
- env->inserted = new_nodeset(128);
- 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;
}
-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);
phase_free(&env->ph);
- del_nodeset(env->inserted);
heights_free(env->heights);
free(env);
}
projects / libfirm / blobdiff