* @author Sebastian Hack
* @date 04.04.2006
*/
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
#include <limits.h>
#include "irnode_t.h"
#include "iredges_t.h"
#include "ircons_t.h"
+#include "irphase_t.h"
#include "irgwalk.h"
#include "irtools.h"
+#include "height.h"
+
#include "benode_t.h"
#include "besched_t.h"
#include "beschedmris.h"
struct _mris_env_t {
- firm_dbg_module_t *dbg;
+ phase_t 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;
#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(phase_t *ph, 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]));
+ 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);
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)
{
set_irn_visited(desc, visited);
}
}
+
+ foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
+ ir_node *desc = get_edge_src_irn(edge);
+ if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
+ obstack_ptr_grow(&env->obst, desc);
+ set_irn_visited(desc, visited);
+ }
+ }
}
static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
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;
}
}
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) {
reaches_walker(env, src, tgt, &found, visited);
return found;
}
+#endif
static INLINE ir_node *skip_Projs(ir_node *irn)
{
nodeset_insert(nodes, irn);
}
- compute_heights(env);
-
while(nodeset_count(nodes) > 0) {
mris_irn_t *mi;
ir_node *irn;
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) {
+ 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 a lineage beginning with highest_node. */
mi = get_mris_irn(env, highest_node);
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);
*/
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)
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);
+ add_irn_dep(lowest_desc, in[1]);
}
obstack_free(&env->obst, in);
/* recompute the heights if desired. */
if(recompute_height)
- compute_heights(env);
+ heights_recompute(env->heights);
}
}
/* 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;
/* 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)
+ if(get_irn_ins_or_deps(start) == 0)
return 0;
- op = get_irn_n(start, 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) {
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);
+
+ add_irn_dep(start, last);
}
/* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
/* 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);
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;
+ }
}
}
}
mris_env_t *env = data;
env->bl = bl;
lineage_formation(env);
- fuse_lineages(env);
+ //fuse_lineages(env);
}
{
mris_env_t *env = xmalloc(sizeof(env[0]));
+ 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;
env->visited = 0;
- env->inserted = new_nodeset(128);
+ env->heights = heights_new(birg->irg);
INIT_LIST_HEAD(&env->lineage_head);
FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
obstack_init(&env->obst);
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);
}
projects / libfirm / blobdiff