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