nsz Git - libfirm/blob - ir/ana/interval_analysis.c

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