1 /** vim: set sw=4 ts=4:
4 * @author Adam M. Szalkowski & Sebastian Hack
6 * ILP based spilling & rematerialization
8 * Copyright (C) 2006 Universitaet Karlsruhe
9 * Released under the GPL
36 #include <lpp/lpp_net.h>
37 #include <lpp/lpp_cplex.h>
38 //#include <lc_pset.h>
39 #include <libcore/lc_bitset.h>
43 #include "besched_t.h"
48 #include "bespillremat.h"
51 #include "bechordal_t.h"
58 #define COLLECT_REMATS
59 #define REMAT_WHILE_LIVE
60 #define NO_ENLARGE_L1V3N355
61 #define EXECFREQ_LOOPDEPH
62 #define MAY_DIE_AT_PRE_REMAT
66 #define LPP_SERVER "i44pc52"
67 #define LPP_SOLVER "cplex"
73 #define ILP_TIMEOUT 20
77 typedef struct _spill_ilp_t {
78 const arch_register_class_t *cls;
80 const be_chordal_env_t *chordal_env;
85 pset *all_possible_remats;
89 set *values; /**< for collecting all definitions of values before running ssa-construction */
90 #ifndef EXECFREQ_LOOPDEPH
93 DEBUG_ONLY(firm_dbg_module_t * dbg);
96 typedef int ilp_var_t;
97 typedef int ilp_cst_t;
99 typedef struct _spill_bb_t {
105 typedef struct _remat_t {
106 const ir_node *op; /**< for copy_irn */
107 const ir_node *proj; /**< not NULL if the above op produces a tuple */
108 const ir_node *value; /**< the value which is being recomputed by this remat */
109 int cost; /**< cost of this remat */
113 * Data to be attached to each IR node. For remats this contains the ilp_var
114 * for this remat and for normal ops this contains the ilp_vars for
115 * reloading each operand
117 typedef struct _op_t {
122 remat_t *remat; /** the remat this op belongs to */
123 int pre; /** 1, if this is a pressure-increasing remat */
127 ir_node *op; /** the operation this live range belongs to */
133 typedef struct _defs_t {
135 ir_node *spills; /**< points to the first spill for this value (linked by link field) */
136 ir_node *remats; /**< points to the first definition for this value (linked by link field) */
139 typedef struct _remat_info_t {
140 const ir_node *irn; /**< the irn to which these remats belong */
141 pset *remats; /**< possible remats for this value */
142 pset *remats_by_operand; /**< remats with this value as operand */
145 typedef struct _keyval_t {
150 typedef struct _spill_t {
160 has_reg_class(const spill_ilp_t * si, const ir_node * irn)
162 return chordal_has_class(si->chordal_env, irn);
167 cmp_remat(const void *a, const void *b)
169 const keyval_t *p = a;
170 const keyval_t *q = b;
171 const remat_t *r = p->val;
172 const remat_t *s = q->val;
176 return !(r == s || r->op == s->op);
180 cmp_remat(const void *a, const void *b)
182 const remat_t *r = a;
183 const remat_t *s = a;
185 return !(r == s || r->op == s->op);
189 cmp_spill(const void *a, const void *b, size_t size)
191 const spill_t *p = a;
192 const spill_t *q = b;
194 // return !(p->irn == q->irn && p->bb == q->bb);
195 return !(p->irn == q->irn);
199 set_find_keyval(set * set, void * key)
204 return set_find(set, &query, sizeof(query), HASH_PTR(key));
208 set_insert_keyval(set * set, void * key, void * val)
214 return set_insert(set, &query, sizeof(query), HASH_PTR(key));
218 set_find_def(set * set, ir_node * value)
223 return set_find(set, &query, sizeof(query), HASH_PTR(value));
227 set_insert_def(set * set, ir_node * value)
234 return set_insert(set, &query, sizeof(query), HASH_PTR(value));
238 set_find_spill(set * set, ir_node * value)
243 return set_find(set, &query, sizeof(query), HASH_PTR(value));
246 #define pset_foreach(s,i) for((i)=pset_first((s)); (i); (i)=pset_next((s)))
247 #define set_foreach(s,i) for((i)=set_first((s)); (i); (i)=set_next((s)))
248 #define foreach_post_remat(s,i) for((i)=next_post_remat((s)); (i); (i)=next_post_remat((i)))
249 #define foreach_pre_remat(si,s,i) for((i)=next_pre_remat((si),(s)); (i); (i)=next_pre_remat((si),(i)))
250 #define sched_foreach_op(s,i) for((i)=sched_next_op((s));!sched_is_end((i));(i)=sched_next_op((i)))
253 cmp_remat_info(const void *a, const void *b, size_t size)
255 const remat_info_t *p = a;
256 const remat_info_t *q = b;
258 return !(p->irn == q->irn);
262 cmp_defs(const void *a, const void *b, size_t size)
267 return !(p->value == q->value);
271 cmp_keyval(const void *a, const void *b, size_t size)
273 const keyval_t *p = a;
274 const keyval_t *q = b;
276 return !(p->key == q->key);
280 execution_frequency(const spill_ilp_t * si, const ir_node * irn)
282 #ifdef EXECFREQ_LOOPDEPH
284 return expf((float)get_loop_depth(get_irn_loop(irn)) * logf(10));
286 return expf((float)get_loop_depth(get_irn_loop(get_nodes_block(irn))) * logf(10));
289 return get_block_execfreq(si->execfreqs, irn);
291 return get_block_execfreq(si->execfreqs, get_nodes_block(irn));
297 * Checks, whether node and its operands have suitable reg classes
300 is_rematerializable(const spill_ilp_t * si, const ir_node * irn)
304 const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
305 int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
309 ir_fprintf(stderr, " Node %+F is not rematerializable\n", irn);
312 for (i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
313 ir_node *op = get_irn_n(irn, i);
314 remat &= has_reg_class(si, op) || arch_irn_get_flags(arch_env, op) & arch_irn_flags_ignore || (get_irn_op(op) == op_NoMem);
317 // ir_fprintf(stderr, " Argument %d (%+F) of Node %+F has wrong regclass\n", i, op, irn);
324 * Try to create a remat from @p op with destination value @p dest_value
326 static INLINE remat_t *
327 get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * op)
329 remat_t *remat = NULL;
331 // if(!mode_is_datab(get_irn_mode(dest_value)))
334 if(dest_value == op) {
335 const ir_node *proj = NULL;
337 if(is_Proj(dest_value)) {
338 op = get_irn_n(op, 0);
342 if(!is_rematerializable(si, op))
345 remat = obstack_alloc(si->obst, sizeof(*remat));
347 remat->cost = COST_REMAT; /* TODO ask backend for real cost */
348 remat->value = dest_value;
351 arch_inverse_t inverse;
355 /* get the index of the operand we want to retrieve by the inverse op */
356 for (i = 0, n = get_irn_arity(op); i < n; ++i) {
357 ir_node *arg = get_irn_n(op, i);
359 if(arg == dest_value) break;
361 if(i == n) return NULL;
363 DBG((si->dbg, LEVEL_5, "\t requesting inverse op for argument %d of op %+F\n", i, op));
365 /* else ask the backend to give an inverse op */
366 if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, i, &inverse, si->obst)) {
367 DBG((si->dbg, LEVEL_4, "\t backend gave us an inverse op with %d nodes and cost %d\n", inverse.n, inverse.costs));
369 assert(inverse.n > 0 && "inverse op should have at least one node");
372 remat = obstack_alloc(si->obst, sizeof(*remat));
373 remat->op = inverse.nodes[0];
374 remat->cost = inverse.costs;
375 remat->value = dest_value;
376 remat->proj = (inverse.n==2)?inverse.nodes[1]:NULL;
378 assert(is_Proj(remat->proj));
380 DBG((si->dbg, LEVEL_1, "\t I can not handle remats with %d nodes\n", inverse.n));
387 DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F with %+F\n", remat->op, dest_value, op, remat->proj));
389 DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F\n", remat->op, dest_value, op));
397 add_remat(const spill_ilp_t * si, const remat_t * remat)
399 remat_info_t *remat_info,
405 assert(remat->value);
407 query.irn = remat->value;
409 query.remats_by_operand = NULL;
410 remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(remat->value));
412 if(remat_info->remats == NULL) {
413 remat_info->remats = new_pset(cmp_remat, 4096);
415 pset_insert(remat_info->remats, remat, HASH_PTR(remat->op));
417 /* insert the remat into the remats_be_operand set of each argument of the remat op */
418 for (i = 0, n = get_irn_arity(remat->op); i < n; ++i) {
419 ir_node *arg = get_irn_n(remat->op, i);
423 query.remats_by_operand = NULL;
424 remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(arg));
426 if(remat_info->remats_by_operand == NULL) {
427 remat_info->remats_by_operand = new_pset(cmp_remat, 4096);
429 pset_insert(remat_info->remats_by_operand, remat, HASH_PTR(remat->op));
434 get_remats_from_op(spill_ilp_t * si, const ir_node * op)
440 if(has_reg_class(si, op)) {
441 remat = get_remat_from_op(si, op, op);
443 add_remat(si, remat);
447 /* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg)
449 for (i = 0, n = get_irn_arity(op); i < n; ++i) {
450 ir_node *arg = get_irn_n(op, i);
452 if(has_reg_class(si, arg)) {
453 /* try to get an inverse remat */
454 remat = get_remat_from_op(si, arg, op);
456 add_remat(si, remat);
464 value_is_defined_before(const spill_ilp_t * si, const ir_node * pos, const ir_node * val)
467 ir_node *def_block = get_nodes_block(val);
473 /* if pos is at end of a basic block */
475 ret = (pos == def_block || block_dominates(def_block, pos));
476 // ir_fprintf(stderr, "(def(bb)=%d) ", ret);
480 /* else if this is a normal operation */
481 block = get_nodes_block(pos);
482 if(block == def_block) {
483 ret = sched_comes_after(val, pos);
484 // ir_fprintf(stderr, "(def(same block)=%d) ",ret);
488 ret = block_dominates(def_block, block);
489 // ir_fprintf(stderr, "(def(other block)=%d) ", ret);
493 static INLINE ir_node *
494 sched_block_last_noncf(const spill_ilp_t * si, const ir_node * bb)
496 return sched_skip((ir_node*)bb, 0, sched_skip_cf_predicator, (void *) si->chordal_env->birg->main_env->arch_env);
500 * Returns first non-Phi node of block @p bb
502 static INLINE ir_node *
503 sched_block_first_nonphi(const ir_node * bb)
505 return sched_skip((ir_node*)bb, 1, sched_skip_phi_predicator, NULL);
509 sched_skip_proj_predicator(const ir_node * irn, void * data)
511 return (is_Proj(irn));
514 static INLINE ir_node *
515 sched_next_nonproj(const ir_node * irn, int forward)
517 return sched_skip((ir_node*)irn, forward, sched_skip_proj_predicator, NULL);
521 * Returns next operation node (non-Proj) after @p irn
522 * or the basic block of this node
524 static INLINE ir_node *
525 sched_next_op(const ir_node * irn)
527 ir_node *next = sched_next(irn);
532 return sched_next_nonproj(next, 1);
536 * Returns previous operation node (non-Proj) before @p irn
537 * or the basic block of this node
539 static INLINE ir_node *
540 sched_prev_op(const ir_node * irn)
542 ir_node *prev = sched_prev(irn);
547 return sched_next_nonproj(prev, 0);
551 sched_put_after(ir_node * insert, ir_node * irn)
553 if(is_Block(insert)) {
554 insert = sched_block_first_nonphi(insert);
556 insert = sched_next_op(insert);
558 sched_add_before(insert, irn);
562 sched_put_before(const spill_ilp_t * si, ir_node * insert, ir_node * irn)
564 if(is_Block(insert)) {
565 insert = sched_block_last_noncf(si, insert);
567 insert = sched_next_nonproj(insert, 0);
568 insert = sched_prev(insert);
570 sched_add_after(insert, irn);
574 * Tells you whether a @p remat can be placed before the irn @p pos
577 can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
579 const ir_node *op = remat->op;
586 prev = sched_block_last_noncf(si, pos);
587 prev = sched_next_nonproj(prev, 0);
589 prev = sched_prev_op(pos);
591 /* do not remat if the rematted value is defined immediately before this op */
592 if(prev == remat->op) {
597 /* this should be just fine, the following OP will be using this value, right? */
599 /* only remat AFTER the real definition of a value (?) */
600 if(!value_is_defined_before(si, pos, remat->value)) {
601 // ir_fprintf(stderr, "error(not defined)");
606 for(i=0, n=get_irn_arity(op); i<n && res; ++i) {
607 const ir_node *arg = get_irn_n(op, i);
609 #ifdef NO_ENLARGE_L1V3N355
610 if(has_reg_class(si, arg) && live) {
611 res &= pset_find_ptr(live, arg)?1:0;
613 res &= value_is_defined_before(si, pos, arg);
616 res &= value_is_defined_before(si, pos, arg);
624 * Tells you whether a @p remat can be placed after the irn @p pos
627 can_remat_after(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
630 pos = sched_block_first_nonphi(pos);
632 pos = sched_next_op(pos);
635 /* only remat AFTER the real definition of a value (?) */
636 if(!value_is_defined_before(si, pos, remat->value)) {
640 return can_remat_before(si, remat, pos, live);
644 * Collect potetially rematerializable OPs
647 walker_remat_collector(ir_node * irn, void * data)
649 spill_ilp_t *si = data;
651 if(!is_Block(irn) && !is_Phi(irn)) {
652 DBG((si->dbg, LEVEL_4, "\t Processing %+F\n", irn));
653 get_remats_from_op(si, irn);
658 * Inserts a copy of @p irn before @p pos
661 insert_copy_before(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
666 bb = is_Block(pos)?pos:get_nodes_block(pos);
667 copy = exact_copy(irn);
668 set_nodes_block(copy, bb);
669 sched_put_before(si, pos, copy);
675 * Inserts a copy of @p irn after @p pos
678 insert_copy_after(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
683 bb = is_Block(pos)?pos:get_nodes_block(pos);
684 copy = exact_copy(irn);
685 set_nodes_block(copy, bb);
686 sched_put_after(pos, copy);
692 insert_remat_after(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
696 if(can_remat_after(si, remat, pos, live)) {
701 DBG((si->dbg, LEVEL_3, "\t >inserting remat %+F\n", remat->op));
703 copy = insert_copy_after(si, remat->op, pos);
705 // ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", remat->value, pos);
706 ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", copy, pos);
707 op = obstack_alloc(si->obst, sizeof(*op));
709 op->attr.remat.remat = remat;
710 op->attr.remat.pre = 0;
711 op->attr.remat.ilp = lpp_add_var(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos));
713 set_irn_link(copy, op);
714 pset_insert_ptr(si->all_possible_remats, copy);
716 proj_copy = insert_copy_after(si, remat->proj, copy);
717 set_irn_n(proj_copy, 0, copy);
718 set_irn_link(proj_copy, op);
719 pset_insert_ptr(si->all_possible_remats, proj_copy);
727 insert_remat_before(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
731 if(can_remat_before(si, remat, pos, live)) {
736 DBG((si->dbg, LEVEL_3, "\t >inserting remat %+F\n", remat->op));
738 copy = insert_copy_before(si, remat->op, pos);
740 // ir_snprintf(buf, sizeof(buf), "remat_%N_%N", remat->value, pos);
741 ir_snprintf(buf, sizeof(buf), "remat_%N_%N", copy, pos);
742 op = obstack_alloc(si->obst, sizeof(*op));
744 op->attr.remat.remat = remat;
745 op->attr.remat.pre = 1;
746 op->attr.remat.ilp = lpp_add_var(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos));
748 set_irn_link(copy, op);
749 pset_insert_ptr(si->all_possible_remats, copy);
751 proj_copy = insert_copy_after(si, remat->proj, copy);
752 set_irn_n(proj_copy, 0, copy);
753 set_irn_link(proj_copy, op);
754 pset_insert_ptr(si->all_possible_remats, proj_copy);
763 * Insert (so far unused) remats into the irg to
764 * recompute the potential liveness of all values
767 walker_remat_insertor(ir_node * bb, void * data)
769 spill_ilp_t *si = data;
770 spill_bb_t *spill_bb;
775 pset *live = pset_new_ptr_default();
777 DBG((si->dbg, LEVEL_3, "\t Entering %+F\n\n", bb));
779 live_foreach(bb, li) {
780 ir_node *value = (ir_node *) li->irn;
782 /* add remats at end of block */
783 if (live_is_end(li) && has_reg_class(si, value)) {
784 pset_insert_ptr(live, value);
788 spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
789 set_irn_link(bb, spill_bb);
791 irn = sched_last(bb);
792 while(!sched_is_end(irn)) {
798 next = sched_prev(irn);
800 DBG((si->dbg, LEVEL_5, "\t at %+F (next: %+F)\n", irn, next));
802 if(is_Phi(irn) || is_Proj(irn)) {
805 if(has_reg_class(si, irn)) {
806 pset_remove_ptr(live, irn);
809 op = obstack_alloc(si->obst, sizeof(*op));
811 op->attr.live_range.reloads = NULL;
812 op->attr.live_range.ilp = ILP_UNDEF;
813 set_irn_link(irn, op);
819 op = obstack_alloc(si->obst, sizeof(*op));
821 op->attr.live_range.ilp = ILP_UNDEF;
822 op->attr.live_range.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.reloads) * get_irn_arity(irn));
823 memset(op->attr.live_range.reloads, 0xFF, sizeof(*op->attr.live_range.reloads) * get_irn_arity(irn));
824 set_irn_link(irn, op);
826 args = pset_new_ptr_default();
828 /* collect arguments of op */
829 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
830 ir_node *arg = get_irn_n(irn, i);
832 pset_insert_ptr(args, arg);
835 /* set args of op live in epilog */
836 pset_foreach(args, arg) {
837 if(has_reg_class(si, arg)) {
838 pset_insert_ptr(live, arg);
842 /* insert all possible remats after irn */
843 pset_foreach(args, arg) {
844 remat_info_t *remat_info,
848 /* continue if the operand has the wrong reg class
850 if(!has_reg_class(si, arg))
855 query.remats_by_operand = NULL;
856 remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(arg));
862 /* do not place post remats after jumps */
863 if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) continue;
865 if(remat_info->remats_by_operand) {
866 pset_foreach(remat_info->remats_by_operand, remat) {
867 /* do not insert remats producing the same value as one of the operands */
868 if(!pset_find_ptr(args, remat->value)) {
869 DBG((si->dbg, LEVEL_4, "\t considering remat %+F with arg %+F\n", remat->op, arg));
870 #ifdef REMAT_WHILE_LIVE
871 if(pset_find_ptr(live, remat->value)) {
872 insert_remat_after(si, remat, irn, live);
875 insert_remat_after(si, remat, irn, live);
882 /* delete defined value from live set */
883 if(has_reg_class(si, irn)) {
884 pset_remove_ptr(live, irn);
887 /* insert all possible remats before irn */
888 pset_foreach(args, arg) {
889 remat_info_t *remat_info,
893 /* continue if the operand has the wrong reg class
895 if(!has_reg_class(si, arg))
900 query.remats_by_operand = NULL;
901 remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(arg));
907 if(remat_info->remats) {
908 pset_foreach(remat_info->remats, remat) {
909 DBG((si->dbg, LEVEL_4, "\t considering remat %+F for arg %+F\n", remat->op, arg));
910 #ifdef REMAT_WHILE_LIVE
911 if(pset_find_ptr(live, remat->value)) {
912 insert_remat_before(si, remat, irn, live);
915 insert_remat_before(si, remat, irn, live);
925 live_foreach(bb, li) {
926 ir_node *value = (ir_node *) li->irn;
928 /* add remats at end of block */
929 if (live_is_end(li) && has_reg_class(si, value)) {
930 remat_info_t *remat_info,
936 query.remats_by_operand = NULL;
937 remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value));
939 if(remat_info && remat_info->remats) {
940 pset_foreach(remat_info->remats, remat) {
941 DBG((si->dbg, LEVEL_4, "\t considering remat %+F at end of block %+F\n", remat->op, bb));
942 #ifdef REMAT_WHILE_LIVE
943 if(is_live_end(bb, remat->value)) {
944 insert_remat_before(si, remat, bb, NULL); //TODO
947 insert_remat_before(si, remat, bb, NULL);
954 /* add remat2s at beginning of block */
955 if ((live_is_in(li) || is_Phi(value)) && has_reg_class(si, value)) {
956 remat_info_t *remat_info,
962 query.remats_by_operand = NULL;
963 remat_info = set_find(si->remat_info, &query, sizeof(query), HASH_PTR(value));
965 if(remat_info && remat_info->remats_by_operand) {
966 pset_foreach(remat_info->remats_by_operand, remat) {
967 DBG((si->dbg, LEVEL_4, "\t considering remat %+F at beginning of block %+F\n", remat->op, bb));
968 #ifdef REMAT_WHILE_LIVE
969 if(is_live_in(bb, remat->value)) {
970 insert_remat_after(si, remat, bb, NULL);
973 insert_remat_after(si, remat, bb, NULL);
982 * Preparation of blocks' ends for Luke Blockwalker(tm)(R)
985 luke_endwalker(ir_node * bb, void * data)
987 spill_ilp_t *si = (spill_ilp_t*)data;
994 spill_bb_t *spill_bb = get_irn_link(bb);
997 live = pset_new_ptr_default();
998 use_end = pset_new_ptr_default();
1000 live_foreach(bb, li) {
1001 irn = (ir_node *) li->irn;
1002 if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
1005 pset_insert_ptr(live, irn);
1006 op = get_irn_link(irn);
1007 assert(!op->is_remat);
1011 /* collect values used by cond jumps etc. at bb end (use_end) -> always live */
1012 /* their reg_out is unimportant because it can always be set */
1013 sched_foreach_reverse(bb, irn) {
1017 if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
1019 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
1020 ir_node *irn_arg = get_irn_n(irn, i);
1021 if(has_reg_class(si, irn_arg)) {
1022 pset_insert_ptr(use_end, irn);
1027 ir_snprintf(buf, sizeof(buf), "check_end_%N", bb);
1028 cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - pset_count(use_end));
1030 spill_bb->ilp = new_set(cmp_spill, 16);
1032 live_foreach(bb, li) {
1033 irn = (ir_node *) li->irn;
1034 if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
1039 spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn));
1041 ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", bb, irn);
1042 spill->reg_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1043 /* if irn is used at the end of the block, then it is live anyway */
1044 if(!pset_find_ptr(use_end, irn))
1045 lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
1047 ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", bb, irn);
1048 spill->mem_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1050 ir_snprintf(buf, sizeof(buf), "spill_%N_%N", bb, irn);
1051 spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, irn));
1053 spill->reg_in = ILP_UNDEF;
1054 spill->mem_in = ILP_UNDEF;
1063 next_post_remat(const ir_node * irn)
1068 irn = sched_block_first_nonphi(irn);
1070 irn = sched_next_op(irn);
1073 if(sched_is_end(irn))
1076 op = (op_t*)get_irn_link(irn);
1077 if(op->is_remat && !op->attr.remat.pre) {
1086 next_pre_remat(const spill_ilp_t * si, const ir_node * irn)
1092 ret = sched_block_last_noncf(si, irn);
1093 ret = sched_next(ret);
1094 ret = sched_prev_op(ret);
1096 ret = sched_prev_op(irn);
1099 if(sched_is_end(ret) || is_Phi(ret))
1102 op = (op_t*)get_irn_link(ret);
1103 if(op->is_remat && op->attr.remat.pre) {
1111 * Find a remat of value @p value in the epilog of @p pos
1114 find_post_remat(const ir_node * value, const ir_node * pos)
1116 while((pos = next_post_remat(pos)) != NULL) {
1119 op = get_irn_link(pos);
1120 assert(op->is_remat && !op->attr.remat.pre);
1122 if(op->attr.remat.remat->value == value)
1123 return (ir_node*)pos;
1126 const ir_edge_t *edge;
1127 foreach_out_edge(pos, edge) {
1128 ir_node *proj = get_edge_src_irn(edge);
1129 assert(is_Proj(proj));
1139 * Find a remat of value @p value in the prolog of @p pos
1142 find_pre_remat(const spill_ilp_t * si, const ir_node * value, const ir_node * pos)
1144 while((pos = next_pre_remat(si,pos)) != NULL) {
1147 op = get_irn_link(pos);
1148 assert(op->is_remat && op->attr.remat.pre);
1150 if(op->attr.remat.remat->value == value)
1151 return (ir_node*)pos;
1158 add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn)
1160 spill_bb_t *spill_bb = get_irn_link(bb);
1166 spill = set_find(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn));
1168 spill = set_insert(spill_bb->ilp, &query, sizeof(query), HASH_PTR(irn));
1170 spill->reg_out = ILP_UNDEF;
1171 spill->reg_in = ILP_UNDEF;
1172 spill->mem_in = ILP_UNDEF;
1174 ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", irn, bb);
1175 spill->mem_out = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1177 ir_snprintf(buf, sizeof(buf), "spill_%N_%N", irn, bb);
1178 spill->spill = lpp_add_var(si->lpp, buf, lpp_binary, COST_STORE*execution_frequency(si, bb));
1185 * Walk all irg blocks and emit this ILP
1188 luke_blockwalker(ir_node * bb, void * data)
1190 spill_ilp_t *si = (spill_ilp_t*)data;
1196 spill_bb_t *spill_bb = get_irn_link(bb);
1202 live = pset_new_ptr_default();
1204 /* do something at the end of the block */
1206 /* init live values at end of block */
1207 live_foreach(bb, li) {
1208 ir_node *irn = (ir_node *) li->irn;
1210 if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
1211 pset_insert_ptr(live, irn);
1215 spill_bb->reloads = obstack_alloc(si->obst, pset_count(live) * sizeof(*spill_bb->reloads));
1216 memset(spill_bb->reloads, 0xFF, pset_count(live) * sizeof(*spill_bb->reloads));
1219 live_foreach(bb, li) {
1220 ir_node *irn = (ir_node *) li->irn;
1223 if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
1224 spill = set_find_spill(spill_bb->ilp, irn);
1227 ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn);
1228 spill_bb->reloads[i] = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, bb));
1230 /* reload <= mem_out */
1231 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1232 lpp_set_factor_fast(si->lpp, cst, spill_bb->reloads[i], 1.0);
1233 lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0);
1235 op = get_irn_link(irn);
1236 assert(!op->is_remat);
1238 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", irn, bb);
1239 op->attr.live_range.ilp = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1240 op->attr.live_range.op = bb;
1242 ir_snprintf(buf, sizeof(buf), "reg_out_%N_%N", bb, irn);
1243 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1245 /* reg_out - reload - remat - live_range <= 0 */
1246 lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
1247 lpp_set_factor_fast(si->lpp, cst, spill_bb->reloads[i], -1.0);
1248 lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -1.0);
1249 foreach_pre_remat(si, bb, tmp) {
1250 op_t *remat_op = get_irn_link(tmp);
1251 if(remat_op->attr.remat.remat->value == irn) {
1252 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
1259 DBG((si->dbg, LEVEL_4, "\t %d values live at end of block %+F\n", pset_count(live), bb));
1261 sched_foreach_reverse(bb, irn) {
1267 ilp_cst_t check_pre,
1270 set *args = new_set(cmp_keyval, get_irn_arity(irn));
1276 op = get_irn_link(irn);
1278 if(op->is_remat) continue;
1279 DBG((si->dbg, LEVEL_4, "\t at node %+F\n", irn));
1281 if(has_reg_class(si, irn)) {
1282 assert(pset_find_ptr(live, irn));
1283 pset_remove_ptr(live, irn);
1286 /* init set of irn's arguments */
1287 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
1288 ir_node *irn_arg = get_irn_n(irn, i);
1289 if(has_reg_class(si, irn_arg)) {
1290 set_insert_keyval(args, irn_arg, (void*)i);
1294 /* check the register pressure after the epilog */
1295 ir_snprintf(buf, sizeof(buf), "check_post_remat_%N", irn);
1296 check_post_remat = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs);
1298 /* iterate over L\U */
1299 pset_foreach(live, tmp) {
1300 if(!set_find_keyval(args, tmp)) {
1301 /* if a live value is not used by irn */
1302 tmp_op = get_irn_link(tmp);
1303 // assert(tmp_op->attr.live_range.op != irn);
1304 lpp_set_factor_fast(si->lpp, check_post_remat, tmp_op->attr.live_range.ilp, 1.0);
1307 /* iterate over following remats and remove possibly defined values again from check_post_remat */
1308 foreach_post_remat(irn, tmp) {
1309 op_t *remat_op = get_irn_link(tmp);
1310 const ir_node *value = remat_op->attr.remat.remat->value;
1311 op_t *val_op = get_irn_link(value);
1313 assert(remat_op->is_remat && !remat_op->attr.remat.pre);
1315 /* values that are defined by remats are not counted */
1316 /* TODO assert(val_op->attr.live_range.ilp)) */
1317 if(val_op->attr.live_range.ilp != ILP_UNDEF) {
1318 lpp_set_factor_fast(si->lpp, check_post_remat, val_op->attr.live_range.ilp, 0.0);
1323 /* new live ranges for values from L\U defined by remat2s or used by remats */
1324 pset_foreach(live, tmp) {
1325 ir_node *value = tmp;//remat_op->attr.remat.remat->value;
1326 op_t *value_op = get_irn_link(value);
1328 if(!set_find_keyval(args, value)) {
1329 ilp_var_t prev_lr = ILP_UNDEF;
1333 foreach_post_remat(irn, remat) {
1334 op_t *remat_op = get_irn_link(remat);
1336 /* if value is being rematerialized by this remat */
1337 if(value == remat_op->attr.remat.remat->value) {
1338 if(cst == ILP_UNDEF) {
1339 /* next_live_range <= prev_live_range + sum remat2s */
1340 ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn);
1341 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1342 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", value, irn);
1343 prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1344 lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0);
1345 lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0);
1348 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
1352 #ifdef MAY_DIE_AT_PRE_REMAT
1353 if(cst == ILP_UNDEF) {
1354 foreach_pre_remat(si, irn, remat) {
1358 for (i = 0, n = get_irn_arity(remat); i < n; ++i) {
1359 ir_node *remat_arg = get_irn_n(remat, i);
1361 /* if value is being used by this remat */
1362 if(value == remat_arg) {
1363 /* next_live_range <= prev_live_range */
1364 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", value, irn);
1365 prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1367 ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn);
1368 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1369 lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0);
1370 lpp_set_factor_fast(si->lpp, cst, prev_lr, -1.0);
1373 /* TODO check afterwards whether lr dies after a pre-remat (should not happen) */
1380 if(prev_lr != ILP_UNDEF) {
1381 value_op->attr.live_range.ilp = prev_lr;
1382 value_op->attr.live_range.op = irn;
1387 /* get count of values in my register class defined by irn */
1388 /* also add defined values to check_post_remat; do this before iterating over args */
1389 if(get_irn_mode(irn) == mode_T) {
1390 ir_node *proj = sched_next(irn);
1391 op_t *proj_op = get_irn_link(proj);
1393 while(is_Proj(proj)) {
1394 if(has_reg_class(si, proj)) {
1396 lpp_set_factor_fast(si->lpp, check_post_remat, proj_op->attr.live_range.ilp, 1.0);
1398 proj = sched_next(proj);
1399 proj_op = get_irn_link(proj);
1402 if(has_reg_class(si, irn)) {
1404 lpp_set_factor_fast(si->lpp, check_post_remat, op->attr.live_range.ilp, 1.0);
1407 DBG((si->dbg, LEVEL_4, "\t %+F produces %d values in my register class\n", irn, d));
1409 /* count how many regs irn needs for arguments */
1410 k = set_count(args);
1412 /* check the register pressure in the prolog */
1413 /* sum_{L\U} lr <= n - |U| */
1414 ir_snprintf(buf, sizeof(buf), "check_pre_%N", irn);
1415 check_pre = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - k);
1417 /* check the register pressure in the epilog */
1418 ir_snprintf(buf, sizeof(buf), "check_post_%N", irn);
1419 check_post = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs - d);
1421 set_foreach(args, keyval) {
1427 ir_node *arg = keyval->key;
1429 spill = add_to_spill_bb(si, bb, arg);
1431 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", arg, irn);
1432 next_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1434 i = (int)keyval->val;
1437 ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn);
1438 op->attr.live_range.reloads[i] = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD*execution_frequency(si, irn));
1440 /* reload <= mem_out */
1441 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1442 lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[i], 1.0);
1443 lpp_set_factor_fast(si->lpp, cst, spill->mem_out, -1.0);
1445 arg_op = get_irn_link(arg);
1447 /* requirement: arg must be in register for use */
1448 /* reload + remat + live_range == 1 */
1449 ir_snprintf(buf, sizeof(buf), "req_%N_%N", irn, arg);
1450 cst = lpp_add_cst(si->lpp, buf, lpp_equal, 1.0);
1452 lpp_set_factor_fast(si->lpp, cst, next_lr, 1.0);
1453 lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[i], 1.0);
1454 foreach_pre_remat(si, irn, tmp) {
1455 op_t *remat_op = get_irn_link(tmp);
1456 if(remat_op->attr.remat.remat->value == arg) {
1457 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
1461 /* the epilog stuff - including post_use, post, post_remat */
1462 ir_snprintf(buf, sizeof(buf), "post_use_%N_%N", arg, irn);
1463 post_use = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1465 lpp_set_factor_fast(si->lpp, check_post, post_use, 1.0);
1467 /* arg is live throughout epilog if the next live_range is in a register */
1468 if(pset_find_ptr(live, arg)) {
1469 DBG((si->dbg, LEVEL_3, "\t arg %+F is possibly live in epilog of %+F\n", arg, irn));
1471 ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
1472 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1473 lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
1474 lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0);
1476 lpp_set_factor_fast(si->lpp, check_post_remat, arg_op->attr.live_range.ilp, 1.0);
1479 /*forall remat2 which use arg add a similar cst*/
1480 foreach_post_remat(irn, tmp) {
1484 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1485 ir_node *remat_arg = get_irn_n(tmp, i);
1486 op_t *remat_op = get_irn_link(tmp);
1488 if(remat_arg == arg) {
1489 DBG((si->dbg, LEVEL_3, "\t found remat with arg %+F in epilog of %+F\n", arg, irn));
1491 ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
1492 cst = lpp_add_cst(si->lpp, buf, lpp_greater, 0.0);
1493 lpp_set_factor_fast(si->lpp, cst, post_use, 1.0);
1494 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
1499 /* new live range begins for each argument */
1500 arg_op->attr.live_range.ilp = next_lr;
1501 arg_op->attr.live_range.op = irn;
1503 pset_insert_ptr(live, arg);
1506 /* start new live ranges for values used by remats */
1507 foreach_pre_remat(si, irn, tmp) {
1511 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1512 ir_node *remat_arg = get_irn_n(tmp, i);
1513 op_t *arg_op = get_irn_link(remat_arg);
1516 if(!has_reg_class(si, remat_arg)) continue;
1518 /* if value is becoming live through use by remat */
1519 if(!pset_find_ptr(live, remat_arg)) {
1520 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", remat_arg, irn);
1521 prev_lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1523 arg_op->attr.live_range.ilp = prev_lr;
1524 arg_op->attr.live_range.op = irn;
1526 DBG((si->dbg, LEVEL_4, " value %+F becoming live through use by remat %+F\n", remat_arg, tmp));
1528 /* TODO ist das hier die richtige Stelle???? */
1529 pset_insert_ptr(live, remat_arg);
1530 add_to_spill_bb(si, bb, remat_arg);
1532 /* TODO check afterwards whether lr dies after a pre-remat (should not happen) */
1536 /* iterate over L\U */
1537 pset_foreach(live, tmp) {
1538 if(!set_find_keyval(args, tmp)) {
1539 /* if a live value is not used by irn */
1540 tmp_op = get_irn_link(tmp);
1541 // assert(tmp_op->attr.live_range.op != irn);
1542 lpp_set_factor_fast(si->lpp, check_pre, tmp_op->attr.live_range.ilp, 1.0);
1543 lpp_set_factor_fast(si->lpp, check_post, tmp_op->attr.live_range.ilp, 1.0);
1547 /* requirements for remats */
1548 foreach_pre_remat(si, irn, tmp) {
1549 op_t *remat_op = get_irn_link(tmp);
1553 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1554 ir_node *remat_arg = get_irn_n(tmp, i);
1555 op_t *arg_op = get_irn_link(remat_arg);
1557 if(!has_reg_class(si, remat_arg)) continue;
1559 /* remat <= live_rang(remat_arg) [ + reload(remat_arg) ] */
1560 ir_snprintf(buf, sizeof(buf), "req_remat_%N_arg_%N", tmp, remat_arg);
1561 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1563 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
1564 lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0);
1566 /* if remat arg is also used by current op then we can use reload placed for this argument */
1567 if((keyval = set_find_keyval(args, remat_arg)) != NULL) {
1568 int index = (int)keyval->val;
1570 lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.reloads[index], -1.0);
1575 /* requirements for remats2
1577 * TODO unsure if this does the right thing.
1578 * should insert values into set if they do not become live through remat and
1581 foreach_post_remat(irn, tmp) {
1582 op_t *remat_op = get_irn_link(tmp);
1586 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1587 ir_node *remat_arg = get_irn_n(tmp, i);
1588 op_t *arg_op = get_irn_link(remat_arg);
1590 if(!has_reg_class(si, remat_arg)) continue;
1592 /* only for values in L\U, the others are handled with post_use */
1593 if(!set_find_keyval(args, remat_arg)) {
1594 /* remat <= live_rang(remat_arg) */
1595 ir_snprintf(buf, sizeof(buf), "req_remat2_%N_arg_%N", tmp, remat_arg);
1596 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1598 /* if value is becoming live through use by remat2 */
1599 if(!pset_find_ptr(live, remat_arg)) {
1602 ir_snprintf(buf, sizeof(buf), "lr_%N_%N", remat_arg, irn);
1603 lr = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1605 arg_op->attr.live_range.ilp = lr;
1606 arg_op->attr.live_range.op = irn;
1608 DBG((si->dbg, LEVEL_3, " value %+F becoming live through use by remat2 %+F\n", remat_arg, tmp));
1610 pset_insert_ptr(live, remat_arg);
1611 add_to_spill_bb(si, bb, remat_arg);
1614 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
1615 lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0);
1620 /* iterate over following remats and add them to check_post_remat */
1621 foreach_post_remat(irn, tmp) {
1622 op_t *remat_op = get_irn_link(tmp);
1624 assert(remat_op->is_remat && !remat_op->attr.remat.pre);
1626 lpp_set_factor_fast(si->lpp, check_post_remat, remat_op->attr.remat.ilp, 1.0);
1630 DBG((si->dbg, LEVEL_4, "\t %d values live at %+F\n", pset_count(live), irn));
1632 pset_foreach(live, tmp) {
1633 assert(has_reg_class(si, tmp));
1636 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
1637 ir_node *arg = get_irn_n(irn, i);
1639 assert(!find_post_remat(arg, irn) && "there should be no post remat for an argument of an op");
1647 /* do something at the beginning of the block */
1649 /* we are now at the beginning of the basic block, there are only \Phis in front of us */
1650 DBG((si->dbg, LEVEL_3, "\t %d values live at beginning of block %+F\n", pset_count(live), bb));
1652 pset_foreach(live, irn) {
1653 assert(is_Phi(irn) || get_nodes_block(irn) != bb);
1656 /* construct mem_outs for all values */
1658 set_foreach(spill_bb->ilp, spill) {
1659 ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", spill->irn, bb);
1660 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1662 lpp_set_factor_fast(si->lpp, cst, spill->mem_out, 1.0);
1663 lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0);
1665 if(pset_find_ptr(live, spill->irn)) {
1666 DBG((si->dbg, LEVEL_5, "\t %+F live at beginning of block %+F\n", spill->irn, bb));
1668 ir_snprintf(buf, sizeof(buf), "mem_in_%N_%N", spill->irn, bb);
1669 spill->mem_in = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1671 lpp_set_factor_fast(si->lpp, cst, spill->mem_in, -1.0);
1676 /* L\U is empty at bb start */
1677 /* arg is live throughout epilog if it is reg_in into this block */
1679 /* check the register pressure at the beginning of the block
1682 ir_snprintf(buf, sizeof(buf), "check_start_%N", bb);
1683 cst = lpp_add_cst(si->lpp, buf, lpp_less, si->n_regs);
1685 pset_foreach(live, irn) {
1686 spill = set_find_spill(spill_bb->ilp, irn);
1689 ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N", irn, bb);
1690 spill->reg_in = lpp_add_var(si->lpp, buf, lpp_binary, 0.0);
1692 lpp_set_factor_fast(si->lpp, cst, spill->reg_in, 1.0);
1694 foreach_post_remat(bb, irn) {
1695 op_t *remat_op = get_irn_link(irn);
1697 DBG((si->dbg, LEVEL_4, "\t next post remat: %+F\n", irn));
1698 assert(remat_op->is_remat && !remat_op->attr.remat.pre);
1700 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
1703 /* forall remat2 add requirements */
1704 foreach_post_remat(bb, tmp) {
1708 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1709 ir_node *remat_arg = get_irn_n(tmp, i);
1710 op_t *remat_op = get_irn_link(tmp);
1712 if(!has_reg_class(si, remat_arg)) continue;
1714 spill = set_find_spill(spill_bb->ilp, remat_arg);
1717 /* TODO verify this is placed correctly */
1718 ir_snprintf(buf, sizeof(buf), "req_remat2_%N_%N_arg_%N", tmp, bb, remat_arg);
1719 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1720 lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
1721 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
1725 /* mem_in/reg_in for live_in values, especially phis and their arguments */
1726 // if(get_Block_n_cfgpreds(bb) > 1) {
1727 pset_foreach(live, irn) {
1732 spill = set_find_spill(spill_bb->ilp, irn);
1733 assert(spill && spill->irn == irn);
1735 if(is_Phi(irn) && get_nodes_block(irn) == bb) {
1736 for (i = 0, n = get_Phi_n_preds(irn); i < n; ++i) {
1739 ir_node *phi_arg = get_Phi_pred(irn, i);
1740 ir_node *bb_p = get_Block_cfgpred_block(bb, i);
1741 spill_bb_t *spill_bb_p = get_irn_link(bb_p);
1744 /* although the phi is in the right regclass one or more of
1745 * its arguments can be in a different one or at least to
1748 if(has_reg_class(si, phi_arg)) {
1749 ir_snprintf(buf, sizeof(buf), "mem_in_%N_%N-%d", irn, bb, p);
1750 mem_in = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1751 ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N-%d", irn, bb, p++);
1752 reg_in = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1754 lpp_set_factor_fast(si->lpp, mem_in, spill->mem_in, 1.0);
1755 lpp_set_factor_fast(si->lpp, reg_in, spill->reg_in, 1.0);
1757 spill_p = set_find_spill(spill_bb_p->ilp, phi_arg);
1760 lpp_set_factor_fast(si->lpp, mem_in, spill_p->mem_out, -1.0);
1761 lpp_set_factor_fast(si->lpp, reg_in, spill_p->reg_out, -1.0);
1765 /* else assure the value arrives on all paths in the same resource */
1767 for (i = 0, n = get_Block_n_cfgpreds(bb); i < n; ++i) {
1770 ir_node *bb_p = get_Block_cfgpred_block(bb, i);
1771 spill_bb_t *spill_bb_p = get_irn_link(bb_p);
1774 ir_snprintf(buf, sizeof(buf), "mem_in_%N_%N-%d", irn, bb, p);
1775 mem_in = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1776 ir_snprintf(buf, sizeof(buf), "reg_in_%N_%N-%d", irn, bb, p++);
1777 reg_in = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1779 lpp_set_factor_fast(si->lpp, mem_in, spill->mem_in, 1.0);
1780 lpp_set_factor_fast(si->lpp, reg_in, spill->reg_in, 1.0);
1782 spill_p = set_find_spill(spill_bb_p->ilp, irn);
1785 lpp_set_factor_fast(si->lpp, mem_in, spill_p->mem_out, -1.0);
1786 lpp_set_factor_fast(si->lpp, reg_in, spill_p->reg_out, -1.0);
1792 /* first live ranges from reg_ins */
1793 pset_foreach(live, irn) {
1794 op_t *op = get_irn_link(irn);
1796 spill = set_find_spill(spill_bb->ilp, irn);
1797 assert(spill && spill->irn == irn);
1799 ir_snprintf(buf, sizeof(buf), "first_lr_%N_%N", irn, bb);
1800 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1801 lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, 1.0);
1802 lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
1804 foreach_post_remat(bb, tmp) {
1805 op_t *remat_op = get_irn_link(tmp);
1807 if(remat_op->attr.remat.remat->value == irn) {
1808 lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
1813 /* walk forward now and compute constraints for placing spills */
1814 /* this must only be done for values that are not defined in this block */
1815 pset_foreach(live, irn) {
1816 ir_snprintf(buf, sizeof(buf), "req_spill_%N_%N", spill->irn, bb);
1817 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1819 spill = set_find_spill(spill_bb->ilp, irn);
1822 lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
1823 lpp_set_factor_fast(si->lpp, cst, spill->reg_in, -1.0);
1825 sched_foreach_op(bb, tmp) {
1826 op_t *op = get_irn_link(tmp);
1828 if(is_Phi(tmp)) continue;
1829 assert(!is_Proj(tmp));
1832 ir_node *value = op->attr.remat.remat->value;
1835 /* only collect remats up to the first use of a value */
1836 lpp_set_factor_fast(si->lpp, cst, op->attr.remat.ilp, -1.0);
1842 for (i = 0, n = get_irn_arity(tmp); i < n; ++i) {
1843 ir_node *arg = get_irn_n(tmp, i);
1846 /* if a value is used stop collecting remats */
1852 if(cst == ILP_UNDEF) break;
1857 /* if a value is used by a mem-phi, then mem_in of this value is 0 (has to be spilled again into a different slot)
1858 mem_in(phi) -> not mem_in(orig_value) TODO: how does this depend on a certain predecessor?
1861 /* mem_in of mem-phi has associated costs (but first one is free) */
1862 /* define n_mem_copies as positive integer in each predecessor block,
1863 #mem_in into this block from predecessor block - 1 weighted with SPILL_COST*execfreq(predecessor)
1868 /* ir_snprintf(buf, sizeof(buf), "next_lr_%N_%N", value, irn);
1869 cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
1870 lpp_set_factor_fast(si->lpp, cst, value_op->attr.live_range.ilp, 1.0);
1874 ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
1875 cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
1876 lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
1877 op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
1886 process_block(ir_node * block, void *data)
1888 spill_ilp_t *si = data;
1890 int n_regs = arch_register_class_n_regs(si->cls);
1891 int n_preds = get_irn_arity(block);
1895 DBG((si->dbg, LEVEL_3, "\nProcessing %+F\n", block));
1898 * compute all possible remats, sorted by operands *and* resulting
1901 ir_node *new_r_Tuple(ir_graph * irg, ir_node * block, int arity, ir_node * in[]);
1902 ir_node *new_r_Proj(ir_graph * irg, ir_node * block, ir_node * arg, ir_mode * mode, long proj);
1903 void *get_irn_link(const ir_node * node);
1904 void set_irn_link(ir_node * node, void *link);
1906 int block_dominates(const ir_node * a, const ir_node * b);
1909 void compute_doms(ir_graph * irg);
1910 void free_dom(ir_graph * irg);
1914 * nochmal: - laufe in dominatorreihenfolge die bloecke ab -
1915 * sammle dabei moeglichkeiten zur rematerialisierung von werten
1916 * (auch inverse etc.) - mehrere listen: fuer zielwert und fuer
1917 * jeden operanden (get_remats_with_operand) - ignoriere projs
1918 * (und phis?) und andere registerklassen - wenn ich nun auf eine
1919 * op treffe füge ich für alle operanden mögliche remats ein
1920 * (keine reloads und spills) in den schedule direkt vor der op
1921 * ein (in der Hoffnung, dass diese nicht wegoptimiert werden...).
1922 * - dann überspringe ich die folgenden projs - nach den projs
1923 * wird der epilog eingefügt (nur remats, keine spills) -
1924 * lebendigkeit neu berechnen
1926 * -durchlaufe den ganzen mist nochmal und emittiere dabei das ILP:
1929 * datenhaltung: - remat merkt sich die zugehörige ilp_var und op
1930 * - op merkt sich (zugehörige remats) - block merkt sich ilp_vars
1933 * nachbearbeitung: - durchlaufe alle instruktionen, dabei entferne
1934 * nicht benötigte remats und füge benötigte reloads ein - wenn
1935 * spill in Grundblock eingesetzt werden soll durchlaufen wir den
1936 * Block von oben runter und setzen das spill an der letzten
1937 * möglichen Stelle vor der ersten Benutzung/Reload ein. -
1938 * Speicherkopienminimierung: teste Speicherwerte auf Interferenz
1939 * und weise Spillkontexte zu. Sorge bei Phis dafuer, dass gleiche
1940 * Kontexte zusammenfliessen (Operanden und Ergebnis hat gleichen
1943 * nachoptimierung: - laufe wieder von oben nach unten durch jeden
1944 * block - wenn ich ein reload finde, dann schiebe es hoch solange
1945 * es der Registerdruck erlaubt (wenn ich es über sein
1946 * zugehöriges spill schiebe ist das ein bug, oder?)
1956 return fabs(x) < 0.00001;
1961 is_spilled(const spill_ilp_t * si, const live_range_t * lr)
1963 return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
1968 is_mem_phi(const ir_node * phi, void *data)
1970 spill_ilp_t *si = data;
1971 // return is_spilled(si, get_use_head(si, phi)->closest_use);
1975 static int mark_remat_nodes_hook(FILE *F, ir_node *n, ir_node *l)
1977 spill_ilp_t *si = get_irg_link(current_ir_graph);
1979 if(pset_find_ptr(si->all_possible_remats, n)) {
1980 op_t *op = (op_t*)get_irn_link(n);
1981 assert(op && op->is_remat);
1983 if(op->attr.remat.pre) {
1984 ir_fprintf(F, "color:red info3:\"remat value: %+F\"", op->attr.remat.remat->value);
1986 ir_fprintf(F, "color:orange info3:\"remat2 value: %+F\"", op->attr.remat.remat->value);
1996 dump_graph_with_remats(ir_graph * irg, const char * suffix)
1998 set_dump_node_vcgattr_hook(mark_remat_nodes_hook);
1999 be_dump(irg, suffix, dump_ir_block_graph_sched);
2000 set_dump_node_vcgattr_hook(NULL);
2004 * Edge hook to dump the schedule edges with annotated register pressure.
2007 sched_pressure_edge_hook(FILE *F, ir_node *irn)
2009 if(sched_is_scheduled(irn) && sched_has_prev(irn)) {
2010 ir_node *prev = sched_prev(irn);
2011 fprintf(F, "edge:{sourcename:\"");
2013 fprintf(F, "\" targetname:\"");
2015 fprintf(F, "\" label:\"%d", (int)get_irn_link(irn));
2016 fprintf(F, "\" color:magenta}\n");
2022 dump_ir_block_graph_sched_pressure(ir_graph *irg, const char *suffix)
2024 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
2026 dump_consts_local(0);
2027 set_dump_node_edge_hook(sched_pressure_edge_hook);
2028 dump_ir_block_graph(irg, suffix);
2029 set_dump_node_edge_hook(old);
2033 walker_pressure_annotator(ir_node * bb, void * data)
2035 spill_ilp_t *si = data;
2040 pset *live = pset_new_ptr_default();
2043 live_foreach(bb, li) {
2044 irn = (ir_node *) li->irn;
2046 if (live_is_end(li) && has_reg_class(si, irn)) {
2047 pset_insert_ptr(live, irn);
2051 set_irn_link(bb, (void*)pset_count(live));
2053 sched_foreach_reverse(bb, irn) {
2055 set_irn_link(irn, (void*)pset_count(live));
2059 if(has_reg_class(si, irn)) {
2060 pset_remove_ptr(live, irn);
2061 if(is_Proj(irn)) ++projs;
2064 if(!is_Proj(irn)) projs = 0;
2066 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
2067 ir_node *arg = get_irn_n(irn, i);
2069 if(has_reg_class(si, arg)) pset_insert_ptr(live, arg);
2071 set_irn_link(irn, (void*)pset_count(live)+projs);
2078 dump_pressure_graph(spill_ilp_t * si, const char *suffix)
2080 be_dump(si->chordal_env->irg, suffix, dump_ir_block_graph_sched_pressure);
2085 connect_all_remats_with_keep(spill_ilp_t * si)
2093 n_remats = pset_count(si->all_possible_remats);
2095 ins = obstack_alloc(si->obst, n_remats * sizeof(*ins));
2098 pset_foreach(si->all_possible_remats, irn) {
2103 si->keep = be_new_Keep(si->chordal_env->cls, si->chordal_env->irg, get_irg_end_block(si->chordal_env->irg), n_remats, ins);
2105 obstack_free(si->obst, ins);
2110 /** insert a spill at an arbitrary position */
2111 ir_node *be_spill2(const arch_env_t *arch_env, ir_node *irn, ir_node *insert, ir_node *ctx)
2113 ir_node *bl = is_Block(insert)?insert:get_nodes_block(insert);
2114 ir_graph *irg = get_irn_irg(bl);
2115 ir_node *frame = get_irg_frame(irg);
2119 const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
2120 const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
2122 spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn, ctx);
2125 * search the right insertion point. a spill of a phi cannot be put
2126 * directly after the phi, if there are some phis behind the one which
2127 * is spilled. Also, a spill of a Proj must be after all Projs of the
2130 * Here's one special case:
2131 * If the spill is in the start block, the spill must be after the frame
2132 * pointer is set up. This is done by setting insert to the end of the block
2133 * which is its default initialization (see above).
2136 if(bl == get_irg_start_block(irg) && sched_get_time_step(frame) >= sched_get_time_step(insert))
2139 for (next = sched_next(insert); is_Phi(next) || is_Proj(next); next = sched_next(insert))
2142 sched_add_after(insert, spill);
2147 delete_remat(spill_ilp_t * si, ir_node * remat) {
2150 ir_node *bad = get_irg_bad(si->chordal_env->irg);
2152 sched_remove(remat);
2154 /* kill links to operands */
2155 for (i = -1, n = get_irn_arity(remat); i < n; ++i) {
2156 set_irn_n(remat, i, bad);
2161 clean_remat_info(spill_ilp_t * si)
2166 remat_info_t *remat_info;
2167 ir_node *bad = get_irg_bad(si->chordal_env->irg);
2169 set_foreach(si->remat_info, remat_info) {
2170 if(!remat_info->remats) continue;
2172 pset_foreach(remat_info->remats, remat)
2174 if(remat->proj && get_irn_n_edges(remat->proj) == 0) {
2175 set_irn_n(remat->proj, -1, bad);
2176 set_irn_n(remat->proj, 0, bad);
2179 if(get_irn_n_edges(remat->op) == 0) {
2180 for (i = -1, n = get_irn_arity(remat->op); i < n; ++i) {
2181 set_irn_n(remat->op, i, bad);
2186 if(remat_info->remats) del_pset(remat_info->remats);
2187 if(remat_info->remats_by_operand) del_pset(remat_info->remats_by_operand);
2192 delete_unnecessary_remats(spill_ilp_t * si)
2196 ir_node *bad = get_irg_bad(si->chordal_env->irg);
2200 ir_node *end = get_irg_end(si->chordal_env->irg);
2203 for (i = 0, n = get_irn_arity(si->keep); i < n; ++i) {
2204 ir_node *keep_arg = get_irn_n(si->keep, i);
2205 op_t *arg_op = get_irn_link(keep_arg);
2208 assert(arg_op->is_remat);
2210 name = si->lpp->vars[arg_op->attr.remat.ilp];
2212 if(is_zero(name->value)) {
2213 DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", keep_arg));
2214 /* TODO check whether reload is preferred over remat (could be bug) */
2215 delete_remat(si, keep_arg);
2217 if(arg_op->attr.remat.pre) {
2218 DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", keep_arg));
2220 DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", keep_arg));
2224 set_irn_n(si->keep, i, bad);
2227 for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
2228 ir_node *end_arg = get_End_keepalive(end, i);
2230 if(end_arg != si->keep) {
2231 obstack_grow(si->obst, &end_arg, sizeof(end_arg));
2234 keeps = obstack_finish(si->obst);
2235 set_End_keepalives(end, n-1, keeps);
2236 obstack_free(si->obst, keeps);
2239 DBG((si->dbg, LEVEL_2, "\t no remats to delete (none have been inserted)\n"));
2244 pset_foreach(si->all_possible_remats, remat) {
2245 op_t *remat_op = get_irn_link(remat);
2246 lpp_name_t *name = si->lpp->vars[remat_op->attr.remat.ilp];
2248 if(is_zero(name->value)) {
2249 DBG((si->dbg, LEVEL_3, "\t deleting remat %+F\n", remat));
2250 /* TODO check whether reload is preferred over remat (could be bug) */
2251 delete_remat(si, remat);
2253 if(remat_op->attr.remat.pre) {
2254 DBG((si->dbg, LEVEL_2, "\t**remat kept: %+F\n", remat));
2256 DBG((si->dbg, LEVEL_2, "\t%%%%remat2 kept: %+F\n", remat));
2264 * @param before The node after which the spill will be placed in the schedule
2266 /* TODO set context properly */
2268 insert_spill(spill_ilp_t * si, const ir_node * irn, const ir_node * value, const ir_node * before)
2272 const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
2274 DBG((si->dbg, LEVEL_3, "\t inserting spill for value %+F after %+F\n", irn, before));
2276 spill = be_spill2(arch_env, irn, before, irn);
2278 defs = set_insert_def(si->values, value);
2281 /* enter into the linked list */
2282 set_irn_link(spill, defs->spills);
2283 defs->spills = spill;
2285 #ifdef KEEPALIVE_SPILLS
2294 * Add remat to list of defs, destroys link field!
2297 insert_remat(spill_ilp_t * si, ir_node * remat)
2300 op_t *remat_op = get_irn_link(remat);
2302 assert(remat_op->is_remat);
2304 defs = set_insert_def(si->values, remat_op->attr.remat.remat->value);
2307 /* enter into the linked list */
2308 set_irn_link(remat, defs->remats);
2309 defs->remats = remat;
2313 collect_spills(spill_ilp_t * si, ir_node * value, pset * spills, pset * visited)
2318 defs = set_find_def(si->values, value);
2320 if(defs && defs->spills) {
2321 for(next = defs->spills; next; next = get_irn_link(next)) {
2322 pset_insert_ptr(spills, next);
2324 } else if (is_Phi(value)) {
2326 if(!pset_find_ptr(visited, value)) {
2330 pset_insert_ptr(visited, value);
2331 for(i=0, n=get_irn_arity(value); i<n; ++i) {
2332 ir_node *arg = get_irn_n(value, i);
2334 collect_spills(si, arg, spills, visited);
2338 // assert(0 && "Phi operand not spilled");
2343 get_spills_for_value(spill_ilp_t * si, ir_node * value)
2345 pset *spills = pset_new_ptr_default();
2346 pset *visited = pset_new_ptr_default();
2348 collect_spills(si, value, spills, visited);
2355 * Add reload before operation and add to list of defs
2358 insert_reload(spill_ilp_t * si, const ir_node * value, const ir_node * after)
2363 const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
2365 DBG((si->dbg, LEVEL_3, "\t inserting reload for value %+F before %+F\n", value, after));
2367 defs = set_find_def(si->values, value);
2368 /* get a spill of this value */
2369 if((!defs || !defs->spills) && is_Phi(value)) {
2372 spills = get_spills_for_value(si, value);
2374 spill = pset_first(spills);
2378 defs = set_insert_def(si->values, value);
2381 spill = defs->spills;
2383 assert(spill && "no spill placed before reload");
2385 reload = be_reload(arch_env, si->cls, after, get_irn_mode(value), spill);
2387 /* enter into the linked list */
2388 set_irn_link(reload, defs->remats);
2389 defs->remats = reload;
2396 walker_spill_placer(ir_node * bb, void * data) {
2397 spill_ilp_t *si = (spill_ilp_t*)data;
2399 spill_bb_t *spill_bb = get_irn_link(bb);
2400 pset *spills_to_do = pset_new_ptr_default();
2403 set_foreach(spill_bb->ilp, spill) {
2406 assert(spill->spill > 0);
2408 if(is_Phi(spill->irn) && get_nodes_block(spill->irn) == bb) {
2409 name = si->lpp->vars[spill->mem_in];
2410 if(!is_zero(name->value)) {
2411 DBG((si->dbg, LEVEL_2, "\t >>spilled Phi %+F\n", spill->irn));
2415 name = si->lpp->vars[spill->spill];
2416 if(!is_zero(name->value)) {
2417 if(spill->reg_in > 0) {
2418 name = si->lpp->vars[spill->reg_in];
2419 if(!is_zero(name->value)) {
2420 insert_spill(si, spill->irn, spill->irn, bb);
2424 pset_insert_ptr(spills_to_do, spill->irn);
2427 DBG((si->dbg, LEVEL_3, "\t %d spills to do in block %+F\n", pset_count(spills_to_do), bb));
2430 for(irn = sched_block_first_nonphi(bb); !sched_is_end(irn); irn = sched_next(irn)) {
2431 op_t *op = get_irn_link(irn);
2433 if(be_is_Spill(irn)) continue;
2436 /* TODO fix this if we want to support remats with more than two nodes */
2437 if(get_irn_mode(irn) != mode_T && pset_find_ptr(spills_to_do, op->attr.remat.remat->value)) {
2438 pset_remove_ptr(spills_to_do, op->attr.remat.remat->value);
2440 insert_spill(si, irn, op->attr.remat.remat->value, irn);
2443 if(pset_find_ptr(spills_to_do, irn)) {
2444 pset_remove_ptr(spills_to_do, irn);
2446 insert_spill(si, irn, irn, irn);
2452 assert(pset_count(spills_to_do) == 0);
2454 /* afterwards free data in block */
2455 del_pset(spills_to_do);
2459 walker_reload_placer(ir_node * bb, void * data) {
2460 spill_ilp_t *si = (spill_ilp_t*)data;
2462 spill_bb_t *spill_bb = get_irn_link(bb);
2466 sched_foreach_reverse(bb, irn) {
2467 op_t *op = get_irn_link(irn);
2469 if(be_is_Reload(irn) || be_is_Spill(irn)) continue;
2470 if(is_Phi(irn)) break;
2473 if(get_irn_mode(irn) != mode_T) {
2474 insert_remat(si, irn);
2479 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
2480 ir_node *arg = get_irn_n(irn, i);
2482 if(op->attr.live_range.reloads && op->attr.live_range.reloads[i] != ILP_UNDEF) {
2485 name = si->lpp->vars[op->attr.live_range.reloads[i]];
2486 if(!is_zero(name->value)) {
2488 ir_node *insert_pos = irn;
2489 ir_node *prev = sched_prev(insert_pos);
2490 op_t *prev_op = get_irn_link(prev);
2492 /* insert reload before pre-remats */
2493 while(!sched_is_end(prev) && !be_is_Reload(prev) && !be_is_Spill(prev)
2494 && prev_op->is_remat && prev_op->attr.remat.pre) {
2497 prev = sched_prev(insert_pos);
2498 prev_op = get_irn_link(prev);
2501 reload = insert_reload(si, arg, insert_pos);
2503 set_irn_n(irn, i, reload);
2506 #ifdef KEEPALIVE_SPILLS
2516 live_foreach(bb, li) {
2517 ir_node *irn = (ir_node *) li->irn;
2519 if (live_is_end(li) && has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
2522 name = si->lpp->vars[spill_bb->reloads[i]];
2523 if(!is_zero(name->value)) {
2525 ir_node *insert_pos = bb;
2526 ir_node *prev = sched_prev(insert_pos);
2527 op_t *prev_op = get_irn_link(prev);
2529 /* insert reload before pre-remats */
2530 while(!sched_is_end(prev) && !be_is_Reload(prev) && !be_is_Spill(prev)
2531 && prev_op->is_remat && prev_op->attr.remat.pre) {
2534 prev = sched_prev(insert_pos);
2535 prev_op = get_irn_link(prev);
2538 reload = insert_reload(si, irn, insert_pos);
2540 #ifdef KEEPALIVE_SPILLS
2548 del_set(spill_bb->ilp);
2552 walker_collect_used(ir_node * irn, void * data)
2554 lc_bitset_t *used = data;
2556 lc_bitset_set(used, get_irn_idx(irn));
2560 walker_kill_unused(ir_node * bb, void * data)
2562 lc_bitset_t *used = data;
2563 const ir_node *bad = get_irg_bad(get_irn_irg(bb));
2567 for(irn=sched_first(bb); !sched_is_end(irn);) {
2568 ir_node *next = sched_next(irn);
2572 if(!lc_bitset_is_set(used, get_irn_idx(irn))) {
2573 assert(!be_is_Spill(irn) && !be_is_Reload(irn) && "something is fishy, spill or remat is unused");
2577 set_nodes_block(irn, bad);
2578 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
2579 ir_node *arg = get_irn_n(irn, i);
2581 set_irn_n(irn, i, bad);
2589 kill_all_unused_values_in_schedule(spill_ilp_t * si)
2591 lc_bitset_t *used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
2593 irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, used);
2594 irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, used);
2596 lc_bitset_free(used);
2600 print_irn_pset(pset * p)
2604 pset_foreach(p, irn) {
2605 ir_printf("%+F\n", irn);
2610 rewire_uses(spill_ilp_t * si)
2612 dom_front_info_t *dfi = be_compute_dominance_frontiers(si->chordal_env->irg);
2615 /* then fix uses of spills */
2616 set_foreach(si->values, defs) {
2619 ir_node *next = defs->remats;
2623 reloads = pset_new_ptr_default();
2626 if(be_is_Reload(next)) {
2627 pset_insert_ptr(reloads, next);
2631 next = get_irn_link(next);
2634 spills = get_spills_for_value(si, defs->value);
2635 DBG((si->dbg, LEVEL_2, "\t %d remats, %d reloads, and %d spills for value %+F\n", remats, pset_count(reloads), pset_count(spills), defs->value));
2636 if(pset_count(spills) > 1) {
2637 assert(pset_count(reloads) > 0);
2638 // print_irn_pset(spills);
2639 // print_irn_pset(reloads);
2640 be_ssa_constr_set_uses(dfi, spills, reloads);
2648 /* first fix uses of remats and reloads */
2649 set_foreach(si->values, defs) {
2651 ir_node *next = defs->remats;
2654 nodes = pset_new_ptr_default();
2655 pset_insert_ptr(nodes, defs->value);
2658 pset_insert_ptr(nodes, next);
2659 next = get_irn_link(next);
2662 if(pset_count(nodes) > 1) {
2663 DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-1, defs->value));
2664 be_ssa_constr_set(dfi, nodes);
2671 // remove_unused_defs(si);
2673 be_free_dominance_frontiers(dfi);
2677 writeback_results(spill_ilp_t * si)
2679 /* walk through the graph and collect all spills, reloads and remats for a value */
2681 si->values = new_set(cmp_defs, 4096);
2683 DBG((si->dbg, LEVEL_1, "Applying results\n"));
2684 delete_unnecessary_remats(si);
2685 irg_block_walk_graph(si->chordal_env->irg, walker_spill_placer, NULL, si);
2686 irg_block_walk_graph(si->chordal_env->irg, walker_reload_placer, NULL, si);
2688 /* clean the remat info! there are still back-edges leading there! */
2689 clean_remat_info(si);
2693 del_set(si->values);
2697 get_n_regs(spill_ilp_t * si)
2699 int arch_n_regs = arch_register_class_n_regs(si->cls);
2703 for(i=0; i<arch_n_regs; i++) {
2704 if(!arch_register_type_is(&si->cls->regs[i], ignore)) {
2709 DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", free, si->cls->name));
2714 #define enqueue(r) if(reloads[ins_pos]) put(); \
2715 assert(reloads[ins_pos]==NULL); \
2716 reload[ins_pos] = (r); \
2717 ins_pos = (ins_pos+1)%si->n_regs; \
2719 #define put() if(reloads[del_pos]) sched_put_before(irn, reloads[del_pos]); \
2720 reloads[del_pos] = NULL; \
2721 del_pos = (del_pos+1)%si->n_regs; \
2725 walker_reload_mover(ir_node * bb, void * data)
2727 spill_ilp_t *si = data;
2730 sched_foreach(bb, irn) {
2731 if(be_is_Reload(irn) && has_reg_class(si, irn)) {
2732 ir_node *reload = irn;
2735 /* move reload upwards */
2737 int pressure = (int)get_irn_link(reload);
2738 if(pressure < si->n_regs) {
2739 irn = sched_prev(reload);
2740 DBG((si->dbg, LEVEL_5, "regpressure before %+F: %d\n", reload, pressure));
2741 sched_remove(reload);
2742 pressure = (int)get_irn_link(irn);
2744 while(pressure < si->n_regs) {
2745 if(sched_is_end(irn) || (be_is_Reload(irn) && has_reg_class(si, irn))) break;
2747 set_irn_link(irn, (void*)(pressure+1));
2748 DBG((si->dbg, LEVEL_5, "new regpressure before %+F: %d\n", irn, pressure+1));
2749 irn = sched_prev(irn);
2751 pressure = (int)get_irn_link(irn);
2754 DBG((si->dbg, LEVEL_3, "putting reload %+F after %+F\n", reload, irn));
2755 sched_put_after(irn, reload);
2756 // sched_add_after(irn, reload);
2757 // pressure = (int)get_irn_link(sched_next(reload));
2758 // set_irn_link(reload, (void*)(pressure-1));
2765 move_reloads_upward(spill_ilp_t * si)
2767 irg_block_walk_graph(si->chordal_env->irg, walker_reload_mover, NULL, si);
2771 be_spill_remat(const be_chordal_env_t * chordal_env)
2773 char problem_name[256];
2774 char dump_suffix[256];
2775 char dump_suffix2[256];
2776 char dump_suffix3[256];
2777 struct obstack obst;
2780 ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name);
2781 ir_snprintf(dump_suffix, sizeof(dump_suffix), "-%s-remats", chordal_env->cls->name);
2782 ir_snprintf(dump_suffix2, sizeof(dump_suffix2), "-%s-pressure", chordal_env->cls->name);
2783 ir_snprintf(dump_suffix2, sizeof(dump_suffix3), "-%s-reloads_moved", chordal_env->cls->name);
2785 FIRM_DBG_REGISTER(si.dbg, "firm.be.ra.spillremat");
2786 DBG((si.dbg, LEVEL_1, "\n\n\t\t===== Processing %s =====\n\n", problem_name));
2788 obstack_init(&obst);
2789 si.chordal_env = chordal_env;
2791 si.senv = be_new_spill_env(chordal_env, is_mem_phi, &si);
2792 si.cls = chordal_env->cls;
2793 si.lpp = new_lpp(problem_name, lpp_minimize);
2794 si.remat_info = new_set(cmp_remat_info, 4096);
2795 si.all_possible_remats = pset_new_ptr_default();
2796 #ifndef EXECFREQ_LOOPDEPH
2797 si.execfreqs = compute_execfreq(chordal_env->irg);
2802 si.n_regs = get_n_regs(&si);
2804 set_irg_link(chordal_env->irg, &si);
2805 compute_doms(chordal_env->irg);
2807 #ifdef COLLECT_REMATS
2808 // irg_block_walk_graph(chordal_env->irg, process_block, NULL, &si);
2809 /* collect remats */
2810 DBG((si.dbg, LEVEL_1, "Collecting remats\n"));
2811 irg_walk_graph(chordal_env->irg, walker_remat_collector, NULL, &si);
2814 /* insert possible remats */
2815 DBG((si.dbg, LEVEL_1, "Inserting possible remats\n"));
2816 irg_block_walk_graph(chordal_env->irg, walker_remat_insertor, NULL, &si);
2817 DBG((si.dbg, LEVEL_2, " -> inserted %d possible remats\n", pset_count(si.all_possible_remats)));
2820 DBG((si.dbg, LEVEL_1, "Connecting remats with keep and dumping\n"));
2821 connect_all_remats_with_keep(&si);
2822 /* dump graph with inserted remats */
2823 dump_graph_with_remats(chordal_env->irg, dump_suffix);
2827 /* recompute liveness */
2828 DBG((si.dbg, LEVEL_1, "Recomputing liveness\n"));
2829 be_liveness(chordal_env->irg);
2833 DBG((si.dbg, LEVEL_1, "\tBuilding ILP\n"));
2834 DBG((si.dbg, LEVEL_2, "\t endwalker\n"));
2835 irg_block_walk_graph(chordal_env->irg, luke_endwalker, NULL, &si);
2837 DBG((si.dbg, LEVEL_2, "\t blockwalker\n"));
2838 irg_block_walk_graph(chordal_env->irg, luke_blockwalker, NULL, &si);
2845 ir_snprintf(buf, sizeof(buf), "%s-spillremat.ilp", problem_name);
2846 if ((f = fopen(buf, "wt")) != NULL) {
2847 lpp_dump_plain(si.lpp, f);
2854 DBG((si.dbg, LEVEL_1, "\tSolving %F\n", chordal_env->irg));
2855 lpp_set_time_limit(si.lpp, ILP_TIMEOUT);
2858 lpp_solve_cplex(si.lpp);
2860 lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
2862 assert(lpp_is_sol_valid(si.lpp)
2863 && "solution of ILP must be valid");
2865 DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, si.lpp->objval));
2867 #ifdef DUMP_SOLUTION
2872 ir_snprintf(buf, sizeof(buf), "%s-spillremat.sol", problem_name);
2873 if ((f = fopen(buf, "wt")) != NULL) {
2875 for (i = 0; i < si.lpp->var_next; ++i) {
2876 lpp_name_t *name = si.lpp->vars[i];
2877 fprintf(f, "%20s %4d %10f\n", name->name, name->nr, name->value);
2884 writeback_results(&si);
2888 kill_all_unused_values_in_schedule(&si);
2890 be_liveness(chordal_env->irg);
2891 irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
2893 dump_pressure_graph(&si, dump_suffix2);
2895 // TODO fix temporarily exceeded regpressure due to remat2s
2897 // TODO insert copys to fix interferences in memory
2899 // move reloads upwards
2900 move_reloads_upward(&si);
2901 irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
2902 dump_pressure_graph(&si, dump_suffix3);
2904 free_dom(chordal_env->irg);
2905 del_pset(si.all_possible_remats);
2906 #ifndef EXECFREQ_LOOPDEPH
2907 del_set(si.execfreqs);
2910 obstack_free(&obst, NULL);
2914 #else /* WITH_ILP */
2917 only_that_you_can_compile_without_WITH_ILP_defined(void)
2921 #endif /* WITH_ILP */