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

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "config.h"
  33
  34 #include <limits.h>
  35
  36 #include "obst.h"
  37 #include "debug.h"
  38
  39 #include "irgraph_t.h"
  40 #include "irnode_t.h"
  41 #include "iredges_t.h"
  42 #include "ircons_t.h"
  43 #include "irphase_t.h"
  44 #include "irdump_t.h"
  45 #include "irgwalk.h"
  46 #include "irtools.h"
  47 #include "irbitset.h"
  48 #include "irnodeset.h"
  49 #include "heights.h"
  50
  51 #include "benode.h"
  52 #include "besched.h"
  53 #include "beschedmris.h"
  54 #include "beirg.h"
  55 #include "belistsched.h"
  56
  57 struct mris_env_t {
  58         ir_phase          ph;
  59         ir_heights_t      *heights;
  60         ir_graph          *irg;
  61         ir_node           *bl;
  62         int               visited;
  63         struct list_head  lineage_head;
  64         struct obstack    obst;
  65         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  66 };
  67
  68 typedef struct mris_irn_t {
  69         int visited;
  70         ir_node *lineage_start;
  71         ir_node *lineage_next;
  72         ir_node *lineage_end;
  73         struct list_head lineage_list;
  74 } mris_irn_t;
  75
  76 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
  77
  78 #define get_mris_irn(env, irn)   ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
  79 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
  80
  81 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn)
  82 {
  83         mris_irn_t *mi = (mris_irn_t*)phase_alloc(ph, sizeof(mi[0]));
  84         (void) irn;
  85         memset(mi, 0, sizeof(mi[0]));
  86         INIT_LIST_HEAD(&mi->lineage_list);
  87         return mi;
  88 }
  89
  90 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
  91
  92 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
  93 {
  94         const ir_edge_t *edge;
  95
  96         // assert(get_irn_mode(irn) != mode_T);
  97
  98         foreach_out_edge(irn, edge) {
  99                 ir_node *desc = get_edge_src_irn(edge);
 100                 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
 101                         obstack_ptr_grow(&env->obst, desc);
 102                         bitset_add_irn(visited, desc);
 103                 }
 104         }
 105
 106         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 107                 ir_node *desc = get_edge_src_irn(edge);
 108                 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
 109                         obstack_ptr_grow(&env->obst, desc);
 110                         bitset_add_irn(visited, desc);
 111                 }
 112         }
 113 }
 114
 115 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
 116 {
 117         bitset_t *visited = bitset_irg_malloc(env->irg);
 118
 119         grow_all_descendands(env, irn, visited);
 120
 121 #if 0
 122         if (get_irn_mode(irn) == mode_T) {
 123                 const ir_edge_t *edge;
 124                 foreach_out_edge(irn, edge) {
 125                         ir_node *desc = get_edge_src_irn(edge);
 126                         assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
 127                         grow_all_descendands(env, desc, visited);
 128                 }
 129         }
 130
 131         else
 132                 grow_all_descendands(env, irn, visited);
 133 #endif
 134         bitset_free(visited);
 135         obstack_ptr_grow(&env->obst, NULL);
 136         return (ir_node**)obstack_finish(&env->obst);
 137 }
 138
 139 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
 140 {
 141         int lowest_index       = 0;
 142         unsigned lowest_height = INT_MAX;
 143         int i;
 144
 145         for (i = 0; in[i]; ++i) {
 146                 unsigned height = get_irn_height(env->heights, in[i]);
 147                 if (height < lowest_height) {
 148                         lowest_height = height;
 149                         lowest_index  = i;
 150                 }
 151         }
 152
 153         if (i > 0) {
 154                 ir_node *tmp     = in[0];
 155                 in[0]            = in[lowest_index];
 156                 in[lowest_index] = tmp;
 157         }
 158
 159         return in[0];
 160 }
 161
 162 static inline ir_node *skip_Projs(ir_node *irn)
 163 {
 164         return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
 165 }
 166
 167 static void lineage_formation(mris_env_t *env)
 168 {
 169         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
 170         ir_nodeset_t                  nodes;
 171         const ir_edge_t              *edge;
 172
 173         ir_nodeset_init(&nodes);
 174
 175         foreach_out_edge(env->bl, edge) {
 176                 ir_node *irn = get_edge_src_irn(edge);
 177                 if (to_appear(env, irn))
 178                         ir_nodeset_insert(&nodes, irn);
 179         }
 180
 181         while (ir_nodeset_size(&nodes) > 0) {
 182                 mris_irn_t *mi;
 183                 ir_node    *irn;
 184                 ir_node    *highest_node = NULL;
 185                 ir_node    *lowest_desc  = NULL;
 186                 ir_node    *start;
 187                 mris_irn_t *start_mi;
 188                 ir_nodeset_iterator_t iter;
 189
 190                 ir_node **in;
 191                 int recompute_height  = 0;
 192                 unsigned  curr_height = 0;
 193
 194                 /* search the highest node which is not yet in a lineage. */
 195                 foreach_ir_nodeset(&nodes, irn, iter) {
 196                         unsigned height = get_irn_height(env->heights, irn);
 197                         if (height > curr_height) {
 198                                 highest_node = irn;
 199                                 curr_height  = height;
 200                         }
 201                 }
 202
 203                 assert(highest_node);
 204                 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
 205
 206                 start = highest_node;
 207                 mi = start_mi = get_mris_irn(env, highest_node);
 208
 209                 /* start a lineage beginning with highest_node. */
 210                 mi->lineage_start = highest_node;
 211                 mi->lineage_next  = NULL;
 212                 mi->lineage_end   = NULL;
 213                 list_add(&mi->lineage_list, &env->lineage_head);
 214                 ir_nodeset_remove(&nodes, highest_node);
 215
 216                 /*
 217                         put all descendants in an array.
 218                         we also move the lowest descendant in front, so that the other nodes
 219                         are easily accessible as an array, too.
 220                 */
 221                 in          = all_descendants(env, highest_node);
 222                 lowest_desc = put_lowest_in_front(env, in);
 223
 224                 /* as long as the current highest node has still descendants */
 225                 while (lowest_desc) {
 226                         mris_irn_t *lowest_mi  = get_mris_irn(env, lowest_desc);
 227                         mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
 228
 229                         int n_desc;
 230
 231                         DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
 232
 233                         /* count the number of all descendants which are not the lowest descendant */
 234                         for (n_desc = 0; in[n_desc]; ++n_desc) {
 235                         }
 236
 237                         /*
 238                         we insert a CopyKeep node to express the artificial dependencies from the lowest
 239                         descendant to all other descendants.
 240                         */
 241                         if (n_desc > 1 && !be_is_Keep(lowest_desc)) {
 242                                 ir_node *op;
 243                                 int i, n;
 244
 245                                 for (i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
 246                                         op = get_irn_in_or_dep(lowest_desc, i);
 247                                         if (op == highest_node)
 248                                                 break;
 249                                 }
 250
 251                                 assert(i < n && "could not find operand");
 252
 253                                 //replace_tuple_by_repr_proj(env, &in[1]);
 254                                 if (!is_Proj(lowest_desc))
 255                                         add_irn_dep(lowest_desc, in[1]);
 256                         }
 257                         obstack_free(&env->obst, in);
 258
 259                         /* if the current lowest node is not yet in a lineage, add it to the current one. */
 260                         if (!lowest_mi->lineage_start) {
 261                                 /* mark the current lowest node as the last one in the lineage. */
 262                                 highest_mi->lineage_next = lowest_desc;
 263                                 start_mi->lineage_end    = lowest_desc;
 264
 265                                 lowest_mi->lineage_start = start;
 266                                 ir_nodeset_remove(&nodes, lowest_desc);
 267                         }
 268
 269                         /* else we cannot extend this lineage, so break. */
 270                         else
 271                                 break;
 272
 273                         highest_node = lowest_desc;
 274                         highest_mi   = lowest_mi;
 275
 276                         /* recompute the descendants array and the new lowest descendant. */
 277                         in          = all_descendants(env, highest_node);
 278                         lowest_desc = put_lowest_in_front(env, in);
 279                 }
 280
 281                 /* recompute the heights if desired. */
 282                 if (recompute_height)
 283                         heights_recompute(env->heights);
 284         }
 285
 286         ir_nodeset_destroy(&nodes);
 287 }
 288
 289 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
 290 {
 291         mris_irn_t *mi;
 292         ir_node *irn, *last;
 293         ir_node *u_end   = u->lineage_end;
 294         ir_node *v_start = v->lineage_start;
 295         ir_node *start   = skip_Projs(v_start);
 296
 297         if (be_is_Keep(start))
 298                 return 0;
 299
 300         /* set lineage end of nodes in u to end of v. */
 301         irn = last = u->lineage_start;
 302         mi         = get_mris_irn(env, irn);
 303         while (irn && irn != u_end) {
 304                 mi = get_mris_irn(env, irn);
 305                 mi->lineage_end = v->lineage_end;
 306                 last = irn;
 307                 irn = mi->lineage_next;
 308         }
 309
 310         /* insert a CopyKeep to make lineage v dependent on u. */
 311         if (get_irn_ins_or_deps(start) == 0)
 312                 return 0;
 313
 314         if (get_irn_mode(last) == mode_T) {
 315                 const ir_edge_t *edge = get_irn_out_edge_first(last);
 316                 last = get_edge_src_irn(edge);
 317         }
 318
 319         /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
 320         mi->lineage_next       = v_start;
 321
 322         /* add a dependency from the first node in v's lineage to the last in u's */
 323         add_irn_dep(u_end, v_start);
 324
 325         /* set lineage start of nodes in v to start of u. */
 326         irn = v->lineage_start;
 327         while (irn && irn != v->lineage_end) {
 328                 mris_irn_t *mi = get_mris_irn(env, irn);
 329                 mi->lineage_start = u->lineage_start;
 330                 irn = mi->lineage_next;
 331         }
 332
 333         heights_recompute(env->heights);
 334
 335         mi = get_mris_irn(env, v_start);
 336         list_del(&mi->lineage_list);
 337
 338         return 1;
 339 }
 340
 341 static void fuse_lineages(mris_env_t *env)
 342 {
 343         mris_irn_t *u, *v, *tmp1, *tmp2;
 344
 345 again:
 346         foreach_lineage(env, u, tmp1) {
 347                 foreach_lineage(env, v, tmp2) {
 348                         if (u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
 349                                 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
 350                                 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
 351                                 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
 352
 353                                 if (uv && !vu) {
 354                                         if (fuse_two_lineages(env, u, v))
 355                                                 goto again;
 356                                 }
 357                         }
 358                 }
 359         }
 360 }
 361
 362 static mris_env_t *dump_env = NULL;
 363
 364 static void block_walker(ir_node *bl, void *data)
 365 {
 366         mris_env_t *env = (mris_env_t*)data;
 367         env->bl = bl;
 368         lineage_formation(env);
 369         fuse_lineages(env);
 370 }
 371
 372 static void mris_edge_hook(FILE *F, ir_node *irn)
 373 {
 374         mris_irn_t *mi = get_mris_irn(dump_env, irn);
 375
 376         if (mi->lineage_next) {
 377                 fprintf(F, "edge:{sourcename:\"");
 378                 PRINT_NODEID(mi->lineage_next);
 379                 fprintf(F, "\" targetname:\"");
 380                 PRINT_NODEID(irn);
 381                 fprintf(F, "\" color:lilac}\n");
 382         }
 383 }
 384
 385 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix)
 386 {
 387         dump_node_edge_func old = get_dump_node_edge_hook();
 388
 389         set_dump_node_edge_hook(mris_edge_hook);
 390         dump_env = env;
 391         dump_ir_graph(env->irg, suffix);
 392         set_dump_node_edge_hook(old);
 393 }
 394
 395 mris_env_t *be_sched_mris_preprocess(ir_graph *irg)
 396 {
 397         mris_env_t *env = XMALLOC(mris_env_t);
 398
 399         phase_init(&env->ph, irg, mris_irn_data_init);
 400         env->irg      = irg;
 401         env->visited  = 0;
 402         env->heights  = heights_new(irg);
 403         INIT_LIST_HEAD(&env->lineage_head);
 404         FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
 405         obstack_init(&env->obst);
 406         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 407         irg_block_walk_graph(irg, block_walker, NULL, env);
 408         obstack_free(&env->obst, NULL);
 409         // dump_ir_block_graph_mris(env, "-mris");
 410         return env;
 411 }
 412
 413 void be_sched_mris_free(mris_env_t *env)
 414 {
 415         phase_deinit(&env->ph);
 416         heights_free(env->heights);
 417         free(env);
 418 }