*/
#include "config.h"
+#include "beschedrss.h"
+
#include <limits.h>
#include "obst.h"
#include "plist.h"
#include "array_t.h"
-#include "height.h"
+#include "heights.h"
#include "beabi.h"
#include "bemodule.h"
#define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
/* the rss options */
-typedef struct _rss_opts_t {
+typedef struct rss_opts_t {
int dump_flags;
} rss_opts_t;
/* Represents a child with associated costs */
-typedef struct _child {
+typedef struct child {
ir_node *irn;
float cost;
} child_t;
/* We need edges for several purposes. */
-typedef struct _rss_edge {
+typedef struct rss_edge {
ir_node *src;
ir_node *tgt;
void *next;
} rss_edge_t;
/* Represents a connected bipartite component. */
-typedef struct _cbc {
+typedef struct cbc {
ir_nodeset_t parents; /**< = S a set of value producers */
ir_nodeset_t children; /**< = T a set of value consumers */
pset *kill_edges; /**< = E a set of edges (t in T, s in S) such as each s in S gets killed by at least one t in T */
} cbc_t;
/* Represents a disjoint value DAG. */
-typedef struct _dvg {
+typedef struct dvg {
ir_nodeset_t nodes;
pset *edges;
} dvg_t;
/* Represents a chain of nodes. */
-typedef struct _chain {
+typedef struct chain {
plist_t *elements; /**< List of chain elements */
int nr; /**< a deterministic index for set insertion (used as hash) */
} chain_t;
-typedef struct _rss_irn {
+typedef struct rss_irn {
plist_t *consumer_list; /**< List of consumers */
const ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
} rss_irn_t;
/* Represents a serialization edge with associated costs. */
-typedef struct _serialization {
+typedef struct serialization {
rss_irn_t *u; /* the top node */
rss_irn_t *v; /* the node about to be serialized after u */
rss_edge_t *edge; /* the edge selected for the serialization */
int new_killer;
} serialization_t;
-typedef struct _rss {
+typedef struct rss {
ir_phase ph; /**< Phase to hold some data */
- heights_t *h; /**< The current height object */
+ ir_heights_t *h; /**< The current height object */
ir_graph *irg; /**< The irg to preprocess */
plist_t *nodes; /**< The list of interesting nodes */
const arch_env_t *arch_env; /**< The architecture environment */
DEBUG_ONLY(firm_dbg_module_t *dbg);
} rss_t;
-#define get_rss_irn(rss, irn) (phase_get_or_set_irn_data(&rss->ph, irn))
+static inline rss_irn_t *get_rss_irn(rss_t *env, const ir_node *node)
+{
+ return (rss_irn_t*)phase_get_or_set_irn_data(&env->ph, node);
+}
/**
* We need some special nodes:
/**
* Acquire opcodes if needed and create source and sink nodes.
*/
-static void init_rss_special_nodes(ir_graph *irg) {
+static void init_rss_special_nodes(ir_graph *irg)
+{
ir_node *block;
if (op_rss_Source == 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) {
- const int *i1 = a;
- const int *i2 = b;
+static int cmp_int(const void *a, const void *b)
+{
+ const int *i1 = (const int*)a;
+ const int *i2 = (const int*)b;
return QSORT_CMP(*i1, *i2);
}
-static int cmp_child_costs(const void *a, const void *b) {
- const child_t *c1 = a;
- const child_t *c2 = b;
+static int cmp_child_costs(const void *a, const void *b)
+{
+ const child_t *c1 = (const child_t*)a;
+ const child_t *c2 = (const child_t*)b;
return QSORT_CMP(c1->cost, c2->cost);
}
-static int cmp_irn_idx(const void *a, const void *b) {
+static int cmp_irn_idx(const void *a, const void *b)
+{
const ir_node *n1 = *(ir_node **)a;
const ir_node *n2 = *(ir_node **)b;
return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
}
-static int cmp_rss_edges(const void *a, const void *b) {
- const rss_edge_t *e1 = a;
- const rss_edge_t *e2 = b;
+static int cmp_rss_edges(const void *a, const void *b)
+{
+ const rss_edge_t *e1 = (const rss_edge_t*)a;
+ const rss_edge_t *e2 = (const rss_edge_t*)b;
return (e1->src != e2->src) || (e1->tgt != e2->tgt);
}
-static int bsearch_for_index(int key, int *arr, size_t len, int force) {
+static int bsearch_for_index(int key, int *arr, size_t len, int force)
+{
int left = 0;
int right = len;
return -1;
}
-static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
+static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst)
+{
plist_element_t *el;
int i = 0;
int len = plist_count(irn_list);
/* copy the list into the array */
foreach_plist(irn_list, el) {
- arr[i++] = plist_element_get_value(el);
+ arr[i++] = (ir_node*)plist_element_get_value(el);
}
/* sort the array by node index */
*****************************************************/
#ifdef DEBUG_libfirm
-static void dump_nodeset(ir_nodeset_t *ns, const char *prefix) {
+static void dump_nodeset(ir_nodeset_t *ns, const char *prefix)
+{
ir_nodeset_iterator_t iter;
ir_node *irn;
ir_nodeset_iterator_init(&iter, ns);
- while( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
+ while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
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) {
+static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len)
+{
const char *irg_name;
memset(buf, 0, len);
}
/* Dumps all collected bipartite components of current irg as vcg. */
-static void debug_vcg_dump_bipartite(rss_t *rss) {
+static void debug_vcg_dump_bipartite(rss_t *rss)
+{
cbc_t *cbc;
FILE *f;
char file_name[256];
fprintf(f, "layoutalgorithm: mindepth\n");
fprintf(f, "manhattan_edges: yes\n\n");
- foreach_pset(rss->cbc_set, cbc) {
+ foreach_pset(rss->cbc_set, cbc_t*, cbc) {
ir_nodeset_iterator_t iter;
ir_node *n;
rss_edge_t *ke;
foreach_ir_nodeset(&cbc->children, n, iter) {
ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
}
- foreach_pset(cbc->kill_edges, ke) {
+ foreach_pset(cbc->kill_edges, rss_edge_t*, ke) {
ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
}
}
/* Dump the computed killing function as vcg. */
-static void debug_vcg_dump_kill(rss_t *rss) {
+static void debug_vcg_dump_kill(rss_t *rss)
+{
FILE *f;
char file_name[256];
plist_element_t *el;
/* dump all nodes and their killers */
foreach_plist(rss->nodes, el) {
- ir_node *irn = plist_element_get_value(el);
+ ir_node *irn = (ir_node *)plist_element_get_value(el);
rss_irn_t *rirn = get_rss_irn(rss, irn);
rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);
}
foreach_plist(rss->nodes, el) {
- ir_node *irn = plist_element_get_value(el);
- rss_irn_t *rirn = get_rss_irn(rss, irn);
- char *c1 = "";
+ ir_node *irn = (ir_node *)plist_element_get_value(el);
+ rss_irn_t *rirn = get_rss_irn(rss, irn);
+ const char *c1 = "";
plist_element_t *k_el;
/* dump selected saturating values in yellow */
}
foreach_plist(rirn->pkiller_list, k_el) {
- ir_node *pkiller = plist_element_get_value(k_el);
- rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
- char *c2 = "";
+ ir_node *pkiller = (ir_node *)plist_element_get_value(k_el);
+ rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
+ const char *c2 = "";
if (max_ac && ir_nodeset_contains(max_ac, pkiller))
c2 = "color:yellow";
}
/* Dumps the disjoint value DAG (DVG) as vcg. */
-static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
+static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg)
+{
static const char suffix[] = "-RSS-DVG.vcg";
FILE *f;
char file_name[256];
}
/* dump all edges */
- foreach_pset(dvg->edges, edge) {
+ foreach_pset(dvg->edges, rss_edge_t*, edge) {
ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
}
#if 0
/* Dumps the PKG(DVG). */
-static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
+static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg)
+{
static const char suffix[] = "-RSS-DVG-PKG.vcg";
FILE *f;
char file_name[256];
/**
* In case there is no rss information for irn, initialize it.
*/
-static void *init_rss_irn(ir_phase *ph, const ir_node *irn, void *old) {
- rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
+static void *init_rss_irn(ir_phase *ph, const ir_node *irn)
+{
+ rss_irn_t *res = (rss_irn_t*)phase_alloc(ph, sizeof(res[0]));
res->descendant_list = plist_obstack_new(phase_obst(ph));
res->descendants = NULL;
/**
* Collect all nodes data dependent on current node.
*/
-static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
+static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk)
+{
const ir_edge_t *edge;
rss_irn_t *cur_node = get_rss_irn(rss, irn);
ir_node *block = rss->block;
/**
* Handles a single consumer.
*/
-static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
+static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink)
+{
ir_node *block = rss->block;
assert(! is_Proj(consumer) && "Cannot handle Projs");
/**
* Collect all nodes consuming the value(s) produced by current node.
*/
-static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
+static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink)
+{
const ir_edge_t *edge;
int i;
ir_edge_kind_t ekind[2] = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
/**
* Collects all consumer and descendant of a irn.
*/
-static void collect_node_info(rss_t *rss, ir_node *irn) {
+static void collect_node_info(rss_t *rss, ir_node *irn)
+{
static unsigned cur_desc_walk = 0;
rss_irn_t *rss_irn = get_rss_irn(rss, irn);
int got_sink;
/* check if node info is already available */
if (rss_irn->handled)
return;
- //phase_reinit_single_irn_data(&rss->ph, irn);
DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
* @param u The potentially killed value
* @return 1 if v is in pkill(u), 0 otherwise
*/
-static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
+static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u)
+{
plist_t *list;
const ir_node **arr;
plist_element_t *el;
(void) rss;
- assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
- assert(is_Sink(u->irn) || ((plist_count(u->consumer_list) > 0 && u->consumer) || 1));
-
/* as we loop over the list: loop over the shorter one */
if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
list = u->consumer_list;
/* for each list element: try to find element in array */
foreach_plist(list, el) {
- ir_node *irn = plist_element_get_value(el);
- ir_node *match = BSEARCH_IRN_ARR(irn, arr);
+ ir_node *irn = (ir_node*)plist_element_get_value(el);
+ ir_node *match = (ir_node*)BSEARCH_IRN_ARR(irn, arr);
if (match && match != irn)
return 0;
/**
* Update descendants, consumer and pkiller list for the given irn.
*/
-static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
+static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn)
+{
rss_irn_t *node = get_rss_irn(rss, irn);
rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);
plist_insert_back(node->descendant_list, pk_irn);
foreach_plist(pkiller->descendant_list, el) {
- ir_node *desc = plist_element_get_value(el);
+ ir_node *desc = (ir_node*)plist_element_get_value(el);
if (! plist_has_value(node->descendant_list, desc))
plist_insert_back(node->descendant_list, desc);
/**
* Compute the potential killing set PK.
*/
-static void compute_pkill_set(rss_t *rss) {
+static void compute_pkill_set(rss_t *rss)
+{
plist_element_t *u_el, *v_el;
foreach_plist(rss->nodes, u_el) {
- ir_node *u_irn = plist_element_get_value(u_el);
+ ir_node *u_irn = (ir_node*)plist_element_get_value(u_el);
rss_irn_t *u = get_rss_irn(rss, u_irn);
DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
/* check each consumer if it is a potential killer */
foreach_plist(u->consumer_list, v_el) {
- ir_node *v_irn = plist_element_get_value(v_el);
+ ir_node *v_irn = (ir_node*)plist_element_get_value(v_el);
rss_irn_t *v = get_rss_irn(rss, v_irn);
/* check, if v is a potential killer of u */
/**
* Build set of killing edges (from values to their potential killers)
*/
-static void build_kill_edges(rss_t *rss, pset *epk) {
+static void build_kill_edges(rss_t *rss, pset *epk)
+{
plist_element_t *el, *k_el;
foreach_plist(rss->nodes, el) {
- ir_node *irn = plist_element_get_value(el);
+ ir_node *irn = (ir_node*)plist_element_get_value(el);
rss_irn_t *rirn = get_rss_irn(rss, irn);
DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));
foreach_plist(rirn->pkiller_list, k_el) {
- ir_node *pkiller = plist_element_get_value(k_el);
+ ir_node *pkiller = (ir_node*)plist_element_get_value(k_el);
rss_edge_t *ke = OALLOC(phase_obst(&rss->ph), rss_edge_t);
ke->src = irn;
#ifdef DEBUG_libfirm
/* print the given cbc for debugging purpose */
-static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
+static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc)
+{
ir_nodeset_iterator_t iter;
ir_node *n;
rss_edge_t *ke;
DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
}
DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
- foreach_pset(cbc->kill_edges, ke) {
+ foreach_pset(cbc->kill_edges, rss_edge_t*, ke) {
DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
}
}
* Sid-Ahmed-Ali Touati, Phd Thesis
* Register Pressure in Instruction Level Parallelism, p. 71
*/
-static void compute_bipartite_decomposition(rss_t *rss) {
+static void compute_bipartite_decomposition(rss_t *rss)
+{
pset *epk = new_pset(cmp_rss_edges, 10);
int cur_num = 0;
build_kill_edges(rss, epk);
foreach_plist(rss->nodes, el) {
- ir_node *u_irn = plist_element_get_value(el);
+ ir_node *u_irn = (ir_node*)plist_element_get_value(el);
rss_irn_t *u = get_rss_irn(rss, u_irn);
int p_change = 1;
int c_change = 1;
/* T_cb = PK_successors(u) */
ir_nodeset_init_size(&cbc->children, 5);
foreach_plist(u->pkiller_list, el2) {
- ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
+ ir_nodeset_insert(&cbc->children, (ir_node*)plist_element_get_value(el2));
DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
}
/* accumulate parents */
foreach_ir_nodeset(&cbc->children, t_irn, iter) {
- foreach_pset(epk, k_edge) {
+ foreach_pset(epk, rss_edge_t*, k_edge) {
ir_node *val = k_edge->src;
if (k_edge->tgt == t_irn && ! ir_nodeset_contains(&cbc->parents, val)) {
/* accumulate children */
foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
- foreach_pset(epk, k_edge) {
+ foreach_pset(epk, rss_edge_t*, k_edge) {
ir_node *val = k_edge->tgt;
if (k_edge->src == s_irn && ! ir_nodeset_contains(&cbc->children, val)) {
}
/* update edges */
- foreach_pset(epk, k_edge) {
+ foreach_pset(epk, rss_edge_t*, k_edge) {
if (ir_nodeset_contains(&cbc->parents, k_edge->src) &&
ir_nodeset_contains(&cbc->children, k_edge->tgt)) {
pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
}
/* remove all linked k_edges */
- for (; kedge_root; kedge_root = kedge_root->next) {
+ for (; kedge_root; kedge_root = (rss_edge_t*)kedge_root->next) {
pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
}
foreach_ir_nodeset(&cbc->parents, s_irn, iter) {
int is_killed = 0;
- foreach_pset(cbc->kill_edges, k_edge) {
+ foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
if (k_edge->src == s_irn) {
is_killed = 1;
pset_break(cbc->kill_edges);
/**
* Select the child with the maximum cost.
*/
-static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc) {
+static child_t *select_child_max_cost(rss_t *rss, ir_nodeset_t *x, ir_nodeset_t *y, child_t *t, cbc_t *cbc)
+{
ir_node *child;
ir_nodeset_iterator_t iter;
float max_cost = -1.0f;
float cost;
/* get the number of unkilled parents */
- foreach_pset(cbc->kill_edges, k_edge) {
+ foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
if (k_edge->tgt == child && ir_nodeset_contains(x, k_edge->src))
++num_unkilled_parents;
}
/**
* Remove all parents from x which are killed by t_irn.
*/
-static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc) {
+static void remove_covered_parents(rss_t *rss, ir_nodeset_t *x, ir_node *t_irn, cbc_t *cbc)
+{
rss_irn_t *t = get_rss_irn(rss, t_irn);
rss_edge_t *k_edge;
DBG((rss->dbg, LEVEL_2, "\t\tremoving parents covered by %+F:\n", t_irn));
- foreach_pset(cbc->kill_edges, k_edge) {
+ foreach_pset(cbc->kill_edges, rss_edge_t*, k_edge) {
if (k_edge->tgt == t_irn && ir_nodeset_contains(x, k_edge->src)) {
ir_nodeset_remove(x, k_edge->src);
plist_insert_back(t->parent_list, k_edge->src);
}
}
-static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn) {
+static void update_cumulated_descendent_values(rss_t *rss, ir_nodeset_t *y, ir_node *t_irn)
+{
rss_irn_t *t = get_rss_irn(rss, t_irn);
plist_element_t *el;
DBG((rss->dbg, LEVEL_2, "\t\tupdating cumulated descendant value of %+F:\n", t_irn));
foreach_plist(t->descendant_list, el) {
- ir_nodeset_insert(y, plist_element_get_value(el));
+ ir_nodeset_insert(y, (ir_node*)plist_element_get_value(el));
DBG((rss->dbg, LEVEL_3, "\t\t\t%+F\n", plist_element_get_value(el)));
}
}
/**
* Greedy-k: a heuristics for the MMA problem
*/
-static void compute_killing_function(rss_t *rss) {
+static void compute_killing_function(rss_t *rss)
+{
cbc_t *cbc;
struct obstack obst;
compute_bipartite_decomposition(rss);
/* for all bipartite components do: */
- foreach_pset(rss->cbc_set, cbc) {
+ foreach_pset(rss->cbc_set, cbc_t*, cbc) {
ir_node *p;
ir_nodeset_t x;
ir_nodeset_t y;
/* kill all unkilled parents of t */
foreach_plist(rt->parent_list, p_el) {
- ir_node *par = plist_element_get_value(p_el);
+ ir_node *par = (ir_node*)plist_element_get_value(p_el);
rss_irn_t *rpar = get_rss_irn(rss, par);
if (is_Sink(rpar->killer)) {
/**
* 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, const ir_node *src, const ir_node *tgt, int have_source) {
+static inline void add_dvg_edge(rss_t *rss, dvg_t *dvg, const ir_node *src, const ir_node *tgt, int have_source)
+{
rss_edge_t *dvg_edge;
rss_edge_t key;
* BEWARE: It is not made explicitly clear in the Touati paper,
* but the DVG is meant to be build from the KILLING DAG
*/
-static void compute_dvg(rss_t *rss, dvg_t *dvg) {
+static void compute_dvg(rss_t *rss, dvg_t *dvg)
+{
plist_element_t *el;
DBG((rss->dbg, LEVEL_1, "\tcomputing DVG:\n"));
foreach_plist(rss->nodes, el) {
- ir_node *u_irn = plist_element_get_value(el);
+ ir_node *u_irn = (ir_node*)plist_element_get_value(el);
rss_irn_t *u = get_rss_irn(rss, u_irn);
rss_irn_t *u_killer = get_rss_irn(rss, u->killer);
int i;
/**
* 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) {
+static void update_dvg(rss_t *rss, dvg_t *dvg, rss_irn_t *src, rss_irn_t *tgt)
+{
int i, j, idx;
rss_edge_t *edge;
rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges));
/* 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) {
+ foreach_pset(dvg->edges, rss_edge_t*, edge) {
if (edge->tgt == tgt->irn) {
arr[idx++] = edge;
}
/**
* Accumulate all descendants for root into list.
*/
-static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list) {
+static void accumulate_dvg_descendant_values(rss_t *rss, rss_irn_t *root, plist_t *list)
+{
if (plist_count(root->dvg_user_list) > 0) {
plist_element_t *el;
* in the given DVG.
* Needs the descendant list for all user as sorted array.
*/
-static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg) {
+static void build_dvg_pkiller_list(rss_t *rss, dvg_t *dvg)
+{
ir_nodeset_iterator_t iter;
ir_node *irn;
* This is a reimplementation of the MAXIMAL_ANTI_CHAIN function
* from the DDG library 1.1 (DAG.cpp).
*/
-static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
- int n = ir_nodeset_size(&dvg->nodes);
- int *assignment = ALLOCAN(int, n);
- int *assignment_rev = ALLOCAN(int, n);
+static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration)
+{
+ unsigned n = ir_nodeset_size(&dvg->nodes);
+ unsigned *assignment = ALLOCAN(unsigned, n);
+ unsigned *assignment_rev = ALLOCAN(unsigned, n);
int *idx_map = ALLOCAN(int, n);
hungarian_problem_t *bp;
ir_nodeset_t *values, *temp;
ir_nodeset_iterator_t iter;
ir_node *u_irn;
- int i, j, cost, cur_chain, res;
+ unsigned i, j;
+ unsigned cost;
+ int cur_chain, res;
rss_edge_t *dvg_edge;
#define MAP_IDX(irn) bsearch_for_index(get_irn_idx(irn), idx_map, n, 1)
}
qsort(idx_map, n, sizeof(idx_map[0]), cmp_int);
- foreach_pset(dvg->edges, dvg_edge) {
+ foreach_pset(dvg->edges, rss_edge_t*, dvg_edge) {
int idx_u = MAP_IDX(dvg_edge->src);
int idx_v = MAP_IDX(dvg_edge->tgt);
/* build the reverse assignment, ie. foreach i -> j, add j -> i */
for (i = 0; i < n; ++i) {
- if (assignment[i] >= 0) {
- int j = assignment[i];
+ if (assignment[i] != (unsigned)-1) {
+ unsigned j = assignment[i];
assignment_rev[j] = i;
}
}
- DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %d\n", cost));
- DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n", cost));
+ DBG((rss->dbg, LEVEL_2, "\t\tgot assignment with cost %u\n", cost));
+ DBG((rss->dbg, LEVEL_3, "\t\t\tassignment --- reverse assignment\n"));
for (i = 0; i < n; ++i) {
- DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
+ DBG((rss->dbg, LEVEL_3, "\t\t\t%3u -> %3u %3u -> %3u\n", i, assignment[i], i, assignment_rev[i]));
}
values = XMALLOC(ir_nodeset_t);
/* Construction of the minimal chain partition */
for (j = 0; j < n; ++j) {
/* check nodes, which did not occur as target */
- if (assignment_rev[j] == -1) {
+ if (assignment_rev[j] == (unsigned)-1) {
int xj = idx_map[j];
ir_node *xj_irn = get_idx_irn(rss->irg, xj);
rss_irn_t *xj_rss = get_rss_irn(rss, xj_irn);
chain_t *c = OALLOC(phase_obst(&rss->ph), chain_t);
- int source;
+ unsigned source;
/* there was no source for j -> we have a source of a new chain */
ir_nodeset_insert(values, xj_irn);
xj_rss->chain = c;
DBG((rss->dbg, LEVEL_2, "\t\tstarting chain %d:\n", c->nr));
- DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%d)", xj_irn, j));
+ DBG((rss->dbg, LEVEL_2, "\t\t\t%+F (%u)", xj_irn, j));
/* follow chain, having j as source */
source = j;
- while (assignment[source] >= 0) {
+ while (assignment[source] != (unsigned)-1) {
int target = assignment[source];
int irn_idx = idx_map[target];
ir_node *irn = get_idx_irn(rss->irg, irn_idx);
set at the same time. :-(((((
TODO Matze: now we can, so rewrite this...
*/
- int n = ir_nodeset_size(values);
- int i = 0;
+ unsigned n = ir_nodeset_size(values);
+ unsigned i = 0;
ir_node **val_arr = NEW_ARR_F(ir_node *, n);
foreach_ir_nodeset(values, u_irn, iter)
/* If u has predecessor in chain: insert the predecessor */
if (el == plist_element_get_prev(el)) {
- ir_nodeset_insert(values, plist_element_get_value(el));
+ ir_nodeset_insert(values, (ir_node*)plist_element_get_value(el));
DBG((rss->dbg, LEVEL_3, "\t\t\tadding %+F to values\n", plist_element_get_value(el)));
}
}
if (rss->opts->dump_flags & RSS_DUMP_MAXAC)
debug_vcg_dump_pkg(rss, values, iteration);
- if(temp != NULL) {
+ if (temp != NULL) {
ir_nodeset_destroy(temp);
free(temp);
}
/**
* Computes the best serialization between two nodes of sat_vals.
*/
-static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs) {
+static serialization_t *compute_best_admissible_serialization(rss_t *rss, ir_nodeset_t *sat_vals, serialization_t *ser, int num_regs)
+{
int n = ir_nodeset_size(sat_vals);
int n_idx = ARR_LEN_SAFE(rss->idx_map);
int i = 0;
/* accumulate all descendants of all pkiller(u) */
bitset_clear_all(bs_ukilldesc);
foreach_plist(u->pkiller_list, el) {
- ir_node *irn = plist_element_get_value(el);
+ ir_node *irn = (ir_node*)plist_element_get_value(el);
rss_irn_t *node = get_rss_irn(rss, irn);
if (! is_Sink(irn))
/* for all vv in pkiller(u) */
foreach_plist(u->pkiller_list, el) {
- ir_node *vv_irn = plist_element_get_value(el);
+ ir_node *vv_irn = (ir_node*)plist_element_get_value(el);
int add_edge;
if (is_Sink(vv_irn) || is_cfop(vv_irn))
be simultaneously alive with u
*/
bitset_copy(bs_tmp, bs_vdesc);
- mu1 = bitset_popcnt(bitset_and(bs_tmp, bs_sv));
+ bitset_and(bs_tmp, bs_sv);
+ mu1 = bitset_popcount(bs_tmp);
/*
mu2 = | accum_desc_all_pkiller(u) without descendants(v) |
*/
if (is_pkiller) {
bitset_copy(bs_tmp, bs_ukilldesc);
- mu2 = bitset_popcnt(bitset_andnot(bs_tmp, bs_vdesc));
+ bitset_andnot(bs_tmp, bs_vdesc);
+ mu2 = bitset_popcount(bs_tmp);
}
else {
mu2 = 0;
* Perform the value serialization heuristic and add all
* computed serialization edges as dependencies to the irg.
*/
-static void perform_value_serialization_heuristic(rss_t *rss) {
- bitset_t *arch_nonign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
- bitset_t *abi_ign_bs = bitset_alloca(arch_register_class_n_regs(rss->cls));
+static void perform_value_serialization_heuristic(rss_t *rss)
+{
unsigned available_regs, iteration;
dvg_t dvg;
ir_nodeset_t *sat_vals;
pset *ser_set = new_pset(cmp_rss_edges, 20);
- /* available_regs = R = |arch_non_ignore_regs cut ~abi_ignore_regs| */
- arch_put_non_ignore_regs(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);
- //num_live = pset_count(rss->live_block);
- //available_regs -= num_live < available_regs ? num_live : 0;
+ available_regs = be_get_n_allocatable_regs(rss->irg, rss->cls);
DBG((rss->dbg, LEVEL_1, "\n\t#available regs: %d\n\n", available_regs));
/* update the dvg */
update_dvg(rss, &dvg, ser->v, ser->u);
update_dvg(rss, &dvg, get_rss_irn(rss, ser->edge->src), get_rss_irn(rss, ser->edge->tgt));
- if(sat_vals != NULL) {
+ if (sat_vals != NULL) {
ir_nodeset_destroy(sat_vals);
free(sat_vals);
}
/**
* Do initial calculations for a block.
*/
-static void process_block(ir_node *block, void *env) {
- rss_t *rss = env;
+static void process_block(ir_node *block, void *env)
+{
+ rss_t *rss = (rss_t*)env;
int i, n;
const ir_edge_t *edge;
- phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
+ phase_init(&rss->ph, rss->irg, init_rss_irn);
DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
rss->block = block;
/* build an index map for all nodes in the current block */
i = 0;
n = get_irn_n_edges(block);
- NEW_ARR_A(int *, rss->idx_map, n);
+ NEW_ARR_A(int, rss->idx_map, n);
foreach_out_edge(block, edge) {
ir_node *irn = get_edge_src_irn(edge);
rss->idx_map[i++] = get_irn_idx(irn);
rss->max_height = heights_recompute_block(rss->h, block);
/* loop over all register classes */
- for (i = arch_env_get_n_reg_class(rss->arch_env) - 1; i >= 0; --i) {
- const arch_register_class_t *cls = arch_env_get_reg_class(rss->arch_env, i);
+ for (i = rss->arch_env->n_register_classes - 1; i >= 0; --i) {
+ const arch_register_class_t *cls = &rss->arch_env->register_classes[i];
rss->cls = cls;
DBG((rss->dbg, LEVEL_1, "register class %s\n", arch_register_class_name(cls)));
ir_nodeset_destroy(&rss->live_block);
}
- phase_free(&rss->ph);
+ phase_deinit(&rss->ph);
}
-/**
- * Register the options.
- */
-void be_init_schedrss(void) {
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
+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");
lc_opt_add_table(rss_grp, rss_option_table);
}
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_schedrss);
-
/**
* Preprocess the irg for scheduling.
*/
-void rss_schedule_preparation(be_irg_t *birg) {
- ir_graph *irg = be_get_birg_irg(birg);
+void rss_schedule_preparation(ir_graph *irg)
+{
rss_t rss;
FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
init_rss_special_nodes(irg);
rss.irg = irg;
- rss.arch_env = be_get_birg_arch_env(birg);
- rss.abi = birg->abi;
+ rss.arch_env = be_get_irg_arch_env(irg);
+ rss.abi = be_get_irg_abi(irg);
rss.h = heights_new(irg);
rss.nodes = plist_new();
rss.opts = &rss_options;
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);
+ if (be_get_irg_options(irg)->dump_flags & DUMP_SCHED)
+ dump_ir_graph(irg, "rss");
}
projects / libfirm / blobdiff