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