+static void solve_lpp(ir_nodeset_t *live_nodes, ir_node *node,
+ unsigned *forbidden_regs, unsigned *live_through_regs)
+{
+ unsigned *forbidden_edges = rbitset_malloc(n_regs * n_regs);
+ int *lpp_vars = XMALLOCNZ(int, n_regs*n_regs);
+ int arity = get_irn_arity(node);
+ int i;
+ unsigned l;
+ unsigned r;
+
+ lpp_t *lpp = lpp_new("prefalloc", lpp_minimize);
+ //lpp_set_time_limit(lpp, 20);
+ lpp_set_log(lpp, stdout);
+
+ /** mark some edges as forbidden */
+ for (i = 0; i < arity; ++i) {
+ ir_node *op = get_irn_n(node, i);
+ const arch_register_t *reg;
+ const arch_register_req_t *req;
+ const unsigned *limited;
+ unsigned current_reg;
+
+ if (!arch_irn_consider_in_reg_alloc(cls, op))
+ continue;
+
+ req = arch_get_irn_register_req_in(node, i);
+ if (!(req->type & arch_register_req_type_limited))
+ continue;
+
+ limited = req->limited;
+ reg = arch_get_irn_register(op);
+ current_reg = arch_register_get_index(reg);
+ for (r = 0; r < n_regs; ++r) {
+ if (rbitset_is_set(limited, r))
+ continue;
+
+ rbitset_set(forbidden_edges, current_reg*n_regs + r);
+ }
+ }
+
+ /* add all combinations, except for not allowed ones */
+ for (l = 0; l < n_regs; ++l) {
+ if (!rbitset_is_set(normal_regs, l)) {
+ char name[15];
+ snprintf(name, sizeof(name), "%u_to_%u", l, l);
+ lpp_vars[l*n_regs+l] = lpp_add_var(lpp, name, lpp_binary, 1);
+ continue;
+ }
+
+ for (r = 0; r < n_regs; ++r) {
+ if (!rbitset_is_set(normal_regs, r))
+ continue;
+ if (rbitset_is_set(forbidden_edges, l*n_regs + r))
+ continue;
+ /* livethrough values may not use constrained output registers */
+ if (rbitset_is_set(live_through_regs, l)
+ && rbitset_is_set(forbidden_regs, r))
+ continue;
+
+ char name[15];
+ snprintf(name, sizeof(name), "%u_to_%u", l, r);
+
+ double costs = l==r ? 9 : 8;
+ lpp_vars[l*n_regs+r]
+ = lpp_add_var(lpp, name, lpp_binary, costs);
+ assert(lpp_vars[l*n_regs+r] > 0);
+ }
+ }
+ /* add constraints */
+ for (l = 0; l < n_regs; ++l) {
+ int constraint;
+ /* only 1 destination per register */
+ constraint = -1;
+ for (r = 0; r < n_regs; ++r) {
+ int var = lpp_vars[l*n_regs+r];
+ if (var == 0)
+ continue;
+ if (constraint < 0) {
+ char name[64];
+ snprintf(name, sizeof(name), "%u_to_dest", l);
+ constraint = lpp_add_cst(lpp, name, lpp_equal, 1);
+ }
+ lpp_set_factor_fast(lpp, constraint, var, 1);
+ }
+ /* each destination used by at most 1 value */
+ constraint = -1;
+ for (r = 0; r < n_regs; ++r) {
+ int var = lpp_vars[r*n_regs+l];
+ if (var == 0)
+ continue;
+ if (constraint < 0) {
+ char name[64];
+ snprintf(name, sizeof(name), "one_to_%u", l);
+ constraint = lpp_add_cst(lpp, name, lpp_less_equal, 1);
+ }
+ lpp_set_factor_fast(lpp, constraint, var, 1);
+ }
+ }
+
+ lpp_dump_plain(lpp, fopen("lppdump.txt", "w"));
+
+ /* solve lpp */
+ {
+ ir_graph *irg = get_irn_irg(node);
+ be_options_t *options = be_get_irg_options(irg);
+ unsigned *assignment;
+ lpp_solve(lpp, options->ilp_server, options->ilp_solver);
+ if (!lpp_is_sol_valid(lpp))
+ panic("ilp solution not valid!");
+
+ assignment = ALLOCAN(unsigned, n_regs);
+ for (l = 0; l < n_regs; ++l) {
+ unsigned dest_reg = (unsigned)-1;
+ for (r = 0; r < n_regs; ++r) {
+ int var = lpp_vars[l*n_regs+r];
+ if (var == 0)
+ continue;
+ double val = lpp_get_var_sol(lpp, var);
+ if (val == 1) {
+ assert(dest_reg == (unsigned)-1);
+ dest_reg = r;
+ }
+ }
+ assert(dest_reg != (unsigned)-1);
+ assignment[dest_reg] = l;
+ }
+
+ fprintf(stderr, "Assignment: ");
+ for (l = 0; l < n_regs; ++l) {
+ fprintf(stderr, "%u ", assignment[l]);
+ }
+ fprintf(stderr, "\n");
+ fflush(stdout);
+ permute_values(live_nodes, node, assignment);
+ }
+ lpp_free(lpp);
+}
+
+static bool is_aligned(unsigned num, unsigned alignment)
+{
+ unsigned mask = alignment-1;
+ assert(is_po2(alignment));
+ return (num&mask) == 0;
+}
+