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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @brief   Use the strong normal form theorem (though it does not hold)
   8  * @author  Christoph Mallon
   9  */
  10 #include "config.h"
  11
  12 #include <stdlib.h>
  13
  14 #include "besched.h"
  15 #include "belistsched.h"
  16 #include "belive_t.h"
  17 #include "beutil.h"
  18 #include "heights.h"
  19 #include "irgwalk.h"
  20 #include "benode.h"
  21 #include "bemodule.h"
  22 #include "util.h"
  23 #include "array_t.h"
  24
  25 // XXX there is no one time init for schedulers
  26 //#define NORMAL_DBG
  27 #include "irprintf.h"
  28
  29 /** An instance of the normal scheduler. */
  30 typedef struct instance_t {
  31         ir_graph*      irg;          /**< the IR graph of this instance */
  32         struct obstack obst;         /**< obstack for temporary data */
  33         ir_node*       curr_list;    /**< current block schedule list */
  34 } instance_t;
  35
  36 static int must_be_scheduled(const ir_node* const irn)
  37 {
  38         return !is_Proj(irn) && !arch_irn_is(irn, not_scheduled);
  39 }
  40
  41
  42 static ir_node *normal_select(void *block_env, ir_nodeset_t *ready_set)
  43 {
  44         instance_t* inst = (instance_t*)block_env;
  45         ir_node*    irn;
  46         ir_node*    next;
  47         ir_node*    last = NULL;
  48
  49         for (irn = inst->curr_list; irn != NULL; last = irn, irn = next) {
  50                 next = (ir_node*)get_irn_link(irn);
  51                 if (ir_nodeset_contains(ready_set, irn)) {
  52 #if defined NORMAL_DBG
  53                         ir_fprintf(stderr, "scheduling %+F\n", irn);
  54 #endif
  55                         if (last == NULL)
  56                                 inst->curr_list = next;
  57                         else
  58                                 set_irn_link(last, next);
  59                         return irn;
  60                 }
  61         }
  62
  63         return ir_nodeset_first(ready_set);
  64 }
  65
  66
  67 typedef struct irn_cost_pair {
  68         ir_node* irn;
  69         int      cost;
  70 } irn_cost_pair;
  71
  72 static int cost_cmp(const void* a, const void* b)
  73 {
  74         const irn_cost_pair* const a1 = (const irn_cost_pair*)a;
  75         const irn_cost_pair* const b1 = (const irn_cost_pair*)b;
  76         int ret = b1->cost - a1->cost;
  77         if (ret == 0)
  78                 ret = (int)get_irn_idx(a1->irn) - (int)get_irn_idx(b1->irn);
  79 #if defined NORMAL_DBG
  80         ir_fprintf(stderr, "cost %+F %s %+F\n", a1->irn, ret < 0 ? "<" : ret > 0 ? ">" : "=", b1->irn);
  81 #endif
  82         return ret;
  83 }
  84
  85
  86 typedef struct flag_and_cost {
  87         int no_root;
  88         irn_cost_pair costs[];
  89 } flag_and_cost;
  90
  91 #define get_irn_fc(irn)     ((flag_and_cost*)get_irn_link(irn))
  92 #define set_irn_fc(irn, fc) set_irn_link(irn, fc)
  93
  94
  95 static int count_result(const ir_node* irn)
  96 {
  97         const ir_mode* mode = get_irn_mode(irn);
  98
  99         if (mode == mode_M || mode == mode_X)
 100                 return 0;
 101
 102         if (mode == mode_T)
 103                 return 1;
 104
 105         arch_register_req_t const *const req = arch_get_irn_register_req(irn);
 106         if (arch_register_req_is(req, ignore))
 107                 return 0;
 108
 109         return 1;
 110 }
 111
 112
 113 /* TODO high cost for store trees
 114  */
 115
 116 static int normal_tree_cost(ir_node* irn, instance_t *inst)
 117 {
 118         flag_and_cost* fc;
 119         int            arity;
 120         ir_node*       last;
 121         int            n_res;
 122         int            cost;
 123         int            n_op_res = 0;
 124         int            i;
 125
 126         if (be_is_Keep(irn))
 127                 return 0;
 128
 129         if (is_Proj(irn)) {
 130                 return normal_tree_cost(get_Proj_pred(irn), inst);
 131         }
 132
 133         arity = get_irn_arity(irn);
 134         fc    = get_irn_fc(irn);
 135
 136         if (fc == NULL) {
 137                 irn_cost_pair* costs;
 138                 ir_node*       block = get_nodes_block(irn);
 139
 140                 fc = OALLOCF(&inst->obst, flag_and_cost, costs, arity);
 141                 fc->no_root = 0;
 142                 costs = fc->costs;
 143
 144                 for (i = 0; i < arity; ++i) {
 145                         ir_node* pred = get_irn_n(irn, i);
 146
 147                         if (is_Phi(irn) || get_irn_mode(pred) == mode_M) {
 148                                 cost = 0;
 149                         } else if (get_nodes_block(pred) != block) {
 150                                 cost = 1;
 151                         } else {
 152                                 flag_and_cost* pred_fc;
 153                                 ir_node*       real_pred;
 154
 155                                 cost = normal_tree_cost(pred, inst);
 156                                 if (!arch_irn_is_ignore(pred)) {
 157                                         real_pred = (is_Proj(pred) ? get_Proj_pred(pred) : pred);
 158                                         pred_fc = get_irn_fc(real_pred);
 159                                         pred_fc->no_root = 1;
 160 #if defined NORMAL_DBG
 161                                         ir_fprintf(stderr, "%+F says that %+F is no root\n", irn, real_pred);
 162 #endif
 163                                 }
 164                         }
 165
 166                         costs[i].irn  = pred;
 167                         costs[i].cost = cost;
 168                 }
 169
 170                 qsort(costs, arity, sizeof(*costs), cost_cmp);
 171                 set_irn_link(irn, fc);
 172         }
 173
 174         cost = 0;
 175         last = 0;
 176         for (i = 0; i < arity; ++i) {
 177                 ir_node* op = fc->costs[i].irn;
 178                 ir_mode* mode;
 179                 if (op == last)
 180                         continue;
 181                 mode = get_irn_mode(op);
 182                 if (mode == mode_M)
 183                         continue;
 184                 if (arch_irn_is_ignore(op))
 185                         continue;
 186                 cost = MAX(fc->costs[i].cost + n_op_res, cost);
 187                 last = op;
 188                 ++n_op_res;
 189         }
 190         n_res = count_result(irn);
 191         cost = MAX(n_res, cost);
 192
 193 #if defined NORMAL_DBG
 194         ir_fprintf(stderr, "reguse of %+F is %d\n", irn, cost);
 195 #endif
 196
 197         return cost;
 198 }
 199
 200
 201 static void normal_cost_walker(ir_node* irn, void* env)
 202 {
 203         instance_t *inst = (instance_t*)env;
 204
 205 #if defined NORMAL_DBG
 206         ir_fprintf(stderr, "cost walking node %+F\n", irn);
 207 #endif
 208         if (is_Block(irn)) {
 209                 ir_node **const roots = NEW_ARR_F(ir_node*, 0);
 210                 set_irn_link(irn, roots);
 211                 return;
 212         }
 213         if (!must_be_scheduled(irn)) return;
 214         normal_tree_cost(irn, inst);
 215 }
 216
 217
 218 static void collect_roots(ir_node* irn, void* env)
 219 {
 220         int is_root;
 221
 222         (void)env;
 223
 224         if (!must_be_scheduled(irn)) return;
 225
 226         is_root = be_is_Keep(irn) || !get_irn_fc(irn)->no_root;
 227
 228 #if defined NORMAL_DBG
 229         ir_fprintf(stderr, "%+F is %sroot\n", irn, is_root ? "" : "no ");
 230 #endif
 231
 232         if (is_root) {
 233                 ir_node* block = get_nodes_block(irn);
 234                 ir_node** roots = (ir_node**)get_irn_link(block);
 235                 ARR_APP1(ir_node*, roots, irn);
 236                 set_irn_link(block, roots);
 237         }
 238 }
 239
 240
 241 static ir_node** sched_node(ir_node** sched, ir_node* irn)
 242 {
 243         if (irn_visited_else_mark(irn)) return sched;
 244
 245         if (!is_Phi(irn) && !be_is_Keep(irn)) {
 246                 ir_node*       block = get_nodes_block(irn);
 247                 int            arity = get_irn_arity(irn);
 248                 flag_and_cost* fc    = get_irn_fc(irn);
 249                 irn_cost_pair* irns  = fc->costs;
 250                 int            i;
 251
 252                 for (i = 0; i < arity; ++i) {
 253                         ir_node* pred = irns[i].irn;
 254                         if (get_nodes_block(pred) != block) continue;
 255                         if (get_irn_mode(pred) == mode_M) continue;
 256                         if (is_Proj(pred)) pred = get_Proj_pred(pred);
 257                         sched = sched_node(sched, pred);
 258                 }
 259         }
 260
 261         ARR_APP1(ir_node*, sched, irn);
 262         return sched;
 263 }
 264
 265
 266 static int root_cmp(const void* a, const void* b)
 267 {
 268         const irn_cost_pair* const a1 = (const irn_cost_pair*)a;
 269         const irn_cost_pair* const b1 = (const irn_cost_pair*)b;
 270         int ret;
 271         if (is_irn_forking(a1->irn) && !is_irn_forking(b1->irn)) {
 272                 ret = 1;
 273         } else if (is_irn_forking(b1->irn) && !is_irn_forking(a1->irn)) {
 274                 ret = -1;
 275         } else {
 276                 ret = b1->cost - a1->cost;
 277                 if (ret == 0) {
 278                         /* place live-out nodes later */
 279                         ret = (count_result(a1->irn) != 0) - (count_result(b1->irn) != 0);
 280                         if (ret == 0) {
 281                                 /* compare node idx */
 282                                 ret = get_irn_idx(a1->irn) - get_irn_idx(b1->irn);
 283                         }
 284                 }
 285         }
 286 #if defined NORMAL_DBG
 287         ir_fprintf(stderr, "root %+F %s %+F\n", a1->irn, ret < 0 ? "<" : ret > 0 ? ">" : "=", b1->irn);
 288 #endif
 289         return ret;
 290 }
 291
 292
 293 static void normal_sched_block(ir_node* block, void* env)
 294 {
 295         ir_node**      roots = (ir_node**)get_irn_link(block);
 296         ir_heights_t*  heights = (ir_heights_t*)env;
 297         irn_cost_pair* root_costs;
 298         int i;
 299         ir_node**      sched;
 300
 301 #if defined NORMAL_DBG
 302         ir_fprintf(stderr, "sched walking block %+F\n", block);
 303 #endif
 304
 305         int const root_count = ARR_LEN(roots);
 306         if (root_count == 0) {
 307 #if defined NORMAL_DBG
 308                 fprintf(stderr, "has no roots\n");
 309 #endif
 310                 return;
 311         }
 312
 313         NEW_ARR_A(irn_cost_pair, root_costs, root_count);
 314         for (i = 0; i < root_count; ++i) {
 315                 root_costs[i].irn  = roots[i];
 316                 root_costs[i].cost = get_irn_height(heights, roots[i]);
 317 #if defined NORMAL_DBG
 318                 ir_fprintf(stderr, "height of %+F is %u\n", roots[i], root_costs[i].cost);
 319 #endif
 320         }
 321         qsort(root_costs, root_count, sizeof(*root_costs), root_cmp);
 322 #if defined NORMAL_DBG
 323         {
 324                 int n = root_count;
 325                 int i;
 326
 327                 ir_fprintf(stderr, "Root Scheduling of %+F:\n", block);
 328                 for (i = 0; i < n; ++i) {
 329                         ir_fprintf(stderr, "  %+F\n", root_costs[i].irn);
 330                 }
 331                 fprintf(stderr, "\n");
 332         }
 333 #endif
 334
 335         sched = NEW_ARR_F(ir_node*, 0);
 336         for (i = 0; i < root_count; ++i) {
 337                 ir_node* irn = root_costs[i].irn;
 338                 assert(must_be_scheduled(irn));
 339                 sched = sched_node(sched, irn);
 340         }
 341         set_irn_link(block, sched);
 342         DEL_ARR_F(roots);
 343
 344 #if defined NORMAL_DBG
 345         {
 346                 int n = ARR_LEN(sched);
 347                 int i;
 348
 349                 ir_fprintf(stderr, "Scheduling of %+F:\n", block);
 350                 for (i = 0; i < n; ++i) {
 351                         ir_fprintf(stderr, "  %+F\n", sched[i]);
 352                 }
 353                 fprintf(stderr, "\n");
 354         }
 355 #endif
 356 }
 357
 358
 359 static void *normal_init_graph(ir_graph *irg)
 360 {
 361         instance_t   *inst = XMALLOC(instance_t);
 362         ir_heights_t *heights;
 363
 364         be_clear_links(irg);
 365
 366         obstack_init(&inst->obst);
 367         inst->irg         = irg;
 368
 369         heights = heights_new(irg);
 370
 371         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 372         irg_walk_graph(irg, normal_cost_walker,  NULL, inst);
 373         irg_walk_graph(irg, collect_roots, NULL, NULL);
 374         inc_irg_visited(irg);
 375         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 376         irg_block_walk_graph(irg, normal_sched_block, NULL, heights);
 377         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 378
 379         heights_free(heights);
 380
 381         return inst;
 382 }
 383
 384 static void *normal_init_block(void *graph_env, ir_node *block)
 385 {
 386         instance_t* inst  = (instance_t*)graph_env;
 387         ir_node**   sched = (ir_node**)get_irn_link(block);
 388         ir_node*    first = NULL;
 389         int         i;
 390
 391         /* turn into a list, so we can easily remove nodes.
 392            The link field is used anyway. */
 393         for (i = ARR_LEN(sched) - 1; i >= 0; --i) {
 394                 ir_node* irn = sched[i];
 395                 if (!is_cfop(irn)) {
 396                         set_irn_link(irn, first);
 397                         first = irn;
 398                 }
 399         }
 400         /* note: we can free sched here, there should be no attempt to schedule
 401            a block twice */
 402         DEL_ARR_F(sched);
 403         set_irn_link(block, sched);
 404         inst->curr_list = first;
 405         return inst;
 406 }
 407
 408 static void normal_finish_graph(void *env)
 409 {
 410         instance_t *inst = (instance_t*)env;
 411
 412         /* block uses the link field to store the schedule */
 413         ir_free_resources(inst->irg, IR_RESOURCE_IRN_LINK);
 414         obstack_free(&inst->obst, NULL);
 415         xfree(inst);
 416 }
 417
 418 static void sched_normal(ir_graph *irg)
 419 {
 420         static const list_sched_selector_t normal_selector = {
 421                 normal_init_graph,
 422                 normal_init_block,
 423                 normal_select,
 424                 NULL,              /* node_ready */
 425                 NULL,              /* node_selected */
 426                 NULL,              /* finish_block */
 427                 normal_finish_graph
 428         };
 429         be_list_sched_graph(irg, &normal_selector);
 430 }
 431
 432 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched_normal)
 433 void be_init_sched_normal(void)
 434 {
 435         be_register_scheduler("normal", sched_normal);
 436 }