/*
- * Copyright (C) 1995-2011 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
#include <stdlib.h>
#include <limits.h>
+#include "beintlive_t.h"
+#include "beirg.h"
#include "list.h"
#include "pdeq.h"
#include "bitset.h"
#include "util.h"
#include "irtools.h"
#include "irnodemap.h"
-
+#include "be_t.h"
#include "bemodule.h"
#include "beabi.h"
#include "benode.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
-#include "beirg.h"
#define DUMP_BEFORE 1
#define DUMP_AFTER 2
} col_cost_pair_t;
typedef struct {
- ir_nodemap map;
- struct obstack obst;
- copy_opt_t *co;
- bitset_t *allocatable_regs;
- co2_irn_t *touched;
- int visited;
- int n_regs;
+ ir_nodemap map;
+ struct obstack obst;
+ copy_opt_t *co;
+ unsigned const *allocatable_regs;
+ co2_irn_t *touched;
+ int visited;
+ int n_regs;
struct list_head cloud_head;
DEBUG_ONLY(firm_dbg_module_t *dbg;)
} co2_t;
co2_irn_t *touched_next;
col_t tmp_col;
col_t orig_col;
- int last_color_change;
- bitset_t *adm_cache;
+ unsigned const *admissible;
unsigned fixed : 1;
unsigned tmp_fixed : 1;
- unsigned is_constrained : 1;
struct list_head changed_list;
};
int inevit;
int best_costs;
int n_memb;
- int n_constr;
- int max_degree;
int ticks;
double freedom;
co2_cloud_irn_t *master;
ci->irn = node;
ci->aff = NULL;
+ arch_register_req_t const *const req = arch_get_irn_register_req(node);
+ ci->admissible = arch_register_req_is(req, limited) ? req->limited : env->allocatable_regs;
+
ir_nodemap_insert(&env->map, node, ci);
}
return ci;
return ci->fixed || ci->tmp_fixed;
}
-static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
-{
- if (ci->adm_cache == NULL) {
- const arch_register_req_t *req;
- ci->adm_cache = bitset_obstack_alloc(&env->obst, env->n_regs);
- req = arch_get_irn_register_req(ci->irn);
-
- if (arch_register_req_is(req, limited)) {
- int i, n;
-
- n = env->n_regs;
- for (i = 0; i < n; ++i) {
- if (rbitset_is_set(req->limited, i))
- bitset_set(ci->adm_cache, i);
- }
- ci->is_constrained = 1;
- } else {
- bitset_copy(ci->adm_cache, env->allocatable_regs);
- }
- }
-
- return ci->adm_cache;
-}
-
-static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
-{
- bitset_copy(bs, get_adm(env, ci));
- return bs;
-}
-
-static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
-{
- bitset_t *bs = get_adm(env, ci);
- return bitset_is_set(bs, col);
-}
-
-static inline int is_constrained(co2_t *env, co2_irn_t *ci)
+static inline int is_color_admissible(co2_irn_t *const ci, col_t const col)
{
- if (!ci->adm_cache)
- get_adm(env, ci);
- return ci->is_constrained;
+ unsigned const *const bs = ci->admissible;
+ return rbitset_is_set(bs, col);
}
-static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
+static void incur_constraint_costs(ir_node const *const irn, col_cost_pair_t *const col_costs, int const costs)
{
const arch_register_req_t *req = arch_get_irn_register_req(irn);
if (arch_register_req_is(req, limited)) {
- unsigned n_regs = env->co->cls->n_regs;
- unsigned n_constr = 0;
- unsigned i;
-
- n_constr = rbitset_popcount(req->limited, n_regs);
- for (i = 0; i < n_regs; ++i) {
+ unsigned const n_regs = req->cls->n_regs;
+ unsigned const n_constr = rbitset_popcount(req->limited, n_regs);
+ for (unsigned i = 0; i < n_regs; ++i) {
if (rbitset_is_set(req->limited, i)) {
col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
}
int n_regs = env->co->cls->n_regs;
affinity_node_t *a = ci->aff;
- const ir_node *pos;
neighbours_iter_t it;
int i;
- /* Put all forbidden colors into the aux bitset. */
- bitset_t *const admissible = bitset_alloca(n_regs);
- admissible_colors(env, ci, admissible);
-
for (i = 0; i < n_regs; ++i) {
col_costs[i].col = i;
col_costs[i].costs = 0;
col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
}
- incur_constraint_costs(env, n->irn, col_costs, -n->costs);
+ incur_constraint_costs(n->irn, col_costs, -n->costs);
}
}
col_costs[col].costs = INT_MAX;
}
else {
- incur_constraint_costs(env, pos, col_costs, INT_MAX);
+ incur_constraint_costs(pos, col_costs, INT_MAX);
col_costs[col].costs = add_saturated(col_costs[col].costs, 8 * be_ifg_degree(ifg, pos));
}
}
- be_ifg_neighbours_break(&it);
/* Set the costs to infinity for each color which is not allowed at this node. */
- bitset_foreach_clear(admissible, elm) {
+ unsigned const *const admissible = ci->admissible;
+ rbitset_foreach_clear(admissible, n_regs, elm) {
col_costs[elm].costs = INT_MAX;
}
-
}
static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pair_t *seq)
}
(void) ci;
- assert(is_color_admissible(env, ci, col));
+ assert(is_color_admissible(ci, col));
seq[col].col = 0;
seq[0].col = col;
seq[0].costs = 0;
int neigh_ok = 1;
struct list_head changed;
- const ir_node *n;
neighbours_iter_t it;
DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
INIT_LIST_HEAD(&tmp);
neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
list_splice(&tmp, &changed);
- if (!neigh_ok)
+ if (!neigh_ok) {
+ be_ifg_neighbours_break(&it);
break;
+ }
}
}
- be_ifg_neighbours_break(&it);
/*
We managed to assign the target color to all neighbors, so from the perspective
goto end;
}
- if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
+ if (!color_is_fix(env, irn) && is_color_admissible(ci, tgt_col)) {
int n_regs = env->co->cls->n_regs;
col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
*/
static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
{
- co2_t *env = ci->cloud->env;
- co2_irn_t *ir = &ci->inh;
- int n_regs = env->n_regs;
- be_ifg_t *ifg = env->co->cenv->ifg;
- bitset_t *bs = bitset_alloca(n_regs);
+ co2_t *const env = ci->cloud->env;
+ size_t const n_regs = env->n_regs;
- const ir_node *irn;
neighbours_iter_t it;
- admissible_colors(env, &ci->inh, bs);
- bitset_foreach_clear(bs, elm)
- badness[elm] = ci->costs;
+ {
+ unsigned const *const bs = ci->inh.admissible;
+ rbitset_foreach_clear(bs, n_regs, elm)
+ badness[elm] = ci->costs;
+ }
/* Use constrained/fixed interfering neighbors to influence the color badness */
- be_ifg_foreach_neighbour(ifg, &it, ir->irn, irn) {
+ be_ifg_foreach_neighbour(env->co->cenv->ifg, &it, ci->inh.irn, irn) {
co2_irn_t *ni = get_co2_irn(env, irn);
- admissible_colors(env, ni, bs);
- if (bitset_popcount(bs) == 1) {
- size_t c = bitset_next_set(bs, 0);
+ unsigned const *const bs = ni->admissible;
+ if (rbitset_popcount(bs, n_regs) == 1) {
+ size_t const c = rbitset_next_max(bs, 0, n_regs, true);
badness[c] += ci->costs;
- }
-
- else if (ni->fixed) {
+ } else if (ni->fixed) {
col_t c = get_col(env, ni->irn);
badness[c] += ci->costs;
}
}
- be_ifg_neighbours_break(&it);
}
/**
int badness = ci->color_badness[i];
seq[i].col = i;
- seq[i].costs = is_color_admissible(env, &ci->inh, i) ? badness : INT_MAX;
+ seq[i].costs = is_color_admissible(&ci->inh, i) ? badness : INT_MAX;
min_badness = MIN(min_badness, badness);
}
/* If we are not the root and the parent's color is allowed for this node give it top prio. */
- if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
+ if (!is_root && is_color_admissible(&ci->inh, parent_col))
seq[parent_col].costs = min_badness - 1;
/* Sort the colors. The will be processed in that ordering. */
static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, int curr_costs)
{
- be_ifg_t *ifg = env->co->cenv->ifg;
co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
int costs = 0;
DB((env->dbg, LEVEL_2, "\t%+F\n", ci->inh.irn));
/* determine the nodes costs */
+ be_lv_t *const lv = be_get_irg_liveness(env->co->irg);
co_gs_foreach_neighb(a, n) {
costs += n->costs;
DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
- if (be_ifg_connected(ifg, a->irn, n->irn))
+ if (be_values_interfere(lv, a->irn, n->irn))
cloud->inevit += n->costs;
}
/* add the node's cost to the total costs of the cloud. */
- ci->costs = costs;
- cloud->costs += costs;
- cloud->n_constr += is_constrained(env, &ci->inh);
- cloud->freedom += bitset_popcount(get_adm(env, &ci->inh));
- cloud->max_degree = MAX(cloud->max_degree, ci->inh.aff->degree);
- cloud->n_memb++;
+ ci->costs = costs;
+ cloud->costs += costs;
+ cloud->freedom += rbitset_popcount(ci->inh.admissible, env->n_regs);
+ cloud->n_memb += 1;
/* If this is the heaviest node in the cloud, set it as the cloud's master. */
if (costs >= curr_costs) {
ir_nodemap_init(&env.map, co->irg);
obstack_init(&env.obst);
- env.touched = NULL;
- env.visited = 0;
- env.co = co;
- env.n_regs = co->cls->n_regs;
- env.allocatable_regs = bitset_alloca(co->cls->n_regs);
- be_put_allocatable_regs(co->cenv->irg, co->cls, env.allocatable_regs);
+ env.touched = NULL;
+ env.visited = 0;
+ env.co = co;
+ env.n_regs = co->cls->n_regs;
+ env.allocatable_regs = co->cenv->allocatable_regs->data;
FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
INIT_LIST_HEAD(&env.cloud_head);
projects / libfirm / blobdiff