* Minimum Register Instruction Sequencing to Reduce Register Spills
* in out-of-order issue superscalar architectures
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <limits.h>
#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 "beirg.h"
struct _mris_env_t {
ir_phase ph;
heights_t *heights;
- const arch_env_t *aenv;
ir_graph *irg;
ir_node *bl;
int visited;
return mi;
}
-#if 0
-static int compute_height(mris_env_t *env, ir_node *irn, ir_visited_t 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;
- ir_visited_t 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)
foreach_out_edge(irn, edge) {
ir_node *desc = get_edge_src_irn(edge);
- if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
+ 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)) {
+ if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
obstack_ptr_grow(&env->obst, desc);
bitset_add_irn(visited, desc);
}
grow_all_descendands(env, irn, visited);
#if 0
- if(get_irn_mode(irn) == mode_T) {
+ 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);
unsigned lowest_height = INT_MAX;
int i;
- for(i = 0; in[i]; ++i) {
+ for (i = 0; in[i]; ++i) {
unsigned height = get_irn_height(env->heights, in[i]);
- if(height < lowest_height) {
+ if (height < lowest_height) {
lowest_height = height;
lowest_index = i;
}
}
- if(i > 0) {
+ if (i > 0) {
ir_node *tmp = in[0];
in[0] = in[lowest_index];
in[lowest_index] = tmp;
return in[0];
}
-#if 0
-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) {
-
- 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;
- ir_visited_t 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);
foreach_out_edge(env->bl, edge) {
ir_node *irn = get_edge_src_irn(edge);
- if(to_appear(env, irn))
+ if (to_appear(env, irn))
ir_nodeset_insert(&nodes, irn);
}
- while(ir_nodeset_size(&nodes) > 0) {
+ while (ir_nodeset_size(&nodes) > 0) {
mris_irn_t *mi;
ir_node *irn;
ir_node *highest_node = NULL;
/* search the highest node which is not yet in a lineage. */
foreach_ir_nodeset(&nodes, irn, iter) {
unsigned height = get_irn_height(env->heights, irn);
- if(height > curr_height) {
+ if (height > curr_height) {
highest_node = irn;
curr_height = height;
}
lowest_desc = put_lowest_in_front(env, in);
/* as long as the current highest node has still descendants */
- while(lowest_desc) {
+ 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);
- 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]; ++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)) {
+ if (n_desc > 1 && !be_is_Keep(lowest_desc)) {
ir_node *op;
int i, n;
- for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
- ir_node *cmp;
-
- op = get_irn_in_or_dep(lowest_desc, i);
- cmp = highest_is_tuple ? skip_Projs(op) : op;
-
- // if(cmp == highest_node)
- if(op == highest_node)
+ for (i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
+ op = get_irn_in_or_dep(lowest_desc, i);
+ if (op == highest_node)
break;
}
assert(i < n && "could not find operand");
//replace_tuple_by_repr_proj(env, &in[1]);
- if(!is_Proj(lowest_desc))
+ if (!is_Proj(lowest_desc))
add_irn_dep(lowest_desc, in[1]);
}
obstack_free(&env->obst, in);
/* if the current lowest node is not yet in a lineage, add it to the current one. */
- if(!lowest_mi->lineage_start) {
+ if (!lowest_mi->lineage_start) {
/* mark the current lowest node as the last one in the lineage. */
highest_mi->lineage_next = lowest_desc;
start_mi->lineage_end = lowest_desc;
}
/* recompute the heights if desired. */
- if(recompute_height)
+ if (recompute_height)
heights_recompute(env->heights);
}
ir_node *v_start = v->lineage_start;
ir_node *start = skip_Projs(v_start);
- if(be_is_Keep(start))
+ if (be_is_Keep(start))
return 0;
/* set lineage end of nodes in u to end of v. */
irn = last = u->lineage_start;
mi = get_mris_irn(env, irn);
- while(irn && 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. */
- if(get_irn_ins_or_deps(start) == 0)
+ if (get_irn_ins_or_deps(start) == 0)
return 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 = get_irn_out_edge_first(last);
+ last = get_edge_src_irn(edge);
}
/* 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 && 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;
again:
foreach_lineage(env, u, tmp1) {
foreach_lineage(env, v, tmp2) {
- if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
+ 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))
+ if (uv && !vu) {
+ if (fuse_two_lineages(env, u, v))
goto again;
}
}
fuse_lineages(env);
}
-static int mris_edge_hook(FILE *F, ir_node *irn)
+static void mris_edge_hook(FILE *F, ir_node *irn)
{
mris_irn_t *mi = get_mris_irn(dump_env, irn);
- if(mi->lineage_next) {
+ 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();
+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);
+ dump_ir_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 *be_sched_mris_preprocess(ir_graph *irg)
{
- mris_env_t *env = xmalloc(sizeof(env[0]));
- ir_graph *irg = be_get_birg_irg(birg);
+ mris_env_t *env = XMALLOC(mris_env_t);
- phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
- env->aenv = be_get_birg_arch_env(birg);
+ phase_init(&env->ph, irg, mris_irn_data_init);
env->irg = irg;
env->visited = 0;
env->heights = heights_new(irg);
void be_sched_mris_free(mris_env_t *env)
{
- phase_free(&env->ph);
+ phase_deinit(&env->ph);
heights_free(env->heights);
free(env);
}
projects / libfirm / blobdiff