+/**
+ * Build a ring of phis for each block in the link field.
+ * @param env The chordal env.
+ */
+static INLINE void build_phi_rings(be_chordal_env_t *env)
+{
+ irg_walk_graph(env->irg, clear_link, collect_phis, env);
+}
+
+/**
+ * This struct represents a Proj for a Perm.
+ * It records the argument in the Perm and the corresponding Proj of the
+ * Perm.
+ */
+typedef struct {
+ ir_node *arg; /**< The phi argument to make the Proj for. */
+ int pos; /**< The proj number the Proj will get.
+ This also denotes the position of @p arg
+ in the in array of the Perm. */
+ ir_node *proj; /**< The proj created for @p arg. */
+} perm_proj_t;
+
+static int cmp_perm_proj(const void *a, const void *b, size_t n)
+{
+ const perm_proj_t *p = a;
+ const perm_proj_t *q = b;
+ return !(p->arg == q->arg);
+}
+
+static void insert_all_perms_walker(ir_node *bl, void *data)
+{
+ be_chordal_env_t *chordal_env = data;
+ pmap *perm_map = chordal_env->data;
+ ir_graph *irg = chordal_env->irg;
+ const be_node_factory_t *fact = chordal_env->main_env->node_factory;
+
+ /* Dummy targets for the projs */
+ ir_node *dummy = new_rd_Unknown(irg, mode_T);
+
+ assert(is_Block(bl));
+
+ /* If the link flag is NULL, this block has no phis. */
+ if(get_irn_link(bl)) {
+ int i, n;
+
+ /* Look at all predecessors of the phi block */
+ for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
+ ir_node *phi, *perm, *insert_after, **in;
+ perm_proj_t *pp;
+
+ set *arg_set = new_set(cmp_perm_proj, chordal_env->cls->n_regs);
+ ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
+ int n_projs = 0;
+
+ assert(!pmap_contains(perm_map, pred_bl) && "Already permed that block");
+
+ /*
+ * Note that all phis in the list are in the same register class
+ * by construction.
+ */
+ for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
+ perm_proj_t templ;
+ ir_node *arg = get_irn_n(phi, i);
+ unsigned hash = HASH_PTR(arg);
+
+ templ.arg = arg;
+ pp = set_find(arg_set, &templ, sizeof(templ), hash);
+
+ /*
+ * If a proj_perm_t entry has not been made in the argument set,
+ * create one. The only restriction is, that the phi argument
+ * mey not be live in at the current block, since this argument
+ * interferes with the phi and must thus not be member of a
+ * Perm. A copy will be inserted for this argument alter on.
+ */
+ if(!pp && !is_live_in(bl, arg)) {
+ templ.pos = n_projs++;
+ set_insert(arg_set, &templ, sizeof(templ), hash);
+ }
+ }
+
+ /*
+ * set the in array of the Perm to the arguments of the phis
+ * recorded above
+ */
+ in = malloc(n_projs * sizeof(in[0]));
+ for(pp = set_first(arg_set); pp; pp = set_next(arg_set))
+ in[pp->pos] = pp->arg;
+
+ perm = new_Perm(fact, chordal_env->cls, irg, pred_bl, n_projs, in);
+ insert_after = sched_skip(sched_last(pred_bl), 0, sched_skip_cf_predicator,
+ chordal_env->main_env->arch_env);
+ sched_add_after(insert_after, perm);
+ exchange(dummy, perm);
+
+ /*
+ * Make the Projs for the Perm.
+ * register allocation is copied form former phi arguments
+ * to the projs (new phi arguments)
+ */
+ for(pp = set_first(arg_set); pp; pp = set_next(arg_set)) {
+ pp->proj = new_r_Proj(irg, pred_bl, perm, get_irn_mode(pp->arg), pp->pos);
+ set_reg(pp->proj, get_reg(pp->arg));
+ DBG((dbg, LEVEL_2, "Copy register assignment %s from %+F to %+F\n",
+ get_reg(pp->arg)->name, pp->arg, pp->proj));
+ }
+
+ /*
+ * Set the phi nodes to their new arguments: The Projs of the Perm
+ */
+ for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
+ perm_proj_t templ;
+
+ templ.arg = get_irn_n(phi, i);
+ pp = set_find(arg_set, &templ, sizeof(templ), HASH_PTR(templ.arg));