+
+static void extend_path(ilp_env_t *ienv, pdeq *path, ir_node *irn) {
+ be_ifg_t *ifg = ienv->co->cenv->ifg;
+ int i, len;
+ ir_node **curr_path;
+ affinity_node_t *aff;
+ neighb_t *nbr;
+
+ /* do not walk backwards or in circles */
+ if (pdeq_contains(path, irn))
+ return;
+
+ /* insert the new irn */
+ pdeq_putr(path, irn);
+
+
+
+ /* check for forbidden interferences */
+ len = pdeq_len(path);
+ curr_path = alloca(len * sizeof(*curr_path));
+ pdeq_copyl(path, (const void **)curr_path);
+
+ for (i=1; i<len; ++i)
+ if (be_ifg_connected(ifg, irn, curr_path[i]))
+ goto end;
+
+
+
+ /* check for terminating interference */
+ if (be_ifg_connected(ifg, irn, curr_path[0])) {
+
+ /* One node is not a path. */
+ /* And a path of length 2 is covered by a clique star constraint. */
+ if (len > 2) {
+ /* finally build the constraint */
+ int cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, 1.0);
+ for (i=1; i<len; ++i) {
+ char buf[16];
+ int nr_1 = get_irn_node_nr(curr_path[i-1]);
+ int nr_2 = get_irn_node_nr(curr_path[i]);
+ int var_idx = lpp_get_var_idx(ienv->lp, name_cdd_sorted(buf, 'y', nr_1, nr_2));
+ lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1.0);
+ }
+ }
+
+ /* this path cannot be extended anymore */
+ goto end;
+ }
+
+
+
+ /* recursively extend the path */
+ aff = get_affinity_info(ienv->co, irn);
+ co_gs_foreach_neighb(aff, nbr)
+ extend_path(ienv, path, nbr->irn);
+
+
+end:
+ /* remove the irn */
+ pdeq_getr(path);
+
+}
+