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

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