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