#include <stdbool.h>
#include "be_t.h"
+#include "beintlive_t.h"
+#include "beirg.h"
#include "irtools.h"
#include "irprintf.h"
#include "lc_opts_enum.h"
#define DUMP_ILP 1
-#define DUMP_SOL 2
static int time_limit = 60;
static int solve_log = 0;
static unsigned dump_flags = 0;
static const lc_opt_enum_mask_items_t dump_items[] = {
- { "ilp", DUMP_ILP },
- { "sol", DUMP_SOL },
- { NULL, 0 }
+ { "ilp", DUMP_ILP },
+ { NULL, 0 }
};
static lc_opt_enum_mask_var_t dump_var = {
*****************************************************************************/
-size_red_t *new_size_red(copy_opt_t *co)
+/**
+ * Checks if a node is simplicial in the graph heeding the already removed nodes.
+ */
+static inline bool sr_is_simplicial(ilp_env_t *const ienv, ir_node const *const ifn)
{
- size_red_t *res = XMALLOC(size_red_t);
+ bool res = true;
+ ir_node **all = NEW_ARR_F(ir_node*, 0);
+ be_lv_t *const lv = be_get_irg_liveness(ienv->co->irg);
+ neighbours_iter_t iter;
+ be_ifg_foreach_neighbour(ienv->co->cenv->ifg, &iter, ifn, curr) {
+ /* Only consider non-removed neighbours. */
+ if (sr_is_removed(ienv, curr))
+ continue;
+
+ /* Check whether the current node forms a clique with all previous nodes. */
+ for (size_t i = ARR_LEN(all); i-- != 0;) {
+ if (!be_values_interfere(lv, curr, all[i])) {
+ res = false;
+ goto end;
+ }
+ }
- res->co = co;
- res->all_removed = pset_new_ptr_default();
- res->col_suff = NULL;
- obstack_init(&res->ob);
+ ARR_APP1(ir_node*, all, curr);
+ }
+end:
+ DEL_ARR_F(all);
return res;
}
/**
- * Checks if a node is simplicial in the graph heeding the already removed nodes.
+ * Virtually remove all nodes not related to the problem
+ * (simplicial AND not adjacent to a equal-color-edge)
*/
-static inline bool sr_is_simplicial(size_red_t *sr, const ir_node *ifn)
-{
- be_ifg_t *ifg = sr->co->cenv->ifg;
- neighbours_iter_t iter;
- ir_node **all = ALLOCAN(ir_node*, be_ifg_degree(ifg, ifn));
- int size = 0;
- int i;
- int o;
-
- /* get all non-removed neighbors */
- be_ifg_foreach_neighbour(ifg, &iter, ifn, curr)
- if (!sr_is_removed(sr, curr))
- all[size++] = curr;
-
- /* check if these form a clique */
- for (i=0; i<size; ++i)
- for (o=i+1; o<size; ++o)
- if (!be_ifg_connected(ifg, all[i], all[o]))
- return false;
-
- /* all edges exist so this is a clique */
- return true;
-}
-
-void sr_remove(size_red_t *sr)
+static void sr_remove(ilp_env_t *const ienv)
{
bool redo = true;
- const be_ifg_t *ifg = sr->co->cenv->ifg;
+ const be_ifg_t *ifg = ienv->co->cenv->ifg;
while (redo) {
redo = false;
be_ifg_foreach_node(ifg, irn) {
const arch_register_req_t *req = arch_get_irn_register_req(irn);
- coloring_suffix_t *cs;
-
- if (arch_register_req_is(req, limited) || sr_is_removed(sr, irn))
+ if (arch_register_req_is(req, limited) || sr_is_removed(ienv, irn))
continue;
- if (co_gs_is_optimizable(sr->co, irn))
+ if (co_gs_is_optimizable(ienv->co, irn))
continue;
- if (!sr_is_simplicial(sr, irn))
+ if (!sr_is_simplicial(ienv, irn))
continue;
- cs = OALLOC(&sr->ob, coloring_suffix_t);
- cs->irn = irn;
- cs->next = sr->col_suff;
- sr->col_suff = cs;
-
- pset_insert_ptr(sr->all_removed, irn);
+ ARR_APP1(ir_node*, ienv->col_suff, irn);
+ ir_nodeset_insert(&ienv->all_removed, irn);
redo = true;
}
}
}
-void sr_reinsert(size_red_t *sr)
+/**
+ * Virtually reinsert the nodes removed before and color them
+ */
+static void sr_reinsert(ilp_env_t *const ienv)
{
- coloring_suffix_t *cs;
- ir_graph *irg = sr->co->irg;
- be_ifg_t *ifg = sr->co->cenv->ifg;
- unsigned n_regs = arch_register_class_n_regs(sr->co->cls);
+ ir_graph *irg = ienv->co->irg;
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ unsigned n_regs = arch_register_class_n_regs(ienv->co->cls);
unsigned *const allocatable_cols = rbitset_alloca(n_regs);
- be_set_allocatable_regs(irg, sr->co->cls, allocatable_cols);
+ be_set_allocatable_regs(irg, ienv->co->cls, allocatable_cols);
unsigned *const possible_cols = rbitset_alloca(n_regs);
neighbours_iter_t iter;
/* color the removed nodes in right order */
- for (cs = sr->col_suff; cs; cs = cs->next) {
- unsigned free_col;
- ir_node *irn = cs->irn;
+ for (size_t i = ARR_LEN(ienv->col_suff); i-- != 0;) {
+ ir_node *const irn = ienv->col_suff[i];
rbitset_copy(possible_cols, allocatable_cols, n_regs);
unsigned cur_col;
/* only inspect nodes which are in graph right now */
- if (sr_is_removed(sr, other))
+ if (sr_is_removed(ienv, other))
continue;
cur_req = arch_get_irn_register_req(other);
/* now all bits not set are possible colors */
/* take one that matches the alignment constraint */
- free_col = 0;
+ unsigned free_col;
assert(!rbitset_is_empty(possible_cols, n_regs) && "No free color found. This can not be.");
- while (true) {
+ for (;;) {
free_col = (unsigned)rbitset_next(possible_cols, free_col, true);
if (free_col % arch_get_irn_register_req(irn)->width == 0)
break;
++free_col;
assert(free_col < n_regs);
}
- set_irn_col(sr->co->cls, irn, free_col);
- pset_remove_ptr(sr->all_removed, irn); /* irn is back in graph again */
+ set_irn_col(ienv->co->cls, irn, free_col);
+ ir_nodeset_remove(&ienv->all_removed, irn); /* irn is back in graph again */
}
}
-void free_size_red(size_red_t *sr)
-{
- del_pset(sr->all_removed);
- obstack_free(&sr->ob, NULL);
- free(sr);
-}
-
/******************************************************************************
_____ _ _____ _ _____
/ ____| (_) |_ _| | | __ \
res->build = build;
res->apply = apply;
res->env = env;
- res->sr = new_size_red(co);
+ res->col_suff = NEW_ARR_F(ir_node*, 0);
+ ir_nodeset_init(&res->all_removed);
return res;
}
{
ir_graph *irg = ienv->co->irg;
- sr_remove(ienv->sr);
+ sr_remove(ienv);
ienv->build(ienv);
ienv->apply(ienv);
- sr_reinsert(ienv->sr);
+ sr_reinsert(ienv);
return lpp_get_sol_state(ienv->lp);
}
void free_ilp_env(ilp_env_t *ienv)
{
- free_size_red(ienv->sr);
+ ir_nodeset_destroy(&ienv->all_removed);
+ DEL_ARR_F(ienv->col_suff);
lpp_free(ienv->lp);
free(ienv);
}
projects / libfirm / blobdiff