* @brief Preference Guided Register Assignment
* @author Matthias Braun
* @date 14.2.2009
- * @version $Id$
*
* The idea is to allocate registers in 2 passes:
* 1. A first pass to determine "preferred" registers for live-ranges. This
#include "irnode_t.h"
#include "irprintf.h"
#include "irdump.h"
+#include "irtools.h"
+#include "util.h"
#include "obst.h"
#include "raw_bitset.h"
#include "unionfind.h"
static void check_defs(const ir_nodeset_t *live_nodes, float weight,
ir_node *node)
{
- const arch_register_req_t *req = arch_get_register_req_out(node);
+ const arch_register_req_t *req = arch_get_irn_register_req(node);
if (req->type & arch_register_req_type_limited) {
const unsigned *limited = req->limited;
float penalty = weight * DEF_FACTOR;
info = get_allocation_info(node);
for (i = 0; i < arity; ++i) {
ir_node *op = get_irn_n(node, i);
- const arch_register_req_t *req = arch_get_register_req_out(op);
+ const arch_register_req_t *req = arch_get_irn_register_req(op);
if (req->cls != cls)
continue;
if (!arch_irn_consider_in_reg_alloc(cls, op))
continue;
- req = arch_get_register_req(node, i);
+ req = arch_get_irn_register_req_in(node, i);
if (!(req->type & arch_register_req_type_limited))
continue;
static void congruence_def(ir_nodeset_t *live_nodes, const ir_node *node)
{
- const arch_register_req_t *req = arch_get_register_req_out(node);
+ 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) {
* (so we don't split away the values produced because of
* must_be_different constraints) */
original_insn = skip_Proj(info->original_value);
- if (arch_irn_get_flags(original_insn) & arch_irn_flags_dont_spill)
+ if (arch_get_irn_flags(original_insn) & arch_irn_flags_dont_spill)
return false;
from_reg = arch_get_irn_register(to_split);
return false;
reg = arch_register_for_index(cls, r);
- copy = be_new_Copy(cls, block, to_split);
+ copy = be_new_Copy(block, to_split);
mark_as_copy_of(copy, to_split);
/* hacky, but correct here */
if (assignments[arch_register_get_index(from_reg)] == to_split)
return;
}
- req = arch_get_register_req_out(node);
+ req = arch_get_irn_register_req(node);
/* ignore reqs must be preassigned */
assert (! (req->type & arch_register_req_type_ignore));
* registers.
*/
static void permute_values(ir_nodeset_t *live_nodes, ir_node *before,
- unsigned *permutation)
+ unsigned *permutation)
{
unsigned *n_used = ALLOCANZ(unsigned, n_regs);
ir_node *block;
/* create a copy */
src = assignments[old_r];
- copy = be_new_Copy(cls, block, src);
+ copy = be_new_Copy(block, src);
sched_add_before(before, copy);
reg = arch_register_for_index(cls, r);
DB((dbg, LEVEL_2, "Copy %+F (from %+F, before %+F) -> %s\n",
if (!arch_irn_consider_in_reg_alloc(cls, op))
continue;
- req = arch_get_register_req(node, i);
+ req = arch_get_irn_register_req_in(node, i);
if (!(req->type & arch_register_req_type_limited))
continue;
}
}
- /* add all combinations, then remove not allowed ones */
+ /* add all combinations, except for not allowed ones */
for (l = 0; l < n_regs; ++l) {
+ if (!rbitset_is_set(normal_regs, l)) {
+ char name[15];
+ snprintf(name, sizeof(name), "%u_to_%u", l, l);
+ lpp_vars[l*n_regs+l] = lpp_add_var(lpp, name, lpp_binary, 1);
+ continue;
+ }
+
for (r = 0; r < n_regs; ++r) {
if (!rbitset_is_set(normal_regs, r))
continue;
&& rbitset_is_set(forbidden_regs, r))
continue;
+ char name[15];
+ snprintf(name, sizeof(name), "%u_to_%u", l, r);
+
double costs = l==r ? 9 : 8;
lpp_vars[l*n_regs+r]
- = lpp_add_var(lpp, NULL, lpp_binary, costs);
+ = lpp_add_var(lpp, name, lpp_binary, costs);
assert(lpp_vars[l*n_regs+r] > 0);
}
}
/* add constraints */
for (l = 0; l < n_regs; ++l) {
+ int constraint;
/* only 1 destination per register */
- int constraint = lpp_add_cst(lpp, NULL, lpp_equal, 1);
+ constraint = -1;
for (r = 0; r < n_regs; ++r) {
int var = lpp_vars[l*n_regs+r];
if (var == 0)
continue;
+ if (constraint < 0) {
+ char name[64];
+ snprintf(name, sizeof(name), "%u_to_dest", l);
+ constraint = lpp_add_cst(lpp, name, lpp_equal, 1);
+ }
lpp_set_factor_fast(lpp, constraint, var, 1);
}
/* each destination used by at most 1 value */
- constraint = lpp_add_cst(lpp, NULL, lpp_less_equal, 1);
+ constraint = -1;
+ for (r = 0; r < n_regs; ++r) {
+ int var = lpp_vars[r*n_regs+l];
+ if (var == 0)
+ continue;
+ if (constraint < 0) {
+ char name[64];
+ snprintf(name, sizeof(name), "one_to_%u", l);
+ constraint = lpp_add_cst(lpp, name, lpp_less_equal, 1);
+ }
+ lpp_set_factor_fast(lpp, constraint, var, 1);
+ }
}
+ lpp_dump_plain(lpp, fopen("lppdump.txt", "w"));
+
/* solve lpp */
{
ir_graph *irg = get_irn_irg(node);
}
}
assert(dest_reg != (unsigned)-1);
- assignment[l] = dest_reg;
+ assignment[dest_reg] = l;
}
+
+ fprintf(stderr, "Assignment: ");
+ for (l = 0; l < n_regs; ++l) {
+ fprintf(stderr, "%u ", assignment[l]);
+ }
+ fprintf(stderr, "\n");
+ fflush(stdout);
permute_values(live_nodes, node, assignment);
}
lpp_free(lpp);
}
+static bool is_aligned(unsigned num, unsigned alignment)
+{
+ unsigned mask = alignment-1;
+ assert(is_po2(alignment));
+ return (num&mask) == 0;
+}
+
/**
* Enforce constraints at a node by live range splits.
*
/* construct a list of register occupied by live-through values */
unsigned *live_through_regs = NULL;
- /* see if any use constraints are not met */
+ /* see if any use constraints are not met and whether double-width
+ * values are involved */
bool double_width = false;
bool good = true;
for (i = 0; i < arity; ++i) {
continue;
/* are there any limitations for the i'th operand? */
- req = arch_get_register_req(node, i);
+ req = arch_get_irn_register_req_in(node, i);
if (req->width > 1)
double_width = true;
+ reg = arch_get_irn_register(op);
+ reg_index = arch_register_get_index(reg);
+ if (req->type & arch_register_req_type_aligned) {
+ if (!is_aligned(reg_index, req->width)) {
+ good = false;
+ continue;
+ }
+ }
if (!(req->type & arch_register_req_type_limited))
continue;
limited = req->limited;
- reg = arch_get_irn_register(op);
- reg_index = arch_register_get_index(reg);
if (!rbitset_is_set(limited, reg_index)) {
/* found an assignment outside the limited set */
good = false;
- break;
+ continue;
}
}
}
if (double_width) {
+ /* only the ILP variant can solve this yet */
solve_lpp(live_nodes, node, forbidden_regs, live_through_regs);
return;
}
if (!arch_irn_consider_in_reg_alloc(cls, op))
continue;
- req = arch_get_register_req(node, i);
+ req = arch_get_irn_register_req_in(node, i);
if (!(req->type & arch_register_req_type_limited))
continue;
int p;
node = be_lv_get_irn(lv, block, i);
- req = arch_get_register_req_out(node);
+ req = arch_get_irn_register_req(node);
if (req->cls != cls)
continue;
{
size_t i;
- lv = be_assure_liveness(irg);
- be_liveness_assure_sets(lv);
+ be_assure_live_sets(irg);
+ lv = be_get_irg_liveness(irg);
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
be_pre_spill_prepare_constr(irg, cls);
be_timer_pop(T_RA_CONSTR);
- dump(DUMP_RA, irg, "-spillprepare");
+ dump(DUMP_RA, irg, "spillprepare");
/* spill */
be_timer_push(T_RA_SPILL);
check_for_memory_operands(irg);
be_timer_pop(T_RA_SPILL_APPLY);
- dump(DUMP_RA, irg, "-spill");
+ dump(DUMP_RA, irg, "spill");
}
/**
/* we most probably constructed new Phis so liveness info is invalid
* now */
- /* TODO: test liveness_introduce */
- be_liveness_invalidate(lv);
+ be_invalidate_live_sets(irg);
free(normal_regs);
stat_ev_ctx_pop("regcls");
projects / libfirm / blobdiff