nsz Git - libfirm/blob - ir/be/becopyopt.c

   1 /**
   2  * @author Daniel Grund
   3  * @date 12.04.2005
   4  */
   5
   6 #include "becopyopt.h"
   7 #include "becopystat.h"
   8
   9 #define DEBUG_LVL SET_LEVEL_1
  10 static firm_dbg_module_t *dbg = NULL;
  11
  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))
  15
  16 /**
  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.
  22  */
  23 static void co_append_unit(copy_opt_t *co, const ir_node *root) {
  24         int i, arity;
  25         unit_t *unit;
  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))
  29                 return;
  30         pset_insert_ptr(co->roots, root);
  31
  32         assert(is_curr_reg_class(root) && "node is in wrong register class!");
  33
  34         /* init unit */
  35         arity = get_irn_arity(root);
  36         unit = calloc(1, sizeof(*unit));
  37         unit->interf = 0;
  38         unit->node_count = 1;
  39         unit->nodes = malloc((arity+1) * sizeof(*unit->nodes));
  40         unit->nodes[0] = root;
  41         INIT_LIST_HEAD(&unit->queue);
  42
  43         /* check all args */
  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.");
  47                 if (arg != root) {
  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;
  53                         } else
  54                                 unit->interf++;
  55                 }
  56         }
  57
  58         unit->nodes = realloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
  59         list_add_tail(&unit->units, &co->units);
  60 }
  61
  62 static void co_collect_in_block(ir_node *block, void *env) {
  63         copy_opt_t *co = env;
  64         struct list_head *head = &get_ra_block_info(block)->border_head;
  65         border_t *curr;
  66
  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);
  70 }
  71
  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);
  76         del_pset(co->roots);
  77 }
  78
  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);
  82
  83         copy_opt_t *co = calloc(1, sizeof(*co));
  84         co->irg = irg;
  85         co->isa = isa;
  86         co->cls = cls;
  87         INIT_LIST_HEAD(&co->units);
  88         co_collect_units(co);
  89         return co;
  90 }
  91
  92 void free_copy_opt(copy_opt_t *co) {
  93         unit_t *curr, *tmp;
  94         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
  95                 free(curr->nodes);
  96                 free(curr);
  97         }
  98 }
  99
 100 int co_get_copy_count(copy_opt_t *co) {
 101         int i, res = 0;
 102         unit_t *curr;
 103         list_for_each_entry(unit_t, curr, &co->units, units) {
 104                 int root_col = get_irn_color(curr->nodes[0]);
 105                 res += curr->interf;
 106                 for (i=1; i<curr->node_count; ++i)
 107                         if (root_col != get_irn_color(curr->nodes[i]))
 108                                 res++;
 109         }
 110         return res;
 111 }
 112
 113 int co_get_lower_bound(copy_opt_t *co) {
 114         int res = 0;
 115         unit_t *curr;
 116         list_for_each_entry(unit_t, curr, &co->units, units)
 117                 res += curr->interf + curr->node_count - curr->mis_size;
 118         return res;
 119 }
 120
 121 int co_get_interferer_count(copy_opt_t *co) {
 122         int res = 0;
 123         unit_t *curr;
 124         list_for_each_entry(unit_t, curr, &co->units, units)
 125                 res += curr->interf;
 126         return res;
 127 }
 128
 129 /**
 130  * Needed for result checking
 131  */
 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;
 135         border_t *curr;
 136
 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);
 140 }
 141
 142 /**
 143  * This O(n^2) checker checks, if two ifg-connected nodes have the same color.
 144  */
 145 void co_check_allocation(copy_opt_t *co) {
 146         ir_node **nodes, *n1, *n2;
 147         int i, o;
 148
 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);
 152
 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!");
 160                         }
 161         }
 162         obstack_free(&co->ob, NULL);
 163         DBG((dbg, 2, "The checker seems to be happy!\n"));
 164 }