nsz Git - libfirm/blob - ir/be/beschedmris.c

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