*/
#include "config.h"
+#include "be_t.h"
#include "bitset.h"
+#include "error.h"
#include "raw_bitset.h"
#include "pdeq.h"
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
typedef struct local_env_t {
- int first_x_var;
- int last_x_var;
- unsigned n_colors;
- unsigned *normal_colors;
+ int first_x_var;
+ int last_x_var;
+ const unsigned *allocatable_colors;
} local_env_t;
+static unsigned check_alignment_constraints(ir_node *node)
+{
+ const arch_register_req_t *req = arch_get_irn_register_req(node);
+ // For larger than 1 variables, support only aligned constraints
+ assert((arch_register_req_is(req, aligned) || req->width == 1) && "Unaligned large (width > 1) variables not supported");
+ return arch_register_req_is(req, aligned) && req->width > 1;
+}
+
static void make_color_var_name(char *buf, size_t buf_size,
const ir_node *node, unsigned color)
{
static void build_coloring_cstr(ilp_env_t *ienv)
{
- local_env_t *lenv = ienv->env;
- be_ifg_t *ifg = ienv->co->cenv->ifg;
- unsigned n_regs = arch_register_class_n_regs(ienv->co->cls);
- nodes_iter_t iter;
- unsigned *colors;
- ir_node *irn;
- char buf[32];
-
- rbitset_alloca(colors, n_regs);
-
+ local_env_t *lenv = (local_env_t*)ienv->env;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ unsigned n_regs = arch_register_class_n_regs(ienv->co->cls);
+ const unsigned *allocatable_colors = lenv->allocatable_colors;
+ nodes_iter_t iter;
+ ir_node *irn;
+ char buf[32];
+
+ unsigned *const colors = rbitset_alloca(n_regs);
be_ifg_foreach_node(ifg, &iter, irn) {
const arch_register_req_t *req;
unsigned col;
int cst_idx;
unsigned curr_node_color;
+ unsigned has_alignment_cstr;
if (sr_is_removed(ienv->sr, irn))
continue;
+ has_alignment_cstr = check_alignment_constraints(irn);
+
req = arch_get_irn_register_req(irn);
/* get assignable colors */
if (arch_register_req_is(req, limited)) {
rbitset_copy(colors, req->limited, n_regs);
} else {
- rbitset_copy(colors, lenv->normal_colors, n_regs);
+ rbitset_copy(colors, allocatable_colors, n_regs);
}
/* add the coloring constraint */
for (col = 0; col < n_regs; ++col) {
int var_idx;
double val;
- if (!rbitset_is_set(colors, col))
+ if (!rbitset_is_set(colors, col)
+ || (has_alignment_cstr && ((col % req->width) != 0)))
continue;
make_color_var_name(buf, sizeof(buf), irn, col);
for (col = 0; col < n_regs; ++col) {
int cst_idx;
int var_idx;
- if (rbitset_is_set(colors, col))
+ if (rbitset_is_set(colors, col)
+ // for aligned variable, we set the unaligned part to 0
+ && (!has_alignment_cstr || ((col % req->width) == 0)))
continue;
make_color_var_name(buf, sizeof(buf), irn, col);
static void build_interference_cstr(ilp_env_t *ienv)
{
- lpp_t *lpp = ienv->lp;
- local_env_t *lenv = ienv->env;
- be_ifg_t *ifg = ienv->co->cenv->ifg;
- unsigned n_colors = lenv->n_colors;
- ir_node **clique = ALLOCAN(ir_node*, n_colors);
+ lpp_t *lpp = ienv->lp;
+ local_env_t *lenv = (local_env_t*)ienv->env;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ unsigned n_colors = arch_register_class_n_regs(ienv->co->cls);
+ ir_node **clique = ALLOCAN(ir_node*, n_colors);
+ const unsigned *allocatable_colors = lenv->allocatable_colors;
cliques_iter_t iter;
int size;
unsigned col;
/* for all colors */
for (col=0; col<n_colors; ++col) {
- int cst_idx = lpp_add_cst(lpp, NULL, lpp_less_equal, 1.0);
+ int cst_idx;
+ if (!rbitset_is_set(allocatable_colors, col))
+ continue;
+
+ cst_idx = lpp_add_cst(lpp, NULL, lpp_less_equal, 1.0);
/* for each member of this clique */
for (i=0; i<size; ++i) {
ir_node *irn = clique[i];
char buf[32];
int var_idx;
+ unsigned aligment_offset = 0;
if (sr_is_removed(ienv->sr, irn))
continue;
- make_color_var_name(buf, sizeof(buf), irn, col);
+ // Use the first part of the large registers for all
+ // interference, since it is the only colorable one.
+ if (check_alignment_constraints(irn)) {
+ const arch_register_req_t *req
+ = arch_get_irn_register_req(irn);
+ aligment_offset = col % req->width;
+ }
+
+ make_color_var_name(buf, sizeof(buf), irn,
+ col - aligment_offset);
var_idx = lpp_get_var_idx(lpp, buf);
lpp_set_factor_fast(lpp, cst_idx, var_idx, 1);
}
*/
static void build_affinity_cstr(ilp_env_t *ienv)
{
- local_env_t *lenv = ienv->env;
- unsigned n_colors = lenv->n_colors;
- unit_t *curr;
+ unsigned n_colors = arch_register_class_n_regs(ienv->co->cls);
/* for all optimization units */
list_for_each_entry(unit_t, curr, &ienv->co->units, units) {
static int compare_edge_t(const void *k1, const void *k2, size_t size)
{
- const edge_t *e1 = k1;
- const edge_t *e2 = k2;
+ const edge_t *e1 = (const edge_t*)k1;
+ const edge_t *e2 = (const edge_t*)k2;
(void) size;
return ! (e1->n1 == e2->n1 && e1->n2 == e2->n2);
new_edge.n2 = n1;
}
(*counter)++;
- return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+ return set_insert(edge_t, edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
static inline edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2)
new_edge.n1 = n2;
new_edge.n2 = n1;
}
- return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+ return set_find(edge_t, edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, size_t *counter)
new_edge.n1 = n2;
new_edge.n2 = n1;
}
- e = set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+ e = set_find(edge_t, edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
if (e) {
e->n1 = NULL;
e->n2 = NULL;
}
}
-#define pset_foreach(pset, irn) for (irn=pset_first(pset); irn; irn=pset_next(pset))
+#define pset_foreach(pset, irn) foreach_pset((pset), ir_node, (irn))
/**
* Search for an interference clique and an external node
*/
static void build_clique_star_cstr(ilp_env_t *ienv)
{
- affinity_node_t *aff;
-
/* for each node with affinity edges */
co_gs_foreach_aff_node(ienv->co, aff) {
struct obstack ob;
- neighb_t *nbr;
const ir_node *center = aff->irn;
ir_node **nodes;
set *edges;
++n_nodes;
}
}
- nodes = obstack_finish(&ob);
+ nodes = (ir_node**)obstack_finish(&ob);
/* get all interference edges between these */
n_edges = 0;
bool growed;
/* get 2 starting nodes to form a clique */
- for (e=set_first(edges); !e->n1; e=set_next(edges)) {
- }
+ for (e = set_first(edge_t, edges); !e->n1; e = set_next(edge_t, edges)) {}
/* we could be stepped out of the loop before the set iterated to the end */
set_break(edges);
/* search for a candidate to extend the clique */
for (i=0; i<n_nodes; ++i) {
ir_node *cand = nodes[i];
- ir_node *member;
bool is_cand;
/* if its already in the clique try the next */
/* now the clique is maximal. Finally add the constraint */
{
- ir_node *member;
- int var_idx;
- int cst_idx;
- char buf[32];
+ int var_idx;
+ int cst_idx;
+ char buf[32];
cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater_equal, pset_count(clique)-1);
int i, len;
ir_node **curr_path;
affinity_node_t *aff;
- neighb_t *nbr;
/* do not walk backwards or in circles */
if (pdeq_contains(path, irn))
}
/**
- * Search a path of affinity edges, whose ends are connected
- * by an interference edge and there are no other interference
- * edges in between.
- * Then at least one of these affinity edges must break.
+ * Search a path of affinity edges, whose ends are connected
+ * by an interference edge and there are no other interference
+ * edges in between.
+ * Then at least one of these affinity edges must break.
*/
static void build_path_cstr(ilp_env_t *ienv)
{
- affinity_node_t *aff_info;
-
/* for each node with affinity edges */
co_gs_foreach_aff_node(ienv->co, aff_info) {
pdeq *path = new_pdeq();
static void ilp2_apply(ilp_env_t *ienv)
{
- local_env_t *lenv = ienv->env;
+ local_env_t *lenv = (local_env_t*)ienv->env;
ir_graph *irg = ienv->co->irg;
/* first check if there was sth. to optimize */
my.last_x_var = -1;
FIRM_DBG_REGISTER(dbg, "firm.be.coilp2");
- rbitset_alloca(my.normal_colors, n_regs);
- be_set_allocatable_regs(co->irg, co->cls, my.normal_colors);
- my.n_colors = rbitset_popcount(my.normal_colors, n_regs);
+ unsigned *const allocatable_colors = rbitset_alloca(n_regs);
+ be_set_allocatable_regs(co->irg, co->cls, allocatable_colors);
+ my.allocatable_colors = allocatable_colors;
ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
projects / libfirm / blobdiff