#include "belive_t.h"
#include "benode_t.h"
#include "bearch.h"
+#include "beirgmod.h"
#include "beifg.h"
+#include "beinsn_t.h"
#include "bechordal_t.h"
#include "bechordal_draw.h"
#define NO_COLOR (-1)
+#define MAX(x, y) ((x) > (y) ? (x) : (y))
+#define MIN(x, y) ((x) < (y) ? (x) : (y))
+
#define DUMP_INTERVALS
typedef struct _be_chordal_alloc_env_t {
be_chordal_env_t *chordal_env;
- pset *pre_colored; /**< Set of precolored nodes. */
- bitset_t *live; /**< A liveness bitset. */
- bitset_t *colors; /**< The color mask. */
- bitset_t *in_colors; /**< Colors used by live in values. */
- int colors_n; /**< The number of colors. */
+ pset *pre_colored; /**< Set of precolored nodes. */
+ bitset_t *live; /**< A liveness bitset. */
+ bitset_t *tmp_colors; /**< An auxiliary bitset which is as long as the number of colors in the class. */
+ bitset_t *colors; /**< The color mask. */
+ bitset_t *in_colors; /**< Colors used by live in values. */
+ int colors_n; /**< The number of colors. */
+ DEBUG_ONLY(firm_dbg_module_t *constr_dbg;) /**< Debug output for the constraint handler. */
} be_chordal_alloc_env_t;
#include "fourcc.h"
*/
static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
{
- // return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
- return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
+ return arch_irn_has_reg_class(env->birg->main_env->arch_env, irn, -1, env->cls);
+ // return arch_irn_consider_in_reg_alloc(env->birg->main_env->arch_env, env->cls, irn);
}
#define has_limited_constr(req, irn) \
(arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
-typedef struct _operand_t operand_t;
-
-struct _operand_t {
- ir_node *irn;
- ir_node *carrier;
- operand_t *partner;
- int pos;
- arch_register_req_t req;
-};
-
-typedef struct {
- operand_t *ops;
- int n_ops;
- int use_start;
- ir_node *next_insn;
- unsigned in_constraints : 1;
- unsigned out_constraints : 1;
- unsigned has_constraints : 1;
- unsigned pre_colored : 1;
-} insn_t;
-
-static insn_t *scan_insn(be_chordal_env_t *env, ir_node *irn, struct obstack *obst)
+static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
{
- const arch_env_t *arch_env = env->birg->main_env->arch_env;
- operand_t o;
- insn_t *insn;
- int i, n;
- int pre_colored = 0;
-
- insn = obstack_alloc(obst, sizeof(insn[0]));
- memset(insn, 0, sizeof(insn[0]));
-
- insn->next_insn = sched_next(irn);
- if(get_irn_mode(irn) == mode_T) {
- ir_node *p;
-
- for(p = sched_next(irn); is_Proj(p); p = sched_next(p)) {
- if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, p)) {
- o.carrier = p;
- o.irn = irn;
- o.pos = -(get_Proj_proj(p) + 1);
- o.partner = NULL;
- arch_get_register_req(arch_env, &o.req, p, -1);
- obstack_grow(obst, &o, sizeof(o));
- insn->n_ops++;
- insn->out_constraints |= arch_register_req_is(&o.req, limited);
- pre_colored += arch_get_irn_register(arch_env, p) != NULL;
- }
- }
+ bitset_t *tmp = alloc_env->tmp_colors;
+ bitset_copy(tmp, colors);
+ bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
+ return bitset_next_clear(tmp, 0);
+}
- insn->next_insn = p;
- }
+static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
+{
+ bitset_t *res = bs;
- else if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, irn)) {
- o.carrier = irn;
- o.irn = irn;
- o.pos = -1;
- o.partner = NULL;
- arch_get_register_req(arch_env, &o.req, irn, -1);
- obstack_grow(obst, &o, sizeof(o));
- insn->n_ops++;
- insn->out_constraints |= arch_register_req_is(&o.req, limited);
- pre_colored += arch_get_irn_register(arch_env, irn) != NULL;
+ if(!o1) {
+ bitset_copy(bs, o2->regs);
+ return bs;
}
- insn->pre_colored = pre_colored == insn->n_ops;
- insn->use_start = insn->n_ops;
-
- for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
- ir_node *op = get_irn_n(irn, i);
-
- if(arch_irn_consider_in_reg_alloc(arch_env, env->cls, op)) {
- o.carrier = op;
- o.irn = irn;
- o.pos = i;
- o.partner = NULL;
- arch_get_register_req(arch_env, &o.req, irn, i);
- obstack_grow(obst, &o, sizeof(o));
- insn->n_ops++;
- insn->in_constraints |= arch_register_req_is(&o.req, limited);
- }
+ if(!o2) {
+ bitset_copy(bs, o1->regs);
+ return bs;
}
- insn->has_constraints = insn->in_constraints | insn->out_constraints;
- insn->ops = obstack_finish(obst);
- return insn;
-}
-
-#if 0
-static operand_t *find_unpaired_use(insn_t *insn, const operand_t *op, int can_be_constrained)
-{
- int i;
- operand_t *res = NULL;
-
- for(i = insn->use_start; i < insn->n_ops; ++i) {
- operand_t *op = &insn->ops[i];
- int has_constraint = arch_register_req_is(&op->req, limited);
-
- if(!values_interfere(op->carrier, op->irn) && !op->partner) {
+ assert(o1->req.cls == o2->req.cls);
- if(!has_constraint || can_be_constrained) {
- if(arch_register_req_is(&op->req, should_be_same) && op->req.other_same == op->carrier)
- return op;
- else
- res = op;
- }
- }
- }
+ if(bitset_contains(o1->regs, o2->regs))
+ bitset_copy(bs, o1->regs);
+ else if(bitset_contains(o2->regs, o1->regs))
+ bitset_copy(bs, o2->regs);
+ else
+ res = NULL;
return res;
}
-static void pair_up_operands(insn_t *insn)
+static be_insn_t *chordal_scan_insn(be_chordal_alloc_env_t *env, ir_node *irn)
{
- firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
- int i;
-
- for(i = 0; i < insn->use_start; ++i) {
- operand_t *op = &insn->ops[i];
- int has_constraint = arch_register_req_is(&op->req, limited);
- operand_t *partner = find_unpaired_use(insn, op, !has_constraint);
+ be_insn_env_t ie;
- if(partner) {
- op->partner = partner;
- partner->partner = op;
- }
- }
+ ie.ignore_colors = env->chordal_env->ignore_colors;
+ ie.aenv = env->chordal_env->birg->main_env->arch_env;
+ ie.obst = &env->chordal_env->obst;
+ ie.cls = env->chordal_env->cls;
+ return be_scan_insn(&ie, irn);
}
-#endif
-static void add_possible_partners(insn_t *insn, int curr, const arch_register_t *out_reg, bipartite_t *bp, int can_be_constrained)
+static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
{
- bitset_t *bs;
- int i;
+ const be_chordal_env_t *env = alloc_env->chordal_env;
- if(out_reg)
- bs = bitset_alloca(out_reg->reg_class->n_regs);
+ int n_uses = be_insn_n_uses(insn);
+ int n_defs = be_insn_n_defs(insn);
+ bitset_t *bs = bitset_alloca(env->cls->n_regs);
+ bipartite_t *bp = bipartite_new(n_defs, n_uses);
+ int *pairing = alloca(MAX(n_defs, n_uses) * sizeof(pairing[0]));
- for(i = insn->use_start; i < insn->n_ops; ++i) {
- const operand_t *op = &insn->ops[i];
+ int i, j;
- /*
+ /*
+ For each out operand, try to find an in operand which can be assigned the
+ same register as the out operand.
+ */
+ for(j = 0; j < insn->use_start; ++j) {
+ be_operand_t *out_op = &insn->ops[j];
+
+ /* Try to find an in operand which has ... */
+ for(i = insn->use_start; i < insn->n_ops; ++i) {
+ const be_operand_t *op = &insn->ops[i];
+
+ /*
The in operand can only be paired with a def, if the node defining the
operand's value does not interfere with the instruction itself. That
would mean, that it is live at the instruction, so no result of the instruction
can have the same register as the operand.
- Furthermore, if the operand has already been paired (due to previous calls)
- to this function, we do not touch this partnership.
- */
- if(!values_interfere(op->irn, op->carrier) && !op->partner) {
- int has_constraint = arch_register_req_is(&op->req, limited);
-
- if(has_constraint && out_reg && out_reg->reg_class == op->req.cls) {
- bitset_clear_all(bs);
- op->req.limited(op->req.limited_env, bs);
- if(bitset_is_set(bs, out_reg->index)) {
- bipartite_add(bp, curr, i - insn->use_start);
- return;
- }
+ Furthermore, tow operands can be paired, if the admissible registers
+ of one are a subset of the other's. We record the operand whose constraints
+ count in the decisive array.
+ */
+ if(!values_interfere(op->irn, op->carrier)) {
+ if(get_decisive_partner_regs(bs, out_op, op))
+ bipartite_add(bp, j, i - insn->use_start);
}
+ }
+ }
- if(!has_constraint || can_be_constrained) {
- bipartite_add(bp, curr, i - insn->use_start);
- if(arch_register_req_is(&op->req, should_be_same) && op->req.other_same == op->carrier)
- return;
- }
+ /* Compute the pairing. */
+ bipartite_matching(bp, pairing);
+ for(i = 0; i < insn->use_start; ++i) {
+ int p = pairing[i] + insn->use_start;
+
+ if(p >= insn->use_start) {
+ insn->ops[i].partner = &insn->ops[p];
+ insn->ops[p].partner = &insn->ops[i];
}
}
+
+ bipartite_free(bp);
}
-static void pair_up_operands(const arch_env_t *arch_env, insn_t *insn) {
+
+static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env, be_insn_t **the_insn)
+{
+ be_chordal_env_t *env = alloc_env->chordal_env;
+ const arch_env_t *aenv = env->birg->main_env->arch_env;
+ be_insn_t *insn = *the_insn;
+ ir_node *bl = get_nodes_block(insn->irn);
+ ir_node *copy = NULL;
+ ir_node *perm = NULL;
+ bitset_t *out_constr = bitset_alloca(env->cls->n_regs);
+ bitset_t *bs = bitset_alloca(env->cls->n_regs);
+ DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
+
int i;
- bipartite_t *bp = bipartite_new(insn->use_start, insn->n_ops - insn->use_start);
- int *match = alloca(insn->use_start * sizeof(match[0]));
+ assert(insn->has_constraints && "only do this for constrained nodes");
+
+ /*
+ Collect all registers that occur in output constraints.
+ This is necessary, since if the insn has one of these as an input constraint
+ and the corresponding operand interferes with the insn, the operand must
+ be copied.
+ */
for(i = 0; i < insn->use_start; ++i) {
- operand_t *op = &insn->ops[i];
- const arch_register_t *reg = arch_get_irn_register(arch_env, op->carrier);
- int has_constraint = arch_register_req_is(&op->req, limited);
- add_possible_partners(insn, i, reg, bp, !has_constraint);
+ be_operand_t *op = &insn->ops[i];
+ if(op->has_constraints)
+ bitset_or(out_constr, op->regs);
}
- bipartite_matching(bp, match);
- for(i = 0; i < insn->use_start; ++i) {
- int p = match[i] + insn->use_start;
+ /*
+ Now, figure out which input operand must be copied since it has input
+ constraints which are also output constraints.
+ */
+ for(i = insn->use_start; i < insn->n_ops; ++i) {
+ be_operand_t *op = &insn->ops[i];
+ if(op->has_constraints && (values_interfere(op->carrier, insn->irn) || arch_irn_is(aenv, op->carrier, ignore))) {
+ bitset_copy(bs, op->regs);
+ bitset_and(bs, out_constr);
+
+ /*
+ The operand (interfering with the node) has input constraints
+ which also occur as output constraints, so insert a copy.
+ */
+ if(bitset_popcnt(bs) > 0) {
+ copy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
+ op->carrier = copy;
+ sched_add_before(insn->irn, copy);
+ set_irn_n(insn->irn, op->pos, op->carrier);
+
+ DBG((dbg, LEVEL_2, "adding copy for interfering and constrained op %+F\n", op->carrier));
+ }
+ }
+ }
- if(p >= insn->use_start) {
- insn->ops[i].partner = &insn->ops[p];
- insn->ops[p].partner = &insn->ops[i];
+ /*
+ Make the Perm, recompute liveness and re-scan the insn since the
+ in operands are now the Projs of the Perm.
+ */
+ perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(insn->irn));
+
+ /* Registers are propagated by insert_Perm_after(). Clean them here! */
+ if(perm) {
+ const ir_edge_t *edge;
+
+ foreach_out_edge(perm, edge) {
+ ir_node *proj = get_edge_src_irn(edge);
+ arch_set_irn_register(aenv, proj, NULL);
+ }
+
+ /*
+ We also have to re-build the insn since the input operands are now the Projs of
+ the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
+ the live sets may change.
+ */
+ be_liveness(env->irg);
+ obstack_free(&env->obst, insn);
+ *the_insn = insn = chordal_scan_insn(alloc_env, insn->irn);
+
+ /*
+ Copy the input constraints of the insn to the Perm as output
+ constraints. Succeeding phases (coalescing will need that).
+ */
+ for(i = insn->use_start; i < insn->n_ops; ++i) {
+ be_operand_t *op = &insn->ops[i];
+ ir_node *proj = op->carrier;
+ /*
+ Note that the predecessor must not be a Proj of the Perm,
+ since ignore-nodes are not Perm'ed.
+ */
+ if(op->has_constraints && is_Proj(proj) && get_Proj_pred(proj) == perm) {
+ be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), &op->req);
+ }
}
}
- bipartite_free(bp);
+ return perm;
}
-static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn)
+static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env, ir_node *irn, int *silent)
{
be_chordal_env_t *env = alloc_env->chordal_env;
void *base = obstack_base(&env->obst);
- insn_t *insn = scan_insn(env, irn, &env->obst);
+ be_insn_t *insn = chordal_scan_insn(alloc_env, irn);
ir_node *res = insn->next_insn;
+ int be_silent = *silent;
if(insn->pre_colored) {
int i;
pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
}
+ /*
+ If the current node is a barrier toggle the silent flag.
+ If we are in the start block, we are ought to be silent at the beginning,
+ so the toggling activates the constraint handling but skips the barrier.
+ If we are in the end block we handle the in requirements of the barrier
+ and set the rest to silent.
+ */
+ if(be_is_Barrier(irn))
+ *silent = !*silent;
+
+ if(be_silent)
+ goto end;
+
/*
Perms inserted before the constraint handling phase are considered to be
correctly precolored. These Perms arise during the ABI handling phase.
*/
- if(insn->has_constraints && !be_is_Perm(irn)) {
- firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
+ if(insn->has_constraints) {
const arch_env_t *aenv = env->birg->main_env->arch_env;
int n_regs = env->cls->n_regs;
bitset_t *bs = bitset_alloca(n_regs);
- bitset_t *non_ignore = bitset_alloca(n_regs);
ir_node **alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
bipartite_t *bp = bipartite_new(n_regs, n_regs);
int *assignment = alloca(n_regs * sizeof(assignment[0]));
pmap *partners = pmap_create();
+ DEBUG_ONLY(firm_dbg_module_t *dbg = alloc_env->constr_dbg;)
int i, n_alloc;
long col;
const ir_edge_t *edge;
- ir_node *perm = insert_Perm_after(aenv, env->cls, env->dom_front, sched_prev(irn));
-
- arch_put_non_ignore_regs(aenv, env->cls, non_ignore);
-
- /* Registers are propagated by insert_Perm_after(). Clean them here! */
- if(perm) {
- foreach_out_edge(perm, edge) {
- ir_node *proj = get_edge_src_irn(edge);
- arch_set_irn_register(aenv, proj, NULL);
- }
- }
-
-
- be_liveness(env->irg);
- insn = scan_insn(env, irn, &env->obst);
-
- DBG((dbg, LEVEL_1, "handling constraints for %+F\n", irn));
+ ir_node *perm = NULL;
/*
- * If there was no Perm made, nothing was alive in this register class.
- * This means, that the node has no operands, thus no input constraints.
- * so it had output constraints. The other results then can be assigned freely.
- */
+ prepare the constraint handling of this node.
+ Perms are constructed and Copies are created for constrained values
+ interfering with the instruction.
+ */
+ perm = pre_process_constraints(alloc_env, &insn);
- pair_up_operands(aenv, insn);
+ /* find suitable in operands to the out operands of the node. */
+ pair_up_operands(alloc_env, insn);
+ /*
+ look at the in/out operands and add each operand (and its possible partner)
+ to a bipartite graph (left: nodes with partners, right: admissible colors).
+ */
for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
- operand_t *op = &insn->ops[i];
- if((op->partner ? !pmap_contains(partners, op->partner->carrier) : 1)
- && arch_register_req_is(&op->req, limited)
- && arch_irn_consider_in_reg_alloc(aenv, env->cls, op->carrier)) {
+ be_operand_t *op = &insn->ops[i];
+
+ /*
+ If the operand has no partner or the partner has not been marked
+ for allocation, determine the admissible registers and mark it
+ for allocation by associating the node and its partner with the
+ set of admissible registers via a bipartite graph.
+ */
+ if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
pmap_insert(partners, op->carrier, op->partner ? op->partner->carrier : NULL);
alloc_nodes[n_alloc] = op->carrier;
- DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, pmap_get(partners, op->carrier)));
+ DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, op->partner ? op->partner->carrier : NULL));
- bitset_clear_all(bs);
- op->req.limited(op->req.limited_env, bs);
- bitset_and(bs, non_ignore);
+ bitset_clear_all(bs);
+ get_decisive_partner_regs(bs, op, op->partner);
DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));
}
}
+ /*
+ Put all nodes which live by the constrained instruction also to the
+ allocation bipartite graph. They are considered unconstrained.
+ */
if(perm) {
- /* Make the input constraints of the node to output constraints of the Perm's Projs */
- for(i = insn->use_start; i < insn->n_ops; ++i) {
- operand_t *op = &insn->ops[i];
-
- /*
- If the operand is an "in" operand, constrained and the carrier is a Proj to the Perm,
- then copy the in constraint to the Perm's out constraint
- */
- if(arch_register_req_is(&op->req, limited) && is_Proj(op->carrier) && perm == get_Proj_pred(op->carrier))
- be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(op->carrier)), &op->req);
- }
-
foreach_out_edge(perm, edge) {
ir_node *proj = get_edge_src_irn(edge);
assert(is_Proj(proj));
- if(values_interfere(proj, irn)) {
+ if(values_interfere(proj, irn) && !pmap_contains(partners, proj)) {
assert(n_alloc < n_regs);
alloc_nodes[n_alloc] = proj;
pmap_insert(partners, proj, NULL);
bitset_clear_all(bs);
- arch_get_allocatable_regs(aenv, proj, -1, bs);
- bitset_and(bs, non_ignore);
+ arch_put_non_ignore_regs(aenv, env->cls, bs);
bitset_foreach(bs, col)
bipartite_add(bp, n_alloc, col);
}
}
+ /* Compute a valid register allocation. */
bipartite_matching(bp, assignment);
/* Assign colors obtained from the matching. */
for(i = 0; i < n_alloc; ++i) {
- int j;
- ir_node *nodes[2];
const arch_register_t *reg;
+ ir_node *nodes[2];
+ int j;
assert(assignment[i] >= 0 && "there must have been a register assigned");
reg = arch_register_for_index(env->cls, assignment[i]);
/* Allocate the non-constrained Projs of the Perm. */
if(perm) {
+
bitset_clear_all(bs);
/* Put the colors of all Projs in a bitset. */
DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
if(reg == NULL) {
- col = bitset_next_clear(bs, 0);
+ col = get_next_free_reg(alloc_env, bs);
reg = arch_register_for_index(env->cls, col);
bitset_set(bs, reg->index);
arch_set_irn_register(aenv, proj, reg);
pmap_destroy(partners);
}
+end:
obstack_free(&env->obst, base);
return res;
}
/**
* Handle constraint nodes in each basic block.
- * be_insert_constr_perms() inserts Perm nodes which perm
+ * handle_constraints() inserts Perm nodes which perm
* over all values live at the constrained node right in front
* of the constrained node. These Perms signal a constrained node.
- * For further comments, refer to handle_constraints_at_perm().
+ * For further comments, refer to handle_constraints().
*/
static void constraints(ir_node *bl, void *data)
{
- firm_dbg_module_t *dbg = firm_dbg_register("firm.be.chordal.constr");
be_chordal_alloc_env_t *env = data;
- arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
+
+ /*
+ Start silent in the start block.
+ The silence remains until the first barrier is seen.
+ Each other block is begun loud.
+ */
+ int silent = bl == get_irg_start_block(get_irn_irg(bl));
ir_node *irn;
+ /*
+ If the block is the start block search the barrier and
+ start handling constraints from there.
+ */
+
for(irn = sched_first(bl); !sched_is_end(irn);) {
- irn = handle_constraints(env, irn);
+ irn = handle_constraints(env, irn, &silent);
}
}
be_chordal_alloc_env_t *alloc_env = env_ptr;
be_chordal_env_t *env = alloc_env->chordal_env;
- const arch_env_t *arch_env = env->birg->main_env->arch_env;
bitset_t *live = alloc_env->live;
- firm_dbg_module_t *dbg = env->dbg;
ir_node *irn;
+ DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
int i, n;
unsigned step = 0;
unsigned pressure = 0;
struct list_head *head;
- pset *live_in = put_live_in(block, pset_new_ptr_default());
+ pset *live_in = put_live_in(block, pset_new_ptr_default());
pset *live_end = put_live_end(block, pset_new_ptr_default());
DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
* Make final uses of all values live out of the block.
* They are necessary to build up real intervals.
*/
- for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
+ foreach_pset(live_end, irn) {
if(has_reg_class(env, irn)) {
- DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
- bitset_set(live, get_irn_graph_nr(irn));
+ DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
+ bitset_set(live, get_irn_idx(irn));
border_use(irn, step, 0);
}
}
*/
sched_foreach_reverse(block, irn) {
DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
- DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
+ DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
/*
* If the node defines some value, which can put into a
* register of the current class, make a border for it.
*/
if(has_reg_class(env, irn)) {
- int nr = get_irn_graph_nr(irn);
+ int nr = get_irn_idx(irn);
bitset_clear(live, nr);
border_def(irn, step, 1);
ir_node *op = get_irn_n(irn, i);
if(has_reg_class(env, op)) {
- int nr = get_irn_graph_nr(op);
-
- DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
+ int nr = get_irn_idx(op);
+ const char *msg = "-";
if(!bitset_is_set(live, nr)) {
border_use(op, step, 1);
bitset_set(live, nr);
+ msg = "X";
}
+
+ DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
}
}
}
/*
* Add initial defs for all values live in.
*/
- for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
+ foreach_pset(live_in, irn) {
if(has_reg_class(env, irn)) {
/* Mark the value live in. */
- bitset_set(live, get_irn_graph_nr(irn));
+ bitset_set(live, get_irn_idx(irn));
/* Add the def */
border_def(irn, step, 0);
}
}
-
- del_pset(live_in);
- del_pset(live_end);
+ del_pset(live_in);
+ del_pset(live_end);
}
static void assign(ir_node *block, void *env_ptr)
{
be_chordal_alloc_env_t *alloc_env = env_ptr;
be_chordal_env_t *env = alloc_env->chordal_env;
- firm_dbg_module_t *dbg = env->dbg;
bitset_t *live = alloc_env->live;
bitset_t *colors = alloc_env->colors;
bitset_t *in_colors = alloc_env->in_colors;
const arch_env_t *arch_env = env->birg->main_env->arch_env;
+ struct list_head *head = get_block_border_head(env, block);
+ pset *live_in = put_live_in(block, pset_new_ptr_default());
const ir_node *irn;
border_t *b;
- struct list_head *head = get_block_border_head(env, block);
- pset *live_in = put_live_in(block, pset_new_ptr_default());
+ DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
bitset_clear_all(colors);
bitset_clear_all(live);
DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
list_for_each_entry(border_t, b, head, list) {
DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
- b->irn, get_irn_graph_nr(b->irn)));
+ b->irn, get_irn_idx(b->irn)));
}
/*
* Since their colors have already been assigned (The dominators were
* allocated before), we have to mark their colors as used also.
*/
- for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
+ foreach_pset(live_in, irn) {
if(has_reg_class(env, irn)) {
const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
int col;
assert(reg && "Node must have been assigned a register");
col = arch_register_get_index(reg);
+ DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
+
/* Mark the color of the live in value as used. */
bitset_set(colors, col);
bitset_set(in_colors, col);
/* Mark the value live in. */
- bitset_set(live, get_irn_graph_nr(irn));
+ bitset_set(live, get_irn_idx(irn));
}
}
*/
list_for_each_entry_reverse(border_t, b, head, list) {
ir_node *irn = b->irn;
- int nr = get_irn_graph_nr(irn);
+ int nr = get_irn_idx(irn);
+ int ignore = arch_irn_is(arch_env, irn, ignore);
/*
* Assign a color, if it is a local def. Global defs already have a
const arch_register_t *reg;
int col = NO_COLOR;
- if(pset_find_ptr(alloc_env->pre_colored, irn)) {
+ if(pset_find_ptr(alloc_env->pre_colored, irn) || ignore) {
reg = arch_get_irn_register(arch_env, irn);
col = reg->index;
assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
}
else {
- col = bitset_next_clear(colors, 0);
+ col = get_next_free_reg(alloc_env, colors);
reg = arch_register_for_index(env->cls, col);
assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
+ assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
}
bitset_set(colors, col);
arch_set_irn_register(arch_env, irn, reg);
- DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
- arch_register_get_name(reg), col, irn));
+ DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
bitset_set(live, nr);
ir_graph *irg = chordal_env->irg;
- if(get_irg_dom_state(irg) != dom_consistent)
- compute_doms(irg);
+ assure_doms(irg);
env.chordal_env = chordal_env;
env.colors_n = colors_n;
- env.colors = bitset_malloc(colors_n);
- env.in_colors = bitset_malloc(colors_n);
+ env.colors = bitset_alloca(colors_n);
+ env.tmp_colors = bitset_alloca(colors_n);
+ env.in_colors = bitset_alloca(colors_n);
env.pre_colored = pset_new_ptr_default();
+ FIRM_DBG_REGISTER(env.constr_dbg, "firm.be.chordal.constr");
+
/* Handle register targeting constraints */
dom_tree_walk_irg(irg, constraints, NULL, &env);
}
be_numbering(irg);
- env.live = bitset_malloc(get_graph_node_count(chordal_env->irg));
+ env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
/* First, determine the pressure */
dom_tree_walk_irg(irg, pressure, NULL, &env);
be_numbering_done(irg);
if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
- plotter_t *plotter;
+ plotter_t *plotter;
ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
- plotter = new_plotter_ps(buf);
- draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
- plotter_free(plotter);
+ plotter = new_plotter_ps(buf);
+ draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
+ plotter_free(plotter);
}
- free(env.live);
- free(env.colors);
- free(env.in_colors);
del_pset(env.pre_colored);
}
projects / libfirm / blobdiff