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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Register pressure node selector.
  23  * @author      Sebastian Hack
  24  * @date        29.08.2006
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <stdlib.h>
  32
  33 #include "iredges_t.h"
  34 #include "irgwalk.h"
  35
  36 #include "besched_t.h"
  37 #include "belistsched.h"
  38 #include "benode_t.h"
  39
  40
  41 typedef struct _usage_stats_t {
  42         ir_node *irn;
  43         struct _usage_stats_t *next;
  44         int max_hops;
  45         int uses_in_block;      /**< Number of uses inside the current block. */
  46         int already_consumed;   /**< Number of insns using this value already
  47                                                         scheduled. */
  48 } usage_stats_t;
  49
  50 typedef struct {
  51         const list_sched_selector_t *vtab;
  52         const arch_env_t *arch_env;
  53 } reg_pressure_main_env_t;
  54
  55 typedef struct {
  56         struct obstack obst;
  57         const reg_pressure_main_env_t *main_env;
  58         usage_stats_t *root;
  59         ir_nodeset_t already_scheduled;
  60 } reg_pressure_selector_env_t;
  61
  62
  63 #if 0
  64 /*
  65 * Ugly global variable for the compare function
  66 * since qsort(3) does not pass an extra pointer.
  67 */
  68 static ir_node *curr_bl = NULL;
  69
  70 static int cmp_usage(const void *a, const void *b)
  71 {
  72         struct trivial_sched_env *env;
  73         const ir_node *p = a;
  74         const ir_node *q = b;
  75         int res = 0;
  76
  77         res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
  78
  79         /*
  80         * One of them is live at the end of the block.
  81         * Then, that one shall be scheduled at after the other
  82         */
  83         if(res != 0)
  84                 return res;
  85
  86
  87         return res;
  88 }
  89 #endif
  90
  91 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
  92 {
  93         usage_stats_t *us = get_irn_link(irn);
  94
  95         if(!us) {
  96                 us                   = obstack_alloc(&env->obst, sizeof(us[0]));
  97                 us->irn              = irn;
  98                 us->already_consumed = 0;
  99                 us->max_hops         = INT_MAX;
 100                 us->next             = env->root;
 101                 env->root            = us;
 102                 set_irn_link(irn, us);
 103         }
 104
 105         return us;
 106 }
 107
 108 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
 109 {
 110         usage_stats_t *us = get_irn_link(irn);
 111         assert(us && "This node must have usage stats");
 112         return us;
 113 }
 114
 115 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
 116 {
 117         ir_node *bl = get_nodes_block(irn);
 118         /*
 119         * If the reached node is not in the block desired,
 120         * return the value passed for this situation.
 121         */
 122         if(get_nodes_block(irn) != bl)
 123                 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
 124
 125         /*
 126         * If the node is in the current block but not
 127         * yet scheduled, we keep on searching from that node.
 128         */
 129         if(!ir_nodeset_contains(&env->already_scheduled, irn)) {
 130                 int i, n;
 131                 int res = 0;
 132                 for(i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 133                         ir_node *operand = get_irn_in_or_dep(irn, i);
 134
 135                         if(get_irn_visited(operand) < visited_nr) {
 136                                 int tmp;
 137
 138                                 set_irn_visited(operand, visited_nr);
 139                                 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
 140                                 res = MAX(tmp, res);
 141                         }
 142                 }
 143
 144                 return res;
 145         }
 146
 147         /*
 148         * If the node is in the current block and scheduled, return
 149         * the depth which indicates the number of steps to the
 150         * region of scheduled nodes.
 151         */
 152         return depth;
 153 }
 154
 155 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
 156 {
 157         ir_node *bl   = get_nodes_block(irn);
 158         ir_graph *irg = get_irn_irg(bl);
 159         int res       = 0;
 160
 161         const ir_edge_t *edge;
 162
 163         foreach_out_edge(irn, edge) {
 164                 ir_node *user       = get_edge_src_irn(edge);
 165                 unsigned visited_nr = get_irg_visited(irg) + 1;
 166                 int max_hops;
 167
 168                 set_irg_visited(irg, visited_nr);
 169                 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
 170                 res      = MAX(res, max_hops);
 171         }
 172
 173         return res;
 174 }
 175
 176 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 177 {
 178         reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
 179
 180         main_env->arch_env = arch_env;
 181         main_env->vtab     = vtab;
 182         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 183
 184         return main_env;
 185 }
 186
 187 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
 188 {
 189         int res = -1;
 190
 191         if(sel->to_appear_in_schedule)
 192                 res = sel->to_appear_in_schedule(block_env, irn);
 193
 194         return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn));
 195 }
 196
 197 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
 198 {
 199         ir_node *irn;
 200         reg_pressure_selector_env_t *env  = xmalloc(sizeof(env[0]));
 201
 202         obstack_init(&env->obst);
 203         ir_nodeset_init(&env->already_scheduled);
 204         env->root              = NULL;
 205         env->main_env          = graph_env;
 206
 207         /*
 208         * Collect usage statistics.
 209         */
 210         sched_foreach(bl, irn) {
 211                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 212                         int i, n;
 213
 214                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 215                                 //ir_node *op = get_irn_n(irn, i);
 216                                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 217                                         usage_stats_t *us = get_or_set_usage_stats(env, irn);
 218 #if 0 /* Liveness is not computed here! */
 219                                         if(is_live_end(bl, op))
 220                                                 us->uses_in_block = 99999;
 221                                         else
 222 #endif
 223                                                 us->uses_in_block++;
 224                                 }
 225                         }
 226                 }
 227         }
 228
 229         return env;
 230 }
 231
 232 static void reg_pressure_block_free(void *block_env)
 233 {
 234         reg_pressure_selector_env_t *env = block_env;
 235         usage_stats_t *us;
 236
 237         for(us = env->root; us; us = us->next)
 238                 set_irn_link(us->irn, NULL);
 239
 240         obstack_free(&env->obst, NULL);
 241         ir_nodeset_destroy(&env->already_scheduled);
 242         free(env);
 243 }
 244
 245 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
 246 {
 247         int res = 0;
 248         if(get_irn_mode(irn) == mode_T) {
 249                 const ir_edge_t *edge;
 250
 251                 foreach_out_edge(irn, edge)
 252                         res += get_result_hops_sum(env, get_edge_src_irn(edge));
 253         }
 254
 255         else if(mode_is_data(get_irn_mode(irn)))
 256                 res = compute_max_hops(env, irn);
 257
 258
 259         return res;
 260 }
 261
 262 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
 263 {
 264         int i, n;
 265         int sum = 0;
 266
 267         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 268                 ir_node *op = get_irn_n(irn, i);
 269
 270                 if(must_appear_in_schedule(env->main_env->vtab, env, op))
 271                         sum += compute_max_hops(env, op);
 272         }
 273
 274         sum += get_result_hops_sum(env, irn);
 275
 276         return sum;
 277 }
 278
 279 static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set,
 280                                     ir_nodeset_t *live_set)
 281 {
 282         ir_nodeset_iterator_t iter;
 283         reg_pressure_selector_env_t *env = block_env;
 284         ir_node *irn, *res     = NULL;
 285         int curr_cost          = INT_MAX;
 286         (void) live_set;
 287
 288         assert(ir_nodeset_size(ready_set) > 0);
 289
 290         ir_nodeset_iterator_init(&iter, ready_set);
 291         while( (irn = ir_nodeset_iterator_next(&iter)) != NULL) {
 292                 /*
 293                 Ignore branch instructions for the time being.
 294                 They should only be scheduled if there is nothing else.
 295                 */
 296                 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
 297                         int costs = reg_pr_costs(env, irn);
 298                         if (costs <= curr_cost) {
 299                                 res       = irn;
 300                                 curr_cost = costs;
 301                         }
 302                 }
 303         }
 304
 305         /*
 306         There was no result so we only saw a branch.
 307         Take it and finish.
 308         */
 309
 310         if(!res) {
 311                 ir_nodeset_iterator_init(&iter, ready_set);
 312                 res = ir_nodeset_iterator_next(&iter);
 313
 314                 assert(res && "There must be a node scheduled.");
 315         }
 316
 317         ir_nodeset_insert(&env->already_scheduled, res);
 318         return res;
 319 }
 320
 321 static const list_sched_selector_t reg_pressure_selector_struct = {
 322         reg_pressure_graph_init,
 323         reg_pressure_block_init,
 324         reg_pressure_select,
 325         NULL,                    /* to_appear_in_schedule */
 326         NULL,                    /* node_ready */
 327         NULL,                    /* node_selected */
 328         NULL,                    /* exectime */
 329         NULL,                    /* latency */
 330         reg_pressure_block_free,
 331         free
 332 };
 333
 334 const list_sched_selector_t *reg_pressure_selector = &reg_pressure_selector_struct;