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

   1 /**
   2  * Implements a list scheduler for the MRIS algorithm in:
   3  * Govindarajan, Yang, Amaral, Zhang, Gao
   4  * Minimum Register Instruction Sequencing to Reduce Register Spills
   5  * in out-of-order issue superscalar architectures
   6  * @author Sebastian Hack
   7  * @date   04.04.2006
   8  */
   9
  10 #include <limits.h>
  11
  12 #include "obst.h"
  13 #include "debug.h"
  14
  15 #include "irgraph_t.h"
  16 #include "irnode_t.h"
  17 #include "iredges_t.h"
  18 #include "ircons_t.h"
  19 #include "irgwalk.h"
  20 #include "irtools.h"
  21
  22 #include "benode_t.h"
  23 #include "besched_t.h"
  24 #include "beschedmris.h"
  25
  26 struct _mris_env_t {
  27         firm_dbg_module_t *dbg;
  28         const arch_env_t  *aenv;
  29         ir_graph          *irg;
  30         ir_node           *bl;
  31         nodeset           *inserted;
  32         int               visited;
  33         struct list_head  lineage_head;
  34         struct obstack    obst;
  35 };
  36
  37 typedef struct _mris_irn_t {
  38         int visited;
  39         int height;
  40         ir_node *lineage_start;
  41         ir_node *lineage_next;
  42         ir_node *lineage_end;
  43         struct list_head lineage_list;
  44 } mris_irn_t;
  45
  46 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
  47
  48 #define get_irn_height(env, irn) (get_mris_irn(env, irn)->height)
  49 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
  50
  51 static mris_irn_t *get_mris_irn(mris_env_t *env, ir_node *irn)
  52 {
  53         mris_irn_t *mi = get_irn_link(irn);
  54
  55         if(!mi) {
  56                 mi = obstack_alloc(&env->obst, sizeof(mi[0]));
  57                 memset(mi, 0, sizeof(mi[0]));
  58                 set_irn_link(irn, mi);
  59                 INIT_LIST_HEAD(&mi->lineage_list);
  60         }
  61
  62         return mi;
  63 }
  64
  65 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
  66 {
  67         mris_irn_t *mi = get_mris_irn(env, irn);
  68
  69         if(get_irn_visited(irn) >= visited) {
  70                 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
  71                 return mi->height;
  72         }
  73
  74         else {
  75                 const ir_edge_t *edge;
  76
  77                 set_irn_visited(irn, visited);
  78                 mi->height  = 0;
  79
  80                 foreach_out_edge(irn, edge) {
  81                         ir_node *dep = get_edge_src_irn(edge);
  82
  83                         if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
  84                                 int dep_height = compute_height(env, dep, visited);
  85                                 mi->height     = MAX(mi->height, dep_height);
  86                         }
  87                 }
  88
  89                 mi->height++;
  90                 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
  91         }
  92
  93         return mi->height;
  94 }
  95
  96 static void compute_heights(mris_env_t *env)
  97 {
  98         const ir_edge_t *edge;
  99         unsigned long visited;
 100
 101         visited = get_irg_visited(env->irg) + 1;
 102         set_irg_visited(env->irg, visited);
 103
 104         foreach_out_edge(env->bl, edge) {
 105                 ir_node *dep = get_edge_src_irn(edge);
 106                 if(to_appear(env, dep))
 107                         compute_height(env, dep, visited);
 108         }
 109 }
 110
 111 #define valid_node(env, dep) (to_appear(env, dep) && !nodeset_find(env->inserted, dep) && !be_is_Keep(dep))
 112
 113 static void grow_all_descendands(mris_env_t *env, ir_node *irn, unsigned long visited)
 114 {
 115         const ir_edge_t *edge;
 116
 117         assert(get_irn_mode(irn) != mode_T);
 118
 119         foreach_out_edge(irn, edge) {
 120                 ir_node *desc = get_edge_src_irn(edge);
 121                 if(valid_node(env, desc) && get_irn_visited(desc) < visited) {
 122                         obstack_ptr_grow(&env->obst, desc);
 123                         set_irn_visited(desc, visited);
 124                 }
 125         }
 126 }
 127
 128 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
 129 {
 130         unsigned long visited;
 131         const ir_edge_t *edge;
 132
 133         visited = get_irg_visited(env->irg) + 1;
 134         set_irg_visited(env->irg, visited);
 135
 136         if(get_irn_mode(irn) == mode_T) {
 137                 foreach_out_edge(irn, edge) {
 138                         ir_node *desc = get_edge_src_irn(edge);
 139                         assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
 140                         grow_all_descendands(env, desc, visited);
 141                 }
 142         }
 143
 144         else
 145                 grow_all_descendands(env, irn, visited);
 146
 147         obstack_ptr_grow(&env->obst, NULL);
 148         return obstack_finish(&env->obst);
 149 }
 150
 151 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
 152 {
 153         int lowest_index  = 0;
 154         int lowest_height = INT_MAX;
 155         int i;
 156
 157         for(i = 0; in[i]; ++i) {
 158                 mris_irn_t *mi = get_mris_irn(env, in[i]);
 159                 if(mi->height < lowest_height) {
 160                         lowest_height = mi->height;
 161                         lowest_index  = i;
 162                 }
 163         }
 164
 165         if(i > 0) {
 166                 ir_node *tmp     = in[0];
 167                 in[0]            = in[lowest_index];
 168                 in[lowest_index] = tmp;
 169         }
 170
 171         return in[0];
 172 }
 173
 174 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
 175 {
 176         if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
 177
 178                 set_irn_visited(irn, visited);
 179
 180                 if(irn == tgt)
 181                         *found = 1;
 182                 else {
 183                         int i, n;
 184
 185                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 186                                 ir_node *op = get_irn_n(irn, i);
 187                                 if(!*found)
 188                                         reaches_walker(env, op, tgt, found, visited);
 189                         }
 190                 }
 191         }
 192 }
 193
 194 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
 195 {
 196         int found = 0;
 197         unsigned long visited = get_irg_visited(env->irg) + 1;
 198
 199         set_irg_visited(env->irg, visited);
 200         reaches_walker(env, src, tgt, &found, visited);
 201         return found;
 202 }
 203
 204 static INLINE ir_node *skip_Projs(ir_node *irn)
 205 {
 206         return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
 207 }
 208
 209 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
 210 {
 211         int i;
 212
 213         for(i = 0; in[i]; ++i) {
 214                 if(get_irn_mode(in[i]) == mode_T) {
 215                         const ir_edge_t *edge;
 216                         ir_node *proj  = NULL;
 217                         ir_node *first = NULL;
 218
 219                         foreach_out_edge(in[i], edge) {
 220                                 ir_node *desc = get_edge_src_irn(edge);
 221
 222                                 first = first ? first : desc;
 223                                 if(get_irn_mode(desc) == mode_M) {
 224                                         proj = desc;
 225                                         break;
 226                                 }
 227                         }
 228
 229                         proj = proj ? proj : first;
 230                         assert(proj);
 231                         in[i] = proj;
 232                 }
 233         }
 234 }
 235
 236 static void lineage_formation(mris_env_t *env)
 237 {
 238         firm_dbg_module_t *dbg = env->dbg;
 239         nodeset *nodes         = new_nodeset(128);
 240
 241         const ir_edge_t *edge;
 242
 243         foreach_out_edge(env->bl, edge) {
 244                 ir_node *irn = get_edge_src_irn(edge);
 245                 if(to_appear(env, irn))
 246                         nodeset_insert(nodes, irn);
 247         }
 248
 249         compute_heights(env);
 250
 251         while(nodeset_count(nodes) > 0) {
 252                 mris_irn_t *mi;
 253                 ir_node *irn;
 254                 ir_node *highest_node = NULL;
 255                 ir_node *lowest_desc  = NULL;
 256
 257                 ir_node **in;
 258                 int recompute_height  = 0;
 259                 int curr_height       = 0;
 260
 261                 /* search the highest node which is not yet in a lineage. */
 262                 for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
 263                         mris_irn_t *inf = get_mris_irn(env, irn);
 264                         if(inf->height > curr_height) {
 265                                 highest_node = irn;
 266                                 curr_height  = inf->height;
 267                         }
 268                 }
 269
 270                 assert(highest_node);
 271                 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env, highest_node)));
 272
 273                 /* start a lineage beginning with highest_node. */
 274                 mi = get_mris_irn(env, highest_node);
 275                 mi->lineage_start = highest_node;
 276                 mi->lineage_next  = NULL;
 277                 mi->lineage_end   = NULL;
 278                 list_add(&mi->lineage_list, &env->lineage_head);
 279                 nodeset_remove(nodes, highest_node);
 280
 281                 /*
 282                         put all descendants in an array.
 283                         we also move the lowest descendant in front, so that the other nodes
 284                         are easily accessible as an array, too.
 285                 */
 286                 in          = all_descendants(env, highest_node);
 287                 lowest_desc = put_lowest_in_front(env, in);
 288
 289                 /* as long as the current highest node has still descendants */
 290                 while(lowest_desc) {
 291                         mris_irn_t *lowest_mi  = get_mris_irn(env, lowest_desc);
 292                         mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
 293                         mris_irn_t *start_mi   = get_mris_irn(env, highest_mi->lineage_start);
 294                         int highest_is_tuple   = get_irn_mode(highest_node) == mode_T;
 295
 296                         int n_desc;
 297
 298                         DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, mi->height));
 299
 300                         /* count the number of all descendants which are not the lowest descendant */
 301                         for(n_desc = 0; in[n_desc + 1]; ++n_desc);
 302
 303                         /*
 304                         we insert a CopyKeep node to express the artificial dependencies from the lowest
 305                         descendant to all other descendants.
 306                         */
 307                         if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
 308                                 const arch_register_class_t *cls;
 309                                 ir_node *copy_keep, *op;
 310                                 int i, n;
 311
 312                                 for(i = 0, n = get_irn_arity(lowest_desc); i < n; ++i) {
 313                                         ir_node *cmp;
 314
 315                                         op  = get_irn_n(lowest_desc, i);
 316                                         cmp = highest_is_tuple ? skip_Projs(op) : op;
 317
 318                                         if(cmp == highest_node)
 319                                                 break;
 320                                 }
 321
 322                                 assert(i < n && "could not find operand");
 323
 324                                 cls = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
 325                                 replace_tuple_by_repr_proj(env, &in[1]);
 326                                 copy_keep = be_new_CopyKeep(cls, env->irg, env->bl, op, n_desc, &in[1], get_irn_mode(op));
 327                                 set_irn_n(lowest_desc, i, copy_keep);
 328                                 nodeset_insert(env->inserted, copy_keep);
 329                         }
 330                         obstack_free(&env->obst, in);
 331
 332                         /* mark the current lowest node as the last one in the lineage. */
 333                         highest_mi->lineage_next = lowest_desc;
 334                         start_mi->lineage_end    = lowest_desc;
 335
 336                         /* if the current lowest node is not yet in a lineage, add it to the current one. */
 337                         if(!lowest_mi->lineage_start) {
 338                                 lowest_mi->lineage_start = highest_mi->lineage_start;
 339                                 nodeset_remove(nodes, lowest_desc);
 340                         }
 341
 342                         /* else we cannot extend this lineage, so break. */
 343                         else
 344                                 break;
 345
 346                         highest_node = lowest_desc;
 347                         highest_mi   = lowest_mi;
 348
 349                         /* recompute the descendants array and the new lowest descendant. */
 350                         in          = all_descendants(env, highest_node);
 351                         lowest_desc = put_lowest_in_front(env, in);
 352                 }
 353
 354                 /* recompute the heights if desired. */
 355                 if(recompute_height)
 356                         compute_heights(env);
 357         }
 358 }
 359
 360 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
 361 {
 362         mris_irn_t *mi;
 363         mris_irn_t *copy_mi;
 364         ir_node *irn, *last, *copy;
 365         ir_node *u_end   = u->lineage_end;
 366         ir_node *v_start = v->lineage_start;
 367         ir_node *start   = skip_Projs(v_start);
 368
 369         if(be_is_Keep(start))
 370                 return 0;
 371
 372         /* set lineage end of nodes in u to end of v. */
 373         irn = last = u->lineage_start;
 374         mi         = get_mris_irn(env, irn);
 375         while(irn != u_end) {
 376                 mi = get_mris_irn(env, irn);
 377                 mi->lineage_end = v->lineage_end;
 378                 last = irn;
 379                 irn = mi->lineage_next;
 380         }
 381
 382         /* insert a CopyKeep to make lineage v dependent on u. */
 383         {
 384                 const arch_register_class_t *cls;
 385                 ir_node *op    = NULL;
 386
 387                 if(get_irn_arity(start) == 0)
 388                         return 0;
 389
 390                 op = get_irn_n(start, 0);
 391
 392                 cls  = arch_get_irn_reg_class(env->aenv, op, BE_OUT_POS(0));
 393                 if(get_irn_mode(last) == mode_T) {
 394                         const ir_edge_t *edge;
 395                         foreach_out_edge(last, edge) {
 396                                 last = get_edge_src_irn(edge);
 397                                 break;
 398                         }
 399                 }
 400                 copy = be_new_CopyKeep_single(cls, env->irg, env->bl, op, last, get_irn_mode(op));
 401                 set_irn_n(start, 0, copy);
 402                 copy_mi = get_mris_irn(env, copy);
 403                 nodeset_insert(env->inserted, copy);
 404         }
 405
 406         /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
 407         mi->lineage_next       = copy;
 408         copy_mi->lineage_start = u->lineage_start;
 409         copy_mi->lineage_end   = v->lineage_end;
 410         copy_mi->lineage_next  = v_start;
 411
 412         /* set lineage start of nodes in v to start of u. */
 413         irn = v->lineage_start;
 414         while(irn != v->lineage_end) {
 415                 mris_irn_t *mi = get_mris_irn(env, irn);
 416                 mi->lineage_start = u->lineage_start;
 417                 irn = mi->lineage_next;
 418         }
 419
 420         mi = get_mris_irn(env, v_start);
 421         list_del(&mi->lineage_list);
 422
 423         return 1;
 424 }
 425
 426 static void fuse_lineages(mris_env_t *env)
 427 {
 428         int fused = 1;
 429         mris_irn_t *u, *v, *tmp1, *tmp2;
 430
 431 again:
 432         foreach_lineage(env, u, tmp1) {
 433                 foreach_lineage(env, v, tmp2) {
 434                         if(u == v)
 435                                 continue;
 436
 437                         if(!reaches(env, u->lineage_start, v->lineage_end) && reaches(env, v->lineage_start, u->lineage_end)) {
 438                                 if(fuse_two_lineages(env, u, v))
 439                                         goto again;
 440                         }
 441                 }
 442         }
 443 }
 444
 445 static void block_walker(ir_node *bl, void *data)
 446 {
 447         mris_env_t *env = data;
 448         env->bl = bl;
 449         lineage_formation(env);
 450         fuse_lineages(env);
 451 }
 452
 453
 454 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
 455 {
 456         mris_env_t *env = xmalloc(sizeof(env[0]));
 457
 458         env->aenv     = birg->main_env->arch_env;
 459         env->irg      = birg->irg;
 460         env->visited  = 0;
 461         env->inserted = new_nodeset(128);
 462         INIT_LIST_HEAD(&env->lineage_head);
 463         FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
 464         obstack_init(&env->obst);
 465         irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
 466         irg_block_walk_graph(birg->irg, block_walker, NULL, env);
 467         obstack_free(&env->obst, NULL);
 468         return env;
 469 }
 470
 471 static void cleanup_inserted(mris_env_t *env)
 472 {
 473         ir_node *irn;
 474
 475         foreach_nodeset(env->inserted, irn) {
 476                 int i, n;
 477                 ir_node *tgt;
 478
 479                 assert(be_is_CopyKeep(irn));
 480                 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
 481
 482                 /* reroute the edges, remove from schedule and make it invisible. */
 483                 edges_reroute(irn, tgt, env->irg);
 484                 if (sched_is_scheduled(irn))
 485                         sched_remove(irn);
 486                 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
 487                         set_irn_n(irn, i, new_r_Bad(env->irg));
 488         }
 489 }
 490
 491 void be_sched_mris_free(mris_env_t *env)
 492 {
 493         cleanup_inserted(env);
 494         del_nodeset(env->inserted);
 495         free(env);
 496 }