7 #include "becopystat.h"
9 #define DEBUG_LVL SET_LEVEL_1
10 static firm_dbg_module_t *dbg = NULL;
12 //TODO external things
13 #define is_curr_reg_class(irn) (co->isa->get_irn_reg_class(irn)==co->cls)
14 #define is_optimizable(irn) (is_Phi(irn) || is_Copy(irn))
17 * Builds an optimization unit for a given optimizable irn (root).
18 * This opt-unit is inserted in the main structure co.
19 * If an arg of root itself is optimizable process this arg before with a
20 * recursive call. For handling this situation and loops co->root is used
21 * to remember all roots.
23 static void co_append_unit(copy_opt_t *co, const ir_node *root) {
26 DBG((dbg, LEVEL_1, "\t Root: %n\n", root));
27 /* check if we encountered this root earlier */
28 if (pset_find_ptr(co->roots, root))
30 pset_insert_ptr(co->roots, root);
32 assert(is_curr_reg_class(root) && "node is in wrong register class!");
35 arity = get_irn_arity(root);
36 unit = calloc(1, sizeof(*unit));
39 unit->nodes = malloc((arity+1) * sizeof(*unit->nodes));
40 unit->nodes[0] = root;
41 INIT_LIST_HEAD(&unit->queue);
44 for (i=0; i<arity; ++i) {
45 ir_node *arg = get_irn_n(root, i);
46 assert(is_curr_reg_class(arg) && "Argument not in same register class.");
48 if (!values_interfere(root, arg)) {
49 DBG((dbg, LEVEL_1, "\t Member: %n\n", arg));
50 if (is_optimizable(arg))
51 co_append_unit(co, arg);
52 unit->nodes[unit->node_count++] = arg;
58 unit->nodes = realloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
59 list_add_tail(&unit->units, &co->units);
62 static void co_collect_in_block(ir_node *block, void *env) {
64 struct list_head *head = &get_ra_block_info(block)->border_head;
67 list_for_each_entry_reverse(border_t, curr, head, list)
68 if (curr->is_def && curr->is_real && is_optimizable(curr->irn))
69 co_append_unit(co, curr->irn);
72 static void co_collect_units(copy_opt_t *co) {
73 DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
74 co->roots = pset_new_ptr(64);
75 dom_tree_walk_irg(co->irg, co_collect_in_block, NULL, co);
79 copy_opt_t *new_copy_opt(ir_graph *irg, const arch_isa_if_t *isa, const arch_register_class_t *cls) {
80 dbg = firm_dbg_register("ir.be.copyopt");
81 firm_dbg_set_mask(dbg, DEBUG_LVL);
83 copy_opt_t *co = calloc(1, sizeof(*co));
87 INIT_LIST_HEAD(&co->units);
92 void free_copy_opt(copy_opt_t *co) {
94 list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
100 int co_get_copy_count(copy_opt_t *co) {
103 list_for_each_entry(unit_t, curr, &co->units, units) {
104 int root_col = get_irn_color(curr->nodes[0]);
106 for (i=1; i<curr->node_count; ++i)
107 if (root_col != get_irn_color(curr->nodes[i]))
113 int co_get_lower_bound(copy_opt_t *co) {
116 list_for_each_entry(unit_t, curr, &co->units, units)
117 res += curr->interf + curr->node_count - curr->mis_size;
121 int co_get_interferer_count(copy_opt_t *co) {
124 list_for_each_entry(unit_t, curr, &co->units, units)
130 * Needed for result checking
132 static void co_collect_for_checker(ir_node *block, void *env) {
133 copy_opt_t *co = env;
134 struct list_head *head = &get_ra_block_info(block)->border_head;
137 list_for_each_entry_reverse(border_t, curr, head, list)
138 if (curr->is_def && curr->is_real && is_curr_reg_class(curr->irn))
139 obstack_ptr_grow(&co->ob, curr->irn);
143 * This O(n^2) checker checks, if two ifg-connected nodes have the same color.
145 void co_check_allocation(copy_opt_t *co) {
146 ir_node **nodes, *n1, *n2;
149 obstack_init(&co->ob);
150 dom_tree_walk_irg(co->irg, co_collect_for_checker, NULL, co);
151 obstack_ptr_grow(&co->ob, NULL);
153 nodes = (ir_node **) obstack_finish(&co->ob);
154 for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
155 assert(! (is_allocatable_irn(n1) && get_irn_color(n1) == NO_COLOR));
156 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
157 if (phi_ops_interfere(n1, n2) && get_irn_color(n1) == get_irn_color(n2)) {
158 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)));
159 assert(0 && "Interfering values have the same color!");
162 obstack_free(&co->ob, NULL);
163 DBG((dbg, 2, "The checker seems to be happy!\n"));