#include "unionfind.h"
#include "pdeq.h"
#include "hungarian.h"
-
+#include "statev.h"
#include "beabi.h"
#include "bechordal_t.h"
#include "be.h"
static int *congruence_classes;
static ir_node **block_order;
static size_t n_block_order;
-static int create_preferences = true;
-static int create_congruence_classes = true;
-static int propagate_phi_registers = true;
-
-static const lc_opt_table_entry_t options[] = {
- LC_OPT_ENT_BOOL("prefs", "use preference based coloring", &create_preferences),
- LC_OPT_ENT_BOOL("congruences", "create congruence classes", &create_congruence_classes),
- LC_OPT_ENT_BOOL("prop_phi", "propagate phi registers", &propagate_phi_registers),
- LC_OPT_LAST
-};
/** currently active assignments (while processing a basic block)
* maps registers to values(their current copies) */
* @param weight the weight
* @param node the current node
*/
-static void check_defs(const ir_nodeset_t *live_nodes, float weight,
- ir_node *node)
+static void check_defs(ir_nodeset_t const *const live_nodes, float const weight, ir_node *const node, arch_register_req_t const *const req)
{
- const arch_register_req_t *req = arch_get_irn_register_req(node);
- if (req->type & arch_register_req_type_limited) {
+ if (arch_register_req_is(req, limited)) {
const unsigned *limited = req->limited;
float penalty = weight * DEF_FACTOR;
give_penalties_for_limits(live_nodes, penalty, limited, node);
}
- if (req->type & arch_register_req_type_should_be_same) {
+ if (arch_register_req_is(req, should_be_same)) {
ir_node *insn = skip_Proj(node);
allocation_info_t *info = get_allocation_info(node);
int arity = get_irn_arity(insn);
if (is_Phi(node))
break;
- if (create_preferences) {
- ir_node *value;
- be_foreach_definition(node, cls, value,
- check_defs(&live_nodes, weight, value);
- );
- }
+ be_foreach_definition(node, cls, value, req,
+ check_defs(&live_nodes, weight, value, req);
+ );
/* mark last uses */
int arity = get_irn_arity(node);
be_liveness_transfer(cls, node, &live_nodes);
- if (create_preferences) {
- /* update weights based on usage constraints */
- for (int i = 0; i < arity; ++i) {
- ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
-
- const arch_register_req_t *req
- = arch_get_irn_register_req_in(node, i);
- if (!(req->type & arch_register_req_type_limited))
- continue;
+ /* update weights based on usage constraints */
+ be_foreach_use(node, cls, req, op, op_req,
+ if (!arch_register_req_is(req, limited))
+ continue;
- const unsigned *limited = req->limited;
- give_penalties_for_limits(&live_nodes, weight * USE_FACTOR,
- limited, op);
- }
- }
+ give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, req->limited, op);
+ );
}
ir_nodeset_destroy(&live_nodes);
}
-static void congruence_def(ir_nodeset_t *live_nodes, const ir_node *node)
+static void congruence_def(ir_nodeset_t *const live_nodes, ir_node const *const node, arch_register_req_t const *const req)
{
- const arch_register_req_t *req = arch_get_irn_register_req(node);
-
/* should be same constraint? */
- if (req->type & arch_register_req_type_should_be_same) {
+ if (arch_register_req_is(req, should_be_same)) {
const ir_node *insn = skip_Proj_const(node);
int arity = get_irn_arity(insn);
unsigned node_idx = get_irn_idx(node);
if (interferes)
continue;
- node_idx = uf_union(congruence_classes, node_idx, op_idx);
+ uf_union(congruence_classes, node_idx, op_idx);
DB((dbg, LEVEL_3, "Merge %+F and %+F congruence classes\n",
node, op));
/* one should_be_same is enough... */
/* check should be same constraints */
ir_node *last_phi = NULL;
sched_foreach_reverse(block, node) {
- ir_node *value;
if (is_Phi(node)) {
last_phi = node;
break;
}
- be_foreach_definition(node, cls, value,
- congruence_def(&live_nodes, value);
+ be_foreach_definition(node, cls, value, req,
+ congruence_def(&live_nodes, value, req);
);
be_liveness_transfer(cls, node, &live_nodes);
}
- if (!last_phi)
+ if (!last_phi) {
+ ir_nodeset_destroy(&live_nodes);
return;
+ }
/* check phi congruence classes */
sched_foreach_reverse_from(last_phi, phi) {
}
}
}
+ ir_nodeset_destroy(&live_nodes);
}
static void set_congruence_prefs(ir_node *node, void *data)
* @param node the node
* @param reg the register
*/
-static void use_reg(ir_node *node, const arch_register_t *reg)
+static void use_reg(ir_node *node, const arch_register_t *reg, unsigned width)
{
- unsigned r = arch_register_get_index(reg);
- assignments[r] = node;
+ unsigned r = reg->index;
+ for (unsigned r0 = r; r0 < r + width; ++r0)
+ assignments[r0] = node;
arch_set_irn_register(node, reg);
}
if (!arch_irn_consider_in_reg_alloc(cls, node))
return;
- const arch_register_t *reg = arch_get_irn_register(node);
- unsigned r = arch_register_get_index(reg);
+ const arch_register_t *reg = arch_get_irn_register(node);
+ const arch_register_req_t *req = arch_get_irn_register_req(node);
+ unsigned r = reg->index;
/* assignment->value may be NULL if a value is used at 2 inputs
- so it gets freed twice. */
- assert(assignments[r] == node || assignments[r] == NULL);
- assignments[r] = NULL;
+ * so it gets freed twice. */
+ for (unsigned r0 = r; r0 < r + req->width; ++r0) {
+ assert(assignments[r0] == node || assignments[r0] == NULL);
+ assignments[r0] = NULL;
+ }
}
/**
allocation_info_t *info = get_allocation_info(to_split);
float delta = 0;
- /* stupid hack: don't optimisticallt split don't spill nodes...
+ /* stupid hack: don't optimistically split don't spill nodes...
* (so we don't split away the values produced because of
* must_be_different constraints) */
ir_node *original_insn = skip_Proj(info->original_value);
return false;
const arch_register_t *from_reg = arch_get_irn_register(to_split);
- unsigned from_r = arch_register_get_index(from_reg);
+ unsigned from_r = from_reg->index;
ir_node *block = get_nodes_block(before);
float split_threshold = (float)get_block_execfreq(block) * SPLIT_DELTA;
if (i >= n_regs)
return false;
- const arch_register_t *reg = arch_register_for_index(cls, r);
- ir_node *copy = be_new_Copy(block, to_split);
+ const arch_register_t *reg = arch_register_for_index(cls, r);
+ ir_node *copy = be_new_Copy(block, to_split);
+ unsigned width = 1;
mark_as_copy_of(copy, to_split);
/* hacky, but correct here */
- if (assignments[arch_register_get_index(from_reg)] == to_split)
+ if (assignments[from_reg->index] == to_split)
free_reg_of_value(to_split);
- use_reg(copy, reg);
+ use_reg(copy, reg, width);
sched_add_before(before, copy);
DB((dbg, LEVEL_3,
/**
* Determine and assign a register for node @p node
*/
-static void assign_reg(const ir_node *block, ir_node *node,
- unsigned *forbidden_regs)
+static void assign_reg(ir_node const *const block, ir_node *const node, arch_register_req_t const *const req, unsigned *const forbidden_regs)
{
assert(!is_Phi(node));
/* preassigned register? */
- const arch_register_t *final_reg = arch_get_irn_register(node);
+ arch_register_t const *final_reg = arch_get_irn_register(node);
+ unsigned const width = req->width;
if (final_reg != NULL) {
DB((dbg, LEVEL_2, "Preassignment %+F -> %s\n", node, final_reg->name));
- use_reg(node, final_reg);
+ use_reg(node, final_reg, width);
return;
}
- const arch_register_req_t *req = arch_get_irn_register_req(node);
/* ignore reqs must be preassigned */
- assert (! (req->type & arch_register_req_type_ignore));
+ assert(!arch_register_req_is(req, ignore));
/* give should_be_same boni */
allocation_info_t *info = get_allocation_info(node);
ir_node *in_node = skip_Proj(node);
- if (req->type & arch_register_req_type_should_be_same) {
+ if (arch_register_req_is(req, should_be_same)) {
float weight = (float)get_block_execfreq(block);
int arity = get_irn_arity(in_node);
ir_node *in = get_irn_n(in_node, i);
const arch_register_t *reg = arch_get_irn_register(in);
- unsigned reg_index = arch_register_get_index(reg);
+ unsigned reg_index = reg->index;
/* if the value didn't die here then we should not propagate the
* should_be_same info */
DB((dbg, LEVEL_2, "\n"));
const unsigned *allowed_regs = normal_regs;
- if (req->type & arch_register_req_type_limited) {
+ if (arch_register_req_is(req, limited)) {
allowed_regs = req->limited;
}
if (!rbitset_is_set(allowed_regs, final_reg_index))
continue;
/* alignment constraint? */
- if (req->width > 1 && (req->type & arch_register_req_type_aligned)
- && (final_reg_index % req->width) != 0)
- continue;
+ if (width > 1) {
+ if (arch_register_req_is(req, aligned) && (final_reg_index % width) != 0)
+ continue;
+ bool fine = true;
+ for (unsigned r0 = r+1; r0 < r+width; ++r0) {
+ if (assignments[r0] != NULL)
+ fine = false;
+ }
+ /* TODO: attempt optimistic split here */
+ if (!fine)
+ continue;
+ }
if (assignments[final_reg_index] == NULL)
break;
final_reg = arch_register_for_index(cls, final_reg_index);
DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, final_reg->name));
- use_reg(node, final_reg);
+ use_reg(node, final_reg, width);
}
/**
DB((dbg, LEVEL_2, "Copy %+F (from %+F, before %+F) -> %s\n",
copy, src, before, reg->name));
mark_as_copy_of(copy, src);
- use_reg(copy, reg);
+ unsigned width = 1; /* TODO */
+ use_reg(copy, reg, width);
if (live_nodes != NULL) {
ir_nodeset_insert(live_nodes, copy);
}
/* old register has 1 user less, permutation is resolved */
- assert(arch_register_get_index(arch_get_irn_register(src)) == old_r);
+ assert(arch_get_irn_register(src)->index == old_r);
permutation[r] = r;
assert(n_used[old_r] > 0);
DB((dbg, LEVEL_2, "Perm %+F (perm %+F,%+F, before %+F)\n",
perm, in[0], in[1], before));
+ unsigned width = 1; /* TODO */
+
ir_node *proj0 = new_r_Proj(perm, get_irn_mode(in[0]), 0);
mark_as_copy_of(proj0, in[0]);
const arch_register_t *reg0 = arch_register_for_index(cls, old_r);
- use_reg(proj0, reg0);
+ use_reg(proj0, reg0, width);
ir_node *proj1 = new_r_Proj(perm, get_irn_mode(in[1]), 1);
mark_as_copy_of(proj1, in[1]);
const arch_register_t *reg1 = arch_register_for_index(cls, r2);
- use_reg(proj1, reg1);
+ use_reg(proj1, reg1, width);
/* 1 value is now in the correct register */
permutation[old_r] = old_r;
}
}
-#ifdef DEBUG_libfirm
+#ifndef NDEBUG
/* now we should only have fixpoints left */
for (unsigned r = 0; r < n_regs; ++r) {
assert(permutation[r] == r);
ir_node *op = get_irn_n(node, i);
const arch_register_t *reg = arch_get_irn_register(op);
- rbitset_clear(bitset, arch_register_get_index(reg));
+ rbitset_clear(bitset, reg->index);
}
}
lpp_set_log(lpp, stdout);
/** mark some edges as forbidden */
- int arity = get_irn_arity(node);
- for (int i = 0; i < arity; ++i) {
- ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
-
- const arch_register_req_t *req = arch_get_irn_register_req_in(node, i);
- if (!(req->type & arch_register_req_type_limited))
+ be_foreach_use(node, cls, req, op, op_req,
+ if (!arch_register_req_is(req, limited))
continue;
const unsigned *limited = req->limited;
const arch_register_t *reg = arch_get_irn_register(op);
- unsigned current_reg = arch_register_get_index(reg);
+ unsigned current_reg = reg->index;
for (unsigned r = 0; r < n_regs; ++r) {
if (rbitset_is_set(limited, r))
continue;
rbitset_set(forbidden_edges, current_reg*n_regs + r);
}
- }
+ );
/* add all combinations, except for not allowed ones */
for (unsigned l = 0; l < n_regs; ++l) {
* values are involved */
bool double_width = false;
bool good = true;
- int arity = get_irn_arity(node);
- for (int i = 0; i < arity; ++i) {
- ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
-
+ be_foreach_use(node, cls, req, op, op_req,
/* are there any limitations for the i'th operand? */
- const arch_register_req_t *req = arch_get_irn_register_req_in(node, i);
if (req->width > 1)
double_width = true;
const arch_register_t *reg = arch_get_irn_register(op);
- unsigned reg_index = arch_register_get_index(reg);
- if (req->type & arch_register_req_type_aligned) {
+ unsigned reg_index = reg->index;
+ if (arch_register_req_is(req, aligned)) {
if (!is_aligned(reg_index, req->width)) {
good = false;
continue;
}
}
- if (!(req->type & arch_register_req_type_limited))
+ if (!arch_register_req_is(req, limited))
continue;
const unsigned *limited = req->limited;
good = false;
continue;
}
- }
+ );
/* is any of the live-throughs using a constrained output register? */
- ir_node *value;
unsigned *live_through_regs = NULL;
- be_foreach_definition(node, cls, value,
- if (req_->width > 1)
+ be_foreach_definition(node, cls, value, req,
+ (void)value;
+ if (req->width > 1)
double_width = true;
- if (! (req_->type & arch_register_req_type_limited))
+ if (!arch_register_req_is(req, limited))
continue;
if (live_through_regs == NULL) {
- rbitset_alloca(live_through_regs, n_regs);
+ live_through_regs = rbitset_alloca(n_regs);
determine_live_through_regs(live_through_regs, node);
}
- rbitset_or(forbidden_regs, req_->limited, n_regs);
- if (rbitsets_have_common(req_->limited, live_through_regs, n_regs))
+ rbitset_or(forbidden_regs, req->limited, n_regs);
+ if (rbitsets_have_common(req->limited, live_through_regs, n_regs))
good = false;
);
/* create these arrays if we haven't yet */
if (live_through_regs == NULL) {
- rbitset_alloca(live_through_regs, n_regs);
+ live_through_regs = rbitset_alloca(n_regs);
}
if (double_width) {
}
}
- for (int i = 0; i < arity; ++i) {
- ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
-
- const arch_register_req_t *req = arch_get_irn_register_req_in(node, i);
- if (!(req->type & arch_register_req_type_limited))
+ be_foreach_use(node, cls, req, op, op_req,
+ if (!arch_register_req_is(req, limited))
continue;
const unsigned *limited = req->limited;
const arch_register_t *reg = arch_get_irn_register(op);
- unsigned current_reg = arch_register_get_index(reg);
+ unsigned current_reg = reg->index;
for (unsigned r = 0; r < n_regs; ++r) {
if (rbitset_is_set(limited, r))
continue;
hungarian_remove(bp, r, current_reg);
}
- }
+ );
//hungarian_print_cost_matrix(bp, 1);
hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
assert(a >= 0);
const arch_register_t *reg = arch_get_irn_register(phi);
- int regn = arch_register_get_index(reg);
+ int regn = reg->index;
/* same register? nothing to do */
if (regn == a)
continue;
ir_node *op = pred_info->assignments[a];
const arch_register_t *op_reg = arch_get_irn_register(op);
- /* virtual or joker registers are ok too */
- if ((op_reg->type & arch_register_type_joker)
- || (op_reg->type & arch_register_type_virtual))
+ /* Virtual registers are ok, too. */
+ if (op_reg->type & arch_register_type_virtual)
continue;
permutation[regn] = a;
/* we have permuted all values into the correct registers so we can
simply query which value occupies the phis register in the
predecessor */
- int a = arch_register_get_index(arch_get_irn_register(phi));
+ int a = arch_get_irn_register(phi)->index;
ir_node *op = pred_info->assignments[a];
set_Phi_pred(phi, p, op);
}
continue;
/* give bonus for already assigned register */
- float weight = (float)get_block_execfreq(pred_block);
- unsigned r = arch_register_get_index(reg);
- info->prefs[r] += weight * AFF_PHI;
+ float weight = (float)get_block_execfreq(pred_block);
+ info->prefs[reg->index] += weight * AFF_PHI;
}
}
break;
if (!arch_irn_consider_in_reg_alloc(cls, node))
continue;
+ const arch_register_req_t *req
+ = arch_get_irn_register_req(node);
unsigned r = assignment[n++];
assert(rbitset_is_set(normal_regs, r));
const arch_register_t *reg = arch_register_for_index(cls, r);
DB((dbg, LEVEL_2, "Assign %+F -> %s\n", node, reg->name));
- use_reg(node, reg);
+ use_reg(node, reg, req->width);
/* adapt preferences for phi inputs */
- if (propagate_phi_registers)
- propagate_phi_register(node, r);
+ propagate_phi_register(node, r);
}
}
+static arch_register_req_t *allocate_reg_req(ir_graph *irg)
+{
+ struct obstack *obst = be_get_be_obst(irg);
+ arch_register_req_t *req = OALLOCZ(obst, arch_register_req_t);
+ return req;
+}
+
/**
* Walker: assign registers to all nodes of a block that
* need registers from the currently considered register class.
if (req->cls != cls)
continue;
- if (req->type & arch_register_req_type_ignore) {
+ if (arch_register_req_is(req, ignore)) {
allocation_info_t *info = get_allocation_info(node);
info->current_value = node;
const arch_register_t *reg = arch_get_irn_register(node);
assert(reg != NULL); /* ignore values must be preassigned */
- use_reg(node, reg);
+ use_reg(node, reg, req->width);
continue;
}
if (need_phi) {
ir_mode *mode = get_irn_mode(node);
+ const arch_register_req_t *phi_req = cls->class_req;
+ if (req->width > 1) {
+ arch_register_req_t *new_req = allocate_reg_req(irg);
+ new_req->cls = cls;
+ new_req->type = req->type & arch_register_req_type_aligned;
+ new_req->width = req->width;
+ phi_req = new_req;
+ }
ir_node *phi = be_new_Phi(block, n_preds, phi_ins, mode,
- cls->class_req);
+ phi_req);
DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node));
#ifdef DEBUG_libfirm
/* if the node already has a register assigned use it */
const arch_register_t *reg = arch_get_irn_register(node);
if (reg != NULL) {
- use_reg(node, reg);
+ use_reg(node, reg, req->width);
}
/* remember that this node is live at the beginning of the block */
ir_nodeset_insert(&live_nodes, node);
}
- unsigned *forbidden_regs; /**< collects registers which must
- not be used for optimistic splits */
- rbitset_alloca(forbidden_regs, n_regs);
+ /** Collects registers which must not be used for optimistic splits. */
+ unsigned *const forbidden_regs = rbitset_alloca(n_regs);
/* handle phis... */
assign_phi_registers(block);
/* all live-ins must have a register */
-#ifdef DEBUG_libfirm
+#ifndef NDEBUG
foreach_ir_nodeset(&live_nodes, node, iter) {
const arch_register_t *reg = arch_get_irn_register(node);
assert(reg != NULL);
rewire_inputs(node);
/* we may not use registers used for inputs for optimistic splits */
- int arity = get_irn_arity(node);
- for (int i = 0; i < arity; ++i) {
- ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
-
+ be_foreach_use(node, cls, in_req, op, op_req,
const arch_register_t *reg = arch_get_irn_register(op);
- rbitset_set(forbidden_regs, arch_register_get_index(reg));
- }
+ rbitset_set(forbidden_regs, reg->index);
+ );
/* free registers of values last used at this instruction */
free_last_uses(&live_nodes, node);
/* assign output registers */
- ir_node *value;
- be_foreach_definition_(node, cls, value,
- assign_reg(block, value, forbidden_regs);
+ be_foreach_definition_(node, cls, value, req,
+ assign_reg(block, value, req, forbidden_regs);
);
}
n_block_order = n_blocks;
}
+static void free_block_order(void)
+{
+ xfree(block_order);
+}
+
/**
* Run the register allocator for the current register class.
*/
be_clear_links(irg);
irg_block_walk_graph(irg, NULL, analyze_block, NULL);
- if (create_congruence_classes)
- combine_congruence_classes();
+ combine_congruence_classes();
for (size_t i = 0; i < n_block_order; ++i) {
ir_node *block = block_order[i];
stat_ev_ctx_pop("regcls");
}
+ free_block_order();
+
be_timer_push(T_RA_SPILL_APPLY);
be_abi_fix_stack_nodes(irg);
be_timer_pop(T_RA_SPILL_APPLY);
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pref_alloc)
void be_init_pref_alloc(void)
{
- static be_ra_t be_ra_pref = {
- be_pref_alloc,
- };
- lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
- lc_opt_entry_t *prefalloc_group = lc_opt_get_grp(be_grp, "prefalloc");
- lc_opt_add_table(prefalloc_group, options);
-
+ static be_ra_t be_ra_pref = { be_pref_alloc };
be_register_allocator("pref", &be_ra_pref);
FIRM_DBG_REGISTER(dbg, "firm.be.prefalloc");
}
projects / libfirm / blobdiff