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

   1 /**
   2  * Chordal register allocation.
   3  * @author Sebastian Hack
   4  * @date 8.12.2004
   5  */
   6
   7 #include <ctype.h>
   8
   9 #include "obst.h"
  10 #include "list.h"
  11 #include "bitset.h"
  12 #include "iterator.h"
  13
  14 #include "irmode_t.h"
  15 #include "irprintf_t.h"
  16 #include "irgwalk.h"
  17 #include "irgraph.h"
  18 #include "irdump.h"
  19 #include "irdom.h"
  20 #include "debug.h"
  21 #include "xmalloc.h"
  22
  23 #include "beutil.h"
  24 #include "besched.h"
  25 #include "bera_t.h"
  26 #include "benumb_t.h"
  27 #include "besched_t.h"
  28 #include "belive_t.h"
  29
  30 #undef DUMP_INTERVALS
  31 #undef DUMP_PRESSURE
  32
  33 #define TEST_COLORS 2048
  34
  35 static firm_dbg_module_t *dbg;
  36
  37 /** An interval border. */
  38 typedef struct _border_t {
  39         struct list_head list;          /**< list head for queuing. */
  40         const ir_node *irn;                             /**< The node. */
  41         unsigned step;                                          /**< The number equal to the interval border. */
  42         unsigned is_def : 1;                    /**< Does this border denote a use or a def. */
  43 } border_t;
  44
  45 typedef struct _env_t {
  46         struct obstack obst;    /**< An obstack for temporary storage. */
  47         set *phi_if;                                    /**< The phi interference map. */
  48         bitset_t *live;                 /**< A live bitset to use in every block. */
  49         bitset_t *processed;    /**< A set marking processed blocks. */
  50         bitset_t *colors;                       /**< The color mask. */
  51         bitset_t *in_colors;    /**< Colors used by live in values. */
  52         int colors_n;                                   /**< The number of colors. */
  53 } env_t;
  54
  55 typedef struct _be_chordal_dump_params_t {
  56         int x_dist;
  57         int y_dist;
  58         double font_scale;
  59 } be_chordal_dump_params_t;
  60
  61 static const be_chordal_dump_params_t dump_params = {
  62         30,
  63         10,
  64         4
  65 };
  66
  67 static void draw_interval_graphs(ir_node *block,
  68                 struct list_head *border_head,
  69                 const be_chordal_dump_params_t *params)
  70 {
  71         int i;
  72         int x_dist = params->x_dist;
  73         int y_dist = params->y_dist;
  74         ir_graph *irg = get_irn_irg(block);
  75
  76         FILE *f;
  77         char buf[1024];
  78
  79         ir_snprintf(buf, sizeof(buf), "intv_%s_bl%N.eps",
  80                         get_entity_name(get_irg_entity(irg)), block);
  81
  82         if((f = fopen(buf, "wt")) != NULL) {
  83                 border_t *b;
  84                 int *seen = xcalloc(get_graph_node_count(irg), sizeof(seen[0]));
  85                 int last_pos = list_empty(border_head) ? 0 : list_entry(border_head->prev, border_t, list)->step;
  86                 int max_col = 0;
  87
  88                 list_for_each_entry_reverse(border_t, b, border_head, list) {
  89                         const ir_node *irn = b->irn;
  90                         int col = get_irn_color(irn);
  91                         max_col = max_col > col ? max_col : col;
  92                 }
  93
  94                 fprintf(f, "%%!PS-Adobe-2.0\n");
  95                 fprintf(f, "%%%%BoundingBox: -10 -10 %d %d\n",
  96                                 x_dist * last_pos + x_dist, y_dist * max_col + y_dist);
  97                 fprintf(f, "/mainfont /Courier findfont %f scalefont def\n", params->font_scale);
  98                 fprintf(f, "mainfont setfont\n");
  99                 fprintf(f, "0.2 setlinewidth\n");
 100
 101                 for(i = 0; i <= last_pos; ++i) {
 102                         fprintf(f, "0 0 0 setrgbcolor\n");
 103                         fprintf(f, "%d %d moveto\n", i * x_dist, -2);
 104                         fprintf(f, "%d %d lineto\n", i * x_dist, max_col * y_dist + 2);
 105                         fprintf(f, "stroke\n");
 106                 }
 107                 fprintf(f, "0.5 setlinewidth\n");
 108
 109                 list_for_each_entry_reverse(border_t, b, border_head, list) {
 110                         const ir_node *irn = b->irn;
 111                         int nr = get_irn_graph_nr(irn);
 112
 113                         if(b->is_def)
 114                                 seen[nr] = b->step;
 115                         else {
 116                                 int col = get_irn_color(irn);
 117
 118                                 int pos = last_pos - seen[nr];
 119                                 int end_pos = last_pos - b->step;
 120                                 int live_in = is_live_in(block, irn);
 121                                 int live_end = is_live_end(block, irn);
 122                                 int y_val = y_dist * col;
 123
 124                                 int red = 0;
 125                                 int green = live_end;
 126                                 int blue = live_in;
 127
 128                                 fprintf(f, "0 0 0 setrgbcolor\n");
 129                                 fprintf(f, "%d %d moveto\n", x_dist * pos + 2, y_val + 2);
 130                                 ir_fprintf(f, "(%n/%d%s) show\n", irn, nr, is_phi_operand(irn) ? "*" : "");
 131                                 fprintf(f, "%d %d %d setrgbcolor\n", red, green, blue);
 132                                 fprintf(f, "%d %d moveto\n", x_dist * pos, y_val);
 133                                 fprintf(f, "%d %d lineto\n", (x_dist * end_pos) - 5, y_val);
 134                                 fprintf(f, "stroke\n");
 135                         }
 136                 }
 137
 138                 free(seen);
 139                 fclose(f);
 140         }
 141 }
 142
 143 #ifdef USE_OLD_PHI_INTERFERENCE
 144
 145 typedef struct _if_edge_t {
 146         int src, tgt;
 147 } if_edge_t;
 148
 149 #define IF_EDGE_HASH(e) ((e)->src)
 150
 151 static int if_edge_cmp(const void *p1, const void *p2, size_t size)
 152 {
 153         const if_edge_t *e1 = p1;
 154         const if_edge_t *e2 = p2;
 155
 156         return !(e1->src == e2->src && e1->tgt == e2->tgt);
 157 }
 158
 159 static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt)
 160 {
 161         /* Bring the smaller entry to src. */
 162         if(src > tgt) {
 163                 edge->src = tgt;
 164                 edge->tgt = src;
 165         } else {
 166                 edge->src = src;
 167                 edge->tgt = tgt;
 168         }
 169
 170         return edge;
 171 }
 172
 173 static INLINE void add_if(const env_t *env, int src, int tgt)
 174 {
 175         if_edge_t edge;
 176         edge_init(&edge, src, tgt);
 177         set_insert(env->phi_if, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
 178 }
 179
 180 static INLINE int are_connected(const env_t *env, int src, int tgt)
 181 {
 182         if_edge_t edge;
 183         edge_init(&edge, src, tgt);
 184         return set_find(env->phi_if, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
 185 }
 186
 187 #endif /* USE_OLD_PHI_INTERFERENCE */
 188
 189 static INLINE border_t *border_add(env_t *env, struct list_head *head,
 190                         const ir_node *irn, int step, int is_def)
 191 {
 192         border_t *b = obstack_alloc(&env->obst, sizeof(*b));
 193         b->is_def = is_def;
 194         b->irn = irn;
 195         b->step = step;
 196         list_add_tail(&b->list, head);
 197         return b;
 198 }
 199
 200 static void block_alloc(ir_node *block, void *env_ptr)
 201 {
 202         env_t *env = env_ptr;
 203         struct obstack *obst = &env->obst;
 204         void *obstack_level = obstack_base(obst);
 205         bitset_t *live = env->live;
 206         bitset_t *colors = env->colors;
 207         bitset_t *in_colors = env->in_colors;
 208         bitset_t *used_colors = bitset_malloc(env->colors_n);
 209         bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);
 210         ir_graph *irg = get_irn_irg(block);
 211
 212         int i, n;
 213         unsigned step = 0;
 214         int block_nr = get_block_graph_nr(block);
 215         const ir_node *irn;
 216         border_t *b;
 217         struct list_head head;
 218         pset *live_in = get_live_in(block);
 219         pset *live_end = get_live_end(block);
 220         ir_node *idom = get_Block_idom(block);
 221
 222         /*
 223          * Check, if this block has already been processed, if true, return
 224          * immediately.
 225          */
 226         if(bitset_is_set(env->processed, block_nr))
 227                 return;
 228
 229         /*
 230          * Ensure, that the immediate dominator of this block is allocated
 231          * before this block, since the values live in at this block are
 232          * defined in the dominators of this block. Coloring the dominators
 233          * thus is vital before coloring this block.
 234          */
 235         if(idom)
 236                 block_alloc(idom, env);
 237
 238         /* Clear the live and allocate the color bitset. */
 239         bitset_clear_all(live);
 240         bitset_clear_all(colors);
 241         bitset_clear_all(in_colors);
 242
 243         INIT_LIST_HEAD(&head);
 244
 245         /*
 246          * Make final uses of all values live out of the block.
 247          * They are neccessary to build up real intervals.
 248          */
 249         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 250                 DBG((dbg, LEVEL_3, "Making live: %n/%d\n", irn, get_irn_graph_nr(irn)));
 251                 bitset_set(live, get_irn_graph_nr(irn));
 252                 if(!is_Phi(irn) && is_allocatable_irn(irn))
 253                         border_add(env, &head, irn, step, 0);
 254         }
 255
 256         ++step;
 257
 258         /*
 259          * Determine the last uses of a value inside the block, since they are
 260          * relevant for the interval borders.
 261          */
 262         sched_foreach_reverse(block, irn) {
 263                 DBG((dbg, LEVEL_1, "insn: %n\n", irn));
 264                 DBG((dbg, LEVEL_2, "live: %b\n", live));
 265
 266                 set_irn_color(irn, NO_COLOR);
 267
 268                 /*
 269                  * If the node defines a datab value, i.e. something, registers must
 270                  * be allocated for, add a new def border to the border list.
 271                  */
 272                 if(is_allocatable_irn(irn)) {
 273                         int nr = get_irn_graph_nr(irn);
 274
 275                         bitset_clear(live, nr);
 276                         border_add(env, &head, irn, step, 1);
 277
 278 #ifdef USE_OLD_PHI_INTERFERENCE
 279                         if(is_phi_operand(irn)) {
 280                                 unsigned long elm;
 281                                 bitset_foreach(live, elm) {
 282                                         int live_nr = (int) elm;
 283                                         ir_node *live_irn = get_irn_for_graph_nr(irg, live_nr);
 284                                         if(is_phi_operand(live_irn)) {
 285                                                 DBG((dbg, LEVEL_3, "\t\tinterfering phi operands: %n, %n\n", irn, live_irn));
 286                                                 add_if(env, nr, live_nr);
 287                                         }
 288                                 }
 289                         }
 290 #endif
 291                 }
 292
 293                 /*
 294                  * If the node is no phi node we can examine the uses.
 295                  */
 296                 if(!is_Phi(irn)) {
 297                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 298                                 ir_node *op = get_irn_n(irn, i);
 299
 300                                 if(is_allocatable_irn(op)) {
 301                                         int nr = get_irn_graph_nr(op);
 302
 303                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op));
 304
 305                                         if(!bitset_is_set(live, nr)) {
 306                                                 border_add(env, &head, op, step, 0);
 307                                                 bitset_set(live, nr);
 308                                         }
 309                                 }
 310                         }
 311                 }
 312
 313                 ++step;
 314         }
 315
 316         bitset_clear_all(live);
 317
 318         /*
 319          * Add initial defs for all values live in.
 320          * Since their colors have already been assigned (The dominators were
 321          * allocated before), we have to mark their colors as used also.
 322          */
 323         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 324                 if(is_allocatable_irn(irn)) {
 325                         int col = get_irn_color(irn);
 326
 327                         /* Mark the color of the live in value as used. */
 328                         assert(is_color(col) && "Node must have been assigned a color.");
 329                         bitset_set(colors, col);
 330                         bitset_set(in_colors, col);
 331                         bitset_set(used_colors, col);
 332
 333                         /* Mark the value live in. */
 334                         bitset_set(live, get_irn_graph_nr(irn));
 335
 336                         /* Add the def */
 337                         border_add(env, &head, irn, step, 1);
 338                 }
 339         }
 340
 341         DBG((dbg, LEVEL_4, "usedef chain for block %n\n", block));
 342         list_for_each_entry(border_t, b, &head, list) {
 343                 DBG((dbg, LEVEL_4, "\t%s %n %d\n", b->is_def ? "def" : "use", b->irn, get_irn_graph_nr(b->irn)));
 344         }
 345
 346         /*
 347          * Mind that the sequence of defs from back to front defines a perfect
 348          * elimination order. So, coloring the definitions from first to last
 349          * will work.
 350          */
 351         list_for_each_entry_reverse(border_t, b, &head, list) {
 352                 const ir_node *irn = b->irn;
 353                 int nr = get_irn_graph_nr(irn);
 354
 355                 /*
 356                  * Assign a color, if it is a local def. Global defs already have a
 357                  * color.
 358                  */
 359                 if(b->is_def && !is_live_in(block, irn)) {
 360                         ra_node_info_t *ri = get_ra_node_info(irn);
 361                         int col = NO_COLOR;
 362
 363                         /*
 364                          * Try to assign live out values colors which are not used by live
 365                          * in values.
 366                          */
 367                         if(is_live_out(block, irn)) {
 368                                 bitset_copy(tmp_colors, colors);
 369                                 bitset_andnot(tmp_colors, in_colors);
 370                                 col = bitset_next_clear(tmp_colors, 0);
 371                         }
 372
 373                         /* If a color is not yet assigned, do it now. */
 374                         if(!is_color(col))
 375                                 col = bitset_next_clear(colors, 0);
 376
 377                         assert(!is_color(get_irn_color(irn)) && "Color must not have assigned");
 378                         assert(!bitset_is_set(live, nr) && "Value def must not have been encountered");
 379
 380                         bitset_set(colors, col);
 381                         bitset_set(used_colors, col);
 382                         bitset_set(live, nr);
 383
 384                         ri->color = col;
 385                         ri->pressure = bitset_popcnt(colors);
 386
 387                         DBG((dbg, LEVEL_1, "\tassigning color %d to %n\n", col, irn));
 388                 }
 389
 390                 /* Clear the color upon a use. */
 391                 else if(!b->is_def) {
 392                         int col = get_irn_color(irn);
 393
 394                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 395                         assert(is_color(col) && "A color must have been assigned");
 396
 397                         bitset_clear(colors, col);
 398                         bitset_clear(live, nr);
 399                 }
 400         }
 401
 402 #ifdef DUMP_INTERVALS
 403         draw_interval_graphs(block, &head, &dump_params);
 404 #endif
 405
 406 #ifdef DUMP_PRESSURE
 407         {
 408                 char buf[128];
 409                 FILE *f;
 410
 411                 ir_snprintf(buf, sizeof(buf), "pres_%s_bl_%N.txt",
 412                                 get_entity_name(get_irg_entity(irg)), block);
 413
 414                 if((f = fopen(buf, "wt")) != NULL) {
 415                         sched_foreach_reverse(block, irn) {
 416                                 if(is_allocatable_irn(irn))
 417                                         ir_fprintf(f, "\"%n\" %d %d\n", irn, sched_get_time_step(irn),
 418                                                         get_ra_node_info(irn)->pressure);
 419
 420                         }
 421                         fclose(f);
 422                 }
 423         }
 424 #endif
 425
 426         /*
 427          * Allocate the used colors array in the blocks ra info structure and
 428          * fill it.
 429          */
 430         get_ra_block_info(block)->used_colors = used_colors;
 431
 432         /* Mark this block has processed. */
 433         bitset_set(env->processed, block_nr);
 434
 435         /* Reset the obstack to its initial level */
 436         obstack_free(obst, obstack_level);
 437 }
 438
 439 void be_ra_chordal_init(void)
 440 {
 441         dbg = firm_dbg_register(DBG_BERA);
 442         firm_dbg_set_mask(dbg, -1);
 443 }
 444
 445 void be_ra_chordal(ir_graph *irg)
 446 {
 447         int node_count = get_graph_node_count(irg);
 448         env_t *env = malloc(sizeof(*env));
 449
 450         if(get_irg_dom_state(irg) != dom_consistent)
 451                 compute_doms(irg);
 452
 453         obstack_init(&env->obst);
 454
 455 #ifdef USE_OLD_PHI_INTERFERENCE
 456         env->phi_if = new_set(if_edge_cmp, node_count);
 457 #endif /* USE_OLD_PHI_INTERFERENCE */
 458
 459         env->live = bitset_obstack_alloc(&env->obst, node_count);
 460         env->processed = bitset_obstack_alloc(&env->obst, get_graph_block_count(irg));
 461         env->colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 462         env->in_colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 463         env->colors_n = TEST_COLORS;
 464
 465         irg_block_walk_graph(irg, block_alloc, NULL, env);
 466         obstack_free(&env->obst, NULL);
 467
 468         set_irg_ra_link(irg, env);
 469 }
 470
 471 void be_ra_chordal_done(ir_graph *irg)
 472 {
 473         env_t *env = get_irg_ra_link(irg);
 474         free(env->phi_if);
 475         free(env);
 476 }
 477
 478 int phi_ops_interfere(const ir_node *a, const ir_node *b)
 479 {
 480 #ifdef USE_OLD_PHI_INTERFERENCE
 481         ir_graph *irg = get_irn_irg(a);
 482         env_t *env = get_irg_ra_link(irg);
 483
 484         assert(irg == get_irn_irg(b) && "Both nodes must be in the same graph");
 485
 486         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 487 #else
 488         return values_interfere(a, b);
 489 #endif /* USE_OLD_PHI_INTERFERENCE */
 490 }