* @cvs-id $Id$
*/
#ifdef HAVE_CONFIG_H
-#include "config.h"
+#include <config.h>
#endif
#include <limits.h>
#include "height.h"
#include "beabi.h"
+#include "bemodule.h"
#include "benode_t.h"
#include "besched_t.h"
-#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
-#endif /* WITH_LIBCORE */
#define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
int *idx_map; /**< Mapping irn indices to per block indices */
unsigned max_height; /**< maximum height in the current block */
rss_opts_t *opts; /**< The options */
+ be_lv_t *liveness; /**< The liveness information for this irg */
+ pset *live_block; /**< Values alive at end of block */
const arch_register_class_t *cls; /**< The current register class */
DEBUG_ONLY(firm_dbg_module_t *dbg);
} rss_t;
* We need some special nodes:
* a source and a sink for all live-in and live-out values of a block
*/
-
enum {
iro_rss_Source,
iro_rss_Sink,
iro_rss_last
};
+/** The opcode of the rss_Source node once allocated. */
+static ir_op *op_rss_Source;
+/** The opcode of the rss_Sink node once allocated. */
+static ir_op *op_rss_Sink;
+
+/** The rss_Source node of the current graph. */
static ir_node *_source = NULL;
+/** The rss_Sink node of the current graph. */
static ir_node *_sink = NULL;
#define is_Source(irn) ((irn) == _source)
RSS_DUMP_NONE,
};
-#ifdef WITH_LIBCORE
static const lc_opt_enum_int_items_t dump_items[] = {
{ "none", RSS_DUMP_NONE },
{ "cbc", RSS_DUMP_CBC },
};
static const lc_opt_table_entry_t rss_option_table[] = {
- LC_OPT_ENT_ENUM_MASK("dump", "dump phases (none, cbc, pkg, kill, dvg, maxac, all)", &dump_var),
+ LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
{ NULL }
};
-#endif /* WITH_LIBCORE */
/******************************************************************************
* _ _ __ _ _
******************************************************************************/
/**
- * Acquire opcodes and create source and sink nodes.
+ * Acquire opcodes if needed and create source and sink nodes.
*/
static void init_rss_special_nodes(ir_graph *irg) {
- ir_node *block = get_irg_start_block(irg);
- int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
- ir_op *op_rss_Source = new_ir_op(iro_rss_base + iro_rss_Source, "rss_Source", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
- ir_op *op_rss_Sink = new_ir_op(iro_rss_base + iro_rss_Sink, "rss_Sink", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
- _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
- _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
+ ir_node *block;
+
+ if (op_rss_Source == NULL) {
+ int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
+ op_rss_Source = new_ir_op(iro_rss_base + iro_rss_Source, "rss_Source", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
+ op_rss_Sink = new_ir_op(iro_rss_base + iro_rss_Sink, "rss_Sink", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
+ }
+ block = get_irg_start_block(irg);
+ _source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
+ _sink = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
}
static int cmp_int(const void *a, const void *b) {
*
*****************************************************/
+#ifdef DEBUG_libfirm
static void dump_nodeset(nodeset *ns, const char *prefix) {
ir_node *irn;
foreach_nodeset(ns, irn) {
ir_fprintf(stderr, "%s%+F\n", prefix, irn);
}
}
+#endif
static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
const char *irg_name;
fprintf(f, "layoutalgorithm: mindepth\n");
fprintf(f, "manhattan_edges: yes\n\n");
- /* first: reset dumped flag of all nodes */
- foreach_plist(rss->nodes, el) {
- ir_node *irn = plist_element_get_value(el);
- rss_irn_t *rirn = get_rss_irn(rss, irn);
- rirn->dumped = 0;
+ {
+ /* reset dump_flag */
+ ir_node *irn;
+ foreach_phase_irn(&rss->ph, irn) {
+ rss_irn_t *node = get_rss_irn(rss, irn);
+ node->dumped = 0;
+ }
}
/* dump all nodes and their killers */
fprintf(f, "layoutalgorithm: mindepth\n");
fprintf(f, "manhattan_edges: yes\n\n");
+ {
+ /* reset dump_flag */
+ ir_node *irn;
+ foreach_phase_irn(&rss->ph, irn) {
+ rss_irn_t *node = get_rss_irn(rss, irn);
+ node->dumped = 0;
+ }
+ }
+
foreach_plist(rss->nodes, el) {
ir_node *irn = plist_element_get_value(el);
rss_irn_t *rirn = get_rss_irn(rss, irn);
if (max_ac && nodeset_find(max_ac, irn))
c1 = "color:yellow";
- if (rirn->chain)
- ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
- else
- ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
- rirn->dumped = 1;
+ if (! rirn->dumped) {
+ if (rirn->chain)
+ ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
+ else
+ ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
+ rirn->dumped = 1;
+ }
foreach_plist(rirn->pkiller_list, k_el) {
ir_node *pkiller = plist_element_get_value(k_el);
return;
cur_node->desc_walk = cur_desc_walk;
- /* Stop at Barriers and Keeps */
- if (be_is_Barrier(irn) || be_is_Keep(irn))
+ /* Stop at Barriers */
+ if (be_is_Barrier(irn))
return;
/* loop over normal and dependency edges */
if (arch_irn_is(rss->arch_env, user, ignore))
continue;
- if (is_Proj(user)) {
- if (get_irn_mode(user) == mode_X && ! *got_sink)
+ /*
+ (a) mode_X means Jump -> out_edge
+ (b) Phi as user of a normal node -> out-edge
+ */
+ if (get_irn_mode(user) == mode_X || is_Phi(user)) {
+ if (! *got_sink)
goto force_sink;
+ else
+ continue;
+ }
+
+ if (is_Proj(user)) {
- if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
+ //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
}
else {
assert(! is_Proj(consumer) && "Cannot handle Projs");
- if (get_nodes_block(consumer) == block) {
- if (! arch_irn_is(rss->arch_env, consumer, ignore)) {
+ if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
+ if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) {
plist_insert_back(rss_irn->consumer_list, consumer);
DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
}
ir_node *consumer = get_edge_src_irn(edge);
if (is_Proj(consumer)) {
- if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
+ //if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
collect_consumer(rss, rss_irn, consumer, got_sink);
}
else
/* check if node info is already available */
if (rss_irn->handled)
- phase_reinit_single_irn_data(&rss->ph, irn);
+ return;
+ //phase_reinit_single_irn_data(&rss->ph, irn);
DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
}
}
+#ifdef DEBUG_libfirm
/* print the given cbc for debugging purpose */
static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
ir_node *n;
DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
}
}
+#endif
/**
* Construct the bipartite decomposition.
rss_irn_t *u = get_rss_irn(rss, u_irn);
int p_change = 1;
int c_change = 1;
+ int vrfy_ok = 1;
cbc_t *cbc;
plist_element_t *el2;
if (k_edge->tgt == t_irn && ! nodeset_find(cbc->parents, val)) {
nodeset_insert(cbc->parents, val);
p_change = 1;
- DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents\n", val));
+ DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (killed by %+F)\n", val, t_irn));
}
}
}
if (k_edge->src == s_irn && ! nodeset_find(cbc->children, val)) {
nodeset_insert(cbc->children, val);
c_change = 1;
- DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children\n", val));
+ DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (kills %+F)\n", val, s_irn));
}
}
}
rss_irn_t *s = get_rss_irn(rss, s_irn);
s->visited = 1;
/* assure bipartite property */
+#if 0
if (nodeset_find(cbc->children, s_irn)) {
nodeset_remove(cbc->children, s_irn);
DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
}
+#endif
}
/* update edges */
pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
}
+ /* verify the cbc */
+ foreach_nodeset(cbc->parents, s_irn) {
+ int is_killed = 0;
+
+ foreach_pset(cbc->kill_edges, k_edge) {
+ if (k_edge->src == s_irn) {
+ is_killed = 1;
+ pset_break(cbc->kill_edges);
+ break;
+ }
+ }
+
+ if (! is_killed) {
+ vrfy_ok = 0;
+ ir_fprintf(stderr, "Warning: parent %+F is not killed in current cbc\n", s_irn);
+ }
+ }
+ assert(vrfy_ok && "Verification of CBC failed");
+
/* add the connected bipartite component */
if (nodeset_count(cbc->parents) > 0 && nodeset_count(cbc->children) > 0 && pset_count(cbc->kill_edges) > 0)
pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
* Adds the edge src -> tgt to the dvg. Checks if reverse edge is already there (asserts).
*/
static INLINE void add_dvg_edge(rss_t *rss, dvg_t *dvg, ir_node *src, ir_node *tgt, int have_source) {
- rss_edge_t *dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
+ rss_edge_t *dvg_edge;
rss_edge_t key;
if (! have_source)
nodeset_insert(dvg->nodes, tgt);
- /* add an edge to our killer */
- dvg_edge->src = src;
- dvg_edge->tgt = tgt;
- dvg_edge->next = NULL;
-
key.src = tgt;
key.tgt = src;
assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
- /* add the edge to the DVG */
- DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
- pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
+ key.src = src;
+ key.tgt = tgt;
+ if (NULL != pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
+ /* add the edge to the DVG */
+ dvg_edge = obstack_alloc(phase_obst(&rss->ph), sizeof(*dvg_edge));
+
+ dvg_edge->src = src;
+ dvg_edge->tgt = tgt;
+ dvg_edge->next = NULL;
+
+ DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, tgt));
+ pset_insert(dvg->edges, dvg_edge, HASH_RSS_EDGE(dvg_edge));
+ }
}
/**
* Updates the dvg structure when a serialization edge from src -> tgt is added.
*/
static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt) {
- int i;
+ int i, j, idx;
+ rss_edge_t *edge;
+ rss_edge_t **arr = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
+ /*
+ Add an edge from serialization target to serialization src:
+ src cannot be alive with target
+ */
add_dvg_edge(rss, dvg, tgt->irn, src->irn, 0);
+ /* Add edges to src's descendants as well, they also getting serialized. */
for (i = ARR_LEN_SAFE(src->descendants) - 1; i >= 0; --i) {
add_dvg_edge(rss, dvg, tgt->irn, src->descendants[i], 1);
}
+
+ /* We also have to add edges from targets predecessors in dvg */
+ idx = 0;
+ /* We cannot insert elements into set over which we iterate ... */
+ foreach_pset(dvg->edges, edge) {
+ if (edge->tgt == tgt->irn) {
+ arr[idx++] = edge;
+ }
+ }
+
+ for (i = 0; i < idx; ++i) {
+ edge = arr[i];
+ add_dvg_edge(rss, dvg, edge->src, src->irn, 1);
+ for (j = ARR_LEN_SAFE(src->descendants) - 1; j >= 0; --j) {
+ add_dvg_edge(rss, dvg, edge->src, src->descendants[j], 1);
+ }
+ }
}
#if 0
ir_node *irn;
rss_edge_t min_benefit_edge;
rss_edge_t min_omega20_edge;
- rss_irn_t *ser_u_omega1, *ser_v_omega1;
- rss_irn_t *ser_u_omega20, *ser_v_omega20;
+ rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
+ rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
DBG((rss->dbg, LEVEL_1, "\tcomputing admissible serializations:\n"));
ir_node *vv_irn = plist_element_get_value(el);
int add_edge;
- if (is_Sink(vv_irn))
+ if (is_Sink(vv_irn) || is_cfop(vv_irn))
continue;
if (is_pkiller)
arch_put_non_ignore_regs(rss->arch_env, rss->cls, arch_nonign_bs);
be_abi_put_ignore_regs(rss->abi, rss->cls, abi_ign_bs);
bitset_andnot(arch_nonign_bs, abi_ign_bs);
- available_regs = bitset_popcnt(arch_nonign_bs) - 1;
+ available_regs = bitset_popcnt(arch_nonign_bs);
+ //num_live = pset_count(rss->live_block);
+ //available_regs -= num_live < available_regs ? num_live : 0;
DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
rss->cls = cls;
DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
+ /* Get all live value at end of Block having current register class */
+ rss->live_block = pset_new_ptr(10);
+ be_liveness_end_of_block(rss->liveness, rss->arch_env, rss->cls, rss->block, rss->live_block);
+
/* reset the list of interesting nodes */
plist_clear(rss->nodes);
plist_insert_back(rss->nodes, _sink);
/* collect all nodes having a certain register class */
foreach_out_edge(block, edge) {
- ir_node *irn = get_edge_src_irn(edge);
+ ir_node *irn = get_edge_src_irn(edge);
+ ir_mode *mode = get_irn_mode(irn);
/*
We skip:
- Keeps (they are always immediately scheduled)
- Phi (same as Keep)
*/
- if (get_irn_mode(irn) == mode_T || be_is_Keep(irn) || is_Phi(irn))
+ if (mode == mode_T || mode == mode_X || is_Phi(irn))
continue;
/*
continue;
}
+ /* calculate the descendants and consumer for each node in the block */
+ collect_node_info(rss, skip_Proj(irn));
+
+ if (be_is_Keep(irn))
+ continue;
+
if (! arch_irn_is(rss->arch_env, irn, ignore) && arch_get_irn_reg_class(rss->arch_env, irn, -1) == cls) {
plist_insert_back(rss->nodes, skip_Proj(irn));
-
- /* calculate the descendants and consumer for each node in the block */
- collect_node_info(rss, skip_Proj(irn));
}
+ //}
}
/* compute the potential killing set PK(G) */
add the necessary dependencies to the irg.
*/
perform_value_serialization_heuristic(rss);
+
+ del_pset(rss->live_block);
}
phase_free(&rss->ph);
}
-#ifdef WITH_LIBCORE
/**
* Register the options.
*/
-void rss_register_options(lc_opt_entry_t *grp) {
- static int run_once = 0;
- lc_opt_entry_t *rss_grp;
+void be_init_schedrss(void) {
+ lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+ lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "sched");
+ lc_opt_entry_t *rss_grp = lc_opt_get_grp(sched_grp, "rss");
- if (! run_once) {
- run_once = 1;
- rss_grp = lc_opt_get_grp(grp, "rss");
-
- lc_opt_add_table(rss_grp, rss_option_table);
- }
+ lc_opt_add_table(rss_grp, rss_option_table);
}
-#endif /* WITH_LIBCORE */
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
/**
* Preprocess the irg for scheduling.
rss.h = heights_new(birg->irg);
rss.nodes = plist_new();
rss.opts = &rss_options;
+ rss.liveness = be_liveness(birg->irg);
irg_block_walk_graph(birg->irg, NULL, process_block, &rss);
heights_free(rss.h);
plist_free(rss.nodes);
+ be_liveness_free(rss.liveness);
if (birg->main_env->options->dump_flags & DUMP_SCHED)
be_dump(rss.irg, "-rss", dump_ir_block_graph);
projects / libfirm / blobdiff