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

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