4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 #include <libcore/lc_timing.h>
26 #include "iredges_t.h"
31 #include "becopyopt_t.h"
32 #include "becopystat.h"
36 static firm_dbg_module_t *dbg = NULL;
39 * Determines a maximum weighted independent set with respect to
40 * the interference and conflict edges of all nodes in a qnode.
42 static int ou_max_ind_set_costs(unit_t *ou) {
43 be_chordal_env_t *chordal_env = ou->co->cenv;
44 ir_node **safe, **unsafe;
45 int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
47 int max, pos, curr_weight, best_weight = 0;
49 /* assign the nodes into two groups.
50 * safe: node has no interference, hence it is in every max stable set.
51 * unsafe: node has an interference
53 safe = alloca((ou->node_count-1) * sizeof(*safe));
56 unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
57 unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
59 for(i=1; i<ou->node_count; ++i) {
61 for(o=1; o<ou->node_count; ++o) {
64 if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
65 unsafe_costs[unsafe_count] = ou->costs[i];
66 unsafe[unsafe_count] = ou->nodes[i];
73 safe_costs += ou->costs[i];
74 safe[safe_count++] = ou->nodes[i];
79 /* now compute the best set out of the unsafe nodes*/
80 if (unsafe_count > MIS_HEUR_TRIGGER) {
81 bitset_t *best = bitset_alloca(unsafe_count);
82 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
83 for (i=0; i<unsafe_count; ++i) {
85 /* check if it is a stable set */
86 for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
87 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
88 bitset_clear(best, i); /* clear the bit and try next one */
92 /* compute the weight */
93 bitset_foreach(best, pos)
94 best_weight += unsafe_costs[pos];
96 /* Exact Algorithm: Brute force */
97 curr = bitset_alloca(unsafe_count);
99 while ((max = bitset_popcnt(curr)) != 0) {
100 /* check if curr is a stable set */
101 for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
102 for (o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */
103 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
106 /* if we arrive here, we have a stable set */
107 /* compute the weigth of the stable set*/
109 bitset_foreach(curr, pos)
110 curr_weight += unsafe_costs[pos];
113 if (curr_weight > best_weight) {
114 best_weight = curr_weight;
122 return safe_costs+best_weight;
125 static void co_collect_units(ir_node *irn, void *env) {
126 copy_opt_t *co = env;
128 arch_register_req_t req;
130 if (!is_curr_reg_class(co, irn))
132 if (!co_is_optimizable(co->aenv, irn, &req))
135 /* Init a new unit */
136 unit = xcalloc(1, sizeof(*unit));
138 unit->node_count = 1;
139 INIT_LIST_HEAD(&unit->queue);
141 /* Phi with some/all of its arguments */
142 if (is_Reg_Phi(irn)) {
146 arity = get_irn_arity(irn);
147 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
148 unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
149 unit->nodes[0] = irn;
152 for (i=0; i<arity; ++i) {
154 ir_node *arg = get_irn_n(irn, i);
156 assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
159 if (nodes_interfere(co->cenv, irn, arg)) {
160 unit->inevitable_costs += co->get_costs(irn, arg, i);
164 /* Else insert the argument of the phi to the members of this ou */
165 DBG((dbg, LEVEL_1, "\t Member: %+F\n", arg));
167 /* Check if arg has occurred at a prior position in the arg/list */
169 for (o=0; o<unit->node_count; ++o)
170 if (unit->nodes[o] == arg) {
175 if (!arg_pos) { /* a new argument */
176 /* insert node, set costs */
177 unit->nodes[unit->node_count] = arg;
178 unit->costs[unit->node_count] = co->get_costs(irn, arg, i);
180 } else { /* arg has occured before in same phi */
181 /* increase costs for existing arg */
182 unit->costs[arg_pos] += co->get_costs(irn, arg, i);
185 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
186 unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
189 /* Proj of a perm with corresponding arg */
190 if (is_Perm_Proj(co->aenv, irn)) {
191 assert(!nodes_interfere(co->cenv, irn, get_Copy_src(irn)));
192 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
193 unit->costs = xmalloc(2 * sizeof(*unit->costs));
194 unit->node_count = 2;
195 unit->nodes[0] = irn;
196 unit->nodes[1] = get_Copy_src(irn);
197 unit->costs[1] = co->get_costs(irn, unit->nodes[1], -1);
200 /* Src == Tgt of a 2-addr-code instruction */
201 if (is_2addr_code(co->aenv, irn, &req)) {
202 ir_node *other = req.other_same;
203 if (!nodes_interfere(co->cenv, irn, other)) {
204 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
205 unit->costs = xmalloc(2 * sizeof(*unit->costs));
206 unit->node_count = 2;
207 unit->nodes[0] = irn;
208 unit->nodes[1] = other;
209 unit->costs[1] = co->get_costs(irn, other, -120480);
212 assert(0 && "This is not an optimizable node!");
214 /* Insert the new unit at a position according to its costs */
215 if (unit->node_count > 1) {
217 struct list_head *tmp;
219 /* Determine the maximum costs this unit can cause: all_nodes_cost */
220 for(i=1; i<unit->node_count; ++i) {
221 unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
222 unit->all_nodes_costs += unit->costs[i];
225 /* Determine the minimal costs this unit will cause: min_nodes_costs */
226 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
228 /* Insert the new ou according to its sort_key */
230 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
232 list_add(&unit->units, tmp);
238 void be_copy_opt_init(void) {
239 dbg = firm_dbg_register("ir.be.copyoptmain");
242 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int)) {
243 const char *s1, *s2, *s3;
247 dbg = firm_dbg_register("ir.be.copyopt");
249 co = xcalloc(1, sizeof(*co));
250 co->cenv = chordal_env;
251 co->aenv = chordal_env->birg->main_env->arch_env;
252 co->irg = chordal_env->irg;
253 co->cls = chordal_env->cls;
254 co->get_costs = get_costs;
256 s1 = get_irp_prog_name();
257 s2 = get_entity_name(get_irg_entity(co->irg));
258 s3 = chordal_env->cls->name;
259 len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
260 co->name = xmalloc(len);
261 snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
263 DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
264 INIT_LIST_HEAD(&co->units);
265 irg_walk_graph(co->irg, co_collect_units, NULL, co);
269 void free_copy_opt(copy_opt_t *co) {
272 list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
279 int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
280 const ir_edge_t *edge;
282 if (arch_irn_is_ignore(co->aenv, irn))
285 foreach_out_edge(irn, edge) {
286 ir_node *n = edge->src;
288 if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
289 arch_register_req_t req;
290 arch_get_register_req(co->aenv, &req, n, -1);
293 is_Perm(co->aenv, n) ||
294 (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
303 int get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) {
306 ir_node *root_block = get_nodes_block(root);
309 /* for phis the copies are placed in the corresponding pred-block */
310 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
312 /* a perm places the copy in the same block as it resides */
313 loop = get_irn_loop(root_block);
316 int d = get_loop_depth(loop);
322 int get_costs_all_one(ir_node *root, ir_node* arg, int pos) {
326 int co_get_max_copy_costs(const copy_opt_t *co) {
330 list_for_each_entry(unit_t, curr, &co->units, units) {
331 res += curr->inevitable_costs;
332 for (i=1; i<curr->node_count; ++i)
333 res += curr->costs[i];
338 int co_get_inevit_copy_costs(const copy_opt_t *co) {
342 list_for_each_entry(unit_t, curr, &co->units, units)
343 res += curr->inevitable_costs;
347 int co_get_copy_costs(const copy_opt_t *co) {
351 list_for_each_entry(unit_t, curr, &co->units, units) {
352 int root_col = get_irn_col(co, curr->nodes[0]);
353 DBG((dbg, LEVEL_1, " %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
354 res += curr->inevitable_costs;
355 for (i=1; i<curr->node_count; ++i) {
356 int arg_col = get_irn_col(co, curr->nodes[i]);
357 if (root_col != arg_col) {
358 DBG((dbg, LEVEL_1, " %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
359 res += curr->costs[i];
366 int co_get_lower_bound(const copy_opt_t *co) {
369 list_for_each_entry(unit_t, curr, &co->units, units)
370 res += curr->inevitable_costs + curr->min_nodes_costs;
382 * Helpers for saving and restoring colors of nodes.
383 * Used to get dependable and comparable benchmark results.
385 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
387 typedef struct color_saver {
388 arch_env_t *arch_env;
389 be_chordal_env_t *chordal_env;
391 int flag; /* 0 save, 1 load */
394 static void save_load(ir_node *irn, void *env) {
395 color_save_t *saver = env;
396 if (saver->chordal_env->cls == arch_get_irn_reg_class(saver->arch_env, irn, -1)) {
397 if (saver->flag == 0) { /* save */
398 const arch_register_t *reg = arch_get_irn_register(saver->arch_env, irn);
399 pmap_insert(saver->saved_colors, irn, (void *) reg);
401 arch_register_t *reg = pmap_get(saver->saved_colors, irn);
402 arch_set_irn_register(saver->arch_env, irn, reg);
407 static void save_colors(color_save_t *color_saver) {
408 color_saver->flag = 0;
409 irg_walk_graph(color_saver->chordal_env->irg, save_load, NULL, color_saver);
412 static void load_colors(color_save_t *color_saver) {
413 color_saver->flag = 1;
414 irg_walk_graph(color_saver->chordal_env->irg, save_load, NULL, color_saver);
417 #endif /* Need save/load stuff */
421 void co_compare_solvers(be_chordal_env_t *chordal_env) {
427 int costs, costs_inevit, costs_init, costs_heur, costs_classes, costs_ilp, lower_bound;
430 co = new_copy_opt(chordal_env, get_costs_loop_depth);
431 DBG((dbg, LEVEL_1, "----> CO: %s\n", co->name));
432 phi_class_compute(chordal_env->irg);
436 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
437 saver.arch_env = chordal_env->main_env->arch_env;
438 saver.chordal_env = chordal_env;
439 saver.saved_colors = pmap_create();
443 costs_inevit = co_get_inevit_copy_costs(co);
444 lower_bound = co_get_lower_bound(co);
445 costs_init = co_get_copy_costs(co);
447 DBG((dbg, LEVEL_1, "Inevit Costs: %3d\n", costs_inevit));
448 DBG((dbg, LEVEL_1, "Lower Bound: %3d\n", lower_bound));
449 DBG((dbg, LEVEL_1, "Init costs: %3d\n", costs_init));
451 copystat_add_inevit_costs(costs_inevit);
452 copystat_add_init_costs(costs_init);
453 copystat_add_max_costs(co_get_max_copy_costs(co));
459 timer = lc_timer_register("heur", NULL);
460 lc_timer_reset_and_start(timer);
463 co_solve_heuristic(co);
466 lc_timer_stop(timer);
467 costs_heur = co_get_copy_costs(co);
468 DBG((dbg, LEVEL_1, "Heur costs: %3d\n", costs_heur));
469 copystat_add_heur_time(lc_timer_elapsed_msec(timer));
470 copystat_add_heur_costs(costs_heur);
471 assert(lower_bound <= costs_heur);
482 timer = lc_timer_register("classes", NULL);
483 lc_timer_reset_and_start(timer);
489 lc_timer_stop(timer);
490 costs_classes = co_get_copy_costs(co);
491 DBG((dbg, LEVEL_1, "Classes costs: %3d\n", costs_classes));
492 copystat_add_classes_time(lc_timer_elapsed_msec(timer));
493 copystat_add_classes_costs(costs_heur);
494 assert(lower_bound <= costs_classes);
496 #endif /* DO_CLASSES */
502 #if defined(DO_HEUR) || defined(DO_CLASSES)
507 co_solve_ilp1(co, 60.0);
510 costs_ilp = co_get_copy_costs(co);
511 DBG((dbg, LEVEL_1, "Opt costs: %3d\n", costs_ilp));
512 copystat_add_opt_costs(costs_ilp);
513 assert(lower_bound <= costs_ilp);
519 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
520 pmap_destroy(saver.saved_colors);