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