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