+/*
+ * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
/**
+ * @file
+ * @brief Implementation of a register saturating list scheduler.
+ * @author Christian Wuerdig
+ * @date 29.08.2006
+ * @version $Id$
+ *
* Implementation of a register saturating list scheduler
* as described in: Sid-Ahmed-Ali Touati
* Register Saturation in Superscalar and VLIW Codes
- *
- * @license This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
- * @author Christian Wuerdig
- * @date 29.08.2006
- * @cvs-id $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <limits.h>
#include "bipartite.h"
#include "hungarian.h"
#include "plist.h"
+#include "array_t.h"
#include "height.h"
#include "bemodule.h"
#include "benode_t.h"
#include "besched_t.h"
+#include "beirg_t.h"
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
#define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
typedef struct _rss_irn {
plist_t *consumer_list; /**< List of consumers */
- ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
+ const ir_node **consumer; /**< Sorted consumer array (needed for faster access) */
plist_t *parent_list; /**< List of parents */
plist_t *pkiller_list; /**< List of potential killers */
plist_t *descendant_list; /**< List of descendants */
- ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
+ const ir_node **descendants; /**< Sorted descendant array (needed for faster access) */
- ir_node *killer; /**< The selected unique killer */
- ir_node *irn; /**< The corresponding firm node to this rss_irn */
+ const ir_node *killer; /**< The selected unique killer */
+ const ir_node *irn; /**< The corresponding firm node to this rss_irn */
chain_t *chain; /**< The chain, this node is associated to */
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 */
+ ir_nodeset_t 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;
static const lc_opt_table_entry_t rss_option_table[] = {
LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
- { NULL }
+ LC_OPT_LAST
};
/******************************************************************************
return -1;
}
-static 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);
- ir_node **arr = NEW_ARR_D(ir_node *, obst, len);
+ int i = 0;
+ int len = plist_count(irn_list);
+ const ir_node **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len);
/* copy the list into the array */
foreach_plist(irn_list, el) {
}
/* sort the array by node index */
- qsort(arr, len, sizeof(arr[0]), cmp_irn_idx);
+ /* HACK cast for MSVC */
+ qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx);
return arr;
}
}
/* Dumps the potential killing DAG (PKG) as vcg. */
-static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration) {
+static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration)
+{
FILE *f;
char file_name[256];
- char *suffix = alloca(32);
+ char suffix[32];
static const char suffix1[] = "-RSS-PKG.vcg";
static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
plist_element_t *el;
if (! max_ac) {
- snprintf(suffix, 32, "%s", suffix1);
+ snprintf(suffix, sizeof(suffix), "%s", suffix1);
}
else {
- snprintf(suffix, 32, "-%02d%s", iteration, suffix2);
+ snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2);
}
build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
/**
* In case there is no rss information for irn, initialize it.
*/
-static void *init_rss_irn(ir_phase *ph, ir_node *irn, void *old) {
+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]));
res->descendant_list = plist_obstack_new(phase_obst(ph));
ir_node *user = get_edge_src_irn(edge);
/* skip ignore nodes as they do not really contribute to register pressure */
- if (arch_irn_is(rss->arch_env, user, ignore))
+ if (arch_irn_is_ignore(user))
continue;
/*
}
if (is_Proj(user)) {
-
- //if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
+ //if (arch_get_irn_reg_class_out(user) == rss->cls)
collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
}
else {
assert(! is_Proj(consumer) && "Cannot handle Projs");
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)) {
+ if (!arch_irn_is_ignore(consumer) &&
+ !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_out(consumer) == rss->cls)
collect_consumer(rss, rss_irn, consumer, got_sink);
}
else
*/
static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
plist_t *list;
- ir_node **arr;
+ 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));
/**
* 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) {
+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;
if (! have_source)
- ir_nodeset_insert(&dvg->nodes, src);
+ ir_nodeset_insert(&dvg->nodes, (ir_node *) src);
else
assert(ir_nodeset_contains(&dvg->nodes, src) && "Wrong assumption");
- ir_nodeset_insert(&dvg->nodes, tgt);
+ ir_nodeset_insert(&dvg->nodes, (ir_node *) tgt);
- key.src = tgt;
- key.tgt = src;
+ key.src = (ir_node *) tgt;
+ key.tgt = (ir_node *) src;
assert(pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key)) == NULL && "DVG must be acyclic!");
- key.src = src;
- key.tgt = tgt;
+ key.src = (ir_node *) src;
+ key.tgt = (ir_node *) 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->src = (ir_node *) src;
+ dvg_edge->tgt = (ir_node *) tgt;
dvg_edge->next = NULL;
DBG((rss->dbg, LEVEL_3, "\t\tadd edge %+F -> %+F\n", src, 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 = alloca(pset_count(dvg->edges) * sizeof(arr[0]));
+ rss_edge_t **arr = ALLOCAN(rss_edge_t*, pset_count(dvg->edges));
/*
Add an edge from serialization target to serialization src:
*/
static ir_nodeset_t *compute_maximal_antichain(rss_t *rss, dvg_t *dvg, int iteration) {
int n = ir_nodeset_size(&dvg->nodes);
- int *assignment = alloca(n * sizeof(assignment[0]));
- int *assignment_rev = alloca(n * sizeof(assignment_rev[0]));
- int *idx_map = alloca(n * sizeof(idx_map[0]));
+ int *assignment = ALLOCAN(int, n);
+ int *assignment_rev = ALLOCAN(int, n);
+ int *idx_map = ALLOCAN(int, n);
hungarian_problem_t *bp;
ir_nodeset_t *values, *temp;
ir_nodeset_iterator_t iter;
DBG((rss->dbg, LEVEL_3, "\t\t\t%3d -> %3d %3d -> %3d\n", i, assignment[i], i, assignment_rev[i]));
}
- values = xmalloc(sizeof(values[0]));
+ values = XMALLOC(ir_nodeset_t);
ir_nodeset_init_size(values, 10);
cur_chain = 0;
/* Construction of the minimal chain partition */
free(temp);
}
- temp = xmalloc(sizeof(temp[0]));
+ temp = XMALLOC(ir_nodeset_t);
ir_nodeset_init_size(temp, 10);
/* Select all nodes from current value set, having another node in the set as descendant. */
if (pset_find(dvg->edges, &key, HASH_RSS_EDGE(&key))) {
/* v[j] is descendant of u -> remove u and break */
- ir_nodeset_insert(temp, u->irn);
+ ir_nodeset_insert(temp, (ir_node *) u->irn);
ir_nodeset_remove(values, u->irn);
DBG((rss->dbg, LEVEL_3, "\t\t\tremoving %+F from values, adding it to temp\n", u->irn));
int n = ir_nodeset_size(sat_vals);
int n_idx = ARR_LEN_SAFE(rss->idx_map);
int i = 0;
- ir_node **val_arr = alloca(n * sizeof(val_arr[0]));
+ ir_node **val_arr = ALLOCAN(ir_node*, n);
bitset_t *bs_sv = bitset_alloca(n_idx);
bitset_t *bs_vdesc = bitset_alloca(n_idx);
bitset_t *bs_tmp = bitset_alloca(n_idx);
int j, k;
ir_node *irn;
ir_nodeset_iterator_t iter;
- rss_edge_t min_benefit_edge;
- rss_edge_t min_omega20_edge;
+ rss_edge_t min_benefit_edge = {NULL, NULL, NULL};
+ rss_edge_t min_omega20_edge = {NULL, NULL, NULL};
rss_irn_t *ser_u_omega1 = NULL, *ser_v_omega1 = NULL;
rss_irn_t *ser_u_omega20 = NULL, *ser_v_omega20 = NULL;
/* v cannot be serialized with itself
* ignore nodes where serialization does not help */
if (i == j || IS_UNSERIALIZABLE_NODE(v)) {
+#ifdef DEBUG_libfirm
if (i != j)
DBG((rss->dbg, LEVEL_3, "\t\t\t%+F considered unserializable\n", v->irn));
+#endif
continue;
}
*/
if (add_edge) {
- int vv_height = get_irn_height(rss->h, vv_irn);
- int mu1, mu2, critical_path_cost;
+ unsigned vv_height = get_irn_height(rss->h, vv_irn);
+ unsigned critical_path_cost;
+ unsigned mu1, mu2;
/*
mu1 = | descendants(v) cut sat_vals |
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));
- int available_regs, iteration;
+ 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->arch_env, rss->cls, arch_nonign_bs);
+ 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);
int i, n;
const ir_edge_t *edge;
- phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn);
+ phase_init(&rss->ph, "rss block preprocessor", rss->irg, PHASE_DEFAULT_GROWTH, init_rss_irn, NULL);
DBG((rss->dbg, LEVEL_1, "preprocessing block %+F\n", block));
rss->block = block;
rss->max_height = heights_recompute_block(rss->h, block);
/* loop over all register classes */
- for (i = arch_isa_get_n_reg_class(rss->arch_env->isa) - 1; i >= 0; --i) {
- const arch_register_class_t *cls = arch_isa_get_reg_class(rss->arch_env->isa, i);
+ 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);
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);
+ ir_nodeset_init(&rss->live_block);
+ be_liveness_end_of_block(rss->liveness, rss->cls, rss->block, &rss->live_block);
/* reset the list of interesting nodes */
plist_clear(rss->nodes);
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) {
+ if (!arch_irn_is_ignore(irn) &&
+ arch_get_irn_reg_class_out(irn) == cls) {
plist_insert_back(rss->nodes, skip_Proj(irn));
}
//}
*/
perform_value_serialization_heuristic(rss);
- del_pset(rss->live_block);
+ ir_nodeset_destroy(&rss->live_block);
}
phase_free(&rss->ph);
/**
* Preprocess the irg for scheduling.
*/
-void rss_schedule_preparation(const be_irg_t *birg) {
+void rss_schedule_preparation(be_irg_t *birg) {
+ ir_graph *irg = be_get_birg_irg(birg);
rss_t rss;
FIRM_DBG_REGISTER(rss.dbg, "firm.be.sched.rss");
//firm_dbg_set_mask(rss.dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
- init_rss_special_nodes(birg->irg);
+ init_rss_special_nodes(irg);
- rss.irg = birg->irg;
- rss.arch_env = birg->main_env->arch_env;
+ rss.irg = irg;
+ rss.arch_env = be_get_birg_arch_env(birg);
rss.abi = birg->abi;
- rss.h = heights_new(birg->irg);
+ rss.h = heights_new(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);
+ rss.liveness = be_liveness(irg);
+ be_liveness_assure_sets(rss.liveness);
+ irg_block_walk_graph(irg, NULL, process_block, &rss);
heights_free(rss.h);
plist_free(rss.nodes);
be_liveness_free(rss.liveness);
projects / libfirm / blobdiff