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 "irphase_t.h"
  20 #include "irgwalk.h"
  21 #include "irtools.h"
  22
  23 #include "height.h"
  24
  25 #include "benode_t.h"
  26 #include "besched_t.h"
  27 #include "beschedmris.h"
  28
  29 struct _mris_env_t {
  30         phase_t            ph;
  31         heights_t         *heights;
  32         const arch_env_t  *aenv;
  33         ir_graph          *irg;
  34         ir_node           *bl;
  35         nodeset           *inserted;
  36         int               visited;
  37         struct list_head  lineage_head;
  38         struct obstack    obst;
  39         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  40 };
  41
  42 typedef struct _mris_irn_t {
  43         int visited;
  44         ir_node *lineage_start;
  45         ir_node *lineage_next;
  46         ir_node *lineage_end;
  47         struct list_head lineage_list;
  48 } mris_irn_t;
  49
  50 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
  51
  52 #define get_mris_irn(env, irn)   ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
  53 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
  54
  55 static void *mris_irn_data_init(phase_t *ph, const ir_node *irn, void *data)
  56 {
  57         mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
  58         memset(mi, 0, sizeof(mi[0]));
  59         INIT_LIST_HEAD(&mi->lineage_list);
  60         return mi;
  61 }
  62
  63 #if 0
  64 static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
  65 {
  66         mris_irn_t *mi = get_mris_irn(env, irn);
  67
  68         if(get_irn_visited(irn) >= visited) {
  69                 DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
  70                 return mi->height;
  71         }
  72
  73         else {
  74                 const ir_edge_t *edge;
  75
  76                 set_irn_visited(irn, visited);
  77                 mi->height  = 0;
  78
  79                 foreach_out_edge(irn, edge) {
  80                         ir_node *dep = get_edge_src_irn(edge);
  81
  82                         if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
  83                                 int dep_height = compute_height(env, dep, visited);
  84                                 mi->height     = MAX(mi->height, dep_height);
  85                         }
  86                 }
  87
  88                 mi->height++;
  89                 DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
  90         }
  91
  92         return mi->height;
  93 }
  94
  95 static void compute_heights(mris_env_t *env)
  96 {
  97         const ir_edge_t *edge;
  98         unsigned long visited;
  99
 100         visited = get_irg_visited(env->irg) + 1;
 101         set_irg_visited(env->irg, visited);
 102
 103         foreach_out_edge(env->bl, edge) {
 104                 ir_node *dep = get_edge_src_irn(edge);
 105                 if(to_appear(env, dep))
 106                         compute_height(env, dep, visited);
 107         }
 108 }
 109 #endif
 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         unsigned lowest_height = INT_MAX;
 155         int i;
 156
 157         for(i = 0; in[i]; ++i) {
 158                 unsigned height = get_irn_height(env->heights, in[i]);
 159                 if(height < lowest_height) {
 160                         lowest_height = 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 #if 0
 175 static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
 176 {
 177         if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {
 178
 179                 set_irn_visited(irn, visited);
 180
 181                 if(irn == tgt)
 182                         *found = 1;
 183                 else {
 184                         int i, n;
 185
 186                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 187                                 ir_node *op = get_irn_n(irn, i);
 188                                 if(!*found)
 189                                         reaches_walker(env, op, tgt, found, visited);
 190                         }
 191                 }
 192         }
 193 }
 194
 195 static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
 196 {
 197         int found = 0;
 198         unsigned long visited = get_irg_visited(env->irg) + 1;
 199
 200         set_irg_visited(env->irg, visited);
 201         reaches_walker(env, src, tgt, &found, visited);
 202         return found;
 203 }
 204 #endif
 205
 206 static INLINE ir_node *skip_Projs(ir_node *irn)
 207 {
 208         return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
 209 }
 210
 211 static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
 212 {
 213         int i;
 214
 215         for(i = 0; in[i]; ++i) {
 216                 if(get_irn_mode(in[i]) == mode_T) {
 217                         const ir_edge_t *edge;
 218                         ir_node *proj  = NULL;
 219                         ir_node *first = NULL;
 220
 221                         foreach_out_edge(in[i], edge) {
 222                                 ir_node *desc = get_edge_src_irn(edge);
 223
 224                                 first = first ? first : desc;
 225                                 if(get_irn_mode(desc) == mode_M) {
 226                                         proj = desc;
 227                                         break;
 228                                 }
 229                         }
 230
 231                         proj = proj ? proj : first;
 232                         assert(proj);
 233                         in[i] = proj;
 234                 }
 235         }
 236 }
 237
 238 static void lineage_formation(mris_env_t *env)
 239 {
 240         firm_dbg_module_t *dbg = env->dbg;
 241         nodeset *nodes         = new_nodeset(128);
 242
 243         const ir_edge_t *edge;
 244
 245         foreach_out_edge(env->bl, edge) {
 246                 ir_node *irn = get_edge_src_irn(edge);
 247                 if(to_appear(env, irn))
 248                         nodeset_insert(nodes, irn);
 249         }
 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                 unsigned  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                         unsigned height = get_irn_height(env->heights, irn);
 264                         if(height > curr_height) {
 265                                 highest_node = irn;
 266                                 curr_height  = 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->heights, 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, get_irn_height(env->heights, lowest_desc)));
 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                         heights_recompute(env->heights);
 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 && 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 && 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         heights_recompute(env->heights);
 421
 422         mi = get_mris_irn(env, v_start);
 423         list_del(&mi->lineage_list);
 424
 425         return 1;
 426 }
 427
 428 static void fuse_lineages(mris_env_t *env)
 429 {
 430         int fused = 1;
 431         mris_irn_t *u, *v, *tmp1, *tmp2;
 432
 433 again:
 434         foreach_lineage(env, u, tmp1) {
 435                 foreach_lineage(env, v, tmp2) {
 436                         if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
 437                                 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
 438                                 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
 439                                 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
 440
 441                                 if(uv && !vu) {
 442                                         if(fuse_two_lineages(env, u, v))
 443                                                 goto again;
 444                                 }
 445                         }
 446                 }
 447         }
 448 }
 449
 450 static void block_walker(ir_node *bl, void *data)
 451 {
 452         mris_env_t *env = data;
 453         env->bl = bl;
 454         lineage_formation(env);
 455         fuse_lineages(env);
 456 }
 457
 458
 459 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
 460 {
 461         mris_env_t *env = xmalloc(sizeof(env[0]));
 462
 463         phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
 464         env->aenv     = birg->main_env->arch_env;
 465         env->irg      = birg->irg;
 466         env->visited  = 0;
 467         env->inserted = new_nodeset(128);
 468         env->heights  = heights_new(birg->irg);
 469         INIT_LIST_HEAD(&env->lineage_head);
 470         FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
 471         obstack_init(&env->obst);
 472         irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
 473         irg_block_walk_graph(birg->irg, block_walker, NULL, env);
 474         obstack_free(&env->obst, NULL);
 475         return env;
 476 }
 477
 478 static void cleanup_inserted(mris_env_t *env)
 479 {
 480         ir_node *irn;
 481
 482         foreach_nodeset(env->inserted, irn) {
 483                 int i, n;
 484                 ir_node *tgt;
 485
 486                 assert(be_is_CopyKeep(irn));
 487                 tgt = get_irn_n(irn, be_pos_CopyKeep_op);
 488
 489                 /* reroute the edges, remove from schedule and make it invisible. */
 490                 edges_reroute(irn, tgt, env->irg);
 491                 if (sched_is_scheduled(irn))
 492                         sched_remove(irn);
 493                 for(i = -1, n = get_irn_arity(irn); i < n; ++i)
 494                         set_irn_n(irn, i, new_r_Bad(env->irg));
 495         }
 496 }
 497
 498 void be_sched_mris_free(mris_env_t *env)
 499 {
 500         cleanup_inserted(env);
 501         phase_free(&env->ph);
 502         del_nodeset(env->inserted);
 503         heights_free(env->heights);
 504         free(env);
 505 }