+ return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
+}
+
+#define has_limited_constr(req, irn) \
+ (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
+
+static int try_pre_color(be_chordal_env_t *env, ir_node *irn,
+ pset *pre_colored, bitset_t *colors_used)
+{
+ arch_register_req_t req;
+
+ if(arch_get_register_req(env->main_env->arch_env, &req, irn, -1) && arch_register_req_is(&req, limited)) {
+
+ bitset_t *bs = bitset_alloca(env->cls->n_regs);
+ const arch_register_t *reg;
+ int col;
+
+ req.limited(irn, -1, bs);
+ col = bitset_next_set(bs, 0);
+ reg = arch_register_for_index(env->cls, col);
+
+ pset_insert_ptr(pre_colored, irn);
+ arch_set_irn_register(env->main_env->arch_env, irn, reg);
+ bitset_set(colors_used, col);
+
+ DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name));
+
+ return 1;
+ }
+
+ return 0;
+}
+
+/**
+ * Handle register targeting constraints signaled by a Perm.
+ * @param alloc_env Private data for the allocation phase.
+ * @param perm The Perm node guarding the constrained node.
+ * @return The constrained node.
+
+ Pro-coloring works as follows:
+
+ +-----------------------------------+
+ | Perm |
+ +---.-------.--------.---------.----+
+ | | | |
+ +---+--+ | | |
+ | Proj | | | |
+ +------+ | | |
+ | | |
+ +--+---+ | |
+ | Proj | | |
+ +--.---+ | |
+ | | |
+ | +--+---+ |
+ | | Proj | |
+ | +------+ |
+ | |
+ | +---+--+
+ `-. | Proj | Result:
+ `._ +---.--+ R1
+ `. |
+ `-. |
+ `._ |
+ +`.-+--+
+ |Constr| Result:
+ +------+ R2
+
+ 1) Look at all Projs of the Perm if they have output constraints.
+ If one has an output constraint, pre-color it, else record it
+ in the set leftover. Its color has to be chosen after all
+ constrained nodes are colored. Furthermore record all colors
+ used in the pre-coloring in the set colors_used.
+
+ 2) Look whether the first node not a Proj (this is the constrained
+ node due to which the Perm has been inserted) has an output
+ constraint. If yes, pre-color the node accordingly else do nothing
+ since the node's input constraints are modelled by the Proj's
+ output constraint.
+
+ There's one subtle point here: If thenode has an output constraint
+ and the live range of some Proj ends at that node, we must give
+ that Proj the color of the constrained node. Otherwise the
+ available colors may not suffice for the rest of the projs.
+
+ 3) At last, color the Projs which have not been colored yet with the
+ left over colors.
+
+ So afterwards, everything including the constrained node will
+ be colored and the assign() phase can complete this coloring.
+ Note that therefore, we put the pre-colored nodes in a set
+ called pre_colored().
+
+ */
+static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
+{
+ be_chordal_env_t *env = alloc_env->chordal_env;
+ firm_dbg_module_t *dbg = env->dbg;
+ const arch_env_t *arch_env = env->main_env->arch_env;
+
+ pset *leftover = pset_new_ptr(8);
+ pset *pre_colored = pset_new_ptr(8);
+ bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
+ ir_node *irn, *cnstr, *last;
+ int has_cnstr = 0;
+
+ assert(be_is_Perm(perm));
+
+ DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
+
+ /*
+ * Color constrained Projs first.
+ */
+ for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn))
+ if(!try_pre_color(env, irn, pre_colored, colors_used))
+ pset_insert_ptr(leftover, irn);
+
+ cnstr = irn;
+ last = irn;
+
+ if(get_irn_mode(cnstr) == mode_T) {
+ for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn))
+ if(!try_pre_color(env, irn, pre_colored, colors_used))
+ pset_insert_ptr(leftover, irn);
+
+ last = sched_prev(irn);
+ }
+
+ else
+ try_pre_color(env, cnstr, pre_colored, colors_used);
+
+ pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
+
+ for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
+ const arch_register_t *reg;
+ ir_node *precol;
+ int colored = 0;
+
+ for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) {
+ const arch_register_t *pre_col_reg = arch_get_irn_register(arch_env, precol);
+
+ if(!values_interfere(irn, precol)) {
+ reg = arch_get_irn_register(arch_env, precol);
+ pset_break(pre_colored);
+ pset_remove_ptr(pre_colored, precol);
+ DBG((dbg, LEVEL_2, "non-interfering %+F setting to %s\n", irn, reg->name));
+ colored = 1;
+ break;
+ }
+ }
+
+ if(!colored) {
+ int col = bitset_next_clear(colors_used, 0);
+
+ assert(col >= 0 && col < env->cls->n_regs && "There must be a register left");
+ reg = arch_register_for_index(env->cls, col);
+
+ DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
+ }
+
+ arch_set_irn_register(arch_env, irn, reg);
+ pset_insert_ptr(alloc_env->pre_colored, irn);
+ bitset_set(colors_used, reg->index);
+ }
+
+ del_pset(leftover);
+ del_pset(pre_colored);
+
+ return last;
+}
+
+/**
+ * Handle constraint nodes in each basic block.
+ * be_insert_constr_perms() 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().
+ */
+static void constraints(ir_node *bl, void *data)
+{
+ be_chordal_alloc_env_t *env = data;
+ arch_env_t *arch_env = env->chordal_env->main_env->arch_env;
+ ir_node *irn;
+
+ for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
+ if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
+ irn = handle_constraints_at_perm(env, irn);
+ }