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 0 //SET_LEVEL_1
  10 static firm_dbg_module_t *dbg = NULL;
  11
  12 #define is_curr_reg_class(irn) (co->isa->get_irn_reg_class(irn)==co->cls)
  13 #define is_optimizable(irn) (is_Phi(irn) || is_Copy(irn))
  14
  15 /**
  16  * Builds an optimization unit for a given optimizable irn (root).
  17  * This opt-unit is inserted in the main structure co.
  18  * If an arg of root itself is optimizable process this arg before with a
  19  * recursive call. For handling this situation and loops co->root is used
  20  * to remember all roots.
  21  */
  22 static void co_append_unit(copy_opt_t *co, const ir_node *root) {
  23         int i, arity;
  24         unit_t *unit;
  25         DBG((dbg, LEVEL_1, "\t  Root: %n\n", root));
  26         /* check if we encountered this root earlier */
  27         if (pset_find_ptr(co->roots, root))
  28                 return;
  29         pset_insert_ptr(co->roots, root);
  30
  31         assert(is_curr_reg_class(root) && "node is in wrong register class!");
  32
  33         /* init unit */
  34         arity = get_irn_arity(root);
  35         unit = calloc(1, sizeof(*unit));
  36         unit->co = co;
  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         unit->nodes = realloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
  58         list_add_tail(&unit->units, &co->units);
  59         /* Init mis_size to node_count. So get_lower_bound returns correct results.
  60          * - Now it can be called even before the heuristic has run.
  61          * - And it will return correct results for units with nodecount 1 which are
  62          * not optimized during the heuristic and have therefor delivered wrong results for get_lower_bound
  63          */
  64         unit->mis_size = unit->node_count;
  65
  66 }
  67
  68 static void co_collect_in_block(ir_node *block, void *env) {
  69         copy_opt_t *co = env;
  70         struct list_head *head = &get_ra_block_info(block)->border_head;
  71         border_t *curr;
  72
  73         list_for_each_entry_reverse(border_t, curr, head, list)
  74                 if (curr->is_def && curr->is_real && is_optimizable(curr->irn))
  75                         co_append_unit(co, curr->irn);
  76 }
  77
  78 static void co_collect_units(copy_opt_t *co) {
  79         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
  80         co->roots = pset_new_ptr(64);
  81         dom_tree_walk_irg(co->irg, co_collect_in_block, NULL, co);
  82         del_pset(co->roots);
  83 }
  84
  85 copy_opt_t *new_copy_opt(ir_graph *irg, const arch_isa_if_t *isa, const arch_register_class_t *cls) {
  86         const char *s1, *s2, *s3;
  87         int len;
  88         dbg = firm_dbg_register("ir.be.copyopt");
  89         firm_dbg_set_mask(dbg, DEBUG_LVL);
  90
  91         copy_opt_t *co = calloc(1, sizeof(*co));
  92         co->irg = irg;
  93         co->isa = isa;
  94         co->cls = cls;
  95
  96         s1 = get_irp_prog_name();
  97         s2 = get_entity_name(get_irg_entity(co->irg));
  98         s3 = cls->name;
  99         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
 100         co->name = malloc(len);
 101         if (!strcmp(co->name, DEBUG_IRG))
 102                 firm_dbg_set_mask(dbg, -1);
 103         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
 104
 105         INIT_LIST_HEAD(&co->units);
 106         co_collect_units(co);
 107         return co;
 108 }
 109
 110 void free_copy_opt(copy_opt_t *co) {
 111         unit_t *curr, *tmp;
 112         free(co->name);
 113         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 114                 free(curr->nodes);
 115                 free(curr);
 116         }
 117 }
 118
 119 int co_get_copy_count(copy_opt_t *co) {
 120         int i, res = 0;
 121         unit_t *curr;
 122         list_for_each_entry(unit_t, curr, &co->units, units) {
 123                 int root_col = get_irn_color(curr->nodes[0]);
 124                 res += curr->interf;
 125                 for (i=1; i<curr->node_count; ++i)
 126                         if (root_col != get_irn_color(curr->nodes[i]))
 127                                 res++;
 128         }
 129         return res;
 130 }
 131
 132 int co_get_lower_bound(copy_opt_t *co) {
 133         int res = 0;
 134         unit_t *curr;
 135         list_for_each_entry(unit_t, curr, &co->units, units)
 136                 res += curr->interf + curr->node_count - curr->mis_size;
 137         return res;
 138 }
 139
 140 int co_get_interferer_count(copy_opt_t *co) {
 141         int res = 0;
 142         unit_t *curr;
 143         list_for_each_entry(unit_t, curr, &co->units, units)
 144                 res += curr->interf;
 145         return res;
 146 }
 147
 148 /**
 149  * Needed for result checking
 150  */
 151 static void co_collect_for_checker(ir_node *block, void *env) {
 152         copy_opt_t *co = env;
 153         struct list_head *head = &get_ra_block_info(block)->border_head;
 154         border_t *curr;
 155
 156         list_for_each_entry_reverse(border_t, curr, head, list)
 157                 if (curr->is_def && curr->is_real && is_curr_reg_class(curr->irn))
 158                         obstack_ptr_grow(&co->ob, curr->irn);
 159 }
 160
 161 /**
 162  * This O(n^2) checker checks, if two ifg-connected nodes have the same color.
 163  */
 164 void co_check_allocation(copy_opt_t *co) {
 165         ir_node **nodes, *n1, *n2;
 166         int i, o;
 167
 168         obstack_init(&co->ob);
 169         dom_tree_walk_irg(co->irg, co_collect_for_checker, NULL, co);
 170         obstack_ptr_grow(&co->ob, NULL);
 171
 172         nodes = (ir_node **) obstack_finish(&co->ob);
 173         for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
 174                 assert(! (is_allocatable_irn(n1) && get_irn_color(n1) == NO_COLOR));
 175                 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
 176                         if (phi_ops_interfere(n1, n2) && get_irn_color(n1) == get_irn_color(n2)) {
 177                                 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)));
 178                                 assert(0 && "Interfering values have the same color!");
 179                         }
 180         }
 181         obstack_free(&co->ob, NULL);
 182         DBG((dbg, 2, "The checker seems to be happy!\n"));
 183 }