4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
12 #include "bechordal_t.h"
13 #include "becopyopt.h"
14 #include "becopystat.h"
16 #define DEBUG_LVL 0 //SET_LEVEL_1
17 static firm_dbg_module_t *dbg = NULL;
19 #define is_curr_reg_class(irn) (arch_get_irn_reg_class(co->env, irn, arch_pos_make_out(0)) == co->cls)
22 * Builds an optimization unit for a given optimizable irn (root).
23 * This opt-unit is inserted in the main structure co.
24 * If an arg of root itself is optimizable process this arg before with a
25 * recursive call. For handling this situation and loops co->root is used
26 * to remember all roots.
28 static void co_append_unit(copy_opt_t *co, ir_node *root) {
31 DBG((dbg, LEVEL_1, "\t Root: %n\n", root));
32 /* check if we encountered this root earlier */
33 if (pset_find_ptr(co->roots, root))
35 pset_insert_ptr(co->roots, root);
37 assert(is_curr_reg_class(root) && "node is in wrong register class!");
40 arity = get_irn_arity(root);
41 unit = xcalloc(1, sizeof(*unit));
45 unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
46 unit->nodes[0] = root;
47 INIT_LIST_HEAD(&unit->queue);
50 for (i=0; i<arity; ++i) {
51 ir_node *arg = get_irn_n(root, i);
52 assert(is_curr_reg_class(arg) && "Argument not in same register class.");
54 if (!nodes_interfere(co->chordal_env, root, arg)) {
55 DBG((dbg, LEVEL_1, "\t Member: %n\n", arg));
56 if (is_optimizable(arg))
57 co_append_unit(co, arg);
58 unit->nodes[unit->node_count++] = arg;
63 unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
64 list_add_tail(&unit->units, &co->units);
65 /* Init mis_size to node_count. So get_lower_bound returns correct results.
66 * - Now it can be called even before the heuristic has run.
67 * - And it will return correct results for units with nodecount 1 which are
68 * not optimized during the heuristic and have therefor delivered wrong results for get_lower_bound
70 unit->mis_size = unit->node_count;
74 static void co_collect_in_block(ir_node *block, void *env) {
76 struct list_head *head = get_block_border_head(co->chordal_env, block);
79 list_for_each_entry_reverse(border_t, curr, head, list)
80 if (curr->is_def && curr->is_real && is_optimizable(curr->irn))
81 co_append_unit(co, curr->irn);
84 static void co_collect_units(copy_opt_t *co) {
85 DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
86 co->roots = pset_new_ptr(64);
87 dom_tree_walk_irg(co->irg, co_collect_in_block, NULL, co);
91 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env,
92 const arch_env_t *env, const arch_register_class_t *cls) {
93 const char *s1, *s2, *s3;
97 dbg = firm_dbg_register("ir.be.copyopt");
98 firm_dbg_set_mask(dbg, DEBUG_LVL);
100 co = xcalloc(1, sizeof(*co));
101 co->chordal_env = chordal_env;
102 co->irg = chordal_env->irg;
104 // co->isa = env->isa;
107 s1 = get_irp_prog_name();
108 s2 = get_entity_name(get_irg_entity(co->irg));
110 len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
111 co->name = xmalloc(len);
112 if (!strcmp(co->name, DEBUG_IRG))
113 firm_dbg_set_mask(dbg, -1);
114 snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
116 INIT_LIST_HEAD(&co->units);
117 co_collect_units(co);
121 void free_copy_opt(copy_opt_t *co) {
124 list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
130 int is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
132 for(i=0, max=get_irn_n_outs(irn); i<max; ++i) {
133 ir_node *n = get_irn_out(irn, i);
134 if (is_optimizable(n) && (irn == n || !nodes_interfere(co->chordal_env, irn, n)))
141 int co_get_copy_count(const copy_opt_t *co) {
144 list_for_each_entry(unit_t, curr, &co->units, units) {
145 int root_col = get_irn_col(co, curr->nodes[0]);
147 for (i=1; i<curr->node_count; ++i)
148 if (root_col != get_irn_col(co, curr->nodes[i]))
154 int co_get_lower_bound(const copy_opt_t *co) {
157 list_for_each_entry(unit_t, curr, &co->units, units)
158 res += curr->interf + curr->node_count - curr->mis_size;
162 int co_get_interferer_count(const copy_opt_t *co) {
165 list_for_each_entry(unit_t, curr, &co->units, units)
171 * Needed for result checking
173 static void co_collect_for_checker(ir_node *block, void *env) {
174 copy_opt_t *co = env;
175 struct list_head *head = get_block_border_head(co->chordal_env, block);
178 list_for_each_entry_reverse(border_t, curr, head, list)
179 if (curr->is_def && curr->is_real && is_curr_reg_class(curr->irn))
180 obstack_ptr_grow(&co->ob, curr->irn);
184 * This O(n^2) checker checks, if two ifg-connected nodes have the same color.
186 void co_check_allocation(copy_opt_t *co) {
187 ir_node **nodes, *n1, *n2;
190 obstack_init(&co->ob);
191 dom_tree_walk_irg(co->irg, co_collect_for_checker, NULL, co);
192 obstack_ptr_grow(&co->ob, NULL);
194 nodes = (ir_node **) obstack_finish(&co->ob);
195 for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
196 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
197 if (nodes_interfere(co->chordal_env, n1, n2)
198 && get_irn_col(co, n1) == get_irn_col(co, n2)) {
200 DBG((dbg, 0, "Error: %n in %n and %n in %n have the same color.\n", n1, get_nodes_block(n1), n2, get_nodes_block(n2)));
201 assert(0 && "Interfering values have the same color!");
204 obstack_free(&co->ob, NULL);
205 DBG((dbg, 2, "The checker seems to be happy!\n"));