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

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