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