4 * @author Sebastian Hack
8 * Copyright (C) 2005 Universitaet Karlsruhe
9 * Released under the GPL
26 #include <lpp/lpp_net.h>
27 #include <lpp/lpp_cplex.h>
31 #include "besched_t.h"
36 #include "bespillilp.h"
40 #define MAX(a,b) ((a) > (b) ? (a) : (b))
42 #define DBG_LEVEL SET_LEVEL_4
49 #define LPP_SERVER "i44pc52"
50 #define LPP_SOLVER "cplex"
54 #define COST_REMAT (-9)
56 #define is_end_of_block_use(lr) (is_Block((lr)->user))
61 typedef struct _edge_reload_t {
66 struct _edge_reload_t *next;
69 typedef struct _spill_stat_t {
75 typedef struct _spill_ilp_t {
76 const arch_register_class_t *cls;
77 const be_main_session_env_t *session;
78 firm_dbg_module_t *dbg;
90 typedef struct _live_range_t live_range_t;
92 typedef struct _irn_use_head_t {
93 struct list_head head;
97 live_range_t *closest_use;
100 struct _live_range_t {
101 struct list_head list;
102 irn_use_head_t *use_head;
111 * Associates the first use of a live-in in a block
112 * with its live range.
114 typedef struct _first_use_t {
116 ir_node *irn; /**< A value live in at bl. */
117 live_range_t *lr; /**< The live range for the first use of irn in bl. */
122 static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
124 return arch_irn_has_reg_class(si->session->main_env->arch_env,
125 irn, arch_pos_make_out(0), si->cls);
128 static int cmp_live_range(const void *a, const void *b, size_t n)
130 const live_range_t *p = a;
131 const live_range_t *q = b;
133 return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
136 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
138 const irn_use_head_t *p = a;
139 const irn_use_head_t *q = b;
141 return !(p->irn == q->irn);
144 static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn)
146 irn_use_head_t templ;
147 templ.irn = (ir_node *) irn;
148 return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn));
151 static int cmp_first_use(const void *a, const void *b, size_t n)
153 const first_use_t *p = a;
154 const first_use_t *q = b;
156 return !(p->irn == q->irn && p->bl == q->bl);
159 static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
166 set_insert(si->first_uses, &templ, sizeof(templ),
167 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
170 static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
177 res = set_find(si->first_uses, &templ, sizeof(templ),
178 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
180 return res ? res->lr : NULL;
184 * Checks, if a vertain node can be recomputed at a certain position.
185 * @param si The spill ILP environment.
186 * @param irn The node to recompute.
187 * @param live The nodes live at the place where @p irn shall be
189 * @return 1, if irn can be recomputed, 0 if not.
191 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
194 const arch_env_t *arch_env = si->session->main_env->arch_env;
195 int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
197 for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
198 ir_node *op = get_irn_n(irn, i);
199 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
205 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
207 live_range_t lr, *res;
208 irn_use_head_t iuh, *head;
210 unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
216 lr.is_remat_var = -1;
218 res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
219 is_new = res->in_mem_var == -1;
223 ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
224 is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
225 res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0);
228 memset(&iuh, 0, sizeof(iuh));
231 head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
232 if(head->n_uses == -1) {
234 INIT_LIST_HEAD(&head->head);
238 list_add_tail(&res->list, &head->head);
242 res->use_head = head;
247 static ir_node *process_irn(spill_ilp_t *si, pset *live, ir_node *irn, int *demand)
250 int relevant_args = 0, results = 0;
252 DBG((si->dbg, LEVEL_1, "at %+F\n", irn));
254 while(is_Proj(irn)) {
255 if(has_reg_class(si, irn)) {
256 assert(pset_find_ptr(live, irn) && "node must be live");
257 pset_remove_ptr(live, irn);
261 DBG((si->dbg, LEVEL_1, "skipped proj %+F\n", irn));
262 irn = sched_prev(irn);
265 DBG((si->dbg, LEVEL_1, "\tlanded at irn %+F\n", irn));
268 assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
270 if(has_reg_class(si, irn)) {
271 assert( pset_find_ptr(live, irn) && "node must be live");
272 pset_remove_ptr(live, irn);
276 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
277 ir_node *op = get_irn_n(irn, i);
278 if(has_reg_class(si, op) && !pset_find_ptr(live, op)) {
280 DBG((si->dbg, LEVEL_1, "\trelevant arg %+F\n", op));
284 *demand = MAX(results, relevant_args);
285 DBG((si->dbg, LEVEL_1, "\tdemand: %d\n", *demand));
289 static void process_block(ir_node *bl, void *data)
293 spill_ilp_t *si = data;
295 int n_regs = arch_register_class_n_regs(si->cls);
296 int n_preds = get_irn_arity(bl);
297 pset *live = pset_new_ptr_default();
301 /* as always, bring the live end nodes to life here */
302 live_foreach(bl, li) {
303 if(live_is_end(li) && has_reg_class(si, li->irn)) {
304 ir_node *irn = (ir_node *) li->irn;
305 pset_insert_ptr(live, irn);
308 * The "user" of the live range to the end of a block
309 * is the block itself. This is quite arbitrary.
311 set_irn_link(irn, get_live_range(si, irn, bl, -1));
315 for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
322 /* We handle phi togther with live ins after this loop (see below). */
327 if(has_reg_class(si, irn))
328 pset_remove_ptr(live, irn);
330 demand = register_demand(si, live, irn);
331 n_live = pset_count(live);
334 irn = process_irn(si, live, irn, &demand);
335 n_live = pset_count(live);
338 * Determine, how many values (which are not used at the label)
340 * demand means the number of registers, the operation will consume.
341 * So there are n_regs - demand registers available to store values
342 * which are not used at this label. The rest must reside in memory.
344 must_be_in_mem = MAX(n_live + demand - n_regs, 0);
346 DBG((si->dbg, LEVEL_1, "%+F: demand: %d, live: %d, in mem: %d\n",
347 irn, demand, n_live, must_be_in_mem));
349 if(must_be_in_mem > 0) {
352 * The constraint limiting the pressure at this label to
353 * the number of free registers.
355 ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
356 cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
358 for(l = pset_first(live); l; l = pset_next(live)) {
359 live_range_t *lr = get_irn_link(l);
360 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
364 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
365 ir_node *op = get_irn_n(irn, i);
367 if(has_reg_class(si, op)) {
368 live_range_t *op_lr = get_live_range(si, op, irn, i);
370 set_irn_link(op, op_lr);
373 * The operand is reloaded at its usage, so it must not occur
374 * in the constraint which determines which values live at the
375 * instruction must reside in memory.
377 if(must_be_in_mem > 0)
378 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
381 * Check, if the node is a rematerializable node and
382 * if its operands are live here.
384 if(si->enable_remat && can_remat(si, op, live)) {
389 for(j = 0, n = get_irn_arity(op); j < n; ++j)
390 n_operands += has_reg_class(si, get_irn_n(op, j));
392 /* Make the remat constraint for this operand */
393 ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
394 cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
396 /* Make the rematerialize variable for the operand */
397 ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
398 op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
399 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
401 for(j = 0, n = get_irn_arity(op); j < n; ++j) {
402 ir_node *oop = get_irn_n(op, j);
403 if(has_reg_class(si, oop)) {
404 live_range_t *lr = get_irn_link(oop);
405 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
409 ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
410 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
411 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
412 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
417 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
418 ir_node *op = get_irn_n(irn, i);
419 if(has_reg_class(si, op) && !is_Phi(irn))
420 pset_insert_ptr(live, op);
426 if(bl == get_irg_start_block(get_irn_irg(bl)))
430 * Here, only the phis in the block and the values live in are in the
433 * If a value is live in, it must be in a register in all predecessor
434 * blocks or in memory at the end of all predecessor blocks. Also, the
435 * closest use in the current block must then be from register or
436 * memory, respectively.
438 for(irn = pset_first(live); irn; irn = pset_next(live)) {
439 live_range_t *lr = get_irn_link(irn);
440 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
443 /* Deprecated: Can be done with the first uses map */
445 lr->use_head->closest_use = lr;
448 * Remind the liverange of the first use of a live (or phi) in the
451 add_first_use(si, bl, irn, lr);
453 assert(has_reg_class(si, irn));
454 assert(is_Phi(irn) || is_live_in(bl, irn));
456 for(i = 0; i < n_preds; ++i) {
457 ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
458 ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn;
459 live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1);
460 edge_reload_t *edge = obstack_alloc(si->obst, sizeof(edge[0]));
462 ir_snprintf(buf, sizeof(buf), "edge_%N_%N_%N_%N",
463 bl, pred_bl, end_node, op_lr->irn);
464 edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD);
466 edge->irn = end_node;
470 ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N",
471 bl, pred_bl, end_node, op_lr->irn);
472 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
473 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
474 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
475 lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
485 * Add the costs for a store.
487 * If one of the uses is from memory, add additional costs for the
490 * m_1 + ... + m_n - M * s <= 0
492 * @param si The ILP spilling environment.
494 static void add_store_costs(spill_ilp_t *si)
498 double costs = si->enable_store ? COST_STORE : 0.0;
500 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
504 ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
505 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
507 ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
508 uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs);
509 lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
511 list_for_each_entry(live_range_t, lr, &uh->head, list)
512 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
516 static INLINE int is_zero(double x)
518 return fabs(x) < 0.00001;
521 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
523 return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
526 static int is_mem_phi(const ir_node *phi, void *data)
528 spill_ilp_t *si = data;
529 return is_spilled(si, get_use_head(si, phi)->closest_use);
533 static void writeback_results(spill_ilp_t *si)
538 /* Look at each node and examine the usages. */
539 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
542 /* Go through all live ranges of the node. */
543 list_for_each_entry(live_range_t, lr, &uh->head, list) {
544 if(is_spilled(si, lr) && !is_end_of_block_use(lr))
545 be_add_spill(si->senv, lr->irn, lr->user);
549 for(edge = si->edges; edge; edge = edge->next) {
550 if(!is_zero(edge->in_mem_var))
551 be_add_spill_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
554 be_insert_spills_reloads(si->senv, NULL, is_mem_phi, si);
557 void be_spill_ilp(const be_main_session_env_t *session_env,
558 const arch_register_class_t *cls)
560 char problem_name[256];
564 ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
567 si.session = session_env;
569 si.dbg = firm_dbg_register("be.ra.spillilp");
570 si.senv = be_new_spill_env(si.dbg, session_env, cls);
572 si.lpp = new_lpp(problem_name, lpp_minimize);
573 si.irn_use_heads = new_set(cmp_irn_use_head, 4096);
574 si.live_ranges = new_set(cmp_live_range, 16384);
575 si.first_uses = new_set(cmp_first_use, 4096);
580 firm_dbg_set_mask(si.dbg, DBG_LEVEL);
581 irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
583 add_store_costs(&si);
590 ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
591 if((f = fopen(buf, "wt")) != NULL) {
592 lpp_dump_plain(si.lpp, f);
598 DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
600 lpp_solve_cplex(si.lpp);
602 lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
604 assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
606 DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
607 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
608 DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
609 si.lpp->iterations, si.lpp->sol_time));
616 ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
617 if((f = fopen(buf, "wt")) != NULL) {
619 for(i = 0; i < si.lpp->var_next; ++i) {
620 lpp_name_t *name = si.lpp->vars[i];
621 fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
628 writeback_results(&si);
634 ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
635 if((f = fopen(buf, "wt")) != NULL) {
636 fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
637 fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
638 fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
639 fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
640 fprintf(f, "%20s: %d\n", "spills", si->stats.n_spills);
641 fprintf(f, "%20s: %d\n", "reloads", si->stats.n_reloads);
642 fprintf(f, "%20s: %d\n", "remats", si->stats.n_remat);
648 del_set(si.irn_use_heads);
649 del_set(si.live_ranges);
651 obstack_free(&obst, NULL);