/*
- * 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.
*
*/
/**
+ * @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 <limits.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 "benodesets.h"
#include "beirg.h"
struct _mris_env_t {
- ir_phase ph;
+ ir_phase ph;
heights_t *heights;
- const arch_env_t *aenv;
ir_graph *irg;
ir_node *bl;
int visited;
#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(ir_phase *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)
+static int compute_height(mris_env_t *env, ir_node *irn, ir_visited_t visited)
{
mris_irn_t *mi = get_mris_irn(env, irn);
static void compute_heights(mris_env_t *env)
{
const ir_edge_t *edge;
- unsigned long visited;
+ ir_visited_t visited;
visited = get_irg_visited(env->irg) + 1;
set_irg_visited(env->irg, visited);
}
#if 0
-static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
+static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, ir_visited_t visited)
{
if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
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;
+ ir_visited_t visited = get_irg_visited(env->irg) + 1;
set_irg_visited(env->irg, visited);
reaches_walker(env, src, tgt, &found, visited);
}
#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;
}
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;
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.
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. */
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_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", 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->heights = heights_new(irg);