4 * @author Sebastian Hack
8 * Copyright (C) 2005 Universitaet Karlsruhe
9 * Released under the GPL
27 #include <lpp/lpp_net.h>
28 #include <lpp/lpp_cplex.h>
32 #include "besched_t.h"
37 #include "bespillilp.h"
41 #define MAX(a,b) ((a) > (b) ? (a) : (b))
43 #define DBG_LEVEL SET_LEVEL_0 // 3
50 #define LPP_SERVER "i44pc52"
51 #define LPP_SOLVER "cplex"
55 #define COST_REMAT (-9)
57 #define is_end_of_block_use(lr) (is_Block((lr)->user))
62 typedef struct _edge_reload_t {
67 struct _edge_reload_t *next;
70 typedef struct _spill_stat_t {
76 typedef struct _spill_ilp_t {
78 const arch_register_class_t *cls;
79 const be_main_session_env_t *session;
80 firm_dbg_module_t *dbg;
92 typedef struct _live_range_t live_range_t;
94 typedef struct _irn_use_head_t {
95 struct list_head head;
99 live_range_t *closest_use;
102 struct _live_range_t {
103 struct list_head list;
104 irn_use_head_t *use_head;
113 * Associates the first use of a live-in in a block
114 * with its live range.
116 typedef struct _first_use_t {
118 ir_node *irn; /**< A value live in at bl. */
119 live_range_t *lr; /**< The live range for the first use of irn in bl. */
124 * Get weight for spill/reload costs
125 * Actually computed with loop depth.
126 * @param irn The location where to check for the weights.
127 * @return The weights at this points.
129 static double get_weight(const ir_node *irn)
131 ir_loop *loop = get_irn_loop((ir_node *) irn);
135 int depth = get_loop_depth(loop);
136 res += depth * depth;
138 // ir_printf("%+F has loop depth %d\n", irn, depth);
145 static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
147 return arch_irn_has_reg_class(si->session->main_env->arch_env,
148 irn, arch_pos_make_out(0), si->cls);
151 static int cmp_live_range(const void *a, const void *b, size_t n)
153 const live_range_t *p = a;
154 const live_range_t *q = b;
156 return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
159 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
161 const irn_use_head_t *p = a;
162 const irn_use_head_t *q = b;
164 return !(p->irn == q->irn);
167 static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn)
169 irn_use_head_t templ;
170 templ.irn = (ir_node *) irn;
171 return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn));
174 static int cmp_first_use(const void *a, const void *b, size_t n)
176 const first_use_t *p = a;
177 const first_use_t *q = b;
179 return !(p->irn == q->irn && p->bl == q->bl);
182 static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
189 set_insert(si->first_uses, &templ, sizeof(templ),
190 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
193 static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
200 res = set_find(si->first_uses, &templ, sizeof(templ),
201 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
203 return res ? res->lr : NULL;
207 * Checks, if a vertain node can be recomputed at a certain position.
208 * @param si The spill ILP environment.
209 * @param irn The node to recompute.
210 * @param live The nodes live at the place where @p irn shall be
212 * @return 1, if irn can be recomputed, 0 if not.
214 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
217 const arch_env_t *arch_env = si->session->main_env->arch_env;
218 int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
220 for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
221 ir_node *op = get_irn_n(irn, i);
222 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
228 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
230 live_range_t lr, *res;
231 irn_use_head_t iuh, *head;
233 unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
239 lr.is_remat_var = -1;
241 res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
242 is_new = res->in_mem_var == -1;
249 cost = get_weight(user) * COST_LOAD;
251 ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
252 is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
253 res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, cost);
256 memset(&iuh, 0, sizeof(iuh));
259 head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
260 if(head->n_uses == -1) {
262 INIT_LIST_HEAD(&head->head);
266 list_add_tail(&res->list, &head->head);
270 res->use_head = head;
275 static void print_live_set(spill_ilp_t *si, pset *s) {
277 for(n=pset_first(s); n; n=pset_next(s))
278 DBG((si->dbg, LEVEL_3, " %+F\n", n));
281 static void process_block(ir_node *bl, void *data)
285 spill_ilp_t *si = data;
287 int n_regs = arch_register_class_n_regs(si->cls);
288 int n_preds = get_irn_arity(bl);
289 pset *live = pset_new_ptr_default();
293 DBG((si->dbg, LEVEL_3, "\n"));
294 DBG((si->dbg, LEVEL_3, "Processing %+F\n", bl));
297 * Get all live-end values of this block
299 live_foreach(bl, li) {
300 if(live_is_end(li) && has_reg_class(si, li->irn)) {
301 ir_node *irn = (ir_node *) li->irn;
302 pset_insert_ptr(live, irn);
304 /*The "user" of the live range to the end of a block
305 * is the block itself. This is quite arbitrary. */
306 set_irn_link(irn, get_live_range(si, irn, bl, -1));
309 DBG((si->dbg, LEVEL_3, "Live-End:\n"));
310 print_live_set(si, live);
313 * Walk through the schedule of this block from end to begin.
314 * Phis are handled togther with live ins after this loop.
316 for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
319 int relevant_args, results;
326 * Determine the number of results
328 /* Special handling of Projs */
330 if(has_reg_class(si, irn)) {
331 assert(pset_find_ptr(live, irn) && "node must be live");
332 pset_remove_ptr(live, irn);
336 DBG((si->dbg, LEVEL_2, "Skipped %+F\n", irn));
340 DBG((si->dbg, LEVEL_1, "Irn %+F\n", irn));
343 assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
348 if(has_reg_class(si, irn)) {
349 assert(get_irn_mode(irn) != mode_T && "node must not be a tuple");
350 assert(pset_find_ptr(live, irn) && "node must be live");
351 pset_remove_ptr(live, irn);
358 /* cand holds the irns which may be spilled */
359 cand = pset_new_ptr(8);
360 for(l=pset_first(live); l; l=pset_next(live))
361 pset_insert_ptr(cand, l);
364 * Determine number of arguments
367 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
368 ir_node *op = get_irn_n(irn, i);
369 if(has_reg_class(si, op)) {
370 DBG((si->dbg, LEVEL_2, " arg %+F\n", op));
373 /* arguments must not be spilled */
374 if(pset_find_ptr(cand, op))
375 pset_remove_ptr(cand, op);
380 * Determine, how many values must be in memory.
381 * We have 'n_regs' registers.
382 * The instr. needs 'demand'.
383 * So (R:= n_regs - demand) registers can be used for candidates 'cand'.
384 * The rest (M:= n_cand - R) must reside in memory.
386 demand = MAX(results, relevant_args);
387 n_cand = pset_count(cand);
388 must_be_in_mem = n_cand - (n_regs - demand);
390 DBG((si->dbg, LEVEL_1, " Demand: %d, Cands: %d, InMem: %d\n", demand, n_cand, must_be_in_mem));
391 DBG((si->dbg, LEVEL_3, " Cand-Set:\n"));
392 print_live_set(si, cand);
395 * Generate the corresponding constraint spilling
396 * enough candidates at this label.
398 if(must_be_in_mem > 0) {
399 ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
400 cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
402 for(l = pset_first(cand); l; l = pset_next(cand)) {
403 live_range_t *lr = get_irn_link(l);
404 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
408 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
409 ir_node *op = get_irn_n(irn, i);
411 if(has_reg_class(si, op)) {
412 live_range_t *op_lr = get_live_range(si, op, irn, i);
413 set_irn_link(op, op_lr);
417 * The operand is reloaded at its usage, so it must not occur
418 * in the constraint which determines which values live at the
419 * instruction must reside in memory.
421 if(must_be_in_mem > 0) {
422 DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
423 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
428 * Check, if the node is a rematerializable node and
429 * if its operands are live here.
431 if(si->enable_remat && can_remat(si, op, live)) {
436 for(j = 0, n = get_irn_arity(op); j < n; ++j)
437 n_operands += has_reg_class(si, get_irn_n(op, j));
439 /* Make the remat constraint for this operand */
440 ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
441 cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
443 /* Make the rematerialize variable for the operand */
444 ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
445 op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
446 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
448 for(j = 0, n = get_irn_arity(op); j < n; ++j) {
449 ir_node *oop = get_irn_n(op, j);
450 if(has_reg_class(si, oop)) {
451 live_range_t *lr = get_irn_link(oop);
452 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
456 ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
457 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
458 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
459 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
465 * Insert arguments of current instr into the live set
467 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
468 ir_node *op = get_irn_n(irn, i);
469 if(has_reg_class(si, op))
470 pset_insert_ptr(live, op);
477 if(bl == get_irg_start_block(get_irn_irg(bl)))
481 * Here, the live set contains
482 * - phis of the block
483 * - live-in values of the block
485 * TODO: comment is wrong
486 * If a value is live in, it must be in a register in all predecessor
487 * blocks or in memory at the end of all predecessor blocks. Also, the
488 * closest use in the current block must then be from register or
489 * memory, respectively.
491 for(irn = pset_first(live); irn; irn = pset_next(live)) {
492 live_range_t *lr = get_irn_link(irn);
493 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
496 assert(has_reg_class(si, irn));
497 assert(is_Phi(irn) || is_live_in(bl, irn));
499 /* Deprecated: Can be done with the first uses map */
501 lr->use_head->closest_use = lr;
504 * Remind the liverange of the first use of a live (or phi) in the
507 add_first_use(si, bl, irn, lr);
509 for(i = 0; i < n_preds; ++i) {
510 ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
511 ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn;
512 live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1);
513 edge_reload_t *edge = obstack_alloc(si->obst, sizeof(edge[0]));
515 ir_snprintf(buf, sizeof(buf), "edge_b%N_p%N_i%N", bl, pred_bl, end_node);
516 edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, get_weight(pred_bl) * COST_LOAD);
518 edge->irn = end_node;
520 edge->next = si->edges;
523 ir_snprintf(buf, sizeof(buf), "cedge_b%N_p%N_i%N", bl, pred_bl, end_node);
524 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
525 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
526 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
527 lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
536 * Add the costs for a store.
538 * If one of the uses is from memory, add additional costs for the
541 * m_1 + ... + m_n - M * s <= 0
543 * @param si The ILP spilling environment.
545 static void add_store_costs(spill_ilp_t *si)
547 if(si->enable_store) {
551 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
555 ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
556 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
558 ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
559 uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary,
560 get_weight(uh->irn) * COST_STORE);
561 lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
563 list_for_each_entry(live_range_t, lr, &uh->head, list)
564 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
569 static INLINE int is_zero(double x)
571 return fabs(x) < 0.00001;
574 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
576 return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
579 static int is_mem_phi(const ir_node *phi, void *data)
581 spill_ilp_t *si = data;
582 return is_spilled(si, get_use_head(si, phi)->closest_use);
585 static void writeback_results(spill_ilp_t *si)
590 /* Look at each node and examine the usages. */
591 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
594 si->stats.n_spills += !is_zero(lpp_get_var_sol(si->lpp, uh->spill_var));
596 /* Go through all live ranges of the node. */
597 list_for_each_entry(live_range_t, lr, &uh->head, list) {
598 if(is_spilled(si, lr) && !is_end_of_block_use(lr)) {
599 DBG((si->dbg, LEVEL_2, "%+F: inserting reload at user %+F\n",
601 be_add_reload(si->senv, lr->irn, lr->user);
602 si->stats.n_reloads += 1;
607 for(edge = si->edges; edge; edge = edge->next) {
608 if(!is_zero(lpp_get_var_sol(si->lpp, edge->in_mem_var))) {
609 DBG((si->dbg, LEVEL_2, "%+F: insert reload on edge %d from %+F\n",
610 edge->irn, edge->pos, edge->bl));
611 be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
612 si->stats.n_reloads += 1;
616 be_insert_spills_reloads(si->senv, NULL);
619 void be_spill_ilp(const be_main_session_env_t *session_env,
620 const arch_register_class_t *cls)
622 char problem_name[256];
626 ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
629 memset(&si.stats, 0, sizeof(si.stats));
630 si.session = session_env;
632 si.dbg = firm_dbg_register("be.ra.spillilp");
633 si.senv = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si);
635 si.lpp = new_lpp(problem_name, lpp_minimize);
636 si.irn_use_heads = new_set(cmp_irn_use_head, 4096);
637 si.live_ranges = new_set(cmp_live_range, 16384);
638 si.first_uses = new_set(cmp_first_use, 4096);
643 firm_dbg_set_mask(si.dbg, DBG_LEVEL);
644 irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
646 add_store_costs(&si);
653 ir_snprintf(buf, sizeof(buf), "%s-spill.ilp", problem_name);
654 if((f = fopen(buf, "wt")) != NULL) {
655 lpp_dump_plain(si.lpp, f);
661 DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
663 lpp_solve_cplex(si.lpp);
665 lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
667 assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
669 DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
670 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
671 DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
672 si.lpp->iterations, si.lpp->sol_time));
679 ir_snprintf(buf, sizeof(buf), "%s-spill.sol", problem_name);
680 if((f = fopen(buf, "wt")) != NULL) {
682 for(i = 0; i < si.lpp->var_next; ++i) {
683 lpp_name_t *name = si.lpp->vars[i];
684 fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
691 writeback_results(&si);
698 ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
699 if((f = fopen(buf, "wt")) != NULL) {
700 fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
701 fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
702 fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
703 fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
704 fprintf(f, "%20s: %d\n", "spills", si.stats.n_spills);
705 fprintf(f, "%20s: %d\n", "reloads", si.stats.n_reloads);
706 fprintf(f, "%20s: %d\n", "remats", si.stats.n_remat);
712 del_set(si.irn_use_heads);
713 del_set(si.live_ranges);
715 obstack_free(&obst, NULL);