#include "beverify.h"
#include "beutil.h"
-#define USE_FACTOR 1.0f
-#define DEF_FACTOR 1.0f
-#define NEIGHBOR_FACTOR 0.2f
-#define AFF_SHOULD_BE_SAME 0.5f
-#define AFF_PHI 1.0f
-#define SPLIT_DELTA 1.0f
+#define USE_FACTOR 1.0f
+#define DEF_FACTOR 1.0f
+#define NEIGHBOR_FACTOR 0.2f
+#define AFF_SHOULD_BE_SAME 0.5f
+#define AFF_PHI 1.0f
+#define SPLIT_DELTA 1.0f
+#define MAX_OPTIMISTIC_SPLIT_RECURSION 0
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
static int *congruence_classes;
static ir_node **block_order;
static int 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) */
return info;
}
+static allocation_info_t *try_get_allocation_info(const ir_node *node)
+{
+ return (allocation_info_t*) get_irn_link(node);
+}
+
/**
* Get allocation information for a basic block
*/
n_allowed = rbitset_popcnt(limited, n_regs);
if (n_allowed > 1) {
/* only create a very weak penalty if multiple regs are allowed */
- penalty = (penalty * 0.8) / n_allowed;
+ penalty = (penalty * 0.8f) / n_allowed;
}
foreach_ir_nodeset(live_nodes, neighbor, iter) {
allocation_info_t *neighbor_info;
if (is_Phi(node))
break;
- check_defs(&live_nodes, weight, node);
+ if (create_preferences)
+ check_defs(&live_nodes, weight, node);
/* mark last uses */
arity = get_irn_arity(node);
be_liveness_transfer(cls, node, &live_nodes);
- /* update weights based on usage constraints */
- for (i = 0; i < arity; ++i) {
- const arch_register_req_t *req;
- const unsigned *limited;
- ir_node *op = get_irn_n(node, i);
+ if (create_preferences) {
+ /* update weights based on usage constraints */
+ for (i = 0; i < arity; ++i) {
+ const arch_register_req_t *req;
+ const unsigned *limited;
+ ir_node *op = get_irn_n(node, i);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
- continue;
+ if (!arch_irn_consider_in_reg_alloc(cls, op))
+ continue;
- req = arch_get_register_req(node, i);
- if (!(req->type & arch_register_req_type_limited))
- continue;
+ req = arch_get_register_req(node, i);
+ if (!(req->type & arch_register_req_type_limited))
+ continue;
- limited = req->limited;
- give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited,
- op);
+ limited = req->limited;
+ give_penalties_for_limits(&live_nodes, weight * USE_FACTOR, limited,
+ op);
+ }
}
}
/* merge preferences */
irg_walk_graph(irg, merge_congruence_prefs, NULL, NULL);
irg_walk_graph(irg, set_congruence_prefs, NULL, NULL);
+ free(congruence_classes);
}
static bool try_optimistic_split(ir_node *to_split, ir_node *before,
float pref, float pref_delta,
- unsigned *output_regs)
+ unsigned *forbidden_regs, int recursion)
{
+ const arch_register_t *from_reg;
const arch_register_t *reg;
ir_node *original_insn;
ir_node *block;
ir_node *copy;
unsigned r;
+ unsigned from_r;
unsigned i;
allocation_info_t *info = get_allocation_info(to_split);
reg_pref_t *prefs;
if (arch_irn_get_flags(original_insn) & arch_irn_flags_dont_spill)
return false;
+ from_reg = arch_get_irn_register(to_split);
+ from_r = arch_register_get_index(from_reg);
+ block = get_nodes_block(before);
+ split_threshold = get_block_execfreq(execfreqs, block) * SPLIT_DELTA;
+
+ if (pref_delta < split_threshold*0.5)
+ return false;
+
/* find the best free position where we could move to */
prefs = ALLOCAN(reg_pref_t, n_regs);
fill_sort_candidates(prefs, info);
for (i = 0; i < n_regs; ++i) {
+ float apref;
+ float apref_delta;
+ bool res;
+ bool old_source_state;
+
+ /* we need a normal register which is not an output register
+ an different from the current register of to_split */
r = prefs[i].num;
if (!rbitset_is_set(normal_regs, r))
continue;
- if (rbitset_is_set(output_regs, r))
+ if (rbitset_is_set(forbidden_regs, r))
+ continue;
+ if (r == from_r)
continue;
+
+ /* is the split worth it? */
+ delta = pref_delta + prefs[i].pref;
+ if (delta < split_threshold) {
+ DB((dbg, LEVEL_3, "Not doing optimistical split of %+F (depth %d), win %f too low\n",
+ to_split, recursion, delta));
+ return false;
+ }
+
+ /* if the register is free then we can do the split */
if (assignments[r] == NULL)
break;
+
+ /* otherwise we might try recursively calling optimistic_split */
+ if (recursion+1 > MAX_OPTIMISTIC_SPLIT_RECURSION)
+ continue;
+
+ apref = prefs[i].pref;
+ apref_delta = i+1 < n_regs ? apref - prefs[i+1].pref : 0;
+ apref_delta += pref_delta - split_threshold;
+
+ /* our source register isn't a usefull destination for recursive
+ splits */
+ old_source_state = rbitset_is_set(forbidden_regs, from_r);
+ rbitset_set(forbidden_regs, from_r);
+ /* try recursive split */
+ res = try_optimistic_split(assignments[r], before, apref,
+ apref_delta, forbidden_regs, recursion+1);
+ /* restore our destination */
+ if (old_source_state) {
+ rbitset_set(forbidden_regs, from_r);
+ } else {
+ rbitset_clear(forbidden_regs, from_r);
+ }
+
+ if (res)
+ break;
}
- if (i >= n_regs) {
- return false;
- }
- /* TODO: use execfreq somehow... */
- block = get_nodes_block(before);
- delta = pref_delta + prefs[i].pref;
- split_threshold = get_block_execfreq(execfreqs, block) * SPLIT_DELTA;
- if (delta < split_threshold) {
- DB((dbg, LEVEL_3, "Not doing optimistical split, win %f too low\n",
- delta));
+ if (i >= n_regs)
return false;
- }
- reg = arch_register_for_index(cls, r);
+ reg = arch_register_for_index(cls, r);
copy = be_new_Copy(cls, block, to_split);
mark_as_copy_of(copy, to_split);
- free_reg_of_value(to_split);
+ /* hacky, but correct here */
+ if (assignments[arch_register_get_index(from_reg)] == to_split)
+ free_reg_of_value(to_split);
use_reg(copy, reg);
sched_add_before(before, copy);
DB((dbg, LEVEL_3,
- "Optimistic live-range split %+F move %+F -> %s before %+F (win %f)\n",
- copy, to_split, reg->name, before, delta));
+ "Optimistic live-range split %+F move %+F(%s) -> %s before %+F (win %f, depth %d)\n",
+ copy, to_split, from_reg->name, reg->name, before, delta, recursion));
return true;
}
* Determine and assign a register for node @p node
*/
static void assign_reg(const ir_node *block, ir_node *node,
- unsigned *output_regs)
+ unsigned *forbidden_regs)
{
const arch_register_t *reg;
allocation_info_t *info;
const unsigned *allowed_regs;
unsigned r;
+ assert(!is_Phi(node));
assert(arch_irn_consider_in_reg_alloc(cls, node));
/* preassigned register? */
}
for (i = 0; i < n_regs; ++i) {
+ float pref, delta;
+ ir_node *before;
+ bool res;
+
r = reg_prefs[i].num;
if (!rbitset_is_set(allowed_regs, r))
continue;
if (assignments[r] == NULL)
break;
- if (!is_Phi(node)) {
- float pref = reg_prefs[i].pref;
- float delta = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0;
- ir_node *before = skip_Proj(node);
- bool res = try_optimistic_split(assignments[r], before,
- pref, delta,
- output_regs);
- if (res)
- break;
- }
+ pref = reg_prefs[i].pref;
+ delta = i+1 < n_regs ? pref - reg_prefs[i+1].pref : 0;
+ before = skip_Proj(node);
+ res = try_optimistic_split(assignments[r], before,
+ pref, delta, forbidden_regs, 0);
+ if (res)
+ break;
}
if (i >= n_regs) {
panic("No register left for %+F\n", node);
for (i = 0; i < arity; ++i) {
ir_node *op = get_irn_n(node, i);
- allocation_info_t *info;
+ allocation_info_t *info = try_get_allocation_info(op);
- if (!arch_irn_consider_in_reg_alloc(cls, op))
+ if (info == NULL)
continue;
- info = get_allocation_info(op);
info = get_allocation_info(info->original_value);
if (info->current_value != op) {
set_irn_n(node, i, info->current_value);
* @param node the current node
*/
static void enforce_constraints(ir_nodeset_t *live_nodes, ir_node *node,
- unsigned *output_regs)
+ unsigned *forbidden_regs)
{
int arity = get_irn_arity(node);
int i, res;
determine_live_through_regs(live_through_regs, node);
}
- rbitset_or(output_regs, req->limited, n_regs);
+ rbitset_or(forbidden_regs, req->limited, n_regs);
if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
good = false;
}
determine_live_through_regs(live_through_regs, node);
if (rbitsets_have_common(req->limited, live_through_regs, n_regs)) {
good = false;
- rbitset_or(output_regs, req->limited, n_regs);
+ rbitset_or(forbidden_regs, req->limited, n_regs);
}
}
}
continue;
/* livethrough values may not use constrainted output registers */
if (rbitset_is_set(live_through_regs, l)
- && rbitset_is_set(output_regs, r))
+ && rbitset_is_set(forbidden_regs, r))
continue;
hungarian_add(bp, r, l, l == r ? 9 : 8);
if (!arch_irn_consider_in_reg_alloc(cls, op))
continue;
- a = find_value_in_block_info(pred_info, op);
+ a = find_value_in_block_info(pred_info, op);
assert(a >= 0);
reg = arch_get_irn_register(node);
*/
static void propagate_phi_register(ir_node *phi, unsigned assigned_r)
{
- int i;
- ir_node *block = get_nodes_block(phi);
- int arity = get_irn_arity(phi);
+ int i;
+ ir_node *block = get_nodes_block(phi);
+ int arity = get_irn_arity(phi);
for (i = 0; i < arity; ++i) {
ir_node *op = get_Phi_pred(phi, i);
/* promote the prefered register */
for (r = 0; r < n_regs; ++r) {
- if (r == assigned_r) {
- info->prefs[r] = AFF_PHI * weight;
- } else {
- info->prefs[r] -= AFF_PHI * weight;
+ if (info->prefs[r] > -weight) {
+ info->prefs[r] = -weight;
}
}
+ info->prefs[assigned_r] = weight;
if (is_Phi(op))
propagate_phi_register(op, assigned_r);
use_reg(node, reg);
/* adapt preferences for phi inputs */
- propagate_phi_register(node, r);
+ if (propagate_phi_registers)
+ propagate_phi_register(node, r);
}
}
{
int i;
ir_nodeset_t live_nodes;
- ir_nodeset_iterator_t iter;
ir_node *node;
int n_preds;
block_info_t *block_info;
block_info_t **pred_block_infos;
ir_node **phi_ins;
- unsigned *output_regs; /**< collects registers which must not
- be used for optimistic splits */
+ unsigned *forbidden_regs; /**< collects registers which must
+ not be used for optimistic splits */
(void) data;
DB((dbg, LEVEL_2, "* Block %+F\n", block));
ir_mode *mode = get_irn_mode(node);
const arch_register_req_t *req = get_default_req_current_cls();
ir_node *phi;
- int i;
phi = new_r_Phi(block, n_preds, phi_ins, mode);
be_set_phi_reg_req(phi, req);
DB((dbg, LEVEL_3, "Create Phi %+F (for %+F) -", phi, node));
#ifdef DEBUG_libfirm
- for (i = 0; i < n_preds; ++i) {
- DB((dbg, LEVEL_3, " %+F", phi_ins[i]));
+ {
+ int i;
+ for (i = 0; i < n_preds; ++i) {
+ DB((dbg, LEVEL_3, " %+F", phi_ins[i]));
+ }
+ DB((dbg, LEVEL_3, "\n"));
}
- DB((dbg, LEVEL_3, "\n"));
#endif
mark_as_copy_of(phi, node);
sched_add_after(block, phi);
/* if the node already has a register assigned use it */
reg = arch_get_irn_register(node);
if (reg != NULL) {
- /* TODO: consult pred-block infos here. The value could be copied
- away in some/all predecessor blocks. We need to construct
- phi-nodes in this case.
- We even need to construct some Phi_0 like constructs in cases
- where the predecessor allocation is not determined yet. */
use_reg(node, reg);
}
ir_nodeset_insert(&live_nodes, node);
}
- rbitset_alloca(output_regs, n_regs);
+ rbitset_alloca(forbidden_regs, n_regs);
/* handle phis... */
assign_phi_registers(block);
- /* assign regs for live-in values */
- foreach_ir_nodeset(&live_nodes, node, iter) {
- const arch_register_t *reg = arch_get_irn_register(node);
- if (reg != NULL)
- continue;
-
- assign_reg(block, node, output_regs);
- /* shouldn't happen if we color in dominance order */
- assert (!is_Phi(node));
+ /* all live-ins must have a register */
+#ifdef DEBUG_libfirm
+ {
+ ir_nodeset_iterator_t iter;
+ foreach_ir_nodeset(&live_nodes, node, iter) {
+ const arch_register_t *reg = arch_get_irn_register(node);
+ assert(reg != NULL);
+ }
}
+#endif
/* assign instructions in the block */
sched_foreach(block, node) {
- unsigned r;
+ int i;
+ int arity;
/* phis are already assigned */
if (is_Phi(node))
rewire_inputs(node);
/* enforce use constraints */
- rbitset_clear_all(output_regs, n_regs);
- enforce_constraints(&live_nodes, node, output_regs);
- /* we may not use registers occupied here for optimistic splits */
- for (r = 0; r < n_regs; ++r) {
- if (assignments[r] != NULL)
- rbitset_set(output_regs, r);
- }
+ rbitset_clear_all(forbidden_regs, n_regs);
+ enforce_constraints(&live_nodes, node, forbidden_regs);
rewire_inputs(node);
+ /* we may not use registers used for inputs for optimistic splits */
+ arity = get_irn_arity(node);
+ for (i = 0; i < arity; ++i) {
+ ir_node *op = get_irn_n(node, i);
+ const arch_register_t *reg;
+ if (!arch_irn_consider_in_reg_alloc(cls, op))
+ continue;
+
+ reg = arch_get_irn_register(op);
+ rbitset_set(forbidden_regs, arch_register_get_index(reg));
+ }
+
/* free registers of values last used at this instruction */
free_last_uses(&live_nodes, node);
ir_node *proj = get_edge_src_irn(edge);
if (!arch_irn_consider_in_reg_alloc(cls, proj))
continue;
- assign_reg(block, proj, output_regs);
+ assign_reg(block, proj, forbidden_regs);
}
} else if (arch_irn_consider_in_reg_alloc(cls, node)) {
- assign_reg(block, node, output_regs);
+ assign_reg(block, node, forbidden_regs);
}
}
lv = be_assure_liveness(birg);
be_liveness_assure_sets(lv);
- be_liveness_assure_chk(lv);
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
DB((dbg, LEVEL_2, "=== Allocating registers of %s ===\n", cls->name));
be_clear_links(irg);
+
irg_block_walk_graph(irg, NULL, analyze_block, NULL);
- combine_congruence_classes();
+ if (create_congruence_classes)
+ combine_congruence_classes();
for (i = 0; i < n_block_order; ++i) {
ir_node *block = block_order[i];
static be_ra_t be_ra_straight = {
be_straight_alloc,
};
-
- FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc");
+ lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+ lc_opt_entry_t *straightalloc_group = lc_opt_get_grp(be_grp, "straightalloc");
+ lc_opt_add_table(straightalloc_group, options);
be_register_allocator("straight", &be_ra_straight);
+ FIRM_DBG_REGISTER(dbg, "firm.be.straightalloc");
}
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_straight_alloc);
projects / libfirm / blobdiff