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  */
  26 #include "config.h"
  27
  28 #include <stdlib.h>
  29
  30 #include "iredges_t.h"
  31 #include "irgwalk.h"
  32 #include "irtools.h"
  33 #include "util.h"
  34
  35 #include "besched.h"
  36 #include "belistsched.h"
  37 #include "benode.h"
  38 #include "bemodule.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         struct obstack obst;
  52         usage_stats_t *root;
  53         ir_nodeset_t already_scheduled;
  54 } reg_pressure_selector_env_t;
  55
  56
  57 static inline usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
  58 {
  59         usage_stats_t *us = (usage_stats_t*)get_irn_link(irn);
  60
  61         if (!us) {
  62                 us                   = OALLOC(&env->obst, usage_stats_t);
  63                 us->irn              = irn;
  64                 us->already_consumed = 0;
  65                 us->max_hops         = INT_MAX;
  66                 us->next             = env->root;
  67                 env->root            = us;
  68                 set_irn_link(irn, us);
  69         }
  70
  71         return us;
  72 }
  73
  74 static inline usage_stats_t *get_usage_stats(ir_node *irn)
  75 {
  76         usage_stats_t *us = (usage_stats_t*)get_irn_link(irn);
  77         assert(us && "This node must have usage stats");
  78         return us;
  79 }
  80
  81 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
  82 {
  83         ir_node *bl = get_nodes_block(irn);
  84         /*
  85         * If the reached node is not in the block desired,
  86         * return the value passed for this situation.
  87         */
  88         if (get_nodes_block(irn) != bl)
  89                 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
  90
  91         /*
  92         * If the node is in the current block but not
  93         * yet scheduled, we keep on searching from that node.
  94         */
  95         if (!ir_nodeset_contains(&env->already_scheduled, irn)) {
  96                 int i, n;
  97                 int res = 0;
  98                 for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
  99                         ir_node *operand = get_irn_in_or_dep(irn, i);
 100
 101                         if (get_irn_visited(operand) < visited_nr) {
 102                                 int tmp;
 103
 104                                 set_irn_visited(operand, visited_nr);
 105                                 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
 106                                 res = MAX(tmp, res);
 107                         }
 108                 }
 109
 110                 return res;
 111         }
 112
 113         /*
 114         * If the node is in the current block and scheduled, return
 115         * the depth which indicates the number of steps to the
 116         * region of scheduled nodes.
 117         */
 118         return depth;
 119 }
 120
 121 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
 122 {
 123         ir_node *bl   = get_nodes_block(irn);
 124         ir_graph *irg = get_irn_irg(bl);
 125         int res       = 0;
 126
 127         foreach_out_edge(irn, edge) {
 128                 ir_node *user       = get_edge_src_irn(edge);
 129                 unsigned visited_nr = get_irg_visited(irg) + 1;
 130                 int max_hops;
 131
 132                 set_irg_visited(irg, visited_nr);
 133                 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
 134                 res      = MAX(res, max_hops);
 135         }
 136
 137         return res;
 138 }
 139
 140 static void *reg_pressure_graph_init(ir_graph *irg)
 141 {
 142         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 143
 144         return NULL;
 145 }
 146
 147 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
 148 {
 149         reg_pressure_selector_env_t *env = XMALLOC(reg_pressure_selector_env_t);
 150         (void) graph_env;
 151
 152         obstack_init(&env->obst);
 153         ir_nodeset_init(&env->already_scheduled);
 154         env->root              = NULL;
 155
 156         /*
 157         * Collect usage statistics.
 158         */
 159         sched_foreach(bl, irn) {
 160                 for (int i = 0, n = get_irn_arity(irn); i < n; ++i) {
 161                         usage_stats_t *us = get_or_set_usage_stats(env, irn);
 162                         us->uses_in_block++;
 163                 }
 164         }
 165
 166         return env;
 167 }
 168
 169 static void reg_pressure_block_free(void *block_env)
 170 {
 171         reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env;
 172         usage_stats_t *us;
 173
 174         for (us = env->root; us; us = us->next)
 175                 set_irn_link(us->irn, NULL);
 176
 177         obstack_free(&env->obst, NULL);
 178         ir_nodeset_destroy(&env->already_scheduled);
 179         free(env);
 180 }
 181
 182 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
 183 {
 184         int res = 0;
 185         if (get_irn_mode(irn) == mode_T) {
 186                 foreach_out_edge(irn, edge)
 187                         res += get_result_hops_sum(env, get_edge_src_irn(edge));
 188         }
 189
 190         else if (mode_is_data(get_irn_mode(irn)))
 191                 res = compute_max_hops(env, irn);
 192
 193
 194         return res;
 195 }
 196
 197 static inline int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
 198 {
 199         int i, n;
 200         int sum = 0;
 201
 202         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 203                 ir_node *op = get_irn_n(irn, i);
 204
 205                 if (is_Proj(op)
 206                     || (arch_get_irn_flags(op) & arch_irn_flags_not_scheduled))
 207                         continue;
 208
 209                 sum += compute_max_hops(env, op);
 210         }
 211
 212         sum += get_result_hops_sum(env, irn);
 213
 214         return sum;
 215 }
 216
 217 static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set)
 218 {
 219         reg_pressure_selector_env_t *env = (reg_pressure_selector_env_t*)block_env;
 220         ir_node *res       = NULL;
 221         int      curr_cost = INT_MAX;
 222
 223         assert(ir_nodeset_size(ready_set) > 0);
 224
 225         foreach_ir_nodeset(ready_set, irn, iter) {
 226                 /*
 227                 Ignore branch instructions for the time being.
 228                 They should only be scheduled if there is nothing else.
 229                 */
 230                 if (!is_cfop(irn)) {
 231                         int costs = reg_pr_costs(env, irn);
 232                         if (costs <= curr_cost) {
 233                                 res       = irn;
 234                                 curr_cost = costs;
 235                         }
 236                 }
 237         }
 238
 239         /*
 240         There was no result so we only saw a branch.
 241         Take it and finish.
 242         */
 243
 244         if (!res) {
 245                 res = ir_nodeset_first(ready_set);
 246                 assert(res && "There must be a node scheduled.");
 247         }
 248
 249         ir_nodeset_insert(&env->already_scheduled, res);
 250         return res;
 251 }
 252
 253 static void sched_reg_pressure(ir_graph *irg)
 254 {
 255         static const list_sched_selector_t reg_pressure_selector = {
 256                 reg_pressure_graph_init,
 257                 reg_pressure_block_init,
 258                 reg_pressure_select,
 259                 NULL,                    /* node_ready */
 260                 NULL,                    /* node_selected */
 261                 reg_pressure_block_free,
 262                 free
 263         };
 264         be_list_sched_graph(irg, &reg_pressure_selector);
 265 }
 266
 267 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_regpress)
 268 void be_init_sched_regpress(void)
 269 {
 270         be_register_scheduler("regpress", sched_reg_pressure);
 271 }