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

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