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

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