nsz Git - libfirm/blob - ir/ana/interval_analysis.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   Implementation of interval analysis
  23  * @version $Id$
  24  */
  25 #include "config.h"
  26
  27 #include <string.h>
  28
  29 #include "debug.h"
  30 #include "interval_analysis.h"
  31 #include "execution_frequency.h"
  32 #include "set.h"
  33 #include "array.h"
  34
  35 #include "irloop.h"
  36 #include "irnode.h"
  37 #include "irdump_t.h"
  38 #include "irdom.h"
  39 #include "irflag.h"
  40 #include "irprintf.h"
  41 #include "hashptr.h"
  42
  43 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  44
  45 /*------------------------------------------------------------------*/
  46 /* A new in array via a hashmap. */
  47 /* The in array refers to the loop the block is contained in if the */
  48 /* block is not in blocks loop. */
  49 /*------------------------------------------------------------------*/
  50
  51 /** The attributes of a region. */
  52 typedef struct {
  53         void *reg;        /**< The region: A block or a loop. */
  54         void **in_array;  /**< New in-array for this region, may contain NULL (to be synchronized with block inputs). */
  55         void **op_array;  /**< If reg is a loop, the control flow operations leading to this loop. */
  56         int n_outs;       /**< The number of out edges of this region. */
  57         int n_exc_outs;   /**< The number of exception out edges of this region. */
  58 } region_attr;
  59
  60 /** A Hashset containing the region attributes. */
  61 static set *region_attr_set = NULL;
  62
  63 /**
  64  * Compare two region attributes for identical regions.
  65  */
  66 static int region_attr_cmp(const void *e1, const void *e2, size_t size) {
  67         region_attr *ra1 = (region_attr *)e1;
  68         region_attr *ra2 = (region_attr *)e2;
  69         (void) size;
  70         return (ra1->reg != ra2->reg);
  71 }
  72
  73 /** Hash a region attribute (the region only). */
  74 static inline int attr_set_hash(region_attr *a) {
  75         return HASH_PTR(a->reg);
  76 }
  77
  78 /**
  79  * Return the region attribute for a given region.
  80  * Allocate one if not exists.
  81  *
  82  * @param region  the region
  83  */
  84 static inline region_attr *get_region_attr(void *region) {
  85         region_attr r_attr, *res;
  86         r_attr.reg = region;
  87
  88         res = set_find(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
  89
  90         if (res == NULL) {
  91                 r_attr.in_array = NEW_ARR_F(void *, 0);
  92                 if (is_ir_loop(region))
  93                         r_attr.op_array = NEW_ARR_F(void *, 0);
  94                 else
  95                         r_attr.op_array = NULL;
  96                 r_attr.n_outs     = 0;
  97                 r_attr.n_exc_outs = 0;
  98                 res = set_insert(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
  99         }
 100
 101         return res;
 102 }
 103
 104 int get_region_n_ins(void *region) {
 105         return ARR_LEN(get_region_attr(region)->in_array);
 106 }
 107
 108 void *get_region_in(void *region, int pos) {
 109         assert(0 <= pos && pos < get_region_n_ins(region));
 110         return ((get_region_attr(region)->in_array)[pos]);
 111 }
 112
 113 void add_region_in(void *region, void *in) {
 114         ARR_APP1(void *, get_region_attr(region)->in_array, in);
 115         get_region_attr(in)->n_outs++;
 116 }
 117
 118 int get_region_n_outs(void *region) {
 119         return get_region_attr(region)->n_outs;
 120 }
 121
 122 int get_region_n_exc_outs(void *region) {
 123         return get_region_attr(region)->n_exc_outs;
 124 }
 125
 126 void inc_region_n_exc_outs(void *region) {
 127         (get_region_attr(region)->n_exc_outs)++;
 128 }
 129
 130 void *get_loop_cfop(void *region, int pos) {
 131         assert(0 <= pos && pos < get_region_n_ins(region));
 132         return ((get_region_attr(region)->op_array)[pos]);
 133 }
 134
 135 /** Add a control flow op to a loop region. */
 136 static inline void add_loop_cfop(void *region, void *cfop) {
 137         assert(cfop);
 138         ARR_APP1(void *, get_region_attr(region)->op_array, cfop);
 139 }
 140
 141 /**
 142  * Increase the number of exception outputs if a control flow
 143  * operation (that is inside the given region) is a fragile operation.
 144  *
 145  * @param reg   a region
 146  * @param cfop  a control flow operation leaving this region
 147  */
 148 static inline void exc_outs(void *reg, ir_node *cfop) {
 149         if (is_fragile_op(cfop) || is_fragile_Proj(cfop))
 150                 inc_region_n_exc_outs(reg);
 151 }
 152
 153 /*------------------------------------------------------------------*/
 154 /* Algorithm to construct the interval edges based on a loop tree. */
 155 /* Walk a loop and add all edges.  Walk inner loops by recursion. */
 156 /*------------------------------------------------------------------*/
 157
 158 /**
 159  * Check if the loop of a given block is the outer loop of the current one.
 160  * If yes, add an edge from the block to the region of the current loop.
 161  *
 162  * @param inner  the current (possible inner) loop
 163  * @param outer  the loop of blk
 164  * @param blk    a block
 165  * @param cfop   the control flow op leaving blk
 166  *
 167  * @return  non-zero if outer can be reached from inner via the outer loop relation
 168  */
 169 static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *blk, ir_node *cfop) {
 170         if (get_loop_outer_loop(inner) == outer) {
 171                 add_region_in(inner, blk);
 172                 add_loop_cfop(inner, cfop);
 173                 exc_outs(blk, cfop);
 174                 return 1;
 175         }
 176         return 0;
 177 }
 178
 179 /**
 180  * Check if a given block can be found in a given loop
 181  * or its nesting loops.
 182  *
 183  * @param blk   a block
 184  * @param loop  a loop
 185  */
 186 static int test_loop_nest(ir_node *blk, ir_loop *loop) {
 187         int i, n_elems = get_loop_n_elements(loop);
 188
 189         for (i = 0; i < n_elems; ++i) {
 190                 loop_element e = get_loop_element(loop, i);
 191                 switch (*e.kind) {
 192                 case k_ir_node:
 193                         if (e.node == blk)
 194                                 return 1;
 195                         break;
 196                 case k_ir_loop:
 197                         if (test_loop_nest(blk, e.son))
 198                                 return 1;
 199                         break;
 200                 default:
 201                         break;
 202                 }
 203         }
 204         return 0;
 205 }
 206
 207 /**
 208  * Check if pred is a block from an inner loop jumping via cfop to the block blk.
 209  * If yes, add an edge from pred's loop to the region blk.
 210
 211  * @param blk   a block
 212  * @param l     the loop of blk
 213  * @param pred  a predecessor block of blk
 214  * @param cfop  the control flow op from pred to blk
 215  *
 216  * @return non-zero if pred is from an inner loop
 217  */
 218 static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfop) {
 219         int i, n_elems = get_loop_n_elements(l);
 220         int found = 0;
 221
 222         for (i = 0; i < n_elems; ++i) {
 223                 loop_element e = get_loop_element(l, i);
 224                 switch (*e.kind) {
 225                 case k_ir_node:
 226                         if (e.node == blk) {
 227                                 /* stop the search if we reach blk, pred cannot be found
 228                                    later in the loop */
 229                                 return 0;
 230                         }
 231                         break;
 232                 case k_ir_loop:
 233                         found = test_loop_nest(pred, e.son);
 234                         if (found) {
 235                                 add_region_in(blk, e.son);
 236                                 exc_outs(e.son, cfop);
 237                                 return found;
 238                         }
 239                         break;
 240                 default:
 241                         break;
 242                 }
 243         }
 244         return found;
 245 }
 246
 247 /**
 248  * Check if a predecessor block pred_b is from a previous loop of the
 249  * block b.
 250  *
 251  * @param l       the loop of the block b
 252  * @param pred_l  the loop of the block pred_b
 253  * @param b       the block
 254  * @param pred_b  the predecessor block
 255  * @param cfop    the control flow node leaving pred_b for b
 256  *
 257  * @return non-zero if pred is from an previous loop
 258  */
 259 static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b,
 260                               ir_node *pred_b, ir_node *cfop)
 261 {
 262         ir_loop *outer = get_loop_outer_loop(l);
 263         int found, i;
 264         int l_pos = get_loop_element_pos(outer, l);
 265         (void) pred_l;
 266         assert(l_pos > -1);
 267         assert(l_pos > 0 && "Is this a necessary condition?  There could be a perfect nest ...");
 268
 269         for (i = l_pos -1, found = 0; i > -1 && !found; --i) {
 270                 ir_loop *k = get_loop_element(outer, i).son;
 271                 if (is_ir_loop(k)) {
 272                         found = test_loop_nest(pred_b, k);
 273                         if (found) {
 274                                 add_region_in(l, k);
 275                                 exc_outs(k, cfop);
 276                                 add_loop_cfop(l, cfop);
 277                                 /* placeholder: the edge is in the loop region */
 278                                 add_region_in(b, NULL);
 279                         }
 280                 }
 281         }
 282
 283         return found;
 284 }
 285
 286
 287 /**
 288  * Compute the edges for the interval graph.
 289  *
 290  * @param blk  The block for which to construct the edges.
 291  * @param l    The loop of blk.
 292  *
 293  * There are four cases:
 294  * - A predecessor block is in the same loop.  Add a normal block-block edge.
 295  * - A predecessor block is in a loop contained in this loop, somewhere down in
 296  *   the nesting.  The predecessor of this block is the outermost loop of the nest
 297  *   directly contained in l.
 298  * - A predecessor block is in the outer loop of l.  l gets an edge to the predecessor block.
 299  * - The outer loop of l contains another loop k just before l.  The control flow
 300  *   branches directly from loop k to loop l.  Add an edge l->k.  Watch it: k must
 301  *   not be a direct predecessor of l in the loop tree!
 302  */
 303 static void construct_interval_block(ir_node *blk, ir_loop *l) {
 304         int i, n_cfgpreds;
 305
 306         if (blk == get_irg_start_block(current_ir_graph))
 307                 return;
 308
 309         n_cfgpreds = get_Block_n_cfgpreds(blk);
 310         /* We want nice blocks. */
 311         assert(n_cfgpreds > 0);
 312
 313         for (i = 0; i < n_cfgpreds; ++i) {
 314                 ir_node *cfop, *pred;
 315                 ir_loop *pred_l;
 316
 317                 if (is_backedge(blk, i)) {
 318                         if (blk != get_loop_element(l, 0).node) {
 319                                 DB((dbg, LEVEL_1, "Loophead not at loop position 0. %+F\n", blk));
 320                         }
 321                         /* There are no backedges in the interval decomposition. */
 322                         add_region_in(blk, NULL);
 323                         continue;
 324                 }
 325
 326                 cfop = get_Block_cfgpred(blk, i);
 327                 if (is_Proj(cfop)) {
 328                         ir_node *op = skip_Proj(cfop);
 329                         if (is_fragile_op(op) && get_Proj_proj(cfop) == pn_Generic_X_except) {
 330                                 /*
 331                                  * Skip the Proj for the exception flow only, leave the
 332                                  * not exception flow Proj's intact.
 333                                  * If the old semantic is used (only one exception Proj) this
 334                                  * should lead to the same representation as before.
 335                                  */
 336                                 cfop = op;
 337                         } else {
 338                                 assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop)));
 339                         }
 340                 }
 341
 342                 pred = skip_Proj(get_nodes_block(cfop));
 343                 /* We want nice blocks. */
 344                 assert(!is_Bad(pred) && !is_Bad(skip_Proj(get_Block_cfgpred(blk, i))));
 345                 pred_l = get_irn_loop(pred);
 346                 if (pred_l == l) {
 347                         /* first case: both blocks are in the same loop */
 348                         add_region_in(blk, pred);
 349                         exc_outs(pred, cfop);
 350                 } else {
 351                         /* check for the second case: pred is from an inner loop */
 352                         int found = find_inner_loop(blk, l, pred, cfop);
 353                         if (!found) {
 354                                 if (blk != get_loop_element(l, 0).node) {
 355                                         DB((dbg, LEVEL_1, "Loop entry not at loop position 0. %+F\n", blk));
 356                                 }
 357                                 /* check for the third case: pred is in an outer loop */
 358                                 found = find_outer_loop(l, pred_l, pred, cfop);
 359                                 if (found) {
 360                                           /* placeholder: the edge is added to the loop region */
 361                                         add_region_in(blk, NULL);
 362                                 } else {
 363                                         /* fourth case: pred is from the previous loop */
 364                                         found = find_previous_loop(l, pred_l, blk, pred, cfop);
 365
 366                                         assert(found && "decomposition failed");
 367                                 }
 368                         }
 369                 }
 370
 371 #ifdef DEBUG_libfirm
 372                 if (blk != get_loop_element(l, 0).node) {
 373                         /* Check for improper region. But these can happen, so what? */
 374                         if (has_backedges(blk)) {
 375                                 DB((dbg, LEVEL_1, "Improper Region %+F\n", blk));
 376                         }
 377                 }
 378 #endif
 379         }
 380 }
 381
 382 /**
 383  * Construct interval edges for a given (control flow) loop.
 384  *
 385  * @param l  the cf loop
 386  */
 387 static void construct_interval_edges(ir_loop *l) {
 388         int i, n_elems = get_loop_n_elements(l);
 389         for (i = 0; i < n_elems; ++i) {
 390                 loop_element e = get_loop_element(l, i);
 391                 switch (*e.kind) {
 392                 case k_ir_node:
 393                         construct_interval_block(e.node, l);
 394                         break;
 395                 case k_ir_loop:
 396                         construct_interval_edges(e.son);
 397                         break;
 398                 default:
 399                         break;
 400                 }
 401         }
 402 }
 403
 404 void construct_intervals(ir_graph *irg) {
 405         ir_loop  *l;
 406         ir_graph *rem = current_ir_graph;
 407
 408         current_ir_graph = irg;
 409
 410         FIRM_DBG_REGISTER(dbg, "firm.ana.interval");
 411
 412         if (region_attr_set == NULL)
 413                 region_attr_set = new_set(region_attr_cmp, 256);
 414
 415         construct_cf_backedges(current_ir_graph);
 416
 417         l = get_irg_loop(current_ir_graph);
 418
 419         construct_interval_edges(l);
 420
 421         current_ir_graph = rem;
 422 }
 423
 424 void free_intervals(void) {
 425         region_attr *res;
 426
 427         if (region_attr_set == NULL)
 428                 return;
 429
 430         for (res = set_first(region_attr_set);
 431              res != NULL;
 432              res = set_next(region_attr_set)) {
 433                 DEL_ARR_F(res->in_array);
 434                 if (res->op_array != NULL)
 435                         DEL_ARR_F(res->op_array);
 436         }
 437
 438         del_set(region_attr_set);
 439         region_attr_set = NULL;
 440 }
 441
 442 /*------------------------------------------------------------------*/
 443 /* A vcg dumper showing an interval decomposition of a cfg.         */
 444 /*                                                                  */
 445 /*------------------------------------------------------------------*/
 446
 447 void dump_region_edges(FILE *F, void *reg) {
 448         int i, n_ins = get_region_n_ins(reg);
 449
 450         if (is_ir_node(reg)) {
 451                 ir_node *irn = reg;
 452                 if (get_Block_n_cfgpreds(irn) > get_region_n_ins(reg)) {
 453                         for (i = n_ins; i < get_Block_n_cfgpreds(irn); ++i) {
 454                                 if (is_backedge(irn, i))
 455                                         fprintf(F, "backedge: { sourcename: \"");
 456                                 else
 457                                         fprintf(F, "edge: { sourcename: \"");
 458                                 PRINT_NODEID(irn);
 459                                 fprintf(F, "\" targetname: \"");
 460                                 PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred(irn, i))));
 461                                 fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
 462                         }
 463                 }
 464         }
 465
 466         for (i = 0; i < n_ins; ++i) {
 467                 void *target = get_region_in(reg, i);
 468
 469                 if (is_ir_node(reg)) {
 470                         ir_node *irn = reg;
 471                         if (get_Block_n_cfgpreds(irn) != get_region_n_ins(reg)) {
 472                                 ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds(irn), get_region_n_ins(reg), irn);
 473                         }
 474                 }
 475
 476                 if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
 477                         assert(is_ir_node(reg));
 478                         if (is_backedge((ir_node *)reg, i))
 479                                 fprintf(F, "backedge: { sourcename: \"");
 480                         else
 481                                 fprintf(F, "edge: { sourcename: \"");
 482                         PRINT_NODEID(((ir_node *)reg));
 483                         fprintf(F, "\" targetname: \"");
 484                         PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
 485                         fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
 486
 487                         if (!target) continue;
 488                 }
 489
 490                 fprintf(F, "edge: { sourcename: \"");
 491                 if (is_ir_node(reg)) {
 492                         PRINT_NODEID(((ir_node *)reg));
 493                 } else {
 494                         PRINT_LOOPID(((ir_loop *)reg));
 495                 }
 496                 fprintf(F, "\" targetname: \"");
 497                 if (is_ir_node(target)) {
 498                         PRINT_NODEID(((ir_node *)target));
 499                 } else {
 500                         PRINT_LOOPID(((ir_loop *)target));
 501                 }
 502                 fprintf(F, "\"");
 503                 if (is_ir_node(reg) && is_fragile_op(skip_Proj(get_Block_cfgpred(reg, i))))
 504                         fprintf(F, EXC_CF_EDGE_ATTR);
 505                 fprintf(F, "}\n");
 506         }
 507 }
 508
 509 #include "execution_frequency.h"
 510
 511 static void dump_interval_block(FILE *F, ir_node *block) {
 512         int i, fl;
 513         /* This is a block. Dump a node for the block. */
 514         fprintf(F, "node: {title: \""); PRINT_NODEID(block);
 515         fprintf(F, "\" label: \"");
 516         if (block == get_irg_start_block(get_irn_irg(block)))
 517                 fprintf(F, "Start ");
 518         if (block == get_irg_end_block(get_irn_irg(block)))
 519                 fprintf(F, "End ");
 520
 521         fprintf(F, "%s ", get_op_name(get_irn_op(block)));
 522         PRINT_NODEID(block);
 523         fprintf(F, " freq: %9.4lf", get_region_exec_freq(block));
 524         fprintf(F, " n_outs: %d", get_region_n_outs(block));
 525         fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(block));
 526         fprintf(F, "\" ");
 527         fprintf(F, "info1:\"");
 528         if (dump_dominator_information_flag)
 529                 fprintf(F, "dom depth %d\n", get_Block_dom_depth(block));
 530
 531         /* show arity and possible Bad predecessors of the block */
 532         fprintf(F, "arity: %d\n", get_Block_n_cfgpreds(block));
 533         for (fl = i = 0; i < get_Block_n_cfgpreds(block); ++i) {
 534                 ir_node *pred = get_Block_cfgpred(block, i);
 535                 if (is_Bad(pred)) {
 536                         if (! fl)
 537                                 fprintf(F, "Bad pred at pos: ");
 538                         fprintf(F, "%d ", i);
 539                         fl = 1;
 540                 }
 541         }
 542         if (fl)
 543                 fprintf(F, "\n");
 544
 545         fprintf(F, "\"");  /* closing quote of info */
 546
 547         if ((block == get_irg_start_block(get_irn_irg(block))) ||
 548                 (block == get_irg_end_block(get_irn_irg(block)))     )
 549                 fprintf(F, " color:blue ");
 550         else if (fl)
 551                 fprintf(F, " color:yellow ");
 552
 553         fprintf(F, "}\n");
 554 }
 555
 556 static void dump_interval_loop(FILE *F, ir_loop *l) {
 557         int i, n_elems = get_loop_n_elements(l);
 558
 559         fprintf(F, "graph: { title: \"");
 560         PRINT_LOOPID(l);
 561         fprintf(F, "\" label: \"loop %d", get_loop_loop_nr(l));
 562         fprintf(F, " freq: %9.4lf", get_region_exec_freq(l));
 563         fprintf(F, " n_outs: %d", get_region_n_outs(l));
 564         fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(l));
 565         fprintf(F, "\" status:clustered color:white \n");
 566
 567         for (i = 0; i < n_elems; ++i) {
 568                 loop_element e = get_loop_element(l, i);
 569                 dump_region_edges(F, e.node);
 570                 switch (*e.kind) {
 571                 case k_ir_node:
 572                         dump_interval_block(F, e.node);
 573                         break;
 574                 case k_ir_loop:
 575                         dump_interval_loop(F, e.son);
 576                         break;
 577                 default:
 578                         break;
 579                 }
 580         }
 581
 582         fprintf(F, "}\n\n");
 583 }
 584
 585
 586 void dump_interval_graph(ir_graph *irg, const char *suffix) {
 587         FILE     *f;
 588         ir_graph *rem;
 589
 590         if (!is_filtered_dump_name(get_entity_ident(get_irg_entity(irg))))
 591                 return;
 592
 593         f = vcg_open(irg, suffix, "-intervals");
 594         dump_vcg_header(f, get_irg_dump_name(irg), NULL, NULL);
 595
 596         rem              = current_ir_graph;
 597         current_ir_graph = irg;
 598
 599         dump_interval_loop(f, get_irg_loop(irg));
 600
 601         dump_vcg_footer(f);
 602         fclose(f);
 603
 604         current_ir_graph = rem;
 605 }