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"
35 static firm_dbg_module_t *dbg = NULL;
38 * Determines a maximum weighted independent set with respect to
39 * the interference and conflict edges of all nodes in a qnode.
41 static int ou_max_ind_set_costs(unit_t *ou) {
42 be_chordal_env_t *chordal_env = ou->co->cenv;
43 ir_node **safe, **unsafe;
44 int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
46 int max, pos, curr_weight, best_weight = 0;
48 /* assign the nodes into two groups.
49 * safe: node has no interference, hence it is in every max stable set.
50 * unsafe: node has an interference
52 safe = alloca((ou->node_count-1) * sizeof(*safe));
55 unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
56 unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
58 for(i=1; i<ou->node_count; ++i) {
60 for(o=1; o<ou->node_count; ++o) {
63 if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
64 unsafe_costs[unsafe_count] = ou->costs[i];
65 unsafe[unsafe_count] = ou->nodes[i];
72 safe_costs += ou->costs[i];
73 safe[safe_count++] = ou->nodes[i];
78 /* now compute the best set out of the unsafe nodes*/
79 if (unsafe_count > MIS_HEUR_TRIGGER) {
80 bitset_t *best = bitset_alloca(unsafe_count);
81 /* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
82 for (i=0; i<unsafe_count; ++i) {
84 /* check if it is a stable set */
85 for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
86 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
87 bitset_clear(best, i); /* clear the bit and try next one */
91 /* compute the weight */
92 bitset_foreach(best, pos)
93 best_weight += unsafe_costs[pos];
95 /* Exact Algorithm: Brute force */
96 curr = bitset_alloca(unsafe_count);
98 while ((max = bitset_popcnt(curr)) != 0) {
99 /* check if curr is a stable set */
100 for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
101 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) */
102 if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
105 /* if we arrive here, we have a stable set */
106 /* compute the weigth of the stable set*/
108 bitset_foreach(curr, pos)
109 curr_weight += unsafe_costs[pos];
112 if (curr_weight > best_weight) {
113 best_weight = curr_weight;
121 return safe_costs+best_weight;
124 static void co_collect_units(ir_node *irn, void *env) {
125 copy_opt_t *co = env;
127 arch_register_req_t req;
129 if (!is_curr_reg_class(co, irn))
131 if (!co_is_optimizable(co->aenv, irn, &req))
134 /* Init a new unit */
135 unit = xcalloc(1, sizeof(*unit));
137 unit->node_count = 1;
138 INIT_LIST_HEAD(&unit->queue);
140 /* Phi with some/all of its arguments */
141 if (is_Reg_Phi(irn)) {
145 arity = get_irn_arity(irn);
146 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
147 unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
148 unit->nodes[0] = irn;
151 for (i=0; i<arity; ++i) {
153 ir_node *arg = get_irn_n(irn, i);
155 assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
158 if (nodes_interfere(co->cenv, irn, arg)) {
159 unit->inevitable_costs += co->get_costs(irn, arg, i);
163 /* Else insert the argument of the phi to the members of this ou */
164 DBG((dbg, LEVEL_1, "\t Member: %+F\n", arg));
166 /* Check if arg has occurred at a prior position in the arg/list */
168 for (o=0; o<unit->node_count; ++o)
169 if (unit->nodes[o] == arg) {
174 if (!arg_pos) { /* a new argument */
175 /* insert node, set costs */
176 unit->nodes[unit->node_count] = arg;
177 unit->costs[unit->node_count] = co->get_costs(irn, arg, i);
179 } else { /* arg has occured before in same phi */
180 /* increase costs for existing arg */
181 unit->costs[arg_pos] += co->get_costs(irn, arg, i);
184 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
185 unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
188 /* Proj of a perm with corresponding arg */
189 if (is_Perm_Proj(co->aenv, irn)) {
190 assert(!nodes_interfere(co->cenv, irn, get_Copy_src(irn)));
191 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
192 unit->costs = xmalloc(2 * sizeof(*unit->costs));
193 unit->node_count = 2;
194 unit->nodes[0] = irn;
195 unit->nodes[1] = get_Copy_src(irn);
196 unit->costs[1] = co->get_costs(irn, unit->nodes[1], -1);
199 /* Src == Tgt of a 2-addr-code instruction */
200 if (is_2addr_code(co->aenv, irn, &req)) {
201 ir_node *other = req.other_same;
202 if (!nodes_interfere(co->cenv, irn, other)) {
203 unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
204 unit->costs = xmalloc(2 * sizeof(*unit->costs));
205 unit->node_count = 2;
206 unit->nodes[0] = irn;
207 unit->nodes[1] = other;
208 unit->costs[1] = co->get_costs(irn, other, -120480);
211 assert(0 && "This is not an optimizable node!");
213 /* Insert the new unit at a position according to its costs */
214 if (unit->node_count > 1) {
216 struct list_head *tmp;
218 /* Determine the maximum costs this unit can cause: all_nodes_cost */
219 for(i=1; i<unit->node_count; ++i) {
220 unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
221 unit->all_nodes_costs += unit->costs[i];
224 /* Determine the minimal costs this unit will cause: min_nodes_costs */
225 unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
227 /* Insert the new ou according to its sort_key */
229 while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
231 list_add(&unit->units, tmp);
237 void be_copy_opt_init(void) {
238 dbg = firm_dbg_register("ir.be.copyoptmain");
241 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int)) {
242 const char *s1, *s2, *s3;
246 dbg = firm_dbg_register("ir.be.copyopt");
248 co = xcalloc(1, sizeof(*co));
249 co->cenv = chordal_env;
250 co->aenv = chordal_env->birg->main_env->arch_env;
251 co->irg = chordal_env->irg;
252 co->cls = chordal_env->cls;
253 co->get_costs = get_costs;
255 s1 = get_irp_prog_name();
256 s2 = get_entity_name(get_irg_entity(co->irg));
257 s3 = chordal_env->cls->name;
258 len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
259 co->name = xmalloc(len);
260 snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
262 DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
263 INIT_LIST_HEAD(&co->units);
264 irg_walk_graph(co->irg, co_collect_units, NULL, co);
268 void free_copy_opt(copy_opt_t *co) {
271 list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
278 int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
279 const ir_edge_t *edge;
281 if (arch_irn_is_ignore(co->aenv, irn))
284 foreach_out_edge(irn, edge) {
285 ir_node *n = edge->src;
287 if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
288 arch_register_req_t req;
289 arch_get_register_req(co->aenv, &req, n, -1);
292 is_Perm(co->aenv, n) ||
293 (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
302 int co_get_costs_loop_depth(ir_node *root, ir_node* arg, int pos) {
305 ir_node *root_block = get_nodes_block(root);
308 /* for phis the copies are placed in the corresponding pred-block */
309 loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
311 /* a perm places the copy in the same block as it resides */
312 loop = get_irn_loop(root_block);
315 int d = get_loop_depth(loop);
321 int co_get_costs_all_one(ir_node *root, ir_node* arg, int pos) {
325 int co_get_max_copy_costs(const copy_opt_t *co) {
329 list_for_each_entry(unit_t, curr, &co->units, units) {
330 res += curr->inevitable_costs;
331 for (i=1; i<curr->node_count; ++i)
332 res += curr->costs[i];
337 int co_get_inevit_copy_costs(const copy_opt_t *co) {
341 list_for_each_entry(unit_t, curr, &co->units, units)
342 res += curr->inevitable_costs;
346 int co_get_copy_costs(const copy_opt_t *co) {
350 list_for_each_entry(unit_t, curr, &co->units, units) {
351 int root_col = get_irn_col(co, curr->nodes[0]);
352 DBG((dbg, LEVEL_1, " %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
353 res += curr->inevitable_costs;
354 for (i=1; i<curr->node_count; ++i) {
355 int arg_col = get_irn_col(co, curr->nodes[i]);
356 if (root_col != arg_col) {
357 DBG((dbg, LEVEL_1, " %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
358 res += curr->costs[i];
365 int co_get_lower_bound(const copy_opt_t *co) {
368 list_for_each_entry(unit_t, curr, &co->units, units)
369 res += curr->inevitable_costs + curr->min_nodes_costs;
381 * Helpers for saving and restoring colors of nodes.
382 * Used to get dependable and comparable benchmark results.
384 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
386 typedef struct color_saver {
387 arch_env_t *arch_env;
388 be_chordal_env_t *chordal_env;
390 int flag; /* 0 save, 1 load */
393 static void save_load(ir_node *irn, void *env) {
394 color_save_t *saver = env;
395 if (saver->chordal_env->cls == arch_get_irn_reg_class(saver->arch_env, irn, -1)) {
396 if (saver->flag == 0) { /* save */
397 const arch_register_t *reg = arch_get_irn_register(saver->arch_env, irn);
398 pmap_insert(saver->saved_colors, irn, (void *) reg);
400 arch_register_t *reg = pmap_get(saver->saved_colors, irn);
401 arch_set_irn_register(saver->arch_env, irn, reg);
406 static void save_colors(color_save_t *color_saver) {
407 color_saver->flag = 0;
408 irg_walk_graph(color_saver->chordal_env->irg, save_load, NULL, color_saver);
411 static void load_colors(color_save_t *color_saver) {
412 color_saver->flag = 1;
413 irg_walk_graph(color_saver->chordal_env->irg, save_load, NULL, color_saver);
416 #endif /* Need save/load stuff */
420 void co_compare_solvers(be_chordal_env_t *chordal_env) {
426 int costs, costs_inevit, costs_init, costs_heur, costs_classes, costs_ilp, lower_bound;
429 co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
430 DBG((dbg, LEVEL_1, "----> CO: %s\n", co->name));
431 phi_class_compute(chordal_env->irg);
435 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
436 saver.arch_env = chordal_env->main_env->arch_env;
437 saver.chordal_env = chordal_env;
438 saver.saved_colors = pmap_create();
442 costs_inevit = co_get_inevit_copy_costs(co);
443 lower_bound = co_get_lower_bound(co);
444 costs_init = co_get_copy_costs(co);
446 DBG((dbg, LEVEL_1, "Inevit Costs: %3d\n", costs_inevit));
447 DBG((dbg, LEVEL_1, "Lower Bound: %3d\n", lower_bound));
448 DBG((dbg, LEVEL_1, "Init costs: %3d\n", costs_init));
450 copystat_add_inevit_costs(costs_inevit);
451 copystat_add_init_costs(costs_init);
452 copystat_add_max_costs(co_get_max_copy_costs(co));
458 timer = lc_timer_register("heur", NULL);
459 lc_timer_reset_and_start(timer);
462 co_solve_heuristic(co);
465 lc_timer_stop(timer);
466 costs_heur = co_get_copy_costs(co);
467 DBG((dbg, LEVEL_1, "Heur costs: %3d\n", costs_heur));
468 copystat_add_heur_time(lc_timer_elapsed_msec(timer));
469 copystat_add_heur_costs(costs_heur);
470 assert(lower_bound <= costs_heur);
481 timer = lc_timer_register("classes", NULL);
482 lc_timer_reset_and_start(timer);
488 lc_timer_stop(timer);
489 costs_classes = co_get_copy_costs(co);
490 DBG((dbg, LEVEL_1, "Classes costs: %3d\n", costs_classes));
491 copystat_add_classes_time(lc_timer_elapsed_msec(timer));
492 copystat_add_classes_costs(costs_heur);
493 assert(lower_bound <= costs_classes);
495 #endif /* DO_CLASSES */
501 #if defined(DO_HEUR) || defined(DO_CLASSES)
506 co_solve_ilp1(co, 60.0);
509 costs_ilp = co_get_copy_costs(co);
510 DBG((dbg, LEVEL_1, "Opt costs: %3d\n", costs_ilp));
511 copystat_add_opt_costs(costs_ilp);
512 assert(lower_bound <= costs_ilp);
518 #if (defined(DO_HEUR) && defined(DO_BETTER)) || (defined(DO_HEUR) && defined(DO_ILP)) || (defined(DO_BETTER) && defined(DO_ILP))
519 pmap_destroy(saver.saved_colors);