4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 #include "bechordal_t.h"
18 #include "becopyopt.h"
19 #include "becopystat.h"
21 #define DEBUG_LVL 0 //SET_LEVEL_1
22 static firm_dbg_module_t *dbg = NULL;
24 #define is_curr_reg_class(irn) (arch_get_irn_reg_class(co->chordal_env->arch_env, irn, arch_pos_make_out(0)) == co->chordal_env->cls)
26 #define MIN(a,b) ((a<b)?(a):(b))
29 * Computes a 'max independent set' wrt. ifg-edges only (no coloring conflicts, no register constraints)
30 * @return The size of such a mis
31 * NOTE: Code adapted from becopyheur
32 * BETTER: Here we can be sure having a chordal graph to work on, so for 'larger' opt-units we
33 * could use a special algorithm.
35 static int get_ifg_mis_size(unit_t *ou) {
36 int all_size, curr_size, i, o;
38 ir_node **curr, **all = alloca(ou->node_count * sizeof(*all));
40 /* all contains all nodes */
42 for (i=0; i<ou->node_count; ++i)
43 all[all_size++] = ou->nodes[i];
45 /* which[i] says which element to take out of all[] and put into curr[i] */
46 which = alloca(all_size*sizeof(*which));
47 for (curr_size=0; curr_size<all_size; ++curr_size)
48 which[curr_size] = curr_size;
50 /* stores the currently examined set */
51 curr = alloca(all_size*sizeof(*curr));
53 while (1) { /* this loop will terminate because at least a single node will be a max indep. set */
54 /* build current set */
55 for (i=0; i<curr_size; ++i)
56 curr[i] = all[which[all_size-curr_size+i]];
58 /* check current set */
59 for (i=0; i<curr_size; ++i)
60 for (o=i+1; o<curr_size; ++o)
61 if (nodes_interfere(ou->co->chordal_env, curr[i], curr[o]))
64 /* We had no conflict. This is the (one) max indep. set */
68 /* We had a conflict. Generate next set */
69 if (which[all_size-curr_size+1] == all_size-curr_size+1) {
71 for (i=0; i<curr_size; ++i)
72 which[all_size-curr_size+i] = i;
79 } while (!(which[pos] = (which[pos]+1) % all_size));
81 for (i=pos+1; i<all_size; ++i)
82 which[i] = MIN(which[i-1]+1, all_size-1);
85 for (i=all_size-curr_size; i<all_size-1; ++i)
86 if (which[i]>=which[i+1]) {
93 assert(0 && "How did you get here?");
97 * Builds an optimization unit for a given optimizable irn (root).
98 * This opt-unit is inserted in the main structure co.
99 * If an arg of root itself is optimizable process this arg before with a
100 * recursive call. For handling this situation and loops co->root is used
101 * to remember all roots.
103 static void co_append_unit(copy_opt_t *co, ir_node *root) {
106 DBG((dbg, LEVEL_1, "\t Root: %n\n", root));
107 /* check if we encountered this root earlier */
108 if (pset_find_ptr(co->roots, root))
110 pset_insert_ptr(co->roots, root);
112 assert(is_curr_reg_class(root) && "node is in wrong register class!");
115 arity = get_irn_arity(root);
116 unit = xcalloc(1, sizeof(*unit));
119 unit->node_count = 1;
120 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
121 unit->nodes[0] = root;
122 INIT_LIST_HEAD(&unit->queue);
125 for (i=0; i<arity; ++i) {
126 ir_node *arg = get_irn_n(root, i);
127 assert(is_curr_reg_class(arg) && "Argument not in same register class.");
129 if (!nodes_interfere(co->chordal_env, root, arg)) {
130 DBG((dbg, LEVEL_1, "\t Member: %n\n", arg));
131 if (is_optimizable(arg))
132 co_append_unit(co, arg);
133 unit->nodes[unit->node_count++] = arg;
138 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
139 list_add_tail(&unit->units, &co->units);
140 /* Init ifg_mis_size to node_count. So get_lower_bound returns correct results. */
141 unit->ifg_mis_size = get_ifg_mis_size(unit);
144 static void co_collect_in_block(ir_node *block, void *env) {
145 copy_opt_t *co = env;
146 struct list_head *head = get_block_border_head(co->chordal_env, block);
149 list_for_each_entry_reverse(border_t, curr, head, list)
150 if (curr->is_def && curr->is_real && is_optimizable(curr->irn))
151 co_append_unit(co, curr->irn);
154 static void co_collect_units(copy_opt_t *co) {
155 DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
156 co->roots = pset_new_ptr(64);
157 dom_tree_walk_irg(co->chordal_env->irg, co_collect_in_block, NULL, co);
161 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env) {
162 const char *s1, *s2, *s3;
166 dbg = firm_dbg_register("ir.be.copyopt");
167 firm_dbg_set_mask(dbg, DEBUG_LVL);
169 co = xcalloc(1, sizeof(*co));
170 co->chordal_env = chordal_env;
172 s1 = get_irp_prog_name();
173 s2 = get_entity_name(get_irg_entity(co->chordal_env->irg));
174 s3 = chordal_env->cls->name;
175 len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
176 co->name = xmalloc(len);
177 if (!strcmp(co->name, DEBUG_IRG))
178 firm_dbg_set_mask(dbg, -1);
179 snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
181 INIT_LIST_HEAD(&co->units);
182 co_collect_units(co);
186 void free_copy_opt(copy_opt_t *co) {
189 list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
195 int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
197 for(i=0, max=get_irn_n_outs(irn); i<max; ++i) {
198 ir_node *n = get_irn_out(irn, i);
199 if (is_optimizable(n) && (irn == n || !nodes_interfere(co->chordal_env, irn, n)))
206 int co_get_copy_count(const copy_opt_t *co) {
209 list_for_each_entry(unit_t, curr, &co->units, units) {
210 int root_col = get_irn_col(co, curr->nodes[0]);
212 for (i=1; i<curr->node_count; ++i)
213 if (root_col != get_irn_col(co, curr->nodes[i]))
219 int co_get_lower_bound(const copy_opt_t *co) {
222 list_for_each_entry(unit_t, curr, &co->units, units)
223 res += curr->interf + curr->node_count - curr->ifg_mis_size;
227 int co_get_interferer_count(const copy_opt_t *co) {
230 list_for_each_entry(unit_t, curr, &co->units, units)
236 * Needed for result checking
238 static void co_collect_for_checker(ir_node *block, void *env) {
239 copy_opt_t *co = env;
240 struct list_head *head = get_block_border_head(co->chordal_env, block);
243 list_for_each_entry_reverse(border_t, curr, head, list)
244 if (curr->is_def && curr->is_real && is_curr_reg_class(curr->irn))
245 obstack_ptr_grow(&co->ob, curr->irn);
249 * This O(n^2) checker checks if
250 * two ifg-connected nodes have the same color
251 * register constraint are satisfied
253 void co_check_allocation(copy_opt_t *co) {
254 ir_node **nodes, *n1, *n2;
257 obstack_init(&co->ob);
258 dom_tree_walk_irg(co->chordal_env->irg, co_collect_for_checker, NULL, co);
259 obstack_ptr_grow(&co->ob, NULL);
261 nodes = (ir_node **) obstack_finish(&co->ob);
262 for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
263 assert(arch_reg_is_allocatable(co->chordal_env->arch_env, n1, arch_pos_make_out(0),
264 arch_get_irn_register(co->chordal_env->arch_env, n1, 0)) && "Constraint does not hold");
265 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
266 if (nodes_interfere(co->chordal_env, n1, n2)
267 && get_irn_col(co, n1) == get_irn_col(co, n2)) {
268 DBG((dbg, 0, "Error: %n %d and %n %d have the same color %d.\n", n1, get_irn_graph_nr(n1), n2, get_irn_graph_nr(n2), get_irn_col(co, n1)));
269 assert(0 && "Interfering values have the same color!");
272 obstack_free(&co->ob, NULL);
273 DBG((dbg, 2, "The checker seems to be happy!\n"));