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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                12.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #include "xmalloc.h"
  12 #include "becopyopt.h"
  13 #include "becopystat.h"
  14
  15 #define DEBUG_LVL 0 //SET_LEVEL_1
  16 static firm_dbg_module_t *dbg = NULL;
  17
  18 #define is_curr_reg_class(irn) (arch_get_irn_reg_class(co->env, irn, arch_pos_make_out(0)) == co->cls)
  19
  20 /**
  21  * Builds an optimization unit for a given optimizable irn (root).
  22  * This opt-unit is inserted in the main structure co.
  23  * If an arg of root itself is optimizable process this arg before with a
  24  * recursive call. For handling this situation and loops co->root is used
  25  * to remember all roots.
  26  */
  27 static void co_append_unit(copy_opt_t *co, ir_node *root) {
  28         int i, arity;
  29         unit_t *unit;
  30         DBG((dbg, LEVEL_1, "\t  Root: %n\n", root));
  31         /* check if we encountered this root earlier */
  32         if (pset_find_ptr(co->roots, root))
  33                 return;
  34         pset_insert_ptr(co->roots, root);
  35
  36         assert(is_curr_reg_class(root) && "node is in wrong register class!");
  37
  38         /* init unit */
  39         arity = get_irn_arity(root);
  40         unit = xcalloc(1, sizeof(*unit));
  41         unit->co = co;
  42         unit->interf = 0;
  43         unit->node_count = 1;
  44         unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
  45         unit->nodes[0] = root;
  46         INIT_LIST_HEAD(&unit->queue);
  47
  48         /* check all args */
  49         for (i=0; i<arity; ++i) {
  50                 ir_node *arg = get_irn_n(root, i);
  51                 assert(is_curr_reg_class(arg) && "Argument not in same register class.");
  52                 if (arg != root) {
  53                         if (!values_interfere(root, arg)) {
  54                                 DBG((dbg, LEVEL_1, "\t  Member: %n\n", arg));
  55                                 if (is_optimizable(arg))
  56                                         co_append_unit(co, arg);
  57                                 unit->nodes[unit->node_count++] = arg;
  58                         } else
  59                                 unit->interf++;
  60                 }
  61         }
  62         unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
  63         list_add_tail(&unit->units, &co->units);
  64         /* Init mis_size to node_count. So get_lower_bound returns correct results.
  65          * - Now it can be called even before the heuristic has run.
  66          * - And it will return correct results for units with nodecount 1 which are
  67          * not optimized during the heuristic and have therefor delivered wrong results for get_lower_bound
  68          */
  69         unit->mis_size = unit->node_count;
  70
  71 }
  72
  73 static void co_collect_in_block(ir_node *block, void *env) {
  74         copy_opt_t *co = env;
  75         struct list_head *head = &get_ra_block_info(block)->border_head;
  76         border_t *curr;
  77
  78         list_for_each_entry_reverse(border_t, curr, head, list)
  79                 if (curr->is_def && curr->is_real && is_optimizable(curr->irn))
  80                         co_append_unit(co, curr->irn);
  81 }
  82
  83 static void co_collect_units(copy_opt_t *co) {
  84         DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
  85         co->roots = pset_new_ptr(64);
  86         dom_tree_walk_irg(co->irg, co_collect_in_block, NULL, co);
  87         del_pset(co->roots);
  88 }
  89
  90 copy_opt_t *new_copy_opt(ir_graph *irg, const arch_env_t *env, const arch_register_class_t *cls) {
  91         const char *s1, *s2, *s3;
  92         int len;
  93         copy_opt_t *co;
  94
  95         dbg = firm_dbg_register("ir.be.copyopt");
  96         firm_dbg_set_mask(dbg, DEBUG_LVL);
  97
  98         co = xcalloc(1, sizeof(*co));
  99         co->irg = irg;
 100         co->env = env;
 101 //      co->isa = env->isa;
 102         co->cls = cls;
 103
 104         s1 = get_irp_prog_name();
 105         s2 = get_entity_name(get_irg_entity(co->irg));
 106         s3 = cls->name;
 107         len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
 108         co->name = xmalloc(len);
 109         if (!strcmp(co->name, DEBUG_IRG))
 110                 firm_dbg_set_mask(dbg, -1);
 111         snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);
 112
 113         INIT_LIST_HEAD(&co->units);
 114         co_collect_units(co);
 115         return co;
 116 }
 117
 118 void free_copy_opt(copy_opt_t *co) {
 119         unit_t *curr, *tmp;
 120         xfree(co->name);
 121         list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
 122                 xfree(curr->nodes);
 123                 xfree(curr);
 124         }
 125 }
 126
 127 int is_optimizable_arg(ir_node *irn) {
 128         int i, max;
 129         for(i=0, max=get_irn_n_outs(irn); i<max; ++i) {
 130                 ir_node *n = get_irn_out(irn, i);
 131                 if (is_optimizable(n) && (irn == n || !values_interfere(irn, n)))
 132                         return 1;
 133         }
 134         return 0;
 135 }
 136
 137
 138 int co_get_copy_count(copy_opt_t *co) {
 139         int i, res = 0;
 140         unit_t *curr;
 141         list_for_each_entry(unit_t, curr, &co->units, units) {
 142                 int root_col = get_irn_col(co, curr->nodes[0]);
 143                 res += curr->interf;
 144                 for (i=1; i<curr->node_count; ++i)
 145                         if (root_col != get_irn_col(co, curr->nodes[i]))
 146                                 res++;
 147         }
 148         return res;
 149 }
 150
 151 int co_get_lower_bound(copy_opt_t *co) {
 152         int res = 0;
 153         unit_t *curr;
 154         list_for_each_entry(unit_t, curr, &co->units, units)
 155                 res += curr->interf + curr->node_count - curr->mis_size;
 156         return res;
 157 }
 158
 159 int co_get_interferer_count(copy_opt_t *co) {
 160         int res = 0;
 161         unit_t *curr;
 162         list_for_each_entry(unit_t, curr, &co->units, units)
 163                 res += curr->interf;
 164         return res;
 165 }
 166
 167 /**
 168  * Needed for result checking
 169  */
 170 static void co_collect_for_checker(ir_node *block, void *env) {
 171         copy_opt_t *co = env;
 172         struct list_head *head = &get_ra_block_info(block)->border_head;
 173         border_t *curr;
 174
 175         list_for_each_entry_reverse(border_t, curr, head, list)
 176                 if (curr->is_def && curr->is_real && is_curr_reg_class(curr->irn))
 177                         obstack_ptr_grow(&co->ob, curr->irn);
 178 }
 179
 180 /**
 181  * This O(n^2) checker checks, if two ifg-connected nodes have the same color.
 182  */
 183 void co_check_allocation(copy_opt_t *co) {
 184         ir_node **nodes, *n1, *n2;
 185         int i, o;
 186
 187         obstack_init(&co->ob);
 188         dom_tree_walk_irg(co->irg, co_collect_for_checker, NULL, co);
 189         obstack_ptr_grow(&co->ob, NULL);
 190
 191         nodes = (ir_node **) obstack_finish(&co->ob);
 192         for (i = 0, n1 = nodes[i]; n1; n1 = nodes[++i]) {
 193                 assert(! (is_allocatable_irn(n1) && get_irn_col(co, n1) == NO_COLOR));
 194                 for (o = i+1, n2 = nodes[o]; n2; n2 = nodes[++o])
 195                         if (phi_ops_interfere(n1, n2) && get_irn_col(co, n1) == get_irn_col(co, n2)) {
 196                                 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)));
 197                                 assert(0 && "Interfering values have the same color!");
 198                         }
 199         }
 200         obstack_free(&co->ob, NULL);
 201         DBG((dbg, 2, "The checker seems to be happy!\n"));
 202 }