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

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "config.h"
  28
  29 #include <stdlib.h>
  30
  31 #include "iredges_t.h"
  32 #include "irgwalk.h"
  33 #include "irtools.h"
  34 #include "util.h"
  35
  36 #include "besched.h"
  37 #include "belistsched.h"
  38 #include "benode.h"
  39 #include "bemodule.h"
  40
  41
  42 typedef struct usage_stats_t {
  43         ir_node *irn;
  44         struct usage_stats_t *next;
  45         int max_hops;
  46         int uses_in_block;      /**< Number of uses inside the current block. */
  47         int already_consumed;   /**< Number of insns using this value already
  48                                                         scheduled. */
  49 } usage_stats_t;
  50
  51 typedef struct {
  52         struct obstack obst;
  53         usage_stats_t *root;
  54         ir_nodeset_t already_scheduled;
  55 } reg_pressure_selector_env_t;
  56
  57
  58 #if 0
  59 /*
  60 * Ugly global variable for the compare function
  61 * since qsort(3) does not pass an extra pointer.
  62 */
  63 static ir_node *curr_bl = NULL;
  64
  65 static int cmp_usage(const void *a, const void *b)
  66 {
  67         struct trivial_sched_env *env;
  68         const ir_node *p = a;
  69         const ir_node *q = b;
  70         int res = 0;
  71
  72         res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
  73
  74         /*
  75         * One of them is live at the end of the block.
  76         * Then, that one shall be scheduled at after the other
  77         */
  78         if (res != 0)
  79                 return res;
  80
  81
  82         return res;
  83 }
  84 #endif
  85
  86 static inline usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
  87 {
  88         usage_stats_t *us = (usage_stats_t*)get_irn_link(irn);
  89
  90         if (!us) {
  91                 us                   = OALLOC(&env->obst, usage_stats_t);
  92                 us->irn              = irn;
  93                 us->already_consumed = 0;
  94                 us->max_hops         = INT_MAX;
  95                 us->next             = env->root;
  96                 env->root            = us;
  97                 set_irn_link(irn, us);
  98         }
  99
 100         return us;
 101 }
 102
 103 static inline usage_stats_t *get_usage_stats(ir_node *irn)
 104 {
 105         usage_stats_t *us = (usage_stats_t*)get_irn_link(irn);
 106         assert(us && "This node must have usage stats");
 107         return us;
 108 }
 109
 110 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
 111 {
 112         ir_node *bl = get_nodes_block(irn);
 113         /*
 114         * If the reached node is not in the block desired,
 115         * return the value passed for this situation.
 116         */
 117         if (get_nodes_block(irn) != bl)
 118                 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
 119
 120         /*
 121         * If the node is in the current block but not
 122         * yet scheduled, we keep on searching from that node.
 123         */
 124         if (!ir_nodeset_contains(&env->already_scheduled, irn)) {
 125                 int i, n;
 126                 int res = 0;
 127                 for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 128                         ir_node *operand = get_irn_in_or_dep(irn, i);
 129
 130                         if (get_irn_visited(operand) < visited_nr) {
 131                                 int tmp;
 132
 133                                 set_irn_visited(operand, visited_nr);
 134                                 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
 135                                 res = MAX(tmp, res);
 136                         }
 137                 }
 138
 139                 return res;
 140         }
 141
 142         /*
 143         * If the node is in the current block and scheduled, return
 144         * the depth which indicates the number of steps to the
 145         * region of scheduled nodes.
 146         */
 147         return depth;
 148 }
 149
 150 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
 151 {
 152         ir_node *bl   = get_nodes_block(irn);
 153         ir_graph *irg = get_irn_irg(bl);
 154         int res       = 0;
 155
 156         const ir_edge_t *edge;
 157
 158         foreach_out_edge(irn, edge) {
 159                 ir_node *user       = get_edge_src_irn(edge);
 160                 unsigned visited_nr = get_irg_visited(irg) + 1;
 161                 int max_hops;
 162
 163                 set_irg_visited(irg, visited_nr);
 164                 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
 165                 res      = MAX(res, max_hops);
 166         }
 167
 168         return res;
 169 }
 170
 171 static void *reg_pressure_graph_init(ir_graph *irg)
 172 {
 173         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 174
 175         return NULL;
 176 }
 177
 178 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
 179 {
 180         ir_node *irn;
 181         reg_pressure_selector_env_t *env = XMALLOC(reg_pressure_selector_env_t);
 182         (void) graph_env;
 183
 184         obstack_init(&env->obst);
 185         ir_nodeset_init(&env->already_scheduled);
 186         env->root              = NULL;
 187
 188         /*
 189         * Collect usage statistics.
 190         */
 191         sched_foreach(bl, irn) {
 192                 int i, n;
 193                 if (is_Proj(irn)
 194                                 || (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled))
 195                         continue;
 196
 197                 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 198                         usage_stats_t *us = get_or_set_usage_stats(env, irn);
 199 #if 0 /* Liveness is not computed here! */
 200                         if (is_live_end(bl, op))
 201                                 us->uses_in_block = 99999;
 202                         else
 203 #endif
 204                                 us->uses_in_block++;
 205                 }
 206         }
 207
 208         return env;
 209 }
 210
 211 static void reg_pressure_block_free(void *block_env)
 212 {
 213         reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env;
 214         usage_stats_t *us;
 215
 216         for (us = env->root; us; us = us->next)
 217                 set_irn_link(us->irn, NULL);
 218
 219         obstack_free(&env->obst, NULL);
 220         ir_nodeset_destroy(&env->already_scheduled);
 221         free(env);
 222 }
 223
 224 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
 225 {
 226         int res = 0;
 227         if (get_irn_mode(irn) == mode_T) {
 228                 const ir_edge_t *edge;
 229
 230                 foreach_out_edge(irn, edge)
 231                         res += get_result_hops_sum(env, get_edge_src_irn(edge));
 232         }
 233
 234         else if (mode_is_data(get_irn_mode(irn)))
 235                 res = compute_max_hops(env, irn);
 236
 237
 238         return res;
 239 }
 240
 241 static inline int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
 242 {
 243         int i, n;
 244         int sum = 0;
 245
 246         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 247                 ir_node *op = get_irn_n(irn, i);
 248
 249                 if (is_Proj(op)
 250                     || (arch_get_irn_flags(op) & arch_irn_flags_not_scheduled))
 251                         continue;
 252
 253                 sum += compute_max_hops(env, op);
 254         }
 255
 256         sum += get_result_hops_sum(env, irn);
 257
 258         return sum;
 259 }
 260
 261 static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set)
 262 {
 263         ir_nodeset_iterator_t iter;
 264         reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env;
 265         ir_node *irn, *res     = NULL;
 266         int curr_cost          = INT_MAX;
 267
 268         assert(ir_nodeset_size(ready_set) > 0);
 269
 270         ir_nodeset_iterator_init(&iter, ready_set);
 271         while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL) {
 272                 /*
 273                 Ignore branch instructions for the time being.
 274                 They should only be scheduled if there is nothing else.
 275                 */
 276                 if (!is_cfop(irn)) {
 277                         int costs = reg_pr_costs(env, irn);
 278                         if (costs <= curr_cost) {
 279                                 res       = irn;
 280                                 curr_cost = costs;
 281                         }
 282                 }
 283         }
 284
 285         /*
 286         There was no result so we only saw a branch.
 287         Take it and finish.
 288         */
 289
 290         if (!res) {
 291                 ir_nodeset_iterator_init(&iter, ready_set);
 292                 res = ir_nodeset_iterator_next(&iter);
 293
 294                 assert(res && "There must be a node scheduled.");
 295         }
 296
 297         ir_nodeset_insert(&env->already_scheduled, res);
 298         return res;
 299 }
 300
 301 static void sched_reg_pressure(ir_graph *irg)
 302 {
 303         static const list_sched_selector_t reg_pressure_selector = {
 304                 reg_pressure_graph_init,
 305                 reg_pressure_block_init,
 306                 reg_pressure_select,
 307                 NULL,                    /* node_ready */
 308                 NULL,                    /* node_selected */
 309                 reg_pressure_block_free,
 310                 free
 311         };
 312         be_list_sched_graph(irg, &reg_pressure_selector);
 313 }
 314
 315 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_regpress)
 316 void be_init_sched_regpress(void)
 317 {
 318         be_register_scheduler("regpress", sched_reg_pressure);
 319 }