4 * @author Sebastian Hack
8 * Copyright (C) 2005 Universitaet Karlsruhe
9 * Released under the GPL
33 #include <lpp/lpp_net.h>
34 #include <lpp/lpp_cplex.h>
38 #include "besched_t.h"
43 #include "bespillilp.h"
46 #include "bechordal_t.h"
50 #define MAX(a,b) ((a) > (b) ? (a) : (b))
52 #define DBG_LEVEL SET_LEVEL_0 // 3
59 #define LPP_SERVER "i44pc52"
60 #define LPP_SOLVER "cplex"
64 #define COST_REMAT (-9)
66 #define is_end_of_block_use(lr) (is_Block((lr)->user))
71 typedef struct _edge_reload_t {
76 struct _edge_reload_t *next;
79 typedef struct _spill_stat_t {
85 typedef struct _spill_ilp_t {
87 const arch_register_class_t *cls;
88 const be_chordal_env_t *chordal_env;
98 DEBUG_ONLY(firm_dbg_module_t *dbg;)
101 typedef struct _live_range_t live_range_t;
103 typedef struct _irn_use_head_t {
104 struct list_head head;
108 live_range_t *closest_use;
111 struct _live_range_t {
112 struct list_head list;
113 irn_use_head_t *use_head;
122 * Associates the first use of a live-in in a block
123 * with its live range.
125 typedef struct _first_use_t {
127 ir_node *irn; /**< A value live in at bl. */
128 live_range_t *lr; /**< The live range for the first use of irn in bl. */
133 * Get weight for spill/reload costs
134 * Actually computed with loop depth.
135 * @param irn The location where to check for the weights.
136 * @return The weights at this points.
138 static double get_weight(const ir_node *irn)
140 ir_loop *loop = get_irn_loop((ir_node *) irn);
144 int depth = get_loop_depth(loop);
145 res += depth * depth;
152 static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
154 return chordal_has_class(si->chordal_env, irn);
157 static int cmp_live_range(const void *a, const void *b, size_t n)
159 const live_range_t *p = a;
160 const live_range_t *q = b;
162 return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
165 static int cmp_irn_use_head(const void *a, const void *b, size_t n)
167 const irn_use_head_t *p = a;
168 const irn_use_head_t *q = b;
170 return !(p->irn == q->irn);
173 static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn)
175 irn_use_head_t templ;
176 templ.irn = (ir_node *) irn;
177 return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn));
180 static int cmp_first_use(const void *a, const void *b, size_t n)
182 const first_use_t *p = a;
183 const first_use_t *q = b;
185 return !(p->irn == q->irn && p->bl == q->bl);
188 static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
195 set_insert(si->first_uses, &templ, sizeof(templ),
196 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
199 static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
206 res = set_find(si->first_uses, &templ, sizeof(templ),
207 HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
209 return res ? res->lr : NULL;
213 * Checks, if a vertain node can be recomputed at a certain position.
214 * @param si The spill ILP environment.
215 * @param irn The node to recompute.
216 * @param live The nodes live at the place where @p irn shall be
218 * @return 1, if irn can be recomputed, 0 if not.
220 static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
223 const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
224 int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
226 for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
227 ir_node *op = get_irn_n(irn, i);
228 remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
234 static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
236 live_range_t lr, *res;
237 irn_use_head_t iuh, *head;
239 unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
245 lr.is_remat_var = -1;
247 res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
248 is_new = res->in_mem_var == -1;
255 cost = get_weight(user) * COST_LOAD;
257 ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
258 is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
259 res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, cost);
262 memset(&iuh, 0, sizeof(iuh));
265 head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
266 if(head->n_uses == -1) {
268 INIT_LIST_HEAD(&head->head);
272 list_add_tail(&res->list, &head->head);
276 res->use_head = head;
281 static void print_live_set(spill_ilp_t *si, pset *s) {
283 for(n=pset_first(s); n; n=pset_next(s))
284 DBG((si->dbg, LEVEL_3, " %+F\n", n));
287 static void process_block(ir_node *bl, void *data)
291 spill_ilp_t *si = data;
293 int n_regs = arch_register_class_n_regs(si->cls);
294 int n_preds = get_irn_arity(bl);
295 pset *live = pset_new_ptr_default();
299 DBG((si->dbg, LEVEL_3, "\n"));
300 DBG((si->dbg, LEVEL_3, "Processing %+F\n", bl));
303 * Get all live-end values of this block
305 live_foreach(bl, li) {
306 if(live_is_end(li) && has_reg_class(si, li->irn)) {
307 ir_node *irn = (ir_node *) li->irn;
308 pset_insert_ptr(live, irn);
310 /*The "user" of the live range to the end of a block
311 * is the block itself. This is quite arbitrary. */
312 set_irn_link(irn, get_live_range(si, irn, bl, -1));
315 DBG((si->dbg, LEVEL_3, "Live-End:\n"));
316 print_live_set(si, live);
319 * Walk through the schedule of this block from end to begin.
320 * Phis are handled togther with live ins after this loop.
322 for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
325 int relevant_args, results;
332 * Determine the number of results
334 /* Special handling of Projs */
336 if(has_reg_class(si, irn)) {
337 assert(pset_find_ptr(live, irn) && "node must be live");
338 pset_remove_ptr(live, irn);
342 DBG((si->dbg, LEVEL_2, "Skipped %+F\n", irn));
346 DBG((si->dbg, LEVEL_1, "Irn %+F\n", irn));
349 assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
354 if(has_reg_class(si, irn)) {
355 assert(get_irn_mode(irn) != mode_T && "node must not be a tuple");
356 assert(pset_find_ptr(live, irn) && "node must be live");
357 pset_remove_ptr(live, irn);
364 /* cand holds the irns which may be spilled */
365 cand = pset_new_ptr(8);
366 for(l=pset_first(live); l; l=pset_next(live))
367 pset_insert_ptr(cand, l);
370 * Determine number of arguments
373 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
374 ir_node *op = get_irn_n(irn, i);
375 if(has_reg_class(si, op)) {
376 DBG((si->dbg, LEVEL_2, " arg %+F\n", op));
379 /* arguments must not be spilled */
380 if(pset_find_ptr(cand, op))
381 pset_remove_ptr(cand, op);
386 * Determine, how many values must be in memory.
387 * We have 'n_regs' registers.
388 * The instr. needs 'demand'.
389 * So (R:= n_regs - demand) registers can be used for candidates 'cand'.
390 * The rest (M:= n_cand - R) must reside in memory.
392 demand = MAX(results, relevant_args);
393 n_cand = pset_count(cand);
394 must_be_in_mem = n_cand - (n_regs - demand);
396 DBG((si->dbg, LEVEL_1, " Demand: %d, Cands: %d, InMem: %d\n", demand, n_cand, must_be_in_mem));
397 DBG((si->dbg, LEVEL_3, " Cand-Set:\n"));
398 print_live_set(si, cand);
401 * Generate the corresponding constraint spilling
402 * enough candidates at this label.
404 if(must_be_in_mem > 0) {
405 ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
406 cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
408 for(l = pset_first(cand); l; l = pset_next(cand)) {
409 live_range_t *lr = get_irn_link(l);
410 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
414 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
415 ir_node *op = get_irn_n(irn, i);
417 if(has_reg_class(si, op)) {
418 live_range_t *op_lr = get_live_range(si, op, irn, i);
419 set_irn_link(op, op_lr);
423 * The operand is reloaded at its usage, so it must not occur
424 * in the constraint which determines which values live at the
425 * instruction must reside in memory.
427 if(must_be_in_mem > 0) {
428 DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
429 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
434 * Check, if the node is a rematerializable node and
435 * if its operands are live here.
437 if(si->enable_remat && can_remat(si, op, live)) {
442 for(j = 0, n = get_irn_arity(op); j < n; ++j)
443 n_operands += has_reg_class(si, get_irn_n(op, j));
445 /* Make the remat constraint for this operand */
446 ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
447 cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
449 /* Make the rematerialize variable for the operand */
450 ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
451 op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
452 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
454 for(j = 0, n = get_irn_arity(op); j < n; ++j) {
455 ir_node *oop = get_irn_n(op, j);
456 if(has_reg_class(si, oop)) {
457 live_range_t *lr = get_irn_link(oop);
458 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
462 ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
463 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
464 lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
465 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
471 * Insert arguments of current instr into the live set
473 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
474 ir_node *op = get_irn_n(irn, i);
475 if(has_reg_class(si, op))
476 pset_insert_ptr(live, op);
483 if(bl == get_irg_start_block(get_irn_irg(bl)))
487 * Here, the live set contains
488 * - phis of the block
489 * - live-in values of the block
491 * TODO: comment is wrong
492 * If a value is live in, it must be in a register in all predecessor
493 * blocks or in memory at the end of all predecessor blocks. Also, the
494 * closest use in the current block must then be from register or
495 * memory, respectively.
497 for(irn = pset_first(live); irn; irn = pset_next(live)) {
498 live_range_t *lr = get_irn_link(irn);
499 int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
502 assert(has_reg_class(si, irn));
503 assert(is_Phi(irn) || is_live_in(bl, irn));
505 /* Deprecated: Can be done with the first uses map */
507 lr->use_head->closest_use = lr;
510 * Remind the liverange of the first use of a live (or phi) in the
513 add_first_use(si, bl, irn, lr);
515 for(i = 0; i < n_preds; ++i) {
516 ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
517 ir_node *end_node = is_phi ? get_irn_n(irn, i) : irn;
518 live_range_t *op_lr = get_live_range(si, end_node, pred_bl, -1);
519 edge_reload_t *edge = obstack_alloc(si->obst, sizeof(edge[0]));
521 ir_snprintf(buf, sizeof(buf), "edge_b%N_p%N_i%N", bl, pred_bl, end_node);
522 edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, get_weight(pred_bl) * COST_LOAD);
524 edge->irn = end_node;
526 edge->next = si->edges;
529 ir_snprintf(buf, sizeof(buf), "cedge_b%N_p%N_i%N", bl, pred_bl, end_node);
530 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
531 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
532 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
533 lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
542 * Add the costs for a store.
544 * If one of the uses is from memory, add additional costs for the
547 * m_1 + ... + m_n - M * s <= 0
549 * @param si The ILP spilling environment.
551 static void add_store_costs(spill_ilp_t *si)
553 if(si->enable_store) {
557 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
561 ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
562 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
564 ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
565 uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary,
566 get_weight(uh->irn) * COST_STORE);
567 lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
569 list_for_each_entry(live_range_t, lr, &uh->head, list)
570 lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
575 static INLINE int is_zero(double x)
577 return fabs(x) < 0.00001;
580 static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
582 return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
585 static int is_mem_phi(const ir_node *phi, void *data)
587 spill_ilp_t *si = data;
588 return is_spilled(si, get_use_head(si, phi)->closest_use);
591 static void writeback_results(spill_ilp_t *si)
596 /* Look at each node and examine the usages. */
597 for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
600 si->stats.n_spills += !is_zero(lpp_get_var_sol(si->lpp, uh->spill_var));
602 /* Go through all live ranges of the node. */
603 list_for_each_entry(live_range_t, lr, &uh->head, list) {
604 if(is_spilled(si, lr) && !is_end_of_block_use(lr)) {
605 DBG((si->dbg, LEVEL_2, "%+F: inserting reload at user %+F\n",
607 be_add_reload(si->senv, lr->irn, lr->user);
608 si->stats.n_reloads += 1;
613 for(edge = si->edges; edge; edge = edge->next) {
614 if(!is_zero(lpp_get_var_sol(si->lpp, edge->in_mem_var))) {
615 DBG((si->dbg, LEVEL_2, "%+F: insert reload on edge %d from %+F\n",
616 edge->irn, edge->pos, edge->bl));
617 be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
618 si->stats.n_reloads += 1;
622 be_insert_spills_reloads(si->senv, NULL);
625 void be_spill_ilp(const be_chordal_env_t *chordal_env)
627 char problem_name[256];
631 ir_snprintf(problem_name, sizeof(problem_name), "%F_%s",
632 chordal_env->irg, chordal_env->cls->name);
635 memset(&si.stats, 0, sizeof(si.stats));
636 si.chordal_env = chordal_env;
638 si.senv = be_new_spill_env(chordal_env, is_mem_phi, &si);
639 DEBUG_ONLY(si.senv->dbg = si.dbg;)
640 si.cls = chordal_env->cls;
641 si.lpp = new_lpp(problem_name, lpp_minimize);
642 si.irn_use_heads = new_set(cmp_irn_use_head, 4096);
643 si.live_ranges = new_set(cmp_live_range, 16384);
644 si.first_uses = new_set(cmp_first_use, 4096);
648 FIRM_DBG_REGISTER(si.dbg, "firm.be.ra.spillilp");
650 irg_block_walk_graph(chordal_env->irg, process_block, NULL, &si);
652 add_store_costs(&si);
659 ir_snprintf(buf, sizeof(buf), "%s-spill.ilp", problem_name);
660 if((f = fopen(buf, "wt")) != NULL) {
661 lpp_dump_plain(si.lpp, f);
667 DBG((si.dbg, LEVEL_1, "%F\n", chordal_env->irg));
669 lpp_solve_cplex(si.lpp);
671 lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
673 assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
675 DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
676 set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
677 DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
678 si.lpp->iterations, si.lpp->sol_time));
685 ir_snprintf(buf, sizeof(buf), "%s-spill.sol", problem_name);
686 if((f = fopen(buf, "wt")) != NULL) {
688 for(i = 0; i < si.lpp->var_next; ++i) {
689 lpp_name_t *name = si.lpp->vars[i];
690 fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
697 writeback_results(&si);
704 ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
705 if((f = fopen(buf, "wt")) != NULL) {
706 fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
707 fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
708 fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
709 fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
710 fprintf(f, "%20s: %d\n", "spills", si.stats.n_spills);
711 fprintf(f, "%20s: %d\n", "reloads", si.stats.n_reloads);
712 fprintf(f, "%20s: %d\n", "remats", si.stats.n_remat);
718 del_set(si.irn_use_heads);
719 del_set(si.live_ranges);
721 obstack_free(&obst, NULL);
726 static void only_that_you_can_compile_without_WITH_ILP_defined(void) {
729 #endif /* WITH_ILP */